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