summaryrefslogtreecommitdiff
path: root/fs/namei.c
diff options
context:
space:
mode:
authorGeorge Spelvin <linux@horizon.com>2016-05-02 13:31:01 +0300
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-16 21:35:08 +0300
commit0fed3ac866eabf01924457921ee3684c8e4c9005 (patch)
treed32e64a6c0dbe6f93e5345caec509cc580db2a37 /fs/namei.c
parent2dcd0af568b0cf583645c8a317dd12e344b1c72a (diff)
downloadlinux-0fed3ac866eabf01924457921ee3684c8e4c9005.tar.xz
namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS
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> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'fs/namei.c')
-rw-r--r--fs/namei.c33
1 files changed, 26 insertions, 7 deletions
diff --git a/fs/namei.c b/fs/namei.c
index 30145f8f21ed..42f8ca038254 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('/');