1/******************************************************************************/ 2#ifdef JEMALLOC_H_TYPES 3 4/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */ 5#define LG_BITMAP_MAXBITS LG_RUN_MAXREGS 6#define BITMAP_MAXBITS (ZU(1) << LG_BITMAP_MAXBITS) 7 8typedef struct bitmap_level_s bitmap_level_t; 9typedef struct bitmap_info_s bitmap_info_t; 10typedef unsigned long bitmap_t; 11#define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 12 13/* Number of bits per group. */ 14#define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 15#define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) 16#define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 17 18/* 19 * Do some analysis on how big the bitmap is before we use a tree. For a brute 20 * force linear search, if we would have to call ffs_lu() more than 2^3 times, 21 * use a tree instead. 22 */ 23#if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3 24# define USE_TREE 25#endif 26 27/* Number of groups required to store a given number of bits. */ 28#define BITMAP_BITS2GROUPS(nbits) \ 29 ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS) 30 31/* 32 * Number of groups required at a particular level for a given number of bits. 33 */ 34#define BITMAP_GROUPS_L0(nbits) \ 35 BITMAP_BITS2GROUPS(nbits) 36#define BITMAP_GROUPS_L1(nbits) \ 37 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits)) 38#define BITMAP_GROUPS_L2(nbits) \ 39 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits)))) 40#define BITMAP_GROUPS_L3(nbits) \ 41 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS( \ 42 BITMAP_BITS2GROUPS((nbits))))) 43 44/* 45 * Assuming the number of levels, number of groups required for a given number 46 * of bits. 47 */ 48#define BITMAP_GROUPS_1_LEVEL(nbits) \ 49 BITMAP_GROUPS_L0(nbits) 50#define BITMAP_GROUPS_2_LEVEL(nbits) \ 51 (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits)) 52#define BITMAP_GROUPS_3_LEVEL(nbits) \ 53 (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits)) 54#define BITMAP_GROUPS_4_LEVEL(nbits) \ 55 (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits)) 56 57/* 58 * Maximum number of groups required to support LG_BITMAP_MAXBITS. 59 */ 60#ifdef USE_TREE 61 62#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS 63# define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS) 64#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2 65# define BITMAP_GROUPS_MAX BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS) 66#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3 67# define BITMAP_GROUPS_MAX BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS) 68#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4 69# define BITMAP_GROUPS_MAX BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS) 70#else 71# error "Unsupported bitmap size" 72#endif 73 74/* Maximum number of levels possible. */ 75#define BITMAP_MAX_LEVELS \ 76 (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 77 + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 78 79#else /* USE_TREE */ 80 81#define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS) 82 83#endif /* USE_TREE */ 84 85#endif /* JEMALLOC_H_TYPES */ 86/******************************************************************************/ 87#ifdef JEMALLOC_H_STRUCTS 88 89struct bitmap_level_s { 90 /* Offset of this level's groups within the array of groups. */ 91 size_t group_offset; 92}; 93 94struct bitmap_info_s { 95 /* Logical number of bits in bitmap (stored at bottom level). */ 96 size_t nbits; 97 98#ifdef USE_TREE 99 /* Number of levels necessary for nbits. */ 100 unsigned nlevels; 101 102 /* 103 * Only the first (nlevels+1) elements are used, and levels are ordered 104 * bottom to top (e.g. the bottom level is stored in levels[0]). 105 */ 106 bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 107#else /* USE_TREE */ 108 /* Number of groups necessary for nbits. */ 109 size_t ngroups; 110#endif /* USE_TREE */ 111}; 112 113#endif /* JEMALLOC_H_STRUCTS */ 114/******************************************************************************/ 115#ifdef JEMALLOC_H_EXTERNS 116 117void bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 118void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 119size_t bitmap_size(const bitmap_info_t *binfo); 120 121#endif /* JEMALLOC_H_EXTERNS */ 122/******************************************************************************/ 123#ifdef JEMALLOC_H_INLINES 124 125#ifndef JEMALLOC_ENABLE_INLINE 126bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 127bool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 128void bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 129size_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 130void bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 131#endif 132 133#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 134JEMALLOC_INLINE bool 135bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 136{ 137#ifdef USE_TREE 138 size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 139 bitmap_t rg = bitmap[rgoff]; 140 /* The bitmap is full iff the root group is 0. */ 141 return (rg == 0); 142#else 143 size_t i; 144 145 for (i = 0; i < binfo->ngroups; i++) { 146 if (bitmap[i] != 0) 147 return (false); 148 } 149 return (true); 150#endif 151} 152 153JEMALLOC_INLINE bool 154bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 155{ 156 size_t goff; 157 bitmap_t g; 158 159 assert(bit < binfo->nbits); 160 goff = bit >> LG_BITMAP_GROUP_NBITS; 161 g = bitmap[goff]; 162 return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))); 163} 164 165JEMALLOC_INLINE void 166bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 167{ 168 size_t goff; 169 bitmap_t *gp; 170 bitmap_t g; 171 172 assert(bit < binfo->nbits); 173 assert(!bitmap_get(bitmap, binfo, bit)); 174 goff = bit >> LG_BITMAP_GROUP_NBITS; 175 gp = &bitmap[goff]; 176 g = *gp; 177 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 178 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 179 *gp = g; 180 assert(bitmap_get(bitmap, binfo, bit)); 181#ifdef USE_TREE 182 /* Propagate group state transitions up the tree. */ 183 if (g == 0) { 184 unsigned i; 185 for (i = 1; i < binfo->nlevels; i++) { 186 bit = goff; 187 goff = bit >> LG_BITMAP_GROUP_NBITS; 188 gp = &bitmap[binfo->levels[i].group_offset + goff]; 189 g = *gp; 190 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 191 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 192 *gp = g; 193 if (g != 0) 194 break; 195 } 196 } 197#endif 198} 199 200/* sfu: set first unset. */ 201JEMALLOC_INLINE size_t 202bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 203{ 204 size_t bit; 205 bitmap_t g; 206 unsigned i; 207 208 assert(!bitmap_full(bitmap, binfo)); 209 210#ifdef USE_TREE 211 i = binfo->nlevels - 1; 212 g = bitmap[binfo->levels[i].group_offset]; 213 bit = ffs_lu(g) - 1; 214 while (i > 0) { 215 i--; 216 g = bitmap[binfo->levels[i].group_offset + bit]; 217 bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1); 218 } 219#else 220 i = 0; 221 g = bitmap[0]; 222 while ((bit = ffs_lu(g)) == 0) { 223 i++; 224 g = bitmap[i]; 225 } 226 bit = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1); 227#endif 228 bitmap_set(bitmap, binfo, bit); 229 return (bit); 230} 231 232JEMALLOC_INLINE void 233bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 234{ 235 size_t goff; 236 bitmap_t *gp; 237 bitmap_t g; 238 UNUSED bool propagate; 239 240 assert(bit < binfo->nbits); 241 assert(bitmap_get(bitmap, binfo, bit)); 242 goff = bit >> LG_BITMAP_GROUP_NBITS; 243 gp = &bitmap[goff]; 244 g = *gp; 245 propagate = (g == 0); 246 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); 247 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 248 *gp = g; 249 assert(!bitmap_get(bitmap, binfo, bit)); 250#ifdef USE_TREE 251 /* Propagate group state transitions up the tree. */ 252 if (propagate) { 253 unsigned i; 254 for (i = 1; i < binfo->nlevels; i++) { 255 bit = goff; 256 goff = bit >> LG_BITMAP_GROUP_NBITS; 257 gp = &bitmap[binfo->levels[i].group_offset + goff]; 258 g = *gp; 259 propagate = (g == 0); 260 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) 261 == 0); 262 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 263 *gp = g; 264 if (!propagate) 265 break; 266 } 267 } 268#endif /* USE_TREE */ 269} 270 271#endif 272 273#endif /* JEMALLOC_H_INLINES */ 274/******************************************************************************/ 275