From patchwork Wed Sep 26 20:26:57 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Wang, Yipeng1" X-Patchwork-Id: 45475 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id B06F81B126; Thu, 27 Sep 2018 05:33:53 +0200 (CEST) Received: from mga06.intel.com (mga06.intel.com [134.134.136.31]) by dpdk.org (Postfix) with ESMTP id CA1031B126 for ; Thu, 27 Sep 2018 05:33:35 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by orsmga104.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 26 Sep 2018 20:33:33 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,308,1534834800"; d="scan'208";a="74018104" Received: from skx-yipeng.jf.intel.com ([10.54.81.175]) by fmsmga008.fm.intel.com with ESMTP; 26 Sep 2018 20:31:51 -0700 From: Yipeng Wang To: bruce.richardson@intel.com Cc: dev@dpdk.org, yipeng1.wang@intel.com, honnappa.nagarahalli@arm.com, michel@digirati.com.br, sameh.gobriel@intel.com Date: Wed, 26 Sep 2018 13:26:57 -0700 Message-Id: <1537993618-92630-3-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> References: <1536253745-133104-1-git-send-email-yipeng1.wang@intel.com> <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> Subject: [dpdk-dev] [PATCH v3 2/3] test/hash: implement extendable bucket hash test X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" This commit changes the current rte_hash unit test to test the extendable table feature and performance. Signed-off-by: Yipeng Wang --- test/test/test_hash.c | 151 +++++++++++++++++++++++++++++++++++++++++++-- test/test/test_hash_perf.c | 114 +++++++++++++++++++++++++--------- 2 files changed, 230 insertions(+), 35 deletions(-) diff --git a/test/test/test_hash.c b/test/test/test_hash.c index b3db9fd..c97095f 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++) { @@ -1161,7 +1282,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 +1298,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 +1312,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 +1605,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 +1616,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 4d00c20..d169cd0 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 */ #define BUCKET_SIZE 8 #define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE) @@ -77,7 +78,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]; @@ -95,6 +96,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(); @@ -116,15 +120,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]); @@ -146,14 +156,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; @@ -170,7 +186,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; @@ -234,14 +250,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], @@ -283,22 +305,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], @@ -351,13 +382,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]; @@ -366,11 +398,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) { @@ -418,19 +459,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], @@ -450,7 +497,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; } @@ -468,7 +515,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; @@ -477,25 +525,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 */ @@ -631,10 +679,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;