29 	num_bitmaps = div_u64(cache->key.offset + bitmap_range - 1,  in set_free_space_tree_thresholds()
52 	struct btrfs_key key;  in add_new_free_space_info()  local
56 	key.objectid = block_group->key.objectid;  in add_new_free_space_info()
57 	key.type = BTRFS_FREE_SPACE_INFO_KEY;  in add_new_free_space_info()
58 	key.offset = block_group->key.offset;  in add_new_free_space_info()
60 	ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));  in add_new_free_space_info()
84 	struct btrfs_key key;  in search_free_space_info()  local
87 	key.objectid = block_group->key.objectid;  in search_free_space_info()
88 	key.type = BTRFS_FREE_SPACE_INFO_KEY;  in search_free_space_info()
89 	key.offset = block_group->key.offset;  in search_free_space_info()
91 	ret = btrfs_search_slot(trans, root, &key, path, 0, cow);  in search_free_space_info()
96 			   block_group->key.objectid);  in search_free_space_info()
111 				  struct btrfs_key *key, struct btrfs_path *p,  in btrfs_search_prev_slot()  argument
116 	ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);  in btrfs_search_prev_slot()
186 	struct btrfs_key key, found_key;  in convert_free_space_to_bitmaps()  local
197 	bitmap_size = free_space_bitmap_size(block_group->key.offset,  in convert_free_space_to_bitmaps()
205 	start = block_group->key.objectid;  in convert_free_space_to_bitmaps()
206 	end = block_group->key.objectid + block_group->key.offset;  in convert_free_space_to_bitmaps()
208 	key.objectid = end - 1;  in convert_free_space_to_bitmaps()
209 	key.type = (u8)-1;  in convert_free_space_to_bitmaps()
210 	key.offset = (u64)-1;  in convert_free_space_to_bitmaps()
213 		ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in convert_free_space_to_bitmaps()
224 				ASSERT(found_key.objectid == block_group->key.objectid);  in convert_free_space_to_bitmaps()
225 				ASSERT(found_key.offset == block_group->key.offset);  in convert_free_space_to_bitmaps()
271 			  block_group->key.objectid, extent_count,  in convert_free_space_to_bitmaps()
290 		key.objectid = i;  in convert_free_space_to_bitmaps()
291 		key.type = BTRFS_FREE_SPACE_BITMAP_KEY;  in convert_free_space_to_bitmaps()
292 		key.offset = extent_size;  in convert_free_space_to_bitmaps()
294 		ret = btrfs_insert_empty_item(trans, root, path, &key,  in convert_free_space_to_bitmaps()
325 	struct btrfs_key key, found_key;  in convert_free_space_to_extents()  local
335 	bitmap_size = free_space_bitmap_size(block_group->key.offset,  in convert_free_space_to_extents()
343 	start = block_group->key.objectid;  in convert_free_space_to_extents()
344 	end = block_group->key.objectid + block_group->key.offset;  in convert_free_space_to_extents()
346 	key.objectid = end - 1;  in convert_free_space_to_extents()
347 	key.type = (u8)-1;  in convert_free_space_to_extents()
348 	key.offset = (u64)-1;  in convert_free_space_to_extents()
351 		ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in convert_free_space_to_extents()
362 				ASSERT(found_key.objectid == block_group->key.objectid);  in convert_free_space_to_extents()
363 				ASSERT(found_key.offset == block_group->key.offset);  in convert_free_space_to_extents()
412 	nrbits = div_u64(block_group->key.offset, block_group->fs_info->sectorsize);  in convert_free_space_to_extents()
419 		key.objectid = start + start_bit * block_group->fs_info->sectorsize;  in convert_free_space_to_extents()
420 		key.type = BTRFS_FREE_SPACE_EXTENT_KEY;  in convert_free_space_to_extents()
421 		key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize;  in convert_free_space_to_extents()
423 		ret = btrfs_insert_empty_item(trans, root, path, &key, 0);  in convert_free_space_to_extents()
436 			  block_group->key.objectid, extent_count,  in convert_free_space_to_extents()
494 	struct btrfs_key key;  in free_space_test_bit()  local
499 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);  in free_space_test_bit()
500 	ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);  in free_space_test_bit()
502 	found_start = key.objectid;  in free_space_test_bit()
503 	found_end = key.objectid + key.offset;  in free_space_test_bit()
518 	struct btrfs_key key;  in free_space_set_bits()  local
524 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);  in free_space_set_bits()
525 	ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);  in free_space_set_bits()
527 	found_start = key.objectid;  in free_space_set_bits()
528 	found_end = key.objectid + key.offset;  in free_space_set_bits()
557 	struct btrfs_key key;  in free_space_next_bitmap()  local
564 	btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);  in free_space_next_bitmap()
567 	key.objectid += key.offset;  in free_space_next_bitmap()
568 	key.type = (u8)-1;  in free_space_next_bitmap()
569 	key.offset = (u64)-1;  in free_space_next_bitmap()
571 	return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);  in free_space_next_bitmap()
585 	struct btrfs_key key;  in modify_free_space_bitmap()  local
596 	if (start > block_group->key.objectid) {  in modify_free_space_bitmap()
599 		key.objectid = prev_block;  in modify_free_space_bitmap()
600 		key.type = (u8)-1;  in modify_free_space_bitmap()
601 		key.offset = (u64)-1;  in modify_free_space_bitmap()
603 		ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);  in modify_free_space_bitmap()
610 		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in modify_free_space_bitmap()
611 		if (start >= key.objectid + key.offset) {  in modify_free_space_bitmap()
617 		key.objectid = start;  in modify_free_space_bitmap()
618 		key.type = (u8)-1;  in modify_free_space_bitmap()
619 		key.offset = (u64)-1;  in modify_free_space_bitmap()
621 		ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);  in modify_free_space_bitmap()
648 	if (end < block_group->key.objectid + block_group->key.offset) {  in modify_free_space_bitmap()
650 		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in modify_free_space_bitmap()
651 		if (end >= key.objectid + key.offset) {  in modify_free_space_bitmap()
698 	struct btrfs_key key;  in remove_free_space_extent()  local
704 	key.objectid = start;  in remove_free_space_extent()
705 	key.type = (u8)-1;  in remove_free_space_extent()
706 	key.offset = (u64)-1;  in remove_free_space_extent()
708 	ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in remove_free_space_extent()
712 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in remove_free_space_extent()
714 	ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);  in remove_free_space_extent()
716 	found_start = key.objectid;  in remove_free_space_extent()
717 	found_end = key.objectid + key.offset;  in remove_free_space_extent()
746 		key.objectid = found_start;  in remove_free_space_extent()
747 		key.type = BTRFS_FREE_SPACE_EXTENT_KEY;  in remove_free_space_extent()
748 		key.offset = start - found_start;  in remove_free_space_extent()
751 		ret = btrfs_insert_empty_item(trans, root, path, &key, 0);  in remove_free_space_extent()
759 		key.objectid = end;  in remove_free_space_extent()
760 		key.type = BTRFS_FREE_SPACE_EXTENT_KEY;  in remove_free_space_extent()
761 		key.offset = found_end - end;  in remove_free_space_extent()
764 		ret = btrfs_insert_empty_item(trans, root, path, &key, 0);  in remove_free_space_extent()
850 	struct btrfs_key key, new_key;  in add_free_space_extent()  local
879 	if (start == block_group->key.objectid)  in add_free_space_extent()
881 	key.objectid = start - 1;  in add_free_space_extent()
882 	key.type = (u8)-1;  in add_free_space_extent()
883 	key.offset = (u64)-1;  in add_free_space_extent()
885 	ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in add_free_space_extent()
889 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in add_free_space_extent()
891 	if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {  in add_free_space_extent()
892 		ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);  in add_free_space_extent()
897 	found_start = key.objectid;  in add_free_space_extent()
898 	found_end = key.objectid + key.offset;  in add_free_space_extent()
899 	ASSERT(found_start >= block_group->key.objectid &&  in add_free_space_extent()
900 	       found_end > block_group->key.objectid);  in add_free_space_extent()
912 		new_key.offset += key.offset;  in add_free_space_extent()
919 	if (end == block_group->key.objectid + block_group->key.offset)  in add_free_space_extent()
921 	key.objectid = end;  in add_free_space_extent()
922 	key.type = (u8)-1;  in add_free_space_extent()
923 	key.offset = (u64)-1;  in add_free_space_extent()
925 	ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in add_free_space_extent()
929 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in add_free_space_extent()
931 	if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {  in add_free_space_extent()
932 		ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);  in add_free_space_extent()
937 	found_start = key.objectid;  in add_free_space_extent()
938 	found_end = key.objectid + key.offset;  in add_free_space_extent()
939 	ASSERT(found_start >= block_group->key.objectid &&  in add_free_space_extent()
940 	       found_end > block_group->key.objectid);  in add_free_space_extent()
952 		new_key.offset += key.offset;  in add_free_space_extent()
1046 	struct btrfs_key key;  in populate_free_space_tree()  local
1074 	key.objectid = block_group->key.objectid;  in populate_free_space_tree()
1075 	key.type = BTRFS_EXTENT_ITEM_KEY;  in populate_free_space_tree()
1076 	key.offset = 0;  in populate_free_space_tree()
1078 	ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);  in populate_free_space_tree()
1083 	start = block_group->key.objectid;  in populate_free_space_tree()
1084 	end = block_group->key.objectid + block_group->key.offset;  in populate_free_space_tree()
1086 		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in populate_free_space_tree()
1088 		if (key.type == BTRFS_EXTENT_ITEM_KEY ||  in populate_free_space_tree()
1089 		    key.type == BTRFS_METADATA_ITEM_KEY) {  in populate_free_space_tree()
1090 			if (key.objectid >= end)  in populate_free_space_tree()
1093 			if (start < key.objectid) {  in populate_free_space_tree()
1097 							       key.objectid -  in populate_free_space_tree()
1102 			start = key.objectid;  in populate_free_space_tree()
1103 			if (key.type == BTRFS_METADATA_ITEM_KEY)  in populate_free_space_tree()
1106 				start += key.offset;  in populate_free_space_tree()
1107 		} else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {  in populate_free_space_tree()
1108 			if (key.objectid != block_group->key.objectid)  in populate_free_space_tree()
1183 	struct btrfs_key key;  in clear_free_space_tree()  local
1193 	key.objectid = 0;  in clear_free_space_tree()
1194 	key.type = 0;  in clear_free_space_tree()
1195 	key.offset = 0;  in clear_free_space_tree()
1198 		ret = btrfs_search_slot(trans, root, &key, path, -1, 1);  in clear_free_space_tree()
1276 					block_group->key.objectid,  in __add_block_group_free_space()
1277 					block_group->key.offset);  in __add_block_group_free_space()
1315 	struct btrfs_key key, found_key;  in remove_block_group_free_space()  local
1335 	start = block_group->key.objectid;  in remove_block_group_free_space()
1336 	end = block_group->key.objectid + block_group->key.offset;  in remove_block_group_free_space()
1338 	key.objectid = end - 1;  in remove_block_group_free_space()
1339 	key.type = (u8)-1;  in remove_block_group_free_space()
1340 	key.offset = (u64)-1;  in remove_block_group_free_space()
1343 		ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);  in remove_block_group_free_space()
1354 				ASSERT(found_key.objectid == block_group->key.objectid);  in remove_block_group_free_space()
1355 				ASSERT(found_key.offset == block_group->key.offset);  in remove_block_group_free_space()
1393 	struct btrfs_key key;  in load_free_space_bitmaps()  local
1406 	end = block_group->key.objectid + block_group->key.offset;  in load_free_space_bitmaps()
1415 		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in load_free_space_bitmaps()
1417 		if (key.type == BTRFS_FREE_SPACE_INFO_KEY)  in load_free_space_bitmaps()
1420 		ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);  in load_free_space_bitmaps()
1421 		ASSERT(key.objectid < end && key.objectid + key.offset <= end);  in load_free_space_bitmaps()
1423 		caching_ctl->progress = key.objectid;  in load_free_space_bitmaps()
1425 		offset = key.objectid;  in load_free_space_bitmaps()
1426 		while (offset < key.objectid + key.offset) {  in load_free_space_bitmaps()
1453 			  block_group->key.objectid, extent_count,  in load_free_space_bitmaps()
1474 	struct btrfs_key key;  in load_free_space_extents()  local
1484 	end = block_group->key.objectid + block_group->key.offset;  in load_free_space_extents()
1493 		btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);  in load_free_space_extents()
1495 		if (key.type == BTRFS_FREE_SPACE_INFO_KEY)  in load_free_space_extents()
1498 		ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);  in load_free_space_extents()
1499 		ASSERT(key.objectid < end && key.objectid + key.offset <= end);  in load_free_space_extents()
1501 		caching_ctl->progress = key.objectid;  in load_free_space_extents()
1503 		total_found += add_new_free_space(block_group, key.objectid,  in load_free_space_extents()
1504 						  key.objectid + key.offset);  in load_free_space_extents()
1515 			  block_group->key.objectid, extent_count,  in load_free_space_extents()