The original ext3 hash algorithms assumed that variables of type char
were signed, as God and K&R intended. Unfortunately, this assumption
is not true on some architectures. Userspace support for marking
filesystems with non-native signed/unsigned chars was added two years
ago, but the kernel-side support was never added (until now).
Signed-off-by: "Theodore Ts'o" <[email protected]>
Cc: [email protected]
Cc: [email protected]
---
fs/ext3/hash.c | 42 +++++++++++++++++++++++++++++++++---------
fs/ext3/namei.c | 7 +++++++
fs/ext3/super.c | 15 +++++++++++++++
include/linux/ext3_fs.h | 28 +++++++++++++++++++++++++++-
include/linux/ext3_fs_sb.h | 1 +
5 files changed, 83 insertions(+), 10 deletions(-)
diff --git a/fs/ext3/hash.c b/fs/ext3/hash.c
index c30e149..855eacb 100644
--- a/fs/ext3/hash.c
+++ b/fs/ext3/hash.c
@@ -35,11 +35,20 @@ static void TEA_transform(__u32 buf[4], __u32 const in[])
/* The old legacy hash */
-static __u32 dx_hack_hash (const char *name, int len)
+static __u32 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;
@@ -48,10 +57,13 @@ static __u32 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;
@@ -62,7 +74,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;
@@ -95,6 +112,7 @@ int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
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;
@@ -113,13 +131,17 @@ int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
}
switch (hinfo->hash_version) {
+ case DX_HASH_LEGACY_UNSIGNED:
+ unsigned_flag++;
case DX_HASH_LEGACY:
- hash = dx_hack_hash(name, len);
+ hash = dx_hack_hash(name, len, unsigned_flag);
break;
+ case DX_HASH_HALF_MD4_UNSIGNED:
+ unsigned_flag++;
case DX_HASH_HALF_MD4:
p = name;
while (len > 0) {
- str2hashbuf(p, len, in, 8);
+ str2hashbuf(p, len, in, 8, unsigned_flag);
half_md4_transform(buf, in);
len -= 32;
p += 32;
@@ -127,10 +149,12 @@ int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
minor_hash = buf[2];
hash = buf[1];
break;
+ case DX_HASH_TEA_UNSIGNED:
+ unsigned_flag++;
case DX_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/fs/ext3/namei.c b/fs/ext3/namei.c
index de13e91..a688a47 100644
--- a/fs/ext3/namei.c
+++ b/fs/ext3/namei.c
@@ -369,6 +369,8 @@ dx_probe(struct dentry *dentry, struct inode *dir,
goto fail;
}
hinfo->hash_version = root->info.hash_version;
+ if (hinfo->hash_version <= DX_HASH_TEA)
+ hinfo->hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned;
hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed;
if (dentry)
ext3fs_dirhash(dentry->d_name.name, dentry->d_name.len, hinfo);
@@ -637,6 +639,9 @@ int ext3_htree_fill_tree(struct file *dir_file, __u32 start_hash,
dir = dir_file->f_path.dentry->d_inode;
if (!(EXT3_I(dir)->i_flags & EXT3_INDEX_FL)) {
hinfo.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
+ if (hinfo.hash_version <= DX_HASH_TEA)
+ hinfo.hash_version +=
+ EXT3_SB(dir->i_sb)->s_hash_unsigned;
hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
start_hash, start_minor_hash);
@@ -1415,6 +1420,8 @@ static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
/* Initialize as for dx_probe */
hinfo.hash_version = root->info.hash_version;
+ if (hinfo.hash_version <= DX_HASH_TEA)
+ hinfo.hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned;
hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
ext3fs_dirhash(name, namelen, &hinfo);
frame = frames;
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index f38a5af..fa706ea 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -1727,6 +1727,21 @@ static int ext3_fill_super (struct super_block *sb, void *data, int silent)
for (i=0; i < 4; i++)
sbi->s_hash_seed[i] = le32_to_cpu(es->s_hash_seed[i]);
sbi->s_def_hash_version = es->s_def_hash_version;
+ i = le32_to_cpu(es->s_flags);
+ if (i & EXT2_FLAGS_UNSIGNED_HASH)
+ sbi->s_hash_unsigned = 3;
+ else if ((i & EXT2_FLAGS_SIGNED_HASH) == 0) {
+ char c;
+
+ c = (char) 255;
+ if (((int) c) == -1) {
+ es->s_flags |= cpu_to_le32(EXT2_FLAGS_SIGNED_HASH);
+ } else {
+ es->s_flags |= cpu_to_le32(EXT2_FLAGS_UNSIGNED_HASH);
+ sbi->s_hash_unsigned = 3;
+ }
+ sb->s_dirt = 1;
+ }
if (sbi->s_blocks_per_group > blocksize * 8) {
printk (KERN_ERR
diff --git a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
index 8120fa1..57420c8 100644
--- a/include/linux/ext3_fs.h
+++ b/include/linux/ext3_fs.h
@@ -354,6 +354,13 @@ struct ext3_inode {
#define EXT3_ORPHAN_FS 0x0004 /* Orphans being recovered */
/*
+ * Misc. filesystem flags
+ */
+#define EXT2_FLAGS_SIGNED_HASH 0x0001 /* Signed dirhash in use */
+#define EXT2_FLAGS_UNSIGNED_HASH 0x0002 /* Unsigned dirhash in use */
+#define EXT2_FLAGS_TEST_FILESYS 0x0004 /* to test development code */
+
+/*
* Mount flags
*/
#define EXT3_MOUNT_CHECK 0x00001 /* Do mount-time checks */
@@ -487,7 +494,23 @@ struct ext3_super_block {
__u16 s_reserved_word_pad;
__le32 s_default_mount_opts;
__le32 s_first_meta_bg; /* First metablock block group */
- __u32 s_reserved[190]; /* Padding to the end of the block */
+ __le32 s_mkfs_time; /* When the filesystem was created */
+ __le32 s_jnl_blocks[17]; /* Backup of the journal inode */
+ /* 64bit support valid if EXT4_FEATURE_COMPAT_64BIT */
+/*150*/ __le32 s_blocks_count_hi; /* Blocks count */
+ __le32 s_r_blocks_count_hi; /* Reserved blocks count */
+ __le32 s_free_blocks_count_hi; /* Free blocks count */
+ __le16 s_min_extra_isize; /* All inodes have at least # bytes */
+ __le16 s_want_extra_isize; /* New inodes should reserve # bytes */
+ __le32 s_flags; /* Miscellaneous flags */
+ __le16 s_raid_stride; /* RAID stride */
+ __le16 s_mmp_interval; /* # seconds to wait in MMP checking */
+ __le64 s_mmp_block; /* Block for multi-mount protection */
+ __le32 s_raid_stripe_width; /* blocks on all data disks (N*stride)*/
+ __u8 s_log_groups_per_flex; /* FLEX_BG group size */
+ __u8 s_reserved_char_pad2;
+ __le16 s_reserved_pad;
+ __u32 s_reserved[162]; /* Padding to the end of the block */
};
#ifdef __KERNEL__
@@ -692,6 +715,9 @@ static inline __le16 ext3_rec_len_to_disk(unsigned len)
#define DX_HASH_LEGACY 0
#define DX_HASH_HALF_MD4 1
#define DX_HASH_TEA 2
+#define DX_HASH_LEGACY_UNSIGNED 3
+#define DX_HASH_HALF_MD4_UNSIGNED 4
+#define DX_HASH_TEA_UNSIGNED 5
#ifdef __KERNEL__
diff --git a/include/linux/ext3_fs_sb.h b/include/linux/ext3_fs_sb.h
index b65f028..50dc80a 100644
--- a/include/linux/ext3_fs_sb.h
+++ b/include/linux/ext3_fs_sb.h
@@ -57,6 +57,7 @@ struct ext3_sb_info {
u32 s_next_generation;
u32 s_hash_seed[4];
int s_def_hash_version;
+ int s_hash_unsigned; /* 3 if hash should be signed, 0 if not */
struct percpu_counter s_freeblocks_counter;
struct percpu_counter s_freeinodes_counter;
struct percpu_counter s_dirs_counter;
--
1.5.6.1.205.ge2c7.dirty
On Monday 20 October 2008 20:43, Theodore Ts'o wrote:
> The original ext3 hash algorithms assumed that variables of type char
> were signed, as God and K&R intended.
But I didn't. Sorry about that, it was a dumb oversight.
Regards,
Daniel
On Monday 20 October 2008 20:43, Theodore Ts'o wrote:
> +static __u32 dx_hack_hash (const char *name, int len, int unsigned_flag)
> ...
> + if (unsigned_flag)
> + c = (int) *ucp++;
> + else
> + c = (int) *scp++;
This being a high performance hash function and all, why not something
like:
+static __u32 uchar_hack_hash (const char *name, int len)
+...
+static __u32 char_hack_hash (const char *name, int len)
+...
+static __u32 dx_hack_hash(const char *name, int len, int unsigned_flag)
+{
+ if (unsigned_flag)
+ return uchar_hack_hash(name, len);
+ return char_hack_hash(name, len);
+}
Excuse me,
> +static __u32 uchar_hack_hash (const char *name, int len)
I meant:
+static __u32 uchar_hack_hash(const unsigned char *name, int len)
Regards
Daniel
On Mon, 2008-10-20 at 23:43 -0400, Theodore Ts'o wrote:
> The original ext3 hash algorithms assumed that variables of type char
> were signed, as God and K&R intended. Unfortunately, this assumption
> is not true on some architectures. Userspace support for marking
> filesystems with non-native signed/unsigned chars was added two years
> ago, but the kernel-side support was never added (until now).
>
> Signed-off-by: "Theodore Ts'o" <[email protected]>
> Cc: [email protected]
> Cc: [email protected]
> ---
> fs/ext3/hash.c | 42 +++++++++++++++++++++++++++++++++---------
> fs/ext3/namei.c | 7 +++++++
> fs/ext3/super.c | 15 +++++++++++++++
> include/linux/ext3_fs.h | 28 +++++++++++++++++++++++++++-
> include/linux/ext3_fs_sb.h | 1 +
> 5 files changed, 83 insertions(+), 10 deletions(-)
>
> diff --git a/fs/ext3/hash.c b/fs/ext3/hash.c
> index c30e149..855eacb 100644
> --- a/fs/ext3/hash.c
> +++ b/fs/ext3/hash.c
> @@ -35,11 +35,20 @@ static void TEA_transform(__u32 buf[4], __u32 const in[])
>
>
> /* The old legacy hash */
> -static __u32 dx_hack_hash (const char *name, int len)
> +static __u32 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++;
Branch in the inner loop? Space after typecast?
> 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);
And here.
--
Mathematics is the supreme nostalgia of our time.
On Mon, 20 Oct 2008 23:43:44 -0400
"Theodore Ts'o" <[email protected]> wrote:
> + i = le32_to_cpu(es->s_flags);
> + if (i & EXT2_FLAGS_UNSIGNED_HASH)
> + sbi->s_hash_unsigned = 3;
> + else if ((i & EXT2_FLAGS_SIGNED_HASH) == 0) {
> + char c;
> +
> + c = (char) 255;
> + if (((int) c) == -1) {
arm says
fs/ext3/super.c: In function `ext3_fill_super':
fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
Also, is there any way in which this new code can be, umm, cleaned up?
On Wed, Oct 22, 2008 at 05:22:21PM -0700, Andrew Morton wrote:
> > + if (((int) c) == -1) {
>
> arm says
>
> fs/ext3/super.c: In function `ext3_fill_super':
> fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
>
> Also, is there any way in which this new code can be, umm, cleaned up?
Hmm..... is it considered safe to depend on the userspace limits.h
header file? I guess if we trust that header file to be correct we
could check the value of CHAR_MIN and/or CHAR_MAX as defined by
limits.h.
Alternatively we could do an #ifdef __CHAR_UNSIGNED__, which is
defined by gcc. The manual for gcc tells us not to depend on it, but
to depend on limits.h instead.
Any thoughts, or comments? Does anyone know if the Intel compiler
will DTRT with either of these approaches?
- Ted
On Oct 22, 2008 22:56 -0400, Theodore Ts'o wrote:
> On Wed, Oct 22, 2008 at 05:22:21PM -0700, Andrew Morton wrote:
> > arm says
> >
> > fs/ext3/super.c: In function `ext3_fill_super':
> > fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
> >
> > Also, is there any way in which this new code can be, umm, cleaned up?
>
> Hmm..... is it considered safe to depend on the userspace limits.h
> header file? I guess if we trust that header file to be correct we
> could check the value of CHAR_MIN and/or CHAR_MAX as defined by
> limits.h.
That would likely fail on cross-compiled environments, right?
> Alternatively we could do an #ifdef __CHAR_UNSIGNED__, which is
> defined by gcc. The manual for gcc tells us not to depend on it, but
> to depend on limits.h instead.
This warning likely is aimed at userspace for portable applications.
> Any thoughts, or comments? Does anyone know if the Intel compiler
> will DTRT with either of these approaches?
If it doesn't, then it probably has some equivalent that can be #ifdef'd
in its place.
Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.
Andreas Dilger wrote:
>
>> Hmm..... is it considered safe to depend on the userspace limits.h
>> header file? I guess if we trust that header file to be correct we
>> could check the value of CHAR_MIN and/or CHAR_MAX as defined by
>> limits.h.
>>
>
> That would likely fail on cross-compiled environments, right?
>
/usr/include/limits.h uses #include_next to pick up gcc's private
limits.h, so it should be safe to use in a kernel cross-build
environment. (Picking up the compiler's limits.h directly would be better.)
J
I've added Tony Luck to the CC list since as the Itanium maintainer,
he's most likely to be able to speak to both cross compilation issues
especially as it relates to the Intel Compiler....
Tony, Andrew has requested I clean up this compile-time test to
determine whether variables of type char are signed or unsigned:
char c;
...
c = (char) 255;
if (((int) c) == -1) {
...
}
... since it results in this annoying gcc warning:
> fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
Two possible solutions which come to mind is to use the C preprocessor
macros CHAR_MIN/CHAR_MAX as defined in limits.h, or to use
__CHAR_UNSIGNED__ which is defined by gcc on platforms where char's
are unsigned (or if the gcc option --funsigned-char is given).
I believe at this point, it's settled that either of the above
solutions should do the right thing for gcc, either in
cross-compilation environments, or natively. (I prefer
__CHAR_UNSIGNED__ since it doesn't depend on the userspace header
files, which might be screwy on some distributions, and depending on a
macro set by gcc seems much more robust in cross-compilation
environments.)
The question is whether this solution is likely to work on the Intel C
compiler. My understanding is that a kernel compiled with gcc is
pathetically slow on the Itanic (not to mention taking aeons to
compile), and so there has always been a desire to make sure that the
Linux Kernel will compile on the Intel C compiler, at least for the
Intanium platform. Do you know if icc will do the right thing as far
as defining __CHAR_UNSIGNED__ if necessary?
I don't even know if the Itanium is one of those wierd-sh*t platforms
that tried to make char's unsigned, one of those really horrific
design decisions perpetrated by the Arm and PowerPC platforms since it
tends to break compatibility with K&R C which doesn't even have a
signed keyword (and for which char's were always signed). If it's one
of the sane platforms, then this might not matter so much.
Thanks,
- Ted
> I've added Tony Luck to the CC list since as the Itanium maintainer,
> he's most likely to be able to speak to both cross compilation issues
> especially as it relates to the Intel Compiler....
Sorry to disappoint ... but I'm not an expert on cross compilation (I
run all my builds natively) or on the Intel compiler (I just use gcc).
> Tony, Andrew has requested I clean up this compile-time test to
> determine whether variables of type char are signed or unsigned:
> char c;
> ...
> c = (char) 255;
> if (((int) c) == -1) {
> ...
> }
> ... since it results in this annoying gcc warning:
> > fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
I don't see any code like this near line 1750 of fs/ext3/super.c so
I guess the offending lines have been moved up or down by recent
changes.
> Two possible solutions which come to mind is to use the C preprocessor
> macros CHAR_MIN/CHAR_MAX as defined in limits.h, or to use
> __CHAR_UNSIGNED__ which is defined by gcc on platforms where char's
> are unsigned (or if the gcc option --funsigned-char is given).
> I believe at this point, it's settled that either of the above
> solutions should do the right thing for gcc, either in
> cross-compilation environments, or natively. (I prefer
> __CHAR_UNSIGNED__ since it doesn't depend on the userspace header
> files, which might be screwy on some distributions, and depending on a
> macro set by gcc seems much more robust in cross-compilation
> environments.)
Either option seems OK to me. char is signed on Itanium, so
the Intel compiler doesn't need to provide __CHAR_UNSIGNED__.
> The question is whether this solution is likely to work on the Intel C
> compiler. My understanding is that a kernel compiled with gcc is
> pathetically slow on the Itanic (not to mention taking aeons to
> compile), and so there has always been a desire to make sure that the
> Linux Kernel will compile on the Intel C compiler, at least for the
> Intanium platform. Do you know if icc will do the right thing as far
> as defining __CHAR_UNSIGNED__ if necessary?
The Linux kernel doesn't benefit hugely from being compiled by the
Intel compiler ... there just aren't that many loops that run
for many iterations, no floating point code, and little else that
can benefit. I challenge the "aeons to compile" claim too. Most
of the config files I build take about 2 minutes each (and this is
on a basic 4-socket machine ... not on a giant SGI box). Not
great by the "5 seconds to build" that Linus mentioned at KS,
but hardly "aeons".
> I don't even know if the Itanium is one of those wierd-sh*t platforms
> that tried to make char's unsigned, one of those really horrific
> design decisions perpetrated by the Arm and PowerPC platforms since it
"char" defaults to signed on Itanium (so in this respect at least it is
a "sane" architecture :-)
> tends to break compatibility with K&R C which doesn't even have a
> signed keyword (and for which char's were always signed). If it's one
> of the sane platforms, then this might not matter so much.
This is incorrect. K&R (first edition, (c) 1978) says (p. 183):
"6.1 Characters and integers
...
Whether or not sign-extension occurs for characters is machine
dependent, but it is guaranteed that a member of the standard
character set is non-negative. Of the machines treated by this
manual, only the PDP-11 sign-extends."
-Tony
Theodore Tso writes:
> On Wed, Oct 22, 2008 at 05:22:21PM -0700, Andrew Morton wrote:
>> > + if (((int) c) == -1) {
>>
>> arm says
>>
>> fs/ext3/super.c: In function `ext3_fill_super':
>> fs/ext3/super.c:1750: warning: comparison is always false due to limited range of data type
>>
>> Also, is there any way in which this new code can be, umm, cleaned up?
> Hmm..... is it considered safe to depend on the userspace limits.h
> header file? I guess if we trust that header file to be correct we
> could check the value of CHAR_MIN and/or CHAR_MAX as defined by
> limits.h.
> Alternatively we could do an #ifdef __CHAR_UNSIGNED__, which is
> defined by gcc. The manual for gcc tells us not to depend on it, but
> to depend on limits.h instead.
> Any thoughts, or comments? Does anyone know if the Intel compiler
> will DTRT with either of these approaches?
Why not write the test like this?
if ((char)-1 > 0) {
/* char is unsigned */
} else {
/* char is signed */
}
--
Olaf Weber