File Manager

003 File Manager

Current Path: /usr/src/contrib/jemalloc/include/jemalloc/internal

usr / src / contrib / jemalloc / include / jemalloc / internal /

📁 ..
📄 arena_externs.h(4.83 KB)
📄 arena_inlines_a.h(1.44 KB)
📄 arena_inlines_b.h(11.54 KB)
📄 arena_stats.h(7.92 KB)
📄 arena_structs_a.h(293 B)
📄 arena_structs_b.h(6.63 KB)
📄 arena_types.h(1.67 KB)
📄 assert.h(1.3 KB)
📄 atomic.h(2.66 KB)
📄 atomic_c11.h(3.46 KB)
📄 atomic_gcc_atomic.h(4.06 KB)
📄 atomic_gcc_sync.h(6.21 KB)
📄 background_thread_externs.h(1.29 KB)
📄 background_thread_inlines.h(2.09 KB)
📄 background_thread_structs.h(1.74 KB)
📄 base_externs.h(946 B)
📄 base_inlines.h(312 B)
📄 base_structs.h(1.52 KB)
📄 base_types.h(1.08 KB)
📄 bin.h(3.6 KB)
📄 bin_stats.h(1.35 KB)
📄 bin_types.h(474 B)
📄 bit_util.h(5.22 KB)
📄 bitmap.h(10.97 KB)
📄 cache_bin.h(3.69 KB)
📄 ckh.h(3.19 KB)
📄 ctl.h(3.62 KB)
📄 div.h(1.14 KB)
📄 emitter.h(13.06 KB)
📄 extent_dss.h(728 B)
📄 extent_externs.h(3.75 KB)
📄 extent_inlines.h(13.4 KB)
📄 extent_mmap.h(328 B)
📄 extent_structs.h(8.46 KB)
📄 extent_types.h(700 B)
📄 hash.h(7.88 KB)
📄 hook.h(5.41 KB)
📄 jemalloc_internal_decls.h(2.19 KB)
📄 jemalloc_internal_defs.h(10.93 KB)
📄 jemalloc_internal_defs_FreeBSD.h(256 B)
📄 jemalloc_internal_externs.h(1.75 KB)
📄 jemalloc_internal_includes.h(4.19 KB)
📄 jemalloc_internal_inlines_a.h(4.39 KB)
📄 jemalloc_internal_inlines_b.h(2.24 KB)
📄 jemalloc_internal_inlines_c.h(7.08 KB)
📄 jemalloc_internal_macros.h(3.99 KB)
📄 jemalloc_internal_types.h(3.42 KB)
📄 jemalloc_preamble.h(3.9 KB)
📄 large_externs.h(1.4 KB)
📄 log.h(3.67 KB)
📄 malloc_io.h(2.9 KB)
📄 mutex.h(9.34 KB)
📄 mutex_pool.h(2.81 KB)
📄 mutex_prof.h(3.55 KB)
📄 nstime.h(1.27 KB)
📄 pages.h(3.05 KB)
📄 ph.h(12.26 KB)
📄 private_namespace.h(22.72 KB)
📄 prng.h(4.69 KB)
📄 prof_externs.h(3.79 KB)
📄 prof_inlines_a.h(2.44 KB)
📄 prof_inlines_b.h(6.42 KB)
📄 prof_structs.h(5.02 KB)
📄 prof_types.h(1.74 KB)
📄 public_namespace.h(1.03 KB)
📄 ql.h(2.45 KB)
📄 qr.h(2.29 KB)
📄 quantum.h(1.75 KB)
📄 rb.h(37.41 KB)
📄 rtree.h(17.01 KB)
📄 rtree_tsd.h(1.82 KB)
📄 safety_check.h(797 B)
📄 sc.h(12.98 KB)
📄 seq.h(1.81 KB)
📄 smoothstep.h(15.26 KB)
📄 spin.h(613 B)
📄 stats.h(998 B)
📄 sz.h(7.96 KB)
📄 tcache_externs.h(2.09 KB)
📄 tcache_inlines.h(5.73 KB)
📄 tcache_structs.h(2.05 KB)
📄 tcache_types.h(2.01 KB)
📄 test_hooks.h(459 B)
📄 ticker.h(2.21 KB)
📄 tsd.h(12.49 KB)
📄 tsd_generic.h(3.76 KB)
📄 tsd_malloc_thread_cleanup.h(1.19 KB)
📄 tsd_tls.h(1.12 KB)
📄 tsd_types.h(258 B)
📄 util.h(1.43 KB)
📄 witness.h(9.32 KB)

Editing: bitmap.h

#ifndef JEMALLOC_INTERNAL_BITMAP_H
#define JEMALLOC_INTERNAL_BITMAP_H

#include "jemalloc/internal/arena_types.h"
#include "jemalloc/internal/bit_util.h"
#include "jemalloc/internal/sc.h"

typedef unsigned long bitmap_t;
#define LG_SIZEOF_BITMAP	LG_SIZEOF_LONG

/* Maximum bitmap bit count is 2^LG_BITMAP_MAXBITS. */
#if LG_SLAB_MAXREGS > LG_CEIL(SC_NSIZES)
/* Maximum bitmap bit count is determined by maximum regions per slab. */
#  define LG_BITMAP_MAXBITS	LG_SLAB_MAXREGS
#else
/* Maximum bitmap bit count is determined by number of extent size classes. */
#  define LG_BITMAP_MAXBITS	LG_CEIL(SC_NSIZES)
#endif
#define BITMAP_MAXBITS		(ZU(1) << LG_BITMAP_MAXBITS)

/* Number of bits per group. */
#define LG_BITMAP_GROUP_NBITS		(LG_SIZEOF_BITMAP + 3)
#define BITMAP_GROUP_NBITS		(1U << 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 BITMAP_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)))))
#define BITMAP_GROUPS_L4(nbits)						\
    BITMAP_BITS2GROUPS(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))
#define BITMAP_GROUPS_5_LEVEL(nbits)					\
    (BITMAP_GROUPS_4_LEVEL(nbits) + BITMAP_GROUPS_L4(nbits))

/*
 * Maximum number of groups required to support LG_BITMAP_MAXBITS.
 */
#ifdef BITMAP_USE_TREE

#if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
#  define BITMAP_GROUPS(nbits)	BITMAP_GROUPS_1_LEVEL(nbits)
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2
#  define BITMAP_GROUPS(nbits)	BITMAP_GROUPS_2_LEVEL(nbits)
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_2_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 3
#  define BITMAP_GROUPS(nbits)	BITMAP_GROUPS_3_LEVEL(nbits)
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
#  define BITMAP_GROUPS(nbits)	BITMAP_GROUPS_4_LEVEL(nbits)
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 5
#  define BITMAP_GROUPS(nbits)	BITMAP_GROUPS_5_LEVEL(nbits)
#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_5_LEVEL(BITMAP_MAXBITS)
#else
#  error "Unsupported bitmap size"
#endif

/*
 * Maximum number of levels possible.  This could be statically computed based
 * on LG_BITMAP_MAXBITS:
 *
 * #define BITMAP_MAX_LEVELS \
 *     (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \
 *     + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
 *
 * However, that would not allow the generic BITMAP_INFO_INITIALIZER() macro, so
 * instead hardcode BITMAP_MAX_LEVELS to the largest number supported by the
 * various cascading macros.  The only additional cost this incurs is some
 * unused trailing entries in bitmap_info_t structures; the bitmaps themselves
 * are not impacted.
 */
#define BITMAP_MAX_LEVELS	5

#define BITMAP_INFO_INITIALIZER(nbits) {				\
	/* nbits. */							\
	nbits,								\
	/* nlevels. */							\
	(BITMAP_GROUPS_L0(nbits) > BITMAP_GROUPS_L1(nbits)) +		\
	    (BITMAP_GROUPS_L1(nbits) > BITMAP_GROUPS_L2(nbits)) +	\
	    (BITMAP_GROUPS_L2(nbits) > BITMAP_GROUPS_L3(nbits)) +	\
	    (BITMAP_GROUPS_L3(nbits) > BITMAP_GROUPS_L4(nbits)) + 1,	\
	/* levels. */							\
	{								\
		{0},							\
		{BITMAP_GROUPS_L0(nbits)},				\
		{BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
		{BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits) +	\
		    BITMAP_GROUPS_L0(nbits)},				\
		{BITMAP_GROUPS_L3(nbits) + BITMAP_GROUPS_L2(nbits) +	\
		    BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
		{BITMAP_GROUPS_L4(nbits) + BITMAP_GROUPS_L3(nbits) +	\
		     BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits)	\
		     + BITMAP_GROUPS_L0(nbits)}				\
	}								\
}

#else /* BITMAP_USE_TREE */

#define BITMAP_GROUPS(nbits)	BITMAP_BITS2GROUPS(nbits)
#define BITMAP_GROUPS_MAX	BITMAP_BITS2GROUPS(BITMAP_MAXBITS)

#define BITMAP_INFO_INITIALIZER(nbits) {				\
	/* nbits. */							\
	nbits,								\
	/* ngroups. */							\
	BITMAP_BITS2GROUPS(nbits)					\
}

#endif /* BITMAP_USE_TREE */

typedef struct bitmap_level_s {
	/* Offset of this level's groups within the array of groups. */
	size_t group_offset;
} bitmap_level_t;

typedef struct bitmap_info_s {
	/* Logical number of bits in bitmap (stored at bottom level). */
	size_t nbits;

#ifdef BITMAP_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 /* BITMAP_USE_TREE */
	/* Number of groups necessary for nbits. */
	size_t ngroups;
#endif /* BITMAP_USE_TREE */
} bitmap_info_t;

void bitmap_info_init(bitmap_info_t *binfo, size_t nbits);
void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill);
size_t bitmap_size(const bitmap_info_t *binfo);

static inline bool
bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) {
#ifdef BITMAP_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
}

static inline bool
bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) {
	size_t goff;
	bitmap_t g;

assert(bit < binfo->nbits);
	goff = bit >> LG_BITMAP_GROUP_NBITS;
	g = bitmap[goff];
	return !(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
}

static 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 BITMAP_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
}

/* ffu: find first unset >= bit. */
static inline size_t
bitmap_ffu(const bitmap_t *bitmap, const bitmap_info_t *binfo, size_t min_bit) {
	assert(min_bit < binfo->nbits);

#ifdef BITMAP_USE_TREE
	size_t bit = 0;
	for (unsigned level = binfo->nlevels; level--;) {
		size_t lg_bits_per_group = (LG_BITMAP_GROUP_NBITS * (level +
		    1));
		bitmap_t group = bitmap[binfo->levels[level].group_offset + (bit
		    >> lg_bits_per_group)];
		unsigned group_nmask = (unsigned)(((min_bit > bit) ? (min_bit -
		    bit) : 0) >> (lg_bits_per_group - LG_BITMAP_GROUP_NBITS));
		assert(group_nmask <= BITMAP_GROUP_NBITS);
		bitmap_t group_mask = ~((1LU << group_nmask) - 1);
		bitmap_t group_masked = group & group_mask;
		if (group_masked == 0LU) {
			if (group == 0LU) {
				return binfo->nbits;
			}
			/*
			 * min_bit was preceded by one or more unset bits in
			 * this group, but there are no other unset bits in this
			 * group.  Try again starting at the first bit of the
			 * next sibling.  This will recurse at most once per
			 * non-root level.
			 */
			size_t sib_base = bit + (ZU(1) << lg_bits_per_group);
			assert(sib_base > min_bit);
			assert(sib_base > bit);
			if (sib_base >= binfo->nbits) {
				return binfo->nbits;
			}
			return bitmap_ffu(bitmap, binfo, sib_base);
		}
		bit += ((size_t)(ffs_lu(group_masked) - 1)) <<
		    (lg_bits_per_group - LG_BITMAP_GROUP_NBITS);
	}
	assert(bit >= min_bit);
	assert(bit < binfo->nbits);
	return bit;
#else
	size_t i = min_bit >> LG_BITMAP_GROUP_NBITS;
	bitmap_t g = bitmap[i] & ~((1LU << (min_bit & BITMAP_GROUP_NBITS_MASK))
	    - 1);
	size_t bit;
	do {
		bit = ffs_lu(g);
		if (bit != 0) {
			return (i << LG_BITMAP_GROUP_NBITS) + (bit - 1);
		}
		i++;
		g = bitmap[i];
	} while (i < binfo->ngroups);
	return binfo->nbits;
#endif
}

/* sfu: set first unset. */
static 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 BITMAP_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;
}

static inline void
bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) {
	size_t goff;
	bitmap_t *gp;
	bitmap_t g;
	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 BITMAP_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 /* BITMAP_USE_TREE */
}

#endif /* JEMALLOC_INTERNAL_BITMAP_H */

003 File Manager

Editing: bitmap.h

Upload File

Create Folder