[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(-)
  

> -----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(&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;
> 
> --
> 2.7.4

Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>