Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1406695 > unrolled thread

[PATCH 00/10] String hash improvements

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 00/10] String hash improvements "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 09:30 +0200
    Re: [PATCH 00/10] String hash improvements Geert Uytterhoeven <geert@linux-m68k.org> - 2016-05-25 10:10 +0200
      Re: [PATCH 00/10] String hash improvements "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 10:20 +0200
        Re: [PATCH 00/10] String hash improvements Geert Uytterhoeven <geert@linux-m68k.org> - 2016-05-25 11:00 +0200
          Re: [PATCH 00/10] String hash improvements "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 11:10 +0200
    Re: [PATCH 00/10] String hash improvements Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-25 18:10 +0200
      [PATCH v3 01/10] Pull out string hash to <linux/stringhash.h> George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
      [PATCH v3 04/10] Change hash_64() return value to 32 bits George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
      [PATCH v3 03/10] <linux/sunrpc/svcauth.h>: Define hash_str() in terms of hashlen_string() George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
      [PATCH v3 10/10] h8300: Add <asm/hash.h> George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
      [PATCH v3 07/10] <linux/hash.h>: Add support for architecture-specific functions George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
        Re: [PATCH v3 07/10] <linux/hash.h>: Add support for  architecture-specific functions Geert Uytterhoeven <geert@linux-m68k.org> - 2016-05-29 10:00 +0200
      [PATCH v3 00/10] String hash improvements George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
        [PATCH v3 05/10] Eliminate bad hash multipliers from hash_32() and  hash_64() George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
        [PATCH v3 09/10] microblaze: Add <asm/hash.h> George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
        [PATCH v3 08/10] m68k: Add <asm/hash.h> George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
        [PATCH v3 06/10] fs/namei.c: Improve dcache hash function George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:00 +0200
          Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function Peter Zijlstra <peterz@infradead.org> - 2016-05-30 17:20 +0200
            Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function "George Spelvin" <linux@sciencehorizons.net> - 2016-05-30 18:10 +0200
              Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function Peter Zijlstra <peterz@infradead.org> - 2016-05-30 18:30 +0200
                Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function "George Spelvin" <linux@sciencehorizons.net> - 2016-05-30 20:20 +0200
        [PATCH v3 02/10] fs/namei.c: Add hashlen_string() function George Spelvin <linux@sciencehorizons.net> - 2016-05-28 22:10 +0200
        Re: [PATCH v3 00/10] String hash improvements Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-28 22:50 +0200
          Re: [PATCH v3 00/10] String hash improvements "George Spelvin" <linux@sciencehorizons.net> - 2016-05-28 23:00 +0200
    [PATCH v2 00/10] String hash improvements "George Spelvin" <linux@horizon.com> - 2016-05-27 17:00 +0200

Page 2 of 2 — ← Prev page 1 [2]

#1409308 — Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function

On Mon, 30 May 2016 at 18:27:21 +0200, Peter Zijlstra wrote:
> On Mon, May 30, 2016 at 12:06:18PM -0400, George Spelvin wrote:
> Right; as stated performance really isn't a goal here.

I understand, but 64x64-bit multiply on 32-bit is pretty annoyingly
expensive.  In time, code size, and register pressure which bloats
surrounding code.

>> If performance mattered, I'd be inclined to use one or two iterations
>> of the 32-bit HASH_MIX() function, which is specifically designed
>> to add 32 bits to a 64-bit hash value.
> 
> Ah, I missed that HASH_MIX() had 64 bit state, so much for being able to
> read it seems. Also; should we not move that entire section of
> fs/namei.c into linux/hash.h ?
> 
> These two primitives seem generally useful.

Actually, the state is 2*sizeof(long), which is 128 bits on 64-bit.

I thought about moving it out to <linux/hash.h> as you suggest, but given
the tight coupling to the dcache hash, I decided not to until another
user showed up.

Remember, HASH_MIX() is *heavily* optimized for speed and just-barely-
adequate hash mixing for the dcache use case.  Other users should think
carefully about using it.

In particular, it's designed for 32 bits of output.  It does *not* achieve
full-width mixing, but rather achieves mixing to at least 32 bits of
output in the two rounds it has before cancellation can occur.  If you
want 64 bits of hash, as in your application, it's kind of marginal.

>> A more thorough mixing would be achieved by __jhash_mix().  Basically:
>> 
>> static inline u64 iterate_chain_key(u64 key, u32 idx)
>> {
>> 	u32 k0 = key, k1 = key >> 32;
>> 
>> 	__jhash_mix(idx, k0, k1)	/* Macro that modifies arguments! */
>> 
>> 	return k0 | (u64)k1 << 32;
>> }
>> 
>> (The order of arguments is chosen to perserve the two "most-hashed" values.)
> 
> (I'd never have managed to deduce that property given the information in
> jhash.h)

The last line of __jhash_mix(a,b,c) is
	c -= b;  c ^= rol32(b, 4);  b += a;

Thus, b and a are the last variables assigned to.  If you had dropped
one of them and returned a instead, you'd have created dead code.

>> Also, I just had contact from the hppa folks who have brought to my
>> attention that it's an example of an out-of-order superscalar CPU that
>> *doesn't* have a good integer multiplier.  For general multiplies,
>> you have to move values to the FPU and the code is a pain.
> 
> Egads, that's horrible, but sounds exactly like the thing you 'like'
> given these patches :-) Good luck with that.

Well, low-level bit-twiddling can be kind of fun.

In this case, the level of effort was required to improve the hash
mixing from "embarrassingly bad" (did you *see* what it was before
0fed3ac866?) without adding delay to a scorchingly hot code path that
Linus watches like a hawk.

[toc] | [prev] | [next] | [standalone]

#1408519 — [PATCH v3 02/10] fs/namei.c: Add hashlen_string() function

We'd like to make more use of the highly-optimized dcache hash functions
throughout the kernel, rather than have every subsystem create its own,
and a function that hashes basic null-terminated strings is required
for that.

(The name is to emphasize that it returns both hash and length.)

It's actually useful in the dcache itself, specifically d_alloc_name().
Other uses in the next patch.

full_name_hash() is also tweaked to make it more generally useful:
1) Take a "char *" rather than "unsigned char *" argument, to
   be consistent with hash_name().
2) Handle zero-length inputs.  If we want more callers, we don't want
   to make them worry about corner cases.

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
---
 fs/dcache.c                |  3 +--
 fs/namei.c                 | 51 +++++++++++++++++++++++++++++++++++++++++-----
 include/linux/stringhash.h |  8 ++++++--
 3 files changed, 53 insertions(+), 9 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index d5ecc6e4..19b75180 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -1653,8 +1653,7 @@ struct dentry *d_alloc_name(struct dentry *parent, const char *name)
 	struct qstr q;
 
 	q.name = name;
-	q.len = strlen(name);
-	q.hash = full_name_hash(q.name, q.len);
+	q.hash_len = hashlen_string(name);
 	return d_alloc(parent, &q);
 }
 EXPORT_SYMBOL(d_alloc_name);
diff --git a/fs/namei.c b/fs/namei.c
index 42f8ca03..dd98d43a 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -1822,19 +1822,20 @@ static inline unsigned long mix_hash(unsigned long hash)
 
 #endif
 
-unsigned int full_name_hash(const unsigned char *name, unsigned int len)
+/* Return the hash of a string of known length */
+unsigned int full_name_hash(const char *name, unsigned int len)
 {
 	unsigned long a, hash = 0;
 
 	for (;;) {
+		if (!len)
+			goto done;
 		a = load_unaligned_zeropad(name);
 		if (len < sizeof(unsigned long))
 			break;
 		hash = mix_hash(hash + a);
 		name += sizeof(unsigned long);
 		len -= sizeof(unsigned long);
-		if (!len)
-			goto done;
 	}
 	hash += a & bytemask_from_count(len);
 done:
@@ -1842,6 +1843,29 @@ done:
 }
 EXPORT_SYMBOL(full_name_hash);
 
+/* Return the "hash_len" (hash and length) of a null-terminated string */
+u64 hashlen_string(const char *name)
+{
+	unsigned long a, adata, mask, hash, len;
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+
+	hash = a = 0;
+	len = -sizeof(unsigned long);
+	do {
+		hash = mix_hash(hash + a);
+		len += sizeof(unsigned long);
+		a = load_unaligned_zeropad(name+len);
+	} while (!has_zero(a, &adata, &constants));
+
+	adata = prep_zero_mask(a, adata, &constants);
+	mask = create_zero_mask(adata);
+	hash += a & zero_bytemask(mask);
+	len += find_zero(mask);
+
+	return hashlen_create(fold_hash(hash), len);
+}
+EXPORT_SYMBOL(hashlen_string);
+
 /*
  * Calculate the length and hash of the path component, and
  * return the "hash_len" as the result.
@@ -1872,15 +1896,32 @@ static inline u64 hash_name(const char *name)
 
 #else
 
-unsigned int full_name_hash(const unsigned char *name, unsigned int len)
+/* Return the hash of a string of known length */
+unsigned int full_name_hash(const char *name, unsigned int len)
 {
 	unsigned long hash = init_name_hash();
 	while (len--)
-		hash = partial_name_hash(*name++, hash);
+		hash = partial_name_hash((unsigned char)*name++, hash);
 	return end_name_hash(hash);
 }
 EXPORT_SYMBOL(full_name_hash);
 
+/* Return the "hash_len" (hash and length) of a null-terminated string */
+u64 hash_string(const char *name)
+{
+	unsigned long hash = init_name_hash();
+	unsigned long len = 0, c;
+
+	c = (unsigned char)*name;
+	do {
+		len++;
+		hash = partial_name_hash(c, hash);
+		c = (unsigned char)name[len];
+	} while (c);
+	return hashlen_create(end_name_hash(hash), len);
+}
+EXPORT_SYMBOL(hash_string);
+
 /*
  * We know there's a real path component here of at least
  * one character.
diff --git a/include/linux/stringhash.h b/include/linux/stringhash.h
index 2eaaaf6d..451771d9 100644
--- a/include/linux/stringhash.h
+++ b/include/linux/stringhash.h
@@ -1,7 +1,8 @@
 #ifndef __LINUX_STRINGHASH_H
 #define __LINUX_STRINGHASH_H
 
-#include <linux/types.h>
+#include <linux/compiler.h>	/* For __pure */
+#include <linux/types.h>	/* For u32, u64 */
 
 /*
  * Routines for hashing strings of bytes to a 32-bit hash value.
@@ -59,7 +60,7 @@ static inline unsigned long end_name_hash(unsigned long hash)
  *
  * If not set, this falls back to a wrapper around the preceding.
  */
-extern unsigned int full_name_hash(const unsigned char *, unsigned int);
+extern unsigned int __pure full_name_hash(const char *, unsigned int);
 
 /*
  * A hash_len is a u64 with the hash of a string in the low
@@ -69,4 +70,7 @@ extern unsigned int full_name_hash(const unsigned char *, unsigned int);
 #define hashlen_len(hashlen)  ((u32)((hashlen) >> 32))
 #define hashlen_create(hash, len) ((u64)(len)<<32 | (u32)(hash))
 
+/* Return the "hash_len" (hash and length) of a null-terminated string */
+extern u64 __pure hashlen_string(const char *name);
+
 #endif	/* __LINUX_STRINGHASH_H */
-- 
2.8.1

[toc] | [prev] | [next] | [standalone]

#1408520 — Re: [PATCH v3 00/10] String hash improvements

On Sat, May 28, 2016 at 12:57 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
> Okay, Linus, it's still warm from the oven, but I think it's fully baked.

Hmm. Whioch commit did you use as a base for this? It's not plain 4.6,
but it's not toay's git either.

I did find a point where this applies, but it would be even better if
you just told me what your base was, and I'll start the branch from
there - that gets the git history "correct" too.

Thanks,

               Linus

[toc] | [prev] | [next] | [standalone]

#1408522 — Re: [PATCH v3 00/10] String hash improvements

Oh!  I based in on 0fed3ac866eabf01924457921ee3684c8e4c9005, which
I hope makes sense.

[toc] | [prev] | [next] | [standalone]

#1408120 — [PATCH v2 00/10] String hash improvements

This is just the arch-specific part, updated as per requests.

* Fix the stupidly overcomplex m68k conditionals (per Geert Uytterhoeven)
* Renamed the arch file to <asm/hash.h> (per Geert Uytterhoeven)
* Improved the comments on the progress of shift-and-add (Philippe De Muyter)
* Added a self-test (per Michal Simek)

Things I did *not* do, because I thought the concerns were withdrawn
after discussion:  (If I misintrepreted silence, please correct me!)

* Use unconditional inclusion with an <asm-generic/hash.h> fallback.
* Change the multi-line asm() formatting (Philippe De Muyter)
* Move reference about algorithm credit (Philippe De Muyter)

The big change is the addition of a self-test in lib/test_hash.c.
That had to be written and the various tests validated by introducing
deliberate bugs into <arch/hash.h>.

Handling the fact that architectures are allowed to change the computed
function (even though none of the ones written so far have used that
freedom) added some complexity.  I ended up using the value of the
HAVE_ARCH_* macro.  If it's 1, that means it's expected to be a clone
of the generic versions, and it's compared against them.  If it's 0,
it's its own magic thing.

The big question is, should these go through the arch trees, or may I
just include them in the series to Linus?  The latter is simpler for me,
but obviously not okay without permission.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web