This patch adds functional and performance tests for sketch mode of
membership library.
Signed-off-by: Yipeng Wang <yipeng1.w...@intel.com>
Signed-off-by: Leyi Rong <leyi.r...@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(¶ms);
+ 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(¶ms, j) < 0)
return exit_with_fail("timed_adds", ¶ms,
@@ -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(¶ms, j) < 0)
+ return exit_with_fail
+ ("timed_adds_sketch", ¶ms, i, j);
+
+ if (timed_lookups_sketch(¶ms, j) < 0)
+ return exit_with_fail
+ ("timed_lookups_sketch", ¶ms, 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(¶ms, j) < 0)
return exit_with_fail("timed_miss_lookup",
¶ms, 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);
--
2.25.1
