@@ -7,6 +7,42 @@ if is_windows
subdir_done()
endif
-sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c')
+sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c', 'rte_member_sketch.c')
headers = files('rte_member.h')
deps += ['hash']
+includes += include_directories('../hash', '../ring')
+
+# compile AVX512 version if:
+# we are building 64-bit binary AND binutils can generate proper code
+if dpdk_conf.has('RTE_ARCH_X86_64') and binutils_ok
+ # compile AVX512 version if either:
+ # a. we have AVX512 supported in minimum instruction set
+ # baseline
+ # b. it's not minimum instruction set, but supported by
+ # compiler
+ #
+ # in former case, just add avx512 C file to files list
+ # in latter case, compile c file to static lib, using correct
+ # compiler flags, and then have the .o file from static lib
+ # linked into main lib.
+ sketch_avx512_cpu_support = (
+ cc.get_define('__AVX512F__', args: machine_args) != ''
+ )
+
+ if sketch_avx512_cpu_support == true
+ cflags += ['-DCC_AVX512_SUPPORT']
+ if cc.has_multi_arguments('-mavx512f', '-mavx512dq', '-mavx512ifma')
+ cflags += ['-mavx512f', '-mavx512dq', '-mavx512ifma']
+ endif
+ sources += files('rte_member_sketch_avx512.c')
+ elif cc.has_multi_arguments('-mavx512f', '-mavx512dq', '-mavx512ifma')
+ cflags += ['-DCC_AVX512_SUPPORT']
+ cflags += ['-mavx512f', '-mavx512dq', '-mavx512ifma']
+ sketch_avx512_tmp = static_library('sketch_avx512_tmp',
+ 'rte_member_sketch_avx512.c',
+ include_directories: includes,
+ dependencies: static_rte_eal,
+ c_args: cflags)
+ objs += sketch_avx512_tmp.extract_objects('rte_member_sketch_avx512.c')
+ endif
+endif
@@ -9,10 +9,12 @@
#include <rte_malloc.h>
#include <rte_errno.h>
#include <rte_tailq.h>
+#include <rte_ring_elem.h>
#include "rte_member.h"
#include "rte_member_ht.h"
#include "rte_member_vbf.h"
+#include "rte_member_sketch.h"
TAILQ_HEAD(rte_member_list, rte_tailq_entry);
static struct rte_tailq_elem rte_member_tailq = {
@@ -72,6 +74,9 @@ rte_member_free(struct rte_member_setsum *setsum)
case RTE_MEMBER_TYPE_VBF:
rte_member_free_vbf(setsum);
break;
+ case RTE_MEMBER_TYPE_SKETCH:
+ rte_member_free_sketch(setsum);
+ break;
default:
break;
}
@@ -86,6 +91,8 @@ rte_member_create(const struct rte_member_parameters *params)
struct rte_member_list *member_list;
struct rte_member_setsum *setsum;
int ret;
+ char ring_name[RTE_RING_NAMESIZE];
+ struct rte_ring *sketch_key_ring = NULL;
if (params == NULL) {
rte_errno = EINVAL;
@@ -100,6 +107,16 @@ rte_member_create(const struct rte_member_parameters *params)
return NULL;
}
+ if (params->type == RTE_MEMBER_TYPE_SKETCH) {
+ snprintf(ring_name, sizeof(ring_name), "SK_%s", params->name);
+ sketch_key_ring = rte_ring_create_elem(ring_name, sizeof(uint32_t),
+ rte_align32pow2(params->top_k), params->socket_id, 0);
+ if (sketch_key_ring == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Ring Memory allocation failed\n");
+ return NULL;
+ }
+ }
+
member_list = RTE_TAILQ_CAST(rte_member_tailq.head, rte_member_list);
rte_mcfg_tailq_write_lock();
@@ -145,6 +162,9 @@ rte_member_create(const struct rte_member_parameters *params)
case RTE_MEMBER_TYPE_VBF:
ret = rte_member_create_vbf(setsum, params);
break;
+ case RTE_MEMBER_TYPE_SKETCH:
+ ret = rte_member_create_sketch(setsum, params, sketch_key_ring);
+ break;
default:
goto error_unlock_exit;
}
@@ -162,6 +182,7 @@ rte_member_create(const struct rte_member_parameters *params)
error_unlock_exit:
rte_free(te);
rte_free(setsum);
+ rte_ring_free(sketch_key_ring);
rte_mcfg_tailq_write_unlock();
return NULL;
}
@@ -178,6 +199,23 @@ rte_member_add(const struct rte_member_setsum *setsum, const void *key,
return rte_member_add_ht(setsum, key, set_id);
case RTE_MEMBER_TYPE_VBF:
return rte_member_add_vbf(setsum, key, set_id);
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_add_sketch(setsum, key, set_id);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_add_byte_count(const struct rte_member_setsum *setsum,
+ const void *key, uint32_t byte_count)
+{
+ if (setsum == NULL || key == NULL || byte_count == 0)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_add_sketch_byte_count(setsum, key, byte_count);
default:
return -EINVAL;
}
@@ -195,6 +233,8 @@ rte_member_lookup(const struct rte_member_setsum *setsum, const void *key,
return rte_member_lookup_ht(setsum, key, set_id);
case RTE_MEMBER_TYPE_VBF:
return rte_member_lookup_vbf(setsum, key, set_id);
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_lookup_sketch(setsum, key, set_id);
default:
return -EINVAL;
}
@@ -261,6 +301,36 @@ rte_member_lookup_multi_bulk(const struct rte_member_setsum *setsum,
}
}
+int
+rte_member_query_count(const struct rte_member_setsum *setsum,
+ const void *key, uint64_t *output)
+{
+ if (setsum == NULL || key == NULL || output == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_query_sketch(setsum, key, output);
+ default:
+ return -EINVAL;
+ }
+}
+
+int
+rte_member_report_heavyhitter(const struct rte_member_setsum *setsum,
+ void **key, uint64_t *count)
+{
+ if (setsum == NULL || key == NULL || count == NULL)
+ return -EINVAL;
+
+ switch (setsum->type) {
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_report_heavyhitter_sketch(setsum, key, count);
+ default:
+ return -EINVAL;
+ }
+}
+
int
rte_member_delete(const struct rte_member_setsum *setsum, const void *key,
member_set_t set_id)
@@ -272,6 +342,8 @@ rte_member_delete(const struct rte_member_setsum *setsum, const void *key,
case RTE_MEMBER_TYPE_HT:
return rte_member_delete_ht(setsum, key, set_id);
/* current vBF implementation does not support delete function */
+ case RTE_MEMBER_TYPE_SKETCH:
+ return rte_member_delete_sketch(setsum, key);
case RTE_MEMBER_TYPE_VBF:
default:
return -EINVAL;
@@ -290,6 +362,9 @@ rte_member_reset(const struct rte_member_setsum *setsum)
case RTE_MEMBER_TYPE_VBF:
rte_member_reset_vbf(setsum);
return;
+ case RTE_MEMBER_TYPE_SKETCH:
+ rte_member_reset_sketch(setsum);
+ return;
default:
return;
}
@@ -39,6 +39,18 @@
* | | | not overwrite | |
* | | | existing key. | |
* +----------+---------------------+----------------+-------------------------+
+ * +==========+=============================+
+ * | type | sketch |
+ * +==========+=============================+
+ * |structure | counting bloom filter array |
+ * +----------+-----------------------------+
+ * |set id | 1: heavy set, 0: light set |
+ * | | |
+ * +----------+-----------------------------+
+ * |usages & | count size of a flow, |
+ * |properties| used for heavy hitter |
+ * | | detection. |
+ * +----------+-----------------------------+
* -->
*/
@@ -50,6 +62,8 @@ extern "C" {
#endif
#include <stdint.h>
+#include <stdbool.h>
+#include <inttypes.h>
#include <rte_common.h>
@@ -65,6 +79,20 @@ typedef uint16_t member_set_t;
#define RTE_MEMBER_BUCKET_ENTRIES 16
/** Maximum number of characters in setsum name. */
#define RTE_MEMBER_NAMESIZE 32
+/** Max value of the random number */
+#define RTE_RAND_MAX ~0LLU
+/**
+ * As packets skipped in the sampling-based algorithm, the accounting
+ * results accuracy is not guaranteed in the start stage. There should
+ * be a "convergence time" to achieve the accuracy after receiving enough
+ * packets.
+ * For sketch, use the flag if prefer always bounded mode, which only
+ * starts sampling after receiving enough packets to keep the results
+ * accuracy always bounded.
+ */
+#define RTE_MEMBER_SKETCH_ALWAYS_BOUNDED 0x01
+/** For sketch, use the flag if to count packet size instead of packet count */
+#define RTE_MEMBER_SKETCH_COUNT_BYTE 0x02
/** @internal Hash function used by membership library. */
#if defined(RTE_ARCH_X86) || defined(__ARM_FEATURE_CRC32)
@@ -104,6 +132,7 @@ struct rte_member_parameters;
enum rte_member_setsum_type {
RTE_MEMBER_TYPE_HT = 0, /**< Hash table based set summary. */
RTE_MEMBER_TYPE_VBF, /**< Vector of bloom filters. */
+ RTE_MEMBER_TYPE_SKETCH,
RTE_MEMBER_NUM_TYPE
};
@@ -114,6 +143,19 @@ enum rte_member_sig_compare_function {
RTE_MEMBER_COMPARE_NUM
};
+/* sketch update function with different implementations. */
+typedef void (*sketch_update_fn_t)(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t count);
+
+/* sketch lookup function with different implementations. */
+typedef uint64_t (*sketch_lookup_fn_t)(const struct rte_member_setsum *ss,
+ const void *key);
+
+/* sketch delete function with different implementations. */
+typedef void (*sketch_delete_fn_t)(const struct rte_member_setsum *ss,
+ const void *key);
+
/** @internal setsummary structure. */
struct rte_member_setsum {
enum rte_member_setsum_type type; /* Type of the set summary. */
@@ -134,6 +176,21 @@ struct rte_member_setsum {
uint32_t bit_mask; /* Bit mask to get bit location in bf. */
uint32_t num_hashes; /* Number of hash values to index bf. */
+ /* Parameters for sketch */
+ float error_rate;
+ float sample_rate;
+ uint32_t num_col;
+ uint32_t num_row;
+ int always_bounded;
+ double converge_thresh;
+ uint32_t topk;
+ uint32_t count_byte;
+ uint64_t *hash_seeds;
+ sketch_update_fn_t sketch_update; /* Pointer to the sketch update function */
+ sketch_lookup_fn_t sketch_lookup; /* Pointer to the sketch lookup function */
+ sketch_delete_fn_t sketch_delete; /* Pointer to the sketch delete function */
+
+ void *runtime_var;
uint32_t mul_shift; /* vbf internal variable used during bit test. */
uint32_t div_shift; /* vbf internal variable used during bit test. */
@@ -143,6 +200,9 @@ struct rte_member_setsum {
/* Second cache line should start here. */
uint32_t socket_id; /* NUMA Socket ID for memory. */
char name[RTE_MEMBER_NAMESIZE]; /* Name of this set summary. */
+#ifdef RTE_ARCH_X86
+ bool use_avx512;
+#endif
} __rte_cache_aligned;
/**
@@ -261,8 +321,33 @@ struct rte_member_parameters {
*/
uint32_t sec_hash_seed;
+ /**
+ * For count(min) sketch data structure, error rate defines the accuracy
+ * required by the user. Higher accuracy leads to more memory usage, but
+ * the flow size is estimated more accurately.
+ */
+ float error_rate;
+
+ /**
+ * Sampling rate means the internal sample rate of the rows of the count
+ * min sketches. Lower sampling rate can reduce CPU overhead, but the
+ * data structure will require more time to converge statistically.
+ */
+ float sample_rate;
+
+ /**
+ * How many top heavy hitter to be reported. The library will internally
+ * keep the keys of heavy hitters for final report.
+ */
+ uint32_t top_k;
+
+ /**
+ * Extra flags that may passed in by user
+ */
+ uint32_t extra_flag;
+
int socket_id; /**< NUMA Socket ID for memory. */
-};
+} __rte_cache_aligned;
/**
* @warning
@@ -418,7 +503,7 @@ rte_member_lookup_multi_bulk(const struct rte_member_setsum *setsum,
* RTE_MEMBER_NO_MATCH by default is set as 0.
* For HT mode, the set_id has range as [1, 0x7FFF], MSB is reserved.
* For vBF mode the set id is limited by the num_set parameter when create
- * the set-summary.
+ * the set-summary. For sketch mode, this id is ignored.
* @return
* HT (cache mode) and vBF should never fail unless the set_id is not in the
* valid range. In such case -EINVAL is returned.
@@ -429,12 +514,72 @@ rte_member_lookup_multi_bulk(const struct rte_member_setsum *setsum,
* Return 0 for HT (cache mode) if the add does not cause
* eviction, return 1 otherwise. Return 0 for non-cache mode if success,
* -ENOSPC for full, and 1 if cuckoo eviction happens.
- * Always returns 0 for vBF mode.
+ * Always returns 0 for vBF mode and sketch.
*/
int
rte_member_add(const struct rte_member_setsum *setsum, const void *key,
member_set_t set_id);
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add the packet byte size into the sketch.
+ *
+ * @param setsum
+ * Pointer of a set-summary.
+ * @param key
+ * Pointer of the key to be added.
+ * @param byte_count
+ * Add the byte count of the packet into the sketch.
+ * @return
+ * Return -EINVAL for invalid parameters, otherwise return 0.
+ */
+int
+rte_member_add_byte_count(const struct rte_member_setsum *setsum,
+ const void *key, uint32_t byte_count);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Query packet count for a certain flow-key.
+ *
+ * @param setsum
+ * Pointer of a set-summary.
+ * @param key
+ * Pointer of the key to be added.
+ * @param count
+ * The output packet count or byte count.
+ * @return
+ * Return -EINVAL for invalid parameters.
+ */
+int
+rte_member_query_count(const struct rte_member_setsum *setsum,
+ const void *key, uint64_t *count);
+
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Report heavyhitter flow-keys into set-summary (SS).
+ *
+ * @param setsum
+ * Pointer of a set-summary.
+ * @param keys
+ * Pointer of the output top-k key array.
+ * @param counts
+ * Pointer of the output packet count or byte count array of the top-k keys.
+ * @return
+ * Return -EINVAL for invalid parameters. Return a positive integer indicate
+ * how many heavy hitters are reported.
+ */
+int
+rte_member_report_heavyhitter(const struct rte_member_setsum *setsum,
+ void **keys, uint64_t *counts);
+
+
/**
* @warning
* @b EXPERIMENTAL: this API may change without prior notice
new file mode 100644
@@ -0,0 +1,424 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ * Copyright(c) 2020, Alan Liu <zaoxingliu@gmail.com>
+ */
+
+#ifndef _RTE_MEMBER_HEAP_H_
+#define _RTE_MEMBER_HEAP_H_
+
+#include <rte_ring_elem.h>
+#include "rte_member.h"
+
+#define LCHILD(x) (2 * x + 1)
+#define RCHILD(x) (2 * x + 2)
+#define PARENT(x) ((x - 1) / 2)
+
+#define HASH_BKT_SIZE 16
+#define HASH_HP_MULTI 4
+#define HASH_RESIZE_MULTI 2
+
+struct hash_bkt {
+ uint16_t sig[HASH_BKT_SIZE];
+ uint16_t idx[HASH_BKT_SIZE];
+};
+
+struct hash {
+ uint16_t bkt_cnt;
+ uint16_t num_item;
+ uint32_t seed;
+ struct hash_bkt buckets[0];
+};
+
+struct node {
+ void *key;
+ uint64_t count;
+};
+
+struct minheap {
+ uint32_t key_len;
+ uint32_t size;
+ uint32_t socket;
+ struct hash *hashtable;
+ struct node *elem;
+};
+
+static int
+hash_table_insert(const void *key, int value, int key_len, struct hash *table)
+{
+ uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
+ uint16_t idx = hash % table->bkt_cnt;
+ uint16_t sig = hash >> 16;
+ int i;
+
+ for (i = 0; i < HASH_BKT_SIZE; i++) {
+ if (table->buckets[idx].idx[i] == 0) {
+ table->buckets[idx].idx[i] = value;
+ table->buckets[idx].sig[i] = sig;
+ table->num_item++;
+ return 0;
+ }
+ }
+
+ return -ENOMEM;
+}
+
+static int
+hash_table_update(const void *key, int old_value, int value, int key_len, struct hash *table)
+{
+ uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
+ uint16_t idx = hash % table->bkt_cnt;
+ uint16_t sig = hash >> 16;
+ int i;
+
+ for (i = 0; i < HASH_BKT_SIZE; i++) {
+ if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] == old_value) {
+ table->buckets[idx].idx[i] = value;
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+static int
+hash_table_del(const void *key, uint16_t value, int key_len, struct hash *table)
+{
+ uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
+ uint16_t idx = hash % table->bkt_cnt;
+ uint16_t sig = hash >> 16;
+ int i;
+
+ for (i = 0; i < HASH_BKT_SIZE; i++) {
+ if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] == value) {
+ table->buckets[idx].idx[i] = 0;
+ table->num_item--;
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+static int
+hash_table_lookup(const void *key, int key_len, struct minheap *hp)
+{
+ struct hash *table = hp->hashtable;
+ uint32_t hash = MEMBER_HASH_FUNC(key, key_len, table->seed);
+ uint16_t idx = hash % table->bkt_cnt;
+ uint16_t sig = hash >> 16;
+ int i;
+
+ for (i = 0; i < HASH_BKT_SIZE; i++) {
+ if (table->buckets[idx].sig[i] == sig && table->buckets[idx].idx[i] != 0) {
+ uint32_t hp_idx = table->buckets[idx].idx[i] - 1;
+
+ if (memcmp(hp->elem[hp_idx].key, key, hp->key_len) == 0)
+ return hp_idx;
+ }
+ }
+
+ return -ENOENT; /* key doesn't exist */
+}
+
+static int
+resize_hash_table(struct minheap *hp)
+{
+ uint32_t i;
+ uint32_t new_bkt_cnt;
+
+ while (1) {
+ new_bkt_cnt = hp->hashtable->bkt_cnt * HASH_RESIZE_MULTI;
+
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap HT load factor is [%f]\n",
+ hp->hashtable->num_item / ((float)hp->hashtable->bkt_cnt * HASH_BKT_SIZE));
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap HT resize happen!\n");
+ rte_free(hp->hashtable);
+ hp->hashtable = rte_zmalloc_socket(NULL, sizeof(struct hash) +
+ new_bkt_cnt * sizeof(struct hash_bkt),
+ RTE_CACHE_LINE_SIZE, hp->socket);
+
+ if (hp->hashtable == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap HT allocation failed\n");
+ return -ENOMEM;
+ }
+
+ hp->hashtable->bkt_cnt = new_bkt_cnt;
+
+ for (i = 0; i < hp->size; ++i) {
+ if (hash_table_insert(hp->elem[i].key,
+ i + 1, hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR,
+ "Sketch Minheap HT resize insert fail!\n");
+ break;
+ }
+ }
+ if (i == hp->size)
+ break;
+ }
+
+ return 0;
+}
+
+/* find the item in the given minheap */
+static int
+rte_member_minheap_find(struct minheap *hp, const void *key)
+{
+ int idx = hash_table_lookup(key, hp->key_len, hp);
+ return idx;
+}
+
+static int
+rte_member_minheap_init(struct minheap *heap, int size,
+ uint32_t socket, uint32_t seed)
+{
+ heap->elem = rte_zmalloc_socket(NULL, sizeof(struct node) * size,
+ RTE_CACHE_LINE_SIZE, socket);
+ if (heap->elem == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap elem allocation failed\n");
+ return -ENOMEM;
+ }
+
+ uint32_t hash_bkt_cnt = rte_align32pow2(size * HASH_HP_MULTI) / HASH_BKT_SIZE;
+
+ if (hash_bkt_cnt == 0)
+ hash_bkt_cnt = 1;
+
+ heap->hashtable = rte_zmalloc_socket(NULL, sizeof(struct hash) +
+ hash_bkt_cnt * sizeof(struct hash_bkt),
+ RTE_CACHE_LINE_SIZE, socket);
+
+ if (heap->hashtable == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap HT allocation failed\n");
+ rte_free(heap->elem);
+ return -ENOMEM;
+ }
+
+ heap->hashtable->seed = seed;
+ heap->hashtable->bkt_cnt = hash_bkt_cnt;
+ heap->socket = socket;
+
+ return 0;
+}
+
+/* swap the minheap nodes */
+static __rte_always_inline void
+rte_member_heap_swap(struct node *n1, struct node *n2)
+{
+ struct node temp = *n1;
+ *n1 = *n2;
+ *n2 = temp;
+}
+
+/* heapify function */
+static void
+rte_member_heapify(struct minheap *hp, uint32_t idx, bool update_hash)
+{
+ uint32_t smallest;
+
+ if (LCHILD(idx) < hp->size &&
+ hp->elem[LCHILD(idx)].count < hp->elem[idx].count)
+ smallest = LCHILD(idx);
+ else
+ smallest = idx;
+
+ if (RCHILD(idx) < hp->size &&
+ hp->elem[RCHILD(idx)].count < hp->elem[smallest].count)
+ smallest = RCHILD(idx);
+
+ if (smallest != idx) {
+ rte_member_heap_swap(&(hp->elem[idx]), &(hp->elem[smallest]));
+
+ if (update_hash) {
+ if (hash_table_update(hp->elem[smallest].key, idx + 1, smallest + 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return;
+ }
+
+ if (hash_table_update(hp->elem[idx].key, smallest + 1, idx + 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return;
+ }
+ }
+ rte_member_heapify(hp, smallest, update_hash);
+ }
+}
+
+/* insert a node into the minheap */
+static int
+rte_member_minheap_insert_node(struct minheap *hp, const void *key,
+ int counter, void *key_slot,
+ struct rte_ring *free_key_slot)
+{
+ struct node nd;
+ uint32_t slot_id;
+
+ if (rte_ring_sc_dequeue_elem(free_key_slot, &slot_id, sizeof(uint32_t)) != 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap get empty keyslot failed\n");
+ return -1;
+ }
+
+ nd.count = counter;
+ nd.key = RTE_PTR_ADD(key_slot, slot_id * hp->key_len);
+
+ memcpy(nd.key, key, hp->key_len);
+
+ uint32_t i = (hp->size)++;
+
+ while (i && nd.count < hp->elem[PARENT(i)].count) {
+ hp->elem[i] = hp->elem[PARENT(i)];
+ if (hash_table_update(hp->elem[i].key, PARENT(i) + 1, i + 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return -1;
+ }
+ i = PARENT(i);
+ }
+ hp->elem[i] = nd;
+
+ if (hash_table_insert(key, i + 1, hp->key_len, hp->hashtable) < 0) {
+ if (resize_hash_table(hp) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table resize failed\n");
+ return -1;
+ }
+ }
+
+ return 0;
+}
+
+/* delete a key from the minheap */
+static int
+rte_member_minheap_delete_node(struct minheap *hp, const void *key,
+ void *key_slot, struct rte_ring *free_key_slot)
+{
+ int idx = rte_member_minheap_find(hp, key);
+ uint32_t offset = RTE_PTR_DIFF(hp->elem[idx].key, key_slot) / hp->key_len;
+
+ if (hash_table_del(key, idx + 1, hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table delete failed\n");
+ return -1;
+ }
+
+ rte_ring_sp_enqueue_elem(free_key_slot, &offset, sizeof(uint32_t));
+
+ if (idx == (int)(hp->size - 1)) {
+ hp->size--;
+ return 0;
+ }
+
+ hp->elem[idx] = hp->elem[hp->size - 1];
+
+ if (hash_table_update(hp->elem[idx].key, hp->size, idx + 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return -1;
+ }
+ hp->size--;
+ rte_member_heapify(hp, idx, true);
+
+ return 0;
+}
+
+/* replace a min node with a new key. */
+static int
+rte_member_minheap_replace_node(struct minheap *hp,
+ const void *new_key,
+ int new_counter)
+{
+ struct node nd;
+ void *recycle_key = NULL;
+
+ recycle_key = hp->elem[0].key;
+
+ if (hash_table_del(recycle_key, 1, hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table delete failed\n");
+ return -1;
+ }
+
+ hp->elem[0] = hp->elem[hp->size - 1];
+
+ if (hash_table_update(hp->elem[0].key, hp->size, 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return -1;
+ }
+ hp->size--;
+
+ rte_member_heapify(hp, 0, true);
+
+ nd.count = new_counter;
+ nd.key = recycle_key;
+
+ memcpy(nd.key, new_key, hp->key_len);
+
+ uint32_t i = (hp->size)++;
+
+ while (i && nd.count < hp->elem[PARENT(i)].count) {
+ hp->elem[i] = hp->elem[PARENT(i)];
+ if (hash_table_update(hp->elem[i].key, PARENT(i) + 1, i + 1,
+ hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table update failed\n");
+ return -1;
+ }
+ i = PARENT(i);
+ }
+
+ hp->elem[i] = nd;
+
+ if (hash_table_insert(new_key, i + 1, hp->key_len, hp->hashtable) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table replace insert failed\n");
+ if (resize_hash_table(hp) < 0) {
+ RTE_MEMBER_LOG(ERR, "Minheap Hash Table replace resize failed\n");
+ return -1;
+ }
+ }
+
+ return 0;
+}
+
+/* sort the heap into a descending array */
+static void
+rte_member_heapsort(struct minheap *hp, struct node *result_array)
+{
+ struct minheap new_hp;
+
+ /* build a new heap for using the given array */
+ new_hp.size = hp->size;
+ new_hp.key_len = hp->key_len;
+ new_hp.elem = result_array;
+ memcpy(result_array, hp->elem, hp->size * sizeof(struct node));
+
+ /* sort the new heap */
+ while (new_hp.size > 1) {
+ rte_member_heap_swap(&(new_hp.elem[0]), &(new_hp.elem[new_hp.size - 1]));
+ new_hp.size--;
+ rte_member_heapify(&new_hp, 0, false);
+ }
+}
+
+static void
+rte_member_minheap_free(struct minheap *hp)
+{
+ if (hp == NULL)
+ return;
+
+ rte_free(hp->elem);
+ rte_free(hp->hashtable);
+}
+
+static void
+rte_member_minheap_reset(struct minheap *hp)
+{
+ if (hp == NULL)
+ return;
+
+ memset(hp->elem, 0, sizeof(struct node) * hp->size);
+ hp->size = 0;
+
+ memset((char *)hp->hashtable + sizeof(struct hash), 0,
+ hp->hashtable->bkt_cnt * sizeof(struct hash_bkt));
+ hp->hashtable->num_item = 0;
+}
+
+#endif /* _RTE_MEMBER_HEAP_H_ */
new file mode 100644
@@ -0,0 +1,594 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ * Copyright(c) 2020, Alan Liu <zaoxingliu@gmail.com>
+ */
+
+#include <math.h>
+#include <string.h>
+
+#include <rte_malloc.h>
+#include <rte_memory.h>
+#include <rte_errno.h>
+#include <rte_log.h>
+#include <rte_random.h>
+#include <rte_prefetch.h>
+#include <rte_ring_elem.h>
+
+#include "rte_member.h"
+#include "rte_member_sketch.h"
+#include "rte_member_heap.h"
+
+#ifdef CC_AVX512_SUPPORT
+#include "rte_member_sketch_avx512.h"
+#endif /* CC_AVX512_SUPPORT */
+
+struct sketch_runtime {
+ uint64_t pkt_cnt;
+ uint32_t until_next;
+ int converged;
+ struct minheap heap;
+ struct node *report_array;
+ void *key_slots;
+ struct rte_ring *free_key_slots;
+} __rte_cache_aligned;
+
+/*
+ * Geometric sampling to calculate how many packets needs to be
+ * skipped until next update. This method can mitigate the CPU
+ * overheads compared with coin-toss sampling.
+ */
+static uint32_t
+draw_geometric(const struct rte_member_setsum *ss)
+{
+ double rand = 1;
+
+ if (ss->sample_rate == 1)
+ return 1;
+
+ while (rand == 1 || rand == 0)
+ rand = (double) rte_rand() / (double)(RTE_RAND_MAX);
+
+ return (uint32_t)ceil(log(1 - rand) / log(1 - ss->sample_rate));
+}
+
+static void
+isort(uint64_t *array, int n)
+{
+ int i;
+
+ for (i = 1; i < n; i++) {
+ uint64_t t = array[i];
+ int j;
+
+ for (j = i - 1; j >= 0; j--) {
+ if (t < array[j])
+ array[j + 1] = array[j];
+ else
+ break;
+ }
+ array[j + 1] = t;
+ }
+}
+
+static __rte_always_inline void
+swap(uint64_t *a, uint64_t *b)
+{
+ uint64_t tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+static uint64_t
+medianof5(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e)
+{
+ if (a > b)
+ swap(&a, &b);
+ if (c > d)
+ swap(&c, &d);
+ if (a > c) {
+ if (d > e)
+ swap(&c, &e);
+ else {
+ swap(&c, &d);
+ swap(&d, &e);
+ }
+ } else {
+ if (b > e)
+ swap(&a, &e);
+ else {
+ swap(&a, &b);
+ swap(&b, &e);
+ }
+ }
+
+ if (a > c)
+ return a > d ? d : a;
+ else
+ return b > c ? c : b;
+}
+
+int
+rte_member_create_sketch(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params,
+ struct rte_ring *ring)
+{
+ struct sketch_runtime *runtime;
+ uint32_t num_col;
+ uint32_t i;
+
+ if (params->sample_rate == 0 || params->sample_rate > 1) {
+ rte_errno = EINVAL;
+ RTE_MEMBER_LOG(ERR,
+ "Membership Sketch created with invalid parameters\n");
+ return -EINVAL;
+ }
+
+ if (params->extra_flag & RTE_MEMBER_SKETCH_COUNT_BYTE)
+ ss->count_byte = 1;
+
+#ifdef RTE_ARCH_X86
+ if (ss->count_byte == 1 &&
+ rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_512 &&
+ rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) == 1 &&
+ rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512IFMA) == 1) {
+#ifdef CC_AVX512_SUPPORT
+ ss->use_avx512 = true;
+#else
+ ss->use_avx512 = false;
+#endif
+ }
+
+ if (ss->use_avx512 == true) {
+#ifdef CC_AVX512_SUPPORT
+ ss->num_row = NUM_ROW_VEC;
+ RTE_MEMBER_LOG(NOTICE,
+ "Membership Sketch AVX512 update/lookup/delete ops is selected\n");
+ ss->sketch_update = sketch_update_avx512;
+ ss->sketch_lookup = sketch_lookup_avx512;
+ ss->sketch_delete = sketch_delete_avx512;
+#endif
+ } else
+#endif
+ {
+ ss->num_row = NUM_ROW_SCALAR;
+ RTE_MEMBER_LOG(NOTICE,
+ "Membership Sketch SCALAR update/lookup/delete ops is selected\n");
+ ss->sketch_update = sketch_update_scalar;
+ ss->sketch_lookup = sketch_lookup_scalar;
+ ss->sketch_delete = sketch_delete_scalar;
+ }
+
+ ss->socket_id = params->socket_id;
+
+ if (ss->count_byte == 0)
+ num_col = 4.0 / params->error_rate / params->sample_rate;
+#ifdef RTE_ARCH_X86
+ else if (ss->use_avx512 == true)
+ num_col = rte_align32pow2(4.0 / params->error_rate);
+#endif
+ else
+ num_col = 4.0 / params->error_rate;
+
+ ss->table = rte_zmalloc_socket(NULL,
+ sizeof(uint64_t) * num_col * ss->num_row,
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (ss->table == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Table memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ ss->hash_seeds = rte_zmalloc_socket(NULL, sizeof(uint64_t) * ss->num_row,
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (ss->hash_seeds == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Hashseeds memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ ss->runtime_var = rte_zmalloc_socket(NULL, sizeof(struct sketch_runtime),
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (ss->runtime_var == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Runtime memory allocation failed\n");
+ rte_free(ss);
+ return -ENOMEM;
+ }
+ runtime = ss->runtime_var;
+
+ ss->num_col = num_col;
+ ss->sample_rate = params->sample_rate;
+ ss->prim_hash_seed = params->prim_hash_seed;
+ ss->sec_hash_seed = params->sec_hash_seed;
+ ss->error_rate = params->error_rate;
+ ss->topk = params->top_k;
+ ss->key_len = params->key_len;
+ runtime->heap.key_len = ss->key_len;
+
+ runtime->key_slots = rte_zmalloc_socket(NULL, ss->key_len * ss->topk,
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (runtime->key_slots == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Key Slots allocation failed\n");
+ goto error;
+ }
+
+ runtime->free_key_slots = ring;
+ for (i = 0; i < ss->topk; i++)
+ rte_ring_sp_enqueue_elem(runtime->free_key_slots,
+ &i, sizeof(uint32_t));
+
+ if (rte_member_minheap_init(&(runtime->heap), params->top_k,
+ ss->socket_id, params->prim_hash_seed) < 0) {
+ RTE_MEMBER_LOG(ERR, "Sketch Minheap allocation failed\n");
+ goto error_runtime;
+ }
+
+ runtime->report_array = rte_zmalloc_socket(NULL, sizeof(struct node) * ss->topk,
+ RTE_CACHE_LINE_SIZE, ss->socket_id);
+ if (runtime->report_array == NULL) {
+ RTE_MEMBER_LOG(ERR, "Sketch Runtime Report Array allocation failed\n");
+ goto error_runtime;
+ }
+
+ rte_srand(ss->prim_hash_seed);
+ for (i = 0; i < ss->num_row; i++)
+ ss->hash_seeds[i] = rte_rand();
+
+ if (params->extra_flag & RTE_MEMBER_SKETCH_ALWAYS_BOUNDED)
+ ss->always_bounded = 1;
+
+ if (ss->always_bounded) {
+ double delta = 1.0 / (pow(2, ss->num_row));
+
+ ss->converge_thresh = 10 * pow(ss->error_rate, -2.0) * sqrt(log(1 / delta));
+ }
+
+ RTE_MEMBER_LOG(DEBUG, "Sketch created, "
+ "the total memory required is %u Bytes\n", ss->num_col * ss->num_row * 8);
+
+ return 0;
+
+error_runtime:
+ rte_member_minheap_free(&runtime->heap);
+ rte_ring_free(runtime->free_key_slots);
+ rte_free(runtime->key_slots);
+error:
+ rte_free(runtime);
+ rte_free(ss);
+
+ return -ENOMEM;
+}
+
+uint64_t
+sketch_lookup_scalar(const struct rte_member_setsum *ss, const void *key)
+{
+ uint64_t *count_array = ss->table;
+ uint32_t col[ss->num_row];
+ uint64_t count_row[ss->num_row];
+ uint32_t cur_row;
+ uint64_t count;
+
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
+ col[cur_row] = MEMBER_HASH_FUNC(key, ss->key_len,
+ ss->hash_seeds[cur_row]) % ss->num_col;
+
+ rte_prefetch0(&count_array[cur_row * ss->num_col + col[cur_row]]);
+ }
+
+ /* if sample rate is 1, it is a regular count-min, we report the min */
+ if (ss->sample_rate == 1 || ss->count_byte == 1)
+ return count_min(ss, col);
+
+ memset(count_row, 0, sizeof(uint64_t) * ss->num_row);
+
+ /* otherwise we report the median number */
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++)
+ count_row[cur_row] = count_array[cur_row * ss->num_col + col[cur_row]];
+
+ if (ss->num_row == 5)
+ return medianof5(count_row[0], count_row[1],
+ count_row[2], count_row[3], count_row[4]);
+
+ isort(count_row, ss->num_row);
+
+ if (ss->num_row % 2 == 0) {
+ count = (count_row[ss->num_row / 2] + count_row[ss->num_row / 2 - 1]) / 2;
+ return count;
+ }
+ /* ss->num_row % 2 != 0 */
+ count = count_row[ss->num_row / 2];
+
+ return count;
+}
+
+void
+sketch_delete_scalar(const struct rte_member_setsum *ss, const void *key)
+{
+ uint32_t col[ss->num_row];
+ uint64_t *count_array = ss->table;
+ uint32_t cur_row;
+
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
+ col[cur_row] = MEMBER_HASH_FUNC(key, ss->key_len,
+ ss->hash_seeds[cur_row]) % ss->num_col;
+
+ /* set corresponding counter to 0 */
+ count_array[cur_row * ss->num_col + col[cur_row]] = 0;
+ }
+}
+
+int
+rte_member_query_sketch(const struct rte_member_setsum *ss,
+ const void *key,
+ uint64_t *output)
+{
+ uint64_t count = ss->sketch_lookup(ss, key);
+ *output = count;
+
+ return 0;
+}
+
+void
+rte_member_update_heap(const struct rte_member_setsum *ss)
+{
+ uint32_t i;
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+
+ for (i = 0; i < runtime_var->heap.size; i++) {
+ uint64_t count = ss->sketch_lookup(ss, runtime_var->heap.elem[i].key);
+
+ runtime_var->heap.elem[i].count = count;
+ }
+}
+
+int
+rte_member_report_heavyhitter_sketch(const struct rte_member_setsum *setsum,
+ void **key,
+ uint64_t *count)
+{
+ uint32_t i;
+ struct sketch_runtime *runtime_var = setsum->runtime_var;
+
+ rte_member_update_heap(setsum);
+ rte_member_heapsort(&(runtime_var->heap), runtime_var->report_array);
+
+ for (i = 0; i < runtime_var->heap.size; i++) {
+ key[i] = runtime_var->report_array[i].key;
+ count[i] = runtime_var->report_array[i].count;
+ }
+
+ return runtime_var->heap.size;
+}
+
+int
+rte_member_lookup_sketch(const struct rte_member_setsum *ss,
+ const void *key, member_set_t *set_id)
+{
+ uint64_t count = ss->sketch_lookup(ss, key);
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+
+ if (runtime_var->heap.size > 0 && count >= runtime_var->heap.elem[0].count)
+ *set_id = 1;
+ else
+ *set_id = 0;
+
+ if (count == 0)
+ return 0;
+ else
+ return 1;
+}
+
+static void
+should_converge(const struct rte_member_setsum *ss)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+
+ /* For count min sketch - L1 norm */
+ if (runtime_var->pkt_cnt > ss->converge_thresh) {
+ runtime_var->converged = 1;
+ RTE_MEMBER_LOG(DEBUG, "Sketch converged, begin sampling "
+ "from key count %"PRIu64"\n",
+ runtime_var->pkt_cnt);
+ }
+}
+
+static void
+sketch_update_row(const struct rte_member_setsum *ss, const void *key,
+ uint32_t count, uint32_t cur_row)
+{
+ uint64_t *count_array = ss->table;
+ uint32_t col = MEMBER_HASH_FUNC(key, ss->key_len,
+ ss->hash_seeds[cur_row]) % ss->num_col;
+
+ /* sketch counter update */
+ count_array[cur_row * ss->num_col + col] +=
+ ceil(count / (ss->sample_rate));
+}
+
+void
+sketch_update_scalar(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t count)
+{
+ uint64_t *count_array = ss->table;
+ uint32_t col;
+ uint32_t cur_row;
+
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
+ col = MEMBER_HASH_FUNC(key, ss->key_len,
+ ss->hash_seeds[cur_row]) % ss->num_col;
+ count_array[cur_row * ss->num_col + col] += count;
+ }
+}
+
+static void
+heap_update(const struct rte_member_setsum *ss, const void *key)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+ uint64_t key_cnt = 0;
+ int found;
+
+ /* We also update the heap for this key */
+ key_cnt = ss->sketch_lookup(ss, key);
+ if (key_cnt > runtime_var->heap.elem[0].count) {
+ found = rte_member_minheap_find(&runtime_var->heap, key);
+ /* the key is found in the top-k heap */
+ if (found >= 0) {
+ if (runtime_var->heap.elem[found].count < key_cnt)
+ rte_member_heapify(&runtime_var->heap, found, true);
+
+ runtime_var->heap.elem[found].count = key_cnt;
+ } else if (runtime_var->heap.size < ss->topk) {
+ rte_member_minheap_insert_node(&runtime_var->heap, key,
+ key_cnt, runtime_var->key_slots, runtime_var->free_key_slots);
+ } else {
+ rte_member_minheap_replace_node(&runtime_var->heap, key, key_cnt);
+ }
+ } else if (runtime_var->heap.size < ss->topk) {
+ found = rte_member_minheap_find(&runtime_var->heap, key);
+ if (found >= 0) {
+ if (runtime_var->heap.elem[found].count < key_cnt)
+ rte_member_heapify(&runtime_var->heap, found, true);
+
+ runtime_var->heap.elem[found].count = key_cnt;
+ } else
+ rte_member_minheap_insert_node(&runtime_var->heap, key,
+ key_cnt, runtime_var->key_slots, runtime_var->free_key_slots);
+ }
+}
+
+/*
+ * Add a single packet into the sketch.
+ * Sketch value is meatured by packet numbers in this mode.
+ */
+int
+rte_member_add_sketch(const struct rte_member_setsum *ss,
+ const void *key,
+ __rte_unused member_set_t set_id)
+{
+ uint32_t cur_row;
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+ uint32_t *until_next = &(runtime_var->until_next);
+
+ /*
+ * If sketch is measured by byte count,
+ * the rte_member_add_sketch_byte_count routine should be used.
+ */
+ if (ss->count_byte == 1) {
+ RTE_MEMBER_LOG(ERR, "Sketch is Byte Mode, "
+ "should use rte_member_add_byte_count()!\n");
+ return -EINVAL;
+ }
+
+ if (ss->sample_rate == 1) {
+ ss->sketch_update(ss, key, 1);
+ heap_update(ss, key);
+ return 0;
+ }
+
+ /* convergence stage if it's needed */
+ if (ss->always_bounded && !runtime_var->converged) {
+ ss->sketch_update(ss, key, 1);
+
+ if (!((++runtime_var->pkt_cnt) & (INTERVAL - 1)))
+ should_converge(ss);
+
+ heap_update(ss, key);
+ return 0;
+ }
+
+ /* should we skip this packet */
+ if (*until_next >= ss->num_row) {
+ *until_next -= ss->num_row;
+ return 0;
+ }
+ cur_row = *until_next;
+ do {
+ sketch_update_row(ss, key, 1, cur_row);
+ *until_next = draw_geometric(ss);
+ if (cur_row + *until_next >= ss->num_row)
+ break;
+ cur_row += *until_next;
+ } while (1);
+
+ *until_next -= (ss->num_row - cur_row);
+
+ heap_update(ss, key);
+
+ return 0;
+}
+
+/*
+ * Add the byte count of the packet into the sketch.
+ * Sketch value is meatured by byte count numbers in this mode.
+ */
+int
+rte_member_add_sketch_byte_count(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t byte_count)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+ uint32_t *until_next = &(runtime_var->until_next);
+
+ /* should not call this API if not in count byte mode */
+ if (ss->count_byte == 0) {
+ RTE_MEMBER_LOG(ERR, "Sketch is Pkt Mode, "
+ "should use rte_member_add()!\n");
+ return -EINVAL;
+ }
+
+ /* there's specific optimization for the sketch update */
+ ss->sketch_update(ss, key, byte_count);
+
+ if (*until_next != 0) {
+ *until_next = *until_next - 1;
+ return 0;
+ }
+
+ *until_next = draw_geometric(ss) - 1;
+
+ heap_update(ss, key);
+
+ return 0;
+}
+
+int
+rte_member_delete_sketch(const struct rte_member_setsum *ss,
+ const void *key)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+ int found;
+
+ found = rte_member_minheap_find(&runtime_var->heap, key);
+ if (found < 0)
+ return -1;
+
+ ss->sketch_delete(ss, key);
+
+ return rte_member_minheap_delete_node
+ (&runtime_var->heap, key, runtime_var->key_slots, runtime_var->free_key_slots);
+}
+
+void
+rte_member_free_sketch(struct rte_member_setsum *ss)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+
+ rte_free(ss->table);
+ rte_member_minheap_free(&runtime_var->heap);
+ rte_free(runtime_var->key_slots);
+ rte_ring_free(runtime_var->free_key_slots);
+ rte_free(runtime_var);
+}
+
+void
+rte_member_reset_sketch(const struct rte_member_setsum *ss)
+{
+ struct sketch_runtime *runtime_var = ss->runtime_var;
+ uint64_t *sketch = ss->table;
+ uint32_t i;
+
+ memset(sketch, 0, sizeof(uint64_t) * ss->num_col * ss->num_row);
+ rte_member_minheap_reset(&runtime_var->heap);
+ rte_ring_reset(runtime_var->free_key_slots);
+
+ for (i = 0; i < ss->topk; i++)
+ rte_ring_sp_enqueue_elem(runtime_var->free_key_slots, &i, sizeof(uint32_t));
+}
new file mode 100644
@@ -0,0 +1,97 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2017 Intel Corporation
+ */
+
+#ifndef _RTE_MEMBER_SKETCH_H_
+#define _RTE_MEMBER_SKETCH_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_vect.h>
+#include <rte_ring_elem.h>
+
+#define NUM_ROW_SCALAR 5
+#define INTERVAL (1 << 15)
+
+#if !RTE_IS_POWER_OF_2(INTERVAL)
+#error sketch INTERVAL macro must be a power of 2
+#endif
+
+int
+rte_member_create_sketch(struct rte_member_setsum *ss,
+ const struct rte_member_parameters *params,
+ struct rte_ring *r);
+
+int
+rte_member_lookup_sketch(const struct rte_member_setsum *setsum,
+ const void *key, member_set_t *set_id);
+
+int
+rte_member_add_sketch(const struct rte_member_setsum *setsum,
+ const void *key,
+ member_set_t set_id);
+
+int
+rte_member_add_sketch_byte_count(const struct rte_member_setsum *ss,
+ const void *key, uint32_t byte_count);
+
+void
+sketch_update_scalar(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t count);
+
+uint64_t
+sketch_lookup_scalar(const struct rte_member_setsum *ss,
+ const void *key);
+
+void
+sketch_delete_scalar(const struct rte_member_setsum *ss,
+ const void *key);
+
+int
+rte_member_delete_sketch(const struct rte_member_setsum *setsum,
+ const void *key);
+
+int
+rte_member_query_sketch(const struct rte_member_setsum *setsum,
+ const void *key, uint64_t *output);
+
+void
+rte_member_free_sketch(struct rte_member_setsum *ss);
+
+void
+rte_member_reset_sketch(const struct rte_member_setsum *setsum);
+
+int
+rte_member_report_heavyhitter_sketch(const struct rte_member_setsum *setsum,
+ void **key, uint64_t *count);
+
+void
+rte_member_update_heap(const struct rte_member_setsum *ss);
+
+static __rte_always_inline uint64_t
+count_min(const struct rte_member_setsum *ss, const uint32_t *hash_results)
+{
+ uint64_t *count_array = ss->table;
+ uint64_t count;
+ uint32_t cur_row;
+ uint64_t min = UINT64_MAX;
+
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
+ uint64_t cnt = count_array[cur_row * ss->num_col + hash_results[cur_row]];
+
+ if (cnt < min)
+ min = cnt;
+ }
+ count = min;
+
+ return count;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_SKETCH_H_ */
new file mode 100644
@@ -0,0 +1,69 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ */
+
+#include "rte_member_sketch_avx512.h"
+
+__rte_always_inline void
+sketch_update_avx512(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t count)
+{
+ uint64_t *count_array = ss->table;
+ uint32_t num_col = ss->num_col;
+ uint32_t key_len = ss->key_len;
+ __m256i v_row_base;
+ __m256i v_hash_result;
+ __m512i current_sketch;
+ __m512i updated_sketch;
+ __m512i v_count;
+
+ const __m256i v_idx = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);
+ const __m256i v_col = _mm256_set1_epi32(num_col);
+
+ /* compute the hash result parallelly */
+ v_hash_result = rte_xxh64_sketch_avx512
+ (key, key_len, *(__m512i *)ss->hash_seeds, num_col);
+ v_row_base = _mm256_mullo_epi32(v_idx, v_col);
+ v_hash_result = _mm256_add_epi32(v_row_base, v_hash_result);
+
+ current_sketch =
+ _mm512_i32gather_epi64(v_hash_result, count_array, 8);
+ v_count = _mm512_set1_epi64(count);
+ updated_sketch = _mm512_add_epi64(current_sketch, v_count);
+ _mm512_i32scatter_epi64
+ ((void *)count_array, v_hash_result, updated_sketch, 8);
+}
+
+uint64_t
+sketch_lookup_avx512(const struct rte_member_setsum *ss, const void *key)
+{
+ uint32_t col[ss->num_row];
+
+ /* currently only for sketch byte count mode */
+ __m256i v_hash_result = rte_xxh64_sketch_avx512
+ (key, ss->key_len, *(__m512i *)ss->hash_seeds, ss->num_col);
+ _mm256_storeu_si256((__m256i *)col, v_hash_result);
+
+ return count_min(ss, col);
+}
+
+void
+sketch_delete_avx512(const struct rte_member_setsum *ss, const void *key)
+{
+ uint32_t col[ss->num_row];
+ uint64_t *count_array = ss->table;
+ uint64_t min = UINT64_MAX;
+ uint32_t cur_row;
+
+ __m256i v_hash_result = rte_xxh64_sketch_avx512
+ (key, ss->key_len, *(__m512i *)ss->hash_seeds,
+ RTE_ALIGN_FLOOR(ss->num_col, 32));
+ _mm256_storeu_si256((__m256i *)col, v_hash_result);
+
+ min = count_min(ss, col);
+
+ /* subtract the min value from all the counters */
+ for (cur_row = 0; cur_row < ss->num_row; cur_row++)
+ count_array[cur_row * ss->num_col + col[cur_row]] -= min;
+}
new file mode 100644
@@ -0,0 +1,36 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ */
+
+#ifndef _RTE_MEMBER_SKETCH_AVX512_H_
+#define _RTE_MEMBER_SKETCH_AVX512_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_vect.h>
+#include "rte_member.h"
+#include "rte_member_sketch.h"
+#include "rte_xxh64_avx512.h"
+
+#define NUM_ROW_VEC 8
+
+void
+sketch_update_avx512(const struct rte_member_setsum *ss,
+ const void *key,
+ uint32_t count);
+
+uint64_t
+sketch_lookup_avx512(const struct rte_member_setsum *ss,
+ const void *key);
+
+void
+sketch_delete_avx512(const struct rte_member_setsum *ss,
+ const void *key);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_MEMBER_SKETCH_AVX512_H_ */
new file mode 100644
@@ -0,0 +1,117 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2020 Intel Corporation
+ */
+
+#ifndef _RTE_XXH64_AVX512_H_
+#define _RTE_XXH64_AVX512_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_common.h>
+#include <immintrin.h>
+
+/* 0b1001111000110111011110011011000110000101111010111100101010000111 */
+static const uint64_t PRIME64_1 = 0x9E3779B185EBCA87ULL;
+/* 0b1100001010110010101011100011110100100111110101001110101101001111 */
+static const uint64_t PRIME64_2 = 0xC2B2AE3D27D4EB4FULL;
+/* 0b0001011001010110011001111011000110011110001101110111100111111001 */
+static const uint64_t PRIME64_3 = 0x165667B19E3779F9ULL;
+/* 0b1000010111101011110010100111011111000010101100101010111001100011 */
+static const uint64_t PRIME64_4 = 0x85EBCA77C2B2AE63ULL;
+/* 0b0010011111010100111010110010111100010110010101100110011111000101 */
+static const uint64_t PRIME64_5 = 0x27D4EB2F165667C5ULL;
+
+static __rte_always_inline __m512i
+xxh64_round_avx512(__m512i hash, __m512i input)
+{
+ hash = _mm512_madd52lo_epu64(hash,
+ input,
+ _mm512_set1_epi64(PRIME64_2));
+
+ hash = _mm512_rol_epi64(hash, 31);
+
+ return hash;
+}
+
+static __rte_always_inline __m512i
+xxh64_fmix_avx512(__m512i hash)
+{
+ hash = _mm512_xor_si512(hash, _mm512_srli_epi64(hash, 33));
+
+ return hash;
+}
+
+static __rte_always_inline __m256i
+rte_xxh64_sketch_avx512(const void *key, uint32_t key_len,
+ __m512i v_seed, uint32_t modulo)
+{
+ __m512i v_prime64_5, v_hash;
+ size_t remaining = key_len;
+ size_t offset = 0;
+ __m512i input;
+
+ v_prime64_5 = _mm512_set1_epi64(PRIME64_5);
+ v_hash = _mm512_add_epi64
+ (_mm512_add_epi64(v_seed, v_prime64_5),
+ _mm512_set1_epi64(key_len));
+
+ while (remaining >= 8) {
+ input = _mm512_set1_epi64(*(uint64_t *)RTE_PTR_ADD(key, offset));
+ v_hash = _mm512_xor_epi64(v_hash,
+ xxh64_round_avx512(_mm512_setzero_si512(), input));
+ v_hash = _mm512_madd52lo_epu64(_mm512_set1_epi64(PRIME64_4),
+ v_hash,
+ _mm512_set1_epi64(PRIME64_1));
+
+ remaining -= 8;
+ offset += 8;
+ }
+
+ if (remaining >= 4) {
+ input = _mm512_set1_epi64
+ (*(uint32_t *)RTE_PTR_ADD(key, offset));
+ v_hash = _mm512_xor_epi64(v_hash,
+ _mm512_mullo_epi64(input,
+ _mm512_set1_epi64(PRIME64_1)));
+ v_hash = _mm512_madd52lo_epu64
+ (_mm512_set1_epi64(PRIME64_3),
+ _mm512_rol_epi64(v_hash, 23),
+ _mm512_set1_epi64(PRIME64_2));
+
+ offset += 4;
+ remaining -= 4;
+ }
+
+ while (remaining != 0) {
+ input = _mm512_set1_epi64
+ (*(uint8_t *)RTE_PTR_ADD(key, offset));
+ v_hash = _mm512_xor_epi64(v_hash,
+ _mm512_mullo_epi64(input,
+ _mm512_set1_epi64(PRIME64_5)));
+ v_hash = _mm512_mullo_epi64
+ (_mm512_rol_epi64(v_hash, 11),
+ _mm512_set1_epi64(PRIME64_1));
+ offset++;
+ remaining--;
+ }
+
+ v_hash = xxh64_fmix_avx512(v_hash);
+
+ /*
+ * theoritically, such modular operations can be replaced by
+ * _mm512_rem_epi64(), but seems it depends on the compiler's
+ * implementation. so here is the limitation that the modulo
+ * value should be power of 2.
+ */
+ __m512i v_hash_remainder = _mm512_set1_epi64((modulo - 1));
+
+ return _mm512_cvtepi64_epi32(_mm512_and_si512(v_hash, v_hash_remainder));
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_XXH64_AVX512_H_ */
@@ -2,6 +2,9 @@ DPDK_23 {
global:
rte_member_add;
+ rte_member_add_byte_count;
+ rte_member_query_count;
+ rte_member_report_heavyhitter;
rte_member_create;
rte_member_delete;
rte_member_find_existing;