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