^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (C) 2015 Facebook. All rights reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/sched/mm.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include "ctree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include "disk-io.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "locking.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include "free-space-tree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include "transaction.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include "block-group.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) struct btrfs_path *path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) void set_free_space_tree_thresholds(struct btrfs_block_group *cache)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) u32 bitmap_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) size_t bitmap_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) u64 num_bitmaps, total_bitmap_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) if (WARN_ON(cache->length == 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) btrfs_warn(cache->fs_info, "block group %llu length is zero",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) cache->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * We convert to bitmaps when the disk space required for using extents
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * exceeds that required for using bitmaps.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) total_bitmap_size = num_bitmaps * bitmap_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) cache->bitmap_high_thresh = div_u64(total_bitmap_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) sizeof(struct btrfs_item));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * We allow for a small buffer between the high threshold and low
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) * threshold to avoid thrashing back and forth between the two formats.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) if (cache->bitmap_high_thresh > 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) cache->bitmap_low_thresh = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) static int add_new_free_space_info(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) struct btrfs_path *path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) struct btrfs_root *root = trans->fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) key.objectid = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) key.type = BTRFS_FREE_SPACE_INFO_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) key.offset = block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) info = btrfs_item_ptr(leaf, path->slots[0],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) struct btrfs_free_space_info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) btrfs_set_free_space_extent_count(leaf, info, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) btrfs_set_free_space_flags(leaf, info, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) btrfs_mark_buffer_dirty(leaf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) struct btrfs_free_space_info *search_free_space_info(
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) struct btrfs_path *path, int cow)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) struct btrfs_fs_info *fs_info = block_group->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) struct btrfs_root *root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) key.objectid = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) key.type = BTRFS_FREE_SPACE_INFO_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) key.offset = block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) return ERR_PTR(ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) if (ret != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) btrfs_warn(fs_info, "missing free space info for %llu",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) return ERR_PTR(-ENOENT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) return btrfs_item_ptr(path->nodes[0], path->slots[0],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) struct btrfs_free_space_info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * btrfs_search_slot() but we're looking for the greatest key less than the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) * passed key.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) struct btrfs_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) struct btrfs_key *key, struct btrfs_path *p,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) int ins_len, int cow)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) if (ret == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) return -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (p->slots[0] == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) return -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) p->slots[0]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) static unsigned long *alloc_bitmap(u32 bitmap_size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) unsigned long *ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) unsigned int nofs_flag;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) * into the filesystem as the free space bitmap can be modified in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) * critical section of a transaction commit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) * TODO: push the memalloc_nofs_{save,restore}() to the caller where we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) * know that recursion is unsafe.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) nofs_flag = memalloc_nofs_save();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) memalloc_nofs_restore(nofs_flag);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) static void le_bitmap_set(unsigned long *map, unsigned int start, int len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) u8 *p = ((u8 *)map) + BIT_BYTE(start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) const unsigned int size = start + len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) while (len - bits_to_set >= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) *p |= mask_to_set;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) len -= bits_to_set;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) bits_to_set = BITS_PER_BYTE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) mask_to_set = ~0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) p++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) if (len) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) *p |= mask_to_set;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) struct btrfs_path *path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) struct btrfs_fs_info *fs_info = trans->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) struct btrfs_root *root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) struct btrfs_key key, found_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) unsigned long *bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) char *bitmap_cursor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) u64 start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) u64 bitmap_range, i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) u32 bitmap_size, flags, expected_extent_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) u32 extent_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) int done = 0, nr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) bitmap_size = free_space_bitmap_size(block_group->length,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) bitmap = alloc_bitmap(bitmap_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) if (!bitmap) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) start = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) key.objectid = end - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) while (!done) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) nr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) path->slots[0]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) while (path->slots[0] > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) ASSERT(found_key.objectid == block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) ASSERT(found_key.offset == block_group->length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) done = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) u64 first, last;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) ASSERT(found_key.objectid >= start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) ASSERT(found_key.objectid < end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) ASSERT(found_key.objectid + found_key.offset <= end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) first = div_u64(found_key.objectid - start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) last = div_u64(found_key.objectid + found_key.offset - start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) le_bitmap_set(bitmap, first, last - first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) extent_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) nr++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) path->slots[0]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) info = search_free_space_info(trans, block_group, path, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) if (IS_ERR(info)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) ret = PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) flags = btrfs_free_space_flags(leaf, info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) btrfs_set_free_space_flags(leaf, info, flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) expected_extent_count = btrfs_free_space_extent_count(leaf, info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) btrfs_mark_buffer_dirty(leaf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) if (extent_count != expected_extent_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) btrfs_err(fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) "incorrect extent count for %llu; counted %u, expected %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) block_group->start, extent_count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) expected_extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) ret = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) bitmap_cursor = (char *)bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) i = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) while (i < end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) unsigned long ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) u64 extent_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) u32 data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) extent_size = min(end - i, bitmap_range);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) data_size = free_space_bitmap_size(extent_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) key.objectid = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) key.offset = extent_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) ret = btrfs_insert_empty_item(trans, root, path, &key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) write_extent_buffer(leaf, bitmap_cursor, ptr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) btrfs_mark_buffer_dirty(leaf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) i += extent_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) bitmap_cursor += data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) kvfree(bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) struct btrfs_path *path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) struct btrfs_fs_info *fs_info = trans->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) struct btrfs_root *root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) struct btrfs_key key, found_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) unsigned long *bitmap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) u64 start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) u32 bitmap_size, flags, expected_extent_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) unsigned long nrbits, start_bit, end_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) u32 extent_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) int done = 0, nr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) bitmap_size = free_space_bitmap_size(block_group->length,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) bitmap = alloc_bitmap(bitmap_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) if (!bitmap) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) start = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) key.objectid = end - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) while (!done) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) nr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) path->slots[0]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) while (path->slots[0] > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) ASSERT(found_key.objectid == block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) ASSERT(found_key.offset == block_group->length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) done = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) unsigned long ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) char *bitmap_cursor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) u32 bitmap_pos, data_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) ASSERT(found_key.objectid >= start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) ASSERT(found_key.objectid < end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) ASSERT(found_key.objectid + found_key.offset <= end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) bitmap_pos = div_u64(found_key.objectid - start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) fs_info->sectorsize *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) BITS_PER_BYTE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) bitmap_cursor = ((char *)bitmap) + bitmap_pos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) data_size = free_space_bitmap_size(found_key.offset,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) read_extent_buffer(leaf, bitmap_cursor, ptr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) data_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) nr++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) path->slots[0]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) info = search_free_space_info(trans, block_group, path, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) if (IS_ERR(info)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) ret = PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) flags = btrfs_free_space_flags(leaf, info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) btrfs_set_free_space_flags(leaf, info, flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) expected_extent_count = btrfs_free_space_extent_count(leaf, info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) btrfs_mark_buffer_dirty(leaf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) nrbits = div_u64(block_group->length, block_group->fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) start_bit = find_next_bit_le(bitmap, nrbits, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) while (start_bit < nrbits) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) ASSERT(start_bit < end_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) key.objectid = start + start_bit * block_group->fs_info->sectorsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) extent_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) start_bit = find_next_bit_le(bitmap, nrbits, end_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) if (extent_count != expected_extent_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) btrfs_err(fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) "incorrect extent count for %llu; counted %u, expected %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) block_group->start, extent_count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) expected_extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) ret = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) kvfree(bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) int new_extents)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) u32 flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) u32 extent_count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) if (new_extents == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) info = search_free_space_info(trans, block_group, path, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) if (IS_ERR(info)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) ret = PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) flags = btrfs_free_space_flags(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) extent_count += new_extents;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) btrfs_mark_buffer_dirty(path->nodes[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) extent_count > block_group->bitmap_high_thresh) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) ret = convert_free_space_to_bitmaps(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) extent_count < block_group->bitmap_low_thresh) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) ret = convert_free_space_to_extents(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) int free_space_test_bit(struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) struct btrfs_path *path, u64 offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) u64 found_start, found_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) unsigned long ptr, i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) found_start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) found_end = key.objectid + key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) ASSERT(offset >= found_start && offset < found_end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) i = div_u64(offset - found_start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) block_group->fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) return !!extent_buffer_test_bit(leaf, ptr, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) static void free_space_set_bits(struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) struct btrfs_path *path, u64 *start, u64 *size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) int bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) struct btrfs_fs_info *fs_info = block_group->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) u64 end = *start + *size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) u64 found_start, found_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) unsigned long ptr, first, last;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) found_start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) found_end = key.objectid + key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) ASSERT(*start >= found_start && *start < found_end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) ASSERT(end > found_start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) if (end > found_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) end = found_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) first = div_u64(*start - found_start, fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) last = div_u64(end - found_start, fs_info->sectorsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) if (bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) extent_buffer_bitmap_set(leaf, ptr, first, last - first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) btrfs_mark_buffer_dirty(leaf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) *size -= end - *start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) *start = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) * We can't use btrfs_next_item() in modify_free_space_bitmap() because
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) * looking for.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) struct btrfs_root *root, struct btrfs_path *p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) p->slots[0]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) btrfs_release_path(p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) key.objectid += key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) * If remove is 1, then we are removing free space, thus clearing bits in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) * bitmap. If remove is 0, then we are adding free space, thus setting bits in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) * the bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) u64 start, u64 size, int remove)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) struct btrfs_root *root = block_group->fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) u64 end = start + size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) u64 cur_start, cur_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) int prev_bit, next_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) int new_extents;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) * Read the bit for the block immediately before the extent of space if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) * that block is within the block group.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) if (start > block_group->start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) u64 prev_block = start - block_group->fs_info->sectorsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) key.objectid = prev_block;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) prev_bit = free_space_test_bit(block_group, path, prev_block);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) /* The previous block may have been in the previous bitmap. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) if (start >= key.objectid + key.offset) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) ret = free_space_next_bitmap(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) key.objectid = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) prev_bit = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) * Iterate over all of the bitmaps overlapped by the extent of space,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) * clearing/setting bits as required.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) cur_start = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) cur_size = size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) free_space_set_bits(block_group, path, &cur_start, &cur_size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) !remove);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) if (cur_size == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) ret = free_space_next_bitmap(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) * Read the bit for the block immediately after the extent of space if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) * that block is within the block group.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) if (end < block_group->start + block_group->length) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) /* The next block may be in the next bitmap. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) if (end >= key.objectid + key.offset) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) ret = free_space_next_bitmap(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) next_bit = free_space_test_bit(block_group, path, end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) next_bit = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) if (remove) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) new_extents = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) if (prev_bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) /* Leftover on the left. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) new_extents++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) if (next_bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) /* Leftover on the right. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) new_extents++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) new_extents = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) if (prev_bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) /* Merging with neighbor on the left. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) new_extents--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) if (next_bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) /* Merging with neighbor on the right. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) new_extents--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) ret = update_free_space_extent_count(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) new_extents);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) static int remove_free_space_extent(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) struct btrfs_root *root = trans->fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) u64 found_start, found_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) u64 end = start + size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) int new_extents = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) key.objectid = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) found_start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) found_end = key.objectid + key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) ASSERT(start >= found_start && end <= found_end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) * Okay, now that we've found the free space extent which contains the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) * free space that we are removing, there are four cases:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) * 1. We're using the whole extent: delete the key we found and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) * decrement the free space extent count.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) * 2. We are using part of the extent starting at the beginning: delete
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) * the key we found and insert a new key representing the leftover at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) * the end. There is no net change in the number of extents.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) * 3. We are using part of the extent ending at the end: delete the key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) * we found and insert a new key representing the leftover at the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) * beginning. There is no net change in the number of extents.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) * 4. We are using part of the extent in the middle: delete the key we
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) * found and insert two new keys representing the leftovers on each
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) * side. Where we used to have one extent, we now have two, so increment
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) * the extent count. We may need to convert the block group to bitmaps
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) * as a result.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) /* Delete the existing key (cases 1-4). */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) ret = btrfs_del_item(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) /* Add a key for leftovers at the beginning (cases 3 and 4). */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) if (start > found_start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) key.objectid = found_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) key.offset = start - found_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) new_extents++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) /* Add a key for leftovers at the end (cases 2 and 4). */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) if (end < found_end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) key.objectid = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) key.offset = found_end - end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) new_extents++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) ret = update_free_space_extent_count(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) new_extents);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) struct btrfs_path *path, u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) u32 flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) if (block_group->needs_free_space) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) ret = __add_block_group_free_space(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) info = search_free_space_info(NULL, block_group, path, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) if (IS_ERR(info))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) return PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) flags = btrfs_free_space_flags(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) return modify_free_space_bitmap(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) start, size, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) return remove_free_space_extent(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) start, size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) if (!path) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) block_group = btrfs_lookup_block_group(trans->fs_info, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) if (!block_group) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) ret = -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838) mutex_lock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) ret = __remove_from_free_space_tree(trans, block_group, path, start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) mutex_unlock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) btrfs_put_block_group(block_group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) static int add_free_space_extent(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) struct btrfs_root *root = trans->fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) struct btrfs_key key, new_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) u64 found_start, found_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) u64 end = start + size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) int new_extents = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) * We are adding a new extent of free space, but we need to merge
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) * extents. There are four cases here:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) * 1. The new extent does not have any immediate neighbors to merge
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) * with: add the new key and increment the free space extent count. We
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) * may need to convert the block group to bitmaps as a result.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) * 2. The new extent has an immediate neighbor before it: remove the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) * previous key and insert a new key combining both of them. There is no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) * net change in the number of extents.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) * 3. The new extent has an immediate neighbor after it: remove the next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) * key and insert a new key combining both of them. There is no net
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) * change in the number of extents.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) * 4. The new extent has immediate neighbors on both sides: remove both
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) * of the keys and insert a new key combining all of them. Where we used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) * to have two extents, we now have one, so decrement the extent count.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) new_key.objectid = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) new_key.offset = size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) /* Search for a neighbor on the left. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) if (start == block_group->start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) goto right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) key.objectid = start - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901) goto right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904) found_start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) found_end = key.objectid + key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906) ASSERT(found_start >= block_group->start &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) found_end > block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) ASSERT(found_start < start && found_end <= start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) * Delete the neighbor on the left and absorb it into the new key (cases
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) * 2 and 4).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) if (found_end == start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) ret = btrfs_del_item(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918) new_key.objectid = found_start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) new_key.offset += key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) new_extents--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) right:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) /* Search for a neighbor on the right. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) if (end == block_group->start + block_group->length)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) goto insert;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) key.objectid = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939) ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941) goto insert;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) found_start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945) found_end = key.objectid + key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) ASSERT(found_start >= block_group->start &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) found_end > block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) ASSERT((found_start < start && found_end <= start) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) (found_start >= end && found_end > end));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) * Delete the neighbor on the right and absorb it into the new key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953) * (cases 3 and 4).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) if (found_start == end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) ret = btrfs_del_item(trans, root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) new_key.offset += key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) new_extents--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) insert:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) /* Insert the new key (cases 1-4). */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) ret = update_free_space_extent_count(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) new_extents);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) EXPORT_FOR_TESTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) struct btrfs_path *path, u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) u32 flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) if (block_group->needs_free_space) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) ret = __add_block_group_free_space(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) info = search_free_space_info(NULL, block_group, path, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) if (IS_ERR(info))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) return PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) flags = btrfs_free_space_flags(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) return modify_free_space_bitmap(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) start, size, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) return add_free_space_extent(trans, block_group, path, start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) int add_to_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) u64 start, u64 size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) if (!path) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024) block_group = btrfs_lookup_block_group(trans->fs_info, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025) if (!block_group) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027) ret = -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031) mutex_lock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) ret = __add_to_free_space_tree(trans, block_group, path, start, size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033) mutex_unlock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) btrfs_put_block_group(block_group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044) * Populate the free space tree by walking the extent tree. Operations on the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) * extent tree that happen as a result of writes to the free space tree will go
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) * through the normal add/remove hooks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) static int populate_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) struct btrfs_block_group *block_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) struct btrfs_root *extent_root = trans->fs_info->extent_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) struct btrfs_path *path, *path2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) u64 start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) if (!path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) path->reada = READA_FORWARD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) path2 = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) if (!path2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) ret = add_new_free_space_info(trans, block_group, path2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) mutex_lock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075) * Iterate through all of the extent and metadata items in this block
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) * group, adding the free space between them and the free space at the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077) * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) * contained in.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081) key.objectid = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) key.type = BTRFS_EXTENT_ITEM_KEY;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) key.offset = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087) goto out_locked;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) ASSERT(ret == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) start = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) if (key.type == BTRFS_EXTENT_ITEM_KEY ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096) key.type == BTRFS_METADATA_ITEM_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097) if (key.objectid >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) if (start < key.objectid) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101) ret = __add_to_free_space_tree(trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102) block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) path2, start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) key.objectid -
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107) goto out_locked;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109) start = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) if (key.type == BTRFS_METADATA_ITEM_KEY)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) start += trans->fs_info->nodesize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) start += key.offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114) } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) if (key.objectid != block_group->start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119) ret = btrfs_next_item(extent_root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121) goto out_locked;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) if (start < end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126) ret = __add_to_free_space_tree(trans, block_group, path2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127) start, end - start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) goto out_locked;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) out_locked:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) mutex_unlock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1135) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1136) btrfs_free_path(path2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1137) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1138) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1139) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1141) int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1142) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1143) struct btrfs_trans_handle *trans;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1144) struct btrfs_root *tree_root = fs_info->tree_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1145) struct btrfs_root *free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1146) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1147) struct rb_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1148) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1149)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1150) trans = btrfs_start_transaction(tree_root, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1151) if (IS_ERR(trans))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1152) return PTR_ERR(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1154) set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1155) set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1156) free_space_root = btrfs_create_tree(trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1157) BTRFS_FREE_SPACE_TREE_OBJECTID);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1158) if (IS_ERR(free_space_root)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1159) ret = PTR_ERR(free_space_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1160) goto abort;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1161) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1162) fs_info->free_space_root = free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1164) node = rb_first(&fs_info->block_group_cache_tree);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1165) while (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1166) block_group = rb_entry(node, struct btrfs_block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1167) cache_node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1168) ret = populate_free_space_tree(trans, block_group);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1169) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1170) goto abort;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1171) node = rb_next(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1174) btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1175) btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1176) clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1177) ret = btrfs_commit_transaction(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1178)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1179) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1180) * Now that we've committed the transaction any reading of our commit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1181) * root will be safe, so we can cache from the free space tree now.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1182) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1183) clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1184) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1185)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1186) abort:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1187) clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1188) clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1189) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1190) btrfs_end_transaction(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1191) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1192) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1193)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1194) static int clear_free_space_tree(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1195) struct btrfs_root *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1196) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1197) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1198) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1199) int nr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1200) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1201)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1202) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1203) if (!path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1204) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1206) path->leave_spinning = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1207)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1208) key.objectid = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1209) key.type = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1210) key.offset = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1211)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1212) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1213) ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1214) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1215) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1216)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1217) nr = btrfs_header_nritems(path->nodes[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1218) if (!nr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1219) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1220)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1221) path->slots[0] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1222) ret = btrfs_del_items(trans, root, path, 0, nr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1223) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1224) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1226) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1227) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1229) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1230) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1231) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1232) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1233) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1234)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1235) int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1236) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1237) struct btrfs_trans_handle *trans;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1238) struct btrfs_root *tree_root = fs_info->tree_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1239) struct btrfs_root *free_space_root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1240) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1241)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1242) trans = btrfs_start_transaction(tree_root, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1243) if (IS_ERR(trans))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1244) return PTR_ERR(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1246) btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1247) btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1248) fs_info->free_space_root = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1249)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1250) ret = clear_free_space_tree(trans, free_space_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1251) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1252) goto abort;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1254) ret = btrfs_del_root(trans, &free_space_root->root_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1255) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1256) goto abort;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1257)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1258) list_del(&free_space_root->dirty_list);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1259)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1260) btrfs_tree_lock(free_space_root->node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1261) btrfs_clean_tree_block(free_space_root->node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1262) btrfs_tree_unlock(free_space_root->node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1263) btrfs_free_tree_block(trans, free_space_root, free_space_root->node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1264) 0, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1265)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1266) btrfs_put_root(free_space_root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1267)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1268) return btrfs_commit_transaction(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1269)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1270) abort:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1271) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1272) btrfs_end_transaction(trans);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1273) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1274) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1275)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1276) static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1277) struct btrfs_block_group *block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1278) struct btrfs_path *path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1279) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1280) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1282) block_group->needs_free_space = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1284) ret = add_new_free_space_info(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1285) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1286) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1287)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1288) return __add_to_free_space_tree(trans, block_group, path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1289) block_group->start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1290) block_group->length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1291) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1292)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1293) int add_block_group_free_space(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1294) struct btrfs_block_group *block_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1295) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1296) struct btrfs_fs_info *fs_info = trans->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1297) struct btrfs_path *path = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1298) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1300) if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1301) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1302)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1303) mutex_lock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1304) if (!block_group->needs_free_space)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1305) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1306)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1307) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1308) if (!path) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1309) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1310) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1311) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1312)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1313) ret = __add_block_group_free_space(trans, block_group, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1315) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1316) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1317) mutex_unlock(&block_group->free_space_lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1318) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1319) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1320) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1321) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1323) int remove_block_group_free_space(struct btrfs_trans_handle *trans,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1324) struct btrfs_block_group *block_group)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1325) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1326) struct btrfs_root *root = trans->fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1327) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1328) struct btrfs_key key, found_key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1329) struct extent_buffer *leaf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1330) u64 start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1331) int done = 0, nr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1332) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1333)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1334) if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1335) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1336)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1337) if (block_group->needs_free_space) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1338) /* We never added this block group to the free space tree. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1339) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1340) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1341)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1342) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1343) if (!path) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1344) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1345) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1346) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1348) start = block_group->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1349) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1350)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1351) key.objectid = end - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1352) key.type = (u8)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1353) key.offset = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1354)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1355) while (!done) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1356) ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1357) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1358) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1359)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1360) leaf = path->nodes[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1361) nr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1362) path->slots[0]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1363) while (path->slots[0] > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1364) btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1365)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1366) if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1367) ASSERT(found_key.objectid == block_group->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1368) ASSERT(found_key.offset == block_group->length);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1369) done = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1370) nr++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1371) path->slots[0]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1372) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1373) } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1374) found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1375) ASSERT(found_key.objectid >= start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1376) ASSERT(found_key.objectid < end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1377) ASSERT(found_key.objectid + found_key.offset <= end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1378) nr++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1379) path->slots[0]--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1380) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1381) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1382) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1383) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1385) ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1386) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1387) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1388) btrfs_release_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1389) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1390)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1391) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1392) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1393) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1394) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1395) btrfs_abort_transaction(trans, ret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1396) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1397) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1398)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1399) static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1400) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1401) u32 expected_extent_count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1402) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1403) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1404) struct btrfs_fs_info *fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1405) struct btrfs_root *root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1406) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1407) int prev_bit = 0, bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1408) /* Initialize to silence GCC. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1409) u64 extent_start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1410) u64 end, offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1411) u64 total_found = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1412) u32 extent_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1413) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1414)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1415) block_group = caching_ctl->block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1416) fs_info = block_group->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1417) root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1418)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1419) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1421) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1422) ret = btrfs_next_item(root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1423) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1424) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1425) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1426) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1428) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1430) if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1431) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1432)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1433) ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1434) ASSERT(key.objectid < end && key.objectid + key.offset <= end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1435)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1436) caching_ctl->progress = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1437)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1438) offset = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1439) while (offset < key.objectid + key.offset) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1440) bit = free_space_test_bit(block_group, path, offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1441) if (prev_bit == 0 && bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1442) extent_start = offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1443) } else if (prev_bit == 1 && bit == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1444) total_found += add_new_free_space(block_group,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1445) extent_start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1446) offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1447) if (total_found > CACHING_CTL_WAKE_UP) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1448) total_found = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1449) wake_up(&caching_ctl->wait);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1450) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1451) extent_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1452) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1453) prev_bit = bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1454) offset += fs_info->sectorsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1455) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1456) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1457) if (prev_bit == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1458) total_found += add_new_free_space(block_group, extent_start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1459) end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1460) extent_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1461) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1462)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1463) if (extent_count != expected_extent_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1464) btrfs_err(fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1465) "incorrect extent count for %llu; counted %u, expected %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1466) block_group->start, extent_count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1467) expected_extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1468) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1469) ret = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1470) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1471) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1472)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1473) caching_ctl->progress = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1474)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1475) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1476) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1477) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1478) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1479)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1480) static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1481) struct btrfs_path *path,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1482) u32 expected_extent_count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1483) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1484) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1485) struct btrfs_fs_info *fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1486) struct btrfs_root *root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1487) struct btrfs_key key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1488) u64 end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1489) u64 total_found = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1490) u32 extent_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1491) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1492)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1493) block_group = caching_ctl->block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1494) fs_info = block_group->fs_info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1495) root = fs_info->free_space_root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1496)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1497) end = block_group->start + block_group->length;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1498)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1499) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1500) ret = btrfs_next_item(root, path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1501) if (ret < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1502) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1503) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1504) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1505)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1506) btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1507)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1508) if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1509) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1510)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1511) ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1512) ASSERT(key.objectid < end && key.objectid + key.offset <= end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1513)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1514) caching_ctl->progress = key.objectid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1515)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1516) total_found += add_new_free_space(block_group, key.objectid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1517) key.objectid + key.offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1518) if (total_found > CACHING_CTL_WAKE_UP) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1519) total_found = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1520) wake_up(&caching_ctl->wait);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1521) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1522) extent_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1523) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1524)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1525) if (extent_count != expected_extent_count) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1526) btrfs_err(fs_info,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1527) "incorrect extent count for %llu; counted %u, expected %u",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1528) block_group->start, extent_count,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1529) expected_extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1530) ASSERT(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1531) ret = -EIO;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1532) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1533) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1534)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1535) caching_ctl->progress = (u64)-1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1536)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1537) ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1538) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1539) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1540) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1541)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1542) int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1543) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1544) struct btrfs_block_group *block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1545) struct btrfs_free_space_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1546) struct btrfs_path *path;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1547) u32 extent_count, flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1548) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1549)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1550) block_group = caching_ctl->block_group;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1551)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1552) path = btrfs_alloc_path();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1553) if (!path)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1554) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1555)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1556) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1557) * Just like caching_thread() doesn't want to deadlock on the extent
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1558) * tree, we don't want to deadlock on the free space tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1559) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1560) path->skip_locking = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1561) path->search_commit_root = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1562) path->reada = READA_FORWARD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1563)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1564) info = search_free_space_info(NULL, block_group, path, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1565) if (IS_ERR(info)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1566) ret = PTR_ERR(info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1567) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1568) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1569) extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1570) flags = btrfs_free_space_flags(path->nodes[0], info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1571)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1572) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1573) * We left path pointing to the free space info item, so now
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1574) * load_free_space_foo can just iterate through the free space tree from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1575) * there.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1576) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1577) if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1578) ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1579) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1580) ret = load_free_space_extents(caching_ctl, path, extent_count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1581)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1582) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1583) btrfs_free_path(path);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1584) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1585) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags