• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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