fs/btrfs/block-rsv.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "misc.h"
   4 #include "ctree.h"
   5 #include "block-rsv.h"
   6 #include "space-info.h"
   7 #include "transaction.h"
   8 #include "block-group.h"
   9 #include "disk-io.h"
  10
  11 /*
  12  * HOW DO BLOCK RESERVES WORK
  13  *
  14  *   Think of block_rsv's as buckets for logically grouped metadata
  15  *   reservations.  Each block_rsv has a ->size and a ->reserved.  ->size is
  16  *   how large we want our block rsv to be, ->reserved is how much space is
  17  *   currently reserved for this block reserve.
  18  *
  19  *   ->failfast exists for the truncate case, and is described below.
  20  *
  21  * NORMAL OPERATION
  22  *
  23  *   -> Reserve
  24  *     Entrance: btrfs_block_rsv_add, btrfs_block_rsv_refill
  25  *
  26  *     We call into btrfs_reserve_metadata_bytes() with our bytes, which is
  27  *     accounted for in space_info->bytes_may_use, and then add the bytes to
  28  *     ->reserved, and ->size in the case of btrfs_block_rsv_add.
  29  *
  30  *     ->size is an over-estimation of how much we may use for a particular
  31  *     operation.
  32  *
  33  *   -> Use
  34  *     Entrance: btrfs_use_block_rsv
  35  *
  36  *     When we do a btrfs_alloc_tree_block() we call into btrfs_use_block_rsv()
  37  *     to determine the appropriate block_rsv to use, and then verify that
  38  *     ->reserved has enough space for our tree block allocation.  Once
  39  *     successful we subtract fs_info->nodesize from ->reserved.
  40  *
  41  *   -> Finish
  42  *     Entrance: btrfs_block_rsv_release
  43  *
  44  *     We are finished with our operation, subtract our individual reservation
  45  *     from ->size, and then subtract ->size from ->reserved and free up the
  46  *     excess if there is any.
  47  *
  48  *     There is some logic here to refill the delayed refs rsv or the global rsv
  49  *     as needed, otherwise the excess is subtracted from
  50  *     space_info->bytes_may_use.
  51  *
  52  * TYPES OF BLOCK RESERVES
  53  *
  54  * BLOCK_RSV_TRANS, BLOCK_RSV_DELOPS, BLOCK_RSV_CHUNK
  55  *   These behave normally, as described above, just within the confines of the
  56  *   lifetime of their particular operation (transaction for the whole trans
  57  *   handle lifetime, for example).
  58  *
  59  * BLOCK_RSV_GLOBAL
  60  *   It is impossible to properly account for all the space that may be required
  61  *   to make our extent tree updates.  This block reserve acts as an overflow
  62  *   buffer in case our delayed refs reserve does not reserve enough space to
  63  *   update the extent tree.
  64  *
  65  *   We can steal from this in some cases as well, notably on evict() or
  66  *   truncate() in order to help users recover from ENOSPC conditions.
  67  *
  68  * BLOCK_RSV_DELALLOC
  69  *   The individual item sizes are determined by the per-inode size
  70  *   calculations, which are described with the delalloc code.  This is pretty
  71  *   straightforward, it's just the calculation of ->size encodes a lot of
  72  *   different items, and thus it gets used when updating inodes, inserting file
  73  *   extents, and inserting checksums.
  74  *
  75  * BLOCK_RSV_DELREFS
  76  *   We keep a running tally of how many delayed refs we have on the system.
  77  *   We assume each one of these delayed refs are going to use a full
  78  *   reservation.  We use the transaction items and pre-reserve space for every
  79  *   operation, and use this reservation to refill any gap between ->size and
  80  *   ->reserved that may exist.
  81  *
  82  *   From there it's straightforward, removing a delayed ref means we remove its
  83  *   count from ->size and free up reservations as necessary.  Since this is
  84  *   the most dynamic block reserve in the system, we will try to refill this
  85  *   block reserve first with any excess returned by any other block reserve.
  86  *
  87  * BLOCK_RSV_EMPTY
  88  *   This is the fallback block reserve to make us try to reserve space if we
  89  *   don't have a specific bucket for this allocation.  It is mostly used for
  90  *   updating the device tree and such, since that is a separate pool we're
  91  *   content to just reserve space from the space_info on demand.
  92  *
  93  * BLOCK_RSV_TEMP
  94  *   This is used by things like truncate and iput.  We will temporarily
  95  *   allocate a block reserve, set it to some size, and then truncate bytes
  96  *   until we have no space left.  With ->failfast set we'll simply return
  97  *   ENOSPC from btrfs_use_block_rsv() to signal that we need to unwind and try
  98  *   to make a new reservation.  This is because these operations are
  99  *   unbounded, so we want to do as much work as we can, and then back off and
 100  *   re-reserve.
 101  */
 102
 103 static u64 block_rsv_release_bytes(struct btrfs_fs_info *fs_info,
 104                                     struct btrfs_block_rsv *block_rsv,
 105                                     struct btrfs_block_rsv *dest, u64 num_bytes,
 106                                     u64 *qgroup_to_release_ret)
 107 {
 108         struct btrfs_space_info *space_info = block_rsv->space_info;
 109         u64 qgroup_to_release = 0;
 110         u64 ret;
 111
 112         spin_lock(&block_rsv->lock);
 113         if (num_bytes == (u64)-1) {
 114                 num_bytes = block_rsv->size;
 115                 qgroup_to_release = block_rsv->qgroup_rsv_size;
 116         }
 117         block_rsv->size -= num_bytes;
 118         if (block_rsv->reserved >= block_rsv->size) {
 119                 num_bytes = block_rsv->reserved - block_rsv->size;
 120                 block_rsv->reserved = block_rsv->size;
 121                 block_rsv->full = true;
 122         } else {
 123                 num_bytes = 0;
 124         }
 125         if (qgroup_to_release_ret &&
 126             block_rsv->qgroup_rsv_reserved >= block_rsv->qgroup_rsv_size) {
 127                 qgroup_to_release = block_rsv->qgroup_rsv_reserved -
 128                                     block_rsv->qgroup_rsv_size;
 129                 block_rsv->qgroup_rsv_reserved = block_rsv->qgroup_rsv_size;
 130         } else {
 131                 qgroup_to_release = 0;
 132         }
 133         spin_unlock(&block_rsv->lock);
 134
 135         ret = num_bytes;
 136         if (num_bytes > 0) {
 137                 if (dest) {
 138                         spin_lock(&dest->lock);
 139                         if (!dest->full) {
 140                                 u64 bytes_to_add;
 141
 142                                 bytes_to_add = dest->size - dest->reserved;
 143                                 bytes_to_add = min(num_bytes, bytes_to_add);
 144                                 dest->reserved += bytes_to_add;
 145                                 if (dest->reserved >= dest->size)
 146                                         dest->full = true;
 147                                 num_bytes -= bytes_to_add;
 148                         }
 149                         spin_unlock(&dest->lock);
 150                 }
 151                 if (num_bytes)
 152                         btrfs_space_info_free_bytes_may_use(fs_info,
 153                                                             space_info,
 154                                                             num_bytes);
 155         }
 156         if (qgroup_to_release_ret)
 157                 *qgroup_to_release_ret = qgroup_to_release;
 158         return ret;
 159 }
 160
 161 int btrfs_block_rsv_migrate(struct btrfs_block_rsv *src,
 162                             struct btrfs_block_rsv *dst, u64 num_bytes,
 163                             bool update_size)
 164 {
 165         int ret;
 166
 167         ret = btrfs_block_rsv_use_bytes(src, num_bytes);
 168         if (ret)
 169                 return ret;
 170
 171         btrfs_block_rsv_add_bytes(dst, num_bytes, update_size);
 172         return 0;
 173 }
 174
 175 void btrfs_init_block_rsv(struct btrfs_block_rsv *rsv, enum btrfs_rsv_type type)
 176 {
 177         memset(rsv, 0, sizeof(*rsv));
 178         spin_lock_init(&rsv->lock);
 179         rsv->type = type;
 180 }
 181
 182 void btrfs_init_metadata_block_rsv(struct btrfs_fs_info *fs_info,
 183                                    struct btrfs_block_rsv *rsv,
 184                                    enum btrfs_rsv_type type)
 185 {
 186         btrfs_init_block_rsv(rsv, type);
 187         rsv->space_info = btrfs_find_space_info(fs_info,
 188                                             BTRFS_BLOCK_GROUP_METADATA);
 189 }
 190
 191 struct btrfs_block_rsv *btrfs_alloc_block_rsv(struct btrfs_fs_info *fs_info,
 192                                               enum btrfs_rsv_type type)
 193 {
 194         struct btrfs_block_rsv *block_rsv;
 195
 196         block_rsv = kmalloc(sizeof(*block_rsv), GFP_NOFS);
 197         if (!block_rsv)
 198                 return NULL;
 199
 200         btrfs_init_metadata_block_rsv(fs_info, block_rsv, type);
 201         return block_rsv;
 202 }
 203
 204 void btrfs_free_block_rsv(struct btrfs_fs_info *fs_info,
 205                           struct btrfs_block_rsv *rsv)
 206 {
 207         if (!rsv)
 208                 return;
 209         btrfs_block_rsv_release(fs_info, rsv, (u64)-1, NULL);
 210         kfree(rsv);
 211 }
 212
 213 int btrfs_block_rsv_add(struct btrfs_fs_info *fs_info,
 214                         struct btrfs_block_rsv *block_rsv, u64 num_bytes,
 215                         enum btrfs_reserve_flush_enum flush)
 216 {
 217         int ret;
 218
 219         if (num_bytes == 0)
 220                 return 0;
 221
 222         ret = btrfs_reserve_metadata_bytes(fs_info, block_rsv, num_bytes, flush);
 223         if (!ret)
 224                 btrfs_block_rsv_add_bytes(block_rsv, num_bytes, true);
 225
 226         return ret;
 227 }
 228
 229 int btrfs_block_rsv_check(struct btrfs_block_rsv *block_rsv, int min_factor)
 230 {
 231         u64 num_bytes = 0;
 232         int ret = -ENOSPC;
 233
 234         if (!block_rsv)
 235                 return 0;
 236
 237         spin_lock(&block_rsv->lock);
 238         num_bytes = div_factor(block_rsv->size, min_factor);
 239         if (block_rsv->reserved >= num_bytes)
 240                 ret = 0;
 241         spin_unlock(&block_rsv->lock);
 242
 243         return ret;
 244 }
 245
 246 int btrfs_block_rsv_refill(struct btrfs_fs_info *fs_info,
 247                            struct btrfs_block_rsv *block_rsv, u64 min_reserved,
 248                            enum btrfs_reserve_flush_enum flush)
 249 {
 250         u64 num_bytes = 0;
 251         int ret = -ENOSPC;
 252
 253         if (!block_rsv)
 254                 return 0;
 255
 256         spin_lock(&block_rsv->lock);
 257         num_bytes = min_reserved;
 258         if (block_rsv->reserved >= num_bytes)
 259                 ret = 0;
 260         else
 261                 num_bytes -= block_rsv->reserved;
 262         spin_unlock(&block_rsv->lock);
 263
 264         if (!ret)
 265                 return 0;
 266
 267         ret = btrfs_reserve_metadata_bytes(fs_info, block_rsv, num_bytes, flush);
 268         if (!ret) {
 269                 btrfs_block_rsv_add_bytes(block_rsv, num_bytes, false);
 270                 return 0;
 271         }
 272
 273         return ret;
 274 }
 275
 276 u64 btrfs_block_rsv_release(struct btrfs_fs_info *fs_info,
 277                             struct btrfs_block_rsv *block_rsv, u64 num_bytes,
 278                             u64 *qgroup_to_release)
 279 {
 280         struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
 281         struct btrfs_block_rsv *delayed_rsv = &fs_info->delayed_refs_rsv;
 282         struct btrfs_block_rsv *target = NULL;
 283
 284         /*
 285          * If we are the delayed_rsv then push to the global rsv, otherwise dump
 286          * into the delayed rsv if it is not full.
 287          */
 288         if (block_rsv == delayed_rsv)
 289                 target = global_rsv;
 290         else if (block_rsv != global_rsv && !btrfs_block_rsv_full(delayed_rsv))
 291                 target = delayed_rsv;
 292
 293         if (target && block_rsv->space_info != target->space_info)
 294                 target = NULL;
 295
 296         return block_rsv_release_bytes(fs_info, block_rsv, target, num_bytes,
 297                                        qgroup_to_release);
 298 }
 299
 300 int btrfs_block_rsv_use_bytes(struct btrfs_block_rsv *block_rsv, u64 num_bytes)
 301 {
 302         int ret = -ENOSPC;
 303
 304         spin_lock(&block_rsv->lock);
 305         if (block_rsv->reserved >= num_bytes) {
 306                 block_rsv->reserved -= num_bytes;
 307                 if (block_rsv->reserved < block_rsv->size)
 308                         block_rsv->full = false;
 309                 ret = 0;
 310         }
 311         spin_unlock(&block_rsv->lock);
 312         return ret;
 313 }
 314
 315 void btrfs_block_rsv_add_bytes(struct btrfs_block_rsv *block_rsv,
 316                                u64 num_bytes, bool update_size)
 317 {
 318         spin_lock(&block_rsv->lock);
 319         block_rsv->reserved += num_bytes;
 320         if (update_size)
 321                 block_rsv->size += num_bytes;
 322         else if (block_rsv->reserved >= block_rsv->size)
 323                 block_rsv->full = true;
 324         spin_unlock(&block_rsv->lock);
 325 }
 326
 327 int btrfs_cond_migrate_bytes(struct btrfs_fs_info *fs_info,
 328                              struct btrfs_block_rsv *dest, u64 num_bytes,
 329                              int min_factor)
 330 {
 331         struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
 332         u64 min_bytes;
 333
 334         if (global_rsv->space_info != dest->space_info)
 335                 return -ENOSPC;
 336
 337         spin_lock(&global_rsv->lock);
 338         min_bytes = div_factor(global_rsv->size, min_factor);
 339         if (global_rsv->reserved < min_bytes + num_bytes) {
 340                 spin_unlock(&global_rsv->lock);
 341                 return -ENOSPC;
 342         }
 343         global_rsv->reserved -= num_bytes;
 344         if (global_rsv->reserved < global_rsv->size)
 345                 global_rsv->full = false;
 346         spin_unlock(&global_rsv->lock);
 347
 348         btrfs_block_rsv_add_bytes(dest, num_bytes, true);
 349         return 0;
 350 }
 351
 352 void btrfs_update_global_block_rsv(struct btrfs_fs_info *fs_info)
 353 {
 354         struct btrfs_block_rsv *block_rsv = &fs_info->global_block_rsv;
 355         struct btrfs_space_info *sinfo = block_rsv->space_info;
 356         struct btrfs_root *root, *tmp;
 357         u64 num_bytes = btrfs_root_used(&fs_info->tree_root->root_item);
 358         unsigned int min_items = 1;
 359
 360         /*
 361          * The global block rsv is based on the size of the extent tree, the
 362          * checksum tree and the root tree.  If the fs is empty we want to set
 363          * it to a minimal amount for safety.
 364          *
 365          * We also are going to need to modify the minimum of the tree root and
 366          * any global roots we could touch.
 367          */
 368         read_lock(&fs_info->global_root_lock);
 369         rbtree_postorder_for_each_entry_safe(root, tmp, &fs_info->global_root_tree,
 370                                              rb_node) {
 371                 if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
 372                     root->root_key.objectid == BTRFS_CSUM_TREE_OBJECTID ||
 373                     root->root_key.objectid == BTRFS_FREE_SPACE_TREE_OBJECTID) {
 374                         num_bytes += btrfs_root_used(&root->root_item);
 375                         min_items++;
 376                 }
 377         }
 378         read_unlock(&fs_info->global_root_lock);
 379
 380         if (btrfs_fs_compat_ro(fs_info, BLOCK_GROUP_TREE)) {
 381                 num_bytes += btrfs_root_used(&fs_info->block_group_root->root_item);
 382                 min_items++;
 383         }
 384
 385         /*
 386          * But we also want to reserve enough space so we can do the fallback
 387          * global reserve for an unlink, which is an additional 5 items (see the
 388          * comment in __unlink_start_trans for what we're modifying.)
 389          *
 390          * But we also need space for the delayed ref updates from the unlink,
 391          * so its 10, 5 for the actual operation, and 5 for the delayed ref
 392          * updates.
 393          */
 394         min_items += 10;
 395
 396         num_bytes = max_t(u64, num_bytes,
 397                           btrfs_calc_insert_metadata_size(fs_info, min_items));
 398
 399         spin_lock(&sinfo->lock);
 400         spin_lock(&block_rsv->lock);
 401
 402         block_rsv->size = min_t(u64, num_bytes, SZ_512M);
 403
 404         if (block_rsv->reserved < block_rsv->size) {
 405                 num_bytes = block_rsv->size - block_rsv->reserved;
 406                 btrfs_space_info_update_bytes_may_use(fs_info, sinfo,
 407                                                       num_bytes);
 408                 block_rsv->reserved = block_rsv->size;
 409         } else if (block_rsv->reserved > block_rsv->size) {
 410                 num_bytes = block_rsv->reserved - block_rsv->size;
 411                 btrfs_space_info_update_bytes_may_use(fs_info, sinfo,
 412                                                       -num_bytes);
 413                 block_rsv->reserved = block_rsv->size;
 414                 btrfs_try_granting_tickets(fs_info, sinfo);
 415         }
 416
 417         block_rsv->full = (block_rsv->reserved == block_rsv->size);
 418
 419         if (block_rsv->size >= sinfo->total_bytes)
 420                 sinfo->force_alloc = CHUNK_ALLOC_FORCE;
 421         spin_unlock(&block_rsv->lock);
 422         spin_unlock(&sinfo->lock);
 423 }
 424
 425 void btrfs_init_root_block_rsv(struct btrfs_root *root)
 426 {
 427         struct btrfs_fs_info *fs_info = root->fs_info;
 428
 429         switch (root->root_key.objectid) {
 430         case BTRFS_CSUM_TREE_OBJECTID:
 431         case BTRFS_EXTENT_TREE_OBJECTID:
 432         case BTRFS_FREE_SPACE_TREE_OBJECTID:
 433         case BTRFS_BLOCK_GROUP_TREE_OBJECTID:
 434                 root->block_rsv = &fs_info->delayed_refs_rsv;
 435                 break;
 436         case BTRFS_ROOT_TREE_OBJECTID:
 437         case BTRFS_DEV_TREE_OBJECTID:
 438         case BTRFS_QUOTA_TREE_OBJECTID:
 439                 root->block_rsv = &fs_info->global_block_rsv;
 440                 break;
 441         case BTRFS_CHUNK_TREE_OBJECTID:
 442                 root->block_rsv = &fs_info->chunk_block_rsv;
 443                 break;
 444         default:
 445                 root->block_rsv = NULL;
 446                 break;
 447         }
 448 }
 449
 450 void btrfs_init_global_block_rsv(struct btrfs_fs_info *fs_info)
 451 {
 452         struct btrfs_space_info *space_info;
 453
 454         space_info = btrfs_find_space_info(fs_info, BTRFS_BLOCK_GROUP_SYSTEM);
 455         fs_info->chunk_block_rsv.space_info = space_info;
 456
 457         space_info = btrfs_find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
 458         fs_info->global_block_rsv.space_info = space_info;
 459         fs_info->trans_block_rsv.space_info = space_info;
 460         fs_info->empty_block_rsv.space_info = space_info;
 461         fs_info->delayed_block_rsv.space_info = space_info;
 462         fs_info->delayed_refs_rsv.space_info = space_info;
 463
 464         btrfs_update_global_block_rsv(fs_info);
 465 }
 466
 467 void btrfs_release_global_block_rsv(struct btrfs_fs_info *fs_info)
 468 {
 469         btrfs_block_rsv_release(fs_info, &fs_info->global_block_rsv, (u64)-1,
 470                                 NULL);
 471         WARN_ON(fs_info->trans_block_rsv.size > 0);
 472         WARN_ON(fs_info->trans_block_rsv.reserved > 0);
 473         WARN_ON(fs_info->chunk_block_rsv.size > 0);
 474         WARN_ON(fs_info->chunk_block_rsv.reserved > 0);
 475         WARN_ON(fs_info->delayed_block_rsv.size > 0);
 476         WARN_ON(fs_info->delayed_block_rsv.reserved > 0);
 477         WARN_ON(fs_info->delayed_refs_rsv.reserved > 0);
 478         WARN_ON(fs_info->delayed_refs_rsv.size > 0);
 479 }
 480
 481 static struct btrfs_block_rsv *get_block_rsv(
 482                                         const struct btrfs_trans_handle *trans,
 483                                         const struct btrfs_root *root)
 484 {
 485         struct btrfs_fs_info *fs_info = root->fs_info;
 486         struct btrfs_block_rsv *block_rsv = NULL;
 487
 488         if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) ||
 489             (root == fs_info->uuid_root) ||
 490             (trans->adding_csums &&
 491              root->root_key.objectid == BTRFS_CSUM_TREE_OBJECTID))
 492                 block_rsv = trans->block_rsv;
 493
 494         if (!block_rsv)
 495                 block_rsv = root->block_rsv;
 496
 497         if (!block_rsv)
 498                 block_rsv = &fs_info->empty_block_rsv;
 499
 500         return block_rsv;
 501 }
 502
 503 struct btrfs_block_rsv *btrfs_use_block_rsv(struct btrfs_trans_handle *trans,
 504                                             struct btrfs_root *root,
 505                                             u32 blocksize)
 506 {
 507         struct btrfs_fs_info *fs_info = root->fs_info;
 508         struct btrfs_block_rsv *block_rsv;
 509         struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
 510         int ret;
 511         bool global_updated = false;
 512
 513         block_rsv = get_block_rsv(trans, root);
 514
 515         if (unlikely(btrfs_block_rsv_size(block_rsv) == 0))
 516                 goto try_reserve;
 517 again:
 518         ret = btrfs_block_rsv_use_bytes(block_rsv, blocksize);
 519         if (!ret)
 520                 return block_rsv;
 521
 522         if (block_rsv->failfast)
 523                 return ERR_PTR(ret);
 524
 525         if (block_rsv->type == BTRFS_BLOCK_RSV_GLOBAL && !global_updated) {
 526                 global_updated = true;
 527                 btrfs_update_global_block_rsv(fs_info);
 528                 goto again;
 529         }
 530
 531         /*
 532          * The global reserve still exists to save us from ourselves, so don't
 533          * warn_on if we are short on our delayed refs reserve.
 534          */
 535         if (block_rsv->type != BTRFS_BLOCK_RSV_DELREFS &&
 536             btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
 537                 static DEFINE_RATELIMIT_STATE(_rs,
 538                                 DEFAULT_RATELIMIT_INTERVAL * 10,
 539                                 /*DEFAULT_RATELIMIT_BURST*/ 1);
 540                 if (__ratelimit(&_rs))
 541                         WARN(1, KERN_DEBUG
 542                                 "BTRFS: block rsv %d returned %d\n",
 543                                 block_rsv->type, ret);
 544         }
 545 try_reserve:
 546         ret = btrfs_reserve_metadata_bytes(fs_info, block_rsv, blocksize,
 547                                            BTRFS_RESERVE_NO_FLUSH);
 548         if (!ret)
 549                 return block_rsv;
 550         /*
 551          * If we couldn't reserve metadata bytes try and use some from
 552          * the global reserve if its space type is the same as the global
 553          * reservation.
 554          */
 555         if (block_rsv->type != BTRFS_BLOCK_RSV_GLOBAL &&
 556             block_rsv->space_info == global_rsv->space_info) {
 557                 ret = btrfs_block_rsv_use_bytes(global_rsv, blocksize);
 558                 if (!ret)
 559                         return global_rsv;
 560         }
 561         return ERR_PTR(ret);
 562 }