<linux/stringhash.h>: fix end_name_hash() for 64bit long
RFC PATCH 1/1 <linux/stringhash.h>: fix end_name_hash() for 64bit long
The comment claims that this helper will try not to loose bits, but for 64bit long it looses the high bits before hashing 64bit long into 32bit int. Use the helper hash_long() to do the right thing for 64bit long. For 32bit long, there is no change.
All the callers of end_name_hash() either assign the result to qstr->hash, which is u32 or return the result as an int value (e.g. full_name_hash()). Change the helper return type to int to conform to its users.
---
Linus,
This file doesn't have any explicit maintainer and it has your fingerprints on it. Also, the alleged issue is there since git epoc, so.. please tell me, am I interpreting "try to avoid losing bits" wrong?
For context, I have been working on a flavor full_name_long_hash() that does not cut down the higher bits for 64bits long when I ran into this.
Assuming the fix is not moronic, I wouldn't even know where to begin testing its affects, or how to prove if there really is a problem.
Any suggestions?
Thanks,
Amir.
include/linux/stringhash.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/stringhash.h +2 -2
@@ -50,9 +50,9 @@ partial_name_hash(unsigned long c, unsigned long prevhash)* losing bits). This also has the property (wanted by the dcache) * that the msbits make a good hash table index. */ -static inline unsigned long end_name_hash (unsigned long hash) +static inline unsigned int end_name_hash (unsigned long hash) { -return __hash_32 ((unsigned int )hash); +return hash_long (hash,32 ); }/*
Signature · 1 line
2.7.4
Quoted 4 lines · Amir Goldstein
Assuming the fix is not moronic, I wouldn't even know where to begin testing its affects, or how to prove if there really is a problem.
Any suggestions?
So I *think* that this was on purpose, but it's a long time ago, and we've changed some of the hashing since.
And I think you're wrong that it's a no-op on 32-bit. It's a very expensive and pointless multiplication there too, even if the *shift* ends up being a nop-op.
The name hashing is pretty performance-sensitive.
Linus
Quoted 6 lines · Linus Torvalds
Quoted 4 lines · Amir Goldstein
Assuming the fix is not moronic, I wouldn't even know where to begin testing its affects, or how to prove if there really is a problem.
Any suggestions?
Quoted 7 lines
So I *think* that this was on purpose, but it's a long time ago, and we've changed some of the hashing since.
And I think you're wrong that it's a no-op on 32-bit. It's a very expensive and pointless multiplication there too, even if the *shift* ends up being a nop-op.
I did not mean this is no-op on 32-bit, what I meant is that the patch changes nothing for 32-bit long, besides the zero shift, because:
#if BITS_PER_LONG == 32
#define hash_long(val, bits) hash_32(val, bits)
and hash_32_generic() is just __hash_32() with zero shift.
I guess I cannot make that claim for platforms that HAVE_ARCH_HASH_32.
Quoted 2 lines
The name hashing is pretty performance-sensitive.
I realize that, that's why I am asking.
BTW, I think this shouldn't affect dcache on x86_64 and arm64, because they use the CONFIG_DCACHE_WORD_ACCESS variant of full_name_hash().
Anyway, my work does not depend on this fix, so I am fine with leaving it be. I just wanted to point it out is case you knew what the original intention was.
Thanks,
Amir.
Quoted 2 lines · Amir Goldstein
and
hash_32_generic()is just__hash_32()with zero shift.
Right. But that __hash_32() is very expensive and doesn't help.
So the patch as-is doesn't seem to buy anything, and only adds cost.
Note that the dentry code is a bit unusual, in that the final shift is done later, in d_hash(). And that takes the _high_ bits of the hash, so unlike a lot of other hash functions, the name hashing doesn't need to try to spread the bits down to the low bits. The intermediate hash value should be fine without any extra spreading.
Anyway, we did have numbers at one point. That's what really matters:
how good the actual hashing ends up being. So for me to take the patch, I would need to see that it actually improves the hash bucket spreading enough to be worth the cost.
Linus
Quoted 7 lines · Linus Torvalds
Quoted 2 lines · Amir Goldstein
and
hash_32_generic()is just__hash_32()with zero shift.Right. But that
__hash_32()is very expensive and doesn't help.So the patch as-is doesn't seem to buy anything, and only adds cost.
But my patch doesn't add any __hash_32() call. It was already there. Anyway, I'll drop the patch.
Thanks,
Amir.
Quoted 2 lines · Amir Goldstein
But my patch doesn't add any
__hash_32()call. It was already there.
Oh, duh. My bad. It was indeed there already.
Let me go back and look at the history of this thing, it's changed several times, and it looks like George Spelvin (not his real name) isn't on his old email address.
Linus
Quoted 4 lines · Amir Goldstein
The comment claims that this helper will try not to loose bits, but for 64bit long it looses the high bits before hashing 64bit long into 32bit int. Use the helper
hash_long()to do the right thing for 64bit long. For 32bit long, there is no change.
Ok, sorry for the delay, I only got back to this now because the merge window is calming down (famous last words - sometimes Friday ends up being busy, but I might decide that it's too late if somebody sends me an annoying late pull request now).
And after having looked more at it, I take back all my complaints about the patch, you were right and I was mis-reading things or just being stupid.
I also don't worry too much about the possible performance impact of this on 64-bit, since most architectures that actually care about performance end up not using this very much (the dcache code is the most performance-critical, but the word-at-a-time case uses its own hashing anyway).
So this ends up being mostly used for filesystems that do their own degraded hashing (usually because they want a case-insensitive comparison function).
A _tiny_ worry remains, in that not everybody uses DCACHE_WORD_ACCESS, and then this potentially makes things more expensive on 64-bit architectures with slow or lacking multipliers even for the normal case.
That said, realistically the only such architecture I can think of is PA-RISC. Nobody really cares about performance on that, it's more of a "look ma, I've got warts^W an odd machine" platform.
So I think your patch is fine, and all my initial worries were just misplaced from not looking at this properly.
Sorry.
I *would* love to get some kind of estimate on how this changes the hash distribution. Do you have anything like that? The way this function is designed to be used, the upper bits should be used for the hash bucket information, so doing some bucket size distribution on (say) the upper ~12 bits or something with some real string input would be really good.
Linus
Quoted 8 lines · Linus Torvalds
I *would* love to get some kind of estimate on how this changes the hash distribution. Do you have anything like that? The way this function is designed to be used, the upper bits should be used for the hash bucket information, so doing some bucket size distribution on (say) the upper ~12 bits or something with some real string input would be really good.
I've added bucket counters and tracing number of entries / number of non empty buckets and largest bucket to dcache (patch attached). Increased d_hash_shift to take only 12 bits for hash table offset. The results vary a bit per run, but below are some outputs from sample runs of find / of 55K entries right after boot.
The bottom line is that, at least w.r.t this simplistic bucket analysis and this specific workload, the patch does not seem to move the needle. The bucket distribution of before and after patch are similar and also similar to the word-at-a-time results.
Just for comparison, I added a run with noop end_name_hash() which shows a worse bucket distribution.
Perhaps it would take a different workload, or different analysis to demonstrate the alleged deficiencies of the current implementation? Not sure which evidence will be required to justify the change, even if, the patch is correct in theory? I wonder if we should just let this old code be... maybe add something to the comment or remove the part about "try to avoid losing bits..."?
Thanks,
Amir.
----------------------------------------------------
x86_64, word-at-a-time, 12 bits:
[ 0.008583] dcache: d_hash_shift = 20, nentries = 1, nbuckets = 1, maxcount = 1 [ 0.783683] dcache: d_hash_shift = 20, nentries = 130, nbuckets = 129, maxcount = 2 [ 0.785336] dcache: d_hash_shift = 20, nentries = 314, nbuckets = 303, maxcount = 3 [ 0.789104] dcache: d_hash_shift = 20, nentries = 818, nbuckets = 736, maxcount = 4 [ 0.795435] dcache: d_hash_shift = 20, nentries = 1738, nbuckets = 1406, maxcount = 5 [ 0.804935] dcache: d_hash_shift = 20, nentries = 3056, nbuckets = 2134, maxcount = 6 [ 0.814014] dcache: d_hash_shift = 20, nentries = 4158, nbuckets = 2595, maxcount = 7 [ 0.824848] dcache: d_hash_shift = 20, nentries = 5635, nbuckets = 3051, maxcount = 8 [ 0.844848] dcache: d_hash_shift = 20, nentries = 8523, nbuckets = 3584, maxcount = 9 [ 0.852072] dcache: d_hash_shift = 20, nentries = 9571, nbuckets = 3708, maxcount = 10 [ 0.855598] dcache: d_hash_shift = 20, nentries = 10098, nbuckets = 3745, maxcount = 11 [ 2.793453] dcache: d_hash_shift = 20, nentries = 13547, nbuckets = 3937, maxcount = 12 [ 3.097325] dcache: d_hash_shift = 20, nentries = 14394, nbuckets = 3965, maxcount = 13 [ 3.559967] dcache: d_hash_shift = 20, nentries = 16783, nbuckets = 4017, maxcount = 14 [ 10.259225] dcache: d_hash_shift = 20, nentries = 22166, nbuckets = 4070, maxcount = 15 [ 10.326126] dcache: d_hash_shift = 20, nentries = 24960, nbuckets = 4083, maxcount = 16 [ 10.338824] dcache: d_hash_shift = 20, nentries = 25348, nbuckets = 4084, maxcount = 17 [ 10.423085] dcache: d_hash_shift = 20, nentries = 29715, nbuckets = 4095, maxcount = 18 [ 10.746374] dcache: d_hash_shift = 20, nentries = 30771, nbuckets =
4095, maxcount = 19
x86_64, byte at a time, before patch:
[ 0.008624] dcache: d_hash_shift = 20, nentries = 1, nbuckets = 1, maxcount = 1 [ 0.797948] dcache: d_hash_shift = 20, nentries = 168, nbuckets = 167, maxcount = 2 [ 0.803184] dcache: d_hash_shift = 20, nentries = 953, nbuckets = 858, maxcount = 3 [ 0.809085] dcache: d_hash_shift = 20, nentries = 1690, nbuckets = 1390, maxcount = 4 [ 0.818364] dcache: d_hash_shift = 20, nentries = 2868, nbuckets = 2082, maxcount = 5 [ 0.826448] dcache: d_hash_shift = 20, nentries = 4016, nbuckets = 2609, maxcount = 6 [ 0.844307] dcache: d_hash_shift = 20, nentries = 6525, nbuckets = 3357, maxcount = 7 [ 0.848492] dcache: d_hash_shift = 20, nentries = 7121, nbuckets = 3473, maxcount = 8 [ 0.850470] dcache: d_hash_shift = 20, nentries = 7419, nbuckets = 3514, maxcount = 9 [ 2.781536] dcache: d_hash_shift = 20, nentries = 13484, nbuckets = 3984, maxcount = 10 [ 3.082709] dcache: d_hash_shift = 20, nentries = 14329, nbuckets = 4012, maxcount = 11 [ 3.116017] dcache: d_hash_shift = 20, nentries = 14411, nbuckets = 4011, maxcount = 12 [ 3.736935] dcache: d_hash_shift = 20, nentries = 17509, nbuckets = 4054, maxcount = 13 [ 17.557370] dcache: d_hash_shift = 20, nentries = 19928, nbuckets = 4073, maxcount = 14 [ 17.587867] dcache: d_hash_shift = 20, nentries = 21488, nbuckets = 4083, maxcount = 15 [ 17.622295] dcache: d_hash_shift = 20, nentries = 22798, nbuckets = 4085, maxcount = 16 [ 17.642227] dcache: d_hash_shift = 20, nentries = 23505, nbuckets = 4086, maxcount = 17 [ 17.722103] dcache: d_hash_shift = 20, nentries = 27107, nbuckets = 4092, maxcount = 18 [ 17.749791] dcache: d_hash_shift = 20, nentries = 28353, nbuckets = 4093, maxcount = 19 [ 17.958165] dcache: d_hash_shift = 20, nentries = 30687, nbuckets =
4095, maxcount = 20
x86_64, byte at a time, after patch:
[ 0.008648] dcache: d_hash_shift = 20, nentries = 1, nbuckets = 1, maxcount = 1 [ 0.795676] dcache: d_hash_shift = 20, nentries = 157, nbuckets = 156, maxcount = 2 [ 0.799493] dcache: d_hash_shift = 20, nentries = 619, nbuckets = 563, maxcount = 3 [ 0.803741] dcache: d_hash_shift = 20, nentries = 1115, nbuckets = 928, maxcount = 4 [ 0.814418] dcache: d_hash_shift = 20, nentries = 2619, nbuckets = 1894, maxcount = 5 [ 0.817449] dcache: d_hash_shift = 20, nentries = 3053, nbuckets = 2095, maxcount = 6 [ 0.838418] dcache: d_hash_shift = 20, nentries = 5981, nbuckets = 3159, maxcount = 7 [ 0.843916] dcache: d_hash_shift = 20, nentries = 6790, nbuckets = 3340, maxcount = 8 [ 0.854101] dcache: d_hash_shift = 20, nentries = 8263, nbuckets = 3565, maxcount = 9 [ 0.864520] dcache: d_hash_shift = 20, nentries = 9745, nbuckets = 3760, maxcount = 10 [ 2.799091] dcache: d_hash_shift = 20, nentries = 13273, nbuckets = 3954, maxcount = 11 [ 3.201936] dcache: d_hash_shift = 20, nentries = 14576, nbuckets = 3988, maxcount = 12 [ 3.996005] dcache: d_hash_shift = 20, nentries = 17902, nbuckets = 4051, maxcount = 13 [ 9.847851] dcache: d_hash_shift = 20, nentries = 19322, nbuckets = 4068, maxcount = 14 [ 9.858100] dcache: d_hash_shift = 20, nentries = 19891, nbuckets = 4074, maxcount = 15 [ 9.889944] dcache: d_hash_shift = 20, nentries = 21424, nbuckets = 4082, maxcount = 16 [ 9.912863] dcache: d_hash_shift = 20, nentries = 22145, nbuckets = 4087, maxcount = 17 [ 9.940020] dcache: d_hash_shift = 20, nentries = 23126, nbuckets = 4089, maxcount = 18 [ 10.016343] dcache: d_hash_shift = 20, nentries = 26093, nbuckets = 4094, maxcount = 19 [ 10.072039] dcache: d_hash_shift = 20, nentries = 28712, nbuckets =
4094, maxcount = 20
x86_64, byte at a time, with NOOP end_name_hash() (i.e. take 32 LSB):
[ 0.008609] dcache: d_hash_shift = 20, nentries = 1, nbuckets = 1, maxcount = 1 [ 0.081990] dcache: d_hash_shift = 20, nentries = 5, nbuckets = 4, maxcount = 2 [ 0.802145] dcache: d_hash_shift = 20, nentries = 31, nbuckets = 28, maxcount = 3 [ 0.813503] dcache: d_hash_shift = 20, nentries = 554, nbuckets = 482, maxcount = 4 [ 0.817755] dcache: d_hash_shift = 20, nentries = 1151, nbuckets = 932, maxcount = 5 [ 0.817910] dcache: d_hash_shift = 20, nentries = 1175, nbuckets = 947, maxcount = 6 [ 0.817987] dcache: d_hash_shift = 20, nentries = 1187, nbuckets = 952, maxcount = 7 [ 0.838691] dcache: d_hash_shift = 20, nentries = 4152, nbuckets = 2502, maxcount = 8 [ 0.848732] dcache: d_hash_shift = 20, nentries = 5564, nbuckets = 2959, maxcount = 9 [ 0.848774] dcache: d_hash_shift = 20, nentries = 5570, nbuckets = 2960, maxcount = 10 [ 0.872152] dcache: d_hash_shift = 20, nentries = 8949, nbuckets = 3548, maxcount = 11 [ 0.879572] dcache: d_hash_shift = 20, nentries = 10020, nbuckets = 3647, maxcount = 12 [ 0.893884] dcache: d_hash_shift = 20, nentries = 12009, nbuckets = 3803, maxcount = 13 [ 0.897821] dcache: d_hash_shift = 20, nentries = 12570, nbuckets = 3827, maxcount = 14 [ 0.898154] dcache: d_hash_shift = 20, nentries = 12615, nbuckets = 3827, maxcount = 15 [ 0.898432] dcache: d_hash_shift = 20, nentries = 12654, nbuckets = 3829, maxcount = 16 [ 0.898877] dcache: d_hash_shift = 20, nentries = 12717, nbuckets = 3830, maxcount = 17 [ 0.906711] dcache: d_hash_shift = 20, nentries = 12821, nbuckets = 3838, maxcount = 18 [ 0.906822] dcache: d_hash_shift = 20, nentries = 12822, nbuckets = 3838, maxcount = 19 [ 0.906920] dcache: d_hash_shift = 20, nentries = 12823, nbuckets = 3838, maxcount = 20 [...] [ 3.743889] dcache: d_hash_shift = 20, nentries = 17112, nbuckets = 3992, maxcount = 91 [ 4.113855] dcache: d_hash_shift = 20, nentries = 17927, nbuckets = 4000, maxcount = 92 [ 11.915833] dcache: d_hash_shift = 20, nentries = 27988, nbuckets =
4084, maxcount = 93
fs/dcache.c +43 -12
@@ -103,13 +103,25 @@ EXPORT_SYMBOL(slash_name);static unsigned int d_hash_shift__read_mostly ; -static struct hlist_bl_head *dentry_hashtable__read_mostly ; +struct _hlist_bl_head { +struct hlist_bl_head head; +int count; +}; -static inline struct hlist_bl_head *d_hash (unsigned int hash) +static int nentries, nbuckets, maxcount; + +static struct _hlist_bl_head *dentry_hashtable__read_mostly ; + +static inline struct _hlist_bl_head *_d_hash (unsigned int hash) {return dentry_hashtable + (hash >> d_hash_shift); } +static inline struct hlist_bl_head *d_hash (unsigned int hash) +{ +return &_d_hash (hash)->head; +} +#define IN_LOOKUP_SHIFT 10static struct hlist_bl_head in_lookup_hashtable[1 <<IN_LOOKUP_SHIFT ];
@@ -174,7 +186,7 @@ int proc_nr_dentry(struct ctl_table *table, int write, void __user *buffer,* Compare 2 name strings, return 0 if they match, otherwise non-zero. * The strings are both count bytes long, and count is non-zero. */ -#ifdef CONFIG_DCACHE_WORD_ACCESS +#if 0 //def CONFIG_DCACHE_WORD_ACCESS #include <asm/word-at-a-time.h> /*
@@ -471,19 +483,28 @@ static void dentry_lru_add(struct dentry *dentry)static void ___d_drop (struct dentry *dentry) {if (!d_unhashed (dentry)) { +struct _hlist_bl_head *_b;struct hlist_bl_head *b;/* * Hashed dentries are normally on the dentry hashtable, * with the exception of those newly allocated by * d_obtain_root, which are always IS_ROOT: */ -if (unlikely (IS_ROOT (dentry))) +if (unlikely (IS_ROOT (dentry))) { + _b =NULL ; b = &dentry->d_sb->s_roots; -else - b =d_hash (dentry->d_name.hash); - + }else { + _b =_d_hash (dentry->d_name.hash); + b = &_b->head; + }hlist_bl_lock (b);__hlist_bl_del (&dentry->d_hash); +if (_b) { + _b->count--; +if (!_b->count) + nbuckets--; + nentries--; + }hlist_bl_unlock (b);/* After this call, in-progress rcu-walk path lookup will fail. */ write_seqcount_invalidate (&dentry->d_seq);
@@ -2406,10 +2427,20 @@ EXPORT_SYMBOL(d_delete);static void __d_rehash (struct dentry *entry) { -struct hlist_bl_head *b =d_hash (entry->d_name.hash); +struct _hlist_bl_head *_b =_d_hash (entry->d_name.hash); +struct hlist_bl_head *b = &_b->head;hlist_bl_lock (b);hlist_bl_add_head_rcu (&entry->d_hash, b); +if (!_b->count) + nbuckets++; + _b->count++; + nentries++; +if (_b->count > maxcount) { + maxcount = _b->count; +pr_info ("dcache: d_hash_shift = %d, nentries = %d, nbuckets = %d, maxcount = %d\n" , + d_hash_shift, nentries, nbuckets, maxcount); + }hlist_bl_unlock (b); }
@@ -3610,7 +3641,7 @@ static void __init dcache_init_early(void) dentry_hashtable = alloc_large_system_hash("Dentry cache", - sizeof(struct hlist_bl_head), + sizeof(struct _hlist_bl_head), dhash_entries, 13, HASH_EARLY | HASH_ZERO,
@@ -3618,7 +3649,7 @@ static void __init dcache_init_early(void)NULL ,0 , 0); - d_hash_shift =32 - d_hash_shift; + d_hash_shift =32 -12 ;//d_hash_shift; }static void __init dcache_init (void )
@@ -3638,7 +3669,7 @@ static void __init dcache_init(void) dentry_hashtable = alloc_large_system_hash("Dentry cache", - sizeof(struct hlist_bl_head), + sizeof(struct _hlist_bl_head), dhash_entries, 13, HASH_ZERO,
@@ -3646,7 +3677,7 @@ static void __init dcache_init(void)NULL ,0 , 0); - d_hash_shift =32 - d_hash_shift; + d_hash_shift =32 -12 ;//d_hash_shift; }/* SLAB cache for __getname() consumers */
fs/namei.c +4 -1
@@ -1798,7 +1798,7 @@ static int walk_component(struct nameidata *nd, int flags)* the final mask". Again, that could be replaced with a * efficient population count instruction or similar. */ -#ifdef CONFIG_DCACHE_WORD_ACCESS +#if 0 //def CONFIG_DCACHE_WORD_ACCESS #include <asm/word-at-a-time.h>
@@ -1985,6 +1985,9 @@ unsigned long full_name_long_hash(const void *salt, const char *name, }EXPORT_SYMBOL (full_name_long_hash); +// define end_name_hash to NOOP +//#define end_name_hash (unsigned int) +unsigned int full_name_hash (const void *salt,const char *name,unsigned int len) {