diff options
-rw-r--r-- | Makefile.in | 2 | ||||
-rw-r--r-- | cmds-check.c | 35 | ||||
-rw-r--r-- | ctree.h | 6 | ||||
-rw-r--r-- | extent-tree.c | 118 | ||||
-rw-r--r-- | extent_io.c | 6 | ||||
-rw-r--r-- | extent_io.h | 2 | ||||
-rw-r--r-- | free-space-cache.c | 4 | ||||
-rw-r--r-- | free-space-cache.h | 2 | ||||
-rw-r--r-- | free-space-tree.c | 267 | ||||
-rw-r--r-- | free-space-tree.h | 25 |
10 files changed, 459 insertions, 8 deletions
diff --git a/Makefile.in b/Makefile.in index b7a7e269..c32cc705 100644 --- a/Makefile.in +++ b/Makefile.in @@ -70,7 +70,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ extent-cache.o extent_io.o volumes.o utils.o repair.o \ qgroup.o raid6.o free-space-cache.o list_sort.o props.o \ ulist.o qgroup-verify.o backref.o string-table.o task-utils.o \ - inode.o file.o find-root.o + inode.o file.o find-root.o free-space-tree.o cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \ cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \ diff --git a/cmds-check.c b/cmds-check.c index e7516569..680fc875 100644 --- a/cmds-check.c +++ b/cmds-check.c @@ -35,6 +35,7 @@ #include "utils.h" #include "commands.h" #include "free-space-cache.h" +#include "free-space-tree.h" #include "btrfsck.h" #include "qgroup-verify.h" #include "rbtree-utils.h" @@ -5476,9 +5477,29 @@ static int check_space_cache(struct btrfs_root *root) btrfs_remove_free_space_cache(cache); } - ret = load_free_space_cache(root->fs_info, cache); - if (!ret) - continue; + if (btrfs_fs_compat_ro(root->fs_info, + BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) { + ret = exclude_super_stripes(root, cache); + if (ret) { + fprintf(stderr, "could not exclude super stripes: %s\n", + strerror(-ret)); + error++; + continue; + } + ret = load_free_space_tree(root->fs_info, cache); + free_excluded_extents(root, cache); + if (ret < 0) { + fprintf(stderr, "could not load free space tree: %s\n", + strerror(-ret)); + error++; + continue; + } + error += ret; + } else { + ret = load_free_space_cache(root->fs_info, cache); + if (!ret) + continue; + } ret = verify_space_cache(root, cache); if (ret) { @@ -9717,8 +9738,12 @@ int cmd_check(int argc, char **argv) goto close_out; } - if (!ctx.progress_enabled) - fprintf(stderr, "checking free space cache\n"); + if (!ctx.progress_enabled) { + if (btrfs_fs_compat_ro(info, BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) + fprintf(stderr, "checking free space tree\n"); + else + fprintf(stderr, "checking free space cache\n"); + } ret = check_space_cache(root); if (ret) goto out; @@ -2329,6 +2329,12 @@ int btrfs_record_file_extent(struct btrfs_trans_handle *trans, u64 num_bytes); int btrfs_free_block_group(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, u64 len); +void free_excluded_extents(struct btrfs_root *root, + struct btrfs_block_group_cache *cache); +int exclude_super_stripes(struct btrfs_root *root, + struct btrfs_block_group_cache *cache); +u64 add_new_free_space(struct btrfs_block_group_cache *block_group, + struct btrfs_fs_info *info, u64 start, u64 end); /* ctree.c */ int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2); int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, diff --git a/extent-tree.c b/extent-tree.c index e04d9628..1650bdb7 100644 --- a/extent-tree.c +++ b/extent-tree.c @@ -4001,3 +4001,121 @@ fail: btrfs_release_path(&path); return ret; } + + +static int add_excluded_extent(struct btrfs_root *root, + u64 start, u64 num_bytes) +{ + u64 end = start + num_bytes - 1; + set_extent_bits(&root->fs_info->pinned_extents, + start, end, EXTENT_UPTODATE, GFP_NOFS); + return 0; +} + +void free_excluded_extents(struct btrfs_root *root, + struct btrfs_block_group_cache *cache) +{ + u64 start, end; + + start = cache->key.objectid; + end = start + cache->key.offset - 1; + + clear_extent_bits(&root->fs_info->pinned_extents, + start, end, EXTENT_UPTODATE, GFP_NOFS); +} + +int exclude_super_stripes(struct btrfs_root *root, + struct btrfs_block_group_cache *cache) +{ + u64 bytenr; + u64 *logical; + int stripe_len; + int i, nr, ret; + + if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) { + stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid; + cache->bytes_super += stripe_len; + ret = add_excluded_extent(root, cache->key.objectid, + stripe_len); + if (ret) + return ret; + } + + for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) { + bytenr = btrfs_sb_offset(i); + ret = btrfs_rmap_block(&root->fs_info->mapping_tree, + cache->key.objectid, bytenr, + 0, &logical, &nr, &stripe_len); + if (ret) + return ret; + + while (nr--) { + u64 start, len; + + if (logical[nr] > cache->key.objectid + + cache->key.offset) + continue; + + if (logical[nr] + stripe_len <= cache->key.objectid) + continue; + + start = logical[nr]; + if (start < cache->key.objectid) { + start = cache->key.objectid; + len = (logical[nr] + stripe_len) - start; + } else { + len = min_t(u64, stripe_len, + cache->key.objectid + + cache->key.offset - start); + } + + cache->bytes_super += len; + ret = add_excluded_extent(root, start, len); + if (ret) { + kfree(logical); + return ret; + } + } + + kfree(logical); + } + return 0; +} + +u64 add_new_free_space(struct btrfs_block_group_cache *block_group, + struct btrfs_fs_info *info, u64 start, u64 end) +{ + u64 extent_start, extent_end, size, total_added = 0; + int ret; + + while (start < end) { + ret = find_first_extent_bit(&info->pinned_extents, start, + &extent_start, &extent_end, + EXTENT_DIRTY | EXTENT_UPTODATE); + if (ret) + break; + + if (extent_start <= start) { + start = extent_end + 1; + } else if (extent_start > start && extent_start < end) { + size = extent_start - start; + total_added += size; + ret = btrfs_add_free_space(block_group->free_space_ctl, + start, size); + BUG_ON(ret); /* -ENOMEM or logic error */ + start = extent_end + 1; + } else { + break; + } + } + + if (start < end) { + size = end - start; + total_added += size; + ret = btrfs_add_free_space(block_group->free_space_ctl, start, + size); + BUG_ON(ret); /* -ENOMEM or logic error */ + } + + return total_added; +} diff --git a/extent_io.c b/extent_io.c index 75496ce9..88e92736 100644 --- a/extent_io.c +++ b/extent_io.c @@ -884,3 +884,9 @@ void memset_extent_buffer(struct extent_buffer *eb, char c, { memset(eb->data + start, c, len); } + +int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start, + unsigned long nr) +{ + return test_bit(nr, (unsigned long *)(eb->data + start)); +} diff --git a/extent_io.h b/extent_io.h index 27c4b693..a9a73535 100644 --- a/extent_io.h +++ b/extent_io.h @@ -148,6 +148,8 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset, unsigned long src_offset, unsigned long len); void memset_extent_buffer(struct extent_buffer *eb, char c, unsigned long start, unsigned long len); +int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start, + unsigned long nr); int set_extent_buffer_dirty(struct extent_buffer *eb); int clear_extent_buffer_dirty(struct extent_buffer *eb); int read_data_from_disk(struct btrfs_fs_info *info, void *buf, u64 offset, diff --git a/free-space-cache.c b/free-space-cache.c index 19ab0c90..d10a5f51 100644 --- a/free-space-cache.c +++ b/free-space-cache.c @@ -802,8 +802,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) __btrfs_remove_free_space_cache(block_group->free_space_ctl); } -static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, - u64 bytes) +int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, + u64 bytes) { struct btrfs_free_space *info; int ret = 0; diff --git a/free-space-cache.h b/free-space-cache.h index 85411a10..9214077a 100644 --- a/free-space-cache.h +++ b/free-space-cache.h @@ -57,4 +57,6 @@ int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group, int sectorsize); void unlink_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info); +int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, + u64 bytes); #endif diff --git a/free-space-tree.c b/free-space-tree.c new file mode 100644 index 00000000..a323e8aa --- /dev/null +++ b/free-space-tree.c @@ -0,0 +1,267 @@ +/* + * Copyright (C) 2015 Facebook. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#include "ctree.h" +#include "disk-io.h" +#include "free-space-cache.h" +#include "free-space-tree.h" + +static struct btrfs_free_space_info * +search_free_space_info(struct btrfs_trans_handle *trans, + struct btrfs_fs_info *fs_info, + struct btrfs_block_group_cache *block_group, + struct btrfs_path *path, int cow) +{ + struct btrfs_root *root = fs_info->free_space_root; + struct btrfs_key key; + int ret; + + key.objectid = block_group->key.objectid; + key.type = BTRFS_FREE_SPACE_INFO_KEY; + key.offset = block_group->key.offset; + + ret = btrfs_search_slot(trans, root, &key, path, 0, cow); + if (ret < 0) + return ERR_PTR(ret); + if (ret != 0) + return ERR_PTR(-ENOENT); + + return btrfs_item_ptr(path->nodes[0], path->slots[0], + struct btrfs_free_space_info); +} + +static int free_space_test_bit(struct btrfs_block_group_cache *block_group, + struct btrfs_path *path, u64 offset, + u64 sectorsize) +{ + struct extent_buffer *leaf; + struct btrfs_key key; + u64 found_start, found_end; + unsigned long ptr, i; + + leaf = path->nodes[0]; + btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY); + + found_start = key.objectid; + found_end = key.objectid + key.offset; + ASSERT(offset >= found_start && offset < found_end); + + ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); + i = (offset - found_start) / sectorsize; + return !!extent_buffer_test_bit(leaf, ptr, i); +} + +static int load_free_space_bitmaps(struct btrfs_fs_info *fs_info, + struct btrfs_block_group_cache *block_group, + struct btrfs_path *path, + u32 expected_extent_count, + int *errors) +{ + struct btrfs_root *root = fs_info->free_space_root; + struct btrfs_key key; + int prev_bit = 0, bit; + u64 extent_start = 0; + u64 start, end, offset; + u32 extent_count = 0; + int ret; + + start = block_group->key.objectid; + end = block_group->key.objectid + block_group->key.offset; + + while (1) { + ret = btrfs_next_item(root, path); + if (ret < 0) + goto out; + if (ret) + break; + + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + + if (key.type == BTRFS_FREE_SPACE_INFO_KEY) + break; + + if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY) { + fprintf(stderr, "unexpected key of type %u\n", key.type); + (*errors)++; + break; + } + if (key.objectid >= end) { + fprintf(stderr, "free space bitmap starts at %Lu, beyond end of block group %Lu-%Lu\n", + key.objectid, start, end); + (*errors)++; + break; + } + if (key.objectid + key.offset > end) { + fprintf(stderr, "free space bitmap ends at %Lu, beyond end of block group %Lu-%Lu\n", + key.objectid, start, end); + (*errors)++; + break; + } + + offset = key.objectid; + while (offset < key.objectid + key.offset) { + bit = free_space_test_bit(block_group, path, offset, + root->sectorsize); + if (prev_bit == 0 && bit == 1) { + extent_start = offset; + } else if (prev_bit == 1 && bit == 0) { + add_new_free_space(block_group, fs_info, extent_start, offset); + extent_count++; + } + prev_bit = bit; + offset += root->sectorsize; + } + } + + if (prev_bit == 1) { + add_new_free_space(block_group, fs_info, extent_start, end); + extent_count++; + } + + if (extent_count != expected_extent_count) { + fprintf(stderr, "free space info recorded %u extents, counted %u\n", + expected_extent_count, extent_count); + (*errors)++; + } + + ret = 0; +out: + return ret; +} + +static int load_free_space_extents(struct btrfs_fs_info *fs_info, + struct btrfs_block_group_cache *block_group, + struct btrfs_path *path, + u32 expected_extent_count, + int *errors) +{ + struct btrfs_root *root = fs_info->free_space_root; + struct btrfs_key key, prev_key; + int have_prev = 0; + u64 start, end; + u32 extent_count = 0; + int ret; + + start = block_group->key.objectid; + end = block_group->key.objectid + block_group->key.offset; + + while (1) { + ret = btrfs_next_item(root, path); + if (ret < 0) + goto out; + if (ret) + break; + + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + + if (key.type == BTRFS_FREE_SPACE_INFO_KEY) + break; + + if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) { + fprintf(stderr, "unexpected key of type %u\n", key.type); + (*errors)++; + break; + } + if (key.objectid >= end) { + fprintf(stderr, "free space extent starts at %Lu, beyond end of block group %Lu-%Lu\n", + key.objectid, start, end); + (*errors)++; + break; + } + if (key.objectid + key.offset > end) { + fprintf(stderr, "free space extent ends at %Lu, beyond end of block group %Lu-%Lu\n", + key.objectid, start, end); + (*errors)++; + break; + } + + if (have_prev) { + u64 cur_start = key.objectid; + u64 cur_end = cur_start + key.offset; + u64 prev_start = prev_key.objectid; + u64 prev_end = prev_start + prev_key.offset; + + if (cur_start < prev_end) { + fprintf(stderr, "free space extent %Lu-%Lu overlaps with previous %Lu-%Lu\n", + cur_start, cur_end, + prev_start, prev_end); + (*errors)++; + } else if (cur_start == prev_end) { + fprintf(stderr, "free space extent %Lu-%Lu is unmerged with previous %Lu-%Lu\n", + cur_start, cur_end, + prev_start, prev_end); + (*errors)++; + } + } + + add_new_free_space(block_group, fs_info, key.objectid, key.objectid + key.offset); + extent_count++; + + prev_key = key; + have_prev = 1; + } + + if (extent_count != expected_extent_count) { + fprintf(stderr, "free space info recorded %u extents, counted %u\n", + expected_extent_count, extent_count); + (*errors)++; + } + + ret = 0; +out: + return ret; +} + +int load_free_space_tree(struct btrfs_fs_info *fs_info, + struct btrfs_block_group_cache *block_group) +{ + struct btrfs_free_space_info *info; + struct btrfs_path *path; + u32 extent_count, flags; + int errors = 0; + int ret; + + path = btrfs_alloc_path(); + if (!path) + return -ENOMEM; + path->reada = 1; + + info = search_free_space_info(NULL, fs_info, block_group, path, 0); + if (IS_ERR(info)) { + ret = PTR_ERR(info); + goto out; + } + extent_count = btrfs_free_space_extent_count(path->nodes[0], info); + flags = btrfs_free_space_flags(path->nodes[0], info); + + if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { + ret = load_free_space_bitmaps(fs_info, block_group, path, + extent_count, &errors); + } else { + ret = load_free_space_extents(fs_info, block_group, path, + extent_count, &errors); + } + if (ret) + goto out; + + ret = 0; +out: + btrfs_free_path(path); + return ret ? ret : errors; +} diff --git a/free-space-tree.h b/free-space-tree.h new file mode 100644 index 00000000..7529a468 --- /dev/null +++ b/free-space-tree.h @@ -0,0 +1,25 @@ +/* + * Copyright (C) 2015 Facebook. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#ifndef __BTRFS_FREE_SPACE_TREE_H__ +#define __BTRFS_FREE_SPACE_TREE_H__ + +int load_free_space_tree(struct btrfs_fs_info *fs_info, + struct btrfs_block_group_cache *block_group); + +#endif |