jemalloc/include/jemalloc/internal/arena.h - platform/external/jemalloc - Gitiles

 /******************************************************************************/
 #ifdef JEMALLOC_H_TYPES

 /*
  * Subpages are an artificially designated partitioning of pages.  Their only
  * purpose is to support subpage-spaced size classes.
  *
  * There must be at least 4 subpages per page, due to the way size classes are
  * handled.
  */
 #define	LG_SUBPAGE		8
 #define	SUBPAGE			((size_t)(1U << LG_SUBPAGE))
 #define	SUBPAGE_MASK		(SUBPAGE - 1)

 /* Return the smallest subpage multiple that is >= s. */
 #define	SUBPAGE_CEILING(s)						\
 	(((s) + SUBPAGE_MASK) & ~SUBPAGE_MASK)

 #ifdef JEMALLOC_TINY
    /* Smallest size class to support. */
 #  define LG_TINY_MIN		LG_SIZEOF_PTR
 #endif

 /*
  * Maximum size class that is a multiple of the quantum, but not (necessarily)
  * a power of 2.  Above this size, allocations are rounded up to the nearest
  * power of 2.
  */
 #define	LG_QSPACE_MAX_DEFAULT	7

 /*
  * Maximum size class that is a multiple of the cacheline, but not (necessarily)
  * a power of 2.  Above this size, allocations are rounded up to the nearest
  * power of 2.
  */
 #define	LG_CSPACE_MAX_DEFAULT	9

 /*
  * RUN_MAX_OVRHD indicates maximum desired run header overhead.  Runs are sized
  * as small as possible such that this setting is still honored, without
  * violating other constraints.  The goal is to make runs as small as possible
  * without exceeding a per run external fragmentation threshold.
  *
  * We use binary fixed point math for overhead computations, where the binary
  * point is implicitly RUN_BFP bits to the left.
  *
  * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
  * honored for some/all object sizes, since there is one bit of header overhead
  * per object (plus a constant).  This constraint is relaxed (ignored) for runs
  * that are so small that the per-region overhead is greater than:
  *
  *   (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
  */
 #define	RUN_BFP			12
 /*                                    \/   Implicit binary fixed point. */
 #define	RUN_MAX_OVRHD		0x0000003dU
 #define	RUN_MAX_OVRHD_RELAX	0x00001800U

 /*
  * The minimum ratio of active:dirty pages per arena is computed as:
  *
  *   (nactive >> opt_lg_dirty_mult) >= ndirty
  *
  * So, supposing that opt_lg_dirty_mult is 5, there can be no less than 32
  * times as many active pages as dirty pages.
  */
 #define	LG_DIRTY_MULT_DEFAULT	5

 typedef struct arena_chunk_map_s arena_chunk_map_t;
 typedef struct arena_chunk_s arena_chunk_t;
 typedef struct arena_run_s arena_run_t;
 typedef struct arena_bin_s arena_bin_t;
 typedef struct arena_s arena_t;

 #endif /* JEMALLOC_H_TYPES */
 /******************************************************************************/
 #ifdef JEMALLOC_H_STRUCTS

 /* Each element of the chunk map corresponds to one page within the chunk. */
 struct arena_chunk_map_s {
 	union {
 		/*
 		 * Linkage for run trees.  There are two disjoint uses:
 		 *
 		 * 1) arena_t's runs_avail_{clean,dirty} trees.
 		 * 2) arena_run_t conceptually uses this linkage for in-use
 		 *    non-full runs, rather than directly embedding linkage.
 		 */
 		rb_node(arena_chunk_map_t)	rb_link;
 		/*
 		 * List of runs currently in purgatory.  arena_chunk_purge()
 		 * temporarily allocates runs that contain dirty pages while
 		 * purging, so that other threads cannot use the runs while the
 		 * purging thread is operating without the arena lock held.
 		 */
 		ql_elm(arena_chunk_map_t)	ql_link;
 	}				u;

 #ifdef JEMALLOC_PROF
 	/* Profile counters, used for large object runs. */
 	prof_ctx_t			*prof_ctx;
 #endif

 	/*
 	 * Run address (or size) and various flags are stored together.  The bit
 	 * layout looks like (assuming 32-bit system):
 	 *
 	 *   ???????? ???????? ????---- ----dzla
 	 *
 	 * ? : Unallocated: Run address for first/last pages, unset for internal
 	 *                  pages.
 	 *     Small: Run page offset.
 	 *     Large: Run size for first page, unset for trailing pages.
 	 * - : Unused.
 	 * d : dirty?
 	 * z : zeroed?
 	 * l : large?
 	 * a : allocated?
 	 *
 	 * Following are example bit patterns for the three types of runs.
 	 *
 	 * p : run page offset
 	 * s : run size
 	 * c : size class (used only if prof_promote is true)
 	 * x : don't care
 	 * - : 0
 	 * + : 1
 	 * [DZLA] : bit set
 	 * [dzla] : bit unset
 	 *
 	 *   Unallocated (clean):
 	 *     ssssssss ssssssss ssss---- ----dz--
 	 *     xxxxxxxx xxxxxxxx xxxx---- -----Zxx
 	 *     ssssssss ssssssss ssss---- ----dZ--
 	 *
 	 *   Unallocated (dirty):
 	 *     ssssssss ssssssss ssss---- ----D---
 	 *     xxxxxxxx xxxxxxxx xxxx---- ----xxxx
 	 *     ssssssss ssssssss ssss---- ----D---
 	 *
 	 *   Small:
 	 *     pppppppp pppppppp pppp---- ----d--a
 	 *     pppppppp pppppppp pppp---- -------a
 	 *     pppppppp pppppppp pppp---- ----d--a
 	 *
 	 *   Large:
 	 *     ssssssss ssssssss ssss++++ ++++D-la
 	 *     xxxxxxxx xxxxxxxx xxxx---- ----xxxx
 	 *     -------- -------- -------- ----D-la
 	 *
 	 *   Large (sampled, size <= PAGE_SIZE):
 	 *     ssssssss ssssssss sssscccc ccccD-la
 	 *
 	 *   Large (not sampled, size == PAGE_SIZE):
 	 *     ssssssss ssssssss ssss++++ ++++D-la
 	 */
 	size_t				bits;
 #ifdef JEMALLOC_PROF
 #define	CHUNK_MAP_CLASS_SHIFT	4
 #define	CHUNK_MAP_CLASS_MASK	((size_t)0xff0U)
 #endif
 #define	CHUNK_MAP_FLAGS_MASK	((size_t)0xfU)
 #define	CHUNK_MAP_DIRTY		((size_t)0x8U)
 #define	CHUNK_MAP_ZEROED	((size_t)0x4U)
 #define	CHUNK_MAP_LARGE		((size_t)0x2U)
 #define	CHUNK_MAP_ALLOCATED	((size_t)0x1U)
 #define	CHUNK_MAP_KEY		CHUNK_MAP_ALLOCATED
 };
 typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
 typedef rb_tree(arena_chunk_map_t) arena_run_tree_t;

 /* Arena chunk header. */
 struct arena_chunk_s {
 	/* Arena that owns the chunk. */
 	arena_t		*arena;

 	/* Linkage for the arena's chunks_dirty list. */
 	ql_elm(arena_chunk_t) link_dirty;

 	/*
 	 * True if the chunk is currently in the chunks_dirty list, due to
 	 * having at some point contained one or more dirty pages.  Removal
 	 * from chunks_dirty is lazy, so (dirtied && ndirty == 0) is possible.
 	 */
 	bool		dirtied;

 	/* Number of dirty pages. */
 	size_t		ndirty;

 	/* Map of pages within chunk that keeps track of free/large/small. */
 	arena_chunk_map_t map[1]; /* Dynamically sized. */
 };
 typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;

 struct arena_run_s {
 #ifdef JEMALLOC_DEBUG
 	uint32_t	magic;
 #  define ARENA_RUN_MAGIC 0x384adf93
 #endif

 	/* Bin this run is associated with. */
 	arena_bin_t	*bin;

 	/* Stack of available freed regions, or NULL. */
 	void		*avail;

 	/* Next region that has never been allocated, or run boundary. */
 	void		*next;

 	/* Number of free regions in run. */
 	unsigned	nfree;
 };

 struct arena_bin_s {
 	/*
 	 * All operations on runcur, runs, and stats require that lock be
 	 * locked.  Run allocation/deallocation are protected by the arena lock,
 	 * which may be acquired while holding one or more bin locks, but not
 	 * vise versa.
 	 */
 	malloc_mutex_t	lock;

 	/*
 	 * Current run being used to service allocations of this bin's size
 	 * class.
 	 */
 	arena_run_t	*runcur;

 	/*
 	 * Tree of non-full runs.  This tree is used when looking for an
 	 * existing run when runcur is no longer usable.  We choose the
 	 * non-full run that is lowest in memory; this policy tends to keep
 	 * objects packed well, and it can also help reduce the number of
 	 * almost-empty chunks.
 	 */
 	arena_run_tree_t runs;

 	/* Size of regions in a run for this bin's size class. */
 	size_t		reg_size;

 	/* Total size of a run for this bin's size class. */
 	size_t		run_size;

 	/* Total number of regions in a run for this bin's size class. */
 	uint32_t	nregs;

 #ifdef JEMALLOC_PROF
 	/*
 	 * Offset of first (prof_ctx_t *) in a run header for this bin's size
 	 * class, or 0 if (opt_prof == false).
 	 */
 	uint32_t	ctx0_offset;
 #endif

 	/* Offset of first region in a run for this bin's size class. */
 	uint32_t	reg0_offset;

 #ifdef JEMALLOC_STATS
 	/* Bin statistics. */
 	malloc_bin_stats_t stats;
 #endif
 };

 struct arena_s {
 #ifdef JEMALLOC_DEBUG
 	uint32_t		magic;
 #  define ARENA_MAGIC 0x947d3d24
 #endif

 	/* This arena's index within the arenas array. */
 	unsigned		ind;

 	/*
 	 * All non-bin-related operations on this arena require that lock be
 	 * locked.
 	 */
 	malloc_mutex_t		lock;

 #ifdef JEMALLOC_STATS
 	arena_stats_t		stats;
 #  ifdef JEMALLOC_TCACHE
 	/*
 	 * List of tcaches for extant threads associated with this arena.
 	 * Stats from these are merged incrementally, and at exit.
 	 */
 	ql_head(tcache_t)	tcache_ql;
 #  endif
 #endif

 #ifdef JEMALLOC_PROF
 	uint64_t		prof_accumbytes;
 #endif

 	/* List of dirty-page-containing chunks this arena manages. */
 	ql_head(arena_chunk_t)	chunks_dirty;

 	/*
 	 * In order to avoid rapid chunk allocation/deallocation when an arena
 	 * oscillates right on the cusp of needing a new chunk, cache the most
 	 * recently freed chunk.  The spare is left in the arena's chunk trees
 	 * until it is deleted.
 	 *
 	 * There is one spare chunk per arena, rather than one spare total, in
 	 * order to avoid interactions between multiple threads that could make
 	 * a single spare inadequate.
 	 */
 	arena_chunk_t		*spare;

 	/* Number of pages in active runs. */
 	size_t			nactive;

 	/*
 	 * Current count of pages within unused runs that are potentially
 	 * dirty, and for which madvise(... MADV_DONTNEED) has not been called.
 	 * By tracking this, we can institute a limit on how much dirty unused
 	 * memory is mapped for each arena.
 	 */
 	size_t			ndirty;

 	/*
 	 * Approximate number of pages being purged.  It is possible for
 	 * multiple threads to purge dirty pages concurrently, and they use
 	 * npurgatory to indicate the total number of pages all threads are
 	 * attempting to purge.
 	 */
 	size_t			npurgatory;

 	/*
 	 * Size/address-ordered trees of this arena's available runs.  The trees
 	 * are used for first-best-fit run allocation.  The dirty tree contains
 	 * runs with dirty pages (i.e. very likely to have been touched and
 	 * therefore have associated physical pages), whereas the clean tree
 	 * contains runs with pages that either have no associated physical
 	 * pages, or have pages that the kernel may recycle at any time due to
 	 * previous madvise(2) calls.  The dirty tree is used in preference to
 	 * the clean tree for allocations, because using dirty pages reduces
 	 * the amount of dirty purging necessary to keep the active:dirty page
 	 * ratio below the purge threshold.
 	 */
 	arena_avail_tree_t	runs_avail_clean;
 	arena_avail_tree_t	runs_avail_dirty;

 	/*
 	 * bins is used to store trees of free regions of the following sizes,
 	 * assuming a 16-byte quantum, 4 KiB page size, and default
 	 * JEMALLOC_OPTIONS.
 	 *
 	 *   bins[i] |   size |
 	 *   --------+--------+
 	 *        0  |      2 |
 	 *        1  |      4 |
 	 *        2  |      8 |
 	 *   --------+--------+
 	 *        3  |     16 |
 	 *        4  |     32 |
 	 *        5  |     48 |
 	 *           :        :
 	 *        8  |     96 |
 	 *        9  |    112 |
 	 *       10  |    128 |
 	 *   --------+--------+
 	 *       11  |    192 |
 	 *       12  |    256 |
 	 *       13  |    320 |
 	 *       14  |    384 |
 	 *       15  |    448 |
 	 *       16  |    512 |
 	 *   --------+--------+
 	 *       17  |    768 |
 	 *       18  |   1024 |
 	 *       19  |   1280 |
 	 *           :        :
 	 *       27  |   3328 |
 	 *       28  |   3584 |
 	 *       29  |   3840 |
 	 *   --------+--------+
 	 *       30  |  4 KiB |
 	 *       31  |  6 KiB |
 	 *       33  |  8 KiB |
 	 *           :        :
 	 *       43  | 28 KiB |
 	 *       44  | 30 KiB |
 	 *       45  | 32 KiB |
 	 *   --------+--------+
 	 */
 	arena_bin_t		bins[1]; /* Dynamically sized. */
 };

 #endif /* JEMALLOC_H_STRUCTS */
 /******************************************************************************/
 #ifdef JEMALLOC_H_EXTERNS

 extern size_t	opt_lg_qspace_max;
 extern size_t	opt_lg_cspace_max;
 extern ssize_t		opt_lg_dirty_mult;
 extern uint8_t const	*small_size2bin;

 /* Various bin-related settings. */
 #ifdef JEMALLOC_TINY		/* Number of (2^n)-spaced tiny bins. */
 #  define		ntbins	((unsigned)(LG_QUANTUM - LG_TINY_MIN))
 #else
 #  define		ntbins	0
 #endif
 extern unsigned		nqbins; /* Number of quantum-spaced bins. */
 extern unsigned		ncbins; /* Number of cacheline-spaced bins. */
 extern unsigned		nsbins; /* Number of subpage-spaced bins. */
 extern unsigned		nbins;
 #ifdef JEMALLOC_TINY
 #  define		tspace_max	((size_t)(QUANTUM >> 1))
 #endif
 #define			qspace_min	QUANTUM
 extern size_t		qspace_max;
 extern size_t		cspace_min;
 extern size_t		cspace_max;
 extern size_t		sspace_min;
 extern size_t		sspace_max;
 #define			small_maxclass	sspace_max

 #define			nlclasses (chunk_npages - arena_chunk_header_npages)

 #ifdef JEMALLOC_TCACHE
 void	arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin,
     size_t binind
 #  ifdef JEMALLOC_PROF
     , uint64_t prof_accumbytes
 #  endif
     );
 #endif
 #ifdef JEMALLOC_PROF
 void	arena_prof_accum(arena_t *arena, uint64_t accumbytes);
 #endif
 void	*arena_malloc_small(arena_t *arena, size_t size, bool zero);
 void	*arena_malloc_large(arena_t *arena, size_t size, bool zero);
 void	*arena_malloc(size_t size, bool zero);
 void	*arena_palloc(arena_t *arena, size_t alignment, size_t size,
     size_t alloc_size);
 size_t	arena_salloc(const void *ptr);
 #ifdef JEMALLOC_PROF
 void	arena_prof_promoted(const void *ptr, size_t size);
 size_t	arena_salloc_demote(const void *ptr);
 prof_ctx_t	*arena_prof_ctx_get(const void *ptr);
 void	arena_prof_ctx_set(const void *ptr, prof_ctx_t *ctx);
 #endif
 void	arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
     arena_chunk_map_t *mapelm);
 void	arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr);
 #ifdef JEMALLOC_STATS
 void	arena_stats_merge(arena_t *arena, size_t *nactive, size_t *ndirty,
     arena_stats_t *astats, malloc_bin_stats_t *bstats,
     malloc_large_stats_t *lstats);
 #endif
 void	*arena_ralloc(void *ptr, size_t size, size_t oldsize);
 bool	arena_new(arena_t *arena, unsigned ind);
 bool	arena_boot(void);

 #endif /* JEMALLOC_H_EXTERNS */
 /******************************************************************************/
 #ifdef JEMALLOC_H_INLINES

 #ifndef JEMALLOC_ENABLE_INLINE
 void	arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
 #endif

 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_ARENA_C_))
 JEMALLOC_INLINE void
 arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
 {
 	size_t pageind;
 	arena_chunk_map_t *mapelm;

 	assert(arena != NULL);
 	assert(arena->magic == ARENA_MAGIC);
 	assert(chunk->arena == arena);
 	assert(ptr != NULL);
 	assert(CHUNK_ADDR2BASE(ptr) != ptr);

 	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT);
 	mapelm = &chunk->map[pageind];
 	assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0);
 	if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) {
 		/* Small allocation. */
 #ifdef JEMALLOC_TCACHE
 		tcache_t *tcache;

 		if ((tcache = tcache_get()) != NULL)
 			tcache_dalloc_small(tcache, ptr);
 		else {
 #endif
 			arena_run_t *run;
 			arena_bin_t *bin;

 			run = (arena_run_t *)((uintptr_t)chunk +
 			    (uintptr_t)((pageind - (mapelm->bits >>
 			    PAGE_SHIFT)) << PAGE_SHIFT));
 			assert(run->magic == ARENA_RUN_MAGIC);
 			assert(((uintptr_t)ptr - ((uintptr_t)run +
 			    (uintptr_t)run->bin->reg0_offset)) %
 			    run->bin->reg_size == 0);
 			bin = run->bin;
 			malloc_mutex_lock(&bin->lock);
 			arena_dalloc_bin(arena, chunk, ptr, mapelm);
 			malloc_mutex_unlock(&bin->lock);
 #ifdef JEMALLOC_TCACHE
 		}
 #endif
 	} else {
 #ifdef JEMALLOC_TCACHE
 		size_t size = mapelm->bits & ~PAGE_MASK;

 		assert(((uintptr_t)ptr & PAGE_MASK) == 0);
 		if (size <= tcache_maxclass) {
 			tcache_t *tcache;

 			if ((tcache = tcache_get()) != NULL)
 				tcache_dalloc_large(tcache, ptr, size);
 			else {
 				malloc_mutex_lock(&arena->lock);
 				arena_dalloc_large(arena, chunk, ptr);
 				malloc_mutex_unlock(&arena->lock);
 			}
 		} else {
 			malloc_mutex_lock(&arena->lock);
 			arena_dalloc_large(arena, chunk, ptr);
 			malloc_mutex_unlock(&arena->lock);
 		}
 #else
 		assert(((uintptr_t)ptr & PAGE_MASK) == 0);
 		malloc_mutex_lock(&arena->lock);
 		arena_dalloc_large(arena, chunk, ptr);
 		malloc_mutex_unlock(&arena->lock);
 #endif
 	}
 }
 #endif

 #endif /* JEMALLOC_H_INLINES */
 /******************************************************************************/
	/******************************************************************************/
	#ifdef JEMALLOC_H_TYPES

	/*
	* Subpages are an artificially designated partitioning of pages. Their only
	* purpose is to support subpage-spaced size classes.
	*
	* There must be at least 4 subpages per page, due to the way size classes are
	* handled.
	*/
	#define LG_SUBPAGE 8
	#define SUBPAGE ((size_t)(1U << LG_SUBPAGE))
	#define SUBPAGE_MASK (SUBPAGE - 1)

	/* Return the smallest subpage multiple that is >= s. */
	#define SUBPAGE_CEILING(s) \
	(((s) + SUBPAGE_MASK) & ~SUBPAGE_MASK)

	#ifdef JEMALLOC_TINY
	/* Smallest size class to support. */
	# define LG_TINY_MIN LG_SIZEOF_PTR
	#endif

	/*
	* Maximum size class that is a multiple of the quantum, but not (necessarily)
	* a power of 2. Above this size, allocations are rounded up to the nearest
	* power of 2.
	*/
	#define LG_QSPACE_MAX_DEFAULT 7

	/*
	* Maximum size class that is a multiple of the cacheline, but not (necessarily)
	* a power of 2. Above this size, allocations are rounded up to the nearest
	* power of 2.
	*/
	#define LG_CSPACE_MAX_DEFAULT 9

	/*
	* RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized
	* as small as possible such that this setting is still honored, without
	* violating other constraints. The goal is to make runs as small as possible
	* without exceeding a per run external fragmentation threshold.
	*
	* We use binary fixed point math for overhead computations, where the binary
	* point is implicitly RUN_BFP bits to the left.
	*
	* Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be
	* honored for some/all object sizes, since there is one bit of header overhead
	* per object (plus a constant). This constraint is relaxed (ignored) for runs
	* that are so small that the per-region overhead is greater than:
	*
	* (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP))
	*/
	#define RUN_BFP 12
	/* \/ Implicit binary fixed point. */
	#define RUN_MAX_OVRHD 0x0000003dU
	#define RUN_MAX_OVRHD_RELAX 0x00001800U

	/*
	* The minimum ratio of active:dirty pages per arena is computed as:
	*
	* (nactive >> opt_lg_dirty_mult) >= ndirty
	*
	* So, supposing that opt_lg_dirty_mult is 5, there can be no less than 32
	* times as many active pages as dirty pages.
	*/
	#define LG_DIRTY_MULT_DEFAULT 5

	typedef struct arena_chunk_map_s arena_chunk_map_t;
	typedef struct arena_chunk_s arena_chunk_t;
	typedef struct arena_run_s arena_run_t;
	typedef struct arena_bin_s arena_bin_t;
	typedef struct arena_s arena_t;

	#endif /* JEMALLOC_H_TYPES */
	/******************************************************************************/
	#ifdef JEMALLOC_H_STRUCTS

	/* Each element of the chunk map corresponds to one page within the chunk. */
	struct arena_chunk_map_s {
	union {
	/*
	* Linkage for run trees. There are two disjoint uses:
	*
	* 1) arena_t's runs_avail_{clean,dirty} trees.
	* 2) arena_run_t conceptually uses this linkage for in-use
	* non-full runs, rather than directly embedding linkage.
	*/
	rb_node(arena_chunk_map_t) rb_link;
	/*
	* List of runs currently in purgatory. arena_chunk_purge()
	* temporarily allocates runs that contain dirty pages while
	* purging, so that other threads cannot use the runs while the
	* purging thread is operating without the arena lock held.
	*/
	ql_elm(arena_chunk_map_t) ql_link;
	} u;

	#ifdef JEMALLOC_PROF
	/* Profile counters, used for large object runs. */
	prof_ctx_t *prof_ctx;
	#endif

	/*
	* Run address (or size) and various flags are stored together. The bit
	* layout looks like (assuming 32-bit system):
	*
	* ???????? ???????? ????---- ----dzla
	*
	* ? : Unallocated: Run address for first/last pages, unset for internal
	* pages.
	* Small: Run page offset.
	* Large: Run size for first page, unset for trailing pages.
	* - : Unused.
	* d : dirty?
	* z : zeroed?
	* l : large?
	* a : allocated?
	*
	* Following are example bit patterns for the three types of runs.
	*
	* p : run page offset
	* s : run size
	* c : size class (used only if prof_promote is true)
	* x : don't care
	* - : 0
	* + : 1
	* [DZLA] : bit set
	* [dzla] : bit unset
	*
	* Unallocated (clean):
	* ssssssss ssssssss ssss---- ----dz--
	* xxxxxxxx xxxxxxxx xxxx---- -----Zxx
	* ssssssss ssssssss ssss---- ----dZ--
	*
	* Unallocated (dirty):
	* ssssssss ssssssss ssss---- ----D---
	* xxxxxxxx xxxxxxxx xxxx---- ----xxxx
	* ssssssss ssssssss ssss---- ----D---
	*
	* Small:
	* pppppppp pppppppp pppp---- ----d--a
	* pppppppp pppppppp pppp---- -------a
	* pppppppp pppppppp pppp---- ----d--a
	*
	* Large:
	* ssssssss ssssssss ssss++++ ++++D-la
	* xxxxxxxx xxxxxxxx xxxx---- ----xxxx
	* -------- -------- -------- ----D-la
	*
	* Large (sampled, size <= PAGE_SIZE):
	* ssssssss ssssssss sssscccc ccccD-la
	*
	* Large (not sampled, size == PAGE_SIZE):
	* ssssssss ssssssss ssss++++ ++++D-la
	*/
	size_t bits;
	#ifdef JEMALLOC_PROF
	#define CHUNK_MAP_CLASS_SHIFT 4
	#define CHUNK_MAP_CLASS_MASK ((size_t)0xff0U)
	#endif
	#define CHUNK_MAP_FLAGS_MASK ((size_t)0xfU)
	#define CHUNK_MAP_DIRTY ((size_t)0x8U)
	#define CHUNK_MAP_ZEROED ((size_t)0x4U)
	#define CHUNK_MAP_LARGE ((size_t)0x2U)
	#define CHUNK_MAP_ALLOCATED ((size_t)0x1U)
	#define CHUNK_MAP_KEY CHUNK_MAP_ALLOCATED
	};
	typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
	typedef rb_tree(arena_chunk_map_t) arena_run_tree_t;

	/* Arena chunk header. */
	struct arena_chunk_s {
	/* Arena that owns the chunk. */
	arena_t *arena;

	/* Linkage for the arena's chunks_dirty list. */
	ql_elm(arena_chunk_t) link_dirty;

	/*
	* True if the chunk is currently in the chunks_dirty list, due to
	* having at some point contained one or more dirty pages. Removal
	* from chunks_dirty is lazy, so (dirtied && ndirty == 0) is possible.
	*/
	bool dirtied;

	/* Number of dirty pages. */
	size_t ndirty;

	/* Map of pages within chunk that keeps track of free/large/small. */
	arena_chunk_map_t map[1]; /* Dynamically sized. */
	};
	typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;

	struct arena_run_s {
	#ifdef JEMALLOC_DEBUG
	uint32_t magic;
	# define ARENA_RUN_MAGIC 0x384adf93
	#endif

	/* Bin this run is associated with. */
	arena_bin_t *bin;

	/* Stack of available freed regions, or NULL. */
	void *avail;

	/* Next region that has never been allocated, or run boundary. */
	void *next;

	/* Number of free regions in run. */
	unsigned nfree;
	};

	struct arena_bin_s {
	/*
	* All operations on runcur, runs, and stats require that lock be
	* locked. Run allocation/deallocation are protected by the arena lock,
	* which may be acquired while holding one or more bin locks, but not
	* vise versa.
	*/
	malloc_mutex_t lock;

	/*
	* Current run being used to service allocations of this bin's size
	* class.
	*/
	arena_run_t *runcur;

	/*
	* Tree of non-full runs. This tree is used when looking for an
	* existing run when runcur is no longer usable. We choose the
	* non-full run that is lowest in memory; this policy tends to keep
	* objects packed well, and it can also help reduce the number of
	* almost-empty chunks.
	*/
	arena_run_tree_t runs;

	/* Size of regions in a run for this bin's size class. */
	size_t reg_size;

	/* Total size of a run for this bin's size class. */
	size_t run_size;

	/* Total number of regions in a run for this bin's size class. */
	uint32_t nregs;

	#ifdef JEMALLOC_PROF
	/*
	* Offset of first (prof_ctx_t *) in a run header for this bin's size
	* class, or 0 if (opt_prof == false).
	*/
	uint32_t ctx0_offset;
	#endif

	/* Offset of first region in a run for this bin's size class. */
	uint32_t reg0_offset;

	#ifdef JEMALLOC_STATS
	/* Bin statistics. */
	malloc_bin_stats_t stats;
	#endif
	};

	struct arena_s {
	#ifdef JEMALLOC_DEBUG
	uint32_t magic;
	# define ARENA_MAGIC 0x947d3d24
	#endif

	/* This arena's index within the arenas array. */
	unsigned ind;

	/*
	* All non-bin-related operations on this arena require that lock be
	* locked.
	*/
	malloc_mutex_t lock;

	#ifdef JEMALLOC_STATS
	arena_stats_t stats;
	# ifdef JEMALLOC_TCACHE
	/*
	* List of tcaches for extant threads associated with this arena.
	* Stats from these are merged incrementally, and at exit.
	*/
	ql_head(tcache_t) tcache_ql;
	# endif
	#endif

	#ifdef JEMALLOC_PROF
	uint64_t prof_accumbytes;
	#endif

	/* List of dirty-page-containing chunks this arena manages. */
	ql_head(arena_chunk_t) chunks_dirty;

	/*
	* In order to avoid rapid chunk allocation/deallocation when an arena
	* oscillates right on the cusp of needing a new chunk, cache the most
	* recently freed chunk. The spare is left in the arena's chunk trees
	* until it is deleted.
	*
	* There is one spare chunk per arena, rather than one spare total, in
	* order to avoid interactions between multiple threads that could make
	* a single spare inadequate.
	*/
	arena_chunk_t *spare;

	/* Number of pages in active runs. */
	size_t nactive;

	/*
	* Current count of pages within unused runs that are potentially
	* dirty, and for which madvise(... MADV_DONTNEED) has not been called.
	* By tracking this, we can institute a limit on how much dirty unused
	* memory is mapped for each arena.
	*/
	size_t ndirty;

	/*
	* Approximate number of pages being purged. It is possible for
	* multiple threads to purge dirty pages concurrently, and they use
	* npurgatory to indicate the total number of pages all threads are
	* attempting to purge.
	*/
	size_t npurgatory;

	/*
	* Size/address-ordered trees of this arena's available runs. The trees
	* are used for first-best-fit run allocation. The dirty tree contains
	* runs with dirty pages (i.e. very likely to have been touched and
	* therefore have associated physical pages), whereas the clean tree
	* contains runs with pages that either have no associated physical
	* pages, or have pages that the kernel may recycle at any time due to
	* previous madvise(2) calls. The dirty tree is used in preference to
	* the clean tree for allocations, because using dirty pages reduces
	* the amount of dirty purging necessary to keep the active:dirty page
	* ratio below the purge threshold.
	*/
	arena_avail_tree_t runs_avail_clean;
	arena_avail_tree_t runs_avail_dirty;

	/*
	* bins is used to store trees of free regions of the following sizes,
	* assuming a 16-byte quantum, 4 KiB page size, and default
	* JEMALLOC_OPTIONS.
	*
	* bins[i] \| size \|
	* --------+--------+
	* 0 \| 2 \|
	* 1 \| 4 \|
	* 2 \| 8 \|
	* --------+--------+
	* 3 \| 16 \|
	* 4 \| 32 \|
	* 5 \| 48 \|
	* : :
	* 8 \| 96 \|
	* 9 \| 112 \|
	* 10 \| 128 \|
	* --------+--------+
	* 11 \| 192 \|
	* 12 \| 256 \|
	* 13 \| 320 \|
	* 14 \| 384 \|
	* 15 \| 448 \|
	* 16 \| 512 \|
	* --------+--------+
	* 17 \| 768 \|
	* 18 \| 1024 \|
	* 19 \| 1280 \|
	* : :
	* 27 \| 3328 \|
	* 28 \| 3584 \|
	* 29 \| 3840 \|
	* --------+--------+
	* 30 \| 4 KiB \|
	* 31 \| 6 KiB \|
	* 33 \| 8 KiB \|
	* : :
	* 43 \| 28 KiB \|
	* 44 \| 30 KiB \|
	* 45 \| 32 KiB \|
	* --------+--------+
	*/
	arena_bin_t bins[1]; /* Dynamically sized. */
	};

	#endif /* JEMALLOC_H_STRUCTS */
	/******************************************************************************/
	#ifdef JEMALLOC_H_EXTERNS

	extern size_t opt_lg_qspace_max;
	extern size_t opt_lg_cspace_max;
	extern ssize_t opt_lg_dirty_mult;
	extern uint8_t const *small_size2bin;

	/* Various bin-related settings. */
	#ifdef JEMALLOC_TINY /* Number of (2^n)-spaced tiny bins. */
	# define ntbins ((unsigned)(LG_QUANTUM - LG_TINY_MIN))
	#else
	# define ntbins 0
	#endif
	extern unsigned nqbins; /* Number of quantum-spaced bins. */
	extern unsigned ncbins; /* Number of cacheline-spaced bins. */
	extern unsigned nsbins; /* Number of subpage-spaced bins. */
	extern unsigned nbins;
	#ifdef JEMALLOC_TINY
	# define tspace_max ((size_t)(QUANTUM >> 1))
	#endif
	#define qspace_min QUANTUM
	extern size_t qspace_max;
	extern size_t cspace_min;
	extern size_t cspace_max;
	extern size_t sspace_min;
	extern size_t sspace_max;
	#define small_maxclass sspace_max

	#define nlclasses (chunk_npages - arena_chunk_header_npages)

	#ifdef JEMALLOC_TCACHE
	void arena_tcache_fill_small(arena_t arena, tcache_bin_t tbin,
	size_t binind
	# ifdef JEMALLOC_PROF
	, uint64_t prof_accumbytes
	# endif
	);
	#endif
	#ifdef JEMALLOC_PROF
	void arena_prof_accum(arena_t *arena, uint64_t accumbytes);
	#endif
	void arena_malloc_small(arena_t arena, size_t size, bool zero);
	void arena_malloc_large(arena_t arena, size_t size, bool zero);
	void *arena_malloc(size_t size, bool zero);
	void arena_palloc(arena_t arena, size_t alignment, size_t size,
	size_t alloc_size);
	size_t arena_salloc(const void *ptr);
	#ifdef JEMALLOC_PROF
	void arena_prof_promoted(const void *ptr, size_t size);
	size_t arena_salloc_demote(const void *ptr);
	prof_ctx_t arena_prof_ctx_get(const void ptr);
	void arena_prof_ctx_set(const void ptr, prof_ctx_t ctx);
	#endif
	void arena_dalloc_bin(arena_t arena, arena_chunk_t chunk, void *ptr,
	arena_chunk_map_t *mapelm);
	void arena_dalloc_large(arena_t arena, arena_chunk_t chunk, void *ptr);
	#ifdef JEMALLOC_STATS
	void arena_stats_merge(arena_t arena, size_t nactive, size_t *ndirty,
	arena_stats_t astats, malloc_bin_stats_t bstats,
	malloc_large_stats_t *lstats);
	#endif
	void arena_ralloc(void ptr, size_t size, size_t oldsize);
	bool arena_new(arena_t *arena, unsigned ind);
	bool arena_boot(void);

	#endif /* JEMALLOC_H_EXTERNS */
	/******************************************************************************/
	#ifdef JEMALLOC_H_INLINES

	#ifndef JEMALLOC_ENABLE_INLINE
	void arena_dalloc(arena_t arena, arena_chunk_t chunk, void *ptr);
	#endif

	#if (defined(JEMALLOC_ENABLE_INLINE) \|\| defined(JEMALLOC_ARENA_C_))
	JEMALLOC_INLINE void
	arena_dalloc(arena_t arena, arena_chunk_t chunk, void *ptr)
	{
	size_t pageind;
	arena_chunk_map_t *mapelm;

	assert(arena != NULL);
	assert(arena->magic == ARENA_MAGIC);
	assert(chunk->arena == arena);
	assert(ptr != NULL);
	assert(CHUNK_ADDR2BASE(ptr) != ptr);

	pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT);
	mapelm = &chunk->map[pageind];
	assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0);
	if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) {
	/* Small allocation. */
	#ifdef JEMALLOC_TCACHE
	tcache_t *tcache;

	if ((tcache = tcache_get()) != NULL)
	tcache_dalloc_small(tcache, ptr);
	else {
	#endif
	arena_run_t *run;
	arena_bin_t *bin;

	run = (arena_run_t *)((uintptr_t)chunk +
	(uintptr_t)((pageind - (mapelm->bits >>
	PAGE_SHIFT)) << PAGE_SHIFT));
	assert(run->magic == ARENA_RUN_MAGIC);
	assert(((uintptr_t)ptr - ((uintptr_t)run +
	(uintptr_t)run->bin->reg0_offset)) %
	run->bin->reg_size == 0);
	bin = run->bin;
	malloc_mutex_lock(&bin->lock);
	arena_dalloc_bin(arena, chunk, ptr, mapelm);
	malloc_mutex_unlock(&bin->lock);
	#ifdef JEMALLOC_TCACHE
	}
	#endif
	} else {
	#ifdef JEMALLOC_TCACHE
	size_t size = mapelm->bits & ~PAGE_MASK;

	assert(((uintptr_t)ptr & PAGE_MASK) == 0);
	if (size <= tcache_maxclass) {
	tcache_t *tcache;

	if ((tcache = tcache_get()) != NULL)
	tcache_dalloc_large(tcache, ptr, size);
	else {
	malloc_mutex_lock(&arena->lock);
	arena_dalloc_large(arena, chunk, ptr);
	malloc_mutex_unlock(&arena->lock);
	}
	} else {
	malloc_mutex_lock(&arena->lock);
	arena_dalloc_large(arena, chunk, ptr);
	malloc_mutex_unlock(&arena->lock);
	}
	#else
	assert(((uintptr_t)ptr & PAGE_MASK) == 0);
	malloc_mutex_lock(&arena->lock);
	arena_dalloc_large(arena, chunk, ptr);
	malloc_mutex_unlock(&arena->lock);
	#endif
	}
	}
	#endif

	#endif /* JEMALLOC_H_INLINES */
	/******************************************************************************/