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