contrib/jemalloc/include/jemalloc/internal/bitmap.h

   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 #define BITMAP_MAXBITS          (ZU(1) << LG_BITMAP_MAXBITS)
   7
   8 typedef struct bitmap_level_s bitmap_level_t;
   9 typedef struct bitmap_info_s bitmap_info_t;
  10 typedef unsigned long bitmap_t;
  11 #define LG_SIZEOF_BITMAP        LG_SIZEOF_LONG
  12
  13 /* Number of bits per group. */
  14 #define LG_BITMAP_GROUP_NBITS           (LG_SIZEOF_BITMAP + 3)
  15 #define BITMAP_GROUP_NBITS              (ZU(1) << LG_BITMAP_GROUP_NBITS)
  16 #define BITMAP_GROUP_NBITS_MASK         (BITMAP_GROUP_NBITS-1)
  17
  18 /*
  19  * Do some analysis on how big the bitmap is before we use a tree.  For a brute
  20  * force linear search, if we would have to call ffsl more than 2^3 times, use a
  21  * tree instead.
  22  */
  23 #if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3
  24 #  define USE_TREE
  25 #endif
  26
  27 /* Number of groups required to store a given number of bits. */
  28 #define BITMAP_BITS2GROUPS(nbits)                                       \
  29     ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
  30
  31 /*
  32  * Number of groups required at a particular level for a given number of bits.
  33  */
  34 #define BITMAP_GROUPS_L0(nbits)                                         \
  35     BITMAP_BITS2GROUPS(nbits)
  36 #define BITMAP_GROUPS_L1(nbits)                                         \
  37     BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits))
  38 #define BITMAP_GROUPS_L2(nbits)                                         \
  39     BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))
  40 #define BITMAP_GROUPS_L3(nbits)                                         \
  41     BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(           \
  42         BITMAP_BITS2GROUPS((nbits)))))
  43
  44 /*
  45  * Assuming the number of levels, number of groups required for a given number
  46  * of bits.
  47  */
  48 #define BITMAP_GROUPS_1_LEVEL(nbits)                                    \
  49     BITMAP_GROUPS_L0(nbits)
  50 #define BITMAP_GROUPS_2_LEVEL(nbits)                                    \
  51     (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits))
  52 #define BITMAP_GROUPS_3_LEVEL(nbits)                                    \
  53     (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
  54 #define BITMAP_GROUPS_4_LEVEL(nbits)                                    \
  55     (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
  56
  57 /*
  58  * Maximum number of groups required to support LG_BITMAP_MAXBITS.
  59  */
  60 #ifdef USE_TREE
  61
  62 #if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
  63 #  define BITMAP_GROUPS_MAX     BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
  64 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
  65 #  define BITMAP_GROUPS_MAX     BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
  66 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
  67 #  define BITMAP_GROUPS_MAX     BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
  68 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
  69 #  define BITMAP_GROUPS_MAX     BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
  70 #else
  71 #  error "Unsupported bitmap size"
  72 #endif
  73
  74 /* Maximum number of levels possible. */
  75 #define BITMAP_MAX_LEVELS                                               \
  76     (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)                              \
  77     + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
  78
  79 #else /* USE_TREE */
  80
  81 #define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS)
  82
  83 #endif /* USE_TREE */
  84
  85 #endif /* JEMALLOC_H_TYPES */
  86 /******************************************************************************/
  87 #ifdef JEMALLOC_H_STRUCTS
  88
  89 struct bitmap_level_s {
  90         /* Offset of this level's groups within the array of groups. */
  91         size_t group_offset;
  92 };
  93
  94 struct bitmap_info_s {
  95         /* Logical number of bits in bitmap (stored at bottom level). */
  96         size_t nbits;
  97
  98 #ifdef USE_TREE
  99         /* Number of levels necessary for nbits. */
 100         unsigned nlevels;
 101
 102         /*
 103          * Only the first (nlevels+1) elements are used, and levels are ordered
 104          * bottom to top (e.g. the bottom level is stored in levels[0]).
 105          */
 106         bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
 107 #else /* USE_TREE */
 108         /* Number of groups necessary for nbits. */
 109         size_t ngroups;
 110 #endif /* USE_TREE */
 111 };
 112
 113 #endif /* JEMALLOC_H_STRUCTS */
 114 /******************************************************************************/
 115 #ifdef JEMALLOC_H_EXTERNS
 116
 117 void    bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
 118 void    bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
 119 size_t  bitmap_size(const bitmap_info_t *binfo);
 120
 121 #endif /* JEMALLOC_H_EXTERNS */
 122 /******************************************************************************/
 123 #ifdef JEMALLOC_H_INLINES
 124
 125 #ifndef JEMALLOC_ENABLE_INLINE
 126 bool    bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
 127 bool    bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 128 void    bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 129 size_t  bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
 130 void    bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 131 #endif
 132
 133 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
 134 JEMALLOC_INLINE bool
 135 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
 136 {
 137 #ifdef USE_TREE
 138         size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
 139         bitmap_t rg = bitmap[rgoff];
 140         /* The bitmap is full iff the root group is 0. */
 141         return (rg == 0);
 142 #else
 143         size_t i;
 144
 145         for (i = 0; i < binfo->ngroups; i++) {
 146                 if (bitmap[i] != 0)
 147                         return (false);
 148         }
 149         return (true);
 150 #endif
 151 }
 152
 153 JEMALLOC_INLINE bool
 154 bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 155 {
 156         size_t goff;
 157         bitmap_t g;
 158
 159         assert(bit < binfo->nbits);
 160         goff = bit >> LG_BITMAP_GROUP_NBITS;
 161         g = bitmap[goff];
 162         return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))));
 163 }
 164
 165 JEMALLOC_INLINE void
 166 bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 167 {
 168         size_t goff;
 169         bitmap_t *gp;
 170         bitmap_t g;
 171
 172         assert(bit < binfo->nbits);
 173         assert(!bitmap_get(bitmap, binfo, bit));
 174         goff = bit >> LG_BITMAP_GROUP_NBITS;
 175         gp = &bitmap[goff];
 176         g = *gp;
 177         assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
 178         g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 179         *gp = g;
 180         assert(bitmap_get(bitmap, binfo, bit));
 181 #ifdef USE_TREE
 182         /* Propagate group state transitions up the tree. */
 183         if (g == 0) {
 184                 unsigned i;
 185                 for (i = 1; i < binfo->nlevels; i++) {
 186                         bit = goff;
 187                         goff = bit >> LG_BITMAP_GROUP_NBITS;
 188                         gp = &bitmap[binfo->levels[i].group_offset + goff];
 189                         g = *gp;
 190                         assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
 191                         g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 192                         *gp = g;
 193                         if (g != 0)
 194                                 break;
 195                 }
 196         }
 197 #endif
 198 }
 199
 200 /* sfu: set first unset. */
 201 JEMALLOC_INLINE size_t
 202 bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
 203 {
 204         size_t bit;
 205         bitmap_t g;
 206         unsigned i;
 207
 208         assert(!bitmap_full(bitmap, binfo));
 209
 210 #ifdef USE_TREE
 211         i = binfo->nlevels - 1;
 212         g = bitmap[binfo->levels[i].group_offset];
 213         bit = ffs_lu(g) - 1;
 214         while (i > 0) {
 215                 i--;
 216                 g = bitmap[binfo->levels[i].group_offset + bit];
 217                 bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1);
 218         }
 219 #else
 220         i = 0;
 221         g = bitmap[0];
 222         while ((bit = ffs_lu(g)) == 0) {
 223                 i++;
 224                 g = bitmap[i];
 225         }
 226         bit = (bit - 1) + (i << 6);
 227 #endif
 228         bitmap_set(bitmap, binfo, bit);
 229         return (bit);
 230 }
 231
 232 JEMALLOC_INLINE void
 233 bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 234 {
 235         size_t goff;
 236         bitmap_t *gp;
 237         bitmap_t g;
 238         UNUSED bool propagate;
 239
 240         assert(bit < binfo->nbits);
 241         assert(bitmap_get(bitmap, binfo, bit));
 242         goff = bit >> LG_BITMAP_GROUP_NBITS;
 243         gp = &bitmap[goff];
 244         g = *gp;
 245         propagate = (g == 0);
 246         assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
 247         g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 248         *gp = g;
 249         assert(!bitmap_get(bitmap, binfo, bit));
 250 #ifdef USE_TREE
 251         /* Propagate group state transitions up the tree. */
 252         if (propagate) {
 253                 unsigned i;
 254                 for (i = 1; i < binfo->nlevels; i++) {
 255                         bit = goff;
 256                         goff = bit >> LG_BITMAP_GROUP_NBITS;
 257                         gp = &bitmap[binfo->levels[i].group_offset + goff];
 258                         g = *gp;
 259                         propagate = (g == 0);
 260                         assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))
 261                             == 0);
 262                         g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 263                         *gp = g;
 264                         if (!propagate)
 265                                 break;
 266                 }
 267         }
 268 #endif /* USE_TREE */
 269 }
 270
 271 #endif
 272
 273 #endif /* JEMALLOC_H_INLINES */
 274 /******************************************************************************/