fs/nilfs2/btree.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * btree.c - NILFS B-tree.
   4  *
   5  * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
   6  *
   7  * Written by Koji Sato.
   8  */
   9
  10 #include <linux/slab.h>
  11 #include <linux/string.h>
  12 #include <linux/errno.h>
  13 #include <linux/pagevec.h>
  14 #include "nilfs.h"
  15 #include "page.h"
  16 #include "btnode.h"
  17 #include "btree.h"
  18 #include "alloc.h"
  19 #include "dat.h"
  20
  21 static void __nilfs_btree_init(struct nilfs_bmap *bmap);
  22
  23 static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
  24 {
  25         struct nilfs_btree_path *path;
  26         int level = NILFS_BTREE_LEVEL_DATA;
  27
  28         path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
  29         if (path == NULL)
  30                 goto out;
  31
  32         for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
  33                 path[level].bp_bh = NULL;
  34                 path[level].bp_sib_bh = NULL;
  35                 path[level].bp_index = 0;
  36                 path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
  37                 path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
  38                 path[level].bp_op = NULL;
  39         }
  40
  41 out:
  42         return path;
  43 }
  44
  45 static void nilfs_btree_free_path(struct nilfs_btree_path *path)
  46 {
  47         int level = NILFS_BTREE_LEVEL_DATA;
  48
  49         for (; level < NILFS_BTREE_LEVEL_MAX; level++)
  50                 brelse(path[level].bp_bh);
  51
  52         kmem_cache_free(nilfs_btree_path_cache, path);
  53 }
  54
  55 /*
  56  * B-tree node operations
  57  */
  58 static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
  59                                      __u64 ptr, struct buffer_head **bhp)
  60 {
  61         struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
  62         struct address_space *btnc = btnc_inode->i_mapping;
  63         struct buffer_head *bh;
  64
  65         bh = nilfs_btnode_create_block(btnc, ptr);
  66         if (!bh)
  67                 return -ENOMEM;
  68
  69         set_buffer_nilfs_volatile(bh);
  70         *bhp = bh;
  71         return 0;
  72 }
  73
  74 static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
  75 {
  76         return node->bn_flags;
  77 }
  78
  79 static void
  80 nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
  81 {
  82         node->bn_flags = flags;
  83 }
  84
  85 static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
  86 {
  87         return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
  88 }
  89
  90 static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
  91 {
  92         return node->bn_level;
  93 }
  94
  95 static void
  96 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
  97 {
  98         node->bn_level = level;
  99 }
 100
 101 static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
 102 {
 103         return le16_to_cpu(node->bn_nchildren);
 104 }
 105
 106 static void
 107 nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
 108 {
 109         node->bn_nchildren = cpu_to_le16(nchildren);
 110 }
 111
 112 static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
 113 {
 114         return i_blocksize(btree->b_inode);
 115 }
 116
 117 static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
 118 {
 119         return btree->b_nchildren_per_block;
 120 }
 121
 122 static __le64 *
 123 nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
 124 {
 125         return (__le64 *)((char *)(node + 1) +
 126                           (nilfs_btree_node_root(node) ?
 127                            0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
 128 }
 129
 130 static __le64 *
 131 nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
 132 {
 133         return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
 134 }
 135
 136 static __u64
 137 nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
 138 {
 139         return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
 140 }
 141
 142 static void
 143 nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
 144 {
 145         *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
 146 }
 147
 148 static __u64
 149 nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
 150                          int ncmax)
 151 {
 152         return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
 153 }
 154
 155 static void
 156 nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
 157                          int ncmax)
 158 {
 159         *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
 160 }
 161
 162 static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
 163                                   int level, int nchildren, int ncmax,
 164                                   const __u64 *keys, const __u64 *ptrs)
 165 {
 166         __le64 *dkeys;
 167         __le64 *dptrs;
 168         int i;
 169
 170         nilfs_btree_node_set_flags(node, flags);
 171         nilfs_btree_node_set_level(node, level);
 172         nilfs_btree_node_set_nchildren(node, nchildren);
 173
 174         dkeys = nilfs_btree_node_dkeys(node);
 175         dptrs = nilfs_btree_node_dptrs(node, ncmax);
 176         for (i = 0; i < nchildren; i++) {
 177                 dkeys[i] = cpu_to_le64(keys[i]);
 178                 dptrs[i] = cpu_to_le64(ptrs[i]);
 179         }
 180 }
 181
 182 /* Assume the buffer heads corresponding to left and right are locked. */
 183 static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
 184                                        struct nilfs_btree_node *right,
 185                                        int n, int lncmax, int rncmax)
 186 {
 187         __le64 *ldkeys, *rdkeys;
 188         __le64 *ldptrs, *rdptrs;
 189         int lnchildren, rnchildren;
 190
 191         ldkeys = nilfs_btree_node_dkeys(left);
 192         ldptrs = nilfs_btree_node_dptrs(left, lncmax);
 193         lnchildren = nilfs_btree_node_get_nchildren(left);
 194
 195         rdkeys = nilfs_btree_node_dkeys(right);
 196         rdptrs = nilfs_btree_node_dptrs(right, rncmax);
 197         rnchildren = nilfs_btree_node_get_nchildren(right);
 198
 199         memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
 200         memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
 201         memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
 202         memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));
 203
 204         lnchildren += n;
 205         rnchildren -= n;
 206         nilfs_btree_node_set_nchildren(left, lnchildren);
 207         nilfs_btree_node_set_nchildren(right, rnchildren);
 208 }
 209
 210 /* Assume that the buffer heads corresponding to left and right are locked. */
 211 static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
 212                                         struct nilfs_btree_node *right,
 213                                         int n, int lncmax, int rncmax)
 214 {
 215         __le64 *ldkeys, *rdkeys;
 216         __le64 *ldptrs, *rdptrs;
 217         int lnchildren, rnchildren;
 218
 219         ldkeys = nilfs_btree_node_dkeys(left);
 220         ldptrs = nilfs_btree_node_dptrs(left, lncmax);
 221         lnchildren = nilfs_btree_node_get_nchildren(left);
 222
 223         rdkeys = nilfs_btree_node_dkeys(right);
 224         rdptrs = nilfs_btree_node_dptrs(right, rncmax);
 225         rnchildren = nilfs_btree_node_get_nchildren(right);
 226
 227         memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
 228         memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
 229         memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
 230         memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));
 231
 232         lnchildren -= n;
 233         rnchildren += n;
 234         nilfs_btree_node_set_nchildren(left, lnchildren);
 235         nilfs_btree_node_set_nchildren(right, rnchildren);
 236 }
 237
 238 /* Assume that the buffer head corresponding to node is locked. */
 239 static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
 240                                     __u64 key, __u64 ptr, int ncmax)
 241 {
 242         __le64 *dkeys;
 243         __le64 *dptrs;
 244         int nchildren;
 245
 246         dkeys = nilfs_btree_node_dkeys(node);
 247         dptrs = nilfs_btree_node_dptrs(node, ncmax);
 248         nchildren = nilfs_btree_node_get_nchildren(node);
 249         if (index < nchildren) {
 250                 memmove(dkeys + index + 1, dkeys + index,
 251                         (nchildren - index) * sizeof(*dkeys));
 252                 memmove(dptrs + index + 1, dptrs + index,
 253                         (nchildren - index) * sizeof(*dptrs));
 254         }
 255         dkeys[index] = cpu_to_le64(key);
 256         dptrs[index] = cpu_to_le64(ptr);
 257         nchildren++;
 258         nilfs_btree_node_set_nchildren(node, nchildren);
 259 }
 260
 261 /* Assume that the buffer head corresponding to node is locked. */
 262 static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
 263                                     __u64 *keyp, __u64 *ptrp, int ncmax)
 264 {
 265         __u64 key;
 266         __u64 ptr;
 267         __le64 *dkeys;
 268         __le64 *dptrs;
 269         int nchildren;
 270
 271         dkeys = nilfs_btree_node_dkeys(node);
 272         dptrs = nilfs_btree_node_dptrs(node, ncmax);
 273         key = le64_to_cpu(dkeys[index]);
 274         ptr = le64_to_cpu(dptrs[index]);
 275         nchildren = nilfs_btree_node_get_nchildren(node);
 276         if (keyp != NULL)
 277                 *keyp = key;
 278         if (ptrp != NULL)
 279                 *ptrp = ptr;
 280
 281         if (index < nchildren - 1) {
 282                 memmove(dkeys + index, dkeys + index + 1,
 283                         (nchildren - index - 1) * sizeof(*dkeys));
 284                 memmove(dptrs + index, dptrs + index + 1,
 285                         (nchildren - index - 1) * sizeof(*dptrs));
 286         }
 287         nchildren--;
 288         nilfs_btree_node_set_nchildren(node, nchildren);
 289 }
 290
 291 static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
 292                                    __u64 key, int *indexp)
 293 {
 294         __u64 nkey;
 295         int index, low, high, s;
 296
 297         /* binary search */
 298         low = 0;
 299         high = nilfs_btree_node_get_nchildren(node) - 1;
 300         index = 0;
 301         s = 0;
 302         while (low <= high) {
 303                 index = (low + high) / 2;
 304                 nkey = nilfs_btree_node_get_key(node, index);
 305                 if (nkey == key) {
 306                         s = 0;
 307                         goto out;
 308                 } else if (nkey < key) {
 309                         low = index + 1;
 310                         s = -1;
 311                 } else {
 312                         high = index - 1;
 313                         s = 1;
 314                 }
 315         }
 316
 317         /* adjust index */
 318         if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
 319                 if (s > 0 && index > 0)
 320                         index--;
 321         } else if (s < 0)
 322                 index++;
 323
 324  out:
 325         *indexp = index;
 326
 327         return s == 0;
 328 }
 329
 330 /**
 331  * nilfs_btree_node_broken - verify consistency of btree node
 332  * @node: btree node block to be examined
 333  * @size: node size (in bytes)
 334  * @inode: host inode of btree
 335  * @blocknr: block number
 336  *
 337  * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 338  */
 339 static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
 340                                    size_t size, struct inode *inode,
 341                                    sector_t blocknr)
 342 {
 343         int level, flags, nchildren;
 344         int ret = 0;
 345
 346         level = nilfs_btree_node_get_level(node);
 347         flags = nilfs_btree_node_get_flags(node);
 348         nchildren = nilfs_btree_node_get_nchildren(node);
 349
 350         if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
 351                      level >= NILFS_BTREE_LEVEL_MAX ||
 352                      (flags & NILFS_BTREE_NODE_ROOT) ||
 353                      nchildren < 0 ||
 354                      nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
 355                 nilfs_crit(inode->i_sb,
 356                            "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
 357                            inode->i_ino, (unsigned long long)blocknr, level,
 358                            flags, nchildren);
 359                 ret = 1;
 360         }
 361         return ret;
 362 }
 363
 364 /**
 365  * nilfs_btree_root_broken - verify consistency of btree root node
 366  * @node: btree root node to be examined
 367  * @inode: host inode of btree
 368  *
 369  * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 370  */
 371 static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
 372                                    struct inode *inode)
 373 {
 374         int level, flags, nchildren;
 375         int ret = 0;
 376
 377         level = nilfs_btree_node_get_level(node);
 378         flags = nilfs_btree_node_get_flags(node);
 379         nchildren = nilfs_btree_node_get_nchildren(node);
 380
 381         if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
 382                      level >= NILFS_BTREE_LEVEL_MAX ||
 383                      nchildren < 0 ||
 384                      nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
 385                 nilfs_crit(inode->i_sb,
 386                            "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
 387                            inode->i_ino, level, flags, nchildren);
 388                 ret = 1;
 389         }
 390         return ret;
 391 }
 392
 393 int nilfs_btree_broken_node_block(struct buffer_head *bh)
 394 {
 395         struct inode *inode;
 396         int ret;
 397
 398         if (buffer_nilfs_checked(bh))
 399                 return 0;
 400
 401         inode = bh->b_page->mapping->host;
 402         ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
 403                                       bh->b_size, inode, bh->b_blocknr);
 404         if (likely(!ret))
 405                 set_buffer_nilfs_checked(bh);
 406         return ret;
 407 }
 408
 409 static struct nilfs_btree_node *
 410 nilfs_btree_get_root(const struct nilfs_bmap *btree)
 411 {
 412         return (struct nilfs_btree_node *)btree->b_u.u_data;
 413 }
 414
 415 static struct nilfs_btree_node *
 416 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
 417 {
 418         return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
 419 }
 420
 421 static struct nilfs_btree_node *
 422 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
 423 {
 424         return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
 425 }
 426
 427 static int nilfs_btree_height(const struct nilfs_bmap *btree)
 428 {
 429         return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
 430 }
 431
 432 static struct nilfs_btree_node *
 433 nilfs_btree_get_node(const struct nilfs_bmap *btree,
 434                      const struct nilfs_btree_path *path,
 435                      int level, int *ncmaxp)
 436 {
 437         struct nilfs_btree_node *node;
 438
 439         if (level == nilfs_btree_height(btree) - 1) {
 440                 node = nilfs_btree_get_root(btree);
 441                 *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
 442         } else {
 443                 node = nilfs_btree_get_nonroot_node(path, level);
 444                 *ncmaxp = nilfs_btree_nchildren_per_block(btree);
 445         }
 446         return node;
 447 }
 448
 449 static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
 450                                 struct nilfs_btree_node *node, int level)
 451 {
 452         if (unlikely(nilfs_btree_node_get_level(node) != level)) {
 453                 dump_stack();
 454                 nilfs_crit(btree->b_inode->i_sb,
 455                            "btree level mismatch (ino=%lu): %d != %d",
 456                            btree->b_inode->i_ino,
 457                            nilfs_btree_node_get_level(node), level);
 458                 return 1;
 459         }
 460         return 0;
 461 }
 462
 463 struct nilfs_btree_readahead_info {
 464         struct nilfs_btree_node *node;  /* parent node */
 465         int max_ra_blocks;              /* max nof blocks to read ahead */
 466         int index;                      /* current index on the parent node */
 467         int ncmax;                      /* nof children in the parent node */
 468 };
 469
 470 static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
 471                                    struct buffer_head **bhp,
 472                                    const struct nilfs_btree_readahead_info *ra)
 473 {
 474         struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
 475         struct address_space *btnc = btnc_inode->i_mapping;
 476         struct buffer_head *bh, *ra_bh;
 477         sector_t submit_ptr = 0;
 478         int ret;
 479
 480         ret = nilfs_btnode_submit_block(btnc, ptr, 0, REQ_OP_READ, 0, &bh,
 481                                         &submit_ptr);
 482         if (ret) {
 483                 if (likely(ret == -EEXIST))
 484                         goto out_check;
 485                 if (ret == -ENOENT) {
 486                         /*
 487                          * Block address translation failed due to invalid
 488                          * value of 'ptr'.  In this case, return internal code
 489                          * -EINVAL (broken bmap) to notify bmap layer of fatal
 490                          * metadata corruption.
 491                          */
 492                         ret = -EINVAL;
 493                 }
 494                 return ret;
 495         }
 496
 497         if (ra) {
 498                 int i, n;
 499                 __u64 ptr2;
 500
 501                 /* read ahead sibling nodes */
 502                 for (n = ra->max_ra_blocks, i = ra->index + 1;
 503                      n > 0 && i < ra->ncmax; n--, i++) {
 504                         ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);
 505
 506                         ret = nilfs_btnode_submit_block(btnc, ptr2, 0,
 507                                                         REQ_OP_READ, REQ_RAHEAD,
 508                                                         &ra_bh, &submit_ptr);
 509                         if (likely(!ret || ret == -EEXIST))
 510                                 brelse(ra_bh);
 511                         else if (ret != -EBUSY)
 512                                 break;
 513                         if (!buffer_locked(bh))
 514                                 goto out_no_wait;
 515                 }
 516         }
 517
 518         wait_on_buffer(bh);
 519
 520  out_no_wait:
 521         if (!buffer_uptodate(bh)) {
 522                 nilfs_err(btree->b_inode->i_sb,
 523                           "I/O error reading b-tree node block (ino=%lu, blocknr=%llu)",
 524                           btree->b_inode->i_ino, (unsigned long long)ptr);
 525                 brelse(bh);
 526                 return -EIO;
 527         }
 528
 529  out_check:
 530         if (nilfs_btree_broken_node_block(bh)) {
 531                 clear_buffer_uptodate(bh);
 532                 brelse(bh);
 533                 return -EINVAL;
 534         }
 535
 536         *bhp = bh;
 537         return 0;
 538 }
 539
 540 static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
 541                                    struct buffer_head **bhp)
 542 {
 543         return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
 544 }
 545
 546 static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
 547                                  struct nilfs_btree_path *path,
 548                                  __u64 key, __u64 *ptrp, int minlevel,
 549                                  int readahead)
 550 {
 551         struct nilfs_btree_node *node;
 552         struct nilfs_btree_readahead_info p, *ra;
 553         __u64 ptr;
 554         int level, index, found, ncmax, ret;
 555
 556         node = nilfs_btree_get_root(btree);
 557         level = nilfs_btree_node_get_level(node);
 558         if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
 559                 return -ENOENT;
 560
 561         found = nilfs_btree_node_lookup(node, key, &index);
 562         ptr = nilfs_btree_node_get_ptr(node, index,
 563                                        NILFS_BTREE_ROOT_NCHILDREN_MAX);
 564         path[level].bp_bh = NULL;
 565         path[level].bp_index = index;
 566
 567         ncmax = nilfs_btree_nchildren_per_block(btree);
 568
 569         while (--level >= minlevel) {
 570                 ra = NULL;
 571                 if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
 572                         p.node = nilfs_btree_get_node(btree, path, level + 1,
 573                                                       &p.ncmax);
 574                         p.index = index;
 575                         p.max_ra_blocks = 7;
 576                         ra = &p;
 577                 }
 578                 ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
 579                                               ra);
 580                 if (ret < 0)
 581                         return ret;
 582
 583                 node = nilfs_btree_get_nonroot_node(path, level);
 584                 if (nilfs_btree_bad_node(btree, node, level))
 585                         return -EINVAL;
 586                 if (!found)
 587                         found = nilfs_btree_node_lookup(node, key, &index);
 588                 else
 589                         index = 0;
 590                 if (index < ncmax) {
 591                         ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
 592                 } else {
 593                         WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
 594                         /* insert */
 595                         ptr = NILFS_BMAP_INVALID_PTR;
 596                 }
 597                 path[level].bp_index = index;
 598         }
 599         if (!found)
 600                 return -ENOENT;
 601
 602         if (ptrp != NULL)
 603                 *ptrp = ptr;
 604
 605         return 0;
 606 }
 607
 608 static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
 609                                       struct nilfs_btree_path *path,
 610                                       __u64 *keyp, __u64 *ptrp)
 611 {
 612         struct nilfs_btree_node *node;
 613         __u64 ptr;
 614         int index, level, ncmax, ret;
 615
 616         node = nilfs_btree_get_root(btree);
 617         index = nilfs_btree_node_get_nchildren(node) - 1;
 618         if (index < 0)
 619                 return -ENOENT;
 620         level = nilfs_btree_node_get_level(node);
 621         ptr = nilfs_btree_node_get_ptr(node, index,
 622                                        NILFS_BTREE_ROOT_NCHILDREN_MAX);
 623         path[level].bp_bh = NULL;
 624         path[level].bp_index = index;
 625         ncmax = nilfs_btree_nchildren_per_block(btree);
 626
 627         for (level--; level > 0; level--) {
 628                 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
 629                 if (ret < 0)
 630                         return ret;
 631                 node = nilfs_btree_get_nonroot_node(path, level);
 632                 if (nilfs_btree_bad_node(btree, node, level))
 633                         return -EINVAL;
 634                 index = nilfs_btree_node_get_nchildren(node) - 1;
 635                 ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
 636                 path[level].bp_index = index;
 637         }
 638
 639         if (keyp != NULL)
 640                 *keyp = nilfs_btree_node_get_key(node, index);
 641         if (ptrp != NULL)
 642                 *ptrp = ptr;
 643
 644         return 0;
 645 }
 646
 647 /**
 648  * nilfs_btree_get_next_key - get next valid key from btree path array
 649  * @btree: bmap struct of btree
 650  * @path: array of nilfs_btree_path struct
 651  * @minlevel: start level
 652  * @nextkey: place to store the next valid key
 653  *
 654  * Return Value: If a next key was found, 0 is returned. Otherwise,
 655  * -ENOENT is returned.
 656  */
 657 static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
 658                                     const struct nilfs_btree_path *path,
 659                                     int minlevel, __u64 *nextkey)
 660 {
 661         struct nilfs_btree_node *node;
 662         int maxlevel = nilfs_btree_height(btree) - 1;
 663         int index, next_adj, level;
 664
 665         /* Next index is already set to bp_index for leaf nodes. */
 666         next_adj = 0;
 667         for (level = minlevel; level <= maxlevel; level++) {
 668                 if (level == maxlevel)
 669                         node = nilfs_btree_get_root(btree);
 670                 else
 671                         node = nilfs_btree_get_nonroot_node(path, level);
 672
 673                 index = path[level].bp_index + next_adj;
 674                 if (index < nilfs_btree_node_get_nchildren(node)) {
 675                         /* Next key is in this node */
 676                         *nextkey = nilfs_btree_node_get_key(node, index);
 677                         return 0;
 678                 }
 679                 /* For non-leaf nodes, next index is stored at bp_index + 1. */
 680                 next_adj = 1;
 681         }
 682         return -ENOENT;
 683 }
 684
 685 static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
 686                               __u64 key, int level, __u64 *ptrp)
 687 {
 688         struct nilfs_btree_path *path;
 689         int ret;
 690
 691         path = nilfs_btree_alloc_path();
 692         if (path == NULL)
 693                 return -ENOMEM;
 694
 695         ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
 696
 697         nilfs_btree_free_path(path);
 698
 699         return ret;
 700 }
 701
 702 static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
 703                                      __u64 key, __u64 *ptrp,
 704                                      unsigned int maxblocks)
 705 {
 706         struct nilfs_btree_path *path;
 707         struct nilfs_btree_node *node;
 708         struct inode *dat = NULL;
 709         __u64 ptr, ptr2;
 710         sector_t blocknr;
 711         int level = NILFS_BTREE_LEVEL_NODE_MIN;
 712         int ret, cnt, index, maxlevel, ncmax;
 713         struct nilfs_btree_readahead_info p;
 714
 715         path = nilfs_btree_alloc_path();
 716         if (path == NULL)
 717                 return -ENOMEM;
 718
 719         ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
 720         if (ret < 0)
 721                 goto out;
 722
 723         if (NILFS_BMAP_USE_VBN(btree)) {
 724                 dat = nilfs_bmap_get_dat(btree);
 725                 ret = nilfs_dat_translate(dat, ptr, &blocknr);
 726                 if (ret < 0)
 727                         goto dat_error;
 728                 ptr = blocknr;
 729         }
 730         cnt = 1;
 731         if (cnt == maxblocks)
 732                 goto end;
 733
 734         maxlevel = nilfs_btree_height(btree) - 1;
 735         node = nilfs_btree_get_node(btree, path, level, &ncmax);
 736         index = path[level].bp_index + 1;
 737         for (;;) {
 738                 while (index < nilfs_btree_node_get_nchildren(node)) {
 739                         if (nilfs_btree_node_get_key(node, index) !=
 740                             key + cnt)
 741                                 goto end;
 742                         ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
 743                         if (dat) {
 744                                 ret = nilfs_dat_translate(dat, ptr2, &blocknr);
 745                                 if (ret < 0)
 746                                         goto dat_error;
 747                                 ptr2 = blocknr;
 748                         }
 749                         if (ptr2 != ptr + cnt || ++cnt == maxblocks)
 750                                 goto end;
 751                         index++;
 752                         continue;
 753                 }
 754                 if (level == maxlevel)
 755                         break;
 756
 757                 /* look-up right sibling node */
 758                 p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
 759                 p.index = path[level + 1].bp_index + 1;
 760                 p.max_ra_blocks = 7;
 761                 if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
 762                     nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
 763                         break;
 764                 ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
 765                 path[level + 1].bp_index = p.index;
 766
 767                 brelse(path[level].bp_bh);
 768                 path[level].bp_bh = NULL;
 769
 770                 ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
 771                                               &p);
 772                 if (ret < 0)
 773                         goto out;
 774                 node = nilfs_btree_get_nonroot_node(path, level);
 775                 ncmax = nilfs_btree_nchildren_per_block(btree);
 776                 index = 0;
 777                 path[level].bp_index = index;
 778         }
 779  end:
 780         *ptrp = ptr;
 781         ret = cnt;
 782  out:
 783         nilfs_btree_free_path(path);
 784         return ret;
 785
 786  dat_error:
 787         if (ret == -ENOENT)
 788                 ret = -EINVAL;  /* Notify bmap layer of metadata corruption */
 789         goto out;
 790 }
 791
 792 static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
 793                                     struct nilfs_btree_path *path,
 794                                     int level, __u64 key)
 795 {
 796         if (level < nilfs_btree_height(btree) - 1) {
 797                 do {
 798                         nilfs_btree_node_set_key(
 799                                 nilfs_btree_get_nonroot_node(path, level),
 800                                 path[level].bp_index, key);
 801                         if (!buffer_dirty(path[level].bp_bh))
 802                                 mark_buffer_dirty(path[level].bp_bh);
 803                 } while ((path[level].bp_index == 0) &&
 804                          (++level < nilfs_btree_height(btree) - 1));
 805         }
 806
 807         /* root */
 808         if (level == nilfs_btree_height(btree) - 1) {
 809                 nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
 810                                          path[level].bp_index, key);
 811         }
 812 }
 813
 814 static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
 815                                   struct nilfs_btree_path *path,
 816                                   int level, __u64 *keyp, __u64 *ptrp)
 817 {
 818         struct nilfs_btree_node *node;
 819         int ncblk;
 820
 821         if (level < nilfs_btree_height(btree) - 1) {
 822                 node = nilfs_btree_get_nonroot_node(path, level);
 823                 ncblk = nilfs_btree_nchildren_per_block(btree);
 824                 nilfs_btree_node_insert(node, path[level].bp_index,
 825                                         *keyp, *ptrp, ncblk);
 826                 if (!buffer_dirty(path[level].bp_bh))
 827                         mark_buffer_dirty(path[level].bp_bh);
 828
 829                 if (path[level].bp_index == 0)
 830                         nilfs_btree_promote_key(btree, path, level + 1,
 831                                                 nilfs_btree_node_get_key(node,
 832                                                                          0));
 833         } else {
 834                 node = nilfs_btree_get_root(btree);
 835                 nilfs_btree_node_insert(node, path[level].bp_index,
 836                                         *keyp, *ptrp,
 837                                         NILFS_BTREE_ROOT_NCHILDREN_MAX);
 838         }
 839 }
 840
 841 static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
 842                                    struct nilfs_btree_path *path,
 843                                    int level, __u64 *keyp, __u64 *ptrp)
 844 {
 845         struct nilfs_btree_node *node, *left;
 846         int nchildren, lnchildren, n, move, ncblk;
 847
 848         node = nilfs_btree_get_nonroot_node(path, level);
 849         left = nilfs_btree_get_sib_node(path, level);
 850         nchildren = nilfs_btree_node_get_nchildren(node);
 851         lnchildren = nilfs_btree_node_get_nchildren(left);
 852         ncblk = nilfs_btree_nchildren_per_block(btree);
 853         move = 0;
 854
 855         n = (nchildren + lnchildren + 1) / 2 - lnchildren;
 856         if (n > path[level].bp_index) {
 857                 /* move insert point */
 858                 n--;
 859                 move = 1;
 860         }
 861
 862         nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
 863
 864         if (!buffer_dirty(path[level].bp_bh))
 865                 mark_buffer_dirty(path[level].bp_bh);
 866         if (!buffer_dirty(path[level].bp_sib_bh))
 867                 mark_buffer_dirty(path[level].bp_sib_bh);
 868
 869         nilfs_btree_promote_key(btree, path, level + 1,
 870                                 nilfs_btree_node_get_key(node, 0));
 871
 872         if (move) {
 873                 brelse(path[level].bp_bh);
 874                 path[level].bp_bh = path[level].bp_sib_bh;
 875                 path[level].bp_sib_bh = NULL;
 876                 path[level].bp_index += lnchildren;
 877                 path[level + 1].bp_index--;
 878         } else {
 879                 brelse(path[level].bp_sib_bh);
 880                 path[level].bp_sib_bh = NULL;
 881                 path[level].bp_index -= n;
 882         }
 883
 884         nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
 885 }
 886
 887 static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
 888                                     struct nilfs_btree_path *path,
 889                                     int level, __u64 *keyp, __u64 *ptrp)
 890 {
 891         struct nilfs_btree_node *node, *right;
 892         int nchildren, rnchildren, n, move, ncblk;
 893
 894         node = nilfs_btree_get_nonroot_node(path, level);
 895         right = nilfs_btree_get_sib_node(path, level);
 896         nchildren = nilfs_btree_node_get_nchildren(node);
 897         rnchildren = nilfs_btree_node_get_nchildren(right);
 898         ncblk = nilfs_btree_nchildren_per_block(btree);
 899         move = 0;
 900
 901         n = (nchildren + rnchildren + 1) / 2 - rnchildren;
 902         if (n > nchildren - path[level].bp_index) {
 903                 /* move insert point */
 904                 n--;
 905                 move = 1;
 906         }
 907
 908         nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
 909
 910         if (!buffer_dirty(path[level].bp_bh))
 911                 mark_buffer_dirty(path[level].bp_bh);
 912         if (!buffer_dirty(path[level].bp_sib_bh))
 913                 mark_buffer_dirty(path[level].bp_sib_bh);
 914
 915         path[level + 1].bp_index++;
 916         nilfs_btree_promote_key(btree, path, level + 1,
 917                                 nilfs_btree_node_get_key(right, 0));
 918         path[level + 1].bp_index--;
 919
 920         if (move) {
 921                 brelse(path[level].bp_bh);
 922                 path[level].bp_bh = path[level].bp_sib_bh;
 923                 path[level].bp_sib_bh = NULL;
 924                 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
 925                 path[level + 1].bp_index++;
 926         } else {
 927                 brelse(path[level].bp_sib_bh);
 928                 path[level].bp_sib_bh = NULL;
 929         }
 930
 931         nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
 932 }
 933
 934 static void nilfs_btree_split(struct nilfs_bmap *btree,
 935                               struct nilfs_btree_path *path,
 936                               int level, __u64 *keyp, __u64 *ptrp)
 937 {
 938         struct nilfs_btree_node *node, *right;
 939         int nchildren, n, move, ncblk;
 940
 941         node = nilfs_btree_get_nonroot_node(path, level);
 942         right = nilfs_btree_get_sib_node(path, level);
 943         nchildren = nilfs_btree_node_get_nchildren(node);
 944         ncblk = nilfs_btree_nchildren_per_block(btree);
 945         move = 0;
 946
 947         n = (nchildren + 1) / 2;
 948         if (n > nchildren - path[level].bp_index) {
 949                 n--;
 950                 move = 1;
 951         }
 952
 953         nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
 954
 955         if (!buffer_dirty(path[level].bp_bh))
 956                 mark_buffer_dirty(path[level].bp_bh);
 957         if (!buffer_dirty(path[level].bp_sib_bh))
 958                 mark_buffer_dirty(path[level].bp_sib_bh);
 959
 960         if (move) {
 961                 path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
 962                 nilfs_btree_node_insert(right, path[level].bp_index,
 963                                         *keyp, *ptrp, ncblk);
 964
 965                 *keyp = nilfs_btree_node_get_key(right, 0);
 966                 *ptrp = path[level].bp_newreq.bpr_ptr;
 967
 968                 brelse(path[level].bp_bh);
 969                 path[level].bp_bh = path[level].bp_sib_bh;
 970                 path[level].bp_sib_bh = NULL;
 971         } else {
 972                 nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
 973
 974                 *keyp = nilfs_btree_node_get_key(right, 0);
 975                 *ptrp = path[level].bp_newreq.bpr_ptr;
 976
 977                 brelse(path[level].bp_sib_bh);
 978                 path[level].bp_sib_bh = NULL;
 979         }
 980
 981         path[level + 1].bp_index++;
 982 }
 983
 984 static void nilfs_btree_grow(struct nilfs_bmap *btree,
 985                              struct nilfs_btree_path *path,
 986                              int level, __u64 *keyp, __u64 *ptrp)
 987 {
 988         struct nilfs_btree_node *root, *child;
 989         int n, ncblk;
 990
 991         root = nilfs_btree_get_root(btree);
 992         child = nilfs_btree_get_sib_node(path, level);
 993         ncblk = nilfs_btree_nchildren_per_block(btree);
 994
 995         n = nilfs_btree_node_get_nchildren(root);
 996
 997         nilfs_btree_node_move_right(root, child, n,
 998                                     NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
 999         nilfs_btree_node_set_level(root, level + 1);
1000
1001         if (!buffer_dirty(path[level].bp_sib_bh))
1002                 mark_buffer_dirty(path[level].bp_sib_bh);
1003
1004         path[level].bp_bh = path[level].bp_sib_bh;
1005         path[level].bp_sib_bh = NULL;
1006
1007         nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
1008
1009         *keyp = nilfs_btree_node_get_key(child, 0);
1010         *ptrp = path[level].bp_newreq.bpr_ptr;
1011 }
1012
1013 static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
1014                                    const struct nilfs_btree_path *path)
1015 {
1016         struct nilfs_btree_node *node;
1017         int level, ncmax;
1018
1019         if (path == NULL)
1020                 return NILFS_BMAP_INVALID_PTR;
1021
1022         /* left sibling */
1023         level = NILFS_BTREE_LEVEL_NODE_MIN;
1024         if (path[level].bp_index > 0) {
1025                 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1026                 return nilfs_btree_node_get_ptr(node,
1027                                                 path[level].bp_index - 1,
1028                                                 ncmax);
1029         }
1030
1031         /* parent */
1032         level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
1033         if (level <= nilfs_btree_height(btree) - 1) {
1034                 node = nilfs_btree_get_node(btree, path, level, &ncmax);
1035                 return nilfs_btree_node_get_ptr(node, path[level].bp_index,
1036                                                 ncmax);
1037         }
1038
1039         return NILFS_BMAP_INVALID_PTR;
1040 }
1041
1042 static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
1043                                        const struct nilfs_btree_path *path,
1044                                        __u64 key)
1045 {
1046         __u64 ptr;
1047
1048         ptr = nilfs_bmap_find_target_seq(btree, key);
1049         if (ptr != NILFS_BMAP_INVALID_PTR)
1050                 /* sequential access */
1051                 return ptr;
1052
1053         ptr = nilfs_btree_find_near(btree, path);
1054         if (ptr != NILFS_BMAP_INVALID_PTR)
1055                 /* near */
1056                 return ptr;
1057
1058         /* block group */
1059         return nilfs_bmap_find_target_in_group(btree);
1060 }
1061
1062 static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1063                                       struct nilfs_btree_path *path,
1064                                       int *levelp, __u64 key, __u64 ptr,
1065                                       struct nilfs_bmap_stats *stats)
1066 {
1067         struct buffer_head *bh;
1068         struct nilfs_btree_node *node, *parent, *sib;
1069         __u64 sibptr;
1070         int pindex, level, ncmax, ncblk, ret;
1071         struct inode *dat = NULL;
1072
1073         stats->bs_nblocks = 0;
1074         level = NILFS_BTREE_LEVEL_DATA;
1075
1076         /* allocate a new ptr for data block */
1077         if (NILFS_BMAP_USE_VBN(btree)) {
1078                 path[level].bp_newreq.bpr_ptr =
1079                         nilfs_btree_find_target_v(btree, path, key);
1080                 dat = nilfs_bmap_get_dat(btree);
1081         }
1082
1083         ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1084         if (ret < 0)
1085                 goto err_out_data;
1086
1087         ncblk = nilfs_btree_nchildren_per_block(btree);
1088
1089         for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1090              level < nilfs_btree_height(btree) - 1;
1091              level++) {
1092                 node = nilfs_btree_get_nonroot_node(path, level);
1093                 if (nilfs_btree_node_get_nchildren(node) < ncblk) {
1094                         path[level].bp_op = nilfs_btree_do_insert;
1095                         stats->bs_nblocks++;
1096                         goto out;
1097                 }
1098
1099                 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1100                 pindex = path[level + 1].bp_index;
1101
1102                 /* left sibling */
1103                 if (pindex > 0) {
1104                         sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
1105                                                           ncmax);
1106                         ret = nilfs_btree_get_block(btree, sibptr, &bh);
1107                         if (ret < 0)
1108                                 goto err_out_child_node;
1109                         sib = (struct nilfs_btree_node *)bh->b_data;
1110                         if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
1111                                 path[level].bp_sib_bh = bh;
1112                                 path[level].bp_op = nilfs_btree_carry_left;
1113                                 stats->bs_nblocks++;
1114                                 goto out;
1115                         } else {
1116                                 brelse(bh);
1117                         }
1118                 }
1119
1120                 /* right sibling */
1121                 if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
1122                         sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
1123                                                           ncmax);
1124                         ret = nilfs_btree_get_block(btree, sibptr, &bh);
1125                         if (ret < 0)
1126                                 goto err_out_child_node;
1127                         sib = (struct nilfs_btree_node *)bh->b_data;
1128                         if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
1129                                 path[level].bp_sib_bh = bh;
1130                                 path[level].bp_op = nilfs_btree_carry_right;
1131                                 stats->bs_nblocks++;
1132                                 goto out;
1133                         } else {
1134                                 brelse(bh);
1135                         }
1136                 }
1137
1138                 /* split */
1139                 path[level].bp_newreq.bpr_ptr =
1140                         path[level - 1].bp_newreq.bpr_ptr + 1;
1141                 ret = nilfs_bmap_prepare_alloc_ptr(btree,
1142                                                    &path[level].bp_newreq, dat);
1143                 if (ret < 0)
1144                         goto err_out_child_node;
1145                 ret = nilfs_btree_get_new_block(btree,
1146                                                 path[level].bp_newreq.bpr_ptr,
1147                                                 &bh);
1148                 if (ret < 0)
1149                         goto err_out_curr_node;
1150
1151                 stats->bs_nblocks++;
1152
1153                 sib = (struct nilfs_btree_node *)bh->b_data;
1154                 nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
1155                 path[level].bp_sib_bh = bh;
1156                 path[level].bp_op = nilfs_btree_split;
1157         }
1158
1159         /* root */
1160         node = nilfs_btree_get_root(btree);
1161         if (nilfs_btree_node_get_nchildren(node) <
1162             NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1163                 path[level].bp_op = nilfs_btree_do_insert;
1164                 stats->bs_nblocks++;
1165                 goto out;
1166         }
1167
1168         /* grow */
1169         path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1170         ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1171         if (ret < 0)
1172                 goto err_out_child_node;
1173         ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
1174                                         &bh);
1175         if (ret < 0)
1176                 goto err_out_curr_node;
1177
1178         nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
1179                               0, level, 0, ncblk, NULL, NULL);
1180         path[level].bp_sib_bh = bh;
1181         path[level].bp_op = nilfs_btree_grow;
1182
1183         level++;
1184         path[level].bp_op = nilfs_btree_do_insert;
1185
1186         /* a newly-created node block and a data block are added */
1187         stats->bs_nblocks += 2;
1188
1189         /* success */
1190  out:
1191         *levelp = level;
1192         return ret;
1193
1194         /* error */
1195  err_out_curr_node:
1196         nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1197  err_out_child_node:
1198         for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
1199                 nilfs_btnode_delete(path[level].bp_sib_bh);
1200                 nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1201
1202         }
1203
1204         nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1205  err_out_data:
1206         *levelp = level;
1207         stats->bs_nblocks = 0;
1208         return ret;
1209 }
1210
1211 static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1212                                       struct nilfs_btree_path *path,
1213                                       int maxlevel, __u64 key, __u64 ptr)
1214 {
1215         struct inode *dat = NULL;
1216         int level;
1217
1218         set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1219         ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1220         if (NILFS_BMAP_USE_VBN(btree)) {
1221                 nilfs_bmap_set_target_v(btree, key, ptr);
1222                 dat = nilfs_bmap_get_dat(btree);
1223         }
1224
1225         for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1226                 nilfs_bmap_commit_alloc_ptr(btree,
1227                                             &path[level - 1].bp_newreq, dat);
1228                 path[level].bp_op(btree, path, level, &key, &ptr);
1229         }
1230
1231         if (!nilfs_bmap_dirty(btree))
1232                 nilfs_bmap_set_dirty(btree);
1233 }
1234
1235 static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1236 {
1237         struct nilfs_btree_path *path;
1238         struct nilfs_bmap_stats stats;
1239         int level, ret;
1240
1241         path = nilfs_btree_alloc_path();
1242         if (path == NULL)
1243                 return -ENOMEM;
1244
1245         ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1246                                     NILFS_BTREE_LEVEL_NODE_MIN, 0);
1247         if (ret != -ENOENT) {
1248                 if (ret == 0)
1249                         ret = -EEXIST;
1250                 goto out;
1251         }
1252
1253         ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
1254         if (ret < 0)
1255                 goto out;
1256         nilfs_btree_commit_insert(btree, path, level, key, ptr);
1257         nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1258
1259  out:
1260         nilfs_btree_free_path(path);
1261         return ret;
1262 }
1263
1264 static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1265                                   struct nilfs_btree_path *path,
1266                                   int level, __u64 *keyp, __u64 *ptrp)
1267 {
1268         struct nilfs_btree_node *node;
1269         int ncblk;
1270
1271         if (level < nilfs_btree_height(btree) - 1) {
1272                 node = nilfs_btree_get_nonroot_node(path, level);
1273                 ncblk = nilfs_btree_nchildren_per_block(btree);
1274                 nilfs_btree_node_delete(node, path[level].bp_index,
1275                                         keyp, ptrp, ncblk);
1276                 if (!buffer_dirty(path[level].bp_bh))
1277                         mark_buffer_dirty(path[level].bp_bh);
1278                 if (path[level].bp_index == 0)
1279                         nilfs_btree_promote_key(btree, path, level + 1,
1280                                 nilfs_btree_node_get_key(node, 0));
1281         } else {
1282                 node = nilfs_btree_get_root(btree);
1283                 nilfs_btree_node_delete(node, path[level].bp_index,
1284                                         keyp, ptrp,
1285                                         NILFS_BTREE_ROOT_NCHILDREN_MAX);
1286         }
1287 }
1288
1289 static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1290                                     struct nilfs_btree_path *path,
1291                                     int level, __u64 *keyp, __u64 *ptrp)
1292 {
1293         struct nilfs_btree_node *node, *left;
1294         int nchildren, lnchildren, n, ncblk;
1295
1296         nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1297
1298         node = nilfs_btree_get_nonroot_node(path, level);
1299         left = nilfs_btree_get_sib_node(path, level);
1300         nchildren = nilfs_btree_node_get_nchildren(node);
1301         lnchildren = nilfs_btree_node_get_nchildren(left);
1302         ncblk = nilfs_btree_nchildren_per_block(btree);
1303
1304         n = (nchildren + lnchildren) / 2 - nchildren;
1305
1306         nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
1307
1308         if (!buffer_dirty(path[level].bp_bh))
1309                 mark_buffer_dirty(path[level].bp_bh);
1310         if (!buffer_dirty(path[level].bp_sib_bh))
1311                 mark_buffer_dirty(path[level].bp_sib_bh);
1312
1313         nilfs_btree_promote_key(btree, path, level + 1,
1314                                 nilfs_btree_node_get_key(node, 0));
1315
1316         brelse(path[level].bp_sib_bh);
1317         path[level].bp_sib_bh = NULL;
1318         path[level].bp_index += n;
1319 }
1320
1321 static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
1322                                      struct nilfs_btree_path *path,
1323                                      int level, __u64 *keyp, __u64 *ptrp)
1324 {
1325         struct nilfs_btree_node *node, *right;
1326         int nchildren, rnchildren, n, ncblk;
1327
1328         nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1329
1330         node = nilfs_btree_get_nonroot_node(path, level);
1331         right = nilfs_btree_get_sib_node(path, level);
1332         nchildren = nilfs_btree_node_get_nchildren(node);
1333         rnchildren = nilfs_btree_node_get_nchildren(right);
1334         ncblk = nilfs_btree_nchildren_per_block(btree);
1335
1336         n = (nchildren + rnchildren) / 2 - nchildren;
1337
1338         nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
1339
1340         if (!buffer_dirty(path[level].bp_bh))
1341                 mark_buffer_dirty(path[level].bp_bh);
1342         if (!buffer_dirty(path[level].bp_sib_bh))
1343                 mark_buffer_dirty(path[level].bp_sib_bh);
1344
1345         path[level + 1].bp_index++;
1346         nilfs_btree_promote_key(btree, path, level + 1,
1347                                 nilfs_btree_node_get_key(right, 0));
1348         path[level + 1].bp_index--;
1349
1350         brelse(path[level].bp_sib_bh);
1351         path[level].bp_sib_bh = NULL;
1352 }
1353
1354 static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
1355                                     struct nilfs_btree_path *path,
1356                                     int level, __u64 *keyp, __u64 *ptrp)
1357 {
1358         struct nilfs_btree_node *node, *left;
1359         int n, ncblk;
1360
1361         nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1362
1363         node = nilfs_btree_get_nonroot_node(path, level);
1364         left = nilfs_btree_get_sib_node(path, level);
1365         ncblk = nilfs_btree_nchildren_per_block(btree);
1366
1367         n = nilfs_btree_node_get_nchildren(node);
1368
1369         nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
1370
1371         if (!buffer_dirty(path[level].bp_sib_bh))
1372                 mark_buffer_dirty(path[level].bp_sib_bh);
1373
1374         nilfs_btnode_delete(path[level].bp_bh);
1375         path[level].bp_bh = path[level].bp_sib_bh;
1376         path[level].bp_sib_bh = NULL;
1377         path[level].bp_index += nilfs_btree_node_get_nchildren(left);
1378 }
1379
1380 static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
1381                                      struct nilfs_btree_path *path,
1382                                      int level, __u64 *keyp, __u64 *ptrp)
1383 {
1384         struct nilfs_btree_node *node, *right;
1385         int n, ncblk;
1386
1387         nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1388
1389         node = nilfs_btree_get_nonroot_node(path, level);
1390         right = nilfs_btree_get_sib_node(path, level);
1391         ncblk = nilfs_btree_nchildren_per_block(btree);
1392
1393         n = nilfs_btree_node_get_nchildren(right);
1394
1395         nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
1396
1397         if (!buffer_dirty(path[level].bp_bh))
1398                 mark_buffer_dirty(path[level].bp_bh);
1399
1400         nilfs_btnode_delete(path[level].bp_sib_bh);
1401         path[level].bp_sib_bh = NULL;
1402         path[level + 1].bp_index++;
1403 }
1404
1405 static void nilfs_btree_shrink(struct nilfs_bmap *btree,
1406                                struct nilfs_btree_path *path,
1407                                int level, __u64 *keyp, __u64 *ptrp)
1408 {
1409         struct nilfs_btree_node *root, *child;
1410         int n, ncblk;
1411
1412         nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
1413
1414         root = nilfs_btree_get_root(btree);
1415         child = nilfs_btree_get_nonroot_node(path, level);
1416         ncblk = nilfs_btree_nchildren_per_block(btree);
1417
1418         nilfs_btree_node_delete(root, 0, NULL, NULL,
1419                                 NILFS_BTREE_ROOT_NCHILDREN_MAX);
1420         nilfs_btree_node_set_level(root, level);
1421         n = nilfs_btree_node_get_nchildren(child);
1422         nilfs_btree_node_move_left(root, child, n,
1423                                    NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
1424
1425         nilfs_btnode_delete(path[level].bp_bh);
1426         path[level].bp_bh = NULL;
1427 }
1428
1429 static void nilfs_btree_nop(struct nilfs_bmap *btree,
1430                             struct nilfs_btree_path *path,
1431                             int level, __u64 *keyp, __u64 *ptrp)
1432 {
1433 }
1434
1435 static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1436                                       struct nilfs_btree_path *path,
1437                                       int *levelp,
1438                                       struct nilfs_bmap_stats *stats,
1439                                       struct inode *dat)
1440 {
1441         struct buffer_head *bh;
1442         struct nilfs_btree_node *node, *parent, *sib;
1443         __u64 sibptr;
1444         int pindex, dindex, level, ncmin, ncmax, ncblk, ret;
1445
1446         ret = 0;
1447         stats->bs_nblocks = 0;
1448         ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1449         ncblk = nilfs_btree_nchildren_per_block(btree);
1450
1451         for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
1452              level < nilfs_btree_height(btree) - 1;
1453              level++) {
1454                 node = nilfs_btree_get_nonroot_node(path, level);
1455                 path[level].bp_oldreq.bpr_ptr =
1456                         nilfs_btree_node_get_ptr(node, dindex, ncblk);
1457                 ret = nilfs_bmap_prepare_end_ptr(btree,
1458                                                  &path[level].bp_oldreq, dat);
1459                 if (ret < 0)
1460                         goto err_out_child_node;
1461
1462                 if (nilfs_btree_node_get_nchildren(node) > ncmin) {
1463                         path[level].bp_op = nilfs_btree_do_delete;
1464                         stats->bs_nblocks++;
1465                         goto out;
1466                 }
1467
1468                 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1469                 pindex = path[level + 1].bp_index;
1470                 dindex = pindex;
1471
1472                 if (pindex > 0) {
1473                         /* left sibling */
1474                         sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
1475                                                           ncmax);
1476                         ret = nilfs_btree_get_block(btree, sibptr, &bh);
1477                         if (ret < 0)
1478                                 goto err_out_curr_node;
1479                         sib = (struct nilfs_btree_node *)bh->b_data;
1480                         if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1481                                 path[level].bp_sib_bh = bh;
1482                                 path[level].bp_op = nilfs_btree_borrow_left;
1483                                 stats->bs_nblocks++;
1484                                 goto out;
1485                         } else {
1486                                 path[level].bp_sib_bh = bh;
1487                                 path[level].bp_op = nilfs_btree_concat_left;
1488                                 stats->bs_nblocks++;
1489                                 /* continue; */
1490                         }
1491                 } else if (pindex <
1492                            nilfs_btree_node_get_nchildren(parent) - 1) {
1493                         /* right sibling */
1494                         sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
1495                                                           ncmax);
1496                         ret = nilfs_btree_get_block(btree, sibptr, &bh);
1497                         if (ret < 0)
1498                                 goto err_out_curr_node;
1499                         sib = (struct nilfs_btree_node *)bh->b_data;
1500                         if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1501                                 path[level].bp_sib_bh = bh;
1502                                 path[level].bp_op = nilfs_btree_borrow_right;
1503                                 stats->bs_nblocks++;
1504                                 goto out;
1505                         } else {
1506                                 path[level].bp_sib_bh = bh;
1507                                 path[level].bp_op = nilfs_btree_concat_right;
1508                                 stats->bs_nblocks++;
1509                                 /*
1510                                  * When merging right sibling node
1511                                  * into the current node, pointer to
1512                                  * the right sibling node must be
1513                                  * terminated instead.  The adjustment
1514                                  * below is required for that.
1515                                  */
1516                                 dindex = pindex + 1;
1517                                 /* continue; */
1518                         }
1519                 } else {
1520                         /* no siblings */
1521                         /* the only child of the root node */
1522                         WARN_ON(level != nilfs_btree_height(btree) - 2);
1523                         if (nilfs_btree_node_get_nchildren(node) - 1 <=
1524                             NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1525                                 path[level].bp_op = nilfs_btree_shrink;
1526                                 stats->bs_nblocks += 2;
1527                                 level++;
1528                                 path[level].bp_op = nilfs_btree_nop;
1529                                 goto shrink_root_child;
1530                         } else {
1531                                 path[level].bp_op = nilfs_btree_do_delete;
1532                                 stats->bs_nblocks++;
1533                                 goto out;
1534                         }
1535                 }
1536         }
1537
1538         /* child of the root node is deleted */
1539         path[level].bp_op = nilfs_btree_do_delete;
1540         stats->bs_nblocks++;
1541
1542 shrink_root_child:
1543         node = nilfs_btree_get_root(btree);
1544         path[level].bp_oldreq.bpr_ptr =
1545                 nilfs_btree_node_get_ptr(node, dindex,
1546                                          NILFS_BTREE_ROOT_NCHILDREN_MAX);
1547
1548         ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
1549         if (ret < 0)
1550                 goto err_out_child_node;
1551
1552         /* success */
1553  out:
1554         *levelp = level;
1555         return ret;
1556
1557         /* error */
1558  err_out_curr_node:
1559         nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1560  err_out_child_node:
1561         for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
1562                 brelse(path[level].bp_sib_bh);
1563                 nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
1564         }
1565         *levelp = level;
1566         stats->bs_nblocks = 0;
1567         return ret;
1568 }
1569
1570 static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
1571                                       struct nilfs_btree_path *path,
1572                                       int maxlevel, struct inode *dat)
1573 {
1574         int level;
1575
1576         for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1577                 nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
1578                 path[level].bp_op(btree, path, level, NULL, NULL);
1579         }
1580
1581         if (!nilfs_bmap_dirty(btree))
1582                 nilfs_bmap_set_dirty(btree);
1583 }
1584
1585 static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
1586
1587 {
1588         struct nilfs_btree_path *path;
1589         struct nilfs_bmap_stats stats;
1590         struct inode *dat;
1591         int level, ret;
1592
1593         path = nilfs_btree_alloc_path();
1594         if (path == NULL)
1595                 return -ENOMEM;
1596
1597         ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1598                                     NILFS_BTREE_LEVEL_NODE_MIN, 0);
1599         if (ret < 0)
1600                 goto out;
1601
1602
1603         dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1604
1605         ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
1606         if (ret < 0)
1607                 goto out;
1608         nilfs_btree_commit_delete(btree, path, level, dat);
1609         nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
1610
1611 out:
1612         nilfs_btree_free_path(path);
1613         return ret;
1614 }
1615
1616 static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
1617                                 __u64 *keyp)
1618 {
1619         struct nilfs_btree_path *path;
1620         const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
1621         int ret;
1622
1623         path = nilfs_btree_alloc_path();
1624         if (!path)
1625                 return -ENOMEM;
1626
1627         ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
1628         if (!ret)
1629                 *keyp = start;
1630         else if (ret == -ENOENT)
1631                 ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
1632
1633         nilfs_btree_free_path(path);
1634         return ret;
1635 }
1636
1637 static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
1638 {
1639         struct nilfs_btree_path *path;
1640         int ret;
1641
1642         path = nilfs_btree_alloc_path();
1643         if (path == NULL)
1644                 return -ENOMEM;
1645
1646         ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
1647
1648         nilfs_btree_free_path(path);
1649
1650         return ret;
1651 }
1652
1653 static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
1654 {
1655         struct buffer_head *bh;
1656         struct nilfs_btree_node *root, *node;
1657         __u64 maxkey, nextmaxkey;
1658         __u64 ptr;
1659         int nchildren, ret;
1660
1661         root = nilfs_btree_get_root(btree);
1662         switch (nilfs_btree_height(btree)) {
1663         case 2:
1664                 bh = NULL;
1665                 node = root;
1666                 break;
1667         case 3:
1668                 nchildren = nilfs_btree_node_get_nchildren(root);
1669                 if (nchildren > 1)
1670                         return 0;
1671                 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1672                                                NILFS_BTREE_ROOT_NCHILDREN_MAX);
1673                 ret = nilfs_btree_get_block(btree, ptr, &bh);
1674                 if (ret < 0)
1675                         return ret;
1676                 node = (struct nilfs_btree_node *)bh->b_data;
1677                 break;
1678         default:
1679                 return 0;
1680         }
1681
1682         nchildren = nilfs_btree_node_get_nchildren(node);
1683         maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
1684         nextmaxkey = (nchildren > 1) ?
1685                 nilfs_btree_node_get_key(node, nchildren - 2) : 0;
1686         if (bh != NULL)
1687                 brelse(bh);
1688
1689         return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
1690 }
1691
1692 static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
1693                                    __u64 *keys, __u64 *ptrs, int nitems)
1694 {
1695         struct buffer_head *bh;
1696         struct nilfs_btree_node *node, *root;
1697         __le64 *dkeys;
1698         __le64 *dptrs;
1699         __u64 ptr;
1700         int nchildren, ncmax, i, ret;
1701
1702         root = nilfs_btree_get_root(btree);
1703         switch (nilfs_btree_height(btree)) {
1704         case 2:
1705                 bh = NULL;
1706                 node = root;
1707                 ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
1708                 break;
1709         case 3:
1710                 nchildren = nilfs_btree_node_get_nchildren(root);
1711                 WARN_ON(nchildren > 1);
1712                 ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
1713                                                NILFS_BTREE_ROOT_NCHILDREN_MAX);
1714                 ret = nilfs_btree_get_block(btree, ptr, &bh);
1715                 if (ret < 0)
1716                         return ret;
1717                 node = (struct nilfs_btree_node *)bh->b_data;
1718                 ncmax = nilfs_btree_nchildren_per_block(btree);
1719                 break;
1720         default:
1721                 node = NULL;
1722                 return -EINVAL;
1723         }
1724
1725         nchildren = nilfs_btree_node_get_nchildren(node);
1726         if (nchildren < nitems)
1727                 nitems = nchildren;
1728         dkeys = nilfs_btree_node_dkeys(node);
1729         dptrs = nilfs_btree_node_dptrs(node, ncmax);
1730         for (i = 0; i < nitems; i++) {
1731                 keys[i] = le64_to_cpu(dkeys[i]);
1732                 ptrs[i] = le64_to_cpu(dptrs[i]);
1733         }
1734
1735         if (bh != NULL)
1736                 brelse(bh);
1737
1738         return nitems;
1739 }
1740
1741 static int
1742 nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
1743                                        union nilfs_bmap_ptr_req *dreq,
1744                                        union nilfs_bmap_ptr_req *nreq,
1745                                        struct buffer_head **bhp,
1746                                        struct nilfs_bmap_stats *stats)
1747 {
1748         struct buffer_head *bh;
1749         struct inode *dat = NULL;
1750         int ret;
1751
1752         stats->bs_nblocks = 0;
1753
1754         /* for data */
1755         /* cannot find near ptr */
1756         if (NILFS_BMAP_USE_VBN(btree)) {
1757                 dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
1758                 dat = nilfs_bmap_get_dat(btree);
1759         }
1760
1761         ret = nilfs_attach_btree_node_cache(&NILFS_BMAP_I(btree)->vfs_inode);
1762         if (ret < 0)
1763                 return ret;
1764
1765         ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
1766         if (ret < 0)
1767                 return ret;
1768
1769         *bhp = NULL;
1770         stats->bs_nblocks++;
1771         if (nreq != NULL) {
1772                 nreq->bpr_ptr = dreq->bpr_ptr + 1;
1773                 ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
1774                 if (ret < 0)
1775                         goto err_out_dreq;
1776
1777                 ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
1778                 if (ret < 0)
1779                         goto err_out_nreq;
1780
1781                 *bhp = bh;
1782                 stats->bs_nblocks++;
1783         }
1784
1785         /* success */
1786         return 0;
1787
1788         /* error */
1789  err_out_nreq:
1790         nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
1791  err_out_dreq:
1792         nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
1793         stats->bs_nblocks = 0;
1794         return ret;
1795
1796 }
1797
1798 static void
1799 nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
1800                                       __u64 key, __u64 ptr,
1801                                       const __u64 *keys, const __u64 *ptrs,
1802                                       int n,
1803                                       union nilfs_bmap_ptr_req *dreq,
1804                                       union nilfs_bmap_ptr_req *nreq,
1805                                       struct buffer_head *bh)
1806 {
1807         struct nilfs_btree_node *node;
1808         struct inode *dat;
1809         __u64 tmpptr;
1810         int ncblk;
1811
1812         /* free resources */
1813         if (btree->b_ops->bop_clear != NULL)
1814                 btree->b_ops->bop_clear(btree);
1815
1816         /* ptr must be a pointer to a buffer head. */
1817         set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
1818
1819         /* convert and insert */
1820         dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
1821         __nilfs_btree_init(btree);
1822         if (nreq != NULL) {
1823                 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1824                 nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
1825
1826                 /* create child node at level 1 */
1827                 node = (struct nilfs_btree_node *)bh->b_data;
1828                 ncblk = nilfs_btree_nchildren_per_block(btree);
1829                 nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
1830                 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
1831                 if (!buffer_dirty(bh))
1832                         mark_buffer_dirty(bh);
1833                 if (!nilfs_bmap_dirty(btree))
1834                         nilfs_bmap_set_dirty(btree);
1835
1836                 brelse(bh);
1837
1838                 /* create root node at level 2 */
1839                 node = nilfs_btree_get_root(btree);
1840                 tmpptr = nreq->bpr_ptr;
1841                 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
1842                                       NILFS_BTREE_ROOT_NCHILDREN_MAX,
1843                                       &keys[0], &tmpptr);
1844         } else {
1845                 nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
1846
1847                 /* create root node at level 1 */
1848                 node = nilfs_btree_get_root(btree);
1849                 nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
1850                                       NILFS_BTREE_ROOT_NCHILDREN_MAX,
1851                                       keys, ptrs);
1852                 nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
1853                                         NILFS_BTREE_ROOT_NCHILDREN_MAX);
1854                 if (!nilfs_bmap_dirty(btree))
1855                         nilfs_bmap_set_dirty(btree);
1856         }
1857
1858         if (NILFS_BMAP_USE_VBN(btree))
1859                 nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
1860 }
1861
1862 /**
1863  * nilfs_btree_convert_and_insert -
1864  * @bmap:
1865  * @key:
1866  * @ptr:
1867  * @keys:
1868  * @ptrs:
1869  * @n:
1870  */
1871 int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
1872                                    __u64 key, __u64 ptr,
1873                                    const __u64 *keys, const __u64 *ptrs, int n)
1874 {
1875         struct buffer_head *bh = NULL;
1876         union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
1877         struct nilfs_bmap_stats stats;
1878         int ret;
1879
1880         if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1881                 di = &dreq;
1882                 ni = NULL;
1883         } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
1884                            nilfs_btree_node_size(btree))) {
1885                 di = &dreq;
1886                 ni = &nreq;
1887         } else {
1888                 di = NULL;
1889                 ni = NULL;
1890                 BUG();
1891         }
1892
1893         ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
1894                                                      &stats);
1895         if (ret < 0)
1896                 return ret;
1897         nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
1898                                               di, ni, bh);
1899         nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1900         return 0;
1901 }
1902
1903 static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
1904                                    struct nilfs_btree_path *path,
1905                                    int level,
1906                                    struct buffer_head *bh)
1907 {
1908         while ((++level < nilfs_btree_height(btree) - 1) &&
1909                !buffer_dirty(path[level].bp_bh))
1910                 mark_buffer_dirty(path[level].bp_bh);
1911
1912         return 0;
1913 }
1914
1915 static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
1916                                         struct nilfs_btree_path *path,
1917                                         int level, struct inode *dat)
1918 {
1919         struct nilfs_btree_node *parent;
1920         int ncmax, ret;
1921
1922         parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1923         path[level].bp_oldreq.bpr_ptr =
1924                 nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
1925                                          ncmax);
1926         path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
1927         ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
1928                                        &path[level].bp_newreq.bpr_req);
1929         if (ret < 0)
1930                 return ret;
1931
1932         if (buffer_nilfs_node(path[level].bp_bh)) {
1933                 path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
1934                 path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
1935                 path[level].bp_ctxt.bh = path[level].bp_bh;
1936                 ret = nilfs_btnode_prepare_change_key(
1937                         NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1938                         &path[level].bp_ctxt);
1939                 if (ret < 0) {
1940                         nilfs_dat_abort_update(dat,
1941                                                &path[level].bp_oldreq.bpr_req,
1942                                                &path[level].bp_newreq.bpr_req);
1943                         return ret;
1944                 }
1945         }
1946
1947         return 0;
1948 }
1949
1950 static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
1951                                         struct nilfs_btree_path *path,
1952                                         int level, struct inode *dat)
1953 {
1954         struct nilfs_btree_node *parent;
1955         int ncmax;
1956
1957         nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
1958                                 &path[level].bp_newreq.bpr_req,
1959                                 btree->b_ptr_type == NILFS_BMAP_PTR_VS);
1960
1961         if (buffer_nilfs_node(path[level].bp_bh)) {
1962                 nilfs_btnode_commit_change_key(
1963                         NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1964                         &path[level].bp_ctxt);
1965                 path[level].bp_bh = path[level].bp_ctxt.bh;
1966         }
1967         set_buffer_nilfs_volatile(path[level].bp_bh);
1968
1969         parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1970         nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
1971                                  path[level].bp_newreq.bpr_ptr, ncmax);
1972 }
1973
1974 static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
1975                                        struct nilfs_btree_path *path,
1976                                        int level, struct inode *dat)
1977 {
1978         nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
1979                                &path[level].bp_newreq.bpr_req);
1980         if (buffer_nilfs_node(path[level].bp_bh))
1981                 nilfs_btnode_abort_change_key(
1982                         NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
1983                         &path[level].bp_ctxt);
1984 }
1985
1986 static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
1987                                            struct nilfs_btree_path *path,
1988                                            int minlevel, int *maxlevelp,
1989                                            struct inode *dat)
1990 {
1991         int level, ret;
1992
1993         level = minlevel;
1994         if (!buffer_nilfs_volatile(path[level].bp_bh)) {
1995                 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
1996                 if (ret < 0)
1997                         return ret;
1998         }
1999         while ((++level < nilfs_btree_height(btree) - 1) &&
2000                !buffer_dirty(path[level].bp_bh)) {
2001
2002                 WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
2003                 ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
2004                 if (ret < 0)
2005                         goto out;
2006         }
2007
2008         /* success */
2009         *maxlevelp = level - 1;
2010         return 0;
2011
2012         /* error */
2013  out:
2014         while (--level > minlevel)
2015                 nilfs_btree_abort_update_v(btree, path, level, dat);
2016         if (!buffer_nilfs_volatile(path[level].bp_bh))
2017                 nilfs_btree_abort_update_v(btree, path, level, dat);
2018         return ret;
2019 }
2020
2021 static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
2022                                            struct nilfs_btree_path *path,
2023                                            int minlevel, int maxlevel,
2024                                            struct buffer_head *bh,
2025                                            struct inode *dat)
2026 {
2027         int level;
2028
2029         if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
2030                 nilfs_btree_commit_update_v(btree, path, minlevel, dat);
2031
2032         for (level = minlevel + 1; level <= maxlevel; level++)
2033                 nilfs_btree_commit_update_v(btree, path, level, dat);
2034 }
2035
2036 static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
2037                                    struct nilfs_btree_path *path,
2038                                    int level, struct buffer_head *bh)
2039 {
2040         int maxlevel = 0, ret;
2041         struct nilfs_btree_node *parent;
2042         struct inode *dat = nilfs_bmap_get_dat(btree);
2043         __u64 ptr;
2044         int ncmax;
2045
2046         get_bh(bh);
2047         path[level].bp_bh = bh;
2048         ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
2049                                               dat);
2050         if (ret < 0)
2051                 goto out;
2052
2053         if (buffer_nilfs_volatile(path[level].bp_bh)) {
2054                 parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2055                 ptr = nilfs_btree_node_get_ptr(parent,
2056                                                path[level + 1].bp_index,
2057                                                ncmax);
2058                 ret = nilfs_dat_mark_dirty(dat, ptr);
2059                 if (ret < 0)
2060                         goto out;
2061         }
2062
2063         nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
2064
2065  out:
2066         brelse(path[level].bp_bh);
2067         path[level].bp_bh = NULL;
2068         return ret;
2069 }
2070
2071 static int nilfs_btree_propagate(struct nilfs_bmap *btree,
2072                                  struct buffer_head *bh)
2073 {
2074         struct nilfs_btree_path *path;
2075         struct nilfs_btree_node *node;
2076         __u64 key;
2077         int level, ret;
2078
2079         WARN_ON(!buffer_dirty(bh));
2080
2081         path = nilfs_btree_alloc_path();
2082         if (path == NULL)
2083                 return -ENOMEM;
2084
2085         if (buffer_nilfs_node(bh)) {
2086                 node = (struct nilfs_btree_node *)bh->b_data;
2087                 key = nilfs_btree_node_get_key(node, 0);
2088                 level = nilfs_btree_node_get_level(node);
2089         } else {
2090                 key = nilfs_bmap_data_get_key(btree, bh);
2091                 level = NILFS_BTREE_LEVEL_DATA;
2092         }
2093
2094         ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2095         if (ret < 0) {
2096                 if (unlikely(ret == -ENOENT))
2097                         nilfs_crit(btree->b_inode->i_sb,
2098                                    "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d",
2099                                    btree->b_inode->i_ino,
2100                                    (unsigned long long)key, level);
2101                 goto out;
2102         }
2103
2104         ret = NILFS_BMAP_USE_VBN(btree) ?
2105                 nilfs_btree_propagate_v(btree, path, level, bh) :
2106                 nilfs_btree_propagate_p(btree, path, level, bh);
2107
2108  out:
2109         nilfs_btree_free_path(path);
2110
2111         return ret;
2112 }
2113
2114 static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
2115                                     struct buffer_head *bh)
2116 {
2117         return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
2118 }
2119
2120 static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
2121                                          struct list_head *lists,
2122                                          struct buffer_head *bh)
2123 {
2124         struct list_head *head;
2125         struct buffer_head *cbh;
2126         struct nilfs_btree_node *node, *cnode;
2127         __u64 key, ckey;
2128         int level;
2129
2130         get_bh(bh);
2131         node = (struct nilfs_btree_node *)bh->b_data;
2132         key = nilfs_btree_node_get_key(node, 0);
2133         level = nilfs_btree_node_get_level(node);
2134         if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
2135             level >= NILFS_BTREE_LEVEL_MAX) {
2136                 dump_stack();
2137                 nilfs_warn(btree->b_inode->i_sb,
2138                            "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
2139                            level, (unsigned long long)key,
2140                            btree->b_inode->i_ino,
2141                            (unsigned long long)bh->b_blocknr);
2142                 return;
2143         }
2144
2145         list_for_each(head, &lists[level]) {
2146                 cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
2147                 cnode = (struct nilfs_btree_node *)cbh->b_data;
2148                 ckey = nilfs_btree_node_get_key(cnode, 0);
2149                 if (key < ckey)
2150                         break;
2151         }
2152         list_add_tail(&bh->b_assoc_buffers, head);
2153 }
2154
2155 static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
2156                                              struct list_head *listp)
2157 {
2158         struct inode *btnc_inode = NILFS_BMAP_I(btree)->i_assoc_inode;
2159         struct address_space *btcache = btnc_inode->i_mapping;
2160         struct list_head lists[NILFS_BTREE_LEVEL_MAX];
2161         struct pagevec pvec;
2162         struct buffer_head *bh, *head;
2163         pgoff_t index = 0;
2164         int level, i;
2165
2166         for (level = NILFS_BTREE_LEVEL_NODE_MIN;
2167              level < NILFS_BTREE_LEVEL_MAX;
2168              level++)
2169                 INIT_LIST_HEAD(&lists[level]);
2170
2171         pagevec_init(&pvec);
2172
2173         while (pagevec_lookup_tag(&pvec, btcache, &index,
2174                                         PAGECACHE_TAG_DIRTY)) {
2175                 for (i = 0; i < pagevec_count(&pvec); i++) {
2176                         bh = head = page_buffers(pvec.pages[i]);
2177                         do {
2178                                 if (buffer_dirty(bh))
2179                                         nilfs_btree_add_dirty_buffer(btree,
2180                                                                      lists, bh);
2181                         } while ((bh = bh->b_this_page) != head);
2182                 }
2183                 pagevec_release(&pvec);
2184                 cond_resched();
2185         }
2186
2187         for (level = NILFS_BTREE_LEVEL_NODE_MIN;
2188              level < NILFS_BTREE_LEVEL_MAX;
2189              level++)
2190                 list_splice_tail(&lists[level], listp);
2191 }
2192
2193 static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
2194                                 struct nilfs_btree_path *path,
2195                                 int level,
2196                                 struct buffer_head **bh,
2197                                 sector_t blocknr,
2198                                 union nilfs_binfo *binfo)
2199 {
2200         struct nilfs_btree_node *parent;
2201         __u64 key;
2202         __u64 ptr;
2203         int ncmax, ret;
2204
2205         parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2206         ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2207                                        ncmax);
2208         if (buffer_nilfs_node(*bh)) {
2209                 path[level].bp_ctxt.oldkey = ptr;
2210                 path[level].bp_ctxt.newkey = blocknr;
2211                 path[level].bp_ctxt.bh = *bh;
2212                 ret = nilfs_btnode_prepare_change_key(
2213                         NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2214                         &path[level].bp_ctxt);
2215                 if (ret < 0)
2216                         return ret;
2217                 nilfs_btnode_commit_change_key(
2218                         NILFS_BMAP_I(btree)->i_assoc_inode->i_mapping,
2219                         &path[level].bp_ctxt);
2220                 *bh = path[level].bp_ctxt.bh;
2221         }
2222
2223         nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
2224                                  ncmax);
2225
2226         key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2227         /* on-disk format */
2228         binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
2229         binfo->bi_dat.bi_level = level;
2230
2231         return 0;
2232 }
2233
2234 static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
2235                                 struct nilfs_btree_path *path,
2236                                 int level,
2237                                 struct buffer_head **bh,
2238                                 sector_t blocknr,
2239                                 union nilfs_binfo *binfo)
2240 {
2241         struct nilfs_btree_node *parent;
2242         struct inode *dat = nilfs_bmap_get_dat(btree);
2243         __u64 key;
2244         __u64 ptr;
2245         union nilfs_bmap_ptr_req req;
2246         int ncmax, ret;
2247
2248         parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
2249         ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
2250                                        ncmax);
2251         req.bpr_ptr = ptr;
2252         ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
2253         if (ret < 0)
2254                 return ret;
2255         nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);
2256
2257         key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
2258         /* on-disk format */
2259         binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
2260         binfo->bi_v.bi_blkoff = cpu_to_le64(key);
2261
2262         return 0;
2263 }
2264
2265 static int nilfs_btree_assign(struct nilfs_bmap *btree,
2266                               struct buffer_head **bh,
2267                               sector_t blocknr,
2268                               union nilfs_binfo *binfo)
2269 {
2270         struct nilfs_btree_path *path;
2271         struct nilfs_btree_node *node;
2272         __u64 key;
2273         int level, ret;
2274
2275         path = nilfs_btree_alloc_path();
2276         if (path == NULL)
2277                 return -ENOMEM;
2278
2279         if (buffer_nilfs_node(*bh)) {
2280                 node = (struct nilfs_btree_node *)(*bh)->b_data;
2281                 key = nilfs_btree_node_get_key(node, 0);
2282                 level = nilfs_btree_node_get_level(node);
2283         } else {
2284                 key = nilfs_bmap_data_get_key(btree, *bh);
2285                 level = NILFS_BTREE_LEVEL_DATA;
2286         }
2287
2288         ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
2289         if (ret < 0) {
2290                 WARN_ON(ret == -ENOENT);
2291                 goto out;
2292         }
2293
2294         ret = NILFS_BMAP_USE_VBN(btree) ?
2295                 nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
2296                 nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
2297
2298  out:
2299         nilfs_btree_free_path(path);
2300
2301         return ret;
2302 }
2303
2304 static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
2305                                  struct buffer_head **bh,
2306                                  sector_t blocknr,
2307                                  union nilfs_binfo *binfo)
2308 {
2309         struct nilfs_btree_node *node;
2310         __u64 key;
2311         int ret;
2312
2313         ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
2314                              blocknr);
2315         if (ret < 0)
2316                 return ret;
2317
2318         if (buffer_nilfs_node(*bh)) {
2319                 node = (struct nilfs_btree_node *)(*bh)->b_data;
2320                 key = nilfs_btree_node_get_key(node, 0);
2321         } else
2322                 key = nilfs_bmap_data_get_key(btree, *bh);
2323
2324         /* on-disk format */
2325         binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
2326         binfo->bi_v.bi_blkoff = cpu_to_le64(key);
2327
2328         return 0;
2329 }
2330
2331 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
2332 {
2333         struct buffer_head *bh;
2334         struct nilfs_btree_path *path;
2335         __u64 ptr;
2336         int ret;
2337
2338         path = nilfs_btree_alloc_path();
2339         if (path == NULL)
2340                 return -ENOMEM;
2341
2342         ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
2343         if (ret < 0) {
2344                 WARN_ON(ret == -ENOENT);
2345                 goto out;
2346         }
2347         ret = nilfs_btree_get_block(btree, ptr, &bh);
2348         if (ret < 0) {
2349                 WARN_ON(ret == -ENOENT);
2350                 goto out;
2351         }
2352
2353         if (!buffer_dirty(bh))
2354                 mark_buffer_dirty(bh);
2355         brelse(bh);
2356         if (!nilfs_bmap_dirty(btree))
2357                 nilfs_bmap_set_dirty(btree);
2358
2359  out:
2360         nilfs_btree_free_path(path);
2361         return ret;
2362 }
2363
2364 static const struct nilfs_bmap_operations nilfs_btree_ops = {
2365         .bop_lookup             =       nilfs_btree_lookup,
2366         .bop_lookup_contig      =       nilfs_btree_lookup_contig,
2367         .bop_insert             =       nilfs_btree_insert,
2368         .bop_delete             =       nilfs_btree_delete,
2369         .bop_clear              =       NULL,
2370
2371         .bop_propagate          =       nilfs_btree_propagate,
2372
2373         .bop_lookup_dirty_buffers =     nilfs_btree_lookup_dirty_buffers,
2374
2375         .bop_assign             =       nilfs_btree_assign,
2376         .bop_mark               =       nilfs_btree_mark,
2377
2378         .bop_seek_key           =       nilfs_btree_seek_key,
2379         .bop_last_key           =       nilfs_btree_last_key,
2380
2381         .bop_check_insert       =       NULL,
2382         .bop_check_delete       =       nilfs_btree_check_delete,
2383         .bop_gather_data        =       nilfs_btree_gather_data,
2384 };
2385
2386 static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
2387         .bop_lookup             =       NULL,
2388         .bop_lookup_contig      =       NULL,
2389         .bop_insert             =       NULL,
2390         .bop_delete             =       NULL,
2391         .bop_clear              =       NULL,
2392
2393         .bop_propagate          =       nilfs_btree_propagate_gc,
2394
2395         .bop_lookup_dirty_buffers =     nilfs_btree_lookup_dirty_buffers,
2396
2397         .bop_assign             =       nilfs_btree_assign_gc,
2398         .bop_mark               =       NULL,
2399
2400         .bop_seek_key           =       NULL,
2401         .bop_last_key           =       NULL,
2402
2403         .bop_check_insert       =       NULL,
2404         .bop_check_delete       =       NULL,
2405         .bop_gather_data        =       NULL,
2406 };
2407
2408 static void __nilfs_btree_init(struct nilfs_bmap *bmap)
2409 {
2410         bmap->b_ops = &nilfs_btree_ops;
2411         bmap->b_nchildren_per_block =
2412                 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
2413 }
2414
2415 int nilfs_btree_init(struct nilfs_bmap *bmap)
2416 {
2417         int ret = 0;
2418
2419         __nilfs_btree_init(bmap);
2420
2421         if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap), bmap->b_inode))
2422                 ret = -EIO;
2423         else
2424                 ret = nilfs_attach_btree_node_cache(
2425                         &NILFS_BMAP_I(bmap)->vfs_inode);
2426
2427         return ret;
2428 }
2429
2430 void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
2431 {
2432         bmap->b_ops = &nilfs_btree_ops_gc;
2433         bmap->b_nchildren_per_block =
2434                 NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
2435 }