On Wed, Jan 11, 2023 at 6:24 AM Ilya Maximets <[email protected]> wrote:
>
> On 1/11/23 06:33, Mike Pattrick wrote:
> > UB Sanitizer report:
> >
> > lib/hash.h:219:17: runtime error: load of misaligned address
> > 0x7ffc164a88b4 for type 'const uint64_t', which requires 8 byte
> > alignment
> >
> > #0 in hash_words_inline lib/hash.h:219
> > #1 in hash_words lib/hash.h:297
> > [...]
> >
> > Signed-off-by: Mike Pattrick <[email protected]>
> > ---
> > lib/hash.h | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++---
> > 1 file changed, 66 insertions(+), 3 deletions(-)
> >
>
> Hi, Mike.
>
> I didn't read the patch well enough, but I remember that the main
> issue with these hash functions is that aligned and unaligned
> versions *must* return exact same hash result. Is that the case
> with your patch? And we'll need a unit test to ensure that.
Yes. I had mocked up a unit test for this, but I found that it was
duplicative of the check_3word_hash() function in test-hash.c. But if
you prefer I could re-add the explicit test for alignment.
-M
>
> And, FYI, this version fails build in CI.
>
> Best regards, Ilya Maximets.
>
> > diff --git a/lib/hash.h b/lib/hash.h
> > index 60a39a40b..ca468c52c 100644
> > --- a/lib/hash.h
> > +++ b/lib/hash.h
> > @@ -187,6 +187,16 @@ static inline uint32_t hash_finish(uint64_t hash,
> > uint64_t final)
> > return hash ^ (uint32_t)hash >> 16; /* Increase entropy in LSBs. */
> > }
> >
> > +static inline uint32_t
> > +hash_finish32(uint64_t hash, uint32_t final, uint32_t semifinal)
> > +{
> > + /* The finishing multiplier 0x805204f3 has been experimentally
> > + * derived to pass the testsuite hash tests. */
> > + hash = _mm_crc32_u32(hash, semifinal);
> > + hash = _mm_crc32_u32(hash, final) * 0x805204f3;
> > + return hash ^ ((uint32_t) hash >> 16); /* Increase entropy in LSBs. */
> > +}
> > +
> > /* Returns the hash of the 'n' 32-bit words at 'p_', starting from 'basis'.
> > * We access 'p_' as a uint64_t pointer, which is fine for __SSE_4_2__.
> > *
> > @@ -232,6 +242,55 @@ hash_words_inline(const uint32_t p_[], size_t n_words,
> > uint32_t basis)
> > return hash_finish(hash1, hash2 << 32 | hash3);
> > }
> >
> > +static inline uint32_t
> > +hash_words_32aligned(const uint32_t p_[], size_t n_words, uint32_t basis)
> > +{
> > + const uint32_t *p = (const void *) p_;
> > + uint32_t hash1 = basis;
> > + uint32_t hash2 = 0;
> > + uint32_t hash3 = n_words;
> > + const uint32_t *endp = (const uint32_t *) p + n_words;
> > + const uint32_t *limit = p + n_words - 6;
> > +
> > + while (p <= limit) {
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + hash1 = _mm_crc32_u32(hash1, p[1]);
> > + hash2 = _mm_crc32_u32(hash2, p[2]);
> > + hash2 = _mm_crc32_u32(hash2, p[3]);
> > + hash3 = _mm_crc32_u32(hash3, p[4]);
> > + hash3 = _mm_crc32_u32(hash3, p[5]);
> > + p += 6;
> > + }
> > + switch (endp - (const uint32_t *) p) {
> > + case 1:
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + break;
> > + case 2:
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + hash1 = _mm_crc32_u32(hash1, p[1]);
> > + break;
> > + case 3:
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + hash1 = _mm_crc32_u32(hash1, p[1]);
> > + hash2 = _mm_crc32_u32(hash2, p[2]);
> > + break;
> > + case 4:
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + hash1 = _mm_crc32_u32(hash1, p[1]);
> > + hash2 = _mm_crc32_u32(hash2, p[2]);
> > + hash2 = _mm_crc32_u32(hash2, p[3]);
> > + break;
> > + case 5:
> > + hash1 = _mm_crc32_u32(hash1, p[0]);
> > + hash1 = _mm_crc32_u32(hash1, p[1]);
> > + hash2 = _mm_crc32_u32(hash2, p[2]);
> > + hash2 = _mm_crc32_u32(hash2, p[3]);
> > + hash3 = _mm_crc32_u32(hash3, p[4]);
> > + break;
> > + }
> > + return hash_finish32(hash1, hash2, hash3);
> > +}
> > +
> > /* A simpler version for 64-bit data.
> > * 'n_words' is the count of 64-bit words, basis is 64 bits. */
> > static inline uint32_t
> > @@ -293,10 +352,14 @@ uint32_t hash_words64__(const uint64_t *p, size_t
> > n_words, uint32_t basis);
> > static inline uint32_t
> > hash_words(const uint32_t *p, size_t n_words, uint32_t basis)
> > {
> > - if (__builtin_constant_p(n_words)) {
> > - return hash_words_inline(p, n_words, basis);
> > + if (OVS_LIKELY(((intptr_t) p & ((sizeof(uint64_t)) - 1)) == 0)) {
> > + if (__builtin_constant_p(n_words)) {
> > + return hash_words_inline(p, n_words, basis);
> > + } else {
> > + return hash_words__(p, n_words, basis);
> > + }
> > } else {
> > - return hash_words__(p, n_words, basis);
> > + return hash_words_32aligned(p, n_words, basis);
> > }
> > }
> >
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
