1 #ifndef JEMALLOC_INTERNAL_BITMAP_H 2 #define JEMALLOC_INTERNAL_BITMAP_H 3 4 #include "jemalloc/internal/arena_types.h" 5 #include "jemalloc/internal/bit_util.h" 6 #include "jemalloc/internal/size_classes.h" 7 8 typedef unsigned long bitmap_t; 9 #define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 10 11 /* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */ 12 #if LG_SLAB_MAXREGS > LG_CEIL_NSIZES 13 /* Maximum bitmap bit count is determined by maximum regions per slab. */ 14 # define LG_BITMAP_MAXBITS LG_SLAB_MAXREGS 15 #else 16 /* Maximum bitmap bit count is determined by number of extent size classes. */ 17 # define LG_BITMAP_MAXBITS LG_CEIL_NSIZES 18 #endif 19 #define BITMAP_MAXBITS (ZU(1) << LG_BITMAP_MAXBITS) 20 21 /* Number of bits per group. */ 22 #define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 23 #define BITMAP_GROUP_NBITS (1U << LG_BITMAP_GROUP_NBITS) 24 #define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 25 26 /* 27 * Do some analysis on how big the bitmap is before we use a tree. For a brute 28 * force linear search, if we would have to call ffs_lu() more than 2^3 times, 29 * use a tree instead. 30 */ 31 #if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3 32 # define BITMAP_USE_TREE 33 #endif 34 35 /* Number of groups required to store a given number of bits. */ 36 #define BITMAP_BITS2GROUPS(nbits) \ 37 (((nbits) + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS) 38 39 /* 40 * Number of groups required at a particular level for a given number of bits. 41 */ 42 #define BITMAP_GROUPS_L0(nbits) \ 43 BITMAP_BITS2GROUPS(nbits) 44 #define BITMAP_GROUPS_L1(nbits) \ 45 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits)) 46 #define BITMAP_GROUPS_L2(nbits) \ 47 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits)))) 48 #define BITMAP_GROUPS_L3(nbits) \ 49 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS( \ 50 BITMAP_BITS2GROUPS((nbits))))) 51 #define BITMAP_GROUPS_L4(nbits) \ 52 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS( \ 53 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits)))))) 54 55 /* 56 * Assuming the number of levels, number of groups required for a given number 57 * of bits. 58 */ 59 #define BITMAP_GROUPS_1_LEVEL(nbits) \ 60 BITMAP_GROUPS_L0(nbits) 61 #define BITMAP_GROUPS_2_LEVEL(nbits) \ 62 (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits)) 63 #define BITMAP_GROUPS_3_LEVEL(nbits) \ 64 (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits)) 65 #define BITMAP_GROUPS_4_LEVEL(nbits) \ 66 (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits)) 67 #define BITMAP_GROUPS_5_LEVEL(nbits) \ 68 (BITMAP_GROUPS_4_LEVEL(nbits) + BITMAP_GROUPS_L4(nbits)) 69 70 /* 71 * Maximum number of groups required to support LG_BITMAP_MAXBITS. 72 */ 73 #ifdef BITMAP_USE_TREE 74 75 #if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS 76 # define BITMAP_GROUPS(nbits) BITMAP_GROUPS_1_LEVEL(nbits) 77 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS) 78 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2 79 # define BITMAP_GROUPS(nbits) BITMAP_GROUPS_2_LEVEL(nbits) 80 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS) 81 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3 82 # define BITMAP_GROUPS(nbits) BITMAP_GROUPS_3_LEVEL(nbits) 83 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS) 84 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4 85 # define BITMAP_GROUPS(nbits) BITMAP_GROUPS_4_LEVEL(nbits) 86 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS) 87 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 5 88 # define BITMAP_GROUPS(nbits) BITMAP_GROUPS_5_LEVEL(nbits) 89 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_5_LEVEL(BITMAP_MAXBITS) 90 #else 91 # error "Unsupported bitmap size" 92 #endif 93 94 /* 95 * Maximum number of levels possible. This could be statically computed based 96 * on LG_BITMAP_MAXBITS: 97 * 98 * #define BITMAP_MAX_LEVELS \ 99 * (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 100 * + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 101 * 102 * However, that would not allow the generic BITMAP_INFO_INITIALIZER() macro, so 103 * instead hardcode BITMAP_MAX_LEVELS to the largest number supported by the 104 * various cascading macros. The only additional cost this incurs is some 105 * unused trailing entries in bitmap_info_t structures; the bitmaps themselves 106 * are not impacted. 107 */ 108 #define BITMAP_MAX_LEVELS 5 109 110 #define BITMAP_INFO_INITIALIZER(nbits) { \ 111 /* nbits. */ \ 112 nbits, \ 113 /* nlevels. */ \ 114 (BITMAP_GROUPS_L0(nbits) > BITMAP_GROUPS_L1(nbits)) + \ 115 (BITMAP_GROUPS_L1(nbits) > BITMAP_GROUPS_L2(nbits)) + \ 116 (BITMAP_GROUPS_L2(nbits) > BITMAP_GROUPS_L3(nbits)) + \ 117 (BITMAP_GROUPS_L3(nbits) > BITMAP_GROUPS_L4(nbits)) + 1, \ 118 /* levels. */ \ 119 { \ 120 {0}, \ 121 {BITMAP_GROUPS_L0(nbits)}, \ 122 {BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)}, \ 123 {BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits) + \ 124 BITMAP_GROUPS_L0(nbits)}, \ 125 {BITMAP_GROUPS_L3(nbits) + BITMAP_GROUPS_L2(nbits) + \ 126 BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)}, \ 127 {BITMAP_GROUPS_L4(nbits) + BITMAP_GROUPS_L3(nbits) + \ 128 BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits) \ 129 + BITMAP_GROUPS_L0(nbits)} \ 130 } \ 131 } 132 133 #else /* BITMAP_USE_TREE */ 134 135 #define BITMAP_GROUPS(nbits) BITMAP_BITS2GROUPS(nbits) 136 #define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS) 137 138 #define BITMAP_INFO_INITIALIZER(nbits) { \ 139 /* nbits. */ \ 140 nbits, \ 141 /* ngroups. */ \ 142 BITMAP_BITS2GROUPS(nbits) \ 143 } 144 145 #endif /* BITMAP_USE_TREE */ 146 147 typedef struct bitmap_level_s { 148 /* Offset of this level's groups within the array of groups. */ 149 size_t group_offset; 150 } bitmap_level_t; 151 152 typedef struct bitmap_info_s { 153 /* Logical number of bits in bitmap (stored at bottom level). */ 154 size_t nbits; 155 156 #ifdef BITMAP_USE_TREE 157 /* Number of levels necessary for nbits. */ 158 unsigned nlevels; 159 160 /* 161 * Only the first (nlevels+1) elements are used, and levels are ordered 162 * bottom to top (e.g. the bottom level is stored in levels[0]). 163 */ 164 bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 165 #else /* BITMAP_USE_TREE */ 166 /* Number of groups necessary for nbits. */ 167 size_t ngroups; 168 #endif /* BITMAP_USE_TREE */ 169 } bitmap_info_t; 170 171 void bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 172 void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill); 173 size_t bitmap_size(const bitmap_info_t *binfo); 174 175 static inline bool 176 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) { 177 #ifdef BITMAP_USE_TREE 178 size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 179 bitmap_t rg = bitmap[rgoff]; 180 /* The bitmap is full iff the root group is 0. */ 181 return (rg == 0); 182 #else 183 size_t i; 184 185 for (i = 0; i < binfo->ngroups; i++) { 186 if (bitmap[i] != 0) { 187 return false; 188 } 189 } 190 return true; 191 #endif 192 } 193 194 static inline bool 195 bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) { 196 size_t goff; 197 bitmap_t g; 198 199 assert(bit < binfo->nbits); 200 goff = bit >> LG_BITMAP_GROUP_NBITS; 201 g = bitmap[goff]; 202 return !(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 203 } 204 205 static inline void 206 bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) { 207 size_t goff; 208 bitmap_t *gp; 209 bitmap_t g; 210 211 assert(bit < binfo->nbits); 212 assert(!bitmap_get(bitmap, binfo, bit)); 213 goff = bit >> LG_BITMAP_GROUP_NBITS; 214 gp = &bitmap[goff]; 215 g = *gp; 216 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 217 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 218 *gp = g; 219 assert(bitmap_get(bitmap, binfo, bit)); 220 #ifdef BITMAP_USE_TREE 221 /* Propagate group state transitions up the tree. */ 222 if (g == 0) { 223 unsigned i; 224 for (i = 1; i < binfo->nlevels; i++) { 225 bit = goff; 226 goff = bit >> LG_BITMAP_GROUP_NBITS; 227 gp = &bitmap[binfo->levels[i].group_offset + goff]; 228 g = *gp; 229 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 230 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 231 *gp = g; 232 if (g != 0) { 233 break; 234 } 235 } 236 } 237 #endif 238 } 239 240 /* ffu: find first unset >= bit. */ 241 static inline size_t 242 bitmap_ffu(const bitmap_t *bitmap, const bitmap_info_t *binfo, size_t min_bit) { 243 assert(min_bit < binfo->nbits); 244 245 #ifdef BITMAP_USE_TREE 246 size_t bit = 0; 247 for (unsigned level = binfo->nlevels; level--;) { 248 size_t lg_bits_per_group = (LG_BITMAP_GROUP_NBITS * (level + 249 1)); 250 bitmap_t group = bitmap[binfo->levels[level].group_offset + (bit 251 >> lg_bits_per_group)]; 252 unsigned group_nmask = (unsigned)(((min_bit > bit) ? (min_bit - 253 bit) : 0) >> (lg_bits_per_group - LG_BITMAP_GROUP_NBITS)); 254 assert(group_nmask <= BITMAP_GROUP_NBITS); 255 bitmap_t group_mask = ~((1LU << group_nmask) - 1); 256 bitmap_t group_masked = group & group_mask; 257 if (group_masked == 0LU) { 258 if (group == 0LU) { 259 return binfo->nbits; 260 } 261 /* 262 * min_bit was preceded by one or more unset bits in 263 * this group, but there are no other unset bits in this 264 * group. Try again starting at the first bit of the 265 * next sibling. This will recurse at most once per 266 * non-root level. 267 */ 268 size_t sib_base = bit + (ZU(1) << lg_bits_per_group); 269 assert(sib_base > min_bit); 270 assert(sib_base > bit); 271 if (sib_base >= binfo->nbits) { 272 return binfo->nbits; 273 } 274 return bitmap_ffu(bitmap, binfo, sib_base); 275 } 276 bit += ((size_t)(ffs_lu(group_masked) - 1)) << 277 (lg_bits_per_group - LG_BITMAP_GROUP_NBITS); 278 } 279 assert(bit >= min_bit); 280 assert(bit < binfo->nbits); 281 return bit; 282 #else 283 size_t i = min_bit >> LG_BITMAP_GROUP_NBITS; 284 bitmap_t g = bitmap[i] & ~((1LU << (min_bit & BITMAP_GROUP_NBITS_MASK)) 285 - 1); 286 size_t bit; 287 do { 288 bit = ffs_lu(g); 289 if (bit != 0) { 290 return (i << LG_BITMAP_GROUP_NBITS) + (bit - 1); 291 } 292 i++; 293 g = bitmap[i]; 294 } while (i < binfo->ngroups); 295 return binfo->nbits; 296 #endif 297 } 298 299 /* sfu: set first unset. */ 300 static inline size_t 301 bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) { 302 size_t bit; 303 bitmap_t g; 304 unsigned i; 305 306 assert(!bitmap_full(bitmap, binfo)); 307 308 #ifdef BITMAP_USE_TREE 309 i = binfo->nlevels - 1; 310 g = bitmap[binfo->levels[i].group_offset]; 311 bit = ffs_lu(g) - 1; 312 while (i > 0) { 313 i--; 314 g = bitmap[binfo->levels[i].group_offset + bit]; 315 bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1); 316 } 317 #else 318 i = 0; 319 g = bitmap[0]; 320 while ((bit = ffs_lu(g)) == 0) { 321 i++; 322 g = bitmap[i]; 323 } 324 bit = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1); 325 #endif 326 bitmap_set(bitmap, binfo, bit); 327 return bit; 328 } 329 330 static inline void 331 bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) { 332 size_t goff; 333 bitmap_t *gp; 334 bitmap_t g; 335 UNUSED bool propagate; 336 337 assert(bit < binfo->nbits); 338 assert(bitmap_get(bitmap, binfo, bit)); 339 goff = bit >> LG_BITMAP_GROUP_NBITS; 340 gp = &bitmap[goff]; 341 g = *gp; 342 propagate = (g == 0); 343 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); 344 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 345 *gp = g; 346 assert(!bitmap_get(bitmap, binfo, bit)); 347 #ifdef BITMAP_USE_TREE 348 /* Propagate group state transitions up the tree. */ 349 if (propagate) { 350 unsigned i; 351 for (i = 1; i < binfo->nlevels; i++) { 352 bit = goff; 353 goff = bit >> LG_BITMAP_GROUP_NBITS; 354 gp = &bitmap[binfo->levels[i].group_offset + goff]; 355 g = *gp; 356 propagate = (g == 0); 357 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) 358 == 0); 359 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 360 *gp = g; 361 if (!propagate) { 362 break; 363 } 364 } 365 } 366 #endif /* BITMAP_USE_TREE */ 367 } 368 369 #endif /* JEMALLOC_INTERNAL_BITMAP_H */ 370