1#ifndef JEMALLOC_INTERNAL_H 2#define JEMALLOC_INTERNAL_H 3 4#ifdef __cplusplus 5extern "C" { 6#endif 7 8#include "jemalloc_internal_defs.h" 9#include "jemalloc/internal/jemalloc_internal_decls.h" 10 11#ifdef JEMALLOC_UTRACE 12#include <sys/ktrace.h> 13#endif 14 15#define JEMALLOC_NO_DEMANGLE 16#ifdef JEMALLOC_JET 17# define JEMALLOC_N(n) jet_##n 18# include "jemalloc/internal/public_namespace.h" 19# define JEMALLOC_NO_RENAME 20# include "../jemalloc@install_suffix@.h" 21# undef JEMALLOC_NO_RENAME 22#else 23# define JEMALLOC_N(n) @private_namespace@##n 24# include "../jemalloc@install_suffix@.h" 25#endif 26#include "jemalloc/internal/private_namespace.h" 27 28static const bool config_debug = 29#ifdef JEMALLOC_DEBUG 30 true 31#else 32 false 33#endif 34 ; 35static const bool have_dss = 36#ifdef JEMALLOC_DSS 37 true 38#else 39 false 40#endif 41 ; 42static const bool config_fill = 43#ifdef JEMALLOC_FILL 44 true 45#else 46 false 47#endif 48 ; 49static const bool config_lazy_lock = 50#ifdef JEMALLOC_LAZY_LOCK 51 true 52#else 53 false 54#endif 55 ; 56static const char * const config_malloc_conf = JEMALLOC_CONFIG_MALLOC_CONF; 57static const bool config_prof = 58#ifdef JEMALLOC_PROF 59 true 60#else 61 false 62#endif 63 ; 64static const bool config_prof_libgcc = 65#ifdef JEMALLOC_PROF_LIBGCC 66 true 67#else 68 false 69#endif 70 ; 71static const bool config_prof_libunwind = 72#ifdef JEMALLOC_PROF_LIBUNWIND 73 true 74#else 75 false 76#endif 77 ; 78static const bool maps_coalesce = 79#ifdef JEMALLOC_MAPS_COALESCE 80 true 81#else 82 false 83#endif 84 ; 85static const bool config_munmap = 86#ifdef JEMALLOC_MUNMAP 87 true 88#else 89 false 90#endif 91 ; 92static const bool config_stats = 93#ifdef JEMALLOC_STATS 94 true 95#else 96 false 97#endif 98 ; 99static const bool config_tcache = 100#ifdef JEMALLOC_TCACHE 101 true 102#else 103 false 104#endif 105 ; 106static const bool config_tls = 107#ifdef JEMALLOC_TLS 108 true 109#else 110 false 111#endif 112 ; 113static const bool config_utrace = 114#ifdef JEMALLOC_UTRACE 115 true 116#else 117 false 118#endif 119 ; 120static const bool config_xmalloc = 121#ifdef JEMALLOC_XMALLOC 122 true 123#else 124 false 125#endif 126 ; 127static const bool config_ivsalloc = 128#ifdef JEMALLOC_IVSALLOC 129 true 130#else 131 false 132#endif 133 ; 134static const bool config_cache_oblivious = 135#ifdef JEMALLOC_CACHE_OBLIVIOUS 136 true 137#else 138 false 139#endif 140 ; 141static const bool have_thp = 142#ifdef JEMALLOC_THP 143 true 144#else 145 false 146#endif 147 ; 148 149#if defined(JEMALLOC_C11ATOMICS) && !defined(__cplusplus) 150#include <stdatomic.h> 151#endif 152 153#ifdef JEMALLOC_ATOMIC9 154#include <machine/atomic.h> 155#endif 156 157#if (defined(JEMALLOC_OSATOMIC) || defined(JEMALLOC_OSSPIN)) 158#include <libkern/OSAtomic.h> 159#endif 160 161#ifdef JEMALLOC_ZONE 162#include <mach/mach_error.h> 163#include <mach/mach_init.h> 164#include <mach/vm_map.h> 165#endif 166 167#include "jemalloc/internal/ph.h" 168#ifndef __PGI 169#define RB_COMPACT 170#endif 171#include "jemalloc/internal/rb.h" 172#include "jemalloc/internal/qr.h" 173#include "jemalloc/internal/ql.h" 174 175/* 176 * jemalloc can conceptually be broken into components (arena, tcache, etc.), 177 * but there are circular dependencies that cannot be broken without 178 * substantial performance degradation. 179 * 180 * Historically, we dealt with this by each header into four sections (types, 181 * structs, externs, and inlines), and included each header file multiple times 182 * in this file, picking out the portion we want on each pass using the 183 * following #defines: 184 * JEMALLOC_H_TYPES : Preprocessor-defined constants and psuedo-opaque data 185 * types. 186 * JEMALLOC_H_STRUCTS : Data structures. 187 * JEMALLOC_H_EXTERNS : Extern data declarations and function prototypes. 188 * JEMALLOC_H_INLINES : Inline functions. 189 * 190 * We're moving toward a world in which the dependencies are explicit; each file 191 * will #include the headers it depends on (rather than relying on them being 192 * implicitly available via this file including every header file in the 193 * project). 194 * 195 * We're now in an intermediate state: we've broken up the header files to avoid 196 * having to include each one multiple times, but have not yet moved the 197 * dependency information into the header files (i.e. we still rely on the 198 * ordering in this file to ensure all a header's dependencies are available in 199 * its translation unit). Each component is now broken up into multiple header 200 * files, corresponding to the sections above (e.g. instead of "tsd.h", we now 201 * have "tsd_types.h", "tsd_structs.h", "tsd_externs.h", "tsd_inlines.h"). 202 */ 203 204#include "jemalloc/internal/jemalloc_internal_macros.h" 205 206/******************************************************************************/ 207/* TYPES */ 208/******************************************************************************/ 209 210/* Page size index type. */ 211typedef unsigned pszind_t; 212 213/* Size class index type. */ 214typedef unsigned szind_t; 215 216/* 217 * Flags bits: 218 * 219 * a: arena 220 * t: tcache 221 * 0: unused 222 * z: zero 223 * n: alignment 224 * 225 * aaaaaaaa aaaatttt tttttttt 0znnnnnn 226 */ 227#define MALLOCX_ARENA_BITS 12 228#define MALLOCX_TCACHE_BITS 12 229#define MALLOCX_LG_ALIGN_BITS 6 230#define MALLOCX_ARENA_SHIFT 20 231#define MALLOCX_TCACHE_SHIFT 8 232#define MALLOCX_ARENA_MASK \ 233 (((1 << MALLOCX_ARENA_BITS) - 1) << MALLOCX_ARENA_SHIFT) 234/* NB: Arena index bias decreases the maximum number of arenas by 1. */ 235#define MALLOCX_ARENA_MAX ((1 << MALLOCX_ARENA_BITS) - 2) 236#define MALLOCX_TCACHE_MASK \ 237 (((1 << MALLOCX_TCACHE_BITS) - 1) << MALLOCX_TCACHE_SHIFT) 238#define MALLOCX_TCACHE_MAX ((1 << MALLOCX_TCACHE_BITS) - 3) 239#define MALLOCX_LG_ALIGN_MASK ((1 << MALLOCX_LG_ALIGN_BITS) - 1) 240/* Use MALLOCX_ALIGN_GET() if alignment may not be specified in flags. */ 241#define MALLOCX_ALIGN_GET_SPECIFIED(flags) \ 242 (ZU(1) << (flags & MALLOCX_LG_ALIGN_MASK)) 243#define MALLOCX_ALIGN_GET(flags) \ 244 (MALLOCX_ALIGN_GET_SPECIFIED(flags) & (SIZE_T_MAX-1)) 245#define MALLOCX_ZERO_GET(flags) \ 246 ((bool)(flags & MALLOCX_ZERO)) 247 248#define MALLOCX_TCACHE_GET(flags) \ 249 (((unsigned)((flags & MALLOCX_TCACHE_MASK) >> MALLOCX_TCACHE_SHIFT)) - 2) 250#define MALLOCX_ARENA_GET(flags) \ 251 (((unsigned)(((unsigned)flags) >> MALLOCX_ARENA_SHIFT)) - 1) 252 253/* Smallest size class to support. */ 254#define TINY_MIN (1U << LG_TINY_MIN) 255 256/* 257 * Minimum allocation alignment is 2^LG_QUANTUM bytes (ignoring tiny size 258 * classes). 259 */ 260#ifndef LG_QUANTUM 261# if (defined(__i386__) || defined(_M_IX86)) 262# define LG_QUANTUM 4 263# endif 264# ifdef __ia64__ 265# define LG_QUANTUM 4 266# endif 267# ifdef __alpha__ 268# define LG_QUANTUM 4 269# endif 270# if (defined(__sparc64__) || defined(__sparcv9) || defined(__sparc_v9__)) 271# define LG_QUANTUM 4 272# endif 273# if (defined(__amd64__) || defined(__x86_64__) || defined(_M_X64)) 274# define LG_QUANTUM 4 275# endif 276# ifdef __arm__ 277# define LG_QUANTUM 3 278# endif 279# ifdef __aarch64__ 280# define LG_QUANTUM 4 281# endif 282# ifdef __hppa__ 283# define LG_QUANTUM 4 284# endif 285# ifdef __mips__ 286# define LG_QUANTUM 3 287# endif 288# ifdef __or1k__ 289# define LG_QUANTUM 3 290# endif 291# ifdef __powerpc__ 292# define LG_QUANTUM 4 293# endif 294# ifdef __riscv__ 295# define LG_QUANTUM 4 296# endif 297# ifdef __s390__ 298# define LG_QUANTUM 4 299# endif 300# ifdef __SH4__ 301# define LG_QUANTUM 4 302# endif 303# ifdef __tile__ 304# define LG_QUANTUM 4 305# endif 306# ifdef __le32__ 307# define LG_QUANTUM 4 308# endif 309# ifndef LG_QUANTUM 310# error "Unknown minimum alignment for architecture; specify via " 311 "--with-lg-quantum" 312# endif 313#endif 314 315#define QUANTUM ((size_t)(1U << LG_QUANTUM)) 316#define QUANTUM_MASK (QUANTUM - 1) 317 318/* Return the smallest quantum multiple that is >= a. */ 319#define QUANTUM_CEILING(a) \ 320 (((a) + QUANTUM_MASK) & ~QUANTUM_MASK) 321 322#define LONG ((size_t)(1U << LG_SIZEOF_LONG)) 323#define LONG_MASK (LONG - 1) 324 325/* Return the smallest long multiple that is >= a. */ 326#define LONG_CEILING(a) \ 327 (((a) + LONG_MASK) & ~LONG_MASK) 328 329#define SIZEOF_PTR (1U << LG_SIZEOF_PTR) 330#define PTR_MASK (SIZEOF_PTR - 1) 331 332/* Return the smallest (void *) multiple that is >= a. */ 333#define PTR_CEILING(a) \ 334 (((a) + PTR_MASK) & ~PTR_MASK) 335 336/* 337 * Maximum size of L1 cache line. This is used to avoid cache line aliasing. 338 * In addition, this controls the spacing of cacheline-spaced size classes. 339 * 340 * CACHELINE cannot be based on LG_CACHELINE because __declspec(align()) can 341 * only handle raw constants. 342 */ 343#define LG_CACHELINE 6 344#define CACHELINE 64 345#define CACHELINE_MASK (CACHELINE - 1) 346 347/* Return the smallest cacheline multiple that is >= s. */ 348#define CACHELINE_CEILING(s) \ 349 (((s) + CACHELINE_MASK) & ~CACHELINE_MASK) 350 351/* Return the nearest aligned address at or below a. */ 352#define ALIGNMENT_ADDR2BASE(a, alignment) \ 353 ((void *)((uintptr_t)(a) & ((~(alignment)) + 1))) 354 355/* Return the offset between a and the nearest aligned address at or below a. */ 356#define ALIGNMENT_ADDR2OFFSET(a, alignment) \ 357 ((size_t)((uintptr_t)(a) & (alignment - 1))) 358 359/* Return the smallest alignment multiple that is >= s. */ 360#define ALIGNMENT_CEILING(s, alignment) \ 361 (((s) + (alignment - 1)) & ((~(alignment)) + 1)) 362 363/* Declare a variable-length array. */ 364#if __STDC_VERSION__ < 199901L 365# ifdef _MSC_VER 366# include <malloc.h> 367# define alloca _alloca 368# else 369# ifdef JEMALLOC_HAS_ALLOCA_H 370# include <alloca.h> 371# else 372# include <stdlib.h> 373# endif 374# endif 375# define VARIABLE_ARRAY(type, name, count) \ 376 type *name = alloca(sizeof(type) * (count)) 377#else 378# define VARIABLE_ARRAY(type, name, count) type name[(count)] 379#endif 380 381#include "jemalloc/internal/nstime_types.h" 382#include "jemalloc/internal/util_types.h" 383#include "jemalloc/internal/spin_types.h" 384#include "jemalloc/internal/prng_types.h" 385#include "jemalloc/internal/ticker_types.h" 386#include "jemalloc/internal/ckh_types.h" 387#include "jemalloc/internal/size_classes.h" 388#include "jemalloc/internal/smoothstep.h" 389#include "jemalloc/internal/stats_types.h" 390#include "jemalloc/internal/ctl_types.h" 391#include "jemalloc/internal/witness_types.h" 392#include "jemalloc/internal/mutex_types.h" 393#include "jemalloc/internal/tsd_types.h" 394#include "jemalloc/internal/extent_types.h" 395#include "jemalloc/internal/extent_dss_types.h" 396#include "jemalloc/internal/base_types.h" 397#include "jemalloc/internal/arena_types.h" 398#include "jemalloc/internal/bitmap_types.h" 399#include "jemalloc/internal/rtree_types.h" 400#include "jemalloc/internal/pages_types.h" 401#include "jemalloc/internal/tcache_types.h" 402#include "jemalloc/internal/prof_types.h" 403 404 405/******************************************************************************/ 406/* STRUCTS */ 407/******************************************************************************/ 408 409#include "jemalloc/internal/nstime_structs.h" 410#include "jemalloc/internal/spin_structs.h" 411#include "jemalloc/internal/ticker_structs.h" 412#include "jemalloc/internal/ckh_structs.h" 413#include "jemalloc/internal/stats_structs.h" 414#include "jemalloc/internal/ctl_structs.h" 415#include "jemalloc/internal/witness_structs.h" 416#include "jemalloc/internal/mutex_structs.h" 417#include "jemalloc/internal/bitmap_structs.h" 418#include "jemalloc/internal/arena_structs_a.h" 419#include "jemalloc/internal/extent_structs.h" 420#include "jemalloc/internal/extent_dss_structs.h" 421#include "jemalloc/internal/base_structs.h" 422#include "jemalloc/internal/arena_structs_b.h" 423#include "jemalloc/internal/rtree_structs.h" 424#include "jemalloc/internal/tcache_structs.h" 425#include "jemalloc/internal/prof_structs.h" 426#include "jemalloc/internal/tsd_structs.h" 427 428 429/******************************************************************************/ 430/* EXTERNS */ 431/******************************************************************************/ 432 433extern bool opt_abort; 434extern const char *opt_junk; 435extern bool opt_junk_alloc; 436extern bool opt_junk_free; 437extern bool opt_utrace; 438extern bool opt_xmalloc; 439extern bool opt_zero; 440extern unsigned opt_narenas; 441 442/* Number of CPUs. */ 443extern unsigned ncpus; 444 445/* Number of arenas used for automatic multiplexing of threads and arenas. */ 446extern unsigned narenas_auto; 447 448/* 449 * Arenas that are used to service external requests. Not all elements of the 450 * arenas array are necessarily used; arenas are created lazily as needed. 451 */ 452extern arena_t **arenas; 453 454/* 455 * pind2sz_tab encodes the same information as could be computed by 456 * pind2sz_compute(). 457 */ 458extern size_t const pind2sz_tab[NPSIZES+1]; 459/* 460 * index2size_tab encodes the same information as could be computed (at 461 * unacceptable cost in some code paths) by index2size_compute(). 462 */ 463extern size_t const index2size_tab[NSIZES]; 464/* 465 * size2index_tab is a compact lookup table that rounds request sizes up to 466 * size classes. In order to reduce cache footprint, the table is compressed, 467 * and all accesses are via size2index(). 468 */ 469extern uint8_t const size2index_tab[]; 470 471void *a0malloc(size_t size); 472void a0dalloc(void *ptr); 473void *bootstrap_malloc(size_t size); 474void *bootstrap_calloc(size_t num, size_t size); 475void bootstrap_free(void *ptr); 476void arena_set(unsigned ind, arena_t *arena); 477unsigned narenas_total_get(void); 478arena_t *arena_init(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks); 479arena_tdata_t *arena_tdata_get_hard(tsd_t *tsd, unsigned ind); 480arena_t *arena_choose_hard(tsd_t *tsd, bool internal); 481void arena_migrate(tsd_t *tsd, unsigned oldind, unsigned newind); 482void iarena_cleanup(tsd_t *tsd); 483void arena_cleanup(tsd_t *tsd); 484void arenas_tdata_cleanup(tsd_t *tsd); 485void jemalloc_prefork(void); 486void jemalloc_postfork_parent(void); 487void jemalloc_postfork_child(void); 488 489#include "jemalloc/internal/nstime_externs.h" 490#include "jemalloc/internal/util_externs.h" 491#include "jemalloc/internal/atomic_externs.h" 492#include "jemalloc/internal/ckh_externs.h" 493#include "jemalloc/internal/stats_externs.h" 494#include "jemalloc/internal/ctl_externs.h" 495#include "jemalloc/internal/witness_externs.h" 496#include "jemalloc/internal/mutex_externs.h" 497#include "jemalloc/internal/bitmap_externs.h" 498#include "jemalloc/internal/extent_externs.h" 499#include "jemalloc/internal/extent_dss_externs.h" 500#include "jemalloc/internal/extent_mmap_externs.h" 501#include "jemalloc/internal/base_externs.h" 502#include "jemalloc/internal/arena_externs.h" 503#include "jemalloc/internal/rtree_externs.h" 504#include "jemalloc/internal/pages_externs.h" 505#include "jemalloc/internal/large_externs.h" 506#include "jemalloc/internal/tcache_externs.h" 507#include "jemalloc/internal/prof_externs.h" 508#include "jemalloc/internal/tsd_externs.h" 509 510/******************************************************************************/ 511/* INLINES */ 512/******************************************************************************/ 513 514#include "jemalloc/internal/util_inlines.h" 515#include "jemalloc/internal/atomic_inlines.h" 516#include "jemalloc/internal/spin_inlines.h" 517#include "jemalloc/internal/prng_inlines.h" 518#include "jemalloc/internal/ticker_inlines.h" 519#include "jemalloc/internal/tsd_inlines.h" 520#include "jemalloc/internal/witness_inlines.h" 521#include "jemalloc/internal/mutex_inlines.h" 522#include "jemalloc/internal/rtree_inlines.h" 523#include "jemalloc/internal/extent_inlines.h" 524#include "jemalloc/internal/base_inlines.h" 525 526#ifndef JEMALLOC_ENABLE_INLINE 527pszind_t psz2ind(size_t psz); 528size_t pind2sz_compute(pszind_t pind); 529size_t pind2sz_lookup(pszind_t pind); 530size_t pind2sz(pszind_t pind); 531size_t psz2u(size_t psz); 532szind_t size2index_compute(size_t size); 533szind_t size2index_lookup(size_t size); 534szind_t size2index(size_t size); 535size_t index2size_compute(szind_t index); 536size_t index2size_lookup(szind_t index); 537size_t index2size(szind_t index); 538size_t s2u_compute(size_t size); 539size_t s2u_lookup(size_t size); 540size_t s2u(size_t size); 541size_t sa2u(size_t size, size_t alignment); 542arena_t *arena_choose_impl(tsd_t *tsd, arena_t *arena, bool internal); 543arena_t *arena_choose(tsd_t *tsd, arena_t *arena); 544arena_t *arena_ichoose(tsd_t *tsd, arena_t *arena); 545arena_tdata_t *arena_tdata_get(tsd_t *tsd, unsigned ind, 546 bool refresh_if_missing); 547arena_t *arena_get(tsdn_t *tsdn, unsigned ind, bool init_if_missing); 548ticker_t *decay_ticker_get(tsd_t *tsd, unsigned ind); 549#endif 550 551#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_C_)) 552JEMALLOC_ALWAYS_INLINE pszind_t 553psz2ind(size_t psz) 554{ 555 if (unlikely(psz > LARGE_MAXCLASS)) 556 return (NPSIZES); 557 { 558 pszind_t x = lg_floor((psz<<1)-1); 559 pszind_t shift = (x < LG_SIZE_CLASS_GROUP + LG_PAGE) ? 0 : x - 560 (LG_SIZE_CLASS_GROUP + LG_PAGE); 561 pszind_t grp = shift << LG_SIZE_CLASS_GROUP; 562 563 pszind_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_PAGE + 1) ? 564 LG_PAGE : x - LG_SIZE_CLASS_GROUP - 1; 565 566 size_t delta_inverse_mask = ZI(-1) << lg_delta; 567 pszind_t mod = ((((psz-1) & delta_inverse_mask) >> lg_delta)) & 568 ((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); 569 570 pszind_t ind = grp + mod; 571 return (ind); 572 } 573} 574 575JEMALLOC_INLINE size_t 576pind2sz_compute(pszind_t pind) 577{ 578 if (unlikely(pind == NPSIZES)) 579 return (LARGE_MAXCLASS + PAGE); 580 { 581 size_t grp = pind >> LG_SIZE_CLASS_GROUP; 582 size_t mod = pind & ((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); 583 584 size_t grp_size_mask = ~((!!grp)-1); 585 size_t grp_size = ((ZU(1) << (LG_PAGE + 586 (LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask; 587 588 size_t shift = (grp == 0) ? 1 : grp; 589 size_t lg_delta = shift + (LG_PAGE-1); 590 size_t mod_size = (mod+1) << lg_delta; 591 592 size_t sz = grp_size + mod_size; 593 return (sz); 594 } 595} 596 597JEMALLOC_INLINE size_t 598pind2sz_lookup(pszind_t pind) 599{ 600 size_t ret = (size_t)pind2sz_tab[pind]; 601 assert(ret == pind2sz_compute(pind)); 602 return (ret); 603} 604 605JEMALLOC_INLINE size_t 606pind2sz(pszind_t pind) 607{ 608 assert(pind < NPSIZES+1); 609 return (pind2sz_lookup(pind)); 610} 611 612JEMALLOC_INLINE size_t 613psz2u(size_t psz) 614{ 615 if (unlikely(psz > LARGE_MAXCLASS)) 616 return (LARGE_MAXCLASS + PAGE); 617 { 618 size_t x = lg_floor((psz<<1)-1); 619 size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_PAGE + 1) ? 620 LG_PAGE : x - LG_SIZE_CLASS_GROUP - 1; 621 size_t delta = ZU(1) << lg_delta; 622 size_t delta_mask = delta - 1; 623 size_t usize = (psz + delta_mask) & ~delta_mask; 624 return (usize); 625 } 626} 627 628JEMALLOC_INLINE szind_t 629size2index_compute(size_t size) 630{ 631 if (unlikely(size > LARGE_MAXCLASS)) 632 return (NSIZES); 633#if (NTBINS != 0) 634 if (size <= (ZU(1) << LG_TINY_MAXCLASS)) { 635 szind_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1; 636 szind_t lg_ceil = lg_floor(pow2_ceil_zu(size)); 637 return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin); 638 } 639#endif 640 { 641 szind_t x = lg_floor((size<<1)-1); 642 szind_t shift = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM) ? 0 : 643 x - (LG_SIZE_CLASS_GROUP + LG_QUANTUM); 644 szind_t grp = shift << LG_SIZE_CLASS_GROUP; 645 646 szind_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1) 647 ? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1; 648 649 size_t delta_inverse_mask = ZI(-1) << lg_delta; 650 szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) & 651 ((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); 652 653 szind_t index = NTBINS + grp + mod; 654 return (index); 655 } 656} 657 658JEMALLOC_ALWAYS_INLINE szind_t 659size2index_lookup(size_t size) 660{ 661 assert(size <= LOOKUP_MAXCLASS); 662 { 663 szind_t ret = (size2index_tab[(size-1) >> LG_TINY_MIN]); 664 assert(ret == size2index_compute(size)); 665 return (ret); 666 } 667} 668 669JEMALLOC_ALWAYS_INLINE szind_t 670size2index(size_t size) 671{ 672 assert(size > 0); 673 if (likely(size <= LOOKUP_MAXCLASS)) 674 return (size2index_lookup(size)); 675 return (size2index_compute(size)); 676} 677 678JEMALLOC_INLINE size_t 679index2size_compute(szind_t index) 680{ 681#if (NTBINS > 0) 682 if (index < NTBINS) 683 return (ZU(1) << (LG_TINY_MAXCLASS - NTBINS + 1 + index)); 684#endif 685 { 686 size_t reduced_index = index - NTBINS; 687 size_t grp = reduced_index >> LG_SIZE_CLASS_GROUP; 688 size_t mod = reduced_index & ((ZU(1) << LG_SIZE_CLASS_GROUP) - 689 1); 690 691 size_t grp_size_mask = ~((!!grp)-1); 692 size_t grp_size = ((ZU(1) << (LG_QUANTUM + 693 (LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask; 694 695 size_t shift = (grp == 0) ? 1 : grp; 696 size_t lg_delta = shift + (LG_QUANTUM-1); 697 size_t mod_size = (mod+1) << lg_delta; 698 699 size_t usize = grp_size + mod_size; 700 return (usize); 701 } 702} 703 704JEMALLOC_ALWAYS_INLINE size_t 705index2size_lookup(szind_t index) 706{ 707 size_t ret = (size_t)index2size_tab[index]; 708 assert(ret == index2size_compute(index)); 709 return (ret); 710} 711 712JEMALLOC_ALWAYS_INLINE size_t 713index2size(szind_t index) 714{ 715 assert(index < NSIZES); 716 return (index2size_lookup(index)); 717} 718 719JEMALLOC_ALWAYS_INLINE size_t 720s2u_compute(size_t size) 721{ 722 if (unlikely(size > LARGE_MAXCLASS)) 723 return (0); 724#if (NTBINS > 0) 725 if (size <= (ZU(1) << LG_TINY_MAXCLASS)) { 726 size_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1; 727 size_t lg_ceil = lg_floor(pow2_ceil_zu(size)); 728 return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) : 729 (ZU(1) << lg_ceil)); 730 } 731#endif 732 { 733 size_t x = lg_floor((size<<1)-1); 734 size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1) 735 ? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1; 736 size_t delta = ZU(1) << lg_delta; 737 size_t delta_mask = delta - 1; 738 size_t usize = (size + delta_mask) & ~delta_mask; 739 return (usize); 740 } 741} 742 743JEMALLOC_ALWAYS_INLINE size_t 744s2u_lookup(size_t size) 745{ 746 size_t ret = index2size_lookup(size2index_lookup(size)); 747 748 assert(ret == s2u_compute(size)); 749 return (ret); 750} 751 752/* 753 * Compute usable size that would result from allocating an object with the 754 * specified size. 755 */ 756JEMALLOC_ALWAYS_INLINE size_t 757s2u(size_t size) 758{ 759 assert(size > 0); 760 if (likely(size <= LOOKUP_MAXCLASS)) 761 return (s2u_lookup(size)); 762 return (s2u_compute(size)); 763} 764 765/* 766 * Compute usable size that would result from allocating an object with the 767 * specified size and alignment. 768 */ 769JEMALLOC_ALWAYS_INLINE size_t 770sa2u(size_t size, size_t alignment) 771{ 772 size_t usize; 773 774 assert(alignment != 0 && ((alignment - 1) & alignment) == 0); 775 776 /* Try for a small size class. */ 777 if (size <= SMALL_MAXCLASS && alignment < PAGE) { 778 /* 779 * Round size up to the nearest multiple of alignment. 780 * 781 * This done, we can take advantage of the fact that for each 782 * small size class, every object is aligned at the smallest 783 * power of two that is non-zero in the base two representation 784 * of the size. For example: 785 * 786 * Size | Base 2 | Minimum alignment 787 * -----+----------+------------------ 788 * 96 | 1100000 | 32 789 * 144 | 10100000 | 32 790 * 192 | 11000000 | 64 791 */ 792 usize = s2u(ALIGNMENT_CEILING(size, alignment)); 793 if (usize < LARGE_MINCLASS) 794 return (usize); 795 } 796 797 /* Large size class. Beware of overflow. */ 798 799 if (unlikely(alignment > LARGE_MAXCLASS)) 800 return (0); 801 802 /* Make sure result is a large size class. */ 803 if (size <= LARGE_MINCLASS) 804 usize = LARGE_MINCLASS; 805 else { 806 usize = s2u(size); 807 if (usize < size) { 808 /* size_t overflow. */ 809 return (0); 810 } 811 } 812 813 /* 814 * Calculate the multi-page mapping that large_palloc() would need in 815 * order to guarantee the alignment. 816 */ 817 if (usize + large_pad + PAGE_CEILING(alignment) - PAGE < usize) { 818 /* size_t overflow. */ 819 return (0); 820 } 821 return (usize); 822} 823 824/* Choose an arena based on a per-thread value. */ 825JEMALLOC_INLINE arena_t * 826arena_choose_impl(tsd_t *tsd, arena_t *arena, bool internal) 827{ 828 arena_t *ret; 829 830 if (arena != NULL) 831 return (arena); 832 833 ret = internal ? tsd_iarena_get(tsd) : tsd_arena_get(tsd); 834 if (unlikely(ret == NULL)) 835 ret = arena_choose_hard(tsd, internal); 836 837 return (ret); 838} 839 840JEMALLOC_INLINE arena_t * 841arena_choose(tsd_t *tsd, arena_t *arena) 842{ 843 return (arena_choose_impl(tsd, arena, false)); 844} 845 846JEMALLOC_INLINE arena_t * 847arena_ichoose(tsd_t *tsd, arena_t *arena) 848{ 849 return (arena_choose_impl(tsd, arena, true)); 850} 851 852JEMALLOC_INLINE arena_tdata_t * 853arena_tdata_get(tsd_t *tsd, unsigned ind, bool refresh_if_missing) 854{ 855 arena_tdata_t *tdata; 856 arena_tdata_t *arenas_tdata = tsd_arenas_tdata_get(tsd); 857 858 if (unlikely(arenas_tdata == NULL)) { 859 /* arenas_tdata hasn't been initialized yet. */ 860 return (arena_tdata_get_hard(tsd, ind)); 861 } 862 if (unlikely(ind >= tsd_narenas_tdata_get(tsd))) { 863 /* 864 * ind is invalid, cache is old (too small), or tdata to be 865 * initialized. 866 */ 867 return (refresh_if_missing ? arena_tdata_get_hard(tsd, ind) : 868 NULL); 869 } 870 871 tdata = &arenas_tdata[ind]; 872 if (likely(tdata != NULL) || !refresh_if_missing) 873 return (tdata); 874 return (arena_tdata_get_hard(tsd, ind)); 875} 876 877JEMALLOC_INLINE arena_t * 878arena_get(tsdn_t *tsdn, unsigned ind, bool init_if_missing) 879{ 880 arena_t *ret; 881 882 assert(ind <= MALLOCX_ARENA_MAX); 883 884 ret = arenas[ind]; 885 if (unlikely(ret == NULL)) { 886 ret = (arena_t *)atomic_read_p((void **)&arenas[ind]); 887 if (init_if_missing && unlikely(ret == NULL)) { 888 ret = arena_init(tsdn, ind, 889 (extent_hooks_t *)&extent_hooks_default); 890 } 891 } 892 return (ret); 893} 894 895JEMALLOC_INLINE ticker_t * 896decay_ticker_get(tsd_t *tsd, unsigned ind) 897{ 898 arena_tdata_t *tdata; 899 900 tdata = arena_tdata_get(tsd, ind, true); 901 if (unlikely(tdata == NULL)) 902 return (NULL); 903 return (&tdata->decay_ticker); 904} 905#endif 906 907#include "jemalloc/internal/bitmap_inlines.h" 908/* 909 * Include portions of arena code interleaved with tcache code in order to 910 * resolve circular dependencies. 911 */ 912#include "jemalloc/internal/arena_inlines_a.h" 913 914#ifndef JEMALLOC_ENABLE_INLINE 915extent_t *iealloc(tsdn_t *tsdn, const void *ptr); 916#endif 917 918#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_C_)) 919JEMALLOC_ALWAYS_INLINE extent_t * 920iealloc(tsdn_t *tsdn, const void *ptr) 921{ 922 return (extent_lookup(tsdn, ptr, true)); 923} 924#endif 925 926#include "jemalloc/internal/tcache_inlines.h" 927#include "jemalloc/internal/arena_inlines_b.h" 928#include "jemalloc/internal/hash_inlines.h" 929 930#ifndef JEMALLOC_ENABLE_INLINE 931arena_t *iaalloc(tsdn_t *tsdn, const void *ptr); 932size_t isalloc(tsdn_t *tsdn, const extent_t *extent, const void *ptr); 933void *iallocztm(tsdn_t *tsdn, size_t size, szind_t ind, bool zero, 934 tcache_t *tcache, bool is_internal, arena_t *arena, bool slow_path); 935void *ialloc(tsd_t *tsd, size_t size, szind_t ind, bool zero, 936 bool slow_path); 937void *ipallocztm(tsdn_t *tsdn, size_t usize, size_t alignment, bool zero, 938 tcache_t *tcache, bool is_internal, arena_t *arena); 939void *ipalloct(tsdn_t *tsdn, size_t usize, size_t alignment, bool zero, 940 tcache_t *tcache, arena_t *arena); 941void *ipalloc(tsd_t *tsd, size_t usize, size_t alignment, bool zero); 942size_t ivsalloc(tsdn_t *tsdn, const void *ptr); 943void idalloctm(tsdn_t *tsdn, extent_t *extent, void *ptr, tcache_t *tcache, 944 bool is_internal, bool slow_path); 945void idalloc(tsd_t *tsd, extent_t *extent, void *ptr); 946void isdalloct(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t size, 947 tcache_t *tcache, bool slow_path); 948void *iralloct_realign(tsdn_t *tsdn, extent_t *extent, void *ptr, 949 size_t oldsize, size_t size, size_t extra, size_t alignment, bool zero, 950 tcache_t *tcache, arena_t *arena); 951void *iralloct(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t oldsize, 952 size_t size, size_t alignment, bool zero, tcache_t *tcache, arena_t *arena); 953void *iralloc(tsd_t *tsd, extent_t *extent, void *ptr, size_t oldsize, 954 size_t size, size_t alignment, bool zero); 955bool ixalloc(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t oldsize, 956 size_t size, size_t extra, size_t alignment, bool zero); 957#endif 958 959#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_C_)) 960JEMALLOC_ALWAYS_INLINE arena_t * 961iaalloc(tsdn_t *tsdn, const void *ptr) 962{ 963 assert(ptr != NULL); 964 965 return (arena_aalloc(tsdn, ptr)); 966} 967 968/* 969 * Typical usage: 970 * tsdn_t *tsdn = [...] 971 * void *ptr = [...] 972 * extent_t *extent = iealloc(tsdn, ptr); 973 * size_t sz = isalloc(tsdn, extent, ptr); 974 */ 975JEMALLOC_ALWAYS_INLINE size_t 976isalloc(tsdn_t *tsdn, const extent_t *extent, const void *ptr) 977{ 978 assert(ptr != NULL); 979 980 return (arena_salloc(tsdn, extent, ptr)); 981} 982 983JEMALLOC_ALWAYS_INLINE void * 984iallocztm(tsdn_t *tsdn, size_t size, szind_t ind, bool zero, tcache_t *tcache, 985 bool is_internal, arena_t *arena, bool slow_path) 986{ 987 void *ret; 988 989 assert(size != 0); 990 assert(!is_internal || tcache == NULL); 991 assert(!is_internal || arena == NULL || arena_ind_get(arena) < 992 narenas_auto); 993 994 ret = arena_malloc(tsdn, arena, size, ind, zero, tcache, slow_path); 995 if (config_stats && is_internal && likely(ret != NULL)) { 996 arena_internal_add(iaalloc(tsdn, ret), isalloc(tsdn, 997 iealloc(tsdn, ret), ret)); 998 } 999 return (ret); 1000} 1001 1002JEMALLOC_ALWAYS_INLINE void * 1003ialloc(tsd_t *tsd, size_t size, szind_t ind, bool zero, bool slow_path) 1004{ 1005 return (iallocztm(tsd_tsdn(tsd), size, ind, zero, tcache_get(tsd, true), 1006 false, NULL, slow_path)); 1007} 1008 1009JEMALLOC_ALWAYS_INLINE void * 1010ipallocztm(tsdn_t *tsdn, size_t usize, size_t alignment, bool zero, 1011 tcache_t *tcache, bool is_internal, arena_t *arena) 1012{ 1013 void *ret; 1014 1015 assert(usize != 0); 1016 assert(usize == sa2u(usize, alignment)); 1017 assert(!is_internal || tcache == NULL); 1018 assert(!is_internal || arena == NULL || arena_ind_get(arena) < 1019 narenas_auto); 1020 1021 ret = arena_palloc(tsdn, arena, usize, alignment, zero, tcache); 1022 assert(ALIGNMENT_ADDR2BASE(ret, alignment) == ret); 1023 if (config_stats && is_internal && likely(ret != NULL)) { 1024 arena_internal_add(iaalloc(tsdn, ret), isalloc(tsdn, 1025 iealloc(tsdn, ret), ret)); 1026 } 1027 return (ret); 1028} 1029 1030JEMALLOC_ALWAYS_INLINE void * 1031ipalloct(tsdn_t *tsdn, size_t usize, size_t alignment, bool zero, 1032 tcache_t *tcache, arena_t *arena) 1033{ 1034 return (ipallocztm(tsdn, usize, alignment, zero, tcache, false, arena)); 1035} 1036 1037JEMALLOC_ALWAYS_INLINE void * 1038ipalloc(tsd_t *tsd, size_t usize, size_t alignment, bool zero) 1039{ 1040 return (ipallocztm(tsd_tsdn(tsd), usize, alignment, zero, 1041 tcache_get(tsd, true), false, NULL)); 1042} 1043 1044JEMALLOC_ALWAYS_INLINE size_t 1045ivsalloc(tsdn_t *tsdn, const void *ptr) 1046{ 1047 extent_t *extent; 1048 1049 /* 1050 * Return 0 if ptr is not within an extent managed by jemalloc. This 1051 * function has two extra costs relative to isalloc(): 1052 * - The extent_lookup() call cannot claim to be a dependent lookup, 1053 * which induces rtree lookup load dependencies. 1054 * - The lookup may fail, so there is an extra branch to check for 1055 * failure. 1056 * */ 1057 extent = extent_lookup(tsdn, ptr, false); 1058 if (extent == NULL) 1059 return (0); 1060 assert(extent_active_get(extent)); 1061 /* Only slab members should be looked up via interior pointers. */ 1062 assert(extent_addr_get(extent) == ptr || extent_slab_get(extent)); 1063 1064 return (isalloc(tsdn, extent, ptr)); 1065} 1066 1067JEMALLOC_ALWAYS_INLINE void 1068idalloctm(tsdn_t *tsdn, extent_t *extent, void *ptr, tcache_t *tcache, 1069 bool is_internal, bool slow_path) 1070{ 1071 assert(ptr != NULL); 1072 assert(!is_internal || tcache == NULL); 1073 assert(!is_internal || arena_ind_get(iaalloc(tsdn, ptr)) < 1074 narenas_auto); 1075 if (config_stats && is_internal) { 1076 arena_internal_sub(iaalloc(tsdn, ptr), isalloc(tsdn, extent, 1077 ptr)); 1078 } 1079 1080 arena_dalloc(tsdn, extent, ptr, tcache, slow_path); 1081} 1082 1083JEMALLOC_ALWAYS_INLINE void 1084idalloc(tsd_t *tsd, extent_t *extent, void *ptr) 1085{ 1086 idalloctm(tsd_tsdn(tsd), extent, ptr, tcache_get(tsd, false), false, 1087 true); 1088} 1089 1090JEMALLOC_ALWAYS_INLINE void 1091isdalloct(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t size, 1092 tcache_t *tcache, bool slow_path) 1093{ 1094 arena_sdalloc(tsdn, extent, ptr, size, tcache, slow_path); 1095} 1096 1097JEMALLOC_ALWAYS_INLINE void * 1098iralloct_realign(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t oldsize, 1099 size_t size, size_t extra, size_t alignment, bool zero, tcache_t *tcache, 1100 arena_t *arena) 1101{ 1102 void *p; 1103 size_t usize, copysize; 1104 1105 usize = sa2u(size + extra, alignment); 1106 if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) 1107 return (NULL); 1108 p = ipalloct(tsdn, usize, alignment, zero, tcache, arena); 1109 if (p == NULL) { 1110 if (extra == 0) 1111 return (NULL); 1112 /* Try again, without extra this time. */ 1113 usize = sa2u(size, alignment); 1114 if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) 1115 return (NULL); 1116 p = ipalloct(tsdn, usize, alignment, zero, tcache, arena); 1117 if (p == NULL) 1118 return (NULL); 1119 } 1120 /* 1121 * Copy at most size bytes (not size+extra), since the caller has no 1122 * expectation that the extra bytes will be reliably preserved. 1123 */ 1124 copysize = (size < oldsize) ? size : oldsize; 1125 memcpy(p, ptr, copysize); 1126 isdalloct(tsdn, extent, ptr, oldsize, tcache, true); 1127 return (p); 1128} 1129 1130JEMALLOC_ALWAYS_INLINE void * 1131iralloct(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t oldsize, size_t size, 1132 size_t alignment, bool zero, tcache_t *tcache, arena_t *arena) 1133{ 1134 assert(ptr != NULL); 1135 assert(size != 0); 1136 1137 if (alignment != 0 && ((uintptr_t)ptr & ((uintptr_t)alignment-1)) 1138 != 0) { 1139 /* 1140 * Existing object alignment is inadequate; allocate new space 1141 * and copy. 1142 */ 1143 return (iralloct_realign(tsdn, extent, ptr, oldsize, size, 0, 1144 alignment, zero, tcache, arena)); 1145 } 1146 1147 return (arena_ralloc(tsdn, arena, extent, ptr, oldsize, size, alignment, 1148 zero, tcache)); 1149} 1150 1151JEMALLOC_ALWAYS_INLINE void * 1152iralloc(tsd_t *tsd, extent_t *extent, void *ptr, size_t oldsize, size_t size, 1153 size_t alignment, bool zero) 1154{ 1155 return (iralloct(tsd_tsdn(tsd), extent, ptr, oldsize, size, alignment, 1156 zero, tcache_get(tsd, true), NULL)); 1157} 1158 1159JEMALLOC_ALWAYS_INLINE bool 1160ixalloc(tsdn_t *tsdn, extent_t *extent, void *ptr, size_t oldsize, size_t size, 1161 size_t extra, size_t alignment, bool zero) 1162{ 1163 assert(ptr != NULL); 1164 assert(size != 0); 1165 1166 if (alignment != 0 && ((uintptr_t)ptr & ((uintptr_t)alignment-1)) 1167 != 0) { 1168 /* Existing object alignment is inadequate. */ 1169 return (true); 1170 } 1171 1172 return (arena_ralloc_no_move(tsdn, extent, ptr, oldsize, size, extra, 1173 zero)); 1174} 1175#endif 1176 1177#include "jemalloc/internal/prof_inlines.h" 1178 1179 1180#ifdef __cplusplus 1181} 1182#endif 1183 1184#endif /* JEMALLOC_INTERNAL_H */ 1185