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 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 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 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 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 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 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 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 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 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