Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2020 Intel Corporation
3 : : * Copyright(c) 2020, Alan Liu <zaoxingliu@gmail.com>
4 : : */
5 : :
6 : : #include <math.h>
7 : : #include <string.h>
8 : :
9 : : #include <rte_malloc.h>
10 : : #include <rte_memory.h>
11 : : #include <rte_errno.h>
12 : : #include <rte_log.h>
13 : : #include <rte_random.h>
14 : : #include <rte_prefetch.h>
15 : : #include <rte_cpuflags.h>
16 : : #include <rte_ring_elem.h>
17 : :
18 : : #include "member.h"
19 : : #include "rte_member.h"
20 : : #include "rte_member_sketch.h"
21 : : #include "rte_member_heap.h"
22 : :
23 : : #ifdef CC_AVX512_SUPPORT
24 : : #include "rte_member_sketch_avx512.h"
25 : : #endif /* CC_AVX512_SUPPORT */
26 : :
27 : : struct __rte_cache_aligned sketch_runtime {
28 : : uint64_t pkt_cnt;
29 : : uint32_t until_next;
30 : : int converged;
31 : : struct minheap heap;
32 : : struct node *report_array;
33 : : void *key_slots;
34 : : struct rte_ring *free_key_slots;
35 : : };
36 : :
37 : : /*
38 : : * Geometric sampling to calculate how many packets needs to be
39 : : * skipped until next update. This method can mitigate the CPU
40 : : * overheads compared with coin-toss sampling.
41 : : */
42 : : static uint32_t
43 : 143054 : draw_geometric(const struct rte_member_setsum *ss)
44 : : {
45 : : double rand = 1;
46 : :
47 [ + - ]: 143054 : if (ss->sample_rate == 1)
48 : : return 1;
49 : :
50 [ + + ]: 286108 : while (rand == 1 || rand == 0)
51 : 143054 : rand = (double) rte_rand() / (double)(RTE_RAND_MAX);
52 : :
53 : 143054 : return (uint32_t)ceil(log(1 - rand) / log(1 - ss->sample_rate));
54 : : }
55 : :
56 : : static void
57 : 0 : isort(uint64_t *array, int n)
58 : : {
59 : : int i;
60 : :
61 [ # # ]: 0 : for (i = 1; i < n; i++) {
62 : 0 : uint64_t t = array[i];
63 : : int j;
64 : :
65 [ # # ]: 0 : for (j = i - 1; j >= 0; j--) {
66 [ # # ]: 0 : if (t < array[j])
67 : 0 : array[j + 1] = array[j];
68 : : else
69 : : break;
70 : : }
71 : 0 : array[j + 1] = t;
72 : : }
73 : 0 : }
74 : :
75 : : static __rte_always_inline void
76 : : swap(uint64_t *a, uint64_t *b)
77 : : {
78 : : uint64_t tmp = *a;
79 : : *a = *b;
80 : : *b = tmp;
81 : 229269 : }
82 : :
83 : : static uint64_t
84 : : medianof5(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e)
85 : : {
86 : 174702 : if (a > b)
87 : : swap(&a, &b);
88 [ + + ]: 174702 : if (c > d)
89 : : swap(&c, &d);
90 [ + + ]: 174702 : if (a > c) {
91 [ + + ]: 57538 : if (d > e)
92 : : swap(&c, &e);
93 : : else {
94 : : swap(&c, &d);
95 : : swap(&d, &e);
96 : : }
97 : : } else {
98 [ + + ]: 117164 : if (b > e)
99 : : swap(&a, &e);
100 : : else {
101 : : swap(&a, &b);
102 : : swap(&b, &e);
103 : : }
104 : : }
105 : :
106 [ + + ]: 174702 : if (a > c)
107 : 65358 : return a > d ? d : a;
108 : : else
109 : 109344 : return b > c ? c : b;
110 : : }
111 : :
112 : : int
113 : 4 : rte_member_create_sketch(struct rte_member_setsum *ss,
114 : : const struct rte_member_parameters *params,
115 : : struct rte_ring *ring)
116 : : {
117 : : struct sketch_runtime *runtime;
118 : : uint32_t num_col;
119 : : uint32_t i;
120 : :
121 [ + - - + ]: 4 : if (params->sample_rate == 0 || params->sample_rate > 1) {
122 : 0 : rte_errno = EINVAL;
123 : 0 : MEMBER_LOG(ERR,
124 : : "Membership Sketch created with invalid parameters");
125 : 0 : return -EINVAL;
126 : : }
127 : :
128 [ + + ]: 4 : if (params->extra_flag & RTE_MEMBER_SKETCH_COUNT_BYTE)
129 : 1 : ss->count_byte = 1;
130 : :
131 : : #ifdef RTE_ARCH_X86
132 [ + + - + ]: 5 : if (ss->count_byte == 1 &&
133 [ - - ]: 1 : rte_vect_get_max_simd_bitwidth() >= RTE_VECT_SIMD_512 &&
134 [ # # ]: 0 : rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) == 1 &&
135 : 0 : rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512IFMA) == 1) {
136 : : #ifdef CC_AVX512_SUPPORT
137 : 0 : ss->use_avx512 = true;
138 : : #else
139 : : ss->use_avx512 = false;
140 : : #endif
141 : : }
142 : :
143 [ - + ]: 4 : if (ss->use_avx512 == true) {
144 : : #ifdef CC_AVX512_SUPPORT
145 : 0 : ss->num_row = NUM_ROW_VEC;
146 : 0 : MEMBER_LOG(NOTICE,
147 : : "Membership Sketch AVX512 update/lookup/delete ops is selected");
148 : 0 : ss->sketch_update = sketch_update_avx512;
149 : 0 : ss->sketch_lookup = sketch_lookup_avx512;
150 : 0 : ss->sketch_delete = sketch_delete_avx512;
151 : : #endif
152 : : } else
153 : : #endif
154 : : {
155 : 4 : ss->num_row = NUM_ROW_SCALAR;
156 : 4 : MEMBER_LOG(NOTICE,
157 : : "Membership Sketch SCALAR update/lookup/delete ops is selected");
158 : 4 : ss->sketch_update = sketch_update_scalar;
159 : 4 : ss->sketch_lookup = sketch_lookup_scalar;
160 : 4 : ss->sketch_delete = sketch_delete_scalar;
161 : : }
162 : :
163 : 4 : ss->socket_id = params->socket_id;
164 : :
165 [ + + ]: 4 : if (ss->count_byte == 0)
166 : 3 : num_col = 4.0 / params->error_rate / params->sample_rate;
167 : : #ifdef RTE_ARCH_X86
168 [ - + ]: 1 : else if (ss->use_avx512 == true)
169 : 0 : num_col = rte_align32pow2(4.0 / params->error_rate);
170 : : #endif
171 : : else
172 : 1 : num_col = 4.0 / params->error_rate;
173 : :
174 : 8 : ss->table = rte_zmalloc_socket(NULL,
175 : 4 : sizeof(uint64_t) * num_col * ss->num_row,
176 : : RTE_CACHE_LINE_SIZE, ss->socket_id);
177 [ - + ]: 4 : if (ss->table == NULL) {
178 : 0 : MEMBER_LOG(ERR, "Sketch Table memory allocation failed");
179 : 0 : return -ENOMEM;
180 : : }
181 : :
182 : 8 : ss->hash_seeds = rte_zmalloc_socket(NULL, sizeof(uint64_t) * ss->num_row,
183 : 4 : RTE_CACHE_LINE_SIZE, ss->socket_id);
184 [ - + ]: 4 : if (ss->hash_seeds == NULL) {
185 : 0 : MEMBER_LOG(ERR, "Sketch Hashseeds memory allocation failed");
186 : 0 : return -ENOMEM;
187 : : }
188 : :
189 : 8 : ss->runtime_var = rte_zmalloc_socket(NULL, sizeof(struct sketch_runtime),
190 : 4 : RTE_CACHE_LINE_SIZE, ss->socket_id);
191 [ - + ]: 4 : if (ss->runtime_var == NULL) {
192 : 0 : MEMBER_LOG(ERR, "Sketch Runtime memory allocation failed");
193 : 0 : rte_free(ss);
194 : 0 : return -ENOMEM;
195 : : }
196 : : runtime = ss->runtime_var;
197 : :
198 : 4 : ss->num_col = num_col;
199 : 4 : ss->sample_rate = params->sample_rate;
200 : 4 : ss->prim_hash_seed = params->prim_hash_seed;
201 : 4 : ss->sec_hash_seed = params->sec_hash_seed;
202 : 4 : ss->error_rate = params->error_rate;
203 : 4 : ss->topk = params->top_k;
204 : 4 : ss->key_len = params->key_len;
205 : 4 : runtime->heap.key_len = ss->key_len;
206 : :
207 : 8 : runtime->key_slots = rte_zmalloc_socket(NULL, ss->key_len * ss->topk,
208 : 4 : RTE_CACHE_LINE_SIZE, ss->socket_id);
209 [ - + ]: 4 : if (runtime->key_slots == NULL) {
210 : 0 : MEMBER_LOG(ERR, "Sketch Key Slots allocation failed");
211 : 0 : goto error;
212 : : }
213 : :
214 : 4 : runtime->free_key_slots = ring;
215 [ + + ]: 44 : for (i = 0; i < ss->topk; i++)
216 : 40 : rte_ring_sp_enqueue_elem(runtime->free_key_slots,
217 : : &i, sizeof(uint32_t));
218 : :
219 [ - + ]: 4 : if (rte_member_minheap_init(&(runtime->heap), params->top_k,
220 : 4 : ss->socket_id, params->prim_hash_seed) < 0) {
221 : 0 : MEMBER_LOG(ERR, "Sketch Minheap allocation failed");
222 : 0 : goto error_runtime;
223 : : }
224 : :
225 : 8 : runtime->report_array = rte_zmalloc_socket(NULL, sizeof(struct node) * ss->topk,
226 : 4 : RTE_CACHE_LINE_SIZE, ss->socket_id);
227 [ - + ]: 4 : if (runtime->report_array == NULL) {
228 : 0 : MEMBER_LOG(ERR, "Sketch Runtime Report Array allocation failed");
229 : 0 : goto error_runtime;
230 : : }
231 : :
232 [ + + ]: 24 : for (i = 0; i < ss->num_row; i++)
233 : 20 : ss->hash_seeds[i] = rte_rand();
234 : :
235 [ + + ]: 4 : if (params->extra_flag & RTE_MEMBER_SKETCH_ALWAYS_BOUNDED)
236 : 2 : ss->always_bounded = 1;
237 : :
238 [ + + ]: 4 : if (ss->always_bounded) {
239 : 2 : double delta = 1.0 / (pow(2, ss->num_row));
240 : :
241 : 2 : ss->converge_thresh = 10 * pow(ss->error_rate, -2.0) * sqrt(log(1 / delta));
242 : : }
243 : :
244 : 4 : MEMBER_LOG(DEBUG, "Sketch created, "
245 : : "the total memory required is %u Bytes", ss->num_col * ss->num_row * 8);
246 : :
247 : 4 : return 0;
248 : :
249 : 0 : error_runtime:
250 : 0 : rte_member_minheap_free(&runtime->heap);
251 : 0 : rte_ring_free(runtime->free_key_slots);
252 : 0 : rte_free(runtime->key_slots);
253 : 0 : error:
254 : 0 : rte_free(runtime);
255 : 0 : rte_free(ss);
256 : :
257 : 0 : return -ENOMEM;
258 : : }
259 : :
260 : : uint64_t
261 : 182603 : sketch_lookup_scalar(const struct rte_member_setsum *ss, const void *key)
262 : 182603 : {
263 : 182603 : uint64_t *count_array = ss->table;
264 : 182603 : uint32_t col[ss->num_row];
265 : 182603 : uint64_t count_row[ss->num_row];
266 : : uint32_t cur_row;
267 : : uint64_t count;
268 : :
269 [ + + ]: 1095618 : for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
270 : 1826030 : col[cur_row] = MEMBER_HASH_FUNC(key, ss->key_len,
271 : 913015 : ss->hash_seeds[cur_row]) % ss->num_col;
272 : :
273 : 913015 : rte_prefetch0(&count_array[cur_row * ss->num_col + col[cur_row]]);
274 : : }
275 : :
276 : : /* if sample rate is 1, it is a regular count-min, we report the min */
277 [ + - + + ]: 182603 : if (ss->sample_rate == 1 || ss->count_byte == 1)
278 : 7901 : return count_min(ss, col);
279 : :
280 : : memset(count_row, 0, sizeof(uint64_t) * ss->num_row);
281 : :
282 : : /* otherwise we report the median number */
283 [ + + ]: 1048212 : for (cur_row = 0; cur_row < ss->num_row; cur_row++)
284 : 873510 : count_row[cur_row] = count_array[cur_row * ss->num_col + col[cur_row]];
285 : :
286 [ + - ]: 174702 : if (ss->num_row == 5)
287 [ + + ]: 174702 : return medianof5(count_row[0], count_row[1],
288 : : count_row[2], count_row[3], count_row[4]);
289 : :
290 : 0 : isort(count_row, ss->num_row);
291 : :
292 [ # # ]: 0 : if (ss->num_row % 2 == 0) {
293 : 0 : count = (count_row[ss->num_row / 2] + count_row[ss->num_row / 2 - 1]) / 2;
294 : 0 : return count;
295 : : }
296 : : /* ss->num_row % 2 != 0 */
297 : 0 : count = count_row[ss->num_row / 2];
298 : :
299 : 0 : return count;
300 : : }
301 : :
302 : : void
303 : 2 : sketch_delete_scalar(const struct rte_member_setsum *ss, const void *key)
304 : 2 : {
305 : 2 : uint32_t col[ss->num_row];
306 : 2 : uint64_t *count_array = ss->table;
307 : : uint32_t cur_row;
308 : :
309 [ + + ]: 12 : for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
310 : 20 : col[cur_row] = MEMBER_HASH_FUNC(key, ss->key_len,
311 : 10 : ss->hash_seeds[cur_row]) % ss->num_col;
312 : :
313 : : /* set corresponding counter to 0 */
314 : 10 : count_array[cur_row * ss->num_col + col[cur_row]] = 0;
315 : : }
316 : 2 : }
317 : :
318 : : int
319 : 3500 : rte_member_query_sketch(const struct rte_member_setsum *ss,
320 : : const void *key,
321 : : uint64_t *output)
322 : : {
323 : 3500 : uint64_t count = ss->sketch_lookup(ss, key);
324 : 3500 : *output = count;
325 : :
326 : 3500 : return 0;
327 : : }
328 : :
329 : : void
330 : 6 : rte_member_update_heap(const struct rte_member_setsum *ss)
331 : : {
332 : : uint32_t i;
333 : 6 : struct sketch_runtime *runtime_var = ss->runtime_var;
334 : :
335 [ + + ]: 64 : for (i = 0; i < runtime_var->heap.size; i++) {
336 : 58 : uint64_t count = ss->sketch_lookup(ss, runtime_var->heap.elem[i].key);
337 : :
338 : 58 : runtime_var->heap.elem[i].count = count;
339 : : }
340 : 6 : }
341 : :
342 : : int
343 : 6 : rte_member_report_heavyhitter_sketch(const struct rte_member_setsum *setsum,
344 : : void **key,
345 : : uint64_t *count)
346 : : {
347 : : uint32_t i;
348 : 6 : struct sketch_runtime *runtime_var = setsum->runtime_var;
349 : :
350 : 6 : rte_member_update_heap(setsum);
351 : 6 : rte_member_heapsort(&(runtime_var->heap), runtime_var->report_array);
352 : :
353 [ + + ]: 64 : for (i = 0; i < runtime_var->heap.size; i++) {
354 : 58 : key[i] = runtime_var->report_array[i].key;
355 : 58 : count[i] = runtime_var->report_array[i].count;
356 : : }
357 : :
358 : 6 : return runtime_var->heap.size;
359 : : }
360 : :
361 : : int
362 : 3500 : rte_member_lookup_sketch(const struct rte_member_setsum *ss,
363 : : const void *key, member_set_t *set_id)
364 : : {
365 : 3500 : uint64_t count = ss->sketch_lookup(ss, key);
366 : 3500 : struct sketch_runtime *runtime_var = ss->runtime_var;
367 : :
368 [ + + + + ]: 3500 : if (runtime_var->heap.size > 0 && count >= runtime_var->heap.elem[0].count)
369 : 58 : *set_id = 1;
370 : : else
371 : 3442 : *set_id = 0;
372 : :
373 [ + + ]: 3500 : if (count == 0)
374 : : return 0;
375 : : else
376 : 2995 : return 1;
377 : : }
378 : :
379 : : static void
380 : 1 : should_converge(const struct rte_member_setsum *ss)
381 : : {
382 : 1 : struct sketch_runtime *runtime_var = ss->runtime_var;
383 : :
384 : : /* For count min sketch - L1 norm */
385 [ + - ]: 1 : if (runtime_var->pkt_cnt > ss->converge_thresh) {
386 : 1 : runtime_var->converged = 1;
387 : 1 : MEMBER_LOG(DEBUG, "Sketch converged, begin sampling "
388 : : "from key count %"PRIu64,
389 : : runtime_var->pkt_cnt);
390 : : }
391 : 1 : }
392 : :
393 : : static void
394 : 136163 : sketch_update_row(const struct rte_member_setsum *ss, const void *key,
395 : : uint32_t count, uint32_t cur_row)
396 : : {
397 : 136163 : uint64_t *count_array = ss->table;
398 : 272326 : uint32_t col = MEMBER_HASH_FUNC(key, ss->key_len,
399 : 136163 : ss->hash_seeds[cur_row]) % ss->num_col;
400 : :
401 : : /* sketch counter update */
402 : 136163 : count_array[cur_row * ss->num_col + col] +=
403 : 136163 : ceil(count / (ss->sample_rate));
404 : 136163 : }
405 : :
406 : : void
407 : 6825847 : sketch_update_scalar(const struct rte_member_setsum *ss,
408 : : const void *key,
409 : : uint32_t count)
410 : : {
411 : 6825847 : uint64_t *count_array = ss->table;
412 : : uint32_t col;
413 : : uint32_t cur_row;
414 : :
415 [ + + ]: 40955082 : for (cur_row = 0; cur_row < ss->num_row; cur_row++) {
416 : 68258470 : col = MEMBER_HASH_FUNC(key, ss->key_len,
417 : 34129235 : ss->hash_seeds[cur_row]) % ss->num_col;
418 : 34129235 : count_array[cur_row * ss->num_col + col] += count;
419 : : }
420 : 6825847 : }
421 : :
422 : : static void
423 : 175545 : heap_update(const struct rte_member_setsum *ss, const void *key)
424 : : {
425 : 175545 : struct sketch_runtime *runtime_var = ss->runtime_var;
426 : : uint64_t key_cnt = 0;
427 : : int found;
428 : :
429 : : /* We also update the heap for this key */
430 : 175545 : key_cnt = ss->sketch_lookup(ss, key);
431 [ + + ]: 175545 : if (key_cnt > runtime_var->heap.elem[0].count) {
432 : 73513 : found = rte_member_minheap_find(&runtime_var->heap, key);
433 : : /* the key is found in the top-k heap */
434 [ + + ]: 73513 : if (found >= 0) {
435 [ + + ]: 73328 : if (runtime_var->heap.elem[found].count < key_cnt)
436 : 28591 : rte_member_heapify(&runtime_var->heap, found, true);
437 : :
438 : 73328 : runtime_var->heap.elem[found].count = key_cnt;
439 [ + + ]: 185 : } else if (runtime_var->heap.size < ss->topk) {
440 : 11 : rte_member_minheap_insert_node(&runtime_var->heap, key,
441 : : key_cnt, runtime_var->key_slots, runtime_var->free_key_slots);
442 : : } else {
443 : 174 : rte_member_minheap_replace_node(&runtime_var->heap, key, key_cnt);
444 : : }
445 [ + + ]: 102032 : } else if (runtime_var->heap.size < ss->topk) {
446 : 42 : found = rte_member_minheap_find(&runtime_var->heap, key);
447 [ + + ]: 42 : if (found >= 0) {
448 [ - + ]: 3 : if (runtime_var->heap.elem[found].count < key_cnt)
449 : 0 : rte_member_heapify(&runtime_var->heap, found, true);
450 : :
451 : 3 : runtime_var->heap.elem[found].count = key_cnt;
452 : : } else
453 : 39 : rte_member_minheap_insert_node(&runtime_var->heap, key,
454 : : key_cnt, runtime_var->key_slots, runtime_var->free_key_slots);
455 : : }
456 : 175545 : }
457 : :
458 : : /*
459 : : * Add a single packet into the sketch.
460 : : * Sketch value is meatured by packet numbers in this mode.
461 : : */
462 : : int
463 : 27172316 : rte_member_add_sketch(const struct rte_member_setsum *ss,
464 : : const void *key,
465 : : __rte_unused member_set_t set_id)
466 : : {
467 : : uint32_t cur_row;
468 : 27172316 : struct sketch_runtime *runtime_var = ss->runtime_var;
469 : : uint32_t *until_next = &(runtime_var->until_next);
470 : :
471 : : /*
472 : : * If sketch is measured by byte count,
473 : : * the rte_member_add_sketch_byte_count routine should be used.
474 : : */
475 [ - + ]: 27172316 : if (ss->count_byte == 1) {
476 : 0 : MEMBER_LOG(ERR, "Sketch is Byte Mode, "
477 : : "should use rte_member_add_byte_count()!");
478 : 0 : return -EINVAL;
479 : : }
480 : :
481 [ - + ]: 27172316 : if (ss->sample_rate == 1) {
482 : 0 : ss->sketch_update(ss, key, 1);
483 : 0 : heap_update(ss, key);
484 : 0 : return 0;
485 : : }
486 : :
487 : : /* convergence stage if it's needed */
488 [ + + + + ]: 27172316 : if (ss->always_bounded && !runtime_var->converged) {
489 : 32768 : ss->sketch_update(ss, key, 1);
490 : :
491 [ + + ]: 32768 : if (!((++runtime_var->pkt_cnt) & (INTERVAL - 1)))
492 : 1 : should_converge(ss);
493 : :
494 : 32768 : heap_update(ss, key);
495 : 32768 : return 0;
496 : : }
497 : :
498 : : /* should we skip this packet */
499 [ + + ]: 27139548 : if (*until_next >= ss->num_row) {
500 : 27003662 : *until_next -= ss->num_row;
501 : 27003662 : return 0;
502 : : }
503 : : cur_row = *until_next;
504 : : do {
505 : 136163 : sketch_update_row(ss, key, 1, cur_row);
506 : 136163 : *until_next = draw_geometric(ss);
507 [ + + ]: 136163 : if (cur_row + *until_next >= ss->num_row)
508 : : break;
509 : : cur_row += *until_next;
510 : : } while (1);
511 : :
512 : 135886 : *until_next -= (ss->num_row - cur_row);
513 : :
514 : 135886 : heap_update(ss, key);
515 : :
516 : 135886 : return 0;
517 : : }
518 : :
519 : : /*
520 : : * Add the byte count of the packet into the sketch.
521 : : * Sketch value is meatured by byte count numbers in this mode.
522 : : */
523 : : int
524 : 6793079 : rte_member_add_sketch_byte_count(const struct rte_member_setsum *ss,
525 : : const void *key,
526 : : uint32_t byte_count)
527 : : {
528 : 6793079 : struct sketch_runtime *runtime_var = ss->runtime_var;
529 : : uint32_t *until_next = &(runtime_var->until_next);
530 : :
531 : : /* should not call this API if not in count byte mode */
532 [ - + ]: 6793079 : if (ss->count_byte == 0) {
533 : 0 : MEMBER_LOG(ERR, "Sketch is Pkt Mode, "
534 : : "should use rte_member_add()!");
535 : 0 : return -EINVAL;
536 : : }
537 : :
538 : : /* there's specific optimization for the sketch update */
539 : 6793079 : ss->sketch_update(ss, key, byte_count);
540 : :
541 [ + + ]: 6793079 : if (*until_next != 0) {
542 : 6786188 : *until_next = *until_next - 1;
543 : 6786188 : return 0;
544 : : }
545 : :
546 : 6891 : *until_next = draw_geometric(ss) - 1;
547 : :
548 : 6891 : heap_update(ss, key);
549 : :
550 : 6891 : return 0;
551 : : }
552 : :
553 : : int
554 : 2 : rte_member_delete_sketch(const struct rte_member_setsum *ss,
555 : : const void *key)
556 : : {
557 : 2 : struct sketch_runtime *runtime_var = ss->runtime_var;
558 : : int found;
559 : :
560 : 2 : found = rte_member_minheap_find(&runtime_var->heap, key);
561 [ + - ]: 2 : if (found < 0)
562 : : return -1;
563 : :
564 : 2 : ss->sketch_delete(ss, key);
565 : :
566 : 2 : return rte_member_minheap_delete_node
567 : : (&runtime_var->heap, key, runtime_var->key_slots, runtime_var->free_key_slots);
568 : : }
569 : :
570 : : void
571 : 4 : rte_member_free_sketch(struct rte_member_setsum *ss)
572 : : {
573 : 4 : struct sketch_runtime *runtime_var = ss->runtime_var;
574 : :
575 : 4 : rte_free(ss->table);
576 : 4 : rte_member_minheap_free(&runtime_var->heap);
577 : 4 : rte_free(runtime_var->key_slots);
578 : 4 : rte_ring_free(runtime_var->free_key_slots);
579 : 4 : rte_free(runtime_var);
580 : 4 : }
581 : :
582 : : void
583 : 1 : rte_member_reset_sketch(const struct rte_member_setsum *ss)
584 : : {
585 : 1 : struct sketch_runtime *runtime_var = ss->runtime_var;
586 : 1 : uint64_t *sketch = ss->table;
587 : : uint32_t i;
588 : :
589 : 1 : memset(sketch, 0, sizeof(uint64_t) * ss->num_col * ss->num_row);
590 : 1 : rte_member_minheap_reset(&runtime_var->heap);
591 : 1 : rte_ring_reset(runtime_var->free_key_slots);
592 : :
593 [ + + ]: 11 : for (i = 0; i < ss->topk; i++)
594 : 10 : rte_ring_sp_enqueue_elem(runtime_var->free_key_slots, &i, sizeof(uint32_t));
595 : 1 : }
|
