[PATCH 16/18] Squashfs: don't store large export table indexes in memory

[Phillip Lougher <phillip@squashfs.org.uk>]

When mounting a Squashfs filesystem, the code reads the entire
export table indexes into memory.  Their size is determined by the
number of inodes in the filesystem.  For the maximum inode
count of 2^32, this will allocate and read 32 MiB.

This is an excessive and unnecessary amount of memory because the
indexes do not need to be read into memory in their entirety.  In
addition kmalloc() is used to allocate memory, and this can fail when
large amounts of memory are requested.  Kmalloc() on modern kernels is
usually limited to 4096 KiB.  If panic-on-warn is set, then failure to
allocate memory will result in a kernel panic.

This commit uses a 4 page cache if the size of the export table indexes
are 4 pages in size or larger.  A simple and fast lookup array is
retained where the total index size is less than 4 pages in size, which
is the vast majority of Squashfs filesystems.

Reproducer
==========

The following reproducer will create a Squashfs filesystem with
540,540,568 inodes (540 million files).  This will cause the export
table indexes to exceed 4096 KiB, and the kmalloc() should fail when the
filesystem is mounted.  Due to the large amount of inodes the Squashfs
filesystem reproducer needs to be run on a 64-bit machine with around
60 GiB of memory (or swap).

The latest development Mksquashfs from the GitHub Squashfs-tools
repository also needs to be used.

=====================================================================
#!/bin/bash

finish() {
	popd 2>&1 > /dev/null
	rm -rf $DIR
	exit 1
}

IMG=$PWD/reproducer.sqsh
DIR=$(mktemp -d)

if [ -e $IMG ]; then
	rm $IMG
fi

pushd $DIR 2>&1 > /dev/null

# create 20 million pseudo file links to empty file
touch a
a=0
while [ $a -le 19 ]; do
	b=0
	while [ $b -le 999 ]; do
		c=0
		while [ $c -le 999 ]; do
			echo "x/$a/$b/$c l a" >> file
			(( c ++ ))
		done
		(( b ++ ))
	done
	(( a ++ ))
done

for i in $(seq 1 27); do
	sed "s/x/$i/g" file > pseudo
	echo
	echo Iteration $i - appending 20 million files to Squashfs filesystem
	echo
	if ! mksquashfs - $IMG -pf pseudo -no-hardlinks -pd "d 0777 0 0" -no-recovery -no-progress -comp lz4; then
		echo Appending to Squashfs filesystem failed
		finish
	fi
done

popd 2>&1 > /dev/null
rm -rf $DIR

echo Generated Squashfs filesystem $IMG
=====================================================================

Fixes: 122601408d20c ("Squashfs: export operations")
Signed-off-by: Phillip Lougher <phillip@squashfs.org.uk>
---
 fs/squashfs/export.c           | 142 +++++++++++++++++++++++----------
 fs/squashfs/squashfs.h         |   3 +-
 fs/squashfs/squashfs_fs_sb.h   |   8 +-
 fs/squashfs/squashfs_helpers.h |  28 ++++++-
 fs/squashfs/super.c            |  36 ++++++---
 5 files changed, 158 insertions(+), 59 deletions(-)

diff --git a/fs/squashfs/export.c b/fs/squashfs/export.c
index ad7cc882d789..e672e359ed59 100644
--- a/fs/squashfs/export.c
+++ b/fs/squashfs/export.c
@@ -34,24 +34,64 @@
 #include "squashfs_helpers.h"
 #include "squashfs.h"
 
+s64 squashfs_inode_lookup_start(struct super_block *sb, u32 ino_num)
+{
+	struct squashfs_sb_info *msblk = sb->s_fs_info;
+	s64 start;
+	int err;
+
+	if (msblk->lookup_table_is_cache) {
+		s32 length = squashfs_lookup_blocks_bytes(msblk->inodes);
+		s32 base = squashfs_lookup_blocks_base(ino_num - 1);
+		s16 offset = squashfs_lookup_blocks_offset(ino_num - 1);
+		s32 avail = min_t(int, length - base, PAGE_SIZE);
+		struct squashfs_cache_entry *entry;
+
+		start = squashfs_lookup_blocks_start(ino_num - 1, msblk);
+		if (start < 0)
+			return start;
+
+		entry = squashfs_cache_get(sb, msblk->inode_lookup_cache, start,
+					avail | SQUASHFS_COMPRESSED_BIT_BLOCK);
+		if (entry->error < 0) {
+			err = entry->error;
+			squashfs_cache_put(entry);
+			return err;
+		}
+
+		start = le64_to_cpu(((__le64 *)entry->data[0])[offset >> 3]);
+		squashfs_cache_put(entry);
+	} else {
+		s32 blk = squashfs_lookup_block(ino_num - 1);
+
+		start = le64_to_cpu(msblk->inode_lookup_array[blk]);
+	}
+
+	if (start < msblk->lookup_table_start || start >= msblk->lookup_table)
+		return -EIO;
+
+	return start;
+}
+
 /*
  * Look-up inode number (ino) in table, returning the inode location.
  */
-static long long squashfs_inode_lookup(struct super_block *sb, int ino_num)
+static long long squashfs_inode_lookup(struct super_block *sb, u32 ino_num)
 {
 	struct squashfs_sb_info *msblk = sb->s_fs_info;
-	int blk = squashfs_lookup_block(ino_num - 1);
-	int offset = squashfs_lookup_block_offset(ino_num - 1);
-	u64 start;
+	s32 offset = squashfs_lookup_block_offset(ino_num - 1);
+	s64 start;
 	__le64 ino;
 	int err;
 
-	TRACE("Entered squashfs_inode_lookup, inode_number = %d\n", ino_num);
+	TRACE("Entered squashfs_inode_lookup, inode_number = %u\n", ino_num);
 
 	if (ino_num == 0 || (ino_num - 1) >= msblk->inodes)
 		return -EINVAL;
 
-	start = le64_to_cpu(msblk->inode_lookup_table[blk]);
+	start = squashfs_inode_lookup_start(sb, ino_num);
+	if (start < 0)
+		return start;
 
 	err = squashfs_read_metadata(sb, &ino, &start, &offset, sizeof(ino));
 	if (err < 0)
@@ -113,14 +153,11 @@ static struct dentry *squashfs_get_parent(struct dentry *child)
 /*
  * Read uncompressed inode lookup table indexes off disk into memory
  */
-__le64 *squashfs_read_inode_lookup_table(struct super_block *sb,
+int squashfs_read_inode_lookup_table(struct super_block *sb,
 		u64 lookup_table_start, u64 next_table, unsigned int inodes)
 {
-	unsigned int length = squashfs_lookup_block_bytes(inodes);
-	unsigned int indexes = squashfs_lookup_blocks(inodes);
-	int n;
-	__le64 *table;
-	u64 start, end;
+	struct squashfs_sb_info *msblk = sb->s_fs_info;
+	s32 length = squashfs_lookup_blocks_bytes(inodes);
 
 	TRACE("In read_inode_lookup_table, length %d\n", length);
 
@@ -128,51 +165,68 @@ __le64 *squashfs_read_inode_lookup_table(struct super_block *sb,
 
 	/* there should always be at least one inode */
 	if (inodes == 0)
-		return ERR_PTR(-EINVAL);
+		return -EIO;
 
 	/*
 	 * The computed size of the lookup table (length bytes) should exactly
 	 * match the table start and end points
 	 */
 	if (length != (next_table - lookup_table_start))
-		return ERR_PTR(-EINVAL);
-
-	table = squashfs_read_table(sb, lookup_table_start, length);
-	if (IS_ERR(table))
-		return table;
+		return -EIO;
+
+	if (length <= (PAGE_SIZE * 4)) {
+		/* Read lookup table index into memory */
+		s32 indexes = squashfs_lookup_blocks(inodes);
+		__le64 *array;
+		u64 start, end;
+		int n;
+
+		array = squashfs_read_table(sb, lookup_table_start, length);
+		if (IS_ERR(array))
+			return PTR_ERR(array);
+
+		/*
+		 * array0], array[1], ... array[indexes - 1] store the locations
+		 * of the compressed inode lookup blocks.  Each entry should be
+		 * less than the next (i.e. array[0] < array[1]), and the difference
+		 * between them should be SQUASHFS_METADATA_SIZE or less.
+		 * array[indexes - 1] should  be less than lookup_array_start, and
+		 * again the difference should be SQUASHFS_METADATA_SIZE or less
+		 */
+		for (n = 0; n < (indexes - 1); n++) {
+			start = le64_to_cpu(array[n]);
+			end = le64_to_cpu(array[n + 1]);
+
+			if (start >= end || (end - start) > (SQUASHFS_METADATA_SIZE
+						+ SQUASHFS_BLOCK_OFFSET)) {
+				kfree(array);
+				return -EIO;
+			}
+		}
 
-	/*
-	 * table0], table[1], ... table[indexes - 1] store the locations
-	 * of the compressed inode lookup blocks.  Each entry should be
-	 * less than the next (i.e. table[0] < table[1]), and the difference
-	 * between them should be SQUASHFS_METADATA_SIZE or less.
-	 * table[indexes - 1] should  be less than lookup_table_start, and
-	 * again the difference should be SQUASHFS_METADATA_SIZE or less
-	 */
-	for (n = 0; n < (indexes - 1); n++) {
-		start = le64_to_cpu(table[n]);
-		end = le64_to_cpu(table[n + 1]);
-
-		if (start >= end
-		    || (end - start) >
-		    (SQUASHFS_METADATA_SIZE + SQUASHFS_BLOCK_OFFSET)) {
-			kfree(table);
-			return ERR_PTR(-EINVAL);
+		start = le64_to_cpu(array[indexes - 1]);
+		if (start >= lookup_table_start || (lookup_table_start - start) >
+			    (SQUASHFS_METADATA_SIZE + SQUASHFS_BLOCK_OFFSET)) {
+			kfree(array);
+			return -EIO;
 		}
-	}
 
-	start = le64_to_cpu(table[indexes - 1]);
-	if (start >= lookup_table_start ||
-	    (lookup_table_start - start) >
-	    (SQUASHFS_METADATA_SIZE + SQUASHFS_BLOCK_OFFSET)) {
-		kfree(table);
-		return ERR_PTR(-EINVAL);
+		msblk->inode_lookup_array = array;
+		msblk->lookup_table_is_cache = false;
+	} else {
+		/* Use a cache to store the last 4 pages of indexes read */
+		struct squashfs_cache *cache = squashfs_cache_init("inode index", 4, PAGE_SIZE);
+
+		if (IS_ERR(cache))
+			return PTR_ERR(cache);
+
+		msblk->inode_lookup_cache = cache;
+		msblk->lookup_table_is_cache = true;
 	}
 
-	return table;
+	return 0;
 }
 
-
 const struct export_operations squashfs_export_ops = {
 	.encode_fh = generic_encode_ino32_fh,
 	.fh_to_dentry = squashfs_fh_to_dentry,
diff --git a/fs/squashfs/squashfs.h b/fs/squashfs/squashfs.h
index 4851bd964502..d40d40bd61ae 100644
--- a/fs/squashfs/squashfs.h
+++ b/fs/squashfs/squashfs.h
@@ -64,8 +64,9 @@ extern const struct squashfs_decompressor_thread_ops squashfs_decompressor_percp
 #endif
 
 /* export.c */
-extern __le64 *squashfs_read_inode_lookup_table(struct super_block *, u64, u64,
+extern int squashfs_read_inode_lookup_table(struct super_block *, u64, u64,
 				unsigned int);
+extern s64 squashfs_inode_lookup_start(struct super_block *sb, u32 ino_num);
 
 /* fragment.c */
 extern int squashfs_frag_lookup(struct super_block *, unsigned int, u64 *);
diff --git a/fs/squashfs/squashfs_fs_sb.h b/fs/squashfs/squashfs_fs_sb.h
index 949dab87a241..d6b5908fff51 100644
--- a/fs/squashfs/squashfs_fs_sb.h
+++ b/fs/squashfs/squashfs_fs_sb.h
@@ -64,11 +64,16 @@ struct squashfs_sb_info {
 	struct mutex				meta_index_mutex;
 	struct meta_index			*meta_index;
 	void					*stream;
-	__le64					*inode_lookup_table;
+	union {
+		__le64				*inode_lookup_array;
+		struct squashfs_cache		*inode_lookup_cache;
+	};
 	u64					inode_table;
 	u64					directory_table;
 	u64					directory_table_end;
 	u64					xattr_table;
+	u64					lookup_table;
+	u64					lookup_table_start;
 	unsigned int				block_size;
 	unsigned short				block_log;
 	long long				bytes_used;
@@ -79,5 +84,6 @@ struct squashfs_sb_info {
 	bool					panic_on_errors;
 	const struct squashfs_decompressor_thread_ops *thread_ops;
 	int					max_thread_num;
+	bool					lookup_table_is_cache;
 };
 #endif
diff --git a/fs/squashfs/squashfs_helpers.h b/fs/squashfs/squashfs_helpers.h
index 5250cf7348a3..be8481e808af 100644
--- a/fs/squashfs/squashfs_helpers.h
+++ b/fs/squashfs/squashfs_helpers.h
@@ -135,11 +135,37 @@ static inline s32 squashfs_lookup_blocks(u32 inodes)
 		SQUASHFS_METADATA_SIZE;
 }
 
-static inline s32 squashfs_lookup_block_bytes(u32 inodes)
+static inline s32 squashfs_lookup_blocks_bytes(u32 inodes)
 {
 	return squashfs_lookup_blocks(inodes) * sizeof(long long);
 }
 
+static inline s32 squashfs_lookup_blocks_base(u32 inodes)
+{
+	return (squashfs_lookup_block(inodes) * sizeof(long long)) & ~(PAGE_SIZE - 1);
+}
+
+static inline s64 squashfs_lookup_blocks_start(u32 inodes, struct squashfs_sb_info *msblk)
+{
+	s32 base = squashfs_lookup_blocks_base(inodes);
+	s64 start;
+
+	if (S64_MAX - msblk->lookup_table < base)
+		return -EINVAL;
+
+	start = msblk->lookup_table + base;
+
+	if (start > msblk->bytes_used)
+		return -EINVAL;
+
+	return start;
+}
+
+static inline s16 squashfs_lookup_blocks_offset(u32 inodes)
+{
+	return (squashfs_lookup_block(inodes) * sizeof(long long)) & (PAGE_SIZE - 1);
+}
+
 /* uid lookup table defines */
 static inline s32 squashfs_id_bytes(u16 ids)
 {
diff --git a/fs/squashfs/super.c b/fs/squashfs/super.c
index 8c42f1eb375b..8504939f9a8e 100644
--- a/fs/squashfs/super.c
+++ b/fs/squashfs/super.c
@@ -177,6 +177,13 @@ static const struct squashfs_decompressor *supported_squashfs_filesystem(
 	return decompressor;
 }
 
+static void squashfs_free_inode_table(struct squashfs_sb_info *msblk)
+{
+	if (msblk->lookup_table_is_cache)
+		squashfs_cache_delete(msblk->inode_lookup_cache);
+	else
+		kfree(msblk->inode_lookup_array);
+}
 
 static int squashfs_fill_super(struct super_block *sb, struct fs_context *fc)
 {
@@ -187,8 +194,9 @@ static int squashfs_fill_super(struct super_block *sb, struct fs_context *fc)
 	long long root_inode;
 	unsigned short flags;
 	unsigned int fragments;
-	u64 lookup_table_start, xattr_id_table_start, next_table;
-	int err, devblksize = sb_min_blocksize(sb, SQUASHFS_DEVBLK_SIZE);
+	u64 xattr_id_table_start, next_table;
+	s64 err;
+	int devblksize = sb_min_blocksize(sb, SQUASHFS_DEVBLK_SIZE);
 
 	TRACE("Entered squashfs_fill_superblock\n");
 
@@ -391,20 +399,24 @@ static int squashfs_fill_super(struct super_block *sb, struct fs_context *fc)
 	next_table = le64_to_cpu(msblk->id_table[0]);
 
 	/* Handle inode lookup table */
-	lookup_table_start = le64_to_cpu(sblk->lookup_table_start);
-	if (lookup_table_start == SQUASHFS_INVALID_BLK)
+	msblk->lookup_table = le64_to_cpu(sblk->lookup_table_start);
+	if (msblk->lookup_table == SQUASHFS_INVALID_BLK)
 		goto handle_fragments;
 
 	/* Allocate and read inode lookup table */
-	msblk->inode_lookup_table = squashfs_read_inode_lookup_table(sb,
-		lookup_table_start, next_table, msblk->inodes);
-	if (IS_ERR(msblk->inode_lookup_table)) {
+	err = squashfs_read_inode_lookup_table(sb, msblk->lookup_table,
+			next_table, msblk->inodes);
+	if (err < 0) {
+		errorf(fc, "unable to read inode lookup table");
+		goto failed_mount;
+	}
+
+	err = squashfs_inode_lookup_start(sb, 1);
+	if (err < 0) {
 		errorf(fc, "unable to read inode lookup table");
-		err = PTR_ERR(msblk->inode_lookup_table);
-		msblk->inode_lookup_table = NULL;
 		goto failed_mount;
 	}
-	next_table = le64_to_cpu(msblk->inode_lookup_table[0]);
+	next_table = msblk->lookup_table_start = err;
 
 	sb->s_export_op = &squashfs_export_ops;
 
@@ -480,7 +492,7 @@ static int squashfs_fill_super(struct super_block *sb, struct fs_context *fc)
 	if (msblk->cache_mapping)
 		iput(msblk->cache_mapping->host);
 	msblk->thread_ops->destroy(msblk);
-	kfree(msblk->inode_lookup_table);
+	squashfs_free_inode_table(msblk);
 	kfree(msblk->fragment_index);
 	kfree(msblk->id_table);
 	kfree(msblk->xattr_id_table);
@@ -603,7 +615,7 @@ static void squashfs_put_super(struct super_block *sb)
 		kfree(sbi->id_table);
 		kfree(sbi->fragment_index);
 		kfree(sbi->meta_index);
-		kfree(sbi->inode_lookup_table);
+		squashfs_free_inode_table(sbi);
 		kfree(sbi->xattr_id_table);
 		kfree(sb->s_fs_info);
 		sb->s_fs_info = NULL;
-- 
2.47.3