Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1392113
| From | "George Spelvin" <linux@horizon.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | [RFC PATCH 4/2] namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS |
| Date | 2016-05-02 12:40 +0200 |
| Message-ID | <rujqG-1DM-13@gated-at.bofh.it> (permalink) |
| References | <rujh0-1xT-9@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
The hash mixing between adding the next 64 bits of name
was just a bit weak.
Replaced with a still very fast but slightly more effective
mixing function.
Signed-off-by: George Spelvin <linux@horizon.com>
---
As long as I was looking at all sorts of hashing in the kernel, I noticed
this. I'm not sure if this is still too expansive and will slow down
the loop.
fs/namei.c | 33 ++++++++++++++++++++++++++-------
1 file changed, 26 insertions(+), 7 deletions(-)
diff --git a/fs/namei.c b/fs/namei.c
index 1d9ca2d5..e2bff05d 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -1794,30 +1794,49 @@ static inline unsigned int fold_hash(unsigned long hash)
return hash_64(hash, 32);
}
+/*
+ * This is George Marsaglia's XORSHIFT generator.
+ * It implements a maximum-period LFSR in only a few
+ * instructions. It also has the property (required
+ * by hash_name()) that mix_hash(0) = 0.
+ */
+static inline unsigned long mix_hash(unsigned long hash)
+{
+ hash ^= hash << 13;
+ hash ^= hash >> 7;
+ hash ^= hash << 17;
+ return hash;
+}
+
#else /* 32-bit case */
#define fold_hash(x) (x)
+static inline unsigned long mix_hash(unsigned long hash)
+{
+ hash ^= hash << 13;
+ hash ^= hash >> 17;
+ hash ^= hash << 5;
+ return hash;
+}
+
#endif
unsigned int full_name_hash(const unsigned char *name, unsigned int len)
{
- unsigned long a, mask;
- unsigned long hash = 0;
+ unsigned long a, hash = 0;
for (;;) {
a = load_unaligned_zeropad(name);
if (len < sizeof(unsigned long))
break;
- hash += a;
- hash *= 9;
+ hash = mix_hash(hash + a);
name += sizeof(unsigned long);
len -= sizeof(unsigned long);
if (!len)
goto done;
}
- mask = bytemask_from_count(len);
- hash += mask & a;
+ hash += a & bytemask_from_count(len);
done:
return fold_hash(hash);
}
@@ -1835,7 +1854,7 @@ static inline u64 hash_name(const char *name)
hash = a = 0;
len = -sizeof(unsigned long);
do {
- hash = (hash + a) * 9;
+ hash = mix_hash(hash + a);
len += sizeof(unsigned long);
a = load_unaligned_zeropad(name+len);
b = a ^ REPEAT_BYTE('/');
--
2.8.1
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-04-30 23:00 +0200
Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-01 10:40 +0200
Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-05-01 11:50 +0200
Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-01 19:00 +0200
Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-02 09:20 +0200
[PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
[PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
Re: [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 22:10 +0200
[RFC PATCH 3/2] (Rant) Fix various hash abuses "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
[RFC PATCH 4/2] namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS "George Spelvin" <linux@horizon.com> - 2016-05-02 12:40 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Peter Zijlstra <peterz@infradead.org> - 2016-05-02 15:30 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 21:10 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 18:30 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 22:30 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:20 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:50 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-03 04:00 +0200
Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-03 05:10 +0200
csiph-web