-/*-
- * BSD LICENSE
- *
- * Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- * * Neither the name of Intel Corporation nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2010-2015 Intel Corporation
*/
#include <stdio.h>
#include "test.h"
#define MAX_ENTRIES (1 << 19)
-#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */
+#define KEYS_TO_ADD (MAX_ENTRIES)
+#define ADD_PERCENT 0.75 /* 75% table utilization */
#define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */
-#define BUCKET_SIZE 4
+/* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */
+#define BUCKET_SIZE 8
#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
#define MAX_KEYSIZE 64
#define NUM_KEYSIZES 10
#define BURST_SIZE 16
enum operations {
- ADD = 0,
- LOOKUP,
- LOOKUP_MULTI,
- DELETE,
+ OP_ADD = 0,
+ OP_LOOKUP,
+ OP_LOOKUP_MULTI,
+ OP_DELETE,
NUM_OPERATIONS
};
struct rte_hash *h[NUM_KEYSIZES];
/* Array that stores if a slot is full */
-uint8_t slot_taken[MAX_ENTRIES];
+static uint8_t slot_taken[MAX_ENTRIES];
/* Array to store number of cycles per operation */
-uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
+static uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2];
/* Array to store all input keys */
-uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
+static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
/* Array to store the precomputed hash for 'keys' */
-hash_sig_t signatures[KEYS_TO_ADD];
+static hash_sig_t signatures[KEYS_TO_ADD];
/* Array to store how many busy entries have each bucket */
-uint8_t buckets[NUM_BUCKETS];
+static uint8_t buckets[NUM_BUCKETS];
/* Array to store the positions where keys are added */
-int32_t positions[KEYS_TO_ADD];
+static int32_t positions[KEYS_TO_ADD];
/* Parameters used for hash table in unit test functions. */
static struct rte_hash_parameters ut_params = {
};
static int
-create_table(unsigned with_data, unsigned table_index)
+create_table(unsigned int with_data, unsigned int table_index,
+ unsigned int with_locks, unsigned int ext)
{
char name[RTE_HASH_NAMESIZE];
if (with_data)
/* Table will store 8-byte data */
- sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]);
+ snprintf(name, sizeof(name), "test_hash%u_data",
+ hashtest_key_lens[table_index]);
else
- sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
+ snprintf(name, sizeof(name), "test_hash%u",
+ hashtest_key_lens[table_index]);
+
+
+ if (with_locks)
+ ut_params.extra_flag =
+ RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT
+ | RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY;
+ else
+ ut_params.extra_flag = 0;
+
+ if (ext)
+ ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
ut_params.name = name;
ut_params.key_len = hashtest_key_lens[table_index];
/* Shuffle the keys that have been added, so lookups will be totally random */
static void
-shuffle_input_keys(unsigned table_index)
+shuffle_input_keys(unsigned int table_index, unsigned int ext)
{
unsigned i;
uint32_t swap_idx;
uint8_t temp_key[MAX_KEYSIZE];
hash_sig_t temp_signature;
int32_t temp_position;
+ unsigned int keys_to_add;
+
+ if (!ext)
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ else
+ keys_to_add = KEYS_TO_ADD;
- for (i = KEYS_TO_ADD - 1; i > 0; i--) {
+ for (i = keys_to_add - 1; i > 0; i--) {
swap_idx = rte_rand() % i;
memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
* ALL can fit in hash table (no errors)
*/
static int
-get_input_keys(unsigned with_pushes, unsigned table_index)
+get_input_keys(unsigned int with_pushes, unsigned int table_index,
+ unsigned int ext)
{
unsigned i, j;
unsigned bucket_idx, incr, success = 1;
uint8_t k = 0;
int32_t ret;
const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
+ unsigned int keys_to_add;
+ if (!ext)
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ else
+ keys_to_add = KEYS_TO_ADD;
/* Reset all arrays */
for (i = 0; i < MAX_ENTRIES; i++)
slot_taken[i] = 0;
* Regardless a key has been added correctly or not (success),
* the next one to try will be increased by 1.
*/
- for (i = 0; i < KEYS_TO_ADD;) {
+ for (i = 0; i < keys_to_add;) {
incr = 0;
if (i != 0) {
keys[i][0] = ++k;
}
static int
-timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
+timed_adds(unsigned int with_hash, unsigned int with_data,
+ unsigned int table_index, unsigned int ext)
{
unsigned i;
const uint64_t start_tsc = rte_rdtsc();
void *data;
int32_t ret;
+ unsigned int keys_to_add;
+ if (!ext)
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ else
+ keys_to_add = KEYS_TO_ADD;
- for (i = 0; i < KEYS_TO_ADD; i++) {
+ for (i = 0; i < keys_to_add; i++) {
data = (void *) ((uintptr_t) signatures[i]);
if (with_hash && with_data) {
ret = rte_hash_add_key_with_hash_data(h[table_index],
(const void *) keys[i],
signatures[i], data);
if (ret < 0) {
- printf("Failed to add key number %u\n", ret);
+ printf("H+D: Failed to add key number %u\n", i);
return -1;
}
} else if (with_hash && !with_data) {
if (ret >= 0)
positions[i] = ret;
else {
- printf("Failed to add key number %u\n", ret);
+ printf("H: Failed to add key number %u\n", i);
return -1;
}
} else if (!with_hash && with_data) {
(const void *) keys[i],
data);
if (ret < 0) {
- printf("Failed to add key number %u\n", ret);
+ printf("D: Failed to add key number %u\n", i);
return -1;
}
} else {
if (ret >= 0)
positions[i] = ret;
else {
- printf("Failed to add key number %u\n", ret);
+ printf("Failed to add key number %u\n", i);
return -1;
}
}
const uint64_t end_tsc = rte_rdtsc();
const uint64_t time_taken = end_tsc - start_tsc;
- cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD;
+ cycles[table_index][OP_ADD][with_hash][with_data] = time_taken/keys_to_add;
return 0;
}
static int
-timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
+timed_lookups(unsigned int with_hash, unsigned int with_data,
+ unsigned int table_index, unsigned int ext)
{
unsigned i, j;
const uint64_t start_tsc = rte_rdtsc();
void *ret_data;
void *expected_data;
int32_t ret;
-
- for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
- for (j = 0; j < KEYS_TO_ADD; j++) {
+ unsigned int keys_to_add, num_lookups;
+
+ if (!ext) {
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ num_lookups = NUM_LOOKUPS * ADD_PERCENT;
+ } else {
+ keys_to_add = KEYS_TO_ADD;
+ num_lookups = NUM_LOOKUPS;
+ }
+ for (i = 0; i < num_lookups / keys_to_add; i++) {
+ for (j = 0; j < keys_to_add; j++) {
if (with_hash && with_data) {
ret = rte_hash_lookup_with_hash_data(h[table_index],
(const void *) keys[j],
const uint64_t end_tsc = rte_rdtsc();
const uint64_t time_taken = end_tsc - start_tsc;
- cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS;
+ cycles[table_index][OP_LOOKUP][with_hash][with_data] = time_taken/num_lookups;
return 0;
}
static int
-timed_lookups_multi(unsigned with_data, unsigned table_index)
+timed_lookups_multi(unsigned int with_hash, unsigned int with_data,
+ unsigned int table_index, unsigned int ext)
{
unsigned i, j, k;
int32_t positions_burst[BURST_SIZE];
void *ret_data[BURST_SIZE];
uint64_t hit_mask;
int ret;
+ unsigned int keys_to_add, num_lookups;
+
+ if (!ext) {
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ num_lookups = NUM_LOOKUPS * ADD_PERCENT;
+ } else {
+ keys_to_add = KEYS_TO_ADD;
+ num_lookups = NUM_LOOKUPS;
+ }
const uint64_t start_tsc = rte_rdtsc();
- for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {
- for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {
+ for (i = 0; i < num_lookups/keys_to_add; i++) {
+ for (j = 0; j < keys_to_add/BURST_SIZE; j++) {
for (k = 0; k < BURST_SIZE; k++)
keys_burst[k] = keys[j * BURST_SIZE + k];
- if (with_data) {
+ if (!with_hash && with_data) {
ret = rte_hash_lookup_bulk_data(h[table_index],
(const void **) keys_burst,
BURST_SIZE,
return -1;
}
}
+ } else if (with_hash && with_data) {
+ ret = rte_hash_lookup_with_hash_bulk_data(
+ h[table_index],
+ (const void **)keys_burst,
+ &signatures[j * BURST_SIZE],
+ BURST_SIZE, &hit_mask, ret_data);
+ if (ret != BURST_SIZE) {
+ printf("Expect to find %u keys,"
+ " but found %d\n",
+ BURST_SIZE, ret);
+ return -1;
+ }
+ for (k = 0; k < BURST_SIZE; k++) {
+ if ((hit_mask & (1ULL << k)) == 0) {
+ printf("Key number %u"
+ " not found\n",
+ j * BURST_SIZE + k);
+ return -1;
+ }
+ expected_data[k] =
+ (void *)((uintptr_t)signatures[
+ j * BURST_SIZE + k]);
+ if (ret_data[k] != expected_data[k]) {
+ printf("Data returned for key"
+ " number %u is %p,"
+ " but should be %p\n",
+ j * BURST_SIZE + k,
+ ret_data[k],
+ expected_data[k]);
+ return -1;
+ }
+ }
+ } else if (with_hash && !with_data) {
+ ret = rte_hash_lookup_with_hash_bulk(
+ h[table_index],
+ (const void **)keys_burst,
+ &signatures[j * BURST_SIZE],
+ BURST_SIZE, positions_burst);
+ for (k = 0; k < BURST_SIZE; k++) {
+ if (positions_burst[k] !=
+ positions[j *
+ BURST_SIZE + k]) {
+ printf("Key looked up in %d, should be in %d\n",
+ positions_burst[k],
+ positions[j *
+ BURST_SIZE + k]);
+ return -1;
+ }
+ }
} else {
rte_hash_lookup_bulk(h[table_index],
(const void **) keys_burst,
const uint64_t end_tsc = rte_rdtsc();
const uint64_t time_taken = end_tsc - start_tsc;
- cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS;
+ cycles[table_index][OP_LOOKUP_MULTI][with_hash][with_data] =
+ time_taken/num_lookups;
return 0;
}
static int
-timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
+timed_deletes(unsigned int with_hash, unsigned int with_data,
+ unsigned int table_index, unsigned int ext)
{
unsigned i;
const uint64_t start_tsc = rte_rdtsc();
int32_t ret;
+ unsigned int keys_to_add;
+ if (!ext)
+ keys_to_add = KEYS_TO_ADD * ADD_PERCENT;
+ else
+ keys_to_add = KEYS_TO_ADD;
- for (i = 0; i < KEYS_TO_ADD; i++) {
+ for (i = 0; i < keys_to_add; i++) {
/* There are no delete functions with data, so just call two functions */
if (with_hash)
ret = rte_hash_del_key_with_hash(h[table_index],
if (ret >= 0)
positions[i] = ret;
else {
- printf("Failed to add key number %u\n", ret);
+ printf("Failed to delete key number %u\n", i);
return -1;
}
}
const uint64_t end_tsc = rte_rdtsc();
const uint64_t time_taken = end_tsc - start_tsc;
- cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD;
+ cycles[table_index][OP_DELETE][with_hash][with_data] = time_taken/keys_to_add;
return 0;
}
}
static int
-run_all_tbl_perf_tests(unsigned with_pushes)
+run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks,
+ unsigned int ext)
{
unsigned i, j, with_data, with_hash;
for (with_data = 0; with_data <= 1; with_data++) {
for (i = 0; i < NUM_KEYSIZES; i++) {
- if (create_table(with_data, i) < 0)
+ if (create_table(with_data, i, with_locks, ext) < 0)
return -1;
- if (get_input_keys(with_pushes, i) < 0)
+ if (get_input_keys(with_pushes, i, ext) < 0)
return -1;
for (with_hash = 0; with_hash <= 1; with_hash++) {
- if (timed_adds(with_hash, with_data, i) < 0)
+ if (timed_adds(with_hash, with_data, i, ext) < 0)
return -1;
for (j = 0; j < NUM_SHUFFLES; j++)
- shuffle_input_keys(i);
+ shuffle_input_keys(i, ext);
- if (timed_lookups(with_hash, with_data, i) < 0)
+ if (timed_lookups(with_hash, with_data, i, ext) < 0)
return -1;
- if (timed_lookups_multi(with_data, i) < 0)
+ if (timed_lookups_multi(with_hash, with_data,
+ i, ext) < 0)
return -1;
- if (timed_deletes(with_hash, with_data, i) < 0)
+ if (timed_deletes(with_hash, with_data, i, ext) < 0)
return -1;
/* Print a dot to show progress on operations */
static int
test_hash_perf(void)
{
- unsigned with_pushes;
+ unsigned int with_pushes, with_locks;
- for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
- if (with_pushes == 0)
- printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
+ if (RTE_EXEC_ENV_IS_WINDOWS)
+ return TEST_SKIPPED;
+
+ for (with_locks = 0; with_locks <= 1; with_locks++) {
+ if (with_locks)
+ printf("\nWith locks in the code\n");
else
- printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
- if (run_all_tbl_perf_tests(with_pushes) < 0)
- return -1;
+ printf("\nWithout locks in the code\n");
+ for (with_pushes = 0; with_pushes <= 1; with_pushes++) {
+ if (with_pushes == 0)
+ printf("\nALL ELEMENTS IN PRIMARY LOCATION\n");
+ else
+ printf("\nELEMENTS IN PRIMARY OR SECONDARY LOCATION\n");
+ if (run_all_tbl_perf_tests(with_pushes, with_locks, 0) < 0)
+ return -1;
+ }
}
+
+ printf("\n EXTENDABLE BUCKETS PERFORMANCE\n");
+
+ if (run_all_tbl_perf_tests(1, 0, 1) < 0)
+ return -1;
+
if (fbk_hash_perf_test() < 0)
return -1;