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()
106 struct btrfs_fs_info *fs_info = block_group->fs_info; in search_free_space_info()
108 struct btrfs_key key; in search_free_space_info() local
111 key.objectid = block_group->start; in search_free_space_info()
112 key.type = BTRFS_FREE_SPACE_INFO_KEY; in search_free_space_info()
113 key.offset = block_group->length; in search_free_space_info()
115 ret = btrfs_search_slot(trans, root, &key, path, 0, cow); in search_free_space_info()
120 block_group->start); in search_free_space_info()
122 return ERR_PTR(-ENOENT); in search_free_space_info()
125 return btrfs_item_ptr(path->nodes[0], path->slots[0], in search_free_space_info()
130 * btrfs_search_slot() but we're looking for the greatest key less than the
131 * passed key.
135 struct btrfs_key *key, struct btrfs_path *p, in btrfs_search_prev_slot() argument
140 ret = btrfs_search_slot(trans, root, key, p, ins_len, cow); in btrfs_search_prev_slot()
146 return -EIO; in btrfs_search_prev_slot()
149 if (p->slots[0] == 0) { in btrfs_search_prev_slot()
151 return -EIO; in btrfs_search_prev_slot()
153 p->slots[0]--; in btrfs_search_prev_slot()
161 return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE); in free_space_bitmap_size()
188 int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE); in le_bitmap_set()
191 while (len - bits_to_set >= 0) { in le_bitmap_set()
193 len -= bits_to_set; in le_bitmap_set()
209 struct btrfs_fs_info *fs_info = trans->fs_info; in convert_free_space_to_bitmaps()
212 struct btrfs_key key, found_key; in convert_free_space_to_bitmaps() local
223 bitmap_size = free_space_bitmap_size(fs_info, block_group->length); in convert_free_space_to_bitmaps()
226 ret = -ENOMEM; in convert_free_space_to_bitmaps()
230 start = block_group->start; in convert_free_space_to_bitmaps()
231 end = block_group->start + block_group->length; in convert_free_space_to_bitmaps()
233 key.objectid = end - 1; in convert_free_space_to_bitmaps()
234 key.type = (u8)-1; in convert_free_space_to_bitmaps()
235 key.offset = (u64)-1; in convert_free_space_to_bitmaps()
238 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in convert_free_space_to_bitmaps()
242 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
244 path->slots[0]++; in convert_free_space_to_bitmaps()
245 while (path->slots[0] > 0) { in convert_free_space_to_bitmaps()
246 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in convert_free_space_to_bitmaps()
249 ASSERT(found_key.objectid == block_group->start); in convert_free_space_to_bitmaps()
250 ASSERT(found_key.offset == block_group->length); in convert_free_space_to_bitmaps()
251 done = 1; in convert_free_space_to_bitmaps()
260 first = div_u64(found_key.objectid - start, in convert_free_space_to_bitmaps()
261 fs_info->sectorsize); in convert_free_space_to_bitmaps()
262 last = div_u64(found_key.objectid + found_key.offset - start, in convert_free_space_to_bitmaps()
263 fs_info->sectorsize); in convert_free_space_to_bitmaps()
264 le_bitmap_set(bitmap, first, last - first); in convert_free_space_to_bitmaps()
268 path->slots[0]--; in convert_free_space_to_bitmaps()
274 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in convert_free_space_to_bitmaps()
280 info = search_free_space_info(trans, block_group, path, 1); in convert_free_space_to_bitmaps()
285 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
296 block_group->start, extent_count, in convert_free_space_to_bitmaps()
299 ret = -EIO; in convert_free_space_to_bitmaps()
304 bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; in convert_free_space_to_bitmaps()
311 extent_size = min(end - i, bitmap_range); in convert_free_space_to_bitmaps()
314 key.objectid = i; in convert_free_space_to_bitmaps()
315 key.type = BTRFS_FREE_SPACE_BITMAP_KEY; in convert_free_space_to_bitmaps()
316 key.offset = extent_size; in convert_free_space_to_bitmaps()
318 ret = btrfs_insert_empty_item(trans, root, path, &key, in convert_free_space_to_bitmaps()
323 leaf = path->nodes[0]; in convert_free_space_to_bitmaps()
324 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in convert_free_space_to_bitmaps()
347 struct btrfs_fs_info *fs_info = trans->fs_info; in convert_free_space_to_extents()
350 struct btrfs_key key, found_key; in convert_free_space_to_extents() local
360 bitmap_size = free_space_bitmap_size(fs_info, block_group->length); in convert_free_space_to_extents()
363 ret = -ENOMEM; in convert_free_space_to_extents()
367 start = block_group->start; in convert_free_space_to_extents()
368 end = block_group->start + block_group->length; in convert_free_space_to_extents()
370 key.objectid = end - 1; in convert_free_space_to_extents()
371 key.type = (u8)-1; in convert_free_space_to_extents()
372 key.offset = (u64)-1; in convert_free_space_to_extents()
375 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in convert_free_space_to_extents()
379 leaf = path->nodes[0]; in convert_free_space_to_extents()
381 path->slots[0]++; in convert_free_space_to_extents()
382 while (path->slots[0] > 0) { in convert_free_space_to_extents()
383 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in convert_free_space_to_extents()
386 ASSERT(found_key.objectid == block_group->start); in convert_free_space_to_extents()
387 ASSERT(found_key.offset == block_group->length); in convert_free_space_to_extents()
388 done = 1; in convert_free_space_to_extents()
399 bitmap_pos = div_u64(found_key.objectid - start, in convert_free_space_to_extents()
400 fs_info->sectorsize * in convert_free_space_to_extents()
406 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1); in convert_free_space_to_extents()
411 path->slots[0]--; in convert_free_space_to_extents()
417 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in convert_free_space_to_extents()
423 info = search_free_space_info(trans, block_group, path, 1); in convert_free_space_to_extents()
428 leaf = path->nodes[0]; in convert_free_space_to_extents()
436 nrbits = block_group->length >> block_group->fs_info->sectorsize_bits; in convert_free_space_to_extents()
443 key.objectid = start + start_bit * block_group->fs_info->sectorsize; in convert_free_space_to_extents()
444 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in convert_free_space_to_extents()
445 key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize; in convert_free_space_to_extents()
447 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in convert_free_space_to_extents()
460 block_group->start, extent_count, in convert_free_space_to_extents()
463 ret = -EIO; in convert_free_space_to_extents()
488 info = search_free_space_info(trans, block_group, path, 1); in update_free_space_extent_count()
493 flags = btrfs_free_space_flags(path->nodes[0], info); in update_free_space_extent_count()
494 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); in update_free_space_extent_count()
497 btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count); in update_free_space_extent_count()
498 btrfs_mark_buffer_dirty(trans, path->nodes[0]); in update_free_space_extent_count()
502 extent_count > block_group->bitmap_high_thresh) { in update_free_space_extent_count()
505 extent_count < block_group->bitmap_low_thresh) { in update_free_space_extent_count()
518 struct btrfs_key key; in free_space_test_bit() local
522 leaf = path->nodes[0]; in free_space_test_bit()
523 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in free_space_test_bit()
524 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in free_space_test_bit()
526 found_start = key.objectid; in free_space_test_bit()
527 found_end = key.objectid + key.offset; in free_space_test_bit()
530 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in free_space_test_bit()
531 i = div_u64(offset - found_start, in free_space_test_bit()
532 block_group->fs_info->sectorsize); in free_space_test_bit()
541 struct btrfs_fs_info *fs_info = block_group->fs_info; in free_space_set_bits()
543 struct btrfs_key key; in free_space_set_bits() local
548 leaf = path->nodes[0]; in free_space_set_bits()
549 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); in free_space_set_bits()
550 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in free_space_set_bits()
552 found_start = key.objectid; in free_space_set_bits()
553 found_end = key.objectid + key.offset; in free_space_set_bits()
560 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); in free_space_set_bits()
561 first = (*start - found_start) >> fs_info->sectorsize_bits; in free_space_set_bits()
562 last = (end - found_start) >> fs_info->sectorsize_bits; in free_space_set_bits()
564 extent_buffer_bitmap_set(leaf, ptr, first, last - first); in free_space_set_bits()
566 extent_buffer_bitmap_clear(leaf, ptr, first, last - first); in free_space_set_bits()
569 *size -= end - *start; in free_space_set_bits()
582 struct btrfs_key key; in free_space_next_bitmap() local
584 if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) { in free_space_next_bitmap()
585 p->slots[0]++; in free_space_next_bitmap()
589 btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]); in free_space_next_bitmap()
592 key.objectid += key.offset; in free_space_next_bitmap()
593 key.type = (u8)-1; in free_space_next_bitmap()
594 key.offset = (u64)-1; in free_space_next_bitmap()
596 return btrfs_search_prev_slot(trans, root, &key, p, 0, 1); in free_space_next_bitmap()
600 * If remove is 1, then we are removing free space, thus clearing bits in the
610 struct btrfs_key key; in modify_free_space_bitmap() local
621 if (start > block_group->start) { in modify_free_space_bitmap()
622 u64 prev_block = start - block_group->fs_info->sectorsize; in modify_free_space_bitmap()
624 key.objectid = prev_block; in modify_free_space_bitmap()
625 key.type = (u8)-1; in modify_free_space_bitmap()
626 key.offset = (u64)-1; in modify_free_space_bitmap()
628 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); in modify_free_space_bitmap()
635 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in modify_free_space_bitmap()
636 if (start >= key.objectid + key.offset) { in modify_free_space_bitmap()
642 key.objectid = start; in modify_free_space_bitmap()
643 key.type = (u8)-1; in modify_free_space_bitmap()
644 key.offset = (u64)-1; in modify_free_space_bitmap()
646 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); in modify_free_space_bitmap()
650 prev_bit = -1; in modify_free_space_bitmap()
659 while (1) { in modify_free_space_bitmap()
673 if (end < block_group->start + block_group->length) { in modify_free_space_bitmap()
675 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in modify_free_space_bitmap()
676 if (end >= key.objectid + key.offset) { in modify_free_space_bitmap()
684 next_bit = -1; in modify_free_space_bitmap()
688 new_extents = -1; in modify_free_space_bitmap()
689 if (prev_bit == 1) { in modify_free_space_bitmap()
693 if (next_bit == 1) { in modify_free_space_bitmap()
698 new_extents = 1; in modify_free_space_bitmap()
699 if (prev_bit == 1) { in modify_free_space_bitmap()
701 new_extents--; in modify_free_space_bitmap()
703 if (next_bit == 1) { in modify_free_space_bitmap()
705 new_extents--; in modify_free_space_bitmap()
723 struct btrfs_key key; in remove_free_space_extent() local
726 int new_extents = -1; in remove_free_space_extent()
729 key.objectid = start; in remove_free_space_extent()
730 key.type = (u8)-1; in remove_free_space_extent()
731 key.offset = (u64)-1; in remove_free_space_extent()
733 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in remove_free_space_extent()
737 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in remove_free_space_extent()
739 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); in remove_free_space_extent()
741 found_start = key.objectid; in remove_free_space_extent()
742 found_end = key.objectid + key.offset; in remove_free_space_extent()
749 * 1. We're using the whole extent: delete the key we found and in remove_free_space_extent()
752 * the key we found and insert a new key representing the leftover at in remove_free_space_extent()
754 * 3. We are using part of the extent ending at the end: delete the key in remove_free_space_extent()
755 * we found and insert a new key representing the leftover at the in remove_free_space_extent()
757 * 4. We are using part of the extent in the middle: delete the key we in remove_free_space_extent()
764 /* Delete the existing key (cases 1-4). */ in remove_free_space_extent()
769 /* Add a key for leftovers at the beginning (cases 3 and 4). */ in remove_free_space_extent()
771 key.objectid = found_start; in remove_free_space_extent()
772 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in remove_free_space_extent()
773 key.offset = start - found_start; in remove_free_space_extent()
776 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in remove_free_space_extent()
782 /* Add a key for leftovers at the end (cases 2 and 4). */ in remove_free_space_extent()
784 key.objectid = end; in remove_free_space_extent()
785 key.type = BTRFS_FREE_SPACE_EXTENT_KEY; in remove_free_space_extent()
786 key.offset = found_end - end; in remove_free_space_extent()
789 ret = btrfs_insert_empty_item(trans, root, path, &key, 0); in remove_free_space_extent()
812 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in __remove_from_free_space_tree()
821 flags = btrfs_free_space_flags(path->nodes[0], info); in __remove_from_free_space_tree()
826 start, size, 1); in __remove_from_free_space_tree()
840 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in remove_from_free_space_tree()
845 ret = -ENOMEM; in remove_from_free_space_tree()
849 block_group = btrfs_lookup_block_group(trans->fs_info, start); in remove_from_free_space_tree()
852 ret = -ENOENT; in remove_from_free_space_tree()
856 mutex_lock(&block_group->free_space_lock); in remove_from_free_space_tree()
859 mutex_unlock(&block_group->free_space_lock); in remove_from_free_space_tree()
875 struct btrfs_key key, new_key; in add_free_space_extent() local
878 int new_extents = 1; in add_free_space_extent()
885 * 1. The new extent does not have any immediate neighbors to merge in add_free_space_extent()
886 * with: add the new key and increment the free space extent count. We in add_free_space_extent()
889 * previous key and insert a new key combining both of them. There is no in add_free_space_extent()
892 * key and insert a new key combining both of them. There is no net in add_free_space_extent()
895 * of the keys and insert a new key combining all of them. Where we used in add_free_space_extent()
904 if (start == block_group->start) in add_free_space_extent()
906 key.objectid = start - 1; in add_free_space_extent()
907 key.type = (u8)-1; in add_free_space_extent()
908 key.offset = (u64)-1; in add_free_space_extent()
910 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in add_free_space_extent()
914 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in add_free_space_extent()
916 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { in add_free_space_extent()
917 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); in add_free_space_extent()
922 found_start = key.objectid; in add_free_space_extent()
923 found_end = key.objectid + key.offset; in add_free_space_extent()
924 ASSERT(found_start >= block_group->start && in add_free_space_extent()
925 found_end > block_group->start); in add_free_space_extent()
929 * Delete the neighbor on the left and absorb it into the new key (cases in add_free_space_extent()
937 new_key.offset += key.offset; in add_free_space_extent()
938 new_extents--; in add_free_space_extent()
944 if (end == block_group->start + block_group->length) in add_free_space_extent()
946 key.objectid = end; in add_free_space_extent()
947 key.type = (u8)-1; in add_free_space_extent()
948 key.offset = (u64)-1; in add_free_space_extent()
950 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in add_free_space_extent()
954 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in add_free_space_extent()
956 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { in add_free_space_extent()
957 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); in add_free_space_extent()
962 found_start = key.objectid; in add_free_space_extent()
963 found_end = key.objectid + key.offset; in add_free_space_extent()
964 ASSERT(found_start >= block_group->start && in add_free_space_extent()
965 found_end > block_group->start); in add_free_space_extent()
970 * Delete the neighbor on the right and absorb it into the new key in add_free_space_extent()
977 new_key.offset += key.offset; in add_free_space_extent()
978 new_extents--; in add_free_space_extent()
983 /* Insert the new key (cases 1-4). */ in add_free_space_extent()
1005 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in __add_to_free_space_tree()
1014 flags = btrfs_free_space_flags(path->nodes[0], info); in __add_to_free_space_tree()
1033 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in add_to_free_space_tree()
1038 ret = -ENOMEM; in add_to_free_space_tree()
1042 block_group = btrfs_lookup_block_group(trans->fs_info, start); in add_to_free_space_tree()
1045 ret = -ENOENT; in add_to_free_space_tree()
1049 mutex_lock(&block_group->free_space_lock); in add_to_free_space_tree()
1051 mutex_unlock(&block_group->free_space_lock); in add_to_free_space_tree()
1071 struct btrfs_key key; in populate_free_space_tree() local
1077 return -ENOMEM; in populate_free_space_tree()
1078 path->reada = READA_FORWARD; in populate_free_space_tree()
1083 return -ENOMEM; in populate_free_space_tree()
1090 mutex_lock(&block_group->free_space_lock); in populate_free_space_tree()
1099 key.objectid = block_group->start; in populate_free_space_tree()
1100 key.type = BTRFS_EXTENT_ITEM_KEY; in populate_free_space_tree()
1101 key.offset = 0; in populate_free_space_tree()
1103 extent_root = btrfs_extent_root(trans->fs_info, key.objectid); in populate_free_space_tree()
1104 ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0); in populate_free_space_tree()
1109 start = block_group->start; in populate_free_space_tree()
1110 end = block_group->start + block_group->length; in populate_free_space_tree()
1111 while (1) { in populate_free_space_tree()
1112 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in populate_free_space_tree()
1114 if (key.type == BTRFS_EXTENT_ITEM_KEY || in populate_free_space_tree()
1115 key.type == BTRFS_METADATA_ITEM_KEY) { in populate_free_space_tree()
1116 if (key.objectid >= end) in populate_free_space_tree()
1119 if (start < key.objectid) { in populate_free_space_tree()
1123 key.objectid - in populate_free_space_tree()
1128 start = key.objectid; in populate_free_space_tree()
1129 if (key.type == BTRFS_METADATA_ITEM_KEY) in populate_free_space_tree()
1130 start += trans->fs_info->nodesize; in populate_free_space_tree()
1132 start += key.offset; in populate_free_space_tree()
1133 } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { in populate_free_space_tree()
1134 if (key.objectid != block_group->start) in populate_free_space_tree()
1146 start, end - start); in populate_free_space_tree()
1153 mutex_unlock(&block_group->free_space_lock); in populate_free_space_tree()
1163 struct btrfs_root *tree_root = fs_info->tree_root; in btrfs_create_free_space_tree()
1173 set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_create_free_space_tree()
1174 set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_create_free_space_tree()
1191 node = rb_first_cached(&fs_info->block_group_cache_tree); in btrfs_create_free_space_tree()
1206 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()
1217 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_create_free_space_tree()
1218 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_create_free_space_tree()
1226 struct btrfs_key key; in clear_free_space_tree() local
1232 return -ENOMEM; in clear_free_space_tree()
1234 key.objectid = 0; in clear_free_space_tree()
1235 key.type = 0; in clear_free_space_tree()
1236 key.offset = 0; in clear_free_space_tree()
1238 while (1) { in clear_free_space_tree()
1239 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); in clear_free_space_tree()
1243 nr = btrfs_header_nritems(path->nodes[0]); in clear_free_space_tree()
1247 path->slots[0] = 0; in clear_free_space_tree()
1264 struct btrfs_root *tree_root = fs_info->tree_root; in btrfs_delete_free_space_tree()
1265 struct btrfs_key key = { in btrfs_delete_free_space_tree() local
1270 struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); in btrfs_delete_free_space_tree()
1287 ret = btrfs_del_root(trans, &free_space_root->root_key); in btrfs_delete_free_space_tree()
1296 spin_lock(&fs_info->trans_lock); in btrfs_delete_free_space_tree()
1297 list_del(&free_space_root->dirty_list); in btrfs_delete_free_space_tree()
1298 spin_unlock(&fs_info->trans_lock); in btrfs_delete_free_space_tree()
1300 btrfs_tree_lock(free_space_root->node); in btrfs_delete_free_space_tree()
1301 btrfs_clear_buffer_dirty(trans, free_space_root->node); in btrfs_delete_free_space_tree()
1302 btrfs_tree_unlock(free_space_root->node); in btrfs_delete_free_space_tree()
1304 free_space_root->node, 0, 1); in btrfs_delete_free_space_tree()
1318 struct btrfs_key key = { in btrfs_rebuild_free_space_tree() local
1323 struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); in btrfs_rebuild_free_space_tree()
1327 trans = btrfs_start_transaction(free_space_root, 1); in btrfs_rebuild_free_space_tree()
1331 set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1332 set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1341 node = rb_first_cached(&fs_info->block_group_cache_tree); in btrfs_rebuild_free_space_tree()
1358 clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1361 clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); in btrfs_rebuild_free_space_tree()
1371 clear_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags); in __add_block_group_free_space()
1378 block_group->start, in __add_block_group_free_space()
1379 block_group->length); in __add_block_group_free_space()
1385 struct btrfs_fs_info *fs_info = trans->fs_info; in add_block_group_free_space()
1392 mutex_lock(&block_group->free_space_lock); in add_block_group_free_space()
1393 if (!test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) in add_block_group_free_space()
1398 ret = -ENOMEM; in add_block_group_free_space()
1406 mutex_unlock(&block_group->free_space_lock); in add_block_group_free_space()
1417 struct btrfs_key key, found_key; in remove_block_group_free_space() local
1423 if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) in remove_block_group_free_space()
1426 if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { in remove_block_group_free_space()
1433 ret = -ENOMEM; in remove_block_group_free_space()
1437 start = block_group->start; in remove_block_group_free_space()
1438 end = block_group->start + block_group->length; in remove_block_group_free_space()
1440 key.objectid = end - 1; in remove_block_group_free_space()
1441 key.type = (u8)-1; in remove_block_group_free_space()
1442 key.offset = (u64)-1; in remove_block_group_free_space()
1445 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); in remove_block_group_free_space()
1449 leaf = path->nodes[0]; in remove_block_group_free_space()
1451 path->slots[0]++; in remove_block_group_free_space()
1452 while (path->slots[0] > 0) { in remove_block_group_free_space()
1453 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); in remove_block_group_free_space()
1456 ASSERT(found_key.objectid == block_group->start); in remove_block_group_free_space()
1457 ASSERT(found_key.offset == block_group->length); in remove_block_group_free_space()
1458 done = 1; in remove_block_group_free_space()
1460 path->slots[0]--; in remove_block_group_free_space()
1468 path->slots[0]--; in remove_block_group_free_space()
1474 ret = btrfs_del_items(trans, root, path, path->slots[0], nr); in remove_block_group_free_space()
1495 struct btrfs_key key; in load_free_space_bitmaps() local
1504 block_group = caching_ctl->block_group; in load_free_space_bitmaps()
1505 fs_info = block_group->fs_info; in load_free_space_bitmaps()
1508 end = block_group->start + block_group->length; in load_free_space_bitmaps()
1510 while (1) { in load_free_space_bitmaps()
1517 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in load_free_space_bitmaps()
1519 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) in load_free_space_bitmaps()
1522 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); in load_free_space_bitmaps()
1523 ASSERT(key.objectid < end && key.objectid + key.offset <= end); in load_free_space_bitmaps()
1525 offset = key.objectid; in load_free_space_bitmaps()
1526 while (offset < key.objectid + key.offset) { in load_free_space_bitmaps()
1528 if (prev_bit == 0 && bit == 1) { in load_free_space_bitmaps()
1530 } else if (prev_bit == 1 && bit == 0) { in load_free_space_bitmaps()
1542 wake_up(&caching_ctl->wait); in load_free_space_bitmaps()
1547 offset += fs_info->sectorsize; in load_free_space_bitmaps()
1550 if (prev_bit == 1) { in load_free_space_bitmaps()
1560 block_group->start, extent_count, in load_free_space_bitmaps()
1563 ret = -EIO; in load_free_space_bitmaps()
1579 struct btrfs_key key; in load_free_space_extents() local
1585 block_group = caching_ctl->block_group; in load_free_space_extents()
1586 fs_info = block_group->fs_info; in load_free_space_extents()
1589 end = block_group->start + block_group->length; in load_free_space_extents()
1591 while (1) { in load_free_space_extents()
1600 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); in load_free_space_extents()
1602 if (key.type == BTRFS_FREE_SPACE_INFO_KEY) in load_free_space_extents()
1605 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); in load_free_space_extents()
1606 ASSERT(key.objectid < end && key.objectid + key.offset <= end); in load_free_space_extents()
1608 ret = btrfs_add_new_free_space(block_group, key.objectid, in load_free_space_extents()
1609 key.objectid + key.offset, in load_free_space_extents()
1616 wake_up(&caching_ctl->wait); in load_free_space_extents()
1624 block_group->start, extent_count, in load_free_space_extents()
1627 ret = -EIO; in load_free_space_extents()
1644 block_group = caching_ctl->block_group; in load_free_space_tree()
1648 return -ENOMEM; in load_free_space_tree()
1654 path->skip_locking = 1; in load_free_space_tree()
1655 path->search_commit_root = 1; in load_free_space_tree()
1656 path->reada = READA_FORWARD; in load_free_space_tree()
1663 extent_count = btrfs_free_space_extent_count(path->nodes[0], info); in load_free_space_tree()
1664 flags = btrfs_free_space_flags(path->nodes[0], info); in load_free_space_tree()