Add support to e2fsck to reindex directories to use hash trees.

11 files changed, 732 insertions, 23 deletions

diff --git a/e2fsck/ChangeLog b/e2fsck/ChangeLog
index da1d2c9e..aaf77636 100644
--- a/e2fsck/ChangeLog
+++ b/e2fsck/ChangeLog
@@ -1,3 +1,39 @@
+2002-07-19  Theodore Ts'o  <tytso@mit.edu>
+
+	* rehash.c, Makefile.in: New file which rewrites directories using
+		the htree format.
+	
+	* problem.c (fix_problem), problemP.h (PR_PREEN_NOHDR): Add option
+		which suppresses the header printed when in preen mode.
+
+	* pass3.c (e2fsck_pass3): If there are entries on the dirs_to_hash
+		list, call e2fsck_rehash_directories to reindex those
+		directories.
+		(e2fsck_expand_directory): Generalize the old
+		expand_dirctory() function so it can expand a directory to
+		a guaranteed minimum size. 
+
+	* e2fsck.h (struct e2fsck_struct): Add the dirs_to_hash list.  Add
+		new function prototypes for rehash.c and for
+		e2fsck_expand_directory().
+	
+	* e2fsck.c (e2fsck_reset_context): Free the dirs_to_hash list.
+
+	* pass1.c (e2fsck_pass1): Initialize the dirs_to_hash list if the
+		htree feature is present in the filesystem.
+		(check_blocks): If a non-htree directory has more than 2
+		blocks, put it on the dirs_to_hash list.
+
+	* pass2.c (clear_htree): Add corrupt htree directories to the
+		dirs_to_hash list.
+
+	* problem.h, problem.c (PR_3A_PASS_HEADER, PR_3A_REHASH_ITER, 
+		PR_3A_REHASH_DIR_ERR, PR_3A_REHASH_DIR_HEADER,
+		PR_3A_REHASH_DIR, PR_3A_REHASH_DIR_END): Add new problem codes
+
+	* pass2.c (parse_int_node), problem.c (PR_2_HTREE_BADBLK): Fix
+		problem display.
+	
 2002-07-15  Theodore Ts'o  <tytso@mit.edu>
 
 	* pass2.c (e2fsck_pass2): Use dx_dir->numblocks instead of
diff --git a/e2fsck/Makefile.in b/e2fsck/Makefile.in
index 51c08212..44732803 100644
--- a/e2fsck/Makefile.in
+++ b/e2fsck/Makefile.in
@@ -57,7 +57,7 @@ PROFILED_DEPLIBS= $(PROFILED_LIBEXT2FS) $(PROFILED_LIBCOM_ERR) \
 OBJS= unix.o e2fsck.o super.o pass1.o pass1b.o pass2.o pass3.o pass4.o \
 	pass5.o journal.o swapfs.o badblocks.o util.o dirinfo.o dx_dirinfo.o \
 	ehandler.o problem.o message.o recovery.o region.o revoke.o \
-	ea_refcount.o $(MTRACE_OBJ)
+	ea_refcount.o rehash.o $(MTRACE_OBJ)
 
 PROFILED_OBJS= profiled/unix.o profiled/e2fsck.o profiled/super.o \
 	profiled/pass1.o profiled/pass1b.o \
@@ -66,7 +66,7 @@ PROFILED_OBJS= profiled/unix.o profiled/e2fsck.o profiled/super.o \
 	profiled/dirinfo.o profiled/dx_dirinfo.o profiled/ehandler.o \
 	profiled/message.o profiled/problem.o profiled/swapfs.o \
 	profiled/recovery.o profiled/region.o profiled/revoke.o \
-	profiled/ea_refcount.o
+	profiled/ea_refcount.o profiled/rehash.o
 
 SRCS= $(srcdir)/e2fsck.c \
 	$(srcdir)/super.c \
@@ -89,6 +89,7 @@ SRCS= $(srcdir)/e2fsck.c \
 	$(srcdir)/message.c \
 	$(srcdir)/swapfs.c \
 	$(srcdir)/ea_refcount.c \
+	$(srcdir)/rehash.c \
 	$(srcdir)/region.c \
 	$(MTRACE_SRC)
 
diff --git a/e2fsck/e2fsck.c b/e2fsck/e2fsck.c
index 0abae190..7356f326 100644
--- a/e2fsck/e2fsck.c
+++ b/e2fsck/e2fsck.c
@@ -103,6 +103,10 @@ errcode_t e2fsck_reset_context(e2fsck_t ctx)
 		ext2fs_free_inode_bitmap(ctx->inode_imagic_map);
 		ctx->inode_imagic_map = 0;
 	}
+	if (ctx->dirs_to_hash) {
+		ext2fs_u32_list_free(ctx->dirs_to_hash);
+		ctx->dirs_to_hash = 0;
+	}
 
 	/*
 	 * Clear the array of invalid meta-data flags
diff --git a/e2fsck/e2fsck.h b/e2fsck/e2fsck.h
index 49097fe6..d68b79c1 100644
--- a/e2fsck/e2fsck.h
+++ b/e2fsck/e2fsck.h
@@ -249,6 +249,11 @@ struct e2fsck_struct {
 	struct dx_dir_info *dx_dir_info;
 
 	/*
+	 * Directories to hash
+	 */
+	ext2_u32_list	dirs_to_hash;
+
+	/*
 	 * Tuning parameters
 	 */
 	int process_inode_size;
@@ -379,12 +384,19 @@ extern int e2fsck_process_bad_inode(e2fsck_t ctx, ext2_ino_t dir,
 
 /* pass3.c */
 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);
+
 
 /* region.c */
 extern region_t region_create(region_addr_t min, region_addr_t max);
 extern void region_free(region_t region);
 extern int region_allocate(region_t region, region_addr_t start, int n);
 
+/* rehash.c */
+errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino);
+void e2fsck_rehash_directories(e2fsck_t ctx);
+
 /* super.c */
 void check_super_block(e2fsck_t ctx);
 errcode_t e2fsck_get_device_size(e2fsck_t ctx);
diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index 8bc35a2c..bc4ac26a 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -277,6 +277,11 @@ void e2fsck_pass1(e2fsck_t ctx)
 	if (!(ctx->options & E2F_OPT_PREEN))
 		fix_problem(ctx, PR_1_PASS_HEADER, &pctx);
 
+	if (fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) {
+		if (ext2fs_u32_list_create(&ctx->dirs_to_hash, 50))
+			ctx->dirs_to_hash = 0;
+	}
+
 #ifdef MTRACE
 	mtrace_print("Pass 1");
 #endif
@@ -1269,7 +1274,11 @@ static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
 #endif
 		}
 	}
-	
+	if (ctx->dirs_to_hash && pb.is_dir &&
+	    !(inode->i_flags & EXT2_INDEX_FL) &&
+	    ((inode->i_size / fs->blocksize) >= 3))
+		ext2fs_u32_list_add(ctx->dirs_to_hash, ino);
+		
 	if (inode->i_file_acl && check_ext_attr(ctx, pctx, block_buf))
 		pb.num_blocks++;
 
diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
index d730765b..db23c88e 100644
--- a/e2fsck/pass2.c
+++ b/e2fsck/pass2.c
@@ -500,6 +500,7 @@ static void parse_int_node(ext2_filsys fs,
 		blk = ent[i].block & 0x0ffffff;
 		/* Check to make sure the block is valid */
 		if (blk > dx_dir->numblocks) {
+			cd->pctx.blk = blk;
 			if (fix_problem(cd->ctx, PR_2_HTREE_BADBLK,
 					&cd->pctx)) {
 				clear_htree(cd->ctx, cd->pctx.ino);
@@ -838,6 +839,7 @@ static int check_dir_block(ext2_filsys fs,
 		       db->blockcnt, dx_db->type,
 		       dx_db->min_hash, dx_db->max_hash);
 #endif
+		cd->pctx.dir = cd->pctx.ino;
 		if ((dx_db->type == DX_DIRBLOCK_ROOT) ||
 		    (dx_db->type == DX_DIRBLOCK_NODE))
 			parse_int_node(fs, db, cd, dx_dir, buf);
@@ -946,6 +948,8 @@ static void clear_htree(e2fsck_t ctx, ext2_ino_t ino)
 	e2fsck_read_inode(ctx, ino, &inode, "clear_htree");
 	inode.i_flags = inode.i_flags & ~EXT2_INDEX_FL;
 	e2fsck_write_inode(ctx, ino, &inode, "clear_htree");
+	if (ctx->dirs_to_hash)
+		ext2fs_u32_list_add(ctx->dirs_to_hash, ino);
 }
 
 
diff --git a/e2fsck/pass3.c b/e2fsck/pass3.c
index bebd67f2..7fdd8146 100644
--- a/e2fsck/pass3.c
+++ b/e2fsck/pass3.c
@@ -47,7 +47,6 @@ static int check_directory(e2fsck_t ctx, struct dir_info *dir,
 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 errcode_t expand_directory(e2fsck_t ctx, ext2_ino_t dir);
 
 static ext2_ino_t lost_and_found = 0;
 static int bad_lost_and_found = 0;
@@ -135,6 +134,11 @@ abort_exit:
 		ext2fs_free_inode_bitmap(inode_done_map);
 		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);
@@ -353,7 +357,7 @@ static int check_directory(e2fsck_t ctx, struct dir_info *dir,
 			fix_dotdot(ctx, dir, dir->parent);
 	}
 	return 0;
-}	
+}
 
 /*
  * This routine gets the lost_and_found inode, making it a directory
@@ -528,7 +532,7 @@ int e2fsck_reconnect_file(e2fsck_t ctx, ext2_ino_t ino)
 	if (retval == EXT2_ET_DIR_NO_SPACE) {
 		if (!fix_problem(ctx, PR_3_EXPAND_LF_DIR, &pctx))
 			return 1;
-		retval = expand_directory(ctx, lost_and_found);
+		retval = e2fsck_expand_directory(ctx, lost_and_found, 1, 0);
 		if (retval) {
 			pctx.errcode = retval;
 			fix_problem(ctx, PR_3_CANT_EXPAND_LPF, &pctx);
@@ -672,8 +676,10 @@ static void fix_dotdot(e2fsck_t ctx, struct dir_info *dir, ext2_ino_t parent)
  */
 
 struct expand_dir_struct {
-	int			done;
+	int			num;
+	int			guaranteed_size;
 	int			newblocks;
+	int			last_block;
 	errcode_t		err;
 	e2fsck_t		ctx;
 };
@@ -694,6 +700,11 @@ static int expand_dir_proc(ext2_filsys fs,
 
 	ctx = es->ctx;
 	
+	if (es->guaranteed_size && blockcnt >= es->guaranteed_size)
+		return BLOCK_ABORT;
+
+	if (blockcnt > 0)
+		es->last_block = blockcnt;
 	if (*blocknr) {
 		last_blk = *blocknr;
 		return 0;
@@ -710,7 +721,7 @@ static int expand_dir_proc(ext2_filsys fs,
 			es->err = retval;
 			return BLOCK_ABORT;
 		}
-		es->done = 1;
+		es->num--;
 		retval = ext2fs_write_dir_block(fs, new_blk, block);
 	} else {
 		retval = ext2fs_get_mem(fs->blocksize, (void **) &block);
@@ -728,17 +739,17 @@ static int expand_dir_proc(ext2_filsys fs,
 	ext2fs_free_mem((void **) &block);
 	*blocknr = new_blk;
 	ext2fs_mark_block_bitmap(ctx->block_found_map, new_blk);
-	ext2fs_mark_block_bitmap(fs->block_map, new_blk);
-	ext2fs_mark_bb_dirty(fs);
+	ext2fs_block_alloc_stats(fs, new_blk, +1);
 	es->newblocks++;
 	
-	if (es->done)
+	if (es->num == 0)
 		return (BLOCK_CHANGED | BLOCK_ABORT);
 	else
 		return BLOCK_CHANGED;
 }
 
-static errcode_t expand_directory(e2fsck_t ctx, ext2_ino_t dir)
+errcode_t e2fsck_expand_directory(e2fsck_t ctx, ext2_ino_t dir,
+				  int num, int guaranteed_size)
 {
 	ext2_filsys fs = ctx->fs;
 	errcode_t	retval;
@@ -758,7 +769,9 @@ static errcode_t expand_directory(e2fsck_t ctx, ext2_ino_t dir)
 	if (retval)
 		return retval;
 	
-	es.done = 0;
+	es.num = num;
+	es.guaranteed_size = guaranteed_size;
+	es.last_block = 0;
 	es.err = 0;
 	es.newblocks = 0;
 	es.ctx = ctx;
@@ -768,8 +781,6 @@ static errcode_t expand_directory(e2fsck_t ctx, ext2_ino_t dir)
 
 	if (es.err)
 		return es.err;
-	if (!es.done)
-		return EXT2_ET_EXPAND_DIR_ERR;
 
 	/*
 	 * Update the size and block count fields in the inode.
@@ -778,10 +789,11 @@ static errcode_t expand_directory(e2fsck_t ctx, ext2_ino_t dir)
 	if (retval)
 		return retval;
 	
-	inode.i_size += fs->blocksize;
+	inode.i_size = (es.last_block + 1) * fs->blocksize;
 	inode.i_blocks += (fs->blocksize / 512) * es.newblocks;
 
 	e2fsck_write_inode(ctx, dir, &inode, "expand_directory");
 
 	return 0;
 }
+
diff --git a/e2fsck/problem.c b/e2fsck/problem.c
index 7f019a76..ff9714e5 100644
--- a/e2fsck/problem.c
+++ b/e2fsck/problem.c
@@ -1048,7 +1048,7 @@ static const struct e2fsck_problem problem_table[] = {
 
 	/* Bad block in htree interior node */
 	{ PR_2_HTREE_BADBLK,
-	  N_("@p @h %d (%q): bad @b number %B.\n"),
+	  N_("@p @h %d (%q): bad @b number %b.\n"),
 	  PROMPT_CLEAR_HTREE, 0 },
 
 	/* Pass 3 errors */
@@ -1171,7 +1171,39 @@ static const struct e2fsck_problem problem_table[] = {
 	/* Lost+found not a directory */
 	{ PR_3_LPF_NOTDIR,
 	  N_("/@l is not a @d (ino=%i)\n"),
-	  PROMPT_UNLINK, 0 }, 
+	  PROMPT_UNLINK, 0 },
+
+	/* Pass 3a (rehashing directory) errors	*/
+
+	/* Pass 3a: Reindexing directories */
+	{ PR_3A_PASS_HEADER,
+	  N_("Pass 3a: Reindexing directories\n"),
+	  PROMPT_NONE, PR_PREEN_NOMSG },
+
+	/* Error iterating over directories */
+	{ PR_3A_REHASH_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"),
+	  PROMPT_NONE, 0 },
+
+	/* Rehashing dir header */
+	{ PR_3A_REHASH_DIR_HEADER,
+	  N_("Rehashing directories: "),
+	  PROMPT_NONE, PR_MSG_ONLY },
+
+	/* Rehashing directory %d */
+	{ PR_3A_REHASH_DIR,
+	  " %d",
+	  PROMPT_NONE, PR_LATCH_REHASH_DIR | PR_PREEN_NOHDR},
+		  
+	/* Rehashing dir end */	  
+	{ PR_3A_REHASH_DIR_END,
+	  "\n",
+	  PROMPT_NONE, PR_PREEN_NOHDR },
 
 	/* Pass 4 errors */
 	
@@ -1343,6 +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 },
 	{ -1, 0, 0 },
 };
 
@@ -1459,13 +1492,10 @@ int fix_problem(e2fsck_t ctx, problem_t code, struct problem_context *pctx)
 		suppress++;
 	if (!suppress) {
 		message = ptr->e2p_description;
-		if (ctx->options & E2F_OPT_PREEN) {
+		if ((ctx->options & E2F_OPT_PREEN) &&
+		    !(ptr->flags & PR_PREEN_NOHDR)) {
 			printf("%s: ", ctx->device_name ?
 			       ctx->device_name : ctx->filesystem_name);
-#if 0
-			if (ptr->e2p_preen_msg)
-				message = ptr->e2p_preen_msg;
-#endif
 		}
 		print_e2fsck_message(ctx, _(message), pctx, 1);
 	}
diff --git a/e2fsck/problem.h b/e2fsck/problem.h
index 91c0bd0c..693ecb76 100644
--- a/e2fsck/problem.h
+++ b/e2fsck/problem.h
@@ -37,6 +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(x)	((((x) & PR_LATCH_MASK) >> 4) - 1)
 
@@ -700,6 +701,27 @@ struct problem_context {
 #define PR_3_LPF_NOTDIR			0x030017
 
 /*
+ * Pass 3a --- rehashing diretories
+ */
+/* Pass 3a: Reindexing directories */
+#define PR_3A_PASS_HEADER		0x031000
+
+/* Error iterating over directories */
+#define PR_3A_REHASH_ITER		0x031001
+
+/* Error rehash directory */
+#define PR_3A_REHASH_DIR_ERR		0x031002		
+
+/* Rehashing dir header */
+#define PR_3A_REHASH_DIR_HEADER		0x031003
+
+/* Rehashing directory %d */
+#define PR_3A_REHASH_DIR		0x031004
+		  
+/* Rehashing dir end */	  
+#define PR_3A_REHASH_DIR_END		0x031005
+	
+/*
  * Pass 4 errors
  */
 
diff --git a/e2fsck/problemP.h b/e2fsck/problemP.h
index cce5511a..329056b9 100644
--- a/e2fsck/problemP.h
+++ b/e2fsck/problemP.h
@@ -38,4 +38,5 @@ struct latch_descr {
 #define PR_NOCOLLATE	0x008000 /* Don't collate answers for this latch */
 #define PR_NO_NOMSG	0x010000 /* Don't print a message if e2fsck -n */
 #define PR_PREEN_NO	0x020000 /* Use No as an answer if preening */
+#define PR_PREEN_NOHDR	0x040000 /* Don't print the preen header */
 
diff --git a/e2fsck/rehash.c b/e2fsck/rehash.c
new file mode 100644
index 00000000..95bb6785
--- /dev/null
+++ b/e2fsck/rehash.c
@@ -0,0 +1,578 @@
+/*
+ * rehash.c --- rebuild hash tree directories
+ * 
+ * Copyright (C) 2002 Theodore Ts'o
+ *
+ * %Begin-Header%
+ * This file may be redistributed under the terms of the GNU Public
+ * License.
+ * %End-Header%
+ * 
+ * This algorithm is designed for simplicity of implementation and to
+ * pack the directory as much as possible.  It however requires twice
+ * as much memory as the size of the directory.  The maximum size
+ * directory supported using a 4k blocksize is roughly a gigabyte, and
+ * so there may very well be problems with machines that don't have
+ * virtual memory, and obscenely large directories.
+ *
+ * An alternate algorithm which is much more disk intensive could be
+ * written, and probably will need to be written in the future.  The
+ * design goals of such an algorithm are: (a) use (roughly) constant
+ * amounts of memory, no matter how large the directory, (b) the
+ * directory must be safe at all times, even if e2fsck is interrupted
+ * in the middle, (c) we must use minimal amounts of extra disk
+ * blocks.  This pretty much requires an incremental approach, where
+ * we are reading from one part of the directory, and inserting into
+ * the front half.  So the algorithm will have to keep track of a
+ * moving block boundary between the new tree and the old tree, and
+ * files will need to be moved from the old directory and inserted
+ * into the new tree.  If the new directory requires space which isn't
+ * yet available, blocks from the beginning part of the old directory
+ * may need to be moved to the end of the directory to make room for
+ * the new tree:
+ *
+ *    --------------------------------------------------------
+ *    |  new tree   |        | old tree                      |
+ *    --------------------------------------------------------
+ *                  ^ ptr    ^ptr
+ *                tail new   head old
+ * 
+ * This is going to be a pain in the tuckus to implement, and will
+ * require a lot more disk accesses.  So I'm going to skip it for now;
+ * it's only really going to be an issue for really, really big
+ * filesystems (when we reach the level of tens of millions of files
+ * in a single directory).  It will probably be easier to simply
+ * require that e2fsck use VM first.
+ */
+
+#include <errno.h>
+#include "e2fsck.h"
+#include "problem.h"
+
+struct fill_dir_struct {
+	char *buf;
+	struct ext2_inode *inode;
+	int err;
+	e2fsck_t ctx;
+	struct hash_entry *harray;
+	int max_array, num_array;
+	int dir_size;
+	ino_t parent;
+};
+
+struct hash_entry {
+	ext2_dirhash_t	hash;
+	ext2_dirhash_t	minor_hash;
+	struct ext2_dir_entry	*dir;
+};
+
+struct out_dir {
+	int		num;
+	int		max;
+	char		*buf;
+	ext2_dirhash_t	*hashes;
+};
+
+static int fill_dir_block(ext2_filsys fs,
+			  blk_t	*block_nr,
+			  e2_blkcnt_t blockcnt,
+			  blk_t ref_block,
+			  int ref_offset, 
+			  void *priv_data)
+{
+	struct fill_dir_struct	*fd = (struct fill_dir_struct *) priv_data;
+	struct hash_entry 	*new_array, *ent;
+	struct ext2_dir_entry 	*dirent;
+	char			*dir;
+	int			offset, dir_offset;
+	
+	if (blockcnt < 0)
+		return 0;
+
+	offset = blockcnt * fs->blocksize;
+	if (offset + fs->blocksize > fd->inode->i_size) {
+		fd->err = EXT2_ET_DIR_CORRUPTED;
+		return BLOCK_ABORT;
+	}
+	dir = (fd->buf+offset);
+	if (HOLE_BLKADDR(*block_nr)) {
+		memset(dir, 0, fs->blocksize);
+		dirent = (struct ext2_dir_entry *) dir;
+		dirent->rec_len = fs->blocksize;
+	} else {
+		fd->err = ext2fs_read_dir_block(fs, *block_nr, dir);
+		if (fd->err)
+			return BLOCK_ABORT;
+	}
+	/* While the directory block is "hot", index it. */
+	dir_offset = 0;
+	while (dir_offset < fs->blocksize) {
+		dirent = (struct ext2_dir_entry *) (dir + dir_offset);
+		if (((dir_offset + dirent->rec_len) > fs->blocksize) ||
+		    (dirent->rec_len < 8) ||
+		    ((dirent->rec_len % 4) != 0) ||
+		    (((dirent->name_len & 0xFF)+8) > dirent->rec_len)) {
+			fd->err = EXT2_ET_DIR_CORRUPTED;
+			return BLOCK_ABORT;
+		}
+		if (dirent->inode == 0)
+			goto next;
+		if (((dirent->name_len&0xFF) == 1) && (dirent->name[0] == '.'))
+			goto next;
+		if (((dirent->name_len&0xFF) == 2) &&
+		    (dirent->name[0] == '.') && (dirent->name[1] == '.')) {
+			fd->parent = dirent->inode;
+			goto next;
+		}
+		if (fd->num_array >= fd->max_array) {
+			new_array = realloc(fd->harray,
+			    sizeof(struct hash_entry) * (fd->max_array+500));
+			if (!new_array) {
+				fd->err = ENOMEM;
+				return BLOCK_ABORT;
+			}
+			fd->harray = new_array;
+			fd->max_array += 500;
+		}
+		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;
+	}
+	
+	return 0;
+}
+
+/* Used for sorting the hash entry */
+static EXT2_QSORT_TYPE hash_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;
+	
+	if (he_a->hash > he_b->hash)
+		ret = 1;
+	else if (he_a->hash < he_b->hash)
+		ret = -1;
+	else {
+		if (he_a->minor_hash > he_b->minor_hash)
+			ret = 1;
+		else if (he_a->minor_hash < he_b->minor_hash)
+			ret = -1;
+		else
+			ret = 0;
+	}
+	return ret;
+}
+
+static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir, 
+				int blocks)
+{
+	void			*new_mem;
+
+	if (outdir->max) {
+		new_mem = realloc(outdir->buf, blocks * fs->blocksize);
+		if (!new_mem)
+			return ENOMEM;
+		outdir->buf = new_mem;
+		new_mem = realloc(outdir->hashes,
+				  blocks * sizeof(ext2_dirhash_t));
+		if (!new_mem)
+			return ENOMEM;
+		outdir->hashes = new_mem;
+	} else {
+		outdir->buf = malloc(blocks * fs->blocksize);
+		outdir->hashes = malloc(blocks * sizeof(ext2_dirhash_t));
+		outdir->num = 0;
+	}
+	outdir->max = blocks;
+	return 0;
+}
+
+static void free_out_dir(struct out_dir *outdir)
+{
+	free(outdir->buf);
+	free(outdir->hashes);
+	outdir->max = 0;
+	outdir->num =0;
+}
+
+errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir,
+			 char ** ret)
+{
+	errcode_t	retval;
+
+	if (outdir->num >= outdir->max) {
+		retval = alloc_size_dir(fs, outdir, outdir->max + 50);
+		if (retval)
+			return retval;
+	}
+	*ret = outdir->buf + (outdir->num++ * fs->blocksize);
+	return 0;
+}
+
+
+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;
+
+	if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_FILETYPE)
+		filetype = EXT2_FT_DIR << 8;
+	
+	memset(buf, 0, fs->blocksize);
+	dir = (struct ext2_dir_entry *) buf;
+	dir->inode = ino;
+	dir->name[0] = '.';
+	dir->name_len = 1 | filetype;
+	dir->rec_len = 12;
+	dir = (struct ext2_dir_entry *) (buf + 12);
+	dir->inode = parent;
+	dir->name[0] = '.';
+	dir->name[1] = '.';
+	dir->name_len = 2 | filetype;
+	dir->rec_len = fs->blocksize - 12;
+	
+	root = (struct ext2_dx_root_info *) (buf+24);
+	root->reserved_zero = 0;
+	root->hash_version = fs->super->s_def_hash_version;
+	root->info_length = 8;
+	root->indirect_levels = 0;
+	root->unused_flags = 0;
+
+	limits = (struct ext2_dx_countlimit *) (buf+32);
+	limits->limit = (fs->blocksize - 32) / sizeof(struct ext2_dx_entry);
+	limits->count = 0;
+
+	return root;
+}
+
+
+struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf)
+{
+	struct ext2_dir_entry 		*dir;
+	struct ext2_dx_countlimit	*limits;
+
+	memset(buf, 0, fs->blocksize);
+	dir = (struct ext2_dir_entry *) buf;
+	dir->inode = 0;
+	dir->rec_len = fs->blocksize;
+	
+	limits = (struct ext2_dx_countlimit *) (buf+8);
+	limits->limit = (fs->blocksize - 8) / sizeof(struct ext2_dx_entry);
+	limits->count = 0;
+
+	return (struct ext2_dx_entry *) limits;
+}
+
+
+struct write_dir_struct {
+	struct out_dir *outdir;
+	errcode_t	err;
+	e2fsck_t	ctx;
+	int		cleared;
+};
+
+/*
+ * This makes sure we have enough space to write out the modified
+ * directory.
+ */
+static int write_dir_block(ext2_filsys fs,
+			   blk_t	*block_nr,
+			   e2_blkcnt_t blockcnt,
+			   blk_t ref_block,
+			   int ref_offset, 
+			   void *priv_data)
+{
+	struct write_dir_struct	*wd = (struct write_dir_struct *) priv_data;
+	blk_t	new_blk, blk;
+	char	*dir;
+	errcode_t	retval;
+
+	if (*block_nr == 0)
+		return 0;
+	if (blockcnt >= wd->outdir->num) {
+		e2fsck_read_bitmaps(wd->ctx);
+		blk = *block_nr;
+		ext2fs_unmark_block_bitmap(wd->ctx->block_found_map, blk);
+		ext2fs_block_alloc_stats(fs, blk, -1);
+		*block_nr = 0;
+		wd->cleared++;
+		return BLOCK_CHANGED;
+	}
+	if (blockcnt < 0)
+		return 0;
+
+	dir = wd->outdir->buf + (blockcnt * fs->blocksize);
+	wd->err = ext2fs_write_dir_block(fs, *block_nr, dir);
+	if (wd->err)
+		return BLOCK_ABORT;
+	return 0;
+}
+
+
+static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs,
+				 struct out_dir *outdir, ext2_ino_t ino)
+{
+	struct write_dir_struct wd;
+	errcode_t	retval;
+	struct ext2_inode 	inode;
+
+	retval = e2fsck_expand_directory(ctx, ino, -1, outdir->num);
+	if (retval)
+		return retval;
+
+	wd.outdir = outdir;
+	wd.err = 0;
+	wd.ctx = ctx;
+	wd.cleared = 0;
+
+	retval = ext2fs_block_iterate2(fs, ino, 0, 0,
+				       write_dir_block, &wd);
+	if (retval)
+		return retval;
+	if (wd.err)
+		return wd.err;
+
+	e2fsck_read_inode(ctx, ino, &inode, "rehash_dir");
+	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");
+
+	return 0;
+}
+
+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;
+	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;
+	dir_buf = malloc(inode.i_size);
+	if (!dir_buf)
+		goto errout;
+
+	fd.max_array = inode.i_size / 32;
+	fd.num_array = 0;
+	fd.harray = malloc(fd.max_array * sizeof(struct hash_entry));
+	if (!fd.harray)
+		goto errout;
+
+	fd.ctx = ctx;
+	fd.buf = dir_buf;
+	fd.inode = &inode;
+	fd.err = 0;
+	fd.dir_size = 0;
+	fd.parent = 0;
+
+	/* Read in the entire directory into memory */
+	retval = ext2fs_block_iterate2(fs, ino, 0, 0,
+				       fill_dir_block, &fd);
+	if (fd.err) {
+		retval = fd.err;
+		goto errout;
+	}
+
+#if 0
+	printf("%d entries (%d bytes) found in inode %d\n",
+	       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);
+	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);
+	}
+	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);
+	if (retval)
+		goto errout;
+
+errout:
+	if (dir_buf)
+		free(dir_buf);
+	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;
+
+	if (!ctx->dirs_to_hash)
+		return;
+
+	retval = ext2fs_lookup(ctx->fs, EXT2_ROOT_INO, name,
+			       sizeof(name)-1, 0, &lpf);
+	if (retval)
+		lpf = 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;
+	}
+	while (ext2fs_u32_list_iterate(iter, &ino)) {
+		if (ino == lpf)
+			continue;
+		pctx.dir = ino;
+		if (first) {
+			fix_problem(ctx, PR_3A_PASS_HEADER, &pctx);
+			first = 0;
+		}
+		fix_problem(ctx, PR_3A_REHASH_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_REHASH_DIR);
+	ext2fs_u32_list_iterate_end(iter);
+	
+	ext2fs_u32_list_free(ctx->dirs_to_hash);
+	ctx->dirs_to_hash = 0;
+}