xref: /openbmc/linux/fs/btrfs/space-info.c (revision b4e18b29)
1 // SPDX-License-Identifier: GPL-2.0
2 
3 #include "misc.h"
4 #include "ctree.h"
5 #include "space-info.h"
6 #include "sysfs.h"
7 #include "volumes.h"
8 #include "free-space-cache.h"
9 #include "ordered-data.h"
10 #include "transaction.h"
11 #include "block-group.h"
12 
13 /*
14  * HOW DOES SPACE RESERVATION WORK
15  *
16  * If you want to know about delalloc specifically, there is a separate comment
17  * for that with the delalloc code.  This comment is about how the whole system
18  * works generally.
19  *
20  * BASIC CONCEPTS
21  *
22  *   1) space_info.  This is the ultimate arbiter of how much space we can use.
23  *   There's a description of the bytes_ fields with the struct declaration,
24  *   refer to that for specifics on each field.  Suffice it to say that for
25  *   reservations we care about total_bytes - SUM(space_info->bytes_) when
26  *   determining if there is space to make an allocation.  There is a space_info
27  *   for METADATA, SYSTEM, and DATA areas.
28  *
29  *   2) block_rsv's.  These are basically buckets for every different type of
30  *   metadata reservation we have.  You can see the comment in the block_rsv
31  *   code on the rules for each type, but generally block_rsv->reserved is how
32  *   much space is accounted for in space_info->bytes_may_use.
33  *
34  *   3) btrfs_calc*_size.  These are the worst case calculations we used based
35  *   on the number of items we will want to modify.  We have one for changing
36  *   items, and one for inserting new items.  Generally we use these helpers to
37  *   determine the size of the block reserves, and then use the actual bytes
38  *   values to adjust the space_info counters.
39  *
40  * MAKING RESERVATIONS, THE NORMAL CASE
41  *
42  *   We call into either btrfs_reserve_data_bytes() or
43  *   btrfs_reserve_metadata_bytes(), depending on which we're looking for, with
44  *   num_bytes we want to reserve.
45  *
46  *   ->reserve
47  *     space_info->bytes_may_reserve += num_bytes
48  *
49  *   ->extent allocation
50  *     Call btrfs_add_reserved_bytes() which does
51  *     space_info->bytes_may_reserve -= num_bytes
52  *     space_info->bytes_reserved += extent_bytes
53  *
54  *   ->insert reference
55  *     Call btrfs_update_block_group() which does
56  *     space_info->bytes_reserved -= extent_bytes
57  *     space_info->bytes_used += extent_bytes
58  *
59  * MAKING RESERVATIONS, FLUSHING NORMALLY (non-priority)
60  *
61  *   Assume we are unable to simply make the reservation because we do not have
62  *   enough space
63  *
64  *   -> __reserve_bytes
65  *     create a reserve_ticket with ->bytes set to our reservation, add it to
66  *     the tail of space_info->tickets, kick async flush thread
67  *
68  *   ->handle_reserve_ticket
69  *     wait on ticket->wait for ->bytes to be reduced to 0, or ->error to be set
70  *     on the ticket.
71  *
72  *   -> btrfs_async_reclaim_metadata_space/btrfs_async_reclaim_data_space
73  *     Flushes various things attempting to free up space.
74  *
75  *   -> btrfs_try_granting_tickets()
76  *     This is called by anything that either subtracts space from
77  *     space_info->bytes_may_use, ->bytes_pinned, etc, or adds to the
78  *     space_info->total_bytes.  This loops through the ->priority_tickets and
79  *     then the ->tickets list checking to see if the reservation can be
80  *     completed.  If it can the space is added to space_info->bytes_may_use and
81  *     the ticket is woken up.
82  *
83  *   -> ticket wakeup
84  *     Check if ->bytes == 0, if it does we got our reservation and we can carry
85  *     on, if not return the appropriate error (ENOSPC, but can be EINTR if we
86  *     were interrupted.)
87  *
88  * MAKING RESERVATIONS, FLUSHING HIGH PRIORITY
89  *
90  *   Same as the above, except we add ourselves to the
91  *   space_info->priority_tickets, and we do not use ticket->wait, we simply
92  *   call flush_space() ourselves for the states that are safe for us to call
93  *   without deadlocking and hope for the best.
94  *
95  * THE FLUSHING STATES
96  *
97  *   Generally speaking we will have two cases for each state, a "nice" state
98  *   and a "ALL THE THINGS" state.  In btrfs we delay a lot of work in order to
99  *   reduce the locking over head on the various trees, and even to keep from
100  *   doing any work at all in the case of delayed refs.  Each of these delayed
101  *   things however hold reservations, and so letting them run allows us to
102  *   reclaim space so we can make new reservations.
103  *
104  *   FLUSH_DELAYED_ITEMS
105  *     Every inode has a delayed item to update the inode.  Take a simple write
106  *     for example, we would update the inode item at write time to update the
107  *     mtime, and then again at finish_ordered_io() time in order to update the
108  *     isize or bytes.  We keep these delayed items to coalesce these operations
109  *     into a single operation done on demand.  These are an easy way to reclaim
110  *     metadata space.
111  *
112  *   FLUSH_DELALLOC
113  *     Look at the delalloc comment to get an idea of how much space is reserved
114  *     for delayed allocation.  We can reclaim some of this space simply by
115  *     running delalloc, but usually we need to wait for ordered extents to
116  *     reclaim the bulk of this space.
117  *
118  *   FLUSH_DELAYED_REFS
119  *     We have a block reserve for the outstanding delayed refs space, and every
120  *     delayed ref operation holds a reservation.  Running these is a quick way
121  *     to reclaim space, but we want to hold this until the end because COW can
122  *     churn a lot and we can avoid making some extent tree modifications if we
123  *     are able to delay for as long as possible.
124  *
125  *   ALLOC_CHUNK
126  *     We will skip this the first time through space reservation, because of
127  *     overcommit and we don't want to have a lot of useless metadata space when
128  *     our worst case reservations will likely never come true.
129  *
130  *   RUN_DELAYED_IPUTS
131  *     If we're freeing inodes we're likely freeing checksums, file extent
132  *     items, and extent tree items.  Loads of space could be freed up by these
133  *     operations, however they won't be usable until the transaction commits.
134  *
135  *   COMMIT_TRANS
136  *     may_commit_transaction() is the ultimate arbiter on whether we commit the
137  *     transaction or not.  In order to avoid constantly churning we do all the
138  *     above flushing first and then commit the transaction as the last resort.
139  *     However we need to take into account things like pinned space that would
140  *     be freed, plus any delayed work we may not have gotten rid of in the case
141  *     of metadata.
142  *
143  * OVERCOMMIT
144  *
145  *   Because we hold so many reservations for metadata we will allow you to
146  *   reserve more space than is currently free in the currently allocate
147  *   metadata space.  This only happens with metadata, data does not allow
148  *   overcommitting.
149  *
150  *   You can see the current logic for when we allow overcommit in
151  *   btrfs_can_overcommit(), but it only applies to unallocated space.  If there
152  *   is no unallocated space to be had, all reservations are kept within the
153  *   free space in the allocated metadata chunks.
154  *
155  *   Because of overcommitting, you generally want to use the
156  *   btrfs_can_overcommit() logic for metadata allocations, as it does the right
157  *   thing with or without extra unallocated space.
158  */
159 
160 u64 __pure btrfs_space_info_used(struct btrfs_space_info *s_info,
161 			  bool may_use_included)
162 {
163 	ASSERT(s_info);
164 	return s_info->bytes_used + s_info->bytes_reserved +
165 		s_info->bytes_pinned + s_info->bytes_readonly +
166 		(may_use_included ? s_info->bytes_may_use : 0);
167 }
168 
169 /*
170  * after adding space to the filesystem, we need to clear the full flags
171  * on all the space infos.
172  */
173 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
174 {
175 	struct list_head *head = &info->space_info;
176 	struct btrfs_space_info *found;
177 
178 	list_for_each_entry(found, head, list)
179 		found->full = 0;
180 }
181 
182 static int create_space_info(struct btrfs_fs_info *info, u64 flags)
183 {
184 
185 	struct btrfs_space_info *space_info;
186 	int i;
187 	int ret;
188 
189 	space_info = kzalloc(sizeof(*space_info), GFP_NOFS);
190 	if (!space_info)
191 		return -ENOMEM;
192 
193 	ret = percpu_counter_init(&space_info->total_bytes_pinned, 0,
194 				 GFP_KERNEL);
195 	if (ret) {
196 		kfree(space_info);
197 		return ret;
198 	}
199 
200 	for (i = 0; i < BTRFS_NR_RAID_TYPES; i++)
201 		INIT_LIST_HEAD(&space_info->block_groups[i]);
202 	init_rwsem(&space_info->groups_sem);
203 	spin_lock_init(&space_info->lock);
204 	space_info->flags = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
205 	space_info->force_alloc = CHUNK_ALLOC_NO_FORCE;
206 	INIT_LIST_HEAD(&space_info->ro_bgs);
207 	INIT_LIST_HEAD(&space_info->tickets);
208 	INIT_LIST_HEAD(&space_info->priority_tickets);
209 
210 	ret = btrfs_sysfs_add_space_info_type(info, space_info);
211 	if (ret)
212 		return ret;
213 
214 	list_add(&space_info->list, &info->space_info);
215 	if (flags & BTRFS_BLOCK_GROUP_DATA)
216 		info->data_sinfo = space_info;
217 
218 	return ret;
219 }
220 
221 int btrfs_init_space_info(struct btrfs_fs_info *fs_info)
222 {
223 	struct btrfs_super_block *disk_super;
224 	u64 features;
225 	u64 flags;
226 	int mixed = 0;
227 	int ret;
228 
229 	disk_super = fs_info->super_copy;
230 	if (!btrfs_super_root(disk_super))
231 		return -EINVAL;
232 
233 	features = btrfs_super_incompat_flags(disk_super);
234 	if (features & BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)
235 		mixed = 1;
236 
237 	flags = BTRFS_BLOCK_GROUP_SYSTEM;
238 	ret = create_space_info(fs_info, flags);
239 	if (ret)
240 		goto out;
241 
242 	if (mixed) {
243 		flags = BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_DATA;
244 		ret = create_space_info(fs_info, flags);
245 	} else {
246 		flags = BTRFS_BLOCK_GROUP_METADATA;
247 		ret = create_space_info(fs_info, flags);
248 		if (ret)
249 			goto out;
250 
251 		flags = BTRFS_BLOCK_GROUP_DATA;
252 		ret = create_space_info(fs_info, flags);
253 	}
254 out:
255 	return ret;
256 }
257 
258 void btrfs_update_space_info(struct btrfs_fs_info *info, u64 flags,
259 			     u64 total_bytes, u64 bytes_used,
260 			     u64 bytes_readonly,
261 			     struct btrfs_space_info **space_info)
262 {
263 	struct btrfs_space_info *found;
264 	int factor;
265 
266 	factor = btrfs_bg_type_to_factor(flags);
267 
268 	found = btrfs_find_space_info(info, flags);
269 	ASSERT(found);
270 	spin_lock(&found->lock);
271 	found->total_bytes += total_bytes;
272 	found->disk_total += total_bytes * factor;
273 	found->bytes_used += bytes_used;
274 	found->disk_used += bytes_used * factor;
275 	found->bytes_readonly += bytes_readonly;
276 	if (total_bytes > 0)
277 		found->full = 0;
278 	btrfs_try_granting_tickets(info, found);
279 	spin_unlock(&found->lock);
280 	*space_info = found;
281 }
282 
283 struct btrfs_space_info *btrfs_find_space_info(struct btrfs_fs_info *info,
284 					       u64 flags)
285 {
286 	struct list_head *head = &info->space_info;
287 	struct btrfs_space_info *found;
288 
289 	flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
290 
291 	list_for_each_entry(found, head, list) {
292 		if (found->flags & flags)
293 			return found;
294 	}
295 	return NULL;
296 }
297 
298 static u64 calc_available_free_space(struct btrfs_fs_info *fs_info,
299 			  struct btrfs_space_info *space_info,
300 			  enum btrfs_reserve_flush_enum flush)
301 {
302 	u64 profile;
303 	u64 avail;
304 	int factor;
305 
306 	if (space_info->flags & BTRFS_BLOCK_GROUP_SYSTEM)
307 		profile = btrfs_system_alloc_profile(fs_info);
308 	else
309 		profile = btrfs_metadata_alloc_profile(fs_info);
310 
311 	avail = atomic64_read(&fs_info->free_chunk_space);
312 
313 	/*
314 	 * If we have dup, raid1 or raid10 then only half of the free
315 	 * space is actually usable.  For raid56, the space info used
316 	 * doesn't include the parity drive, so we don't have to
317 	 * change the math
318 	 */
319 	factor = btrfs_bg_type_to_factor(profile);
320 	avail = div_u64(avail, factor);
321 
322 	/*
323 	 * If we aren't flushing all things, let us overcommit up to
324 	 * 1/2th of the space. If we can flush, don't let us overcommit
325 	 * too much, let it overcommit up to 1/8 of the space.
326 	 */
327 	if (flush == BTRFS_RESERVE_FLUSH_ALL)
328 		avail >>= 3;
329 	else
330 		avail >>= 1;
331 	return avail;
332 }
333 
334 int btrfs_can_overcommit(struct btrfs_fs_info *fs_info,
335 			 struct btrfs_space_info *space_info, u64 bytes,
336 			 enum btrfs_reserve_flush_enum flush)
337 {
338 	u64 avail;
339 	u64 used;
340 
341 	/* Don't overcommit when in mixed mode */
342 	if (space_info->flags & BTRFS_BLOCK_GROUP_DATA)
343 		return 0;
344 
345 	used = btrfs_space_info_used(space_info, true);
346 	avail = calc_available_free_space(fs_info, space_info, flush);
347 
348 	if (used + bytes < space_info->total_bytes + avail)
349 		return 1;
350 	return 0;
351 }
352 
353 static void remove_ticket(struct btrfs_space_info *space_info,
354 			  struct reserve_ticket *ticket)
355 {
356 	if (!list_empty(&ticket->list)) {
357 		list_del_init(&ticket->list);
358 		ASSERT(space_info->reclaim_size >= ticket->bytes);
359 		space_info->reclaim_size -= ticket->bytes;
360 	}
361 }
362 
363 /*
364  * This is for space we already have accounted in space_info->bytes_may_use, so
365  * basically when we're returning space from block_rsv's.
366  */
367 void btrfs_try_granting_tickets(struct btrfs_fs_info *fs_info,
368 				struct btrfs_space_info *space_info)
369 {
370 	struct list_head *head;
371 	enum btrfs_reserve_flush_enum flush = BTRFS_RESERVE_NO_FLUSH;
372 
373 	lockdep_assert_held(&space_info->lock);
374 
375 	head = &space_info->priority_tickets;
376 again:
377 	while (!list_empty(head)) {
378 		struct reserve_ticket *ticket;
379 		u64 used = btrfs_space_info_used(space_info, true);
380 
381 		ticket = list_first_entry(head, struct reserve_ticket, list);
382 
383 		/* Check and see if our ticket can be satisified now. */
384 		if ((used + ticket->bytes <= space_info->total_bytes) ||
385 		    btrfs_can_overcommit(fs_info, space_info, ticket->bytes,
386 					 flush)) {
387 			btrfs_space_info_update_bytes_may_use(fs_info,
388 							      space_info,
389 							      ticket->bytes);
390 			remove_ticket(space_info, ticket);
391 			ticket->bytes = 0;
392 			space_info->tickets_id++;
393 			wake_up(&ticket->wait);
394 		} else {
395 			break;
396 		}
397 	}
398 
399 	if (head == &space_info->priority_tickets) {
400 		head = &space_info->tickets;
401 		flush = BTRFS_RESERVE_FLUSH_ALL;
402 		goto again;
403 	}
404 }
405 
406 #define DUMP_BLOCK_RSV(fs_info, rsv_name)				\
407 do {									\
408 	struct btrfs_block_rsv *__rsv = &(fs_info)->rsv_name;		\
409 	spin_lock(&__rsv->lock);					\
410 	btrfs_info(fs_info, #rsv_name ": size %llu reserved %llu",	\
411 		   __rsv->size, __rsv->reserved);			\
412 	spin_unlock(&__rsv->lock);					\
413 } while (0)
414 
415 static void __btrfs_dump_space_info(struct btrfs_fs_info *fs_info,
416 				    struct btrfs_space_info *info)
417 {
418 	lockdep_assert_held(&info->lock);
419 
420 	btrfs_info(fs_info, "space_info %llu has %llu free, is %sfull",
421 		   info->flags,
422 		   info->total_bytes - btrfs_space_info_used(info, true),
423 		   info->full ? "" : "not ");
424 	btrfs_info(fs_info,
425 		"space_info total=%llu, used=%llu, pinned=%llu, reserved=%llu, may_use=%llu, readonly=%llu",
426 		info->total_bytes, info->bytes_used, info->bytes_pinned,
427 		info->bytes_reserved, info->bytes_may_use,
428 		info->bytes_readonly);
429 
430 	DUMP_BLOCK_RSV(fs_info, global_block_rsv);
431 	DUMP_BLOCK_RSV(fs_info, trans_block_rsv);
432 	DUMP_BLOCK_RSV(fs_info, chunk_block_rsv);
433 	DUMP_BLOCK_RSV(fs_info, delayed_block_rsv);
434 	DUMP_BLOCK_RSV(fs_info, delayed_refs_rsv);
435 
436 }
437 
438 void btrfs_dump_space_info(struct btrfs_fs_info *fs_info,
439 			   struct btrfs_space_info *info, u64 bytes,
440 			   int dump_block_groups)
441 {
442 	struct btrfs_block_group *cache;
443 	int index = 0;
444 
445 	spin_lock(&info->lock);
446 	__btrfs_dump_space_info(fs_info, info);
447 	spin_unlock(&info->lock);
448 
449 	if (!dump_block_groups)
450 		return;
451 
452 	down_read(&info->groups_sem);
453 again:
454 	list_for_each_entry(cache, &info->block_groups[index], list) {
455 		spin_lock(&cache->lock);
456 		btrfs_info(fs_info,
457 			"block group %llu has %llu bytes, %llu used %llu pinned %llu reserved %s",
458 			cache->start, cache->length, cache->used, cache->pinned,
459 			cache->reserved, cache->ro ? "[readonly]" : "");
460 		spin_unlock(&cache->lock);
461 		btrfs_dump_free_space(cache, bytes);
462 	}
463 	if (++index < BTRFS_NR_RAID_TYPES)
464 		goto again;
465 	up_read(&info->groups_sem);
466 }
467 
468 static inline u64 calc_reclaim_items_nr(struct btrfs_fs_info *fs_info,
469 					u64 to_reclaim)
470 {
471 	u64 bytes;
472 	u64 nr;
473 
474 	bytes = btrfs_calc_insert_metadata_size(fs_info, 1);
475 	nr = div64_u64(to_reclaim, bytes);
476 	if (!nr)
477 		nr = 1;
478 	return nr;
479 }
480 
481 #define EXTENT_SIZE_PER_ITEM	SZ_256K
482 
483 /*
484  * shrink metadata reservation for delalloc
485  */
486 static void shrink_delalloc(struct btrfs_fs_info *fs_info,
487 			    struct btrfs_space_info *space_info,
488 			    u64 to_reclaim, bool wait_ordered)
489 {
490 	struct btrfs_trans_handle *trans;
491 	u64 delalloc_bytes;
492 	u64 dio_bytes;
493 	u64 items;
494 	long time_left;
495 	int loops;
496 
497 	/* Calc the number of the pages we need flush for space reservation */
498 	if (to_reclaim == U64_MAX) {
499 		items = U64_MAX;
500 	} else {
501 		/*
502 		 * to_reclaim is set to however much metadata we need to
503 		 * reclaim, but reclaiming that much data doesn't really track
504 		 * exactly, so increase the amount to reclaim by 2x in order to
505 		 * make sure we're flushing enough delalloc to hopefully reclaim
506 		 * some metadata reservations.
507 		 */
508 		items = calc_reclaim_items_nr(fs_info, to_reclaim) * 2;
509 		to_reclaim = items * EXTENT_SIZE_PER_ITEM;
510 	}
511 
512 	trans = (struct btrfs_trans_handle *)current->journal_info;
513 
514 	delalloc_bytes = percpu_counter_sum_positive(
515 						&fs_info->delalloc_bytes);
516 	dio_bytes = percpu_counter_sum_positive(&fs_info->dio_bytes);
517 	if (delalloc_bytes == 0 && dio_bytes == 0) {
518 		if (trans)
519 			return;
520 		if (wait_ordered)
521 			btrfs_wait_ordered_roots(fs_info, items, 0, (u64)-1);
522 		return;
523 	}
524 
525 	/*
526 	 * If we are doing more ordered than delalloc we need to just wait on
527 	 * ordered extents, otherwise we'll waste time trying to flush delalloc
528 	 * that likely won't give us the space back we need.
529 	 */
530 	if (dio_bytes > delalloc_bytes)
531 		wait_ordered = true;
532 
533 	loops = 0;
534 	while ((delalloc_bytes || dio_bytes) && loops < 3) {
535 		u64 nr_pages = min(delalloc_bytes, to_reclaim) >> PAGE_SHIFT;
536 
537 		btrfs_start_delalloc_roots(fs_info, nr_pages, true);
538 
539 		loops++;
540 		if (wait_ordered && !trans) {
541 			btrfs_wait_ordered_roots(fs_info, items, 0, (u64)-1);
542 		} else {
543 			time_left = schedule_timeout_killable(1);
544 			if (time_left)
545 				break;
546 		}
547 
548 		spin_lock(&space_info->lock);
549 		if (list_empty(&space_info->tickets) &&
550 		    list_empty(&space_info->priority_tickets)) {
551 			spin_unlock(&space_info->lock);
552 			break;
553 		}
554 		spin_unlock(&space_info->lock);
555 
556 		delalloc_bytes = percpu_counter_sum_positive(
557 						&fs_info->delalloc_bytes);
558 		dio_bytes = percpu_counter_sum_positive(&fs_info->dio_bytes);
559 	}
560 }
561 
562 /**
563  * maybe_commit_transaction - possibly commit the transaction if its ok to
564  * @root - the root we're allocating for
565  * @bytes - the number of bytes we want to reserve
566  * @force - force the commit
567  *
568  * This will check to make sure that committing the transaction will actually
569  * get us somewhere and then commit the transaction if it does.  Otherwise it
570  * will return -ENOSPC.
571  */
572 static int may_commit_transaction(struct btrfs_fs_info *fs_info,
573 				  struct btrfs_space_info *space_info)
574 {
575 	struct reserve_ticket *ticket = NULL;
576 	struct btrfs_block_rsv *delayed_rsv = &fs_info->delayed_block_rsv;
577 	struct btrfs_block_rsv *delayed_refs_rsv = &fs_info->delayed_refs_rsv;
578 	struct btrfs_block_rsv *trans_rsv = &fs_info->trans_block_rsv;
579 	struct btrfs_trans_handle *trans;
580 	u64 reclaim_bytes = 0;
581 	u64 bytes_needed = 0;
582 	u64 cur_free_bytes = 0;
583 
584 	trans = (struct btrfs_trans_handle *)current->journal_info;
585 	if (trans)
586 		return -EAGAIN;
587 
588 	spin_lock(&space_info->lock);
589 	cur_free_bytes = btrfs_space_info_used(space_info, true);
590 	if (cur_free_bytes < space_info->total_bytes)
591 		cur_free_bytes = space_info->total_bytes - cur_free_bytes;
592 	else
593 		cur_free_bytes = 0;
594 
595 	if (!list_empty(&space_info->priority_tickets))
596 		ticket = list_first_entry(&space_info->priority_tickets,
597 					  struct reserve_ticket, list);
598 	else if (!list_empty(&space_info->tickets))
599 		ticket = list_first_entry(&space_info->tickets,
600 					  struct reserve_ticket, list);
601 	if (ticket)
602 		bytes_needed = ticket->bytes;
603 
604 	if (bytes_needed > cur_free_bytes)
605 		bytes_needed -= cur_free_bytes;
606 	else
607 		bytes_needed = 0;
608 	spin_unlock(&space_info->lock);
609 
610 	if (!bytes_needed)
611 		return 0;
612 
613 	trans = btrfs_join_transaction(fs_info->extent_root);
614 	if (IS_ERR(trans))
615 		return PTR_ERR(trans);
616 
617 	/*
618 	 * See if there is enough pinned space to make this reservation, or if
619 	 * we have block groups that are going to be freed, allowing us to
620 	 * possibly do a chunk allocation the next loop through.
621 	 */
622 	if (test_bit(BTRFS_TRANS_HAVE_FREE_BGS, &trans->transaction->flags) ||
623 	    __percpu_counter_compare(&space_info->total_bytes_pinned,
624 				     bytes_needed,
625 				     BTRFS_TOTAL_BYTES_PINNED_BATCH) >= 0)
626 		goto commit;
627 
628 	/*
629 	 * See if there is some space in the delayed insertion reserve for this
630 	 * reservation.  If the space_info's don't match (like for DATA or
631 	 * SYSTEM) then just go enospc, reclaiming this space won't recover any
632 	 * space to satisfy those reservations.
633 	 */
634 	if (space_info != delayed_rsv->space_info)
635 		goto enospc;
636 
637 	spin_lock(&delayed_rsv->lock);
638 	reclaim_bytes += delayed_rsv->reserved;
639 	spin_unlock(&delayed_rsv->lock);
640 
641 	spin_lock(&delayed_refs_rsv->lock);
642 	reclaim_bytes += delayed_refs_rsv->reserved;
643 	spin_unlock(&delayed_refs_rsv->lock);
644 
645 	spin_lock(&trans_rsv->lock);
646 	reclaim_bytes += trans_rsv->reserved;
647 	spin_unlock(&trans_rsv->lock);
648 
649 	if (reclaim_bytes >= bytes_needed)
650 		goto commit;
651 	bytes_needed -= reclaim_bytes;
652 
653 	if (__percpu_counter_compare(&space_info->total_bytes_pinned,
654 				   bytes_needed,
655 				   BTRFS_TOTAL_BYTES_PINNED_BATCH) < 0)
656 		goto enospc;
657 
658 commit:
659 	return btrfs_commit_transaction(trans);
660 enospc:
661 	btrfs_end_transaction(trans);
662 	return -ENOSPC;
663 }
664 
665 /*
666  * Try to flush some data based on policy set by @state. This is only advisory
667  * and may fail for various reasons. The caller is supposed to examine the
668  * state of @space_info to detect the outcome.
669  */
670 static void flush_space(struct btrfs_fs_info *fs_info,
671 		       struct btrfs_space_info *space_info, u64 num_bytes,
672 		       int state)
673 {
674 	struct btrfs_root *root = fs_info->extent_root;
675 	struct btrfs_trans_handle *trans;
676 	int nr;
677 	int ret = 0;
678 
679 	switch (state) {
680 	case FLUSH_DELAYED_ITEMS_NR:
681 	case FLUSH_DELAYED_ITEMS:
682 		if (state == FLUSH_DELAYED_ITEMS_NR)
683 			nr = calc_reclaim_items_nr(fs_info, num_bytes) * 2;
684 		else
685 			nr = -1;
686 
687 		trans = btrfs_join_transaction(root);
688 		if (IS_ERR(trans)) {
689 			ret = PTR_ERR(trans);
690 			break;
691 		}
692 		ret = btrfs_run_delayed_items_nr(trans, nr);
693 		btrfs_end_transaction(trans);
694 		break;
695 	case FLUSH_DELALLOC:
696 	case FLUSH_DELALLOC_WAIT:
697 		shrink_delalloc(fs_info, space_info, num_bytes,
698 				state == FLUSH_DELALLOC_WAIT);
699 		break;
700 	case FLUSH_DELAYED_REFS_NR:
701 	case FLUSH_DELAYED_REFS:
702 		trans = btrfs_join_transaction(root);
703 		if (IS_ERR(trans)) {
704 			ret = PTR_ERR(trans);
705 			break;
706 		}
707 		if (state == FLUSH_DELAYED_REFS_NR)
708 			nr = calc_reclaim_items_nr(fs_info, num_bytes);
709 		else
710 			nr = 0;
711 		btrfs_run_delayed_refs(trans, nr);
712 		btrfs_end_transaction(trans);
713 		break;
714 	case ALLOC_CHUNK:
715 	case ALLOC_CHUNK_FORCE:
716 		trans = btrfs_join_transaction(root);
717 		if (IS_ERR(trans)) {
718 			ret = PTR_ERR(trans);
719 			break;
720 		}
721 		ret = btrfs_chunk_alloc(trans,
722 				btrfs_get_alloc_profile(fs_info, space_info->flags),
723 				(state == ALLOC_CHUNK) ? CHUNK_ALLOC_NO_FORCE :
724 					CHUNK_ALLOC_FORCE);
725 		btrfs_end_transaction(trans);
726 		if (ret > 0 || ret == -ENOSPC)
727 			ret = 0;
728 		break;
729 	case RUN_DELAYED_IPUTS:
730 		/*
731 		 * If we have pending delayed iputs then we could free up a
732 		 * bunch of pinned space, so make sure we run the iputs before
733 		 * we do our pinned bytes check below.
734 		 */
735 		btrfs_run_delayed_iputs(fs_info);
736 		btrfs_wait_on_delayed_iputs(fs_info);
737 		break;
738 	case COMMIT_TRANS:
739 		ret = may_commit_transaction(fs_info, space_info);
740 		break;
741 	default:
742 		ret = -ENOSPC;
743 		break;
744 	}
745 
746 	trace_btrfs_flush_space(fs_info, space_info->flags, num_bytes, state,
747 				ret);
748 	return;
749 }
750 
751 static inline u64
752 btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
753 				 struct btrfs_space_info *space_info)
754 {
755 	u64 used;
756 	u64 avail;
757 	u64 expected;
758 	u64 to_reclaim = space_info->reclaim_size;
759 
760 	lockdep_assert_held(&space_info->lock);
761 
762 	avail = calc_available_free_space(fs_info, space_info,
763 					  BTRFS_RESERVE_FLUSH_ALL);
764 	used = btrfs_space_info_used(space_info, true);
765 
766 	/*
767 	 * We may be flushing because suddenly we have less space than we had
768 	 * before, and now we're well over-committed based on our current free
769 	 * space.  If that's the case add in our overage so we make sure to put
770 	 * appropriate pressure on the flushing state machine.
771 	 */
772 	if (space_info->total_bytes + avail < used)
773 		to_reclaim += used - (space_info->total_bytes + avail);
774 
775 	if (to_reclaim)
776 		return to_reclaim;
777 
778 	to_reclaim = min_t(u64, num_online_cpus() * SZ_1M, SZ_16M);
779 	if (btrfs_can_overcommit(fs_info, space_info, to_reclaim,
780 				 BTRFS_RESERVE_FLUSH_ALL))
781 		return 0;
782 
783 	used = btrfs_space_info_used(space_info, true);
784 
785 	if (btrfs_can_overcommit(fs_info, space_info, SZ_1M,
786 				 BTRFS_RESERVE_FLUSH_ALL))
787 		expected = div_factor_fine(space_info->total_bytes, 95);
788 	else
789 		expected = div_factor_fine(space_info->total_bytes, 90);
790 
791 	if (used > expected)
792 		to_reclaim = used - expected;
793 	else
794 		to_reclaim = 0;
795 	to_reclaim = min(to_reclaim, space_info->bytes_may_use +
796 				     space_info->bytes_reserved);
797 	return to_reclaim;
798 }
799 
800 static inline int need_do_async_reclaim(struct btrfs_fs_info *fs_info,
801 					struct btrfs_space_info *space_info,
802 					u64 used)
803 {
804 	u64 thresh = div_factor_fine(space_info->total_bytes, 98);
805 
806 	/* If we're just plain full then async reclaim just slows us down. */
807 	if ((space_info->bytes_used + space_info->bytes_reserved) >= thresh)
808 		return 0;
809 
810 	if (!btrfs_calc_reclaim_metadata_size(fs_info, space_info))
811 		return 0;
812 
813 	return (used >= thresh && !btrfs_fs_closing(fs_info) &&
814 		!test_bit(BTRFS_FS_STATE_REMOUNTING, &fs_info->fs_state));
815 }
816 
817 static bool steal_from_global_rsv(struct btrfs_fs_info *fs_info,
818 				  struct btrfs_space_info *space_info,
819 				  struct reserve_ticket *ticket)
820 {
821 	struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
822 	u64 min_bytes;
823 
824 	if (global_rsv->space_info != space_info)
825 		return false;
826 
827 	spin_lock(&global_rsv->lock);
828 	min_bytes = div_factor(global_rsv->size, 1);
829 	if (global_rsv->reserved < min_bytes + ticket->bytes) {
830 		spin_unlock(&global_rsv->lock);
831 		return false;
832 	}
833 	global_rsv->reserved -= ticket->bytes;
834 	remove_ticket(space_info, ticket);
835 	ticket->bytes = 0;
836 	wake_up(&ticket->wait);
837 	space_info->tickets_id++;
838 	if (global_rsv->reserved < global_rsv->size)
839 		global_rsv->full = 0;
840 	spin_unlock(&global_rsv->lock);
841 
842 	return true;
843 }
844 
845 /*
846  * maybe_fail_all_tickets - we've exhausted our flushing, start failing tickets
847  * @fs_info - fs_info for this fs
848  * @space_info - the space info we were flushing
849  *
850  * We call this when we've exhausted our flushing ability and haven't made
851  * progress in satisfying tickets.  The reservation code handles tickets in
852  * order, so if there is a large ticket first and then smaller ones we could
853  * very well satisfy the smaller tickets.  This will attempt to wake up any
854  * tickets in the list to catch this case.
855  *
856  * This function returns true if it was able to make progress by clearing out
857  * other tickets, or if it stumbles across a ticket that was smaller than the
858  * first ticket.
859  */
860 static bool maybe_fail_all_tickets(struct btrfs_fs_info *fs_info,
861 				   struct btrfs_space_info *space_info)
862 {
863 	struct reserve_ticket *ticket;
864 	u64 tickets_id = space_info->tickets_id;
865 	u64 first_ticket_bytes = 0;
866 
867 	if (btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
868 		btrfs_info(fs_info, "cannot satisfy tickets, dumping space info");
869 		__btrfs_dump_space_info(fs_info, space_info);
870 	}
871 
872 	while (!list_empty(&space_info->tickets) &&
873 	       tickets_id == space_info->tickets_id) {
874 		ticket = list_first_entry(&space_info->tickets,
875 					  struct reserve_ticket, list);
876 
877 		if (ticket->steal &&
878 		    steal_from_global_rsv(fs_info, space_info, ticket))
879 			return true;
880 
881 		/*
882 		 * may_commit_transaction will avoid committing the transaction
883 		 * if it doesn't feel like the space reclaimed by the commit
884 		 * would result in the ticket succeeding.  However if we have a
885 		 * smaller ticket in the queue it may be small enough to be
886 		 * satisified by committing the transaction, so if any
887 		 * subsequent ticket is smaller than the first ticket go ahead
888 		 * and send us back for another loop through the enospc flushing
889 		 * code.
890 		 */
891 		if (first_ticket_bytes == 0)
892 			first_ticket_bytes = ticket->bytes;
893 		else if (first_ticket_bytes > ticket->bytes)
894 			return true;
895 
896 		if (btrfs_test_opt(fs_info, ENOSPC_DEBUG))
897 			btrfs_info(fs_info, "failing ticket with %llu bytes",
898 				   ticket->bytes);
899 
900 		remove_ticket(space_info, ticket);
901 		ticket->error = -ENOSPC;
902 		wake_up(&ticket->wait);
903 
904 		/*
905 		 * We're just throwing tickets away, so more flushing may not
906 		 * trip over btrfs_try_granting_tickets, so we need to call it
907 		 * here to see if we can make progress with the next ticket in
908 		 * the list.
909 		 */
910 		btrfs_try_granting_tickets(fs_info, space_info);
911 	}
912 	return (tickets_id != space_info->tickets_id);
913 }
914 
915 /*
916  * This is for normal flushers, we can wait all goddamned day if we want to.  We
917  * will loop and continuously try to flush as long as we are making progress.
918  * We count progress as clearing off tickets each time we have to loop.
919  */
920 static void btrfs_async_reclaim_metadata_space(struct work_struct *work)
921 {
922 	struct btrfs_fs_info *fs_info;
923 	struct btrfs_space_info *space_info;
924 	u64 to_reclaim;
925 	int flush_state;
926 	int commit_cycles = 0;
927 	u64 last_tickets_id;
928 
929 	fs_info = container_of(work, struct btrfs_fs_info, async_reclaim_work);
930 	space_info = btrfs_find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
931 
932 	spin_lock(&space_info->lock);
933 	to_reclaim = btrfs_calc_reclaim_metadata_size(fs_info, space_info);
934 	if (!to_reclaim) {
935 		space_info->flush = 0;
936 		spin_unlock(&space_info->lock);
937 		return;
938 	}
939 	last_tickets_id = space_info->tickets_id;
940 	spin_unlock(&space_info->lock);
941 
942 	flush_state = FLUSH_DELAYED_ITEMS_NR;
943 	do {
944 		flush_space(fs_info, space_info, to_reclaim, flush_state);
945 		spin_lock(&space_info->lock);
946 		if (list_empty(&space_info->tickets)) {
947 			space_info->flush = 0;
948 			spin_unlock(&space_info->lock);
949 			return;
950 		}
951 		to_reclaim = btrfs_calc_reclaim_metadata_size(fs_info,
952 							      space_info);
953 		if (last_tickets_id == space_info->tickets_id) {
954 			flush_state++;
955 		} else {
956 			last_tickets_id = space_info->tickets_id;
957 			flush_state = FLUSH_DELAYED_ITEMS_NR;
958 			if (commit_cycles)
959 				commit_cycles--;
960 		}
961 
962 		/*
963 		 * We don't want to force a chunk allocation until we've tried
964 		 * pretty hard to reclaim space.  Think of the case where we
965 		 * freed up a bunch of space and so have a lot of pinned space
966 		 * to reclaim.  We would rather use that than possibly create a
967 		 * underutilized metadata chunk.  So if this is our first run
968 		 * through the flushing state machine skip ALLOC_CHUNK_FORCE and
969 		 * commit the transaction.  If nothing has changed the next go
970 		 * around then we can force a chunk allocation.
971 		 */
972 		if (flush_state == ALLOC_CHUNK_FORCE && !commit_cycles)
973 			flush_state++;
974 
975 		if (flush_state > COMMIT_TRANS) {
976 			commit_cycles++;
977 			if (commit_cycles > 2) {
978 				if (maybe_fail_all_tickets(fs_info, space_info)) {
979 					flush_state = FLUSH_DELAYED_ITEMS_NR;
980 					commit_cycles--;
981 				} else {
982 					space_info->flush = 0;
983 				}
984 			} else {
985 				flush_state = FLUSH_DELAYED_ITEMS_NR;
986 			}
987 		}
988 		spin_unlock(&space_info->lock);
989 	} while (flush_state <= COMMIT_TRANS);
990 }
991 
992 /*
993  * FLUSH_DELALLOC_WAIT:
994  *   Space is freed from flushing delalloc in one of two ways.
995  *
996  *   1) compression is on and we allocate less space than we reserved
997  *   2) we are overwriting existing space
998  *
999  *   For #1 that extra space is reclaimed as soon as the delalloc pages are
1000  *   COWed, by way of btrfs_add_reserved_bytes() which adds the actual extent
1001  *   length to ->bytes_reserved, and subtracts the reserved space from
1002  *   ->bytes_may_use.
1003  *
1004  *   For #2 this is trickier.  Once the ordered extent runs we will drop the
1005  *   extent in the range we are overwriting, which creates a delayed ref for
1006  *   that freed extent.  This however is not reclaimed until the transaction
1007  *   commits, thus the next stages.
1008  *
1009  * RUN_DELAYED_IPUTS
1010  *   If we are freeing inodes, we want to make sure all delayed iputs have
1011  *   completed, because they could have been on an inode with i_nlink == 0, and
1012  *   thus have been truncated and freed up space.  But again this space is not
1013  *   immediately re-usable, it comes in the form of a delayed ref, which must be
1014  *   run and then the transaction must be committed.
1015  *
1016  * FLUSH_DELAYED_REFS
1017  *   The above two cases generate delayed refs that will affect
1018  *   ->total_bytes_pinned.  However this counter can be inconsistent with
1019  *   reality if there are outstanding delayed refs.  This is because we adjust
1020  *   the counter based solely on the current set of delayed refs and disregard
1021  *   any on-disk state which might include more refs.  So for example, if we
1022  *   have an extent with 2 references, but we only drop 1, we'll see that there
1023  *   is a negative delayed ref count for the extent and assume that the space
1024  *   will be freed, and thus increase ->total_bytes_pinned.
1025  *
1026  *   Running the delayed refs gives us the actual real view of what will be
1027  *   freed at the transaction commit time.  This stage will not actually free
1028  *   space for us, it just makes sure that may_commit_transaction() has all of
1029  *   the information it needs to make the right decision.
1030  *
1031  * COMMIT_TRANS
1032  *   This is where we reclaim all of the pinned space generated by the previous
1033  *   two stages.  We will not commit the transaction if we don't think we're
1034  *   likely to satisfy our request, which means if our current free space +
1035  *   total_bytes_pinned < reservation we will not commit.  This is why the
1036  *   previous states are actually important, to make sure we know for sure
1037  *   whether committing the transaction will allow us to make progress.
1038  *
1039  * ALLOC_CHUNK_FORCE
1040  *   For data we start with alloc chunk force, however we could have been full
1041  *   before, and then the transaction commit could have freed new block groups,
1042  *   so if we now have space to allocate do the force chunk allocation.
1043  */
1044 static const enum btrfs_flush_state data_flush_states[] = {
1045 	FLUSH_DELALLOC_WAIT,
1046 	RUN_DELAYED_IPUTS,
1047 	FLUSH_DELAYED_REFS,
1048 	COMMIT_TRANS,
1049 	ALLOC_CHUNK_FORCE,
1050 };
1051 
1052 static void btrfs_async_reclaim_data_space(struct work_struct *work)
1053 {
1054 	struct btrfs_fs_info *fs_info;
1055 	struct btrfs_space_info *space_info;
1056 	u64 last_tickets_id;
1057 	int flush_state = 0;
1058 
1059 	fs_info = container_of(work, struct btrfs_fs_info, async_data_reclaim_work);
1060 	space_info = fs_info->data_sinfo;
1061 
1062 	spin_lock(&space_info->lock);
1063 	if (list_empty(&space_info->tickets)) {
1064 		space_info->flush = 0;
1065 		spin_unlock(&space_info->lock);
1066 		return;
1067 	}
1068 	last_tickets_id = space_info->tickets_id;
1069 	spin_unlock(&space_info->lock);
1070 
1071 	while (!space_info->full) {
1072 		flush_space(fs_info, space_info, U64_MAX, ALLOC_CHUNK_FORCE);
1073 		spin_lock(&space_info->lock);
1074 		if (list_empty(&space_info->tickets)) {
1075 			space_info->flush = 0;
1076 			spin_unlock(&space_info->lock);
1077 			return;
1078 		}
1079 		last_tickets_id = space_info->tickets_id;
1080 		spin_unlock(&space_info->lock);
1081 	}
1082 
1083 	while (flush_state < ARRAY_SIZE(data_flush_states)) {
1084 		flush_space(fs_info, space_info, U64_MAX,
1085 			    data_flush_states[flush_state]);
1086 		spin_lock(&space_info->lock);
1087 		if (list_empty(&space_info->tickets)) {
1088 			space_info->flush = 0;
1089 			spin_unlock(&space_info->lock);
1090 			return;
1091 		}
1092 
1093 		if (last_tickets_id == space_info->tickets_id) {
1094 			flush_state++;
1095 		} else {
1096 			last_tickets_id = space_info->tickets_id;
1097 			flush_state = 0;
1098 		}
1099 
1100 		if (flush_state >= ARRAY_SIZE(data_flush_states)) {
1101 			if (space_info->full) {
1102 				if (maybe_fail_all_tickets(fs_info, space_info))
1103 					flush_state = 0;
1104 				else
1105 					space_info->flush = 0;
1106 			} else {
1107 				flush_state = 0;
1108 			}
1109 		}
1110 		spin_unlock(&space_info->lock);
1111 	}
1112 }
1113 
1114 void btrfs_init_async_reclaim_work(struct btrfs_fs_info *fs_info)
1115 {
1116 	INIT_WORK(&fs_info->async_reclaim_work, btrfs_async_reclaim_metadata_space);
1117 	INIT_WORK(&fs_info->async_data_reclaim_work, btrfs_async_reclaim_data_space);
1118 }
1119 
1120 static const enum btrfs_flush_state priority_flush_states[] = {
1121 	FLUSH_DELAYED_ITEMS_NR,
1122 	FLUSH_DELAYED_ITEMS,
1123 	ALLOC_CHUNK,
1124 };
1125 
1126 static const enum btrfs_flush_state evict_flush_states[] = {
1127 	FLUSH_DELAYED_ITEMS_NR,
1128 	FLUSH_DELAYED_ITEMS,
1129 	FLUSH_DELAYED_REFS_NR,
1130 	FLUSH_DELAYED_REFS,
1131 	FLUSH_DELALLOC,
1132 	FLUSH_DELALLOC_WAIT,
1133 	ALLOC_CHUNK,
1134 	COMMIT_TRANS,
1135 };
1136 
1137 static void priority_reclaim_metadata_space(struct btrfs_fs_info *fs_info,
1138 				struct btrfs_space_info *space_info,
1139 				struct reserve_ticket *ticket,
1140 				const enum btrfs_flush_state *states,
1141 				int states_nr)
1142 {
1143 	u64 to_reclaim;
1144 	int flush_state;
1145 
1146 	spin_lock(&space_info->lock);
1147 	to_reclaim = btrfs_calc_reclaim_metadata_size(fs_info, space_info);
1148 	if (!to_reclaim) {
1149 		spin_unlock(&space_info->lock);
1150 		return;
1151 	}
1152 	spin_unlock(&space_info->lock);
1153 
1154 	flush_state = 0;
1155 	do {
1156 		flush_space(fs_info, space_info, to_reclaim, states[flush_state]);
1157 		flush_state++;
1158 		spin_lock(&space_info->lock);
1159 		if (ticket->bytes == 0) {
1160 			spin_unlock(&space_info->lock);
1161 			return;
1162 		}
1163 		spin_unlock(&space_info->lock);
1164 	} while (flush_state < states_nr);
1165 }
1166 
1167 static void priority_reclaim_data_space(struct btrfs_fs_info *fs_info,
1168 					struct btrfs_space_info *space_info,
1169 					struct reserve_ticket *ticket)
1170 {
1171 	while (!space_info->full) {
1172 		flush_space(fs_info, space_info, U64_MAX, ALLOC_CHUNK_FORCE);
1173 		spin_lock(&space_info->lock);
1174 		if (ticket->bytes == 0) {
1175 			spin_unlock(&space_info->lock);
1176 			return;
1177 		}
1178 		spin_unlock(&space_info->lock);
1179 	}
1180 }
1181 
1182 static void wait_reserve_ticket(struct btrfs_fs_info *fs_info,
1183 				struct btrfs_space_info *space_info,
1184 				struct reserve_ticket *ticket)
1185 
1186 {
1187 	DEFINE_WAIT(wait);
1188 	int ret = 0;
1189 
1190 	spin_lock(&space_info->lock);
1191 	while (ticket->bytes > 0 && ticket->error == 0) {
1192 		ret = prepare_to_wait_event(&ticket->wait, &wait, TASK_KILLABLE);
1193 		if (ret) {
1194 			/*
1195 			 * Delete us from the list. After we unlock the space
1196 			 * info, we don't want the async reclaim job to reserve
1197 			 * space for this ticket. If that would happen, then the
1198 			 * ticket's task would not known that space was reserved
1199 			 * despite getting an error, resulting in a space leak
1200 			 * (bytes_may_use counter of our space_info).
1201 			 */
1202 			remove_ticket(space_info, ticket);
1203 			ticket->error = -EINTR;
1204 			break;
1205 		}
1206 		spin_unlock(&space_info->lock);
1207 
1208 		schedule();
1209 
1210 		finish_wait(&ticket->wait, &wait);
1211 		spin_lock(&space_info->lock);
1212 	}
1213 	spin_unlock(&space_info->lock);
1214 }
1215 
1216 /**
1217  * handle_reserve_ticket - do the appropriate flushing and waiting for a ticket
1218  * @fs_info - the fs
1219  * @space_info - the space_info for the reservation
1220  * @ticket - the ticket for the reservation
1221  * @flush - how much we can flush
1222  *
1223  * This does the work of figuring out how to flush for the ticket, waiting for
1224  * the reservation, and returning the appropriate error if there is one.
1225  */
1226 static int handle_reserve_ticket(struct btrfs_fs_info *fs_info,
1227 				 struct btrfs_space_info *space_info,
1228 				 struct reserve_ticket *ticket,
1229 				 enum btrfs_reserve_flush_enum flush)
1230 {
1231 	int ret;
1232 
1233 	switch (flush) {
1234 	case BTRFS_RESERVE_FLUSH_DATA:
1235 	case BTRFS_RESERVE_FLUSH_ALL:
1236 	case BTRFS_RESERVE_FLUSH_ALL_STEAL:
1237 		wait_reserve_ticket(fs_info, space_info, ticket);
1238 		break;
1239 	case BTRFS_RESERVE_FLUSH_LIMIT:
1240 		priority_reclaim_metadata_space(fs_info, space_info, ticket,
1241 						priority_flush_states,
1242 						ARRAY_SIZE(priority_flush_states));
1243 		break;
1244 	case BTRFS_RESERVE_FLUSH_EVICT:
1245 		priority_reclaim_metadata_space(fs_info, space_info, ticket,
1246 						evict_flush_states,
1247 						ARRAY_SIZE(evict_flush_states));
1248 		break;
1249 	case BTRFS_RESERVE_FLUSH_FREE_SPACE_INODE:
1250 		priority_reclaim_data_space(fs_info, space_info, ticket);
1251 		break;
1252 	default:
1253 		ASSERT(0);
1254 		break;
1255 	}
1256 
1257 	spin_lock(&space_info->lock);
1258 	ret = ticket->error;
1259 	if (ticket->bytes || ticket->error) {
1260 		/*
1261 		 * We were a priority ticket, so we need to delete ourselves
1262 		 * from the list.  Because we could have other priority tickets
1263 		 * behind us that require less space, run
1264 		 * btrfs_try_granting_tickets() to see if their reservations can
1265 		 * now be made.
1266 		 */
1267 		if (!list_empty(&ticket->list)) {
1268 			remove_ticket(space_info, ticket);
1269 			btrfs_try_granting_tickets(fs_info, space_info);
1270 		}
1271 
1272 		if (!ret)
1273 			ret = -ENOSPC;
1274 	}
1275 	spin_unlock(&space_info->lock);
1276 	ASSERT(list_empty(&ticket->list));
1277 	/*
1278 	 * Check that we can't have an error set if the reservation succeeded,
1279 	 * as that would confuse tasks and lead them to error out without
1280 	 * releasing reserved space (if an error happens the expectation is that
1281 	 * space wasn't reserved at all).
1282 	 */
1283 	ASSERT(!(ticket->bytes == 0 && ticket->error));
1284 	return ret;
1285 }
1286 
1287 /*
1288  * This returns true if this flush state will go through the ordinary flushing
1289  * code.
1290  */
1291 static inline bool is_normal_flushing(enum btrfs_reserve_flush_enum flush)
1292 {
1293 	return	(flush == BTRFS_RESERVE_FLUSH_ALL) ||
1294 		(flush == BTRFS_RESERVE_FLUSH_ALL_STEAL);
1295 }
1296 
1297 /**
1298  * reserve_metadata_bytes - try to reserve bytes from the block_rsv's space
1299  * @root - the root we're allocating for
1300  * @space_info - the space info we want to allocate from
1301  * @orig_bytes - the number of bytes we want
1302  * @flush - whether or not we can flush to make our reservation
1303  *
1304  * This will reserve orig_bytes number of bytes from the space info associated
1305  * with the block_rsv.  If there is not enough space it will make an attempt to
1306  * flush out space to make room.  It will do this by flushing delalloc if
1307  * possible or committing the transaction.  If flush is 0 then no attempts to
1308  * regain reservations will be made and this will fail if there is not enough
1309  * space already.
1310  */
1311 static int __reserve_bytes(struct btrfs_fs_info *fs_info,
1312 			   struct btrfs_space_info *space_info, u64 orig_bytes,
1313 			   enum btrfs_reserve_flush_enum flush)
1314 {
1315 	struct work_struct *async_work;
1316 	struct reserve_ticket ticket;
1317 	u64 used;
1318 	int ret = 0;
1319 	bool pending_tickets;
1320 
1321 	ASSERT(orig_bytes);
1322 	ASSERT(!current->journal_info || flush != BTRFS_RESERVE_FLUSH_ALL);
1323 
1324 	if (flush == BTRFS_RESERVE_FLUSH_DATA)
1325 		async_work = &fs_info->async_data_reclaim_work;
1326 	else
1327 		async_work = &fs_info->async_reclaim_work;
1328 
1329 	spin_lock(&space_info->lock);
1330 	ret = -ENOSPC;
1331 	used = btrfs_space_info_used(space_info, true);
1332 
1333 	/*
1334 	 * We don't want NO_FLUSH allocations to jump everybody, they can
1335 	 * generally handle ENOSPC in a different way, so treat them the same as
1336 	 * normal flushers when it comes to skipping pending tickets.
1337 	 */
1338 	if (is_normal_flushing(flush) || (flush == BTRFS_RESERVE_NO_FLUSH))
1339 		pending_tickets = !list_empty(&space_info->tickets) ||
1340 			!list_empty(&space_info->priority_tickets);
1341 	else
1342 		pending_tickets = !list_empty(&space_info->priority_tickets);
1343 
1344 	/*
1345 	 * Carry on if we have enough space (short-circuit) OR call
1346 	 * can_overcommit() to ensure we can overcommit to continue.
1347 	 */
1348 	if (!pending_tickets &&
1349 	    ((used + orig_bytes <= space_info->total_bytes) ||
1350 	     btrfs_can_overcommit(fs_info, space_info, orig_bytes, flush))) {
1351 		btrfs_space_info_update_bytes_may_use(fs_info, space_info,
1352 						      orig_bytes);
1353 		ret = 0;
1354 	}
1355 
1356 	/*
1357 	 * If we couldn't make a reservation then setup our reservation ticket
1358 	 * and kick the async worker if it's not already running.
1359 	 *
1360 	 * If we are a priority flusher then we just need to add our ticket to
1361 	 * the list and we will do our own flushing further down.
1362 	 */
1363 	if (ret && flush != BTRFS_RESERVE_NO_FLUSH) {
1364 		ticket.bytes = orig_bytes;
1365 		ticket.error = 0;
1366 		space_info->reclaim_size += ticket.bytes;
1367 		init_waitqueue_head(&ticket.wait);
1368 		ticket.steal = (flush == BTRFS_RESERVE_FLUSH_ALL_STEAL);
1369 		if (flush == BTRFS_RESERVE_FLUSH_ALL ||
1370 		    flush == BTRFS_RESERVE_FLUSH_ALL_STEAL ||
1371 		    flush == BTRFS_RESERVE_FLUSH_DATA) {
1372 			list_add_tail(&ticket.list, &space_info->tickets);
1373 			if (!space_info->flush) {
1374 				space_info->flush = 1;
1375 				trace_btrfs_trigger_flush(fs_info,
1376 							  space_info->flags,
1377 							  orig_bytes, flush,
1378 							  "enospc");
1379 				queue_work(system_unbound_wq, async_work);
1380 			}
1381 		} else {
1382 			list_add_tail(&ticket.list,
1383 				      &space_info->priority_tickets);
1384 		}
1385 	} else if (!ret && space_info->flags & BTRFS_BLOCK_GROUP_METADATA) {
1386 		used += orig_bytes;
1387 		/*
1388 		 * We will do the space reservation dance during log replay,
1389 		 * which means we won't have fs_info->fs_root set, so don't do
1390 		 * the async reclaim as we will panic.
1391 		 */
1392 		if (!test_bit(BTRFS_FS_LOG_RECOVERING, &fs_info->flags) &&
1393 		    need_do_async_reclaim(fs_info, space_info, used) &&
1394 		    !work_busy(&fs_info->async_reclaim_work)) {
1395 			trace_btrfs_trigger_flush(fs_info, space_info->flags,
1396 						  orig_bytes, flush, "preempt");
1397 			queue_work(system_unbound_wq,
1398 				   &fs_info->async_reclaim_work);
1399 		}
1400 	}
1401 	spin_unlock(&space_info->lock);
1402 	if (!ret || flush == BTRFS_RESERVE_NO_FLUSH)
1403 		return ret;
1404 
1405 	return handle_reserve_ticket(fs_info, space_info, &ticket, flush);
1406 }
1407 
1408 /**
1409  * reserve_metadata_bytes - try to reserve bytes from the block_rsv's space
1410  * @root - the root we're allocating for
1411  * @block_rsv - the block_rsv we're allocating for
1412  * @orig_bytes - the number of bytes we want
1413  * @flush - whether or not we can flush to make our reservation
1414  *
1415  * This will reserve orig_bytes number of bytes from the space info associated
1416  * with the block_rsv.  If there is not enough space it will make an attempt to
1417  * flush out space to make room.  It will do this by flushing delalloc if
1418  * possible or committing the transaction.  If flush is 0 then no attempts to
1419  * regain reservations will be made and this will fail if there is not enough
1420  * space already.
1421  */
1422 int btrfs_reserve_metadata_bytes(struct btrfs_root *root,
1423 				 struct btrfs_block_rsv *block_rsv,
1424 				 u64 orig_bytes,
1425 				 enum btrfs_reserve_flush_enum flush)
1426 {
1427 	struct btrfs_fs_info *fs_info = root->fs_info;
1428 	struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
1429 	int ret;
1430 
1431 	ret = __reserve_bytes(fs_info, block_rsv->space_info, orig_bytes, flush);
1432 	if (ret == -ENOSPC &&
1433 	    unlikely(root->orphan_cleanup_state == ORPHAN_CLEANUP_STARTED)) {
1434 		if (block_rsv != global_rsv &&
1435 		    !btrfs_block_rsv_use_bytes(global_rsv, orig_bytes))
1436 			ret = 0;
1437 	}
1438 	if (ret == -ENOSPC) {
1439 		trace_btrfs_space_reservation(fs_info, "space_info:enospc",
1440 					      block_rsv->space_info->flags,
1441 					      orig_bytes, 1);
1442 
1443 		if (btrfs_test_opt(fs_info, ENOSPC_DEBUG))
1444 			btrfs_dump_space_info(fs_info, block_rsv->space_info,
1445 					      orig_bytes, 0);
1446 	}
1447 	return ret;
1448 }
1449 
1450 /**
1451  * btrfs_reserve_data_bytes - try to reserve data bytes for an allocation
1452  * @fs_info - the filesystem
1453  * @bytes - the number of bytes we need
1454  * @flush - how we are allowed to flush
1455  *
1456  * This will reserve bytes from the data space info.  If there is not enough
1457  * space then we will attempt to flush space as specified by flush.
1458  */
1459 int btrfs_reserve_data_bytes(struct btrfs_fs_info *fs_info, u64 bytes,
1460 			     enum btrfs_reserve_flush_enum flush)
1461 {
1462 	struct btrfs_space_info *data_sinfo = fs_info->data_sinfo;
1463 	int ret;
1464 
1465 	ASSERT(flush == BTRFS_RESERVE_FLUSH_DATA ||
1466 	       flush == BTRFS_RESERVE_FLUSH_FREE_SPACE_INODE);
1467 	ASSERT(!current->journal_info || flush != BTRFS_RESERVE_FLUSH_DATA);
1468 
1469 	ret = __reserve_bytes(fs_info, data_sinfo, bytes, flush);
1470 	if (ret == -ENOSPC) {
1471 		trace_btrfs_space_reservation(fs_info, "space_info:enospc",
1472 					      data_sinfo->flags, bytes, 1);
1473 		if (btrfs_test_opt(fs_info, ENOSPC_DEBUG))
1474 			btrfs_dump_space_info(fs_info, data_sinfo, bytes, 0);
1475 	}
1476 	return ret;
1477 }
1478