SAFE public projects git trees. - safe/jmp/linux-2.6/blob - fs/nilfs2/btree.c

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