bitmap.h revision 7427525c28d58c423a68930160e3b0fe577fe953 
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
7typedef struct bitmap_level_s bitmap_level_t;
8typedef struct bitmap_info_s bitmap_info_t;
9typedef unsigned long bitmap_t;
10#define	LG_SIZEOF_BITMAP	LG_SIZEOF_LONG
11
12/* Number of bits per group. */
13#define	LG_BITMAP_GROUP_NBITS		(LG_SIZEOF_BITMAP + 3)
14#define	BITMAP_GROUP_NBITS		(ZU(1) << LG_BITMAP_GROUP_NBITS)
15#define	BITMAP_GROUP_NBITS_MASK		(BITMAP_GROUP_NBITS-1)
16
17/* Maximum number of levels possible. */
18#define	BITMAP_MAX_LEVELS						\
19    (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)				\
20    + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
21
22#endif /* JEMALLOC_H_TYPES */
23/******************************************************************************/
24#ifdef JEMALLOC_H_STRUCTS
25
26struct bitmap_level_s {
27	/* Offset of this level's groups within the array of groups. */
28	size_t group_offset;
29};
30
31struct bitmap_info_s {
32	/* Logical number of bits in bitmap (stored at bottom level). */
33	size_t nbits;
34
35	/* Number of levels necessary for nbits. */
36	unsigned nlevels;
37
38	/*
39	 * Only the first (nlevels+1) elements are used, and levels are ordered
40	 * bottom to top (e.g. the bottom level is stored in levels[0]).
41	 */
42	bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
43};
44
45#endif /* JEMALLOC_H_STRUCTS */
46/******************************************************************************/
47#ifdef JEMALLOC_H_EXTERNS
48
49void	bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
50size_t	bitmap_info_ngroups(const bitmap_info_t *binfo);
51size_t	bitmap_size(size_t nbits);
52void	bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
53
54#endif /* JEMALLOC_H_EXTERNS */
55/******************************************************************************/
56#ifdef JEMALLOC_H_INLINES
57
58#ifndef JEMALLOC_ENABLE_INLINE
59bool	bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
60bool	bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
61void	bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
62size_t	bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
63void	bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
64#endif
65
66#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
67JEMALLOC_INLINE bool
68bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
69{
70	unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
71	bitmap_t rg = bitmap[rgoff];
72	/* The bitmap is full iff the root group is 0. */
73	return (rg == 0);
74}
75
76JEMALLOC_INLINE bool
77bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
78{
79	size_t goff;
80	bitmap_t g;
81
82	assert(bit < binfo->nbits);
83	goff = bit >> LG_BITMAP_GROUP_NBITS;
84	g = bitmap[goff];
85	return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))));
86}
87
88JEMALLOC_INLINE void
89bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
90{
91	size_t goff;
92	bitmap_t *gp;
93	bitmap_t g;
94
95	assert(bit < binfo->nbits);
96	assert(bitmap_get(bitmap, binfo, bit) == false);
97	goff = bit >> LG_BITMAP_GROUP_NBITS;
98	gp = &bitmap[goff];
99	g = *gp;
100	assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
101	g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
102	*gp = g;
103	assert(bitmap_get(bitmap, binfo, bit));
104	/* Propagate group state transitions up the tree. */
105	if (g == 0) {
106		unsigned i;
107		for (i = 1; i < binfo->nlevels; i++) {
108			bit = goff;
109			goff = bit >> LG_BITMAP_GROUP_NBITS;
110			gp = &bitmap[binfo->levels[i].group_offset + goff];
111			g = *gp;
112			assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
113			g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
114			*gp = g;
115			if (g != 0)
116				break;
117		}
118	}
119}
120
121/* sfu: set first unset. */
122JEMALLOC_INLINE size_t
123bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
124{
125	size_t bit;
126	bitmap_t g;
127	unsigned i;
128
129	assert(bitmap_full(bitmap, binfo) == false);
130
131	i = binfo->nlevels - 1;
132	g = bitmap[binfo->levels[i].group_offset];
133	bit = ffsl(g) - 1;
134	while (i > 0) {
135		i--;
136		g = bitmap[binfo->levels[i].group_offset + bit];
137		bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffsl(g) - 1);
138	}
139
140	bitmap_set(bitmap, binfo, bit);
141	return (bit);
142}
143
144JEMALLOC_INLINE void
145bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
146{
147	size_t goff;
148	bitmap_t *gp;
149	bitmap_t g;
150	bool propagate;
151
152	assert(bit < binfo->nbits);
153	assert(bitmap_get(bitmap, binfo, bit));
154	goff = bit >> LG_BITMAP_GROUP_NBITS;
155	gp = &bitmap[goff];
156	g = *gp;
157	propagate = (g == 0);
158	assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
159	g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
160	*gp = g;
161	assert(bitmap_get(bitmap, binfo, bit) == false);
162	/* Propagate group state transitions up the tree. */
163	if (propagate) {
164		unsigned i;
165		for (i = 1; i < binfo->nlevels; i++) {
166			bit = goff;
167			goff = bit >> LG_BITMAP_GROUP_NBITS;
168			gp = &bitmap[binfo->levels[i].group_offset + goff];
169			g = *gp;
170			propagate = (g == 0);
171			assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))
172			    == 0);
173			g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
174			*gp = g;
175			if (propagate == false)
176				break;
177		}
178	}
179}
180
181#endif
182
183#endif /* JEMALLOC_H_INLINES */
184/******************************************************************************/
185