30 static int link_free_space(struct btrfs_free_space_ctl *ctl,
32 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
621 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)  in merge_space_tree()  argument
627 	spin_lock(&ctl->tree_lock);  in merge_space_tree()
628 	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {  in merge_space_tree()
635 			unlink_free_space(ctl, prev);  in merge_space_tree()
636 			unlink_free_space(ctl, e);  in merge_space_tree()
639 			link_free_space(ctl, prev);  in merge_space_tree()
641 			spin_unlock(&ctl->tree_lock);  in merge_space_tree()
647 	spin_unlock(&ctl->tree_lock);  in merge_space_tree()
651 				   struct btrfs_free_space_ctl *ctl,  in __load_free_space_cache()  argument
746 			spin_lock(&ctl->tree_lock);  in __load_free_space_cache()
747 			ret = link_free_space(ctl, e);  in __load_free_space_cache()
748 			spin_unlock(&ctl->tree_lock);  in __load_free_space_cache()
764 			spin_lock(&ctl->tree_lock);  in __load_free_space_cache()
765 			ret = link_free_space(ctl, e);  in __load_free_space_cache()
766 			ctl->total_bitmaps++;  in __load_free_space_cache()
767 			ctl->op->recalc_thresholds(ctl);  in __load_free_space_cache()
768 			spin_unlock(&ctl->tree_lock);  in __load_free_space_cache()
795 	merge_space_tree(ctl);  in __load_free_space_cache()
802 	__btrfs_remove_free_space_cache(ctl);  in __load_free_space_cache()
809 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in load_free_space_cache()  local
848 	ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,  in load_free_space_cache()
854 	spin_lock(&ctl->tree_lock);  in load_free_space_cache()
855 	matched = (ctl->free_space == (block_group->key.offset - used -  in load_free_space_cache()
857 	spin_unlock(&ctl->tree_lock);  in load_free_space_cache()
860 		__btrfs_remove_free_space_cache(ctl);  in load_free_space_cache()
885 			      struct btrfs_free_space_ctl *ctl,  in write_cache_extent_entries()  argument
893 	struct rb_node *node = rb_first(&ctl->free_space_offset);  in write_cache_extent_entries()
945 	list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {  in write_cache_extent_entries()
1205 				   struct btrfs_free_space_ctl *ctl,  in __btrfs_write_out_cache()  argument
1251 	mutex_lock(&ctl->cache_writeout_mutex);  in __btrfs_write_out_cache()
1253 	spin_lock(&ctl->tree_lock);  in __btrfs_write_out_cache()
1254 	ret = write_cache_extent_entries(io_ctl, ctl,  in __btrfs_write_out_cache()
1279 	spin_unlock(&ctl->tree_lock);  in __btrfs_write_out_cache()
1280 	mutex_unlock(&ctl->cache_writeout_mutex);  in __btrfs_write_out_cache()
1332 	spin_unlock(&ctl->tree_lock);  in __btrfs_write_out_cache()
1333 	mutex_unlock(&ctl->cache_writeout_mutex);  in __btrfs_write_out_cache()
1350 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_write_out_cache()  local
1365 	ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl,  in btrfs_write_out_cache()
1402 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,  in offset_to_bitmap()  argument
1408 	bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;  in offset_to_bitmap()
1409 	bitmap_start = offset - ctl->start;  in offset_to_bitmap()
1412 	bitmap_start += ctl->start;  in offset_to_bitmap()
1476 tree_search_offset(struct btrfs_free_space_ctl *ctl,  in tree_search_offset()  argument
1479 	struct rb_node *n = ctl->free_space_offset.rb_node;  in tree_search_offset()
1565 		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)  in tree_search_offset()
1576 			    ctl->unit > offset)  in tree_search_offset()
1592 __unlink_free_space(struct btrfs_free_space_ctl *ctl,  in __unlink_free_space()  argument
1595 	rb_erase(&info->offset_index, &ctl->free_space_offset);  in __unlink_free_space()
1596 	ctl->free_extents--;  in __unlink_free_space()
1599 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,  in unlink_free_space()  argument
1602 	__unlink_free_space(ctl, info);  in unlink_free_space()
1603 	ctl->free_space -= info->bytes;  in unlink_free_space()
1606 static int link_free_space(struct btrfs_free_space_ctl *ctl,  in link_free_space()  argument
1612 	ret = tree_insert_offset(&ctl->free_space_offset, info->offset,  in link_free_space()
1617 	ctl->free_space += info->bytes;  in link_free_space()
1618 	ctl->free_extents++;  in link_free_space()
1622 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)  in recalculate_thresholds()  argument
1624 	struct btrfs_block_group_cache *block_group = ctl->private;  in recalculate_thresholds()
1629 	u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;  in recalculate_thresholds()
1634 	ASSERT(ctl->total_bitmaps <= max_bitmaps);  in recalculate_thresholds()
1651 	bitmap_bytes = (ctl->total_bitmaps + 1) * ctl->unit;  in recalculate_thresholds()
1654 		ctl->extents_thresh = 0;  in recalculate_thresholds()
1665 	ctl->extents_thresh =  in recalculate_thresholds()
1669 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,  in __bitmap_clear_bits()  argument
1675 	start = offset_to_bit(info->offset, ctl->unit, offset);  in __bitmap_clear_bits()
1676 	count = bytes_to_bits(bytes, ctl->unit);  in __bitmap_clear_bits()
1684 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,  in bitmap_clear_bits()  argument
1688 	__bitmap_clear_bits(ctl, info, offset, bytes);  in bitmap_clear_bits()
1689 	ctl->free_space -= bytes;  in bitmap_clear_bits()
1692 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,  in bitmap_set_bits()  argument
1698 	start = offset_to_bit(info->offset, ctl->unit, offset);  in bitmap_set_bits()
1699 	count = bytes_to_bits(bytes, ctl->unit);  in bitmap_set_bits()
1705 	ctl->free_space += bytes;  in bitmap_set_bits()
1712 static int search_bitmap(struct btrfs_free_space_ctl *ctl,  in search_bitmap()  argument
1733 	i = offset_to_bit(bitmap_info->offset, ctl->unit,  in search_bitmap()
1735 	bits = bytes_to_bits(*bytes, ctl->unit);  in search_bitmap()
1755 		*offset = (u64)(i * ctl->unit) + bitmap_info->offset;  in search_bitmap()
1756 		*bytes = (u64)(found_bits) * ctl->unit;  in search_bitmap()
1760 	*bytes = (u64)(max_bits) * ctl->unit;  in search_bitmap()
1767 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,  in find_free_space()  argument
1776 	if (!ctl->free_space_offset.rb_node)  in find_free_space()
1779 	entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);  in find_free_space()
1795 			tmp = entry->offset - ctl->start + align - 1;  in find_free_space()
1797 			tmp = tmp * align + ctl->start;  in find_free_space()
1813 			ret = search_bitmap(ctl, entry, &tmp, &size, true);  in find_free_space()
1832 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,  in add_new_bitmap()  argument
1835 	info->offset = offset_to_bitmap(ctl, offset);  in add_new_bitmap()
1838 	link_free_space(ctl, info);  in add_new_bitmap()
1839 	ctl->total_bitmaps++;  in add_new_bitmap()
1841 	ctl->op->recalc_thresholds(ctl);  in add_new_bitmap()
1844 static void free_bitmap(struct btrfs_free_space_ctl *ctl,  in free_bitmap()  argument
1847 	unlink_free_space(ctl, bitmap_info);  in free_bitmap()
1850 	ctl->total_bitmaps--;  in free_bitmap()
1851 	ctl->op->recalc_thresholds(ctl);  in free_bitmap()
1854 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,  in remove_from_bitmap()  argument
1863 	end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;  in remove_from_bitmap()
1872 	search_bytes = ctl->unit;  in remove_from_bitmap()
1874 	ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,  in remove_from_bitmap()
1885 	bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);  in remove_from_bitmap()
1892 			free_bitmap(ctl, bitmap_info);  in remove_from_bitmap()
1918 		search_bytes = ctl->unit;  in remove_from_bitmap()
1919 		ret = search_bitmap(ctl, bitmap_info, &search_start,  in remove_from_bitmap()
1926 		free_bitmap(ctl, bitmap_info);  in remove_from_bitmap()
1931 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,  in add_bytes_to_bitmap()  argument
1938 	end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);  in add_bytes_to_bitmap()
1942 	bitmap_set_bits(ctl, info, offset, bytes_to_set);  in add_bytes_to_bitmap()
1954 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,  in use_bitmap()  argument
1957 	struct btrfs_block_group_cache *block_group = ctl->private;  in use_bitmap()
1970 	if (!forced && ctl->free_extents < ctl->extents_thresh) {  in use_bitmap()
1979 			if (ctl->free_extents * 2 <= ctl->extents_thresh)  in use_bitmap()
1994 	if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset)  in use_bitmap()
2005 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,  in insert_into_bitmap()  argument
2017 	if (!ctl->op->use_bitmap(ctl, info))  in insert_into_bitmap()
2020 	if (ctl->op == &free_space_op)  in insert_into_bitmap()
2021 		block_group = ctl->private;  in insert_into_bitmap()
2049 		if (entry->offset == offset_to_bitmap(ctl, offset)) {  in insert_into_bitmap()
2050 			bytes_added = add_bytes_to_bitmap(ctl, entry,  in insert_into_bitmap()
2063 	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),  in insert_into_bitmap()
2070 	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);  in insert_into_bitmap()
2083 		add_new_bitmap(ctl, info, offset);  in insert_into_bitmap()
2088 		spin_unlock(&ctl->tree_lock);  in insert_into_bitmap()
2095 				spin_lock(&ctl->tree_lock);  in insert_into_bitmap()
2103 		spin_lock(&ctl->tree_lock);  in insert_into_bitmap()
2121 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,  in try_merge_free_space()  argument
2135 	right_info = tree_search_offset(ctl, offset + bytes, 0, 0);  in try_merge_free_space()
2140 		left_info = tree_search_offset(ctl, offset - 1, 0, 0);  in try_merge_free_space()
2144 			unlink_free_space(ctl, right_info);  in try_merge_free_space()
2146 			__unlink_free_space(ctl, right_info);  in try_merge_free_space()
2155 			unlink_free_space(ctl, left_info);  in try_merge_free_space()
2157 			__unlink_free_space(ctl, left_info);  in try_merge_free_space()
2167 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,  in steal_from_bitmap_to_end()  argument
2175 	const u64 bitmap_offset = offset_to_bitmap(ctl, end);  in steal_from_bitmap_to_end()
2178 	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);  in steal_from_bitmap_to_end()
2182 	i = offset_to_bit(bitmap->offset, ctl->unit, end);  in steal_from_bitmap_to_end()
2186 	bytes = (j - i) * ctl->unit;  in steal_from_bitmap_to_end()
2190 		bitmap_clear_bits(ctl, bitmap, end, bytes);  in steal_from_bitmap_to_end()
2192 		__bitmap_clear_bits(ctl, bitmap, end, bytes);  in steal_from_bitmap_to_end()
2195 		free_bitmap(ctl, bitmap);  in steal_from_bitmap_to_end()
2200 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,  in steal_from_bitmap_to_front()  argument
2211 	bitmap_offset = offset_to_bitmap(ctl, info->offset);  in steal_from_bitmap_to_front()
2216 		bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);  in steal_from_bitmap_to_front()
2219 	bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);  in steal_from_bitmap_to_front()
2223 	i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;  in steal_from_bitmap_to_front()
2235 		bytes = (i + 1) * ctl->unit;  in steal_from_bitmap_to_front()
2237 		bytes = (i - prev_j) * ctl->unit;  in steal_from_bitmap_to_front()
2243 		bitmap_clear_bits(ctl, bitmap, info->offset, bytes);  in steal_from_bitmap_to_front()
2245 		__bitmap_clear_bits(ctl, bitmap, info->offset, bytes);  in steal_from_bitmap_to_front()
2248 		free_bitmap(ctl, bitmap);  in steal_from_bitmap_to_front()
2264 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,  in steal_from_bitmap()  argument
2275 	if (ctl->total_bitmaps > 0) {  in steal_from_bitmap()
2279 		stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);  in steal_from_bitmap()
2280 		if (ctl->total_bitmaps > 0)  in steal_from_bitmap()
2281 			stole_front = steal_from_bitmap_to_front(ctl, info,  in steal_from_bitmap()
2285 			try_merge_free_space(ctl, info, update_stat);  in steal_from_bitmap()
2290 			   struct btrfs_free_space_ctl *ctl,  in __btrfs_add_free_space()  argument
2304 	spin_lock(&ctl->tree_lock);  in __btrfs_add_free_space()
2306 	if (try_merge_free_space(ctl, info, true))  in __btrfs_add_free_space()
2314 	ret = insert_into_bitmap(ctl, info);  in __btrfs_add_free_space()
2328 	steal_from_bitmap(ctl, info, true);  in __btrfs_add_free_space()
2330 	ret = link_free_space(ctl, info);  in __btrfs_add_free_space()
2334 	spin_unlock(&ctl->tree_lock);  in __btrfs_add_free_space()
2347 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_remove_free_space()  local
2352 	spin_lock(&ctl->tree_lock);  in btrfs_remove_free_space()
2359 	info = tree_search_offset(ctl, offset, 0, 0);  in btrfs_remove_free_space()
2365 		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),  in btrfs_remove_free_space()
2380 		unlink_free_space(ctl, info);  in btrfs_remove_free_space()
2387 				ret = link_free_space(ctl, info);  in btrfs_remove_free_space()
2400 			ret = link_free_space(ctl, info);  in btrfs_remove_free_space()
2414 			spin_unlock(&ctl->tree_lock);  in btrfs_remove_free_space()
2423 	ret = remove_from_bitmap(ctl, info, &offset, &bytes);  in btrfs_remove_free_space()
2429 	spin_unlock(&ctl->tree_lock);  in btrfs_remove_free_space()
2438 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_dump_free_space()  local
2443 	for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {  in btrfs_dump_free_space()
2460 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_init_free_space_ctl()  local
2462 	spin_lock_init(&ctl->tree_lock);  in btrfs_init_free_space_ctl()
2463 	ctl->unit = fs_info->sectorsize;  in btrfs_init_free_space_ctl()
2464 	ctl->start = block_group->key.objectid;  in btrfs_init_free_space_ctl()
2465 	ctl->private = block_group;  in btrfs_init_free_space_ctl()
2466 	ctl->op = &free_space_op;  in btrfs_init_free_space_ctl()
2467 	INIT_LIST_HEAD(&ctl->trimming_ranges);  in btrfs_init_free_space_ctl()
2468 	mutex_init(&ctl->cache_writeout_mutex);  in btrfs_init_free_space_ctl()
2475 	ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);  in btrfs_init_free_space_ctl()
2489 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in __btrfs_return_cluster_to_free_space()  local
2512 			try_merge_free_space(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2513 			steal_from_bitmap(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2515 		tree_insert_offset(&ctl->free_space_offset,  in __btrfs_return_cluster_to_free_space()
2527 				struct btrfs_free_space_ctl *ctl)  in __btrfs_remove_free_space_cache_locked()  argument
2532 	while ((node = rb_last(&ctl->free_space_offset)) != NULL) {  in __btrfs_remove_free_space_cache_locked()
2535 			unlink_free_space(ctl, info);  in __btrfs_remove_free_space_cache_locked()
2538 			free_bitmap(ctl, info);  in __btrfs_remove_free_space_cache_locked()
2541 		cond_resched_lock(&ctl->tree_lock);  in __btrfs_remove_free_space_cache_locked()
2545 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)  in __btrfs_remove_free_space_cache()  argument
2547 	spin_lock(&ctl->tree_lock);  in __btrfs_remove_free_space_cache()
2548 	__btrfs_remove_free_space_cache_locked(ctl);  in __btrfs_remove_free_space_cache()
2549 	spin_unlock(&ctl->tree_lock);  in __btrfs_remove_free_space_cache()
2554 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_remove_free_space_cache()  local
2558 	spin_lock(&ctl->tree_lock);  in btrfs_remove_free_space_cache()
2567 		cond_resched_lock(&ctl->tree_lock);  in btrfs_remove_free_space_cache()
2569 	__btrfs_remove_free_space_cache_locked(ctl);  in btrfs_remove_free_space_cache()
2570 	spin_unlock(&ctl->tree_lock);  in btrfs_remove_free_space_cache()
2578 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_find_space_for_alloc()  local
2585 	spin_lock(&ctl->tree_lock);  in btrfs_find_space_for_alloc()
2586 	entry = find_free_space(ctl, &offset, &bytes_search,  in btrfs_find_space_for_alloc()
2593 		bitmap_clear_bits(ctl, entry, offset, bytes);  in btrfs_find_space_for_alloc()
2595 			free_bitmap(ctl, entry);  in btrfs_find_space_for_alloc()
2597 		unlink_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2608 			link_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2611 	spin_unlock(&ctl->tree_lock);  in btrfs_find_space_for_alloc()
2614 		__btrfs_add_free_space(block_group->fs_info, ctl,  in btrfs_find_space_for_alloc()
2631 	struct btrfs_free_space_ctl *ctl;  in btrfs_return_cluster_to_free_space()  local
2650 	ctl = block_group->free_space_ctl;  in btrfs_return_cluster_to_free_space()
2653 	spin_lock(&ctl->tree_lock);  in btrfs_return_cluster_to_free_space()
2655 	spin_unlock(&ctl->tree_lock);  in btrfs_return_cluster_to_free_space()
2668 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_alloc_from_bitmap()  local
2677 	err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);  in btrfs_alloc_from_bitmap()
2685 	__bitmap_clear_bits(ctl, entry, ret, bytes);  in btrfs_alloc_from_bitmap()
2699 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_alloc_from_cluster()  local
2761 	spin_lock(&ctl->tree_lock);  in btrfs_alloc_from_cluster()
2763 	ctl->free_space -= bytes;  in btrfs_alloc_from_cluster()
2765 		ctl->free_extents--;  in btrfs_alloc_from_cluster()
2768 			ctl->total_bitmaps--;  in btrfs_alloc_from_cluster()
2769 			ctl->op->recalc_thresholds(ctl);  in btrfs_alloc_from_cluster()
2774 	spin_unlock(&ctl->tree_lock);  in btrfs_alloc_from_cluster()
2785 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_bitmap_cluster()  local
2796 	i = offset_to_bit(entry->offset, ctl->unit,  in btrfs_bitmap_cluster()
2798 	want_bits = bytes_to_bits(bytes, ctl->unit);  in btrfs_bitmap_cluster()
2799 	min_bits = bytes_to_bits(min_bytes, ctl->unit);  in btrfs_bitmap_cluster()
2825 		entry->max_extent_size = (u64)max_bits * ctl->unit;  in btrfs_bitmap_cluster()
2836 	if (cluster->max_size < found_bits * ctl->unit)  in btrfs_bitmap_cluster()
2837 		cluster->max_size = found_bits * ctl->unit;  in btrfs_bitmap_cluster()
2844 	cluster->window_start = start * ctl->unit + entry->offset;  in btrfs_bitmap_cluster()
2845 	rb_erase(&entry->offset_index, &ctl->free_space_offset);  in btrfs_bitmap_cluster()
2851 				  total_found * ctl->unit, 1);  in btrfs_bitmap_cluster()
2866 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in setup_cluster_no_bitmap()  local
2875 	entry = tree_search_offset(ctl, offset, 0, 1);  in setup_cluster_no_bitmap()
2935 		rb_erase(&entry->offset_index, &ctl->free_space_offset);  in setup_cluster_no_bitmap()
2957 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in setup_cluster_bitmap()  local
2960 	u64 bitmap_offset = offset_to_bitmap(ctl, offset);  in setup_cluster_bitmap()
2962 	if (ctl->total_bitmaps == 0)  in setup_cluster_bitmap()
2973 		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);  in setup_cluster_bitmap()
3007 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in btrfs_find_space_cluster()  local
3030 	spin_lock(&ctl->tree_lock);  in btrfs_find_space_cluster()
3036 	if (ctl->free_space < bytes) {  in btrfs_find_space_cluster()
3037 		spin_unlock(&ctl->tree_lock);  in btrfs_find_space_cluster()
3074 	spin_unlock(&ctl->tree_lock);  in btrfs_find_space_cluster()
3100 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in do_trimming()  local
3119 	mutex_lock(&ctl->cache_writeout_mutex);  in do_trimming()
3122 	mutex_unlock(&ctl->cache_writeout_mutex);  in do_trimming()
3141 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in trim_no_bitmap()  local
3152 		mutex_lock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3153 		spin_lock(&ctl->tree_lock);  in trim_no_bitmap()
3155 		if (ctl->free_space < minlen) {  in trim_no_bitmap()
3156 			spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3157 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3161 		entry = tree_search_offset(ctl, start, 0, 1);  in trim_no_bitmap()
3163 			spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3164 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3172 				spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3173 				mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3181 			spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3182 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3191 			spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3192 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3196 		unlink_free_space(ctl, entry);  in trim_no_bitmap()
3199 		spin_unlock(&ctl->tree_lock);  in trim_no_bitmap()
3202 		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);  in trim_no_bitmap()
3203 		mutex_unlock(&ctl->cache_writeout_mutex);  in trim_no_bitmap()
3226 	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;  in trim_bitmaps()  local
3231 	u64 offset = offset_to_bitmap(ctl, start);  in trim_bitmaps()
3237 		mutex_lock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3238 		spin_lock(&ctl->tree_lock);  in trim_bitmaps()
3240 		if (ctl->free_space < minlen) {  in trim_bitmaps()
3241 			spin_unlock(&ctl->tree_lock);  in trim_bitmaps()
3242 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3246 		entry = tree_search_offset(ctl, offset, 1, 0);  in trim_bitmaps()
3248 			spin_unlock(&ctl->tree_lock);  in trim_bitmaps()
3249 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3255 		ret2 = search_bitmap(ctl, entry, &start, &bytes, false);  in trim_bitmaps()
3257 			spin_unlock(&ctl->tree_lock);  in trim_bitmaps()
3258 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3265 			spin_unlock(&ctl->tree_lock);  in trim_bitmaps()
3266 			mutex_unlock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3270 		bitmap_clear_bits(ctl, entry, start, bytes);  in trim_bitmaps()
3272 			free_bitmap(ctl, entry);  in trim_bitmaps()
3274 		spin_unlock(&ctl->tree_lock);  in trim_bitmaps()
3277 		list_add_tail(&trim_entry.list, &ctl->trimming_ranges);  in trim_bitmaps()
3278 		mutex_unlock(&ctl->cache_writeout_mutex);  in trim_bitmaps()
3286 			offset += BITS_PER_BITMAP * ctl->unit;  in trim_bitmaps()
3289 			if (start >= offset + BITS_PER_BITMAP * ctl->unit)  in trim_bitmaps()
3290 				offset += BITS_PER_BITMAP * ctl->unit;  in trim_bitmaps()
3382 	struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;  in btrfs_find_ino_for_alloc()  local
3386 	spin_lock(&ctl->tree_lock);  in btrfs_find_ino_for_alloc()
3388 	if (RB_EMPTY_ROOT(&ctl->free_space_offset))  in btrfs_find_ino_for_alloc()
3391 	entry = rb_entry(rb_first(&ctl->free_space_offset),  in btrfs_find_ino_for_alloc()
3397 		unlink_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3403 			link_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3409 		ret = search_bitmap(ctl, entry, &offset, &count, true);  in btrfs_find_ino_for_alloc()
3414 		bitmap_clear_bits(ctl, entry, offset, 1);  in btrfs_find_ino_for_alloc()
3416 			free_bitmap(ctl, entry);  in btrfs_find_ino_for_alloc()
3419 	spin_unlock(&ctl->tree_lock);  in btrfs_find_ino_for_alloc()
3458 	struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;  in load_free_ino_cache()  local
3485 	ret = __load_free_space_cache(root, inode, ctl, path, 0);  in load_free_ino_cache()
3504 	struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;  in btrfs_write_out_ino_cache()  local
3513 	ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl, trans);  in btrfs_write_out_ino_cache()
3549 	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;  in test_add_free_space_entry()  local
3563 		spin_lock(&ctl->tree_lock);  in test_add_free_space_entry()
3567 		ret = link_free_space(ctl, info);  in test_add_free_space_entry()
3568 		spin_unlock(&ctl->tree_lock);  in test_add_free_space_entry()
3582 	spin_lock(&ctl->tree_lock);  in test_add_free_space_entry()
3583 	bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),  in test_add_free_space_entry()
3588 		add_new_bitmap(ctl, info, offset);  in test_add_free_space_entry()
3593 	bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);  in test_add_free_space_entry()
3597 	spin_unlock(&ctl->tree_lock);  in test_add_free_space_entry()
3617 	struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;  in test_check_exists()  local
3621 	spin_lock(&ctl->tree_lock);  in test_check_exists()
3622 	info = tree_search_offset(ctl, offset, 0, 0);  in test_check_exists()
3624 		info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),  in test_check_exists()
3637 		bit_bytes = ctl->unit;  in test_check_exists()
3638 		ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);  in test_check_exists()
3690 	spin_unlock(&ctl->tree_lock);  in test_check_exists()