jemalloc_internal.h.in revision ae4c7b4b4092906c641d69b4bf9fcb4a7d50790d
1#include <sys/mman.h> 2#include <sys/param.h> 3#include <sys/syscall.h> 4#if !defined(SYS_write) && defined(__NR_write) 5#define SYS_write __NR_write 6#endif 7#include <sys/time.h> 8#include <sys/types.h> 9#include <sys/uio.h> 10 11#include <errno.h> 12#include <limits.h> 13#ifndef SIZE_T_MAX 14# define SIZE_T_MAX SIZE_MAX 15#endif 16#include <pthread.h> 17#include <sched.h> 18#include <stdarg.h> 19#include <stdbool.h> 20#include <stdio.h> 21#include <stdlib.h> 22#include <stdint.h> 23#include <stddef.h> 24#ifndef offsetof 25# define offsetof(type, member) ((size_t)&(((type *)NULL)->member)) 26#endif 27#include <inttypes.h> 28#include <string.h> 29#include <strings.h> 30#include <ctype.h> 31#include <unistd.h> 32#include <fcntl.h> 33#include <pthread.h> 34#include <math.h> 35 36#define JEMALLOC_NO_DEMANGLE 37#include "../jemalloc@install_suffix@.h" 38 39#include "jemalloc/internal/private_namespace.h" 40 41#ifdef JEMALLOC_CC_SILENCE 42#define UNUSED JEMALLOC_ATTR(unused) 43#else 44#define UNUSED 45#endif 46 47static const bool config_debug = 48#ifdef JEMALLOC_DEBUG 49 true 50#else 51 false 52#endif 53 ; 54static const bool config_dss = 55#ifdef JEMALLOC_DSS 56 true 57#else 58 false 59#endif 60 ; 61static const bool config_fill = 62#ifdef JEMALLOC_FILL 63 true 64#else 65 false 66#endif 67 ; 68static const bool config_lazy_lock = 69#ifdef JEMALLOC_LAZY_LOCK 70 true 71#else 72 false 73#endif 74 ; 75static const bool config_prof = 76#ifdef JEMALLOC_PROF 77 true 78#else 79 false 80#endif 81 ; 82static const bool config_prof_libgcc = 83#ifdef JEMALLOC_PROF_LIBGCC 84 true 85#else 86 false 87#endif 88 ; 89static const bool config_prof_libunwind = 90#ifdef JEMALLOC_PROF_LIBUNWIND 91 true 92#else 93 false 94#endif 95 ; 96static const bool config_stats = 97#ifdef JEMALLOC_STATS 98 true 99#else 100 false 101#endif 102 ; 103static const bool config_tcache = 104#ifdef JEMALLOC_TCACHE 105 true 106#else 107 false 108#endif 109 ; 110static const bool config_tls = 111#ifdef JEMALLOC_TLS 112 true 113#else 114 false 115#endif 116 ; 117static const bool config_xmalloc = 118#ifdef JEMALLOC_XMALLOC 119 true 120#else 121 false 122#endif 123 ; 124static const bool config_ivsalloc = 125#ifdef JEMALLOC_IVSALLOC 126 true 127#else 128 false 129#endif 130 ; 131 132#if (defined(JEMALLOC_OSATOMIC) || defined(JEMALLOC_OSSPIN)) 133#include <libkern/OSAtomic.h> 134#endif 135 136#ifdef JEMALLOC_ZONE 137#include <mach/mach_error.h> 138#include <mach/mach_init.h> 139#include <mach/vm_map.h> 140#include <malloc/malloc.h> 141#endif 142 143#define RB_COMPACT 144#include "jemalloc/internal/rb.h" 145#include "jemalloc/internal/qr.h" 146#include "jemalloc/internal/ql.h" 147 148/* 149 * jemalloc can conceptually be broken into components (arena, tcache, etc.), 150 * but there are circular dependencies that cannot be broken without 151 * substantial performance degradation. In order to reduce the effect on 152 * visual code flow, read the header files in multiple passes, with one of the 153 * following cpp variables defined during each pass: 154 * 155 * JEMALLOC_H_TYPES : Preprocessor-defined constants and psuedo-opaque data 156 * types. 157 * JEMALLOC_H_STRUCTS : Data structures. 158 * JEMALLOC_H_EXTERNS : Extern data declarations and function prototypes. 159 * JEMALLOC_H_INLINES : Inline functions. 160 */ 161/******************************************************************************/ 162#define JEMALLOC_H_TYPES 163 164#define ALLOCM_LG_ALIGN_MASK ((int)0x3f) 165 166#define ZU(z) ((size_t)z) 167 168#ifndef __DECONST 169# define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var)) 170#endif 171 172#ifdef JEMALLOC_DEBUG 173 /* Disable inlining to make debugging easier. */ 174# define JEMALLOC_INLINE 175# define inline 176#else 177# define JEMALLOC_ENABLE_INLINE 178# define JEMALLOC_INLINE static inline 179#endif 180 181/* Smallest size class to support. */ 182#define LG_TINY_MIN 3 183#define TINY_MIN (1U << LG_TINY_MIN) 184 185/* 186 * Minimum alignment of allocations is 2^LG_QUANTUM bytes (ignoring tiny size 187 * classes). 188 */ 189#ifndef LG_QUANTUM 190# ifdef __i386__ 191# define LG_QUANTUM 4 192# endif 193# ifdef __ia64__ 194# define LG_QUANTUM 4 195# endif 196# ifdef __alpha__ 197# define LG_QUANTUM 4 198# endif 199# ifdef __sparc64__ 200# define LG_QUANTUM 4 201# endif 202# if (defined(__amd64__) || defined(__x86_64__)) 203# define LG_QUANTUM 4 204# endif 205# ifdef __arm__ 206# define LG_QUANTUM 3 207# endif 208# ifdef __mips__ 209# define LG_QUANTUM 3 210# endif 211# ifdef __powerpc__ 212# define LG_QUANTUM 4 213# endif 214# ifdef __s390x__ 215# define LG_QUANTUM 4 216# endif 217# ifdef __SH4__ 218# define LG_QUANTUM 4 219# endif 220# ifdef __tile__ 221# define LG_QUANTUM 4 222# endif 223# ifndef LG_QUANTUM 224# error "No LG_QUANTUM definition for architecture; specify via CPPFLAGS" 225# endif 226#endif 227 228#define QUANTUM ((size_t)(1U << LG_QUANTUM)) 229#define QUANTUM_MASK (QUANTUM - 1) 230 231/* Return the smallest quantum multiple that is >= a. */ 232#define QUANTUM_CEILING(a) \ 233 (((a) + QUANTUM_MASK) & ~QUANTUM_MASK) 234 235#define LONG ((size_t)(1U << LG_SIZEOF_LONG)) 236#define LONG_MASK (LONG - 1) 237 238/* Return the smallest long multiple that is >= a. */ 239#define LONG_CEILING(a) \ 240 (((a) + LONG_MASK) & ~LONG_MASK) 241 242#define SIZEOF_PTR (1U << LG_SIZEOF_PTR) 243#define PTR_MASK (SIZEOF_PTR - 1) 244 245/* Return the smallest (void *) multiple that is >= a. */ 246#define PTR_CEILING(a) \ 247 (((a) + PTR_MASK) & ~PTR_MASK) 248 249/* 250 * Maximum size of L1 cache line. This is used to avoid cache line aliasing. 251 * In addition, this controls the spacing of cacheline-spaced size classes. 252 */ 253#define LG_CACHELINE 6 254#define CACHELINE ((size_t)(1U << LG_CACHELINE)) 255#define CACHELINE_MASK (CACHELINE - 1) 256 257/* Return the smallest cacheline multiple that is >= s. */ 258#define CACHELINE_CEILING(s) \ 259 (((s) + CACHELINE_MASK) & ~CACHELINE_MASK) 260 261/* Page size. STATIC_PAGE_SHIFT is determined by the configure script. */ 262#ifdef PAGE_MASK 263# undef PAGE_MASK 264#endif 265#define LG_PAGE STATIC_PAGE_SHIFT 266#define PAGE ((size_t)(1U << STATIC_PAGE_SHIFT)) 267#define PAGE_MASK ((size_t)(PAGE - 1)) 268 269/* Return the smallest pagesize multiple that is >= s. */ 270#define PAGE_CEILING(s) \ 271 (((s) + PAGE_MASK) & ~PAGE_MASK) 272 273#include "jemalloc/internal/util.h" 274#include "jemalloc/internal/atomic.h" 275#include "jemalloc/internal/prng.h" 276#include "jemalloc/internal/ckh.h" 277#include "jemalloc/internal/size_classes.h" 278#include "jemalloc/internal/stats.h" 279#include "jemalloc/internal/ctl.h" 280#include "jemalloc/internal/mutex.h" 281#include "jemalloc/internal/tsd.h" 282#include "jemalloc/internal/mb.h" 283#include "jemalloc/internal/extent.h" 284#include "jemalloc/internal/arena.h" 285#include "jemalloc/internal/bitmap.h" 286#include "jemalloc/internal/base.h" 287#include "jemalloc/internal/chunk.h" 288#include "jemalloc/internal/huge.h" 289#include "jemalloc/internal/rtree.h" 290#include "jemalloc/internal/tcache.h" 291#include "jemalloc/internal/hash.h" 292#include "jemalloc/internal/prof.h" 293 294#undef JEMALLOC_H_TYPES 295/******************************************************************************/ 296#define JEMALLOC_H_STRUCTS 297 298#include "jemalloc/internal/util.h" 299#include "jemalloc/internal/atomic.h" 300#include "jemalloc/internal/prng.h" 301#include "jemalloc/internal/ckh.h" 302#include "jemalloc/internal/size_classes.h" 303#include "jemalloc/internal/stats.h" 304#include "jemalloc/internal/ctl.h" 305#include "jemalloc/internal/mutex.h" 306#include "jemalloc/internal/tsd.h" 307#include "jemalloc/internal/mb.h" 308#include "jemalloc/internal/bitmap.h" 309#include "jemalloc/internal/extent.h" 310#include "jemalloc/internal/arena.h" 311#include "jemalloc/internal/base.h" 312#include "jemalloc/internal/chunk.h" 313#include "jemalloc/internal/huge.h" 314#include "jemalloc/internal/rtree.h" 315#include "jemalloc/internal/tcache.h" 316#include "jemalloc/internal/hash.h" 317#include "jemalloc/internal/prof.h" 318 319typedef struct { 320 uint64_t allocated; 321 uint64_t deallocated; 322} thread_allocated_t; 323/* 324 * The JEMALLOC_CONCAT() wrapper is necessary to pass {0, 0} via a cpp macro 325 * argument. 326 */ 327#define THREAD_ALLOCATED_INITIALIZER JEMALLOC_CONCAT({0, 0}) 328 329#undef JEMALLOC_H_STRUCTS 330/******************************************************************************/ 331#define JEMALLOC_H_EXTERNS 332 333extern bool opt_abort; 334extern bool opt_junk; 335extern bool opt_xmalloc; 336extern bool opt_zero; 337extern size_t opt_narenas; 338 339/* Number of CPUs. */ 340extern unsigned ncpus; 341 342extern malloc_mutex_t arenas_lock; /* Protects arenas initialization. */ 343/* 344 * Arenas that are used to service external requests. Not all elements of the 345 * arenas array are necessarily used; arenas are created lazily as needed. 346 */ 347extern arena_t **arenas; 348extern unsigned narenas; 349 350arena_t *arenas_extend(unsigned ind); 351void arenas_cleanup(void *arg); 352arena_t *choose_arena_hard(void); 353void jemalloc_prefork(void); 354void jemalloc_postfork_parent(void); 355void jemalloc_postfork_child(void); 356 357#include "jemalloc/internal/util.h" 358#include "jemalloc/internal/atomic.h" 359#include "jemalloc/internal/prng.h" 360#include "jemalloc/internal/ckh.h" 361#include "jemalloc/internal/size_classes.h" 362#include "jemalloc/internal/stats.h" 363#include "jemalloc/internal/ctl.h" 364#include "jemalloc/internal/mutex.h" 365#include "jemalloc/internal/tsd.h" 366#include "jemalloc/internal/mb.h" 367#include "jemalloc/internal/bitmap.h" 368#include "jemalloc/internal/extent.h" 369#include "jemalloc/internal/arena.h" 370#include "jemalloc/internal/base.h" 371#include "jemalloc/internal/chunk.h" 372#include "jemalloc/internal/huge.h" 373#include "jemalloc/internal/rtree.h" 374#include "jemalloc/internal/tcache.h" 375#include "jemalloc/internal/hash.h" 376#include "jemalloc/internal/prof.h" 377 378#undef JEMALLOC_H_EXTERNS 379/******************************************************************************/ 380#define JEMALLOC_H_INLINES 381 382#include "jemalloc/internal/util.h" 383#include "jemalloc/internal/atomic.h" 384#include "jemalloc/internal/prng.h" 385#include "jemalloc/internal/ckh.h" 386#include "jemalloc/internal/size_classes.h" 387#include "jemalloc/internal/stats.h" 388#include "jemalloc/internal/ctl.h" 389#include "jemalloc/internal/mutex.h" 390#include "jemalloc/internal/tsd.h" 391#include "jemalloc/internal/mb.h" 392#include "jemalloc/internal/extent.h" 393#include "jemalloc/internal/base.h" 394#include "jemalloc/internal/chunk.h" 395#include "jemalloc/internal/huge.h" 396 397#ifndef JEMALLOC_ENABLE_INLINE 398malloc_tsd_protos(JEMALLOC_ATTR(unused), arenas, arena_t *) 399 400size_t s2u(size_t size); 401size_t sa2u(size_t size, size_t alignment, size_t *run_size_p); 402arena_t *choose_arena(void); 403#endif 404 405#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_C_)) 406/* 407 * Map of pthread_self() --> arenas[???], used for selecting an arena to use 408 * for allocations. 409 */ 410malloc_tsd_externs(arenas, arena_t *) 411malloc_tsd_funcs(JEMALLOC_INLINE, arenas, arena_t *, NULL, arenas_cleanup) 412 413/* 414 * Compute usable size that would result from allocating an object with the 415 * specified size. 416 */ 417JEMALLOC_INLINE size_t 418s2u(size_t size) 419{ 420 421 if (size <= SMALL_MAXCLASS) 422 return (arena_bin_info[SMALL_SIZE2BIN(size)].reg_size); 423 if (size <= arena_maxclass) 424 return (PAGE_CEILING(size)); 425 return (CHUNK_CEILING(size)); 426} 427 428/* 429 * Compute usable size that would result from allocating an object with the 430 * specified size and alignment. 431 */ 432JEMALLOC_INLINE size_t 433sa2u(size_t size, size_t alignment, size_t *run_size_p) 434{ 435 size_t usize; 436 437 /* 438 * Round size up to the nearest multiple of alignment. 439 * 440 * This done, we can take advantage of the fact that for each small 441 * size class, every object is aligned at the smallest power of two 442 * that is non-zero in the base two representation of the size. For 443 * example: 444 * 445 * Size | Base 2 | Minimum alignment 446 * -----+----------+------------------ 447 * 96 | 1100000 | 32 448 * 144 | 10100000 | 32 449 * 192 | 11000000 | 64 450 */ 451 usize = (size + (alignment - 1)) & (-alignment); 452 /* 453 * (usize < size) protects against the combination of maximal 454 * alignment and size greater than maximal alignment. 455 */ 456 if (usize < size) { 457 /* size_t overflow. */ 458 return (0); 459 } 460 461 if (usize <= arena_maxclass && alignment <= PAGE) { 462 if (usize <= SMALL_MAXCLASS) 463 return (arena_bin_info[SMALL_SIZE2BIN(usize)].reg_size); 464 return (PAGE_CEILING(usize)); 465 } else { 466 size_t run_size; 467 468 /* 469 * We can't achieve subpage alignment, so round up alignment 470 * permanently; it makes later calculations simpler. 471 */ 472 alignment = PAGE_CEILING(alignment); 473 usize = PAGE_CEILING(size); 474 /* 475 * (usize < size) protects against very large sizes within 476 * PAGE of SIZE_T_MAX. 477 * 478 * (usize + alignment < usize) protects against the 479 * combination of maximal alignment and usize large enough 480 * to cause overflow. This is similar to the first overflow 481 * check above, but it needs to be repeated due to the new 482 * usize value, which may now be *equal* to maximal 483 * alignment, whereas before we only detected overflow if the 484 * original size was *greater* than maximal alignment. 485 */ 486 if (usize < size || usize + alignment < usize) { 487 /* size_t overflow. */ 488 return (0); 489 } 490 491 /* 492 * Calculate the size of the over-size run that arena_palloc() 493 * would need to allocate in order to guarantee the alignment. 494 */ 495 if (usize >= alignment) 496 run_size = usize + alignment - PAGE; 497 else { 498 /* 499 * It is possible that (alignment << 1) will cause 500 * overflow, but it doesn't matter because we also 501 * subtract PAGE, which in the case of overflow leaves 502 * us with a very large run_size. That causes the 503 * first conditional below to fail, which means that 504 * the bogus run_size value never gets used for 505 * anything important. 506 */ 507 run_size = (alignment << 1) - PAGE; 508 } 509 if (run_size_p != NULL) 510 *run_size_p = run_size; 511 512 if (run_size <= arena_maxclass) 513 return (PAGE_CEILING(usize)); 514 return (CHUNK_CEILING(usize)); 515 } 516} 517 518/* Choose an arena based on a per-thread value. */ 519JEMALLOC_INLINE arena_t * 520choose_arena(void) 521{ 522 arena_t *ret; 523 524 if ((ret = *arenas_tsd_get()) == NULL) { 525 ret = choose_arena_hard(); 526 assert(ret != NULL); 527 } 528 529 return (ret); 530} 531#endif 532 533#include "jemalloc/internal/bitmap.h" 534#include "jemalloc/internal/rtree.h" 535#include "jemalloc/internal/tcache.h" 536#include "jemalloc/internal/arena.h" 537#include "jemalloc/internal/hash.h" 538 539#ifndef JEMALLOC_ENABLE_INLINE 540void *imalloc(size_t size); 541void *icalloc(size_t size); 542void *ipalloc(size_t usize, size_t alignment, bool zero); 543size_t isalloc(const void *ptr); 544size_t ivsalloc(const void *ptr); 545void idalloc(void *ptr); 546void *iralloc(void *ptr, size_t size, size_t extra, size_t alignment, 547 bool zero, bool no_move); 548malloc_tsd_protos(JEMALLOC_ATTR(unused), thread_allocated, thread_allocated_t) 549#endif 550 551#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_C_)) 552JEMALLOC_INLINE void * 553imalloc(size_t size) 554{ 555 556 assert(size != 0); 557 558 if (size <= arena_maxclass) 559 return (arena_malloc(size, false)); 560 else 561 return (huge_malloc(size, false)); 562} 563 564JEMALLOC_INLINE void * 565icalloc(size_t size) 566{ 567 568 if (size <= arena_maxclass) 569 return (arena_malloc(size, true)); 570 else 571 return (huge_malloc(size, true)); 572} 573 574JEMALLOC_INLINE void * 575ipalloc(size_t usize, size_t alignment, bool zero) 576{ 577 void *ret; 578 579 assert(usize != 0); 580 assert(usize == sa2u(usize, alignment, NULL)); 581 582 if (usize <= arena_maxclass && alignment <= PAGE) 583 ret = arena_malloc(usize, zero); 584 else { 585 size_t run_size JEMALLOC_CC_SILENCE_INIT(0); 586 587 /* 588 * Ideally we would only ever call sa2u() once per aligned 589 * allocation request, and the caller of this function has 590 * already done so once. However, it's rather burdensome to 591 * require every caller to pass in run_size, especially given 592 * that it's only relevant to large allocations. Therefore, 593 * just call it again here in order to get run_size. 594 */ 595 sa2u(usize, alignment, &run_size); 596 if (run_size <= arena_maxclass) { 597 ret = arena_palloc(choose_arena(), usize, run_size, 598 alignment, zero); 599 } else if (alignment <= chunksize) 600 ret = huge_malloc(usize, zero); 601 else 602 ret = huge_palloc(usize, alignment, zero); 603 } 604 605 assert(((uintptr_t)ret & (alignment - 1)) == 0); 606 return (ret); 607} 608 609JEMALLOC_INLINE size_t 610isalloc(const void *ptr) 611{ 612 size_t ret; 613 arena_chunk_t *chunk; 614 615 assert(ptr != NULL); 616 617 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 618 if (chunk != ptr) { 619 /* Region. */ 620 if (config_prof) 621 ret = arena_salloc_demote(ptr); 622 else 623 ret = arena_salloc(ptr); 624 } else 625 ret = huge_salloc(ptr); 626 627 return (ret); 628} 629 630JEMALLOC_INLINE size_t 631ivsalloc(const void *ptr) 632{ 633 634 /* Return 0 if ptr is not within a chunk managed by jemalloc. */ 635 if (rtree_get(chunks_rtree, (uintptr_t)CHUNK_ADDR2BASE(ptr)) == NULL) 636 return (0); 637 638 return (isalloc(ptr)); 639} 640 641JEMALLOC_INLINE void 642idalloc(void *ptr) 643{ 644 arena_chunk_t *chunk; 645 646 assert(ptr != NULL); 647 648 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr); 649 if (chunk != ptr) 650 arena_dalloc(chunk->arena, chunk, ptr); 651 else 652 huge_dalloc(ptr, true); 653} 654 655JEMALLOC_INLINE void * 656iralloc(void *ptr, size_t size, size_t extra, size_t alignment, bool zero, 657 bool no_move) 658{ 659 void *ret; 660 size_t oldsize; 661 662 assert(ptr != NULL); 663 assert(size != 0); 664 665 oldsize = isalloc(ptr); 666 667 if (alignment != 0 && ((uintptr_t)ptr & ((uintptr_t)alignment-1)) 668 != 0) { 669 size_t usize, copysize; 670 671 /* 672 * Existing object alignment is inadquate; allocate new space 673 * and copy. 674 */ 675 if (no_move) 676 return (NULL); 677 usize = sa2u(size + extra, alignment, NULL); 678 if (usize == 0) 679 return (NULL); 680 ret = ipalloc(usize, alignment, zero); 681 if (ret == NULL) { 682 if (extra == 0) 683 return (NULL); 684 /* Try again, without extra this time. */ 685 usize = sa2u(size, alignment, NULL); 686 if (usize == 0) 687 return (NULL); 688 ret = ipalloc(usize, alignment, zero); 689 if (ret == NULL) 690 return (NULL); 691 } 692 /* 693 * Copy at most size bytes (not size+extra), since the caller 694 * has no expectation that the extra bytes will be reliably 695 * preserved. 696 */ 697 copysize = (size < oldsize) ? size : oldsize; 698 memcpy(ret, ptr, copysize); 699 idalloc(ptr); 700 return (ret); 701 } 702 703 if (no_move) { 704 if (size <= arena_maxclass) { 705 return (arena_ralloc_no_move(ptr, oldsize, size, 706 extra, zero)); 707 } else { 708 return (huge_ralloc_no_move(ptr, oldsize, size, 709 extra)); 710 } 711 } else { 712 if (size + extra <= arena_maxclass) { 713 return (arena_ralloc(ptr, oldsize, size, extra, 714 alignment, zero)); 715 } else { 716 return (huge_ralloc(ptr, oldsize, size, extra, 717 alignment, zero)); 718 } 719 } 720} 721 722malloc_tsd_externs(thread_allocated, thread_allocated_t) 723malloc_tsd_funcs(JEMALLOC_INLINE, thread_allocated, thread_allocated_t, 724 THREAD_ALLOCATED_INITIALIZER, malloc_tsd_no_cleanup) 725#endif 726 727#include "jemalloc/internal/prof.h" 728 729#undef JEMALLOC_H_INLINES 730/******************************************************************************/ 731