brintos / linux-shallow public Read only

1// SPDX-License-Identifier: GPL-2.02/*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/error-injection.h>13#include <linux/sched/mm.h>14#include "ctree.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 "subpage.h"26#include "inode-item.h"27#include "accessors.h"28#include "file-item.h"29#include "file.h"30#include "super.h"31 32#define BITS_PER_BITMAP		(PAGE_SIZE * 8UL)33#define MAX_CACHE_BYTES_PER_GIG	SZ_64K34#define FORCE_EXTENT_THRESHOLD	SZ_1M35 36static struct kmem_cache *btrfs_free_space_cachep;37static struct kmem_cache *btrfs_free_space_bitmap_cachep;38 39struct btrfs_trim_range {40	u64 start;41	u64 bytes;42	struct list_head list;43};44 45static int link_free_space(struct btrfs_free_space_ctl *ctl,46			   struct btrfs_free_space *info);47static void unlink_free_space(struct btrfs_free_space_ctl *ctl,48			      struct btrfs_free_space *info, bool update_stat);49static int search_bitmap(struct btrfs_free_space_ctl *ctl,50			 struct btrfs_free_space *bitmap_info, u64 *offset,51			 u64 *bytes, bool for_alloc);52static void free_bitmap(struct btrfs_free_space_ctl *ctl,53			struct btrfs_free_space *bitmap_info);54static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,55			      struct btrfs_free_space *info, u64 offset,56			      u64 bytes, bool update_stats);57 58static void btrfs_crc32c_final(u32 crc, u8 *result)59{60	put_unaligned_le32(~crc, result);61}62 63static void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)64{65	struct btrfs_free_space *info;66	struct rb_node *node;67 68	while ((node = rb_last(&ctl->free_space_offset)) != NULL) {69		info = rb_entry(node, struct btrfs_free_space, offset_index);70		if (!info->bitmap) {71			unlink_free_space(ctl, info, true);72			kmem_cache_free(btrfs_free_space_cachep, info);73		} else {74			free_bitmap(ctl, info);75		}76 77		cond_resched_lock(&ctl->tree_lock);78	}79}80 81static struct inode *__lookup_free_space_inode(struct btrfs_root *root,82					       struct btrfs_path *path,83					       u64 offset)84{85	struct btrfs_key key;86	struct btrfs_key location;87	struct btrfs_disk_key disk_key;88	struct btrfs_free_space_header *header;89	struct extent_buffer *leaf;90	struct inode *inode = NULL;91	unsigned nofs_flag;92	int ret;93 94	key.objectid = BTRFS_FREE_SPACE_OBJECTID;95	key.offset = offset;96	key.type = 0;97 98	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);99	if (ret < 0)100		return ERR_PTR(ret);101	if (ret > 0) {102		btrfs_release_path(path);103		return ERR_PTR(-ENOENT);104	}105 106	leaf = path->nodes[0];107	header = btrfs_item_ptr(leaf, path->slots[0],108				struct btrfs_free_space_header);109	btrfs_free_space_key(leaf, header, &disk_key);110	btrfs_disk_key_to_cpu(&location, &disk_key);111	btrfs_release_path(path);112 113	/*114	 * We are often under a trans handle at this point, so we need to make115	 * sure NOFS is set to keep us from deadlocking.116	 */117	nofs_flag = memalloc_nofs_save();118	inode = btrfs_iget_path(location.objectid, root, path);119	btrfs_release_path(path);120	memalloc_nofs_restore(nofs_flag);121	if (IS_ERR(inode))122		return inode;123 124	mapping_set_gfp_mask(inode->i_mapping,125			mapping_gfp_constraint(inode->i_mapping,126			~(__GFP_FS | __GFP_HIGHMEM)));127 128	return inode;129}130 131struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group,132		struct btrfs_path *path)133{134	struct btrfs_fs_info *fs_info = block_group->fs_info;135	struct inode *inode = NULL;136	u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;137 138	spin_lock(&block_group->lock);139	if (block_group->inode)140		inode = igrab(&block_group->inode->vfs_inode);141	spin_unlock(&block_group->lock);142	if (inode)143		return inode;144 145	inode = __lookup_free_space_inode(fs_info->tree_root, path,146					  block_group->start);147	if (IS_ERR(inode))148		return inode;149 150	spin_lock(&block_group->lock);151	if (!((BTRFS_I(inode)->flags & flags) == flags)) {152		btrfs_info(fs_info, "Old style space inode found, converting.");153		BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |154			BTRFS_INODE_NODATACOW;155		block_group->disk_cache_state = BTRFS_DC_CLEAR;156	}157 158	if (!test_and_set_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags))159		block_group->inode = BTRFS_I(igrab(inode));160	spin_unlock(&block_group->lock);161 162	return inode;163}164 165static int __create_free_space_inode(struct btrfs_root *root,166				     struct btrfs_trans_handle *trans,167				     struct btrfs_path *path,168				     u64 ino, u64 offset)169{170	struct btrfs_key key;171	struct btrfs_disk_key disk_key;172	struct btrfs_free_space_header *header;173	struct btrfs_inode_item *inode_item;174	struct extent_buffer *leaf;175	/* We inline CRCs for the free disk space cache */176	const u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC |177			  BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;178	int ret;179 180	ret = btrfs_insert_empty_inode(trans, root, path, ino);181	if (ret)182		return ret;183 184	leaf = path->nodes[0];185	inode_item = btrfs_item_ptr(leaf, path->slots[0],186				    struct btrfs_inode_item);187	btrfs_item_key(leaf, &disk_key, path->slots[0]);188	memzero_extent_buffer(leaf, (unsigned long)inode_item,189			     sizeof(*inode_item));190	btrfs_set_inode_generation(leaf, inode_item, trans->transid);191	btrfs_set_inode_size(leaf, inode_item, 0);192	btrfs_set_inode_nbytes(leaf, inode_item, 0);193	btrfs_set_inode_uid(leaf, inode_item, 0);194	btrfs_set_inode_gid(leaf, inode_item, 0);195	btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);196	btrfs_set_inode_flags(leaf, inode_item, flags);197	btrfs_set_inode_nlink(leaf, inode_item, 1);198	btrfs_set_inode_transid(leaf, inode_item, trans->transid);199	btrfs_set_inode_block_group(leaf, inode_item, offset);200	btrfs_mark_buffer_dirty(trans, leaf);201	btrfs_release_path(path);202 203	key.objectid = BTRFS_FREE_SPACE_OBJECTID;204	key.offset = offset;205	key.type = 0;206	ret = btrfs_insert_empty_item(trans, root, path, &key,207				      sizeof(struct btrfs_free_space_header));208	if (ret < 0) {209		btrfs_release_path(path);210		return ret;211	}212 213	leaf = path->nodes[0];214	header = btrfs_item_ptr(leaf, path->slots[0],215				struct btrfs_free_space_header);216	memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header));217	btrfs_set_free_space_key(leaf, header, &disk_key);218	btrfs_mark_buffer_dirty(trans, leaf);219	btrfs_release_path(path);220 221	return 0;222}223 224int create_free_space_inode(struct btrfs_trans_handle *trans,225			    struct btrfs_block_group *block_group,226			    struct btrfs_path *path)227{228	int ret;229	u64 ino;230 231	ret = btrfs_get_free_objectid(trans->fs_info->tree_root, &ino);232	if (ret < 0)233		return ret;234 235	return __create_free_space_inode(trans->fs_info->tree_root, trans, path,236					 ino, block_group->start);237}238 239/*240 * inode is an optional sink: if it is NULL, btrfs_remove_free_space_inode241 * handles lookup, otherwise it takes ownership and iputs the inode.242 * Don't reuse an inode pointer after passing it into this function.243 */244int btrfs_remove_free_space_inode(struct btrfs_trans_handle *trans,245				  struct inode *inode,246				  struct btrfs_block_group *block_group)247{248	struct btrfs_path *path;249	struct btrfs_key key;250	int ret = 0;251 252	path = btrfs_alloc_path();253	if (!path)254		return -ENOMEM;255 256	if (!inode)257		inode = lookup_free_space_inode(block_group, path);258	if (IS_ERR(inode)) {259		if (PTR_ERR(inode) != -ENOENT)260			ret = PTR_ERR(inode);261		goto out;262	}263	ret = btrfs_orphan_add(trans, BTRFS_I(inode));264	if (ret) {265		btrfs_add_delayed_iput(BTRFS_I(inode));266		goto out;267	}268	clear_nlink(inode);269	/* One for the block groups ref */270	spin_lock(&block_group->lock);271	if (test_and_clear_bit(BLOCK_GROUP_FLAG_IREF, &block_group->runtime_flags)) {272		block_group->inode = NULL;273		spin_unlock(&block_group->lock);274		iput(inode);275	} else {276		spin_unlock(&block_group->lock);277	}278	/* One for the lookup ref */279	btrfs_add_delayed_iput(BTRFS_I(inode));280 281	key.objectid = BTRFS_FREE_SPACE_OBJECTID;282	key.type = 0;283	key.offset = block_group->start;284	ret = btrfs_search_slot(trans, trans->fs_info->tree_root, &key, path,285				-1, 1);286	if (ret) {287		if (ret > 0)288			ret = 0;289		goto out;290	}291	ret = btrfs_del_item(trans, trans->fs_info->tree_root, path);292out:293	btrfs_free_path(path);294	return ret;295}296 297int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans,298				    struct btrfs_block_group *block_group,299				    struct inode *vfs_inode)300{301	struct btrfs_truncate_control control = {302		.inode = BTRFS_I(vfs_inode),303		.new_size = 0,304		.ino = btrfs_ino(BTRFS_I(vfs_inode)),305		.min_type = BTRFS_EXTENT_DATA_KEY,306		.clear_extent_range = true,307	};308	struct btrfs_inode *inode = BTRFS_I(vfs_inode);309	struct btrfs_root *root = inode->root;310	struct extent_state *cached_state = NULL;311	int ret = 0;312	bool locked = false;313 314	if (block_group) {315		struct btrfs_path *path = btrfs_alloc_path();316 317		if (!path) {318			ret = -ENOMEM;319			goto fail;320		}321		locked = true;322		mutex_lock(&trans->transaction->cache_write_mutex);323		if (!list_empty(&block_group->io_list)) {324			list_del_init(&block_group->io_list);325 326			btrfs_wait_cache_io(trans, block_group, path);327			btrfs_put_block_group(block_group);328		}329 330		/*331		 * now that we've truncated the cache away, its no longer332		 * setup or written333		 */334		spin_lock(&block_group->lock);335		block_group->disk_cache_state = BTRFS_DC_CLEAR;336		spin_unlock(&block_group->lock);337		btrfs_free_path(path);338	}339 340	btrfs_i_size_write(inode, 0);341	truncate_pagecache(vfs_inode, 0);342 343	lock_extent(&inode->io_tree, 0, (u64)-1, &cached_state);344	btrfs_drop_extent_map_range(inode, 0, (u64)-1, false);345 346	/*347	 * We skip the throttling logic for free space cache inodes, so we don't348	 * need to check for -EAGAIN.349	 */350	ret = btrfs_truncate_inode_items(trans, root, &control);351 352	inode_sub_bytes(&inode->vfs_inode, control.sub_bytes);353	btrfs_inode_safe_disk_i_size_write(inode, control.last_size);354 355	unlock_extent(&inode->io_tree, 0, (u64)-1, &cached_state);356	if (ret)357		goto fail;358 359	ret = btrfs_update_inode(trans, inode);360 361fail:362	if (locked)363		mutex_unlock(&trans->transaction->cache_write_mutex);364	if (ret)365		btrfs_abort_transaction(trans, ret);366 367	return ret;368}369 370static void readahead_cache(struct inode *inode)371{372	struct file_ra_state ra;373	unsigned long last_index;374 375	file_ra_state_init(&ra, inode->i_mapping);376	last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;377 378	page_cache_sync_readahead(inode->i_mapping, &ra, NULL, 0, last_index);379}380 381static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode,382		       int write)383{384	int num_pages;385 386	num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE);387 388	/* Make sure we can fit our crcs and generation into the first page */389	if (write && (num_pages * sizeof(u32) + sizeof(u64)) > PAGE_SIZE)390		return -ENOSPC;391 392	memset(io_ctl, 0, sizeof(struct btrfs_io_ctl));393 394	io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS);395	if (!io_ctl->pages)396		return -ENOMEM;397 398	io_ctl->num_pages = num_pages;399	io_ctl->fs_info = inode_to_fs_info(inode);400	io_ctl->inode = inode;401 402	return 0;403}404ALLOW_ERROR_INJECTION(io_ctl_init, ERRNO);405 406static void io_ctl_free(struct btrfs_io_ctl *io_ctl)407{408	kfree(io_ctl->pages);409	io_ctl->pages = NULL;410}411 412static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl)413{414	if (io_ctl->cur) {415		io_ctl->cur = NULL;416		io_ctl->orig = NULL;417	}418}419 420static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear)421{422	ASSERT(io_ctl->index < io_ctl->num_pages);423	io_ctl->page = io_ctl->pages[io_ctl->index++];424	io_ctl->cur = page_address(io_ctl->page);425	io_ctl->orig = io_ctl->cur;426	io_ctl->size = PAGE_SIZE;427	if (clear)428		clear_page(io_ctl->cur);429}430 431static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl)432{433	int i;434 435	io_ctl_unmap_page(io_ctl);436 437	for (i = 0; i < io_ctl->num_pages; i++) {438		if (io_ctl->pages[i]) {439			btrfs_folio_clear_checked(io_ctl->fs_info,440					page_folio(io_ctl->pages[i]),441					page_offset(io_ctl->pages[i]),442					PAGE_SIZE);443			unlock_page(io_ctl->pages[i]);444			put_page(io_ctl->pages[i]);445		}446	}447}448 449static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, bool uptodate)450{451	struct page *page;452	struct inode *inode = io_ctl->inode;453	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);454	int i;455 456	for (i = 0; i < io_ctl->num_pages; i++) {457		int ret;458 459		page = find_or_create_page(inode->i_mapping, i, mask);460		if (!page) {461			io_ctl_drop_pages(io_ctl);462			return -ENOMEM;463		}464 465		ret = set_page_extent_mapped(page);466		if (ret < 0) {467			unlock_page(page);468			put_page(page);469			io_ctl_drop_pages(io_ctl);470			return ret;471		}472 473		io_ctl->pages[i] = page;474		if (uptodate && !PageUptodate(page)) {475			btrfs_read_folio(NULL, page_folio(page));476			lock_page(page);477			if (page->mapping != inode->i_mapping) {478				btrfs_err(BTRFS_I(inode)->root->fs_info,479					  "free space cache page truncated");480				io_ctl_drop_pages(io_ctl);481				return -EIO;482			}483			if (!PageUptodate(page)) {484				btrfs_err(BTRFS_I(inode)->root->fs_info,485					   "error reading free space cache");486				io_ctl_drop_pages(io_ctl);487				return -EIO;488			}489		}490	}491 492	for (i = 0; i < io_ctl->num_pages; i++)493		clear_page_dirty_for_io(io_ctl->pages[i]);494 495	return 0;496}497 498static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation)499{500	io_ctl_map_page(io_ctl, 1);501 502	/*503	 * Skip the csum areas.  If we don't check crcs then we just have a504	 * 64bit chunk at the front of the first page.505	 */506	io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);507	io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);508 509	put_unaligned_le64(generation, io_ctl->cur);510	io_ctl->cur += sizeof(u64);511}512 513static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation)514{515	u64 cache_gen;516 517	/*518	 * Skip the crc area.  If we don't check crcs then we just have a 64bit519	 * chunk at the front of the first page.520	 */521	io_ctl->cur += sizeof(u32) * io_ctl->num_pages;522	io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);523 524	cache_gen = get_unaligned_le64(io_ctl->cur);525	if (cache_gen != generation) {526		btrfs_err_rl(io_ctl->fs_info,527			"space cache generation (%llu) does not match inode (%llu)",528				cache_gen, generation);529		io_ctl_unmap_page(io_ctl);530		return -EIO;531	}532	io_ctl->cur += sizeof(u64);533	return 0;534}535 536static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index)537{538	u32 *tmp;539	u32 crc = ~(u32)0;540	unsigned offset = 0;541 542	if (index == 0)543		offset = sizeof(u32) * io_ctl->num_pages;544 545	crc = crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);546	btrfs_crc32c_final(crc, (u8 *)&crc);547	io_ctl_unmap_page(io_ctl);548	tmp = page_address(io_ctl->pages[0]);549	tmp += index;550	*tmp = crc;551}552 553static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index)554{555	u32 *tmp, val;556	u32 crc = ~(u32)0;557	unsigned offset = 0;558 559	if (index == 0)560		offset = sizeof(u32) * io_ctl->num_pages;561 562	tmp = page_address(io_ctl->pages[0]);563	tmp += index;564	val = *tmp;565 566	io_ctl_map_page(io_ctl, 0);567	crc = crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);568	btrfs_crc32c_final(crc, (u8 *)&crc);569	if (val != crc) {570		btrfs_err_rl(io_ctl->fs_info,571			"csum mismatch on free space cache");572		io_ctl_unmap_page(io_ctl);573		return -EIO;574	}575 576	return 0;577}578 579static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes,580			    void *bitmap)581{582	struct btrfs_free_space_entry *entry;583 584	if (!io_ctl->cur)585		return -ENOSPC;586 587	entry = io_ctl->cur;588	put_unaligned_le64(offset, &entry->offset);589	put_unaligned_le64(bytes, &entry->bytes);590	entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :591		BTRFS_FREE_SPACE_EXTENT;592	io_ctl->cur += sizeof(struct btrfs_free_space_entry);593	io_ctl->size -= sizeof(struct btrfs_free_space_entry);594 595	if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))596		return 0;597 598	io_ctl_set_crc(io_ctl, io_ctl->index - 1);599 600	/* No more pages to map */601	if (io_ctl->index >= io_ctl->num_pages)602		return 0;603 604	/* map the next page */605	io_ctl_map_page(io_ctl, 1);606	return 0;607}608 609static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap)610{611	if (!io_ctl->cur)612		return -ENOSPC;613 614	/*615	 * If we aren't at the start of the current page, unmap this one and616	 * map the next one if there is any left.617	 */618	if (io_ctl->cur != io_ctl->orig) {619		io_ctl_set_crc(io_ctl, io_ctl->index - 1);620		if (io_ctl->index >= io_ctl->num_pages)621			return -ENOSPC;622		io_ctl_map_page(io_ctl, 0);623	}624 625	copy_page(io_ctl->cur, bitmap);626	io_ctl_set_crc(io_ctl, io_ctl->index - 1);627	if (io_ctl->index < io_ctl->num_pages)628		io_ctl_map_page(io_ctl, 0);629	return 0;630}631 632static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl)633{634	/*635	 * If we're not on the boundary we know we've modified the page and we636	 * need to crc the page.637	 */638	if (io_ctl->cur != io_ctl->orig)639		io_ctl_set_crc(io_ctl, io_ctl->index - 1);640	else641		io_ctl_unmap_page(io_ctl);642 643	while (io_ctl->index < io_ctl->num_pages) {644		io_ctl_map_page(io_ctl, 1);645		io_ctl_set_crc(io_ctl, io_ctl->index - 1);646	}647}648 649static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl,650			    struct btrfs_free_space *entry, u8 *type)651{652	struct btrfs_free_space_entry *e;653	int ret;654 655	if (!io_ctl->cur) {656		ret = io_ctl_check_crc(io_ctl, io_ctl->index);657		if (ret)658			return ret;659	}660 661	e = io_ctl->cur;662	entry->offset = get_unaligned_le64(&e->offset);663	entry->bytes = get_unaligned_le64(&e->bytes);664	*type = e->type;665	io_ctl->cur += sizeof(struct btrfs_free_space_entry);666	io_ctl->size -= sizeof(struct btrfs_free_space_entry);667 668	if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))669		return 0;670 671	io_ctl_unmap_page(io_ctl);672 673	return 0;674}675 676static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl,677			      struct btrfs_free_space *entry)678{679	int ret;680 681	ret = io_ctl_check_crc(io_ctl, io_ctl->index);682	if (ret)683		return ret;684 685	copy_page(entry->bitmap, io_ctl->cur);686	io_ctl_unmap_page(io_ctl);687 688	return 0;689}690 691static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)692{693	struct btrfs_block_group *block_group = ctl->block_group;694	u64 max_bytes;695	u64 bitmap_bytes;696	u64 extent_bytes;697	u64 size = block_group->length;698	u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;699	u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);700 701	max_bitmaps = max_t(u64, max_bitmaps, 1);702 703	if (ctl->total_bitmaps > max_bitmaps)704		btrfs_err(block_group->fs_info,705"invalid free space control: bg start=%llu len=%llu total_bitmaps=%u unit=%u max_bitmaps=%llu bytes_per_bg=%llu",706			  block_group->start, block_group->length,707			  ctl->total_bitmaps, ctl->unit, max_bitmaps,708			  bytes_per_bg);709	ASSERT(ctl->total_bitmaps <= max_bitmaps);710 711	/*712	 * We are trying to keep the total amount of memory used per 1GiB of713	 * space to be MAX_CACHE_BYTES_PER_GIG.  However, with a reclamation714	 * mechanism of pulling extents >= FORCE_EXTENT_THRESHOLD out of715	 * bitmaps, we may end up using more memory than this.716	 */717	if (size < SZ_1G)718		max_bytes = MAX_CACHE_BYTES_PER_GIG;719	else720		max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);721 722	bitmap_bytes = ctl->total_bitmaps * ctl->unit;723 724	/*725	 * we want the extent entry threshold to always be at most 1/2 the max726	 * bytes we can have, or whatever is less than that.727	 */728	extent_bytes = max_bytes - bitmap_bytes;729	extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1);730 731	ctl->extents_thresh =732		div_u64(extent_bytes, sizeof(struct btrfs_free_space));733}734 735static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,736				   struct btrfs_free_space_ctl *ctl,737				   struct btrfs_path *path, u64 offset)738{739	struct btrfs_fs_info *fs_info = root->fs_info;740	struct btrfs_free_space_header *header;741	struct extent_buffer *leaf;742	struct btrfs_io_ctl io_ctl;743	struct btrfs_key key;744	struct btrfs_free_space *e, *n;745	LIST_HEAD(bitmaps);746	u64 num_entries;747	u64 num_bitmaps;748	u64 generation;749	u8 type;750	int ret = 0;751 752	/* Nothing in the space cache, goodbye */753	if (!i_size_read(inode))754		return 0;755 756	key.objectid = BTRFS_FREE_SPACE_OBJECTID;757	key.offset = offset;758	key.type = 0;759 760	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);761	if (ret < 0)762		return 0;763	else if (ret > 0) {764		btrfs_release_path(path);765		return 0;766	}767 768	ret = -1;769 770	leaf = path->nodes[0];771	header = btrfs_item_ptr(leaf, path->slots[0],772				struct btrfs_free_space_header);773	num_entries = btrfs_free_space_entries(leaf, header);774	num_bitmaps = btrfs_free_space_bitmaps(leaf, header);775	generation = btrfs_free_space_generation(leaf, header);776	btrfs_release_path(path);777 778	if (!BTRFS_I(inode)->generation) {779		btrfs_info(fs_info,780			   "the free space cache file (%llu) is invalid, skip it",781			   offset);782		return 0;783	}784 785	if (BTRFS_I(inode)->generation != generation) {786		btrfs_err(fs_info,787			  "free space inode generation (%llu) did not match free space cache generation (%llu)",788			  BTRFS_I(inode)->generation, generation);789		return 0;790	}791 792	if (!num_entries)793		return 0;794 795	ret = io_ctl_init(&io_ctl, inode, 0);796	if (ret)797		return ret;798 799	readahead_cache(inode);800 801	ret = io_ctl_prepare_pages(&io_ctl, true);802	if (ret)803		goto out;804 805	ret = io_ctl_check_crc(&io_ctl, 0);806	if (ret)807		goto free_cache;808 809	ret = io_ctl_check_generation(&io_ctl, generation);810	if (ret)811		goto free_cache;812 813	while (num_entries) {814		e = kmem_cache_zalloc(btrfs_free_space_cachep,815				      GFP_NOFS);816		if (!e) {817			ret = -ENOMEM;818			goto free_cache;819		}820 821		ret = io_ctl_read_entry(&io_ctl, e, &type);822		if (ret) {823			kmem_cache_free(btrfs_free_space_cachep, e);824			goto free_cache;825		}826 827		if (!e->bytes) {828			ret = -1;829			kmem_cache_free(btrfs_free_space_cachep, e);830			goto free_cache;831		}832 833		if (type == BTRFS_FREE_SPACE_EXTENT) {834			spin_lock(&ctl->tree_lock);835			ret = link_free_space(ctl, e);836			spin_unlock(&ctl->tree_lock);837			if (ret) {838				btrfs_err(fs_info,839					"Duplicate entries in free space cache, dumping");840				kmem_cache_free(btrfs_free_space_cachep, e);841				goto free_cache;842			}843		} else {844			ASSERT(num_bitmaps);845			num_bitmaps--;846			e->bitmap = kmem_cache_zalloc(847					btrfs_free_space_bitmap_cachep, GFP_NOFS);848			if (!e->bitmap) {849				ret = -ENOMEM;850				kmem_cache_free(851					btrfs_free_space_cachep, e);852				goto free_cache;853			}854			spin_lock(&ctl->tree_lock);855			ret = link_free_space(ctl, e);856			if (ret) {857				spin_unlock(&ctl->tree_lock);858				btrfs_err(fs_info,859					"Duplicate entries in free space cache, dumping");860				kmem_cache_free(btrfs_free_space_bitmap_cachep, e->bitmap);861				kmem_cache_free(btrfs_free_space_cachep, e);862				goto free_cache;863			}864			ctl->total_bitmaps++;865			recalculate_thresholds(ctl);866			spin_unlock(&ctl->tree_lock);867			list_add_tail(&e->list, &bitmaps);868		}869 870		num_entries--;871	}872 873	io_ctl_unmap_page(&io_ctl);874 875	/*876	 * We add the bitmaps at the end of the entries in order that877	 * the bitmap entries are added to the cache.878	 */879	list_for_each_entry_safe(e, n, &bitmaps, list) {880		list_del_init(&e->list);881		ret = io_ctl_read_bitmap(&io_ctl, e);882		if (ret)883			goto free_cache;884	}885 886	io_ctl_drop_pages(&io_ctl);887	ret = 1;888out:889	io_ctl_free(&io_ctl);890	return ret;891free_cache:892	io_ctl_drop_pages(&io_ctl);893 894	spin_lock(&ctl->tree_lock);895	__btrfs_remove_free_space_cache(ctl);896	spin_unlock(&ctl->tree_lock);897	goto out;898}899 900static int copy_free_space_cache(struct btrfs_block_group *block_group,901				 struct btrfs_free_space_ctl *ctl)902{903	struct btrfs_free_space *info;904	struct rb_node *n;905	int ret = 0;906 907	while (!ret && (n = rb_first(&ctl->free_space_offset)) != NULL) {908		info = rb_entry(n, struct btrfs_free_space, offset_index);909		if (!info->bitmap) {910			const u64 offset = info->offset;911			const u64 bytes = info->bytes;912 913			unlink_free_space(ctl, info, true);914			spin_unlock(&ctl->tree_lock);915			kmem_cache_free(btrfs_free_space_cachep, info);916			ret = btrfs_add_free_space(block_group, offset, bytes);917			spin_lock(&ctl->tree_lock);918		} else {919			u64 offset = info->offset;920			u64 bytes = ctl->unit;921 922			ret = search_bitmap(ctl, info, &offset, &bytes, false);923			if (ret == 0) {924				bitmap_clear_bits(ctl, info, offset, bytes, true);925				spin_unlock(&ctl->tree_lock);926				ret = btrfs_add_free_space(block_group, offset,927							   bytes);928				spin_lock(&ctl->tree_lock);929			} else {930				free_bitmap(ctl, info);931				ret = 0;932			}933		}934		cond_resched_lock(&ctl->tree_lock);935	}936	return ret;937}938 939static struct lock_class_key btrfs_free_space_inode_key;940 941int load_free_space_cache(struct btrfs_block_group *block_group)942{943	struct btrfs_fs_info *fs_info = block_group->fs_info;944	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;945	struct btrfs_free_space_ctl tmp_ctl = {};946	struct inode *inode;947	struct btrfs_path *path;948	int ret = 0;949	bool matched;950	u64 used = block_group->used;951 952	/*953	 * Because we could potentially discard our loaded free space, we want954	 * to load everything into a temporary structure first, and then if it's955	 * valid copy it all into the actual free space ctl.956	 */957	btrfs_init_free_space_ctl(block_group, &tmp_ctl);958 959	/*960	 * If this block group has been marked to be cleared for one reason or961	 * another then we can't trust the on disk cache, so just return.962	 */963	spin_lock(&block_group->lock);964	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {965		spin_unlock(&block_group->lock);966		return 0;967	}968	spin_unlock(&block_group->lock);969 970	path = btrfs_alloc_path();971	if (!path)972		return 0;973	path->search_commit_root = 1;974	path->skip_locking = 1;975 976	/*977	 * We must pass a path with search_commit_root set to btrfs_iget in978	 * order to avoid a deadlock when allocating extents for the tree root.979	 *980	 * When we are COWing an extent buffer from the tree root, when looking981	 * for a free extent, at extent-tree.c:find_free_extent(), we can find982	 * block group without its free space cache loaded. When we find one983	 * we must load its space cache which requires reading its free space984	 * cache's inode item from the root tree. If this inode item is located985	 * in the same leaf that we started COWing before, then we end up in986	 * deadlock on the extent buffer (trying to read lock it when we987	 * previously write locked it).988	 *989	 * It's safe to read the inode item using the commit root because990	 * block groups, once loaded, stay in memory forever (until they are991	 * removed) as well as their space caches once loaded. New block groups992	 * once created get their ->cached field set to BTRFS_CACHE_FINISHED so993	 * we will never try to read their inode item while the fs is mounted.994	 */995	inode = lookup_free_space_inode(block_group, path);996	if (IS_ERR(inode)) {997		btrfs_free_path(path);998		return 0;999	}1000 1001	/* We may have converted the inode and made the cache invalid. */1002	spin_lock(&block_group->lock);1003	if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {1004		spin_unlock(&block_group->lock);1005		btrfs_free_path(path);1006		goto out;1007	}1008	spin_unlock(&block_group->lock);1009 1010	/*1011	 * Reinitialize the class of struct inode's mapping->invalidate_lock for1012	 * free space inodes to prevent false positives related to locks for normal1013	 * inodes.1014	 */1015	lockdep_set_class(&(&inode->i_data)->invalidate_lock,1016			  &btrfs_free_space_inode_key);1017 1018	ret = __load_free_space_cache(fs_info->tree_root, inode, &tmp_ctl,1019				      path, block_group->start);1020	btrfs_free_path(path);1021	if (ret <= 0)1022		goto out;1023 1024	matched = (tmp_ctl.free_space == (block_group->length - used -1025					  block_group->bytes_super));1026 1027	if (matched) {1028		spin_lock(&tmp_ctl.tree_lock);1029		ret = copy_free_space_cache(block_group, &tmp_ctl);1030		spin_unlock(&tmp_ctl.tree_lock);1031		/*1032		 * ret == 1 means we successfully loaded the free space cache,1033		 * so we need to re-set it here.1034		 */1035		if (ret == 0)1036			ret = 1;1037	} else {1038		/*1039		 * We need to call the _locked variant so we don't try to update1040		 * the discard counters.1041		 */1042		spin_lock(&tmp_ctl.tree_lock);1043		__btrfs_remove_free_space_cache(&tmp_ctl);1044		spin_unlock(&tmp_ctl.tree_lock);1045		btrfs_warn(fs_info,1046			   "block group %llu has wrong amount of free space",1047			   block_group->start);1048		ret = -1;1049	}1050out:1051	if (ret < 0) {1052		/* This cache is bogus, make sure it gets cleared */1053		spin_lock(&block_group->lock);1054		block_group->disk_cache_state = BTRFS_DC_CLEAR;1055		spin_unlock(&block_group->lock);1056		ret = 0;1057 1058		btrfs_warn(fs_info,1059			   "failed to load free space cache for block group %llu, rebuilding it now",1060			   block_group->start);1061	}1062 1063	spin_lock(&ctl->tree_lock);1064	btrfs_discard_update_discardable(block_group);1065	spin_unlock(&ctl->tree_lock);1066	iput(inode);1067	return ret;1068}1069 1070static noinline_for_stack1071int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl,1072			      struct btrfs_free_space_ctl *ctl,1073			      struct btrfs_block_group *block_group,1074			      int *entries, int *bitmaps,1075			      struct list_head *bitmap_list)1076{1077	int ret;1078	struct btrfs_free_cluster *cluster = NULL;1079	struct btrfs_free_cluster *cluster_locked = NULL;1080	struct rb_node *node = rb_first(&ctl->free_space_offset);1081	struct btrfs_trim_range *trim_entry;1082 1083	/* Get the cluster for this block_group if it exists */1084	if (block_group && !list_empty(&block_group->cluster_list)) {1085		cluster = list_entry(block_group->cluster_list.next,1086				     struct btrfs_free_cluster,1087				     block_group_list);1088	}1089 1090	if (!node && cluster) {1091		cluster_locked = cluster;1092		spin_lock(&cluster_locked->lock);1093		node = rb_first(&cluster->root);1094		cluster = NULL;1095	}1096 1097	/* Write out the extent entries */1098	while (node) {1099		struct btrfs_free_space *e;1100 1101		e = rb_entry(node, struct btrfs_free_space, offset_index);1102		*entries += 1;1103 1104		ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,1105				       e->bitmap);1106		if (ret)1107			goto fail;1108 1109		if (e->bitmap) {1110			list_add_tail(&e->list, bitmap_list);1111			*bitmaps += 1;1112		}1113		node = rb_next(node);1114		if (!node && cluster) {1115			node = rb_first(&cluster->root);1116			cluster_locked = cluster;1117			spin_lock(&cluster_locked->lock);1118			cluster = NULL;1119		}1120	}1121	if (cluster_locked) {1122		spin_unlock(&cluster_locked->lock);1123		cluster_locked = NULL;1124	}1125 1126	/*1127	 * Make sure we don't miss any range that was removed from our rbtree1128	 * because trimming is running. Otherwise after a umount+mount (or crash1129	 * after committing the transaction) we would leak free space and get1130	 * an inconsistent free space cache report from fsck.1131	 */1132	list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {1133		ret = io_ctl_add_entry(io_ctl, trim_entry->start,1134				       trim_entry->bytes, NULL);1135		if (ret)1136			goto fail;1137		*entries += 1;1138	}1139 1140	return 0;1141fail:1142	if (cluster_locked)1143		spin_unlock(&cluster_locked->lock);1144	return -ENOSPC;1145}1146 1147static noinline_for_stack int1148update_cache_item(struct btrfs_trans_handle *trans,1149		  struct btrfs_root *root,1150		  struct inode *inode,1151		  struct btrfs_path *path, u64 offset,1152		  int entries, int bitmaps)1153{1154	struct btrfs_key key;1155	struct btrfs_free_space_header *header;1156	struct extent_buffer *leaf;1157	int ret;1158 1159	key.objectid = BTRFS_FREE_SPACE_OBJECTID;1160	key.offset = offset;1161	key.type = 0;1162 1163	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);1164	if (ret < 0) {1165		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,1166				 EXTENT_DELALLOC, NULL);1167		goto fail;1168	}1169	leaf = path->nodes[0];1170	if (ret > 0) {1171		struct btrfs_key found_key;1172		ASSERT(path->slots[0]);1173		path->slots[0]--;1174		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);1175		if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||1176		    found_key.offset != offset) {1177			clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,1178					 inode->i_size - 1, EXTENT_DELALLOC,1179					 NULL);1180			btrfs_release_path(path);1181			goto fail;1182		}1183	}1184 1185	BTRFS_I(inode)->generation = trans->transid;1186	header = btrfs_item_ptr(leaf, path->slots[0],1187				struct btrfs_free_space_header);1188	btrfs_set_free_space_entries(leaf, header, entries);1189	btrfs_set_free_space_bitmaps(leaf, header, bitmaps);1190	btrfs_set_free_space_generation(leaf, header, trans->transid);1191	btrfs_mark_buffer_dirty(trans, leaf);1192	btrfs_release_path(path);1193 1194	return 0;1195 1196fail:1197	return -1;1198}1199 1200static noinline_for_stack int write_pinned_extent_entries(1201			    struct btrfs_trans_handle *trans,1202			    struct btrfs_block_group *block_group,1203			    struct btrfs_io_ctl *io_ctl,1204			    int *entries)1205{1206	u64 start, extent_start, extent_end, len;1207	struct extent_io_tree *unpin = NULL;1208	int ret;1209 1210	if (!block_group)1211		return 0;1212 1213	/*1214	 * We want to add any pinned extents to our free space cache1215	 * so we don't leak the space1216	 *1217	 * We shouldn't have switched the pinned extents yet so this is the1218	 * right one1219	 */1220	unpin = &trans->transaction->pinned_extents;1221 1222	start = block_group->start;1223 1224	while (start < block_group->start + block_group->length) {1225		if (!find_first_extent_bit(unpin, start,1226					   &extent_start, &extent_end,1227					   EXTENT_DIRTY, NULL))1228			return 0;1229 1230		/* This pinned extent is out of our range */1231		if (extent_start >= block_group->start + block_group->length)1232			return 0;1233 1234		extent_start = max(extent_start, start);1235		extent_end = min(block_group->start + block_group->length,1236				 extent_end + 1);1237		len = extent_end - extent_start;1238 1239		*entries += 1;1240		ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);1241		if (ret)1242			return -ENOSPC;1243 1244		start = extent_end;1245	}1246 1247	return 0;1248}1249 1250static noinline_for_stack int1251write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list)1252{1253	struct btrfs_free_space *entry, *next;1254	int ret;1255 1256	/* Write out the bitmaps */1257	list_for_each_entry_safe(entry, next, bitmap_list, list) {1258		ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);1259		if (ret)1260			return -ENOSPC;1261		list_del_init(&entry->list);1262	}1263 1264	return 0;1265}1266 1267static int flush_dirty_cache(struct inode *inode)1268{1269	int ret;1270 1271	ret = btrfs_wait_ordered_range(BTRFS_I(inode), 0, (u64)-1);1272	if (ret)1273		clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,1274				 EXTENT_DELALLOC, NULL);1275 1276	return ret;1277}1278 1279static void noinline_for_stack1280cleanup_bitmap_list(struct list_head *bitmap_list)1281{1282	struct btrfs_free_space *entry, *next;1283 1284	list_for_each_entry_safe(entry, next, bitmap_list, list)1285		list_del_init(&entry->list);1286}1287 1288static void noinline_for_stack1289cleanup_write_cache_enospc(struct inode *inode,1290			   struct btrfs_io_ctl *io_ctl,1291			   struct extent_state **cached_state)1292{1293	io_ctl_drop_pages(io_ctl);1294	unlock_extent(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,1295		      cached_state);1296}1297 1298static int __btrfs_wait_cache_io(struct btrfs_root *root,1299				 struct btrfs_trans_handle *trans,1300				 struct btrfs_block_group *block_group,1301				 struct btrfs_io_ctl *io_ctl,1302				 struct btrfs_path *path, u64 offset)1303{1304	int ret;1305	struct inode *inode = io_ctl->inode;1306 1307	if (!inode)1308		return 0;1309 1310	/* Flush the dirty pages in the cache file. */1311	ret = flush_dirty_cache(inode);1312	if (ret)1313		goto out;1314 1315	/* Update the cache item to tell everyone this cache file is valid. */1316	ret = update_cache_item(trans, root, inode, path, offset,1317				io_ctl->entries, io_ctl->bitmaps);1318out:1319	if (ret) {1320		invalidate_inode_pages2(inode->i_mapping);1321		BTRFS_I(inode)->generation = 0;1322		if (block_group)1323			btrfs_debug(root->fs_info,1324	  "failed to write free space cache for block group %llu error %d",1325				  block_group->start, ret);1326	}1327	btrfs_update_inode(trans, BTRFS_I(inode));1328 1329	if (block_group) {1330		/* the dirty list is protected by the dirty_bgs_lock */1331		spin_lock(&trans->transaction->dirty_bgs_lock);1332 1333		/* the disk_cache_state is protected by the block group lock */1334		spin_lock(&block_group->lock);1335 1336		/*1337		 * only mark this as written if we didn't get put back on1338		 * the dirty list while waiting for IO.   Otherwise our1339		 * cache state won't be right, and we won't get written again1340		 */1341		if (!ret && list_empty(&block_group->dirty_list))1342			block_group->disk_cache_state = BTRFS_DC_WRITTEN;1343		else if (ret)1344			block_group->disk_cache_state = BTRFS_DC_ERROR;1345 1346		spin_unlock(&block_group->lock);1347		spin_unlock(&trans->transaction->dirty_bgs_lock);1348		io_ctl->inode = NULL;1349		iput(inode);1350	}1351 1352	return ret;1353 1354}1355 1356int btrfs_wait_cache_io(struct btrfs_trans_handle *trans,1357			struct btrfs_block_group *block_group,1358			struct btrfs_path *path)1359{1360	return __btrfs_wait_cache_io(block_group->fs_info->tree_root, trans,1361				     block_group, &block_group->io_ctl,1362				     path, block_group->start);1363}1364 1365/*1366 * Write out cached info to an inode.1367 *1368 * @inode:       freespace inode we are writing out1369 * @ctl:         free space cache we are going to write out1370 * @block_group: block_group for this cache if it belongs to a block_group1371 * @io_ctl:      holds context for the io1372 * @trans:       the trans handle1373 *1374 * This function writes out a free space cache struct to disk for quick recovery1375 * on mount.  This will return 0 if it was successful in writing the cache out,1376 * or an errno if it was not.1377 */1378static int __btrfs_write_out_cache(struct inode *inode,1379				   struct btrfs_free_space_ctl *ctl,1380				   struct btrfs_block_group *block_group,1381				   struct btrfs_io_ctl *io_ctl,1382				   struct btrfs_trans_handle *trans)1383{1384	struct extent_state *cached_state = NULL;1385	LIST_HEAD(bitmap_list);1386	int entries = 0;1387	int bitmaps = 0;1388	int ret;1389	int must_iput = 0;1390 1391	if (!i_size_read(inode))1392		return -EIO;1393 1394	WARN_ON(io_ctl->pages);1395	ret = io_ctl_init(io_ctl, inode, 1);1396	if (ret)1397		return ret;1398 1399	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {1400		down_write(&block_group->data_rwsem);1401		spin_lock(&block_group->lock);1402		if (block_group->delalloc_bytes) {1403			block_group->disk_cache_state = BTRFS_DC_WRITTEN;1404			spin_unlock(&block_group->lock);1405			up_write(&block_group->data_rwsem);1406			BTRFS_I(inode)->generation = 0;1407			ret = 0;1408			must_iput = 1;1409			goto out;1410		}1411		spin_unlock(&block_group->lock);1412	}1413 1414	/* Lock all pages first so we can lock the extent safely. */1415	ret = io_ctl_prepare_pages(io_ctl, false);1416	if (ret)1417		goto out_unlock;1418 1419	lock_extent(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,1420		    &cached_state);1421 1422	io_ctl_set_generation(io_ctl, trans->transid);1423 1424	mutex_lock(&ctl->cache_writeout_mutex);1425	/* Write out the extent entries in the free space cache */1426	spin_lock(&ctl->tree_lock);1427	ret = write_cache_extent_entries(io_ctl, ctl,1428					 block_group, &entries, &bitmaps,1429					 &bitmap_list);1430	if (ret)1431		goto out_nospc_locked;1432 1433	/*1434	 * Some spaces that are freed in the current transaction are pinned,1435	 * they will be added into free space cache after the transaction is1436	 * committed, we shouldn't lose them.1437	 *1438	 * If this changes while we are working we'll get added back to1439	 * the dirty list and redo it.  No locking needed1440	 */1441	ret = write_pinned_extent_entries(trans, block_group, io_ctl, &entries);1442	if (ret)1443		goto out_nospc_locked;1444 1445	/*1446	 * At last, we write out all the bitmaps and keep cache_writeout_mutex1447	 * locked while doing it because a concurrent trim can be manipulating1448	 * or freeing the bitmap.1449	 */1450	ret = write_bitmap_entries(io_ctl, &bitmap_list);1451	spin_unlock(&ctl->tree_lock);1452	mutex_unlock(&ctl->cache_writeout_mutex);1453	if (ret)1454		goto out_nospc;1455 1456	/* Zero out the rest of the pages just to make sure */1457	io_ctl_zero_remaining_pages(io_ctl);1458 1459	/* Everything is written out, now we dirty the pages in the file. */1460	ret = btrfs_dirty_pages(BTRFS_I(inode), io_ctl->pages,1461				io_ctl->num_pages, 0, i_size_read(inode),1462				&cached_state, false);1463	if (ret)1464		goto out_nospc;1465 1466	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))1467		up_write(&block_group->data_rwsem);1468	/*1469	 * Release the pages and unlock the extent, we will flush1470	 * them out later1471	 */1472	io_ctl_drop_pages(io_ctl);1473	io_ctl_free(io_ctl);1474 1475	unlock_extent(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,1476		      &cached_state);1477 1478	/*1479	 * at this point the pages are under IO and we're happy,1480	 * The caller is responsible for waiting on them and updating1481	 * the cache and the inode1482	 */1483	io_ctl->entries = entries;1484	io_ctl->bitmaps = bitmaps;1485 1486	ret = btrfs_fdatawrite_range(BTRFS_I(inode), 0, (u64)-1);1487	if (ret)1488		goto out;1489 1490	return 0;1491 1492out_nospc_locked:1493	cleanup_bitmap_list(&bitmap_list);1494	spin_unlock(&ctl->tree_lock);1495	mutex_unlock(&ctl->cache_writeout_mutex);1496 1497out_nospc:1498	cleanup_write_cache_enospc(inode, io_ctl, &cached_state);1499 1500out_unlock:1501	if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))1502		up_write(&block_group->data_rwsem);1503 1504out:1505	io_ctl->inode = NULL;1506	io_ctl_free(io_ctl);1507	if (ret) {1508		invalidate_inode_pages2(inode->i_mapping);1509		BTRFS_I(inode)->generation = 0;1510	}1511	btrfs_update_inode(trans, BTRFS_I(inode));1512	if (must_iput)1513		iput(inode);1514	return ret;1515}1516 1517int btrfs_write_out_cache(struct btrfs_trans_handle *trans,1518			  struct btrfs_block_group *block_group,1519			  struct btrfs_path *path)1520{1521	struct btrfs_fs_info *fs_info = trans->fs_info;1522	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;1523	struct inode *inode;1524	int ret = 0;1525 1526	spin_lock(&block_group->lock);1527	if (block_group->disk_cache_state < BTRFS_DC_SETUP) {1528		spin_unlock(&block_group->lock);1529		return 0;1530	}1531	spin_unlock(&block_group->lock);1532 1533	inode = lookup_free_space_inode(block_group, path);1534	if (IS_ERR(inode))1535		return 0;1536 1537	ret = __btrfs_write_out_cache(inode, ctl, block_group,1538				      &block_group->io_ctl, trans);1539	if (ret) {1540		btrfs_debug(fs_info,1541	  "failed to write free space cache for block group %llu error %d",1542			  block_group->start, ret);1543		spin_lock(&block_group->lock);1544		block_group->disk_cache_state = BTRFS_DC_ERROR;1545		spin_unlock(&block_group->lock);1546 1547		block_group->io_ctl.inode = NULL;1548		iput(inode);1549	}1550 1551	/*1552	 * if ret == 0 the caller is expected to call btrfs_wait_cache_io1553	 * to wait for IO and put the inode1554	 */1555 1556	return ret;1557}1558 1559static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,1560					  u64 offset)1561{1562	ASSERT(offset >= bitmap_start);1563	offset -= bitmap_start;1564	return (unsigned long)(div_u64(offset, unit));1565}1566 1567static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)1568{1569	return (unsigned long)(div_u64(bytes, unit));1570}1571 1572static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,1573				   u64 offset)1574{1575	u64 bitmap_start;1576	u64 bytes_per_bitmap;1577 1578	bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;1579	bitmap_start = offset - ctl->start;1580	bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);1581	bitmap_start *= bytes_per_bitmap;1582	bitmap_start += ctl->start;1583 1584	return bitmap_start;1585}1586 1587static int tree_insert_offset(struct btrfs_free_space_ctl *ctl,1588			      struct btrfs_free_cluster *cluster,1589			      struct btrfs_free_space *new_entry)1590{1591	struct rb_root *root;1592	struct rb_node **p;1593	struct rb_node *parent = NULL;1594 1595	lockdep_assert_held(&ctl->tree_lock);1596 1597	if (cluster) {1598		lockdep_assert_held(&cluster->lock);1599		root = &cluster->root;1600	} else {1601		root = &ctl->free_space_offset;1602	}1603 1604	p = &root->rb_node;1605 1606	while (*p) {1607		struct btrfs_free_space *info;1608 1609		parent = *p;1610		info = rb_entry(parent, struct btrfs_free_space, offset_index);1611 1612		if (new_entry->offset < info->offset) {1613			p = &(*p)->rb_left;1614		} else if (new_entry->offset > info->offset) {1615			p = &(*p)->rb_right;1616		} else {1617			/*1618			 * we could have a bitmap entry and an extent entry1619			 * share the same offset.  If this is the case, we want1620			 * the extent entry to always be found first if we do a1621			 * linear search through the tree, since we want to have1622			 * the quickest allocation time, and allocating from an1623			 * extent is faster than allocating from a bitmap.  So1624			 * if we're inserting a bitmap and we find an entry at1625			 * this offset, we want to go right, or after this entry1626			 * logically.  If we are inserting an extent and we've1627			 * found a bitmap, we want to go left, or before1628			 * logically.1629			 */1630			if (new_entry->bitmap) {1631				if (info->bitmap) {1632					WARN_ON_ONCE(1);1633					return -EEXIST;1634				}1635				p = &(*p)->rb_right;1636			} else {1637				if (!info->bitmap) {1638					WARN_ON_ONCE(1);1639					return -EEXIST;1640				}1641				p = &(*p)->rb_left;1642			}1643		}1644	}1645 1646	rb_link_node(&new_entry->offset_index, parent, p);1647	rb_insert_color(&new_entry->offset_index, root);1648 1649	return 0;1650}1651 1652/*1653 * This is a little subtle.  We *only* have ->max_extent_size set if we actually1654 * searched through the bitmap and figured out the largest ->max_extent_size,1655 * otherwise it's 0.  In the case that it's 0 we don't want to tell the1656 * allocator the wrong thing, we want to use the actual real max_extent_size1657 * we've found already if it's larger, or we want to use ->bytes.1658 *1659 * This matters because find_free_space() will skip entries who's ->bytes is1660 * less than the required bytes.  So if we didn't search down this bitmap, we1661 * may pick some previous entry that has a smaller ->max_extent_size than we1662 * have.  For example, assume we have two entries, one that has1663 * ->max_extent_size set to 4K and ->bytes set to 1M.  A second entry hasn't set1664 * ->max_extent_size yet, has ->bytes set to 8K and it's contiguous.  We will1665 *  call into find_free_space(), and return with max_extent_size == 4K, because1666 *  that first bitmap entry had ->max_extent_size set, but the second one did1667 *  not.  If instead we returned 8K we'd come in searching for 8K, and find the1668 *  8K contiguous range.1669 *1670 *  Consider the other case, we have 2 8K chunks in that second entry and still1671 *  don't have ->max_extent_size set.  We'll return 16K, and the next time the1672 *  allocator comes in it'll fully search our second bitmap, and this time it'll1673 *  get an uptodate value of 8K as the maximum chunk size.  Then we'll get the1674 *  right allocation the next loop through.1675 */1676static inline u64 get_max_extent_size(const struct btrfs_free_space *entry)1677{1678	if (entry->bitmap && entry->max_extent_size)1679		return entry->max_extent_size;1680	return entry->bytes;1681}1682 1683/*1684 * We want the largest entry to be leftmost, so this is inverted from what you'd1685 * normally expect.1686 */1687static bool entry_less(struct rb_node *node, const struct rb_node *parent)1688{1689	const struct btrfs_free_space *entry, *exist;1690 1691	entry = rb_entry(node, struct btrfs_free_space, bytes_index);1692	exist = rb_entry(parent, struct btrfs_free_space, bytes_index);1693	return get_max_extent_size(exist) < get_max_extent_size(entry);1694}1695 1696/*1697 * searches the tree for the given offset.1698 *1699 * fuzzy - If this is set, then we are trying to make an allocation, and we just1700 * want a section that has at least bytes size and comes at or after the given1701 * offset.1702 */1703static struct btrfs_free_space *1704tree_search_offset(struct btrfs_free_space_ctl *ctl,1705		   u64 offset, int bitmap_only, int fuzzy)1706{1707	struct rb_node *n = ctl->free_space_offset.rb_node;1708	struct btrfs_free_space *entry = NULL, *prev = NULL;1709 1710	lockdep_assert_held(&ctl->tree_lock);1711 1712	/* find entry that is closest to the 'offset' */1713	while (n) {1714		entry = rb_entry(n, struct btrfs_free_space, offset_index);1715		prev = entry;1716 1717		if (offset < entry->offset)1718			n = n->rb_left;1719		else if (offset > entry->offset)1720			n = n->rb_right;1721		else1722			break;1723 1724		entry = NULL;1725	}1726 1727	if (bitmap_only) {1728		if (!entry)1729			return NULL;1730		if (entry->bitmap)1731			return entry;1732 1733		/*1734		 * bitmap entry and extent entry may share same offset,1735		 * in that case, bitmap entry comes after extent entry.1736		 */1737		n = rb_next(n);1738		if (!n)1739			return NULL;1740		entry = rb_entry(n, struct btrfs_free_space, offset_index);1741		if (entry->offset != offset)1742			return NULL;1743 1744		WARN_ON(!entry->bitmap);1745		return entry;1746	} else if (entry) {1747		if (entry->bitmap) {1748			/*1749			 * if previous extent entry covers the offset,1750			 * we should return it instead of the bitmap entry1751			 */1752			n = rb_prev(&entry->offset_index);1753			if (n) {1754				prev = rb_entry(n, struct btrfs_free_space,1755						offset_index);1756				if (!prev->bitmap &&1757				    prev->offset + prev->bytes > offset)1758					entry = prev;1759			}1760		}1761		return entry;1762	}1763 1764	if (!prev)1765		return NULL;1766 1767	/* find last entry before the 'offset' */1768	entry = prev;1769	if (entry->offset > offset) {1770		n = rb_prev(&entry->offset_index);1771		if (n) {1772			entry = rb_entry(n, struct btrfs_free_space,1773					offset_index);1774			ASSERT(entry->offset <= offset);1775		} else {1776			if (fuzzy)1777				return entry;1778			else1779				return NULL;1780		}1781	}1782 1783	if (entry->bitmap) {1784		n = rb_prev(&entry->offset_index);1785		if (n) {1786			prev = rb_entry(n, struct btrfs_free_space,1787					offset_index);1788			if (!prev->bitmap &&1789			    prev->offset + prev->bytes > offset)1790				return prev;1791		}1792		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)1793			return entry;1794	} else if (entry->offset + entry->bytes > offset)1795		return entry;1796 1797	if (!fuzzy)1798		return NULL;1799 1800	while (1) {1801		n = rb_next(&entry->offset_index);1802		if (!n)1803			return NULL;1804		entry = rb_entry(n, struct btrfs_free_space, offset_index);1805		if (entry->bitmap) {1806			if (entry->offset + BITS_PER_BITMAP *1807			    ctl->unit > offset)1808				break;1809		} else {1810			if (entry->offset + entry->bytes > offset)1811				break;1812		}1813	}1814	return entry;1815}1816 1817static inline void unlink_free_space(struct btrfs_free_space_ctl *ctl,1818				     struct btrfs_free_space *info,1819				     bool update_stat)1820{1821	lockdep_assert_held(&ctl->tree_lock);1822 1823	rb_erase(&info->offset_index, &ctl->free_space_offset);1824	rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);1825	ctl->free_extents--;1826 1827	if (!info->bitmap && !btrfs_free_space_trimmed(info)) {1828		ctl->discardable_extents[BTRFS_STAT_CURR]--;1829		ctl->discardable_bytes[BTRFS_STAT_CURR] -= info->bytes;1830	}1831 1832	if (update_stat)1833		ctl->free_space -= info->bytes;1834}1835 1836static int link_free_space(struct btrfs_free_space_ctl *ctl,1837			   struct btrfs_free_space *info)1838{1839	int ret = 0;1840 1841	lockdep_assert_held(&ctl->tree_lock);1842 1843	ASSERT(info->bytes || info->bitmap);1844	ret = tree_insert_offset(ctl, NULL, info);1845	if (ret)1846		return ret;1847 1848	rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);1849 1850	if (!info->bitmap && !btrfs_free_space_trimmed(info)) {1851		ctl->discardable_extents[BTRFS_STAT_CURR]++;1852		ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;1853	}1854 1855	ctl->free_space += info->bytes;1856	ctl->free_extents++;1857	return ret;1858}1859 1860static void relink_bitmap_entry(struct btrfs_free_space_ctl *ctl,1861				struct btrfs_free_space *info)1862{1863	ASSERT(info->bitmap);1864 1865	/*1866	 * If our entry is empty it's because we're on a cluster and we don't1867	 * want to re-link it into our ctl bytes index.1868	 */1869	if (RB_EMPTY_NODE(&info->bytes_index))1870		return;1871 1872	lockdep_assert_held(&ctl->tree_lock);1873 1874	rb_erase_cached(&info->bytes_index, &ctl->free_space_bytes);1875	rb_add_cached(&info->bytes_index, &ctl->free_space_bytes, entry_less);1876}1877 1878static inline void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,1879				     struct btrfs_free_space *info,1880				     u64 offset, u64 bytes, bool update_stat)1881{1882	unsigned long start, count, end;1883	int extent_delta = -1;1884 1885	start = offset_to_bit(info->offset, ctl->unit, offset);1886	count = bytes_to_bits(bytes, ctl->unit);1887	end = start + count;1888	ASSERT(end <= BITS_PER_BITMAP);1889 1890	bitmap_clear(info->bitmap, start, count);1891 1892	info->bytes -= bytes;1893	if (info->max_extent_size > ctl->unit)1894		info->max_extent_size = 0;1895 1896	relink_bitmap_entry(ctl, info);1897 1898	if (start && test_bit(start - 1, info->bitmap))1899		extent_delta++;1900 1901	if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))1902		extent_delta++;1903 1904	info->bitmap_extents += extent_delta;1905	if (!btrfs_free_space_trimmed(info)) {1906		ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;1907		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;1908	}1909 1910	if (update_stat)1911		ctl->free_space -= bytes;1912}1913 1914static void btrfs_bitmap_set_bits(struct btrfs_free_space_ctl *ctl,1915				  struct btrfs_free_space *info, u64 offset,1916				  u64 bytes)1917{1918	unsigned long start, count, end;1919	int extent_delta = 1;1920 1921	start = offset_to_bit(info->offset, ctl->unit, offset);1922	count = bytes_to_bits(bytes, ctl->unit);1923	end = start + count;1924	ASSERT(end <= BITS_PER_BITMAP);1925 1926	bitmap_set(info->bitmap, start, count);1927 1928	/*1929	 * We set some bytes, we have no idea what the max extent size is1930	 * anymore.1931	 */1932	info->max_extent_size = 0;1933	info->bytes += bytes;1934	ctl->free_space += bytes;1935 1936	relink_bitmap_entry(ctl, info);1937 1938	if (start && test_bit(start - 1, info->bitmap))1939		extent_delta--;1940 1941	if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))1942		extent_delta--;1943 1944	info->bitmap_extents += extent_delta;1945	if (!btrfs_free_space_trimmed(info)) {1946		ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;1947		ctl->discardable_bytes[BTRFS_STAT_CURR] += bytes;1948	}1949}1950 1951/*1952 * If we can not find suitable extent, we will use bytes to record1953 * the size of the max extent.1954 */1955static int search_bitmap(struct btrfs_free_space_ctl *ctl,1956			 struct btrfs_free_space *bitmap_info, u64 *offset,1957			 u64 *bytes, bool for_alloc)1958{1959	unsigned long found_bits = 0;1960	unsigned long max_bits = 0;1961	unsigned long bits, i;1962	unsigned long next_zero;1963	unsigned long extent_bits;1964 1965	/*1966	 * Skip searching the bitmap if we don't have a contiguous section that1967	 * is large enough for this allocation.1968	 */1969	if (for_alloc &&1970	    bitmap_info->max_extent_size &&1971	    bitmap_info->max_extent_size < *bytes) {1972		*bytes = bitmap_info->max_extent_size;1973		return -1;1974	}1975 1976	i = offset_to_bit(bitmap_info->offset, ctl->unit,1977			  max_t(u64, *offset, bitmap_info->offset));1978	bits = bytes_to_bits(*bytes, ctl->unit);1979 1980	for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {1981		if (for_alloc && bits == 1) {1982			found_bits = 1;1983			break;1984		}1985		next_zero = find_next_zero_bit(bitmap_info->bitmap,1986					       BITS_PER_BITMAP, i);1987		extent_bits = next_zero - i;1988		if (extent_bits >= bits) {1989			found_bits = extent_bits;1990			break;1991		} else if (extent_bits > max_bits) {1992			max_bits = extent_bits;1993		}1994		i = next_zero;1995	}1996 1997	if (found_bits) {1998		*offset = (u64)(i * ctl->unit) + bitmap_info->offset;1999		*bytes = (u64)(found_bits) * ctl->unit;2000		return 0;2001	}2002 2003	*bytes = (u64)(max_bits) * ctl->unit;2004	bitmap_info->max_extent_size = *bytes;2005	relink_bitmap_entry(ctl, bitmap_info);2006	return -1;2007}2008 2009/* Cache the size of the max extent in bytes */2010static struct btrfs_free_space *2011find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,2012		unsigned long align, u64 *max_extent_size, bool use_bytes_index)2013{2014	struct btrfs_free_space *entry;2015	struct rb_node *node;2016	u64 tmp;2017	u64 align_off;2018	int ret;2019 2020	if (!ctl->free_space_offset.rb_node)2021		goto out;2022again:2023	if (use_bytes_index) {2024		node = rb_first_cached(&ctl->free_space_bytes);2025	} else {2026		entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset),2027					   0, 1);2028		if (!entry)2029			goto out;2030		node = &entry->offset_index;2031	}2032 2033	for (; node; node = rb_next(node)) {2034		if (use_bytes_index)2035			entry = rb_entry(node, struct btrfs_free_space,2036					 bytes_index);2037		else2038			entry = rb_entry(node, struct btrfs_free_space,2039					 offset_index);2040 2041		/*2042		 * If we are using the bytes index then all subsequent entries2043		 * in this tree are going to be < bytes, so simply set the max2044		 * extent size and exit the loop.2045		 *2046		 * If we're using the offset index then we need to keep going2047		 * through the rest of the tree.2048		 */2049		if (entry->bytes < *bytes) {2050			*max_extent_size = max(get_max_extent_size(entry),2051					       *max_extent_size);2052			if (use_bytes_index)2053				break;2054			continue;2055		}2056 2057		/* make sure the space returned is big enough2058		 * to match our requested alignment2059		 */2060		if (*bytes >= align) {2061			tmp = entry->offset - ctl->start + align - 1;2062			tmp = div64_u64(tmp, align);2063			tmp = tmp * align + ctl->start;2064			align_off = tmp - entry->offset;2065		} else {2066			align_off = 0;2067			tmp = entry->offset;2068		}2069 2070		/*2071		 * We don't break here if we're using the bytes index because we2072		 * may have another entry that has the correct alignment that is2073		 * the right size, so we don't want to miss that possibility.2074		 * At worst this adds another loop through the logic, but if we2075		 * broke here we could prematurely ENOSPC.2076		 */2077		if (entry->bytes < *bytes + align_off) {2078			*max_extent_size = max(get_max_extent_size(entry),2079					       *max_extent_size);2080			continue;2081		}2082 2083		if (entry->bitmap) {2084			struct rb_node *old_next = rb_next(node);2085			u64 size = *bytes;2086 2087			ret = search_bitmap(ctl, entry, &tmp, &size, true);2088			if (!ret) {2089				*offset = tmp;2090				*bytes = size;2091				return entry;2092			} else {2093				*max_extent_size =2094					max(get_max_extent_size(entry),2095					    *max_extent_size);2096			}2097 2098			/*2099			 * The bitmap may have gotten re-arranged in the space2100			 * index here because the max_extent_size may have been2101			 * updated.  Start from the beginning again if this2102			 * happened.2103			 */2104			if (use_bytes_index && old_next != rb_next(node))2105				goto again;2106			continue;2107		}2108 2109		*offset = tmp;2110		*bytes = entry->bytes - align_off;2111		return entry;2112	}2113out:2114	return NULL;2115}2116 2117static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,2118			   struct btrfs_free_space *info, u64 offset)2119{2120	info->offset = offset_to_bitmap(ctl, offset);2121	info->bytes = 0;2122	info->bitmap_extents = 0;2123	INIT_LIST_HEAD(&info->list);2124	link_free_space(ctl, info);2125	ctl->total_bitmaps++;2126	recalculate_thresholds(ctl);2127}2128 2129static void free_bitmap(struct btrfs_free_space_ctl *ctl,2130			struct btrfs_free_space *bitmap_info)2131{2132	/*2133	 * Normally when this is called, the bitmap is completely empty. However,2134	 * if we are blowing up the free space cache for one reason or another2135	 * via __btrfs_remove_free_space_cache(), then it may not be freed and2136	 * we may leave stats on the table.2137	 */2138	if (bitmap_info->bytes && !btrfs_free_space_trimmed(bitmap_info)) {2139		ctl->discardable_extents[BTRFS_STAT_CURR] -=2140			bitmap_info->bitmap_extents;2141		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bitmap_info->bytes;2142 2143	}2144	unlink_free_space(ctl, bitmap_info, true);2145	kmem_cache_free(btrfs_free_space_bitmap_cachep, bitmap_info->bitmap);2146	kmem_cache_free(btrfs_free_space_cachep, bitmap_info);2147	ctl->total_bitmaps--;2148	recalculate_thresholds(ctl);2149}2150 2151static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,2152			      struct btrfs_free_space *bitmap_info,2153			      u64 *offset, u64 *bytes)2154{2155	u64 end;2156	u64 search_start, search_bytes;2157	int ret;2158 2159again:2160	end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;2161 2162	/*2163	 * We need to search for bits in this bitmap.  We could only cover some2164	 * of the extent in this bitmap thanks to how we add space, so we need2165	 * to search for as much as it as we can and clear that amount, and then2166	 * go searching for the next bit.2167	 */2168	search_start = *offset;2169	search_bytes = ctl->unit;2170	search_bytes = min(search_bytes, end - search_start + 1);2171	ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,2172			    false);2173	if (ret < 0 || search_start != *offset)2174		return -EINVAL;2175 2176	/* We may have found more bits than what we need */2177	search_bytes = min(search_bytes, *bytes);2178 2179	/* Cannot clear past the end of the bitmap */2180	search_bytes = min(search_bytes, end - search_start + 1);2181 2182	bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes, true);2183	*offset += search_bytes;2184	*bytes -= search_bytes;2185 2186	if (*bytes) {2187		struct rb_node *next = rb_next(&bitmap_info->offset_index);2188		if (!bitmap_info->bytes)2189			free_bitmap(ctl, bitmap_info);2190 2191		/*2192		 * no entry after this bitmap, but we still have bytes to2193		 * remove, so something has gone wrong.2194		 */2195		if (!next)2196			return -EINVAL;2197 2198		bitmap_info = rb_entry(next, struct btrfs_free_space,2199				       offset_index);2200 2201		/*2202		 * if the next entry isn't a bitmap we need to return to let the2203		 * extent stuff do its work.2204		 */2205		if (!bitmap_info->bitmap)2206			return -EAGAIN;2207 2208		/*2209		 * Ok the next item is a bitmap, but it may not actually hold2210		 * the information for the rest of this free space stuff, so2211		 * look for it, and if we don't find it return so we can try2212		 * everything over again.2213		 */2214		search_start = *offset;2215		search_bytes = ctl->unit;2216		ret = search_bitmap(ctl, bitmap_info, &search_start,2217				    &search_bytes, false);2218		if (ret < 0 || search_start != *offset)2219			return -EAGAIN;2220 2221		goto again;2222	} else if (!bitmap_info->bytes)2223		free_bitmap(ctl, bitmap_info);2224 2225	return 0;2226}2227 2228static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,2229			       struct btrfs_free_space *info, u64 offset,2230			       u64 bytes, enum btrfs_trim_state trim_state)2231{2232	u64 bytes_to_set = 0;2233	u64 end;2234 2235	/*2236	 * This is a tradeoff to make bitmap trim state minimal.  We mark the2237	 * whole bitmap untrimmed if at any point we add untrimmed regions.2238	 */2239	if (trim_state == BTRFS_TRIM_STATE_UNTRIMMED) {2240		if (btrfs_free_space_trimmed(info)) {2241			ctl->discardable_extents[BTRFS_STAT_CURR] +=2242				info->bitmap_extents;2243			ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;2244		}2245		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;2246	}2247 2248	end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);2249 2250	bytes_to_set = min(end - offset, bytes);2251 2252	btrfs_bitmap_set_bits(ctl, info, offset, bytes_to_set);2253 2254	return bytes_to_set;2255 2256}2257 2258static bool use_bitmap(struct btrfs_free_space_ctl *ctl,2259		      struct btrfs_free_space *info)2260{2261	struct btrfs_block_group *block_group = ctl->block_group;2262	struct btrfs_fs_info *fs_info = block_group->fs_info;2263	bool forced = false;2264 2265#ifdef CONFIG_BTRFS_DEBUG2266	if (btrfs_should_fragment_free_space(block_group))2267		forced = true;2268#endif2269 2270	/* This is a way to reclaim large regions from the bitmaps. */2271	if (!forced && info->bytes >= FORCE_EXTENT_THRESHOLD)2272		return false;2273 2274	/*2275	 * If we are below the extents threshold then we can add this as an2276	 * extent, and don't have to deal with the bitmap2277	 */2278	if (!forced && ctl->free_extents < ctl->extents_thresh) {2279		/*2280		 * If this block group has some small extents we don't want to2281		 * use up all of our free slots in the cache with them, we want2282		 * to reserve them to larger extents, however if we have plenty2283		 * of cache left then go ahead an dadd them, no sense in adding2284		 * the overhead of a bitmap if we don't have to.2285		 */2286		if (info->bytes <= fs_info->sectorsize * 8) {2287			if (ctl->free_extents * 3 <= ctl->extents_thresh)2288				return false;2289		} else {2290			return false;2291		}2292	}2293 2294	/*2295	 * The original block groups from mkfs can be really small, like 82296	 * megabytes, so don't bother with a bitmap for those entries.  However2297	 * some block groups can be smaller than what a bitmap would cover but2298	 * are still large enough that they could overflow the 32k memory limit,2299	 * so allow those block groups to still be allowed to have a bitmap2300	 * entry.2301	 */2302	if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->length)2303		return false;2304 2305	return true;2306}2307 2308static const struct btrfs_free_space_op free_space_op = {2309	.use_bitmap		= use_bitmap,2310};2311 2312static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,2313			      struct btrfs_free_space *info)2314{2315	struct btrfs_free_space *bitmap_info;2316	struct btrfs_block_group *block_group = NULL;2317	int added = 0;2318	u64 bytes, offset, bytes_added;2319	enum btrfs_trim_state trim_state;2320	int ret;2321 2322	bytes = info->bytes;2323	offset = info->offset;2324	trim_state = info->trim_state;2325 2326	if (!ctl->op->use_bitmap(ctl, info))2327		return 0;2328 2329	if (ctl->op == &free_space_op)2330		block_group = ctl->block_group;2331again:2332	/*2333	 * Since we link bitmaps right into the cluster we need to see if we2334	 * have a cluster here, and if so and it has our bitmap we need to add2335	 * the free space to that bitmap.2336	 */2337	if (block_group && !list_empty(&block_group->cluster_list)) {2338		struct btrfs_free_cluster *cluster;2339		struct rb_node *node;2340		struct btrfs_free_space *entry;2341 2342		cluster = list_entry(block_group->cluster_list.next,2343				     struct btrfs_free_cluster,2344				     block_group_list);2345		spin_lock(&cluster->lock);2346		node = rb_first(&cluster->root);2347		if (!node) {2348			spin_unlock(&cluster->lock);2349			goto no_cluster_bitmap;2350		}2351 2352		entry = rb_entry(node, struct btrfs_free_space, offset_index);2353		if (!entry->bitmap) {2354			spin_unlock(&cluster->lock);2355			goto no_cluster_bitmap;2356		}2357 2358		if (entry->offset == offset_to_bitmap(ctl, offset)) {2359			bytes_added = add_bytes_to_bitmap(ctl, entry, offset,2360							  bytes, trim_state);2361			bytes -= bytes_added;2362			offset += bytes_added;2363		}2364		spin_unlock(&cluster->lock);2365		if (!bytes) {2366			ret = 1;2367			goto out;2368		}2369	}2370 2371no_cluster_bitmap:2372	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),2373					 1, 0);2374	if (!bitmap_info) {2375		ASSERT(added == 0);2376		goto new_bitmap;2377	}2378 2379	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,2380					  trim_state);2381	bytes -= bytes_added;2382	offset += bytes_added;2383	added = 0;2384 2385	if (!bytes) {2386		ret = 1;2387		goto out;2388	} else2389		goto again;2390 2391new_bitmap:2392	if (info && info->bitmap) {2393		add_new_bitmap(ctl, info, offset);2394		added = 1;2395		info = NULL;2396		goto again;2397	} else {2398		spin_unlock(&ctl->tree_lock);2399 2400		/* no pre-allocated info, allocate a new one */2401		if (!info) {2402			info = kmem_cache_zalloc(btrfs_free_space_cachep,2403						 GFP_NOFS);2404			if (!info) {2405				spin_lock(&ctl->tree_lock);2406				ret = -ENOMEM;2407				goto out;2408			}2409		}2410 2411		/* allocate the bitmap */2412		info->bitmap = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep,2413						 GFP_NOFS);2414		info->trim_state = BTRFS_TRIM_STATE_TRIMMED;2415		spin_lock(&ctl->tree_lock);2416		if (!info->bitmap) {2417			ret = -ENOMEM;2418			goto out;2419		}2420		goto again;2421	}2422 2423out:2424	if (info) {2425		if (info->bitmap)2426			kmem_cache_free(btrfs_free_space_bitmap_cachep,2427					info->bitmap);2428		kmem_cache_free(btrfs_free_space_cachep, info);2429	}2430 2431	return ret;2432}2433 2434/*2435 * Free space merging rules:2436 *  1) Merge trimmed areas together2437 *  2) Let untrimmed areas coalesce with trimmed areas2438 *  3) Always pull neighboring regions from bitmaps2439 *2440 * The above rules are for when we merge free space based on btrfs_trim_state.2441 * Rules 2 and 3 are subtle because they are suboptimal, but are done for the2442 * same reason: to promote larger extent regions which makes life easier for2443 * find_free_extent().  Rule 2 enables coalescing based on the common path2444 * being returning free space from btrfs_finish_extent_commit().  So when free2445 * space is trimmed, it will prevent aggregating trimmed new region and2446 * untrimmed regions in the rb_tree.  Rule 3 is purely to obtain larger extents2447 * and provide find_free_extent() with the largest extents possible hoping for2448 * the reuse path.2449 */2450static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,2451			  struct btrfs_free_space *info, bool update_stat)2452{2453	struct btrfs_free_space *left_info = NULL;2454	struct btrfs_free_space *right_info;2455	bool merged = false;2456	u64 offset = info->offset;2457	u64 bytes = info->bytes;2458	const bool is_trimmed = btrfs_free_space_trimmed(info);2459	struct rb_node *right_prev = NULL;2460 2461	/*2462	 * first we want to see if there is free space adjacent to the range we2463	 * are adding, if there is remove that struct and add a new one to2464	 * cover the entire range2465	 */2466	right_info = tree_search_offset(ctl, offset + bytes, 0, 0);2467	if (right_info)2468		right_prev = rb_prev(&right_info->offset_index);2469 2470	if (right_prev)2471		left_info = rb_entry(right_prev, struct btrfs_free_space, offset_index);2472	else if (!right_info)2473		left_info = tree_search_offset(ctl, offset - 1, 0, 0);2474 2475	/* See try_merge_free_space() comment. */2476	if (right_info && !right_info->bitmap &&2477	    (!is_trimmed || btrfs_free_space_trimmed(right_info))) {2478		unlink_free_space(ctl, right_info, update_stat);2479		info->bytes += right_info->bytes;2480		kmem_cache_free(btrfs_free_space_cachep, right_info);2481		merged = true;2482	}2483 2484	/* See try_merge_free_space() comment. */2485	if (left_info && !left_info->bitmap &&2486	    left_info->offset + left_info->bytes == offset &&2487	    (!is_trimmed || btrfs_free_space_trimmed(left_info))) {2488		unlink_free_space(ctl, left_info, update_stat);2489		info->offset = left_info->offset;2490		info->bytes += left_info->bytes;2491		kmem_cache_free(btrfs_free_space_cachep, left_info);2492		merged = true;2493	}2494 2495	return merged;2496}2497 2498static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,2499				     struct btrfs_free_space *info,2500				     bool update_stat)2501{2502	struct btrfs_free_space *bitmap;2503	unsigned long i;2504	unsigned long j;2505	const u64 end = info->offset + info->bytes;2506	const u64 bitmap_offset = offset_to_bitmap(ctl, end);2507	u64 bytes;2508 2509	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);2510	if (!bitmap)2511		return false;2512 2513	i = offset_to_bit(bitmap->offset, ctl->unit, end);2514	j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);2515	if (j == i)2516		return false;2517	bytes = (j - i) * ctl->unit;2518	info->bytes += bytes;2519 2520	/* See try_merge_free_space() comment. */2521	if (!btrfs_free_space_trimmed(bitmap))2522		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;2523 2524	bitmap_clear_bits(ctl, bitmap, end, bytes, update_stat);2525 2526	if (!bitmap->bytes)2527		free_bitmap(ctl, bitmap);2528 2529	return true;2530}2531 2532static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,2533				       struct btrfs_free_space *info,2534				       bool update_stat)2535{2536	struct btrfs_free_space *bitmap;2537	u64 bitmap_offset;2538	unsigned long i;2539	unsigned long j;2540	unsigned long prev_j;2541	u64 bytes;2542 2543	bitmap_offset = offset_to_bitmap(ctl, info->offset);2544	/* If we're on a boundary, try the previous logical bitmap. */2545	if (bitmap_offset == info->offset) {2546		if (info->offset == 0)2547			return false;2548		bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);2549	}2550 2551	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);2552	if (!bitmap)2553		return false;2554 2555	i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;2556	j = 0;2557	prev_j = (unsigned long)-1;2558	for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {2559		if (j > i)2560			break;2561		prev_j = j;2562	}2563	if (prev_j == i)2564		return false;2565 2566	if (prev_j == (unsigned long)-1)2567		bytes = (i + 1) * ctl->unit;2568	else2569		bytes = (i - prev_j) * ctl->unit;2570 2571	info->offset -= bytes;2572	info->bytes += bytes;2573 2574	/* See try_merge_free_space() comment. */2575	if (!btrfs_free_space_trimmed(bitmap))2576		info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;2577 2578	bitmap_clear_bits(ctl, bitmap, info->offset, bytes, update_stat);2579 2580	if (!bitmap->bytes)2581		free_bitmap(ctl, bitmap);2582 2583	return true;2584}2585 2586/*2587 * We prefer always to allocate from extent entries, both for clustered and2588 * non-clustered allocation requests. So when attempting to add a new extent2589 * entry, try to see if there's adjacent free space in bitmap entries, and if2590 * there is, migrate that space from the bitmaps to the extent.2591 * Like this we get better chances of satisfying space allocation requests2592 * because we attempt to satisfy them based on a single cache entry, and never2593 * on 2 or more entries - even if the entries represent a contiguous free space2594 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry2595 * ends).2596 */2597static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,2598			      struct btrfs_free_space *info,2599			      bool update_stat)2600{2601	/*2602	 * Only work with disconnected entries, as we can change their offset,2603	 * and must be extent entries.2604	 */2605	ASSERT(!info->bitmap);2606	ASSERT(RB_EMPTY_NODE(&info->offset_index));2607 2608	if (ctl->total_bitmaps > 0) {2609		bool stole_end;2610		bool stole_front = false;2611 2612		stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);2613		if (ctl->total_bitmaps > 0)2614			stole_front = steal_from_bitmap_to_front(ctl, info,2615								 update_stat);2616 2617		if (stole_end || stole_front)2618			try_merge_free_space(ctl, info, update_stat);2619	}2620}2621 2622static int __btrfs_add_free_space(struct btrfs_block_group *block_group,2623			   u64 offset, u64 bytes,2624			   enum btrfs_trim_state trim_state)2625{2626	struct btrfs_fs_info *fs_info = block_group->fs_info;2627	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;2628	struct btrfs_free_space *info;2629	int ret = 0;2630	u64 filter_bytes = bytes;2631 2632	ASSERT(!btrfs_is_zoned(fs_info));2633 2634	info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);2635	if (!info)2636		return -ENOMEM;2637 2638	info->offset = offset;2639	info->bytes = bytes;2640	info->trim_state = trim_state;2641	RB_CLEAR_NODE(&info->offset_index);2642	RB_CLEAR_NODE(&info->bytes_index);2643 2644	spin_lock(&ctl->tree_lock);2645 2646	if (try_merge_free_space(ctl, info, true))2647		goto link;2648 2649	/*2650	 * There was no extent directly to the left or right of this new2651	 * extent then we know we're going to have to allocate a new extent, so2652	 * before we do that see if we need to drop this into a bitmap2653	 */2654	ret = insert_into_bitmap(ctl, info);2655	if (ret < 0) {2656		goto out;2657	} else if (ret) {2658		ret = 0;2659		goto out;2660	}2661link:2662	/*2663	 * Only steal free space from adjacent bitmaps if we're sure we're not2664	 * going to add the new free space to existing bitmap entries - because2665	 * that would mean unnecessary work that would be reverted. Therefore2666	 * attempt to steal space from bitmaps if we're adding an extent entry.2667	 */2668	steal_from_bitmap(ctl, info, true);2669 2670	filter_bytes = max(filter_bytes, info->bytes);2671 2672	ret = link_free_space(ctl, info);2673	if (ret)2674		kmem_cache_free(btrfs_free_space_cachep, info);2675out:2676	btrfs_discard_update_discardable(block_group);2677	spin_unlock(&ctl->tree_lock);2678 2679	if (ret) {2680		btrfs_crit(fs_info, "unable to add free space :%d", ret);2681		ASSERT(ret != -EEXIST);2682	}2683 2684	if (trim_state != BTRFS_TRIM_STATE_TRIMMED) {2685		btrfs_discard_check_filter(block_group, filter_bytes);2686		btrfs_discard_queue_work(&fs_info->discard_ctl, block_group);2687	}2688 2689	return ret;2690}2691 2692static int __btrfs_add_free_space_zoned(struct btrfs_block_group *block_group,2693					u64 bytenr, u64 size, bool used)2694{2695	struct btrfs_space_info *sinfo = block_group->space_info;2696	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;2697	u64 offset = bytenr - block_group->start;2698	u64 to_free, to_unusable;2699	int bg_reclaim_threshold = 0;2700	bool initial;2701	u64 reclaimable_unusable;2702 2703	spin_lock(&block_group->lock);2704 2705	initial = ((size == block_group->length) && (block_group->alloc_offset == 0));2706	WARN_ON(!initial && offset + size > block_group->zone_capacity);2707	if (!initial)2708		bg_reclaim_threshold = READ_ONCE(sinfo->bg_reclaim_threshold);2709 2710	if (!used)2711		to_free = size;2712	else if (initial)2713		to_free = block_group->zone_capacity;2714	else if (offset >= block_group->alloc_offset)2715		to_free = size;2716	else if (offset + size <= block_group->alloc_offset)2717		to_free = 0;2718	else2719		to_free = offset + size - block_group->alloc_offset;2720	to_unusable = size - to_free;2721 2722	spin_lock(&ctl->tree_lock);2723	ctl->free_space += to_free;2724	spin_unlock(&ctl->tree_lock);2725	/*2726	 * If the block group is read-only, we should account freed space into2727	 * bytes_readonly.2728	 */2729	if (!block_group->ro) {2730		block_group->zone_unusable += to_unusable;2731		WARN_ON(block_group->zone_unusable > block_group->length);2732	}2733	if (!used) {2734		block_group->alloc_offset -= size;2735	}2736 2737	reclaimable_unusable = block_group->zone_unusable -2738			       (block_group->length - block_group->zone_capacity);2739	/* All the region is now unusable. Mark it as unused and reclaim */2740	if (block_group->zone_unusable == block_group->length) {2741		btrfs_mark_bg_unused(block_group);2742	} else if (bg_reclaim_threshold &&2743		   reclaimable_unusable >=2744		   mult_perc(block_group->zone_capacity, bg_reclaim_threshold)) {2745		btrfs_mark_bg_to_reclaim(block_group);2746	}2747 2748	spin_unlock(&block_group->lock);2749 2750	return 0;2751}2752 2753int btrfs_add_free_space(struct btrfs_block_group *block_group,2754			 u64 bytenr, u64 size)2755{2756	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;2757 2758	if (btrfs_is_zoned(block_group->fs_info))2759		return __btrfs_add_free_space_zoned(block_group, bytenr, size,2760						    true);2761 2762	if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC))2763		trim_state = BTRFS_TRIM_STATE_TRIMMED;2764 2765	return __btrfs_add_free_space(block_group, bytenr, size, trim_state);2766}2767 2768int btrfs_add_free_space_unused(struct btrfs_block_group *block_group,2769				u64 bytenr, u64 size)2770{2771	if (btrfs_is_zoned(block_group->fs_info))2772		return __btrfs_add_free_space_zoned(block_group, bytenr, size,2773						    false);2774 2775	return btrfs_add_free_space(block_group, bytenr, size);2776}2777 2778/*2779 * This is a subtle distinction because when adding free space back in general,2780 * we want it to be added as untrimmed for async. But in the case where we add2781 * it on loading of a block group, we want to consider it trimmed.2782 */2783int btrfs_add_free_space_async_trimmed(struct btrfs_block_group *block_group,2784				       u64 bytenr, u64 size)2785{2786	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;2787 2788	if (btrfs_is_zoned(block_group->fs_info))2789		return __btrfs_add_free_space_zoned(block_group, bytenr, size,2790						    true);2791 2792	if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC) ||2793	    btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC))2794		trim_state = BTRFS_TRIM_STATE_TRIMMED;2795 2796	return __btrfs_add_free_space(block_group, bytenr, size, trim_state);2797}2798 2799int btrfs_remove_free_space(struct btrfs_block_group *block_group,2800			    u64 offset, u64 bytes)2801{2802	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;2803	struct btrfs_free_space *info;2804	int ret;2805	bool re_search = false;2806 2807	if (btrfs_is_zoned(block_group->fs_info)) {2808		/*2809		 * This can happen with conventional zones when replaying log.2810		 * Since the allocation info of tree-log nodes are not recorded2811		 * to the extent-tree, calculate_alloc_pointer() failed to2812		 * advance the allocation pointer after last allocated tree log2813		 * node blocks.2814		 *2815		 * This function is called from2816		 * btrfs_pin_extent_for_log_replay() when replaying the log.2817		 * Advance the pointer not to overwrite the tree-log nodes.2818		 */2819		if (block_group->start + block_group->alloc_offset <2820		    offset + bytes) {2821			block_group->alloc_offset =2822				offset + bytes - block_group->start;2823		}2824		return 0;2825	}2826 2827	spin_lock(&ctl->tree_lock);2828 2829again:2830	ret = 0;2831	if (!bytes)2832		goto out_lock;2833 2834	info = tree_search_offset(ctl, offset, 0, 0);2835	if (!info) {2836		/*2837		 * oops didn't find an extent that matched the space we wanted2838		 * to remove, look for a bitmap instead2839		 */2840		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),2841					  1, 0);2842		if (!info) {2843			/*2844			 * If we found a partial bit of our free space in a2845			 * bitmap but then couldn't find the other part this may2846			 * be a problem, so WARN about it.2847			 */2848			WARN_ON(re_search);2849			goto out_lock;2850		}2851	}2852 2853	re_search = false;2854	if (!info->bitmap) {2855		unlink_free_space(ctl, info, true);2856		if (offset == info->offset) {2857			u64 to_free = min(bytes, info->bytes);2858 2859			info->bytes -= to_free;2860			info->offset += to_free;2861			if (info->bytes) {2862				ret = link_free_space(ctl, info);2863				WARN_ON(ret);2864			} else {2865				kmem_cache_free(btrfs_free_space_cachep, info);2866			}2867 2868			offset += to_free;2869			bytes -= to_free;2870			goto again;2871		} else {2872			u64 old_end = info->bytes + info->offset;2873 2874			info->bytes = offset - info->offset;2875			ret = link_free_space(ctl, info);2876			WARN_ON(ret);2877			if (ret)2878				goto out_lock;2879 2880			/* Not enough bytes in this entry to satisfy us */2881			if (old_end < offset + bytes) {2882				bytes -= old_end - offset;2883				offset = old_end;2884				goto again;2885			} else if (old_end == offset + bytes) {2886				/* all done */2887				goto out_lock;2888			}2889			spin_unlock(&ctl->tree_lock);2890 2891			ret = __btrfs_add_free_space(block_group,2892						     offset + bytes,2893						     old_end - (offset + bytes),2894						     info->trim_state);2895			WARN_ON(ret);2896			goto out;2897		}2898	}2899 2900	ret = remove_from_bitmap(ctl, info, &offset, &bytes);2901	if (ret == -EAGAIN) {2902		re_search = true;2903		goto again;2904	}2905out_lock:2906	btrfs_discard_update_discardable(block_group);2907	spin_unlock(&ctl->tree_lock);2908out:2909	return ret;2910}2911 2912void btrfs_dump_free_space(struct btrfs_block_group *block_group,2913			   u64 bytes)2914{2915	struct btrfs_fs_info *fs_info = block_group->fs_info;2916	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;2917	struct btrfs_free_space *info;2918	struct rb_node *n;2919	int count = 0;2920 2921	/*2922	 * Zoned btrfs does not use free space tree and cluster. Just print2923	 * out the free space after the allocation offset.2924	 */2925	if (btrfs_is_zoned(fs_info)) {2926		btrfs_info(fs_info, "free space %llu active %d",2927			   block_group->zone_capacity - block_group->alloc_offset,2928			   test_bit(BLOCK_GROUP_FLAG_ZONE_IS_ACTIVE,2929				    &block_group->runtime_flags));2930		return;2931	}2932 2933	spin_lock(&ctl->tree_lock);2934	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {2935		info = rb_entry(n, struct btrfs_free_space, offset_index);2936		if (info->bytes >= bytes && !block_group->ro)2937			count++;2938		btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s",2939			   info->offset, info->bytes,2940		       (info->bitmap) ? "yes" : "no");2941	}2942	spin_unlock(&ctl->tree_lock);2943	btrfs_info(fs_info, "block group has cluster?: %s",2944	       list_empty(&block_group->cluster_list) ? "no" : "yes");2945	btrfs_info(fs_info,2946		   "%d free space entries at or bigger than %llu bytes",2947		   count, bytes);2948}2949 2950void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group,2951			       struct btrfs_free_space_ctl *ctl)2952{2953	struct btrfs_fs_info *fs_info = block_group->fs_info;2954 2955	spin_lock_init(&ctl->tree_lock);2956	ctl->unit = fs_info->sectorsize;2957	ctl->start = block_group->start;2958	ctl->block_group = block_group;2959	ctl->op = &free_space_op;2960	ctl->free_space_bytes = RB_ROOT_CACHED;2961	INIT_LIST_HEAD(&ctl->trimming_ranges);2962	mutex_init(&ctl->cache_writeout_mutex);2963 2964	/*2965	 * we only want to have 32k of ram per block group for keeping2966	 * track of free space, and if we pass 1/2 of that we want to2967	 * start converting things over to using bitmaps2968	 */2969	ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);2970}2971 2972/*2973 * for a given cluster, put all of its extents back into the free2974 * space cache.  If the block group passed doesn't match the block group2975 * pointed to by the cluster, someone else raced in and freed the2976 * cluster already.  In that case, we just return without changing anything2977 */2978static void __btrfs_return_cluster_to_free_space(2979			     struct btrfs_block_group *block_group,2980			     struct btrfs_free_cluster *cluster)2981{2982	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;2983	struct rb_node *node;2984 2985	lockdep_assert_held(&ctl->tree_lock);2986 2987	spin_lock(&cluster->lock);2988	if (cluster->block_group != block_group) {2989		spin_unlock(&cluster->lock);2990		return;2991	}2992 2993	cluster->block_group = NULL;2994	cluster->window_start = 0;2995	list_del_init(&cluster->block_group_list);2996 2997	node = rb_first(&cluster->root);2998	while (node) {2999		struct btrfs_free_space *entry;3000 3001		entry = rb_entry(node, struct btrfs_free_space, offset_index);3002		node = rb_next(&entry->offset_index);3003		rb_erase(&entry->offset_index, &cluster->root);3004		RB_CLEAR_NODE(&entry->offset_index);3005 3006		if (!entry->bitmap) {3007			/* Merging treats extents as if they were new */3008			if (!btrfs_free_space_trimmed(entry)) {3009				ctl->discardable_extents[BTRFS_STAT_CURR]--;3010				ctl->discardable_bytes[BTRFS_STAT_CURR] -=3011					entry->bytes;3012			}3013 3014			try_merge_free_space(ctl, entry, false);3015			steal_from_bitmap(ctl, entry, false);3016 3017			/* As we insert directly, update these statistics */3018			if (!btrfs_free_space_trimmed(entry)) {3019				ctl->discardable_extents[BTRFS_STAT_CURR]++;3020				ctl->discardable_bytes[BTRFS_STAT_CURR] +=3021					entry->bytes;3022			}3023		}3024		tree_insert_offset(ctl, NULL, entry);3025		rb_add_cached(&entry->bytes_index, &ctl->free_space_bytes,3026			      entry_less);3027	}3028	cluster->root = RB_ROOT;3029	spin_unlock(&cluster->lock);3030	btrfs_put_block_group(block_group);3031}3032 3033void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group)3034{3035	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3036	struct btrfs_free_cluster *cluster;3037	struct list_head *head;3038 3039	spin_lock(&ctl->tree_lock);3040	while ((head = block_group->cluster_list.next) !=3041	       &block_group->cluster_list) {3042		cluster = list_entry(head, struct btrfs_free_cluster,3043				     block_group_list);3044 3045		WARN_ON(cluster->block_group != block_group);3046		__btrfs_return_cluster_to_free_space(block_group, cluster);3047 3048		cond_resched_lock(&ctl->tree_lock);3049	}3050	__btrfs_remove_free_space_cache(ctl);3051	btrfs_discard_update_discardable(block_group);3052	spin_unlock(&ctl->tree_lock);3053 3054}3055 3056/*3057 * Walk @block_group's free space rb_tree to determine if everything is trimmed.3058 */3059bool btrfs_is_free_space_trimmed(struct btrfs_block_group *block_group)3060{3061	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3062	struct btrfs_free_space *info;3063	struct rb_node *node;3064	bool ret = true;3065 3066	spin_lock(&ctl->tree_lock);3067	node = rb_first(&ctl->free_space_offset);3068 3069	while (node) {3070		info = rb_entry(node, struct btrfs_free_space, offset_index);3071 3072		if (!btrfs_free_space_trimmed(info)) {3073			ret = false;3074			break;3075		}3076 3077		node = rb_next(node);3078	}3079 3080	spin_unlock(&ctl->tree_lock);3081	return ret;3082}3083 3084u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group,3085			       u64 offset, u64 bytes, u64 empty_size,3086			       u64 *max_extent_size)3087{3088	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3089	struct btrfs_discard_ctl *discard_ctl =3090					&block_group->fs_info->discard_ctl;3091	struct btrfs_free_space *entry = NULL;3092	u64 bytes_search = bytes + empty_size;3093	u64 ret = 0;3094	u64 align_gap = 0;3095	u64 align_gap_len = 0;3096	enum btrfs_trim_state align_gap_trim_state = BTRFS_TRIM_STATE_UNTRIMMED;3097	bool use_bytes_index = (offset == block_group->start);3098 3099	ASSERT(!btrfs_is_zoned(block_group->fs_info));3100 3101	spin_lock(&ctl->tree_lock);3102	entry = find_free_space(ctl, &offset, &bytes_search,3103				block_group->full_stripe_len, max_extent_size,3104				use_bytes_index);3105	if (!entry)3106		goto out;3107 3108	ret = offset;3109	if (entry->bitmap) {3110		bitmap_clear_bits(ctl, entry, offset, bytes, true);3111 3112		if (!btrfs_free_space_trimmed(entry))3113			atomic64_add(bytes, &discard_ctl->discard_bytes_saved);3114 3115		if (!entry->bytes)3116			free_bitmap(ctl, entry);3117	} else {3118		unlink_free_space(ctl, entry, true);3119		align_gap_len = offset - entry->offset;3120		align_gap = entry->offset;3121		align_gap_trim_state = entry->trim_state;3122 3123		if (!btrfs_free_space_trimmed(entry))3124			atomic64_add(bytes, &discard_ctl->discard_bytes_saved);3125 3126		entry->offset = offset + bytes;3127		WARN_ON(entry->bytes < bytes + align_gap_len);3128 3129		entry->bytes -= bytes + align_gap_len;3130		if (!entry->bytes)3131			kmem_cache_free(btrfs_free_space_cachep, entry);3132		else3133			link_free_space(ctl, entry);3134	}3135out:3136	btrfs_discard_update_discardable(block_group);3137	spin_unlock(&ctl->tree_lock);3138 3139	if (align_gap_len)3140		__btrfs_add_free_space(block_group, align_gap, align_gap_len,3141				       align_gap_trim_state);3142	return ret;3143}3144 3145/*3146 * given a cluster, put all of its extents back into the free space3147 * cache.  If a block group is passed, this function will only free3148 * a cluster that belongs to the passed block group.3149 *3150 * Otherwise, it'll get a reference on the block group pointed to by the3151 * cluster and remove the cluster from it.3152 */3153void btrfs_return_cluster_to_free_space(3154			       struct btrfs_block_group *block_group,3155			       struct btrfs_free_cluster *cluster)3156{3157	struct btrfs_free_space_ctl *ctl;3158 3159	/* first, get a safe pointer to the block group */3160	spin_lock(&cluster->lock);3161	if (!block_group) {3162		block_group = cluster->block_group;3163		if (!block_group) {3164			spin_unlock(&cluster->lock);3165			return;3166		}3167	} else if (cluster->block_group != block_group) {3168		/* someone else has already freed it don't redo their work */3169		spin_unlock(&cluster->lock);3170		return;3171	}3172	btrfs_get_block_group(block_group);3173	spin_unlock(&cluster->lock);3174 3175	ctl = block_group->free_space_ctl;3176 3177	/* now return any extents the cluster had on it */3178	spin_lock(&ctl->tree_lock);3179	__btrfs_return_cluster_to_free_space(block_group, cluster);3180	spin_unlock(&ctl->tree_lock);3181 3182	btrfs_discard_queue_work(&block_group->fs_info->discard_ctl, block_group);3183 3184	/* finally drop our ref */3185	btrfs_put_block_group(block_group);3186}3187 3188static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group,3189				   struct btrfs_free_cluster *cluster,3190				   struct btrfs_free_space *entry,3191				   u64 bytes, u64 min_start,3192				   u64 *max_extent_size)3193{3194	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3195	int err;3196	u64 search_start = cluster->window_start;3197	u64 search_bytes = bytes;3198	u64 ret = 0;3199 3200	search_start = min_start;3201	search_bytes = bytes;3202 3203	err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);3204	if (err) {3205		*max_extent_size = max(get_max_extent_size(entry),3206				       *max_extent_size);3207		return 0;3208	}3209 3210	ret = search_start;3211	bitmap_clear_bits(ctl, entry, ret, bytes, false);3212 3213	return ret;3214}3215 3216/*3217 * given a cluster, try to allocate 'bytes' from it, returns 03218 * if it couldn't find anything suitably large, or a logical disk offset3219 * if things worked out3220 */3221u64 btrfs_alloc_from_cluster(struct btrfs_block_group *block_group,3222			     struct btrfs_free_cluster *cluster, u64 bytes,3223			     u64 min_start, u64 *max_extent_size)3224{3225	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3226	struct btrfs_discard_ctl *discard_ctl =3227					&block_group->fs_info->discard_ctl;3228	struct btrfs_free_space *entry = NULL;3229	struct rb_node *node;3230	u64 ret = 0;3231 3232	ASSERT(!btrfs_is_zoned(block_group->fs_info));3233 3234	spin_lock(&cluster->lock);3235	if (bytes > cluster->max_size)3236		goto out;3237 3238	if (cluster->block_group != block_group)3239		goto out;3240 3241	node = rb_first(&cluster->root);3242	if (!node)3243		goto out;3244 3245	entry = rb_entry(node, struct btrfs_free_space, offset_index);3246	while (1) {3247		if (entry->bytes < bytes)3248			*max_extent_size = max(get_max_extent_size(entry),3249					       *max_extent_size);3250 3251		if (entry->bytes < bytes ||3252		    (!entry->bitmap && entry->offset < min_start)) {3253			node = rb_next(&entry->offset_index);3254			if (!node)3255				break;3256			entry = rb_entry(node, struct btrfs_free_space,3257					 offset_index);3258			continue;3259		}3260 3261		if (entry->bitmap) {3262			ret = btrfs_alloc_from_bitmap(block_group,3263						      cluster, entry, bytes,3264						      cluster->window_start,3265						      max_extent_size);3266			if (ret == 0) {3267				node = rb_next(&entry->offset_index);3268				if (!node)3269					break;3270				entry = rb_entry(node, struct btrfs_free_space,3271						 offset_index);3272				continue;3273			}3274			cluster->window_start += bytes;3275		} else {3276			ret = entry->offset;3277 3278			entry->offset += bytes;3279			entry->bytes -= bytes;3280		}3281 3282		break;3283	}3284out:3285	spin_unlock(&cluster->lock);3286 3287	if (!ret)3288		return 0;3289 3290	spin_lock(&ctl->tree_lock);3291 3292	if (!btrfs_free_space_trimmed(entry))3293		atomic64_add(bytes, &discard_ctl->discard_bytes_saved);3294 3295	ctl->free_space -= bytes;3296	if (!entry->bitmap && !btrfs_free_space_trimmed(entry))3297		ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;3298 3299	spin_lock(&cluster->lock);3300	if (entry->bytes == 0) {3301		rb_erase(&entry->offset_index, &cluster->root);3302		ctl->free_extents--;3303		if (entry->bitmap) {3304			kmem_cache_free(btrfs_free_space_bitmap_cachep,3305					entry->bitmap);3306			ctl->total_bitmaps--;3307			recalculate_thresholds(ctl);3308		} else if (!btrfs_free_space_trimmed(entry)) {3309			ctl->discardable_extents[BTRFS_STAT_CURR]--;3310		}3311		kmem_cache_free(btrfs_free_space_cachep, entry);3312	}3313 3314	spin_unlock(&cluster->lock);3315	spin_unlock(&ctl->tree_lock);3316 3317	return ret;3318}3319 3320static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,3321				struct btrfs_free_space *entry,3322				struct btrfs_free_cluster *cluster,3323				u64 offset, u64 bytes,3324				u64 cont1_bytes, u64 min_bytes)3325{3326	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3327	unsigned long next_zero;3328	unsigned long i;3329	unsigned long want_bits;3330	unsigned long min_bits;3331	unsigned long found_bits;3332	unsigned long max_bits = 0;3333	unsigned long start = 0;3334	unsigned long total_found = 0;3335	int ret;3336 3337	lockdep_assert_held(&ctl->tree_lock);3338 3339	i = offset_to_bit(entry->offset, ctl->unit,3340			  max_t(u64, offset, entry->offset));3341	want_bits = bytes_to_bits(bytes, ctl->unit);3342	min_bits = bytes_to_bits(min_bytes, ctl->unit);3343 3344	/*3345	 * Don't bother looking for a cluster in this bitmap if it's heavily3346	 * fragmented.3347	 */3348	if (entry->max_extent_size &&3349	    entry->max_extent_size < cont1_bytes)3350		return -ENOSPC;3351again:3352	found_bits = 0;3353	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {3354		next_zero = find_next_zero_bit(entry->bitmap,3355					       BITS_PER_BITMAP, i);3356		if (next_zero - i >= min_bits) {3357			found_bits = next_zero - i;3358			if (found_bits > max_bits)3359				max_bits = found_bits;3360			break;3361		}3362		if (next_zero - i > max_bits)3363			max_bits = next_zero - i;3364		i = next_zero;3365	}3366 3367	if (!found_bits) {3368		entry->max_extent_size = (u64)max_bits * ctl->unit;3369		return -ENOSPC;3370	}3371 3372	if (!total_found) {3373		start = i;3374		cluster->max_size = 0;3375	}3376 3377	total_found += found_bits;3378 3379	if (cluster->max_size < found_bits * ctl->unit)3380		cluster->max_size = found_bits * ctl->unit;3381 3382	if (total_found < want_bits || cluster->max_size < cont1_bytes) {3383		i = next_zero + 1;3384		goto again;3385	}3386 3387	cluster->window_start = start * ctl->unit + entry->offset;3388	rb_erase(&entry->offset_index, &ctl->free_space_offset);3389	rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);3390 3391	/*3392	 * We need to know if we're currently on the normal space index when we3393	 * manipulate the bitmap so that we know we need to remove and re-insert3394	 * it into the space_index tree.  Clear the bytes_index node here so the3395	 * bitmap manipulation helpers know not to mess with the space_index3396	 * until this bitmap entry is added back into the normal cache.3397	 */3398	RB_CLEAR_NODE(&entry->bytes_index);3399 3400	ret = tree_insert_offset(ctl, cluster, entry);3401	ASSERT(!ret); /* -EEXIST; Logic error */3402 3403	trace_btrfs_setup_cluster(block_group, cluster,3404				  total_found * ctl->unit, 1);3405	return 0;3406}3407 3408/*3409 * This searches the block group for just extents to fill the cluster with.3410 * Try to find a cluster with at least bytes total bytes, at least one3411 * extent of cont1_bytes, and other clusters of at least min_bytes.3412 */3413static noinline int3414setup_cluster_no_bitmap(struct btrfs_block_group *block_group,3415			struct btrfs_free_cluster *cluster,3416			struct list_head *bitmaps, u64 offset, u64 bytes,3417			u64 cont1_bytes, u64 min_bytes)3418{3419	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3420	struct btrfs_free_space *first = NULL;3421	struct btrfs_free_space *entry = NULL;3422	struct btrfs_free_space *last;3423	struct rb_node *node;3424	u64 window_free;3425	u64 max_extent;3426	u64 total_size = 0;3427 3428	lockdep_assert_held(&ctl->tree_lock);3429 3430	entry = tree_search_offset(ctl, offset, 0, 1);3431	if (!entry)3432		return -ENOSPC;3433 3434	/*3435	 * We don't want bitmaps, so just move along until we find a normal3436	 * extent entry.3437	 */3438	while (entry->bitmap || entry->bytes < min_bytes) {3439		if (entry->bitmap && list_empty(&entry->list))3440			list_add_tail(&entry->list, bitmaps);3441		node = rb_next(&entry->offset_index);3442		if (!node)3443			return -ENOSPC;3444		entry = rb_entry(node, struct btrfs_free_space, offset_index);3445	}3446 3447	window_free = entry->bytes;3448	max_extent = entry->bytes;3449	first = entry;3450	last = entry;3451 3452	for (node = rb_next(&entry->offset_index); node;3453	     node = rb_next(&entry->offset_index)) {3454		entry = rb_entry(node, struct btrfs_free_space, offset_index);3455 3456		if (entry->bitmap) {3457			if (list_empty(&entry->list))3458				list_add_tail(&entry->list, bitmaps);3459			continue;3460		}3461 3462		if (entry->bytes < min_bytes)3463			continue;3464 3465		last = entry;3466		window_free += entry->bytes;3467		if (entry->bytes > max_extent)3468			max_extent = entry->bytes;3469	}3470 3471	if (window_free < bytes || max_extent < cont1_bytes)3472		return -ENOSPC;3473 3474	cluster->window_start = first->offset;3475 3476	node = &first->offset_index;3477 3478	/*3479	 * now we've found our entries, pull them out of the free space3480	 * cache and put them into the cluster rbtree3481	 */3482	do {3483		int ret;3484 3485		entry = rb_entry(node, struct btrfs_free_space, offset_index);3486		node = rb_next(&entry->offset_index);3487		if (entry->bitmap || entry->bytes < min_bytes)3488			continue;3489 3490		rb_erase(&entry->offset_index, &ctl->free_space_offset);3491		rb_erase_cached(&entry->bytes_index, &ctl->free_space_bytes);3492		ret = tree_insert_offset(ctl, cluster, entry);3493		total_size += entry->bytes;3494		ASSERT(!ret); /* -EEXIST; Logic error */3495	} while (node && entry != last);3496 3497	cluster->max_size = max_extent;3498	trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);3499	return 0;3500}3501 3502/*3503 * This specifically looks for bitmaps that may work in the cluster, we assume3504 * that we have already failed to find extents that will work.3505 */3506static noinline int3507setup_cluster_bitmap(struct btrfs_block_group *block_group,3508		     struct btrfs_free_cluster *cluster,3509		     struct list_head *bitmaps, u64 offset, u64 bytes,3510		     u64 cont1_bytes, u64 min_bytes)3511{3512	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3513	struct btrfs_free_space *entry = NULL;3514	int ret = -ENOSPC;3515	u64 bitmap_offset = offset_to_bitmap(ctl, offset);3516 3517	if (ctl->total_bitmaps == 0)3518		return -ENOSPC;3519 3520	/*3521	 * The bitmap that covers offset won't be in the list unless offset3522	 * is just its start offset.3523	 */3524	if (!list_empty(bitmaps))3525		entry = list_first_entry(bitmaps, struct btrfs_free_space, list);3526 3527	if (!entry || entry->offset != bitmap_offset) {3528		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);3529		if (entry && list_empty(&entry->list))3530			list_add(&entry->list, bitmaps);3531	}3532 3533	list_for_each_entry(entry, bitmaps, list) {3534		if (entry->bytes < bytes)3535			continue;3536		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,3537					   bytes, cont1_bytes, min_bytes);3538		if (!ret)3539			return 0;3540	}3541 3542	/*3543	 * The bitmaps list has all the bitmaps that record free space3544	 * starting after offset, so no more search is required.3545	 */3546	return -ENOSPC;3547}3548 3549/*3550 * here we try to find a cluster of blocks in a block group.  The goal3551 * is to find at least bytes+empty_size.3552 * We might not find them all in one contiguous area.3553 *3554 * returns zero and sets up cluster if things worked out, otherwise3555 * it returns -enospc3556 */3557int btrfs_find_space_cluster(struct btrfs_block_group *block_group,3558			     struct btrfs_free_cluster *cluster,3559			     u64 offset, u64 bytes, u64 empty_size)3560{3561	struct btrfs_fs_info *fs_info = block_group->fs_info;3562	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3563	struct btrfs_free_space *entry, *tmp;3564	LIST_HEAD(bitmaps);3565	u64 min_bytes;3566	u64 cont1_bytes;3567	int ret;3568 3569	/*3570	 * Choose the minimum extent size we'll require for this3571	 * cluster.  For SSD_SPREAD, don't allow any fragmentation.3572	 * For metadata, allow allocates with smaller extents.  For3573	 * data, keep it dense.3574	 */3575	if (btrfs_test_opt(fs_info, SSD_SPREAD)) {3576		cont1_bytes = bytes + empty_size;3577		min_bytes = cont1_bytes;3578	} else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {3579		cont1_bytes = bytes;3580		min_bytes = fs_info->sectorsize;3581	} else {3582		cont1_bytes = max(bytes, (bytes + empty_size) >> 2);3583		min_bytes = fs_info->sectorsize;3584	}3585 3586	spin_lock(&ctl->tree_lock);3587 3588	/*3589	 * If we know we don't have enough space to make a cluster don't even3590	 * bother doing all the work to try and find one.3591	 */3592	if (ctl->free_space < bytes) {3593		spin_unlock(&ctl->tree_lock);3594		return -ENOSPC;3595	}3596 3597	spin_lock(&cluster->lock);3598 3599	/* someone already found a cluster, hooray */3600	if (cluster->block_group) {3601		ret = 0;3602		goto out;3603	}3604 3605	trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,3606				 min_bytes);3607 3608	ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,3609				      bytes + empty_size,3610				      cont1_bytes, min_bytes);3611	if (ret)3612		ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,3613					   offset, bytes + empty_size,3614					   cont1_bytes, min_bytes);3615 3616	/* Clear our temporary list */3617	list_for_each_entry_safe(entry, tmp, &bitmaps, list)3618		list_del_init(&entry->list);3619 3620	if (!ret) {3621		btrfs_get_block_group(block_group);3622		list_add_tail(&cluster->block_group_list,3623			      &block_group->cluster_list);3624		cluster->block_group = block_group;3625	} else {3626		trace_btrfs_failed_cluster_setup(block_group);3627	}3628out:3629	spin_unlock(&cluster->lock);3630	spin_unlock(&ctl->tree_lock);3631 3632	return ret;3633}3634 3635/*3636 * simple code to zero out a cluster3637 */3638void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)3639{3640	spin_lock_init(&cluster->lock);3641	spin_lock_init(&cluster->refill_lock);3642	cluster->root = RB_ROOT;3643	cluster->max_size = 0;3644	cluster->fragmented = false;3645	INIT_LIST_HEAD(&cluster->block_group_list);3646	cluster->block_group = NULL;3647}3648 3649static int do_trimming(struct btrfs_block_group *block_group,3650		       u64 *total_trimmed, u64 start, u64 bytes,3651		       u64 reserved_start, u64 reserved_bytes,3652		       enum btrfs_trim_state reserved_trim_state,3653		       struct btrfs_trim_range *trim_entry)3654{3655	struct btrfs_space_info *space_info = block_group->space_info;3656	struct btrfs_fs_info *fs_info = block_group->fs_info;3657	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3658	int ret;3659	int update = 0;3660	const u64 end = start + bytes;3661	const u64 reserved_end = reserved_start + reserved_bytes;3662	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;3663	u64 trimmed = 0;3664 3665	spin_lock(&space_info->lock);3666	spin_lock(&block_group->lock);3667	if (!block_group->ro) {3668		block_group->reserved += reserved_bytes;3669		space_info->bytes_reserved += reserved_bytes;3670		update = 1;3671	}3672	spin_unlock(&block_group->lock);3673	spin_unlock(&space_info->lock);3674 3675	ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed);3676	if (!ret) {3677		*total_trimmed += trimmed;3678		trim_state = BTRFS_TRIM_STATE_TRIMMED;3679	}3680 3681	mutex_lock(&ctl->cache_writeout_mutex);3682	if (reserved_start < start)3683		__btrfs_add_free_space(block_group, reserved_start,3684				       start - reserved_start,3685				       reserved_trim_state);3686	if (end < reserved_end)3687		__btrfs_add_free_space(block_group, end, reserved_end - end,3688				       reserved_trim_state);3689	__btrfs_add_free_space(block_group, start, bytes, trim_state);3690	list_del(&trim_entry->list);3691	mutex_unlock(&ctl->cache_writeout_mutex);3692 3693	if (update) {3694		spin_lock(&space_info->lock);3695		spin_lock(&block_group->lock);3696		if (block_group->ro)3697			space_info->bytes_readonly += reserved_bytes;3698		block_group->reserved -= reserved_bytes;3699		space_info->bytes_reserved -= reserved_bytes;3700		spin_unlock(&block_group->lock);3701		spin_unlock(&space_info->lock);3702	}3703 3704	return ret;3705}3706 3707/*3708 * If @async is set, then we will trim 1 region and return.3709 */3710static int trim_no_bitmap(struct btrfs_block_group *block_group,3711			  u64 *total_trimmed, u64 start, u64 end, u64 minlen,3712			  bool async)3713{3714	struct btrfs_discard_ctl *discard_ctl =3715					&block_group->fs_info->discard_ctl;3716	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3717	struct btrfs_free_space *entry;3718	struct rb_node *node;3719	int ret = 0;3720	u64 extent_start;3721	u64 extent_bytes;3722	enum btrfs_trim_state extent_trim_state;3723	u64 bytes;3724	const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);3725 3726	while (start < end) {3727		struct btrfs_trim_range trim_entry;3728 3729		mutex_lock(&ctl->cache_writeout_mutex);3730		spin_lock(&ctl->tree_lock);3731 3732		if (ctl->free_space < minlen)3733			goto out_unlock;3734 3735		entry = tree_search_offset(ctl, start, 0, 1);3736		if (!entry)3737			goto out_unlock;3738 3739		/* Skip bitmaps and if async, already trimmed entries */3740		while (entry->bitmap ||3741		       (async && btrfs_free_space_trimmed(entry))) {3742			node = rb_next(&entry->offset_index);3743			if (!node)3744				goto out_unlock;3745			entry = rb_entry(node, struct btrfs_free_space,3746					 offset_index);3747		}3748 3749		if (entry->offset >= end)3750			goto out_unlock;3751 3752		extent_start = entry->offset;3753		extent_bytes = entry->bytes;3754		extent_trim_state = entry->trim_state;3755		if (async) {3756			start = entry->offset;3757			bytes = entry->bytes;3758			if (bytes < minlen) {3759				spin_unlock(&ctl->tree_lock);3760				mutex_unlock(&ctl->cache_writeout_mutex);3761				goto next;3762			}3763			unlink_free_space(ctl, entry, true);3764			/*3765			 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.3766			 * If X < BTRFS_ASYNC_DISCARD_MIN_FILTER, we won't trim3767			 * X when we come back around.  So trim it now.3768			 */3769			if (max_discard_size &&3770			    bytes >= (max_discard_size +3771				      BTRFS_ASYNC_DISCARD_MIN_FILTER)) {3772				bytes = max_discard_size;3773				extent_bytes = max_discard_size;3774				entry->offset += max_discard_size;3775				entry->bytes -= max_discard_size;3776				link_free_space(ctl, entry);3777			} else {3778				kmem_cache_free(btrfs_free_space_cachep, entry);3779			}3780		} else {3781			start = max(start, extent_start);3782			bytes = min(extent_start + extent_bytes, end) - start;3783			if (bytes < minlen) {3784				spin_unlock(&ctl->tree_lock);3785				mutex_unlock(&ctl->cache_writeout_mutex);3786				goto next;3787			}3788 3789			unlink_free_space(ctl, entry, true);3790			kmem_cache_free(btrfs_free_space_cachep, entry);3791		}3792 3793		spin_unlock(&ctl->tree_lock);3794		trim_entry.start = extent_start;3795		trim_entry.bytes = extent_bytes;3796		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);3797		mutex_unlock(&ctl->cache_writeout_mutex);3798 3799		ret = do_trimming(block_group, total_trimmed, start, bytes,3800				  extent_start, extent_bytes, extent_trim_state,3801				  &trim_entry);3802		if (ret) {3803			block_group->discard_cursor = start + bytes;3804			break;3805		}3806next:3807		start += bytes;3808		block_group->discard_cursor = start;3809		if (async && *total_trimmed)3810			break;3811 3812		if (btrfs_trim_interrupted()) {3813			ret = -ERESTARTSYS;3814			break;3815		}3816 3817		cond_resched();3818	}3819 3820	return ret;3821 3822out_unlock:3823	block_group->discard_cursor = btrfs_block_group_end(block_group);3824	spin_unlock(&ctl->tree_lock);3825	mutex_unlock(&ctl->cache_writeout_mutex);3826 3827	return ret;3828}3829 3830/*3831 * If we break out of trimming a bitmap prematurely, we should reset the3832 * trimming bit.  In a rather contrieved case, it's possible to race here so3833 * reset the state to BTRFS_TRIM_STATE_UNTRIMMED.3834 *3835 * start = start of bitmap3836 * end = near end of bitmap3837 *3838 * Thread 1:			Thread 2:3839 * trim_bitmaps(start)3840 *				trim_bitmaps(end)3841 *				end_trimming_bitmap()3842 * reset_trimming_bitmap()3843 */3844static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset)3845{3846	struct btrfs_free_space *entry;3847 3848	spin_lock(&ctl->tree_lock);3849	entry = tree_search_offset(ctl, offset, 1, 0);3850	if (entry) {3851		if (btrfs_free_space_trimmed(entry)) {3852			ctl->discardable_extents[BTRFS_STAT_CURR] +=3853				entry->bitmap_extents;3854			ctl->discardable_bytes[BTRFS_STAT_CURR] += entry->bytes;3855		}3856		entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;3857	}3858 3859	spin_unlock(&ctl->tree_lock);3860}3861 3862static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl,3863				struct btrfs_free_space *entry)3864{3865	if (btrfs_free_space_trimming_bitmap(entry)) {3866		entry->trim_state = BTRFS_TRIM_STATE_TRIMMED;3867		ctl->discardable_extents[BTRFS_STAT_CURR] -=3868			entry->bitmap_extents;3869		ctl->discardable_bytes[BTRFS_STAT_CURR] -= entry->bytes;3870	}3871}3872 3873/*3874 * If @async is set, then we will trim 1 region and return.3875 */3876static int trim_bitmaps(struct btrfs_block_group *block_group,3877			u64 *total_trimmed, u64 start, u64 end, u64 minlen,3878			u64 maxlen, bool async)3879{3880	struct btrfs_discard_ctl *discard_ctl =3881					&block_group->fs_info->discard_ctl;3882	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;3883	struct btrfs_free_space *entry;3884	int ret = 0;3885	int ret2;3886	u64 bytes;3887	u64 offset = offset_to_bitmap(ctl, start);3888	const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);3889 3890	while (offset < end) {3891		bool next_bitmap = false;3892		struct btrfs_trim_range trim_entry;3893 3894		mutex_lock(&ctl->cache_writeout_mutex);3895		spin_lock(&ctl->tree_lock);3896 3897		if (ctl->free_space < minlen) {3898			block_group->discard_cursor =3899				btrfs_block_group_end(block_group);3900			spin_unlock(&ctl->tree_lock);3901			mutex_unlock(&ctl->cache_writeout_mutex);3902			break;3903		}3904 3905		entry = tree_search_offset(ctl, offset, 1, 0);3906		/*3907		 * Bitmaps are marked trimmed lossily now to prevent constant3908		 * discarding of the same bitmap (the reason why we are bound3909		 * by the filters).  So, retrim the block group bitmaps when we3910		 * are preparing to punt to the unused_bgs list.  This uses3911		 * @minlen to determine if we are in BTRFS_DISCARD_INDEX_UNUSED3912		 * which is the only discard index which sets minlen to 0.3913		 */3914		if (!entry || (async && minlen && start == offset &&3915			       btrfs_free_space_trimmed(entry))) {3916			spin_unlock(&ctl->tree_lock);3917			mutex_unlock(&ctl->cache_writeout_mutex);3918			next_bitmap = true;3919			goto next;3920		}3921 3922		/*3923		 * Async discard bitmap trimming begins at by setting the start3924		 * to be key.objectid and the offset_to_bitmap() aligns to the3925		 * start of the bitmap.  This lets us know we are fully3926		 * scanning the bitmap rather than only some portion of it.3927		 */3928		if (start == offset)3929			entry->trim_state = BTRFS_TRIM_STATE_TRIMMING;3930 3931		bytes = minlen;3932		ret2 = search_bitmap(ctl, entry, &start, &bytes, false);3933		if (ret2 || start >= end) {3934			/*3935			 * We lossily consider a bitmap trimmed if we only skip3936			 * over regions <= BTRFS_ASYNC_DISCARD_MIN_FILTER.3937			 */3938			if (ret2 && minlen <= BTRFS_ASYNC_DISCARD_MIN_FILTER)3939				end_trimming_bitmap(ctl, entry);3940			else3941				entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;3942			spin_unlock(&ctl->tree_lock);3943			mutex_unlock(&ctl->cache_writeout_mutex);3944			next_bitmap = true;3945			goto next;3946		}3947 3948		/*3949		 * We already trimmed a region, but are using the locking above3950		 * to reset the trim_state.3951		 */3952		if (async && *total_trimmed) {3953			spin_unlock(&ctl->tree_lock);3954			mutex_unlock(&ctl->cache_writeout_mutex);3955			goto out;3956		}3957 3958		bytes = min(bytes, end - start);3959		if (bytes < minlen || (async && maxlen && bytes > maxlen)) {3960			spin_unlock(&ctl->tree_lock);3961			mutex_unlock(&ctl->cache_writeout_mutex);3962			goto next;3963		}3964 3965		/*3966		 * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.3967		 * If X < @minlen, we won't trim X when we come back around.3968		 * So trim it now.  We differ here from trimming extents as we3969		 * don't keep individual state per bit.3970		 */3971		if (async &&3972		    max_discard_size &&3973		    bytes > (max_discard_size + minlen))3974			bytes = max_discard_size;3975 3976		bitmap_clear_bits(ctl, entry, start, bytes, true);3977		if (entry->bytes == 0)3978			free_bitmap(ctl, entry);3979 3980		spin_unlock(&ctl->tree_lock);3981		trim_entry.start = start;3982		trim_entry.bytes = bytes;3983		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);3984		mutex_unlock(&ctl->cache_writeout_mutex);3985 3986		ret = do_trimming(block_group, total_trimmed, start, bytes,3987				  start, bytes, 0, &trim_entry);3988		if (ret) {3989			reset_trimming_bitmap(ctl, offset);3990			block_group->discard_cursor =3991				btrfs_block_group_end(block_group);3992			break;3993		}3994next:3995		if (next_bitmap) {3996			offset += BITS_PER_BITMAP * ctl->unit;3997			start = offset;3998		} else {3999			start += bytes;4000		}4001		block_group->discard_cursor = start;4002 4003		if (btrfs_trim_interrupted()) {4004			if (start != offset)4005				reset_trimming_bitmap(ctl, offset);4006			ret = -ERESTARTSYS;4007			break;4008		}4009 4010		cond_resched();4011	}4012 4013	if (offset >= end)4014		block_group->discard_cursor = end;4015 4016out:4017	return ret;4018}4019 4020int btrfs_trim_block_group(struct btrfs_block_group *block_group,4021			   u64 *trimmed, u64 start, u64 end, u64 minlen)4022{4023	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;4024	int ret;4025	u64 rem = 0;4026 4027	ASSERT(!btrfs_is_zoned(block_group->fs_info));4028 4029	*trimmed = 0;4030 4031	spin_lock(&block_group->lock);4032	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {4033		spin_unlock(&block_group->lock);4034		return 0;4035	}4036	btrfs_freeze_block_group(block_group);4037	spin_unlock(&block_group->lock);4038 4039	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, false);4040	if (ret)4041		goto out;4042 4043	ret = trim_bitmaps(block_group, trimmed, start, end, minlen, 0, false);4044	div64_u64_rem(end, BITS_PER_BITMAP * ctl->unit, &rem);4045	/* If we ended in the middle of a bitmap, reset the trimming flag */4046	if (rem)4047		reset_trimming_bitmap(ctl, offset_to_bitmap(ctl, end));4048out:4049	btrfs_unfreeze_block_group(block_group);4050	return ret;4051}4052 4053int btrfs_trim_block_group_extents(struct btrfs_block_group *block_group,4054				   u64 *trimmed, u64 start, u64 end, u64 minlen,4055				   bool async)4056{4057	int ret;4058 4059	*trimmed = 0;4060 4061	spin_lock(&block_group->lock);4062	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {4063		spin_unlock(&block_group->lock);4064		return 0;4065	}4066	btrfs_freeze_block_group(block_group);4067	spin_unlock(&block_group->lock);4068 4069	ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, async);4070	btrfs_unfreeze_block_group(block_group);4071 4072	return ret;4073}4074 4075int btrfs_trim_block_group_bitmaps(struct btrfs_block_group *block_group,4076				   u64 *trimmed, u64 start, u64 end, u64 minlen,4077				   u64 maxlen, bool async)4078{4079	int ret;4080 4081	*trimmed = 0;4082 4083	spin_lock(&block_group->lock);4084	if (test_bit(BLOCK_GROUP_FLAG_REMOVED, &block_group->runtime_flags)) {4085		spin_unlock(&block_group->lock);4086		return 0;4087	}4088	btrfs_freeze_block_group(block_group);4089	spin_unlock(&block_group->lock);4090 4091	ret = trim_bitmaps(block_group, trimmed, start, end, minlen, maxlen,4092			   async);4093 4094	btrfs_unfreeze_block_group(block_group);4095 4096	return ret;4097}4098 4099bool btrfs_free_space_cache_v1_active(struct btrfs_fs_info *fs_info)4100{4101	return btrfs_super_cache_generation(fs_info->super_copy);4102}4103 4104static int cleanup_free_space_cache_v1(struct btrfs_fs_info *fs_info,4105				       struct btrfs_trans_handle *trans)4106{4107	struct btrfs_block_group *block_group;4108	struct rb_node *node;4109	int ret = 0;4110 4111	btrfs_info(fs_info, "cleaning free space cache v1");4112 4113	node = rb_first_cached(&fs_info->block_group_cache_tree);4114	while (node) {4115		block_group = rb_entry(node, struct btrfs_block_group, cache_node);4116		ret = btrfs_remove_free_space_inode(trans, NULL, block_group);4117		if (ret)4118			goto out;4119		node = rb_next(node);4120	}4121out:4122	return ret;4123}4124 4125int btrfs_set_free_space_cache_v1_active(struct btrfs_fs_info *fs_info, bool active)4126{4127	struct btrfs_trans_handle *trans;4128	int ret;4129 4130	/*4131	 * update_super_roots will appropriately set or unset4132	 * super_copy->cache_generation based on SPACE_CACHE and4133	 * BTRFS_FS_CLEANUP_SPACE_CACHE_V1. For this reason, we need a4134	 * transaction commit whether we are enabling space cache v1 and don't4135	 * have any other work to do, or are disabling it and removing free4136	 * space inodes.4137	 */4138	trans = btrfs_start_transaction(fs_info->tree_root, 0);4139	if (IS_ERR(trans))4140		return PTR_ERR(trans);4141 4142	if (!active) {4143		set_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags);4144		ret = cleanup_free_space_cache_v1(fs_info, trans);4145		if (ret) {4146			btrfs_abort_transaction(trans, ret);4147			btrfs_end_transaction(trans);4148			goto out;4149		}4150	}4151 4152	ret = btrfs_commit_transaction(trans);4153out:4154	clear_bit(BTRFS_FS_CLEANUP_SPACE_CACHE_V1, &fs_info->flags);4155 4156	return ret;4157}4158 4159int __init btrfs_free_space_init(void)4160{4161	btrfs_free_space_cachep = KMEM_CACHE(btrfs_free_space, 0);4162	if (!btrfs_free_space_cachep)4163		return -ENOMEM;4164 4165	btrfs_free_space_bitmap_cachep = kmem_cache_create("btrfs_free_space_bitmap",4166							PAGE_SIZE, PAGE_SIZE,4167							0, NULL);4168	if (!btrfs_free_space_bitmap_cachep) {4169		kmem_cache_destroy(btrfs_free_space_cachep);4170		return -ENOMEM;4171	}4172 4173	return 0;4174}4175 4176void __cold btrfs_free_space_exit(void)4177{4178	kmem_cache_destroy(btrfs_free_space_cachep);4179	kmem_cache_destroy(btrfs_free_space_bitmap_cachep);4180}4181 4182#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS4183/*4184 * Use this if you need to make a bitmap or extent entry specifically, it4185 * doesn't do any of the merging that add_free_space does, this acts a lot like4186 * how the free space cache loading stuff works, so you can get really weird4187 * configurations.4188 */4189int test_add_free_space_entry(struct btrfs_block_group *cache,4190			      u64 offset, u64 bytes, bool bitmap)4191{4192	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;4193	struct btrfs_free_space *info = NULL, *bitmap_info;4194	void *map = NULL;4195	enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_TRIMMED;4196	u64 bytes_added;4197	int ret;4198 4199again:4200	if (!info) {4201		info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);4202		if (!info)4203			return -ENOMEM;4204	}4205 4206	if (!bitmap) {4207		spin_lock(&ctl->tree_lock);4208		info->offset = offset;4209		info->bytes = bytes;4210		info->max_extent_size = 0;4211		ret = link_free_space(ctl, info);4212		spin_unlock(&ctl->tree_lock);4213		if (ret)4214			kmem_cache_free(btrfs_free_space_cachep, info);4215		return ret;4216	}4217 4218	if (!map) {4219		map = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, GFP_NOFS);4220		if (!map) {4221			kmem_cache_free(btrfs_free_space_cachep, info);4222			return -ENOMEM;4223		}4224	}4225 4226	spin_lock(&ctl->tree_lock);4227	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),4228					 1, 0);4229	if (!bitmap_info) {4230		info->bitmap = map;4231		map = NULL;4232		add_new_bitmap(ctl, info, offset);4233		bitmap_info = info;4234		info = NULL;4235	}4236 4237	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,4238					  trim_state);4239 4240	bytes -= bytes_added;4241	offset += bytes_added;4242	spin_unlock(&ctl->tree_lock);4243 4244	if (bytes)4245		goto again;4246 4247	if (info)4248		kmem_cache_free(btrfs_free_space_cachep, info);4249	if (map)4250		kmem_cache_free(btrfs_free_space_bitmap_cachep, map);4251	return 0;4252}4253 4254/*4255 * Checks to see if the given range is in the free space cache.  This is really4256 * just used to check the absence of space, so if there is free space in the4257 * range at all we will return 1.4258 */4259int test_check_exists(struct btrfs_block_group *cache,4260		      u64 offset, u64 bytes)4261{4262	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;4263	struct btrfs_free_space *info;4264	int ret = 0;4265 4266	spin_lock(&ctl->tree_lock);4267	info = tree_search_offset(ctl, offset, 0, 0);4268	if (!info) {4269		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),4270					  1, 0);4271		if (!info)4272			goto out;4273	}4274 4275have_info:4276	if (info->bitmap) {4277		u64 bit_off, bit_bytes;4278		struct rb_node *n;4279		struct btrfs_free_space *tmp;4280 4281		bit_off = offset;4282		bit_bytes = ctl->unit;4283		ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);4284		if (!ret) {4285			if (bit_off == offset) {4286				ret = 1;4287				goto out;4288			} else if (bit_off > offset &&4289				   offset + bytes > bit_off) {4290				ret = 1;4291				goto out;4292			}4293		}4294 4295		n = rb_prev(&info->offset_index);4296		while (n) {4297			tmp = rb_entry(n, struct btrfs_free_space,4298				       offset_index);4299			if (tmp->offset + tmp->bytes < offset)4300				break;4301			if (offset + bytes < tmp->offset) {4302				n = rb_prev(&tmp->offset_index);4303				continue;4304			}4305			info = tmp;4306			goto have_info;4307		}4308 4309		n = rb_next(&info->offset_index);4310		while (n) {4311			tmp = rb_entry(n, struct btrfs_free_space,4312				       offset_index);4313			if (offset + bytes < tmp->offset)4314				break;4315			if (tmp->offset + tmp->bytes < offset) {4316				n = rb_next(&tmp->offset_index);4317				continue;4318			}4319			info = tmp;4320			goto have_info;4321		}4322 4323		ret = 0;4324		goto out;4325	}4326 4327	if (info->offset == offset) {4328		ret = 1;4329		goto out;4330	}4331 4332	if (offset > info->offset && offset < info->offset + info->bytes)4333		ret = 1;4334out:4335	spin_unlock(&ctl->tree_lock);4336	return ret;4337}4338#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */4339