523 	struct btrfs_free_space_entry *entry;  in io_ctl_add_entry()  local
528 	entry = io_ctl->cur;  in io_ctl_add_entry()
529 	entry->offset = cpu_to_le64(offset);  in io_ctl_add_entry()
530 	entry->bytes = cpu_to_le64(bytes);  in io_ctl_add_entry()
531 	entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :  in io_ctl_add_entry()
591 			    struct btrfs_free_space *entry, u8 *type)  in io_ctl_read_entry()  argument
603 	entry->offset = le64_to_cpu(e->offset);  in io_ctl_read_entry()
604 	entry->bytes = le64_to_cpu(e->bytes);  in io_ctl_read_entry()
618 			      struct btrfs_free_space *entry)  in io_ctl_read_bitmap()  argument
626 	memcpy(entry->bitmap, io_ctl->cur, PAGE_CACHE_SIZE);  in io_ctl_read_bitmap()
1096 		struct btrfs_free_space *entry =  in write_bitmap_entries()  local
1099 		ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);  in write_bitmap_entries()
1102 		list_del_init(&entry->list);  in write_bitmap_entries()
1127 		struct btrfs_free_space *entry =  in cleanup_bitmap_list()  local
1129 		list_del_init(&entry->list);  in cleanup_bitmap_list()
1500 	struct btrfs_free_space *entry, *prev = NULL;  in tree_search_offset()  local
1505 			entry = NULL;  in tree_search_offset()
1509 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1510 		prev = entry;  in tree_search_offset()
1512 		if (offset < entry->offset)  in tree_search_offset()
1514 		else if (offset > entry->offset)  in tree_search_offset()
1521 		if (!entry)  in tree_search_offset()
1523 		if (entry->bitmap)  in tree_search_offset()
1524 			return entry;  in tree_search_offset()
1533 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1534 		if (entry->offset != offset)  in tree_search_offset()
1537 		WARN_ON(!entry->bitmap);  in tree_search_offset()
1538 		return entry;  in tree_search_offset()
1539 	} else if (entry) {  in tree_search_offset()
1540 		if (entry->bitmap) {  in tree_search_offset()
1545 			n = rb_prev(&entry->offset_index);  in tree_search_offset()
1551 					entry = prev;  in tree_search_offset()
1554 		return entry;  in tree_search_offset()
1561 	entry = prev;  in tree_search_offset()
1562 	if (entry->offset > offset) {  in tree_search_offset()
1563 		n = rb_prev(&entry->offset_index);  in tree_search_offset()
1565 			entry = rb_entry(n, struct btrfs_free_space,  in tree_search_offset()
1567 			ASSERT(entry->offset <= offset);  in tree_search_offset()
1570 				return entry;  in tree_search_offset()
1576 	if (entry->bitmap) {  in tree_search_offset()
1577 		n = rb_prev(&entry->offset_index);  in tree_search_offset()
1585 		if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)  in tree_search_offset()
1586 			return entry;  in tree_search_offset()
1587 	} else if (entry->offset + entry->bytes > offset)  in tree_search_offset()
1588 		return entry;  in tree_search_offset()
1594 		if (entry->bitmap) {  in tree_search_offset()
1595 			if (entry->offset + BITS_PER_BITMAP *  in tree_search_offset()
1599 			if (entry->offset + entry->bytes > offset)  in tree_search_offset()
1603 		n = rb_next(&entry->offset_index);  in tree_search_offset()
1606 		entry = rb_entry(n, struct btrfs_free_space, offset_index);  in tree_search_offset()
1608 	return entry;  in tree_search_offset()
1775 	struct btrfs_free_space *entry;  in find_free_space()  local
1784 	entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);  in find_free_space()
1785 	if (!entry)  in find_free_space()
1788 	for (node = &entry->offset_index; node; node = rb_next(node)) {  in find_free_space()
1789 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in find_free_space()
1790 		if (entry->bytes < *bytes) {  in find_free_space()
1791 			if (entry->bytes > *max_extent_size)  in find_free_space()
1792 				*max_extent_size = entry->bytes;  in find_free_space()
1800 			tmp = entry->offset - ctl->start + align - 1;  in find_free_space()
1803 			align_off = tmp - entry->offset;  in find_free_space()
1806 			tmp = entry->offset;  in find_free_space()
1809 		if (entry->bytes < *bytes + align_off) {  in find_free_space()
1810 			if (entry->bytes > *max_extent_size)  in find_free_space()
1811 				*max_extent_size = entry->bytes;  in find_free_space()
1815 		if (entry->bitmap) {  in find_free_space()
1818 			ret = search_bitmap(ctl, entry, &tmp, &size);  in find_free_space()
1822 				return entry;  in find_free_space()
1830 		*bytes = entry->bytes - align_off;  in find_free_space()
1831 		return entry;  in find_free_space()
2022 		struct btrfs_free_space *entry;  in insert_into_bitmap()  local
2034 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in insert_into_bitmap()
2035 		if (!entry->bitmap) {  in insert_into_bitmap()
2040 		if (entry->offset == offset_to_bitmap(ctl, offset)) {  in insert_into_bitmap()
2041 			bytes_added = add_bytes_to_bitmap(ctl, entry,  in insert_into_bitmap()
2480 	struct btrfs_free_space *entry;  in __btrfs_return_cluster_to_free_space()  local
2495 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in __btrfs_return_cluster_to_free_space()
2496 		node = rb_next(&entry->offset_index);  in __btrfs_return_cluster_to_free_space()
2497 		rb_erase(&entry->offset_index, &cluster->root);  in __btrfs_return_cluster_to_free_space()
2498 		RB_CLEAR_NODE(&entry->offset_index);  in __btrfs_return_cluster_to_free_space()
2500 		bitmap = (entry->bitmap != NULL);  in __btrfs_return_cluster_to_free_space()
2502 			try_merge_free_space(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2503 			steal_from_bitmap(ctl, entry, false);  in __btrfs_return_cluster_to_free_space()
2506 				   entry->offset, &entry->offset_index, bitmap);  in __btrfs_return_cluster_to_free_space()
2569 	struct btrfs_free_space *entry = NULL;  in btrfs_find_space_for_alloc()  local
2576 	entry = find_free_space(ctl, &offset, &bytes_search,  in btrfs_find_space_for_alloc()
2578 	if (!entry)  in btrfs_find_space_for_alloc()
2582 	if (entry->bitmap) {  in btrfs_find_space_for_alloc()
2583 		bitmap_clear_bits(ctl, entry, offset, bytes);  in btrfs_find_space_for_alloc()
2584 		if (!entry->bytes)  in btrfs_find_space_for_alloc()
2585 			free_bitmap(ctl, entry);  in btrfs_find_space_for_alloc()
2587 		unlink_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2588 		align_gap_len = offset - entry->offset;  in btrfs_find_space_for_alloc()
2589 		align_gap = entry->offset;  in btrfs_find_space_for_alloc()
2591 		entry->offset = offset + bytes;  in btrfs_find_space_for_alloc()
2592 		WARN_ON(entry->bytes < bytes + align_gap_len);  in btrfs_find_space_for_alloc()
2594 		entry->bytes -= bytes + align_gap_len;  in btrfs_find_space_for_alloc()
2595 		if (!entry->bytes)  in btrfs_find_space_for_alloc()
2596 			kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_find_space_for_alloc()
2598 			link_free_space(ctl, entry);  in btrfs_find_space_for_alloc()
2653 				   struct btrfs_free_space *entry,  in btrfs_alloc_from_bitmap()  argument
2666 	err = search_bitmap(ctl, entry, &search_start, &search_bytes);  in btrfs_alloc_from_bitmap()
2674 	__bitmap_clear_bits(ctl, entry, ret, bytes);  in btrfs_alloc_from_bitmap()
2689 	struct btrfs_free_space *entry = NULL;  in btrfs_alloc_from_cluster()  local
2704 	entry = rb_entry(node, struct btrfs_free_space, offset_index);  in btrfs_alloc_from_cluster()
2706 		if (entry->bytes < bytes && entry->bytes > *max_extent_size)  in btrfs_alloc_from_cluster()
2707 			*max_extent_size = entry->bytes;  in btrfs_alloc_from_cluster()
2709 		if (entry->bytes < bytes ||  in btrfs_alloc_from_cluster()
2710 		    (!entry->bitmap && entry->offset < min_start)) {  in btrfs_alloc_from_cluster()
2711 			node = rb_next(&entry->offset_index);  in btrfs_alloc_from_cluster()
2714 			entry = rb_entry(node, struct btrfs_free_space,  in btrfs_alloc_from_cluster()
2719 		if (entry->bitmap) {  in btrfs_alloc_from_cluster()
2721 						      cluster, entry, bytes,  in btrfs_alloc_from_cluster()
2725 				node = rb_next(&entry->offset_index);  in btrfs_alloc_from_cluster()
2728 				entry = rb_entry(node, struct btrfs_free_space,  in btrfs_alloc_from_cluster()
2734 			ret = entry->offset;  in btrfs_alloc_from_cluster()
2736 			entry->offset += bytes;  in btrfs_alloc_from_cluster()
2737 			entry->bytes -= bytes;  in btrfs_alloc_from_cluster()
2740 		if (entry->bytes == 0)  in btrfs_alloc_from_cluster()
2741 			rb_erase(&entry->offset_index, &cluster->root);  in btrfs_alloc_from_cluster()
2753 	if (entry->bytes == 0) {  in btrfs_alloc_from_cluster()
2755 		if (entry->bitmap) {  in btrfs_alloc_from_cluster()
2756 			kfree(entry->bitmap);  in btrfs_alloc_from_cluster()
2760 		kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_alloc_from_cluster()
2769 				struct btrfs_free_space *entry,  in btrfs_bitmap_cluster()  argument
2784 	i = offset_to_bit(entry->offset, ctl->unit,  in btrfs_bitmap_cluster()
2785 			  max_t(u64, offset, entry->offset));  in btrfs_bitmap_cluster()
2791 	for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {  in btrfs_bitmap_cluster()
2792 		next_zero = find_next_zero_bit(entry->bitmap,  in btrfs_bitmap_cluster()
2819 	cluster->window_start = start * ctl->unit + entry->offset;  in btrfs_bitmap_cluster()
2820 	rb_erase(&entry->offset_index, &ctl->free_space_offset);  in btrfs_bitmap_cluster()
2821 	ret = tree_insert_offset(&cluster->root, entry->offset,  in btrfs_bitmap_cluster()
2822 				 &entry->offset_index, 1);  in btrfs_bitmap_cluster()
2843 	struct btrfs_free_space *entry = NULL;  in setup_cluster_no_bitmap()  local
2850 	entry = tree_search_offset(ctl, offset, 0, 1);  in setup_cluster_no_bitmap()
2851 	if (!entry)  in setup_cluster_no_bitmap()
2858 	while (entry->bitmap || entry->bytes < min_bytes) {  in setup_cluster_no_bitmap()
2859 		if (entry->bitmap && list_empty(&entry->list))  in setup_cluster_no_bitmap()
2860 			list_add_tail(&entry->list, bitmaps);  in setup_cluster_no_bitmap()
2861 		node = rb_next(&entry->offset_index);  in setup_cluster_no_bitmap()
2864 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2867 	window_free = entry->bytes;  in setup_cluster_no_bitmap()
2868 	max_extent = entry->bytes;  in setup_cluster_no_bitmap()
2869 	first = entry;  in setup_cluster_no_bitmap()
2870 	last = entry;  in setup_cluster_no_bitmap()
2872 	for (node = rb_next(&entry->offset_index); node;  in setup_cluster_no_bitmap()
2873 	     node = rb_next(&entry->offset_index)) {  in setup_cluster_no_bitmap()
2874 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2876 		if (entry->bitmap) {  in setup_cluster_no_bitmap()
2877 			if (list_empty(&entry->list))  in setup_cluster_no_bitmap()
2878 				list_add_tail(&entry->list, bitmaps);  in setup_cluster_no_bitmap()
2882 		if (entry->bytes < min_bytes)  in setup_cluster_no_bitmap()
2885 		last = entry;  in setup_cluster_no_bitmap()
2886 		window_free += entry->bytes;  in setup_cluster_no_bitmap()
2887 		if (entry->bytes > max_extent)  in setup_cluster_no_bitmap()
2888 			max_extent = entry->bytes;  in setup_cluster_no_bitmap()
2905 		entry = rb_entry(node, struct btrfs_free_space, offset_index);  in setup_cluster_no_bitmap()
2906 		node = rb_next(&entry->offset_index);  in setup_cluster_no_bitmap()
2907 		if (entry->bitmap || entry->bytes < min_bytes)  in setup_cluster_no_bitmap()
2910 		rb_erase(&entry->offset_index, &ctl->free_space_offset);  in setup_cluster_no_bitmap()
2911 		ret = tree_insert_offset(&cluster->root, entry->offset,  in setup_cluster_no_bitmap()
2912 					 &entry->offset_index, 0);  in setup_cluster_no_bitmap()
2913 		total_size += entry->bytes;  in setup_cluster_no_bitmap()
2915 	} while (node && entry != last);  in setup_cluster_no_bitmap()
2933 	struct btrfs_free_space *entry;  in setup_cluster_bitmap()  local
2944 	entry = list_first_entry(bitmaps, struct btrfs_free_space, list);  in setup_cluster_bitmap()
2945 	if (entry->offset != bitmap_offset) {  in setup_cluster_bitmap()
2946 		entry = tree_search_offset(ctl, bitmap_offset, 1, 0);  in setup_cluster_bitmap()
2947 		if (entry && list_empty(&entry->list))  in setup_cluster_bitmap()
2948 			list_add(&entry->list, bitmaps);  in setup_cluster_bitmap()
2951 	list_for_each_entry(entry, bitmaps, list) {  in setup_cluster_bitmap()
2952 		if (entry->bytes < bytes)  in setup_cluster_bitmap()
2954 		ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,  in setup_cluster_bitmap()
2981 	struct btrfs_free_space *entry, *tmp;  in btrfs_find_space_cluster()  local
3034 	list_for_each_entry_safe(entry, tmp, &bitmaps, list)  in btrfs_find_space_cluster()
3035 		list_del_init(&entry->list);  in btrfs_find_space_cluster()
3115 	struct btrfs_free_space *entry;  in trim_no_bitmap()  local
3134 		entry = tree_search_offset(ctl, start, 0, 1);  in trim_no_bitmap()
3135 		if (!entry) {  in trim_no_bitmap()
3142 		while (entry->bitmap) {  in trim_no_bitmap()
3143 			node = rb_next(&entry->offset_index);  in trim_no_bitmap()
3149 			entry = rb_entry(node, struct btrfs_free_space,  in trim_no_bitmap()
3153 		if (entry->offset >= end) {  in trim_no_bitmap()
3159 		extent_start = entry->offset;  in trim_no_bitmap()
3160 		extent_bytes = entry->bytes;  in trim_no_bitmap()
3169 		unlink_free_space(ctl, entry);  in trim_no_bitmap()
3170 		kmem_cache_free(btrfs_free_space_cachep, entry);  in trim_no_bitmap()
3200 	struct btrfs_free_space *entry;  in trim_bitmaps()  local
3219 		entry = tree_search_offset(ctl, offset, 1, 0);  in trim_bitmaps()
3220 		if (!entry) {  in trim_bitmaps()
3228 		ret2 = search_bitmap(ctl, entry, &start, &bytes);  in trim_bitmaps()
3243 		bitmap_clear_bits(ctl, entry, start, bytes);  in trim_bitmaps()
3244 		if (entry->bytes == 0)  in trim_bitmaps()
3245 			free_bitmap(ctl, entry);  in trim_bitmaps()
3346 	struct btrfs_free_space *entry = NULL;  in btrfs_find_ino_for_alloc()  local
3354 	entry = rb_entry(rb_first(&ctl->free_space_offset),  in btrfs_find_ino_for_alloc()
3357 	if (!entry->bitmap) {  in btrfs_find_ino_for_alloc()
3358 		ino = entry->offset;  in btrfs_find_ino_for_alloc()
3360 		unlink_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3361 		entry->offset++;  in btrfs_find_ino_for_alloc()
3362 		entry->bytes--;  in btrfs_find_ino_for_alloc()
3363 		if (!entry->bytes)  in btrfs_find_ino_for_alloc()
3364 			kmem_cache_free(btrfs_free_space_cachep, entry);  in btrfs_find_ino_for_alloc()
3366 			link_free_space(ctl, entry);  in btrfs_find_ino_for_alloc()
3372 		ret = search_bitmap(ctl, entry, &offset, &count);  in btrfs_find_ino_for_alloc()
3377 		bitmap_clear_bits(ctl, entry, offset, 1);  in btrfs_find_ino_for_alloc()
3378 		if (entry->bytes == 0)  in btrfs_find_ino_for_alloc()
3379 			free_bitmap(ctl, entry);  in btrfs_find_ino_for_alloc()