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