From 850d05e9aa405497e57c72090b9561af98b1b661 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Thu, 25 Jul 2002 00:00:08 -0400 Subject: [PATCH] Add e2fsck -D option which optimizes/compresses directories. General cleanup of rehash code. (Fixed a few bugs, reformatted code to make it more maintainable, etc.) --- e2fsck/ChangeLog | 25 +++ e2fsck/e2fsck.8.in | 7 + e2fsck/e2fsck.c | 2 + e2fsck/e2fsck.h | 8 + e2fsck/pass3.c | 52 +++--- e2fsck/problem.c | 24 +-- e2fsck/problem.h | 14 +- e2fsck/rehash.c | 453 ++++++++++++++++++++++++++++----------------- e2fsck/unix.c | 13 +- tests/f_h_badnode/expect.1 | 4 +- tests/f_h_badroot/expect.1 | 4 +- 11 files changed, 388 insertions(+), 218 deletions(-) diff --git a/e2fsck/ChangeLog b/e2fsck/ChangeLog index b7ad3f3..5aaff7b 100644 --- a/e2fsck/ChangeLog +++ b/e2fsck/ChangeLog @@ -1,5 +1,30 @@ 2002-07-24 Theodore Ts'o + * e2fsck.8.in, e2fsck.h, pass3.c (e2fsck_pass3), unix.c, rehash.c: + Add new option -D, which requests e2fsck to optimize all + directories. Rehash.c will also compress and sort + non-indexed directories. + + * problem.c, problem.h: Rename PR_3A_REHASH_* to PR_3A_OPTIMIZE_* + + * unix.c (PRS): Make sure the signal_cancel is registered without + SA_RESTART. + + * rehash.c (e2fsck_rehash_dir, copy_dir_entries, calculate_tree): + Restructured code in e2fsck_rehash_dir into two new + subroutines to make the code more understandable/maintainable. + (set_root_node): Fixed bug which caused the root node to + be invalid on non-FILETYPE filesystems due to an + unitialized variable. + (calculate_tree): Fix bug where pointers which might get + invalidated if realloc() moves outdir->buf around. + (e2fsck_rehash_dir): Fix memory leak bug. + + * pass3.c (e2fsck_get_lost_and_found), e2fsck.h, e2fsck.c: + Exported as a public interface a function for finding the + lost and found directory. Cache the location of the lost + and found directory in the e2fsck context structure. + * util.c (ask_yn, read_a_char): Note when the user has typed ^C, and abort processing by longjmp'ing to ctx->abort_loc. diff --git a/e2fsck/e2fsck.8.in b/e2fsck/e2fsck.8.in index 57383f7..8438a30 100644 --- a/e2fsck/e2fsck.8.in +++ b/e2fsck/e2fsck.8.in @@ -115,6 +115,13 @@ that e2fsck is running on a video console or terminal. Print debugging output (useless unless you are debugging .BR e2fsck ). .TP +.B \-D +Optimize directories in filesystem. This option causes e2fsck to +try to optimize all directories, either by reindexing them if the +filesystem supports directory indexing, or by sorting and compressing +directories for smaller directories, or for filesystems using +traditional linear directories. +.TP .B \-f Force checking even if the file system seems clean. .TP diff --git a/e2fsck/e2fsck.c b/e2fsck/e2fsck.c index 7356f32..e9ccbb4 100644 --- a/e2fsck/e2fsck.c +++ b/e2fsck/e2fsck.c @@ -42,6 +42,8 @@ errcode_t e2fsck_allocate_context(e2fsck_t *ret) errcode_t e2fsck_reset_context(e2fsck_t ctx) { ctx->flags = 0; + ctx->lost_and_found = 0; + ctx->bad_lost_and_found = 0; if (ctx->inode_used_map) { ext2fs_free_inode_bitmap(ctx->inode_used_map); ctx->inode_used_map = 0; diff --git a/e2fsck/e2fsck.h b/e2fsck/e2fsck.h index c35bf68..c2dbc26 100644 --- a/e2fsck/e2fsck.h +++ b/e2fsck/e2fsck.h @@ -138,6 +138,7 @@ struct resource_track { #define E2F_OPT_DEBUG 0x0080 #define E2F_OPT_FORCE 0x0100 #define E2F_OPT_WRITECHECK 0x0200 +#define E2F_OPT_COMPRESS_DIRS 0x0400 /* * E2fsck flags @@ -236,6 +237,12 @@ struct e2fsck_struct { struct ext2_inode *stashed_inode; /* + * Location of the lost and found directory + */ + ext2_ino_t lost_and_found; + int bad_lost_and_found; + + /* * Directory information */ int dir_info_count; @@ -387,6 +394,7 @@ extern int e2fsck_process_bad_inode(e2fsck_t ctx, ext2_ino_t dir, extern int e2fsck_reconnect_file(e2fsck_t ctx, ext2_ino_t inode); extern errcode_t e2fsck_expand_directory(e2fsck_t ctx, ext2_ino_t dir, int num, int gauranteed_size); +extern ext2_ino_t e2fsck_get_lost_and_found(e2fsck_t ctx, int fix); /* region.c */ diff --git a/e2fsck/pass3.c b/e2fsck/pass3.c index 4b1f397..167add8 100644 --- a/e2fsck/pass3.c +++ b/e2fsck/pass3.c @@ -44,13 +44,9 @@ static void check_root(e2fsck_t ctx); static int check_directory(e2fsck_t ctx, struct dir_info *dir, struct problem_context *pctx); -static ext2_ino_t get_lost_and_found(e2fsck_t ctx); static void fix_dotdot(e2fsck_t ctx, struct dir_info *dir, ext2_ino_t parent); static errcode_t adjust_inode_count(e2fsck_t ctx, ext2_ino_t ino, int adj); -static ext2_ino_t lost_and_found = 0; -static int bad_lost_and_found = 0; - static ext2fs_inode_bitmap inode_loop_detect = 0; static ext2fs_inode_bitmap inode_done_map = 0; @@ -123,8 +119,14 @@ void e2fsck_pass3(e2fsck_t ctx) * Force the creation of /lost+found if not present */ if ((ctx->flags & E2F_OPT_READONLY) == 0) - get_lost_and_found(ctx); + e2fsck_get_lost_and_found(ctx, 1); + /* + * If there are any directories that need to be indexed or + * optimized, do it here. + */ + e2fsck_rehash_directories(ctx); + abort_exit: e2fsck_free_dir_info(ctx); if (inode_loop_detect) { @@ -136,10 +138,6 @@ abort_exit: inode_done_map = 0; } - /* If there are any directories that need to be indexed, do it here. */ - if (ctx->dirs_to_hash) - e2fsck_rehash_directories(ctx); - #ifdef RESOURCE_TRACK if (ctx->options & E2F_OPT_TIME2) { e2fsck_clear_progbar(ctx); @@ -308,8 +306,8 @@ static int check_directory(e2fsck_t ctx, struct dir_info *dir, if (e2fsck_reconnect_file(ctx, p->ino)) ext2fs_unmark_valid(fs); else { - p->parent = lost_and_found; - fix_dotdot(ctx, p, lost_and_found); + p->parent = ctx->lost_and_found; + fix_dotdot(ctx, p, ctx->lost_and_found); } } break; @@ -364,7 +362,7 @@ static int check_directory(e2fsck_t ctx, struct dir_info *dir, * This routine gets the lost_and_found inode, making it a directory * if necessary */ -static ext2_ino_t get_lost_and_found(e2fsck_t ctx) +ext2_ino_t e2fsck_get_lost_and_found(e2fsck_t ctx, int fix) { ext2_filsys fs = ctx->fs; ext2_ino_t ino; @@ -376,14 +374,24 @@ static ext2_ino_t get_lost_and_found(e2fsck_t ctx) struct problem_context pctx; struct dir_info *dirinfo; + if (ctx->lost_and_found) + return ctx->lost_and_found; + clear_problem_context(&pctx); retval = ext2fs_lookup(fs, EXT2_ROOT_INO, name, sizeof(name)-1, 0, &ino); + if (retval && !fix) + return 0; if (!retval) { - if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, ino)) + if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, ino)) { + ctx->lost_and_found = ino; return ino; + } + /* Lost+found isn't a directory! */ + if (!fix) + return 0; pctx.ino = ino; if (!fix_problem(ctx, PR_3_LPF_NOTDIR, &pctx)) return 0; @@ -495,6 +503,7 @@ static ext2_ino_t get_lost_and_found(e2fsck_t ctx) adjust_inode_count(ctx, EXT2_ROOT_INO, 1); ext2fs_icount_store(ctx->inode_count, ino, 2); ext2fs_icount_store(ctx->inode_link_info, ino, 2); + ctx->lost_and_found = ino; #if 0 printf("/lost+found created; inode #%lu\n", ino); #endif @@ -516,12 +525,11 @@ int e2fsck_reconnect_file(e2fsck_t ctx, ext2_ino_t ino) clear_problem_context(&pctx); pctx.ino = ino; - if (!bad_lost_and_found && !lost_and_found) { - lost_and_found = get_lost_and_found(ctx); - if (!lost_and_found) - bad_lost_and_found++; + if (!ctx->bad_lost_and_found && !ctx->lost_and_found) { + if (e2fsck_get_lost_and_found(ctx, 1) == 0) + ctx->bad_lost_and_found++; } - if (bad_lost_and_found) { + if (ctx->bad_lost_and_found) { fix_problem(ctx, PR_3_NO_LPF, &pctx); return 1; } @@ -529,17 +537,19 @@ int e2fsck_reconnect_file(e2fsck_t ctx, ext2_ino_t ino) sprintf(name, "#%u", ino); if (ext2fs_read_inode(fs, ino, &inode) == 0) file_type = ext2_file_type(inode.i_mode); - retval = ext2fs_link(fs, lost_and_found, name, ino, file_type); + retval = ext2fs_link(fs, ctx->lost_and_found, name, ino, file_type); if (retval == EXT2_ET_DIR_NO_SPACE) { if (!fix_problem(ctx, PR_3_EXPAND_LF_DIR, &pctx)) return 1; - retval = e2fsck_expand_directory(ctx, lost_and_found, 1, 0); + retval = e2fsck_expand_directory(ctx, ctx->lost_and_found, + 1, 0); if (retval) { pctx.errcode = retval; fix_problem(ctx, PR_3_CANT_EXPAND_LPF, &pctx); return 1; } - retval = ext2fs_link(fs, lost_and_found, name, ino, file_type); + retval = ext2fs_link(fs, ctx->lost_and_found, name, + ino, file_type); } if (retval) { pctx.errcode = retval; diff --git a/e2fsck/problem.c b/e2fsck/problem.c index ff9714e..07687cd 100644 --- a/e2fsck/problem.c +++ b/e2fsck/problem.c @@ -1173,35 +1173,35 @@ static const struct e2fsck_problem problem_table[] = { N_("/@l is not a @d (ino=%i)\n"), PROMPT_UNLINK, 0 }, - /* Pass 3a (rehashing directory) errors */ + /* Pass 3A Directory Optimization */ - /* Pass 3a: Reindexing directories */ + /* Pass 3A: Optimizing directories */ { PR_3A_PASS_HEADER, - N_("Pass 3a: Reindexing directories\n"), + N_("Pass 3A: Optimizing directories\n"), PROMPT_NONE, PR_PREEN_NOMSG }, /* Error iterating over directories */ - { PR_3A_REHASH_ITER, + { PR_3A_OPTIMIZE_ITER, N_("Failed to create dirs_to_hash iterator: %m"), PROMPT_NONE, 0 }, /* Error rehash directory */ - { PR_3A_REHASH_DIR_ERR, - N_("Failed to rehash directory %q (%d): %m"), + { PR_3A_OPTIMIZE_DIR_ERR, + N_("Failed to optimize directory %q (%d): %m"), PROMPT_NONE, 0 }, /* Rehashing dir header */ - { PR_3A_REHASH_DIR_HEADER, - N_("Rehashing directories: "), + { PR_3A_OPTIMIZE_DIR_HEADER, + N_("Optimizing directories: "), PROMPT_NONE, PR_MSG_ONLY }, /* Rehashing directory %d */ - { PR_3A_REHASH_DIR, + { PR_3A_OPTIMIZE_DIR, " %d", - PROMPT_NONE, PR_LATCH_REHASH_DIR | PR_PREEN_NOHDR}, + PROMPT_NONE, PR_LATCH_OPTIMIZE_DIR | PR_PREEN_NOHDR}, /* Rehashing dir end */ - { PR_3A_REHASH_DIR_END, + { PR_3A_OPTIMIZE_DIR_END, "\n", PROMPT_NONE, PR_PREEN_NOHDR }, @@ -1375,7 +1375,7 @@ static struct latch_descr pr_latch_info[] = { { PR_LATCH_DBLOCK, PR_1B_DUP_BLOCK_HEADER, PR_1B_DUP_BLOCK_END }, { PR_LATCH_LOW_DTIME, PR_1_ORPHAN_LIST_REFUGEES, 0 }, { PR_LATCH_TOOBIG, PR_1_INODE_TOOBIG, 0 }, - { PR_LATCH_REHASH_DIR, PR_3A_REHASH_DIR_HEADER, PR_3A_REHASH_DIR_END }, + { PR_LATCH_OPTIMIZE_DIR, PR_3A_OPTIMIZE_DIR_HEADER, PR_3A_OPTIMIZE_DIR_END }, { -1, 0, 0 }, }; diff --git a/e2fsck/problem.h b/e2fsck/problem.h index 693ecb7..05eba23 100644 --- a/e2fsck/problem.h +++ b/e2fsck/problem.h @@ -37,7 +37,7 @@ struct problem_context { #define PR_LATCH_DBLOCK 0x0060 /* Latch for pass 1b dup block headers */ #define PR_LATCH_LOW_DTIME 0x0070 /* Latch for pass1 orphaned list refugees */ #define PR_LATCH_TOOBIG 0x0080 /* Latch for file to big errors */ -#define PR_LATCH_REHASH_DIR 0x0090 /* Latch for rehashing directories */ +#define PR_LATCH_OPTIMIZE_DIR 0x0090 /* Latch for optimize directories */ #define PR_LATCH(x) ((((x) & PR_LATCH_MASK) >> 4) - 1) @@ -707,20 +707,20 @@ struct problem_context { #define PR_3A_PASS_HEADER 0x031000 /* Error iterating over directories */ -#define PR_3A_REHASH_ITER 0x031001 +#define PR_3A_OPTIMIZE_ITER 0x031001 /* Error rehash directory */ -#define PR_3A_REHASH_DIR_ERR 0x031002 +#define PR_3A_OPTIMIZE_DIR_ERR 0x031002 /* Rehashing dir header */ -#define PR_3A_REHASH_DIR_HEADER 0x031003 +#define PR_3A_OPTIMIZE_DIR_HEADER 0x031003 /* Rehashing directory %d */ -#define PR_3A_REHASH_DIR 0x031004 +#define PR_3A_OPTIMIZE_DIR 0x031004 /* Rehashing dir end */ -#define PR_3A_REHASH_DIR_END 0x031005 - +#define PR_3A_OPTIMIZE_DIR_END 0x031005 + /* * Pass 4 errors */ diff --git a/e2fsck/rehash.c b/e2fsck/rehash.c index 95bb678..2c64ec4 100644 --- a/e2fsck/rehash.c +++ b/e2fsck/rehash.c @@ -57,6 +57,7 @@ struct fill_dir_struct { struct hash_entry *harray; int max_array, num_array; int dir_size; + int compress; ino_t parent; }; @@ -115,14 +116,16 @@ static int fill_dir_block(ext2_filsys fs, fd->err = EXT2_ET_DIR_CORRUPTED; return BLOCK_ABORT; } + dir_offset += dirent->rec_len; if (dirent->inode == 0) - goto next; - if (((dirent->name_len&0xFF) == 1) && (dirent->name[0] == '.')) - goto next; - if (((dirent->name_len&0xFF) == 2) && + continue; + if (!fd->compress && ((dirent->name_len&0xFF) == 1) && + (dirent->name[0] == '.')) + continue; + if (!fd->compress && ((dirent->name_len&0xFF) == 2) && (dirent->name[0] == '.') && (dirent->name[1] == '.')) { fd->parent = dirent->inode; - goto next; + continue; } if (fd->num_array >= fd->max_array) { new_array = realloc(fd->harray, @@ -134,19 +137,20 @@ static int fill_dir_block(ext2_filsys fs, fd->harray = new_array; fd->max_array += 500; } - ent = fd->harray + fd->num_array; + ent = fd->harray + fd->num_array++; ent->dir = dirent; - fd->err = ext2fs_dirhash(fs->super->s_def_hash_version, - dirent->name, - dirent->name_len & 0xFF, - fs->super->s_hash_seed, - &ent->hash, &ent->minor_hash); - if (fd->err) - return BLOCK_ABORT; - fd->num_array++; fd->dir_size += EXT2_DIR_REC_LEN(dirent->name_len & 0xFF); - next: - dir_offset += dirent->rec_len; + if (fd->compress) + ent->hash = ent->minor_hash = 0; + else { + fd->err = ext2fs_dirhash(fs->super->s_def_hash_version, + dirent->name, + dirent->name_len & 0xFF, + fs->super->s_hash_seed, + &ent->hash, &ent->minor_hash); + if (fd->err) + return BLOCK_ABORT; + } } return 0; @@ -174,6 +178,30 @@ static EXT2_QSORT_TYPE hash_cmp(const void *a, const void *b) return ret; } +/* Used for sorting the hash entry */ +static EXT2_QSORT_TYPE name_cmp(const void *a, const void *b) +{ + const struct hash_entry *he_a = (const struct hash_entry *) a; + const struct hash_entry *he_b = (const struct hash_entry *) b; + int ret; + int min_len; + + min_len = he_a->dir->name_len; + if (min_len > he_b->dir->name_len) + min_len = he_b->dir->name_len; + + ret = strncmp(he_a->dir->name, he_b->dir->name, min_len); + if (ret == 0) { + if (he_a->dir->name_len > he_b->dir->name_len) + ret = 1; + else if (he_a->dir->name_len < he_b->dir->name_len) + ret = -1; + else + ret = 0; + } + return ret; +} + static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir, int blocks) { @@ -206,7 +234,7 @@ static void free_out_dir(struct out_dir *outdir) outdir->num =0; } -errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir, +static errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir, char ** ret) { errcode_t retval; @@ -217,17 +245,87 @@ errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir, return retval; } *ret = outdir->buf + (outdir->num++ * fs->blocksize); + memset(*ret, 0, fs->blocksize); return 0; } -struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf, +static errcode_t copy_dir_entries(ext2_filsys fs, + struct fill_dir_struct *fd, + struct out_dir *outdir) +{ + errcode_t retval; + char *block_start; + struct hash_entry *ent; + struct ext2_dir_entry *dirent; + int i, rec_len, left; + ext2_dirhash_t prev_hash; + int offset; + + outdir->max = 0; + retval = alloc_size_dir(fs, outdir, + (fd->dir_size / fs->blocksize) + 2); + if (retval) + return retval; + outdir->num = fd->compress ? 0 : 1; + offset = 0; + outdir->hashes[0] = 0; + prev_hash = 1; + if ((retval = get_next_block(fs, outdir, &block_start))) + return retval; + dirent = (struct ext2_dir_entry *) block_start; + left = fs->blocksize; + for (i=0; i < fd->num_array; i++) { + ent = fd->harray + i; + rec_len = EXT2_DIR_REC_LEN(ent->dir->name_len & 0xFF); + dirent = (struct ext2_dir_entry *) (block_start + offset); + left = fs->blocksize - offset; + if (rec_len > left) { + if (left) { + dirent->rec_len = left; + dirent->inode = 0; + dirent->name_len = 0; + offset += left; + left = 0; + } + if ((retval = get_next_block(fs, outdir, + &block_start))) + return retval; + offset = 0; left = fs->blocksize; + dirent = (struct ext2_dir_entry *) block_start; + } + if (offset == 0) { + if (ent->hash == prev_hash) + outdir->hashes[outdir->num-1] = ent->hash | 1; + else + outdir->hashes[outdir->num-1] = ent->hash; + } + dirent->inode = ent->dir->inode; + dirent->name_len = ent->dir->name_len; + dirent->rec_len = rec_len; + memcpy(dirent->name, ent->dir->name, dirent->name_len & 0xFF); + offset += rec_len; + left -= rec_len; + if (left < 12) { + dirent->rec_len += left; + offset += left; + } + prev_hash = ent->hash; + } + if (left) + dirent->rec_len += left; + + return 0; +} + + +static struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf, ext2_ino_t ino, ext2_ino_t parent) { struct ext2_dir_entry *dir; struct ext2_dx_root_info *root; struct ext2_dx_countlimit *limits; - int filetype; + int filetype = 0; if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_FILETYPE) filetype = EXT2_FT_DIR << 8; @@ -260,7 +358,7 @@ struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf, } -struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf) +static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf) { struct ext2_dir_entry *dir; struct ext2_dx_countlimit *limits; @@ -277,6 +375,84 @@ struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf) return (struct ext2_dx_entry *) limits; } +/* + * This function takes the leaf nodes which have been written in + * outdir, and populates the root node and any necessary interior nodes. + */ +static errcode_t calculate_tree(ext2_filsys fs, + struct out_dir *outdir, + ext2_ino_t ino, + ext2_ino_t parent) +{ + struct ext2_dx_root_info *root_info; + struct ext2_dx_entry *root, *dx_ent = 0; + struct ext2_dx_countlimit *root_limit, *limit; + errcode_t retval; + char * block_start; + int i, c1, c2, nblks; + int limit_offset, root_offset; + + root_info = set_root_node(fs, outdir->buf, ino, parent); + root_offset = limit_offset = ((char *) root_info - outdir->buf) + + root_info->info_length; + root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); + c1 = root_limit->limit; + nblks = outdir->num; + + /* Write out the pointer blocks */ + if (nblks-1 <= c1) { + /* Just write out the root block, and we're done */ + root = (struct ext2_dx_entry *) (outdir->buf + root_offset); + for (i=1; i < nblks; i++) { + root->block = ext2fs_cpu_to_le32(i); + if (i != 1) + root->hash = + ext2fs_cpu_to_le32(outdir->hashes[i]); + root++; + c1--; + } + } else { + c2 = 0; + limit = 0; + root_info->indirect_levels = 1; + for (i=1; i < nblks; i++) { + if (c1 == 0) + return ENOSPC; + if (c2 == 0) { + if (limit) + limit->limit = limit->count = + ext2fs_cpu_to_le16(limit->limit); + root = (struct ext2_dx_entry *) + (outdir->buf + root_offset); + root->block = ext2fs_cpu_to_le32(outdir->num); + if (i != 1) + root->hash = + ext2fs_cpu_to_le32(outdir->hashes[i]); + if ((retval = get_next_block(fs, outdir, + &block_start))) + return retval; + dx_ent = set_int_node(fs, block_start); + limit = (struct ext2_dx_countlimit *) dx_ent; + c2 = limit->limit; + root_offset += sizeof(struct ext2_dx_entry); + c1--; + } + dx_ent->block = ext2fs_cpu_to_le32(i); + if (c2 != limit->limit) + dx_ent->hash = + ext2fs_cpu_to_le32(outdir->hashes[i]); + dx_ent++; + c2--; + } + limit->count = ext2fs_cpu_to_le16(limit->limit - c2); + limit->limit = ext2fs_cpu_to_le16(limit->limit); + } + root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset); + root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1); + root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit); + + return 0; +} struct write_dir_struct { struct out_dir *outdir; @@ -286,8 +462,7 @@ struct write_dir_struct { }; /* - * This makes sure we have enough space to write out the modified - * directory. + * Helper function which writes out a directory block. */ static int write_dir_block(ext2_filsys fs, blk_t *block_nr, @@ -297,9 +472,8 @@ static int write_dir_block(ext2_filsys fs, void *priv_data) { struct write_dir_struct *wd = (struct write_dir_struct *) priv_data; - blk_t new_blk, blk; + blk_t blk; char *dir; - errcode_t retval; if (*block_nr == 0) return 0; @@ -322,9 +496,9 @@ static int write_dir_block(ext2_filsys fs, return 0; } - static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs, - struct out_dir *outdir, ext2_ino_t ino) + struct out_dir *outdir, + ext2_ino_t ino, int compress) { struct write_dir_struct wd; errcode_t retval; @@ -347,7 +521,8 @@ static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs, return wd.err; e2fsck_read_inode(ctx, ino, &inode, "rehash_dir"); - inode.i_flags |= EXT2_INDEX_FL; + if (!compress) + inode.i_flags |= EXT2_INDEX_FL; inode.i_size = outdir->num * fs->blocksize; inode.i_blocks -= (fs->blocksize / 512) * wd.cleared; e2fsck_write_inode(ctx, ino, &inode, "rehash_dir"); @@ -360,22 +535,11 @@ errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino) ext2_filsys fs = ctx->fs; errcode_t retval; struct ext2_inode inode; - char *dir_buf = 0, *block_start; - struct hash_entry *ent; - struct ext2_dir_entry *dirent; + char *dir_buf = 0; struct fill_dir_struct fd; - int i, rec_len, left, c1, c2, nblks; - ext2_dirhash_t prev_hash; - int offset; - void *new_mem; struct out_dir outdir; - struct ext2_dx_root_info *root_info; - struct ext2_dx_entry *root, *dx_ent; - struct ext2_dx_countlimit *root_limit, *limit; e2fsck_read_inode(ctx, ino, &inode, "rehash_dir"); - if ((inode.i_size / fs->blocksize) < 3) - return 0; retval = ENOMEM; fd.harray = 0; @@ -394,6 +558,10 @@ errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino) fd.inode = &inode; fd.err = 0; fd.dir_size = 0; + fd.compress = 0; + if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) || + (inode.i_size / fs->blocksize) < 3) + fd.compress = 1; fd.parent = 0; /* Read in the entire directory into memory */ @@ -409,170 +577,117 @@ errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino) fd.num_array, fd.dir_size, ino); #endif - /* Sort the list into hash order */ - qsort(fd.harray, fd.num_array, sizeof(struct hash_entry), hash_cmp); - - outdir.max = 0; - retval = alloc_size_dir(fs, &outdir, - (fd.dir_size / fs->blocksize) + 2); + /* Sort the list */ + if (fd.compress) + qsort(fd.harray+2, fd.num_array-2, + sizeof(struct hash_entry), name_cmp); + else + qsort(fd.harray, fd.num_array, + sizeof(struct hash_entry), hash_cmp); + + /* + * Copy the directory entries. In a htree directory these + * will become the leaf nodes. + */ + retval = copy_dir_entries(fs, &fd, &outdir); if (retval) goto errout; - outdir.num = 1; offset = 0; - outdir.hashes[0] = 0; - prev_hash = 1; - if ((retval = get_next_block(fs, &outdir, &block_start))) - goto errout; - for (i=0; i < fd.num_array; i++) { - ent = fd.harray + i; - rec_len = EXT2_DIR_REC_LEN(ent->dir->name_len & 0xFF); - dirent = (struct ext2_dir_entry *) (block_start + offset); - left = fs->blocksize - offset; - if (rec_len > left) { - if (left) { - dirent->rec_len = left; - dirent->inode = 0; - dirent->name_len = 0; - offset += left; - left = 0; - } - if ((retval = get_next_block(fs, &outdir, - &block_start))) - goto errout; - offset = 0; left = fs->blocksize; - dirent = (struct ext2_dir_entry *) block_start; - } - if (offset == 0) { - if (ent->hash == prev_hash) - outdir.hashes[outdir.num-1] = ent->hash | 1; - else - outdir.hashes[outdir.num-1] = ent->hash; - } - dirent->inode = ent->dir->inode; - dirent->name_len = ent->dir->name_len; - dirent->rec_len = rec_len; - memcpy(dirent->name, ent->dir->name, dirent->name_len & 0xFF); - offset += rec_len; - left -= rec_len; - if (left < 12) { - dirent->rec_len += left; - offset += left; - } - prev_hash = ent->hash; - } - if (left) - dirent->rec_len += left; + free(dir_buf); dir_buf = 0; - root_info = set_root_node(fs, outdir.buf, ino, fd.parent); - root_limit = (struct ext2_dx_countlimit *) - ((char *)root_info + root_info->info_length); - root = (struct ext2_dx_entry *) root_limit; - c1 = root_limit->limit; - nblks = outdir.num; - - /* Write out the pointer blocks */ - if (nblks-1 <= c1) { - /* Just write out the root block, and we're done */ - for (i=1; i < nblks; i++) { - root->block = ext2fs_cpu_to_le32(i); - if (i != 1) - root->hash = - ext2fs_cpu_to_le32(outdir.hashes[i]); - root++; - c1--; - } - } else { - c2 = 0; - limit = 0; - root_info->indirect_levels = 1; - for (i=1; i < nblks; i++) { - if (c1 == 0) { - retval = ENOSPC; - goto errout; - } - if (c2 == 0) { - if (limit) - limit->limit = limit->count = - ext2fs_cpu_to_le16(limit->limit); - root->block = ext2fs_cpu_to_le32(outdir.num); - if (i != 1) - root->hash = - ext2fs_cpu_to_le32(outdir.hashes[i]); - if ((retval = get_next_block(fs, &outdir, - &block_start))) - goto errout; - dx_ent = set_int_node(fs, block_start); - limit = (struct ext2_dx_countlimit *) dx_ent; - c2 = limit->limit; - root++; - c1--; - } - dx_ent->block = ext2fs_cpu_to_le32(i); - if (c2 != limit->limit) - dx_ent->hash = - ext2fs_cpu_to_le32(outdir.hashes[i]); - dx_ent++; - c2--; - } - limit->count = ext2fs_cpu_to_le16(limit->limit - c2); - limit->limit = ext2fs_cpu_to_le16(limit->limit); + if (!fd.compress) { + /* Calculate the interior nodes */ + retval = calculate_tree(fs, &outdir, ino, fd.parent); + if (retval) + goto errout; } - root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1); - root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit); - - retval = write_directory(ctx, fs, &outdir, ino); + + retval = write_directory(ctx, fs, &outdir, ino, fd.compress); if (retval) goto errout; errout: if (dir_buf) free(dir_buf); + if (fd.harray) + free(fd.harray); + free_out_dir(&outdir); return retval; } void e2fsck_rehash_directories(e2fsck_t ctx) { - errcode_t retval; struct problem_context pctx; - ext2_u32_iterate iter; - ext2_ino_t ino,lpf; - static const char name[] = "lost+found"; - int first = 1; +#ifdef RESOURCE_TRACK + struct resource_track rtrack; +#endif + struct dir_info *dir; + ext2_u32_iterate iter; + ext2_ino_t ino; + errcode_t retval; + int i, all_dirs, dir_index, first = 1; + +#ifdef RESOURCE_TRACK + init_resource_track(&rtrack); +#endif - if (!ctx->dirs_to_hash) + all_dirs = ctx->options & E2F_OPT_COMPRESS_DIRS; + + if (!ctx->dirs_to_hash && !all_dirs) return; - retval = ext2fs_lookup(ctx->fs, EXT2_ROOT_INO, name, - sizeof(name)-1, 0, &lpf); - if (retval) - lpf = 0; + e2fsck_get_lost_and_found(ctx, 0); clear_problem_context(&pctx); - retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash, &iter); - if (retval) { - pctx.errcode = retval; - fix_problem(ctx, PR_3A_REHASH_ITER, &pctx); - return; + + dir_index = ctx->fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX; + if (all_dirs) + i = 0; + else { + retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash, + &iter); + if (retval) { + pctx.errcode = retval; + fix_problem(ctx, PR_3A_OPTIMIZE_ITER, &pctx); + return; + } } - while (ext2fs_u32_list_iterate(iter, &ino)) { - if (ino == lpf) + while (1) { + if (all_dirs) { + if ((dir = e2fsck_dir_info_iter(ctx, &i)) == 0) + break; + ino = dir->ino; + } else { + if (!ext2fs_u32_list_iterate(iter, &ino)) + break; + } + if (ino == ctx->lost_and_found) continue; pctx.dir = ino; if (first) { fix_problem(ctx, PR_3A_PASS_HEADER, &pctx); first = 0; } - fix_problem(ctx, PR_3A_REHASH_DIR, &pctx); + fix_problem(ctx, PR_3A_OPTIMIZE_DIR, &pctx); pctx.errcode = e2fsck_rehash_dir(ctx, ino); if (pctx.errcode) { - end_problem_latch(ctx, PR_LATCH_REHASH_DIR); - fix_problem(ctx, PR_3A_REHASH_DIR_ERR, &pctx); + end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); + fix_problem(ctx, PR_3A_OPTIMIZE_DIR_ERR, &pctx); } } - end_problem_latch(ctx, PR_LATCH_REHASH_DIR); - ext2fs_u32_list_iterate_end(iter); + end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR); + if (!all_dirs) + ext2fs_u32_list_iterate_end(iter); - ext2fs_u32_list_free(ctx->dirs_to_hash); + if (ctx->dirs_to_hash) + ext2fs_u32_list_free(ctx->dirs_to_hash); ctx->dirs_to_hash = 0; + +#ifdef RESOURCE_TRACK + if (ctx->options & E2F_OPT_TIME2) { + e2fsck_clear_progbar(ctx); + print_resource_track("Pass 3A", &rtrack); + } +#endif } diff --git a/e2fsck/unix.c b/e2fsck/unix.c index 7fca08c..fab82a2 100644 --- a/e2fsck/unix.c +++ b/e2fsck/unix.c @@ -475,7 +475,7 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx) ctx->program_name = *argv; else ctx->program_name = "e2fsck"; - while ((c = getopt (argc, argv, "panyrcC:B:dfvtFVM:b:I:j:P:l:L:N:Ss")) != EOF) + while ((c = getopt (argc, argv, "panyrcC:B:dfvtFVM:b:I:j:P:l:L:N:SsD")) != EOF) switch (c) { case 'C': ctx->progress = e2fsck_update_progress; @@ -494,6 +494,9 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx) } else close(fd); break; + case 'D': + ctx->options |= E2F_OPT_COMPRESS_DIRS; + break; case 'p': case 'a': ctx->options |= E2F_OPT_PREEN; @@ -596,7 +599,7 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx) if (optind != argc - 1) usage(ctx); if ((ctx->options & E2F_OPT_NO) && !bad_blocks_file && - !cflag && !swapfs) + !cflag && !swapfs && !(ctx->options & E2F_OPT_COMPRESS_DIRS)) ctx->options |= E2F_OPT_READONLY; ctx->filesystem_name = argv[optind]; if (flush) { @@ -634,6 +637,9 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx) * Set up signal action */ memset(&sa, 0, sizeof(struct sigaction)); + sa.sa_handler = signal_cancel; + sigaction(SIGINT, &sa, 0); + sigaction(SIGTERM, &sa, 0); #ifdef SA_RESTART sa.sa_flags = SA_RESTART; #endif @@ -642,9 +648,6 @@ static errcode_t PRS(int argc, char *argv[], e2fsck_t *ret_ctx) sigaction(SIGUSR1, &sa, 0); sa.sa_handler = signal_progress_off; sigaction(SIGUSR2, &sa, 0); - sa.sa_handler = signal_cancel; - sigaction(SIGINT, &sa, 0); - sigaction(SIGTERM, &sa, 0); #endif /* Update our PATH to include /sbin if we need to run badblocks */ diff --git a/tests/f_h_badnode/expect.1 b/tests/f_h_badnode/expect.1 index a0a13f0..6c8ae82 100644 --- a/tests/f_h_badnode/expect.1 +++ b/tests/f_h_badnode/expect.1 @@ -8,8 +8,8 @@ Problem in HTREE directory inode 12929: node (1062) not referenced Invalid HTREE directory inode 12929 (/test2). Clear? yes Pass 3: Checking directory connectivity -Pass 3a: Reindexing directories -Rehashing directories: 12929 +Pass 3A: Optimizing directories +Optimizing directories: 12929 Pass 4: Checking reference counts Pass 5: Checking group summary information diff --git a/tests/f_h_badroot/expect.1 b/tests/f_h_badroot/expect.1 index 73b5b1b..6f6221b 100644 --- a/tests/f_h_badroot/expect.1 +++ b/tests/f_h_badroot/expect.1 @@ -25,8 +25,8 @@ Problem in HTREE directory inode 80065: node (21) has bad max hash Invalid HTREE directory inode 80065 (/test7). Clear? yes Pass 3: Checking directory connectivity -Pass 3a: Reindexing directories -Rehashing directories: 13345 26689 40033 53377 66721 73393 80065 +Pass 3A: Optimizing directories +Optimizing directories: 13345 26689 40033 53377 66721 73393 80065 Pass 4: Checking reference counts Pass 5: Checking group summary information -- 1.8.3.1