This has survived some very basic testing (creating a test file system,
placing 100K files in the root directory, unmount, remount, finding
a few, e2fsck, debugfs...), so I'll throw it out here for the usual
style kibitzing.
Note that the first 5 patches in the series are to the Linux kernel
tree, while the second 5 are to the e2fsprogs tree. Is there a
convention for that sort of thing?
This makes it easier to add additional hash algorithms in future.
Signed-off-by: George Spelvin <[email protected]>
---
fs/ext4/ext4.h | 17 +++++++++++++----
fs/ext4/super.c | 7 ++++---
2 files changed, 17 insertions(+), 7 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 1bbe7c31..cda8dd9c 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1216,7 +1216,7 @@ struct ext4_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 */
+ int s_hash_unsigned; /* DX_HASH_UNSIGNED_DELTA, or 0 if signed */
struct percpu_counter s_freeclusters_counter;
struct percpu_counter s_freeinodes_counter;
struct percpu_counter s_dirs_counter;
@@ -1737,9 +1737,18 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
#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
+
+/*
+ * For historical reasons, the first three hash algorithms
+ * have signed and unsigned variants. So, for internal
+ * use only, define some extra values outside the range of
+ * what's allowed on disk.
+ */
+#define DX_HASH_UNSIGNED_DELTA 3
+
+#define DX_HASH_LEGACY_UNSIGNED (DX_HASH_LEGACY + DX_HASH_UNSIGNED_DELTA)
+#define DX_HASH_HALF_MD4_UNSIGNED (DX_HASH_HALF_MD4 + DX_HASH_UNSIGNED_DELTA)
+#define DX_HASH_TEA_UNSIGNED (DX_HASH_TEA + DX_HASH_UNSIGNED_DELTA)
static inline u32 ext4_chksum(struct ext4_sb_info *sbi, u32 crc,
const void *address, unsigned int length)
diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index 4566c2fe..6eb2c47a 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -3721,16 +3721,17 @@ static int ext4_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;
- if (EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX)) {
+ if (sbi->s_def_hash_version <= DX_HASH_TEA &&
+ EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX)) {
i = le32_to_cpu(es->s_flags);
if (i & EXT2_FLAGS_UNSIGNED_HASH)
- sbi->s_hash_unsigned = 3;
+ sbi->s_hash_unsigned = DX_HASH_UNSIGNED_DELTA;
else if ((i & EXT2_FLAGS_SIGNED_HASH) == 0) {
#ifdef __CHAR_UNSIGNED__
if (!(sb->s_flags & MS_RDONLY))
es->s_flags |=
cpu_to_le32(EXT2_FLAGS_UNSIGNED_HASH);
- sbi->s_hash_unsigned = 3;
+ sbi->s_hash_unsigned = DX_HASH_UNSIGNED_DELTA;
#else
if (!(sb->s_flags & MS_RDONLY))
es->s_flags |=
--
2.1.0
Minor cleanup as long as I'm messing about in the area.
Signed-off-by: George Spelvin <[email protected]>
---
The str2hashbuf declaration generates a checkpatch warning. False positive?
fs/ext4/hash.c | 19 ++++++++-----------
1 file changed, 8 insertions(+), 11 deletions(-)
diff --git a/fs/ext4/hash.c b/fs/ext4/hash.c
index 3d586f02..5186e09a 100644
--- a/fs/ext4/hash.c
+++ b/fs/ext4/hash.c
@@ -140,11 +140,10 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
{
__u32 hash;
__u32 minor_hash = 0;
- const char *p;
- int i;
- __u32 in[8], buf[4];
- void (*str2hashbuf)(const char *, int, __u32 *, int) =
- str2hashbuf_signed;
+ int i;
+ __u32 in[8], buf[4];
+ void (*str2hashbuf)(const char *, int, __u32 *, int) =
+ str2hashbuf_signed;
/* Initialize the default seed for the hash checksum functions */
buf[0] = 0x67452301;
@@ -172,12 +171,11 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
case DX_HASH_HALF_MD4_UNSIGNED:
str2hashbuf = str2hashbuf_unsigned;
case DX_HASH_HALF_MD4:
- p = name;
while (len > 0) {
- (*str2hashbuf)(p, len, in, 8);
+ (*str2hashbuf)(name, len, in, 8);
half_md4_transform(buf, in);
len -= 32;
- p += 32;
+ name += 32;
}
minor_hash = buf[2];
hash = buf[1];
@@ -185,12 +183,11 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
case DX_HASH_TEA_UNSIGNED:
str2hashbuf = str2hashbuf_unsigned;
case DX_HASH_TEA:
- p = name;
while (len > 0) {
- (*str2hashbuf)(p, len, in, 4);
+ (*str2hashbuf)(name, len, in, 4);
TEA_transform(buf, in);
len -= 16;
- p += 16;
+ name += 16;
}
hash = buf[0];
minor_hash = buf[1];
--
2.1.0
The prototypes obviously didn't make sense.
Signed-off-by: George Spelvin <[email protected]>
Cc: David Howells <[email protected]>
---
I'm not sure who to submit this through. Obviously, it's
hardly a critical bug fix, but it's potentially confusing.
include/linux/byteorder/generic.h | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/include/linux/byteorder/generic.h b/include/linux/byteorder/generic.h
index 0846e6b9..37b3d9d6 100644
--- a/include/linux/byteorder/generic.h
+++ b/include/linux/byteorder/generic.h
@@ -70,12 +70,12 @@
* [bl]eXX_to_cpu(__uXX x)
*
* The same, but takes a pointer to the value to convert
- * cpu_to_[bl]eXXp(__uXX x)
- * [bl]eXX_to_cpup(__uXX x)
+ * cpu_to_[bl]eXXp(const __uXX *x)
+ * [bl]eXX_to_cpup(const __uXX *x)
*
* The same, but change in situ
- * cpu_to_[bl]eXXs(__uXX x)
- * [bl]eXX_to_cpus(__uXX x)
+ * cpu_to_[bl]eXXs(__uXX *x)
+ * [bl]eXX_to_cpus(__uXX *x)
*
* See asm-foo/byteorder.h for examples of how to provide
* architecture-optimized versions
--
2.1.0
SipHash is a fast keyed hash function for short
inputs such as symbol tables and filenames. It's
designed to prevent hash flooding DoS attacks.
This implements SipHash-2-4, the high-speed variant.
For now, ext3/4 are the only users, and the way the seed[] array
is passed is slightly idiosyncratic for their convenience.
Signed-off-by: George Spelvin <[email protected]>
---
If anyone has any better ideas for the seed-passing convention, I'm
all ears. For now, I've left it as is with plenty of warnings.
include/linux/cryptohash.h | 19 +++++++
lib/Makefile | 2 +-
lib/siphash.c | 131 +++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 151 insertions(+), 1 deletion(-)
create mode 100644 lib/siphash.c
diff --git a/include/linux/cryptohash.h b/include/linux/cryptohash.h
index 2cd9f1cf..6b043780 100644
--- a/include/linux/cryptohash.h
+++ b/include/linux/cryptohash.h
@@ -1,6 +1,8 @@
#ifndef __CRYPTOHASH_H
#define __CRYPTOHASH_H
+#include <linux/compiler.h>
+
#define SHA_DIGEST_WORDS 5
#define SHA_MESSAGE_BYTES (512 /*bits*/ / 8)
#define SHA_WORKSPACE_WORDS 16
@@ -15,4 +17,21 @@ void md5_transform(__u32 *hash, __u32 const *in);
__u32 half_md4_transform(__u32 buf[4], __u32 const in[8]);
+/*
+ * Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash-2-4.
+ *
+ * Takes an arbitrary-length byte string, returns a 64-bit hash value.
+ * Extremely fast on 64-bit machines. Faster than half_md4_transform
+ * even on 32-bit machines.
+ *
+ * The fact that the seed is in the form of 4x32-bit words rather
+ * 2x64-bit, and NULL is a synonym for all-zero, is a convenience
+ * to the ext3/ext4 code which is the only current user.
+ *
+ * If it's used for internal hashing with a non-public seed, details
+ * like endianness don't matter. If it's going to be used for something
+ * longer-term, please feel free to revise the interface.
+ */
+__u64 __pure siphash24(char const *in, size_t len, __u32 const seed[4]);
+
#endif
diff --git a/lib/Makefile b/lib/Makefile
index f9a647d3..56d0e35b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -26,7 +26,7 @@ obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
gcd.o lcm.o list_sort.o uuid.o flex_array.o iovec.o clz_ctz.o \
bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o kfifo.o \
- percpu-refcount.o percpu_ida.o hash.o
+ percpu-refcount.o percpu_ida.o hash.o siphash.o
obj-y += string_helpers.o
obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
obj-y += kstrtox.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 00000000..77e8fb4f
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,131 @@
+#include <linux/bitops.h> /* For rol64 */
+#include <linux/cryptohash.h>
+#include <asm/byteorder.h>
+#include <asm/unaligned.h>
+
+/* The basic ARX mixing function, taken from Skein */
+#define SIP_MIX(a, b, s) ((a) += (b), (b) = rol64(b, s), (b) ^= (a))
+
+/*
+ * The complete SipRound. Note that, when unrolled twice like below,
+ * the 32-bit rotates drop out on 32-bit machines.
+ */
+#define SIP_ROUND(a, b, c, d) \
+ (SIP_MIX(a, b, 13), SIP_MIX(c, d, 16), (a) = rol64(a, 32), \
+ SIP_MIX(c, b, 17), SIP_MIX(a, d, 21), (c) = rol64(c, 32))
+
+/*
+ * This is rolled up more than most implementations, resulting in about
+ * 55% the code size. Speed is a few precent slower. A crude benchmark
+ * (for (i=1; i <= max; i++) for (j = 0; j < 4096-i; j++) hash(buf+j, i);)
+ * produces the following timings (in usec):
+ *
+ * i386 i386 i386 x86_64 x86_64 x86_64 x86_64
+ * Length small unroll halfmd4 small unroll halfmd4 teahash
+ * 1..4 1069 1029 1608 195 160 399 690
+ * 1..8 2483 2381 3851 410 360 988 1659
+ * 1..12 4303 4152 6207 690 618 1642 2690
+ * 1..16 6122 5931 8668 968 876 2363 3786
+ * 1..20 8348 8137 11245 1323 1185 3162 5567
+ * 1..24 10580 10327 13935 1657 1504 4066 7635
+ * 1..28 13211 12956 16803 2069 1871 5028 9759
+ * 1..32 15843 15572 19725 2470 2260 6084 11932
+ * 1..36 18864 18609 24259 2934 2678 7566 14794
+ * 1..1024 5890194 6130242 10264816 881933 881244 3617392 7589036
+ *
+ * The performance penalty is quite minor, decreasing for long strings,
+ * and it's significantly faster than half_md4, so I'm going for the
+ * I-cache win.
+ */
+uint64_t
+siphash24(char const *in, size_t len, uint32_t const seed[4])
+{
+ uint64_t a = 0x736f6d6570736575; /* somepseu */
+ uint64_t b = 0x646f72616e646f6d; /* dorandom */
+ uint64_t c = 0x6c7967656e657261; /* lygenera */
+ uint64_t d = 0x7465646279746573; /* tedbytes */
+ uint64_t m = 0;
+ uint8_t padbyte = len;
+
+ /*
+ * Mix in the 128-bit hash seed. This is in a format convenient
+ * to the ext3/ext4 code. Please feel free to adapt the
+ * */
+ if (seed) {
+ m = seed[2] | (uint64_t)seed[3] << 32;
+ b ^= m;
+ d ^= m;
+ m = seed[0] | (uint64_t)seed[1] << 32;
+ /* a ^= m; is done in loop below */
+ c ^= m;
+ }
+
+ /*
+ * By using the same SipRound code for all iterations, we
+ * save space, at the expense of some branch prediction. But
+ * branch prediction is hard because of variable length anyway.
+ */
+ len = len/8 + 3; /* Now number of rounds to perform */
+ do {
+ a ^= m;
+
+ switch (--len) {
+ unsigned bytes;
+
+ default: /* Full words */
+ d ^= m = get_unaligned_le64(in);
+ in += 8;
+ break;
+ case 2: /* Final partial word */
+ /*
+ * We'd like to do one 64-bit fetch rather than
+ * mess around with bytes, but reading past the end
+ * might hit a protection boundary. Fortunately,
+ * we know that protection boundaries are aligned,
+ * so we can consider only three cases:
+ * - The remainder occupies zero words
+ * - The remainder fits into one word
+ * - The remainder straddles two words
+ */
+ bytes = padbyte & 7;
+
+ if (bytes == 0) {
+ m = 0;
+ } else {
+ unsigned offset = (unsigned)(uintptr_t)in & 7;
+
+ if (offset + bytes <= 8) {
+ m = le64_to_cpup((uint64_t const *)
+ (in - offset));
+ m >>= 8*offset;
+ } else {
+ m = get_unaligned_le64(in);
+ }
+ m &= ((uint64_t)1 << 8*bytes) - 1;
+ }
+ /* Could use | or +, but ^ allows associativity */
+ d ^= m ^= (uint64_t)padbyte << 56;
+ break;
+ case 1: /* Beginning of finalization */
+ m = 0;
+ c ^= 0xff;
+ /*FALLTHROUGH*/
+ case 0: /* Second half of finalization */
+ break;
+ }
+
+ SIP_ROUND(a, b, c, d);
+ SIP_ROUND(a, b, c, d);
+ } while (len);
+
+ return a ^ b ^ c ^ d;
+}
+
+#undef SIP_ROUND
+#undef SIP_MIX
+
+/*
+ * No objection to EXPORT_SYMBOL, but we should probably figure out
+ * how the seed[] array should work first. Homework for the first
+ * person to want to call it from a module!
+ */
--
2.1.0
This uses SipHash-2-4 for directory hashing.
Signed-off-by: George Spelvin <[email protected]>
---
The actual feature. Pretty simple, no?
fs/ext4/ext4.h | 3 ++-
fs/ext4/hash.c | 6 ++++++
fs/ext4/namei.c | 3 ++-
3 files changed, 10 insertions(+), 2 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index cda8dd9c..13420bd4 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1737,6 +1737,7 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
#define DX_HASH_LEGACY 0
#define DX_HASH_HALF_MD4 1
#define DX_HASH_TEA 2
+#define DX_HASH_SIPHASH24 3
/*
* For historical reasons, the first three hash algorithms
@@ -1744,7 +1745,7 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
* use only, define some extra values outside the range of
* what's allowed on disk.
*/
-#define DX_HASH_UNSIGNED_DELTA 3
+#define DX_HASH_UNSIGNED_DELTA 4
#define DX_HASH_LEGACY_UNSIGNED (DX_HASH_LEGACY + DX_HASH_UNSIGNED_DELTA)
#define DX_HASH_HALF_MD4_UNSIGNED (DX_HASH_HALF_MD4 + DX_HASH_UNSIGNED_DELTA)
diff --git a/fs/ext4/hash.c b/fs/ext4/hash.c
index 5186e09a..584639f4 100644
--- a/fs/ext4/hash.c
+++ b/fs/ext4/hash.c
@@ -140,6 +140,7 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
{
__u32 hash;
__u32 minor_hash = 0;
+ __u64 hash64;
int i;
__u32 in[8], buf[4];
void (*str2hashbuf)(const char *, int, __u32 *, int) =
@@ -192,6 +193,11 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
hash = buf[0];
minor_hash = buf[1];
break;
+ case DX_HASH_SIPHASH24:
+ hash64 = siphash24(name, len, hinfo->seed);
+ hash = (__u32)hash64;
+ minor_hash = hash64 >> 32;
+ break;
default:
hinfo->hash = 0;
return -1;
diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 9e6eced1..922d6b48 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -685,7 +685,8 @@ dx_probe(const struct qstr *d_name, struct inode *dir,
goto fail;
}
root = (struct dx_root *) bh->b_data;
- if (root->info.hash_version != DX_HASH_TEA &&
+ if (root->info.hash_version != DX_HASH_SIPHASH24 &&
+ root->info.hash_version != DX_HASH_TEA &&
root->info.hash_version != DX_HASH_HALF_MD4 &&
root->info.hash_version != DX_HASH_LEGACY) {
ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
--
2.1.0
This can be changed later, allowing additional hash algorithms.
Signed-off-by: George Spelvin <[email protected]>
---
The code now jumps to e2fsprogs. The patches are mostly analagous
to the kernel ones.
debugfs/htree.c | 2 +-
e2fsck/pass2.c | 2 +-
e2fsck/rehash.c | 4 ++--
lib/ext2fs/dirhash.c | 14 ++++----------
lib/ext2fs/ext2_fs.h | 15 ++++++++++++---
5 files changed, 20 insertions(+), 17 deletions(-)
diff --git a/debugfs/htree.c b/debugfs/htree.c
index 4f0118d..4ab1a4c 100644
--- a/debugfs/htree.c
+++ b/debugfs/htree.c
@@ -68,7 +68,7 @@ static void htree_dump_leaf_node(ext2_filsys fs, ext2_ino_t ino,
hash_alg = rootnode->hash_version;
if ((hash_alg <= EXT2_HASH_TEA) &&
(fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
- hash_alg += 3;
+ hash_alg += EXT2_HASH_UNSIGNED;
while (offset < fs->blocksize) {
dirent = (struct ext2_dir_entry *) (buf + offset);
diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
index 0b9c5c5..454bbdc 100644
--- a/e2fsck/pass2.c
+++ b/e2fsck/pass2.c
@@ -1003,7 +1003,7 @@ inline_read_fail:
dx_dir->hashversion = root->hash_version;
if ((dx_dir->hashversion <= EXT2_HASH_TEA) &&
(fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
- dx_dir->hashversion += 3;
+ dx_dir->hashversion += EXT2_HASH_UNSIGNED;
dx_dir->depth = root->indirect_levels + 1;
} else if ((dirent->inode == 0) &&
(rec_len == fs->blocksize) &&
diff --git a/e2fsck/rehash.c b/e2fsck/rehash.c
index e37e871..e48feb7 100644
--- a/e2fsck/rehash.c
+++ b/e2fsck/rehash.c
@@ -138,7 +138,7 @@ static int fill_dir_block(ext2_filsys fs,
hash_alg = fs->super->s_def_hash_version;
if ((hash_alg <= EXT2_HASH_TEA) &&
(fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
- hash_alg += 3;
+ hash_alg += EXT2_HASH_UNSIGNED;
/* While the directory block is "hot", index it. */
dir_offset = 0;
while (dir_offset < fs->blocksize) {
@@ -375,7 +375,7 @@ static int duplicate_search_and_fix(e2fsck_t ctx, ext2_filsys fs,
hash_alg = fs->super->s_def_hash_version;
if ((hash_alg <= EXT2_HASH_TEA) &&
(fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
- hash_alg += 3;
+ hash_alg += EXT2_HASH_UNSIGNED;
for (i=1; i < fd->num_array; i++) {
ent = fd->harray + i;
diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c
index c4ac94e..ef7820c 100644
--- a/lib/ext2fs/dirhash.c
+++ b/lib/ext2fs/dirhash.c
@@ -197,7 +197,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;
+ int unsigned_flag = (version >= EXT2_HASH_UNSIGNED);
/* Initialize the default seed for the hash checksum functions */
buf[0] = 0x67452301;
@@ -216,16 +216,12 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
}
switch (version) {
- case EXT2_HASH_LEGACY_UNSIGNED:
- unsigned_flag++;
- /* fallthrough */
case EXT2_HASH_LEGACY:
+ case EXT2_HASH_LEGACY_UNSIGNED:
hash = dx_hack_hash(name, len, unsigned_flag);
break;
- case EXT2_HASH_HALF_MD4_UNSIGNED:
- unsigned_flag++;
- /* fallthrough */
case EXT2_HASH_HALF_MD4:
+ case EXT2_HASH_HALF_MD4_UNSIGNED:
p = name;
while (len > 0) {
str2hashbuf(p, len, in, 8, unsigned_flag);
@@ -236,10 +232,8 @@ 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++;
- /* fallthrough */
case EXT2_HASH_TEA:
+ case EXT2_HASH_TEA_UNSIGNED:
p = name;
while (len > 0) {
str2hashbuf(p, len, in, 4, unsigned_flag);
diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
index f9a4bdb..53df88c 100644
--- a/lib/ext2fs/ext2_fs.h
+++ b/lib/ext2fs/ext2_fs.h
@@ -226,9 +226,18 @@ struct ext2_dx_root_info {
#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 */
+
+/*
+ * For historical reasons, the first three hash algorithms
+ * have signed and unsigned variants. So, for internal
+ * use only, define some extra values outside the range of
+ * what's allowed on disk.
+ */
+#define EXT2_HASH_UNSIGNED 3
+
+#define EXT2_HASH_LEGACY_UNSIGNED (EXT2_HASH_UNSIGNED + EXT2_HASH_LEGACY)
+#define EXT2_HASH_HALF_MD4_UNSIGNED (EXT2_HASH_UNSIGNED + EXT2_HASH_HALF_MD4)
+#define EXT2_HASH_TEA_UNSIGNED (EXT2_HASH_UNSIGNED + EXT2_HASH_TEA)
#define EXT2_HASH_FLAG_INCOMPAT 0x1
--
2.1.0
This also makes the variable declarations line up better.
Signed-off-by: George Spelvin <[email protected]>
---
lib/ext2fs/dirhash.c | 17 +++++++----------
1 file changed, 7 insertions(+), 10 deletions(-)
diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c
index ef7820c..048486e 100644
--- a/lib/ext2fs/dirhash.c
+++ b/lib/ext2fs/dirhash.c
@@ -194,10 +194,9 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
{
__u32 hash;
__u32 minor_hash = 0;
- const char *p;
- int i;
- __u32 in[8], buf[4];
- int unsigned_flag = (version >= EXT2_HASH_UNSIGNED);
+ int i;
+ __u32 in[8], buf[4];
+ int unsigned_flag = (version >= EXT2_HASH_UNSIGNED);
/* Initialize the default seed for the hash checksum functions */
buf[0] = 0x67452301;
@@ -222,24 +221,22 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
break;
case EXT2_HASH_HALF_MD4:
case EXT2_HASH_HALF_MD4_UNSIGNED:
- p = name;
while (len > 0) {
- str2hashbuf(p, len, in, 8, unsigned_flag);
+ str2hashbuf(name, len, in, 8, unsigned_flag);
halfMD4Transform(buf, in);
len -= 32;
- p += 32;
+ name += 32;
}
minor_hash = buf[2];
hash = buf[1];
break;
case EXT2_HASH_TEA:
case EXT2_HASH_TEA_UNSIGNED:
- p = name;
while (len > 0) {
- str2hashbuf(p, len, in, 4, unsigned_flag);
+ str2hashbuf(name, len, in, 4, unsigned_flag);
TEA_transform(buf, in);
len -= 16;
- p += 16;
+ name += 16;
}
hash = buf[0];
minor_hash = buf[1];
--
2.1.0
Not hooked up to anything yet.
Signed-off-by: George Spelvin <[email protected]>
---
Is there a nicer way to implement get_unaligned_le64()?
I know we all hate #ifdef, but I was tempted by the Dark Side.
lib/ext2fs/dirhash.c | 126 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 126 insertions(+)
diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c
index 048486e..f51a342 100644
--- a/lib/ext2fs/dirhash.c
+++ b/lib/ext2fs/dirhash.c
@@ -14,6 +14,7 @@
#include "config.h"
#include <stdio.h>
#include <string.h>
+#include <stdint.h>
#include "ext2_fs.h"
#include "ext2fs.h"
@@ -174,6 +175,131 @@ static void str2hashbuf(const char *msg, int len, __u32 *buf, int num,
*buf++ = pad;
}
+#if __i386 || __x86_64
+/* This is such a common case it's worth optimizing */
+# define get_unaligned_le64(p) (*(const __u64 *)(p))
+#else
+#if __GNUC__ >= 3
+__attribute__ ((__pure__))
+#endif
+static __u64 get_unaligned_le64(const void *p)
+{
+ const __u8 *q = p;
+
+ return (__u64)q[0] |
+ (__u64)q[1] << 8 |
+ (__u64)q[2] << 16 |
+ (__u64)q[3] << 24 |
+ (__u64)q[4] << 32 |
+ (__u64)q[5] << 40 |
+ (__u64)q[6] << 48 |
+ (__u64)q[7] << 56;
+}
+#endif
+
+#define rol64(x, s) ((x) << (s) | (x) >> (64 - (s)))
+
+/* The basic ARX mixing function, taken from Skein */
+#define SIP_MIX(a, b, s) ((a) += (b), (b) = rol64(b, s), (b) ^= (a))
+
+/*
+ * The complete SipRound. Note that, when unrolled twice like below,
+ * the 32-bit rotates drop out on 32-bit machines.
+ */
+#define SIP_ROUND(a, b, c, d) \
+ (SIP_MIX(a, b, 13), SIP_MIX(c, d, 16), (a) = rol64(a, 32), \
+ SIP_MIX(c, b, 17), SIP_MIX(a, d, 21), (c) = rol64(c, 32))
+
+#if __GNUC__ >= 3
+__attribute__ ((__pure__))
+#endif
+static __u64
+siphash24(char const *in, size_t len, __u32 const seed[4])
+{
+ __u64 a = 0x736f6d6570736575ull; /* somepseu */
+ __u64 b = 0x646f72616e646f6dull; /* dorandom */
+ __u64 c = 0x6c7967656e657261ull; /* lygenera */
+ __u64 d = 0x7465646279746573ull; /* tedbytes */
+ __u64 m = 0;
+ __u8 padbyte = len;
+
+ /*
+ * Mix in the 128-bit hash seed. This is in a format convenient
+ * to the ext3/ext4 code. Please feel free to adapt the
+ * */
+ if (seed) {
+ m = seed[2] | (__u64)seed[3] << 32;
+ b ^= m;
+ d ^= m;
+ m = seed[0] | (__u64)seed[1] << 32;
+ /* a ^= m; is done in loop below */
+ c ^= m;
+ }
+
+ /*
+ * By using the same SipRound code for all iterations, we
+ * save space, at the expense of some branch prediction. But
+ * branch prediction is hard because of variable length anyway.
+ */
+ len = len/8 + 3; /* Now number of rounds to perform */
+ do {
+ a ^= m;
+
+ switch (--len) {
+ unsigned bytes;
+
+ default: /* Full words */
+ d ^= m = get_unaligned_le64(in);
+ in += 8;
+ break;
+ case 2: /* Final partial word */
+ /*
+ * We'd like to do one 64-bit fetch rather than
+ * mess around with bytes, but reading past the end
+ * might hit a protection boundary. Fortunately,
+ * we know that protection boundaries are aligned,
+ * so we can consider only three cases:
+ * - The remainder occupies zero words
+ * - The remainder fits into one word
+ * - The remainder straddles two words
+ */
+ bytes = padbyte & 7;
+
+ if (bytes == 0) {
+ m = 0;
+ } else {
+ unsigned offset = (unsigned)(uintptr_t)in & 7;
+
+ if (offset + bytes <= 8) {
+ m = ext2fs_le64_to_cpu(*(__u64 const *)
+ (in - offset));
+ m >>= 8*offset;
+ } else {
+ m = get_unaligned_le64(in);
+ }
+ m &= ((__u64)1 << 8*bytes) - 1;
+ }
+ /* Could use | or +, but ^ allows associativity */
+ d ^= m ^= (__u64)padbyte << 56;
+ break;
+ case 1: /* Beginning of finalization */
+ m = 0;
+ c ^= 0xff;
+ /*FALLTHROUGH*/
+ case 0:
+ break;
+ }
+
+ SIP_ROUND(a, b, c, d);
+ SIP_ROUND(a, b, c, d);
+ } while (len);
+
+ return a ^ b ^ c ^ d;
+}
+
+#undef SIP_ROUND
+#undef SIP_MIX
+
/*
* Returns the hash of a filename. If len is 0 and name is NULL, then
* this function can be used to test whether or not a hash version is
--
2.1.0
The #define name refers specifically to SipHash-2-4, but keep the
parameter name short.
Signed-off-by: George Spelvin <[email protected]>
---
The other half of the implementation.
lib/e2p/hashstr.c | 1 +
misc/mke2fs.conf.5.in | 3 ++-
misc/tune2fs.8.in | 3 ++-
3 files changed, 5 insertions(+), 2 deletions(-)
diff --git a/lib/e2p/hashstr.c b/lib/e2p/hashstr.c
index a73758c..bd4a8da 100644
--- a/lib/e2p/hashstr.c
+++ b/lib/e2p/hashstr.c
@@ -27,6 +27,7 @@ static struct hash hash_list[] = {
{ EXT2_HASH_LEGACY, "legacy" },
{ EXT2_HASH_HALF_MD4, "half_md4" },
{ EXT2_HASH_TEA, "tea" },
+ { EXT2_HASH_SIPHASH24, "siphash" },
{ 0, 0 },
};
diff --git a/misc/mke2fs.conf.5.in b/misc/mke2fs.conf.5.in
index ad6c11b..257bddd 100644
--- a/misc/mke2fs.conf.5.in
+++ b/misc/mke2fs.conf.5.in
@@ -173,8 +173,9 @@ new filesystems with hashed b-tree directories. Valid algorithms
accepted are:
.IR legacy ,
.IR half_md4 ,
+.IR tea ,
and
-.IR tea .
+.IR siphash .
.TP
.I inode_ratio
This relation specifies the default inode ratio if the user does not
diff --git a/misc/tune2fs.8.in b/misc/tune2fs.8.in
index c50d475..f25f177 100644
--- a/misc/tune2fs.8.in
+++ b/misc/tune2fs.8.in
@@ -209,8 +209,9 @@ Set the default hash algorithm used for filesystems with hashed b-tree
directories. Valid algorithms accepted are:
.IR legacy ,
.IR half_md4 ,
+.IR tea ,
and
-.IR tea .
+.IR siphash .
.TP
.BI mount_opts= mount_option_string
Set a set of default mount options which will be used when the file
--
2.1.0
As an alternate directory htree hash algorithm.
Signed-off-by: George Spelvin <[email protected]>
---
Half of the actual implementation.
e2fsck/pass1.c | 1 +
lib/ext2fs/dirhash.c | 6 ++++++
lib/ext2fs/ext2_fs.h | 3 ++-
3 files changed, 9 insertions(+), 1 deletion(-)
diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index 4fc5311..a89e556 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -2228,6 +2228,7 @@ static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
if ((root->hash_version != EXT2_HASH_LEGACY) &&
(root->hash_version != EXT2_HASH_HALF_MD4) &&
(root->hash_version != EXT2_HASH_TEA) &&
+ (root->hash_version != EXT2_HASH_SIPHASH24) &&
fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
return 1;
diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c
index f51a342..bb81938 100644
--- a/lib/ext2fs/dirhash.c
+++ b/lib/ext2fs/dirhash.c
@@ -320,6 +320,7 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
{
__u32 hash;
__u32 minor_hash = 0;
+ __u64 hash64;
int i;
__u32 in[8], buf[4];
int unsigned_flag = (version >= EXT2_HASH_UNSIGNED);
@@ -367,6 +368,11 @@ errcode_t ext2fs_dirhash(int version, const char *name, int len,
hash = buf[0];
minor_hash = buf[1];
break;
+ case EXT2_HASH_SIPHASH24:
+ hash64 = siphash24(name, len, seed);
+ hash = (__u32)hash64;
+ minor_hash = hash64 >> 32;
+ break;
default:
*ret_hash = 0;
return EXT2_ET_DIRHASH_UNSUPP;
diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
index 53df88c..7a487d9 100644
--- a/lib/ext2fs/ext2_fs.h
+++ b/lib/ext2fs/ext2_fs.h
@@ -226,6 +226,7 @@ struct ext2_dx_root_info {
#define EXT2_HASH_LEGACY 0
#define EXT2_HASH_HALF_MD4 1
#define EXT2_HASH_TEA 2
+#define EXT2_HASH_SIPHASH24 3
/*
* For historical reasons, the first three hash algorithms
@@ -233,7 +234,7 @@ struct ext2_dx_root_info {
* use only, define some extra values outside the range of
* what's allowed on disk.
*/
-#define EXT2_HASH_UNSIGNED 3
+#define EXT2_HASH_UNSIGNED 4
#define EXT2_HASH_LEGACY_UNSIGNED (EXT2_HASH_UNSIGNED + EXT2_HASH_LEGACY)
#define EXT2_HASH_HALF_MD4_UNSIGNED (EXT2_HASH_UNSIGNED + EXT2_HASH_HALF_MD4)
--
2.1.0
On Sep 23, 2014, at 12:16, "George Spelvin" <[email protected]> wrote:
>
> This uses SipHash-2-4 for directory hashing.
>
> Signed-off-by: George Spelvin <[email protected]>
> ---
> The actual feature. Pretty simple, no?
Simple, except that it introduces a serious bug in the code. It duplicates
the previous on-disk encoding of:
DX_HASH_LEGACY | DX_HASH_UNSIGNED_DELTA = 3
with:
DX_HASH_SIPHASH24 3
and that will mean old filesystems would be considered corrupted.
Due to the changes of your previous patch, it is not at all clear at the
definition of DX_HASH_* that the values 3, 4, 5 are already used.
> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> index cda8dd9c..13420bd4 100644
> --- a/fs/ext4/ext4.h
> +++ b/fs/ext4/ext4.h
> @@ -1737,6 +1737,7 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
> #define DX_HASH_LEGACY 0
> #define DX_HASH_HALF_MD4 1
> #define DX_HASH_TEA 2
> +#define DX_HASH_SIPHASH24 3
This should still explicitly #define the DX_HASH_LEGACY_UNSIGNED
values so that it is clear the values are already in use, otherwise we
expose ourselves to this bug repeatedly in the future.
Cheers, Andreas
> /*
> * For historical reasons, the first three hash algorithms
> @@ -1744,7 +1745,7 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
> * use only, define some extra values outside the range of
> * what's allowed on disk.
> */
> -#define DX_HASH_UNSIGNED_DELTA 3
> +#define DX_HASH_UNSIGNED_DELTA 4
>
> #define DX_HASH_LEGACY_UNSIGNED (DX_HASH_LEGACY + DX_HASH_UNSIGNED_DELTA)
> #define DX_HASH_HALF_MD4_UNSIGNED (DX_HASH_HALF_MD4 + DX_HASH_UNSIGNED_DELTA)
> diff --git a/fs/ext4/hash.c b/fs/ext4/hash.c
> index 5186e09a..584639f4 100644
> --- a/fs/ext4/hash.c
> +++ b/fs/ext4/hash.c
> @@ -140,6 +140,7 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
> {
> __u32 hash;
> __u32 minor_hash = 0;
> + __u64 hash64;
> int i;
> __u32 in[8], buf[4];
> void (*str2hashbuf)(const char *, int, __u32 *, int) =
> @@ -192,6 +193,11 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
> hash = buf[0];
> minor_hash = buf[1];
> break;
> + case DX_HASH_SIPHASH24:
> + hash64 = siphash24(name, len, hinfo->seed);
> + hash = (__u32)hash64;
> + minor_hash = hash64 >> 32;
> + break;
> default:
> hinfo->hash = 0;
> return -1;
> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> index 9e6eced1..922d6b48 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
> @@ -685,7 +685,8 @@ dx_probe(const struct qstr *d_name, struct inode *dir,
> goto fail;
> }
> root = (struct dx_root *) bh->b_data;
> - if (root->info.hash_version != DX_HASH_TEA &&
> + if (root->info.hash_version != DX_HASH_SIPHASH24 &&
> + root->info.hash_version != DX_HASH_TEA &&
> root->info.hash_version != DX_HASH_HALF_MD4 &&
> root->info.hash_version != DX_HASH_LEGACY) {
> ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
> --
> 2.1.0
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
Thanks for the feedback!
> Simple, except that it introduces a serious bug in the code. It duplicates
> the previous on-disk encoding of:
> DX_HASH_LEGACY | DX_HASH_UNSIGNED_DELTA =3D 3
>
> with:
> DX_HASH_SIPHASH24 3
>
> and that will mean old filesystems would be considered corrupted.
Er... I'll let Ted tell me if I screwed up, but I went through
the code quite carefully figuring out what value to use, and
DX_HASH_LEGACY_UNSIGNED is *not* an on-disk encoding.
The only on-disk encodings are 0-2, with the "Unsigned delta" being an
internal-only way of representing EXT2_FLAGS_UNSIGNED_HASH.
You can see all that in patch 1/10, or even more clearly in the first
hunk of patch 9/10, where e2fsck pass 1 is modified to extend the range
of legal on-disk values:
diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index 4fc5311..a89e556 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -2228,6 +2228,7 @@ static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
if ((root->hash_version != EXT2_HASH_LEGACY) &&
(root->hash_version != EXT2_HASH_HALF_MD4) &&
(root->hash_version != EXT2_HASH_TEA) &&
+ (root->hash_version != EXT2_HASH_SIPHASH24) &&
fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
return 1;
Looks to me like any other value (and in particular, the value 3)
appearing on disk is an error.
I didn't want to introduce a hole in the on-disk numbering, so
I bumped up the internal-only values. Allowing that is what patches
1 and 6 of the series are for.
I can try clarify the comments if you find it confusing.
Alternatively, with Ted's permission, I can change DX_HASH_UNSIGNED_DELTA
to 256 (and rename it to show it's a bit flag) so it's obviously not
representable on disk.
--
-Colin
The existing hash algorithms each come in signed and unsigned variants,
with the latter indicated by EXT2_FLAGS_UNSIGNED_HASH. Internally, ext4
represents those by adding a delta to the hash algorithm identifier that
takes them out of the range permitted on disk.
In the ext4_sb_info, s_def_hash_version is the value that actually
appears on disk, and s_hash_unsigned is the extra delta that is
inferred from the flags.
It used to be simply the magic value 3, but give it a symbolic name so
it can be changed freely if more on-disk values are added.
Signed-off-by: George Spelvin <[email protected]>
---
This is my draft with clarified comments. Any better?
fs/ext4/ext4.h | 16 ++++++++++++----
fs/ext4/super.c | 7 ++++---
2 files changed, 16 insertions(+), 7 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 1bbe7c31..07b13c7c 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -1216,7 +1216,7 @@ struct ext4_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 */
+ int s_hash_unsigned; /* DX_HASH_UNSIGNED_DELTA, or 0 if signed */
struct percpu_counter s_freeclusters_counter;
struct percpu_counter s_freeinodes_counter;
struct percpu_counter s_dirs_counter;
@@ -1737,9 +1737,17 @@ static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize)
#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
+
+#define DX_HASH_UNSIGNED_DELTA 3 /* One more than ever appears on disk! */
+
+/*
+ * For historical reasons, the first three hash algorithms
+ * have signed and unsigned variants. The following values
+ * never appear on disk, but are used by the software.
+ */
+#define DX_HASH_LEGACY_UNSIGNED (DX_HASH_LEGACY + DX_HASH_UNSIGNED_DELTA)
+#define DX_HASH_HALF_MD4_UNSIGNED (DX_HASH_HALF_MD4 + DX_HASH_UNSIGNED_DELTA)
+#define DX_HASH_TEA_UNSIGNED (DX_HASH_TEA + DX_HASH_UNSIGNED_DELTA)
static inline u32 ext4_chksum(struct ext4_sb_info *sbi, u32 crc,
const void *address, unsigned int length)
diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index 4566c2fe..6eb2c47a 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -3721,16 +3721,17 @@ static int ext4_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;
- if (EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX)) {
+ if (sbi->s_def_hash_version <= DX_HASH_TEA &&
+ EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX)) {
i = le32_to_cpu(es->s_flags);
if (i & EXT2_FLAGS_UNSIGNED_HASH)
- sbi->s_hash_unsigned = 3;
+ sbi->s_hash_unsigned = DX_HASH_UNSIGNED_DELTA;
else if ((i & EXT2_FLAGS_SIGNED_HASH) == 0) {
#ifdef __CHAR_UNSIGNED__
if (!(sb->s_flags & MS_RDONLY))
es->s_flags |=
cpu_to_le32(EXT2_FLAGS_UNSIGNED_HASH);
- sbi->s_hash_unsigned = 3;
+ sbi->s_hash_unsigned = DX_HASH_UNSIGNED_DELTA;
#else
if (!(sb->s_flags & MS_RDONLY))
es->s_flags |=
--
2.1.0
On Tue, Sep 23, 2014 at 04:45:27PM -0400, George Spelvin wrote:
>
> Er... I'll let Ted tell me if I screwed up, but I went through
> the code quite carefully figuring out what value to use, and
> DX_HASH_LEGACY_UNSIGNED is *not* an on-disk encoding.
You're right, but it would probably be safer to have a hole in the
on-disk numbering. That's because changing the numbering of
EXT2_HASH_*_UNSIGNED will change the ABI of ext2fs_dirhash(). While
we don't officially support a mismatch between the version of e2fsck
and libext2fs, and it's unlikely that other programs would be trying
to use ext2fs_dirhash.
Still, it would probably simpler to not try to assign
DX_HASH_SIPHASH24 to be 6, and to leave better comments about how the
hash values are used.
Cheers,
- Ted
> You're right, but it would probably be safer to have a hole in the
> on-disk numbering. That's because changing the numbering of
> EXT2_HASH_*_UNSIGNED will change the ABI of ext2fs_dirhash().
Ah! I missed that one! I was thinking it would be uglier to
have a hole in the on-disk numbering, so I tried for the cleanest
possible method to move them.
> While we don't officially support a mismatch between the version of
> e2fsck and libext2fs, and it's unlikely that other programs would be
> trying to use ext2fs_dirhash.
debugfs uses it too, but same idea. Mismatched e2fsprogs and libext2fs
seems really rare, but it can happen.
> Still, it would probably simpler to not try to assign
> DX_HASH_SIPHASH24 to be 6, and to leave better comments about how the
> hash values are used.
Is that "not try" supposed to be in there?
You're in charge of the number assignment. The only other issue relevant
to hash_version assignment is the comment before struct ext2_dx_root_info.
BTW, initial benchmarking isn't showing much. I created a 4 GB file
syste, on a RAM disk with -i 1024, and tried the following:
#!/bin/bash
set -e
DEV=/tmp/FS
MNT=/mnt
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor; do
echo performance > $i
done
for k in {1..10}; do
for hash in legacy half_md4 tea siphash; do
echo "=== Timing $hash (#$k) ==="
misc/tune2fs -E hash_alg=$hash $DEV
mount $DEV $MNT
mkdir $MNT/dir
time ( cd $MNT/dir &&
for i in {00..99}; do
touch ${i}{0000..9999} &
done ;
wait )
umount $MNT; mount $DEV $MNT
time ( cd $MNT/dir &&
for i in {00..99}; do
rm ${i}{0000..9999} &
done ;
wait )
rmdir $MNT/dir
umount $MNT
done
done
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor; do
echo ondemand > $i
done
The results, after a little reformatting, are:
Creation:
Legacy Half_MD4 TEA SipHash
real user sys real user sys real user sys real user sys
8.767 2.600 20.303 9.137 2.567 20.483 9.088 2.537 20.690 8.802 2.523 20.693
8.568 2.540 19.633 9.635 2.627 20.830 8.844 2.493 20.223 9.032 2.620 19.947
8.829 2.687 19.710 9.233 2.627 20.633 9.011 2.570 20.583 9.050 2.577 20.307
8.991 2.627 20.553 9.433 2.493 21.190 9.304 2.560 20.773 8.956 2.540 20.547
8.694 2.600 19.577 9.451 2.647 21.147 8.787 2.577 20.143 9.407 2.600 20.293
8.755 2.543 20.120 8.596 2.603 19.193 8.961 2.520 19.857 9.593 2.617 21.150
8.675 2.537 19.650 8.952 2.540 20.253 10.269 2.590 22.013 9.911 2.493 21.887
9.000 2.547 20.163 8.957 2.487 20.980 9.700 2.577 20.947 8.985 2.563 19.983
9.683 2.563 21.237 8.798 2.497 19.897 8.975 2.473 20.657 8.856 2.517 20.627
8.763 2.457 19.643 9.060 2.583 20.083 9.044 2.577 20.507 8.933 2.553 20.737
8.872 2.570 20.059 9.125 2.567 20.469 9.198 2.547 20.639 9.152 2.560 20.617
0.314 0.062 0.536 0.320 0.060 0.628 0.457 0.040 0.583 0.363 0.043 0.575
Last two lines are mean and (sample) standard deviation.
Removal:
Legacy Half_MD4 TEA SipHash
real user sys real user sys real user sys real user sys
6.108 2.610 31.603 6.472 2.620 32.157 6.904 2.650 34.963 6.338 2.617 33.370
6.190 2.697 30.747 6.469 2.560 33.423 6.448 2.733 32.050 6.609 2.720 32.047
6.140 2.703 30.110 6.807 2.517 35.587 6.933 2.663 36.240 6.596 2.563 34.923
6.117 2.653 31.033 6.427 2.677 32.700 6.359 2.647 32.060 6.387 2.687 32.733
6.161 2.767 30.207 6.503 2.790 33.017 6.403 2.683 31.297 6.389 2.730 33.173
6.743 2.637 35.857 6.338 2.683 31.677 6.611 2.600 34.847 6.422 2.690 31.990
6.087 2.687 31.883 6.377 2.697 31.833 6.490 2.727 32.133 6.379 2.657 31.930
6.044 2.553 29.807 6.534 2.747 34.163 6.569 2.653 32.750 6.500 2.630 32.460
6.380 2.653 31.587 6.412 2.687 33.523 6.932 2.600 35.563 6.347 2.613 31.697
6.185 2.687 30.910 6.470 2.667 31.750 6.925 2.730 35.670 6.347 2.653 33.093
6.216 2.665 31.374 6.481 2.664 32.983 6.657 2.669 33.757 6.431 2.656 32.742
0.206 0.058 1.719 0.129 0.081 1.246 0.240 0.049 1.863 0.102 0.052 0.963
Last two lines are mean and (sample) standard deviation.
Anyway, real and system times seem to vary in the expected directions
(legacy is consistently fastest) but the differences are less tha 1
standard deviation, so I'd need to take a lot more data to prove anything.
On Tue, Sep 23, 2014 at 11:08:28PM -0400, George Spelvin wrote:
> > Still, it would probably simpler to not try to assign
> > DX_HASH_SIPHASH24 to be 6, and to leave better comments about how the
> > hash values are used.
>
> Is that "not try" supposed to be in there?
Sorry, typo. Yes, it would be better to assign DX_HASH_SIPHASH24 to
be 6, and not to assign the code points 3, 4, and 5 just to be safe.
> BTW, initial benchmarking isn't showing much. I created a 4 GB file
> syste, on a RAM disk with -i 1024, and tried the following:
> DEV=/tmp/FS
> MNT=/mnt
(I assume you're using tmpfs.) There would be less overhead if you
actually used a real ramdisk, i.e., /dev/ram0, which might reduce some
of the variance and increase the percentage of the difference, but
yeah, it's not that surprising that we're not seeing much difference.
- Ted
>>> Still, it would probably simpler to not try to assign
>>> DX_HASH_SIPHASH24 to be 6, and to leave better comments about how the
>>> hash values are used.
>>
>> Is that "not try" supposed to be in there?
>
> Sorry, typo. Yes, it would be better to assign DX_HASH_SIPHASH24 to
> be 6, and not to assign the code points 3, 4, and 5 just to be safe.
I thought so, I just wanted a retransmit rather than rely on FEC in this
case. :-)
Another option I thought of I'd like to get formally rejected would be
to consider all future hashes unsigned, so there's a +3 offset between
the on-disk value and the ext2fs_dirhash parameter.
That keeps the disk numbering clean and preserves the library ABI, but
(pick any two!) makes the source messier. (Not as much as you might
think, because it just requires extening the current kludge, but still...)
> (I assume you're using tmpfs.) There would be less overhead if you
> actually used a real ramdisk, i.e., /dev/ram0, which might reduce some
> of the variance and increase the percentage of the difference, but
> yeah, it's not that surprising that we're not seeing much difference.
Oops, forgot to say that. Yes, tmpfs. I didn't realize /dev/ram* had
less overhead; I'll try that. Thanks!
On Wed, Sep 24, 2014 at 07:31:13PM -0400, George Spelvin wrote:
> Another option I thought of I'd like to get formally rejected would be
> to consider all future hashes unsigned, so there's a +3 offset between
> the on-disk value and the ext2fs_dirhash parameter.
I'm fine with considering all future hashes to be unsigned; let's see
how messy it actually makes the source code.
Cheers,
- Ted
On Tue, Sep 23, 2014 at 06:14:50AM -0400, George Spelvin wrote:
> SipHash is a fast keyed hash function for short
> inputs such as symbol tables and filenames. It's
> designed to prevent hash flooding DoS attacks.
>
> This implements SipHash-2-4, the high-speed variant.
>
> For now, ext3/4 are the only users, and the way the seed[] array
> is passed is slightly idiosyncratic for their convenience.
>
> Signed-off-by: George Spelvin <[email protected]>
> ---
> If anyone has any better ideas for the seed-passing convention, I'm
> all ears. For now, I've left it as is with plenty of warnings.
Could you please make this part of crypto/ so that anyone who wants to improve
upon the C implementation (Google suggests that SSE/AVX ports are possible) can
do so easily?
This would also make it so that ext4 only loads the algorithm when necessary.
--D
>
> include/linux/cryptohash.h | 19 +++++++
> lib/Makefile | 2 +-
> lib/siphash.c | 131 +++++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 151 insertions(+), 1 deletion(-)
> create mode 100644 lib/siphash.c
>
> diff --git a/include/linux/cryptohash.h b/include/linux/cryptohash.h
> index 2cd9f1cf..6b043780 100644
> --- a/include/linux/cryptohash.h
> +++ b/include/linux/cryptohash.h
> @@ -1,6 +1,8 @@
> #ifndef __CRYPTOHASH_H
> #define __CRYPTOHASH_H
>
> +#include <linux/compiler.h>
> +
> #define SHA_DIGEST_WORDS 5
> #define SHA_MESSAGE_BYTES (512 /*bits*/ / 8)
> #define SHA_WORKSPACE_WORDS 16
> @@ -15,4 +17,21 @@ void md5_transform(__u32 *hash, __u32 const *in);
>
> __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]);
>
> +/*
> + * Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash-2-4.
> + *
> + * Takes an arbitrary-length byte string, returns a 64-bit hash value.
> + * Extremely fast on 64-bit machines. Faster than half_md4_transform
> + * even on 32-bit machines.
> + *
> + * The fact that the seed is in the form of 4x32-bit words rather
> + * 2x64-bit, and NULL is a synonym for all-zero, is a convenience
> + * to the ext3/ext4 code which is the only current user.
> + *
> + * If it's used for internal hashing with a non-public seed, details
> + * like endianness don't matter. If it's going to be used for something
> + * longer-term, please feel free to revise the interface.
> + */
> +__u64 __pure siphash24(char const *in, size_t len, __u32 const seed[4]);
> +
> #endif
> diff --git a/lib/Makefile b/lib/Makefile
> index f9a647d3..56d0e35b 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -26,7 +26,7 @@ obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
> bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
> gcd.o lcm.o list_sort.o uuid.o flex_array.o iovec.o clz_ctz.o \
> bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o kfifo.o \
> - percpu-refcount.o percpu_ida.o hash.o
> + percpu-refcount.o percpu_ida.o hash.o siphash.o
> obj-y += string_helpers.o
> obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
> obj-y += kstrtox.o
> diff --git a/lib/siphash.c b/lib/siphash.c
> new file mode 100644
> index 00000000..77e8fb4f
> --- /dev/null
> +++ b/lib/siphash.c
> @@ -0,0 +1,131 @@
> +#include <linux/bitops.h> /* For rol64 */
> +#include <linux/cryptohash.h>
> +#include <asm/byteorder.h>
> +#include <asm/unaligned.h>
> +
> +/* The basic ARX mixing function, taken from Skein */
> +#define SIP_MIX(a, b, s) ((a) += (b), (b) = rol64(b, s), (b) ^= (a))
> +
> +/*
> + * The complete SipRound. Note that, when unrolled twice like below,
> + * the 32-bit rotates drop out on 32-bit machines.
> + */
> +#define SIP_ROUND(a, b, c, d) \
> + (SIP_MIX(a, b, 13), SIP_MIX(c, d, 16), (a) = rol64(a, 32), \
> + SIP_MIX(c, b, 17), SIP_MIX(a, d, 21), (c) = rol64(c, 32))
> +
> +/*
> + * This is rolled up more than most implementations, resulting in about
> + * 55% the code size. Speed is a few precent slower. A crude benchmark
> + * (for (i=1; i <= max; i++) for (j = 0; j < 4096-i; j++) hash(buf+j, i);)
> + * produces the following timings (in usec):
> + *
> + * i386 i386 i386 x86_64 x86_64 x86_64 x86_64
> + * Length small unroll halfmd4 small unroll halfmd4 teahash
> + * 1..4 1069 1029 1608 195 160 399 690
> + * 1..8 2483 2381 3851 410 360 988 1659
> + * 1..12 4303 4152 6207 690 618 1642 2690
> + * 1..16 6122 5931 8668 968 876 2363 3786
> + * 1..20 8348 8137 11245 1323 1185 3162 5567
> + * 1..24 10580 10327 13935 1657 1504 4066 7635
> + * 1..28 13211 12956 16803 2069 1871 5028 9759
> + * 1..32 15843 15572 19725 2470 2260 6084 11932
> + * 1..36 18864 18609 24259 2934 2678 7566 14794
> + * 1..1024 5890194 6130242 10264816 881933 881244 3617392 7589036
> + *
> + * The performance penalty is quite minor, decreasing for long strings,
> + * and it's significantly faster than half_md4, so I'm going for the
> + * I-cache win.
> + */
> +uint64_t
> +siphash24(char const *in, size_t len, uint32_t const seed[4])
> +{
> + uint64_t a = 0x736f6d6570736575; /* somepseu */
> + uint64_t b = 0x646f72616e646f6d; /* dorandom */
> + uint64_t c = 0x6c7967656e657261; /* lygenera */
> + uint64_t d = 0x7465646279746573; /* tedbytes */
> + uint64_t m = 0;
> + uint8_t padbyte = len;
> +
> + /*
> + * Mix in the 128-bit hash seed. This is in a format convenient
> + * to the ext3/ext4 code. Please feel free to adapt the
> + * */
> + if (seed) {
> + m = seed[2] | (uint64_t)seed[3] << 32;
> + b ^= m;
> + d ^= m;
> + m = seed[0] | (uint64_t)seed[1] << 32;
> + /* a ^= m; is done in loop below */
> + c ^= m;
> + }
> +
> + /*
> + * By using the same SipRound code for all iterations, we
> + * save space, at the expense of some branch prediction. But
> + * branch prediction is hard because of variable length anyway.
> + */
> + len = len/8 + 3; /* Now number of rounds to perform */
> + do {
> + a ^= m;
> +
> + switch (--len) {
> + unsigned bytes;
> +
> + default: /* Full words */
> + d ^= m = get_unaligned_le64(in);
> + in += 8;
> + break;
> + case 2: /* Final partial word */
> + /*
> + * We'd like to do one 64-bit fetch rather than
> + * mess around with bytes, but reading past the end
> + * might hit a protection boundary. Fortunately,
> + * we know that protection boundaries are aligned,
> + * so we can consider only three cases:
> + * - The remainder occupies zero words
> + * - The remainder fits into one word
> + * - The remainder straddles two words
> + */
> + bytes = padbyte & 7;
> +
> + if (bytes == 0) {
> + m = 0;
> + } else {
> + unsigned offset = (unsigned)(uintptr_t)in & 7;
> +
> + if (offset + bytes <= 8) {
> + m = le64_to_cpup((uint64_t const *)
> + (in - offset));
> + m >>= 8*offset;
> + } else {
> + m = get_unaligned_le64(in);
> + }
> + m &= ((uint64_t)1 << 8*bytes) - 1;
> + }
> + /* Could use | or +, but ^ allows associativity */
> + d ^= m ^= (uint64_t)padbyte << 56;
> + break;
> + case 1: /* Beginning of finalization */
> + m = 0;
> + c ^= 0xff;
> + /*FALLTHROUGH*/
> + case 0: /* Second half of finalization */
> + break;
> + }
> +
> + SIP_ROUND(a, b, c, d);
> + SIP_ROUND(a, b, c, d);
> + } while (len);
> +
> + return a ^ b ^ c ^ d;
> +}
> +
> +#undef SIP_ROUND
> +#undef SIP_MIX
> +
> +/*
> + * No objection to EXPORT_SYMBOL, but we should probably figure out
> + * how the seed[] array should work first. Homework for the first
> + * person to want to call it from a module!
> + */
> --
> 2.1.0
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Sep 23, 2014 at 06:31:06AM -0400, George Spelvin wrote:
> The #define name refers specifically to SipHash-2-4, but keep the
> parameter name short.
>
> Signed-off-by: George Spelvin <[email protected]>
> ---
> The other half of the implementation.
Looks reasonable, but are there test cases for e2fsprogs?
--D
>
> lib/e2p/hashstr.c | 1 +
> misc/mke2fs.conf.5.in | 3 ++-
> misc/tune2fs.8.in | 3 ++-
> 3 files changed, 5 insertions(+), 2 deletions(-)
>
> diff --git a/lib/e2p/hashstr.c b/lib/e2p/hashstr.c
> index a73758c..bd4a8da 100644
> --- a/lib/e2p/hashstr.c
> +++ b/lib/e2p/hashstr.c
> @@ -27,6 +27,7 @@ static struct hash hash_list[] = {
> { EXT2_HASH_LEGACY, "legacy" },
> { EXT2_HASH_HALF_MD4, "half_md4" },
> { EXT2_HASH_TEA, "tea" },
> + { EXT2_HASH_SIPHASH24, "siphash" },
> { 0, 0 },
> };
>
> diff --git a/misc/mke2fs.conf.5.in b/misc/mke2fs.conf.5.in
> index ad6c11b..257bddd 100644
> --- a/misc/mke2fs.conf.5.in
> +++ b/misc/mke2fs.conf.5.in
> @@ -173,8 +173,9 @@ new filesystems with hashed b-tree directories. Valid algorithms
> accepted are:
> .IR legacy ,
> .IR half_md4 ,
> +.IR tea ,
> and
> -.IR tea .
> +.IR siphash .
> .TP
> .I inode_ratio
> This relation specifies the default inode ratio if the user does not
> diff --git a/misc/tune2fs.8.in b/misc/tune2fs.8.in
> index c50d475..f25f177 100644
> --- a/misc/tune2fs.8.in
> +++ b/misc/tune2fs.8.in
> @@ -209,8 +209,9 @@ Set the default hash algorithm used for filesystems with hashed b-tree
> directories. Valid algorithms accepted are:
> .IR legacy ,
> .IR half_md4 ,
> +.IR tea ,
> and
> -.IR tea .
> +.IR siphash .
> .TP
> .BI mount_opts= mount_option_string
> Set a set of default mount options which will be used when the file
> --
> 2.1.0
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Sep 229 2014 at 12:12:43 -0700, Darrick J. Wong wrote:
> Could you please make this part of crypto/ so that anyone who wants to
> improve upon the C implementation (Google suggests that SSE/AVX ports
> are possible) can do so easily?
Well, *that* was a rabbit hole. It seems like an obviously good idea,
but let's just say that crypto/ is non-obvious. (No, it didn't take me 2
months of work; I just got sidetracked a lot because it was discouraging.)
But now that my cleanup patches there are getting reviewed, I can answer.
Basically, to fit into the crypto layer would require a very different
implementation with a lot more overhead. The code I proposed is optimized
for both size and performance in the single-contiguous-small-buffer case
that apples to file names.
There's are no separate init/update/final calls, no saving internal
state to memory, no handling of discontiguous input buffers, etc.
This is all because SipHash is designed to be *extremely* lightweight,
so the overhead of marshalling the input bytes is noticeable.
I could easily write a *separate* implementation for crypto/, and
it could share source code, but it wouldn't be the same object code.
> This would also make it so that ext4 only loads the algorithm when necessary.
Yes, but my Cunning Plan is to replace the MD5 use in net/core_secure_seq.c
with this, too. And, after careful consultation with Ted, the one in
get_random_int, too.
With all the simplifying assumptions I mentioed above made specifically in
order to get it down to negligible size, the code is 454 bytes long with
-O2, 397 bytes with -Os. Is that worth the overhead of a separate module?
On Sat, Dec 06, 2014 at 06:32:00PM -0500, George Spelvin wrote:
> Well, *that* was a rabbit hole. It seems like an obviously good idea,
> but let's just say that crypto/ is non-obvious. (No, it didn't take me 2
> months of work; I just got sidetracked a lot because it was discouraging.)
> But now that my cleanup patches there are getting reviewed, I can answer.
Yeah, at this point I think we're better off having our own open-coded
version of siphash. We have in the past exported the core of a crypto
hash which could be used by both /dev/random and the version in
crypto/ with all of the crypto packaging and overhead, but it's
probably not worth it here --- siphash is much smaller than say, any
of the SHA algorithms.
(The same is true for our use of crc32c, BTW --- if you can
demonstrate on a ramdisk --- or a super fast PCIe attached flash, but
randisks are cheaper --- that there are workloads were we are paying
for overheads caused by the crypto layer, it might make sense to
export the crc32c tables, and have an ext4-specific crc32c function.
OTOH, the main resaon why we probably want to keep on using the
crypto/ is that we can more easily take advantage of hardware
acceleration on some platforms, which wouldn't be the case with
siphash.)
Cheers,
- Ted