Lines Matching +full:key +full:- +full:1
1 // SPDX-License-Identifier: GPL-2.0
10 #include "disk-io.h"
12 #include "free-space-tree.h"
14 #include "block-group.h"
17 #include "extent-tree.h"
18 #include "root-tree.h"
27 struct btrfs_key key = { in btrfs_free_space_root() local
33 if (btrfs_fs_incompat(block_group->fs_info, EXTENT_TREE_V2)) in btrfs_free_space_root()
34 key.offset = block_group->global_root_id; in btrfs_free_space_root()
35 return btrfs_global_root(block_group->fs_info, &key); in btrfs_free_space_root()
44 if (WARN_ON(cache->length == 0)) in set_free_space_tree_thresholds()
45 btrfs_warn(cache->fs_info, "block group %llu length is zero", in set_free_space_tree_thresholds()
46 cache->start); in set_free_space_tree_thresholds()
52 bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; in set_free_space_tree_thresholds()
53 num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range); in set_free_space_tree_thresholds()
56 cache->bitmap_high_thresh = div_u64(total_bitmap_size, in set_free_space_tree_thresholds()
63 if (cache->bitmap_high_thresh > 100) in set_free_space_tree_thresholds()
64 cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100; in set_free_space_tree_thresholds()
66 cache->bitmap_low_thresh = 0; in set_free_space_tree_thresholds()
75 struct btrfs_key key; in add_new_free_space_info() local
79 key.objectid = block_group->start; in add_new_free_space_info()
80 key.type = BTRFS_FREE_SPACE_INFO_KEY; in add_new_free_space_info()
81 key.offset = block_group->length; in add_new_free_space_info()
83 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info)); in add_new_free_space_info()
87 leaf = path->nodes[0]; in add_new_free_space_info()
88 info = btrfs_item_ptr(leaf, path->slots[0], in add_new_free_space_info()
105 struct btrfs_fs_info *fs_info = block_group->fs_info; in search_free_space_info()
107 struct btrfs_key key; in search_free_space_info() local
110 key.objectid = block_group->start; in search_free_space_info()
111 key.type = BTRFS_FREE_SPACE_INFO_KEY; in search_free_space_info()
112 key.offset = block_group->length; in search_free_space_info()
114 ret = btrfs_search_slot(trans, root, &key, path, 0, cow); in search_free_space_info()
119 block_group->start); in search_free_space_info()
121 return ERR_PTR(-ENOENT); in search_free_space_info()
124 return btrfs_item_ptr(path->nodes[0], path->slots[0], in search_free_space_info()
129 * btrfs_search_slot() but we're looking for the greatest key less than the
130 * passed key.
134 struct btrfs_key *key, struct btrfs_path *p, in btrfs_search_prev_slot() argument
139 ret = btrfs_search_slot(trans, root, key, p, ins_len, cow); in btrfs_search_prev_slot()
145 return -EIO; in btrfs_search_prev_slot()
148 if (p->slots[0] == 0) { in btrfs_search_prev_slot()
150 return -EIO; in btrfs_search_prev_slot()
152 p->slots[0]--; in btrfs_search_prev_slot()
160 return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE); in free_space_bitmap_size()
187 int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE); in le_bitmap_set()
190 while (len - bits_to_set >= 0) { in le_bitmap_set()
192 len -= bits_to_set; in le_bitmap_set()
208 struct btrfs_fs_info *fs_info = trans->fs_info; in convert_free_space_to_bitmaps()
211 struct btrfs_key key, found_key; in convert_free_space_to_bitmaps() local
222 bitmap_size = free_space_bitmap_size(fs_info, block_group->length); in convert_free_space_to_bitmaps()
225 ret = -ENOMEM; in convert_free_space_to_bitmaps()
229 start = block_group->start; in convert_free_space_to_bitmaps()
230 end = block_group->start + block_group->length; in convert_free_space_to_bitmaps()
232 key.objectid = end - 1; in convert_free_space_to_bitmaps()
233 key.type = (u8)-1; in convert_free_space_to_bitmaps()
234 key.offset = (u64)-1; in convert_free_space_to_bitmaps()
237 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in convert_free_space_to_bitmaps()
241 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
243 path->slots[0]++; in convert_free_space_to_bitmaps()
244 while (path->slots[0] > 0) { in convert_free_space_to_bitmaps()
245 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in convert_free_space_to_bitmaps()
248 ASSERT(found_key.objectid == block_group->start); in convert_free_space_to_bitmaps()
249 ASSERT(found_key.offset == block_group->length); in convert_free_space_to_bitmaps()
250 done = 1; in convert_free_space_to_bitmaps()
259 first = div_u64(found_key.objectid - start, in convert_free_space_to_bitmaps()
260 fs_info->sectorsize); in convert_free_space_to_bitmaps()
261 last = div_u64(found_key.objectid + found_key.offset - start, in convert_free_space_to_bitmaps()
262 fs_info->sectorsize); in convert_free_space_to_bitmaps()
263 le_bitmap_set(bitmap, first, last - first); in convert_free_space_to_bitmaps()
267 path->slots[0]--; in convert_free_space_to_bitmaps()
273 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in convert_free_space_to_bitmaps()
279 info = search_free_space_info(trans, block_group, path, 1); in convert_free_space_to_bitmaps()
284 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
294 block_group->start, extent_count, in convert_free_space_to_bitmaps()
297 ret = -EIO; in convert_free_space_to_bitmaps()
302 bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; in convert_free_space_to_bitmaps()
309 extent_size = min(end - i, bitmap_range); in convert_free_space_to_bitmaps()
312 key.objectid = i; in convert_free_space_to_bitmaps()
313 key.type = BTRFS_FREE_SPACE_BITMAP_KEY; in convert_free_space_to_bitmaps()
314 key.offset = extent_size; in convert_free_space_to_bitmaps()
316 ret = btrfs_insert_empty_item(trans, root, path, &key, in convert_free_space_to_bitmaps()
321 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
322 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in convert_free_space_to_bitmaps()
344 struct btrfs_fs_info *fs_info = trans->fs_info; in convert_free_space_to_extents()
347 struct btrfs_key key, found_key; in convert_free_space_to_extents() local
357 bitmap_size = free_space_bitmap_size(fs_info, block_group->length); in convert_free_space_to_extents()
360 ret = -ENOMEM; in convert_free_space_to_extents()
364 start = block_group->start; in convert_free_space_to_extents()
365 end = block_group->start + block_group->length; in convert_free_space_to_extents()
367 key.objectid = end - 1; in convert_free_space_to_extents()
368 key.type = (u8)-1; in convert_free_space_to_extents()
369 key.offset = (u64)-1; in convert_free_space_to_extents()
372 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in convert_free_space_to_extents()
376 leaf = path->nodes[0]; in convert_free_space_to_extents()
378 path->slots[0]++; in convert_free_space_to_extents()
379 while (path->slots[0] > 0) { in convert_free_space_to_extents()
380 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in convert_free_space_to_extents()
383 ASSERT(found_key.objectid == block_group->start); in convert_free_space_to_extents()
384 ASSERT(found_key.offset == block_group->length); in convert_free_space_to_extents()
385 done = 1; in convert_free_space_to_extents()
396 bitmap_pos = div_u64(found_key.objectid - start, in convert_free_space_to_extents()
397 fs_info->sectorsize * in convert_free_space_to_extents()
403 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1); in convert_free_space_to_extents()
408 path->slots[0]--; in convert_free_space_to_extents()
414 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in convert_free_space_to_extents()
420 info = search_free_space_info(trans, block_group, path, 1); in convert_free_space_to_extents()
425 leaf = path->nodes[0]; in convert_free_space_to_extents()
432 nrbits = block_group->length >> block_group->fs_info->sectorsize_bits; in convert_free_space_to_extents()
439 key.objectid = start + start_bit * block_group->fs_info->sectorsize; in convert_free_space_to_extents()
440 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in convert_free_space_to_extents()
441 key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize; in convert_free_space_to_extents()
443 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in convert_free_space_to_extents()
456 block_group->start, extent_count, in convert_free_space_to_extents()
459 ret = -EIO; in convert_free_space_to_extents()
484 info = search_free_space_info(trans, block_group, path, 1); in update_free_space_extent_count()
489 flags = btrfs_free_space_flags(path->nodes[0], info); in update_free_space_extent_count()
490 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); in update_free_space_extent_count()
493 btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count); in update_free_space_extent_count()
497 extent_count > block_group->bitmap_high_thresh) { in update_free_space_extent_count()
500 extent_count < block_group->bitmap_low_thresh) { in update_free_space_extent_count()
513 struct btrfs_key key; in free_space_test_bit() local
517 leaf = path->nodes[0]; in free_space_test_bit()
518 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in free_space_test_bit()
519 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in free_space_test_bit()
521 found_start = key.objectid; in free_space_test_bit()
522 found_end = key.objectid + key.offset; in free_space_test_bit()
525 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in free_space_test_bit()
526 i = div_u64(offset - found_start, in free_space_test_bit()
527 block_group->fs_info->sectorsize); in free_space_test_bit()
536 struct btrfs_fs_info *fs_info = block_group->fs_info; in free_space_set_bits()
538 struct btrfs_key key; in free_space_set_bits() local
543 leaf = path->nodes[0]; in free_space_set_bits()
544 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in free_space_set_bits()
545 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in free_space_set_bits()
547 found_start = key.objectid; in free_space_set_bits()
548 found_end = key.objectid + key.offset; in free_space_set_bits()
555 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in free_space_set_bits()
556 first = (*start - found_start) >> fs_info->sectorsize_bits; in free_space_set_bits()
557 last = (end - found_start) >> fs_info->sectorsize_bits; in free_space_set_bits()
559 extent_buffer_bitmap_set(leaf, ptr, first, last - first); in free_space_set_bits()
561 extent_buffer_bitmap_clear(leaf, ptr, first, last - first); in free_space_set_bits()
564 *size -= end - *start; in free_space_set_bits()
577 struct btrfs_key key; in free_space_next_bitmap() local
579 if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) { in free_space_next_bitmap()
580 p->slots[0]++; in free_space_next_bitmap()
584 btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]); in free_space_next_bitmap()
587 key.objectid += key.offset; in free_space_next_bitmap()
588 key.type = (u8)-1; in free_space_next_bitmap()
589 key.offset = (u64)-1; in free_space_next_bitmap()
591 return btrfs_search_prev_slot(trans, root, &key, p, 0, 1); in free_space_next_bitmap()
595 * If remove is 1, then we are removing free space, thus clearing bits in the
605 struct btrfs_key key; in modify_free_space_bitmap() local
616 if (start > block_group->start) { in modify_free_space_bitmap()
617 u64 prev_block = start - block_group->fs_info->sectorsize; in modify_free_space_bitmap()
619 key.objectid = prev_block; in modify_free_space_bitmap()
620 key.type = (u8)-1; in modify_free_space_bitmap()
621 key.offset = (u64)-1; in modify_free_space_bitmap()
623 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); in modify_free_space_bitmap()
630 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in modify_free_space_bitmap()
631 if (start >= key.objectid + key.offset) { in modify_free_space_bitmap()
637 key.objectid = start; in modify_free_space_bitmap()
638 key.type = (u8)-1; in modify_free_space_bitmap()
639 key.offset = (u64)-1; in modify_free_space_bitmap()
641 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); in modify_free_space_bitmap()
645 prev_bit = -1; in modify_free_space_bitmap()
654 while (1) { in modify_free_space_bitmap()
668 if (end < block_group->start + block_group->length) { in modify_free_space_bitmap()
670 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in modify_free_space_bitmap()
671 if (end >= key.objectid + key.offset) { in modify_free_space_bitmap()
679 next_bit = -1; in modify_free_space_bitmap()
683 new_extents = -1; in modify_free_space_bitmap()
684 if (prev_bit == 1) { in modify_free_space_bitmap()
688 if (next_bit == 1) { in modify_free_space_bitmap()
693 new_extents = 1; in modify_free_space_bitmap()
694 if (prev_bit == 1) { in modify_free_space_bitmap()
696 new_extents--; in modify_free_space_bitmap()
698 if (next_bit == 1) { in modify_free_space_bitmap()
700 new_extents--; in modify_free_space_bitmap()
718 struct btrfs_key key; in remove_free_space_extent() local
721 int new_extents = -1; in remove_free_space_extent()
724 key.objectid = start; in remove_free_space_extent()
725 key.type = (u8)-1; in remove_free_space_extent()
726 key.offset = (u64)-1; in remove_free_space_extent()
728 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in remove_free_space_extent()
732 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in remove_free_space_extent()
734 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); in remove_free_space_extent()
736 found_start = key.objectid; in remove_free_space_extent()
737 found_end = key.objectid + key.offset; in remove_free_space_extent()
744 * 1. We're using the whole extent: delete the key we found and in remove_free_space_extent()
747 * the key we found and insert a new key representing the leftover at in remove_free_space_extent()
749 * 3. We are using part of the extent ending at the end: delete the key in remove_free_space_extent()
750 * we found and insert a new key representing the leftover at the in remove_free_space_extent()
752 * 4. We are using part of the extent in the middle: delete the key we in remove_free_space_extent()
759 /* Delete the existing key (cases 1-4). */ in remove_free_space_extent()
764 /* Add a key for leftovers at the beginning (cases 3 and 4). */ in remove_free_space_extent()
766 key.objectid = found_start; in remove_free_space_extent()
767 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in remove_free_space_extent()
768 key.offset = start - found_start; in remove_free_space_extent()
771 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in remove_free_space_extent()
777 /* Add a key for leftovers at the end (cases 2 and 4). */ in remove_free_space_extent()
779 key.objectid = end; in remove_free_space_extent()
780 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in remove_free_space_extent()
781 key.offset = found_end - end; in remove_free_space_extent()
784 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in remove_free_space_extent()
807 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in __remove_from_free_space_tree()
816 flags = btrfs_free_space_flags(path->nodes[0], info); in __remove_from_free_space_tree()
821 start, size, 1); in __remove_from_free_space_tree()
835 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in remove_from_free_space_tree()
840 ret = -ENOMEM; in remove_from_free_space_tree()
844 block_group = btrfs_lookup_block_group(trans->fs_info, start); in remove_from_free_space_tree()
847 ret = -ENOENT; in remove_from_free_space_tree()
851 mutex_lock(&block_group->free_space_lock); in remove_from_free_space_tree()
854 mutex_unlock(&block_group->free_space_lock); in remove_from_free_space_tree()
870 struct btrfs_key key, new_key; in add_free_space_extent() local
873 int new_extents = 1; in add_free_space_extent()
880 * 1. The new extent does not have any immediate neighbors to merge in add_free_space_extent()
881 * with: add the new key and increment the free space extent count. We in add_free_space_extent()
884 * previous key and insert a new key combining both of them. There is no in add_free_space_extent()
887 * key and insert a new key combining both of them. There is no net in add_free_space_extent()
890 * of the keys and insert a new key combining all of them. Where we used in add_free_space_extent()
899 if (start == block_group->start) in add_free_space_extent()
901 key.objectid = start - 1; in add_free_space_extent()
902 key.type = (u8)-1; in add_free_space_extent()
903 key.offset = (u64)-1; in add_free_space_extent()
905 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in add_free_space_extent()
909 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in add_free_space_extent()
911 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { in add_free_space_extent()
912 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); in add_free_space_extent()
917 found_start = key.objectid; in add_free_space_extent()
918 found_end = key.objectid + key.offset; in add_free_space_extent()
919 ASSERT(found_start >= block_group->start && in add_free_space_extent()
920 found_end > block_group->start); in add_free_space_extent()
924 * Delete the neighbor on the left and absorb it into the new key (cases in add_free_space_extent()
932 new_key.offset += key.offset; in add_free_space_extent()
933 new_extents--; in add_free_space_extent()
939 if (end == block_group->start + block_group->length) in add_free_space_extent()
941 key.objectid = end; in add_free_space_extent()
942 key.type = (u8)-1; in add_free_space_extent()
943 key.offset = (u64)-1; in add_free_space_extent()
945 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in add_free_space_extent()
949 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in add_free_space_extent()
951 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { in add_free_space_extent()
952 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); in add_free_space_extent()
957 found_start = key.objectid; in add_free_space_extent()
958 found_end = key.objectid + key.offset; in add_free_space_extent()
959 ASSERT(found_start >= block_group->start && in add_free_space_extent()
960 found_end > block_group->start); in add_free_space_extent()
965 * Delete the neighbor on the right and absorb it into the new key in add_free_space_extent()
972 new_key.offset += key.offset; in add_free_space_extent()
973 new_extents--; in add_free_space_extent()
978 /* Insert the new key (cases 1-4). */ in add_free_space_extent()
1000 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in __add_to_free_space_tree()
1009 flags = btrfs_free_space_flags(path->nodes[0], info); in __add_to_free_space_tree()
1028 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in add_to_free_space_tree()
1033 ret = -ENOMEM; in add_to_free_space_tree()
1037 block_group = btrfs_lookup_block_group(trans->fs_info, start); in add_to_free_space_tree()
1040 ret = -ENOENT; in add_to_free_space_tree()
1044 mutex_lock(&block_group->free_space_lock); in add_to_free_space_tree()
1046 mutex_unlock(&block_group->free_space_lock); in add_to_free_space_tree()
1066 struct btrfs_key key; in populate_free_space_tree() local
1072 return -ENOMEM; in populate_free_space_tree()
1073 path->reada = READA_FORWARD; in populate_free_space_tree()
1078 return -ENOMEM; in populate_free_space_tree()
1085 mutex_lock(&block_group->free_space_lock); in populate_free_space_tree()
1094 key.objectid = block_group->start; in populate_free_space_tree()
1095 key.type = BTRFS_EXTENT_ITEM_KEY; in populate_free_space_tree()
1096 key.offset = 0; in populate_free_space_tree()
1098 extent_root = btrfs_extent_root(trans->fs_info, key.objectid); in populate_free_space_tree()
1099 ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0); in populate_free_space_tree()
1104 start = block_group->start; in populate_free_space_tree()
1105 end = block_group->start + block_group->length; in populate_free_space_tree()
1106 while (1) { in populate_free_space_tree()
1107 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in populate_free_space_tree()
1109 if (key.type == BTRFS_EXTENT_ITEM_KEY || in populate_free_space_tree()
1110 key.type == BTRFS_METADATA_ITEM_KEY) { in populate_free_space_tree()
1111 if (key.objectid >= end) in populate_free_space_tree()
1114 if (start < key.objectid) { in populate_free_space_tree()
1118 key.objectid - in populate_free_space_tree()
1123 start = key.objectid; in populate_free_space_tree()
1124 if (key.type == BTRFS_METADATA_ITEM_KEY) in populate_free_space_tree()
1125 start += trans->fs_info->nodesize; in populate_free_space_tree()
1127 start += key.offset; in populate_free_space_tree()
1128 } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { in populate_free_space_tree()
1129 if (key.objectid != block_group->start) in populate_free_space_tree()
1141 start, end - start); in populate_free_space_tree()
1148 mutex_unlock(&block_group->free_space_lock); in populate_free_space_tree()
1158 struct btrfs_root *tree_root = fs_info->tree_root; in btrfs_create_free_space_tree()
1168 set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_create_free_space_tree()
1169 set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_create_free_space_tree()
1186 node = rb_first_cached(&fs_info->block_group_cache_tree); in btrfs_create_free_space_tree()
1201 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_create_free_space_tree()
1208 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_create_free_space_tree()
1212 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_create_free_space_tree()
1213 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_create_free_space_tree()
1221 struct btrfs_key key; in clear_free_space_tree() local
1227 return -ENOMEM; in clear_free_space_tree()
1229 key.objectid = 0; in clear_free_space_tree()
1230 key.type = 0; in clear_free_space_tree()
1231 key.offset = 0; in clear_free_space_tree()
1233 while (1) { in clear_free_space_tree()
1234 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); in clear_free_space_tree()
1238 nr = btrfs_header_nritems(path->nodes[0]); in clear_free_space_tree()
1242 path->slots[0] = 0; in clear_free_space_tree()
1259 struct btrfs_root *tree_root = fs_info->tree_root; in btrfs_delete_free_space_tree()
1260 struct btrfs_key key = { in btrfs_delete_free_space_tree() local
1265 struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); in btrfs_delete_free_space_tree()
1282 ret = btrfs_del_root(trans, &free_space_root->root_key); in btrfs_delete_free_space_tree()
1291 spin_lock(&fs_info->trans_lock); in btrfs_delete_free_space_tree()
1292 list_del(&free_space_root->dirty_list); in btrfs_delete_free_space_tree()
1293 spin_unlock(&fs_info->trans_lock); in btrfs_delete_free_space_tree()
1295 btrfs_tree_lock(free_space_root->node); in btrfs_delete_free_space_tree()
1296 btrfs_clear_buffer_dirty(trans, free_space_root->node); in btrfs_delete_free_space_tree()
1297 btrfs_tree_unlock(free_space_root->node); in btrfs_delete_free_space_tree()
1299 free_space_root->node, 0, 1); in btrfs_delete_free_space_tree()
1313 struct btrfs_key key = { in btrfs_rebuild_free_space_tree() local
1318 struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); in btrfs_rebuild_free_space_tree()
1322 trans = btrfs_start_transaction(free_space_root, 1); in btrfs_rebuild_free_space_tree()
1326 set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1327 set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1336 node = rb_first_cached(&fs_info->block_group_cache_tree); in btrfs_rebuild_free_space_tree()
1350 trans = btrfs_start_transaction(free_space_root, 1); in btrfs_rebuild_free_space_tree()
1359 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1362 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1372 clear_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags); in __add_block_group_free_space()
1379 block_group->start, in __add_block_group_free_space()
1380 block_group->length); in __add_block_group_free_space()
1386 struct btrfs_fs_info *fs_info = trans->fs_info; in add_block_group_free_space()
1393 mutex_lock(&block_group->free_space_lock); in add_block_group_free_space()
1394 if (!test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) in add_block_group_free_space()
1399 ret = -ENOMEM; in add_block_group_free_space()
1407 mutex_unlock(&block_group->free_space_lock); in add_block_group_free_space()
1418 struct btrfs_key key, found_key; in remove_block_group_free_space() local
1424 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in remove_block_group_free_space()
1427 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in remove_block_group_free_space()
1434 ret = -ENOMEM; in remove_block_group_free_space()
1438 start = block_group->start; in remove_block_group_free_space()
1439 end = block_group->start + block_group->length; in remove_block_group_free_space()
1441 key.objectid = end - 1; in remove_block_group_free_space()
1442 key.type = (u8)-1; in remove_block_group_free_space()
1443 key.offset = (u64)-1; in remove_block_group_free_space()
1446 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in remove_block_group_free_space()
1450 leaf = path->nodes[0]; in remove_block_group_free_space()
1452 path->slots[0]++; in remove_block_group_free_space()
1453 while (path->slots[0] > 0) { in remove_block_group_free_space()
1454 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in remove_block_group_free_space()
1457 ASSERT(found_key.objectid == block_group->start); in remove_block_group_free_space()
1458 ASSERT(found_key.offset == block_group->length); in remove_block_group_free_space()
1459 done = 1; in remove_block_group_free_space()
1461 path->slots[0]--; in remove_block_group_free_space()
1469 path->slots[0]--; in remove_block_group_free_space()
1475 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in remove_block_group_free_space()
1496 struct btrfs_key key; in load_free_space_bitmaps() local
1505 block_group = caching_ctl->block_group; in load_free_space_bitmaps()
1506 fs_info = block_group->fs_info; in load_free_space_bitmaps()
1509 end = block_group->start + block_group->length; in load_free_space_bitmaps()
1511 while (1) { in load_free_space_bitmaps()
1518 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in load_free_space_bitmaps()
1520 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) in load_free_space_bitmaps()
1523 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in load_free_space_bitmaps()
1524 ASSERT(key.objectid < end && key.objectid + key.offset <= end); in load_free_space_bitmaps()
1526 offset = key.objectid; in load_free_space_bitmaps()
1527 while (offset < key.objectid + key.offset) { in load_free_space_bitmaps()
1529 if (prev_bit == 0 && bit == 1) { in load_free_space_bitmaps()
1531 } else if (prev_bit == 1 && bit == 0) { in load_free_space_bitmaps()
1543 wake_up(&caching_ctl->wait); in load_free_space_bitmaps()
1548 offset += fs_info->sectorsize; in load_free_space_bitmaps()
1551 if (prev_bit == 1) { in load_free_space_bitmaps()
1561 block_group->start, extent_count, in load_free_space_bitmaps()
1564 ret = -EIO; in load_free_space_bitmaps()
1580 struct btrfs_key key; in load_free_space_extents() local
1586 block_group = caching_ctl->block_group; in load_free_space_extents()
1587 fs_info = block_group->fs_info; in load_free_space_extents()
1590 end = block_group->start + block_group->length; in load_free_space_extents()
1592 while (1) { in load_free_space_extents()
1601 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in load_free_space_extents()
1603 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) in load_free_space_extents()
1606 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); in load_free_space_extents()
1607 ASSERT(key.objectid < end && key.objectid + key.offset <= end); in load_free_space_extents()
1609 ret = btrfs_add_new_free_space(block_group, key.objectid, in load_free_space_extents()
1610 key.objectid + key.offset, in load_free_space_extents()
1617 wake_up(&caching_ctl->wait); in load_free_space_extents()
1625 block_group->start, extent_count, in load_free_space_extents()
1628 ret = -EIO; in load_free_space_extents()
1645 block_group = caching_ctl->block_group; in load_free_space_tree()
1649 return -ENOMEM; in load_free_space_tree()
1655 path->skip_locking = 1; in load_free_space_tree()
1656 path->search_commit_root = 1; in load_free_space_tree()
1657 path->reada = READA_FORWARD; in load_free_space_tree()
1664 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); in load_free_space_tree()
1665 flags = btrfs_free_space_flags(path->nodes[0], info); in load_free_space_tree()