[v4,3/4] test/hash: implement extendable bucket hash test
Checks
Commit Message
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>
---
test/test/test_hash.c | 159 +++++++++++++++++++++++++++++++++++++++++++--
test/test/test_hash_perf.c | 114 +++++++++++++++++++++++---------
2 files changed, 238 insertions(+), 35 deletions(-)
Comments
> -----Original Message-----
> From: Yipeng Wang <yipeng1.wang@intel.com>
> Sent: Friday, September 28, 2018 12:24 PM
> To: bruce.richardson@intel.com
> Cc: konstantin.ananyev@intel.com; dev@dpdk.org; yipeng1.wang@intel.com;
> Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>;
> sameh.gobriel@intel.com
> Subject: [PATCH v4 3/4] test/hash: implement extendable bucket hash test
>
> 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>
> ---
> test/test/test_hash.c | 159
> +++++++++++++++++++++++++++++++++++++++++++--
> test/test/test_hash_perf.c | 114 +++++++++++++++++++++++---------
> 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(¶ms_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;
>
> --
> 2.7.4
Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
@@ -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(¶ms_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();
@@ -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;