1261071Sjasone#define JEMALLOC_BITMAP_C_ 2234370Sjasone#include "jemalloc/internal/jemalloc_internal.h" 3234370Sjasone 4234370Sjasone/******************************************************************************/ 5234370Sjasone 6296221Sjasone#ifdef USE_TREE 7296221Sjasone 8234370Sjasonevoid 9234370Sjasonebitmap_info_init(bitmap_info_t *binfo, size_t nbits) 10234370Sjasone{ 11234370Sjasone unsigned i; 12234370Sjasone size_t group_count; 13234370Sjasone 14234370Sjasone assert(nbits > 0); 15234370Sjasone assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); 16234370Sjasone 17234370Sjasone /* 18234370Sjasone * Compute the number of groups necessary to store nbits bits, and 19234370Sjasone * progressively work upward through the levels until reaching a level 20234370Sjasone * that requires only one group. 21234370Sjasone */ 22234370Sjasone binfo->levels[0].group_offset = 0; 23286866Sjasone group_count = BITMAP_BITS2GROUPS(nbits); 24234370Sjasone for (i = 1; group_count > 1; i++) { 25234370Sjasone assert(i < BITMAP_MAX_LEVELS); 26234370Sjasone binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 27234370Sjasone + group_count; 28286866Sjasone group_count = BITMAP_BITS2GROUPS(group_count); 29234370Sjasone } 30234370Sjasone binfo->levels[i].group_offset = binfo->levels[i-1].group_offset 31234370Sjasone + group_count; 32286866Sjasone assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX); 33234370Sjasone binfo->nlevels = i; 34234370Sjasone binfo->nbits = nbits; 35234370Sjasone} 36234370Sjasone 37296221Sjasonestatic size_t 38234370Sjasonebitmap_info_ngroups(const bitmap_info_t *binfo) 39234370Sjasone{ 40234370Sjasone 41296221Sjasone return (binfo->levels[binfo->nlevels].group_offset); 42234370Sjasone} 43234370Sjasone 44234370Sjasonevoid 45234370Sjasonebitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) 46234370Sjasone{ 47234370Sjasone size_t extra; 48234370Sjasone unsigned i; 49234370Sjasone 50234370Sjasone /* 51234370Sjasone * Bits are actually inverted with regard to the external bitmap 52234370Sjasone * interface, so the bitmap starts out with all 1 bits, except for 53234370Sjasone * trailing unused bits (if any). Note that each group uses bit 0 to 54234370Sjasone * correspond to the first logical bit in the group, so extra bits 55234370Sjasone * are the most significant bits of the last group. 56234370Sjasone */ 57296221Sjasone memset(bitmap, 0xffU, bitmap_size(binfo)); 58234370Sjasone extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) 59234370Sjasone & BITMAP_GROUP_NBITS_MASK; 60234370Sjasone if (extra != 0) 61234370Sjasone bitmap[binfo->levels[1].group_offset - 1] >>= extra; 62234370Sjasone for (i = 1; i < binfo->nlevels; i++) { 63234370Sjasone size_t group_count = binfo->levels[i].group_offset - 64234370Sjasone binfo->levels[i-1].group_offset; 65234370Sjasone extra = (BITMAP_GROUP_NBITS - (group_count & 66234370Sjasone BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK; 67234370Sjasone if (extra != 0) 68234370Sjasone bitmap[binfo->levels[i+1].group_offset - 1] >>= extra; 69234370Sjasone } 70234370Sjasone} 71296221Sjasone 72296221Sjasone#else /* USE_TREE */ 73296221Sjasone 74296221Sjasonevoid 75296221Sjasonebitmap_info_init(bitmap_info_t *binfo, size_t nbits) 76296221Sjasone{ 77296221Sjasone 78296221Sjasone assert(nbits > 0); 79296221Sjasone assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); 80296221Sjasone 81299587Sjasone binfo->ngroups = BITMAP_BITS2GROUPS(nbits); 82296221Sjasone binfo->nbits = nbits; 83296221Sjasone} 84296221Sjasone 85296221Sjasonestatic size_t 86296221Sjasonebitmap_info_ngroups(const bitmap_info_t *binfo) 87296221Sjasone{ 88296221Sjasone 89296221Sjasone return (binfo->ngroups); 90296221Sjasone} 91296221Sjasone 92296221Sjasonevoid 93296221Sjasonebitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) 94296221Sjasone{ 95296221Sjasone size_t extra; 96296221Sjasone 97296221Sjasone memset(bitmap, 0xffU, bitmap_size(binfo)); 98299587Sjasone extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) 99299587Sjasone & BITMAP_GROUP_NBITS_MASK; 100296221Sjasone if (extra != 0) 101299587Sjasone bitmap[binfo->ngroups - 1] >>= extra; 102296221Sjasone} 103296221Sjasone 104296221Sjasone#endif /* USE_TREE */ 105296221Sjasone 106296221Sjasonesize_t 107296221Sjasonebitmap_size(const bitmap_info_t *binfo) 108296221Sjasone{ 109296221Sjasone 110296221Sjasone return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP); 111296221Sjasone} 112