1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright (C) 2016 Intel Corporation.
3 * All rights reserved.
4 */
5
6 #include "spdk/stdinc.h"
7
8 #include "spdk_internal/cunit.h"
9
10 #include "util/bit_array.c"
11 #include "common/lib/test_env.c"
12
13 static void
test_1bit(void)14 test_1bit(void)
15 {
16 struct spdk_bit_array *ba;
17
18 ba = spdk_bit_array_create(1);
19 SPDK_CU_ASSERT_FATAL(ba != NULL);
20 CU_ASSERT(spdk_bit_array_capacity(ba) == 1);
21
22 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
23 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX);
24
25 /* Set bit 0 */
26 CU_ASSERT(spdk_bit_array_set(ba, 0) == 0);
27 CU_ASSERT(spdk_bit_array_get(ba, 0) == true);
28 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 0);
29
30 /* Clear bit 0 */
31 spdk_bit_array_clear(ba, 0);
32 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
33 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX);
34
35 spdk_bit_array_free(&ba);
36 CU_ASSERT(ba == NULL);
37 }
38
39 static void
test_64bit(void)40 test_64bit(void)
41 {
42 struct spdk_bit_array *ba;
43
44 ba = spdk_bit_array_create(64);
45 SPDK_CU_ASSERT_FATAL(ba != NULL);
46 CU_ASSERT(spdk_bit_array_capacity(ba) == 64);
47 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
48 CU_ASSERT(spdk_bit_array_get(ba, 63) == false);
49 CU_ASSERT(spdk_bit_array_get(ba, 64) == false);
50 CU_ASSERT(spdk_bit_array_get(ba, 1000) == false);
51 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX);
52
53 /* Set bit 1 */
54 CU_ASSERT(spdk_bit_array_set(ba, 1) == 0);
55 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
56 CU_ASSERT(spdk_bit_array_get(ba, 1) == true);
57 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 1);
58
59 /* Set bit 63 (1 still set) */
60 CU_ASSERT(spdk_bit_array_set(ba, 63) == 0);
61 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
62 CU_ASSERT(spdk_bit_array_get(ba, 1) == true);
63 CU_ASSERT(spdk_bit_array_get(ba, 63) == true);
64 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 1);
65
66 /* Clear bit 1 (63 still set) */
67 spdk_bit_array_clear(ba, 1);
68 CU_ASSERT(spdk_bit_array_get(ba, 1) == false);
69 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 63);
70
71 /* Clear bit 63 (no bits set) */
72 spdk_bit_array_clear(ba, 63);
73 CU_ASSERT(spdk_bit_array_get(ba, 63) == false);
74 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX);
75
76 spdk_bit_array_free(&ba);
77 }
78
79 static void
test_find(void)80 test_find(void)
81 {
82 struct spdk_bit_array *ba;
83 uint32_t i;
84
85 ba = spdk_bit_array_create(256);
86 SPDK_CU_ASSERT_FATAL(ba != NULL);
87 CU_ASSERT(spdk_bit_array_capacity(ba) == 256);
88
89 /* Set all bits */
90 for (i = 0; i < 256; i++) {
91 CU_ASSERT(spdk_bit_array_set(ba, i) == 0);
92 }
93
94 /* Verify that find_first_set and find_first_clear work for each starting position */
95 for (i = 0; i < 256; i++) {
96 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i);
97 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == UINT32_MAX);
98 }
99 CU_ASSERT(spdk_bit_array_find_first_set(ba, 256) == UINT32_MAX);
100 CU_ASSERT(spdk_bit_array_find_first_clear(ba, 256) == UINT32_MAX);
101
102 /* Clear bits 0 through 31 */
103 for (i = 0; i < 32; i++) {
104 spdk_bit_array_clear(ba, i);
105 }
106
107 for (i = 0; i < 32; i++) {
108 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == 32);
109 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == i);
110 }
111
112 for (i = 32; i < 256; i++) {
113 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i);
114 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == UINT32_MAX);
115 }
116
117 /* Clear bit 255 */
118 spdk_bit_array_clear(ba, 255);
119
120 for (i = 0; i < 32; i++) {
121 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == 32);
122 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == i);
123 }
124
125 for (i = 32; i < 255; i++) {
126 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i);
127 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == 255);
128 }
129
130 CU_ASSERT(spdk_bit_array_find_first_clear(ba, 256) == UINT32_MAX);
131
132 spdk_bit_array_free(&ba);
133 }
134
135 static void
test_resize(void)136 test_resize(void)
137 {
138 struct spdk_bit_array *ba;
139
140 /* Start with a 0 bit array */
141 ba = spdk_bit_array_create(0);
142 SPDK_CU_ASSERT_FATAL(ba != NULL);
143 CU_ASSERT(spdk_bit_array_capacity(ba) == 0);
144 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
145 CU_ASSERT(spdk_bit_array_set(ba, 0) == -EINVAL);
146 spdk_bit_array_clear(ba, 0);
147
148 /* Increase size to 1 bit */
149 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 1) == 0);
150 SPDK_CU_ASSERT_FATAL(ba != NULL);
151 CU_ASSERT(spdk_bit_array_capacity(ba) == 1);
152 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
153 CU_ASSERT(spdk_bit_array_set(ba, 0) == 0);
154 CU_ASSERT(spdk_bit_array_get(ba, 0) == true);
155
156 /* Increase size to 2 bits */
157 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 2) == 0);
158 SPDK_CU_ASSERT_FATAL(ba != NULL);
159 CU_ASSERT(spdk_bit_array_capacity(ba) == 2);
160 CU_ASSERT(spdk_bit_array_get(ba, 1) == false);
161 CU_ASSERT(spdk_bit_array_set(ba, 1) == 0);
162 CU_ASSERT(spdk_bit_array_get(ba, 1) == true);
163
164 /* Shrink size back to 1 bit */
165 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 1) == 0);
166 SPDK_CU_ASSERT_FATAL(ba != NULL);
167 CU_ASSERT(spdk_bit_array_capacity(ba) == 1);
168 CU_ASSERT(spdk_bit_array_get(ba, 0) == true);
169 CU_ASSERT(spdk_bit_array_get(ba, 1) == false);
170
171 /* Increase size to 65 bits */
172 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 65) == 0);
173 SPDK_CU_ASSERT_FATAL(ba != NULL);
174 CU_ASSERT(spdk_bit_array_capacity(ba) == 65);
175 CU_ASSERT(spdk_bit_array_get(ba, 0) == true);
176 CU_ASSERT(spdk_bit_array_get(ba, 1) == false);
177 CU_ASSERT(spdk_bit_array_set(ba, 64) == 0);
178 CU_ASSERT(spdk_bit_array_get(ba, 64) == true);
179
180 /* Shrink size back to 0 bits */
181 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 0) == 0);
182 SPDK_CU_ASSERT_FATAL(ba != NULL);
183 CU_ASSERT(spdk_bit_array_capacity(ba) == 0);
184 CU_ASSERT(spdk_bit_array_get(ba, 0) == false);
185 CU_ASSERT(spdk_bit_array_get(ba, 1) == false);
186
187 spdk_bit_array_free(&ba);
188 }
189
190 static void
test_errors(void)191 test_errors(void)
192 {
193 /* Passing NULL to resize should fail. */
194 CU_ASSERT(spdk_bit_array_resize(NULL, 0) == -EINVAL);
195
196 /* Passing NULL to free is a no-op. */
197 spdk_bit_array_free(NULL);
198 }
199
200 static void
test_count(void)201 test_count(void)
202 {
203 struct spdk_bit_array *ba;
204 uint32_t i;
205
206 /* 0-bit array should have 0 bits set and 0 bits clear */
207 ba = spdk_bit_array_create(0);
208 SPDK_CU_ASSERT_FATAL(ba != NULL);
209 CU_ASSERT(spdk_bit_array_count_set(ba) == 0);
210 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0);
211 spdk_bit_array_free(&ba);
212
213 /* 1-bit array */
214 ba = spdk_bit_array_create(1);
215 SPDK_CU_ASSERT_FATAL(ba != NULL);
216 CU_ASSERT(spdk_bit_array_count_set(ba) == 0);
217 CU_ASSERT(spdk_bit_array_count_clear(ba) == 1);
218 spdk_bit_array_set(ba, 0);
219 CU_ASSERT(spdk_bit_array_count_set(ba) == 1);
220 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0);
221 spdk_bit_array_free(&ba);
222
223 /* 65-bit array */
224 ba = spdk_bit_array_create(65);
225 SPDK_CU_ASSERT_FATAL(ba != NULL);
226 CU_ASSERT(spdk_bit_array_count_set(ba) == 0);
227 CU_ASSERT(spdk_bit_array_count_clear(ba) == 65);
228 spdk_bit_array_set(ba, 0);
229 CU_ASSERT(spdk_bit_array_count_set(ba) == 1);
230 CU_ASSERT(spdk_bit_array_count_clear(ba) == 64);
231 spdk_bit_array_set(ba, 5);
232 CU_ASSERT(spdk_bit_array_count_set(ba) == 2);
233 CU_ASSERT(spdk_bit_array_count_clear(ba) == 63);
234 spdk_bit_array_set(ba, 13);
235 CU_ASSERT(spdk_bit_array_count_set(ba) == 3);
236 CU_ASSERT(spdk_bit_array_count_clear(ba) == 62);
237 spdk_bit_array_clear(ba, 0);
238 CU_ASSERT(spdk_bit_array_count_set(ba) == 2);
239 CU_ASSERT(spdk_bit_array_count_clear(ba) == 63);
240 for (i = 0; i < 65; i++) {
241 spdk_bit_array_set(ba, i);
242 }
243 CU_ASSERT(spdk_bit_array_count_set(ba) == 65);
244 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0);
245 for (i = 0; i < 65; i++) {
246 spdk_bit_array_clear(ba, i);
247 CU_ASSERT(spdk_bit_array_count_set(ba) == 65 - i - 1);
248 CU_ASSERT(spdk_bit_array_count_clear(ba) == i + 1);
249 }
250 spdk_bit_array_free(&ba);
251 }
252
253 #define TEST_MASK_SIZE 128
254 #define TEST_BITS_NUM (TEST_MASK_SIZE * 8 - 3)
255 static void
test_mask_store_load(void)256 test_mask_store_load(void)
257 {
258 struct spdk_bit_array *ba;
259 uint8_t mask[TEST_MASK_SIZE] = { 0 };
260 uint32_t i;
261
262 ba = spdk_bit_array_create(TEST_BITS_NUM);
263
264 /* Check if stored mask is consistent with bit array mask */
265 spdk_bit_array_set(ba, 0);
266 spdk_bit_array_set(ba, TEST_BITS_NUM / 2);
267 spdk_bit_array_set(ba, TEST_BITS_NUM - 1);
268
269 spdk_bit_array_store_mask(ba, mask);
270
271 for (i = 0; i < TEST_BITS_NUM; i++) {
272 if (i == 0 || i == TEST_BITS_NUM / 2 || i == TEST_BITS_NUM - 1) {
273 CU_ASSERT((mask[i / 8] & (1U << (i % 8))));
274 } else {
275 CU_ASSERT(!(mask[i / 8] & (1U << (i % 8))));
276 }
277 }
278
279 /* Check if loaded mask is consistent with bit array mask */
280 memset(mask, 0, TEST_MASK_SIZE);
281 mask[0] = 1;
282 mask[TEST_MASK_SIZE - 1] = 1U << 4;
283
284 spdk_bit_array_load_mask(ba, mask);
285
286 CU_ASSERT(spdk_bit_array_get(ba, 0));
287 CU_ASSERT(spdk_bit_array_get(ba, TEST_BITS_NUM - 1));
288
289 spdk_bit_array_clear(ba, 0);
290 spdk_bit_array_clear(ba, TEST_BITS_NUM - 1);
291
292 for (i = 0; i < TEST_BITS_NUM; i++) {
293 CU_ASSERT(!spdk_bit_array_get(ba, i));
294 }
295
296 spdk_bit_array_free(&ba);
297 }
298
299 static void
test_mask_clear(void)300 test_mask_clear(void)
301 {
302 struct spdk_bit_array *ba;
303 uint32_t i;
304
305 ba = spdk_bit_array_create(TEST_BITS_NUM);
306
307 for (i = 0; i < TEST_BITS_NUM; i++) {
308 spdk_bit_array_set(ba, i);
309 }
310
311 spdk_bit_array_clear_mask(ba);
312
313 for (i = 0; i < TEST_BITS_NUM; i++) {
314 CU_ASSERT(!spdk_bit_array_get(ba, i));
315 }
316
317 spdk_bit_array_free(&ba);
318 }
319
320 int
main(int argc,char ** argv)321 main(int argc, char **argv)
322 {
323 CU_pSuite suite = NULL;
324 unsigned int num_failures;
325
326 CU_initialize_registry();
327
328 suite = CU_add_suite("bit_array", NULL, NULL);
329
330 CU_ADD_TEST(suite, test_1bit);
331 CU_ADD_TEST(suite, test_64bit);
332 CU_ADD_TEST(suite, test_find);
333 CU_ADD_TEST(suite, test_resize);
334 CU_ADD_TEST(suite, test_errors);
335 CU_ADD_TEST(suite, test_count);
336 CU_ADD_TEST(suite, test_mask_store_load);
337 CU_ADD_TEST(suite, test_mask_clear);
338
339
340 num_failures = spdk_ut_run_tests(argc, argv, NULL);
341
342 CU_cleanup_registry();
343
344 return num_failures;
345 }
346