1234370Sjasone/******************************************************************************/ 2234370Sjasone#ifdef JEMALLOC_H_TYPES 3234370Sjasone 4234370Sjasone/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */ 5234370Sjasone#define LG_BITMAP_MAXBITS LG_RUN_MAXREGS 6234370Sjasone 7234370Sjasonetypedef struct bitmap_level_s bitmap_level_t; 8234370Sjasonetypedef struct bitmap_info_s bitmap_info_t; 9234370Sjasonetypedef unsigned long bitmap_t; 10234370Sjasone#define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 11234370Sjasone 12234370Sjasone/* Number of bits per group. */ 13234370Sjasone#define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 14234370Sjasone#define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) 15234370Sjasone#define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 16234370Sjasone 17234370Sjasone/* Maximum number of levels possible. */ 18234370Sjasone#define BITMAP_MAX_LEVELS \ 19234370Sjasone (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 20234370Sjasone + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 21234370Sjasone 22234370Sjasone#endif /* JEMALLOC_H_TYPES */ 23234370Sjasone/******************************************************************************/ 24234370Sjasone#ifdef JEMALLOC_H_STRUCTS 25234370Sjasone 26234370Sjasonestruct bitmap_level_s { 27234370Sjasone /* Offset of this level's groups within the array of groups. */ 28234370Sjasone size_t group_offset; 29234370Sjasone}; 30234370Sjasone 31234370Sjasonestruct bitmap_info_s { 32234370Sjasone /* Logical number of bits in bitmap (stored at bottom level). */ 33234370Sjasone size_t nbits; 34234370Sjasone 35234370Sjasone /* Number of levels necessary for nbits. */ 36234370Sjasone unsigned nlevels; 37234370Sjasone 38234370Sjasone /* 39234370Sjasone * Only the first (nlevels+1) elements are used, and levels are ordered 40234370Sjasone * bottom to top (e.g. the bottom level is stored in levels[0]). 41234370Sjasone */ 42234370Sjasone bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 43234370Sjasone}; 44234370Sjasone 45234370Sjasone#endif /* JEMALLOC_H_STRUCTS */ 46234370Sjasone/******************************************************************************/ 47234370Sjasone#ifdef JEMALLOC_H_EXTERNS 48234370Sjasone 49234370Sjasonevoid bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 50234370Sjasonesize_t bitmap_info_ngroups(const bitmap_info_t *binfo); 51234370Sjasonesize_t bitmap_size(size_t nbits); 52234370Sjasonevoid bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 53234370Sjasone 54234370Sjasone#endif /* JEMALLOC_H_EXTERNS */ 55234370Sjasone/******************************************************************************/ 56234370Sjasone#ifdef JEMALLOC_H_INLINES 57234370Sjasone 58234370Sjasone#ifndef JEMALLOC_ENABLE_INLINE 59234370Sjasonebool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 60234370Sjasonebool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 61234370Sjasonevoid bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 62234370Sjasonesize_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 63234370Sjasonevoid bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 64234370Sjasone#endif 65234370Sjasone 66234370Sjasone#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 67234370SjasoneJEMALLOC_INLINE bool 68234370Sjasonebitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 69234370Sjasone{ 70234370Sjasone unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 71234370Sjasone bitmap_t rg = bitmap[rgoff]; 72234370Sjasone /* The bitmap is full iff the root group is 0. */ 73234370Sjasone return (rg == 0); 74234370Sjasone} 75234370Sjasone 76234370SjasoneJEMALLOC_INLINE bool 77234370Sjasonebitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 78234370Sjasone{ 79234370Sjasone size_t goff; 80234370Sjasone bitmap_t g; 81234370Sjasone 82234370Sjasone assert(bit < binfo->nbits); 83234370Sjasone goff = bit >> LG_BITMAP_GROUP_NBITS; 84234370Sjasone g = bitmap[goff]; 85234370Sjasone return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))); 86234370Sjasone} 87234370Sjasone 88234370SjasoneJEMALLOC_INLINE void 89234370Sjasonebitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 90234370Sjasone{ 91234370Sjasone size_t goff; 92234370Sjasone bitmap_t *gp; 93234370Sjasone bitmap_t g; 94234370Sjasone 95234370Sjasone assert(bit < binfo->nbits); 96234370Sjasone assert(bitmap_get(bitmap, binfo, bit) == false); 97234370Sjasone goff = bit >> LG_BITMAP_GROUP_NBITS; 98234370Sjasone gp = &bitmap[goff]; 99234370Sjasone g = *gp; 100234370Sjasone assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 101234370Sjasone g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 102234370Sjasone *gp = g; 103234370Sjasone assert(bitmap_get(bitmap, binfo, bit)); 104234370Sjasone /* Propagate group state transitions up the tree. */ 105234370Sjasone if (g == 0) { 106234370Sjasone unsigned i; 107234370Sjasone for (i = 1; i < binfo->nlevels; i++) { 108234370Sjasone bit = goff; 109234370Sjasone goff = bit >> LG_BITMAP_GROUP_NBITS; 110234370Sjasone gp = &bitmap[binfo->levels[i].group_offset + goff]; 111234370Sjasone g = *gp; 112234370Sjasone assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 113234370Sjasone g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 114234370Sjasone *gp = g; 115234370Sjasone if (g != 0) 116234370Sjasone break; 117234370Sjasone } 118234370Sjasone } 119234370Sjasone} 120234370Sjasone 121234370Sjasone/* sfu: set first unset. */ 122234370SjasoneJEMALLOC_INLINE size_t 123234370Sjasonebitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 124234370Sjasone{ 125234370Sjasone size_t bit; 126234370Sjasone bitmap_t g; 127234370Sjasone unsigned i; 128234370Sjasone 129234370Sjasone assert(bitmap_full(bitmap, binfo) == false); 130234370Sjasone 131234370Sjasone i = binfo->nlevels - 1; 132234370Sjasone g = bitmap[binfo->levels[i].group_offset]; 133234370Sjasone bit = ffsl(g) - 1; 134234370Sjasone while (i > 0) { 135234370Sjasone i--; 136234370Sjasone g = bitmap[binfo->levels[i].group_offset + bit]; 137234370Sjasone bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffsl(g) - 1); 138234370Sjasone } 139234370Sjasone 140234370Sjasone bitmap_set(bitmap, binfo, bit); 141234370Sjasone return (bit); 142234370Sjasone} 143234370Sjasone 144234370SjasoneJEMALLOC_INLINE void 145234370Sjasonebitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 146234370Sjasone{ 147234370Sjasone size_t goff; 148234370Sjasone bitmap_t *gp; 149234370Sjasone bitmap_t g; 150234370Sjasone bool propagate; 151234370Sjasone 152234370Sjasone assert(bit < binfo->nbits); 153234370Sjasone assert(bitmap_get(bitmap, binfo, bit)); 154234370Sjasone goff = bit >> LG_BITMAP_GROUP_NBITS; 155234370Sjasone gp = &bitmap[goff]; 156234370Sjasone g = *gp; 157234370Sjasone propagate = (g == 0); 158234370Sjasone assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); 159234370Sjasone g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 160234370Sjasone *gp = g; 161234370Sjasone assert(bitmap_get(bitmap, binfo, bit) == false); 162234370Sjasone /* Propagate group state transitions up the tree. */ 163234370Sjasone if (propagate) { 164234370Sjasone unsigned i; 165234370Sjasone for (i = 1; i < binfo->nlevels; i++) { 166234370Sjasone bit = goff; 167234370Sjasone goff = bit >> LG_BITMAP_GROUP_NBITS; 168234370Sjasone gp = &bitmap[binfo->levels[i].group_offset + goff]; 169234370Sjasone g = *gp; 170234370Sjasone propagate = (g == 0); 171234370Sjasone assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) 172234370Sjasone == 0); 173234370Sjasone g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 174234370Sjasone *gp = g; 175234370Sjasone if (propagate == false) 176234370Sjasone break; 177234370Sjasone } 178234370Sjasone } 179234370Sjasone} 180234370Sjasone 181234370Sjasone#endif 182234370Sjasone 183234370Sjasone#endif /* JEMALLOC_H_INLINES */ 184234370Sjasone/******************************************************************************/ 185