Add directory hashed signed/unsigned hint to superblock

The e2fsprogs and kernel implementation of directory hash tree has a
bug which causes the implementation to be dependent on whether
characters are signed or unsigned.  Platforms such as the PowerPC,
Arm, and S/390 have signed characters by default, which means that
hash directories on those systems are incompatible with hash
directories on other systems, such as the x86.

To fix this we add a new flags field to the superblock, and define two
new bits in that field to indicate whether or not the directory should
be signed or unsigned.  If the bits are not set, e2fsck and fixed
kernels will set them to the signed/unsigned value of the currently
running platform, and then respect those bits when calculating the
directory hash.  This allows compatibility with current filesystems,
as well as allowing cross-architectural compatibility.

Addresses Debian Bug: #389772

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

5 files changed, 70 insertions, 13 deletions

diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog
index 3453d686..51a2f3ae 100644
--- a/lib/ext2fs/ChangeLog
+++ b/lib/ext2fs/ChangeLog
@@ -1,5 +1,19 @@
 2006-11-11  Theodore Tso  <tytso@mit.edu>
 
+	* dirhash.c (str2hashbuf, ext2fs_dirhash): Add support for
+		calculating the unsigned version of the directory hash.
+
+	* initialize.c (ext2fs_initialize): Set the dirhash
+		signed/unsigned hint in s_flags.
+
+	* swapfs.c (ext2fs_swap_super): Byte swap the s_flags superblock
+		field.
+
+	* ext2_fs.h: Define a new superblock field, s_flags, which is used
+		to store a signed vs. unsigned dirhash hint.  Define new
+		HTREE hash algorithm numbers to pass to userspace if the
+		unsigned algorithm are required.
+
 	* swapfs.c (ext2fs_swap_super):
 	  ext2_fs.h: Add definition of EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE,
 	  	which adds s_min_extra_isize and s_want_extra_isize fields
diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c
index 4d18593f..9fd20160 100644
--- a/lib/ext2fs/dirhash.c
+++ b/lib/ext2fs/dirhash.c
@@ -116,11 +116,20 @@ static void halfMD4Transform (__u32 buf[4], __u32 const in[])
 #undef K3
 
 /* The old legacy hash */
-static ext2_dirhash_t dx_hack_hash (const char *name, int len)
+static ext2_dirhash_t dx_hack_hash (const char *name, int len,
+				    int unsigned_flag)
 {
-	__u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
+	__u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
+	const unsigned char *ucp = (const unsigned char *) name;
+	const signed char *scp = (const signed char *) name;
+	int c;
+
 	while (len--) {
-		__u32 hash = hash1 + (hash0 ^ (*name++ * 7152373));
+		if (unsigned_flag)
+			c = (int) *ucp++;
+		else
+			c = (int) *scp++;
+		hash = hash1 + (hash0 ^ (c * 7152373));
 		
 		if (hash & 0x80000000) hash -= 0x7fffffff;
 		hash1 = hash0;
@@ -129,10 +138,13 @@ static ext2_dirhash_t dx_hack_hash (const char *name, int len)
 	return (hash0 << 1);
 }
 
-static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
+static void str2hashbuf(const char *msg, int len, __u32 *buf, int num,
+			int unsigned_flag)
 {
 	__u32	pad, val;
-	int	i;
+	int	i, c;
+	const unsigned char *ucp = (const unsigned char *) msg;
+	const signed char *scp = (const signed char *) msg;
 
 	pad = (__u32)len | ((__u32)len << 8);
 	pad |= pad << 16;
@@ -143,7 +155,12 @@ static void str2hashbuf(const char *msg, int len, __u32 *buf, int num)
 	for (i=0; i < len; i++) {
 		if ((i % 4) == 0)
 			val = pad;
-		val = msg[i] + (val << 8);
+		if (unsigned_flag)
+			c = (int) ucp[i];
+		else
+			c = (int) scp[i];
+
+		val = c + (val << 8);
 		if ((i % 4) == 3) {
 			*buf++ = val;
 			val = pad;
@@ -179,6 +196,7 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
 	const char	*p;
 	int		i;
 	__u32 		in[8], buf[4];
+	int		unsigned_flag = 0;
 
 	/* Initialize the default seed for the hash checksum functions */
 	buf[0] = 0x67452301;
@@ -197,13 +215,17 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
 	}
 		
 	switch (version) {
+	case EXT2_HASH_LEGACY_UNSIGNED:
+		unsigned_flag++;
 	case EXT2_HASH_LEGACY:
-		hash = dx_hack_hash(name, len);
+		hash = dx_hack_hash(name, len, unsigned_flag);
 		break;
+	case EXT2_HASH_HALF_MD4_UNSIGNED:
+		unsigned_flag++;
 	case EXT2_HASH_HALF_MD4:
 		p = name;
 		while (len > 0) {
-			str2hashbuf(p, len, in, 8);
+			str2hashbuf(p, len, in, 8, unsigned_flag);
 			halfMD4Transform(buf, in);
 			len -= 32;
 			p += 32;
@@ -211,10 +233,12 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
 		minor_hash = buf[2];
 		hash = buf[1];
 		break;
+	case EXT2_HASH_TEA_UNSIGNED:
+		unsigned_flag++;
 	case EXT2_HASH_TEA:
 		p = name;
 		while (len > 0) {
-			str2hashbuf(p, len, in, 4);
+			str2hashbuf(p, len, in, 4, unsigned_flag);
 			TEA_transform(buf, in);
 			len -= 16;
 			p += 16;
diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
index 61958d90..0203636c 100644
--- a/lib/ext2fs/ext2_fs.h
+++ b/lib/ext2fs/ext2_fs.h
@@ -193,9 +193,12 @@ struct ext2_dx_root_info {
 	__u8 unused_flags;
 };
 
-#define EXT2_HASH_LEGACY	0
-#define EXT2_HASH_HALF_MD4	1
-#define EXT2_HASH_TEA		2
+#define EXT2_HASH_LEGACY		0
+#define EXT2_HASH_HALF_MD4		1
+#define EXT2_HASH_TEA			2
+#define EXT2_HASH_LEGACY_UNSIGNED	3 /* reserved for userspace lib */
+#define EXT2_HASH_HALF_MD4_UNSIGNED	4 /* reserved for userspace lib */
+#define EXT2_HASH_TEA_UNSIGNED		5 /* reserved for userspace lib */
 
 #define EXT2_HASH_FLAG_INCOMPAT	0x1
 
@@ -449,6 +452,12 @@ struct ext2_inode_large {
 #define EXT2_ERROR_FS			0x0002	/* Errors detected */
 
 /*
+ * Misc. filesystem flags
+ */
+#define EXT2_FLAGS_SIGNED_HASH		0x0001  /* Signed dirhash in use */
+#define EXT2_FLAGS_UNSIGNED_HASH	0x0002  /* Unsigned dirhash in use */
+
+/*
  * Mount flags
  */
 #define EXT2_MOUNT_CHECK		0x0001	/* Do mount-time checks */
@@ -557,7 +566,8 @@ struct ext2_super_block {
 	__u32	s_free_blocks_hi; 	/* Free blocks count */
 	__u16	s_min_extra_isize;	/* All inodes have at least # bytes */
 	__u16	s_want_extra_isize; 	/* New inodes should reserve # bytes */
-	__u32	s_reserved[168];	/* Padding to the end of the block */
+	__u32	s_flags;		/* Miscellaneous flags */
+	__u32	s_reserved[167];	/* Padding to the end of the block */
 };
 
 /*
diff --git a/lib/ext2fs/initialize.c b/lib/ext2fs/initialize.c
index 98351f8c..9cc3d121 100644
--- a/lib/ext2fs/initialize.c
+++ b/lib/ext2fs/initialize.c
@@ -105,6 +105,7 @@ errcode_t ext2fs_initialize(const char *name, int flags,
 	int		rsv_gdt;
 	int		io_flags;
 	char		*buf;
+	char		c;
 
 	if (!param || !param->s_blocks_count)
 		return EXT2_ET_INVALID_ARGUMENT;
@@ -373,6 +374,13 @@ ipg_retry:
 		fs->group_desc[i].bg_used_dirs_count = 0;
 	}
 	
+	c = (char) 255;
+	if (((int) c) == -1) {
+		super->s_flags |= EXT2_FLAGS_SIGNED_HASH;
+	} else {
+		super->s_flags |= EXT2_FLAGS_UNSIGNED_HASH;
+	}
+
 	ext2fs_mark_super_dirty(fs);
 	ext2fs_mark_bb_dirty(fs);
 	ext2fs_mark_ib_dirty(fs);
diff --git a/lib/ext2fs/swapfs.c b/lib/ext2fs/swapfs.c
index 54a79252..90ba6f1a 100644
--- a/lib/ext2fs/swapfs.c
+++ b/lib/ext2fs/swapfs.c
@@ -69,6 +69,7 @@ void ext2fs_swap_super(struct ext2_super_block * sb)
 	sb->s_free_blocks_hi = ext2fs_swab32(sb->s_free_blocks_hi);
 	sb->s_min_extra_isize = ext2fs_swab16(sb->s_min_extra_isize);
 	sb->s_want_extra_isize = ext2fs_swab16(sb->s_want_extra_isize);
+	sb->s_flags = ext2fs_swab32(sb->s_flags);
 	for (i=0; i < 4; i++)
 		sb->s_hash_seed[i] = ext2fs_swab32(sb->s_hash_seed[i]);
 	for (i=0; i < 17; i++)