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 684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef struct bitmap_level_s bitmap_level_t; 884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef struct bitmap_info_s bitmap_info_t; 984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanstypedef unsigned long bitmap_t; 1084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 1184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 1284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Number of bits per group. */ 1384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 1484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) 1584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 1684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 1784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* Maximum number of levels possible. */ 1884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#define BITMAP_MAX_LEVELS \ 1984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 2084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 2184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 2284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_TYPES */ 2384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 2484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_STRUCTS 2584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 2684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_level_s { 2784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Offset of this level's groups within the array of groups. */ 2884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t group_offset; 2984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}; 3084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 3184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansstruct bitmap_info_s { 3284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Logical number of bits in bitmap (stored at bottom level). */ 3384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t nbits; 3484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 3584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Number of levels necessary for nbits. */ 3684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned nlevels; 3784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 3884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* 3984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Only the first (nlevels+1) elements are used, and levels are ordered 4084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * bottom to top (e.g. the bottom level is stored in levels[0]). 4184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans */ 4284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 4384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans}; 4484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 4584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_STRUCTS */ 4684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 4784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_EXTERNS 4884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 4984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 5084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t bitmap_info_ngroups(const bitmap_info_t *binfo); 5184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t bitmap_size(size_t nbits); 5284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 5384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 5484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_EXTERNS */ 5584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 5684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifdef JEMALLOC_H_INLINES 5784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 5884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#ifndef JEMALLOC_ENABLE_INLINE 5984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 6084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evanssize_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 6384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansvoid bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif 6584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 6684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 6784c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool 6884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 6984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 7084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 7184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t rg = bitmap[rgoff]; 7284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* The bitmap is full iff the root group is 0. */ 7384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans return (rg == 0); 7484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 7584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 7684c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE bool 7784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 7884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 7984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 8084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 8184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 8284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 8384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 8484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[goff]; 8584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))); 8684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 8784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 8884c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void 8984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 9084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 9184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 9284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t *gp; 9384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 9484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 9584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 9684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit) == false); 9784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 9884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[goff]; 9984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 10084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 10184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 10284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 10384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit)); 10484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Propagate group state transitions up the tree. */ 10584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (g == 0) { 10684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 10784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans for (i = 1; i < binfo->nlevels; i++) { 10884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bit = goff; 10984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 11084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[binfo->levels[i].group_offset + goff]; 11184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 11284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 11384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 11484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 11584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (g != 0) 11684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans break; 11784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 11884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 11984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 12084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 12184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/* sfu: set first unset. */ 12284c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE size_t 12384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 12484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 12584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t bit; 12684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 12784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 12884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 12984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_full(bitmap, binfo) == false); 13084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 13184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans i = binfo->nlevels - 1; 13284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[binfo->levels[i].group_offset]; 1332aa7fed9c983d8dcde7c0cacf1b024c966758b88Richard Diamond bit = jemalloc_ffsl(g) - 1; 13484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans while (i > 0) { 13584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans i--; 13684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = bitmap[binfo->levels[i].group_offset + bit]; 1372aa7fed9c983d8dcde7c0cacf1b024c966758b88Richard Diamond bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1); 13884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 13984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 14084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_set(bitmap, binfo, bit); 14184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans return (bit); 14284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 14384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 14484c8eefeffa246607790ad12e28b0f6a24ecc59dJason EvansJEMALLOC_INLINE void 14584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansbitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 14684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans{ 14784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans size_t goff; 14884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t *gp; 14984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_t g; 15084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bool propagate; 15184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 15284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bit < binfo->nbits); 15384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit)); 15484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 15584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[goff]; 15684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 15784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans propagate = (g == 0); 15884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); 15984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 16084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 16184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert(bitmap_get(bitmap, binfo, bit) == false); 16284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Propagate group state transitions up the tree. */ 16384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (propagate) { 16484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans unsigned i; 16584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans for (i = 1; i < binfo->nlevels; i++) { 16684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bit = goff; 16784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans goff = bit >> LG_BITMAP_GROUP_NBITS; 16884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans gp = &bitmap[binfo->levels[i].group_offset + goff]; 16984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g = *gp; 17084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans propagate = (g == 0); 17184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) 17284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans == 0); 17384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 17484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans *gp = g; 17584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans if (propagate == false) 17684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans break; 17784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 17884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans } 17984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans} 18084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 18184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif 18284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 18384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans#endif /* JEMALLOC_H_INLINES */ 18484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans/******************************************************************************/ 185