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