src/vppinfra/vector/test/toeplitz.c

   1 /* SPDX-License-Identifier: Apache-2.0
   2  * Copyright(c) 2021 Cisco Systems, Inc.
   3  */
   4
   5 #include <vppinfra/format.h>
   6 #include <vppinfra/vector/test/test.h>
   7 #include <vppinfra/vector/toeplitz.h>
   8
   9 /* secret key and test cases taken from:
  10  * https://docs.microsoft.com/en-us/windows-hardware/drivers/network/verifying-the-rss-hash-calculation
  11  */
  12
  13 typedef struct
  14 {
  15   u32 sip, dip;
  16   u16 sport, dport;
  17 } __clib_packed ip4_key_t;
  18
  19 typedef struct
  20 {
  21   ip4_key_t key;
  22   u32 hash_2t, hash_4t;
  23 } ip4_test_t;
  24
  25 typedef struct
  26 {
  27   u16 sip[8], dip[8];
  28   u16 sport, dport;
  29 } __clib_packed ip6_key_t;
  30
  31 typedef struct
  32 {
  33   ip6_key_t key;
  34   u32 hash_2t, hash_4t;
  35 } ip6_test_t;
  36
  37 #define N_IP4_TESTS    5
  38 #define N_IP6_TESTS    3
  39 #define N_LENGTH_TESTS 240
  40
  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)                                          \
  44   {                                                                           \
  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), \
  49   }
  50 #define _PORT(a) ((a) >> 8 | (((a) &0xff) << 8))
  51
  52 const ip4_test_t ip4_tests[N_IP4_TESTS] = {
  53   /* ipv4 tests */
  54   {
  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,
  61   },
  62   {
  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,
  69   },
  70   {
  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,
  77   },
  78   {
  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,
  85   },
  86   {
  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,
  93   }
  94 };
  95
  96 const ip6_test_t ip6_tests[N_IP6_TESTS] = {
  97   {
  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,
 104   },
 105   {
 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,
 112   },
 113   {
 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,
 120   }
 121 };
 122
 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
 164 };
 165
 166 #else
 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];
 170 #endif
 171
 172 __test_funct_fn u32
 173 wrapper (clib_toeplitz_hash_key_t *k, u8 *data, u32 n_bytes)
 174 {
 175   return clib_toeplitz_hash (k, data, n_bytes);
 176 }
 177
 178 static clib_error_t *
 179 test_clib_toeplitz_hash (clib_error_t *err)
 180 {
 181   u32 r;
 182   int n_key_copies, bigkey_len, bigdata_len;
 183   u8 *bigkey, *bigdata;
 184   clib_toeplitz_hash_key_t *k;
 185
 186   k = clib_toeplitz_hash_key_init (0, 0);
 187
 188   for (int i = 0; i < N_IP4_TESTS; i++)
 189     {
 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);
 196
 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);
 203     }
 204
 205   for (int i = 0; i < N_IP6_TESTS; i++)
 206     {
 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);
 213
 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);
 220     }
 221
 222   n_key_copies = 6;
 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;
 228
 229   for (int i = 0; i < n_key_copies; i++)
 230     clib_memcpy (bigkey + i * key_len, k->data, key_len);
 231
 232   for (int i = 0; i < bigdata_len; i++)
 233     bigdata[i] = (u8) i;
 234
 235   clib_toeplitz_hash_key_free (k);
 236   k = clib_toeplitz_hash_key_init (bigkey, n_key_copies * key_len);
 237
 238   for (int i = 0; i < N_LENGTH_TESTS - 4; i++)
 239     {
 240       r = wrapper (k, bigdata, i);
 241       if (length_test_hashes[i] != r)
 242         {
 243           err = clib_error_return (err,
 244                                    "wrong length test hash for length %u, "
 245                                    "calculated 0x%08x expected 0x%08x "
 246                                    "xor 0x%08x",
 247                                    i, r, length_test_hashes[i],
 248                                    r ^ length_test_hashes[i]);
 249           goto done;
 250         }
 251     }
 252
 253 done:
 254   clib_toeplitz_hash_key_free (k);
 255   clib_mem_free (bigkey);
 256   clib_mem_free (bigdata);
 257   return err;
 258 }
 259
 260 void __test_perf_fn
 261 perftest_fixed_12byte (int fd, test_perf_t *tp)
 262 {
 263   u32 n = tp->n_ops;
 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);
 267
 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);
 272
 273   clib_toeplitz_hash_key_free (k);
 274   test_mem_free (data);
 275   test_mem_free (res);
 276 }
 277
 278 void __test_perf_fn
 279 perftest_fixed_36byte (int fd, test_perf_t *tp)
 280 {
 281   u32 n = tp->n_ops;
 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);
 285
 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);
 290
 291   clib_toeplitz_hash_key_free (k);
 292   test_mem_free (data);
 293   test_mem_free (res);
 294 }
 295
 296 void __test_perf_fn
 297 perftest_variable_size (int fd, test_perf_t *tp)
 298 {
 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);
 303
 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);
 310
 311   test_perf_event_enable (fd);
 312   res[0] = clib_toeplitz_hash (k, data, n);
 313   test_perf_event_disable (fd);
 314
 315   clib_toeplitz_hash_key_free (k);
 316   test_mem_free (data);
 317   test_mem_free (res);
 318   test_mem_free (key);
 319 }
 320
 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",
 326                               .n_ops = 1024,
 327                               .fn = perftest_fixed_12byte },
 328                             { .name = "fixed_36",
 329                               .op_name = "36B Tuple",
 330                               .n_ops = 1024,
 331                               .fn = perftest_fixed_36byte },
 332                             { .name = "variable_size",
 333                               .op_name = "Byte",
 334                               .n_ops = 16384,
 335                               .fn = perftest_variable_size }),
 336 };