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