From 052db4b76e552682c1ad94ff4943faa98c958343 Mon Sep 17 00:00:00 2001
From: Theodore Ts'o <tytso@mit.edu>
Date: Thu, 12 Jun 1997 07:14:32 +0000
Subject: [PATCH] Makefile.in, .del-inodemap.c~24510e64, main.c, resize2fs.c,
 resize2fs.h:   New snapshot (almost fully functional)

---
 resize/Makefile.in |   5 +-
 resize/inodemap.c  | 240 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 resize/main.c      |   2 +-
 resize/resize2fs.c | 226 +++++++++++++++++++++++++++++++++++++++++++------
 resize/resize2fs.h |   5 --
 5 files changed, 443 insertions(+), 35 deletions(-)
 create mode 100644 resize/inodemap.c

diff --git a/resize/Makefile.in b/resize/Makefile.in
index 9f5c2cc..d5991f8 100644
--- a/resize/Makefile.in
+++ b/resize/Makefile.in
@@ -14,9 +14,10 @@ INSTALL = @INSTALL@
 PROGS=		resize2fs
 MANPAGES=	resize2fs.8
 
-RESIZE_OBJS= resize2fs.o main.o
+RESIZE_OBJS= inodemap.o resize2fs.o main.o
 
-SRCS= $(srcdir)/resize2fs.c \
+SRCS= $(srcdir)/inodemap.c \
+	$(srcdir)/resize2fs.c \
 	$(srcdir)/main.c 
 
 LIBS= $(LIBEXT2FS) $(LIBE2P) $(LIBCOM_ERR)  $(LIBUUID)
diff --git a/resize/inodemap.c b/resize/inodemap.c
new file mode 100644
index 0000000..9dc3db2
--- /dev/null
+++ b/resize/inodemap.c
@@ -0,0 +1,240 @@
+/*
+ * inodemap.c --- ext2resizer indoe mapper
+ *
+ * Copyright (C) 1997 Theodore Ts'o
+ * 
+ * %Begin-Header%
+ * All rights reserved.
+ * %End-Header%
+ */
+
+#include "resize2fs.h"
+
+struct inode_map_entry {
+	ino_t	old, new;
+};
+
+struct inode_map_struct {
+	struct inode_map_entry *list;
+	int	size;
+	int	num;
+	int	sorted;
+};
+
+typedef struct inode_map_struct *inode_map;
+
+/*
+ * Create inode map table
+ */
+static errcode_t create_inode_map(inode_map *imap, int size) 
+{
+	inode_map	new;
+
+	new = malloc(sizeof(struct inode_map_struct));
+	if (!new)
+		return ENOMEM;
+	memset(new, 0, sizeof(struct inode_map_struct));
+
+	new->size = size ? size : 50;
+	new->num = 0;
+	new->sorted = 1;
+
+	new->list = malloc(sizeof(struct inode_map_struct) * new->size);
+	if (!new->list) {
+		free(new);
+		return ENOMEM;
+	}
+	*imap = new;
+	return 0;
+}
+
+/*
+ * Add an entry to the inode table map
+ */
+static errcode_t add_inode_map_entry(inode_map imap, ino_t old, ino_t new)
+{
+	struct inode_map_entry *p;
+	int	newsize;
+
+	if (imap->num >= imap->size) {
+		newsize = imap->size + 100;
+		p = realloc(imap->list,
+			    sizeof(struct inode_map_struct) * newsize);
+		if (!p)
+			return ENOMEM;
+		imap->list = p;
+		imap->size = newsize;
+	}
+	if (imap->num) {
+		if (imap->list[imap->num-1].old > old)
+			imap->sorted = 0;
+	}
+	imap->list[imap->num].old = old;
+	imap->list[imap->num].new = new;
+	imap->num++;
+	return 0;
+}
+
+/*
+ * Helper function for qsort
+ */
+static int inode_map_cmp(const void *a, const void *b)
+{
+	const struct inode_map_entry *db_a =
+		(const struct inode_map_entry *) a;
+	const struct inode_map_entry *db_b =
+		(const struct inode_map_entry *) b;
+	
+	return (db_a->old - db_b->old);
+}	
+
+/*
+ * Given an inode map and inode number, look up the old inode number
+ * and return the new inode number
+ */
+static ino_t inode_map_translate(inode_map imap, ino_t old)
+{
+	int	low, high, mid;
+	ino_t	lowval, highval;
+	float	range;
+
+	if (!imap->sorted) {
+		qsort(imap->list, imap->num,
+		      sizeof(struct inode_map_entry), inode_map_cmp);
+		imap->sorted = 1;
+	}
+	low = 0;
+	high = imap->num-1;
+	while (low <= high) {
+#if 0
+		mid = (low+high)/2;
+#else
+		if (low == high)
+			mid = low;
+		else {
+			/* Interpolate for efficiency */
+			lowval = imap->list[low].old;
+			highval = imap->list[high].old;
+
+			if (old < lowval)
+				range = 0;
+			else if (old > highval)
+				range = 1;
+			else 
+				range = ((float) (old - lowval)) /
+					(highval - lowval);
+			mid = low + ((int) (range * (high-low)));
+		}
+#endif
+		if (old == imap->list[mid].old)
+			return imap->list[mid].new;
+		if (old < imap->list[mid].old)
+			high = mid-1;
+		else
+			low = mid+1;
+	}
+	return 0;
+}
+
+int check_and_change_inodes(ino_t dir, int entry,
+			    struct ext2_dir_entry *dirent, int offset,
+			    int	blocksize, char *buf, void *private)
+{
+	inode_map imap = private;
+	ino_t	new;
+
+	if (!dirent->inode)
+		return 0;
+
+	new = inode_map_translate(imap, dirent->inode);
+
+	if (!new)
+		return 0;
+
+	printf("Inode translate (dir=%ld, name=%.*s, %ld->%ld)\n",
+	       dir, dirent->name_len, dirent->name, dirent->inode, new);
+
+	dirent->inode = new;
+
+	return DIRENT_CHANGED;
+}
+
+errcode_t ext2fs_inode_move(ext2_resize_t rfs)
+{
+	ino_t			ino, start, end, new;
+	struct ext2_inode 	inode;
+	ext2_inode_scan 	scan;
+	inode_map		imap;
+	errcode_t		retval;
+	int			group;
+	
+	if (rfs->old_fs->group_desc_count <=
+	    rfs->new_fs->group_desc_count)
+		return 0;
+
+	retval = create_inode_map(&imap, 0);
+	if (retval)
+		return retval;
+
+	retval = ext2fs_open_inode_scan(rfs->old_fs, 0, &scan);
+	if (retval)
+		return retval;
+
+	retval = ext2fs_inode_scan_goto_blockgroup(scan,
+				   rfs->new_fs->group_desc_count);
+	if (retval) {
+		ext2fs_close_inode_scan(scan);
+		return retval;
+	}
+
+	new = EXT2_FIRST_INODE(rfs->new_fs->super);
+
+	/*
+	 * First, copy all of the inodes that need to be moved
+	 * elsewhere in the inode table
+	 */
+	while (1) {
+		retval = ext2fs_get_next_inode(scan, &ino, &inode);
+		if (retval)
+			return retval;
+		if (!ino)
+			break;
+		
+		if (!ext2fs_test_inode_bitmap(rfs->old_fs->inode_map, ino)) 
+			continue;
+
+		/*
+		 * Find a new inode
+		 */
+		while (1) { 
+			if (!ext2fs_test_inode_bitmap(rfs->new_fs->inode_map, 
+						      new))
+				break;
+			new++;
+			if (new > rfs->new_fs->super->s_inodes_count)
+				return ENOSPC;
+		}
+		ext2fs_mark_inode_bitmap(rfs->new_fs->inode_map, new);
+		retval = ext2fs_write_inode(rfs->old_fs, new, &inode);
+		if (retval)
+			return retval;
+		group = (new-1) / EXT2_INODES_PER_GROUP(rfs->new_fs->super);
+		if (LINUX_S_ISDIR(inode.i_mode))
+			rfs->new_fs->group_desc[group].bg_used_dirs_count++;
+		
+		printf("inode %ld->%ld\n", ino, new);
+
+		add_inode_map_entry(imap, ino, new);
+	}
+	/*
+	 * Now, we iterate over all of the directories to update the
+	 * inode references
+	 */
+	retval = ext2fs_dblist_dir_iterate(rfs->old_fs->dblist, 0, 0,
+					   check_and_change_inodes, imap);
+	if (retval)
+		return retval;
+
+	return 0;
+}
+
diff --git a/resize/main.c b/resize/main.c
index d8b2200..9a53e74 100644
--- a/resize/main.c
+++ b/resize/main.c
@@ -49,7 +49,7 @@ void main (int argc, char ** argv)
 	device_name = argv[optind++];
 	new_size = atoi(argv[optind++]);
 	initialize_ext2_error_table();
-#if 0
+#if 1
 	io_ptr = unix_io_manager;
 #else
 	io_ptr = test_io_manager;
diff --git a/resize/resize2fs.c b/resize/resize2fs.c
index b2fbc68..805a64c 100644
--- a/resize/resize2fs.c
+++ b/resize/resize2fs.c
@@ -200,7 +200,7 @@ retry:
  */
 static errcode_t determine_relocations(ext2_resize_t rfs)
 {
-	int	i, j;
+	int	i, j, max, adj;
 	blk_t	blk, group_blk;
 	unsigned long old_blocks, new_blocks;
 	errcode_t	retval;
@@ -229,6 +229,9 @@ static errcode_t determine_relocations(ext2_resize_t rfs)
 	if (old_blocks == new_blocks)
 		return 0;
 
+	max = fs->group_desc_count;
+	if (max > rfs->old_fs->group_desc_count)
+		max = rfs->old_fs->group_desc_count;
 	group_blk = rfs->old_fs->super->s_first_data_block;
 	/*
 	 * If we're reducing the number of descriptor blocks, this
@@ -236,15 +239,17 @@ static errcode_t determine_relocations(ext2_resize_t rfs)
 	 * blocks as free.
 	 */
 	if (old_blocks > new_blocks) {
-		for (i = 0; i < fs->group_desc_count; i++) {
+		for (i = 0; i < max; i++) {
 			if (!ext2fs_bg_has_super(fs, i)) {
 				group_blk += fs->super->s_blocks_per_group;
 				continue;
 			}
 			for (blk = group_blk+1+old_blocks;
-			     blk < group_blk+1+new_blocks; blk++)
+			     blk < group_blk+1+new_blocks; blk++) {
 				ext2fs_unmark_block_bitmap(fs->block_map,
 							   blk);
+				rfs->needed_blocks--;
+			}
 			group_blk += fs->super->s_blocks_per_group;
 		}
 		return 0;
@@ -253,7 +258,7 @@ static errcode_t determine_relocations(ext2_resize_t rfs)
 	 * If we're increasing the number of descriptor blocks, life
 	 * gets interesting....  
 	 */
-	for (i = 0; i < fs->group_desc_count; i++) {
+	for (i = 0; i < max; i++) {
 		if (!ext2fs_bg_has_super(fs, i))
 			goto next_group;
 
@@ -266,11 +271,14 @@ static errcode_t determine_relocations(ext2_resize_t rfs)
 			 * Check to see if we overlap with the inode
 			 * or block bitmap
 			 */
-			if (blk == fs->group_desc[i].bg_inode_bitmap)
-				fs->group_desc[i].bg_block_bitmap = 0;	
-			if (blk == fs->group_desc[i].bg_inode_bitmap)
+			if (blk == fs->group_desc[i].bg_block_bitmap) {
+				fs->group_desc[i].bg_block_bitmap = 0;
+				rfs->needed_blocks++;
+			}
+			if (blk == fs->group_desc[i].bg_inode_bitmap) {
 				fs->group_desc[i].bg_inode_bitmap = 0;
-
+				rfs->needed_blocks++;
+			}
 			/*
 			 * Check to see if we overlap with the inode
 			 * table
@@ -320,28 +328,179 @@ static errcode_t determine_relocations(ext2_resize_t rfs)
 		ext2fs_mark_block_bitmap(fs->block_map,
 					 fs->group_desc[i].bg_inode_bitmap);
 
+		/*
+		 * The inode table, if we need to relocate it, is
+		 * handled specially.  We have to reserve the blocks
+		 * for both the old and the new inode table, since we
+		 * can't have the inode table be destroyed during the
+		 * block relocation phase.
+		 */
+		adj = fs->group_desc[i].bg_inode_table -
+			rfs->old_fs->group_desc[i].bg_inode_table;
+		if (!adj)
+			goto next_group; /* inode table not moved */
+
+		/*
+		 * Figure out how many blocks we need to have free.
+		 * This takes into account that we need to reserve
+		 * both inode tables, which may be overallping.
+		 */
+		if (adj < 0)
+			adj = -adj;
+		if (adj > fs->inode_blocks_per_group)
+			adj = fs->inode_blocks_per_group;
+		rfs->needed_blocks += fs->inode_blocks_per_group + adj;
+
+		/*
+		 * Mark the new inode table as in use in the new block
+		 * allocation bitmap.
+		 */
 		for (blk = fs->group_desc[i].bg_inode_table, j=0;
 		     j < fs->inode_blocks_per_group ; j++, blk++)
 			ext2fs_mark_block_bitmap(fs->block_map, blk);
-		
 		/*
-		 * Mark the inode tables which will need to move, and
-		 * restore the old inode table location (for now)
+		 * Make sure the old inode table is reserved in the
+		 * block reservation bitmap.
 		 */
-		if (fs->group_desc[i].bg_inode_table !=
-		    rfs->old_fs->group_desc[i].bg_inode_table) {
-			rfs->move_itable[i] = fs->group_desc[i].bg_inode_table;
-			fs->group_desc[i].bg_inode_table =
-				rfs->old_fs->group_desc[i].bg_inode_table;
-		}
+		for (blk = rfs->old_fs->group_desc[i].bg_inode_table, j=0;
+		     j < fs->inode_blocks_per_group ; j++, blk++)
+			ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 		
 	next_group:
 		group_blk += rfs->new_fs->super->s_blocks_per_group;
 	}
+	return 0;
 }
 
 
 /*
+ * A very scary routine --- this one moves the inode table around!!!
+ *
+ * After this you have to use the rfs->new_fs file handle to read and
+ * write inodes.
+ */
+errcode_t move_itables(ext2_resize_t rfs)
+{
+	int	i, max;
+	ext2_filsys	fs = rfs->new_fs;
+	char		*buf;
+	blk_t		old, new;
+	errcode_t	retval, err;
+
+	printf("Hide the women and children --- "
+	       "commencing inode table moves!!\n");
+	
+	max = fs->group_desc_count;
+	if (max > rfs->old_fs->group_desc_count)
+		max = rfs->old_fs->group_desc_count;
+
+	buf = malloc(fs->blocksize * fs->inode_blocks_per_group);
+	if (!buf)
+		return ENOMEM;
+	
+	for (i=0; i < max; i++) {
+		old = rfs->old_fs->group_desc[i].bg_inode_table;
+		new = fs->group_desc[i].bg_inode_table;
+		
+		printf("Group %d block %ld->%ld\n", i, old, new);
+		
+		if (old == new)
+			continue;
+
+		retval = io_channel_read_blk(fs->io, old,
+					     fs->inode_blocks_per_group, buf);
+		if (retval) 
+			goto backout;
+		retval = io_channel_write_blk(fs->io, new,
+					      fs->inode_blocks_per_group, buf);
+		if (retval) {
+			io_channel_write_blk(fs->io, old,
+					      fs->inode_blocks_per_group, buf);
+			goto backout;
+		}
+	}
+	ext2fs_flush(rfs->new_fs);
+	printf("Inode table move finished.\n");
+	return 0;
+	
+backout:
+	printf("Error: %s; now backing out!\n", error_message(retval));
+	while (--i >= 0) {
+		printf("Group %d block %ld->%ld\n", i, new, old);
+		old = rfs->old_fs->group_desc[i].bg_inode_table;
+		new = fs->group_desc[i].bg_inode_table;
+		
+		err = io_channel_read_blk(fs->io, new,
+					  fs->inode_blocks_per_group, buf);
+		if (err)
+			continue;
+		err = io_channel_write_blk(fs->io, old,
+					   fs->inode_blocks_per_group, buf);
+	}
+	return retval;
+}
+
+/*
+ * Finally, recalculate the summary information
+ */
+static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs)
+{
+	blk_t	blk;
+	ino_t	ino;
+	int	group = 0;
+	int	count = 0;
+	int	total_free = 0;
+	int	group_free = 0;
+
+	/*
+	 * First calculate the block statistics
+	 */
+	for (blk = fs->super->s_first_data_block;
+	     blk < fs->super->s_blocks_count; blk++) {
+		if (!ext2fs_fast_test_block_bitmap(fs->block_map, blk)) {
+			group_free++;
+			total_free++;
+		}
+		count++;
+		if ((count == fs->super->s_blocks_per_group) ||
+		    (blk == fs->super->s_blocks_count-1)) {
+			fs->group_desc[group++].bg_free_blocks_count =
+				group_free;
+			count = 0;
+			group_free = 0;
+		}
+	}
+	fs->super->s_free_blocks_count = total_free;
+	
+	/*
+	 * Next, calculate the inode statistics
+	 */
+	group_free = 0;
+	total_free = 0;
+	count = 0;
+	group = 0;
+	for (ino = 1; ino <= fs->super->s_inodes_count; ino++) {
+		if (!ext2fs_fast_test_inode_bitmap(fs->inode_map, ino)) {
+			group_free++;
+			total_free++;
+		}
+		count++;
+		if ((count == fs->super->s_inodes_per_group) ||
+		    (ino == fs->super->s_inodes_count)) {
+			fs->group_desc[group++].bg_free_inodes_count =
+				group_free;
+			count = 0;
+			group_free = 0;
+		}
+	}
+	fs->super->s_free_inodes_count = total_free;
+	ext2fs_mark_super_dirty(fs);
+	return 0;
+}
+
+
+
+/*
  * This is the top-level routine which does the dirty deed....
  */
 errcode_t resize_fs(ext2_filsys fs, blk_t new_size)
@@ -361,13 +520,6 @@ errcode_t resize_fs(ext2_filsys fs, blk_t new_size)
 		return ENOMEM;
 	memset(rfs, 0, sizeof(struct ext2_resize_struct));
 
-	rfs->move_itable = malloc(sizeof(blk_t) * fs->group_desc_count);
-	if (!rfs->move_itable) {
-		retval = ENOMEM;
-		goto errout;
-	}
-	memset(rfs->move_itable, 0, sizeof(blk_t) * fs->group_desc_count);
-	
 	rfs->old_fs = fs;
 	retval = ext2fs_dup_handle(fs, &rfs->new_fs);
 	if (retval)
@@ -381,6 +533,14 @@ errcode_t resize_fs(ext2_filsys fs, blk_t new_size)
 	if (retval)
 		goto errout;
 
+	printf("Number of free blocks: %d, Needed: %d\n",
+	       fs->super->s_free_blocks_count, rfs->needed_blocks);
+	
+	if (rfs->needed_blocks > fs->super->s_free_blocks_count) {
+		retval = ENOSPC;
+		goto errout;
+	}
+	
 	printf("\nOld superblock:\n");
 	list_super(rfs->old_fs->super);
 	printf("\n\nNew superblock:\n");
@@ -388,8 +548,23 @@ errcode_t resize_fs(ext2_filsys fs, blk_t new_size)
 	printf("\n");
 
 	retval = ext2fs_move_blocks(rfs->old_fs, rfs->reserve_blocks,
+				    rfs->new_fs->block_map,
 				    EXT2_BMOVE_GET_DBLIST);
+	if (retval)
+		return retval;
 
+	retval = ext2fs_inode_move(rfs);
+	if (retval)
+		return retval;
+
+	retval = move_itables(rfs);
+	if (retval)
+		return retval;
+
+	retval = ext2fs_calculate_summary_stats(rfs->new_fs);
+	if (retval)
+		return retval;
+	
 	retval = ext2fs_close(rfs->new_fs);
 	if (retval)
 		return retval;
@@ -399,11 +574,8 @@ errcode_t resize_fs(ext2_filsys fs, blk_t new_size)
 	return 0;
 
 errout:
-	if (rfs->move_itable)
-		free(rfs->move_itable);
 	if (rfs->new_fs)
 		ext2fs_free(rfs->new_fs);
 	free(rfs);
 	return retval;
 }
-
diff --git a/resize/resize2fs.h b/resize/resize2fs.h
index 5c1dad3..cc50004 100644
--- a/resize/resize2fs.h
+++ b/resize/resize2fs.h
@@ -41,11 +41,6 @@ struct ext2_resize_struct {
 	ext2_brel	block_relocate;
 	ext2fs_block_bitmap reserve_blocks;
 	int		needed_blocks;
-	/*
-	 * This array contains the new location of the inode table for
-	 * those block groups where it has to be relocated.
-	 */
-	blk_t		*move_itable;
 };
 
 typedef struct ext2_resize_struct *ext2_resize_t;
-- 
1.8.3.1