Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2015 Facebook.  All rights reserved.
0004  */
0005 
0006 #include <linux/kernel.h>
0007 #include <linux/sched/mm.h>
0008 #include "ctree.h"
0009 #include "disk-io.h"
0010 #include "locking.h"
0011 #include "free-space-tree.h"
0012 #include "transaction.h"
0013 #include "block-group.h"
0014 
0015 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
0016                     struct btrfs_block_group *block_group,
0017                     struct btrfs_path *path);
0018 
0019 static struct btrfs_root *btrfs_free_space_root(
0020                 struct btrfs_block_group *block_group)
0021 {
0022     struct btrfs_key key = {
0023         .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
0024         .type = BTRFS_ROOT_ITEM_KEY,
0025         .offset = 0,
0026     };
0027 
0028     if (btrfs_fs_incompat(block_group->fs_info, EXTENT_TREE_V2))
0029         key.offset = block_group->global_root_id;
0030     return btrfs_global_root(block_group->fs_info, &key);
0031 }
0032 
0033 void set_free_space_tree_thresholds(struct btrfs_block_group *cache)
0034 {
0035     u32 bitmap_range;
0036     size_t bitmap_size;
0037     u64 num_bitmaps, total_bitmap_size;
0038 
0039     if (WARN_ON(cache->length == 0))
0040         btrfs_warn(cache->fs_info, "block group %llu length is zero",
0041                cache->start);
0042 
0043     /*
0044      * We convert to bitmaps when the disk space required for using extents
0045      * exceeds that required for using bitmaps.
0046      */
0047     bitmap_range = cache->fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
0048     num_bitmaps = div_u64(cache->length + bitmap_range - 1, bitmap_range);
0049     bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
0050     total_bitmap_size = num_bitmaps * bitmap_size;
0051     cache->bitmap_high_thresh = div_u64(total_bitmap_size,
0052                         sizeof(struct btrfs_item));
0053 
0054     /*
0055      * We allow for a small buffer between the high threshold and low
0056      * threshold to avoid thrashing back and forth between the two formats.
0057      */
0058     if (cache->bitmap_high_thresh > 100)
0059         cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
0060     else
0061         cache->bitmap_low_thresh = 0;
0062 }
0063 
0064 static int add_new_free_space_info(struct btrfs_trans_handle *trans,
0065                    struct btrfs_block_group *block_group,
0066                    struct btrfs_path *path)
0067 {
0068     struct btrfs_root *root = btrfs_free_space_root(block_group);
0069     struct btrfs_free_space_info *info;
0070     struct btrfs_key key;
0071     struct extent_buffer *leaf;
0072     int ret;
0073 
0074     key.objectid = block_group->start;
0075     key.type = BTRFS_FREE_SPACE_INFO_KEY;
0076     key.offset = block_group->length;
0077 
0078     ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
0079     if (ret)
0080         goto out;
0081 
0082     leaf = path->nodes[0];
0083     info = btrfs_item_ptr(leaf, path->slots[0],
0084                   struct btrfs_free_space_info);
0085     btrfs_set_free_space_extent_count(leaf, info, 0);
0086     btrfs_set_free_space_flags(leaf, info, 0);
0087     btrfs_mark_buffer_dirty(leaf);
0088 
0089     ret = 0;
0090 out:
0091     btrfs_release_path(path);
0092     return ret;
0093 }
0094 
0095 EXPORT_FOR_TESTS
0096 struct btrfs_free_space_info *search_free_space_info(
0097         struct btrfs_trans_handle *trans,
0098         struct btrfs_block_group *block_group,
0099         struct btrfs_path *path, int cow)
0100 {
0101     struct btrfs_fs_info *fs_info = block_group->fs_info;
0102     struct btrfs_root *root = btrfs_free_space_root(block_group);
0103     struct btrfs_key key;
0104     int ret;
0105 
0106     key.objectid = block_group->start;
0107     key.type = BTRFS_FREE_SPACE_INFO_KEY;
0108     key.offset = block_group->length;
0109 
0110     ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
0111     if (ret < 0)
0112         return ERR_PTR(ret);
0113     if (ret != 0) {
0114         btrfs_warn(fs_info, "missing free space info for %llu",
0115                block_group->start);
0116         ASSERT(0);
0117         return ERR_PTR(-ENOENT);
0118     }
0119 
0120     return btrfs_item_ptr(path->nodes[0], path->slots[0],
0121                   struct btrfs_free_space_info);
0122 }
0123 
0124 /*
0125  * btrfs_search_slot() but we're looking for the greatest key less than the
0126  * passed key.
0127  */
0128 static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
0129                   struct btrfs_root *root,
0130                   struct btrfs_key *key, struct btrfs_path *p,
0131                   int ins_len, int cow)
0132 {
0133     int ret;
0134 
0135     ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
0136     if (ret < 0)
0137         return ret;
0138 
0139     if (ret == 0) {
0140         ASSERT(0);
0141         return -EIO;
0142     }
0143 
0144     if (p->slots[0] == 0) {
0145         ASSERT(0);
0146         return -EIO;
0147     }
0148     p->slots[0]--;
0149 
0150     return 0;
0151 }
0152 
0153 static inline u32 free_space_bitmap_size(const struct btrfs_fs_info *fs_info,
0154                      u64 size)
0155 {
0156     return DIV_ROUND_UP(size >> fs_info->sectorsize_bits, BITS_PER_BYTE);
0157 }
0158 
0159 static unsigned long *alloc_bitmap(u32 bitmap_size)
0160 {
0161     unsigned long *ret;
0162     unsigned int nofs_flag;
0163     u32 bitmap_rounded_size = round_up(bitmap_size, sizeof(unsigned long));
0164 
0165     /*
0166      * GFP_NOFS doesn't work with kvmalloc(), but we really can't recurse
0167      * into the filesystem as the free space bitmap can be modified in the
0168      * critical section of a transaction commit.
0169      *
0170      * TODO: push the memalloc_nofs_{save,restore}() to the caller where we
0171      * know that recursion is unsafe.
0172      */
0173     nofs_flag = memalloc_nofs_save();
0174     ret = kvzalloc(bitmap_rounded_size, GFP_KERNEL);
0175     memalloc_nofs_restore(nofs_flag);
0176     return ret;
0177 }
0178 
0179 static void le_bitmap_set(unsigned long *map, unsigned int start, int len)
0180 {
0181     u8 *p = ((u8 *)map) + BIT_BYTE(start);
0182     const unsigned int size = start + len;
0183     int bits_to_set = BITS_PER_BYTE - (start % BITS_PER_BYTE);
0184     u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(start);
0185 
0186     while (len - bits_to_set >= 0) {
0187         *p |= mask_to_set;
0188         len -= bits_to_set;
0189         bits_to_set = BITS_PER_BYTE;
0190         mask_to_set = ~0;
0191         p++;
0192     }
0193     if (len) {
0194         mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
0195         *p |= mask_to_set;
0196     }
0197 }
0198 
0199 EXPORT_FOR_TESTS
0200 int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
0201                   struct btrfs_block_group *block_group,
0202                   struct btrfs_path *path)
0203 {
0204     struct btrfs_fs_info *fs_info = trans->fs_info;
0205     struct btrfs_root *root = btrfs_free_space_root(block_group);
0206     struct btrfs_free_space_info *info;
0207     struct btrfs_key key, found_key;
0208     struct extent_buffer *leaf;
0209     unsigned long *bitmap;
0210     char *bitmap_cursor;
0211     u64 start, end;
0212     u64 bitmap_range, i;
0213     u32 bitmap_size, flags, expected_extent_count;
0214     u32 extent_count = 0;
0215     int done = 0, nr;
0216     int ret;
0217 
0218     bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
0219     bitmap = alloc_bitmap(bitmap_size);
0220     if (!bitmap) {
0221         ret = -ENOMEM;
0222         goto out;
0223     }
0224 
0225     start = block_group->start;
0226     end = block_group->start + block_group->length;
0227 
0228     key.objectid = end - 1;
0229     key.type = (u8)-1;
0230     key.offset = (u64)-1;
0231 
0232     while (!done) {
0233         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
0234         if (ret)
0235             goto out;
0236 
0237         leaf = path->nodes[0];
0238         nr = 0;
0239         path->slots[0]++;
0240         while (path->slots[0] > 0) {
0241             btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
0242 
0243             if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
0244                 ASSERT(found_key.objectid == block_group->start);
0245                 ASSERT(found_key.offset == block_group->length);
0246                 done = 1;
0247                 break;
0248             } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
0249                 u64 first, last;
0250 
0251                 ASSERT(found_key.objectid >= start);
0252                 ASSERT(found_key.objectid < end);
0253                 ASSERT(found_key.objectid + found_key.offset <= end);
0254 
0255                 first = div_u64(found_key.objectid - start,
0256                         fs_info->sectorsize);
0257                 last = div_u64(found_key.objectid + found_key.offset - start,
0258                            fs_info->sectorsize);
0259                 le_bitmap_set(bitmap, first, last - first);
0260 
0261                 extent_count++;
0262                 nr++;
0263                 path->slots[0]--;
0264             } else {
0265                 ASSERT(0);
0266             }
0267         }
0268 
0269         ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
0270         if (ret)
0271             goto out;
0272         btrfs_release_path(path);
0273     }
0274 
0275     info = search_free_space_info(trans, block_group, path, 1);
0276     if (IS_ERR(info)) {
0277         ret = PTR_ERR(info);
0278         goto out;
0279     }
0280     leaf = path->nodes[0];
0281     flags = btrfs_free_space_flags(leaf, info);
0282     flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
0283     btrfs_set_free_space_flags(leaf, info, flags);
0284     expected_extent_count = btrfs_free_space_extent_count(leaf, info);
0285     btrfs_mark_buffer_dirty(leaf);
0286     btrfs_release_path(path);
0287 
0288     if (extent_count != expected_extent_count) {
0289         btrfs_err(fs_info,
0290               "incorrect extent count for %llu; counted %u, expected %u",
0291               block_group->start, extent_count,
0292               expected_extent_count);
0293         ASSERT(0);
0294         ret = -EIO;
0295         goto out;
0296     }
0297 
0298     bitmap_cursor = (char *)bitmap;
0299     bitmap_range = fs_info->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
0300     i = start;
0301     while (i < end) {
0302         unsigned long ptr;
0303         u64 extent_size;
0304         u32 data_size;
0305 
0306         extent_size = min(end - i, bitmap_range);
0307         data_size = free_space_bitmap_size(fs_info, extent_size);
0308 
0309         key.objectid = i;
0310         key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
0311         key.offset = extent_size;
0312 
0313         ret = btrfs_insert_empty_item(trans, root, path, &key,
0314                           data_size);
0315         if (ret)
0316             goto out;
0317 
0318         leaf = path->nodes[0];
0319         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
0320         write_extent_buffer(leaf, bitmap_cursor, ptr,
0321                     data_size);
0322         btrfs_mark_buffer_dirty(leaf);
0323         btrfs_release_path(path);
0324 
0325         i += extent_size;
0326         bitmap_cursor += data_size;
0327     }
0328 
0329     ret = 0;
0330 out:
0331     kvfree(bitmap);
0332     if (ret)
0333         btrfs_abort_transaction(trans, ret);
0334     return ret;
0335 }
0336 
0337 EXPORT_FOR_TESTS
0338 int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
0339                   struct btrfs_block_group *block_group,
0340                   struct btrfs_path *path)
0341 {
0342     struct btrfs_fs_info *fs_info = trans->fs_info;
0343     struct btrfs_root *root = btrfs_free_space_root(block_group);
0344     struct btrfs_free_space_info *info;
0345     struct btrfs_key key, found_key;
0346     struct extent_buffer *leaf;
0347     unsigned long *bitmap;
0348     u64 start, end;
0349     u32 bitmap_size, flags, expected_extent_count;
0350     unsigned long nrbits, start_bit, end_bit;
0351     u32 extent_count = 0;
0352     int done = 0, nr;
0353     int ret;
0354 
0355     bitmap_size = free_space_bitmap_size(fs_info, block_group->length);
0356     bitmap = alloc_bitmap(bitmap_size);
0357     if (!bitmap) {
0358         ret = -ENOMEM;
0359         goto out;
0360     }
0361 
0362     start = block_group->start;
0363     end = block_group->start + block_group->length;
0364 
0365     key.objectid = end - 1;
0366     key.type = (u8)-1;
0367     key.offset = (u64)-1;
0368 
0369     while (!done) {
0370         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
0371         if (ret)
0372             goto out;
0373 
0374         leaf = path->nodes[0];
0375         nr = 0;
0376         path->slots[0]++;
0377         while (path->slots[0] > 0) {
0378             btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
0379 
0380             if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
0381                 ASSERT(found_key.objectid == block_group->start);
0382                 ASSERT(found_key.offset == block_group->length);
0383                 done = 1;
0384                 break;
0385             } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
0386                 unsigned long ptr;
0387                 char *bitmap_cursor;
0388                 u32 bitmap_pos, data_size;
0389 
0390                 ASSERT(found_key.objectid >= start);
0391                 ASSERT(found_key.objectid < end);
0392                 ASSERT(found_key.objectid + found_key.offset <= end);
0393 
0394                 bitmap_pos = div_u64(found_key.objectid - start,
0395                              fs_info->sectorsize *
0396                              BITS_PER_BYTE);
0397                 bitmap_cursor = ((char *)bitmap) + bitmap_pos;
0398                 data_size = free_space_bitmap_size(fs_info,
0399                                 found_key.offset);
0400 
0401                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
0402                 read_extent_buffer(leaf, bitmap_cursor, ptr,
0403                            data_size);
0404 
0405                 nr++;
0406                 path->slots[0]--;
0407             } else {
0408                 ASSERT(0);
0409             }
0410         }
0411 
0412         ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
0413         if (ret)
0414             goto out;
0415         btrfs_release_path(path);
0416     }
0417 
0418     info = search_free_space_info(trans, block_group, path, 1);
0419     if (IS_ERR(info)) {
0420         ret = PTR_ERR(info);
0421         goto out;
0422     }
0423     leaf = path->nodes[0];
0424     flags = btrfs_free_space_flags(leaf, info);
0425     flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
0426     btrfs_set_free_space_flags(leaf, info, flags);
0427     expected_extent_count = btrfs_free_space_extent_count(leaf, info);
0428     btrfs_mark_buffer_dirty(leaf);
0429     btrfs_release_path(path);
0430 
0431     nrbits = block_group->length >> block_group->fs_info->sectorsize_bits;
0432     start_bit = find_next_bit_le(bitmap, nrbits, 0);
0433 
0434     while (start_bit < nrbits) {
0435         end_bit = find_next_zero_bit_le(bitmap, nrbits, start_bit);
0436         ASSERT(start_bit < end_bit);
0437 
0438         key.objectid = start + start_bit * block_group->fs_info->sectorsize;
0439         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
0440         key.offset = (end_bit - start_bit) * block_group->fs_info->sectorsize;
0441 
0442         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
0443         if (ret)
0444             goto out;
0445         btrfs_release_path(path);
0446 
0447         extent_count++;
0448 
0449         start_bit = find_next_bit_le(bitmap, nrbits, end_bit);
0450     }
0451 
0452     if (extent_count != expected_extent_count) {
0453         btrfs_err(fs_info,
0454               "incorrect extent count for %llu; counted %u, expected %u",
0455               block_group->start, extent_count,
0456               expected_extent_count);
0457         ASSERT(0);
0458         ret = -EIO;
0459         goto out;
0460     }
0461 
0462     ret = 0;
0463 out:
0464     kvfree(bitmap);
0465     if (ret)
0466         btrfs_abort_transaction(trans, ret);
0467     return ret;
0468 }
0469 
0470 static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
0471                       struct btrfs_block_group *block_group,
0472                       struct btrfs_path *path,
0473                       int new_extents)
0474 {
0475     struct btrfs_free_space_info *info;
0476     u32 flags;
0477     u32 extent_count;
0478     int ret = 0;
0479 
0480     if (new_extents == 0)
0481         return 0;
0482 
0483     info = search_free_space_info(trans, block_group, path, 1);
0484     if (IS_ERR(info)) {
0485         ret = PTR_ERR(info);
0486         goto out;
0487     }
0488     flags = btrfs_free_space_flags(path->nodes[0], info);
0489     extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
0490 
0491     extent_count += new_extents;
0492     btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
0493     btrfs_mark_buffer_dirty(path->nodes[0]);
0494     btrfs_release_path(path);
0495 
0496     if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
0497         extent_count > block_group->bitmap_high_thresh) {
0498         ret = convert_free_space_to_bitmaps(trans, block_group, path);
0499     } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
0500            extent_count < block_group->bitmap_low_thresh) {
0501         ret = convert_free_space_to_extents(trans, block_group, path);
0502     }
0503 
0504 out:
0505     return ret;
0506 }
0507 
0508 EXPORT_FOR_TESTS
0509 int free_space_test_bit(struct btrfs_block_group *block_group,
0510             struct btrfs_path *path, u64 offset)
0511 {
0512     struct extent_buffer *leaf;
0513     struct btrfs_key key;
0514     u64 found_start, found_end;
0515     unsigned long ptr, i;
0516 
0517     leaf = path->nodes[0];
0518     btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
0519     ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
0520 
0521     found_start = key.objectid;
0522     found_end = key.objectid + key.offset;
0523     ASSERT(offset >= found_start && offset < found_end);
0524 
0525     ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
0526     i = div_u64(offset - found_start,
0527             block_group->fs_info->sectorsize);
0528     return !!extent_buffer_test_bit(leaf, ptr, i);
0529 }
0530 
0531 static void free_space_set_bits(struct btrfs_block_group *block_group,
0532                 struct btrfs_path *path, u64 *start, u64 *size,
0533                 int bit)
0534 {
0535     struct btrfs_fs_info *fs_info = block_group->fs_info;
0536     struct extent_buffer *leaf;
0537     struct btrfs_key key;
0538     u64 end = *start + *size;
0539     u64 found_start, found_end;
0540     unsigned long ptr, first, last;
0541 
0542     leaf = path->nodes[0];
0543     btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
0544     ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
0545 
0546     found_start = key.objectid;
0547     found_end = key.objectid + key.offset;
0548     ASSERT(*start >= found_start && *start < found_end);
0549     ASSERT(end > found_start);
0550 
0551     if (end > found_end)
0552         end = found_end;
0553 
0554     ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
0555     first = (*start - found_start) >> fs_info->sectorsize_bits;
0556     last = (end - found_start) >> fs_info->sectorsize_bits;
0557     if (bit)
0558         extent_buffer_bitmap_set(leaf, ptr, first, last - first);
0559     else
0560         extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
0561     btrfs_mark_buffer_dirty(leaf);
0562 
0563     *size -= end - *start;
0564     *start = end;
0565 }
0566 
0567 /*
0568  * We can't use btrfs_next_item() in modify_free_space_bitmap() because
0569  * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
0570  * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
0571  * looking for.
0572  */
0573 static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
0574                   struct btrfs_root *root, struct btrfs_path *p)
0575 {
0576     struct btrfs_key key;
0577 
0578     if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
0579         p->slots[0]++;
0580         return 0;
0581     }
0582 
0583     btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
0584     btrfs_release_path(p);
0585 
0586     key.objectid += key.offset;
0587     key.type = (u8)-1;
0588     key.offset = (u64)-1;
0589 
0590     return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
0591 }
0592 
0593 /*
0594  * If remove is 1, then we are removing free space, thus clearing bits in the
0595  * bitmap. If remove is 0, then we are adding free space, thus setting bits in
0596  * the bitmap.
0597  */
0598 static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
0599                     struct btrfs_block_group *block_group,
0600                     struct btrfs_path *path,
0601                     u64 start, u64 size, int remove)
0602 {
0603     struct btrfs_root *root = btrfs_free_space_root(block_group);
0604     struct btrfs_key key;
0605     u64 end = start + size;
0606     u64 cur_start, cur_size;
0607     int prev_bit, next_bit;
0608     int new_extents;
0609     int ret;
0610 
0611     /*
0612      * Read the bit for the block immediately before the extent of space if
0613      * that block is within the block group.
0614      */
0615     if (start > block_group->start) {
0616         u64 prev_block = start - block_group->fs_info->sectorsize;
0617 
0618         key.objectid = prev_block;
0619         key.type = (u8)-1;
0620         key.offset = (u64)-1;
0621 
0622         ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
0623         if (ret)
0624             goto out;
0625 
0626         prev_bit = free_space_test_bit(block_group, path, prev_block);
0627 
0628         /* The previous block may have been in the previous bitmap. */
0629         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0630         if (start >= key.objectid + key.offset) {
0631             ret = free_space_next_bitmap(trans, root, path);
0632             if (ret)
0633                 goto out;
0634         }
0635     } else {
0636         key.objectid = start;
0637         key.type = (u8)-1;
0638         key.offset = (u64)-1;
0639 
0640         ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
0641         if (ret)
0642             goto out;
0643 
0644         prev_bit = -1;
0645     }
0646 
0647     /*
0648      * Iterate over all of the bitmaps overlapped by the extent of space,
0649      * clearing/setting bits as required.
0650      */
0651     cur_start = start;
0652     cur_size = size;
0653     while (1) {
0654         free_space_set_bits(block_group, path, &cur_start, &cur_size,
0655                     !remove);
0656         if (cur_size == 0)
0657             break;
0658         ret = free_space_next_bitmap(trans, root, path);
0659         if (ret)
0660             goto out;
0661     }
0662 
0663     /*
0664      * Read the bit for the block immediately after the extent of space if
0665      * that block is within the block group.
0666      */
0667     if (end < block_group->start + block_group->length) {
0668         /* The next block may be in the next bitmap. */
0669         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0670         if (end >= key.objectid + key.offset) {
0671             ret = free_space_next_bitmap(trans, root, path);
0672             if (ret)
0673                 goto out;
0674         }
0675 
0676         next_bit = free_space_test_bit(block_group, path, end);
0677     } else {
0678         next_bit = -1;
0679     }
0680 
0681     if (remove) {
0682         new_extents = -1;
0683         if (prev_bit == 1) {
0684             /* Leftover on the left. */
0685             new_extents++;
0686         }
0687         if (next_bit == 1) {
0688             /* Leftover on the right. */
0689             new_extents++;
0690         }
0691     } else {
0692         new_extents = 1;
0693         if (prev_bit == 1) {
0694             /* Merging with neighbor on the left. */
0695             new_extents--;
0696         }
0697         if (next_bit == 1) {
0698             /* Merging with neighbor on the right. */
0699             new_extents--;
0700         }
0701     }
0702 
0703     btrfs_release_path(path);
0704     ret = update_free_space_extent_count(trans, block_group, path,
0705                          new_extents);
0706 
0707 out:
0708     return ret;
0709 }
0710 
0711 static int remove_free_space_extent(struct btrfs_trans_handle *trans,
0712                     struct btrfs_block_group *block_group,
0713                     struct btrfs_path *path,
0714                     u64 start, u64 size)
0715 {
0716     struct btrfs_root *root = btrfs_free_space_root(block_group);
0717     struct btrfs_key key;
0718     u64 found_start, found_end;
0719     u64 end = start + size;
0720     int new_extents = -1;
0721     int ret;
0722 
0723     key.objectid = start;
0724     key.type = (u8)-1;
0725     key.offset = (u64)-1;
0726 
0727     ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
0728     if (ret)
0729         goto out;
0730 
0731     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0732 
0733     ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
0734 
0735     found_start = key.objectid;
0736     found_end = key.objectid + key.offset;
0737     ASSERT(start >= found_start && end <= found_end);
0738 
0739     /*
0740      * Okay, now that we've found the free space extent which contains the
0741      * free space that we are removing, there are four cases:
0742      *
0743      * 1. We're using the whole extent: delete the key we found and
0744      * decrement the free space extent count.
0745      * 2. We are using part of the extent starting at the beginning: delete
0746      * the key we found and insert a new key representing the leftover at
0747      * the end. There is no net change in the number of extents.
0748      * 3. We are using part of the extent ending at the end: delete the key
0749      * we found and insert a new key representing the leftover at the
0750      * beginning. There is no net change in the number of extents.
0751      * 4. We are using part of the extent in the middle: delete the key we
0752      * found and insert two new keys representing the leftovers on each
0753      * side. Where we used to have one extent, we now have two, so increment
0754      * the extent count. We may need to convert the block group to bitmaps
0755      * as a result.
0756      */
0757 
0758     /* Delete the existing key (cases 1-4). */
0759     ret = btrfs_del_item(trans, root, path);
0760     if (ret)
0761         goto out;
0762 
0763     /* Add a key for leftovers at the beginning (cases 3 and 4). */
0764     if (start > found_start) {
0765         key.objectid = found_start;
0766         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
0767         key.offset = start - found_start;
0768 
0769         btrfs_release_path(path);
0770         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
0771         if (ret)
0772             goto out;
0773         new_extents++;
0774     }
0775 
0776     /* Add a key for leftovers at the end (cases 2 and 4). */
0777     if (end < found_end) {
0778         key.objectid = end;
0779         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
0780         key.offset = found_end - end;
0781 
0782         btrfs_release_path(path);
0783         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
0784         if (ret)
0785             goto out;
0786         new_extents++;
0787     }
0788 
0789     btrfs_release_path(path);
0790     ret = update_free_space_extent_count(trans, block_group, path,
0791                          new_extents);
0792 
0793 out:
0794     return ret;
0795 }
0796 
0797 EXPORT_FOR_TESTS
0798 int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
0799                   struct btrfs_block_group *block_group,
0800                   struct btrfs_path *path, u64 start, u64 size)
0801 {
0802     struct btrfs_free_space_info *info;
0803     u32 flags;
0804     int ret;
0805 
0806     if (block_group->needs_free_space) {
0807         ret = __add_block_group_free_space(trans, block_group, path);
0808         if (ret)
0809             return ret;
0810     }
0811 
0812     info = search_free_space_info(NULL, block_group, path, 0);
0813     if (IS_ERR(info))
0814         return PTR_ERR(info);
0815     flags = btrfs_free_space_flags(path->nodes[0], info);
0816     btrfs_release_path(path);
0817 
0818     if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
0819         return modify_free_space_bitmap(trans, block_group, path,
0820                         start, size, 1);
0821     } else {
0822         return remove_free_space_extent(trans, block_group, path,
0823                         start, size);
0824     }
0825 }
0826 
0827 int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
0828                 u64 start, u64 size)
0829 {
0830     struct btrfs_block_group *block_group;
0831     struct btrfs_path *path;
0832     int ret;
0833 
0834     if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
0835         return 0;
0836 
0837     path = btrfs_alloc_path();
0838     if (!path) {
0839         ret = -ENOMEM;
0840         goto out;
0841     }
0842 
0843     block_group = btrfs_lookup_block_group(trans->fs_info, start);
0844     if (!block_group) {
0845         ASSERT(0);
0846         ret = -ENOENT;
0847         goto out;
0848     }
0849 
0850     mutex_lock(&block_group->free_space_lock);
0851     ret = __remove_from_free_space_tree(trans, block_group, path, start,
0852                         size);
0853     mutex_unlock(&block_group->free_space_lock);
0854 
0855     btrfs_put_block_group(block_group);
0856 out:
0857     btrfs_free_path(path);
0858     if (ret)
0859         btrfs_abort_transaction(trans, ret);
0860     return ret;
0861 }
0862 
0863 static int add_free_space_extent(struct btrfs_trans_handle *trans,
0864                  struct btrfs_block_group *block_group,
0865                  struct btrfs_path *path,
0866                  u64 start, u64 size)
0867 {
0868     struct btrfs_root *root = btrfs_free_space_root(block_group);
0869     struct btrfs_key key, new_key;
0870     u64 found_start, found_end;
0871     u64 end = start + size;
0872     int new_extents = 1;
0873     int ret;
0874 
0875     /*
0876      * We are adding a new extent of free space, but we need to merge
0877      * extents. There are four cases here:
0878      *
0879      * 1. The new extent does not have any immediate neighbors to merge
0880      * with: add the new key and increment the free space extent count. We
0881      * may need to convert the block group to bitmaps as a result.
0882      * 2. The new extent has an immediate neighbor before it: remove the
0883      * previous key and insert a new key combining both of them. There is no
0884      * net change in the number of extents.
0885      * 3. The new extent has an immediate neighbor after it: remove the next
0886      * key and insert a new key combining both of them. There is no net
0887      * change in the number of extents.
0888      * 4. The new extent has immediate neighbors on both sides: remove both
0889      * of the keys and insert a new key combining all of them. Where we used
0890      * to have two extents, we now have one, so decrement the extent count.
0891      */
0892 
0893     new_key.objectid = start;
0894     new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
0895     new_key.offset = size;
0896 
0897     /* Search for a neighbor on the left. */
0898     if (start == block_group->start)
0899         goto right;
0900     key.objectid = start - 1;
0901     key.type = (u8)-1;
0902     key.offset = (u64)-1;
0903 
0904     ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
0905     if (ret)
0906         goto out;
0907 
0908     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0909 
0910     if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
0911         ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
0912         btrfs_release_path(path);
0913         goto right;
0914     }
0915 
0916     found_start = key.objectid;
0917     found_end = key.objectid + key.offset;
0918     ASSERT(found_start >= block_group->start &&
0919            found_end > block_group->start);
0920     ASSERT(found_start < start && found_end <= start);
0921 
0922     /*
0923      * Delete the neighbor on the left and absorb it into the new key (cases
0924      * 2 and 4).
0925      */
0926     if (found_end == start) {
0927         ret = btrfs_del_item(trans, root, path);
0928         if (ret)
0929             goto out;
0930         new_key.objectid = found_start;
0931         new_key.offset += key.offset;
0932         new_extents--;
0933     }
0934     btrfs_release_path(path);
0935 
0936 right:
0937     /* Search for a neighbor on the right. */
0938     if (end == block_group->start + block_group->length)
0939         goto insert;
0940     key.objectid = end;
0941     key.type = (u8)-1;
0942     key.offset = (u64)-1;
0943 
0944     ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
0945     if (ret)
0946         goto out;
0947 
0948     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0949 
0950     if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
0951         ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
0952         btrfs_release_path(path);
0953         goto insert;
0954     }
0955 
0956     found_start = key.objectid;
0957     found_end = key.objectid + key.offset;
0958     ASSERT(found_start >= block_group->start &&
0959            found_end > block_group->start);
0960     ASSERT((found_start < start && found_end <= start) ||
0961            (found_start >= end && found_end > end));
0962 
0963     /*
0964      * Delete the neighbor on the right and absorb it into the new key
0965      * (cases 3 and 4).
0966      */
0967     if (found_start == end) {
0968         ret = btrfs_del_item(trans, root, path);
0969         if (ret)
0970             goto out;
0971         new_key.offset += key.offset;
0972         new_extents--;
0973     }
0974     btrfs_release_path(path);
0975 
0976 insert:
0977     /* Insert the new key (cases 1-4). */
0978     ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
0979     if (ret)
0980         goto out;
0981 
0982     btrfs_release_path(path);
0983     ret = update_free_space_extent_count(trans, block_group, path,
0984                          new_extents);
0985 
0986 out:
0987     return ret;
0988 }
0989 
0990 EXPORT_FOR_TESTS
0991 int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
0992                  struct btrfs_block_group *block_group,
0993                  struct btrfs_path *path, u64 start, u64 size)
0994 {
0995     struct btrfs_free_space_info *info;
0996     u32 flags;
0997     int ret;
0998 
0999     if (block_group->needs_free_space) {
1000         ret = __add_block_group_free_space(trans, block_group, path);
1001         if (ret)
1002             return ret;
1003     }
1004 
1005     info = search_free_space_info(NULL, block_group, path, 0);
1006     if (IS_ERR(info))
1007         return PTR_ERR(info);
1008     flags = btrfs_free_space_flags(path->nodes[0], info);
1009     btrfs_release_path(path);
1010 
1011     if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
1012         return modify_free_space_bitmap(trans, block_group, path,
1013                         start, size, 0);
1014     } else {
1015         return add_free_space_extent(trans, block_group, path, start,
1016                          size);
1017     }
1018 }
1019 
1020 int add_to_free_space_tree(struct btrfs_trans_handle *trans,
1021                u64 start, u64 size)
1022 {
1023     struct btrfs_block_group *block_group;
1024     struct btrfs_path *path;
1025     int ret;
1026 
1027     if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1028         return 0;
1029 
1030     path = btrfs_alloc_path();
1031     if (!path) {
1032         ret = -ENOMEM;
1033         goto out;
1034     }
1035 
1036     block_group = btrfs_lookup_block_group(trans->fs_info, start);
1037     if (!block_group) {
1038         ASSERT(0);
1039         ret = -ENOENT;
1040         goto out;
1041     }
1042 
1043     mutex_lock(&block_group->free_space_lock);
1044     ret = __add_to_free_space_tree(trans, block_group, path, start, size);
1045     mutex_unlock(&block_group->free_space_lock);
1046 
1047     btrfs_put_block_group(block_group);
1048 out:
1049     btrfs_free_path(path);
1050     if (ret)
1051         btrfs_abort_transaction(trans, ret);
1052     return ret;
1053 }
1054 
1055 /*
1056  * Populate the free space tree by walking the extent tree. Operations on the
1057  * extent tree that happen as a result of writes to the free space tree will go
1058  * through the normal add/remove hooks.
1059  */
1060 static int populate_free_space_tree(struct btrfs_trans_handle *trans,
1061                     struct btrfs_block_group *block_group)
1062 {
1063     struct btrfs_root *extent_root;
1064     struct btrfs_path *path, *path2;
1065     struct btrfs_key key;
1066     u64 start, end;
1067     int ret;
1068 
1069     path = btrfs_alloc_path();
1070     if (!path)
1071         return -ENOMEM;
1072     path->reada = READA_FORWARD;
1073 
1074     path2 = btrfs_alloc_path();
1075     if (!path2) {
1076         btrfs_free_path(path);
1077         return -ENOMEM;
1078     }
1079 
1080     ret = add_new_free_space_info(trans, block_group, path2);
1081     if (ret)
1082         goto out;
1083 
1084     mutex_lock(&block_group->free_space_lock);
1085 
1086     /*
1087      * Iterate through all of the extent and metadata items in this block
1088      * group, adding the free space between them and the free space at the
1089      * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
1090      * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
1091      * contained in.
1092      */
1093     key.objectid = block_group->start;
1094     key.type = BTRFS_EXTENT_ITEM_KEY;
1095     key.offset = 0;
1096 
1097     extent_root = btrfs_extent_root(trans->fs_info, key.objectid);
1098     ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
1099     if (ret < 0)
1100         goto out_locked;
1101     ASSERT(ret == 0);
1102 
1103     start = block_group->start;
1104     end = block_group->start + block_group->length;
1105     while (1) {
1106         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1107 
1108         if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1109             key.type == BTRFS_METADATA_ITEM_KEY) {
1110             if (key.objectid >= end)
1111                 break;
1112 
1113             if (start < key.objectid) {
1114                 ret = __add_to_free_space_tree(trans,
1115                                    block_group,
1116                                    path2, start,
1117                                    key.objectid -
1118                                    start);
1119                 if (ret)
1120                     goto out_locked;
1121             }
1122             start = key.objectid;
1123             if (key.type == BTRFS_METADATA_ITEM_KEY)
1124                 start += trans->fs_info->nodesize;
1125             else
1126                 start += key.offset;
1127         } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1128             if (key.objectid != block_group->start)
1129                 break;
1130         }
1131 
1132         ret = btrfs_next_item(extent_root, path);
1133         if (ret < 0)
1134             goto out_locked;
1135         if (ret)
1136             break;
1137     }
1138     if (start < end) {
1139         ret = __add_to_free_space_tree(trans, block_group, path2,
1140                            start, end - start);
1141         if (ret)
1142             goto out_locked;
1143     }
1144 
1145     ret = 0;
1146 out_locked:
1147     mutex_unlock(&block_group->free_space_lock);
1148 out:
1149     btrfs_free_path(path2);
1150     btrfs_free_path(path);
1151     return ret;
1152 }
1153 
1154 int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
1155 {
1156     struct btrfs_trans_handle *trans;
1157     struct btrfs_root *tree_root = fs_info->tree_root;
1158     struct btrfs_root *free_space_root;
1159     struct btrfs_block_group *block_group;
1160     struct rb_node *node;
1161     int ret;
1162 
1163     trans = btrfs_start_transaction(tree_root, 0);
1164     if (IS_ERR(trans))
1165         return PTR_ERR(trans);
1166 
1167     set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1168     set_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1169     free_space_root = btrfs_create_tree(trans,
1170                         BTRFS_FREE_SPACE_TREE_OBJECTID);
1171     if (IS_ERR(free_space_root)) {
1172         ret = PTR_ERR(free_space_root);
1173         goto abort;
1174     }
1175     ret = btrfs_global_root_insert(free_space_root);
1176     if (ret) {
1177         btrfs_put_root(free_space_root);
1178         goto abort;
1179     }
1180 
1181     node = rb_first_cached(&fs_info->block_group_cache_tree);
1182     while (node) {
1183         block_group = rb_entry(node, struct btrfs_block_group,
1184                        cache_node);
1185         ret = populate_free_space_tree(trans, block_group);
1186         if (ret)
1187             goto abort;
1188         node = rb_next(node);
1189     }
1190 
1191     btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1192     btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1193     clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1194     ret = btrfs_commit_transaction(trans);
1195 
1196     /*
1197      * Now that we've committed the transaction any reading of our commit
1198      * root will be safe, so we can cache from the free space tree now.
1199      */
1200     clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1201     return ret;
1202 
1203 abort:
1204     clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1205     clear_bit(BTRFS_FS_FREE_SPACE_TREE_UNTRUSTED, &fs_info->flags);
1206     btrfs_abort_transaction(trans, ret);
1207     btrfs_end_transaction(trans);
1208     return ret;
1209 }
1210 
1211 static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1212                  struct btrfs_root *root)
1213 {
1214     struct btrfs_path *path;
1215     struct btrfs_key key;
1216     int nr;
1217     int ret;
1218 
1219     path = btrfs_alloc_path();
1220     if (!path)
1221         return -ENOMEM;
1222 
1223     key.objectid = 0;
1224     key.type = 0;
1225     key.offset = 0;
1226 
1227     while (1) {
1228         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1229         if (ret < 0)
1230             goto out;
1231 
1232         nr = btrfs_header_nritems(path->nodes[0]);
1233         if (!nr)
1234             break;
1235 
1236         path->slots[0] = 0;
1237         ret = btrfs_del_items(trans, root, path, 0, nr);
1238         if (ret)
1239             goto out;
1240 
1241         btrfs_release_path(path);
1242     }
1243 
1244     ret = 0;
1245 out:
1246     btrfs_free_path(path);
1247     return ret;
1248 }
1249 
1250 int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
1251 {
1252     struct btrfs_trans_handle *trans;
1253     struct btrfs_root *tree_root = fs_info->tree_root;
1254     struct btrfs_key key = {
1255         .objectid = BTRFS_FREE_SPACE_TREE_OBJECTID,
1256         .type = BTRFS_ROOT_ITEM_KEY,
1257         .offset = 0,
1258     };
1259     struct btrfs_root *free_space_root = btrfs_global_root(fs_info, &key);
1260     int ret;
1261 
1262     trans = btrfs_start_transaction(tree_root, 0);
1263     if (IS_ERR(trans))
1264         return PTR_ERR(trans);
1265 
1266     btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1267     btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1268 
1269     ret = clear_free_space_tree(trans, free_space_root);
1270     if (ret)
1271         goto abort;
1272 
1273     ret = btrfs_del_root(trans, &free_space_root->root_key);
1274     if (ret)
1275         goto abort;
1276 
1277     btrfs_global_root_delete(free_space_root);
1278     list_del(&free_space_root->dirty_list);
1279 
1280     btrfs_tree_lock(free_space_root->node);
1281     btrfs_clean_tree_block(free_space_root->node);
1282     btrfs_tree_unlock(free_space_root->node);
1283     btrfs_free_tree_block(trans, btrfs_root_id(free_space_root),
1284                   free_space_root->node, 0, 1);
1285 
1286     btrfs_put_root(free_space_root);
1287 
1288     return btrfs_commit_transaction(trans);
1289 
1290 abort:
1291     btrfs_abort_transaction(trans, ret);
1292     btrfs_end_transaction(trans);
1293     return ret;
1294 }
1295 
1296 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
1297                     struct btrfs_block_group *block_group,
1298                     struct btrfs_path *path)
1299 {
1300     int ret;
1301 
1302     block_group->needs_free_space = 0;
1303 
1304     ret = add_new_free_space_info(trans, block_group, path);
1305     if (ret)
1306         return ret;
1307 
1308     return __add_to_free_space_tree(trans, block_group, path,
1309                     block_group->start,
1310                     block_group->length);
1311 }
1312 
1313 int add_block_group_free_space(struct btrfs_trans_handle *trans,
1314                    struct btrfs_block_group *block_group)
1315 {
1316     struct btrfs_fs_info *fs_info = trans->fs_info;
1317     struct btrfs_path *path = NULL;
1318     int ret = 0;
1319 
1320     if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1321         return 0;
1322 
1323     mutex_lock(&block_group->free_space_lock);
1324     if (!block_group->needs_free_space)
1325         goto out;
1326 
1327     path = btrfs_alloc_path();
1328     if (!path) {
1329         ret = -ENOMEM;
1330         goto out;
1331     }
1332 
1333     ret = __add_block_group_free_space(trans, block_group, path);
1334 
1335 out:
1336     btrfs_free_path(path);
1337     mutex_unlock(&block_group->free_space_lock);
1338     if (ret)
1339         btrfs_abort_transaction(trans, ret);
1340     return ret;
1341 }
1342 
1343 int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1344                   struct btrfs_block_group *block_group)
1345 {
1346     struct btrfs_root *root = btrfs_free_space_root(block_group);
1347     struct btrfs_path *path;
1348     struct btrfs_key key, found_key;
1349     struct extent_buffer *leaf;
1350     u64 start, end;
1351     int done = 0, nr;
1352     int ret;
1353 
1354     if (!btrfs_fs_compat_ro(trans->fs_info, FREE_SPACE_TREE))
1355         return 0;
1356 
1357     if (block_group->needs_free_space) {
1358         /* We never added this block group to the free space tree. */
1359         return 0;
1360     }
1361 
1362     path = btrfs_alloc_path();
1363     if (!path) {
1364         ret = -ENOMEM;
1365         goto out;
1366     }
1367 
1368     start = block_group->start;
1369     end = block_group->start + block_group->length;
1370 
1371     key.objectid = end - 1;
1372     key.type = (u8)-1;
1373     key.offset = (u64)-1;
1374 
1375     while (!done) {
1376         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1377         if (ret)
1378             goto out;
1379 
1380         leaf = path->nodes[0];
1381         nr = 0;
1382         path->slots[0]++;
1383         while (path->slots[0] > 0) {
1384             btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1385 
1386             if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1387                 ASSERT(found_key.objectid == block_group->start);
1388                 ASSERT(found_key.offset == block_group->length);
1389                 done = 1;
1390                 nr++;
1391                 path->slots[0]--;
1392                 break;
1393             } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1394                    found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1395                 ASSERT(found_key.objectid >= start);
1396                 ASSERT(found_key.objectid < end);
1397                 ASSERT(found_key.objectid + found_key.offset <= end);
1398                 nr++;
1399                 path->slots[0]--;
1400             } else {
1401                 ASSERT(0);
1402             }
1403         }
1404 
1405         ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1406         if (ret)
1407             goto out;
1408         btrfs_release_path(path);
1409     }
1410 
1411     ret = 0;
1412 out:
1413     btrfs_free_path(path);
1414     if (ret)
1415         btrfs_abort_transaction(trans, ret);
1416     return ret;
1417 }
1418 
1419 static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1420                    struct btrfs_path *path,
1421                    u32 expected_extent_count)
1422 {
1423     struct btrfs_block_group *block_group;
1424     struct btrfs_fs_info *fs_info;
1425     struct btrfs_root *root;
1426     struct btrfs_key key;
1427     int prev_bit = 0, bit;
1428     /* Initialize to silence GCC. */
1429     u64 extent_start = 0;
1430     u64 end, offset;
1431     u64 total_found = 0;
1432     u32 extent_count = 0;
1433     int ret;
1434 
1435     block_group = caching_ctl->block_group;
1436     fs_info = block_group->fs_info;
1437     root = btrfs_free_space_root(block_group);
1438 
1439     end = block_group->start + block_group->length;
1440 
1441     while (1) {
1442         ret = btrfs_next_item(root, path);
1443         if (ret < 0)
1444             goto out;
1445         if (ret)
1446             break;
1447 
1448         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1449 
1450         if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1451             break;
1452 
1453         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1454         ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1455 
1456         caching_ctl->progress = key.objectid;
1457 
1458         offset = key.objectid;
1459         while (offset < key.objectid + key.offset) {
1460             bit = free_space_test_bit(block_group, path, offset);
1461             if (prev_bit == 0 && bit == 1) {
1462                 extent_start = offset;
1463             } else if (prev_bit == 1 && bit == 0) {
1464                 total_found += add_new_free_space(block_group,
1465                                   extent_start,
1466                                   offset);
1467                 if (total_found > CACHING_CTL_WAKE_UP) {
1468                     total_found = 0;
1469                     wake_up(&caching_ctl->wait);
1470                 }
1471                 extent_count++;
1472             }
1473             prev_bit = bit;
1474             offset += fs_info->sectorsize;
1475         }
1476     }
1477     if (prev_bit == 1) {
1478         total_found += add_new_free_space(block_group, extent_start,
1479                           end);
1480         extent_count++;
1481     }
1482 
1483     if (extent_count != expected_extent_count) {
1484         btrfs_err(fs_info,
1485               "incorrect extent count for %llu; counted %u, expected %u",
1486               block_group->start, extent_count,
1487               expected_extent_count);
1488         ASSERT(0);
1489         ret = -EIO;
1490         goto out;
1491     }
1492 
1493     caching_ctl->progress = (u64)-1;
1494 
1495     ret = 0;
1496 out:
1497     return ret;
1498 }
1499 
1500 static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1501                    struct btrfs_path *path,
1502                    u32 expected_extent_count)
1503 {
1504     struct btrfs_block_group *block_group;
1505     struct btrfs_fs_info *fs_info;
1506     struct btrfs_root *root;
1507     struct btrfs_key key;
1508     u64 end;
1509     u64 total_found = 0;
1510     u32 extent_count = 0;
1511     int ret;
1512 
1513     block_group = caching_ctl->block_group;
1514     fs_info = block_group->fs_info;
1515     root = btrfs_free_space_root(block_group);
1516 
1517     end = block_group->start + block_group->length;
1518 
1519     while (1) {
1520         ret = btrfs_next_item(root, path);
1521         if (ret < 0)
1522             goto out;
1523         if (ret)
1524             break;
1525 
1526         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1527 
1528         if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1529             break;
1530 
1531         ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1532         ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1533 
1534         caching_ctl->progress = key.objectid;
1535 
1536         total_found += add_new_free_space(block_group, key.objectid,
1537                           key.objectid + key.offset);
1538         if (total_found > CACHING_CTL_WAKE_UP) {
1539             total_found = 0;
1540             wake_up(&caching_ctl->wait);
1541         }
1542         extent_count++;
1543     }
1544 
1545     if (extent_count != expected_extent_count) {
1546         btrfs_err(fs_info,
1547               "incorrect extent count for %llu; counted %u, expected %u",
1548               block_group->start, extent_count,
1549               expected_extent_count);
1550         ASSERT(0);
1551         ret = -EIO;
1552         goto out;
1553     }
1554 
1555     caching_ctl->progress = (u64)-1;
1556 
1557     ret = 0;
1558 out:
1559     return ret;
1560 }
1561 
1562 int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1563 {
1564     struct btrfs_block_group *block_group;
1565     struct btrfs_free_space_info *info;
1566     struct btrfs_path *path;
1567     u32 extent_count, flags;
1568     int ret;
1569 
1570     block_group = caching_ctl->block_group;
1571 
1572     path = btrfs_alloc_path();
1573     if (!path)
1574         return -ENOMEM;
1575 
1576     /*
1577      * Just like caching_thread() doesn't want to deadlock on the extent
1578      * tree, we don't want to deadlock on the free space tree.
1579      */
1580     path->skip_locking = 1;
1581     path->search_commit_root = 1;
1582     path->reada = READA_FORWARD;
1583 
1584     info = search_free_space_info(NULL, block_group, path, 0);
1585     if (IS_ERR(info)) {
1586         ret = PTR_ERR(info);
1587         goto out;
1588     }
1589     extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1590     flags = btrfs_free_space_flags(path->nodes[0], info);
1591 
1592     /*
1593      * We left path pointing to the free space info item, so now
1594      * load_free_space_foo can just iterate through the free space tree from
1595      * there.
1596      */
1597     if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1598         ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1599     else
1600         ret = load_free_space_extents(caching_ctl, path, extent_count);
1601 
1602 out:
1603     btrfs_free_path(path);
1604     return ret;
1605 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!