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 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
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
bitmap_full(bitmap_t * bitmap,const bitmap_info_t * binfo)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
bitmap_get(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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
bitmap_set(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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
bitmap_sfu(bitmap_t * bitmap,const bitmap_info_t * binfo)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 = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1);
227 #endif
228 bitmap_set(bitmap, binfo, bit);
229 return (bit);
230 }
231
232 JEMALLOC_INLINE void
bitmap_unset(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)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