Skip to contentSkip to conversation

Add SipHash-2-4 directory hashing support

PATCH In review George Spelvin 4 participants 23 messages Sep 23, 2014 – Dec 8, 2014

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover Add SipHash-2-4 directory hashing support

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?

#1 lore raw

patch V1 1/10] ex4: Introduce DX_HASH_UNSIGNED_DELTA

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

---
 fs/ext4/ext4.h  | 17 +++++++++++++----
 fs/ext4/super.c |  7 ++++---
 2 files changed, 17 insertions(+), 7 deletions(-)
fs/ext4/ext4.h +13 -4
index 1bbe7c31..cda8dd9c 100644
@@ -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)
fs/ext4/super.c +4 -3
index 4566c2fe..6eb2c47a 100644
@@ -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 |=
Signature · 1 line
2.1.0
#2 lore raw

PATCH 1/10 ext4: Introduce DX_HASH_UNSIGNED_DELTA

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.

---
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(-)
fs/ext4/ext4.h +12 -4
index 1bbe7c31..07b13c7c 100644
@@ -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)
fs/ext4/super.c +4 -3
index 4566c2fe..6eb2c47a 100644
@@ -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 |=
Signature · 1 line
2.1.0
#3 lore raw

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

In reply to George Spelvin

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

---
The str2hashbuf declaration generates a checkpatch warning. False positive?

 fs/ext4/hash.c | 19 ++++++++-----------
 1 file changed, 8 insertions(+), 11 deletions(-)
fs/ext4/hash.c +8 -11
index 3d586f02..5186e09a 100644
@@ -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];
Signature · 1 line
2.1.0
#4 lore raw

PATCH 3/10 byteorder: Fix some erroneous comments

In reply to George Spelvin

The prototypes obviously didn't make sense.

---
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(-)
include/linux/byteorder/generic.h +4 -4
index 0846e6b9..37b3d9d6 100644
@@ -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
Signature · 1 line
2.1.0
#5 lore raw

PATCH 4/10 lib/siphash.c: New file

In reply to 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.

---
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
include/linux/cryptohash.h +19 -0
index 2cd9f1cf..6b043780 100644
@@ -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
lib/Makefile +1 -1
index f9a647d3..56d0e35b 100644
@@ -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
lib/siphash.c new file +131 -0

131 lines not on this page · raw message

Signature · 1 line
2.1.0
#6 lore raw

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

Quoted 6 lines · 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.

Quoted 7 lines

For now, ext3/4 are the only users, and the way the seed[] array is passed is slightly idiosyncratic for their convenience.

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

Quoted 199 lines
 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
include/linux/cryptohash.h +19 -0
index 2cd9f1cf..6b043780 100644
@@ -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
lib/Makefile +1 -1
index f9a647d3..56d0e35b 100644
@@ -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
lib/siphash.c new file +131 -0
new file mode 100644
index 00000000..77e8fb4f
@@ -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!
+ */
Signature · 6 lines
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
#7 lore raw

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

Quoted 3 lines · Darrick J. Wong

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.

Quoted 1 line

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?

maintainer
#8 lore raw

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

Quoted 4 lines · George Spelvin

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

#9 lore raw

PATCH 5/10 ext4: Add DX_HASH_SIPHASH24 support

In reply to George Spelvin

This uses SipHash-2-4 for directory hashing.

---
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(-)
fs/ext4/ext4.h +2 -1
index cda8dd9c..13420bd4 100644
@@ -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)
fs/ext4/hash.c +6 -0
index 5186e09a..584639f4 100644
@@ -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;
fs/ext4/namei.c +2 -1
index 9e6eced1..922d6b48 100644
@@ -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",
Signature · 1 line
2.1.0
#10 lore raw

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

Quoted 6 lines · George Spelvin

This uses SipHash-2-4 for directory hashing.

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

fs/ext4/ext4.h static inline __le16 ext4_rec_len_to_disk(unsigned len, unsigned blocksize) · line 1740

Quoted 9 lines
fs/ext4/ext4.h +1 -0
index cda8dd9c..13420bd4 100644
@@ -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

Quoted 56 lines
fs/ext4/ext4.h +1 -1
 /*
 * 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)
fs/ext4/hash.c +6 -0
index 5186e09a..584639f4 100644
@@ -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;
fs/ext4/namei.c +2 -1
index 9e6eced1..922d6b48 100644
@@ -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",
Signature · 6 lines
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
#11 lore raw

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

Thanks for the feedback!

Quoted 8 lines

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:

e2fsck/pass1.c +1 -0
index 4fc5311..a89e556 100644
@@ -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.

Signature · 1 line
	-Colin
maintainer
#12 lore raw

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

Quoted 4 lines · George Spelvin

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

#13 lore raw

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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.

maintainer
#14 lore raw

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

Quoted 5 lines · George Spelvin
Quoted 3 lines

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.

Quoted 5 lines

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

#15 lore raw

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

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

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

Quoted 4 lines

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

maintainer
#16 lore raw

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

Quoted 3 lines · George Spelvin

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

#17 lore raw

PATCH 6/10 Add EXT2_HASH_UNSIGNED instead of magic constant 3

In reply to George Spelvin

This can be changed later, allowing additional hash algorithms.

---
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(-)
debugfs/htree.c +1 -1
index 4f0118d..4ab1a4c 100644
@@ -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);
e2fsck/pass2.c +1 -1
index 0b9c5c5..454bbdc 100644
@@ -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) &&
e2fsck/rehash.c +2 -2
index e37e871..e48feb7 100644
@@ -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;
lib/ext2fs/dirhash.c +4 -10
index c4ac94e..ef7820c 100644
@@ -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);
lib/ext2fs/ext2_fs.h +12 -3
index f9a4bdb..53df88c 100644
@@ -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
 
Signature · 1 line
2.1.0
#18 lore raw

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

In reply to George Spelvin

This also makes the variable declarations line up better.

---
 lib/ext2fs/dirhash.c | 17 +++++++----------
 1 file changed, 7 insertions(+), 10 deletions(-)
lib/ext2fs/dirhash.c +7 -10
index ef7820c..048486e 100644
@@ -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];
Signature · 1 line
2.1.0
#19 lore raw

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

In reply to George Spelvin

Not hooked up to anything yet.

---
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(+)
lib/ext2fs/dirhash.c +126 -0
index 048486e..f51a342 100644
@@ -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
Signature · 1 line
2.1.0
#20 lore raw

PATCH 9/10 Add EXT2_HASH_SIPHASH24 (=3)

In reply to George Spelvin

As an alternate directory htree hash algorithm.

---
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(-)
e2fsck/pass1.c +1 -0
index 4fc5311..a89e556 100644
@@ -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;
 
lib/ext2fs/dirhash.c +6 -0
index f51a342..bb81938 100644
@@ -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;
lib/ext2fs/ext2_fs.h +2 -1
index 53df88c..7a487d9 100644
@@ -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)
Signature · 1 line
2.1.0
#21 lore raw

PATCH 10/10 Add "hash_alg=siphash" support

In reply to George Spelvin

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

---
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(-)
lib/e2p/hashstr.c +1 -0
index a73758c..bd4a8da 100644
@@ -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 },
 };
 
misc/mke2fs.conf.5.in +2 -1
index ad6c11b..257bddd 100644
@@ -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
misc/tune2fs.8.in +2 -1
index c50d475..f25f177 100644
@@ -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
Signature · 1 line
2.1.0
#22 lore raw

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

Quoted 6 lines · George Spelvin

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

---
The other half of the implementation.

Looks reasonable, but are there test cases for e2fsprogs?

--D

Quoted 55 lines
 lib/e2p/hashstr.c     | 1 +
 misc/mke2fs.conf.5.in | 3 ++-
 misc/tune2fs.8.in     | 3 ++-
 3 files changed, 5 insertions(+), 2 deletions(-)
lib/e2p/hashstr.c +1 -0
index a73758c..bd4a8da 100644
@@ -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 },
 };
 
misc/mke2fs.conf.5.in +2 -1
index ad6c11b..257bddd 100644
@@ -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
misc/tune2fs.8.in +2 -1
index c50d475..f25f177 100644
@@ -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
Signature · 6 lines
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