bitmap.h revision 2aa7fed9c983d8dcde7c0cacf1b024c966758b88
147702147608084fec16a50640da54b412c737b9cGriff Hazen/******************************************************************************/ 247702147608084fec16a50640da54b412c737b9cGriff Hazen#ifdef JEMALLOC_H_TYPES 347702147608084fec16a50640da54b412c737b9cGriff Hazen 447702147608084fec16a50640da54b412c737b9cGriff Hazen/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */ 547702147608084fec16a50640da54b412c737b9cGriff Hazen#define LG_BITMAP_MAXBITS LG_RUN_MAXREGS 647702147608084fec16a50640da54b412c737b9cGriff Hazen 747702147608084fec16a50640da54b412c737b9cGriff Hazentypedef struct bitmap_level_s bitmap_level_t; 847702147608084fec16a50640da54b412c737b9cGriff Hazentypedef struct bitmap_info_s bitmap_info_t; 947702147608084fec16a50640da54b412c737b9cGriff Hazentypedef unsigned long bitmap_t; 1047702147608084fec16a50640da54b412c737b9cGriff Hazen#define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 1147702147608084fec16a50640da54b412c737b9cGriff Hazen 1247702147608084fec16a50640da54b412c737b9cGriff Hazen/* Number of bits per group. */ 1347702147608084fec16a50640da54b412c737b9cGriff Hazen#define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 1447702147608084fec16a50640da54b412c737b9cGriff Hazen#define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) 1547702147608084fec16a50640da54b412c737b9cGriff Hazen#define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 1647702147608084fec16a50640da54b412c737b9cGriff Hazen 1747702147608084fec16a50640da54b412c737b9cGriff Hazen/* Maximum number of levels possible. */ 1847702147608084fec16a50640da54b412c737b9cGriff Hazen#define BITMAP_MAX_LEVELS \ 1947702147608084fec16a50640da54b412c737b9cGriff Hazen (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 2047702147608084fec16a50640da54b412c737b9cGriff Hazen + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 2147702147608084fec16a50640da54b412c737b9cGriff Hazen 2247702147608084fec16a50640da54b412c737b9cGriff Hazen#endif /* JEMALLOC_H_TYPES */ 2347702147608084fec16a50640da54b412c737b9cGriff Hazen/******************************************************************************/ 24300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen#ifdef JEMALLOC_H_STRUCTS 2547702147608084fec16a50640da54b412c737b9cGriff Hazen 2647702147608084fec16a50640da54b412c737b9cGriff Hazenstruct bitmap_level_s { 27334514fd61bd192cee3475b3ba44adb4f54a1f89Chris Wren /* Offset of this level's groups within the array of groups. */ 28300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen size_t group_offset; 29334514fd61bd192cee3475b3ba44adb4f54a1f89Chris Wren}; 3047702147608084fec16a50640da54b412c737b9cGriff Hazen 3147702147608084fec16a50640da54b412c737b9cGriff Hazenstruct bitmap_info_s { 3247702147608084fec16a50640da54b412c737b9cGriff Hazen /* Logical number of bits in bitmap (stored at bottom level). */ 3347702147608084fec16a50640da54b412c737b9cGriff Hazen size_t nbits; 3447702147608084fec16a50640da54b412c737b9cGriff Hazen 35300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen /* Number of levels necessary for nbits. */ 3647702147608084fec16a50640da54b412c737b9cGriff Hazen unsigned nlevels; 3747702147608084fec16a50640da54b412c737b9cGriff Hazen 3847702147608084fec16a50640da54b412c737b9cGriff Hazen /* 3947702147608084fec16a50640da54b412c737b9cGriff Hazen * Only the first (nlevels+1) elements are used, and levels are ordered 4047702147608084fec16a50640da54b412c737b9cGriff Hazen * bottom to top (e.g. the bottom level is stored in levels[0]). 4148d8878e34b0d9983166418378125b63faac9aabGriff Hazen */ 4247702147608084fec16a50640da54b412c737b9cGriff Hazen bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 43cd05a19c0775e69e93e4c93b0a48ab044b531d7aGriff Hazen}; 44cd05a19c0775e69e93e4c93b0a48ab044b531d7aGriff Hazen 4547702147608084fec16a50640da54b412c737b9cGriff Hazen#endif /* JEMALLOC_H_STRUCTS */ 4647702147608084fec16a50640da54b412c737b9cGriff Hazen/******************************************************************************/ 4748d8878e34b0d9983166418378125b63faac9aabGriff Hazen#ifdef JEMALLOC_H_EXTERNS 4847702147608084fec16a50640da54b412c737b9cGriff Hazen 4947702147608084fec16a50640da54b412c737b9cGriff Hazenvoid bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 5047702147608084fec16a50640da54b412c737b9cGriff Hazensize_t bitmap_info_ngroups(const bitmap_info_t *binfo); 5147702147608084fec16a50640da54b412c737b9cGriff Hazensize_t bitmap_size(size_t nbits); 5247702147608084fec16a50640da54b412c737b9cGriff Hazenvoid bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 5347702147608084fec16a50640da54b412c737b9cGriff Hazen 5447702147608084fec16a50640da54b412c737b9cGriff Hazen#endif /* JEMALLOC_H_EXTERNS */ 5547702147608084fec16a50640da54b412c737b9cGriff Hazen/******************************************************************************/ 5647702147608084fec16a50640da54b412c737b9cGriff Hazen#ifdef JEMALLOC_H_INLINES 5747702147608084fec16a50640da54b412c737b9cGriff Hazen 5847702147608084fec16a50640da54b412c737b9cGriff Hazen#ifndef JEMALLOC_ENABLE_INLINE 5947702147608084fec16a50640da54b412c737b9cGriff Hazenbool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 6047702147608084fec16a50640da54b412c737b9cGriff Hazenbool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6147702147608084fec16a50640da54b412c737b9cGriff Hazenvoid bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6247702147608084fec16a50640da54b412c737b9cGriff Hazensize_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 6347702147608084fec16a50640da54b412c737b9cGriff Hazenvoid bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 6447702147608084fec16a50640da54b412c737b9cGriff Hazen#endif 6547702147608084fec16a50640da54b412c737b9cGriff Hazen 6647702147608084fec16a50640da54b412c737b9cGriff Hazen#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 6747702147608084fec16a50640da54b412c737b9cGriff HazenJEMALLOC_INLINE bool 6847702147608084fec16a50640da54b412c737b9cGriff Hazenbitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 6947702147608084fec16a50640da54b412c737b9cGriff Hazen{ 7043c5718722bab1f836b7c94f2ec0bc19e653037cGriff Hazen unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 71ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bitmap_t rg = bitmap[rgoff]; 72ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen /* The bitmap is full iff the root group is 0. */ 73ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen return (rg == 0); 74ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen} 75ef9064724c669d8f72a8682b6e7b122008921d43Chris Wren 76cd05a19c0775e69e93e4c93b0a48ab044b531d7aGriff HazenJEMALLOC_INLINE bool 77ef9064724c669d8f72a8682b6e7b122008921d43Chris Wrenbitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 78ef9064724c669d8f72a8682b6e7b122008921d43Chris Wren{ 7947702147608084fec16a50640da54b412c737b9cGriff Hazen size_t goff; 80ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bitmap_t g; 81ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen 82ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen assert(bit < binfo->nbits); 83ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen goff = bit >> LG_BITMAP_GROUP_NBITS; 84ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen g = bitmap[goff]; 85ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))); 86ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen} 87ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen 88ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff HazenJEMALLOC_INLINE void 89ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazenbitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 90ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen{ 91ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen size_t goff; 9247702147608084fec16a50640da54b412c737b9cGriff Hazen bitmap_t *gp; 9347702147608084fec16a50640da54b412c737b9cGriff Hazen bitmap_t g; 9447702147608084fec16a50640da54b412c737b9cGriff Hazen 9547702147608084fec16a50640da54b412c737b9cGriff Hazen assert(bit < binfo->nbits); 96ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen assert(bitmap_get(bitmap, binfo, bit) == false); 97ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen goff = bit >> LG_BITMAP_GROUP_NBITS; 9847702147608084fec16a50640da54b412c737b9cGriff Hazen gp = &bitmap[goff]; 9947702147608084fec16a50640da54b412c737b9cGriff Hazen g = *gp; 10047702147608084fec16a50640da54b412c737b9cGriff Hazen assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 10147702147608084fec16a50640da54b412c737b9cGriff Hazen g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 10247702147608084fec16a50640da54b412c737b9cGriff Hazen *gp = g; 10347702147608084fec16a50640da54b412c737b9cGriff Hazen assert(bitmap_get(bitmap, binfo, bit)); 10447702147608084fec16a50640da54b412c737b9cGriff Hazen /* Propagate group state transitions up the tree. */ 10547702147608084fec16a50640da54b412c737b9cGriff Hazen if (g == 0) { 106300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen unsigned i; 107300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen for (i = 1; i < binfo->nlevels; i++) { 108300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen bit = goff; 109300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen goff = bit >> LG_BITMAP_GROUP_NBITS; 110ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen gp = &bitmap[binfo->levels[i].group_offset + goff]; 111300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen g = *gp; 112300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 113ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 11447702147608084fec16a50640da54b412c737b9cGriff Hazen *gp = g; 11547702147608084fec16a50640da54b412c737b9cGriff Hazen if (g != 0) 11647702147608084fec16a50640da54b412c737b9cGriff Hazen break; 11747702147608084fec16a50640da54b412c737b9cGriff Hazen } 11847702147608084fec16a50640da54b412c737b9cGriff Hazen } 11947702147608084fec16a50640da54b412c737b9cGriff Hazen} 12047702147608084fec16a50640da54b412c737b9cGriff Hazen 12147702147608084fec16a50640da54b412c737b9cGriff Hazen/* sfu: set first unset. */ 122300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff HazenJEMALLOC_INLINE size_t 123300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazenbitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 124300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen{ 125300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen size_t bit; 126ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bitmap_t g; 127ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen unsigned i; 128ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen 129300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen assert(bitmap_full(bitmap, binfo) == false); 130300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen 131300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen i = binfo->nlevels - 1; 132300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen g = bitmap[binfo->levels[i].group_offset]; 133300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen bit = jemalloc_ffsl(g) - 1; 134300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen while (i > 0) { 135300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen i--; 136ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen g = bitmap[binfo->levels[i].group_offset + bit]; 137ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1); 138300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen } 139300ad7c234a0ccfc41ae7fdbdcdd57faece2a8e0Griff Hazen 14047702147608084fec16a50640da54b412c737b9cGriff Hazen bitmap_set(bitmap, binfo, bit); 141ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen return (bit); 142ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen} 143ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen 144ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff HazenJEMALLOC_INLINE void 145ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazenbitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 146ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen{ 147ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen size_t goff; 148ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bitmap_t *gp; 149ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bitmap_t g; 150ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen bool propagate; 151ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen 152ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen assert(bit < binfo->nbits); 153ce16e4276c2f61109a23b3f6707cfcd87b07c735Griff Hazen assert(bitmap_get(bitmap, binfo, bit)); 15447702147608084fec16a50640da54b412c737b9cGriff Hazen goff = bit >> LG_BITMAP_GROUP_NBITS; 15547702147608084fec16a50640da54b412c737b9cGriff Hazen 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