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