1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright (C) 2022 Intel Corporation. 3 * All rights reserved. 4 */ 5 6 #include "spdk/stdinc.h" 7 8 #include "spdk_cunit.h" 9 10 #include "ftl/utils/ftl_bitmap.c" 11 12 #define BITMAP_SIZE 64 13 #define BITMAP_CAPACITY (BITMAP_SIZE * 8) 14 15 #define TEST_BIT(bi, bbi) \ 16 { .byte_idx = (bi), .byte_bit_idx = (bbi), .bit_idx = (((bi) * 8) + (bbi)) } 17 18 static struct { 19 size_t byte_idx; 20 uint8_t byte_bit_idx; 21 uint64_t bit_idx; 22 } g_test_bits[] = { 23 TEST_BIT(0, 0), 24 TEST_BIT(0, 1), 25 TEST_BIT(0, 2), 26 TEST_BIT(1, 3), 27 TEST_BIT(2, 4), 28 TEST_BIT(3, 5), 29 TEST_BIT(15, 7), 30 TEST_BIT(42, 6), 31 TEST_BIT(BITMAP_SIZE - 1, 0), 32 TEST_BIT(BITMAP_SIZE - 1, 7), 33 }; 34 static const size_t g_test_bits_count = sizeof(g_test_bits) / sizeof(*g_test_bits); 35 36 static unsigned long g_buf[BITMAP_SIZE / sizeof(unsigned long)]; 37 static struct ftl_bitmap *g_bitmap; 38 39 static uint64_t 40 count_set_bits(const struct ftl_bitmap *bitmap) 41 { 42 uint64_t n = 0; 43 uint64_t i; 44 45 for (i = 0; i < BITMAP_CAPACITY; i++) { 46 if (ftl_bitmap_get(bitmap, i)) { 47 n++; 48 } 49 } 50 51 return n; 52 } 53 54 static void 55 test_ftl_bitmap_create(void) 56 { 57 struct ftl_bitmap *ret; 58 59 /* unaligned buffer */ 60 ret = ftl_bitmap_create(((uint8_t *)g_buf) + 1, BITMAP_SIZE); 61 CU_ASSERT_EQUAL(ret, NULL); 62 63 /* wrong size */ 64 ret = ftl_bitmap_create(g_buf, BITMAP_SIZE - 1); 65 CU_ASSERT_EQUAL(ret, NULL); 66 } 67 68 static void 69 test_ftl_bitmap_get(void) 70 { 71 uint8_t *buf = (uint8_t *)g_buf; 72 size_t i; 73 74 memset(g_buf, 0, BITMAP_SIZE); 75 76 for (i = 0; i < g_test_bits_count; i++) { 77 buf[g_test_bits[i].byte_idx] += (1 << g_test_bits[i].byte_bit_idx); 78 } 79 80 CU_ASSERT_EQUAL(count_set_bits(g_bitmap), g_test_bits_count); 81 82 for (i = 0; i < g_test_bits_count; i++) { 83 CU_ASSERT_TRUE(ftl_bitmap_get(g_bitmap, g_test_bits[i].bit_idx)); 84 } 85 } 86 87 static void 88 test_ftl_bitmap_set(void) 89 { 90 size_t i; 91 92 memset(g_buf, 0, BITMAP_SIZE); 93 94 for (i = 0; i < g_test_bits_count; i++) { 95 ftl_bitmap_set(g_bitmap, g_test_bits[i].bit_idx); 96 } 97 98 CU_ASSERT_EQUAL(count_set_bits(g_bitmap), g_test_bits_count); 99 100 for (i = 0; i < g_test_bits_count; i++) { 101 CU_ASSERT_TRUE(ftl_bitmap_get(g_bitmap, g_test_bits[i].bit_idx)); 102 } 103 } 104 105 static void 106 test_ftl_bitmap_clear(void) 107 { 108 size_t i; 109 110 memset(g_buf, 0xff, BITMAP_SIZE); 111 112 for (i = 0; i < g_test_bits_count; i++) { 113 ftl_bitmap_clear(g_bitmap, g_test_bits[i].bit_idx); 114 } 115 116 CU_ASSERT_EQUAL(count_set_bits(g_bitmap), BITMAP_CAPACITY - g_test_bits_count); 117 118 for (i = 0; i < g_test_bits_count; i++) { 119 CU_ASSERT_FALSE(ftl_bitmap_get(g_bitmap, g_test_bits[i].bit_idx)); 120 } 121 } 122 123 static void 124 test_ftl_bitmap_find_first_set(void) 125 { 126 size_t i; 127 uint64_t bit; 128 129 memset(g_buf, 0, BITMAP_SIZE); 130 131 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, 0, UINT64_MAX), UINT64_MAX); 132 133 for (i = 1; i <= g_test_bits_count; i++) { 134 bit = g_test_bits[g_test_bits_count - i].bit_idx; 135 136 ftl_bitmap_set(g_bitmap, bit); 137 138 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, 0, UINT64_MAX), bit); 139 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, 0, bit), bit); 140 if (bit > 0) { 141 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, 0, bit - 1), UINT64_MAX); 142 } 143 } 144 145 for (i = 0; i < g_test_bits_count; i++) { 146 bit = g_test_bits[i].bit_idx; 147 148 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, bit, UINT64_MAX), bit); 149 CU_ASSERT_EQUAL(ftl_bitmap_find_first_set(g_bitmap, bit, bit), bit); 150 } 151 } 152 153 static void 154 test_ftl_bitmap_find_first_clear(void) 155 { 156 size_t i; 157 uint64_t bit; 158 159 memset(g_buf, 0xff, BITMAP_SIZE); 160 161 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, 0, UINT64_MAX), UINT64_MAX); 162 163 for (i = 1; i <= g_test_bits_count; i++) { 164 bit = g_test_bits[g_test_bits_count - i].bit_idx; 165 166 ftl_bitmap_clear(g_bitmap, bit); 167 168 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, 0, UINT64_MAX), bit); 169 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, 0, bit), bit); 170 if (bit > 0) { 171 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, 0, bit - 1), UINT64_MAX); 172 } 173 } 174 175 for (i = 0; i < g_test_bits_count; i++) { 176 bit = g_test_bits[i].bit_idx; 177 178 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, bit, UINT64_MAX), bit); 179 CU_ASSERT_EQUAL(ftl_bitmap_find_first_clear(g_bitmap, bit, bit), bit); 180 } 181 } 182 183 static void 184 test_ftl_bitmap_count_set(void) 185 { 186 size_t i; 187 188 memset(g_buf, 0, BITMAP_SIZE); 189 190 for (i = 0; i < g_test_bits_count; i++) { 191 ftl_bitmap_set(g_bitmap, g_test_bits[i].bit_idx); 192 } 193 194 CU_ASSERT_EQUAL(g_test_bits_count, ftl_bitmap_count_set(g_bitmap)); 195 CU_ASSERT_EQUAL(count_set_bits(g_bitmap), ftl_bitmap_count_set(g_bitmap)); 196 } 197 198 static int 199 test_setup(void) 200 { 201 g_bitmap = ftl_bitmap_create(g_buf, BITMAP_SIZE); 202 if (!g_bitmap) { 203 return -ENOMEM; 204 } 205 206 return 0; 207 } 208 209 static int 210 test_cleanup(void) 211 { 212 free(g_bitmap); 213 g_bitmap = NULL; 214 return 0; 215 } 216 217 int 218 main(int argc, char **argv) 219 { 220 CU_pSuite suite = NULL; 221 unsigned int num_failures; 222 223 CU_set_error_action(CUEA_ABORT); 224 CU_initialize_registry(); 225 226 suite = CU_add_suite("ftl_bitmap", test_setup, test_cleanup); 227 CU_ADD_TEST(suite, test_ftl_bitmap_create); 228 CU_ADD_TEST(suite, test_ftl_bitmap_get); 229 CU_ADD_TEST(suite, test_ftl_bitmap_set); 230 CU_ADD_TEST(suite, test_ftl_bitmap_clear); 231 CU_ADD_TEST(suite, test_ftl_bitmap_find_first_set); 232 CU_ADD_TEST(suite, test_ftl_bitmap_find_first_clear); 233 CU_ADD_TEST(suite, test_ftl_bitmap_count_set); 234 235 CU_basic_set_mode(CU_BRM_VERBOSE); 236 CU_basic_run_tests(); 237 num_failures = CU_get_number_of_failures(); 238 CU_cleanup_registry(); 239 240 return num_failures; 241 } 242