282#endif
283
284/* sizeof(int) == (1 << SIZEOF_INT_2POW). */
285#ifndef SIZEOF_INT_2POW
286# define SIZEOF_INT_2POW 2
287#endif
288
289/* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
290#if (!defined(PIC) && !defined(NO_TLS))
291# define NO_TLS
292#endif
293
294/*
295 * Size and alignment of memory chunks that are allocated by the OS's virtual
296 * memory system.
297 *
298 * chunksize limits:
299 *
300 * 2^(pagesize_2pow - 1 + RUN_MIN_REGS_2POW) <= chunk_size <= 2^28
301 */
302#define CHUNK_2POW_DEFAULT 21
303#define CHUNK_2POW_MAX 28
304
305/*
306 * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
307 * so over-estimates are okay (up to a point), but under-estimates will
308 * negatively affect performance.
309 */
310#define CACHELINE_2POW 6
311#define CACHELINE ((size_t)(1 << CACHELINE_2POW))
312
313/*
314 * Maximum size class that is a multiple of the quantum, but not (necessarily)
315 * a power of 2. Above this size, allocations are rounded up to the nearest
316 * power of 2.
317 */
318#define SMALL_MAX_2POW_DEFAULT 9
319#define SMALL_MAX_DEFAULT (1 << SMALL_MAX_2POW_DEFAULT)
320
321/*
322 * Minimum number of regions that must fit into a run that serves quantum-size
323 * bin allocations.
324 *
325 * Note that if this is set too low, space will be wasted if there are size
326 * classes that are small enough that RUN_MIN_REGS regions don't fill a page.
327 * If this is set too high, then the overhead of searching through the bitmap
328 * that tracks region usage will become excessive.
329 */
330#define RUN_MIN_REGS_2POW 10
331#define RUN_MIN_REGS (1 << RUN_MIN_REGS_2POW)
332
333/*
334 * Maximum number of pages for a run that is used for bin allocations.
335 *
336 * Note that if this is set too low, then fragmentation for the largest bin
337 * size classes will be high. If this is set too high, then even small
338 * programs will often have to allocate more than two chunks early on.
339 */
340#define RUN_MAX_PAGES_2POW 4
341#define RUN_MAX_PAGES (1 << RUN_MAX_PAGES_2POW)
342
343/******************************************************************************/
344
345/*
346 * Mutexes based on spinlocks. We can't use normal pthread mutexes, because
347 * they require malloc()ed memory.
348 */
349typedef struct {
350 spinlock_t lock;
351} malloc_mutex_t;
352
353/* Set to true once the allocator has been initialized. */
354static bool malloc_initialized = false;
355
356/* Used to avoid initialization races. */
357static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
358
359/******************************************************************************/
360/*
361 * Statistics data structures.
362 */
363
364#ifdef MALLOC_STATS
365
366typedef struct malloc_bin_stats_s malloc_bin_stats_t;
367struct malloc_bin_stats_s {
368 /*
369 * Number of allocation requests that corresponded to the size of this
370 * bin.
371 */
372 uint64_t nrequests;
373
374 /* Total number of runs created for this bin's size class. */
375 uint64_t nruns;
376
377 /*
378 * Total number of run promotions/demotions for this bin's size class.
379 */
380 uint64_t npromote;
381 uint64_t ndemote;
382
383 /* High-water mark for this bin. */
384 unsigned long highruns;
385
386 /* Current number of runs in this bin. */
387 unsigned long curruns;
388};
389
390typedef struct arena_stats_s arena_stats_t;
391struct arena_stats_s {
392 /* Total byte count of allocated memory, not including overhead. */
393 size_t allocated;
394
395 /* Number of times each function was called. */
396 uint64_t nmalloc;
397 uint64_t ndalloc;
398 uint64_t nmadvise;
399
400 /* Number of large allocation requests. */
401 uint64_t large_nrequests;
402};
403
404typedef struct chunk_stats_s chunk_stats_t;
405struct chunk_stats_s {
406 /* Number of chunks that were allocated. */
407 uint64_t nchunks;
408
409 /* High-water mark for number of chunks allocated. */
410 unsigned long highchunks;
411
412 /*
413 * Current number of chunks allocated. This value isn't maintained for
414 * any other purpose, so keep track of it in order to be able to set
415 * highchunks.
416 */
417 unsigned long curchunks;
418};
419
420#endif /* #ifdef MALLOC_STATS */
421
422/******************************************************************************/
423/*
424 * Chunk data structures.
425 */
426
427/* Tree of chunks. */
428typedef struct chunk_node_s chunk_node_t;
429struct chunk_node_s {
430 /* Linkage for the chunk tree. */
431 RB_ENTRY(chunk_node_s) link;
432
433 /*
434 * Pointer to the chunk that this tree node is responsible for. In some
435 * (but certainly not all) cases, this data structure is placed at the
436 * beginning of the corresponding chunk, so this field may point to this
437 * node.
438 */
439 void *chunk;
440
441 /* Total chunk size. */
442 size_t size;
443};
444typedef struct chunk_tree_s chunk_tree_t;
445RB_HEAD(chunk_tree_s, chunk_node_s);
446
447/******************************************************************************/
448/*
449 * Arena data structures.
450 */
451
452typedef struct arena_s arena_t;
453typedef struct arena_bin_s arena_bin_t;
454
455typedef struct arena_chunk_map_s arena_chunk_map_t;
456struct arena_chunk_map_s {
457 bool free:1;
458 bool large:1;
459 unsigned npages:15; /* Limiting factor for CHUNK_2POW_MAX. */
460 unsigned pos:15;
461};
462
463/* Arena chunk header. */
464typedef struct arena_chunk_s arena_chunk_t;
465struct arena_chunk_s {
466 /* Arena that owns the chunk. */
467 arena_t *arena;
468
469 /* Linkage for the arena's chunk tree. */
470 RB_ENTRY(arena_chunk_s) link;
471
472 /*
473 * Number of pages in use. This is maintained in order to make
474 * detection of empty chunks fast.
475 */
476 uint32_t pages_used;
477
478 /*
479 * Array of counters that keeps track of how many free runs of each
480 * size are available in this chunk. This table is sized at compile
481 * time, which is wasteful. However, due to unrelated rounding, this
482 * doesn't actually waste any otherwise useful space.
483 *
484 * index == 2^n pages
485 *
486 * index | npages
487 * ------+-------
488 * 0 | 1
489 * 1 | 2
490 * 2 | 4
491 * 3 | 8
492 * :
493 */
494 uint32_t nfree_runs[CHUNK_2POW_MAX/* - PAGE_SHIFT */];
495
496 /* Map of pages within chunk that keeps track of free/large/small. */
497 arena_chunk_map_t map[1]; /* Dynamically sized. */
498};
499typedef struct arena_chunk_tree_s arena_chunk_tree_t;
500RB_HEAD(arena_chunk_tree_s, arena_chunk_s);
501
502typedef struct arena_run_s arena_run_t;
503struct arena_run_s {
504 /* Linkage for run rings. */
505 qr(arena_run_t) link;
506
507#ifdef MALLOC_DEBUG
508 uint32_t magic;
509# define ARENA_RUN_MAGIC 0x384adf93
510#endif
511
512 /* Bin this run is associated with. */
513 arena_bin_t *bin;
514
515 /* Bitmask of in-use regions (0: in use, 1: free). */
516#define REGS_MASK_NELMS \
517 (1 << (RUN_MIN_REGS_2POW - SIZEOF_INT_2POW - 2))
518 unsigned regs_mask[REGS_MASK_NELMS];
519
520 /* Index of first element that might have a free region. */
521 unsigned regs_minelm;
522
523 /* Number of free regions in run. */
524 unsigned nfree;
525
526 /*
527 * Current quartile for this run, one of: {RUN_QINIT, RUN_Q0, RUN_25,
528 * RUN_Q50, RUN_Q75, RUN_Q100}.
529 */
530#define RUN_QINIT 0
531#define RUN_Q0 1
532#define RUN_Q25 2
533#define RUN_Q50 3
534#define RUN_Q75 4
535#define RUN_Q100 5
536 unsigned quartile;
537
538 /*
539 * Limits on the number of free regions for the fullness quartile this
540 * run is currently in. If nfree goes outside these limits, the run
541 * is moved to a different fullness quartile.
542 */
543 unsigned free_max;
544 unsigned free_min;
545};
546
547/* Used for run ring headers, where the run isn't actually used. */
548typedef struct arena_run_link_s arena_run_link_t;
549struct arena_run_link_s {
550 /* Linkage for run rings. */
551 qr(arena_run_t) link;
552};
553
554struct arena_bin_s {
555 /*
556 * Current run being used to service allocations of this bin's size
557 * class.
558 */
559 arena_run_t *runcur;
560
561 /*
562 * Links into rings of runs, of various fullnesses (names indicate
563 * approximate lower bounds). A new run conceptually starts off in
564 * runsinit, and it isn't inserted into the runs0 ring until it
565 * reaches 25% full (hysteresis mechanism). For the run to be moved
566 * again, it must become either empty or 50% full. Thus, each ring
567 * contains runs that are within 50% above the advertised fullness for
568 * the ring. This provides a low-overhead mechanism for segregating
569 * runs into approximate fullness classes.
570 *
571 * Conceptually, there is a runs100 that contains completely full runs.
572 * Since we don't need to search for these runs though, no runs100 ring
573 * is actually maintained.
574 *
575 * These rings are useful when looking for an existing run to use when
576 * runcur is no longer usable. We look for usable runs in the
577 * following order:
578 *
579 * 1) runs50
580 * 2) runs25
581 * 3) runs0
582 * 4) runs75
583 *
584 * runs75 isn't a good place to look, because it contains runs that may
585 * be nearly completely full. Still, we look there as a last resort in
586 * order to avoid allocating a new run if at all possible.
587 */
588 /* arena_run_link_t runsinit; 0% <= fullness < 25% */
589 arena_run_link_t runs0; /* 0% < fullness < 50% */
590 arena_run_link_t runs25; /* 25% < fullness < 75% */
591 arena_run_link_t runs50; /* 50% < fullness < 100% */
592 arena_run_link_t runs75; /* 75% < fullness < 100% */
593 /* arena_run_link_t runs100; fullness == 100% */
594
595 /* Size of regions in a run for this bin's size class. */
596 size_t reg_size;
597
598 /* Total size of a run for this bin's size class. */
599 size_t run_size;
600
601 /* Total number of regions in a run for this bin's size class. */
602 uint32_t nregs;
603
604 /* Offset of first region in a run for this bin's size class. */
605 uint32_t reg0_offset;
606
607#ifdef MALLOC_STATS
608 /* Bin statistics. */
609 malloc_bin_stats_t stats;
610#endif
611};
612
613struct arena_s {
614#ifdef MALLOC_DEBUG
615 uint32_t magic;
616# define ARENA_MAGIC 0x947d3d24
617#endif
618
619 /* All operations on this arena require that mtx be locked. */
620 malloc_mutex_t mtx;
621
622#ifdef MALLOC_STATS
623 arena_stats_t stats;
624#endif
625
626 /*
627 * Tree of chunks this arena manages.
628 */
629 arena_chunk_tree_t chunks;
630
631 /*
632 * bins is used to store rings of free regions of the following sizes,
633 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
634 *
635 * bins[i] | size |
636 * --------+------+
637 * 0 | 2 |
638 * 1 | 4 |
639 * 2 | 8 |
640 * --------+------+
641 * 3 | 16 |
642 * 4 | 32 |
643 * 5 | 48 |
644 * 6 | 64 |
645 * : :
646 * : :
647 * 33 | 496 |
648 * 34 | 512 |
649 * --------+------+
650 * 35 | 1024 |
651 * 36 | 2048 |
652 * --------+------+
653 */
654 arena_bin_t bins[1]; /* Dynamically sized. */
655};
656
657/******************************************************************************/
658/*
659 * Data.
660 */
661
662/* Number of CPUs. */
663static unsigned ncpus;
664
665/* VM page size. */
666static unsigned pagesize;
667static unsigned pagesize_2pow;
668
669/* Various bin-related settings. */
670static size_t bin_maxclass; /* Max size class for bins. */
671static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */
672static unsigned nqbins; /* Number of quantum-spaced bins. */
673static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */
674static size_t small_min;
675static size_t small_max;
676static unsigned tiny_min_2pow;
677
678/* Various quantum-related settings. */
679static size_t quantum;
680static size_t quantum_mask; /* (quantum - 1). */
681
682/* Various chunk-related settings. */
683static size_t chunk_size;
684static size_t chunk_size_mask; /* (chunk_size - 1). */
685static size_t arena_maxclass; /* Max size class for arenas. */
686static unsigned arena_chunk_maplen;
687
688/********/
689/*
690 * Chunks.
691 */
692
693/* Protects chunk-related data structures. */
694static malloc_mutex_t chunks_mtx;
695
696/* Tree of chunks that are stand-alone huge allocations. */
697static chunk_tree_t huge;
698
699#ifdef USE_BRK
700/*
701 * Try to use brk for chunk-size allocations, due to address space constraints.
702 */
703/* Result of first sbrk(0) call. */
704static void *brk_base;
705/* Current end of brk, or ((void *)-1) if brk is exhausted. */
706static void *brk_prev;
707/* Current upper limit on brk addresses. */
708static void *brk_max;
709#endif
710
711#ifdef MALLOC_STATS
712/*
713 * Byte counters for allocated/total space used by the chunks in the huge
714 * allocations tree.
715 */
716static uint64_t huge_nmalloc;
717static uint64_t huge_ndalloc;
718static size_t huge_allocated;
719#endif
720
721/*
722 * Tree of chunks that were previously allocated. This is used when allocating
723 * chunks, in an attempt to re-use address space.
724 */
725static chunk_tree_t old_chunks;
726
727/****************************/
728/*
729 * base (internal allocation).
730 */
731
732/*
733 * Current chunk that is being used for internal memory allocations. This
734 * chunk is carved up in cacheline-size quanta, so that there is no chance of
735 * false cache line sharing.
736 */
737static void *base_chunk;
738static void *base_next_addr;
739static void *base_past_addr; /* Addr immediately past base_chunk. */
740static chunk_node_t *base_chunk_nodes; /* LIFO cache of chunk nodes. */
741static malloc_mutex_t base_mtx;
742#ifdef MALLOC_STATS
743static uint64_t base_total;
744#endif
745
746/********/
747/*
748 * Arenas.
749 */
750
751/*
752 * Arenas that are used to service external requests. Not all elements of the
753 * arenas array are necessarily used; arenas are created lazily as needed.
754 */
755static arena_t **arenas;
756static unsigned narenas;
757#ifndef NO_TLS
758static unsigned next_arena;
759#endif
760static malloc_mutex_t arenas_mtx; /* Protects arenas initialization. */
761
762#ifndef NO_TLS
763/*
764 * Map of pthread_self() --> arenas[???], used for selecting an arena to use
765 * for allocations.
766 */
767static __thread arena_t *arenas_map;
768#endif
769
770#ifdef MALLOC_STATS
771/* Chunk statistics. */
772static chunk_stats_t stats_chunks;
773#endif
774
775/*******************************/
776/*
777 * Runtime configuration options.
778 */
779const char *_malloc_options;
780
781#ifndef NO_MALLOC_EXTRAS
782static bool opt_abort = true;
783static bool opt_junk = true;
784#else
785static bool opt_abort = false;
786static bool opt_junk = false;
787#endif
788static bool opt_hint = false;
789static bool opt_print_stats = false;
790static size_t opt_quantum_2pow = QUANTUM_2POW_MIN;
791static size_t opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
792static size_t opt_chunk_2pow = CHUNK_2POW_DEFAULT;
793static bool opt_utrace = false;
794static bool opt_sysv = false;
795static bool opt_xmalloc = false;
796static bool opt_zero = false;
797static int32_t opt_narenas_lshift = 0;
798
799typedef struct {
800 void *p;
801 size_t s;
802 void *r;
803} malloc_utrace_t;
804
805#define UTRACE(a, b, c) \
806 if (opt_utrace) { \
807 malloc_utrace_t ut = {a, b, c}; \
808 utrace(&ut, sizeof(ut)); \
809 }
810
811/******************************************************************************/
812/*
813 * Begin function prototypes for non-inline static functions.
814 */
815
816static void malloc_mutex_init(malloc_mutex_t *a_mutex);
817static void wrtmessage(const char *p1, const char *p2, const char *p3,
818 const char *p4);
819static void malloc_printf(const char *format, ...);
820static void *base_alloc(size_t size);
821static chunk_node_t *base_chunk_node_alloc(void);
822static void base_chunk_node_dealloc(chunk_node_t *node);
823#ifdef MALLOC_STATS
824static void stats_print(arena_t *arena);
825#endif
826static void *pages_map(void *addr, size_t size);
827static void pages_unmap(void *addr, size_t size);
828static void *chunk_alloc(size_t size);
829static void chunk_dealloc(void *chunk, size_t size);
830#ifndef NO_TLS
831static arena_t *choose_arena_hard(void);
832#endif
833static void arena_run_split(arena_t *arena, arena_run_t *run, bool large,
834 size_t size);
835static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
836static void arena_chunk_dealloc(arena_chunk_t *chunk);
837static void arena_bin_run_promote(arena_t *arena, arena_bin_t *bin,
838 arena_run_t *run);
839static void arena_bin_run_demote(arena_t *arena, arena_bin_t *bin,
840 arena_run_t *run);
841static arena_run_t *arena_run_alloc(arena_t *arena, bool large, size_t size);
842static void arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size);
843static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
844static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
845static void *arena_malloc(arena_t *arena, size_t size);
846static size_t arena_salloc(const void *ptr);
847static void *arena_ralloc(void *ptr, size_t size, size_t oldsize);
848static void arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
849static bool arena_new(arena_t *arena);
850static arena_t *arenas_extend(unsigned ind);
851static void *huge_malloc(size_t size);
852static void *huge_ralloc(void *ptr, size_t size, size_t oldsize);
853static void huge_dalloc(void *ptr);
854static void *imalloc(size_t size);
855static void *ipalloc(size_t alignment, size_t size);
856static void *icalloc(size_t size);
857static size_t isalloc(const void *ptr);
858static void *iralloc(void *ptr, size_t size);
859static void idalloc(void *ptr);
860static void malloc_print_stats(void);
861static bool malloc_init_hard(void);
862
863/*
864 * End function prototypes.
865 */
866/******************************************************************************/
867/*
868 * Begin mutex.
869 */
870
871static void
872malloc_mutex_init(malloc_mutex_t *a_mutex)
873{
874 static const spinlock_t lock = _SPINLOCK_INITIALIZER;
875
876 a_mutex->lock = lock;
877}
878
879static inline void
880malloc_mutex_lock(malloc_mutex_t *a_mutex)
881{
882
883 if (__isthreaded)
884 _SPINLOCK(&a_mutex->lock);
885}
886
887static inline void
888malloc_mutex_unlock(malloc_mutex_t *a_mutex)
889{
890
891 if (__isthreaded)
892 _SPINUNLOCK(&a_mutex->lock);
893}
894
895/*
896 * End mutex.
897 */
898/******************************************************************************/
899/*
900 * Begin Utility functions/macros.
901 */
902
903/* Return the chunk address for allocation address a. */
904#define CHUNK_ADDR2BASE(a) \
905 ((void *)((uintptr_t)(a) & ~chunk_size_mask))
906
907/* Return the chunk offset of address a. */
908#define CHUNK_ADDR2OFFSET(a) \
909 ((size_t)((uintptr_t)(a) & chunk_size_mask))
910
911/* Return the smallest chunk multiple that is >= s. */
912#define CHUNK_CEILING(s) \
913 (((s) + chunk_size_mask) & ~chunk_size_mask)
914
915/* Return the smallest cacheline multiple that is >= s. */
916#define CACHELINE_CEILING(s) \
917 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
918
919/* Return the smallest quantum multiple that is >= a. */
920#define QUANTUM_CEILING(a) \
921 (((a) + quantum_mask) & ~quantum_mask)
922
923/* Compute the smallest power of 2 that is >= x. */
924static inline size_t
925pow2_ceil(size_t x)
926{
927
928 x--;
929 x |= x >> 1;
930 x |= x >> 2;
931 x |= x >> 4;
932 x |= x >> 8;
933 x |= x >> 16;
934#if (SIZEOF_PTR == 8)
935 x |= x >> 32;
936#endif
937 x++;
938 return (x);
939}
940
941static void
942wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
943{
944
945 _write(STDERR_FILENO, p1, strlen(p1));
946 _write(STDERR_FILENO, p2, strlen(p2));
947 _write(STDERR_FILENO, p3, strlen(p3));
948 _write(STDERR_FILENO, p4, strlen(p4));
949}
950
951void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
952 const char *p4) = wrtmessage;
953
954/*
955 * Print to stderr in such a way as to (hopefully) avoid memory allocation.
956 */
957static void
958malloc_printf(const char *format, ...)
959{
960 char buf[4096];
961 va_list ap;
962
963 va_start(ap, format);
964 vsnprintf(buf, sizeof(buf), format, ap);
965 va_end(ap);
966 _malloc_message(buf, "", "", "");
967}
968
969/******************************************************************************/
970
971static void *
972base_alloc(size_t size)
973{
974 void *ret;
975 size_t csize;
976
977 /* Round size up to nearest multiple of the cacheline size. */
978 csize = CACHELINE_CEILING(size);
979
980 malloc_mutex_lock(&base_mtx);
981
982 /* Make sure there's enough space for the allocation. */
983 if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
984 void *tchunk;
985
986 assert(csize <= chunk_size);
987
988 tchunk = chunk_alloc(chunk_size);
989 if (tchunk == NULL) {
990 ret = NULL;
991 goto RETURN;
992 }
993 base_chunk = tchunk;
994 base_next_addr = (void *)base_chunk;
995 base_past_addr = (void *)((uintptr_t)base_chunk + chunk_size);
996#ifdef MALLOC_STATS
997 base_total += chunk_size;
998#endif
999 }
1000
1001 /* Allocate. */
1002 ret = base_next_addr;
1003 base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1004
1005RETURN:
1006 malloc_mutex_unlock(&base_mtx);
1007 return (ret);
1008}
1009
1010static chunk_node_t *
1011base_chunk_node_alloc(void)
1012{
1013 chunk_node_t *ret;
1014
1015 malloc_mutex_lock(&base_mtx);
1016 if (base_chunk_nodes != NULL) {
1017 ret = base_chunk_nodes;
1018 base_chunk_nodes = *(chunk_node_t **)ret;
1019 malloc_mutex_unlock(&base_mtx);
1020 } else {
1021 malloc_mutex_unlock(&base_mtx);
1022 ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t));
1023 }
1024
1025 return (ret);
1026}
1027
1028static void
1029base_chunk_node_dealloc(chunk_node_t *node)
1030{
1031
1032 malloc_mutex_lock(&base_mtx);
1033 *(chunk_node_t **)node = base_chunk_nodes;
1034 base_chunk_nodes = node;
1035 malloc_mutex_unlock(&base_mtx);
1036}
1037
1038/******************************************************************************/
1039
1040#ifdef MALLOC_STATS
1041static void
1042stats_print(arena_t *arena)
1043{
1044 unsigned i;
1045 int gap_start;
1046
1047 malloc_printf("allocated: %zu\n", arena->stats.allocated);
1048
1049 malloc_printf("calls:\n");
1050 malloc_printf(" %12s %12s %12s\n", "nmalloc","ndalloc", "nmadvise");
1051 malloc_printf(" %12llu %12llu %12llu\n",
1052 arena->stats.nmalloc, arena->stats.ndalloc, arena->stats.nmadvise);
1053
1054 malloc_printf("large requests: %llu\n", arena->stats.large_nrequests);
1055
1056 malloc_printf("bins:\n");
1057 malloc_printf("%13s %1s %4s %5s %6s %9s %5s %6s %7s %6s %6s\n",
1058 "bin", "", "size", "nregs", "run_sz", "nrequests", "nruns",
1059 "hiruns", "curruns", "npromo", "ndemo");
1060 for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
1061 if (arena->bins[i].stats.nrequests == 0) {
1062 if (gap_start == -1)
1063 gap_start = i;
1064 } else {
1065 if (gap_start != -1) {
1066 if (i > gap_start + 1) {
1067 /* Gap of more than one size class. */
1068 malloc_printf("[%u..%u]\n",
1069 gap_start, i - 1);
1070 } else {
1071 /* Gap of one size class. */
1072 malloc_printf("[%u]\n", gap_start);
1073 }
1074 gap_start = -1;
1075 }
1076 malloc_printf(
1077 "%13u %1s %4u %5u %6u %9llu %5llu"
1078 " %6lu %7lu %6llu %6llu\n",
1079 i,
1080 i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
1081 arena->bins[i].reg_size,
1082 arena->bins[i].nregs,
1083 arena->bins[i].run_size,
1084 arena->bins[i].stats.nrequests,
1085 arena->bins[i].stats.nruns,
1086 arena->bins[i].stats.highruns,
1087 arena->bins[i].stats.curruns,
1088 arena->bins[i].stats.npromote,
1089 arena->bins[i].stats.ndemote);
1090 }
1091 }
1092 if (gap_start != -1) {
1093 if (i > gap_start + 1) {
1094 /* Gap of more than one size class. */
1095 malloc_printf("[%u..%u]\n", gap_start, i - 1);
1096 } else {
1097 /* Gap of one size class. */
1098 malloc_printf("[%u]\n", gap_start);
1099 }
1100 }
1101}
1102#endif
1103
1104/*
1105 * End Utility functions/macros.
1106 */
1107/******************************************************************************/
1108/*
1109 * Begin chunk management functions.
1110 */
1111
1112static inline int
1113chunk_comp(chunk_node_t *a, chunk_node_t *b)
1114{
1115
1116 assert(a != NULL);
1117 assert(b != NULL);
1118
1119 if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
1120 return (-1);
1121 else if (a->chunk == b->chunk)
1122 return (0);
1123 else
1124 return (1);
1125}
1126
1127/* Generate red-black tree code for chunks. */
1128RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);
1129
1130static void *
1131pages_map(void *addr, size_t size)
1132{
1133 void *ret;
1134
1135 /*
1136 * We don't use MAP_FIXED here, because it can cause the *replacement*
1137 * of existing mappings, and we only want to create new mappings.
1138 */
1139 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON,
1140 -1, 0);
1141 assert(ret != NULL);
1142
1143 if (ret == MAP_FAILED)
1144 ret = NULL;
1145 else if (addr != NULL && ret != addr) {
1146 /*
1147 * We succeeded in mapping memory, but not in the right place.
1148 */
1149 if (munmap(ret, size) == -1) {
1150 char buf[STRERROR_BUF];
1151
1152 strerror_r(errno, buf, sizeof(buf));
1153 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1154 _getprogname(), buf);
1155 if (opt_abort)
1156 abort();
1157 }
1158 ret = NULL;
1159 }
1160
1161 assert(ret == NULL || (addr == NULL && ret != addr)
1162 || (addr != NULL && ret == addr));
1163 return (ret);
1164}
1165
1166static void
1167pages_unmap(void *addr, size_t size)
1168{
1169
1170 if (munmap(addr, size) == -1) {
1171 char buf[STRERROR_BUF];
1172
1173 strerror_r(errno, buf, sizeof(buf));
1174 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1175 _getprogname(), buf);
1176 if (opt_abort)
1177 abort();
1178 }
1179}
1180
1181static void *
1182chunk_alloc(size_t size)
1183{
1184 void *ret, *chunk;
1185 chunk_node_t *tchunk, *delchunk;
1186
1187 assert(size != 0);
1188 assert(size % chunk_size == 0);
1189
1190 malloc_mutex_lock(&chunks_mtx);
1191
1192 if (size == chunk_size) {
1193 /*
1194 * Check for address ranges that were previously chunks and try
1195 * to use them.
1196 */
1197
1198 tchunk = RB_MIN(chunk_tree_s, &old_chunks);
1199 while (tchunk != NULL) {
1200 /* Found an address range. Try to recycle it. */
1201
1202 chunk = tchunk->chunk;
1203 delchunk = tchunk;
1204 tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
1205
1206 /* Remove delchunk from the tree. */
1207 RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
1208 base_chunk_node_dealloc(delchunk);
1209
1210#ifdef USE_BRK
1211 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1212 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1213 /* Re-use a previously freed brk chunk. */
1214 ret = chunk;
1215 goto RETURN;
1216 }
1217#endif
1218 if ((ret = pages_map(chunk, size)) != NULL) {
1219 /* Success. */
1220 goto RETURN;
1221 }
1222 }
1223 }
1224
1225#ifdef USE_BRK
1226 /*
1227 * Try to create allocations in brk, in order to make full use of
1228 * limited address space.
1229 */
1230 if (brk_prev != (void *)-1) {
1231 void *brk_cur;
1232 intptr_t incr;
1233
1234 /*
1235 * The loop is necessary to recover from races with other
1236 * threads that are using brk for something other than malloc.
1237 */
1238 do {
1239 /* Get the current end of brk. */
1240 brk_cur = sbrk(0);
1241
1242 /*
1243 * Calculate how much padding is necessary to
1244 * chunk-align the end of brk.
1245 */
1246 incr = (intptr_t)size
1247 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
1248 if (incr == size) {
1249 ret = brk_cur;
1250 } else {
1251 ret = (void *)(intptr_t)brk_cur + incr;
1252 incr += size;
1253 }
1254
1255 brk_prev = sbrk(incr);
1256 if (brk_prev == brk_cur) {
1257 /* Success. */
1258 brk_max = (void *)(intptr_t)ret + size;
1259 goto RETURN;
1260 }
1261 } while (brk_prev != (void *)-1);
1262 }
1263#endif
1264
1265 /*
1266 * Try to over-allocate, but allow the OS to place the allocation
1267 * anywhere. Beware of size_t wrap-around.
1268 */
1269 if (size + chunk_size > size) {
1270 if ((ret = pages_map(NULL, size + chunk_size)) != NULL) {
1271 size_t offset = CHUNK_ADDR2OFFSET(ret);
1272
1273 /*
1274 * Success. Clean up unneeded leading/trailing space.
1275 */
1276 if (offset != 0) {
1277 /* Leading space. */
1278 pages_unmap(ret, chunk_size - offset);
1279
1280 ret = (void *)((uintptr_t)ret + (chunk_size -
1281 offset));
1282
1283 /* Trailing space. */
1284 pages_unmap((void *)((uintptr_t)ret + size),
1285 offset);
1286 } else {
1287 /* Trailing space only. */
1288 pages_unmap((void *)((uintptr_t)ret + size),
1289 chunk_size);
1290 }
1291 goto RETURN;
1292 }
1293 }
1294
1295 /* All strategies for allocation failed. */
1296 ret = NULL;
1297RETURN:
1298#ifdef MALLOC_STATS
1299 if (ret != NULL) {
1300 stats_chunks.nchunks += (size / chunk_size);
1301 stats_chunks.curchunks += (size / chunk_size);
1302 }
1303 if (stats_chunks.curchunks > stats_chunks.highchunks)
1304 stats_chunks.highchunks = stats_chunks.curchunks;
1305#endif
1306 malloc_mutex_unlock(&chunks_mtx);
1307
1308 assert(CHUNK_ADDR2BASE(ret) == ret);
1309 return (ret);
1310}
1311
1312static void
1313chunk_dealloc(void *chunk, size_t size)
1314{
1315 size_t offset;
1316 chunk_node_t key;
1317 chunk_node_t *node;
1318
1319 assert(chunk != NULL);
1320 assert(CHUNK_ADDR2BASE(chunk) == chunk);
1321 assert(size != 0);
1322 assert(size % chunk_size == 0);
1323
1324 malloc_mutex_lock(&chunks_mtx);
1325
1326#ifdef USE_BRK
1327 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1328 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1329 void *brk_cur;
1330
1331 /* Get the current end of brk. */
1332 brk_cur = sbrk(0);
1333
1334 /*
1335 * Try to shrink the data segment if this chunk is at the end
1336 * of the data segment. The sbrk() call here is subject to a
1337 * race condition with threads that use brk(2) or sbrk(2)
1338 * directly, but the alternative would be to leak memory for
1339 * the sake of poorly designed multi-threaded programs.
1340 */
1341 if (brk_cur == brk_max
1342 && (void *)(uintptr_t)chunk + size == brk_max
1343 && sbrk(-(intptr_t)size) == brk_max) {
1344 if (brk_prev == brk_max) {
1345 /* Success. */
1346 brk_prev = (void *)(intptr_t)brk_max
1347 - (intptr_t)size;
1348 brk_max = brk_prev;
1349 }
1350 goto RETURN;
1351 } else
1352 madvise(chunk, size, MADV_FREE);
1353 } else
1354#endif
1355 pages_unmap(chunk, size);
1356
1357 /*
1358 * Iteratively create records of each chunk-sized memory region that
1359 * 'chunk' is comprised of, so that the address range can be recycled
1360 * if memory usage increases later on.
1361 */
1362 for (offset = 0; offset < size; offset += chunk_size) {
1363 /*
1364 * It is possible for chunk to overlap existing entries in
1365 * old_chunks if it is a huge allocation, so take care to not
1366 * leak tree nodes.
1367 */
1368 key.chunk = (void *)((uintptr_t)chunk + (uintptr_t)offset);
1369 if (RB_FIND(chunk_tree_s, &old_chunks, &key) == NULL) {
1370 node = base_chunk_node_alloc();
1371 if (node == NULL)
1372 break;
1373
1374 node->chunk = key.chunk;
1375 node->size = chunk_size;
1376 RB_INSERT(chunk_tree_s, &old_chunks, node);
1377 }
1378 }
1379
1380#ifdef USE_BRK
1381RETURN:
1382#endif
1383#ifdef MALLOC_STATS
1384 stats_chunks.curchunks -= (size / chunk_size);
1385#endif
1386 malloc_mutex_unlock(&chunks_mtx);
1387}
1388
1389/*
1390 * End chunk management functions.
1391 */
1392/******************************************************************************/
1393/*
1394 * Begin arena.
1395 */
1396
1397/*
1398 * Choose an arena based on a per-thread value (fast-path code, calls slow-path
1399 * code if necessary.
1400 */
1401static inline arena_t *
1402choose_arena(void)
1403{
1404 arena_t *ret;
1405
1406 /*
1407 * We can only use TLS if this is a PIC library, since for the static
1408 * library version, libc's malloc is used by TLS allocation, which
1409 * introduces a bootstrapping issue.
1410 */
1411#ifndef NO_TLS
1412 if (__isthreaded == false) {
1413 /*
1414 * Avoid the overhead of TLS for single-threaded operation. If the
1415 * app switches to threaded mode, the initial thread may end up
1416 * being assigned to some other arena, but this one-time switch
1417 * shouldn't cause significant issues.
1418 * */
1419 return (arenas[0]);
1420 }
1421
1422 ret = arenas_map;
1423 if (ret == NULL)
1424 ret = choose_arena_hard();
1425#else
1426 if (__isthreaded) {
1427 unsigned long ind;
1428
1429 /*
1430 * Hash _pthread_self() to one of the arenas. There is a prime
1431 * number of arenas, so this has a reasonable chance of
1432 * working. Even so, the hashing can be easily thwarted by
1433 * inconvenient _pthread_self() values. Without specific
1434 * knowledge of how _pthread_self() calculates values, we can't
1435 * easily do much better than this.
1436 */
1437 ind = (unsigned long) _pthread_self() % narenas;
1438
1439 /*
1440 * Optimistially assume that arenas[ind] has been initialized.
1441 * At worst, we find out that some other thread has already
1442 * done so, after acquiring the lock in preparation. Note that
1443 * this lazy locking also has the effect of lazily forcing
1444 * cache coherency; without the lock acquisition, there's no
1445 * guarantee that modification of arenas[ind] by another thread
1446 * would be seen on this CPU for an arbitrary amount of time.
1447 *
1448 * In general, this approach to modifying a synchronized value
1449 * isn't a good idea, but in this case we only ever modify the
1450 * value once, so things work out well.
1451 */
1452 ret = arenas[ind];
1453 if (ret == NULL) {
1454 /*
1455 * Avoid races with another thread that may have already
1456 * initialized arenas[ind].
1457 */
1458 malloc_mutex_lock(&arenas_mtx);
1459 if (arenas[ind] == NULL)
1460 ret = arenas_extend((unsigned)ind);
1461 else
1462 ret = arenas[ind];
1463 malloc_mutex_unlock(&arenas_mtx);
1464 }
1465 } else
1466 ret = arenas[0];
1467#endif
1468
1469 assert(ret != NULL);
1470 return (ret);
1471}
1472
1473#ifndef NO_TLS
1474/*
1475 * Choose an arena based on a per-thread value (slow-path code only, called
1476 * only by choose_arena()).
1477 */
1478static arena_t *
1479choose_arena_hard(void)
1480{
1481 arena_t *ret;
1482
1483 assert(__isthreaded);
1484
1485 /* Assign one of the arenas to this thread, in a round-robin fashion. */
1486 malloc_mutex_lock(&arenas_mtx);
1487 ret = arenas[next_arena];
1488 if (ret == NULL)
1489 ret = arenas_extend(next_arena);
1490 if (ret == NULL) {
1491 /*
1492 * Make sure that this function never returns NULL, so that
1493 * choose_arena() doesn't have to check for a NULL return
1494 * value.
1495 */
1496 ret = arenas[0];
1497 }
1498 next_arena = (next_arena + 1) % narenas;
1499 malloc_mutex_unlock(&arenas_mtx);
1500 arenas_map = ret;
1501
1502 return (ret);
1503}
1504#endif
1505
1506static inline int
1507arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
1508{
1509
1510 assert(a != NULL);
1511 assert(b != NULL);
1512
1513 if ((uintptr_t)a < (uintptr_t)b)
1514 return (-1);
1515 else if (a == b)
1516 return (0);
1517 else
1518 return (1);
1519}
1520
1521/* Generate red-black tree code for arena chunks. */
1522RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
1523
1524static inline void *
1525arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
1526{
1527 void *ret;
1528 unsigned i, mask, bit, regind;
1529
1530 assert(run->magic == ARENA_RUN_MAGIC);
1531
1532 for (i = run->regs_minelm; i < REGS_MASK_NELMS; i++) {
1533 mask = run->regs_mask[i];
1534 if (mask != 0) {
1535 /* Usable allocation found. */
1536 bit = ffs(mask) - 1;
1537
1538 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
1539 ret = (void *)&((char *)run)[bin->reg0_offset
1540 + (bin->reg_size * regind)];
1541
1542 /* Clear bit. */
1543 mask ^= (1 << bit);
1544 run->regs_mask[i] = mask;
1545
1546 return (ret);
1547 } else {
1548 /*
1549 * Make a note that nothing before this element
1550 * contains a free region.
1551 */
1552 run->regs_minelm = i + 1;
1553 }
1554 }
1555 /* Not reached. */
1556 assert(0);
1557 return (NULL);
1558}
1559
1560static inline void
1561arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
1562{
1563 /*
1564 * To divide by a number D that is not a power of two we multiply
1565 * by (2^21 / D) and then right shift by 21 positions.
1566 *
1567 * X / D
1568 *
1569 * becomes
1570 *
1571 * (size_invs[(D >> QUANTUM_2POW_MIN) - 3] * D) >> SIZE_INV_SHIFT
1572 */
1573#define SIZE_INV_SHIFT 21
1574#define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
1575 static const unsigned size_invs[] = {
1576 SIZE_INV(3),
1577 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
1578 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
1579 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
1580 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
1581 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
1582 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
1583 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
1584#if (QUANTUM_2POW_MIN < 4)
1585 ,
1586 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
1587 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
1588 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
1589 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
1590 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
1591 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
1592 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
1593 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
1594#endif
1595 };
1596 unsigned diff, regind, elm, bit;
1597
1598 assert(run->magic == ARENA_RUN_MAGIC);
1599 assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
1600 >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
1601
1602 /*
1603 * Avoid doing division with a variable divisor if possible. Using
1604 * actual division here can reduce allocator throughput by over 20%!
1605 */
1606 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
1607 if ((size & (size - 1)) == 0) {
1608 /*
1609 * log2_table allows fast division of a power of two in the
1610 * [1..128] range.
1611 *
1612 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
1613 */
1614 static const unsigned char log2_table[] = {
1615 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
1616 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
1617 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1618 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
1619 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1620 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1621 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1622 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
1623 };
1624
1625 if (size <= 128)
1626 regind = (diff >> log2_table[size - 1]);
1627 else if (size <= 32768)
1628 regind = diff >> (8 + log2_table[(size >> 8) - 1]);
1629 else {
1630 /*
1631 * The page size is too large for us to use the lookup
1632 * table. Use real division.
1633 */
1634 regind = diff / size;
1635 }
1636 } else if (size <= ((sizeof(size_invs) / sizeof(unsigned))
1637 << QUANTUM_2POW_MIN) + 2) {
1638 regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
1639 regind >>= SIZE_INV_SHIFT;
1640 } else {
1641 /*
1642 * size_invs isn't large enough to handle this size class, so
1643 * calculate regind using actual division. This only happens
1644 * if the user increases small_max via the 'S' runtime
1645 * configuration option.
1646 */
1647 regind = diff / size;
1648 };
1649 assert(regind == diff / size);
1650 assert(regind < bin->nregs);
1651
1652 elm = regind >> (SIZEOF_INT_2POW + 3);
1653 if (elm < run->regs_minelm)
1654 run->regs_minelm = elm;
1655 bit = regind - (elm << (SIZEOF_INT_2POW + 3));
1656 assert((run->regs_mask[elm] & (1 << bit)) == 0);
1657 run->regs_mask[elm] |= (1 << bit);
1658#undef SIZE_INV
1659#undef SIZE_INV_SHIFT
1660}
1661
1662static void
1663arena_run_split(arena_t *arena, arena_run_t *run, bool large, size_t size)
1664{
1665 arena_chunk_t *chunk;
1666 unsigned run_ind, map_offset, total_pages, need_pages;
1667 unsigned i, log2_run_pages, run_pages;
1668
1669 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1670 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1671 >> pagesize_2pow);
1672 assert(chunk->map[run_ind].free);
1673 total_pages = chunk->map[run_ind].npages;
1674 need_pages = (size >> pagesize_2pow);
1675
1676 assert(chunk->map[run_ind].free);
1677 assert(chunk->map[run_ind].large == false);
1678 assert(chunk->map[run_ind].npages == total_pages);
1679
1680 /* Split enough pages from the front of run to fit allocation size. */
1681 map_offset = run_ind;
1682 for (i = 0; i < need_pages; i++) {
1683 chunk->map[map_offset + i].free = false;
1684 chunk->map[map_offset + i].large = large;
1685 chunk->map[map_offset + i].npages = need_pages;
1686 chunk->map[map_offset + i].pos = i;
1687 }
1688
1689 /* Update map for trailing pages. */
1690 map_offset += need_pages;
1691 while (map_offset < run_ind + total_pages) {
1692 log2_run_pages = ffs(map_offset) - 1;
1693 run_pages = (1 << log2_run_pages);
1694
1695 chunk->map[map_offset].free = true;
1696 chunk->map[map_offset].large = false;
1697 chunk->map[map_offset].npages = run_pages;
1698
1699 chunk->nfree_runs[log2_run_pages]++;
1700
1701 map_offset += run_pages;
1702 }
1703
1704 chunk->pages_used += (size >> pagesize_2pow);
1705}
1706
1707static arena_chunk_t *
1708arena_chunk_alloc(arena_t *arena)
1709{
1710 arena_chunk_t *chunk;
1711 unsigned i, j, header_npages, pow2_header_npages, map_offset;
1712 unsigned log2_run_pages, run_pages;
1713 size_t header_size;
1714
1715 chunk = (arena_chunk_t *)chunk_alloc(chunk_size);
1716 if (chunk == NULL)
1717 return (NULL);
1718
1719 chunk->arena = arena;
1720
1721 RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
1722
1723 /*
1724 * Claim that no pages are in use, since the header is merely overhead.
1725 */
1726 chunk->pages_used = 0;
1727
1728 memset(&chunk->nfree_runs, 0, sizeof(chunk->nfree_runs));
1729
1730 header_size = (size_t)((uintptr_t)&chunk->map[arena_chunk_maplen]
1731 - (uintptr_t)chunk);
1732 if (header_size % pagesize != 0) {
1733 /* Round up to the nearest page boundary. */
1734 header_size += pagesize - (header_size % pagesize);
1735 }
1736
1737 header_npages = header_size >> pagesize_2pow;
1738 pow2_header_npages = pow2_ceil(header_npages);
1739
1740 /*
1741 * Iteratively mark runs as in use, until we've spoken for the entire
1742 * header.
1743 */
1744 map_offset = 0;
1745 for (i = 0; header_npages > 0; i++) {
1746 if ((pow2_header_npages >> i) <= header_npages) {
1747 for (j = 0; j < (pow2_header_npages >> i); j++) {
1748 chunk->map[map_offset + j].free = false;
1749 chunk->map[map_offset + j].large = false;
1750 chunk->map[map_offset + j].npages =
1751 (pow2_header_npages >> i);
1752 chunk->map[map_offset + j].pos = j;
1753 }
1754 header_npages -= (pow2_header_npages >> i);
1755 map_offset += (pow2_header_npages >> i);
1756 }
1757 }
1758
1759 /*
1760 * Finish initializing map. The chunk header takes up some space at
1761 * the beginning of the chunk, which we just took care of by
1762 * "allocating" the leading pages.
1763 */
1764 while (map_offset < (chunk_size >> pagesize_2pow)) {
1765 log2_run_pages = ffs(map_offset) - 1;
1766 run_pages = (1 << log2_run_pages);
1767
1768 chunk->map[map_offset].free = true;
1769 chunk->map[map_offset].large = false;
1770 chunk->map[map_offset].npages = run_pages;
1771
1772 chunk->nfree_runs[log2_run_pages]++;
1773
1774 map_offset += run_pages;
1775 }
1776
1777 return (chunk);
1778}
1779
1780static void
1781arena_chunk_dealloc(arena_chunk_t *chunk)
1782{
1783
1784 RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks, chunk);
1785
1786 chunk_dealloc((void *)chunk, chunk_size);
1787}
1788
1789static void
1790arena_bin_run_promote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1791{
1792
1793 assert(bin == run->bin);
1794
1795 /* Promote. */
1796 assert(run->free_min > run->nfree);
1797 assert(run->quartile < RUN_Q100);
1798 run->quartile++;
1799#ifdef MALLOC_STATS
1800 bin->stats.npromote++;
1801#endif
1802
1803 /* Re-file run. */
1804 switch (run->quartile) {
1805 case RUN_QINIT:
1806 assert(0);
1807 break;
1808 case RUN_Q0:
1809 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1810 run->free_max = bin->nregs - 1;
1811 run->free_min = (bin->nregs >> 1) + 1;
1812 assert(run->nfree <= run->free_max);
1813 assert(run->nfree >= run->free_min);
1814 break;
1815 case RUN_Q25:
1816 qr_remove(run, link);
1817 qr_before_insert((arena_run_t *)&bin->runs25, run,
1818 link);
1819 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1820 run->free_min = (bin->nregs >> 2) + 1;
1821 assert(run->nfree <= run->free_max);
1822 assert(run->nfree >= run->free_min);
1823 break;
1824 case RUN_Q50:
1825 qr_remove(run, link);
1826 qr_before_insert((arena_run_t *)&bin->runs50, run,
1827 link);
1828 run->free_max = (bin->nregs >> 1) - 1;
1829 run->free_min = 1;
1830 assert(run->nfree <= run->free_max);
1831 assert(run->nfree >= run->free_min);
1832 break;
1833 case RUN_Q75:
1834 /*
1835 * Skip RUN_Q75 during promotion from RUN_Q50.
1836 * Separate handling of RUN_Q75 and RUN_Q100 allows us
1837 * to keep completely full runs in RUN_Q100, thus
1838 * guaranteeing that runs in RUN_Q75 are only mostly
1839 * full. This provides a method for avoiding a linear
1840 * search for non-full runs, which avoids some
1841 * pathological edge cases.
1842 */
1843 run->quartile++;
1844 /* Fall through. */
1845 case RUN_Q100:
1846 qr_remove(run, link);
1847 assert(bin->runcur == run);
1848 bin->runcur = NULL;
1849 run->free_max = 0;
1850 run->free_min = 0;
1851 assert(run->nfree <= run->free_max);
1852 assert(run->nfree >= run->free_min);
1853 break;
1854 default:
1855 assert(0);
1856 break;
1857 }
1858}
1859
1860static void
1861arena_bin_run_demote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1862{
1863
1864 assert(bin == run->bin);
1865
1866 /* Demote. */
1867 assert(run->free_max < run->nfree);
1868 assert(run->quartile > RUN_QINIT);
1869 run->quartile--;
1870#ifdef MALLOC_STATS
1871 bin->stats.ndemote++;
1872#endif
1873
1874 /* Re-file run. */
1875 switch (run->quartile) {
1876 case RUN_QINIT:
1877 qr_remove(run, link);
1878#ifdef MALLOC_STATS
1879 bin->stats.curruns--;
1880#endif
1881 if (bin->runcur == run)
1882 bin->runcur = NULL;
1883#ifdef MALLOC_DEBUG
1884 run->magic = 0;
1885#endif
1886 arena_run_dalloc(arena, run, bin->run_size);
1887 break;
1888 case RUN_Q0:
1889 qr_remove(run, link);
1890 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1891 run->free_max = bin->nregs - 1;
1892 run->free_min = (bin->nregs >> 1) + 1;
1893 assert(run->nfree <= run->free_max);
1894 assert(run->nfree >= run->free_min);
1895 break;
1896 case RUN_Q25:
1897 qr_remove(run, link);
1898 qr_before_insert((arena_run_t *)&bin->runs25, run,
1899 link);
1900 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1901 run->free_min = (bin->nregs >> 2) + 1;
1902 assert(run->nfree <= run->free_max);
1903 assert(run->nfree >= run->free_min);
1904 break;
1905 case RUN_Q50:
1906 qr_remove(run, link);
1907 qr_before_insert((arena_run_t *)&bin->runs50, run,
1908 link);
1909 run->free_max = (bin->nregs >> 1) - 1;
1910 run->free_min = 1;
1911 assert(run->nfree <= run->free_max);
1912 assert(run->nfree >= run->free_min);
1913 break;
1914 case RUN_Q75:
1915 qr_before_insert((arena_run_t *)&bin->runs75, run,
1916 link);
1917 run->free_max = (bin->nregs >> 2) - 1;
1918 run->free_min = 1;
1919 assert(run->nfree <= run->free_max);
1920 assert(run->nfree >= run->free_min);
1921 break;
1922 case RUN_Q100:
1923 default:
1924 assert(0);
1925 break;
1926 }
1927}
1928
1929static arena_run_t *
1930arena_run_alloc(arena_t *arena, bool large, size_t size)
1931{
1932 arena_run_t *run;
1933 unsigned min_ind, i, j;
1934 arena_chunk_t *chunk;
1935#ifndef NDEBUG
1936 int rep = 0;
1937#endif
1938
1939 assert(size <= arena_maxclass);
1940
1941AGAIN:
1942#ifndef NDEBUG
1943 rep++;
1944 assert(rep <= 2);
1945#endif
1946
1947 /*
1948 * Search through arena's chunks in address order for a run that is
1949 * large enough. Look for a precise fit, but do not pass up a chunk
1950 * that has a run which is large enough to split.
1951 */
1952 min_ind = ffs(size >> pagesize_2pow) - 1;
1953 RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
1954 for (i = min_ind;
1955 i < (opt_chunk_2pow - pagesize_2pow);
1956 i++) {
1957 if (chunk->nfree_runs[i] > 0) {
1958 arena_chunk_map_t *map = chunk->map;
1959
1960 /* Scan chunk's map for free run. */
1961 for (j = 0;
1962 j < arena_chunk_maplen;
1963 j += map[j].npages) {
1964 if (map[j].free
1965 && map[j].npages == (1 << i))
1966 {/*<----------------------------*/
1967 run = (arena_run_t *)&((char *)chunk)[j
1968 << pagesize_2pow];
1969
1970 assert(chunk->nfree_runs[i] > 0);
1971 chunk->nfree_runs[i]--;
1972
1973 /* Update page map. */
1974 arena_run_split(arena, run, large, size);
1975
1976 return (run);
1977 }/*---------------------------->*/
1978 }
1979 /* Not reached. */
1980 assert(0);
1981 }
1982 }
1983 }
1984
1985 /* No usable runs. Allocate a new chunk, then try again. */
1986 if (arena_chunk_alloc(arena) == NULL)
1987 return (NULL);
1988 goto AGAIN;
1989}
1990
1991static void
1992arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size)
1993{
1994 arena_chunk_t *chunk;
1995 unsigned run_ind, buddy_ind, base_run_ind, run_pages, log2_run_pages;
1996
1997 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1998 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1999 >> pagesize_2pow);
2000 run_pages = (size >> pagesize_2pow);
2001 log2_run_pages = ffs(run_pages) - 1;
2002 assert(run_pages > 0);
2003
2004 /* Subtract pages from count of pages used in chunk. */
2005 chunk->pages_used -= run_pages;
2006
2007 /* Mark run as deallocated. */
2008 chunk->map[run_ind].free = true;
2009 chunk->map[run_ind].large = false;
2010 chunk->map[run_ind].npages = run_pages;
2011
2012 /*
2013 * Tell the kernel that we don't need the data in this run, but only if
2014 * requested via runtime configuration.
2015 */
2016 if (opt_hint) {
2017 madvise(run, size, MADV_FREE);
2018#ifdef MALLOC_STATS
2019 arena->stats.nmadvise += (size >> pagesize_2pow);
2020#endif
2021 }
2022
2023 /*
2024 * Iteratively coalesce with buddies. Conceptually, the buddy scheme
2025 * induces a tree on the set of pages. If we know the number of pages
2026 * in the subtree rooted at the current node, we can quickly determine
2027 * whether a run is the left or right buddy, and then calculate the
2028 * buddy's index.
2029 */
2030 for (;
2031 (run_pages = (1 << log2_run_pages)) < arena_chunk_maplen;
2032 log2_run_pages++) {
2033 if (((run_ind >> log2_run_pages) & 1) == 0) {
2034 /* Current run precedes its buddy. */
2035 buddy_ind = run_ind + run_pages;
2036 base_run_ind = run_ind;
2037 } else {
2038 /* Current run follows its buddy. */
2039 buddy_ind = run_ind - run_pages;
2040 base_run_ind = buddy_ind;
2041 }
2042
2043 if (chunk->map[buddy_ind].free == false
2044 || chunk->map[buddy_ind].npages != run_pages)
2045 break;
2046
2047 assert(chunk->nfree_runs[log2_run_pages] > 0);
2048 chunk->nfree_runs[log2_run_pages]--;
2049
2050 /* Coalesce. */
2051 chunk->map[base_run_ind].npages = (run_pages << 1);
2052
2053 /* Update run_ind to be the beginning of the coalesced run. */
2054 run_ind = base_run_ind;
2055 }
2056
2057 chunk->nfree_runs[log2_run_pages]++;
2058
2059 /* Free pages, to the extent possible. */
2060 if (chunk->pages_used == 0) {
2061 /* This chunk is completely unused now, so deallocate it. */
2062 arena_chunk_dealloc(chunk);
2063 }
2064}
2065
2066static arena_run_t *
2067arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2068{
2069 arena_run_t *run;
2070 unsigned i, remainder;
2071
2072 /* Look for a usable run. */
2073 if ((run = qr_next((arena_run_t *)&bin->runs50, link))
2074 != (arena_run_t *)&bin->runs50
2075 || (run = qr_next((arena_run_t *)&bin->runs25, link))
2076 != (arena_run_t *)&bin->runs25
2077 || (run = qr_next((arena_run_t *)&bin->runs0, link))
2078 != (arena_run_t *)&bin->runs0
2079 || (run = qr_next((arena_run_t *)&bin->runs75, link))
2080 != (arena_run_t *)&bin->runs75) {
2081 /* run is guaranteed to have available space. */
2082 qr_remove(run, link);
2083 return (run);
2084 }
2085 /* No existing runs have any space available. */
2086
2087 /* Allocate a new run. */
2088 run = arena_run_alloc(arena, false, bin->run_size);
2089 if (run == NULL)
2090 return (NULL);
2091
2092 /* Initialize run internals. */
2093 qr_new(run, link);
2094 run->bin = bin;
2095
2096 for (i = 0; i < (bin->nregs >> (SIZEOF_INT_2POW + 3)); i++)
2097 run->regs_mask[i] = UINT_MAX;
2098 remainder = bin->nregs % (1 << (SIZEOF_INT_2POW + 3));
2099 if (remainder != 0) {
2100 run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3))
2101 - remainder));
2102 i++;
2103 }
2104 for (; i < REGS_MASK_NELMS; i++)
2105 run->regs_mask[i] = 0;
2106
2107 run->regs_minelm = 0;
2108
2109 run->nfree = bin->nregs;
2110 run->quartile = RUN_QINIT;
2111 run->free_max = bin->nregs;
2112 run->free_min = ((bin->nregs >> 2) * 3) + 1;
2113#ifdef MALLOC_DEBUG
2114 run->magic = ARENA_RUN_MAGIC;
2115#endif
2116
2117#ifdef MALLOC_STATS
2118 bin->stats.nruns++;
2119 bin->stats.curruns++;
2120 if (bin->stats.curruns > bin->stats.highruns)
2121 bin->stats.highruns = bin->stats.curruns;
2122#endif
2123 return (run);
2124}
2125
2126/* bin->runcur must have space available before this function is called. */
2127static inline void *
2128arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
2129{
2130 void *ret;
2131
2132 assert(run->magic == ARENA_RUN_MAGIC);
2133 assert(run->nfree > 0);
2134
2135 ret = arena_run_reg_alloc(run, bin);
2136 assert(ret != NULL);
2137 run->nfree--;
2138 if (run->nfree < run->free_min) {
2139 /* Promote run to higher fullness quartile. */
2140 arena_bin_run_promote(arena, bin, run);
2141 }
2142
2143 return (ret);
2144}
2145
2146/* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
2147static void *
2148arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
2149{
2150
2151 assert(bin->runcur == NULL || bin->runcur->quartile == RUN_Q100);
2152
2153 bin->runcur = arena_bin_nonfull_run_get(arena, bin);
2154 if (bin->runcur == NULL)
2155 return (NULL);
2156 assert(bin->runcur->magic == ARENA_RUN_MAGIC);
2157 assert(bin->runcur->nfree > 0);
2158
2159 return (arena_bin_malloc_easy(arena, bin, bin->runcur));
2160}
2161
2162static void *
2163arena_malloc(arena_t *arena, size_t size)
2164{
2165 void *ret;
2166
2167 assert(arena != NULL);
2168 assert(arena->magic == ARENA_MAGIC);
2169 assert(size != 0);
2170 assert(QUANTUM_CEILING(size) <= arena_maxclass);
2171
2172 if (size <= bin_maxclass) {
2173 arena_bin_t *bin;
2174 arena_run_t *run;
2175
2176 /* Small allocation. */
2177
2178 if (size < small_min) {
2179 /* Tiny. */
2180 size = pow2_ceil(size);
2181 bin = &arena->bins[ffs(size >> (tiny_min_2pow + 1))];
2182#if (!defined(NDEBUG) || defined(MALLOC_STATS))
2183 /*
2184 * Bin calculation is always correct, but we may need
2185 * to fix size for the purposes of assertions and/or
2186 * stats accuracy.
2187 */
2188 if (size < (1 << tiny_min_2pow))
2189 size = (1 << tiny_min_2pow);
2190#endif
2191 } else if (size <= small_max) {
2192 /* Quantum-spaced. */
2193 size = QUANTUM_CEILING(size);
2194 bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
2195 - 1];
2196 } else {
2197 /* Sub-page. */
2198 size = pow2_ceil(size);
2199 bin = &arena->bins[ntbins + nqbins
2200 + (ffs(size >> opt_small_max_2pow) - 2)];
2201 }
2202 assert(size == bin->reg_size);
2203
2204 malloc_mutex_lock(&arena->mtx);
2205 if ((run = bin->runcur) != NULL)
2206 ret = arena_bin_malloc_easy(arena, bin, run);
2207 else
2208 ret = arena_bin_malloc_hard(arena, bin);
2209
2210#ifdef MALLOC_STATS
2211 bin->stats.nrequests++;
2212#endif
2213 } else {
2214 /* Medium allocation. */
2215 size = pow2_ceil(size);
2216 malloc_mutex_lock(&arena->mtx);
2217 ret = (void *)arena_run_alloc(arena, true, size);
2218#ifdef MALLOC_STATS
2219 arena->stats.large_nrequests++;
2220#endif
2221 }
2222
2223#ifdef MALLOC_STATS
2224 arena->stats.nmalloc++;
2225 if (ret != NULL)
2226 arena->stats.allocated += size;
2227#endif
2228
2229 malloc_mutex_unlock(&arena->mtx);
2230
2231 if (opt_junk && ret != NULL)
2232 memset(ret, 0xa5, size);
2233 else if (opt_zero && ret != NULL)
2234 memset(ret, 0, size);
2235 return (ret);
2236}
2237
2238/* Return the size of the allocation pointed to by ptr. */
2239static size_t
2240arena_salloc(const void *ptr)
2241{
2242 size_t ret;
2243 arena_chunk_t *chunk;
2244 uint32_t pageind;
2245 arena_chunk_map_t mapelm;
2246
2247 assert(ptr != NULL);
2248 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2249
2250 /*
2251 * No arena data structures that we query here can change in a way that
2252 * affects this function, so we don't need to lock.
2253 */
2254 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2255 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2256 mapelm = chunk->map[pageind];
2257 assert(mapelm.free == false);
2258 if (mapelm.large == false) {
2259 arena_run_t *run;
2260
2261 pageind -= mapelm.pos;
2262
2263 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2264 assert(run->magic == ARENA_RUN_MAGIC);
2265 ret = run->bin->reg_size;
2266 } else
2267 ret = mapelm.npages << pagesize_2pow;
2268
2269 return (ret);
2270}
2271
2272static void *
2273arena_ralloc(void *ptr, size_t size, size_t oldsize)
2274{
2275 void *ret;
2276
2277 /* Avoid moving the allocation if the size class would not change. */
2278 if (size < small_min) {
2279 if (oldsize < small_min &&
2280 ffs(pow2_ceil(size) >> (tiny_min_2pow + 1))
2281 == ffs(pow2_ceil(oldsize) >> (tiny_min_2pow + 1)))
2282 goto IN_PLACE;
2283 } else if (size <= small_max) {
2284 if (oldsize >= small_min && oldsize <= small_max &&
2285 (QUANTUM_CEILING(size) >> opt_quantum_2pow)
2286 == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
2287 goto IN_PLACE;
2288 } else {
2289 if (oldsize > small_max && pow2_ceil(size) == oldsize)
2290 goto IN_PLACE;
2291 }
2292
2293 /*
2294 * If we get here, then size and oldsize are different enough that we
2295 * need to use a different size class. In that case, fall back to
2296 * allocating new space and copying.
2297 */
2298 ret = arena_malloc(choose_arena(), size);
2299 if (ret == NULL)
2300 return (NULL);
2301
2302 if (size < oldsize)
2303 memcpy(ret, ptr, size);
2304 else
2305 memcpy(ret, ptr, oldsize);
2306 idalloc(ptr);
2307 return (ret);
2308IN_PLACE:
2309 if (opt_junk && size < oldsize)
2310 memset(&((char *)ptr)[size], 0x5a, oldsize - size);
2311 else if (opt_zero && size > oldsize)
2312 memset(&((char *)ptr)[size], 0, size - oldsize);
2313 return (ptr);
2314}
2315
2316static void
2317arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
2318{
2319 unsigned pageind;
2320 arena_chunk_map_t mapelm;
2321 size_t size;
2322
2323 assert(arena != NULL);
2324 assert(arena->magic == ARENA_MAGIC);
2325 assert(chunk->arena == arena);
2326 assert(ptr != NULL);
2327 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2328
2329 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2330 mapelm = chunk->map[pageind];
2331 assert(mapelm.free == false);
2332 if (mapelm.large == false) {
2333 arena_run_t *run;
2334 arena_bin_t *bin;
2335
2336 /* Small allocation. */
2337
2338 pageind -= mapelm.pos;
2339
2340 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2341 assert(run->magic == ARENA_RUN_MAGIC);
2342 bin = run->bin;
2343 size = bin->reg_size;
2344
2345 if (opt_junk)
2346 memset(ptr, 0x5a, size);
2347
2348 malloc_mutex_lock(&arena->mtx);
2349 arena_run_reg_dalloc(run, bin, ptr, size);
2350 run->nfree++;
2351 if (run->nfree > run->free_max) {
2352 /* Demote run to lower fullness quartile. */
2353 arena_bin_run_demote(arena, bin, run);
2354 }
2355 } else {
2356 /* Medium allocation. */
2357
2358 size = mapelm.npages << pagesize_2pow;
2359 assert((((uintptr_t)ptr) & (size - 1)) == 0);
2360
2361 if (opt_junk)
2362 memset(ptr, 0x5a, size);
2363
2364 malloc_mutex_lock(&arena->mtx);
2365 arena_run_dalloc(arena, (arena_run_t *)ptr, size);
2366 }
2367
2368#ifdef MALLOC_STATS
2369 arena->stats.allocated -= size;
2370#endif
2371
2372 malloc_mutex_unlock(&arena->mtx);
2373}
2374
2375static bool
2376arena_new(arena_t *arena)
2377{
2378 unsigned i;
2379 arena_bin_t *bin;
2380 size_t pow2_size, run_size;
2381
2382 malloc_mutex_init(&arena->mtx);
2383
2384#ifdef MALLOC_STATS
2385 memset(&arena->stats, 0, sizeof(arena_stats_t));
2386#endif
2387
2388 /* Initialize chunks. */
2389 RB_INIT(&arena->chunks);
2390
2391 /* Initialize bins. */
2392
2393 /* (2^n)-spaced tiny bins. */
2394 for (i = 0; i < ntbins; i++) {
2395 bin = &arena->bins[i];
2396 bin->runcur = NULL;
2397 qr_new((arena_run_t *)&bin->runs0, link);
2398 qr_new((arena_run_t *)&bin->runs25, link);
2399 qr_new((arena_run_t *)&bin->runs50, link);
2400 qr_new((arena_run_t *)&bin->runs75, link);
2401
2402 bin->reg_size = (1 << (tiny_min_2pow + i));
2403
2404 /*
2405 * Calculate how large of a run to allocate. Make sure that at
2406 * least RUN_MIN_REGS regions fit in the run.
2407 */
2408 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2409 if (run_size < pagesize)
2410 run_size = pagesize;
2411 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2412 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2413 if (run_size > arena_maxclass)
2414 run_size = arena_maxclass;
2415 bin->run_size = run_size;
2416
2417 assert(run_size >= sizeof(arena_run_t));
2418 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2419 if (bin->nregs > (REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3))) {
2420 /* Take care not to overflow regs_mask. */
2421 bin->nregs = REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3);
2422 }
2423 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2424
2425#ifdef MALLOC_STATS
2426 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2427#endif
2428 }
2429
2430 /* Quantum-spaced bins. */
2431 for (; i < ntbins + nqbins; i++) {
2432 bin = &arena->bins[i];
2433 bin->runcur = NULL;
2434 qr_new((arena_run_t *)&bin->runs0, link);
2435 qr_new((arena_run_t *)&bin->runs25, link);
2436 qr_new((arena_run_t *)&bin->runs50, link);
2437 qr_new((arena_run_t *)&bin->runs75, link);
2438
2439 bin->reg_size = quantum * (i - ntbins + 1);
2440
2441 /*
2442 * Calculate how large of a run to allocate. Make sure that at
2443 * least RUN_MIN_REGS regions fit in the run.
2444 */
2445 pow2_size = pow2_ceil(quantum * (i - ntbins + 1));
2446 run_size = (pow2_size << RUN_MIN_REGS_2POW);
2447 if (run_size < pagesize)
2448 run_size = pagesize;
2449 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2450 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2451 if (run_size > arena_maxclass)
2452 run_size = arena_maxclass;
2453 bin->run_size = run_size;
2454
2455 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2456 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2457 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2458
2459#ifdef MALLOC_STATS
2460 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2461#endif
2462 }
2463
2464 /* (2^n)-spaced sub-page bins. */
2465 for (; i < ntbins + nqbins + nsbins; i++) {
2466 bin = &arena->bins[i];
2467 bin->runcur = NULL;
2468 qr_new((arena_run_t *)&bin->runs0, link);
2469 qr_new((arena_run_t *)&bin->runs25, link);
2470 qr_new((arena_run_t *)&bin->runs50, link);
2471 qr_new((arena_run_t *)&bin->runs75, link);
2472
2473 bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
2474
2475 /*
2476 * Calculate how large of a run to allocate. Make sure that at
2477 * least RUN_MIN_REGS regions fit in the run.
2478 */
2479 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2480 if (run_size < pagesize)
2481 run_size = pagesize;
2482 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2483 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2484 if (run_size > arena_maxclass)
2485 run_size = arena_maxclass;
2486 bin->run_size = run_size;
2487
2488 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2489 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2490 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2491
2492#ifdef MALLOC_STATS
2493 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2494#endif
2495 }
2496
2497#ifdef MALLOC_DEBUG
2498 arena->magic = ARENA_MAGIC;
2499#endif
2500
2501 return (false);
2502}
2503
2504/* Create a new arena and insert it into the arenas array at index ind. */
2505static arena_t *
2506arenas_extend(unsigned ind)
2507{
2508 arena_t *ret;
2509
2510 /* Allocate enough space for trailing bins. */
2511 ret = (arena_t *)base_alloc(sizeof(arena_t)
2512 + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1)));
2513 if (ret != NULL && arena_new(ret) == false) {
2514 arenas[ind] = ret;
2515 return (ret);
2516 }
2517 /* Only reached if there is an OOM error. */
2518
2519 /*
2520 * OOM here is quite inconvenient to propagate, since dealing with it
2521 * would require a check for failure in the fast path. Instead, punt
2522 * by using arenas[0]. In practice, this is an extremely unlikely
2523 * failure.
2524 */
2525 malloc_printf("%s: (malloc) Error initializing arena\n",
2526 _getprogname());
2527 if (opt_abort)
2528 abort();
2529
2530 return (arenas[0]);
2531}
2532
2533/*
2534 * End arena.
2535 */
2536/******************************************************************************/
2537/*
2538 * Begin general internal functions.
2539 */
2540
2541static void *
2542huge_malloc(size_t size)
2543{
2544 void *ret;
2545 size_t csize;
2546 chunk_node_t *node;
2547
2548 /* Allocate one or more contiguous chunks for this request. */
2549
2550 csize = CHUNK_CEILING(size);
2551 if (csize == 0) {
2552 /* size is large enough to cause size_t wrap-around. */
2553 return (NULL);
2554 }
2555
2556 /* Allocate a chunk node with which to track the chunk. */
2557 node = base_chunk_node_alloc();
2558 if (node == NULL)
2559 return (NULL);
2560
2561 ret = chunk_alloc(csize);
2562 if (ret == NULL) {
2563 base_chunk_node_dealloc(node);
2564 return (NULL);
2565 }
2566
2567 /* Insert node into huge. */
2568 node->chunk = ret;
2569 node->size = csize;
2570
2571 malloc_mutex_lock(&chunks_mtx);
2572 RB_INSERT(chunk_tree_s, &huge, node);
2573#ifdef MALLOC_STATS
2574 huge_nmalloc++;
2575 huge_allocated += csize;
2576#endif
2577 malloc_mutex_unlock(&chunks_mtx);
2578
2579 if (opt_junk && ret != NULL)
2580 memset(ret, 0xa5, csize);
2581 else if (opt_zero && ret != NULL)
2582 memset(ret, 0, csize);
2583
2584 return (ret);
2585}
2586
2587static void *
2588huge_ralloc(void *ptr, size_t size, size_t oldsize)
2589{
2590 void *ret;
2591
2592 /* Avoid moving the allocation if the size class would not change. */
2593 if (oldsize > arena_maxclass &&
2594 CHUNK_CEILING(size) == CHUNK_CEILING(oldsize))
2595 return (ptr);
2596
2597 /*
2598 * If we get here, then size and oldsize are different enough that we
2599 * need to use a different size class. In that case, fall back to
2600 * allocating new space and copying.
2601 */
2602 ret = huge_malloc(size);
2603 if (ret == NULL)
2604 return (NULL);
2605
2606 if (CHUNK_ADDR2BASE(ptr) == ptr) {
2607 /* The old allocation is a chunk. */
2608 if (size < oldsize)
2609 memcpy(ret, ptr, size);
2610 else
2611 memcpy(ret, ptr, oldsize);
2612 } else {
2613 /* The old allocation is a region. */
2614 assert(oldsize < size);
2615 memcpy(ret, ptr, oldsize);
2616 }
2617 idalloc(ptr);
2618 return (ret);
2619}
2620
2621static void
2622huge_dalloc(void *ptr)
2623{
2624 chunk_node_t key;
2625 chunk_node_t *node;
2626
2627 malloc_mutex_lock(&chunks_mtx);
2628
2629 /* Extract from tree of huge allocations. */
2630 key.chunk = ptr;
2631 node = RB_FIND(chunk_tree_s, &huge, &key);
2632 assert(node != NULL);
2633 assert(node->chunk == ptr);
2634 RB_REMOVE(chunk_tree_s, &huge, node);
2635
2636#ifdef MALLOC_STATS
2637 /* Update counters. */
2638 huge_ndalloc++;
2639 huge_allocated -= node->size;
2640#endif
2641
2642 malloc_mutex_unlock(&chunks_mtx);
2643
2644 /* Unmap chunk. */
2645#ifdef USE_BRK
2646 if (opt_junk)
2647 memset(node->chunk, 0x5a, node->size);
2648#endif
2649 chunk_dealloc(node->chunk, node->size);
2650
2651 base_chunk_node_dealloc(node);
2652}
2653
2654static void *
2655imalloc(size_t size)
2656{
2657 void *ret;
2658
2659 assert(size != 0);
2660
2661 if (size <= arena_maxclass)
2662 ret = arena_malloc(choose_arena(), size);
2663 else
2664 ret = huge_malloc(size);
2665
2666 return (ret);
2667}
2668
2669static void *
2670ipalloc(size_t alignment, size_t size)
2671{
2672 void *ret;
2673 size_t alloc_size;
2674
2675 /*
2676 * Take advantage of the fact that for each size class, every object is
2677 * aligned at the smallest power of two that is non-zero in the base
2678 * two representation of the size. For example:
2679 *
2680 * Size | Base 2 | Minimum alignment
2681 * -----+----------+------------------
2682 * 96 | 1100000 | 32
2683 * 144 | 10100000 | 32
2684 * 192 | 11000000 | 64
2685 *
2686 * Depending on runtime settings, it is possible that arena_malloc()
2687 * will further round up to a power of two, but that never causes
2688 * correctness issues.
2689 */
2690 alloc_size = (size + (alignment - 1)) & (-alignment);
2691 if (alloc_size < size) {
2692 /* size_t overflow. */
2693 return (NULL);
2694 }
2695
2696 if (alloc_size <= arena_maxclass)
2697 ret = arena_malloc(choose_arena(), alloc_size);
2698 else {
2699 if (alignment <= chunk_size)
2700 ret = huge_malloc(size);
2701 else {
2702 size_t chunksize, offset;
2703 chunk_node_t *node;
2704
2705 /*
2706 * This allocation requires alignment that is even
2707 * larger than chunk alignment. This means that
2708 * huge_malloc() isn't good enough.
2709 *
2710 * Allocate almost twice as many chunks as are demanded
2711 * by the size or alignment, in order to assure the
2712 * alignment can be achieved, then unmap leading and
2713 * trailing chunks.
2714 */
2715
2716 chunksize = CHUNK_CEILING(size);
2717
2718 if (size >= alignment)
2719 alloc_size = chunksize + alignment - chunk_size;
2720 else
2721 alloc_size = (alignment << 1) - chunk_size;
2722
2723 /*
2724 * Allocate a chunk node with which to track the chunk.
2725 */
2726 node = base_chunk_node_alloc();
2727 if (node == NULL)
2728 return (NULL);
2729
2730 ret = chunk_alloc(alloc_size);
2731 if (ret == NULL) {
2732 base_chunk_node_dealloc(node);
2733 return (NULL);
2734 }
2735
2736 offset = (uintptr_t)ret & (alignment - 1);
2737 assert(offset % chunk_size == 0);
2738 assert(offset < alloc_size);
2739 if (offset == 0) {
2740 /* Trim trailing space. */
2741 chunk_dealloc((void *)((uintptr_t)ret
2742 + chunksize), alloc_size - chunksize);
2743 } else {
2744 size_t trailsize;
2745
2746 /* Trim leading space. */
2747 chunk_dealloc(ret, alignment - offset);
2748
2749 ret = (void *)((uintptr_t)ret + (alignment
2750 - offset));
2751
2752 trailsize = alloc_size - (alignment - offset)
2753 - chunksize;
2754 if (trailsize != 0) {
2755 /* Trim trailing space. */
2756 assert(trailsize < alloc_size);
2757 chunk_dealloc((void *)((uintptr_t)ret
2758 + chunksize), trailsize);
2759 }
2760 }
2761
2762 /* Insert node into huge. */
2763 node->chunk = ret;
2764 node->size = chunksize;
2765
2766 malloc_mutex_lock(&chunks_mtx);
2767 RB_INSERT(chunk_tree_s, &huge, node);
2768#ifdef MALLOC_STATS
2769 huge_allocated += size;
2770#endif
2771 malloc_mutex_unlock(&chunks_mtx);
2772
2773 if (opt_junk)
2774 memset(ret, 0xa5, chunksize);
2775 else if (opt_zero)
2776 memset(ret, 0, chunksize);
2777 }
2778 }
2779
2780 assert(((uintptr_t)ret & (alignment - 1)) == 0);
2781 return (ret);
2782}
2783
2784static void *
2785icalloc(size_t size)
2786{
2787 void *ret;
2788
2789 if (size <= arena_maxclass) {
2790 ret = arena_malloc(choose_arena(), size);
2791 if (ret == NULL)
2792 return (NULL);
2793 memset(ret, 0, size);
2794 } else {
2795 /*
2796 * The virtual memory system provides zero-filled pages, so
2797 * there is no need to do so manually, unless opt_junk is
2798 * enabled, in which case huge_malloc() fills huge allocations
2799 * with junk.
2800 */
2801 ret = huge_malloc(size);
2802 if (ret == NULL)
2803 return (NULL);
2804
2805 if (opt_junk)
2806 memset(ret, 0, size);
2807#ifdef USE_BRK
2808 else if ((uintptr_t)ret >= (uintptr_t)brk_base
2809 && (uintptr_t)ret < (uintptr_t)brk_max) {
2810 /*
2811 * This may be a re-used brk chunk. Therefore, zero
2812 * the memory.
2813 */
2814 memset(ret, 0, size);
2815 }
2816#endif
2817 }
2818
2819 return (ret);
2820}
2821
2822static size_t
2823isalloc(const void *ptr)
2824{
2825 size_t ret;
2826 arena_chunk_t *chunk;
2827
2828 assert(ptr != NULL);
2829
2830 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2831 if (chunk != ptr) {
2832 /* Region. */
2833 assert(chunk->arena->magic == ARENA_MAGIC);
2834
2835 ret = arena_salloc(ptr);
2836 } else {
2837 chunk_node_t *node, key;
2838
2839 /* Chunk (huge allocation). */
2840
2841 malloc_mutex_lock(&chunks_mtx);
2842
2843 /* Extract from tree of huge allocations. */
2844 key.chunk = (void *)ptr;
2845 node = RB_FIND(chunk_tree_s, &huge, &key);
2846 assert(node != NULL);
2847
2848 ret = node->size;
2849
2850 malloc_mutex_unlock(&chunks_mtx);
2851 }
2852
2853 return (ret);
2854}
2855
2856static void *
2857iralloc(void *ptr, size_t size)
2858{
2859 void *ret;
2860 size_t oldsize;
2861
2862 assert(ptr != NULL);
2863 assert(size != 0);
2864
2865 oldsize = isalloc(ptr);
2866
2867 if (size <= arena_maxclass)
2868 ret = arena_ralloc(ptr, size, oldsize);
2869 else
2870 ret = huge_ralloc(ptr, size, oldsize);
2871
2872 return (ret);
2873}
2874
2875static void
2876idalloc(void *ptr)
2877{
2878 arena_chunk_t *chunk;
2879
2880 assert(ptr != NULL);
2881
2882 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2883 if (chunk != ptr) {
2884 /* Region. */
2885#ifdef MALLOC_STATS
2886 malloc_mutex_lock(&chunk->arena->mtx);
2887 chunk->arena->stats.ndalloc++;
2888 malloc_mutex_unlock(&chunk->arena->mtx);
2889#endif
2890 arena_dalloc(chunk->arena, chunk, ptr);
2891 } else
2892 huge_dalloc(ptr);
2893}
2894
2895static void
2896malloc_print_stats(void)
2897{
2898
2899 if (opt_print_stats) {
2900 malloc_printf("___ Begin malloc statistics ___\n");
2901 malloc_printf("Number of CPUs: %u\n", ncpus);
2902 malloc_printf("Number of arenas: %u\n", narenas);
2903 malloc_printf("Chunk size: %zu (2^%zu)\n", chunk_size,
2904 opt_chunk_2pow);
2905 malloc_printf("Quantum size: %zu (2^%zu)\n", quantum,
2906 opt_quantum_2pow);
2907 malloc_printf("Max small size: %zu\n", small_max);
2908 malloc_printf("Pointer size: %u\n", sizeof(void *));
2909 malloc_printf("Assertions %s\n",
2910#ifdef NDEBUG
2911 "disabled"
2912#else
2913 "enabled"
2914#endif
2915 );
2916
2917#ifdef MALLOC_STATS
2918
2919 {
2920 size_t allocated, total;
2921 unsigned i;
2922 arena_t *arena;
2923
2924 /* Calculate and print allocated/total stats. */
2925
2926 /* arenas. */
2927 for (i = 0, allocated = 0; i < narenas; i++) {
2928 if (arenas[i] != NULL) {
2929 malloc_mutex_lock(&arenas[i]->mtx);
2930 allocated += arenas[i]->stats.allocated;
2931 malloc_mutex_unlock(&arenas[i]->mtx);
2932 }
2933 }
2934
2935 /* huge. */
2936 malloc_mutex_lock(&chunks_mtx);
2937 allocated += huge_allocated;
2938 total = stats_chunks.curchunks * chunk_size;
2939 malloc_mutex_unlock(&chunks_mtx);
2940
2941 malloc_printf("Allocated: %zu, space used: %zu\n",
2942 allocated, total);
2943
2944 /* Print chunk stats. */
2945 {
2946 chunk_stats_t chunks_stats;
2947
2948 malloc_mutex_lock(&chunks_mtx);
2949 chunks_stats = stats_chunks;
2950 malloc_mutex_unlock(&chunks_mtx);
2951
2952 malloc_printf("\nchunks:\n");
2953 malloc_printf(" %13s%13s%13s\n", "nchunks",
2954 "highchunks", "curchunks");
2955 malloc_printf(" %13llu%13lu%13lu\n",
2956 chunks_stats.nchunks,
2957 chunks_stats.highchunks,
2958 chunks_stats.curchunks);
2959 }
2960
2961 /* Print chunk stats. */
2962 malloc_printf("\nhuge:\n");
2963 malloc_printf("%12s %12s %12s\n",
2964 "nmalloc", "ndalloc", "allocated");
2965 malloc_printf("%12llu %12llu %12zu\n",
2966 huge_nmalloc, huge_ndalloc, huge_allocated);
2967
2968 /* Print stats for each arena. */
2969 for (i = 0; i < narenas; i++) {
2970 arena = arenas[i];
2971 if (arena != NULL) {
2972 malloc_printf(
2973 "\narenas[%u] statistics:\n", i);
2974 malloc_mutex_lock(&arena->mtx);
2975 stats_print(arena);
2976 malloc_mutex_unlock(&arena->mtx);
2977 }
2978 }
2979 }
2980#endif /* #ifdef MALLOC_STATS */
2981 malloc_printf("--- End malloc statistics ---\n");
2982 }
2983}
2984
2985/*
2986 * FreeBSD's pthreads implementation calls malloc(3), so the malloc
2987 * implementation has to take pains to avoid infinite recursion during
2988 * initialization.
2989 */
2990static inline bool
2991malloc_init(void)
2992{
2993
2994 if (malloc_initialized == false)
2995 return (malloc_init_hard());
2996
2997 return (false);
2998}
2999
3000static bool
3001malloc_init_hard(void)
3002{
3003 unsigned i, j;
3004 int linklen;
3005 char buf[PATH_MAX + 1];
3006 const char *opts;
3007
3008 malloc_mutex_lock(&init_lock);
3009 if (malloc_initialized) {
3010 /*
3011 * Another thread initialized the allocator before this one
3012 * acquired init_lock.
3013 */
3014 malloc_mutex_unlock(&init_lock);
3015 return (false);
3016 }
3017
3018 /* Get number of CPUs. */
3019 {
3020 int mib[2];
3021 size_t len;
3022
3023 mib[0] = CTL_HW;
3024 mib[1] = HW_NCPU;
3025 len = sizeof(ncpus);
3026 if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
3027 /* Error. */
3028 ncpus = 1;
3029 }
3030 }
3031
3032 /* Get page size. */
3033 {
3034 long result;
3035
3036 result = sysconf(_SC_PAGESIZE);
3037 assert(result != -1);
3038 pagesize = (unsigned) result;
3039
3040 /*
3041 * We assume that pagesize is a power of 2 when calculating
3042 * pagesize_2pow.
3043 */
3044 assert(((result - 1) & result) == 0);
3045 pagesize_2pow = ffs(result) - 1;
3046 }
3047
3048 for (i = 0; i < 3; i++) {
3049 /* Get runtime configuration. */
3050 switch (i) {
3051 case 0:
3052 if ((linklen = readlink("/etc/malloc.conf", buf,
3053 sizeof(buf) - 1)) != -1) {
3054 /*
3055 * Use the contents of the "/etc/malloc.conf"
3056 * symbolic link's name.
3057 */
3058 buf[linklen] = '\0';
3059 opts = buf;
3060 } else {
3061 /* No configuration specified. */
3062 buf[0] = '\0';
3063 opts = buf;
3064 }
3065 break;
3066 case 1:
3067 if (issetugid() == 0 && (opts =
3068 getenv("MALLOC_OPTIONS")) != NULL) {
3069 /*
3070 * Do nothing; opts is already initialized to
3071 * the value of the MALLOC_OPTIONS environment
3072 * variable.
3073 */
3074 } else {
3075 /* No configuration specified. */
3076 buf[0] = '\0';
3077 opts = buf;
3078 }
3079 break;
3080 case 2:
3081 if (_malloc_options != NULL) {
3082 /*
3083 * Use options that were compiled into the program.
3084 */
3085 opts = _malloc_options;
3086 } else {
3087 /* No configuration specified. */
3088 buf[0] = '\0';
3089 opts = buf;
3090 }
3091 break;
3092 default:
3093 /* NOTREACHED */
3094 assert(false);
3095 }
3096
3097 for (j = 0; opts[j] != '\0'; j++) {
3098 switch (opts[j]) {
3099 case 'a':
3100 opt_abort = false;
3101 break;
3102 case 'A':
3103 opt_abort = true;
3104 break;
3105 case 'h':
3106 opt_hint = false;
3107 break;
3108 case 'H':
3109 opt_hint = true;
3110 break;
3111 case 'j':
3112 opt_junk = false;
3113 break;
3114 case 'J':
3115 opt_junk = true;
3116 break;
3117 case 'k':
3118 /*
3119 * Run fullness quartile limits don't have
3120 * enough resolution if there are too few
3121 * regions for the largest bin size classes.
3122 */
3123 if (opt_chunk_2pow > pagesize_2pow + 4)
3124 opt_chunk_2pow--;
3125 break;
3126 case 'K':
3127 if (opt_chunk_2pow < CHUNK_2POW_MAX)
3128 opt_chunk_2pow++;
3129 break;
3130 case 'n':
3131 opt_narenas_lshift--;
3132 break;
3133 case 'N':
3134 opt_narenas_lshift++;
3135 break;
3136 case 'p':
3137 opt_print_stats = false;
3138 break;
3139 case 'P':
3140 opt_print_stats = true;
3141 break;
3142 case 'q':
3143 if (opt_quantum_2pow > QUANTUM_2POW_MIN)
3144 opt_quantum_2pow--;
3145 break;
3146 case 'Q':
3147 if (opt_quantum_2pow < pagesize_2pow - 1)
3148 opt_quantum_2pow++;
3149 break;
3150 case 's':
3151 if (opt_small_max_2pow > QUANTUM_2POW_MIN)
3152 opt_small_max_2pow--;
3153 break;
3154 case 'S':
3155 if (opt_small_max_2pow < pagesize_2pow - 1)
3156 opt_small_max_2pow++;
3157 break;
3158 case 'u':
3159 opt_utrace = false;
3160 break;
3161 case 'U':
3162 opt_utrace = true;
3163 break;
3164 case 'v':
3165 opt_sysv = false;
3166 break;
3167 case 'V':
3168 opt_sysv = true;
3169 break;
3170 case 'x':
3171 opt_xmalloc = false;
3172 break;
3173 case 'X':
3174 opt_xmalloc = true;
3175 break;
3176 case 'z':
3177 opt_zero = false;
3178 break;
3179 case 'Z':
3180 opt_zero = true;
3181 break;
3182 default:
3183 malloc_printf("%s: (malloc) Unsupported"
3184 " character in malloc options: '%c'\n",
3185 _getprogname(), opts[j]);
3186 }
3187 }
3188 }
3189
3190 /* Take care to call atexit() only once. */
3191 if (opt_print_stats) {
3192 /* Print statistics at exit. */
3193 atexit(malloc_print_stats);
3194 }
3195
3196 /* Set variables according to the value of opt_small_max_2pow. */
3197 if (opt_small_max_2pow < opt_quantum_2pow)
3198 opt_small_max_2pow = opt_quantum_2pow;
3199 small_max = (1 << opt_small_max_2pow);
3200
3201 /* Set bin-related variables. */
3202 bin_maxclass = (pagesize >> 1);
3203 if (pagesize_2pow > RUN_MIN_REGS_2POW + 1)
3204 tiny_min_2pow = pagesize_2pow - (RUN_MIN_REGS_2POW + 1);
3205 else
3206 tiny_min_2pow = 1;
3207 assert(opt_quantum_2pow >= tiny_min_2pow);
3208 ntbins = opt_quantum_2pow - tiny_min_2pow;
3209 assert(ntbins <= opt_quantum_2pow);
3210 nqbins = (small_max >> opt_quantum_2pow);
3211 nsbins = pagesize_2pow - opt_small_max_2pow - 1;
3212
3213 /* Set variables according to the value of opt_quantum_2pow. */
3214 quantum = (1 << opt_quantum_2pow);
3215 quantum_mask = quantum - 1;
3216 if (ntbins > 0)
3217 small_min = (quantum >> 1) + 1;
3218 else
3219 small_min = 1;
3220 assert(small_min <= quantum);
3221
3222 /* Set variables according to the value of opt_chunk_2pow. */
3223 chunk_size = (1 << opt_chunk_2pow);
3224 chunk_size_mask = chunk_size - 1;
3225 arena_chunk_maplen = (1 << (opt_chunk_2pow - pagesize_2pow));
3226 arena_maxclass = (chunk_size >> 1);
3227
3228 UTRACE(0, 0, 0);
3229
3230#ifdef MALLOC_STATS
3231 memset(&stats_chunks, 0, sizeof(chunk_stats_t));
3232#endif
3233
3234 /* Various sanity checks that regard configuration. */
3235 assert(quantum >= sizeof(void *));
3236 assert(quantum <= pagesize);
3237 assert(chunk_size >= pagesize);
3238 assert(quantum * 4 <= chunk_size);
3239
3240 /* Initialize chunks data. */
3241 malloc_mutex_init(&chunks_mtx);
3242 RB_INIT(&huge);
3243#ifdef USE_BRK
3244 brk_base = sbrk(0);
3245 brk_prev = brk_base;
3246 brk_max = brk_base;
3247#endif
3248#ifdef MALLOC_STATS
3249 huge_nmalloc = 0;
3250 huge_ndalloc = 0;
3251 huge_allocated = 0;
3252#endif
3253 RB_INIT(&old_chunks);
3254
3255 /* Initialize base allocation data structures. */
3256#ifdef MALLOC_STATS
3257 base_total = 0;
3258#endif
3259#ifdef USE_BRK
3260 /*
3261 * Do special brk allocation here, since the base chunk doesn't really
3262 * need to be chunk-aligned.
3263 */
3264 {
3265 void *brk_cur;
3266 intptr_t incr;
3267
3268 do {
3269 /* Get the current end of brk. */
3270 brk_cur = sbrk(0);
3271
3272 /*
3273 * Calculate how much padding is necessary to
3274 * chunk-align the end of brk. Don't worry about
3275 * brk_cur not being chunk-aligned though.
3276 */
3277 incr = (intptr_t)chunk_size
3278 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
3279
3280 brk_prev = sbrk(incr);
3281 if (brk_prev == brk_cur) {
3282 /* Success. */
3283 break;
3284 }
3285 } while (brk_prev != (void *)-1);
3286
3287 base_chunk = brk_cur;
3288 base_next_addr = base_chunk;
3289 base_past_addr = (void *)((uintptr_t)base_chunk + incr);
3290#ifdef MALLOC_STATS
3291 base_total += incr;
3292 stats_chunks.nchunks = 1;
3293 stats_chunks.curchunks = 1;
3294 stats_chunks.highchunks = 1;
3295#endif
3296 }
3297#else
3298 /*
3299 * The first base chunk will be allocated when needed by base_alloc().
3300 */
3301 base_chunk = NULL;
3302 base_next_addr = NULL;
3303 base_past_addr = NULL;
3304#endif
3305 base_chunk_nodes = NULL;
3306 malloc_mutex_init(&base_mtx);
3307
3308 if (ncpus > 1) {
3309 /*
3310 * For SMP systems, create four times as many arenas as there
3311 * are CPUs by default.
3312 */
3313 opt_narenas_lshift += 2;
3314 }
3315
3316 /* Determine how many arenas to use. */
3317 narenas = ncpus;
3318 if (opt_narenas_lshift > 0) {
3319 if ((narenas << opt_narenas_lshift) > narenas)
3320 narenas <<= opt_narenas_lshift;
3321 /*
3322 * Make sure not to exceed the limits of what base_malloc()
3323 * can handle.
3324 */
3325 if (narenas * sizeof(arena_t *) > chunk_size)
3326 narenas = chunk_size / sizeof(arena_t *);
3327 } else if (opt_narenas_lshift < 0) {
3328 if ((narenas << opt_narenas_lshift) < narenas)
3329 narenas <<= opt_narenas_lshift;
3330 /* Make sure there is at least one arena. */
3331 if (narenas == 0)
3332 narenas = 1;
3333 }
3334
3335#ifdef NO_TLS
3336 if (narenas > 1) {
3337 static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
3338 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
3339 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
3340 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
3341 223, 227, 229, 233, 239, 241, 251, 257, 263};
3342 unsigned i, nprimes, parenas;
3343
3344 /*
3345 * Pick a prime number of hash arenas that is more than narenas
3346 * so that direct hashing of pthread_self() pointers tends to
3347 * spread allocations evenly among the arenas.
3348 */
3349 assert((narenas & 1) == 0); /* narenas must be even. */
3350 nprimes = (sizeof(primes) >> SIZEOF_INT_2POW);
3351 parenas = primes[nprimes - 1]; /* In case not enough primes. */
3352 for (i = 1; i < nprimes; i++) {
3353 if (primes[i] > narenas) {
3354 parenas = primes[i];
3355 break;
3356 }
3357 }
3358 narenas = parenas;
3359 }
3360#endif
3361
3362#ifndef NO_TLS
3363 next_arena = 0;
3364#endif
3365
3366 /* Allocate and initialize arenas. */
3367 arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
3368 if (arenas == NULL) {
3369 malloc_mutex_unlock(&init_lock);
3370 return (true);
3371 }
3372 /*
3373 * Zero the array. In practice, this should always be pre-zeroed,
3374 * since it was just mmap()ed, but let's be sure.
3375 */
3376 memset(arenas, 0, sizeof(arena_t *) * narenas);
3377
3378 /*
3379 * Initialize one arena here. The rest are lazily created in
3380 * arena_choose_hard().
3381 */
3382 arenas_extend(0);
3383 if (arenas[0] == NULL) {
3384 malloc_mutex_unlock(&init_lock);
3385 return (true);
3386 }
3387
3388 malloc_mutex_init(&arenas_mtx);
3389
3390 malloc_initialized = true;
3391 malloc_mutex_unlock(&init_lock);
3392 return (false);
3393}
3394
3395/*
3396 * End general internal functions.
3397 */
3398/******************************************************************************/
3399/*
3400 * Begin malloc(3)-compatible functions.
3401 */
3402
3403void *
3404malloc(size_t size)
3405{
3406 void *ret;
3407
3408 if (malloc_init()) {
3409 ret = NULL;
3410 goto RETURN;
3411 }
3412
3413 if (size == 0) {
3414 if (opt_sysv == false)
3415 size = 1;
3416 else {
3417 ret = NULL;
3418 goto RETURN;
3419 }
3420 }
3421
3422 ret = imalloc(size);
3423
3424RETURN:
3425 if (ret == NULL) {
3426 if (opt_xmalloc) {
3427 malloc_printf("%s: (malloc) Error in malloc(%zu):"
3428 " out of memory\n", _getprogname(), size);
3429 abort();
3430 }
3431 errno = ENOMEM;
3432 }
3433
3434 UTRACE(0, size, ret);
3435 return (ret);
3436}
3437
3438int
3439posix_memalign(void **memptr, size_t alignment, size_t size)
3440{
3441 int ret;
3442 void *result;
3443
3444 if (malloc_init())
3445 result = NULL;
3446 else {
3447 /* Make sure that alignment is a large enough power of 2. */
3448 if (((alignment - 1) & alignment) != 0
3449 || alignment < sizeof(void *)) {
3450 if (opt_xmalloc) {
3451 malloc_printf("%s: (malloc) Error in"
3452 " posix_memalign(%zu, %zu):"
3453 " invalid alignment\n",
3454 _getprogname(), alignment, size);
3455 abort();
3456 }
3457 result = NULL;
3458 ret = EINVAL;
3459 goto RETURN;
3460 }
3461
3462 result = ipalloc(alignment, size);
3463 }
3464
3465 if (result == NULL) {
3466 if (opt_xmalloc) {
3467 malloc_printf("%s: (malloc) Error in"
3468 " posix_memalign(%zu, %zu): out of memory\n",
3469 _getprogname(), alignment, size);
3470 abort();
3471 }
3472 ret = ENOMEM;
3473 goto RETURN;
3474 }
3475
3476 *memptr = result;
3477 ret = 0;
3478
3479RETURN:
3480 UTRACE(0, size, result);
3481 return (ret);
3482}
3483
3484void *
3485calloc(size_t num, size_t size)
3486{
3487 void *ret;
3488 size_t num_size;
3489
3490 if (malloc_init()) {
3491 ret = NULL;
3492 goto RETURN;
3493 }
3494
3495 num_size = num * size;
3496 if (num_size == 0) {
3497 if (opt_sysv == false)
3498 num_size = 1;
3499 else {
3500 ret = NULL;
3501 goto RETURN;
3502 }
3503 /*
3504 * Try to avoid division here. We know that it isn't possible to
3505 * overflow during multiplication if neither operand uses any of the
3506 * most significant half of the bits in a size_t.
3507 */
3508 } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
3509 && (num_size / size != num)) {
3510 /* size_t overflow. */
3511 ret = NULL;
3512 goto RETURN;
3513 }
3514
3515 ret = icalloc(num_size);
3516
3517RETURN:
3518 if (ret == NULL) {
3519 if (opt_xmalloc) {
3520 malloc_printf("%s: (malloc) Error in"
3521 " calloc(%zu, %zu): out of memory\n",
3522 _getprogname(), num, size);
3523 abort();
3524 }
3525 errno = ENOMEM;
3526 }
3527
3528 UTRACE(0, num_size, ret);
3529 return (ret);
3530}
3531
3532void *
3533realloc(void *ptr, size_t size)
3534{
3535 void *ret;
3536
3537 if (size == 0) {
3538 if (opt_sysv == false)
3539 size = 1;
3540 else {
3541 if (ptr != NULL)
3542 idalloc(ptr);
3543 ret = NULL;
3544 goto RETURN;
3545 }
3546 }
3547
3548 if (ptr != NULL) {
3549 assert(malloc_initialized);
3550
3551 ret = iralloc(ptr, size);
3552
3553 if (ret == NULL) {
3554 if (opt_xmalloc) {
3555 malloc_printf("%s: (malloc) Error in"
3556 " realloc(%p, %zu): out of memory\n",
3557 _getprogname(), ptr, size);
3558 abort();
3559 }
3560 errno = ENOMEM;
3561 }
3562 } else {
3563 if (malloc_init())
3564 ret = NULL;
3565 else
3566 ret = imalloc(size);
3567
3568 if (ret == NULL) {
3569 if (opt_xmalloc) {
3570 malloc_printf("%s: (malloc) Error in"
3571 " realloc(%p, %zu): out of memory\n",
3572 _getprogname(), ptr, size);
3573 abort();
3574 }
3575 errno = ENOMEM;
3576 }
3577 }
3578
3579RETURN:
3580 UTRACE(ptr, size, ret);
3581 return (ret);
3582}
3583
3584void
3585free(void *ptr)
3586{
3587
3588 UTRACE(ptr, 0, 0);
3589 if (ptr != NULL) {
3590 assert(malloc_initialized);
3591
3592 idalloc(ptr);
3593 }
3594}
3595
3596/*
3597 * End malloc(3)-compatible functions.
3598 */
3599/******************************************************************************/
3600/*
3601 * Begin non-standard functions.
3602 */
3603
3604size_t
3605malloc_usable_size(const void *ptr)
3606{
3607
3608 assert(ptr != NULL);
3609
3610 return (isalloc(ptr));
3611}
3612
3613/*
3614 * End non-standard functions.
3615 */
3616/******************************************************************************/
3617/*
3618 * Begin library-private functions, used by threading libraries for protection
3619 * of malloc during fork(). These functions are only called if the program is
3620 * running in threaded mode, so there is no need to check whether the program
3621 * is threaded here.
3622 */
3623
3624void
3625_malloc_prefork(void)
3626{
3627 unsigned i;
3628
3629 /* Acquire all mutexes in a safe order. */
3630
3631 malloc_mutex_lock(&arenas_mtx);
3632 for (i = 0; i < narenas; i++) {
3633 if (arenas[i] != NULL)
3634 malloc_mutex_lock(&arenas[i]->mtx);
3635 }
3636 malloc_mutex_unlock(&arenas_mtx);
3637
3638 malloc_mutex_lock(&base_mtx);
3639
3640 malloc_mutex_lock(&chunks_mtx);
3641}
3642
3643void
3644_malloc_postfork(void)
3645{
3646 unsigned i;
3647
3648 /* Release all mutexes, now that fork() has completed. */
3649
3650 malloc_mutex_unlock(&chunks_mtx);
3651
3652 malloc_mutex_unlock(&base_mtx);
3653
3654 malloc_mutex_lock(&arenas_mtx);
3655 for (i = 0; i < narenas; i++) {
3656 if (arenas[i] != NULL)
3657 malloc_mutex_unlock(&arenas[i]->mtx);
3658 }
3659 malloc_mutex_unlock(&arenas_mtx);
3660}
3661
3662/*
3663 * End library-private functions.
3664 */
3665/******************************************************************************/
| 283#endif
284
285/* sizeof(int) == (1 << SIZEOF_INT_2POW). */
286#ifndef SIZEOF_INT_2POW
287# define SIZEOF_INT_2POW 2
288#endif
289
290/* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
291#if (!defined(PIC) && !defined(NO_TLS))
292# define NO_TLS
293#endif
294
295/*
296 * Size and alignment of memory chunks that are allocated by the OS's virtual
297 * memory system.
298 *
299 * chunksize limits:
300 *
301 * 2^(pagesize_2pow - 1 + RUN_MIN_REGS_2POW) <= chunk_size <= 2^28
302 */
303#define CHUNK_2POW_DEFAULT 21
304#define CHUNK_2POW_MAX 28
305
306/*
307 * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
308 * so over-estimates are okay (up to a point), but under-estimates will
309 * negatively affect performance.
310 */
311#define CACHELINE_2POW 6
312#define CACHELINE ((size_t)(1 << CACHELINE_2POW))
313
314/*
315 * Maximum size class that is a multiple of the quantum, but not (necessarily)
316 * a power of 2. Above this size, allocations are rounded up to the nearest
317 * power of 2.
318 */
319#define SMALL_MAX_2POW_DEFAULT 9
320#define SMALL_MAX_DEFAULT (1 << SMALL_MAX_2POW_DEFAULT)
321
322/*
323 * Minimum number of regions that must fit into a run that serves quantum-size
324 * bin allocations.
325 *
326 * Note that if this is set too low, space will be wasted if there are size
327 * classes that are small enough that RUN_MIN_REGS regions don't fill a page.
328 * If this is set too high, then the overhead of searching through the bitmap
329 * that tracks region usage will become excessive.
330 */
331#define RUN_MIN_REGS_2POW 10
332#define RUN_MIN_REGS (1 << RUN_MIN_REGS_2POW)
333
334/*
335 * Maximum number of pages for a run that is used for bin allocations.
336 *
337 * Note that if this is set too low, then fragmentation for the largest bin
338 * size classes will be high. If this is set too high, then even small
339 * programs will often have to allocate more than two chunks early on.
340 */
341#define RUN_MAX_PAGES_2POW 4
342#define RUN_MAX_PAGES (1 << RUN_MAX_PAGES_2POW)
343
344/******************************************************************************/
345
346/*
347 * Mutexes based on spinlocks. We can't use normal pthread mutexes, because
348 * they require malloc()ed memory.
349 */
350typedef struct {
351 spinlock_t lock;
352} malloc_mutex_t;
353
354/* Set to true once the allocator has been initialized. */
355static bool malloc_initialized = false;
356
357/* Used to avoid initialization races. */
358static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
359
360/******************************************************************************/
361/*
362 * Statistics data structures.
363 */
364
365#ifdef MALLOC_STATS
366
367typedef struct malloc_bin_stats_s malloc_bin_stats_t;
368struct malloc_bin_stats_s {
369 /*
370 * Number of allocation requests that corresponded to the size of this
371 * bin.
372 */
373 uint64_t nrequests;
374
375 /* Total number of runs created for this bin's size class. */
376 uint64_t nruns;
377
378 /*
379 * Total number of run promotions/demotions for this bin's size class.
380 */
381 uint64_t npromote;
382 uint64_t ndemote;
383
384 /* High-water mark for this bin. */
385 unsigned long highruns;
386
387 /* Current number of runs in this bin. */
388 unsigned long curruns;
389};
390
391typedef struct arena_stats_s arena_stats_t;
392struct arena_stats_s {
393 /* Total byte count of allocated memory, not including overhead. */
394 size_t allocated;
395
396 /* Number of times each function was called. */
397 uint64_t nmalloc;
398 uint64_t ndalloc;
399 uint64_t nmadvise;
400
401 /* Number of large allocation requests. */
402 uint64_t large_nrequests;
403};
404
405typedef struct chunk_stats_s chunk_stats_t;
406struct chunk_stats_s {
407 /* Number of chunks that were allocated. */
408 uint64_t nchunks;
409
410 /* High-water mark for number of chunks allocated. */
411 unsigned long highchunks;
412
413 /*
414 * Current number of chunks allocated. This value isn't maintained for
415 * any other purpose, so keep track of it in order to be able to set
416 * highchunks.
417 */
418 unsigned long curchunks;
419};
420
421#endif /* #ifdef MALLOC_STATS */
422
423/******************************************************************************/
424/*
425 * Chunk data structures.
426 */
427
428/* Tree of chunks. */
429typedef struct chunk_node_s chunk_node_t;
430struct chunk_node_s {
431 /* Linkage for the chunk tree. */
432 RB_ENTRY(chunk_node_s) link;
433
434 /*
435 * Pointer to the chunk that this tree node is responsible for. In some
436 * (but certainly not all) cases, this data structure is placed at the
437 * beginning of the corresponding chunk, so this field may point to this
438 * node.
439 */
440 void *chunk;
441
442 /* Total chunk size. */
443 size_t size;
444};
445typedef struct chunk_tree_s chunk_tree_t;
446RB_HEAD(chunk_tree_s, chunk_node_s);
447
448/******************************************************************************/
449/*
450 * Arena data structures.
451 */
452
453typedef struct arena_s arena_t;
454typedef struct arena_bin_s arena_bin_t;
455
456typedef struct arena_chunk_map_s arena_chunk_map_t;
457struct arena_chunk_map_s {
458 bool free:1;
459 bool large:1;
460 unsigned npages:15; /* Limiting factor for CHUNK_2POW_MAX. */
461 unsigned pos:15;
462};
463
464/* Arena chunk header. */
465typedef struct arena_chunk_s arena_chunk_t;
466struct arena_chunk_s {
467 /* Arena that owns the chunk. */
468 arena_t *arena;
469
470 /* Linkage for the arena's chunk tree. */
471 RB_ENTRY(arena_chunk_s) link;
472
473 /*
474 * Number of pages in use. This is maintained in order to make
475 * detection of empty chunks fast.
476 */
477 uint32_t pages_used;
478
479 /*
480 * Array of counters that keeps track of how many free runs of each
481 * size are available in this chunk. This table is sized at compile
482 * time, which is wasteful. However, due to unrelated rounding, this
483 * doesn't actually waste any otherwise useful space.
484 *
485 * index == 2^n pages
486 *
487 * index | npages
488 * ------+-------
489 * 0 | 1
490 * 1 | 2
491 * 2 | 4
492 * 3 | 8
493 * :
494 */
495 uint32_t nfree_runs[CHUNK_2POW_MAX/* - PAGE_SHIFT */];
496
497 /* Map of pages within chunk that keeps track of free/large/small. */
498 arena_chunk_map_t map[1]; /* Dynamically sized. */
499};
500typedef struct arena_chunk_tree_s arena_chunk_tree_t;
501RB_HEAD(arena_chunk_tree_s, arena_chunk_s);
502
503typedef struct arena_run_s arena_run_t;
504struct arena_run_s {
505 /* Linkage for run rings. */
506 qr(arena_run_t) link;
507
508#ifdef MALLOC_DEBUG
509 uint32_t magic;
510# define ARENA_RUN_MAGIC 0x384adf93
511#endif
512
513 /* Bin this run is associated with. */
514 arena_bin_t *bin;
515
516 /* Bitmask of in-use regions (0: in use, 1: free). */
517#define REGS_MASK_NELMS \
518 (1 << (RUN_MIN_REGS_2POW - SIZEOF_INT_2POW - 2))
519 unsigned regs_mask[REGS_MASK_NELMS];
520
521 /* Index of first element that might have a free region. */
522 unsigned regs_minelm;
523
524 /* Number of free regions in run. */
525 unsigned nfree;
526
527 /*
528 * Current quartile for this run, one of: {RUN_QINIT, RUN_Q0, RUN_25,
529 * RUN_Q50, RUN_Q75, RUN_Q100}.
530 */
531#define RUN_QINIT 0
532#define RUN_Q0 1
533#define RUN_Q25 2
534#define RUN_Q50 3
535#define RUN_Q75 4
536#define RUN_Q100 5
537 unsigned quartile;
538
539 /*
540 * Limits on the number of free regions for the fullness quartile this
541 * run is currently in. If nfree goes outside these limits, the run
542 * is moved to a different fullness quartile.
543 */
544 unsigned free_max;
545 unsigned free_min;
546};
547
548/* Used for run ring headers, where the run isn't actually used. */
549typedef struct arena_run_link_s arena_run_link_t;
550struct arena_run_link_s {
551 /* Linkage for run rings. */
552 qr(arena_run_t) link;
553};
554
555struct arena_bin_s {
556 /*
557 * Current run being used to service allocations of this bin's size
558 * class.
559 */
560 arena_run_t *runcur;
561
562 /*
563 * Links into rings of runs, of various fullnesses (names indicate
564 * approximate lower bounds). A new run conceptually starts off in
565 * runsinit, and it isn't inserted into the runs0 ring until it
566 * reaches 25% full (hysteresis mechanism). For the run to be moved
567 * again, it must become either empty or 50% full. Thus, each ring
568 * contains runs that are within 50% above the advertised fullness for
569 * the ring. This provides a low-overhead mechanism for segregating
570 * runs into approximate fullness classes.
571 *
572 * Conceptually, there is a runs100 that contains completely full runs.
573 * Since we don't need to search for these runs though, no runs100 ring
574 * is actually maintained.
575 *
576 * These rings are useful when looking for an existing run to use when
577 * runcur is no longer usable. We look for usable runs in the
578 * following order:
579 *
580 * 1) runs50
581 * 2) runs25
582 * 3) runs0
583 * 4) runs75
584 *
585 * runs75 isn't a good place to look, because it contains runs that may
586 * be nearly completely full. Still, we look there as a last resort in
587 * order to avoid allocating a new run if at all possible.
588 */
589 /* arena_run_link_t runsinit; 0% <= fullness < 25% */
590 arena_run_link_t runs0; /* 0% < fullness < 50% */
591 arena_run_link_t runs25; /* 25% < fullness < 75% */
592 arena_run_link_t runs50; /* 50% < fullness < 100% */
593 arena_run_link_t runs75; /* 75% < fullness < 100% */
594 /* arena_run_link_t runs100; fullness == 100% */
595
596 /* Size of regions in a run for this bin's size class. */
597 size_t reg_size;
598
599 /* Total size of a run for this bin's size class. */
600 size_t run_size;
601
602 /* Total number of regions in a run for this bin's size class. */
603 uint32_t nregs;
604
605 /* Offset of first region in a run for this bin's size class. */
606 uint32_t reg0_offset;
607
608#ifdef MALLOC_STATS
609 /* Bin statistics. */
610 malloc_bin_stats_t stats;
611#endif
612};
613
614struct arena_s {
615#ifdef MALLOC_DEBUG
616 uint32_t magic;
617# define ARENA_MAGIC 0x947d3d24
618#endif
619
620 /* All operations on this arena require that mtx be locked. */
621 malloc_mutex_t mtx;
622
623#ifdef MALLOC_STATS
624 arena_stats_t stats;
625#endif
626
627 /*
628 * Tree of chunks this arena manages.
629 */
630 arena_chunk_tree_t chunks;
631
632 /*
633 * bins is used to store rings of free regions of the following sizes,
634 * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
635 *
636 * bins[i] | size |
637 * --------+------+
638 * 0 | 2 |
639 * 1 | 4 |
640 * 2 | 8 |
641 * --------+------+
642 * 3 | 16 |
643 * 4 | 32 |
644 * 5 | 48 |
645 * 6 | 64 |
646 * : :
647 * : :
648 * 33 | 496 |
649 * 34 | 512 |
650 * --------+------+
651 * 35 | 1024 |
652 * 36 | 2048 |
653 * --------+------+
654 */
655 arena_bin_t bins[1]; /* Dynamically sized. */
656};
657
658/******************************************************************************/
659/*
660 * Data.
661 */
662
663/* Number of CPUs. */
664static unsigned ncpus;
665
666/* VM page size. */
667static unsigned pagesize;
668static unsigned pagesize_2pow;
669
670/* Various bin-related settings. */
671static size_t bin_maxclass; /* Max size class for bins. */
672static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */
673static unsigned nqbins; /* Number of quantum-spaced bins. */
674static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */
675static size_t small_min;
676static size_t small_max;
677static unsigned tiny_min_2pow;
678
679/* Various quantum-related settings. */
680static size_t quantum;
681static size_t quantum_mask; /* (quantum - 1). */
682
683/* Various chunk-related settings. */
684static size_t chunk_size;
685static size_t chunk_size_mask; /* (chunk_size - 1). */
686static size_t arena_maxclass; /* Max size class for arenas. */
687static unsigned arena_chunk_maplen;
688
689/********/
690/*
691 * Chunks.
692 */
693
694/* Protects chunk-related data structures. */
695static malloc_mutex_t chunks_mtx;
696
697/* Tree of chunks that are stand-alone huge allocations. */
698static chunk_tree_t huge;
699
700#ifdef USE_BRK
701/*
702 * Try to use brk for chunk-size allocations, due to address space constraints.
703 */
704/* Result of first sbrk(0) call. */
705static void *brk_base;
706/* Current end of brk, or ((void *)-1) if brk is exhausted. */
707static void *brk_prev;
708/* Current upper limit on brk addresses. */
709static void *brk_max;
710#endif
711
712#ifdef MALLOC_STATS
713/*
714 * Byte counters for allocated/total space used by the chunks in the huge
715 * allocations tree.
716 */
717static uint64_t huge_nmalloc;
718static uint64_t huge_ndalloc;
719static size_t huge_allocated;
720#endif
721
722/*
723 * Tree of chunks that were previously allocated. This is used when allocating
724 * chunks, in an attempt to re-use address space.
725 */
726static chunk_tree_t old_chunks;
727
728/****************************/
729/*
730 * base (internal allocation).
731 */
732
733/*
734 * Current chunk that is being used for internal memory allocations. This
735 * chunk is carved up in cacheline-size quanta, so that there is no chance of
736 * false cache line sharing.
737 */
738static void *base_chunk;
739static void *base_next_addr;
740static void *base_past_addr; /* Addr immediately past base_chunk. */
741static chunk_node_t *base_chunk_nodes; /* LIFO cache of chunk nodes. */
742static malloc_mutex_t base_mtx;
743#ifdef MALLOC_STATS
744static uint64_t base_total;
745#endif
746
747/********/
748/*
749 * Arenas.
750 */
751
752/*
753 * Arenas that are used to service external requests. Not all elements of the
754 * arenas array are necessarily used; arenas are created lazily as needed.
755 */
756static arena_t **arenas;
757static unsigned narenas;
758#ifndef NO_TLS
759static unsigned next_arena;
760#endif
761static malloc_mutex_t arenas_mtx; /* Protects arenas initialization. */
762
763#ifndef NO_TLS
764/*
765 * Map of pthread_self() --> arenas[???], used for selecting an arena to use
766 * for allocations.
767 */
768static __thread arena_t *arenas_map;
769#endif
770
771#ifdef MALLOC_STATS
772/* Chunk statistics. */
773static chunk_stats_t stats_chunks;
774#endif
775
776/*******************************/
777/*
778 * Runtime configuration options.
779 */
780const char *_malloc_options;
781
782#ifndef NO_MALLOC_EXTRAS
783static bool opt_abort = true;
784static bool opt_junk = true;
785#else
786static bool opt_abort = false;
787static bool opt_junk = false;
788#endif
789static bool opt_hint = false;
790static bool opt_print_stats = false;
791static size_t opt_quantum_2pow = QUANTUM_2POW_MIN;
792static size_t opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
793static size_t opt_chunk_2pow = CHUNK_2POW_DEFAULT;
794static bool opt_utrace = false;
795static bool opt_sysv = false;
796static bool opt_xmalloc = false;
797static bool opt_zero = false;
798static int32_t opt_narenas_lshift = 0;
799
800typedef struct {
801 void *p;
802 size_t s;
803 void *r;
804} malloc_utrace_t;
805
806#define UTRACE(a, b, c) \
807 if (opt_utrace) { \
808 malloc_utrace_t ut = {a, b, c}; \
809 utrace(&ut, sizeof(ut)); \
810 }
811
812/******************************************************************************/
813/*
814 * Begin function prototypes for non-inline static functions.
815 */
816
817static void malloc_mutex_init(malloc_mutex_t *a_mutex);
818static void wrtmessage(const char *p1, const char *p2, const char *p3,
819 const char *p4);
820static void malloc_printf(const char *format, ...);
821static void *base_alloc(size_t size);
822static chunk_node_t *base_chunk_node_alloc(void);
823static void base_chunk_node_dealloc(chunk_node_t *node);
824#ifdef MALLOC_STATS
825static void stats_print(arena_t *arena);
826#endif
827static void *pages_map(void *addr, size_t size);
828static void pages_unmap(void *addr, size_t size);
829static void *chunk_alloc(size_t size);
830static void chunk_dealloc(void *chunk, size_t size);
831#ifndef NO_TLS
832static arena_t *choose_arena_hard(void);
833#endif
834static void arena_run_split(arena_t *arena, arena_run_t *run, bool large,
835 size_t size);
836static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
837static void arena_chunk_dealloc(arena_chunk_t *chunk);
838static void arena_bin_run_promote(arena_t *arena, arena_bin_t *bin,
839 arena_run_t *run);
840static void arena_bin_run_demote(arena_t *arena, arena_bin_t *bin,
841 arena_run_t *run);
842static arena_run_t *arena_run_alloc(arena_t *arena, bool large, size_t size);
843static void arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size);
844static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
845static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
846static void *arena_malloc(arena_t *arena, size_t size);
847static size_t arena_salloc(const void *ptr);
848static void *arena_ralloc(void *ptr, size_t size, size_t oldsize);
849static void arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
850static bool arena_new(arena_t *arena);
851static arena_t *arenas_extend(unsigned ind);
852static void *huge_malloc(size_t size);
853static void *huge_ralloc(void *ptr, size_t size, size_t oldsize);
854static void huge_dalloc(void *ptr);
855static void *imalloc(size_t size);
856static void *ipalloc(size_t alignment, size_t size);
857static void *icalloc(size_t size);
858static size_t isalloc(const void *ptr);
859static void *iralloc(void *ptr, size_t size);
860static void idalloc(void *ptr);
861static void malloc_print_stats(void);
862static bool malloc_init_hard(void);
863
864/*
865 * End function prototypes.
866 */
867/******************************************************************************/
868/*
869 * Begin mutex.
870 */
871
872static void
873malloc_mutex_init(malloc_mutex_t *a_mutex)
874{
875 static const spinlock_t lock = _SPINLOCK_INITIALIZER;
876
877 a_mutex->lock = lock;
878}
879
880static inline void
881malloc_mutex_lock(malloc_mutex_t *a_mutex)
882{
883
884 if (__isthreaded)
885 _SPINLOCK(&a_mutex->lock);
886}
887
888static inline void
889malloc_mutex_unlock(malloc_mutex_t *a_mutex)
890{
891
892 if (__isthreaded)
893 _SPINUNLOCK(&a_mutex->lock);
894}
895
896/*
897 * End mutex.
898 */
899/******************************************************************************/
900/*
901 * Begin Utility functions/macros.
902 */
903
904/* Return the chunk address for allocation address a. */
905#define CHUNK_ADDR2BASE(a) \
906 ((void *)((uintptr_t)(a) & ~chunk_size_mask))
907
908/* Return the chunk offset of address a. */
909#define CHUNK_ADDR2OFFSET(a) \
910 ((size_t)((uintptr_t)(a) & chunk_size_mask))
911
912/* Return the smallest chunk multiple that is >= s. */
913#define CHUNK_CEILING(s) \
914 (((s) + chunk_size_mask) & ~chunk_size_mask)
915
916/* Return the smallest cacheline multiple that is >= s. */
917#define CACHELINE_CEILING(s) \
918 (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
919
920/* Return the smallest quantum multiple that is >= a. */
921#define QUANTUM_CEILING(a) \
922 (((a) + quantum_mask) & ~quantum_mask)
923
924/* Compute the smallest power of 2 that is >= x. */
925static inline size_t
926pow2_ceil(size_t x)
927{
928
929 x--;
930 x |= x >> 1;
931 x |= x >> 2;
932 x |= x >> 4;
933 x |= x >> 8;
934 x |= x >> 16;
935#if (SIZEOF_PTR == 8)
936 x |= x >> 32;
937#endif
938 x++;
939 return (x);
940}
941
942static void
943wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
944{
945
946 _write(STDERR_FILENO, p1, strlen(p1));
947 _write(STDERR_FILENO, p2, strlen(p2));
948 _write(STDERR_FILENO, p3, strlen(p3));
949 _write(STDERR_FILENO, p4, strlen(p4));
950}
951
952void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
953 const char *p4) = wrtmessage;
954
955/*
956 * Print to stderr in such a way as to (hopefully) avoid memory allocation.
957 */
958static void
959malloc_printf(const char *format, ...)
960{
961 char buf[4096];
962 va_list ap;
963
964 va_start(ap, format);
965 vsnprintf(buf, sizeof(buf), format, ap);
966 va_end(ap);
967 _malloc_message(buf, "", "", "");
968}
969
970/******************************************************************************/
971
972static void *
973base_alloc(size_t size)
974{
975 void *ret;
976 size_t csize;
977
978 /* Round size up to nearest multiple of the cacheline size. */
979 csize = CACHELINE_CEILING(size);
980
981 malloc_mutex_lock(&base_mtx);
982
983 /* Make sure there's enough space for the allocation. */
984 if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
985 void *tchunk;
986
987 assert(csize <= chunk_size);
988
989 tchunk = chunk_alloc(chunk_size);
990 if (tchunk == NULL) {
991 ret = NULL;
992 goto RETURN;
993 }
994 base_chunk = tchunk;
995 base_next_addr = (void *)base_chunk;
996 base_past_addr = (void *)((uintptr_t)base_chunk + chunk_size);
997#ifdef MALLOC_STATS
998 base_total += chunk_size;
999#endif
1000 }
1001
1002 /* Allocate. */
1003 ret = base_next_addr;
1004 base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1005
1006RETURN:
1007 malloc_mutex_unlock(&base_mtx);
1008 return (ret);
1009}
1010
1011static chunk_node_t *
1012base_chunk_node_alloc(void)
1013{
1014 chunk_node_t *ret;
1015
1016 malloc_mutex_lock(&base_mtx);
1017 if (base_chunk_nodes != NULL) {
1018 ret = base_chunk_nodes;
1019 base_chunk_nodes = *(chunk_node_t **)ret;
1020 malloc_mutex_unlock(&base_mtx);
1021 } else {
1022 malloc_mutex_unlock(&base_mtx);
1023 ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t));
1024 }
1025
1026 return (ret);
1027}
1028
1029static void
1030base_chunk_node_dealloc(chunk_node_t *node)
1031{
1032
1033 malloc_mutex_lock(&base_mtx);
1034 *(chunk_node_t **)node = base_chunk_nodes;
1035 base_chunk_nodes = node;
1036 malloc_mutex_unlock(&base_mtx);
1037}
1038
1039/******************************************************************************/
1040
1041#ifdef MALLOC_STATS
1042static void
1043stats_print(arena_t *arena)
1044{
1045 unsigned i;
1046 int gap_start;
1047
1048 malloc_printf("allocated: %zu\n", arena->stats.allocated);
1049
1050 malloc_printf("calls:\n");
1051 malloc_printf(" %12s %12s %12s\n", "nmalloc","ndalloc", "nmadvise");
1052 malloc_printf(" %12llu %12llu %12llu\n",
1053 arena->stats.nmalloc, arena->stats.ndalloc, arena->stats.nmadvise);
1054
1055 malloc_printf("large requests: %llu\n", arena->stats.large_nrequests);
1056
1057 malloc_printf("bins:\n");
1058 malloc_printf("%13s %1s %4s %5s %6s %9s %5s %6s %7s %6s %6s\n",
1059 "bin", "", "size", "nregs", "run_sz", "nrequests", "nruns",
1060 "hiruns", "curruns", "npromo", "ndemo");
1061 for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
1062 if (arena->bins[i].stats.nrequests == 0) {
1063 if (gap_start == -1)
1064 gap_start = i;
1065 } else {
1066 if (gap_start != -1) {
1067 if (i > gap_start + 1) {
1068 /* Gap of more than one size class. */
1069 malloc_printf("[%u..%u]\n",
1070 gap_start, i - 1);
1071 } else {
1072 /* Gap of one size class. */
1073 malloc_printf("[%u]\n", gap_start);
1074 }
1075 gap_start = -1;
1076 }
1077 malloc_printf(
1078 "%13u %1s %4u %5u %6u %9llu %5llu"
1079 " %6lu %7lu %6llu %6llu\n",
1080 i,
1081 i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
1082 arena->bins[i].reg_size,
1083 arena->bins[i].nregs,
1084 arena->bins[i].run_size,
1085 arena->bins[i].stats.nrequests,
1086 arena->bins[i].stats.nruns,
1087 arena->bins[i].stats.highruns,
1088 arena->bins[i].stats.curruns,
1089 arena->bins[i].stats.npromote,
1090 arena->bins[i].stats.ndemote);
1091 }
1092 }
1093 if (gap_start != -1) {
1094 if (i > gap_start + 1) {
1095 /* Gap of more than one size class. */
1096 malloc_printf("[%u..%u]\n", gap_start, i - 1);
1097 } else {
1098 /* Gap of one size class. */
1099 malloc_printf("[%u]\n", gap_start);
1100 }
1101 }
1102}
1103#endif
1104
1105/*
1106 * End Utility functions/macros.
1107 */
1108/******************************************************************************/
1109/*
1110 * Begin chunk management functions.
1111 */
1112
1113static inline int
1114chunk_comp(chunk_node_t *a, chunk_node_t *b)
1115{
1116
1117 assert(a != NULL);
1118 assert(b != NULL);
1119
1120 if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
1121 return (-1);
1122 else if (a->chunk == b->chunk)
1123 return (0);
1124 else
1125 return (1);
1126}
1127
1128/* Generate red-black tree code for chunks. */
1129RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);
1130
1131static void *
1132pages_map(void *addr, size_t size)
1133{
1134 void *ret;
1135
1136 /*
1137 * We don't use MAP_FIXED here, because it can cause the *replacement*
1138 * of existing mappings, and we only want to create new mappings.
1139 */
1140 ret = mmap(addr, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON,
1141 -1, 0);
1142 assert(ret != NULL);
1143
1144 if (ret == MAP_FAILED)
1145 ret = NULL;
1146 else if (addr != NULL && ret != addr) {
1147 /*
1148 * We succeeded in mapping memory, but not in the right place.
1149 */
1150 if (munmap(ret, size) == -1) {
1151 char buf[STRERROR_BUF];
1152
1153 strerror_r(errno, buf, sizeof(buf));
1154 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1155 _getprogname(), buf);
1156 if (opt_abort)
1157 abort();
1158 }
1159 ret = NULL;
1160 }
1161
1162 assert(ret == NULL || (addr == NULL && ret != addr)
1163 || (addr != NULL && ret == addr));
1164 return (ret);
1165}
1166
1167static void
1168pages_unmap(void *addr, size_t size)
1169{
1170
1171 if (munmap(addr, size) == -1) {
1172 char buf[STRERROR_BUF];
1173
1174 strerror_r(errno, buf, sizeof(buf));
1175 malloc_printf("%s: (malloc) Error in munmap(): %s\n",
1176 _getprogname(), buf);
1177 if (opt_abort)
1178 abort();
1179 }
1180}
1181
1182static void *
1183chunk_alloc(size_t size)
1184{
1185 void *ret, *chunk;
1186 chunk_node_t *tchunk, *delchunk;
1187
1188 assert(size != 0);
1189 assert(size % chunk_size == 0);
1190
1191 malloc_mutex_lock(&chunks_mtx);
1192
1193 if (size == chunk_size) {
1194 /*
1195 * Check for address ranges that were previously chunks and try
1196 * to use them.
1197 */
1198
1199 tchunk = RB_MIN(chunk_tree_s, &old_chunks);
1200 while (tchunk != NULL) {
1201 /* Found an address range. Try to recycle it. */
1202
1203 chunk = tchunk->chunk;
1204 delchunk = tchunk;
1205 tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
1206
1207 /* Remove delchunk from the tree. */
1208 RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
1209 base_chunk_node_dealloc(delchunk);
1210
1211#ifdef USE_BRK
1212 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1213 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1214 /* Re-use a previously freed brk chunk. */
1215 ret = chunk;
1216 goto RETURN;
1217 }
1218#endif
1219 if ((ret = pages_map(chunk, size)) != NULL) {
1220 /* Success. */
1221 goto RETURN;
1222 }
1223 }
1224 }
1225
1226#ifdef USE_BRK
1227 /*
1228 * Try to create allocations in brk, in order to make full use of
1229 * limited address space.
1230 */
1231 if (brk_prev != (void *)-1) {
1232 void *brk_cur;
1233 intptr_t incr;
1234
1235 /*
1236 * The loop is necessary to recover from races with other
1237 * threads that are using brk for something other than malloc.
1238 */
1239 do {
1240 /* Get the current end of brk. */
1241 brk_cur = sbrk(0);
1242
1243 /*
1244 * Calculate how much padding is necessary to
1245 * chunk-align the end of brk.
1246 */
1247 incr = (intptr_t)size
1248 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
1249 if (incr == size) {
1250 ret = brk_cur;
1251 } else {
1252 ret = (void *)(intptr_t)brk_cur + incr;
1253 incr += size;
1254 }
1255
1256 brk_prev = sbrk(incr);
1257 if (brk_prev == brk_cur) {
1258 /* Success. */
1259 brk_max = (void *)(intptr_t)ret + size;
1260 goto RETURN;
1261 }
1262 } while (brk_prev != (void *)-1);
1263 }
1264#endif
1265
1266 /*
1267 * Try to over-allocate, but allow the OS to place the allocation
1268 * anywhere. Beware of size_t wrap-around.
1269 */
1270 if (size + chunk_size > size) {
1271 if ((ret = pages_map(NULL, size + chunk_size)) != NULL) {
1272 size_t offset = CHUNK_ADDR2OFFSET(ret);
1273
1274 /*
1275 * Success. Clean up unneeded leading/trailing space.
1276 */
1277 if (offset != 0) {
1278 /* Leading space. */
1279 pages_unmap(ret, chunk_size - offset);
1280
1281 ret = (void *)((uintptr_t)ret + (chunk_size -
1282 offset));
1283
1284 /* Trailing space. */
1285 pages_unmap((void *)((uintptr_t)ret + size),
1286 offset);
1287 } else {
1288 /* Trailing space only. */
1289 pages_unmap((void *)((uintptr_t)ret + size),
1290 chunk_size);
1291 }
1292 goto RETURN;
1293 }
1294 }
1295
1296 /* All strategies for allocation failed. */
1297 ret = NULL;
1298RETURN:
1299#ifdef MALLOC_STATS
1300 if (ret != NULL) {
1301 stats_chunks.nchunks += (size / chunk_size);
1302 stats_chunks.curchunks += (size / chunk_size);
1303 }
1304 if (stats_chunks.curchunks > stats_chunks.highchunks)
1305 stats_chunks.highchunks = stats_chunks.curchunks;
1306#endif
1307 malloc_mutex_unlock(&chunks_mtx);
1308
1309 assert(CHUNK_ADDR2BASE(ret) == ret);
1310 return (ret);
1311}
1312
1313static void
1314chunk_dealloc(void *chunk, size_t size)
1315{
1316 size_t offset;
1317 chunk_node_t key;
1318 chunk_node_t *node;
1319
1320 assert(chunk != NULL);
1321 assert(CHUNK_ADDR2BASE(chunk) == chunk);
1322 assert(size != 0);
1323 assert(size % chunk_size == 0);
1324
1325 malloc_mutex_lock(&chunks_mtx);
1326
1327#ifdef USE_BRK
1328 if ((uintptr_t)chunk >= (uintptr_t)brk_base
1329 && (uintptr_t)chunk < (uintptr_t)brk_max) {
1330 void *brk_cur;
1331
1332 /* Get the current end of brk. */
1333 brk_cur = sbrk(0);
1334
1335 /*
1336 * Try to shrink the data segment if this chunk is at the end
1337 * of the data segment. The sbrk() call here is subject to a
1338 * race condition with threads that use brk(2) or sbrk(2)
1339 * directly, but the alternative would be to leak memory for
1340 * the sake of poorly designed multi-threaded programs.
1341 */
1342 if (brk_cur == brk_max
1343 && (void *)(uintptr_t)chunk + size == brk_max
1344 && sbrk(-(intptr_t)size) == brk_max) {
1345 if (brk_prev == brk_max) {
1346 /* Success. */
1347 brk_prev = (void *)(intptr_t)brk_max
1348 - (intptr_t)size;
1349 brk_max = brk_prev;
1350 }
1351 goto RETURN;
1352 } else
1353 madvise(chunk, size, MADV_FREE);
1354 } else
1355#endif
1356 pages_unmap(chunk, size);
1357
1358 /*
1359 * Iteratively create records of each chunk-sized memory region that
1360 * 'chunk' is comprised of, so that the address range can be recycled
1361 * if memory usage increases later on.
1362 */
1363 for (offset = 0; offset < size; offset += chunk_size) {
1364 /*
1365 * It is possible for chunk to overlap existing entries in
1366 * old_chunks if it is a huge allocation, so take care to not
1367 * leak tree nodes.
1368 */
1369 key.chunk = (void *)((uintptr_t)chunk + (uintptr_t)offset);
1370 if (RB_FIND(chunk_tree_s, &old_chunks, &key) == NULL) {
1371 node = base_chunk_node_alloc();
1372 if (node == NULL)
1373 break;
1374
1375 node->chunk = key.chunk;
1376 node->size = chunk_size;
1377 RB_INSERT(chunk_tree_s, &old_chunks, node);
1378 }
1379 }
1380
1381#ifdef USE_BRK
1382RETURN:
1383#endif
1384#ifdef MALLOC_STATS
1385 stats_chunks.curchunks -= (size / chunk_size);
1386#endif
1387 malloc_mutex_unlock(&chunks_mtx);
1388}
1389
1390/*
1391 * End chunk management functions.
1392 */
1393/******************************************************************************/
1394/*
1395 * Begin arena.
1396 */
1397
1398/*
1399 * Choose an arena based on a per-thread value (fast-path code, calls slow-path
1400 * code if necessary.
1401 */
1402static inline arena_t *
1403choose_arena(void)
1404{
1405 arena_t *ret;
1406
1407 /*
1408 * We can only use TLS if this is a PIC library, since for the static
1409 * library version, libc's malloc is used by TLS allocation, which
1410 * introduces a bootstrapping issue.
1411 */
1412#ifndef NO_TLS
1413 if (__isthreaded == false) {
1414 /*
1415 * Avoid the overhead of TLS for single-threaded operation. If the
1416 * app switches to threaded mode, the initial thread may end up
1417 * being assigned to some other arena, but this one-time switch
1418 * shouldn't cause significant issues.
1419 * */
1420 return (arenas[0]);
1421 }
1422
1423 ret = arenas_map;
1424 if (ret == NULL)
1425 ret = choose_arena_hard();
1426#else
1427 if (__isthreaded) {
1428 unsigned long ind;
1429
1430 /*
1431 * Hash _pthread_self() to one of the arenas. There is a prime
1432 * number of arenas, so this has a reasonable chance of
1433 * working. Even so, the hashing can be easily thwarted by
1434 * inconvenient _pthread_self() values. Without specific
1435 * knowledge of how _pthread_self() calculates values, we can't
1436 * easily do much better than this.
1437 */
1438 ind = (unsigned long) _pthread_self() % narenas;
1439
1440 /*
1441 * Optimistially assume that arenas[ind] has been initialized.
1442 * At worst, we find out that some other thread has already
1443 * done so, after acquiring the lock in preparation. Note that
1444 * this lazy locking also has the effect of lazily forcing
1445 * cache coherency; without the lock acquisition, there's no
1446 * guarantee that modification of arenas[ind] by another thread
1447 * would be seen on this CPU for an arbitrary amount of time.
1448 *
1449 * In general, this approach to modifying a synchronized value
1450 * isn't a good idea, but in this case we only ever modify the
1451 * value once, so things work out well.
1452 */
1453 ret = arenas[ind];
1454 if (ret == NULL) {
1455 /*
1456 * Avoid races with another thread that may have already
1457 * initialized arenas[ind].
1458 */
1459 malloc_mutex_lock(&arenas_mtx);
1460 if (arenas[ind] == NULL)
1461 ret = arenas_extend((unsigned)ind);
1462 else
1463 ret = arenas[ind];
1464 malloc_mutex_unlock(&arenas_mtx);
1465 }
1466 } else
1467 ret = arenas[0];
1468#endif
1469
1470 assert(ret != NULL);
1471 return (ret);
1472}
1473
1474#ifndef NO_TLS
1475/*
1476 * Choose an arena based on a per-thread value (slow-path code only, called
1477 * only by choose_arena()).
1478 */
1479static arena_t *
1480choose_arena_hard(void)
1481{
1482 arena_t *ret;
1483
1484 assert(__isthreaded);
1485
1486 /* Assign one of the arenas to this thread, in a round-robin fashion. */
1487 malloc_mutex_lock(&arenas_mtx);
1488 ret = arenas[next_arena];
1489 if (ret == NULL)
1490 ret = arenas_extend(next_arena);
1491 if (ret == NULL) {
1492 /*
1493 * Make sure that this function never returns NULL, so that
1494 * choose_arena() doesn't have to check for a NULL return
1495 * value.
1496 */
1497 ret = arenas[0];
1498 }
1499 next_arena = (next_arena + 1) % narenas;
1500 malloc_mutex_unlock(&arenas_mtx);
1501 arenas_map = ret;
1502
1503 return (ret);
1504}
1505#endif
1506
1507static inline int
1508arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
1509{
1510
1511 assert(a != NULL);
1512 assert(b != NULL);
1513
1514 if ((uintptr_t)a < (uintptr_t)b)
1515 return (-1);
1516 else if (a == b)
1517 return (0);
1518 else
1519 return (1);
1520}
1521
1522/* Generate red-black tree code for arena chunks. */
1523RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
1524
1525static inline void *
1526arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
1527{
1528 void *ret;
1529 unsigned i, mask, bit, regind;
1530
1531 assert(run->magic == ARENA_RUN_MAGIC);
1532
1533 for (i = run->regs_minelm; i < REGS_MASK_NELMS; i++) {
1534 mask = run->regs_mask[i];
1535 if (mask != 0) {
1536 /* Usable allocation found. */
1537 bit = ffs(mask) - 1;
1538
1539 regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
1540 ret = (void *)&((char *)run)[bin->reg0_offset
1541 + (bin->reg_size * regind)];
1542
1543 /* Clear bit. */
1544 mask ^= (1 << bit);
1545 run->regs_mask[i] = mask;
1546
1547 return (ret);
1548 } else {
1549 /*
1550 * Make a note that nothing before this element
1551 * contains a free region.
1552 */
1553 run->regs_minelm = i + 1;
1554 }
1555 }
1556 /* Not reached. */
1557 assert(0);
1558 return (NULL);
1559}
1560
1561static inline void
1562arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
1563{
1564 /*
1565 * To divide by a number D that is not a power of two we multiply
1566 * by (2^21 / D) and then right shift by 21 positions.
1567 *
1568 * X / D
1569 *
1570 * becomes
1571 *
1572 * (size_invs[(D >> QUANTUM_2POW_MIN) - 3] * D) >> SIZE_INV_SHIFT
1573 */
1574#define SIZE_INV_SHIFT 21
1575#define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
1576 static const unsigned size_invs[] = {
1577 SIZE_INV(3),
1578 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
1579 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
1580 SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
1581 SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
1582 SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
1583 SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
1584 SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
1585#if (QUANTUM_2POW_MIN < 4)
1586 ,
1587 SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
1588 SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
1589 SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
1590 SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
1591 SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
1592 SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
1593 SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
1594 SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
1595#endif
1596 };
1597 unsigned diff, regind, elm, bit;
1598
1599 assert(run->magic == ARENA_RUN_MAGIC);
1600 assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
1601 >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
1602
1603 /*
1604 * Avoid doing division with a variable divisor if possible. Using
1605 * actual division here can reduce allocator throughput by over 20%!
1606 */
1607 diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
1608 if ((size & (size - 1)) == 0) {
1609 /*
1610 * log2_table allows fast division of a power of two in the
1611 * [1..128] range.
1612 *
1613 * (x / divisor) becomes (x >> log2_table[divisor - 1]).
1614 */
1615 static const unsigned char log2_table[] = {
1616 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
1617 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
1618 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1619 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
1620 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1621 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1622 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1623 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
1624 };
1625
1626 if (size <= 128)
1627 regind = (diff >> log2_table[size - 1]);
1628 else if (size <= 32768)
1629 regind = diff >> (8 + log2_table[(size >> 8) - 1]);
1630 else {
1631 /*
1632 * The page size is too large for us to use the lookup
1633 * table. Use real division.
1634 */
1635 regind = diff / size;
1636 }
1637 } else if (size <= ((sizeof(size_invs) / sizeof(unsigned))
1638 << QUANTUM_2POW_MIN) + 2) {
1639 regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
1640 regind >>= SIZE_INV_SHIFT;
1641 } else {
1642 /*
1643 * size_invs isn't large enough to handle this size class, so
1644 * calculate regind using actual division. This only happens
1645 * if the user increases small_max via the 'S' runtime
1646 * configuration option.
1647 */
1648 regind = diff / size;
1649 };
1650 assert(regind == diff / size);
1651 assert(regind < bin->nregs);
1652
1653 elm = regind >> (SIZEOF_INT_2POW + 3);
1654 if (elm < run->regs_minelm)
1655 run->regs_minelm = elm;
1656 bit = regind - (elm << (SIZEOF_INT_2POW + 3));
1657 assert((run->regs_mask[elm] & (1 << bit)) == 0);
1658 run->regs_mask[elm] |= (1 << bit);
1659#undef SIZE_INV
1660#undef SIZE_INV_SHIFT
1661}
1662
1663static void
1664arena_run_split(arena_t *arena, arena_run_t *run, bool large, size_t size)
1665{
1666 arena_chunk_t *chunk;
1667 unsigned run_ind, map_offset, total_pages, need_pages;
1668 unsigned i, log2_run_pages, run_pages;
1669
1670 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1671 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1672 >> pagesize_2pow);
1673 assert(chunk->map[run_ind].free);
1674 total_pages = chunk->map[run_ind].npages;
1675 need_pages = (size >> pagesize_2pow);
1676
1677 assert(chunk->map[run_ind].free);
1678 assert(chunk->map[run_ind].large == false);
1679 assert(chunk->map[run_ind].npages == total_pages);
1680
1681 /* Split enough pages from the front of run to fit allocation size. */
1682 map_offset = run_ind;
1683 for (i = 0; i < need_pages; i++) {
1684 chunk->map[map_offset + i].free = false;
1685 chunk->map[map_offset + i].large = large;
1686 chunk->map[map_offset + i].npages = need_pages;
1687 chunk->map[map_offset + i].pos = i;
1688 }
1689
1690 /* Update map for trailing pages. */
1691 map_offset += need_pages;
1692 while (map_offset < run_ind + total_pages) {
1693 log2_run_pages = ffs(map_offset) - 1;
1694 run_pages = (1 << log2_run_pages);
1695
1696 chunk->map[map_offset].free = true;
1697 chunk->map[map_offset].large = false;
1698 chunk->map[map_offset].npages = run_pages;
1699
1700 chunk->nfree_runs[log2_run_pages]++;
1701
1702 map_offset += run_pages;
1703 }
1704
1705 chunk->pages_used += (size >> pagesize_2pow);
1706}
1707
1708static arena_chunk_t *
1709arena_chunk_alloc(arena_t *arena)
1710{
1711 arena_chunk_t *chunk;
1712 unsigned i, j, header_npages, pow2_header_npages, map_offset;
1713 unsigned log2_run_pages, run_pages;
1714 size_t header_size;
1715
1716 chunk = (arena_chunk_t *)chunk_alloc(chunk_size);
1717 if (chunk == NULL)
1718 return (NULL);
1719
1720 chunk->arena = arena;
1721
1722 RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
1723
1724 /*
1725 * Claim that no pages are in use, since the header is merely overhead.
1726 */
1727 chunk->pages_used = 0;
1728
1729 memset(&chunk->nfree_runs, 0, sizeof(chunk->nfree_runs));
1730
1731 header_size = (size_t)((uintptr_t)&chunk->map[arena_chunk_maplen]
1732 - (uintptr_t)chunk);
1733 if (header_size % pagesize != 0) {
1734 /* Round up to the nearest page boundary. */
1735 header_size += pagesize - (header_size % pagesize);
1736 }
1737
1738 header_npages = header_size >> pagesize_2pow;
1739 pow2_header_npages = pow2_ceil(header_npages);
1740
1741 /*
1742 * Iteratively mark runs as in use, until we've spoken for the entire
1743 * header.
1744 */
1745 map_offset = 0;
1746 for (i = 0; header_npages > 0; i++) {
1747 if ((pow2_header_npages >> i) <= header_npages) {
1748 for (j = 0; j < (pow2_header_npages >> i); j++) {
1749 chunk->map[map_offset + j].free = false;
1750 chunk->map[map_offset + j].large = false;
1751 chunk->map[map_offset + j].npages =
1752 (pow2_header_npages >> i);
1753 chunk->map[map_offset + j].pos = j;
1754 }
1755 header_npages -= (pow2_header_npages >> i);
1756 map_offset += (pow2_header_npages >> i);
1757 }
1758 }
1759
1760 /*
1761 * Finish initializing map. The chunk header takes up some space at
1762 * the beginning of the chunk, which we just took care of by
1763 * "allocating" the leading pages.
1764 */
1765 while (map_offset < (chunk_size >> pagesize_2pow)) {
1766 log2_run_pages = ffs(map_offset) - 1;
1767 run_pages = (1 << log2_run_pages);
1768
1769 chunk->map[map_offset].free = true;
1770 chunk->map[map_offset].large = false;
1771 chunk->map[map_offset].npages = run_pages;
1772
1773 chunk->nfree_runs[log2_run_pages]++;
1774
1775 map_offset += run_pages;
1776 }
1777
1778 return (chunk);
1779}
1780
1781static void
1782arena_chunk_dealloc(arena_chunk_t *chunk)
1783{
1784
1785 RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks, chunk);
1786
1787 chunk_dealloc((void *)chunk, chunk_size);
1788}
1789
1790static void
1791arena_bin_run_promote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1792{
1793
1794 assert(bin == run->bin);
1795
1796 /* Promote. */
1797 assert(run->free_min > run->nfree);
1798 assert(run->quartile < RUN_Q100);
1799 run->quartile++;
1800#ifdef MALLOC_STATS
1801 bin->stats.npromote++;
1802#endif
1803
1804 /* Re-file run. */
1805 switch (run->quartile) {
1806 case RUN_QINIT:
1807 assert(0);
1808 break;
1809 case RUN_Q0:
1810 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1811 run->free_max = bin->nregs - 1;
1812 run->free_min = (bin->nregs >> 1) + 1;
1813 assert(run->nfree <= run->free_max);
1814 assert(run->nfree >= run->free_min);
1815 break;
1816 case RUN_Q25:
1817 qr_remove(run, link);
1818 qr_before_insert((arena_run_t *)&bin->runs25, run,
1819 link);
1820 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1821 run->free_min = (bin->nregs >> 2) + 1;
1822 assert(run->nfree <= run->free_max);
1823 assert(run->nfree >= run->free_min);
1824 break;
1825 case RUN_Q50:
1826 qr_remove(run, link);
1827 qr_before_insert((arena_run_t *)&bin->runs50, run,
1828 link);
1829 run->free_max = (bin->nregs >> 1) - 1;
1830 run->free_min = 1;
1831 assert(run->nfree <= run->free_max);
1832 assert(run->nfree >= run->free_min);
1833 break;
1834 case RUN_Q75:
1835 /*
1836 * Skip RUN_Q75 during promotion from RUN_Q50.
1837 * Separate handling of RUN_Q75 and RUN_Q100 allows us
1838 * to keep completely full runs in RUN_Q100, thus
1839 * guaranteeing that runs in RUN_Q75 are only mostly
1840 * full. This provides a method for avoiding a linear
1841 * search for non-full runs, which avoids some
1842 * pathological edge cases.
1843 */
1844 run->quartile++;
1845 /* Fall through. */
1846 case RUN_Q100:
1847 qr_remove(run, link);
1848 assert(bin->runcur == run);
1849 bin->runcur = NULL;
1850 run->free_max = 0;
1851 run->free_min = 0;
1852 assert(run->nfree <= run->free_max);
1853 assert(run->nfree >= run->free_min);
1854 break;
1855 default:
1856 assert(0);
1857 break;
1858 }
1859}
1860
1861static void
1862arena_bin_run_demote(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
1863{
1864
1865 assert(bin == run->bin);
1866
1867 /* Demote. */
1868 assert(run->free_max < run->nfree);
1869 assert(run->quartile > RUN_QINIT);
1870 run->quartile--;
1871#ifdef MALLOC_STATS
1872 bin->stats.ndemote++;
1873#endif
1874
1875 /* Re-file run. */
1876 switch (run->quartile) {
1877 case RUN_QINIT:
1878 qr_remove(run, link);
1879#ifdef MALLOC_STATS
1880 bin->stats.curruns--;
1881#endif
1882 if (bin->runcur == run)
1883 bin->runcur = NULL;
1884#ifdef MALLOC_DEBUG
1885 run->magic = 0;
1886#endif
1887 arena_run_dalloc(arena, run, bin->run_size);
1888 break;
1889 case RUN_Q0:
1890 qr_remove(run, link);
1891 qr_before_insert((arena_run_t *)&bin->runs0, run, link);
1892 run->free_max = bin->nregs - 1;
1893 run->free_min = (bin->nregs >> 1) + 1;
1894 assert(run->nfree <= run->free_max);
1895 assert(run->nfree >= run->free_min);
1896 break;
1897 case RUN_Q25:
1898 qr_remove(run, link);
1899 qr_before_insert((arena_run_t *)&bin->runs25, run,
1900 link);
1901 run->free_max = ((bin->nregs >> 2) * 3) - 1;
1902 run->free_min = (bin->nregs >> 2) + 1;
1903 assert(run->nfree <= run->free_max);
1904 assert(run->nfree >= run->free_min);
1905 break;
1906 case RUN_Q50:
1907 qr_remove(run, link);
1908 qr_before_insert((arena_run_t *)&bin->runs50, run,
1909 link);
1910 run->free_max = (bin->nregs >> 1) - 1;
1911 run->free_min = 1;
1912 assert(run->nfree <= run->free_max);
1913 assert(run->nfree >= run->free_min);
1914 break;
1915 case RUN_Q75:
1916 qr_before_insert((arena_run_t *)&bin->runs75, run,
1917 link);
1918 run->free_max = (bin->nregs >> 2) - 1;
1919 run->free_min = 1;
1920 assert(run->nfree <= run->free_max);
1921 assert(run->nfree >= run->free_min);
1922 break;
1923 case RUN_Q100:
1924 default:
1925 assert(0);
1926 break;
1927 }
1928}
1929
1930static arena_run_t *
1931arena_run_alloc(arena_t *arena, bool large, size_t size)
1932{
1933 arena_run_t *run;
1934 unsigned min_ind, i, j;
1935 arena_chunk_t *chunk;
1936#ifndef NDEBUG
1937 int rep = 0;
1938#endif
1939
1940 assert(size <= arena_maxclass);
1941
1942AGAIN:
1943#ifndef NDEBUG
1944 rep++;
1945 assert(rep <= 2);
1946#endif
1947
1948 /*
1949 * Search through arena's chunks in address order for a run that is
1950 * large enough. Look for a precise fit, but do not pass up a chunk
1951 * that has a run which is large enough to split.
1952 */
1953 min_ind = ffs(size >> pagesize_2pow) - 1;
1954 RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
1955 for (i = min_ind;
1956 i < (opt_chunk_2pow - pagesize_2pow);
1957 i++) {
1958 if (chunk->nfree_runs[i] > 0) {
1959 arena_chunk_map_t *map = chunk->map;
1960
1961 /* Scan chunk's map for free run. */
1962 for (j = 0;
1963 j < arena_chunk_maplen;
1964 j += map[j].npages) {
1965 if (map[j].free
1966 && map[j].npages == (1 << i))
1967 {/*<----------------------------*/
1968 run = (arena_run_t *)&((char *)chunk)[j
1969 << pagesize_2pow];
1970
1971 assert(chunk->nfree_runs[i] > 0);
1972 chunk->nfree_runs[i]--;
1973
1974 /* Update page map. */
1975 arena_run_split(arena, run, large, size);
1976
1977 return (run);
1978 }/*---------------------------->*/
1979 }
1980 /* Not reached. */
1981 assert(0);
1982 }
1983 }
1984 }
1985
1986 /* No usable runs. Allocate a new chunk, then try again. */
1987 if (arena_chunk_alloc(arena) == NULL)
1988 return (NULL);
1989 goto AGAIN;
1990}
1991
1992static void
1993arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size)
1994{
1995 arena_chunk_t *chunk;
1996 unsigned run_ind, buddy_ind, base_run_ind, run_pages, log2_run_pages;
1997
1998 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1999 run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
2000 >> pagesize_2pow);
2001 run_pages = (size >> pagesize_2pow);
2002 log2_run_pages = ffs(run_pages) - 1;
2003 assert(run_pages > 0);
2004
2005 /* Subtract pages from count of pages used in chunk. */
2006 chunk->pages_used -= run_pages;
2007
2008 /* Mark run as deallocated. */
2009 chunk->map[run_ind].free = true;
2010 chunk->map[run_ind].large = false;
2011 chunk->map[run_ind].npages = run_pages;
2012
2013 /*
2014 * Tell the kernel that we don't need the data in this run, but only if
2015 * requested via runtime configuration.
2016 */
2017 if (opt_hint) {
2018 madvise(run, size, MADV_FREE);
2019#ifdef MALLOC_STATS
2020 arena->stats.nmadvise += (size >> pagesize_2pow);
2021#endif
2022 }
2023
2024 /*
2025 * Iteratively coalesce with buddies. Conceptually, the buddy scheme
2026 * induces a tree on the set of pages. If we know the number of pages
2027 * in the subtree rooted at the current node, we can quickly determine
2028 * whether a run is the left or right buddy, and then calculate the
2029 * buddy's index.
2030 */
2031 for (;
2032 (run_pages = (1 << log2_run_pages)) < arena_chunk_maplen;
2033 log2_run_pages++) {
2034 if (((run_ind >> log2_run_pages) & 1) == 0) {
2035 /* Current run precedes its buddy. */
2036 buddy_ind = run_ind + run_pages;
2037 base_run_ind = run_ind;
2038 } else {
2039 /* Current run follows its buddy. */
2040 buddy_ind = run_ind - run_pages;
2041 base_run_ind = buddy_ind;
2042 }
2043
2044 if (chunk->map[buddy_ind].free == false
2045 || chunk->map[buddy_ind].npages != run_pages)
2046 break;
2047
2048 assert(chunk->nfree_runs[log2_run_pages] > 0);
2049 chunk->nfree_runs[log2_run_pages]--;
2050
2051 /* Coalesce. */
2052 chunk->map[base_run_ind].npages = (run_pages << 1);
2053
2054 /* Update run_ind to be the beginning of the coalesced run. */
2055 run_ind = base_run_ind;
2056 }
2057
2058 chunk->nfree_runs[log2_run_pages]++;
2059
2060 /* Free pages, to the extent possible. */
2061 if (chunk->pages_used == 0) {
2062 /* This chunk is completely unused now, so deallocate it. */
2063 arena_chunk_dealloc(chunk);
2064 }
2065}
2066
2067static arena_run_t *
2068arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2069{
2070 arena_run_t *run;
2071 unsigned i, remainder;
2072
2073 /* Look for a usable run. */
2074 if ((run = qr_next((arena_run_t *)&bin->runs50, link))
2075 != (arena_run_t *)&bin->runs50
2076 || (run = qr_next((arena_run_t *)&bin->runs25, link))
2077 != (arena_run_t *)&bin->runs25
2078 || (run = qr_next((arena_run_t *)&bin->runs0, link))
2079 != (arena_run_t *)&bin->runs0
2080 || (run = qr_next((arena_run_t *)&bin->runs75, link))
2081 != (arena_run_t *)&bin->runs75) {
2082 /* run is guaranteed to have available space. */
2083 qr_remove(run, link);
2084 return (run);
2085 }
2086 /* No existing runs have any space available. */
2087
2088 /* Allocate a new run. */
2089 run = arena_run_alloc(arena, false, bin->run_size);
2090 if (run == NULL)
2091 return (NULL);
2092
2093 /* Initialize run internals. */
2094 qr_new(run, link);
2095 run->bin = bin;
2096
2097 for (i = 0; i < (bin->nregs >> (SIZEOF_INT_2POW + 3)); i++)
2098 run->regs_mask[i] = UINT_MAX;
2099 remainder = bin->nregs % (1 << (SIZEOF_INT_2POW + 3));
2100 if (remainder != 0) {
2101 run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3))
2102 - remainder));
2103 i++;
2104 }
2105 for (; i < REGS_MASK_NELMS; i++)
2106 run->regs_mask[i] = 0;
2107
2108 run->regs_minelm = 0;
2109
2110 run->nfree = bin->nregs;
2111 run->quartile = RUN_QINIT;
2112 run->free_max = bin->nregs;
2113 run->free_min = ((bin->nregs >> 2) * 3) + 1;
2114#ifdef MALLOC_DEBUG
2115 run->magic = ARENA_RUN_MAGIC;
2116#endif
2117
2118#ifdef MALLOC_STATS
2119 bin->stats.nruns++;
2120 bin->stats.curruns++;
2121 if (bin->stats.curruns > bin->stats.highruns)
2122 bin->stats.highruns = bin->stats.curruns;
2123#endif
2124 return (run);
2125}
2126
2127/* bin->runcur must have space available before this function is called. */
2128static inline void *
2129arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
2130{
2131 void *ret;
2132
2133 assert(run->magic == ARENA_RUN_MAGIC);
2134 assert(run->nfree > 0);
2135
2136 ret = arena_run_reg_alloc(run, bin);
2137 assert(ret != NULL);
2138 run->nfree--;
2139 if (run->nfree < run->free_min) {
2140 /* Promote run to higher fullness quartile. */
2141 arena_bin_run_promote(arena, bin, run);
2142 }
2143
2144 return (ret);
2145}
2146
2147/* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
2148static void *
2149arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
2150{
2151
2152 assert(bin->runcur == NULL || bin->runcur->quartile == RUN_Q100);
2153
2154 bin->runcur = arena_bin_nonfull_run_get(arena, bin);
2155 if (bin->runcur == NULL)
2156 return (NULL);
2157 assert(bin->runcur->magic == ARENA_RUN_MAGIC);
2158 assert(bin->runcur->nfree > 0);
2159
2160 return (arena_bin_malloc_easy(arena, bin, bin->runcur));
2161}
2162
2163static void *
2164arena_malloc(arena_t *arena, size_t size)
2165{
2166 void *ret;
2167
2168 assert(arena != NULL);
2169 assert(arena->magic == ARENA_MAGIC);
2170 assert(size != 0);
2171 assert(QUANTUM_CEILING(size) <= arena_maxclass);
2172
2173 if (size <= bin_maxclass) {
2174 arena_bin_t *bin;
2175 arena_run_t *run;
2176
2177 /* Small allocation. */
2178
2179 if (size < small_min) {
2180 /* Tiny. */
2181 size = pow2_ceil(size);
2182 bin = &arena->bins[ffs(size >> (tiny_min_2pow + 1))];
2183#if (!defined(NDEBUG) || defined(MALLOC_STATS))
2184 /*
2185 * Bin calculation is always correct, but we may need
2186 * to fix size for the purposes of assertions and/or
2187 * stats accuracy.
2188 */
2189 if (size < (1 << tiny_min_2pow))
2190 size = (1 << tiny_min_2pow);
2191#endif
2192 } else if (size <= small_max) {
2193 /* Quantum-spaced. */
2194 size = QUANTUM_CEILING(size);
2195 bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
2196 - 1];
2197 } else {
2198 /* Sub-page. */
2199 size = pow2_ceil(size);
2200 bin = &arena->bins[ntbins + nqbins
2201 + (ffs(size >> opt_small_max_2pow) - 2)];
2202 }
2203 assert(size == bin->reg_size);
2204
2205 malloc_mutex_lock(&arena->mtx);
2206 if ((run = bin->runcur) != NULL)
2207 ret = arena_bin_malloc_easy(arena, bin, run);
2208 else
2209 ret = arena_bin_malloc_hard(arena, bin);
2210
2211#ifdef MALLOC_STATS
2212 bin->stats.nrequests++;
2213#endif
2214 } else {
2215 /* Medium allocation. */
2216 size = pow2_ceil(size);
2217 malloc_mutex_lock(&arena->mtx);
2218 ret = (void *)arena_run_alloc(arena, true, size);
2219#ifdef MALLOC_STATS
2220 arena->stats.large_nrequests++;
2221#endif
2222 }
2223
2224#ifdef MALLOC_STATS
2225 arena->stats.nmalloc++;
2226 if (ret != NULL)
2227 arena->stats.allocated += size;
2228#endif
2229
2230 malloc_mutex_unlock(&arena->mtx);
2231
2232 if (opt_junk && ret != NULL)
2233 memset(ret, 0xa5, size);
2234 else if (opt_zero && ret != NULL)
2235 memset(ret, 0, size);
2236 return (ret);
2237}
2238
2239/* Return the size of the allocation pointed to by ptr. */
2240static size_t
2241arena_salloc(const void *ptr)
2242{
2243 size_t ret;
2244 arena_chunk_t *chunk;
2245 uint32_t pageind;
2246 arena_chunk_map_t mapelm;
2247
2248 assert(ptr != NULL);
2249 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2250
2251 /*
2252 * No arena data structures that we query here can change in a way that
2253 * affects this function, so we don't need to lock.
2254 */
2255 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2256 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2257 mapelm = chunk->map[pageind];
2258 assert(mapelm.free == false);
2259 if (mapelm.large == false) {
2260 arena_run_t *run;
2261
2262 pageind -= mapelm.pos;
2263
2264 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2265 assert(run->magic == ARENA_RUN_MAGIC);
2266 ret = run->bin->reg_size;
2267 } else
2268 ret = mapelm.npages << pagesize_2pow;
2269
2270 return (ret);
2271}
2272
2273static void *
2274arena_ralloc(void *ptr, size_t size, size_t oldsize)
2275{
2276 void *ret;
2277
2278 /* Avoid moving the allocation if the size class would not change. */
2279 if (size < small_min) {
2280 if (oldsize < small_min &&
2281 ffs(pow2_ceil(size) >> (tiny_min_2pow + 1))
2282 == ffs(pow2_ceil(oldsize) >> (tiny_min_2pow + 1)))
2283 goto IN_PLACE;
2284 } else if (size <= small_max) {
2285 if (oldsize >= small_min && oldsize <= small_max &&
2286 (QUANTUM_CEILING(size) >> opt_quantum_2pow)
2287 == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
2288 goto IN_PLACE;
2289 } else {
2290 if (oldsize > small_max && pow2_ceil(size) == oldsize)
2291 goto IN_PLACE;
2292 }
2293
2294 /*
2295 * If we get here, then size and oldsize are different enough that we
2296 * need to use a different size class. In that case, fall back to
2297 * allocating new space and copying.
2298 */
2299 ret = arena_malloc(choose_arena(), size);
2300 if (ret == NULL)
2301 return (NULL);
2302
2303 if (size < oldsize)
2304 memcpy(ret, ptr, size);
2305 else
2306 memcpy(ret, ptr, oldsize);
2307 idalloc(ptr);
2308 return (ret);
2309IN_PLACE:
2310 if (opt_junk && size < oldsize)
2311 memset(&((char *)ptr)[size], 0x5a, oldsize - size);
2312 else if (opt_zero && size > oldsize)
2313 memset(&((char *)ptr)[size], 0, size - oldsize);
2314 return (ptr);
2315}
2316
2317static void
2318arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
2319{
2320 unsigned pageind;
2321 arena_chunk_map_t mapelm;
2322 size_t size;
2323
2324 assert(arena != NULL);
2325 assert(arena->magic == ARENA_MAGIC);
2326 assert(chunk->arena == arena);
2327 assert(ptr != NULL);
2328 assert(CHUNK_ADDR2BASE(ptr) != ptr);
2329
2330 pageind = (((uintptr_t)ptr - (uintptr_t)chunk) >> pagesize_2pow);
2331 mapelm = chunk->map[pageind];
2332 assert(mapelm.free == false);
2333 if (mapelm.large == false) {
2334 arena_run_t *run;
2335 arena_bin_t *bin;
2336
2337 /* Small allocation. */
2338
2339 pageind -= mapelm.pos;
2340
2341 run = (arena_run_t *)&((char *)chunk)[pageind << pagesize_2pow];
2342 assert(run->magic == ARENA_RUN_MAGIC);
2343 bin = run->bin;
2344 size = bin->reg_size;
2345
2346 if (opt_junk)
2347 memset(ptr, 0x5a, size);
2348
2349 malloc_mutex_lock(&arena->mtx);
2350 arena_run_reg_dalloc(run, bin, ptr, size);
2351 run->nfree++;
2352 if (run->nfree > run->free_max) {
2353 /* Demote run to lower fullness quartile. */
2354 arena_bin_run_demote(arena, bin, run);
2355 }
2356 } else {
2357 /* Medium allocation. */
2358
2359 size = mapelm.npages << pagesize_2pow;
2360 assert((((uintptr_t)ptr) & (size - 1)) == 0);
2361
2362 if (opt_junk)
2363 memset(ptr, 0x5a, size);
2364
2365 malloc_mutex_lock(&arena->mtx);
2366 arena_run_dalloc(arena, (arena_run_t *)ptr, size);
2367 }
2368
2369#ifdef MALLOC_STATS
2370 arena->stats.allocated -= size;
2371#endif
2372
2373 malloc_mutex_unlock(&arena->mtx);
2374}
2375
2376static bool
2377arena_new(arena_t *arena)
2378{
2379 unsigned i;
2380 arena_bin_t *bin;
2381 size_t pow2_size, run_size;
2382
2383 malloc_mutex_init(&arena->mtx);
2384
2385#ifdef MALLOC_STATS
2386 memset(&arena->stats, 0, sizeof(arena_stats_t));
2387#endif
2388
2389 /* Initialize chunks. */
2390 RB_INIT(&arena->chunks);
2391
2392 /* Initialize bins. */
2393
2394 /* (2^n)-spaced tiny bins. */
2395 for (i = 0; i < ntbins; i++) {
2396 bin = &arena->bins[i];
2397 bin->runcur = NULL;
2398 qr_new((arena_run_t *)&bin->runs0, link);
2399 qr_new((arena_run_t *)&bin->runs25, link);
2400 qr_new((arena_run_t *)&bin->runs50, link);
2401 qr_new((arena_run_t *)&bin->runs75, link);
2402
2403 bin->reg_size = (1 << (tiny_min_2pow + i));
2404
2405 /*
2406 * Calculate how large of a run to allocate. Make sure that at
2407 * least RUN_MIN_REGS regions fit in the run.
2408 */
2409 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2410 if (run_size < pagesize)
2411 run_size = pagesize;
2412 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2413 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2414 if (run_size > arena_maxclass)
2415 run_size = arena_maxclass;
2416 bin->run_size = run_size;
2417
2418 assert(run_size >= sizeof(arena_run_t));
2419 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2420 if (bin->nregs > (REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3))) {
2421 /* Take care not to overflow regs_mask. */
2422 bin->nregs = REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3);
2423 }
2424 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2425
2426#ifdef MALLOC_STATS
2427 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2428#endif
2429 }
2430
2431 /* Quantum-spaced bins. */
2432 for (; i < ntbins + nqbins; i++) {
2433 bin = &arena->bins[i];
2434 bin->runcur = NULL;
2435 qr_new((arena_run_t *)&bin->runs0, link);
2436 qr_new((arena_run_t *)&bin->runs25, link);
2437 qr_new((arena_run_t *)&bin->runs50, link);
2438 qr_new((arena_run_t *)&bin->runs75, link);
2439
2440 bin->reg_size = quantum * (i - ntbins + 1);
2441
2442 /*
2443 * Calculate how large of a run to allocate. Make sure that at
2444 * least RUN_MIN_REGS regions fit in the run.
2445 */
2446 pow2_size = pow2_ceil(quantum * (i - ntbins + 1));
2447 run_size = (pow2_size << RUN_MIN_REGS_2POW);
2448 if (run_size < pagesize)
2449 run_size = pagesize;
2450 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2451 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2452 if (run_size > arena_maxclass)
2453 run_size = arena_maxclass;
2454 bin->run_size = run_size;
2455
2456 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2457 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2458 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2459
2460#ifdef MALLOC_STATS
2461 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2462#endif
2463 }
2464
2465 /* (2^n)-spaced sub-page bins. */
2466 for (; i < ntbins + nqbins + nsbins; i++) {
2467 bin = &arena->bins[i];
2468 bin->runcur = NULL;
2469 qr_new((arena_run_t *)&bin->runs0, link);
2470 qr_new((arena_run_t *)&bin->runs25, link);
2471 qr_new((arena_run_t *)&bin->runs50, link);
2472 qr_new((arena_run_t *)&bin->runs75, link);
2473
2474 bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
2475
2476 /*
2477 * Calculate how large of a run to allocate. Make sure that at
2478 * least RUN_MIN_REGS regions fit in the run.
2479 */
2480 run_size = bin->reg_size << RUN_MIN_REGS_2POW;
2481 if (run_size < pagesize)
2482 run_size = pagesize;
2483 if (run_size > (pagesize << RUN_MAX_PAGES_2POW))
2484 run_size = (pagesize << RUN_MAX_PAGES_2POW);
2485 if (run_size > arena_maxclass)
2486 run_size = arena_maxclass;
2487 bin->run_size = run_size;
2488
2489 bin->nregs = (run_size - sizeof(arena_run_t)) / bin->reg_size;
2490 assert(bin->nregs <= REGS_MASK_NELMS << (SIZEOF_INT_2POW + 3));
2491 bin->reg0_offset = run_size - (bin->nregs * bin->reg_size);
2492
2493#ifdef MALLOC_STATS
2494 memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2495#endif
2496 }
2497
2498#ifdef MALLOC_DEBUG
2499 arena->magic = ARENA_MAGIC;
2500#endif
2501
2502 return (false);
2503}
2504
2505/* Create a new arena and insert it into the arenas array at index ind. */
2506static arena_t *
2507arenas_extend(unsigned ind)
2508{
2509 arena_t *ret;
2510
2511 /* Allocate enough space for trailing bins. */
2512 ret = (arena_t *)base_alloc(sizeof(arena_t)
2513 + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1)));
2514 if (ret != NULL && arena_new(ret) == false) {
2515 arenas[ind] = ret;
2516 return (ret);
2517 }
2518 /* Only reached if there is an OOM error. */
2519
2520 /*
2521 * OOM here is quite inconvenient to propagate, since dealing with it
2522 * would require a check for failure in the fast path. Instead, punt
2523 * by using arenas[0]. In practice, this is an extremely unlikely
2524 * failure.
2525 */
2526 malloc_printf("%s: (malloc) Error initializing arena\n",
2527 _getprogname());
2528 if (opt_abort)
2529 abort();
2530
2531 return (arenas[0]);
2532}
2533
2534/*
2535 * End arena.
2536 */
2537/******************************************************************************/
2538/*
2539 * Begin general internal functions.
2540 */
2541
2542static void *
2543huge_malloc(size_t size)
2544{
2545 void *ret;
2546 size_t csize;
2547 chunk_node_t *node;
2548
2549 /* Allocate one or more contiguous chunks for this request. */
2550
2551 csize = CHUNK_CEILING(size);
2552 if (csize == 0) {
2553 /* size is large enough to cause size_t wrap-around. */
2554 return (NULL);
2555 }
2556
2557 /* Allocate a chunk node with which to track the chunk. */
2558 node = base_chunk_node_alloc();
2559 if (node == NULL)
2560 return (NULL);
2561
2562 ret = chunk_alloc(csize);
2563 if (ret == NULL) {
2564 base_chunk_node_dealloc(node);
2565 return (NULL);
2566 }
2567
2568 /* Insert node into huge. */
2569 node->chunk = ret;
2570 node->size = csize;
2571
2572 malloc_mutex_lock(&chunks_mtx);
2573 RB_INSERT(chunk_tree_s, &huge, node);
2574#ifdef MALLOC_STATS
2575 huge_nmalloc++;
2576 huge_allocated += csize;
2577#endif
2578 malloc_mutex_unlock(&chunks_mtx);
2579
2580 if (opt_junk && ret != NULL)
2581 memset(ret, 0xa5, csize);
2582 else if (opt_zero && ret != NULL)
2583 memset(ret, 0, csize);
2584
2585 return (ret);
2586}
2587
2588static void *
2589huge_ralloc(void *ptr, size_t size, size_t oldsize)
2590{
2591 void *ret;
2592
2593 /* Avoid moving the allocation if the size class would not change. */
2594 if (oldsize > arena_maxclass &&
2595 CHUNK_CEILING(size) == CHUNK_CEILING(oldsize))
2596 return (ptr);
2597
2598 /*
2599 * If we get here, then size and oldsize are different enough that we
2600 * need to use a different size class. In that case, fall back to
2601 * allocating new space and copying.
2602 */
2603 ret = huge_malloc(size);
2604 if (ret == NULL)
2605 return (NULL);
2606
2607 if (CHUNK_ADDR2BASE(ptr) == ptr) {
2608 /* The old allocation is a chunk. */
2609 if (size < oldsize)
2610 memcpy(ret, ptr, size);
2611 else
2612 memcpy(ret, ptr, oldsize);
2613 } else {
2614 /* The old allocation is a region. */
2615 assert(oldsize < size);
2616 memcpy(ret, ptr, oldsize);
2617 }
2618 idalloc(ptr);
2619 return (ret);
2620}
2621
2622static void
2623huge_dalloc(void *ptr)
2624{
2625 chunk_node_t key;
2626 chunk_node_t *node;
2627
2628 malloc_mutex_lock(&chunks_mtx);
2629
2630 /* Extract from tree of huge allocations. */
2631 key.chunk = ptr;
2632 node = RB_FIND(chunk_tree_s, &huge, &key);
2633 assert(node != NULL);
2634 assert(node->chunk == ptr);
2635 RB_REMOVE(chunk_tree_s, &huge, node);
2636
2637#ifdef MALLOC_STATS
2638 /* Update counters. */
2639 huge_ndalloc++;
2640 huge_allocated -= node->size;
2641#endif
2642
2643 malloc_mutex_unlock(&chunks_mtx);
2644
2645 /* Unmap chunk. */
2646#ifdef USE_BRK
2647 if (opt_junk)
2648 memset(node->chunk, 0x5a, node->size);
2649#endif
2650 chunk_dealloc(node->chunk, node->size);
2651
2652 base_chunk_node_dealloc(node);
2653}
2654
2655static void *
2656imalloc(size_t size)
2657{
2658 void *ret;
2659
2660 assert(size != 0);
2661
2662 if (size <= arena_maxclass)
2663 ret = arena_malloc(choose_arena(), size);
2664 else
2665 ret = huge_malloc(size);
2666
2667 return (ret);
2668}
2669
2670static void *
2671ipalloc(size_t alignment, size_t size)
2672{
2673 void *ret;
2674 size_t alloc_size;
2675
2676 /*
2677 * Take advantage of the fact that for each size class, every object is
2678 * aligned at the smallest power of two that is non-zero in the base
2679 * two representation of the size. For example:
2680 *
2681 * Size | Base 2 | Minimum alignment
2682 * -----+----------+------------------
2683 * 96 | 1100000 | 32
2684 * 144 | 10100000 | 32
2685 * 192 | 11000000 | 64
2686 *
2687 * Depending on runtime settings, it is possible that arena_malloc()
2688 * will further round up to a power of two, but that never causes
2689 * correctness issues.
2690 */
2691 alloc_size = (size + (alignment - 1)) & (-alignment);
2692 if (alloc_size < size) {
2693 /* size_t overflow. */
2694 return (NULL);
2695 }
2696
2697 if (alloc_size <= arena_maxclass)
2698 ret = arena_malloc(choose_arena(), alloc_size);
2699 else {
2700 if (alignment <= chunk_size)
2701 ret = huge_malloc(size);
2702 else {
2703 size_t chunksize, offset;
2704 chunk_node_t *node;
2705
2706 /*
2707 * This allocation requires alignment that is even
2708 * larger than chunk alignment. This means that
2709 * huge_malloc() isn't good enough.
2710 *
2711 * Allocate almost twice as many chunks as are demanded
2712 * by the size or alignment, in order to assure the
2713 * alignment can be achieved, then unmap leading and
2714 * trailing chunks.
2715 */
2716
2717 chunksize = CHUNK_CEILING(size);
2718
2719 if (size >= alignment)
2720 alloc_size = chunksize + alignment - chunk_size;
2721 else
2722 alloc_size = (alignment << 1) - chunk_size;
2723
2724 /*
2725 * Allocate a chunk node with which to track the chunk.
2726 */
2727 node = base_chunk_node_alloc();
2728 if (node == NULL)
2729 return (NULL);
2730
2731 ret = chunk_alloc(alloc_size);
2732 if (ret == NULL) {
2733 base_chunk_node_dealloc(node);
2734 return (NULL);
2735 }
2736
2737 offset = (uintptr_t)ret & (alignment - 1);
2738 assert(offset % chunk_size == 0);
2739 assert(offset < alloc_size);
2740 if (offset == 0) {
2741 /* Trim trailing space. */
2742 chunk_dealloc((void *)((uintptr_t)ret
2743 + chunksize), alloc_size - chunksize);
2744 } else {
2745 size_t trailsize;
2746
2747 /* Trim leading space. */
2748 chunk_dealloc(ret, alignment - offset);
2749
2750 ret = (void *)((uintptr_t)ret + (alignment
2751 - offset));
2752
2753 trailsize = alloc_size - (alignment - offset)
2754 - chunksize;
2755 if (trailsize != 0) {
2756 /* Trim trailing space. */
2757 assert(trailsize < alloc_size);
2758 chunk_dealloc((void *)((uintptr_t)ret
2759 + chunksize), trailsize);
2760 }
2761 }
2762
2763 /* Insert node into huge. */
2764 node->chunk = ret;
2765 node->size = chunksize;
2766
2767 malloc_mutex_lock(&chunks_mtx);
2768 RB_INSERT(chunk_tree_s, &huge, node);
2769#ifdef MALLOC_STATS
2770 huge_allocated += size;
2771#endif
2772 malloc_mutex_unlock(&chunks_mtx);
2773
2774 if (opt_junk)
2775 memset(ret, 0xa5, chunksize);
2776 else if (opt_zero)
2777 memset(ret, 0, chunksize);
2778 }
2779 }
2780
2781 assert(((uintptr_t)ret & (alignment - 1)) == 0);
2782 return (ret);
2783}
2784
2785static void *
2786icalloc(size_t size)
2787{
2788 void *ret;
2789
2790 if (size <= arena_maxclass) {
2791 ret = arena_malloc(choose_arena(), size);
2792 if (ret == NULL)
2793 return (NULL);
2794 memset(ret, 0, size);
2795 } else {
2796 /*
2797 * The virtual memory system provides zero-filled pages, so
2798 * there is no need to do so manually, unless opt_junk is
2799 * enabled, in which case huge_malloc() fills huge allocations
2800 * with junk.
2801 */
2802 ret = huge_malloc(size);
2803 if (ret == NULL)
2804 return (NULL);
2805
2806 if (opt_junk)
2807 memset(ret, 0, size);
2808#ifdef USE_BRK
2809 else if ((uintptr_t)ret >= (uintptr_t)brk_base
2810 && (uintptr_t)ret < (uintptr_t)brk_max) {
2811 /*
2812 * This may be a re-used brk chunk. Therefore, zero
2813 * the memory.
2814 */
2815 memset(ret, 0, size);
2816 }
2817#endif
2818 }
2819
2820 return (ret);
2821}
2822
2823static size_t
2824isalloc(const void *ptr)
2825{
2826 size_t ret;
2827 arena_chunk_t *chunk;
2828
2829 assert(ptr != NULL);
2830
2831 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2832 if (chunk != ptr) {
2833 /* Region. */
2834 assert(chunk->arena->magic == ARENA_MAGIC);
2835
2836 ret = arena_salloc(ptr);
2837 } else {
2838 chunk_node_t *node, key;
2839
2840 /* Chunk (huge allocation). */
2841
2842 malloc_mutex_lock(&chunks_mtx);
2843
2844 /* Extract from tree of huge allocations. */
2845 key.chunk = (void *)ptr;
2846 node = RB_FIND(chunk_tree_s, &huge, &key);
2847 assert(node != NULL);
2848
2849 ret = node->size;
2850
2851 malloc_mutex_unlock(&chunks_mtx);
2852 }
2853
2854 return (ret);
2855}
2856
2857static void *
2858iralloc(void *ptr, size_t size)
2859{
2860 void *ret;
2861 size_t oldsize;
2862
2863 assert(ptr != NULL);
2864 assert(size != 0);
2865
2866 oldsize = isalloc(ptr);
2867
2868 if (size <= arena_maxclass)
2869 ret = arena_ralloc(ptr, size, oldsize);
2870 else
2871 ret = huge_ralloc(ptr, size, oldsize);
2872
2873 return (ret);
2874}
2875
2876static void
2877idalloc(void *ptr)
2878{
2879 arena_chunk_t *chunk;
2880
2881 assert(ptr != NULL);
2882
2883 chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
2884 if (chunk != ptr) {
2885 /* Region. */
2886#ifdef MALLOC_STATS
2887 malloc_mutex_lock(&chunk->arena->mtx);
2888 chunk->arena->stats.ndalloc++;
2889 malloc_mutex_unlock(&chunk->arena->mtx);
2890#endif
2891 arena_dalloc(chunk->arena, chunk, ptr);
2892 } else
2893 huge_dalloc(ptr);
2894}
2895
2896static void
2897malloc_print_stats(void)
2898{
2899
2900 if (opt_print_stats) {
2901 malloc_printf("___ Begin malloc statistics ___\n");
2902 malloc_printf("Number of CPUs: %u\n", ncpus);
2903 malloc_printf("Number of arenas: %u\n", narenas);
2904 malloc_printf("Chunk size: %zu (2^%zu)\n", chunk_size,
2905 opt_chunk_2pow);
2906 malloc_printf("Quantum size: %zu (2^%zu)\n", quantum,
2907 opt_quantum_2pow);
2908 malloc_printf("Max small size: %zu\n", small_max);
2909 malloc_printf("Pointer size: %u\n", sizeof(void *));
2910 malloc_printf("Assertions %s\n",
2911#ifdef NDEBUG
2912 "disabled"
2913#else
2914 "enabled"
2915#endif
2916 );
2917
2918#ifdef MALLOC_STATS
2919
2920 {
2921 size_t allocated, total;
2922 unsigned i;
2923 arena_t *arena;
2924
2925 /* Calculate and print allocated/total stats. */
2926
2927 /* arenas. */
2928 for (i = 0, allocated = 0; i < narenas; i++) {
2929 if (arenas[i] != NULL) {
2930 malloc_mutex_lock(&arenas[i]->mtx);
2931 allocated += arenas[i]->stats.allocated;
2932 malloc_mutex_unlock(&arenas[i]->mtx);
2933 }
2934 }
2935
2936 /* huge. */
2937 malloc_mutex_lock(&chunks_mtx);
2938 allocated += huge_allocated;
2939 total = stats_chunks.curchunks * chunk_size;
2940 malloc_mutex_unlock(&chunks_mtx);
2941
2942 malloc_printf("Allocated: %zu, space used: %zu\n",
2943 allocated, total);
2944
2945 /* Print chunk stats. */
2946 {
2947 chunk_stats_t chunks_stats;
2948
2949 malloc_mutex_lock(&chunks_mtx);
2950 chunks_stats = stats_chunks;
2951 malloc_mutex_unlock(&chunks_mtx);
2952
2953 malloc_printf("\nchunks:\n");
2954 malloc_printf(" %13s%13s%13s\n", "nchunks",
2955 "highchunks", "curchunks");
2956 malloc_printf(" %13llu%13lu%13lu\n",
2957 chunks_stats.nchunks,
2958 chunks_stats.highchunks,
2959 chunks_stats.curchunks);
2960 }
2961
2962 /* Print chunk stats. */
2963 malloc_printf("\nhuge:\n");
2964 malloc_printf("%12s %12s %12s\n",
2965 "nmalloc", "ndalloc", "allocated");
2966 malloc_printf("%12llu %12llu %12zu\n",
2967 huge_nmalloc, huge_ndalloc, huge_allocated);
2968
2969 /* Print stats for each arena. */
2970 for (i = 0; i < narenas; i++) {
2971 arena = arenas[i];
2972 if (arena != NULL) {
2973 malloc_printf(
2974 "\narenas[%u] statistics:\n", i);
2975 malloc_mutex_lock(&arena->mtx);
2976 stats_print(arena);
2977 malloc_mutex_unlock(&arena->mtx);
2978 }
2979 }
2980 }
2981#endif /* #ifdef MALLOC_STATS */
2982 malloc_printf("--- End malloc statistics ---\n");
2983 }
2984}
2985
2986/*
2987 * FreeBSD's pthreads implementation calls malloc(3), so the malloc
2988 * implementation has to take pains to avoid infinite recursion during
2989 * initialization.
2990 */
2991static inline bool
2992malloc_init(void)
2993{
2994
2995 if (malloc_initialized == false)
2996 return (malloc_init_hard());
2997
2998 return (false);
2999}
3000
3001static bool
3002malloc_init_hard(void)
3003{
3004 unsigned i, j;
3005 int linklen;
3006 char buf[PATH_MAX + 1];
3007 const char *opts;
3008
3009 malloc_mutex_lock(&init_lock);
3010 if (malloc_initialized) {
3011 /*
3012 * Another thread initialized the allocator before this one
3013 * acquired init_lock.
3014 */
3015 malloc_mutex_unlock(&init_lock);
3016 return (false);
3017 }
3018
3019 /* Get number of CPUs. */
3020 {
3021 int mib[2];
3022 size_t len;
3023
3024 mib[0] = CTL_HW;
3025 mib[1] = HW_NCPU;
3026 len = sizeof(ncpus);
3027 if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
3028 /* Error. */
3029 ncpus = 1;
3030 }
3031 }
3032
3033 /* Get page size. */
3034 {
3035 long result;
3036
3037 result = sysconf(_SC_PAGESIZE);
3038 assert(result != -1);
3039 pagesize = (unsigned) result;
3040
3041 /*
3042 * We assume that pagesize is a power of 2 when calculating
3043 * pagesize_2pow.
3044 */
3045 assert(((result - 1) & result) == 0);
3046 pagesize_2pow = ffs(result) - 1;
3047 }
3048
3049 for (i = 0; i < 3; i++) {
3050 /* Get runtime configuration. */
3051 switch (i) {
3052 case 0:
3053 if ((linklen = readlink("/etc/malloc.conf", buf,
3054 sizeof(buf) - 1)) != -1) {
3055 /*
3056 * Use the contents of the "/etc/malloc.conf"
3057 * symbolic link's name.
3058 */
3059 buf[linklen] = '\0';
3060 opts = buf;
3061 } else {
3062 /* No configuration specified. */
3063 buf[0] = '\0';
3064 opts = buf;
3065 }
3066 break;
3067 case 1:
3068 if (issetugid() == 0 && (opts =
3069 getenv("MALLOC_OPTIONS")) != NULL) {
3070 /*
3071 * Do nothing; opts is already initialized to
3072 * the value of the MALLOC_OPTIONS environment
3073 * variable.
3074 */
3075 } else {
3076 /* No configuration specified. */
3077 buf[0] = '\0';
3078 opts = buf;
3079 }
3080 break;
3081 case 2:
3082 if (_malloc_options != NULL) {
3083 /*
3084 * Use options that were compiled into the program.
3085 */
3086 opts = _malloc_options;
3087 } else {
3088 /* No configuration specified. */
3089 buf[0] = '\0';
3090 opts = buf;
3091 }
3092 break;
3093 default:
3094 /* NOTREACHED */
3095 assert(false);
3096 }
3097
3098 for (j = 0; opts[j] != '\0'; j++) {
3099 switch (opts[j]) {
3100 case 'a':
3101 opt_abort = false;
3102 break;
3103 case 'A':
3104 opt_abort = true;
3105 break;
3106 case 'h':
3107 opt_hint = false;
3108 break;
3109 case 'H':
3110 opt_hint = true;
3111 break;
3112 case 'j':
3113 opt_junk = false;
3114 break;
3115 case 'J':
3116 opt_junk = true;
3117 break;
3118 case 'k':
3119 /*
3120 * Run fullness quartile limits don't have
3121 * enough resolution if there are too few
3122 * regions for the largest bin size classes.
3123 */
3124 if (opt_chunk_2pow > pagesize_2pow + 4)
3125 opt_chunk_2pow--;
3126 break;
3127 case 'K':
3128 if (opt_chunk_2pow < CHUNK_2POW_MAX)
3129 opt_chunk_2pow++;
3130 break;
3131 case 'n':
3132 opt_narenas_lshift--;
3133 break;
3134 case 'N':
3135 opt_narenas_lshift++;
3136 break;
3137 case 'p':
3138 opt_print_stats = false;
3139 break;
3140 case 'P':
3141 opt_print_stats = true;
3142 break;
3143 case 'q':
3144 if (opt_quantum_2pow > QUANTUM_2POW_MIN)
3145 opt_quantum_2pow--;
3146 break;
3147 case 'Q':
3148 if (opt_quantum_2pow < pagesize_2pow - 1)
3149 opt_quantum_2pow++;
3150 break;
3151 case 's':
3152 if (opt_small_max_2pow > QUANTUM_2POW_MIN)
3153 opt_small_max_2pow--;
3154 break;
3155 case 'S':
3156 if (opt_small_max_2pow < pagesize_2pow - 1)
3157 opt_small_max_2pow++;
3158 break;
3159 case 'u':
3160 opt_utrace = false;
3161 break;
3162 case 'U':
3163 opt_utrace = true;
3164 break;
3165 case 'v':
3166 opt_sysv = false;
3167 break;
3168 case 'V':
3169 opt_sysv = true;
3170 break;
3171 case 'x':
3172 opt_xmalloc = false;
3173 break;
3174 case 'X':
3175 opt_xmalloc = true;
3176 break;
3177 case 'z':
3178 opt_zero = false;
3179 break;
3180 case 'Z':
3181 opt_zero = true;
3182 break;
3183 default:
3184 malloc_printf("%s: (malloc) Unsupported"
3185 " character in malloc options: '%c'\n",
3186 _getprogname(), opts[j]);
3187 }
3188 }
3189 }
3190
3191 /* Take care to call atexit() only once. */
3192 if (opt_print_stats) {
3193 /* Print statistics at exit. */
3194 atexit(malloc_print_stats);
3195 }
3196
3197 /* Set variables according to the value of opt_small_max_2pow. */
3198 if (opt_small_max_2pow < opt_quantum_2pow)
3199 opt_small_max_2pow = opt_quantum_2pow;
3200 small_max = (1 << opt_small_max_2pow);
3201
3202 /* Set bin-related variables. */
3203 bin_maxclass = (pagesize >> 1);
3204 if (pagesize_2pow > RUN_MIN_REGS_2POW + 1)
3205 tiny_min_2pow = pagesize_2pow - (RUN_MIN_REGS_2POW + 1);
3206 else
3207 tiny_min_2pow = 1;
3208 assert(opt_quantum_2pow >= tiny_min_2pow);
3209 ntbins = opt_quantum_2pow - tiny_min_2pow;
3210 assert(ntbins <= opt_quantum_2pow);
3211 nqbins = (small_max >> opt_quantum_2pow);
3212 nsbins = pagesize_2pow - opt_small_max_2pow - 1;
3213
3214 /* Set variables according to the value of opt_quantum_2pow. */
3215 quantum = (1 << opt_quantum_2pow);
3216 quantum_mask = quantum - 1;
3217 if (ntbins > 0)
3218 small_min = (quantum >> 1) + 1;
3219 else
3220 small_min = 1;
3221 assert(small_min <= quantum);
3222
3223 /* Set variables according to the value of opt_chunk_2pow. */
3224 chunk_size = (1 << opt_chunk_2pow);
3225 chunk_size_mask = chunk_size - 1;
3226 arena_chunk_maplen = (1 << (opt_chunk_2pow - pagesize_2pow));
3227 arena_maxclass = (chunk_size >> 1);
3228
3229 UTRACE(0, 0, 0);
3230
3231#ifdef MALLOC_STATS
3232 memset(&stats_chunks, 0, sizeof(chunk_stats_t));
3233#endif
3234
3235 /* Various sanity checks that regard configuration. */
3236 assert(quantum >= sizeof(void *));
3237 assert(quantum <= pagesize);
3238 assert(chunk_size >= pagesize);
3239 assert(quantum * 4 <= chunk_size);
3240
3241 /* Initialize chunks data. */
3242 malloc_mutex_init(&chunks_mtx);
3243 RB_INIT(&huge);
3244#ifdef USE_BRK
3245 brk_base = sbrk(0);
3246 brk_prev = brk_base;
3247 brk_max = brk_base;
3248#endif
3249#ifdef MALLOC_STATS
3250 huge_nmalloc = 0;
3251 huge_ndalloc = 0;
3252 huge_allocated = 0;
3253#endif
3254 RB_INIT(&old_chunks);
3255
3256 /* Initialize base allocation data structures. */
3257#ifdef MALLOC_STATS
3258 base_total = 0;
3259#endif
3260#ifdef USE_BRK
3261 /*
3262 * Do special brk allocation here, since the base chunk doesn't really
3263 * need to be chunk-aligned.
3264 */
3265 {
3266 void *brk_cur;
3267 intptr_t incr;
3268
3269 do {
3270 /* Get the current end of brk. */
3271 brk_cur = sbrk(0);
3272
3273 /*
3274 * Calculate how much padding is necessary to
3275 * chunk-align the end of brk. Don't worry about
3276 * brk_cur not being chunk-aligned though.
3277 */
3278 incr = (intptr_t)chunk_size
3279 - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
3280
3281 brk_prev = sbrk(incr);
3282 if (brk_prev == brk_cur) {
3283 /* Success. */
3284 break;
3285 }
3286 } while (brk_prev != (void *)-1);
3287
3288 base_chunk = brk_cur;
3289 base_next_addr = base_chunk;
3290 base_past_addr = (void *)((uintptr_t)base_chunk + incr);
3291#ifdef MALLOC_STATS
3292 base_total += incr;
3293 stats_chunks.nchunks = 1;
3294 stats_chunks.curchunks = 1;
3295 stats_chunks.highchunks = 1;
3296#endif
3297 }
3298#else
3299 /*
3300 * The first base chunk will be allocated when needed by base_alloc().
3301 */
3302 base_chunk = NULL;
3303 base_next_addr = NULL;
3304 base_past_addr = NULL;
3305#endif
3306 base_chunk_nodes = NULL;
3307 malloc_mutex_init(&base_mtx);
3308
3309 if (ncpus > 1) {
3310 /*
3311 * For SMP systems, create four times as many arenas as there
3312 * are CPUs by default.
3313 */
3314 opt_narenas_lshift += 2;
3315 }
3316
3317 /* Determine how many arenas to use. */
3318 narenas = ncpus;
3319 if (opt_narenas_lshift > 0) {
3320 if ((narenas << opt_narenas_lshift) > narenas)
3321 narenas <<= opt_narenas_lshift;
3322 /*
3323 * Make sure not to exceed the limits of what base_malloc()
3324 * can handle.
3325 */
3326 if (narenas * sizeof(arena_t *) > chunk_size)
3327 narenas = chunk_size / sizeof(arena_t *);
3328 } else if (opt_narenas_lshift < 0) {
3329 if ((narenas << opt_narenas_lshift) < narenas)
3330 narenas <<= opt_narenas_lshift;
3331 /* Make sure there is at least one arena. */
3332 if (narenas == 0)
3333 narenas = 1;
3334 }
3335
3336#ifdef NO_TLS
3337 if (narenas > 1) {
3338 static const unsigned primes[] = {1, 3, 5, 7, 11, 13, 17, 19,
3339 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
3340 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
3341 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
3342 223, 227, 229, 233, 239, 241, 251, 257, 263};
3343 unsigned i, nprimes, parenas;
3344
3345 /*
3346 * Pick a prime number of hash arenas that is more than narenas
3347 * so that direct hashing of pthread_self() pointers tends to
3348 * spread allocations evenly among the arenas.
3349 */
3350 assert((narenas & 1) == 0); /* narenas must be even. */
3351 nprimes = (sizeof(primes) >> SIZEOF_INT_2POW);
3352 parenas = primes[nprimes - 1]; /* In case not enough primes. */
3353 for (i = 1; i < nprimes; i++) {
3354 if (primes[i] > narenas) {
3355 parenas = primes[i];
3356 break;
3357 }
3358 }
3359 narenas = parenas;
3360 }
3361#endif
3362
3363#ifndef NO_TLS
3364 next_arena = 0;
3365#endif
3366
3367 /* Allocate and initialize arenas. */
3368 arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
3369 if (arenas == NULL) {
3370 malloc_mutex_unlock(&init_lock);
3371 return (true);
3372 }
3373 /*
3374 * Zero the array. In practice, this should always be pre-zeroed,
3375 * since it was just mmap()ed, but let's be sure.
3376 */
3377 memset(arenas, 0, sizeof(arena_t *) * narenas);
3378
3379 /*
3380 * Initialize one arena here. The rest are lazily created in
3381 * arena_choose_hard().
3382 */
3383 arenas_extend(0);
3384 if (arenas[0] == NULL) {
3385 malloc_mutex_unlock(&init_lock);
3386 return (true);
3387 }
3388
3389 malloc_mutex_init(&arenas_mtx);
3390
3391 malloc_initialized = true;
3392 malloc_mutex_unlock(&init_lock);
3393 return (false);
3394}
3395
3396/*
3397 * End general internal functions.
3398 */
3399/******************************************************************************/
3400/*
3401 * Begin malloc(3)-compatible functions.
3402 */
3403
3404void *
3405malloc(size_t size)
3406{
3407 void *ret;
3408
3409 if (malloc_init()) {
3410 ret = NULL;
3411 goto RETURN;
3412 }
3413
3414 if (size == 0) {
3415 if (opt_sysv == false)
3416 size = 1;
3417 else {
3418 ret = NULL;
3419 goto RETURN;
3420 }
3421 }
3422
3423 ret = imalloc(size);
3424
3425RETURN:
3426 if (ret == NULL) {
3427 if (opt_xmalloc) {
3428 malloc_printf("%s: (malloc) Error in malloc(%zu):"
3429 " out of memory\n", _getprogname(), size);
3430 abort();
3431 }
3432 errno = ENOMEM;
3433 }
3434
3435 UTRACE(0, size, ret);
3436 return (ret);
3437}
3438
3439int
3440posix_memalign(void **memptr, size_t alignment, size_t size)
3441{
3442 int ret;
3443 void *result;
3444
3445 if (malloc_init())
3446 result = NULL;
3447 else {
3448 /* Make sure that alignment is a large enough power of 2. */
3449 if (((alignment - 1) & alignment) != 0
3450 || alignment < sizeof(void *)) {
3451 if (opt_xmalloc) {
3452 malloc_printf("%s: (malloc) Error in"
3453 " posix_memalign(%zu, %zu):"
3454 " invalid alignment\n",
3455 _getprogname(), alignment, size);
3456 abort();
3457 }
3458 result = NULL;
3459 ret = EINVAL;
3460 goto RETURN;
3461 }
3462
3463 result = ipalloc(alignment, size);
3464 }
3465
3466 if (result == NULL) {
3467 if (opt_xmalloc) {
3468 malloc_printf("%s: (malloc) Error in"
3469 " posix_memalign(%zu, %zu): out of memory\n",
3470 _getprogname(), alignment, size);
3471 abort();
3472 }
3473 ret = ENOMEM;
3474 goto RETURN;
3475 }
3476
3477 *memptr = result;
3478 ret = 0;
3479
3480RETURN:
3481 UTRACE(0, size, result);
3482 return (ret);
3483}
3484
3485void *
3486calloc(size_t num, size_t size)
3487{
3488 void *ret;
3489 size_t num_size;
3490
3491 if (malloc_init()) {
3492 ret = NULL;
3493 goto RETURN;
3494 }
3495
3496 num_size = num * size;
3497 if (num_size == 0) {
3498 if (opt_sysv == false)
3499 num_size = 1;
3500 else {
3501 ret = NULL;
3502 goto RETURN;
3503 }
3504 /*
3505 * Try to avoid division here. We know that it isn't possible to
3506 * overflow during multiplication if neither operand uses any of the
3507 * most significant half of the bits in a size_t.
3508 */
3509 } else if (((num | size) & (SIZE_T_MAX << (sizeof(size_t) << 2)))
3510 && (num_size / size != num)) {
3511 /* size_t overflow. */
3512 ret = NULL;
3513 goto RETURN;
3514 }
3515
3516 ret = icalloc(num_size);
3517
3518RETURN:
3519 if (ret == NULL) {
3520 if (opt_xmalloc) {
3521 malloc_printf("%s: (malloc) Error in"
3522 " calloc(%zu, %zu): out of memory\n",
3523 _getprogname(), num, size);
3524 abort();
3525 }
3526 errno = ENOMEM;
3527 }
3528
3529 UTRACE(0, num_size, ret);
3530 return (ret);
3531}
3532
3533void *
3534realloc(void *ptr, size_t size)
3535{
3536 void *ret;
3537
3538 if (size == 0) {
3539 if (opt_sysv == false)
3540 size = 1;
3541 else {
3542 if (ptr != NULL)
3543 idalloc(ptr);
3544 ret = NULL;
3545 goto RETURN;
3546 }
3547 }
3548
3549 if (ptr != NULL) {
3550 assert(malloc_initialized);
3551
3552 ret = iralloc(ptr, size);
3553
3554 if (ret == NULL) {
3555 if (opt_xmalloc) {
3556 malloc_printf("%s: (malloc) Error in"
3557 " realloc(%p, %zu): out of memory\n",
3558 _getprogname(), ptr, size);
3559 abort();
3560 }
3561 errno = ENOMEM;
3562 }
3563 } else {
3564 if (malloc_init())
3565 ret = NULL;
3566 else
3567 ret = imalloc(size);
3568
3569 if (ret == NULL) {
3570 if (opt_xmalloc) {
3571 malloc_printf("%s: (malloc) Error in"
3572 " realloc(%p, %zu): out of memory\n",
3573 _getprogname(), ptr, size);
3574 abort();
3575 }
3576 errno = ENOMEM;
3577 }
3578 }
3579
3580RETURN:
3581 UTRACE(ptr, size, ret);
3582 return (ret);
3583}
3584
3585void
3586free(void *ptr)
3587{
3588
3589 UTRACE(ptr, 0, 0);
3590 if (ptr != NULL) {
3591 assert(malloc_initialized);
3592
3593 idalloc(ptr);
3594 }
3595}
3596
3597/*
3598 * End malloc(3)-compatible functions.
3599 */
3600/******************************************************************************/
3601/*
3602 * Begin non-standard functions.
3603 */
3604
3605size_t
3606malloc_usable_size(const void *ptr)
3607{
3608
3609 assert(ptr != NULL);
3610
3611 return (isalloc(ptr));
3612}
3613
3614/*
3615 * End non-standard functions.
3616 */
3617/******************************************************************************/
3618/*
3619 * Begin library-private functions, used by threading libraries for protection
3620 * of malloc during fork(). These functions are only called if the program is
3621 * running in threaded mode, so there is no need to check whether the program
3622 * is threaded here.
3623 */
3624
3625void
3626_malloc_prefork(void)
3627{
3628 unsigned i;
3629
3630 /* Acquire all mutexes in a safe order. */
3631
3632 malloc_mutex_lock(&arenas_mtx);
3633 for (i = 0; i < narenas; i++) {
3634 if (arenas[i] != NULL)
3635 malloc_mutex_lock(&arenas[i]->mtx);
3636 }
3637 malloc_mutex_unlock(&arenas_mtx);
3638
3639 malloc_mutex_lock(&base_mtx);
3640
3641 malloc_mutex_lock(&chunks_mtx);
3642}
3643
3644void
3645_malloc_postfork(void)
3646{
3647 unsigned i;
3648
3649 /* Release all mutexes, now that fork() has completed. */
3650
3651 malloc_mutex_unlock(&chunks_mtx);
3652
3653 malloc_mutex_unlock(&base_mtx);
3654
3655 malloc_mutex_lock(&arenas_mtx);
3656 for (i = 0; i < narenas; i++) {
3657 if (arenas[i] != NULL)
3658 malloc_mutex_unlock(&arenas[i]->mtx);
3659 }
3660 malloc_mutex_unlock(&arenas_mtx);
3661}
3662
3663/*
3664 * End library-private functions.
3665 */
3666/******************************************************************************/
|