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
block_rsv_release_bytes(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * block_rsv,struct btrfs_block_rsv * dest,u64 num_bytes,u64 * qgroup_to_release_ret)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
btrfs_block_rsv_migrate(struct btrfs_block_rsv * src,struct btrfs_block_rsv * dst,u64 num_bytes,bool update_size)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
btrfs_init_block_rsv(struct btrfs_block_rsv * rsv,enum btrfs_rsv_type type)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
btrfs_init_metadata_block_rsv(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * rsv,enum btrfs_rsv_type type)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
btrfs_alloc_block_rsv(struct btrfs_fs_info * fs_info,enum btrfs_rsv_type type)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
btrfs_free_block_rsv(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * rsv)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
btrfs_block_rsv_add(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * block_rsv,u64 num_bytes,enum btrfs_reserve_flush_enum flush)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
btrfs_block_rsv_check(struct btrfs_block_rsv * block_rsv,int min_factor)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
btrfs_block_rsv_refill(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * block_rsv,u64 min_reserved,enum btrfs_reserve_flush_enum flush)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
btrfs_block_rsv_release(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * block_rsv,u64 num_bytes,u64 * qgroup_to_release)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
btrfs_block_rsv_use_bytes(struct btrfs_block_rsv * block_rsv,u64 num_bytes)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
btrfs_block_rsv_add_bytes(struct btrfs_block_rsv * block_rsv,u64 num_bytes,bool update_size)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
btrfs_cond_migrate_bytes(struct btrfs_fs_info * fs_info,struct btrfs_block_rsv * dest,u64 num_bytes,int min_factor)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
btrfs_update_global_block_rsv(struct btrfs_fs_info * fs_info)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
btrfs_init_root_block_rsv(struct btrfs_root * root)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
btrfs_init_global_block_rsv(struct btrfs_fs_info * fs_info)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
btrfs_release_global_block_rsv(struct btrfs_fs_info * fs_info)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
get_block_rsv(const struct btrfs_trans_handle * trans,const struct btrfs_root * root)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
btrfs_use_block_rsv(struct btrfs_trans_handle * trans,struct btrfs_root * root,u32 blocksize)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(block_rsv->size == 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 }
563