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); 323