e2fsck: check all sparse_super backups

Teach e2fsck to look for backup super blocks in the "sparse_super"
groups, by checking group #1 first and then powers of 3^n, 5^n,
and 7^n, up to the limit of available block groups.

Export ext2fs_list_backups() function to efficiently iterate groups
for backup sb/GDT instead of checking every group.  Ensure that the
group counters do not try to overflow the 2^32-1 group limit, and
try to limit scanning to the size of the block device (if available).

Signed-off-by: Li Dongyang <dongyangli@ddn.com>
Signed-off-by: Andreas Dilger <adilger@whamcloud.com>
Link: https://lore.kernel.org/r/20230904045742.827584-1-dongyangli@ddn.com
Signed-off-by: Theodore Ts'o <tytso@mit.edu>

5 files changed, 64 insertions, 51 deletions

diff --git a/e2fsck/util.c b/e2fsck/util.c
index 0fe436031..6982966e6 100644
--- a/e2fsck/util.c
+++ b/e2fsck/util.c
@@ -560,29 +560,20 @@ blk64_t get_backup_sb(e2fsck_t ctx, ext2_filsys fs, const char *name,
 	struct ext2_super_block *sb;
 	io_channel		io = NULL;
 	void			*buf = NULL;
-	int			blocksize;
-	blk64_t			superblock, ret_sb = 8193;
+	int			blocksize = EXT2_MIN_BLOCK_SIZE;
+	int			blocksize_known = 0;
+	blk_t			bpg = 0;
+	blk64_t			ret_sb = 8193;
 
 	if (fs && fs->super) {
-		ret_sb = (fs->super->s_blocks_per_group +
-			  fs->super->s_first_data_block);
-		if (ctx) {
-			ctx->superblock = ret_sb;
-			ctx->blocksize = fs->blocksize;
-		}
-		return ret_sb;
+		blocksize = fs->blocksize;
+		blocksize_known = 1;
+		bpg = fs->super->s_blocks_per_group;
 	}
 
-	if (ctx) {
-		if (ctx->blocksize) {
-			ret_sb = ctx->blocksize * 8;
-			if (ctx->blocksize == 1024)
-				ret_sb++;
-			ctx->superblock = ret_sb;
-			return ret_sb;
-		}
-		ctx->superblock = ret_sb;
-		ctx->blocksize = 1024;
+	if (ctx && ctx->blocksize) {
+		blocksize = ctx->blocksize;
+		blocksize_known = 1;
 	}
 
 	if (!name || !manager)
@@ -595,28 +586,42 @@ blk64_t get_backup_sb(e2fsck_t ctx, ext2_filsys fs, const char *name,
 		goto cleanup;
 	sb = (struct ext2_super_block *) buf;
 
-	for (blocksize = EXT2_MIN_BLOCK_SIZE;
-	     blocksize <= EXT2_MAX_BLOCK_SIZE ; blocksize *= 2) {
-		superblock = blocksize*8;
-		if (blocksize == 1024)
-			superblock++;
+	for (; blocksize <= EXT2_MAX_BLOCK_SIZE; blocksize *= 2) {
+		dgrp_t grp, three = 1, five = 5, seven = 7;
+		dgrp_t limit = (dgrp_t)-1;
+		blk_t this_bpg = bpg ? bpg : blocksize * 8;
+
+		if (ctx->num_blocks && limit > ctx->num_blocks / this_bpg)
+			limit = ctx->num_blocks / this_bpg;
+
 		io_channel_set_blksize(io, blocksize);
-		if (io_channel_read_blk64(io, superblock,
-					-SUPERBLOCK_SIZE, buf))
-			continue;
+
+		while ((grp = ext2fs_list_backups(NULL, &three,
+						  &five, &seven)) < limit) {
+			blk64_t superblock = (blk64_t)grp * this_bpg;
+
+			if (blocksize == 1024)
+				superblock++;
+			if (io_channel_read_blk64(io, superblock,
+						-SUPERBLOCK_SIZE, buf))
+				continue;
 #ifdef WORDS_BIGENDIAN
-		if (sb->s_magic == ext2fs_swab16(EXT2_SUPER_MAGIC))
-			ext2fs_swap_super(sb);
+			if (sb->s_magic == ext2fs_swab16(EXT2_SUPER_MAGIC))
+				ext2fs_swap_super(sb);
 #endif
-		if ((sb->s_magic == EXT2_SUPER_MAGIC) &&
-		    (EXT2_BLOCK_SIZE(sb) == blocksize)) {
-			ret_sb = superblock;
-			if (ctx) {
-				ctx->superblock = superblock;
-				ctx->blocksize = blocksize;
+			if ((sb->s_magic == EXT2_SUPER_MAGIC) &&
+			    (EXT2_BLOCK_SIZE(sb) == blocksize)) {
+				ret_sb = superblock;
+				if (ctx) {
+					ctx->superblock = superblock;
+					ctx->blocksize = blocksize;
+				}
+				goto cleanup;
 			}
-			break;
 		}
+
+		if (blocksize_known)
+			break;
 	}
 
 cleanup:
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 8953817ca..9cea4b69a 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1535,6 +1535,8 @@ errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 					   ext2fs_block_bitmap *bitmap);
 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
 				     blk64_t end, blk64_t *out);
+extern unsigned int ext2fs_list_backups(ext2_filsys fs, unsigned int *three,
+				unsigned int *five, unsigned int *seven);
 
 /* get_num_dirs.c */
 extern errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs);
diff --git a/lib/ext2fs/res_gdt.c b/lib/ext2fs/res_gdt.c
index 9024165d6..8d2a08626 100644
--- a/lib/ext2fs/res_gdt.c
+++ b/lib/ext2fs/res_gdt.c
@@ -20,18 +20,19 @@
 /*
  * Iterate through the groups which hold BACKUP superblock/GDT copies in an
  * ext3 filesystem.  The counters should be initialized to 1, 5, and 7 before
- * calling this for the first time.  In a sparse filesystem it will be the
- * sequence of powers of 3, 5, and 7: 1, 3, 5, 7, 9, 25, 27, 49, 81, ...
+ * calling this for the first time.  In a sparse_super filesystem it will be
+ * the sequence of powers of 3, 5, and 7: 1, 3, 5, 7, 9, 25, 27, 49, 81, ...
  * For a non-sparse filesystem it will be every group: 1, 2, 3, 4, ...
+ * For a sparse_super2 filesystem there are two backups in specific groups.
  */
-static unsigned int list_backups(ext2_filsys fs, unsigned int *three,
-				 unsigned int *five, unsigned int *seven)
+dgrp_t ext2fs_list_backups(ext2_filsys fs, dgrp_t *three,
+			   dgrp_t *five, dgrp_t *seven)
 {
-	unsigned int *min = three;
-	int mult = 3;
-	unsigned int ret;
+	dgrp_t *min = three;
+	unsigned long long mult = 3;
+	dgrp_t ret;
 
-	if (ext2fs_has_feature_sparse_super2(fs->super)) {
+	if (fs && ext2fs_has_feature_sparse_super2(fs->super)) {
 		if (*min == 1) {
 			*min += 1;
 			if (fs->super->s_backup_bgs[0])
@@ -42,11 +43,14 @@ static unsigned int list_backups(ext2_filsys fs, unsigned int *three,
 			if (fs->super->s_backup_bgs[1])
 				return fs->super->s_backup_bgs[1];
 		}
+
 		return fs->group_desc_count;
 	}
-	if (!ext2fs_has_feature_sparse_super(fs->super)) {
+
+	if (fs && !ext2fs_has_feature_sparse_super(fs->super)) {
 		ret = *min;
 		*min += 1;
+
 		return ret;
 	}
 
@@ -60,7 +64,11 @@ static unsigned int list_backups(ext2_filsys fs, unsigned int *three,
 	}
 
 	ret = *min;
-	*min *= mult;
+	mult *= *min;
+	if (mult > (dgrp_t)-1)
+		*min = (dgrp_t)-1;
+	else
+		*min = mult;
 
 	return ret;
 }
@@ -142,8 +150,8 @@ errcode_t ext2fs_create_resize_inode(ext2_filsys fs)
 	     gdt_blk = sb_blk + 1 + fs->desc_blocks;
 	     rsv_off < sb->s_reserved_gdt_blocks;
 	     rsv_off++, gdt_off++, gdt_blk++) {
-		unsigned int three = 1, five = 5, seven = 7;
-		unsigned int grp, last = 0;
+		dgrp_t three = 1, five = 5, seven = 7;
+		dgrp_t grp, last = 0;
 		int gdt_dirty = 0;
 
 		gdt_off %= apb;
@@ -183,7 +191,7 @@ errcode_t ext2fs_create_resize_inode(ext2_filsys fs)
 			goto out_dindir;
 		}
 
-		while ((grp = list_backups(fs, &three, &five, &seven)) <
+		while ((grp = ext2fs_list_backups(fs, &three, &five, &seven)) <
 		       fs->group_desc_count) {
 			blk_t expect = gdt_blk + grp * sb->s_blocks_per_group;
 
diff --git a/tests/f_boundscheck/expect.1 b/tests/f_boundscheck/expect.1
index c2170b8f9..5c9ead485 100644
--- a/tests/f_boundscheck/expect.1
+++ b/tests/f_boundscheck/expect.1
@@ -1,6 +1,5 @@
 ext2fs_check_desc: Corrupt group descriptor: bad block for inode table
 ../e2fsck/e2fsck: Group descriptors look bad... trying backup blocks...
-../e2fsck/e2fsck: Bad magic number in super-block while using the backup blocks../e2fsck/e2fsck: going back to original superblock
 Note: if several inode or block bitmap blocks or part
 of the inode table require relocation, you may wish to try
 running e2fsck with the '-b 8193' option first.  The problem
diff --git a/tests/f_boundscheck/expect.2 b/tests/f_boundscheck/expect.2
index c2170b8f9..5c9ead485 100644
--- a/tests/f_boundscheck/expect.2
+++ b/tests/f_boundscheck/expect.2
@@ -1,6 +1,5 @@
 ext2fs_check_desc: Corrupt group descriptor: bad block for inode table
 ../e2fsck/e2fsck: Group descriptors look bad... trying backup blocks...
-../e2fsck/e2fsck: Bad magic number in super-block while using the backup blocks../e2fsck/e2fsck: going back to original superblock
 Note: if several inode or block bitmap blocks or part
 of the inode table require relocation, you may wish to try
 running e2fsck with the '-b 8193' option first.  The problem