arena.h revision b172610317babc7f365584ddd7fdaf4eb8d9d04c
1e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/******************************************************************************/ 2e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#ifdef JEMALLOC_H_TYPES 3e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 4e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/* 5e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * RUN_MAX_OVRHD indicates maximum desired run header overhead. Runs are sized 6e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * as small as possible such that this setting is still honored, without 7e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * violating other constraints. The goal is to make runs as small as possible 8e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * without exceeding a per run external fragmentation threshold. 9e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 10e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * We use binary fixed point math for overhead computations, where the binary 11e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * point is implicitly RUN_BFP bits to the left. 12e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 13e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Note that it is possible to set RUN_MAX_OVRHD low enough that it cannot be 148ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * honored for some/all object sizes, since when heap profiling is enabled 158ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * there is one pointer of header overhead per object (plus a constant). This 168ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * constraint is relaxed (ignored) for runs that are so small that the 178ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * per-region overhead is greater than: 18e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 19e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * (RUN_MAX_OVRHD / (reg_size << (3+RUN_BFP)) 20e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 21e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#define RUN_BFP 12 22e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/* \/ Implicit binary fixed point. */ 23e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#define RUN_MAX_OVRHD 0x0000003dU 24e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#define RUN_MAX_OVRHD_RELAX 0x00001800U 25e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 2647e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans/* Maximum number of regions in one run. */ 2747e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans#define LG_RUN_MAXREGS 11 2847e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans#define RUN_MAXREGS (1U << LG_RUN_MAXREGS) 2947e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans 30e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/* 31e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * The minimum ratio of active:dirty pages per arena is computed as: 32e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 33e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * (nactive >> opt_lg_dirty_mult) >= ndirty 34e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 35e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * So, supposing that opt_lg_dirty_mult is 5, there can be no less than 32 36e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * times as many active pages as dirty pages. 37e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 38e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#define LG_DIRTY_MULT_DEFAULT 5 39e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 40e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef struct arena_chunk_map_s arena_chunk_map_t; 41e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef struct arena_chunk_s arena_chunk_t; 42e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef struct arena_run_s arena_run_t; 4349f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evanstypedef struct arena_bin_info_s arena_bin_info_t; 44e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef struct arena_bin_s arena_bin_t; 45e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef struct arena_s arena_t; 46e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 47e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif /* JEMALLOC_H_TYPES */ 48e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/******************************************************************************/ 49e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#ifdef JEMALLOC_H_STRUCTS 50e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 51e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/* Each element of the chunk map corresponds to one page within the chunk. */ 52e476f8a161d445211fd6e54fe370275196e66bcbJason Evansstruct arena_chunk_map_s { 537372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans#ifndef JEMALLOC_PROF 547372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans /* 557372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans * Overlay prof_ctx in order to allow it to be referenced by dead code. 567372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans * Such antics aren't warranted for per arena data structures, but 577372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans * chunk map overhead accounts for a percentage of memory, rather than 587372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans * being just a fixed cost. 597372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans */ 607372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans union { 617372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans#endif 6205b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans union { 6305b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans /* 6405b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * Linkage for run trees. There are two disjoint uses: 6505b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * 6619b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * 1) arena_t's runs_avail_{clean,dirty} trees. 6705b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * 2) arena_run_t conceptually uses this linkage for in-use 6805b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * non-full runs, rather than directly embedding linkage. 6905b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans */ 7005b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans rb_node(arena_chunk_map_t) rb_link; 7105b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans /* 7205b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * List of runs currently in purgatory. arena_chunk_purge() 7305b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * temporarily allocates runs that contain dirty pages while 7405b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * purging, so that other threads cannot use the runs while the 7505b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans * purging thread is operating without the arena lock held. 7605b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans */ 7705b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans ql_elm(arena_chunk_map_t) ql_link; 7805b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans } u; 79e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 806109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Profile counters, used for large object runs. */ 815065156f3f90e421ba2b1a914e47eeb30d83d994Jason Evans prof_ctx_t *prof_ctx; 827372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans#ifndef JEMALLOC_PROF 837372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans }; /* union { ... }; */ 846109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 856109fe07a14b7a619365977d9523db9f8b333792Jason Evans 86e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 87e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Run address (or size) and various flags are stored together. The bit 88e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * layout looks like (assuming 32-bit system): 89e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 908ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ???????? ???????? ????---- ----dula 91e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 92e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * ? : Unallocated: Run address for first/last pages, unset for internal 93e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * pages. 9419b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * Small: Run page offset. 95e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Large: Run size for first page, unset for trailing pages. 96e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * - : Unused. 97e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * d : dirty? 988ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * u : unzeroed? 99e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * l : large? 100e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * a : allocated? 101e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 102e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Following are example bit patterns for the three types of runs. 103e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 104e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * p : run page offset 105e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * s : run size 106e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans * c : (binind+1) for size class (used only if prof_promote is true) 107e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * x : don't care 108e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * - : 0 1090b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans * + : 1 1103377ffa1f4f8e67bce1e36624285e5baf5f9ecefJason Evans * [DULA] : bit set 1113377ffa1f4f8e67bce1e36624285e5baf5f9ecefJason Evans * [dula] : bit unset 112e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 11319b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * Unallocated (clean): 1148ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----du-a 1153377ffa1f4f8e67bce1e36624285e5baf5f9ecefJason Evans * xxxxxxxx xxxxxxxx xxxx---- -----Uxx 1168ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----dU-a 11719b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * 11819b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * Unallocated (dirty): 1198ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----D--a 12019b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * xxxxxxxx xxxxxxxx xxxx---- ----xxxx 1218ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----D--a 122e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 123dafde14e08ddfda747aabb2045b350848b601b2eJason Evans * Small: 1248ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * pppppppp pppppppp pppp---- ----d--A 1258ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * pppppppp pppppppp pppp---- -------A 1268ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * pppppppp pppppppp pppp---- ----d--A 127e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 128e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Large: 1298ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----D-LA 13019b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * xxxxxxxx xxxxxxxx xxxx---- ----xxxx 1318ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * -------- -------- -------- ----D-LA 1320b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans * 1330b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans * Large (sampled, size <= PAGE_SIZE): 1348ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss sssscccc ccccD-LA 1350b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans * 1360b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans * Large (not sampled, size == PAGE_SIZE): 1378ad0eacfb351af990ae021f219b7b88d70aede41Jason Evans * ssssssss ssssssss ssss---- ----D-LA 138e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 139e476f8a161d445211fd6e54fe370275196e66bcbJason Evans size_t bits; 1400b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_CLASS_SHIFT 4 1410b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_CLASS_MASK ((size_t)0xff0U) 1420b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_FLAGS_MASK ((size_t)0xfU) 1430b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_DIRTY ((size_t)0x8U) 1443377ffa1f4f8e67bce1e36624285e5baf5f9ecefJason Evans#define CHUNK_MAP_UNZEROED ((size_t)0x4U) 1450b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_LARGE ((size_t)0x2U) 1460b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_ALLOCATED ((size_t)0x1U) 1470b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evans#define CHUNK_MAP_KEY CHUNK_MAP_ALLOCATED 148e476f8a161d445211fd6e54fe370275196e66bcbJason Evans}; 149e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef rb_tree(arena_chunk_map_t) arena_avail_tree_t; 150e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef rb_tree(arena_chunk_map_t) arena_run_tree_t; 151e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 152e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/* Arena chunk header. */ 153e476f8a161d445211fd6e54fe370275196e66bcbJason Evansstruct arena_chunk_s { 154e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Arena that owns the chunk. */ 155e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_t *arena; 156e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 1572caa4715ed4f787f263239ff97dd824636289286Jason Evans /* Linkage for the arena's chunks_dirty list. */ 1582caa4715ed4f787f263239ff97dd824636289286Jason Evans ql_elm(arena_chunk_t) link_dirty; 159e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 160e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 1612caa4715ed4f787f263239ff97dd824636289286Jason Evans * True if the chunk is currently in the chunks_dirty list, due to 162e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * having at some point contained one or more dirty pages. Removal 163e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * from chunks_dirty is lazy, so (dirtied && ndirty == 0) is possible. 164e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 165e476f8a161d445211fd6e54fe370275196e66bcbJason Evans bool dirtied; 166e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 167e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Number of dirty pages. */ 168e476f8a161d445211fd6e54fe370275196e66bcbJason Evans size_t ndirty; 16913668262d17fb5950e2441bc9d56a15db9c93877Jason Evans 1707393f44ff025ca67716fc53b68003fd65122fd97Jason Evans /* 1717393f44ff025ca67716fc53b68003fd65122fd97Jason Evans * Map of pages within chunk that keeps track of free/large/small. The 1727393f44ff025ca67716fc53b68003fd65122fd97Jason Evans * first map_bias entries are omitted, since the chunk header does not 1737393f44ff025ca67716fc53b68003fd65122fd97Jason Evans * need to be tracked in the map. This omission saves a header page 1747393f44ff025ca67716fc53b68003fd65122fd97Jason Evans * for common chunk sizes (e.g. 4 MiB). 1757393f44ff025ca67716fc53b68003fd65122fd97Jason Evans */ 176e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_chunk_map_t map[1]; /* Dynamically sized. */ 177e476f8a161d445211fd6e54fe370275196e66bcbJason Evans}; 178e476f8a161d445211fd6e54fe370275196e66bcbJason Evanstypedef rb_tree(arena_chunk_t) arena_chunk_tree_t; 179e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 180e476f8a161d445211fd6e54fe370275196e66bcbJason Evansstruct arena_run_s { 181e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Bin this run is associated with. */ 182e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_bin_t *bin; 183e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 18484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* Index of next region that has never been allocated, or nregs. */ 18584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans uint32_t nextind; 186e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 187e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Number of free regions in run. */ 188e476f8a161d445211fd6e54fe370275196e66bcbJason Evans unsigned nfree; 189e476f8a161d445211fd6e54fe370275196e66bcbJason Evans}; 190e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 19149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans/* 19284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Read-only information associated with each element of arena_t's bins array 19349f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans * is stored separately, partly to reduce memory usage (only one copy, rather 19449f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans * than one per arena), but mainly to avoid false cacheline sharing. 19549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans */ 19649f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evansstruct arena_bin_info_s { 19749f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans /* Size of regions in a run for this bin's size class. */ 19849f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t reg_size; 19949f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 20049f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans /* Total size of a run for this bin's size class. */ 20149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t run_size; 20249f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 20349f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans /* Total number of regions in a run for this bin's size class. */ 20449f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans uint32_t nregs; 20549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 20684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* 20784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Offset of first bitmap_t element in a run header for this bin's size 20884c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * class. 20984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans */ 21084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans uint32_t bitmap_offset; 21184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 21284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* 21384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Metadata used to manipulate bitmaps for runs associated with this 21484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * bin. 21584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans */ 21684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans bitmap_info_t bitmap_info; 21784c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans 21849f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans /* 21949f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans * Offset of first (prof_ctx_t *) in a run header for this bin's size 2207372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans * class, or 0 if (config_prof == false || opt_prof == false). 22149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans */ 22249f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans uint32_t ctx0_offset; 22349f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 22449f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans /* Offset of first region in a run for this bin's size class. */ 22549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans uint32_t reg0_offset; 22649f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans}; 22749f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 228e476f8a161d445211fd6e54fe370275196e66bcbJason Evansstruct arena_bin_s { 229e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 23086815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans * All operations on runcur, runs, and stats require that lock be 23186815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans * locked. Run allocation/deallocation are protected by the arena lock, 23286815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans * which may be acquired while holding one or more bin locks, but not 23386815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans * vise versa. 23486815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans */ 23586815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans malloc_mutex_t lock; 23686815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans 23786815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans /* 238e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Current run being used to service allocations of this bin's size 239e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * class. 240e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 241e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_run_t *runcur; 242e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 243e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 244e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Tree of non-full runs. This tree is used when looking for an 245e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * existing run when runcur is no longer usable. We choose the 246e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * non-full run that is lowest in memory; this policy tends to keep 247e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * objects packed well, and it can also help reduce the number of 248e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * almost-empty chunks. 249e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 250e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_run_tree_t runs; 251e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 252e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Bin statistics. */ 253e476f8a161d445211fd6e54fe370275196e66bcbJason Evans malloc_bin_stats_t stats; 254e476f8a161d445211fd6e54fe370275196e66bcbJason Evans}; 255e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 256e476f8a161d445211fd6e54fe370275196e66bcbJason Evansstruct arena_s { 2576109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* This arena's index within the arenas array. */ 2586109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned ind; 2596109fe07a14b7a619365977d9523db9f8b333792Jason Evans 26086815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans /* 261597632be188d2bcc135dad2145cc46ef44897aadJason Evans * Number of threads currently assigned to this arena. This field is 262597632be188d2bcc135dad2145cc46ef44897aadJason Evans * protected by arenas_lock. 263597632be188d2bcc135dad2145cc46ef44897aadJason Evans */ 264597632be188d2bcc135dad2145cc46ef44897aadJason Evans unsigned nthreads; 265597632be188d2bcc135dad2145cc46ef44897aadJason Evans 266597632be188d2bcc135dad2145cc46ef44897aadJason Evans /* 267597632be188d2bcc135dad2145cc46ef44897aadJason Evans * There are three classes of arena operations from a locking 268597632be188d2bcc135dad2145cc46ef44897aadJason Evans * perspective: 269597632be188d2bcc135dad2145cc46ef44897aadJason Evans * 1) Thread asssignment (modifies nthreads) is protected by 270597632be188d2bcc135dad2145cc46ef44897aadJason Evans * arenas_lock. 271597632be188d2bcc135dad2145cc46ef44897aadJason Evans * 2) Bin-related operations are protected by bin locks. 272597632be188d2bcc135dad2145cc46ef44897aadJason Evans * 3) Chunk- and run-related operations are protected by this mutex. 27386815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans */ 274e476f8a161d445211fd6e54fe370275196e66bcbJason Evans malloc_mutex_t lock; 275e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 276e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_stats_t stats; 277e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 278e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * List of tcaches for extant threads associated with this arena. 279e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Stats from these are merged incrementally, and at exit. 280e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 281e476f8a161d445211fd6e54fe370275196e66bcbJason Evans ql_head(tcache_t) tcache_ql; 282e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 283d34f9e7e9306698e298a703c28526cd6bfc073ecJason Evans uint64_t prof_accumbytes; 284d34f9e7e9306698e298a703c28526cd6bfc073ecJason Evans 2852caa4715ed4f787f263239ff97dd824636289286Jason Evans /* List of dirty-page-containing chunks this arena manages. */ 2862caa4715ed4f787f263239ff97dd824636289286Jason Evans ql_head(arena_chunk_t) chunks_dirty; 287e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 288e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 289e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * In order to avoid rapid chunk allocation/deallocation when an arena 290e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * oscillates right on the cusp of needing a new chunk, cache the most 291e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * recently freed chunk. The spare is left in the arena's chunk trees 292e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * until it is deleted. 293e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * 294e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * There is one spare chunk per arena, rather than one spare total, in 295e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * order to avoid interactions between multiple threads that could make 296e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * a single spare inadequate. 297e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 298e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_chunk_t *spare; 299e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 300e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Number of pages in active runs. */ 301bc25a47ee0e2ac8e10a94d5fa070f0dbbdeb7e7eJason Evans size_t nactive; 302e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 303e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 304e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * Current count of pages within unused runs that are potentially 305e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * dirty, and for which madvise(... MADV_DONTNEED) has not been called. 306e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * By tracking this, we can institute a limit on how much dirty unused 307e476f8a161d445211fd6e54fe370275196e66bcbJason Evans * memory is mapped for each arena. 308e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 309e476f8a161d445211fd6e54fe370275196e66bcbJason Evans size_t ndirty; 310e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 311e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* 312799ca0b68dd2a87eb7696b7a83ed85378cc6721cJason Evans * Approximate number of pages being purged. It is possible for 313799ca0b68dd2a87eb7696b7a83ed85378cc6721cJason Evans * multiple threads to purge dirty pages concurrently, and they use 314799ca0b68dd2a87eb7696b7a83ed85378cc6721cJason Evans * npurgatory to indicate the total number of pages all threads are 315799ca0b68dd2a87eb7696b7a83ed85378cc6721cJason Evans * attempting to purge. 31605b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans */ 317799ca0b68dd2a87eb7696b7a83ed85378cc6721cJason Evans size_t npurgatory; 31805b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans 31905b21be347d66b4afd5147ecd26e8cb22f6ea3feJason Evans /* 32019b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * Size/address-ordered trees of this arena's available runs. The trees 32119b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * are used for first-best-fit run allocation. The dirty tree contains 32219b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * runs with dirty pages (i.e. very likely to have been touched and 32319b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * therefore have associated physical pages), whereas the clean tree 32419b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * contains runs with pages that either have no associated physical 32519b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * pages, or have pages that the kernel may recycle at any time due to 32619b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * previous madvise(2) calls. The dirty tree is used in preference to 32719b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * the clean tree for allocations, because using dirty pages reduces 32819b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * the amount of dirty purging necessary to keep the active:dirty page 32919b3d618924b3542a264612f906bc53bbcec8b70Jason Evans * ratio below the purge threshold. 330e476f8a161d445211fd6e54fe370275196e66bcbJason Evans */ 33119b3d618924b3542a264612f906bc53bbcec8b70Jason Evans arena_avail_tree_t runs_avail_clean; 33219b3d618924b3542a264612f906bc53bbcec8b70Jason Evans arena_avail_tree_t runs_avail_dirty; 333e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 334b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evans /* bins is used to store trees of free regions. */ 335b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evans arena_bin_t bins[NBINS]; 336e476f8a161d445211fd6e54fe370275196e66bcbJason Evans}; 337e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 338e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif /* JEMALLOC_H_STRUCTS */ 339e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/******************************************************************************/ 340e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#ifdef JEMALLOC_H_EXTERNS 341e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 34284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evansextern ssize_t opt_lg_dirty_mult; 34341ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans/* 34441ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans * small_size2bin is a compact lookup table that rounds request sizes up to 34541ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans * size classes. In order to reduce cache footprint, the table is compressed, 34641ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans * and all accesses are via the SMALL_SIZE2BIN macro. 34741ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans */ 348b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evansextern uint8_t const small_size2bin[]; 34941ade967c29ea9312c0b7390ee43bc0c63373f39Jason Evans#define SMALL_SIZE2BIN(s) (small_size2bin[(s-1) >> LG_TINY_MIN]) 350e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 351b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evansextern arena_bin_info_t arena_bin_info[NBINS]; 352e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 353b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evans/* Number of large size classes. */ 3547393f44ff025ca67716fc53b68003fd65122fd97Jason Evans#define nlclasses (chunk_npages - map_bias) 3553c2343518c2b1fbbd66065c75a3c19f908de1d78Jason Evans 3566005f0710cf07d60659d91b20b7ff5592d310027Jason Evansvoid arena_purge_all(arena_t *arena); 3576005f0710cf07d60659d91b20b7ff5592d310027Jason Evansvoid arena_prof_accum(arena_t *arena, uint64_t accumbytes); 358dafde14e08ddfda747aabb2045b350848b601b2eJason Evansvoid arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, 3597372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans size_t binind, uint64_t prof_accumbytes); 360e476f8a161d445211fd6e54fe370275196e66bcbJason Evansvoid *arena_malloc_small(arena_t *arena, size_t size, bool zero); 361dafde14e08ddfda747aabb2045b350848b601b2eJason Evansvoid *arena_malloc_large(arena_t *arena, size_t size, bool zero); 3628e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evansvoid *arena_palloc(arena_t *arena, size_t size, size_t alloc_size, 3638e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans size_t alignment, bool zero); 364e476f8a161d445211fd6e54fe370275196e66bcbJason Evanssize_t arena_salloc(const void *ptr); 3650b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evansvoid arena_prof_promoted(const void *ptr, size_t size); 3660b270a991dd7822b7c7e13d9219f235a5dde9fdfJason Evanssize_t arena_salloc_demote(const void *ptr); 367e476f8a161d445211fd6e54fe370275196e66bcbJason Evansvoid arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr, 368e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_chunk_map_t *mapelm); 369e476f8a161d445211fd6e54fe370275196e66bcbJason Evansvoid arena_dalloc_large(arena_t *arena, arena_chunk_t *chunk, void *ptr); 370b34e8684ec025aa780997c11f847c19fb269755bJason Evansvoid arena_stats_merge(arena_t *arena, size_t *nactive, size_t *ndirty, 371b34e8684ec025aa780997c11f847c19fb269755bJason Evans arena_stats_t *astats, malloc_bin_stats_t *bstats, 372b34e8684ec025aa780997c11f847c19fb269755bJason Evans malloc_large_stats_t *lstats); 3738e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evansvoid *arena_ralloc_no_move(void *ptr, size_t oldsize, size_t size, 3748e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans size_t extra, bool zero); 3758e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evansvoid *arena_ralloc(void *ptr, size_t oldsize, size_t size, size_t extra, 3768e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans size_t alignment, bool zero); 377e476f8a161d445211fd6e54fe370275196e66bcbJason Evansbool arena_new(arena_t *arena, unsigned ind); 378b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evansvoid arena_boot(void); 379e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 380e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif /* JEMALLOC_H_EXTERNS */ 381e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/******************************************************************************/ 382e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#ifdef JEMALLOC_H_INLINES 383e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 384e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#ifndef JEMALLOC_ENABLE_INLINE 38549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evanssize_t arena_bin_index(arena_t *arena, arena_bin_t *bin); 38649f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evansunsigned arena_run_regind(arena_run_t *run, arena_bin_info_t *bin_info, 387b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans const void *ptr); 38881b4e6eb6f06cac048e3743787a70676f1534269Jason Evansprof_ctx_t *arena_prof_ctx_get(const void *ptr); 389e4f7846f1fd279a039ffa2a41707348187219de4Jason Evansvoid arena_prof_ctx_set(const void *ptr, prof_ctx_t *ctx); 390962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evansvoid *arena_malloc(size_t size, bool zero); 391e476f8a161d445211fd6e54fe370275196e66bcbJason Evansvoid arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr); 392e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif 393e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 394e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_ARENA_C_)) 39549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason EvansJEMALLOC_INLINE size_t 39649f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evansarena_bin_index(arena_t *arena, arena_bin_t *bin) 39749f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans{ 39849f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t binind = bin - arena->bins; 399b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evans assert(binind < NBINS); 40049f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans return (binind); 40149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans} 40249f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans 40381b4e6eb6f06cac048e3743787a70676f1534269Jason EvansJEMALLOC_INLINE unsigned 404b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evansarena_run_regind(arena_run_t *run, arena_bin_info_t *bin_info, const void *ptr) 40581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans{ 40681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans unsigned shift, diff, regind; 407b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans size_t size; 40881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 40984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans /* 41084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * Freeing a pointer lower than region zero can cause assertion 41184c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans * failure. 41284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans */ 41384c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans assert((uintptr_t)ptr >= (uintptr_t)run + 41484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans (uintptr_t)bin_info->reg0_offset); 41581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 41681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans /* 41781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * Avoid doing division with a variable divisor if possible. Using 41881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * actual division here can reduce allocator throughput by over 20%! 41981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans */ 42049f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - 42149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans bin_info->reg0_offset); 42281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 42381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans /* Rescale (factor powers of 2 out of the numerator and denominator). */ 424b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans size = bin_info->reg_size; 42581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans shift = ffs(size) - 1; 42681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans diff >>= shift; 42781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans size >>= shift; 42881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 42981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans if (size == 1) { 43081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans /* The divisor was a power of 2. */ 43181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans regind = diff; 43281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans } else { 43381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans /* 43481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * To divide by a number D that is not a power of two we 43581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * multiply by (2^21 / D) and then right shift by 21 positions. 43681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * 43781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * X / D 43881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * 43981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * becomes 44081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * 44181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * (X * size_invs[D - 3]) >> SIZE_INV_SHIFT 44281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * 44381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * We can omit the first three elements, because we never 44481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * divide by 0, and 1 and 2 are both powers of two, which are 44581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans * handled above. 44681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans */ 44747e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans#define SIZE_INV_SHIFT ((sizeof(unsigned) << 3) - LG_RUN_MAXREGS) 44847e57f9bdadfaf999c9dea5d126edf3a4f1b2995Jason Evans#define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s)) + 1) 44981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans static const unsigned size_invs[] = { 45081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(3), 45181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7), 45281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11), 45381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(12), SIZE_INV(13), SIZE_INV(14), SIZE_INV(15), 45481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(16), SIZE_INV(17), SIZE_INV(18), SIZE_INV(19), 45581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(20), SIZE_INV(21), SIZE_INV(22), SIZE_INV(23), 45681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(24), SIZE_INV(25), SIZE_INV(26), SIZE_INV(27), 45781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans SIZE_INV(28), SIZE_INV(29), SIZE_INV(30), SIZE_INV(31) 45881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans }; 45981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 46081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans if (size <= ((sizeof(size_invs) / sizeof(unsigned)) + 2)) 46181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans regind = (diff * size_invs[size - 3]) >> SIZE_INV_SHIFT; 46281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans else 46381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans regind = diff / size; 46481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans#undef SIZE_INV 46581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans#undef SIZE_INV_SHIFT 46681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans } 46781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans assert(diff == regind * size); 46849f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans assert(regind < bin_info->nregs); 46981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 47081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans return (regind); 47181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans} 47281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 47381b4e6eb6f06cac048e3743787a70676f1534269Jason EvansJEMALLOC_INLINE prof_ctx_t * 47481b4e6eb6f06cac048e3743787a70676f1534269Jason Evansarena_prof_ctx_get(const void *ptr) 47581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans{ 47681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans prof_ctx_t *ret; 47781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans arena_chunk_t *chunk; 47881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans size_t pageind, mapbits; 47981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 4807372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans cassert(config_prof); 48181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans assert(ptr != NULL); 48281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans assert(CHUNK_ADDR2BASE(ptr) != ptr); 48381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 48481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 48581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 48681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans mapbits = chunk->map[pageind-map_bias].bits; 48781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); 48881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans if ((mapbits & CHUNK_MAP_LARGE) == 0) { 48981b4e6eb6f06cac048e3743787a70676f1534269Jason Evans if (prof_promote) 49081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans ret = (prof_ctx_t *)(uintptr_t)1U; 49181b4e6eb6f06cac048e3743787a70676f1534269Jason Evans else { 49281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + 49381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) << 49481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans PAGE_SHIFT)); 49549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t binind = arena_bin_index(chunk->arena, run->bin); 49649f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans arena_bin_info_t *bin_info = &arena_bin_info[binind]; 49781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans unsigned regind; 49881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 499b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans regind = arena_run_regind(run, bin_info, ptr); 50081b4e6eb6f06cac048e3743787a70676f1534269Jason Evans ret = *(prof_ctx_t **)((uintptr_t)run + 50149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans bin_info->ctx0_offset + (regind * 50281b4e6eb6f06cac048e3743787a70676f1534269Jason Evans sizeof(prof_ctx_t *))); 50381b4e6eb6f06cac048e3743787a70676f1534269Jason Evans } 50481b4e6eb6f06cac048e3743787a70676f1534269Jason Evans } else 50581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans ret = chunk->map[pageind-map_bias].prof_ctx; 50681b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 50781b4e6eb6f06cac048e3743787a70676f1534269Jason Evans return (ret); 50881b4e6eb6f06cac048e3743787a70676f1534269Jason Evans} 509e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans 510e4f7846f1fd279a039ffa2a41707348187219de4Jason EvansJEMALLOC_INLINE void 511e4f7846f1fd279a039ffa2a41707348187219de4Jason Evansarena_prof_ctx_set(const void *ptr, prof_ctx_t *ctx) 512e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans{ 513e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans arena_chunk_t *chunk; 514e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans size_t pageind, mapbits; 515e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans 5167372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans cassert(config_prof); 517e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans assert(ptr != NULL); 518e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans assert(CHUNK_ADDR2BASE(ptr) != ptr); 519e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans 520e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 521e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 522e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans mapbits = chunk->map[pageind-map_bias].bits; 523e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans assert((mapbits & CHUNK_MAP_ALLOCATED) != 0); 524e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans if ((mapbits & CHUNK_MAP_LARGE) == 0) { 525e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans if (prof_promote == false) { 526e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans arena_run_t *run = (arena_run_t *)((uintptr_t)chunk + 527e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans (uintptr_t)((pageind - (mapbits >> PAGE_SHIFT)) << 528e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans PAGE_SHIFT)); 529e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans arena_bin_t *bin = run->bin; 53049f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t binind; 53149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans arena_bin_info_t *bin_info; 532b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans unsigned regind; 533e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans 53449f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans binind = arena_bin_index(chunk->arena, bin); 53549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans bin_info = &arena_bin_info[binind]; 536b602daa6710dab61d8e1ca0cd3c44ac8a564fd9fJason Evans regind = arena_run_regind(run, bin_info, ptr); 537e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans 53849f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans *((prof_ctx_t **)((uintptr_t)run + bin_info->ctx0_offset 539e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans + (regind * sizeof(prof_ctx_t *)))) = ctx; 540e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans } else 541e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans assert((uintptr_t)ctx == (uintptr_t)1U); 542e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans } else 543e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans chunk->map[pageind-map_bias].prof_ctx = ctx; 544e4f7846f1fd279a039ffa2a41707348187219de4Jason Evans} 54581b4e6eb6f06cac048e3743787a70676f1534269Jason Evans 546962463d9b57bcc65de2fa108a691b4183b9b2fafJason EvansJEMALLOC_INLINE void * 547962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evansarena_malloc(size_t size, bool zero) 548962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans{ 549ef8897b4b938111fcc9b54725067f1dbb33a4c20Jason Evans tcache_t *tcache; 550962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans 551962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans assert(size != 0); 552962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans assert(QUANTUM_CEILING(size) <= arena_maxclass); 553962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans 554b172610317babc7f365584ddd7fdaf4eb8d9d04cJason Evans if (size <= SMALL_MAXCLASS) { 555ef8897b4b938111fcc9b54725067f1dbb33a4c20Jason Evans if ((tcache = tcache_get()) != NULL) 556962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans return (tcache_alloc_small(tcache, size, zero)); 557962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans else 558962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans return (arena_malloc_small(choose_arena(), size, zero)); 559962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans } else { 560746868929afae3e346b47d0fa8a78d7fb131d5a4Jason Evans /* 561746868929afae3e346b47d0fa8a78d7fb131d5a4Jason Evans * Initialize tcache after checking size in order to avoid 562746868929afae3e346b47d0fa8a78d7fb131d5a4Jason Evans * infinite recursion during tcache initialization. 563746868929afae3e346b47d0fa8a78d7fb131d5a4Jason Evans */ 564ef8897b4b938111fcc9b54725067f1dbb33a4c20Jason Evans if (size <= tcache_maxclass && (tcache = tcache_get()) != NULL) 565962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans return (tcache_alloc_large(tcache, size, zero)); 566962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans else 567962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans return (arena_malloc_large(choose_arena(), size, zero)); 568962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans } 569962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans} 570962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans 571e476f8a161d445211fd6e54fe370275196e66bcbJason EvansJEMALLOC_INLINE void 572e476f8a161d445211fd6e54fe370275196e66bcbJason Evansarena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr) 573e476f8a161d445211fd6e54fe370275196e66bcbJason Evans{ 574e476f8a161d445211fd6e54fe370275196e66bcbJason Evans size_t pageind; 575e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_chunk_map_t *mapelm; 576962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans tcache_t *tcache = tcache_get(); 577e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 578e476f8a161d445211fd6e54fe370275196e66bcbJason Evans assert(arena != NULL); 579e476f8a161d445211fd6e54fe370275196e66bcbJason Evans assert(chunk->arena == arena); 580e476f8a161d445211fd6e54fe370275196e66bcbJason Evans assert(ptr != NULL); 581e476f8a161d445211fd6e54fe370275196e66bcbJason Evans assert(CHUNK_ADDR2BASE(ptr) != ptr); 582e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 5837393f44ff025ca67716fc53b68003fd65122fd97Jason Evans pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> PAGE_SHIFT; 5847393f44ff025ca67716fc53b68003fd65122fd97Jason Evans mapelm = &chunk->map[pageind-map_bias]; 585e476f8a161d445211fd6e54fe370275196e66bcbJason Evans assert((mapelm->bits & CHUNK_MAP_ALLOCATED) != 0); 586e476f8a161d445211fd6e54fe370275196e66bcbJason Evans if ((mapelm->bits & CHUNK_MAP_LARGE) == 0) { 587e476f8a161d445211fd6e54fe370275196e66bcbJason Evans /* Small allocation. */ 588962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans if (tcache != NULL) 589dafde14e08ddfda747aabb2045b350848b601b2eJason Evans tcache_dalloc_small(tcache, ptr); 590e476f8a161d445211fd6e54fe370275196e66bcbJason Evans else { 59186815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans arena_run_t *run; 59286815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans arena_bin_t *bin; 59386815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans 59486815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans run = (arena_run_t *)((uintptr_t)chunk + 59519b3d618924b3542a264612f906bc53bbcec8b70Jason Evans (uintptr_t)((pageind - (mapelm->bits >> 59619b3d618924b3542a264612f906bc53bbcec8b70Jason Evans PAGE_SHIFT)) << PAGE_SHIFT)); 59786815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans bin = run->bin; 5987372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans if (config_debug) { 59949f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans size_t binind = arena_bin_index(arena, bin); 6007372b15a31c63ac5cb9ed8aeabc2a0a3c005e8bfJason Evans UNUSED arena_bin_info_t *bin_info = 60149f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans &arena_bin_info[binind]; 60249f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans assert(((uintptr_t)ptr - ((uintptr_t)run + 60349f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans (uintptr_t)bin_info->reg0_offset)) % 60449f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans bin_info->reg_size == 0); 60549f7e8f35ac63d0dd526cf68791dc0ca29538ac9Jason Evans } 60686815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans malloc_mutex_lock(&bin->lock); 607e476f8a161d445211fd6e54fe370275196e66bcbJason Evans arena_dalloc_bin(arena, chunk, ptr, mapelm); 60886815df9dc7d2418a21c87b3dc9747ab42dea73dJason Evans malloc_mutex_unlock(&bin->lock); 609e476f8a161d445211fd6e54fe370275196e66bcbJason Evans } 610f00bb7f132e3b74cb36c34223217df0c4394ada4Jason Evans } else { 611962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans size_t size = mapelm->bits & ~PAGE_MASK; 612962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans 613962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans assert(((uintptr_t)ptr & PAGE_MASK) == 0); 614962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans 615962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans if (size <= tcache_maxclass && tcache != NULL) { 616962463d9b57bcc65de2fa108a691b4183b9b2fafJason Evans tcache_dalloc_large(tcache, ptr, size); 617dafde14e08ddfda747aabb2045b350848b601b2eJason Evans } else { 618dafde14e08ddfda747aabb2045b350848b601b2eJason Evans malloc_mutex_lock(&arena->lock); 619dafde14e08ddfda747aabb2045b350848b601b2eJason Evans arena_dalloc_large(arena, chunk, ptr); 620dafde14e08ddfda747aabb2045b350848b601b2eJason Evans malloc_mutex_unlock(&arena->lock); 621dafde14e08ddfda747aabb2045b350848b601b2eJason Evans } 622f00bb7f132e3b74cb36c34223217df0c4394ada4Jason Evans } 623e476f8a161d445211fd6e54fe370275196e66bcbJason Evans} 624e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif 625e476f8a161d445211fd6e54fe370275196e66bcbJason Evans 626e476f8a161d445211fd6e54fe370275196e66bcbJason Evans#endif /* JEMALLOC_H_INLINES */ 627e476f8a161d445211fd6e54fe370275196e66bcbJason Evans/******************************************************************************/ 628