Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2017 Intel Corporation
3 : : */
4 : :
5 : : /* This test is for membership library's simple feature test */
6 : :
7 : : #include <math.h>
8 : : #include "test.h"
9 : :
10 : : #include <rte_memcpy.h>
11 : : #include <rte_malloc.h>
12 : :
13 : : #ifdef RTE_EXEC_ENV_WINDOWS
14 : : static int
15 : : test_member(void)
16 : : {
17 : : printf("member not supported on Windows, skipping test\n");
18 : : return TEST_SKIPPED;
19 : : }
20 : :
21 : : #else
22 : :
23 : : #include <rte_member.h>
24 : : #include <rte_byteorder.h>
25 : : #include <rte_random.h>
26 : : #include <rte_debug.h>
27 : : #include <rte_ip.h>
28 : :
29 : : struct rte_member_setsum *setsum_ht;
30 : : struct rte_member_setsum *setsum_cache;
31 : : struct rte_member_setsum *setsum_vbf;
32 : : struct rte_member_setsum *setsum_sketch;
33 : :
34 : : /* 5-tuple key type */
35 : : struct flow_key {
36 : : uint32_t ip_src;
37 : : uint32_t ip_dst;
38 : : uint16_t port_src;
39 : : uint16_t port_dst;
40 : : uint8_t proto;
41 : : } __rte_packed;
42 : :
43 : : /* Set ID Macros for multimatch test usage */
44 : : #define M_MATCH_S 1 /* Not start with 0 since by default 0 means no match */
45 : : #define M_MATCH_E 15
46 : : #define M_MATCH_STEP 2
47 : : #define M_MATCH_CNT \
48 : : (1 + (M_MATCH_E - M_MATCH_S) / M_MATCH_STEP)
49 : :
50 : :
51 : : #define NUM_SAMPLES 5
52 : : #define MAX_MATCH 32
53 : :
54 : : /* Keys used by unit test functions */
55 : : static struct flow_key keys[NUM_SAMPLES] = {
56 : : {
57 : : .ip_src = RTE_IPV4(0x03, 0x02, 0x01, 0x00),
58 : : .ip_dst = RTE_IPV4(0x07, 0x06, 0x05, 0x04),
59 : : .port_src = 0x0908,
60 : : .port_dst = 0x0b0a,
61 : : .proto = 0x0c,
62 : : },
63 : : {
64 : : .ip_src = RTE_IPV4(0x13, 0x12, 0x11, 0x10),
65 : : .ip_dst = RTE_IPV4(0x17, 0x16, 0x15, 0x14),
66 : : .port_src = 0x1918,
67 : : .port_dst = 0x1b1a,
68 : : .proto = 0x1c,
69 : : },
70 : : {
71 : : .ip_src = RTE_IPV4(0x23, 0x22, 0x21, 0x20),
72 : : .ip_dst = RTE_IPV4(0x27, 0x26, 0x25, 0x24),
73 : : .port_src = 0x2928,
74 : : .port_dst = 0x2b2a,
75 : : .proto = 0x2c,
76 : : },
77 : : {
78 : : .ip_src = RTE_IPV4(0x33, 0x32, 0x31, 0x30),
79 : : .ip_dst = RTE_IPV4(0x37, 0x36, 0x35, 0x34),
80 : : .port_src = 0x3938,
81 : : .port_dst = 0x3b3a,
82 : : .proto = 0x3c,
83 : : },
84 : : {
85 : : .ip_src = RTE_IPV4(0x43, 0x42, 0x41, 0x40),
86 : : .ip_dst = RTE_IPV4(0x47, 0x46, 0x45, 0x44),
87 : : .port_src = 0x4948,
88 : : .port_dst = 0x4b4a,
89 : : .proto = 0x4c,
90 : : }
91 : : };
92 : :
93 : : uint32_t test_set[NUM_SAMPLES] = {1, 2, 3, 4, 5};
94 : :
95 : : #define ITERATIONS 3
96 : : #define KEY_SIZE 4
97 : :
98 : : #define MAX_ENTRIES (1 << 16)
99 : : uint8_t generated_keys[MAX_ENTRIES][KEY_SIZE];
100 : :
101 : : static struct rte_member_parameters params = {
102 : : .num_keys = MAX_ENTRIES, /* Total hash table entries. */
103 : : .key_len = KEY_SIZE, /* Length of hash key. */
104 : :
105 : : /* num_set and false_positive_rate only relevant to vBF */
106 : : .num_set = 16,
107 : : .false_positive_rate = 0.03,
108 : : .prim_hash_seed = 1,
109 : : .sec_hash_seed = 11,
110 : : .socket_id = 0 /* NUMA Socket ID for memory. */
111 : : };
112 : :
113 : : /* for sketch definitions */
114 : : #define TOP_K 10
115 : : #define HH_PKT_SIZE 16
116 : : #define SKETCH_ERROR_RATE 0.05
117 : : #define SKETCH_SAMPLE_RATE 0.001
118 : : #define PRINT_OUT_COUNT 20
119 : :
120 : : #define SKETCH_LARGEST_KEY_SIZE 1000000
121 : : #define SKETCH_TOTAL_KEY 500
122 : : #define NUM_OF_KEY(key) {\
123 : : (unsigned int)ceil(SKETCH_LARGEST_KEY_SIZE / (key + 1)) \
124 : : }
125 : :
126 : : void *heavy_hitters[TOP_K];
127 : :
128 : : /*
129 : : * Sequence of operations for find existing setsummary
130 : : *
131 : : * - create setsum
132 : : * - find existing setsum: hit
133 : : * - find non-existing setsum: miss
134 : : *
135 : : */
136 : : static int
137 : 1 : test_member_find_existing(void)
138 : : {
139 : : struct rte_member_setsum *tmp_setsum = NULL, *result = NULL;
140 : 1 : struct rte_member_parameters tmp_params = {
141 : : .name = "member_find_existing",
142 : : .num_keys = MAX_ENTRIES, /* Total hash table entries. */
143 : : .key_len = KEY_SIZE, /* Length of hash key. */
144 : : .type = RTE_MEMBER_TYPE_HT,
145 : : .num_set = 32,
146 : : .false_positive_rate = 0.03,
147 : : .prim_hash_seed = 1,
148 : : .sec_hash_seed = 11,
149 : : .socket_id = 0 /* NUMA Socket ID for memory. */
150 : : };
151 : :
152 : : /* Create */
153 : 1 : tmp_setsum = rte_member_create(&tmp_params);
154 [ - + ]: 1 : TEST_ASSERT(tmp_setsum != NULL, "setsum creation failed");
155 : :
156 : : /* Try to find existing hash table */
157 : 1 : result = rte_member_find_existing("member_find_existing");
158 [ - + ]: 1 : TEST_ASSERT(result == tmp_setsum, "could not find existing setsum");
159 : :
160 : : /* Try to find non-existing hash table */
161 : 1 : result = rte_member_find_existing("member_find_non_existing");
162 [ - + ]: 1 : TEST_ASSERT(result == NULL, "found setsum that shouldn't exist");
163 : :
164 : : /* Cleanup. */
165 : 1 : rte_member_free(tmp_setsum);
166 : :
167 : 1 : return 0;
168 : : }
169 : :
170 : : /*
171 : : * Test for bad creating parameters
172 : : */
173 : : static int
174 : 1 : test_member_create_bad_param(void)
175 : : {
176 : : struct rte_member_setsum *bad_setsum = NULL;
177 : 1 : struct rte_member_parameters bad_params = {
178 : : .num_keys = MAX_ENTRIES, /* Total hash table entries. */
179 : : .key_len = KEY_SIZE, /* Length of hash key. */
180 : : .type = RTE_MEMBER_TYPE_HT,
181 : : .num_set = 32,
182 : : .false_positive_rate = 0.03,
183 : : .prim_hash_seed = 1,
184 : : .sec_hash_seed = 11,
185 : : .socket_id = 0 /* NUMA Socket ID for memory. */
186 : : };
187 : :
188 : : printf("Expected error section begin...\n");
189 : 1 : bad_params.name = "bad_param1";
190 : 1 : bad_params.num_set = 0;
191 : 1 : bad_params.type = RTE_MEMBER_TYPE_VBF;
192 : : /* Test with 0 set for vBF should fail */
193 : 1 : bad_setsum = rte_member_create(&bad_params);
194 [ - + ]: 1 : if (bad_setsum != NULL) {
195 : 0 : rte_member_free(bad_setsum);
196 : : printf("Impossible creating setsum successfully with invalid "
197 : : "number of set for vBF\n");
198 : 0 : return -1;
199 : : }
200 : :
201 : 1 : bad_params.name = "bad_param2";
202 : 1 : bad_params.false_positive_rate = 0;
203 : 1 : bad_params.num_set = 32;
204 : : /* Test with 0 false positive for vBF should fail */
205 : 1 : bad_setsum = rte_member_create(&bad_params);
206 [ - + ]: 1 : if (bad_setsum != NULL) {
207 : 0 : rte_member_free(bad_setsum);
208 : : printf("Impossible creating setsum successfully with invalid "
209 : : "false positive rate for vBF\n");
210 : 0 : return -1;
211 : : }
212 : :
213 : 1 : bad_params.name = "bad_param3";
214 : 1 : bad_params.false_positive_rate = 0.03;
215 : 1 : bad_params.num_keys = 0;
216 : : /* Test with 0 key per BF for vBF should fail */
217 : 1 : bad_setsum = rte_member_create(&bad_params);
218 [ - + ]: 1 : if (bad_setsum != NULL) {
219 : 0 : rte_member_free(bad_setsum);
220 : : printf("Impossible creating setsum successfully with invalid "
221 : : "num_keys for vBF\n");
222 : 0 : return -1;
223 : : }
224 : :
225 : 1 : bad_params.name = "bad_param4";
226 : 1 : bad_params.type = RTE_MEMBER_TYPE_HT;
227 : 1 : bad_params.num_keys = RTE_MEMBER_BUCKET_ENTRIES / 2;
228 : : /* Test with less than 1 bucket for HTSS should fail */
229 : 1 : bad_setsum = rte_member_create(&bad_params);
230 [ - + ]: 1 : if (bad_setsum != NULL) {
231 : 0 : rte_member_free(bad_setsum);
232 : : printf("Impossible creating setsum successfully with too few "
233 : : "number of keys(entries) for HT\n");
234 : 0 : return -1;
235 : : }
236 : :
237 : 1 : bad_params.name = "bad_param5";
238 : 1 : bad_params.num_keys = RTE_MEMBER_ENTRIES_MAX + 1;
239 : : /* Test with more than maximum entries for HTSS should fail */
240 : 1 : bad_setsum = rte_member_create(&bad_params);
241 [ - + ]: 1 : if (bad_setsum != NULL) {
242 : 0 : rte_member_free(bad_setsum);
243 : : printf("Impossible creating setsum successfully with to many "
244 : : "number of keys(entries) for HT\n");
245 : 0 : return -1;
246 : : }
247 : :
248 : 1 : bad_params.name = "bad_param5";
249 : : /* Test with same name should fail */
250 : 1 : bad_setsum = rte_member_create(&bad_params);
251 [ - + ]: 1 : if (bad_setsum != NULL) {
252 : 0 : rte_member_free(bad_setsum);
253 : : printf("Impossible creating setsum successfully with existed "
254 : : "name\n");
255 : 0 : return -1;
256 : : }
257 : : printf("Expected error section end...\n");
258 : 1 : rte_member_free(bad_setsum);
259 : 1 : return 0;
260 : : }
261 : :
262 : : /* Create test setsummaries. */
263 : 1 : static int test_member_create(void)
264 : : {
265 : 1 : params.key_len = sizeof(struct flow_key);
266 : :
267 : 1 : params.name = "test_member_ht";
268 : 1 : params.is_cache = 0;
269 : 1 : params.type = RTE_MEMBER_TYPE_HT;
270 : 1 : setsum_ht = rte_member_create(¶ms);
271 : :
272 : 1 : params.name = "test_member_cache";
273 : 1 : params.is_cache = 1;
274 : 1 : setsum_cache = rte_member_create(¶ms);
275 : :
276 : 1 : params.name = "test_member_vbf";
277 : 1 : params.type = RTE_MEMBER_TYPE_VBF;
278 : 1 : setsum_vbf = rte_member_create(¶ms);
279 : :
280 [ + - + - : 1 : if (setsum_ht == NULL || setsum_cache == NULL || setsum_vbf == NULL) {
- + ]
281 : : printf("Creation of setsums fail\n");
282 : 0 : return -1;
283 : : }
284 : : printf("Creation of setsums success\n");
285 : 1 : return 0;
286 : : }
287 : :
288 : 1 : static int test_member_insert(void)
289 : : {
290 : : int ret_ht, ret_cache, ret_vbf, i;
291 : :
292 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++) {
293 : 5 : ret_ht = rte_member_add(setsum_ht, &keys[i], test_set[i]);
294 : 5 : ret_cache = rte_member_add(setsum_cache, &keys[i],
295 : 5 : test_set[i]);
296 : 5 : ret_vbf = rte_member_add(setsum_vbf, &keys[i], test_set[i]);
297 [ + - - + ]: 5 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0,
298 : : "insert error");
299 : : }
300 : : printf("insert key success\n");
301 : 1 : return 0;
302 : : }
303 : :
304 : 1 : static int test_member_lookup(void)
305 : : {
306 : : int ret_ht, ret_cache, ret_vbf, i;
307 : : uint16_t set_ht, set_cache, set_vbf;
308 : 1 : member_set_t set_ids_ht[NUM_SAMPLES] = {0};
309 : 1 : member_set_t set_ids_cache[NUM_SAMPLES] = {0};
310 : 1 : member_set_t set_ids_vbf[NUM_SAMPLES] = {0};
311 : :
312 : : uint32_t num_key_ht = NUM_SAMPLES;
313 : : uint32_t num_key_cache = NUM_SAMPLES;
314 : : uint32_t num_key_vbf = NUM_SAMPLES;
315 : :
316 : : const void *key_array[NUM_SAMPLES];
317 : :
318 : : /* Single lookup test */
319 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++) {
320 : 5 : ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht);
321 : 5 : ret_cache = rte_member_lookup(setsum_cache, &keys[i],
322 : : &set_cache);
323 : 5 : ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf);
324 [ + - - + ]: 5 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0,
325 : : "single lookup function error");
326 : :
327 [ + - + - : 5 : TEST_ASSERT(set_ht == test_set[i] &&
- + ]
328 : : set_cache == test_set[i] &&
329 : : set_vbf == test_set[i],
330 : : "single lookup set value error");
331 : : }
332 : : printf("lookup single key success\n");
333 : :
334 : : /* Bulk lookup test */
335 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++)
336 : 5 : key_array[i] = &keys[i];
337 : :
338 : 1 : ret_ht = rte_member_lookup_bulk(setsum_ht, key_array,
339 : : num_key_ht, set_ids_ht);
340 : :
341 : 1 : ret_cache = rte_member_lookup_bulk(setsum_cache, key_array,
342 : : num_key_cache, set_ids_cache);
343 : :
344 : 1 : ret_vbf = rte_member_lookup_bulk(setsum_vbf, key_array,
345 : : num_key_vbf, set_ids_vbf);
346 : :
347 [ + - - + ]: 1 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0,
348 : : "bulk lookup function error");
349 : :
350 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++) {
351 [ + - + - : 5 : TEST_ASSERT((set_ids_ht[i] == test_set[i]) &&
- + ]
352 : : (set_ids_cache[i] == test_set[i]) &&
353 : : (set_ids_vbf[i] == test_set[i]),
354 : : "bulk lookup result error");
355 : : }
356 : :
357 : : return 0;
358 : : }
359 : :
360 : 1 : static int test_member_delete(void)
361 : : {
362 : : int ret_ht, ret_cache, ret_vbf, i;
363 : : uint16_t set_ht, set_cache, set_vbf;
364 : : const void *key_array[NUM_SAMPLES];
365 : 1 : member_set_t set_ids_ht[NUM_SAMPLES] = {0};
366 : 1 : member_set_t set_ids_cache[NUM_SAMPLES] = {0};
367 : 1 : member_set_t set_ids_vbf[NUM_SAMPLES] = {0};
368 : : uint32_t num_key_ht = NUM_SAMPLES;
369 : : uint32_t num_key_cache = NUM_SAMPLES;
370 : : uint32_t num_key_vbf = NUM_SAMPLES;
371 : :
372 : : /* Delete part of all inserted keys */
373 [ + + ]: 3 : for (i = 0; i < NUM_SAMPLES / 2; i++) {
374 : 2 : ret_ht = rte_member_delete(setsum_ht, &keys[i], test_set[i]);
375 : 2 : ret_cache = rte_member_delete(setsum_cache, &keys[i],
376 : 2 : test_set[i]);
377 : 2 : ret_vbf = rte_member_delete(setsum_vbf, &keys[i], test_set[i]);
378 : : /* VBF does not support delete yet, so return error code */
379 [ - + ]: 2 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0,
380 : : "key deletion function error");
381 [ - + ]: 2 : TEST_ASSERT(ret_vbf < 0,
382 : : "vbf does not support deletion, error");
383 : : }
384 : :
385 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++)
386 : 5 : key_array[i] = &keys[i];
387 : :
388 : 1 : ret_ht = rte_member_lookup_bulk(setsum_ht, key_array,
389 : : num_key_ht, set_ids_ht);
390 : :
391 : 1 : ret_cache = rte_member_lookup_bulk(setsum_cache, key_array,
392 : : num_key_cache, set_ids_cache);
393 : :
394 : 1 : ret_vbf = rte_member_lookup_bulk(setsum_vbf, key_array,
395 : : num_key_vbf, set_ids_vbf);
396 : :
397 [ + - - + ]: 1 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0,
398 : : "bulk lookup function error");
399 : :
400 [ + + ]: 3 : for (i = 0; i < NUM_SAMPLES / 2; i++) {
401 [ + - - + ]: 2 : TEST_ASSERT((set_ids_ht[i] == RTE_MEMBER_NO_MATCH) &&
402 : : (set_ids_cache[i] == RTE_MEMBER_NO_MATCH),
403 : : "bulk lookup result error");
404 : : }
405 : :
406 [ + + ]: 4 : for (i = NUM_SAMPLES / 2; i < NUM_SAMPLES; i++) {
407 [ + - + - : 3 : TEST_ASSERT((set_ids_ht[i] == test_set[i]) &&
- + ]
408 : : (set_ids_cache[i] == test_set[i]) &&
409 : : (set_ids_vbf[i] == test_set[i]),
410 : : "bulk lookup result error");
411 : : }
412 : :
413 : : /* Delete the left of inserted keys */
414 [ + + ]: 4 : for (i = NUM_SAMPLES / 2; i < NUM_SAMPLES; i++) {
415 : 3 : ret_ht = rte_member_delete(setsum_ht, &keys[i], test_set[i]);
416 : 3 : ret_cache = rte_member_delete(setsum_cache, &keys[i],
417 : 3 : test_set[i]);
418 : 3 : ret_vbf = rte_member_delete(setsum_vbf, &keys[i], test_set[i]);
419 : : /* VBF does not support delete yet, so return error code */
420 [ - + ]: 3 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0,
421 : : "key deletion function error");
422 [ - + ]: 3 : TEST_ASSERT(ret_vbf < 0,
423 : : "vbf does not support deletion, error");
424 : : }
425 : :
426 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++) {
427 : 5 : ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht);
428 : 5 : ret_cache = rte_member_lookup(setsum_cache, &keys[i],
429 : : &set_cache);
430 : 5 : ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf);
431 [ - + ]: 5 : TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0,
432 : : "key lookup function error");
433 [ + - - + ]: 5 : TEST_ASSERT(set_ht == RTE_MEMBER_NO_MATCH &&
434 : : ret_cache == RTE_MEMBER_NO_MATCH,
435 : : "key deletion failed");
436 : : }
437 : : /* Reset vbf for other following tests */
438 : 1 : rte_member_reset(setsum_vbf);
439 : :
440 : : printf("delete success\n");
441 : 1 : return 0;
442 : : }
443 : :
444 : 1 : static int test_member_multimatch(void)
445 : : {
446 : : int ret_ht, ret_vbf, ret_cache;
447 : 1 : member_set_t set_ids_ht[MAX_MATCH] = {0};
448 : 1 : member_set_t set_ids_vbf[MAX_MATCH] = {0};
449 : 1 : member_set_t set_ids_cache[MAX_MATCH] = {0};
450 : :
451 : 1 : member_set_t set_ids_ht_m[NUM_SAMPLES][MAX_MATCH] = {{0} };
452 : 1 : member_set_t set_ids_vbf_m[NUM_SAMPLES][MAX_MATCH] = {{0} };
453 : 1 : member_set_t set_ids_cache_m[NUM_SAMPLES][MAX_MATCH] = {{0} };
454 : :
455 : : uint32_t match_count_ht[NUM_SAMPLES];
456 : : uint32_t match_count_vbf[NUM_SAMPLES];
457 : : uint32_t match_count_cache[NUM_SAMPLES];
458 : :
459 : : uint32_t num_key_ht = NUM_SAMPLES;
460 : : uint32_t num_key_vbf = NUM_SAMPLES;
461 : : uint32_t num_key_cache = NUM_SAMPLES;
462 : :
463 : : const void *key_array[NUM_SAMPLES];
464 : :
465 : : uint32_t i, j;
466 : :
467 : : /* Same key at most inserted 2*entry_per_bucket times for HT mode */
468 [ + + ]: 9 : for (i = M_MATCH_S; i <= M_MATCH_E; i += M_MATCH_STEP) {
469 [ + + ]: 48 : for (j = 0; j < NUM_SAMPLES; j++) {
470 : 40 : ret_ht = rte_member_add(setsum_ht, &keys[j], i);
471 : 40 : ret_vbf = rte_member_add(setsum_vbf, &keys[j], i);
472 : 40 : ret_cache = rte_member_add(setsum_cache, &keys[j], i);
473 : :
474 [ + - - + ]: 40 : TEST_ASSERT(ret_ht >= 0 && ret_vbf >= 0 &&
475 : : ret_cache >= 0,
476 : : "insert function error");
477 : : }
478 : : }
479 : :
480 : : /* Single multimatch test */
481 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++) {
482 : 5 : ret_vbf = rte_member_lookup_multi(setsum_vbf, &keys[i],
483 : : MAX_MATCH, set_ids_vbf);
484 : 5 : ret_ht = rte_member_lookup_multi(setsum_ht, &keys[i],
485 : : MAX_MATCH, set_ids_ht);
486 : 5 : ret_cache = rte_member_lookup_multi(setsum_cache, &keys[i],
487 : : MAX_MATCH, set_ids_cache);
488 : : /*
489 : : * For cache mode, keys overwrite when signature same.
490 : : * the multimatch should work like single match.
491 : : */
492 [ + - - + ]: 5 : TEST_ASSERT(ret_ht == M_MATCH_CNT && ret_vbf == M_MATCH_CNT &&
493 : : ret_cache == 1,
494 : : "single lookup_multi error");
495 [ - + ]: 5 : TEST_ASSERT(set_ids_cache[0] == M_MATCH_E,
496 : : "single lookup_multi cache error");
497 : :
498 [ + + ]: 45 : for (j = 1; j <= M_MATCH_CNT; j++) {
499 [ + - - + ]: 40 : TEST_ASSERT(set_ids_ht[j-1] == j * M_MATCH_STEP - 1 &&
500 : : set_ids_vbf[j-1] ==
501 : : j * M_MATCH_STEP - 1,
502 : : "single multimatch lookup error");
503 : : }
504 : : }
505 : : printf("lookup single key for multimatch success\n");
506 : :
507 : : /* Bulk multimatch test */
508 [ + + ]: 6 : for (i = 0; i < NUM_SAMPLES; i++)
509 : 5 : key_array[i] = &keys[i];
510 : 1 : ret_vbf = rte_member_lookup_multi_bulk(setsum_vbf,
511 : : &key_array[0], num_key_ht, MAX_MATCH, match_count_vbf,
512 : : (member_set_t *)set_ids_vbf_m);
513 : :
514 : 1 : ret_ht = rte_member_lookup_multi_bulk(setsum_ht,
515 : : &key_array[0], num_key_vbf, MAX_MATCH, match_count_ht,
516 : : (member_set_t *)set_ids_ht_m);
517 : :
518 : 1 : ret_cache = rte_member_lookup_multi_bulk(setsum_cache,
519 : : &key_array[0], num_key_cache, MAX_MATCH,
520 : : match_count_cache, (member_set_t *)set_ids_cache_m);
521 : :
522 : :
523 [ + + ]: 6 : for (j = 0; j < NUM_SAMPLES; j++) {
524 [ - + ]: 5 : TEST_ASSERT(match_count_ht[j] == M_MATCH_CNT,
525 : : "bulk multimatch lookup HT match count error");
526 [ - + ]: 5 : TEST_ASSERT(match_count_vbf[j] == M_MATCH_CNT,
527 : : "bulk multimatch lookup vBF match count error");
528 [ - + ]: 5 : TEST_ASSERT(match_count_cache[j] == 1,
529 : : "bulk multimatch lookup CACHE match count error");
530 [ - + ]: 5 : TEST_ASSERT(set_ids_cache_m[j][0] == M_MATCH_E,
531 : : "bulk multimatch lookup CACHE set value error");
532 : :
533 [ + + ]: 45 : for (i = 1; i <= M_MATCH_CNT; i++) {
534 [ - + ]: 40 : TEST_ASSERT(set_ids_ht_m[j][i-1] ==
535 : : i * M_MATCH_STEP - 1,
536 : : "bulk multimatch lookup HT set value error");
537 [ - + ]: 40 : TEST_ASSERT(set_ids_vbf_m[j][i-1] ==
538 : : i * M_MATCH_STEP - 1,
539 : : "bulk multimatch lookup vBF set value error");
540 : : }
541 : : }
542 : :
543 : : printf("lookup for bulk multimatch success\n");
544 : :
545 : 1 : return 0;
546 : : }
547 : :
548 : 1489867 : static int key_compare(const void *key1, const void *key2)
549 : : {
550 : 1489867 : return memcmp(key1, key2, KEY_SIZE);
551 : : }
552 : :
553 : : static void
554 : 1 : setup_keys_and_data(void)
555 : : {
556 : : unsigned int i, j;
557 : : int num_duplicates;
558 : :
559 : : /* Reset all arrays */
560 [ + + ]: 5 : for (i = 0; i < KEY_SIZE; i++)
561 : 4 : generated_keys[0][i] = 0;
562 : :
563 : : /* Generate a list of keys, some of which may be duplicates */
564 [ + + ]: 65537 : for (i = 0; i < MAX_ENTRIES; i++) {
565 [ + + ]: 327680 : for (j = 0; j < KEY_SIZE; j++)
566 : 262144 : generated_keys[i][j] = rte_rand() & 0xFF;
567 : : }
568 : :
569 : : /* Remove duplicates from the keys array */
570 : : do {
571 : : num_duplicates = 0;
572 : : /* Sort the list of keys to make it easier to find duplicates */
573 : 2 : qsort(generated_keys, MAX_ENTRIES, KEY_SIZE, key_compare);
574 : :
575 : : /* Sift through the list of keys and look for duplicates */
576 [ + + ]: 131072 : for (i = 0; i < MAX_ENTRIES - 1; i++) {
577 [ + + ]: 131070 : if (memcmp(generated_keys[i], generated_keys[i + 1],
578 : : KEY_SIZE) == 0) {
579 : : /* This key already exists, try again */
580 : 1 : num_duplicates++;
581 [ + + ]: 5 : for (j = 0; j < KEY_SIZE; j++)
582 : 4 : generated_keys[i][j] =
583 : 4 : rte_rand() & 0xFF;
584 : : }
585 : : }
586 [ + + ]: 2 : } while (num_duplicates != 0);
587 : 1 : }
588 : :
589 : : static inline int
590 : 3 : add_generated_keys(struct rte_member_setsum *setsum, unsigned int *added_keys)
591 : : {
592 : : int ret = 0;
593 : :
594 [ + + + - ]: 195591 : for (*added_keys = 0; ret >= 0 && *added_keys < MAX_ENTRIES;
595 : 195588 : (*added_keys)++) {
596 : 195588 : uint16_t set = (rte_rand() & 0xf) + 1;
597 : 195588 : ret = rte_member_add(setsum, &generated_keys[*added_keys], set);
598 : : }
599 : 3 : return ret;
600 : : }
601 : :
602 : : static inline int
603 : 3 : add_generated_keys_cache(struct rte_member_setsum *setsum,
604 : : unsigned int *added_keys)
605 : : {
606 : : int ret = 0;
607 : :
608 [ + + + - ]: 116541 : for (*added_keys = 0; ret == 0 && *added_keys < MAX_ENTRIES;
609 : 116538 : (*added_keys)++) {
610 : 116538 : uint16_t set = (rte_rand() & 0xf) + 1;
611 : 116538 : ret = rte_member_add(setsum, &generated_keys[*added_keys], set);
612 : : }
613 : 3 : return ret;
614 : : }
615 : :
616 : : static int
617 : 1 : test_member_loadfactor(void)
618 : : {
619 : : unsigned int j;
620 : : unsigned int added_keys, average_keys_added = 0;
621 : : int ret;
622 : :
623 : 1 : setup_keys_and_data();
624 : :
625 : 1 : rte_member_free(setsum_ht);
626 : 1 : rte_member_free(setsum_cache);
627 : 1 : rte_member_free(setsum_vbf);
628 : :
629 : 1 : params.key_len = KEY_SIZE;
630 : 1 : params.name = "test_member_ht";
631 : 1 : params.is_cache = 0;
632 : 1 : params.type = RTE_MEMBER_TYPE_HT;
633 : 1 : setsum_ht = rte_member_create(¶ms);
634 : :
635 : 1 : params.name = "test_member_cache";
636 : 1 : params.is_cache = 1;
637 : 1 : setsum_cache = rte_member_create(¶ms);
638 : :
639 : :
640 [ + - - + ]: 1 : if (setsum_ht == NULL || setsum_cache == NULL) {
641 : : printf("Creation of setsums fail\n");
642 : 0 : return -1;
643 : : }
644 : : /* Test HT non-cache mode */
645 [ + + ]: 4 : for (j = 0; j < ITERATIONS; j++) {
646 : : /* Add random entries until key cannot be added */
647 : 3 : ret = add_generated_keys(setsum_ht, &added_keys);
648 [ - + ]: 3 : if (ret != -ENOSPC) {
649 : : printf("Unexpected error when adding keys\n");
650 : 0 : return -1;
651 : : }
652 : 3 : average_keys_added += added_keys;
653 : :
654 : : /* Reset the table */
655 : 3 : rte_member_reset(setsum_ht);
656 : :
657 : : /* Print a dot to show progress on operations */
658 : : printf(".");
659 : 3 : fflush(stdout);
660 : : }
661 : :
662 : 1 : average_keys_added /= ITERATIONS;
663 : :
664 : 1 : printf("\nKeys inserted when no space(non-cache) = %.2f%% (%u/%u)\n",
665 : 1 : ((double) average_keys_added / params.num_keys * 100),
666 : : average_keys_added, params.num_keys);
667 : :
668 : : /* Test cache mode */
669 : 1 : added_keys = average_keys_added = 0;
670 [ + + ]: 4 : for (j = 0; j < ITERATIONS; j++) {
671 : : /* Add random entries until key cannot be added */
672 : 3 : ret = add_generated_keys_cache(setsum_cache, &added_keys);
673 [ - + ]: 3 : if (ret != 1) {
674 : : printf("Unexpected error when adding keys\n");
675 : 0 : return -1;
676 : : }
677 : 3 : average_keys_added += added_keys;
678 : :
679 : : /* Reset the table */
680 : 3 : rte_member_reset(setsum_cache);
681 : :
682 : : /* Print a dot to show progress on operations */
683 : : printf(".");
684 : 3 : fflush(stdout);
685 : : }
686 : :
687 : 1 : average_keys_added /= ITERATIONS;
688 : :
689 : 1 : printf("\nKeys inserted when eviction happens(cache)= %.2f%% (%u/%u)\n",
690 : 1 : ((double) average_keys_added / params.num_keys * 100),
691 : : average_keys_added, params.num_keys);
692 : 1 : return 0;
693 : : }
694 : :
695 : : static void
696 : 1 : perform_free(void)
697 : : {
698 : 1 : rte_member_free(setsum_ht);
699 : 1 : rte_member_free(setsum_cache);
700 : 1 : rte_member_free(setsum_vbf);
701 : 1 : }
702 : :
703 : : static void
704 : 7 : print_out_sketch_results(uint64_t *count_result, member_set_t *heavy_set,
705 : : uint32_t print_num, bool count_byte)
706 : : {
707 : : uint32_t i;
708 : :
709 [ + + ]: 147 : for (i = 0; i < print_num; i++) {
710 [ + + ]: 140 : if (count_byte)
711 : 20 : printf("key %2u, count %8"PRIu64", real count %8u, "
712 : : "heavy_set %u, deviation rate [%.04f]\n",
713 : : i, count_result[i],
714 : 20 : (unsigned int)ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)) *
715 : : HH_PKT_SIZE,
716 : 20 : heavy_set[i],
717 : 20 : fabs((double)count_result[i] - (double)NUM_OF_KEY(i) * HH_PKT_SIZE) /
718 : : ((double)NUM_OF_KEY(i) * HH_PKT_SIZE));
719 : : else
720 : 120 : printf("key %2u, count %8"PRIu64", real count %8u, "
721 : : "heavy_set %u, deviation rate [%.04f]\n",
722 : : i, count_result[i],
723 : 120 : (unsigned int)ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)),
724 : 120 : heavy_set[i],
725 : 120 : fabs((double)count_result[i] - (double)NUM_OF_KEY(i)) /
726 : : (double)NUM_OF_KEY(i));
727 : : }
728 : 7 : }
729 : :
730 : : static int
731 : 4 : sketch_test(uint32_t *keys, uint32_t total_pkt, int count_byte, int reset_test)
732 : : {
733 : : uint32_t i;
734 : : uint64_t result_count[SKETCH_TOTAL_KEY];
735 : : member_set_t heavy_set[SKETCH_TOTAL_KEY];
736 : : uint64_t count[TOP_K];
737 : : int ret;
738 : : int hh_cnt;
739 : :
740 : 4 : setsum_sketch = rte_member_create(¶ms);
741 [ - + ]: 4 : if (setsum_sketch == NULL) {
742 : : printf("Creation of setsums fail\n");
743 : 0 : return -1;
744 : : }
745 : :
746 [ + + ]: 27172320 : for (i = 0; i < total_pkt; i++) {
747 [ + + ]: 27172316 : if (count_byte)
748 : 6793079 : ret = rte_member_add_byte_count(setsum_sketch, &keys[i], HH_PKT_SIZE);
749 : : else
750 : 20379237 : ret = rte_member_add(setsum_sketch, &keys[i], 1);
751 : :
752 [ - + ]: 27172316 : if (ret < 0) {
753 : : printf("rte_member_add Failed! Error [%d]\n", ret);
754 : 0 : rte_member_free(setsum_sketch);
755 : :
756 : 0 : return -1;
757 : : }
758 : : }
759 : :
760 [ + + ]: 2004 : for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
761 : 2000 : uint32_t tmp_key = i;
762 : :
763 : 2000 : rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
764 : 2000 : rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
765 : : }
766 : :
767 : 4 : print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
768 : :
769 : 4 : hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
770 [ - + ]: 4 : if (hh_cnt < 0) {
771 : : printf("sketch report heavy hitter error!");
772 : 0 : rte_member_free(setsum_sketch);
773 : :
774 : 0 : return -1;
775 : : }
776 : :
777 : : printf("Report heavy hitters:");
778 [ + + ]: 44 : for (i = 0; i < (unsigned int)hh_cnt; i++) {
779 : 40 : printf("%u: %"PRIu64"\t",
780 : 40 : *((uint32_t *)heavy_hitters[i]), count[i]);
781 : : }
782 : : printf("\n");
783 : :
784 [ + + ]: 4 : if (reset_test) {
785 : : printf("\nEntering Sketch Reset Test Process!\n");
786 : 1 : rte_member_reset(setsum_sketch);
787 : :
788 : : /* after reset, check some key's count */
789 [ + + ]: 501 : for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
790 : 500 : uint32_t tmp_key = i;
791 : :
792 : 500 : rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
793 : 500 : rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
794 : : }
795 : :
796 : 1 : print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
797 : :
798 : : printf("\nReinsert keys after Sketch Reset!\n");
799 [ + + ]: 6793080 : for (i = 0; i < total_pkt; i++) {
800 [ - + ]: 6793079 : if (count_byte)
801 : 0 : ret = rte_member_add_byte_count
802 : 0 : (setsum_sketch, &keys[i], HH_PKT_SIZE);
803 : : else
804 : 6793079 : ret = rte_member_add(setsum_sketch, &keys[i], 1);
805 : :
806 [ - + ]: 6793079 : if (ret < 0) {
807 : : printf("rte_member_add Failed! Error [%d]\n", ret);
808 : 0 : rte_member_free(setsum_sketch);
809 : :
810 : 0 : return -1;
811 : : }
812 : : }
813 : :
814 [ + + ]: 501 : for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
815 : 500 : uint32_t tmp_key = i;
816 : :
817 : 500 : rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
818 : 500 : rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
819 : : }
820 : :
821 : 1 : print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
822 : :
823 : 1 : hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
824 [ - + ]: 1 : if (hh_cnt < 0) {
825 : : printf("sketch report heavy hitter error!");
826 : 0 : rte_member_free(setsum_sketch);
827 : :
828 : 0 : return -1;
829 : : }
830 : : printf("Report heavy hitters:");
831 [ + + ]: 11 : for (i = 0; i < (unsigned int)hh_cnt; i++) {
832 : 10 : printf("%u: %"PRIu64"\t",
833 : 10 : *((uint32_t *)heavy_hitters[i]), count[i]);
834 : : }
835 : : printf("\n");
836 : :
837 : : printf("\nDelete some keys!\n");
838 : 1 : uint32_t tmp_key = 0;
839 : :
840 : 1 : rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
841 : 1 : tmp_key = 1;
842 : 1 : rte_member_delete(setsum_sketch, (void *)&tmp_key, 0);
843 : :
844 [ + + ]: 501 : for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
845 : 500 : uint32_t tmp_key = i;
846 : :
847 : 500 : rte_member_query_count(setsum_sketch, (void *)&tmp_key, &result_count[i]);
848 : 500 : rte_member_lookup(setsum_sketch, (void *)&tmp_key, &heavy_set[i]);
849 : : }
850 : :
851 : 1 : print_out_sketch_results(result_count, heavy_set, PRINT_OUT_COUNT, count_byte);
852 : :
853 : 1 : hh_cnt = rte_member_report_heavyhitter(setsum_sketch, heavy_hitters, count);
854 [ - + ]: 1 : if (hh_cnt < 0) {
855 : : printf("sketch report heavy hitter error!");
856 : 0 : rte_member_free(setsum_sketch);
857 : :
858 : 0 : return -1;
859 : : }
860 : : printf("Report heavy hitters:");
861 [ + + ]: 9 : for (i = 0; i < (unsigned int)hh_cnt; i++) {
862 : 8 : printf("%u: %"PRIu64"\t",
863 : 8 : *((uint32_t *)heavy_hitters[i]), count[i]);
864 : : }
865 : : printf("\n");
866 : : }
867 : :
868 : 4 : rte_member_free(setsum_sketch);
869 : 4 : return 0;
870 : : }
871 : :
872 : : static int
873 : 1 : test_member_sketch(void)
874 : : {
875 : : unsigned int i, j, index;
876 : : uint32_t total_pkt = 0;
877 : : uint32_t *keys;
878 : : int count_byte = 0;
879 : :
880 [ + + ]: 501 : for (i = 0; i < SKETCH_TOTAL_KEY; i++)
881 : 500 : total_pkt += ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1));
882 : :
883 : : printf("\nTotal key count [%u] in Sketch Autotest\n", total_pkt);
884 : :
885 : 1 : keys = rte_zmalloc(NULL, sizeof(uint32_t) * total_pkt, 0);
886 : :
887 [ - + ]: 1 : if (keys == NULL) {
888 : : printf("RTE_ZMALLOC failed\n");
889 : 0 : return -1;
890 : : }
891 : :
892 : : index = 0;
893 [ + + ]: 501 : for (i = 0; i < SKETCH_TOTAL_KEY; i++) {
894 [ + + ]: 6793579 : for (j = 0; j < ceil((double)SKETCH_LARGEST_KEY_SIZE / (i + 1)); j++)
895 : 6793079 : keys[index++] = i;
896 : : }
897 : :
898 : : /* shuffle the keys */
899 [ + + ]: 6793079 : for (i = index - 1; i > 0; i--) {
900 : 6793078 : uint32_t swap_idx = rte_rand() % i;
901 : 6793078 : uint32_t tmp_key = keys[i];
902 : :
903 : 6793078 : keys[i] = keys[swap_idx];
904 : 6793078 : keys[swap_idx] = tmp_key;
905 : : }
906 : :
907 : 1 : params.key_len = 4;
908 : 1 : params.name = "test_member_sketch";
909 : 1 : params.type = RTE_MEMBER_TYPE_SKETCH;
910 : 1 : params.error_rate = SKETCH_ERROR_RATE;
911 : 1 : params.sample_rate = SKETCH_SAMPLE_RATE;
912 : 1 : params.extra_flag = 0;
913 : 1 : params.top_k = TOP_K;
914 : 1 : params.prim_hash_seed = rte_rdtsc();
915 : : int reset_test = 0;
916 : :
917 : : printf("Default sketching params: Error Rate: [%f]\tSample Rate: [%f]\tTopK: [%d]\n",
918 : : SKETCH_ERROR_RATE, SKETCH_SAMPLE_RATE, TOP_K);
919 : :
920 : : printf("\n[Sketch with Fixed Sampling Rate Mode]\n");
921 [ - + ]: 1 : if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) {
922 : 0 : rte_free(keys);
923 : 0 : return -1;
924 : : }
925 : :
926 : 1 : params.extra_flag |= RTE_MEMBER_SKETCH_ALWAYS_BOUNDED;
927 : : printf("\n[Sketch with Always Bounded Mode]\n");
928 [ - + ]: 1 : if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) {
929 : 0 : rte_free(keys);
930 : 0 : return -1;
931 : : }
932 : :
933 : : count_byte = 1;
934 : 1 : params.extra_flag |= RTE_MEMBER_SKETCH_COUNT_BYTE;
935 : : printf("\n[Sketch with Packet Size Mode]\n");
936 [ - + ]: 1 : if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) {
937 : 0 : rte_free(keys);
938 : 0 : return -1;
939 : : }
940 : :
941 : : count_byte = 0;
942 : 1 : params.extra_flag = 0;
943 : : reset_test = 1;
944 : : printf("\nreset sketch test\n");
945 [ - + ]: 1 : if (sketch_test(keys, total_pkt, count_byte, reset_test) < 0) {
946 : 0 : rte_free(keys);
947 : 0 : return -1;
948 : : }
949 : :
950 : 1 : rte_free(keys);
951 : 1 : return 0;
952 : : }
953 : :
954 : : static int
955 : 1 : test_member(void)
956 : : {
957 [ + - ]: 1 : if (test_member_create_bad_param() < 0)
958 : : return -1;
959 : :
960 [ + - ]: 1 : if (test_member_find_existing() < 0)
961 : : return -1;
962 : :
963 [ - + ]: 1 : if (test_member_create() < 0) {
964 : 0 : perform_free();
965 : 0 : return -1;
966 : : }
967 [ - + ]: 1 : if (test_member_insert() < 0) {
968 : 0 : perform_free();
969 : 0 : return -1;
970 : : }
971 [ - + ]: 1 : if (test_member_lookup() < 0) {
972 : 0 : perform_free();
973 : 0 : return -1;
974 : : }
975 [ - + ]: 1 : if (test_member_delete() < 0) {
976 : 0 : perform_free();
977 : 0 : return -1;
978 : : }
979 [ - + ]: 1 : if (test_member_multimatch() < 0) {
980 : 0 : perform_free();
981 : 0 : return -1;
982 : : }
983 [ - + ]: 1 : if (test_member_loadfactor() < 0) {
984 : 0 : rte_member_free(setsum_ht);
985 : 0 : rte_member_free(setsum_cache);
986 : 0 : return -1;
987 : : }
988 : :
989 [ - + ]: 1 : if (test_member_sketch() < 0) {
990 : 0 : perform_free();
991 : 0 : return -1;
992 : : }
993 : 1 : perform_free();
994 : 1 : return 0;
995 : : }
996 : :
997 : : #endif /* !RTE_EXEC_ENV_WINDOWS */
998 : :
999 : 251 : REGISTER_FAST_TEST(member_autotest, true, true, test_member);
|
