From: Omar Sandoval <osan...@fb.com>
This reuses the existing code for checking the free space cache, we just
need to load the free space tree. While we do that, we check a couple of
invariants on the free space tree itself.
Signed-off-by: Omar Sandoval <osan...@fb.com>
---
Makefile.in | 2 +-
cmds-check.c | 24 ++++-
extent_io.c | 6 ++
extent_io.h | 2 +
free-space-cache.c | 4 +-
free-space-cache.h | 2 +
free-space-tree.c | 277 +++++++++++++++++++++++++++++++++++++++++++++++++++++
free-space-tree.h | 25 +++++
8 files changed, 335 insertions(+), 7 deletions(-)
create mode 100644 free-space-tree.c
create mode 100644 free-space-tree.h
diff --git a/Makefile.in b/Makefile.in
index 665f83c04d00..cac9a269ee8f 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -38,7 +38,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 0694a3bc5646..2a3910c254a4 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -34,6 +34,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"
@@ -5285,9 +5286,21 @@ 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 = load_free_space_tree(root->fs_info, 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) {
@@ -9495,7 +9508,10 @@ int cmd_check(int argc, char **argv)
goto close_out;
}
- fprintf(stderr, "checking free space cache\n");
+ 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;
diff --git a/extent_io.c b/extent_io.c
index 07695ef8a097..079ab7f2fb7d 100644
--- a/extent_io.c
+++ b/extent_io.c
@@ -885,3 +885,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 27c4b6931c97..a9a7353556a7 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 19ab0c904a71..d10a5f517b10 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 85411a10e64b..9214077a1b27 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 000000000000..527af6e5f2a0
--- /dev/null
+++ b/free-space-tree.c
@@ -0,0 +1,277 @@
+/*
+ * 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) {
+ ret =
btrfs_add_free_space(block_group->free_space_ctl,
+ extent_start,
+ offset -
extent_start);
+ if (ret)
+ goto out;
+ extent_count++;
+ }
+ prev_bit = bit;
+ offset += root->sectorsize;
+ }
+ }
+
+ if (prev_bit == 1) {
+ ret = btrfs_add_free_space(block_group->free_space_ctl,
+ extent_start, end - extent_start);
+ if (ret)
+ goto out;
+ 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)++;
+ }
+ }
+
+ ret = btrfs_add_free_space(block_group->free_space_ctl,
+ key.objectid, key.offset);
+ if (ret)
+ goto out;
+ 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 000000000000..7529a46890da
--- /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
--
2.5.1
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
