[ceph.git] / ceph / src / spdk / dpdk / test / test / test_hash_functions.c

/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2010-2015 Intel Corporation
 */

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <sys/queue.h>

#include <rte_cycles.h>
#include <rte_random.h>
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>

#include "test.h"

/*
 * Hash values calculated for key sizes from array "hashtest_key_lens"
 * and for initial values from array "hashtest_initvals.
 * Each key will be formed by increasing each byte by 1:
 * e.g.: key size = 4, key = 0x03020100
 *       key size = 8, key = 0x0706050403020100
 */
static uint32_t hash_values_jhash[2][12] = {{
	0x8ba9414b, 0xdf0d39c9,
	0xe4cf1d42, 0xd4ccb93c, 0x5e84eafc, 0x21362cfe,
	0x2f4775ab, 0x9ff036cc, 0xeca51474, 0xbc9d6816,
	0x12926a31, 0x1c9fa888
},
{
	0x5c62c303, 0x1b8cf784,
	0x8270ac65, 0x05fa6668, 0x762df861, 0xda088f2f,
	0x59614cd4, 0x7a94f690, 0xdc1e4993, 0x30825494,
	0x91d0e462, 0x768087fc
}
};
static uint32_t hash_values_crc[2][12] = {{
	0x00000000, 0xf26b8303,
	0x91545164, 0x06040eb1, 0x9bb99201, 0xcc4c4fe4,
	0x14a90993, 0xf8a5dd8c, 0xcaa1ad0b, 0x7ac1e03e,
	0x43f44466, 0x4a11475e
},
{
	0xbdfd3980, 0x70204542,
	0x98cd4c70, 0xd52c702f, 0x41fc0e1c, 0x3905f65c,
	0x94bff47f, 0x1bab102d, 0xf4a2c645, 0xbf441539,
	0x789c104f, 0x53028d3e
}
};

/*******************************************************************************
 * Hash function performance test configuration section. Each performance test
 * will be performed HASHTEST_ITERATIONS times.
 *
 * The three arrays below control what tests are performed. Every combination
 * from the array entries is tested.
 */
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
static uint32_t hashtest_key_lens[] = {
	1, 2,                 /* Unusual key sizes */
	4, 8, 16, 32, 48, 64, /* standard key sizes */
	9,                    /* IPv4 SRC + DST + protocol, unpadded */
	13,                   /* IPv4 5-tuple, unpadded */
	37,                   /* IPv6 5-tuple, unpadded */
	40                    /* IPv6 5-tuple, padded to 8-byte boundary */
};
/******************************************************************************/

/*
 * To help print out name of hash functions.
 */
static const char *
get_hash_name(rte_hash_function f)
{
	if (f == rte_jhash)
		return "jhash";

	if (f == rte_hash_crc)
		return "rte_hash_crc";

	return "UnknownHash";
}

/*
 * Test a hash function.
 */
static void
run_hash_func_perf_test(uint32_t key_len, uint32_t init_val,
		rte_hash_function f)
{
	static uint8_t key[HASHTEST_ITERATIONS][MAX_KEYSIZE];
	uint64_t ticks, start, end;
	unsigned i, j;

	for (i = 0; i < HASHTEST_ITERATIONS; i++) {
		for (j = 0; j < key_len; j++)
			key[i][j] = (uint8_t) rte_rand();
	}

	start = rte_rdtsc();
	for (i = 0; i < HASHTEST_ITERATIONS; i++)
		f(key[i], key_len, init_val);
	end = rte_rdtsc();
	ticks = end - start;

	printf("%-12s, %-18u, %-13u, %.02f\n", get_hash_name(f), (unsigned) key_len,
			(unsigned) init_val, (double)ticks / HASHTEST_ITERATIONS);
}

/*
 * Test all hash functions.
 */
static void
run_hash_func_perf_tests(void)
{
	unsigned i, j, k;

	printf(" *** Hash function performance test results ***\n");
	printf(" Number of iterations for each test = %d\n",
			HASHTEST_ITERATIONS);
	printf("Hash Func.  , Key Length (bytes), Initial value, Ticks/Op.\n");

	for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
		for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
			for (k = 0; k < RTE_DIM(hashtest_funcs); k++) {
				run_hash_func_perf_test(hashtest_key_lens[j],
						hashtest_initvals[i],
						hashtest_funcs[k]);
			}
		}
	}
}

/*
 * Verify that hash functions return what they are expected to return
 * (using precalculated values stored above)
 */
static int
verify_precalculated_hash_func_tests(void)
{
	unsigned i, j;
	uint8_t key[64];
	uint32_t hash;

	for (i = 0; i < 64; i++)
		key[i] = (uint8_t) i;

	for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
		for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
			hash = rte_jhash(key, hashtest_key_lens[i],
					hashtest_initvals[j]);
			if (hash != hash_values_jhash[j][i]) {
				printf("jhash for %u bytes with initial value 0x%x."
				       "Expected 0x%x, but got 0x%x\n",
				       hashtest_key_lens[i], hashtest_initvals[j],
				       hash_values_jhash[j][i], hash);
				return -1;
			}

			hash = rte_hash_crc(key, hashtest_key_lens[i],
					hashtest_initvals[j]);
			if (hash != hash_values_crc[j][i]) {
				printf("CRC for %u bytes with initial value 0x%x."
				       "Expected 0x%x, but got 0x%x\n",
				       hashtest_key_lens[i], hashtest_initvals[j],
				       hash_values_crc[j][i], hash);
				return -1;
			}
		}
	}

	return 0;
}

/*
 * Verify that rte_jhash and rte_jhash_32b return the same
 */
static int
verify_jhash_32bits(void)
{
	unsigned i, j;
	uint8_t key[64];
	uint32_t hash, hash32;

	for (i = 0; i < 64; i++)
		key[i] = rand() & 0xff;

	for (i = 0; i < sizeof(hashtest_key_lens) / sizeof(uint32_t); i++) {
		for (j = 0; j < sizeof(hashtest_initvals) / sizeof(uint32_t); j++) {
			/* Key size must be multiple of 4 (32 bits) */
			if ((hashtest_key_lens[i] & 0x3) == 0) {
				hash = rte_jhash(key, hashtest_key_lens[i],
						hashtest_initvals[j]);
				/* Divide key length by 4 in rte_jhash for 32 bits */
				hash32 = rte_jhash_32b((const unaligned_uint32_t *)key,
						hashtest_key_lens[i] >> 2,
						hashtest_initvals[j]);
				if (hash != hash32) {
					printf("rte_jhash returns different value (0x%x)"
					       "than rte_jhash_32b (0x%x)\n",
					       hash, hash32);
					return -1;
				}
			}
		}
	}

	return 0;
}

/*
 * Verify that rte_jhash and rte_jhash_1word, rte_jhash_2words
 * and rte_jhash_3words return the same
 */
static int
verify_jhash_words(void)
{
	unsigned i;
	uint32_t key[3];
	uint32_t hash, hash_words;

	for (i = 0; i < 3; i++)
		key[i] = rand();

	/* Test rte_jhash_1word */
	hash = rte_jhash(key, 4, 0);
	hash_words = rte_jhash_1word(key[0], 0);
	if (hash != hash_words) {
		printf("rte_jhash returns different value (0x%x)"
		       "than rte_jhash_1word (0x%x)\n",
		       hash, hash_words);
		return -1;
	}
	/* Test rte_jhash_2words */
	hash = rte_jhash(key, 8, 0);
	hash_words = rte_jhash_2words(key[0], key[1], 0);
	if (hash != hash_words) {
		printf("rte_jhash returns different value (0x%x)"
		       "than rte_jhash_2words (0x%x)\n",
		       hash, hash_words);
		return -1;
	}
	/* Test rte_jhash_3words */
	hash = rte_jhash(key, 12, 0);
	hash_words = rte_jhash_3words(key[0], key[1], key[2], 0);
	if (hash != hash_words) {
		printf("rte_jhash returns different value (0x%x)"
		       "than rte_jhash_3words (0x%x)\n",
		       hash, hash_words);
		return -1;
	}

	return 0;
}

/*
 * Run all functional tests for hash functions
 */
static int
run_hash_func_tests(void)
{
	if (verify_precalculated_hash_func_tests() != 0)
		return -1;

	if (verify_jhash_32bits() != 0)
		return -1;

	if (verify_jhash_words() != 0)
		return -1;

	return 0;

}

static int
test_hash_functions(void)
{
	if (run_hash_func_tests() != 0)
		return -1;

	run_hash_func_perf_tests();

	return 0;
}

REGISTER_TEST_COMMAND(hash_functions_autotest, test_hash_functions);
Commit	Line	Data
11fdf7f2 TL	1	/* SPDX-License-Identifier: BSD-3-Clause
11fdf7f2 TL	2	* Copyright(c) 2010-2015 Intel Corporation
7c673cae FG	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);