app/test/test_hash_functions.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <stdio.h>
  35 #include <stdint.h>
  36 #include <string.h>
  37 #include <stdlib.h>
  38 #include <stdarg.h>
  39 #include <errno.h>
  40 #include <sys/queue.h>
  41
  42 #include <rte_cycles.h>
  43 #include <rte_random.h>
  44 #include <rte_hash.h>
  45 #include <rte_jhash.h>
  46 #include <rte_hash_crc.h>
  47
  48 #include "test.h"
  49
  50 /*
  51  * Hash values calculated for key sizes from array "hashtest_key_lens"
  52  * and for initial values from array "hashtest_initvals.
  53  * Each key will be formed by increasing each byte by 1:
  54  * e.g.: key size = 4, key = 0x03020100
  55  *       key size = 8, key = 0x0706050403020100
  56  */
  57 static uint32_t hash_values_jhash[2][12] = {{
  58         0x8ba9414b, 0xdf0d39c9,
  59         0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
  60         0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
  61         0x12926a31, 0x1c9fa888
  62 },
  63 {
  64         0x5c62c303, 0x1b8cf784,
  65         0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
  66         0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
  67         0x91d0e462, 0x768087fc
  68 }
  69 };
  70 static uint32_t hash_values_crc[2][12] = {{
  71         0x00000000, 0xf26b8303,
  72         0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
  73         0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
  74         0x43f44466, 0x4a11475e
  75 },
  76 {
  77         0xbdfd3980, 0x70204542,
  78         0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
  79         0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
  80         0x789c104f, 0x53028d3e
  81 }
  82 };
  83
  84 /*******************************************************************************
  85  * Hash function performance test configuration section. Each performance test
  86  * will be performed HASHTEST_ITERATIONS times.
  87  *
  88  * The three arrays below control what tests are performed. Every combination
  89  * from the array entries is tested.
  90  */
  91 #define HASHTEST_ITERATIONS 1000000
  92 #define MAX_KEYSIZE 64
  93 static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
  94 static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
  95 static uint32_t hashtest_key_lens[] = {
  96         1, 2,                 /* Unusual key sizes */
  97         4, 8, 16, 32, 48, 64, /* standard key sizes */
  98         9,                    /* IPv4 SRC + DST + protocol, unpadded */
  99         13,                   /* IPv4 5-tuple, unpadded */
 100         37,                   /* IPv6 5-tuple, unpadded */
 101         40                    /* IPv6 5-tuple, padded to 8-byte boundary */
 102 };
 103 /******************************************************************************/
 104
 105 /*
 106  * To help print out name of hash functions.
 107  */
 108 static const char *
 109 get_hash_name(rte_hash_function f)
 110 {
 111         if (f == rte_jhash)
 112                 return "jhash";
 113
 114         if (f == rte_hash_crc)
 115                 return "rte_hash_crc";
 116
 117         return "UnknownHash";
 118 }
 119
 120 /*
 121  * Test a hash function.
 122  */
 123 static void
 124 run_hash_func_perf_test(uint32_t key_len, uint32_t init_val,
 125                 rte_hash_function f)
 126 {
 127         static uint8_t key[HASHTEST_ITERATIONS][MAX_KEYSIZE];
 128         uint64_t ticks, start, end;
 129         unsigned i, j;
 130
 131         for (i = 0; i < HASHTEST_ITERATIONS; i++) {
 132                 for (j = 0; j < key_len; j++)
 133                         key[i][j] = (uint8_t) rte_rand();
 134         }
 135
 136         start = rte_rdtsc();
 137         for (i = 0; i < HASHTEST_ITERATIONS; i++)
 138                 f(key[i], key_len, init_val);
 139         end = rte_rdtsc();
 140         ticks = end - start;
 141
 142         printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
 143                         (unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
 144 }
 145
 146 /*
 147  * Test all hash functions.
 148  */
 149 static void
 150 run_hash_func_perf_tests(void)
 151 {
 152         unsigned i, j, k;
 153
 154         printf(" *** Hash function performance test results ***\n");
 155         printf(" Number of iterations for each test = %d\n",
 156                         HASHTEST_ITERATIONS);
 157         printf("Hash Func.  , Key Length (bytes), Initial value, Ticks/Op.\n");
 158
 159         for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
 160                 for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
 161                         for (k = 0; k < RTE_DIM(hashtest_funcs); k++) {
 162                                 run_hash_func_perf_test(hashtest_key_lens[j],
 163                                                 hashtest_initvals[i],
 164                                                 hashtest_funcs[k]);
 165                         }
 166                 }
 167         }
 168 }
 169
 170 /*
 171  * Verify that hash functions return what they are expected to return
 172  * (using precalculated values stored above)
 173  */
 174 static int
 175 verify_precalculated_hash_func_tests(void)
 176 {
 177         unsigned i, j;
 178         uint8_t key[64];
 179         uint32_t hash;
 180
 181         for (i = 0; i < 64; i++)
 182                 key[i] = (uint8_t) i;
 183
 184         for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
 185                 for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
 186                         hash = rte_jhash(key, hashtest_key_lens[i],
 187                                         hashtest_initvals[j]);
 188                         if (hash != hash_values_jhash[j][i]) {
 189                                 printf("jhash for %u bytes with initial value 0x%x."
 190                                        "Expected 0x%x, but got 0x%x\n",
 191                                        hashtest_key_lens[i], hashtest_initvals[j],
 192                                        hash_values_jhash[j][i], hash);
 193                                 return -1;
 194                         }
 195
 196                         hash = rte_hash_crc(key, hashtest_key_lens[i],
 197                                         hashtest_initvals[j]);
 198                         if (hash != hash_values_crc[j][i]) {
 199                                 printf("CRC for %u bytes with initial value 0x%x."
 200                                        "Expected 0x%x, but got 0x%x\n",
 201                                        hashtest_key_lens[i], hashtest_initvals[j],
 202                                        hash_values_crc[j][i], hash);
 203                                 return -1;
 204                         }
 205                 }
 206         }
 207
 208         return 0;
 209 }
 210
 211 /*
 212  * Verify that rte_jhash and rte_jhash_32b return the same
 213  */
 214 static int
 215 verify_jhash_32bits(void)
 216 {
 217         unsigned i, j;
 218         uint8_t key[64];
 219         uint32_t hash, hash32;
 220
 221         for (i = 0; i < 64; i++)
 222                 key[i] = rand() & 0xff;
 223
 224         for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
 225                 for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
 226                         /* Key size must be multiple of 4 (32 bits) */
 227                         if ((hashtest_key_lens[i] & 0x3) == 0) {
 228                                 hash = rte_jhash(key, hashtest_key_lens[i],
 229                                                 hashtest_initvals[j]);
 230                                 /* Divide key length by 4 in rte_jhash for 32 bits */
 231                                 hash32 = rte_jhash_32b((const unaligned_uint32_t *)key,
 232                                                 hashtest_key_lens[i] >> 2,
 233                                                 hashtest_initvals[j]);
 234                                 if (hash != hash32) {
 235                                         printf("rte_jhash returns different value (0x%x)"
 236                                                "than rte_jhash_32b (0x%x)\n",
 237                                                hash, hash32);
 238                                         return -1;
 239                                 }
 240                         }
 241                 }
 242         }
 243
 244         return 0;
 245 }
 246
 247 /*
 248  * Verify that rte_jhash and rte_jhash_1word, rte_jhash_2words
 249  * and rte_jhash_3words return the same
 250  */
 251 static int
 252 verify_jhash_words(void)
 253 {
 254         unsigned i;
 255         uint32_t key[3];
 256         uint32_t hash, hash_words;
 257
 258         for (i = 0; i < 3; i++)
 259                 key[i] = rand();
 260
 261         /* Test rte_jhash_1word */
 262         hash = rte_jhash(key, 4, 0);
 263         hash_words = rte_jhash_1word(key[0], 0);
 264         if (hash != hash_words) {
 265                 printf("rte_jhash returns different value (0x%x)"
 266                        "than rte_jhash_1word (0x%x)\n",
 267                        hash, hash_words);
 268                 return -1;
 269         }
 270         /* Test rte_jhash_2words */
 271         hash = rte_jhash(key, 8, 0);
 272         hash_words = rte_jhash_2words(key[0], key[1], 0);
 273         if (hash != hash_words) {
 274                 printf("rte_jhash returns different value (0x%x)"
 275                        "than rte_jhash_2words (0x%x)\n",
 276                        hash, hash_words);
 277                 return -1;
 278         }
 279         /* Test rte_jhash_3words */
 280         hash = rte_jhash(key, 12, 0);
 281         hash_words = rte_jhash_3words(key[0], key[1], key[2], 0);
 282         if (hash != hash_words) {
 283                 printf("rte_jhash returns different value (0x%x)"
 284                        "than rte_jhash_3words (0x%x)\n",
 285                        hash, hash_words);
 286                 return -1;
 287         }
 288
 289         return 0;
 290 }
 291
 292 /*
 293  * Run all functional tests for hash functions
 294  */
 295 static int
 296 run_hash_func_tests(void)
 297 {
 298         if (verify_precalculated_hash_func_tests() != 0)
 299                 return -1;
 300
 301         if (verify_jhash_32bits() != 0)
 302                 return -1;
 303
 304         if (verify_jhash_words() != 0)
 305                 return -1;
 306
 307         return 0;
 308
 309 }
 310
 311 static int
 312 test_hash_functions(void)
 313 {
 314         if (run_hash_func_tests() != 0)
 315                 return -1;
 316
 317         run_hash_func_perf_tests();
 318
 319         return 0;
 320 }
 321
 322 REGISTER_TEST_COMMAND(hash_functions_autotest, test_hash_functions);