diff mbox series

[v2,6/7] test/hash: implement extendable bucket hash test

Message ID 1537550255-252066-7-git-send-email-yipeng1.wang@intel.com (mailing list archive)
State Superseded, archived
Delegated to: Thomas Monjalon
Headers show
Series hash: add extendable bucket and partial key hashing | expand

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/Intel-compilation success Compilation OK

Commit Message

Wang, Yipeng1 Sept. 21, 2018, 5:17 p.m. UTC
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      | 151 +++++++++++++++++++++++++++++++++++++++++++--
 test/test/test_hash_perf.c | 114 +++++++++++++++++++++++++---------
 2 files changed, 230 insertions(+), 35 deletions(-)

Comments

Honnappa Nagarahalli Sept. 27, 2018, 4:24 a.m. UTC | #1
> -----Original Message-----
> From: Yipeng Wang <yipeng1.wang@intel.com>
> Sent: Friday, September 21, 2018 12:18 PM
> To: bruce.richardson@intel.com
> Cc: dev@dpdk.org; yipeng1.wang@intel.com; michel@digirati.com.br;
> Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
> Subject: [PATCH v2 6/7] 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      | 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(&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++) {
My understanding is that when extendable table feature is enabled, we will add entries to the full capacity. Hence the rte_hash_count and rte_hash_reset should get tested in this test case.

> @@ -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;
> +}
>  }
>
I suggest we add a call to rte_hash_count() to verify that configured maximum number of entries are added, will be a good corner test for rte_hash_count as well.

>  /* 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;
>
> --
> 2.7.4

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.
Wang, Yipeng1 Sept. 29, 2018, 12:50 a.m. UTC | #2
>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>Sent: Wednesday, September 26, 2018 9:24 PM
>To: Wang, Yipeng1 <yipeng1.wang@intel.com>; Richardson, Bruce <bruce.richardson@intel.com>
>Cc: dev@dpdk.org; michel@digirati.com.br
>Subject: RE: [PATCH v2 6/7] test/hash: implement extendable bucket hash test
>
>>  RETURN_IF_ERROR(handle == NULL, "hash creation failed");
>>
>>  for (j = 0; j < ITERATIONS; j++) {
>My understanding is that when extendable table feature is enabled, we will add entries to the full capacity. Hence the
>rte_hash_count and rte_hash_reset should get tested in this test case.
>
[Wang, Yipeng] Currently both functions are already there in the loop right?
For V4, I've added another condition to double check if the count == param->entries.

>> @@ -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;
>> +}
>>  }
>>
>I suggest we add a call to rte_hash_count() to verify that configured maximum number of entries are added, will be a good corner test
>for rte_hash_count as well.
>
[Wang, Yipeng] Please check if the newly added logic in V4 addresses your concern.
diff mbox series

Patch

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(&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++) {
@@ -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;