1 /******************************************************************************/ 2 #ifdef JEMALLOC_H_TYPES 3 4 /* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */ 5 #define LG_BITMAP_MAXBITS LG_RUN_MAXREGS 6 7 typedef struct bitmap_level_s bitmap_level_t; 8 typedef struct bitmap_info_s bitmap_info_t; 9 typedef unsigned long bitmap_t; 10 #define LG_SIZEOF_BITMAP LG_SIZEOF_LONG 11 12 /* Number of bits per group. */ 13 #define LG_BITMAP_GROUP_NBITS (LG_SIZEOF_BITMAP + 3) 14 #define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) 15 #define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) 16 17 /* Maximum number of levels possible. */ 18 #define BITMAP_MAX_LEVELS \ 19 (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ 20 + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) 21 22 #endif /* JEMALLOC_H_TYPES */ 23 /******************************************************************************/ 24 #ifdef JEMALLOC_H_STRUCTS 25 26 struct bitmap_level_s { 27 /* Offset of this level's groups within the array of groups. */ 28 size_t group_offset; 29 }; 30 31 struct bitmap_info_s { 32 /* Logical number of bits in bitmap (stored at bottom level). */ 33 size_t nbits; 34 35 /* Number of levels necessary for nbits. */ 36 unsigned nlevels; 37 38 /* 39 * Only the first (nlevels+1) elements are used, and levels are ordered 40 * bottom to top (e.g. the bottom level is stored in levels[0]). 41 */ 42 bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; 43 }; 44 45 #endif /* JEMALLOC_H_STRUCTS */ 46 /******************************************************************************/ 47 #ifdef JEMALLOC_H_EXTERNS 48 49 void bitmap_info_init(bitmap_info_t *binfo, size_t nbits); 50 size_t bitmap_info_ngroups(const bitmap_info_t *binfo); 51 size_t bitmap_size(size_t nbits); 52 void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); 53 54 #endif /* JEMALLOC_H_EXTERNS */ 55 /******************************************************************************/ 56 #ifdef JEMALLOC_H_INLINES 57 58 #ifndef JEMALLOC_ENABLE_INLINE 59 bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo); 60 bool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 61 void bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 62 size_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo); 63 void bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); 64 #endif 65 66 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_)) 67 JEMALLOC_INLINE bool 68 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) 69 { 70 unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1; 71 bitmap_t rg = bitmap[rgoff]; 72 /* The bitmap is full iff the root group is 0. */ 73 return (rg == 0); 74 } 75 76 JEMALLOC_INLINE bool 77 bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 78 { 79 size_t goff; 80 bitmap_t g; 81 82 assert(bit < binfo->nbits); 83 goff = bit >> LG_BITMAP_GROUP_NBITS; 84 g = bitmap[goff]; 85 return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))); 86 } 87 88 JEMALLOC_INLINE void 89 bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 90 { 91 size_t goff; 92 bitmap_t *gp; 93 bitmap_t g; 94 95 assert(bit < binfo->nbits); 96 assert(bitmap_get(bitmap, binfo, bit) == false); 97 goff = bit >> LG_BITMAP_GROUP_NBITS; 98 gp = &bitmap[goff]; 99 g = *gp; 100 assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 101 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 102 *gp = g; 103 assert(bitmap_get(bitmap, binfo, bit)); 104 /* Propagate group state transitions up the tree. */ 105 if (g == 0) { 106 unsigned i; 107 for (i = 1; i < binfo->nlevels; i++) { 108 bit = goff; 109 goff = bit >> LG_BITMAP_GROUP_NBITS; 110 gp = &bitmap[binfo->levels[i].group_offset + goff]; 111 g = *gp; 112 assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); 113 g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); 114 *gp = g; 115 if (g != 0) 116 break; 117 } 118 } 119 } 120 121 /* sfu: set first unset. */ 122 JEMALLOC_INLINE size_t 123 bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) 124 { 125 size_t bit; 126 bitmap_t g; 127 unsigned i; 128 129 assert(bitmap_full(bitmap, binfo) == false); 130 131 i = binfo->nlevels - 1; 132 g = bitmap[binfo->levels[i].group_offset]; 133 bit = jemalloc_ffsl(g) - 1; 134 while (i > 0) { 135 i--; 136 g = bitmap[binfo->levels[i].group_offset + bit]; 137 bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1); 138 } 139 140 bitmap_set(bitmap, binfo, bit); 141 return (bit); 142 } 143 144 JEMALLOC_INLINE void 145 bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) 146 { 147 size_t goff; 148 bitmap_t *gp; 149 bitmap_t g; 150 bool propagate; 151 152 assert(bit < binfo->nbits); 153 assert(bitmap_get(bitmap, binfo, bit)); 154 goff = bit >> LG_BITMAP_GROUP_NBITS; 155 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
