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