1 #define JEMALLOC_BITMAP_C_ 2 #include "jemalloc/internal/jemalloc_internal.h" 3 4 /******************************************************************************/ 5 6 void 7 bitmap_info_init(bitmap_info_t *binfo, size_t nbits) 8 { 9 unsigned i; 10 size_t group_count; 11 12 assert(nbits > 0); 13 assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); 14 15 /* 16 * Compute the number of groups necessary to store nbits bits, and 17 * progressively work upward through the levels until reaching a level 18 * that requires only one group. 19 */ 20 binfo->levels[0].group_offset = 0; 21 group_count = BITMAP_BITS2GROUPS(nbits); 22 for (i = 1; group_count > 1; i++) { 23 assert(i < BITMAP_MAX_LEVELS); 24 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 25 + group_count; 26 group_count = BITMAP_BITS2GROUPS(group_count); 27 } 28 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 29 + group_count; 30 assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX); 31 binfo->nlevels = i; 32 binfo->nbits = nbits; 33 } 34 35 size_t 36 bitmap_info_ngroups(const bitmap_info_t *binfo) 37 { 38 39 return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP); 40 } 41 42 size_t 43 bitmap_size(size_t nbits) 44 { 45 bitmap_info_t binfo; 46 47 bitmap_info_init(&binfo, nbits); 48 return (bitmap_info_ngroups(&binfo)); 49 } 50 51 void 52 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) 53 { 54 size_t extra; 55 unsigned i; 56 57 /* 58 * Bits are actually inverted with regard to the external bitmap 59 * interface, so the bitmap starts out with all 1 bits, except for 60 * trailing unused bits (if any). Note that each group uses bit 0 to 61 * correspond to the first logical bit in the group, so extra bits 62 * are the most significant bits of the last group. 63 */ 64 memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset << 65 LG_SIZEOF_BITMAP); 66 extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) 67 & BITMAP_GROUP_NBITS_MASK; 68 if (extra != 0) 69 bitmap[binfo->levels[1].group_offset - 1] >>= extra; 70 for (i = 1; i < binfo->nlevels; i++) { 71 size_t group_count = binfo->levels[i].group_offset - 72 binfo->levels[i-1].group_offset; 73 extra = (BITMAP_GROUP_NBITS - (group_count & 74 BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK; 75 if (extra != 0) 76 bitmap[binfo->levels[i+1].group_offset - 1] >>= extra; 77 } 78 } 79