diff mbox series

[2/2] test/member: add functional and perf tests for sketch

Message ID 20220810074518.1695013-3-leyi.rong@intel.com (mailing list archive)
State Superseded
Delegated to: Thomas Monjalon
Headers show
Series introduce NitroSketch Mode into membership library | expand

Checks

Context Check Description
ci/github-robot: build fail github build: failed
ci/intel-Testing success Testing PASS
ci/Intel-compilation fail Compilation issues
ci/checkpatch warning coding style issues

Commit Message

Leyi Rong Aug. 10, 2022, 7:45 a.m. UTC
This patch adds functional and performance tests for sketch mode of
membership library.

Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
Signed-off-by: Leyi Rong <leyi.rong@intel.com>
---
 app/test/test_member.c      | 258 ++++++++++++++++++++++++++++++++++++
 app/test/test_member_perf.c | 153 ++++++++++++++++++++-
 2 files changed, 407 insertions(+), 4 deletions(-)

Comments

Suanming Mou Aug. 11, 2022, 2:33 a.m. UTC | #1
Hi,

> -----Original Message-----
> From: Leyi Rong <leyi.rong@intel.com>
> Sent: Wednesday, August 10, 2022 3:45 PM
> To: yipeng1.wang@intel.com; zaoxingliu@gmail.com; sameh.gobriel@intel.com
> Cc: dev@dpdk.org; Leyi Rong <leyi.rong@intel.com>
> Subject: [PATCH 2/2] test/member: add functional and perf tests for sketch
> 
> This patch adds functional and performance tests for sketch mode of
> membership library.
> 
> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> Signed-off-by: Leyi Rong <leyi.rong@intel.com>
> ---
>  app/test/test_member.c      | 258 ++++++++++++++++++++++++++++++++++++
>  app/test/test_member_perf.c | 153 ++++++++++++++++++++-
>  2 files changed, 407 insertions(+), 4 deletions(-)
> 
> diff --git a/app/test/test_member.c b/app/test/test_member.c index
> 26a712439f..abe59bb9f8 100644
> --- a/app/test/test_member.c
> +++ b/app/test/test_member.c
> @@ -4,6 +4,7 @@
> 
>  /* This test is for membership library's simple feature test */
> 
> +#include <math.h>
>  #include "test.h"
> 
>  #include <rte_memcpy.h>
> @@ -28,6 +29,7 @@ test_member(void)
>  struct rte_member_setsum *setsum_ht;
>  struct rte_member_setsum *setsum_cache;  struct rte_member_setsum
> *setsum_vbf;
> +struct rte_member_setsum *setsum_sketch;
> 
>  /* 5-tuple key type */
>  struct flow_key {
> @@ -108,6 +110,21 @@ static struct rte_member_parameters params = {
>  		.socket_id = 0			/* NUMA Socket ID for
> memory. */
>  };
> 
> +/* for sketch definitions */
> +#define TOP_K 10
> +#define HH_PKT_SIZE 16
> +#define SKETCH_ERROR_RATE 0.05
> +#define SKETCH_SAMPLE_RATE 0.001
> +#define PRINT_OUT_COUNT 20
> +
> +#define SKETCH_LARGEST_KEY_SIZE 1000000 #define SKETCH_TOTAL_KEY 500
> +#define NUM_OF_KEY(key) {\
> +	(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \ }
> +
> +void *heavy_hitters[TOP_K];
> +
>  /*
>   * Sequence of operations for find existing setsummary
>   *
> @@ -684,6 +701,243 @@ perform_free(void)
>  	rte_member_free(setsum_vbf);
>  }
> 
> +static void
> +print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set,
> +			 uint32_t print_num, bool count_byte) {
> +	uint32_t i;
> +
> +	for (i = 0; i < print_num; i++) {
> +		if (count_byte)
> +			printf("key %2u, count %8lu, real count %8u, "
> +				"heavy_set %u, deviation rate [%.04f]\n",
> +				i, count_result[i],
> +				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE /
> (i + 1)) *
> +				HH_PKT_SIZE,
> +				heavy_set[i],
> +				fabs((float)count_result[i] -
> (float)NUM_OF_KEY(i) * HH_PKT_SIZE) /
> +				((float)NUM_OF_KEY(i) * HH_PKT_SIZE));
> +		else
> +			printf("key %2u, count %8lu, real count %8u, "
> +				"heavy_set %u, deviation rate [%.04f]\n",
> +				i, count_result[i],
> +				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE /
> (i + 1)),
> +				heavy_set[i],
> +				fabs((float)count_result[i] -
> (float)NUM_OF_KEY(i)) /
> +				(float)NUM_OF_KEY(i));
> +	}
> +}
> +
> +static int
> +sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int
> +reset_test) {
> +	uint32_t i;
> +	uint64_t result_count[SKETCH_TOTAL_KEY];
> +	member_set_t heavy_set[SKETCH_TOTAL_KEY];
> +	uint64_t count[TOP_K];
> +	int ret;
> +	int hh_cnt;
> +
> +	setsum_sketch = rte_member_create(&params);
> +	if (setsum_sketch == NULL) {
> +		printf("Creation of setsums fail\n");
> +		return -1;
> +	}
> +
> +	for (i = 0; i < total_pkt; i++) {
> +		if (count_byte)
> +			ret = rte_member_add_byte_count(setsum_sketch,
> &keys[i], HH_PKT_SIZE);
> +		else
> +			ret = rte_member_add(setsum_sketch, &keys[i], 1);
> +
> +		if (ret < 0) {
> +			printf("rte_member_add Failed! Error [%d]\n", ret);

I'm afraid rte_member_free(setsum_sketch) is missing here.
Same code below with "return -1;" should be checked.

> +
> +			return -1;
> +		}
> +	}
> +
> +	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> +		uint32_t tmp_key = i;
> +
> +		rte_member_query_count(setsum_sketch, (void *)&tmp_key,
> &result_count[i]);
> +		rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> &heavy_set[i]);
> +	}
> +
> +	print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT,
> +count_byte);
> +
> +	hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters,
> count);
> +	if (hh_cnt < 0) {
> +		printf("sketch report heavy hitter error!");
> +
> +		return -1;
> +	}
> +
> +	printf("Report heavy hitters:");
> +	for (i = 0; i < (unsigned int)hh_cnt; i++) {
> +		printf("%u: %lu\t",
> +			*((uint32_t *)heavy_hitters[i]), count[i]);
> +	}
> +	printf("\n");
> +
> +	if (reset_test) {
> +		printf("\nEntering Sketch Reset Test Process!\n");
> +		rte_member_reset(setsum_sketch);
> +
> +		/* after reset, check some key's count */
> +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> +			uint32_t tmp_key = i;
> +
> +			rte_member_query_count(setsum_sketch, (void
> *)&tmp_key, &result_count[i]);
> +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> &heavy_set[i]);
> +		}
> +
> +		print_out_sketch_results(result_count, heavy_set,
> PRINT_OUT_COUNT,
> +count_byte);
> +
> +		printf("\nReinsert keys after Sketch Reset!\n");
> +		for (i = 0; i < total_pkt; i++) {
> +			if (count_byte)
> +				ret = rte_member_add_byte_count
> +					(setsum_sketch, &keys[i],
> HH_PKT_SIZE);
> +			else
> +				ret = rte_member_add(setsum_sketch, &keys[i],
> 1);
> +
> +			if (ret < 0) {
> +				printf("rte_member_add Failed! Error [%d]\n",
> ret);
> +
> +				return -1;
> +			}
> +		}
> +
> +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> +			uint32_t tmp_key = i;
> +
> +			rte_member_query_count(setsum_sketch, (void
> *)&tmp_key, &result_count[i]);
> +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> &heavy_set[i]);
> +		}
> +
> +		print_out_sketch_results(result_count, heavy_set,
> PRINT_OUT_COUNT,
> +count_byte);
> +
> +		hh_cnt = rte_member_report_heavyhitter(setsum_sketch,
> heavy_hitters, count);
> +		if (hh_cnt < 0) {
> +			printf("sketch report heavy hitter error!");
> +
> +			return -1;
> +		}
> +		printf("Report heavy hitters:");
> +		for (i = 0; i < (unsigned int)hh_cnt; i++) {
> +			printf("%u: %lu\t",
> +				*((uint32_t *)heavy_hitters[i]), count[i]);
> +		}
> +		printf("\n");
> +
> +		printf("\nDelete some keys!\n");
> +		uint32_t tmp_key = 0;
> +
> +		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
> +		tmp_key = 1;
> +		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
> +
> +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> +			uint32_t tmp_key = i;
> +
> +			rte_member_query_count(setsum_sketch, (void
> *)&tmp_key, &result_count[i]);
> +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> &heavy_set[i]);
> +		}
> +
> +		print_out_sketch_results(result_count, heavy_set,
> PRINT_OUT_COUNT,
> +count_byte);
> +
> +		hh_cnt = rte_member_report_heavyhitter(setsum_sketch,
> heavy_hitters, count);
> +		if (hh_cnt < 0) {
> +			printf("sketch report heavy hitter error!");
> +
> +			return -1;
> +		}
> +		printf("Report heavy hitters:");
> +		for (i = 0; i < (unsigned int)hh_cnt; i++) {
> +			printf("%u: %lu\t",
> +				*((uint32_t *)heavy_hitters[i]), count[i]);
> +		}
> +		printf("\n");
> +	}
> +
> +	rte_member_free(setsum_sketch);
> +	return 0;
> +}
> +
> +static int
> +test_member_sketch(void)
> +{
> +	unsigned int i, j, index;
> +	uint32_t total_pkt = 0;
> +	uint32_t *keys;
> +	int count_byte = 0;
> +
> +	for (i = 0; i < SKETCH_TOTAL_KEY; i++)
> +		total_pkt += ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1));
> +
> +	printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt);
> +
> +	keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0);
> +
> +	if (keys == NULL) {
> +		printf("RTE_ZMALLOC failed\n");
> +		return -1;
> +	}
> +
> +	index = 0;
> +	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> +		for (j = 0; j < ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++)
> +			keys[index++] = i;
> +	}
> +
> +	/* shuffle the keys */
> +	for (i = index - 1; i > 0; i--) {
> +		uint32_t swap_idx = rte_rand() % i;
> +		uint32_t tmp_key = keys[i];
> +
> +		keys[i] = keys[swap_idx];
> +		keys[swap_idx] = tmp_key;
> +	}
> +
> +	params.key_len = 4;
> +	params.name = "test_member_sketch";
> +	params.type = RTE_MEMBER_TYPE_SKETCH;
> +	params.error_rate = SKETCH_ERROR_RATE;
> +	params.sample_rate = SKETCH_SAMPLE_RATE;
> +	params.extra_flag = 0;
> +	params.top_k = TOP_K;
> +	params.prim_hash_seed = rte_rdtsc();
> +	int reset_test = 0;
> +
> +	printf("Default sketching params: Error Rate: [%f]\tSample Rate:
> [%f]\tTopK: [%d]\n",
> +			SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K);
> +
> +	printf("\n[Sketch with Fixed Sampling Rate Mode]\n");
> +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)

Same here, will keys memory allocated by rte_zmalloc be freed in other place?

> +		return -1;
> +
> +	params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED;
> +	printf("\n[Sketch with Always Bounded Mode]\n");
> +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
> +		return -1;
> +
> +	count_byte = 1;
> +	params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE;
> +	printf("\n[Sketch with Packet Size Mode]\n");
> +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
> +		return -1;
> +
> +	count_byte = 0;
> +	params.extra_flag = 0;


snip
Leyi Rong Aug. 26, 2022, 2:26 a.m. UTC | #2
Hi Suanming,

The issues you've mentioned will be fixed in v2, thanks!

> -----Original Message-----
> From: Suanming Mou <suanmingm@nvidia.com>
> Sent: Thursday, August 11, 2022 10:33 AM
> To: Rong, Leyi <leyi.rong@intel.com>; Wang, Yipeng1
> <yipeng1.wang@intel.com>; zaoxingliu@gmail.com; Gobriel, Sameh
> <sameh.gobriel@intel.com>
> Cc: dev@dpdk.org
> Subject: RE: [PATCH 2/2] test/member: add functional and perf tests for sketch
> 
> Hi,
> 
> > -----Original Message-----
> > From: Leyi Rong <leyi.rong@intel.com>
> > Sent: Wednesday, August 10, 2022 3:45 PM
> > To: yipeng1.wang@intel.com; zaoxingliu@gmail.com;
> > sameh.gobriel@intel.com
> > Cc: dev@dpdk.org; Leyi Rong <leyi.rong@intel.com>
> > Subject: [PATCH 2/2] test/member: add functional and perf tests for
> > sketch
> >
> > This patch adds functional and performance tests for sketch mode of
> > membership library.
> >
> > Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
> > Signed-off-by: Leyi Rong <leyi.rong@intel.com>
> > ---
> >  app/test/test_member.c      | 258 ++++++++++++++++++++++++++++++++++++
> >  app/test/test_member_perf.c | 153 ++++++++++++++++++++-
> >  2 files changed, 407 insertions(+), 4 deletions(-)
> >
> > diff --git a/app/test/test_member.c b/app/test/test_member.c index
> > 26a712439f..abe59bb9f8 100644
> > --- a/app/test/test_member.c
> > +++ b/app/test/test_member.c
> > @@ -4,6 +4,7 @@
> >
> >  /* This test is for membership library's simple feature test */
> >
> > +#include <math.h>
> >  #include "test.h"
> >
> >  #include <rte_memcpy.h>
> > @@ -28,6 +29,7 @@ test_member(void)
> >  struct rte_member_setsum *setsum_ht;
> >  struct rte_member_setsum *setsum_cache;  struct rte_member_setsum
> > *setsum_vbf;
> > +struct rte_member_setsum *setsum_sketch;
> >
> >  /* 5-tuple key type */
> >  struct flow_key {
> > @@ -108,6 +110,21 @@ static struct rte_member_parameters params = {
> >  		.socket_id = 0			/* NUMA Socket ID for
> > memory. */
> >  };
> >
> > +/* for sketch definitions */
> > +#define TOP_K 10
> > +#define HH_PKT_SIZE 16
> > +#define SKETCH_ERROR_RATE 0.05
> > +#define SKETCH_SAMPLE_RATE 0.001
> > +#define PRINT_OUT_COUNT 20
> > +
> > +#define SKETCH_LARGEST_KEY_SIZE 1000000 #define SKETCH_TOTAL_KEY
> 500
> > +#define NUM_OF_KEY(key) {\
> > +	(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \ }
> > +
> > +void *heavy_hitters[TOP_K];
> > +
> >  /*
> >   * Sequence of operations for find existing setsummary
> >   *
> > @@ -684,6 +701,243 @@ perform_free(void)
> >  	rte_member_free(setsum_vbf);
> >  }
> >
> > +static void
> > +print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set,
> > +			 uint32_t print_num, bool count_byte) {
> > +	uint32_t i;
> > +
> > +	for (i = 0; i < print_num; i++) {
> > +		if (count_byte)
> > +			printf("key %2u, count %8lu, real count %8u, "
> > +				"heavy_set %u, deviation rate [%.04f]\n",
> > +				i, count_result[i],
> > +				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE /
> > (i + 1)) *
> > +				HH_PKT_SIZE,
> > +				heavy_set[i],
> > +				fabs((float)count_result[i] -
> > (float)NUM_OF_KEY(i) * HH_PKT_SIZE) /
> > +				((float)NUM_OF_KEY(i) * HH_PKT_SIZE));
> > +		else
> > +			printf("key %2u, count %8lu, real count %8u, "
> > +				"heavy_set %u, deviation rate [%.04f]\n",
> > +				i, count_result[i],
> > +				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE /
> > (i + 1)),
> > +				heavy_set[i],
> > +				fabs((float)count_result[i] -
> > (float)NUM_OF_KEY(i)) /
> > +				(float)NUM_OF_KEY(i));
> > +	}
> > +}
> > +
> > +static int
> > +sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int
> > +reset_test) {
> > +	uint32_t i;
> > +	uint64_t result_count[SKETCH_TOTAL_KEY];
> > +	member_set_t heavy_set[SKETCH_TOTAL_KEY];
> > +	uint64_t count[TOP_K];
> > +	int ret;
> > +	int hh_cnt;
> > +
> > +	setsum_sketch = rte_member_create(&params);
> > +	if (setsum_sketch == NULL) {
> > +		printf("Creation of setsums fail\n");
> > +		return -1;
> > +	}
> > +
> > +	for (i = 0; i < total_pkt; i++) {
> > +		if (count_byte)
> > +			ret = rte_member_add_byte_count(setsum_sketch,
> > &keys[i], HH_PKT_SIZE);
> > +		else
> > +			ret = rte_member_add(setsum_sketch, &keys[i], 1);
> > +
> > +		if (ret < 0) {
> > +			printf("rte_member_add Failed! Error [%d]\n", ret);
> 
> I'm afraid rte_member_free(setsum_sketch) is missing here.
> Same code below with "return -1;" should be checked.
> 
> > +
> > +			return -1;
> > +		}
> > +	}
> > +
> > +	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> > +		uint32_t tmp_key = i;
> > +
> > +		rte_member_query_count(setsum_sketch, (void *)&tmp_key,
> > &result_count[i]);
> > +		rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> > &heavy_set[i]);
> > +	}
> > +
> > +	print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT,
> > +count_byte);
> > +
> > +	hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters,
> > count);
> > +	if (hh_cnt < 0) {
> > +		printf("sketch report heavy hitter error!");
> > +
> > +		return -1;
> > +	}
> > +
> > +	printf("Report heavy hitters:");
> > +	for (i = 0; i < (unsigned int)hh_cnt; i++) {
> > +		printf("%u: %lu\t",
> > +			*((uint32_t *)heavy_hitters[i]), count[i]);
> > +	}
> > +	printf("\n");
> > +
> > +	if (reset_test) {
> > +		printf("\nEntering Sketch Reset Test Process!\n");
> > +		rte_member_reset(setsum_sketch);
> > +
> > +		/* after reset, check some key's count */
> > +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> > +			uint32_t tmp_key = i;
> > +
> > +			rte_member_query_count(setsum_sketch, (void
> > *)&tmp_key, &result_count[i]);
> > +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> > &heavy_set[i]);
> > +		}
> > +
> > +		print_out_sketch_results(result_count, heavy_set,
> > PRINT_OUT_COUNT,
> > +count_byte);
> > +
> > +		printf("\nReinsert keys after Sketch Reset!\n");
> > +		for (i = 0; i < total_pkt; i++) {
> > +			if (count_byte)
> > +				ret = rte_member_add_byte_count
> > +					(setsum_sketch, &keys[i],
> > HH_PKT_SIZE);
> > +			else
> > +				ret = rte_member_add(setsum_sketch, &keys[i],
> > 1);
> > +
> > +			if (ret < 0) {
> > +				printf("rte_member_add Failed! Error [%d]\n",
> > ret);
> > +
> > +				return -1;
> > +			}
> > +		}
> > +
> > +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> > +			uint32_t tmp_key = i;
> > +
> > +			rte_member_query_count(setsum_sketch, (void
> > *)&tmp_key, &result_count[i]);
> > +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> > &heavy_set[i]);
> > +		}
> > +
> > +		print_out_sketch_results(result_count, heavy_set,
> > PRINT_OUT_COUNT,
> > +count_byte);
> > +
> > +		hh_cnt = rte_member_report_heavyhitter(setsum_sketch,
> > heavy_hitters, count);
> > +		if (hh_cnt < 0) {
> > +			printf("sketch report heavy hitter error!");
> > +
> > +			return -1;
> > +		}
> > +		printf("Report heavy hitters:");
> > +		for (i = 0; i < (unsigned int)hh_cnt; i++) {
> > +			printf("%u: %lu\t",
> > +				*((uint32_t *)heavy_hitters[i]), count[i]);
> > +		}
> > +		printf("\n");
> > +
> > +		printf("\nDelete some keys!\n");
> > +		uint32_t tmp_key = 0;
> > +
> > +		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
> > +		tmp_key = 1;
> > +		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
> > +
> > +		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> > +			uint32_t tmp_key = i;
> > +
> > +			rte_member_query_count(setsum_sketch, (void
> > *)&tmp_key, &result_count[i]);
> > +			rte_member_lookup(setsum_sketch, (void *)&tmp_key,
> > &heavy_set[i]);
> > +		}
> > +
> > +		print_out_sketch_results(result_count, heavy_set,
> > PRINT_OUT_COUNT,
> > +count_byte);
> > +
> > +		hh_cnt = rte_member_report_heavyhitter(setsum_sketch,
> > heavy_hitters, count);
> > +		if (hh_cnt < 0) {
> > +			printf("sketch report heavy hitter error!");
> > +
> > +			return -1;
> > +		}
> > +		printf("Report heavy hitters:");
> > +		for (i = 0; i < (unsigned int)hh_cnt; i++) {
> > +			printf("%u: %lu\t",
> > +				*((uint32_t *)heavy_hitters[i]), count[i]);
> > +		}
> > +		printf("\n");
> > +	}
> > +
> > +	rte_member_free(setsum_sketch);
> > +	return 0;
> > +}
> > +
> > +static int
> > +test_member_sketch(void)
> > +{
> > +	unsigned int i, j, index;
> > +	uint32_t total_pkt = 0;
> > +	uint32_t *keys;
> > +	int count_byte = 0;
> > +
> > +	for (i = 0; i < SKETCH_TOTAL_KEY; i++)
> > +		total_pkt += ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1));
> > +
> > +	printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt);
> > +
> > +	keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0);
> > +
> > +	if (keys == NULL) {
> > +		printf("RTE_ZMALLOC failed\n");
> > +		return -1;
> > +	}
> > +
> > +	index = 0;
> > +	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
> > +		for (j = 0; j < ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++)
> > +			keys[index++] = i;
> > +	}
> > +
> > +	/* shuffle the keys */
> > +	for (i = index - 1; i > 0; i--) {
> > +		uint32_t swap_idx = rte_rand() % i;
> > +		uint32_t tmp_key = keys[i];
> > +
> > +		keys[i] = keys[swap_idx];
> > +		keys[swap_idx] = tmp_key;
> > +	}
> > +
> > +	params.key_len = 4;
> > +	params.name = "test_member_sketch";
> > +	params.type = RTE_MEMBER_TYPE_SKETCH;
> > +	params.error_rate = SKETCH_ERROR_RATE;
> > +	params.sample_rate = SKETCH_SAMPLE_RATE;
> > +	params.extra_flag = 0;
> > +	params.top_k = TOP_K;
> > +	params.prim_hash_seed = rte_rdtsc();
> > +	int reset_test = 0;
> > +
> > +	printf("Default sketching params: Error Rate: [%f]\tSample Rate:
> > [%f]\tTopK: [%d]\n",
> > +			SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K);
> > +
> > +	printf("\n[Sketch with Fixed Sampling Rate Mode]\n");
> > +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
> 
> Same here, will keys memory allocated by rte_zmalloc be freed in other place?
> 
> > +		return -1;
> > +
> > +	params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED;
> > +	printf("\n[Sketch with Always Bounded Mode]\n");
> > +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
> > +		return -1;
> > +
> > +	count_byte = 1;
> > +	params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE;
> > +	printf("\n[Sketch with Packet Size Mode]\n");
> > +	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
> > +		return -1;
> > +
> > +	count_byte = 0;
> > +	params.extra_flag = 0;
> 
> 
> snip
diff mbox series

Patch

diff --git a/app/test/test_member.c b/app/test/test_member.c
index 26a712439f..abe59bb9f8 100644
--- a/app/test/test_member.c
+++ b/app/test/test_member.c
@@ -4,6 +4,7 @@ 
 
 /* This test is for membership library's simple feature test */
 
+#include <math.h>
 #include "test.h"
 
 #include <rte_memcpy.h>
@@ -28,6 +29,7 @@  test_member(void)
 struct rte_member_setsum *setsum_ht;
 struct rte_member_setsum *setsum_cache;
 struct rte_member_setsum *setsum_vbf;
+struct rte_member_setsum *setsum_sketch;
 
 /* 5-tuple key type */
 struct flow_key {
@@ -108,6 +110,21 @@  static struct rte_member_parameters params = {
 		.socket_id = 0			/* NUMA Socket ID for memory. */
 };
 
+/* for sketch definitions */
+#define TOP_K 10
+#define HH_PKT_SIZE 16
+#define SKETCH_ERROR_RATE 0.05
+#define SKETCH_SAMPLE_RATE 0.001
+#define PRINT_OUT_COUNT 20
+
+#define SKETCH_LARGEST_KEY_SIZE 1000000
+#define SKETCH_TOTAL_KEY 500
+#define NUM_OF_KEY(key) {\
+	(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \
+}
+
+void *heavy_hitters[TOP_K];
+
 /*
  * Sequence of operations for find existing setsummary
  *
@@ -684,6 +701,243 @@  perform_free(void)
 	rte_member_free(setsum_vbf);
 }
 
+static void
+print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set,
+			 uint32_t print_num, bool count_byte)
+{
+	uint32_t i;
+
+	for (i = 0; i < print_num; i++) {
+		if (count_byte)
+			printf("key %2u, count %8lu, real count %8u, "
+				"heavy_set %u, deviation rate [%.04f]\n",
+				i, count_result[i],
+				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)) *
+				HH_PKT_SIZE,
+				heavy_set[i],
+				fabs((float)count_result[i] - (float)NUM_OF_KEY(i) * HH_PKT_SIZE) /
+				((float)NUM_OF_KEY(i) * HH_PKT_SIZE));
+		else
+			printf("key %2u, count %8lu, real count %8u, "
+				"heavy_set %u, deviation rate [%.04f]\n",
+				i, count_result[i],
+				(unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)),
+				heavy_set[i],
+				fabs((float)count_result[i] - (float)NUM_OF_KEY(i)) /
+				(float)NUM_OF_KEY(i));
+	}
+}
+
+static int
+sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int reset_test)
+{
+	uint32_t i;
+	uint64_t result_count[SKETCH_TOTAL_KEY];
+	member_set_t heavy_set[SKETCH_TOTAL_KEY];
+	uint64_t count[TOP_K];
+	int ret;
+	int hh_cnt;
+
+	setsum_sketch = rte_member_create(&params);
+	if (setsum_sketch == NULL) {
+		printf("Creation of setsums fail\n");
+		return -1;
+	}
+
+	for (i = 0; i < total_pkt; i++) {
+		if (count_byte)
+			ret = rte_member_add_byte_count(setsum_sketch, &keys[i], HH_PKT_SIZE);
+		else
+			ret = rte_member_add(setsum_sketch, &keys[i], 1);
+
+		if (ret < 0) {
+			printf("rte_member_add Failed! Error [%d]\n", ret);
+
+			return -1;
+		}
+	}
+
+	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
+		uint32_t tmp_key = i;
+
+		rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
+		rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
+	}
+
+	print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
+
+	hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
+	if (hh_cnt < 0) {
+		printf("sketch report heavy hitter error!");
+
+		return -1;
+	}
+
+	printf("Report heavy hitters:");
+	for (i = 0; i < (unsigned int)hh_cnt; i++) {
+		printf("%u: %lu\t",
+			*((uint32_t *)heavy_hitters[i]), count[i]);
+	}
+	printf("\n");
+
+	if (reset_test) {
+		printf("\nEntering Sketch Reset Test Process!\n");
+		rte_member_reset(setsum_sketch);
+
+		/* after reset, check some key's count */
+		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
+			uint32_t tmp_key = i;
+
+			rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
+			rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
+		}
+
+		print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
+
+		printf("\nReinsert keys after Sketch Reset!\n");
+		for (i = 0; i < total_pkt; i++) {
+			if (count_byte)
+				ret = rte_member_add_byte_count
+					(setsum_sketch, &keys[i], HH_PKT_SIZE);
+			else
+				ret = rte_member_add(setsum_sketch, &keys[i], 1);
+
+			if (ret < 0) {
+				printf("rte_member_add Failed! Error [%d]\n", ret);
+
+				return -1;
+			}
+		}
+
+		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
+			uint32_t tmp_key = i;
+
+			rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
+			rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
+		}
+
+		print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
+
+		hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
+		if (hh_cnt < 0) {
+			printf("sketch report heavy hitter error!");
+
+			return -1;
+		}
+		printf("Report heavy hitters:");
+		for (i = 0; i < (unsigned int)hh_cnt; i++) {
+			printf("%u: %lu\t",
+				*((uint32_t *)heavy_hitters[i]), count[i]);
+		}
+		printf("\n");
+
+		printf("\nDelete some keys!\n");
+		uint32_t tmp_key = 0;
+
+		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
+		tmp_key = 1;
+		rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
+
+		for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
+			uint32_t tmp_key = i;
+
+			rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
+			rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
+		}
+
+		print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
+
+		hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
+		if (hh_cnt < 0) {
+			printf("sketch report heavy hitter error!");
+
+			return -1;
+		}
+		printf("Report heavy hitters:");
+		for (i = 0; i < (unsigned int)hh_cnt; i++) {
+			printf("%u: %lu\t",
+				*((uint32_t *)heavy_hitters[i]), count[i]);
+		}
+		printf("\n");
+	}
+
+	rte_member_free(setsum_sketch);
+	return 0;
+}
+
+static int
+test_member_sketch(void)
+{
+	unsigned int i, j, index;
+	uint32_t total_pkt = 0;
+	uint32_t *keys;
+	int count_byte = 0;
+
+	for (i = 0; i < SKETCH_TOTAL_KEY; i++)
+		total_pkt += ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1));
+
+	printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt);
+
+	keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0);
+
+	if (keys == NULL) {
+		printf("RTE_ZMALLOC failed\n");
+		return -1;
+	}
+
+	index = 0;
+	for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
+		for (j = 0; j < ceil(SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++)
+			keys[index++] = i;
+	}
+
+	/* shuffle the keys */
+	for (i = index - 1; i > 0; i--) {
+		uint32_t swap_idx = rte_rand() % i;
+		uint32_t tmp_key = keys[i];
+
+		keys[i] = keys[swap_idx];
+		keys[swap_idx] = tmp_key;
+	}
+
+	params.key_len = 4;
+	params.name = "test_member_sketch";
+	params.type = RTE_MEMBER_TYPE_SKETCH;
+	params.error_rate = SKETCH_ERROR_RATE;
+	params.sample_rate = SKETCH_SAMPLE_RATE;
+	params.extra_flag = 0;
+	params.top_k = TOP_K;
+	params.prim_hash_seed = rte_rdtsc();
+	int reset_test = 0;
+
+	printf("Default sketching params: Error Rate: [%f]\tSample Rate: [%f]\tTopK: [%d]\n",
+			SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K);
+
+	printf("\n[Sketch with Fixed Sampling Rate Mode]\n");
+	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
+		return -1;
+
+	params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED;
+	printf("\n[Sketch with Always Bounded Mode]\n");
+	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
+		return -1;
+
+	count_byte = 1;
+	params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE;
+	printf("\n[Sketch with Packet Size Mode]\n");
+	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
+		return -1;
+
+	count_byte = 0;
+	params.extra_flag = 0;
+	reset_test = 1;
+	printf("\nreset sketch test\n");
+	if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0)
+		return -1;
+
+	return 0;
+}
+
 static int
 test_member(void)
 {
@@ -719,6 +973,10 @@  test_member(void)
 		return -1;
 	}
 
+	if (test_member_sketch() < 0) {
+		perform_free();
+		return -1;
+	}
 	perform_free();
 	return 0;
 }
diff --git a/app/test/test_member_perf.c b/app/test/test_member_perf.c
index 978db0020a..b7eb3e4c66 100644
--- a/app/test/test_member_perf.c
+++ b/app/test/test_member_perf.c
@@ -13,6 +13,7 @@ 
 #include <rte_random.h>
 #include <rte_memcpy.h>
 #include <rte_thash.h>
+#include <math.h>
 
 #ifdef RTE_EXEC_ENV_WINDOWS
 static int
@@ -26,7 +27,7 @@  test_member_perf(void)
 
 #include <rte_member.h>
 
-#define NUM_KEYSIZES 10
+#define NUM_KEYSIZES RTE_DIM(hashtest_key_lens)
 #define NUM_SHUFFLES 10
 #define MAX_KEYSIZE 64
 #define MAX_ENTRIES (1 << 19)
@@ -36,12 +37,23 @@  test_member_perf(void)
 #define BURST_SIZE 64
 #define VBF_FALSE_RATE 0.03
 
+/* for the heavy hitter detection */
+#define SKETCH_LARGEST_KEY_SIZE (1<<15)
+#define SKETCH_PKT_SIZE 16
+#define TOP_K 100
+#define SKETCH_ERROR_RATE 0.05
+#define SKETCH_SAMPLE_RATE 0.001
+#define NUM_ADDS (KEYS_TO_ADD * 20)
+
 static unsigned int test_socket_id;
 
 enum sstype {
 	HT = 0,
 	CACHE,
 	VBF,
+	SKETCH,
+	SKETCH_BOUNDED,
+	SKETCH_BYTE,
 	NUM_TYPE
 };
 
@@ -88,6 +100,7 @@  static member_set_t data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD];
 
 /* Array to store all input keys */
 static uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
+static uint8_t hh_keys[KEYS_TO_ADD][MAX_KEYSIZE];
 
 /* Shuffle the keys that have been added, so lookups will be totally random */
 static void
@@ -136,6 +149,10 @@  setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
 {
 	unsigned int i, j;
 	int num_duplicates;
+	int distinct_key = 0;
+	int count_down = SKETCH_LARGEST_KEY_SIZE;
+	uint32_t swap_idx;
+	uint8_t temp_key[MAX_KEYSIZE];
 
 	params->key_size = hashtest_key_lens[cycle];
 	params->cycle = cycle;
@@ -176,6 +193,22 @@  setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
 	/* Shuffle the random values again */
 	shuffle_input_keys(params);
 
+	for (i = 0; i < KEYS_TO_ADD; i++) {
+		if (count_down == 0) {
+			distinct_key++;
+			count_down = ceil(SKETCH_LARGEST_KEY_SIZE / (distinct_key + 1));
+		}
+		memcpy(hh_keys[i], keys[distinct_key], params->key_size);
+		count_down--;
+	}
+
+	for (i = KEYS_TO_ADD - 1; i > 0; i--) {
+		swap_idx = rte_rand() % i;
+		memcpy(temp_key, hh_keys[i], params->key_size);
+		memcpy(hh_keys[i], hh_keys[swap_idx], params->key_size);
+		memcpy(hh_keys[swap_idx], temp_key, params->key_size);
+	}
+
 	/* For testing miss lookup, we insert half and lookup the other half */
 	unsigned int entry_cnt, bf_key_cnt;
 	if (!miss) {
@@ -208,6 +241,44 @@  setup_keys_and_data(struct member_perf_params *params, unsigned int cycle,
 	params->setsum[VBF] = rte_member_create(&member_params);
 	if (params->setsum[VBF] == NULL)
 		fprintf(stderr, "VBF create fail\n");
+
+	member_params.name = "test_member_sketch";
+	member_params.key_len = params->key_size;
+	member_params.type = RTE_MEMBER_TYPE_SKETCH;
+	member_params.error_rate = SKETCH_ERROR_RATE;
+	member_params.sample_rate = SKETCH_SAMPLE_RATE;
+	member_params.extra_flag = 0;
+	member_params.top_k = TOP_K;
+	member_params.prim_hash_seed = rte_rdtsc();
+	params->setsum[SKETCH] = rte_member_create(&member_params);
+	if (params->setsum[SKETCH] == NULL)
+		fprintf(stderr, "sketch create fail\n");
+
+	member_params.name = "test_member_sketch_bounded";
+	member_params.key_len = params->key_size;
+	member_params.type = RTE_MEMBER_TYPE_SKETCH;
+	member_params.error_rate = SKETCH_ERROR_RATE;
+	member_params.sample_rate = SKETCH_SAMPLE_RATE;
+	member_params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED;
+	member_params.top_k = TOP_K;
+	member_params.prim_hash_seed = rte_rdtsc();
+	params->setsum[SKETCH_BOUNDED] = rte_member_create(&member_params);
+	if (params->setsum[SKETCH_BOUNDED] == NULL)
+		fprintf(stderr, "sketch create fail\n");
+
+	member_params.name = "test_member_sketch_byte";
+	member_params.key_len = params->key_size;
+	member_params.type = RTE_MEMBER_TYPE_SKETCH;
+	member_params.error_rate = SKETCH_ERROR_RATE;
+	member_params.sample_rate = SKETCH_SAMPLE_RATE;
+	member_params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE;
+	member_params.top_k = TOP_K;
+	member_params.prim_hash_seed = rte_rdtsc();
+	params->setsum[SKETCH_BYTE] = rte_member_create(&member_params);
+	if (params->setsum[SKETCH_BYTE] == NULL)
+		fprintf(stderr, "sketch create fail\n");
+
+
 	for (i = 0; i < NUM_TYPE; i++) {
 		if (params->setsum[i] == NULL)
 			return -1;
@@ -243,6 +314,39 @@  timed_adds(struct member_perf_params *params, int type)
 	return 0;
 }
 
+static int
+timed_adds_sketch(struct member_perf_params *params, int type)
+{
+	const uint64_t start_tsc = rte_rdtsc();
+	unsigned int i, j, a;
+	int32_t ret;
+
+	for (i = 0; i < NUM_ADDS / KEYS_TO_ADD; i++) {
+		for (j = 0; j < KEYS_TO_ADD; j++) {
+			if (type == SKETCH_BYTE)
+				ret = rte_member_add_byte_count(params->setsum[type],
+						&hh_keys[j], SKETCH_PKT_SIZE);
+			else
+				ret = rte_member_add(params->setsum[type], &hh_keys[j], 1);
+			if (ret < 0) {
+				printf("Error %d in rte_member_add - key=0x", ret);
+				for (a = 0; a < params->key_size; a++)
+					printf("%02x", hh_keys[j][a]);
+				printf("type: %d\n", type);
+
+				return -1;
+			}
+		}
+	}
+
+	const uint64_t end_tsc = rte_rdtsc();
+	const uint64_t time_taken = end_tsc - start_tsc;
+
+	cycles[type][params->cycle][ADD] = time_taken / NUM_ADDS;
+
+	return 0;
+}
+
 static int
 timed_lookups(struct member_perf_params *params, int type)
 {
@@ -279,6 +383,36 @@  timed_lookups(struct member_perf_params *params, int type)
 	return 0;
 }
 
+static int
+timed_lookups_sketch(struct member_perf_params *params, int type)
+{
+	unsigned int i, j;
+
+	false_data[type][params->cycle] = 0;
+
+	const uint64_t start_tsc = rte_rdtsc();
+	member_set_t result;
+	int ret;
+
+	for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) {
+		for (j = 0; j < KEYS_TO_ADD; j++) {
+			ret = rte_member_lookup(params->setsum[type], &hh_keys[j],
+						&result);
+			if (ret < 0) {
+				printf("lookup wrong internally");
+				return -1;
+			}
+		}
+	}
+
+	const uint64_t end_tsc = rte_rdtsc();
+	const uint64_t time_taken = end_tsc - start_tsc;
+
+	cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS;
+
+	return 0;
+}
+
 static int
 timed_lookups_bulk(struct member_perf_params *params, int type)
 {
@@ -531,7 +665,7 @@  run_all_tbl_perf_tests(void)
 			printf("Could not create keys/data/table\n");
 			return -1;
 		}
-		for (j = 0; j < NUM_TYPE; j++) {
+		for (j = 0; j < SKETCH; j++) {
 
 			if (timed_adds(&params, j) < 0)
 				return exit_with_fail("timed_adds", &params,
@@ -562,6 +696,17 @@  run_all_tbl_perf_tests(void)
 
 			/* Print a dot to show progress on operations */
 		}
+
+		for (j = SKETCH; j < NUM_TYPE; j++) {
+			if (timed_adds_sketch(&params, j) < 0)
+				return exit_with_fail
+					("timed_adds_sketch", &params, i, j);
+
+			if (timed_lookups_sketch(&params, j) < 0)
+				return exit_with_fail
+					("timed_lookups_sketch", &params, i, j);
+		}
+
 		printf(".");
 		fflush(stdout);
 
@@ -574,7 +719,7 @@  run_all_tbl_perf_tests(void)
 			printf("Could not create keys/data/table\n");
 			return -1;
 			}
-		for (j = 0; j < NUM_TYPE; j++) {
+		for (j = 0; j < SKETCH; j++) {
 			if (timed_miss_lookup(&params, j) < 0)
 				return exit_with_fail("timed_miss_lookup",
 						&params, i, j);
@@ -605,7 +750,7 @@  run_all_tbl_perf_tests(void)
 			"fr_multi_bulk", "false_positive_rate");
 	/* Key size not influence False rate so just print out one key size */
 	for (i = 0; i < 1; i++) {
-		for (j = 0; j < NUM_TYPE; j++) {
+		for (j = 0; j < SKETCH; j++) {
 			printf("%-18d", hashtest_key_lens[i]);
 			printf("%-18d", j);
 			printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS);