xref: /linux/fs/btrfs/free-space-cache.c (revision 28933a094ea7843fd5fd77c5d79190e6fd564f0b)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2008 Red Hat.  All rights reserved.
4  */
5 
6 #include <linux/pagemap.h>
7 #include <linux/sched.h>
8 #include <linux/sched/signal.h>
9 #include <linux/slab.h>
10 #include <linux/math64.h>
11 #include <linux/ratelimit.h>
12 #include <linux/sched/mm.h>
13 #include <linux/string_choices.h>
14 #include "extent-tree.h"
15 #include "fs.h"
16 #include "messages.h"
17 #include "misc.h"
18 #include "free-space-cache.h"
19 #include "transaction.h"
20 #include "disk-io.h"
21 #include "extent_io.h"
22 #include "space-info.h"
23 #include "block-group.h"
24 #include "discard.h"
25 #include "inode-item.h"
26 #include "accessors.h"
27 #include "file-item.h"
28 #include "file.h"
29 #include "super.h"
30 #include "relocation.h"
31 
32 #define BITS_PER_BITMAP		(PAGE_SIZE * 8UL)
33 #define MAX_CACHE_BYTES_PER_GIG	SZ_64K
34 #define FORCE_EXTENT_THRESHOLD	SZ_1M
35 
36 static struct kmem_cache *btrfs_free_space_cachep;
37 static struct kmem_cache *btrfs_free_space_bitmap_cachep;
38 
39 static int link_free_space(struct btrfs_free_space_ctl *ctl,
40 			   struct btrfs_free_space *info);
41 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
42 			      struct btrfs_free_space *info, bool update_stat);
43 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
44 			 struct btrfs_free_space *bitmap_info, u64 *offset,
45 			 u64 *bytes, bool for_alloc);
46 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
47 			struct btrfs_free_space *bitmap_info);
48 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
49 			      struct btrfs_free_space *info, u64 offset,
50 			      u64 bytes, bool update_stats);
51 
52 static void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
53 {
54 	struct btrfs_free_space *info;
55 	struct rb_node *node;
56 
57 	while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
58 		info = rb_entry(node, struct btrfs_free_space, offset_index);
59 		if (!info->bitmap) {
60 			unlink_free_space(ctl, info, true);
61 			kmem_cache_free(btrfs_free_space_cachep, info);
62 		} else {
63 			free_bitmap(ctl, info);
64 		}
65 
66 		cond_resched_lock(&ctl->tree_lock);
67 	}
68 }
69 
70 static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
71 					       struct btrfs_path *path,
72 					       u64 offset)
73 {
74 	struct btrfs_key key;
75 	struct btrfs_key location;
76 	struct btrfs_disk_key disk_key;
77 	struct btrfs_free_space_header *header;
78 	struct extent_buffer *leaf;
79 	struct btrfs_inode *inode;
80 	unsigned nofs_flag;
81 	int ret;
82 
83 	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
84 	key.type = 0;
85 	key.offset = offset;
86 
87 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
88 	if (ret < 0)
89 		return ERR_PTR(ret);
90 	if (ret > 0) {
91 		btrfs_release_path(path);
92 		return ERR_PTR(-ENOENT);
93 	}
94 
95 	leaf = path->nodes[0];
96 	header = btrfs_item_ptr(leaf, path->slots[0],
97 				struct btrfs_free_space_header);
98 	btrfs_free_space_key(leaf, header, &disk_key);
99 	btrfs_disk_key_to_cpu(&location, &disk_key);
100 	btrfs_release_path(path);
101 
102 	/*
103 	 * We are often under a trans handle at this point, so we need to make
104 	 * sure NOFS is set to keep us from deadlocking.
105 	 */
106 	nofs_flag = memalloc_nofs_save();
107 	inode = btrfs_iget_path(location.objectid, root, path);
108 	btrfs_release_path(path);
109 	memalloc_nofs_restore(nofs_flag);
110 	if (IS_ERR(inode))
111 		return ERR_CAST(inode);
112 
113 	return &inode->vfs_inode;
114 }
115 
116 struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group,
117 		struct btrfs_path *path)
118 {
119 	struct btrfs_fs_info *fs_info = block_group->fs_info;
120 	struct inode *inode = NULL;
121 
122 	spin_lock(&block_group->lock);
123 	if (block_group->inode)
124 		inode = igrab(&block_group->inode->vfs_inode);
125 	spin_unlock(&block_group->lock);
126 	if (inode)
127 		return inode;
128 
129 	inode = __lookup_free_space_inode(fs_info->tree_root, path,
130 					  block_group->start);
131 	if (IS_ERR(inode))
132 		return inode;
133 
134 	spin_lock(&block_group->lock);
135 	if (!test_and_set_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags))
136 		block_group->inode = BTRFS_I(igrab(inode));
137 	spin_unlock(&block_group->lock);
138 
139 	return inode;
140 }
141 
142 /*
143  * inode is an optional sink: if it is NULL, btrfs_remove_free_space_inode
144  * handles lookup, otherwise it takes ownership and iputs the inode.
145  * Don't reuse an inode pointer after passing it into this function.
146  */
147 int btrfs_remove_free_space_inode(struct btrfs_trans_handle *trans,
148 				  struct inode *inode,
149 				  struct btrfs_block_group *block_group)
150 {
151 	BTRFS_PATH_AUTO_FREE(path);
152 	struct btrfs_key key;
153 	int ret = 0;
154 
155 	path = btrfs_alloc_path();
156 	if (!path)
157 		return -ENOMEM;
158 
159 	if (!inode)
160 		inode = lookup_free_space_inode(block_group, path);
161 	if (IS_ERR(inode)) {
162 		if (PTR_ERR(inode) != -ENOENT)
163 			ret = PTR_ERR(inode);
164 		return ret;
165 	}
166 	ret = btrfs_orphan_add(trans, BTRFS_I(inode));
167 	if (ret) {
168 		btrfs_add_delayed_iput(BTRFS_I(inode));
169 		return ret;
170 	}
171 	clear_nlink(inode);
172 	/*
173 	 * Persist the zero link count, so that if the delayed iput below
174 	 * doesn't get to evict the inode, the orphan cleanup on the next mount
175 	 * evicts it instead of only deleting the orphan item.
176 	 */
177 	ret = btrfs_update_inode(trans, BTRFS_I(inode));
178 	if (ret) {
179 		btrfs_add_delayed_iput(BTRFS_I(inode));
180 		return ret;
181 	}
182 	/* One for the block groups ref */
183 	spin_lock(&block_group->lock);
184 	if (test_and_clear_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags)) {
185 		block_group->inode = NULL;
186 		spin_unlock(&block_group->lock);
187 		iput(inode);
188 	} else {
189 		spin_unlock(&block_group->lock);
190 	}
191 	/* One for the lookup ref */
192 	btrfs_add_delayed_iput(BTRFS_I(inode));
193 
194 	key.objectid = BTRFS_FREE_SPACE_OBJECTID;
195 	key.type = 0;
196 	key.offset = block_group->start;
197 	ret = btrfs_search_slot(trans, trans->fs_info->tree_root, &key, path,
198 				-1, 1);
199 	if (ret) {
200 		if (ret > 0)
201 			ret = 0;
202 		return ret;
203 	}
204 	return btrfs_del_item(trans, trans->fs_info->tree_root, path);
205 }
206 
207 int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans,
208 				    struct inode *vfs_inode)
209 {
210 	struct btrfs_truncate_control control = {
211 		.inode = BTRFS_I(vfs_inode),
212 		.new_size = 0,
213 		.ino = btrfs_ino(BTRFS_I(vfs_inode)),
214 		.min_type = BTRFS_EXTENT_DATA_KEY,
215 		.clear_extent_range = true,
216 	};
217 	struct btrfs_inode *inode = BTRFS_I(vfs_inode);
218 	struct btrfs_root *root = inode->root;
219 	struct extent_state *cached_state = NULL;
220 	int ret = 0;
221 
222 	btrfs_i_size_write(inode, 0);
223 	truncate_pagecache(vfs_inode, 0);
224 
225 	btrfs_lock_extent(&inode->io_tree, 0, (u64)-1, &cached_state);
226 	btrfs_drop_extent_map_range(inode, 0, (u64)-1, false);
227 
228 	/*
229 	 * We skip the throttling logic for free space cache inodes, so we don't
230 	 * need to check for -EAGAIN.
231 	 */
232 	ret = btrfs_truncate_inode_items(trans, root, &control);
233 
234 	inode_sub_bytes(&inode->vfs_inode, control.sub_bytes);
235 	btrfs_inode_safe_disk_i_size_write(inode, control.last_size);
236 
237 	btrfs_unlock_extent(&inode->io_tree, 0, (u64)-1, &cached_state);
238 	if (ret)
239 		goto fail;
240 
241 	ret = btrfs_update_inode(trans, inode);
242 
243 fail:
244 	if (ret)
245 		btrfs_abort_transaction(trans, ret);
246 
247 	return ret;
248 }
249 
250 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
251 {
252 	struct btrfs_block_group *block_group = ctl->block_group;
253 	const int unit = block_group->fs_info->sectorsize;
254 	u64 max_bytes;
255 	u64 bitmap_bytes;
256 	u64 extent_bytes;
257 	u64 size = block_group->length;
258 	u64 bytes_per_bg = BITS_PER_BITMAP * unit;
259 	u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
260 
261 	max_bitmaps = max_t(u64, max_bitmaps, 1);
262 
263 	if (ctl->total_bitmaps > max_bitmaps)
264 		btrfs_err(block_group->fs_info,
265 "invalid free space control: bg start=%llu len=%llu total_bitmaps=%u unit=%u max_bitmaps=%llu bytes_per_bg=%llu",
266 			  block_group->start, block_group->length,
267 			  ctl->total_bitmaps, unit, max_bitmaps,
268 			  bytes_per_bg);
269 	ASSERT(ctl->total_bitmaps <= max_bitmaps);
270 
271 	/*
272 	 * We are trying to keep the total amount of memory used per 1GiB of
273 	 * space to be MAX_CACHE_BYTES_PER_GIG.  However, with a reclamation
274 	 * mechanism of pulling extents >= FORCE_EXTENT_THRESHOLD out of
275 	 * bitmaps, we may end up using more memory than this.
276 	 */
277 	if (size < SZ_1G)
278 		max_bytes = MAX_CACHE_BYTES_PER_GIG;
279 	else
280 		max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);
281 
282 	bitmap_bytes = ctl->total_bitmaps * unit;
283 
284 	/*
285 	 * we want the extent entry threshold to always be at most 1/2 the max
286 	 * bytes we can have, or whatever is less than that.
287 	 */
288 	extent_bytes = max_bytes - bitmap_bytes;
289 	extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1);
290 
291 	ctl->extents_thresh =
292 		div_u64(extent_bytes, sizeof(struct btrfs_free_space));
293 }
294 
295 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
296 					  u64 offset)
297 {
298 	ASSERT(offset >= bitmap_start);
299 	offset -= bitmap_start;
300 	return (unsigned long)(div_u64(offset, unit));
301 }
302 
303 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
304 {
305 	return (unsigned long)(div_u64(bytes, unit));
306 }
307 
308 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
309 				   u64 offset)
310 {
311 	u64 bitmap_start;
312 	u64 bytes_per_bitmap;
313 
314 	bytes_per_bitmap = BITS_PER_BITMAP * ctl->block_group->fs_info->sectorsize;
315 	bitmap_start = offset - ctl->block_group->start;
316 	bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
317 	bitmap_start *= bytes_per_bitmap;
318 	bitmap_start += ctl->block_group->start;
319 
320 	return bitmap_start;
321 }
322 
323 static int tree_insert_offset(struct btrfs_free_space_ctl *ctl,
324 			      struct btrfs_free_cluster *cluster,
325 			      struct btrfs_free_space *new_entry)
326 {
327 	struct rb_root *root;
328 	struct rb_node **p;
329 	struct rb_node *parent = NULL;
330 
331 	lockdep_assert_held(&ctl->tree_lock);
332 
333 	if (cluster) {
334 		lockdep_assert_held(&cluster->lock);
335 		root = &cluster->root;
336 	} else {
337 		root = &ctl->free_space_offset;
338 	}
339 
340 	p = &root->rb_node;
341 
342 	while (*p) {
343 		struct btrfs_free_space *info;
344 
345 		parent = *p;
346 		info = rb_entry(parent, struct btrfs_free_space, offset_index);
347 
348 		if (new_entry->offset < info->offset) {
349 			p = &(*p)->rb_left;
350 		} else if (new_entry->offset > info->offset) {
351 			p = &(*p)->rb_right;
352 		} else {
353 			/*
354 			 * we could have a bitmap entry and an extent entry
355 			 * share the same offset.  If this is the case, we want
356 			 * the extent entry to always be found first if we do a
357 			 * linear search through the tree, since we want to have
358 			 * the quickest allocation time, and allocating from an
359 			 * extent is faster than allocating from a bitmap.  So
360 			 * if we're inserting a bitmap and we find an entry at
361 			 * this offset, we want to go right, or after this entry
362 			 * logically.  If we are inserting an extent and we've
363 			 * found a bitmap, we want to go left, or before
364 			 * logically.
365 			 */
366 			if (new_entry->bitmap) {
367 				if (info->bitmap) {
368 					WARN_ON_ONCE(1);
369 					return -EEXIST;
370 				}
371 				p = &(*p)->rb_right;
372 			} else {
373 				if (!info->bitmap) {
374 					WARN_ON_ONCE(1);
375 					return -EEXIST;
376 				}
377 				p = &(*p)->rb_left;
378 			}
379 		}
380 	}
381 
382 	rb_link_node(&new_entry->offset_index, parent, p);
383 	rb_insert_color(&new_entry->offset_index, root);
384 
385 	return 0;
386 }
387 
388 /*
389  * This is a little subtle.  We *only* have ->max_extent_size set if we actually
390  * searched through the bitmap and figured out the largest ->max_extent_size,
391  * otherwise it's 0.  In the case that it's 0 we don't want to tell the
392  * allocator the wrong thing, we want to use the actual real max_extent_size
393  * we've found already if it's larger, or we want to use ->bytes.
394  *
395  * This matters because find_free_space() will skip entries who's ->bytes is
396  * less than the required bytes.  So if we didn't search down this bitmap, we
397  * may pick some previous entry that has a smaller ->max_extent_size than we
398  * have.  For example, assume we have two entries, one that has
399  * ->max_extent_size set to 4K and ->bytes set to 1M.  A second entry hasn't set
400  * ->max_extent_size yet, has ->bytes set to 8K and it's contiguous.  We will
401  *  call into find_free_space(), and return with max_extent_size == 4K, because
402  *  that first bitmap entry had ->max_extent_size set, but the second one did
403  *  not.  If instead we returned 8K we'd come in searching for 8K, and find the
404  *  8K contiguous range.
405  *
406  *  Consider the other case, we have 2 8K chunks in that second entry and still
407  *  don't have ->max_extent_size set.  We'll return 16K, and the next time the
408  *  allocator comes in it'll fully search our second bitmap, and this time it'll
409  *  get an uptodate value of 8K as the maximum chunk size.  Then we'll get the
410  *  right allocation the next loop through.
411  */
412 static inline u64 get_max_extent_size(const struct btrfs_free_space *entry)
413 {
414 	if (entry->bitmap && entry->max_extent_size)
415 		return entry->max_extent_size;
416 	return entry->bytes;
417 }
418 
419 /*
420  * We want the largest entry to be leftmost, so this is inverted from what you'd
421  * normally expect.
422  */
423 static bool entry_less(struct rb_node *node, const struct rb_node *parent)
424 {
425 	const struct btrfs_free_space *entry, *exist;
426 
427 	entry = rb_entry(node, struct btrfs_free_space, bytes_index);
428 	exist = rb_entry(parent, struct btrfs_free_space, bytes_index);
429 	return get_max_extent_size(exist) < get_max_extent_size(entry);
430 }
431 
432 /*
433  * searches the tree for the given offset.
434  *
435  * fuzzy - If this is set, then we are trying to make an allocation, and we just
436  * want a section that has at least bytes size and comes at or after the given
437  * offset.
438  */
439 static struct btrfs_free_space *
440 tree_search_offset(struct btrfs_free_space_ctl *ctl,
441 		   u64 offset, int bitmap_only, int fuzzy)
442 {
443 	struct rb_node *n = ctl->free_space_offset.rb_node;
444 	struct btrfs_free_space *entry = NULL, *prev = NULL;
445 	const int unit = ctl->block_group->fs_info->sectorsize;
446 
447 	lockdep_assert_held(&ctl->tree_lock);
448 
449 	/* find entry that is closest to the 'offset' */
450 	while (n) {
451 		entry = rb_entry(n, struct btrfs_free_space, offset_index);
452 		prev = entry;
453 
454 		if (offset < entry->offset)
455 			n = n->rb_left;
456 		else if (offset > entry->offset)
457 			n = n->rb_right;
458 		else
459 			break;
460 
461 		entry = NULL;
462 	}
463 
464 	if (bitmap_only) {
465 		if (!entry)
466 			return NULL;
467 		if (entry->bitmap)
468 			return entry;
469 
470 		/*
471 		 * bitmap entry and extent entry may share same offset,
472 		 * in that case, bitmap entry comes after extent entry.
473 		 */
474 		n = rb_next(n);
475 		if (!n)
476 			return NULL;
477 		entry = rb_entry(n, struct btrfs_free_space, offset_index);
478 		if (entry->offset != offset)
479 			return NULL;
480 
481 		WARN_ON(!entry->bitmap);
482 		return entry;
483 	} else if (entry) {
484 		if (entry->bitmap) {
485 			/*
486 			 * if previous extent entry covers the offset,
487 			 * we should return it instead of the bitmap entry
488 			 */
489 			n = rb_prev(&entry->offset_index);
490 			if (n) {
491 				prev = rb_entry(n, struct btrfs_free_space,
492 						offset_index);
493 				if (!prev->bitmap &&
494 				    prev->offset + prev->bytes > offset)
495 					entry = prev;
496 			}
497 		}
498 		return entry;
499 	}
500 
501 	if (!prev)
502 		return NULL;
503 
504 	/* find last entry before the 'offset' */
505 	entry = prev;
506 	if (entry->offset > offset) {
507 		n = rb_prev(&entry->offset_index);
508 		if (n) {
509 			entry = rb_entry(n, struct btrfs_free_space,
510 					offset_index);
511 			ASSERT(entry->offset <= offset);
512 		} else {
513 			if (fuzzy)
514 				return entry;
515 			else
516 				return NULL;
517 		}
518 	}
519 
520 	if (entry->bitmap) {
521 		n = rb_prev(&entry->offset_index);
522 		if (n) {
523 			prev = rb_entry(n, struct btrfs_free_space,
524 					offset_index);
525 			if (!prev->bitmap &&
526 			    prev->offset + prev->bytes > offset)
527 				return prev;
528 		}
529 		if (entry->offset + BITS_PER_BITMAP * unit > offset)
530 			return entry;
531 	} else if (entry->offset + entry->bytes > offset)
532 		return entry;
533 
534 	if (!fuzzy)
535 		return NULL;
536 
537 	while (1) {
538 		n = rb_next(&entry->offset_index);
539 		if (!n)
540 			return NULL;
541 		entry = rb_entry(n, struct btrfs_free_space, offset_index);
542 		if (entry->bitmap) {
543 			if (entry->offset + BITS_PER_BITMAP * unit > offset)
544 				break;
545 		} else {
546 			if (entry->offset + entry->bytes > offset)
547 				break;
548 		}
549 	}
550 	return entry;
551 }
552 
553 static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl,
554 				     struct btrfs_free_space *info,
555 				     bool update_stat)
556 {
557 	lockdep_assert_held(&ctl->tree_lock);
558 
559 	rb_erase(&info->offset_index, &ctl->free_space_offset);
560 	rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);
561 	ctl->free_extents--;
562 
563 	if (!info->bitmap && !btrfs_free_space_trimmed(info)) {
564 		ctl->discardable_extents[BTRFS_STAT_CURR]--;
565 		ctl->discardable_bytes[BTRFS_STAT_CURR] -= info->bytes;
566 	}
567 
568 	if (update_stat)
569 		ctl->free_space -= info->bytes;
570 }
571 
572 static int link_free_space(struct btrfs_free_space_ctl *ctl,
573 			   struct btrfs_free_space *info)
574 {
575 	int ret = 0;
576 
577 	lockdep_assert_held(&ctl->tree_lock);
578 
579 	ASSERT(info->bytes || info->bitmap);
580 	ret = tree_insert_offset(ctl, NULL, info);
581 	if (ret)
582 		return ret;
583 
584 	rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);
585 
586 	if (!info->bitmap && !btrfs_free_space_trimmed(info)) {
587 		ctl->discardable_extents[BTRFS_STAT_CURR]++;
588 		ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
589 	}
590 
591 	ctl->free_space += info->bytes;
592 	ctl->free_extents++;
593 	return ret;
594 }
595 
596 static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl,
597 				struct btrfs_free_space *info)
598 {
599 	ASSERT(info->bitmap);
600 
601 	/*
602 	 * If our entry is empty it's because we're on a cluster and we don't
603 	 * want to re-link it into our ctl bytes index.
604 	 */
605 	if (RB_EMPTY_NODE(&info->bytes_index))
606 		return;
607 
608 	lockdep_assert_held(&ctl->tree_lock);
609 
610 	rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);
611 	rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);
612 }
613 
614 static inline void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
615 				     struct btrfs_free_space *info,
616 				     u64 offset, u64 bytes, bool update_stat)
617 {
618 	const int unit = ctl->block_group->fs_info->sectorsize;
619 	unsigned long start, count, end;
620 	int extent_delta = -1;
621 
622 	start = offset_to_bit(info->offset, unit, offset);
623 	count = bytes_to_bits(bytes, unit);
624 	end = start + count;
625 	ASSERT(end <= BITS_PER_BITMAP);
626 
627 	bitmap_clear(info->bitmap, start, count);
628 
629 	info->bytes -= bytes;
630 	if (info->max_extent_size > unit)
631 		info->max_extent_size = 0;
632 
633 	relink_bitmap_entry(ctl, info);
634 
635 	if (start && test_bit(start - 1, info->bitmap))
636 		extent_delta++;
637 
638 	if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))
639 		extent_delta++;
640 
641 	info->bitmap_extents += extent_delta;
642 	if (!btrfs_free_space_trimmed(info)) {
643 		ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
644 		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
645 	}
646 
647 	if (update_stat)
648 		ctl->free_space -= bytes;
649 }
650 
651 static void btrfs_bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
652 				  struct btrfs_free_space *info, u64 offset,
653 				  u64 bytes)
654 {
655 	const int unit = ctl->block_group->fs_info->sectorsize;
656 	unsigned long start, count, end;
657 	int extent_delta = 1;
658 
659 	start = offset_to_bit(info->offset, unit, offset);
660 	count = bytes_to_bits(bytes, unit);
661 	end = start + count;
662 	ASSERT(end <= BITS_PER_BITMAP);
663 
664 	bitmap_set(info->bitmap, start, count);
665 
666 	/*
667 	 * We set some bytes, we have no idea what the max extent size is
668 	 * anymore.
669 	 */
670 	info->max_extent_size = 0;
671 	info->bytes += bytes;
672 	ctl->free_space += bytes;
673 
674 	relink_bitmap_entry(ctl, info);
675 
676 	if (start && test_bit(start - 1, info->bitmap))
677 		extent_delta--;
678 
679 	if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))
680 		extent_delta--;
681 
682 	info->bitmap_extents += extent_delta;
683 	if (!btrfs_free_space_trimmed(info)) {
684 		ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
685 		ctl->discardable_bytes[BTRFS_STAT_CURR] += bytes;
686 	}
687 }
688 
689 /*
690  * If we can not find suitable extent, we will use bytes to record
691  * the size of the max extent.
692  */
693 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
694 			 struct btrfs_free_space *bitmap_info, u64 *offset,
695 			 u64 *bytes, bool for_alloc)
696 {
697 	const int unit = ctl->block_group->fs_info->sectorsize;
698 	unsigned long found_bits = 0;
699 	unsigned long max_bits = 0;
700 	unsigned long bits, i;
701 	unsigned long next_zero;
702 	unsigned long extent_bits;
703 
704 	/*
705 	 * Skip searching the bitmap if we don't have a contiguous section that
706 	 * is large enough for this allocation.
707 	 */
708 	if (for_alloc &&
709 	    bitmap_info->max_extent_size &&
710 	    bitmap_info->max_extent_size < *bytes) {
711 		*bytes = bitmap_info->max_extent_size;
712 		return -1;
713 	}
714 
715 	i = offset_to_bit(bitmap_info->offset, unit,
716 			  max_t(u64, *offset, bitmap_info->offset));
717 	bits = bytes_to_bits(*bytes, unit);
718 
719 	for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
720 		if (for_alloc && bits == 1) {
721 			found_bits = 1;
722 			break;
723 		}
724 		next_zero = find_next_zero_bit(bitmap_info->bitmap,
725 					       BITS_PER_BITMAP, i);
726 		extent_bits = next_zero - i;
727 		if (extent_bits >= bits) {
728 			found_bits = extent_bits;
729 			break;
730 		} else if (extent_bits > max_bits) {
731 			max_bits = extent_bits;
732 		}
733 		i = next_zero;
734 	}
735 
736 	if (found_bits) {
737 		*offset = (u64)(i * unit) + bitmap_info->offset;
738 		*bytes = (u64)(found_bits) * unit;
739 		return 0;
740 	}
741 
742 	*bytes = (u64)(max_bits) * unit;
743 	bitmap_info->max_extent_size = *bytes;
744 	relink_bitmap_entry(ctl, bitmap_info);
745 	return -1;
746 }
747 
748 /* Cache the size of the max extent in bytes */
749 static struct btrfs_free_space *
750 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
751 		unsigned long align, u64 *max_extent_size, bool use_bytes_index)
752 {
753 	struct btrfs_free_space *entry;
754 	struct rb_node *node;
755 	u64 tmp;
756 	u64 align_off;
757 	int ret;
758 
759 	if (!ctl->free_space_offset.rb_node)
760 		return NULL;
761 again:
762 	if (use_bytes_index) {
763 		node = rb_first_cached(&ctl->free_space_bytes);
764 	} else {
765 		entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset),
766 					   0, 1);
767 		if (!entry)
768 			return NULL;
769 		node = &entry->offset_index;
770 	}
771 
772 	for (; node; node = rb_next(node)) {
773 		if (use_bytes_index)
774 			entry = rb_entry(node, struct btrfs_free_space,
775 					 bytes_index);
776 		else
777 			entry = rb_entry(node, struct btrfs_free_space,
778 					 offset_index);
779 
780 		/*
781 		 * If we are using the bytes index then all subsequent entries
782 		 * in this tree are going to be < bytes, so simply set the max
783 		 * extent size and exit the loop.
784 		 *
785 		 * If we're using the offset index then we need to keep going
786 		 * through the rest of the tree.
787 		 */
788 		if (entry->bytes < *bytes) {
789 			*max_extent_size = max(get_max_extent_size(entry),
790 					       *max_extent_size);
791 			if (use_bytes_index)
792 				break;
793 			continue;
794 		}
795 
796 		/* make sure the space returned is big enough
797 		 * to match our requested alignment
798 		 */
799 		if (*bytes >= align) {
800 			tmp = entry->offset - ctl->block_group->start + align - 1;
801 			tmp = div64_u64(tmp, align);
802 			tmp = tmp * align + ctl->block_group->start;
803 			align_off = tmp - entry->offset;
804 		} else {
805 			align_off = 0;
806 			tmp = entry->offset;
807 		}
808 
809 		/*
810 		 * We don't break here if we're using the bytes index because we
811 		 * may have another entry that has the correct alignment that is
812 		 * the right size, so we don't want to miss that possibility.
813 		 * At worst this adds another loop through the logic, but if we
814 		 * broke here we could prematurely ENOSPC.
815 		 */
816 		if (entry->bytes < *bytes + align_off) {
817 			*max_extent_size = max(get_max_extent_size(entry),
818 					       *max_extent_size);
819 			continue;
820 		}
821 
822 		if (entry->bitmap) {
823 			struct rb_node *old_next = rb_next(node);
824 			u64 size = *bytes;
825 
826 			ret = search_bitmap(ctl, entry, &tmp, &size, true);
827 			if (!ret) {
828 				*offset = tmp;
829 				*bytes = size;
830 				return entry;
831 			} else {
832 				*max_extent_size =
833 					max(get_max_extent_size(entry),
834 					    *max_extent_size);
835 			}
836 
837 			/*
838 			 * The bitmap may have gotten re-arranged in the space
839 			 * index here because the max_extent_size may have been
840 			 * updated.  Start from the beginning again if this
841 			 * happened.
842 			 */
843 			if (use_bytes_index && old_next != rb_next(node))
844 				goto again;
845 			continue;
846 		}
847 
848 		*offset = tmp;
849 		*bytes = entry->bytes - align_off;
850 		return entry;
851 	}
852 
853 	return NULL;
854 }
855 
856 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
857 			   struct btrfs_free_space *info, u64 offset)
858 {
859 	info->offset = offset_to_bitmap(ctl, offset);
860 	info->bytes = 0;
861 	info->bitmap_extents = 0;
862 	INIT_LIST_HEAD(&info->list);
863 	link_free_space(ctl, info);
864 	ctl->total_bitmaps++;
865 	recalculate_thresholds(ctl);
866 }
867 
868 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
869 			struct btrfs_free_space *bitmap_info)
870 {
871 	/*
872 	 * Normally when this is called, the bitmap is completely empty. However,
873 	 * if we are blowing up the free space cache for one reason or another
874 	 * via __btrfs_remove_free_space_cache(), then it may not be freed and
875 	 * we may leave stats on the table.
876 	 */
877 	if (bitmap_info->bytes && !btrfs_free_space_trimmed(bitmap_info)) {
878 		ctl->discardable_extents[BTRFS_STAT_CURR] -=
879 			bitmap_info->bitmap_extents;
880 		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bitmap_info->bytes;
881 
882 	}
883 	unlink_free_space(ctl, bitmap_info, true);
884 	kmem_cache_free(btrfs_free_space_bitmap_cachep, bitmap_info->bitmap);
885 	kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
886 	ctl->total_bitmaps--;
887 	recalculate_thresholds(ctl);
888 }
889 
890 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
891 			      struct btrfs_free_space *bitmap_info,
892 			      u64 *offset, u64 *bytes)
893 {
894 	const int unit = ctl->block_group->fs_info->sectorsize;
895 	u64 end;
896 	u64 search_start, search_bytes;
897 	int ret;
898 
899 again:
900 	end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * unit) - 1;
901 
902 	/*
903 	 * We need to search for bits in this bitmap.  We could only cover some
904 	 * of the extent in this bitmap thanks to how we add space, so we need
905 	 * to search for as much as it as we can and clear that amount, and then
906 	 * go searching for the next bit.
907 	 */
908 	search_start = *offset;
909 	search_bytes = unit;
910 	search_bytes = min(search_bytes, end - search_start + 1);
911 	ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,
912 			    false);
913 	if (ret < 0 || search_start != *offset)
914 		return -EINVAL;
915 
916 	/* We may have found more bits than what we need */
917 	search_bytes = min(search_bytes, *bytes);
918 
919 	/* Cannot clear past the end of the bitmap */
920 	search_bytes = min(search_bytes, end - search_start + 1);
921 
922 	bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes, true);
923 	*offset += search_bytes;
924 	*bytes -= search_bytes;
925 
926 	if (*bytes) {
927 		struct rb_node *next = rb_next(&bitmap_info->offset_index);
928 		if (!bitmap_info->bytes)
929 			free_bitmap(ctl, bitmap_info);
930 
931 		/*
932 		 * no entry after this bitmap, but we still have bytes to
933 		 * remove, so something has gone wrong.
934 		 */
935 		if (!next)
936 			return -EINVAL;
937 
938 		bitmap_info = rb_entry(next, struct btrfs_free_space,
939 				       offset_index);
940 
941 		/*
942 		 * if the next entry isn't a bitmap we need to return to let the
943 		 * extent stuff do its work.
944 		 */
945 		if (!bitmap_info->bitmap)
946 			return -EAGAIN;
947 
948 		/*
949 		 * Ok the next item is a bitmap, but it may not actually hold
950 		 * the information for the rest of this free space stuff, so
951 		 * look for it, and if we don't find it return so we can try
952 		 * everything over again.
953 		 */
954 		search_start = *offset;
955 		search_bytes = unit;
956 		ret = search_bitmap(ctl, bitmap_info, &search_start,
957 				    &search_bytes, false);
958 		if (ret < 0 || search_start != *offset)
959 			return -EAGAIN;
960 
961 		goto again;
962 	} else if (!bitmap_info->bytes)
963 		free_bitmap(ctl, bitmap_info);
964 
965 	return 0;
966 }
967 
968 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
969 			       struct btrfs_free_space *info, u64 offset,
970 			       u64 bytes, enum btrfs_trim_state trim_state)
971 {
972 	const int unit = ctl->block_group->fs_info->sectorsize;
973 	u64 bytes_to_set = 0;
974 	u64 end;
975 
976 	/*
977 	 * This is a tradeoff to make bitmap trim state minimal.  We mark the
978 	 * whole bitmap untrimmed if at any point we add untrimmed regions.
979 	 */
980 	if (trim_state == BTRFS_TRIM_STATE_UNTRIMMED) {
981 		if (btrfs_free_space_trimmed(info)) {
982 			ctl->discardable_extents[BTRFS_STAT_CURR] +=
983 				info->bitmap_extents;
984 			ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
985 		}
986 		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
987 	}
988 
989 	end = info->offset + (u64)(BITS_PER_BITMAP * unit);
990 
991 	bytes_to_set = min(end - offset, bytes);
992 
993 	btrfs_bitmap_set_bits(ctl, info, offset, bytes_to_set);
994 
995 	return bytes_to_set;
996 
997 }
998 
999 EXPORT_FOR_TESTS
1000 bool btrfs_use_bitmap(struct btrfs_free_space_ctl *ctl,
1001 		      struct btrfs_free_space *info)
1002 {
1003 	struct btrfs_block_group *block_group = ctl->block_group;
1004 	struct btrfs_fs_info *fs_info = block_group->fs_info;
1005 	bool forced = false;
1006 
1007 #ifdef CONFIG_BTRFS_DEBUG
1008 	if (btrfs_should_fragment_free_space(block_group))
1009 		forced = true;
1010 #endif
1011 
1012 	/* This is a way to reclaim large regions from the bitmaps. */
1013 	if (!forced && info->bytes >= FORCE_EXTENT_THRESHOLD)
1014 		return false;
1015 
1016 	/*
1017 	 * If we are below the extents threshold then we can add this as an
1018 	 * extent, and don't have to deal with the bitmap
1019 	 */
1020 	if (!forced && ctl->free_extents < ctl->extents_thresh) {
1021 		/*
1022 		 * If this block group has some small extents we don't want to
1023 		 * use up all of our free slots in the cache with them, we want
1024 		 * to reserve them to larger extents, however if we have plenty
1025 		 * of cache left then go ahead and add them, no sense in adding
1026 		 * the overhead of a bitmap if we don't have to.
1027 		 */
1028 		if (info->bytes <= fs_info->sectorsize * 8) {
1029 			if (ctl->free_extents * 3 <= ctl->extents_thresh)
1030 				return false;
1031 		} else {
1032 			return false;
1033 		}
1034 	}
1035 
1036 	/*
1037 	 * The original block groups from mkfs can be really small, like 8
1038 	 * megabytes, so don't bother with a bitmap for those entries.  However
1039 	 * some block groups can be smaller than what a bitmap would cover but
1040 	 * are still large enough that they could overflow the 32k memory limit,
1041 	 * so allow those block groups to still be allowed to have a bitmap
1042 	 * entry.
1043 	 */
1044 	if (((BITS_PER_BITMAP * fs_info->sectorsize) >> 1) > block_group->length)
1045 		return false;
1046 
1047 	return true;
1048 }
1049 
1050 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
1051 			      struct btrfs_free_space *info)
1052 {
1053 	struct btrfs_free_space *bitmap_info;
1054 	struct btrfs_block_group *block_group = ctl->block_group;
1055 	bool added = false;
1056 	u64 bytes, offset, bytes_added;
1057 	enum btrfs_trim_state trim_state;
1058 	int ret;
1059 
1060 	bytes = info->bytes;
1061 	offset = info->offset;
1062 	trim_state = info->trim_state;
1063 
1064 	if (btrfs_is_testing(block_group->fs_info)) {
1065 		if (!block_group->fs_info->use_bitmap(ctl, info))
1066 			return 0;
1067 	} else {
1068 		if (!btrfs_use_bitmap(ctl, info))
1069 			return 0;
1070 	}
1071 again:
1072 	/*
1073 	 * Since we link bitmaps right into the cluster we need to see if we
1074 	 * have a cluster here, and if so and it has our bitmap we need to add
1075 	 * the free space to that bitmap.
1076 	 */
1077 	if (!list_empty(&block_group->cluster_list)) {
1078 		struct btrfs_free_cluster *cluster;
1079 		struct rb_node *node;
1080 		struct btrfs_free_space *entry;
1081 
1082 		cluster = list_first_entry(&block_group->cluster_list,
1083 					   struct btrfs_free_cluster, block_group_list);
1084 		spin_lock(&cluster->lock);
1085 		node = rb_first(&cluster->root);
1086 		if (!node) {
1087 			spin_unlock(&cluster->lock);
1088 			goto no_cluster_bitmap;
1089 		}
1090 
1091 		entry = rb_entry(node, struct btrfs_free_space, offset_index);
1092 		if (!entry->bitmap) {
1093 			spin_unlock(&cluster->lock);
1094 			goto no_cluster_bitmap;
1095 		}
1096 
1097 		if (entry->offset == offset_to_bitmap(ctl, offset)) {
1098 			bytes_added = add_bytes_to_bitmap(ctl, entry, offset,
1099 							  bytes, trim_state);
1100 			bytes -= bytes_added;
1101 			offset += bytes_added;
1102 		}
1103 		spin_unlock(&cluster->lock);
1104 		if (!bytes) {
1105 			ret = 1;
1106 			goto out;
1107 		}
1108 	}
1109 
1110 no_cluster_bitmap:
1111 	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1112 					 1, 0);
1113 	if (!bitmap_info) {
1114 		ASSERT(!added);
1115 		goto new_bitmap;
1116 	}
1117 
1118 	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
1119 					  trim_state);
1120 	bytes -= bytes_added;
1121 	offset += bytes_added;
1122 	added = false;
1123 
1124 	if (!bytes) {
1125 		ret = 1;
1126 		goto out;
1127 	} else
1128 		goto again;
1129 
1130 new_bitmap:
1131 	if (info && info->bitmap) {
1132 		add_new_bitmap(ctl, info, offset);
1133 		added = true;
1134 		info = NULL;
1135 		goto again;
1136 	} else {
1137 		spin_unlock(&ctl->tree_lock);
1138 
1139 		/* no pre-allocated info, allocate a new one */
1140 		if (!info) {
1141 			info = kmem_cache_zalloc(btrfs_free_space_cachep,
1142 						 GFP_NOFS);
1143 			if (!info) {
1144 				spin_lock(&ctl->tree_lock);
1145 				ret = -ENOMEM;
1146 				goto out;
1147 			}
1148 		}
1149 
1150 		/* allocate the bitmap */
1151 		info->bitmap = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep,
1152 						 GFP_NOFS);
1153 		info->trim_state = BTRFS_TRIM_STATE_TRIMMED;
1154 		spin_lock(&ctl->tree_lock);
1155 		if (!info->bitmap) {
1156 			ret = -ENOMEM;
1157 			goto out;
1158 		}
1159 		goto again;
1160 	}
1161 
1162 out:
1163 	if (info) {
1164 		if (info->bitmap)
1165 			kmem_cache_free(btrfs_free_space_bitmap_cachep,
1166 					info->bitmap);
1167 		kmem_cache_free(btrfs_free_space_cachep, info);
1168 	}
1169 
1170 	return ret;
1171 }
1172 
1173 /*
1174  * Free space merging rules:
1175  *  1) Merge trimmed areas together
1176  *  2) Let untrimmed areas coalesce with trimmed areas
1177  *  3) Always pull neighboring regions from bitmaps
1178  *
1179  * The above rules are for when we merge free space based on btrfs_trim_state.
1180  * Rules 2 and 3 are subtle because they are suboptimal, but are done for the
1181  * same reason: to promote larger extent regions which makes life easier for
1182  * find_free_extent().  Rule 2 enables coalescing based on the common path
1183  * being returning free space from btrfs_finish_extent_commit().  So when free
1184  * space is trimmed, it will prevent aggregating trimmed new region and
1185  * untrimmed regions in the rb_tree.  Rule 3 is purely to obtain larger extents
1186  * and provide find_free_extent() with the largest extents possible hoping for
1187  * the reuse path.
1188  */
1189 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
1190 			  struct btrfs_free_space *info, bool update_stat)
1191 {
1192 	struct btrfs_free_space *left_info = NULL;
1193 	struct btrfs_free_space *right_info;
1194 	bool merged = false;
1195 	u64 offset = info->offset;
1196 	u64 bytes = info->bytes;
1197 	const bool is_trimmed = btrfs_free_space_trimmed(info);
1198 	struct rb_node *right_prev = NULL;
1199 
1200 	/*
1201 	 * first we want to see if there is free space adjacent to the range we
1202 	 * are adding, if there is remove that struct and add a new one to
1203 	 * cover the entire range
1204 	 */
1205 	right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
1206 	if (right_info)
1207 		right_prev = rb_prev(&right_info->offset_index);
1208 
1209 	if (right_prev)
1210 		left_info = rb_entry(right_prev, struct btrfs_free_space, offset_index);
1211 	else if (!right_info)
1212 		left_info = tree_search_offset(ctl, offset - 1, 0, 0);
1213 
1214 	/* See try_merge_free_space() comment. */
1215 	if (right_info && !right_info->bitmap &&
1216 	    (!is_trimmed || btrfs_free_space_trimmed(right_info))) {
1217 		unlink_free_space(ctl, right_info, update_stat);
1218 		info->bytes += right_info->bytes;
1219 		kmem_cache_free(btrfs_free_space_cachep, right_info);
1220 		merged = true;
1221 	}
1222 
1223 	/* See try_merge_free_space() comment. */
1224 	if (left_info && !left_info->bitmap &&
1225 	    left_info->offset + left_info->bytes == offset &&
1226 	    (!is_trimmed || btrfs_free_space_trimmed(left_info))) {
1227 		unlink_free_space(ctl, left_info, update_stat);
1228 		info->offset = left_info->offset;
1229 		info->bytes += left_info->bytes;
1230 		kmem_cache_free(btrfs_free_space_cachep, left_info);
1231 		merged = true;
1232 	}
1233 
1234 	return merged;
1235 }
1236 
1237 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
1238 				     struct btrfs_free_space *info,
1239 				     bool update_stat)
1240 {
1241 	const int unit = ctl->block_group->fs_info->sectorsize;
1242 	struct btrfs_free_space *bitmap;
1243 	unsigned long i;
1244 	unsigned long j;
1245 	const u64 end = info->offset + info->bytes;
1246 	const u64 bitmap_offset = offset_to_bitmap(ctl, end);
1247 	u64 bytes;
1248 
1249 	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
1250 	if (!bitmap)
1251 		return false;
1252 
1253 	i = offset_to_bit(bitmap->offset, unit, end);
1254 	j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
1255 	if (j == i)
1256 		return false;
1257 	bytes = (j - i) * unit;
1258 	info->bytes += bytes;
1259 
1260 	/* See try_merge_free_space() comment. */
1261 	if (!btrfs_free_space_trimmed(bitmap))
1262 		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
1263 
1264 	bitmap_clear_bits(ctl, bitmap, end, bytes, update_stat);
1265 
1266 	if (!bitmap->bytes)
1267 		free_bitmap(ctl, bitmap);
1268 
1269 	return true;
1270 }
1271 
1272 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
1273 				       struct btrfs_free_space *info,
1274 				       bool update_stat)
1275 {
1276 	const int unit = ctl->block_group->fs_info->sectorsize;
1277 	struct btrfs_free_space *bitmap;
1278 	u64 bitmap_offset;
1279 	unsigned long i;
1280 	unsigned long j;
1281 	unsigned long prev_j;
1282 	u64 bytes;
1283 
1284 	bitmap_offset = offset_to_bitmap(ctl, info->offset);
1285 	/* If we're on a boundary, try the previous logical bitmap. */
1286 	if (bitmap_offset == info->offset) {
1287 		if (info->offset == 0)
1288 			return false;
1289 		bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
1290 	}
1291 
1292 	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
1293 	if (!bitmap)
1294 		return false;
1295 
1296 	i = offset_to_bit(bitmap->offset, unit, info->offset) - 1;
1297 	j = 0;
1298 	prev_j = (unsigned long)-1;
1299 	for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
1300 		if (j > i)
1301 			break;
1302 		prev_j = j;
1303 	}
1304 	if (prev_j == i)
1305 		return false;
1306 
1307 	if (prev_j == (unsigned long)-1)
1308 		bytes = (i + 1) * unit;
1309 	else
1310 		bytes = (i - prev_j) * unit;
1311 
1312 	info->offset -= bytes;
1313 	info->bytes += bytes;
1314 
1315 	/* See try_merge_free_space() comment. */
1316 	if (!btrfs_free_space_trimmed(bitmap))
1317 		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
1318 
1319 	bitmap_clear_bits(ctl, bitmap, info->offset, bytes, update_stat);
1320 
1321 	if (!bitmap->bytes)
1322 		free_bitmap(ctl, bitmap);
1323 
1324 	return true;
1325 }
1326 
1327 /*
1328  * We prefer always to allocate from extent entries, both for clustered and
1329  * non-clustered allocation requests. So when attempting to add a new extent
1330  * entry, try to see if there's adjacent free space in bitmap entries, and if
1331  * there is, migrate that space from the bitmaps to the extent.
1332  * Like this we get better chances of satisfying space allocation requests
1333  * because we attempt to satisfy them based on a single cache entry, and never
1334  * on 2 or more entries - even if the entries represent a contiguous free space
1335  * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
1336  * ends).
1337  */
1338 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
1339 			      struct btrfs_free_space *info,
1340 			      bool update_stat)
1341 {
1342 	/*
1343 	 * Only work with disconnected entries, as we can change their offset,
1344 	 * and must be extent entries.
1345 	 */
1346 	ASSERT(!info->bitmap);
1347 	ASSERT(RB_EMPTY_NODE(&info->offset_index));
1348 
1349 	if (ctl->total_bitmaps > 0) {
1350 		bool stole_end;
1351 		bool stole_front = false;
1352 
1353 		stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
1354 		if (ctl->total_bitmaps > 0)
1355 			stole_front = steal_from_bitmap_to_front(ctl, info,
1356 								 update_stat);
1357 
1358 		if (stole_end || stole_front)
1359 			try_merge_free_space(ctl, info, update_stat);
1360 	}
1361 }
1362 
1363 static int __btrfs_add_free_space(struct btrfs_block_group *block_group,
1364 			   u64 offset, u64 bytes,
1365 			   enum btrfs_trim_state trim_state)
1366 {
1367 	struct btrfs_fs_info *fs_info = block_group->fs_info;
1368 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1369 	struct btrfs_free_space *info;
1370 	int ret = 0;
1371 	u64 filter_bytes = bytes;
1372 
1373 	ASSERT(!btrfs_is_zoned(fs_info));
1374 
1375 	info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
1376 	if (!info)
1377 		return -ENOMEM;
1378 
1379 	info->offset = offset;
1380 	info->bytes = bytes;
1381 	info->trim_state = trim_state;
1382 	RB_CLEAR_NODE(&info->offset_index);
1383 	RB_CLEAR_NODE(&info->bytes_index);
1384 
1385 	spin_lock(&ctl->tree_lock);
1386 
1387 	if (try_merge_free_space(ctl, info, true))
1388 		goto link;
1389 
1390 	/*
1391 	 * There was no extent directly to the left or right of this new
1392 	 * extent then we know we're going to have to allocate a new extent, so
1393 	 * before we do that see if we need to drop this into a bitmap
1394 	 */
1395 	ret = insert_into_bitmap(ctl, info);
1396 	if (ret < 0) {
1397 		goto out;
1398 	} else if (ret) {
1399 		ret = 0;
1400 		goto out;
1401 	}
1402 link:
1403 	/*
1404 	 * Only steal free space from adjacent bitmaps if we're sure we're not
1405 	 * going to add the new free space to existing bitmap entries - because
1406 	 * that would mean unnecessary work that would be reverted. Therefore
1407 	 * attempt to steal space from bitmaps if we're adding an extent entry.
1408 	 */
1409 	steal_from_bitmap(ctl, info, true);
1410 
1411 	filter_bytes = max(filter_bytes, info->bytes);
1412 
1413 	ret = link_free_space(ctl, info);
1414 	if (ret)
1415 		kmem_cache_free(btrfs_free_space_cachep, info);
1416 out:
1417 	btrfs_discard_update_discardable(block_group);
1418 	spin_unlock(&ctl->tree_lock);
1419 
1420 	if (ret) {
1421 		btrfs_crit(fs_info, "unable to add free space :%d", ret);
1422 		ASSERT(ret != -EEXIST);
1423 	}
1424 
1425 	if (trim_state != BTRFS_TRIM_STATE_TRIMMED) {
1426 		btrfs_discard_check_filter(block_group, filter_bytes);
1427 		btrfs_discard_queue_work(&fs_info->discard_ctl, block_group);
1428 	}
1429 
1430 	return ret;
1431 }
1432 
1433 static int __btrfs_add_free_space_zoned(struct btrfs_block_group *block_group,
1434 					u64 bytenr, u64 size, bool used)
1435 {
1436 	struct btrfs_space_info *sinfo = block_group->space_info;
1437 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1438 	u64 offset = bytenr - block_group->start;
1439 	u64 to_free, to_unusable;
1440 	int bg_reclaim_threshold = 0;
1441 	bool initial;
1442 	u64 reclaimable_unusable;
1443 
1444 	spin_lock(&block_group->lock);
1445 
1446 	initial = ((size == block_group->length) && (block_group->alloc_offset == 0));
1447 	WARN_ON(!initial && offset + size > block_group->zone_capacity);
1448 	if (!initial)
1449 		bg_reclaim_threshold = READ_ONCE(sinfo->bg_reclaim_threshold);
1450 
1451 	if (!used)
1452 		to_free = size;
1453 	else if (initial)
1454 		to_free = block_group->zone_capacity;
1455 	else if (offset >= block_group->alloc_offset)
1456 		to_free = size;
1457 	else if (offset + size <= block_group->alloc_offset)
1458 		to_free = 0;
1459 	else
1460 		to_free = offset + size - block_group->alloc_offset;
1461 	to_unusable = size - to_free;
1462 
1463 	spin_lock(&ctl->tree_lock);
1464 	ctl->free_space += to_free;
1465 	spin_unlock(&ctl->tree_lock);
1466 	/*
1467 	 * If the block group is read-only, we should account freed space into
1468 	 * bytes_readonly.
1469 	 */
1470 	if (!block_group->ro) {
1471 		block_group->zone_unusable += to_unusable;
1472 		WARN_ON(block_group->zone_unusable > block_group->length);
1473 	}
1474 	if (!used) {
1475 		block_group->alloc_offset -= size;
1476 	}
1477 
1478 	reclaimable_unusable = block_group->zone_unusable -
1479 			       (block_group->length - block_group->zone_capacity);
1480 	/* All the region is now unusable. Mark it as unused and reclaim */
1481 	if (block_group->zone_unusable == block_group->length) {
1482 		btrfs_mark_bg_unused(block_group);
1483 	} else if (bg_reclaim_threshold &&
1484 		   reclaimable_unusable >=
1485 		   mult_perc(block_group->zone_capacity, bg_reclaim_threshold)) {
1486 		btrfs_mark_bg_to_reclaim(block_group);
1487 	}
1488 
1489 	spin_unlock(&block_group->lock);
1490 
1491 	return 0;
1492 }
1493 
1494 int btrfs_add_free_space(struct btrfs_block_group *block_group,
1495 			 u64 bytenr, u64 size)
1496 {
1497 	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
1498 
1499 	if (block_group->flags & BTRFS_BLOCK_GROUP_REMAPPED)
1500 		return 0;
1501 
1502 	if (btrfs_is_zoned(block_group->fs_info))
1503 		return __btrfs_add_free_space_zoned(block_group, bytenr, size,
1504 						    true);
1505 
1506 	if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC))
1507 		trim_state = BTRFS_TRIM_STATE_TRIMMED;
1508 
1509 	return __btrfs_add_free_space(block_group, bytenr, size, trim_state);
1510 }
1511 
1512 int btrfs_add_free_space_unused(struct btrfs_block_group *block_group,
1513 				u64 bytenr, u64 size)
1514 {
1515 	if (btrfs_is_zoned(block_group->fs_info))
1516 		return __btrfs_add_free_space_zoned(block_group, bytenr, size,
1517 						    false);
1518 
1519 	return btrfs_add_free_space(block_group, bytenr, size);
1520 }
1521 
1522 /*
1523  * This is a subtle distinction because when adding free space back in general,
1524  * we want it to be added as untrimmed for async. But in the case where we add
1525  * it on loading of a block group, we want to consider it trimmed.
1526  */
1527 int btrfs_add_free_space_async_trimmed(struct btrfs_block_group *block_group,
1528 				       u64 bytenr, u64 size)
1529 {
1530 	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
1531 
1532 	if (btrfs_is_zoned(block_group->fs_info))
1533 		return __btrfs_add_free_space_zoned(block_group, bytenr, size,
1534 						    true);
1535 
1536 	if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC) ||
1537 	    btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC))
1538 		trim_state = BTRFS_TRIM_STATE_TRIMMED;
1539 
1540 	return __btrfs_add_free_space(block_group, bytenr, size, trim_state);
1541 }
1542 
1543 int btrfs_remove_free_space(struct btrfs_block_group *block_group,
1544 			    u64 offset, u64 bytes)
1545 {
1546 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1547 	struct btrfs_free_space *info;
1548 	int ret;
1549 	bool re_search = false;
1550 
1551 	if (btrfs_is_zoned(block_group->fs_info)) {
1552 		/*
1553 		 * This can happen with conventional zones when replaying log.
1554 		 * Since the allocation info of tree-log nodes are not recorded
1555 		 * to the extent-tree, calculate_alloc_pointer() failed to
1556 		 * advance the allocation pointer after last allocated tree log
1557 		 * node blocks.
1558 		 *
1559 		 * This function is called from
1560 		 * btrfs_pin_extent_for_log_replay() when replaying the log.
1561 		 * Advance the pointer not to overwrite the tree-log nodes.
1562 		 */
1563 		if (block_group->start + block_group->alloc_offset <
1564 		    offset + bytes) {
1565 			block_group->alloc_offset =
1566 				offset + bytes - block_group->start;
1567 		}
1568 		return 0;
1569 	}
1570 
1571 	spin_lock(&ctl->tree_lock);
1572 
1573 again:
1574 	ret = 0;
1575 	if (!bytes)
1576 		goto out_lock;
1577 
1578 	info = tree_search_offset(ctl, offset, 0, 0);
1579 	if (!info) {
1580 		/*
1581 		 * oops didn't find an extent that matched the space we wanted
1582 		 * to remove, look for a bitmap instead
1583 		 */
1584 		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1585 					  1, 0);
1586 		if (!info) {
1587 			/*
1588 			 * If we found a partial bit of our free space in a
1589 			 * bitmap but then couldn't find the other part this may
1590 			 * be a problem, so WARN about it.
1591 			 */
1592 			WARN_ON(re_search);
1593 			goto out_lock;
1594 		}
1595 	}
1596 
1597 	re_search = false;
1598 	if (!info->bitmap) {
1599 		unlink_free_space(ctl, info, true);
1600 		if (offset == info->offset) {
1601 			u64 to_free = min(bytes, info->bytes);
1602 
1603 			info->bytes -= to_free;
1604 			info->offset += to_free;
1605 			if (info->bytes) {
1606 				ret = link_free_space(ctl, info);
1607 				WARN_ON(ret);
1608 			} else {
1609 				kmem_cache_free(btrfs_free_space_cachep, info);
1610 			}
1611 
1612 			offset += to_free;
1613 			bytes -= to_free;
1614 			goto again;
1615 		} else {
1616 			u64 old_end = info->bytes + info->offset;
1617 
1618 			info->bytes = offset - info->offset;
1619 			ret = link_free_space(ctl, info);
1620 			WARN_ON(ret);
1621 			if (ret)
1622 				goto out_lock;
1623 
1624 			/* Not enough bytes in this entry to satisfy us */
1625 			if (old_end < offset + bytes) {
1626 				bytes -= old_end - offset;
1627 				offset = old_end;
1628 				goto again;
1629 			} else if (old_end == offset + bytes) {
1630 				/* all done */
1631 				goto out_lock;
1632 			}
1633 			spin_unlock(&ctl->tree_lock);
1634 
1635 			ret = __btrfs_add_free_space(block_group,
1636 						     offset + bytes,
1637 						     old_end - (offset + bytes),
1638 						     info->trim_state);
1639 			WARN_ON(ret);
1640 			return ret;
1641 		}
1642 	}
1643 
1644 	ret = remove_from_bitmap(ctl, info, &offset, &bytes);
1645 	if (ret == -EAGAIN) {
1646 		re_search = true;
1647 		goto again;
1648 	}
1649 out_lock:
1650 	btrfs_discard_update_discardable(block_group);
1651 	spin_unlock(&ctl->tree_lock);
1652 
1653 	return ret;
1654 }
1655 
1656 void btrfs_dump_free_space(struct btrfs_block_group *block_group,
1657 			   u64 bytes)
1658 {
1659 	struct btrfs_fs_info *fs_info = block_group->fs_info;
1660 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1661 	struct btrfs_free_space *info;
1662 	struct rb_node *n;
1663 	int count = 0;
1664 
1665 	/*
1666 	 * Zoned btrfs does not use free space tree and cluster. Just print
1667 	 * out the free space after the allocation offset.
1668 	 */
1669 	if (btrfs_is_zoned(fs_info)) {
1670 		btrfs_info(fs_info, "free space %llu active %d",
1671 			   block_group->zone_capacity - block_group->alloc_offset,
1672 			   test_bit(BLOCK_GROUP_FLAG_ZONE_IS_ACTIVE,
1673 				    &block_group->runtime_flags));
1674 		return;
1675 	}
1676 
1677 	spin_lock(&ctl->tree_lock);
1678 	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
1679 		info = rb_entry(n, struct btrfs_free_space, offset_index);
1680 		if (info->bytes >= bytes && !block_group->ro)
1681 			count++;
1682 		btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s",
1683 			   info->offset, info->bytes, str_yes_no(info->bitmap));
1684 	}
1685 	spin_unlock(&ctl->tree_lock);
1686 	btrfs_info(fs_info, "block group has cluster?: %s",
1687 	       str_no_yes(list_empty(&block_group->cluster_list)));
1688 	btrfs_info(fs_info,
1689 		   "%d free space entries at or bigger than %llu bytes",
1690 		   count, bytes);
1691 }
1692 
1693 void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group,
1694 			       struct btrfs_free_space_ctl *ctl)
1695 {
1696 	spin_lock_init(&ctl->tree_lock);
1697 	ctl->block_group = block_group;
1698 	ctl->free_space_bytes = RB_ROOT_CACHED;
1699 
1700 	/*
1701 	 * we only want to have 32k of ram per block group for keeping
1702 	 * track of free space, and if we pass 1/2 of that we want to
1703 	 * start converting things over to using bitmaps
1704 	 */
1705 	ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);
1706 }
1707 
1708 /*
1709  * for a given cluster, put all of its extents back into the free
1710  * space cache.  If the block group passed doesn't match the block group
1711  * pointed to by the cluster, someone else raced in and freed the
1712  * cluster already.  In that case, we just return without changing anything
1713  */
1714 static void __btrfs_return_cluster_to_free_space(
1715 			     struct btrfs_block_group *block_group,
1716 			     struct btrfs_free_cluster *cluster)
1717 {
1718 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1719 	struct rb_node *node;
1720 
1721 	lockdep_assert_held(&ctl->tree_lock);
1722 
1723 	spin_lock(&cluster->lock);
1724 	if (cluster->block_group != block_group) {
1725 		spin_unlock(&cluster->lock);
1726 		return;
1727 	}
1728 
1729 	cluster->block_group = NULL;
1730 	cluster->window_start = 0;
1731 	list_del_init(&cluster->block_group_list);
1732 
1733 	node = rb_first(&cluster->root);
1734 	while (node) {
1735 		struct btrfs_free_space *entry;
1736 
1737 		entry = rb_entry(node, struct btrfs_free_space, offset_index);
1738 		node = rb_next(&entry->offset_index);
1739 		rb_erase(&entry->offset_index, &cluster->root);
1740 		RB_CLEAR_NODE(&entry->offset_index);
1741 
1742 		if (!entry->bitmap) {
1743 			/* Merging treats extents as if they were new */
1744 			if (!btrfs_free_space_trimmed(entry)) {
1745 				ctl->discardable_extents[BTRFS_STAT_CURR]--;
1746 				ctl->discardable_bytes[BTRFS_STAT_CURR] -=
1747 					entry->bytes;
1748 			}
1749 
1750 			try_merge_free_space(ctl, entry, false);
1751 			steal_from_bitmap(ctl, entry, false);
1752 
1753 			/* As we insert directly, update these statistics */
1754 			if (!btrfs_free_space_trimmed(entry)) {
1755 				ctl->discardable_extents[BTRFS_STAT_CURR]++;
1756 				ctl->discardable_bytes[BTRFS_STAT_CURR] +=
1757 					entry->bytes;
1758 			}
1759 		}
1760 		tree_insert_offset(ctl, NULL, entry);
1761 		rb_add_cached(&entry->bytes_index, &ctl->free_space_bytes,
1762 			      entry_less);
1763 	}
1764 	cluster->root = RB_ROOT;
1765 	spin_unlock(&cluster->lock);
1766 	btrfs_put_block_group(block_group);
1767 }
1768 
1769 void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group)
1770 {
1771 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1772 	struct btrfs_free_cluster *cluster;
1773 	struct list_head *head;
1774 
1775 	spin_lock(&ctl->tree_lock);
1776 	while ((head = block_group->cluster_list.next) !=
1777 	       &block_group->cluster_list) {
1778 		cluster = list_entry(head, struct btrfs_free_cluster,
1779 				     block_group_list);
1780 
1781 		WARN_ON(cluster->block_group != block_group);
1782 		__btrfs_return_cluster_to_free_space(block_group, cluster);
1783 
1784 		cond_resched_lock(&ctl->tree_lock);
1785 	}
1786 	__btrfs_remove_free_space_cache(ctl);
1787 	btrfs_discard_update_discardable(block_group);
1788 	spin_unlock(&ctl->tree_lock);
1789 
1790 }
1791 
1792 /*
1793  * Walk @block_group's free space rb_tree to determine if everything is trimmed.
1794  */
1795 bool btrfs_is_free_space_trimmed(struct btrfs_block_group *block_group)
1796 {
1797 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1798 	struct btrfs_free_space *info;
1799 	struct rb_node *node;
1800 	bool ret = true;
1801 
1802 	if (block_group->flags & BTRFS_BLOCK_GROUP_REMAPPED &&
1803 	    !test_bit(BLOCK_GROUP_FLAG_STRIPE_REMOVAL_PENDING, &block_group->runtime_flags) &&
1804 	    block_group->identity_remap_count == 0) {
1805 		return true;
1806 	}
1807 
1808 	spin_lock(&ctl->tree_lock);
1809 	node = rb_first(&ctl->free_space_offset);
1810 
1811 	while (node) {
1812 		info = rb_entry(node, struct btrfs_free_space, offset_index);
1813 
1814 		if (!btrfs_free_space_trimmed(info)) {
1815 			ret = false;
1816 			break;
1817 		}
1818 
1819 		node = rb_next(node);
1820 	}
1821 
1822 	spin_unlock(&ctl->tree_lock);
1823 	return ret;
1824 }
1825 
1826 u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group,
1827 			       u64 offset, u64 bytes, u64 empty_size,
1828 			       u64 *max_extent_size)
1829 {
1830 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1831 	struct btrfs_discard_ctl *discard_ctl =
1832 					&block_group->fs_info->discard_ctl;
1833 	struct btrfs_free_space *entry = NULL;
1834 	u64 bytes_search = bytes + empty_size;
1835 	u64 ret = 0;
1836 	u64 align_gap = 0;
1837 	u64 align_gap_len = 0;
1838 	enum btrfs_trim_state align_gap_trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
1839 	bool use_bytes_index = (offset == block_group->start);
1840 
1841 	ASSERT(!btrfs_is_zoned(block_group->fs_info));
1842 
1843 	spin_lock(&ctl->tree_lock);
1844 	entry = find_free_space(ctl, &offset, &bytes_search,
1845 				block_group->full_stripe_len, max_extent_size,
1846 				use_bytes_index);
1847 	if (!entry)
1848 		goto out;
1849 
1850 	ret = offset;
1851 	if (entry->bitmap) {
1852 		bitmap_clear_bits(ctl, entry, offset, bytes, true);
1853 
1854 		if (!btrfs_free_space_trimmed(entry))
1855 			atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
1856 
1857 		if (!entry->bytes)
1858 			free_bitmap(ctl, entry);
1859 	} else {
1860 		unlink_free_space(ctl, entry, true);
1861 		align_gap_len = offset - entry->offset;
1862 		align_gap = entry->offset;
1863 		align_gap_trim_state = entry->trim_state;
1864 
1865 		if (!btrfs_free_space_trimmed(entry))
1866 			atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
1867 
1868 		entry->offset = offset + bytes;
1869 		WARN_ON(entry->bytes < bytes + align_gap_len);
1870 
1871 		entry->bytes -= bytes + align_gap_len;
1872 		if (!entry->bytes)
1873 			kmem_cache_free(btrfs_free_space_cachep, entry);
1874 		else
1875 			link_free_space(ctl, entry);
1876 	}
1877 out:
1878 	btrfs_discard_update_discardable(block_group);
1879 	spin_unlock(&ctl->tree_lock);
1880 
1881 	if (align_gap_len)
1882 		__btrfs_add_free_space(block_group, align_gap, align_gap_len,
1883 				       align_gap_trim_state);
1884 	return ret;
1885 }
1886 
1887 /*
1888  * given a cluster, put all of its extents back into the free space
1889  * cache.  If a block group is passed, this function will only free
1890  * a cluster that belongs to the passed block group.
1891  *
1892  * Otherwise, it'll get a reference on the block group pointed to by the
1893  * cluster and remove the cluster from it.
1894  */
1895 void btrfs_return_cluster_to_free_space(
1896 			       struct btrfs_block_group *block_group,
1897 			       struct btrfs_free_cluster *cluster)
1898 {
1899 	struct btrfs_free_space_ctl *ctl;
1900 
1901 	/* first, get a safe pointer to the block group */
1902 	spin_lock(&cluster->lock);
1903 	if (!block_group) {
1904 		block_group = cluster->block_group;
1905 		if (!block_group) {
1906 			spin_unlock(&cluster->lock);
1907 			return;
1908 		}
1909 	} else if (cluster->block_group != block_group) {
1910 		/* someone else has already freed it don't redo their work */
1911 		spin_unlock(&cluster->lock);
1912 		return;
1913 	}
1914 	btrfs_get_block_group(block_group);
1915 	spin_unlock(&cluster->lock);
1916 
1917 	ctl = block_group->free_space_ctl;
1918 
1919 	/* now return any extents the cluster had on it */
1920 	spin_lock(&ctl->tree_lock);
1921 	__btrfs_return_cluster_to_free_space(block_group, cluster);
1922 	spin_unlock(&ctl->tree_lock);
1923 
1924 	btrfs_discard_queue_work(&block_group->fs_info->discard_ctl, block_group);
1925 
1926 	/* finally drop our ref */
1927 	btrfs_put_block_group(block_group);
1928 }
1929 
1930 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group,
1931 				   struct btrfs_free_cluster *cluster,
1932 				   struct btrfs_free_space *entry,
1933 				   u64 bytes, u64 min_start,
1934 				   u64 *max_extent_size)
1935 {
1936 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1937 	int ret2;
1938 	u64 search_start = cluster->window_start;
1939 	u64 search_bytes = bytes;
1940 	u64 ret = 0;
1941 
1942 	search_start = min_start;
1943 	search_bytes = bytes;
1944 
1945 	ret2 = search_bitmap(ctl, entry, &search_start, &search_bytes, true);
1946 	if (ret2) {
1947 		*max_extent_size = max(get_max_extent_size(entry),
1948 				       *max_extent_size);
1949 		return 0;
1950 	}
1951 
1952 	ret = search_start;
1953 	bitmap_clear_bits(ctl, entry, ret, bytes, false);
1954 
1955 	return ret;
1956 }
1957 
1958 /*
1959  * given a cluster, try to allocate 'bytes' from it, returns 0
1960  * if it couldn't find anything suitably large, or a logical disk offset
1961  * if things worked out
1962  */
1963 u64 btrfs_alloc_from_cluster(struct btrfs_block_group *block_group,
1964 			     struct btrfs_free_cluster *cluster, u64 bytes,
1965 			     u64 min_start, u64 *max_extent_size)
1966 {
1967 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1968 	struct btrfs_discard_ctl *discard_ctl =
1969 					&block_group->fs_info->discard_ctl;
1970 	struct btrfs_free_space *entry = NULL;
1971 	struct rb_node *node;
1972 	u64 ret = 0;
1973 
1974 	ASSERT(!btrfs_is_zoned(block_group->fs_info));
1975 
1976 	spin_lock(&cluster->lock);
1977 	if (bytes > cluster->max_size)
1978 		goto out;
1979 
1980 	if (cluster->block_group != block_group)
1981 		goto out;
1982 
1983 	node = rb_first(&cluster->root);
1984 	if (!node)
1985 		goto out;
1986 
1987 	entry = rb_entry(node, struct btrfs_free_space, offset_index);
1988 	while (1) {
1989 		if (entry->bytes < bytes)
1990 			*max_extent_size = max(get_max_extent_size(entry),
1991 					       *max_extent_size);
1992 
1993 		if (entry->bytes < bytes ||
1994 		    (!entry->bitmap && entry->offset < min_start)) {
1995 			node = rb_next(&entry->offset_index);
1996 			if (!node)
1997 				break;
1998 			entry = rb_entry(node, struct btrfs_free_space,
1999 					 offset_index);
2000 			continue;
2001 		}
2002 
2003 		if (entry->bitmap) {
2004 			ret = btrfs_alloc_from_bitmap(block_group,
2005 						      cluster, entry, bytes,
2006 						      cluster->window_start,
2007 						      max_extent_size);
2008 			if (ret == 0) {
2009 				node = rb_next(&entry->offset_index);
2010 				if (!node)
2011 					break;
2012 				entry = rb_entry(node, struct btrfs_free_space,
2013 						 offset_index);
2014 				continue;
2015 			}
2016 			cluster->window_start += bytes;
2017 		} else {
2018 			ret = entry->offset;
2019 
2020 			entry->offset += bytes;
2021 			entry->bytes -= bytes;
2022 		}
2023 
2024 		break;
2025 	}
2026 out:
2027 	spin_unlock(&cluster->lock);
2028 
2029 	if (!ret)
2030 		return 0;
2031 
2032 	spin_lock(&ctl->tree_lock);
2033 
2034 	if (!btrfs_free_space_trimmed(entry))
2035 		atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
2036 
2037 	ctl->free_space -= bytes;
2038 	if (!entry->bitmap && !btrfs_free_space_trimmed(entry))
2039 		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
2040 
2041 	spin_lock(&cluster->lock);
2042 	if (entry->bytes == 0) {
2043 		rb_erase(&entry->offset_index, &cluster->root);
2044 		ctl->free_extents--;
2045 		if (entry->bitmap) {
2046 			kmem_cache_free(btrfs_free_space_bitmap_cachep,
2047 					entry->bitmap);
2048 			ctl->total_bitmaps--;
2049 			recalculate_thresholds(ctl);
2050 		} else if (!btrfs_free_space_trimmed(entry)) {
2051 			ctl->discardable_extents[BTRFS_STAT_CURR]--;
2052 		}
2053 		kmem_cache_free(btrfs_free_space_cachep, entry);
2054 	}
2055 
2056 	spin_unlock(&cluster->lock);
2057 	spin_unlock(&ctl->tree_lock);
2058 
2059 	return ret;
2060 }
2061 
2062 static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,
2063 				struct btrfs_free_space *entry,
2064 				struct btrfs_free_cluster *cluster,
2065 				u64 offset, u64 bytes,
2066 				u64 cont1_bytes, u64 min_bytes)
2067 {
2068 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2069 	const int unit = block_group->fs_info->sectorsize;
2070 	unsigned long next_zero;
2071 	unsigned long i;
2072 	unsigned long want_bits;
2073 	unsigned long min_bits;
2074 	unsigned long found_bits;
2075 	unsigned long max_bits = 0;
2076 	unsigned long start = 0;
2077 	unsigned long total_found = 0;
2078 	int ret;
2079 
2080 	lockdep_assert_held(&ctl->tree_lock);
2081 
2082 	i = offset_to_bit(entry->offset, unit,
2083 			  max_t(u64, offset, entry->offset));
2084 	want_bits = bytes_to_bits(bytes, unit);
2085 	min_bits = bytes_to_bits(min_bytes, unit);
2086 
2087 	/*
2088 	 * Don't bother looking for a cluster in this bitmap if it's heavily
2089 	 * fragmented.
2090 	 */
2091 	if (entry->max_extent_size &&
2092 	    entry->max_extent_size < cont1_bytes)
2093 		return -ENOSPC;
2094 again:
2095 	found_bits = 0;
2096 	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2097 		next_zero = find_next_zero_bit(entry->bitmap,
2098 					       BITS_PER_BITMAP, i);
2099 		if (next_zero - i >= min_bits) {
2100 			found_bits = next_zero - i;
2101 			if (found_bits > max_bits)
2102 				max_bits = found_bits;
2103 			break;
2104 		}
2105 		if (next_zero - i > max_bits)
2106 			max_bits = next_zero - i;
2107 		i = next_zero;
2108 	}
2109 
2110 	if (!found_bits) {
2111 		entry->max_extent_size = (u64)max_bits * unit;
2112 		return -ENOSPC;
2113 	}
2114 
2115 	if (!total_found) {
2116 		start = i;
2117 		cluster->max_size = 0;
2118 	}
2119 
2120 	total_found += found_bits;
2121 
2122 	if (cluster->max_size < found_bits * unit)
2123 		cluster->max_size = found_bits * unit;
2124 
2125 	if (total_found < want_bits || cluster->max_size < cont1_bytes) {
2126 		i = next_zero + 1;
2127 		goto again;
2128 	}
2129 
2130 	cluster->window_start = start * unit + entry->offset;
2131 	rb_erase(&entry->offset_index, &ctl->free_space_offset);
2132 	rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);
2133 
2134 	/*
2135 	 * We need to know if we're currently on the normal space index when we
2136 	 * manipulate the bitmap so that we know we need to remove and re-insert
2137 	 * it into the space_index tree.  Clear the bytes_index node here so the
2138 	 * bitmap manipulation helpers know not to mess with the space_index
2139 	 * until this bitmap entry is added back into the normal cache.
2140 	 */
2141 	RB_CLEAR_NODE(&entry->bytes_index);
2142 
2143 	ret = tree_insert_offset(ctl, cluster, entry);
2144 	ASSERT(!ret); /* -EEXIST; Logic error */
2145 
2146 	trace_btrfs_setup_cluster(block_group, cluster, total_found * unit, 1);
2147 	return 0;
2148 }
2149 
2150 /*
2151  * This searches the block group for just extents to fill the cluster with.
2152  * Try to find a cluster with at least bytes total bytes, at least one
2153  * extent of cont1_bytes, and other clusters of at least min_bytes.
2154  */
2155 static noinline int
2156 setup_cluster_no_bitmap(struct btrfs_block_group *block_group,
2157 			struct btrfs_free_cluster *cluster,
2158 			struct list_head *bitmaps, u64 offset, u64 bytes,
2159 			u64 cont1_bytes, u64 min_bytes)
2160 {
2161 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2162 	struct btrfs_free_space *first = NULL;
2163 	struct btrfs_free_space *entry = NULL;
2164 	struct btrfs_free_space *last;
2165 	struct rb_node *node;
2166 	u64 window_free;
2167 	u64 max_extent;
2168 	u64 total_size = 0;
2169 
2170 	lockdep_assert_held(&ctl->tree_lock);
2171 
2172 	entry = tree_search_offset(ctl, offset, 0, 1);
2173 	if (!entry)
2174 		return -ENOSPC;
2175 
2176 	/*
2177 	 * We don't want bitmaps, so just move along until we find a normal
2178 	 * extent entry.
2179 	 */
2180 	while (entry->bitmap || entry->bytes < min_bytes) {
2181 		if (entry->bitmap && list_empty(&entry->list))
2182 			list_add_tail(&entry->list, bitmaps);
2183 		node = rb_next(&entry->offset_index);
2184 		if (!node)
2185 			return -ENOSPC;
2186 		entry = rb_entry(node, struct btrfs_free_space, offset_index);
2187 	}
2188 
2189 	window_free = entry->bytes;
2190 	max_extent = entry->bytes;
2191 	first = entry;
2192 	last = entry;
2193 
2194 	for (node = rb_next(&entry->offset_index); node;
2195 	     node = rb_next(&entry->offset_index)) {
2196 		entry = rb_entry(node, struct btrfs_free_space, offset_index);
2197 
2198 		if (entry->bitmap) {
2199 			if (list_empty(&entry->list))
2200 				list_add_tail(&entry->list, bitmaps);
2201 			continue;
2202 		}
2203 
2204 		if (entry->bytes < min_bytes)
2205 			continue;
2206 
2207 		last = entry;
2208 		window_free += entry->bytes;
2209 		if (entry->bytes > max_extent)
2210 			max_extent = entry->bytes;
2211 	}
2212 
2213 	if (window_free < bytes || max_extent < cont1_bytes)
2214 		return -ENOSPC;
2215 
2216 	cluster->window_start = first->offset;
2217 
2218 	node = &first->offset_index;
2219 
2220 	/*
2221 	 * now we've found our entries, pull them out of the free space
2222 	 * cache and put them into the cluster rbtree
2223 	 */
2224 	do {
2225 		int ret;
2226 
2227 		entry = rb_entry(node, struct btrfs_free_space, offset_index);
2228 		node = rb_next(&entry->offset_index);
2229 		if (entry->bitmap || entry->bytes < min_bytes)
2230 			continue;
2231 
2232 		rb_erase(&entry->offset_index, &ctl->free_space_offset);
2233 		rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);
2234 		ret = tree_insert_offset(ctl, cluster, entry);
2235 		total_size += entry->bytes;
2236 		ASSERT(!ret); /* -EEXIST; Logic error */
2237 	} while (node && entry != last);
2238 
2239 	cluster->max_size = max_extent;
2240 	trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
2241 	return 0;
2242 }
2243 
2244 /*
2245  * This specifically looks for bitmaps that may work in the cluster, we assume
2246  * that we have already failed to find extents that will work.
2247  */
2248 static noinline int
2249 setup_cluster_bitmap(struct btrfs_block_group *block_group,
2250 		     struct btrfs_free_cluster *cluster,
2251 		     struct list_head *bitmaps, u64 offset, u64 bytes,
2252 		     u64 cont1_bytes, u64 min_bytes)
2253 {
2254 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2255 	struct btrfs_free_space *entry = NULL;
2256 	int ret = -ENOSPC;
2257 	u64 bitmap_offset = offset_to_bitmap(ctl, offset);
2258 
2259 	if (ctl->total_bitmaps == 0)
2260 		return -ENOSPC;
2261 
2262 	/*
2263 	 * The bitmap that covers offset won't be in the list unless offset
2264 	 * is just its start offset.
2265 	 */
2266 	if (!list_empty(bitmaps))
2267 		entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
2268 
2269 	if (!entry || entry->offset != bitmap_offset) {
2270 		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
2271 		if (entry && list_empty(&entry->list))
2272 			list_add(&entry->list, bitmaps);
2273 	}
2274 
2275 	list_for_each_entry(entry, bitmaps, list) {
2276 		if (entry->bytes < bytes)
2277 			continue;
2278 		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2279 					   bytes, cont1_bytes, min_bytes);
2280 		if (!ret)
2281 			return 0;
2282 	}
2283 
2284 	/*
2285 	 * The bitmaps list has all the bitmaps that record free space
2286 	 * starting after offset, so no more search is required.
2287 	 */
2288 	return -ENOSPC;
2289 }
2290 
2291 /*
2292  * here we try to find a cluster of blocks in a block group.  The goal
2293  * is to find at least bytes+empty_size.
2294  * We might not find them all in one contiguous area.
2295  *
2296  * returns zero and sets up cluster if things worked out, otherwise
2297  * it returns -enospc
2298  */
2299 int btrfs_find_space_cluster(struct btrfs_block_group *block_group,
2300 			     struct btrfs_free_cluster *cluster,
2301 			     u64 offset, u64 bytes, u64 empty_size)
2302 {
2303 	struct btrfs_fs_info *fs_info = block_group->fs_info;
2304 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2305 	struct btrfs_free_space *entry, *tmp;
2306 	LIST_HEAD(bitmaps);
2307 	u64 min_bytes;
2308 	u64 cont1_bytes;
2309 	int ret;
2310 
2311 	/*
2312 	 * Choose the minimum extent size we'll require for this
2313 	 * cluster.  For SSD_SPREAD, don't allow any fragmentation.
2314 	 * For metadata, allow allocates with smaller extents.  For
2315 	 * data, keep it dense.
2316 	 */
2317 	if (btrfs_test_opt(fs_info, SSD_SPREAD)) {
2318 		cont1_bytes = bytes + empty_size;
2319 		min_bytes = cont1_bytes;
2320 	} else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
2321 		cont1_bytes = bytes;
2322 		min_bytes = fs_info->sectorsize;
2323 	} else {
2324 		cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
2325 		min_bytes = fs_info->sectorsize;
2326 	}
2327 
2328 	spin_lock(&ctl->tree_lock);
2329 
2330 	/*
2331 	 * If we know we don't have enough space to make a cluster don't even
2332 	 * bother doing all the work to try and find one.
2333 	 */
2334 	if (ctl->free_space < bytes) {
2335 		spin_unlock(&ctl->tree_lock);
2336 		return -ENOSPC;
2337 	}
2338 
2339 	spin_lock(&cluster->lock);
2340 
2341 	/* someone already found a cluster, hooray */
2342 	if (cluster->block_group) {
2343 		ret = 0;
2344 		goto out;
2345 	}
2346 
2347 	trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
2348 				 min_bytes);
2349 
2350 	ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
2351 				      bytes + empty_size,
2352 				      cont1_bytes, min_bytes);
2353 	if (ret)
2354 		ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
2355 					   offset, bytes + empty_size,
2356 					   cont1_bytes, min_bytes);
2357 
2358 	/* Clear our temporary list */
2359 	list_for_each_entry_safe(entry, tmp, &bitmaps, list)
2360 		list_del_init(&entry->list);
2361 
2362 	if (!ret) {
2363 		btrfs_get_block_group(block_group);
2364 		list_add_tail(&cluster->block_group_list,
2365 			      &block_group->cluster_list);
2366 		cluster->block_group = block_group;
2367 	} else {
2368 		trace_btrfs_failed_cluster_setup(block_group);
2369 	}
2370 out:
2371 	spin_unlock(&cluster->lock);
2372 	spin_unlock(&ctl->tree_lock);
2373 
2374 	return ret;
2375 }
2376 
2377 /*
2378  * simple code to zero out a cluster
2379  */
2380 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
2381 {
2382 	spin_lock_init(&cluster->lock);
2383 	spin_lock_init(&cluster->refill_lock);
2384 	cluster->root = RB_ROOT;
2385 	cluster->max_size = 0;
2386 	cluster->fragmented = false;
2387 	INIT_LIST_HEAD(&cluster->block_group_list);
2388 	cluster->block_group = NULL;
2389 }
2390 
2391 static int do_trimming(struct btrfs_block_group *block_group,
2392 		       u64 *total_trimmed, u64 start, u64 bytes,
2393 		       u64 reserved_start, u64 reserved_bytes,
2394 		       enum btrfs_trim_state reserved_trim_state)
2395 {
2396 	struct btrfs_space_info *space_info = block_group->space_info;
2397 	struct btrfs_fs_info *fs_info = block_group->fs_info;
2398 	int ret;
2399 	bool bg_ro;
2400 	const u64 end = start + bytes;
2401 	const u64 reserved_end = reserved_start + reserved_bytes;
2402 	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
2403 	u64 trimmed = 0;
2404 
2405 	spin_lock(&space_info->lock);
2406 	spin_lock(&block_group->lock);
2407 	bg_ro = block_group->ro;
2408 	if (!bg_ro) {
2409 		block_group->reserved += reserved_bytes;
2410 		spin_unlock(&block_group->lock);
2411 		space_info->bytes_reserved += reserved_bytes;
2412 	} else {
2413 		spin_unlock(&block_group->lock);
2414 	}
2415 	spin_unlock(&space_info->lock);
2416 
2417 	ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed, false);
2418 	if (!ret) {
2419 		*total_trimmed += trimmed;
2420 		trim_state = BTRFS_TRIM_STATE_TRIMMED;
2421 	}
2422 
2423 	if (reserved_start < start)
2424 		__btrfs_add_free_space(block_group, reserved_start,
2425 				       start - reserved_start,
2426 				       reserved_trim_state);
2427 	if (end < reserved_end)
2428 		__btrfs_add_free_space(block_group, end, reserved_end - end,
2429 				       reserved_trim_state);
2430 	__btrfs_add_free_space(block_group, start, bytes, trim_state);
2431 
2432 	if (!bg_ro) {
2433 		spin_lock(&space_info->lock);
2434 		spin_lock(&block_group->lock);
2435 		bg_ro = block_group->ro;
2436 		block_group->reserved -= reserved_bytes;
2437 		spin_unlock(&block_group->lock);
2438 
2439 		space_info->bytes_reserved -= reserved_bytes;
2440 		if (bg_ro)
2441 			space_info->bytes_readonly += reserved_bytes;
2442 		spin_unlock(&space_info->lock);
2443 	}
2444 
2445 	return ret;
2446 }
2447 
2448 /*
2449  * If @async is set, then we will trim 1 region and return.
2450  */
2451 static int trim_no_bitmap(struct btrfs_block_group *block_group,
2452 			  u64 *total_trimmed, u64 start, u64 end, u64 minlen,
2453 			  bool async)
2454 {
2455 	struct btrfs_discard_ctl *discard_ctl =
2456 					&block_group->fs_info->discard_ctl;
2457 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2458 	struct btrfs_free_space *entry;
2459 	struct rb_node *node;
2460 	int ret = 0;
2461 	u64 extent_start;
2462 	u64 extent_bytes;
2463 	enum btrfs_trim_state extent_trim_state;
2464 	u64 bytes;
2465 	const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);
2466 
2467 	while (start < end) {
2468 		spin_lock(&ctl->tree_lock);
2469 
2470 		if (ctl->free_space < minlen)
2471 			goto out_unlock;
2472 
2473 		entry = tree_search_offset(ctl, start, 0, 1);
2474 		if (!entry)
2475 			goto out_unlock;
2476 
2477 		/* Skip bitmaps and if async, already trimmed entries */
2478 		while (entry->bitmap ||
2479 		       (async && btrfs_free_space_trimmed(entry))) {
2480 			node = rb_next(&entry->offset_index);
2481 			if (!node)
2482 				goto out_unlock;
2483 			entry = rb_entry(node, struct btrfs_free_space,
2484 					 offset_index);
2485 		}
2486 
2487 		if (entry->offset >= end)
2488 			goto out_unlock;
2489 
2490 		extent_start = entry->offset;
2491 		extent_bytes = entry->bytes;
2492 		extent_trim_state = entry->trim_state;
2493 		if (async) {
2494 			start = entry->offset;
2495 			bytes = entry->bytes;
2496 			if (bytes < minlen) {
2497 				spin_unlock(&ctl->tree_lock);
2498 				goto next;
2499 			}
2500 			unlink_free_space(ctl, entry, true);
2501 			/*
2502 			 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.
2503 			 * If X < BTRFS_ASYNC_DISCARD_MIN_FILTER, we won't trim
2504 			 * X when we come back around.  So trim it now.
2505 			 */
2506 			if (max_discard_size &&
2507 			    bytes >= (max_discard_size +
2508 				      BTRFS_ASYNC_DISCARD_MIN_FILTER)) {
2509 				bytes = max_discard_size;
2510 				extent_bytes = max_discard_size;
2511 				entry->offset += max_discard_size;
2512 				entry->bytes -= max_discard_size;
2513 				link_free_space(ctl, entry);
2514 			} else {
2515 				kmem_cache_free(btrfs_free_space_cachep, entry);
2516 			}
2517 		} else {
2518 			start = max(start, extent_start);
2519 			bytes = min(extent_start + extent_bytes, end) - start;
2520 			if (bytes < minlen) {
2521 				spin_unlock(&ctl->tree_lock);
2522 				goto next;
2523 			}
2524 
2525 			unlink_free_space(ctl, entry, true);
2526 			kmem_cache_free(btrfs_free_space_cachep, entry);
2527 		}
2528 
2529 		spin_unlock(&ctl->tree_lock);
2530 
2531 		ret = do_trimming(block_group, total_trimmed, start, bytes,
2532 				  extent_start, extent_bytes, extent_trim_state);
2533 		if (ret) {
2534 			block_group->discard_cursor = start + bytes;
2535 			break;
2536 		}
2537 next:
2538 		start += bytes;
2539 		block_group->discard_cursor = start;
2540 		if (async && *total_trimmed)
2541 			break;
2542 
2543 		if (btrfs_trim_interrupted()) {
2544 			ret = -ERESTARTSYS;
2545 			break;
2546 		}
2547 
2548 		cond_resched();
2549 	}
2550 
2551 	return ret;
2552 
2553 out_unlock:
2554 	block_group->discard_cursor = btrfs_block_group_end(block_group);
2555 	spin_unlock(&ctl->tree_lock);
2556 
2557 	return ret;
2558 }
2559 
2560 void btrfs_trim_fully_remapped_block_group(struct btrfs_block_group *bg)
2561 {
2562 	struct btrfs_fs_info *fs_info = bg->fs_info;
2563 	struct btrfs_discard_ctl *discard_ctl = &fs_info->discard_ctl;
2564 	int ret = 0;
2565 	u64 bytes, trimmed;
2566 	const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);
2567 	u64 end = btrfs_block_group_end(bg);
2568 
2569 	if (!test_bit(BLOCK_GROUP_FLAG_STRIPE_REMOVAL_PENDING, &bg->runtime_flags)) {
2570 		bg->discard_cursor = end;
2571 
2572 		if (bg->used == 0) {
2573 			spin_lock(&fs_info->unused_bgs_lock);
2574 			if (!list_empty(&bg->bg_list)) {
2575 				list_del_init(&bg->bg_list);
2576 				btrfs_put_block_group(bg);
2577 			}
2578 			spin_unlock(&fs_info->unused_bgs_lock);
2579 
2580 			btrfs_mark_bg_unused(bg);
2581 		}
2582 
2583 		return;
2584 	}
2585 
2586 	bytes = end - bg->discard_cursor;
2587 
2588 	if (max_discard_size &&
2589 	    bytes >= (max_discard_size + BTRFS_ASYNC_DISCARD_MIN_FILTER))
2590 		bytes = max_discard_size;
2591 
2592 	ret = btrfs_discard_extent(fs_info, bg->discard_cursor, bytes, &trimmed, false);
2593 	if (ret)
2594 		return;
2595 
2596 	bg->discard_cursor += trimmed;
2597 
2598 	if (bg->discard_cursor < end)
2599 		return;
2600 
2601 	btrfs_complete_bg_remapping(bg);
2602 }
2603 
2604 /*
2605  * If we break out of trimming a bitmap prematurely, we should reset the
2606  * trimming bit.  In a rather contrived case, it's possible to race here so
2607  * reset the state to BTRFS_TRIM_STATE_UNTRIMMED.
2608  *
2609  * start = start of bitmap
2610  * end = near end of bitmap
2611  *
2612  * Thread 1:			Thread 2:
2613  * trim_bitmaps(start)
2614  *				trim_bitmaps(end)
2615  *				end_trimming_bitmap()
2616  * reset_trimming_bitmap()
2617  */
2618 static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset)
2619 {
2620 	struct btrfs_free_space *entry;
2621 
2622 	spin_lock(&ctl->tree_lock);
2623 	entry = tree_search_offset(ctl, offset, 1, 0);
2624 	if (entry) {
2625 		if (btrfs_free_space_trimmed(entry)) {
2626 			ctl->discardable_extents[BTRFS_STAT_CURR] +=
2627 				entry->bitmap_extents;
2628 			ctl->discardable_bytes[BTRFS_STAT_CURR] += entry->bytes;
2629 		}
2630 		entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
2631 	}
2632 
2633 	spin_unlock(&ctl->tree_lock);
2634 }
2635 
2636 static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl,
2637 				struct btrfs_free_space *entry)
2638 {
2639 	if (btrfs_free_space_trimming_bitmap(entry)) {
2640 		entry->trim_state = BTRFS_TRIM_STATE_TRIMMED;
2641 		ctl->discardable_extents[BTRFS_STAT_CURR] -=
2642 			entry->bitmap_extents;
2643 		ctl->discardable_bytes[BTRFS_STAT_CURR] -= entry->bytes;
2644 	}
2645 }
2646 
2647 /*
2648  * If @async is set, then we will trim 1 region and return.
2649  */
2650 static int trim_bitmaps(struct btrfs_block_group *block_group,
2651 			u64 *total_trimmed, u64 start, u64 end, u64 minlen,
2652 			u64 maxlen, bool async)
2653 {
2654 	struct btrfs_discard_ctl *discard_ctl =
2655 					&block_group->fs_info->discard_ctl;
2656 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2657 	struct btrfs_free_space *entry;
2658 	int ret = 0;
2659 	int ret2;
2660 	u64 bytes;
2661 	u64 offset = offset_to_bitmap(ctl, start);
2662 	const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);
2663 
2664 	while (offset < end) {
2665 		bool next_bitmap = false;
2666 
2667 		spin_lock(&ctl->tree_lock);
2668 
2669 		if (ctl->free_space < minlen) {
2670 			block_group->discard_cursor =
2671 				btrfs_block_group_end(block_group);
2672 			spin_unlock(&ctl->tree_lock);
2673 			break;
2674 		}
2675 
2676 		entry = tree_search_offset(ctl, offset, 1, 0);
2677 		/*
2678 		 * Bitmaps are marked trimmed lossily now to prevent constant
2679 		 * discarding of the same bitmap (the reason why we are bound
2680 		 * by the filters).  So, retrim the block group bitmaps when we
2681 		 * are preparing to punt to the unused_bgs list.  This uses
2682 		 * @minlen to determine if we are in BTRFS_DISCARD_INDEX_UNUSED
2683 		 * which is the only discard index which sets minlen to 0.
2684 		 */
2685 		if (!entry || (async && minlen && start == offset &&
2686 			       btrfs_free_space_trimmed(entry))) {
2687 			spin_unlock(&ctl->tree_lock);
2688 			next_bitmap = true;
2689 			goto next;
2690 		}
2691 
2692 		/*
2693 		 * Async discard bitmap trimming begins at by setting the start
2694 		 * to be key.objectid and the offset_to_bitmap() aligns to the
2695 		 * start of the bitmap.  This lets us know we are fully
2696 		 * scanning the bitmap rather than only some portion of it.
2697 		 */
2698 		if (start == offset)
2699 			entry->trim_state = BTRFS_TRIM_STATE_TRIMMING;
2700 
2701 		bytes = minlen;
2702 		ret2 = search_bitmap(ctl, entry, &start, &bytes, false);
2703 		if (ret2 || start >= end) {
2704 			/*
2705 			 * We lossily consider a bitmap trimmed if we only skip
2706 			 * over regions <= BTRFS_ASYNC_DISCARD_MIN_FILTER.
2707 			 */
2708 			if (ret2 && minlen <= BTRFS_ASYNC_DISCARD_MIN_FILTER)
2709 				end_trimming_bitmap(ctl, entry);
2710 			else
2711 				entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
2712 			spin_unlock(&ctl->tree_lock);
2713 			next_bitmap = true;
2714 			goto next;
2715 		}
2716 
2717 		/*
2718 		 * We already trimmed a region, but are using the locking above
2719 		 * to reset the trim_state.
2720 		 */
2721 		if (async && *total_trimmed) {
2722 			spin_unlock(&ctl->tree_lock);
2723 			return ret;
2724 		}
2725 
2726 		bytes = min(bytes, end - start);
2727 		if (bytes < minlen || (async && maxlen && bytes > maxlen)) {
2728 			spin_unlock(&ctl->tree_lock);
2729 			goto next;
2730 		}
2731 
2732 		/*
2733 		 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.
2734 		 * If X < @minlen, we won't trim X when we come back around.
2735 		 * So trim it now.  We differ here from trimming extents as we
2736 		 * don't keep individual state per bit.
2737 		 */
2738 		if (async &&
2739 		    max_discard_size &&
2740 		    bytes > (max_discard_size + minlen))
2741 			bytes = max_discard_size;
2742 
2743 		bitmap_clear_bits(ctl, entry, start, bytes, true);
2744 		if (entry->bytes == 0)
2745 			free_bitmap(ctl, entry);
2746 
2747 		spin_unlock(&ctl->tree_lock);
2748 
2749 		ret = do_trimming(block_group, total_trimmed, start, bytes,
2750 				  start, bytes, 0);
2751 		if (ret) {
2752 			reset_trimming_bitmap(ctl, offset);
2753 			block_group->discard_cursor =
2754 				btrfs_block_group_end(block_group);
2755 			break;
2756 		}
2757 next:
2758 		if (next_bitmap) {
2759 			const int unit = block_group->fs_info->sectorsize;
2760 
2761 			offset += BITS_PER_BITMAP * unit;
2762 			start = offset;
2763 		} else {
2764 			start += bytes;
2765 		}
2766 		block_group->discard_cursor = start;
2767 
2768 		if (btrfs_trim_interrupted()) {
2769 			if (start != offset)
2770 				reset_trimming_bitmap(ctl, offset);
2771 			ret = -ERESTARTSYS;
2772 			break;
2773 		}
2774 
2775 		cond_resched();
2776 	}
2777 
2778 	if (offset >= end)
2779 		block_group->discard_cursor = end;
2780 
2781 	return ret;
2782 }
2783 
2784 int btrfs_trim_block_group(struct btrfs_block_group *block_group,
2785 			   u64 *trimmed, u64 start, u64 end, u64 minlen)
2786 {
2787 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2788 	const int unit = block_group->fs_info->sectorsize;
2789 	int ret;
2790 	u64 rem = 0;
2791 
2792 	ASSERT(!btrfs_is_zoned(block_group->fs_info));
2793 
2794 	*trimmed = 0;
2795 
2796 	spin_lock(&block_group->lock);
2797 	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {
2798 		spin_unlock(&block_group->lock);
2799 		return 0;
2800 	}
2801 	btrfs_freeze_block_group(block_group);
2802 	spin_unlock(&block_group->lock);
2803 
2804 	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, false);
2805 	if (ret)
2806 		goto out;
2807 
2808 	ret = trim_bitmaps(block_group, trimmed, start, end, minlen, 0, false);
2809 	div64_u64_rem(end, BITS_PER_BITMAP * unit, &rem);
2810 	/* If we ended in the middle of a bitmap, reset the trimming flag */
2811 	if (rem)
2812 		reset_trimming_bitmap(ctl, offset_to_bitmap(ctl, end));
2813 out:
2814 	btrfs_unfreeze_block_group(block_group);
2815 	return ret;
2816 }
2817 
2818 int btrfs_trim_block_group_extents(struct btrfs_block_group *block_group,
2819 				   u64 *trimmed, u64 start, u64 end, u64 minlen,
2820 				   bool async)
2821 {
2822 	int ret;
2823 
2824 	*trimmed = 0;
2825 
2826 	spin_lock(&block_group->lock);
2827 	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {
2828 		spin_unlock(&block_group->lock);
2829 		return 0;
2830 	}
2831 	btrfs_freeze_block_group(block_group);
2832 	spin_unlock(&block_group->lock);
2833 
2834 	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, async);
2835 	btrfs_unfreeze_block_group(block_group);
2836 
2837 	return ret;
2838 }
2839 
2840 int btrfs_trim_block_group_bitmaps(struct btrfs_block_group *block_group,
2841 				   u64 *trimmed, u64 start, u64 end, u64 minlen,
2842 				   u64 maxlen, bool async)
2843 {
2844 	int ret;
2845 
2846 	*trimmed = 0;
2847 
2848 	spin_lock(&block_group->lock);
2849 	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {
2850 		spin_unlock(&block_group->lock);
2851 		return 0;
2852 	}
2853 	btrfs_freeze_block_group(block_group);
2854 	spin_unlock(&block_group->lock);
2855 
2856 	ret = trim_bitmaps(block_group, trimmed, start, end, minlen, maxlen,
2857 			   async);
2858 
2859 	btrfs_unfreeze_block_group(block_group);
2860 
2861 	return ret;
2862 }
2863 
2864 bool btrfs_free_space_cache_v1_active(struct btrfs_fs_info *fs_info)
2865 {
2866 	return btrfs_super_cache_generation(fs_info->super_copy);
2867 }
2868 
2869 int btrfs_cleanup_free_space_cache_v1(struct btrfs_fs_info *fs_info)
2870 {
2871 	struct btrfs_trans_handle *trans;
2872 	struct rb_node *node;
2873 	int ret;
2874 
2875 	btrfs_info(fs_info, "cleaning free space cache v1");
2876 
2877 	/*
2878 	 * update_super_roots() zeroes super_copy->cache_generation while
2879 	 * BTRFS_FS_CLEANUP_SPACE_CACHE_V1 is set, so this needs a commit.
2880 	 */
2881 	trans = btrfs_start_transaction(fs_info->tree_root, 0);
2882 	if (IS_ERR(trans))
2883 		return PTR_ERR(trans);
2884 
2885 	set_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags);
2886 	for (node = rb_first_cached(&fs_info->block_group_cache_tree); node;
2887 	     node = rb_next(node)) {
2888 		struct btrfs_block_group *block_group;
2889 
2890 		block_group = rb_entry(node, struct btrfs_block_group, cache_node);
2891 		ret = btrfs_remove_free_space_inode(trans, NULL, block_group);
2892 		if (unlikely(ret)) {
2893 			btrfs_abort_transaction(trans, ret);
2894 			btrfs_end_transaction(trans);
2895 			goto out;
2896 		}
2897 	}
2898 
2899 	ret = btrfs_commit_transaction(trans);
2900 out:
2901 	clear_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags);
2902 
2903 	return ret;
2904 }
2905 
2906 int __init btrfs_free_space_init(void)
2907 {
2908 	btrfs_free_space_cachep = KMEM_CACHE(btrfs_free_space, 0);
2909 	if (!btrfs_free_space_cachep)
2910 		return -ENOMEM;
2911 
2912 	btrfs_free_space_bitmap_cachep = kmem_cache_create("btrfs_free_space_bitmap",
2913 							PAGE_SIZE, PAGE_SIZE,
2914 							0, NULL);
2915 	if (!btrfs_free_space_bitmap_cachep) {
2916 		kmem_cache_destroy(btrfs_free_space_cachep);
2917 		return -ENOMEM;
2918 	}
2919 
2920 	return 0;
2921 }
2922 
2923 void __cold btrfs_free_space_exit(void)
2924 {
2925 	kmem_cache_destroy(btrfs_free_space_cachep);
2926 	kmem_cache_destroy(btrfs_free_space_bitmap_cachep);
2927 }
2928 
2929 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
2930 /*
2931  * Use this if you need to make a bitmap or extent entry specifically, it
2932  * doesn't do any of the merging that add_free_space does, this acts a lot like
2933  * how the free space cache loading stuff works, so you can get really weird
2934  * configurations.
2935  */
2936 int test_add_free_space_entry(struct btrfs_block_group *cache,
2937 			      u64 offset, u64 bytes, bool bitmap)
2938 {
2939 	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
2940 	struct btrfs_free_space *info = NULL, *bitmap_info;
2941 	void *map = NULL;
2942 	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_TRIMMED;
2943 	u64 bytes_added;
2944 	int ret;
2945 
2946 again:
2947 	if (!info) {
2948 		info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2949 		if (!info)
2950 			return -ENOMEM;
2951 	}
2952 
2953 	if (!bitmap) {
2954 		spin_lock(&ctl->tree_lock);
2955 		info->offset = offset;
2956 		info->bytes = bytes;
2957 		info->max_extent_size = 0;
2958 		ret = link_free_space(ctl, info);
2959 		spin_unlock(&ctl->tree_lock);
2960 		if (ret)
2961 			kmem_cache_free(btrfs_free_space_cachep, info);
2962 		return ret;
2963 	}
2964 
2965 	if (!map) {
2966 		map = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, GFP_NOFS);
2967 		if (!map) {
2968 			kmem_cache_free(btrfs_free_space_cachep, info);
2969 			return -ENOMEM;
2970 		}
2971 	}
2972 
2973 	spin_lock(&ctl->tree_lock);
2974 	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2975 					 1, 0);
2976 	if (!bitmap_info) {
2977 		info->bitmap = map;
2978 		map = NULL;
2979 		add_new_bitmap(ctl, info, offset);
2980 		bitmap_info = info;
2981 		info = NULL;
2982 	}
2983 
2984 	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
2985 					  trim_state);
2986 
2987 	bytes -= bytes_added;
2988 	offset += bytes_added;
2989 	spin_unlock(&ctl->tree_lock);
2990 
2991 	if (bytes)
2992 		goto again;
2993 
2994 	if (info)
2995 		kmem_cache_free(btrfs_free_space_cachep, info);
2996 	if (map)
2997 		kmem_cache_free(btrfs_free_space_bitmap_cachep, map);
2998 	return 0;
2999 }
3000 
3001 /*
3002  * Checks to see if the given range is in the free space cache.  This is really
3003  * just used to check the absence of space, so if there is free space in the
3004  * range at all we will return 1.
3005  */
3006 int test_check_exists(struct btrfs_block_group *cache,
3007 		      u64 offset, u64 bytes)
3008 {
3009 	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3010 	const int unit = cache->fs_info->sectorsize;
3011 	struct btrfs_free_space *info;
3012 	int ret = 0;
3013 
3014 	spin_lock(&ctl->tree_lock);
3015 	info = tree_search_offset(ctl, offset, 0, 0);
3016 	if (!info) {
3017 		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3018 					  1, 0);
3019 		if (!info)
3020 			goto out;
3021 	}
3022 
3023 have_info:
3024 	if (info->bitmap) {
3025 		u64 bit_off, bit_bytes;
3026 		struct rb_node *n;
3027 		struct btrfs_free_space *tmp;
3028 
3029 		bit_off = offset;
3030 		bit_bytes = unit;
3031 		ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
3032 		if (!ret) {
3033 			if (bit_off == offset) {
3034 				ret = 1;
3035 				goto out;
3036 			} else if (bit_off > offset &&
3037 				   offset + bytes > bit_off) {
3038 				ret = 1;
3039 				goto out;
3040 			}
3041 		}
3042 
3043 		n = rb_prev(&info->offset_index);
3044 		while (n) {
3045 			tmp = rb_entry(n, struct btrfs_free_space,
3046 				       offset_index);
3047 			if (tmp->offset + tmp->bytes < offset)
3048 				break;
3049 			if (offset + bytes < tmp->offset) {
3050 				n = rb_prev(&tmp->offset_index);
3051 				continue;
3052 			}
3053 			info = tmp;
3054 			goto have_info;
3055 		}
3056 
3057 		n = rb_next(&info->offset_index);
3058 		while (n) {
3059 			tmp = rb_entry(n, struct btrfs_free_space,
3060 				       offset_index);
3061 			if (offset + bytes < tmp->offset)
3062 				break;
3063 			if (tmp->offset + tmp->bytes < offset) {
3064 				n = rb_next(&tmp->offset_index);
3065 				continue;
3066 			}
3067 			info = tmp;
3068 			goto have_info;
3069 		}
3070 
3071 		ret = 0;
3072 		goto out;
3073 	}
3074 
3075 	if (info->offset == offset) {
3076 		ret = 1;
3077 		goto out;
3078 	}
3079 
3080 	if (offset > info->offset && offset < info->offset + info->bytes)
3081 		ret = 1;
3082 out:
3083 	spin_unlock(&ctl->tree_lock);
3084 	return ret;
3085 }
3086 #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3087