184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/
284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_TYPES
384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */
547e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans#define	LG_BITMAP_MAXBITS	LG_RUN_MAXREGS
683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_MAXBITS		(ZU(1) << LG_BITMAP_MAXBITS)
784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef struct bitmap_level_s bitmap_level_t;
984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef struct bitmap_info_s bitmap_info_t;
1084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef unsigned long bitmap_t;
1184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define	LG_SIZEOF_BITMAP	LG_SIZEOF_LONG
1284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
1384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Number of bits per group. */
1484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define	LG_BITMAP_GROUP_NBITS		(LG_SIZEOF_BITMAP + 3)
1584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define	BITMAP_GROUP_NBITS		(ZU(1) << LG_BITMAP_GROUP_NBITS)
1684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define	BITMAP_GROUP_NBITS_MASK		(BITMAP_GROUP_NBITS-1)
1784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
1883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* Number of groups required to store a given number of bits. */
1983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_BITS2GROUPS(nbits)					\
2083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
2183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris
2283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/*
2383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Number of groups required at a particular level for a given number of bits.
2483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */
2583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_L0(nbits)						\
2683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    BITMAP_BITS2GROUPS(nbits)
2783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_L1(nbits)						\
2883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits))
2983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_L2(nbits)						\
3083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))
3183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_L3(nbits)						\
3283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(		\
3383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris	BITMAP_BITS2GROUPS((nbits)))))
3483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris
3583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/*
3683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Assuming the number of levels, number of groups required for a given number
3783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * of bits.
3883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */
3983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_1_LEVEL(nbits)					\
4083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    BITMAP_GROUPS_L0(nbits)
4183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_2_LEVEL(nbits)					\
4283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits))
4383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_3_LEVEL(nbits)					\
4483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
4583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define	BITMAP_GROUPS_4_LEVEL(nbits)					\
4683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris    (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
4783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris
4883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/*
4983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Maximum number of groups required to support LG_BITMAP_MAXBITS.
5083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */
5183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
5283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
5383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
5483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
5583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
5683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
5783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
5883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
5983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#else
6083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#  error "Unsupported bitmap size"
6183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#endif
6283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris
6384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Maximum number of levels possible. */
6484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define	BITMAP_MAX_LEVELS						\
6584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans    (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)				\
6684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans    + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
6784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
6884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_TYPES */
6984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/
7084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_STRUCTS
7184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
7284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_level_s {
7384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* Offset of this level's groups within the array of groups. */
7484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t group_offset;
7584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans};
7684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
7784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_info_s {
7884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* Logical number of bits in bitmap (stored at bottom level). */
7984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t nbits;
8084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
8184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* Number of levels necessary for nbits. */
8284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	unsigned nlevels;
8384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
8484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/*
8584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	 * Only the first (nlevels+1) elements are used, and levels are ordered
8684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	 * bottom to top (e.g. the bottom level is stored in levels[0]).
8784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	 */
8884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
8984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans};
9084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
9184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_STRUCTS */
9284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/
9384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_EXTERNS
9484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
9584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid	bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
9684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t	bitmap_info_ngroups(const bitmap_info_t *binfo);
9784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t	bitmap_size(size_t nbits);
9884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid	bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
9984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
10084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_EXTERNS */
10184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/
10284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_INLINES
10384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
10484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifndef JEMALLOC_ENABLE_INLINE
10584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool	bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
10684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool	bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
10784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid	bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
10884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t	bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
10984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid	bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
11084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif
11184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
11284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
11384c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool
11484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
11584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{
11684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
11784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t rg = bitmap[rgoff];
11884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* The bitmap is full iff the root group is 0. */
11984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	return (rg == 0);
12084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}
12184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
12284c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool
12384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
12484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{
12584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t goff;
12684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t g;
12784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
12884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(bit < binfo->nbits);
12984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	goff = bit >> LG_BITMAP_GROUP_NBITS;
13084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g = bitmap[goff];
13184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))));
13284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}
13384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
13484c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void
13584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
13684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{
13784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t goff;
13884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t *gp;
13984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t g;
14084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
14184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(bit < binfo->nbits);
14283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris	assert(!bitmap_get(bitmap, binfo, bit));
14384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	goff = bit >> LG_BITMAP_GROUP_NBITS;
14484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	gp = &bitmap[goff];
14584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g = *gp;
14684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
14784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
14884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	*gp = g;
14984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(bitmap_get(bitmap, binfo, bit));
15084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* Propagate group state transitions up the tree. */
15184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	if (g == 0) {
15284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		unsigned i;
15384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		for (i = 1; i < binfo->nlevels; i++) {
15484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			bit = goff;
15584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			goff = bit >> LG_BITMAP_GROUP_NBITS;
15684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			gp = &bitmap[binfo->levels[i].group_offset + goff];
15784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			g = *gp;
15884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
15984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
16084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			*gp = g;
16184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			if (g != 0)
16284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans				break;
16384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		}
16484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	}
16584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}
16684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
16784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* sfu: set first unset. */
16884c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE size_t
16984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
17084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{
17184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t bit;
17284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t g;
17384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	unsigned i;
17484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
17583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris	assert(!bitmap_full(bitmap, binfo));
17684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
17784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	i = binfo->nlevels - 1;
17884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g = bitmap[binfo->levels[i].group_offset];
1799c3a10fdf6baa5ddb042b6adbef1ff1b3c613ce3Richard Diamond	bit = jemalloc_ffsl(g) - 1;
18084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	while (i > 0) {
18184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		i--;
18284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		g = bitmap[binfo->levels[i].group_offset + bit];
1839c3a10fdf6baa5ddb042b6adbef1ff1b3c613ce3Richard Diamond		bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1);
18484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	}
18584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
18684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_set(bitmap, binfo, bit);
18784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	return (bit);
18884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}
18984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
19084c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void
19184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
19284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{
19384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	size_t goff;
19484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t *gp;
19584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bitmap_t g;
19684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	bool propagate;
19784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
19884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(bit < binfo->nbits);
19984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert(bitmap_get(bitmap, binfo, bit));
20084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	goff = bit >> LG_BITMAP_GROUP_NBITS;
20184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	gp = &bitmap[goff];
20284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g = *gp;
20384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	propagate = (g == 0);
20484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
20584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
20684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	*gp = g;
20783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris	assert(!bitmap_get(bitmap, binfo, bit));
20884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	/* Propagate group state transitions up the tree. */
20984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	if (propagate) {
21084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		unsigned i;
21184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		for (i = 1; i < binfo->nlevels; i++) {
21284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			bit = goff;
21384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			goff = bit >> LG_BITMAP_GROUP_NBITS;
21484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			gp = &bitmap[binfo->levels[i].group_offset + goff];
21584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			g = *gp;
21684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			propagate = (g == 0);
21784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))
21884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			    == 0);
21984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
22084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans			*gp = g;
22183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris			if (!propagate)
22284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans				break;
22384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans		}
22484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans	}
22584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}
22684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
22784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif
22884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans
22984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_INLINES */
23084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/
231