ceph/src/spdk/test/unit/lib/util/bit_array.c/bit_array_ut.c

   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         if (CU_initialize_registry() != CUE_SUCCESS) {
 355                 return CU_get_error();
 356         }
 357
 358         suite = CU_add_suite("bit_array", NULL, NULL);
 359         if (suite == NULL) {
 360                 CU_cleanup_registry();
 361                 return CU_get_error();
 362         }
 363
 364         if (
 365                 CU_add_test(suite, "test_1bit", test_1bit) == NULL ||
 366                 CU_add_test(suite, "test_64bit", test_64bit) == NULL ||
 367                 CU_add_test(suite, "test_find", test_find) == NULL ||
 368                 CU_add_test(suite, "test_resize", test_resize) == NULL ||
 369                 CU_add_test(suite, "test_errors", test_errors) == NULL ||
 370                 CU_add_test(suite, "test_count", test_count) == NULL ||
 371                 CU_add_test(suite, "test_mask_store_load", test_mask_store_load) == NULL ||
 372                 CU_add_test(suite, "test_mask_clear", test_mask_clear) == NULL) {
 373                 CU_cleanup_registry();
 374                 return CU_get_error();
 375         }
 376
 377         CU_basic_set_mode(CU_BRM_VERBOSE);
 378
 379         CU_basic_run_tests();
 380
 381         num_failures = CU_get_number_of_failures();
 382         CU_cleanup_registry();
 383
 384         return num_failures;
 385 }