btrfs-progs: check: check tree blocks using walking tree down and up
diff mbox

Message ID 20170727105739.4867-1-suy.fnst@cn.fujitsu.com
State New
Headers show

Commit Message

Su Yue July 27, 2017, 10:57 a.m. UTC
This patch prepares for extent-tree repair in lowmem mode.
In the lowmem mode, checking tree blocks of various tree is in
recursive way.
But if during repair, add or delete of item(s) may modify upper nodes which
will cause the repair to be complicated and dangerous.

Changing the way of traversal to be same as fs tree which calls
walk_down_tree_v2() and walk_up_tree_v2() is easy for further
repair. And now check_***_items() is with btrfs_path.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 cmds-check.c | 325 +++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 182 insertions(+), 143 deletions(-)

Patch
diff mbox

diff --git a/cmds-check.c b/cmds-check.c
index 23adc032..dadad0b3 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -2227,14 +2227,48 @@  out:
 
 static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path,
 			    unsigned int ext_ref);
+static int check_leaf_items(struct btrfs_root *root, struct btrfs_path *path);
+static int check_tree_block_ref(struct btrfs_root *root,
+				struct extent_buffer *eb, u64 bytenr,
+				int level, u64 owner);
+static int fs_root_objectid(u64 objectid);
 
 /*
+ * Update global fs information.
+ */
+static void account_bytes(struct btrfs_root *root, struct btrfs_path *path,
+			 int level)
+{
+	u32 free_nrs;
+	struct extent_buffer *eb = path->nodes[level];
+
+	total_btree_bytes += eb->len;
+	if (fs_root_objectid(root->objectid))
+		total_fs_tree_bytes += eb->len;
+	if (btrfs_header_owner(eb) == BTRFS_EXTENT_TREE_OBJECTID)
+		total_extent_tree_bytes += eb->len;
+
+	if (level == 0) {
+		btree_space_waste +=
+			btrfs_leaf_free_space(root, eb);
+	} else {
+		free_nrs = (BTRFS_NODEPTRS_PER_BLOCK(root) -
+			    btrfs_header_nritems(eb));
+		btree_space_waste += free_nrs *
+			sizeof(struct btrfs_key_ptr);
+	}
+}
+
+/*
+ * @account do account and check tree block ref if it is not zero
+ *
  * Returns >0  Found error, should continue
  * Returns <0  Fatal error, must exit the whole check
  * Returns 0   No errors found
  */
 static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
-			     int *level, struct node_refs *nrefs, int ext_ref)
+			     int *level, struct node_refs *nrefs, int ext_ref,
+			     int account)
 {
 	enum btrfs_tree_block_status status;
 	u64 bytenr;
@@ -2242,15 +2276,19 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 	struct extent_buffer *next;
 	struct extent_buffer *cur;
 	u32 blocksize;
-	int ret;
+	int ret = 0;
+	int err = 0;
+	int is_fs = is_fstree(root->objectid);
 
 	WARN_ON(*level < 0);
 	WARN_ON(*level >= BTRFS_MAX_LEVEL);
 
-	ret = update_nodes_refs(root, path->nodes[*level]->start,
+	if (is_fs) {
+		ret = update_nodes_refs(root, path->nodes[*level]->start,
 				nrefs, *level);
-	if (ret < 0)
-		return ret;
+		if (ret < 0)
+			return ret;
+	}
 
 	while (*level >= 0) {
 		WARN_ON(*level < 0);
@@ -2259,23 +2297,41 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 
 		if (btrfs_header_level(cur) != *level)
 			WARN_ON(1);
+	       /*
+		* Update bytes accounting and check tree block ref
+		* *NOTICE* Doing account and check before check nritems
+		* is necessary because of empty node/leaf.
+		*/
+		if (account && path->slots[*level] == 0) {
+			account_bytes(root, path, *level);
+			err |= check_tree_block_ref(root, cur,
+				btrfs_header_bytenr(path->nodes[*level]),
+				btrfs_header_level(path->nodes[*level]),
+				btrfs_header_owner(path->nodes[*level]));
+		}
 
 		if (path->slots[*level] >= btrfs_header_nritems(cur))
 			break;
+
 		/* Don't forgot to check leaf/node validation */
 		if (*level == 0) {
 			ret = btrfs_check_leaf(root, NULL, cur);
 			if (ret != BTRFS_TREE_BLOCK_CLEAN) {
-				ret = -EIO;
+				err |= -EIO;
 				break;
 			}
-			ret = process_one_leaf_v2(root, path, nrefs,
-						  level, ext_ref);
+
+			if (is_fs && !account)
+				ret = process_one_leaf_v2(root, path, nrefs,
+							  level, ext_ref);
+			else
+				ret = check_leaf_items(root, path);
+			err |= ret;
 			break;
 		} else {
 			ret = btrfs_check_node(root, NULL, cur);
 			if (ret != BTRFS_TREE_BLOCK_CLEAN) {
-				ret = -EIO;
+				err |= -EIO;
 				break;
 			}
 		}
@@ -2283,14 +2339,18 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
 		blocksize = root->nodesize;
 
-		ret = update_nodes_refs(root, bytenr, nrefs, *level - 1);
-		if (ret)
-			break;
-		if (!nrefs->need_check[*level - 1]) {
-			path->slots[*level]++;
-			continue;
+		if (is_fs) {
+			ret = update_nodes_refs(root, bytenr, nrefs,
+						*level - 1);
+			if (ret) {
+				err |= ret;
+				break;
+			}
+			if (!nrefs->need_check[*level - 1]) {
+				path->slots[*level]++;
+				continue;
+			}
 		}
-
 		next = btrfs_find_tree_block(root, bytenr, blocksize);
 		if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
 			free_extent_buffer(next);
@@ -2307,12 +2367,13 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 						&node_key,
 						path->nodes[*level]->start,
 						root->nodesize, *level);
-				ret = -EIO;
+				err |= -EIO;
 				break;
 			}
 		}
 
 		ret = check_child_node(cur, path->slots[*level], next);
+		err |= ret;
 		if (ret < 0) 
 			break;
 
@@ -2322,7 +2383,7 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 			status = btrfs_check_node(root, NULL, next);
 		if (status != BTRFS_TREE_BLOCK_CLEAN) {
 			free_extent_buffer(next);
-			ret = -EIO;
+			err |= -EIO;
 			break;
 		}
 
@@ -2331,7 +2392,7 @@  static int walk_down_tree_v2(struct btrfs_root *root, struct btrfs_path *path,
 		path->nodes[*level] = next;
 		path->slots[*level] = 0;
 	}
-	return ret;
+	return err;
 }
 
 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
@@ -5051,16 +5112,22 @@  out:
 	return ret;
 }
 
+static int should_check(struct btrfs_root *root, struct extent_buffer *eb);
+
 /*
- * Iterate all item on the tree and call check_inode_item() to check.
+ * This function calls walk_down_tree_v2 and walk_up_tree_v2 to check tree
+ * blocks and integrity of fs tree items.
  *
- * @root:	the root of the tree to be checked.
- * @ext_ref:	the EXTENDED_IREF feature
- *
- * Return 0 if no error found.
- * Return <0 for error.
+ * @root:         the root of the tree to be checked.
+ * @ext_ref       feature EXTENDED_IREF is enable or not.
+ * @account       if NOT 0 means check the tree(include tree)'s treeblocks.
+ *                otherwise means check fs tree(s) items relationship and
+ *		  @root *MUST* be a fs tree root.
+ * Returns 0      represents OK.
+ * Returns not 0  represents error.
  */
-static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
+static int check_btrfs_root(struct btrfs_root *root, unsigned int ext_ref,
+			    int account)
 {
 	struct btrfs_path path;
 	struct node_refs nrefs;
@@ -5068,16 +5135,19 @@  static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
 	int ret;
 	int level;
 	int err = 0;
+	int is_fs = is_fstree(root->objectid);
 
-	/*
-	 * We need to manually check the first inode item(256)
-	 * As the following traversal function will only start from
-	 * the first inode item in the leaf, if inode item(256) is missing
-	 * we will just skip it forever.
-	 */
-	ret = check_fs_first_inode(root, ext_ref);
-	if (ret < 0)
-		return ret;
+	if (is_fs && !account) {
+		/*
+		 * We need to manually check the first inode item(256)
+		 * As the following traversal function will only start from
+		 * the first inode item in the leaf, if inode item(256) is
+		 * missing we will just skip it forever.
+		 */
+		ret = check_fs_first_inode(root, ext_ref);
+		if (ret < 0)
+			return ret;
+	}
 
 	memset(&nrefs, 0, sizeof(nrefs));
 	level = btrfs_header_level(root->node);
@@ -5098,10 +5168,24 @@  static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
 		if (ret < 0)
 			goto out;
 		ret = 0;
+
+		/*
+		 * While the tree is in drop progress, path.slots[0]
+		 * may not be 0.
+		 */
+		if (account && path.slots[level] != 0 &&
+		    should_check(root, path.nodes[level])) {
+			account_bytes(root, &path, level);
+			err |= check_tree_block_ref(root, path.nodes[level],
+					btrfs_header_bytenr(path.nodes[level]),
+					btrfs_header_level(path.nodes[level]),
+					btrfs_header_owner(path.nodes[level]));
+		}
 	}
 
 	while (1) {
-		ret = walk_down_tree_v2(root, &path, &level, &nrefs, ext_ref);
+		ret = walk_down_tree_v2(root, &path, &level, &nrefs, ext_ref,
+					account);
 		err |= !!ret;
 
 		/* if ret is negative, walk shall stop */
@@ -5124,6 +5208,20 @@  out:
 }
 
 /*
+ * Iterate all items on the tree and call check_inode_item() to check.
+ *
+ * @root:	the root of the tree to be checked.
+ * @ext_ref:	the EXTENDED_IREF feature
+ *
+ * Return 0 if no error found.
+ * Return <0 for error.
+ */
+static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref)
+{
+	return check_btrfs_root(root, ext_ref, 0);
+}
+
+/*
  * Find the relative ref for root_ref and root_backref.
  *
  * @root:	the root of the root tree.
@@ -10209,9 +10307,10 @@  out:
  * Return 0 for no error found
  */
 static int check_extent_data_item(struct btrfs_root *root,
-				  struct extent_buffer *eb, int slot)
+				  struct btrfs_path *pathp)
 {
 	struct btrfs_file_extent_item *fi;
+	struct extent_buffer *eb = pathp->nodes[0];
 	struct btrfs_path path;
 	struct btrfs_root *extent_root = root->fs_info->extent_root;
 	struct btrfs_key fi_key;
@@ -10231,6 +10330,7 @@  static int check_extent_data_item(struct btrfs_root *root,
 	int type;
 	u64 ref_root;
 	int found_dbackref = 0;
+	int slot = pathp->slots[0];
 	int err = 0;
 	int ret;
 
@@ -10243,6 +10343,7 @@  static int check_extent_data_item(struct btrfs_root *root,
 		return 0;
 
 	disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
+
 	disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 	extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
 
@@ -10766,13 +10867,15 @@  out:
  * Since we don't use extent_record anymore, introduce new error bit
  */
 static int check_extent_item(struct btrfs_fs_info *fs_info,
-			     struct extent_buffer *eb, int slot)
+			     struct btrfs_path *path)
 {
 	struct btrfs_extent_item *ei;
 	struct btrfs_extent_inline_ref *iref;
 	struct btrfs_extent_data_ref *dref;
+	struct extent_buffer *eb = path->nodes[0];
 	unsigned long end;
 	unsigned long ptr;
+	int slot = path->slots[0];
 	int type;
 	u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
 	u32 item_size = btrfs_item_size_nr(eb, slot);
@@ -10887,15 +10990,17 @@  out:
  * Check if a dev extent item is referred correctly by its chunk
  */
 static int check_dev_extent_item(struct btrfs_fs_info *fs_info,
-				 struct extent_buffer *eb, int slot)
+				 struct btrfs_path *pathp)
 {
 	struct btrfs_root *chunk_root = fs_info->chunk_root;
+	struct extent_buffer *eb = pathp->nodes[0];
 	struct btrfs_dev_extent *ptr;
 	struct btrfs_path path;
 	struct btrfs_key chunk_key;
 	struct btrfs_key devext_key;
 	struct btrfs_chunk *chunk;
 	struct extent_buffer *l;
+	int slot = pathp->slots[0];
 	int num_stripes;
 	u64 length;
 	int i;
@@ -10946,16 +11051,18 @@  out:
  * Check if the used space is correct with the dev item
  */
 static int check_dev_item(struct btrfs_fs_info *fs_info,
-			  struct extent_buffer *eb, int slot)
+			  struct btrfs_path *pathp)
 {
 	struct btrfs_root *dev_root = fs_info->dev_root;
 	struct btrfs_dev_item *dev_item;
 	struct btrfs_path path;
 	struct btrfs_key key;
 	struct btrfs_dev_extent *ptr;
+	struct extent_buffer *eb = pathp->nodes[0];
 	u64 dev_id;
 	u64 used;
 	u64 total = 0;
+	int slot = pathp->slots[0];
 	int ret;
 
 	dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
@@ -11013,10 +11120,11 @@  next:
  * with extent/metadata item
  */
 static int check_block_group_item(struct btrfs_fs_info *fs_info,
-				  struct extent_buffer *eb, int slot)
+				  struct btrfs_path *pathp)
 {
 	struct btrfs_root *extent_root = fs_info->extent_root;
 	struct btrfs_root *chunk_root = fs_info->chunk_root;
+	struct extent_buffer *eb = pathp->nodes[0];
 	struct btrfs_block_group_item *bi;
 	struct btrfs_block_group_item bg_item;
 	struct btrfs_path path;
@@ -11031,6 +11139,7 @@  static int check_block_group_item(struct btrfs_fs_info *fs_info,
 	u64 bg_flags;
 	u64 used;
 	u64 total = 0;
+	int slot = pathp->slots[0];
 	int ret;
 	int err = 0;
 
@@ -11142,10 +11251,11 @@  out:
  * Including checking all referred dev_extents and block group
  */
 static int check_chunk_item(struct btrfs_fs_info *fs_info,
-			    struct extent_buffer *eb, int slot)
+			    struct btrfs_path *pathp)
 {
 	struct btrfs_root *extent_root = fs_info->extent_root;
 	struct btrfs_root *dev_root = fs_info->dev_root;
+	struct extent_buffer *eb = pathp->nodes[0];
 	struct btrfs_path path;
 	struct btrfs_key chunk_key;
 	struct btrfs_key bg_key;
@@ -11163,6 +11273,7 @@  static int check_chunk_item(struct btrfs_fs_info *fs_info,
 	int num_stripes;
 	u64 offset;
 	u64 objectid;
+	int slot = pathp->slots[0];
 	int i;
 	int ret;
 	int err = 0;
@@ -11252,51 +11363,64 @@  out:
 	return err;
 }
 
+
 /*
  * Main entry function to check known items and update related accounting info
  */
-static int check_leaf_items(struct btrfs_root *root, struct extent_buffer *eb)
+static int check_leaf_items(struct btrfs_root *root, struct btrfs_path *path)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct btrfs_key key;
-	int slot = 0;
+	struct extent_buffer *eb = path->nodes[0];
+	int slot;
 	int type;
 	struct btrfs_extent_data_ref *dref;
-	int ret;
+	int ret = 0;
 	int err = 0;
 
 next:
+	slot = path->slots[0];
+	if (slot >= btrfs_header_nritems(eb)) {
+		if (slot == 0) {
+			error("Empty leaf [%llu %u] root %llu",
+			      eb->start, root->nodesize, root->objectid);
+			err |= EIO;
+		}
+		goto out;
+	}
+
 	btrfs_item_key_to_cpu(eb, &key, slot);
 	type = key.type;
 
 	switch (type) {
 	case BTRFS_EXTENT_DATA_KEY:
-		ret = check_extent_data_item(root, eb, slot);
+		ret = check_extent_data_item(root, path);
 		err |= ret;
 		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
-		ret = check_block_group_item(fs_info, eb, slot);
+		ret = check_block_group_item(fs_info, path);
 		err |= ret;
 		break;
 	case BTRFS_DEV_ITEM_KEY:
-		ret = check_dev_item(fs_info, eb, slot);
+		ret = check_dev_item(fs_info, path);
 		err |= ret;
 		break;
 	case BTRFS_CHUNK_ITEM_KEY:
-		ret = check_chunk_item(fs_info, eb, slot);
+		ret = check_chunk_item(fs_info, path);
 		err |= ret;
 		break;
 	case BTRFS_DEV_EXTENT_KEY:
-		ret = check_dev_extent_item(fs_info, eb, slot);
+		ret = check_dev_extent_item(fs_info, path);
 		err |= ret;
 		break;
 	case BTRFS_EXTENT_ITEM_KEY:
 	case BTRFS_METADATA_ITEM_KEY:
-		ret = check_extent_item(fs_info, eb, slot);
+		ret = check_extent_item(fs_info, path);
 		err |= ret;
 		break;
 	case BTRFS_EXTENT_CSUM_KEY:
 		total_csum_bytes += btrfs_item_size_nr(eb, slot);
+		err |= ret;
 		break;
 	case BTRFS_TREE_BLOCK_REF_KEY:
 		ret = check_tree_block_backref(fs_info, key.offset,
@@ -11327,9 +11451,9 @@  next:
 		break;
 	}
 
-	if (++slot < btrfs_header_nritems(eb))
-		goto next;
-
+	++path->slots[0];
+	goto next;
+out:
 	return err;
 }
 
@@ -11423,91 +11547,6 @@  need_check:
 }
 
 /*
- * Traversal function for tree block. We will do:
- * 1) Skip shared fs/subvolume tree blocks
- * 2) Update related bytes accounting
- * 3) Pre-order traversal
- */
-static int traverse_tree_block(struct btrfs_root *root,
-				struct extent_buffer *node)
-{
-	struct extent_buffer *eb;
-	struct btrfs_key key;
-	struct btrfs_key drop_key;
-	int level;
-	u64 nr;
-	int i;
-	int err = 0;
-	int ret;
-
-	/*
-	 * Skip shared fs/subvolume tree block, in that case they will
-	 * be checked by referencer with lowest rootid
-	 */
-	if (is_fstree(root->objectid) && !should_check(root, node))
-		return 0;
-
-	/* Update bytes accounting */
-	total_btree_bytes += node->len;
-	if (fs_root_objectid(btrfs_header_owner(node)))
-		total_fs_tree_bytes += node->len;
-	if (btrfs_header_owner(node) == BTRFS_EXTENT_TREE_OBJECTID)
-		total_extent_tree_bytes += node->len;
-	if (!found_old_backref &&
-	    btrfs_header_owner(node) == BTRFS_TREE_RELOC_OBJECTID &&
-	    btrfs_header_backref_rev(node) == BTRFS_MIXED_BACKREF_REV &&
-	    !btrfs_header_flag(node, BTRFS_HEADER_FLAG_RELOC))
-		found_old_backref = 1;
-
-	/* pre-order tranversal, check itself first */
-	level = btrfs_header_level(node);
-	ret = check_tree_block_ref(root, node, btrfs_header_bytenr(node),
-				   btrfs_header_level(node),
-				   btrfs_header_owner(node));
-	err |= ret;
-	if (err)
-		error(
-	"check %s failed root %llu bytenr %llu level %d, force continue check",
-			level ? "node":"leaf", root->objectid,
-			btrfs_header_bytenr(node), btrfs_header_level(node));
-
-	if (!level) {
-		btree_space_waste += btrfs_leaf_free_space(root, node);
-		ret = check_leaf_items(root, node);
-		err |= ret;
-		return err;
-	}
-
-	nr = btrfs_header_nritems(node);
-	btrfs_disk_key_to_cpu(&drop_key, &root->root_item.drop_progress);
-	btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) - nr) *
-		sizeof(struct btrfs_key_ptr);
-
-	/* Then check all its children */
-	for (i = 0; i < nr; i++) {
-		u64 blocknr = btrfs_node_blockptr(node, i);
-
-		btrfs_node_key_to_cpu(node, &key, i);
-		if (level == root->root_item.drop_level &&
-		    is_dropped_key(&key, &drop_key))
-			continue;
-
-		/*
-		 * As a btrfs tree has most 8 levels (0..7), so it's quite safe
-		 * to call the function itself.
-		 */
-		eb = read_tree_block(root, blocknr, root->nodesize, 0);
-		if (extent_buffer_uptodate(eb)) {
-			ret = traverse_tree_block(root, eb);
-			err |= ret;
-		}
-		free_extent_buffer(eb);
-	}
-
-	return err;
-}
-
-/*
  * Low memory usage version check_chunks_and_extents.
  */
 static int check_chunks_and_extents_v2(struct btrfs_root *root)
@@ -11520,11 +11559,11 @@  static int check_chunks_and_extents_v2(struct btrfs_root *root)
 	int ret;
 
 	root1 = root->fs_info->chunk_root;
-	ret = traverse_tree_block(root1, root1->node);
+	ret = check_btrfs_root(root1, 0, 1);
 	err |= ret;
 
 	root1 = root->fs_info->tree_root;
-	ret = traverse_tree_block(root1, root1->node);
+	ret = check_btrfs_root(root1, 0, 1);
 	err |= ret;
 
 	btrfs_init_path(&path);
@@ -11534,7 +11573,7 @@  static int check_chunks_and_extents_v2(struct btrfs_root *root)
 
 	ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0);
 	if (ret) {
-		error("cannot find extent treet in tree_root");
+		error("cannot find extent tree in tree_root");
 		goto out;
 	}
 
@@ -11554,7 +11593,7 @@  static int check_chunks_and_extents_v2(struct btrfs_root *root)
 			goto next;
 		}
 
-		ret = traverse_tree_block(cur_root, cur_root->node);
+		ret = check_btrfs_root(cur_root, 0, 1);
 		err |= ret;
 
 		if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)