1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2008 Red Hat. All rights reserved. 4 */ 5 6 #include <linux/pagemap.h> 7 #include <linux/sched.h> 8 #include <linux/sched/signal.h> 9 #include <linux/slab.h> 10 #include <linux/math64.h> 11 #include <linux/ratelimit.h> 12 #include <linux/sched/mm.h> 13 #include <linux/string_choices.h> 14 #include "extent-tree.h" 15 #include "fs.h" 16 #include "messages.h" 17 #include "misc.h" 18 #include "free-space-cache.h" 19 #include "transaction.h" 20 #include "disk-io.h" 21 #include "extent_io.h" 22 #include "space-info.h" 23 #include "block-group.h" 24 #include "discard.h" 25 #include "inode-item.h" 26 #include "accessors.h" 27 #include "file-item.h" 28 #include "file.h" 29 #include "super.h" 30 #include "relocation.h" 31 32 #define BITS_PER_BITMAP (PAGE_SIZE * 8UL) 33 #define MAX_CACHE_BYTES_PER_GIG SZ_64K 34 #define FORCE_EXTENT_THRESHOLD SZ_1M 35 36 static struct kmem_cache *btrfs_free_space_cachep; 37 static struct kmem_cache *btrfs_free_space_bitmap_cachep; 38 39 static int link_free_space(struct btrfs_free_space_ctl *ctl, 40 struct btrfs_free_space *info); 41 static void unlink_free_space(struct btrfs_free_space_ctl *ctl, 42 struct btrfs_free_space *info, bool update_stat); 43 static int search_bitmap(struct btrfs_free_space_ctl *ctl, 44 struct btrfs_free_space *bitmap_info, u64 *offset, 45 u64 *bytes, bool for_alloc); 46 static void free_bitmap(struct btrfs_free_space_ctl *ctl, 47 struct btrfs_free_space *bitmap_info); 48 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, 49 struct btrfs_free_space *info, u64 offset, 50 u64 bytes, bool update_stats); 51 52 static void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl) 53 { 54 struct btrfs_free_space *info; 55 struct rb_node *node; 56 57 while ((node = rb_last(&ctl->free_space_offset)) != NULL) { 58 info = rb_entry(node, struct btrfs_free_space, offset_index); 59 if (!info->bitmap) { 60 unlink_free_space(ctl, info, true); 61 kmem_cache_free(btrfs_free_space_cachep, info); 62 } else { 63 free_bitmap(ctl, info); 64 } 65 66 cond_resched_lock(&ctl->tree_lock); 67 } 68 } 69 70 static struct inode *__lookup_free_space_inode(struct btrfs_root *root, 71 struct btrfs_path *path, 72 u64 offset) 73 { 74 struct btrfs_key key; 75 struct btrfs_key location; 76 struct btrfs_disk_key disk_key; 77 struct btrfs_free_space_header *header; 78 struct extent_buffer *leaf; 79 struct btrfs_inode *inode; 80 unsigned nofs_flag; 81 int ret; 82 83 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 84 key.type = 0; 85 key.offset = offset; 86 87 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 88 if (ret < 0) 89 return ERR_PTR(ret); 90 if (ret > 0) { 91 btrfs_release_path(path); 92 return ERR_PTR(-ENOENT); 93 } 94 95 leaf = path->nodes[0]; 96 header = btrfs_item_ptr(leaf, path->slots[0], 97 struct btrfs_free_space_header); 98 btrfs_free_space_key(leaf, header, &disk_key); 99 btrfs_disk_key_to_cpu(&location, &disk_key); 100 btrfs_release_path(path); 101 102 /* 103 * We are often under a trans handle at this point, so we need to make 104 * sure NOFS is set to keep us from deadlocking. 105 */ 106 nofs_flag = memalloc_nofs_save(); 107 inode = btrfs_iget_path(location.objectid, root, path); 108 btrfs_release_path(path); 109 memalloc_nofs_restore(nofs_flag); 110 if (IS_ERR(inode)) 111 return ERR_CAST(inode); 112 113 return &inode->vfs_inode; 114 } 115 116 struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group, 117 struct btrfs_path *path) 118 { 119 struct btrfs_fs_info *fs_info = block_group->fs_info; 120 struct inode *inode = NULL; 121 122 spin_lock(&block_group->lock); 123 if (block_group->inode) 124 inode = igrab(&block_group->inode->vfs_inode); 125 spin_unlock(&block_group->lock); 126 if (inode) 127 return inode; 128 129 inode = __lookup_free_space_inode(fs_info->tree_root, path, 130 block_group->start); 131 if (IS_ERR(inode)) 132 return inode; 133 134 spin_lock(&block_group->lock); 135 if (!test_and_set_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags)) 136 block_group->inode = BTRFS_I(igrab(inode)); 137 spin_unlock(&block_group->lock); 138 139 return inode; 140 } 141 142 /* 143 * inode is an optional sink: if it is NULL, btrfs_remove_free_space_inode 144 * handles lookup, otherwise it takes ownership and iputs the inode. 145 * Don't reuse an inode pointer after passing it into this function. 146 */ 147 int btrfs_remove_free_space_inode(struct btrfs_trans_handle *trans, 148 struct inode *inode, 149 struct btrfs_block_group *block_group) 150 { 151 BTRFS_PATH_AUTO_FREE(path); 152 struct btrfs_key key; 153 int ret = 0; 154 155 path = btrfs_alloc_path(); 156 if (!path) 157 return -ENOMEM; 158 159 if (!inode) 160 inode = lookup_free_space_inode(block_group, path); 161 if (IS_ERR(inode)) { 162 if (PTR_ERR(inode) != -ENOENT) 163 ret = PTR_ERR(inode); 164 return ret; 165 } 166 ret = btrfs_orphan_add(trans, BTRFS_I(inode)); 167 if (ret) { 168 btrfs_add_delayed_iput(BTRFS_I(inode)); 169 return ret; 170 } 171 clear_nlink(inode); 172 /* 173 * Persist the zero link count, so that if the delayed iput below 174 * doesn't get to evict the inode, the orphan cleanup on the next mount 175 * evicts it instead of only deleting the orphan item. 176 */ 177 ret = btrfs_update_inode(trans, BTRFS_I(inode)); 178 if (ret) { 179 btrfs_add_delayed_iput(BTRFS_I(inode)); 180 return ret; 181 } 182 /* One for the block groups ref */ 183 spin_lock(&block_group->lock); 184 if (test_and_clear_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags)) { 185 block_group->inode = NULL; 186 spin_unlock(&block_group->lock); 187 iput(inode); 188 } else { 189 spin_unlock(&block_group->lock); 190 } 191 /* One for the lookup ref */ 192 btrfs_add_delayed_iput(BTRFS_I(inode)); 193 194 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 195 key.type = 0; 196 key.offset = block_group->start; 197 ret = btrfs_search_slot(trans, trans->fs_info->tree_root, &key, path, 198 -1, 1); 199 if (ret) { 200 if (ret > 0) 201 ret = 0; 202 return ret; 203 } 204 return btrfs_del_item(trans, trans->fs_info->tree_root, path); 205 } 206 207 int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans, 208 struct inode *vfs_inode) 209 { 210 struct btrfs_truncate_control control = { 211 .inode = BTRFS_I(vfs_inode), 212 .new_size = 0, 213 .ino = btrfs_ino(BTRFS_I(vfs_inode)), 214 .min_type = BTRFS_EXTENT_DATA_KEY, 215 .clear_extent_range = true, 216 }; 217 struct btrfs_inode *inode = BTRFS_I(vfs_inode); 218 struct btrfs_root *root = inode->root; 219 struct extent_state *cached_state = NULL; 220 int ret = 0; 221 222 btrfs_i_size_write(inode, 0); 223 truncate_pagecache(vfs_inode, 0); 224 225 btrfs_lock_extent(&inode->io_tree, 0, (u64)-1, &cached_state); 226 btrfs_drop_extent_map_range(inode, 0, (u64)-1, false); 227 228 /* 229 * We skip the throttling logic for free space cache inodes, so we don't 230 * need to check for -EAGAIN. 231 */ 232 ret = btrfs_truncate_inode_items(trans, root, &control); 233 234 inode_sub_bytes(&inode->vfs_inode, control.sub_bytes); 235 btrfs_inode_safe_disk_i_size_write(inode, control.last_size); 236 237 btrfs_unlock_extent(&inode->io_tree, 0, (u64)-1, &cached_state); 238 if (ret) 239 goto fail; 240 241 ret = btrfs_update_inode(trans, inode); 242 243 fail: 244 if (ret) 245 btrfs_abort_transaction(trans, ret); 246 247 return ret; 248 } 249 250 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl) 251 { 252 struct btrfs_block_group *block_group = ctl->block_group; 253 const int unit = block_group->fs_info->sectorsize; 254 u64 max_bytes; 255 u64 bitmap_bytes; 256 u64 extent_bytes; 257 u64 size = block_group->length; 258 u64 bytes_per_bg = BITS_PER_BITMAP * unit; 259 u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg); 260 261 max_bitmaps = max_t(u64, max_bitmaps, 1); 262 263 if (ctl->total_bitmaps > max_bitmaps) 264 btrfs_err(block_group->fs_info, 265 "invalid free space control: bg start=%llu len=%llu total_bitmaps=%u unit=%u max_bitmaps=%llu bytes_per_bg=%llu", 266 block_group->start, block_group->length, 267 ctl->total_bitmaps, unit, max_bitmaps, 268 bytes_per_bg); 269 ASSERT(ctl->total_bitmaps <= max_bitmaps); 270 271 /* 272 * We are trying to keep the total amount of memory used per 1GiB of 273 * space to be MAX_CACHE_BYTES_PER_GIG. However, with a reclamation 274 * mechanism of pulling extents >= FORCE_EXTENT_THRESHOLD out of 275 * bitmaps, we may end up using more memory than this. 276 */ 277 if (size < SZ_1G) 278 max_bytes = MAX_CACHE_BYTES_PER_GIG; 279 else 280 max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G); 281 282 bitmap_bytes = ctl->total_bitmaps * unit; 283 284 /* 285 * we want the extent entry threshold to always be at most 1/2 the max 286 * bytes we can have, or whatever is less than that. 287 */ 288 extent_bytes = max_bytes - bitmap_bytes; 289 extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1); 290 291 ctl->extents_thresh = 292 div_u64(extent_bytes, sizeof(struct btrfs_free_space)); 293 } 294 295 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit, 296 u64 offset) 297 { 298 ASSERT(offset >= bitmap_start); 299 offset -= bitmap_start; 300 return (unsigned long)(div_u64(offset, unit)); 301 } 302 303 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit) 304 { 305 return (unsigned long)(div_u64(bytes, unit)); 306 } 307 308 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl, 309 u64 offset) 310 { 311 u64 bitmap_start; 312 u64 bytes_per_bitmap; 313 314 bytes_per_bitmap = BITS_PER_BITMAP * ctl->block_group->fs_info->sectorsize; 315 bitmap_start = offset - ctl->block_group->start; 316 bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap); 317 bitmap_start *= bytes_per_bitmap; 318 bitmap_start += ctl->block_group->start; 319 320 return bitmap_start; 321 } 322 323 static int tree_insert_offset(struct btrfs_free_space_ctl *ctl, 324 struct btrfs_free_cluster *cluster, 325 struct btrfs_free_space *new_entry) 326 { 327 struct rb_root *root; 328 struct rb_node **p; 329 struct rb_node *parent = NULL; 330 331 lockdep_assert_held(&ctl->tree_lock); 332 333 if (cluster) { 334 lockdep_assert_held(&cluster->lock); 335 root = &cluster->root; 336 } else { 337 root = &ctl->free_space_offset; 338 } 339 340 p = &root->rb_node; 341 342 while (*p) { 343 struct btrfs_free_space *info; 344 345 parent = *p; 346 info = rb_entry(parent, struct btrfs_free_space, offset_index); 347 348 if (new_entry->offset < info->offset) { 349 p = &(*p)->rb_left; 350 } else if (new_entry->offset > info->offset) { 351 p = &(*p)->rb_right; 352 } else { 353 /* 354 * we could have a bitmap entry and an extent entry 355 * share the same offset. If this is the case, we want 356 * the extent entry to always be found first if we do a 357 * linear search through the tree, since we want to have 358 * the quickest allocation time, and allocating from an 359 * extent is faster than allocating from a bitmap. So 360 * if we're inserting a bitmap and we find an entry at 361 * this offset, we want to go right, or after this entry 362 * logically. If we are inserting an extent and we've 363 * found a bitmap, we want to go left, or before 364 * logically. 365 */ 366 if (new_entry->bitmap) { 367 if (info->bitmap) { 368 WARN_ON_ONCE(1); 369 return -EEXIST; 370 } 371 p = &(*p)->rb_right; 372 } else { 373 if (!info->bitmap) { 374 WARN_ON_ONCE(1); 375 return -EEXIST; 376 } 377 p = &(*p)->rb_left; 378 } 379 } 380 } 381 382 rb_link_node(&new_entry->offset_index, parent, p); 383 rb_insert_color(&new_entry->offset_index, root); 384 385 return 0; 386 } 387 388 /* 389 * This is a little subtle. We *only* have ->max_extent_size set if we actually 390 * searched through the bitmap and figured out the largest ->max_extent_size, 391 * otherwise it's 0. In the case that it's 0 we don't want to tell the 392 * allocator the wrong thing, we want to use the actual real max_extent_size 393 * we've found already if it's larger, or we want to use ->bytes. 394 * 395 * This matters because find_free_space() will skip entries who's ->bytes is 396 * less than the required bytes. So if we didn't search down this bitmap, we 397 * may pick some previous entry that has a smaller ->max_extent_size than we 398 * have. For example, assume we have two entries, one that has 399 * ->max_extent_size set to 4K and ->bytes set to 1M. A second entry hasn't set 400 * ->max_extent_size yet, has ->bytes set to 8K and it's contiguous. We will 401 * call into find_free_space(), and return with max_extent_size == 4K, because 402 * that first bitmap entry had ->max_extent_size set, but the second one did 403 * not. If instead we returned 8K we'd come in searching for 8K, and find the 404 * 8K contiguous range. 405 * 406 * Consider the other case, we have 2 8K chunks in that second entry and still 407 * don't have ->max_extent_size set. We'll return 16K, and the next time the 408 * allocator comes in it'll fully search our second bitmap, and this time it'll 409 * get an uptodate value of 8K as the maximum chunk size. Then we'll get the 410 * right allocation the next loop through. 411 */ 412 static inline u64 get_max_extent_size(const struct btrfs_free_space *entry) 413 { 414 if (entry->bitmap && entry->max_extent_size) 415 return entry->max_extent_size; 416 return entry->bytes; 417 } 418 419 /* 420 * We want the largest entry to be leftmost, so this is inverted from what you'd 421 * normally expect. 422 */ 423 static bool entry_less(struct rb_node *node, const struct rb_node *parent) 424 { 425 const struct btrfs_free_space *entry, *exist; 426 427 entry = rb_entry(node, struct btrfs_free_space, bytes_index); 428 exist = rb_entry(parent, struct btrfs_free_space, bytes_index); 429 return get_max_extent_size(exist) < get_max_extent_size(entry); 430 } 431 432 /* 433 * searches the tree for the given offset. 434 * 435 * fuzzy - If this is set, then we are trying to make an allocation, and we just 436 * want a section that has at least bytes size and comes at or after the given 437 * offset. 438 */ 439 static struct btrfs_free_space * 440 tree_search_offset(struct btrfs_free_space_ctl *ctl, 441 u64 offset, int bitmap_only, int fuzzy) 442 { 443 struct rb_node *n = ctl->free_space_offset.rb_node; 444 struct btrfs_free_space *entry = NULL, *prev = NULL; 445 const int unit = ctl->block_group->fs_info->sectorsize; 446 447 lockdep_assert_held(&ctl->tree_lock); 448 449 /* find entry that is closest to the 'offset' */ 450 while (n) { 451 entry = rb_entry(n, struct btrfs_free_space, offset_index); 452 prev = entry; 453 454 if (offset < entry->offset) 455 n = n->rb_left; 456 else if (offset > entry->offset) 457 n = n->rb_right; 458 else 459 break; 460 461 entry = NULL; 462 } 463 464 if (bitmap_only) { 465 if (!entry) 466 return NULL; 467 if (entry->bitmap) 468 return entry; 469 470 /* 471 * bitmap entry and extent entry may share same offset, 472 * in that case, bitmap entry comes after extent entry. 473 */ 474 n = rb_next(n); 475 if (!n) 476 return NULL; 477 entry = rb_entry(n, struct btrfs_free_space, offset_index); 478 if (entry->offset != offset) 479 return NULL; 480 481 WARN_ON(!entry->bitmap); 482 return entry; 483 } else if (entry) { 484 if (entry->bitmap) { 485 /* 486 * if previous extent entry covers the offset, 487 * we should return it instead of the bitmap entry 488 */ 489 n = rb_prev(&entry->offset_index); 490 if (n) { 491 prev = rb_entry(n, struct btrfs_free_space, 492 offset_index); 493 if (!prev->bitmap && 494 prev->offset + prev->bytes > offset) 495 entry = prev; 496 } 497 } 498 return entry; 499 } 500 501 if (!prev) 502 return NULL; 503 504 /* find last entry before the 'offset' */ 505 entry = prev; 506 if (entry->offset > offset) { 507 n = rb_prev(&entry->offset_index); 508 if (n) { 509 entry = rb_entry(n, struct btrfs_free_space, 510 offset_index); 511 ASSERT(entry->offset <= offset); 512 } else { 513 if (fuzzy) 514 return entry; 515 else 516 return NULL; 517 } 518 } 519 520 if (entry->bitmap) { 521 n = rb_prev(&entry->offset_index); 522 if (n) { 523 prev = rb_entry(n, struct btrfs_free_space, 524 offset_index); 525 if (!prev->bitmap && 526 prev->offset + prev->bytes > offset) 527 return prev; 528 } 529 if (entry->offset + BITS_PER_BITMAP * unit > offset) 530 return entry; 531 } else if (entry->offset + entry->bytes > offset) 532 return entry; 533 534 if (!fuzzy) 535 return NULL; 536 537 while (1) { 538 n = rb_next(&entry->offset_index); 539 if (!n) 540 return NULL; 541 entry = rb_entry(n, struct btrfs_free_space, offset_index); 542 if (entry->bitmap) { 543 if (entry->offset + BITS_PER_BITMAP * unit > offset) 544 break; 545 } else { 546 if (entry->offset + entry->bytes > offset) 547 break; 548 } 549 } 550 return entry; 551 } 552 553 static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl, 554 struct btrfs_free_space *info, 555 bool update_stat) 556 { 557 lockdep_assert_held(&ctl->tree_lock); 558 559 rb_erase(&info->offset_index, &ctl->free_space_offset); 560 rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes); 561 ctl->free_extents--; 562 563 if (!info->bitmap && !btrfs_free_space_trimmed(info)) { 564 ctl->discardable_extents[BTRFS_STAT_CURR]--; 565 ctl->discardable_bytes[BTRFS_STAT_CURR] -= info->bytes; 566 } 567 568 if (update_stat) 569 ctl->free_space -= info->bytes; 570 } 571 572 static int link_free_space(struct btrfs_free_space_ctl *ctl, 573 struct btrfs_free_space *info) 574 { 575 int ret = 0; 576 577 lockdep_assert_held(&ctl->tree_lock); 578 579 ASSERT(info->bytes || info->bitmap); 580 ret = tree_insert_offset(ctl, NULL, info); 581 if (ret) 582 return ret; 583 584 rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less); 585 586 if (!info->bitmap && !btrfs_free_space_trimmed(info)) { 587 ctl->discardable_extents[BTRFS_STAT_CURR]++; 588 ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes; 589 } 590 591 ctl->free_space += info->bytes; 592 ctl->free_extents++; 593 return ret; 594 } 595 596 static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl, 597 struct btrfs_free_space *info) 598 { 599 ASSERT(info->bitmap); 600 601 /* 602 * If our entry is empty it's because we're on a cluster and we don't 603 * want to re-link it into our ctl bytes index. 604 */ 605 if (RB_EMPTY_NODE(&info->bytes_index)) 606 return; 607 608 lockdep_assert_held(&ctl->tree_lock); 609 610 rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes); 611 rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less); 612 } 613 614 static inline void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, 615 struct btrfs_free_space *info, 616 u64 offset, u64 bytes, bool update_stat) 617 { 618 const int unit = ctl->block_group->fs_info->sectorsize; 619 unsigned long start, count, end; 620 int extent_delta = -1; 621 622 start = offset_to_bit(info->offset, unit, offset); 623 count = bytes_to_bits(bytes, unit); 624 end = start + count; 625 ASSERT(end <= BITS_PER_BITMAP); 626 627 bitmap_clear(info->bitmap, start, count); 628 629 info->bytes -= bytes; 630 if (info->max_extent_size > unit) 631 info->max_extent_size = 0; 632 633 relink_bitmap_entry(ctl, info); 634 635 if (start && test_bit(start - 1, info->bitmap)) 636 extent_delta++; 637 638 if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap)) 639 extent_delta++; 640 641 info->bitmap_extents += extent_delta; 642 if (!btrfs_free_space_trimmed(info)) { 643 ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta; 644 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes; 645 } 646 647 if (update_stat) 648 ctl->free_space -= bytes; 649 } 650 651 static void btrfs_bitmap_set_bits(struct btrfs_free_space_ctl *ctl, 652 struct btrfs_free_space *info, u64 offset, 653 u64 bytes) 654 { 655 const int unit = ctl->block_group->fs_info->sectorsize; 656 unsigned long start, count, end; 657 int extent_delta = 1; 658 659 start = offset_to_bit(info->offset, unit, offset); 660 count = bytes_to_bits(bytes, unit); 661 end = start + count; 662 ASSERT(end <= BITS_PER_BITMAP); 663 664 bitmap_set(info->bitmap, start, count); 665 666 /* 667 * We set some bytes, we have no idea what the max extent size is 668 * anymore. 669 */ 670 info->max_extent_size = 0; 671 info->bytes += bytes; 672 ctl->free_space += bytes; 673 674 relink_bitmap_entry(ctl, info); 675 676 if (start && test_bit(start - 1, info->bitmap)) 677 extent_delta--; 678 679 if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap)) 680 extent_delta--; 681 682 info->bitmap_extents += extent_delta; 683 if (!btrfs_free_space_trimmed(info)) { 684 ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta; 685 ctl->discardable_bytes[BTRFS_STAT_CURR] += bytes; 686 } 687 } 688 689 /* 690 * If we can not find suitable extent, we will use bytes to record 691 * the size of the max extent. 692 */ 693 static int search_bitmap(struct btrfs_free_space_ctl *ctl, 694 struct btrfs_free_space *bitmap_info, u64 *offset, 695 u64 *bytes, bool for_alloc) 696 { 697 const int unit = ctl->block_group->fs_info->sectorsize; 698 unsigned long found_bits = 0; 699 unsigned long max_bits = 0; 700 unsigned long bits, i; 701 unsigned long next_zero; 702 unsigned long extent_bits; 703 704 /* 705 * Skip searching the bitmap if we don't have a contiguous section that 706 * is large enough for this allocation. 707 */ 708 if (for_alloc && 709 bitmap_info->max_extent_size && 710 bitmap_info->max_extent_size < *bytes) { 711 *bytes = bitmap_info->max_extent_size; 712 return -1; 713 } 714 715 i = offset_to_bit(bitmap_info->offset, unit, 716 max_t(u64, *offset, bitmap_info->offset)); 717 bits = bytes_to_bits(*bytes, unit); 718 719 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) { 720 if (for_alloc && bits == 1) { 721 found_bits = 1; 722 break; 723 } 724 next_zero = find_next_zero_bit(bitmap_info->bitmap, 725 BITS_PER_BITMAP, i); 726 extent_bits = next_zero - i; 727 if (extent_bits >= bits) { 728 found_bits = extent_bits; 729 break; 730 } else if (extent_bits > max_bits) { 731 max_bits = extent_bits; 732 } 733 i = next_zero; 734 } 735 736 if (found_bits) { 737 *offset = (u64)(i * unit) + bitmap_info->offset; 738 *bytes = (u64)(found_bits) * unit; 739 return 0; 740 } 741 742 *bytes = (u64)(max_bits) * unit; 743 bitmap_info->max_extent_size = *bytes; 744 relink_bitmap_entry(ctl, bitmap_info); 745 return -1; 746 } 747 748 /* Cache the size of the max extent in bytes */ 749 static struct btrfs_free_space * 750 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, 751 unsigned long align, u64 *max_extent_size, bool use_bytes_index) 752 { 753 struct btrfs_free_space *entry; 754 struct rb_node *node; 755 u64 tmp; 756 u64 align_off; 757 int ret; 758 759 if (!ctl->free_space_offset.rb_node) 760 return NULL; 761 again: 762 if (use_bytes_index) { 763 node = rb_first_cached(&ctl->free_space_bytes); 764 } else { 765 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 766 0, 1); 767 if (!entry) 768 return NULL; 769 node = &entry->offset_index; 770 } 771 772 for (; node; node = rb_next(node)) { 773 if (use_bytes_index) 774 entry = rb_entry(node, struct btrfs_free_space, 775 bytes_index); 776 else 777 entry = rb_entry(node, struct btrfs_free_space, 778 offset_index); 779 780 /* 781 * If we are using the bytes index then all subsequent entries 782 * in this tree are going to be < bytes, so simply set the max 783 * extent size and exit the loop. 784 * 785 * If we're using the offset index then we need to keep going 786 * through the rest of the tree. 787 */ 788 if (entry->bytes < *bytes) { 789 *max_extent_size = max(get_max_extent_size(entry), 790 *max_extent_size); 791 if (use_bytes_index) 792 break; 793 continue; 794 } 795 796 /* make sure the space returned is big enough 797 * to match our requested alignment 798 */ 799 if (*bytes >= align) { 800 tmp = entry->offset - ctl->block_group->start + align - 1; 801 tmp = div64_u64(tmp, align); 802 tmp = tmp * align + ctl->block_group->start; 803 align_off = tmp - entry->offset; 804 } else { 805 align_off = 0; 806 tmp = entry->offset; 807 } 808 809 /* 810 * We don't break here if we're using the bytes index because we 811 * may have another entry that has the correct alignment that is 812 * the right size, so we don't want to miss that possibility. 813 * At worst this adds another loop through the logic, but if we 814 * broke here we could prematurely ENOSPC. 815 */ 816 if (entry->bytes < *bytes + align_off) { 817 *max_extent_size = max(get_max_extent_size(entry), 818 *max_extent_size); 819 continue; 820 } 821 822 if (entry->bitmap) { 823 struct rb_node *old_next = rb_next(node); 824 u64 size = *bytes; 825 826 ret = search_bitmap(ctl, entry, &tmp, &size, true); 827 if (!ret) { 828 *offset = tmp; 829 *bytes = size; 830 return entry; 831 } else { 832 *max_extent_size = 833 max(get_max_extent_size(entry), 834 *max_extent_size); 835 } 836 837 /* 838 * The bitmap may have gotten re-arranged in the space 839 * index here because the max_extent_size may have been 840 * updated. Start from the beginning again if this 841 * happened. 842 */ 843 if (use_bytes_index && old_next != rb_next(node)) 844 goto again; 845 continue; 846 } 847 848 *offset = tmp; 849 *bytes = entry->bytes - align_off; 850 return entry; 851 } 852 853 return NULL; 854 } 855 856 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl, 857 struct btrfs_free_space *info, u64 offset) 858 { 859 info->offset = offset_to_bitmap(ctl, offset); 860 info->bytes = 0; 861 info->bitmap_extents = 0; 862 INIT_LIST_HEAD(&info->list); 863 link_free_space(ctl, info); 864 ctl->total_bitmaps++; 865 recalculate_thresholds(ctl); 866 } 867 868 static void free_bitmap(struct btrfs_free_space_ctl *ctl, 869 struct btrfs_free_space *bitmap_info) 870 { 871 /* 872 * Normally when this is called, the bitmap is completely empty. However, 873 * if we are blowing up the free space cache for one reason or another 874 * via __btrfs_remove_free_space_cache(), then it may not be freed and 875 * we may leave stats on the table. 876 */ 877 if (bitmap_info->bytes && !btrfs_free_space_trimmed(bitmap_info)) { 878 ctl->discardable_extents[BTRFS_STAT_CURR] -= 879 bitmap_info->bitmap_extents; 880 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bitmap_info->bytes; 881 882 } 883 unlink_free_space(ctl, bitmap_info, true); 884 kmem_cache_free(btrfs_free_space_bitmap_cachep, bitmap_info->bitmap); 885 kmem_cache_free(btrfs_free_space_cachep, bitmap_info); 886 ctl->total_bitmaps--; 887 recalculate_thresholds(ctl); 888 } 889 890 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl, 891 struct btrfs_free_space *bitmap_info, 892 u64 *offset, u64 *bytes) 893 { 894 const int unit = ctl->block_group->fs_info->sectorsize; 895 u64 end; 896 u64 search_start, search_bytes; 897 int ret; 898 899 again: 900 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * unit) - 1; 901 902 /* 903 * We need to search for bits in this bitmap. We could only cover some 904 * of the extent in this bitmap thanks to how we add space, so we need 905 * to search for as much as it as we can and clear that amount, and then 906 * go searching for the next bit. 907 */ 908 search_start = *offset; 909 search_bytes = unit; 910 search_bytes = min(search_bytes, end - search_start + 1); 911 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes, 912 false); 913 if (ret < 0 || search_start != *offset) 914 return -EINVAL; 915 916 /* We may have found more bits than what we need */ 917 search_bytes = min(search_bytes, *bytes); 918 919 /* Cannot clear past the end of the bitmap */ 920 search_bytes = min(search_bytes, end - search_start + 1); 921 922 bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes, true); 923 *offset += search_bytes; 924 *bytes -= search_bytes; 925 926 if (*bytes) { 927 struct rb_node *next = rb_next(&bitmap_info->offset_index); 928 if (!bitmap_info->bytes) 929 free_bitmap(ctl, bitmap_info); 930 931 /* 932 * no entry after this bitmap, but we still have bytes to 933 * remove, so something has gone wrong. 934 */ 935 if (!next) 936 return -EINVAL; 937 938 bitmap_info = rb_entry(next, struct btrfs_free_space, 939 offset_index); 940 941 /* 942 * if the next entry isn't a bitmap we need to return to let the 943 * extent stuff do its work. 944 */ 945 if (!bitmap_info->bitmap) 946 return -EAGAIN; 947 948 /* 949 * Ok the next item is a bitmap, but it may not actually hold 950 * the information for the rest of this free space stuff, so 951 * look for it, and if we don't find it return so we can try 952 * everything over again. 953 */ 954 search_start = *offset; 955 search_bytes = unit; 956 ret = search_bitmap(ctl, bitmap_info, &search_start, 957 &search_bytes, false); 958 if (ret < 0 || search_start != *offset) 959 return -EAGAIN; 960 961 goto again; 962 } else if (!bitmap_info->bytes) 963 free_bitmap(ctl, bitmap_info); 964 965 return 0; 966 } 967 968 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl, 969 struct btrfs_free_space *info, u64 offset, 970 u64 bytes, enum btrfs_trim_state trim_state) 971 { 972 const int unit = ctl->block_group->fs_info->sectorsize; 973 u64 bytes_to_set = 0; 974 u64 end; 975 976 /* 977 * This is a tradeoff to make bitmap trim state minimal. We mark the 978 * whole bitmap untrimmed if at any point we add untrimmed regions. 979 */ 980 if (trim_state == BTRFS_TRIM_STATE_UNTRIMMED) { 981 if (btrfs_free_space_trimmed(info)) { 982 ctl->discardable_extents[BTRFS_STAT_CURR] += 983 info->bitmap_extents; 984 ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes; 985 } 986 info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 987 } 988 989 end = info->offset + (u64)(BITS_PER_BITMAP * unit); 990 991 bytes_to_set = min(end - offset, bytes); 992 993 btrfs_bitmap_set_bits(ctl, info, offset, bytes_to_set); 994 995 return bytes_to_set; 996 997 } 998 999 EXPORT_FOR_TESTS 1000 bool btrfs_use_bitmap(struct btrfs_free_space_ctl *ctl, 1001 struct btrfs_free_space *info) 1002 { 1003 struct btrfs_block_group *block_group = ctl->block_group; 1004 struct btrfs_fs_info *fs_info = block_group->fs_info; 1005 bool forced = false; 1006 1007 #ifdef CONFIG_BTRFS_DEBUG 1008 if (btrfs_should_fragment_free_space(block_group)) 1009 forced = true; 1010 #endif 1011 1012 /* This is a way to reclaim large regions from the bitmaps. */ 1013 if (!forced && info->bytes >= FORCE_EXTENT_THRESHOLD) 1014 return false; 1015 1016 /* 1017 * If we are below the extents threshold then we can add this as an 1018 * extent, and don't have to deal with the bitmap 1019 */ 1020 if (!forced && ctl->free_extents < ctl->extents_thresh) { 1021 /* 1022 * If this block group has some small extents we don't want to 1023 * use up all of our free slots in the cache with them, we want 1024 * to reserve them to larger extents, however if we have plenty 1025 * of cache left then go ahead and add them, no sense in adding 1026 * the overhead of a bitmap if we don't have to. 1027 */ 1028 if (info->bytes <= fs_info->sectorsize * 8) { 1029 if (ctl->free_extents * 3 <= ctl->extents_thresh) 1030 return false; 1031 } else { 1032 return false; 1033 } 1034 } 1035 1036 /* 1037 * The original block groups from mkfs can be really small, like 8 1038 * megabytes, so don't bother with a bitmap for those entries. However 1039 * some block groups can be smaller than what a bitmap would cover but 1040 * are still large enough that they could overflow the 32k memory limit, 1041 * so allow those block groups to still be allowed to have a bitmap 1042 * entry. 1043 */ 1044 if (((BITS_PER_BITMAP * fs_info->sectorsize) >> 1) > block_group->length) 1045 return false; 1046 1047 return true; 1048 } 1049 1050 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl, 1051 struct btrfs_free_space *info) 1052 { 1053 struct btrfs_free_space *bitmap_info; 1054 struct btrfs_block_group *block_group = ctl->block_group; 1055 bool added = false; 1056 u64 bytes, offset, bytes_added; 1057 enum btrfs_trim_state trim_state; 1058 int ret; 1059 1060 bytes = info->bytes; 1061 offset = info->offset; 1062 trim_state = info->trim_state; 1063 1064 if (btrfs_is_testing(block_group->fs_info)) { 1065 if (!block_group->fs_info->use_bitmap(ctl, info)) 1066 return 0; 1067 } else { 1068 if (!btrfs_use_bitmap(ctl, info)) 1069 return 0; 1070 } 1071 again: 1072 /* 1073 * Since we link bitmaps right into the cluster we need to see if we 1074 * have a cluster here, and if so and it has our bitmap we need to add 1075 * the free space to that bitmap. 1076 */ 1077 if (!list_empty(&block_group->cluster_list)) { 1078 struct btrfs_free_cluster *cluster; 1079 struct rb_node *node; 1080 struct btrfs_free_space *entry; 1081 1082 cluster = list_first_entry(&block_group->cluster_list, 1083 struct btrfs_free_cluster, block_group_list); 1084 spin_lock(&cluster->lock); 1085 node = rb_first(&cluster->root); 1086 if (!node) { 1087 spin_unlock(&cluster->lock); 1088 goto no_cluster_bitmap; 1089 } 1090 1091 entry = rb_entry(node, struct btrfs_free_space, offset_index); 1092 if (!entry->bitmap) { 1093 spin_unlock(&cluster->lock); 1094 goto no_cluster_bitmap; 1095 } 1096 1097 if (entry->offset == offset_to_bitmap(ctl, offset)) { 1098 bytes_added = add_bytes_to_bitmap(ctl, entry, offset, 1099 bytes, trim_state); 1100 bytes -= bytes_added; 1101 offset += bytes_added; 1102 } 1103 spin_unlock(&cluster->lock); 1104 if (!bytes) { 1105 ret = 1; 1106 goto out; 1107 } 1108 } 1109 1110 no_cluster_bitmap: 1111 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 1112 1, 0); 1113 if (!bitmap_info) { 1114 ASSERT(!added); 1115 goto new_bitmap; 1116 } 1117 1118 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes, 1119 trim_state); 1120 bytes -= bytes_added; 1121 offset += bytes_added; 1122 added = false; 1123 1124 if (!bytes) { 1125 ret = 1; 1126 goto out; 1127 } else 1128 goto again; 1129 1130 new_bitmap: 1131 if (info && info->bitmap) { 1132 add_new_bitmap(ctl, info, offset); 1133 added = true; 1134 info = NULL; 1135 goto again; 1136 } else { 1137 spin_unlock(&ctl->tree_lock); 1138 1139 /* no pre-allocated info, allocate a new one */ 1140 if (!info) { 1141 info = kmem_cache_zalloc(btrfs_free_space_cachep, 1142 GFP_NOFS); 1143 if (!info) { 1144 spin_lock(&ctl->tree_lock); 1145 ret = -ENOMEM; 1146 goto out; 1147 } 1148 } 1149 1150 /* allocate the bitmap */ 1151 info->bitmap = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, 1152 GFP_NOFS); 1153 info->trim_state = BTRFS_TRIM_STATE_TRIMMED; 1154 spin_lock(&ctl->tree_lock); 1155 if (!info->bitmap) { 1156 ret = -ENOMEM; 1157 goto out; 1158 } 1159 goto again; 1160 } 1161 1162 out: 1163 if (info) { 1164 if (info->bitmap) 1165 kmem_cache_free(btrfs_free_space_bitmap_cachep, 1166 info->bitmap); 1167 kmem_cache_free(btrfs_free_space_cachep, info); 1168 } 1169 1170 return ret; 1171 } 1172 1173 /* 1174 * Free space merging rules: 1175 * 1) Merge trimmed areas together 1176 * 2) Let untrimmed areas coalesce with trimmed areas 1177 * 3) Always pull neighboring regions from bitmaps 1178 * 1179 * The above rules are for when we merge free space based on btrfs_trim_state. 1180 * Rules 2 and 3 are subtle because they are suboptimal, but are done for the 1181 * same reason: to promote larger extent regions which makes life easier for 1182 * find_free_extent(). Rule 2 enables coalescing based on the common path 1183 * being returning free space from btrfs_finish_extent_commit(). So when free 1184 * space is trimmed, it will prevent aggregating trimmed new region and 1185 * untrimmed regions in the rb_tree. Rule 3 is purely to obtain larger extents 1186 * and provide find_free_extent() with the largest extents possible hoping for 1187 * the reuse path. 1188 */ 1189 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl, 1190 struct btrfs_free_space *info, bool update_stat) 1191 { 1192 struct btrfs_free_space *left_info = NULL; 1193 struct btrfs_free_space *right_info; 1194 bool merged = false; 1195 u64 offset = info->offset; 1196 u64 bytes = info->bytes; 1197 const bool is_trimmed = btrfs_free_space_trimmed(info); 1198 struct rb_node *right_prev = NULL; 1199 1200 /* 1201 * first we want to see if there is free space adjacent to the range we 1202 * are adding, if there is remove that struct and add a new one to 1203 * cover the entire range 1204 */ 1205 right_info = tree_search_offset(ctl, offset + bytes, 0, 0); 1206 if (right_info) 1207 right_prev = rb_prev(&right_info->offset_index); 1208 1209 if (right_prev) 1210 left_info = rb_entry(right_prev, struct btrfs_free_space, offset_index); 1211 else if (!right_info) 1212 left_info = tree_search_offset(ctl, offset - 1, 0, 0); 1213 1214 /* See try_merge_free_space() comment. */ 1215 if (right_info && !right_info->bitmap && 1216 (!is_trimmed || btrfs_free_space_trimmed(right_info))) { 1217 unlink_free_space(ctl, right_info, update_stat); 1218 info->bytes += right_info->bytes; 1219 kmem_cache_free(btrfs_free_space_cachep, right_info); 1220 merged = true; 1221 } 1222 1223 /* See try_merge_free_space() comment. */ 1224 if (left_info && !left_info->bitmap && 1225 left_info->offset + left_info->bytes == offset && 1226 (!is_trimmed || btrfs_free_space_trimmed(left_info))) { 1227 unlink_free_space(ctl, left_info, update_stat); 1228 info->offset = left_info->offset; 1229 info->bytes += left_info->bytes; 1230 kmem_cache_free(btrfs_free_space_cachep, left_info); 1231 merged = true; 1232 } 1233 1234 return merged; 1235 } 1236 1237 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl, 1238 struct btrfs_free_space *info, 1239 bool update_stat) 1240 { 1241 const int unit = ctl->block_group->fs_info->sectorsize; 1242 struct btrfs_free_space *bitmap; 1243 unsigned long i; 1244 unsigned long j; 1245 const u64 end = info->offset + info->bytes; 1246 const u64 bitmap_offset = offset_to_bitmap(ctl, end); 1247 u64 bytes; 1248 1249 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0); 1250 if (!bitmap) 1251 return false; 1252 1253 i = offset_to_bit(bitmap->offset, unit, end); 1254 j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i); 1255 if (j == i) 1256 return false; 1257 bytes = (j - i) * unit; 1258 info->bytes += bytes; 1259 1260 /* See try_merge_free_space() comment. */ 1261 if (!btrfs_free_space_trimmed(bitmap)) 1262 info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 1263 1264 bitmap_clear_bits(ctl, bitmap, end, bytes, update_stat); 1265 1266 if (!bitmap->bytes) 1267 free_bitmap(ctl, bitmap); 1268 1269 return true; 1270 } 1271 1272 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl, 1273 struct btrfs_free_space *info, 1274 bool update_stat) 1275 { 1276 const int unit = ctl->block_group->fs_info->sectorsize; 1277 struct btrfs_free_space *bitmap; 1278 u64 bitmap_offset; 1279 unsigned long i; 1280 unsigned long j; 1281 unsigned long prev_j; 1282 u64 bytes; 1283 1284 bitmap_offset = offset_to_bitmap(ctl, info->offset); 1285 /* If we're on a boundary, try the previous logical bitmap. */ 1286 if (bitmap_offset == info->offset) { 1287 if (info->offset == 0) 1288 return false; 1289 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1); 1290 } 1291 1292 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0); 1293 if (!bitmap) 1294 return false; 1295 1296 i = offset_to_bit(bitmap->offset, unit, info->offset) - 1; 1297 j = 0; 1298 prev_j = (unsigned long)-1; 1299 for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) { 1300 if (j > i) 1301 break; 1302 prev_j = j; 1303 } 1304 if (prev_j == i) 1305 return false; 1306 1307 if (prev_j == (unsigned long)-1) 1308 bytes = (i + 1) * unit; 1309 else 1310 bytes = (i - prev_j) * unit; 1311 1312 info->offset -= bytes; 1313 info->bytes += bytes; 1314 1315 /* See try_merge_free_space() comment. */ 1316 if (!btrfs_free_space_trimmed(bitmap)) 1317 info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 1318 1319 bitmap_clear_bits(ctl, bitmap, info->offset, bytes, update_stat); 1320 1321 if (!bitmap->bytes) 1322 free_bitmap(ctl, bitmap); 1323 1324 return true; 1325 } 1326 1327 /* 1328 * We prefer always to allocate from extent entries, both for clustered and 1329 * non-clustered allocation requests. So when attempting to add a new extent 1330 * entry, try to see if there's adjacent free space in bitmap entries, and if 1331 * there is, migrate that space from the bitmaps to the extent. 1332 * Like this we get better chances of satisfying space allocation requests 1333 * because we attempt to satisfy them based on a single cache entry, and never 1334 * on 2 or more entries - even if the entries represent a contiguous free space 1335 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry 1336 * ends). 1337 */ 1338 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl, 1339 struct btrfs_free_space *info, 1340 bool update_stat) 1341 { 1342 /* 1343 * Only work with disconnected entries, as we can change their offset, 1344 * and must be extent entries. 1345 */ 1346 ASSERT(!info->bitmap); 1347 ASSERT(RB_EMPTY_NODE(&info->offset_index)); 1348 1349 if (ctl->total_bitmaps > 0) { 1350 bool stole_end; 1351 bool stole_front = false; 1352 1353 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat); 1354 if (ctl->total_bitmaps > 0) 1355 stole_front = steal_from_bitmap_to_front(ctl, info, 1356 update_stat); 1357 1358 if (stole_end || stole_front) 1359 try_merge_free_space(ctl, info, update_stat); 1360 } 1361 } 1362 1363 static int __btrfs_add_free_space(struct btrfs_block_group *block_group, 1364 u64 offset, u64 bytes, 1365 enum btrfs_trim_state trim_state) 1366 { 1367 struct btrfs_fs_info *fs_info = block_group->fs_info; 1368 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1369 struct btrfs_free_space *info; 1370 int ret = 0; 1371 u64 filter_bytes = bytes; 1372 1373 ASSERT(!btrfs_is_zoned(fs_info)); 1374 1375 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); 1376 if (!info) 1377 return -ENOMEM; 1378 1379 info->offset = offset; 1380 info->bytes = bytes; 1381 info->trim_state = trim_state; 1382 RB_CLEAR_NODE(&info->offset_index); 1383 RB_CLEAR_NODE(&info->bytes_index); 1384 1385 spin_lock(&ctl->tree_lock); 1386 1387 if (try_merge_free_space(ctl, info, true)) 1388 goto link; 1389 1390 /* 1391 * There was no extent directly to the left or right of this new 1392 * extent then we know we're going to have to allocate a new extent, so 1393 * before we do that see if we need to drop this into a bitmap 1394 */ 1395 ret = insert_into_bitmap(ctl, info); 1396 if (ret < 0) { 1397 goto out; 1398 } else if (ret) { 1399 ret = 0; 1400 goto out; 1401 } 1402 link: 1403 /* 1404 * Only steal free space from adjacent bitmaps if we're sure we're not 1405 * going to add the new free space to existing bitmap entries - because 1406 * that would mean unnecessary work that would be reverted. Therefore 1407 * attempt to steal space from bitmaps if we're adding an extent entry. 1408 */ 1409 steal_from_bitmap(ctl, info, true); 1410 1411 filter_bytes = max(filter_bytes, info->bytes); 1412 1413 ret = link_free_space(ctl, info); 1414 if (ret) 1415 kmem_cache_free(btrfs_free_space_cachep, info); 1416 out: 1417 btrfs_discard_update_discardable(block_group); 1418 spin_unlock(&ctl->tree_lock); 1419 1420 if (ret) { 1421 btrfs_crit(fs_info, "unable to add free space :%d", ret); 1422 ASSERT(ret != -EEXIST); 1423 } 1424 1425 if (trim_state != BTRFS_TRIM_STATE_TRIMMED) { 1426 btrfs_discard_check_filter(block_group, filter_bytes); 1427 btrfs_discard_queue_work(&fs_info->discard_ctl, block_group); 1428 } 1429 1430 return ret; 1431 } 1432 1433 static int __btrfs_add_free_space_zoned(struct btrfs_block_group *block_group, 1434 u64 bytenr, u64 size, bool used) 1435 { 1436 struct btrfs_space_info *sinfo = block_group->space_info; 1437 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1438 u64 offset = bytenr - block_group->start; 1439 u64 to_free, to_unusable; 1440 int bg_reclaim_threshold = 0; 1441 bool initial; 1442 u64 reclaimable_unusable; 1443 1444 spin_lock(&block_group->lock); 1445 1446 initial = ((size == block_group->length) && (block_group->alloc_offset == 0)); 1447 WARN_ON(!initial && offset + size > block_group->zone_capacity); 1448 if (!initial) 1449 bg_reclaim_threshold = READ_ONCE(sinfo->bg_reclaim_threshold); 1450 1451 if (!used) 1452 to_free = size; 1453 else if (initial) 1454 to_free = block_group->zone_capacity; 1455 else if (offset >= block_group->alloc_offset) 1456 to_free = size; 1457 else if (offset + size <= block_group->alloc_offset) 1458 to_free = 0; 1459 else 1460 to_free = offset + size - block_group->alloc_offset; 1461 to_unusable = size - to_free; 1462 1463 spin_lock(&ctl->tree_lock); 1464 ctl->free_space += to_free; 1465 spin_unlock(&ctl->tree_lock); 1466 /* 1467 * If the block group is read-only, we should account freed space into 1468 * bytes_readonly. 1469 */ 1470 if (!block_group->ro) { 1471 block_group->zone_unusable += to_unusable; 1472 WARN_ON(block_group->zone_unusable > block_group->length); 1473 } 1474 if (!used) { 1475 block_group->alloc_offset -= size; 1476 } 1477 1478 reclaimable_unusable = block_group->zone_unusable - 1479 (block_group->length - block_group->zone_capacity); 1480 /* All the region is now unusable. Mark it as unused and reclaim */ 1481 if (block_group->zone_unusable == block_group->length) { 1482 btrfs_mark_bg_unused(block_group); 1483 } else if (bg_reclaim_threshold && 1484 reclaimable_unusable >= 1485 mult_perc(block_group->zone_capacity, bg_reclaim_threshold)) { 1486 btrfs_mark_bg_to_reclaim(block_group); 1487 } 1488 1489 spin_unlock(&block_group->lock); 1490 1491 return 0; 1492 } 1493 1494 int btrfs_add_free_space(struct btrfs_block_group *block_group, 1495 u64 bytenr, u64 size) 1496 { 1497 enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 1498 1499 if (block_group->flags & BTRFS_BLOCK_GROUP_REMAPPED) 1500 return 0; 1501 1502 if (btrfs_is_zoned(block_group->fs_info)) 1503 return __btrfs_add_free_space_zoned(block_group, bytenr, size, 1504 true); 1505 1506 if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC)) 1507 trim_state = BTRFS_TRIM_STATE_TRIMMED; 1508 1509 return __btrfs_add_free_space(block_group, bytenr, size, trim_state); 1510 } 1511 1512 int btrfs_add_free_space_unused(struct btrfs_block_group *block_group, 1513 u64 bytenr, u64 size) 1514 { 1515 if (btrfs_is_zoned(block_group->fs_info)) 1516 return __btrfs_add_free_space_zoned(block_group, bytenr, size, 1517 false); 1518 1519 return btrfs_add_free_space(block_group, bytenr, size); 1520 } 1521 1522 /* 1523 * This is a subtle distinction because when adding free space back in general, 1524 * we want it to be added as untrimmed for async. But in the case where we add 1525 * it on loading of a block group, we want to consider it trimmed. 1526 */ 1527 int btrfs_add_free_space_async_trimmed(struct btrfs_block_group *block_group, 1528 u64 bytenr, u64 size) 1529 { 1530 enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 1531 1532 if (btrfs_is_zoned(block_group->fs_info)) 1533 return __btrfs_add_free_space_zoned(block_group, bytenr, size, 1534 true); 1535 1536 if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC) || 1537 btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC)) 1538 trim_state = BTRFS_TRIM_STATE_TRIMMED; 1539 1540 return __btrfs_add_free_space(block_group, bytenr, size, trim_state); 1541 } 1542 1543 int btrfs_remove_free_space(struct btrfs_block_group *block_group, 1544 u64 offset, u64 bytes) 1545 { 1546 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1547 struct btrfs_free_space *info; 1548 int ret; 1549 bool re_search = false; 1550 1551 if (btrfs_is_zoned(block_group->fs_info)) { 1552 /* 1553 * This can happen with conventional zones when replaying log. 1554 * Since the allocation info of tree-log nodes are not recorded 1555 * to the extent-tree, calculate_alloc_pointer() failed to 1556 * advance the allocation pointer after last allocated tree log 1557 * node blocks. 1558 * 1559 * This function is called from 1560 * btrfs_pin_extent_for_log_replay() when replaying the log. 1561 * Advance the pointer not to overwrite the tree-log nodes. 1562 */ 1563 if (block_group->start + block_group->alloc_offset < 1564 offset + bytes) { 1565 block_group->alloc_offset = 1566 offset + bytes - block_group->start; 1567 } 1568 return 0; 1569 } 1570 1571 spin_lock(&ctl->tree_lock); 1572 1573 again: 1574 ret = 0; 1575 if (!bytes) 1576 goto out_lock; 1577 1578 info = tree_search_offset(ctl, offset, 0, 0); 1579 if (!info) { 1580 /* 1581 * oops didn't find an extent that matched the space we wanted 1582 * to remove, look for a bitmap instead 1583 */ 1584 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 1585 1, 0); 1586 if (!info) { 1587 /* 1588 * If we found a partial bit of our free space in a 1589 * bitmap but then couldn't find the other part this may 1590 * be a problem, so WARN about it. 1591 */ 1592 WARN_ON(re_search); 1593 goto out_lock; 1594 } 1595 } 1596 1597 re_search = false; 1598 if (!info->bitmap) { 1599 unlink_free_space(ctl, info, true); 1600 if (offset == info->offset) { 1601 u64 to_free = min(bytes, info->bytes); 1602 1603 info->bytes -= to_free; 1604 info->offset += to_free; 1605 if (info->bytes) { 1606 ret = link_free_space(ctl, info); 1607 WARN_ON(ret); 1608 } else { 1609 kmem_cache_free(btrfs_free_space_cachep, info); 1610 } 1611 1612 offset += to_free; 1613 bytes -= to_free; 1614 goto again; 1615 } else { 1616 u64 old_end = info->bytes + info->offset; 1617 1618 info->bytes = offset - info->offset; 1619 ret = link_free_space(ctl, info); 1620 WARN_ON(ret); 1621 if (ret) 1622 goto out_lock; 1623 1624 /* Not enough bytes in this entry to satisfy us */ 1625 if (old_end < offset + bytes) { 1626 bytes -= old_end - offset; 1627 offset = old_end; 1628 goto again; 1629 } else if (old_end == offset + bytes) { 1630 /* all done */ 1631 goto out_lock; 1632 } 1633 spin_unlock(&ctl->tree_lock); 1634 1635 ret = __btrfs_add_free_space(block_group, 1636 offset + bytes, 1637 old_end - (offset + bytes), 1638 info->trim_state); 1639 WARN_ON(ret); 1640 return ret; 1641 } 1642 } 1643 1644 ret = remove_from_bitmap(ctl, info, &offset, &bytes); 1645 if (ret == -EAGAIN) { 1646 re_search = true; 1647 goto again; 1648 } 1649 out_lock: 1650 btrfs_discard_update_discardable(block_group); 1651 spin_unlock(&ctl->tree_lock); 1652 1653 return ret; 1654 } 1655 1656 void btrfs_dump_free_space(struct btrfs_block_group *block_group, 1657 u64 bytes) 1658 { 1659 struct btrfs_fs_info *fs_info = block_group->fs_info; 1660 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1661 struct btrfs_free_space *info; 1662 struct rb_node *n; 1663 int count = 0; 1664 1665 /* 1666 * Zoned btrfs does not use free space tree and cluster. Just print 1667 * out the free space after the allocation offset. 1668 */ 1669 if (btrfs_is_zoned(fs_info)) { 1670 btrfs_info(fs_info, "free space %llu active %d", 1671 block_group->zone_capacity - block_group->alloc_offset, 1672 test_bit(BLOCK_GROUP_FLAG_ZONE_IS_ACTIVE, 1673 &block_group->runtime_flags)); 1674 return; 1675 } 1676 1677 spin_lock(&ctl->tree_lock); 1678 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) { 1679 info = rb_entry(n, struct btrfs_free_space, offset_index); 1680 if (info->bytes >= bytes && !block_group->ro) 1681 count++; 1682 btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s", 1683 info->offset, info->bytes, str_yes_no(info->bitmap)); 1684 } 1685 spin_unlock(&ctl->tree_lock); 1686 btrfs_info(fs_info, "block group has cluster?: %s", 1687 str_no_yes(list_empty(&block_group->cluster_list))); 1688 btrfs_info(fs_info, 1689 "%d free space entries at or bigger than %llu bytes", 1690 count, bytes); 1691 } 1692 1693 void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group, 1694 struct btrfs_free_space_ctl *ctl) 1695 { 1696 spin_lock_init(&ctl->tree_lock); 1697 ctl->block_group = block_group; 1698 ctl->free_space_bytes = RB_ROOT_CACHED; 1699 1700 /* 1701 * we only want to have 32k of ram per block group for keeping 1702 * track of free space, and if we pass 1/2 of that we want to 1703 * start converting things over to using bitmaps 1704 */ 1705 ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space); 1706 } 1707 1708 /* 1709 * for a given cluster, put all of its extents back into the free 1710 * space cache. If the block group passed doesn't match the block group 1711 * pointed to by the cluster, someone else raced in and freed the 1712 * cluster already. In that case, we just return without changing anything 1713 */ 1714 static void __btrfs_return_cluster_to_free_space( 1715 struct btrfs_block_group *block_group, 1716 struct btrfs_free_cluster *cluster) 1717 { 1718 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1719 struct rb_node *node; 1720 1721 lockdep_assert_held(&ctl->tree_lock); 1722 1723 spin_lock(&cluster->lock); 1724 if (cluster->block_group != block_group) { 1725 spin_unlock(&cluster->lock); 1726 return; 1727 } 1728 1729 cluster->block_group = NULL; 1730 cluster->window_start = 0; 1731 list_del_init(&cluster->block_group_list); 1732 1733 node = rb_first(&cluster->root); 1734 while (node) { 1735 struct btrfs_free_space *entry; 1736 1737 entry = rb_entry(node, struct btrfs_free_space, offset_index); 1738 node = rb_next(&entry->offset_index); 1739 rb_erase(&entry->offset_index, &cluster->root); 1740 RB_CLEAR_NODE(&entry->offset_index); 1741 1742 if (!entry->bitmap) { 1743 /* Merging treats extents as if they were new */ 1744 if (!btrfs_free_space_trimmed(entry)) { 1745 ctl->discardable_extents[BTRFS_STAT_CURR]--; 1746 ctl->discardable_bytes[BTRFS_STAT_CURR] -= 1747 entry->bytes; 1748 } 1749 1750 try_merge_free_space(ctl, entry, false); 1751 steal_from_bitmap(ctl, entry, false); 1752 1753 /* As we insert directly, update these statistics */ 1754 if (!btrfs_free_space_trimmed(entry)) { 1755 ctl->discardable_extents[BTRFS_STAT_CURR]++; 1756 ctl->discardable_bytes[BTRFS_STAT_CURR] += 1757 entry->bytes; 1758 } 1759 } 1760 tree_insert_offset(ctl, NULL, entry); 1761 rb_add_cached(&entry->bytes_index, &ctl->free_space_bytes, 1762 entry_less); 1763 } 1764 cluster->root = RB_ROOT; 1765 spin_unlock(&cluster->lock); 1766 btrfs_put_block_group(block_group); 1767 } 1768 1769 void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group) 1770 { 1771 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1772 struct btrfs_free_cluster *cluster; 1773 struct list_head *head; 1774 1775 spin_lock(&ctl->tree_lock); 1776 while ((head = block_group->cluster_list.next) != 1777 &block_group->cluster_list) { 1778 cluster = list_entry(head, struct btrfs_free_cluster, 1779 block_group_list); 1780 1781 WARN_ON(cluster->block_group != block_group); 1782 __btrfs_return_cluster_to_free_space(block_group, cluster); 1783 1784 cond_resched_lock(&ctl->tree_lock); 1785 } 1786 __btrfs_remove_free_space_cache(ctl); 1787 btrfs_discard_update_discardable(block_group); 1788 spin_unlock(&ctl->tree_lock); 1789 1790 } 1791 1792 /* 1793 * Walk @block_group's free space rb_tree to determine if everything is trimmed. 1794 */ 1795 bool btrfs_is_free_space_trimmed(struct btrfs_block_group *block_group) 1796 { 1797 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1798 struct btrfs_free_space *info; 1799 struct rb_node *node; 1800 bool ret = true; 1801 1802 if (block_group->flags & BTRFS_BLOCK_GROUP_REMAPPED && 1803 !test_bit(BLOCK_GROUP_FLAG_STRIPE_REMOVAL_PENDING, &block_group->runtime_flags) && 1804 block_group->identity_remap_count == 0) { 1805 return true; 1806 } 1807 1808 spin_lock(&ctl->tree_lock); 1809 node = rb_first(&ctl->free_space_offset); 1810 1811 while (node) { 1812 info = rb_entry(node, struct btrfs_free_space, offset_index); 1813 1814 if (!btrfs_free_space_trimmed(info)) { 1815 ret = false; 1816 break; 1817 } 1818 1819 node = rb_next(node); 1820 } 1821 1822 spin_unlock(&ctl->tree_lock); 1823 return ret; 1824 } 1825 1826 u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group, 1827 u64 offset, u64 bytes, u64 empty_size, 1828 u64 *max_extent_size) 1829 { 1830 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1831 struct btrfs_discard_ctl *discard_ctl = 1832 &block_group->fs_info->discard_ctl; 1833 struct btrfs_free_space *entry = NULL; 1834 u64 bytes_search = bytes + empty_size; 1835 u64 ret = 0; 1836 u64 align_gap = 0; 1837 u64 align_gap_len = 0; 1838 enum btrfs_trim_state align_gap_trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 1839 bool use_bytes_index = (offset == block_group->start); 1840 1841 ASSERT(!btrfs_is_zoned(block_group->fs_info)); 1842 1843 spin_lock(&ctl->tree_lock); 1844 entry = find_free_space(ctl, &offset, &bytes_search, 1845 block_group->full_stripe_len, max_extent_size, 1846 use_bytes_index); 1847 if (!entry) 1848 goto out; 1849 1850 ret = offset; 1851 if (entry->bitmap) { 1852 bitmap_clear_bits(ctl, entry, offset, bytes, true); 1853 1854 if (!btrfs_free_space_trimmed(entry)) 1855 atomic64_add(bytes, &discard_ctl->discard_bytes_saved); 1856 1857 if (!entry->bytes) 1858 free_bitmap(ctl, entry); 1859 } else { 1860 unlink_free_space(ctl, entry, true); 1861 align_gap_len = offset - entry->offset; 1862 align_gap = entry->offset; 1863 align_gap_trim_state = entry->trim_state; 1864 1865 if (!btrfs_free_space_trimmed(entry)) 1866 atomic64_add(bytes, &discard_ctl->discard_bytes_saved); 1867 1868 entry->offset = offset + bytes; 1869 WARN_ON(entry->bytes < bytes + align_gap_len); 1870 1871 entry->bytes -= bytes + align_gap_len; 1872 if (!entry->bytes) 1873 kmem_cache_free(btrfs_free_space_cachep, entry); 1874 else 1875 link_free_space(ctl, entry); 1876 } 1877 out: 1878 btrfs_discard_update_discardable(block_group); 1879 spin_unlock(&ctl->tree_lock); 1880 1881 if (align_gap_len) 1882 __btrfs_add_free_space(block_group, align_gap, align_gap_len, 1883 align_gap_trim_state); 1884 return ret; 1885 } 1886 1887 /* 1888 * given a cluster, put all of its extents back into the free space 1889 * cache. If a block group is passed, this function will only free 1890 * a cluster that belongs to the passed block group. 1891 * 1892 * Otherwise, it'll get a reference on the block group pointed to by the 1893 * cluster and remove the cluster from it. 1894 */ 1895 void btrfs_return_cluster_to_free_space( 1896 struct btrfs_block_group *block_group, 1897 struct btrfs_free_cluster *cluster) 1898 { 1899 struct btrfs_free_space_ctl *ctl; 1900 1901 /* first, get a safe pointer to the block group */ 1902 spin_lock(&cluster->lock); 1903 if (!block_group) { 1904 block_group = cluster->block_group; 1905 if (!block_group) { 1906 spin_unlock(&cluster->lock); 1907 return; 1908 } 1909 } else if (cluster->block_group != block_group) { 1910 /* someone else has already freed it don't redo their work */ 1911 spin_unlock(&cluster->lock); 1912 return; 1913 } 1914 btrfs_get_block_group(block_group); 1915 spin_unlock(&cluster->lock); 1916 1917 ctl = block_group->free_space_ctl; 1918 1919 /* now return any extents the cluster had on it */ 1920 spin_lock(&ctl->tree_lock); 1921 __btrfs_return_cluster_to_free_space(block_group, cluster); 1922 spin_unlock(&ctl->tree_lock); 1923 1924 btrfs_discard_queue_work(&block_group->fs_info->discard_ctl, block_group); 1925 1926 /* finally drop our ref */ 1927 btrfs_put_block_group(block_group); 1928 } 1929 1930 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group, 1931 struct btrfs_free_cluster *cluster, 1932 struct btrfs_free_space *entry, 1933 u64 bytes, u64 min_start, 1934 u64 *max_extent_size) 1935 { 1936 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1937 int ret2; 1938 u64 search_start = cluster->window_start; 1939 u64 search_bytes = bytes; 1940 u64 ret = 0; 1941 1942 search_start = min_start; 1943 search_bytes = bytes; 1944 1945 ret2 = search_bitmap(ctl, entry, &search_start, &search_bytes, true); 1946 if (ret2) { 1947 *max_extent_size = max(get_max_extent_size(entry), 1948 *max_extent_size); 1949 return 0; 1950 } 1951 1952 ret = search_start; 1953 bitmap_clear_bits(ctl, entry, ret, bytes, false); 1954 1955 return ret; 1956 } 1957 1958 /* 1959 * given a cluster, try to allocate 'bytes' from it, returns 0 1960 * if it couldn't find anything suitably large, or a logical disk offset 1961 * if things worked out 1962 */ 1963 u64 btrfs_alloc_from_cluster(struct btrfs_block_group *block_group, 1964 struct btrfs_free_cluster *cluster, u64 bytes, 1965 u64 min_start, u64 *max_extent_size) 1966 { 1967 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1968 struct btrfs_discard_ctl *discard_ctl = 1969 &block_group->fs_info->discard_ctl; 1970 struct btrfs_free_space *entry = NULL; 1971 struct rb_node *node; 1972 u64 ret = 0; 1973 1974 ASSERT(!btrfs_is_zoned(block_group->fs_info)); 1975 1976 spin_lock(&cluster->lock); 1977 if (bytes > cluster->max_size) 1978 goto out; 1979 1980 if (cluster->block_group != block_group) 1981 goto out; 1982 1983 node = rb_first(&cluster->root); 1984 if (!node) 1985 goto out; 1986 1987 entry = rb_entry(node, struct btrfs_free_space, offset_index); 1988 while (1) { 1989 if (entry->bytes < bytes) 1990 *max_extent_size = max(get_max_extent_size(entry), 1991 *max_extent_size); 1992 1993 if (entry->bytes < bytes || 1994 (!entry->bitmap && entry->offset < min_start)) { 1995 node = rb_next(&entry->offset_index); 1996 if (!node) 1997 break; 1998 entry = rb_entry(node, struct btrfs_free_space, 1999 offset_index); 2000 continue; 2001 } 2002 2003 if (entry->bitmap) { 2004 ret = btrfs_alloc_from_bitmap(block_group, 2005 cluster, entry, bytes, 2006 cluster->window_start, 2007 max_extent_size); 2008 if (ret == 0) { 2009 node = rb_next(&entry->offset_index); 2010 if (!node) 2011 break; 2012 entry = rb_entry(node, struct btrfs_free_space, 2013 offset_index); 2014 continue; 2015 } 2016 cluster->window_start += bytes; 2017 } else { 2018 ret = entry->offset; 2019 2020 entry->offset += bytes; 2021 entry->bytes -= bytes; 2022 } 2023 2024 break; 2025 } 2026 out: 2027 spin_unlock(&cluster->lock); 2028 2029 if (!ret) 2030 return 0; 2031 2032 spin_lock(&ctl->tree_lock); 2033 2034 if (!btrfs_free_space_trimmed(entry)) 2035 atomic64_add(bytes, &discard_ctl->discard_bytes_saved); 2036 2037 ctl->free_space -= bytes; 2038 if (!entry->bitmap && !btrfs_free_space_trimmed(entry)) 2039 ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes; 2040 2041 spin_lock(&cluster->lock); 2042 if (entry->bytes == 0) { 2043 rb_erase(&entry->offset_index, &cluster->root); 2044 ctl->free_extents--; 2045 if (entry->bitmap) { 2046 kmem_cache_free(btrfs_free_space_bitmap_cachep, 2047 entry->bitmap); 2048 ctl->total_bitmaps--; 2049 recalculate_thresholds(ctl); 2050 } else if (!btrfs_free_space_trimmed(entry)) { 2051 ctl->discardable_extents[BTRFS_STAT_CURR]--; 2052 } 2053 kmem_cache_free(btrfs_free_space_cachep, entry); 2054 } 2055 2056 spin_unlock(&cluster->lock); 2057 spin_unlock(&ctl->tree_lock); 2058 2059 return ret; 2060 } 2061 2062 static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group, 2063 struct btrfs_free_space *entry, 2064 struct btrfs_free_cluster *cluster, 2065 u64 offset, u64 bytes, 2066 u64 cont1_bytes, u64 min_bytes) 2067 { 2068 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2069 const int unit = block_group->fs_info->sectorsize; 2070 unsigned long next_zero; 2071 unsigned long i; 2072 unsigned long want_bits; 2073 unsigned long min_bits; 2074 unsigned long found_bits; 2075 unsigned long max_bits = 0; 2076 unsigned long start = 0; 2077 unsigned long total_found = 0; 2078 int ret; 2079 2080 lockdep_assert_held(&ctl->tree_lock); 2081 2082 i = offset_to_bit(entry->offset, unit, 2083 max_t(u64, offset, entry->offset)); 2084 want_bits = bytes_to_bits(bytes, unit); 2085 min_bits = bytes_to_bits(min_bytes, unit); 2086 2087 /* 2088 * Don't bother looking for a cluster in this bitmap if it's heavily 2089 * fragmented. 2090 */ 2091 if (entry->max_extent_size && 2092 entry->max_extent_size < cont1_bytes) 2093 return -ENOSPC; 2094 again: 2095 found_bits = 0; 2096 for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) { 2097 next_zero = find_next_zero_bit(entry->bitmap, 2098 BITS_PER_BITMAP, i); 2099 if (next_zero - i >= min_bits) { 2100 found_bits = next_zero - i; 2101 if (found_bits > max_bits) 2102 max_bits = found_bits; 2103 break; 2104 } 2105 if (next_zero - i > max_bits) 2106 max_bits = next_zero - i; 2107 i = next_zero; 2108 } 2109 2110 if (!found_bits) { 2111 entry->max_extent_size = (u64)max_bits * unit; 2112 return -ENOSPC; 2113 } 2114 2115 if (!total_found) { 2116 start = i; 2117 cluster->max_size = 0; 2118 } 2119 2120 total_found += found_bits; 2121 2122 if (cluster->max_size < found_bits * unit) 2123 cluster->max_size = found_bits * unit; 2124 2125 if (total_found < want_bits || cluster->max_size < cont1_bytes) { 2126 i = next_zero + 1; 2127 goto again; 2128 } 2129 2130 cluster->window_start = start * unit + entry->offset; 2131 rb_erase(&entry->offset_index, &ctl->free_space_offset); 2132 rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes); 2133 2134 /* 2135 * We need to know if we're currently on the normal space index when we 2136 * manipulate the bitmap so that we know we need to remove and re-insert 2137 * it into the space_index tree. Clear the bytes_index node here so the 2138 * bitmap manipulation helpers know not to mess with the space_index 2139 * until this bitmap entry is added back into the normal cache. 2140 */ 2141 RB_CLEAR_NODE(&entry->bytes_index); 2142 2143 ret = tree_insert_offset(ctl, cluster, entry); 2144 ASSERT(!ret); /* -EEXIST; Logic error */ 2145 2146 trace_btrfs_setup_cluster(block_group, cluster, total_found * unit, 1); 2147 return 0; 2148 } 2149 2150 /* 2151 * This searches the block group for just extents to fill the cluster with. 2152 * Try to find a cluster with at least bytes total bytes, at least one 2153 * extent of cont1_bytes, and other clusters of at least min_bytes. 2154 */ 2155 static noinline int 2156 setup_cluster_no_bitmap(struct btrfs_block_group *block_group, 2157 struct btrfs_free_cluster *cluster, 2158 struct list_head *bitmaps, u64 offset, u64 bytes, 2159 u64 cont1_bytes, u64 min_bytes) 2160 { 2161 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2162 struct btrfs_free_space *first = NULL; 2163 struct btrfs_free_space *entry = NULL; 2164 struct btrfs_free_space *last; 2165 struct rb_node *node; 2166 u64 window_free; 2167 u64 max_extent; 2168 u64 total_size = 0; 2169 2170 lockdep_assert_held(&ctl->tree_lock); 2171 2172 entry = tree_search_offset(ctl, offset, 0, 1); 2173 if (!entry) 2174 return -ENOSPC; 2175 2176 /* 2177 * We don't want bitmaps, so just move along until we find a normal 2178 * extent entry. 2179 */ 2180 while (entry->bitmap || entry->bytes < min_bytes) { 2181 if (entry->bitmap && list_empty(&entry->list)) 2182 list_add_tail(&entry->list, bitmaps); 2183 node = rb_next(&entry->offset_index); 2184 if (!node) 2185 return -ENOSPC; 2186 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2187 } 2188 2189 window_free = entry->bytes; 2190 max_extent = entry->bytes; 2191 first = entry; 2192 last = entry; 2193 2194 for (node = rb_next(&entry->offset_index); node; 2195 node = rb_next(&entry->offset_index)) { 2196 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2197 2198 if (entry->bitmap) { 2199 if (list_empty(&entry->list)) 2200 list_add_tail(&entry->list, bitmaps); 2201 continue; 2202 } 2203 2204 if (entry->bytes < min_bytes) 2205 continue; 2206 2207 last = entry; 2208 window_free += entry->bytes; 2209 if (entry->bytes > max_extent) 2210 max_extent = entry->bytes; 2211 } 2212 2213 if (window_free < bytes || max_extent < cont1_bytes) 2214 return -ENOSPC; 2215 2216 cluster->window_start = first->offset; 2217 2218 node = &first->offset_index; 2219 2220 /* 2221 * now we've found our entries, pull them out of the free space 2222 * cache and put them into the cluster rbtree 2223 */ 2224 do { 2225 int ret; 2226 2227 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2228 node = rb_next(&entry->offset_index); 2229 if (entry->bitmap || entry->bytes < min_bytes) 2230 continue; 2231 2232 rb_erase(&entry->offset_index, &ctl->free_space_offset); 2233 rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes); 2234 ret = tree_insert_offset(ctl, cluster, entry); 2235 total_size += entry->bytes; 2236 ASSERT(!ret); /* -EEXIST; Logic error */ 2237 } while (node && entry != last); 2238 2239 cluster->max_size = max_extent; 2240 trace_btrfs_setup_cluster(block_group, cluster, total_size, 0); 2241 return 0; 2242 } 2243 2244 /* 2245 * This specifically looks for bitmaps that may work in the cluster, we assume 2246 * that we have already failed to find extents that will work. 2247 */ 2248 static noinline int 2249 setup_cluster_bitmap(struct btrfs_block_group *block_group, 2250 struct btrfs_free_cluster *cluster, 2251 struct list_head *bitmaps, u64 offset, u64 bytes, 2252 u64 cont1_bytes, u64 min_bytes) 2253 { 2254 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2255 struct btrfs_free_space *entry = NULL; 2256 int ret = -ENOSPC; 2257 u64 bitmap_offset = offset_to_bitmap(ctl, offset); 2258 2259 if (ctl->total_bitmaps == 0) 2260 return -ENOSPC; 2261 2262 /* 2263 * The bitmap that covers offset won't be in the list unless offset 2264 * is just its start offset. 2265 */ 2266 if (!list_empty(bitmaps)) 2267 entry = list_first_entry(bitmaps, struct btrfs_free_space, list); 2268 2269 if (!entry || entry->offset != bitmap_offset) { 2270 entry = tree_search_offset(ctl, bitmap_offset, 1, 0); 2271 if (entry && list_empty(&entry->list)) 2272 list_add(&entry->list, bitmaps); 2273 } 2274 2275 list_for_each_entry(entry, bitmaps, list) { 2276 if (entry->bytes < bytes) 2277 continue; 2278 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset, 2279 bytes, cont1_bytes, min_bytes); 2280 if (!ret) 2281 return 0; 2282 } 2283 2284 /* 2285 * The bitmaps list has all the bitmaps that record free space 2286 * starting after offset, so no more search is required. 2287 */ 2288 return -ENOSPC; 2289 } 2290 2291 /* 2292 * here we try to find a cluster of blocks in a block group. The goal 2293 * is to find at least bytes+empty_size. 2294 * We might not find them all in one contiguous area. 2295 * 2296 * returns zero and sets up cluster if things worked out, otherwise 2297 * it returns -enospc 2298 */ 2299 int btrfs_find_space_cluster(struct btrfs_block_group *block_group, 2300 struct btrfs_free_cluster *cluster, 2301 u64 offset, u64 bytes, u64 empty_size) 2302 { 2303 struct btrfs_fs_info *fs_info = block_group->fs_info; 2304 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2305 struct btrfs_free_space *entry, *tmp; 2306 LIST_HEAD(bitmaps); 2307 u64 min_bytes; 2308 u64 cont1_bytes; 2309 int ret; 2310 2311 /* 2312 * Choose the minimum extent size we'll require for this 2313 * cluster. For SSD_SPREAD, don't allow any fragmentation. 2314 * For metadata, allow allocates with smaller extents. For 2315 * data, keep it dense. 2316 */ 2317 if (btrfs_test_opt(fs_info, SSD_SPREAD)) { 2318 cont1_bytes = bytes + empty_size; 2319 min_bytes = cont1_bytes; 2320 } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) { 2321 cont1_bytes = bytes; 2322 min_bytes = fs_info->sectorsize; 2323 } else { 2324 cont1_bytes = max(bytes, (bytes + empty_size) >> 2); 2325 min_bytes = fs_info->sectorsize; 2326 } 2327 2328 spin_lock(&ctl->tree_lock); 2329 2330 /* 2331 * If we know we don't have enough space to make a cluster don't even 2332 * bother doing all the work to try and find one. 2333 */ 2334 if (ctl->free_space < bytes) { 2335 spin_unlock(&ctl->tree_lock); 2336 return -ENOSPC; 2337 } 2338 2339 spin_lock(&cluster->lock); 2340 2341 /* someone already found a cluster, hooray */ 2342 if (cluster->block_group) { 2343 ret = 0; 2344 goto out; 2345 } 2346 2347 trace_btrfs_find_cluster(block_group, offset, bytes, empty_size, 2348 min_bytes); 2349 2350 ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset, 2351 bytes + empty_size, 2352 cont1_bytes, min_bytes); 2353 if (ret) 2354 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps, 2355 offset, bytes + empty_size, 2356 cont1_bytes, min_bytes); 2357 2358 /* Clear our temporary list */ 2359 list_for_each_entry_safe(entry, tmp, &bitmaps, list) 2360 list_del_init(&entry->list); 2361 2362 if (!ret) { 2363 btrfs_get_block_group(block_group); 2364 list_add_tail(&cluster->block_group_list, 2365 &block_group->cluster_list); 2366 cluster->block_group = block_group; 2367 } else { 2368 trace_btrfs_failed_cluster_setup(block_group); 2369 } 2370 out: 2371 spin_unlock(&cluster->lock); 2372 spin_unlock(&ctl->tree_lock); 2373 2374 return ret; 2375 } 2376 2377 /* 2378 * simple code to zero out a cluster 2379 */ 2380 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster) 2381 { 2382 spin_lock_init(&cluster->lock); 2383 spin_lock_init(&cluster->refill_lock); 2384 cluster->root = RB_ROOT; 2385 cluster->max_size = 0; 2386 cluster->fragmented = false; 2387 INIT_LIST_HEAD(&cluster->block_group_list); 2388 cluster->block_group = NULL; 2389 } 2390 2391 static int do_trimming(struct btrfs_block_group *block_group, 2392 u64 *total_trimmed, u64 start, u64 bytes, 2393 u64 reserved_start, u64 reserved_bytes, 2394 enum btrfs_trim_state reserved_trim_state) 2395 { 2396 struct btrfs_space_info *space_info = block_group->space_info; 2397 struct btrfs_fs_info *fs_info = block_group->fs_info; 2398 int ret; 2399 bool bg_ro; 2400 const u64 end = start + bytes; 2401 const u64 reserved_end = reserved_start + reserved_bytes; 2402 enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 2403 u64 trimmed = 0; 2404 2405 spin_lock(&space_info->lock); 2406 spin_lock(&block_group->lock); 2407 bg_ro = block_group->ro; 2408 if (!bg_ro) { 2409 block_group->reserved += reserved_bytes; 2410 spin_unlock(&block_group->lock); 2411 space_info->bytes_reserved += reserved_bytes; 2412 } else { 2413 spin_unlock(&block_group->lock); 2414 } 2415 spin_unlock(&space_info->lock); 2416 2417 ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed, false); 2418 if (!ret) { 2419 *total_trimmed += trimmed; 2420 trim_state = BTRFS_TRIM_STATE_TRIMMED; 2421 } 2422 2423 if (reserved_start < start) 2424 __btrfs_add_free_space(block_group, reserved_start, 2425 start - reserved_start, 2426 reserved_trim_state); 2427 if (end < reserved_end) 2428 __btrfs_add_free_space(block_group, end, reserved_end - end, 2429 reserved_trim_state); 2430 __btrfs_add_free_space(block_group, start, bytes, trim_state); 2431 2432 if (!bg_ro) { 2433 spin_lock(&space_info->lock); 2434 spin_lock(&block_group->lock); 2435 bg_ro = block_group->ro; 2436 block_group->reserved -= reserved_bytes; 2437 spin_unlock(&block_group->lock); 2438 2439 space_info->bytes_reserved -= reserved_bytes; 2440 if (bg_ro) 2441 space_info->bytes_readonly += reserved_bytes; 2442 spin_unlock(&space_info->lock); 2443 } 2444 2445 return ret; 2446 } 2447 2448 /* 2449 * If @async is set, then we will trim 1 region and return. 2450 */ 2451 static int trim_no_bitmap(struct btrfs_block_group *block_group, 2452 u64 *total_trimmed, u64 start, u64 end, u64 minlen, 2453 bool async) 2454 { 2455 struct btrfs_discard_ctl *discard_ctl = 2456 &block_group->fs_info->discard_ctl; 2457 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2458 struct btrfs_free_space *entry; 2459 struct rb_node *node; 2460 int ret = 0; 2461 u64 extent_start; 2462 u64 extent_bytes; 2463 enum btrfs_trim_state extent_trim_state; 2464 u64 bytes; 2465 const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size); 2466 2467 while (start < end) { 2468 spin_lock(&ctl->tree_lock); 2469 2470 if (ctl->free_space < minlen) 2471 goto out_unlock; 2472 2473 entry = tree_search_offset(ctl, start, 0, 1); 2474 if (!entry) 2475 goto out_unlock; 2476 2477 /* Skip bitmaps and if async, already trimmed entries */ 2478 while (entry->bitmap || 2479 (async && btrfs_free_space_trimmed(entry))) { 2480 node = rb_next(&entry->offset_index); 2481 if (!node) 2482 goto out_unlock; 2483 entry = rb_entry(node, struct btrfs_free_space, 2484 offset_index); 2485 } 2486 2487 if (entry->offset >= end) 2488 goto out_unlock; 2489 2490 extent_start = entry->offset; 2491 extent_bytes = entry->bytes; 2492 extent_trim_state = entry->trim_state; 2493 if (async) { 2494 start = entry->offset; 2495 bytes = entry->bytes; 2496 if (bytes < minlen) { 2497 spin_unlock(&ctl->tree_lock); 2498 goto next; 2499 } 2500 unlink_free_space(ctl, entry, true); 2501 /* 2502 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X. 2503 * If X < BTRFS_ASYNC_DISCARD_MIN_FILTER, we won't trim 2504 * X when we come back around. So trim it now. 2505 */ 2506 if (max_discard_size && 2507 bytes >= (max_discard_size + 2508 BTRFS_ASYNC_DISCARD_MIN_FILTER)) { 2509 bytes = max_discard_size; 2510 extent_bytes = max_discard_size; 2511 entry->offset += max_discard_size; 2512 entry->bytes -= max_discard_size; 2513 link_free_space(ctl, entry); 2514 } else { 2515 kmem_cache_free(btrfs_free_space_cachep, entry); 2516 } 2517 } else { 2518 start = max(start, extent_start); 2519 bytes = min(extent_start + extent_bytes, end) - start; 2520 if (bytes < minlen) { 2521 spin_unlock(&ctl->tree_lock); 2522 goto next; 2523 } 2524 2525 unlink_free_space(ctl, entry, true); 2526 kmem_cache_free(btrfs_free_space_cachep, entry); 2527 } 2528 2529 spin_unlock(&ctl->tree_lock); 2530 2531 ret = do_trimming(block_group, total_trimmed, start, bytes, 2532 extent_start, extent_bytes, extent_trim_state); 2533 if (ret) { 2534 block_group->discard_cursor = start + bytes; 2535 break; 2536 } 2537 next: 2538 start += bytes; 2539 block_group->discard_cursor = start; 2540 if (async && *total_trimmed) 2541 break; 2542 2543 if (btrfs_trim_interrupted()) { 2544 ret = -ERESTARTSYS; 2545 break; 2546 } 2547 2548 cond_resched(); 2549 } 2550 2551 return ret; 2552 2553 out_unlock: 2554 block_group->discard_cursor = btrfs_block_group_end(block_group); 2555 spin_unlock(&ctl->tree_lock); 2556 2557 return ret; 2558 } 2559 2560 void btrfs_trim_fully_remapped_block_group(struct btrfs_block_group *bg) 2561 { 2562 struct btrfs_fs_info *fs_info = bg->fs_info; 2563 struct btrfs_discard_ctl *discard_ctl = &fs_info->discard_ctl; 2564 int ret = 0; 2565 u64 bytes, trimmed; 2566 const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size); 2567 u64 end = btrfs_block_group_end(bg); 2568 2569 if (!test_bit(BLOCK_GROUP_FLAG_STRIPE_REMOVAL_PENDING, &bg->runtime_flags)) { 2570 bg->discard_cursor = end; 2571 2572 if (bg->used == 0) { 2573 spin_lock(&fs_info->unused_bgs_lock); 2574 if (!list_empty(&bg->bg_list)) { 2575 list_del_init(&bg->bg_list); 2576 btrfs_put_block_group(bg); 2577 } 2578 spin_unlock(&fs_info->unused_bgs_lock); 2579 2580 btrfs_mark_bg_unused(bg); 2581 } 2582 2583 return; 2584 } 2585 2586 bytes = end - bg->discard_cursor; 2587 2588 if (max_discard_size && 2589 bytes >= (max_discard_size + BTRFS_ASYNC_DISCARD_MIN_FILTER)) 2590 bytes = max_discard_size; 2591 2592 ret = btrfs_discard_extent(fs_info, bg->discard_cursor, bytes, &trimmed, false); 2593 if (ret) 2594 return; 2595 2596 bg->discard_cursor += trimmed; 2597 2598 if (bg->discard_cursor < end) 2599 return; 2600 2601 btrfs_complete_bg_remapping(bg); 2602 } 2603 2604 /* 2605 * If we break out of trimming a bitmap prematurely, we should reset the 2606 * trimming bit. In a rather contrived case, it's possible to race here so 2607 * reset the state to BTRFS_TRIM_STATE_UNTRIMMED. 2608 * 2609 * start = start of bitmap 2610 * end = near end of bitmap 2611 * 2612 * Thread 1: Thread 2: 2613 * trim_bitmaps(start) 2614 * trim_bitmaps(end) 2615 * end_trimming_bitmap() 2616 * reset_trimming_bitmap() 2617 */ 2618 static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset) 2619 { 2620 struct btrfs_free_space *entry; 2621 2622 spin_lock(&ctl->tree_lock); 2623 entry = tree_search_offset(ctl, offset, 1, 0); 2624 if (entry) { 2625 if (btrfs_free_space_trimmed(entry)) { 2626 ctl->discardable_extents[BTRFS_STAT_CURR] += 2627 entry->bitmap_extents; 2628 ctl->discardable_bytes[BTRFS_STAT_CURR] += entry->bytes; 2629 } 2630 entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 2631 } 2632 2633 spin_unlock(&ctl->tree_lock); 2634 } 2635 2636 static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl, 2637 struct btrfs_free_space *entry) 2638 { 2639 if (btrfs_free_space_trimming_bitmap(entry)) { 2640 entry->trim_state = BTRFS_TRIM_STATE_TRIMMED; 2641 ctl->discardable_extents[BTRFS_STAT_CURR] -= 2642 entry->bitmap_extents; 2643 ctl->discardable_bytes[BTRFS_STAT_CURR] -= entry->bytes; 2644 } 2645 } 2646 2647 /* 2648 * If @async is set, then we will trim 1 region and return. 2649 */ 2650 static int trim_bitmaps(struct btrfs_block_group *block_group, 2651 u64 *total_trimmed, u64 start, u64 end, u64 minlen, 2652 u64 maxlen, bool async) 2653 { 2654 struct btrfs_discard_ctl *discard_ctl = 2655 &block_group->fs_info->discard_ctl; 2656 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2657 struct btrfs_free_space *entry; 2658 int ret = 0; 2659 int ret2; 2660 u64 bytes; 2661 u64 offset = offset_to_bitmap(ctl, start); 2662 const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size); 2663 2664 while (offset < end) { 2665 bool next_bitmap = false; 2666 2667 spin_lock(&ctl->tree_lock); 2668 2669 if (ctl->free_space < minlen) { 2670 block_group->discard_cursor = 2671 btrfs_block_group_end(block_group); 2672 spin_unlock(&ctl->tree_lock); 2673 break; 2674 } 2675 2676 entry = tree_search_offset(ctl, offset, 1, 0); 2677 /* 2678 * Bitmaps are marked trimmed lossily now to prevent constant 2679 * discarding of the same bitmap (the reason why we are bound 2680 * by the filters). So, retrim the block group bitmaps when we 2681 * are preparing to punt to the unused_bgs list. This uses 2682 * @minlen to determine if we are in BTRFS_DISCARD_INDEX_UNUSED 2683 * which is the only discard index which sets minlen to 0. 2684 */ 2685 if (!entry || (async && minlen && start == offset && 2686 btrfs_free_space_trimmed(entry))) { 2687 spin_unlock(&ctl->tree_lock); 2688 next_bitmap = true; 2689 goto next; 2690 } 2691 2692 /* 2693 * Async discard bitmap trimming begins at by setting the start 2694 * to be key.objectid and the offset_to_bitmap() aligns to the 2695 * start of the bitmap. This lets us know we are fully 2696 * scanning the bitmap rather than only some portion of it. 2697 */ 2698 if (start == offset) 2699 entry->trim_state = BTRFS_TRIM_STATE_TRIMMING; 2700 2701 bytes = minlen; 2702 ret2 = search_bitmap(ctl, entry, &start, &bytes, false); 2703 if (ret2 || start >= end) { 2704 /* 2705 * We lossily consider a bitmap trimmed if we only skip 2706 * over regions <= BTRFS_ASYNC_DISCARD_MIN_FILTER. 2707 */ 2708 if (ret2 && minlen <= BTRFS_ASYNC_DISCARD_MIN_FILTER) 2709 end_trimming_bitmap(ctl, entry); 2710 else 2711 entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED; 2712 spin_unlock(&ctl->tree_lock); 2713 next_bitmap = true; 2714 goto next; 2715 } 2716 2717 /* 2718 * We already trimmed a region, but are using the locking above 2719 * to reset the trim_state. 2720 */ 2721 if (async && *total_trimmed) { 2722 spin_unlock(&ctl->tree_lock); 2723 return ret; 2724 } 2725 2726 bytes = min(bytes, end - start); 2727 if (bytes < minlen || (async && maxlen && bytes > maxlen)) { 2728 spin_unlock(&ctl->tree_lock); 2729 goto next; 2730 } 2731 2732 /* 2733 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X. 2734 * If X < @minlen, we won't trim X when we come back around. 2735 * So trim it now. We differ here from trimming extents as we 2736 * don't keep individual state per bit. 2737 */ 2738 if (async && 2739 max_discard_size && 2740 bytes > (max_discard_size + minlen)) 2741 bytes = max_discard_size; 2742 2743 bitmap_clear_bits(ctl, entry, start, bytes, true); 2744 if (entry->bytes == 0) 2745 free_bitmap(ctl, entry); 2746 2747 spin_unlock(&ctl->tree_lock); 2748 2749 ret = do_trimming(block_group, total_trimmed, start, bytes, 2750 start, bytes, 0); 2751 if (ret) { 2752 reset_trimming_bitmap(ctl, offset); 2753 block_group->discard_cursor = 2754 btrfs_block_group_end(block_group); 2755 break; 2756 } 2757 next: 2758 if (next_bitmap) { 2759 const int unit = block_group->fs_info->sectorsize; 2760 2761 offset += BITS_PER_BITMAP * unit; 2762 start = offset; 2763 } else { 2764 start += bytes; 2765 } 2766 block_group->discard_cursor = start; 2767 2768 if (btrfs_trim_interrupted()) { 2769 if (start != offset) 2770 reset_trimming_bitmap(ctl, offset); 2771 ret = -ERESTARTSYS; 2772 break; 2773 } 2774 2775 cond_resched(); 2776 } 2777 2778 if (offset >= end) 2779 block_group->discard_cursor = end; 2780 2781 return ret; 2782 } 2783 2784 int btrfs_trim_block_group(struct btrfs_block_group *block_group, 2785 u64 *trimmed, u64 start, u64 end, u64 minlen) 2786 { 2787 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2788 const int unit = block_group->fs_info->sectorsize; 2789 int ret; 2790 u64 rem = 0; 2791 2792 ASSERT(!btrfs_is_zoned(block_group->fs_info)); 2793 2794 *trimmed = 0; 2795 2796 spin_lock(&block_group->lock); 2797 if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) { 2798 spin_unlock(&block_group->lock); 2799 return 0; 2800 } 2801 btrfs_freeze_block_group(block_group); 2802 spin_unlock(&block_group->lock); 2803 2804 ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, false); 2805 if (ret) 2806 goto out; 2807 2808 ret = trim_bitmaps(block_group, trimmed, start, end, minlen, 0, false); 2809 div64_u64_rem(end, BITS_PER_BITMAP * unit, &rem); 2810 /* If we ended in the middle of a bitmap, reset the trimming flag */ 2811 if (rem) 2812 reset_trimming_bitmap(ctl, offset_to_bitmap(ctl, end)); 2813 out: 2814 btrfs_unfreeze_block_group(block_group); 2815 return ret; 2816 } 2817 2818 int btrfs_trim_block_group_extents(struct btrfs_block_group *block_group, 2819 u64 *trimmed, u64 start, u64 end, u64 minlen, 2820 bool async) 2821 { 2822 int ret; 2823 2824 *trimmed = 0; 2825 2826 spin_lock(&block_group->lock); 2827 if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) { 2828 spin_unlock(&block_group->lock); 2829 return 0; 2830 } 2831 btrfs_freeze_block_group(block_group); 2832 spin_unlock(&block_group->lock); 2833 2834 ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, async); 2835 btrfs_unfreeze_block_group(block_group); 2836 2837 return ret; 2838 } 2839 2840 int btrfs_trim_block_group_bitmaps(struct btrfs_block_group *block_group, 2841 u64 *trimmed, u64 start, u64 end, u64 minlen, 2842 u64 maxlen, bool async) 2843 { 2844 int ret; 2845 2846 *trimmed = 0; 2847 2848 spin_lock(&block_group->lock); 2849 if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) { 2850 spin_unlock(&block_group->lock); 2851 return 0; 2852 } 2853 btrfs_freeze_block_group(block_group); 2854 spin_unlock(&block_group->lock); 2855 2856 ret = trim_bitmaps(block_group, trimmed, start, end, minlen, maxlen, 2857 async); 2858 2859 btrfs_unfreeze_block_group(block_group); 2860 2861 return ret; 2862 } 2863 2864 bool btrfs_free_space_cache_v1_active(struct btrfs_fs_info *fs_info) 2865 { 2866 return btrfs_super_cache_generation(fs_info->super_copy); 2867 } 2868 2869 int btrfs_cleanup_free_space_cache_v1(struct btrfs_fs_info *fs_info) 2870 { 2871 struct btrfs_trans_handle *trans; 2872 struct rb_node *node; 2873 int ret; 2874 2875 btrfs_info(fs_info, "cleaning free space cache v1"); 2876 2877 /* 2878 * update_super_roots() zeroes super_copy->cache_generation while 2879 * BTRFS_FS_CLEANUP_SPACE_CACHE_V1 is set, so this needs a commit. 2880 */ 2881 trans = btrfs_start_transaction(fs_info->tree_root, 0); 2882 if (IS_ERR(trans)) 2883 return PTR_ERR(trans); 2884 2885 set_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags); 2886 for (node = rb_first_cached(&fs_info->block_group_cache_tree); node; 2887 node = rb_next(node)) { 2888 struct btrfs_block_group *block_group; 2889 2890 block_group = rb_entry(node, struct btrfs_block_group, cache_node); 2891 ret = btrfs_remove_free_space_inode(trans, NULL, block_group); 2892 if (unlikely(ret)) { 2893 btrfs_abort_transaction(trans, ret); 2894 btrfs_end_transaction(trans); 2895 goto out; 2896 } 2897 } 2898 2899 ret = btrfs_commit_transaction(trans); 2900 out: 2901 clear_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags); 2902 2903 return ret; 2904 } 2905 2906 int __init btrfs_free_space_init(void) 2907 { 2908 btrfs_free_space_cachep = KMEM_CACHE(btrfs_free_space, 0); 2909 if (!btrfs_free_space_cachep) 2910 return -ENOMEM; 2911 2912 btrfs_free_space_bitmap_cachep = kmem_cache_create("btrfs_free_space_bitmap", 2913 PAGE_SIZE, PAGE_SIZE, 2914 0, NULL); 2915 if (!btrfs_free_space_bitmap_cachep) { 2916 kmem_cache_destroy(btrfs_free_space_cachep); 2917 return -ENOMEM; 2918 } 2919 2920 return 0; 2921 } 2922 2923 void __cold btrfs_free_space_exit(void) 2924 { 2925 kmem_cache_destroy(btrfs_free_space_cachep); 2926 kmem_cache_destroy(btrfs_free_space_bitmap_cachep); 2927 } 2928 2929 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS 2930 /* 2931 * Use this if you need to make a bitmap or extent entry specifically, it 2932 * doesn't do any of the merging that add_free_space does, this acts a lot like 2933 * how the free space cache loading stuff works, so you can get really weird 2934 * configurations. 2935 */ 2936 int test_add_free_space_entry(struct btrfs_block_group *cache, 2937 u64 offset, u64 bytes, bool bitmap) 2938 { 2939 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl; 2940 struct btrfs_free_space *info = NULL, *bitmap_info; 2941 void *map = NULL; 2942 enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_TRIMMED; 2943 u64 bytes_added; 2944 int ret; 2945 2946 again: 2947 if (!info) { 2948 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); 2949 if (!info) 2950 return -ENOMEM; 2951 } 2952 2953 if (!bitmap) { 2954 spin_lock(&ctl->tree_lock); 2955 info->offset = offset; 2956 info->bytes = bytes; 2957 info->max_extent_size = 0; 2958 ret = link_free_space(ctl, info); 2959 spin_unlock(&ctl->tree_lock); 2960 if (ret) 2961 kmem_cache_free(btrfs_free_space_cachep, info); 2962 return ret; 2963 } 2964 2965 if (!map) { 2966 map = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, GFP_NOFS); 2967 if (!map) { 2968 kmem_cache_free(btrfs_free_space_cachep, info); 2969 return -ENOMEM; 2970 } 2971 } 2972 2973 spin_lock(&ctl->tree_lock); 2974 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 2975 1, 0); 2976 if (!bitmap_info) { 2977 info->bitmap = map; 2978 map = NULL; 2979 add_new_bitmap(ctl, info, offset); 2980 bitmap_info = info; 2981 info = NULL; 2982 } 2983 2984 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes, 2985 trim_state); 2986 2987 bytes -= bytes_added; 2988 offset += bytes_added; 2989 spin_unlock(&ctl->tree_lock); 2990 2991 if (bytes) 2992 goto again; 2993 2994 if (info) 2995 kmem_cache_free(btrfs_free_space_cachep, info); 2996 if (map) 2997 kmem_cache_free(btrfs_free_space_bitmap_cachep, map); 2998 return 0; 2999 } 3000 3001 /* 3002 * Checks to see if the given range is in the free space cache. This is really 3003 * just used to check the absence of space, so if there is free space in the 3004 * range at all we will return 1. 3005 */ 3006 int test_check_exists(struct btrfs_block_group *cache, 3007 u64 offset, u64 bytes) 3008 { 3009 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl; 3010 const int unit = cache->fs_info->sectorsize; 3011 struct btrfs_free_space *info; 3012 int ret = 0; 3013 3014 spin_lock(&ctl->tree_lock); 3015 info = tree_search_offset(ctl, offset, 0, 0); 3016 if (!info) { 3017 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 3018 1, 0); 3019 if (!info) 3020 goto out; 3021 } 3022 3023 have_info: 3024 if (info->bitmap) { 3025 u64 bit_off, bit_bytes; 3026 struct rb_node *n; 3027 struct btrfs_free_space *tmp; 3028 3029 bit_off = offset; 3030 bit_bytes = unit; 3031 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false); 3032 if (!ret) { 3033 if (bit_off == offset) { 3034 ret = 1; 3035 goto out; 3036 } else if (bit_off > offset && 3037 offset + bytes > bit_off) { 3038 ret = 1; 3039 goto out; 3040 } 3041 } 3042 3043 n = rb_prev(&info->offset_index); 3044 while (n) { 3045 tmp = rb_entry(n, struct btrfs_free_space, 3046 offset_index); 3047 if (tmp->offset + tmp->bytes < offset) 3048 break; 3049 if (offset + bytes < tmp->offset) { 3050 n = rb_prev(&tmp->offset_index); 3051 continue; 3052 } 3053 info = tmp; 3054 goto have_info; 3055 } 3056 3057 n = rb_next(&info->offset_index); 3058 while (n) { 3059 tmp = rb_entry(n, struct btrfs_free_space, 3060 offset_index); 3061 if (offset + bytes < tmp->offset) 3062 break; 3063 if (tmp->offset + tmp->bytes < offset) { 3064 n = rb_next(&tmp->offset_index); 3065 continue; 3066 } 3067 info = tmp; 3068 goto have_info; 3069 } 3070 3071 ret = 0; 3072 goto out; 3073 } 3074 3075 if (info->offset == offset) { 3076 ret = 1; 3077 goto out; 3078 } 3079 3080 if (offset > info->offset && offset < info->offset + info->bytes) 3081 ret = 1; 3082 out: 3083 spin_unlock(&ctl->tree_lock); 3084 return ret; 3085 } 3086 #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */ 3087