Gitweb:
http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=...
Commit: 4182a036b732bfadad49f4b886b935c7ef431000
Parent: 35c2c9b2a295ae79231107d4861caae97cb31053
Author: Bob Peterson <bob(a)ganesha.peterson>
AuthorDate: Thu Jan 21 13:12:15 2010 -0600
Committer: Bob Peterson <rpeterso(a)redhat.com>
CommitterDate: Tue Jan 26 14:39:29 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
---
gfs2/fsck/fsck.h | 6 ++--
gfs2/fsck/initialize.c | 22 ++++++++------
gfs2/fsck/main.c | 7 ++--
gfs2/fsck/metawalk.c | 73 ------------------------------------------------
gfs2/fsck/metawalk.h | 5 ---
gfs2/fsck/pass1.c | 32 +--------------------
gfs2/fsck/pass2.c | 10 ++++--
gfs2/fsck/pass3.c | 19 +++++-------
gfs2/fsck/util.c | 58 ++++++++++++++++++++++++++++++++++++++
9 files changed, 92 insertions(+), 140 deletions(-)
diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index d04168b..3d52b00 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -34,7 +34,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;
@@ -110,11 +110,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;
@@ -124,5 +123,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 81194c5..971decd 100644
--- a/gfs2/fsck/initialize.c
+++ b/gfs2/fsck/initialize.c
@@ -66,6 +66,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
@@ -89,16 +100,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();
}
@@ -415,10 +421,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 b75f012..f9c5fa3 100644
--- a/gfs2/fsck/main.c
+++ b/gfs2/fsck/main.c
@@ -31,6 +31,7 @@ uint64_t last_data_block;
uint64_t first_data_block;
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, ...)
@@ -174,8 +175,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
@@ -193,8 +193,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 dad6d34..d5a29b7 100644
--- a/gfs2/fsck/metawalk.c
+++ b/gfs2/fsck/metawalk.c
@@ -1113,79 +1113,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 dbbe4c3..9710b01 100644
--- a/gfs2/fsck/metawalk.h
+++ b/gfs2/fsck/metawalk.h
@@ -15,11 +15,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 6862f29..2cd8bdc 100644
--- a/gfs2/fsck/pass1.c
+++ b/gfs2/fsck/pass1.c
@@ -587,36 +587,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)
{
@@ -667,7 +637,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 90f6572..a368124 100644
--- a/gfs2/fsck/pass2.c
+++ b/gfs2/fsck/pass2.c
@@ -23,7 +23,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
@@ -50,7 +51,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 */
@@ -722,8 +724,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 c1986f3..fd34de2 100644
--- a/gfs2/fsck/pass3.c
+++ b/gfs2/fsck/pass3.c
@@ -150,7 +150,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;
}
@@ -163,19 +163,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;
}
@@ -185,9 +184,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
@@ -264,7 +262,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 8a89d01..9f2aae0 100644
--- a/gfs2/fsck/util.c
+++ b/gfs2/fsck/util.c
@@ -181,6 +181,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;
@@ -197,3 +249,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);
+}