Changeset View
Changeset View
Standalone View
Standalone View
head/contrib/jemalloc/include/jemalloc/internal/sz.h
#ifndef JEMALLOC_INTERNAL_SIZE_H | #ifndef JEMALLOC_INTERNAL_SIZE_H | ||||
#define JEMALLOC_INTERNAL_SIZE_H | #define JEMALLOC_INTERNAL_SIZE_H | ||||
#include "jemalloc/internal/bit_util.h" | #include "jemalloc/internal/bit_util.h" | ||||
#include "jemalloc/internal/pages.h" | #include "jemalloc/internal/pages.h" | ||||
#include "jemalloc/internal/size_classes.h" | #include "jemalloc/internal/sc.h" | ||||
#include "jemalloc/internal/util.h" | #include "jemalloc/internal/util.h" | ||||
/* | /* | ||||
* sz module: Size computations. | * sz module: Size computations. | ||||
* | * | ||||
* Some abbreviations used here: | * Some abbreviations used here: | ||||
* p: Page | * p: Page | ||||
* ind: Index | * ind: Index | ||||
* s, sz: Size | * s, sz: Size | ||||
* u: Usable size | * u: Usable size | ||||
* a: Aligned | * a: Aligned | ||||
* | * | ||||
* These are not always used completely consistently, but should be enough to | * These are not always used completely consistently, but should be enough to | ||||
* interpret function names. E.g. sz_psz2ind converts page size to page size | * interpret function names. E.g. sz_psz2ind converts page size to page size | ||||
* index; sz_sa2u converts a (size, alignment) allocation request to the usable | * index; sz_sa2u converts a (size, alignment) allocation request to the usable | ||||
* size that would result from such an allocation. | * size that would result from such an allocation. | ||||
*/ | */ | ||||
/* | /* | ||||
* sz_pind2sz_tab encodes the same information as could be computed by | * sz_pind2sz_tab encodes the same information as could be computed by | ||||
* sz_pind2sz_compute(). | * sz_pind2sz_compute(). | ||||
*/ | */ | ||||
extern size_t const sz_pind2sz_tab[NPSIZES+1]; | extern size_t sz_pind2sz_tab[SC_NPSIZES + 1]; | ||||
/* | /* | ||||
* sz_index2size_tab encodes the same information as could be computed (at | * sz_index2size_tab encodes the same information as could be computed (at | ||||
* unacceptable cost in some code paths) by sz_index2size_compute(). | * unacceptable cost in some code paths) by sz_index2size_compute(). | ||||
*/ | */ | ||||
extern size_t const sz_index2size_tab[NSIZES]; | extern size_t sz_index2size_tab[SC_NSIZES]; | ||||
/* | /* | ||||
* sz_size2index_tab is a compact lookup table that rounds request sizes up to | * sz_size2index_tab is a compact lookup table that rounds request sizes up to | ||||
* size classes. In order to reduce cache footprint, the table is compressed, | * size classes. In order to reduce cache footprint, the table is compressed, | ||||
* and all accesses are via sz_size2index(). | * and all accesses are via sz_size2index(). | ||||
*/ | */ | ||||
extern uint8_t const sz_size2index_tab[]; | extern uint8_t sz_size2index_tab[]; | ||||
static const size_t sz_large_pad = | static const size_t sz_large_pad = | ||||
#ifdef JEMALLOC_CACHE_OBLIVIOUS | #ifdef JEMALLOC_CACHE_OBLIVIOUS | ||||
PAGE | PAGE | ||||
#else | #else | ||||
0 | 0 | ||||
#endif | #endif | ||||
; | ; | ||||
extern void sz_boot(const sc_data_t *sc_data); | |||||
JEMALLOC_ALWAYS_INLINE pszind_t | JEMALLOC_ALWAYS_INLINE pszind_t | ||||
sz_psz2ind(size_t psz) { | sz_psz2ind(size_t psz) { | ||||
if (unlikely(psz > LARGE_MAXCLASS)) { | if (unlikely(psz > SC_LARGE_MAXCLASS)) { | ||||
return NPSIZES; | return SC_NPSIZES; | ||||
} | } | ||||
{ | |||||
pszind_t x = lg_floor((psz<<1)-1); | pszind_t x = lg_floor((psz<<1)-1); | ||||
pszind_t shift = (x < LG_SIZE_CLASS_GROUP + LG_PAGE) ? 0 : x - | pszind_t shift = (x < SC_LG_NGROUP + LG_PAGE) ? | ||||
(LG_SIZE_CLASS_GROUP + LG_PAGE); | 0 : x - (SC_LG_NGROUP + LG_PAGE); | ||||
pszind_t grp = shift << LG_SIZE_CLASS_GROUP; | pszind_t grp = shift << SC_LG_NGROUP; | ||||
pszind_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_PAGE + 1) ? | pszind_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ? | ||||
LG_PAGE : x - LG_SIZE_CLASS_GROUP - 1; | LG_PAGE : x - SC_LG_NGROUP - 1; | ||||
size_t delta_inverse_mask = ZU(-1) << lg_delta; | size_t delta_inverse_mask = ZU(-1) << lg_delta; | ||||
pszind_t mod = ((((psz-1) & delta_inverse_mask) >> lg_delta)) & | pszind_t mod = ((((psz-1) & delta_inverse_mask) >> lg_delta)) & | ||||
((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); | ((ZU(1) << SC_LG_NGROUP) - 1); | ||||
pszind_t ind = grp + mod; | pszind_t ind = grp + mod; | ||||
return ind; | return ind; | ||||
} | } | ||||
} | |||||
static inline size_t | static inline size_t | ||||
sz_pind2sz_compute(pszind_t pind) { | sz_pind2sz_compute(pszind_t pind) { | ||||
if (unlikely(pind == NPSIZES)) { | if (unlikely(pind == SC_NPSIZES)) { | ||||
return LARGE_MAXCLASS + PAGE; | return SC_LARGE_MAXCLASS + PAGE; | ||||
} | } | ||||
{ | size_t grp = pind >> SC_LG_NGROUP; | ||||
size_t grp = pind >> LG_SIZE_CLASS_GROUP; | size_t mod = pind & ((ZU(1) << SC_LG_NGROUP) - 1); | ||||
size_t mod = pind & ((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); | |||||
size_t grp_size_mask = ~((!!grp)-1); | size_t grp_size_mask = ~((!!grp)-1); | ||||
size_t grp_size = ((ZU(1) << (LG_PAGE + | size_t grp_size = ((ZU(1) << (LG_PAGE + (SC_LG_NGROUP-1))) << grp) | ||||
(LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask; | & grp_size_mask; | ||||
size_t shift = (grp == 0) ? 1 : grp; | size_t shift = (grp == 0) ? 1 : grp; | ||||
size_t lg_delta = shift + (LG_PAGE-1); | size_t lg_delta = shift + (LG_PAGE-1); | ||||
size_t mod_size = (mod+1) << lg_delta; | size_t mod_size = (mod+1) << lg_delta; | ||||
size_t sz = grp_size + mod_size; | size_t sz = grp_size + mod_size; | ||||
return sz; | return sz; | ||||
} | } | ||||
} | |||||
static inline size_t | static inline size_t | ||||
sz_pind2sz_lookup(pszind_t pind) { | sz_pind2sz_lookup(pszind_t pind) { | ||||
size_t ret = (size_t)sz_pind2sz_tab[pind]; | size_t ret = (size_t)sz_pind2sz_tab[pind]; | ||||
assert(ret == sz_pind2sz_compute(pind)); | assert(ret == sz_pind2sz_compute(pind)); | ||||
return ret; | return ret; | ||||
} | } | ||||
static inline size_t | static inline size_t | ||||
sz_pind2sz(pszind_t pind) { | sz_pind2sz(pszind_t pind) { | ||||
assert(pind < NPSIZES+1); | assert(pind < SC_NPSIZES + 1); | ||||
return sz_pind2sz_lookup(pind); | return sz_pind2sz_lookup(pind); | ||||
} | } | ||||
static inline size_t | static inline size_t | ||||
sz_psz2u(size_t psz) { | sz_psz2u(size_t psz) { | ||||
if (unlikely(psz > LARGE_MAXCLASS)) { | if (unlikely(psz > SC_LARGE_MAXCLASS)) { | ||||
return LARGE_MAXCLASS + PAGE; | return SC_LARGE_MAXCLASS + PAGE; | ||||
} | } | ||||
{ | |||||
size_t x = lg_floor((psz<<1)-1); | size_t x = lg_floor((psz<<1)-1); | ||||
size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_PAGE + 1) ? | size_t lg_delta = (x < SC_LG_NGROUP + LG_PAGE + 1) ? | ||||
LG_PAGE : x - LG_SIZE_CLASS_GROUP - 1; | LG_PAGE : x - SC_LG_NGROUP - 1; | ||||
size_t delta = ZU(1) << lg_delta; | size_t delta = ZU(1) << lg_delta; | ||||
size_t delta_mask = delta - 1; | size_t delta_mask = delta - 1; | ||||
size_t usize = (psz + delta_mask) & ~delta_mask; | size_t usize = (psz + delta_mask) & ~delta_mask; | ||||
return usize; | return usize; | ||||
} | } | ||||
} | |||||
static inline szind_t | static inline szind_t | ||||
sz_size2index_compute(size_t size) { | sz_size2index_compute(size_t size) { | ||||
if (unlikely(size > LARGE_MAXCLASS)) { | if (unlikely(size > SC_LARGE_MAXCLASS)) { | ||||
return NSIZES; | return SC_NSIZES; | ||||
} | } | ||||
#if (NTBINS != 0) | |||||
if (size <= (ZU(1) << LG_TINY_MAXCLASS)) { | if (size == 0) { | ||||
szind_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1; | return 0; | ||||
} | |||||
#if (SC_NTINY != 0) | |||||
if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) { | |||||
szind_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1; | |||||
szind_t lg_ceil = lg_floor(pow2_ceil_zu(size)); | szind_t lg_ceil = lg_floor(pow2_ceil_zu(size)); | ||||
return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin); | return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin); | ||||
} | } | ||||
#endif | #endif | ||||
{ | { | ||||
szind_t x = lg_floor((size<<1)-1); | szind_t x = lg_floor((size<<1)-1); | ||||
szind_t shift = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM) ? 0 : | szind_t shift = (x < SC_LG_NGROUP + LG_QUANTUM) ? 0 : | ||||
x - (LG_SIZE_CLASS_GROUP + LG_QUANTUM); | x - (SC_LG_NGROUP + LG_QUANTUM); | ||||
szind_t grp = shift << LG_SIZE_CLASS_GROUP; | szind_t grp = shift << SC_LG_NGROUP; | ||||
szind_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1) | szind_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1) | ||||
? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1; | ? LG_QUANTUM : x - SC_LG_NGROUP - 1; | ||||
size_t delta_inverse_mask = ZU(-1) << lg_delta; | size_t delta_inverse_mask = ZU(-1) << lg_delta; | ||||
szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) & | szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) & | ||||
((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); | ((ZU(1) << SC_LG_NGROUP) - 1); | ||||
szind_t index = NTBINS + grp + mod; | szind_t index = SC_NTINY + grp + mod; | ||||
return index; | return index; | ||||
} | } | ||||
} | } | ||||
JEMALLOC_ALWAYS_INLINE szind_t | JEMALLOC_ALWAYS_INLINE szind_t | ||||
sz_size2index_lookup(size_t size) { | sz_size2index_lookup(size_t size) { | ||||
assert(size <= LOOKUP_MAXCLASS); | assert(size <= SC_LOOKUP_MAXCLASS); | ||||
{ | szind_t ret = (sz_size2index_tab[(size + (ZU(1) << SC_LG_TINY_MIN) - 1) | ||||
szind_t ret = (sz_size2index_tab[(size-1) >> LG_TINY_MIN]); | >> SC_LG_TINY_MIN]); | ||||
assert(ret == sz_size2index_compute(size)); | assert(ret == sz_size2index_compute(size)); | ||||
return ret; | return ret; | ||||
} | } | ||||
} | |||||
JEMALLOC_ALWAYS_INLINE szind_t | JEMALLOC_ALWAYS_INLINE szind_t | ||||
sz_size2index(size_t size) { | sz_size2index(size_t size) { | ||||
assert(size > 0); | if (likely(size <= SC_LOOKUP_MAXCLASS)) { | ||||
if (likely(size <= LOOKUP_MAXCLASS)) { | |||||
return sz_size2index_lookup(size); | return sz_size2index_lookup(size); | ||||
} | } | ||||
return sz_size2index_compute(size); | return sz_size2index_compute(size); | ||||
} | } | ||||
static inline size_t | static inline size_t | ||||
sz_index2size_compute(szind_t index) { | sz_index2size_compute(szind_t index) { | ||||
#if (NTBINS > 0) | #if (SC_NTINY > 0) | ||||
if (index < NTBINS) { | if (index < SC_NTINY) { | ||||
return (ZU(1) << (LG_TINY_MAXCLASS - NTBINS + 1 + index)); | return (ZU(1) << (SC_LG_TINY_MAXCLASS - SC_NTINY + 1 + index)); | ||||
} | } | ||||
#endif | #endif | ||||
{ | { | ||||
size_t reduced_index = index - NTBINS; | size_t reduced_index = index - SC_NTINY; | ||||
size_t grp = reduced_index >> LG_SIZE_CLASS_GROUP; | size_t grp = reduced_index >> SC_LG_NGROUP; | ||||
size_t mod = reduced_index & ((ZU(1) << LG_SIZE_CLASS_GROUP) - | size_t mod = reduced_index & ((ZU(1) << SC_LG_NGROUP) - | ||||
1); | 1); | ||||
size_t grp_size_mask = ~((!!grp)-1); | size_t grp_size_mask = ~((!!grp)-1); | ||||
size_t grp_size = ((ZU(1) << (LG_QUANTUM + | size_t grp_size = ((ZU(1) << (LG_QUANTUM + | ||||
(LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask; | (SC_LG_NGROUP-1))) << grp) & grp_size_mask; | ||||
size_t shift = (grp == 0) ? 1 : grp; | size_t shift = (grp == 0) ? 1 : grp; | ||||
size_t lg_delta = shift + (LG_QUANTUM-1); | size_t lg_delta = shift + (LG_QUANTUM-1); | ||||
size_t mod_size = (mod+1) << lg_delta; | size_t mod_size = (mod+1) << lg_delta; | ||||
size_t usize = grp_size + mod_size; | size_t usize = grp_size + mod_size; | ||||
return usize; | return usize; | ||||
} | } | ||||
} | } | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_index2size_lookup(szind_t index) { | sz_index2size_lookup(szind_t index) { | ||||
size_t ret = (size_t)sz_index2size_tab[index]; | size_t ret = (size_t)sz_index2size_tab[index]; | ||||
assert(ret == sz_index2size_compute(index)); | assert(ret == sz_index2size_compute(index)); | ||||
return ret; | return ret; | ||||
} | } | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_index2size(szind_t index) { | sz_index2size(szind_t index) { | ||||
assert(index < NSIZES); | assert(index < SC_NSIZES); | ||||
return sz_index2size_lookup(index); | return sz_index2size_lookup(index); | ||||
} | } | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_s2u_compute(size_t size) { | sz_s2u_compute(size_t size) { | ||||
if (unlikely(size > LARGE_MAXCLASS)) { | if (unlikely(size > SC_LARGE_MAXCLASS)) { | ||||
return 0; | return 0; | ||||
} | } | ||||
#if (NTBINS > 0) | |||||
if (size <= (ZU(1) << LG_TINY_MAXCLASS)) { | if (size == 0) { | ||||
size_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1; | size++; | ||||
} | |||||
#if (SC_NTINY > 0) | |||||
if (size <= (ZU(1) << SC_LG_TINY_MAXCLASS)) { | |||||
size_t lg_tmin = SC_LG_TINY_MAXCLASS - SC_NTINY + 1; | |||||
size_t lg_ceil = lg_floor(pow2_ceil_zu(size)); | size_t lg_ceil = lg_floor(pow2_ceil_zu(size)); | ||||
return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) : | return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) : | ||||
(ZU(1) << lg_ceil)); | (ZU(1) << lg_ceil)); | ||||
} | } | ||||
#endif | #endif | ||||
{ | { | ||||
size_t x = lg_floor((size<<1)-1); | size_t x = lg_floor((size<<1)-1); | ||||
size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1) | size_t lg_delta = (x < SC_LG_NGROUP + LG_QUANTUM + 1) | ||||
? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1; | ? LG_QUANTUM : x - SC_LG_NGROUP - 1; | ||||
size_t delta = ZU(1) << lg_delta; | size_t delta = ZU(1) << lg_delta; | ||||
size_t delta_mask = delta - 1; | size_t delta_mask = delta - 1; | ||||
size_t usize = (size + delta_mask) & ~delta_mask; | size_t usize = (size + delta_mask) & ~delta_mask; | ||||
return usize; | return usize; | ||||
} | } | ||||
} | } | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_s2u_lookup(size_t size) { | sz_s2u_lookup(size_t size) { | ||||
size_t ret = sz_index2size_lookup(sz_size2index_lookup(size)); | size_t ret = sz_index2size_lookup(sz_size2index_lookup(size)); | ||||
assert(ret == sz_s2u_compute(size)); | assert(ret == sz_s2u_compute(size)); | ||||
return ret; | return ret; | ||||
} | } | ||||
/* | /* | ||||
* Compute usable size that would result from allocating an object with the | * Compute usable size that would result from allocating an object with the | ||||
* specified size. | * specified size. | ||||
*/ | */ | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_s2u(size_t size) { | sz_s2u(size_t size) { | ||||
assert(size > 0); | if (likely(size <= SC_LOOKUP_MAXCLASS)) { | ||||
if (likely(size <= LOOKUP_MAXCLASS)) { | |||||
return sz_s2u_lookup(size); | return sz_s2u_lookup(size); | ||||
} | } | ||||
return sz_s2u_compute(size); | return sz_s2u_compute(size); | ||||
} | } | ||||
/* | /* | ||||
* Compute usable size that would result from allocating an object with the | * Compute usable size that would result from allocating an object with the | ||||
* specified size and alignment. | * specified size and alignment. | ||||
*/ | */ | ||||
JEMALLOC_ALWAYS_INLINE size_t | JEMALLOC_ALWAYS_INLINE size_t | ||||
sz_sa2u(size_t size, size_t alignment) { | sz_sa2u(size_t size, size_t alignment) { | ||||
size_t usize; | size_t usize; | ||||
assert(alignment != 0 && ((alignment - 1) & alignment) == 0); | assert(alignment != 0 && ((alignment - 1) & alignment) == 0); | ||||
/* Try for a small size class. */ | /* Try for a small size class. */ | ||||
if (size <= SMALL_MAXCLASS && alignment < PAGE) { | if (size <= SC_SMALL_MAXCLASS && alignment < PAGE) { | ||||
/* | /* | ||||
* Round size up to the nearest multiple of alignment. | * Round size up to the nearest multiple of alignment. | ||||
* | * | ||||
* This done, we can take advantage of the fact that for each | * This done, we can take advantage of the fact that for each | ||||
* small size class, every object is aligned at the smallest | * small size class, every object is aligned at the smallest | ||||
* power of two that is non-zero in the base two representation | * power of two that is non-zero in the base two representation | ||||
* of the size. For example: | * of the size. For example: | ||||
* | * | ||||
* Size | Base 2 | Minimum alignment | * Size | Base 2 | Minimum alignment | ||||
* -----+----------+------------------ | * -----+----------+------------------ | ||||
* 96 | 1100000 | 32 | * 96 | 1100000 | 32 | ||||
* 144 | 10100000 | 32 | * 144 | 10100000 | 32 | ||||
* 192 | 11000000 | 64 | * 192 | 11000000 | 64 | ||||
*/ | */ | ||||
usize = sz_s2u(ALIGNMENT_CEILING(size, alignment)); | usize = sz_s2u(ALIGNMENT_CEILING(size, alignment)); | ||||
if (usize < LARGE_MINCLASS) { | if (usize < SC_LARGE_MINCLASS) { | ||||
return usize; | return usize; | ||||
} | } | ||||
} | } | ||||
/* Large size class. Beware of overflow. */ | /* Large size class. Beware of overflow. */ | ||||
if (unlikely(alignment > LARGE_MAXCLASS)) { | if (unlikely(alignment > SC_LARGE_MAXCLASS)) { | ||||
return 0; | return 0; | ||||
} | } | ||||
/* Make sure result is a large size class. */ | /* Make sure result is a large size class. */ | ||||
if (size <= LARGE_MINCLASS) { | if (size <= SC_LARGE_MINCLASS) { | ||||
usize = LARGE_MINCLASS; | usize = SC_LARGE_MINCLASS; | ||||
} else { | } else { | ||||
usize = sz_s2u(size); | usize = sz_s2u(size); | ||||
if (usize < size) { | if (usize < size) { | ||||
/* size_t overflow. */ | /* size_t overflow. */ | ||||
return 0; | return 0; | ||||
} | } | ||||
} | } | ||||
Show All 12 Lines |