Rework e2fsck's dirinfo abstraction to be more friendly for databases

Change the iterator abstraction and replace e2fsck_get_dir_info() with
e2fsck_dir_info_{set,get}_{parent,dotdot} so that we can support an
on-disk dirinfo implementation.  This allows e2fsck to check very large
filesystems on systems with smaller amounts of memory and/or address
space.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

1 files changed, 213 insertions, 50 deletions

diff --git a/e2fsck/dirinfo.c b/e2fsck/dirinfo.c
index 516c4613..4e660758 100644
--- a/e2fsck/dirinfo.c
+++ b/e2fsck/dirinfo.c
@@ -5,7 +5,45 @@
  * under the terms of the GNU Public License.
  */
 
+#undef DIRINFO_DEBUG
+
 #include "e2fsck.h"
+struct dir_info_db {
+	int		count;
+	int		size;
+	struct dir_info *array;
+	struct dir_info *last_lookup;
+};
+
+struct dir_info_iter {
+	int	i;
+};
+
+static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir);
+
+void setup_db(e2fsck_t ctx)
+{
+	struct dir_info_db	*db;
+	ext2_ino_t		num_dirs;
+	errcode_t		retval;
+
+	db = (struct dir_info_db *)
+		e2fsck_allocate_memory(ctx, sizeof(struct dir_info_db),
+				       "directory map db");
+	db->count = db->size = 0;
+	db->array = 0;
+
+	retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
+	if (retval)
+		num_dirs = 1024;	/* Guess */
+	db->size = num_dirs + 10;
+	db->array  = (struct dir_info *)
+		e2fsck_allocate_memory(ctx, db->size 
+				       * sizeof (struct dir_info),
+				       "directory map");
+
+	ctx->dir_info = db;
+}
 
 /*
  * This subroutine is called during pass1 to create a directory info
@@ -14,39 +52,37 @@
  */
 void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
 {
-	struct dir_info *dir;
-	int		i, j;
-	ext2_ino_t	num_dirs;
-	errcode_t	retval;
-	unsigned long	old_size;
-
-#if 0
-	printf("add_dir_info for inode %lu...\n", ino);
+	struct dir_info_db 	*db;
+	struct dir_info 	*dir, ent;
+	int			i, j;
+	errcode_t		retval;
+	unsigned long		old_size;
+
+#ifdef DIRINFO_DEBUG
+	printf("add_dir_info for inode (%lu, %lu)...\n", ino, parent);
 #endif
-	if (!ctx->dir_info) {
-		ctx->dir_info_count = 0;
-		retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
-		if (retval)
-			num_dirs = 1024;	/* Guess */
-		ctx->dir_info_size = num_dirs + 10;
-		ctx->dir_info  = (struct dir_info *)
-			e2fsck_allocate_memory(ctx, ctx->dir_info_size
-					       * sizeof (struct dir_info),
-					       "directory map");
-	}
+	if (!ctx->dir_info)
+		setup_db(ctx);
+	db = ctx->dir_info;
 	
-	if (ctx->dir_info_count >= ctx->dir_info_size) {
-		old_size = ctx->dir_info_size * sizeof(struct dir_info);
-		ctx->dir_info_size += 10;
-		retval = ext2fs_resize_mem(old_size, ctx->dir_info_size *
+	if (ctx->dir_info->count >= ctx->dir_info->size) {
+		old_size = ctx->dir_info->size * sizeof(struct dir_info);
+		ctx->dir_info->size += 10;
+		retval = ext2fs_resize_mem(old_size, ctx->dir_info->size *
 					   sizeof(struct dir_info),
 					   &ctx->dir_info);
 		if (retval) {
-			ctx->dir_info_size -= 10;
+			ctx->dir_info->size -= 10;
 			return;
 		}
 	}
 
+	ent.ino = ino;
+	ent.parent = parent;
+	ent.dotdot = parent;
+
+	e2fsck_put_dir_info(ctx, &ent);
+
 	/*
 	 * Normally, add_dir_info is called with each inode in
 	 * sequential order; but once in a while (like when pass 3
@@ -56,17 +92,17 @@ void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
 	 * the dir_info array needs to be sorted by inode number for
 	 * get_dir_info()'s sake.
 	 */
-	if (ctx->dir_info_count &&
-	    ctx->dir_info[ctx->dir_info_count-1].ino >= ino) {
-		for (i = ctx->dir_info_count-1; i > 0; i--)
-			if (ctx->dir_info[i-1].ino < ino)
+	if (ctx->dir_info->count &&
+	    ctx->dir_info->array[ctx->dir_info->count-1].ino >= ino) {
+		for (i = ctx->dir_info->count-1; i > 0; i--)
+			if (ctx->dir_info->array[i-1].ino < ino)
 				break;
-		dir = &ctx->dir_info[i];
+		dir = &ctx->dir_info->array[i];
 		if (dir->ino != ino) 
-			for (j = ctx->dir_info_count++; j > i; j--)
-				ctx->dir_info[j] = ctx->dir_info[j-1];
+			for (j = ctx->dir_info->count++; j > i; j--)
+				ctx->dir_info->array[j] = ctx->dir_info->array[j-1];
 	} else
-		dir = &ctx->dir_info[ctx->dir_info_count++];
+		dir = &ctx->dir_info->array[ctx->dir_info->count++];
 	
 	dir->ino = ino;
 	dir->dotdot = parent;
@@ -77,26 +113,53 @@ void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
  * get_dir_info() --- given an inode number, try to find the directory
  * information entry for it.
  */
-struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
+static struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
 {
-	int	low, high, mid;
+	struct dir_info_db	*db = ctx->dir_info;
+	int			low, high, mid, ret;
 
-	low = 0;
-	high = ctx->dir_info_count-1;
-	if (!ctx->dir_info)
+	if (!db)
 		return 0;
-	if (ino == ctx->dir_info[low].ino)
-		return &ctx->dir_info[low];
-	if  (ino == ctx->dir_info[high].ino)
-		return &ctx->dir_info[high];
+
+#ifdef DIRINFO_DEBUG
+	printf("e2fsck_get_dir_info %d...", ino);
+#endif
+
+	if (db->last_lookup && db->last_lookup->ino == ino)
+		return db->last_lookup;
+
+	low = 0;
+	high = ctx->dir_info->count-1;
+	if (ino == ctx->dir_info->array[low].ino) {
+#ifdef DIRINFO_DEBUG
+		printf("(%d,%d,%d)\n", ino, 
+		       ctx->dir_info->array[low].dotdot, 
+		       ctx->dir_info->array[low].parent);
+#endif
+		return &ctx->dir_info->array[low];
+	}
+	if (ino == ctx->dir_info->array[high].ino) {
+#ifdef DIRINFO_DEBUG
+		printf("(%d,%d,%d)\n", ino, 
+		       ctx->dir_info->array[high].dotdot, 
+		       ctx->dir_info->array[high].parent);
+#endif
+		return &ctx->dir_info->array[high];
+	}
 
 	while (low < high) {
 		mid = (low+high)/2;
 		if (mid == low || mid == high)
 			break;
-		if (ino == ctx->dir_info[mid].ino)
-			return &ctx->dir_info[mid];
-		if (ino < ctx->dir_info[mid].ino)
+		if (ino == ctx->dir_info->array[mid].ino) {
+#ifdef DIRINFO_DEBUG
+			printf("(%d,%d,%d)\n", ino, 
+			       ctx->dir_info->array[mid].dotdot, 
+			       ctx->dir_info->array[mid].parent);
+#endif
+			return &ctx->dir_info->array[mid];
+		}
+		if (ino < ctx->dir_info->array[mid].ino)
 			high = mid;
 		else
 			low = mid;
@@ -104,17 +167,26 @@ struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
 	return 0;
 }
 
+static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir)
+{
+#ifdef DIRINFO_DEBUG
+	printf("e2fsck_put_dir_info (%d, %d, %d)...", dir->ino, dir->dotdot,
+	       dir->parent);
+#endif
+	return;
+}
+
 /*
  * Free the dir_info structure when it isn't needed any more.
  */
 void e2fsck_free_dir_info(e2fsck_t ctx)
 {
 	if (ctx->dir_info) {
+		ctx->dir_info->size = 0;
+		ctx->dir_info->count = 0;
 		ext2fs_free_mem(&ctx->dir_info);
 		ctx->dir_info = 0;
 	}
-	ctx->dir_info_size = 0;
-	ctx->dir_info_count = 0;
 }
 
 /*
@@ -122,16 +194,107 @@ void e2fsck_free_dir_info(e2fsck_t ctx)
  */
 int e2fsck_get_num_dirinfo(e2fsck_t ctx)
 {
-	return ctx->dir_info_count;
+	return ctx->dir_info ? ctx->dir_info->count : 0;
+}
+
+extern struct dir_info_iter *e2fsck_dir_info_iter_begin(e2fsck_t ctx)
+{
+	struct dir_info_iter *iter;
+	struct dir_info_db *db = ctx->dir_info;
+	int ret;
+
+	iter = e2fsck_allocate_memory(ctx, sizeof(struct dir_info_iter),
+				      "dir_info iterator");
+	memset(iter, 0, sizeof(iter));
+	return iter;
+}
+
+extern void e2fsck_dir_info_iter_end(e2fsck_t ctx, 
+				     struct dir_info_iter *iter)
+{
+	ext2fs_free_mem(&iter);
 }
 
 /*
  * A simple interator function
  */
-struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
+struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, struct dir_info_iter *iter)
 {
-	if (*control >= ctx->dir_info_count)
+	if (!ctx->dir_info || !iter ||
+	    (iter->i >= ctx->dir_info->count))
 		return 0;
+	
+#ifdef DIRINFO_DEBUG
+	printf("iter(%d, %d, %d)...", ctx->dir_info->array[iter->i].ino, 
+	       ctx->dir_info->array[iter->i].dotdot, 
+	       ctx->dir_info->array[iter->i].parent);
+#endif
+	return(ctx->dir_info->array + iter->i++);
+}
+
+/*
+ * This function only sets the parent pointer, and requires that
+ * dirinfo structure has already been created.
+ */
+int e2fsck_dir_info_set_parent(e2fsck_t ctx, ext2_ino_t ino, 
+			       ext2_ino_t parent)
+{
+	struct dir_info *p;
+
+	p = e2fsck_get_dir_info(ctx, ino);
+	if (!p)
+		return 1;
+	p->parent = parent;
+	e2fsck_put_dir_info(ctx, p);
+	return 0;
+}
+
+/*
+ * This function only sets the dot dot pointer, and requires that
+ * dirinfo structure has already been created.
+ */
+int e2fsck_dir_info_set_dotdot(e2fsck_t ctx, ext2_ino_t ino, 
+			       ext2_ino_t dotdot)
+{
+	struct dir_info *p;
 
-	return(ctx->dir_info + (*control)++);
+	p = e2fsck_get_dir_info(ctx, ino);
+	if (!p)
+		return 1;
+	p->dotdot = dotdot;
+	e2fsck_put_dir_info(ctx, p);
+	return 0;
+}
+
+/*
+ * This function only sets the parent pointer, and requires that
+ * dirinfo structure has already been created.
+ */
+int e2fsck_dir_info_get_parent(e2fsck_t ctx, ext2_ino_t ino, 
+			       ext2_ino_t *parent)
+{
+	struct dir_info *p;
+
+	p = e2fsck_get_dir_info(ctx, ino);
+	if (!p)
+		return 1;
+	*parent = p->parent;
+	return 0;
 }
+
+/*
+ * This function only sets the dot dot pointer, and requires that
+ * dirinfo structure has already been created.
+ */
+int e2fsck_dir_info_get_dotdot(e2fsck_t ctx, ext2_ino_t ino, 
+			       ext2_ino_t *dotdot)
+{
+	struct dir_info *p;
+
+	p = e2fsck_get_dir_info(ctx, ino);
+	if (!p)
+		return 1;
+	*dotdot = p->dotdot;
+	return 0;
+}
+