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
bitmap_full(bitmap_t * bitmap,const bitmap_info_t * binfo)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
bitmap_get(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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
bitmap_set(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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
bitmap_ffu(const bitmap_t * bitmap,const bitmap_info_t * binfo,size_t min_bit)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
bitmap_sfu(bitmap_t * bitmap,const bitmap_info_t * binfo)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
bitmap_unset(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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