btrfs-progs: check the free space tree in btrfsck

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. This requires pulling in some
code from the kernel to exclude the super stripes.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

1 files changed, 267 insertions, 0 deletions

diff --git a/free-space-tree.c b/free-space-tree.c
new file mode 100644
index 0000000..a323e8a
--- /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;
+}