Annotation of src/lib/libc/stdlib/jemalloc.c, Revision 1.19.12.1
1.19.12.1! matt 1: /* $NetBSD: jemalloc.c,v 1.19.4.1 2010/03/13 00:53:32 riz Exp $ */
1.2 ad 2:
1.1 ad 3: /*-
4: * Copyright (C) 2006,2007 Jason Evans <jasone@FreeBSD.org>.
5: * All rights reserved.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: * 1. Redistributions of source code must retain the above copyright
11: * notice(s), this list of conditions and the following disclaimer as
12: * the first lines of this file unmodified other than the possible
13: * addition of one or more copyright notices.
14: * 2. Redistributions in binary form must reproduce the above copyright
15: * notice(s), this list of conditions and the following disclaimer in
16: * the documentation and/or other materials provided with the
17: * distribution.
18: *
19: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
20: * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
23: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26: * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
28: * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
29: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30: *
31: *******************************************************************************
32: *
33: * This allocator implementation is designed to provide scalable performance
34: * for multi-threaded programs on multi-processor systems. The following
35: * features are included for this purpose:
36: *
37: * + Multiple arenas are used if there are multiple CPUs, which reduces lock
38: * contention and cache sloshing.
39: *
40: * + Cache line sharing between arenas is avoided for internal data
41: * structures.
42: *
43: * + Memory is managed in chunks and runs (chunks can be split into runs),
44: * rather than as individual pages. This provides a constant-time
45: * mechanism for associating allocations with particular arenas.
46: *
47: * Allocation requests are rounded up to the nearest size class, and no record
48: * of the original request size is maintained. Allocations are broken into
49: * categories according to size class. Assuming runtime defaults, 4 kB pages
50: * and a 16 byte quantum, the size classes in each category are as follows:
51: *
52: * |=====================================|
53: * | Category | Subcategory | Size |
54: * |=====================================|
55: * | Small | Tiny | 2 |
56: * | | | 4 |
57: * | | | 8 |
58: * | |----------------+---------|
59: * | | Quantum-spaced | 16 |
60: * | | | 32 |
61: * | | | 48 |
62: * | | | ... |
63: * | | | 480 |
64: * | | | 496 |
65: * | | | 512 |
66: * | |----------------+---------|
67: * | | Sub-page | 1 kB |
68: * | | | 2 kB |
69: * |=====================================|
70: * | Large | 4 kB |
71: * | | 8 kB |
72: * | | 12 kB |
73: * | | ... |
74: * | | 1012 kB |
75: * | | 1016 kB |
76: * | | 1020 kB |
77: * |=====================================|
78: * | Huge | 1 MB |
79: * | | 2 MB |
80: * | | 3 MB |
81: * | | ... |
82: * |=====================================|
83: *
84: * A different mechanism is used for each category:
85: *
86: * Small : Each size class is segregated into its own set of runs. Each run
87: * maintains a bitmap of which regions are free/allocated.
88: *
89: * Large : Each allocation is backed by a dedicated run. Metadata are stored
90: * in the associated arena chunk header maps.
91: *
92: * Huge : Each allocation is backed by a dedicated contiguous set of chunks.
93: * Metadata are stored in a separate red-black tree.
94: *
95: *******************************************************************************
96: */
97:
1.2 ad 98: /* LINTLIBRARY */
99:
100: #ifdef __NetBSD__
101: # define xutrace(a, b) utrace("malloc", (a), (b))
102: # define __DECONST(x, y) ((x)__UNCONST(y))
103: # define NO_TLS
104: #else
105: # define xutrace(a, b) utrace((a), (b))
106: #endif /* __NetBSD__ */
107:
1.1 ad 108: /*
109: * MALLOC_PRODUCTION disables assertions and statistics gathering. It also
110: * defaults the A and J runtime options to off. These settings are appropriate
111: * for production systems.
112: */
1.2 ad 113: #define MALLOC_PRODUCTION
1.1 ad 114:
115: #ifndef MALLOC_PRODUCTION
116: # define MALLOC_DEBUG
117: #endif
118:
119: #include <sys/cdefs.h>
1.2 ad 120: /* __FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.147 2007/06/15 22:00:16 jasone Exp $"); */
1.19.12.1! matt 121: __RCSID("$NetBSD: jemalloc.c,v 1.19.4.1 2010/03/13 00:53:32 riz Exp $");
1.1 ad 122:
1.2 ad 123: #ifdef __FreeBSD__
1.1 ad 124: #include "libc_private.h"
125: #ifdef MALLOC_DEBUG
126: # define _LOCK_DEBUG
127: #endif
128: #include "spinlock.h"
1.2 ad 129: #endif
1.1 ad 130: #include "namespace.h"
131: #include <sys/mman.h>
132: #include <sys/param.h>
1.2 ad 133: #ifdef __FreeBSD__
1.1 ad 134: #include <sys/stddef.h>
1.2 ad 135: #endif
1.1 ad 136: #include <sys/time.h>
137: #include <sys/types.h>
138: #include <sys/sysctl.h>
139: #include <sys/tree.h>
140: #include <sys/uio.h>
141: #include <sys/ktrace.h> /* Must come after several other sys/ includes. */
142:
1.2 ad 143: #ifdef __FreeBSD__
1.1 ad 144: #include <machine/atomic.h>
145: #include <machine/cpufunc.h>
1.2 ad 146: #endif
1.1 ad 147: #include <machine/vmparam.h>
148:
149: #include <errno.h>
150: #include <limits.h>
151: #include <pthread.h>
152: #include <sched.h>
153: #include <stdarg.h>
154: #include <stdbool.h>
155: #include <stdio.h>
156: #include <stdint.h>
157: #include <stdlib.h>
158: #include <string.h>
159: #include <strings.h>
160: #include <unistd.h>
161:
1.2 ad 162: #ifdef __NetBSD__
163: # include <reentrant.h>
1.16 christos 164: # include "extern.h"
165:
166: #define STRERROR_R(a, b, c) __strerror_r(a, b, c);
167: /*
168: * A non localized version of strerror, that avoids bringing in
169: * stdio and the locale code. All the malloc messages are in English
170: * so why bother?
171: */
172: static int
173: __strerror_r(int e, char *s, size_t l)
174: {
175: int rval;
176: size_t slen;
177:
178: if (e >= 0 && e < sys_nerr) {
179: slen = strlcpy(s, sys_errlist[e], l);
180: rval = 0;
181: } else {
182: slen = snprintf_ss(s, l, "Unknown error %u", e);
183: rval = EINVAL;
184: }
185: return slen >= l ? ERANGE : rval;
186: }
1.2 ad 187: #endif
188:
189: #ifdef __FreeBSD__
1.16 christos 190: #define STRERROR_R(a, b, c) strerror_r(a, b, c);
1.1 ad 191: #include "un-namespace.h"
1.2 ad 192: #endif
1.1 ad 193:
194: /* MALLOC_STATS enables statistics calculation. */
195: #ifndef MALLOC_PRODUCTION
196: # define MALLOC_STATS
197: #endif
198:
199: #ifdef MALLOC_DEBUG
200: # ifdef NDEBUG
201: # undef NDEBUG
202: # endif
203: #else
204: # ifndef NDEBUG
205: # define NDEBUG
206: # endif
207: #endif
208: #include <assert.h>
209:
210: #ifdef MALLOC_DEBUG
211: /* Disable inlining to make debugging easier. */
212: # define inline
213: #endif
214:
215: /* Size of stack-allocated buffer passed to strerror_r(). */
216: #define STRERROR_BUF 64
217:
218: /* Minimum alignment of allocations is 2^QUANTUM_2POW_MIN bytes. */
219: #ifdef __i386__
220: # define QUANTUM_2POW_MIN 4
221: # define SIZEOF_PTR_2POW 2
222: # define USE_BRK
223: #endif
224: #ifdef __ia64__
225: # define QUANTUM_2POW_MIN 4
226: # define SIZEOF_PTR_2POW 3
227: #endif
228: #ifdef __alpha__
229: # define QUANTUM_2POW_MIN 4
230: # define SIZEOF_PTR_2POW 3
231: # define NO_TLS
232: #endif
233: #ifdef __sparc64__
234: # define QUANTUM_2POW_MIN 4
235: # define SIZEOF_PTR_2POW 3
236: # define NO_TLS
237: #endif
238: #ifdef __amd64__
239: # define QUANTUM_2POW_MIN 4
240: # define SIZEOF_PTR_2POW 3
241: #endif
242: #ifdef __arm__
243: # define QUANTUM_2POW_MIN 3
244: # define SIZEOF_PTR_2POW 2
245: # define USE_BRK
246: # define NO_TLS
247: #endif
248: #ifdef __powerpc__
249: # define QUANTUM_2POW_MIN 4
250: # define SIZEOF_PTR_2POW 2
251: # define USE_BRK
252: #endif
1.3 he 253: #if defined(__sparc__) && !defined(__sparc64__)
1.2 ad 254: # define QUANTUM_2POW_MIN 4
255: # define SIZEOF_PTR_2POW 2
256: # define USE_BRK
257: #endif
258: #ifdef __vax__
259: # define QUANTUM_2POW_MIN 4
260: # define SIZEOF_PTR_2POW 2
261: # define USE_BRK
262: #endif
263: #ifdef __sh__
264: # define QUANTUM_2POW_MIN 4
265: # define SIZEOF_PTR_2POW 2
266: # define USE_BRK
267: #endif
268: #ifdef __m68k__
269: # define QUANTUM_2POW_MIN 4
270: # define SIZEOF_PTR_2POW 2
271: # define USE_BRK
272: #endif
273: #ifdef __mips__
274: # define QUANTUM_2POW_MIN 4
275: # define SIZEOF_PTR_2POW 2
276: # define USE_BRK
277: #endif
1.4 ad 278: #ifdef __hppa__
279: # define QUANTUM_2POW_MIN 4
280: # define SIZEOF_PTR_2POW 2
281: # define USE_BRK
282: #endif
1.1 ad 283:
284: #define SIZEOF_PTR (1 << SIZEOF_PTR_2POW)
285:
286: /* sizeof(int) == (1 << SIZEOF_INT_2POW). */
287: #ifndef SIZEOF_INT_2POW
288: # define SIZEOF_INT_2POW 2
289: #endif
290:
291: /* We can't use TLS in non-PIC programs, since TLS relies on loader magic. */
292: #if (!defined(PIC) && !defined(NO_TLS))
293: # define NO_TLS
294: #endif
295:
296: /*
297: * Size and alignment of memory chunks that are allocated by the OS's virtual
298: * memory system.
299: */
300: #define CHUNK_2POW_DEFAULT 20
301:
302: /*
303: * Maximum size of L1 cache line. This is used to avoid cache line aliasing,
304: * so over-estimates are okay (up to a point), but under-estimates will
305: * negatively affect performance.
306: */
307: #define CACHELINE_2POW 6
308: #define CACHELINE ((size_t)(1 << CACHELINE_2POW))
309:
310: /* Smallest size class to support. */
311: #define TINY_MIN_2POW 1
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: * Maximum desired run header overhead. Runs are sized as small as possible
323: * such that this setting is still honored, without violating other constraints.
324: * The goal is to make runs as small as possible without exceeding a per run
325: * external fragmentation threshold.
326: *
327: * Note that it is possible to set this low enough that it cannot be honored
328: * for some/all object sizes, since there is one bit of header overhead per
329: * object (plus a constant). In such cases, this constraint is relaxed.
330: *
331: * RUN_MAX_OVRHD_RELAX specifies the maximum number of bits per region of
332: * overhead for which RUN_MAX_OVRHD is relaxed.
333: */
334: #define RUN_MAX_OVRHD 0.015
335: #define RUN_MAX_OVRHD_RELAX 1.5
336:
337: /* Put a cap on small object run size. This overrides RUN_MAX_OVRHD. */
338: #define RUN_MAX_SMALL_2POW 15
339: #define RUN_MAX_SMALL (1 << RUN_MAX_SMALL_2POW)
340:
341: /******************************************************************************/
342:
1.2 ad 343: #ifdef __FreeBSD__
1.1 ad 344: /*
345: * Mutexes based on spinlocks. We can't use normal pthread mutexes, because
346: * they require malloc()ed memory.
347: */
348: typedef struct {
349: spinlock_t lock;
350: } malloc_mutex_t;
351:
352: /* Set to true once the allocator has been initialized. */
353: static bool malloc_initialized = false;
354:
355: /* Used to avoid initialization races. */
356: static malloc_mutex_t init_lock = {_SPINLOCK_INITIALIZER};
1.2 ad 357: #else
358: #define malloc_mutex_t mutex_t
359:
360: /* Set to true once the allocator has been initialized. */
361: static bool malloc_initialized = false;
362:
363: /* Used to avoid initialization races. */
364: static mutex_t init_lock = MUTEX_INITIALIZER;
365: #endif
1.1 ad 366:
367: /******************************************************************************/
368: /*
369: * Statistics data structures.
370: */
371:
372: #ifdef MALLOC_STATS
373:
374: typedef struct malloc_bin_stats_s malloc_bin_stats_t;
375: struct malloc_bin_stats_s {
376: /*
377: * Number of allocation requests that corresponded to the size of this
378: * bin.
379: */
380: uint64_t nrequests;
381:
382: /* Total number of runs created for this bin's size class. */
383: uint64_t nruns;
384:
385: /*
386: * Total number of runs reused by extracting them from the runs tree for
387: * this bin's size class.
388: */
389: uint64_t reruns;
390:
391: /* High-water mark for this bin. */
392: unsigned long highruns;
393:
394: /* Current number of runs in this bin. */
395: unsigned long curruns;
396: };
397:
398: typedef struct arena_stats_s arena_stats_t;
399: struct arena_stats_s {
400: /* Number of bytes currently mapped. */
401: size_t mapped;
402:
403: /* Per-size-category statistics. */
404: size_t allocated_small;
405: uint64_t nmalloc_small;
406: uint64_t ndalloc_small;
407:
408: size_t allocated_large;
409: uint64_t nmalloc_large;
410: uint64_t ndalloc_large;
411: };
412:
413: typedef struct chunk_stats_s chunk_stats_t;
414: struct chunk_stats_s {
415: /* Number of chunks that were allocated. */
416: uint64_t nchunks;
417:
418: /* High-water mark for number of chunks allocated. */
419: unsigned long highchunks;
420:
421: /*
422: * Current number of chunks allocated. This value isn't maintained for
423: * any other purpose, so keep track of it in order to be able to set
424: * highchunks.
425: */
426: unsigned long curchunks;
427: };
428:
429: #endif /* #ifdef MALLOC_STATS */
430:
431: /******************************************************************************/
432: /*
433: * Chunk data structures.
434: */
435:
436: /* Tree of chunks. */
437: typedef struct chunk_node_s chunk_node_t;
438: struct chunk_node_s {
439: /* Linkage for the chunk tree. */
440: RB_ENTRY(chunk_node_s) link;
441:
442: /*
443: * Pointer to the chunk that this tree node is responsible for. In some
444: * (but certainly not all) cases, this data structure is placed at the
445: * beginning of the corresponding chunk, so this field may point to this
446: * node.
447: */
448: void *chunk;
449:
450: /* Total chunk size. */
451: size_t size;
452: };
453: typedef struct chunk_tree_s chunk_tree_t;
454: RB_HEAD(chunk_tree_s, chunk_node_s);
455:
456: /******************************************************************************/
457: /*
458: * Arena data structures.
459: */
460:
461: typedef struct arena_s arena_t;
462: typedef struct arena_bin_s arena_bin_t;
463:
464: typedef struct arena_chunk_map_s arena_chunk_map_t;
465: struct arena_chunk_map_s {
466: /* Number of pages in run. */
467: uint32_t npages;
468: /*
469: * Position within run. For a free run, this is POS_FREE for the first
470: * and last pages. The POS_FREE special value makes it possible to
471: * quickly coalesce free runs.
472: *
473: * This is the limiting factor for chunksize; there can be at most 2^31
474: * pages in a run.
475: */
476: #define POS_FREE ((uint32_t)0xffffffffU)
477: uint32_t pos;
478: };
479:
480: /* Arena chunk header. */
481: typedef struct arena_chunk_s arena_chunk_t;
482: struct arena_chunk_s {
483: /* Arena that owns the chunk. */
484: arena_t *arena;
485:
486: /* Linkage for the arena's chunk tree. */
487: RB_ENTRY(arena_chunk_s) link;
488:
489: /*
490: * Number of pages in use. This is maintained in order to make
491: * detection of empty chunks fast.
492: */
493: uint32_t pages_used;
494:
495: /*
496: * Every time a free run larger than this value is created/coalesced,
497: * this value is increased. The only way that the value decreases is if
498: * arena_run_alloc() fails to find a free run as large as advertised by
499: * this value.
500: */
501: uint32_t max_frun_npages;
502:
503: /*
504: * Every time a free run that starts at an earlier page than this value
505: * is created/coalesced, this value is decreased. It is reset in a
506: * similar fashion to max_frun_npages.
507: */
508: uint32_t min_frun_ind;
509:
510: /*
511: * Map of pages within chunk that keeps track of free/large/small. For
512: * free runs, only the map entries for the first and last pages are
513: * kept up to date, so that free runs can be quickly coalesced.
514: */
515: arena_chunk_map_t map[1]; /* Dynamically sized. */
516: };
517: typedef struct arena_chunk_tree_s arena_chunk_tree_t;
518: RB_HEAD(arena_chunk_tree_s, arena_chunk_s);
519:
520: typedef struct arena_run_s arena_run_t;
521: struct arena_run_s {
522: /* Linkage for run trees. */
523: RB_ENTRY(arena_run_s) link;
524:
525: #ifdef MALLOC_DEBUG
526: uint32_t magic;
527: # define ARENA_RUN_MAGIC 0x384adf93
528: #endif
529:
530: /* Bin this run is associated with. */
531: arena_bin_t *bin;
532:
533: /* Index of first element that might have a free region. */
534: unsigned regs_minelm;
535:
536: /* Number of free regions in run. */
537: unsigned nfree;
538:
539: /* Bitmask of in-use regions (0: in use, 1: free). */
540: unsigned regs_mask[1]; /* Dynamically sized. */
541: };
542: typedef struct arena_run_tree_s arena_run_tree_t;
543: RB_HEAD(arena_run_tree_s, arena_run_s);
544:
545: struct arena_bin_s {
546: /*
547: * Current run being used to service allocations of this bin's size
548: * class.
549: */
550: arena_run_t *runcur;
551:
552: /*
553: * Tree of non-full runs. This tree is used when looking for an
554: * existing run when runcur is no longer usable. We choose the
555: * non-full run that is lowest in memory; this policy tends to keep
556: * objects packed well, and it can also help reduce the number of
557: * almost-empty chunks.
558: */
559: arena_run_tree_t runs;
560:
561: /* Size of regions in a run for this bin's size class. */
562: size_t reg_size;
563:
564: /* Total size of a run for this bin's size class. */
565: size_t run_size;
566:
567: /* Total number of regions in a run for this bin's size class. */
568: uint32_t nregs;
569:
570: /* Number of elements in a run's regs_mask for this bin's size class. */
571: uint32_t regs_mask_nelms;
572:
573: /* Offset of first region in a run for this bin's size class. */
574: uint32_t reg0_offset;
575:
576: #ifdef MALLOC_STATS
577: /* Bin statistics. */
578: malloc_bin_stats_t stats;
579: #endif
580: };
581:
582: struct arena_s {
583: #ifdef MALLOC_DEBUG
584: uint32_t magic;
585: # define ARENA_MAGIC 0x947d3d24
586: #endif
587:
588: /* All operations on this arena require that mtx be locked. */
589: malloc_mutex_t mtx;
590:
591: #ifdef MALLOC_STATS
592: arena_stats_t stats;
593: #endif
594:
595: /*
596: * Tree of chunks this arena manages.
597: */
598: arena_chunk_tree_t chunks;
599:
600: /*
601: * In order to avoid rapid chunk allocation/deallocation when an arena
602: * oscillates right on the cusp of needing a new chunk, cache the most
603: * recently freed chunk. This caching is disabled by opt_hint.
604: *
605: * There is one spare chunk per arena, rather than one spare total, in
606: * order to avoid interactions between multiple threads that could make
607: * a single spare inadequate.
608: */
609: arena_chunk_t *spare;
610:
611: /*
612: * bins is used to store rings of free regions of the following sizes,
613: * assuming a 16-byte quantum, 4kB pagesize, and default MALLOC_OPTIONS.
614: *
615: * bins[i] | size |
616: * --------+------+
617: * 0 | 2 |
618: * 1 | 4 |
619: * 2 | 8 |
620: * --------+------+
621: * 3 | 16 |
622: * 4 | 32 |
623: * 5 | 48 |
624: * 6 | 64 |
625: * : :
626: * : :
627: * 33 | 496 |
628: * 34 | 512 |
629: * --------+------+
630: * 35 | 1024 |
631: * 36 | 2048 |
632: * --------+------+
633: */
634: arena_bin_t bins[1]; /* Dynamically sized. */
635: };
636:
637: /******************************************************************************/
638: /*
639: * Data.
640: */
641:
642: /* Number of CPUs. */
643: static unsigned ncpus;
644:
645: /* VM page size. */
646: static size_t pagesize;
647: static size_t pagesize_mask;
1.9 christos 648: static int pagesize_2pow;
1.1 ad 649:
650: /* Various bin-related settings. */
651: static size_t bin_maxclass; /* Max size class for bins. */
652: static unsigned ntbins; /* Number of (2^n)-spaced tiny bins. */
653: static unsigned nqbins; /* Number of quantum-spaced bins. */
654: static unsigned nsbins; /* Number of (2^n)-spaced sub-page bins. */
655: static size_t small_min;
656: static size_t small_max;
657:
658: /* Various quantum-related settings. */
659: static size_t quantum;
660: static size_t quantum_mask; /* (quantum - 1). */
661:
662: /* Various chunk-related settings. */
663: static size_t chunksize;
664: static size_t chunksize_mask; /* (chunksize - 1). */
1.5 yamt 665: static int chunksize_2pow;
1.1 ad 666: static unsigned chunk_npages;
667: static unsigned arena_chunk_header_npages;
668: static size_t arena_maxclass; /* Max size class for arenas. */
669:
670: /********/
671: /*
672: * Chunks.
673: */
674:
675: /* Protects chunk-related data structures. */
676: static malloc_mutex_t chunks_mtx;
677:
678: /* Tree of chunks that are stand-alone huge allocations. */
679: static chunk_tree_t huge;
680:
681: #ifdef USE_BRK
682: /*
683: * Try to use brk for chunk-size allocations, due to address space constraints.
684: */
685: /*
686: * Protects sbrk() calls. This must be separate from chunks_mtx, since
687: * base_pages_alloc() also uses sbrk(), but cannot lock chunks_mtx (doing so
688: * could cause recursive lock acquisition).
689: */
690: static malloc_mutex_t brk_mtx;
691: /* Result of first sbrk(0) call. */
692: static void *brk_base;
693: /* Current end of brk, or ((void *)-1) if brk is exhausted. */
694: static void *brk_prev;
695: /* Current upper limit on brk addresses. */
696: static void *brk_max;
697: #endif
698:
699: #ifdef MALLOC_STATS
700: /* Huge allocation statistics. */
701: static uint64_t huge_nmalloc;
702: static uint64_t huge_ndalloc;
1.8 yamt 703: static uint64_t huge_nralloc;
1.1 ad 704: static size_t huge_allocated;
705: #endif
706:
707: /*
708: * Tree of chunks that were previously allocated. This is used when allocating
709: * chunks, in an attempt to re-use address space.
710: */
711: static chunk_tree_t old_chunks;
712:
713: /****************************/
714: /*
715: * base (internal allocation).
716: */
717:
718: /*
719: * Current pages that are being used for internal memory allocations. These
720: * pages are carved up in cacheline-size quanta, so that there is no chance of
721: * false cache line sharing.
722: */
723: static void *base_pages;
724: static void *base_next_addr;
725: static void *base_past_addr; /* Addr immediately past base_pages. */
726: static chunk_node_t *base_chunk_nodes; /* LIFO cache of chunk nodes. */
727: static malloc_mutex_t base_mtx;
728: #ifdef MALLOC_STATS
729: static size_t base_mapped;
730: #endif
731:
732: /********/
733: /*
734: * Arenas.
735: */
736:
737: /*
738: * Arenas that are used to service external requests. Not all elements of the
739: * arenas array are necessarily used; arenas are created lazily as needed.
740: */
741: static arena_t **arenas;
742: static unsigned narenas;
743: static unsigned next_arena;
744: static malloc_mutex_t arenas_mtx; /* Protects arenas initialization. */
745:
1.15 ad 746: #ifndef NO_TLS
747: /*
748: * Map of pthread_self() --> arenas[???], used for selecting an arena to use
749: * for allocations.
750: */
751: static __thread arena_t *arenas_map;
752: #define get_arenas_map() (arenas_map)
753: #define set_arenas_map(x) (arenas_map = x)
754: #else
1.2 ad 755: static thread_key_t arenas_map_key;
1.15 ad 756: #define get_arenas_map() thr_getspecific(arenas_map_key)
757: #define set_arenas_map(x) thr_setspecific(arenas_map_key, x)
758: #endif
1.1 ad 759:
760: #ifdef MALLOC_STATS
761: /* Chunk statistics. */
762: static chunk_stats_t stats_chunks;
763: #endif
764:
765: /*******************************/
766: /*
767: * Runtime configuration options.
768: */
769: const char *_malloc_options;
770:
771: #ifndef MALLOC_PRODUCTION
772: static bool opt_abort = true;
773: static bool opt_junk = true;
774: #else
775: static bool opt_abort = false;
776: static bool opt_junk = false;
777: #endif
778: static bool opt_hint = false;
779: static bool opt_print_stats = false;
1.9 christos 780: static int opt_quantum_2pow = QUANTUM_2POW_MIN;
781: static int opt_small_max_2pow = SMALL_MAX_2POW_DEFAULT;
782: static int opt_chunk_2pow = CHUNK_2POW_DEFAULT;
1.1 ad 783: static bool opt_utrace = false;
784: static bool opt_sysv = false;
785: static bool opt_xmalloc = false;
786: static bool opt_zero = false;
787: static int32_t opt_narenas_lshift = 0;
788:
789: typedef struct {
790: void *p;
791: size_t s;
792: void *r;
793: } malloc_utrace_t;
794:
795: #define UTRACE(a, b, c) \
796: if (opt_utrace) { \
1.2 ad 797: malloc_utrace_t ut; \
798: ut.p = a; \
799: ut.s = b; \
800: ut.r = c; \
801: xutrace(&ut, sizeof(ut)); \
1.1 ad 802: }
803:
804: /******************************************************************************/
805: /*
806: * Begin function prototypes for non-inline static functions.
807: */
808:
809: static void wrtmessage(const char *p1, const char *p2, const char *p3,
810: const char *p4);
811: #ifdef MALLOC_STATS
812: static void malloc_printf(const char *format, ...);
813: #endif
814: static char *umax2s(uintmax_t x, char *s);
815: static bool base_pages_alloc(size_t minsize);
816: static void *base_alloc(size_t size);
817: static chunk_node_t *base_chunk_node_alloc(void);
818: static void base_chunk_node_dealloc(chunk_node_t *node);
819: #ifdef MALLOC_STATS
820: static void stats_print(arena_t *arena);
821: #endif
822: static void *pages_map(void *addr, size_t size);
1.5 yamt 823: static void *pages_map_align(void *addr, size_t size, int align);
1.1 ad 824: static void pages_unmap(void *addr, size_t size);
825: static void *chunk_alloc(size_t size);
826: static void chunk_dealloc(void *chunk, size_t size);
827: static void arena_run_split(arena_t *arena, arena_run_t *run, size_t size);
828: static arena_chunk_t *arena_chunk_alloc(arena_t *arena);
829: static void arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk);
830: static arena_run_t *arena_run_alloc(arena_t *arena, size_t size);
831: static void arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size);
832: static arena_run_t *arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin);
833: static void *arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin);
834: static size_t arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size);
835: static void *arena_malloc(arena_t *arena, size_t size);
836: static void *arena_palloc(arena_t *arena, size_t alignment, size_t size,
837: size_t alloc_size);
838: static size_t arena_salloc(const void *ptr);
839: static void *arena_ralloc(void *ptr, size_t size, size_t oldsize);
840: static void arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr);
841: static bool arena_new(arena_t *arena);
842: static arena_t *arenas_extend(unsigned ind);
843: static void *huge_malloc(size_t size);
844: static void *huge_palloc(size_t alignment, size_t size);
845: static void *huge_ralloc(void *ptr, size_t size, size_t oldsize);
846: static void huge_dalloc(void *ptr);
847: static void *imalloc(size_t size);
848: static void *ipalloc(size_t alignment, size_t size);
849: static void *icalloc(size_t size);
850: static size_t isalloc(const void *ptr);
851: static void *iralloc(void *ptr, size_t size);
852: static void idalloc(void *ptr);
853: static void malloc_print_stats(void);
854: static bool malloc_init_hard(void);
855:
856: /*
857: * End function prototypes.
858: */
859: /******************************************************************************/
860: /*
861: * Begin mutex.
862: */
863:
1.15 ad 864: #ifdef __NetBSD__
1.2 ad 865: #define malloc_mutex_init(m) mutex_init(m, NULL)
866: #define malloc_mutex_lock(m) mutex_lock(m)
867: #define malloc_mutex_unlock(m) mutex_unlock(m)
1.15 ad 868: #else /* __NetBSD__ */
869: static inline void
870: malloc_mutex_init(malloc_mutex_t *a_mutex)
871: {
872: static const spinlock_t lock = _SPINLOCK_INITIALIZER;
873:
874: a_mutex->lock = lock;
875: }
876:
877: static inline void
878: malloc_mutex_lock(malloc_mutex_t *a_mutex)
879: {
880:
881: if (__isthreaded)
882: _SPINLOCK(&a_mutex->lock);
883: }
884:
885: static inline void
886: malloc_mutex_unlock(malloc_mutex_t *a_mutex)
887: {
888:
889: if (__isthreaded)
890: _SPINUNLOCK(&a_mutex->lock);
891: }
892: #endif /* __NetBSD__ */
1.1 ad 893:
894: /*
895: * End mutex.
896: */
897: /******************************************************************************/
898: /*
899: * Begin Utility functions/macros.
900: */
901:
902: /* Return the chunk address for allocation address a. */
903: #define CHUNK_ADDR2BASE(a) \
904: ((void *)((uintptr_t)(a) & ~chunksize_mask))
905:
906: /* Return the chunk offset of address a. */
907: #define CHUNK_ADDR2OFFSET(a) \
908: ((size_t)((uintptr_t)(a) & chunksize_mask))
909:
910: /* Return the smallest chunk multiple that is >= s. */
911: #define CHUNK_CEILING(s) \
912: (((s) + chunksize_mask) & ~chunksize_mask)
913:
914: /* Return the smallest cacheline multiple that is >= s. */
915: #define CACHELINE_CEILING(s) \
916: (((s) + (CACHELINE - 1)) & ~(CACHELINE - 1))
917:
918: /* Return the smallest quantum multiple that is >= a. */
919: #define QUANTUM_CEILING(a) \
920: (((a) + quantum_mask) & ~quantum_mask)
921:
922: /* Return the smallest pagesize multiple that is >= s. */
923: #define PAGE_CEILING(s) \
924: (((s) + pagesize_mask) & ~pagesize_mask)
925:
926: /* Compute the smallest power of 2 that is >= x. */
927: static inline size_t
928: pow2_ceil(size_t x)
929: {
930:
931: x--;
932: x |= x >> 1;
933: x |= x >> 2;
934: x |= x >> 4;
935: x |= x >> 8;
936: x |= x >> 16;
937: #if (SIZEOF_PTR == 8)
938: x |= x >> 32;
939: #endif
940: x++;
941: return (x);
942: }
943:
944: static void
945: wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
946: {
947:
1.16 christos 948: write(STDERR_FILENO, p1, strlen(p1));
949: write(STDERR_FILENO, p2, strlen(p2));
950: write(STDERR_FILENO, p3, strlen(p3));
951: write(STDERR_FILENO, p4, strlen(p4));
1.1 ad 952: }
953:
954: void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
955: const char *p4) = wrtmessage;
956:
957: #ifdef MALLOC_STATS
958: /*
959: * Print to stderr in such a way as to (hopefully) avoid memory allocation.
960: */
961: static void
962: malloc_printf(const char *format, ...)
963: {
964: char buf[4096];
965: va_list ap;
966:
967: va_start(ap, format);
968: vsnprintf(buf, sizeof(buf), format, ap);
969: va_end(ap);
970: _malloc_message(buf, "", "", "");
971: }
972: #endif
973:
974: /*
975: * We don't want to depend on vsnprintf() for production builds, since that can
976: * cause unnecessary bloat for static binaries. umax2s() provides minimal
977: * integer printing functionality, so that malloc_printf() use can be limited to
978: * MALLOC_STATS code.
979: */
980: #define UMAX2S_BUFSIZE 21
981: static char *
982: umax2s(uintmax_t x, char *s)
983: {
984: unsigned i;
985:
986: /* Make sure UMAX2S_BUFSIZE is large enough. */
1.7 yamt 987: /* LINTED */
1.1 ad 988: assert(sizeof(uintmax_t) <= 8);
989:
990: i = UMAX2S_BUFSIZE - 1;
991: s[i] = '\0';
992: do {
993: i--;
1.2 ad 994: s[i] = "0123456789"[(int)x % 10];
995: x /= (uintmax_t)10LL;
1.1 ad 996: } while (x > 0);
997:
998: return (&s[i]);
999: }
1000:
1001: /******************************************************************************/
1002:
1003: static bool
1004: base_pages_alloc(size_t minsize)
1005: {
1.2 ad 1006: size_t csize = 0;
1.1 ad 1007:
1008: #ifdef USE_BRK
1009: /*
1010: * Do special brk allocation here, since base allocations don't need to
1011: * be chunk-aligned.
1012: */
1013: if (brk_prev != (void *)-1) {
1014: void *brk_cur;
1015: intptr_t incr;
1016:
1017: if (minsize != 0)
1018: csize = CHUNK_CEILING(minsize);
1019:
1020: malloc_mutex_lock(&brk_mtx);
1021: do {
1022: /* Get the current end of brk. */
1023: brk_cur = sbrk(0);
1024:
1025: /*
1026: * Calculate how much padding is necessary to
1027: * chunk-align the end of brk. Don't worry about
1028: * brk_cur not being chunk-aligned though.
1029: */
1030: incr = (intptr_t)chunksize
1031: - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
1032: if (incr < minsize)
1033: incr += csize;
1034:
1035: brk_prev = sbrk(incr);
1036: if (brk_prev == brk_cur) {
1037: /* Success. */
1038: malloc_mutex_unlock(&brk_mtx);
1039: base_pages = brk_cur;
1040: base_next_addr = base_pages;
1041: base_past_addr = (void *)((uintptr_t)base_pages
1042: + incr);
1043: #ifdef MALLOC_STATS
1044: base_mapped += incr;
1045: #endif
1046: return (false);
1047: }
1048: } while (brk_prev != (void *)-1);
1049: malloc_mutex_unlock(&brk_mtx);
1050: }
1051: if (minsize == 0) {
1052: /*
1053: * Failure during initialization doesn't matter, so avoid
1054: * falling through to the mmap-based page mapping code.
1055: */
1056: return (true);
1057: }
1058: #endif
1059: assert(minsize != 0);
1060: csize = PAGE_CEILING(minsize);
1061: base_pages = pages_map(NULL, csize);
1062: if (base_pages == NULL)
1063: return (true);
1064: base_next_addr = base_pages;
1065: base_past_addr = (void *)((uintptr_t)base_pages + csize);
1066: #ifdef MALLOC_STATS
1067: base_mapped += csize;
1068: #endif
1069: return (false);
1070: }
1071:
1072: static void *
1073: base_alloc(size_t size)
1074: {
1075: void *ret;
1076: size_t csize;
1077:
1078: /* Round size up to nearest multiple of the cacheline size. */
1079: csize = CACHELINE_CEILING(size);
1080:
1081: malloc_mutex_lock(&base_mtx);
1082:
1083: /* Make sure there's enough space for the allocation. */
1084: if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
1085: if (base_pages_alloc(csize)) {
1086: ret = NULL;
1087: goto RETURN;
1088: }
1089: }
1090:
1091: /* Allocate. */
1092: ret = base_next_addr;
1093: base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
1094:
1095: RETURN:
1096: malloc_mutex_unlock(&base_mtx);
1097: return (ret);
1098: }
1099:
1100: static chunk_node_t *
1101: base_chunk_node_alloc(void)
1102: {
1103: chunk_node_t *ret;
1104:
1105: malloc_mutex_lock(&base_mtx);
1106: if (base_chunk_nodes != NULL) {
1107: ret = base_chunk_nodes;
1.2 ad 1108: /* LINTED */
1.1 ad 1109: base_chunk_nodes = *(chunk_node_t **)ret;
1110: malloc_mutex_unlock(&base_mtx);
1111: } else {
1112: malloc_mutex_unlock(&base_mtx);
1113: ret = (chunk_node_t *)base_alloc(sizeof(chunk_node_t));
1114: }
1115:
1116: return (ret);
1117: }
1118:
1119: static void
1120: base_chunk_node_dealloc(chunk_node_t *node)
1121: {
1122:
1123: malloc_mutex_lock(&base_mtx);
1.2 ad 1124: /* LINTED */
1.1 ad 1125: *(chunk_node_t **)node = base_chunk_nodes;
1126: base_chunk_nodes = node;
1127: malloc_mutex_unlock(&base_mtx);
1128: }
1129:
1130: /******************************************************************************/
1131:
1132: #ifdef MALLOC_STATS
1133: static void
1134: stats_print(arena_t *arena)
1135: {
1136: unsigned i;
1137: int gap_start;
1138:
1139: malloc_printf(
1140: " allocated/mapped nmalloc ndalloc\n");
1.2 ad 1141:
1142: malloc_printf("small: %12zu %-12s %12llu %12llu\n",
1.1 ad 1143: arena->stats.allocated_small, "", arena->stats.nmalloc_small,
1144: arena->stats.ndalloc_small);
1.2 ad 1145: malloc_printf("large: %12zu %-12s %12llu %12llu\n",
1.1 ad 1146: arena->stats.allocated_large, "", arena->stats.nmalloc_large,
1147: arena->stats.ndalloc_large);
1.2 ad 1148: malloc_printf("total: %12zu/%-12zu %12llu %12llu\n",
1.1 ad 1149: arena->stats.allocated_small + arena->stats.allocated_large,
1150: arena->stats.mapped,
1151: arena->stats.nmalloc_small + arena->stats.nmalloc_large,
1152: arena->stats.ndalloc_small + arena->stats.ndalloc_large);
1153:
1154: malloc_printf("bins: bin size regs pgs requests newruns"
1155: " reruns maxruns curruns\n");
1156: for (i = 0, gap_start = -1; i < ntbins + nqbins + nsbins; i++) {
1157: if (arena->bins[i].stats.nrequests == 0) {
1158: if (gap_start == -1)
1159: gap_start = i;
1160: } else {
1161: if (gap_start != -1) {
1162: if (i > gap_start + 1) {
1163: /* Gap of more than one size class. */
1164: malloc_printf("[%u..%u]\n",
1165: gap_start, i - 1);
1166: } else {
1167: /* Gap of one size class. */
1168: malloc_printf("[%u]\n", gap_start);
1169: }
1170: gap_start = -1;
1171: }
1172: malloc_printf(
1173: "%13u %1s %4u %4u %3u %9llu %9llu"
1174: " %9llu %7lu %7lu\n",
1175: i,
1176: i < ntbins ? "T" : i < ntbins + nqbins ? "Q" : "S",
1177: arena->bins[i].reg_size,
1178: arena->bins[i].nregs,
1179: arena->bins[i].run_size >> pagesize_2pow,
1180: arena->bins[i].stats.nrequests,
1181: arena->bins[i].stats.nruns,
1182: arena->bins[i].stats.reruns,
1183: arena->bins[i].stats.highruns,
1184: arena->bins[i].stats.curruns);
1185: }
1186: }
1187: if (gap_start != -1) {
1188: if (i > gap_start + 1) {
1189: /* Gap of more than one size class. */
1190: malloc_printf("[%u..%u]\n", gap_start, i - 1);
1191: } else {
1192: /* Gap of one size class. */
1193: malloc_printf("[%u]\n", gap_start);
1194: }
1195: }
1196: }
1197: #endif
1198:
1199: /*
1200: * End Utility functions/macros.
1201: */
1202: /******************************************************************************/
1203: /*
1204: * Begin chunk management functions.
1205: */
1206:
1.7 yamt 1207: #ifndef lint
1.1 ad 1208: static inline int
1209: chunk_comp(chunk_node_t *a, chunk_node_t *b)
1210: {
1211:
1212: assert(a != NULL);
1213: assert(b != NULL);
1214:
1215: if ((uintptr_t)a->chunk < (uintptr_t)b->chunk)
1216: return (-1);
1217: else if (a->chunk == b->chunk)
1218: return (0);
1219: else
1220: return (1);
1221: }
1222:
1223: /* Generate red-black tree code for chunks. */
1224: RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);
1.2 ad 1225: #endif
1.1 ad 1226:
1227: static void *
1.5 yamt 1228: pages_map_align(void *addr, size_t size, int align)
1.1 ad 1229: {
1230: void *ret;
1231:
1232: /*
1233: * We don't use MAP_FIXED here, because it can cause the *replacement*
1234: * of existing mappings, and we only want to create new mappings.
1235: */
1.5 yamt 1236: ret = mmap(addr, size, PROT_READ | PROT_WRITE,
1237: MAP_PRIVATE | MAP_ANON | MAP_ALIGNED(align), -1, 0);
1.1 ad 1238: assert(ret != NULL);
1239:
1240: if (ret == MAP_FAILED)
1241: ret = NULL;
1242: else if (addr != NULL && ret != addr) {
1243: /*
1244: * We succeeded in mapping memory, but not in the right place.
1245: */
1246: if (munmap(ret, size) == -1) {
1247: char buf[STRERROR_BUF];
1248:
1.16 christos 1249: STRERROR_R(errno, buf, sizeof(buf));
1250: _malloc_message(getprogname(),
1.1 ad 1251: ": (malloc) Error in munmap(): ", buf, "\n");
1252: if (opt_abort)
1253: abort();
1254: }
1255: ret = NULL;
1256: }
1257:
1258: assert(ret == NULL || (addr == NULL && ret != addr)
1259: || (addr != NULL && ret == addr));
1260: return (ret);
1261: }
1262:
1.5 yamt 1263: static void *
1264: pages_map(void *addr, size_t size)
1265: {
1266:
1267: return pages_map_align(addr, size, 0);
1268: }
1269:
1.1 ad 1270: static void
1271: pages_unmap(void *addr, size_t size)
1272: {
1273:
1274: if (munmap(addr, size) == -1) {
1275: char buf[STRERROR_BUF];
1276:
1.16 christos 1277: STRERROR_R(errno, buf, sizeof(buf));
1278: _malloc_message(getprogname(),
1.1 ad 1279: ": (malloc) Error in munmap(): ", buf, "\n");
1280: if (opt_abort)
1281: abort();
1282: }
1283: }
1284:
1285: static void *
1286: chunk_alloc(size_t size)
1287: {
1288: void *ret, *chunk;
1289: chunk_node_t *tchunk, *delchunk;
1290:
1291: assert(size != 0);
1292: assert((size & chunksize_mask) == 0);
1293:
1294: malloc_mutex_lock(&chunks_mtx);
1295:
1296: if (size == chunksize) {
1297: /*
1298: * Check for address ranges that were previously chunks and try
1299: * to use them.
1300: */
1301:
1.2 ad 1302: /* LINTED */
1.1 ad 1303: tchunk = RB_MIN(chunk_tree_s, &old_chunks);
1304: while (tchunk != NULL) {
1305: /* Found an address range. Try to recycle it. */
1306:
1307: chunk = tchunk->chunk;
1308: delchunk = tchunk;
1.2 ad 1309: /* LINTED */
1.1 ad 1310: tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
1311:
1312: /* Remove delchunk from the tree. */
1.2 ad 1313: /* LINTED */
1.1 ad 1314: RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
1315: base_chunk_node_dealloc(delchunk);
1316:
1317: #ifdef USE_BRK
1318: if ((uintptr_t)chunk >= (uintptr_t)brk_base
1319: && (uintptr_t)chunk < (uintptr_t)brk_max) {
1320: /* Re-use a previously freed brk chunk. */
1321: ret = chunk;
1322: goto RETURN;
1323: }
1324: #endif
1325: if ((ret = pages_map(chunk, size)) != NULL) {
1326: /* Success. */
1327: goto RETURN;
1328: }
1329: }
1330: }
1331:
1332: /*
1333: * Try to over-allocate, but allow the OS to place the allocation
1334: * anywhere. Beware of size_t wrap-around.
1335: */
1336: if (size + chunksize > size) {
1.5 yamt 1337: if ((ret = pages_map_align(NULL, size, chunksize_2pow))
1338: != NULL) {
1.1 ad 1339: goto RETURN;
1340: }
1341: }
1342:
1343: #ifdef USE_BRK
1344: /*
1345: * Try to create allocations in brk, in order to make full use of
1346: * limited address space.
1347: */
1348: if (brk_prev != (void *)-1) {
1349: void *brk_cur;
1350: intptr_t incr;
1351:
1352: /*
1353: * The loop is necessary to recover from races with other
1354: * threads that are using brk for something other than malloc.
1355: */
1356: malloc_mutex_lock(&brk_mtx);
1357: do {
1358: /* Get the current end of brk. */
1359: brk_cur = sbrk(0);
1360:
1361: /*
1362: * Calculate how much padding is necessary to
1363: * chunk-align the end of brk.
1364: */
1365: incr = (intptr_t)size
1366: - (intptr_t)CHUNK_ADDR2OFFSET(brk_cur);
1367: if (incr == size) {
1368: ret = brk_cur;
1369: } else {
1370: ret = (void *)((intptr_t)brk_cur + incr);
1371: incr += size;
1372: }
1373:
1374: brk_prev = sbrk(incr);
1375: if (brk_prev == brk_cur) {
1376: /* Success. */
1377: malloc_mutex_unlock(&brk_mtx);
1378: brk_max = (void *)((intptr_t)ret + size);
1379: goto RETURN;
1380: }
1381: } while (brk_prev != (void *)-1);
1382: malloc_mutex_unlock(&brk_mtx);
1383: }
1384: #endif
1385:
1386: /* All strategies for allocation failed. */
1387: ret = NULL;
1388: RETURN:
1389: if (ret != NULL) {
1390: chunk_node_t key;
1391: /*
1392: * Clean out any entries in old_chunks that overlap with the
1393: * memory we just allocated.
1394: */
1395: key.chunk = ret;
1.2 ad 1396: /* LINTED */
1.1 ad 1397: tchunk = RB_NFIND(chunk_tree_s, &old_chunks, &key);
1398: while (tchunk != NULL
1399: && (uintptr_t)tchunk->chunk >= (uintptr_t)ret
1400: && (uintptr_t)tchunk->chunk < (uintptr_t)ret + size) {
1401: delchunk = tchunk;
1.2 ad 1402: /* LINTED */
1.1 ad 1403: tchunk = RB_NEXT(chunk_tree_s, &old_chunks, delchunk);
1.2 ad 1404: /* LINTED */
1.1 ad 1405: RB_REMOVE(chunk_tree_s, &old_chunks, delchunk);
1406: base_chunk_node_dealloc(delchunk);
1407: }
1408:
1409: }
1410: #ifdef MALLOC_STATS
1411: if (ret != NULL) {
1412: stats_chunks.nchunks += (size / chunksize);
1413: stats_chunks.curchunks += (size / chunksize);
1414: }
1415: if (stats_chunks.curchunks > stats_chunks.highchunks)
1416: stats_chunks.highchunks = stats_chunks.curchunks;
1417: #endif
1418: malloc_mutex_unlock(&chunks_mtx);
1419:
1420: assert(CHUNK_ADDR2BASE(ret) == ret);
1421: return (ret);
1422: }
1423:
1424: static void
1425: chunk_dealloc(void *chunk, size_t size)
1426: {
1427: chunk_node_t *node;
1428:
1429: assert(chunk != NULL);
1430: assert(CHUNK_ADDR2BASE(chunk) == chunk);
1431: assert(size != 0);
1432: assert((size & chunksize_mask) == 0);
1433:
1434: malloc_mutex_lock(&chunks_mtx);
1435:
1436: #ifdef USE_BRK
1437: if ((uintptr_t)chunk >= (uintptr_t)brk_base
1438: && (uintptr_t)chunk < (uintptr_t)brk_max) {
1439: void *brk_cur;
1440:
1441: malloc_mutex_lock(&brk_mtx);
1442: /* Get the current end of brk. */
1443: brk_cur = sbrk(0);
1444:
1445: /*
1446: * Try to shrink the data segment if this chunk is at the end
1447: * of the data segment. The sbrk() call here is subject to a
1448: * race condition with threads that use brk(2) or sbrk(2)
1449: * directly, but the alternative would be to leak memory for
1450: * the sake of poorly designed multi-threaded programs.
1451: */
1452: if (brk_cur == brk_max
1453: && (void *)((uintptr_t)chunk + size) == brk_max
1454: && sbrk(-(intptr_t)size) == brk_max) {
1455: malloc_mutex_unlock(&brk_mtx);
1456: if (brk_prev == brk_max) {
1457: /* Success. */
1458: brk_prev = (void *)((intptr_t)brk_max
1459: - (intptr_t)size);
1460: brk_max = brk_prev;
1461: }
1462: } else {
1463: size_t offset;
1464:
1465: malloc_mutex_unlock(&brk_mtx);
1466: madvise(chunk, size, MADV_FREE);
1467:
1468: /*
1469: * Iteratively create records of each chunk-sized
1470: * memory region that 'chunk' is comprised of, so that
1471: * the address range can be recycled if memory usage
1472: * increases later on.
1473: */
1474: for (offset = 0; offset < size; offset += chunksize) {
1475: node = base_chunk_node_alloc();
1476: if (node == NULL)
1477: break;
1478:
1479: node->chunk = (void *)((uintptr_t)chunk
1480: + (uintptr_t)offset);
1481: node->size = chunksize;
1.2 ad 1482: /* LINTED */
1.1 ad 1483: RB_INSERT(chunk_tree_s, &old_chunks, node);
1484: }
1485: }
1486: } else {
1487: #endif
1488: pages_unmap(chunk, size);
1489:
1490: /*
1491: * Make a record of the chunk's address, so that the address
1492: * range can be recycled if memory usage increases later on.
1493: * Don't bother to create entries if (size > chunksize), since
1494: * doing so could cause scalability issues for truly gargantuan
1495: * objects (many gigabytes or larger).
1496: */
1497: if (size == chunksize) {
1498: node = base_chunk_node_alloc();
1499: if (node != NULL) {
1500: node->chunk = (void *)(uintptr_t)chunk;
1501: node->size = chunksize;
1.2 ad 1502: /* LINTED */
1.1 ad 1503: RB_INSERT(chunk_tree_s, &old_chunks, node);
1504: }
1505: }
1506: #ifdef USE_BRK
1507: }
1508: #endif
1509:
1510: #ifdef MALLOC_STATS
1511: stats_chunks.curchunks -= (size / chunksize);
1512: #endif
1513: malloc_mutex_unlock(&chunks_mtx);
1514: }
1515:
1516: /*
1517: * End chunk management functions.
1518: */
1519: /******************************************************************************/
1520: /*
1521: * Begin arena.
1522: */
1523:
1524: /*
1.17 ad 1525: * Choose an arena based on a per-thread and (optimistically) per-CPU value.
1526: *
1527: * We maintain at least one block of arenas. Usually there are more.
1528: * The blocks are $ncpu arenas in size. Whole blocks are 'hashed'
1529: * amongst threads. To accomplish this, next_arena advances only in
1530: * ncpu steps.
1.1 ad 1531: */
1.19 ad 1532: static __noinline arena_t *
1533: choose_arena_hard(void)
1.1 ad 1534: {
1.17 ad 1535: unsigned i, curcpu;
1536: arena_t **map;
1.1 ad 1537:
1.17 ad 1538: /* Initialize the current block of arenas and advance to next. */
1.1 ad 1539: malloc_mutex_lock(&arenas_mtx);
1.17 ad 1540: assert(next_arena % ncpus == 0);
1541: assert(narenas % ncpus == 0);
1542: map = &arenas[next_arena];
1543: set_arenas_map(map);
1544: for (i = 0; i < ncpus; i++) {
1545: if (arenas[next_arena] == NULL)
1546: arenas_extend(next_arena);
1547: next_arena = (next_arena + 1) % narenas;
1.15 ad 1548: }
1.1 ad 1549: malloc_mutex_unlock(&arenas_mtx);
1550:
1.17 ad 1551: /*
1552: * If we were unable to allocate an arena above, then default to
1553: * the first arena, which is always present.
1554: */
1555: curcpu = thr_curcpu();
1556: if (map[curcpu] != NULL)
1557: return map[curcpu];
1558: return arenas[0];
1.1 ad 1559: }
1560:
1.19 ad 1561: static inline arena_t *
1562: choose_arena(void)
1563: {
1564: unsigned curcpu;
1565: arena_t **map;
1566:
1567: map = get_arenas_map();
1568: curcpu = thr_curcpu();
1569: if (__predict_true(map != NULL && map[curcpu] != NULL))
1570: return map[curcpu];
1571:
1572: return choose_arena_hard();
1573: }
1574:
1.7 yamt 1575: #ifndef lint
1.1 ad 1576: static inline int
1577: arena_chunk_comp(arena_chunk_t *a, arena_chunk_t *b)
1578: {
1579:
1580: assert(a != NULL);
1581: assert(b != NULL);
1582:
1583: if ((uintptr_t)a < (uintptr_t)b)
1584: return (-1);
1585: else if (a == b)
1586: return (0);
1587: else
1588: return (1);
1589: }
1590:
1591: /* Generate red-black tree code for arena chunks. */
1592: RB_GENERATE_STATIC(arena_chunk_tree_s, arena_chunk_s, link, arena_chunk_comp);
1.2 ad 1593: #endif
1.1 ad 1594:
1.7 yamt 1595: #ifndef lint
1.1 ad 1596: static inline int
1597: arena_run_comp(arena_run_t *a, arena_run_t *b)
1598: {
1599:
1600: assert(a != NULL);
1601: assert(b != NULL);
1602:
1603: if ((uintptr_t)a < (uintptr_t)b)
1604: return (-1);
1605: else if (a == b)
1606: return (0);
1607: else
1608: return (1);
1609: }
1610:
1611: /* Generate red-black tree code for arena runs. */
1612: RB_GENERATE_STATIC(arena_run_tree_s, arena_run_s, link, arena_run_comp);
1.2 ad 1613: #endif
1.1 ad 1614:
1615: static inline void *
1616: arena_run_reg_alloc(arena_run_t *run, arena_bin_t *bin)
1617: {
1618: void *ret;
1619: unsigned i, mask, bit, regind;
1620:
1621: assert(run->magic == ARENA_RUN_MAGIC);
1622: assert(run->regs_minelm < bin->regs_mask_nelms);
1623:
1624: /*
1625: * Move the first check outside the loop, so that run->regs_minelm can
1626: * be updated unconditionally, without the possibility of updating it
1627: * multiple times.
1628: */
1629: i = run->regs_minelm;
1630: mask = run->regs_mask[i];
1631: if (mask != 0) {
1632: /* Usable allocation found. */
1633: bit = ffs((int)mask) - 1;
1634:
1635: regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
1636: ret = (void *)(((uintptr_t)run) + bin->reg0_offset
1637: + (bin->reg_size * regind));
1638:
1639: /* Clear bit. */
1640: mask ^= (1 << bit);
1641: run->regs_mask[i] = mask;
1642:
1643: return (ret);
1644: }
1645:
1646: for (i++; i < bin->regs_mask_nelms; i++) {
1647: mask = run->regs_mask[i];
1648: if (mask != 0) {
1649: /* Usable allocation found. */
1650: bit = ffs((int)mask) - 1;
1651:
1652: regind = ((i << (SIZEOF_INT_2POW + 3)) + bit);
1653: ret = (void *)(((uintptr_t)run) + bin->reg0_offset
1654: + (bin->reg_size * regind));
1655:
1656: /* Clear bit. */
1657: mask ^= (1 << bit);
1658: run->regs_mask[i] = mask;
1659:
1660: /*
1661: * Make a note that nothing before this element
1662: * contains a free region.
1663: */
1664: run->regs_minelm = i; /* Low payoff: + (mask == 0); */
1665:
1666: return (ret);
1667: }
1668: }
1669: /* Not reached. */
1.7 yamt 1670: /* LINTED */
1.1 ad 1671: assert(0);
1672: return (NULL);
1673: }
1674:
1675: static inline void
1676: arena_run_reg_dalloc(arena_run_t *run, arena_bin_t *bin, void *ptr, size_t size)
1677: {
1678: /*
1679: * To divide by a number D that is not a power of two we multiply
1680: * by (2^21 / D) and then right shift by 21 positions.
1681: *
1682: * X / D
1683: *
1684: * becomes
1685: *
1686: * (X * size_invs[(D >> QUANTUM_2POW_MIN) - 3]) >> SIZE_INV_SHIFT
1687: */
1688: #define SIZE_INV_SHIFT 21
1689: #define SIZE_INV(s) (((1 << SIZE_INV_SHIFT) / (s << QUANTUM_2POW_MIN)) + 1)
1690: static const unsigned size_invs[] = {
1691: SIZE_INV(3),
1692: SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
1693: SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
1694: SIZE_INV(12),SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
1695: SIZE_INV(16),SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
1696: SIZE_INV(20),SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
1697: SIZE_INV(24),SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
1698: SIZE_INV(28),SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
1699: #if (QUANTUM_2POW_MIN < 4)
1700: ,
1701: SIZE_INV(32), SIZE_INV(33), SIZE_INV(34), SIZE_INV(35),
1702: SIZE_INV(36), SIZE_INV(37), SIZE_INV(38), SIZE_INV(39),
1703: SIZE_INV(40), SIZE_INV(41), SIZE_INV(42), SIZE_INV(43),
1704: SIZE_INV(44), SIZE_INV(45), SIZE_INV(46), SIZE_INV(47),
1705: SIZE_INV(48), SIZE_INV(49), SIZE_INV(50), SIZE_INV(51),
1706: SIZE_INV(52), SIZE_INV(53), SIZE_INV(54), SIZE_INV(55),
1707: SIZE_INV(56), SIZE_INV(57), SIZE_INV(58), SIZE_INV(59),
1708: SIZE_INV(60), SIZE_INV(61), SIZE_INV(62), SIZE_INV(63)
1709: #endif
1710: };
1711: unsigned diff, regind, elm, bit;
1712:
1.7 yamt 1713: /* LINTED */
1.1 ad 1714: assert(run->magic == ARENA_RUN_MAGIC);
1715: assert(((sizeof(size_invs)) / sizeof(unsigned)) + 3
1716: >= (SMALL_MAX_DEFAULT >> QUANTUM_2POW_MIN));
1717:
1718: /*
1719: * Avoid doing division with a variable divisor if possible. Using
1720: * actual division here can reduce allocator throughput by over 20%!
1721: */
1722: diff = (unsigned)((uintptr_t)ptr - (uintptr_t)run - bin->reg0_offset);
1723: if ((size & (size - 1)) == 0) {
1724: /*
1725: * log2_table allows fast division of a power of two in the
1726: * [1..128] range.
1727: *
1728: * (x / divisor) becomes (x >> log2_table[divisor - 1]).
1729: */
1730: static const unsigned char log2_table[] = {
1731: 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4,
1732: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
1733: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1734: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
1735: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1736: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1737: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1738: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
1739: };
1740:
1741: if (size <= 128)
1742: regind = (diff >> log2_table[size - 1]);
1743: else if (size <= 32768)
1744: regind = diff >> (8 + log2_table[(size >> 8) - 1]);
1745: else {
1746: /*
1747: * The page size is too large for us to use the lookup
1748: * table. Use real division.
1749: */
1.9 christos 1750: regind = (unsigned)(diff / size);
1.1 ad 1751: }
1752: } else if (size <= ((sizeof(size_invs) / sizeof(unsigned))
1753: << QUANTUM_2POW_MIN) + 2) {
1754: regind = size_invs[(size >> QUANTUM_2POW_MIN) - 3] * diff;
1755: regind >>= SIZE_INV_SHIFT;
1756: } else {
1757: /*
1758: * size_invs isn't large enough to handle this size class, so
1759: * calculate regind using actual division. This only happens
1760: * if the user increases small_max via the 'S' runtime
1761: * configuration option.
1762: */
1.9 christos 1763: regind = (unsigned)(diff / size);
1.1 ad 1764: };
1765: assert(diff == regind * size);
1766: assert(regind < bin->nregs);
1767:
1768: elm = regind >> (SIZEOF_INT_2POW + 3);
1769: if (elm < run->regs_minelm)
1770: run->regs_minelm = elm;
1771: bit = regind - (elm << (SIZEOF_INT_2POW + 3));
1772: assert((run->regs_mask[elm] & (1 << bit)) == 0);
1773: run->regs_mask[elm] |= (1 << bit);
1774: #undef SIZE_INV
1775: #undef SIZE_INV_SHIFT
1776: }
1777:
1778: static void
1779: arena_run_split(arena_t *arena, arena_run_t *run, size_t size)
1780: {
1781: arena_chunk_t *chunk;
1782: unsigned run_ind, map_offset, total_pages, need_pages, rem_pages;
1783: unsigned i;
1784:
1785: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1786: run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1787: >> pagesize_2pow);
1788: total_pages = chunk->map[run_ind].npages;
1.9 christos 1789: need_pages = (unsigned)(size >> pagesize_2pow);
1.1 ad 1790: assert(need_pages <= total_pages);
1791: rem_pages = total_pages - need_pages;
1792:
1793: /* Split enough pages from the front of run to fit allocation size. */
1794: map_offset = run_ind;
1795: for (i = 0; i < need_pages; i++) {
1796: chunk->map[map_offset + i].npages = need_pages;
1797: chunk->map[map_offset + i].pos = i;
1798: }
1799:
1800: /* Keep track of trailing unused pages for later use. */
1801: if (rem_pages > 0) {
1802: /* Update map for trailing pages. */
1803: map_offset += need_pages;
1804: chunk->map[map_offset].npages = rem_pages;
1805: chunk->map[map_offset].pos = POS_FREE;
1806: chunk->map[map_offset + rem_pages - 1].npages = rem_pages;
1807: chunk->map[map_offset + rem_pages - 1].pos = POS_FREE;
1808: }
1809:
1810: chunk->pages_used += need_pages;
1811: }
1812:
1813: static arena_chunk_t *
1814: arena_chunk_alloc(arena_t *arena)
1815: {
1816: arena_chunk_t *chunk;
1817:
1818: if (arena->spare != NULL) {
1819: chunk = arena->spare;
1820: arena->spare = NULL;
1821:
1.2 ad 1822: /* LINTED */
1.1 ad 1823: RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
1824: } else {
1825: chunk = (arena_chunk_t *)chunk_alloc(chunksize);
1826: if (chunk == NULL)
1827: return (NULL);
1828: #ifdef MALLOC_STATS
1829: arena->stats.mapped += chunksize;
1830: #endif
1831:
1832: chunk->arena = arena;
1833:
1.2 ad 1834: /* LINTED */
1.1 ad 1835: RB_INSERT(arena_chunk_tree_s, &arena->chunks, chunk);
1836:
1837: /*
1838: * Claim that no pages are in use, since the header is merely
1839: * overhead.
1840: */
1841: chunk->pages_used = 0;
1842:
1843: chunk->max_frun_npages = chunk_npages -
1844: arena_chunk_header_npages;
1845: chunk->min_frun_ind = arena_chunk_header_npages;
1846:
1847: /*
1848: * Initialize enough of the map to support one maximal free run.
1849: */
1850: chunk->map[arena_chunk_header_npages].npages = chunk_npages -
1851: arena_chunk_header_npages;
1852: chunk->map[arena_chunk_header_npages].pos = POS_FREE;
1853: chunk->map[chunk_npages - 1].npages = chunk_npages -
1854: arena_chunk_header_npages;
1855: chunk->map[chunk_npages - 1].pos = POS_FREE;
1856: }
1857:
1858: return (chunk);
1859: }
1860:
1861: static void
1862: arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
1863: {
1864:
1865: /*
1866: * Remove chunk from the chunk tree, regardless of whether this chunk
1867: * will be cached, so that the arena does not use it.
1868: */
1.2 ad 1869: /* LINTED */
1.1 ad 1870: RB_REMOVE(arena_chunk_tree_s, &chunk->arena->chunks, chunk);
1871:
1872: if (opt_hint == false) {
1873: if (arena->spare != NULL) {
1874: chunk_dealloc((void *)arena->spare, chunksize);
1875: #ifdef MALLOC_STATS
1876: arena->stats.mapped -= chunksize;
1877: #endif
1878: }
1879: arena->spare = chunk;
1880: } else {
1881: assert(arena->spare == NULL);
1882: chunk_dealloc((void *)chunk, chunksize);
1883: #ifdef MALLOC_STATS
1884: arena->stats.mapped -= chunksize;
1885: #endif
1886: }
1887: }
1888:
1889: static arena_run_t *
1890: arena_run_alloc(arena_t *arena, size_t size)
1891: {
1892: arena_chunk_t *chunk;
1893: arena_run_t *run;
1894: unsigned need_npages, limit_pages, compl_need_npages;
1895:
1896: assert(size <= (chunksize - (arena_chunk_header_npages <<
1897: pagesize_2pow)));
1898: assert((size & pagesize_mask) == 0);
1899:
1900: /*
1901: * Search through arena's chunks in address order for a free run that is
1902: * large enough. Look for the first fit.
1903: */
1.9 christos 1904: need_npages = (unsigned)(size >> pagesize_2pow);
1.1 ad 1905: limit_pages = chunk_npages - arena_chunk_header_npages;
1906: compl_need_npages = limit_pages - need_npages;
1.2 ad 1907: /* LINTED */
1.1 ad 1908: RB_FOREACH(chunk, arena_chunk_tree_s, &arena->chunks) {
1909: /*
1910: * Avoid searching this chunk if there are not enough
1911: * contiguous free pages for there to possibly be a large
1912: * enough free run.
1913: */
1914: if (chunk->pages_used <= compl_need_npages &&
1915: need_npages <= chunk->max_frun_npages) {
1916: arena_chunk_map_t *mapelm;
1917: unsigned i;
1918: unsigned max_frun_npages = 0;
1919: unsigned min_frun_ind = chunk_npages;
1920:
1921: assert(chunk->min_frun_ind >=
1922: arena_chunk_header_npages);
1923: for (i = chunk->min_frun_ind; i < chunk_npages;) {
1924: mapelm = &chunk->map[i];
1925: if (mapelm->pos == POS_FREE) {
1926: if (mapelm->npages >= need_npages) {
1927: run = (arena_run_t *)
1928: ((uintptr_t)chunk + (i <<
1929: pagesize_2pow));
1930: /* Update page map. */
1931: arena_run_split(arena, run,
1932: size);
1933: return (run);
1934: }
1935: if (mapelm->npages >
1936: max_frun_npages) {
1937: max_frun_npages =
1938: mapelm->npages;
1939: }
1940: if (i < min_frun_ind) {
1941: min_frun_ind = i;
1942: if (i < chunk->min_frun_ind)
1943: chunk->min_frun_ind = i;
1944: }
1945: }
1946: i += mapelm->npages;
1947: }
1948: /*
1949: * Search failure. Reset cached chunk->max_frun_npages.
1950: * chunk->min_frun_ind was already reset above (if
1951: * necessary).
1952: */
1953: chunk->max_frun_npages = max_frun_npages;
1954: }
1955: }
1956:
1957: /*
1958: * No usable runs. Create a new chunk from which to allocate the run.
1959: */
1960: chunk = arena_chunk_alloc(arena);
1961: if (chunk == NULL)
1962: return (NULL);
1963: run = (arena_run_t *)((uintptr_t)chunk + (arena_chunk_header_npages <<
1964: pagesize_2pow));
1965: /* Update page map. */
1966: arena_run_split(arena, run, size);
1967: return (run);
1968: }
1969:
1970: static void
1971: arena_run_dalloc(arena_t *arena, arena_run_t *run, size_t size)
1972: {
1973: arena_chunk_t *chunk;
1974: unsigned run_ind, run_pages;
1975:
1976: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
1977:
1978: run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk)
1979: >> pagesize_2pow);
1980: assert(run_ind >= arena_chunk_header_npages);
1981: assert(run_ind < (chunksize >> pagesize_2pow));
1.9 christos 1982: run_pages = (unsigned)(size >> pagesize_2pow);
1.1 ad 1983: assert(run_pages == chunk->map[run_ind].npages);
1984:
1985: /* Subtract pages from count of pages used in chunk. */
1986: chunk->pages_used -= run_pages;
1987:
1988: /* Mark run as deallocated. */
1989: assert(chunk->map[run_ind].npages == run_pages);
1990: chunk->map[run_ind].pos = POS_FREE;
1991: assert(chunk->map[run_ind + run_pages - 1].npages == run_pages);
1992: chunk->map[run_ind + run_pages - 1].pos = POS_FREE;
1993:
1994: /*
1995: * Tell the kernel that we don't need the data in this run, but only if
1996: * requested via runtime configuration.
1997: */
1998: if (opt_hint)
1999: madvise(run, size, MADV_FREE);
2000:
2001: /* Try to coalesce with neighboring runs. */
2002: if (run_ind > arena_chunk_header_npages &&
2003: chunk->map[run_ind - 1].pos == POS_FREE) {
2004: unsigned prev_npages;
2005:
2006: /* Coalesce with previous run. */
2007: prev_npages = chunk->map[run_ind - 1].npages;
2008: run_ind -= prev_npages;
2009: assert(chunk->map[run_ind].npages == prev_npages);
2010: assert(chunk->map[run_ind].pos == POS_FREE);
2011: run_pages += prev_npages;
2012:
2013: chunk->map[run_ind].npages = run_pages;
2014: assert(chunk->map[run_ind].pos == POS_FREE);
2015: chunk->map[run_ind + run_pages - 1].npages = run_pages;
2016: assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE);
2017: }
2018:
2019: if (run_ind + run_pages < chunk_npages &&
2020: chunk->map[run_ind + run_pages].pos == POS_FREE) {
2021: unsigned next_npages;
2022:
2023: /* Coalesce with next run. */
2024: next_npages = chunk->map[run_ind + run_pages].npages;
2025: run_pages += next_npages;
2026: assert(chunk->map[run_ind + run_pages - 1].npages ==
2027: next_npages);
2028: assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE);
2029:
2030: chunk->map[run_ind].npages = run_pages;
2031: chunk->map[run_ind].pos = POS_FREE;
2032: chunk->map[run_ind + run_pages - 1].npages = run_pages;
2033: assert(chunk->map[run_ind + run_pages - 1].pos == POS_FREE);
2034: }
2035:
2036: if (chunk->map[run_ind].npages > chunk->max_frun_npages)
2037: chunk->max_frun_npages = chunk->map[run_ind].npages;
2038: if (run_ind < chunk->min_frun_ind)
2039: chunk->min_frun_ind = run_ind;
2040:
2041: /* Deallocate chunk if it is now completely unused. */
2042: if (chunk->pages_used == 0)
2043: arena_chunk_dealloc(arena, chunk);
2044: }
2045:
2046: static arena_run_t *
2047: arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
2048: {
2049: arena_run_t *run;
2050: unsigned i, remainder;
2051:
2052: /* Look for a usable run. */
1.2 ad 2053: /* LINTED */
1.1 ad 2054: if ((run = RB_MIN(arena_run_tree_s, &bin->runs)) != NULL) {
2055: /* run is guaranteed to have available space. */
1.2 ad 2056: /* LINTED */
1.1 ad 2057: RB_REMOVE(arena_run_tree_s, &bin->runs, run);
2058: #ifdef MALLOC_STATS
2059: bin->stats.reruns++;
2060: #endif
2061: return (run);
2062: }
2063: /* No existing runs have any space available. */
2064:
2065: /* Allocate a new run. */
2066: run = arena_run_alloc(arena, bin->run_size);
2067: if (run == NULL)
2068: return (NULL);
2069:
2070: /* Initialize run internals. */
2071: run->bin = bin;
2072:
2073: for (i = 0; i < bin->regs_mask_nelms; i++)
2074: run->regs_mask[i] = UINT_MAX;
2075: remainder = bin->nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1);
2076: if (remainder != 0) {
2077: /* The last element has spare bits that need to be unset. */
2078: run->regs_mask[i] = (UINT_MAX >> ((1 << (SIZEOF_INT_2POW + 3))
2079: - remainder));
2080: }
2081:
2082: run->regs_minelm = 0;
2083:
2084: run->nfree = bin->nregs;
2085: #ifdef MALLOC_DEBUG
2086: run->magic = ARENA_RUN_MAGIC;
2087: #endif
2088:
2089: #ifdef MALLOC_STATS
2090: bin->stats.nruns++;
2091: bin->stats.curruns++;
2092: if (bin->stats.curruns > bin->stats.highruns)
2093: bin->stats.highruns = bin->stats.curruns;
2094: #endif
2095: return (run);
2096: }
2097:
2098: /* bin->runcur must have space available before this function is called. */
2099: static inline void *
2100: arena_bin_malloc_easy(arena_t *arena, arena_bin_t *bin, arena_run_t *run)
2101: {
2102: void *ret;
2103:
2104: assert(run->magic == ARENA_RUN_MAGIC);
2105: assert(run->nfree > 0);
2106:
2107: ret = arena_run_reg_alloc(run, bin);
2108: assert(ret != NULL);
2109: run->nfree--;
2110:
2111: return (ret);
2112: }
2113:
2114: /* Re-fill bin->runcur, then call arena_bin_malloc_easy(). */
2115: static void *
2116: arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
2117: {
2118:
2119: bin->runcur = arena_bin_nonfull_run_get(arena, bin);
2120: if (bin->runcur == NULL)
2121: return (NULL);
2122: assert(bin->runcur->magic == ARENA_RUN_MAGIC);
2123: assert(bin->runcur->nfree > 0);
2124:
2125: return (arena_bin_malloc_easy(arena, bin, bin->runcur));
2126: }
2127:
2128: /*
2129: * Calculate bin->run_size such that it meets the following constraints:
2130: *
2131: * *) bin->run_size >= min_run_size
2132: * *) bin->run_size <= arena_maxclass
2133: * *) bin->run_size <= RUN_MAX_SMALL
2134: * *) run header overhead <= RUN_MAX_OVRHD (or header overhead relaxed).
2135: *
2136: * bin->nregs, bin->regs_mask_nelms, and bin->reg0_offset are
2137: * also calculated here, since these settings are all interdependent.
2138: */
2139: static size_t
2140: arena_bin_run_size_calc(arena_bin_t *bin, size_t min_run_size)
2141: {
2142: size_t try_run_size, good_run_size;
2143: unsigned good_nregs, good_mask_nelms, good_reg0_offset;
2144: unsigned try_nregs, try_mask_nelms, try_reg0_offset;
2145: float max_ovrhd = RUN_MAX_OVRHD;
2146:
2147: assert(min_run_size >= pagesize);
2148: assert(min_run_size <= arena_maxclass);
2149: assert(min_run_size <= RUN_MAX_SMALL);
2150:
2151: /*
2152: * Calculate known-valid settings before entering the run_size
2153: * expansion loop, so that the first part of the loop always copies
2154: * valid settings.
2155: *
2156: * The do..while loop iteratively reduces the number of regions until
2157: * the run header and the regions no longer overlap. A closed formula
2158: * would be quite messy, since there is an interdependency between the
2159: * header's mask length and the number of regions.
2160: */
2161: try_run_size = min_run_size;
1.9 christos 2162: try_nregs = (unsigned)(((try_run_size - sizeof(arena_run_t)) /
2163: bin->reg_size) + 1); /* Counter-act the first line of the loop. */
1.1 ad 2164: do {
2165: try_nregs--;
2166: try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
2167: ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ? 1 : 0);
1.9 christos 2168: try_reg0_offset = (unsigned)(try_run_size -
2169: (try_nregs * bin->reg_size));
1.1 ad 2170: } while (sizeof(arena_run_t) + (sizeof(unsigned) * (try_mask_nelms - 1))
2171: > try_reg0_offset);
2172:
2173: /* run_size expansion loop. */
2174: do {
2175: /*
2176: * Copy valid settings before trying more aggressive settings.
2177: */
2178: good_run_size = try_run_size;
2179: good_nregs = try_nregs;
2180: good_mask_nelms = try_mask_nelms;
2181: good_reg0_offset = try_reg0_offset;
2182:
2183: /* Try more aggressive settings. */
2184: try_run_size += pagesize;
1.9 christos 2185: try_nregs = (unsigned)(((try_run_size - sizeof(arena_run_t)) /
2186: bin->reg_size) + 1); /* Counter-act try_nregs-- in loop. */
1.1 ad 2187: do {
2188: try_nregs--;
2189: try_mask_nelms = (try_nregs >> (SIZEOF_INT_2POW + 3)) +
2190: ((try_nregs & ((1 << (SIZEOF_INT_2POW + 3)) - 1)) ?
2191: 1 : 0);
1.9 christos 2192: try_reg0_offset = (unsigned)(try_run_size - (try_nregs *
2193: bin->reg_size));
1.1 ad 2194: } while (sizeof(arena_run_t) + (sizeof(unsigned) *
2195: (try_mask_nelms - 1)) > try_reg0_offset);
2196: } while (try_run_size <= arena_maxclass && try_run_size <= RUN_MAX_SMALL
2197: && max_ovrhd > RUN_MAX_OVRHD_RELAX / ((float)(bin->reg_size << 3))
2198: && ((float)(try_reg0_offset)) / ((float)(try_run_size)) >
2199: max_ovrhd);
2200:
2201: assert(sizeof(arena_run_t) + (sizeof(unsigned) * (good_mask_nelms - 1))
2202: <= good_reg0_offset);
2203: assert((good_mask_nelms << (SIZEOF_INT_2POW + 3)) >= good_nregs);
2204:
2205: /* Copy final settings. */
2206: bin->run_size = good_run_size;
2207: bin->nregs = good_nregs;
2208: bin->regs_mask_nelms = good_mask_nelms;
2209: bin->reg0_offset = good_reg0_offset;
2210:
2211: return (good_run_size);
2212: }
2213:
2214: static void *
2215: arena_malloc(arena_t *arena, size_t size)
2216: {
2217: void *ret;
2218:
2219: assert(arena != NULL);
2220: assert(arena->magic == ARENA_MAGIC);
2221: assert(size != 0);
2222: assert(QUANTUM_CEILING(size) <= arena_maxclass);
2223:
2224: if (size <= bin_maxclass) {
2225: arena_bin_t *bin;
2226: arena_run_t *run;
2227:
2228: /* Small allocation. */
2229:
2230: if (size < small_min) {
2231: /* Tiny. */
2232: size = pow2_ceil(size);
2233: bin = &arena->bins[ffs((int)(size >> (TINY_MIN_2POW +
2234: 1)))];
2235: #if (!defined(NDEBUG) || defined(MALLOC_STATS))
2236: /*
2237: * Bin calculation is always correct, but we may need
2238: * to fix size for the purposes of assertions and/or
2239: * stats accuracy.
2240: */
2241: if (size < (1 << TINY_MIN_2POW))
2242: size = (1 << TINY_MIN_2POW);
2243: #endif
2244: } else if (size <= small_max) {
2245: /* Quantum-spaced. */
2246: size = QUANTUM_CEILING(size);
2247: bin = &arena->bins[ntbins + (size >> opt_quantum_2pow)
2248: - 1];
2249: } else {
2250: /* Sub-page. */
2251: size = pow2_ceil(size);
2252: bin = &arena->bins[ntbins + nqbins
2253: + (ffs((int)(size >> opt_small_max_2pow)) - 2)];
2254: }
2255: assert(size == bin->reg_size);
2256:
2257: malloc_mutex_lock(&arena->mtx);
2258: if ((run = bin->runcur) != NULL && run->nfree > 0)
2259: ret = arena_bin_malloc_easy(arena, bin, run);
2260: else
2261: ret = arena_bin_malloc_hard(arena, bin);
2262:
2263: if (ret == NULL) {
2264: malloc_mutex_unlock(&arena->mtx);
2265: return (NULL);
2266: }
2267:
2268: #ifdef MALLOC_STATS
2269: bin->stats.nrequests++;
2270: arena->stats.nmalloc_small++;
2271: arena->stats.allocated_small += size;
2272: #endif
2273: } else {
2274: /* Large allocation. */
2275: size = PAGE_CEILING(size);
2276: malloc_mutex_lock(&arena->mtx);
2277: ret = (void *)arena_run_alloc(arena, size);
2278: if (ret == NULL) {
2279: malloc_mutex_unlock(&arena->mtx);
2280: return (NULL);
2281: }
2282: #ifdef MALLOC_STATS
2283: arena->stats.nmalloc_large++;
2284: arena->stats.allocated_large += size;
2285: #endif
2286: }
2287:
2288: malloc_mutex_unlock(&arena->mtx);
2289:
2290: if (opt_junk)
2291: memset(ret, 0xa5, size);
2292: else if (opt_zero)
2293: memset(ret, 0, size);
2294: return (ret);
2295: }
2296:
2297: static inline void
2298: arena_palloc_trim(arena_t *arena, arena_chunk_t *chunk, unsigned pageind,
2299: unsigned npages)
2300: {
2301: unsigned i;
2302:
2303: assert(npages > 0);
2304:
2305: /*
2306: * Modifiy the map such that arena_run_dalloc() sees the run as
2307: * separately allocated.
2308: */
2309: for (i = 0; i < npages; i++) {
2310: chunk->map[pageind + i].npages = npages;
2311: chunk->map[pageind + i].pos = i;
2312: }
2313: arena_run_dalloc(arena, (arena_run_t *)((uintptr_t)chunk + (pageind <<
2314: pagesize_2pow)), npages << pagesize_2pow);
2315: }
2316:
2317: /* Only handles large allocations that require more than page alignment. */
2318: static void *
2319: arena_palloc(arena_t *arena, size_t alignment, size_t size, size_t alloc_size)
2320: {
2321: void *ret;
2322: size_t offset;
2323: arena_chunk_t *chunk;
2324: unsigned pageind, i, npages;
2325:
2326: assert((size & pagesize_mask) == 0);
2327: assert((alignment & pagesize_mask) == 0);
2328:
1.9 christos 2329: npages = (unsigned)(size >> pagesize_2pow);
1.1 ad 2330:
2331: malloc_mutex_lock(&arena->mtx);
2332: ret = (void *)arena_run_alloc(arena, alloc_size);
2333: if (ret == NULL) {
2334: malloc_mutex_unlock(&arena->mtx);
2335: return (NULL);
2336: }
2337:
2338: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ret);
2339:
2340: offset = (uintptr_t)ret & (alignment - 1);
2341: assert((offset & pagesize_mask) == 0);
2342: assert(offset < alloc_size);
2343: if (offset == 0) {
1.9 christos 2344: pageind = (unsigned)(((uintptr_t)ret - (uintptr_t)chunk) >>
1.1 ad 2345: pagesize_2pow);
2346:
2347: /* Update the map for the run to be kept. */
2348: for (i = 0; i < npages; i++) {
2349: chunk->map[pageind + i].npages = npages;
2350: assert(chunk->map[pageind + i].pos == i);
2351: }
2352:
2353: /* Trim trailing space. */
2354: arena_palloc_trim(arena, chunk, pageind + npages,
1.9 christos 2355: (unsigned)((alloc_size - size) >> pagesize_2pow));
1.1 ad 2356: } else {
2357: size_t leadsize, trailsize;
2358:
2359: leadsize = alignment - offset;
2360: ret = (void *)((uintptr_t)ret + leadsize);
1.9 christos 2361: pageind = (unsigned)(((uintptr_t)ret - (uintptr_t)chunk) >>
1.1 ad 2362: pagesize_2pow);
2363:
2364: /* Update the map for the run to be kept. */
2365: for (i = 0; i < npages; i++) {
2366: chunk->map[pageind + i].npages = npages;
2367: chunk->map[pageind + i].pos = i;
2368: }
2369:
2370: /* Trim leading space. */
1.9 christos 2371: arena_palloc_trim(arena, chunk,
2372: (unsigned)(pageind - (leadsize >> pagesize_2pow)),
2373: (unsigned)(leadsize >> pagesize_2pow));
1.1 ad 2374:
2375: trailsize = alloc_size - leadsize - size;
2376: if (trailsize != 0) {
2377: /* Trim trailing space. */
2378: assert(trailsize < alloc_size);
2379: arena_palloc_trim(arena, chunk, pageind + npages,
1.9 christos 2380: (unsigned)(trailsize >> pagesize_2pow));
1.1 ad 2381: }
2382: }
2383:
2384: #ifdef MALLOC_STATS
2385: arena->stats.nmalloc_large++;
2386: arena->stats.allocated_large += size;
2387: #endif
2388: malloc_mutex_unlock(&arena->mtx);
2389:
2390: if (opt_junk)
2391: memset(ret, 0xa5, size);
2392: else if (opt_zero)
2393: memset(ret, 0, size);
2394: return (ret);
2395: }
2396:
2397: /* Return the size of the allocation pointed to by ptr. */
2398: static size_t
2399: arena_salloc(const void *ptr)
2400: {
2401: size_t ret;
2402: arena_chunk_t *chunk;
2403: arena_chunk_map_t *mapelm;
2404: unsigned pageind;
2405:
2406: assert(ptr != NULL);
2407: assert(CHUNK_ADDR2BASE(ptr) != ptr);
2408:
2409: /*
2410: * No arena data structures that we query here can change in a way that
2411: * affects this function, so we don't need to lock.
2412: */
2413: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
1.9 christos 2414: pageind = (unsigned)(((uintptr_t)ptr - (uintptr_t)chunk) >>
2415: pagesize_2pow);
1.1 ad 2416: mapelm = &chunk->map[pageind];
1.10 simonb 2417: if (mapelm->pos != 0 || ptr != (char *)((uintptr_t)chunk) + (pageind <<
2418: pagesize_2pow)) {
2419: arena_run_t *run;
1.1 ad 2420:
2421: pageind -= mapelm->pos;
2422:
1.10 simonb 2423: run = (arena_run_t *)((uintptr_t)chunk + (pageind <<
2424: pagesize_2pow));
1.1 ad 2425: assert(run->magic == ARENA_RUN_MAGIC);
2426: ret = run->bin->reg_size;
2427: } else
2428: ret = mapelm->npages << pagesize_2pow;
2429:
2430: return (ret);
2431: }
2432:
2433: static void *
2434: arena_ralloc(void *ptr, size_t size, size_t oldsize)
2435: {
2436: void *ret;
2437:
2438: /* Avoid moving the allocation if the size class would not change. */
2439: if (size < small_min) {
2440: if (oldsize < small_min &&
2441: ffs((int)(pow2_ceil(size) >> (TINY_MIN_2POW + 1)))
2442: == ffs((int)(pow2_ceil(oldsize) >> (TINY_MIN_2POW + 1))))
2443: goto IN_PLACE;
2444: } else if (size <= small_max) {
2445: if (oldsize >= small_min && oldsize <= small_max &&
2446: (QUANTUM_CEILING(size) >> opt_quantum_2pow)
2447: == (QUANTUM_CEILING(oldsize) >> opt_quantum_2pow))
2448: goto IN_PLACE;
2449: } else {
2450: /*
2451: * We make no attempt to resize runs here, though it would be
2452: * possible to do so.
2453: */
2454: if (oldsize > small_max && PAGE_CEILING(size) == oldsize)
2455: goto IN_PLACE;
2456: }
2457:
2458: /*
2459: * If we get here, then size and oldsize are different enough that we
2460: * need to use a different size class. In that case, fall back to
2461: * allocating new space and copying.
2462: */
2463: ret = arena_malloc(choose_arena(), size);
2464: if (ret == NULL)
2465: return (NULL);
2466:
2467: /* Junk/zero-filling were already done by arena_malloc(). */
2468: if (size < oldsize)
2469: memcpy(ret, ptr, size);
2470: else
2471: memcpy(ret, ptr, oldsize);
2472: idalloc(ptr);
2473: return (ret);
2474: IN_PLACE:
2475: if (opt_junk && size < oldsize)
2476: memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize - size);
2477: else if (opt_zero && size > oldsize)
2478: memset((void *)((uintptr_t)ptr + oldsize), 0, size - oldsize);
2479: return (ptr);
2480: }
2481:
2482: static void
2483: arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr)
2484: {
2485: unsigned pageind;
2486: arena_chunk_map_t *mapelm;
2487: size_t size;
2488:
2489: assert(arena != NULL);
2490: assert(arena->magic == ARENA_MAGIC);
2491: assert(chunk->arena == arena);
2492: assert(ptr != NULL);
2493: assert(CHUNK_ADDR2BASE(ptr) != ptr);
2494:
1.9 christos 2495: pageind = (unsigned)(((uintptr_t)ptr - (uintptr_t)chunk) >>
2496: pagesize_2pow);
1.1 ad 2497: mapelm = &chunk->map[pageind];
1.10 simonb 2498: if (mapelm->pos != 0 || ptr != (char *)((uintptr_t)chunk) + (pageind <<
2499: pagesize_2pow)) {
2500: arena_run_t *run;
1.1 ad 2501: arena_bin_t *bin;
2502:
2503: /* Small allocation. */
2504:
2505: pageind -= mapelm->pos;
2506:
1.10 simonb 2507: run = (arena_run_t *)((uintptr_t)chunk + (pageind <<
2508: pagesize_2pow));
1.1 ad 2509: assert(run->magic == ARENA_RUN_MAGIC);
2510: bin = run->bin;
2511: size = bin->reg_size;
2512:
2513: if (opt_junk)
2514: memset(ptr, 0x5a, size);
2515:
2516: malloc_mutex_lock(&arena->mtx);
2517: arena_run_reg_dalloc(run, bin, ptr, size);
2518: run->nfree++;
2519:
2520: if (run->nfree == bin->nregs) {
2521: /* Deallocate run. */
2522: if (run == bin->runcur)
2523: bin->runcur = NULL;
2524: else if (bin->nregs != 1) {
2525: /*
2526: * This block's conditional is necessary because
2527: * if the run only contains one region, then it
2528: * never gets inserted into the non-full runs
2529: * tree.
2530: */
1.2 ad 2531: /* LINTED */
1.1 ad 2532: RB_REMOVE(arena_run_tree_s, &bin->runs, run);
2533: }
2534: #ifdef MALLOC_DEBUG
2535: run->magic = 0;
2536: #endif
2537: arena_run_dalloc(arena, run, bin->run_size);
2538: #ifdef MALLOC_STATS
2539: bin->stats.curruns--;
2540: #endif
2541: } else if (run->nfree == 1 && run != bin->runcur) {
2542: /*
2543: * Make sure that bin->runcur always refers to the
2544: * lowest non-full run, if one exists.
2545: */
2546: if (bin->runcur == NULL)
2547: bin->runcur = run;
2548: else if ((uintptr_t)run < (uintptr_t)bin->runcur) {
2549: /* Switch runcur. */
2550: if (bin->runcur->nfree > 0) {
2551: /* Insert runcur. */
1.2 ad 2552: /* LINTED */
1.1 ad 2553: RB_INSERT(arena_run_tree_s, &bin->runs,
2554: bin->runcur);
2555: }
2556: bin->runcur = run;
1.2 ad 2557: } else {
2558: /* LINTED */
1.1 ad 2559: RB_INSERT(arena_run_tree_s, &bin->runs, run);
1.2 ad 2560: }
1.1 ad 2561: }
2562: #ifdef MALLOC_STATS
2563: arena->stats.allocated_small -= size;
2564: arena->stats.ndalloc_small++;
2565: #endif
2566: } else {
2567: /* Large allocation. */
2568:
2569: size = mapelm->npages << pagesize_2pow;
2570: assert((((uintptr_t)ptr) & pagesize_mask) == 0);
2571:
2572: if (opt_junk)
2573: memset(ptr, 0x5a, size);
2574:
2575: malloc_mutex_lock(&arena->mtx);
2576: arena_run_dalloc(arena, (arena_run_t *)ptr, size);
2577: #ifdef MALLOC_STATS
2578: arena->stats.allocated_large -= size;
2579: arena->stats.ndalloc_large++;
2580: #endif
2581: }
2582:
2583: malloc_mutex_unlock(&arena->mtx);
2584: }
2585:
2586: static bool
2587: arena_new(arena_t *arena)
2588: {
2589: unsigned i;
2590: arena_bin_t *bin;
1.2 ad 2591: size_t prev_run_size;
1.1 ad 2592:
2593: malloc_mutex_init(&arena->mtx);
2594:
2595: #ifdef MALLOC_STATS
2596: memset(&arena->stats, 0, sizeof(arena_stats_t));
2597: #endif
2598:
2599: /* Initialize chunks. */
2600: RB_INIT(&arena->chunks);
2601: arena->spare = NULL;
2602:
2603: /* Initialize bins. */
2604: prev_run_size = pagesize;
2605:
2606: /* (2^n)-spaced tiny bins. */
2607: for (i = 0; i < ntbins; i++) {
2608: bin = &arena->bins[i];
2609: bin->runcur = NULL;
2610: RB_INIT(&bin->runs);
2611:
2612: bin->reg_size = (1 << (TINY_MIN_2POW + i));
2613: prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
2614:
2615: #ifdef MALLOC_STATS
2616: memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2617: #endif
2618: }
2619:
2620: /* Quantum-spaced bins. */
2621: for (; i < ntbins + nqbins; i++) {
2622: bin = &arena->bins[i];
2623: bin->runcur = NULL;
2624: RB_INIT(&bin->runs);
2625:
2626: bin->reg_size = quantum * (i - ntbins + 1);
1.2 ad 2627: /*
1.1 ad 2628: pow2_size = pow2_ceil(quantum * (i - ntbins + 1));
1.2 ad 2629: */
1.1 ad 2630: prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
2631:
2632: #ifdef MALLOC_STATS
2633: memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2634: #endif
2635: }
2636:
2637: /* (2^n)-spaced sub-page bins. */
2638: for (; i < ntbins + nqbins + nsbins; i++) {
2639: bin = &arena->bins[i];
2640: bin->runcur = NULL;
2641: RB_INIT(&bin->runs);
2642:
2643: bin->reg_size = (small_max << (i - (ntbins + nqbins) + 1));
2644:
2645: prev_run_size = arena_bin_run_size_calc(bin, prev_run_size);
2646:
2647: #ifdef MALLOC_STATS
2648: memset(&bin->stats, 0, sizeof(malloc_bin_stats_t));
2649: #endif
2650: }
2651:
2652: #ifdef MALLOC_DEBUG
2653: arena->magic = ARENA_MAGIC;
2654: #endif
2655:
2656: return (false);
2657: }
2658:
2659: /* Create a new arena and insert it into the arenas array at index ind. */
2660: static arena_t *
2661: arenas_extend(unsigned ind)
2662: {
2663: arena_t *ret;
2664:
2665: /* Allocate enough space for trailing bins. */
2666: ret = (arena_t *)base_alloc(sizeof(arena_t)
2667: + (sizeof(arena_bin_t) * (ntbins + nqbins + nsbins - 1)));
2668: if (ret != NULL && arena_new(ret) == false) {
2669: arenas[ind] = ret;
2670: return (ret);
2671: }
2672: /* Only reached if there is an OOM error. */
2673:
2674: /*
2675: * OOM here is quite inconvenient to propagate, since dealing with it
2676: * would require a check for failure in the fast path. Instead, punt
2677: * by using arenas[0]. In practice, this is an extremely unlikely
2678: * failure.
2679: */
1.16 christos 2680: _malloc_message(getprogname(),
1.1 ad 2681: ": (malloc) Error initializing arena\n", "", "");
2682: if (opt_abort)
2683: abort();
2684:
2685: return (arenas[0]);
2686: }
2687:
2688: /*
2689: * End arena.
2690: */
2691: /******************************************************************************/
2692: /*
2693: * Begin general internal functions.
2694: */
2695:
2696: static void *
2697: huge_malloc(size_t size)
2698: {
2699: void *ret;
2700: size_t csize;
2701: chunk_node_t *node;
2702:
2703: /* Allocate one or more contiguous chunks for this request. */
2704:
2705: csize = CHUNK_CEILING(size);
2706: if (csize == 0) {
2707: /* size is large enough to cause size_t wrap-around. */
2708: return (NULL);
2709: }
2710:
2711: /* Allocate a chunk node with which to track the chunk. */
2712: node = base_chunk_node_alloc();
2713: if (node == NULL)
2714: return (NULL);
2715:
2716: ret = chunk_alloc(csize);
2717: if (ret == NULL) {
2718: base_chunk_node_dealloc(node);
2719: return (NULL);
2720: }
2721:
2722: /* Insert node into huge. */
2723: node->chunk = ret;
2724: node->size = csize;
2725:
2726: malloc_mutex_lock(&chunks_mtx);
2727: RB_INSERT(chunk_tree_s, &huge, node);
2728: #ifdef MALLOC_STATS
2729: huge_nmalloc++;
2730: huge_allocated += csize;
2731: #endif
2732: malloc_mutex_unlock(&chunks_mtx);
2733:
2734: if (opt_junk)
2735: memset(ret, 0xa5, csize);
2736: else if (opt_zero)
2737: memset(ret, 0, csize);
2738:
2739: return (ret);
2740: }
2741:
2742: /* Only handles large allocations that require more than chunk alignment. */
2743: static void *
2744: huge_palloc(size_t alignment, size_t size)
2745: {
2746: void *ret;
2747: size_t alloc_size, chunk_size, offset;
2748: chunk_node_t *node;
2749:
2750: /*
2751: * This allocation requires alignment that is even larger than chunk
2752: * alignment. This means that huge_malloc() isn't good enough.
2753: *
2754: * Allocate almost twice as many chunks as are demanded by the size or
2755: * alignment, in order to assure the alignment can be achieved, then
2756: * unmap leading and trailing chunks.
2757: */
2758: assert(alignment >= chunksize);
2759:
2760: chunk_size = CHUNK_CEILING(size);
2761:
2762: if (size >= alignment)
2763: alloc_size = chunk_size + alignment - chunksize;
2764: else
2765: alloc_size = (alignment << 1) - chunksize;
2766:
2767: /* Allocate a chunk node with which to track the chunk. */
2768: node = base_chunk_node_alloc();
2769: if (node == NULL)
2770: return (NULL);
2771:
2772: ret = chunk_alloc(alloc_size);
2773: if (ret == NULL) {
2774: base_chunk_node_dealloc(node);
2775: return (NULL);
2776: }
2777:
2778: offset = (uintptr_t)ret & (alignment - 1);
2779: assert((offset & chunksize_mask) == 0);
2780: assert(offset < alloc_size);
2781: if (offset == 0) {
2782: /* Trim trailing space. */
2783: chunk_dealloc((void *)((uintptr_t)ret + chunk_size), alloc_size
2784: - chunk_size);
2785: } else {
2786: size_t trailsize;
2787:
2788: /* Trim leading space. */
2789: chunk_dealloc(ret, alignment - offset);
2790:
2791: ret = (void *)((uintptr_t)ret + (alignment - offset));
2792:
2793: trailsize = alloc_size - (alignment - offset) - chunk_size;
2794: if (trailsize != 0) {
2795: /* Trim trailing space. */
2796: assert(trailsize < alloc_size);
2797: chunk_dealloc((void *)((uintptr_t)ret + chunk_size),
2798: trailsize);
2799: }
2800: }
2801:
2802: /* Insert node into huge. */
2803: node->chunk = ret;
2804: node->size = chunk_size;
2805:
2806: malloc_mutex_lock(&chunks_mtx);
2807: RB_INSERT(chunk_tree_s, &huge, node);
2808: #ifdef MALLOC_STATS
2809: huge_nmalloc++;
2810: huge_allocated += chunk_size;
2811: #endif
2812: malloc_mutex_unlock(&chunks_mtx);
2813:
2814: if (opt_junk)
2815: memset(ret, 0xa5, chunk_size);
2816: else if (opt_zero)
2817: memset(ret, 0, chunk_size);
2818:
2819: return (ret);
2820: }
2821:
2822: static void *
2823: huge_ralloc(void *ptr, size_t size, size_t oldsize)
2824: {
2825: void *ret;
2826:
2827: /* Avoid moving the allocation if the size class would not change. */
2828: if (oldsize > arena_maxclass &&
2829: CHUNK_CEILING(size) == CHUNK_CEILING(oldsize)) {
2830: if (opt_junk && size < oldsize) {
2831: memset((void *)((uintptr_t)ptr + size), 0x5a, oldsize
2832: - size);
2833: } else if (opt_zero && size > oldsize) {
2834: memset((void *)((uintptr_t)ptr + oldsize), 0, size
2835: - oldsize);
2836: }
2837: return (ptr);
2838: }
2839:
1.8 yamt 2840: if (CHUNK_ADDR2BASE(ptr) == ptr
2841: #ifdef USE_BRK
2842: && ((uintptr_t)ptr < (uintptr_t)brk_base
2843: || (uintptr_t)ptr >= (uintptr_t)brk_max)
2844: #endif
2845: ) {
2846: chunk_node_t *node, key;
2847: void *newptr;
2848: size_t oldcsize;
2849: size_t newcsize;
2850:
2851: newcsize = CHUNK_CEILING(size);
2852: oldcsize = CHUNK_CEILING(oldsize);
2853: assert(oldcsize != newcsize);
2854: if (newcsize == 0) {
2855: /* size_t wrap-around */
2856: return (NULL);
2857: }
1.19.12.1! matt 2858:
! 2859: /*
! 2860: * Remove the old region from the tree now. If mremap()
! 2861: * returns the region to the system, other thread may
! 2862: * map it for same huge allocation and insert it to the
! 2863: * tree before we acquire the mutex lock again.
! 2864: */
! 2865: malloc_mutex_lock(&chunks_mtx);
! 2866: key.chunk = __DECONST(void *, ptr);
! 2867: /* LINTED */
! 2868: node = RB_FIND(chunk_tree_s, &huge, &key);
! 2869: assert(node != NULL);
! 2870: assert(node->chunk == ptr);
! 2871: assert(node->size == oldcsize);
! 2872: RB_REMOVE(chunk_tree_s, &huge, node);
! 2873: malloc_mutex_unlock(&chunks_mtx);
! 2874:
1.8 yamt 2875: newptr = mremap(ptr, oldcsize, NULL, newcsize,
2876: MAP_ALIGNED(chunksize_2pow));
1.19.12.1! matt 2877: if (newptr == MAP_FAILED) {
! 2878: /* We still own the old region. */
! 2879: malloc_mutex_lock(&chunks_mtx);
! 2880: RB_INSERT(chunk_tree_s, &huge, node);
! 2881: malloc_mutex_unlock(&chunks_mtx);
! 2882: } else {
1.8 yamt 2883: assert(CHUNK_ADDR2BASE(newptr) == newptr);
2884:
1.19.12.1! matt 2885: /* Insert new or resized old region. */
1.8 yamt 2886: malloc_mutex_lock(&chunks_mtx);
2887: node->size = newcsize;
1.19.12.1! matt 2888: node->chunk = newptr;
! 2889: RB_INSERT(chunk_tree_s, &huge, node);
1.8 yamt 2890: #ifdef MALLOC_STATS
2891: huge_nralloc++;
2892: huge_allocated += newcsize - oldcsize;
2893: if (newcsize > oldcsize) {
2894: stats_chunks.curchunks +=
2895: (newcsize - oldcsize) / chunksize;
2896: if (stats_chunks.curchunks >
2897: stats_chunks.highchunks)
2898: stats_chunks.highchunks =
2899: stats_chunks.curchunks;
2900: } else {
2901: stats_chunks.curchunks -=
2902: (oldcsize - newcsize) / chunksize;
2903: }
2904: #endif
2905: malloc_mutex_unlock(&chunks_mtx);
2906:
2907: if (opt_junk && size < oldsize) {
2908: memset((void *)((uintptr_t)newptr + size), 0x5a,
2909: newcsize - size);
2910: } else if (opt_zero && size > oldsize) {
2911: memset((void *)((uintptr_t)newptr + oldsize), 0,
2912: size - oldsize);
2913: }
2914: return (newptr);
2915: }
2916: }
2917:
1.1 ad 2918: /*
2919: * If we get here, then size and oldsize are different enough that we
2920: * need to use a different size class. In that case, fall back to
2921: * allocating new space and copying.
2922: */
2923: ret = huge_malloc(size);
2924: if (ret == NULL)
2925: return (NULL);
2926:
2927: if (CHUNK_ADDR2BASE(ptr) == ptr) {
2928: /* The old allocation is a chunk. */
2929: if (size < oldsize)
2930: memcpy(ret, ptr, size);
2931: else
2932: memcpy(ret, ptr, oldsize);
2933: } else {
2934: /* The old allocation is a region. */
2935: assert(oldsize < size);
2936: memcpy(ret, ptr, oldsize);
2937: }
2938: idalloc(ptr);
2939: return (ret);
2940: }
2941:
2942: static void
2943: huge_dalloc(void *ptr)
2944: {
2945: chunk_node_t key;
2946: chunk_node_t *node;
2947:
2948: malloc_mutex_lock(&chunks_mtx);
2949:
2950: /* Extract from tree of huge allocations. */
2951: key.chunk = ptr;
1.2 ad 2952: /* LINTED */
1.1 ad 2953: node = RB_FIND(chunk_tree_s, &huge, &key);
2954: assert(node != NULL);
2955: assert(node->chunk == ptr);
1.2 ad 2956: /* LINTED */
1.1 ad 2957: RB_REMOVE(chunk_tree_s, &huge, node);
2958:
2959: #ifdef MALLOC_STATS
2960: huge_ndalloc++;
2961: huge_allocated -= node->size;
2962: #endif
2963:
2964: malloc_mutex_unlock(&chunks_mtx);
2965:
2966: /* Unmap chunk. */
2967: #ifdef USE_BRK
2968: if (opt_junk)
2969: memset(node->chunk, 0x5a, node->size);
2970: #endif
2971: chunk_dealloc(node->chunk, node->size);
2972:
2973: base_chunk_node_dealloc(node);
2974: }
2975:
2976: static void *
2977: imalloc(size_t size)
2978: {
2979: void *ret;
2980:
2981: assert(size != 0);
2982:
2983: if (size <= arena_maxclass)
2984: ret = arena_malloc(choose_arena(), size);
2985: else
2986: ret = huge_malloc(size);
2987:
2988: return (ret);
2989: }
2990:
2991: static void *
2992: ipalloc(size_t alignment, size_t size)
2993: {
2994: void *ret;
2995: size_t ceil_size;
2996:
2997: /*
2998: * Round size up to the nearest multiple of alignment.
2999: *
3000: * This done, we can take advantage of the fact that for each small
3001: * size class, every object is aligned at the smallest power of two
3002: * that is non-zero in the base two representation of the size. For
3003: * example:
3004: *
3005: * Size | Base 2 | Minimum alignment
3006: * -----+----------+------------------
3007: * 96 | 1100000 | 32
3008: * 144 | 10100000 | 32
3009: * 192 | 11000000 | 64
3010: *
3011: * Depending on runtime settings, it is possible that arena_malloc()
3012: * will further round up to a power of two, but that never causes
3013: * correctness issues.
3014: */
3015: ceil_size = (size + (alignment - 1)) & (-alignment);
3016: /*
3017: * (ceil_size < size) protects against the combination of maximal
3018: * alignment and size greater than maximal alignment.
3019: */
3020: if (ceil_size < size) {
3021: /* size_t overflow. */
3022: return (NULL);
3023: }
3024:
3025: if (ceil_size <= pagesize || (alignment <= pagesize
3026: && ceil_size <= arena_maxclass))
3027: ret = arena_malloc(choose_arena(), ceil_size);
3028: else {
3029: size_t run_size;
3030:
3031: /*
3032: * We can't achieve sub-page alignment, so round up alignment
3033: * permanently; it makes later calculations simpler.
3034: */
3035: alignment = PAGE_CEILING(alignment);
3036: ceil_size = PAGE_CEILING(size);
3037: /*
3038: * (ceil_size < size) protects against very large sizes within
3039: * pagesize of SIZE_T_MAX.
3040: *
3041: * (ceil_size + alignment < ceil_size) protects against the
3042: * combination of maximal alignment and ceil_size large enough
3043: * to cause overflow. This is similar to the first overflow
3044: * check above, but it needs to be repeated due to the new
3045: * ceil_size value, which may now be *equal* to maximal
3046: * alignment, whereas before we only detected overflow if the
3047: * original size was *greater* than maximal alignment.
3048: */
3049: if (ceil_size < size || ceil_size + alignment < ceil_size) {
3050: /* size_t overflow. */
3051: return (NULL);
3052: }
3053:
3054: /*
3055: * Calculate the size of the over-size run that arena_palloc()
3056: * would need to allocate in order to guarantee the alignment.
3057: */
3058: if (ceil_size >= alignment)
3059: run_size = ceil_size + alignment - pagesize;
3060: else {
3061: /*
3062: * It is possible that (alignment << 1) will cause
3063: * overflow, but it doesn't matter because we also
3064: * subtract pagesize, which in the case of overflow
3065: * leaves us with a very large run_size. That causes
3066: * the first conditional below to fail, which means
3067: * that the bogus run_size value never gets used for
3068: * anything important.
3069: */
3070: run_size = (alignment << 1) - pagesize;
3071: }
3072:
3073: if (run_size <= arena_maxclass) {
3074: ret = arena_palloc(choose_arena(), alignment, ceil_size,
3075: run_size);
3076: } else if (alignment <= chunksize)
3077: ret = huge_malloc(ceil_size);
3078: else
3079: ret = huge_palloc(alignment, ceil_size);
3080: }
3081:
3082: assert(((uintptr_t)ret & (alignment - 1)) == 0);
3083: return (ret);
3084: }
3085:
3086: static void *
3087: icalloc(size_t size)
3088: {
3089: void *ret;
3090:
3091: if (size <= arena_maxclass) {
3092: ret = arena_malloc(choose_arena(), size);
3093: if (ret == NULL)
3094: return (NULL);
3095: memset(ret, 0, size);
3096: } else {
3097: /*
3098: * The virtual memory system provides zero-filled pages, so
3099: * there is no need to do so manually, unless opt_junk is
3100: * enabled, in which case huge_malloc() fills huge allocations
3101: * with junk.
3102: */
3103: ret = huge_malloc(size);
3104: if (ret == NULL)
3105: return (NULL);
3106:
3107: if (opt_junk)
3108: memset(ret, 0, size);
3109: #ifdef USE_BRK
3110: else if ((uintptr_t)ret >= (uintptr_t)brk_base
3111: && (uintptr_t)ret < (uintptr_t)brk_max) {
3112: /*
3113: * This may be a re-used brk chunk. Therefore, zero
3114: * the memory.
3115: */
3116: memset(ret, 0, size);
3117: }
3118: #endif
3119: }
3120:
3121: return (ret);
3122: }
3123:
3124: static size_t
3125: isalloc(const void *ptr)
3126: {
3127: size_t ret;
3128: arena_chunk_t *chunk;
3129:
3130: assert(ptr != NULL);
3131:
3132: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3133: if (chunk != ptr) {
3134: /* Region. */
3135: assert(chunk->arena->magic == ARENA_MAGIC);
3136:
3137: ret = arena_salloc(ptr);
3138: } else {
3139: chunk_node_t *node, key;
3140:
3141: /* Chunk (huge allocation). */
3142:
3143: malloc_mutex_lock(&chunks_mtx);
3144:
3145: /* Extract from tree of huge allocations. */
3146: key.chunk = __DECONST(void *, ptr);
1.2 ad 3147: /* LINTED */
1.1 ad 3148: node = RB_FIND(chunk_tree_s, &huge, &key);
3149: assert(node != NULL);
3150:
3151: ret = node->size;
3152:
3153: malloc_mutex_unlock(&chunks_mtx);
3154: }
3155:
3156: return (ret);
3157: }
3158:
3159: static void *
3160: iralloc(void *ptr, size_t size)
3161: {
3162: void *ret;
3163: size_t oldsize;
3164:
3165: assert(ptr != NULL);
3166: assert(size != 0);
3167:
3168: oldsize = isalloc(ptr);
3169:
3170: if (size <= arena_maxclass)
3171: ret = arena_ralloc(ptr, size, oldsize);
3172: else
3173: ret = huge_ralloc(ptr, size, oldsize);
3174:
3175: return (ret);
3176: }
3177:
3178: static void
3179: idalloc(void *ptr)
3180: {
3181: arena_chunk_t *chunk;
3182:
3183: assert(ptr != NULL);
3184:
3185: chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
3186: if (chunk != ptr) {
3187: /* Region. */
3188: arena_dalloc(chunk->arena, chunk, ptr);
3189: } else
3190: huge_dalloc(ptr);
3191: }
3192:
3193: static void
3194: malloc_print_stats(void)
3195: {
3196:
3197: if (opt_print_stats) {
3198: char s[UMAX2S_BUFSIZE];
3199: _malloc_message("___ Begin malloc statistics ___\n", "", "",
3200: "");
3201: _malloc_message("Assertions ",
3202: #ifdef NDEBUG
3203: "disabled",
3204: #else
3205: "enabled",
3206: #endif
3207: "\n", "");
3208: _malloc_message("Boolean MALLOC_OPTIONS: ",
3209: opt_abort ? "A" : "a",
3210: opt_junk ? "J" : "j",
3211: opt_hint ? "H" : "h");
3212: _malloc_message(opt_utrace ? "PU" : "Pu",
3213: opt_sysv ? "V" : "v",
3214: opt_xmalloc ? "X" : "x",
3215: opt_zero ? "Z\n" : "z\n");
3216:
3217: _malloc_message("CPUs: ", umax2s(ncpus, s), "\n", "");
3218: _malloc_message("Max arenas: ", umax2s(narenas, s), "\n", "");
3219: _malloc_message("Pointer size: ", umax2s(sizeof(void *), s),
3220: "\n", "");
3221: _malloc_message("Quantum size: ", umax2s(quantum, s), "\n", "");
3222: _malloc_message("Max small size: ", umax2s(small_max, s), "\n",
3223: "");
3224:
3225: _malloc_message("Chunk size: ", umax2s(chunksize, s), "", "");
3226: _malloc_message(" (2^", umax2s(opt_chunk_2pow, s), ")\n", "");
3227:
3228: #ifdef MALLOC_STATS
3229: {
3230: size_t allocated, mapped;
3231: unsigned i;
3232: arena_t *arena;
3233:
3234: /* Calculate and print allocated/mapped stats. */
3235:
3236: /* arenas. */
3237: for (i = 0, allocated = 0; i < narenas; i++) {
3238: if (arenas[i] != NULL) {
3239: malloc_mutex_lock(&arenas[i]->mtx);
3240: allocated +=
3241: arenas[i]->stats.allocated_small;
3242: allocated +=
3243: arenas[i]->stats.allocated_large;
3244: malloc_mutex_unlock(&arenas[i]->mtx);
3245: }
3246: }
3247:
3248: /* huge/base. */
3249: malloc_mutex_lock(&chunks_mtx);
3250: allocated += huge_allocated;
3251: mapped = stats_chunks.curchunks * chunksize;
3252: malloc_mutex_unlock(&chunks_mtx);
3253:
3254: malloc_mutex_lock(&base_mtx);
3255: mapped += base_mapped;
3256: malloc_mutex_unlock(&base_mtx);
3257:
3258: malloc_printf("Allocated: %zu, mapped: %zu\n",
3259: allocated, mapped);
3260:
3261: /* Print chunk stats. */
3262: {
3263: chunk_stats_t chunks_stats;
3264:
3265: malloc_mutex_lock(&chunks_mtx);
3266: chunks_stats = stats_chunks;
3267: malloc_mutex_unlock(&chunks_mtx);
3268:
3269: malloc_printf("chunks: nchunks "
3270: "highchunks curchunks\n");
3271: malloc_printf(" %13llu%13lu%13lu\n",
3272: chunks_stats.nchunks,
3273: chunks_stats.highchunks,
3274: chunks_stats.curchunks);
3275: }
3276:
3277: /* Print chunk stats. */
3278: malloc_printf(
1.8 yamt 3279: "huge: nmalloc ndalloc "
3280: "nralloc allocated\n");
3281: malloc_printf(" %12llu %12llu %12llu %12zu\n",
3282: huge_nmalloc, huge_ndalloc, huge_nralloc,
3283: huge_allocated);
1.1 ad 3284:
3285: /* Print stats for each arena. */
3286: for (i = 0; i < narenas; i++) {
3287: arena = arenas[i];
3288: if (arena != NULL) {
3289: malloc_printf(
1.2 ad 3290: "\narenas[%u] @ %p\n", i, arena);
1.1 ad 3291: malloc_mutex_lock(&arena->mtx);
3292: stats_print(arena);
3293: malloc_mutex_unlock(&arena->mtx);
3294: }
3295: }
3296: }
3297: #endif /* #ifdef MALLOC_STATS */
3298: _malloc_message("--- End malloc statistics ---\n", "", "", "");
3299: }
3300: }
3301:
3302: /*
3303: * FreeBSD's pthreads implementation calls malloc(3), so the malloc
3304: * implementation has to take pains to avoid infinite recursion during
3305: * initialization.
3306: */
3307: static inline bool
3308: malloc_init(void)
3309: {
3310:
3311: if (malloc_initialized == false)
3312: return (malloc_init_hard());
3313:
3314: return (false);
3315: }
3316:
3317: static bool
3318: malloc_init_hard(void)
3319: {
3320: unsigned i, j;
1.9 christos 3321: ssize_t linklen;
1.1 ad 3322: char buf[PATH_MAX + 1];
1.2 ad 3323: const char *opts = "";
1.1 ad 3324:
3325: malloc_mutex_lock(&init_lock);
3326: if (malloc_initialized) {
3327: /*
3328: * Another thread initialized the allocator before this one
3329: * acquired init_lock.
3330: */
3331: malloc_mutex_unlock(&init_lock);
3332: return (false);
3333: }
3334:
3335: /* Get number of CPUs. */
3336: {
3337: int mib[2];
3338: size_t len;
3339:
3340: mib[0] = CTL_HW;
3341: mib[1] = HW_NCPU;
3342: len = sizeof(ncpus);
3343: if (sysctl(mib, 2, &ncpus, &len, (void *) 0, 0) == -1) {
3344: /* Error. */
3345: ncpus = 1;
3346: }
3347: }
3348:
3349: /* Get page size. */
3350: {
3351: long result;
3352:
3353: result = sysconf(_SC_PAGESIZE);
3354: assert(result != -1);
3355: pagesize = (unsigned) result;
3356:
3357: /*
3358: * We assume that pagesize is a power of 2 when calculating
3359: * pagesize_mask and pagesize_2pow.
3360: */
3361: assert(((result - 1) & result) == 0);
3362: pagesize_mask = result - 1;
3363: pagesize_2pow = ffs((int)result) - 1;
3364: }
3365:
3366: for (i = 0; i < 3; i++) {
3367: /* Get runtime configuration. */
3368: switch (i) {
3369: case 0:
3370: if ((linklen = readlink("/etc/malloc.conf", buf,
3371: sizeof(buf) - 1)) != -1) {
3372: /*
3373: * Use the contents of the "/etc/malloc.conf"
3374: * symbolic link's name.
3375: */
3376: buf[linklen] = '\0';
3377: opts = buf;
3378: } else {
3379: /* No configuration specified. */
3380: buf[0] = '\0';
3381: opts = buf;
3382: }
3383: break;
3384: case 1:
1.18 ad 3385: if ((opts = getenv("MALLOC_OPTIONS")) != NULL &&
3386: issetugid() == 0) {
1.1 ad 3387: /*
3388: * Do nothing; opts is already initialized to
3389: * the value of the MALLOC_OPTIONS environment
3390: * variable.
3391: */
3392: } else {
3393: /* No configuration specified. */
3394: buf[0] = '\0';
3395: opts = buf;
3396: }
3397: break;
3398: case 2:
3399: if (_malloc_options != NULL) {
3400: /*
3401: * Use options that were compiled into the program.
3402: */
3403: opts = _malloc_options;
3404: } else {
3405: /* No configuration specified. */
3406: buf[0] = '\0';
3407: opts = buf;
3408: }
3409: break;
3410: default:
3411: /* NOTREACHED */
1.7 yamt 3412: /* LINTED */
1.1 ad 3413: assert(false);
3414: }
3415:
3416: for (j = 0; opts[j] != '\0'; j++) {
3417: switch (opts[j]) {
3418: case 'a':
3419: opt_abort = false;
3420: break;
3421: case 'A':
3422: opt_abort = true;
3423: break;
3424: case 'h':
3425: opt_hint = false;
3426: break;
3427: case 'H':
3428: opt_hint = true;
3429: break;
3430: case 'j':
3431: opt_junk = false;
3432: break;
3433: case 'J':
3434: opt_junk = true;
3435: break;
3436: case 'k':
3437: /*
3438: * Chunks always require at least one header
3439: * page, so chunks can never be smaller than
3440: * two pages.
3441: */
3442: if (opt_chunk_2pow > pagesize_2pow + 1)
3443: opt_chunk_2pow--;
3444: break;
3445: case 'K':
3446: /*
3447: * There must be fewer pages in a chunk than
3448: * can be recorded by the pos field of
3449: * arena_chunk_map_t, in order to make POS_FREE
3450: * special.
3451: */
3452: if (opt_chunk_2pow - pagesize_2pow
3453: < (sizeof(uint32_t) << 3) - 1)
3454: opt_chunk_2pow++;
3455: break;
3456: case 'n':
3457: opt_narenas_lshift--;
3458: break;
3459: case 'N':
3460: opt_narenas_lshift++;
3461: break;
3462: case 'p':
3463: opt_print_stats = false;
3464: break;
3465: case 'P':
3466: opt_print_stats = true;
3467: break;
3468: case 'q':
3469: if (opt_quantum_2pow > QUANTUM_2POW_MIN)
3470: opt_quantum_2pow--;
3471: break;
3472: case 'Q':
3473: if (opt_quantum_2pow < pagesize_2pow - 1)
3474: opt_quantum_2pow++;
3475: break;
3476: case 's':
3477: if (opt_small_max_2pow > QUANTUM_2POW_MIN)
3478: opt_small_max_2pow--;
3479: break;
3480: case 'S':
3481: if (opt_small_max_2pow < pagesize_2pow - 1)
3482: opt_small_max_2pow++;
3483: break;
3484: case 'u':
3485: opt_utrace = false;
3486: break;
3487: case 'U':
3488: opt_utrace = true;
3489: break;
3490: case 'v':
3491: opt_sysv = false;
3492: break;
3493: case 'V':
3494: opt_sysv = true;
3495: break;
3496: case 'x':
3497: opt_xmalloc = false;
3498: break;
3499: case 'X':
3500: opt_xmalloc = true;
3501: break;
3502: case 'z':
3503: opt_zero = false;
3504: break;
3505: case 'Z':
3506: opt_zero = true;
3507: break;
3508: default: {
3509: char cbuf[2];
3510:
3511: cbuf[0] = opts[j];
3512: cbuf[1] = '\0';
1.16 christos 3513: _malloc_message(getprogname(),
1.1 ad 3514: ": (malloc) Unsupported character in "
3515: "malloc options: '", cbuf, "'\n");
3516: }
3517: }
3518: }
3519: }
3520:
3521: /* Take care to call atexit() only once. */
3522: if (opt_print_stats) {
3523: /* Print statistics at exit. */
3524: atexit(malloc_print_stats);
3525: }
3526:
3527: /* Set variables according to the value of opt_small_max_2pow. */
3528: if (opt_small_max_2pow < opt_quantum_2pow)
3529: opt_small_max_2pow = opt_quantum_2pow;
3530: small_max = (1 << opt_small_max_2pow);
3531:
3532: /* Set bin-related variables. */
3533: bin_maxclass = (pagesize >> 1);
3534: assert(opt_quantum_2pow >= TINY_MIN_2POW);
1.9 christos 3535: ntbins = (unsigned)(opt_quantum_2pow - TINY_MIN_2POW);
1.1 ad 3536: assert(ntbins <= opt_quantum_2pow);
1.9 christos 3537: nqbins = (unsigned)(small_max >> opt_quantum_2pow);
3538: nsbins = (unsigned)(pagesize_2pow - opt_small_max_2pow - 1);
1.1 ad 3539:
3540: /* Set variables according to the value of opt_quantum_2pow. */
3541: quantum = (1 << opt_quantum_2pow);
3542: quantum_mask = quantum - 1;
3543: if (ntbins > 0)
3544: small_min = (quantum >> 1) + 1;
3545: else
3546: small_min = 1;
3547: assert(small_min <= quantum);
3548:
3549: /* Set variables according to the value of opt_chunk_2pow. */
3550: chunksize = (1LU << opt_chunk_2pow);
3551: chunksize_mask = chunksize - 1;
1.9 christos 3552: chunksize_2pow = (unsigned)opt_chunk_2pow;
3553: chunk_npages = (unsigned)(chunksize >> pagesize_2pow);
1.1 ad 3554: {
3555: unsigned header_size;
3556:
1.9 christos 3557: header_size = (unsigned)(sizeof(arena_chunk_t) +
3558: (sizeof(arena_chunk_map_t) * (chunk_npages - 1)));
1.1 ad 3559: arena_chunk_header_npages = (header_size >> pagesize_2pow);
3560: if ((header_size & pagesize_mask) != 0)
3561: arena_chunk_header_npages++;
3562: }
3563: arena_maxclass = chunksize - (arena_chunk_header_npages <<
3564: pagesize_2pow);
3565:
3566: UTRACE(0, 0, 0);
3567:
3568: #ifdef MALLOC_STATS
3569: memset(&stats_chunks, 0, sizeof(chunk_stats_t));
3570: #endif
3571:
3572: /* Various sanity checks that regard configuration. */
3573: assert(quantum >= sizeof(void *));
3574: assert(quantum <= pagesize);
3575: assert(chunksize >= pagesize);
3576: assert(quantum * 4 <= chunksize);
3577:
3578: /* Initialize chunks data. */
3579: malloc_mutex_init(&chunks_mtx);
3580: RB_INIT(&huge);
3581: #ifdef USE_BRK
3582: malloc_mutex_init(&brk_mtx);
3583: brk_base = sbrk(0);
3584: brk_prev = brk_base;
3585: brk_max = brk_base;
3586: #endif
3587: #ifdef MALLOC_STATS
3588: huge_nmalloc = 0;
3589: huge_ndalloc = 0;
1.8 yamt 3590: huge_nralloc = 0;
1.1 ad 3591: huge_allocated = 0;
3592: #endif
3593: RB_INIT(&old_chunks);
3594:
3595: /* Initialize base allocation data structures. */
3596: #ifdef MALLOC_STATS
3597: base_mapped = 0;
3598: #endif
3599: #ifdef USE_BRK
3600: /*
3601: * Allocate a base chunk here, since it doesn't actually have to be
3602: * chunk-aligned. Doing this before allocating any other chunks allows
3603: * the use of space that would otherwise be wasted.
3604: */
3605: base_pages_alloc(0);
3606: #endif
3607: base_chunk_nodes = NULL;
3608: malloc_mutex_init(&base_mtx);
3609:
3610: if (ncpus > 1) {
3611: /*
3612: * For SMP systems, create four times as many arenas as there
3613: * are CPUs by default.
3614: */
3615: opt_narenas_lshift += 2;
3616: }
3617:
1.2 ad 3618: #ifdef NO_TLS
3619: /* Initialize arena key. */
3620: (void)thr_keycreate(&arenas_map_key, NULL);
3621: #endif
3622:
1.1 ad 3623: /* Determine how many arenas to use. */
3624: narenas = ncpus;
3625: if (opt_narenas_lshift > 0) {
3626: if ((narenas << opt_narenas_lshift) > narenas)
3627: narenas <<= opt_narenas_lshift;
3628: /*
3629: * Make sure not to exceed the limits of what base_malloc()
3630: * can handle.
3631: */
3632: if (narenas * sizeof(arena_t *) > chunksize)
1.9 christos 3633: narenas = (unsigned)(chunksize / sizeof(arena_t *));
1.1 ad 3634: } else if (opt_narenas_lshift < 0) {
3635: if ((narenas << opt_narenas_lshift) < narenas)
3636: narenas <<= opt_narenas_lshift;
1.15 ad 3637: /* Make sure there is at least one arena. */
3638: if (narenas == 0)
3639: narenas = 1;
1.1 ad 3640: }
3641:
3642: next_arena = 0;
3643:
3644: /* Allocate and initialize arenas. */
3645: arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas);
3646: if (arenas == NULL) {
3647: malloc_mutex_unlock(&init_lock);
3648: return (true);
3649: }
3650: /*
3651: * Zero the array. In practice, this should always be pre-zeroed,
3652: * since it was just mmap()ed, but let's be sure.
3653: */
3654: memset(arenas, 0, sizeof(arena_t *) * narenas);
3655:
3656: /*
3657: * Initialize one arena here. The rest are lazily created in
3658: * arena_choose_hard().
3659: */
3660: arenas_extend(0);
3661: if (arenas[0] == NULL) {
3662: malloc_mutex_unlock(&init_lock);
3663: return (true);
3664: }
3665:
3666: malloc_mutex_init(&arenas_mtx);
3667:
3668: malloc_initialized = true;
3669: malloc_mutex_unlock(&init_lock);
3670: return (false);
3671: }
3672:
3673: /*
3674: * End general internal functions.
3675: */
3676: /******************************************************************************/
3677: /*
3678: * Begin malloc(3)-compatible functions.
3679: */
3680:
3681: void *
3682: malloc(size_t size)
3683: {
3684: void *ret;
3685:
3686: if (malloc_init()) {
3687: ret = NULL;
3688: goto RETURN;
3689: }
3690:
3691: if (size == 0) {
3692: if (opt_sysv == false)
3693: size = 1;
3694: else {
3695: ret = NULL;
3696: goto RETURN;
3697: }
3698: }
3699:
3700: ret = imalloc(size);
3701:
3702: RETURN:
3703: if (ret == NULL) {
3704: if (opt_xmalloc) {
1.16 christos 3705: _malloc_message(getprogname(),
1.1 ad 3706: ": (malloc) Error in malloc(): out of memory\n", "",
3707: "");
3708: abort();
3709: }
3710: errno = ENOMEM;
3711: }
3712:
3713: UTRACE(0, size, ret);
3714: return (ret);
3715: }
3716:
3717: int
3718: posix_memalign(void **memptr, size_t alignment, size_t size)
3719: {
3720: int ret;
3721: void *result;
3722:
3723: if (malloc_init())
3724: result = NULL;
3725: else {
3726: /* Make sure that alignment is a large enough power of 2. */
3727: if (((alignment - 1) & alignment) != 0
3728: || alignment < sizeof(void *)) {
3729: if (opt_xmalloc) {
1.16 christos 3730: _malloc_message(getprogname(),
1.1 ad 3731: ": (malloc) Error in posix_memalign(): "
3732: "invalid alignment\n", "", "");
3733: abort();
3734: }
3735: result = NULL;
3736: ret = EINVAL;
3737: goto RETURN;
3738: }
3739:
3740: result = ipalloc(alignment, size);
3741: }
3742:
3743: if (result == NULL) {
3744: if (opt_xmalloc) {
1.16 christos 3745: _malloc_message(getprogname(),
1.1 ad 3746: ": (malloc) Error in posix_memalign(): out of memory\n",
3747: "", "");
3748: abort();
3749: }
3750: ret = ENOMEM;
3751: goto RETURN;
3752: }
3753:
3754: *memptr = result;
3755: ret = 0;
3756:
3757: RETURN:
3758: UTRACE(0, size, result);
3759: return (ret);
3760: }
3761:
3762: void *
3763: calloc(size_t num, size_t size)
3764: {
3765: void *ret;
3766: size_t num_size;
3767:
3768: if (malloc_init()) {
3769: num_size = 0;
3770: ret = NULL;
3771: goto RETURN;
3772: }
3773:
3774: num_size = num * size;
3775: if (num_size == 0) {
3776: if ((opt_sysv == false) && ((num == 0) || (size == 0)))
3777: num_size = 1;
3778: else {
3779: ret = NULL;
3780: goto RETURN;
3781: }
3782: /*
3783: * Try to avoid division here. We know that it isn't possible to
3784: * overflow during multiplication if neither operand uses any of the
3785: * most significant half of the bits in a size_t.
3786: */
1.2 ad 3787: } else if ((unsigned long long)((num | size) &
3788: ((unsigned long long)SIZE_T_MAX << (sizeof(size_t) << 2))) &&
3789: (num_size / size != num)) {
1.1 ad 3790: /* size_t overflow. */
3791: ret = NULL;
3792: goto RETURN;
3793: }
3794:
3795: ret = icalloc(num_size);
3796:
3797: RETURN:
3798: if (ret == NULL) {
3799: if (opt_xmalloc) {
1.16 christos 3800: _malloc_message(getprogname(),
1.1 ad 3801: ": (malloc) Error in calloc(): out of memory\n", "",
3802: "");
3803: abort();
3804: }
3805: errno = ENOMEM;
3806: }
3807:
3808: UTRACE(0, num_size, ret);
3809: return (ret);
3810: }
3811:
3812: void *
3813: realloc(void *ptr, size_t size)
3814: {
3815: void *ret;
3816:
3817: if (size == 0) {
3818: if (opt_sysv == false)
3819: size = 1;
3820: else {
3821: if (ptr != NULL)
3822: idalloc(ptr);
3823: ret = NULL;
3824: goto RETURN;
3825: }
3826: }
3827:
3828: if (ptr != NULL) {
3829: assert(malloc_initialized);
3830:
3831: ret = iralloc(ptr, size);
3832:
3833: if (ret == NULL) {
3834: if (opt_xmalloc) {
1.16 christos 3835: _malloc_message(getprogname(),
1.1 ad 3836: ": (malloc) Error in realloc(): out of "
3837: "memory\n", "", "");
3838: abort();
3839: }
3840: errno = ENOMEM;
3841: }
3842: } else {
3843: if (malloc_init())
3844: ret = NULL;
3845: else
3846: ret = imalloc(size);
3847:
3848: if (ret == NULL) {
3849: if (opt_xmalloc) {
1.16 christos 3850: _malloc_message(getprogname(),
1.1 ad 3851: ": (malloc) Error in realloc(): out of "
3852: "memory\n", "", "");
3853: abort();
3854: }
3855: errno = ENOMEM;
3856: }
3857: }
3858:
3859: RETURN:
3860: UTRACE(ptr, size, ret);
3861: return (ret);
3862: }
3863:
3864: void
3865: free(void *ptr)
3866: {
3867:
3868: UTRACE(ptr, 0, 0);
3869: if (ptr != NULL) {
3870: assert(malloc_initialized);
3871:
3872: idalloc(ptr);
3873: }
3874: }
3875:
3876: /*
3877: * End malloc(3)-compatible functions.
3878: */
3879: /******************************************************************************/
3880: /*
3881: * Begin non-standard functions.
3882: */
1.2 ad 3883: #ifndef __NetBSD__
1.1 ad 3884: size_t
3885: malloc_usable_size(const void *ptr)
3886: {
3887:
3888: assert(ptr != NULL);
3889:
3890: return (isalloc(ptr));
3891: }
1.2 ad 3892: #endif
1.1 ad 3893:
3894: /*
3895: * End non-standard functions.
3896: */
3897: /******************************************************************************/
3898: /*
3899: * Begin library-private functions, used by threading libraries for protection
3900: * of malloc during fork(). These functions are only called if the program is
3901: * running in threaded mode, so there is no need to check whether the program
3902: * is threaded here.
3903: */
3904:
3905: void
3906: _malloc_prefork(void)
3907: {
3908: unsigned i;
3909:
3910: /* Acquire all mutexes in a safe order. */
3911:
3912: malloc_mutex_lock(&arenas_mtx);
3913: for (i = 0; i < narenas; i++) {
3914: if (arenas[i] != NULL)
3915: malloc_mutex_lock(&arenas[i]->mtx);
3916: }
3917: malloc_mutex_unlock(&arenas_mtx);
3918:
3919: malloc_mutex_lock(&base_mtx);
3920:
3921: malloc_mutex_lock(&chunks_mtx);
3922: }
3923:
3924: void
3925: _malloc_postfork(void)
3926: {
3927: unsigned i;
3928:
3929: /* Release all mutexes, now that fork() has completed. */
3930:
3931: malloc_mutex_unlock(&chunks_mtx);
3932:
3933: malloc_mutex_unlock(&base_mtx);
3934:
3935: malloc_mutex_lock(&arenas_mtx);
3936: for (i = 0; i < narenas; i++) {
3937: if (arenas[i] != NULL)
3938: malloc_mutex_unlock(&arenas[i]->mtx);
3939: }
3940: malloc_mutex_unlock(&arenas_mtx);
3941: }
3942:
3943: /*
3944: * End library-private functions.
3945: */
3946: /******************************************************************************/
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to jemalloc.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / lib / libc / stdlib