fs/nilfs2/btree.c

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