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 8 typedef struct bitmap_level_s bitmap_level_t; 9 typedef struct bitmap_info_s bitmap_info_t; 10 typedef 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 ffsl more than 2^3 times, use a 21 * 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 89 struct bitmap_level_s { 90 /* Offset of this level's groups within the array of groups. */ 91 size_t group_offset; 92 }; 93 94 struct 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 117 void bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 118 void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 119 size_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 126 bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 127 bool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 128 void bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 129 size_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 130 void 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_)) 134 JEMALLOC_INLINE bool 135 bitmap_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 153 JEMALLOC_INLINE bool 154 bitmap_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 165 JEMALLOC_INLINE void 166 bitmap_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. */ 201 JEMALLOC_INLINE size_t 202 bitmap_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 = (bit - 1) + (i << 6); 227 #endif 228 bitmap_set(bitmap, binfo, bit); 229 return (bit); 230 } 231 232 JEMALLOC_INLINE void 233 bitmap_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