From 62be05693c5a1e3db42822f1e292d69628ef2955 Mon Sep 17 00:00:00 2001 From: Greg Kroah-Hartman Date: Mon, 15 Sep 2014 09:32:54 -0700 Subject: [PATCH] 3.14-stable patches added patches: vfs-fix-bad-hashing-of-dentries.patch --- queue-3.14/series | 1 + .../vfs-fix-bad-hashing-of-dentries.patch | 108 ++++++++++++++++++ 2 files changed, 109 insertions(+) create mode 100644 queue-3.14/vfs-fix-bad-hashing-of-dentries.patch diff --git a/queue-3.14/series b/queue-3.14/series index df1e700a051..950a5be8893 100644 --- a/queue-3.14/series +++ b/queue-3.14/series @@ -108,3 +108,4 @@ mtd-nand-omap-fix-1-bit-hamming-code-scheme-omap_calculate_ecc.patch blkcg-don-t-call-into-policy-draining-if-root_blkg-is-already-gone.patch ib-srp-fix-deadlock-between-host-removal-and-multipathd.patch drm-nouveau-bump-version-from-1.1.1-to-1.1.2.patch +vfs-fix-bad-hashing-of-dentries.patch diff --git a/queue-3.14/vfs-fix-bad-hashing-of-dentries.patch b/queue-3.14/vfs-fix-bad-hashing-of-dentries.patch new file mode 100644 index 00000000000..c033c28ed33 --- /dev/null +++ b/queue-3.14/vfs-fix-bad-hashing-of-dentries.patch @@ -0,0 +1,108 @@ +From 99d263d4c5b2f541dfacb5391e22e8c91ea982a6 Mon Sep 17 00:00:00 2001 +From: Linus Torvalds +Date: Sat, 13 Sep 2014 11:30:10 -0700 +Subject: vfs: fix bad hashing of dentries + +From: Linus Torvalds + +commit 99d263d4c5b2f541dfacb5391e22e8c91ea982a6 upstream. + +Josef Bacik found a performance regression between 3.2 and 3.10 and +narrowed it down to commit bfcfaa77bdf0 ("vfs: use 'unsigned long' +accesses for dcache name comparison and hashing"). He reports: + + "The test case is essentially + + for (i = 0; i < 1000000; i++) + mkdir("a$i"); + + On xfs on a fio card this goes at about 20k dir/sec with 3.2, and 12k + dir/sec with 3.10. This is because we spend waaaaay more time in + __d_lookup on 3.10 than in 3.2. + + The new hashing function for strings is suboptimal for < + sizeof(unsigned long) string names (and hell even > sizeof(unsigned + long) string names that I've tested). I broke out the old hashing + function and the new one into a userspace helper to get real numbers + and this is what I'm getting: + + Old hash table had 1000000 entries, 0 dupes, 0 max dupes + New hash table had 12628 entries, 987372 dupes, 900 max dupes + We had 11400 buckets with a p50 of 30 dupes, p90 of 240 dupes, p99 of 567 dupes for the new hash + + My test does the hash, and then does the d_hash into a integer pointer + array the same size as the dentry hash table on my system, and then + just increments the value at the address we got to see how many + entries we overlap with. + + As you can see the old hash function ended up with all 1 million + entries in their own bucket, whereas the new one they are only + distributed among ~12.5k buckets, which is why we're using so much + more CPU in __d_lookup". + +The reason for this hash regression is two-fold: + + - On 64-bit architectures the down-mixing of the original 64-bit + word-at-a-time hash into the final 32-bit hash value is very + simplistic and suboptimal, and just adds the two 32-bit parts + together. + + In particular, because there is no bit shuffling and the mixing + boundary is also a byte boundary, similar character patterns in the + low and high word easily end up just canceling each other out. + + - the old byte-at-a-time hash mixed each byte into the final hash as it + hashed the path component name, resulting in the low bits of the hash + generally being a good source of hash data. That is not true for the + word-at-a-time case, and the hash data is distributed among all the + bits. + +The fix is the same in both cases: do a better job of mixing the bits up +and using as much of the hash data as possible. We already have the +"hash_32|64()" functions to do that. + +Reported-by: Josef Bacik +Cc: Al Viro +Cc: Christoph Hellwig +Cc: Chris Mason +Cc: linux-fsdevel@vger.kernel.org +Signed-off-by: Linus Torvalds +Signed-off-by: Greg Kroah-Hartman + +--- + fs/dcache.c | 3 +-- + fs/namei.c | 4 ++-- + 2 files changed, 3 insertions(+), 4 deletions(-) + +--- a/fs/dcache.c ++++ b/fs/dcache.c +@@ -106,8 +106,7 @@ static inline struct hlist_bl_head *d_ha + unsigned int hash) + { + hash += (unsigned long) parent / L1_CACHE_BYTES; +- hash = hash + (hash >> d_hash_shift); +- return dentry_hashtable + (hash & d_hash_mask); ++ return dentry_hashtable + hash_32(hash, d_hash_shift); + } + + /* Statistics gathering. */ +--- a/fs/namei.c ++++ b/fs/namei.c +@@ -34,6 +34,7 @@ + #include + #include + #include ++#include + #include + + #include "internal.h" +@@ -1624,8 +1625,7 @@ static inline int nested_symlink(struct + + static inline unsigned int fold_hash(unsigned long hash) + { +- hash += hash >> (8*sizeof(int)); +- return hash; ++ return hash_64(hash, 32); + } + + #else /* 32-bit case */ -- 2.47.3