bitmap.h

Go to the documentation of this file.

/******************************************************************************/
#ifdef JEMALLOC_H_TYPES
 
/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */
#define LG_BITMAP_MAXBITS   LG_RUN_MAXREGS
#define BITMAP_MAXBITS      (ZU(1) << LG_BITMAP_MAXBITS)
 
typedef struct bitmap_level_s bitmap_level_t;
typedef struct bitmap_info_s bitmap_info_t;
typedef unsigned long bitmap_t;
#define LG_SIZEOF_BITMAP    LG_SIZEOF_LONG
 
/* Number of bits per group. */
#define LG_BITMAP_GROUP_NBITS       (LG_SIZEOF_BITMAP + 3)
#define BITMAP_GROUP_NBITS      (ZU(1) << LG_BITMAP_GROUP_NBITS)
#define BITMAP_GROUP_NBITS_MASK     (BITMAP_GROUP_NBITS-1)
 
/*
 * Do some analysis on how big the bitmap is before we use a tree.  For a brute
 * force linear search, if we would have to call ffs_lu() more than 2^3 times,
 * use a tree instead.
 */
#if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3
#  define USE_TREE
#endif
 
/* Number of groups required to store a given number of bits. */
#define BITMAP_BITS2GROUPS(nbits)                   \
    ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
 
/*
 * Number of groups required at a particular level for a given number of bits.
 */
#define BITMAP_GROUPS_L0(nbits)                     \
    BITMAP_BITS2GROUPS(nbits)
#define BITMAP_GROUPS_L1(nbits)                     \
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(nbits))
#define BITMAP_GROUPS_L2(nbits)                     \
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))
#define BITMAP_GROUPS_L3(nbits)                     \
    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(       \
    BITMAP_BITS2GROUPS((nbits)))))
 
/*
 * Assuming the number of levels, number of groups required for a given number
 * of bits.
 */
#define BITMAP_GROUPS_1_LEVEL(nbits)                    \
    BITMAP_GROUPS_L0(nbits)
#define BITMAP_GROUPS_2_LEVEL(nbits)                    \
    (BITMAP_GROUPS_1_LEVEL(nbits) + BITMAP_GROUPS_L1(nbits))
#define BITMAP_GROUPS_3_LEVEL(nbits)                    \
    (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
#define BITMAP_GROUPS_4_LEVEL(nbits)                    \
    (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
 
/*
 * Maximum number of groups required to support LG_BITMAP_MAXBITS.
 */
#ifdef USE_TREE
 
#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
#  define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
#  define BITMAP_GROUPS_MAX BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
#  define BITMAP_GROUPS_MAX BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
#  define BITMAP_GROUPS_MAX BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
#else
#  error "Unsupported bitmap size"
#endif
 
/* Maximum number of levels possible. */
#define BITMAP_MAX_LEVELS                       \
    (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)              \
    + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
 
#else /* USE_TREE */
 
#define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS)
 
#endif /* USE_TREE */
 
#endif /* JEMALLOC_H_TYPES */
/******************************************************************************/
#ifdef JEMALLOC_H_STRUCTS
 
struct bitmap_level_s {
    /* Offset of this level's groups within the array of groups. */
    size_t group_offset;
};
 
struct bitmap_info_s {
    /* Logical number of bits in bitmap (stored at bottom level). */
    size_t nbits;
 
#ifdef USE_TREE
    /* Number of levels necessary for nbits. */
    unsigned nlevels;
 
    /*
     * Only the first (nlevels+1) elements are used, and levels are ordered
     * bottom to top (e.g. the bottom level is stored in levels[0]).
     */
    bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
#else /* USE_TREE */
    /* Number of groups necessary for nbits. */
    size_t ngroups;
#endif /* USE_TREE */
};
 
#endif /* JEMALLOC_H_STRUCTS */
/******************************************************************************/
#ifdef JEMALLOC_H_EXTERNS
 
void    bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
void    bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo);
size_t  bitmap_size(const bitmap_info_t *binfo);
 
#endif /* JEMALLOC_H_EXTERNS */
/******************************************************************************/
#ifdef JEMALLOC_H_INLINES
 
#ifndef JEMALLOC_ENABLE_INLINE
bool    bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
bool    bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
void    bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
size_t  bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
void    bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
#endif
 
#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
JEMALLOC_INLINE bool
bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
{
#ifdef USE_TREE
    size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
    bitmap_t rg = bitmap[rgoff];
    /* The bitmap is full iff the root group is 0. */
    return (rg == 0);
#else
    size_t i;
 
    for (i = 0; i < binfo->ngroups; i++) {
        if (bitmap[i] != 0)
            return (false);
    }
    return (true);
#endif
}
 
JEMALLOC_INLINE bool
bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
{
    size_t goff;
    bitmap_t g;
    if (unlikely(bit > binfo->nbits))
        return (false);
 
    goff = bit >> LG_BITMAP_GROUP_NBITS;
    g = bitmap[goff];
    return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))));
}
 
JEMALLOC_INLINE void
bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
{
    size_t goff;
    bitmap_t *gp;
    bitmap_t g;
 
    assert(bit < binfo->nbits);
    assert(!bitmap_get(bitmap, binfo, bit));
    goff = bit >> LG_BITMAP_GROUP_NBITS;
    gp = &bitmap[goff];
    g = *gp;
    assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
    g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
    *gp = g;
    assert(bitmap_get(bitmap, binfo, bit));
#ifdef USE_TREE
    /* Propagate group state transitions up the tree. */
    if (g == 0) {
        unsigned i;
        for (i = 1; i < binfo->nlevels; i++) {
            bit = goff;
            goff = bit >> LG_BITMAP_GROUP_NBITS;
            gp = &bitmap[binfo->levels[i].group_offset + goff];
            g = *gp;
            assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
            g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
            *gp = g;
            if (g != 0)
                break;
        }
    }
#endif
}
 
/* sfu: set first unset. */
JEMALLOC_INLINE size_t
bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
{
    size_t bit;
    bitmap_t g;
    unsigned i;
 
    assert(!bitmap_full(bitmap, binfo));
 
#ifdef USE_TREE
    i = binfo->nlevels - 1;
    g = bitmap[binfo->levels[i].group_offset];
    bit = ffs_lu(g) - 1;
    while (i > 0) {
        i--;
        g = bitmap[binfo->levels[i].group_offset + bit];
        bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1);
    }
#else
    i = 0;
    g = bitmap[0];
    while ((bit = ffs_lu(g)) == 0) {
        i++;
        g = bitmap[i];
    }
    bit = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1);
#endif
    bitmap_set(bitmap, binfo, bit);
    return (bit);
}
 
JEMALLOC_INLINE void
bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
{
    size_t goff;
    bitmap_t *gp;
    bitmap_t g;
    RZ_UNUSED bool propagate;
 
    assert(bit < binfo->nbits);
    assert(bitmap_get(bitmap, binfo, bit));
    goff = bit >> LG_BITMAP_GROUP_NBITS;
    gp = &bitmap[goff];
    g = *gp;
    propagate = (g == 0);
    assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
    g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
    *gp = g;
    assert(!bitmap_get(bitmap, binfo, bit));
#ifdef USE_TREE
    /* Propagate group state transitions up the tree. */
    if (propagate) {
        unsigned i;
        for (i = 1; i < binfo->nlevels; i++) {
            bit = goff;
            goff = bit >> LG_BITMAP_GROUP_NBITS;
            gp = &bitmap[binfo->levels[i].group_offset + goff];
            g = *gp;
            propagate = (g == 0);
            assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))
                == 0);
            g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
            *gp = g;
            if (!propagate)
                break;
        }
    }
#endif /* USE_TREE */
}
 
#endif
 
#endif /* JEMALLOC_H_INLINES */
/******************************************************************************/