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 {
98 bitmap_info_t binfo_dyn;
99 bitmap_info_init(&binfo_dyn, nbits);
100
101 assert_zu_eq(bitmap_size(binfo), bitmap_size(&binfo_dyn),
102 "Unexpected difference between static and dynamic initialization, "
103 "nbits=%zu", nbits);
104 assert_zu_eq(binfo->nbits, binfo_dyn.nbits,
105 "Unexpected difference between static and dynamic initialization, "
106 "nbits=%zu", nbits);
107 #ifdef BITMAP_USE_TREE
108 assert_u_eq(binfo->nlevels, binfo_dyn.nlevels,
109 "Unexpected difference between static and dynamic initialization, "
110 "nbits=%zu", nbits);
111 {
112 unsigned i;
113
114 for (i = 0; i < binfo->nlevels; i++) {
115 assert_zu_eq(binfo->levels[i].group_offset,
116 binfo_dyn.levels[i].group_offset,
117 "Unexpected difference between static and dynamic "
118 "initialization, nbits=%zu, level=%u", nbits, i);
119 }
120 }
121 #else
122 assert_zu_eq(binfo->ngroups, binfo_dyn.ngroups,
123 "Unexpected difference between static and dynamic initialization");
124 #endif
125 }
126
TEST_BEGIN(test_bitmap_initializer)127 TEST_BEGIN(test_bitmap_initializer)
128 {
129 #define NB(nbits) { \
130 if (nbits <= BITMAP_MAXBITS) { \
131 bitmap_info_t binfo = \
132 BITMAP_INFO_INITIALIZER(nbits); \
133 test_bitmap_initializer_body(&binfo, nbits); \
134 } \
135 }
136 NBITS_TAB
137 #undef NB
138 }
139 TEST_END
140
141 static size_t
test_bitmap_size_body(const bitmap_info_t * binfo,size_t nbits,size_t prev_size)142 test_bitmap_size_body(const bitmap_info_t *binfo, size_t nbits,
143 size_t prev_size)
144 {
145 size_t size = bitmap_size(binfo);
146 assert_zu_ge(size, (nbits >> 3),
147 "Bitmap size is smaller than expected");
148 assert_zu_ge(size, prev_size, "Bitmap size is smaller than expected");
149 return (size);
150 }
151
TEST_BEGIN(test_bitmap_size)152 TEST_BEGIN(test_bitmap_size)
153 {
154 size_t nbits, prev_size;
155
156 prev_size = 0;
157 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
158 bitmap_info_t binfo;
159 bitmap_info_init(&binfo, nbits);
160 prev_size = test_bitmap_size_body(&binfo, nbits, prev_size);
161 }
162 #define NB(nbits) { \
163 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
164 prev_size = test_bitmap_size_body(&binfo, nbits, \
165 prev_size); \
166 }
167 prev_size = 0;
168 NBITS_TAB
169 #undef NB
170 }
171 TEST_END
172
173 static void
test_bitmap_init_body(const bitmap_info_t * binfo,size_t nbits)174 test_bitmap_init_body(const bitmap_info_t *binfo, size_t nbits)
175 {
176 size_t i;
177 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
178 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
179 bitmap_init(bitmap, binfo);
180
181 for (i = 0; i < nbits; i++) {
182 assert_false(bitmap_get(bitmap, binfo, i),
183 "Bit should be unset");
184 }
185 free(bitmap);
186 }
187
TEST_BEGIN(test_bitmap_init)188 TEST_BEGIN(test_bitmap_init)
189 {
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 {
209 size_t i;
210 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
211 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
212 bitmap_init(bitmap, binfo);
213
214 for (i = 0; i < nbits; i++)
215 bitmap_set(bitmap, binfo, i);
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 {
222 size_t nbits;
223
224 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
225 bitmap_info_t binfo;
226 bitmap_info_init(&binfo, nbits);
227 test_bitmap_set_body(&binfo, nbits);
228 }
229 #define NB(nbits) { \
230 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
231 test_bitmap_set_body(&binfo, nbits); \
232 }
233 NBITS_TAB
234 #undef NB
235 }
236 TEST_END
237
238 static void
test_bitmap_unset_body(const bitmap_info_t * binfo,size_t nbits)239 test_bitmap_unset_body(const bitmap_info_t *binfo, size_t nbits)
240 {
241 size_t i;
242 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
243 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
244 bitmap_init(bitmap, binfo);
245
246 for (i = 0; i < nbits; i++)
247 bitmap_set(bitmap, binfo, i);
248 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
249 for (i = 0; i < nbits; i++)
250 bitmap_unset(bitmap, binfo, i);
251 for (i = 0; i < nbits; i++)
252 bitmap_set(bitmap, binfo, i);
253 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
254 free(bitmap);
255 }
256
TEST_BEGIN(test_bitmap_unset)257 TEST_BEGIN(test_bitmap_unset)
258 {
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_sfu_body(const bitmap_info_t * binfo,size_t nbits)276 test_bitmap_sfu_body(const bitmap_info_t *binfo, size_t nbits)
277 {
278 size_t i;
279 bitmap_t *bitmap = (bitmap_t *)malloc(bitmap_size(binfo));
280 assert_ptr_not_null(bitmap, "Unexpected malloc() failure");
281 bitmap_init(bitmap, binfo);
282
283 /* Iteratively set bits starting at the beginning. */
284 for (i = 0; i < nbits; i++) {
285 assert_zd_eq(bitmap_sfu(bitmap, binfo), i,
286 "First unset bit should be just after previous first unset "
287 "bit");
288 }
289 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
290
291 /*
292 * Iteratively unset bits starting at the end, and verify that
293 * bitmap_sfu() reaches the unset bits.
294 */
295 for (i = nbits - 1; i < nbits; i--) { /* (nbits..0] */
296 bitmap_unset(bitmap, binfo, i);
297 assert_zd_eq(bitmap_sfu(bitmap, binfo), i,
298 "First unset bit should the bit previously unset");
299 bitmap_unset(bitmap, binfo, i);
300 }
301 assert_false(bitmap_get(bitmap, binfo, 0), "Bit should be unset");
302
303 /*
304 * Iteratively set bits starting at the beginning, and verify that
305 * bitmap_sfu() looks past them.
306 */
307 for (i = 1; i < nbits; i++) {
308 bitmap_set(bitmap, binfo, i - 1);
309 assert_zd_eq(bitmap_sfu(bitmap, binfo), i,
310 "First unset bit should be just after the bit previously "
311 "set");
312 bitmap_unset(bitmap, binfo, i);
313 }
314 assert_zd_eq(bitmap_sfu(bitmap, binfo), nbits - 1,
315 "First unset bit should be the last bit");
316 assert_true(bitmap_full(bitmap, binfo), "All bits should be set");
317 free(bitmap);
318 }
319
TEST_BEGIN(test_bitmap_sfu)320 TEST_BEGIN(test_bitmap_sfu)
321 {
322 size_t nbits;
323
324 for (nbits = 1; nbits <= BITMAP_MAXBITS; nbits++) {
325 bitmap_info_t binfo;
326 bitmap_info_init(&binfo, nbits);
327 test_bitmap_sfu_body(&binfo, nbits);
328 }
329 #define NB(nbits) { \
330 bitmap_info_t binfo = BITMAP_INFO_INITIALIZER(nbits); \
331 test_bitmap_sfu_body(&binfo, nbits); \
332 }
333 NBITS_TAB
334 #undef NB
335 }
336 TEST_END
337
338 int
main(void)339 main(void)
340 {
341 return (test(
342 test_bitmap_initializer,
343 test_bitmap_size,
344 test_bitmap_init,
345 test_bitmap_set,
346 test_bitmap_unset,
347 test_bitmap_sfu));
348 }
349