2 * DMALLOC.C - Dillon's malloc
4 * Copyright (c) 2011,2017 The DragonFly Project. All rights reserved.
6 * This code is derived from software contributed to The DragonFly Project
7 * by Matthew Dillon <dillon@backplane.com>.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
19 * 3. Neither the name of The DragonFly Project nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific, prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * This module implements a modified slab allocator as a drop-in replacement
38 * for the libc malloc(). The slab algorithm has been adjusted to support
39 * dynamic sizing of slabs which effectively allows slabs to be used for
40 * allocations of any size. Because of this we neither have a small-block
41 * allocator or a big-block allocator and the code paths are simplified.
43 * To support dynamic slab sizing available user virtual memory is broken
44 * down into ~1024 regions. Each region has fixed slab size whos value is
45 * set when the region is opened up for use. The free() path simply applies
46 * a mask based on the region to the pointer to acquire the base of the
47 * governing slab structure.
49 * Regions[NREGIONS] (1024)
51 * Slab management and locking is done on a per-zone basis.
53 * Alloc Size Chunking Number of zones
64 * ... continues forever ... 4 zones
66 * For a 2^63 memory space each doubling >= 64K is broken down into
67 * 4 chunking zones, so we support 88 + (48 * 4) = 280 zones.
69 * API FEATURES AND SIDE EFFECTS
71 * + power-of-2 sized allocations up to a page will be power-of-2 aligned.
72 * Above that power-of-2 sized allocations are page-aligned. Non
73 * power-of-2 sized allocations are aligned the same as the chunk
74 * size for their zone.
75 * + ability to allocate arbitrarily large chunks of memory
76 * + realloc will reuse the passed pointer if possible, within the
77 * limitations of the zone chunking.
79 * On top of the slab allocator we also implement a 16-entry-per-thread
80 * magazine cache for allocations <= NOMSLABSIZE.
84 * + [better] garbage collection
85 * + better initial sizing.
89 * The value of the environment variable MALLOC_OPTIONS is a character string
90 * containing various flags to tune nmalloc. Upper case letters enabled
91 * or increase the feature, lower case disables or decreases the feature.
93 * U Enable UTRACE for all operations, observable with ktrace.
94 * Diasbled by default.
96 * Z Zero out allocations, otherwise allocations (except for
97 * calloc) will contain garbage.
98 * Disabled by default.
100 * H Pass a hint with madvise() about unused pages.
101 * Disabled by default.
102 * Not currently implemented.
104 * F Disable local per-thread caching.
105 * Disabled by default.
107 * C Increase (decrease) how much excess cache to retain.
108 * Set to 4 by default.
111 /* cc -shared -fPIC -g -O -I/usr/src/lib/libc/include -o dmalloc.so dmalloc.c */
113 #ifndef STANDALONE_DEBUG
114 #include "libc_private.h"
117 #include <sys/param.h>
118 #include <sys/types.h>
119 #include <sys/mman.h>
120 #include <sys/queue.h>
121 #include <sys/ktrace.h>
134 #include <machine/atomic.h>
135 #include <machine/cpufunc.h>
137 #ifdef STANDALONE_DEBUG
138 void _nmalloc_thr_init(void);
140 #include "spinlock.h"
141 #include "un-namespace.h"
144 #ifndef MAP_SIZEALIGN
145 #define MAP_SIZEALIGN 0
148 #if SSIZE_MAX == 0x7FFFFFFF
150 #define UVM_BITS 32 /* worst case */
153 #define UVM_BITS 48 /* worst case XXX */
156 #if LONG_MAX == 0x7FFFFFFF
158 #define LONG_BITS_SHIFT 5
161 #define LONG_BITS_SHIFT 6
164 #define LOCKEDPTR ((void *)(intptr_t)-1)
169 #define NREGIONS_BITS 10
170 #define NREGIONS (1 << NREGIONS_BITS)
171 #define NREGIONS_MASK (NREGIONS - 1)
172 #define NREGIONS_SHIFT (UVM_BITS - NREGIONS_BITS)
173 #define NREGIONS_SIZE (1LU << NREGIONS_SHIFT)
175 typedef struct region
*region_t
;
176 typedef struct slglobaldata
*slglobaldata_t
;
177 typedef struct slab
*slab_t
;
181 slab_t slab
; /* conditional out of band slab */
184 static struct region Regions
[NREGIONS
];
187 * Number of chunking zones available
189 #define CHUNKFACTOR 8
191 #define NZONES (16 + 9 * CHUNKFACTOR + 16 * CHUNKFACTOR)
193 #define NZONES (16 + 9 * CHUNKFACTOR + 48 * CHUNKFACTOR)
196 static int MaxChunks
[NZONES
];
198 #define NDEPOTS 8 /* must be power of 2 */
201 * Maximum number of chunks per slab, governed by the allocation bitmap in
202 * each slab. The maximum is reduced for large chunk sizes.
204 #define MAXCHUNKS (LONG_BITS * LONG_BITS)
205 #define MAXCHUNKS_BITS (LONG_BITS_SHIFT * LONG_BITS_SHIFT)
206 #define LITSLABSIZE (32 * 1024)
207 #define NOMSLABSIZE (2 * 1024 * 1024)
208 #define BIGSLABSIZE (128 * 1024 * 1024)
210 #define ZALLOC_SLAB_MAGIC 0x736c6162 /* magic sanity */
212 TAILQ_HEAD(slab_list
, slab
);
218 struct slab
*next
; /* slabs with available space */
219 TAILQ_ENTRY(slab
) entry
;
220 int32_t magic
; /* magic number for sanity check */
221 u_int navail
; /* number of free elements available */
223 u_int free_bit
; /* free hint bitno */
224 u_int free_index
; /* free hint index */
225 u_long bitmap
[LONG_BITS
]; /* free chunks */
226 size_t slab_size
; /* size of entire slab */
227 size_t chunk_size
; /* chunk size for validation */
229 enum { UNKNOWN
, AVAIL
, EMPTY
, FULL
} state
;
231 region_t region
; /* related region */
232 char *chunks
; /* chunk base */
233 slglobaldata_t slgd
; /* localized to thread else NULL */
237 * per-thread data + global depot
239 * NOTE: The magazine shortcut is only used for per-thread data.
241 #define NMAGSHORTCUT 16
243 struct slglobaldata
{
244 spinlock_t lock
; /* only used by slglobaldepot */
252 void *mag_shortcut
[NMAGSHORTCUT
];
254 struct slab_list full_zones
; /* via entry */
260 #define SLAB_ZEROD 0x0001
263 * Misc constants. Note that allocations that are exact multiples of
264 * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module.
265 * IN_SAME_PAGE_MASK is used to sanity-check the per-page free lists.
267 #define MIN_CHUNK_SIZE 8 /* in bytes */
268 #define MIN_CHUNK_MASK (MIN_CHUNK_SIZE - 1)
270 #define SAFLAG_ZERO 0x00000001
273 * The WEIRD_ADDR is used as known text to copy into free objects to
274 * try to create deterministic failure cases if the data is accessed after
277 * WARNING: A limited number of spinlocks are available, BIGXSIZE should
278 * not be larger then 64.
281 #define WEIRD_ADDR 0xdeadc0de
288 #define MASSERT(exp) do { if (__predict_false(!(exp))) \
289 _mpanic("assertion: %s in %s", \
294 * With this attribute set, do not require a function call for accessing
295 * this variable when the code is compiled -fPIC.
297 * Must be empty for libc_rtld (similar to __thread)
299 #if defined(__LIBC_RTLD)
300 #define TLS_ATTRIBUTE
302 #define TLS_ATTRIBUTE __attribute__ ((tls_model ("initial-exec")));
305 static __thread
struct slglobaldata slglobal TLS_ATTRIBUTE
;
306 static pthread_key_t thread_malloc_key
;
307 static pthread_once_t thread_malloc_once
= PTHREAD_ONCE_INIT
;
308 static struct slglobaldata slglobaldepot
;
310 static int opt_madvise
= 0;
311 static int opt_free
= 0;
312 static int opt_cache
= 4;
313 static int opt_utrace
= 0;
314 static int g_malloc_flags
= 0;
315 static int malloc_panic
;
318 static const int32_t weirdary
[16] = {
319 WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
,
320 WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
,
321 WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
,
322 WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
, WEIRD_ADDR
326 static void *memalloc(size_t size
, int flags
);
327 static void *memrealloc(void *ptr
, size_t size
);
328 static void memfree(void *ptr
, int);
329 static int memalign(void **memptr
, size_t alignment
, size_t size
);
330 static slab_t
slaballoc(int zi
, size_t chunking
, size_t chunk_size
);
331 static void slabfree(slab_t slab
);
332 static void slabterm(slglobaldata_t slgd
, slab_t slab
);
333 static void *_vmem_alloc(int ri
, size_t slab_size
);
334 static void _vmem_free(void *ptr
, size_t slab_size
);
335 static void _mpanic(const char *ctl
, ...) __printflike(1, 2);
336 #ifndef STANDALONE_DEBUG
337 static void malloc_init(void) __constructor(101);
339 static void malloc_init(void) __constructor(101);
343 struct nmalloc_utrace
{
349 #define UTRACE(a, b, c) \
351 struct nmalloc_utrace ut = { \
356 utrace(&ut, sizeof(ut)); \
361 * If enabled any memory allocated without M_ZERO is initialized to -1.
363 static int use_malloc_pattern
;
369 const char *p
= NULL
;
371 TAILQ_INIT(&slglobal
.full_zones
);
373 Regions
[0].mask
= -1; /* disallow activity in lowest region */
375 if (issetugid() == 0)
376 p
= getenv("MALLOC_OPTIONS");
378 for (; p
!= NULL
&& *p
!= '\0'; p
++) {
409 g_malloc_flags
= SAFLAG_ZERO
;
416 UTRACE((void *) -1, 0, NULL
);
420 * We have to install a handler for nmalloc thread teardowns when
421 * the thread is created. We cannot delay this because destructors in
422 * sophisticated userland programs can call malloc() for the first time
423 * during their thread exit.
425 * This routine is called directly from pthreads.
427 static void _nmalloc_thr_init_once(void);
428 static void _nmalloc_thr_destructor(void *thrp
);
431 _nmalloc_thr_init(void)
435 TAILQ_INIT(&slglobal
.full_zones
);
443 pthread_once(&thread_malloc_once
, _nmalloc_thr_init_once
);
445 pthread_setspecific(thread_malloc_key
, &slglobal
);
450 _nmalloc_thr_prepfork(void)
453 _SPINLOCK(&slglobaldepot
.lock
);
457 _nmalloc_thr_parentfork(void)
460 _SPINUNLOCK(&slglobaldepot
.lock
);
464 _nmalloc_thr_childfork(void)
467 _SPINUNLOCK(&slglobaldepot
.lock
);
474 _nmalloc_thr_init_once(void)
476 /* ignore error from stub if not threaded */
477 pthread_key_create(&thread_malloc_key
, _nmalloc_thr_destructor
);
481 * Called for each thread undergoing exit
483 * Move all of the thread's slabs into a depot.
486 _nmalloc_thr_destructor(void *thrp
)
488 slglobaldata_t slgd
= thrp
;
489 struct zoneinfo
*zinfo
;
497 for (i
= 0; i
<= slgd
->biggest_index
; i
++) {
498 zinfo
= &slgd
->zone
[i
];
500 while ((j
= zinfo
->mag_index
) > 0) {
502 ptr
= zinfo
->mag_shortcut
[j
];
503 zinfo
->mag_shortcut
[j
] = NULL
; /* SAFETY */
504 zinfo
->mag_index
= j
;
508 while ((slab
= zinfo
->empty_base
) != NULL
) {
509 zinfo
->empty_base
= slab
->next
;
510 --zinfo
->empty_count
;
511 slabterm(slgd
, slab
);
514 while ((slab
= zinfo
->avail_base
) != NULL
) {
515 zinfo
->avail_base
= slab
->next
;
516 --zinfo
->avail_count
;
517 slabterm(slgd
, slab
);
520 while ((slab
= TAILQ_FIRST(&slgd
->full_zones
)) != NULL
) {
521 TAILQ_REMOVE(&slgd
->full_zones
, slab
, entry
);
522 slabterm(slgd
, slab
);
528 * Calculate the zone index for the allocation request size and set the
529 * allocation request size to that particular zone's chunk size.
531 * Minimum alignment is 16 bytes for allocations >= 16 bytes to conform
532 * with malloc requirements for intel/amd.
535 zoneindex(size_t *bytes
, size_t *chunking
)
537 size_t n
= (size_t)*bytes
;
544 *bytes
= n
= (n
+ 7) & ~7;
546 return(n
/ 8 - 1); /* 8 byte chunks, 2 zones */
548 *bytes
= n
= (n
+ 15) & ~15;
550 return(n
/ 16 + 2); /* 16 byte chunks, 8 zones */
555 c
= x
/ (CHUNKFACTOR
* 2);
559 c
= x
/ (CHUNKFACTOR
* 2);
560 i
= 16 + CHUNKFACTOR
* 5; /* 256->512,1024,2048,4096,8192 */
567 _mpanic("slaballoc: byte value too high");
569 *bytes
= n
= roundup2(n
, c
);
571 return (i
+ n
/ c
- CHUNKFACTOR
);
573 *bytes
= n
= (n
+ c
- 1) & ~(c
- 1);
578 *bytes
= n
= (n
+ 15) & ~15;
580 return(n
/ (CHUNKINGLO
*2) + CHUNKINGLO
*1 - 1);
584 *bytes
= n
= (n
+ 31) & ~31;
586 return(n
/ (CHUNKINGLO
*4) + CHUNKINGLO
*2 - 1);
589 *bytes
= n
= (n
+ 63) & ~63;
591 return(n
/ (CHUNKINGLO
*8) + CHUNKINGLO
*3 - 1);
594 *bytes
= n
= (n
+ 127) & ~127;
596 return(n
/ (CHUNKINGLO
*16) + CHUNKINGLO
*4 - 1);
599 *bytes
= n
= (n
+ 255) & ~255;
601 return(n
/ (CHUNKINGLO
*32) + CHUNKINGLO
*5 - 1);
603 *bytes
= n
= (n
+ 511) & ~511;
605 return(n
/ (CHUNKINGLO
*64) + CHUNKINGLO
*6 - 1);
608 *bytes
= n
= (n
+ 1023) & ~1023;
610 return(n
/ (CHUNKINGLO
*128) + CHUNKINGLO
*7 - 1);
612 if (n
< 32768) { /* 16384-32767 */
613 *bytes
= n
= (n
+ 2047) & ~2047;
615 return(n
/ (CHUNKINGLO
*256) + CHUNKINGLO
*8 - 1);
618 *bytes
= n
= (n
+ 4095) & ~4095; /* 32768-65535 */
620 return(n
/ (CHUNKINGLO
*512) + CHUNKINGLO
*9 - 1);
625 i
= CHUNKINGLO
*10 - 1;
632 _mpanic("slaballoc: byte value too high");
634 *bytes
= n
= (n
+ c
- 1) & ~(c
- 1);
641 * malloc() - call internal slab allocator
644 __malloc(size_t size
)
648 ptr
= memalloc(size
, 0);
652 UTRACE(0, size
, ptr
);
657 * calloc() - call internal slab allocator
660 __calloc(size_t number
, size_t size
)
664 ptr
= memalloc(number
* size
, SAFLAG_ZERO
);
668 UTRACE(0, number
* size
, ptr
);
673 * realloc() (SLAB ALLOCATOR)
675 * We do not attempt to optimize this routine beyond reusing the same
676 * pointer if the new size fits within the chunking of the old pointer's
680 __realloc(void *ptr
, size_t size
)
685 ret
= memalloc(size
, 0);
687 ret
= memrealloc(ptr
, size
);
691 UTRACE(ptr
, size
, ret
);
698 * Allocate (size) bytes with a alignment of (alignment).
701 __aligned_alloc(size_t alignment
, size_t size
)
707 rc
= memalign(&ptr
, alignment
, size
);
717 * Allocate (size) bytes with a alignment of (alignment), where (alignment)
718 * is a power of 2 >= sizeof(void *).
721 __posix_memalign(void **memptr
, size_t alignment
, size_t size
)
726 * OpenGroup spec issue 6 check
728 if (alignment
< sizeof(void *)) {
733 rc
= memalign(memptr
, alignment
, size
);
739 * The slab allocator will allocate on power-of-2 boundaries up to at least
740 * PAGE_SIZE. Otherwise we use the zoneindex mechanic to find a zone
741 * matching the requirements.
744 memalign(void **memptr
, size_t alignment
, size_t size
)
753 * OpenGroup spec issue 6 check
755 if ((alignment
| (alignment
- 1)) + 1 != (alignment
<< 1)) {
761 * XXX for now just find the nearest power of 2 >= size and also
762 * >= alignment and allocate that.
764 while (alignment
< size
) {
767 _mpanic("posix_memalign: byte value too high");
769 *memptr
= memalloc(alignment
, 0);
770 return(*memptr
? 0 : ENOMEM
);
774 * free() (SLAB ALLOCATOR) - do the obvious
786 * memalloc() (SLAB ALLOCATOR)
788 * Allocate memory via the slab allocator.
791 memalloc(size_t size
, int flags
)
794 struct zoneinfo
*zinfo
;
808 * If 0 bytes is requested we have to return a unique pointer, allocate
814 /* Capture global flags */
815 flags
|= g_malloc_flags
;
817 /* Compute allocation zone; zoneindex will panic on excessive sizes */
818 zi
= zoneindex(&size
, &chunking
);
819 MASSERT(zi
< NZONES
);
824 * Try magazine shortcut first
827 zinfo
= &slgd
->zone
[zi
];
829 if ((j
= zinfo
->mag_index
) != 0) {
830 zinfo
->mag_index
= --j
;
831 obj
= zinfo
->mag_shortcut
[j
];
832 zinfo
->mag_shortcut
[j
] = NULL
; /* SAFETY */
833 if (flags
& SAFLAG_ZERO
)
839 * Locate a slab with available space. If no slabs are available
840 * back-off to the empty list and if we still come up dry allocate
841 * a new slab (which will try the depot first).
844 if ((slab
= zinfo
->avail_base
) == NULL
) {
845 if ((slab
= zinfo
->empty_base
) == NULL
) {
849 slab
= slaballoc(zi
, chunking
, size
);
852 slab
->next
= zinfo
->avail_base
;
853 zinfo
->avail_base
= slab
;
854 ++zinfo
->avail_count
;
856 if (slgd
->biggest_index
< zi
)
857 slgd
->biggest_index
= zi
;
861 * Pulled from empty list
863 zinfo
->empty_base
= slab
->next
;
864 slab
->next
= zinfo
->avail_base
;
865 zinfo
->avail_base
= slab
;
866 ++zinfo
->avail_count
;
868 --zinfo
->empty_count
;
873 * Allocate a chunk out of the slab. HOT PATH
875 * Only the thread owning the slab can allocate out of it.
877 * NOTE: The last bit in the bitmap is always marked allocated so
878 * we cannot overflow here.
880 bno
= slab
->free_bit
;
881 bmi
= slab
->free_index
;
882 bmp
= &slab
->bitmap
[bmi
];
883 if (*bmp
& (1LU << bno
)) {
884 atomic_clear_long(bmp
, 1LU << bno
);
885 obj
= slab
->chunks
+ ((bmi
<< LONG_BITS_SHIFT
) + bno
) * size
;
886 slab
->free_bit
= (bno
+ 1) & (LONG_BITS
- 1);
887 atomic_add_int(&slab
->navail
, -1);
888 if (flags
& SAFLAG_ZERO
)
894 * Allocate a chunk out of a slab. COLD PATH
896 if (slab
->navail
== 0) {
897 zinfo
->avail_base
= slab
->next
;
898 --zinfo
->avail_count
;
900 TAILQ_INSERT_TAIL(&slgd
->full_zones
, slab
, entry
);
904 while (bmi
< LONG_BITS
) {
905 bmp
= &slab
->bitmap
[bmi
];
908 atomic_clear_long(bmp
, 1LU << bno
);
909 obj
= slab
->chunks
+ ((bmi
<< LONG_BITS_SHIFT
) + bno
) *
911 slab
->free_index
= bmi
;
912 slab
->free_bit
= (bno
+ 1) & (LONG_BITS
- 1);
913 atomic_add_int(&slab
->navail
, -1);
914 if (flags
& SAFLAG_ZERO
)
921 while (bmi
< LONG_BITS
) {
922 bmp
= &slab
->bitmap
[bmi
];
925 atomic_clear_long(bmp
, 1LU << bno
);
926 obj
= slab
->chunks
+ ((bmi
<< LONG_BITS_SHIFT
) + bno
) *
928 slab
->free_index
= bmi
;
929 slab
->free_bit
= (bno
+ 1) & (LONG_BITS
- 1);
930 atomic_add_int(&slab
->navail
, -1);
931 if (flags
& SAFLAG_ZERO
)
937 _mpanic("slaballoc: corrupted zone: navail %d", slab
->navail
);
943 * Reallocate memory within the chunk
946 memrealloc(void *ptr
, size_t nsize
)
955 * If 0 bytes is requested we have to return a unique pointer, allocate
961 /* Capture global flags */
962 flags
|= g_malloc_flags
;
965 * Locate the zone by looking up the dynamic slab size mask based
966 * on the memory region the allocation resides in.
968 region
= &Regions
[((uintptr_t)ptr
>> NREGIONS_SHIFT
) & NREGIONS_MASK
];
969 if ((slab
= region
->slab
) == NULL
)
970 slab
= (void *)((uintptr_t)ptr
& region
->mask
);
971 MASSERT(slab
->magic
== ZALLOC_SLAB_MAGIC
);
972 osize
= slab
->chunk_size
;
973 if (nsize
<= osize
) {
974 if (osize
< 32 || nsize
>= osize
/ 2) {
976 if ((flags
& SAFLAG_ZERO
) && nsize
< osize
)
977 bzero(obj
+ nsize
, osize
- nsize
);
983 * Otherwise resize the object
985 obj
= memalloc(nsize
, 0);
989 bcopy(ptr
, obj
, nsize
);
996 * free (SLAB ALLOCATOR)
998 * Free a memory block previously allocated by malloc.
1003 memfree(void *ptr
, int flags
)
1006 slglobaldata_t slgd
;
1016 * Locate the zone by looking up the dynamic slab size mask based
1017 * on the memory region the allocation resides in.
1019 * WARNING! The slab may be owned by another thread!
1021 region
= &Regions
[((uintptr_t)ptr
>> NREGIONS_SHIFT
) & NREGIONS_MASK
];
1022 if ((slab
= region
->slab
) == NULL
)
1023 slab
= (void *)((uintptr_t)ptr
& region
->mask
);
1024 MASSERT(slab
!= NULL
);
1025 MASSERT(slab
->magic
== ZALLOC_SLAB_MAGIC
);
1029 * Put weird data into the memory to detect modifications after
1030 * freeing, illegal pointer use after freeing (we should fault on
1031 * the odd address), and so forth.
1033 if (slab
->chunk_size
< sizeof(weirdary
))
1034 bcopy(weirdary
, ptr
, slab
->chunk_size
);
1036 bcopy(weirdary
, ptr
, sizeof(weirdary
));
1041 * Use mag_shortcut[] when possible
1043 if (slgd
->masked
== 0 && slab
->chunk_size
<= NOMSLABSIZE
) {
1044 struct zoneinfo
*zinfo
;
1046 zinfo
= &slgd
->zone
[slab
->zone_index
];
1047 j
= zinfo
->mag_index
;
1048 if (j
< NMAGSHORTCUT
) {
1049 zinfo
->mag_shortcut
[j
] = ptr
;
1050 zinfo
->mag_index
= j
+ 1;
1056 * Free to slab and increment navail. We can delay incrementing
1057 * navail to prevent the slab from being destroyed out from under
1058 * us while we do other optimizations.
1060 bno
= ((uintptr_t)ptr
- (uintptr_t)slab
->chunks
) / slab
->chunk_size
;
1061 bmi
= bno
>> LONG_BITS_SHIFT
;
1062 bno
&= (LONG_BITS
- 1);
1063 bmp
= &slab
->bitmap
[bmi
];
1065 MASSERT(bmi
>= 0 && bmi
< slab
->nmax
);
1066 MASSERT((*bmp
& (1LU << bno
)) == 0);
1067 atomic_set_long(bmp
, 1LU << bno
);
1069 if (slab
->slgd
== slgd
) {
1071 * We can only do the following if we own the slab. Note
1072 * that navail can be incremented by any thread even if
1075 struct zoneinfo
*zinfo
;
1077 atomic_add_int(&slab
->navail
, 1);
1078 if (slab
->free_index
> bmi
) {
1079 slab
->free_index
= bmi
;
1080 slab
->free_bit
= bno
;
1081 } else if (slab
->free_index
== bmi
&&
1082 slab
->free_bit
> bno
) {
1083 slab
->free_bit
= bno
;
1085 zinfo
= &slgd
->zone
[slab
->zone_index
];
1088 * Freeing an object from a full slab makes it less than
1089 * full. The slab must be moved to the available list.
1091 * If the available list has too many slabs, release some
1094 if (slab
->state
== FULL
) {
1095 TAILQ_REMOVE(&slgd
->full_zones
, slab
, entry
);
1096 slab
->state
= AVAIL
;
1097 stmp
= zinfo
->avail_base
;
1099 zinfo
->avail_base
= slab
;
1100 ++zinfo
->avail_count
;
1101 while (zinfo
->avail_count
> opt_cache
) {
1102 slab
= zinfo
->avail_base
;
1103 zinfo
->avail_base
= slab
->next
;
1104 --zinfo
->avail_count
;
1105 slabterm(slgd
, slab
);
1111 * If the slab becomes completely empty dispose of it in
1112 * some manner. By default each thread caches up to 4
1113 * empty slabs. Only small slabs are cached.
1115 if (slab
->navail
== slab
->nmax
&& slab
->state
== AVAIL
) {
1117 * Remove slab from available queue
1119 slabp
= &zinfo
->avail_base
;
1120 while ((stmp
= *slabp
) != slab
)
1121 slabp
= &stmp
->next
;
1122 *slabp
= slab
->next
;
1123 --zinfo
->avail_count
;
1125 if (opt_free
|| opt_cache
== 0) {
1127 * If local caching is disabled cache the
1128 * slab in the depot (or free it).
1130 slabterm(slgd
, slab
);
1131 } else if (slab
->slab_size
> BIGSLABSIZE
) {
1133 * We do not try to retain large slabs
1134 * in per-thread caches.
1136 slabterm(slgd
, slab
);
1137 } else if (zinfo
->empty_count
> opt_cache
) {
1139 * We have too many slabs cached, but
1140 * instead of freeing this one free
1141 * an empty slab that's been idle longer.
1143 * (empty_count does not change)
1145 stmp
= zinfo
->empty_base
;
1146 slab
->state
= EMPTY
;
1147 slab
->next
= stmp
->next
;
1148 zinfo
->empty_base
= slab
;
1149 slabterm(slgd
, stmp
);
1152 * Cache the empty slab in our thread local
1155 ++zinfo
->empty_count
;
1156 slab
->state
= EMPTY
;
1157 slab
->next
= zinfo
->empty_base
;
1158 zinfo
->empty_base
= slab
;
1161 } else if (slab
->slgd
== NULL
&& slab
->navail
+ 1 == slab
->nmax
) {
1162 slglobaldata_t sldepot
;
1165 * If freeing to a slab owned by the global depot, and
1166 * the slab becomes completely EMPTY, try to move it to
1169 sldepot
= &slglobaldepot
;
1171 _SPINLOCK(&sldepot
->lock
);
1172 if (slab
->slgd
== NULL
&& slab
->navail
+ 1 == slab
->nmax
) {
1173 struct zoneinfo
*zinfo
;
1176 * Move the slab to the empty list
1178 MASSERT(slab
->state
== AVAIL
);
1179 atomic_add_int(&slab
->navail
, 1);
1180 zinfo
= &sldepot
->zone
[slab
->zone_index
];
1181 slabp
= &zinfo
->avail_base
;
1182 while (slab
!= *slabp
)
1183 slabp
= &(*slabp
)->next
;
1184 *slabp
= slab
->next
;
1185 --zinfo
->avail_count
;
1188 * Clean out excessive empty entries from the
1191 slab
->state
= EMPTY
;
1192 slab
->next
= zinfo
->empty_base
;
1193 zinfo
->empty_base
= slab
;
1194 ++zinfo
->empty_count
;
1195 while (zinfo
->empty_count
> opt_cache
) {
1196 slab
= zinfo
->empty_base
;
1197 zinfo
->empty_base
= slab
->next
;
1198 --zinfo
->empty_count
;
1199 slab
->state
= UNKNOWN
;
1201 _SPINUNLOCK(&sldepot
->lock
);
1204 _SPINLOCK(&sldepot
->lock
);
1207 atomic_add_int(&slab
->navail
, 1);
1210 _SPINUNLOCK(&sldepot
->lock
);
1213 * We can't act on the slab other than by adjusting navail
1214 * (and the bitmap which we did in the common code at the
1217 atomic_add_int(&slab
->navail
, 1);
1224 * Allocate a new slab holding objects of size chunk_size.
1227 slaballoc(int zi
, size_t chunking
, size_t chunk_size
)
1229 slglobaldata_t slgd
;
1230 slglobaldata_t sldepot
;
1231 struct zoneinfo
*zinfo
;
1238 uintptr_t chunk_offset
;
1249 * First look in the depot. Any given zone in the depot may be
1250 * locked by being set to -1. We have to do this instead of simply
1251 * removing the entire chain because removing the entire chain can
1252 * cause racing threads to allocate local slabs for large objects,
1253 * resulting in a large VSZ.
1256 sldepot
= &slglobaldepot
;
1257 zinfo
= &sldepot
->zone
[zi
];
1259 if (zinfo
->avail_base
) {
1261 _SPINLOCK(&sldepot
->lock
);
1262 slab
= zinfo
->avail_base
;
1264 MASSERT(slab
->slgd
== NULL
);
1266 zinfo
->avail_base
= slab
->next
;
1267 --zinfo
->avail_count
;
1269 _SPINUNLOCK(&sldepot
->lock
);
1273 _SPINUNLOCK(&sldepot
->lock
);
1277 * Nothing in the depot, allocate a new slab by locating or assigning
1278 * a region and then using the system virtual memory allocator.
1283 * Calculate the start of the data chunks relative to the start
1284 * of the slab. If chunk_size is a power of 2 we guarantee
1285 * power of 2 alignment. If it is not we guarantee alignment
1286 * to the chunk size.
1288 if ((chunk_size
^ (chunk_size
- 1)) == (chunk_size
<< 1) - 1) {
1290 chunk_offset
= roundup2(sizeof(*slab
), chunk_size
);
1293 chunk_offset
= sizeof(*slab
) + chunking
- 1;
1294 chunk_offset
-= chunk_offset
% chunking
;
1298 * Calculate a reasonable number of chunks for the slab.
1300 * Once initialized the MaxChunks[] array can only ever be
1301 * reinitialized to the same value.
1303 maxchunks
= MaxChunks
[zi
];
1304 if (maxchunks
== 0) {
1306 * First calculate how many chunks would fit in 1/1024
1307 * available memory. This is around 2MB on a 32 bit
1308 * system and 128G on a 64-bit (48-bits available) system.
1310 maxchunks
= (ssize_t
)(NREGIONS_SIZE
- chunk_offset
) /
1311 (ssize_t
)chunk_size
;
1316 * A slab cannot handle more than MAXCHUNKS chunks, but
1317 * limit us to approximately MAXCHUNKS / 2 here because
1318 * we may have to expand maxchunks when we calculate the
1319 * actual power-of-2 slab.
1321 if (maxchunks
> MAXCHUNKS
/ 2)
1322 maxchunks
= MAXCHUNKS
/ 2;
1325 * Try to limit the slabs to BIGSLABSIZE (~128MB). Larger
1326 * slabs will be created if the allocation does not fit.
1328 if (chunk_offset
+ chunk_size
* maxchunks
> BIGSLABSIZE
) {
1329 tmpchunks
= (ssize_t
)(BIGSLABSIZE
- chunk_offset
) /
1330 (ssize_t
)chunk_size
;
1333 if (maxchunks
> tmpchunks
)
1334 maxchunks
= tmpchunks
;
1338 * If the slab calculates to greater than 2MB see if we
1339 * can cut it down to ~2MB. This controls VSZ but has
1340 * no effect on run-time size or performance.
1342 * This is very important in case you core dump and also
1343 * important to reduce unnecessary region allocations.
1345 if (chunk_offset
+ chunk_size
* maxchunks
> NOMSLABSIZE
) {
1346 tmpchunks
= (ssize_t
)(NOMSLABSIZE
- chunk_offset
) /
1347 (ssize_t
)chunk_size
;
1350 if (maxchunks
> tmpchunks
)
1351 maxchunks
= tmpchunks
;
1355 * If the slab calculates to greater than 128K see if we
1356 * can cut it down to ~128K while still maintaining a
1357 * reasonably large number of chunks in each slab. This
1358 * controls VSZ but has no effect on run-time size or
1361 * This is very important in case you core dump and also
1362 * important to reduce unnecessary region allocations.
1364 if (chunk_offset
+ chunk_size
* maxchunks
> LITSLABSIZE
) {
1365 tmpchunks
= (ssize_t
)(LITSLABSIZE
- chunk_offset
) /
1366 (ssize_t
)chunk_size
;
1369 if (maxchunks
> tmpchunks
)
1370 maxchunks
= tmpchunks
;
1373 MaxChunks
[zi
] = maxchunks
;
1375 MASSERT(maxchunks
> 0 && maxchunks
<= MAXCHUNKS
);
1378 * Calculate the actual slab size. maxchunks will be recalculated
1381 slab_desire
= chunk_offset
+ chunk_size
* maxchunks
;
1382 slab_size
= 8 * MAXCHUNKS
;
1383 power
= 3 + MAXCHUNKS_BITS
;
1384 while (slab_size
< slab_desire
) {
1390 * Do a quick recalculation based on the actual slab size but not
1391 * yet dealing with whether the slab header is in-band or out-of-band.
1392 * The purpose here is to see if we can reasonably reduce slab_size
1393 * to a power of 4 to allow more chunk sizes to use the same slab
1396 if ((power
& 1) && slab_size
> 32768) {
1397 maxchunks
= (slab_size
- chunk_offset
) / chunk_size
;
1398 if (maxchunks
>= MAXCHUNKS
/ 8) {
1403 if ((power
& 2) && slab_size
> 32768 * 4) {
1404 maxchunks
= (slab_size
- chunk_offset
) / chunk_size
;
1405 if (maxchunks
>= MAXCHUNKS
/ 4) {
1411 * This case occurs when the slab_size is larger than 1/1024 available
1414 nswath
= slab_size
/ NREGIONS_SIZE
;
1415 if (nswath
> NREGIONS
)
1420 * Try to allocate from our current best region for this zi
1422 region_mask
= ~(slab_size
- 1);
1423 ri
= slgd
->zone
[zi
].best_region
;
1424 if (Regions
[ri
].mask
== region_mask
) {
1425 if ((slab
= _vmem_alloc(ri
, slab_size
)) != NULL
)
1430 * Try to find an existing region to allocate from. The normal
1431 * case will be for allocations that are less than 1/1024 available
1432 * UVM, which fit into a single Regions[] entry.
1434 while (slab_size
<= NREGIONS_SIZE
) {
1436 for (ri
= 0; ri
< NREGIONS
; ++ri
) {
1437 if (rx
< 0 && Regions
[ri
].mask
== 0)
1439 if (Regions
[ri
].mask
== region_mask
) {
1440 slab
= _vmem_alloc(ri
, slab_size
);
1442 slgd
->zone
[zi
].best_region
= ri
;
1452 * This can fail, retry either way
1454 atomic_cmpset_ptr((void **)&Regions
[rx
].mask
,
1456 (void *)region_mask
);
1461 for (ri
= 0; ri
< NREGIONS
; ri
+= nswath
) {
1462 if (Regions
[ri
].mask
== region_mask
) {
1463 slab
= _vmem_alloc(ri
, slab_size
);
1465 slgd
->zone
[zi
].best_region
= ri
;
1470 for (j
= nswath
- 1; j
>= 0; --j
) {
1471 if (Regions
[ri
+j
].mask
!= 0)
1480 * We found a candidate, try to allocate it backwards so
1481 * another thread racing a slaballoc() does not see the
1482 * mask in the base index position until we are done.
1484 * We can safely zero-out any partial allocations because
1485 * the mask is only accessed from the base index. Any other
1486 * threads racing us will fail prior to us clearing the mask.
1490 for (j
= nswath
- 1; j
>= 0; --j
) {
1491 if (!atomic_cmpset_ptr((void **)&Regions
[rx
+j
].mask
,
1492 NULL
, (void *)region_mask
)) {
1493 while (++j
< nswath
)
1494 Regions
[rx
+j
].mask
= 0;
1502 * Fill in the new slab in region ri. If the slab_size completely
1503 * fills one or more region slots we move the slab structure out of
1504 * band which should optimize the chunking (particularly for a power
1508 region
= &Regions
[ri
];
1509 MASSERT(region
->slab
== NULL
);
1510 if (slab_size
>= NREGIONS_SIZE
) {
1512 slab
= memalloc(sizeof(*slab
), 0);
1513 bzero(slab
, sizeof(*slab
));
1514 slab
->chunks
= save
;
1515 for (j
= 0; j
< nswath
; ++j
)
1516 region
[j
].slab
= slab
;
1519 bzero(slab
, sizeof(*slab
));
1520 slab
->chunks
= (char *)slab
+ chunk_offset
;
1524 * Calculate the start of the chunks memory and recalculate the
1525 * actual number of chunks the slab can hold.
1527 maxchunks
= (slab_size
- chunk_offset
) / chunk_size
;
1528 if (maxchunks
> MAXCHUNKS
)
1529 maxchunks
= MAXCHUNKS
;
1532 * And fill in the rest
1534 slab
->magic
= ZALLOC_SLAB_MAGIC
;
1535 slab
->navail
= maxchunks
;
1536 slab
->nmax
= maxchunks
;
1537 slab
->slab_size
= slab_size
;
1538 slab
->chunk_size
= chunk_size
;
1539 slab
->zone_index
= zi
;
1541 slab
->state
= UNKNOWN
;
1542 slab
->region
= region
;
1544 for (ri
= 0; ri
< maxchunks
; ri
+= LONG_BITS
) {
1545 if (ri
+ LONG_BITS
<= maxchunks
)
1546 slab
->bitmap
[ri
>> LONG_BITS_SHIFT
] = ULONG_MAX
;
1548 slab
->bitmap
[ri
>> LONG_BITS_SHIFT
] =
1549 (1LU << (maxchunks
- ri
)) - 1;
1558 slabfree(slab_t slab
)
1563 if (slab
->region
->slab
== slab
) {
1567 nswath
= slab
->slab_size
/ NREGIONS_SIZE
;
1568 for (j
= 0; j
< nswath
; ++j
)
1569 slab
->region
[j
].slab
= NULL
;
1571 _vmem_free(slab
->chunks
, slab
->slab_size
);
1578 _vmem_free(slab
, slab
->slab_size
);
1583 * Terminate a slab's use in the current thread. The slab may still have
1584 * outstanding allocations and thus not be deallocatable.
1587 slabterm(slglobaldata_t slgd
, slab_t slab
)
1589 slglobaldata_t sldepot
;
1590 struct zoneinfo
*zinfo
;
1591 int zi
= slab
->zone_index
;
1595 sldepot
= &slglobaldepot
;
1596 zinfo
= &sldepot
->zone
[zi
];
1599 * Move the slab to the avail list or the empty list.
1602 _SPINLOCK(&sldepot
->lock
);
1603 if (slab
->navail
== slab
->nmax
) {
1604 slab
->state
= EMPTY
;
1605 slab
->next
= zinfo
->empty_base
;
1606 zinfo
->empty_base
= slab
;
1607 ++zinfo
->empty_count
;
1609 slab
->state
= AVAIL
;
1610 slab
->next
= zinfo
->avail_base
;
1611 zinfo
->avail_base
= slab
;
1612 ++zinfo
->avail_count
;
1616 * Clean extra slabs out of the empty list
1618 while (zinfo
->empty_count
> opt_cache
) {
1619 slab
= zinfo
->empty_base
;
1620 zinfo
->empty_base
= slab
->next
;
1621 --zinfo
->empty_count
;
1622 slab
->state
= UNKNOWN
;
1624 _SPINUNLOCK(&sldepot
->lock
);
1627 _SPINLOCK(&sldepot
->lock
);
1630 _SPINUNLOCK(&sldepot
->lock
);
1636 * Directly map memory in PAGE_SIZE'd chunks with the specified
1639 * Alignment must be a multiple of PAGE_SIZE.
1641 * Size must be >= alignment.
1644 _vmem_alloc(int ri
, size_t slab_size
)
1646 char *baddr
= (void *)((uintptr_t)ri
<< NREGIONS_SHIFT
);
1652 if (slab_size
< NREGIONS_SIZE
)
1653 eaddr
= baddr
+ NREGIONS_SIZE
;
1655 eaddr
= baddr
+ slab_size
;
1658 * This usually just works but might not.
1660 addr
= mmap(baddr
, slab_size
, PROT_READ
|PROT_WRITE
,
1661 MAP_PRIVATE
| MAP_ANON
| MAP_SIZEALIGN
, -1, 0);
1662 if (addr
== MAP_FAILED
) {
1665 if (addr
< baddr
|| addr
+ slab_size
> eaddr
) {
1666 munmap(addr
, slab_size
);
1671 * Check alignment. The misaligned offset is also the excess
1672 * amount. If misaligned unmap the excess so we have a chance of
1673 * mapping at the next alignment point and recursively try again.
1675 * BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB block alignment
1676 * aaaaaaaaa aaaaaaaaaaa aa mis-aligned allocation
1677 * xxxxxxxxx final excess calculation
1678 * ^ returned address
1680 excess
= (uintptr_t)addr
& (slab_size
- 1);
1682 excess
= slab_size
- excess
;
1685 munmap(save
+ excess
, slab_size
- excess
);
1686 addr
= _vmem_alloc(ri
, slab_size
);
1687 munmap(save
, excess
);
1690 if (addr
< baddr
|| addr
+ slab_size
> eaddr
) {
1691 munmap(addr
, slab_size
);
1694 excess
= (uintptr_t)addr
& (slab_size
- 1);
1702 * Free a chunk of memory allocated with _vmem_alloc()
1705 _vmem_free(void *ptr
, size_t size
)
1711 * Panic on fatal conditions
1714 _mpanic(const char *ctl
, ...)
1718 if (malloc_panic
== 0) {
1721 vfprintf(stderr
, ctl
, va
);
1722 fprintf(stderr
, "\n");
1729 __weak_reference(__aligned_alloc
, aligned_alloc
);
1730 __weak_reference(__malloc
, malloc
);
1731 __weak_reference(__calloc
, calloc
);
1732 __weak_reference(__posix_memalign
, posix_memalign
);
1733 __weak_reference(__realloc
, realloc
);
1734 __weak_reference(__free
, free
);