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_internal/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
count_set_bits(const struct ftl_bitmap * bitmap)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
test_ftl_bitmap_create(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
test_ftl_bitmap_get(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
test_ftl_bitmap_set(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
test_ftl_bitmap_clear(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
test_ftl_bitmap_find_first_set(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
test_ftl_bitmap_find_first_clear(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
test_ftl_bitmap_count_set(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
test_setup(void)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
test_cleanup(void)210 test_cleanup(void)
211 {
212 free(g_bitmap);
213 g_bitmap = NULL;
214 return 0;
215 }
216
217 int
main(int argc,char ** argv)218 main(int argc, char **argv)
219 {
220 CU_pSuite suite = NULL;
221 unsigned int num_failures;
222
223 CU_initialize_registry();
224
225 suite = CU_add_suite("ftl_bitmap", test_setup, test_cleanup);
226 CU_ADD_TEST(suite, test_ftl_bitmap_create);
227 CU_ADD_TEST(suite, test_ftl_bitmap_get);
228 CU_ADD_TEST(suite, test_ftl_bitmap_set);
229 CU_ADD_TEST(suite, test_ftl_bitmap_clear);
230 CU_ADD_TEST(suite, test_ftl_bitmap_find_first_set);
231 CU_ADD_TEST(suite, test_ftl_bitmap_find_first_clear);
232 CU_ADD_TEST(suite, test_ftl_bitmap_count_set);
233
234 num_failures = spdk_ut_run_tests(argc, argv, NULL);
235 CU_cleanup_registry();
236
237 return num_failures;
238 }
239