fs/btrfs/block-group.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include <linux/list_sort.h>
   4 #include "misc.h"
   5 #include "ctree.h"
   6 #include "block-group.h"
   7 #include "space-info.h"
   8 #include "disk-io.h"
   9 #include "free-space-cache.h"
  10 #include "free-space-tree.h"
  11 #include "volumes.h"
  12 #include "transaction.h"
  13 #include "ref-verify.h"
  14 #include "sysfs.h"
  15 #include "tree-log.h"
  16 #include "delalloc-space.h"
  17 #include "discard.h"
  18 #include "raid56.h"
  19 #include "zoned.h"
  20
  21 /*
  22  * Return target flags in extended format or 0 if restripe for this chunk_type
  23  * is not in progress
  24  *
  25  * Should be called with balance_lock held
  26  */
  27 static u64 get_restripe_target(struct btrfs_fs_info *fs_info, u64 flags)
  28 {
  29         struct btrfs_balance_control *bctl = fs_info->balance_ctl;
  30         u64 target = 0;
  31
  32         if (!bctl)
  33                 return 0;
  34
  35         if (flags & BTRFS_BLOCK_GROUP_DATA &&
  36             bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT) {
  37                 target = BTRFS_BLOCK_GROUP_DATA | bctl->data.target;
  38         } else if (flags & BTRFS_BLOCK_GROUP_SYSTEM &&
  39                    bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) {
  40                 target = BTRFS_BLOCK_GROUP_SYSTEM | bctl->sys.target;
  41         } else if (flags & BTRFS_BLOCK_GROUP_METADATA &&
  42                    bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT) {
  43                 target = BTRFS_BLOCK_GROUP_METADATA | bctl->meta.target;
  44         }
  45
  46         return target;
  47 }
  48
  49 /*
  50  * @flags: available profiles in extended format (see ctree.h)
  51  *
  52  * Return reduced profile in chunk format.  If profile changing is in progress
  53  * (either running or paused) picks the target profile (if it's already
  54  * available), otherwise falls back to plain reducing.
  55  */
  56 static u64 btrfs_reduce_alloc_profile(struct btrfs_fs_info *fs_info, u64 flags)
  57 {
  58         u64 num_devices = fs_info->fs_devices->rw_devices;
  59         u64 target;
  60         u64 raid_type;
  61         u64 allowed = 0;
  62
  63         /*
  64          * See if restripe for this chunk_type is in progress, if so try to
  65          * reduce to the target profile
  66          */
  67         spin_lock(&fs_info->balance_lock);
  68         target = get_restripe_target(fs_info, flags);
  69         if (target) {
  70                 spin_unlock(&fs_info->balance_lock);
  71                 return extended_to_chunk(target);
  72         }
  73         spin_unlock(&fs_info->balance_lock);
  74
  75         /* First, mask out the RAID levels which aren't possible */
  76         for (raid_type = 0; raid_type < BTRFS_NR_RAID_TYPES; raid_type++) {
  77                 if (num_devices >= btrfs_raid_array[raid_type].devs_min)
  78                         allowed |= btrfs_raid_array[raid_type].bg_flag;
  79         }
  80         allowed &= flags;
  81
  82         /* Select the highest-redundancy RAID level. */
  83         if (allowed & BTRFS_BLOCK_GROUP_RAID1C4)
  84                 allowed = BTRFS_BLOCK_GROUP_RAID1C4;
  85         else if (allowed & BTRFS_BLOCK_GROUP_RAID6)
  86                 allowed = BTRFS_BLOCK_GROUP_RAID6;
  87         else if (allowed & BTRFS_BLOCK_GROUP_RAID1C3)
  88                 allowed = BTRFS_BLOCK_GROUP_RAID1C3;
  89         else if (allowed & BTRFS_BLOCK_GROUP_RAID5)
  90                 allowed = BTRFS_BLOCK_GROUP_RAID5;
  91         else if (allowed & BTRFS_BLOCK_GROUP_RAID10)
  92                 allowed = BTRFS_BLOCK_GROUP_RAID10;
  93         else if (allowed & BTRFS_BLOCK_GROUP_RAID1)
  94                 allowed = BTRFS_BLOCK_GROUP_RAID1;
  95         else if (allowed & BTRFS_BLOCK_GROUP_DUP)
  96                 allowed = BTRFS_BLOCK_GROUP_DUP;
  97         else if (allowed & BTRFS_BLOCK_GROUP_RAID0)
  98                 allowed = BTRFS_BLOCK_GROUP_RAID0;
  99
 100         flags &= ~BTRFS_BLOCK_GROUP_PROFILE_MASK;
 101
 102         return extended_to_chunk(flags | allowed);
 103 }
 104
 105 u64 btrfs_get_alloc_profile(struct btrfs_fs_info *fs_info, u64 orig_flags)
 106 {
 107         unsigned seq;
 108         u64 flags;
 109
 110         do {
 111                 flags = orig_flags;
 112                 seq = read_seqbegin(&fs_info->profiles_lock);
 113
 114                 if (flags & BTRFS_BLOCK_GROUP_DATA)
 115                         flags |= fs_info->avail_data_alloc_bits;
 116                 else if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 117                         flags |= fs_info->avail_system_alloc_bits;
 118                 else if (flags & BTRFS_BLOCK_GROUP_METADATA)
 119                         flags |= fs_info->avail_metadata_alloc_bits;
 120         } while (read_seqretry(&fs_info->profiles_lock, seq));
 121
 122         return btrfs_reduce_alloc_profile(fs_info, flags);
 123 }
 124
 125 void btrfs_get_block_group(struct btrfs_block_group *cache)
 126 {
 127         refcount_inc(&cache->refs);
 128 }
 129
 130 void btrfs_put_block_group(struct btrfs_block_group *cache)
 131 {
 132         if (refcount_dec_and_test(&cache->refs)) {
 133                 WARN_ON(cache->pinned > 0);
 134                 /*
 135                  * If there was a failure to cleanup a log tree, very likely due
 136                  * to an IO failure on a writeback attempt of one or more of its
 137                  * extent buffers, we could not do proper (and cheap) unaccounting
 138                  * of their reserved space, so don't warn on reserved > 0 in that
 139                  * case.
 140                  */
 141                 if (!(cache->flags & BTRFS_BLOCK_GROUP_METADATA) ||
 142                     !BTRFS_FS_LOG_CLEANUP_ERROR(cache->fs_info))
 143                         WARN_ON(cache->reserved > 0);
 144
 145                 /*
 146                  * A block_group shouldn't be on the discard_list anymore.
 147                  * Remove the block_group from the discard_list to prevent us
 148                  * from causing a panic due to NULL pointer dereference.
 149                  */
 150                 if (WARN_ON(!list_empty(&cache->discard_list)))
 151                         btrfs_discard_cancel_work(&cache->fs_info->discard_ctl,
 152                                                   cache);
 153
 154                 /*
 155                  * If not empty, someone is still holding mutex of
 156                  * full_stripe_lock, which can only be released by caller.
 157                  * And it will definitely cause use-after-free when caller
 158                  * tries to release full stripe lock.
 159                  *
 160                  * No better way to resolve, but only to warn.
 161                  */
 162                 WARN_ON(!RB_EMPTY_ROOT(&cache->full_stripe_locks_root.root));
 163                 kfree(cache->free_space_ctl);
 164                 kfree(cache->physical_map);
 165                 kfree(cache);
 166         }
 167 }
 168
 169 /*
 170  * This adds the block group to the fs_info rb tree for the block group cache
 171  */
 172 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 173                                        struct btrfs_block_group *block_group)
 174 {
 175         struct rb_node **p;
 176         struct rb_node *parent = NULL;
 177         struct btrfs_block_group *cache;
 178         bool leftmost = true;
 179
 180         ASSERT(block_group->length != 0);
 181
 182         write_lock(&info->block_group_cache_lock);
 183         p = &info->block_group_cache_tree.rb_root.rb_node;
 184
 185         while (*p) {
 186                 parent = *p;
 187                 cache = rb_entry(parent, struct btrfs_block_group, cache_node);
 188                 if (block_group->start < cache->start) {
 189                         p = &(*p)->rb_left;
 190                 } else if (block_group->start > cache->start) {
 191                         p = &(*p)->rb_right;
 192                         leftmost = false;
 193                 } else {
 194                         write_unlock(&info->block_group_cache_lock);
 195                         return -EEXIST;
 196                 }
 197         }
 198
 199         rb_link_node(&block_group->cache_node, parent, p);
 200         rb_insert_color_cached(&block_group->cache_node,
 201                                &info->block_group_cache_tree, leftmost);
 202
 203         write_unlock(&info->block_group_cache_lock);
 204
 205         return 0;
 206 }
 207
 208 /*
 209  * This will return the block group at or after bytenr if contains is 0, else
 210  * it will return the block group that contains the bytenr
 211  */
 212 static struct btrfs_block_group *block_group_cache_tree_search(
 213                 struct btrfs_fs_info *info, u64 bytenr, int contains)
 214 {
 215         struct btrfs_block_group *cache, *ret = NULL;
 216         struct rb_node *n;
 217         u64 end, start;
 218
 219         read_lock(&info->block_group_cache_lock);
 220         n = info->block_group_cache_tree.rb_root.rb_node;
 221
 222         while (n) {
 223                 cache = rb_entry(n, struct btrfs_block_group, cache_node);
 224                 end = cache->start + cache->length - 1;
 225                 start = cache->start;
 226
 227                 if (bytenr < start) {
 228                         if (!contains && (!ret || start < ret->start))
 229                                 ret = cache;
 230                         n = n->rb_left;
 231                 } else if (bytenr > start) {
 232                         if (contains && bytenr <= end) {
 233                                 ret = cache;
 234                                 break;
 235                         }
 236                         n = n->rb_right;
 237                 } else {
 238                         ret = cache;
 239                         break;
 240                 }
 241         }
 242         if (ret)
 243                 btrfs_get_block_group(ret);
 244         read_unlock(&info->block_group_cache_lock);
 245
 246         return ret;
 247 }
 248
 249 /*
 250  * Return the block group that starts at or after bytenr
 251  */
 252 struct btrfs_block_group *btrfs_lookup_first_block_group(
 253                 struct btrfs_fs_info *info, u64 bytenr)
 254 {
 255         return block_group_cache_tree_search(info, bytenr, 0);
 256 }
 257
 258 /*
 259  * Return the block group that contains the given bytenr
 260  */
 261 struct btrfs_block_group *btrfs_lookup_block_group(
 262                 struct btrfs_fs_info *info, u64 bytenr)
 263 {
 264         return block_group_cache_tree_search(info, bytenr, 1);
 265 }
 266
 267 struct btrfs_block_group *btrfs_next_block_group(
 268                 struct btrfs_block_group *cache)
 269 {
 270         struct btrfs_fs_info *fs_info = cache->fs_info;
 271         struct rb_node *node;
 272
 273         read_lock(&fs_info->block_group_cache_lock);
 274
 275         /* If our block group was removed, we need a full search. */
 276         if (RB_EMPTY_NODE(&cache->cache_node)) {
 277                 const u64 next_bytenr = cache->start + cache->length;
 278
 279                 read_unlock(&fs_info->block_group_cache_lock);
 280                 btrfs_put_block_group(cache);
 281                 return btrfs_lookup_first_block_group(fs_info, next_bytenr);
 282         }
 283         node = rb_next(&cache->cache_node);
 284         btrfs_put_block_group(cache);
 285         if (node) {
 286                 cache = rb_entry(node, struct btrfs_block_group, cache_node);
 287                 btrfs_get_block_group(cache);
 288         } else
 289                 cache = NULL;
 290         read_unlock(&fs_info->block_group_cache_lock);
 291         return cache;
 292 }
 293
 294 /**
 295  * Check if we can do a NOCOW write for a given extent.
 296  *
 297  * @fs_info:       The filesystem information object.
 298  * @bytenr:        Logical start address of the extent.
 299  *
 300  * Check if we can do a NOCOW write for the given extent, and increments the
 301  * number of NOCOW writers in the block group that contains the extent, as long
 302  * as the block group exists and it's currently not in read-only mode.
 303  *
 304  * Returns: A non-NULL block group pointer if we can do a NOCOW write, the caller
 305  *          is responsible for calling btrfs_dec_nocow_writers() later.
 306  *
 307  *          Or NULL if we can not do a NOCOW write
 308  */
 309 struct btrfs_block_group *btrfs_inc_nocow_writers(struct btrfs_fs_info *fs_info,
 310                                                   u64 bytenr)
 311 {
 312         struct btrfs_block_group *bg;
 313         bool can_nocow = true;
 314
 315         bg = btrfs_lookup_block_group(fs_info, bytenr);
 316         if (!bg)
 317                 return NULL;
 318
 319         spin_lock(&bg->lock);
 320         if (bg->ro)
 321                 can_nocow = false;
 322         else
 323                 atomic_inc(&bg->nocow_writers);
 324         spin_unlock(&bg->lock);
 325
 326         if (!can_nocow) {
 327                 btrfs_put_block_group(bg);
 328                 return NULL;
 329         }
 330
 331         /* No put on block group, done by btrfs_dec_nocow_writers(). */
 332         return bg;
 333 }
 334
 335 /**
 336  * Decrement the number of NOCOW writers in a block group.
 337  *
 338  * @bg:       The block group.
 339  *
 340  * This is meant to be called after a previous call to btrfs_inc_nocow_writers(),
 341  * and on the block group returned by that call. Typically this is called after
 342  * creating an ordered extent for a NOCOW write, to prevent races with scrub and
 343  * relocation.
 344  *
 345  * After this call, the caller should not use the block group anymore. It it wants
 346  * to use it, then it should get a reference on it before calling this function.
 347  */
 348 void btrfs_dec_nocow_writers(struct btrfs_block_group *bg)
 349 {
 350         if (atomic_dec_and_test(&bg->nocow_writers))
 351                 wake_up_var(&bg->nocow_writers);
 352
 353         /* For the lookup done by a previous call to btrfs_inc_nocow_writers(). */
 354         btrfs_put_block_group(bg);
 355 }
 356
 357 void btrfs_wait_nocow_writers(struct btrfs_block_group *bg)
 358 {
 359         wait_var_event(&bg->nocow_writers, !atomic_read(&bg->nocow_writers));
 360 }
 361
 362 void btrfs_dec_block_group_reservations(struct btrfs_fs_info *fs_info,
 363                                         const u64 start)
 364 {
 365         struct btrfs_block_group *bg;
 366
 367         bg = btrfs_lookup_block_group(fs_info, start);
 368         ASSERT(bg);
 369         if (atomic_dec_and_test(&bg->reservations))
 370                 wake_up_var(&bg->reservations);
 371         btrfs_put_block_group(bg);
 372 }
 373
 374 void btrfs_wait_block_group_reservations(struct btrfs_block_group *bg)
 375 {
 376         struct btrfs_space_info *space_info = bg->space_info;
 377
 378         ASSERT(bg->ro);
 379
 380         if (!(bg->flags & BTRFS_BLOCK_GROUP_DATA))
 381                 return;
 382
 383         /*
 384          * Our block group is read only but before we set it to read only,
 385          * some task might have had allocated an extent from it already, but it
 386          * has not yet created a respective ordered extent (and added it to a
 387          * root's list of ordered extents).
 388          * Therefore wait for any task currently allocating extents, since the
 389          * block group's reservations counter is incremented while a read lock
 390          * on the groups' semaphore is held and decremented after releasing
 391          * the read access on that semaphore and creating the ordered extent.
 392          */
 393         down_write(&space_info->groups_sem);
 394         up_write(&space_info->groups_sem);
 395
 396         wait_var_event(&bg->reservations, !atomic_read(&bg->reservations));
 397 }
 398
 399 struct btrfs_caching_control *btrfs_get_caching_control(
 400                 struct btrfs_block_group *cache)
 401 {
 402         struct btrfs_caching_control *ctl;
 403
 404         spin_lock(&cache->lock);
 405         if (!cache->caching_ctl) {
 406                 spin_unlock(&cache->lock);
 407                 return NULL;
 408         }
 409
 410         ctl = cache->caching_ctl;
 411         refcount_inc(&ctl->count);
 412         spin_unlock(&cache->lock);
 413         return ctl;
 414 }
 415
 416 void btrfs_put_caching_control(struct btrfs_caching_control *ctl)
 417 {
 418         if (refcount_dec_and_test(&ctl->count))
 419                 kfree(ctl);
 420 }
 421
 422 /*
 423  * When we wait for progress in the block group caching, its because our
 424  * allocation attempt failed at least once.  So, we must sleep and let some
 425  * progress happen before we try again.
 426  *
 427  * This function will sleep at least once waiting for new free space to show
 428  * up, and then it will check the block group free space numbers for our min
 429  * num_bytes.  Another option is to have it go ahead and look in the rbtree for
 430  * a free extent of a given size, but this is a good start.
 431  *
 432  * Callers of this must check if cache->cached == BTRFS_CACHE_ERROR before using
 433  * any of the information in this block group.
 434  */
 435 void btrfs_wait_block_group_cache_progress(struct btrfs_block_group *cache,
 436                                            u64 num_bytes)
 437 {
 438         struct btrfs_caching_control *caching_ctl;
 439         int progress;
 440
 441         caching_ctl = btrfs_get_caching_control(cache);
 442         if (!caching_ctl)
 443                 return;
 444
 445         /*
 446          * We've already failed to allocate from this block group, so even if
 447          * there's enough space in the block group it isn't contiguous enough to
 448          * allow for an allocation, so wait for at least the next wakeup tick,
 449          * or for the thing to be done.
 450          */
 451         progress = atomic_read(&caching_ctl->progress);
 452
 453         wait_event(caching_ctl->wait, btrfs_block_group_done(cache) ||
 454                    (progress != atomic_read(&caching_ctl->progress) &&
 455                     (cache->free_space_ctl->free_space >= num_bytes)));
 456
 457         btrfs_put_caching_control(caching_ctl);
 458 }
 459
 460 static int btrfs_caching_ctl_wait_done(struct btrfs_block_group *cache,
 461                                        struct btrfs_caching_control *caching_ctl)
 462 {
 463         wait_event(caching_ctl->wait, btrfs_block_group_done(cache));
 464         return cache->cached == BTRFS_CACHE_ERROR ? -EIO : 0;
 465 }
 466
 467 static int btrfs_wait_block_group_cache_done(struct btrfs_block_group *cache)
 468 {
 469         struct btrfs_caching_control *caching_ctl;
 470         int ret;
 471
 472         caching_ctl = btrfs_get_caching_control(cache);
 473         if (!caching_ctl)
 474                 return (cache->cached == BTRFS_CACHE_ERROR) ? -EIO : 0;
 475         ret = btrfs_caching_ctl_wait_done(cache, caching_ctl);
 476         btrfs_put_caching_control(caching_ctl);
 477         return ret;
 478 }
 479
 480 #ifdef CONFIG_BTRFS_DEBUG
 481 static void fragment_free_space(struct btrfs_block_group *block_group)
 482 {
 483         struct btrfs_fs_info *fs_info = block_group->fs_info;
 484         u64 start = block_group->start;
 485         u64 len = block_group->length;
 486         u64 chunk = block_group->flags & BTRFS_BLOCK_GROUP_METADATA ?
 487                 fs_info->nodesize : fs_info->sectorsize;
 488         u64 step = chunk << 1;
 489
 490         while (len > chunk) {
 491                 btrfs_remove_free_space(block_group, start, chunk);
 492                 start += step;
 493                 if (len < step)
 494                         len = 0;
 495                 else
 496                         len -= step;
 497         }
 498 }
 499 #endif
 500
 501 /*
 502  * This is only called by btrfs_cache_block_group, since we could have freed
 503  * extents we need to check the pinned_extents for any extents that can't be
 504  * used yet since their free space will be released as soon as the transaction
 505  * commits.
 506  */
 507 int add_new_free_space(struct btrfs_block_group *block_group, u64 start, u64 end,
 508                        u64 *total_added_ret)
 509 {
 510         struct btrfs_fs_info *info = block_group->fs_info;
 511         u64 extent_start, extent_end, size;
 512         int ret;
 513
 514         if (total_added_ret)
 515                 *total_added_ret = 0;
 516
 517         while (start < end) {
 518                 ret = find_first_extent_bit(&info->excluded_extents, start,
 519                                             &extent_start, &extent_end,
 520                                             EXTENT_DIRTY | EXTENT_UPTODATE,
 521                                             NULL);
 522                 if (ret)
 523                         break;
 524
 525                 if (extent_start <= start) {
 526                         start = extent_end + 1;
 527                 } else if (extent_start > start && extent_start < end) {
 528                         size = extent_start - start;
 529                         ret = btrfs_add_free_space_async_trimmed(block_group,
 530                                                                  start, size);
 531                         if (ret)
 532                                 return ret;
 533                         if (total_added_ret)
 534                                 *total_added_ret += size;
 535                         start = extent_end + 1;
 536                 } else {
 537                         break;
 538                 }
 539         }
 540
 541         if (start < end) {
 542                 size = end - start;
 543                 ret = btrfs_add_free_space_async_trimmed(block_group, start,
 544                                                          size);
 545                 if (ret)
 546                         return ret;
 547                 if (total_added_ret)
 548                         *total_added_ret += size;
 549         }
 550
 551         return 0;
 552 }
 553
 554 static int load_extent_tree_free(struct btrfs_caching_control *caching_ctl)
 555 {
 556         struct btrfs_block_group *block_group = caching_ctl->block_group;
 557         struct btrfs_fs_info *fs_info = block_group->fs_info;
 558         struct btrfs_root *extent_root;
 559         struct btrfs_path *path;
 560         struct extent_buffer *leaf;
 561         struct btrfs_key key;
 562         u64 total_found = 0;
 563         u64 last = 0;
 564         u32 nritems;
 565         int ret;
 566         bool wakeup = true;
 567
 568         path = btrfs_alloc_path();
 569         if (!path)
 570                 return -ENOMEM;
 571
 572         last = max_t(u64, block_group->start, BTRFS_SUPER_INFO_OFFSET);
 573         extent_root = btrfs_extent_root(fs_info, last);
 574
 575 #ifdef CONFIG_BTRFS_DEBUG
 576         /*
 577          * If we're fragmenting we don't want to make anybody think we can
 578          * allocate from this block group until we've had a chance to fragment
 579          * the free space.
 580          */
 581         if (btrfs_should_fragment_free_space(block_group))
 582                 wakeup = false;
 583 #endif
 584         /*
 585          * We don't want to deadlock with somebody trying to allocate a new
 586          * extent for the extent root while also trying to search the extent
 587          * root to add free space.  So we skip locking and search the commit
 588          * root, since its read-only
 589          */
 590         path->skip_locking = 1;
 591         path->search_commit_root = 1;
 592         path->reada = READA_FORWARD;
 593
 594         key.objectid = last;
 595         key.offset = 0;
 596         key.type = BTRFS_EXTENT_ITEM_KEY;
 597
 598 next:
 599         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 600         if (ret < 0)
 601                 goto out;
 602
 603         leaf = path->nodes[0];
 604         nritems = btrfs_header_nritems(leaf);
 605
 606         while (1) {
 607                 if (btrfs_fs_closing(fs_info) > 1) {
 608                         last = (u64)-1;
 609                         break;
 610                 }
 611
 612                 if (path->slots[0] < nritems) {
 613                         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 614                 } else {
 615                         ret = btrfs_find_next_key(extent_root, path, &key, 0, 0);
 616                         if (ret)
 617                                 break;
 618
 619                         if (need_resched() ||
 620                             rwsem_is_contended(&fs_info->commit_root_sem)) {
 621                                 btrfs_release_path(path);
 622                                 up_read(&fs_info->commit_root_sem);
 623                                 mutex_unlock(&caching_ctl->mutex);
 624                                 cond_resched();
 625                                 mutex_lock(&caching_ctl->mutex);
 626                                 down_read(&fs_info->commit_root_sem);
 627                                 goto next;
 628                         }
 629
 630                         ret = btrfs_next_leaf(extent_root, path);
 631                         if (ret < 0)
 632                                 goto out;
 633                         if (ret)
 634                                 break;
 635                         leaf = path->nodes[0];
 636                         nritems = btrfs_header_nritems(leaf);
 637                         continue;
 638                 }
 639
 640                 if (key.objectid < last) {
 641                         key.objectid = last;
 642                         key.offset = 0;
 643                         key.type = BTRFS_EXTENT_ITEM_KEY;
 644                         btrfs_release_path(path);
 645                         goto next;
 646                 }
 647
 648                 if (key.objectid < block_group->start) {
 649                         path->slots[0]++;
 650                         continue;
 651                 }
 652
 653                 if (key.objectid >= block_group->start + block_group->length)
 654                         break;
 655
 656                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
 657                     key.type == BTRFS_METADATA_ITEM_KEY) {
 658                         u64 space_added;
 659
 660                         ret = add_new_free_space(block_group, last, key.objectid,
 661                                                  &space_added);
 662                         if (ret)
 663                                 goto out;
 664                         total_found += space_added;
 665                         if (key.type == BTRFS_METADATA_ITEM_KEY)
 666                                 last = key.objectid +
 667                                         fs_info->nodesize;
 668                         else
 669                                 last = key.objectid + key.offset;
 670
 671                         if (total_found > CACHING_CTL_WAKE_UP) {
 672                                 total_found = 0;
 673                                 if (wakeup) {
 674                                         atomic_inc(&caching_ctl->progress);
 675                                         wake_up(&caching_ctl->wait);
 676                                 }
 677                         }
 678                 }
 679                 path->slots[0]++;
 680         }
 681
 682         ret = add_new_free_space(block_group, last,
 683                                  block_group->start + block_group->length,
 684                                  NULL);
 685 out:
 686         btrfs_free_path(path);
 687         return ret;
 688 }
 689
 690 static noinline void caching_thread(struct btrfs_work *work)
 691 {
 692         struct btrfs_block_group *block_group;
 693         struct btrfs_fs_info *fs_info;
 694         struct btrfs_caching_control *caching_ctl;
 695         int ret;
 696
 697         caching_ctl = container_of(work, struct btrfs_caching_control, work);
 698         block_group = caching_ctl->block_group;
 699         fs_info = block_group->fs_info;
 700
 701         mutex_lock(&caching_ctl->mutex);
 702         down_read(&fs_info->commit_root_sem);
 703
 704         if (btrfs_test_opt(fs_info, SPACE_CACHE)) {
 705                 ret = load_free_space_cache(block_group);
 706                 if (ret == 1) {
 707                         ret = 0;
 708                         goto done;
 709                 }
 710
 711                 /*
 712                  * We failed to load the space cache, set ourselves to
 713                  * CACHE_STARTED and carry on.
 714                  */
 715                 spin_lock(&block_group->lock);
 716                 block_group->cached = BTRFS_CACHE_STARTED;
 717                 spin_unlock(&block_group->lock);
 718                 wake_up(&caching_ctl->wait);
 719         }
 720
 721         /*
 722          * If we are in the transaction that populated the free space tree we
 723          * can't actually cache from the free space tree as our commit root and
 724          * real root are the same, so we could change the contents of the blocks
 725          * while caching.  Instead do the slow caching in this case, and after
 726          * the transaction has committed we will be safe.
 727          */
 728         if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE) &&
 729             !(test_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags)))
 730                 ret = load_free_space_tree(caching_ctl);
 731         else
 732                 ret = load_extent_tree_free(caching_ctl);
 733 done:
 734         spin_lock(&block_group->lock);
 735         block_group->caching_ctl = NULL;
 736         block_group->cached = ret ? BTRFS_CACHE_ERROR : BTRFS_CACHE_FINISHED;
 737         spin_unlock(&block_group->lock);
 738
 739 #ifdef CONFIG_BTRFS_DEBUG
 740         if (btrfs_should_fragment_free_space(block_group)) {
 741                 u64 bytes_used;
 742
 743                 spin_lock(&block_group->space_info->lock);
 744                 spin_lock(&block_group->lock);
 745                 bytes_used = block_group->length - block_group->used;
 746                 block_group->space_info->bytes_used += bytes_used >> 1;
 747                 spin_unlock(&block_group->lock);
 748                 spin_unlock(&block_group->space_info->lock);
 749                 fragment_free_space(block_group);
 750         }
 751 #endif
 752
 753         up_read(&fs_info->commit_root_sem);
 754         btrfs_free_excluded_extents(block_group);
 755         mutex_unlock(&caching_ctl->mutex);
 756
 757         wake_up(&caching_ctl->wait);
 758
 759         btrfs_put_caching_control(caching_ctl);
 760         btrfs_put_block_group(block_group);
 761 }
 762
 763 int btrfs_cache_block_group(struct btrfs_block_group *cache, bool wait)
 764 {
 765         struct btrfs_fs_info *fs_info = cache->fs_info;
 766         struct btrfs_caching_control *caching_ctl = NULL;
 767         int ret = 0;
 768
 769         /* Allocator for zoned filesystems does not use the cache at all */
 770         if (btrfs_is_zoned(fs_info))
 771                 return 0;
 772
 773         caching_ctl = kzalloc(sizeof(*caching_ctl), GFP_NOFS);
 774         if (!caching_ctl)
 775                 return -ENOMEM;
 776
 777         INIT_LIST_HEAD(&caching_ctl->list);
 778         mutex_init(&caching_ctl->mutex);
 779         init_waitqueue_head(&caching_ctl->wait);
 780         caching_ctl->block_group = cache;
 781         refcount_set(&caching_ctl->count, 2);
 782         atomic_set(&caching_ctl->progress, 0);
 783         btrfs_init_work(&caching_ctl->work, caching_thread, NULL, NULL);
 784
 785         spin_lock(&cache->lock);
 786         if (cache->cached != BTRFS_CACHE_NO) {
 787                 kfree(caching_ctl);
 788
 789                 caching_ctl = cache->caching_ctl;
 790                 if (caching_ctl)
 791                         refcount_inc(&caching_ctl->count);
 792                 spin_unlock(&cache->lock);
 793                 goto out;
 794         }
 795         WARN_ON(cache->caching_ctl);
 796         cache->caching_ctl = caching_ctl;
 797         cache->cached = BTRFS_CACHE_STARTED;
 798         spin_unlock(&cache->lock);
 799
 800         write_lock(&fs_info->block_group_cache_lock);
 801         refcount_inc(&caching_ctl->count);
 802         list_add_tail(&caching_ctl->list, &fs_info->caching_block_groups);
 803         write_unlock(&fs_info->block_group_cache_lock);
 804
 805         btrfs_get_block_group(cache);
 806
 807         btrfs_queue_work(fs_info->caching_workers, &caching_ctl->work);
 808 out:
 809         if (wait && caching_ctl)
 810                 ret = btrfs_caching_ctl_wait_done(cache, caching_ctl);
 811         if (caching_ctl)
 812                 btrfs_put_caching_control(caching_ctl);
 813
 814         return ret;
 815 }
 816
 817 static void clear_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
 818 {
 819         u64 extra_flags = chunk_to_extended(flags) &
 820                                 BTRFS_EXTENDED_PROFILE_MASK;
 821
 822         write_seqlock(&fs_info->profiles_lock);
 823         if (flags & BTRFS_BLOCK_GROUP_DATA)
 824                 fs_info->avail_data_alloc_bits &= ~extra_flags;
 825         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 826                 fs_info->avail_metadata_alloc_bits &= ~extra_flags;
 827         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 828                 fs_info->avail_system_alloc_bits &= ~extra_flags;
 829         write_sequnlock(&fs_info->profiles_lock);
 830 }
 831
 832 /*
 833  * Clear incompat bits for the following feature(s):
 834  *
 835  * - RAID56 - in case there's neither RAID5 nor RAID6 profile block group
 836  *            in the whole filesystem
 837  *
 838  * - RAID1C34 - same as above for RAID1C3 and RAID1C4 block groups
 839  */
 840 static void clear_incompat_bg_bits(struct btrfs_fs_info *fs_info, u64 flags)
 841 {
 842         bool found_raid56 = false;
 843         bool found_raid1c34 = false;
 844
 845         if ((flags & BTRFS_BLOCK_GROUP_RAID56_MASK) ||
 846             (flags & BTRFS_BLOCK_GROUP_RAID1C3) ||
 847             (flags & BTRFS_BLOCK_GROUP_RAID1C4)) {
 848                 struct list_head *head = &fs_info->space_info;
 849                 struct btrfs_space_info *sinfo;
 850
 851                 list_for_each_entry_rcu(sinfo, head, list) {
 852                         down_read(&sinfo->groups_sem);
 853                         if (!list_empty(&sinfo->block_groups[BTRFS_RAID_RAID5]))
 854                                 found_raid56 = true;
 855                         if (!list_empty(&sinfo->block_groups[BTRFS_RAID_RAID6]))
 856                                 found_raid56 = true;
 857                         if (!list_empty(&sinfo->block_groups[BTRFS_RAID_RAID1C3]))
 858                                 found_raid1c34 = true;
 859                         if (!list_empty(&sinfo->block_groups[BTRFS_RAID_RAID1C4]))
 860                                 found_raid1c34 = true;
 861                         up_read(&sinfo->groups_sem);
 862                 }
 863                 if (!found_raid56)
 864                         btrfs_clear_fs_incompat(fs_info, RAID56);
 865                 if (!found_raid1c34)
 866                         btrfs_clear_fs_incompat(fs_info, RAID1C34);
 867         }
 868 }
 869
 870 static int remove_block_group_item(struct btrfs_trans_handle *trans,
 871                                    struct btrfs_path *path,
 872                                    struct btrfs_block_group *block_group)
 873 {
 874         struct btrfs_fs_info *fs_info = trans->fs_info;
 875         struct btrfs_root *root;
 876         struct btrfs_key key;
 877         int ret;
 878
 879         root = btrfs_block_group_root(fs_info);
 880         key.objectid = block_group->start;
 881         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 882         key.offset = block_group->length;
 883
 884         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 885         if (ret > 0)
 886                 ret = -ENOENT;
 887         if (ret < 0)
 888                 return ret;
 889
 890         ret = btrfs_del_item(trans, root, path);
 891         return ret;
 892 }
 893
 894 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
 895                              u64 group_start, struct extent_map *em)
 896 {
 897         struct btrfs_fs_info *fs_info = trans->fs_info;
 898         struct btrfs_path *path;
 899         struct btrfs_block_group *block_group;
 900         struct btrfs_free_cluster *cluster;
 901         struct inode *inode;
 902         struct kobject *kobj = NULL;
 903         int ret;
 904         int index;
 905         int factor;
 906         struct btrfs_caching_control *caching_ctl = NULL;
 907         bool remove_em;
 908         bool remove_rsv = false;
 909
 910         block_group = btrfs_lookup_block_group(fs_info, group_start);
 911         BUG_ON(!block_group);
 912         BUG_ON(!block_group->ro);
 913
 914         trace_btrfs_remove_block_group(block_group);
 915         /*
 916          * Free the reserved super bytes from this block group before
 917          * remove it.
 918          */
 919         btrfs_free_excluded_extents(block_group);
 920         btrfs_free_ref_tree_range(fs_info, block_group->start,
 921                                   block_group->length);
 922
 923         index = btrfs_bg_flags_to_raid_index(block_group->flags);
 924         factor = btrfs_bg_type_to_factor(block_group->flags);
 925
 926         /* make sure this block group isn't part of an allocation cluster */
 927         cluster = &fs_info->data_alloc_cluster;
 928         spin_lock(&cluster->refill_lock);
 929         btrfs_return_cluster_to_free_space(block_group, cluster);
 930         spin_unlock(&cluster->refill_lock);
 931
 932         /*
 933          * make sure this block group isn't part of a metadata
 934          * allocation cluster
 935          */
 936         cluster = &fs_info->meta_alloc_cluster;
 937         spin_lock(&cluster->refill_lock);
 938         btrfs_return_cluster_to_free_space(block_group, cluster);
 939         spin_unlock(&cluster->refill_lock);
 940
 941         btrfs_clear_treelog_bg(block_group);
 942         btrfs_clear_data_reloc_bg(block_group);
 943
 944         path = btrfs_alloc_path();
 945         if (!path) {
 946                 ret = -ENOMEM;
 947                 goto out;
 948         }
 949
 950         /*
 951          * get the inode first so any iput calls done for the io_list
 952          * aren't the final iput (no unlinks allowed now)
 953          */
 954         inode = lookup_free_space_inode(block_group, path);
 955
 956         mutex_lock(&trans->transaction->cache_write_mutex);
 957         /*
 958          * Make sure our free space cache IO is done before removing the
 959          * free space inode
 960          */
 961         spin_lock(&trans->transaction->dirty_bgs_lock);
 962         if (!list_empty(&block_group->io_list)) {
 963                 list_del_init(&block_group->io_list);
 964
 965                 WARN_ON(!IS_ERR(inode) && inode != block_group->io_ctl.inode);
 966
 967                 spin_unlock(&trans->transaction->dirty_bgs_lock);
 968                 btrfs_wait_cache_io(trans, block_group, path);
 969                 btrfs_put_block_group(block_group);
 970                 spin_lock(&trans->transaction->dirty_bgs_lock);
 971         }
 972
 973         if (!list_empty(&block_group->dirty_list)) {
 974                 list_del_init(&block_group->dirty_list);
 975                 remove_rsv = true;
 976                 btrfs_put_block_group(block_group);
 977         }
 978         spin_unlock(&trans->transaction->dirty_bgs_lock);
 979         mutex_unlock(&trans->transaction->cache_write_mutex);
 980
 981         ret = btrfs_remove_free_space_inode(trans, inode, block_group);
 982         if (ret)
 983                 goto out;
 984
 985         write_lock(&fs_info->block_group_cache_lock);
 986         rb_erase_cached(&block_group->cache_node,
 987                         &fs_info->block_group_cache_tree);
 988         RB_CLEAR_NODE(&block_group->cache_node);
 989
 990         /* Once for the block groups rbtree */
 991         btrfs_put_block_group(block_group);
 992
 993         write_unlock(&fs_info->block_group_cache_lock);
 994
 995         down_write(&block_group->space_info->groups_sem);
 996         /*
 997          * we must use list_del_init so people can check to see if they
 998          * are still on the list after taking the semaphore
 999          */
1000         list_del_init(&block_group->list);
1001         if (list_empty(&block_group->space_info->block_groups[index])) {
1002                 kobj = block_group->space_info->block_group_kobjs[index];
1003                 block_group->space_info->block_group_kobjs[index] = NULL;
1004                 clear_avail_alloc_bits(fs_info, block_group->flags);
1005         }
1006         up_write(&block_group->space_info->groups_sem);
1007         clear_incompat_bg_bits(fs_info, block_group->flags);
1008         if (kobj) {
1009                 kobject_del(kobj);
1010                 kobject_put(kobj);
1011         }
1012
1013         if (block_group->cached == BTRFS_CACHE_STARTED)
1014                 btrfs_wait_block_group_cache_done(block_group);
1015
1016         write_lock(&fs_info->block_group_cache_lock);
1017         caching_ctl = btrfs_get_caching_control(block_group);
1018         if (!caching_ctl) {
1019                 struct btrfs_caching_control *ctl;
1020
1021                 list_for_each_entry(ctl, &fs_info->caching_block_groups, list) {
1022                         if (ctl->block_group == block_group) {
1023                                 caching_ctl = ctl;
1024                                 refcount_inc(&caching_ctl->count);
1025                                 break;
1026                         }
1027                 }
1028         }
1029         if (caching_ctl)
1030                 list_del_init(&caching_ctl->list);
1031         write_unlock(&fs_info->block_group_cache_lock);
1032
1033         if (caching_ctl) {
1034                 /* Once for the caching bgs list and once for us. */
1035                 btrfs_put_caching_control(caching_ctl);
1036                 btrfs_put_caching_control(caching_ctl);
1037         }
1038
1039         spin_lock(&trans->transaction->dirty_bgs_lock);
1040         WARN_ON(!list_empty(&block_group->dirty_list));
1041         WARN_ON(!list_empty(&block_group->io_list));
1042         spin_unlock(&trans->transaction->dirty_bgs_lock);
1043
1044         btrfs_remove_free_space_cache(block_group);
1045
1046         spin_lock(&block_group->space_info->lock);
1047         list_del_init(&block_group->ro_list);
1048
1049         if (btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
1050                 WARN_ON(block_group->space_info->total_bytes
1051                         < block_group->length);
1052                 WARN_ON(block_group->space_info->bytes_readonly
1053                         < block_group->length - block_group->zone_unusable);
1054                 WARN_ON(block_group->space_info->bytes_zone_unusable
1055                         < block_group->zone_unusable);
1056                 WARN_ON(block_group->space_info->disk_total
1057                         < block_group->length * factor);
1058                 WARN_ON(test_bit(BLOCK_GROUP_FLAG_ZONE_IS_ACTIVE,
1059                                  &block_group->runtime_flags) &&
1060                         block_group->space_info->active_total_bytes
1061                         < block_group->length);
1062         }
1063         block_group->space_info->total_bytes -= block_group->length;
1064         if (test_bit(BLOCK_GROUP_FLAG_ZONE_IS_ACTIVE, &block_group->runtime_flags))
1065                 block_group->space_info->active_total_bytes -= block_group->length;
1066         block_group->space_info->bytes_readonly -=
1067                 (block_group->length - block_group->zone_unusable);
1068         block_group->space_info->bytes_zone_unusable -=
1069                 block_group->zone_unusable;
1070         block_group->space_info->disk_total -= block_group->length * factor;
1071
1072         spin_unlock(&block_group->space_info->lock);
1073
1074         /*
1075          * Remove the free space for the block group from the free space tree
1076          * and the block group's item from the extent tree before marking the
1077          * block group as removed. This is to prevent races with tasks that
1078          * freeze and unfreeze a block group, this task and another task
1079          * allocating a new block group - the unfreeze task ends up removing
1080          * the block group's extent map before the task calling this function
1081          * deletes the block group item from the extent tree, allowing for
1082          * another task to attempt to create another block group with the same
1083          * item key (and failing with -EEXIST and a transaction abort).
1084          */
1085         ret = remove_block_group_free_space(trans, block_group);
1086         if (ret)
1087                 goto out;
1088
1089         ret = remove_block_group_item(trans, path, block_group);
1090         if (ret < 0)
1091                 goto out;
1092
1093         spin_lock(&block_group->lock);
1094         set_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags);
1095
1096         /*
1097          * At this point trimming or scrub can't start on this block group,
1098          * because we removed the block group from the rbtree
1099          * fs_info->block_group_cache_tree so no one can't find it anymore and
1100          * even if someone already got this block group before we removed it
1101          * from the rbtree, they have already incremented block_group->frozen -
1102          * if they didn't, for the trimming case they won't find any free space
1103          * entries because we already removed them all when we called
1104          * btrfs_remove_free_space_cache().
1105          *
1106          * And we must not remove the extent map from the fs_info->mapping_tree
1107          * to prevent the same logical address range and physical device space
1108          * ranges from being reused for a new block group. This is needed to
1109          * avoid races with trimming and scrub.
1110          *
1111          * An fs trim operation (btrfs_trim_fs() / btrfs_ioctl_fitrim()) is
1112          * completely transactionless, so while it is trimming a range the
1113          * currently running transaction might finish and a new one start,
1114          * allowing for new block groups to be created that can reuse the same
1115          * physical device locations unless we take this special care.
1116          *
1117          * There may also be an implicit trim operation if the file system
1118          * is mounted with -odiscard. The same protections must remain
1119          * in place until the extents have been discarded completely when
1120          * the transaction commit has completed.
1121          */
1122         remove_em = (atomic_read(&block_group->frozen) == 0);
1123         spin_unlock(&block_group->lock);
1124
1125         if (remove_em) {
1126                 struct extent_map_tree *em_tree;
1127
1128                 em_tree = &fs_info->mapping_tree;
1129                 write_lock(&em_tree->lock);
1130                 remove_extent_mapping(em_tree, em);
1131                 write_unlock(&em_tree->lock);
1132                 /* once for the tree */
1133                 free_extent_map(em);
1134         }
1135
1136 out:
1137         /* Once for the lookup reference */
1138         btrfs_put_block_group(block_group);
1139         if (remove_rsv)
1140                 btrfs_delayed_refs_rsv_release(fs_info, 1);
1141         btrfs_free_path(path);
1142         return ret;
1143 }
1144
1145 struct btrfs_trans_handle *btrfs_start_trans_remove_block_group(
1146                 struct btrfs_fs_info *fs_info, const u64 chunk_offset)
1147 {
1148         struct btrfs_root *root = btrfs_block_group_root(fs_info);
1149         struct extent_map_tree *em_tree = &fs_info->mapping_tree;
1150         struct extent_map *em;
1151         struct map_lookup *map;
1152         unsigned int num_items;
1153
1154         read_lock(&em_tree->lock);
1155         em = lookup_extent_mapping(em_tree, chunk_offset, 1);
1156         read_unlock(&em_tree->lock);
1157         ASSERT(em && em->start == chunk_offset);
1158
1159         /*
1160          * We need to reserve 3 + N units from the metadata space info in order
1161          * to remove a block group (done at btrfs_remove_chunk() and at
1162          * btrfs_remove_block_group()), which are used for:
1163          *
1164          * 1 unit for adding the free space inode's orphan (located in the tree
1165          * of tree roots).
1166          * 1 unit for deleting the block group item (located in the extent
1167          * tree).
1168          * 1 unit for deleting the free space item (located in tree of tree
1169          * roots).
1170          * N units for deleting N device extent items corresponding to each
1171          * stripe (located in the device tree).
1172          *
1173          * In order to remove a block group we also need to reserve units in the
1174          * system space info in order to update the chunk tree (update one or
1175          * more device items and remove one chunk item), but this is done at
1176          * btrfs_remove_chunk() through a call to check_system_chunk().
1177          */
1178         map = em->map_lookup;
1179         num_items = 3 + map->num_stripes;
1180         free_extent_map(em);
1181
1182         return btrfs_start_transaction_fallback_global_rsv(root, num_items);
1183 }
1184
1185 /*
1186  * Mark block group @cache read-only, so later write won't happen to block
1187  * group @cache.
1188  *
1189  * If @force is not set, this function will only mark the block group readonly
1190  * if we have enough free space (1M) in other metadata/system block groups.
1191  * If @force is not set, this function will mark the block group readonly
1192  * without checking free space.
1193  *
1194  * NOTE: This function doesn't care if other block groups can contain all the
1195  * data in this block group. That check should be done by relocation routine,
1196  * not this function.
1197  */
1198 static int inc_block_group_ro(struct btrfs_block_group *cache, int force)
1199 {
1200         struct btrfs_space_info *sinfo = cache->space_info;
1201         u64 num_bytes;
1202         int ret = -ENOSPC;
1203
1204         spin_lock(&sinfo->lock);
1205         spin_lock(&cache->lock);
1206
1207         if (cache->swap_extents) {
1208                 ret = -ETXTBSY;
1209                 goto out;
1210         }
1211
1212         if (cache->ro) {
1213                 cache->ro++;
1214                 ret = 0;
1215                 goto out;
1216         }
1217
1218         num_bytes = cache->length - cache->reserved - cache->pinned -
1219                     cache->bytes_super - cache->zone_unusable - cache->used;
1220
1221         /*
1222          * Data never overcommits, even in mixed mode, so do just the straight
1223          * check of left over space in how much we have allocated.
1224          */
1225         if (force) {
1226                 ret = 0;
1227         } else if (sinfo->flags & BTRFS_BLOCK_GROUP_DATA) {
1228                 u64 sinfo_used = btrfs_space_info_used(sinfo, true);
1229
1230                 /*
1231                  * Here we make sure if we mark this bg RO, we still have enough
1232                  * free space as buffer.
1233                  */
1234                 if (sinfo_used + num_bytes <= sinfo->total_bytes)
1235                         ret = 0;
1236         } else {
1237                 /*
1238                  * We overcommit metadata, so we need to do the
1239                  * btrfs_can_overcommit check here, and we need to pass in
1240                  * BTRFS_RESERVE_NO_FLUSH to give ourselves the most amount of
1241                  * leeway to allow us to mark this block group as read only.
1242                  */
1243                 if (btrfs_can_overcommit(cache->fs_info, sinfo, num_bytes,
1244                                          BTRFS_RESERVE_NO_FLUSH))
1245                         ret = 0;
1246         }
1247
1248         if (!ret) {
1249                 sinfo->bytes_readonly += num_bytes;
1250                 if (btrfs_is_zoned(cache->fs_info)) {
1251                         /* Migrate zone_unusable bytes to readonly */
1252                         sinfo->bytes_readonly += cache->zone_unusable;
1253                         sinfo->bytes_zone_unusable -= cache->zone_unusable;
1254                         cache->zone_unusable = 0;
1255                 }
1256                 cache->ro++;
1257                 list_add_tail(&cache->ro_list, &sinfo->ro_bgs);
1258         }
1259 out:
1260         spin_unlock(&cache->lock);
1261         spin_unlock(&sinfo->lock);
1262         if (ret == -ENOSPC && btrfs_test_opt(cache->fs_info, ENOSPC_DEBUG)) {
1263                 btrfs_info(cache->fs_info,
1264                         "unable to make block group %llu ro", cache->start);
1265                 btrfs_dump_space_info(cache->fs_info, cache->space_info, 0, 0);
1266         }
1267         return ret;
1268 }
1269
1270 static bool clean_pinned_extents(struct btrfs_trans_handle *trans,
1271                                  struct btrfs_block_group *bg)
1272 {
1273         struct btrfs_fs_info *fs_info = bg->fs_info;
1274         struct btrfs_transaction *prev_trans = NULL;
1275         const u64 start = bg->start;
1276         const u64 end = start + bg->length - 1;
1277         int ret;
1278
1279         spin_lock(&fs_info->trans_lock);
1280         if (trans->transaction->list.prev != &fs_info->trans_list) {
1281                 prev_trans = list_last_entry(&trans->transaction->list,
1282                                              struct btrfs_transaction, list);
1283                 refcount_inc(&prev_trans->use_count);
1284         }
1285         spin_unlock(&fs_info->trans_lock);
1286
1287         /*
1288          * Hold the unused_bg_unpin_mutex lock to avoid racing with
1289          * btrfs_finish_extent_commit(). If we are at transaction N, another
1290          * task might be running finish_extent_commit() for the previous
1291          * transaction N - 1, and have seen a range belonging to the block
1292          * group in pinned_extents before we were able to clear the whole block
1293          * group range from pinned_extents. This means that task can lookup for
1294          * the block group after we unpinned it from pinned_extents and removed
1295          * it, leading to a BUG_ON() at unpin_extent_range().
1296          */
1297         mutex_lock(&fs_info->unused_bg_unpin_mutex);
1298         if (prev_trans) {
1299                 ret = clear_extent_bits(&prev_trans->pinned_extents, start, end,
1300                                         EXTENT_DIRTY);
1301                 if (ret)
1302                         goto out;
1303         }
1304
1305         ret = clear_extent_bits(&trans->transaction->pinned_extents, start, end,
1306                                 EXTENT_DIRTY);
1307 out:
1308         mutex_unlock(&fs_info->unused_bg_unpin_mutex);
1309         if (prev_trans)
1310                 btrfs_put_transaction(prev_trans);
1311
1312         return ret == 0;
1313 }
1314
1315 /*
1316  * Process the unused_bgs list and remove any that don't have any allocated
1317  * space inside of them.
1318  */
1319 void btrfs_delete_unused_bgs(struct btrfs_fs_info *fs_info)
1320 {
1321         struct btrfs_block_group *block_group;
1322         struct btrfs_space_info *space_info;
1323         struct btrfs_trans_handle *trans;
1324         const bool async_trim_enabled = btrfs_test_opt(fs_info, DISCARD_ASYNC);
1325         int ret = 0;
1326
1327         if (!test_bit(BTRFS_FS_OPEN, &fs_info->flags))
1328                 return;
1329
1330         if (btrfs_fs_closing(fs_info))
1331                 return;
1332
1333         /*
1334          * Long running balances can keep us blocked here for eternity, so
1335          * simply skip deletion if we're unable to get the mutex.
1336          */
1337         if (!mutex_trylock(&fs_info->reclaim_bgs_lock))
1338                 return;
1339
1340         spin_lock(&fs_info->unused_bgs_lock);
1341         while (!list_empty(&fs_info->unused_bgs)) {
1342                 int trimming;
1343
1344                 block_group = list_first_entry(&fs_info->unused_bgs,
1345                                                struct btrfs_block_group,
1346                                                bg_list);
1347                 list_del_init(&block_group->bg_list);
1348
1349                 space_info = block_group->space_info;
1350
1351                 if (ret || btrfs_mixed_space_info(space_info)) {
1352                         btrfs_put_block_group(block_group);
1353                         continue;
1354                 }
1355                 spin_unlock(&fs_info->unused_bgs_lock);
1356
1357                 btrfs_discard_cancel_work(&fs_info->discard_ctl, block_group);
1358
1359                 /* Don't want to race with allocators so take the groups_sem */
1360                 down_write(&space_info->groups_sem);
1361
1362                 /*
1363                  * Async discard moves the final block group discard to be prior
1364                  * to the unused_bgs code path.  Therefore, if it's not fully
1365                  * trimmed, punt it back to the async discard lists.
1366                  */
1367                 if (btrfs_test_opt(fs_info, DISCARD_ASYNC) &&
1368                     !btrfs_is_free_space_trimmed(block_group)) {
1369                         trace_btrfs_skip_unused_block_group(block_group);
1370                         up_write(&space_info->groups_sem);
1371                         /* Requeue if we failed because of async discard */
1372                         btrfs_discard_queue_work(&fs_info->discard_ctl,
1373                                                  block_group);
1374                         goto next;
1375                 }
1376
1377                 spin_lock(&block_group->lock);
1378                 if (block_group->reserved || block_group->pinned ||
1379                     block_group->used || block_group->ro ||
1380                     list_is_singular(&block_group->list)) {
1381                         /*
1382                          * We want to bail if we made new allocations or have
1383                          * outstanding allocations in this block group.  We do
1384                          * the ro check in case balance is currently acting on
1385                          * this block group.
1386                          */
1387                         trace_btrfs_skip_unused_block_group(block_group);
1388                         spin_unlock(&block_group->lock);
1389                         up_write(&space_info->groups_sem);
1390                         goto next;
1391                 }
1392                 spin_unlock(&block_group->lock);
1393
1394                 /* We don't want to force the issue, only flip if it's ok. */
1395                 ret = inc_block_group_ro(block_group, 0);
1396                 up_write(&space_info->groups_sem);
1397                 if (ret < 0) {
1398                         ret = 0;
1399                         goto next;
1400                 }
1401
1402                 ret = btrfs_zone_finish(block_group);
1403                 if (ret < 0) {
1404                         btrfs_dec_block_group_ro(block_group);
1405                         if (ret == -EAGAIN)
1406                                 ret = 0;
1407                         goto next;
1408                 }
1409
1410                 /*
1411                  * Want to do this before we do anything else so we can recover
1412                  * properly if we fail to join the transaction.
1413                  */
1414                 trans = btrfs_start_trans_remove_block_group(fs_info,
1415                                                      block_group->start);
1416                 if (IS_ERR(trans)) {
1417                         btrfs_dec_block_group_ro(block_group);
1418                         ret = PTR_ERR(trans);
1419                         goto next;
1420                 }
1421
1422                 /*
1423                  * We could have pending pinned extents for this block group,
1424                  * just delete them, we don't care about them anymore.
1425                  */
1426                 if (!clean_pinned_extents(trans, block_group)) {
1427                         btrfs_dec_block_group_ro(block_group);
1428                         goto end_trans;
1429                 }
1430
1431                 /*
1432                  * At this point, the block_group is read only and should fail
1433                  * new allocations.  However, btrfs_finish_extent_commit() can
1434                  * cause this block_group to be placed back on the discard
1435                  * lists because now the block_group isn't fully discarded.
1436                  * Bail here and try again later after discarding everything.
1437                  */
1438                 spin_lock(&fs_info->discard_ctl.lock);
1439                 if (!list_empty(&block_group->discard_list)) {
1440                         spin_unlock(&fs_info->discard_ctl.lock);
1441                         btrfs_dec_block_group_ro(block_group);
1442                         btrfs_discard_queue_work(&fs_info->discard_ctl,
1443                                                  block_group);
1444                         goto end_trans;
1445                 }
1446                 spin_unlock(&fs_info->discard_ctl.lock);
1447
1448                 /* Reset pinned so btrfs_put_block_group doesn't complain */
1449                 spin_lock(&space_info->lock);
1450                 spin_lock(&block_group->lock);
1451
1452                 btrfs_space_info_update_bytes_pinned(fs_info, space_info,
1453                                                      -block_group->pinned);
1454                 space_info->bytes_readonly += block_group->pinned;
1455                 block_group->pinned = 0;
1456
1457                 spin_unlock(&block_group->lock);
1458                 spin_unlock(&space_info->lock);
1459
1460                 /*
1461                  * The normal path here is an unused block group is passed here,
1462                  * then trimming is handled in the transaction commit path.
1463                  * Async discard interposes before this to do the trimming
1464                  * before coming down the unused block group path as trimming
1465                  * will no longer be done later in the transaction commit path.
1466                  */
1467                 if (!async_trim_enabled && btrfs_test_opt(fs_info, DISCARD_ASYNC))
1468                         goto flip_async;
1469
1470                 /*
1471                  * DISCARD can flip during remount. On zoned filesystems, we
1472                  * need to reset sequential-required zones.
1473                  */
1474                 trimming = btrfs_test_opt(fs_info, DISCARD_SYNC) ||
1475                                 btrfs_is_zoned(fs_info);
1476
1477                 /* Implicit trim during transaction commit. */
1478                 if (trimming)
1479                         btrfs_freeze_block_group(block_group);
1480
1481                 /*
1482                  * Btrfs_remove_chunk will abort the transaction if things go
1483                  * horribly wrong.
1484                  */
1485                 ret = btrfs_remove_chunk(trans, block_group->start);
1486
1487                 if (ret) {
1488                         if (trimming)
1489                                 btrfs_unfreeze_block_group(block_group);
1490                         goto end_trans;
1491                 }
1492
1493                 /*
1494                  * If we're not mounted with -odiscard, we can just forget
1495                  * about this block group. Otherwise we'll need to wait
1496                  * until transaction commit to do the actual discard.
1497                  */
1498                 if (trimming) {
1499                         spin_lock(&fs_info->unused_bgs_lock);
1500                         /*
1501                          * A concurrent scrub might have added us to the list
1502                          * fs_info->unused_bgs, so use a list_move operation
1503                          * to add the block group to the deleted_bgs list.
1504                          */
1505                         list_move(&block_group->bg_list,
1506                                   &trans->transaction->deleted_bgs);
1507                         spin_unlock(&fs_info->unused_bgs_lock);
1508                         btrfs_get_block_group(block_group);
1509                 }
1510 end_trans:
1511                 btrfs_end_transaction(trans);
1512 next:
1513                 btrfs_put_block_group(block_group);
1514                 spin_lock(&fs_info->unused_bgs_lock);
1515         }
1516         spin_unlock(&fs_info->unused_bgs_lock);
1517         mutex_unlock(&fs_info->reclaim_bgs_lock);
1518         return;
1519
1520 flip_async:
1521         btrfs_end_transaction(trans);
1522         mutex_unlock(&fs_info->reclaim_bgs_lock);
1523         btrfs_put_block_group(block_group);
1524         btrfs_discard_punt_unused_bgs_list(fs_info);
1525 }
1526
1527 void btrfs_mark_bg_unused(struct btrfs_block_group *bg)
1528 {
1529         struct btrfs_fs_info *fs_info = bg->fs_info;
1530
1531         spin_lock(&fs_info->unused_bgs_lock);
1532         if (list_empty(&bg->bg_list)) {
1533                 btrfs_get_block_group(bg);
1534                 trace_btrfs_add_unused_block_group(bg);
1535                 list_add_tail(&bg->bg_list, &fs_info->unused_bgs);
1536         } else if (!test_bit(BLOCK_GROUP_FLAG_NEW, &bg->runtime_flags)) {
1537                 /* Pull out the block group from the reclaim_bgs list. */
1538                 trace_btrfs_add_unused_block_group(bg);
1539                 list_move_tail(&bg->bg_list, &fs_info->unused_bgs);
1540         }
1541         spin_unlock(&fs_info->unused_bgs_lock);
1542 }
1543
1544 /*
1545  * We want block groups with a low number of used bytes to be in the beginning
1546  * of the list, so they will get reclaimed first.
1547  */
1548 static int reclaim_bgs_cmp(void *unused, const struct list_head *a,
1549                            const struct list_head *b)
1550 {
1551         const struct btrfs_block_group *bg1, *bg2;
1552
1553         bg1 = list_entry(a, struct btrfs_block_group, bg_list);
1554         bg2 = list_entry(b, struct btrfs_block_group, bg_list);
1555
1556         return bg1->used > bg2->used;
1557 }
1558
1559 static inline bool btrfs_should_reclaim(struct btrfs_fs_info *fs_info)
1560 {
1561         if (btrfs_is_zoned(fs_info))
1562                 return btrfs_zoned_should_reclaim(fs_info);
1563         return true;
1564 }
1565
1566 void btrfs_reclaim_bgs_work(struct work_struct *work)
1567 {
1568         struct btrfs_fs_info *fs_info =
1569                 container_of(work, struct btrfs_fs_info, reclaim_bgs_work);
1570         struct btrfs_block_group *bg;
1571         struct btrfs_space_info *space_info;
1572
1573         if (!test_bit(BTRFS_FS_OPEN, &fs_info->flags))
1574                 return;
1575
1576         if (btrfs_fs_closing(fs_info))
1577                 return;
1578
1579         if (!btrfs_should_reclaim(fs_info))
1580                 return;
1581
1582         sb_start_write(fs_info->sb);
1583
1584         if (!btrfs_exclop_start(fs_info, BTRFS_EXCLOP_BALANCE)) {
1585                 sb_end_write(fs_info->sb);
1586                 return;
1587         }
1588
1589         /*
1590          * Long running balances can keep us blocked here for eternity, so
1591          * simply skip reclaim if we're unable to get the mutex.
1592          */
1593         if (!mutex_trylock(&fs_info->reclaim_bgs_lock)) {
1594                 btrfs_exclop_finish(fs_info);
1595                 sb_end_write(fs_info->sb);
1596                 return;
1597         }
1598
1599         spin_lock(&fs_info->unused_bgs_lock);
1600         /*
1601          * Sort happens under lock because we can't simply splice it and sort.
1602          * The block groups might still be in use and reachable via bg_list,
1603          * and their presence in the reclaim_bgs list must be preserved.
1604          */
1605         list_sort(NULL, &fs_info->reclaim_bgs, reclaim_bgs_cmp);
1606         while (!list_empty(&fs_info->reclaim_bgs)) {
1607                 u64 zone_unusable;
1608                 int ret = 0;
1609
1610                 bg = list_first_entry(&fs_info->reclaim_bgs,
1611                                       struct btrfs_block_group,
1612                                       bg_list);
1613                 list_del_init(&bg->bg_list);
1614
1615                 space_info = bg->space_info;
1616                 spin_unlock(&fs_info->unused_bgs_lock);
1617
1618                 /* Don't race with allocators so take the groups_sem */
1619                 down_write(&space_info->groups_sem);
1620
1621                 spin_lock(&bg->lock);
1622                 if (bg->reserved || bg->pinned || bg->ro) {
1623                         /*
1624                          * We want to bail if we made new allocations or have
1625                          * outstanding allocations in this block group.  We do
1626                          * the ro check in case balance is currently acting on
1627                          * this block group.
1628                          */
1629                         spin_unlock(&bg->lock);
1630                         up_write(&space_info->groups_sem);
1631                         goto next;
1632                 }
1633                 spin_unlock(&bg->lock);
1634
1635                 /*
1636                  * Get out fast, in case we're read-only or unmounting the
1637                  * filesystem. It is OK to drop block groups from the list even
1638                  * for the read-only case. As we did sb_start_write(),
1639                  * "mount -o remount,ro" won't happen and read-only filesystem
1640                  * means it is forced read-only due to a fatal error. So, it
1641                  * never gets back to read-write to let us reclaim again.
1642                  */
1643                 if (btrfs_need_cleaner_sleep(fs_info)) {
1644                         up_write(&space_info->groups_sem);
1645                         goto next;
1646                 }
1647
1648                 /*
1649                  * Cache the zone_unusable value before turning the block group
1650                  * to read only. As soon as the blog group is read only it's
1651                  * zone_unusable value gets moved to the block group's read-only
1652                  * bytes and isn't available for calculations anymore.
1653                  */
1654                 zone_unusable = bg->zone_unusable;
1655                 ret = inc_block_group_ro(bg, 0);
1656                 up_write(&space_info->groups_sem);
1657                 if (ret < 0)
1658                         goto next;
1659
1660                 btrfs_info(fs_info,
1661                         "reclaiming chunk %llu with %llu%% used %llu%% unusable",
1662                                 bg->start,
1663                                 div64_u64(bg->used * 100, bg->length),
1664                                 div64_u64(zone_unusable * 100, bg->length));
1665                 trace_btrfs_reclaim_block_group(bg);
1666                 ret = btrfs_relocate_chunk(fs_info, bg->start);
1667                 if (ret) {
1668                         btrfs_dec_block_group_ro(bg);
1669                         btrfs_err(fs_info, "error relocating chunk %llu",
1670                                   bg->start);
1671                 }
1672
1673 next:
1674                 if (ret)
1675                         btrfs_mark_bg_to_reclaim(bg);
1676                 btrfs_put_block_group(bg);
1677
1678                 mutex_unlock(&fs_info->reclaim_bgs_lock);
1679                 /*
1680                  * Reclaiming all the block groups in the list can take really
1681                  * long.  Prioritize cleaning up unused block groups.
1682                  */
1683                 btrfs_delete_unused_bgs(fs_info);
1684                 /*
1685                  * If we are interrupted by a balance, we can just bail out. The
1686                  * cleaner thread restart again if necessary.
1687                  */
1688                 if (!mutex_trylock(&fs_info->reclaim_bgs_lock))
1689                         goto end;
1690                 spin_lock(&fs_info->unused_bgs_lock);
1691         }
1692         spin_unlock(&fs_info->unused_bgs_lock);
1693         mutex_unlock(&fs_info->reclaim_bgs_lock);
1694 end:
1695         btrfs_exclop_finish(fs_info);
1696         sb_end_write(fs_info->sb);
1697 }
1698
1699 void btrfs_reclaim_bgs(struct btrfs_fs_info *fs_info)
1700 {
1701         spin_lock(&fs_info->unused_bgs_lock);
1702         if (!list_empty(&fs_info->reclaim_bgs))
1703                 queue_work(system_unbound_wq, &fs_info->reclaim_bgs_work);
1704         spin_unlock(&fs_info->unused_bgs_lock);
1705 }
1706
1707 void btrfs_mark_bg_to_reclaim(struct btrfs_block_group *bg)
1708 {
1709         struct btrfs_fs_info *fs_info = bg->fs_info;
1710
1711         spin_lock(&fs_info->unused_bgs_lock);
1712         if (list_empty(&bg->bg_list)) {
1713                 btrfs_get_block_group(bg);
1714                 trace_btrfs_add_reclaim_block_group(bg);
1715                 list_add_tail(&bg->bg_list, &fs_info->reclaim_bgs);
1716         }
1717         spin_unlock(&fs_info->unused_bgs_lock);
1718 }
1719
1720 static int read_bg_from_eb(struct btrfs_fs_info *fs_info, struct btrfs_key *key,
1721                            struct btrfs_path *path)
1722 {
1723         struct extent_map_tree *em_tree;
1724         struct extent_map *em;
1725         struct btrfs_block_group_item bg;
1726         struct extent_buffer *leaf;
1727         int slot;
1728         u64 flags;
1729         int ret = 0;
1730
1731         slot = path->slots[0];
1732         leaf = path->nodes[0];
1733
1734         em_tree = &fs_info->mapping_tree;
1735         read_lock(&em_tree->lock);
1736         em = lookup_extent_mapping(em_tree, key->objectid, key->offset);
1737         read_unlock(&em_tree->lock);
1738         if (!em) {
1739                 btrfs_err(fs_info,
1740                           "logical %llu len %llu found bg but no related chunk",
1741                           key->objectid, key->offset);
1742                 return -ENOENT;
1743         }
1744
1745         if (em->start != key->objectid || em->len != key->offset) {
1746                 btrfs_err(fs_info,
1747                         "block group %llu len %llu mismatch with chunk %llu len %llu",
1748                         key->objectid, key->offset, em->start, em->len);
1749                 ret = -EUCLEAN;
1750                 goto out_free_em;
1751         }
1752
1753         read_extent_buffer(leaf, &bg, btrfs_item_ptr_offset(leaf, slot),
1754                            sizeof(bg));
1755         flags = btrfs_stack_block_group_flags(&bg) &
1756                 BTRFS_BLOCK_GROUP_TYPE_MASK;
1757
1758         if (flags != (em->map_lookup->type & BTRFS_BLOCK_GROUP_TYPE_MASK)) {
1759                 btrfs_err(fs_info,
1760 "block group %llu len %llu type flags 0x%llx mismatch with chunk type flags 0x%llx",
1761                           key->objectid, key->offset, flags,
1762                           (BTRFS_BLOCK_GROUP_TYPE_MASK & em->map_lookup->type));
1763                 ret = -EUCLEAN;
1764         }
1765
1766 out_free_em:
1767         free_extent_map(em);
1768         return ret;
1769 }
1770
1771 static int find_first_block_group(struct btrfs_fs_info *fs_info,
1772                                   struct btrfs_path *path,
1773                                   struct btrfs_key *key)
1774 {
1775         struct btrfs_root *root = btrfs_block_group_root(fs_info);
1776         int ret;
1777         struct btrfs_key found_key;
1778
1779         btrfs_for_each_slot(root, key, &found_key, path, ret) {
1780                 if (found_key.objectid >= key->objectid &&
1781                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1782                         return read_bg_from_eb(fs_info, &found_key, path);
1783                 }
1784         }
1785         return ret;
1786 }
1787
1788 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1789 {
1790         u64 extra_flags = chunk_to_extended(flags) &
1791                                 BTRFS_EXTENDED_PROFILE_MASK;
1792
1793         write_seqlock(&fs_info->profiles_lock);
1794         if (flags & BTRFS_BLOCK_GROUP_DATA)
1795                 fs_info->avail_data_alloc_bits |= extra_flags;
1796         if (flags & BTRFS_BLOCK_GROUP_METADATA)
1797                 fs_info->avail_metadata_alloc_bits |= extra_flags;
1798         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1799                 fs_info->avail_system_alloc_bits |= extra_flags;
1800         write_sequnlock(&fs_info->profiles_lock);
1801 }
1802
1803 /**
1804  * Map a physical disk address to a list of logical addresses
1805  *
1806  * @fs_info:       the filesystem
1807  * @chunk_start:   logical address of block group
1808  * @bdev:          physical device to resolve, can be NULL to indicate any device
1809  * @physical:      physical address to map to logical addresses
1810  * @logical:       return array of logical addresses which map to @physical
1811  * @naddrs:        length of @logical
1812  * @stripe_len:    size of IO stripe for the given block group
1813  *
1814  * Maps a particular @physical disk address to a list of @logical addresses.
1815  * Used primarily to exclude those portions of a block group that contain super
1816  * block copies.
1817  */
1818 int btrfs_rmap_block(struct btrfs_fs_info *fs_info, u64 chunk_start,
1819                      struct block_device *bdev, u64 physical, u64 **logical,
1820                      int *naddrs, int *stripe_len)
1821 {
1822         struct extent_map *em;
1823         struct map_lookup *map;
1824         u64 *buf;
1825         u64 bytenr;
1826         u64 data_stripe_length;
1827         u64 io_stripe_size;
1828         int i, nr = 0;
1829         int ret = 0;
1830
1831         em = btrfs_get_chunk_map(fs_info, chunk_start, 1);
1832         if (IS_ERR(em))
1833                 return -EIO;
1834
1835         map = em->map_lookup;
1836         data_stripe_length = em->orig_block_len;
1837         io_stripe_size = map->stripe_len;
1838         chunk_start = em->start;
1839
1840         /* For RAID5/6 adjust to a full IO stripe length */
1841         if (map->type & BTRFS_BLOCK_GROUP_RAID56_MASK)
1842                 io_stripe_size = map->stripe_len * nr_data_stripes(map);
1843
1844         buf = kcalloc(map->num_stripes, sizeof(u64), GFP_NOFS);
1845         if (!buf) {
1846                 ret = -ENOMEM;
1847                 goto out;
1848         }
1849
1850         for (i = 0; i < map->num_stripes; i++) {
1851                 bool already_inserted = false;
1852                 u64 stripe_nr;
1853                 u64 offset;
1854                 int j;
1855
1856                 if (!in_range(physical, map->stripes[i].physical,
1857                               data_stripe_length))
1858                         continue;
1859
1860                 if (bdev && map->stripes[i].dev->bdev != bdev)
1861                         continue;
1862
1863                 stripe_nr = physical - map->stripes[i].physical;
1864                 stripe_nr = div64_u64_rem(stripe_nr, map->stripe_len, &offset);
1865
1866                 if (map->type & (BTRFS_BLOCK_GROUP_RAID0 |
1867                                  BTRFS_BLOCK_GROUP_RAID10)) {
1868                         stripe_nr = stripe_nr * map->num_stripes + i;
1869                         stripe_nr = div_u64(stripe_nr, map->sub_stripes);
1870                 }
1871                 /*
1872                  * The remaining case would be for RAID56, multiply by
1873                  * nr_data_stripes().  Alternatively, just use rmap_len below
1874                  * instead of map->stripe_len
1875                  */
1876
1877                 bytenr = chunk_start + stripe_nr * io_stripe_size + offset;
1878
1879                 /* Ensure we don't add duplicate addresses */
1880                 for (j = 0; j < nr; j++) {
1881                         if (buf[j] == bytenr) {
1882                                 already_inserted = true;
1883                                 break;
1884                         }
1885                 }
1886
1887                 if (!already_inserted)
1888                         buf[nr++] = bytenr;
1889         }
1890
1891         *logical = buf;
1892         *naddrs = nr;
1893         *stripe_len = io_stripe_size;
1894 out:
1895         free_extent_map(em);
1896         return ret;
1897 }
1898
1899 static int exclude_super_stripes(struct btrfs_block_group *cache)
1900 {
1901         struct btrfs_fs_info *fs_info = cache->fs_info;
1902         const bool zoned = btrfs_is_zoned(fs_info);
1903         u64 bytenr;
1904         u64 *logical;
1905         int stripe_len;
1906         int i, nr, ret;
1907
1908         if (cache->start < BTRFS_SUPER_INFO_OFFSET) {
1909                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->start;
1910                 cache->bytes_super += stripe_len;
1911                 ret = btrfs_add_excluded_extent(fs_info, cache->start,
1912                                                 stripe_len);
1913                 if (ret)
1914                         return ret;
1915         }
1916
1917         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
1918                 bytenr = btrfs_sb_offset(i);
1919                 ret = btrfs_rmap_block(fs_info, cache->start, NULL,
1920                                        bytenr, &logical, &nr, &stripe_len);
1921                 if (ret)
1922                         return ret;
1923
1924                 /* Shouldn't have super stripes in sequential zones */
1925                 if (zoned && nr) {
1926                         kfree(logical);
1927                         btrfs_err(fs_info,
1928                         "zoned: block group %llu must not contain super block",
1929                                   cache->start);
1930                         return -EUCLEAN;
1931                 }
1932
1933                 while (nr--) {
1934                         u64 len = min_t(u64, stripe_len,
1935                                 cache->start + cache->length - logical[nr]);
1936
1937                         cache->bytes_super += len;
1938                         ret = btrfs_add_excluded_extent(fs_info, logical[nr],
1939                                                         len);
1940                         if (ret) {
1941                                 kfree(logical);
1942                                 return ret;
1943                         }
1944                 }
1945
1946                 kfree(logical);
1947         }
1948         return 0;
1949 }
1950
1951 static struct btrfs_block_group *btrfs_create_block_group_cache(
1952                 struct btrfs_fs_info *fs_info, u64 start)
1953 {
1954         struct btrfs_block_group *cache;
1955
1956         cache = kzalloc(sizeof(*cache), GFP_NOFS);
1957         if (!cache)
1958                 return NULL;
1959
1960         cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
1961                                         GFP_NOFS);
1962         if (!cache->free_space_ctl) {
1963                 kfree(cache);
1964                 return NULL;
1965         }
1966
1967         cache->start = start;
1968
1969         cache->fs_info = fs_info;
1970         cache->full_stripe_len = btrfs_full_stripe_len(fs_info, start);
1971
1972         cache->discard_index = BTRFS_DISCARD_INDEX_UNUSED;
1973
1974         refcount_set(&cache->refs, 1);
1975         spin_lock_init(&cache->lock);
1976         init_rwsem(&cache->data_rwsem);
1977         INIT_LIST_HEAD(&cache->list);
1978         INIT_LIST_HEAD(&cache->cluster_list);
1979         INIT_LIST_HEAD(&cache->bg_list);
1980         INIT_LIST_HEAD(&cache->ro_list);
1981         INIT_LIST_HEAD(&cache->discard_list);
1982         INIT_LIST_HEAD(&cache->dirty_list);
1983         INIT_LIST_HEAD(&cache->io_list);
1984         INIT_LIST_HEAD(&cache->active_bg_list);
1985         btrfs_init_free_space_ctl(cache, cache->free_space_ctl);
1986         atomic_set(&cache->frozen, 0);
1987         mutex_init(&cache->free_space_lock);
1988         cache->full_stripe_locks_root.root = RB_ROOT;
1989         mutex_init(&cache->full_stripe_locks_root.lock);
1990
1991         return cache;
1992 }
1993
1994 /*
1995  * Iterate all chunks and verify that each of them has the corresponding block
1996  * group
1997  */
1998 static int check_chunk_block_group_mappings(struct btrfs_fs_info *fs_info)
1999 {
2000         struct extent_map_tree *map_tree = &fs_info->mapping_tree;
2001         struct extent_map *em;
2002         struct btrfs_block_group *bg;
2003         u64 start = 0;
2004         int ret = 0;
2005
2006         while (1) {
2007                 read_lock(&map_tree->lock);
2008                 /*
2009                  * lookup_extent_mapping will return the first extent map
2010                  * intersecting the range, so setting @len to 1 is enough to
2011                  * get the first chunk.
2012                  */
2013                 em = lookup_extent_mapping(map_tree, start, 1);
2014                 read_unlock(&map_tree->lock);
2015                 if (!em)
2016                         break;
2017
2018                 bg = btrfs_lookup_block_group(fs_info, em->start);
2019                 if (!bg) {
2020                         btrfs_err(fs_info,
2021         "chunk start=%llu len=%llu doesn't have corresponding block group",
2022                                      em->start, em->len);
2023                         ret = -EUCLEAN;
2024                         free_extent_map(em);
2025                         break;
2026                 }
2027                 if (bg->start != em->start || bg->length != em->len ||
2028                     (bg->flags & BTRFS_BLOCK_GROUP_TYPE_MASK) !=
2029                     (em->map_lookup->type & BTRFS_BLOCK_GROUP_TYPE_MASK)) {
2030                         btrfs_err(fs_info,
2031 "chunk start=%llu len=%llu flags=0x%llx doesn't match block group start=%llu len=%llu flags=0x%llx",
2032                                 em->start, em->len,
2033                                 em->map_lookup->type & BTRFS_BLOCK_GROUP_TYPE_MASK,
2034                                 bg->start, bg->length,
2035                                 bg->flags & BTRFS_BLOCK_GROUP_TYPE_MASK);
2036                         ret = -EUCLEAN;
2037                         free_extent_map(em);
2038                         btrfs_put_block_group(bg);
2039                         break;
2040                 }
2041                 start = em->start + em->len;
2042                 free_extent_map(em);
2043                 btrfs_put_block_group(bg);
2044         }
2045         return ret;
2046 }
2047
2048 static int read_one_block_group(struct btrfs_fs_info *info,
2049                                 struct btrfs_block_group_item *bgi,
2050                                 const struct btrfs_key *key,
2051                                 int need_clear)
2052 {
2053         struct btrfs_block_group *cache;
2054         const bool mixed = btrfs_fs_incompat(info, MIXED_GROUPS);
2055         int ret;
2056
2057         ASSERT(key->type == BTRFS_BLOCK_GROUP_ITEM_KEY);
2058
2059         cache = btrfs_create_block_group_cache(info, key->objectid);
2060         if (!cache)
2061                 return -ENOMEM;
2062
2063         cache->length = key->offset;
2064         cache->used = btrfs_stack_block_group_used(bgi);
2065         cache->flags = btrfs_stack_block_group_flags(bgi);
2066         cache->global_root_id = btrfs_stack_block_group_chunk_objectid(bgi);
2067
2068         set_free_space_tree_thresholds(cache);
2069
2070         if (need_clear) {
2071                 /*
2072                  * When we mount with old space cache, we need to
2073                  * set BTRFS_DC_CLEAR and set dirty flag.
2074                  *
2075                  * a) Setting 'BTRFS_DC_CLEAR' makes sure that we
2076                  *    truncate the old free space cache inode and
2077                  *    setup a new one.
2078                  * b) Setting 'dirty flag' makes sure that we flush
2079                  *    the new space cache info onto disk.
2080                  */
2081                 if (btrfs_test_opt(info, SPACE_CACHE))
2082                         cache->disk_cache_state = BTRFS_DC_CLEAR;
2083         }
2084         if (!mixed && ((cache->flags & BTRFS_BLOCK_GROUP_METADATA) &&
2085             (cache->flags & BTRFS_BLOCK_GROUP_DATA))) {
2086                         btrfs_err(info,
2087 "bg %llu is a mixed block group but filesystem hasn't enabled mixed block groups",
2088                                   cache->start);
2089                         ret = -EINVAL;
2090                         goto error;
2091         }
2092
2093         ret = btrfs_load_block_group_zone_info(cache, false);
2094         if (ret) {
2095                 btrfs_err(info, "zoned: failed to load zone info of bg %llu",
2096                           cache->start);
2097                 goto error;
2098         }
2099
2100         /*
2101          * We need to exclude the super stripes now so that the space info has
2102          * super bytes accounted for, otherwise we'll think we have more space
2103          * than we actually do.
2104          */
2105         ret = exclude_super_stripes(cache);
2106         if (ret) {
2107                 /* We may have excluded something, so call this just in case. */
2108                 btrfs_free_excluded_extents(cache);
2109                 goto error;
2110         }
2111
2112         /*
2113          * For zoned filesystem, space after the allocation offset is the only
2114          * free space for a block group. So, we don't need any caching work.
2115          * btrfs_calc_zone_unusable() will set the amount of free space and
2116          * zone_unusable space.
2117          *
2118          * For regular filesystem, check for two cases, either we are full, and
2119          * therefore don't need to bother with the caching work since we won't
2120          * find any space, or we are empty, and we can just add all the space
2121          * in and be done with it.  This saves us _a_lot_ of time, particularly
2122          * in the full case.
2123          */
2124         if (btrfs_is_zoned(info)) {
2125                 btrfs_calc_zone_unusable(cache);
2126                 /* Should not have any excluded extents. Just in case, though. */
2127                 btrfs_free_excluded_extents(cache);
2128         } else if (cache->length == cache->used) {
2129                 cache->cached = BTRFS_CACHE_FINISHED;
2130                 btrfs_free_excluded_extents(cache);
2131         } else if (cache->used == 0) {
2132                 cache->cached = BTRFS_CACHE_FINISHED;
2133                 ret = add_new_free_space(cache, cache->start,
2134                                          cache->start + cache->length, NULL);
2135                 btrfs_free_excluded_extents(cache);
2136                 if (ret)
2137                         goto error;
2138         }
2139
2140         ret = btrfs_add_block_group_cache(info, cache);
2141         if (ret) {
2142                 btrfs_remove_free_space_cache(cache);
2143                 goto error;
2144         }
2145         trace_btrfs_add_block_group(info, cache, 0);
2146         btrfs_add_bg_to_space_info(info, cache);
2147
2148         set_avail_alloc_bits(info, cache->flags);
2149         if (btrfs_chunk_writeable(info, cache->start)) {
2150                 if (cache->used == 0) {
2151                         ASSERT(list_empty(&cache->bg_list));
2152                         if (btrfs_test_opt(info, DISCARD_ASYNC))
2153                                 btrfs_discard_queue_work(&info->discard_ctl, cache);
2154                         else
2155                                 btrfs_mark_bg_unused(cache);
2156                 }
2157         } else {
2158                 inc_block_group_ro(cache, 1);
2159         }
2160
2161         return 0;
2162 error:
2163         btrfs_put_block_group(cache);
2164         return ret;
2165 }
2166
2167 static int fill_dummy_bgs(struct btrfs_fs_info *fs_info)
2168 {
2169         struct extent_map_tree *em_tree = &fs_info->mapping_tree;
2170         struct rb_node *node;
2171         int ret = 0;
2172
2173         for (node = rb_first_cached(&em_tree->map); node; node = rb_next(node)) {
2174                 struct extent_map *em;
2175                 struct map_lookup *map;
2176                 struct btrfs_block_group *bg;
2177
2178                 em = rb_entry(node, struct extent_map, rb_node);
2179                 map = em->map_lookup;
2180                 bg = btrfs_create_block_group_cache(fs_info, em->start);
2181                 if (!bg) {
2182                         ret = -ENOMEM;
2183                         break;
2184                 }
2185
2186                 /* Fill dummy cache as FULL */
2187                 bg->length = em->len;
2188                 bg->flags = map->type;
2189                 bg->cached = BTRFS_CACHE_FINISHED;
2190                 bg->used = em->len;
2191                 bg->flags = map->type;
2192                 ret = btrfs_add_block_group_cache(fs_info, bg);
2193                 /*
2194                  * We may have some valid block group cache added already, in
2195                  * that case we skip to the next one.
2196                  */
2197                 if (ret == -EEXIST) {
2198                         ret = 0;
2199                         btrfs_put_block_group(bg);
2200                         continue;
2201                 }
2202
2203                 if (ret) {
2204                         btrfs_remove_free_space_cache(bg);
2205                         btrfs_put_block_group(bg);
2206                         break;
2207                 }
2208
2209                 btrfs_add_bg_to_space_info(fs_info, bg);
2210
2211                 set_avail_alloc_bits(fs_info, bg->flags);
2212         }
2213         if (!ret)
2214                 btrfs_init_global_block_rsv(fs_info);
2215         return ret;
2216 }
2217
2218 int btrfs_read_block_groups(struct btrfs_fs_info *info)
2219 {
2220         struct btrfs_root *root = btrfs_block_group_root(info);
2221         struct btrfs_path *path;
2222         int ret;
2223         struct btrfs_block_group *cache;
2224         struct btrfs_space_info *space_info;
2225         struct btrfs_key key;
2226         int need_clear = 0;
2227         u64 cache_gen;
2228
2229         /*
2230          * Either no extent root (with ibadroots rescue option) or we have
2231          * unsupported RO options. The fs can never be mounted read-write, so no
2232          * need to waste time searching block group items.
2233          *
2234          * This also allows new extent tree related changes to be RO compat,
2235          * no need for a full incompat flag.
2236          */
2237         if (!root || (btrfs_super_compat_ro_flags(info->super_copy) &
2238                       ~BTRFS_FEATURE_COMPAT_RO_SUPP))
2239                 return fill_dummy_bgs(info);
2240
2241         key.objectid = 0;
2242         key.offset = 0;
2243         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
2244         path = btrfs_alloc_path();
2245         if (!path)
2246                 return -ENOMEM;
2247
2248         cache_gen = btrfs_super_cache_generation(info->super_copy);
2249         if (btrfs_test_opt(info, SPACE_CACHE) &&
2250             btrfs_super_generation(info->super_copy) != cache_gen)
2251                 need_clear = 1;
2252         if (btrfs_test_opt(info, CLEAR_CACHE))
2253                 need_clear = 1;
2254
2255         while (1) {
2256                 struct btrfs_block_group_item bgi;
2257                 struct extent_buffer *leaf;
2258                 int slot;
2259
2260                 ret = find_first_block_group(info, path, &key);
2261                 if (ret > 0)
2262                         break;
2263                 if (ret != 0)
2264                         goto error;
2265
2266                 leaf = path->nodes[0];
2267                 slot = path->slots[0];
2268
2269                 read_extent_buffer(leaf, &bgi, btrfs_item_ptr_offset(leaf, slot),
2270                                    sizeof(bgi));
2271
2272                 btrfs_item_key_to_cpu(leaf, &key, slot);
2273                 btrfs_release_path(path);
2274                 ret = read_one_block_group(info, &bgi, &key, need_clear);
2275                 if (ret < 0)
2276                         goto error;
2277                 key.objectid += key.offset;
2278                 key.offset = 0;
2279         }
2280         btrfs_release_path(path);
2281
2282         list_for_each_entry(space_info, &info->space_info, list) {
2283                 int i;
2284
2285                 for (i = 0; i < BTRFS_NR_RAID_TYPES; i++) {
2286                         if (list_empty(&space_info->block_groups[i]))
2287                                 continue;
2288                         cache = list_first_entry(&space_info->block_groups[i],
2289                                                  struct btrfs_block_group,
2290                                                  list);
2291                         btrfs_sysfs_add_block_group_type(cache);
2292                 }
2293
2294                 if (!(btrfs_get_alloc_profile(info, space_info->flags) &
2295                       (BTRFS_BLOCK_GROUP_RAID10 |
2296                        BTRFS_BLOCK_GROUP_RAID1_MASK |
2297                        BTRFS_BLOCK_GROUP_RAID56_MASK |
2298                        BTRFS_BLOCK_GROUP_DUP)))
2299                         continue;
2300                 /*
2301                  * Avoid allocating from un-mirrored block group if there are
2302                  * mirrored block groups.
2303                  */
2304                 list_for_each_entry(cache,
2305                                 &space_info->block_groups[BTRFS_RAID_RAID0],
2306                                 list)
2307                         inc_block_group_ro(cache, 1);
2308                 list_for_each_entry(cache,
2309                                 &space_info->block_groups[BTRFS_RAID_SINGLE],
2310                                 list)
2311                         inc_block_group_ro(cache, 1);
2312         }
2313
2314         btrfs_init_global_block_rsv(info);
2315         ret = check_chunk_block_group_mappings(info);
2316 error:
2317         btrfs_free_path(path);
2318         /*
2319          * We've hit some error while reading the extent tree, and have
2320          * rescue=ibadroots mount option.
2321          * Try to fill the tree using dummy block groups so that the user can
2322          * continue to mount and grab their data.
2323          */
2324         if (ret && btrfs_test_opt(info, IGNOREBADROOTS))
2325                 ret = fill_dummy_bgs(info);
2326         return ret;
2327 }
2328
2329 /*
2330  * This function, insert_block_group_item(), belongs to the phase 2 of chunk
2331  * allocation.
2332  *
2333  * See the comment at btrfs_chunk_alloc() for details about the chunk allocation
2334  * phases.
2335  */
2336 static int insert_block_group_item(struct btrfs_trans_handle *trans,
2337                                    struct btrfs_block_group *block_group)
2338 {
2339         struct btrfs_fs_info *fs_info = trans->fs_info;
2340         struct btrfs_block_group_item bgi;
2341         struct btrfs_root *root = btrfs_block_group_root(fs_info);
2342         struct btrfs_key key;
2343
2344         spin_lock(&block_group->lock);
2345         btrfs_set_stack_block_group_used(&bgi, block_group->used);
2346         btrfs_set_stack_block_group_chunk_objectid(&bgi,
2347                                                    block_group->global_root_id);
2348         btrfs_set_stack_block_group_flags(&bgi, block_group->flags);
2349         key.objectid = block_group->start;
2350         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
2351         key.offset = block_group->length;
2352         spin_unlock(&block_group->lock);
2353
2354         return btrfs_insert_item(trans, root, &key, &bgi, sizeof(bgi));
2355 }
2356
2357 static int insert_dev_extent(struct btrfs_trans_handle *trans,
2358                             struct btrfs_device *device, u64 chunk_offset,
2359                             u64 start, u64 num_bytes)
2360 {
2361         struct btrfs_fs_info *fs_info = device->fs_info;
2362         struct btrfs_root *root = fs_info->dev_root;
2363         struct btrfs_path *path;
2364         struct btrfs_dev_extent *extent;
2365         struct extent_buffer *leaf;
2366         struct btrfs_key key;
2367         int ret;
2368
2369         WARN_ON(!test_bit(BTRFS_DEV_STATE_IN_FS_METADATA, &device->dev_state));
2370         WARN_ON(test_bit(BTRFS_DEV_STATE_REPLACE_TGT, &device->dev_state));
2371         path = btrfs_alloc_path();
2372         if (!path)
2373                 return -ENOMEM;
2374
2375         key.objectid = device->devid;
2376         key.type = BTRFS_DEV_EXTENT_KEY;
2377         key.offset = start;
2378         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*extent));
2379         if (ret)
2380                 goto out;
2381
2382         leaf = path->nodes[0];
2383         extent = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_extent);
2384         btrfs_set_dev_extent_chunk_tree(leaf, extent, BTRFS_CHUNK_TREE_OBJECTID);
2385         btrfs_set_dev_extent_chunk_objectid(leaf, extent,
2386                                             BTRFS_FIRST_CHUNK_TREE_OBJECTID);
2387         btrfs_set_dev_extent_chunk_offset(leaf, extent, chunk_offset);
2388
2389         btrfs_set_dev_extent_length(leaf, extent, num_bytes);
2390         btrfs_mark_buffer_dirty(leaf);
2391 out:
2392         btrfs_free_path(path);
2393         return ret;
2394 }
2395
2396 /*
2397  * This function belongs to phase 2.
2398  *
2399  * See the comment at btrfs_chunk_alloc() for details about the chunk allocation
2400  * phases.
2401  */
2402 static int insert_dev_extents(struct btrfs_trans_handle *trans,
2403                                    u64 chunk_offset, u64 chunk_size)
2404 {
2405         struct btrfs_fs_info *fs_info = trans->fs_info;
2406         struct btrfs_device *device;
2407         struct extent_map *em;
2408         struct map_lookup *map;
2409         u64 dev_offset;
2410         u64 stripe_size;
2411         int i;
2412         int ret = 0;
2413
2414         em = btrfs_get_chunk_map(fs_info, chunk_offset, chunk_size);
2415         if (IS_ERR(em))
2416                 return PTR_ERR(em);
2417
2418         map = em->map_lookup;
2419         stripe_size = em->orig_block_len;
2420
2421         /*
2422          * Take the device list mutex to prevent races with the final phase of
2423          * a device replace operation that replaces the device object associated
2424          * with the map's stripes, because the device object's id can change
2425          * at any time during that final phase of the device replace operation
2426          * (dev-replace.c:btrfs_dev_replace_finishing()), so we could grab the
2427          * replaced device and then see it with an ID of BTRFS_DEV_REPLACE_DEVID,
2428          * resulting in persisting a device extent item with such ID.
2429          */
2430         mutex_lock(&fs_info->fs_devices->device_list_mutex);
2431         for (i = 0; i < map->num_stripes; i++) {
2432                 device = map->stripes[i].dev;
2433                 dev_offset = map->stripes[i].physical;
2434
2435                 ret = insert_dev_extent(trans, device, chunk_offset, dev_offset,
2436                                        stripe_size);
2437                 if (ret)
2438                         break;
2439         }
2440         mutex_unlock(&fs_info->fs_devices->device_list_mutex);
2441
2442         free_extent_map(em);
2443         return ret;
2444 }
2445
2446 /*
2447  * This function, btrfs_create_pending_block_groups(), belongs to the phase 2 of
2448  * chunk allocation.
2449  *
2450  * See the comment at btrfs_chunk_alloc() for details about the chunk allocation
2451  * phases.
2452  */
2453 void btrfs_create_pending_block_groups(struct btrfs_trans_handle *trans)
2454 {
2455         struct btrfs_fs_info *fs_info = trans->fs_info;
2456         struct btrfs_block_group *block_group;
2457         int ret = 0;
2458
2459         while (!list_empty(&trans->new_bgs)) {
2460                 int index;
2461
2462                 block_group = list_first_entry(&trans->new_bgs,
2463                                                struct btrfs_block_group,
2464                                                bg_list);
2465                 if (ret)
2466                         goto next;
2467
2468                 index = btrfs_bg_flags_to_raid_index(block_group->flags);
2469
2470                 ret = insert_block_group_item(trans, block_group);
2471                 if (ret)
2472                         btrfs_abort_transaction(trans, ret);
2473                 if (!test_bit(BLOCK_GROUP_FLAG_CHUNK_ITEM_INSERTED,
2474                               &block_group->runtime_flags)) {
2475                         mutex_lock(&fs_info->chunk_mutex);
2476                         ret = btrfs_chunk_alloc_add_chunk_item(trans, block_group);
2477                         mutex_unlock(&fs_info->chunk_mutex);
2478                         if (ret)
2479                                 btrfs_abort_transaction(trans, ret);
2480                 }
2481                 ret = insert_dev_extents(trans, block_group->start,
2482                                          block_group->length);
2483                 if (ret)
2484                         btrfs_abort_transaction(trans, ret);
2485                 add_block_group_free_space(trans, block_group);
2486
2487                 /*
2488                  * If we restriped during balance, we may have added a new raid
2489                  * type, so now add the sysfs entries when it is safe to do so.
2490                  * We don't have to worry about locking here as it's handled in
2491                  * btrfs_sysfs_add_block_group_type.
2492                  */
2493                 if (block_group->space_info->block_group_kobjs[index] == NULL)
2494                         btrfs_sysfs_add_block_group_type(block_group);
2495
2496                 /* Already aborted the transaction if it failed. */
2497 next:
2498                 btrfs_delayed_refs_rsv_release(fs_info, 1);
2499                 list_del_init(&block_group->bg_list);
2500                 clear_bit(BLOCK_GROUP_FLAG_NEW, &block_group->runtime_flags);
2501         }
2502         btrfs_trans_release_chunk_metadata(trans);
2503 }
2504
2505 /*
2506  * For extent tree v2 we use the block_group_item->chunk_offset to point at our
2507  * global root id.  For v1 it's always set to BTRFS_FIRST_CHUNK_TREE_OBJECTID.
2508  */
2509 static u64 calculate_global_root_id(struct btrfs_fs_info *fs_info, u64 offset)
2510 {
2511         u64 div = SZ_1G;
2512         u64 index;
2513
2514         if (!btrfs_fs_incompat(fs_info, EXTENT_TREE_V2))
2515                 return BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2516
2517         /* If we have a smaller fs index based on 128MiB. */
2518         if (btrfs_super_total_bytes(fs_info->super_copy) <= (SZ_1G * 10ULL))
2519                 div = SZ_128M;
2520
2521         offset = div64_u64(offset, div);
2522         div64_u64_rem(offset, fs_info->nr_global_roots, &index);
2523         return index;
2524 }
2525
2526 struct btrfs_block_group *btrfs_make_block_group(struct btrfs_trans_handle *trans,
2527                                                  u64 bytes_used, u64 type,
2528                                                  u64 chunk_offset, u64 size)
2529 {
2530         struct btrfs_fs_info *fs_info = trans->fs_info;
2531         struct btrfs_block_group *cache;
2532         int ret;
2533
2534         btrfs_set_log_full_commit(trans);
2535
2536         cache = btrfs_create_block_group_cache(fs_info, chunk_offset);
2537         if (!cache)
2538                 return ERR_PTR(-ENOMEM);
2539
2540         /*
2541          * Mark it as new before adding it to the rbtree of block groups or any
2542          * list, so that no other task finds it and calls btrfs_mark_bg_unused()
2543          * before the new flag is set.
2544          */
2545         set_bit(BLOCK_GROUP_FLAG_NEW, &cache->runtime_flags);
2546
2547         cache->length = size;
2548         set_free_space_tree_thresholds(cache);
2549         cache->used = bytes_used;
2550         cache->flags = type;
2551         cache->cached = BTRFS_CACHE_FINISHED;
2552         cache->global_root_id = calculate_global_root_id(fs_info, cache->start);
2553
2554         if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
2555                 set_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &cache->runtime_flags);
2556
2557         ret = btrfs_load_block_group_zone_info(cache, true);
2558         if (ret) {
2559                 btrfs_put_block_group(cache);
2560                 return ERR_PTR(ret);
2561         }
2562
2563         ret = exclude_super_stripes(cache);
2564         if (ret) {
2565                 /* We may have excluded something, so call this just in case */
2566                 btrfs_free_excluded_extents(cache);
2567                 btrfs_put_block_group(cache);
2568                 return ERR_PTR(ret);
2569         }
2570
2571         ret = add_new_free_space(cache, chunk_offset, chunk_offset + size, NULL);
2572         btrfs_free_excluded_extents(cache);
2573         if (ret) {
2574                 btrfs_put_block_group(cache);
2575                 return ERR_PTR(ret);
2576         }
2577
2578         /*
2579          * Ensure the corresponding space_info object is created and
2580          * assigned to our block group. We want our bg to be added to the rbtree
2581          * with its ->space_info set.
2582          */
2583         cache->space_info = btrfs_find_space_info(fs_info, cache->flags);
2584         ASSERT(cache->space_info);
2585
2586         ret = btrfs_add_block_group_cache(fs_info, cache);
2587         if (ret) {
2588                 btrfs_remove_free_space_cache(cache);
2589                 btrfs_put_block_group(cache);
2590                 return ERR_PTR(ret);
2591         }
2592
2593         /*
2594          * Now that our block group has its ->space_info set and is inserted in
2595          * the rbtree, update the space info's counters.
2596          */
2597         trace_btrfs_add_block_group(fs_info, cache, 1);
2598         btrfs_add_bg_to_space_info(fs_info, cache);
2599         btrfs_update_global_block_rsv(fs_info);
2600
2601 #ifdef CONFIG_BTRFS_DEBUG
2602         if (btrfs_should_fragment_free_space(cache)) {
2603                 u64 new_bytes_used = size - bytes_used;
2604
2605                 cache->space_info->bytes_used += new_bytes_used >> 1;
2606                 fragment_free_space(cache);
2607         }
2608 #endif
2609
2610         list_add_tail(&cache->bg_list, &trans->new_bgs);
2611         trans->delayed_ref_updates++;
2612         btrfs_update_delayed_refs_rsv(trans);
2613
2614         set_avail_alloc_bits(fs_info, type);
2615         return cache;
2616 }
2617
2618 /*
2619  * Mark one block group RO, can be called several times for the same block
2620  * group.
2621  *
2622  * @cache:              the destination block group
2623  * @do_chunk_alloc:     whether need to do chunk pre-allocation, this is to
2624  *                      ensure we still have some free space after marking this
2625  *                      block group RO.
2626  */
2627 int btrfs_inc_block_group_ro(struct btrfs_block_group *cache,
2628                              bool do_chunk_alloc)
2629 {
2630         struct btrfs_fs_info *fs_info = cache->fs_info;
2631         struct btrfs_trans_handle *trans;
2632         struct btrfs_root *root = btrfs_block_group_root(fs_info);
2633         u64 alloc_flags;
2634         int ret;
2635         bool dirty_bg_running;
2636
2637         /*
2638          * This can only happen when we are doing read-only scrub on read-only
2639          * mount.
2640          * In that case we should not start a new transaction on read-only fs.
2641          * Thus here we skip all chunk allocations.
2642          */
2643         if (sb_rdonly(fs_info->sb)) {
2644                 mutex_lock(&fs_info->ro_block_group_mutex);
2645                 ret = inc_block_group_ro(cache, 0);
2646                 mutex_unlock(&fs_info->ro_block_group_mutex);
2647                 return ret;
2648         }
2649
2650         do {
2651                 trans = btrfs_join_transaction(root);
2652                 if (IS_ERR(trans))
2653                         return PTR_ERR(trans);
2654
2655                 dirty_bg_running = false;
2656
2657                 /*
2658                  * We're not allowed to set block groups readonly after the dirty
2659                  * block group cache has started writing.  If it already started,
2660                  * back off and let this transaction commit.
2661                  */
2662                 mutex_lock(&fs_info->ro_block_group_mutex);
2663                 if (test_bit(BTRFS_TRANS_DIRTY_BG_RUN, &trans->transaction->flags)) {
2664                         u64 transid = trans->transid;
2665
2666                         mutex_unlock(&fs_info->ro_block_group_mutex);
2667                         btrfs_end_transaction(trans);
2668
2669                         ret = btrfs_wait_for_commit(fs_info, transid);
2670                         if (ret)
2671                                 return ret;
2672                         dirty_bg_running = true;
2673                 }
2674         } while (dirty_bg_running);
2675
2676         if (do_chunk_alloc) {
2677                 /*
2678                  * If we are changing raid levels, try to allocate a
2679                  * corresponding block group with the new raid level.
2680                  */
2681                 alloc_flags = btrfs_get_alloc_profile(fs_info, cache->flags);
2682                 if (alloc_flags != cache->flags) {
2683                         ret = btrfs_chunk_alloc(trans, alloc_flags,
2684                                                 CHUNK_ALLOC_FORCE);
2685                         /*
2686                          * ENOSPC is allowed here, we may have enough space
2687                          * already allocated at the new raid level to carry on
2688                          */
2689                         if (ret == -ENOSPC)
2690                                 ret = 0;
2691                         if (ret < 0)
2692                                 goto out;
2693                 }
2694         }
2695
2696         ret = inc_block_group_ro(cache, 0);
2697         if (!ret)
2698                 goto out;
2699         if (ret == -ETXTBSY)
2700                 goto unlock_out;
2701
2702         /*
2703          * Skip chunk alloction if the bg is SYSTEM, this is to avoid system
2704          * chunk allocation storm to exhaust the system chunk array.  Otherwise
2705          * we still want to try our best to mark the block group read-only.
2706          */
2707         if (!do_chunk_alloc && ret == -ENOSPC &&
2708             (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM))
2709                 goto unlock_out;
2710
2711         alloc_flags = btrfs_get_alloc_profile(fs_info, cache->space_info->flags);
2712         ret = btrfs_chunk_alloc(trans, alloc_flags, CHUNK_ALLOC_FORCE);
2713         if (ret < 0)
2714                 goto out;
2715         /*
2716          * We have allocated a new chunk. We also need to activate that chunk to
2717          * grant metadata tickets for zoned filesystem.
2718          */
2719         ret = btrfs_zoned_activate_one_bg(fs_info, cache->space_info, true);
2720         if (ret < 0)
2721                 goto out;
2722
2723         ret = inc_block_group_ro(cache, 0);
2724         if (ret == -ETXTBSY)
2725                 goto unlock_out;
2726 out:
2727         if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
2728                 alloc_flags = btrfs_get_alloc_profile(fs_info, cache->flags);
2729                 mutex_lock(&fs_info->chunk_mutex);
2730                 check_system_chunk(trans, alloc_flags);
2731                 mutex_unlock(&fs_info->chunk_mutex);
2732         }
2733 unlock_out:
2734         mutex_unlock(&fs_info->ro_block_group_mutex);
2735
2736         btrfs_end_transaction(trans);
2737         return ret;
2738 }
2739
2740 void btrfs_dec_block_group_ro(struct btrfs_block_group *cache)
2741 {
2742         struct btrfs_space_info *sinfo = cache->space_info;
2743         u64 num_bytes;
2744
2745         BUG_ON(!cache->ro);
2746
2747         spin_lock(&sinfo->lock);
2748         spin_lock(&cache->lock);
2749         if (!--cache->ro) {
2750                 if (btrfs_is_zoned(cache->fs_info)) {
2751                         /* Migrate zone_unusable bytes back */
2752                         cache->zone_unusable =
2753                                 (cache->alloc_offset - cache->used) +
2754                                 (cache->length - cache->zone_capacity);
2755                         sinfo->bytes_zone_unusable += cache->zone_unusable;
2756                         sinfo->bytes_readonly -= cache->zone_unusable;
2757                 }
2758                 num_bytes = cache->length - cache->reserved -
2759                             cache->pinned - cache->bytes_super -
2760                             cache->zone_unusable - cache->used;
2761                 sinfo->bytes_readonly -= num_bytes;
2762                 list_del_init(&cache->ro_list);
2763         }
2764         spin_unlock(&cache->lock);
2765         spin_unlock(&sinfo->lock);
2766 }
2767
2768 static int update_block_group_item(struct btrfs_trans_handle *trans,
2769                                    struct btrfs_path *path,
2770                                    struct btrfs_block_group *cache)
2771 {
2772         struct btrfs_fs_info *fs_info = trans->fs_info;
2773         int ret;
2774         struct btrfs_root *root = btrfs_block_group_root(fs_info);
2775         unsigned long bi;
2776         struct extent_buffer *leaf;
2777         struct btrfs_block_group_item bgi;
2778         struct btrfs_key key;
2779
2780         key.objectid = cache->start;
2781         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
2782         key.offset = cache->length;
2783
2784         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2785         if (ret) {
2786                 if (ret > 0)
2787                         ret = -ENOENT;
2788                 goto fail;
2789         }
2790
2791         leaf = path->nodes[0];
2792         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
2793         btrfs_set_stack_block_group_used(&bgi, cache->used);
2794         btrfs_set_stack_block_group_chunk_objectid(&bgi,
2795                                                    cache->global_root_id);
2796         btrfs_set_stack_block_group_flags(&bgi, cache->flags);
2797         write_extent_buffer(leaf, &bgi, bi, sizeof(bgi));
2798         btrfs_mark_buffer_dirty(leaf);
2799 fail:
2800         btrfs_release_path(path);
2801         return ret;
2802
2803 }
2804
2805 static int cache_save_setup(struct btrfs_block_group *block_group,
2806                             struct btrfs_trans_handle *trans,
2807                             struct btrfs_path *path)
2808 {
2809         struct btrfs_fs_info *fs_info = block_group->fs_info;
2810         struct btrfs_root *root = fs_info->tree_root;
2811         struct inode *inode = NULL;
2812         struct extent_changeset *data_reserved = NULL;
2813         u64 alloc_hint = 0;
2814         int dcs = BTRFS_DC_ERROR;
2815         u64 cache_size = 0;
2816         int retries = 0;
2817         int ret = 0;
2818
2819         if (!btrfs_test_opt(fs_info, SPACE_CACHE))
2820                 return 0;
2821
2822         /*
2823          * If this block group is smaller than 100 megs don't bother caching the
2824          * block group.
2825          */
2826         if (block_group->length < (100 * SZ_1M)) {
2827                 spin_lock(&block_group->lock);
2828                 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
2829                 spin_unlock(&block_group->lock);
2830                 return 0;
2831         }
2832
2833         if (TRANS_ABORTED(trans))
2834                 return 0;
2835 again:
2836         inode = lookup_free_space_inode(block_group, path);
2837         if (IS_ERR(inode) && PTR_ERR(inode) != -ENOENT) {
2838                 ret = PTR_ERR(inode);
2839                 btrfs_release_path(path);
2840                 goto out;
2841         }
2842
2843         if (IS_ERR(inode)) {
2844                 BUG_ON(retries);
2845                 retries++;
2846
2847                 if (block_group->ro)
2848                         goto out_free;
2849
2850                 ret = create_free_space_inode(trans, block_group, path);
2851                 if (ret)
2852                         goto out_free;
2853                 goto again;
2854         }
2855
2856         /*
2857          * We want to set the generation to 0, that way if anything goes wrong
2858          * from here on out we know not to trust this cache when we load up next
2859          * time.
2860          */
2861         BTRFS_I(inode)->generation = 0;
2862         ret = btrfs_update_inode(trans, root, BTRFS_I(inode));
2863         if (ret) {
2864                 /*
2865                  * So theoretically we could recover from this, simply set the
2866                  * super cache generation to 0 so we know to invalidate the
2867                  * cache, but then we'd have to keep track of the block groups
2868                  * that fail this way so we know we _have_ to reset this cache
2869                  * before the next commit or risk reading stale cache.  So to
2870                  * limit our exposure to horrible edge cases lets just abort the
2871                  * transaction, this only happens in really bad situations
2872                  * anyway.
2873                  */
2874                 btrfs_abort_transaction(trans, ret);
2875                 goto out_put;
2876         }
2877         WARN_ON(ret);
2878
2879         /* We've already setup this transaction, go ahead and exit */
2880         if (block_group->cache_generation == trans->transid &&
2881             i_size_read(inode)) {
2882                 dcs = BTRFS_DC_SETUP;
2883                 goto out_put;
2884         }
2885
2886         if (i_size_read(inode) > 0) {
2887                 ret = btrfs_check_trunc_cache_free_space(fs_info,
2888                                         &fs_info->global_block_rsv);
2889                 if (ret)
2890                         goto out_put;
2891
2892                 ret = btrfs_truncate_free_space_cache(trans, NULL, inode);
2893                 if (ret)
2894                         goto out_put;
2895         }
2896
2897         spin_lock(&block_group->lock);
2898         if (block_group->cached != BTRFS_CACHE_FINISHED ||
2899             !btrfs_test_opt(fs_info, SPACE_CACHE)) {
2900                 /*
2901                  * don't bother trying to write stuff out _if_
2902                  * a) we're not cached,
2903                  * b) we're with nospace_cache mount option,
2904                  * c) we're with v2 space_cache (FREE_SPACE_TREE).
2905                  */
2906                 dcs = BTRFS_DC_WRITTEN;
2907                 spin_unlock(&block_group->lock);
2908                 goto out_put;
2909         }
2910         spin_unlock(&block_group->lock);
2911
2912         /*
2913          * We hit an ENOSPC when setting up the cache in this transaction, just
2914          * skip doing the setup, we've already cleared the cache so we're safe.
2915          */
2916         if (test_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags)) {
2917                 ret = -ENOSPC;
2918                 goto out_put;
2919         }
2920
2921         /*
2922          * Try to preallocate enough space based on how big the block group is.
2923          * Keep in mind this has to include any pinned space which could end up
2924          * taking up quite a bit since it's not folded into the other space
2925          * cache.
2926          */
2927         cache_size = div_u64(block_group->length, SZ_256M);
2928         if (!cache_size)
2929                 cache_size = 1;
2930
2931         cache_size *= 16;
2932         cache_size *= fs_info->sectorsize;
2933
2934         ret = btrfs_check_data_free_space(BTRFS_I(inode), &data_reserved, 0,
2935                                           cache_size, false);
2936         if (ret)
2937                 goto out_put;
2938
2939         ret = btrfs_prealloc_file_range_trans(inode, trans, 0, 0, cache_size,
2940                                               cache_size, cache_size,
2941                                               &alloc_hint);
2942         /*
2943          * Our cache requires contiguous chunks so that we don't modify a bunch
2944          * of metadata or split extents when writing the cache out, which means
2945          * we can enospc if we are heavily fragmented in addition to just normal
2946          * out of space conditions.  So if we hit this just skip setting up any
2947          * other block groups for this transaction, maybe we'll unpin enough
2948          * space the next time around.
2949          */
2950         if (!ret)
2951                 dcs = BTRFS_DC_SETUP;
2952         else if (ret == -ENOSPC)
2953                 set_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags);
2954
2955 out_put:
2956         iput(inode);
2957 out_free:
2958         btrfs_release_path(path);
2959 out:
2960         spin_lock(&block_group->lock);
2961         if (!ret && dcs == BTRFS_DC_SETUP)
2962                 block_group->cache_generation = trans->transid;
2963         block_group->disk_cache_state = dcs;
2964         spin_unlock(&block_group->lock);
2965
2966         extent_changeset_free(data_reserved);
2967         return ret;
2968 }
2969
2970 int btrfs_setup_space_cache(struct btrfs_trans_handle *trans)
2971 {
2972         struct btrfs_fs_info *fs_info = trans->fs_info;
2973         struct btrfs_block_group *cache, *tmp;
2974         struct btrfs_transaction *cur_trans = trans->transaction;
2975         struct btrfs_path *path;
2976
2977         if (list_empty(&cur_trans->dirty_bgs) ||
2978             !btrfs_test_opt(fs_info, SPACE_CACHE))
2979                 return 0;
2980
2981         path = btrfs_alloc_path();
2982         if (!path)
2983                 return -ENOMEM;
2984
2985         /* Could add new block groups, use _safe just in case */
2986         list_for_each_entry_safe(cache, tmp, &cur_trans->dirty_bgs,
2987                                  dirty_list) {
2988                 if (cache->disk_cache_state == BTRFS_DC_CLEAR)
2989                         cache_save_setup(cache, trans, path);
2990         }
2991
2992         btrfs_free_path(path);
2993         return 0;
2994 }
2995
2996 /*
2997  * Transaction commit does final block group cache writeback during a critical
2998  * section where nothing is allowed to change the FS.  This is required in
2999  * order for the cache to actually match the block group, but can introduce a
3000  * lot of latency into the commit.
3001  *
3002  * So, btrfs_start_dirty_block_groups is here to kick off block group cache IO.
3003  * There's a chance we'll have to redo some of it if the block group changes
3004  * again during the commit, but it greatly reduces the commit latency by
3005  * getting rid of the easy block groups while we're still allowing others to
3006  * join the commit.
3007  */
3008 int btrfs_start_dirty_block_groups(struct btrfs_trans_handle *trans)
3009 {
3010         struct btrfs_fs_info *fs_info = trans->fs_info;
3011         struct btrfs_block_group *cache;
3012         struct btrfs_transaction *cur_trans = trans->transaction;
3013         int ret = 0;
3014         int should_put;
3015         struct btrfs_path *path = NULL;
3016         LIST_HEAD(dirty);
3017         struct list_head *io = &cur_trans->io_bgs;
3018         int loops = 0;
3019
3020         spin_lock(&cur_trans->dirty_bgs_lock);
3021         if (list_empty(&cur_trans->dirty_bgs)) {
3022                 spin_unlock(&cur_trans->dirty_bgs_lock);
3023                 return 0;
3024         }
3025         list_splice_init(&cur_trans->dirty_bgs, &dirty);
3026         spin_unlock(&cur_trans->dirty_bgs_lock);
3027
3028 again:
3029         /* Make sure all the block groups on our dirty list actually exist */
3030         btrfs_create_pending_block_groups(trans);
3031
3032         if (!path) {
3033                 path = btrfs_alloc_path();
3034                 if (!path) {
3035                         ret = -ENOMEM;
3036                         goto out;
3037                 }
3038         }
3039
3040         /*
3041          * cache_write_mutex is here only to save us from balance or automatic
3042          * removal of empty block groups deleting this block group while we are
3043          * writing out the cache
3044          */
3045         mutex_lock(&trans->transaction->cache_write_mutex);
3046         while (!list_empty(&dirty)) {
3047                 bool drop_reserve = true;
3048
3049                 cache = list_first_entry(&dirty, struct btrfs_block_group,
3050                                          dirty_list);
3051                 /*
3052                  * This can happen if something re-dirties a block group that
3053                  * is already under IO.  Just wait for it to finish and then do
3054                  * it all again
3055                  */
3056                 if (!list_empty(&cache->io_list)) {
3057                         list_del_init(&cache->io_list);
3058                         btrfs_wait_cache_io(trans, cache, path);
3059                         btrfs_put_block_group(cache);
3060                 }
3061
3062
3063                 /*
3064                  * btrfs_wait_cache_io uses the cache->dirty_list to decide if
3065                  * it should update the cache_state.  Don't delete until after
3066                  * we wait.
3067                  *
3068                  * Since we're not running in the commit critical section
3069                  * we need the dirty_bgs_lock to protect from update_block_group
3070                  */
3071                 spin_lock(&cur_trans->dirty_bgs_lock);
3072                 list_del_init(&cache->dirty_list);
3073                 spin_unlock(&cur_trans->dirty_bgs_lock);
3074
3075                 should_put = 1;
3076
3077                 cache_save_setup(cache, trans, path);
3078
3079                 if (cache->disk_cache_state == BTRFS_DC_SETUP) {
3080                         cache->io_ctl.inode = NULL;
3081                         ret = btrfs_write_out_cache(trans, cache, path);
3082                         if (ret == 0 && cache->io_ctl.inode) {
3083                                 should_put = 0;
3084
3085                                 /*
3086                                  * The cache_write_mutex is protecting the
3087                                  * io_list, also refer to the definition of
3088                                  * btrfs_transaction::io_bgs for more details
3089                                  */
3090                                 list_add_tail(&cache->io_list, io);
3091                         } else {
3092                                 /*
3093                                  * If we failed to write the cache, the
3094                                  * generation will be bad and life goes on
3095                                  */
3096                                 ret = 0;
3097                         }
3098                 }
3099                 if (!ret) {
3100                         ret = update_block_group_item(trans, path, cache);
3101                         /*
3102                          * Our block group might still be attached to the list
3103                          * of new block groups in the transaction handle of some
3104                          * other task (struct btrfs_trans_handle->new_bgs). This
3105                          * means its block group item isn't yet in the extent
3106                          * tree. If this happens ignore the error, as we will
3107                          * try again later in the critical section of the
3108                          * transaction commit.
3109                          */
3110                         if (ret == -ENOENT) {
3111                                 ret = 0;
3112                                 spin_lock(&cur_trans->dirty_bgs_lock);
3113                                 if (list_empty(&cache->dirty_list)) {
3114                                         list_add_tail(&cache->dirty_list,
3115                                                       &cur_trans->dirty_bgs);
3116                                         btrfs_get_block_group(cache);
3117                                         drop_reserve = false;
3118                                 }
3119                                 spin_unlock(&cur_trans->dirty_bgs_lock);
3120                         } else if (ret) {
3121                                 btrfs_abort_transaction(trans, ret);
3122                         }
3123                 }
3124
3125                 /* If it's not on the io list, we need to put the block group */
3126                 if (should_put)
3127                         btrfs_put_block_group(cache);
3128                 if (drop_reserve)
3129                         btrfs_delayed_refs_rsv_release(fs_info, 1);
3130                 /*
3131                  * Avoid blocking other tasks for too long. It might even save
3132                  * us from writing caches for block groups that are going to be
3133                  * removed.
3134                  */
3135                 mutex_unlock(&trans->transaction->cache_write_mutex);
3136                 if (ret)
3137                         goto out;
3138                 mutex_lock(&trans->transaction->cache_write_mutex);
3139         }
3140         mutex_unlock(&trans->transaction->cache_write_mutex);
3141
3142         /*
3143          * Go through delayed refs for all the stuff we've just kicked off
3144          * and then loop back (just once)
3145          */
3146         if (!ret)
3147                 ret = btrfs_run_delayed_refs(trans, 0);
3148         if (!ret && loops == 0) {
3149                 loops++;
3150                 spin_lock(&cur_trans->dirty_bgs_lock);
3151                 list_splice_init(&cur_trans->dirty_bgs, &dirty);
3152                 /*
3153                  * dirty_bgs_lock protects us from concurrent block group
3154                  * deletes too (not just cache_write_mutex).
3155                  */
3156                 if (!list_empty(&dirty)) {
3157                         spin_unlock(&cur_trans->dirty_bgs_lock);
3158                         goto again;
3159                 }
3160                 spin_unlock(&cur_trans->dirty_bgs_lock);
3161         }
3162 out:
3163         if (ret < 0) {
3164                 spin_lock(&cur_trans->dirty_bgs_lock);
3165                 list_splice_init(&dirty, &cur_trans->dirty_bgs);
3166                 spin_unlock(&cur_trans->dirty_bgs_lock);
3167                 btrfs_cleanup_dirty_bgs(cur_trans, fs_info);
3168         }
3169
3170         btrfs_free_path(path);
3171         return ret;
3172 }
3173
3174 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans)
3175 {
3176         struct btrfs_fs_info *fs_info = trans->fs_info;
3177         struct btrfs_block_group *cache;
3178         struct btrfs_transaction *cur_trans = trans->transaction;
3179         int ret = 0;
3180         int should_put;
3181         struct btrfs_path *path;
3182         struct list_head *io = &cur_trans->io_bgs;
3183
3184         path = btrfs_alloc_path();
3185         if (!path)
3186                 return -ENOMEM;
3187
3188         /*
3189          * Even though we are in the critical section of the transaction commit,
3190          * we can still have concurrent tasks adding elements to this
3191          * transaction's list of dirty block groups. These tasks correspond to
3192          * endio free space workers started when writeback finishes for a
3193          * space cache, which run inode.c:btrfs_finish_ordered_io(), and can
3194          * allocate new block groups as a result of COWing nodes of the root
3195          * tree when updating the free space inode. The writeback for the space
3196          * caches is triggered by an earlier call to
3197          * btrfs_start_dirty_block_groups() and iterations of the following
3198          * loop.
3199          * Also we want to do the cache_save_setup first and then run the
3200          * delayed refs to make sure we have the best chance at doing this all
3201          * in one shot.
3202          */
3203         spin_lock(&cur_trans->dirty_bgs_lock);
3204         while (!list_empty(&cur_trans->dirty_bgs)) {
3205                 cache = list_first_entry(&cur_trans->dirty_bgs,
3206                                          struct btrfs_block_group,
3207                                          dirty_list);
3208
3209                 /*
3210                  * This can happen if cache_save_setup re-dirties a block group
3211                  * that is already under IO.  Just wait for it to finish and
3212                  * then do it all again
3213                  */
3214                 if (!list_empty(&cache->io_list)) {
3215                         spin_unlock(&cur_trans->dirty_bgs_lock);
3216                         list_del_init(&cache->io_list);
3217                         btrfs_wait_cache_io(trans, cache, path);
3218                         btrfs_put_block_group(cache);
3219                         spin_lock(&cur_trans->dirty_bgs_lock);
3220                 }
3221
3222                 /*
3223                  * Don't remove from the dirty list until after we've waited on
3224                  * any pending IO
3225                  */
3226                 list_del_init(&cache->dirty_list);
3227                 spin_unlock(&cur_trans->dirty_bgs_lock);
3228                 should_put = 1;
3229
3230                 cache_save_setup(cache, trans, path);
3231
3232                 if (!ret)
3233                         ret = btrfs_run_delayed_refs(trans,
3234                                                      (unsigned long) -1);
3235
3236                 if (!ret && cache->disk_cache_state == BTRFS_DC_SETUP) {
3237                         cache->io_ctl.inode = NULL;
3238                         ret = btrfs_write_out_cache(trans, cache, path);
3239                         if (ret == 0 && cache->io_ctl.inode) {
3240                                 should_put = 0;
3241                                 list_add_tail(&cache->io_list, io);
3242                         } else {
3243                                 /*
3244                                  * If we failed to write the cache, the
3245                                  * generation will be bad and life goes on
3246                                  */
3247                                 ret = 0;
3248                         }
3249                 }
3250                 if (!ret) {
3251                         ret = update_block_group_item(trans, path, cache);
3252                         /*
3253                          * One of the free space endio workers might have
3254                          * created a new block group while updating a free space
3255                          * cache's inode (at inode.c:btrfs_finish_ordered_io())
3256                          * and hasn't released its transaction handle yet, in
3257                          * which case the new block group is still attached to
3258                          * its transaction handle and its creation has not
3259                          * finished yet (no block group item in the extent tree
3260                          * yet, etc). If this is the case, wait for all free
3261                          * space endio workers to finish and retry. This is a
3262                          * very rare case so no need for a more efficient and
3263                          * complex approach.
3264                          */
3265                         if (ret == -ENOENT) {
3266                                 wait_event(cur_trans->writer_wait,
3267                                    atomic_read(&cur_trans->num_writers) == 1);
3268                                 ret = update_block_group_item(trans, path, cache);
3269                         }
3270                         if (ret)
3271                                 btrfs_abort_transaction(trans, ret);
3272                 }
3273
3274                 /* If its not on the io list, we need to put the block group */
3275                 if (should_put)
3276                         btrfs_put_block_group(cache);
3277                 btrfs_delayed_refs_rsv_release(fs_info, 1);
3278                 spin_lock(&cur_trans->dirty_bgs_lock);
3279         }
3280         spin_unlock(&cur_trans->dirty_bgs_lock);
3281
3282         /*
3283          * Refer to the definition of io_bgs member for details why it's safe
3284          * to use it without any locking
3285          */
3286         while (!list_empty(io)) {
3287                 cache = list_first_entry(io, struct btrfs_block_group,
3288                                          io_list);
3289                 list_del_init(&cache->io_list);
3290                 btrfs_wait_cache_io(trans, cache, path);
3291                 btrfs_put_block_group(cache);
3292         }
3293
3294         btrfs_free_path(path);
3295         return ret;
3296 }
3297
3298 static inline bool should_reclaim_block_group(struct btrfs_block_group *bg,
3299                                               u64 bytes_freed)
3300 {
3301         const struct btrfs_space_info *space_info = bg->space_info;
3302         const int reclaim_thresh = READ_ONCE(space_info->bg_reclaim_threshold);
3303         const u64 new_val = bg->used;
3304         const u64 old_val = new_val + bytes_freed;
3305         u64 thresh;
3306
3307         if (reclaim_thresh == 0)
3308                 return false;
3309
3310         thresh = div_factor_fine(bg->length, reclaim_thresh);
3311
3312         /*
3313          * If we were below the threshold before don't reclaim, we are likely a
3314          * brand new block group and we don't want to relocate new block groups.
3315          */
3316         if (old_val < thresh)
3317                 return false;
3318         if (new_val >= thresh)
3319                 return false;
3320         return true;
3321 }
3322
3323 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
3324                              u64 bytenr, u64 num_bytes, bool alloc)
3325 {
3326         struct btrfs_fs_info *info = trans->fs_info;
3327         struct btrfs_block_group *cache = NULL;
3328         u64 total = num_bytes;
3329         u64 old_val;
3330         u64 byte_in_group;
3331         int factor;
3332         int ret = 0;
3333
3334         /* Block accounting for super block */
3335         spin_lock(&info->delalloc_root_lock);
3336         old_val = btrfs_super_bytes_used(info->super_copy);
3337         if (alloc)
3338                 old_val += num_bytes;
3339         else
3340                 old_val -= num_bytes;
3341         btrfs_set_super_bytes_used(info->super_copy, old_val);
3342         spin_unlock(&info->delalloc_root_lock);
3343
3344         while (total) {
3345                 struct btrfs_space_info *space_info;
3346                 bool reclaim = false;
3347
3348                 cache = btrfs_lookup_block_group(info, bytenr);
3349                 if (!cache) {
3350                         ret = -ENOENT;
3351                         break;
3352                 }
3353                 space_info = cache->space_info;
3354                 factor = btrfs_bg_type_to_factor(cache->flags);
3355
3356                 /*
3357                  * If this block group has free space cache written out, we
3358                  * need to make sure to load it if we are removing space.  This
3359                  * is because we need the unpinning stage to actually add the
3360                  * space back to the block group, otherwise we will leak space.
3361                  */
3362                 if (!alloc && !btrfs_block_group_done(cache))
3363                         btrfs_cache_block_group(cache, true);
3364
3365                 byte_in_group = bytenr - cache->start;
3366                 WARN_ON(byte_in_group > cache->length);
3367
3368                 spin_lock(&space_info->lock);
3369                 spin_lock(&cache->lock);
3370
3371                 if (btrfs_test_opt(info, SPACE_CACHE) &&
3372                     cache->disk_cache_state < BTRFS_DC_CLEAR)
3373                         cache->disk_cache_state = BTRFS_DC_CLEAR;
3374
3375                 old_val = cache->used;
3376                 num_bytes = min(total, cache->length - byte_in_group);
3377                 if (alloc) {
3378                         old_val += num_bytes;
3379                         cache->used = old_val;
3380                         cache->reserved -= num_bytes;
3381                         space_info->bytes_reserved -= num_bytes;
3382                         space_info->bytes_used += num_bytes;
3383                         space_info->disk_used += num_bytes * factor;
3384                         spin_unlock(&cache->lock);
3385                         spin_unlock(&space_info->lock);
3386                 } else {
3387                         old_val -= num_bytes;
3388                         cache->used = old_val;
3389                         cache->pinned += num_bytes;
3390                         btrfs_space_info_update_bytes_pinned(info, space_info,
3391                                                              num_bytes);
3392                         space_info->bytes_used -= num_bytes;
3393                         space_info->disk_used -= num_bytes * factor;
3394
3395                         reclaim = should_reclaim_block_group(cache, num_bytes);
3396                         spin_unlock(&cache->lock);
3397                         spin_unlock(&space_info->lock);
3398
3399                         set_extent_dirty(&trans->transaction->pinned_extents,
3400                                          bytenr, bytenr + num_bytes - 1,
3401                                          GFP_NOFS | __GFP_NOFAIL);
3402                 }
3403
3404                 spin_lock(&trans->transaction->dirty_bgs_lock);
3405                 if (list_empty(&cache->dirty_list)) {
3406                         list_add_tail(&cache->dirty_list,
3407                                       &trans->transaction->dirty_bgs);
3408                         trans->delayed_ref_updates++;
3409                         btrfs_get_block_group(cache);
3410                 }
3411                 spin_unlock(&trans->transaction->dirty_bgs_lock);
3412
3413                 /*
3414                  * No longer have used bytes in this block group, queue it for
3415                  * deletion. We do this after adding the block group to the
3416                  * dirty list to avoid races between cleaner kthread and space
3417                  * cache writeout.
3418                  */
3419                 if (!alloc && old_val == 0) {
3420                         if (!btrfs_test_opt(info, DISCARD_ASYNC))
3421                                 btrfs_mark_bg_unused(cache);
3422                 } else if (!alloc && reclaim) {
3423                         btrfs_mark_bg_to_reclaim(cache);
3424                 }
3425
3426                 btrfs_put_block_group(cache);
3427                 total -= num_bytes;
3428                 bytenr += num_bytes;
3429         }
3430
3431         /* Modified block groups are accounted for in the delayed_refs_rsv. */
3432         btrfs_update_delayed_refs_rsv(trans);
3433         return ret;
3434 }
3435
3436 /**
3437  * btrfs_add_reserved_bytes - update the block_group and space info counters
3438  * @cache:      The cache we are manipulating
3439  * @ram_bytes:  The number of bytes of file content, and will be same to
3440  *              @num_bytes except for the compress path.
3441  * @num_bytes:  The number of bytes in question
3442  * @delalloc:   The blocks are allocated for the delalloc write
3443  *
3444  * This is called by the allocator when it reserves space. If this is a
3445  * reservation and the block group has become read only we cannot make the
3446  * reservation and return -EAGAIN, otherwise this function always succeeds.
3447  */
3448 int btrfs_add_reserved_bytes(struct btrfs_block_group *cache,
3449                              u64 ram_bytes, u64 num_bytes, int delalloc)
3450 {
3451         struct btrfs_space_info *space_info = cache->space_info;
3452         int ret = 0;
3453
3454         spin_lock(&space_info->lock);
3455         spin_lock(&cache->lock);
3456         if (cache->ro) {
3457                 ret = -EAGAIN;
3458         } else {
3459                 cache->reserved += num_bytes;
3460                 space_info->bytes_reserved += num_bytes;
3461                 trace_btrfs_space_reservation(cache->fs_info, "space_info",
3462                                               space_info->flags, num_bytes, 1);
3463                 btrfs_space_info_update_bytes_may_use(cache->fs_info,
3464                                                       space_info, -ram_bytes);
3465                 if (delalloc)
3466                         cache->delalloc_bytes += num_bytes;
3467
3468                 /*
3469                  * Compression can use less space than we reserved, so wake
3470                  * tickets if that happens
3471                  */
3472                 if (num_bytes < ram_bytes)
3473                         btrfs_try_granting_tickets(cache->fs_info, space_info);
3474         }
3475         spin_unlock(&cache->lock);
3476         spin_unlock(&space_info->lock);
3477         return ret;
3478 }
3479
3480 /**
3481  * btrfs_free_reserved_bytes - update the block_group and space info counters
3482  * @cache:      The cache we are manipulating
3483  * @num_bytes:  The number of bytes in question
3484  * @delalloc:   The blocks are allocated for the delalloc write
3485  *
3486  * This is called by somebody who is freeing space that was never actually used
3487  * on disk.  For example if you reserve some space for a new leaf in transaction
3488  * A and before transaction A commits you free that leaf, you call this with
3489  * reserve set to 0 in order to clear the reservation.
3490  */
3491 void btrfs_free_reserved_bytes(struct btrfs_block_group *cache,
3492                                u64 num_bytes, int delalloc)
3493 {
3494         struct btrfs_space_info *space_info = cache->space_info;
3495
3496         spin_lock(&space_info->lock);
3497         spin_lock(&cache->lock);
3498         if (cache->ro)
3499                 space_info->bytes_readonly += num_bytes;
3500         cache->reserved -= num_bytes;
3501         space_info->bytes_reserved -= num_bytes;
3502         space_info->max_extent_size = 0;
3503
3504         if (delalloc)
3505                 cache->delalloc_bytes -= num_bytes;
3506         spin_unlock(&cache->lock);
3507
3508         btrfs_try_granting_tickets(cache->fs_info, space_info);
3509         spin_unlock(&space_info->lock);
3510 }
3511
3512 static void force_metadata_allocation(struct btrfs_fs_info *info)
3513 {
3514         struct list_head *head = &info->space_info;
3515         struct btrfs_space_info *found;
3516
3517         list_for_each_entry(found, head, list) {
3518                 if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
3519                         found->force_alloc = CHUNK_ALLOC_FORCE;
3520         }
3521 }
3522
3523 static int should_alloc_chunk(struct btrfs_fs_info *fs_info,
3524                               struct btrfs_space_info *sinfo, int force)
3525 {
3526         u64 bytes_used = btrfs_space_info_used(sinfo, false);
3527         u64 thresh;
3528
3529         if (force == CHUNK_ALLOC_FORCE)
3530                 return 1;
3531
3532         /*
3533          * in limited mode, we want to have some free space up to
3534          * about 1% of the FS size.
3535          */
3536         if (force == CHUNK_ALLOC_LIMITED) {
3537                 thresh = btrfs_super_total_bytes(fs_info->super_copy);
3538                 thresh = max_t(u64, SZ_64M, div_factor_fine(thresh, 1));
3539
3540                 if (sinfo->total_bytes - bytes_used < thresh)
3541                         return 1;
3542         }
3543
3544         if (bytes_used + SZ_2M < div_factor(sinfo->total_bytes, 8))
3545                 return 0;
3546         return 1;
3547 }
3548
3549 int btrfs_force_chunk_alloc(struct btrfs_trans_handle *trans, u64 type)
3550 {
3551         u64 alloc_flags = btrfs_get_alloc_profile(trans->fs_info, type);
3552
3553         return btrfs_chunk_alloc(trans, alloc_flags, CHUNK_ALLOC_FORCE);
3554 }
3555
3556 static struct btrfs_block_group *do_chunk_alloc(struct btrfs_trans_handle *trans, u64 flags)
3557 {
3558         struct btrfs_block_group *bg;
3559         int ret;
3560
3561         /*
3562          * Check if we have enough space in the system space info because we
3563          * will need to update device items in the chunk btree and insert a new
3564          * chunk item in the chunk btree as well. This will allocate a new
3565          * system block group if needed.
3566          */
3567         check_system_chunk(trans, flags);
3568
3569         bg = btrfs_create_chunk(trans, flags);
3570         if (IS_ERR(bg)) {
3571                 ret = PTR_ERR(bg);
3572                 goto out;
3573         }
3574
3575         ret = btrfs_chunk_alloc_add_chunk_item(trans, bg);
3576         /*
3577          * Normally we are not expected to fail with -ENOSPC here, since we have
3578          * previously reserved space in the system space_info and allocated one
3579          * new system chunk if necessary. However there are three exceptions:
3580          *
3581          * 1) We may have enough free space in the system space_info but all the
3582          *    existing system block groups have a profile which can not be used
3583          *    for extent allocation.
3584          *
3585          *    This happens when mounting in degraded mode. For example we have a
3586          *    RAID1 filesystem with 2 devices, lose one device and mount the fs
3587          *    using the other device in degraded mode. If we then allocate a chunk,
3588          *    we may have enough free space in the existing system space_info, but
3589          *    none of the block groups can be used for extent allocation since they
3590          *    have a RAID1 profile, and because we are in degraded mode with a
3591          *    single device, we are forced to allocate a new system chunk with a
3592          *    SINGLE profile. Making check_system_chunk() iterate over all system
3593          *    block groups and check if they have a usable profile and enough space
3594          *    can be slow on very large filesystems, so we tolerate the -ENOSPC and
3595          *    try again after forcing allocation of a new system chunk. Like this
3596          *    we avoid paying the cost of that search in normal circumstances, when
3597          *    we were not mounted in degraded mode;
3598          *
3599          * 2) We had enough free space info the system space_info, and one suitable
3600          *    block group to allocate from when we called check_system_chunk()
3601          *    above. However right after we called it, the only system block group
3602          *    with enough free space got turned into RO mode by a running scrub,
3603          *    and in this case we have to allocate a new one and retry. We only
3604          *    need do this allocate and retry once, since we have a transaction
3605          *    handle and scrub uses the commit root to search for block groups;
3606          *
3607          * 3) We had one system block group with enough free space when we called
3608          *    check_system_chunk(), but after that, right before we tried to
3609          *    allocate the last extent buffer we needed, a discard operation came
3610          *    in and it temporarily removed the last free space entry from the
3611          *    block group (discard removes a free space entry, discards it, and
3612          *    then adds back the entry to the block group cache).
3613          */
3614         if (ret == -ENOSPC) {
3615                 const u64 sys_flags = btrfs_system_alloc_profile(trans->fs_info);
3616                 struct btrfs_block_group *sys_bg;
3617
3618                 sys_bg = btrfs_create_chunk(trans, sys_flags);
3619                 if (IS_ERR(sys_bg)) {
3620                         ret = PTR_ERR(sys_bg);
3621                         btrfs_abort_transaction(trans, ret);
3622                         goto out;
3623                 }
3624
3625                 ret = btrfs_chunk_alloc_add_chunk_item(trans, sys_bg);
3626                 if (ret) {
3627                         btrfs_abort_transaction(trans, ret);
3628                         goto out;
3629                 }
3630
3631                 ret = btrfs_chunk_alloc_add_chunk_item(trans, bg);
3632                 if (ret) {
3633                         btrfs_abort_transaction(trans, ret);
3634                         goto out;
3635                 }
3636         } else if (ret) {
3637                 btrfs_abort_transaction(trans, ret);
3638                 goto out;
3639         }
3640 out:
3641         btrfs_trans_release_chunk_metadata(trans);
3642
3643         if (ret)
3644                 return ERR_PTR(ret);
3645
3646         btrfs_get_block_group(bg);
3647         return bg;
3648 }
3649
3650 /*
3651  * Chunk allocation is done in 2 phases:
3652  *
3653  * 1) Phase 1 - through btrfs_chunk_alloc() we allocate device extents for
3654  *    the chunk, the chunk mapping, create its block group and add the items
3655  *    that belong in the chunk btree to it - more specifically, we need to
3656  *    update device items in the chunk btree and add a new chunk item to it.
3657  *
3658  * 2) Phase 2 - through btrfs_create_pending_block_groups(), we add the block
3659  *    group item to the extent btree and the device extent items to the devices
3660  *    btree.
3661  *
3662  * This is done to prevent deadlocks. For example when COWing a node from the
3663  * extent btree we are holding a write lock on the node's parent and if we
3664  * trigger chunk allocation and attempted to insert the new block group item
3665  * in the extent btree right way, we could deadlock because the path for the
3666  * insertion can include that parent node. At first glance it seems impossible
3667  * to trigger chunk allocation after starting a transaction since tasks should
3668  * reserve enough transaction units (metadata space), however while that is true
3669  * most of the time, chunk allocation may still be triggered for several reasons:
3670  *
3671  * 1) When reserving metadata, we check if there is enough free space in the
3672  *    metadata space_info and therefore don't trigger allocation of a new chunk.
3673  *    However later when the task actually tries to COW an extent buffer from
3674  *    the extent btree or from the device btree for example, it is forced to
3675  *    allocate a new block group (chunk) because the only one that had enough
3676  *    free space was just turned to RO mode by a running scrub for example (or
3677  *    device replace, block group reclaim thread, etc), so we can not use it
3678  *    for allocating an extent and end up being forced to allocate a new one;
3679  *
3680  * 2) Because we only check that the metadata space_info has enough free bytes,
3681  *    we end up not allocating a new metadata chunk in that case. However if
3682  *    the filesystem was mounted in degraded mode, none of the existing block
3683  *    groups might be suitable for extent allocation due to their incompatible
3684  *    profile (for e.g. mounting a 2 devices filesystem, where all block groups
3685  *    use a RAID1 profile, in degraded mode using a single device). In this case
3686  *    when the task attempts to COW some extent buffer of the extent btree for
3687  *    example, it will trigger allocation of a new metadata block group with a
3688  *    suitable profile (SINGLE profile in the example of the degraded mount of
3689  *    the RAID1 filesystem);
3690  *
3691  * 3) The task has reserved enough transaction units / metadata space, but when
3692  *    it attempts to COW an extent buffer from the extent or device btree for
3693  *    example, it does not find any free extent in any metadata block group,
3694  *    therefore forced to try to allocate a new metadata block group.
3695  *    This is because some other task allocated all available extents in the
3696  *    meanwhile - this typically happens with tasks that don't reserve space
3697  *    properly, either intentionally or as a bug. One example where this is
3698  *    done intentionally is fsync, as it does not reserve any transaction units
3699  *    and ends up allocating a variable number of metadata extents for log
3700  *    tree extent buffers;
3701  *
3702  * 4) The task has reserved enough transaction units / metadata space, but right
3703  *    before it tries to allocate the last extent buffer it needs, a discard
3704  *    operation comes in and, temporarily, removes the last free space entry from
3705  *    the only metadata block group that had free space (discard starts by
3706  *    removing a free space entry from a block group, then does the discard
3707  *    operation and, once it's done, it adds back the free space entry to the
3708  *    block group).
3709  *
3710  * We also need this 2 phases setup when adding a device to a filesystem with
3711  * a seed device - we must create new metadata and system chunks without adding
3712  * any of the block group items to the chunk, extent and device btrees. If we
3713  * did not do it this way, we would get ENOSPC when attempting to update those
3714  * btrees, since all the chunks from the seed device are read-only.
3715  *
3716  * Phase 1 does the updates and insertions to the chunk btree because if we had
3717  * it done in phase 2 and have a thundering herd of tasks allocating chunks in
3718  * parallel, we risk having too many system chunks allocated by many tasks if
3719  * many tasks reach phase 1 without the previous ones completing phase 2. In the
3720  * extreme case this leads to exhaustion of the system chunk array in the
3721  * superblock. This is easier to trigger if using a btree node/leaf size of 64K
3722  * and with RAID filesystems (so we have more device items in the chunk btree).
3723  * This has happened before and commit eafa4fd0ad0607 ("btrfs: fix exhaustion of
3724  * the system chunk array due to concurrent allocations") provides more details.
3725  *
3726  * Allocation of system chunks does not happen through this function. A task that
3727  * needs to update the chunk btree (the only btree that uses system chunks), must
3728  * preallocate chunk space by calling either check_system_chunk() or
3729  * btrfs_reserve_chunk_metadata() - the former is used when allocating a data or
3730  * metadata chunk or when removing a chunk, while the later is used before doing
3731  * a modification to the chunk btree - use cases for the later are adding,
3732  * removing and resizing a device as well as relocation of a system chunk.
3733  * See the comment below for more details.
3734  *
3735  * The reservation of system space, done through check_system_chunk(), as well
3736  * as all the updates and insertions into the chunk btree must be done while
3737  * holding fs_info->chunk_mutex. This is important to guarantee that while COWing
3738  * an extent buffer from the chunks btree we never trigger allocation of a new
3739  * system chunk, which would result in a deadlock (trying to lock twice an
3740  * extent buffer of the chunk btree, first time before triggering the chunk
3741  * allocation and the second time during chunk allocation while attempting to
3742  * update the chunks btree). The system chunk array is also updated while holding
3743  * that mutex. The same logic applies to removing chunks - we must reserve system
3744  * space, update the chunk btree and the system chunk array in the superblock
3745  * while holding fs_info->chunk_mutex.
3746  *
3747  * This function, btrfs_chunk_alloc(), belongs to phase 1.
3748  *
3749  * If @force is CHUNK_ALLOC_FORCE:
3750  *    - return 1 if it successfully allocates a chunk,
3751  *    - return errors including -ENOSPC otherwise.
3752  * If @force is NOT CHUNK_ALLOC_FORCE:
3753  *    - return 0 if it doesn't need to allocate a new chunk,
3754  *    - return 1 if it successfully allocates a chunk,
3755  *    - return errors including -ENOSPC otherwise.
3756  */
3757 int btrfs_chunk_alloc(struct btrfs_trans_handle *trans, u64 flags,
3758                       enum btrfs_chunk_alloc_enum force)
3759 {
3760         struct btrfs_fs_info *fs_info = trans->fs_info;
3761         struct btrfs_space_info *space_info;
3762         struct btrfs_block_group *ret_bg;
3763         bool wait_for_alloc = false;
3764         bool should_alloc = false;
3765         bool from_extent_allocation = false;
3766         int ret = 0;
3767
3768         if (force == CHUNK_ALLOC_FORCE_FOR_EXTENT) {
3769                 from_extent_allocation = true;
3770                 force = CHUNK_ALLOC_FORCE;
3771         }
3772
3773         /* Don't re-enter if we're already allocating a chunk */
3774         if (trans->allocating_chunk)
3775                 return -ENOSPC;
3776         /*
3777          * Allocation of system chunks can not happen through this path, as we
3778          * could end up in a deadlock if we are allocating a data or metadata
3779          * chunk and there is another task modifying the chunk btree.
3780          *
3781          * This is because while we are holding the chunk mutex, we will attempt
3782          * to add the new chunk item to the chunk btree or update an existing
3783          * device item in the chunk btree, while the other task that is modifying
3784          * the chunk btree is attempting to COW an extent buffer while holding a
3785          * lock on it and on its parent - if the COW operation triggers a system
3786          * chunk allocation, then we can deadlock because we are holding the
3787          * chunk mutex and we may need to access that extent buffer or its parent
3788          * in order to add the chunk item or update a device item.
3789          *
3790          * Tasks that want to modify the chunk tree should reserve system space
3791          * before updating the chunk btree, by calling either
3792          * btrfs_reserve_chunk_metadata() or check_system_chunk().
3793          * It's possible that after a task reserves the space, it still ends up
3794          * here - this happens in the cases described above at do_chunk_alloc().
3795          * The task will have to either retry or fail.
3796          */
3797         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
3798                 return -ENOSPC;
3799
3800         space_info = btrfs_find_space_info(fs_info, flags);
3801         ASSERT(space_info);
3802
3803         do {
3804                 spin_lock(&space_info->lock);
3805                 if (force < space_info->force_alloc)
3806                         force = space_info->force_alloc;
3807                 should_alloc = should_alloc_chunk(fs_info, space_info, force);
3808                 if (space_info->full) {
3809                         /* No more free physical space */
3810                         if (should_alloc)
3811                                 ret = -ENOSPC;
3812                         else
3813                                 ret = 0;
3814                         spin_unlock(&space_info->lock);
3815                         return ret;
3816                 } else if (!should_alloc) {
3817                         spin_unlock(&space_info->lock);
3818                         return 0;
3819                 } else if (space_info->chunk_alloc) {
3820                         /*
3821                          * Someone is already allocating, so we need to block
3822                          * until this someone is finished and then loop to
3823                          * recheck if we should continue with our allocation
3824                          * attempt.
3825                          */
3826                         wait_for_alloc = true;
3827                         force = CHUNK_ALLOC_NO_FORCE;
3828                         spin_unlock(&space_info->lock);
3829                         mutex_lock(&fs_info->chunk_mutex);
3830                         mutex_unlock(&fs_info->chunk_mutex);
3831                 } else {
3832                         /* Proceed with allocation */
3833                         space_info->chunk_alloc = 1;
3834                         wait_for_alloc = false;
3835                         spin_unlock(&space_info->lock);
3836                 }
3837
3838                 cond_resched();
3839         } while (wait_for_alloc);
3840
3841         mutex_lock(&fs_info->chunk_mutex);
3842         trans->allocating_chunk = true;
3843
3844         /*
3845          * If we have mixed data/metadata chunks we want to make sure we keep
3846          * allocating mixed chunks instead of individual chunks.
3847          */
3848         if (btrfs_mixed_space_info(space_info))
3849                 flags |= (BTRFS_BLOCK_GROUP_DATA | BTRFS_BLOCK_GROUP_METADATA);
3850
3851         /*
3852          * if we're doing a data chunk, go ahead and make sure that
3853          * we keep a reasonable number of metadata chunks allocated in the
3854          * FS as well.
3855          */
3856         if (flags & BTRFS_BLOCK_GROUP_DATA && fs_info->metadata_ratio) {
3857                 fs_info->data_chunk_allocations++;
3858                 if (!(fs_info->data_chunk_allocations %
3859                       fs_info->metadata_ratio))
3860                         force_metadata_allocation(fs_info);
3861         }
3862
3863         ret_bg = do_chunk_alloc(trans, flags);
3864         trans->allocating_chunk = false;
3865
3866         if (IS_ERR(ret_bg)) {
3867                 ret = PTR_ERR(ret_bg);
3868         } else if (from_extent_allocation) {
3869                 /*
3870                  * New block group is likely to be used soon. Try to activate
3871                  * it now. Failure is OK for now.
3872                  */
3873                 btrfs_zone_activate(ret_bg);
3874         }
3875
3876         if (!ret)
3877                 btrfs_put_block_group(ret_bg);
3878
3879         spin_lock(&space_info->lock);
3880         if (ret < 0) {
3881                 if (ret == -ENOSPC)
3882                         space_info->full = 1;
3883                 else
3884                         goto out;
3885         } else {
3886                 ret = 1;
3887                 space_info->max_extent_size = 0;
3888         }
3889
3890         space_info->force_alloc = CHUNK_ALLOC_NO_FORCE;
3891 out:
3892         space_info->chunk_alloc = 0;
3893         spin_unlock(&space_info->lock);
3894         mutex_unlock(&fs_info->chunk_mutex);
3895
3896         return ret;
3897 }
3898
3899 static u64 get_profile_num_devs(struct btrfs_fs_info *fs_info, u64 type)
3900 {
3901         u64 num_dev;
3902
3903         num_dev = btrfs_raid_array[btrfs_bg_flags_to_raid_index(type)].devs_max;
3904         if (!num_dev)
3905                 num_dev = fs_info->fs_devices->rw_devices;
3906
3907         return num_dev;
3908 }
3909
3910 static void reserve_chunk_space(struct btrfs_trans_handle *trans,
3911                                 u64 bytes,
3912                                 u64 type)
3913 {
3914         struct btrfs_fs_info *fs_info = trans->fs_info;
3915         struct btrfs_space_info *info;
3916         u64 left;
3917         int ret = 0;
3918
3919         /*
3920          * Needed because we can end up allocating a system chunk and for an
3921          * atomic and race free space reservation in the chunk block reserve.
3922          */
3923         lockdep_assert_held(&fs_info->chunk_mutex);
3924
3925         info = btrfs_find_space_info(fs_info, BTRFS_BLOCK_GROUP_SYSTEM);
3926         spin_lock(&info->lock);
3927         left = info->total_bytes - btrfs_space_info_used(info, true);
3928         spin_unlock(&info->lock);
3929
3930         if (left < bytes && btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
3931                 btrfs_info(fs_info, "left=%llu, need=%llu, flags=%llu",
3932                            left, bytes, type);
3933                 btrfs_dump_space_info(fs_info, info, 0, 0);
3934         }
3935
3936         if (left < bytes) {
3937                 u64 flags = btrfs_system_alloc_profile(fs_info);
3938                 struct btrfs_block_group *bg;
3939
3940                 /*
3941                  * Ignore failure to create system chunk. We might end up not
3942                  * needing it, as we might not need to COW all nodes/leafs from
3943                  * the paths we visit in the chunk tree (they were already COWed
3944                  * or created in the current transaction for example).
3945                  */
3946                 bg = btrfs_create_chunk(trans, flags);
3947                 if (IS_ERR(bg)) {
3948                         ret = PTR_ERR(bg);
3949                 } else {
3950                         /*
3951                          * We have a new chunk. We also need to activate it for
3952                          * zoned filesystem.
3953                          */
3954                         ret = btrfs_zoned_activate_one_bg(fs_info, info, true);
3955                         if (ret < 0)
3956                                 return;
3957
3958                         /*
3959                          * If we fail to add the chunk item here, we end up
3960                          * trying again at phase 2 of chunk allocation, at
3961                          * btrfs_create_pending_block_groups(). So ignore
3962                          * any error here. An ENOSPC here could happen, due to
3963                          * the cases described at do_chunk_alloc() - the system
3964                          * block group we just created was just turned into RO
3965                          * mode by a scrub for example, or a running discard
3966                          * temporarily removed its free space entries, etc.
3967                          */
3968                         btrfs_chunk_alloc_add_chunk_item(trans, bg);
3969                 }
3970         }
3971
3972         if (!ret) {
3973                 ret = btrfs_block_rsv_add(fs_info,
3974                                           &fs_info->chunk_block_rsv,
3975                                           bytes, BTRFS_RESERVE_NO_FLUSH);
3976                 if (!ret)
3977                         trans->chunk_bytes_reserved += bytes;
3978         }
3979 }
3980
3981 /*
3982  * Reserve space in the system space for allocating or removing a chunk.
3983  * The caller must be holding fs_info->chunk_mutex.
3984  */
3985 void check_system_chunk(struct btrfs_trans_handle *trans, u64 type)
3986 {
3987         struct btrfs_fs_info *fs_info = trans->fs_info;
3988         const u64 num_devs = get_profile_num_devs(fs_info, type);
3989         u64 bytes;
3990
3991         /* num_devs device items to update and 1 chunk item to add or remove. */
3992         bytes = btrfs_calc_metadata_size(fs_info, num_devs) +
3993                 btrfs_calc_insert_metadata_size(fs_info, 1);
3994
3995         reserve_chunk_space(trans, bytes, type);
3996 }
3997
3998 /*
3999  * Reserve space in the system space, if needed, for doing a modification to the
4000  * chunk btree.
4001  *
4002  * @trans:              A transaction handle.
4003  * @is_item_insertion:  Indicate if the modification is for inserting a new item
4004  *                      in the chunk btree or if it's for the deletion or update
4005  *                      of an existing item.
4006  *
4007  * This is used in a context where we need to update the chunk btree outside
4008  * block group allocation and removal, to avoid a deadlock with a concurrent
4009  * task that is allocating a metadata or data block group and therefore needs to
4010  * update the chunk btree while holding the chunk mutex. After the update to the
4011  * chunk btree is done, btrfs_trans_release_chunk_metadata() should be called.
4012  *
4013  */
4014 void btrfs_reserve_chunk_metadata(struct btrfs_trans_handle *trans,
4015                                   bool is_item_insertion)
4016 {
4017         struct btrfs_fs_info *fs_info = trans->fs_info;
4018         u64 bytes;
4019
4020         if (is_item_insertion)
4021                 bytes = btrfs_calc_insert_metadata_size(fs_info, 1);
4022         else
4023                 bytes = btrfs_calc_metadata_size(fs_info, 1);
4024
4025         mutex_lock(&fs_info->chunk_mutex);
4026         reserve_chunk_space(trans, bytes, BTRFS_BLOCK_GROUP_SYSTEM);
4027         mutex_unlock(&fs_info->chunk_mutex);
4028 }
4029
4030 void btrfs_put_block_group_cache(struct btrfs_fs_info *info)
4031 {
4032         struct btrfs_block_group *block_group;
4033
4034         block_group = btrfs_lookup_first_block_group(info, 0);
4035         while (block_group) {
4036                 btrfs_wait_block_group_cache_done(block_group);
4037                 spin_lock(&block_group->lock);
4038                 if (test_and_clear_bit(BLOCK_GROUP_FLAG_IREF,
4039                                        &block_group->runtime_flags)) {
4040                         struct inode *inode = block_group->inode;
4041
4042                         block_group->inode = NULL;
4043                         spin_unlock(&block_group->lock);
4044
4045                         ASSERT(block_group->io_ctl.inode == NULL);
4046                         iput(inode);
4047                 } else {
4048                         spin_unlock(&block_group->lock);
4049                 }
4050                 block_group = btrfs_next_block_group(block_group);
4051         }
4052 }
4053
4054 /*
4055  * Must be called only after stopping all workers, since we could have block
4056  * group caching kthreads running, and therefore they could race with us if we
4057  * freed the block groups before stopping them.
4058  */
4059 int btrfs_free_block_groups(struct btrfs_fs_info *info)
4060 {
4061         struct btrfs_block_group *block_group;
4062         struct btrfs_space_info *space_info;
4063         struct btrfs_caching_control *caching_ctl;
4064         struct rb_node *n;
4065
4066         write_lock(&info->block_group_cache_lock);
4067         while (!list_empty(&info->caching_block_groups)) {
4068                 caching_ctl = list_entry(info->caching_block_groups.next,
4069                                          struct btrfs_caching_control, list);
4070                 list_del(&caching_ctl->list);
4071                 btrfs_put_caching_control(caching_ctl);
4072         }
4073         write_unlock(&info->block_group_cache_lock);
4074
4075         spin_lock(&info->unused_bgs_lock);
4076         while (!list_empty(&info->unused_bgs)) {
4077                 block_group = list_first_entry(&info->unused_bgs,
4078                                                struct btrfs_block_group,
4079                                                bg_list);
4080                 list_del_init(&block_group->bg_list);
4081                 btrfs_put_block_group(block_group);
4082         }
4083
4084         while (!list_empty(&info->reclaim_bgs)) {
4085                 block_group = list_first_entry(&info->reclaim_bgs,
4086                                                struct btrfs_block_group,
4087                                                bg_list);
4088                 list_del_init(&block_group->bg_list);
4089                 btrfs_put_block_group(block_group);
4090         }
4091         spin_unlock(&info->unused_bgs_lock);
4092
4093         spin_lock(&info->zone_active_bgs_lock);
4094         while (!list_empty(&info->zone_active_bgs)) {
4095                 block_group = list_first_entry(&info->zone_active_bgs,
4096                                                struct btrfs_block_group,
4097                                                active_bg_list);
4098                 list_del_init(&block_group->active_bg_list);
4099                 btrfs_put_block_group(block_group);
4100         }
4101         spin_unlock(&info->zone_active_bgs_lock);
4102
4103         write_lock(&info->block_group_cache_lock);
4104         while ((n = rb_last(&info->block_group_cache_tree.rb_root)) != NULL) {
4105                 block_group = rb_entry(n, struct btrfs_block_group,
4106                                        cache_node);
4107                 rb_erase_cached(&block_group->cache_node,
4108                                 &info->block_group_cache_tree);
4109                 RB_CLEAR_NODE(&block_group->cache_node);
4110                 write_unlock(&info->block_group_cache_lock);
4111
4112                 down_write(&block_group->space_info->groups_sem);
4113                 list_del(&block_group->list);
4114                 up_write(&block_group->space_info->groups_sem);
4115
4116                 /*
4117                  * We haven't cached this block group, which means we could
4118                  * possibly have excluded extents on this block group.
4119                  */
4120                 if (block_group->cached == BTRFS_CACHE_NO ||
4121                     block_group->cached == BTRFS_CACHE_ERROR)
4122                         btrfs_free_excluded_extents(block_group);
4123
4124                 btrfs_remove_free_space_cache(block_group);
4125                 ASSERT(block_group->cached != BTRFS_CACHE_STARTED);
4126                 ASSERT(list_empty(&block_group->dirty_list));
4127                 ASSERT(list_empty(&block_group->io_list));
4128                 ASSERT(list_empty(&block_group->bg_list));
4129                 ASSERT(refcount_read(&block_group->refs) == 1);
4130                 ASSERT(block_group->swap_extents == 0);
4131                 btrfs_put_block_group(block_group);
4132
4133                 write_lock(&info->block_group_cache_lock);
4134         }
4135         write_unlock(&info->block_group_cache_lock);
4136
4137         btrfs_release_global_block_rsv(info);
4138
4139         while (!list_empty(&info->space_info)) {
4140                 space_info = list_entry(info->space_info.next,
4141                                         struct btrfs_space_info,
4142                                         list);
4143
4144                 /*
4145                  * Do not hide this behind enospc_debug, this is actually
4146                  * important and indicates a real bug if this happens.
4147                  */
4148                 if (WARN_ON(space_info->bytes_pinned > 0 ||
4149                             space_info->bytes_may_use > 0))
4150                         btrfs_dump_space_info(info, space_info, 0, 0);
4151
4152                 /*
4153                  * If there was a failure to cleanup a log tree, very likely due
4154                  * to an IO failure on a writeback attempt of one or more of its
4155                  * extent buffers, we could not do proper (and cheap) unaccounting
4156                  * of their reserved space, so don't warn on bytes_reserved > 0 in
4157                  * that case.
4158                  */
4159                 if (!(space_info->flags & BTRFS_BLOCK_GROUP_METADATA) ||
4160                     !BTRFS_FS_LOG_CLEANUP_ERROR(info)) {
4161                         if (WARN_ON(space_info->bytes_reserved > 0))
4162                                 btrfs_dump_space_info(info, space_info, 0, 0);
4163                 }
4164
4165                 WARN_ON(space_info->reclaim_size > 0);
4166                 list_del(&space_info->list);
4167                 btrfs_sysfs_remove_space_info(space_info);
4168         }
4169         return 0;
4170 }
4171
4172 void btrfs_freeze_block_group(struct btrfs_block_group *cache)
4173 {
4174         atomic_inc(&cache->frozen);
4175 }
4176
4177 void btrfs_unfreeze_block_group(struct btrfs_block_group *block_group)
4178 {
4179         struct btrfs_fs_info *fs_info = block_group->fs_info;
4180         struct extent_map_tree *em_tree;
4181         struct extent_map *em;
4182         bool cleanup;
4183
4184         spin_lock(&block_group->lock);
4185         cleanup = (atomic_dec_and_test(&block_group->frozen) &&
4186                    test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags));
4187         spin_unlock(&block_group->lock);
4188
4189         if (cleanup) {
4190                 em_tree = &fs_info->mapping_tree;
4191                 write_lock(&em_tree->lock);
4192                 em = lookup_extent_mapping(em_tree, block_group->start,
4193                                            1);
4194                 BUG_ON(!em); /* logic error, can't happen */
4195                 remove_extent_mapping(em_tree, em);
4196                 write_unlock(&em_tree->lock);
4197
4198                 /* once for us and once for the tree */
4199                 free_extent_map(em);
4200                 free_extent_map(em);
4201
4202                 /*
4203                  * We may have left one free space entry and other possible
4204                  * tasks trimming this block group have left 1 entry each one.
4205                  * Free them if any.
4206                  */
4207                 btrfs_remove_free_space_cache(block_group);
4208         }
4209 }
4210
4211 bool btrfs_inc_block_group_swap_extents(struct btrfs_block_group *bg)
4212 {
4213         bool ret = true;
4214
4215         spin_lock(&bg->lock);
4216         if (bg->ro)
4217                 ret = false;
4218         else
4219                 bg->swap_extents++;
4220         spin_unlock(&bg->lock);
4221
4222         return ret;
4223 }
4224
4225 void btrfs_dec_block_group_swap_extents(struct btrfs_block_group *bg, int amount)
4226 {
4227         spin_lock(&bg->lock);
4228         ASSERT(!bg->ro);
4229         ASSERT(bg->swap_extents >= amount);
4230         bg->swap_extents -= amount;
4231         spin_unlock(&bg->lock);
4232 }