summaryrefslogtreecommitdiff
path: root/test/test
diff options
context:
space:
mode:
authorYipeng Wang <yipeng1.wang@intel.com>2018-10-22 11:39:47 -0700
committerThomas Monjalon <thomas@monjalon.net>2018-10-26 01:04:33 +0200
commit6f4d0c79072a98282f566ff550f2639479dbc484 (patch)
tree75a07208272cd5d38cecade75e35c6b7b5205d54 /test/test
parent75706568a7eb8875328e2c95f4d71871bd58e494 (diff)
downloaddpdk-6f4d0c79072a98282f566ff550f2639479dbc484.zip
dpdk-6f4d0c79072a98282f566ff550f2639479dbc484.tar.gz
dpdk-6f4d0c79072a98282f566ff550f2639479dbc484.tar.xz
test/hash: add extendable bucket
This commit changes the current rte_hash unit test to test the extendable table feature and performance. Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com> Acked-by: Dharmik Thakkar <dharmik.thakkar@arm.com> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
Diffstat (limited to 'test/test')
-rw-r--r--test/test/test_hash.c159
-rw-r--r--test/test/test_hash_perf.c114
2 files changed, 238 insertions, 35 deletions
diff --git a/test/test/test_hash.c b/test/test/test_hash.c
index b3db9fd..815c734 100644
--- a/test/test/test_hash.c
+++ b/test/test/test_hash.c
@@ -660,6 +660,116 @@ static int test_full_bucket(void)
return 0;
}
+/*
+ * Similar to the test above (full bucket test), but for extendable buckets.
+ */
+static int test_extendable_bucket(void)
+{
+ struct rte_hash_parameters params_pseudo_hash = {
+ .name = "test5",
+ .entries = 64,
+ .key_len = sizeof(struct flow_key), /* 13 */
+ .hash_func = pseudo_hash,
+ .hash_func_init_val = 0,
+ .socket_id = 0,
+ .extra_flag = RTE_HASH_EXTRA_FLAGS_EXT_TABLE
+ };
+ struct rte_hash *handle;
+ int pos[64];
+ int expected_pos[64];
+ unsigned int i;
+ struct flow_key rand_keys[64];
+
+ for (i = 0; i < 64; i++) {
+ rand_keys[i].port_dst = i;
+ rand_keys[i].port_src = i+1;
+ }
+
+ handle = rte_hash_create(&params_pseudo_hash);
+ RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+
+ /* Fill bucket */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
+ print_key_info("Add", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] < 0,
+ "failed to add key (pos[%u]=%d)", i, pos[i]);
+ expected_pos[i] = pos[i];
+ }
+
+ /* Lookup */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
+ print_key_info("Lkp", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != expected_pos[i],
+ "failed to find key (pos[%u]=%d)", i, pos[i]);
+ }
+
+ /* Add - update */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
+ print_key_info("Add", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != expected_pos[i],
+ "failed to add key (pos[%u]=%d)", i, pos[i]);
+ }
+
+ /* Lookup */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
+ print_key_info("Lkp", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != expected_pos[i],
+ "failed to find key (pos[%u]=%d)", i, pos[i]);
+ }
+
+ /* Delete 1 key, check other keys are still found */
+ pos[35] = rte_hash_del_key(handle, &rand_keys[35]);
+ print_key_info("Del", &rand_keys[35], pos[35]);
+ RETURN_IF_ERROR(pos[35] != expected_pos[35],
+ "failed to delete key (pos[1]=%d)", pos[35]);
+ pos[20] = rte_hash_lookup(handle, &rand_keys[20]);
+ print_key_info("Lkp", &rand_keys[20], pos[20]);
+ RETURN_IF_ERROR(pos[20] != expected_pos[20],
+ "failed lookup after deleting key from same bucket "
+ "(pos[20]=%d)", pos[20]);
+
+ /* Go back to previous state */
+ pos[35] = rte_hash_add_key(handle, &rand_keys[35]);
+ print_key_info("Add", &rand_keys[35], pos[35]);
+ expected_pos[35] = pos[35];
+ RETURN_IF_ERROR(pos[35] < 0, "failed to add key (pos[1]=%d)", pos[35]);
+
+ /* Delete */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_del_key(handle, &rand_keys[i]);
+ print_key_info("Del", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != expected_pos[i],
+ "failed to delete key (pos[%u]=%d)", i, pos[i]);
+ }
+
+ /* Lookup */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_lookup(handle, &rand_keys[i]);
+ print_key_info("Lkp", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] != -ENOENT,
+ "fail: found non-existent key (pos[%u]=%d)", i, pos[i]);
+ }
+
+ /* Add again */
+ for (i = 0; i < 64; i++) {
+ pos[i] = rte_hash_add_key(handle, &rand_keys[i]);
+ print_key_info("Add", &rand_keys[i], pos[i]);
+ RETURN_IF_ERROR(pos[i] < 0,
+ "failed to add key (pos[%u]=%d)", i, pos[i]);
+ expected_pos[i] = pos[i];
+ }
+
+ rte_hash_free(handle);
+
+ /* Cover the NULL case. */
+ rte_hash_free(0);
+ return 0;
+}
+
/******************************************************************************/
static int
fbk_hash_unit_test(void)
@@ -1096,7 +1206,7 @@ test_hash_creation_with_good_parameters(void)
* Test to see the average table utilization (entries added/max entries)
* before hitting a random entry that cannot be added
*/
-static int test_average_table_utilization(void)
+static int test_average_table_utilization(uint32_t ext_table)
{
struct rte_hash *handle;
uint8_t simple_key[MAX_KEYSIZE];
@@ -1107,12 +1217,23 @@ static int test_average_table_utilization(void)
printf("\n# Running test to determine average utilization"
"\n before adding elements begins to fail\n");
+ if (ext_table)
+ printf("ext table is enabled\n");
+ else
+ printf("ext table is disabled\n");
+
printf("Measuring performance, please wait");
fflush(stdout);
ut_params.entries = 1 << 16;
ut_params.name = "test_average_utilization";
ut_params.hash_func = rte_jhash;
+ if (ext_table)
+ ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
+ else
+ ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
+
handle = rte_hash_create(&ut_params);
+
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
for (j = 0; j < ITERATIONS; j++) {
@@ -1139,6 +1260,14 @@ static int test_average_table_utilization(void)
rte_hash_free(handle);
return -1;
}
+ if (ext_table) {
+ if (cnt != ut_params.entries) {
+ printf("rte_hash_count returned wrong value "
+ "%u, %u, %u\n", j, added_keys, cnt);
+ rte_hash_free(handle);
+ return -1;
+ }
+ }
average_keys_added += added_keys;
@@ -1161,7 +1290,7 @@ static int test_average_table_utilization(void)
}
#define NUM_ENTRIES 256
-static int test_hash_iteration(void)
+static int test_hash_iteration(uint32_t ext_table)
{
struct rte_hash *handle;
unsigned i;
@@ -1177,6 +1306,11 @@ static int test_hash_iteration(void)
ut_params.name = "test_hash_iteration";
ut_params.hash_func = rte_jhash;
ut_params.key_len = 16;
+ if (ext_table)
+ ut_params.extra_flag |= RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
+ else
+ ut_params.extra_flag &= ~RTE_HASH_EXTRA_FLAGS_EXT_TABLE;
+
handle = rte_hash_create(&ut_params);
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
@@ -1186,8 +1320,13 @@ static int test_hash_iteration(void)
for (i = 0; i < ut_params.key_len; i++)
keys[added_keys][i] = rte_rand() % 255;
ret = rte_hash_add_key_data(handle, keys[added_keys], data[added_keys]);
- if (ret < 0)
+ if (ret < 0) {
+ if (ext_table) {
+ printf("Insertion failed for ext table\n");
+ goto err;
+ }
break;
+ }
}
/* Iterate through the hash table */
@@ -1474,6 +1613,8 @@ test_hash(void)
return -1;
if (test_full_bucket() < 0)
return -1;
+ if (test_extendable_bucket() < 0)
+ return -1;
if (test_fbk_hash_find_existing() < 0)
return -1;
@@ -1483,9 +1624,17 @@ test_hash(void)
return -1;
if (test_hash_creation_with_good_parameters() < 0)
return -1;
- if (test_average_table_utilization() < 0)
+
+ /* ext table disabled */
+ if (test_average_table_utilization(0) < 0)
+ return -1;
+ if (test_hash_iteration(0) < 0)
+ return -1;
+
+ /* ext table enabled */
+ if (test_average_table_utilization(1) < 0)
return -1;
- if (test_hash_iteration() < 0)
+ if (test_hash_iteration(1) < 0)
return -1;
run_hash_func_tests();
diff --git a/test/test/test_hash_perf.c b/test/test/test_hash_perf.c
index 0d39e10..5252111 100644
--- a/test/test/test_hash_perf.c
+++ b/test/test/test_hash_perf.c
@@ -18,7 +18,8 @@
#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 */
/* BUCKET_SIZE should be same as RTE_HASH_BUCKET_ENTRIES in rte_hash library */
#define BUCKET_SIZE 8
@@ -78,7 +79,7 @@ static struct rte_hash_parameters ut_params = {
static int
create_table(unsigned int with_data, unsigned int table_index,
- unsigned int with_locks)
+ unsigned int with_locks, unsigned int ext)
{
char name[RTE_HASH_NAMESIZE];
@@ -96,6 +97,9 @@ create_table(unsigned int with_data, unsigned int table_index,
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];
ut_params.socket_id = rte_socket_id();
@@ -117,15 +121,21 @@ create_table(unsigned int with_data, unsigned int 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]);
@@ -147,14 +157,20 @@ shuffle_input_keys(unsigned 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;
@@ -171,7 +187,7 @@ get_input_keys(unsigned with_pushes, unsigned table_index)
* 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;
@@ -235,14 +251,20 @@ get_input_keys(unsigned with_pushes, unsigned table_index)
}
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],
@@ -284,22 +306,31 @@ timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index)
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][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],
@@ -352,13 +383,14 @@ timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index)
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][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_data, unsigned int table_index,
+ unsigned int ext)
{
unsigned i, j, k;
int32_t positions_burst[BURST_SIZE];
@@ -367,11 +399,20 @@ timed_lookups_multi(unsigned with_data, unsigned table_index)
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) {
@@ -419,19 +460,25 @@ timed_lookups_multi(unsigned with_data, unsigned table_index)
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][LOOKUP_MULTI][0][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],
@@ -451,7 +498,7 @@ timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index)
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][DELETE][with_hash][with_data] = time_taken/keys_to_add;
return 0;
}
@@ -469,7 +516,8 @@ reset_table(unsigned table_index)
}
static int
-run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks)
+run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks,
+ unsigned int ext)
{
unsigned i, j, with_data, with_hash;
@@ -478,25 +526,25 @@ run_all_tbl_perf_tests(unsigned int with_pushes, unsigned int with_locks)
for (with_data = 0; with_data <= 1; with_data++) {
for (i = 0; i < NUM_KEYSIZES; i++) {
- if (create_table(with_data, i, with_locks) < 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_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 */
@@ -632,10 +680,16 @@ test_hash_perf(void)
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)
+ 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;