Skip to contentSkip to conversation

dcache: allow word-at-a-time name hashing with big-endian CPUs

PATCH Superseded Will Deacon 3 participants 5 messages Dec 10, 2013 – Dec 12, 2013

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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
index 4bdb300b16e2..60c7264163bc 100644
@@ -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));
 }
 
fs/namei.c +4 -5
index c53d3a9547f9..ac35646b3da6 100644
@@ -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
#1 lore raw

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
index 3f21f1b72e45..d3909effd725 100644
@@ -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
#2 lore raw

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

#3 lore raw

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

#4 lore raw
In reply to Will Deacon

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.