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