Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2023 Ericsson AB
3 : : */
4 : :
5 : : #include <inttypes.h>
6 : : #include <stdlib.h>
7 : :
8 : : #include <rte_bitset.h>
9 : : #include <rte_random.h>
10 : :
11 : : #include "test.h"
12 : :
13 : : #define MAGIC UINT64_C(0xdeadbeefdeadbeef)
14 : :
15 : : static void
16 : : rand_buf(void *buf, size_t n)
17 : : {
18 : : size_t i;
19 : :
20 [ + + + + : 10833911 : for (i = 0; i < n; i++)
+ + + + +
+ + + ]
21 : 10663904 : ((unsigned char *)buf)[i] = rte_rand();
22 : : }
23 : :
24 : : static uint64_t *
25 : 130005 : alloc_bitset(size_t size)
26 : : {
27 : : uint64_t *p;
28 : :
29 : 130005 : p = malloc(RTE_BITSET_SIZE(size) + 2 * sizeof(uint64_t));
30 [ - + ]: 130005 : if (p == NULL)
31 : 0 : rte_panic("Unable to allocate memory\n");
32 : :
33 : 130005 : rand_buf(&p[0], RTE_BITSET_SIZE(size));
34 : :
35 : 130005 : p[0] = MAGIC;
36 : 130005 : p[RTE_BITSET_NUM_WORDS(size) + 1] = MAGIC;
37 : :
38 : 130005 : return p + 1;
39 : : }
40 : :
41 : :
42 : : static int
43 : 130005 : free_bitset(uint64_t *bitset, size_t size)
44 : : {
45 : : uint64_t *p;
46 : :
47 : 130005 : p = bitset - 1;
48 : :
49 [ + - ]: 130005 : if (p[0] != MAGIC)
50 : : return TEST_FAILED;
51 : :
52 [ + - ]: 130005 : if (p[RTE_BITSET_NUM_WORDS(size) + 1] != MAGIC)
53 : : return TEST_FAILED;
54 : :
55 : 130005 : free(p);
56 : :
57 : 130005 : return TEST_SUCCESS;
58 : : }
59 : :
60 : : static bool
61 : : rand_bool(void)
62 : : {
63 : 30983712 : return rte_rand_max(2);
64 : : }
65 : :
66 : : static void
67 : : rand_bool_ary(bool *ary, size_t len)
68 : : {
69 : : size_t i;
70 : :
71 [ + + + + : 29996047 : for (i = 0; i < len; i++)
+ + + + ]
72 : 29936044 : ary[i] = rand_bool();
73 : : }
74 : :
75 : : static void
76 : 80005 : rand_unused_bits(uint64_t *bitset, size_t size)
77 : : {
78 : 80005 : uint64_t bits = rte_rand() & ~__RTE_BITSET_USED_MASK(size);
79 : :
80 : 80005 : bitset[RTE_BITSET_NUM_WORDS(size) - 1] |= bits;
81 : 80005 : }
82 : :
83 : : static void
84 : 30000 : rand_bitset(uint64_t *bitset, size_t size)
85 : : {
86 : : size_t i;
87 : :
88 : : rte_bitset_init(bitset, size);
89 : :
90 [ + + ]: 14989680 : for (i = 0; i < size; i++)
91 : : rte_bitset_assign(bitset, i, rand_bool());
92 : :
93 : 30000 : rand_unused_bits(bitset, size);
94 : 30000 : }
95 : :
96 : : typedef bool test_fun(const uint64_t *bitset, size_t bit_num);
97 : : typedef void set_fun(uint64_t *bitset, size_t bit_num);
98 : : typedef void clear_fun(uint64_t *bitset, size_t bit_num);
99 : : typedef void assign_fun(uint64_t *bitset, size_t bit_num, bool value);
100 : : typedef void flip_fun(uint64_t *bitset, size_t bit_num);
101 : :
102 : : static int
103 : 20000 : test_set_clear_size(test_fun test_fun, set_fun set_fun, clear_fun clear_fun, size_t size)
104 : 20000 : {
105 : : size_t i;
106 : 20000 : bool reference[size];
107 : : uint64_t *bitset;
108 : :
109 : : rand_bool_ary(reference, size);
110 : :
111 : 20000 : bitset = alloc_bitset(size);
112 : :
113 [ - + ]: 20000 : TEST_ASSERT(bitset != NULL, "Failed to allocate memory");
114 : :
115 : : rte_bitset_init(bitset, size);
116 : :
117 [ + + ]: 10023446 : for (i = 0; i < size; i++) {
118 [ + + ]: 10003446 : if (reference[i])
119 : 5000958 : set_fun(bitset, i);
120 : : else
121 : 5002488 : clear_fun(bitset, i);
122 : : }
123 : :
124 [ + + ]: 10023446 : for (i = 0; i < size; i++)
125 [ + - ]: 10003446 : if (reference[i] != test_fun(bitset, i))
126 : : return TEST_FAILED;
127 : :
128 [ - + ]: 20000 : TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS,
129 : : "Buffer over- or underrun detected");
130 : :
131 : : return TEST_SUCCESS;
132 : : }
133 : :
134 : : #define RAND_ITERATIONS (10000)
135 : : #define RAND_SET_MAX_SIZE (1000)
136 : :
137 : : static int
138 : 2 : test_set_clear_fun(test_fun test_fun, set_fun set_fun, clear_fun clear_fun)
139 : : {
140 : : size_t i;
141 : :
142 [ + + ]: 20002 : for (i = 0; i < RAND_ITERATIONS; i++) {
143 : 20000 : size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
144 : :
145 [ + - ]: 20000 : if (test_set_clear_size(test_fun, set_fun, clear_fun, size) != TEST_SUCCESS)
146 : : return TEST_FAILED;
147 : : }
148 : :
149 : : return TEST_SUCCESS;
150 : : }
151 : :
152 : : static int
153 : 1 : test_set_clear(void)
154 : : {
155 : 1 : return test_set_clear_fun(rte_bitset_test, rte_bitset_set, rte_bitset_clear);
156 : : }
157 : :
158 : : static int
159 : 20000 : test_flip_size(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun, size_t size)
160 : : {
161 : : size_t i;
162 : : uint64_t *bitset;
163 : :
164 : 20000 : bitset = alloc_bitset(size);
165 : :
166 [ - + ]: 20000 : TEST_ASSERT(bitset != NULL, "Failed to allocate memory");
167 : :
168 : 20000 : rand_bitset(bitset, size);
169 : :
170 [ + + ]: 10034614 : for (i = 0; i < size; i++) {
171 : 10014614 : RTE_BITSET_DECLARE(reference, size);
172 : :
173 : 10014614 : rte_bitset_copy(reference, bitset, size);
174 : :
175 : 10014614 : bool value = test_fun(bitset, i);
176 : :
177 : 10014614 : flip_fun(bitset, i);
178 : :
179 [ - + ]: 10014614 : TEST_ASSERT(test_fun(bitset, i) != value, "Bit %zd was not flipped", i);
180 : :
181 : 10014614 : assign_fun(reference, i, !value);
182 : :
183 [ - + ]: 10014614 : TEST_ASSERT(rte_bitset_equal(bitset, reference, size),
184 : : "Not only the target bit %zd was flipped", i);
185 : :
186 : :
187 : : }
188 : :
189 [ - + ]: 20000 : TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS,
190 : : "Buffer over- or underrun detected");
191 : :
192 : : return TEST_SUCCESS;
193 : : }
194 : :
195 : : static int
196 : 2 : test_flip_fun(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun)
197 : : {
198 : : size_t i;
199 : :
200 [ + + ]: 20002 : for (i = 0; i < RAND_ITERATIONS; i++) {
201 : 20000 : size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
202 : :
203 [ + - ]: 20000 : if (test_flip_size(test_fun, assign_fun, flip_fun, size) != TEST_SUCCESS)
204 : : return TEST_FAILED;
205 : : }
206 : :
207 : : return TEST_SUCCESS;
208 : : }
209 : :
210 : : static int
211 : 1 : test_flip(void)
212 : : {
213 : 1 : return test_flip_fun(rte_bitset_test, rte_bitset_assign, rte_bitset_flip);
214 : : }
215 : :
216 : : static bool
217 : 15049302 : bitset_atomic_test(const uint64_t *bitset, size_t bit_num)
218 : : {
219 : 15049302 : return rte_bitset_atomic_test(bitset, bit_num, rte_memory_order_relaxed);
220 : : }
221 : :
222 : : static void
223 : 2504079 : bitset_atomic_set(uint64_t *bitset, size_t bit_num)
224 : : {
225 : : rte_bitset_atomic_set(bitset, bit_num, rte_memory_order_relaxed);
226 : 2504079 : }
227 : :
228 : : static void
229 : 2504509 : bitset_atomic_clear(uint64_t *bitset, size_t bit_num)
230 : : {
231 : : rte_bitset_atomic_clear(bitset, bit_num, rte_memory_order_relaxed);
232 : 2504509 : }
233 : :
234 : : static void
235 : 5020357 : bitset_atomic_flip(uint64_t *bitset, size_t bit_num)
236 : : {
237 : : rte_bitset_atomic_flip(bitset, bit_num, rte_memory_order_relaxed);
238 : 5020357 : }
239 : :
240 : : static void
241 : 5020357 : bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value)
242 : : {
243 : 5020357 : rte_bitset_atomic_assign(bitset, bit_num, bit_value, rte_memory_order_relaxed);
244 : 5020357 : }
245 : :
246 : : static int
247 : 1 : test_atomic_set_clear(void)
248 : : {
249 : 1 : return test_set_clear_fun(bitset_atomic_test, bitset_atomic_set, bitset_atomic_clear);
250 : : }
251 : :
252 : : static int
253 : 1 : test_atomic_flip(void)
254 : : {
255 : 1 : return test_flip_fun(bitset_atomic_test, bitset_atomic_assign, bitset_atomic_flip);
256 : : }
257 : :
258 : : static ssize_t
259 : : find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set)
260 : : {
261 : : size_t i;
262 : :
263 [ + + + + ]: 3976035 : for (i = 0; i < len; i++) {
264 : 3953345 : ssize_t idx = (start + i) % num_bools;
265 : :
266 [ + + + + ]: 3953345 : if (ary[idx] == set)
267 : : return idx;
268 : : }
269 : :
270 : : return -1;
271 : : }
272 : :
273 : : static ssize_t
274 : : find_set(const bool *ary, size_t num_bools, size_t start, size_t len)
275 : : {
276 : : return find(ary, num_bools, start, len, true);
277 : : }
278 : :
279 : : static ssize_t
280 : : find_clear(const bool *ary, size_t num_bools, size_t start, size_t len)
281 : : {
282 : : return find(ary, num_bools, start, len, false);
283 : : }
284 : :
285 : : #define FFS_ITERATIONS (100)
286 : :
287 : : static int
288 : 20000 : test_find_size(size_t size, bool set)
289 : 20000 : {
290 : : uint64_t *bitset;
291 : 20000 : bool reference[size];
292 : : size_t i;
293 : :
294 : 20000 : bitset = alloc_bitset(size);
295 : :
296 [ - + ]: 20000 : TEST_ASSERT(bitset != NULL, "Failed to allocate memory");
297 : :
298 : : rte_bitset_init(bitset, size);
299 : :
300 [ + + ]: 10008580 : for (i = 0; i < size; i++) {
301 : : bool bit = rand_bool();
302 : 9988580 : reference[i] = bit;
303 : :
304 [ + + ]: 9988580 : if (bit)
305 : : rte_bitset_set(bitset, i);
306 : : else /* redundant, still useful for testing */
307 : : rte_bitset_clear(bitset, i);
308 : : }
309 : :
310 [ + + ]: 2020000 : for (i = 0; i < FFS_ITERATIONS; i++) {
311 : 2000000 : size_t start_bit = rte_rand_max(size);
312 : 2000000 : size_t len = rte_rand_max(size + 1);
313 : 2000000 : bool full_range = len == size && start_bit == 0;
314 : 2000000 : bool wraps = start_bit + len > size;
315 : : ssize_t rc;
316 : :
317 [ + + ]: 2000000 : if (set) {
318 [ + + + + ]: 1000416 : if (full_range && rand_bool())
319 : 218 : rc = rte_bitset_find_first_set(bitset, size);
320 [ + + + + ]: 1505019 : else if (wraps || rand_bool())
321 : 747219 : rc = rte_bitset_find_set_wrap(bitset, size, start_bit, len);
322 : : else
323 : : rc = rte_bitset_find_set(bitset, size, start_bit, len);
324 : :
325 [ + - ]: 1000000 : if (rc != find_set(reference, size, start_bit, len))
326 : : return TEST_FAILED;
327 : : } else {
328 [ + + + + ]: 1000392 : if (full_range && rand_bool())
329 : 193 : rc = rte_bitset_find_first_clear(bitset, size);
330 [ + + + + ]: 1505394 : else if (wraps || rand_bool())
331 : 747478 : rc = rte_bitset_find_clear_wrap(bitset, size, start_bit, len);
332 : : else
333 : : rc = rte_bitset_find_clear(bitset, size, start_bit, len);
334 : :
335 [ + - ]: 1000000 : if (rc != find_clear(reference, size, start_bit, len))
336 : : return TEST_FAILED;
337 : : }
338 : :
339 : : }
340 : :
341 [ - + ]: 20000 : TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS,
342 : : "Buffer over- or underrun detected");
343 : :
344 : : return TEST_SUCCESS;
345 : : }
346 : :
347 : : static int
348 : : test_find_set_size(size_t size)
349 : : {
350 : 10000 : return test_find_size(size, true);
351 : : }
352 : :
353 : : static int
354 : : test_find_clear_size(size_t size)
355 : : {
356 : 10000 : return test_find_size(size, false);
357 : : }
358 : :
359 : : static int
360 : 1 : test_find(void)
361 : : {
362 : : size_t i;
363 : :
364 [ + + ]: 10001 : for (i = 0; i < RAND_ITERATIONS; i++) {
365 : 10000 : size_t size = 2 + rte_rand_max(RAND_SET_MAX_SIZE - 2);
366 : :
367 [ + - ]: 10000 : if (test_find_set_size(size) != TEST_SUCCESS)
368 : : return TEST_FAILED;
369 : :
370 [ + - ]: 10000 : if (test_find_clear_size(size) != TEST_SUCCESS)
371 : : return TEST_FAILED;
372 : : }
373 : :
374 : : return TEST_SUCCESS;
375 : : }
376 : :
377 : : static int
378 : : record_match(ssize_t match_idx, size_t size, int *calls)
379 : : {
380 [ + - + - : 3779774 : if (match_idx < 0 || (size_t)match_idx >= size)
+ - + - +
- + - ]
381 : : return TEST_FAILED;
382 : :
383 : 3779774 : calls[match_idx]++;
384 : :
385 : : return TEST_SUCCESS;
386 : : }
387 : :
388 : : static int
389 : 40000 : test_foreach_size(ssize_t size, bool may_wrap, bool set)
390 : 40000 : {
391 : 40000 : bool reference[size];
392 : 40000 : int calls[size];
393 : : uint64_t *bitset;
394 : : ssize_t i;
395 : : ssize_t start_bit;
396 : : ssize_t len;
397 : : bool full_range;
398 : : size_t total_calls = 0;
399 : :
400 : : rand_bool_ary(reference, size);
401 : :
402 : 40000 : bitset = alloc_bitset(size);
403 : :
404 [ - + ]: 40000 : TEST_ASSERT(bitset != NULL, "Failed to allocate memory");
405 : :
406 : : memset(calls, 0, sizeof(calls));
407 : :
408 : 40000 : start_bit = rte_rand_max(size);
409 [ + + ]: 60000 : len = may_wrap ? rte_rand_max(size + 1) :
410 : 20000 : rte_rand_max(size - start_bit + 1);
411 : :
412 : : rte_bitset_init(bitset, size);
413 : :
414 : : /* random data in the unused bits should not matter */
415 : 40000 : rand_buf(bitset, RTE_BITSET_SIZE(size));
416 : :
417 [ + + ]: 7595417 : for (i = start_bit; i < start_bit + len; i++) {
418 : 7555417 : size_t idx = i % size;
419 : :
420 [ + + ]: 7555417 : if (reference[idx])
421 : : rte_bitset_set(bitset, idx);
422 : : else
423 : : rte_bitset_clear(bitset, idx);
424 : :
425 [ + - ]: 7555417 : if (rte_bitset_test(bitset, idx) != reference[idx])
426 : : return TEST_FAILED;
427 : : }
428 : :
429 : 40000 : full_range = (len == size && start_bit == 0);
430 : :
431 : : /* XXX: verify iteration order as well */
432 [ + + ]: 40000 : if (set) {
433 [ + + + + ]: 20021 : if (full_range && rand_bool()) {
434 [ + + + + ]: 28 : RTE_BITSET_FOREACH_SET(i, bitset, size) {
435 : : if (record_match(i, size, calls) != TEST_SUCCESS)
436 : : return TEST_FAILED;
437 : : }
438 [ + + ]: 19989 : } else if (may_wrap) {
439 [ + + + + : 1260124 : RTE_BITSET_FOREACH_SET_WRAP(i, bitset, size, start_bit, len) {
+ + ]
440 : : if (record_match(i, size, calls) != TEST_SUCCESS) {
441 : : printf("failed\n");
442 : 0 : return TEST_FAILED;
443 : : }
444 : : }
445 : : } else {
446 [ + - + + : 651202 : RTE_BITSET_FOREACH_SET_RANGE(i, bitset, size, start_bit, len) {
+ + ]
447 : : if (record_match(i, size, calls) != TEST_SUCCESS)
448 : : return TEST_FAILED;
449 : : }
450 : : }
451 : : } else {
452 [ + + + + ]: 20013 : if (full_range && rand_bool()) {
453 [ + + + + ]: 28 : RTE_BITSET_FOREACH_CLEAR(i, bitset, size)
454 : : if (record_match(i, size, calls) != TEST_SUCCESS)
455 : : return TEST_FAILED;
456 [ + + ]: 19995 : } else if (may_wrap) {
457 [ + + + + : 1258607 : RTE_BITSET_FOREACH_CLEAR_WRAP(i, bitset, size, start_bit, len) {
+ + ]
458 : : if (record_match(i, size, calls) != TEST_SUCCESS)
459 : : return TEST_FAILED;
460 : : }
461 : : } else {
462 [ + - + + : 649785 : RTE_BITSET_FOREACH_CLEAR_RANGE(i, bitset, size, start_bit, len)
+ + ]
463 : : if (record_match(i, size, calls) != TEST_SUCCESS)
464 : : return TEST_FAILED;
465 : : }
466 : : }
467 : :
468 [ + + ]: 7595417 : for (i = 0; i < len; i++) {
469 : 7555417 : size_t idx = (start_bit + i) % size;
470 : :
471 [ + + - + ]: 7555417 : if (reference[idx] == set && calls[idx] != 1) {
472 : : printf("bit %zd shouldn't have been found %d times\n", idx, calls[idx]);
473 : 0 : return TEST_FAILED;
474 : : }
475 : :
476 [ + + - + ]: 7555417 : if (reference[idx] != set && calls[idx] != 0) {
477 : 0 : puts("bar");
478 : 0 : return TEST_FAILED;
479 : : }
480 : :
481 : 7555417 : total_calls += calls[idx];
482 : : }
483 : :
484 [ + + ]: 40000 : if (full_range) {
485 : : size_t count;
486 : :
487 [ + + ]: 34 : count = set ? rte_bitset_count_set(bitset, size) :
488 : : rte_bitset_count_clear(bitset, size);
489 : :
490 [ + - ]: 34 : if (count != total_calls)
491 : : return TEST_FAILED;
492 : : }
493 : :
494 [ - + ]: 40000 : TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS,
495 : : "Buffer over- or underrun detected");
496 : :
497 : : return TEST_SUCCESS;
498 : : }
499 : :
500 : : static int
501 : 1 : test_foreach(void)
502 : : {
503 : : size_t i;
504 : :
505 [ + + ]: 10001 : for (i = 0; i < RAND_ITERATIONS; i++) {
506 : 10000 : size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
507 : :
508 [ + - ]: 10000 : if (test_foreach_size(size, false, true) != TEST_SUCCESS)
509 : : return TEST_FAILED;
510 : :
511 [ + - ]: 10000 : if (test_foreach_size(size, false, false) != TEST_SUCCESS)
512 : : return TEST_FAILED;
513 : :
514 [ + - ]: 10000 : if (test_foreach_size(size, true, true) != TEST_SUCCESS)
515 : : return TEST_FAILED;
516 : :
517 [ + - ]: 10000 : if (test_foreach_size(size, true, false) != TEST_SUCCESS)
518 : : return TEST_FAILED;
519 : : }
520 : :
521 : : return TEST_SUCCESS;
522 : : }
523 : :
524 : : static int
525 : 10005 : test_count_size(size_t size)
526 : : {
527 : : uint64_t *bitset;
528 : :
529 : 10005 : bitset = alloc_bitset(size);
530 : :
531 [ - + ]: 10005 : TEST_ASSERT(bitset != NULL, "Failed to allocate memory");
532 : :
533 : : rte_bitset_init(bitset, size);
534 : :
535 : 10005 : rand_unused_bits(bitset, size);
536 : :
537 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != 0)
538 : : return TEST_FAILED;
539 : :
540 : : if (rte_bitset_count_clear(bitset, size) != size)
541 : : return TEST_FAILED;
542 : :
543 : : rte_bitset_set_all(bitset, size);
544 : :
545 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != size)
546 : : return TEST_FAILED;
547 : :
548 : : if (rte_bitset_count_clear(bitset, size) != 0)
549 : : return TEST_FAILED;
550 : :
551 : : rte_bitset_clear_all(bitset, size);
552 : :
553 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != 0)
554 : : return TEST_FAILED;
555 : :
556 : : if (rte_bitset_count_clear(bitset, size) != size)
557 : : return TEST_FAILED;
558 : :
559 : 10005 : rte_bitset_set(bitset, rte_rand_max(size));
560 : :
561 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != 1)
562 : : return TEST_FAILED;
563 : :
564 : : if (rte_bitset_count_clear(bitset, size) != (size - 1))
565 : : return TEST_FAILED;
566 : :
567 : : rte_bitset_clear_all(bitset, size);
568 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != 0)
569 : : return TEST_FAILED;
570 : : if (rte_bitset_count_clear(bitset, size) != size)
571 : : return TEST_FAILED;
572 : :
573 : : rte_bitset_set_all(bitset, size);
574 [ + - ]: 10005 : if (rte_bitset_count_set(bitset, size) != size)
575 : : return TEST_FAILED;
576 : : if (rte_bitset_count_clear(bitset, size) != 0)
577 : : return TEST_FAILED;
578 : :
579 [ - + ]: 10005 : TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS,
580 : : "Buffer over- or underrun detected");
581 : :
582 : : return TEST_SUCCESS;
583 : : }
584 : :
585 : : static int
586 : 1 : test_count(void)
587 : : {
588 : : size_t i;
589 : :
590 [ + - ]: 1 : if (test_count_size(128) != TEST_SUCCESS)
591 : : return TEST_FAILED;
592 [ + - ]: 1 : if (test_count_size(1) != TEST_SUCCESS)
593 : : return TEST_FAILED;
594 [ + - ]: 1 : if (test_count_size(63) != TEST_SUCCESS)
595 : : return TEST_FAILED;
596 [ + - ]: 1 : if (test_count_size(64) != TEST_SUCCESS)
597 : : return TEST_FAILED;
598 [ + - ]: 1 : if (test_count_size(65) != TEST_SUCCESS)
599 : : return TEST_FAILED;
600 : :
601 [ + + ]: 10001 : for (i = 0; i < RAND_ITERATIONS; i++) {
602 : 10000 : size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
603 : :
604 [ + - ]: 10000 : if (test_count_size(size) != TEST_SUCCESS)
605 : : return TEST_FAILED;
606 : : }
607 : :
608 : : return TEST_SUCCESS;
609 : : }
610 : :
611 : : #define GEN_DECLARE(size) \
612 : : { \
613 : : RTE_BITSET_DECLARE(bitset, size); \
614 : : size_t idx = rte_rand_max(size); \
615 : : rte_bitset_init(bitset, size); \
616 : : rte_bitset_set(bitset, idx); \
617 : : if (!rte_bitset_test(bitset, idx)) \
618 : : return TEST_FAILED; \
619 : : if (rte_bitset_count_set(bitset, size) != 1) \
620 : : return TEST_FAILED; \
621 : : return TEST_SUCCESS; \
622 : : }
623 : :
624 : : static int
625 : 1 : test_define(void)
626 : : {
627 [ - + ]: 1 : GEN_DECLARE(1);
628 : : GEN_DECLARE(64);
629 : : GEN_DECLARE(65);
630 : : GEN_DECLARE(4097);
631 : : }
632 : :
633 : : typedef void bitset_op(uint64_t *dst, const uint64_t *a, const uint64_t *b, size_t bit_num);
634 : : typedef bool bool_op(bool a, bool b);
635 : :
636 : : static int
637 : 3 : test_logic_op(bitset_op bitset_op, bool_op bool_op)
638 : 3 : {
639 : 3 : const size_t size = 1 + rte_rand_max(200);
640 : 3 : RTE_BITSET_DECLARE(bitset_a, size);
641 : 3 : RTE_BITSET_DECLARE(bitset_b, size);
642 : 3 : RTE_BITSET_DECLARE(bitset_d, size);
643 : :
644 : 3 : bool ary_a[size];
645 : 3 : bool ary_b[size];
646 : 3 : bool ary_d[size];
647 : :
648 : : rand_bool_ary(ary_a, size);
649 : : rand_bool_ary(ary_b, size);
650 : :
651 : : size_t i;
652 [ + + ]: 428 : for (i = 0; i < size; i++) {
653 [ + + ]: 425 : rte_bitset_assign(bitset_a, i, ary_a[i]);
654 [ + + ]: 425 : rte_bitset_assign(bitset_b, i, ary_b[i]);
655 : 425 : ary_d[i] = bool_op(ary_a[i], ary_b[i]);
656 : : }
657 : :
658 : 3 : bitset_op(bitset_d, bitset_a, bitset_b, size);
659 : :
660 [ + + ]: 428 : for (i = 0; i < size; i++)
661 [ - + ]: 425 : TEST_ASSERT_EQUAL(rte_bitset_test(bitset_d, i), ary_d[i],
662 : : "Unexpected value of bit %zd", i);
663 : :
664 : : return TEST_SUCCESS;
665 : : }
666 : :
667 : : static bool
668 : 161 : bool_or(bool a, bool b)
669 : : {
670 : 161 : return a || b;
671 : : }
672 : :
673 : : static int
674 : 1 : test_or(void)
675 : : {
676 : 1 : return test_logic_op(rte_bitset_or, bool_or);
677 : : }
678 : :
679 : : static bool
680 : 194 : bool_and(bool a, bool b)
681 : : {
682 : 194 : return a && b;
683 : : }
684 : :
685 : : static int
686 : 1 : test_and(void)
687 : : {
688 : 1 : return test_logic_op(rte_bitset_and, bool_and);
689 : : }
690 : :
691 : : static bool
692 : 70 : bool_xor(bool a, bool b)
693 : : {
694 : 70 : return a != b;
695 : : }
696 : :
697 : : static int
698 : 1 : test_xor(void)
699 : : {
700 : 1 : return test_logic_op(rte_bitset_xor, bool_xor);
701 : : }
702 : :
703 : : static int
704 : 1 : test_complement(void)
705 : : {
706 : : int i;
707 : :
708 [ + + ]: 10001 : for (i = 0; i < RAND_ITERATIONS; i++) {
709 : 10000 : const size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
710 : :
711 : 10000 : RTE_BITSET_DECLARE(src, size);
712 : :
713 : 10000 : rand_bitset(src, size);
714 : :
715 : 10000 : bool bit_idx = rte_rand_max(size);
716 : : bool bit_value = rte_bitset_test(src, bit_idx);
717 : :
718 : 10000 : RTE_BITSET_DECLARE(dst, size);
719 : :
720 : : rte_bitset_complement(dst, src, size);
721 : :
722 [ - + ]: 10000 : TEST_ASSERT(bit_value != rte_bitset_test(dst, bit_idx),
723 : : "Bit %d was not flipped", bit_idx);
724 : : }
725 : :
726 : : return TEST_SUCCESS;
727 : : }
728 : :
729 : : static int
730 : 2 : test_shift(bool right)
731 : : {
732 : : int i;
733 : :
734 [ + + ]: 2 : const char *direction = right ? "right" : "left";
735 : :
736 [ + + ]: 20002 : for (i = 0; i < 10000; i++) {
737 : 20000 : const int size = 1 + (int)rte_rand_max(500);
738 : 20000 : const int shift_count = (int)rte_rand_max(1.5 * size);
739 : : int src_idx;
740 : :
741 : 20000 : RTE_BITSET_DECLARE(src, size);
742 : 20000 : RTE_BITSET_DECLARE(reference, size);
743 : :
744 : : rte_bitset_init(src, size);
745 : : rte_bitset_init(reference, size);
746 : :
747 : 20000 : rand_unused_bits(src, size);
748 : 20000 : rand_unused_bits(reference, size);
749 : :
750 [ + + ]: 5043786 : for (src_idx = 0; src_idx < size; src_idx++) {
751 : : bool value = rand_bool();
752 : :
753 [ + + ]: 5023786 : rte_bitset_assign(src, src_idx, value);
754 : :
755 [ + + ]: 5023786 : int dst_idx = right ? src_idx - shift_count : src_idx + shift_count;
756 : :
757 [ + + ]: 5023786 : if (dst_idx >= 0 && dst_idx < size)
758 [ + + ]: 1681498 : rte_bitset_assign(reference, dst_idx, value);
759 : : }
760 : :
761 : 20000 : uint64_t *dst = alloc_bitset(size);
762 : :
763 [ + + ]: 20000 : if (right)
764 : 10000 : rte_bitset_shift_right(dst, src, size, shift_count);
765 : : else
766 : 10000 : rte_bitset_shift_left(dst, src, size, shift_count);
767 : :
768 [ - + ]: 20000 : TEST_ASSERT(rte_bitset_equal(dst, reference, size),
769 : : "Unexpected result from shifting bitset of size %d bits %d bits %s",
770 : : size, shift_count, direction);
771 : :
772 [ - + ]: 20000 : TEST_ASSERT_EQUAL(free_bitset(dst, size), TEST_SUCCESS,
773 : : "Shift %s operation overwrote buffer", direction);
774 : : }
775 : :
776 : : return TEST_SUCCESS;
777 : : }
778 : :
779 : : static int
780 : 1 : test_shift_right(void)
781 : : {
782 : 1 : return test_shift(true);
783 : : }
784 : :
785 : : static int
786 : 1 : test_shift_left(void)
787 : : {
788 : 1 : return test_shift(false);
789 : : }
790 : :
791 : : static int
792 : 1 : test_equal(void)
793 : 1 : {
794 : : const size_t size = 100;
795 : : RTE_BITSET_DECLARE(bitset_a, size);
796 : : RTE_BITSET_DECLARE(bitset_b, size);
797 : :
798 : : rand_buf(bitset_a, RTE_BITSET_SIZE(size));
799 : : rand_buf(bitset_b, RTE_BITSET_SIZE(size));
800 : :
801 : : rte_bitset_init(bitset_a, size);
802 : : rte_bitset_init(bitset_b, size);
803 : :
804 : : rte_bitset_set(bitset_a, 9);
805 : : rte_bitset_set(bitset_b, 9);
806 : : rte_bitset_set(bitset_a, 90);
807 : : rte_bitset_set(bitset_b, 90);
808 : :
809 [ + - ]: 1 : if (!rte_bitset_equal(bitset_a, bitset_b, size))
810 : : return TEST_FAILED;
811 : :
812 : : /* set unused bit, which should be ignored */
813 : : rte_bitset_set(&bitset_a[1], 60);
814 : :
815 [ - + ]: 1 : if (!rte_bitset_equal(bitset_a, bitset_b, size))
816 : 0 : return TEST_FAILED;
817 : :
818 : : return TEST_SUCCESS;
819 : : }
820 : :
821 : : static int
822 : 1 : test_copy(void)
823 : 1 : {
824 : : const size_t size = 100;
825 : : RTE_BITSET_DECLARE(bitset_a, size);
826 : : RTE_BITSET_DECLARE(bitset_b, size);
827 : :
828 : : rand_buf(bitset_a, RTE_BITSET_SIZE(size));
829 : : rand_buf(bitset_b, RTE_BITSET_SIZE(size));
830 : :
831 : : rte_bitset_copy(bitset_a, bitset_b, size);
832 : :
833 [ - + ]: 1 : if (!rte_bitset_equal(bitset_a, bitset_b, size))
834 : 0 : return TEST_FAILED;
835 : :
836 : : return TEST_SUCCESS;
837 : : }
838 : :
839 : : static int
840 : 1 : test_to_str(void)
841 : : {
842 : : char buf[1024];
843 : : RTE_BITSET_DECLARE(bitset, 128);
844 : :
845 : : rte_bitset_init(bitset, 128);
846 : : rte_bitset_set(bitset, 1);
847 : :
848 [ + - ]: 1 : if (rte_bitset_to_str(bitset, 2, buf, 3) != 3)
849 : : return TEST_FAILED;
850 [ + - ]: 1 : if (strcmp(buf, "10") != 0)
851 : : return TEST_FAILED;
852 : :
853 : : rte_bitset_set(bitset, 0);
854 : :
855 [ + - ]: 1 : if (rte_bitset_to_str(bitset, 1, buf, sizeof(buf)) != 2)
856 : : return TEST_FAILED;
857 [ + - ]: 1 : if (strcmp(buf, "1") != 0)
858 : : return TEST_FAILED;
859 : :
860 : : rte_bitset_init(bitset, 99);
861 : : rte_bitset_set(bitset, 98);
862 : :
863 [ + - ]: 1 : if (rte_bitset_to_str(bitset, 99, buf, sizeof(buf)) != 100)
864 : : return TEST_FAILED;
865 : :
866 [ + - + - ]: 1 : if (buf[0] != '1' || strchr(&buf[1], '1') != NULL)
867 : : return TEST_FAILED;
868 : :
869 [ - + ]: 1 : if (rte_bitset_to_str(bitset, 128, buf, 64) != -EINVAL)
870 : 0 : return TEST_FAILED;
871 : :
872 : : return TEST_SUCCESS;
873 : : }
874 : :
875 : : static struct unit_test_suite bitset_tests = {
876 : : .suite_name = "bitset test suite",
877 : : .unit_test_cases = {
878 : : TEST_CASE_ST(NULL, NULL, test_set_clear),
879 : : TEST_CASE_ST(NULL, NULL, test_flip),
880 : : TEST_CASE_ST(NULL, NULL, test_atomic_set_clear),
881 : : TEST_CASE_ST(NULL, NULL, test_atomic_flip),
882 : : TEST_CASE_ST(NULL, NULL, test_find),
883 : : TEST_CASE_ST(NULL, NULL, test_foreach),
884 : : TEST_CASE_ST(NULL, NULL, test_count),
885 : : TEST_CASE_ST(NULL, NULL, test_define),
886 : : TEST_CASE_ST(NULL, NULL, test_or),
887 : : TEST_CASE_ST(NULL, NULL, test_and),
888 : : TEST_CASE_ST(NULL, NULL, test_xor),
889 : : TEST_CASE_ST(NULL, NULL, test_complement),
890 : : TEST_CASE_ST(NULL, NULL, test_shift_right),
891 : : TEST_CASE_ST(NULL, NULL, test_shift_left),
892 : : TEST_CASE_ST(NULL, NULL, test_equal),
893 : : TEST_CASE_ST(NULL, NULL, test_copy),
894 : : TEST_CASE_ST(NULL, NULL, test_to_str),
895 : : TEST_CASES_END()
896 : : }
897 : : };
898 : :
899 : : static int
900 : 1 : test_bitset(void)
901 : : {
902 : 1 : return unit_test_suite_runner(&bitset_tests);
903 : : }
904 : :
905 : 251 : REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset);
|
