1*8e33eff8Schristos #define JEMALLOC_BITMAP_C_ 2*8e33eff8Schristos #include "jemalloc/internal/jemalloc_preamble.h" 3*8e33eff8Schristos #include "jemalloc/internal/jemalloc_internal_includes.h" 4*8e33eff8Schristos 5*8e33eff8Schristos #include "jemalloc/internal/assert.h" 6*8e33eff8Schristos 7*8e33eff8Schristos /******************************************************************************/ 8*8e33eff8Schristos 9*8e33eff8Schristos #ifdef BITMAP_USE_TREE 10*8e33eff8Schristos 11*8e33eff8Schristos void 12*8e33eff8Schristos bitmap_info_init(bitmap_info_t *binfo, size_t nbits) { 13*8e33eff8Schristos unsigned i; 14*8e33eff8Schristos size_t group_count; 15*8e33eff8Schristos 16*8e33eff8Schristos assert(nbits > 0); 17*8e33eff8Schristos assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); 18*8e33eff8Schristos 19*8e33eff8Schristos /* 20*8e33eff8Schristos * Compute the number of groups necessary to store nbits bits, and 21*8e33eff8Schristos * progressively work upward through the levels until reaching a level 22*8e33eff8Schristos * that requires only one group. 23*8e33eff8Schristos */ 24*8e33eff8Schristos binfo->levels[0].group_offset = 0; 25*8e33eff8Schristos group_count = BITMAP_BITS2GROUPS(nbits); 26*8e33eff8Schristos for (i = 1; group_count > 1; i++) { 27*8e33eff8Schristos assert(i < BITMAP_MAX_LEVELS); 28*8e33eff8Schristos binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 29*8e33eff8Schristos + group_count; 30*8e33eff8Schristos group_count = BITMAP_BITS2GROUPS(group_count); 31*8e33eff8Schristos } 32*8e33eff8Schristos binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 33*8e33eff8Schristos + group_count; 34*8e33eff8Schristos assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX); 35*8e33eff8Schristos binfo->nlevels = i; 36*8e33eff8Schristos binfo->nbits = nbits; 37*8e33eff8Schristos } 38*8e33eff8Schristos 39*8e33eff8Schristos static size_t 40*8e33eff8Schristos bitmap_info_ngroups(const bitmap_info_t *binfo) { 41*8e33eff8Schristos return binfo->levels[binfo->nlevels].group_offset; 42*8e33eff8Schristos } 43*8e33eff8Schristos 44*8e33eff8Schristos void 45*8e33eff8Schristos bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill) { 46*8e33eff8Schristos size_t extra; 47*8e33eff8Schristos unsigned i; 48*8e33eff8Schristos 49*8e33eff8Schristos /* 50*8e33eff8Schristos * Bits are actually inverted with regard to the external bitmap 51*8e33eff8Schristos * interface. 52*8e33eff8Schristos */ 53*8e33eff8Schristos 54*8e33eff8Schristos if (fill) { 55*8e33eff8Schristos /* The "filled" bitmap starts out with all 0 bits. */ 56*8e33eff8Schristos memset(bitmap, 0, bitmap_size(binfo)); 57*8e33eff8Schristos return; 58*8e33eff8Schristos } 59*8e33eff8Schristos 60*8e33eff8Schristos /* 61*8e33eff8Schristos * The "empty" bitmap starts out with all 1 bits, except for trailing 62*8e33eff8Schristos * unused bits (if any). Note that each group uses bit 0 to correspond 63*8e33eff8Schristos * to the first logical bit in the group, so extra bits are the most 64*8e33eff8Schristos * significant bits of the last group. 65*8e33eff8Schristos */ 66*8e33eff8Schristos memset(bitmap, 0xffU, bitmap_size(binfo)); 67*8e33eff8Schristos extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) 68*8e33eff8Schristos & BITMAP_GROUP_NBITS_MASK; 69*8e33eff8Schristos if (extra != 0) { 70*8e33eff8Schristos bitmap[binfo->levels[1].group_offset - 1] >>= extra; 71*8e33eff8Schristos } 72*8e33eff8Schristos for (i = 1; i < binfo->nlevels; i++) { 73*8e33eff8Schristos size_t group_count = binfo->levels[i].group_offset - 74*8e33eff8Schristos binfo->levels[i-1].group_offset; 75*8e33eff8Schristos extra = (BITMAP_GROUP_NBITS - (group_count & 76*8e33eff8Schristos BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK; 77*8e33eff8Schristos if (extra != 0) { 78*8e33eff8Schristos bitmap[binfo->levels[i+1].group_offset - 1] >>= extra; 79*8e33eff8Schristos } 80*8e33eff8Schristos } 81*8e33eff8Schristos } 82*8e33eff8Schristos 83*8e33eff8Schristos #else /* BITMAP_USE_TREE */ 84*8e33eff8Schristos 85*8e33eff8Schristos void 86*8e33eff8Schristos bitmap_info_init(bitmap_info_t *binfo, size_t nbits) { 87*8e33eff8Schristos assert(nbits > 0); 88*8e33eff8Schristos assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); 89*8e33eff8Schristos 90*8e33eff8Schristos binfo->ngroups = BITMAP_BITS2GROUPS(nbits); 91*8e33eff8Schristos binfo->nbits = nbits; 92*8e33eff8Schristos } 93*8e33eff8Schristos 94*8e33eff8Schristos static size_t 95*8e33eff8Schristos bitmap_info_ngroups(const bitmap_info_t *binfo) { 96*8e33eff8Schristos return binfo->ngroups; 97*8e33eff8Schristos } 98*8e33eff8Schristos 99*8e33eff8Schristos void 100*8e33eff8Schristos bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill) { 101*8e33eff8Schristos size_t extra; 102*8e33eff8Schristos 103*8e33eff8Schristos if (fill) { 104*8e33eff8Schristos memset(bitmap, 0, bitmap_size(binfo)); 105*8e33eff8Schristos return; 106*8e33eff8Schristos } 107*8e33eff8Schristos 108*8e33eff8Schristos memset(bitmap, 0xffU, bitmap_size(binfo)); 109*8e33eff8Schristos extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) 110*8e33eff8Schristos & BITMAP_GROUP_NBITS_MASK; 111*8e33eff8Schristos if (extra != 0) { 112*8e33eff8Schristos bitmap[binfo->ngroups - 1] >>= extra; 113*8e33eff8Schristos } 114*8e33eff8Schristos } 115*8e33eff8Schristos 116*8e33eff8Schristos #endif /* BITMAP_USE_TREE */ 117*8e33eff8Schristos 118*8e33eff8Schristos size_t 119*8e33eff8Schristos bitmap_size(const bitmap_info_t *binfo) { 120*8e33eff8Schristos return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP); 121*8e33eff8Schristos } 122