Gitweb: http://git.fedorahosted.org/git/?p=cluster.git;a=commitdiff;h=a472edcae35302... Commit: a472edcae35302d0abc4bf9ca0e5183b27ca715d Parent: 737668db7dec805e3bcddd32c1e03b7ddf2eecb2 Author: Bob Peterson rpeterso@redhat.com AuthorDate: Fri Jan 6 16:02:26 2012 -0600 Committer: Bob Peterson rpeterso@redhat.com CommitterDate: Fri Apr 5 06:25:01 2013 -0700
libgfs2: Make in-core rgrps use rbtree
This patch changes the in-core structure used for resource groups from a linked list to an rbtree.
rhbz#877150 --- gfs2/convert/gfs2_convert.c | 61 +++++++------ gfs2/edit/extended.c | 2 +- gfs2/edit/hexedit.c | 56 ++++++------ gfs2/edit/hexedit.h | 4 +- gfs2/edit/savemeta.c | 27 ++++--- gfs2/fsck/fs_recovery.c | 1 + gfs2/fsck/initialize.c | 32 ++++---- gfs2/fsck/main.c | 9 +- gfs2/fsck/metawalk.c | 2 +- gfs2/fsck/pass1.c | 14 ++-- gfs2/fsck/pass5.c | 11 ++- gfs2/fsck/rgrepair.c | 205 +++++++++++++++++++++++++------------------ gfs2/fsck/util.c | 1 - gfs2/libgfs2/fs_bits.c | 4 +- gfs2/libgfs2/fs_geometry.c | 52 ++++++----- gfs2/libgfs2/fs_ops.c | 16 ++-- gfs2/libgfs2/gfs1.c | 31 +++---- gfs2/libgfs2/libgfs2.h | 45 +++++---- gfs2/libgfs2/rgrp.c | 78 ++++++++++------ gfs2/libgfs2/structures.c | 22 +++--- gfs2/libgfs2/super.c | 29 +++---- gfs2/mkfs/main_grow.c | 55 ++++++------ gfs2/mkfs/main_mkfs.c | 6 +- gfs2/tool/df.c | 2 +- 24 files changed, 417 insertions(+), 348 deletions(-)
diff --git a/gfs2/convert/gfs2_convert.c b/gfs2/convert/gfs2_convert.c index d887838..2300e63 100644 --- a/gfs2/convert/gfs2_convert.c +++ b/gfs2/convert/gfs2_convert.c @@ -178,7 +178,7 @@ void print_it(const char *label, const char *fmt, const char *fmt2, ...) /* Fixes all unallocated metadata bitmap states (which are */ /* valid in gfs1 but invalid in gfs2). */ /* ------------------------------------------------------------------------- */ -static void convert_bitmaps(struct gfs2_sbd *sdp, struct rgrp_list *rg) +static void convert_bitmaps(struct gfs2_sbd *sdp, struct rgrp_tree *rg) { uint32_t blk; int x, y; @@ -206,16 +206,18 @@ static void convert_bitmaps(struct gfs2_sbd *sdp, struct rgrp_list *rg) /* ------------------------------------------------------------------------- */ static int convert_rgs(struct gfs2_sbd *sbp) { - struct rgrp_list *rgd; - osi_list_t *tmp; + struct rgrp_tree *rgd; + struct osi_node *n, *next = NULL; struct gfs1_rgrp *rgd1; int rgs = 0;
/* --------------------------------- */ /* Now convert its rgs into gfs2 rgs */ /* --------------------------------- */ - osi_list_foreach(tmp, &sbp->rglist) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sbp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; + rgd1 = (struct gfs1_rgrp *)&rgd->rg; /* recast as gfs1 structure */ /* rg_freemeta is a gfs1 structure, so libgfs2 doesn't know to */ /* convert from be to cpu. We must do it now. */ @@ -990,8 +992,8 @@ static int adjust_inode(struct gfs2_sbd *sbp, struct gfs2_buffer_head *bh) /* ------------------------------------------------------------------------- */ static int inode_renumber(struct gfs2_sbd *sbp, uint64_t root_inode_addr, osi_list_t *cdpn_to_fix) { - struct rgrp_list *rgd; - osi_list_t *tmp; + struct rgrp_tree *rgd; + struct osi_node *n, *next = NULL; uint64_t block; struct gfs2_buffer_head *bh; int first; @@ -1006,9 +1008,10 @@ static int inode_renumber(struct gfs2_sbd *sbp, uint64_t root_inode_addr, osi_li /* ---------------------------------------------------------------- */ /* Traverse the resource groups to figure out where the inodes are. */ /* ---------------------------------------------------------------- */ - osi_list_foreach(tmp, &sbp->rglist) { + for (n = osi_first(&sbp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; rgs_processed++; - rgd = osi_list_entry(tmp, struct rgrp_list, list); first = 1; while (1) { /* for all inodes in the resource group */ gettimeofday(&tv, NULL); @@ -1510,7 +1513,7 @@ static int init(struct gfs2_sbd *sbp) sbp->dinodes_alloced = 0; /* dinodes allocated - total them up later */ sbp->sd_sb.sb_bsize = GFS2_DEFAULT_BSIZE; sbp->bsize = sbp->sd_sb.sb_bsize; - osi_list_init(&sbp->rglist); + sbp->rgtree.osi_node = NULL; compute_constants(sbp);
bh = bread(sbp, GFS2_SB_ADDR >> sbp->sd_fsb2bb_shift); @@ -1726,9 +1729,10 @@ static int journ_space_to_rg(struct gfs2_sbd *sdp) int error = 0; int j, x; struct gfs1_jindex *jndx; - struct rgrp_list *rgd, *rgdhigh; - osi_list_t *tmp; + struct rgrp_tree *rgd, *rgdhigh; + struct osi_node *n, *next = NULL; struct gfs2_meta_header mh; + uint64_t ri_addr;
mh.mh_magic = GFS2_MAGIC; mh.mh_type = GFS2_METATYPE_RB; @@ -1746,8 +1750,9 @@ static int journ_space_to_rg(struct gfs2_sbd *sdp) by jadd. gfs_grow adds rgs out of order, so we can't count on them being in ascending order. */ rgdhigh = NULL; - osi_list_foreach(tmp, &sdp->rglist) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; if (rgd->ri.ri_addr < jndx->ji_addr && ((rgdhigh == NULL) || (rgd->ri.ri_addr > rgdhigh->ri.ri_addr))) @@ -1759,15 +1764,12 @@ static int journ_space_to_rg(struct gfs2_sbd *sdp) log_crit("Error: No suitable rg found for journal.\n"); return -1; } + ri_addr = jndx->ji_addr; /* Allocate a new rgd entry which includes rg and ri. */ + rgd = rgrp_insert(&sdp->rgtree, ri_addr); /* convert the gfs1 rgrp into a new gfs2 rgrp */ - rgd = malloc(sizeof(struct rgrp_list)); - if (!rgd) { - log_crit("Error: unable to allocate memory for rg conversion.\n"); - return -1; - } - memset(rgd, 0, sizeof(struct rgrp_list)); - size = jndx->ji_nsegment * be32_to_cpu(raw_gfs1_ondisk_sb.sb_seg_size); + size = jndx->ji_nsegment * + be32_to_cpu(raw_gfs1_ondisk_sb.sb_seg_size); rgd->rg.rg_header.mh_magic = GFS2_MAGIC; rgd->rg.rg_header.mh_type = GFS2_METATYPE_RG; rgd->rg.rg_header.mh_format = GFS2_FORMAT_RG; @@ -1810,9 +1812,6 @@ static int journ_space_to_rg(struct gfs2_sbd *sdp) else gfs2_rgrp_out(&rgd->rg, rgd->bh[x]); } - /* Add the new gfs2 rg to our list: We'll output the rg index later. */ - osi_list_add_prev((osi_list_t *)&rgd->list, - (osi_list_t *)&sdp->rglist); } /* for each journal */ return error; }/* journ_space_to_rg */ @@ -1988,16 +1987,17 @@ static int check_fit(struct gfs2_sbd *sdp)
/* build_rindex() */ { - osi_list_t *tmp, *head; + struct osi_node *n, *next = NULL; unsigned int rg_count = 0;
blks_need++; /* creationg of 'rindex' disk inode */ /* find the total # of rindex entries, gives size of rindex inode */ - for (head = &sdp->rglist, tmp = head->next; tmp != head; - tmp = tmp->next) + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); rg_count++; - blks_need += - total_file_blocks(sdp, rg_count * sizeof(struct gfs2_rindex), 1); + } + blks_need += total_file_blocks(sdp, rg_count * + sizeof(struct gfs2_rindex), 1); } /* build_quota() */ blks_need++; /* quota inode block and uid=gid=0 quota - total 1 block */ @@ -2132,6 +2132,7 @@ int main(int argc, char **argv) /* ---------------------------------------------- */ if (!error) { int jreduce = 0; + /* Now we've got to treat it as a gfs2 file system */ compute_constants(&sb2);
@@ -2187,7 +2188,7 @@ int main(int argc, char **argv) fsync(sb2.device_fd); /* write the buffers to disk */
/* Now free all the in memory */ - gfs2_rgrp_free(&sb2.rglist); + gfs2_rgrp_free(&sb2.rgtree); log_notice("Committing changes to disk.\n"); fflush(stdout); /* Set filesystem type in superblock to gfs2. We do this at the */ diff --git a/gfs2/edit/extended.c b/gfs2/edit/extended.c index 3c45060..b615b19 100644 --- a/gfs2/edit/extended.c +++ b/gfs2/edit/extended.c @@ -662,7 +662,7 @@ int display_extended(void) return -1; else if (display_indirect(indirect, indirect_blocks, 0, 0) == 0) return -1; - else if (block_is_rglist()) { + else if (block_is_rgtree()) { if (gfs1) tmp_bh = bread(&sbd, sbd1->sb_rindex_di.no_addr); else diff --git a/gfs2/edit/hexedit.c b/gfs2/edit/hexedit.c index 3cc05f4..d3b1f24 100644 --- a/gfs2/edit/hexedit.c +++ b/gfs2/edit/hexedit.c @@ -1166,7 +1166,7 @@ int display_block_type(int from_restore) return ret_type; if (termlines && dmode == HEX_MODE) { int type; - struct rgrp_list *rgd; + struct rgrp_tree *rgd;
rgd = gfs2_blk2rgrpd(&sbd, block); if (rgd) { @@ -1484,7 +1484,7 @@ static void rgcount(void) printf("%lld RGs in this file system.\n", (unsigned long long)sbd.md.riinode->i_di.di_size / risize()); inode_put(&sbd.md.riinode); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_SUCCESS); }
@@ -1757,7 +1757,7 @@ static int block_has_extended_info(void) { if (has_indirect_blocks() || block_is_rindex() || - block_is_rglist() || + block_is_rgtree() || block_is_jindex() || block_is_inum_file() || block_is_statfs_file() || @@ -1784,7 +1784,7 @@ static void read_superblock(int fd) sbd.utsize = GFS2_DEFAULT_UTSIZE; sbd.qcsize = GFS2_DEFAULT_QCSIZE; sbd.time = time(NULL); - osi_list_init(&sbd.rglist); + sbd.rgtree.osi_node = NULL; gfs2_sb_in(&sbd.sd_sb, bh); /* parse it out into the sb structure */ /* Check to see if this is really gfs1 */ if (sbd1->sb_fs_format == GFS_FORMAT_FS && @@ -2102,7 +2102,7 @@ static uint64_t find_metablockoftype_slow(uint64_t startblk, int metatype, int p else printf("%llu\n", (unsigned long long)blk); } - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); if (print) exit(0); return blk; @@ -2117,16 +2117,17 @@ static uint64_t find_metablockoftype_slow(uint64_t startblk, int metatype, int p /* ------------------------------------------------------------------------ */ static uint64_t find_metablockoftype_rg(uint64_t startblk, int metatype, int print) { + struct osi_node *n, *next = NULL; uint64_t blk; int first = 1, found = 0; - struct rgrp_list *rgd; + struct rgrp_tree *rgd; struct gfs2_rindex *ri; - osi_list_t *tmp;
blk = 0; /* Skip the rgs prior to the block we've been given */ - for(tmp = sbd.rglist.next; tmp != &sbd.rglist; tmp = tmp->next){ - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sbd.rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; ri = &rgd->ri; if (first && startblk <= ri->ri_data0) { startblk = ri->ri_data0; @@ -2141,12 +2142,13 @@ static uint64_t find_metablockoftype_rg(uint64_t startblk, int metatype, int pri if (!rgd) { if (print) printf("0\n"); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); if (print) exit(-1); } - for(; !found && tmp != &sbd.rglist; tmp = tmp->next){ - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (; !found && n; n = next){ + next = osi_next(n); + rgd = (struct rgrp_tree *)n; first = 1; do { if (gfs2_next_rg_metatype(&sbd, rgd, &blk, metatype, @@ -2167,7 +2169,7 @@ static uint64_t find_metablockoftype_rg(uint64_t startblk, int metatype, int pri else printf("%llu\n", (unsigned long long)blk); } - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); if (print) exit(0); return blk; @@ -2201,7 +2203,7 @@ static uint64_t find_metablockoftype(const char *strtype, int print) "specified: must be one of:\n"); fprintf(stderr, "sb rg rb di in lf jd lh ld" " ea ed lb 13 qc\n"); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(-1); } return blk; @@ -2502,7 +2504,7 @@ static void find_print_block_type(void) type = get_block_type(lbh); print_block_type(tblock, type, ""); brelse(lbh); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(0); }
@@ -2513,7 +2515,7 @@ static void find_print_block_rg(int bitmap) { uint64_t rblock, rgblock; int i; - struct rgrp_list *rgd; + struct rgrp_tree *rgd;
rblock = blockstack[blockhist % BLOCK_STACK_SIZE].block; if (rblock == sbd.sb_addr) @@ -2545,7 +2547,7 @@ static void find_print_block_rg(int bitmap) printf("-1 (block invalid or part of an rgrp).\n"); } } - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(0); }
@@ -2556,7 +2558,7 @@ static void find_change_block_alloc(int *newval) { uint64_t ablock; int type; - struct rgrp_list *rgd; + struct rgrp_tree *rgd;
if (newval && (*newval < GFS2_BLKST_FREE || *newval > GFS2_BLKST_DINODE)) { @@ -2566,7 +2568,7 @@ static void find_change_block_alloc(int *newval) *newval); for (i = GFS2_BLKST_FREE; i <= GFS2_BLKST_DINODE; i++) printf("%d - %s\n", i, allocdesc[gfs1][i]); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(-1); } ablock = blockstack[blockhist % BLOCK_STACK_SIZE].block; @@ -2592,12 +2594,12 @@ static void find_change_block_alloc(int *newval) } gfs2_rgrp_relse(rgd); } else { - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); printf("-1 (block invalid or part of an rgrp).\n"); exit(-1); } } - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); if (newval) fsync(sbd.device_fd); exit(0); @@ -3525,7 +3527,7 @@ static void process_parameters(int argc, char *argv[], int pass) printf("Error: field not specified.\n"); printf("Format is: %s -p <block> field " "<field> [newvalue]\n", argv[0]); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_FAILURE); } process_field(argv[i], argv[i + 1]); @@ -3558,7 +3560,7 @@ static void process_parameters(int argc, char *argv[], int pass) printf("Error: rg # not specified.\n"); printf("Format is: %s rgflags rgnum" "[newvalue]\n", argv[0]); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_FAILURE); } if (argv[i][0]=='0' && argv[i][1]=='x') @@ -3575,7 +3577,7 @@ static void process_parameters(int argc, char *argv[], int pass) new_flags = atoi(argv[i]); } set_rgrp_flags(rg, new_flags, set, FALSE); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_SUCCESS); } else if (!strcmp(argv[i], "rg")) { int rg; @@ -3584,7 +3586,7 @@ static void process_parameters(int argc, char *argv[], int pass) if (i >= argc - 1) { printf("Error: rg # not specified.\n"); printf("Format is: %s rg rgnum\n", argv[0]); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_FAILURE); } rg = atoi(argv[i]); @@ -3593,7 +3595,7 @@ static void process_parameters(int argc, char *argv[], int pass) push_block(temp_blk); } else { set_rgrp_flags(rg, 0, FALSE, TRUE); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_SUCCESS); } } @@ -3705,6 +3707,6 @@ int main(int argc, char *argv[]) close(fd); if (indirect) free(indirect); - gfs2_rgrp_free(&sbd.rglist); + gfs2_rgrp_free(&sbd.rgtree); exit(EXIT_SUCCESS); } diff --git a/gfs2/edit/hexedit.h b/gfs2/edit/hexedit.h index 8732c27..d90b4c5 100644 --- a/gfs2/edit/hexedit.h +++ b/gfs2/edit/hexedit.h @@ -262,11 +262,11 @@ static inline int risize(void) }
/* ------------------------------------------------------------------------ */ -/* block_is_rglist - there's no such block as the rglist. This is a */ +/* block_is_rgtree - there's no such block as the rglist. This is a */ /* special case meant to parse the rindex and follow the */ /* blocks to the real rgs. */ /* ------------------------------------------------------------------------ */ -static inline int block_is_rglist(void) +static inline int block_is_rgtree(void) { if (block == RGLIST_DUMMY_BLOCK) return TRUE; diff --git a/gfs2/edit/savemeta.c b/gfs2/edit/savemeta.c index fd0e1e4..337d98a 100644 --- a/gfs2/edit/savemeta.c +++ b/gfs2/edit/savemeta.c @@ -600,7 +600,7 @@ static void get_journal_inode_blocks(void) } }
-static int next_rg_freemeta(struct gfs2_sbd *sdp, struct rgrp_list *rgd, +static int next_rg_freemeta(struct gfs2_sbd *sdp, struct rgrp_tree *rgd, uint64_t *nrfblock, int first) { struct gfs2_bitmap *bits = NULL; @@ -642,11 +642,10 @@ static int next_rg_freemeta(struct gfs2_sbd *sdp, struct rgrp_list *rgd, void savemeta(char *out_fn, int saveoption, int gziplevel) { int slow; - osi_list_t *tmp; int rgcount; uint64_t jindex_block; struct gfs2_buffer_head *lbh; - struct rgrp_list *last_rgd; + struct rgrp_tree *last_rgd, *prev_rgd; struct metafd mfd;
slow = (saveoption == 1); @@ -665,7 +664,7 @@ void savemeta(char *out_fn, int saveoption, int gziplevel) if (!slow) { device_geometry(&sbd); fix_device_geometry(&sbd); - osi_list_init(&sbd.rglist); + sbd.rgtree.osi_node = NULL; if (!gfs1) sbd.sd_sb.sb_bsize = GFS2_DEFAULT_BSIZE; compute_constants(&sbd); @@ -716,6 +715,7 @@ void savemeta(char *out_fn, int saveoption, int gziplevel) if (!slow) { int sane; uint64_t fssize; + struct osi_node *n;
printf("Reading resource groups..."); fflush(stdout); @@ -723,9 +723,12 @@ void savemeta(char *out_fn, int saveoption, int gziplevel) slow = gfs1_ri_update(&sbd, 0, &rgcount, 0); else slow = ri_update(&sbd, 0, &rgcount, &sane); - last_rgd = osi_list_entry(sbd.rglist.prev, - struct rgrp_list, list); - fssize = last_rgd->ri.ri_addr + rgrp_size(last_rgd); + n = osi_last(&sbd.rgtree); + last_rgd = (struct rgrp_tree *)n; + n = osi_prev(n); + prev_rgd = (struct rgrp_tree *)n; + fssize = last_rgd->ri.ri_addr + + (last_rgd->ri.ri_addr - prev_rgd->ri.ri_addr); last_fs_block = fssize; fssize *= sbd.bsize; printf("Done. File system size: %s\n\n", @@ -734,6 +737,8 @@ void savemeta(char *out_fn, int saveoption, int gziplevel) } get_journal_inode_blocks(); if (!slow) { + struct osi_node *n, *next = NULL; + /* Save off the superblock */ save_block(sbd.device_fd, &mfd, 0x10 * (4096 / sbd.bsize)); /* If this is gfs1, save off the rindex because it's not @@ -755,12 +760,12 @@ void savemeta(char *out_fn, int saveoption, int gziplevel) } } /* Walk through the resource groups saving everything within */ - for (tmp = sbd.rglist.next; tmp != &sbd.rglist; - tmp = tmp->next){ - struct rgrp_list *rgd; + for (n = osi_first(&sbd.rgtree); n; n = next) { int first; + struct rgrp_tree *rgd;
- rgd = osi_list_entry(tmp, struct rgrp_list, list); + next = osi_next(n); + rgd = (struct rgrp_tree *)n; slow = gfs2_rgrp_read(&sbd, rgd); if (slow) continue; diff --git a/gfs2/fsck/fs_recovery.c b/gfs2/fsck/fs_recovery.c index 214aa18..da80f5c 100644 --- a/gfs2/fsck/fs_recovery.c +++ b/gfs2/fsck/fs_recovery.c @@ -14,6 +14,7 @@ #include <errno.h> #include <inttypes.h> #include <linux_endian.h> +#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> diff --git a/gfs2/fsck/initialize.c b/gfs2/fsck/initialize.c index 75f81f5..7855db4 100644 --- a/gfs2/fsck/initialize.c +++ b/gfs2/fsck/initialize.c @@ -121,7 +121,7 @@ static void gfs2_inodetree_free(void) static void empty_super_block(struct gfs2_sbd *sdp) { log_info( _("Freeing buffers.\n")); - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree);
if (bl) gfs2_bmap_destroy(sdp, bl); @@ -142,10 +142,9 @@ static void empty_super_block(struct gfs2_sbd *sdp) */ static int set_block_ranges(struct gfs2_sbd *sdp) { - - struct rgrp_list *rgd; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rgd; struct gfs2_rindex *ri; - osi_list_t *tmp; char buf[sdp->sd_sb.sb_bsize]; uint64_t rmax = 0; uint64_t rmin = 0; @@ -153,9 +152,9 @@ static int set_block_ranges(struct gfs2_sbd *sdp)
log_info( _("Setting block ranges...\n"));
- for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) - { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; ri = &rgd->ri; if (ri->ri_data0 + ri->ri_data - 1 > rmax) rmax = ri->ri_data0 + ri->ri_data - 1; @@ -200,7 +199,7 @@ static int set_block_ranges(struct gfs2_sbd *sdp) /** * check_rgrp_integrity - verify a rgrp free block count against the bitmap */ -static void check_rgrp_integrity(struct gfs2_sbd *sdp, struct rgrp_list *rgd, +static void check_rgrp_integrity(struct gfs2_sbd *sdp, struct rgrp_tree *rgd, int *fixit, int *this_rg_fixed, int *this_rg_bad) { @@ -305,17 +304,18 @@ static void check_rgrp_integrity(struct gfs2_sbd *sdp, struct rgrp_list *rgd, */ static int check_rgrps_integrity(struct gfs2_sbd *sdp) { + struct osi_node *n, *next = NULL; int rgs_good = 0, rgs_bad = 0, rgs_fixed = 0; int was_bad = 0, was_fixed = 0, error = 0; - osi_list_t *tmp; - struct rgrp_list *rgd; + struct rgrp_tree *rgd; int reclaim_unlinked = 0;
log_info( _("Checking the integrity of all resource groups.\n")); - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; if (fsck_abort) return 0; - rgd = osi_list_entry(tmp, struct rgrp_list, list); check_rgrp_integrity(sdp, rgd, &reclaim_unlinked, &was_fixed, &was_bad); if (was_fixed) @@ -542,7 +542,7 @@ static int fetch_rgrps(struct gfs2_sbd *sdp) *******************************************************************/ log_warn( _("Validating Resource Group index.\n")); for (trust_lvl = blind_faith; trust_lvl <= distrust; trust_lvl++) { - int ret; + int ret = 0;
log_warn( _("Level %d rgrp check: %s.\n"), trust_lvl + 1, level_desc[trust_lvl]); @@ -749,7 +749,7 @@ static int get_lockproto_table(struct gfs2_sbd *sdp) { FILE *fp; char line[PATH_MAX]; - char *cluname, *end; + char *cluname = NULL, *end = NULL; const char *fsname, *cfgfile = "/etc/cluster/cluster.conf";
memset(sdp->lockproto, 0, sizeof(sdp->lockproto)); @@ -1218,7 +1218,7 @@ static int fill_super_block(struct gfs2_sbd *sdp) ***************** First, initialize all lists ********************** ********************************************************************/ log_info( _("Initializing lists...\n")); - osi_list_init(&sdp->rglist); + sdp->rgtree.osi_node = NULL;
/******************************************************************** ************ next, read in on-disk SB and set constants ********** @@ -1298,7 +1298,7 @@ static int init_jindex(struct gfs2_sbd *sdp)
err = build_jindex(sdp); /* Free rgrps read in earlier (re-read them later) */ - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree); if (err) { log_crit(_("Error %d rebuilding jindex\n"), err); return err; diff --git a/gfs2/fsck/main.c b/gfs2/fsck/main.c index 4e556f1..40aaaab 100644 --- a/gfs2/fsck/main.c +++ b/gfs2/fsck/main.c @@ -159,8 +159,8 @@ static void interrupt(int sig)
static void check_statfs(struct gfs2_sbd *sdp) { - osi_list_t *tmp; - struct rgrp_list *rgd; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rgd; struct gfs2_rindex *ri; struct gfs2_statfs_change sc; char buf[sizeof(struct gfs2_statfs_change)]; @@ -177,8 +177,9 @@ static void check_statfs(struct gfs2_sbd *sdp) sdp->blks_alloced = 0; sdp->dinodes_alloced = 0;
- for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; ri = &rgd->ri; sdp->blks_total += ri->ri_data; sdp->blks_alloced += (ri->ri_data - rgd->rg.rg_free); diff --git a/gfs2/fsck/metawalk.c b/gfs2/fsck/metawalk.c index a61971c..035fb34 100644 --- a/gfs2/fsck/metawalk.c +++ b/gfs2/fsck/metawalk.c @@ -43,7 +43,7 @@ int check_n_fix_bitmap(struct gfs2_sbd *sdp, uint64_t blk, enum gfs2_mark_block new_blockmap_state) { int old_bitmap_state, new_bitmap_state; - struct rgrp_list *rgd; + struct rgrp_tree *rgd;
rgd = gfs2_blk2rgrpd(sdp, blk);
diff --git a/gfs2/fsck/pass1.c b/gfs2/fsck/pass1.c index 6075ac5..c0369c5 100644 --- a/gfs2/fsck/pass1.c +++ b/gfs2/fsck/pass1.c @@ -1505,10 +1505,10 @@ static int check_system_inodes(struct gfs2_sbd *sdp) */ int pass1(struct gfs2_sbd *sdp) { + struct osi_node *n, *next = NULL; struct gfs2_buffer_head *bh; - osi_list_t *tmp; uint64_t block; - struct rgrp_list *rgd; + struct rgrp_tree *rgd; int first; uint64_t i; uint64_t blk_count; @@ -1533,11 +1533,11 @@ int pass1(struct gfs2_sbd *sdp) * uses the rg bitmaps, so maybe that's the best way to start * things - we can change the method later if necessary. */ - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; - tmp = tmp->next, rg_count++) { - log_debug( _("Checking metadata in Resource Group #%" PRIu64 "\n"), - rg_count); - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next, rg_count++) { + next = osi_next(n); + log_debug( _("Checking metadata in Resource Group #%llu\n"), + (unsigned long long)rg_count); + rgd = (struct rgrp_tree *)n; for (i = 0; i < rgd->ri.ri_length; i++) { log_debug( _("rgrp block %lld (0x%llx) " "is now marked as 'rgrp data'\n"), diff --git a/gfs2/fsck/pass5.c b/gfs2/fsck/pass5.c index f2d23cd..a811cdb 100644 --- a/gfs2/fsck/pass5.c +++ b/gfs2/fsck/pass5.c @@ -157,7 +157,7 @@ static int check_block_status(struct gfs2_sbd *sdp, char *buffer, return 0; }
-static void update_rgrp(struct gfs2_sbd *sdp, struct rgrp_list *rgp, +static void update_rgrp(struct gfs2_sbd *sdp, struct rgrp_tree *rgp, uint32_t *count) { uint32_t i; @@ -221,18 +221,19 @@ static void update_rgrp(struct gfs2_sbd *sdp, struct rgrp_list *rgp, */ int pass5(struct gfs2_sbd *sdp) { - osi_list_t *tmp; - struct rgrp_list *rgp = NULL; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rgp = NULL; uint32_t count[3]; uint64_t rg_count = 0;
/* Reconcile RG bitmaps with fsck bitmap */ - for(tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next){ + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); if (skip_this_pass || fsck_abort) /* if asked to skip the rest */ return FSCK_OK; log_info( _("Verifying Resource Group #%" PRIu64 "\n"), rg_count); memset(count, 0, sizeof(count)); - rgp = osi_list_entry(tmp, struct rgrp_list, list); + rgp = (struct rgrp_tree *)n;
rg_count++; /* Compare the bitmaps and report the differences */ diff --git a/gfs2/fsck/rgrepair.c b/gfs2/fsck/rgrepair.c index 2afa4ce..fb4d092 100644 --- a/gfs2/fsck/rgrepair.c +++ b/gfs2/fsck/rgrepair.c @@ -110,24 +110,22 @@ static int is_false_rg(uint64_t block) * same RG size determined by the original mkfs, so recovery is easier. * */ -static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, osi_list_t *ret_list, - int *num_rgs) +static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, int *num_rgs) { + struct osi_node *n, *next = NULL; struct gfs2_buffer_head *bh; uint64_t shortest_dist_btwn_rgs; uint64_t blk, block_of_last_rg; uint64_t fwd_block, block_bump; uint64_t first_rg_dist, initial_first_rg_dist; - struct rgrp_list *calc_rgd, *prev_rgd; + struct rgrp_tree *calc_rgd, *prev_rgd; int number_of_rgs, rgi; struct gfs2_rindex buf, tmpndx; int rg_was_fnd = FALSE, corrupt_rgs = 0, bitmap_was_fnd; - osi_list_t *tmp;
/* Figure out if there are any RG-looking blocks in the journal we need to ignore. */ find_journaled_rgs(sdp); - osi_list_init(ret_list); number_of_rgs = 0; initial_first_rg_dist = first_rg_dist = sdp->sb_addr + 1; block_of_last_rg = sdp->sb_addr + 1; @@ -210,6 +208,7 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, osi_list_t *ret_list, log_debug( _("Adjusted first RG distance: 0x%" PRIx64 "\n"), first_rg_dist); } /* if first RG distance is within tolerance */ + /* -------------------------------------------------------------- */ /* Now go through the RGs and verify their integrity, fixing as */ /* needed when corruption is encountered. */ @@ -223,15 +222,12 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, osi_list_t *ret_list, rg_was_fnd = (!gfs2_check_meta(bh, GFS2_METATYPE_RG)); brelse(bh); /* Allocate a new RG and index. */ - calc_rgd = malloc(sizeof(struct rgrp_list)); + calc_rgd = rgrp_insert(&sdp->rgcalc, blk); if (!calc_rgd) { log_crit( _("Can't allocate memory for rg repair.\n")); return -1; } - memset(calc_rgd, 0, sizeof(struct rgrp_list)); - osi_list_add_prev(&calc_rgd->list, ret_list); calc_rgd->ri.ri_length = 1; - calc_rgd->ri.ri_addr = blk; if (!rg_was_fnd) { /* if not an RG */ /* ------------------------------------------------- */ /* This SHOULD be an RG but isn't. */ @@ -316,10 +312,10 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, osi_list_t *ret_list, /* ---------------------------------------------- */ /* Now dump out the information (if verbose mode) */ /* ---------------------------------------------- */ - log_debug( _("RG index rebuilt as follows:\n")); - for (tmp = ret_list, rgi = 0; tmp != ret_list; - tmp = tmp->next, rgi++) { - calc_rgd = osi_list_entry(tmp, struct rgrp_list, list); + log_debug( _("rindex rebuilt as follows:\n")); + for (n = osi_first(&sdp->rgcalc), rgi = 0; n; n = next, rgi++) { + next = osi_next(n); + calc_rgd = (struct rgrp_tree *)n; log_debug("%d: 0x%llx / %x / 0x%llx" " / 0x%x / 0x%x\n", rgi + 1, (unsigned long long)calc_rgd->ri.ri_addr, @@ -344,15 +340,13 @@ static int gfs2_rindex_rebuild(struct gfs2_sbd *sdp, osi_list_t *ret_list, * Sets: sdp->rglist to a linked list of fsck_rgrp structs representing * what we think the rindex should really look like. */ -static int gfs2_rindex_calculate(struct gfs2_sbd *sdp, osi_list_t *ret_list, - int *num_rgs) +static int gfs2_rindex_calculate(struct gfs2_sbd *sdp, int *num_rgs) { - osi_list_init(ret_list); sdp->rgsize = GFS2_DEFAULT_RGSIZE; /* compute_rgrp_layout adjusts */ device_geometry(sdp); fix_device_geometry(sdp); /* Compute the default resource group layout as mkfs would have done */ - compute_rgrp_layout(sdp, FALSE); + compute_rgrp_layout(sdp, &sdp->rgcalc, FALSE); build_rgrps(sdp, FALSE); /* FALSE = calc but don't write to disk. */ *num_rgs = 0; log_debug( _("fs_total_size = 0x%" PRIX64 " blocks.\n"), @@ -365,12 +359,8 @@ static int gfs2_rindex_calculate(struct gfs2_sbd *sdp, osi_list_t *ret_list, /* the index. */ /* ----------------------------------------------------------------- */ *num_rgs = sdp->md.riinode->i_di.di_size / sizeof(struct gfs2_rindex); - log_warn( _("L2: number of rgs in the index = %d.\n"), *num_rgs); - /* Move the rg list to the return list */ - ret_list->next = sdp->rglist.next; - ret_list->prev = sdp->rglist.prev; - ret_list->next->prev = ret_list; - ret_list->prev->next = ret_list; + + sdp->rgcalc.osi_node = NULL; return 0; }
@@ -378,8 +368,8 @@ static int gfs2_rindex_calculate(struct gfs2_sbd *sdp, osi_list_t *ret_list, * rewrite_rg_block - rewrite ("fix") a buffer with rg or bitmap data * returns: 0 if the rg was repaired, otherwise 1 */ -static int rewrite_rg_block(struct gfs2_sbd *sdp, struct rgrp_list *rg, - uint64_t errblock) +static int rewrite_rg_block(struct gfs2_sbd *sdp, struct rgrp_tree *rg, + uint64_t errblock) { int x = errblock - rg->ri.ri_addr;
@@ -418,18 +408,16 @@ static int rewrite_rg_block(struct gfs2_sbd *sdp, struct rgrp_list *rg, * values as our expected values and assume the * damage is only to the rgrps themselves. */ -static int expect_rindex_sanity(struct gfs2_sbd *sdp, osi_list_t *ret_list, - int *num_rgs) +static int expect_rindex_sanity(struct gfs2_sbd *sdp, int *num_rgs) { - osi_list_t *tmp; - struct rgrp_list *exp, *rgd; /* expected, actual */ + struct osi_node *n, *next = NULL; + struct rgrp_tree *rgd, *exp;
*num_rgs = sdp->md.riinode->i_di.di_size / sizeof(struct gfs2_rindex) ; - osi_list_init(ret_list); - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); - - exp = calloc(1, sizeof(struct rgrp_list)); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; + exp = rgrp_insert(&sdp->rgcalc, rgd->ri.ri_addr); if (exp == NULL) { fprintf(stderr, "Out of memory in %s\n", __FUNCTION__); exit(-1); @@ -440,7 +428,6 @@ static int expect_rindex_sanity(struct gfs2_sbd *sdp, osi_list_t *ret_list, memcpy(&exp->rg, &rgd->rg, sizeof(exp->rg)); exp->bits = NULL; gfs2_compute_bitstructs(sdp, exp); - osi_list_add_prev(&exp->list, ret_list); } sdp->rgrps = *num_rgs; return 0; @@ -456,10 +443,9 @@ static int expect_rindex_sanity(struct gfs2_sbd *sdp, osi_list_t *ret_list, */ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) { + struct osi_node *n, *next = NULL, *e, *enext; int error, discrepancies; - osi_list_t expected_rglist; int calc_rg_count = 0, rgcount_from_index, rg; - osi_list_t *exp, *act; /* expected, actual */ struct gfs2_rindex buf;
if (trust_lvl == blind_faith) @@ -470,45 +456,53 @@ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) "expectations.\n")); return -1; } - error = expect_rindex_sanity(sdp, &expected_rglist, - &calc_rg_count); - if (error) + error = expect_rindex_sanity(sdp, &calc_rg_count); + if (error) { + gfs2_rgrp_free(&sdp->rgcalc); return error; + } } else if (trust_lvl == open_minded) { /* If we can't trust RG index */ + /* Free previous incarnations in memory, if any. */ + gfs2_rgrp_free(&sdp->rgtree); + /* Calculate our own RG index for comparison */ - error = gfs2_rindex_calculate(sdp, &expected_rglist, - &calc_rg_count); + error = gfs2_rindex_calculate(sdp, &calc_rg_count); if (error) { /* If calculated RGs don't match the fs */ - gfs2_rgrp_free(&expected_rglist); + gfs2_rgrp_free(&sdp->rgcalc); return -1; } } else if (trust_lvl == distrust) { /* If we can't trust RG index */ - error = gfs2_rindex_rebuild(sdp, &expected_rglist, - &calc_rg_count); + /* Free previous incarnations in memory, if any. */ + gfs2_rgrp_free(&sdp->rgtree); + + error = gfs2_rindex_rebuild(sdp, &calc_rg_count); if (error) { - log_crit( _("Error rebuilding rg list.\n")); - gfs2_rgrp_free(&expected_rglist); + log_crit( _("Error rebuilding rgrp list.\n")); + gfs2_rgrp_free(&sdp->rgcalc); return -1; } sdp->rgrps = calc_rg_count; } + /* Read in the rindex */ - osi_list_init(&sdp->rglist); /* Just to be safe */ + sdp->rgtree.osi_node = NULL; /* Just to be safe */ rindex_read(sdp, 0, &rgcount_from_index, sane); if (sdp->md.riinode->i_di.di_size % sizeof(struct gfs2_rindex)) { log_warn( _("WARNING: rindex file is corrupt.\n")); - gfs2_rgrp_free(&expected_rglist); - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgcalc); + gfs2_rgrp_free(&sdp->rgtree); return -1; } log_warn( _("L%d: number of rgs expected = %lld.\n"), trust_lvl + 1, (unsigned long long)sdp->rgrps); if (calc_rg_count != sdp->rgrps) { - log_warn( _("L%d: They don't match; either (1) the fs was extended, (2) an odd\n"), trust_lvl + 1); - log_warn( _("L%d: rg size was used, or (3) we have a corrupt rg index.\n"), trust_lvl + 1); - gfs2_rgrp_free(&expected_rglist); - gfs2_rgrp_free(&sdp->rglist); + log_warn( _("L%d: They don't match; either (1) the fs was " + "extended, (2) an odd\n"), trust_lvl + 1); + log_warn( _("L%d: rgrp size was used, or (3) we have a corrupt " + "rg index.\n"), trust_lvl + 1); + gfs2_rgrp_free(&sdp->rgcalc); + gfs2_rgrp_free(&sdp->rgtree); return -1; } /* ------------------------------------------------------------- */ @@ -519,28 +513,46 @@ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) /* abandon this method of recovery and try a better one. */ /* ------------------------------------------------------------- */ discrepancies = 0; - for (rg = 0, act = sdp->rglist.next, exp = expected_rglist.next; - act != &sdp->rglist && exp != &expected_rglist; - act = act->next, exp = exp->next, rg++) { - struct rgrp_list *expected, *actual; - - expected = osi_list_entry(exp, struct rgrp_list, list); - actual = osi_list_entry(act, struct rgrp_list, list); - if (!ri_equal(actual->ri, expected->ri, ri_addr) || - !ri_equal(actual->ri, expected->ri, ri_length) || + for (rg = 0, n = osi_first(&sdp->rgtree), e = osi_first(&sdp->rgcalc); + n && e && !fsck_abort; rg++) { + struct rgrp_tree *expected, *actual; + + next = osi_next(n); + enext = osi_next(e); + + expected = (struct rgrp_tree *)e; + actual = (struct rgrp_tree *)n; + if (actual->ri.ri_addr < expected->ri.ri_addr) { + n = next; + discrepancies++; + log_info(_("%d addr: 0x%llx < 0x%llx * mismatch\n"), + rg + 1, actual->ri.ri_addr, + expected->ri.ri_addr); + continue; + } else if (expected->ri.ri_addr < actual->ri.ri_addr) { + e = enext; + discrepancies++; + log_info(_("%d addr: 0x%llx > 0x%llx * mismatch\n"), + rg + 1, actual->ri.ri_addr, + expected->ri.ri_addr); + continue; + } + if (!ri_equal(actual->ri, expected->ri, ri_length) || !ri_equal(actual->ri, expected->ri, ri_data0) || !ri_equal(actual->ri, expected->ri, ri_data) || !ri_equal(actual->ri, expected->ri, ri_bitbytes)) { discrepancies++; } + n = next; + e = enext; } if (trust_lvl < distrust && discrepancies > (trust_lvl * 8)) { log_warn( _("Level %d didn't work. Too many descepencies.\n"), trust_lvl + 1); log_warn( _("%d out of %d RGs did not match what was expected.\n"), discrepancies, rg); - gfs2_rgrp_free(&expected_rglist); - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgcalc); + gfs2_rgrp_free(&sdp->rgtree); return -1; } /* ------------------------------------------------------------- */ @@ -548,19 +560,40 @@ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) /* Our rindex should be pretty predictable unless we've grown */ /* so look for index problems first before looking at the rgs. */ /* ------------------------------------------------------------- */ - for (rg = 0, act = sdp->rglist.next, exp = expected_rglist.next; - act != &sdp->rglist && exp != &expected_rglist; - act = act->next, exp = exp->next, rg++) { - struct rgrp_list *expected, *actual; - - expected = osi_list_entry(exp, struct rgrp_list, list); - actual = osi_list_entry(act, struct rgrp_list, list); - ri_compare(rg, actual->ri, expected->ri, ri_addr, PRIx64); - ri_compare(rg, actual->ri, expected->ri, ri_length, PRIx32); - ri_compare(rg, actual->ri, expected->ri, ri_data0, PRIx64); - ri_compare(rg, actual->ri, expected->ri, ri_data, PRIx32); - ri_compare(rg, actual->ri, expected->ri, ri_bitbytes, - PRIx32); + for (rg = 0, n = osi_first(&sdp->rgtree), e = osi_first(&sdp->rgcalc); + e && !fsck_abort; rg++) { + struct rgrp_tree *expected, *actual; + + if (n) + next = osi_next(n); + enext = osi_next(e); + expected = (struct rgrp_tree *)e; + + /* If we ran out of actual rindex entries due to rindex + damage, fill in a new one with the expected values. */ + if (!n) { /* end of actual rindex */ + log_err( _("Entry missing from rindex: 0x%llx\n"), + (unsigned long long)expected->ri.ri_addr); + actual = rgrp_insert(&sdp->rgtree, + expected->ri.ri_addr); + if (!actual) { + log_err(_("Out of memory!\n")); + break; + } + rindex_modified = 1; + } else { + actual = (struct rgrp_tree *)n; + ri_compare(rg, actual->ri, expected->ri, ri_addr, + "llx"); + ri_compare(rg, actual->ri, expected->ri, ri_length, + PRIx32); + ri_compare(rg, actual->ri, expected->ri, ri_data0, + "llx"); + ri_compare(rg, actual->ri, expected->ri, ri_data, + PRIx32); + ri_compare(rg, actual->ri, expected->ri, ri_bitbytes, + PRIx32); + } /* If we modified the index, write it back to disk. */ if (rindex_modified) { if (query( _("Fix the index? (y/n)"))) { @@ -586,23 +619,27 @@ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) gfs2_compute_bitstructs(sdp, actual); rindex_modified = FALSE; } + e = enext; + if (n) + n = next; } /* ------------------------------------------------------------- */ /* Read the real RGs and check their integrity. */ /* Now we can somewhat trust the rindex and the RG addresses, */ /* so let's read them in, check them and optionally fix them. */ /* ------------------------------------------------------------- */ - for (rg = 0, act = sdp->rglist.next; act != &sdp->rglist; - act = act->next, rg++) { - struct rgrp_list *rgd; + for (rg = 0, n = osi_first(&sdp->rgtree); n && !fsck_abort; + n = next, rg++) { + struct rgrp_tree *rgd; uint64_t prev_err = 0, errblock; int i;
+ next = osi_next(n); /* Now we try repeatedly to read in the rg. For every block */ /* we encounter that has errors, repair it and try again. */ i = 0; do { - rgd = osi_list_entry(act, struct rgrp_list, list); + rgd = (struct rgrp_tree *)n; errblock = gfs2_rgrp_read(sdp, rgd); if (errblock) { if (errblock == prev_err) @@ -617,7 +654,7 @@ int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count, int *sane) } while (i < rgd->ri.ri_length); } *rg_count = rg; - gfs2_rgrp_free(&expected_rglist); - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgcalc); + gfs2_rgrp_free(&sdp->rgtree); return 0; } diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c index 79d76cf..d95461b 100644 --- a/gfs2/fsck/util.c +++ b/gfs2/fsck/util.c @@ -492,7 +492,6 @@ void *gfs2_bmap_destroy(struct gfs2_sbd *sdp, struct gfs2_bmap *il) int set_ip_blockmap(struct gfs2_inode *ip, int instree) { uint64_t block = ip->i_bh->b_blocknr; - struct gfs2_sbd *sdp = ip->i_sbd; uint32_t mode;
mode = ip->i_di.di_mode & S_IFMT; diff --git a/gfs2/libgfs2/fs_bits.c b/gfs2/libgfs2/fs_bits.c index 11b6fb2..4834a2a 100644 --- a/gfs2/libgfs2/fs_bits.c +++ b/gfs2/libgfs2/fs_bits.c @@ -188,7 +188,7 @@ int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state) int buf; uint32_t rgrp_block; struct gfs2_bitmap *bits = NULL; - struct rgrp_list *rgd; + struct rgrp_tree *rgd; unsigned char *byte, cur_state; unsigned int bit;
@@ -236,7 +236,7 @@ int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state) * Returns: state on success, -1 on error */ int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, - struct rgrp_list *rgd) + struct rgrp_tree *rgd) { int i, val; uint32_t rgrp_block; diff --git a/gfs2/libgfs2/fs_geometry.c b/gfs2/libgfs2/fs_geometry.c index 9969577..58c1c89 100644 --- a/gfs2/libgfs2/fs_geometry.c +++ b/gfs2/libgfs2/fs_geometry.c @@ -62,12 +62,14 @@ static uint64_t how_many_rgrps(struct gfs2_sbd *sdp, struct device *dev, int rgs * Returns: a list of rgrp_list_t structures */
-void compute_rgrp_layout(struct gfs2_sbd *sdp, int rgsize_specified) +void compute_rgrp_layout(struct gfs2_sbd *sdp, struct osi_root *rgtree, + int rgsize_specified) { struct device *dev; - struct rgrp_list *rl, *rlast = NULL, *rlast2 = NULL; - osi_list_t *tmp, *head = &sdp->rglist; + struct rgrp_tree *rl, *rlast = NULL, *rlast2 = NULL; + struct osi_node *n, *next = NULL; unsigned int rgrp = 0, nrgrp, rglength; + uint64_t rgaddr;
sdp->new_rgrps = 0; dev = &sdp->device; @@ -78,7 +80,7 @@ void compute_rgrp_layout(struct gfs2_sbd *sdp, int rgsize_specified) /* If this is a new file system, compute the length and number */ /* of rgs based on the size of the device. */ /* If we have existing RGs (i.e. gfs2_grow) find the last one. */ - if (osi_list_empty(&sdp->rglist)) { + if (!rgtree->osi_node) { dev->length -= sdp->sb_addr + 1; nrgrp = how_many_rgrps(sdp, dev, rgsize_specified); rglength = dev->length / nrgrp; @@ -87,10 +89,10 @@ void compute_rgrp_layout(struct gfs2_sbd *sdp, int rgsize_specified) uint64_t old_length, new_chunk;
log_info("Existing resource groups:\n"); - rgsize_specified = TRUE; /* consistently use existing size */ - for (rgrp = 0, tmp = head->next; tmp != head; - tmp = tmp->next, rgrp++) { - rl = osi_list_entry(tmp, struct rgrp_list, list); + for (rgrp = 0, n = osi_first(rgtree); n; n = next, rgrp++) { + next = osi_next(n); + rl = (struct rgrp_tree *)n; + log_info("%d: start: %" PRIu64 " (0x%" PRIx64 "), length = %"PRIu64" (0x%" PRIx64 ")\n", rgrp + 1, rl->start, rl->start, @@ -109,32 +111,31 @@ void compute_rgrp_layout(struct gfs2_sbd *sdp, int rgsize_specified)
log_info("\nNew resource groups:\n"); for (; rgrp < nrgrp; rgrp++) { - zalloc(rl, sizeof(struct rgrp_list)); - if (rgrp) { - rl->start = rlast->start + rlast->length; + rgaddr = rlast->start + rlast->length; + rl = rgrp_insert(rgtree, rgaddr); rl->length = rglength; } else { - rl->start = dev->start; + rgaddr = dev->start; + rl = rgrp_insert(rgtree, rgaddr); rl->length = dev->length - (nrgrp - 1) * (dev->length / nrgrp); } - + rl->start = rgaddr; log_info("%d: start: %" PRIu64 " (0x%" PRIx64 "), length = %"PRIu64" (0x%" PRIx64 ")\n", rgrp + 1, rl->start, rl->start, rl->length, rl->length); - osi_list_add_prev(&rl->list, head); rlast = rl; }
sdp->rgrps = nrgrp; - if (sdp->debug) { log_info("\n");
- for (tmp = head->next; tmp != head; tmp = tmp->next) { - rl = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(rgtree); n; n = next) { + next = osi_next(n); + rl = (struct rgrp_tree *)n; log_info("rg_o = %llu, rg_l = %llu\n", rl->start, rl->length); } @@ -185,8 +186,8 @@ rgblocks2bitblocks(unsigned int bsize, uint32_t *rgblocks, uint32_t *bitblocks) */ void build_rgrps(struct gfs2_sbd *sdp, int do_write) { - osi_list_t *tmp, *head; - struct rgrp_list *rl; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rl; uint32_t rgblocks, bitblocks; struct gfs2_rindex *ri; struct gfs2_meta_header mh; @@ -195,11 +196,14 @@ void build_rgrps(struct gfs2_sbd *sdp, int do_write) mh.mh_magic = GFS2_MAGIC; mh.mh_type = GFS2_METATYPE_RB; mh.mh_format = GFS2_FORMAT_RB; - - for (head = &sdp->rglist, tmp = head->next; - tmp != head; - tmp = tmp->next) { - rl = osi_list_entry(tmp, struct rgrp_list, list); + if (do_write) + n = osi_first(&sdp->rgtree); + else + n = osi_first(&sdp->rgcalc); + + for (; n; n = next) { + next = osi_next(n); + rl = (struct rgrp_tree *)n; ri = &rl->ri;
rgblocks = rl->length; diff --git a/gfs2/libgfs2/fs_ops.c b/gfs2/libgfs2/fs_ops.c index 1c20e61..78b3a8d 100644 --- a/gfs2/libgfs2/fs_ops.c +++ b/gfs2/libgfs2/fs_ops.c @@ -117,8 +117,8 @@ void inode_put(struct gfs2_inode **ip_in)
static uint64_t blk_alloc_i(struct gfs2_sbd *sdp, unsigned int type) { - osi_list_t *tmp, *head; - struct rgrp_list *rl = NULL; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rl = NULL; struct gfs2_rindex *ri; struct gfs2_rgrp *rg; unsigned int block, bn = 0, x = 0, y = 0; @@ -126,14 +126,14 @@ static uint64_t blk_alloc_i(struct gfs2_sbd *sdp, unsigned int type) struct gfs2_buffer_head *bh;
memset(&rg, 0, sizeof(rg)); - for (head = &sdp->rglist, tmp = head->next; tmp != head; - tmp = tmp->next) { - rl = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rl = (struct rgrp_tree *)n; if (rl->rg.rg_free) break; }
- if (tmp == head) + if (n == NULL) die("out of space\n");
ri = &rl->ri; @@ -1676,7 +1676,7 @@ int gfs2_lookupi(struct gfs2_inode *dip, const char *filename, int len, */ void gfs2_free_block(struct gfs2_sbd *sdp, uint64_t block) { - struct rgrp_list *rgd; + struct rgrp_tree *rgd;
/* Adjust the free space count for the freed block */ rgd = gfs2_blk2rgrpd(sdp, block); /* find the rg for indir block */ @@ -1698,7 +1698,7 @@ int gfs2_freedi(struct gfs2_sbd *sdp, uint64_t diblock) struct gfs2_buffer_head *bh, *nbh; int h, head_size; uint64_t *ptr, block; - struct rgrp_list *rgd; + struct rgrp_tree *rgd; uint32_t height; osi_list_t metalist[GFS2_MAX_META_HEIGHT]; osi_list_t *cur_list, *next_list, *tmp; diff --git a/gfs2/libgfs2/gfs1.c b/gfs2/libgfs2/gfs1.c index 5018334..41edf16 100644 --- a/gfs2/libgfs2/gfs1.c +++ b/gfs2/libgfs2/gfs1.c @@ -234,8 +234,8 @@ int gfs1_rindex_read(struct gfs2_sbd *sdp, int fd, int *count1) { unsigned int rg; int error; - struct gfs2_rindex buf; - struct rgrp_list *rgd, *prev_rgd; + struct gfs2_rindex buf, ri; + struct rgrp_tree *rgd = NULL, *prev_rgd = NULL; uint64_t prev_length = 0;
*count1 = 0; @@ -252,20 +252,14 @@ int gfs1_rindex_read(struct gfs2_sbd *sdp, int fd, int *count1) if (error != sizeof(struct gfs2_rindex)) return -1;
- rgd = (struct rgrp_list *)malloc(sizeof(struct rgrp_list)); - if (!rgd) { - log_crit("Cannot allocate memory for rindex.\n"); - exit(-1); - } - memset(rgd, 0, sizeof(struct rgrp_list)); - osi_list_add_prev(&rgd->list, &sdp->rglist); - - gfs2_rindex_in(&rgd->ri, (char *)&buf); + gfs2_rindex_in(&ri, (char *)&buf); + rgd = rgrp_insert(&sdp->rgtree, ri.ri_addr); + memcpy(&rgd->ri, &ri, sizeof(struct gfs2_rindex));
rgd->start = rgd->ri.ri_addr; if (prev_rgd) { prev_length = rgd->start - prev_rgd->start; - prev_rgd->length = prev_length; + prev_rgd->length = rgrp_size(prev_rgd); }
if(gfs2_compute_bitstructs(sdp, rgd)) @@ -275,7 +269,7 @@ int gfs1_rindex_read(struct gfs2_sbd *sdp, int fd, int *count1) prev_rgd = rgd; } if (prev_rgd) - prev_rgd->length = prev_length; + prev_rgd->length = rgrp_size(prev_rgd); return 0; }
@@ -291,17 +285,18 @@ int gfs1_rindex_read(struct gfs2_sbd *sdp, int fd, int *count1) */ int gfs1_ri_update(struct gfs2_sbd *sdp, int fd, int *rgcount, int quiet) { - struct rgrp_list *rgd; + struct rgrp_tree *rgd; struct gfs2_rindex *ri; - osi_list_t *tmp; int count1 = 0, count2 = 0; uint64_t errblock = 0; uint64_t rmax = 0; + struct osi_node *n, *next = NULL;
if (gfs1_rindex_read(sdp, fd, &count1)) goto fail; - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; errblock = gfs2_rgrp_read(sdp, rgd); if (errblock) return errblock; @@ -323,7 +318,7 @@ int gfs1_ri_update(struct gfs2_sbd *sdp, int fd, int *rgcount, int quiet) return 0;
fail: - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree); return -1; }
diff --git a/gfs2/libgfs2/libgfs2.h b/gfs2/libgfs2/libgfs2.h index 87c65c6..95a4ddb 100644 --- a/gfs2/libgfs2/libgfs2.h +++ b/gfs2/libgfs2/libgfs2.h @@ -23,6 +23,7 @@ #include <linux/gfs2_ondisk.h> #include "osi_list.h" #include "copyright.cf" +#include "osi_tree.h"
#ifndef TRUE #define TRUE (1) @@ -94,8 +95,8 @@ struct gfs2_bitmap }; typedef struct gfs2_bitmap gfs2_bitmap_t;
-struct rgrp_list { - osi_list_t list; +struct rgrp_tree { + struct osi_node node; uint64_t start; /* The offset of the beginning of this resource group */ uint64_t length; /* The length of this resource group */
@@ -221,7 +222,8 @@ struct gfs2_sbd { uint64_t orig_rgrps; uint64_t rgrps; uint64_t new_rgrps; - osi_list_t rglist; + struct osi_root rgtree; + struct osi_root rgcalc;
unsigned int orig_journals;
@@ -307,22 +309,23 @@ unsigned long gfs2_bitfit(const unsigned char *buf, const unsigned int len, unsigned long goal, unsigned char state);
/* functions with blk #'s that are rgrp relative */ -uint32_t gfs2_blkalloc_internal(struct rgrp_list *rgd, uint32_t goal, - unsigned char old_state, - unsigned char new_state, int do_it); -int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno); +extern uint32_t gfs2_blkalloc_internal(struct rgrp_tree *rgd, uint32_t goal, + unsigned char old_state, + unsigned char new_state, int do_it); +extern int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno);
/* functions with blk #'s that are file system relative */ extern int valid_block(struct gfs2_sbd *sdp, uint64_t blkno); extern int gfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, - struct rgrp_list *rgd); + struct rgrp_tree *rgd); extern int gfs2_set_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, int state);
/* fs_geometry.c */ -void rgblocks2bitblocks(unsigned int bsize, uint32_t *rgblocks, - uint32_t *bitblocks); -void compute_rgrp_layout(struct gfs2_sbd *sdp, int rgsize_specified); -void build_rgrps(struct gfs2_sbd *sdp, int write); +extern void rgblocks2bitblocks(unsigned int bsize, uint32_t *rgblocks, + uint32_t *bitblocks); +extern void compute_rgrp_layout(struct gfs2_sbd *sdp, struct osi_root *rgtree, + int rgsize_specified); +extern void build_rgrps(struct gfs2_sbd *sdp, int write);
/* fs_ops.c */ #define IS_LEAF (1) @@ -583,13 +586,15 @@ int gfs2_find_jhead(struct gfs2_inode *ip, struct gfs2_log_header *head); int clean_journal(struct gfs2_inode *ip, struct gfs2_log_header *head);
/* rgrp.c */ -extern int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_list *rgd); -extern struct rgrp_list *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk); -extern uint64_t gfs2_rgrp_read(struct gfs2_sbd *sdp, struct rgrp_list *rgd); -extern void gfs2_rgrp_relse(struct rgrp_list *rgd); -extern void gfs2_rgrp_free(osi_list_t *rglist); +extern int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_tree *rgd); +extern struct rgrp_tree *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk); +extern uint64_t gfs2_rgrp_read(struct gfs2_sbd *sdp, struct rgrp_tree *rgd); +extern void gfs2_rgrp_relse(struct rgrp_tree *rgd); +extern struct rgrp_tree *rgrp_insert(struct osi_root *rgtree, + uint64_t rgblock); +extern void gfs2_rgrp_free(struct osi_root *rgrp_tree); /* figure out the size of the given resource group, in blocks */ -static inline unsigned int rgrp_size(struct rgrp_list *rgrp) +static inline unsigned int rgrp_size(struct rgrp_tree *rgrp) { return rgrp->ri.ri_data + rgrp->ri.ri_length; } @@ -609,9 +614,9 @@ extern int build_root(struct gfs2_sbd *sdp); extern int do_init_inum(struct gfs2_sbd *sdp); extern int do_init_statfs(struct gfs2_sbd *sdp); extern int gfs2_check_meta(struct gfs2_buffer_head *bh, int type); -extern int gfs2_next_rg_meta(struct rgrp_list *rgd, uint64_t *block, +extern int gfs2_next_rg_meta(struct rgrp_tree *rgd, uint64_t *block, int first); -extern int gfs2_next_rg_metatype(struct gfs2_sbd *sdp, struct rgrp_list *rgd, +extern int gfs2_next_rg_metatype(struct gfs2_sbd *sdp, struct rgrp_tree *rgd, uint64_t *block, uint32_t type, int first); /* super.c */ extern int check_sb(struct gfs2_sb *sb); diff --git a/gfs2/libgfs2/rgrp.c b/gfs2/libgfs2/rgrp.c index 438d320..e9addeb 100644 --- a/gfs2/libgfs2/rgrp.c +++ b/gfs2/libgfs2/rgrp.c @@ -24,7 +24,7 @@ * * Returns: 0 on success, -1 on error */ -int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_list *rgd) +int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_tree *rgd) { struct gfs2_bitmap *bits; uint32_t length = rgd->ri.ri_length; @@ -104,33 +104,21 @@ int gfs2_compute_bitstructs(struct gfs2_sbd *sdp, struct rgrp_list *rgd) * * Returns: Ths resource group, or NULL if not found */ -struct rgrp_list *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk) +struct rgrp_tree *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk) { - osi_list_t *tmp; - struct rgrp_list *rgd; - static struct rgrp_list *prev_rgd = NULL; + struct osi_node *node = sdp->rgtree.osi_node; struct gfs2_rindex *ri;
- if (prev_rgd) { - ri = &prev_rgd->ri; - if (ri->ri_data0 <= blk && blk < ri->ri_data0 + ri->ri_data) - return prev_rgd; - if (blk >= ri->ri_addr && blk < ri->ri_addr + ri->ri_length) - return prev_rgd; - } - - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + while (node) { + struct rgrp_tree *rgd = (struct rgrp_tree *)node; ri = &rgd->ri;
- if (blk >= ri->ri_addr && blk < ri->ri_addr + ri->ri_length) { - prev_rgd = rgd; + if (blk < ri->ri_addr) + node = node->osi_left; + else if (blk > ri->ri_data0 + ri->ri_data) + node = node->osi_right; + else return rgd; - } - if (ri->ri_data0 <= blk && blk < ri->ri_data0 + ri->ri_data) { - prev_rgd = rgd; - return rgd; - } } return NULL; } @@ -140,7 +128,7 @@ struct rgrp_list *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, uint64_t blk) * @rgd - resource group structure * returns: 0 if no error, otherwise the block number that failed */ -uint64_t gfs2_rgrp_read(struct gfs2_sbd *sdp, struct rgrp_list *rgd) +uint64_t gfs2_rgrp_read(struct gfs2_sbd *sdp, struct rgrp_tree *rgd) { int x, length = rgd->ri.ri_length;
@@ -164,7 +152,7 @@ uint64_t gfs2_rgrp_read(struct gfs2_sbd *sdp, struct rgrp_list *rgd) return 0; }
-void gfs2_rgrp_relse(struct rgrp_list *rgd) +void gfs2_rgrp_relse(struct rgrp_tree *rgd) { int x, length = rgd->ri.ri_length;
@@ -177,12 +165,44 @@ void gfs2_rgrp_relse(struct rgrp_list *rgd) } }
-void gfs2_rgrp_free(osi_list_t *rglist) +struct rgrp_tree *rgrp_insert(struct osi_root *rgtree, uint64_t rgblock) +{ + struct osi_node **newn = &rgtree->osi_node, *parent = NULL; + struct rgrp_tree *data; + + /* Figure out where to put new node */ + while (*newn) { + struct rgrp_tree *cur = (struct rgrp_tree *)*newn; + + parent = *newn; + if (rgblock < cur->ri.ri_addr) + newn = &((*newn)->osi_left); + else if (rgblock > cur->ri.ri_addr) + newn = &((*newn)->osi_right); + else + return cur; + } + + data = malloc(sizeof(struct rgrp_tree)); + if (!data) + return NULL; + if (!memset(data, 0, sizeof(struct rgrp_tree))) + return NULL; + /* Add new node and rebalance tree. */ + data->ri.ri_addr = rgblock; + osi_link_node(&data->node, parent, newn); + osi_insert_color(&data->node, rgtree); + + return data; +} + +void gfs2_rgrp_free(struct osi_root *rgrp_tree) { - struct rgrp_list *rgd; + struct rgrp_tree *rgd; + struct osi_node *n;
- while(!osi_list_empty(rglist->next)){ - rgd = osi_list_entry(rglist->next, struct rgrp_list, list); + while ((n = osi_first(rgrp_tree))) { + rgd = (struct rgrp_tree *)n; if (rgd->bh && rgd->bh[0]) /* if a buffer exists */ gfs2_rgrp_relse(rgd); /* free them all. */ if(rgd->bits) @@ -191,7 +211,7 @@ void gfs2_rgrp_free(osi_list_t *rglist) free(rgd->bh); rgd->bh = NULL; } - osi_list_del(&rgd->list); + osi_erase(&rgd->node, rgrp_tree); free(rgd); } } diff --git a/gfs2/libgfs2/structures.c b/gfs2/libgfs2/structures.c index b7851e8..8a19afe 100644 --- a/gfs2/libgfs2/structures.c +++ b/gfs2/libgfs2/structures.c @@ -320,8 +320,8 @@ int build_statfs(struct gfs2_sbd *sdp) int build_rindex(struct gfs2_sbd *sdp) { struct gfs2_inode *ip; - osi_list_t *tmp, *head; - struct rgrp_list *rl; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rl; char buf[sizeof(struct gfs2_rindex)]; int count;
@@ -330,9 +330,9 @@ int build_rindex(struct gfs2_sbd *sdp) ip->i_di.di_payload_format = GFS2_FORMAT_RI; bmodified(ip->i_bh);
- for (head = &sdp->rglist, tmp = head->next; tmp != head; - tmp = tmp->next) { - rl = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rl = (struct rgrp_tree *)n;
gfs2_rindex_out(&rl->ri, buf);
@@ -498,24 +498,24 @@ int gfs2_set_meta(struct gfs2_buffer_head *bh, int type, int format) * * Returns: 0 on success, -1 when finished */ -int gfs2_next_rg_meta(struct rgrp_list *rgd, uint64_t *block, int first) +int gfs2_next_rg_meta(struct rgrp_tree *rgd, uint64_t *block, int first) { struct gfs2_bitmap *bits = NULL; uint32_t length = rgd->ri.ri_length; uint32_t blk = (first)? 0: (uint32_t)((*block+1)-rgd->ri.ri_data0); int i;
- if(!first && (*block < rgd->ri.ri_data0)) { + if (!first && (*block < rgd->ri.ri_data0)) { log_err("next_rg_meta: Start block is outside rgrp bounds.\n"); exit(1); } - for(i=0; i < length; i++){ + for (i = 0; i < length; i++){ bits = &rgd->bits[i]; if(blk < bits->bi_len*GFS2_NBBY) break; blk -= bits->bi_len*GFS2_NBBY; } - for(; i < length; i++){ + for (; i < length; i++){ bits = &rgd->bits[i]; blk = gfs2_bitfit((unsigned char *)rgd->bh[i]->b_data + bits->bi_offset, bits->bi_len, blk, @@ -526,7 +526,7 @@ int gfs2_next_rg_meta(struct rgrp_list *rgd, uint64_t *block, int first) } blk=0; } - if(i == length) + if (i == length) return -1; return 0; } @@ -540,7 +540,7 @@ int gfs2_next_rg_meta(struct rgrp_list *rgd, uint64_t *block, int first) * * Returns: 0 on success, -1 on error or finished */ -int gfs2_next_rg_metatype(struct gfs2_sbd *sdp, struct rgrp_list *rgd, +int gfs2_next_rg_metatype(struct gfs2_sbd *sdp, struct rgrp_tree *rgd, uint64_t *block, uint32_t type, int first) { struct gfs2_buffer_head *bh = NULL; diff --git a/gfs2/libgfs2/super.c b/gfs2/libgfs2/super.c index 51a8047..3a51eb4 100644 --- a/gfs2/libgfs2/super.c +++ b/gfs2/libgfs2/super.c @@ -144,12 +144,12 @@ int rindex_read(struct gfs2_sbd *sdp, int fd, int *count1, int *sane) unsigned int rg; int error; struct gfs2_rindex buf; - struct rgrp_list *rgd, *prev_rgd; + struct gfs2_rindex ri; + struct rgrp_tree *rgd = NULL, *prev_rgd = NULL; uint64_t prev_length = 0;
*sane = 1; *count1 = 0; - prev_rgd = NULL; if (!fd && sdp->md.riinode->i_di.di_size % sizeof(struct gfs2_rindex)) *sane = 0; /* rindex file size must be a multiple of 96 */ for (rg = 0; ; rg++) { @@ -164,15 +164,9 @@ int rindex_read(struct gfs2_sbd *sdp, int fd, int *count1, int *sane) if (error != sizeof(struct gfs2_rindex)) return -1;
- rgd = (struct rgrp_list *)malloc(sizeof(struct rgrp_list)); - if (!rgd) { - log_crit("Cannot allocate memory for rindex.\n"); - exit(-1); - } - memset(rgd, 0, sizeof(struct rgrp_list)); - osi_list_add_prev(&rgd->list, &sdp->rglist); - - gfs2_rindex_in(&rgd->ri, (char *)&buf); + gfs2_rindex_in(&ri, (char *)&buf); + rgd = rgrp_insert(&sdp->rgtree, ri.ri_addr); + memcpy(&rgd->ri, &ri, sizeof(struct gfs2_rindex));
rgd->start = rgd->ri.ri_addr; if (prev_rgd) { @@ -219,17 +213,18 @@ int rindex_read(struct gfs2_sbd *sdp, int fd, int *count1, int *sane) */ int ri_update(struct gfs2_sbd *sdp, int fd, int *rgcount, int *sane) { - struct rgrp_list *rgd; + struct rgrp_tree *rgd; struct gfs2_rindex *ri; - osi_list_t *tmp; int count1 = 0, count2 = 0; uint64_t errblock = 0; uint64_t rmax = 0; + struct osi_node *n, *next = NULL;
if (rindex_read(sdp, fd, &count1, sane)) - goto fail; - for (tmp = sdp->rglist.next; tmp != &sdp->rglist; tmp = tmp->next) { - rgd = osi_list_entry(tmp, struct rgrp_list, list); + goto fail; + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgd = (struct rgrp_tree *)n; errblock = gfs2_rgrp_read(sdp, rgd); if (errblock) return errblock; @@ -247,7 +242,7 @@ int ri_update(struct gfs2_sbd *sdp, int fd, int *rgcount, int *sane) return 0;
fail: - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree); return -1; }
diff --git a/gfs2/mkfs/main_grow.c b/gfs2/mkfs/main_grow.c index 252bcb2..9aba5da 100644 --- a/gfs2/mkfs/main_grow.c +++ b/gfs2/mkfs/main_grow.c @@ -129,16 +129,13 @@ static void decode_arguments(int argc, char *argv[], struct gfs2_sbd *sdp)
static uint64_t filesystem_size(struct gfs2_sbd *sdp) { - osi_list_t *tmp; - struct rgrp_list *rgl; + struct osi_node *n, *next = NULL; + struct rgrp_tree *rgl; uint64_t size = 0, extent;
- tmp = &sdp->rglist; - for (;;) { - tmp = tmp->next; - if (tmp == &sdp->rglist) - break; - rgl = osi_list_entry(tmp, struct rgrp_list, list); + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); + rgl = (struct rgrp_tree *)n; extent = rgl->ri.ri_addr + rgl->ri.ri_length + rgl->ri.ri_data; if (extent > size) size = extent; @@ -151,15 +148,19 @@ static uint64_t filesystem_size(struct gfs2_sbd *sdp) */ static void initialize_new_portion(struct gfs2_sbd *sdp, int *old_rg_count) { + struct osi_node *n, *next = NULL; uint64_t rgrp = 0; - osi_list_t *head = &sdp->rglist; + struct rgrp_tree *rl;
*old_rg_count = 0; /* Delete the old RGs from the rglist */ - for (rgrp = 0; !osi_list_empty(head) && - rgrp < (sdp->rgrps - sdp->new_rgrps); rgrp++) { + for (rgrp = 0, n = osi_first(&sdp->rgtree); + n && rgrp < (sdp->rgrps - sdp->new_rgrps); n = next, rgrp++) { + next = osi_next(n); (*old_rg_count)++; - osi_list_del(head->next); + rl = (struct rgrp_tree *)n; + osi_erase(&rl->node, &sdp->rgtree); + free(rl); } /* Build the remaining resource groups */ build_rgrps(sdp, !test); @@ -176,17 +177,19 @@ static void initialize_new_portion(struct gfs2_sbd *sdp, int *old_rg_count) */ static void fix_rindex(struct gfs2_sbd *sdp, int rindex_fd, int old_rg_count) { + struct osi_node *n, *next = NULL; int count, rg; - struct rgrp_list *rl; + struct rgrp_tree *rl; char *buf, *bufptr; - osi_list_t *tmp; ssize_t writelen; struct stat statbuf;
/* Count the number of new RGs. */ rg = 0; - osi_list_foreach(tmp, &sdp->rglist) + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); rg++; + } log_info( _("%d new rindex entries.\n"), rg); writelen = rg * sizeof(struct gfs2_rindex); zalloc(buf, writelen); @@ -196,13 +199,14 @@ static void fix_rindex(struct gfs2_sbd *sdp, int rindex_fd, int old_rg_count) /* need to use the gfs2 kernel code rather than the libgfs2 */ /* code so we have a live update while mounted. */ bufptr = buf; - osi_list_foreach(tmp, &sdp->rglist) { + for (n = osi_first(&sdp->rgtree); n; n = next) { + next = osi_next(n); rg++; - rl = osi_list_entry(tmp, struct rgrp_list, list); + rl = (struct rgrp_tree *)n; gfs2_rindex_out(&rl->ri, bufptr); bufptr += sizeof(struct gfs2_rindex); } - gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree); fsync(sdp->device_fd); if (!test) { if (fstat(rindex_fd, &statbuf) != 0) { @@ -284,7 +288,6 @@ main_grow(int argc, char *argv[]) struct gfs2_sbd sbd, *sdp = &sbd; int rgcount, rindex_fd; char rindex_name[PATH_MAX]; - osi_list_t *head = &sdp->rglist;
memset(sdp, 0, sizeof(struct gfs2_sbd)); sdp->bsize = GFS2_DEFAULT_BSIZE; @@ -296,7 +299,7 @@ main_grow(int argc, char *argv[]) while ((argc - optind) > 0) { int sane; - struct rgrp_list *last_rgrp; + struct rgrp_tree *last_rgrp;
sdp->path_name = argv[optind++]; sdp->path_fd = open(sdp->path_name, O_RDONLY); @@ -312,7 +315,8 @@ main_grow(int argc, char *argv[]) sdp->device_name, strerror(errno)); device_geometry(sdp); log_info( _("Initializing lists...\n")); - osi_list_init(&sdp->rglist); + sdp->rgtree.osi_node = NULL; + sdp->rgcalc.osi_node = NULL;
sdp->sd_sb.sb_bsize = GFS2_DEFAULT_BSIZE; sdp->bsize = sdp->sd_sb.sb_bsize; @@ -340,11 +344,11 @@ main_grow(int argc, char *argv[]) /* the existing RGs, and only write to the index at EOF. */ ri_update(sdp, rindex_fd, &rgcount, &sane); fssize = filesystem_size(sdp); - if (osi_list_empty(head)) { + if (!sdp->rgtree.osi_node) { log_err(_("Error: No resource groups found.\n")); goto out; } - last_rgrp = osi_list_entry(head->prev, struct rgrp_list, list); + last_rgrp = (struct rgrp_tree *)osi_last(&sdp->rgtree); sdp->rgsize = GFS2_DEFAULT_RGSIZE; rgsize = rgrp_size(last_rgrp); fsgrowth = ((sdp->device.length - fssize) * sdp->bsize); @@ -359,15 +363,14 @@ main_grow(int argc, char *argv[]) else { int old_rg_count;
- compute_rgrp_layout(sdp, TRUE); + compute_rgrp_layout(sdp, &sdp->rgtree, TRUE); print_info(sdp); initialize_new_portion(sdp, &old_rg_count); fix_rindex(sdp, rindex_fd, old_rg_count); } out: /* Delete the remaining RGs from the rglist */ - while (!osi_list_empty(head)) - osi_list_del(head->next); + gfs2_rgrp_free(&sdp->rgtree); close(rindex_fd); cleanup_metafs(sdp); close(sdp->device_fd); diff --git a/gfs2/mkfs/main_mkfs.c b/gfs2/mkfs/main_mkfs.c index bfe6c45..a2ed1be 100644 --- a/gfs2/mkfs/main_mkfs.c +++ b/gfs2/mkfs/main_mkfs.c @@ -361,7 +361,7 @@ main_mkfs(int argc, char *argv[]) sdp->qcsize = GFS2_DEFAULT_QCSIZE; strcpy(sdp->lockproto, GFS2_DEFAULT_LOCKPROTO); sdp->time = time(NULL); - osi_list_init(&sdp->rglist); + sdp->rgtree.osi_node = NULL;
decode_arguments(argc, argv, sdp); if (sdp->rgsize == -1) /* if rg size not specified */ @@ -408,7 +408,7 @@ main_mkfs(int argc, char *argv[])
/* Compute the resource group layouts */
- compute_rgrp_layout(sdp, rgsize_specified); + compute_rgrp_layout(sdp, &sdp->rgtree, rgsize_specified);
/* Generate a random uuid */ get_random_bytes(uuid, sizeof(uuid)); @@ -438,7 +438,7 @@ main_mkfs(int argc, char *argv[]) inode_put(&sdp->md.inum); inode_put(&sdp->md.statfs);
- gfs2_rgrp_free(&sdp->rglist); + gfs2_rgrp_free(&sdp->rgtree); error = fsync(sdp->device_fd); if (error) die( _("can't fsync device (%d): %s\n"), diff --git a/gfs2/tool/df.c b/gfs2/tool/df.c index 26299ff..c4a6d93 100644 --- a/gfs2/tool/df.c +++ b/gfs2/tool/df.c @@ -112,7 +112,7 @@ do_df_one(char *path) sbd.rgsize = GFS2_DEFAULT_RGSIZE; sbd.utsize = GFS2_DEFAULT_UTSIZE; sbd.qcsize = GFS2_DEFAULT_QCSIZE; - osi_list_init(&sbd.rglist); + sbd.rgtree.osi_node = NULL;
do_lseek(sbd.device_fd, 0x10 * sbd.bsize); do_read(sbd.device_fd, buf, sbd.bsize); /* read in the superblock */