521 	struct btrfs_free_space_entry *entry;  in io_ctl_add_entry()  local
526 	entry = io_ctl->cur;  in io_ctl_add_entry()
527 	entry->offset = cpu_to_le64(offset);  in io_ctl_add_entry()
528 	entry->bytes = cpu_to_le64(bytes);  in io_ctl_add_entry()
529 	entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :  in io_ctl_add_entry()
589 			    struct btrfs_free_space *entry, u8 *type)  in io_ctl_read_entry()  argument
601 	entry->offset = le64_to_cpu(e->offset);  in io_ctl_read_entry()
602 	entry->bytes = le64_to_cpu(e->bytes);  in io_ctl_read_entry()
616 			      struct btrfs_free_space *entry)  in io_ctl_read_bitmap()  argument
624 	memcpy(entry->bitmap, io_ctl->cur, PAGE_CACHE_SIZE);  in io_ctl_read_bitmap()
1094 		struct btrfs_free_space *entry =  in write_bitmap_entries()  local
1097 		ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);  in write_bitmap_entries()
1100 		list_del_init(&entry->list);  in write_bitmap_entries()
1125 		struct btrfs_free_space *entry =  in cleanup_bitmap_list()  local
1127 		list_del_init(&entry->list);  in cleanup_bitmap_list()
1498 	struct btrfs_free_space *entry, *prev = NULL;  in tree_search_offset()  local
1503 			entry = NULL;  in tree_search_offset()
1507 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1508 		prev = entry;  in tree_search_offset()
1510 		if (offset < entry->offset)  in tree_search_offset()
1512 		else if (offset > entry->offset)  in tree_search_offset()
1519 		if (!entry)  in tree_search_offset()
1521 		if (entry->bitmap)  in tree_search_offset()
1522 			return entry;  in tree_search_offset()
1531 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1532 		if (entry->offset != offset)  in tree_search_offset()
1535 		WARN_ON(!entry->bitmap);  in tree_search_offset()
1536 		return entry;  in tree_search_offset()
1537 	} else if (entry) {  in tree_search_offset()
1538 		if (entry->bitmap) {  in tree_search_offset()
1543 			n = rb_prev(&entry->offset_index);  in tree_search_offset()
1549 					entry = prev;  in tree_search_offset()
1552 		return entry;  in tree_search_offset()
1559 	entry = prev;  in tree_search_offset()
1560 	if (entry->offset > offset) {  in tree_search_offset()
1561 		n = rb_prev(&entry->offset_index);  in tree_search_offset()
1563 			entry = rb_entry(n, struct btrfs_free_space,  in tree_search_offset()
1565 			ASSERT(entry->offset <= offset);  in tree_search_offset()
1568 				return entry;  in tree_search_offset()
1574 	if (entry->bitmap) {  in tree_search_offset()
1575 		n = rb_prev(&entry->offset_index);  in tree_search_offset()
1583 		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)  in tree_search_offset()
1584 			return entry;  in tree_search_offset()
1585 	} else if (entry->offset + entry->bytes > offset)  in tree_search_offset()
1586 		return entry;  in tree_search_offset()
1592 		if (entry->bitmap) {  in tree_search_offset()
1593 			if (entry->offset + BITS_PER_BITMAP *  in tree_search_offset()
1597 			if (entry->offset + entry->bytes > offset)  in tree_search_offset()
1601 		n = rb_next(&entry->offset_index);  in tree_search_offset()
1604 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1606 	return entry;  in tree_search_offset()
1789 	struct btrfs_free_space *entry;  in find_free_space()  local
1798 	entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);  in find_free_space()
1799 	if (!entry)  in find_free_space()
1802 	for (node = &entry->offset_index; node; node = rb_next(node)) {  in find_free_space()
1803 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in find_free_space()
1804 		if (entry->bytes < *bytes) {  in find_free_space()
1805 			if (entry->bytes > *max_extent_size)  in find_free_space()
1806 				*max_extent_size = entry->bytes;  in find_free_space()
1814 			tmp = entry->offset - ctl->start + align - 1;  in find_free_space()
1817 			align_off = tmp - entry->offset;  in find_free_space()
1820 			tmp = entry->offset;  in find_free_space()
1823 		if (entry->bytes < *bytes + align_off) {  in find_free_space()
1824 			if (entry->bytes > *max_extent_size)  in find_free_space()
1825 				*max_extent_size = entry->bytes;  in find_free_space()
1829 		if (entry->bitmap) {  in find_free_space()
1832 			ret = search_bitmap(ctl, entry, &tmp, &size, true);  in find_free_space()
1836 				return entry;  in find_free_space()
1844 		*bytes = entry->bytes - align_off;  in find_free_space()
1845 		return entry;  in find_free_space()
2050 		struct btrfs_free_space *entry;  in insert_into_bitmap()  local
2062 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in insert_into_bitmap()
2063 		if (!entry->bitmap) {  in insert_into_bitmap()
2068 		if (entry->offset == offset_to_bitmap(ctl, offset)) {  in insert_into_bitmap()
2069 			bytes_added = add_bytes_to_bitmap(ctl, entry,  in insert_into_bitmap()
2508 	struct btrfs_free_space *entry;  in __btrfs_return_cluster_to_free_space()  local
2523 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in __btrfs_return_cluster_to_free_space()
2524 		node = rb_next(&entry->offset_index);  in __btrfs_return_cluster_to_free_space()
2525 		rb_erase(&entry->offset_index, &cluster->root);  in __btrfs_return_cluster_to_free_space()
2526 		RB_CLEAR_NODE(&entry->offset_index);  in __btrfs_return_cluster_to_free_space()
2528 		bitmap = (entry->bitmap != NULL);  in __btrfs_return_cluster_to_free_space()
2530 			try_merge_free_space(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2531 			steal_from_bitmap(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2534 				   entry->offset, &entry->offset_index, bitmap);  in __btrfs_return_cluster_to_free_space()
2597 	struct btrfs_free_space *entry = NULL;  in btrfs_find_space_for_alloc()  local
2604 	entry = find_free_space(ctl, &offset, &bytes_search,  in btrfs_find_space_for_alloc()
2606 	if (!entry)  in btrfs_find_space_for_alloc()
2610 	if (entry->bitmap) {  in btrfs_find_space_for_alloc()
2611 		bitmap_clear_bits(ctl, entry, offset, bytes);  in btrfs_find_space_for_alloc()
2612 		if (!entry->bytes)  in btrfs_find_space_for_alloc()
2613 			free_bitmap(ctl, entry);  in btrfs_find_space_for_alloc()
2615 		unlink_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2616 		align_gap_len = offset - entry->offset;  in btrfs_find_space_for_alloc()
2617 		align_gap = entry->offset;  in btrfs_find_space_for_alloc()
2619 		entry->offset = offset + bytes;  in btrfs_find_space_for_alloc()
2620 		WARN_ON(entry->bytes < bytes + align_gap_len);  in btrfs_find_space_for_alloc()
2622 		entry->bytes -= bytes + align_gap_len;  in btrfs_find_space_for_alloc()
2623 		if (!entry->bytes)  in btrfs_find_space_for_alloc()
2624 			kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_find_space_for_alloc()
2626 			link_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2681 				   struct btrfs_free_space *entry,  in btrfs_alloc_from_bitmap()  argument
2694 	err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);  in btrfs_alloc_from_bitmap()
2702 	__bitmap_clear_bits(ctl, entry, ret, bytes);  in btrfs_alloc_from_bitmap()
2717 	struct btrfs_free_space *entry = NULL;  in btrfs_alloc_from_cluster()  local
2732 	entry = rb_entry(node, struct btrfs_free_space, offset_index);  in btrfs_alloc_from_cluster()
2734 		if (entry->bytes < bytes && entry->bytes > *max_extent_size)  in btrfs_alloc_from_cluster()
2735 			*max_extent_size = entry->bytes;  in btrfs_alloc_from_cluster()
2737 		if (entry->bytes < bytes ||  in btrfs_alloc_from_cluster()
2738 		    (!entry->bitmap && entry->offset < min_start)) {  in btrfs_alloc_from_cluster()
2739 			node = rb_next(&entry->offset_index);  in btrfs_alloc_from_cluster()
2742 			entry = rb_entry(node, struct btrfs_free_space,  in btrfs_alloc_from_cluster()
2747 		if (entry->bitmap) {  in btrfs_alloc_from_cluster()
2749 						      cluster, entry, bytes,  in btrfs_alloc_from_cluster()
2753 				node = rb_next(&entry->offset_index);  in btrfs_alloc_from_cluster()
2756 				entry = rb_entry(node, struct btrfs_free_space,  in btrfs_alloc_from_cluster()
2762 			ret = entry->offset;  in btrfs_alloc_from_cluster()
2764 			entry->offset += bytes;  in btrfs_alloc_from_cluster()
2765 			entry->bytes -= bytes;  in btrfs_alloc_from_cluster()
2768 		if (entry->bytes == 0)  in btrfs_alloc_from_cluster()
2769 			rb_erase(&entry->offset_index, &cluster->root);  in btrfs_alloc_from_cluster()
2781 	if (entry->bytes == 0) {  in btrfs_alloc_from_cluster()
2783 		if (entry->bitmap) {  in btrfs_alloc_from_cluster()
2784 			kfree(entry->bitmap);  in btrfs_alloc_from_cluster()
2788 		kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_alloc_from_cluster()
2797 				struct btrfs_free_space *entry,  in btrfs_bitmap_cluster()  argument
2813 	i = offset_to_bit(entry->offset, ctl->unit,  in btrfs_bitmap_cluster()
2814 			  max_t(u64, offset, entry->offset));  in btrfs_bitmap_cluster()
2822 	if (entry->max_extent_size &&  in btrfs_bitmap_cluster()
2823 	    entry->max_extent_size < cont1_bytes)  in btrfs_bitmap_cluster()
2827 	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {  in btrfs_bitmap_cluster()
2828 		next_zero = find_next_zero_bit(entry->bitmap,  in btrfs_bitmap_cluster()
2842 		entry->max_extent_size = (u64)max_bits * ctl->unit;  in btrfs_bitmap_cluster()
2861 	cluster->window_start = start * ctl->unit + entry->offset;  in btrfs_bitmap_cluster()
2862 	rb_erase(&entry->offset_index, &ctl->free_space_offset);  in btrfs_bitmap_cluster()
2863 	ret = tree_insert_offset(&cluster->root, entry->offset,  in btrfs_bitmap_cluster()
2864 				 &entry->offset_index, 1);  in btrfs_bitmap_cluster()
2885 	struct btrfs_free_space *entry = NULL;  in setup_cluster_no_bitmap()  local
2892 	entry = tree_search_offset(ctl, offset, 0, 1);  in setup_cluster_no_bitmap()
2893 	if (!entry)  in setup_cluster_no_bitmap()
2900 	while (entry->bitmap || entry->bytes < min_bytes) {  in setup_cluster_no_bitmap()
2901 		if (entry->bitmap && list_empty(&entry->list))  in setup_cluster_no_bitmap()
2902 			list_add_tail(&entry->list, bitmaps);  in setup_cluster_no_bitmap()
2903 		node = rb_next(&entry->offset_index);  in setup_cluster_no_bitmap()
2906 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2909 	window_free = entry->bytes;  in setup_cluster_no_bitmap()
2910 	max_extent = entry->bytes;  in setup_cluster_no_bitmap()
2911 	first = entry;  in setup_cluster_no_bitmap()
2912 	last = entry;  in setup_cluster_no_bitmap()
2914 	for (node = rb_next(&entry->offset_index); node;  in setup_cluster_no_bitmap()
2915 	     node = rb_next(&entry->offset_index)) {  in setup_cluster_no_bitmap()
2916 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2918 		if (entry->bitmap) {  in setup_cluster_no_bitmap()
2919 			if (list_empty(&entry->list))  in setup_cluster_no_bitmap()
2920 				list_add_tail(&entry->list, bitmaps);  in setup_cluster_no_bitmap()
2924 		if (entry->bytes < min_bytes)  in setup_cluster_no_bitmap()
2927 		last = entry;  in setup_cluster_no_bitmap()
2928 		window_free += entry->bytes;  in setup_cluster_no_bitmap()
2929 		if (entry->bytes > max_extent)  in setup_cluster_no_bitmap()
2930 			max_extent = entry->bytes;  in setup_cluster_no_bitmap()
2947 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2948 		node = rb_next(&entry->offset_index);  in setup_cluster_no_bitmap()
2949 		if (entry->bitmap || entry->bytes < min_bytes)  in setup_cluster_no_bitmap()
2952 		rb_erase(&entry->offset_index, &ctl->free_space_offset);  in setup_cluster_no_bitmap()
2953 		ret = tree_insert_offset(&cluster->root, entry->offset,  in setup_cluster_no_bitmap()
2954 					 &entry->offset_index, 0);  in setup_cluster_no_bitmap()
2955 		total_size += entry->bytes;  in setup_cluster_no_bitmap()
2957 	} while (node && entry != last);  in setup_cluster_no_bitmap()
2975 	struct btrfs_free_space *entry = NULL;  in setup_cluster_bitmap()  local
2987 		entry = list_first_entry(bitmaps, struct btrfs_free_space, list);  in setup_cluster_bitmap()
2989 	if (!entry || entry->offset != bitmap_offset) {  in setup_cluster_bitmap()
2990 		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);  in setup_cluster_bitmap()
2991 		if (entry && list_empty(&entry->list))  in setup_cluster_bitmap()
2992 			list_add(&entry->list, bitmaps);  in setup_cluster_bitmap()
2995 	list_for_each_entry(entry, bitmaps, list) {  in setup_cluster_bitmap()
2996 		if (entry->bytes < bytes)  in setup_cluster_bitmap()
2998 		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,  in setup_cluster_bitmap()
3025 	struct btrfs_free_space *entry, *tmp;  in btrfs_find_space_cluster()  local
3078 	list_for_each_entry_safe(entry, tmp, &bitmaps, list)  in btrfs_find_space_cluster()
3079 		list_del_init(&entry->list);  in btrfs_find_space_cluster()
3160 	struct btrfs_free_space *entry;  in trim_no_bitmap()  local
3179 		entry = tree_search_offset(ctl, start, 0, 1);  in trim_no_bitmap()
3180 		if (!entry) {  in trim_no_bitmap()
3187 		while (entry->bitmap) {  in trim_no_bitmap()
3188 			node = rb_next(&entry->offset_index);  in trim_no_bitmap()
3194 			entry = rb_entry(node, struct btrfs_free_space,  in trim_no_bitmap()
3198 		if (entry->offset >= end) {  in trim_no_bitmap()
3204 		extent_start = entry->offset;  in trim_no_bitmap()
3205 		extent_bytes = entry->bytes;  in trim_no_bitmap()
3214 		unlink_free_space(ctl, entry);  in trim_no_bitmap()
3215 		kmem_cache_free(btrfs_free_space_cachep, entry);  in trim_no_bitmap()
3245 	struct btrfs_free_space *entry;  in trim_bitmaps()  local
3264 		entry = tree_search_offset(ctl, offset, 1, 0);  in trim_bitmaps()
3265 		if (!entry) {  in trim_bitmaps()
3273 		ret2 = search_bitmap(ctl, entry, &start, &bytes, false);  in trim_bitmaps()
3288 		bitmap_clear_bits(ctl, entry, start, bytes);  in trim_bitmaps()
3289 		if (entry->bytes == 0)  in trim_bitmaps()
3290 			free_bitmap(ctl, entry);  in trim_bitmaps()
3400 	struct btrfs_free_space *entry = NULL;  in btrfs_find_ino_for_alloc()  local
3408 	entry = rb_entry(rb_first(&ctl->free_space_offset),  in btrfs_find_ino_for_alloc()
3411 	if (!entry->bitmap) {  in btrfs_find_ino_for_alloc()
3412 		ino = entry->offset;  in btrfs_find_ino_for_alloc()
3414 		unlink_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3415 		entry->offset++;  in btrfs_find_ino_for_alloc()
3416 		entry->bytes--;  in btrfs_find_ino_for_alloc()
3417 		if (!entry->bytes)  in btrfs_find_ino_for_alloc()
3418 			kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_find_ino_for_alloc()
3420 			link_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3426 		ret = search_bitmap(ctl, entry, &offset, &count, true);  in btrfs_find_ino_for_alloc()
3431 		bitmap_clear_bits(ctl, entry, offset, 1);  in btrfs_find_ino_for_alloc()
3432 		if (entry->bytes == 0)  in btrfs_find_ino_for_alloc()
3433 			free_bitmap(ctl, entry);  in btrfs_find_ino_for_alloc()