btrfs-progs: check: introduce function to speed up fs tree check

Introduce function should_check() to reduced duplicated tree block check
for fs/subvolume tree.

The idea is, we only check the fs/subvolue tree block if we have the
lowest referencer rootid, according to extent tree.

In that case, we can skip a lot of fs/subvolume tree block checks if
there are a lot of snapshots.

Although we will do a lot of extent tree searches for it.

Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Reviewed-by: Josef Bacik <jbacik@fb.com>
Signed-off-by: David Sterba <dsterba@suse.com>

diff --git a/cmds-check.c b/cmds-check.c
index 5817889..59d4867 100644 (file)
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -9786,6 +9786,95 @@ next:
        return err;
 }
 
+/*
+ * Helper function for later fs/subvol tree check.  To determine if a tree
+ * block should be checked.
+ * This function will ensure only the direct referencer with lowest rootid to
+ * check a fs/subvolume tree block.
+ *
+ * Backref check at extent tree would detect errors like missing subvolume
+ * tree, so we can do aggressive check to reduce duplicated checks.
+ */
+static int should_check(struct btrfs_root *root, struct extent_buffer *eb)
+{
+       struct btrfs_root *extent_root = root->fs_info->extent_root;
+       struct btrfs_key key;
+       struct btrfs_path path;
+       struct extent_buffer *leaf;
+       int slot;
+       struct btrfs_extent_item *ei;
+       unsigned long ptr;
+       unsigned long end;
+       int type;
+       u32 item_size;
+       u64 offset;
+       struct btrfs_extent_inline_ref *iref;
+       int ret;
+
+       btrfs_init_path(&path);
+       key.objectid = btrfs_header_bytenr(eb);
+       key.type = BTRFS_METADATA_ITEM_KEY;
+       key.offset = (u64)-1;
+
+       /*
+        * Any failure in backref resolving means we can't determine
+        * whom the tree block belongs to.
+        * So in that case, we need to check that tree block
+        */
+       ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+       if (ret < 0)
+               goto need_check;
+
+       ret = btrfs_previous_extent_item(extent_root, &path,
+                                        btrfs_header_bytenr(eb));
+       if (ret)
+               goto need_check;
+
+       leaf = path.nodes[0];
+       slot = path.slots[0];
+       btrfs_item_key_to_cpu(leaf, &key, slot);
+       ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+
+       if (key.type == BTRFS_METADATA_ITEM_KEY) {
+               iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+       } else {
+               struct btrfs_tree_block_info *info;
+
+               info = (struct btrfs_tree_block_info *)(ei + 1);
+               iref = (struct btrfs_extent_inline_ref *)(info + 1);
+       }
+
+       item_size = btrfs_item_size_nr(leaf, slot);
+       ptr = (unsigned long)iref;
+       end = (unsigned long)ei + item_size;
+       while (ptr < end) {
+               iref = (struct btrfs_extent_inline_ref *)ptr;
+               type = btrfs_extent_inline_ref_type(leaf, iref);
+               offset = btrfs_extent_inline_ref_offset(leaf, iref);
+
+               /*
+                * We only check the tree block if current root is
+                * the lowest referencer of it.
+                */
+               if (type == BTRFS_TREE_BLOCK_REF_KEY &&
+                   offset < root->objectid) {
+                       btrfs_release_path(&path);
+                       return 0;
+               }
+
+               ptr += btrfs_extent_inline_ref_size(type);
+       }
+       /*
+        * Normally we should also check keyed tree block ref, but that may be
+        * very time consuming.  Inlined ref should already make us skip a lot
+        * of refs now.  So skip search keyed tree block ref.
+        */
+
+need_check:
+       btrfs_release_path(&path);
+       return 1;
+}
+
 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
                           struct btrfs_root *root, int overwrite)
 {