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