| Message ID | 163906888735.143852.10944614318596881429.stgit@warthog.procyon.org.uk |
|---|---|
| State | New |
| Headers | show |
| Series | fscache, cachefiles: Rewrite | expand |
On Thu, Dec 9, 2021 at 8:54 AM David Howells <dhowells@redhat.com> wrote: > > Implement a function to generate hashes. It needs to be stable over time > and endianness-independent as the hashes will appear on disk in future > patches. I'm not actually seeing this being endianness-independent. Is the input just regular 32-bit data in native word order? Because then it's not endianness-independent, it's purely that there *is* no endianness to the data at all and it is purely native data. So the code may be correct, but the explanation is confusing. There is absolutely nothing here that is about endianness. Linus
Linus Torvalds <torvalds@linux-foundation.org> wrote: > > Implement a function to generate hashes. It needs to be stable over time > > and endianness-independent as the hashes will appear on disk in future > > patches. > > I'm not actually seeing this being endianness-independent. > > Is the input just regular 32-bit data in native word order? Because > then it's not endianness-independent, it's purely that there *is* no > endianness to the data at all and it is purely native data. > > So the code may be correct, but the explanation is confusing. There is > absolutely nothing here that is about endianness. What I'm trying to get at is that the hash needs to be consistent, no matter the endianness of the cpu, for any particular input blob. The hashing function shouldn't need to know the structure of the input blob. In the case of the volume key, it's a padded printable string; in the case of the cookie key, it's probably some sort of structured blob, quite possibly an actual array of be32. The reason it needs to be consistent is that people seem to like seeding the cache by tarring up the cache from one machine and untarring it on another. And looking again at my code: unsigned int fscache_hash(unsigned int salt, unsigned int *data, unsigned int n) { unsigned int a, x = 0, y = salt; for (; n; n--) { a = *data++; <<<<<<< HASH_MIX(x, y, a); } return fold_hash(x, y); } The marked line should probably use something like le/be32_to_cpu(). I also need to fix 9p to canonicalise its cookie key. Thanks for catching that, David
Linus Torvalds <torvalds@linux-foundation.org> wrote: > > What I'm trying to get at is that the hash needs to be consistent, no matter > > the endianness of the cpu, for any particular input blob. > > Yeah, if that's the case, then you should probably make that "unsigned > int *data" argument probably just be "void *" and then: > > > a = *data++; <<<<<<< > > HASH_MIX(x, y, a); > > } > > return fold_hash(x, y); > > } > > > > The marked line should probably use something like le/be32_to_cpu(). > > Yes, it should be using a '__le32 *' inside that function and you > should use l32_to_cpu(). Obviously, BE would work too, but cause > unnecessary work on common hardware. Okay, how about I make the attached change to make the hashing stable? This will make fscache_hash() take an opaque buffer and a length (the length must be a multiple of four). David --- diff --git a/fs/fscache/cookie.c b/fs/fscache/cookie.c index e287952292c5..65cf2ae22a70 100644 --- a/fs/fscache/cookie.c +++ b/fs/fscache/cookie.c @@ -269,22 +269,23 @@ EXPORT_SYMBOL(fscache_caching_failed); static int fscache_set_key(struct fscache_cookie *cookie, const void *index_key, size_t index_key_len) { - u32 *buf; - int bufs; + void *buf; + size_t buf_size; - bufs = DIV_ROUND_UP(index_key_len, sizeof(*buf)); + buf_size = round_up(index_key_len, sizeof(__le32)); if (index_key_len > sizeof(cookie->inline_key)) { - buf = kcalloc(bufs, sizeof(*buf), GFP_KERNEL); + buf = kzalloc(buf_size, GFP_KERNEL); if (!buf) return -ENOMEM; cookie->key = buf; } else { - buf = (u32 *)cookie->inline_key; + buf = cookie->inline_key; } memcpy(buf, index_key, index_key_len); - cookie->key_hash = fscache_hash(cookie->volume->key_hash, buf, bufs); + cookie->key_hash = fscache_hash(cookie->volume->key_hash, + buf, buf_size); return 0; } diff --git a/fs/fscache/internal.h b/fs/fscache/internal.h index 87884f4b34fb..f121c21590dc 100644 --- a/fs/fscache/internal.h +++ b/fs/fscache/internal.h @@ -86,7 +86,7 @@ static inline void fscache_end_operation(struct netfs_cache_resources *cres) */ extern unsigned fscache_debug; -extern unsigned int fscache_hash(unsigned int salt, unsigned int *data, unsigned int n); +extern unsigned int fscache_hash(unsigned int salt, const void *data, size_t len); /* * proc.c diff --git a/fs/fscache/main.c b/fs/fscache/main.c index 01d57433702c..dad85fd84f6f 100644 --- a/fs/fscache/main.c +++ b/fs/fscache/main.c @@ -53,15 +53,16 @@ static inline unsigned int fold_hash(unsigned long x, unsigned long y) /* * Generate a hash. This is derived from full_name_hash(), but we want to be * sure it is arch independent and that it doesn't change as bits of the - * computed hash value might appear on disk. The caller also guarantees that - * the hashed data will be a series of aligned 32-bit words. + * computed hash value might appear on disk. The caller must guarantee that + * the source data is a multiple of four bytes in size. */ -unsigned int fscache_hash(unsigned int salt, unsigned int *data, unsigned int n) +unsigned int fscache_hash(unsigned int salt, const void *data, size_t len) { - unsigned int a, x = 0, y = salt; + const __le32 *p = data; + unsigned int a, x = 0, y = salt, n = len / sizeof(__le32); for (; n; n--) { - a = *data++; + a = le32_to_cpu(*p++); HASH_MIX(x, y, a); } return fold_hash(x, y); diff --git a/fs/fscache/volume.c b/fs/fscache/volume.c index edd3c245010e..26a6b8f315e1 100644 --- a/fs/fscache/volume.c +++ b/fs/fscache/volume.c @@ -131,7 +131,7 @@ static long fscache_compare_volume(const struct fscache_volume *a, if (a->key[0] != b->key[0]) return (long)a->key[0] - (long)b->key[0]; - klen = round_up(a->key[0] + 1, sizeof(unsigned int)); + klen = round_up(a->key[0] + 1, sizeof(__le32)); return memcmp(a->key, b->key, klen); } @@ -225,7 +225,7 @@ static struct fscache_volume *fscache_alloc_volume(const char *volume_key, * hashing easier. */ klen = strlen(volume_key); - hlen = round_up(1 + klen + 1, sizeof(unsigned int)); + hlen = round_up(1 + klen + 1, sizeof(__le32)); key = kzalloc(hlen, GFP_KERNEL); if (!key) goto err_vol; @@ -233,8 +233,7 @@ static struct fscache_volume *fscache_alloc_volume(const char *volume_key, memcpy(key + 1, volume_key, klen); volume->key = key; - volume->key_hash = fscache_hash(0, (unsigned int *)key, - hlen / sizeof(unsigned int)); + volume->key_hash = fscache_hash(0, key, hlen); volume->debug_id = atomic_inc_return(&fscache_volume_debug_id); down_write(&fscache_addremove_sem);
On Fri, Dec 10, 2021 at 6:41 AM David Howells <dhowells@redhat.com> wrote: > > However, since the comparator functions are only used to see if they're the > same or different, the attached change makes them return bool instead, no > cast or subtraction required. Ok, thanks, that resolves my worries. Which is not to say it all works - I obviously only scanned the patches rather than testing anything. Linus
diff --git a/fs/fscache/internal.h b/fs/fscache/internal.h index ea52f8594a77..64767992bd15 100644 --- a/fs/fscache/internal.h +++ b/fs/fscache/internal.h @@ -22,6 +22,8 @@ */ extern unsigned fscache_debug; +extern unsigned int fscache_hash(unsigned int salt, unsigned int *data, unsigned int n); + /* * proc.c */ diff --git a/fs/fscache/main.c b/fs/fscache/main.c index 819de2ee1276..a4afba1b9d3b 100644 --- a/fs/fscache/main.c +++ b/fs/fscache/main.c @@ -24,6 +24,45 @@ MODULE_PARM_DESC(fscache_debug, struct workqueue_struct *fscache_wq; EXPORT_SYMBOL(fscache_wq); +/* + * Mixing scores (in bits) for (7,20): + * Input delta: 1-bit 2-bit + * 1 round: 330.3 9201.6 + * 2 rounds: 1246.4 25475.4 + * 3 rounds: 1907.1 31295.1 + * 4 rounds: 2042.3 31718.6 + * Perfect: 2048 31744 + * (32*64) (32*31/2 * 64) + */ +#define HASH_MIX(x, y, a) \ + ( x ^= (a), \ + y ^= x, x = rol32(x, 7),\ + x += y, y = rol32(y,20),\ + y *= 9 ) + +static inline unsigned int fold_hash(unsigned long x, unsigned long y) +{ + /* Use arch-optimized multiply if one exists */ + return __hash_32(y ^ __hash_32(x)); +} + +/* + * Generate a hash. This is derived from full_name_hash(), but we want to be + * sure it is arch independent and that it doesn't change as bits of the + * computed hash value might appear on disk. The caller also guarantees that + * the hashed data will be a series of aligned 32-bit words. + */ +unsigned int fscache_hash(unsigned int salt, unsigned int *data, unsigned int n) +{ + unsigned int a, x = 0, y = salt; + + for (; n; n--) { + a = *data++; + HASH_MIX(x, y, a); + } + return fold_hash(x, y); +} + /* * initialise the fs caching module */
Implement a function to generate hashes. It needs to be stable over time and endianness-independent as the hashes will appear on disk in future patches. It can assume that its input is a multiple of four bytes in size and alignment. This is borrowed from the VFS and simplified. Signed-off-by: David Howells <dhowells@redhat.com> cc: linux-cachefs@redhat.com Link: https://lore.kernel.org/r/163819586113.215744.1699465806130102367.stgit@warthog.procyon.org.uk/ # v1 --- fs/fscache/internal.h | 2 ++ fs/fscache/main.c | 39 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+)