197f17497SC.J. Collier/*-
297f17497SC.J. Collier *   BSD LICENSE
397f17497SC.J. Collier *
497f17497SC.J. Collier *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
597f17497SC.J. Collier *   All rights reserved.
697f17497SC.J. Collier *
797f17497SC.J. Collier *   Redistribution and use in source and binary forms, with or without
897f17497SC.J. Collier *   modification, are permitted provided that the following conditions
997f17497SC.J. Collier *   are met:
1097f17497SC.J. Collier *
1197f17497SC.J. Collier *     * Redistributions of source code must retain the above copyright
1297f17497SC.J. Collier *       notice, this list of conditions and the following disclaimer.
1397f17497SC.J. Collier *     * Redistributions in binary form must reproduce the above copyright
1497f17497SC.J. Collier *       notice, this list of conditions and the following disclaimer in
1597f17497SC.J. Collier *       the documentation and/or other materials provided with the
1697f17497SC.J. Collier *       distribution.
1797f17497SC.J. Collier *     * Neither the name of Intel Corporation nor the names of its
1897f17497SC.J. Collier *       contributors may be used to endorse or promote products derived
1997f17497SC.J. Collier *       from this software without specific prior written permission.
2097f17497SC.J. Collier *
2197f17497SC.J. Collier *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2297f17497SC.J. Collier *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2397f17497SC.J. Collier *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2497f17497SC.J. Collier *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2597f17497SC.J. Collier *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2697f17497SC.J. Collier *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2797f17497SC.J. Collier *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2897f17497SC.J. Collier *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2997f17497SC.J. Collier *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3097f17497SC.J. Collier *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3197f17497SC.J. Collier *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3297f17497SC.J. Collier */
3397f17497SC.J. Collier
3497f17497SC.J. Collier#include <stdio.h>
3597f17497SC.J. Collier#include <inttypes.h>
3697f17497SC.J. Collier
3797f17497SC.J. Collier#include <rte_lcore.h>
3897f17497SC.J. Collier#include <rte_cycles.h>
3997f17497SC.J. Collier#include <rte_malloc.h>
4097f17497SC.J. Collier#include <rte_hash.h>
4197f17497SC.J. Collier#include <rte_hash_crc.h>
4297f17497SC.J. Collier#include <rte_jhash.h>
4397f17497SC.J. Collier#include <rte_fbk_hash.h>
4497f17497SC.J. Collier#include <rte_random.h>
4597f17497SC.J. Collier#include <rte_string_fns.h>
4697f17497SC.J. Collier
4797f17497SC.J. Collier#include "test.h"
4897f17497SC.J. Collier
4997f17497SC.J. Collier#define MAX_ENTRIES (1 << 19)
5097f17497SC.J. Collier#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */
5197f17497SC.J. Collier#define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
52f7a9461eSLuca Boccassi/* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */
53f7a9461eSLuca Boccassi#define BUCKET_SIZE 8
5497f17497SC.J. Collier#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
5597f17497SC.J. Collier#define MAX_KEYSIZE 64
5697f17497SC.J. Collier#define NUM_KEYSIZES 10
5797f17497SC.J. Collier#define NUM_SHUFFLES 10
5897f17497SC.J. Collier#define BURST_SIZE 16
5997f17497SC.J. Collier
6097f17497SC.J. Collierenum operations {
6197f17497SC.J. Collier	ADD = 0,
6297f17497SC.J. Collier	LOOKUP,
6397f17497SC.J. Collier	LOOKUP_MULTI,
6497f17497SC.J. Collier	DELETE,
6597f17497SC.J. Collier	NUM_OPERATIONS
6697f17497SC.J. Collier};
6797f17497SC.J. Collier
6897f17497SC.J. Collierstatic uint32_t hashtest_key_lens[] = {
6997f17497SC.J. Collier	/* standard key sizes */
7097f17497SC.J. Collier	4, 8, 16, 32, 48, 64,
7197f17497SC.J. Collier	/* IPv4 SRC + DST + protocol, unpadded */
7297f17497SC.J. Collier	9,
7397f17497SC.J. Collier	/* IPv4 5-tuple, unpadded */
7497f17497SC.J. Collier	13,
7597f17497SC.J. Collier	/* IPv6 5-tuple, unpadded */
7697f17497SC.J. Collier	37,
7797f17497SC.J. Collier	/* IPv6 5-tuple, padded to 8-byte boundary */
7897f17497SC.J. Collier	40
7997f17497SC.J. Collier};
8097f17497SC.J. Collier
8197f17497SC.J. Collierstruct rte_hash *h[NUM_KEYSIZES];
8297f17497SC.J. Collier
8397f17497SC.J. Collier/* Array that stores if a slot is full */
8497f17497SC.J. Collieruint8_t slot_taken[MAX_ENTRIES];
8597f17497SC.J. Collier
8697f17497SC.J. Collier/* Array to store number of cycles per operation */
8797f17497SC.J. Collieruint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
8897f17497SC.J. Collier
8997f17497SC.J. Collier/* Array to store all input keys */
9097f17497SC.J. Collieruint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
9197f17497SC.J. Collier
9297f17497SC.J. Collier/* Array to store the precomputed hash for 'keys' */
9397f17497SC.J. Collierhash_sig_t signatures[KEYS_TO_ADD];
9497f17497SC.J. Collier
9597f17497SC.J. Collier/* Array to store how many busy entries have each bucket */
9697f17497SC.J. Collieruint8_t buckets[NUM_BUCKETS];
9797f17497SC.J. Collier
9897f17497SC.J. Collier/* Array to store the positions where keys are added */
9997f17497SC.J. Collierint32_t positions[KEYS_TO_ADD];
10097f17497SC.J. Collier
10197f17497SC.J. Collier/* Parameters used for hash table in unit test functions. */
10297f17497SC.J. Collierstatic struct rte_hash_parameters ut_params = {
10397f17497SC.J. Collier	.entries = MAX_ENTRIES,
10497f17497SC.J. Collier	.hash_func = rte_jhash,
10597f17497SC.J. Collier	.hash_func_init_val = 0,
10697f17497SC.J. Collier};
10797f17497SC.J. Collier
10897f17497SC.J. Collierstatic int
10997f17497SC.J. Colliercreate_table(unsigned with_data, unsigned table_index)
11097f17497SC.J. Collier{
11197f17497SC.J. Collier	char name[RTE_HASH_NAMESIZE];
11297f17497SC.J. Collier
11397f17497SC.J. Collier	if (with_data)
11497f17497SC.J. Collier		/* Table will store 8-byte data */
11597f17497SC.J. Collier		sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]);
11697f17497SC.J. Collier	else
11797f17497SC.J. Collier		sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
11897f17497SC.J. Collier
11997f17497SC.J. Collier	ut_params.name = name;
12097f17497SC.J. Collier	ut_params.key_len = hashtest_key_lens[table_index];
12197f17497SC.J. Collier	ut_params.socket_id = rte_socket_id();
12297f17497SC.J. Collier	h[table_index] = rte_hash_find_existing(name);
12397f17497SC.J. Collier	if (h[table_index] != NULL)
12497f17497SC.J. Collier		/*
12597f17497SC.J. Collier		 * If table was already created, free it to create it again,
12697f17497SC.J. Collier		 * so we force it is empty
12797f17497SC.J. Collier		 */
12897f17497SC.J. Collier		rte_hash_free(h[table_index]);
12997f17497SC.J. Collier	h[table_index] = rte_hash_create(&ut_params);
13097f17497SC.J. Collier	if (h[table_index] == NULL) {
13197f17497SC.J. Collier		printf("Error creating table\n");
13297f17497SC.J. Collier		return -1;
13397f17497SC.J. Collier	}
13497f17497SC.J. Collier	return 0;
13597f17497SC.J. Collier
13697f17497SC.J. Collier}
13797f17497SC.J. Collier
13897f17497SC.J. Collier/* Shuffle the keys that have been added, so lookups will be totally random */
13997f17497SC.J. Collierstatic void
14097f17497SC.J. Colliershuffle_input_keys(unsigned table_index)
14197f17497SC.J. Collier{
14297f17497SC.J. Collier	unsigned i;
14397f17497SC.J. Collier	uint32_t swap_idx;
14497f17497SC.J. Collier	uint8_t temp_key[MAX_KEYSIZE];
14597f17497SC.J. Collier	hash_sig_t temp_signature;
14697f17497SC.J. Collier	int32_t temp_position;
14797f17497SC.J. Collier
14897f17497SC.J. Collier	for (i = KEYS_TO_ADD - 1; i > 0; i--) {
14997f17497SC.J. Collier		swap_idx = rte_rand() % i;
15097f17497SC.J. Collier
15197f17497SC.J. Collier		memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
15297f17497SC.J. Collier		temp_signature = signatures[i];
15397f17497SC.J. Collier		temp_position = positions[i];
15497f17497SC.J. Collier
15597f17497SC.J. Collier		memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
15697f17497SC.J. Collier		signatures[i] = signatures[swap_idx];
15797f17497SC.J. Collier		positions[i] = positions[swap_idx];
15897f17497SC.J. Collier
15997f17497SC.J. Collier		memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
16097f17497SC.J. Collier		signatures[swap_idx] = temp_signature;
16197f17497SC.J. Collier		positions[swap_idx] = temp_position;
16297f17497SC.J. Collier	}
16397f17497SC.J. Collier}
16497f17497SC.J. Collier
16597f17497SC.J. Collier/*
16697f17497SC.J. Collier * Looks for random keys which
16797f17497SC.J. Collier * ALL can fit in hash table (no errors)
16897f17497SC.J. Collier */
16997f17497SC.J. Collierstatic int
17097f17497SC.J. Collierget_input_keys(unsigned with_pushes, unsigned table_index)
17197f17497SC.J. Collier{
17297f17497SC.J. Collier	unsigned i, j;
17397f17497SC.J. Collier	unsigned bucket_idx, incr, success = 1;
17497f17497SC.J. Collier	uint8_t k = 0;
17597f17497SC.J. Collier	int32_t ret;
17697f17497SC.J. Collier	const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
17797f17497SC.J. Collier
17897f17497SC.J. Collier	/* Reset all arrays */
17997f17497SC.J. Collier	for (i = 0; i < MAX_ENTRIES; i++)
18097f17497SC.J. Collier		slot_taken[i] = 0;
18197f17497SC.J. Collier
18297f17497SC.J. Collier	for (i = 0; i < NUM_BUCKETS; i++)
18397f17497SC.J. Collier		buckets[i] = 0;
18497f17497SC.J. Collier
18597f17497SC.J. Collier	for (j = 0; j < hashtest_key_lens[table_index]; j++)
18697f17497SC.J. Collier		keys[0][j] = 0;
18797f17497SC.J. Collier
18897f17497SC.J. Collier	/*
18997f17497SC.J. Collier	 * Add only entries that are not duplicated and that fits in the table
19097f17497SC.J. Collier	 * (cannot store more than BUCKET_SIZE entries in a bucket).
19197f17497SC.J. Collier	 * Regardless a key has been added correctly or not (success),
19297f17497SC.J. Collier	 * the next one to try will be increased by 1.
19397f17497SC.J. Collier	 */
19497f17497SC.J. Collier	for (i = 0; i < KEYS_TO_ADD;) {
19597f17497SC.J. Collier		incr = 0;
19697f17497SC.J. Collier		if (i != 0) {
19797f17497SC.J. Collier			keys[i][0] = ++k;
19897f17497SC.J. Collier			/* Overflow, need to increment the next byte */
19997f17497SC.J. Collier			if (keys[i][0] == 0)
20097f17497SC.J. Collier				incr = 1;
20197f17497SC.J. Collier			for (j = 1; j < hashtest_key_lens[table_index]; j++) {
20297f17497SC.J. Collier				/* Do not increase next byte */
20397f17497SC.J. Collier				if (incr == 0)
20497f17497SC.J. Collier					if (success == 1)
20597f17497SC.J. Collier						keys[i][j] = keys[i - 1][j];
20697f17497SC.J. Collier					else
20797f17497SC.J. Collier						keys[i][j] = keys[i][j];
20897f17497SC.J. Collier				/* Increase next byte by one */
20997f17497SC.J. Collier				else {
21097f17497SC.J. Collier					if (success == 1)
21197f17497SC.J. Collier						keys[i][j] = keys[i-1][j] + 1;
21297f17497SC.J. Collier					else
21397f17497SC.J. Collier						keys[i][j] = keys[i][j] + 1;
21497f17497SC.J. Collier					if (keys[i][j] == 0)
21597f17497SC.J. Collier						incr = 1;
21697f17497SC.J. Collier					else
21797f17497SC.J. Collier						incr = 0;
21897f17497SC.J. Collier				}
21997f17497SC.J. Collier			}
22097f17497SC.J. Collier		}
22197f17497SC.J. Collier		success = 0;
22297f17497SC.J. Collier		signatures[i] = rte_hash_hash(h[table_index], keys[i]);
22397f17497SC.J. Collier		bucket_idx = signatures[i] & bucket_bitmask;
22497f17497SC.J. Collier		/*
22597f17497SC.J. Collier		 * If we are not inserting keys in secondary location,
22697f17497SC.J. Collier		 * when bucket is full, do not try to insert the key
22797f17497SC.J. Collier		 */
22897f17497SC.J. Collier		if (with_pushes == 0)
22997f17497SC.J. Collier			if (buckets[bucket_idx] == BUCKET_SIZE)
23097f17497SC.J. Collier				continue;
23197f17497SC.J. Collier
23297f17497SC.J. Collier		/* If key can be added, leave in successful key arrays "keys" */
23397f17497SC.J. Collier		ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
23497f17497SC.J. Collier						signatures[i]);
23597f17497SC.J. Collier		if (ret >= 0) {
23697f17497SC.J. Collier			/* If key is already added, ignore the entry and do not store */
23797f17497SC.J. Collier			if (slot_taken[ret])
23897f17497SC.J. Collier				continue;
23997f17497SC.J. Collier			else {
24097f17497SC.J. Collier				/* Store the returned position and mark slot as taken */
24197f17497SC.J. Collier				slot_taken[ret] = 1;
24297f17497SC.J. Collier				positions[i] = ret;
24397f17497SC.J. Collier				buckets[bucket_idx]++;
24497f17497SC.J. Collier				success = 1;
24597f17497SC.J. Collier				i++;
24697f17497SC.J. Collier			}
24797f17497SC.J. Collier		}
24897f17497SC.J. Collier	}
24997f17497SC.J. Collier
25097f17497SC.J. Collier	/* Reset the table, so we can measure the time to add all the entries */
25197f17497SC.J. Collier	rte_hash_free(h[table_index]);
25297f17497SC.J. Collier	h[table_index] = rte_hash_create(&ut_params);
25397f17497SC.J. Collier
25497f17497SC.J. Collier	return 0;
25597f17497SC.J. Collier}
25697f17497SC.J. Collier
25797f17497SC.J. Collierstatic int
25897f17497SC.J. Colliertimed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
25997f17497SC.J. Collier{
26097f17497SC.J. Collier	unsigned i;
26197f17497SC.J. Collier	const uint64_t start_tsc = rte_rdtsc();
26297f17497SC.J. Collier	void *data;
26397f17497SC.J. Collier	int32_t ret;
26497f17497SC.J. Collier
26597f17497SC.J. Collier	for (i = 0; i < KEYS_TO_ADD; i++) {
26697f17497SC.J. Collier		data = (void *) ((uintptr_t) signatures[i]);
26797f17497SC.J. Collier		if (with_hash && with_data) {
26897f17497SC.J. Collier			ret = rte_hash_add_key_with_hash_data(h[table_index],
26997f17497SC.J. Collier						(const void *) keys[i],
27097f17497SC.J. Collier						signatures[i], data);
27197f17497SC.J. Collier			if (ret < 0) {
27297f17497SC.J. Collier				printf("Failed to add key number %u\n", ret);
27397f17497SC.J. Collier				return -1;
27497f17497SC.J. Collier			}
27597f17497SC.J. Collier		} else if (with_hash && !with_data) {
27697f17497SC.J. Collier			ret = rte_hash_add_key_with_hash(h[table_index],
27797f17497SC.J. Collier						(const void *) keys[i],
27897f17497SC.J. Collier						signatures[i]);
27997f17497SC.J. Collier			if (ret >= 0)
28097f17497SC.J. Collier				positions[i] = ret;
28197f17497SC.J. Collier			else {
28297f17497SC.J. Collier				printf("Failed to add key number %u\n", ret);
28397f17497SC.J. Collier				return -1;
28497f17497SC.J. Collier			}
28597f17497SC.J. Collier		} else if (!with_hash && with_data) {
28697f17497SC.J. Collier			ret = rte_hash_add_key_data(h[table_index],
28797f17497SC.J. Collier						(const void *) keys[i],
28897f17497SC.J. Collier						data);
28997f17497SC.J. Collier			if (ret < 0) {
29097f17497SC.J. Collier				printf("Failed to add key number %u\n", ret);
29197f17497SC.J. Collier				return -1;
29297f17497SC.J. Collier			}
29397f17497SC.J. Collier		} else {
29497f17497SC.J. Collier			ret = rte_hash_add_key(h[table_index], keys[i]);
29597f17497SC.J. Collier			if (ret >= 0)
29697f17497SC.J. Collier				positions[i] = ret;
29797f17497SC.J. Collier			else {
29897f17497SC.J. Collier				printf("Failed to add key number %u\n", ret);
29997f17497SC.J. Collier				return -1;
30097f17497SC.J. Collier			}
30197f17497SC.J. Collier		}
30297f17497SC.J. Collier	}
30397f17497SC.J. Collier
30497f17497SC.J. Collier	const uint64_t end_tsc = rte_rdtsc();
30597f17497SC.J. Collier	const uint64_t time_taken = end_tsc - start_tsc;
30697f17497SC.J. Collier
30797f17497SC.J. Collier	cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD;
30897f17497SC.J. Collier
30997f17497SC.J. Collier	return 0;
31097f17497SC.J. Collier}
31197f17497SC.J. Collier
31297f17497SC.J. Collierstatic int
31397f17497SC.J. Colliertimed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
31497f17497SC.J. Collier{
31597f17497SC.J. Collier	unsigned i, j;
31697f17497SC.J. Collier	const uint64_t start_tsc = rte_rdtsc();
31797f17497SC.J. Collier	void *ret_data;
31897f17497SC.J. Collier	void *expected_data;
31997f17497SC.J. Collier	int32_t ret;
32097f17497SC.J. Collier
32197f17497SC.J. Collier	for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
32297f17497SC.J. Collier		for (j = 0; j < KEYS_TO_ADD; j++) {
32397f17497SC.J. Collier			if (with_hash && with_data) {
32497f17497SC.J. Collier				ret = rte_hash_lookup_with_hash_data(h[table_index],
32597f17497SC.J. Collier							(const void *) keys[j],
32697f17497SC.J. Collier							signatures[j], &ret_data);
32797f17497SC.J. Collier				if (ret < 0) {
32897f17497SC.J. Collier					printf("Key number %u was not found\n", j);
32997f17497SC.J. Collier					return -1;
33097f17497SC.J. Collier				}
33197f17497SC.J. Collier				expected_data = (void *) ((uintptr_t) signatures[j]);
33297f17497SC.J. Collier				if (ret_data != expected_data) {
33397f17497SC.J. Collier					printf("Data returned for key number %u is %p,"
33497f17497SC.J. Collier					       " but should be %p\n", j, ret_data,
33597f17497SC.J. Collier						expected_data);
33697f17497SC.J. Collier					return -1;
33797f17497SC.J. Collier				}
33897f17497SC.J. Collier			} else if (with_hash && !with_data) {
33997f17497SC.J. Collier				ret = rte_hash_lookup_with_hash(h[table_index],
34097f17497SC.J. Collier							(const void *) keys[j],
34197f17497SC.J. Collier							signatures[j]);
34297f17497SC.J. Collier				if (ret < 0 || ret != positions[j]) {
34397f17497SC.J. Collier					printf("Key looked up in %d, should be in %d\n",
34497f17497SC.J. Collier						ret, positions[j]);
34597f17497SC.J. Collier					return -1;
34697f17497SC.J. Collier				}
34797f17497SC.J. Collier			} else if (!with_hash && with_data) {
34897f17497SC.J. Collier				ret = rte_hash_lookup_data(h[table_index],
34997f17497SC.J. Collier							(const void *) keys[j], &ret_data);
35097f17497SC.J. Collier				if (ret < 0) {
35197f17497SC.J. Collier					printf("Key number %u was not found\n", j);
35297f17497SC.J. Collier					return -1;
35397f17497SC.J. Collier				}
35497f17497SC.J. Collier				expected_data = (void *) ((uintptr_t) signatures[j]);
35597f17497SC.J. Collier				if (ret_data != expected_data) {
35697f17497SC.J. Collier					printf("Data returned for key number %u is %p,"
35797f17497SC.J. Collier					       " but should be %p\n", j, ret_data,
35897f17497SC.J. Collier						expected_data);
35997f17497SC.J. Collier					return -1;
36097f17497SC.J. Collier				}
36197f17497SC.J. Collier			} else {
36297f17497SC.J. Collier				ret = rte_hash_lookup(h[table_index], keys[j]);
36397f17497SC.J. Collier				if (ret < 0 || ret != positions[j]) {
36497f17497SC.J. Collier					printf("Key looked up in %d, should be in %d\n",
36597f17497SC.J. Collier						ret, positions[j]);
36697f17497SC.J. Collier					return -1;
36797f17497SC.J. Collier				}
36897f17497SC.J. Collier			}
36997f17497SC.J. Collier		}
37097f17497SC.J. Collier	}
37197f17497SC.J. Collier
37297f17497SC.J. Collier	const uint64_t end_tsc = rte_rdtsc();
37397f17497SC.J. Collier	const uint64_t time_taken = end_tsc - start_tsc;
37497f17497SC.J. Collier
37597f17497SC.J. Collier	cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS;
37697f17497SC.J. Collier
37797f17497SC.J. Collier	return 0;
37897f17497SC.J. Collier}
37997f17497SC.J. Collier
38097f17497SC.J. Collierstatic int
38197f17497SC.J. Colliertimed_lookups_multi(unsigned with_data, unsigned table_index)
38297f17497SC.J. Collier{
38397f17497SC.J. Collier	unsigned i, j, k;
38497f17497SC.J. Collier	int32_t positions_burst[BURST_SIZE];
38597f17497SC.J. Collier	const void *keys_burst[BURST_SIZE];
38697f17497SC.J. Collier	void *expected_data[BURST_SIZE];
38797f17497SC.J. Collier	void *ret_data[BURST_SIZE];
38897f17497SC.J. Collier	uint64_t hit_mask;
38997f17497SC.J. Collier	int ret;
39097f17497SC.J. Collier
39197f17497SC.J. Collier	const uint64_t start_tsc = rte_rdtsc();
39297f17497SC.J. Collier
39397f17497SC.J. Collier	for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
39497f17497SC.J. Collier		for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
39597f17497SC.J. Collier			for (k = 0; k < BURST_SIZE; k++)
39697f17497SC.J. Collier				keys_burst[k] = keys[j * BURST_SIZE + k];
39797f17497SC.J. Collier			if (with_data) {
39897f17497SC.J. Collier				ret = rte_hash_lookup_bulk_data(h[table_index],
39997f17497SC.J. Collier					(const void **) keys_burst,
40097f17497SC.J. Collier					BURST_SIZE,
40197f17497SC.J. Collier					&hit_mask,
40297f17497SC.J. Collier					ret_data);
40397f17497SC.J. Collier				if (ret != BURST_SIZE) {
40497f17497SC.J. Collier					printf("Expect to find %u keys,"
40597f17497SC.J. Collier					       " but found %d\n", BURST_SIZE, ret);
40697f17497SC.J. Collier					return -1;
40797f17497SC.J. Collier				}
40897f17497SC.J. Collier				for (k = 0; k < BURST_SIZE; k++) {
40997f17497SC.J. Collier					if ((hit_mask & (1ULL << k))  == 0) {
41097f17497SC.J. Collier						printf("Key number %u not found\n",
41197f17497SC.J. Collier							j * BURST_SIZE + k);
41297f17497SC.J. Collier						return -1;
41397f17497SC.J. Collier					}
41497f17497SC.J. Collier					expected_data[k] = (void *) ((uintptr_t) signatures[j * BURST_SIZE + k]);
41597f17497SC.J. Collier					if (ret_data[k] != expected_data[k]) {
41697f17497SC.J. Collier						printf("Data returned for key number %u is %p,"
41797f17497SC.J. Collier						       " but should be %p\n", j * BURST_SIZE + k,
41897f17497SC.J. Collier							ret_data[k], expected_data[k]);
41997f17497SC.J. Collier						return -1;
42097f17497SC.J. Collier					}
42197f17497SC.J. Collier				}
42297f17497SC.J. Collier			} else {
42397f17497SC.J. Collier				rte_hash_lookup_bulk(h[table_index],
42497f17497SC.J. Collier						(const void **) keys_burst,
42597f17497SC.J. Collier						BURST_SIZE,
42697f17497SC.J. Collier						positions_burst);
42797f17497SC.J. Collier				for (k = 0; k < BURST_SIZE; k++) {
42897f17497SC.J. Collier					if (positions_burst[k] != positions[j * BURST_SIZE + k]) {
42997f17497SC.J. Collier						printf("Key looked up in %d, should be in %d\n",
43097f17497SC.J. Collier							positions_burst[k],
43197f17497SC.J. Collier							positions[j * BURST_SIZE + k]);
43297f17497SC.J. Collier						return -1;
43397f17497SC.J. Collier					}
43497f17497SC.J. Collier				}
43597f17497SC.J. Collier			}
43697f17497SC.J. Collier		}
43797f17497SC.J. Collier	}
43897f17497SC.J. Collier
43997f17497SC.J. Collier	const uint64_t end_tsc = rte_rdtsc();
44097f17497SC.J. Collier	const uint64_t time_taken = end_tsc - start_tsc;
44197f17497SC.J. Collier
44297f17497SC.J. Collier	cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS;
44397f17497SC.J. Collier
44497f17497SC.J. Collier	return 0;
44597f17497SC.J. Collier}
44697f17497SC.J. Collier
44797f17497SC.J. Collierstatic int
44897f17497SC.J. Colliertimed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
44997f17497SC.J. Collier{
45097f17497SC.J. Collier	unsigned i;
45197f17497SC.J. Collier	const uint64_t start_tsc = rte_rdtsc();
45297f17497SC.J. Collier	int32_t ret;
45397f17497SC.J. Collier
45497f17497SC.J. Collier	for (i = 0; i < KEYS_TO_ADD; i++) {
45597f17497SC.J. Collier		/* There are no delete functions with data, so just call two functions */
45697f17497SC.J. Collier		if (with_hash)
45797f17497SC.J. Collier			ret = rte_hash_del_key_with_hash(h[table_index],
45897f17497SC.J. Collier							(const void *) keys[i],
45997f17497SC.J. Collier							signatures[i]);
46097f17497SC.J. Collier		else
46197f17497SC.J. Collier			ret = rte_hash_del_key(h[table_index],
46297f17497SC.J. Collier							(const void *) keys[i]);
46397f17497SC.J. Collier		if (ret >= 0)
46497f17497SC.J. Collier			positions[i] = ret;
46597f17497SC.J. Collier		else {
46697f17497SC.J. Collier			printf("Failed to add key number %u\n", ret);
46797f17497SC.J. Collier			return -1;
46897f17497SC.J. Collier		}
46997f17497SC.J. Collier	}
47097f17497SC.J. Collier
47197f17497SC.J. Collier	const uint64_t end_tsc = rte_rdtsc();
47297f17497SC.J. Collier	const uint64_t time_taken = end_tsc - start_tsc;
47397f17497SC.J. Collier
47497f17497SC.J. Collier	cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD;
47597f17497SC.J. Collier
47697f17497SC.J. Collier	return 0;
47797f17497SC.J. Collier}
47897f17497SC.J. Collier
47997f17497SC.J. Collierstatic void
48097f17497SC.J. Collierfree_table(unsigned table_index)
48197f17497SC.J. Collier{
48297f17497SC.J. Collier	rte_hash_free(h[table_index]);
48397f17497SC.J. Collier}
48497f17497SC.J. Collier
48597f17497SC.J. Collierstatic void
48697f17497SC.J. Collierreset_table(unsigned table_index)
48797f17497SC.J. Collier{
48897f17497SC.J. Collier	rte_hash_reset(h[table_index]);
48997f17497SC.J. Collier}
49097f17497SC.J. Collier
49197f17497SC.J. Collierstatic int
49297f17497SC.J. Collierrun_all_tbl_perf_tests(unsigned with_pushes)
49397f17497SC.J. Collier{
49497f17497SC.J. Collier	unsigned i, j, with_data, with_hash;
49597f17497SC.J. Collier
49697f17497SC.J. Collier	printf("Measuring performance, please wait");
49797f17497SC.J. Collier	fflush(stdout);
49897f17497SC.J. Collier
49997f17497SC.J. Collier	for (with_data = 0; with_data <= 1; with_data++) {
50097f17497SC.J. Collier		for (i = 0; i < NUM_KEYSIZES; i++) {
50197f17497SC.J. Collier			if (create_table(with_data, i) < 0)
50297f17497SC.J. Collier				return -1;
50397f17497SC.J. Collier
50497f17497SC.J. Collier			if (get_input_keys(with_pushes, i) < 0)
50597f17497SC.J. Collier				return -1;
50697f17497SC.J. Collier			for (with_hash = 0; with_hash <= 1; with_hash++) {
50797f17497SC.J. Collier				if (timed_adds(with_hash, with_data, i) < 0)
50897f17497SC.J. Collier					return -1;
50997f17497SC.J. Collier
51097f17497SC.J. Collier				for (j = 0; j < NUM_SHUFFLES; j++)
51197f17497SC.J. Collier					shuffle_input_keys(i);
51297f17497SC.J. Collier
51397f17497SC.J. Collier				if (timed_lookups(with_hash, with_data, i) < 0)
51497f17497SC.J. Collier					return -1;
51597f17497SC.J. Collier
51697f17497SC.J. Collier				if (timed_lookups_multi(with_data, i) < 0)
51797f17497SC.J. Collier					return -1;
51897f17497SC.J. Collier
51997f17497SC.J. Collier				if (timed_deletes(with_hash, with_data, i) < 0)
52097f17497SC.J. Collier					return -1;
52197f17497SC.J. Collier
52297f17497SC.J. Collier				/* Print a dot to show progress on operations */
52397f17497SC.J. Collier				printf(".");
52497f17497SC.J. Collier				fflush(stdout);
52597f17497SC.J. Collier
52697f17497SC.J. Collier				reset_table(i);
52797f17497SC.J. Collier			}
52897f17497SC.J. Collier			free_table(i);
52997f17497SC.J. Collier		}
53097f17497SC.J. Collier	}
53197f17497SC.J. Collier
53297f17497SC.J. Collier	printf("\nResults (in CPU cycles/operation)\n");
53397f17497SC.J. Collier	printf("-----------------------------------\n");
53497f17497SC.J. Collier	for (with_data = 0; with_data <= 1; with_data++) {
53597f17497SC.J. Collier		if (with_data)
53697f17497SC.J. Collier			printf("\n Operations with 8-byte data\n");
53797f17497SC.J. Collier		else
53897f17497SC.J. Collier			printf("\n Operations without data\n");
53997f17497SC.J. Collier		for (with_hash = 0; with_hash <= 1; with_hash++) {
54097f17497SC.J. Collier			if (with_hash)
54197f17497SC.J. Collier				printf("\nWith pre-computed hash values\n");
54297f17497SC.J. Collier			else
54397f17497SC.J. Collier				printf("\nWithout pre-computed hash values\n");
54497f17497SC.J. Collier
54597f17497SC.J. Collier			printf("\n%-18s%-18s%-18s%-18s%-18s\n",
54697f17497SC.J. Collier			"Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
54797f17497SC.J. Collier			for (i = 0; i < NUM_KEYSIZES; i++) {
54897f17497SC.J. Collier				printf("%-18d", hashtest_key_lens[i]);
54997f17497SC.J. Collier				for (j = 0; j < NUM_OPERATIONS; j++)
55097f17497SC.J. Collier					printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]);
55197f17497SC.J. Collier				printf("\n");
55297f17497SC.J. Collier			}
55397f17497SC.J. Collier		}
55497f17497SC.J. Collier	}
55597f17497SC.J. Collier	return 0;
55697f17497SC.J. Collier}
55797f17497SC.J. Collier
55897f17497SC.J. Collier/* Control operation of performance testing of fbk hash. */
55997f17497SC.J. Collier#define LOAD_FACTOR 0.667	/* How full to make the hash table. */
56097f17497SC.J. Collier#define TEST_SIZE 1000000	/* How many operations to time. */
56197f17497SC.J. Collier#define TEST_ITERATIONS 30	/* How many measurements to take. */
56297f17497SC.J. Collier#define ENTRIES (1 << 15)	/* How many entries. */
56397f17497SC.J. Collier
56497f17497SC.J. Collierstatic int
56597f17497SC.J. Collierfbk_hash_perf_test(void)
56697f17497SC.J. Collier{
56797f17497SC.J. Collier	struct rte_fbk_hash_params params = {
56897f17497SC.J. Collier		.name = "fbk_hash_test",
56997f17497SC.J. Collier		.entries = ENTRIES,
57097f17497SC.J. Collier		.entries_per_bucket = 4,
57197f17497SC.J. Collier		.socket_id = rte_socket_id(),
57297f17497SC.J. Collier	};
57397f17497SC.J. Collier	struct rte_fbk_hash_table *handle = NULL;
57497f17497SC.J. Collier	uint32_t *keys = NULL;
57597f17497SC.J. Collier	unsigned indexes[TEST_SIZE];
57697f17497SC.J. Collier	uint64_t lookup_time = 0;
57797f17497SC.J. Collier	unsigned added = 0;
57897f17497SC.J. Collier	unsigned value = 0;
57997f17497SC.J. Collier	uint32_t key;
58097f17497SC.J. Collier	uint16_t val;
58197f17497SC.J. Collier	unsigned i, j;
58297f17497SC.J. Collier
58397f17497SC.J. Collier	handle = rte_fbk_hash_create(&params);
58497f17497SC.J. Collier	if (handle == NULL) {
58597f17497SC.J. Collier		printf("Error creating table\n");
58697f17497SC.J. Collier		return -1;
58797f17497SC.J. Collier	}
58897f17497SC.J. Collier
58997f17497SC.J. Collier	keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
59097f17497SC.J. Collier	if (keys == NULL) {
59197f17497SC.J. Collier		printf("fbk hash: memory allocation for key store failed\n");
59297f17497SC.J. Collier		return -1;
59397f17497SC.J. Collier	}
59497f17497SC.J. Collier
59597f17497SC.J. Collier	/* Generate random keys and values. */
59697f17497SC.J. Collier	for (i = 0; i < ENTRIES; i++) {
59797f17497SC.J. Collier		key = (uint32_t)rte_rand();
59897f17497SC.J. Collier		key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
59997f17497SC.J. Collier		val = (uint16_t)rte_rand();
60097f17497SC.J. Collier
60197f17497SC.J. Collier		if (rte_fbk_hash_add_key(handle, key, val) == 0) {
60297f17497SC.J. Collier			keys[added] = key;
60397f17497SC.J. Collier			added++;
60497f17497SC.J. Collier		}
60597f17497SC.J. Collier		if (added > (LOAD_FACTOR * ENTRIES))
60697f17497SC.J. Collier			break;
60797f17497SC.J. Collier	}
60897f17497SC.J. Collier
60997f17497SC.J. Collier	for (i = 0; i < TEST_ITERATIONS; i++) {
61097f17497SC.J. Collier		uint64_t begin;
61197f17497SC.J. Collier		uint64_t end;
61297f17497SC.J. Collier
61397f17497SC.J. Collier		/* Generate random indexes into keys[] array. */
61497f17497SC.J. Collier		for (j = 0; j < TEST_SIZE; j++)
61597f17497SC.J. Collier			indexes[j] = rte_rand() % added;
61697f17497SC.J. Collier
61797f17497SC.J. Collier		begin = rte_rdtsc();
61897f17497SC.J. Collier		/* Do lookups */
61997f17497SC.J. Collier		for (j = 0; j < TEST_SIZE; j++)
62097f17497SC.J. Collier			value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
62197f17497SC.J. Collier
62297f17497SC.J. Collier		end = rte_rdtsc();
62397f17497SC.J. Collier		lookup_time += (double)(end - begin);
62497f17497SC.J. Collier	}
62597f17497SC.J. Collier
62697f17497SC.J. Collier	printf("\n\n *** FBK Hash function performance test results ***\n");
62797f17497SC.J. Collier	/*
62897f17497SC.J. Collier	 * The use of the 'value' variable ensures that the hash lookup is not
62997f17497SC.J. Collier	 * being optimised out by the compiler.
63097f17497SC.J. Collier	 */
63197f17497SC.J. Collier	if (value != 0)
63297f17497SC.J. Collier		printf("Number of ticks per lookup = %g\n",
63397f17497SC.J. Collier			(double)lookup_time /
63497f17497SC.J. Collier			((double)TEST_ITERATIONS * (double)TEST_SIZE));
63597f17497SC.J. Collier
63697f17497SC.J. Collier	rte_fbk_hash_free(handle);
63797f17497SC.J. Collier
63897f17497SC.J. Collier	return 0;
63997f17497SC.J. Collier}
64097f17497SC.J. Collier
64197f17497SC.J. Collierstatic int
64297f17497SC.J. Colliertest_hash_perf(void)
64397f17497SC.J. Collier{
64497f17497SC.J. Collier	unsigned with_pushes;
64597f17497SC.J. Collier
64697f17497SC.J. Collier	for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
64797f17497SC.J. Collier		if (with_pushes == 0)
64897f17497SC.J. Collier			printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
64997f17497SC.J. Collier		else
65097f17497SC.J. Collier			printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
65197f17497SC.J. Collier		if (run_all_tbl_perf_tests(with_pushes) < 0)
65297f17497SC.J. Collier			return -1;
65397f17497SC.J. Collier	}
65497f17497SC.J. Collier	if (fbk_hash_perf_test() < 0)
65597f17497SC.J. Collier		return -1;
65697f17497SC.J. Collier
65797f17497SC.J. Collier	return 0;
65897f17497SC.J. Collier}
65997f17497SC.J. Collier
6605d4e5dcdSRicardo SalvetiREGISTER_TEST_COMMAND(hash_perf_autotest, test_hash_perf);
661