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 18e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris/* 19e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris * Do some analysis on how big the bitmap is before we use a tree. For a brute 20e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris * force linear search, if we would have to call ffsl more than 2^3 times, use a 21e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris * tree instead. 22e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris */ 23e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3 24e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris# define USE_TREE 25e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif 26e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 2783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* Number of groups required to store a given number of bits. */ 2883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_BITS2GROUPS(nbits) \ 2983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS) 3083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 3183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* 3283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Number of groups required at a particular level for a given number of bits. 3383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */ 3483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_L0(nbits) \ 3583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_BITS2GROUPS(nbits) 3683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_L1(nbits) \ 3783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits)) 3883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_L2(nbits) \ 3983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits)))) 4083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_L3(nbits) \ 4183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS( \ 4283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_BITS2GROUPS((nbits))))) 4383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 4483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* 4583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Assuming the number of levels, number of groups required for a given number 4683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * of bits. 4783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */ 4883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_1_LEVEL(nbits) \ 4983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris BITMAP_GROUPS_L0(nbits) 5083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_2_LEVEL(nbits) \ 5183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits)) 5283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_3_LEVEL(nbits) \ 5383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits)) 5483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#define BITMAP_GROUPS_4_LEVEL(nbits) \ 5583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits)) 5683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 5783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris/* 5883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris * Maximum number of groups required to support LG_BITMAP_MAXBITS. 5983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris */ 60e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 61e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 6283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS 6383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris# define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS) 6483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2 6583e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris# define BITMAP_GROUPS_MAX BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS) 6683e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3 6783e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris# define BITMAP_GROUPS_MAX BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS) 6883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4 6983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris# define BITMAP_GROUPS_MAX BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS) 7083e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#else 7183e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris# error "Unsupported bitmap size" 7283e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris#endif 7383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris 7484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Maximum number of levels possible. */ 7584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define BITMAP_MAX_LEVELS \ 7684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 7784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 7884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 79e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#else /* USE_TREE */ 80e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 81e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS) 82e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 83e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif /* USE_TREE */ 84e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 8584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_TYPES */ 8684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 8784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_STRUCTS 8884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 8984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_level_s { 9084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Offset of this level's groups within the array of groups. */ 9184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t group_offset; 9284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}; 9384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 9484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_info_s { 9584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Logical number of bits in bitmap (stored at bottom level). */ 9684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t nbits; 9784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 98e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 9984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Number of levels necessary for nbits. */ 10084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned nlevels; 10184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 10284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* 10384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Only the first (nlevels+1) elements are used, and levels are ordered 10484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * bottom to top (e.g. the bottom level is stored in levels[0]). 10584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans */ 10684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 107e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#else /* USE_TREE */ 108e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris /* Number of groups necessary for nbits. */ 109e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris size_t ngroups; 110e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif /* USE_TREE */ 11184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}; 11284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 11384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_STRUCTS */ 11484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 11584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_EXTERNS 11684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 11784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 11884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 119e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferrissize_t bitmap_size(const bitmap_info_t *binfo); 12084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 12184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_EXTERNS */ 12284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 12384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_INLINES 12484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 12584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifndef JEMALLOC_ENABLE_INLINE 12684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 12784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 12884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 12984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 13084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 13184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif 13284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 13384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 13484c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool 13584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 13684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 137e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 138e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 13984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t rg = bitmap[rgoff]; 14084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* The bitmap is full iff the root group is 0. */ 14184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans return (rg == 0); 142e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#else 143e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris size_t i; 144e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris 145e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris for (i = 0; i < binfo->ngroups; i++) { 146e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris if (bitmap[i] != 0) 147e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris return (false); 148e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris } 149e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris return (true); 150e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif 15184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 15284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 15384c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool 15484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 15584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 15684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 15784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 15884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 15984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 16084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 16184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[goff]; 162e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))); 16384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 16484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 16584c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void 16684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 16784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 16884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 16984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t *gp; 17084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 17184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 17284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 17383e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris assert(!bitmap_get(bitmap, binfo, bit)); 17484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 17584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[goff]; 17684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 177e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 178e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 17984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 18084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit)); 181e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 18284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Propagate group state transitions up the tree. */ 18384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (g == 0) { 18484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 18584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans for (i = 1; i < binfo->nlevels; i++) { 18684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bit = goff; 18784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 18884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[binfo->levels[i].group_offset + goff]; 18984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 190e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); 191e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 19284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 19384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (g != 0) 19484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans break; 19584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 19684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 197e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif 19884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 19984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 20084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* sfu: set first unset. */ 20184c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE size_t 20284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 20384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 20484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t bit; 20584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 20684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 20784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 20883e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris assert(!bitmap_full(bitmap, binfo)); 20984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 210e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 21184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans i = binfo->nlevels - 1; 21284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[binfo->levels[i].group_offset]; 213e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris bit = ffs_lu(g) - 1; 21484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans while (i > 0) { 21584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans i--; 21684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[binfo->levels[i].group_offset + bit]; 217e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1); 21884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 219e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#else 220e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris i = 0; 221e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g = bitmap[0]; 222e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris while ((bit = ffs_lu(g)) == 0) { 223e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris i++; 224e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g = bitmap[i]; 225e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris } 226e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris bit = (bit - 1) + (i << 6); 227e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif 22884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_set(bitmap, binfo, bit); 22984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans return (bit); 23084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 23184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 23284c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void 23384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 23484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 23584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 23684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t *gp; 23784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 238e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris UNUSED bool propagate; 23984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 24084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 24184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit)); 24284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 24384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[goff]; 24484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 24584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans propagate = (g == 0); 246e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); 247e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 24884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 24983e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris assert(!bitmap_get(bitmap, binfo, bit)); 250e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#ifdef USE_TREE 25184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Propagate group state transitions up the tree. */ 25284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (propagate) { 25384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 25484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans for (i = 1; i < binfo->nlevels; i++) { 25584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bit = goff; 25684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 25784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[binfo->levels[i].group_offset + goff]; 25884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 25984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans propagate = (g == 0); 260e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) 26184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans == 0); 262e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); 26384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 26483e5767ee9a8c68150cca06ae0d27a13ba4fcaf8Christopher Ferris if (!propagate) 26584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans break; 26684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 26784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 268e42940346e47de63bfc47470c86c3c132ec2db8cChristopher Ferris#endif /* USE_TREE */ 26984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 27084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 27184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif 27284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 27384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_INLINES */ 27484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 275