1// SPDX-License-Identifier: GPL-2.0 2/* 3 * Copyright (C) 2015 Facebook. All rights reserved. 4 */ 5 6#include <linux/kernel.h> 7#include <linux/sched/mm.h> 8#include "ctree.h" 9#include "disk-io.h" 10#include "locking.h" 11#include "free-space-tree.h" 12#include "transaction.h" 13#include "block-group.h" 14 15static int __add_block_group_free_space(struct btrfs_trans_handle *trans, 16 struct btrfs_block_group *block_group, 17 struct btrfs_path *path); 18 19void set_free_space_tree_thresholds(struct btrfs_block_group *cache) 20{ 21 u32 bitmap_range; 22 size_t bitmap_size; 23 u64 num_bitmaps, total_bitmap_size; 24 25 if (WARN_ON(cache->length == 0)) 26 btrfs_warn(cache->fs_info, "block group %llu length is zero", 27 cache->start); 28 29 /* 30 * We convert to bitmaps when the disk space required for using extents 31 * exceeds that required for using bitmaps. 32 */ 33 bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; 34 num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range); 35 bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE; 36 total_bitmap_size = num_bitmaps * bitmap_size; 37 cache->bitmap_high_thresh = div_u64(total_bitmap_size, 38 sizeof(struct btrfs_item)); 39 40 /* 41 * We allow for a small buffer between the high threshold and low 42 * threshold to avoid thrashing back and forth between the two formats. 43 */ 44 if (cache->bitmap_high_thresh > 100) 45 cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100; 46 else 47 cache->bitmap_low_thresh = 0; 48} 49 50static int add_new_free_space_info(struct btrfs_trans_handle *trans, 51 struct btrfs_block_group *block_group, 52 struct btrfs_path *path) 53{ 54 struct btrfs_root *root = trans->fs_info->free_space_root; 55 struct btrfs_free_space_info *info; 56 struct btrfs_key key; 57 struct extent_buffer *leaf; 58 int ret; 59 60 key.objectid = block_group->start; 61 key.type = BTRFS_FREE_SPACE_INFO_KEY; 62 key.offset = block_group->length; 63 64 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info)); 65 if (ret) 66 goto out; 67 68 leaf = path->nodes[0]; 69 info = btrfs_item_ptr(leaf, path->slots[0], 70 struct btrfs_free_space_info); 71 btrfs_set_free_space_extent_count(leaf, info, 0); 72 btrfs_set_free_space_flags(leaf, info, 0); 73 btrfs_mark_buffer_dirty(leaf); 74 75 ret = 0; 76out: 77 btrfs_release_path(path); 78 return ret; 79} 80 81EXPORT_FOR_TESTS 82struct btrfs_free_space_info *search_free_space_info( 83 struct btrfs_trans_handle *trans, 84 struct btrfs_block_group *block_group, 85 struct btrfs_path *path, int cow) 86{ 87 struct btrfs_fs_info *fs_info = block_group->fs_info; 88 struct btrfs_root *root = fs_info->free_space_root; 89 struct btrfs_key key; 90 int ret; 91 92 key.objectid = block_group->start; 93 key.type = BTRFS_FREE_SPACE_INFO_KEY; 94 key.offset = block_group->length; 95 96 ret = btrfs_search_slot(trans, root, &key, path, 0, cow); 97 if (ret < 0) 98 return ERR_PTR(ret); 99 if (ret != 0) { 100 btrfs_warn(fs_info, "missing free space info for %llu", 101 block_group->start); 102 ASSERT(0); 103 return ERR_PTR(-ENOENT); 104 } 105 106 return btrfs_item_ptr(path->nodes[0], path->slots[0], 107 struct btrfs_free_space_info); 108} 109 110/* 111 * btrfs_search_slot() but we're looking for the greatest key less than the 112 * passed key. 113 */ 114static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans, 115 struct btrfs_root *root, 116 struct btrfs_key *key, struct btrfs_path *p, 117 int ins_len, int cow) 118{ 119 int ret; 120 121 ret = btrfs_search_slot(trans, root, key, p, ins_len, cow); 122 if (ret < 0) 123 return ret; 124 125 if (ret == 0) { 126 ASSERT(0); 127 return -EIO; 128 } 129 130 if (p->slots[0] == 0) { 131 ASSERT(0); 132 return -EIO; 133 } 134 p->slots[0]--; 135 136 return 0; 137} 138 139static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize) 140{ 141 return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE); 142} 143 144static unsigned long *alloc_bitmap(u32 bitmap_size) 145{ 146 unsigned long *ret; 147 unsigned int nofs_flag; 148 u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long)); 149 150 /* 151 * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse 152 * into the filesystem as the free space bitmap can be modified in the 153 * critical section of a transaction commit. 154 * 155 * TODO: push the memalloc_nofs_{save,restore}() to the caller where we 156 * know that recursion is unsafe. 157 */ 158 nofs_flag = memalloc_nofs_save(); 159 ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL); 160 memalloc_nofs_restore(nofs_flag); 161 return ret; 162} 163 164static void le_bitmap_set(unsigned long *map, unsigned int start, int len) 165{ 166 u8 *p = ((u8 *)map) + BIT_BYTE(start); 167 const unsigned int size = start + len; 168 int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE); 169 u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start); 170 171 while (len - bits_to_set >= 0) { 172 *p |= mask_to_set; 173 len -= bits_to_set; 174 bits_to_set = BITS_PER_BYTE; 175 mask_to_set = ~0; 176 p++; 177 } 178 if (len) { 179 mask_to_set &= BITMAP_LAST_BYTE_MASK(size); 180 *p |= mask_to_set; 181 } 182} 183 184EXPORT_FOR_TESTS 185int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans, 186 struct btrfs_block_group *block_group, 187 struct btrfs_path *path) 188{ 189 struct btrfs_fs_info *fs_info = trans->fs_info; 190 struct btrfs_root *root = fs_info->free_space_root; 191 struct btrfs_free_space_info *info; 192 struct btrfs_key key, found_key; 193 struct extent_buffer *leaf; 194 unsigned long *bitmap; 195 char *bitmap_cursor; 196 u64 start, end; 197 u64 bitmap_range, i; 198 u32 bitmap_size, flags, expected_extent_count; 199 u32 extent_count = 0; 200 int done = 0, nr; 201 int ret; 202 203 bitmap_size = free_space_bitmap_size(block_group->length, 204 fs_info->sectorsize); 205 bitmap = alloc_bitmap(bitmap_size); 206 if (!bitmap) { 207 ret = -ENOMEM; 208 goto out; 209 } 210 211 start = block_group->start; 212 end = block_group->start + block_group->length; 213 214 key.objectid = end - 1; 215 key.type = (u8)-1; 216 key.offset = (u64)-1; 217 218 while (!done) { 219 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 220 if (ret) 221 goto out; 222 223 leaf = path->nodes[0]; 224 nr = 0; 225 path->slots[0]++; 226 while (path->slots[0] > 0) { 227 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 228 229 if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 230 ASSERT(found_key.objectid == block_group->start); 231 ASSERT(found_key.offset == block_group->length); 232 done = 1; 233 break; 234 } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) { 235 u64 first, last; 236 237 ASSERT(found_key.objectid >= start); 238 ASSERT(found_key.objectid < end); 239 ASSERT(found_key.objectid + found_key.offset <= end); 240 241 first = div_u64(found_key.objectid - start, 242 fs_info->sectorsize); 243 last = div_u64(found_key.objectid + found_key.offset - start, 244 fs_info->sectorsize); 245 le_bitmap_set(bitmap, first, last - first); 246 247 extent_count++; 248 nr++; 249 path->slots[0]--; 250 } else { 251 ASSERT(0); 252 } 253 } 254 255 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 256 if (ret) 257 goto out; 258 btrfs_release_path(path); 259 } 260 261 info = search_free_space_info(trans, block_group, path, 1); 262 if (IS_ERR(info)) { 263 ret = PTR_ERR(info); 264 goto out; 265 } 266 leaf = path->nodes[0]; 267 flags = btrfs_free_space_flags(leaf, info); 268 flags |= BTRFS_FREE_SPACE_USING_BITMAPS; 269 btrfs_set_free_space_flags(leaf, info, flags); 270 expected_extent_count = btrfs_free_space_extent_count(leaf, info); 271 btrfs_mark_buffer_dirty(leaf); 272 btrfs_release_path(path); 273 274 if (extent_count != expected_extent_count) { 275 btrfs_err(fs_info, 276 "incorrect extent count for %llu; counted %u, expected %u", 277 block_group->start, extent_count, 278 expected_extent_count); 279 ASSERT(0); 280 ret = -EIO; 281 goto out; 282 } 283 284 bitmap_cursor = (char *)bitmap; 285 bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; 286 i = start; 287 while (i < end) { 288 unsigned long ptr; 289 u64 extent_size; 290 u32 data_size; 291 292 extent_size = min(end - i, bitmap_range); 293 data_size = free_space_bitmap_size(extent_size, 294 fs_info->sectorsize); 295 296 key.objectid = i; 297 key.type = BTRFS_FREE_SPACE_BITMAP_KEY; 298 key.offset = extent_size; 299 300 ret = btrfs_insert_empty_item(trans, root, path, &key, 301 data_size); 302 if (ret) 303 goto out; 304 305 leaf = path->nodes[0]; 306 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 307 write_extent_buffer(leaf, bitmap_cursor, ptr, 308 data_size); 309 btrfs_mark_buffer_dirty(leaf); 310 btrfs_release_path(path); 311 312 i += extent_size; 313 bitmap_cursor += data_size; 314 } 315 316 ret = 0; 317out: 318 kvfree(bitmap); 319 if (ret) 320 btrfs_abort_transaction(trans, ret); 321 return ret; 322} 323 324EXPORT_FOR_TESTS 325int convert_free_space_to_extents(struct btrfs_trans_handle *trans, 326 struct btrfs_block_group *block_group, 327 struct btrfs_path *path) 328{ 329 struct btrfs_fs_info *fs_info = trans->fs_info; 330 struct btrfs_root *root = fs_info->free_space_root; 331 struct btrfs_free_space_info *info; 332 struct btrfs_key key, found_key; 333 struct extent_buffer *leaf; 334 unsigned long *bitmap; 335 u64 start, end; 336 u32 bitmap_size, flags, expected_extent_count; 337 unsigned long nrbits, start_bit, end_bit; 338 u32 extent_count = 0; 339 int done = 0, nr; 340 int ret; 341 342 bitmap_size = free_space_bitmap_size(block_group->length, 343 fs_info->sectorsize); 344 bitmap = alloc_bitmap(bitmap_size); 345 if (!bitmap) { 346 ret = -ENOMEM; 347 goto out; 348 } 349 350 start = block_group->start; 351 end = block_group->start + block_group->length; 352 353 key.objectid = end - 1; 354 key.type = (u8)-1; 355 key.offset = (u64)-1; 356 357 while (!done) { 358 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 359 if (ret) 360 goto out; 361 362 leaf = path->nodes[0]; 363 nr = 0; 364 path->slots[0]++; 365 while (path->slots[0] > 0) { 366 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 367 368 if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 369 ASSERT(found_key.objectid == block_group->start); 370 ASSERT(found_key.offset == block_group->length); 371 done = 1; 372 break; 373 } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) { 374 unsigned long ptr; 375 char *bitmap_cursor; 376 u32 bitmap_pos, data_size; 377 378 ASSERT(found_key.objectid >= start); 379 ASSERT(found_key.objectid < end); 380 ASSERT(found_key.objectid + found_key.offset <= end); 381 382 bitmap_pos = div_u64(found_key.objectid - start, 383 fs_info->sectorsize * 384 BITS_PER_BYTE); 385 bitmap_cursor = ((char *)bitmap) + bitmap_pos; 386 data_size = free_space_bitmap_size(found_key.offset, 387 fs_info->sectorsize); 388 389 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1); 390 read_extent_buffer(leaf, bitmap_cursor, ptr, 391 data_size); 392 393 nr++; 394 path->slots[0]--; 395 } else { 396 ASSERT(0); 397 } 398 } 399 400 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 401 if (ret) 402 goto out; 403 btrfs_release_path(path); 404 } 405 406 info = search_free_space_info(trans, block_group, path, 1); 407 if (IS_ERR(info)) { 408 ret = PTR_ERR(info); 409 goto out; 410 } 411 leaf = path->nodes[0]; 412 flags = btrfs_free_space_flags(leaf, info); 413 flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS; 414 btrfs_set_free_space_flags(leaf, info, flags); 415 expected_extent_count = btrfs_free_space_extent_count(leaf, info); 416 btrfs_mark_buffer_dirty(leaf); 417 btrfs_release_path(path); 418 419 nrbits = div_u64(block_group->length, block_group->fs_info->sectorsize); 420 start_bit = find_next_bit_le(bitmap, nrbits, 0); 421 422 while (start_bit < nrbits) { 423 end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit); 424 ASSERT(start_bit < end_bit); 425 426 key.objectid = start + start_bit * block_group->fs_info->sectorsize; 427 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 428 key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize; 429 430 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 431 if (ret) 432 goto out; 433 btrfs_release_path(path); 434 435 extent_count++; 436 437 start_bit = find_next_bit_le(bitmap, nrbits, end_bit); 438 } 439 440 if (extent_count != expected_extent_count) { 441 btrfs_err(fs_info, 442 "incorrect extent count for %llu; counted %u, expected %u", 443 block_group->start, extent_count, 444 expected_extent_count); 445 ASSERT(0); 446 ret = -EIO; 447 goto out; 448 } 449 450 ret = 0; 451out: 452 kvfree(bitmap); 453 if (ret) 454 btrfs_abort_transaction(trans, ret); 455 return ret; 456} 457 458static int update_free_space_extent_count(struct btrfs_trans_handle *trans, 459 struct btrfs_block_group *block_group, 460 struct btrfs_path *path, 461 int new_extents) 462{ 463 struct btrfs_free_space_info *info; 464 u32 flags; 465 u32 extent_count; 466 int ret = 0; 467 468 if (new_extents == 0) 469 return 0; 470 471 info = search_free_space_info(trans, block_group, path, 1); 472 if (IS_ERR(info)) { 473 ret = PTR_ERR(info); 474 goto out; 475 } 476 flags = btrfs_free_space_flags(path->nodes[0], info); 477 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); 478 479 extent_count += new_extents; 480 btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count); 481 btrfs_mark_buffer_dirty(path->nodes[0]); 482 btrfs_release_path(path); 483 484 if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) && 485 extent_count > block_group->bitmap_high_thresh) { 486 ret = convert_free_space_to_bitmaps(trans, block_group, path); 487 } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) && 488 extent_count < block_group->bitmap_low_thresh) { 489 ret = convert_free_space_to_extents(trans, block_group, path); 490 } 491 492out: 493 return ret; 494} 495 496EXPORT_FOR_TESTS 497int free_space_test_bit(struct btrfs_block_group *block_group, 498 struct btrfs_path *path, u64 offset) 499{ 500 struct extent_buffer *leaf; 501 struct btrfs_key key; 502 u64 found_start, found_end; 503 unsigned long ptr, i; 504 505 leaf = path->nodes[0]; 506 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 507 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 508 509 found_start = key.objectid; 510 found_end = key.objectid + key.offset; 511 ASSERT(offset >= found_start && offset < found_end); 512 513 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 514 i = div_u64(offset - found_start, 515 block_group->fs_info->sectorsize); 516 return !!extent_buffer_test_bit(leaf, ptr, i); 517} 518 519static void free_space_set_bits(struct btrfs_block_group *block_group, 520 struct btrfs_path *path, u64 *start, u64 *size, 521 int bit) 522{ 523 struct btrfs_fs_info *fs_info = block_group->fs_info; 524 struct extent_buffer *leaf; 525 struct btrfs_key key; 526 u64 end = *start + *size; 527 u64 found_start, found_end; 528 unsigned long ptr, first, last; 529 530 leaf = path->nodes[0]; 531 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 532 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 533 534 found_start = key.objectid; 535 found_end = key.objectid + key.offset; 536 ASSERT(*start >= found_start && *start < found_end); 537 ASSERT(end > found_start); 538 539 if (end > found_end) 540 end = found_end; 541 542 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 543 first = div_u64(*start - found_start, fs_info->sectorsize); 544 last = div_u64(end - found_start, fs_info->sectorsize); 545 if (bit) 546 extent_buffer_bitmap_set(leaf, ptr, first, last - first); 547 else 548 extent_buffer_bitmap_clear(leaf, ptr, first, last - first); 549 btrfs_mark_buffer_dirty(leaf); 550 551 *size -= end - *start; 552 *start = end; 553} 554 555/* 556 * We can't use btrfs_next_item() in modify_free_space_bitmap() because 557 * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy 558 * tree walking in btrfs_next_leaf() anyways because we know exactly what we're 559 * looking for. 560 */ 561static int free_space_next_bitmap(struct btrfs_trans_handle *trans, 562 struct btrfs_root *root, struct btrfs_path *p) 563{ 564 struct btrfs_key key; 565 566 if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) { 567 p->slots[0]++; 568 return 0; 569 } 570 571 btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]); 572 btrfs_release_path(p); 573 574 key.objectid += key.offset; 575 key.type = (u8)-1; 576 key.offset = (u64)-1; 577 578 return btrfs_search_prev_slot(trans, root, &key, p, 0, 1); 579} 580 581/* 582 * If remove is 1, then we are removing free space, thus clearing bits in the 583 * bitmap. If remove is 0, then we are adding free space, thus setting bits in 584 * the bitmap. 585 */ 586static int modify_free_space_bitmap(struct btrfs_trans_handle *trans, 587 struct btrfs_block_group *block_group, 588 struct btrfs_path *path, 589 u64 start, u64 size, int remove) 590{ 591 struct btrfs_root *root = block_group->fs_info->free_space_root; 592 struct btrfs_key key; 593 u64 end = start + size; 594 u64 cur_start, cur_size; 595 int prev_bit, next_bit; 596 int new_extents; 597 int ret; 598 599 /* 600 * Read the bit for the block immediately before the extent of space if 601 * that block is within the block group. 602 */ 603 if (start > block_group->start) { 604 u64 prev_block = start - block_group->fs_info->sectorsize; 605 606 key.objectid = prev_block; 607 key.type = (u8)-1; 608 key.offset = (u64)-1; 609 610 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); 611 if (ret) 612 goto out; 613 614 prev_bit = free_space_test_bit(block_group, path, prev_block); 615 616 /* The previous block may have been in the previous bitmap. */ 617 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 618 if (start >= key.objectid + key.offset) { 619 ret = free_space_next_bitmap(trans, root, path); 620 if (ret) 621 goto out; 622 } 623 } else { 624 key.objectid = start; 625 key.type = (u8)-1; 626 key.offset = (u64)-1; 627 628 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); 629 if (ret) 630 goto out; 631 632 prev_bit = -1; 633 } 634 635 /* 636 * Iterate over all of the bitmaps overlapped by the extent of space, 637 * clearing/setting bits as required. 638 */ 639 cur_start = start; 640 cur_size = size; 641 while (1) { 642 free_space_set_bits(block_group, path, &cur_start, &cur_size, 643 !remove); 644 if (cur_size == 0) 645 break; 646 ret = free_space_next_bitmap(trans, root, path); 647 if (ret) 648 goto out; 649 } 650 651 /* 652 * Read the bit for the block immediately after the extent of space if 653 * that block is within the block group. 654 */ 655 if (end < block_group->start + block_group->length) { 656 /* The next block may be in the next bitmap. */ 657 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 658 if (end >= key.objectid + key.offset) { 659 ret = free_space_next_bitmap(trans, root, path); 660 if (ret) 661 goto out; 662 } 663 664 next_bit = free_space_test_bit(block_group, path, end); 665 } else { 666 next_bit = -1; 667 } 668 669 if (remove) { 670 new_extents = -1; 671 if (prev_bit == 1) { 672 /* Leftover on the left. */ 673 new_extents++; 674 } 675 if (next_bit == 1) { 676 /* Leftover on the right. */ 677 new_extents++; 678 } 679 } else { 680 new_extents = 1; 681 if (prev_bit == 1) { 682 /* Merging with neighbor on the left. */ 683 new_extents--; 684 } 685 if (next_bit == 1) { 686 /* Merging with neighbor on the right. */ 687 new_extents--; 688 } 689 } 690 691 btrfs_release_path(path); 692 ret = update_free_space_extent_count(trans, block_group, path, 693 new_extents); 694 695out: 696 return ret; 697} 698 699static int remove_free_space_extent(struct btrfs_trans_handle *trans, 700 struct btrfs_block_group *block_group, 701 struct btrfs_path *path, 702 u64 start, u64 size) 703{ 704 struct btrfs_root *root = trans->fs_info->free_space_root; 705 struct btrfs_key key; 706 u64 found_start, found_end; 707 u64 end = start + size; 708 int new_extents = -1; 709 int ret; 710 711 key.objectid = start; 712 key.type = (u8)-1; 713 key.offset = (u64)-1; 714 715 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 716 if (ret) 717 goto out; 718 719 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 720 721 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); 722 723 found_start = key.objectid; 724 found_end = key.objectid + key.offset; 725 ASSERT(start >= found_start && end <= found_end); 726 727 /* 728 * Okay, now that we've found the free space extent which contains the 729 * free space that we are removing, there are four cases: 730 * 731 * 1. We're using the whole extent: delete the key we found and 732 * decrement the free space extent count. 733 * 2. We are using part of the extent starting at the beginning: delete 734 * the key we found and insert a new key representing the leftover at 735 * the end. There is no net change in the number of extents. 736 * 3. We are using part of the extent ending at the end: delete the key 737 * we found and insert a new key representing the leftover at the 738 * beginning. There is no net change in the number of extents. 739 * 4. We are using part of the extent in the middle: delete the key we 740 * found and insert two new keys representing the leftovers on each 741 * side. Where we used to have one extent, we now have two, so increment 742 * the extent count. We may need to convert the block group to bitmaps 743 * as a result. 744 */ 745 746 /* Delete the existing key (cases 1-4). */ 747 ret = btrfs_del_item(trans, root, path); 748 if (ret) 749 goto out; 750 751 /* Add a key for leftovers at the beginning (cases 3 and 4). */ 752 if (start > found_start) { 753 key.objectid = found_start; 754 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 755 key.offset = start - found_start; 756 757 btrfs_release_path(path); 758 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 759 if (ret) 760 goto out; 761 new_extents++; 762 } 763 764 /* Add a key for leftovers at the end (cases 2 and 4). */ 765 if (end < found_end) { 766 key.objectid = end; 767 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 768 key.offset = found_end - end; 769 770 btrfs_release_path(path); 771 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 772 if (ret) 773 goto out; 774 new_extents++; 775 } 776 777 btrfs_release_path(path); 778 ret = update_free_space_extent_count(trans, block_group, path, 779 new_extents); 780 781out: 782 return ret; 783} 784 785EXPORT_FOR_TESTS 786int __remove_from_free_space_tree(struct btrfs_trans_handle *trans, 787 struct btrfs_block_group *block_group, 788 struct btrfs_path *path, u64 start, u64 size) 789{ 790 struct btrfs_free_space_info *info; 791 u32 flags; 792 int ret; 793 794 if (block_group->needs_free_space) { 795 ret = __add_block_group_free_space(trans, block_group, path); 796 if (ret) 797 return ret; 798 } 799 800 info = search_free_space_info(NULL, block_group, path, 0); 801 if (IS_ERR(info)) 802 return PTR_ERR(info); 803 flags = btrfs_free_space_flags(path->nodes[0], info); 804 btrfs_release_path(path); 805 806 if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { 807 return modify_free_space_bitmap(trans, block_group, path, 808 start, size, 1); 809 } else { 810 return remove_free_space_extent(trans, block_group, path, 811 start, size); 812 } 813} 814 815int remove_from_free_space_tree(struct btrfs_trans_handle *trans, 816 u64 start, u64 size) 817{ 818 struct btrfs_block_group *block_group; 819 struct btrfs_path *path; 820 int ret; 821 822 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 823 return 0; 824 825 path = btrfs_alloc_path(); 826 if (!path) { 827 ret = -ENOMEM; 828 goto out; 829 } 830 831 block_group = btrfs_lookup_block_group(trans->fs_info, start); 832 if (!block_group) { 833 ASSERT(0); 834 ret = -ENOENT; 835 goto out; 836 } 837 838 mutex_lock(&block_group->free_space_lock); 839 ret = __remove_from_free_space_tree(trans, block_group, path, start, 840 size); 841 mutex_unlock(&block_group->free_space_lock); 842 843 btrfs_put_block_group(block_group); 844out: 845 btrfs_free_path(path); 846 if (ret) 847 btrfs_abort_transaction(trans, ret); 848 return ret; 849} 850 851static int add_free_space_extent(struct btrfs_trans_handle *trans, 852 struct btrfs_block_group *block_group, 853 struct btrfs_path *path, 854 u64 start, u64 size) 855{ 856 struct btrfs_root *root = trans->fs_info->free_space_root; 857 struct btrfs_key key, new_key; 858 u64 found_start, found_end; 859 u64 end = start + size; 860 int new_extents = 1; 861 int ret; 862 863 /* 864 * We are adding a new extent of free space, but we need to merge 865 * extents. There are four cases here: 866 * 867 * 1. The new extent does not have any immediate neighbors to merge 868 * with: add the new key and increment the free space extent count. We 869 * may need to convert the block group to bitmaps as a result. 870 * 2. The new extent has an immediate neighbor before it: remove the 871 * previous key and insert a new key combining both of them. There is no 872 * net change in the number of extents. 873 * 3. The new extent has an immediate neighbor after it: remove the next 874 * key and insert a new key combining both of them. There is no net 875 * change in the number of extents. 876 * 4. The new extent has immediate neighbors on both sides: remove both 877 * of the keys and insert a new key combining all of them. Where we used 878 * to have two extents, we now have one, so decrement the extent count. 879 */ 880 881 new_key.objectid = start; 882 new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 883 new_key.offset = size; 884 885 /* Search for a neighbor on the left. */ 886 if (start == block_group->start) 887 goto right; 888 key.objectid = start - 1; 889 key.type = (u8)-1; 890 key.offset = (u64)-1; 891 892 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 893 if (ret) 894 goto out; 895 896 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 897 898 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { 899 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); 900 btrfs_release_path(path); 901 goto right; 902 } 903 904 found_start = key.objectid; 905 found_end = key.objectid + key.offset; 906 ASSERT(found_start >= block_group->start && 907 found_end > block_group->start); 908 ASSERT(found_start < start && found_end <= start); 909 910 /* 911 * Delete the neighbor on the left and absorb it into the new key (cases 912 * 2 and 4). 913 */ 914 if (found_end == start) { 915 ret = btrfs_del_item(trans, root, path); 916 if (ret) 917 goto out; 918 new_key.objectid = found_start; 919 new_key.offset += key.offset; 920 new_extents--; 921 } 922 btrfs_release_path(path); 923 924right: 925 /* Search for a neighbor on the right. */ 926 if (end == block_group->start + block_group->length) 927 goto insert; 928 key.objectid = end; 929 key.type = (u8)-1; 930 key.offset = (u64)-1; 931 932 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 933 if (ret) 934 goto out; 935 936 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 937 938 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { 939 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); 940 btrfs_release_path(path); 941 goto insert; 942 } 943 944 found_start = key.objectid; 945 found_end = key.objectid + key.offset; 946 ASSERT(found_start >= block_group->start && 947 found_end > block_group->start); 948 ASSERT((found_start < start && found_end <= start) || 949 (found_start >= end && found_end > end)); 950 951 /* 952 * Delete the neighbor on the right and absorb it into the new key 953 * (cases 3 and 4). 954 */ 955 if (found_start == end) { 956 ret = btrfs_del_item(trans, root, path); 957 if (ret) 958 goto out; 959 new_key.offset += key.offset; 960 new_extents--; 961 } 962 btrfs_release_path(path); 963 964insert: 965 /* Insert the new key (cases 1-4). */ 966 ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0); 967 if (ret) 968 goto out; 969 970 btrfs_release_path(path); 971 ret = update_free_space_extent_count(trans, block_group, path, 972 new_extents); 973 974out: 975 return ret; 976} 977 978EXPORT_FOR_TESTS 979int __add_to_free_space_tree(struct btrfs_trans_handle *trans, 980 struct btrfs_block_group *block_group, 981 struct btrfs_path *path, u64 start, u64 size) 982{ 983 struct btrfs_free_space_info *info; 984 u32 flags; 985 int ret; 986 987 if (block_group->needs_free_space) { 988 ret = __add_block_group_free_space(trans, block_group, path); 989 if (ret) 990 return ret; 991 } 992 993 info = search_free_space_info(NULL, block_group, path, 0); 994 if (IS_ERR(info)) 995 return PTR_ERR(info); 996 flags = btrfs_free_space_flags(path->nodes[0], info); 997 btrfs_release_path(path); 998 999 if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { 1000 return modify_free_space_bitmap(trans, block_group, path, 1001 start, size, 0); 1002 } else { 1003 return add_free_space_extent(trans, block_group, path, start, 1004 size); 1005 } 1006} 1007 1008int add_to_free_space_tree(struct btrfs_trans_handle *trans, 1009 u64 start, u64 size) 1010{ 1011 struct btrfs_block_group *block_group; 1012 struct btrfs_path *path; 1013 int ret; 1014 1015 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 1016 return 0; 1017 1018 path = btrfs_alloc_path(); 1019 if (!path) { 1020 ret = -ENOMEM; 1021 goto out; 1022 } 1023 1024 block_group = btrfs_lookup_block_group(trans->fs_info, start); 1025 if (!block_group) { 1026 ASSERT(0); 1027 ret = -ENOENT; 1028 goto out; 1029 } 1030 1031 mutex_lock(&block_group->free_space_lock); 1032 ret = __add_to_free_space_tree(trans, block_group, path, start, size); 1033 mutex_unlock(&block_group->free_space_lock); 1034 1035 btrfs_put_block_group(block_group); 1036out: 1037 btrfs_free_path(path); 1038 if (ret) 1039 btrfs_abort_transaction(trans, ret); 1040 return ret; 1041} 1042 1043/* 1044 * Populate the free space tree by walking the extent tree. Operations on the 1045 * extent tree that happen as a result of writes to the free space tree will go 1046 * through the normal add/remove hooks. 1047 */ 1048static int populate_free_space_tree(struct btrfs_trans_handle *trans, 1049 struct btrfs_block_group *block_group) 1050{ 1051 struct btrfs_root *extent_root = trans->fs_info->extent_root; 1052 struct btrfs_path *path, *path2; 1053 struct btrfs_key key; 1054 u64 start, end; 1055 int ret; 1056 1057 path = btrfs_alloc_path(); 1058 if (!path) 1059 return -ENOMEM; 1060 path->reada = READA_FORWARD; 1061 1062 path2 = btrfs_alloc_path(); 1063 if (!path2) { 1064 btrfs_free_path(path); 1065 return -ENOMEM; 1066 } 1067 1068 ret = add_new_free_space_info(trans, block_group, path2); 1069 if (ret) 1070 goto out; 1071 1072 mutex_lock(&block_group->free_space_lock); 1073 1074 /* 1075 * Iterate through all of the extent and metadata items in this block 1076 * group, adding the free space between them and the free space at the 1077 * end. Note that EXTENT_ITEM and METADATA_ITEM are less than 1078 * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's 1079 * contained in. 1080 */ 1081 key.objectid = block_group->start; 1082 key.type = BTRFS_EXTENT_ITEM_KEY; 1083 key.offset = 0; 1084 1085 ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0); 1086 if (ret < 0) 1087 goto out_locked; 1088 ASSERT(ret == 0); 1089 1090 start = block_group->start; 1091 end = block_group->start + block_group->length; 1092 while (1) { 1093 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1094 1095 if (key.type == BTRFS_EXTENT_ITEM_KEY || 1096 key.type == BTRFS_METADATA_ITEM_KEY) { 1097 if (key.objectid >= end) 1098 break; 1099 1100 if (start < key.objectid) { 1101 ret = __add_to_free_space_tree(trans, 1102 block_group, 1103 path2, start, 1104 key.objectid - 1105 start); 1106 if (ret) 1107 goto out_locked; 1108 } 1109 start = key.objectid; 1110 if (key.type == BTRFS_METADATA_ITEM_KEY) 1111 start += trans->fs_info->nodesize; 1112 else 1113 start += key.offset; 1114 } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { 1115 if (key.objectid != block_group->start) 1116 break; 1117 } 1118 1119 ret = btrfs_next_item(extent_root, path); 1120 if (ret < 0) 1121 goto out_locked; 1122 if (ret) 1123 break; 1124 } 1125 if (start < end) { 1126 ret = __add_to_free_space_tree(trans, block_group, path2, 1127 start, end - start); 1128 if (ret) 1129 goto out_locked; 1130 } 1131 1132 ret = 0; 1133out_locked: 1134 mutex_unlock(&block_group->free_space_lock); 1135out: 1136 btrfs_free_path(path2); 1137 btrfs_free_path(path); 1138 return ret; 1139} 1140 1141int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info) 1142{ 1143 struct btrfs_trans_handle *trans; 1144 struct btrfs_root *tree_root = fs_info->tree_root; 1145 struct btrfs_root *free_space_root; 1146 struct btrfs_block_group *block_group; 1147 struct rb_node *node; 1148 int ret; 1149 1150 trans = btrfs_start_transaction(tree_root, 0); 1151 if (IS_ERR(trans)) 1152 return PTR_ERR(trans); 1153 1154 set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 1155 set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 1156 free_space_root = btrfs_create_tree(trans, 1157 BTRFS_FREE_SPACE_TREE_OBJECTID); 1158 if (IS_ERR(free_space_root)) { 1159 ret = PTR_ERR(free_space_root); 1160 goto abort; 1161 } 1162 fs_info->free_space_root = free_space_root; 1163 1164 node = rb_first(&fs_info->block_group_cache_tree); 1165 while (node) { 1166 block_group = rb_entry(node, struct btrfs_block_group, 1167 cache_node); 1168 ret = populate_free_space_tree(trans, block_group); 1169 if (ret) 1170 goto abort; 1171 node = rb_next(node); 1172 } 1173 1174 btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE); 1175 btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID); 1176 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 1177 ret = btrfs_commit_transaction(trans); 1178 1179 /* 1180 * Now that we've committed the transaction any reading of our commit 1181 * root will be safe, so we can cache from the free space tree now. 1182 */ 1183 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 1184 return ret; 1185 1186abort: 1187 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 1188 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 1189 btrfs_abort_transaction(trans, ret); 1190 btrfs_end_transaction(trans); 1191 return ret; 1192} 1193 1194static int clear_free_space_tree(struct btrfs_trans_handle *trans, 1195 struct btrfs_root *root) 1196{ 1197 struct btrfs_path *path; 1198 struct btrfs_key key; 1199 int nr; 1200 int ret; 1201 1202 path = btrfs_alloc_path(); 1203 if (!path) 1204 return -ENOMEM; 1205 1206 path->leave_spinning = 1; 1207 1208 key.objectid = 0; 1209 key.type = 0; 1210 key.offset = 0; 1211 1212 while (1) { 1213 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 1214 if (ret < 0) 1215 goto out; 1216 1217 nr = btrfs_header_nritems(path->nodes[0]); 1218 if (!nr) 1219 break; 1220 1221 path->slots[0] = 0; 1222 ret = btrfs_del_items(trans, root, path, 0, nr); 1223 if (ret) 1224 goto out; 1225 1226 btrfs_release_path(path); 1227 } 1228 1229 ret = 0; 1230out: 1231 btrfs_free_path(path); 1232 return ret; 1233} 1234 1235int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info) 1236{ 1237 struct btrfs_trans_handle *trans; 1238 struct btrfs_root *tree_root = fs_info->tree_root; 1239 struct btrfs_root *free_space_root = fs_info->free_space_root; 1240 int ret; 1241 1242 trans = btrfs_start_transaction(tree_root, 0); 1243 if (IS_ERR(trans)) 1244 return PTR_ERR(trans); 1245 1246 btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE); 1247 btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID); 1248 fs_info->free_space_root = NULL; 1249 1250 ret = clear_free_space_tree(trans, free_space_root); 1251 if (ret) 1252 goto abort; 1253 1254 ret = btrfs_del_root(trans, &free_space_root->root_key); 1255 if (ret) 1256 goto abort; 1257 1258 list_del(&free_space_root->dirty_list); 1259 1260 btrfs_tree_lock(free_space_root->node); 1261 btrfs_clean_tree_block(free_space_root->node); 1262 btrfs_tree_unlock(free_space_root->node); 1263 btrfs_free_tree_block(trans, free_space_root, free_space_root->node, 1264 0, 1); 1265 1266 btrfs_put_root(free_space_root); 1267 1268 return btrfs_commit_transaction(trans); 1269 1270abort: 1271 btrfs_abort_transaction(trans, ret); 1272 btrfs_end_transaction(trans); 1273 return ret; 1274} 1275 1276static int __add_block_group_free_space(struct btrfs_trans_handle *trans, 1277 struct btrfs_block_group *block_group, 1278 struct btrfs_path *path) 1279{ 1280 int ret; 1281 1282 block_group->needs_free_space = 0; 1283 1284 ret = add_new_free_space_info(trans, block_group, path); 1285 if (ret) 1286 return ret; 1287 1288 return __add_to_free_space_tree(trans, block_group, path, 1289 block_group->start, 1290 block_group->length); 1291} 1292 1293int add_block_group_free_space(struct btrfs_trans_handle *trans, 1294 struct btrfs_block_group *block_group) 1295{ 1296 struct btrfs_fs_info *fs_info = trans->fs_info; 1297 struct btrfs_path *path = NULL; 1298 int ret = 0; 1299 1300 if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) 1301 return 0; 1302 1303 mutex_lock(&block_group->free_space_lock); 1304 if (!block_group->needs_free_space) 1305 goto out; 1306 1307 path = btrfs_alloc_path(); 1308 if (!path) { 1309 ret = -ENOMEM; 1310 goto out; 1311 } 1312 1313 ret = __add_block_group_free_space(trans, block_group, path); 1314 1315out: 1316 btrfs_free_path(path); 1317 mutex_unlock(&block_group->free_space_lock); 1318 if (ret) 1319 btrfs_abort_transaction(trans, ret); 1320 return ret; 1321} 1322 1323int remove_block_group_free_space(struct btrfs_trans_handle *trans, 1324 struct btrfs_block_group *block_group) 1325{ 1326 struct btrfs_root *root = trans->fs_info->free_space_root; 1327 struct btrfs_path *path; 1328 struct btrfs_key key, found_key; 1329 struct extent_buffer *leaf; 1330 u64 start, end; 1331 int done = 0, nr; 1332 int ret; 1333 1334 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 1335 return 0; 1336 1337 if (block_group->needs_free_space) { 1338 /* We never added this block group to the free space tree. */ 1339 return 0; 1340 } 1341 1342 path = btrfs_alloc_path(); 1343 if (!path) { 1344 ret = -ENOMEM; 1345 goto out; 1346 } 1347 1348 start = block_group->start; 1349 end = block_group->start + block_group->length; 1350 1351 key.objectid = end - 1; 1352 key.type = (u8)-1; 1353 key.offset = (u64)-1; 1354 1355 while (!done) { 1356 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 1357 if (ret) 1358 goto out; 1359 1360 leaf = path->nodes[0]; 1361 nr = 0; 1362 path->slots[0]++; 1363 while (path->slots[0] > 0) { 1364 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 1365 1366 if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 1367 ASSERT(found_key.objectid == block_group->start); 1368 ASSERT(found_key.offset == block_group->length); 1369 done = 1; 1370 nr++; 1371 path->slots[0]--; 1372 break; 1373 } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY || 1374 found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) { 1375 ASSERT(found_key.objectid >= start); 1376 ASSERT(found_key.objectid < end); 1377 ASSERT(found_key.objectid + found_key.offset <= end); 1378 nr++; 1379 path->slots[0]--; 1380 } else { 1381 ASSERT(0); 1382 } 1383 } 1384 1385 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 1386 if (ret) 1387 goto out; 1388 btrfs_release_path(path); 1389 } 1390 1391 ret = 0; 1392out: 1393 btrfs_free_path(path); 1394 if (ret) 1395 btrfs_abort_transaction(trans, ret); 1396 return ret; 1397} 1398 1399static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl, 1400 struct btrfs_path *path, 1401 u32 expected_extent_count) 1402{ 1403 struct btrfs_block_group *block_group; 1404 struct btrfs_fs_info *fs_info; 1405 struct btrfs_root *root; 1406 struct btrfs_key key; 1407 int prev_bit = 0, bit; 1408 /* Initialize to silence GCC. */ 1409 u64 extent_start = 0; 1410 u64 end, offset; 1411 u64 total_found = 0; 1412 u32 extent_count = 0; 1413 int ret; 1414 1415 block_group = caching_ctl->block_group; 1416 fs_info = block_group->fs_info; 1417 root = fs_info->free_space_root; 1418 1419 end = block_group->start + block_group->length; 1420 1421 while (1) { 1422 ret = btrfs_next_item(root, path); 1423 if (ret < 0) 1424 goto out; 1425 if (ret) 1426 break; 1427 1428 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1429 1430 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) 1431 break; 1432 1433 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 1434 ASSERT(key.objectid < end && key.objectid + key.offset <= end); 1435 1436 caching_ctl->progress = key.objectid; 1437 1438 offset = key.objectid; 1439 while (offset < key.objectid + key.offset) { 1440 bit = free_space_test_bit(block_group, path, offset); 1441 if (prev_bit == 0 && bit == 1) { 1442 extent_start = offset; 1443 } else if (prev_bit == 1 && bit == 0) { 1444 total_found += add_new_free_space(block_group, 1445 extent_start, 1446 offset); 1447 if (total_found > CACHING_CTL_WAKE_UP) { 1448 total_found = 0; 1449 wake_up(&caching_ctl->wait); 1450 } 1451 extent_count++; 1452 } 1453 prev_bit = bit; 1454 offset += fs_info->sectorsize; 1455 } 1456 } 1457 if (prev_bit == 1) { 1458 total_found += add_new_free_space(block_group, extent_start, 1459 end); 1460 extent_count++; 1461 } 1462 1463 if (extent_count != expected_extent_count) { 1464 btrfs_err(fs_info, 1465 "incorrect extent count for %llu; counted %u, expected %u", 1466 block_group->start, extent_count, 1467 expected_extent_count); 1468 ASSERT(0); 1469 ret = -EIO; 1470 goto out; 1471 } 1472 1473 caching_ctl->progress = (u64)-1; 1474 1475 ret = 0; 1476out: 1477 return ret; 1478} 1479 1480static int load_free_space_extents(struct btrfs_caching_control *caching_ctl, 1481 struct btrfs_path *path, 1482 u32 expected_extent_count) 1483{ 1484 struct btrfs_block_group *block_group; 1485 struct btrfs_fs_info *fs_info; 1486 struct btrfs_root *root; 1487 struct btrfs_key key; 1488 u64 end; 1489 u64 total_found = 0; 1490 u32 extent_count = 0; 1491 int ret; 1492 1493 block_group = caching_ctl->block_group; 1494 fs_info = block_group->fs_info; 1495 root = fs_info->free_space_root; 1496 1497 end = block_group->start + block_group->length; 1498 1499 while (1) { 1500 ret = btrfs_next_item(root, path); 1501 if (ret < 0) 1502 goto out; 1503 if (ret) 1504 break; 1505 1506 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1507 1508 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) 1509 break; 1510 1511 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); 1512 ASSERT(key.objectid < end && key.objectid + key.offset <= end); 1513 1514 caching_ctl->progress = key.objectid; 1515 1516 total_found += add_new_free_space(block_group, key.objectid, 1517 key.objectid + key.offset); 1518 if (total_found > CACHING_CTL_WAKE_UP) { 1519 total_found = 0; 1520 wake_up(&caching_ctl->wait); 1521 } 1522 extent_count++; 1523 } 1524 1525 if (extent_count != expected_extent_count) { 1526 btrfs_err(fs_info, 1527 "incorrect extent count for %llu; counted %u, expected %u", 1528 block_group->start, extent_count, 1529 expected_extent_count); 1530 ASSERT(0); 1531 ret = -EIO; 1532 goto out; 1533 } 1534 1535 caching_ctl->progress = (u64)-1; 1536 1537 ret = 0; 1538out: 1539 return ret; 1540} 1541 1542int load_free_space_tree(struct btrfs_caching_control *caching_ctl) 1543{ 1544 struct btrfs_block_group *block_group; 1545 struct btrfs_free_space_info *info; 1546 struct btrfs_path *path; 1547 u32 extent_count, flags; 1548 int ret; 1549 1550 block_group = caching_ctl->block_group; 1551 1552 path = btrfs_alloc_path(); 1553 if (!path) 1554 return -ENOMEM; 1555 1556 /* 1557 * Just like caching_thread() doesn't want to deadlock on the extent 1558 * tree, we don't want to deadlock on the free space tree. 1559 */ 1560 path->skip_locking = 1; 1561 path->search_commit_root = 1; 1562 path->reada = READA_FORWARD; 1563 1564 info = search_free_space_info(NULL, block_group, path, 0); 1565 if (IS_ERR(info)) { 1566 ret = PTR_ERR(info); 1567 goto out; 1568 } 1569 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); 1570 flags = btrfs_free_space_flags(path->nodes[0], info); 1571 1572 /* 1573 * We left path pointing to the free space info item, so now 1574 * load_free_space_foo can just iterate through the free space tree from 1575 * there. 1576 */ 1577 if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) 1578 ret = load_free_space_bitmaps(caching_ctl, path, extent_count); 1579 else 1580 ret = load_free_space_extents(caching_ctl, path, extent_count); 1581 1582out: 1583 btrfs_free_path(path); 1584 return ret; 1585} 1586