fs/btrfs/block-group.c

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