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