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