1 /*- 2 * BSD LICENSE 3 * 4 * Copyright (c) Intel Corporation. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * * Neither the name of Intel Corporation nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include "spdk/stdinc.h" 35 36 #include "spdk_cunit.h" 37 38 #include "util/bit_array.c" 39 40 void * 41 spdk_dma_realloc(void *buf, size_t size, size_t align, uint64_t *phys_addr) 42 { 43 return realloc(buf, size); 44 } 45 46 void 47 spdk_dma_free(void *buf) 48 { 49 free(buf); 50 } 51 52 static void 53 test_1bit(void) 54 { 55 struct spdk_bit_array *ba; 56 57 ba = spdk_bit_array_create(1); 58 SPDK_CU_ASSERT_FATAL(ba != NULL); 59 CU_ASSERT(spdk_bit_array_capacity(ba) == 1); 60 61 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 62 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX); 63 64 /* Set bit 0 */ 65 CU_ASSERT(spdk_bit_array_set(ba, 0) == 0); 66 CU_ASSERT(spdk_bit_array_get(ba, 0) == true); 67 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 0); 68 69 /* Clear bit 0 */ 70 spdk_bit_array_clear(ba, 0); 71 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 72 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX); 73 74 spdk_bit_array_free(&ba); 75 CU_ASSERT(ba == NULL); 76 } 77 78 static void 79 test_64bit(void) 80 { 81 struct spdk_bit_array *ba; 82 83 ba = spdk_bit_array_create(64); 84 SPDK_CU_ASSERT_FATAL(ba != NULL); 85 CU_ASSERT(spdk_bit_array_capacity(ba) == 64); 86 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 87 CU_ASSERT(spdk_bit_array_get(ba, 63) == false); 88 CU_ASSERT(spdk_bit_array_get(ba, 64) == false); 89 CU_ASSERT(spdk_bit_array_get(ba, 1000) == false); 90 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX); 91 92 /* Set bit 1 */ 93 CU_ASSERT(spdk_bit_array_set(ba, 1) == 0); 94 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 95 CU_ASSERT(spdk_bit_array_get(ba, 1) == true); 96 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 1); 97 98 /* Set bit 63 (1 still set) */ 99 CU_ASSERT(spdk_bit_array_set(ba, 63) == 0); 100 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 101 CU_ASSERT(spdk_bit_array_get(ba, 1) == true); 102 CU_ASSERT(spdk_bit_array_get(ba, 63) == true); 103 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 1); 104 105 /* Clear bit 1 (63 still set) */ 106 spdk_bit_array_clear(ba, 1); 107 CU_ASSERT(spdk_bit_array_get(ba, 1) == false); 108 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == 63); 109 110 /* Clear bit 63 (no bits set) */ 111 spdk_bit_array_clear(ba, 63); 112 CU_ASSERT(spdk_bit_array_get(ba, 63) == false); 113 CU_ASSERT(spdk_bit_array_find_first_set(ba, 0) == UINT32_MAX); 114 115 spdk_bit_array_free(&ba); 116 } 117 118 static void 119 test_find(void) 120 { 121 struct spdk_bit_array *ba; 122 uint32_t i; 123 124 ba = spdk_bit_array_create(256); 125 SPDK_CU_ASSERT_FATAL(ba != NULL); 126 CU_ASSERT(spdk_bit_array_capacity(ba) == 256); 127 128 /* Set all bits */ 129 for (i = 0; i < 256; i++) { 130 CU_ASSERT(spdk_bit_array_set(ba, i) == 0); 131 } 132 133 /* Verify that find_first_set and find_first_clear work for each starting position */ 134 for (i = 0; i < 256; i++) { 135 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i); 136 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == UINT32_MAX); 137 } 138 CU_ASSERT(spdk_bit_array_find_first_set(ba, 256) == UINT32_MAX); 139 CU_ASSERT(spdk_bit_array_find_first_clear(ba, 256) == UINT32_MAX); 140 141 /* Clear bits 0 through 31 */ 142 for (i = 0; i < 32; i++) { 143 spdk_bit_array_clear(ba, i); 144 } 145 146 for (i = 0; i < 32; i++) { 147 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == 32); 148 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == i); 149 } 150 151 for (i = 32; i < 256; i++) { 152 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i); 153 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == UINT32_MAX); 154 } 155 156 /* Clear bit 255 */ 157 spdk_bit_array_clear(ba, 255); 158 159 for (i = 0; i < 32; i++) { 160 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == 32); 161 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == i); 162 } 163 164 for (i = 32; i < 255; i++) { 165 CU_ASSERT(spdk_bit_array_find_first_set(ba, i) == i); 166 CU_ASSERT(spdk_bit_array_find_first_clear(ba, i) == 255); 167 } 168 169 CU_ASSERT(spdk_bit_array_find_first_clear(ba, 256) == UINT32_MAX); 170 171 spdk_bit_array_free(&ba); 172 } 173 174 static void 175 test_resize(void) 176 { 177 struct spdk_bit_array *ba; 178 179 /* Start with a 0 bit array */ 180 ba = spdk_bit_array_create(0); 181 SPDK_CU_ASSERT_FATAL(ba != NULL); 182 CU_ASSERT(spdk_bit_array_capacity(ba) == 0); 183 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 184 CU_ASSERT(spdk_bit_array_set(ba, 0) == -EINVAL); 185 spdk_bit_array_clear(ba, 0); 186 187 /* Increase size to 1 bit */ 188 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 1) == 0); 189 SPDK_CU_ASSERT_FATAL(ba != NULL); 190 CU_ASSERT(spdk_bit_array_capacity(ba) == 1); 191 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 192 CU_ASSERT(spdk_bit_array_set(ba, 0) == 0); 193 CU_ASSERT(spdk_bit_array_get(ba, 0) == true); 194 195 /* Increase size to 2 bits */ 196 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 2) == 0); 197 SPDK_CU_ASSERT_FATAL(ba != NULL); 198 CU_ASSERT(spdk_bit_array_capacity(ba) == 2); 199 CU_ASSERT(spdk_bit_array_get(ba, 1) == false); 200 CU_ASSERT(spdk_bit_array_set(ba, 1) == 0); 201 CU_ASSERT(spdk_bit_array_get(ba, 1) == true); 202 203 /* Shrink size back to 1 bit */ 204 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 1) == 0); 205 SPDK_CU_ASSERT_FATAL(ba != NULL); 206 CU_ASSERT(spdk_bit_array_capacity(ba) == 1); 207 CU_ASSERT(spdk_bit_array_get(ba, 0) == true); 208 CU_ASSERT(spdk_bit_array_get(ba, 1) == false); 209 210 /* Increase size to 65 bits */ 211 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 65) == 0); 212 SPDK_CU_ASSERT_FATAL(ba != NULL); 213 CU_ASSERT(spdk_bit_array_capacity(ba) == 65); 214 CU_ASSERT(spdk_bit_array_get(ba, 0) == true); 215 CU_ASSERT(spdk_bit_array_get(ba, 1) == false); 216 CU_ASSERT(spdk_bit_array_set(ba, 64) == 0); 217 CU_ASSERT(spdk_bit_array_get(ba, 64) == true); 218 219 /* Shrink size back to 0 bits */ 220 SPDK_CU_ASSERT_FATAL(spdk_bit_array_resize(&ba, 0) == 0); 221 SPDK_CU_ASSERT_FATAL(ba != NULL); 222 CU_ASSERT(spdk_bit_array_capacity(ba) == 0); 223 CU_ASSERT(spdk_bit_array_get(ba, 0) == false); 224 CU_ASSERT(spdk_bit_array_get(ba, 1) == false); 225 226 spdk_bit_array_free(&ba); 227 } 228 229 static void 230 test_errors(void) 231 { 232 /* Passing NULL to resize should fail. */ 233 CU_ASSERT(spdk_bit_array_resize(NULL, 0) == -EINVAL); 234 235 /* Passing NULL to free is a no-op. */ 236 spdk_bit_array_free(NULL); 237 } 238 239 static void 240 test_count(void) 241 { 242 struct spdk_bit_array *ba; 243 uint32_t i; 244 245 /* 0-bit array should have 0 bits set and 0 bits clear */ 246 ba = spdk_bit_array_create(0); 247 SPDK_CU_ASSERT_FATAL(ba != NULL); 248 CU_ASSERT(spdk_bit_array_count_set(ba) == 0); 249 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0); 250 spdk_bit_array_free(&ba); 251 252 /* 1-bit array */ 253 ba = spdk_bit_array_create(1); 254 SPDK_CU_ASSERT_FATAL(ba != NULL); 255 CU_ASSERT(spdk_bit_array_count_set(ba) == 0); 256 CU_ASSERT(spdk_bit_array_count_clear(ba) == 1); 257 spdk_bit_array_set(ba, 0); 258 CU_ASSERT(spdk_bit_array_count_set(ba) == 1); 259 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0); 260 spdk_bit_array_free(&ba); 261 262 /* 65-bit array */ 263 ba = spdk_bit_array_create(65); 264 SPDK_CU_ASSERT_FATAL(ba != NULL); 265 CU_ASSERT(spdk_bit_array_count_set(ba) == 0); 266 CU_ASSERT(spdk_bit_array_count_clear(ba) == 65); 267 spdk_bit_array_set(ba, 0); 268 CU_ASSERT(spdk_bit_array_count_set(ba) == 1); 269 CU_ASSERT(spdk_bit_array_count_clear(ba) == 64); 270 spdk_bit_array_set(ba, 5); 271 CU_ASSERT(spdk_bit_array_count_set(ba) == 2); 272 CU_ASSERT(spdk_bit_array_count_clear(ba) == 63); 273 spdk_bit_array_set(ba, 13); 274 CU_ASSERT(spdk_bit_array_count_set(ba) == 3); 275 CU_ASSERT(spdk_bit_array_count_clear(ba) == 62); 276 spdk_bit_array_clear(ba, 0); 277 CU_ASSERT(spdk_bit_array_count_set(ba) == 2); 278 CU_ASSERT(spdk_bit_array_count_clear(ba) == 63); 279 for (i = 0; i < 65; i++) { 280 spdk_bit_array_set(ba, i); 281 } 282 CU_ASSERT(spdk_bit_array_count_set(ba) == 65); 283 CU_ASSERT(spdk_bit_array_count_clear(ba) == 0); 284 for (i = 0; i < 65; i++) { 285 spdk_bit_array_clear(ba, i); 286 CU_ASSERT(spdk_bit_array_count_set(ba) == 65 - i - 1); 287 CU_ASSERT(spdk_bit_array_count_clear(ba) == i + 1); 288 } 289 spdk_bit_array_free(&ba); 290 } 291 292 #define TEST_MASK_SIZE 128 293 #define TEST_BITS_NUM (TEST_MASK_SIZE * 8 - 3) 294 static void 295 test_mask_store_load(void) 296 { 297 struct spdk_bit_array *ba; 298 uint8_t mask[TEST_MASK_SIZE] = { 0 }; 299 uint32_t i; 300 301 ba = spdk_bit_array_create(TEST_BITS_NUM); 302 303 /* Check if stored mask is consistent with bit array mask */ 304 spdk_bit_array_set(ba, 0); 305 spdk_bit_array_set(ba, TEST_BITS_NUM / 2); 306 spdk_bit_array_set(ba, TEST_BITS_NUM - 1); 307 308 spdk_bit_array_store_mask(ba, mask); 309 310 for (i = 0; i < TEST_BITS_NUM; i++) { 311 if (i == 0 || i == TEST_BITS_NUM / 2 || i == TEST_BITS_NUM - 1) { 312 CU_ASSERT((mask[i / 8] & (1U << (i % 8)))); 313 } else { 314 CU_ASSERT(!(mask[i / 8] & (1U << (i % 8)))); 315 } 316 } 317 318 /* Check if loaded mask is consistent with bit array mask */ 319 memset(mask, 0, TEST_MASK_SIZE); 320 mask[0] = 1; 321 mask[TEST_MASK_SIZE - 1] = 1U << 4; 322 323 spdk_bit_array_load_mask(ba, mask); 324 325 CU_ASSERT(spdk_bit_array_get(ba, 0)); 326 CU_ASSERT(spdk_bit_array_get(ba, TEST_BITS_NUM - 1)); 327 328 spdk_bit_array_clear(ba, 0); 329 spdk_bit_array_clear(ba, TEST_BITS_NUM - 1); 330 331 for (i = 0; i < TEST_BITS_NUM; i++) { 332 CU_ASSERT(!spdk_bit_array_get(ba, i)); 333 } 334 335 spdk_bit_array_free(&ba); 336 } 337 338 static void 339 test_mask_clear(void) 340 { 341 struct spdk_bit_array *ba; 342 uint32_t i; 343 344 ba = spdk_bit_array_create(TEST_BITS_NUM); 345 346 for (i = 0; i < TEST_BITS_NUM; i++) { 347 spdk_bit_array_set(ba, i); 348 } 349 350 spdk_bit_array_clear_mask(ba); 351 352 for (i = 0; i < TEST_BITS_NUM; i++) { 353 CU_ASSERT(!spdk_bit_array_get(ba, i)); 354 } 355 356 spdk_bit_array_free(&ba); 357 } 358 359 int 360 main(int argc, char **argv) 361 { 362 CU_pSuite suite = NULL; 363 unsigned int num_failures; 364 365 if (CU_initialize_registry() != CUE_SUCCESS) { 366 return CU_get_error(); 367 } 368 369 suite = CU_add_suite("bit_array", NULL, NULL); 370 if (suite == NULL) { 371 CU_cleanup_registry(); 372 return CU_get_error(); 373 } 374 375 if ( 376 CU_add_test(suite, "test_1bit", test_1bit) == NULL || 377 CU_add_test(suite, "test_64bit", test_64bit) == NULL || 378 CU_add_test(suite, "test_find", test_find) == NULL || 379 CU_add_test(suite, "test_resize", test_resize) == NULL || 380 CU_add_test(suite, "test_errors", test_errors) == NULL || 381 CU_add_test(suite, "test_count", test_count) == NULL || 382 CU_add_test(suite, "test_mask_store_load", test_mask_store_load) == NULL || 383 CU_add_test(suite, "test_mask_clear", test_mask_clear) == NULL) { 384 CU_cleanup_registry(); 385 return CU_get_error(); 386 } 387 388 CU_basic_set_mode(CU_BRM_VERBOSE); 389 390 CU_basic_run_tests(); 391 392 num_failures = CU_get_number_of_failures(); 393 CU_cleanup_registry(); 394 395 return num_failures; 396 } 397