From 88019c40725704e6998625937c764d1d0c827975 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Wed, 15 Dec 2021 10:17:04 +0000 Subject: vppinfra: toeplitz hash four in parallel Type: improvement Change-Id: Icb3f39f42d01c51d7b03543cb7d6b5dabad11866 Signed-off-by: Damjan Marion --- src/vppinfra/clib.h | 1 + src/vppinfra/vector/test/test.h | 6 +- src/vppinfra/vector/test/toeplitz.c | 243 ++++++++++++++++++++- src/vppinfra/vector/toeplitz.h | 419 ++++++++++++++++++++++++++++++------ src/vppinfra/vector_avx2.h | 10 + src/vppinfra/vector_avx512.h | 19 +- 6 files changed, 622 insertions(+), 76 deletions(-) diff --git a/src/vppinfra/clib.h b/src/vppinfra/clib.h index 52e721768bc..50f04e18f84 100644 --- a/src/vppinfra/clib.h +++ b/src/vppinfra/clib.h @@ -100,6 +100,7 @@ #define __clib_packed __attribute__ ((packed)) #define __clib_constructor __attribute__ ((constructor)) #define __clib_noinline __attribute__ ((noinline)) +#define __clib_noclone __attribute__ ((noclone)) #define __clib_aligned(x) __attribute__ ((aligned(x))) #define __clib_section(s) __attribute__ ((section(s))) #define __clib_warn_unused_result __attribute__ ((warn_unused_result)) diff --git a/src/vppinfra/vector/test/test.h b/src/vppinfra/vector/test/test.h index 4334dfa53a1..4511bf31fa9 100644 --- a/src/vppinfra/vector/test/test.h +++ b/src/vppinfra/vector/test/test.h @@ -59,8 +59,10 @@ typedef struct } test_main_t; extern test_main_t test_main; -#define __test_funct_fn static __clib_noinline __clib_section (".test_func") -#define __test_perf_fn static __clib_noinline __clib_section (".test_perf") +#define __test_funct_fn \ + static __clib_noinline __clib_noclone __clib_section (".test_func") +#define __test_perf_fn \ + static __clib_noinline __clib_noclone __clib_section (".test_perf") #define REGISTER_TEST(x) \ test_registration_t CLIB_MARCH_SFX (__test_##x); \ diff --git a/src/vppinfra/vector/test/toeplitz.c b/src/vppinfra/vector/test/toeplitz.c index 0efc4239a13..d425a443eec 100644 --- a/src/vppinfra/vector/test/toeplitz.c +++ b/src/vppinfra/vector/test/toeplitz.c @@ -175,6 +175,13 @@ wrapper (clib_toeplitz_hash_key_t *k, u8 *data, u32 n_bytes) return clib_toeplitz_hash (k, data, n_bytes); } +__test_funct_fn void +wrapper_x4 (clib_toeplitz_hash_key_t *k, u8 *d0, u8 *d1, u8 *d2, u8 *d3, + u32 *h0, u32 *h1, u32 *h2, u32 *h3, u32 n_bytes) +{ + clib_toeplitz_hash_x4 (k, d0, d1, d2, d3, h0, h1, h2, h3, n_bytes); +} + static clib_error_t * test_clib_toeplitz_hash (clib_error_t *err) { @@ -222,16 +229,10 @@ test_clib_toeplitz_hash (clib_error_t *err) n_key_copies = 6; bigkey_len = k->key_length * n_key_copies; bigdata_len = bigkey_len - 4; - bigkey = clib_mem_alloc (bigkey_len); - bigdata = clib_mem_alloc (bigdata_len); + bigkey = test_mem_alloc_and_splat (k->key_length, n_key_copies, k->data); + bigdata = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0); u32 key_len = k->key_length; - for (int i = 0; i < n_key_copies; i++) - clib_memcpy (bigkey + i * key_len, k->data, key_len); - - for (int i = 0; i < bigdata_len; i++) - bigdata[i] = (u8) i; - clib_toeplitz_hash_key_free (k); k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len); @@ -252,8 +253,8 @@ test_clib_toeplitz_hash (clib_error_t *err) done: clib_toeplitz_hash_key_free (k); - clib_mem_free (bigkey); - clib_mem_free (bigdata); + test_mem_free (bigkey); + test_mem_free (bigdata); return err; } @@ -334,3 +335,225 @@ REGISTER_TEST (clib_toeplitz_hash) = { .n_ops = 16384, .fn = perftest_variable_size }), }; + +static clib_error_t * +test_clib_toeplitz_hash_x4 (clib_error_t *err) +{ + u32 r[4]; + int n_key_copies, bigkey_len, bigdata_len; + u8 *bigkey, *bigdata0, *bigdata1, *bigdata2, *bigdata3; + clib_toeplitz_hash_key_t *k; + + k = clib_toeplitz_hash_key_init (0, 0); + + wrapper_x4 (k, (u8 *) &ip4_tests[0].key, (u8 *) &ip4_tests[1].key, + (u8 *) &ip4_tests[2].key, (u8 *) &ip4_tests[3].key, r, r + 1, + r + 2, r + 3, 8); + + if (ip4_tests[0].hash_2t != r[0] || ip4_tests[1].hash_2t != r[1] || + ip4_tests[2].hash_2t != r[2] || ip4_tests[3].hash_2t != r[3]) + return clib_error_return (err, + "wrong IPv4 2 tuple x4 hash " + "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } " + "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }", + ip4_tests[0].hash_2t, ip4_tests[1].hash_2t, + ip4_tests[2].hash_2t, ip4_tests[3].hash_2t, r[0], + r[1], r[2], r[3]); + + wrapper_x4 (k, (u8 *) &ip4_tests[0].key, (u8 *) &ip4_tests[1].key, + (u8 *) &ip4_tests[2].key, (u8 *) &ip4_tests[3].key, r, r + 1, + r + 2, r + 3, 12); + + if (ip4_tests[0].hash_4t != r[0] || ip4_tests[1].hash_4t != r[1] || + ip4_tests[2].hash_4t != r[2] || ip4_tests[3].hash_4t != r[3]) + return clib_error_return (err, + "wrong IPv4 4 tuple x4 hash " + "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } " + "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }", + ip4_tests[0].hash_4t, ip4_tests[1].hash_4t, + ip4_tests[2].hash_4t, ip4_tests[3].hash_4t, r[0], + r[1], r[2], r[3]); + + wrapper_x4 (k, (u8 *) &ip6_tests[0].key, (u8 *) &ip6_tests[1].key, + (u8 *) &ip6_tests[2].key, (u8 *) &ip6_tests[0].key, r, r + 1, + r + 2, r + 3, 32); + + if (ip6_tests[0].hash_2t != r[0] || ip6_tests[1].hash_2t != r[1] || + ip6_tests[2].hash_2t != r[2] || ip6_tests[0].hash_2t != r[3]) + return clib_error_return (err, + "wrong IPv6 2 tuple x4 hash " + "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } " + "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }", + ip6_tests[0].hash_2t, ip6_tests[1].hash_2t, + ip6_tests[2].hash_2t, ip6_tests[0].hash_2t, r[0], + r[1], r[2], r[3]); + + wrapper_x4 (k, (u8 *) &ip6_tests[0].key, (u8 *) &ip6_tests[1].key, + (u8 *) &ip6_tests[2].key, (u8 *) &ip6_tests[0].key, r, r + 1, + r + 2, r + 3, 36); + + if (ip6_tests[0].hash_4t != r[0] || ip6_tests[1].hash_4t != r[1] || + ip6_tests[2].hash_4t != r[2] || ip6_tests[0].hash_4t != r[3]) + return clib_error_return (err, + "wrong IPv6 4 tuple x4 hash " + "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x } " + "expected { 0x%08x, 0x%08x, 0x%08x, 0x%08x }", + ip6_tests[0].hash_4t, ip6_tests[1].hash_4t, + ip6_tests[2].hash_4t, ip6_tests[0].hash_4t, r[0], + r[1], r[2], r[3]); + + n_key_copies = 6; + bigkey_len = k->key_length * n_key_copies; + bigdata_len = bigkey_len - 4; + bigkey = test_mem_alloc_and_splat (k->key_length, n_key_copies, k->data); + bigdata0 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0); + bigdata1 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0); + bigdata2 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0); + bigdata3 = test_mem_alloc_and_fill_inc_u8 (bigdata_len, 0, 0); + u32 key_len = k->key_length; + + clib_toeplitz_hash_key_free (k); + k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len); + + for (int i = 0; i < N_LENGTH_TESTS - 4; i++) + { + wrapper_x4 (k, bigdata0, bigdata1, bigdata2, bigdata3, r, r + 1, r + 2, + r + 3, i); + if (length_test_hashes[i] != r[0] || length_test_hashes[i] != r[1] || + length_test_hashes[i] != r[2] || length_test_hashes[i] != r[3]) + { + err = clib_error_return ( + err, + "wrong length test hash x4 for length %u, " + "calculated { 0x%08x, 0x%08x, 0x%08x, 0x%08x }, expected 0x%08x", + i, r[0], r[1], r[2], r[3], length_test_hashes[i]); + goto done; + } + } + +done: + clib_toeplitz_hash_key_free (k); + test_mem_free (bigkey); + test_mem_free (bigdata0); + test_mem_free (bigdata1); + test_mem_free (bigdata2); + test_mem_free (bigdata3); + return err; +} + +void __test_perf_fn +perftest_fixed_12byte_x4 (int fd, test_perf_t *tp) +{ + u32 n = tp->n_ops / 4; + u8 *d0 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[0].key); + u8 *d1 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[1].key); + u8 *d2 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[2].key); + u8 *d3 = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[3].key); + u32 *h0 = test_mem_alloc (4 * n); + u32 *h1 = test_mem_alloc (4 * n); + u32 *h2 = test_mem_alloc (4 * n); + u32 *h3 = test_mem_alloc (4 * n); + clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0); + + test_perf_event_enable (fd); + for (int i = 0; i < n; i++) + clib_toeplitz_hash_x4 (k, d0 + i * 12, d1 + i * 12, d2 + i * 12, + d3 + i * 12, h0 + i, h1 + i, h2 + i, h3 + i, 12); + test_perf_event_disable (fd); + + clib_toeplitz_hash_key_free (k); + test_mem_free (d0); + test_mem_free (d1); + test_mem_free (d2); + test_mem_free (d3); + test_mem_free (h0); + test_mem_free (h1); + test_mem_free (h2); + test_mem_free (h3); +} + +void __test_perf_fn +perftest_fixed_36byte_x4 (int fd, test_perf_t *tp) +{ + u32 n = tp->n_ops / 4; + u8 *d0 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[0].key); + u8 *d1 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[1].key); + u8 *d2 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[2].key); + u8 *d3 = test_mem_alloc_and_splat (36, n, (void *) &ip4_tests[3].key); + u32 *h0 = test_mem_alloc (4 * n); + u32 *h1 = test_mem_alloc (4 * n); + u32 *h2 = test_mem_alloc (4 * n); + u32 *h3 = test_mem_alloc (4 * n); + clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0); + + test_perf_event_enable (fd); + for (int i = 0; i < n; i++) + clib_toeplitz_hash_x4 (k, d0 + i * 36, d1 + i * 36, d2 + i * 36, + d3 + i * 36, h0 + i, h1 + i, h2 + i, h3 + i, 36); + test_perf_event_disable (fd); + + clib_toeplitz_hash_key_free (k); + test_mem_free (d0); + test_mem_free (d1); + test_mem_free (d2); + test_mem_free (d3); + test_mem_free (h0); + test_mem_free (h1); + test_mem_free (h2); + test_mem_free (h3); +} + +void __test_perf_fn +perftest_variable_size_x4 (int fd, test_perf_t *tp) +{ + u32 key_len, n_keys, n = tp->n_ops / 4; + u8 *key; + u8 *d0 = test_mem_alloc (n); + u8 *d1 = test_mem_alloc (n); + u8 *d2 = test_mem_alloc (n); + u8 *d3 = test_mem_alloc (n); + u32 *h0 = test_mem_alloc (sizeof (u32)); + u32 *h1 = test_mem_alloc (sizeof (u32)); + u32 *h2 = test_mem_alloc (sizeof (u32)); + u32 *h3 = test_mem_alloc (sizeof (u32)); + clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0); + + k = clib_toeplitz_hash_key_init (0, 0); + key_len = k->key_length; + n_keys = ((n + 4) / k->key_length) + 1; + key = test_mem_alloc_and_splat (n_keys, key_len, k->data); + clib_toeplitz_hash_key_free (k); + k = clib_toeplitz_hash_key_init (key, key_len * n_keys); + + test_perf_event_enable (fd); + clib_toeplitz_hash_x4 (k, d0, d1, d2, d3, h0, h1, h2, h3, n); + test_perf_event_disable (fd); + + clib_toeplitz_hash_key_free (k); + test_mem_free (key); + test_mem_free (d0); + test_mem_free (d1); + test_mem_free (d2); + test_mem_free (d3); + test_mem_free (h0); + test_mem_free (h1); + test_mem_free (h2); + test_mem_free (h3); +} + +REGISTER_TEST (clib_toeplitz_hash_x4) = { + .name = "clib_toeplitz_hash_x4", + .fn = test_clib_toeplitz_hash_x4, + .perf_tests = PERF_TESTS ({ .name = "fixed_12", + .op_name = "12B Tuple", + .n_ops = 1024, + .fn = perftest_fixed_12byte_x4 }, + { .name = "fixed_36", + .op_name = "36B Tuple", + .n_ops = 1024, + .fn = perftest_fixed_36byte_x4 }, + { .name = "variable_size", + .op_name = "Byte", + .n_ops = 16384, + .fn = perftest_variable_size_x4 }), +}; diff --git a/src/vppinfra/vector/toeplitz.h b/src/vppinfra/vector/toeplitz.h index a199a4d68a6..76297f05195 100644 --- a/src/vppinfra/vector/toeplitz.h +++ b/src/vppinfra/vector/toeplitz.h @@ -16,13 +16,6 @@ typedef struct clib_toeplitz_hash_key_t *clib_toeplitz_hash_key_init (u8 *key, u32 keylen); void clib_toeplitz_hash_key_free (clib_toeplitz_hash_key_t *k); -#if defined(__GFNI__) && defined(__AVX512F__) - -#define u64x8_gf2p8_affine(d, m, imm) \ - (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) (d), (__m512i) (m), imm) - -#endif - #ifdef CLIB_HAVE_VEC256 static_always_inline u32x8 toeplitz_hash_one_x8 (u32x8 hash, u64x4 v4, u8 data, u8 off) @@ -40,6 +33,58 @@ toeplitz_hash_one_x8 (u32x8 hash, u64x4 v4, u8 data, u8 off) } #endif +#if defined(__GFNI__) && defined(__AVX512F__) +static const u8x64 __clib_toeplitz_hash_gfni_permute = { + /* clang-format off */ + 0x00, 0x01, 0x02, 0x03, 0x40, 0x41, 0x42, 0x43, + 0x01, 0x02, 0x03, 0x04, 0x41, 0x42, 0x43, 0x44, + 0x02, 0x03, 0x04, 0x05, 0x42, 0x43, 0x44, 0x45, + 0x03, 0x04, 0x05, 0x06, 0x43, 0x44, 0x45, 0x46, + 0x04, 0x05, 0x06, 0x07, 0x44, 0x45, 0x46, 0x47, + 0x05, 0x06, 0x07, 0x08, 0x45, 0x46, 0x47, 0x48, + 0x06, 0x07, 0x08, 0x09, 0x46, 0x47, 0x48, 0x49, + 0x07, 0x08, 0x09, 0x0a, 0x47, 0x48, 0x49, 0x4a + /* clang-format on */ +}; +static_always_inline u64x8 +clib_toeplitz_hash_gfni_one (u8x64 d0, u64x8 m, int i) +{ + + d0 = i == 1 ? (u8x64) u64x8_align_right (d0, d0, 1) : d0; + d0 = i == 2 ? (u8x64) u64x8_align_right (d0, d0, 2) : d0; + d0 = i == 3 ? (u8x64) u64x8_align_right (d0, d0, 3) : d0; + d0 = i == 4 ? (u8x64) u64x8_align_right (d0, d0, 4) : d0; + d0 = i == 5 ? (u8x64) u64x8_align_right (d0, d0, 5) : d0; + d0 = i == 6 ? (u8x64) u64x8_align_right (d0, d0, 6) : d0; + + d0 = u8x64_permute (__clib_toeplitz_hash_gfni_permute, d0); + + return (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) d0, (__m512i) m, 0); +} + +static_always_inline u64x8 +clib_toeplitz_hash_gfni_two (u8x64 d0, u8x64 d1, u64x8 m, int i) +{ + + d0 = i == 1 ? (u8x64) u64x8_align_right (d0, d0, 1) : d0; + d1 = i == 1 ? (u8x64) u64x8_align_right (d1, d1, 1) : d1; + d0 = i == 2 ? (u8x64) u64x8_align_right (d0, d0, 2) : d0; + d1 = i == 2 ? (u8x64) u64x8_align_right (d1, d1, 2) : d1; + d0 = i == 3 ? (u8x64) u64x8_align_right (d0, d0, 3) : d0; + d1 = i == 3 ? (u8x64) u64x8_align_right (d1, d1, 3) : d1; + d0 = i == 4 ? (u8x64) u64x8_align_right (d0, d0, 4) : d0; + d1 = i == 4 ? (u8x64) u64x8_align_right (d1, d1, 4) : d1; + d0 = i == 5 ? (u8x64) u64x8_align_right (d0, d0, 5) : d0; + d1 = i == 5 ? (u8x64) u64x8_align_right (d1, d1, 5) : d1; + d0 = i == 6 ? (u8x64) u64x8_align_right (d0, d0, 6) : d0; + d1 = i == 6 ? (u8x64) u64x8_align_right (d1, d1, 6) : d1; + + d0 = u8x64_permute2 (__clib_toeplitz_hash_gfni_permute, d0, d1); + + return (u64x8) _mm512_gf2p8affine_epi64_epi8 ((__m512i) d0, (__m512i) m, 0); +} +#endif + static_always_inline u32 clib_toeplitz_hash (clib_toeplitz_hash_key_t *k, u8 *data, int n_bytes) { @@ -48,91 +93,68 @@ clib_toeplitz_hash (clib_toeplitz_hash_key_t *k, u8 *data, int n_bytes) ASSERT (k->key_length - n_bytes >= 4); #if defined(__GFNI__) && defined(__AVX512F__) - u8x64 a, b, dv; - u64x8 xor_sum_x8 = {}; + u8x64 d0; + u64x8 h0 = {}; u64x8u *m = (u64x8u *) ((u8 *) k + k->gfni_offset); - u8x64 idx = { 0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x02, 0x03, 0x01, 0x02, - 0x03, 0x04, 0x01, 0x02, 0x03, 0x04, 0x02, 0x03, 0x04, 0x05, - 0x02, 0x03, 0x04, 0x05, 0x03, 0x04, 0x05, 0x06, 0x03, 0x04, - 0x05, 0x06, 0x04, 0x05, 0x06, 0x07, 0x04, 0x05, 0x06, 0x07, - 0x05, 0x06, 0x07, 0x08, 0x05, 0x06, 0x07, 0x08, 0x06, 0x07, - 0x08, 0x09, 0x06, 0x07, 0x08, 0x09, 0x07, 0x08, 0x09, 0x0a, - 0x07, 0x08, 0x09, 0x0a }; - /* move data ptr backwards for 3 byte so mask load "prepends" three zeros */ data -= 3; n_bytes += 3; if (n_bytes < 64) { - dv = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes - 3) << 3); + d0 = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes - 3) << 3); goto last8; } - dv = u8x64_mask_load_zero ((u8 *) data, -1ULL << 3); + d0 = u8x64_mask_load_zero ((u8 *) data, -1ULL << 3); next56: - a = u8x64_permute (idx, dv); - b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 1)); - xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[0], 0), - u64x8_gf2p8_affine (b, m[1], 0)); - - a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 2)); - b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 3)); - xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[2], 0), - u64x8_gf2p8_affine (b, m[3], 0)); - - a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 4)); - b = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 5)); - xor_sum_x8 = u64x8_xor3 (xor_sum_x8, u64x8_gf2p8_affine (a, m[4], 0), - u64x8_gf2p8_affine (b, m[5], 0)); - - a = u8x64_permute (idx, (u8x64) u64x8_align_right (dv, dv, 6)); - xor_sum_x8 ^= u64x8_gf2p8_affine (a, m[6], 0); + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[0], 0), + clib_toeplitz_hash_gfni_one (d0, m[1], 1)); + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[2], 2), + clib_toeplitz_hash_gfni_one (d0, m[3], 3)); + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_one (d0, m[4], 4), + clib_toeplitz_hash_gfni_one (d0, m[5], 5)); + h0 ^= clib_toeplitz_hash_gfni_one (d0, m[6], 6); n_bytes -= 56; data += 56; m += 7; if (n_bytes >= 64) { - dv = *(u8x64u *) data; + d0 = *(u8x64u *) data; goto next56; } if (n_bytes == 0) goto done; - dv = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes)); + d0 = u8x64_mask_load_zero ((u8 *) data, pow2_mask (n_bytes)); last8: - a = u8x64_permute (idx, dv); - xor_sum_x8 ^= u64x8_gf2p8_affine (a, m[0], 0); + h0 ^= clib_toeplitz_hash_gfni_one (d0, m[0], 0); n_bytes -= 8; if (n_bytes > 0) { m += 1; - dv = (u8x64) u64x8_align_right (u64x8_zero (), dv, 1); + d0 = (u8x64) u64x8_align_right (u64x8_zero (), d0, 1); goto last8; } done: - /* horizontal xor */ - xor_sum_x8 ^= u64x8_align_right (xor_sum_x8, xor_sum_x8, 4); - xor_sum_x8 ^= u64x8_align_right (xor_sum_x8, xor_sum_x8, 2); - return xor_sum_x8[0] ^ xor_sum_x8[1]; + return u64x8_hxor (h0); #elif defined(CLIB_HAVE_VEC256) u64x4 v4, shift = { 0, 1, 2, 3 }; - u32x8 hash8 = {}; - u32x4 hash4; + u32x8 h0 = {}; while (n_bytes >= 4) { v4 = u64x4_splat (clib_net_to_host_u64 (*(u64u *) key)) << shift; - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[2], 2); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[3], 3); + h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0); + h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1); + h0 = toeplitz_hash_one_x8 (h0, v4, data[2], 2); + h0 = toeplitz_hash_one_x8 (h0, v4, data[3], 3); data += 4; key += 4; @@ -149,29 +171,25 @@ done: v |= (u64) key[5] << 16; v |= (u64) key[6] << 8; v4 = u64x4_splat (v) << shift; - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[2], 2); + h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0); + h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1); + h0 = toeplitz_hash_one_x8 (h0, v4, data[2], 2); } else if (n_bytes == 2) { v |= (u64) key[5] << 16; v4 = u64x4_splat (v) << shift; - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0); - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[1], 1); + h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0); + h0 = toeplitz_hash_one_x8 (h0, v4, data[1], 1); } else { v4 = u64x4_splat (v) << shift; - hash8 = toeplitz_hash_one_x8 (hash8, v4, data[0], 0); + h0 = toeplitz_hash_one_x8 (h0, v4, data[0], 0); } } - hash4 = u32x8_extract_lo (hash8) ^ u32x8_extract_hi (hash8); - hash4 ^= (u32x4) u8x16_align_right (hash4, hash4, 8); - hash4 ^= (u32x4) u8x16_align_right (hash4, hash4, 4); - return hash4[0]; - + return u32x8_hxor (h0); #endif u64 v, hash = 0; @@ -215,4 +233,281 @@ done: return hash >> 32; } +static_always_inline void +clib_toeplitz_hash_x4 (clib_toeplitz_hash_key_t *k, u8 *data0, u8 *data1, + u8 *data2, u8 *data3, u32 *hash0, u32 *hash1, + u32 *hash2, u32 *hash3, int n_bytes) +{ + /* key must be 4 bytes longer than data */ + ASSERT (k->key_length - n_bytes >= 4); +#if defined(__GFNI__) && defined(__AVX512F__) + u64x8u *m = (u64x8u *) ((u8 *) k + k->gfni_offset); + u8x64 d0, d1, d2, d3; + u64x8 h0 = {}, h2 = {}; + u64 h, mask; + + /* move data ptr backwards for 3 byte so mask load "prepends" three zeros */ + data0 -= 3; + data1 -= 3; + data2 -= 3; + data3 -= 3; + n_bytes += 3; + + if (n_bytes < 64) + { + mask = pow2_mask (n_bytes - 3) << 3; + d0 = u8x64_mask_load_zero ((u8 *) data0, mask); + d1 = u8x64_mask_load_zero ((u8 *) data1, mask); + d2 = u8x64_mask_load_zero ((u8 *) data2, mask); + d3 = u8x64_mask_load_zero ((u8 *) data3, mask); + goto last8; + } + + mask = -1ULL << 3; + d0 = u8x64_mask_load_zero ((u8 *) data0, mask); + d1 = u8x64_mask_load_zero ((u8 *) data1, mask); + d2 = u8x64_mask_load_zero ((u8 *) data2, mask); + d3 = u8x64_mask_load_zero ((u8 *) data3, mask); +next56: + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[0], 0), + clib_toeplitz_hash_gfni_two (d0, d1, m[1], 1)); + h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[0], 0), + clib_toeplitz_hash_gfni_two (d2, d3, m[1], 1)); + + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[2], 2), + clib_toeplitz_hash_gfni_two (d0, d1, m[3], 3)); + h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[2], 2), + clib_toeplitz_hash_gfni_two (d2, d3, m[3], 3)); + + h0 = u64x8_xor3 (h0, clib_toeplitz_hash_gfni_two (d0, d1, m[4], 4), + clib_toeplitz_hash_gfni_two (d0, d1, m[5], 5)); + h2 = u64x8_xor3 (h2, clib_toeplitz_hash_gfni_two (d2, d3, m[4], 4), + clib_toeplitz_hash_gfni_two (d2, d3, m[5], 5)); + + h0 ^= clib_toeplitz_hash_gfni_two (d0, d1, m[6], 6); + h2 ^= clib_toeplitz_hash_gfni_two (d2, d3, m[6], 6); + + n_bytes -= 56; + data0 += 56; + data1 += 56; + data2 += 56; + data3 += 56; + m += 7; + + if (n_bytes >= 64) + { + d0 = *(u8x64u *) data0; + d1 = *(u8x64u *) data1; + d2 = *(u8x64u *) data2; + d3 = *(u8x64u *) data3; + goto next56; + } + + if (n_bytes == 0) + goto done; + + mask = pow2_mask (n_bytes); + d0 = u8x64_mask_load_zero ((u8 *) data0, mask); + d1 = u8x64_mask_load_zero ((u8 *) data1, mask); + d2 = u8x64_mask_load_zero ((u8 *) data2, mask); + d3 = u8x64_mask_load_zero ((u8 *) data3, mask); +last8: + h0 ^= clib_toeplitz_hash_gfni_two (d0, d1, m[0], 0); + h2 ^= clib_toeplitz_hash_gfni_two (d2, d3, m[0], 0); + n_bytes -= 8; + + if (n_bytes > 0) + { + u64x8 zero = {}; + m += 1; + d0 = (u8x64) u64x8_align_right (zero, d0, 1); + d1 = (u8x64) u64x8_align_right (zero, d1, 1); + d2 = (u8x64) u64x8_align_right (zero, d2, 1); + d3 = (u8x64) u64x8_align_right (zero, d3, 1); + goto last8; + } + +done: + h = u64x8_hxor (h0); + *hash0 = h; + *hash1 = h >> 32; + h = u64x8_hxor (h2); + *hash2 = h; + *hash3 = h >> 32; +#elif defined(CLIB_HAVE_VEC256) + u8 *key = k->data; + u64x4 v4, shift = { 0, 1, 2, 3 }; + u32x8 h0 = {}, h1 = {}, h2 = {}, h3 = {}; + + while (n_bytes >= 4) + { + v4 = u64x4_splat (clib_net_to_host_u64 (*(u64u *) key)) << shift; + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[2], 2); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[2], 2); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[2], 2); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[2], 2); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[3], 3); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[3], 3); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[3], 3); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[3], 3); + + data0 += 4; + data1 += 4; + data2 += 4; + data3 += 4; + key += 4; + n_bytes -= 4; + } + + if (n_bytes) + { + u64 v = (u64) clib_net_to_host_u32 ((u64) (*(u32u *) key)) << 32; + v |= (u64) key[4] << 24; + + if (n_bytes == 3) + { + v |= (u64) key[5] << 16; + v |= (u64) key[6] << 8; + v4 = u64x4_splat (v) << shift; + h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[2], 2); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[2], 2); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[2], 2); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[2], 2); + } + else if (n_bytes == 2) + { + v |= (u64) key[5] << 16; + v4 = u64x4_splat (v) << shift; + h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0); + + h0 = toeplitz_hash_one_x8 (h0, v4, data0[1], 1); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[1], 1); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[1], 1); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[1], 1); + } + else + { + v4 = u64x4_splat (v) << shift; + h0 = toeplitz_hash_one_x8 (h0, v4, data0[0], 0); + h1 = toeplitz_hash_one_x8 (h1, v4, data1[0], 0); + h2 = toeplitz_hash_one_x8 (h2, v4, data2[0], 0); + h3 = toeplitz_hash_one_x8 (h3, v4, data3[0], 0); + } + } + + *hash0 = u32x8_hxor (h0); + *hash1 = u32x8_hxor (h1); + *hash2 = u32x8_hxor (h2); + *hash3 = u32x8_hxor (h3); +#else + u8 *key = k->data; + u64 v, h0 = 0, h1 = 0, h2 = 0, h3 = 0; + + while (n_bytes >= 4) + { + v = clib_net_to_host_u64 (*(u64u *) key); + + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[0] & bit ? v : 0; + h1 ^= data1[0] & bit ? v : 0; + h2 ^= data2[0] & bit ? v : 0; + h3 ^= data3[0] & bit ? v : 0; + } + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[1] & bit ? v : 0; + h1 ^= data1[1] & bit ? v : 0; + h2 ^= data2[1] & bit ? v : 0; + h3 ^= data3[1] & bit ? v : 0; + } + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[2] & bit ? v : 0; + h1 ^= data1[2] & bit ? v : 0; + h2 ^= data2[2] & bit ? v : 0; + h3 ^= data3[2] & bit ? v : 0; + } + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[3] & bit ? v : 0; + h1 ^= data1[3] & bit ? v : 0; + h2 ^= data2[3] & bit ? v : 0; + h3 ^= data3[3] & bit ? v : 0; + } + + data0 += 4; + data1 += 4; + data2 += 4; + data3 += 4; + key += 4; + n_bytes -= 4; + } + + if (n_bytes) + { + v = (u64) clib_net_to_host_u32 ((u64) (*(u32u *) key)) << 32; + v |= (u64) key[4] << 24; + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[0] & bit ? v : 0; + h1 ^= data1[0] & bit ? v : 0; + h2 ^= data2[0] & bit ? v : 0; + h3 ^= data3[0] & bit ? v : 0; + } + if (n_bytes > 1) + { + v |= (u64) key[5] << 24; + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[1] & bit ? v : 0; + h1 ^= data1[1] & bit ? v : 0; + h2 ^= data2[1] & bit ? v : 0; + h3 ^= data3[1] & bit ? v : 0; + } + } + if (n_bytes > 2) + { + v |= (u64) key[6] << 24; + for (u8 bit = 1 << 7; bit; bit >>= 1, v <<= 1) + { + h0 ^= data0[2] & bit ? v : 0; + h1 ^= data1[2] & bit ? v : 0; + h2 ^= data2[2] & bit ? v : 0; + h3 ^= data3[2] & bit ? v : 0; + } + } + } + *hash0 = h0 >> 32; + *hash1 = h1 >> 32; + *hash2 = h2 >> 32; + *hash3 = h3 >> 32; +#endif +} + #endif diff --git a/src/vppinfra/vector_avx2.h b/src/vppinfra/vector_avx2.h index 59857182a93..6a363ccfa92 100644 --- a/src/vppinfra/vector_avx2.h +++ b/src/vppinfra/vector_avx2.h @@ -203,6 +203,16 @@ u32x8_hadd (u32x8 v1, u32x8 v2) return (u32x8) _mm256_hadd_epi32 ((__m256i) v1, (__m256i) v2); } +static_always_inline u32 +u32x8_hxor (u32x8 v) +{ + u32x4 v4; + v4 = u32x8_extract_lo (v) ^ u32x8_extract_hi (v); + v4 ^= (u32x4) u8x16_align_right (v4, v4, 8); + v4 ^= (u32x4) u8x16_align_right (v4, v4, 4); + return v4[0]; +} + static_always_inline u16x16 u16x16_mask_last (u16x16 v, u8 n_last) { diff --git a/src/vppinfra/vector_avx512.h b/src/vppinfra/vector_avx512.h index 3505961dca5..e71a8a70aa9 100644 --- a/src/vppinfra/vector_avx512.h +++ b/src/vppinfra/vector_avx512.h @@ -322,9 +322,16 @@ u8x64_mask_blend (u8x64 a, u8x64 b, u64 mask) } static_always_inline u8x64 -u8x64_permute (u8x64 v, u8x64 idx) +u8x64_permute (u8x64 idx, u8x64 a) { - return (u8x64) _mm512_permutexvar_epi8 ((__m512i) v, (__m512i) idx); + return (u8x64) _mm512_permutexvar_epi8 ((__m512i) idx, (__m512i) a); +} + +static_always_inline u8x64 +u8x64_permute2 (u8x64 idx, u8x64 a, u8x64 b) +{ + return (u8x64) _mm512_permutex2var_epi8 ((__m512i) a, (__m512i) idx, + (__m512i) b); } #define _(t, m, e, p, it) \ @@ -436,6 +443,14 @@ u16x8_compress (u16x8 v, u8 mask) } #endif +static_always_inline u64 +u64x8_hxor (u64x8 v) +{ + v ^= u64x8_align_right (v, v, 4); + v ^= u64x8_align_right (v, v, 2); + return v[0] ^ v[1]; +} + static_always_inline void u32x16_transpose (u32x16 m[16]) { -- cgit 1.2.3-korg