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