[PATCH 1/2] dcache: allow word-at-a-time name hashing with big-endian CPUs

[PATCH 1/2] dcache: allow word-at-a-time name hashing with big-endian CPUs

[Will Deacon]

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).

Cc: Al Viro <viro@zeniv.linux.org.uk>
Signed-off-by: Will Deacon <will.deacon@arm.com>
---
 fs/dcache.c | 4 ++++
 fs/namei.c  | 9 ++++-----
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 4bdb300b16e2..60c7264163bc 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -192,7 +192,11 @@ static inline int dentry_string_cmp(const unsigned char *cs, const unsigned char
 		if (!tcount)
 			return 0;
 	}
+#ifdef __BIG_ENDIAN
+	mask = ~(~0ul >> tcount*8);
+#else
 	mask = ~(~0ul << tcount*8);
+#endif
 	return unlikely(!!((a ^ b) & mask));
 }
 
diff --git a/fs/namei.c b/fs/namei.c
index c53d3a9547f9..ac35646b3da6 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -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);
-- 
1.8.2.2

[PATCH 2/2] word-at-a-time: provide generic big-endian zero_bytemask implementation

[Will Deacon]

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.

Signed-off-by: Will Deacon <will.deacon@arm.com>
---

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(+)

diff --git a/include/asm-generic/word-at-a-time.h b/include/asm-generic/word-at-a-time.h
index 3f21f1b72e45..d3909effd725 100644
--- a/include/asm-generic/word-at-a-time.h
+++ b/include/asm-generic/word-at-a-time.h
@@ -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 */
-- 
1.8.2.2

Re: [PATCH 2/2] word-at-a-time: provide generic big-endian zero_bytemask implementation

[Linus Torvalds]

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

[Will Deacon]

Hi Linus,

On Tue, Dec 10, 2013 at 08:08:20PM +0000, Linus Torvalds wrote:
> 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.

> 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.

Yup, that's a good idea, I can probably just add something to dcache.h.
I'll spin a v2.

Cheers,

Will

Re: [PATCH 1/2] dcache: allow word-at-a-time name hashing with big-endian CPUs

[Christoph Hellwig]

> +#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.