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