[Ocfs2-tools-devel] [PATCH 36/50] fsck.ocfs2: Record refcount tree we have checked.

[Tao Ma]

We check refcount tree if an inode have one. But there
are many inodes sharing the same tree, and we only need
to check once.

This patch adds a rb-tree to store the already-checked
refcount tree so that we can skip them. Also we added
the checked inodes to a list so that it can be used later
by other patches.

Signed-off-by: Tao Ma <tao.ma at oracle.com>
---
 fsck.ocfs2/fsck.c         |    1 +
 fsck.ocfs2/include/fsck.h |    2 +
 fsck.ocfs2/refcount.c     |   87 +++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 88 insertions(+), 2 deletions(-)

diff --git a/fsck.ocfs2/fsck.c b/fsck.ocfs2/fsck.c
index 6fdc02a..ead4f20 100644
--- a/fsck.ocfs2/fsck.c
+++ b/fsck.ocfs2/fsck.c
@@ -642,6 +642,7 @@ int main(int argc, char **argv)
 	ost->ost_ask = 1;
 	ost->ost_dirblocks.db_root = RB_ROOT;
 	ost->ost_dir_parents = RB_ROOT;
+	ost->ost_refcount_trees = RB_ROOT;
 
 	/* These mean "autodetect" */
 	blksize = 0;
diff --git a/fsck.ocfs2/include/fsck.h b/fsck.ocfs2/include/fsck.h
index a533aad..f671a8a 100644
--- a/fsck.ocfs2/include/fsck.h
+++ b/fsck.ocfs2/include/fsck.h
@@ -58,6 +58,8 @@ typedef struct _o2fsck_state {
 
 	struct rb_root	ost_dir_parents;
 
+	struct rb_root	ost_refcount_trees;
+
 	unsigned	ost_ask:1,	/* confirm with the user */
 			ost_answer:1,	/* answer if we don't ask the user */
 			ost_force:1,	/* -f supplied; force check */
diff --git a/fsck.ocfs2/refcount.c b/fsck.ocfs2/refcount.c
index 5ec7dd4..346117d 100644
--- a/fsck.ocfs2/refcount.c
+++ b/fsck.ocfs2/refcount.c
@@ -18,6 +18,9 @@
 #include <inttypes.h>
 #include <assert.h>
 
+#include "ocfs2/kernel-rbtree.h"
+#include "ocfs2-kernel/kernel-list.h"
+
 #include "ocfs2/ocfs2.h"
 #include "problem.h"
 #include "fsck.h"
@@ -32,6 +35,18 @@ struct check_refcount_rec {
 	uint64_t c_end;
 };
 
+struct refcount_file {
+	struct list_head list;
+	uint64_t i_blkno;
+};
+
+struct refcount_tree {
+	struct rb_node ref_node;
+	uint64_t rf_blkno;
+	struct list_head files_list;
+	int is_valid;
+};
+
 static errcode_t check_rb(o2fsck_state *ost, uint64_t blkno,
 			  uint64_t root_blkno, uint64_t *c_end, int *is_valid);
 
@@ -287,20 +302,79 @@ out:
 	return 0;
 }
 
+/* See if the recount_tree rbtree has the given ref_blkno.  */
+static struct refcount_tree*
+refcount_tree_lookup(o2fsck_state *ost, uint64_t ref_blkno)
+{
+	struct rb_node *p = ost->ost_refcount_trees.rb_node;
+	struct refcount_tree *ref_tree;
+
+	while (p) {
+		ref_tree = rb_entry(p, struct refcount_tree, ref_node);
+		if (ref_blkno < ref_tree->rf_blkno)
+			p = p->rb_left;
+		else if (ref_blkno > ref_tree->rf_blkno)
+			p = p->rb_right;
+		else
+			return ref_tree;
+	}
+
+	return NULL;
+}
+
+static void refcount_tree_insert(o2fsck_state *ost,
+				 struct refcount_tree *insert_rb)
+{
+	struct rb_node **p = &ost->ost_refcount_trees.rb_node;
+	struct rb_node *parent = NULL;
+	struct refcount_tree *ref_tree = NULL;
+
+	while (*p) {
+		parent = *p;
+		ref_tree = rb_entry(parent, struct refcount_tree, ref_node);
+		if (insert_rb->rf_blkno < ref_tree->rf_blkno)
+			p = &(*p)->rb_left;
+		else if (insert_rb->rf_blkno > ref_tree->rf_blkno)
+			p = &(*p)->rb_right;
+		else
+			assert(0);  /* Caller checked */
+	}
+
+	rb_link_node(&insert_rb->ref_node, parent, p);
+	rb_insert_color(&insert_rb->ref_node, &ost->ost_refcount_trees);
+}
+
 errcode_t o2fsck_check_refcount_tree(o2fsck_state *ost,
 				     struct ocfs2_dinode *di)
 {
-	errcode_t ret;
+	errcode_t ret = 0;
 	uint64_t c_end = 0;
 	int is_valid = 1;
+	struct refcount_tree *tree;
+	struct refcount_file *file;
 
 	if (!(di->i_dyn_features & OCFS2_HAS_REFCOUNT_FL))
 		return 0;
 
+	tree = refcount_tree_lookup(ost, di->i_refcount_loc);
+	if (tree)
+		goto check_valid;
+
+	ret = ocfs2_malloc0(sizeof(struct refcount_tree), &tree);
+	if (ret)
+		return ret;
+
 	ret = check_rb(ost, di->i_refcount_loc, di->i_refcount_loc,
 		       &c_end, &is_valid);
 
-	if (!is_valid &&
+	/* Add refcount tree to the rb-tree. */
+	tree->rf_blkno = di->i_refcount_loc;
+	tree->is_valid = is_valid;
+	INIT_LIST_HEAD(&tree->files_list);
+	refcount_tree_insert(ost, tree);
+
+check_valid:
+	if (!tree->is_valid &&
 	    prompt(ost, PY, PR_REFCOUNT_ROOT_BLOCK_INVALID,
 		   "Refcount tree %"PRIu64 " for inode %"PRIu64" is invalid. "
 		   "Remove it and clear the flag for the inode?",
@@ -309,6 +383,15 @@ errcode_t o2fsck_check_refcount_tree(o2fsck_state *ost,
 		di->i_dyn_features &= ~OCFS2_HAS_REFCOUNT_FL;
 
 		o2fsck_write_inode(ost, di->i_blkno, di);
+	} else {
+		ret = ocfs2_malloc0(sizeof(struct refcount_file), &file);
+		if (!ret) {
+			file->i_blkno = di->i_blkno;
+			INIT_LIST_HEAD(&file->list);
+
+			list_add_tail(&file->list, &tree->files_list);
+		}
 	}
+
 	return ret;
 }
-- 
1.5.5