btree.c 61.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
/*
 * btree.c - NILFS B-tree.
 *
 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Written by Koji Sato <koji@osrg.net>.
 */

#include <linux/slab.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/pagevec.h>
#include "nilfs.h"
#include "page.h"
#include "btnode.h"
#include "btree.h"
#include "alloc.h"
32
#include "dat.h"
33

34 35
static void __nilfs_btree_init(struct nilfs_bmap *bmap);

36
static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
37
{
38 39
	struct nilfs_btree_path *path;
	int level = NILFS_BTREE_LEVEL_DATA;
40

41 42 43
	path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
	if (path == NULL)
		goto out;
44

45
	for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
46 47 48 49 50 51 52
		path[level].bp_bh = NULL;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index = 0;
		path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_op = NULL;
	}
53 54 55 56 57

out:
	return path;
}

58
static void nilfs_btree_free_path(struct nilfs_btree_path *path)
59
{
60
	int level = NILFS_BTREE_LEVEL_DATA;
61

62
	for (; level < NILFS_BTREE_LEVEL_MAX; level++)
63
		brelse(path[level].bp_bh);
64 65

	kmem_cache_free(nilfs_btree_path_cache, path);
66 67 68 69 70
}

/*
 * B-tree node operations
 */
71
static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
72 73
				     __u64 ptr, struct buffer_head **bhp)
{
74
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
75
	struct buffer_head *bh;
76

77 78 79 80 81 82 83
	bh = nilfs_btnode_create_block(btnc, ptr);
	if (!bh)
		return -ENOMEM;

	set_buffer_nilfs_volatile(bh);
	*bhp = bh;
	return 0;
84
}
85

86
static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
87 88 89 90
{
	return node->bn_flags;
}

91
static void
92
nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
93 94 95 96
{
	node->bn_flags = flags;
}

97
static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
98
{
99
	return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
100 101
}

102
static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
103 104 105 106
{
	return node->bn_level;
}

107
static void
108
nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
109 110 111 112
{
	node->bn_level = level;
}

113
static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
114 115 116 117
{
	return le16_to_cpu(node->bn_nchildren);
}

118
static void
119
nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
120 121 122 123
{
	node->bn_nchildren = cpu_to_le16(nchildren);
}

124
static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
125
{
126
	return 1 << btree->b_inode->i_blkbits;
127 128
}

129
static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
130
{
131
	return btree->b_nchildren_per_block;
132 133
}

134
static __le64 *
135
nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
136 137
{
	return (__le64 *)((char *)(node + 1) +
138
			  (nilfs_btree_node_root(node) ?
139 140 141
			   0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
}

142
static __le64 *
143
nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
144
{
145
	return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
146 147
}

148
static __u64
149
nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
150
{
151
	return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
152 153
}

154
static void
155
nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
156
{
157
	*(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
158 159
}

160
static __u64
161 162
nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
			 int ncmax)
163
{
164
	return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
165 166
}

167
static void
168 169
nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
			 int ncmax)
170
{
171
	*(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
172 173
}

174 175
static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
				  int level, int nchildren, int ncmax,
176 177 178 179 180 181
				  const __u64 *keys, const __u64 *ptrs)
{
	__le64 *dkeys;
	__le64 *dptrs;
	int i;

182 183 184
	nilfs_btree_node_set_flags(node, flags);
	nilfs_btree_node_set_level(node, level);
	nilfs_btree_node_set_nchildren(node, nchildren);
185

186
	dkeys = nilfs_btree_node_dkeys(node);
187
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
188
	for (i = 0; i < nchildren; i++) {
189 190
		dkeys[i] = cpu_to_le64(keys[i]);
		dptrs[i] = cpu_to_le64(ptrs[i]);
191 192 193 194
	}
}

/* Assume the buffer heads corresponding to left and right are locked. */
195
static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
196
				       struct nilfs_btree_node *right,
197
				       int n, int lncmax, int rncmax)
198 199 200 201 202
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

203
	ldkeys = nilfs_btree_node_dkeys(left);
204
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
205
	lnchildren = nilfs_btree_node_get_nchildren(left);
206

207
	rdkeys = nilfs_btree_node_dkeys(right);
208
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
209
	rnchildren = nilfs_btree_node_get_nchildren(right);
210 211 212 213 214 215 216 217

	memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
	memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
	memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
	memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));

	lnchildren += n;
	rnchildren -= n;
218 219
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
220 221 222
}

/* Assume that the buffer heads corresponding to left and right are locked. */
223
static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
224
					struct nilfs_btree_node *right,
225
					int n, int lncmax, int rncmax)
226 227 228 229 230
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

231
	ldkeys = nilfs_btree_node_dkeys(left);
232
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
233
	lnchildren = nilfs_btree_node_get_nchildren(left);
234

235
	rdkeys = nilfs_btree_node_dkeys(right);
236
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
237
	rnchildren = nilfs_btree_node_get_nchildren(right);
238 239 240 241 242 243 244 245

	memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
	memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
	memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
	memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));

	lnchildren -= n;
	rnchildren += n;
246 247
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
248 249 250
}

/* Assume that the buffer head corresponding to node is locked. */
251 252
static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
				    __u64 key, __u64 ptr, int ncmax)
253 254 255 256 257
{
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

258
	dkeys = nilfs_btree_node_dkeys(node);
259
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
260
	nchildren = nilfs_btree_node_get_nchildren(node);
261 262 263 264 265 266
	if (index < nchildren) {
		memmove(dkeys + index + 1, dkeys + index,
			(nchildren - index) * sizeof(*dkeys));
		memmove(dptrs + index + 1, dptrs + index,
			(nchildren - index) * sizeof(*dptrs));
	}
267 268
	dkeys[index] = cpu_to_le64(key);
	dptrs[index] = cpu_to_le64(ptr);
269
	nchildren++;
270
	nilfs_btree_node_set_nchildren(node, nchildren);
271 272 273
}

/* Assume that the buffer head corresponding to node is locked. */
274 275
static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
				    __u64 *keyp, __u64 *ptrp, int ncmax)
276 277 278 279 280 281 282
{
	__u64 key;
	__u64 ptr;
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

283
	dkeys = nilfs_btree_node_dkeys(node);
284
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
285 286
	key = le64_to_cpu(dkeys[index]);
	ptr = le64_to_cpu(dptrs[index]);
287
	nchildren = nilfs_btree_node_get_nchildren(node);
288 289 290 291 292 293 294 295 296 297 298 299
	if (keyp != NULL)
		*keyp = key;
	if (ptrp != NULL)
		*ptrp = ptr;

	if (index < nchildren - 1) {
		memmove(dkeys + index, dkeys + index + 1,
			(nchildren - index - 1) * sizeof(*dkeys));
		memmove(dptrs + index, dptrs + index + 1,
			(nchildren - index - 1) * sizeof(*dptrs));
	}
	nchildren--;
300
	nilfs_btree_node_set_nchildren(node, nchildren);
301 302
}

303
static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
304 305 306 307 308 309 310
				   __u64 key, int *indexp)
{
	__u64 nkey;
	int index, low, high, s;

	/* binary search */
	low = 0;
311
	high = nilfs_btree_node_get_nchildren(node) - 1;
312 313 314 315
	index = 0;
	s = 0;
	while (low <= high) {
		index = (low + high) / 2;
316
		nkey = nilfs_btree_node_get_key(node, index);
317 318 319 320 321 322 323 324 325 326 327 328 329
		if (nkey == key) {
			s = 0;
			goto out;
		} else if (nkey < key) {
			low = index + 1;
			s = -1;
		} else {
			high = index - 1;
			s = 1;
		}
	}

	/* adjust index */
330 331
	if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
		if (s > 0 && index > 0)
332 333 334 335 336 337 338 339 340 341
			index--;
	} else if (s < 0)
		index++;

 out:
	*indexp = index;

	return s == 0;
}

342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
/**
 * nilfs_btree_node_broken - verify consistency of btree node
 * @node: btree node block to be examined
 * @size: node size (in bytes)
 * @blocknr: block number
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */
static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
				   size_t size, sector_t blocknr)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
		     level >= NILFS_BTREE_LEVEL_MAX ||
		     (flags & NILFS_BTREE_NODE_ROOT) ||
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
		printk(KERN_CRIT "NILFS: bad btree node (blocknr=%llu): "
		       "level = %d, flags = 0x%x, nchildren = %d\n",
		       (unsigned long long)blocknr, level, flags, nchildren);
		ret = 1;
	}
	return ret;
}

373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
/**
 * nilfs_btree_root_broken - verify consistency of btree root node
 * @node: btree root node to be examined
 * @ino: inode number
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */
static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
				   unsigned long ino)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
391
		     level >= NILFS_BTREE_LEVEL_MAX ||
392 393 394 395 396 397 398 399 400
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
		pr_crit("NILFS: bad btree root (inode number=%lu): level = %d, flags = 0x%x, nchildren = %d\n",
			ino, level, flags, nchildren);
		ret = 1;
	}
	return ret;
}

401 402
int nilfs_btree_broken_node_block(struct buffer_head *bh)
{
403 404 405 406 407 408
	int ret;

	if (buffer_nilfs_checked(bh))
		return 0;

	ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
409
				       bh->b_size, bh->b_blocknr);
410 411 412
	if (likely(!ret))
		set_buffer_nilfs_checked(bh);
	return ret;
413 414
}

415
static struct nilfs_btree_node *
416
nilfs_btree_get_root(const struct nilfs_bmap *btree)
417
{
418
	return (struct nilfs_btree_node *)btree->b_u.u_data;
419 420
}

421
static struct nilfs_btree_node *
422
nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
423 424 425 426
{
	return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
}

427
static struct nilfs_btree_node *
428
nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
429 430 431 432
{
	return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
}

433
static int nilfs_btree_height(const struct nilfs_bmap *btree)
434
{
435
	return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
436 437
}

438
static struct nilfs_btree_node *
439
nilfs_btree_get_node(const struct nilfs_bmap *btree,
440
		     const struct nilfs_btree_path *path,
441
		     int level, int *ncmaxp)
442
{
443 444 445 446 447 448 449 450 451 452
	struct nilfs_btree_node *node;

	if (level == nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_root(btree);
		*ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
	} else {
		node = nilfs_btree_get_nonroot_node(path, level);
		*ncmaxp = nilfs_btree_nchildren_per_block(btree);
	}
	return node;
453 454
}

455
static int
456 457 458 459 460 461 462 463 464 465 466
nilfs_btree_bad_node(struct nilfs_btree_node *node, int level)
{
	if (unlikely(nilfs_btree_node_get_level(node) != level)) {
		dump_stack();
		printk(KERN_CRIT "NILFS: btree level mismatch: %d != %d\n",
		       nilfs_btree_node_get_level(node), level);
		return 1;
	}
	return 0;
}

467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534
struct nilfs_btree_readahead_info {
	struct nilfs_btree_node *node;	/* parent node */
	int max_ra_blocks;		/* max nof blocks to read ahead */
	int index;			/* current index on the parent node */
	int ncmax;			/* nof children in the parent node */
};

static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp,
				   const struct nilfs_btree_readahead_info *ra)
{
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct buffer_head *bh, *ra_bh;
	sector_t submit_ptr = 0;
	int ret;

	ret = nilfs_btnode_submit_block(btnc, ptr, 0, READ, &bh, &submit_ptr);
	if (ret) {
		if (ret != -EEXIST)
			return ret;
		goto out_check;
	}

	if (ra) {
		int i, n;
		__u64 ptr2;

		/* read ahead sibling nodes */
		for (n = ra->max_ra_blocks, i = ra->index + 1;
		     n > 0 && i < ra->ncmax; n--, i++) {
			ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);

			ret = nilfs_btnode_submit_block(btnc, ptr2, 0, READA,
							&ra_bh, &submit_ptr);
			if (likely(!ret || ret == -EEXIST))
				brelse(ra_bh);
			else if (ret != -EBUSY)
				break;
			if (!buffer_locked(bh))
				goto out_no_wait;
		}
	}

	wait_on_buffer(bh);

 out_no_wait:
	if (!buffer_uptodate(bh)) {
		brelse(bh);
		return -EIO;
	}

 out_check:
	if (nilfs_btree_broken_node_block(bh)) {
		clear_buffer_uptodate(bh);
		brelse(bh);
		return -EINVAL;
	}

	*bhp = bh;
	return 0;
}

static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp)
{
	return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
}

535
static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
536
				 struct nilfs_btree_path *path,
537 538
				 __u64 key, __u64 *ptrp, int minlevel,
				 int readahead)
539 540
{
	struct nilfs_btree_node *node;
541
	struct nilfs_btree_readahead_info p, *ra;
542
	__u64 ptr;
543
	int level, index, found, ncmax, ret;
544 545

	node = nilfs_btree_get_root(btree);
546 547
	level = nilfs_btree_node_get_level(node);
	if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
548 549
		return -ENOENT;

550
	found = nilfs_btree_node_lookup(node, key, &index);
551 552
	ptr = nilfs_btree_node_get_ptr(node, index,
				       NILFS_BTREE_ROOT_NCHILDREN_MAX);
553 554 555
	path[level].bp_bh = NULL;
	path[level].bp_index = index;

556
	ncmax = nilfs_btree_nchildren_per_block(btree);
557

558 559 560 561 562 563 564 565 566 567 568
	while (--level >= minlevel) {
		ra = NULL;
		if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
			p.node = nilfs_btree_get_node(btree, path, level + 1,
						      &p.ncmax);
			p.index = index;
			p.max_ra_blocks = 7;
			ra = &p;
		}
		ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
					      ra);
569 570
		if (ret < 0)
			return ret;
571

572
		node = nilfs_btree_get_nonroot_node(path, level);
573 574
		if (nilfs_btree_bad_node(node, level))
			return -EINVAL;
575
		if (!found)
576
			found = nilfs_btree_node_lookup(node, key, &index);
577 578
		else
			index = 0;
579
		if (index < ncmax) {
580
			ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
581
		} else {
582
			WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
583 584 585 586 587 588 589 590 591 592 593 594 595 596
			/* insert */
			ptr = NILFS_BMAP_INVALID_PTR;
		}
		path[level].bp_index = index;
	}
	if (!found)
		return -ENOENT;

	if (ptrp != NULL)
		*ptrp = ptr;

	return 0;
}

597
static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
598 599 600 601 602
				      struct nilfs_btree_path *path,
				      __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
	__u64 ptr;
603
	int index, level, ncmax, ret;
604 605

	node = nilfs_btree_get_root(btree);
606
	index = nilfs_btree_node_get_nchildren(node) - 1;
607 608
	if (index < 0)
		return -ENOENT;
609
	level = nilfs_btree_node_get_level(node);
610 611
	ptr = nilfs_btree_node_get_ptr(node, index,
				       NILFS_BTREE_ROOT_NCHILDREN_MAX);
612 613
	path[level].bp_bh = NULL;
	path[level].bp_index = index;
614
	ncmax = nilfs_btree_nchildren_per_block(btree);
615 616

	for (level--; level > 0; level--) {
617
		ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
618 619
		if (ret < 0)
			return ret;
620
		node = nilfs_btree_get_nonroot_node(path, level);
621 622
		if (nilfs_btree_bad_node(node, level))
			return -EINVAL;
623
		index = nilfs_btree_node_get_nchildren(node) - 1;
624
		ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
625 626 627 628
		path[level].bp_index = index;
	}

	if (keyp != NULL)
629
		*keyp = nilfs_btree_node_get_key(node, index);
630 631 632 633 634 635
	if (ptrp != NULL)
		*ptrp = ptr;

	return 0;
}

636
static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
637 638 639 640 641
			      __u64 key, int level, __u64 *ptrp)
{
	struct nilfs_btree_path *path;
	int ret;

642
	path = nilfs_btree_alloc_path();
643 644 645
	if (path == NULL)
		return -ENOMEM;

646
	ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
647

648
	nilfs_btree_free_path(path);
649 650 651 652

	return ret;
}

653
static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
654 655 656 657 658 659 660 661
				     __u64 key, __u64 *ptrp, unsigned maxblocks)
{
	struct nilfs_btree_path *path;
	struct nilfs_btree_node *node;
	struct inode *dat = NULL;
	__u64 ptr, ptr2;
	sector_t blocknr;
	int level = NILFS_BTREE_LEVEL_NODE_MIN;
662
	int ret, cnt, index, maxlevel, ncmax;
663
	struct nilfs_btree_readahead_info p;
664

665
	path = nilfs_btree_alloc_path();
666 667
	if (path == NULL)
		return -ENOMEM;
668

669
	ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
670 671 672
	if (ret < 0)
		goto out;

673 674
	if (NILFS_BMAP_USE_VBN(btree)) {
		dat = nilfs_bmap_get_dat(btree);
675 676 677 678 679 680 681 682 683 684
		ret = nilfs_dat_translate(dat, ptr, &blocknr);
		if (ret < 0)
			goto out;
		ptr = blocknr;
	}
	cnt = 1;
	if (cnt == maxblocks)
		goto end;

	maxlevel = nilfs_btree_height(btree) - 1;
685
	node = nilfs_btree_get_node(btree, path, level, &ncmax);
686 687
	index = path[level].bp_index + 1;
	for (;;) {
688 689
		while (index < nilfs_btree_node_get_nchildren(node)) {
			if (nilfs_btree_node_get_key(node, index) !=
690 691
			    key + cnt)
				goto end;
692
			ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
693 694 695 696 697 698 699 700 701 702 703 704 705 706 707
			if (dat) {
				ret = nilfs_dat_translate(dat, ptr2, &blocknr);
				if (ret < 0)
					goto out;
				ptr2 = blocknr;
			}
			if (ptr2 != ptr + cnt || ++cnt == maxblocks)
				goto end;
			index++;
			continue;
		}
		if (level == maxlevel)
			break;

		/* look-up right sibling node */
708 709 710 711 712
		p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
		p.index = path[level + 1].bp_index + 1;
		p.max_ra_blocks = 7;
		if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
		    nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
713
			break;
714 715
		ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
		path[level + 1].bp_index = p.index;
716 717 718

		brelse(path[level].bp_bh);
		path[level].bp_bh = NULL;
719 720 721

		ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
					      &p);
722 723
		if (ret < 0)
			goto out;
724
		node = nilfs_btree_get_nonroot_node(path, level);
725
		ncmax = nilfs_btree_nchildren_per_block(btree);
726 727 728 729 730 731 732
		index = 0;
		path[level].bp_index = index;
	}
 end:
	*ptrp = ptr;
	ret = cnt;
 out:
733
	nilfs_btree_free_path(path);
734 735 736
	return ret;
}

737
static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
738 739 740 741 742 743
				    struct nilfs_btree_path *path,
				    int level, __u64 key)
{
	if (level < nilfs_btree_height(btree) - 1) {
		do {
			nilfs_btree_node_set_key(
744
				nilfs_btree_get_nonroot_node(path, level),
745 746
				path[level].bp_index, key);
			if (!buffer_dirty(path[level].bp_bh))
747
				mark_buffer_dirty(path[level].bp_bh);
748 749 750 751 752 753
		} while ((path[level].bp_index == 0) &&
			 (++level < nilfs_btree_height(btree) - 1));
	}

	/* root */
	if (level == nilfs_btree_height(btree) - 1) {
754
		nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
755 756 757 758
					 path[level].bp_index, key);
	}
}

759
static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
760 761 762 763
				  struct nilfs_btree_path *path,
				  int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
764
	int ncblk;
765 766

	if (level < nilfs_btree_height(btree) - 1) {
767
		node = nilfs_btree_get_nonroot_node(path, level);
768 769 770
		ncblk = nilfs_btree_nchildren_per_block(btree);
		nilfs_btree_node_insert(node, path[level].bp_index,
					*keyp, *ptrp, ncblk);
771
		if (!buffer_dirty(path[level].bp_bh))
772
			mark_buffer_dirty(path[level].bp_bh);
773 774 775

		if (path[level].bp_index == 0)
			nilfs_btree_promote_key(btree, path, level + 1,
776 777
						nilfs_btree_node_get_key(node,
									 0));
778 779
	} else {
		node = nilfs_btree_get_root(btree);
780 781 782
		nilfs_btree_node_insert(node, path[level].bp_index,
					*keyp, *ptrp,
					NILFS_BTREE_ROOT_NCHILDREN_MAX);
783 784 785
	}
}

786
static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
787 788 789 790
				   struct nilfs_btree_path *path,
				   int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *left;
791
	int nchildren, lnchildren, n, move, ncblk;
792

793 794 795 796
	node = nilfs_btree_get_nonroot_node(path, level);
	left = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	lnchildren = nilfs_btree_node_get_nchildren(left);
797
	ncblk = nilfs_btree_nchildren_per_block(btree);
798 799 800 801 802 803 804 805 806
	move = 0;

	n = (nchildren + lnchildren + 1) / 2 - lnchildren;
	if (n > path[level].bp_index) {
		/* move insert point */
		n--;
		move = 1;
	}

807
	nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
808 809

	if (!buffer_dirty(path[level].bp_bh))
810
		mark_buffer_dirty(path[level].bp_bh);
811
	if (!buffer_dirty(path[level].bp_sib_bh))
812
		mark_buffer_dirty(path[level].bp_sib_bh);
813 814

	nilfs_btree_promote_key(btree, path, level + 1,
815
				nilfs_btree_node_get_key(node, 0));
816 817

	if (move) {
818
		brelse(path[level].bp_bh);
819 820 821 822 823
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index += lnchildren;
		path[level + 1].bp_index--;
	} else {
824
		brelse(path[level].bp_sib_bh);
825 826 827 828 829 830 831
		path[level].bp_sib_bh = NULL;
		path[level].bp_index -= n;
	}

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
}

832
static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
833 834 835 836
				    struct nilfs_btree_path *path,
				    int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
837
	int nchildren, rnchildren, n, move, ncblk;
838

839 840 841 842
	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	rnchildren = nilfs_btree_node_get_nchildren(right);
843
	ncblk = nilfs_btree_nchildren_per_block(btree);
844 845 846 847 848 849 850 851 852
	move = 0;

	n = (nchildren + rnchildren + 1) / 2 - rnchildren;
	if (n > nchildren - path[level].bp_index) {
		/* move insert point */
		n--;
		move = 1;
	}

853
	nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
854 855

	if (!buffer_dirty(path[level].bp_bh))
856
		mark_buffer_dirty(path[level].bp_bh);
857
	if (!buffer_dirty(path[level].bp_sib_bh))
858
		mark_buffer_dirty(path[level].bp_sib_bh);
859 860 861

	path[level + 1].bp_index++;
	nilfs_btree_promote_key(btree, path, level + 1,
862
				nilfs_btree_node_get_key(right, 0));
863 864 865
	path[level + 1].bp_index--;

	if (move) {
866
		brelse(path[level].bp_bh);
867 868
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
869
		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
870 871
		path[level + 1].bp_index++;
	} else {
872
		brelse(path[level].bp_sib_bh);
873 874 875 876 877 878
		path[level].bp_sib_bh = NULL;
	}

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
}

879
static void nilfs_btree_split(struct nilfs_bmap *btree,
880 881 882 883 884 885
			      struct nilfs_btree_path *path,
			      int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *right;
	__u64 newkey;
	__u64 newptr;
886
	int nchildren, n, move, ncblk;
887

888 889 890
	node = nilfs_btree_get_nonroot_node(path, level);
	right = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
891
	ncblk = nilfs_btree_nchildren_per_block(btree);
892 893 894 895 896 897 898 899
	move = 0;

	n = (nchildren + 1) / 2;
	if (n > nchildren - path[level].bp_index) {
		n--;
		move = 1;
	}

900
	nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
901 902

	if (!buffer_dirty(path[level].bp_bh))
903
		mark_buffer_dirty(path[level].bp_bh);
904
	if (!buffer_dirty(path[level].bp_sib_bh))
905
		mark_buffer_dirty(path[level].bp_sib_bh);
906

907
	newkey = nilfs_btree_node_get_key(right, 0);
908 909 910
	newptr = path[level].bp_newreq.bpr_ptr;

	if (move) {
911
		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
912 913
		nilfs_btree_node_insert(right, path[level].bp_index,
					*keyp, *ptrp, ncblk);
914

915
		*keyp = nilfs_btree_node_get_key(right, 0);
916 917
		*ptrp = path[level].bp_newreq.bpr_ptr;

918
		brelse(path[level].bp_bh);
919 920 921 922 923
		path[level].bp_bh = path[level].bp_sib_bh;
		path[level].bp_sib_bh = NULL;
	} else {
		nilfs_btree_do_insert(btree, path, level, keyp, ptrp);

924
		*keyp = nilfs_btree_node_get_key(right, 0);
925 926
		*ptrp = path[level].bp_newreq.bpr_ptr;

927
		brelse(path[level].bp_sib_bh);
928 929 930 931 932 933
		path[level].bp_sib_bh = NULL;
	}

	path[level + 1].bp_index++;
}

934
static void nilfs_btree_grow(struct nilfs_bmap *btree,
935 936 937 938
			     struct nilfs_btree_path *path,
			     int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *root, *child;
939
	int n, ncblk;
940 941

	root = nilfs_btree_get_root(btree);
942
	child = nilfs_btree_get_sib_node(path, level);
943
	ncblk = nilfs_btree_nchildren_per_block(btree);
944

945
	n = nilfs_btree_node_get_nchildren(root);
946

947 948
	nilfs_btree_node_move_right(root, child, n,
				    NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
949
	nilfs_btree_node_set_level(root, level + 1);
950 951

	if (!buffer_dirty(path[level].bp_sib_bh))
952
		mark_buffer_dirty(path[level].bp_sib_bh);
953 954 955 956 957 958

	path[level].bp_bh = path[level].bp_sib_bh;
	path[level].bp_sib_bh = NULL;

	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);

959
	*keyp = nilfs_btree_node_get_key(child, 0);
960 961 962
	*ptrp = path[level].bp_newreq.bpr_ptr;
}

963
static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
964 965 966
				   const struct nilfs_btree_path *path)
{
	struct nilfs_btree_node *node;
967
	int level, ncmax;
968 969 970 971 972 973 974

	if (path == NULL)
		return NILFS_BMAP_INVALID_PTR;

	/* left sibling */
	level = NILFS_BTREE_LEVEL_NODE_MIN;
	if (path[level].bp_index > 0) {
975 976 977 978
		node = nilfs_btree_get_node(btree, path, level, &ncmax);
		return nilfs_btree_node_get_ptr(node,
						path[level].bp_index - 1,
						ncmax);
979 980 981 982 983
	}

	/* parent */
	level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
	if (level <= nilfs_btree_height(btree) - 1) {
984 985 986
		node = nilfs_btree_get_node(btree, path, level, &ncmax);
		return nilfs_btree_node_get_ptr(node, path[level].bp_index,
						ncmax);
987 988 989 990 991
	}

	return NILFS_BMAP_INVALID_PTR;
}

992
static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
993 994 995 996 997
				       const struct nilfs_btree_path *path,
				       __u64 key)
{
	__u64 ptr;

998
	ptr = nilfs_bmap_find_target_seq(btree, key);
999 1000 1001 1002 1003 1004 1005 1006 1007 1008
	if (ptr != NILFS_BMAP_INVALID_PTR)
		/* sequential access */
		return ptr;
	else {
		ptr = nilfs_btree_find_near(btree, path);
		if (ptr != NILFS_BMAP_INVALID_PTR)
			/* near */
			return ptr;
	}
	/* block group */
1009
	return nilfs_bmap_find_target_in_group(btree);
1010 1011
}

1012
static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1013 1014 1015 1016 1017 1018 1019
				      struct nilfs_btree_path *path,
				      int *levelp, __u64 key, __u64 ptr,
				      struct nilfs_bmap_stats *stats)
{
	struct buffer_head *bh;
	struct nilfs_btree_node *node, *parent, *sib;
	__u64 sibptr;
1020
	int pindex, level, ncmax, ncblk, ret;
1021
	struct inode *dat = NULL;
1022 1023 1024 1025 1026

	stats->bs_nblocks = 0;
	level = NILFS_BTREE_LEVEL_DATA;

	/* allocate a new ptr for data block */
1027
	if (NILFS_BMAP_USE_VBN(btree)) {
1028
		path[level].bp_newreq.bpr_ptr =
1029
			nilfs_btree_find_target_v(btree, path, key);
1030
		dat = nilfs_bmap_get_dat(btree);
1031
	}
1032

1033
	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1034 1035 1036
	if (ret < 0)
		goto err_out_data;

1037
	ncblk = nilfs_btree_nchildren_per_block(btree);
1038

1039 1040 1041
	for (level = NILFS_BTREE_LEVEL_NODE_MIN;
	     level < nilfs_btree_height(btree) - 1;
	     level++) {
1042
		node = nilfs_btree_get_nonroot_node(path, level);
1043
		if (nilfs_btree_node_get_nchildren(node) < ncblk) {
1044 1045 1046 1047 1048
			path[level].bp_op = nilfs_btree_do_insert;
			stats->bs_nblocks++;
			goto out;
		}

1049
		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
1050 1051 1052 1053
		pindex = path[level + 1].bp_index;

		/* left sibling */
		if (pindex > 0) {
1054 1055
			sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
							  ncmax);
1056
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
1057 1058 1059
			if (ret < 0)
				goto err_out_child_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
1060
			if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
1061 1062 1063 1064
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_carry_left;
				stats->bs_nblocks++;
				goto out;
1065
			} else {
1066
				brelse(bh);
1067
			}
1068 1069 1070
		}

		/* right sibling */
1071 1072 1073
		if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
			sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
							  ncmax);
1074
			ret = nilfs_btree_get_block(btree, sibptr, &bh);
1075 1076 1077
			if (ret < 0)
				goto err_out_child_node;
			sib = (struct nilfs_btree_node *)bh->b_data;
1078
			if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
1079 1080 1081 1082
				path[level].bp_sib_bh = bh;
				path[level].bp_op = nilfs_btree_carry_right;
				stats->bs_nblocks++;
				goto out;
1083
			} else {
1084
				brelse(bh);
1085
			}
1086 1087 1088 1089 1090
		}

		/* split */
		path[level].bp_newreq.bpr_ptr =
			path[level - 1].bp_newreq.bpr_ptr + 1;
1091
		ret = nilfs_bmap_prepare_alloc_ptr(btree,
1092
						   &path[level].bp_newreq, dat);
1093 1094
		if (ret < 0)
			goto err_out_child_node;
1095 1096 1097
		ret = nilfs_btree_get_new_block(btree,
						path[level].bp_newreq.bpr_ptr,
						&bh);
1098 1099 1100 1101 1102
		if (ret < 0)
			goto err_out_curr_node;

		stats->bs_nblocks++;

1103 1104
		sib = (struct nilfs_btree_node *)bh->b_data;
		nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
1105 1106 1107 1108 1109 1110
		path[level].bp_sib_bh = bh;
		path[level].bp_op = nilfs_btree_split;
	}

	/* root */
	node = nilfs_btree_get_root(btree);
1111
	if (nilfs_btree_node_get_nchildren(node) <
1112
	    NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1113 1114 1115 1116 1117 1118 1119
		path[level].bp_op = nilfs_btree_do_insert;
		stats->bs_nblocks++;
		goto out;
	}

	/* grow */
	path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
1120
	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
1121 1122
	if (ret < 0)
		goto err_out_child_node;
1123 1124
	ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
					&bh);
1125 1126 1127
	if (ret < 0)
		goto err_out_curr_node;

1128 1129
	nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
			      0, level, 0, ncblk, NULL, NULL);
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145
	path[level].bp_sib_bh = bh;
	path[level].bp_op = nilfs_btree_grow;

	level++;
	path[level].bp_op = nilfs_btree_do_insert;

	/* a newly-created node block and a data block are added */
	stats->bs_nblocks += 2;

	/* success */
 out:
	*levelp = level;
	return ret;

	/* error */
 err_out_curr_node:
1146
	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1147 1148
 err_out_child_node:
	for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
1149
		nilfs_btnode_delete(path[level].bp_sib_bh);
1150
		nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1151 1152 1153

	}

1154
	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
1155 1156 1157 1158 1159 1160
 err_out_data:
	*levelp = level;
	stats->bs_nblocks = 0;
	return ret;
}

1161
static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
1162 1163 1164
				      struct nilfs_btree_path *path,
				      int maxlevel, __u64 key, __u64 ptr)
{
1165
	struct inode *dat = NULL;
1166 1167 1168 1169
	int level;

	set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
	ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
1170
	if (NILFS_BMAP_USE_VBN(btree)) {
1171
		nilfs_bmap_set_target_v(btree, key, ptr);
1172
		dat = nilfs_bmap_get_dat(btree);
1173
	}
1174 1175

	for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
1176
		nilfs_bmap_commit_alloc_ptr(btree,
1177
					    &path[level - 1].bp_newreq, dat);
1178
		path[level].bp_op(btree, path, level, &key, &ptr);
1179 1180
	}

1181 1182
	if (!nilfs_bmap_dirty(btree))
		nilfs_bmap_set_dirty(btree);
1183 1184
}

1185
static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
1186 1187 1188 1189 1190
{
	struct nilfs_btree_path *path;
	struct nilfs_bmap_stats stats;
	int level, ret;

1191
	path = nilfs_btree_alloc_path();
1192 1193 1194 1195
	if (path == NULL)
		return -ENOMEM;

	ret = nilfs_btree_do_lookup(btree, path, key, NULL,
1196
				    NILFS_BTREE_LEVEL_NODE_MIN, 0);
1197 1198 1199 1200 1201 1202 1203 1204 1205 1206
	if (ret != -ENOENT) {
		if (ret == 0)
			ret = -EEXIST;
		goto out;
	}

	ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
	if (ret < 0)
		goto out;
	nilfs_btree_commit_insert(btree, path, level, key, ptr);
1207
	nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
1208 1209

 out:
1210
	nilfs_btree_free_path(path);
1211 1212 1213
	return ret;
}

1214
static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
1215 1216 1217 1218
				  struct nilfs_btree_path *path,
				  int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
1219
	int ncblk;
1220 1221

	if (level < nilfs_btree_height(btree) - 1) {
1222
		node = nilfs_btree_get_nonroot_node(path, level);
1223 1224 1225
		ncblk = nilfs_btree_nchildren_per_block(btree);
		nilfs_btree_node_delete(node, path[level].bp_index,
					keyp, ptrp, ncblk);
1226
		if (!buffer_dirty(path[level].bp_bh))
1227
			mark_buffer_dirty(path[level].bp_bh);
1228 1229
		if (path[level].bp_index == 0)
			nilfs_btree_promote_key(btree, path, level + 1,
1230
				nilfs_btree_node_get_key(node, 0));
1231 1232
	} else {
		node = nilfs_btree_get_root(btree);
1233 1234 1235
		nilfs_btree_node_delete(node, path[level].bp_index,
					keyp, ptrp,
					NILFS_BTREE_ROOT_NCHILDREN_MAX);
1236 1237 1238
	}
}

1239
static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
1240 1241 1242 1243
				    struct nilfs_btree_path *path,
				    int level, __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node, *left;
1244
	int nchildren, lnchildren, n, ncblk;
1245 1246 1247

	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);

1248 1249 1250 1251
	node = nilfs_btree_get_nonroot_node(path, level);
	left = nilfs_btree_get_sib_node(path, level);
	nchildren = nilfs_btree_node_get_nchildren(node);
	lnchildren = nilfs_btree_node_get_nchildren(left);
1252
	ncblk = nilfs_btree_nchildren_per_block(btree);
1253 1254 1255

	n = (nchildren + lnchildren) / 2 - nchildren;

1256
	nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
1257 1258

	if (!buffer_dirty(path[level].bp_bh))
1259
		mark_buffer_dirty(path[level].bp_bh);