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