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