Gitweb: http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=cb6... Commit: cb66bfe79239309ace78c06f3548fb402be4e201 Parent: 221038f9a959a0ac4f457afec470e7d3135b090a Author: Bob Peterson bob@ganesha.peterson AuthorDate: Thu Jan 21 14:01:44 2010 -0600 Committer: Bob Peterson rpeterso@redhat.com CommitterDate: Fri Apr 9 23:33:16 2010 -0500
fsck.gfs2: convert inode hash to rbtree
This patch converts the inode hash table to an rbtree to speed things up.
rhbz#455300 --- gfs2/fsck/fsck.h | 4 +- gfs2/fsck/initialize.c | 30 +++++++-------- gfs2/fsck/inode_hash.c | 95 ++++++++++++++++++++++-------------------------- gfs2/fsck/inode_hash.h | 9 +++-- gfs2/fsck/link.c | 61 +++++++++---------------------- gfs2/fsck/link.h | 2 +- gfs2/fsck/main.c | 3 +- gfs2/fsck/pass1.c | 3 +- gfs2/fsck/pass1b.c | 8 +++-- gfs2/fsck/pass4.c | 37 +++++++------------ 10 files changed, 104 insertions(+), 148 deletions(-)
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)