1 // SPDX-License-Identifier: GPL-2.0 2 3 #include "messages.h" 4 #include "tree-mod-log.h" 5 #include "disk-io.h" 6 #include "fs.h" 7 #include "accessors.h" 8 9 struct tree_mod_root { 10 u64 logical; 11 u8 level; 12 }; 13 14 struct tree_mod_elem { 15 struct rb_node node; 16 u64 logical; 17 u64 seq; 18 enum btrfs_mod_log_op op; 19 20 /* 21 * This is used for BTRFS_MOD_LOG_KEY_* and BTRFS_MOD_LOG_MOVE_KEYS 22 * operations. 23 */ 24 int slot; 25 26 /* This is used for BTRFS_MOD_LOG_KEY* and BTRFS_MOD_LOG_ROOT_REPLACE. */ 27 u64 generation; 28 29 /* Those are used for op == BTRFS_MOD_LOG_KEY_{REPLACE,REMOVE}. */ 30 struct btrfs_disk_key key; 31 u64 blockptr; 32 33 /* This is used for op == BTRFS_MOD_LOG_MOVE_KEYS. */ 34 struct { 35 int dst_slot; 36 int nr_items; 37 } move; 38 39 /* This is used for op == BTRFS_MOD_LOG_ROOT_REPLACE. */ 40 struct tree_mod_root old_root; 41 }; 42 43 /* 44 * Pull a new tree mod seq number for our operation. 45 */ 46 static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info) 47 { 48 return atomic64_inc_return(&fs_info->tree_mod_seq); 49 } 50 51 /* 52 * This adds a new blocker to the tree mod log's blocker list if the @elem 53 * passed does not already have a sequence number set. So when a caller expects 54 * to record tree modifications, it should ensure to set elem->seq to zero 55 * before calling btrfs_get_tree_mod_seq. 56 * Returns a fresh, unused tree log modification sequence number, even if no new 57 * blocker was added. 58 */ 59 u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info, 60 struct btrfs_seq_list *elem) 61 { 62 write_lock(&fs_info->tree_mod_log_lock); 63 if (!elem->seq) { 64 elem->seq = btrfs_inc_tree_mod_seq(fs_info); 65 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list); 66 set_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags); 67 } 68 write_unlock(&fs_info->tree_mod_log_lock); 69 70 return elem->seq; 71 } 72 73 void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info, 74 struct btrfs_seq_list *elem) 75 { 76 struct rb_root *tm_root; 77 struct rb_node *node; 78 struct rb_node *next; 79 struct tree_mod_elem *tm; 80 u64 min_seq = BTRFS_SEQ_LAST; 81 u64 seq_putting = elem->seq; 82 83 if (!seq_putting) 84 return; 85 86 write_lock(&fs_info->tree_mod_log_lock); 87 list_del(&elem->list); 88 elem->seq = 0; 89 90 if (list_empty(&fs_info->tree_mod_seq_list)) { 91 clear_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags); 92 } else { 93 struct btrfs_seq_list *first; 94 95 first = list_first_entry(&fs_info->tree_mod_seq_list, 96 struct btrfs_seq_list, list); 97 if (seq_putting > first->seq) { 98 /* 99 * Blocker with lower sequence number exists, we cannot 100 * remove anything from the log. 101 */ 102 write_unlock(&fs_info->tree_mod_log_lock); 103 return; 104 } 105 min_seq = first->seq; 106 } 107 108 /* 109 * Anything that's lower than the lowest existing (read: blocked) 110 * sequence number can be removed from the tree. 111 */ 112 tm_root = &fs_info->tree_mod_log; 113 for (node = rb_first(tm_root); node; node = next) { 114 next = rb_next(node); 115 tm = rb_entry(node, struct tree_mod_elem, node); 116 if (tm->seq >= min_seq) 117 continue; 118 rb_erase(node, tm_root); 119 kfree(tm); 120 } 121 write_unlock(&fs_info->tree_mod_log_lock); 122 } 123 124 /* 125 * Key order of the log: 126 * node/leaf start address -> sequence 127 * 128 * The 'start address' is the logical address of the *new* root node for root 129 * replace operations, or the logical address of the affected block for all 130 * other operations. 131 */ 132 static noinline int tree_mod_log_insert(struct btrfs_fs_info *fs_info, 133 struct tree_mod_elem *tm) 134 { 135 struct rb_root *tm_root; 136 struct rb_node **new; 137 struct rb_node *parent = NULL; 138 struct tree_mod_elem *cur; 139 140 lockdep_assert_held_write(&fs_info->tree_mod_log_lock); 141 142 tm->seq = btrfs_inc_tree_mod_seq(fs_info); 143 144 tm_root = &fs_info->tree_mod_log; 145 new = &tm_root->rb_node; 146 while (*new) { 147 cur = rb_entry(*new, struct tree_mod_elem, node); 148 parent = *new; 149 if (cur->logical < tm->logical) 150 new = &((*new)->rb_left); 151 else if (cur->logical > tm->logical) 152 new = &((*new)->rb_right); 153 else if (cur->seq < tm->seq) 154 new = &((*new)->rb_left); 155 else if (cur->seq > tm->seq) 156 new = &((*new)->rb_right); 157 else 158 return -EEXIST; 159 } 160 161 rb_link_node(&tm->node, parent, new); 162 rb_insert_color(&tm->node, tm_root); 163 return 0; 164 } 165 166 /* 167 * Determines if logging can be omitted. Returns true if it can. Otherwise, it 168 * returns false with the tree_mod_log_lock acquired. The caller must hold 169 * this until all tree mod log insertions are recorded in the rb tree and then 170 * write unlock fs_info::tree_mod_log_lock. 171 */ 172 static inline bool tree_mod_dont_log(struct btrfs_fs_info *fs_info, 173 struct extent_buffer *eb) 174 { 175 if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags)) 176 return true; 177 if (eb && btrfs_header_level(eb) == 0) 178 return true; 179 180 write_lock(&fs_info->tree_mod_log_lock); 181 if (list_empty(&(fs_info)->tree_mod_seq_list)) { 182 write_unlock(&fs_info->tree_mod_log_lock); 183 return true; 184 } 185 186 return false; 187 } 188 189 /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */ 190 static inline bool tree_mod_need_log(const struct btrfs_fs_info *fs_info, 191 struct extent_buffer *eb) 192 { 193 if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags)) 194 return false; 195 if (eb && btrfs_header_level(eb) == 0) 196 return false; 197 198 return true; 199 } 200 201 static struct tree_mod_elem *alloc_tree_mod_elem(struct extent_buffer *eb, 202 int slot, 203 enum btrfs_mod_log_op op) 204 { 205 struct tree_mod_elem *tm; 206 207 tm = kzalloc(sizeof(*tm), GFP_NOFS); 208 if (!tm) 209 return NULL; 210 211 tm->logical = eb->start; 212 if (op != BTRFS_MOD_LOG_KEY_ADD) { 213 btrfs_node_key(eb, &tm->key, slot); 214 tm->blockptr = btrfs_node_blockptr(eb, slot); 215 } 216 tm->op = op; 217 tm->slot = slot; 218 tm->generation = btrfs_node_ptr_generation(eb, slot); 219 RB_CLEAR_NODE(&tm->node); 220 221 return tm; 222 } 223 224 int btrfs_tree_mod_log_insert_key(struct extent_buffer *eb, int slot, 225 enum btrfs_mod_log_op op) 226 { 227 struct tree_mod_elem *tm; 228 int ret; 229 230 if (!tree_mod_need_log(eb->fs_info, eb)) 231 return 0; 232 233 tm = alloc_tree_mod_elem(eb, slot, op); 234 if (!tm) 235 return -ENOMEM; 236 237 if (tree_mod_dont_log(eb->fs_info, eb)) { 238 kfree(tm); 239 return 0; 240 } 241 242 ret = tree_mod_log_insert(eb->fs_info, tm); 243 write_unlock(&eb->fs_info->tree_mod_log_lock); 244 if (ret) 245 kfree(tm); 246 247 return ret; 248 } 249 250 int btrfs_tree_mod_log_insert_move(struct extent_buffer *eb, 251 int dst_slot, int src_slot, 252 int nr_items) 253 { 254 struct tree_mod_elem *tm = NULL; 255 struct tree_mod_elem **tm_list = NULL; 256 int ret = 0; 257 int i; 258 bool locked = false; 259 260 if (!tree_mod_need_log(eb->fs_info, eb)) 261 return 0; 262 263 tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), GFP_NOFS); 264 if (!tm_list) 265 return -ENOMEM; 266 267 tm = kzalloc(sizeof(*tm), GFP_NOFS); 268 if (!tm) { 269 ret = -ENOMEM; 270 goto free_tms; 271 } 272 273 tm->logical = eb->start; 274 tm->slot = src_slot; 275 tm->move.dst_slot = dst_slot; 276 tm->move.nr_items = nr_items; 277 tm->op = BTRFS_MOD_LOG_MOVE_KEYS; 278 279 for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) { 280 tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot, 281 BTRFS_MOD_LOG_KEY_REMOVE_WHILE_MOVING); 282 if (!tm_list[i]) { 283 ret = -ENOMEM; 284 goto free_tms; 285 } 286 } 287 288 if (tree_mod_dont_log(eb->fs_info, eb)) 289 goto free_tms; 290 locked = true; 291 292 /* 293 * When we override something during the move, we log these removals. 294 * This can only happen when we move towards the beginning of the 295 * buffer, i.e. dst_slot < src_slot. 296 */ 297 for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) { 298 ret = tree_mod_log_insert(eb->fs_info, tm_list[i]); 299 if (ret) 300 goto free_tms; 301 } 302 303 ret = tree_mod_log_insert(eb->fs_info, tm); 304 if (ret) 305 goto free_tms; 306 write_unlock(&eb->fs_info->tree_mod_log_lock); 307 kfree(tm_list); 308 309 return 0; 310 311 free_tms: 312 for (i = 0; i < nr_items; i++) { 313 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node)) 314 rb_erase(&tm_list[i]->node, &eb->fs_info->tree_mod_log); 315 kfree(tm_list[i]); 316 } 317 if (locked) 318 write_unlock(&eb->fs_info->tree_mod_log_lock); 319 kfree(tm_list); 320 kfree(tm); 321 322 return ret; 323 } 324 325 static inline int tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, 326 struct tree_mod_elem **tm_list, 327 int nritems) 328 { 329 int i, j; 330 int ret; 331 332 for (i = nritems - 1; i >= 0; i--) { 333 ret = tree_mod_log_insert(fs_info, tm_list[i]); 334 if (ret) { 335 for (j = nritems - 1; j > i; j--) 336 rb_erase(&tm_list[j]->node, 337 &fs_info->tree_mod_log); 338 return ret; 339 } 340 } 341 342 return 0; 343 } 344 345 int btrfs_tree_mod_log_insert_root(struct extent_buffer *old_root, 346 struct extent_buffer *new_root, 347 bool log_removal) 348 { 349 struct btrfs_fs_info *fs_info = old_root->fs_info; 350 struct tree_mod_elem *tm = NULL; 351 struct tree_mod_elem **tm_list = NULL; 352 int nritems = 0; 353 int ret = 0; 354 int i; 355 356 if (!tree_mod_need_log(fs_info, NULL)) 357 return 0; 358 359 if (log_removal && btrfs_header_level(old_root) > 0) { 360 nritems = btrfs_header_nritems(old_root); 361 tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), 362 GFP_NOFS); 363 if (!tm_list) { 364 ret = -ENOMEM; 365 goto free_tms; 366 } 367 for (i = 0; i < nritems; i++) { 368 tm_list[i] = alloc_tree_mod_elem(old_root, i, 369 BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING); 370 if (!tm_list[i]) { 371 ret = -ENOMEM; 372 goto free_tms; 373 } 374 } 375 } 376 377 tm = kzalloc(sizeof(*tm), GFP_NOFS); 378 if (!tm) { 379 ret = -ENOMEM; 380 goto free_tms; 381 } 382 383 tm->logical = new_root->start; 384 tm->old_root.logical = old_root->start; 385 tm->old_root.level = btrfs_header_level(old_root); 386 tm->generation = btrfs_header_generation(old_root); 387 tm->op = BTRFS_MOD_LOG_ROOT_REPLACE; 388 389 if (tree_mod_dont_log(fs_info, NULL)) 390 goto free_tms; 391 392 if (tm_list) 393 ret = tree_mod_log_free_eb(fs_info, tm_list, nritems); 394 if (!ret) 395 ret = tree_mod_log_insert(fs_info, tm); 396 397 write_unlock(&fs_info->tree_mod_log_lock); 398 if (ret) 399 goto free_tms; 400 kfree(tm_list); 401 402 return ret; 403 404 free_tms: 405 if (tm_list) { 406 for (i = 0; i < nritems; i++) 407 kfree(tm_list[i]); 408 kfree(tm_list); 409 } 410 kfree(tm); 411 412 return ret; 413 } 414 415 static struct tree_mod_elem *__tree_mod_log_search(struct btrfs_fs_info *fs_info, 416 u64 start, u64 min_seq, 417 bool smallest) 418 { 419 struct rb_root *tm_root; 420 struct rb_node *node; 421 struct tree_mod_elem *cur = NULL; 422 struct tree_mod_elem *found = NULL; 423 424 read_lock(&fs_info->tree_mod_log_lock); 425 tm_root = &fs_info->tree_mod_log; 426 node = tm_root->rb_node; 427 while (node) { 428 cur = rb_entry(node, struct tree_mod_elem, node); 429 if (cur->logical < start) { 430 node = node->rb_left; 431 } else if (cur->logical > start) { 432 node = node->rb_right; 433 } else if (cur->seq < min_seq) { 434 node = node->rb_left; 435 } else if (!smallest) { 436 /* We want the node with the highest seq */ 437 if (found) 438 BUG_ON(found->seq > cur->seq); 439 found = cur; 440 node = node->rb_left; 441 } else if (cur->seq > min_seq) { 442 /* We want the node with the smallest seq */ 443 if (found) 444 BUG_ON(found->seq < cur->seq); 445 found = cur; 446 node = node->rb_right; 447 } else { 448 found = cur; 449 break; 450 } 451 } 452 read_unlock(&fs_info->tree_mod_log_lock); 453 454 return found; 455 } 456 457 /* 458 * This returns the element from the log with the smallest time sequence 459 * value that's in the log (the oldest log item). Any element with a time 460 * sequence lower than min_seq will be ignored. 461 */ 462 static struct tree_mod_elem *tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, 463 u64 start, u64 min_seq) 464 { 465 return __tree_mod_log_search(fs_info, start, min_seq, true); 466 } 467 468 /* 469 * This returns the element from the log with the largest time sequence 470 * value that's in the log (the most recent log item). Any element with 471 * a time sequence lower than min_seq will be ignored. 472 */ 473 static struct tree_mod_elem *tree_mod_log_search(struct btrfs_fs_info *fs_info, 474 u64 start, u64 min_seq) 475 { 476 return __tree_mod_log_search(fs_info, start, min_seq, false); 477 } 478 479 int btrfs_tree_mod_log_eb_copy(struct extent_buffer *dst, 480 struct extent_buffer *src, 481 unsigned long dst_offset, 482 unsigned long src_offset, 483 int nr_items) 484 { 485 struct btrfs_fs_info *fs_info = dst->fs_info; 486 int ret = 0; 487 struct tree_mod_elem **tm_list = NULL; 488 struct tree_mod_elem **tm_list_add, **tm_list_rem; 489 int i; 490 bool locked = false; 491 492 if (!tree_mod_need_log(fs_info, NULL)) 493 return 0; 494 495 if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0) 496 return 0; 497 498 tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *), 499 GFP_NOFS); 500 if (!tm_list) 501 return -ENOMEM; 502 503 tm_list_add = tm_list; 504 tm_list_rem = tm_list + nr_items; 505 for (i = 0; i < nr_items; i++) { 506 tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset, 507 BTRFS_MOD_LOG_KEY_REMOVE); 508 if (!tm_list_rem[i]) { 509 ret = -ENOMEM; 510 goto free_tms; 511 } 512 513 tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset, 514 BTRFS_MOD_LOG_KEY_ADD); 515 if (!tm_list_add[i]) { 516 ret = -ENOMEM; 517 goto free_tms; 518 } 519 } 520 521 if (tree_mod_dont_log(fs_info, NULL)) 522 goto free_tms; 523 locked = true; 524 525 for (i = 0; i < nr_items; i++) { 526 ret = tree_mod_log_insert(fs_info, tm_list_rem[i]); 527 if (ret) 528 goto free_tms; 529 ret = tree_mod_log_insert(fs_info, tm_list_add[i]); 530 if (ret) 531 goto free_tms; 532 } 533 534 write_unlock(&fs_info->tree_mod_log_lock); 535 kfree(tm_list); 536 537 return 0; 538 539 free_tms: 540 for (i = 0; i < nr_items * 2; i++) { 541 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node)) 542 rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log); 543 kfree(tm_list[i]); 544 } 545 if (locked) 546 write_unlock(&fs_info->tree_mod_log_lock); 547 kfree(tm_list); 548 549 return ret; 550 } 551 552 int btrfs_tree_mod_log_free_eb(struct extent_buffer *eb) 553 { 554 struct tree_mod_elem **tm_list = NULL; 555 int nritems = 0; 556 int i; 557 int ret = 0; 558 559 if (!tree_mod_need_log(eb->fs_info, eb)) 560 return 0; 561 562 nritems = btrfs_header_nritems(eb); 563 tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS); 564 if (!tm_list) 565 return -ENOMEM; 566 567 for (i = 0; i < nritems; i++) { 568 tm_list[i] = alloc_tree_mod_elem(eb, i, 569 BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING); 570 if (!tm_list[i]) { 571 ret = -ENOMEM; 572 goto free_tms; 573 } 574 } 575 576 if (tree_mod_dont_log(eb->fs_info, eb)) 577 goto free_tms; 578 579 ret = tree_mod_log_free_eb(eb->fs_info, tm_list, nritems); 580 write_unlock(&eb->fs_info->tree_mod_log_lock); 581 if (ret) 582 goto free_tms; 583 kfree(tm_list); 584 585 return 0; 586 587 free_tms: 588 for (i = 0; i < nritems; i++) 589 kfree(tm_list[i]); 590 kfree(tm_list); 591 592 return ret; 593 } 594 595 /* 596 * Returns the logical address of the oldest predecessor of the given root. 597 * Entries older than time_seq are ignored. 598 */ 599 static struct tree_mod_elem *tree_mod_log_oldest_root(struct extent_buffer *eb_root, 600 u64 time_seq) 601 { 602 struct tree_mod_elem *tm; 603 struct tree_mod_elem *found = NULL; 604 u64 root_logical = eb_root->start; 605 bool looped = false; 606 607 if (!time_seq) 608 return NULL; 609 610 /* 611 * The very last operation that's logged for a root is the replacement 612 * operation (if it is replaced at all). This has the logical address 613 * of the *new* root, making it the very first operation that's logged 614 * for this root. 615 */ 616 while (1) { 617 tm = tree_mod_log_search_oldest(eb_root->fs_info, root_logical, 618 time_seq); 619 if (!looped && !tm) 620 return NULL; 621 /* 622 * If there are no tree operation for the oldest root, we simply 623 * return it. This should only happen if that (old) root is at 624 * level 0. 625 */ 626 if (!tm) 627 break; 628 629 /* 630 * If there's an operation that's not a root replacement, we 631 * found the oldest version of our root. Normally, we'll find a 632 * BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here. 633 */ 634 if (tm->op != BTRFS_MOD_LOG_ROOT_REPLACE) 635 break; 636 637 found = tm; 638 root_logical = tm->old_root.logical; 639 looped = true; 640 } 641 642 /* If there's no old root to return, return what we found instead */ 643 if (!found) 644 found = tm; 645 646 return found; 647 } 648 649 650 /* 651 * tm is a pointer to the first operation to rewind within eb. Then, all 652 * previous operations will be rewound (until we reach something older than 653 * time_seq). 654 */ 655 static void tree_mod_log_rewind(struct btrfs_fs_info *fs_info, 656 struct extent_buffer *eb, 657 u64 time_seq, 658 struct tree_mod_elem *first_tm) 659 { 660 u32 n; 661 struct rb_node *next; 662 struct tree_mod_elem *tm = first_tm; 663 unsigned long o_dst; 664 unsigned long o_src; 665 unsigned long p_size = sizeof(struct btrfs_key_ptr); 666 667 n = btrfs_header_nritems(eb); 668 read_lock(&fs_info->tree_mod_log_lock); 669 while (tm && tm->seq >= time_seq) { 670 /* 671 * All the operations are recorded with the operator used for 672 * the modification. As we're going backwards, we do the 673 * opposite of each operation here. 674 */ 675 switch (tm->op) { 676 case BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING: 677 BUG_ON(tm->slot < n); 678 fallthrough; 679 case BTRFS_MOD_LOG_KEY_REMOVE_WHILE_MOVING: 680 case BTRFS_MOD_LOG_KEY_REMOVE: 681 btrfs_set_node_key(eb, &tm->key, tm->slot); 682 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr); 683 btrfs_set_node_ptr_generation(eb, tm->slot, 684 tm->generation); 685 n++; 686 break; 687 case BTRFS_MOD_LOG_KEY_REPLACE: 688 BUG_ON(tm->slot >= n); 689 btrfs_set_node_key(eb, &tm->key, tm->slot); 690 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr); 691 btrfs_set_node_ptr_generation(eb, tm->slot, 692 tm->generation); 693 break; 694 case BTRFS_MOD_LOG_KEY_ADD: 695 /* if a move operation is needed it's in the log */ 696 n--; 697 break; 698 case BTRFS_MOD_LOG_MOVE_KEYS: 699 o_dst = btrfs_node_key_ptr_offset(tm->slot); 700 o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot); 701 memmove_extent_buffer(eb, o_dst, o_src, 702 tm->move.nr_items * p_size); 703 break; 704 case BTRFS_MOD_LOG_ROOT_REPLACE: 705 /* 706 * This operation is special. For roots, this must be 707 * handled explicitly before rewinding. 708 * For non-roots, this operation may exist if the node 709 * was a root: root A -> child B; then A gets empty and 710 * B is promoted to the new root. In the mod log, we'll 711 * have a root-replace operation for B, a tree block 712 * that is no root. We simply ignore that operation. 713 */ 714 break; 715 } 716 next = rb_next(&tm->node); 717 if (!next) 718 break; 719 tm = rb_entry(next, struct tree_mod_elem, node); 720 if (tm->logical != first_tm->logical) 721 break; 722 } 723 read_unlock(&fs_info->tree_mod_log_lock); 724 btrfs_set_header_nritems(eb, n); 725 } 726 727 /* 728 * Called with eb read locked. If the buffer cannot be rewound, the same buffer 729 * is returned. If rewind operations happen, a fresh buffer is returned. The 730 * returned buffer is always read-locked. If the returned buffer is not the 731 * input buffer, the lock on the input buffer is released and the input buffer 732 * is freed (its refcount is decremented). 733 */ 734 struct extent_buffer *btrfs_tree_mod_log_rewind(struct btrfs_fs_info *fs_info, 735 struct btrfs_path *path, 736 struct extent_buffer *eb, 737 u64 time_seq) 738 { 739 struct extent_buffer *eb_rewin; 740 struct tree_mod_elem *tm; 741 742 if (!time_seq) 743 return eb; 744 745 if (btrfs_header_level(eb) == 0) 746 return eb; 747 748 tm = tree_mod_log_search(fs_info, eb->start, time_seq); 749 if (!tm) 750 return eb; 751 752 if (tm->op == BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) { 753 BUG_ON(tm->slot != 0); 754 eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start); 755 if (!eb_rewin) { 756 btrfs_tree_read_unlock(eb); 757 free_extent_buffer(eb); 758 return NULL; 759 } 760 btrfs_set_header_bytenr(eb_rewin, eb->start); 761 btrfs_set_header_backref_rev(eb_rewin, 762 btrfs_header_backref_rev(eb)); 763 btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb)); 764 btrfs_set_header_level(eb_rewin, btrfs_header_level(eb)); 765 } else { 766 eb_rewin = btrfs_clone_extent_buffer(eb); 767 if (!eb_rewin) { 768 btrfs_tree_read_unlock(eb); 769 free_extent_buffer(eb); 770 return NULL; 771 } 772 } 773 774 btrfs_tree_read_unlock(eb); 775 free_extent_buffer(eb); 776 777 btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb_rewin), 778 eb_rewin, btrfs_header_level(eb_rewin)); 779 btrfs_tree_read_lock(eb_rewin); 780 tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm); 781 WARN_ON(btrfs_header_nritems(eb_rewin) > 782 BTRFS_NODEPTRS_PER_BLOCK(fs_info)); 783 784 return eb_rewin; 785 } 786 787 /* 788 * Rewind the state of @root's root node to the given @time_seq value. 789 * If there are no changes, the current root->root_node is returned. If anything 790 * changed in between, there's a fresh buffer allocated on which the rewind 791 * operations are done. In any case, the returned buffer is read locked. 792 * Returns NULL on error (with no locks held). 793 */ 794 struct extent_buffer *btrfs_get_old_root(struct btrfs_root *root, u64 time_seq) 795 { 796 struct btrfs_fs_info *fs_info = root->fs_info; 797 struct tree_mod_elem *tm; 798 struct extent_buffer *eb = NULL; 799 struct extent_buffer *eb_root; 800 u64 eb_root_owner = 0; 801 struct extent_buffer *old; 802 struct tree_mod_root *old_root = NULL; 803 u64 old_generation = 0; 804 u64 logical; 805 int level; 806 807 eb_root = btrfs_read_lock_root_node(root); 808 tm = tree_mod_log_oldest_root(eb_root, time_seq); 809 if (!tm) 810 return eb_root; 811 812 if (tm->op == BTRFS_MOD_LOG_ROOT_REPLACE) { 813 old_root = &tm->old_root; 814 old_generation = tm->generation; 815 logical = old_root->logical; 816 level = old_root->level; 817 } else { 818 logical = eb_root->start; 819 level = btrfs_header_level(eb_root); 820 } 821 822 tm = tree_mod_log_search(fs_info, logical, time_seq); 823 if (old_root && tm && tm->op != BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) { 824 btrfs_tree_read_unlock(eb_root); 825 free_extent_buffer(eb_root); 826 old = read_tree_block(fs_info, logical, root->root_key.objectid, 827 0, level, NULL); 828 if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) { 829 if (!IS_ERR(old)) 830 free_extent_buffer(old); 831 btrfs_warn(fs_info, 832 "failed to read tree block %llu from get_old_root", 833 logical); 834 } else { 835 struct tree_mod_elem *tm2; 836 837 btrfs_tree_read_lock(old); 838 eb = btrfs_clone_extent_buffer(old); 839 /* 840 * After the lookup for the most recent tree mod operation 841 * above and before we locked and cloned the extent buffer 842 * 'old', a new tree mod log operation may have been added. 843 * So lookup for a more recent one to make sure the number 844 * of mod log operations we replay is consistent with the 845 * number of items we have in the cloned extent buffer, 846 * otherwise we can hit a BUG_ON when rewinding the extent 847 * buffer. 848 */ 849 tm2 = tree_mod_log_search(fs_info, logical, time_seq); 850 btrfs_tree_read_unlock(old); 851 free_extent_buffer(old); 852 ASSERT(tm2); 853 ASSERT(tm2 == tm || tm2->seq > tm->seq); 854 if (!tm2 || tm2->seq < tm->seq) { 855 free_extent_buffer(eb); 856 return NULL; 857 } 858 tm = tm2; 859 } 860 } else if (old_root) { 861 eb_root_owner = btrfs_header_owner(eb_root); 862 btrfs_tree_read_unlock(eb_root); 863 free_extent_buffer(eb_root); 864 eb = alloc_dummy_extent_buffer(fs_info, logical); 865 } else { 866 eb = btrfs_clone_extent_buffer(eb_root); 867 btrfs_tree_read_unlock(eb_root); 868 free_extent_buffer(eb_root); 869 } 870 871 if (!eb) 872 return NULL; 873 if (old_root) { 874 btrfs_set_header_bytenr(eb, eb->start); 875 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV); 876 btrfs_set_header_owner(eb, eb_root_owner); 877 btrfs_set_header_level(eb, old_root->level); 878 btrfs_set_header_generation(eb, old_generation); 879 } 880 btrfs_set_buffer_lockdep_class(btrfs_header_owner(eb), eb, 881 btrfs_header_level(eb)); 882 btrfs_tree_read_lock(eb); 883 if (tm) 884 tree_mod_log_rewind(fs_info, eb, time_seq, tm); 885 else 886 WARN_ON(btrfs_header_level(eb) != 0); 887 WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(fs_info)); 888 889 return eb; 890 } 891 892 int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq) 893 { 894 struct tree_mod_elem *tm; 895 int level; 896 struct extent_buffer *eb_root = btrfs_root_node(root); 897 898 tm = tree_mod_log_oldest_root(eb_root, time_seq); 899 if (tm && tm->op == BTRFS_MOD_LOG_ROOT_REPLACE) 900 level = tm->old_root.level; 901 else 902 level = btrfs_header_level(eb_root); 903 904 free_extent_buffer(eb_root); 905 906 return level; 907 } 908 909 /* 910 * Return the lowest sequence number in the tree modification log. 911 * 912 * Return the sequence number of the oldest tree modification log user, which 913 * corresponds to the lowest sequence number of all existing users. If there are 914 * no users it returns 0. 915 */ 916 u64 btrfs_tree_mod_log_lowest_seq(struct btrfs_fs_info *fs_info) 917 { 918 u64 ret = 0; 919 920 read_lock(&fs_info->tree_mod_log_lock); 921 if (!list_empty(&fs_info->tree_mod_seq_list)) { 922 struct btrfs_seq_list *elem; 923 924 elem = list_first_entry(&fs_info->tree_mod_seq_list, 925 struct btrfs_seq_list, list); 926 ret = elem->seq; 927 } 928 read_unlock(&fs_info->tree_mod_log_lock); 929 930 return ret; 931 } 932