1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(bitmap, .intensity_desc = {
4 .curve = SCALE_PIECEWISE_LOG,
5 .unit = "bits",
6 });
7
8/* Bitmaps are arrays of 64 bit words, so every op that takes a bit count
9 * has a partial trailing word to deal with, which can cause counting/reporting
10 * bits that live past nbits inside the last word, and mishandling of cases
11 * where nbits lands on a word boundary
12 *
13 * We try to test exact boundaries and off-by-ones, 64, 1, 63, 65, 128, etc */
14
15#define BM_WORDS 4
16#define BM_BITS (BM_WORDS * BITMAP_BITS_PER_WORD)
17
18static void bm_reset(bitmap_word_t *map) {
19 for (size_t i = 0; i < BM_WORDS; i++)
20 map[i] = 0;
21}
22
23static void bm_fill(bitmap_word_t *map) {
24 for (size_t i = 0; i < BM_WORDS; i++)
25 map[i] = ~(bitmap_word_t) 0;
26}
27
28static void bm_reset_n(bitmap_word_t *map, size_t nwords) {
29 for (size_t i = 0; i < nwords; i++)
30 map[i] = 0;
31}
32
33static void bm_fill_n(bitmap_word_t *map, size_t nwords) {
34 for (size_t i = 0; i < nwords; i++)
35 map[i] = ~(bitmap_word_t) 0;
36}
37
38TEST_DECLARE_UNIT(bitmap, set_test_clear, TEST_INTENSITY(64, 256, 4096)) {
39 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
40 size_t nwords = BITMAP_WORDS(nbits);
41 bitmap_word_t *map =
42 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_ZERO);
43 TEST_ASSERT_NONNULL(map);
44
45 for (size_t bit = 0; bit < nbits; bit++) {
46 TEST_ASSERT(!bitmap_test(map, bit));
47 bitmap_set(map, bit);
48 TEST_ASSERT(bitmap_test(map, bit));
49
50 /* Setting one bit must not
51 * disturb neighbors across the word boundary */
52 if (bit > 0)
53 TEST_ASSERT(!bitmap_test(map, bit - 1));
54
55 bitmap_clear(map, bit);
56 TEST_ASSERT(!bitmap_test(map, bit));
57 }
58
59 kfree(map);
60 return TEST_SUCCESS;
61}
62
63TEST_DECLARE_UNIT(bitmap, bit_isolation, TEST_INTENSITY(64, 256, 1024)) {
64 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
65 size_t nwords = BITMAP_WORDS(nbits);
66 bitmap_word_t *map =
67 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_NONE);
68 TEST_ASSERT_NONNULL(map);
69
70 for (size_t bit = 0; bit < nbits; bit++) {
71 bm_reset_n(map, nwords);
72 bitmap_set(map, bit);
73
74 for (size_t other = 0; other < nbits; other++)
75 TEST_ASSERT_EQ(bitmap_test(map, other), (other == bit));
76
77 TEST_ASSERT_EQ(bitmap_weight(map, nbits), 1);
78 }
79
80 kfree(map);
81 return TEST_SUCCESS;
82}
83
84TEST_DECLARE_UNIT(bitmap, toggle_and_test_ops) {
85 bitmap_word_t map[BM_WORDS];
86 bm_reset(map);
87
88 bitmap_toggle(map, bit: 70);
89 TEST_ASSERT(bitmap_test(map, 70));
90 bitmap_toggle(map, bit: 70);
91 TEST_ASSERT(!bitmap_test(map, 70));
92
93 /* The test_and_* must report the state from before change */
94 TEST_ASSERT_EQ(bitmap_test_and_set(map, 5), false);
95 TEST_ASSERT_EQ(bitmap_test_and_set(map, 5), true);
96 TEST_ASSERT_EQ(bitmap_test_and_clear(map, 5), true);
97 TEST_ASSERT_EQ(bitmap_test_and_clear(map, 5), false);
98
99 return TEST_SUCCESS;
100}
101
102/* Bits above nbits are memory and could be set, but shan't be counted */
103TEST_DECLARE_UNIT(bitmap, weight_ignores_past_end) {
104 bitmap_word_t map[BM_WORDS];
105 bm_fill(map);
106
107 static const size_t sizes[] = {1, 7, 63, 64, 65, 100, 127, 128, BM_BITS};
108
109 for (size_t i = 0; i < TEST_ARRAY_LEN(sizes); i++)
110 TEST_ASSERT_EQ(bitmap_weight(map, sizes[i]), sizes[i]);
111
112 bm_reset(map);
113 TEST_ASSERT_EQ(bitmap_weight(map, BM_BITS), 0);
114
115 return TEST_SUCCESS;
116}
117
118TEST_DECLARE_UNIT(bitmap, weight_counts, TEST_INTENSITY(64, 256, 4096)) {
119 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
120 size_t nwords = BITMAP_WORDS(nbits);
121 bitmap_word_t *map =
122 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_ZERO);
123 TEST_ASSERT_NONNULL(map);
124
125 for (size_t n = 0; n < nbits; n++) {
126 TEST_ASSERT_EQ(bitmap_weight(map, nbits), n);
127 bitmap_set(map, bit: n);
128 }
129 TEST_ASSERT_EQ(bitmap_weight(map, nbits), nbits);
130
131 kfree(map);
132 return TEST_SUCCESS;
133}
134
135TEST_DECLARE_UNIT(bitmap, ranges) {
136 bitmap_word_t map[BM_WORDS];
137 bm_reset(map);
138
139 /* range over word boundary */
140 bitmap_set_range(map, start: 60, len: 10);
141 for (size_t bit = 0; bit < BM_BITS; bit++)
142 TEST_ASSERT_EQ(bitmap_test(map, bit), (bit >= 60 && bit < 70));
143
144 bitmap_clear_range(map, start: 62, len: 4);
145 for (size_t bit = 60; bit < 70; bit++)
146 TEST_ASSERT_EQ(bitmap_test(map, bit), (bit < 62 || bit >= 66));
147
148 /* zero length range == no-op */
149 bm_reset(map);
150 bitmap_set_range(map, start: 10, len: 0);
151 TEST_ASSERT_EQ(bitmap_weight(map, BM_BITS), 0);
152
153 return TEST_SUCCESS;
154}
155
156TEST_DECLARE_UNIT(bitmap, find_first_set, TEST_INTENSITY(64, 256, 2048)) {
157 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
158 size_t nwords = BITMAP_WORDS(nbits);
159 bitmap_word_t *map =
160 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_NONE);
161 TEST_ASSERT_NONNULL(map);
162
163 bm_reset_n(map, nwords);
164 TEST_ASSERT_EQ(bitmap_find_first_set(map, nbits), nbits);
165
166 for (size_t bit = 0; bit < nbits; bit++) {
167 bm_reset_n(map, nwords);
168 bitmap_set(map, bit);
169 TEST_ASSERT_EQ(bitmap_find_first_set(map, nbits), bit);
170 }
171
172 /* Bit set beyond nbits mustn't report as found */
173 if (nbits >= 128) {
174 bm_reset_n(map, nwords);
175 bitmap_set(map, bit: 100);
176 TEST_ASSERT_EQ(bitmap_find_first_set(map, 100), 100);
177 TEST_ASSERT_EQ(bitmap_find_first_set(map, 101), 100);
178 }
179
180 kfree(map);
181 return TEST_SUCCESS;
182}
183
184TEST_DECLARE_UNIT(bitmap, find_first_zero, TEST_INTENSITY(64, 256, 2048)) {
185 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
186 size_t nwords = BITMAP_WORDS(nbits);
187 bitmap_word_t *map =
188 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_NONE);
189 TEST_ASSERT_NONNULL(map);
190
191 bm_reset_n(map, nwords);
192 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), 0);
193
194 bm_fill_n(map, nwords);
195 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), nbits);
196
197 for (size_t bit = 0; bit < nbits; bit++) {
198 bm_fill_n(map, nwords);
199 bitmap_clear(map, bit);
200 TEST_ASSERT_EQ(bitmap_find_first_zero(map, nbits), bit);
201 }
202
203 /* Full at word boundary must report nothing free */
204 if (nbits >= 128) {
205 bm_fill_n(map, nwords);
206 TEST_ASSERT_EQ(bitmap_find_first_zero(map, 64), 64);
207 TEST_ASSERT_EQ(bitmap_find_first_zero(map, 128), 128);
208 }
209
210 kfree(map);
211 return TEST_SUCCESS;
212}
213
214TEST_DECLARE_UNIT(bitmap, find_next_bit) {
215 bitmap_word_t map[BM_WORDS];
216 bm_reset(map);
217
218 bitmap_set(map, bit: 3);
219 bitmap_set(map, bit: 64);
220 bitmap_set(map, bit: 65);
221 bitmap_set(map, bit: 200);
222
223 /* Starting on a set bit finds that bit */
224 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 0), 3);
225 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 3), 3);
226 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 4), 64);
227 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 64), 64);
228 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 65), 65);
229 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 66), 200);
230 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, 201), BM_BITS);
231
232 /* A start at or past the end isn't a search */
233 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, BM_BITS), BM_BITS);
234 TEST_ASSERT_EQ(bitmap_find_next_bit(map, BM_BITS, BM_BITS + 10), BM_BITS);
235
236 /* Bits past nbits stay invisible */
237 TEST_ASSERT_EQ(bitmap_find_next_bit(map, 100, 66), 100);
238
239 return TEST_SUCCESS;
240}
241
242/* Walking every set bit via find_next_bit must visit the bits that
243 * bitmap_test agrees are set, and terminate */
244TEST_DECLARE_UNIT(bitmap, find_next_bit_walk, TEST_INTENSITY(64, 256, 4096)) {
245 size_t nbits = ctx->intensity_val ? ctx->intensity_val : BM_BITS;
246 size_t nwords = BITMAP_WORDS(nbits);
247 bitmap_word_t *map =
248 kmalloc(sizeof(bitmap_word_t) * nwords, ALLOC_FLAGS_ZERO);
249 TEST_ASSERT_NONNULL(map);
250
251 for (size_t bit = 0; bit < nbits; bit += 7)
252 bitmap_set(map, bit);
253
254 size_t seen = 0;
255 for (size_t bit = bitmap_find_next_bit(map, nbits, start: 0); bit < nbits;
256 bit = bitmap_find_next_bit(map, nbits, start: bit + 1)) {
257 TEST_ASSERT(bitmap_test(map, bit));
258 TEST_ASSERT_EQ(bit % 7, 0);
259 seen++;
260 }
261
262 TEST_ASSERT_EQ(seen, bitmap_weight(map, nbits));
263
264 kfree(map);
265 return TEST_SUCCESS;
266}
267
268TEST_DECLARE_UNIT(bitmap, word_index_math) {
269 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(0), 0);
270 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(63), 0);
271 TEST_ASSERT_EQ(BITMAP_WORD_INDEX(64), 1);
272 TEST_ASSERT_EQ(BITMAP_BIT_OFFSET(64), 0);
273 TEST_ASSERT_EQ(BITMAP_BIT_OFFSET(65), 1);
274
275 /* BITMAP_WORDS rounds up */
276 TEST_ASSERT_EQ(BITMAP_WORDS(1), 1);
277 TEST_ASSERT_EQ(BITMAP_WORDS(64), 1);
278 TEST_ASSERT_EQ(BITMAP_WORDS(65), 2);
279 TEST_ASSERT_EQ(BITMAP_WORDS(128), 2);
280
281 return TEST_SUCCESS;
282}
283