From 82949828d84137a0576569c347cdfa5a22164447 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Wed, 22 Apr 2009 12:18:07 -0700 Subject: [PATCH] Replace the old BSD malloc code with a port of our slab allocator. This should give us a better base with which we can work up a more thread-friendly user malloc. Buildworld performance is about the same (just slightly faster). malloc performance is about twice as fast as the original. --- lib/libc/gen/_spinlock_stub.c | 14 +- lib/libc/include/spinlock.h | 2 + lib/libc/stdlib/Makefile.inc | 4 +- lib/libc/stdlib/nmalloc.c | 1019 ++++++++++++++++++++++++ lib/libthread_xu/thread/thr_spinlock.c | 20 + libexec/rtld-elf/malloc.c | 15 + 6 files changed, 1071 insertions(+), 3 deletions(-) create mode 100644 lib/libc/stdlib/nmalloc.c diff --git a/lib/libc/gen/_spinlock_stub.c b/lib/libc/gen/_spinlock_stub.c index 09caa74545..017f451943 100644 --- a/lib/libc/gen/_spinlock_stub.c +++ b/lib/libc/gen/_spinlock_stub.c @@ -41,6 +41,7 @@ long _atomic_lock_stub(volatile long *); void _spinlock_stub(spinlock_t *); +int _spintrylock_stub(spinlock_t *); void _spinunlock_stub(spinlock_t *); void _spinlock_debug_stub(spinlock_t *, char *, int); @@ -50,8 +51,9 @@ void _spinlock_debug_stub(spinlock_t *, char *, int); */ __weak_reference(_atomic_lock_stub,_atomic_lock); __weak_reference(_spinlock_stub,_spinlock); -__weak_reference(_spinlock_debug_stub,_spinlock_debug); +__weak_reference(_spintrylock_stub,_spintrylock); __weak_reference(_spinunlock_stub,_spinunlock); +__weak_reference(_spinlock_debug_stub,_spinlock_debug); /* * This function is a stub for the _atomic_lock function in libpthread. @@ -78,6 +80,16 @@ _spinunlock_stub(spinlock_t *lck __unused) { } +/* + * This function is a stub for the spintrylock function in libpthread. + * Return 0 on success, non-zero on failure. + */ +int +_spintrylock_stub(spinlock_t *lck __unused) +{ + return(0); +} + /* * This function is a stub for the debug spinlock function in libpthread. */ diff --git a/lib/libc/include/spinlock.h b/lib/libc/include/spinlock.h index e6961e4d70..4ce7c057eb 100644 --- a/lib/libc/include/spinlock.h +++ b/lib/libc/include/spinlock.h @@ -59,6 +59,7 @@ typedef struct { #else #define _SPINLOCK(_lck) _spinlock(_lck) #endif +#define _SPINTRYLOCK(_lck) _spintrylock(_lck) /* * Thread function prototype definitions: @@ -66,6 +67,7 @@ typedef struct { __BEGIN_DECLS long _atomic_lock (volatile long *); void _spinlock (spinlock_t *); +int _spintrylock (spinlock_t *); void _spinlock_debug (spinlock_t *, char *, int); void _spinunlock (spinlock_t *); __END_DECLS diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index ab514abba1..e5e5b9ff6e 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -6,9 +6,9 @@ .PATH: ${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib ${.CURDIR}/../libc/stdlib MISRCS+=a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ - bsearch.c calloc.c div.c exit.c getenv.c getopt.c getopt_long.c \ + bsearch.c div.c exit.c getenv.c getopt.c getopt_long.c \ getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \ - insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c malloc.c \ + insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c nmalloc.c \ merge.c qsort.c qsort_r.c radixsort.c rand.c random.c \ reallocf.c realpath.c remque.c strfmon.c strtoimax.c \ strtol.c strtoll.c strtonum.c strtoq.c strtoul.c strtoull.c \ diff --git a/lib/libc/stdlib/nmalloc.c b/lib/libc/stdlib/nmalloc.c new file mode 100644 index 0000000000..8392614455 --- /dev/null +++ b/lib/libc/stdlib/nmalloc.c @@ -0,0 +1,1019 @@ +/* + * NMALLOC.C - New Malloc (ported from kernel slab allocator) + * + * Copyright (c) 2003,2004,2009 The DragonFly Project. All rights reserved. + * + * This code is derived from software contributed to The DragonFly Project + * by Matthew Dillon + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name of The DragonFly Project nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific, prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +/* + * This module implements a slab allocator drop-in replacement for the + * libc malloc(). + * + * A slab allocator reserves a ZONE for each chunk size, then lays the + * chunks out in an array within the zone. Allocation and deallocation + * is nearly instantanious, and overhead losses are limited to a fixed + * worst-case amount. + * + * The slab allocator does not have to pre-initialize the list of + * free chunks for each zone, and the underlying VM will not be + * touched at all beyond the zone header until an actual allocation + * needs it. + * + * Slab management and locking is done on a per-zone basis. + * + * Alloc Size Chunking Number of zones + * 0-127 8 16 + * 128-255 16 8 + * 256-511 32 8 + * 512-1023 64 8 + * 1024-2047 128 8 + * 2048-4095 256 8 + * 4096-8191 512 8 + * 8192-16383 1024 8 + * 16384-32767 2048 8 + * + * Allocations >= ZoneLimit (16K) go directly to mmap and a hash table + * is used to locate for free. One and Two-page allocations use the + * zone mechanic to avoid excessive mmap()/munmap() calls. + * + * API FEATURES AND SIDE EFFECTS + * + * + power-of-2 sized allocations up to a page will be power-of-2 aligned. + * Above that power-of-2 sized allocations are page-aligned. Non + * power-of-2 sized allocations are aligned the same as the chunk + * size for their zone. + * + malloc(0) returns a special non-NULL value + * + ability to allocate arbitrarily large chunks of memory + * + realloc will reuse the passed pointer if possible, within the + * limitations of the zone chunking. + */ + +#include "libc_private.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "spinlock.h" +#include "un-namespace.h" + +/* + * Linked list of large allocations + */ +typedef struct bigalloc { + struct bigalloc *next; /* hash link */ + void *base; /* base pointer */ + u_long bytes; /* bytes allocated */ + u_long unused01; +} *bigalloc_t; + +/* + * Note that any allocations which are exact multiples of PAGE_SIZE, or + * which are >= ZALLOC_ZONE_LIMIT, will fall through to the kmem subsystem. + */ +#define ZALLOC_ZONE_LIMIT (16 * 1024) /* max slab-managed alloc */ +#define ZALLOC_MIN_ZONE_SIZE (32 * 1024) /* minimum zone size */ +#define ZALLOC_MAX_ZONE_SIZE (128 * 1024) /* maximum zone size */ +#define ZALLOC_ZONE_SIZE (64 * 1024) +#define ZALLOC_SLAB_MAGIC 0x736c6162 /* magic sanity */ +#define ZALLOC_SLAB_SLIDE 20 /* L1-cache skip */ + +#if ZALLOC_ZONE_LIMIT == 16384 +#define NZONES 72 +#elif ZALLOC_ZONE_LIMIT == 32768 +#define NZONES 80 +#else +#error "I couldn't figure out NZONES" +#endif + +/* + * Chunk structure for free elements + */ +typedef struct slchunk { + struct slchunk *c_Next; +} *slchunk_t; + +/* + * The IN-BAND zone header is placed at the beginning of each zone. + */ +struct slglobaldata; + +typedef struct slzone { + __int32_t z_Magic; /* magic number for sanity check */ + int z_NFree; /* total free chunks / ualloc space */ + struct slzone *z_Next; /* ZoneAry[] link if z_NFree non-zero */ + struct slglobaldata *z_GlobalData; + int z_NMax; /* maximum free chunks */ + char *z_BasePtr; /* pointer to start of chunk array */ + int z_UIndex; /* current initial allocation index */ + int z_UEndIndex; /* last (first) allocation index */ + int z_ChunkSize; /* chunk size for validation */ + int z_FirstFreePg; /* chunk list on a page-by-page basis */ + int z_ZoneIndex; + int z_Flags; + struct slchunk *z_PageAry[ZALLOC_ZONE_SIZE / PAGE_SIZE]; +#if defined(INVARIANTS) + __uint32_t z_Bitmap[]; /* bitmap of free chunks / sanity */ +#endif +} *slzone_t; + +typedef struct slglobaldata { + spinlock_t Spinlock; + slzone_t ZoneAry[NZONES];/* linked list of zones NFree > 0 */ + slzone_t FreeZones; /* whole zones that have become free */ + int NFreeZones; /* free zone count */ + int JunkIndex; +} *slglobaldata_t; + +#define SLZF_UNOTZEROD 0x0001 + +/* + * Misc constants. Note that allocations that are exact multiples of + * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module. + * IN_SAME_PAGE_MASK is used to sanity-check the per-page free lists. + */ +#define MIN_CHUNK_SIZE 8 /* in bytes */ +#define MIN_CHUNK_MASK (MIN_CHUNK_SIZE - 1) +#define ZONE_RELS_THRESH 4 /* threshold number of zones */ +#define IN_SAME_PAGE_MASK (~(intptr_t)PAGE_MASK | MIN_CHUNK_MASK) + +/* + * The WEIRD_ADDR is used as known text to copy into free objects to + * try to create deterministic failure cases if the data is accessed after + * free. + */ +#define WEIRD_ADDR 0xdeadc0de +#define MAX_COPY sizeof(weirdary) +#define ZERO_LENGTH_PTR ((void *)-8) + +#define BIGHSHIFT 10 /* bigalloc hash table */ +#define BIGHSIZE (1 << BIGHSHIFT) +#define BIGHMASK (BIGHSIZE - 1) +#define BIGXSIZE (BIGHSIZE / 16) /* bigalloc lock table */ +#define BIGXMASK (BIGXSIZE - 1) + +#define SLGD_MAX 4 /* parallel allocations */ + +#define SAFLAG_ZERO 0x0001 +#define SAFLAG_PASSIVE 0x0002 + +/* + * Thread control + */ + +#define arysize(ary) (sizeof(ary)/sizeof((ary)[0])) + +#define MASSERT(exp) do { if (__predict_false(!(exp))) \ + _mpanic("assertion: %s in %s", \ + #exp, __func__); \ + } while (0) + +/* + * Fixed globals (not per-cpu) + */ +static const int ZoneSize = ZALLOC_ZONE_SIZE; +static const int ZoneLimit = ZALLOC_ZONE_LIMIT; +static const int ZonePageCount = ZALLOC_ZONE_SIZE / PAGE_SIZE; +static const int ZoneMask = ZALLOC_ZONE_SIZE - 1; + +static struct slglobaldata SLGlobalData[SLGD_MAX]; +static bigalloc_t bigalloc_array[BIGHSIZE]; +static spinlock_t bigspin_array[BIGXSIZE]; +static int malloc_panic; + +static const int32_t weirdary[16] = { + WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, + WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, + WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, + WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR +}; + +static __thread slglobaldata_t LastSLGD = &SLGlobalData[0]; + +static void *_slaballoc(size_t size, int flags); +static void *_slabrealloc(void *ptr, size_t size); +static void _slabfree(void *ptr); +static void *_vmem_alloc(size_t bytes, size_t align, int flags); +static void _vmem_free(void *ptr, size_t bytes); +static void _mpanic(const char *ctl, ...); +#if defined(INVARIANTS) +static void chunk_mark_allocated(slzone_t z, void *chunk); +static void chunk_mark_free(slzone_t z, void *chunk); +#endif + +#ifdef INVARIANTS +/* + * If enabled any memory allocated without M_ZERO is initialized to -1. + */ +static int use_malloc_pattern; +#endif + +/* + * Thread locks. + * + * NOTE: slgd_trylock() returns 0 or EBUSY + */ +static __inline void +slgd_lock(slglobaldata_t slgd) +{ + if (__isthreaded) + _SPINLOCK(&slgd->Spinlock); +} + +static __inline int +slgd_trylock(slglobaldata_t slgd) +{ + if (__isthreaded) + return(_SPINTRYLOCK(&slgd->Spinlock)); + return(0); +} + +static __inline void +slgd_unlock(slglobaldata_t slgd) +{ + if (__isthreaded) + _SPINUNLOCK(&slgd->Spinlock); +} + +/* + * bigalloc hashing and locking support. + * + * Return an unmasked hash code for the passed pointer. + */ +static __inline int +_bigalloc_hash(void *ptr) +{ + int hv; + + hv = ((int)ptr >> PAGE_SHIFT) ^ ((int)ptr >> (PAGE_SHIFT + BIGHSHIFT)); + + return(hv); +} + +/* + * Lock the hash chain and return a pointer to its base for the specified + * address. + */ +static __inline bigalloc_t * +bigalloc_lock(void *ptr) +{ + int hv = _bigalloc_hash(ptr); + bigalloc_t *bigp; + + bigp = &bigalloc_array[hv & BIGHMASK]; + if (__isthreaded) + _SPINLOCK(&bigspin_array[hv & BIGXMASK]); + return(bigp); +} + +/* + * Lock the hash chain and return a pointer to its base for the specified + * address. + * + * BUT, if the hash chain is empty, just return NULL and do not bother + * to lock anything. + */ +static __inline bigalloc_t * +bigalloc_check_and_lock(void *ptr) +{ + int hv = _bigalloc_hash(ptr); + bigalloc_t *bigp; + + bigp = &bigalloc_array[hv & BIGHMASK]; + if (*bigp == NULL) + return(NULL); + if (__isthreaded) { + _SPINLOCK(&bigspin_array[hv & BIGXMASK]); + } + return(bigp); +} + +static __inline void +bigalloc_unlock(void *ptr) +{ + int hv; + + if (__isthreaded) { + hv = _bigalloc_hash(ptr); + _SPINUNLOCK(&bigspin_array[hv & BIGXMASK]); + } +} + +/* + * Calculate the zone index for the allocation request size and set the + * allocation request size to that particular zone's chunk size. + */ +static __inline int +zoneindex(size_t *bytes, size_t *chunking) +{ + size_t n = (unsigned int)*bytes; /* unsigned for shift opt */ + if (n < 128) { + *bytes = n = (n + 7) & ~7; + *chunking = 8; + return(n / 8 - 1); /* 8 byte chunks, 16 zones */ + } + if (n < 256) { + *bytes = n = (n + 15) & ~15; + *chunking = 16; + return(n / 16 + 7); + } + if (n < 8192) { + if (n < 512) { + *bytes = n = (n + 31) & ~31; + *chunking = 32; + return(n / 32 + 15); + } + if (n < 1024) { + *bytes = n = (n + 63) & ~63; + *chunking = 64; + return(n / 64 + 23); + } + if (n < 2048) { + *bytes = n = (n + 127) & ~127; + *chunking = 128; + return(n / 128 + 31); + } + if (n < 4096) { + *bytes = n = (n + 255) & ~255; + *chunking = 256; + return(n / 256 + 39); + } + *bytes = n = (n + 511) & ~511; + *chunking = 512; + return(n / 512 + 47); + } +#if ZALLOC_ZONE_LIMIT > 8192 + if (n < 16384) { + *bytes = n = (n + 1023) & ~1023; + *chunking = 1024; + return(n / 1024 + 55); + } +#endif +#if ZALLOC_ZONE_LIMIT > 16384 + if (n < 32768) { + *bytes = n = (n + 2047) & ~2047; + *chunking = 2048; + return(n / 2048 + 63); + } +#endif + _mpanic("Unexpected byte count %d", n); + return(0); +} + +/* + * malloc() - call internal slab allocator + */ +void * +malloc(size_t size) +{ + return(_slaballoc(size, 0)); +} + +/* + * calloc() - call internal slab allocator + */ +void * +calloc(size_t number, size_t size) +{ + return(_slaballoc(number * size, SAFLAG_ZERO)); +} + +/* + * realloc() (SLAB ALLOCATOR) + * + * We do not attempt to optimize this routine beyond reusing the same + * pointer if the new size fits within the chunking of the old pointer's + * zone. + */ +void * +realloc(void *ptr, size_t size) +{ + return(_slabrealloc(ptr, size)); +} + +void +free(void *ptr) +{ + _slabfree(ptr); +} + +/* + * _slaballoc() (SLAB ALLOCATOR) + * + * Allocate memory via the slab allocator. If the request is too large, + * or if it page-aligned beyond a certain size, we fall back to the + * KMEM subsystem + */ +static void * +_slaballoc(size_t size, int flags) +{ + slzone_t z; + slchunk_t chunk; + slglobaldata_t slgd; + int chunking; + int zi; +#ifdef INVARIANTS + int i; +#endif + int off; + + /* + * Handle the degenerate size == 0 case. Yes, this does happen. + * Return a special pointer. This is to maintain compatibility with + * the original malloc implementation. Certain devices, such as the + * adaptec driver, not only allocate 0 bytes, they check for NULL and + * also realloc() later on. Joy. + */ + if (size == 0) + return(ZERO_LENGTH_PTR); + + /* + * Handle large allocations directly. There should not be very many + * of these so performance is not a big issue. + * + * The backend allocator is pretty nasty on a SMP system. Use the + * slab allocator for one and two page-sized chunks even though we + * lose some efficiency. + */ + if (size >= ZoneLimit || + ((size & PAGE_MASK) == 0 && size > PAGE_SIZE*2)) { + bigalloc_t big; + bigalloc_t *bigp; + + size = (size + PAGE_MASK) & ~(size_t)PAGE_MASK; + chunk = _vmem_alloc(size, PAGE_SIZE, flags); + if (chunk == NULL) + return(NULL); + + big = _slaballoc(sizeof(struct bigalloc), 0); + bigp = bigalloc_lock(chunk); + big->base = chunk; + big->bytes = size; + big->unused01 = 0; + big->next = *bigp; + *bigp = big; + bigalloc_unlock(chunk); + + return(chunk); + } + + /* + * Multi-threading support. This needs work XXX. + * + * Choose a globaldata structure to allocate from. If we cannot + * immediately get the lock try a different one. + * + * LastSLGD is a per-thread global. + */ + slgd = LastSLGD; + if (slgd_trylock(slgd) != 0) { + if (++slgd == &SLGlobalData[SLGD_MAX]) + slgd = &SLGlobalData[0]; + LastSLGD = slgd; + slgd_lock(slgd); + } + + /* + * Attempt to allocate out of an existing zone. If all zones are + * exhausted pull one off the free list or allocate a new one. + * + * Note: zoneindex() will panic of size is too large. + */ + zi = zoneindex(&size, &chunking); + MASSERT(zi < NZONES); + + if ((z = slgd->ZoneAry[zi]) == NULL) { + /* + * Pull the zone off the free list. If the zone on + * the free list happens to be correctly set up we + * do not have to reinitialize it. + */ + if ((z = slgd->FreeZones) != NULL) { + slgd->FreeZones = z->z_Next; + --slgd->NFreeZones; + if (z->z_ChunkSize == size) { + z->z_Magic = ZALLOC_SLAB_MAGIC; + z->z_Next = slgd->ZoneAry[zi]; + slgd->ZoneAry[zi] = z; + goto have_zone; + } + bzero(z, sizeof(struct slzone)); + z->z_Flags |= SLZF_UNOTZEROD; + } else { + z = _vmem_alloc(ZoneSize, ZoneSize, flags); + if (z == NULL) + goto fail; + } + + /* + * How big is the base structure? + */ +#if defined(INVARIANTS) + /* + * Make room for z_Bitmap. An exact calculation is + * somewhat more complicated so don't make an exact + * calculation. + */ + off = offsetof(struct slzone, + z_Bitmap[(ZoneSize / size + 31) / 32]); + bzero(z->z_Bitmap, (ZoneSize / size + 31) / 8); +#else + off = sizeof(struct slzone); +#endif + + /* + * Align the storage in the zone based on the chunking. + * + * Guarentee power-of-2 alignment for power-of-2-sized + * chunks. Otherwise align based on the chunking size + * (typically 8 or 16 bytes for small allocations). + * + * NOTE: Allocations >= ZoneLimit are governed by the + * bigalloc code and typically only guarantee page-alignment. + * + * Set initial conditions for UIndex near the zone header + * to reduce unecessary page faults, vs semi-randomization + * to improve L1 cache saturation. + */ + if ((size | (size - 1)) + 1 == (size << 1)) + off = (off + size - 1) & ~(size - 1); + else + off = (off + chunking - 1) & ~(chunking - 1); + z->z_Magic = ZALLOC_SLAB_MAGIC; + z->z_GlobalData = slgd; + z->z_ZoneIndex = zi; + z->z_NMax = (ZoneSize - off) / size; + z->z_NFree = z->z_NMax; + z->z_BasePtr = (char *)z + off; + /*z->z_UIndex = z->z_UEndIndex = slgd->JunkIndex % z->z_NMax;*/ + z->z_UIndex = z->z_UEndIndex = 0; + z->z_ChunkSize = size; + z->z_FirstFreePg = ZonePageCount; + z->z_Next = slgd->ZoneAry[zi]; + slgd->ZoneAry[zi] = z; + if ((z->z_Flags & SLZF_UNOTZEROD) == 0) { + flags &= ~SAFLAG_ZERO; /* already zero'd */ + flags |= SAFLAG_PASSIVE; + } + + /* + * Slide the base index for initial allocations out of the + * next zone we create so we do not over-weight the lower + * part of the cpu memory caches. + */ + slgd->JunkIndex = (slgd->JunkIndex + ZALLOC_SLAB_SLIDE) + & (ZALLOC_MAX_ZONE_SIZE - 1); + } + + /* + * Ok, we have a zone from which at least one chunk is available. + * + * Remove us from the ZoneAry[] when we become empty + */ +have_zone: + MASSERT(z->z_NFree > 0); + + if (--z->z_NFree == 0) { + slgd->ZoneAry[zi] = z->z_Next; + z->z_Next = NULL; + } + + /* + * Locate a chunk in a free page. This attempts to localize + * reallocations into earlier pages without us having to sort + * the chunk list. A chunk may still overlap a page boundary. + */ + while (z->z_FirstFreePg < ZonePageCount) { + if ((chunk = z->z_PageAry[z->z_FirstFreePg]) != NULL) { +#ifdef DIAGNOSTIC + /* + * Diagnostic: c_Next is not total garbage. + */ + MASSERT(chunk->c_Next == NULL || + ((intptr_t)chunk->c_Next & IN_SAME_PAGE_MASK) == + ((intptr_t)chunk & IN_SAME_PAGE_MASK)); +#endif +#ifdef INVARIANTS + chunk_mark_allocated(z, chunk); +#endif + MASSERT((uintptr_t)chunk & ZoneMask); + z->z_PageAry[z->z_FirstFreePg] = chunk->c_Next; + goto done; + } + ++z->z_FirstFreePg; + } + + /* + * No chunks are available but NFree said we had some memory, + * so it must be available in the never-before-used-memory + * area governed by UIndex. The consequences are very + * serious if our zone got corrupted so we use an explicit + * panic rather then a KASSERT. + */ + chunk = (slchunk_t)(z->z_BasePtr + z->z_UIndex * size); + + if (++z->z_UIndex == z->z_NMax) + z->z_UIndex = 0; + if (z->z_UIndex == z->z_UEndIndex) { + if (z->z_NFree != 0) + _mpanic("slaballoc: corrupted zone"); + } + + if ((z->z_Flags & SLZF_UNOTZEROD) == 0) { + flags &= ~SAFLAG_ZERO; + flags |= SAFLAG_PASSIVE; + } +#if defined(INVARIANTS) + chunk_mark_allocated(z, chunk); +#endif + +done: + slgd_unlock(slgd); + if (flags & SAFLAG_ZERO) { + bzero(chunk, size); +#ifdef INVARIANTS + } else if ((flags & (SAFLAG_ZERO|SAFLAG_PASSIVE)) == 0) { + if (use_malloc_pattern) { + for (i = 0; i < size; i += sizeof(int)) { + *(int *)((char *)chunk + i) = -1; + } + } + /* avoid accidental double-free check */ + chunk->c_Next = (void *)-1; +#endif + } + return(chunk); +fail: + slgd_unlock(slgd); + return(NULL); +} + +/* + * Reallocate memory within the chunk + */ +static void * +_slabrealloc(void *ptr, size_t size) +{ + bigalloc_t *bigp; + void *nptr; + slzone_t z; + size_t chunking; + + if (ptr == NULL || ptr == ZERO_LENGTH_PTR) + return(_slaballoc(size, 0)); + + if (size == 0) { + free(ptr); + return(ZERO_LENGTH_PTR); + } + + /* + * Handle oversized allocations. XXX we really should require + * that a size be passed to free() instead of this nonsense. + */ + if ((bigp = bigalloc_check_and_lock(ptr)) != NULL) { + bigalloc_t big; + size_t bigbytes; + + while ((big = *bigp) != NULL) { + if (big->base == ptr) { + size = (size + PAGE_MASK) & ~(size_t)PAGE_MASK; + bigbytes = big->bytes; + bigalloc_unlock(ptr); + if (bigbytes == size) + return(ptr); + if ((nptr = _slaballoc(size, 0)) == NULL) + return(NULL); + if (size > bigbytes) + size = bigbytes; + bcopy(ptr, nptr, size); + _slabfree(ptr); + return(nptr); + } + bigp = &big->next; + } + bigalloc_unlock(ptr); + } + + /* + * Get the original allocation's zone. If the new request winds + * up using the same chunk size we do not have to do anything. + * + * NOTE: We don't have to lock the globaldata here, the fields we + * access here will not change at least as long as we have control + * over the allocation. + */ + z = (slzone_t)((uintptr_t)ptr & ~(uintptr_t)ZoneMask); + MASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC); + + /* + * Use zoneindex() to chunk-align the new size, as long as the + * new size is not too large. + */ + if (size < ZoneLimit) { + zoneindex(&size, &chunking); + if (z->z_ChunkSize == size) + return(ptr); + } + + /* + * Allocate memory for the new request size and copy as appropriate. + */ + if ((nptr = _slaballoc(size, 0)) != NULL) { + if (size > z->z_ChunkSize) + size = z->z_ChunkSize; + bcopy(ptr, nptr, size); + _slabfree(ptr); + } + + return(nptr); +} + +/* + * free (SLAB ALLOCATOR) + * + * Free a memory block previously allocated by malloc. Note that we do not + * attempt to uplodate ks_loosememuse as MP races could prevent us from + * checking memory limits in malloc. + * + * MPSAFE + */ +static void +_slabfree(void *ptr) +{ + slzone_t z; + slchunk_t chunk; + bigalloc_t big; + bigalloc_t *bigp; + slglobaldata_t slgd; + size_t size; + int pgno; + + /* + * Handle NULL frees and special 0-byte allocations + */ + if (ptr == NULL) + return; + if (ptr == ZERO_LENGTH_PTR) + return; + + /* + * Handle oversized allocations. + */ + if ((bigp = bigalloc_check_and_lock(ptr)) != NULL) { + while ((big = *bigp) != NULL) { + if (big->base == ptr) { + *bigp = big->next; + bigalloc_unlock(ptr); + size = big->bytes; + _slabfree(big); +#ifdef INVARIANTS + MASSERT(sizeof(weirdary) <= size); + bcopy(weirdary, ptr, sizeof(weirdary)); +#endif + _vmem_free(ptr, size); + return; + } + bigp = &big->next; + } + bigalloc_unlock(ptr); + } + + /* + * Zone case. Figure out the zone based on the fact that it is + * ZoneSize aligned. + */ + z = (slzone_t)((uintptr_t)ptr & ~(uintptr_t)ZoneMask); + MASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC); + + pgno = ((char *)ptr - (char *)z) >> PAGE_SHIFT; + chunk = ptr; + slgd = z->z_GlobalData; + slgd_lock(slgd); + +#ifdef INVARIANTS + /* + * Attempt to detect a double-free. To reduce overhead we only check + * if there appears to be link pointer at the base of the data. + */ + if (((intptr_t)chunk->c_Next - (intptr_t)z) >> PAGE_SHIFT == pgno) { + slchunk_t scan; + + for (scan = z->z_PageAry[pgno]; scan; scan = scan->c_Next) { + if (scan == chunk) + _mpanic("Double free at %p", chunk); + } + } + chunk_mark_free(z, chunk); +#endif + + /* + * Put weird data into the memory to detect modifications after + * freeing, illegal pointer use after freeing (we should fault on + * the odd address), and so forth. + */ +#ifdef INVARIANTS + if (z->z_ChunkSize < sizeof(weirdary)) + bcopy(weirdary, chunk, z->z_ChunkSize); + else + bcopy(weirdary, chunk, sizeof(weirdary)); +#endif + + /* + * Add this free non-zero'd chunk to a linked list for reuse, adjust + * z_FirstFreePg. + */ + chunk->c_Next = z->z_PageAry[pgno]; + z->z_PageAry[pgno] = chunk; + if (z->z_FirstFreePg > pgno) + z->z_FirstFreePg = pgno; + + /* + * Bump the number of free chunks. If it becomes non-zero the zone + * must be added back onto the appropriate list. + */ + if (z->z_NFree++ == 0) { + z->z_Next = slgd->ZoneAry[z->z_ZoneIndex]; + slgd->ZoneAry[z->z_ZoneIndex] = z; + } + + /* + * If the zone becomes totally free then move this zone to + * the FreeZones list. + * + * Do not madvise here, avoiding the edge case where a malloc/free + * loop is sitting on the edge of a new zone. + * + * We could leave at least one zone in the ZoneAry for the index, + * using something like the below, but while this might be fine + * for the kernel (who cares about ~10MB of wasted memory), it + * probably isn't such a good idea for a user program. + * + * && (z->z_Next || slgd->ZoneAry[z->z_ZoneIndex] != z) + */ + if (z->z_NFree == z->z_NMax) { + slzone_t *pz; + + pz = &slgd->ZoneAry[z->z_ZoneIndex]; + while (z != *pz) + pz = &(*pz)->z_Next; + *pz = z->z_Next; + z->z_Magic = -1; + z->z_Next = slgd->FreeZones; + slgd->FreeZones = z; + ++slgd->NFreeZones; + } + + /* + * Limit the number of zones we keep cached. + */ + while (slgd->NFreeZones > ZONE_RELS_THRESH) { + z = slgd->FreeZones; + slgd->FreeZones = z->z_Next; + --slgd->NFreeZones; + slgd_unlock(slgd); + _vmem_free(z, ZoneSize); + slgd_lock(slgd); + } + slgd_unlock(slgd); +} + +#if defined(INVARIANTS) +/* + * Helper routines for sanity checks + */ +static +void +chunk_mark_allocated(slzone_t z, void *chunk) +{ + int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize; + __uint32_t *bitptr; + + MASSERT(bitdex >= 0 && bitdex < z->z_NMax); + bitptr = &z->z_Bitmap[bitdex >> 5]; + bitdex &= 31; + MASSERT((*bitptr & (1 << bitdex)) == 0); + *bitptr |= 1 << bitdex; +} + +static +void +chunk_mark_free(slzone_t z, void *chunk) +{ + int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize; + __uint32_t *bitptr; + + MASSERT(bitdex >= 0 && bitdex < z->z_NMax); + bitptr = &z->z_Bitmap[bitdex >> 5]; + bitdex &= 31; + MASSERT((*bitptr & (1 << bitdex)) != 0); + *bitptr &= ~(1 << bitdex); +} + +#endif + +/* + * _vmem_alloc() + * + * Directly map memory in PAGE_SIZE'd chunks with the specified + * alignment. + * + * Alignment must be a multiple of PAGE_SIZE. + */ +static void * +_vmem_alloc(size_t size, size_t align, int flags) +{ + char *addr; + char *save; + size_t excess; + + /* + * Map anonymous private memory. + */ + addr = mmap(NULL, size, PROT_READ|PROT_WRITE, + MAP_PRIVATE|MAP_ANON, -1, 0); + if (addr == MAP_FAILED) { + errno = ENOMEM; + return(NULL); + } + + /* + * Check alignment. The misaligned offset is also the excess + * amount. If misaligned unmap the excess so we have a chance of + * mapping at the next alignment point and recursively try again. + */ + excess = (uintptr_t)addr & (align - 1); + if (excess) { + save = addr; + munmap(save + align - excess, excess); + addr = _vmem_alloc(size, align, flags); + munmap(save, align - excess); + } + return((void *)addr); +} + +/* + * _vmem_free() + * + * Free a chunk of memory allocated with _vmem_alloc() + */ +static void +_vmem_free(void *ptr, vm_size_t size) +{ + munmap(ptr, size); +} + +/* + * Panic on fatal conditions + */ +static void +_mpanic(const char *ctl, ...) +{ + va_list va; + + if (malloc_panic == 0) { + malloc_panic = 1; + va_start(va, ctl); + vfprintf(stderr, ctl, va); + fprintf(stderr, "\n"); + fflush(stderr); + va_end(va); + } + abort(); +} diff --git a/lib/libthread_xu/thread/thr_spinlock.c b/lib/libthread_xu/thread/thr_spinlock.c index 87b5bf7c85..da5b2e91ed 100644 --- a/lib/libthread_xu/thread/thr_spinlock.c +++ b/lib/libthread_xu/thread/thr_spinlock.c @@ -89,6 +89,26 @@ _spinlock(spinlock_t *lck) THR_UMTX_LOCK(curthread, (volatile umtx_t *)&lck->access_lock); } +/* + * Returns 0 on success, else EBUSY + */ +int +_spintrylock(spinlock_t *lck) +{ + struct pthread *curthread; + + if (!__isthreaded) + PANIC("Spinlock called when not threaded."); + if (!initialized) + PANIC("Spinlocks not initialized."); + if (lck->fname == NULL) + init_spinlock(lck); + + curthread = tls_get_curthread(); + return(THR_UMTX_TRYLOCK(curthread, + (volatile umtx_t *)&lck->access_lock)); +} + void _spinlock_debug(spinlock_t *lck, char *fname __unused, int lineno __unused) { diff --git a/libexec/rtld-elf/malloc.c b/libexec/rtld-elf/malloc.c index 04566f5c84..faea9f0ea3 100644 --- a/libexec/rtld-elf/malloc.c +++ b/libexec/rtld-elf/malloc.c @@ -234,6 +234,21 @@ malloc(nbytes) return ((char *)(op + 1)); } +/* + * Used by rtld.c, if we don't override it here the calloc from + * libc may try to pull in the malloc/realloc/free from libc too. + */ +void * +calloc(size_t num, size_t size) +{ + void *p; + + size *= num; + if ((p = malloc(size)) != NULL) + bzero(p, size); + return(p); +} + /* * Allocate more memory to the indicated bucket. */ -- 2.41.0