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 /* Number of groups required to store a given number of bits. */
19 #define BITMAP_BITS2GROUPS(nbits) \
20 ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
21
22 /*
23 * Number of groups required at a particular level for a given number of bits.
24 */
25 #define BITMAP_GROUPS_L0(nbits) \
26 BITMAP_BITS2GROUPS(nbits)
27 #define BITMAP_GROUPS_L1(nbits) \
28 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits))
29 #define BITMAP_GROUPS_L2(nbits) \
30 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))
31 #define BITMAP_GROUPS_L3(nbits) \
32 BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS( \
33 BITMAP_BITS2GROUPS((nbits)))))
34
35 /*
36 * Assuming the number of levels, number of groups required for a given number
37 * of bits.
38 */
39 #define BITMAP_GROUPS_1_LEVEL(nbits) \
40 BITMAP_GROUPS_L0(nbits)
41 #define BITMAP_GROUPS_2_LEVEL(nbits) \
42 (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits))
43 #define BITMAP_GROUPS_3_LEVEL(nbits) \
44 (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
45 #define BITMAP_GROUPS_4_LEVEL(nbits) \
46 (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
47
48 /*
49 * Maximum number of groups required to support LG_BITMAP_MAXBITS.
50 */
51 #if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
52 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
53 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
54 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
55 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
56 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
57 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
58 # define BITMAP_GROUPS_MAX BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
59 #else
60 # error "Unsupported bitmap size"
61 #endif
62
63 /* Maximum number of levels possible. */
64 #define BITMAP_MAX_LEVELS \
65 (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \
66 + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
67
68 #endif /* JEMALLOC_H_TYPES */
69 /******************************************************************************/
70 #ifdef JEMALLOC_H_STRUCTS
71
72 struct bitmap_level_s {
73 /* Offset of this level's groups within the array of groups. */
74 size_t group_offset;
75 };
76
77 struct bitmap_info_s {
78 /* Logical number of bits in bitmap (stored at bottom level). */
79 size_t nbits;
80
81 /* Number of levels necessary for nbits. */
82 unsigned nlevels;
83
84 /*
85 * Only the first (nlevels+1) elements are used, and levels are ordered
86 * bottom to top (e.g. the bottom level is stored in levels[0]).
87 */
88 bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
89 };
90
91 #endif /* JEMALLOC_H_STRUCTS */
92 /******************************************************************************/
93 #ifdef JEMALLOC_H_EXTERNS
94
95 void bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
96 size_t bitmap_info_ngroups(const bitmap_info_t *binfo);
97 size_t bitmap_size(size_t nbits);
98 void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
99
100 #endif /* JEMALLOC_H_EXTERNS */
101 /******************************************************************************/
102 #ifdef JEMALLOC_H_INLINES
103
104 #ifndef JEMALLOC_ENABLE_INLINE
105 bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
106 bool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
107 void bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
108 size_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
109 void bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
110 #endif
111
112 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
113 JEMALLOC_INLINE bool
bitmap_full(bitmap_t * bitmap,const bitmap_info_t * binfo)114 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
115 {
116 unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
117 bitmap_t rg = bitmap[rgoff];
118 /* The bitmap is full iff the root group is 0. */
119 return (rg == 0);
120 }
121
122 JEMALLOC_INLINE bool
bitmap_get(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)123 bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
124 {
125 size_t goff;
126 bitmap_t g;
127
128 assert(bit < binfo->nbits);
129 goff = bit >> LG_BITMAP_GROUP_NBITS;
130 g = bitmap[goff];
131 return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))));
132 }
133
134 JEMALLOC_INLINE void
bitmap_set(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)135 bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
136 {
137 size_t goff;
138 bitmap_t *gp;
139 bitmap_t g;
140
141 assert(bit < binfo->nbits);
142 assert(!bitmap_get(bitmap, binfo, bit));
143 goff = bit >> LG_BITMAP_GROUP_NBITS;
144 gp = &bitmap[goff];
145 g = *gp;
146 assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
147 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
148 *gp = g;
149 assert(bitmap_get(bitmap, binfo, bit));
150 /* Propagate group state transitions up the tree. */
151 if (g == 0) {
152 unsigned i;
153 for (i = 1; i < binfo->nlevels; i++) {
154 bit = goff;
155 goff = bit >> LG_BITMAP_GROUP_NBITS;
156 gp = &bitmap[binfo->levels[i].group_offset + goff];
157 g = *gp;
158 assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
159 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
160 *gp = g;
161 if (g != 0)
162 break;
163 }
164 }
165 }
166
167 /* sfu: set first unset. */
168 JEMALLOC_INLINE size_t
bitmap_sfu(bitmap_t * bitmap,const bitmap_info_t * binfo)169 bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
170 {
171 size_t bit;
172 bitmap_t g;
173 unsigned i;
174
175 assert(!bitmap_full(bitmap, binfo));
176
177 i = binfo->nlevels - 1;
178 g = bitmap[binfo->levels[i].group_offset];
179 bit = jemalloc_ffsl(g) - 1;
180 while (i > 0) {
181 i--;
182 g = bitmap[binfo->levels[i].group_offset + bit];
183 bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1);
184 }
185
186 bitmap_set(bitmap, binfo, bit);
187 return (bit);
188 }
189
190 JEMALLOC_INLINE void
bitmap_unset(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)191 bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
192 {
193 size_t goff;
194 bitmap_t *gp;
195 bitmap_t g;
196 bool propagate;
197
198 assert(bit < binfo->nbits);
199 assert(bitmap_get(bitmap, binfo, bit));
200 goff = bit >> LG_BITMAP_GROUP_NBITS;
201 gp = &bitmap[goff];
202 g = *gp;
203 propagate = (g == 0);
204 assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
205 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
206 *gp = g;
207 assert(!bitmap_get(bitmap, binfo, bit));
208 /* Propagate group state transitions up the tree. */
209 if (propagate) {
210 unsigned i;
211 for (i = 1; i < binfo->nlevels; i++) {
212 bit = goff;
213 goff = bit >> LG_BITMAP_GROUP_NBITS;
214 gp = &bitmap[binfo->levels[i].group_offset + goff];
215 g = *gp;
216 propagate = (g == 0);
217 assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))
218 == 0);
219 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
220 *gp = g;
221 if (!propagate)
222 break;
223 }
224 }
225 }
226
227 #endif
228
229 #endif /* JEMALLOC_H_INLINES */
230 /******************************************************************************/
231