commit 221038f9a959a0ac4f457afec470e7d3135b090a
Author: Bob Peterson <bob@ganesha.peterson>
Date:   Thu Jan 21 13:12:15 2010 -0600

    fsck.gfs2: convert dir_info list to rbtree
    
    This patch replaces the linked list of directories with another
    rbtree to speedy things up.
    
    rhbz#455300

diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index fadb73e..0e56a2f 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -46,7 +46,7 @@ struct inode_info
 
 struct dir_info
 {
-        osi_list_t list;
+        struct osi_node node;
         uint64_t dinode;
         uint64_t treewalk_parent;
         uint64_t dotdot_parent;
@@ -122,11 +122,10 @@ extern void dirtree_delete(struct dir_info *b);
 
 /* FIXME: Hack to get this going for pass2 - this should be pulled out
  * of pass1 and put somewhere else... */
-int add_to_dir_list(struct gfs2_sbd *sbp, uint64_t block);
+struct dir_info *dirtree_insert(uint64_t dblock);
 
 extern struct gfs2_options opts;
 extern struct gfs2_inode *lf_dip; /* Lost and found directory inode */
-extern osi_list_t dir_hash[FSCK_HASH_SIZE];
 extern osi_list_t inode_hash[FSCK_HASH_SIZE];
 extern struct gfs2_bmap *bl;
 extern uint64_t last_fs_block, last_reported_block;
@@ -136,5 +135,6 @@ extern int errors_found, errors_corrected;
 extern uint64_t last_data_block;
 extern uint64_t first_data_block;
 extern struct osi_root dup_blocks;
+extern struct osi_root dirtree;
 
 #endif /* _FSCK_H */
diff --git a/gfs2/fsck/initialize.c b/gfs2/fsck/initialize.c
index 48859eb..f9c3251 100644
--- a/gfs2/fsck/initialize.c
+++ b/gfs2/fsck/initialize.c
@@ -83,6 +83,17 @@ void gfs2_dup_free(void)
 	}
 }
 
+static void gfs2_dirtree_free(void)
+{
+	struct osi_node *n;
+	struct dir_info *dt;
+
+	while ((n = osi_first(&dirtree))) {
+		dt = (struct dir_info *)n;
+		dirtree_delete(dt);
+	}
+}
+
 /*
  * empty_super_block - free all structures in the super block
  * sdp: the in-core super block
@@ -106,16 +117,11 @@ static void empty_super_block(struct gfs2_sbd *sdp)
 			osi_list_del(&ii->list);
 			free(ii);
 		}
-		while(!osi_list_empty(&dir_hash[i])) {
-			struct dir_info *di;
-			di = osi_list_entry(dir_hash[i].next, struct dir_info, list);
-			osi_list_del(&di->list);
-			free(di);
-		}
 	}
 
 	if (bl)
 		gfs2_bmap_destroy(sdp, bl);
+	gfs2_dirtree_free();
 	gfs2_dup_free();
 }
 
@@ -431,10 +437,8 @@ static int fill_super_block(struct gfs2_sbd *sdp)
 	 ********************************************************************/
 	log_info( _("Initializing lists...\n"));
 	osi_list_init(&sdp->rglist);
-	for(i = 0; i < FSCK_HASH_SIZE; i++) {
-		osi_list_init(&dir_hash[i]);
+	for(i = 0; i < FSCK_HASH_SIZE; i++)
 		osi_list_init(&inode_hash[i]);
-	}
 
 	/********************************************************************
 	 ************  next, read in on-disk SB and set constants  **********
diff --git a/gfs2/fsck/main.c b/gfs2/fsck/main.c
index 24f9500..52f6204 100644
--- a/gfs2/fsck/main.c
+++ b/gfs2/fsck/main.c
@@ -44,6 +44,7 @@ uint64_t first_data_block;
 const char *prog_name = "gfs2_fsck"; /* needed by libgfs2 */
 int preen = 0, force_check = 0;
 struct osi_root dup_blocks = (struct osi_root) { NULL, };
+struct osi_root dirtree = (struct osi_root) { NULL, };
 
 /* This function is for libgfs2's sake.                                      */
 void print_it(const char *label, const char *fmt, const char *fmt2, ...)
@@ -187,8 +188,7 @@ static int check_system_inode(struct gfs2_inode *sysinode, const char *filename,
 				       mark);
 			ds.q = mark;
 			if (mark == gfs2_inode_dir)
-				add_to_dir_list(sysinode->i_sbd,
-						sysinode->i_di.di_num.no_addr);
+				dirtree_insert(sysinode->i_di.di_num.no_addr);
 		}
 	}
 	else
@@ -206,8 +206,7 @@ static int check_system_inode(struct gfs2_inode *sysinode, const char *filename,
 				       mark);
 			ds.q = mark;
 			if (mark == gfs2_inode_dir)
-				add_to_dir_list(sysinode->i_sbd,
-						sysinode->i_di.di_num.no_addr);
+				dirtree_insert(sysinode->i_di.di_num.no_addr);
 		}
 		else {
 			log_err( _("Cannot continue without valid %s inode\n"),
diff --git a/gfs2/fsck/metawalk.c b/gfs2/fsck/metawalk.c
index dae71ab..86da8a2 100644
--- a/gfs2/fsck/metawalk.c
+++ b/gfs2/fsck/metawalk.c
@@ -1125,79 +1125,6 @@ int remove_dentry_from_dir(struct gfs2_sbd *sbp, uint64_t dir,
 	return error;
 }
 
-/* FIXME: These should be merged with the hash routines in inode_hash.c */
-static uint32_t dinode_hash(uint64_t block_no)
-{
-	unsigned int h;
-
-	h = fsck_hash(&block_no, sizeof (uint64_t));
-	h &= FSCK_HASH_MASK;
-
-	return h;
-}
-
-int find_di(struct gfs2_sbd *sbp, uint64_t childblock, struct dir_info **dip)
-{
-	osi_list_t *bucket = &dir_hash[dinode_hash(childblock)];
-	osi_list_t *tmp;
-	struct dir_info *di = NULL;
-
-	osi_list_foreach(tmp, bucket) {
-		di = osi_list_entry(tmp, struct dir_info, list);
-		if(di->dinode == childblock) {
-			*dip = di;
-			return 0;
-		}
-	}
-	*dip = NULL;
-	return -1;
-
-}
-
-int dinode_hash_insert(osi_list_t *buckets, uint64_t key, struct dir_info *di)
-{
-	osi_list_t *tmp;
-	osi_list_t *bucket = &buckets[dinode_hash(key)];
-	struct dir_info *dtmp = NULL;
-
-	if(osi_list_empty(bucket)) {
-		osi_list_add(&di->list, bucket);
-		return 0;
-	}
-
-	osi_list_foreach(tmp, bucket) {
-		dtmp = osi_list_entry(tmp, struct dir_info, list);
-		if(dtmp->dinode < key) {
-			continue;
-		}
-		else {
-			osi_list_add_prev(&di->list, tmp);
-			return 0;
-		}
-	}
-	osi_list_add_prev(&di->list, bucket);
-	return 0;
-}
-
-int dinode_hash_remove(osi_list_t *buckets, uint64_t key)
-{
-	osi_list_t *tmp;
-	osi_list_t *bucket = &buckets[dinode_hash(key)];
-	struct dir_info *dtmp = NULL;
-
-	if(osi_list_empty(bucket)) {
-		return -1;
-	}
-	osi_list_foreach(tmp, bucket) {
-		dtmp = osi_list_entry(tmp, struct dir_info, list);
-		if(dtmp->dinode == key) {
-			osi_list_del(tmp);
-			return 0;
-		}
-	}
-	return -1;
-}
-
 /**
  * delete_blocks - delete blocks associated with an inode
  */
diff --git a/gfs2/fsck/metawalk.h b/gfs2/fsck/metawalk.h
index 497a1bf..08fc9e1 100644
--- a/gfs2/fsck/metawalk.h
+++ b/gfs2/fsck/metawalk.h
@@ -27,11 +27,6 @@ extern int check_linear_dir(struct gfs2_inode *ip, struct gfs2_buffer_head *bh,
 			    struct metawalk_fxns *pass);
 extern int remove_dentry_from_dir(struct gfs2_sbd *sbp, uint64_t dir,
 				  uint64_t dentryblock);
-extern int find_di(struct gfs2_sbd *sbp, uint64_t childblock,
-		   struct dir_info **dip);
-extern int dinode_hash_insert(osi_list_t *buckets, uint64_t key,
-			      struct dir_info *di);
-extern int dinode_hash_remove(osi_list_t *buckets, uint64_t key);
 extern int delete_blocks(struct gfs2_inode *ip, uint64_t block,
 			 struct gfs2_buffer_head **bh, const char *btype,
 			 void *private);
diff --git a/gfs2/fsck/pass1.c b/gfs2/fsck/pass1.c
index 961a59c..bd0230d 100644
--- a/gfs2/fsck/pass1.c
+++ b/gfs2/fsck/pass1.c
@@ -601,36 +601,6 @@ static int clear_leaf(struct gfs2_inode *ip, uint64_t block,
 	return 0;
 }
 
-int add_to_dir_list(struct gfs2_sbd *sbp, uint64_t block)
-{
-	struct dir_info *di = NULL;
-	struct dir_info *newdi;
-
-	/* FIXME: This list should probably be a b-tree or
-	 * something...but since most of the time we're going to be
-	 * tacking the directory onto the end of the list, it doesn't
-	 * matter too much */
-	find_di(sbp, block, &di);
-	if(di) {
-		log_err( _("Attempting to add directory block #%" PRIu64
-				" (0x%" PRIx64 ") which is already in list\n"), block, block);
-		return -1;
-	}
-
-	if(!(newdi = (struct dir_info *) malloc(sizeof(struct dir_info)))) {
-		log_crit( _("Unable to allocate dir_info structure\n"));
-		return -1;
-	}
-	if(!memset(newdi, 0, sizeof(*newdi))) {
-		log_crit( _("Error while zeroing dir_info structure\n"));
-		return -1;
-	}
-
-	newdi->dinode = block;
-	dinode_hash_insert(dir_hash, block, newdi);
-	return 0;
-}
-
 static int handle_di(struct gfs2_sbd *sdp, struct gfs2_buffer_head *bh,
 			  uint64_t block)
 {
@@ -681,7 +651,7 @@ static int handle_di(struct gfs2_sbd *sdp, struct gfs2_buffer_head *bh,
 			fsck_inode_put(&ip);
 			return -1;
 		}
-		if(add_to_dir_list(sdp, block)) {
+		if(!dirtree_insert(block)) {
 			stack;
 			fsck_inode_put(&ip);
 			return -1;
diff --git a/gfs2/fsck/pass2.c b/gfs2/fsck/pass2.c
index 55a5be3..7586071 100644
--- a/gfs2/fsck/pass2.c
+++ b/gfs2/fsck/pass2.c
@@ -36,7 +36,8 @@ static int set_parent_dir(struct gfs2_sbd *sbp, uint64_t childblock,
 {
 	struct dir_info *di;
 
-	if(!find_di(sbp, childblock, &di)) {
+	di = dirtree_find(childblock);
+	if (di) {
 		if(di->dinode == childblock) {
 			if (di->treewalk_parent) {
 				log_err( _("Another directory at block %" PRIu64
@@ -63,7 +64,8 @@ static int set_dotdot_dir(struct gfs2_sbd *sbp, uint64_t childblock,
 {
 	struct dir_info *di;
 
-	if(!find_di(sbp, childblock, &di)) {
+	di = dirtree_find(childblock);
+	if(di) {
 		if(di->dinode == childblock) {
 			/* Special case for root inode because we set
 			 * it earlier */
@@ -735,8 +737,8 @@ int pass2(struct gfs2_sbd *sbp)
 		if (error > 0) {
 			struct dir_info *di = NULL;
 
-			error = find_di(sbp, dirblk, &di);
-			if(error < 0) {
+			di = dirtree_find(dirblk);
+			if(!di) {
 				stack;
 				return FSCK_ERROR;
 			}
diff --git a/gfs2/fsck/pass3.c b/gfs2/fsck/pass3.c
index 5ccccc8..bfef9bb 100644
--- a/gfs2/fsck/pass3.c
+++ b/gfs2/fsck/pass3.c
@@ -163,7 +163,7 @@ static struct dir_info *mark_and_return_parent(struct gfs2_sbd *sbp,
 			return NULL;
 		}
 	}
-	find_di(sbp, di->dotdot_parent, &pdi);
+	pdi = dirtree_find(di->dotdot_parent);
 
 	return pdi;
 }
@@ -176,19 +176,18 @@ static struct dir_info *mark_and_return_parent(struct gfs2_sbd *sbp,
  */
 int pass3(struct gfs2_sbd *sbp)
 {
-	osi_list_t *tmp;
+	struct osi_node *tmp;
 	struct dir_info *di, *tdi;
 	struct gfs2_inode *ip;
 	uint8_t q;
-	int i;
 
-	find_di(sbp, sbp->md.rooti->i_di.di_num.no_addr, &di);
-	if(di) {
+	di = dirtree_find(sbp->md.rooti->i_di.di_num.no_addr);
+	if (di) {
 		log_info( _("Marking root inode connected\n"));
 		di->checked = 1;
 	}
-	find_di(sbp, sbp->master_dir->i_di.di_num.no_addr, &di);
-	if(di) {
+	di = dirtree_find(sbp->master_dir->i_di.di_num.no_addr);
+	if (di) {
 		log_info( _("Marking master directory inode connected\n"));
 		di->checked = 1;
 	}
@@ -198,9 +197,8 @@ int pass3(struct gfs2_sbd *sbp)
 	 * find a parent, put in lost+found.
 	 */
 	log_info( _("Checking directory linkage.\n"));
-	for(i = 0; i < FSCK_HASH_SIZE; i++) {
-	osi_list_foreach(tmp, &dir_hash[i]) {
-		di = osi_list_entry(tmp, struct dir_info, list);
+	for (tmp = osi_first(&dirtree); tmp; tmp = osi_next(tmp)) {
+		di = (struct dir_info *)tmp;
 		while(!di->checked) {
 			/* FIXME: Change this so it returns success or
 			 * failure and put the parent inode in a
@@ -277,7 +275,6 @@ int pass3(struct gfs2_sbd *sbp)
 			di = tdi;
 		}
 	}
-	}
 	if(lf_dip)
 		log_debug( _("At end of pass3, lost+found entries is %u\n"),
 				  lf_dip->i_di.di_entries);
diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c
index 6af2b41..a37a286 100644
--- a/gfs2/fsck/util.c
+++ b/gfs2/fsck/util.c
@@ -227,6 +227,58 @@ struct duptree *gfs2_dup_set(uint64_t dblock)
 	return data;
 }
 
+struct dir_info *dirtree_insert(uint64_t dblock)
+{
+	struct osi_node **newn = &dirtree.osi_node, *parent = NULL;
+	struct dir_info *data;
+
+	/* Figure out where to put new node */
+	while (*newn) {
+		struct dir_info *cur = (struct dir_info *)*newn;
+
+		parent = *newn;
+		if (dblock < cur->dinode)
+			newn = &((*newn)->osi_left);
+		else if (dblock > cur->dinode)
+			newn = &((*newn)->osi_right);
+		else
+			return cur;
+	}
+
+	data = malloc(sizeof(struct dir_info));
+	if (!data) {
+		log_crit( _("Unable to allocate dir_info structure\n"));
+		return NULL;
+	}
+	if (!memset(data, 0, sizeof(struct dir_info))) {
+		log_crit( _("Error while zeroing dir_info structure\n"));
+		return NULL;
+	}
+	/* Add new node and rebalance tree. */
+	data->dinode = dblock;
+	osi_link_node(&data->node, parent, newn);
+	osi_insert_color(&data->node, &dirtree);
+
+	return data;
+}
+
+struct dir_info *dirtree_find(uint64_t block)
+{
+	struct osi_node *node = dirtree.osi_node;
+
+	while (node) {
+		struct dir_info *data = (struct dir_info *)node;
+
+		if (block < data->dinode)
+			node = node->osi_left;
+		else if (block > data->dinode)
+			node = node->osi_right;
+		else
+			return data;
+	}
+	return NULL;
+}
+
 void dup_delete(struct duptree *b)
 {
 	struct inode_with_dups *id;
@@ -243,3 +295,9 @@ void dup_delete(struct duptree *b)
 	osi_erase(&b->node, &dup_blocks);
 	free(b);
 }
+
+void dirtree_delete(struct dir_info *b)
+{
+	osi_erase(&b->node, &dirtree);
+	free(b);
+}