[PATCH v1 0/10] Add SipHash-2-4 directory hashing support

[PATCH v1 0/10] Add SipHash-2-4 directory hashing support

[George Spelvin]

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?

patch V1 1/10] ex4: Introduce DX_HASH_UNSIGNED_DELTA

[George Spelvin]

This makes it easier to add additional hash algorithms in future.

Signed-off-by: George Spelvin <linux@horizon.com>
---
 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

[PATCH v1 2/10] ext4: Remove redundant local variable p from ext4fs_dirhash

[George Spelvin]

Minor cleanup as long as I'm messing about in the area.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

[PATCH v1 3/10] byteorder: Fix some erroneous comments

[George Spelvin]

The prototypes obviously didn't make sense.

Signed-off-by: George Spelvin <linux@horizon.com>
Cc: David Howells <dhowells@redhat.com>
---
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

[PATCH v1 4/10] lib/siphash.c: New file

[George Spelvin]

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 <linux@horizon.com>
---
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

[PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[George Spelvin]

This uses SipHash-2-4 for directory hashing.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

[PATCH v1 6/10] Add EXT2_HASH_UNSIGNED instead of magic constant 3

[George Spelvin]

This can be changed later, allowing additional hash algorithms.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

[PATCH v1 7/10] dirhash.c (ext2fs_dirhash): Remove redundant local variable p

[George Spelvin]

This also makes the variable declarations line up better.

Signed-off-by: George Spelvin <linux@horizon.com>
---
 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

[PATCH v1 8/10] dirhash.c: Add siphash24()

[George Spelvin]

Not hooked up to anything yet.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

[PATCH v1 9/10] Add EXT2_HASH_SIPHASH24 (=3)

[George Spelvin]

As an alternate directory htree hash algorithm.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

[PATCH v1 10/10] Add "hash_alg=siphash" support

[George Spelvin]

The #define name refers specifically to SipHash-2-4, but keep the
parameter name short.

Signed-off-by: George Spelvin <linux@horizon.com>
---
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

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[Andreas Dilger]

On Sep 23, 2014, at 12:16, "George Spelvin" <linux@horizon.com> wrote:
> 
> This uses SipHash-2-4 for directory hashing.
> 
> Signed-off-by: George Spelvin <linux@horizon.com>
> ---
> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[George Spelvin]

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

[PATCH v1.1 1/10] ext4: Introduce DX_HASH_UNSIGNED_DELTA

[George Spelvin]

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 <linux@horizon.com>
---
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

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[Theodore Ts'o]

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

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[George Spelvin]

> 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.

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[Theodore Ts'o]

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

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[George Spelvin]

>>> 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!

Re: [PATCH v1 5/10] ext4: Add DX_HASH_SIPHASH24 support

[Theodore Ts'o]

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

Re: [PATCH v1 4/10] lib/siphash.c: New file

[Darrick J. Wong]

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 <linux@horizon.com>
> ---
> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v1 10/10] Add "hash_alg=siphash" support

[Darrick J. Wong]

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 <linux@horizon.com>
> ---
> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v1 4/10] lib/siphash.c: New file

[George Spelvin]

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?

Re: [PATCH v1 4/10] lib/siphash.c: New file

[Theodore Ts'o]

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