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
   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 = 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) + (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 /******************************************************************************/