dcache: allow word-at-a-time name hashing with big-endian CPUs
Subsystems (2)
PATCH 1/2 dcache: allow word-at-a-time name hashing with big-endian CPUs
When explicitly hashing the end of a string with the word-at-a-time interface, we have to be careful which end of the word we pick up.
On big-endian CPUs, the upper-bits will contain the data we're after, so ensure we generate our masks accordingly (and avoid hashing whatever random junk may have been sitting after the string).
--- fs/dcache.c | 4 ++++ fs/namei.c | 9 ++++----- 2 files changed, 8 insertions(+), 5 deletions(-)
fs/dcache.c +4 -0
@@ -192,7 +192,11 @@ static inline int dentry_string_cmp(const unsigned char *cs, const unsigned charif (!tcount)return 0 ; } +#ifdef __BIG_ENDIAN + mask = ~(~0ul >> tcount*8 ); +#else mask = ~(~0ul << tcount*8 ); +#endif return unlikely (!!((a ^ b) & mask)); }
fs/namei.c +4 -5
@@ -1598,11 +1598,6 @@ static inline int nested_symlink(struct path *path, struct nameidata *nd)* do a "get_unaligned()" if this helps and is sufficiently * fast. * -* - Little-endian machines (so that we can generate the mask -* of low bytes efficiently). Again, we *could* do a byte -* swapping load on big-endian architectures if that is not -* expensive enough to make the optimization worthless. -* * - non-CONFIG_DEBUG_PAGEALLOC configurations (so that we * do not trap on the (extremely unlikely) case of a page * crossing operation.
@@ -1646,7 +1641,11 @@ unsigned int full_name_hash(const unsigned char *name, unsigned int len)if (!len) goto done; } +#ifdef __BIG_ENDIAN + mask = ~(~0ul >> len*8 ); +#else mask = ~(~0ul << len*8 ); +#endif hash += mask & a; done:return fold_hash (hash);
Signature · 1 line
1.8.2.2
PATCH 2/2 word-at-a-time: provide generic big-endian zero_bytemask implementation
Whilst architectures may be able to do better than this (which they can, by simply defining their own macro), this is a generic stab at a zero_bytemask implementation for the asm-generic, big-endian word-at-a-time implementation.
On arm64, a clz instruction is used to implement the fls efficiently.
---
I'm happy to move this into the arch/ backends, but there's a strong linkage between this and the generic word-at-a-time algorithm that could easily break if they don't live together.
include/asm-generic/word-at-a-time.h | 8 ++++++++ 1 file changed, 8 insertions(+)
include/asm-generic/word-at-a-time.h +8 -0
@@ -49,4 +49,12 @@ static inline bool has_zero(unsigned long val, unsigned long *data, const struct return (val + c->high_bits) & ~rhs; } +#ifndef zero_bytemask +#ifdef CONFIG_64BIT +#define zero_bytemask (mask) (~0ul << fls64(mask)) +#else +#define zero_bytemask (mask) (~0ul << fls(mask)) +#endif /* CONFIG_64BIT */ +#endif /* zero_bytemask */ +#endif /* _ASM_WORD_AT_A_TIME_H */
Signature · 1 line
1.8.2.2
Re: [PATCH 2/2] word-at-a-time: provide generic big-endian zero_bytemask implementation
Hmm. Did you try to time this?
Also, I really have #ifdef's in code, and I think we'd be better off just exposing a function that does this
+#ifdef __BIG_ENDIAN
+ mask = ~(~0ul >> tcount*8);
+#else
mask = ~(~0ul << tcount*8);
+#endif
thing. I think it would logically go together with zero_bytemask(), call it something like "bytemask_from_count()" or something. Hmm? It's basically just the reverse of "count_masked_bytes()", which we also have an abstraction for.
So the #ifdef really looks out of place for me. We've generated all these nice abstractions for all the other mask handling, and then you add that ugly ifdef for this case.
Linus
Re: [PATCH 2/2] word-at-a-time: provide generic big-endian zero_bytemask implementation
Hi Linus,
Quoted 1 line · Linus Torvalds
Hmm. Did you try to time this?
I took it for a spin on a big-endian ARMv7 platform (32-bit) and the hashing is around 40% faster.
Quoted 9 lines
Also, I really have #ifdef's in code, and I think we'd be better off just exposing a function that does this
(quoted diff) +4
-0+#ifdef __BIG_ENDIAN + mask = ~(~0ul >> tcount*8); +#else mask = ~(~0ul << tcount*8); +#endif
Quoted 4 lines
thing. I think it would logically go together with
zero_bytemask(), call it something like "bytemask_from_count()" or something. Hmm? It's basically just the reverse of "count_masked_bytes()", which we also have an abstraction for.
Yup, that's a good idea, I can probably just add something to dcache.h. I'll spin a v2.
Cheers,
Will
fs/dcache.c static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char
Quoted 12 lines
fs/dcache.c +8
-0+#ifdef __BIG_ENDIAN + mask = ~(~0ul >> tcount*8 ); +#else mask = ~(~0ul << tcount*8 ); +#endif return unlikely (!!((a ^ b) & mask)); +#ifdef __BIG_ENDIAN + mask = ~(~0ul >> len*8 ); +#else mask = ~(~0ul << len*8 ); +#endif
This should really be a common helper.