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