test/test/test_hash_functions.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2015 Intel Corporation
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdint.h>
   7 #include <string.h>
   8 #include <stdlib.h>
   9 #include <stdarg.h>
  10 #include <errno.h>
  11 #include <sys/queue.h>
  12
  13 #include <rte_cycles.h>
  14 #include <rte_random.h>
  15 #include <rte_hash.h>
  16 #include <rte_jhash.h>
  17 #include <rte_hash_crc.h>
  18
  19 #include "test.h"
  20
  21 /*
  22  * Hash values calculated for key sizes from array "hashtest_key_lens"
  23  * and for initial values from array "hashtest_initvals.
  24  * Each key will be formed by increasing each byte by 1:
  25  * e.g.: key size = 4, key = 0x03020100
  26  *       key size = 8, key = 0x0706050403020100
  27  */
  28 static uint32_t hash_values_jhash[2][12] = {{
  29         0x8ba9414b, 0xdf0d39c9,
  30         0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
  31         0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
  32         0x12926a31, 0x1c9fa888
  33 },
  34 {
  35         0x5c62c303, 0x1b8cf784,
  36         0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
  37         0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
  38         0x91d0e462, 0x768087fc
  39 }
  40 };
  41 static uint32_t hash_values_crc[2][12] = {{
  42         0x00000000, 0xf26b8303,
  43         0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
  44         0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
  45         0x43f44466, 0x4a11475e
  46 },
  47 {
  48         0xbdfd3980, 0x70204542,
  49         0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
  50         0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
  51         0x789c104f, 0x53028d3e
  52 }
  53 };
  54
  55 /*******************************************************************************
  56  * Hash function performance test configuration section. Each performance test
  57  * will be performed HASHTEST_ITERATIONS times.
  58  *
  59  * The three arrays below control what tests are performed. Every combination
  60  * from the array entries is tested.
  61  */
  62 #define HASHTEST_ITERATIONS 1000000
  63 #define MAX_KEYSIZE 64
  64 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
  65 static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
  66 static uint32_t hashtest_key_lens[] = {
  67         1, 2,                 /* Unusual key sizes */
  68         4, 8, 16, 32, 48, 64, /* standard key sizes */
  69         9,                    /* IPv4 SRC + DST + protocol, unpadded */
  70         13,                   /* IPv4 5-tuple, unpadded */
  71         37,                   /* IPv6 5-tuple, unpadded */
  72         40                    /* IPv6 5-tuple, padded to 8-byte boundary */
  73 };
  74 /******************************************************************************/
  75
  76 /*
  77  * To help print out name of hash functions.
  78  */
  79 static const char *
  80 get_hash_name(rte_hash_function f)
  81 {
  82         if (f == rte_jhash)
  83                 return "jhash";
  84
  85         if (f == rte_hash_crc)
  86                 return "rte_hash_crc";
  87
  88         return "UnknownHash";
  89 }
  90
  91 /*
  92  * Test a hash function.
  93  */
  94 static void
  95 run_hash_func_perf_test(uint32_t key_len, uint32_t init_val,
  96                 rte_hash_function f)
  97 {
  98         static uint8_t key[HASHTEST_ITERATIONS][MAX_KEYSIZE];
  99         uint64_t ticks, start, end;
 100         unsigned i, j;
 101
 102         for (i = 0; i < HASHTEST_ITERATIONS; i++) {
 103                 for (j = 0; j < key_len; j++)
 104                         key[i][j] = (uint8_t) rte_rand();
 105         }
 106
 107         start = rte_rdtsc();
 108         for (i = 0; i < HASHTEST_ITERATIONS; i++)
 109                 f(key[i], key_len, init_val);
 110         end = rte_rdtsc();
 111         ticks = end - start;
 112
 113         printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
 114                         (unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
 115 }
 116
 117 /*
 118  * Test all hash functions.
 119  */
 120 static void
 121 run_hash_func_perf_tests(void)
 122 {
 123         unsigned i, j, k;
 124
 125         printf(" *** Hash function performance test results ***\n");
 126         printf(" Number of iterations for each test = %d\n",
 127                         HASHTEST_ITERATIONS);
 128         printf("Hash Func.  , Key Length (bytes), Initial value, Ticks/Op.\n");
 129
 130         for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
 131                 for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
 132                         for (k = 0; k < RTE_DIM(hashtest_funcs); k++) {
 133                                 run_hash_func_perf_test(hashtest_key_lens[j],
 134                                                 hashtest_initvals[i],
 135                                                 hashtest_funcs[k]);
 136                         }
 137                 }
 138         }
 139 }
 140
 141 /*
 142  * Verify that hash functions return what they are expected to return
 143  * (using precalculated values stored above)
 144  */
 145 static int
 146 verify_precalculated_hash_func_tests(void)
 147 {
 148         unsigned i, j;
 149         uint8_t key[64];
 150         uint32_t hash;
 151
 152         for (i = 0; i < 64; i++)
 153                 key[i] = (uint8_t) i;
 154
 155         for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
 156                 for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
 157                         hash = rte_jhash(key, hashtest_key_lens[i],
 158                                         hashtest_initvals[j]);
 159                         if (hash != hash_values_jhash[j][i]) {
 160                                 printf("jhash for %u bytes with initial value 0x%x."
 161                                        "Expected 0x%x, but got 0x%x\n",
 162                                        hashtest_key_lens[i], hashtest_initvals[j],
 163                                        hash_values_jhash[j][i], hash);
 164                                 return -1;
 165                         }
 166
 167                         hash = rte_hash_crc(key, hashtest_key_lens[i],
 168                                         hashtest_initvals[j]);
 169                         if (hash != hash_values_crc[j][i]) {
 170                                 printf("CRC for %u bytes with initial value 0x%x."
 171                                        "Expected 0x%x, but got 0x%x\n",
 172                                        hashtest_key_lens[i], hashtest_initvals[j],
 173                                        hash_values_crc[j][i], hash);
 174                                 return -1;
 175                         }
 176                 }
 177         }
 178
 179         return 0;
 180 }
 181
 182 /*
 183  * Verify that rte_jhash and rte_jhash_32b return the same
 184  */
 185 static int
 186 verify_jhash_32bits(void)
 187 {
 188         unsigned i, j;
 189         uint8_t key[64];
 190         uint32_t hash, hash32;
 191
 192         for (i = 0; i < 64; i++)
 193                 key[i] = rand() & 0xff;
 194
 195         for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
 196                 for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
 197                         /* Key size must be multiple of 4 (32 bits) */
 198                         if ((hashtest_key_lens[i] & 0x3) == 0) {
 199                                 hash = rte_jhash(key, hashtest_key_lens[i],
 200                                                 hashtest_initvals[j]);
 201                                 /* Divide key length by 4 in rte_jhash for 32 bits */
 202                                 hash32 = rte_jhash_32b((const unaligned_uint32_t *)key,
 203                                                 hashtest_key_lens[i] >> 2,
 204                                                 hashtest_initvals[j]);
 205                                 if (hash != hash32) {
 206                                         printf("rte_jhash returns different value (0x%x)"
 207                                                "than rte_jhash_32b (0x%x)\n",
 208                                                hash, hash32);
 209                                         return -1;
 210                                 }
 211                         }
 212                 }
 213         }
 214
 215         return 0;
 216 }
 217
 218 /*
 219  * Verify that rte_jhash and rte_jhash_1word, rte_jhash_2words
 220  * and rte_jhash_3words return the same
 221  */
 222 static int
 223 verify_jhash_words(void)
 224 {
 225         unsigned i;
 226         uint32_t key[3];
 227         uint32_t hash, hash_words;
 228
 229         for (i = 0; i < 3; i++)
 230                 key[i] = rand();
 231
 232         /* Test rte_jhash_1word */
 233         hash = rte_jhash(key, 4, 0);
 234         hash_words = rte_jhash_1word(key[0], 0);
 235         if (hash != hash_words) {
 236                 printf("rte_jhash returns different value (0x%x)"
 237                        "than rte_jhash_1word (0x%x)\n",
 238                        hash, hash_words);
 239                 return -1;
 240         }
 241         /* Test rte_jhash_2words */
 242         hash = rte_jhash(key, 8, 0);
 243         hash_words = rte_jhash_2words(key[0], key[1], 0);
 244         if (hash != hash_words) {
 245                 printf("rte_jhash returns different value (0x%x)"
 246                        "than rte_jhash_2words (0x%x)\n",
 247                        hash, hash_words);
 248                 return -1;
 249         }
 250         /* Test rte_jhash_3words */
 251         hash = rte_jhash(key, 12, 0);
 252         hash_words = rte_jhash_3words(key[0], key[1], key[2], 0);
 253         if (hash != hash_words) {
 254                 printf("rte_jhash returns different value (0x%x)"
 255                        "than rte_jhash_3words (0x%x)\n",
 256                        hash, hash_words);
 257                 return -1;
 258         }
 259
 260         return 0;
 261 }
 262
 263 /*
 264  * Run all functional tests for hash functions
 265  */
 266 static int
 267 run_hash_func_tests(void)
 268 {
 269         if (verify_precalculated_hash_func_tests() != 0)
 270                 return -1;
 271
 272         if (verify_jhash_32bits() != 0)
 273                 return -1;
 274
 275         if (verify_jhash_words() != 0)
 276                 return -1;
 277
 278         return 0;
 279
 280 }
 281
 282 static int
 283 test_hash_functions(void)
 284 {
 285         if (run_hash_func_tests() != 0)
 286                 return -1;
 287
 288         run_hash_func_perf_tests();
 289
 290         return 0;
 291 }
 292
 293 REGISTER_TEST_COMMAND(hash_functions_autotest, test_hash_functions);