1 /* SPDX-License-Identifier: Apache-2.0
2 * Copyright(c) 2021 Cisco Systems, Inc.
5 #include <vppinfra/format.h>
6 #include <vppinfra/vector/test/test.h>
7 #include <vppinfra/vector/toeplitz.h>
9 /* secret key and test cases taken from:
10 * https://docs.microsoft.com/en-us/windows-hardware/drivers/network/verifying-the-rss-hash-calculation
17 } __clib_packed ip4_key_t;
29 } __clib_packed ip6_key_t;
39 #define N_LENGTH_TESTS 240
41 #ifndef CLIB_MARCH_VARIANT
42 #define _IP4(a, b, c, d) ((d) << 24 | (c) << 16 | (b) << 8 | (a))
43 #define _IP6(a, b, c, d, e, f, g, h) \
45 (u16) ((a) << 8) | (u8) ((a) >> 8), (u16) ((b) << 8) | (u8) ((b) >> 8), \
46 (u16) ((c) << 8) | (u8) ((c) >> 8), (u16) ((d) << 8) | (u8) ((d) >> 8), \
47 (u16) ((e) << 8) | (u8) ((e) >> 8), (u16) ((f) << 8) | (u8) ((f) >> 8), \
48 (u16) ((g) << 8) | (u8) ((g) >> 8), (u16) ((h) << 8) | (u8) ((h) >> 8), \
50 #define _PORT(a) ((a) >> 8 | (((a) &0xff) << 8))
52 const ip4_test_t ip4_tests[N_IP4_TESTS] = {
55 .key.sip = _IP4 (66, 9, 149, 187),
56 .key.dip = _IP4 (161, 142, 100, 80),
57 .key.sport = _PORT (2794),
58 .key.dport = _PORT (1766),
59 .hash_2t = 0x323e8fc2,
60 .hash_4t = 0x51ccc178,
63 .key.sip = _IP4 (199, 92, 111, 2),
64 .key.dip = _IP4 (65, 69, 140, 83),
65 .key.sport = _PORT (14230),
66 .key.dport = _PORT (4739),
67 .hash_2t = 0xd718262a,
68 .hash_4t = 0xc626b0ea,
71 .key.sip = _IP4 (24, 19, 198, 95),
72 .key.dip = _IP4 (12, 22, 207, 184),
73 .key.sport = _PORT (12898),
74 .key.dport = _PORT (38024),
75 .hash_2t = 0xd2d0a5de,
76 .hash_4t = 0x5c2b394a,
79 .key.sip = _IP4 (38, 27, 205, 30),
80 .key.dip = _IP4 (209, 142, 163, 6),
81 .key.sport = _PORT (48228),
82 .key.dport = _PORT (2217),
83 .hash_2t = 0x82989176,
84 .hash_4t = 0xafc7327f,
87 .key.sip = _IP4 (153, 39, 163, 191),
88 .key.dip = _IP4 (202, 188, 127, 2),
89 .key.sport = _PORT (44251),
90 .key.dport = _PORT (1303),
91 .hash_2t = 0x5d1809c5,
92 .hash_4t = 0x10e828a2,
96 const ip6_test_t ip6_tests[N_IP6_TESTS] = {
98 .key.sip = _IP6 (0x3ffe, 0x2501, 0x200, 0x1fff, 0, 0, 0, 7),
99 .key.dip = _IP6 (0x3ffe, 0x2501, 0x200, 3, 0, 0, 0, 1),
100 .key.sport = _PORT (2794),
101 .key.dport = _PORT (1766),
102 .hash_2t = 0x2cc18cd5,
103 .hash_4t = 0x40207d3d,
106 .key.sip = _IP6 (0x3ffe, 0x501, 8, 0, 0x260, 0x97ff, 0xfe40, 0xefab),
107 .key.dip = _IP6 (0xff02, 0, 0, 0, 0, 0, 0, 1),
108 .key.sport = _PORT (14230),
109 .key.dport = _PORT (4739),
110 .hash_2t = 0x0f0c461c,
111 .hash_4t = 0xdde51bbf,
114 .key.sip = _IP6 (0x3ffe, 0x1900, 0x4545, 3, 0x200, 0xf8ff, 0xfe21, 0x67cf),
115 .key.dip = _IP6 (0xfe80, 0, 0, 0, 0x200, 0xf8ff, 0xfe21, 0x67cf),
116 .key.sport = _PORT (44251),
117 .key.dport = _PORT (38024),
118 .hash_2t = 0x4b61e985,
119 .hash_4t = 0x02d1feef,
123 const u32 length_test_hashes[N_LENGTH_TESTS] = {
124 0x00000000, 0x00000000, 0x2b6d12ad, 0x9de4446e, 0x061f00bf, 0xad7ed8f7,
125 0x4bc7b068, 0x231fc545, 0xdbd97a33, 0xcdab29e7, 0x2d665c0c, 0x31e28ed7,
126 0x14e19218, 0x5aa89f0f, 0xd47de07f, 0x355ec712, 0x7e1cbfc0, 0xf84de19d,
127 0xbcf66bd3, 0x104086c6, 0x71900b34, 0xcd2f9819, 0xeae68ebb, 0x54d63b4c,
128 0x5f865a2c, 0x9d6ded08, 0xe00b0912, 0x3fcf07a6, 0x3bd9ca93, 0x3f4f3bbb,
129 0xd0b82624, 0xa28a08e1, 0xa585969f, 0x0c8f4a71, 0x5dce7bdd, 0x4fcf2a6d,
130 0x91c89ae9, 0xbef8a24d, 0x8e3d30fe, 0xc8027848, 0xc1e7e513, 0xa12bd3d9,
131 0x46700bb4, 0xc6339dab, 0x970805ad, 0xfcb50ac8, 0xc6db4f44, 0x792e2987,
132 0xacfb7836, 0xa25ec529, 0x957d7beb, 0x6732809a, 0x891836ed, 0xeefb83b2,
133 0xca96b40b, 0x93fd5abd, 0x9076f922, 0x59adb4eb, 0x9705aafb, 0x282719b1,
134 0xdda9cb8a, 0x3f499131, 0x47491130, 0x30ef0759, 0xad1cf855, 0x428aa312,
135 0x4200240a, 0x71a72857, 0x16b30c36, 0x10cca9a3, 0x166f091e, 0x30e00560,
136 0x8acd20ba, 0xfa633d76, 0x0fe32eb7, 0xdcc0122f, 0x20aa8ab0, 0x62b2a9af,
137 0x7a6c80a6, 0x27e87268, 0x95b797a8, 0x25d18ccd, 0x68a7fb00, 0xc54bcdad,
138 0x3bd0e717, 0xf0df54c9, 0x780daadf, 0x7b435605, 0x150c1e10, 0x8a892e54,
139 0x9d27cb25, 0xe23383a5, 0x57aac408, 0x83b8abf8, 0x560f33af, 0xd5cb3307,
140 0x79ae8edc, 0x9b127665, 0x320f18bd, 0x385d636b, 0xbd1b2dbf, 0x97679888,
141 0x738894a4, 0xeba2afb0, 0xfa7c2d50, 0xb6741aa1, 0x28922bba, 0x7783242b,
142 0xa694cca2, 0xa32781c0, 0x696cd670, 0xa714d72f, 0xea34d35a, 0xc5aed81e,
143 0x0438433a, 0xc1939ab2, 0xb51c123a, 0x121426b9, 0x1add93ba, 0x50c56b6a,
144 0x7e90902a, 0xae3abd85, 0x2f7a0088, 0xb45cf6f9, 0x80070094, 0x8bd46467,
145 0xdfd1b762, 0x0bb25856, 0x48eefe84, 0x0989dbb9, 0xfc32472b, 0x965fec6b,
146 0x5a256bd0, 0x6df7127a, 0x7856d0d6, 0xedc82bd3, 0x1b563b96, 0xc73eace7,
147 0xba4c0a93, 0xdfd6dd97, 0x923c41db, 0x14926ca6, 0x22e52ab1, 0x22852a66,
148 0x79606b9c, 0xb0f22b23, 0xb46354ba, 0x9c3cd931, 0x03a92bd6, 0x84000834,
149 0x5425df65, 0xf4dd3fc9, 0x391cc873, 0xa560b52e, 0x828037d9, 0x31323dd5,
150 0x5c6e3147, 0x28e21f85, 0xa431eb51, 0xf468c4a3, 0x9bea1d2e, 0x43d9109c,
151 0x5bb9b081, 0xe0825675, 0xc9c92591, 0xd29fc812, 0x03136bc9, 0x5e005a1f,
152 0x6d821ed8, 0x3f0bfcc4, 0x24774162, 0x893bde94, 0x6475efea, 0x6711538e,
153 0xc4755f6d, 0x9425ebe2, 0xacf471b4, 0xb947ab0c, 0x1f78c455, 0x372b3ed7,
154 0xb3ec24d7, 0x18c4459f, 0xa8ff3695, 0xe4aa2b85, 0x8a52ad7e, 0xe05e8177,
155 0x7aa348ed, 0x3e4ac6aa, 0x17dcf8a5, 0x93b933b0, 0x8f7413ec, 0xc77bfe61,
156 0xfdb72874, 0x4370f138, 0xdf3462ad, 0xc8970a59, 0xb4a9fed8, 0xa2ddc39b,
157 0xd61db62a, 0x95c5fc1b, 0x7b22e6e0, 0x1969702c, 0x7992aebb, 0x59d7c225,
158 0x0e16db0b, 0x9f2afc21, 0x246cf66b, 0xb3d6569d, 0x29c532d7, 0xe155747a,
159 0xe38d7872, 0xea704969, 0xb69095b0, 0x1b198efd, 0x55daab76, 0xa2a377b6,
160 0xb31aa2fa, 0x48b73c41, 0xf0cc501a, 0x9c9ca831, 0x1b591b99, 0xb2d8d22f,
161 0xab4b5f69, 0x4fe00e71, 0xdf5480bd, 0x982540d7, 0x7f34ea4f, 0xd7be66e1,
162 0x9d2ab1ba, 0x1ba62e12, 0xee3fb36c, 0xf28d7c5a, 0x756311eb, 0xc68567f2,
163 0x7b6ea177, 0xc398d9f3
167 extern const ip4_test_t ip4_tests[N_IP4_TESTS];
168 extern const ip6_test_t ip6_tests[N_IP6_TESTS];
169 extern const u32 length_test_hashes[N_LENGTH_TESTS];
173 wrapper (clib_toeplitz_hash_key_t *k, u8 *data, u32 n_bytes)
175 return clib_toeplitz_hash (k, data, n_bytes);
178 static clib_error_t *
179 test_clib_toeplitz_hash (clib_error_t *err)
182 int n_key_copies, bigkey_len, bigdata_len;
183 u8 *bigkey, *bigdata;
184 clib_toeplitz_hash_key_t *k;
186 k = clib_toeplitz_hash_key_init (0, 0);
188 for (int i = 0; i < N_IP4_TESTS; i++)
190 r = wrapper (k, (u8 *) &ip4_tests[i].key, 8);
191 if (ip4_tests[i].hash_2t != r)
192 return clib_error_return (err,
193 "wrong IPv4 2 tuple hash for test %u, "
194 "calculated 0x%08x expected 0x%08x",
195 i, ip4_tests[i].hash_2t, r);
197 r = wrapper (k, (u8 *) &ip4_tests[i].key, 12);
198 if (ip4_tests[i].hash_4t != r)
199 return clib_error_return (err,
200 "wrong IPv4 4 tuple hash for test %u, "
201 "calculated 0x%08x expected 0x%08x",
202 i, ip4_tests[i].hash_4t, r);
205 for (int i = 0; i < N_IP6_TESTS; i++)
207 r = wrapper (k, (u8 *) &ip6_tests[i].key, 32);
208 if (ip6_tests[i].hash_2t != r)
209 return clib_error_return (err,
210 "wrong IPv6 2 tuple hash for test %u, "
211 "calculated 0x%08x expected 0x%08x",
212 i, ip6_tests[i].hash_2t, r);
214 r = wrapper (k, (u8 *) &ip6_tests[i].key, 36);
215 if (ip6_tests[i].hash_4t != r)
216 return clib_error_return (err,
217 "wrong IPv6 4 tuple hash for test %u, "
218 "calculated 0x%08x expected 0x%08x",
219 i, ip6_tests[i].hash_4t, r);
223 bigkey_len = k->key_length * n_key_copies;
224 bigdata_len = bigkey_len - 4;
225 bigkey = clib_mem_alloc (bigkey_len);
226 bigdata = clib_mem_alloc (bigdata_len);
227 u32 key_len = k->key_length;
229 for (int i = 0; i < n_key_copies; i++)
230 clib_memcpy (bigkey + i * key_len, k->data, key_len);
232 for (int i = 0; i < bigdata_len; i++)
235 clib_toeplitz_hash_key_free (k);
236 k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len);
238 for (int i = 0; i < N_LENGTH_TESTS - 4; i++)
240 r = wrapper (k, bigdata, i);
241 if (length_test_hashes[i] != r)
243 err = clib_error_return (err,
244 "wrong length test hash for length %u, "
245 "calculated 0x%08x expected 0x%08x "
247 i, r, length_test_hashes[i],
248 r ^ length_test_hashes[i]);
254 clib_toeplitz_hash_key_free (k);
255 clib_mem_free (bigkey);
256 clib_mem_free (bigdata);
261 perftest_fixed_12byte (int fd, test_perf_t *tp)
264 u8 *data = test_mem_alloc_and_splat (12, n, (void *) &ip4_tests[0].key);
265 u8 *res = test_mem_alloc (4 * n);
266 clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
268 test_perf_event_enable (fd);
269 for (int i = 0; i < n; i++)
270 ((u32 *) res)[i] = clib_toeplitz_hash (k, data + i * 12, 12);
271 test_perf_event_disable (fd);
273 clib_toeplitz_hash_key_free (k);
274 test_mem_free (data);
279 perftest_fixed_36byte (int fd, test_perf_t *tp)
282 u8 *data = test_mem_alloc_and_splat (36, n, (void *) &ip6_tests[0].key);
283 u8 *res = test_mem_alloc (4 * n);
284 clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
286 test_perf_event_enable (fd);
287 for (int i = 0; i < n; i++)
288 ((u32 *) res)[i] = clib_toeplitz_hash (k, data + i * 36, 36);
289 test_perf_event_disable (fd);
291 clib_toeplitz_hash_key_free (k);
292 test_mem_free (data);
297 perftest_variable_size (int fd, test_perf_t *tp)
299 u32 key_len, n_keys, n = tp->n_ops;
300 u8 *key, *data = test_mem_alloc (n);
301 u32 *res = test_mem_alloc (sizeof (u32));
302 clib_toeplitz_hash_key_t *k = clib_toeplitz_hash_key_init (0, 0);
304 k = clib_toeplitz_hash_key_init (0, 0);
305 key_len = k->key_length;
306 n_keys = ((n + 4) / k->key_length) + 1;
307 key = test_mem_alloc_and_splat (n_keys, key_len, k->data);
308 clib_toeplitz_hash_key_free (k);
309 k = clib_toeplitz_hash_key_init (key, key_len * n_keys);
311 test_perf_event_enable (fd);
312 res[0] = clib_toeplitz_hash (k, data, n);
313 test_perf_event_disable (fd);
315 clib_toeplitz_hash_key_free (k);
316 test_mem_free (data);
321 REGISTER_TEST (clib_toeplitz_hash) = {
322 .name = "clib_toeplitz_hash",
323 .fn = test_clib_toeplitz_hash,
324 .perf_tests = PERF_TESTS ({ .name = "fixed_12",
325 .op_name = "12B Tuple",
327 .fn = perftest_fixed_12byte },
328 { .name = "fixed_36",
329 .op_name = "36B Tuple",
331 .fn = perftest_fixed_36byte },
332 { .name = "variable_size",
335 .fn = perftest_variable_size }),