1c1d7c514SDavid Sterba // SPDX-License-Identifier: GPL-2.0 2a5ed9182SOmar Sandoval /* 3a5ed9182SOmar Sandoval * Copyright (C) 2015 Facebook. All rights reserved. 4a5ed9182SOmar Sandoval */ 5a5ed9182SOmar Sandoval 6a5ed9182SOmar Sandoval #include <linux/kernel.h> 725ff17e8SOmar Sandoval #include <linux/sched/mm.h> 89b569ea0SJosef Bacik #include "messages.h" 9a5ed9182SOmar Sandoval #include "ctree.h" 10a5ed9182SOmar Sandoval #include "disk-io.h" 11a5ed9182SOmar Sandoval #include "locking.h" 12a5ed9182SOmar Sandoval #include "free-space-tree.h" 13a5ed9182SOmar Sandoval #include "transaction.h" 14aac0023cSJosef Bacik #include "block-group.h" 15c7f13d42SJosef Bacik #include "fs.h" 1607e81dc9SJosef Bacik #include "accessors.h" 17a0231804SJosef Bacik #include "extent-tree.h" 1845c40c8fSJosef Bacik #include "root-tree.h" 19a5ed9182SOmar Sandoval 20a5ed9182SOmar Sandoval static int __add_block_group_free_space(struct btrfs_trans_handle *trans, 2132da5386SDavid Sterba struct btrfs_block_group *block_group, 22a5ed9182SOmar Sandoval struct btrfs_path *path); 23a5ed9182SOmar Sandoval 247939dd9fSJosef Bacik static struct btrfs_root *btrfs_free_space_root( 257939dd9fSJosef Bacik struct btrfs_block_group *block_group) 267939dd9fSJosef Bacik { 27abed4aaaSJosef Bacik struct btrfs_key key = { 28abed4aaaSJosef Bacik .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID, 29abed4aaaSJosef Bacik .type = BTRFS_ROOT_ITEM_KEY, 30abed4aaaSJosef Bacik .offset = 0, 31abed4aaaSJosef Bacik }; 32abed4aaaSJosef Bacik 33f7238e50SJosef Bacik if (btrfs_fs_incompat(block_group->fs_info, EXTENT_TREE_V2)) 34f7238e50SJosef Bacik key.offset = block_group->global_root_id; 35abed4aaaSJosef Bacik return btrfs_global_root(block_group->fs_info, &key); 367939dd9fSJosef Bacik } 377939dd9fSJosef Bacik 3832da5386SDavid Sterba void set_free_space_tree_thresholds(struct btrfs_block_group *cache) 39a5ed9182SOmar Sandoval { 40a5ed9182SOmar Sandoval u32 bitmap_range; 41a5ed9182SOmar Sandoval size_t bitmap_size; 42a5ed9182SOmar Sandoval u64 num_bitmaps, total_bitmap_size; 43a5ed9182SOmar Sandoval 44e3e39c72SMarcos Paulo de Souza if (WARN_ON(cache->length == 0)) 45e3e39c72SMarcos Paulo de Souza btrfs_warn(cache->fs_info, "block group %llu length is zero", 46e3e39c72SMarcos Paulo de Souza cache->start); 47e3e39c72SMarcos Paulo de Souza 48a5ed9182SOmar Sandoval /* 49a5ed9182SOmar Sandoval * We convert to bitmaps when the disk space required for using extents 50a5ed9182SOmar Sandoval * exceeds that required for using bitmaps. 51a5ed9182SOmar Sandoval */ 52da17066cSJeff Mahoney bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; 53b3470b5dSDavid Sterba num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range); 54a5ed9182SOmar Sandoval bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE; 55a5ed9182SOmar Sandoval total_bitmap_size = num_bitmaps * bitmap_size; 56a5ed9182SOmar Sandoval cache->bitmap_high_thresh = div_u64(total_bitmap_size, 57a5ed9182SOmar Sandoval sizeof(struct btrfs_item)); 58a5ed9182SOmar Sandoval 59a5ed9182SOmar Sandoval /* 60a5ed9182SOmar Sandoval * We allow for a small buffer between the high threshold and low 61a5ed9182SOmar Sandoval * threshold to avoid thrashing back and forth between the two formats. 62a5ed9182SOmar Sandoval */ 63a5ed9182SOmar Sandoval if (cache->bitmap_high_thresh > 100) 64a5ed9182SOmar Sandoval cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100; 65a5ed9182SOmar Sandoval else 66a5ed9182SOmar Sandoval cache->bitmap_low_thresh = 0; 67a5ed9182SOmar Sandoval } 68a5ed9182SOmar Sandoval 69a5ed9182SOmar Sandoval static int add_new_free_space_info(struct btrfs_trans_handle *trans, 7032da5386SDavid Sterba struct btrfs_block_group *block_group, 71a5ed9182SOmar Sandoval struct btrfs_path *path) 72a5ed9182SOmar Sandoval { 737939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 74a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 75a5ed9182SOmar Sandoval struct btrfs_key key; 76a5ed9182SOmar Sandoval struct extent_buffer *leaf; 77a5ed9182SOmar Sandoval int ret; 78a5ed9182SOmar Sandoval 79b3470b5dSDavid Sterba key.objectid = block_group->start; 80a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_INFO_KEY; 81b3470b5dSDavid Sterba key.offset = block_group->length; 82a5ed9182SOmar Sandoval 83a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info)); 84a5ed9182SOmar Sandoval if (ret) 85a5ed9182SOmar Sandoval goto out; 86a5ed9182SOmar Sandoval 87a5ed9182SOmar Sandoval leaf = path->nodes[0]; 88a5ed9182SOmar Sandoval info = btrfs_item_ptr(leaf, path->slots[0], 89a5ed9182SOmar Sandoval struct btrfs_free_space_info); 90a5ed9182SOmar Sandoval btrfs_set_free_space_extent_count(leaf, info, 0); 91a5ed9182SOmar Sandoval btrfs_set_free_space_flags(leaf, info, 0); 92a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(leaf); 93a5ed9182SOmar Sandoval 94a5ed9182SOmar Sandoval ret = 0; 95a5ed9182SOmar Sandoval out: 96a5ed9182SOmar Sandoval btrfs_release_path(path); 97a5ed9182SOmar Sandoval return ret; 98a5ed9182SOmar Sandoval } 99a5ed9182SOmar Sandoval 100ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 101ce9f967fSJohannes Thumshirn struct btrfs_free_space_info *search_free_space_info( 1022ccf545eSDavid Sterba struct btrfs_trans_handle *trans, 10332da5386SDavid Sterba struct btrfs_block_group *block_group, 104a5ed9182SOmar Sandoval struct btrfs_path *path, int cow) 105a5ed9182SOmar Sandoval { 1062ccf545eSDavid Sterba struct btrfs_fs_info *fs_info = block_group->fs_info; 1077939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 108a5ed9182SOmar Sandoval struct btrfs_key key; 109a5ed9182SOmar Sandoval int ret; 110a5ed9182SOmar Sandoval 111b3470b5dSDavid Sterba key.objectid = block_group->start; 112a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_INFO_KEY; 113b3470b5dSDavid Sterba key.offset = block_group->length; 114a5ed9182SOmar Sandoval 115a5ed9182SOmar Sandoval ret = btrfs_search_slot(trans, root, &key, path, 0, cow); 116a5ed9182SOmar Sandoval if (ret < 0) 117a5ed9182SOmar Sandoval return ERR_PTR(ret); 118a5ed9182SOmar Sandoval if (ret != 0) { 119ab8d0fc4SJeff Mahoney btrfs_warn(fs_info, "missing free space info for %llu", 120b3470b5dSDavid Sterba block_group->start); 121a5ed9182SOmar Sandoval ASSERT(0); 122a5ed9182SOmar Sandoval return ERR_PTR(-ENOENT); 123a5ed9182SOmar Sandoval } 124a5ed9182SOmar Sandoval 125a5ed9182SOmar Sandoval return btrfs_item_ptr(path->nodes[0], path->slots[0], 126a5ed9182SOmar Sandoval struct btrfs_free_space_info); 127a5ed9182SOmar Sandoval } 128a5ed9182SOmar Sandoval 129a5ed9182SOmar Sandoval /* 130a5ed9182SOmar Sandoval * btrfs_search_slot() but we're looking for the greatest key less than the 131a5ed9182SOmar Sandoval * passed key. 132a5ed9182SOmar Sandoval */ 133a5ed9182SOmar Sandoval static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans, 134a5ed9182SOmar Sandoval struct btrfs_root *root, 135a5ed9182SOmar Sandoval struct btrfs_key *key, struct btrfs_path *p, 136a5ed9182SOmar Sandoval int ins_len, int cow) 137a5ed9182SOmar Sandoval { 138a5ed9182SOmar Sandoval int ret; 139a5ed9182SOmar Sandoval 140a5ed9182SOmar Sandoval ret = btrfs_search_slot(trans, root, key, p, ins_len, cow); 141a5ed9182SOmar Sandoval if (ret < 0) 142a5ed9182SOmar Sandoval return ret; 143a5ed9182SOmar Sandoval 144a5ed9182SOmar Sandoval if (ret == 0) { 145a5ed9182SOmar Sandoval ASSERT(0); 146a5ed9182SOmar Sandoval return -EIO; 147a5ed9182SOmar Sandoval } 148a5ed9182SOmar Sandoval 149a5ed9182SOmar Sandoval if (p->slots[0] == 0) { 150a5ed9182SOmar Sandoval ASSERT(0); 151a5ed9182SOmar Sandoval return -EIO; 152a5ed9182SOmar Sandoval } 153a5ed9182SOmar Sandoval p->slots[0]--; 154a5ed9182SOmar Sandoval 155a5ed9182SOmar Sandoval return 0; 156a5ed9182SOmar Sandoval } 157a5ed9182SOmar Sandoval 158098e6308SDavid Sterba static inline u32 free_space_bitmap_size(const struct btrfs_fs_info *fs_info, 159098e6308SDavid Sterba u64 size) 160a5ed9182SOmar Sandoval { 161098e6308SDavid Sterba return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE); 162a5ed9182SOmar Sandoval } 163a5ed9182SOmar Sandoval 164a565971fSHoward McLauchlan static unsigned long *alloc_bitmap(u32 bitmap_size) 165a5ed9182SOmar Sandoval { 166a565971fSHoward McLauchlan unsigned long *ret; 16725ff17e8SOmar Sandoval unsigned int nofs_flag; 168a565971fSHoward McLauchlan u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long)); 16979b134a2SDavid Sterba 17079b134a2SDavid Sterba /* 17125ff17e8SOmar Sandoval * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse 17225ff17e8SOmar Sandoval * into the filesystem as the free space bitmap can be modified in the 17325ff17e8SOmar Sandoval * critical section of a transaction commit. 17425ff17e8SOmar Sandoval * 17525ff17e8SOmar Sandoval * TODO: push the memalloc_nofs_{save,restore}() to the caller where we 17625ff17e8SOmar Sandoval * know that recursion is unsafe. 17779b134a2SDavid Sterba */ 17825ff17e8SOmar Sandoval nofs_flag = memalloc_nofs_save(); 179a565971fSHoward McLauchlan ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL); 18025ff17e8SOmar Sandoval memalloc_nofs_restore(nofs_flag); 18125ff17e8SOmar Sandoval return ret; 182a5ed9182SOmar Sandoval } 183a5ed9182SOmar Sandoval 184a565971fSHoward McLauchlan static void le_bitmap_set(unsigned long *map, unsigned int start, int len) 1856faa8f47SHoward McLauchlan { 186a565971fSHoward McLauchlan u8 *p = ((u8 *)map) + BIT_BYTE(start); 1876faa8f47SHoward McLauchlan const unsigned int size = start + len; 1886faa8f47SHoward McLauchlan int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE); 1896faa8f47SHoward McLauchlan u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start); 1906faa8f47SHoward McLauchlan 1916faa8f47SHoward McLauchlan while (len - bits_to_set >= 0) { 1926faa8f47SHoward McLauchlan *p |= mask_to_set; 1936faa8f47SHoward McLauchlan len -= bits_to_set; 1946faa8f47SHoward McLauchlan bits_to_set = BITS_PER_BYTE; 1956faa8f47SHoward McLauchlan mask_to_set = ~0; 1966faa8f47SHoward McLauchlan p++; 1976faa8f47SHoward McLauchlan } 1986faa8f47SHoward McLauchlan if (len) { 1996faa8f47SHoward McLauchlan mask_to_set &= BITMAP_LAST_BYTE_MASK(size); 2006faa8f47SHoward McLauchlan *p |= mask_to_set; 2016faa8f47SHoward McLauchlan } 2026faa8f47SHoward McLauchlan } 2036faa8f47SHoward McLauchlan 204ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 205a5ed9182SOmar Sandoval int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans, 20632da5386SDavid Sterba struct btrfs_block_group *block_group, 207a5ed9182SOmar Sandoval struct btrfs_path *path) 208a5ed9182SOmar Sandoval { 209719fb4deSNikolay Borisov struct btrfs_fs_info *fs_info = trans->fs_info; 2107939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 211a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 212a5ed9182SOmar Sandoval struct btrfs_key key, found_key; 213a5ed9182SOmar Sandoval struct extent_buffer *leaf; 214a565971fSHoward McLauchlan unsigned long *bitmap; 215a565971fSHoward McLauchlan char *bitmap_cursor; 216a5ed9182SOmar Sandoval u64 start, end; 217a5ed9182SOmar Sandoval u64 bitmap_range, i; 218a5ed9182SOmar Sandoval u32 bitmap_size, flags, expected_extent_count; 219a5ed9182SOmar Sandoval u32 extent_count = 0; 220a5ed9182SOmar Sandoval int done = 0, nr; 221a5ed9182SOmar Sandoval int ret; 222a5ed9182SOmar Sandoval 223098e6308SDavid Sterba bitmap_size = free_space_bitmap_size(fs_info, block_group->length); 224a5ed9182SOmar Sandoval bitmap = alloc_bitmap(bitmap_size); 225a5ed9182SOmar Sandoval if (!bitmap) { 226a5ed9182SOmar Sandoval ret = -ENOMEM; 227a5ed9182SOmar Sandoval goto out; 228a5ed9182SOmar Sandoval } 229a5ed9182SOmar Sandoval 230b3470b5dSDavid Sterba start = block_group->start; 231b3470b5dSDavid Sterba end = block_group->start + block_group->length; 232a5ed9182SOmar Sandoval 233a5ed9182SOmar Sandoval key.objectid = end - 1; 234a5ed9182SOmar Sandoval key.type = (u8)-1; 235a5ed9182SOmar Sandoval key.offset = (u64)-1; 236a5ed9182SOmar Sandoval 237a5ed9182SOmar Sandoval while (!done) { 238a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 239a5ed9182SOmar Sandoval if (ret) 240a5ed9182SOmar Sandoval goto out; 241a5ed9182SOmar Sandoval 242a5ed9182SOmar Sandoval leaf = path->nodes[0]; 243a5ed9182SOmar Sandoval nr = 0; 244a5ed9182SOmar Sandoval path->slots[0]++; 245a5ed9182SOmar Sandoval while (path->slots[0] > 0) { 246a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 247a5ed9182SOmar Sandoval 248a5ed9182SOmar Sandoval if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 249b3470b5dSDavid Sterba ASSERT(found_key.objectid == block_group->start); 250b3470b5dSDavid Sterba ASSERT(found_key.offset == block_group->length); 251a5ed9182SOmar Sandoval done = 1; 252a5ed9182SOmar Sandoval break; 253a5ed9182SOmar Sandoval } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) { 254a5ed9182SOmar Sandoval u64 first, last; 255a5ed9182SOmar Sandoval 256a5ed9182SOmar Sandoval ASSERT(found_key.objectid >= start); 257a5ed9182SOmar Sandoval ASSERT(found_key.objectid < end); 258a5ed9182SOmar Sandoval ASSERT(found_key.objectid + found_key.offset <= end); 259a5ed9182SOmar Sandoval 260a5ed9182SOmar Sandoval first = div_u64(found_key.objectid - start, 2610b246afaSJeff Mahoney fs_info->sectorsize); 262a5ed9182SOmar Sandoval last = div_u64(found_key.objectid + found_key.offset - start, 2630b246afaSJeff Mahoney fs_info->sectorsize); 2642fe1d551SOmar Sandoval le_bitmap_set(bitmap, first, last - first); 265a5ed9182SOmar Sandoval 266a5ed9182SOmar Sandoval extent_count++; 267a5ed9182SOmar Sandoval nr++; 268a5ed9182SOmar Sandoval path->slots[0]--; 269a5ed9182SOmar Sandoval } else { 270a5ed9182SOmar Sandoval ASSERT(0); 271a5ed9182SOmar Sandoval } 272a5ed9182SOmar Sandoval } 273a5ed9182SOmar Sandoval 274a5ed9182SOmar Sandoval ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 275a5ed9182SOmar Sandoval if (ret) 276a5ed9182SOmar Sandoval goto out; 277a5ed9182SOmar Sandoval btrfs_release_path(path); 278a5ed9182SOmar Sandoval } 279a5ed9182SOmar Sandoval 2802ccf545eSDavid Sterba info = search_free_space_info(trans, block_group, path, 1); 281a5ed9182SOmar Sandoval if (IS_ERR(info)) { 282a5ed9182SOmar Sandoval ret = PTR_ERR(info); 283a5ed9182SOmar Sandoval goto out; 284a5ed9182SOmar Sandoval } 285a5ed9182SOmar Sandoval leaf = path->nodes[0]; 286a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(leaf, info); 287a5ed9182SOmar Sandoval flags |= BTRFS_FREE_SPACE_USING_BITMAPS; 288a5ed9182SOmar Sandoval btrfs_set_free_space_flags(leaf, info, flags); 289a5ed9182SOmar Sandoval expected_extent_count = btrfs_free_space_extent_count(leaf, info); 290a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(leaf); 291a5ed9182SOmar Sandoval btrfs_release_path(path); 292a5ed9182SOmar Sandoval 293a5ed9182SOmar Sandoval if (extent_count != expected_extent_count) { 2945d163e0eSJeff Mahoney btrfs_err(fs_info, 2955d163e0eSJeff Mahoney "incorrect extent count for %llu; counted %u, expected %u", 296b3470b5dSDavid Sterba block_group->start, extent_count, 297a5ed9182SOmar Sandoval expected_extent_count); 298a5ed9182SOmar Sandoval ASSERT(0); 299a5ed9182SOmar Sandoval ret = -EIO; 300a5ed9182SOmar Sandoval goto out; 301a5ed9182SOmar Sandoval } 302a5ed9182SOmar Sandoval 303a565971fSHoward McLauchlan bitmap_cursor = (char *)bitmap; 3040b246afaSJeff Mahoney bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS; 305a5ed9182SOmar Sandoval i = start; 306a5ed9182SOmar Sandoval while (i < end) { 307a5ed9182SOmar Sandoval unsigned long ptr; 308a5ed9182SOmar Sandoval u64 extent_size; 309a5ed9182SOmar Sandoval u32 data_size; 310a5ed9182SOmar Sandoval 311a5ed9182SOmar Sandoval extent_size = min(end - i, bitmap_range); 312098e6308SDavid Sterba data_size = free_space_bitmap_size(fs_info, extent_size); 313a5ed9182SOmar Sandoval 314a5ed9182SOmar Sandoval key.objectid = i; 315a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_BITMAP_KEY; 316a5ed9182SOmar Sandoval key.offset = extent_size; 317a5ed9182SOmar Sandoval 318a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &key, 319a5ed9182SOmar Sandoval data_size); 320a5ed9182SOmar Sandoval if (ret) 321a5ed9182SOmar Sandoval goto out; 322a5ed9182SOmar Sandoval 323a5ed9182SOmar Sandoval leaf = path->nodes[0]; 324a5ed9182SOmar Sandoval ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 325a5ed9182SOmar Sandoval write_extent_buffer(leaf, bitmap_cursor, ptr, 326a5ed9182SOmar Sandoval data_size); 327a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(leaf); 328a5ed9182SOmar Sandoval btrfs_release_path(path); 329a5ed9182SOmar Sandoval 330a5ed9182SOmar Sandoval i += extent_size; 331a5ed9182SOmar Sandoval bitmap_cursor += data_size; 332a5ed9182SOmar Sandoval } 333a5ed9182SOmar Sandoval 334a5ed9182SOmar Sandoval ret = 0; 335a5ed9182SOmar Sandoval out: 33679b134a2SDavid Sterba kvfree(bitmap); 337a5ed9182SOmar Sandoval if (ret) 33866642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 339a5ed9182SOmar Sandoval return ret; 340a5ed9182SOmar Sandoval } 341a5ed9182SOmar Sandoval 342ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 343a5ed9182SOmar Sandoval int convert_free_space_to_extents(struct btrfs_trans_handle *trans, 34432da5386SDavid Sterba struct btrfs_block_group *block_group, 345a5ed9182SOmar Sandoval struct btrfs_path *path) 346a5ed9182SOmar Sandoval { 3475296c2bfSNikolay Borisov struct btrfs_fs_info *fs_info = trans->fs_info; 3487939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 349a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 350a5ed9182SOmar Sandoval struct btrfs_key key, found_key; 351a5ed9182SOmar Sandoval struct extent_buffer *leaf; 352a565971fSHoward McLauchlan unsigned long *bitmap; 353a5ed9182SOmar Sandoval u64 start, end; 354a5ed9182SOmar Sandoval u32 bitmap_size, flags, expected_extent_count; 355a565971fSHoward McLauchlan unsigned long nrbits, start_bit, end_bit; 356a5ed9182SOmar Sandoval u32 extent_count = 0; 357a5ed9182SOmar Sandoval int done = 0, nr; 358a5ed9182SOmar Sandoval int ret; 359a5ed9182SOmar Sandoval 360098e6308SDavid Sterba bitmap_size = free_space_bitmap_size(fs_info, block_group->length); 361a5ed9182SOmar Sandoval bitmap = alloc_bitmap(bitmap_size); 362a5ed9182SOmar Sandoval if (!bitmap) { 363a5ed9182SOmar Sandoval ret = -ENOMEM; 364a5ed9182SOmar Sandoval goto out; 365a5ed9182SOmar Sandoval } 366a5ed9182SOmar Sandoval 367b3470b5dSDavid Sterba start = block_group->start; 368b3470b5dSDavid Sterba end = block_group->start + block_group->length; 369a5ed9182SOmar Sandoval 370a5ed9182SOmar Sandoval key.objectid = end - 1; 371a5ed9182SOmar Sandoval key.type = (u8)-1; 372a5ed9182SOmar Sandoval key.offset = (u64)-1; 373a5ed9182SOmar Sandoval 374a5ed9182SOmar Sandoval while (!done) { 375a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 376a5ed9182SOmar Sandoval if (ret) 377a5ed9182SOmar Sandoval goto out; 378a5ed9182SOmar Sandoval 379a5ed9182SOmar Sandoval leaf = path->nodes[0]; 380a5ed9182SOmar Sandoval nr = 0; 381a5ed9182SOmar Sandoval path->slots[0]++; 382a5ed9182SOmar Sandoval while (path->slots[0] > 0) { 383a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 384a5ed9182SOmar Sandoval 385a5ed9182SOmar Sandoval if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 386b3470b5dSDavid Sterba ASSERT(found_key.objectid == block_group->start); 387b3470b5dSDavid Sterba ASSERT(found_key.offset == block_group->length); 388a5ed9182SOmar Sandoval done = 1; 389a5ed9182SOmar Sandoval break; 390a5ed9182SOmar Sandoval } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) { 391a5ed9182SOmar Sandoval unsigned long ptr; 392a565971fSHoward McLauchlan char *bitmap_cursor; 393a5ed9182SOmar Sandoval u32 bitmap_pos, data_size; 394a5ed9182SOmar Sandoval 395a5ed9182SOmar Sandoval ASSERT(found_key.objectid >= start); 396a5ed9182SOmar Sandoval ASSERT(found_key.objectid < end); 397a5ed9182SOmar Sandoval ASSERT(found_key.objectid + found_key.offset <= end); 398a5ed9182SOmar Sandoval 399a5ed9182SOmar Sandoval bitmap_pos = div_u64(found_key.objectid - start, 4000b246afaSJeff Mahoney fs_info->sectorsize * 401a5ed9182SOmar Sandoval BITS_PER_BYTE); 402a565971fSHoward McLauchlan bitmap_cursor = ((char *)bitmap) + bitmap_pos; 403098e6308SDavid Sterba data_size = free_space_bitmap_size(fs_info, 404098e6308SDavid Sterba found_key.offset); 405a5ed9182SOmar Sandoval 406a5ed9182SOmar Sandoval ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1); 407a5ed9182SOmar Sandoval read_extent_buffer(leaf, bitmap_cursor, ptr, 408a5ed9182SOmar Sandoval data_size); 409a5ed9182SOmar Sandoval 410a5ed9182SOmar Sandoval nr++; 411a5ed9182SOmar Sandoval path->slots[0]--; 412a5ed9182SOmar Sandoval } else { 413a5ed9182SOmar Sandoval ASSERT(0); 414a5ed9182SOmar Sandoval } 415a5ed9182SOmar Sandoval } 416a5ed9182SOmar Sandoval 417a5ed9182SOmar Sandoval ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 418a5ed9182SOmar Sandoval if (ret) 419a5ed9182SOmar Sandoval goto out; 420a5ed9182SOmar Sandoval btrfs_release_path(path); 421a5ed9182SOmar Sandoval } 422a5ed9182SOmar Sandoval 4232ccf545eSDavid Sterba info = search_free_space_info(trans, block_group, path, 1); 424a5ed9182SOmar Sandoval if (IS_ERR(info)) { 425a5ed9182SOmar Sandoval ret = PTR_ERR(info); 426a5ed9182SOmar Sandoval goto out; 427a5ed9182SOmar Sandoval } 428a5ed9182SOmar Sandoval leaf = path->nodes[0]; 429a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(leaf, info); 430a5ed9182SOmar Sandoval flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS; 431a5ed9182SOmar Sandoval btrfs_set_free_space_flags(leaf, info, flags); 432a5ed9182SOmar Sandoval expected_extent_count = btrfs_free_space_extent_count(leaf, info); 433a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(leaf); 434a5ed9182SOmar Sandoval btrfs_release_path(path); 435a5ed9182SOmar Sandoval 436ab108d99SDavid Sterba nrbits = block_group->length >> block_group->fs_info->sectorsize_bits; 437a565971fSHoward McLauchlan start_bit = find_next_bit_le(bitmap, nrbits, 0); 438a565971fSHoward McLauchlan 439a565971fSHoward McLauchlan while (start_bit < nrbits) { 440a565971fSHoward McLauchlan end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit); 441a565971fSHoward McLauchlan ASSERT(start_bit < end_bit); 442a565971fSHoward McLauchlan 443a565971fSHoward McLauchlan key.objectid = start + start_bit * block_group->fs_info->sectorsize; 444a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 445a565971fSHoward McLauchlan key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize; 446a5ed9182SOmar Sandoval 447a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 448a5ed9182SOmar Sandoval if (ret) 449a5ed9182SOmar Sandoval goto out; 450a5ed9182SOmar Sandoval btrfs_release_path(path); 451a5ed9182SOmar Sandoval 452a5ed9182SOmar Sandoval extent_count++; 453a5ed9182SOmar Sandoval 454a565971fSHoward McLauchlan start_bit = find_next_bit_le(bitmap, nrbits, end_bit); 455a5ed9182SOmar Sandoval } 456a5ed9182SOmar Sandoval 457a5ed9182SOmar Sandoval if (extent_count != expected_extent_count) { 4585d163e0eSJeff Mahoney btrfs_err(fs_info, 4595d163e0eSJeff Mahoney "incorrect extent count for %llu; counted %u, expected %u", 460b3470b5dSDavid Sterba block_group->start, extent_count, 461a5ed9182SOmar Sandoval expected_extent_count); 462a5ed9182SOmar Sandoval ASSERT(0); 463a5ed9182SOmar Sandoval ret = -EIO; 464a5ed9182SOmar Sandoval goto out; 465a5ed9182SOmar Sandoval } 466a5ed9182SOmar Sandoval 467a5ed9182SOmar Sandoval ret = 0; 468a5ed9182SOmar Sandoval out: 46979b134a2SDavid Sterba kvfree(bitmap); 470a5ed9182SOmar Sandoval if (ret) 47166642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 472a5ed9182SOmar Sandoval return ret; 473a5ed9182SOmar Sandoval } 474a5ed9182SOmar Sandoval 475a5ed9182SOmar Sandoval static int update_free_space_extent_count(struct btrfs_trans_handle *trans, 47632da5386SDavid Sterba struct btrfs_block_group *block_group, 477a5ed9182SOmar Sandoval struct btrfs_path *path, 478a5ed9182SOmar Sandoval int new_extents) 479a5ed9182SOmar Sandoval { 480a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 481a5ed9182SOmar Sandoval u32 flags; 482a5ed9182SOmar Sandoval u32 extent_count; 483a5ed9182SOmar Sandoval int ret = 0; 484a5ed9182SOmar Sandoval 485a5ed9182SOmar Sandoval if (new_extents == 0) 486a5ed9182SOmar Sandoval return 0; 487a5ed9182SOmar Sandoval 4882ccf545eSDavid Sterba info = search_free_space_info(trans, block_group, path, 1); 489a5ed9182SOmar Sandoval if (IS_ERR(info)) { 490a5ed9182SOmar Sandoval ret = PTR_ERR(info); 491a5ed9182SOmar Sandoval goto out; 492a5ed9182SOmar Sandoval } 493a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(path->nodes[0], info); 494a5ed9182SOmar Sandoval extent_count = btrfs_free_space_extent_count(path->nodes[0], info); 495a5ed9182SOmar Sandoval 496a5ed9182SOmar Sandoval extent_count += new_extents; 497a5ed9182SOmar Sandoval btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count); 498a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(path->nodes[0]); 499a5ed9182SOmar Sandoval btrfs_release_path(path); 500a5ed9182SOmar Sandoval 501a5ed9182SOmar Sandoval if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) && 502a5ed9182SOmar Sandoval extent_count > block_group->bitmap_high_thresh) { 503719fb4deSNikolay Borisov ret = convert_free_space_to_bitmaps(trans, block_group, path); 504a5ed9182SOmar Sandoval } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) && 505a5ed9182SOmar Sandoval extent_count < block_group->bitmap_low_thresh) { 5065296c2bfSNikolay Borisov ret = convert_free_space_to_extents(trans, block_group, path); 507a5ed9182SOmar Sandoval } 508a5ed9182SOmar Sandoval 509a5ed9182SOmar Sandoval out: 510a5ed9182SOmar Sandoval return ret; 511a5ed9182SOmar Sandoval } 512a5ed9182SOmar Sandoval 513ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 51432da5386SDavid Sterba int free_space_test_bit(struct btrfs_block_group *block_group, 515a5ed9182SOmar Sandoval struct btrfs_path *path, u64 offset) 516a5ed9182SOmar Sandoval { 517a5ed9182SOmar Sandoval struct extent_buffer *leaf; 518a5ed9182SOmar Sandoval struct btrfs_key key; 519a5ed9182SOmar Sandoval u64 found_start, found_end; 520a5ed9182SOmar Sandoval unsigned long ptr, i; 521a5ed9182SOmar Sandoval 522a5ed9182SOmar Sandoval leaf = path->nodes[0]; 523a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 524a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 525a5ed9182SOmar Sandoval 526a5ed9182SOmar Sandoval found_start = key.objectid; 527a5ed9182SOmar Sandoval found_end = key.objectid + key.offset; 528a5ed9182SOmar Sandoval ASSERT(offset >= found_start && offset < found_end); 529a5ed9182SOmar Sandoval 530a5ed9182SOmar Sandoval ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 531da17066cSJeff Mahoney i = div_u64(offset - found_start, 532da17066cSJeff Mahoney block_group->fs_info->sectorsize); 533a5ed9182SOmar Sandoval return !!extent_buffer_test_bit(leaf, ptr, i); 534a5ed9182SOmar Sandoval } 535a5ed9182SOmar Sandoval 53632da5386SDavid Sterba static void free_space_set_bits(struct btrfs_block_group *block_group, 537a5ed9182SOmar Sandoval struct btrfs_path *path, u64 *start, u64 *size, 538a5ed9182SOmar Sandoval int bit) 539a5ed9182SOmar Sandoval { 5400b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = block_group->fs_info; 541a5ed9182SOmar Sandoval struct extent_buffer *leaf; 542a5ed9182SOmar Sandoval struct btrfs_key key; 543a5ed9182SOmar Sandoval u64 end = *start + *size; 544a5ed9182SOmar Sandoval u64 found_start, found_end; 545a5ed9182SOmar Sandoval unsigned long ptr, first, last; 546a5ed9182SOmar Sandoval 547a5ed9182SOmar Sandoval leaf = path->nodes[0]; 548a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 549a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 550a5ed9182SOmar Sandoval 551a5ed9182SOmar Sandoval found_start = key.objectid; 552a5ed9182SOmar Sandoval found_end = key.objectid + key.offset; 553a5ed9182SOmar Sandoval ASSERT(*start >= found_start && *start < found_end); 554a5ed9182SOmar Sandoval ASSERT(end > found_start); 555a5ed9182SOmar Sandoval 556a5ed9182SOmar Sandoval if (end > found_end) 557a5ed9182SOmar Sandoval end = found_end; 558a5ed9182SOmar Sandoval 559a5ed9182SOmar Sandoval ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 560ab108d99SDavid Sterba first = (*start - found_start) >> fs_info->sectorsize_bits; 561ab108d99SDavid Sterba last = (end - found_start) >> fs_info->sectorsize_bits; 562a5ed9182SOmar Sandoval if (bit) 563a5ed9182SOmar Sandoval extent_buffer_bitmap_set(leaf, ptr, first, last - first); 564a5ed9182SOmar Sandoval else 565a5ed9182SOmar Sandoval extent_buffer_bitmap_clear(leaf, ptr, first, last - first); 566a5ed9182SOmar Sandoval btrfs_mark_buffer_dirty(leaf); 567a5ed9182SOmar Sandoval 568a5ed9182SOmar Sandoval *size -= end - *start; 569a5ed9182SOmar Sandoval *start = end; 570a5ed9182SOmar Sandoval } 571a5ed9182SOmar Sandoval 572a5ed9182SOmar Sandoval /* 573a5ed9182SOmar Sandoval * We can't use btrfs_next_item() in modify_free_space_bitmap() because 574a5ed9182SOmar Sandoval * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy 575a5ed9182SOmar Sandoval * tree walking in btrfs_next_leaf() anyways because we know exactly what we're 576a5ed9182SOmar Sandoval * looking for. 577a5ed9182SOmar Sandoval */ 578a5ed9182SOmar Sandoval static int free_space_next_bitmap(struct btrfs_trans_handle *trans, 579a5ed9182SOmar Sandoval struct btrfs_root *root, struct btrfs_path *p) 580a5ed9182SOmar Sandoval { 581a5ed9182SOmar Sandoval struct btrfs_key key; 582a5ed9182SOmar Sandoval 583a5ed9182SOmar Sandoval if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) { 584a5ed9182SOmar Sandoval p->slots[0]++; 585a5ed9182SOmar Sandoval return 0; 586a5ed9182SOmar Sandoval } 587a5ed9182SOmar Sandoval 588a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]); 589a5ed9182SOmar Sandoval btrfs_release_path(p); 590a5ed9182SOmar Sandoval 591a5ed9182SOmar Sandoval key.objectid += key.offset; 592a5ed9182SOmar Sandoval key.type = (u8)-1; 593a5ed9182SOmar Sandoval key.offset = (u64)-1; 594a5ed9182SOmar Sandoval 595a5ed9182SOmar Sandoval return btrfs_search_prev_slot(trans, root, &key, p, 0, 1); 596a5ed9182SOmar Sandoval } 597a5ed9182SOmar Sandoval 598a5ed9182SOmar Sandoval /* 599a5ed9182SOmar Sandoval * If remove is 1, then we are removing free space, thus clearing bits in the 600a5ed9182SOmar Sandoval * bitmap. If remove is 0, then we are adding free space, thus setting bits in 601a5ed9182SOmar Sandoval * the bitmap. 602a5ed9182SOmar Sandoval */ 603a5ed9182SOmar Sandoval static int modify_free_space_bitmap(struct btrfs_trans_handle *trans, 60432da5386SDavid Sterba struct btrfs_block_group *block_group, 605a5ed9182SOmar Sandoval struct btrfs_path *path, 606a5ed9182SOmar Sandoval u64 start, u64 size, int remove) 607a5ed9182SOmar Sandoval { 6087939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 609a5ed9182SOmar Sandoval struct btrfs_key key; 610a5ed9182SOmar Sandoval u64 end = start + size; 611a5ed9182SOmar Sandoval u64 cur_start, cur_size; 612a5ed9182SOmar Sandoval int prev_bit, next_bit; 613a5ed9182SOmar Sandoval int new_extents; 614a5ed9182SOmar Sandoval int ret; 615a5ed9182SOmar Sandoval 616a5ed9182SOmar Sandoval /* 617a5ed9182SOmar Sandoval * Read the bit for the block immediately before the extent of space if 618a5ed9182SOmar Sandoval * that block is within the block group. 619a5ed9182SOmar Sandoval */ 620b3470b5dSDavid Sterba if (start > block_group->start) { 621da17066cSJeff Mahoney u64 prev_block = start - block_group->fs_info->sectorsize; 622a5ed9182SOmar Sandoval 623a5ed9182SOmar Sandoval key.objectid = prev_block; 624a5ed9182SOmar Sandoval key.type = (u8)-1; 625a5ed9182SOmar Sandoval key.offset = (u64)-1; 626a5ed9182SOmar Sandoval 627a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); 628a5ed9182SOmar Sandoval if (ret) 629a5ed9182SOmar Sandoval goto out; 630a5ed9182SOmar Sandoval 631a5ed9182SOmar Sandoval prev_bit = free_space_test_bit(block_group, path, prev_block); 632a5ed9182SOmar Sandoval 633a5ed9182SOmar Sandoval /* The previous block may have been in the previous bitmap. */ 634a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 635a5ed9182SOmar Sandoval if (start >= key.objectid + key.offset) { 636a5ed9182SOmar Sandoval ret = free_space_next_bitmap(trans, root, path); 637a5ed9182SOmar Sandoval if (ret) 638a5ed9182SOmar Sandoval goto out; 639a5ed9182SOmar Sandoval } 640a5ed9182SOmar Sandoval } else { 641a5ed9182SOmar Sandoval key.objectid = start; 642a5ed9182SOmar Sandoval key.type = (u8)-1; 643a5ed9182SOmar Sandoval key.offset = (u64)-1; 644a5ed9182SOmar Sandoval 645a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1); 646a5ed9182SOmar Sandoval if (ret) 647a5ed9182SOmar Sandoval goto out; 648a5ed9182SOmar Sandoval 649a5ed9182SOmar Sandoval prev_bit = -1; 650a5ed9182SOmar Sandoval } 651a5ed9182SOmar Sandoval 652a5ed9182SOmar Sandoval /* 653a5ed9182SOmar Sandoval * Iterate over all of the bitmaps overlapped by the extent of space, 654a5ed9182SOmar Sandoval * clearing/setting bits as required. 655a5ed9182SOmar Sandoval */ 656a5ed9182SOmar Sandoval cur_start = start; 657a5ed9182SOmar Sandoval cur_size = size; 658a5ed9182SOmar Sandoval while (1) { 659a5ed9182SOmar Sandoval free_space_set_bits(block_group, path, &cur_start, &cur_size, 660a5ed9182SOmar Sandoval !remove); 661a5ed9182SOmar Sandoval if (cur_size == 0) 662a5ed9182SOmar Sandoval break; 663a5ed9182SOmar Sandoval ret = free_space_next_bitmap(trans, root, path); 664a5ed9182SOmar Sandoval if (ret) 665a5ed9182SOmar Sandoval goto out; 666a5ed9182SOmar Sandoval } 667a5ed9182SOmar Sandoval 668a5ed9182SOmar Sandoval /* 669a5ed9182SOmar Sandoval * Read the bit for the block immediately after the extent of space if 670a5ed9182SOmar Sandoval * that block is within the block group. 671a5ed9182SOmar Sandoval */ 672b3470b5dSDavid Sterba if (end < block_group->start + block_group->length) { 673a5ed9182SOmar Sandoval /* The next block may be in the next bitmap. */ 674a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 675a5ed9182SOmar Sandoval if (end >= key.objectid + key.offset) { 676a5ed9182SOmar Sandoval ret = free_space_next_bitmap(trans, root, path); 677a5ed9182SOmar Sandoval if (ret) 678a5ed9182SOmar Sandoval goto out; 679a5ed9182SOmar Sandoval } 680a5ed9182SOmar Sandoval 681a5ed9182SOmar Sandoval next_bit = free_space_test_bit(block_group, path, end); 682a5ed9182SOmar Sandoval } else { 683a5ed9182SOmar Sandoval next_bit = -1; 684a5ed9182SOmar Sandoval } 685a5ed9182SOmar Sandoval 686a5ed9182SOmar Sandoval if (remove) { 687a5ed9182SOmar Sandoval new_extents = -1; 688a5ed9182SOmar Sandoval if (prev_bit == 1) { 689a5ed9182SOmar Sandoval /* Leftover on the left. */ 690a5ed9182SOmar Sandoval new_extents++; 691a5ed9182SOmar Sandoval } 692a5ed9182SOmar Sandoval if (next_bit == 1) { 693a5ed9182SOmar Sandoval /* Leftover on the right. */ 694a5ed9182SOmar Sandoval new_extents++; 695a5ed9182SOmar Sandoval } 696a5ed9182SOmar Sandoval } else { 697a5ed9182SOmar Sandoval new_extents = 1; 698a5ed9182SOmar Sandoval if (prev_bit == 1) { 699a5ed9182SOmar Sandoval /* Merging with neighbor on the left. */ 700a5ed9182SOmar Sandoval new_extents--; 701a5ed9182SOmar Sandoval } 702a5ed9182SOmar Sandoval if (next_bit == 1) { 703a5ed9182SOmar Sandoval /* Merging with neighbor on the right. */ 704a5ed9182SOmar Sandoval new_extents--; 705a5ed9182SOmar Sandoval } 706a5ed9182SOmar Sandoval } 707a5ed9182SOmar Sandoval 708a5ed9182SOmar Sandoval btrfs_release_path(path); 709690d7682SNikolay Borisov ret = update_free_space_extent_count(trans, block_group, path, 710a5ed9182SOmar Sandoval new_extents); 711a5ed9182SOmar Sandoval 712a5ed9182SOmar Sandoval out: 713a5ed9182SOmar Sandoval return ret; 714a5ed9182SOmar Sandoval } 715a5ed9182SOmar Sandoval 716a5ed9182SOmar Sandoval static int remove_free_space_extent(struct btrfs_trans_handle *trans, 71732da5386SDavid Sterba struct btrfs_block_group *block_group, 718a5ed9182SOmar Sandoval struct btrfs_path *path, 719a5ed9182SOmar Sandoval u64 start, u64 size) 720a5ed9182SOmar Sandoval { 7217939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 722a5ed9182SOmar Sandoval struct btrfs_key key; 723a5ed9182SOmar Sandoval u64 found_start, found_end; 724a5ed9182SOmar Sandoval u64 end = start + size; 725a5ed9182SOmar Sandoval int new_extents = -1; 726a5ed9182SOmar Sandoval int ret; 727a5ed9182SOmar Sandoval 728a5ed9182SOmar Sandoval key.objectid = start; 729a5ed9182SOmar Sandoval key.type = (u8)-1; 730a5ed9182SOmar Sandoval key.offset = (u64)-1; 731a5ed9182SOmar Sandoval 732a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 733a5ed9182SOmar Sandoval if (ret) 734a5ed9182SOmar Sandoval goto out; 735a5ed9182SOmar Sandoval 736a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 737a5ed9182SOmar Sandoval 738a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); 739a5ed9182SOmar Sandoval 740a5ed9182SOmar Sandoval found_start = key.objectid; 741a5ed9182SOmar Sandoval found_end = key.objectid + key.offset; 742a5ed9182SOmar Sandoval ASSERT(start >= found_start && end <= found_end); 743a5ed9182SOmar Sandoval 744a5ed9182SOmar Sandoval /* 745a5ed9182SOmar Sandoval * Okay, now that we've found the free space extent which contains the 746a5ed9182SOmar Sandoval * free space that we are removing, there are four cases: 747a5ed9182SOmar Sandoval * 748a5ed9182SOmar Sandoval * 1. We're using the whole extent: delete the key we found and 749a5ed9182SOmar Sandoval * decrement the free space extent count. 750a5ed9182SOmar Sandoval * 2. We are using part of the extent starting at the beginning: delete 751a5ed9182SOmar Sandoval * the key we found and insert a new key representing the leftover at 752a5ed9182SOmar Sandoval * the end. There is no net change in the number of extents. 753a5ed9182SOmar Sandoval * 3. We are using part of the extent ending at the end: delete the key 754a5ed9182SOmar Sandoval * we found and insert a new key representing the leftover at the 755a5ed9182SOmar Sandoval * beginning. There is no net change in the number of extents. 756a5ed9182SOmar Sandoval * 4. We are using part of the extent in the middle: delete the key we 757a5ed9182SOmar Sandoval * found and insert two new keys representing the leftovers on each 758a5ed9182SOmar Sandoval * side. Where we used to have one extent, we now have two, so increment 759a5ed9182SOmar Sandoval * the extent count. We may need to convert the block group to bitmaps 760a5ed9182SOmar Sandoval * as a result. 761a5ed9182SOmar Sandoval */ 762a5ed9182SOmar Sandoval 763a5ed9182SOmar Sandoval /* Delete the existing key (cases 1-4). */ 764a5ed9182SOmar Sandoval ret = btrfs_del_item(trans, root, path); 765a5ed9182SOmar Sandoval if (ret) 766a5ed9182SOmar Sandoval goto out; 767a5ed9182SOmar Sandoval 768a5ed9182SOmar Sandoval /* Add a key for leftovers at the beginning (cases 3 and 4). */ 769a5ed9182SOmar Sandoval if (start > found_start) { 770a5ed9182SOmar Sandoval key.objectid = found_start; 771a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 772a5ed9182SOmar Sandoval key.offset = start - found_start; 773a5ed9182SOmar Sandoval 774a5ed9182SOmar Sandoval btrfs_release_path(path); 775a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 776a5ed9182SOmar Sandoval if (ret) 777a5ed9182SOmar Sandoval goto out; 778a5ed9182SOmar Sandoval new_extents++; 779a5ed9182SOmar Sandoval } 780a5ed9182SOmar Sandoval 781a5ed9182SOmar Sandoval /* Add a key for leftovers at the end (cases 2 and 4). */ 782a5ed9182SOmar Sandoval if (end < found_end) { 783a5ed9182SOmar Sandoval key.objectid = end; 784a5ed9182SOmar Sandoval key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 785a5ed9182SOmar Sandoval key.offset = found_end - end; 786a5ed9182SOmar Sandoval 787a5ed9182SOmar Sandoval btrfs_release_path(path); 788a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &key, 0); 789a5ed9182SOmar Sandoval if (ret) 790a5ed9182SOmar Sandoval goto out; 791a5ed9182SOmar Sandoval new_extents++; 792a5ed9182SOmar Sandoval } 793a5ed9182SOmar Sandoval 794a5ed9182SOmar Sandoval btrfs_release_path(path); 795690d7682SNikolay Borisov ret = update_free_space_extent_count(trans, block_group, path, 796a5ed9182SOmar Sandoval new_extents); 797a5ed9182SOmar Sandoval 798a5ed9182SOmar Sandoval out: 799a5ed9182SOmar Sandoval return ret; 800a5ed9182SOmar Sandoval } 801a5ed9182SOmar Sandoval 802ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 803a5ed9182SOmar Sandoval int __remove_from_free_space_tree(struct btrfs_trans_handle *trans, 80432da5386SDavid Sterba struct btrfs_block_group *block_group, 805a5ed9182SOmar Sandoval struct btrfs_path *path, u64 start, u64 size) 806a5ed9182SOmar Sandoval { 807a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 808a5ed9182SOmar Sandoval u32 flags; 809a5ed9182SOmar Sandoval int ret; 810a5ed9182SOmar Sandoval 8110d7764ffSDavid Sterba if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { 8129a7e0f92SNikolay Borisov ret = __add_block_group_free_space(trans, block_group, path); 813a5ed9182SOmar Sandoval if (ret) 814a5ed9182SOmar Sandoval return ret; 815a5ed9182SOmar Sandoval } 816a5ed9182SOmar Sandoval 8172ccf545eSDavid Sterba info = search_free_space_info(NULL, block_group, path, 0); 818a5ed9182SOmar Sandoval if (IS_ERR(info)) 819a5ed9182SOmar Sandoval return PTR_ERR(info); 820a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(path->nodes[0], info); 821a5ed9182SOmar Sandoval btrfs_release_path(path); 822a5ed9182SOmar Sandoval 823a5ed9182SOmar Sandoval if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { 82485a7ef13SNikolay Borisov return modify_free_space_bitmap(trans, block_group, path, 82585a7ef13SNikolay Borisov start, size, 1); 826a5ed9182SOmar Sandoval } else { 827e581168dSNikolay Borisov return remove_free_space_extent(trans, block_group, path, 828e581168dSNikolay Borisov start, size); 829a5ed9182SOmar Sandoval } 830a5ed9182SOmar Sandoval } 831a5ed9182SOmar Sandoval 832a5ed9182SOmar Sandoval int remove_from_free_space_tree(struct btrfs_trans_handle *trans, 833a5ed9182SOmar Sandoval u64 start, u64 size) 834a5ed9182SOmar Sandoval { 83532da5386SDavid Sterba struct btrfs_block_group *block_group; 836a5ed9182SOmar Sandoval struct btrfs_path *path; 837a5ed9182SOmar Sandoval int ret; 838a5ed9182SOmar Sandoval 83925a356d3SNikolay Borisov if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 840a5ed9182SOmar Sandoval return 0; 841a5ed9182SOmar Sandoval 842a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 843a5ed9182SOmar Sandoval if (!path) { 844a5ed9182SOmar Sandoval ret = -ENOMEM; 845a5ed9182SOmar Sandoval goto out; 846a5ed9182SOmar Sandoval } 847a5ed9182SOmar Sandoval 84825a356d3SNikolay Borisov block_group = btrfs_lookup_block_group(trans->fs_info, start); 849a5ed9182SOmar Sandoval if (!block_group) { 850a5ed9182SOmar Sandoval ASSERT(0); 851a5ed9182SOmar Sandoval ret = -ENOENT; 852a5ed9182SOmar Sandoval goto out; 853a5ed9182SOmar Sandoval } 854a5ed9182SOmar Sandoval 855a5ed9182SOmar Sandoval mutex_lock(&block_group->free_space_lock); 856c31683a6SNikolay Borisov ret = __remove_from_free_space_tree(trans, block_group, path, start, 857c31683a6SNikolay Borisov size); 858a5ed9182SOmar Sandoval mutex_unlock(&block_group->free_space_lock); 859a5ed9182SOmar Sandoval 860a5ed9182SOmar Sandoval btrfs_put_block_group(block_group); 861a5ed9182SOmar Sandoval out: 862a5ed9182SOmar Sandoval btrfs_free_path(path); 863a5ed9182SOmar Sandoval if (ret) 86466642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 865a5ed9182SOmar Sandoval return ret; 866a5ed9182SOmar Sandoval } 867a5ed9182SOmar Sandoval 868a5ed9182SOmar Sandoval static int add_free_space_extent(struct btrfs_trans_handle *trans, 86932da5386SDavid Sterba struct btrfs_block_group *block_group, 870a5ed9182SOmar Sandoval struct btrfs_path *path, 871a5ed9182SOmar Sandoval u64 start, u64 size) 872a5ed9182SOmar Sandoval { 8737939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 874a5ed9182SOmar Sandoval struct btrfs_key key, new_key; 875a5ed9182SOmar Sandoval u64 found_start, found_end; 876a5ed9182SOmar Sandoval u64 end = start + size; 877a5ed9182SOmar Sandoval int new_extents = 1; 878a5ed9182SOmar Sandoval int ret; 879a5ed9182SOmar Sandoval 880a5ed9182SOmar Sandoval /* 881a5ed9182SOmar Sandoval * We are adding a new extent of free space, but we need to merge 882a5ed9182SOmar Sandoval * extents. There are four cases here: 883a5ed9182SOmar Sandoval * 884a5ed9182SOmar Sandoval * 1. The new extent does not have any immediate neighbors to merge 885a5ed9182SOmar Sandoval * with: add the new key and increment the free space extent count. We 886a5ed9182SOmar Sandoval * may need to convert the block group to bitmaps as a result. 887a5ed9182SOmar Sandoval * 2. The new extent has an immediate neighbor before it: remove the 888a5ed9182SOmar Sandoval * previous key and insert a new key combining both of them. There is no 889a5ed9182SOmar Sandoval * net change in the number of extents. 890a5ed9182SOmar Sandoval * 3. The new extent has an immediate neighbor after it: remove the next 891a5ed9182SOmar Sandoval * key and insert a new key combining both of them. There is no net 892a5ed9182SOmar Sandoval * change in the number of extents. 893a5ed9182SOmar Sandoval * 4. The new extent has immediate neighbors on both sides: remove both 894a5ed9182SOmar Sandoval * of the keys and insert a new key combining all of them. Where we used 895a5ed9182SOmar Sandoval * to have two extents, we now have one, so decrement the extent count. 896a5ed9182SOmar Sandoval */ 897a5ed9182SOmar Sandoval 898a5ed9182SOmar Sandoval new_key.objectid = start; 899a5ed9182SOmar Sandoval new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY; 900a5ed9182SOmar Sandoval new_key.offset = size; 901a5ed9182SOmar Sandoval 902a5ed9182SOmar Sandoval /* Search for a neighbor on the left. */ 903b3470b5dSDavid Sterba if (start == block_group->start) 904a5ed9182SOmar Sandoval goto right; 905a5ed9182SOmar Sandoval key.objectid = start - 1; 906a5ed9182SOmar Sandoval key.type = (u8)-1; 907a5ed9182SOmar Sandoval key.offset = (u64)-1; 908a5ed9182SOmar Sandoval 909a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 910a5ed9182SOmar Sandoval if (ret) 911a5ed9182SOmar Sandoval goto out; 912a5ed9182SOmar Sandoval 913a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 914a5ed9182SOmar Sandoval 915a5ed9182SOmar Sandoval if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { 916a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); 917a5ed9182SOmar Sandoval btrfs_release_path(path); 918a5ed9182SOmar Sandoval goto right; 919a5ed9182SOmar Sandoval } 920a5ed9182SOmar Sandoval 921a5ed9182SOmar Sandoval found_start = key.objectid; 922a5ed9182SOmar Sandoval found_end = key.objectid + key.offset; 923b3470b5dSDavid Sterba ASSERT(found_start >= block_group->start && 924b3470b5dSDavid Sterba found_end > block_group->start); 925a5ed9182SOmar Sandoval ASSERT(found_start < start && found_end <= start); 926a5ed9182SOmar Sandoval 927a5ed9182SOmar Sandoval /* 928a5ed9182SOmar Sandoval * Delete the neighbor on the left and absorb it into the new key (cases 929a5ed9182SOmar Sandoval * 2 and 4). 930a5ed9182SOmar Sandoval */ 931a5ed9182SOmar Sandoval if (found_end == start) { 932a5ed9182SOmar Sandoval ret = btrfs_del_item(trans, root, path); 933a5ed9182SOmar Sandoval if (ret) 934a5ed9182SOmar Sandoval goto out; 935a5ed9182SOmar Sandoval new_key.objectid = found_start; 936a5ed9182SOmar Sandoval new_key.offset += key.offset; 937a5ed9182SOmar Sandoval new_extents--; 938a5ed9182SOmar Sandoval } 939a5ed9182SOmar Sandoval btrfs_release_path(path); 940a5ed9182SOmar Sandoval 941a5ed9182SOmar Sandoval right: 942a5ed9182SOmar Sandoval /* Search for a neighbor on the right. */ 943b3470b5dSDavid Sterba if (end == block_group->start + block_group->length) 944a5ed9182SOmar Sandoval goto insert; 945a5ed9182SOmar Sandoval key.objectid = end; 946a5ed9182SOmar Sandoval key.type = (u8)-1; 947a5ed9182SOmar Sandoval key.offset = (u64)-1; 948a5ed9182SOmar Sandoval 949a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 950a5ed9182SOmar Sandoval if (ret) 951a5ed9182SOmar Sandoval goto out; 952a5ed9182SOmar Sandoval 953a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 954a5ed9182SOmar Sandoval 955a5ed9182SOmar Sandoval if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { 956a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY); 957a5ed9182SOmar Sandoval btrfs_release_path(path); 958a5ed9182SOmar Sandoval goto insert; 959a5ed9182SOmar Sandoval } 960a5ed9182SOmar Sandoval 961a5ed9182SOmar Sandoval found_start = key.objectid; 962a5ed9182SOmar Sandoval found_end = key.objectid + key.offset; 963b3470b5dSDavid Sterba ASSERT(found_start >= block_group->start && 964b3470b5dSDavid Sterba found_end > block_group->start); 965a5ed9182SOmar Sandoval ASSERT((found_start < start && found_end <= start) || 966a5ed9182SOmar Sandoval (found_start >= end && found_end > end)); 967a5ed9182SOmar Sandoval 968a5ed9182SOmar Sandoval /* 969a5ed9182SOmar Sandoval * Delete the neighbor on the right and absorb it into the new key 970a5ed9182SOmar Sandoval * (cases 3 and 4). 971a5ed9182SOmar Sandoval */ 972a5ed9182SOmar Sandoval if (found_start == end) { 973a5ed9182SOmar Sandoval ret = btrfs_del_item(trans, root, path); 974a5ed9182SOmar Sandoval if (ret) 975a5ed9182SOmar Sandoval goto out; 976a5ed9182SOmar Sandoval new_key.offset += key.offset; 977a5ed9182SOmar Sandoval new_extents--; 978a5ed9182SOmar Sandoval } 979a5ed9182SOmar Sandoval btrfs_release_path(path); 980a5ed9182SOmar Sandoval 981a5ed9182SOmar Sandoval insert: 982a5ed9182SOmar Sandoval /* Insert the new key (cases 1-4). */ 983a5ed9182SOmar Sandoval ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0); 984a5ed9182SOmar Sandoval if (ret) 985a5ed9182SOmar Sandoval goto out; 986a5ed9182SOmar Sandoval 987a5ed9182SOmar Sandoval btrfs_release_path(path); 988690d7682SNikolay Borisov ret = update_free_space_extent_count(trans, block_group, path, 989a5ed9182SOmar Sandoval new_extents); 990a5ed9182SOmar Sandoval 991a5ed9182SOmar Sandoval out: 992a5ed9182SOmar Sandoval return ret; 993a5ed9182SOmar Sandoval } 994a5ed9182SOmar Sandoval 995ce9f967fSJohannes Thumshirn EXPORT_FOR_TESTS 996a5ed9182SOmar Sandoval int __add_to_free_space_tree(struct btrfs_trans_handle *trans, 99732da5386SDavid Sterba struct btrfs_block_group *block_group, 998a5ed9182SOmar Sandoval struct btrfs_path *path, u64 start, u64 size) 999a5ed9182SOmar Sandoval { 1000a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 1001a5ed9182SOmar Sandoval u32 flags; 1002a5ed9182SOmar Sandoval int ret; 1003a5ed9182SOmar Sandoval 10040d7764ffSDavid Sterba if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { 10059a7e0f92SNikolay Borisov ret = __add_block_group_free_space(trans, block_group, path); 1006a5ed9182SOmar Sandoval if (ret) 1007a5ed9182SOmar Sandoval return ret; 1008a5ed9182SOmar Sandoval } 1009a5ed9182SOmar Sandoval 10102ccf545eSDavid Sterba info = search_free_space_info(NULL, block_group, path, 0); 1011a5ed9182SOmar Sandoval if (IS_ERR(info)) 1012a5ed9182SOmar Sandoval return PTR_ERR(info); 1013a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(path->nodes[0], info); 1014a5ed9182SOmar Sandoval btrfs_release_path(path); 1015a5ed9182SOmar Sandoval 1016a5ed9182SOmar Sandoval if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { 101785a7ef13SNikolay Borisov return modify_free_space_bitmap(trans, block_group, path, 101885a7ef13SNikolay Borisov start, size, 0); 1019a5ed9182SOmar Sandoval } else { 10205cb17822SNikolay Borisov return add_free_space_extent(trans, block_group, path, start, 10215cb17822SNikolay Borisov size); 1022a5ed9182SOmar Sandoval } 1023a5ed9182SOmar Sandoval } 1024a5ed9182SOmar Sandoval 1025a5ed9182SOmar Sandoval int add_to_free_space_tree(struct btrfs_trans_handle *trans, 1026a5ed9182SOmar Sandoval u64 start, u64 size) 1027a5ed9182SOmar Sandoval { 102832da5386SDavid Sterba struct btrfs_block_group *block_group; 1029a5ed9182SOmar Sandoval struct btrfs_path *path; 1030a5ed9182SOmar Sandoval int ret; 1031a5ed9182SOmar Sandoval 1032e7355e50SNikolay Borisov if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 1033a5ed9182SOmar Sandoval return 0; 1034a5ed9182SOmar Sandoval 1035a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1036a5ed9182SOmar Sandoval if (!path) { 1037a5ed9182SOmar Sandoval ret = -ENOMEM; 1038a5ed9182SOmar Sandoval goto out; 1039a5ed9182SOmar Sandoval } 1040a5ed9182SOmar Sandoval 1041e7355e50SNikolay Borisov block_group = btrfs_lookup_block_group(trans->fs_info, start); 1042a5ed9182SOmar Sandoval if (!block_group) { 1043a5ed9182SOmar Sandoval ASSERT(0); 1044a5ed9182SOmar Sandoval ret = -ENOENT; 1045a5ed9182SOmar Sandoval goto out; 1046a5ed9182SOmar Sandoval } 1047a5ed9182SOmar Sandoval 1048a5ed9182SOmar Sandoval mutex_lock(&block_group->free_space_lock); 10492d5cffa1SNikolay Borisov ret = __add_to_free_space_tree(trans, block_group, path, start, size); 1050a5ed9182SOmar Sandoval mutex_unlock(&block_group->free_space_lock); 1051a5ed9182SOmar Sandoval 1052a5ed9182SOmar Sandoval btrfs_put_block_group(block_group); 1053a5ed9182SOmar Sandoval out: 1054a5ed9182SOmar Sandoval btrfs_free_path(path); 1055a5ed9182SOmar Sandoval if (ret) 105666642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 1057a5ed9182SOmar Sandoval return ret; 1058a5ed9182SOmar Sandoval } 1059a5ed9182SOmar Sandoval 1060a5ed9182SOmar Sandoval /* 1061a5ed9182SOmar Sandoval * Populate the free space tree by walking the extent tree. Operations on the 1062a5ed9182SOmar Sandoval * extent tree that happen as a result of writes to the free space tree will go 1063a5ed9182SOmar Sandoval * through the normal add/remove hooks. 1064a5ed9182SOmar Sandoval */ 1065a5ed9182SOmar Sandoval static int populate_free_space_tree(struct btrfs_trans_handle *trans, 106632da5386SDavid Sterba struct btrfs_block_group *block_group) 1067a5ed9182SOmar Sandoval { 106829cbcf40SJosef Bacik struct btrfs_root *extent_root; 1069a5ed9182SOmar Sandoval struct btrfs_path *path, *path2; 1070a5ed9182SOmar Sandoval struct btrfs_key key; 1071a5ed9182SOmar Sandoval u64 start, end; 1072a5ed9182SOmar Sandoval int ret; 1073a5ed9182SOmar Sandoval 1074a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1075a5ed9182SOmar Sandoval if (!path) 1076a5ed9182SOmar Sandoval return -ENOMEM; 1077019599adSGu Jinxiang path->reada = READA_FORWARD; 1078a5ed9182SOmar Sandoval 1079a5ed9182SOmar Sandoval path2 = btrfs_alloc_path(); 1080a5ed9182SOmar Sandoval if (!path2) { 1081a5ed9182SOmar Sandoval btrfs_free_path(path); 1082a5ed9182SOmar Sandoval return -ENOMEM; 1083a5ed9182SOmar Sandoval } 1084a5ed9182SOmar Sandoval 108566afee18SNikolay Borisov ret = add_new_free_space_info(trans, block_group, path2); 1086a5ed9182SOmar Sandoval if (ret) 1087a5ed9182SOmar Sandoval goto out; 1088a5ed9182SOmar Sandoval 1089511711afSChris Mason mutex_lock(&block_group->free_space_lock); 1090511711afSChris Mason 1091a5ed9182SOmar Sandoval /* 1092a5ed9182SOmar Sandoval * Iterate through all of the extent and metadata items in this block 1093a5ed9182SOmar Sandoval * group, adding the free space between them and the free space at the 1094a5ed9182SOmar Sandoval * end. Note that EXTENT_ITEM and METADATA_ITEM are less than 1095a5ed9182SOmar Sandoval * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's 1096a5ed9182SOmar Sandoval * contained in. 1097a5ed9182SOmar Sandoval */ 1098b3470b5dSDavid Sterba key.objectid = block_group->start; 1099a5ed9182SOmar Sandoval key.type = BTRFS_EXTENT_ITEM_KEY; 1100a5ed9182SOmar Sandoval key.offset = 0; 1101a5ed9182SOmar Sandoval 110229cbcf40SJosef Bacik extent_root = btrfs_extent_root(trans->fs_info, key.objectid); 1103a5ed9182SOmar Sandoval ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0); 1104a5ed9182SOmar Sandoval if (ret < 0) 1105511711afSChris Mason goto out_locked; 1106a5ed9182SOmar Sandoval ASSERT(ret == 0); 1107a5ed9182SOmar Sandoval 1108b3470b5dSDavid Sterba start = block_group->start; 1109b3470b5dSDavid Sterba end = block_group->start + block_group->length; 1110a5ed9182SOmar Sandoval while (1) { 1111a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1112a5ed9182SOmar Sandoval 1113a5ed9182SOmar Sandoval if (key.type == BTRFS_EXTENT_ITEM_KEY || 1114a5ed9182SOmar Sandoval key.type == BTRFS_METADATA_ITEM_KEY) { 1115a5ed9182SOmar Sandoval if (key.objectid >= end) 1116a5ed9182SOmar Sandoval break; 1117a5ed9182SOmar Sandoval 1118a5ed9182SOmar Sandoval if (start < key.objectid) { 11192d5cffa1SNikolay Borisov ret = __add_to_free_space_tree(trans, 1120a5ed9182SOmar Sandoval block_group, 1121a5ed9182SOmar Sandoval path2, start, 1122a5ed9182SOmar Sandoval key.objectid - 1123a5ed9182SOmar Sandoval start); 1124a5ed9182SOmar Sandoval if (ret) 1125511711afSChris Mason goto out_locked; 1126a5ed9182SOmar Sandoval } 1127a5ed9182SOmar Sandoval start = key.objectid; 1128a5ed9182SOmar Sandoval if (key.type == BTRFS_METADATA_ITEM_KEY) 1129ffa9a9efSNikolay Borisov start += trans->fs_info->nodesize; 1130a5ed9182SOmar Sandoval else 1131a5ed9182SOmar Sandoval start += key.offset; 1132a5ed9182SOmar Sandoval } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { 1133b3470b5dSDavid Sterba if (key.objectid != block_group->start) 1134a5ed9182SOmar Sandoval break; 1135a5ed9182SOmar Sandoval } 1136a5ed9182SOmar Sandoval 1137a5ed9182SOmar Sandoval ret = btrfs_next_item(extent_root, path); 1138a5ed9182SOmar Sandoval if (ret < 0) 1139511711afSChris Mason goto out_locked; 1140a5ed9182SOmar Sandoval if (ret) 1141a5ed9182SOmar Sandoval break; 1142a5ed9182SOmar Sandoval } 1143a5ed9182SOmar Sandoval if (start < end) { 11442d5cffa1SNikolay Borisov ret = __add_to_free_space_tree(trans, block_group, path2, 11452d5cffa1SNikolay Borisov start, end - start); 1146a5ed9182SOmar Sandoval if (ret) 1147511711afSChris Mason goto out_locked; 1148a5ed9182SOmar Sandoval } 1149a5ed9182SOmar Sandoval 1150a5ed9182SOmar Sandoval ret = 0; 1151511711afSChris Mason out_locked: 1152511711afSChris Mason mutex_unlock(&block_group->free_space_lock); 1153a5ed9182SOmar Sandoval out: 1154a5ed9182SOmar Sandoval btrfs_free_path(path2); 1155a5ed9182SOmar Sandoval btrfs_free_path(path); 1156a5ed9182SOmar Sandoval return ret; 1157a5ed9182SOmar Sandoval } 1158a5ed9182SOmar Sandoval 1159a5ed9182SOmar Sandoval int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info) 1160a5ed9182SOmar Sandoval { 1161a5ed9182SOmar Sandoval struct btrfs_trans_handle *trans; 1162a5ed9182SOmar Sandoval struct btrfs_root *tree_root = fs_info->tree_root; 1163a5ed9182SOmar Sandoval struct btrfs_root *free_space_root; 116432da5386SDavid Sterba struct btrfs_block_group *block_group; 1165a5ed9182SOmar Sandoval struct rb_node *node; 1166a5ed9182SOmar Sandoval int ret; 1167a5ed9182SOmar Sandoval 1168a5ed9182SOmar Sandoval trans = btrfs_start_transaction(tree_root, 0); 1169a5ed9182SOmar Sandoval if (IS_ERR(trans)) 1170a5ed9182SOmar Sandoval return PTR_ERR(trans); 1171a5ed9182SOmar Sandoval 1172afcdd129SJosef Bacik set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 11732f96e402SJosef Bacik set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 11749b7a2440SDavid Sterba free_space_root = btrfs_create_tree(trans, 1175a5ed9182SOmar Sandoval BTRFS_FREE_SPACE_TREE_OBJECTID); 1176a5ed9182SOmar Sandoval if (IS_ERR(free_space_root)) { 1177a5ed9182SOmar Sandoval ret = PTR_ERR(free_space_root); 1178a5ed9182SOmar Sandoval goto abort; 1179a5ed9182SOmar Sandoval } 1180abed4aaaSJosef Bacik ret = btrfs_global_root_insert(free_space_root); 1181abed4aaaSJosef Bacik if (ret) { 1182abed4aaaSJosef Bacik btrfs_put_root(free_space_root); 1183abed4aaaSJosef Bacik goto abort; 1184abed4aaaSJosef Bacik } 1185a5ed9182SOmar Sandoval 118608dddb29SFilipe Manana node = rb_first_cached(&fs_info->block_group_cache_tree); 1187a5ed9182SOmar Sandoval while (node) { 118832da5386SDavid Sterba block_group = rb_entry(node, struct btrfs_block_group, 1189a5ed9182SOmar Sandoval cache_node); 1190ffa9a9efSNikolay Borisov ret = populate_free_space_tree(trans, block_group); 1191a5ed9182SOmar Sandoval if (ret) 1192a5ed9182SOmar Sandoval goto abort; 1193a5ed9182SOmar Sandoval node = rb_next(node); 1194a5ed9182SOmar Sandoval } 1195a5ed9182SOmar Sandoval 1196a5ed9182SOmar Sandoval btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE); 11976675df31SOmar Sandoval btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID); 1198afcdd129SJosef Bacik clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 11992f96e402SJosef Bacik ret = btrfs_commit_transaction(trans); 1200a5ed9182SOmar Sandoval 12012f96e402SJosef Bacik /* 12022f96e402SJosef Bacik * Now that we've committed the transaction any reading of our commit 12032f96e402SJosef Bacik * root will be safe, so we can cache from the free space tree now. 12042f96e402SJosef Bacik */ 12052f96e402SJosef Bacik clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 12062f96e402SJosef Bacik return ret; 1207a5ed9182SOmar Sandoval 1208a5ed9182SOmar Sandoval abort: 1209afcdd129SJosef Bacik clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 12102f96e402SJosef Bacik clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 121166642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 12123a45bb20SJeff Mahoney btrfs_end_transaction(trans); 1213a5ed9182SOmar Sandoval return ret; 1214a5ed9182SOmar Sandoval } 1215a5ed9182SOmar Sandoval 1216a5ed9182SOmar Sandoval static int clear_free_space_tree(struct btrfs_trans_handle *trans, 1217a5ed9182SOmar Sandoval struct btrfs_root *root) 1218a5ed9182SOmar Sandoval { 1219a5ed9182SOmar Sandoval struct btrfs_path *path; 1220a5ed9182SOmar Sandoval struct btrfs_key key; 1221a5ed9182SOmar Sandoval int nr; 1222a5ed9182SOmar Sandoval int ret; 1223a5ed9182SOmar Sandoval 1224a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1225a5ed9182SOmar Sandoval if (!path) 1226a5ed9182SOmar Sandoval return -ENOMEM; 1227a5ed9182SOmar Sandoval 1228a5ed9182SOmar Sandoval key.objectid = 0; 1229a5ed9182SOmar Sandoval key.type = 0; 1230a5ed9182SOmar Sandoval key.offset = 0; 1231a5ed9182SOmar Sandoval 1232a5ed9182SOmar Sandoval while (1) { 1233a5ed9182SOmar Sandoval ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 1234a5ed9182SOmar Sandoval if (ret < 0) 1235a5ed9182SOmar Sandoval goto out; 1236a5ed9182SOmar Sandoval 1237a5ed9182SOmar Sandoval nr = btrfs_header_nritems(path->nodes[0]); 1238a5ed9182SOmar Sandoval if (!nr) 1239a5ed9182SOmar Sandoval break; 1240a5ed9182SOmar Sandoval 1241a5ed9182SOmar Sandoval path->slots[0] = 0; 1242a5ed9182SOmar Sandoval ret = btrfs_del_items(trans, root, path, 0, nr); 1243a5ed9182SOmar Sandoval if (ret) 1244a5ed9182SOmar Sandoval goto out; 1245a5ed9182SOmar Sandoval 1246a5ed9182SOmar Sandoval btrfs_release_path(path); 1247a5ed9182SOmar Sandoval } 1248a5ed9182SOmar Sandoval 1249a5ed9182SOmar Sandoval ret = 0; 1250a5ed9182SOmar Sandoval out: 1251a5ed9182SOmar Sandoval btrfs_free_path(path); 1252a5ed9182SOmar Sandoval return ret; 1253a5ed9182SOmar Sandoval } 1254a5ed9182SOmar Sandoval 1255*1d6a4fc8SQu Wenruo int btrfs_delete_free_space_tree(struct btrfs_fs_info *fs_info) 1256a5ed9182SOmar Sandoval { 1257a5ed9182SOmar Sandoval struct btrfs_trans_handle *trans; 1258a5ed9182SOmar Sandoval struct btrfs_root *tree_root = fs_info->tree_root; 1259abed4aaaSJosef Bacik struct btrfs_key key = { 1260abed4aaaSJosef Bacik .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID, 1261abed4aaaSJosef Bacik .type = BTRFS_ROOT_ITEM_KEY, 1262abed4aaaSJosef Bacik .offset = 0, 1263abed4aaaSJosef Bacik }; 1264abed4aaaSJosef Bacik struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); 1265a5ed9182SOmar Sandoval int ret; 1266a5ed9182SOmar Sandoval 1267a5ed9182SOmar Sandoval trans = btrfs_start_transaction(tree_root, 0); 1268a5ed9182SOmar Sandoval if (IS_ERR(trans)) 1269a5ed9182SOmar Sandoval return PTR_ERR(trans); 1270a5ed9182SOmar Sandoval 1271a5ed9182SOmar Sandoval btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE); 12726675df31SOmar Sandoval btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID); 1273a5ed9182SOmar Sandoval 1274a5ed9182SOmar Sandoval ret = clear_free_space_tree(trans, free_space_root); 1275a5ed9182SOmar Sandoval if (ret) 1276a5ed9182SOmar Sandoval goto abort; 1277a5ed9182SOmar Sandoval 1278ab9ce7d4SLu Fengqi ret = btrfs_del_root(trans, &free_space_root->root_key); 1279a5ed9182SOmar Sandoval if (ret) 1280a5ed9182SOmar Sandoval goto abort; 1281a5ed9182SOmar Sandoval 1282abed4aaaSJosef Bacik btrfs_global_root_delete(free_space_root); 1283a5ed9182SOmar Sandoval list_del(&free_space_root->dirty_list); 1284a5ed9182SOmar Sandoval 1285a5ed9182SOmar Sandoval btrfs_tree_lock(free_space_root->node); 1286190a8339SJosef Bacik btrfs_clear_buffer_dirty(trans, free_space_root->node); 1287a5ed9182SOmar Sandoval btrfs_tree_unlock(free_space_root->node); 12887a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(free_space_root), 12897a163608SFilipe Manana free_space_root->node, 0, 1); 1290a5ed9182SOmar Sandoval 129100246528SJosef Bacik btrfs_put_root(free_space_root); 1292a5ed9182SOmar Sandoval 12930bef7109SSahil Kang return btrfs_commit_transaction(trans); 1294a5ed9182SOmar Sandoval 1295a5ed9182SOmar Sandoval abort: 129666642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 12973a45bb20SJeff Mahoney btrfs_end_transaction(trans); 1298a5ed9182SOmar Sandoval return ret; 1299a5ed9182SOmar Sandoval } 1300a5ed9182SOmar Sandoval 1301*1d6a4fc8SQu Wenruo int btrfs_rebuild_free_space_tree(struct btrfs_fs_info *fs_info) 1302*1d6a4fc8SQu Wenruo { 1303*1d6a4fc8SQu Wenruo struct btrfs_trans_handle *trans; 1304*1d6a4fc8SQu Wenruo struct btrfs_key key = { 1305*1d6a4fc8SQu Wenruo .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID, 1306*1d6a4fc8SQu Wenruo .type = BTRFS_ROOT_ITEM_KEY, 1307*1d6a4fc8SQu Wenruo .offset = 0, 1308*1d6a4fc8SQu Wenruo }; 1309*1d6a4fc8SQu Wenruo struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key); 1310*1d6a4fc8SQu Wenruo struct rb_node *node; 1311*1d6a4fc8SQu Wenruo int ret; 1312*1d6a4fc8SQu Wenruo 1313*1d6a4fc8SQu Wenruo trans = btrfs_start_transaction(free_space_root, 1); 1314*1d6a4fc8SQu Wenruo if (IS_ERR(trans)) 1315*1d6a4fc8SQu Wenruo return PTR_ERR(trans); 1316*1d6a4fc8SQu Wenruo 1317*1d6a4fc8SQu Wenruo set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 1318*1d6a4fc8SQu Wenruo set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 1319*1d6a4fc8SQu Wenruo 1320*1d6a4fc8SQu Wenruo ret = clear_free_space_tree(trans, free_space_root); 1321*1d6a4fc8SQu Wenruo if (ret) 1322*1d6a4fc8SQu Wenruo goto abort; 1323*1d6a4fc8SQu Wenruo 1324*1d6a4fc8SQu Wenruo node = rb_first_cached(&fs_info->block_group_cache_tree); 1325*1d6a4fc8SQu Wenruo while (node) { 1326*1d6a4fc8SQu Wenruo struct btrfs_block_group *block_group; 1327*1d6a4fc8SQu Wenruo 1328*1d6a4fc8SQu Wenruo block_group = rb_entry(node, struct btrfs_block_group, 1329*1d6a4fc8SQu Wenruo cache_node); 1330*1d6a4fc8SQu Wenruo ret = populate_free_space_tree(trans, block_group); 1331*1d6a4fc8SQu Wenruo if (ret) 1332*1d6a4fc8SQu Wenruo goto abort; 1333*1d6a4fc8SQu Wenruo node = rb_next(node); 1334*1d6a4fc8SQu Wenruo } 1335*1d6a4fc8SQu Wenruo 1336*1d6a4fc8SQu Wenruo btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE); 1337*1d6a4fc8SQu Wenruo btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID); 1338*1d6a4fc8SQu Wenruo clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags); 1339*1d6a4fc8SQu Wenruo 1340*1d6a4fc8SQu Wenruo ret = btrfs_commit_transaction(trans); 1341*1d6a4fc8SQu Wenruo clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags); 1342*1d6a4fc8SQu Wenruo return ret; 1343*1d6a4fc8SQu Wenruo abort: 1344*1d6a4fc8SQu Wenruo btrfs_abort_transaction(trans, ret); 1345*1d6a4fc8SQu Wenruo btrfs_end_transaction(trans); 1346*1d6a4fc8SQu Wenruo return ret; 1347*1d6a4fc8SQu Wenruo } 1348*1d6a4fc8SQu Wenruo 1349a5ed9182SOmar Sandoval static int __add_block_group_free_space(struct btrfs_trans_handle *trans, 135032da5386SDavid Sterba struct btrfs_block_group *block_group, 1351a5ed9182SOmar Sandoval struct btrfs_path *path) 1352a5ed9182SOmar Sandoval { 1353a5ed9182SOmar Sandoval int ret; 1354a5ed9182SOmar Sandoval 13550d7764ffSDavid Sterba clear_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags); 1356a5ed9182SOmar Sandoval 135766afee18SNikolay Borisov ret = add_new_free_space_info(trans, block_group, path); 1358a5ed9182SOmar Sandoval if (ret) 1359a5ed9182SOmar Sandoval return ret; 1360a5ed9182SOmar Sandoval 13612d5cffa1SNikolay Borisov return __add_to_free_space_tree(trans, block_group, path, 1362b3470b5dSDavid Sterba block_group->start, 1363b3470b5dSDavid Sterba block_group->length); 1364a5ed9182SOmar Sandoval } 1365a5ed9182SOmar Sandoval 1366a5ed9182SOmar Sandoval int add_block_group_free_space(struct btrfs_trans_handle *trans, 136732da5386SDavid Sterba struct btrfs_block_group *block_group) 1368a5ed9182SOmar Sandoval { 1369e4e0711cSNikolay Borisov struct btrfs_fs_info *fs_info = trans->fs_info; 1370a5ed9182SOmar Sandoval struct btrfs_path *path = NULL; 1371a5ed9182SOmar Sandoval int ret = 0; 1372a5ed9182SOmar Sandoval 1373a5ed9182SOmar Sandoval if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE)) 1374a5ed9182SOmar Sandoval return 0; 1375a5ed9182SOmar Sandoval 1376a5ed9182SOmar Sandoval mutex_lock(&block_group->free_space_lock); 13770d7764ffSDavid Sterba if (!test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) 1378a5ed9182SOmar Sandoval goto out; 1379a5ed9182SOmar Sandoval 1380a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1381a5ed9182SOmar Sandoval if (!path) { 1382a5ed9182SOmar Sandoval ret = -ENOMEM; 1383a5ed9182SOmar Sandoval goto out; 1384a5ed9182SOmar Sandoval } 1385a5ed9182SOmar Sandoval 13869a7e0f92SNikolay Borisov ret = __add_block_group_free_space(trans, block_group, path); 1387a5ed9182SOmar Sandoval 1388a5ed9182SOmar Sandoval out: 1389a5ed9182SOmar Sandoval btrfs_free_path(path); 1390a5ed9182SOmar Sandoval mutex_unlock(&block_group->free_space_lock); 1391a5ed9182SOmar Sandoval if (ret) 139266642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 1393a5ed9182SOmar Sandoval return ret; 1394a5ed9182SOmar Sandoval } 1395a5ed9182SOmar Sandoval 1396a5ed9182SOmar Sandoval int remove_block_group_free_space(struct btrfs_trans_handle *trans, 139732da5386SDavid Sterba struct btrfs_block_group *block_group) 1398a5ed9182SOmar Sandoval { 13997939dd9fSJosef Bacik struct btrfs_root *root = btrfs_free_space_root(block_group); 1400a5ed9182SOmar Sandoval struct btrfs_path *path; 1401a5ed9182SOmar Sandoval struct btrfs_key key, found_key; 1402a5ed9182SOmar Sandoval struct extent_buffer *leaf; 1403a5ed9182SOmar Sandoval u64 start, end; 1404a5ed9182SOmar Sandoval int done = 0, nr; 1405a5ed9182SOmar Sandoval int ret; 1406a5ed9182SOmar Sandoval 1407f3f72779SNikolay Borisov if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE)) 1408a5ed9182SOmar Sandoval return 0; 1409a5ed9182SOmar Sandoval 14100d7764ffSDavid Sterba if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &block_group->runtime_flags)) { 1411a5ed9182SOmar Sandoval /* We never added this block group to the free space tree. */ 1412a5ed9182SOmar Sandoval return 0; 1413a5ed9182SOmar Sandoval } 1414a5ed9182SOmar Sandoval 1415a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1416a5ed9182SOmar Sandoval if (!path) { 1417a5ed9182SOmar Sandoval ret = -ENOMEM; 1418a5ed9182SOmar Sandoval goto out; 1419a5ed9182SOmar Sandoval } 1420a5ed9182SOmar Sandoval 1421b3470b5dSDavid Sterba start = block_group->start; 1422b3470b5dSDavid Sterba end = block_group->start + block_group->length; 1423a5ed9182SOmar Sandoval 1424a5ed9182SOmar Sandoval key.objectid = end - 1; 1425a5ed9182SOmar Sandoval key.type = (u8)-1; 1426a5ed9182SOmar Sandoval key.offset = (u64)-1; 1427a5ed9182SOmar Sandoval 1428a5ed9182SOmar Sandoval while (!done) { 1429a5ed9182SOmar Sandoval ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1); 1430a5ed9182SOmar Sandoval if (ret) 1431a5ed9182SOmar Sandoval goto out; 1432a5ed9182SOmar Sandoval 1433a5ed9182SOmar Sandoval leaf = path->nodes[0]; 1434a5ed9182SOmar Sandoval nr = 0; 1435a5ed9182SOmar Sandoval path->slots[0]++; 1436a5ed9182SOmar Sandoval while (path->slots[0] > 0) { 1437a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1); 1438a5ed9182SOmar Sandoval 1439a5ed9182SOmar Sandoval if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) { 1440b3470b5dSDavid Sterba ASSERT(found_key.objectid == block_group->start); 1441b3470b5dSDavid Sterba ASSERT(found_key.offset == block_group->length); 1442a5ed9182SOmar Sandoval done = 1; 1443a5ed9182SOmar Sandoval nr++; 1444a5ed9182SOmar Sandoval path->slots[0]--; 1445a5ed9182SOmar Sandoval break; 1446a5ed9182SOmar Sandoval } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY || 1447a5ed9182SOmar Sandoval found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) { 1448a5ed9182SOmar Sandoval ASSERT(found_key.objectid >= start); 1449a5ed9182SOmar Sandoval ASSERT(found_key.objectid < end); 1450a5ed9182SOmar Sandoval ASSERT(found_key.objectid + found_key.offset <= end); 1451a5ed9182SOmar Sandoval nr++; 1452a5ed9182SOmar Sandoval path->slots[0]--; 1453a5ed9182SOmar Sandoval } else { 1454a5ed9182SOmar Sandoval ASSERT(0); 1455a5ed9182SOmar Sandoval } 1456a5ed9182SOmar Sandoval } 1457a5ed9182SOmar Sandoval 1458a5ed9182SOmar Sandoval ret = btrfs_del_items(trans, root, path, path->slots[0], nr); 1459a5ed9182SOmar Sandoval if (ret) 1460a5ed9182SOmar Sandoval goto out; 1461a5ed9182SOmar Sandoval btrfs_release_path(path); 1462a5ed9182SOmar Sandoval } 1463a5ed9182SOmar Sandoval 1464a5ed9182SOmar Sandoval ret = 0; 1465a5ed9182SOmar Sandoval out: 1466a5ed9182SOmar Sandoval btrfs_free_path(path); 1467a5ed9182SOmar Sandoval if (ret) 146866642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 1469a5ed9182SOmar Sandoval return ret; 1470a5ed9182SOmar Sandoval } 1471a5ed9182SOmar Sandoval 1472a5ed9182SOmar Sandoval static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl, 1473a5ed9182SOmar Sandoval struct btrfs_path *path, 1474a5ed9182SOmar Sandoval u32 expected_extent_count) 1475a5ed9182SOmar Sandoval { 147632da5386SDavid Sterba struct btrfs_block_group *block_group; 1477a5ed9182SOmar Sandoval struct btrfs_fs_info *fs_info; 1478a5ed9182SOmar Sandoval struct btrfs_root *root; 1479a5ed9182SOmar Sandoval struct btrfs_key key; 1480a5ed9182SOmar Sandoval int prev_bit = 0, bit; 1481a5ed9182SOmar Sandoval /* Initialize to silence GCC. */ 1482a5ed9182SOmar Sandoval u64 extent_start = 0; 1483a5ed9182SOmar Sandoval u64 end, offset; 1484a5ed9182SOmar Sandoval u64 total_found = 0; 1485a5ed9182SOmar Sandoval u32 extent_count = 0; 1486a5ed9182SOmar Sandoval int ret; 1487a5ed9182SOmar Sandoval 1488a5ed9182SOmar Sandoval block_group = caching_ctl->block_group; 1489a5ed9182SOmar Sandoval fs_info = block_group->fs_info; 14907939dd9fSJosef Bacik root = btrfs_free_space_root(block_group); 1491a5ed9182SOmar Sandoval 1492b3470b5dSDavid Sterba end = block_group->start + block_group->length; 1493a5ed9182SOmar Sandoval 1494a5ed9182SOmar Sandoval while (1) { 1495a5ed9182SOmar Sandoval ret = btrfs_next_item(root, path); 1496a5ed9182SOmar Sandoval if (ret < 0) 1497a5ed9182SOmar Sandoval goto out; 1498a5ed9182SOmar Sandoval if (ret) 1499a5ed9182SOmar Sandoval break; 1500a5ed9182SOmar Sandoval 1501a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1502a5ed9182SOmar Sandoval 1503a5ed9182SOmar Sandoval if (key.type == BTRFS_FREE_SPACE_INFO_KEY) 1504a5ed9182SOmar Sandoval break; 1505a5ed9182SOmar Sandoval 1506a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); 1507a5ed9182SOmar Sandoval ASSERT(key.objectid < end && key.objectid + key.offset <= end); 1508a5ed9182SOmar Sandoval 1509a5ed9182SOmar Sandoval offset = key.objectid; 1510a5ed9182SOmar Sandoval while (offset < key.objectid + key.offset) { 1511a5ed9182SOmar Sandoval bit = free_space_test_bit(block_group, path, offset); 1512a5ed9182SOmar Sandoval if (prev_bit == 0 && bit == 1) { 1513a5ed9182SOmar Sandoval extent_start = offset; 1514a5ed9182SOmar Sandoval } else if (prev_bit == 1 && bit == 0) { 1515a5ed9182SOmar Sandoval total_found += add_new_free_space(block_group, 1516a5ed9182SOmar Sandoval extent_start, 1517a5ed9182SOmar Sandoval offset); 1518a5ed9182SOmar Sandoval if (total_found > CACHING_CTL_WAKE_UP) { 1519a5ed9182SOmar Sandoval total_found = 0; 1520a5ed9182SOmar Sandoval wake_up(&caching_ctl->wait); 1521a5ed9182SOmar Sandoval } 1522a5ed9182SOmar Sandoval extent_count++; 1523a5ed9182SOmar Sandoval } 1524a5ed9182SOmar Sandoval prev_bit = bit; 15250b246afaSJeff Mahoney offset += fs_info->sectorsize; 1526a5ed9182SOmar Sandoval } 1527a5ed9182SOmar Sandoval } 1528a5ed9182SOmar Sandoval if (prev_bit == 1) { 15294457c1c7SNikolay Borisov total_found += add_new_free_space(block_group, extent_start, 15304457c1c7SNikolay Borisov end); 1531a5ed9182SOmar Sandoval extent_count++; 1532a5ed9182SOmar Sandoval } 1533a5ed9182SOmar Sandoval 1534a5ed9182SOmar Sandoval if (extent_count != expected_extent_count) { 15355d163e0eSJeff Mahoney btrfs_err(fs_info, 15365d163e0eSJeff Mahoney "incorrect extent count for %llu; counted %u, expected %u", 1537b3470b5dSDavid Sterba block_group->start, extent_count, 1538a5ed9182SOmar Sandoval expected_extent_count); 1539a5ed9182SOmar Sandoval ASSERT(0); 1540a5ed9182SOmar Sandoval ret = -EIO; 1541a5ed9182SOmar Sandoval goto out; 1542a5ed9182SOmar Sandoval } 1543a5ed9182SOmar Sandoval 1544a5ed9182SOmar Sandoval ret = 0; 1545a5ed9182SOmar Sandoval out: 1546a5ed9182SOmar Sandoval return ret; 1547a5ed9182SOmar Sandoval } 1548a5ed9182SOmar Sandoval 1549a5ed9182SOmar Sandoval static int load_free_space_extents(struct btrfs_caching_control *caching_ctl, 1550a5ed9182SOmar Sandoval struct btrfs_path *path, 1551a5ed9182SOmar Sandoval u32 expected_extent_count) 1552a5ed9182SOmar Sandoval { 155332da5386SDavid Sterba struct btrfs_block_group *block_group; 1554a5ed9182SOmar Sandoval struct btrfs_fs_info *fs_info; 1555a5ed9182SOmar Sandoval struct btrfs_root *root; 1556a5ed9182SOmar Sandoval struct btrfs_key key; 1557a5ed9182SOmar Sandoval u64 end; 1558a5ed9182SOmar Sandoval u64 total_found = 0; 1559a5ed9182SOmar Sandoval u32 extent_count = 0; 1560a5ed9182SOmar Sandoval int ret; 1561a5ed9182SOmar Sandoval 1562a5ed9182SOmar Sandoval block_group = caching_ctl->block_group; 1563a5ed9182SOmar Sandoval fs_info = block_group->fs_info; 15647939dd9fSJosef Bacik root = btrfs_free_space_root(block_group); 1565a5ed9182SOmar Sandoval 1566b3470b5dSDavid Sterba end = block_group->start + block_group->length; 1567a5ed9182SOmar Sandoval 1568a5ed9182SOmar Sandoval while (1) { 1569a5ed9182SOmar Sandoval ret = btrfs_next_item(root, path); 1570a5ed9182SOmar Sandoval if (ret < 0) 1571a5ed9182SOmar Sandoval goto out; 1572a5ed9182SOmar Sandoval if (ret) 1573a5ed9182SOmar Sandoval break; 1574a5ed9182SOmar Sandoval 1575a5ed9182SOmar Sandoval btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 1576a5ed9182SOmar Sandoval 1577a5ed9182SOmar Sandoval if (key.type == BTRFS_FREE_SPACE_INFO_KEY) 1578a5ed9182SOmar Sandoval break; 1579a5ed9182SOmar Sandoval 1580a5ed9182SOmar Sandoval ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY); 1581a5ed9182SOmar Sandoval ASSERT(key.objectid < end && key.objectid + key.offset <= end); 1582a5ed9182SOmar Sandoval 15834457c1c7SNikolay Borisov total_found += add_new_free_space(block_group, key.objectid, 1584a5ed9182SOmar Sandoval key.objectid + key.offset); 1585a5ed9182SOmar Sandoval if (total_found > CACHING_CTL_WAKE_UP) { 1586a5ed9182SOmar Sandoval total_found = 0; 1587a5ed9182SOmar Sandoval wake_up(&caching_ctl->wait); 1588a5ed9182SOmar Sandoval } 1589a5ed9182SOmar Sandoval extent_count++; 1590a5ed9182SOmar Sandoval } 1591a5ed9182SOmar Sandoval 1592a5ed9182SOmar Sandoval if (extent_count != expected_extent_count) { 15935d163e0eSJeff Mahoney btrfs_err(fs_info, 15945d163e0eSJeff Mahoney "incorrect extent count for %llu; counted %u, expected %u", 1595b3470b5dSDavid Sterba block_group->start, extent_count, 1596a5ed9182SOmar Sandoval expected_extent_count); 1597a5ed9182SOmar Sandoval ASSERT(0); 1598a5ed9182SOmar Sandoval ret = -EIO; 1599a5ed9182SOmar Sandoval goto out; 1600a5ed9182SOmar Sandoval } 1601a5ed9182SOmar Sandoval 1602a5ed9182SOmar Sandoval ret = 0; 1603a5ed9182SOmar Sandoval out: 1604a5ed9182SOmar Sandoval return ret; 1605a5ed9182SOmar Sandoval } 1606a5ed9182SOmar Sandoval 1607a5ed9182SOmar Sandoval int load_free_space_tree(struct btrfs_caching_control *caching_ctl) 1608a5ed9182SOmar Sandoval { 160932da5386SDavid Sterba struct btrfs_block_group *block_group; 1610a5ed9182SOmar Sandoval struct btrfs_free_space_info *info; 1611a5ed9182SOmar Sandoval struct btrfs_path *path; 1612a5ed9182SOmar Sandoval u32 extent_count, flags; 1613a5ed9182SOmar Sandoval int ret; 1614a5ed9182SOmar Sandoval 1615a5ed9182SOmar Sandoval block_group = caching_ctl->block_group; 1616a5ed9182SOmar Sandoval 1617a5ed9182SOmar Sandoval path = btrfs_alloc_path(); 1618a5ed9182SOmar Sandoval if (!path) 1619a5ed9182SOmar Sandoval return -ENOMEM; 1620a5ed9182SOmar Sandoval 1621a5ed9182SOmar Sandoval /* 1622a5ed9182SOmar Sandoval * Just like caching_thread() doesn't want to deadlock on the extent 1623a5ed9182SOmar Sandoval * tree, we don't want to deadlock on the free space tree. 1624a5ed9182SOmar Sandoval */ 1625a5ed9182SOmar Sandoval path->skip_locking = 1; 1626a5ed9182SOmar Sandoval path->search_commit_root = 1; 16277ce311d5SGu JinXiang path->reada = READA_FORWARD; 1628a5ed9182SOmar Sandoval 16292ccf545eSDavid Sterba info = search_free_space_info(NULL, block_group, path, 0); 1630a5ed9182SOmar Sandoval if (IS_ERR(info)) { 1631a5ed9182SOmar Sandoval ret = PTR_ERR(info); 1632a5ed9182SOmar Sandoval goto out; 1633a5ed9182SOmar Sandoval } 1634a5ed9182SOmar Sandoval extent_count = btrfs_free_space_extent_count(path->nodes[0], info); 1635a5ed9182SOmar Sandoval flags = btrfs_free_space_flags(path->nodes[0], info); 1636a5ed9182SOmar Sandoval 1637a5ed9182SOmar Sandoval /* 1638a5ed9182SOmar Sandoval * We left path pointing to the free space info item, so now 1639a5ed9182SOmar Sandoval * load_free_space_foo can just iterate through the free space tree from 1640a5ed9182SOmar Sandoval * there. 1641a5ed9182SOmar Sandoval */ 1642a5ed9182SOmar Sandoval if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) 1643a5ed9182SOmar Sandoval ret = load_free_space_bitmaps(caching_ctl, path, extent_count); 1644a5ed9182SOmar Sandoval else 1645a5ed9182SOmar Sandoval ret = load_free_space_extents(caching_ctl, path, extent_count); 1646a5ed9182SOmar Sandoval 1647a5ed9182SOmar Sandoval out: 1648a5ed9182SOmar Sandoval btrfs_free_path(path); 1649a5ed9182SOmar Sandoval return ret; 1650a5ed9182SOmar Sandoval } 1651