1 #include "test/jemalloc_test.h"
2
3 #define NBITS_TAB \
4 NB( 1) \
5 NB( 2) \
6 NB( 3) \
7 NB( 4) \
8 NB( 5) \
9 NB( 6) \
10 NB( 7) \
11 NB( 8) \
12 NB( 9) \
13 NB(10) \
14 NB(11) \
15 NB(12) \
16 NB(13) \
17 NB(14) \
18 NB(15) \
19 NB(16) \
20 NB(17) \
21 NB(18) \
22 NB(19) \
23 NB(20) \
24 NB(21) \
25 NB(22) \
26 NB(23) \
27 NB(24) \
28 NB(25) \
29 NB(26) \
30 NB(27) \
31 NB(28) \
32 NB(29) \
33 NB(30) \
34 NB(31) \
35 NB(32) \
36 \
37 NB(33) \
38 NB(34) \
39 NB(35) \
40 NB(36) \
41 NB(37) \
42 NB(38) \
43 NB(39) \
44 NB(40) \
45 NB(41) \
46 NB(42) \
47 NB(43) \
48 NB(44) \
49 NB(45) \
50 NB(46) \
51 NB(47) \
52 NB(48) \
53 NB(49) \
54 NB(50) \
55 NB(51) \
56 NB(52) \
57 NB(53) \
58 NB(54) \
59 NB(55) \
60 NB(56) \
61 NB(57) \
62 NB(58) \
63 NB(59) \
64 NB(60) \
65 NB(61) \
66 NB(62) \
67 NB(63) \
68 NB(64) \
69 NB(65) \
70 \
71 NB(126) \
72 NB(127) \
73 NB(128) \
74 NB(129) \
75 NB(130) \
76 \
77 NB(254) \
78 NB(255) \
79 NB(256) \
80 NB(257) \
81 NB(258) \
82 \
83 NB(510) \
84 NB(511) \
85 NB(512) \
86 NB(513) \
87 NB(514) \
88 \
89 NB(1024) \
90 NB(2048) \
91 NB(4096) \
92 NB(8192) \
93 NB(16384) \
94
95 static void
test_bitmap_initializer_body(const bitmap_info_t * binfo,size_t nbits)96 test_bitmap_initializer_body(const bitmap_info_t *binfo, size_t nbits) {
97 bitmap_info_t binfo_dyn;
98 bitmap_info_init(&binfo_dyn, nbits);
99
100 assert_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn),
101 "Unexpected difference between static and dynamic initialization, "
102 "nbits=%zu", nbits);
103 assert_zu_eq(binfo->nbits, binfo_dyn.nbits,
104 "Unexpected difference between static and dynamic initialization, "
105 "nbits=%zu", nbits);
106 #ifdef BITMAP_USE_TREE
107 assert_u_eq(binfo->nlevels, binfo_dyn.nlevels,
108 "Unexpected difference between static and dynamic initialization, "
109 "nbits=%zu", nbits);
110 {
111 unsigned i;
112
113 for (i = 0; i < binfo->nlevels; i++) {
114 assert_zu_eq(binfo->levels[i].group_offset,
115 binfo_dyn.levels[i].group_offset,
116 "Unexpected difference between static and dynamic "
117 "initialization, nbits=%zu, level=%u", nbits, i);
118 }
119 }
120 #else
121 assert_zu_eq(binfo->ngroups, binfo_dyn.ngroups,
122 "Unexpected difference between static and dynamic initialization");
123 #endif
124 }
125
TEST_BEGIN(test_bitmap_initializer)126 TEST_BEGIN(test_bitmap_initializer) {
127 #define NB(nbits) { \
128 if (nbits <= BITMAP_MAXBITS) { \
129 bitmap_info_t binfo = \
130 BITMAP_INFO_INITIALIZER(nbits); \
131 test_bitmap_initializer_body(&binfo, nbits); \
132 } \
133 }
134 NBITS_TAB
135 #undef NB
136 }
137 TEST_END
138
139 static size_t
test_bitmap_size_body(const bitmap_info_t * binfo,size_t nbits,size_t prev_size)140 test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits,
141 size_t prev_size) {
142 size_t size = bitmap_size(binfo);
143 assert_zu_ge(size, (nbits >> 3),
144 "Bitmap size is smaller than expected");
145 assert_zu_ge(size, prev_size, "Bitmap size is smaller than expected");
146 return size;
147 }
148
TEST_BEGIN(test_bitmap_size)149 TEST_BEGIN(test_bitmap_size) {
150 size_t nbits, prev_size;
151
152 prev_size = 0;
153 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
154 bitmap_info_t binfo;
155 bitmap_info_init(&binfo, nbits);
156 prev_size = test_bitmap_size_body(&binfo, nbits, prev_size);
157 }
158 #define NB(nbits) { \
159 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
160 prev_size = test_bitmap_size_body(&binfo, nbits, \
161 prev_size); \
162 }
163 prev_size = 0;
164 NBITS_TAB
165 #undef NB
166 }
167 TEST_END
168
169 static void
test_bitmap_init_body(const bitmap_info_t * binfo,size_t nbits)170 test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits) {
171 size_t i;
172 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
173 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
174
175 bitmap_init(bitmap, binfo, false);
176 for (i = 0; i < nbits; i++) {
177 assert_false(bitmap_get(bitmap, binfo, i),
178 "Bit should be unset");
179 }
180
181 bitmap_init(bitmap, binfo, true);
182 for (i = 0; i < nbits; i++) {
183 assert_true(bitmap_get(bitmap, binfo, i), "Bit should be set");
184 }
185
186 free(bitmap);
187 }
188
TEST_BEGIN(test_bitmap_init)189 TEST_BEGIN(test_bitmap_init) {
190 size_t nbits;
191
192 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
193 bitmap_info_t binfo;
194 bitmap_info_init(&binfo, nbits);
195 test_bitmap_init_body(&binfo, nbits);
196 }
197 #define NB(nbits) { \
198 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
199 test_bitmap_init_body(&binfo, nbits); \
200 }
201 NBITS_TAB
202 #undef NB
203 }
204 TEST_END
205
206 static void
test_bitmap_set_body(const bitmap_info_t * binfo,size_t nbits)207 test_bitmap_set_body(const bitmap_info_t *binfo, size_t nbits) {
208 size_t i;
209 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
210 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
211 bitmap_init(bitmap, binfo, false);
212
213 for (i = 0; i < nbits; i++) {
214 bitmap_set(bitmap, binfo, i);
215 }
216 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
217 free(bitmap);
218 }
219
TEST_BEGIN(test_bitmap_set)220 TEST_BEGIN(test_bitmap_set) {
221 size_t nbits;
222
223 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
224 bitmap_info_t binfo;
225 bitmap_info_init(&binfo, nbits);
226 test_bitmap_set_body(&binfo, nbits);
227 }
228 #define NB(nbits) { \
229 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
230 test_bitmap_set_body(&binfo, nbits); \
231 }
232 NBITS_TAB
233 #undef NB
234 }
235 TEST_END
236
237 static void
test_bitmap_unset_body(const bitmap_info_t * binfo,size_t nbits)238 test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits) {
239 size_t i;
240 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
241 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
242 bitmap_init(bitmap, binfo, false);
243
244 for (i = 0; i < nbits; i++) {
245 bitmap_set(bitmap, binfo, i);
246 }
247 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
248 for (i = 0; i < nbits; i++) {
249 bitmap_unset(bitmap, binfo, i);
250 }
251 for (i = 0; i < nbits; i++) {
252 bitmap_set(bitmap, binfo, i);
253 }
254 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
255 free(bitmap);
256 }
257
TEST_BEGIN(test_bitmap_unset)258 TEST_BEGIN(test_bitmap_unset) {
259 size_t nbits;
260
261 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
262 bitmap_info_t binfo;
263 bitmap_info_init(&binfo, nbits);
264 test_bitmap_unset_body(&binfo, nbits);
265 }
266 #define NB(nbits) { \
267 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
268 test_bitmap_unset_body(&binfo, nbits); \
269 }
270 NBITS_TAB
271 #undef NB
272 }
273 TEST_END
274
275 static void
test_bitmap_xfu_body(const bitmap_info_t * binfo,size_t nbits)276 test_bitmap_xfu_body(const bitmap_info_t *binfo, size_t nbits) {
277 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
278 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
279 bitmap_init(bitmap, binfo, false);
280
281 /* Iteratively set bits starting at the beginning. */
282 for (size_t i = 0; i < nbits; i++) {
283 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
284 "First unset bit should be just after previous first unset "
285 "bit");
286 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
287 "First unset bit should be just after previous first unset "
288 "bit");
289 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
290 "First unset bit should be just after previous first unset "
291 "bit");
292 assert_zu_eq(bitmap_sfu(bitmap, binfo), i,
293 "First unset bit should be just after previous first unset "
294 "bit");
295 }
296 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
297
298 /*
299 * Iteratively unset bits starting at the end, and verify that
300 * bitmap_sfu() reaches the unset bits.
301 */
302 for (size_t i = nbits - 1; i < nbits; i--) { /* (nbits..0] */
303 bitmap_unset(bitmap, binfo, i);
304 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
305 "First unset bit should the bit previously unset");
306 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
307 "First unset bit should the bit previously unset");
308 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
309 "First unset bit should the bit previously unset");
310 assert_zu_eq(bitmap_sfu(bitmap, binfo), i,
311 "First unset bit should the bit previously unset");
312 bitmap_unset(bitmap, binfo, i);
313 }
314 assert_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset");
315
316 /*
317 * Iteratively set bits starting at the beginning, and verify that
318 * bitmap_sfu() looks past them.
319 */
320 for (size_t i = 1; i < nbits; i++) {
321 bitmap_set(bitmap, binfo, i - 1);
322 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), i,
323 "First unset bit should be just after the bit previously "
324 "set");
325 assert_zu_eq(bitmap_ffu(bitmap, binfo, (i > 0) ? i-1 : i), i,
326 "First unset bit should be just after the bit previously "
327 "set");
328 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
329 "First unset bit should be just after the bit previously "
330 "set");
331 assert_zu_eq(bitmap_sfu(bitmap, binfo), i,
332 "First unset bit should be just after the bit previously "
333 "set");
334 bitmap_unset(bitmap, binfo, i);
335 }
336 assert_zu_eq(bitmap_ffu(bitmap, binfo, 0), nbits - 1,
337 "First unset bit should be the last bit");
338 assert_zu_eq(bitmap_ffu(bitmap, binfo, (nbits > 1) ? nbits-2 : nbits-1),
339 nbits - 1, "First unset bit should be the last bit");
340 assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits - 1), nbits - 1,
341 "First unset bit should be the last bit");
342 assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits - 1,
343 "First unset bit should be the last bit");
344 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
345
346 /*
347 * Bubble a "usu" pattern through the bitmap and verify that
348 * bitmap_ffu() finds the correct bit for all five min_bit cases.
349 */
350 if (nbits >= 3) {
351 for (size_t i = 0; i < nbits-2; i++) {
352 bitmap_unset(bitmap, binfo, i);
353 bitmap_unset(bitmap, binfo, i+2);
354 if (i > 0) {
355 assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i,
356 "Unexpected first unset bit");
357 }
358 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
359 "Unexpected first unset bit");
360 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), i+2,
361 "Unexpected first unset bit");
362 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+2), i+2,
363 "Unexpected first unset bit");
364 if (i + 3 < nbits) {
365 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+3),
366 nbits, "Unexpected first unset bit");
367 }
368 assert_zu_eq(bitmap_sfu(bitmap, binfo), i,
369 "Unexpected first unset bit");
370 assert_zu_eq(bitmap_sfu(bitmap, binfo), i+2,
371 "Unexpected first unset bit");
372 }
373 }
374
375 /*
376 * Unset the last bit, bubble another unset bit through the bitmap, and
377 * verify that bitmap_ffu() finds the correct bit for all four min_bit
378 * cases.
379 */
380 if (nbits >= 3) {
381 bitmap_unset(bitmap, binfo, nbits-1);
382 for (size_t i = 0; i < nbits-1; i++) {
383 bitmap_unset(bitmap, binfo, i);
384 if (i > 0) {
385 assert_zu_eq(bitmap_ffu(bitmap, binfo, i-1), i,
386 "Unexpected first unset bit");
387 }
388 assert_zu_eq(bitmap_ffu(bitmap, binfo, i), i,
389 "Unexpected first unset bit");
390 assert_zu_eq(bitmap_ffu(bitmap, binfo, i+1), nbits-1,
391 "Unexpected first unset bit");
392 assert_zu_eq(bitmap_ffu(bitmap, binfo, nbits-1),
393 nbits-1, "Unexpected first unset bit");
394
395 assert_zu_eq(bitmap_sfu(bitmap, binfo), i,
396 "Unexpected first unset bit");
397 }
398 assert_zu_eq(bitmap_sfu(bitmap, binfo), nbits-1,
399 "Unexpected first unset bit");
400 }
401
402 free(bitmap);
403 }
404
TEST_BEGIN(test_bitmap_xfu)405 TEST_BEGIN(test_bitmap_xfu) {
406 size_t nbits;
407
408 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
409 bitmap_info_t binfo;
410 bitmap_info_init(&binfo, nbits);
411 test_bitmap_xfu_body(&binfo, nbits);
412 }
413 #define NB(nbits) { \
414 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
415 test_bitmap_xfu_body(&binfo, nbits); \
416 }
417 NBITS_TAB
418 #undef NB
419 }
420 TEST_END
421
422 int
main(void)423 main(void) {
424 return test(
425 test_bitmap_initializer,
426 test_bitmap_size,
427 test_bitmap_init,
428 test_bitmap_set,
429 test_bitmap_unset,
430 test_bitmap_xfu);
431 }
432