commit cb66bfe79239309ace78c06f3548fb402be4e201
Author: Bob Peterson <bob@ganesha.peterson>
Date:   Thu Jan 21 14:01:44 2010 -0600

    fsck.gfs2: convert inode hash to rbtree
    
    This patch converts the inode hash table to an rbtree to speed
    things up.
    
    rhbz#455300

diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index 0e56a2f..44ab03b 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -37,7 +37,7 @@
 
 struct inode_info
 {
-        osi_list_t list;
+        struct osi_node node;
         uint64_t   inode;
         uint16_t   link_count;   /* the number of links the inode
                                   * thinks it has */
@@ -126,7 +126,6 @@ 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 inode_hash[FSCK_HASH_SIZE];
 extern struct gfs2_bmap *bl;
 extern uint64_t last_fs_block, last_reported_block;
 extern int64_t last_reported_fblock;
@@ -136,5 +135,6 @@ extern uint64_t last_data_block;
 extern uint64_t first_data_block;
 extern struct osi_root dup_blocks;
 extern struct osi_root dirtree;
+extern struct osi_root inodetree;
 
 #endif /* _FSCK_H */
diff --git a/gfs2/fsck/initialize.c b/gfs2/fsck/initialize.c
index f9c3251..2687bdb 100644
--- a/gfs2/fsck/initialize.c
+++ b/gfs2/fsck/initialize.c
@@ -30,7 +30,8 @@
 #include "fsck.h"
 #include "util.h"
 #include "fs_recovery.h"
-#include "linux_endian.h"
+#include "metawalk.h"
+#include "inode_hash.h"
 
 #define CLEAR_POINTER(x) \
 	if(x) { \
@@ -94,6 +95,17 @@ static void gfs2_dirtree_free(void)
 	}
 }
 
+static void gfs2_inodetree_free(void)
+{
+	struct osi_node *n;
+	struct inode_info *dt;
+
+	while ((n = osi_first(&inodetree))) {
+		dt = (struct inode_info *)n;
+		inodetree_delete(dt);
+	}
+}
+
 /*
  * empty_super_block - free all structures in the super block
  * sdp: the in-core super block
@@ -105,22 +117,12 @@ static void gfs2_dirtree_free(void)
  */
 static void empty_super_block(struct gfs2_sbd *sdp)
 {
-	uint32_t i;
-
 	log_info( _("Freeing buffers.\n"));
 	gfs2_rgrp_free(&sdp->rglist);
 
-	for(i = 0; i < FSCK_HASH_SIZE; i++) {
-		while(!osi_list_empty(&inode_hash[i])) {
-			struct inode_info *ii;
-			ii = osi_list_entry(inode_hash[i].next, struct inode_info, list);
-			osi_list_del(&ii->list);
-			free(ii);
-		}
-	}
-
 	if (bl)
 		gfs2_bmap_destroy(sdp, bl);
+	gfs2_inodetree_free();
 	gfs2_dirtree_free();
 	gfs2_dup_free();
 }
@@ -428,8 +430,6 @@ static int init_system_inodes(struct gfs2_sbd *sdp)
  */
 static int fill_super_block(struct gfs2_sbd *sdp)
 {
-	uint32_t i;
-
 	sync();
 
 	/********************************************************************
@@ -437,8 +437,6 @@ 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(&inode_hash[i]);
 
 	/********************************************************************
 	 ************  next, read in on-disk SB and set constants  **********
diff --git a/gfs2/fsck/inode_hash.c b/gfs2/fsck/inode_hash.c
index 1c94b32..b23fe08 100644
--- a/gfs2/fsck/inode_hash.c
+++ b/gfs2/fsck/inode_hash.c
@@ -13,78 +13,69 @@
 
 #include <stdint.h>
 #include <unistd.h>
+#include <libintl.h>
 
 #include "libgfs2.h"
 #include "osi_list.h"
 #include "hash.h"
 #include "inode_hash.h"
 #include "fsck.h"
+#define _(String) gettext(String)
 
-static uint32_t gfs2_inode_hash(uint64_t block_no)
+struct inode_info *inodetree_find(uint64_t block)
 {
-	unsigned int h;
+	struct osi_node *node = inodetree.osi_node;
 
-	h = fsck_hash(&block_no, sizeof (uint64_t));
-	h &= FSCK_HASH_MASK;
+	while (node) {
+		struct inode_info *data = (struct inode_info *)node;
 
-	return h;
-}
-
-struct inode_info *inode_hash_search(osi_list_t *buckets, uint64_t key)
-{
-	struct inode_info *ii;
-	osi_list_t *tmp;
-	osi_list_t *bucket = &buckets[gfs2_inode_hash(key)];
-
-	osi_list_foreach(tmp, bucket) {
-		ii = osi_list_entry(tmp, struct inode_info, list);
-		if(ii->inode == key) {
-			return ii;
-		}
+		if (block < data->inode)
+			node = node->osi_left;
+		else if (block > data->inode)
+			node = node->osi_right;
+		else
+			return data;
 	}
 	return NULL;
 }
 
-int inode_hash_insert(osi_list_t *buckets, uint64_t key, struct inode_info *ii)
+struct inode_info *inodetree_insert(uint64_t dblock)
 {
-	osi_list_t *tmp;
-	osi_list_t *bucket = &buckets[gfs2_inode_hash(key)];
-	struct inode_info *itmp = NULL;
+	struct osi_node **newn = &inodetree.osi_node, *parent = NULL;
+	struct inode_info *data;
+
+	/* Figure out where to put new node */
+	while (*newn) {
+		struct inode_info *cur = (struct inode_info *)*newn;
 
-	if(osi_list_empty(bucket)) {
-		osi_list_add(&ii->list, bucket);
-		return 0;
+		parent = *newn;
+		if (dblock < cur->inode)
+			newn = &((*newn)->osi_left);
+		else if (dblock > cur->inode)
+			newn = &((*newn)->osi_right);
+		else
+			return cur;
 	}
 
-	osi_list_foreach(tmp, bucket) {
-		itmp = osi_list_entry(tmp, struct inode_info, list);
-		if(itmp->inode < key) {
-			continue;
-		} else {
-			osi_list_add_prev(&ii->list, tmp);
-			return 0;
-		}
+	data = malloc(sizeof(struct inode_info));
+	if (!data) {
+		log_crit( _("Unable to allocate inode_info structure\n"));
+		return NULL;
 	}
-	osi_list_add_prev(&ii->list, bucket);
-	return 0;
-}
+	if (!memset(data, 0, sizeof(struct inode_info))) {
+		log_crit( _("Error while zeroing inode_info structure\n"));
+		return NULL;
+	}
+	/* Add new node and rebalance tree. */
+	data->inode = dblock;
+	osi_link_node(&data->node, parent, newn);
+	osi_insert_color(&data->node, &inodetree);
 
+	return data;
+}
 
-int inode_hash_remove(osi_list_t *buckets, uint64_t key)
+void inodetree_delete(struct inode_info *b)
 {
-	osi_list_t *tmp;
-	osi_list_t *bucket = &buckets[gfs2_inode_hash(key)];
-	struct inode_info *itmp = NULL;
-
-	if(osi_list_empty(bucket)) {
-		return -1;
-	}
-	osi_list_foreach(tmp, bucket) {
-		itmp = osi_list_entry(tmp, struct inode_info, list);
-		if(itmp->inode == key) {
-			osi_list_del(tmp);
-			return 0;
-		}
-	}
-	return -1;
+	osi_erase(&b->node, &inodetree);
+	free(b);
 }
diff --git a/gfs2/fsck/inode_hash.h b/gfs2/fsck/inode_hash.h
index b2f0f26..3495ddc 100644
--- a/gfs2/fsck/inode_hash.h
+++ b/gfs2/fsck/inode_hash.h
@@ -14,9 +14,10 @@
 #ifndef _INODE_HASH_H
 #define _INODE_HASH_H
 
-struct inode_info *inode_hash_search(osi_list_t *buckets, uint64_t block_no);
-int inode_hash_insert(osi_list_t *buckets, uint64_t key,
-					  struct inode_info *ii);
-int inode_hash_remove(osi_list_t *buckets, uint64_t key);
+struct inode_info;
+
+extern struct inode_info *inodetree_find(uint64_t block);
+extern struct inode_info *inodetree_insert(uint64_t dblock);
+extern void inodetree_delete(struct inode_info *b);
 
 #endif /* _INODE_HASH_H */
diff --git a/gfs2/fsck/link.c b/gfs2/fsck/link.c
index 96dc261..b6870c8 100644
--- a/gfs2/fsck/link.c
+++ b/gfs2/fsck/link.c
@@ -24,37 +24,19 @@
 #include "inode_hash.h"
 #include "link.h"
 
-int set_link_count(struct gfs2_sbd *sbp, uint64_t inode_no, uint32_t count)
+int set_link_count(uint64_t inode_no, uint32_t count)
 {
-	struct inode_info *ii = NULL;
-	log_debug( _("Setting link count to %u for %" PRIu64 " (0x%" PRIx64 ")\n"),
-			  count, inode_no, inode_no);
-	/* If the list has entries, look for one that matches
-	 * inode_no */
-	ii = inode_hash_search(inode_hash, inode_no);
-	if(ii) {
-		if(ii->link_count) {
-			log_err( _("Link count already set for inode #%" PRIu64 " (0x%"
-					PRIx64 ")!\n"), inode_no, inode_no);
-			stack;
-			return -1;
-		}
-		else
-			ii->link_count = count;
-	}
-	else {
-		/* If not match was found, add a new entry and set it's
-		 * link count to count*/
-		if(!(ii = (struct inode_info *) malloc(sizeof(*ii)))) {
-			log_err( _("Unable to allocate inode_info structure\n"));
-			stack;
-			return -1;
-		}
-		memset(ii, 0, sizeof(*ii));
-		ii->inode = inode_no;
+	struct inode_info *ii;
+	/*log_debug( _("Setting link count to %u for %" PRIu64
+	  " (0x%" PRIx64 ")\n"), count, inode_no, inode_no);*/
+	/* If the list has entries, look for one that matches inode_no */
+	ii = inodetree_find(inode_no);
+	if (!ii)
+		ii = inodetree_insert(inode_no);
+	if (ii)
 		ii->link_count = count;
-		inode_hash_insert(inode_hash, inode_no, ii);
-	}
+	else
+		return -1;
 	return 0;
 }
 
@@ -62,7 +44,7 @@ int increment_link(struct gfs2_sbd *sbp, uint64_t inode_no)
 {
 	struct inode_info *ii = NULL;
 
-	ii = inode_hash_search(inode_hash, inode_no);
+	ii = inodetree_find(inode_no);
 	/* If the list has entries, look for one that matches
 	 * inode_no */
 	if(ii) {
@@ -75,20 +57,11 @@ int increment_link(struct gfs2_sbd *sbp, uint64_t inode_no)
 			  " (0x%" PRIx64 ")!\n"), inode_no, inode_no);
 	/* If no match was found, add a new entry and set its
 	 * counted links to 1 */
-	if(!(ii = (struct inode_info *) malloc(sizeof(*ii)))) {
-		log_err( _("Unable to allocate inode_info structure\n"));
-		stack;
-		return -1;
-	}
-	if(!memset(ii, 0, sizeof(*ii))) {
-		log_err( _("Unable to zero inode_info structure\n"));
-		stack;
+	ii = inodetree_insert(inode_no);
+	if (ii)
+		ii->counted_links = 1;
+	else
 		return -1;
-	}
-	ii->inode = inode_no;
-	ii->counted_links = 1;
-	inode_hash_insert(inode_hash, inode_no, ii);
-
 	return 0;
 }
 
@@ -96,7 +69,7 @@ int decrement_link(struct gfs2_sbd *sbp, uint64_t inode_no)
 {
 	struct inode_info *ii = NULL;
 
-	ii = inode_hash_search(inode_hash, inode_no);
+	ii = inodetree_find(inode_no);
 	/* If the list has entries, look for one that matches
 	 * inode_no */
 	log_err( _("Decrementing %"PRIu64" (0x%" PRIx64 ")\n"), inode_no, inode_no);
diff --git a/gfs2/fsck/link.h b/gfs2/fsck/link.h
index 96a3d87..0509255 100644
--- a/gfs2/fsck/link.h
+++ b/gfs2/fsck/link.h
@@ -15,7 +15,7 @@
 #ifndef _LINK_H
 #define _LINK_H
 
-int set_link_count(struct gfs2_sbd *sbp, uint64_t inode_no, uint32_t count);
+int set_link_count(uint64_t inode_no, uint32_t count);
 int increment_link(struct gfs2_sbd *sbp, uint64_t inode_no);
 int decrement_link(struct gfs2_sbd *sbp, uint64_t inode_no);
 
diff --git a/gfs2/fsck/main.c b/gfs2/fsck/main.c
index 52f6204..a4fefb5 100644
--- a/gfs2/fsck/main.c
+++ b/gfs2/fsck/main.c
@@ -31,8 +31,6 @@
 
 struct gfs2_options opts = {0};
 struct gfs2_inode *lf_dip; /* Lost and found directory inode */
-osi_list_t dir_hash[FSCK_HASH_SIZE];
-osi_list_t inode_hash[FSCK_HASH_SIZE];
 struct gfs2_bmap *bl = NULL;
 uint64_t last_fs_block, last_reported_block = -1;
 int64_t last_reported_fblock = -1000000;
@@ -45,6 +43,7 @@ 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, };
+struct osi_root inodetree = (struct osi_root) { NULL, };
 
 /* This function is for libgfs2's sake.                                      */
 void print_it(const char *label, const char *fmt, const char *fmt2, ...)
diff --git a/gfs2/fsck/pass1.c b/gfs2/fsck/pass1.c
index bd0230d..a3029d7 100644
--- a/gfs2/fsck/pass1.c
+++ b/gfs2/fsck/pass1.c
@@ -34,6 +34,7 @@
 
 #include "libgfs2.h"
 #include "fsck.h"
+#include "inode_hash.h"
 #include "util.h"
 #include "link.h"
 #include "linux_endian.h"
@@ -723,7 +724,7 @@ static int handle_di(struct gfs2_sbd *sdp, struct gfs2_buffer_head *bh,
 		fsck_inode_put(&ip);
 		return 0;
 	}
-	if(set_link_count(ip->i_sbd, ip->i_di.di_num.no_addr, ip->i_di.di_nlink)) {
+	if(set_link_count(ip->i_di.di_num.no_addr, ip->i_di.di_nlink)) {
 		stack;
 		fsck_inode_put(&ip);
 		return -1;
diff --git a/gfs2/fsck/pass1b.c b/gfs2/fsck/pass1b.c
index d035e4f..7d10917 100644
--- a/gfs2/fsck/pass1b.c
+++ b/gfs2/fsck/pass1b.c
@@ -178,7 +178,6 @@ static int clear_dup_metalist(struct gfs2_inode *ip, uint64_t block,
 		log_err( _("Inode %s is in directory %"PRIu64" (0x%" PRIx64 ")\n"),
 			 dh->id->name ? dh->id->name : "", dh->id->parent,
 			 dh->id->parent);
-		inode_hash_remove(inode_hash, ip->i_di.di_num.no_addr);
 		/* Setting the block to invalid means the inode is
 		 * cleared in pass2 */
 		gfs2_blockmap_set(ip->i_sbd, bl, ip->i_di.di_num.no_addr,
@@ -423,12 +422,15 @@ static int handle_dup_blk(struct gfs2_sbd *sbp, struct duptree *b)
 				  (unsigned long long)b->block,
 				  (unsigned long long)b->block);
 			if (query( _("Clear the inode? (y/n) "))) {
+				struct inode_info *ii;
+
 				log_warn( _("Clearing inode %lld (0x%llx)...\n"),
 					 (unsigned long long)id->block_no,
 					 (unsigned long long)id->block_no);
 				ip = fsck_load_inode(sbp, id->block_no);
-				inode_hash_remove(inode_hash,
-						  ip->i_di.di_num.no_addr);
+				ii = inodetree_find(ip->i_di.di_num.no_addr);
+				if (ii)
+					inodetree_delete(ii);
 				/* Setting the block to invalid means the inode
 				   is cleared in pass2 */
 				gfs2_blockmap_set(ip->i_sbd, bl,
diff --git a/gfs2/fsck/pass4.c b/gfs2/fsck/pass4.c
index eb4f413..eff47aa 100644
--- a/gfs2/fsck/pass4.c
+++ b/gfs2/fsck/pass4.c
@@ -34,8 +34,7 @@ struct metawalk_fxns pass4_fxns_delete = {
 
 /* Updates the link count of an inode to what the fsck has seen for
  * link count */
-static int fix_inode_count(struct gfs2_sbd *sbp, struct inode_info *ii,
-					struct gfs2_inode *ip)
+static int fix_link_count(struct inode_info *ii, struct gfs2_inode *ip)
 {
 	log_info( _("Fixing inode link count (%d->%d) for %llu (0x%llx) \n"),
 		  ip->i_di.di_nlink, ii->counted_links,
@@ -53,8 +52,8 @@ static int fix_inode_count(struct gfs2_sbd *sbp, struct inode_info *ii,
 	return 0;
 }
 
-static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
-	osi_list_t *tmp;
+static int scan_inode_list(struct gfs2_sbd *sbp) {
+	struct osi_node *tmp;
 	struct inode_info *ii;
 	struct gfs2_inode *ip;
 	int lf_addition = 0;
@@ -62,11 +61,11 @@ static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
 
 	/* FIXME: should probably factor this out into a generic
 	 * scanning fxn */
-	osi_list_foreach(tmp, list) {
+	for (tmp = osi_first(&inodetree); tmp; tmp = osi_next(tmp)) {
 		if (skip_this_pass || fsck_abort) /* if asked to skip the rest */
 			return 0;
-		if(!(ii = osi_list_entry(tmp, struct inode_info, list))) {
-			log_crit( _("osi_list_foreach broken in scan_info_list!!\n"));
+		if(!(ii = (struct inode_info *)tmp)) {
+			log_crit( _("osi_tree broken in scan_info_list!!\n"));
 			exit(FSCK_ERROR);
 		}
 		if(ii->counted_links == 0) {
@@ -142,7 +141,7 @@ static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
 					fsck_inode_put(&ip);
 					return -1;
 				} else {
-					fix_inode_count(sbp, ii, ip);
+					fix_link_count(ii, ip);
 					lf_addition = 1;
 				}
 			} else
@@ -159,8 +158,8 @@ static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
 				    " (0x%" PRIx64 ") ? (y/n) "),
 				  ii->inode, ii->inode)) {
 				ip = fsck_load_inode(sbp, ii->inode); /* bread, inode_get */
-				fix_inode_count(sbp, ii, ip);
-				bmodified(ip->i_bh);
+				fix_link_count(ii, ip);
+				ii->link_count = ii->counted_links;
 				fsck_inode_put(&ip); /* out, brelse, free */
 				log_warn( _("Link count updated to %d for "
 					    "inode %" PRIu64 " (0x%"
@@ -176,12 +175,11 @@ static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
 	} /* osi_list_foreach(tmp, list) */
 
 	if (lf_addition) {
-		if(!(ii = inode_hash_search(inode_hash,
-									lf_dip->i_di.di_num.no_addr))) {
+		if(!(ii = inodetree_find(lf_dip->i_di.di_num.no_addr))) {
 			log_crit( _("Unable to find lost+found inode in inode_hash!!\n"));
 			return -1;
 		} else {
-			fix_inode_count(sbp, ii, lf_dip);
+			fix_link_count(ii, lf_dip);
 		}
 	}
 
@@ -199,20 +197,13 @@ static int scan_inode_list(struct gfs2_sbd *sbp, osi_list_t *list) {
  */
 int pass4(struct gfs2_sbd *sbp)
 {
-	uint32_t i;
-	osi_list_t *list;
 	if(lf_dip)
 		log_debug( _("At beginning of pass4, lost+found entries is %u\n"),
 				  lf_dip->i_di.di_entries);
 	log_info( _("Checking inode reference counts.\n"));
-	for (i = 0; i < FSCK_HASH_SIZE; i++) {
-		if (skip_this_pass || fsck_abort) /* if asked to skip the rest */
-			return FSCK_OK;
-		list = &inode_hash[i];
-		if(scan_inode_list(sbp, list)) {
-			stack;
-			return FSCK_ERROR;
-		}
+	if(scan_inode_list(sbp)) {
+		stack;
+		return FSCK_ERROR;
 	}
 
 	if(lf_dip)