xref: /dragonfly/lib/libc/stdlib/dmalloc.c (revision e6d22e9b)

/*
 * DMALLOC.C	- Dillon's malloc
 *
 * Copyright (c) 2011,2017 The DragonFly Project. All rights reserved.
 *
 * This code is derived from software contributed to The DragonFly Project
 * by Matthew Dillon <dillon@backplane.com>.
 *
 * 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 modified slab allocator as a drop-in replacement
 * for the libc malloc().  The slab algorithm has been adjusted to support
 * dynamic sizing of slabs which effectively allows slabs to be used for
 * allocations of any size.  Because of this we neither have a small-block
 * allocator or a big-block allocator and the code paths are simplified.
 *
 * To support dynamic slab sizing available user virtual memory is broken
 * down into ~1024 regions.  Each region has fixed slab size whos value is
 * set when the region is opened up for use.  The free() path simply applies
 * a mask based on the region to the pointer to acquire the base of the
 * governing slab structure.
 *
 * Regions[NREGIONS]	(1024)
 *
 * 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
 *	32768-65535	4096		8
 *	... continues forever ...	4 zones
 *
 *	For a 2^63 memory space each doubling >= 64K is broken down into
 *	4 chunking zones, so we support 88 + (48 * 4) = 280 zones.
 *
 *			   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.
 *    + ability to allocate arbitrarily large chunks of memory
 *    + realloc will reuse the passed pointer if possible, within the
 *	limitations of the zone chunking.
 *
 * On top of the slab allocator we also implement a 16-entry-per-thread
 * magazine cache for allocations <= NOMSLABSIZE.
 *
 *				FUTURE FEATURES
 *
 *    + [better] garbage collection
 *    + better initial sizing.
 *
 * TUNING
 *
 * The value of the environment variable MALLOC_OPTIONS is a character string
 * containing various flags to tune nmalloc.  Upper case letters enabled
 * or increase the feature, lower case disables or decreases the feature.
 *
 * U		Enable UTRACE for all operations, observable with ktrace.
 *		Diasbled by default.
 *
 * Z		Zero out allocations, otherwise allocations (except for
 *		calloc) will contain garbage.
 *		Disabled by default.
 *
 * H		Pass a hint with madvise() about unused pages.
 *		Disabled by default.
 *		Not currently implemented.
 *
 * F		Disable local per-thread caching.
 *		Disabled by default.
 *
 * C		Increase (decrease) how much excess cache to retain.
 *		Set to 4 by default.
 */

/* cc -shared -fPIC -g -O -I/usr/src/lib/libc/include -o dmalloc.so dmalloc.c */

#ifndef STANDALONE_DEBUG
#include "libc_private.h"
#endif

#include <sys/param.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/queue.h>
#include <sys/ktrace.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stddef.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include <errno.h>
#include <pthread.h>
#include <limits.h>

#include <machine/atomic.h>
#include <machine/cpufunc.h>

#ifdef STANDALONE_DEBUG
void _nmalloc_thr_init(void);
#else
#include "spinlock.h"
#include "un-namespace.h"
#endif

#ifndef MAP_SIZEALIGN
#define MAP_SIZEALIGN	0
#endif

#if SSIZE_MAX == 0x7FFFFFFF
#define ADDRBITS	32
#define UVM_BITS	32	/* worst case */
#else
#define ADDRBITS	64
#define UVM_BITS	48	/* worst case XXX */
#endif

#if LONG_MAX == 0x7FFFFFFF
#define LONG_BITS	32
#define LONG_BITS_SHIFT	5
#else
#define LONG_BITS	64
#define LONG_BITS_SHIFT	6
#endif

#define LOCKEDPTR	((void *)(intptr_t)-1)

/*
 * Regions[]
 */
#define NREGIONS_BITS	10
#define NREGIONS	(1 << NREGIONS_BITS)
#define NREGIONS_MASK	(NREGIONS - 1)
#define NREGIONS_SHIFT	(UVM_BITS - NREGIONS_BITS)
#define NREGIONS_SIZE	(1LU << NREGIONS_SHIFT)

typedef struct region *region_t;
typedef struct slglobaldata *slglobaldata_t;
typedef struct slab *slab_t;

struct region {
	uintptr_t	mask;
	slab_t		slab;	/* conditional out of band slab */
};

static struct region Regions[NREGIONS];

/*
 * Number of chunking zones available
 */
#define CHUNKFACTOR	8
#if ADDRBITS == 32
#define NZONES		(16 + 9 * CHUNKFACTOR + 16 * CHUNKFACTOR)
#else
#define NZONES		(16 + 9 * CHUNKFACTOR + 48 * CHUNKFACTOR)
#endif

static int MaxChunks[NZONES];

#define NDEPOTS		8		/* must be power of 2 */

/*
 * Maximum number of chunks per slab, governed by the allocation bitmap in
 * each slab.  The maximum is reduced for large chunk sizes.
 */
#define MAXCHUNKS	(LONG_BITS * LONG_BITS)
#define MAXCHUNKS_BITS	(LONG_BITS_SHIFT * LONG_BITS_SHIFT)
#define LITSLABSIZE	(32 * 1024)
#define NOMSLABSIZE	(2 * 1024 * 1024)
#define BIGSLABSIZE	(128 * 1024 * 1024)

#define ZALLOC_SLAB_MAGIC	0x736c6162	/* magic sanity */

TAILQ_HEAD(slab_list, slab);

/*
 * A slab structure
 */
struct slab {
	struct slab	*next;		/* slabs with available space */
	TAILQ_ENTRY(slab) entry;
	int32_t		magic;		/* magic number for sanity check */
	u_int		navail;		/* number of free elements available */
	u_int		nmax;
	u_int		free_bit;	/* free hint bitno */
	u_int		free_index;	/* free hint index */
	u_long		bitmap[LONG_BITS]; /* free chunks */
	size_t		slab_size;	/* size of entire slab */
	size_t		chunk_size;	/* chunk size for validation */
	int		zone_index;
	enum { UNKNOWN, AVAIL, EMPTY, FULL } state;
	int		flags;
	region_t	region;		/* related region */
	char		*chunks;	/* chunk base */
	slglobaldata_t	slgd;		/* localized to thread else NULL */
};

/*
 * per-thread data + global depot
 *
 * NOTE: The magazine shortcut is only used for per-thread data.
 */
#define NMAGSHORTCUT	16

struct slglobaldata {
	spinlock_t	lock;		/* only used by slglobaldepot */
	struct zoneinfo {
		slab_t	avail_base;
		slab_t	empty_base;
		int	best_region;
		int	mag_index;
		int	avail_count;
		int	empty_count;
		void	*mag_shortcut[NMAGSHORTCUT];
	} zone[NZONES];
	struct slab_list full_zones;	/* via entry */
	int		masked;
	int		biggest_index;
	size_t		nslabs;
};

#define SLAB_ZEROD		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 SAFLAG_ZERO	0x00000001

/*
 * 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.
 *
 * WARNING: A limited number of spinlocks are available, BIGXSIZE should
 *	    not be larger then 64.
 */
#ifdef INVARIANTS
#define WEIRD_ADDR      0xdeadc0de
#endif

/*
 * Thread control
 */

#define MASSERT(exp)	do { if (__predict_false(!(exp)))	\
				_mpanic("assertion: %s in %s",	\
				#exp, __func__);		\
			    } while (0)

/*
 * With this attribute set, do not require a function call for accessing
 * this variable when the code is compiled -fPIC.
 *
 * Must be empty for libc_rtld (similar to __thread)
 */
#if defined(__LIBC_RTLD)
#define TLS_ATTRIBUTE
#else
#define TLS_ATTRIBUTE __attribute__ ((tls_model ("initial-exec")));
#endif

static __thread struct slglobaldata slglobal TLS_ATTRIBUTE;
static pthread_key_t thread_malloc_key;
static pthread_once_t thread_malloc_once = PTHREAD_ONCE_INIT;
static struct slglobaldata slglobaldepot;

static int opt_madvise = 0;
static int opt_free = 0;
static int opt_cache = 4;
static int opt_utrace = 0;
static int g_malloc_flags = 0;
static int malloc_panic;

#ifdef INVARIANTS
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
};
#endif

static void *memalloc(size_t size, int flags);
static void *memrealloc(void *ptr, size_t size);
static void memfree(void *ptr, int);
static int memalign(void **memptr, size_t alignment, size_t size);
static slab_t slaballoc(int zi, size_t chunking, size_t chunk_size);
static void slabfree(slab_t slab);
static void slabterm(slglobaldata_t slgd, slab_t slab);
static void *_vmem_alloc(int ri, size_t slab_size);
static void _vmem_free(void *ptr, size_t slab_size);
static void _mpanic(const char *ctl, ...) __printflike(1, 2);
#ifndef STANDALONE_DEBUG
static void malloc_init(void) __constructor(101);
#else
static void malloc_init(void) __constructor(101);
#endif


struct nmalloc_utrace {
	void *p;
	size_t s;
	void *r;
};

#define UTRACE(a, b, c)						\
	if (opt_utrace) {					\
		struct nmalloc_utrace ut = {			\
			.p = (a),				\
			.s = (b),				\
			.r = (c)				\
		};						\
		utrace(&ut, sizeof(ut));			\
	}

#ifdef INVARIANTS
/*
 * If enabled any memory allocated without M_ZERO is initialized to -1.
 */
static int  use_malloc_pattern;
#endif

static void
malloc_init(void)
{
	const char *p = NULL;

	TAILQ_INIT(&slglobal.full_zones);

	Regions[0].mask = -1; /* disallow activity in lowest region */

	if (issetugid() == 0)
		p = getenv("MALLOC_OPTIONS");

	for (; p != NULL && *p != '\0'; p++) {
		switch(*p) {
		case 'u':
			opt_utrace = 0;
			break;
		case 'U':
			opt_utrace = 1;
			break;
		case 'h':
			opt_madvise = 0;
			break;
		case 'H':
			opt_madvise = 1;
			break;
		case 'c':
			if (opt_cache > 0)
				--opt_cache;
			break;
		case 'C':
			++opt_cache;
			break;
		case 'f':
			opt_free = 0;
			break;
		case 'F':
			opt_free = 1;
			break;
		case 'z':
			g_malloc_flags = 0;
			break;
		case 'Z':
			g_malloc_flags = SAFLAG_ZERO;
			break;
		default:
			break;
		}
	}

	UTRACE((void *) -1, 0, NULL);
}

/*
 * We have to install a handler for nmalloc thread teardowns when
 * the thread is created.  We cannot delay this because destructors in
 * sophisticated userland programs can call malloc() for the first time
 * during their thread exit.
 *
 * This routine is called directly from pthreads.
 */
static void _nmalloc_thr_init_once(void);
static void _nmalloc_thr_destructor(void *thrp);

void
_nmalloc_thr_init(void)
{
	static int did_init;

	TAILQ_INIT(&slglobal.full_zones);

	if (slglobal.masked)
		return;

	slglobal.masked = 1;
	if (did_init == 0) {
		did_init = 1;
		pthread_once(&thread_malloc_once, _nmalloc_thr_init_once);
	}
	pthread_setspecific(thread_malloc_key, &slglobal);
	slglobal.masked = 0;
}

void
_nmalloc_thr_prepfork(void)
{
	if (__isthreaded)
		_SPINLOCK(&slglobaldepot.lock);
}

void
_nmalloc_thr_parentfork(void)
{
	if (__isthreaded)
		_SPINUNLOCK(&slglobaldepot.lock);
}

void
_nmalloc_thr_childfork(void)
{
	if (__isthreaded)
		_SPINUNLOCK(&slglobaldepot.lock);
}

/*
 * Called just once
 */
static void
_nmalloc_thr_init_once(void)
{
	int error;

	error = pthread_key_create(&thread_malloc_key, _nmalloc_thr_destructor);
	if (error)
		abort();
}

/*
 * Called for each thread undergoing exit
 *
 * Move all of the thread's slabs into a depot.
 */
static void
_nmalloc_thr_destructor(void *thrp)
{
	slglobaldata_t slgd = thrp;
	struct zoneinfo *zinfo;
	slab_t slab;
	void *ptr;
	int i;
	int j;

	slgd->masked = 1;

	for (i = 0; i <= slgd->biggest_index; i++) {
		zinfo = &slgd->zone[i];

		while ((j = zinfo->mag_index) > 0) {
			--j;
			ptr = zinfo->mag_shortcut[j];
			zinfo->mag_shortcut[j] = NULL;	/* SAFETY */
			zinfo->mag_index = j;
			memfree(ptr, 0);
		}

		while ((slab = zinfo->empty_base) != NULL) {
			zinfo->empty_base = slab->next;
			--zinfo->empty_count;
			slabterm(slgd, slab);
		}

		while ((slab = zinfo->avail_base) != NULL) {
			zinfo->avail_base = slab->next;
			--zinfo->avail_count;
			slabterm(slgd, slab);
		}

		while ((slab = TAILQ_FIRST(&slgd->full_zones)) != NULL) {
			TAILQ_REMOVE(&slgd->full_zones, slab, entry);
			slabterm(slgd, slab);
		}
	}
}

/*
 * Calculate the zone index for the allocation request size and set the
 * allocation request size to that particular zone's chunk size.
 *
 * Minimum alignment is 16 bytes for allocations >= 16 bytes to conform
 * with malloc requirements for intel/amd.
 */
static __inline int
zoneindex(size_t *bytes, size_t *chunking)
{
	size_t n = (size_t)*bytes;
	size_t x;
	size_t c;
	int i;

	if (n < 128) {
		if (n < 16) {
			*bytes = n = (n + 7) & ~7;
			*chunking = 8;
			return(n / 8 - 1);	/* 8 byte chunks, 2 zones */
		} else {
			*bytes = n = (n + 15) & ~15;
			*chunking = 16;
			return(n / 16 + 2);	/* 16 byte chunks, 8 zones */
		}
	}
	if (n < 4096) {
		x = 256;
		c = x / (CHUNKFACTOR * 2);
		i = 16;
	} else {
		x = 8192;
		c = x / (CHUNKFACTOR * 2);
		i = 16 + CHUNKFACTOR * 5;  /* 256->512,1024,2048,4096,8192 */
	}
	while (n >= x) {
		x <<= 1;
		c <<= 1;
		i += CHUNKFACTOR;
		if (x == 0)
			_mpanic("slaballoc: byte value too high");
	}
	*bytes = n = roundup2(n, c);
	*chunking = c;
	return (i + n / c - CHUNKFACTOR);
#if 0
	*bytes = n = (n + c - 1) & ~(c - 1);
	*chunking = c;
	return (n / c + i);

	if (n < 256) {
		*bytes = n = (n + 15) & ~15;
		*chunking = 16;
		return(n / (CHUNKINGLO*2) + CHUNKINGLO*1 - 1);
	}
	if (n < 8192) {
		if (n < 512) {
			*bytes = n = (n + 31) & ~31;
			*chunking = 32;
			return(n / (CHUNKINGLO*4) + CHUNKINGLO*2 - 1);
		}
		if (n < 1024) {
			*bytes = n = (n + 63) & ~63;
			*chunking = 64;
			return(n / (CHUNKINGLO*8) + CHUNKINGLO*3 - 1);
		}
		if (n < 2048) {
			*bytes = n = (n + 127) & ~127;
			*chunking = 128;
			return(n / (CHUNKINGLO*16) + CHUNKINGLO*4 - 1);
		}
		if (n < 4096) {
			*bytes = n = (n + 255) & ~255;
			*chunking = 256;
			return(n / (CHUNKINGLO*32) + CHUNKINGLO*5 - 1);
		}
		*bytes = n = (n + 511) & ~511;
		*chunking = 512;
		return(n / (CHUNKINGLO*64) + CHUNKINGLO*6 - 1);
	}
	if (n < 16384) {
		*bytes = n = (n + 1023) & ~1023;
		*chunking = 1024;
		return(n / (CHUNKINGLO*128) + CHUNKINGLO*7 - 1);
	}
	if (n < 32768) {				/* 16384-32767 */
		*bytes = n = (n + 2047) & ~2047;
		*chunking = 2048;
		return(n / (CHUNKINGLO*256) + CHUNKINGLO*8 - 1);
	}
	if (n < 65536) {
		*bytes = n = (n + 4095) & ~4095;	/* 32768-65535 */
		*chunking = 4096;
		return(n / (CHUNKINGLO*512) + CHUNKINGLO*9 - 1);
	}

	x = 131072;
	c = 8192;
	i = CHUNKINGLO*10 - 1;

	while (n >= x) {
		x <<= 1;
		c <<= 1;
		i += CHUNKINGHI;
		if (x == 0)
			_mpanic("slaballoc: byte value too high");
	}
	*bytes = n = (n + c - 1) & ~(c - 1);
	*chunking = c;
	return (n / c + i);
#endif
}

/*
 * malloc() - call internal slab allocator
 */
void *
__malloc(size_t size)
{
	void *ptr;

	ptr = memalloc(size, 0);
	if (ptr == NULL)
		errno = ENOMEM;
	else
		UTRACE(0, size, ptr);
	return(ptr);
}

/*
 * calloc() - call internal slab allocator
 */
void *
__calloc(size_t number, size_t size)
{
	void *ptr;

	ptr = memalloc(number * size, SAFLAG_ZERO);
	if (ptr == NULL)
		errno = ENOMEM;
	else
		UTRACE(0, number * size, ptr);
	return(ptr);
}

/*
 * 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)
{
	void *ret;

	if (ptr == NULL)
		ret = memalloc(size, 0);
	else
		ret = memrealloc(ptr, size);
	if (ret == NULL)
		errno = ENOMEM;
	else
		UTRACE(ptr, size, ret);
	return(ret);
}

/*
 * aligned_alloc()
 *
 * Allocate (size) bytes with a alignment of (alignment).
 */
void *
__aligned_alloc(size_t alignment, size_t size)
{
	void *ptr;
	int rc;

	ptr = NULL;
	rc = memalign(&ptr, alignment, size);
	if (rc)
		errno = rc;

	return (ptr);
}

/*
 * posix_memalign()
 *
 * Allocate (size) bytes with a alignment of (alignment), where (alignment)
 * is a power of 2 >= sizeof(void *).
 */
int
__posix_memalign(void **memptr, size_t alignment, size_t size)
{
	int rc;

	/*
	 * OpenGroup spec issue 6 check
	 */
	if (alignment < sizeof(void *)) {
		*memptr = NULL;
		return(EINVAL);
	}

	rc = memalign(memptr, alignment, size);

	return (rc);
}

/*
 * The slab allocator will allocate on power-of-2 boundaries up to at least
 * PAGE_SIZE.  Otherwise we use the zoneindex mechanic to find a zone
 * matching the requirements.
 */
static int
memalign(void **memptr, size_t alignment, size_t size)
{

	if (alignment < 1) {
		*memptr = NULL;
		return(EINVAL);
	}

	/*
	 * OpenGroup spec issue 6 check
	 */
	if ((alignment | (alignment - 1)) + 1 != (alignment << 1)) {
		*memptr = NULL;
		return(EINVAL);
	}

	/*
	 * XXX for now just find the nearest power of 2 >= size and also
	 * >= alignment and allocate that.
	 */
	while (alignment < size) {
		alignment <<= 1;
		if (alignment == 0)
			_mpanic("posix_memalign: byte value too high");
	}
	*memptr = memalloc(alignment, 0);
	return(*memptr ? 0 : ENOMEM);
}

/*
 * free() (SLAB ALLOCATOR) - do the obvious
 */
void
__free(void *ptr)
{
	if (ptr) {
		UTRACE(ptr, 0, 0);
		memfree(ptr, 0);
	}
}

/*
 * memalloc()	(SLAB ALLOCATOR)
 *
 *	Allocate memory via the slab allocator.
 */
static void *
memalloc(size_t size, int flags)
{
	slglobaldata_t slgd;
	struct zoneinfo *zinfo;
	slab_t slab;
	size_t chunking;
	int bmi;
	int bno;
	u_long *bmp;
	int zi;
#ifdef INVARIANTS
	int i;
#endif
	int j;
	char *obj;

	/*
	 * If 0 bytes is requested we have to return a unique pointer, allocate
	 * at least one byte.
	 */
	if (size == 0)
		size = 1;

	/* Capture global flags */
	flags |= g_malloc_flags;

	/* Compute allocation zone; zoneindex will panic on excessive sizes */
	zi = zoneindex(&size, &chunking);
	MASSERT(zi < NZONES);
	if (size == 0)
		return(NULL);

	/*
	 * Try magazine shortcut first
	 */
	slgd = &slglobal;
	zinfo = &slgd->zone[zi];

	if ((j = zinfo->mag_index) != 0) {
		zinfo->mag_index = --j;
		obj = zinfo->mag_shortcut[j];
		zinfo->mag_shortcut[j] = NULL;	/* SAFETY */
		if (flags & SAFLAG_ZERO)
			bzero(obj, size);
		return obj;
	}

	/*
	 * Locate a slab with available space.  If no slabs are available
	 * back-off to the empty list and if we still come up dry allocate
	 * a new slab (which will try the depot first).
	 */
retry:
	if ((slab = zinfo->avail_base) == NULL) {
		if ((slab = zinfo->empty_base) == NULL) {
			/*
			 * Still dry
			 */
			slab = slaballoc(zi, chunking, size);
			if (slab == NULL)
				return(NULL);
			slab->next = zinfo->avail_base;
			zinfo->avail_base = slab;
			++zinfo->avail_count;
			slab->state = AVAIL;
			if (slgd->biggest_index < zi)
				slgd->biggest_index = zi;
			++slgd->nslabs;
		} else {
			/*
			 * Pulled from empty list
			 */
			zinfo->empty_base = slab->next;
			slab->next = zinfo->avail_base;
			zinfo->avail_base = slab;
			++zinfo->avail_count;
			slab->state = AVAIL;
			--zinfo->empty_count;
		}
	}

	/*
	 * Allocate a chunk out of the slab.  HOT PATH
	 *
	 * Only the thread owning the slab can allocate out of it.
	 *
	 * NOTE: The last bit in the bitmap is always marked allocated so
	 *	 we cannot overflow here.
	 */
	bno = slab->free_bit;
	bmi = slab->free_index;
	bmp = &slab->bitmap[bmi];
	if (*bmp & (1LU << bno)) {
		atomic_clear_long(bmp, 1LU << bno);
		obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) * size;
		slab->free_bit = (bno + 1) & (LONG_BITS - 1);
		atomic_add_int(&slab->navail, -1);
		if (flags & SAFLAG_ZERO)
			bzero(obj, size);
		return (obj);
	}

	/*
	 * Allocate a chunk out of a slab.  COLD PATH
	 */
	if (slab->navail == 0) {
		zinfo->avail_base = slab->next;
		--zinfo->avail_count;
		slab->state = FULL;
		TAILQ_INSERT_TAIL(&slgd->full_zones, slab, entry);
		goto retry;
	}

	while (bmi < LONG_BITS) {
		bmp = &slab->bitmap[bmi];
		if (*bmp) {
			bno = bsflong(*bmp);
			atomic_clear_long(bmp, 1LU << bno);
			obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) *
					     size;
			slab->free_index = bmi;
			slab->free_bit = (bno + 1) & (LONG_BITS - 1);
			atomic_add_int(&slab->navail, -1);
			if (flags & SAFLAG_ZERO)
				bzero(obj, size);
			return (obj);
		}
		++bmi;
	}
	bmi = 0;
	while (bmi < LONG_BITS) {
		bmp = &slab->bitmap[bmi];
		if (*bmp) {
			bno = bsflong(*bmp);
			atomic_clear_long(bmp, 1LU << bno);
			obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) *
					     size;
			slab->free_index = bmi;
			slab->free_bit = (bno + 1) & (LONG_BITS - 1);
			atomic_add_int(&slab->navail, -1);
			if (flags & SAFLAG_ZERO)
				bzero(obj, size);
			return (obj);
		}
		++bmi;
	}
	_mpanic("slaballoc: corrupted zone: navail %d", slab->navail);
	/* not reached */
	return NULL;
}

/*
 * Reallocate memory within the chunk
 */
static void *
memrealloc(void *ptr, size_t nsize)
{
	region_t region;
	slab_t slab;
	size_t osize;
	char *obj;
	int flags = 0;

	/*
	 * If 0 bytes is requested we have to return a unique pointer, allocate
	 * at least one byte.
	 */
	if (nsize == 0)
		nsize = 1;

	/* Capture global flags */
	flags |= g_malloc_flags;

	/*
	 * Locate the zone by looking up the dynamic slab size mask based
	 * on the memory region the allocation resides in.
	 */
	region = &Regions[((uintptr_t)ptr >> NREGIONS_SHIFT) & NREGIONS_MASK];
	if ((slab = region->slab) == NULL)
		slab = (void *)((uintptr_t)ptr & region->mask);
	MASSERT(slab->magic == ZALLOC_SLAB_MAGIC);
	osize = slab->chunk_size;
	if (nsize <= osize) {
		if (osize < 32 || nsize >= osize / 2) {
			obj = ptr;
			if ((flags & SAFLAG_ZERO) && nsize < osize)
				bzero(obj + nsize, osize - nsize);
			return(obj);
		}
	}

	/*
	 * Otherwise resize the object
	 */
	obj = memalloc(nsize, 0);
	if (obj) {
		if (nsize > osize)
			nsize = osize;
		bcopy(ptr, obj, nsize);
		memfree(ptr, 0);
	}
	return (obj);
}

/*
 * free (SLAB ALLOCATOR)
 *
 * Free a memory block previously allocated by malloc.
 *
 * MPSAFE
 */
static void
memfree(void *ptr, int flags)
{
	region_t region;
	slglobaldata_t slgd;
	slab_t slab;
	slab_t stmp;
	slab_t *slabp;
	int bmi;
	int bno;
	int j;
	u_long *bmp;

	/*
	 * Locate the zone by looking up the dynamic slab size mask based
	 * on the memory region the allocation resides in.
	 *
	 * WARNING!  The slab may be owned by another thread!
	 */
	region = &Regions[((uintptr_t)ptr >> NREGIONS_SHIFT) & NREGIONS_MASK];
	if ((slab = region->slab) == NULL)
		slab = (void *)((uintptr_t)ptr & region->mask);
	MASSERT(slab != NULL);
	MASSERT(slab->magic == ZALLOC_SLAB_MAGIC);

#ifdef INVARIANTS
	/*
	 * 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.
	 */
	if (slab->chunk_size < sizeof(weirdary))
		bcopy(weirdary, ptr, slab->chunk_size);
	else
		bcopy(weirdary, ptr, sizeof(weirdary));
#endif
	slgd = &slglobal;

	/*
	 * Use mag_shortcut[] when possible
	 */
	if (slgd->masked == 0 && slab->chunk_size <= NOMSLABSIZE) {
		struct zoneinfo *zinfo;

		zinfo = &slgd->zone[slab->zone_index];
		j = zinfo->mag_index;
		if (j < NMAGSHORTCUT) {
			zinfo->mag_shortcut[j] = ptr;
			zinfo->mag_index = j + 1;
			return;
		}
	}

	/*
	 * Free to slab and increment navail.  We can delay incrementing
	 * navail to prevent the slab from being destroyed out from under
	 * us while we do other optimizations.
	 */
	bno = ((uintptr_t)ptr - (uintptr_t)slab->chunks) / slab->chunk_size;
	bmi = bno >> LONG_BITS_SHIFT;
	bno &= (LONG_BITS - 1);
	bmp = &slab->bitmap[bmi];

	MASSERT(bmi >= 0 && bmi < slab->nmax);
	MASSERT((*bmp & (1LU << bno)) == 0);
	atomic_set_long(bmp, 1LU << bno);

	if (slab->slgd == slgd) {
		/*
		 * We can only do the following if we own the slab.  Note
		 * that navail can be incremented by any thread even if
		 * we own the slab.
		 */
		struct zoneinfo *zinfo;

		atomic_add_int(&slab->navail, 1);
		if (slab->free_index > bmi) {
			slab->free_index = bmi;
			slab->free_bit = bno;
		} else if (slab->free_index == bmi &&
			   slab->free_bit > bno) {
			slab->free_bit = bno;
		}
		zinfo = &slgd->zone[slab->zone_index];

		/*
		 * Freeing an object from a full slab makes it less than
		 * full.  The slab must be moved to the available list.
		 *
		 * If the available list has too many slabs, release some
		 * to the depot.
		 */
		if (slab->state == FULL) {
			TAILQ_REMOVE(&slgd->full_zones, slab, entry);
			slab->state = AVAIL;
			stmp = zinfo->avail_base;
			slab->next = stmp;
			zinfo->avail_base = slab;
			++zinfo->avail_count;
			while (zinfo->avail_count > opt_cache) {
				slab = zinfo->avail_base;
				zinfo->avail_base = slab->next;
				--zinfo->avail_count;
				slabterm(slgd, slab);
			}
			goto done;
		}

		/*
		 * If the slab becomes completely empty dispose of it in
		 * some manner.  By default each thread caches up to 4
		 * empty slabs.  Only small slabs are cached.
		 */
		if (slab->navail == slab->nmax && slab->state == AVAIL) {
			/*
			 * Remove slab from available queue
			 */
			slabp = &zinfo->avail_base;
			while ((stmp = *slabp) != slab)
				slabp = &stmp->next;
			*slabp = slab->next;
			--zinfo->avail_count;

			if (opt_free || opt_cache == 0) {
				/*
				 * If local caching is disabled cache the
				 * slab in the depot (or free it).
				 */
				slabterm(slgd, slab);
			} else if (slab->slab_size > BIGSLABSIZE) {
				/*
				 * We do not try to retain large slabs
				 * in per-thread caches.
				 */
				slabterm(slgd, slab);
			} else if (zinfo->empty_count > opt_cache) {
				/*
				 * We have too many slabs cached, but
				 * instead of freeing this one free
				 * an empty slab that's been idle longer.
				 *
				 * (empty_count does not change)
				 */
				stmp = zinfo->empty_base;
				slab->state = EMPTY;
				slab->next = stmp->next;
				zinfo->empty_base = slab;
				slabterm(slgd, stmp);
			} else {
				/*
				 * Cache the empty slab in our thread local
				 * empty list.
				 */
				++zinfo->empty_count;
				slab->state = EMPTY;
				slab->next = zinfo->empty_base;
				zinfo->empty_base = slab;
			}
		}
	} else if (slab->slgd == NULL && slab->navail + 1 == slab->nmax) {
		slglobaldata_t sldepot;

		/*
		 * If freeing to a slab owned by the global depot, and
		 * the slab becomes completely EMPTY, try to move it to
		 * the correct list.
		 */
		sldepot = &slglobaldepot;
		if (__isthreaded)
			_SPINLOCK(&sldepot->lock);
		if (slab->slgd == NULL && slab->navail + 1 == slab->nmax) {
			struct zoneinfo *zinfo;

			/*
			 * Move the slab to the empty list
			 */
			MASSERT(slab->state == AVAIL);
			atomic_add_int(&slab->navail, 1);
			zinfo = &sldepot->zone[slab->zone_index];
			slabp = &zinfo->avail_base;
			while (slab != *slabp)
				slabp = &(*slabp)->next;
			*slabp = slab->next;
			--zinfo->avail_count;

			/*
			 * Clean out excessive empty entries from the
			 * depot.
			 */
			slab->state = EMPTY;
			slab->next = zinfo->empty_base;
			zinfo->empty_base = slab;
			++zinfo->empty_count;
			while (zinfo->empty_count > opt_cache) {
				slab = zinfo->empty_base;
				zinfo->empty_base = slab->next;
				--zinfo->empty_count;
				slab->state = UNKNOWN;
				if (__isthreaded)
					_SPINUNLOCK(&sldepot->lock);
				slabfree(slab);
				if (__isthreaded)
					_SPINLOCK(&sldepot->lock);
			}
		} else {
			atomic_add_int(&slab->navail, 1);
		}
		if (__isthreaded)
			_SPINUNLOCK(&sldepot->lock);
	} else {
		/*
		 * We can't act on the slab other than by adjusting navail
		 * (and the bitmap which we did in the common code at the
		 * top).
		 */
		atomic_add_int(&slab->navail, 1);
	}
done:
	;
}

/*
 * Allocate a new slab holding objects of size chunk_size.
 */
static slab_t
slaballoc(int zi, size_t chunking, size_t chunk_size)
{
	slglobaldata_t slgd;
	slglobaldata_t sldepot;
	struct zoneinfo *zinfo;
	region_t region;
	void *save;
	slab_t slab;
	size_t slab_desire;
	size_t slab_size;
	size_t region_mask;
	uintptr_t chunk_offset;
	ssize_t maxchunks;
	ssize_t tmpchunks;
	int ispower2;
	int power;
	int ri;
	int rx;
	int nswath;
	int j;

	/*
	 * First look in the depot.  Any given zone in the depot may be
	 * locked by being set to -1.  We have to do this instead of simply
	 * removing the entire chain because removing the entire chain can
	 * cause racing threads to allocate local slabs for large objects,
	 * resulting in a large VSZ.
	 */
	slgd = &slglobal;
	sldepot = &slglobaldepot;
	zinfo = &sldepot->zone[zi];

	if (zinfo->avail_base) {
		if (__isthreaded)
			_SPINLOCK(&sldepot->lock);
		slab = zinfo->avail_base;
		if (slab) {
			MASSERT(slab->slgd == NULL);
			slab->slgd = slgd;
			zinfo->avail_base = slab->next;
			--zinfo->avail_count;
			if (__isthreaded)
				_SPINUNLOCK(&sldepot->lock);
			return slab;
		}
		if (__isthreaded)
			_SPINUNLOCK(&sldepot->lock);
	}

	/*
	 * Nothing in the depot, allocate a new slab by locating or assigning
	 * a region and then using the system virtual memory allocator.
	 */
	slab = NULL;

	/*
	 * Calculate the start of the data chunks relative to the start
	 * of the slab.  If chunk_size is a power of 2 we guarantee
	 * power of 2 alignment.  If it is not we guarantee alignment
	 * to the chunk size.
	 */
	if ((chunk_size ^ (chunk_size - 1)) == (chunk_size << 1) - 1) {
		ispower2 = 1;
		chunk_offset = roundup2(sizeof(*slab), chunk_size);
	} else {
		ispower2 = 0;
		chunk_offset = sizeof(*slab) + chunking - 1;
		chunk_offset -= chunk_offset % chunking;
	}

	/*
	 * Calculate a reasonable number of chunks for the slab.
	 *
	 * Once initialized the MaxChunks[] array can only ever be
	 * reinitialized to the same value.
	 */
	maxchunks = MaxChunks[zi];
	if (maxchunks == 0) {
		/*
		 * First calculate how many chunks would fit in 1/1024
		 * available memory.  This is around 2MB on a 32 bit
		 * system and 128G on a 64-bit (48-bits available) system.
		 */
		maxchunks = (ssize_t)(NREGIONS_SIZE - chunk_offset) /
			    (ssize_t)chunk_size;
		if (maxchunks <= 0)
			maxchunks = 1;

		/*
		 * A slab cannot handle more than MAXCHUNKS chunks, but
		 * limit us to approximately MAXCHUNKS / 2 here because
		 * we may have to expand maxchunks when we calculate the
		 * actual power-of-2 slab.
		 */
		if (maxchunks > MAXCHUNKS / 2)
			maxchunks = MAXCHUNKS / 2;

		/*
		 * Try to limit the slabs to BIGSLABSIZE (~128MB).  Larger
		 * slabs will be created if the allocation does not fit.
		 */
		if (chunk_offset + chunk_size * maxchunks > BIGSLABSIZE) {
			tmpchunks = (ssize_t)(BIGSLABSIZE - chunk_offset) /
				    (ssize_t)chunk_size;
			if (tmpchunks <= 0)
				tmpchunks = 1;
			if (maxchunks > tmpchunks)
				maxchunks = tmpchunks;
		}

		/*
		 * If the slab calculates to greater than 2MB see if we
		 * can cut it down to ~2MB.  This controls VSZ but has
		 * no effect on run-time size or performance.
		 *
		 * This is very important in case you core dump and also
		 * important to reduce unnecessary region allocations.
		 */
		if (chunk_offset + chunk_size * maxchunks > NOMSLABSIZE) {
			tmpchunks = (ssize_t)(NOMSLABSIZE - chunk_offset) /
				    (ssize_t)chunk_size;
			if (tmpchunks < 1)
				tmpchunks = 1;
			if (maxchunks > tmpchunks)
				maxchunks = tmpchunks;
		}

		/*
		 * If the slab calculates to greater than 128K see if we
		 * can cut it down to ~128K while still maintaining a
		 * reasonably large number of chunks in each slab.  This
		 * controls VSZ but has no effect on run-time size or
		 * performance.
		 *
		 * This is very important in case you core dump and also
		 * important to reduce unnecessary region allocations.
		 */
		if (chunk_offset + chunk_size * maxchunks > LITSLABSIZE) {
			tmpchunks = (ssize_t)(LITSLABSIZE - chunk_offset) /
				    (ssize_t)chunk_size;
			if (tmpchunks < 32)
				tmpchunks = 32;
			if (maxchunks > tmpchunks)
				maxchunks = tmpchunks;
		}

		MaxChunks[zi] = maxchunks;
	}
	MASSERT(maxchunks > 0 && maxchunks <= MAXCHUNKS);

	/*
	 * Calculate the actual slab size.  maxchunks will be recalculated
	 * a little later.
	 */
	slab_desire = chunk_offset + chunk_size * maxchunks;
	slab_size = 8 * MAXCHUNKS;
	power = 3 + MAXCHUNKS_BITS;
	while (slab_size < slab_desire) {
		slab_size <<= 1;
		++power;
	}

	/*
	 * Do a quick recalculation based on the actual slab size but not
	 * yet dealing with whether the slab header is in-band or out-of-band.
	 * The purpose here is to see if we can reasonably reduce slab_size
	 * to a power of 4 to allow more chunk sizes to use the same slab
	 * size.
	 */
	if ((power & 1) && slab_size > 32768) {
		maxchunks = (slab_size - chunk_offset) / chunk_size;
		if (maxchunks >= MAXCHUNKS / 8) {
			slab_size >>= 1;
			--power;
		}
	}
	if ((power & 2) && slab_size > 32768 * 4) {
		maxchunks = (slab_size - chunk_offset) / chunk_size;
		if (maxchunks >= MAXCHUNKS / 4) {
			slab_size >>= 2;
			power -= 2;
		}
	}
	/*
	 * This case occurs when the slab_size is larger than 1/1024 available
	 * UVM.
	 */
	nswath = slab_size / NREGIONS_SIZE;
	if (nswath > NREGIONS)
		return (NULL);


	/*
	 * Try to allocate from our current best region for this zi
	 */
	region_mask = ~(slab_size - 1);
	ri = slgd->zone[zi].best_region;
	if (Regions[ri].mask == region_mask) {
		if ((slab = _vmem_alloc(ri, slab_size)) != NULL)
			goto found;
	}

	/*
	 * Try to find an existing region to allocate from.  The normal
	 * case will be for allocations that are less than 1/1024 available
	 * UVM, which fit into a single Regions[] entry.
	 */
	while (slab_size <= NREGIONS_SIZE) {
		rx = -1;
		for (ri = 0; ri < NREGIONS; ++ri) {
			if (rx < 0 && Regions[ri].mask == 0)
				rx = ri;
			if (Regions[ri].mask == region_mask) {
				slab = _vmem_alloc(ri, slab_size);
				if (slab) {
					slgd->zone[zi].best_region = ri;
					goto found;
				}
			}
		}

		if (rx < 0)
			return(NULL);

		/*
		 * This can fail, retry either way
		 */
		atomic_cmpset_ptr((void **)&Regions[rx].mask,
				  NULL,
				  (void *)region_mask);
	}

	for (;;) {
		rx = -1;
		for (ri = 0; ri < NREGIONS; ri += nswath) {
			if (Regions[ri].mask == region_mask) {
				slab = _vmem_alloc(ri, slab_size);
				if (slab) {
					slgd->zone[zi].best_region = ri;
					goto found;
				}
			}
			if (rx < 0) {
				for (j = nswath - 1; j >= 0; --j) {
					if (Regions[ri+j].mask != 0)
						break;
				}
				if (j < 0)
					rx = ri;
			}
		}

		/*
		 * We found a candidate, try to allocate it backwards so
		 * another thread racing a slaballoc() does not see the
		 * mask in the base index position until we are done.
		 *
		 * We can safely zero-out any partial allocations because
		 * the mask is only accessed from the base index.  Any other
		 * threads racing us will fail prior to us clearing the mask.
		 */
		if (rx < 0)
			return(NULL);
		for (j = nswath - 1; j >= 0; --j) {
			if (!atomic_cmpset_ptr((void **)&Regions[rx+j].mask,
					       NULL, (void *)region_mask)) {
				while (++j < nswath)
					Regions[rx+j].mask = 0;
				break;
			}
		}
		/* retry */
	}

	/*
	 * Fill in the new slab in region ri.  If the slab_size completely
	 * fills one or more region slots we move the slab structure out of
	 * band which should optimize the chunking (particularly for a power
	 * of 2).
	 */
found:
	region = &Regions[ri];
	MASSERT(region->slab == NULL);
	if (slab_size >= NREGIONS_SIZE) {
		save = slab;
		slab = memalloc(sizeof(*slab), 0);
		bzero(slab, sizeof(*slab));
		slab->chunks = save;
		for (j = 0; j < nswath; ++j)
			region[j].slab = slab;
		chunk_offset = 0;
	} else {
		bzero(slab, sizeof(*slab));
		slab->chunks = (char *)slab + chunk_offset;
	}

	/*
	 * Calculate the start of the chunks memory and recalculate the
	 * actual number of chunks the slab can hold.
	 */
	maxchunks = (slab_size - chunk_offset) / chunk_size;
	if (maxchunks > MAXCHUNKS)
		maxchunks = MAXCHUNKS;

	/*
	 * And fill in the rest
	 */
	slab->magic = ZALLOC_SLAB_MAGIC;
	slab->navail = maxchunks;
	slab->nmax = maxchunks;
	slab->slab_size = slab_size;
	slab->chunk_size = chunk_size;
	slab->zone_index = zi;
	slab->slgd = slgd;
	slab->state = UNKNOWN;
	slab->region = region;

	for (ri = 0; ri < maxchunks; ri += LONG_BITS) {
		if (ri + LONG_BITS <= maxchunks)
			slab->bitmap[ri >> LONG_BITS_SHIFT] = ULONG_MAX;
		else
			slab->bitmap[ri >> LONG_BITS_SHIFT] =
						(1LU << (maxchunks - ri)) - 1;
	}
	return (slab);
}

/*
 * Free a slab.
 */
static void
slabfree(slab_t slab)
{
	int nswath;
	int j;

	if (slab->region->slab == slab) {
		/*
		 * Out-of-band slab.
		 */
		nswath = slab->slab_size / NREGIONS_SIZE;
		for (j = 0; j < nswath; ++j)
			slab->region[j].slab = NULL;
		slab->magic = 0;
		_vmem_free(slab->chunks, slab->slab_size);
		memfree(slab, 0);
	} else {
		/*
		 * In-band slab.
		 */
		slab->magic = 0;
		_vmem_free(slab, slab->slab_size);
	}
}

/*
 * Terminate a slab's use in the current thread.  The slab may still have
 * outstanding allocations and thus not be deallocatable.
 */
static void
slabterm(slglobaldata_t slgd, slab_t slab)
{
	slglobaldata_t sldepot;
	struct zoneinfo *zinfo;
	int zi = slab->zone_index;

	slab->slgd = NULL;
	--slgd->nslabs;
	sldepot = &slglobaldepot;
	zinfo = &sldepot->zone[zi];

	/*
	 * Move the slab to the avail list or the empty list.
	 */
	if (__isthreaded)
		_SPINLOCK(&sldepot->lock);
	if (slab->navail == slab->nmax) {
		slab->state = EMPTY;
		slab->next = zinfo->empty_base;
		zinfo->empty_base = slab;
		++zinfo->empty_count;
	} else {
		slab->state = AVAIL;
		slab->next = zinfo->avail_base;
		zinfo->avail_base = slab;
		++zinfo->avail_count;
	}

	/*
	 * Clean extra slabs out of the empty list
	 */
	while (zinfo->empty_count > opt_cache) {
		slab = zinfo->empty_base;
		zinfo->empty_base = slab->next;
		--zinfo->empty_count;
		slab->state = UNKNOWN;
		if (__isthreaded)
			_SPINUNLOCK(&sldepot->lock);
		slabfree(slab);
		if (__isthreaded)
			_SPINLOCK(&sldepot->lock);
	}
	if (__isthreaded)
		_SPINUNLOCK(&sldepot->lock);
}

/*
 * _vmem_alloc()
 *
 *	Directly map memory in PAGE_SIZE'd chunks with the specified
 *	alignment.
 *
 *	Alignment must be a multiple of PAGE_SIZE.
 *
 *	Size must be >= alignment.
 */
static void *
_vmem_alloc(int ri, size_t slab_size)
{
	char *baddr = (void *)((uintptr_t)ri << NREGIONS_SHIFT);
	char *eaddr;
	char *addr;
	char *save;
	uintptr_t excess;

	if (slab_size < NREGIONS_SIZE)
		eaddr = baddr + NREGIONS_SIZE;
	else
		eaddr = baddr + slab_size;

	/*
	 * This usually just works but might not.
	 */
	addr = mmap(baddr, slab_size, PROT_READ|PROT_WRITE,
		    MAP_PRIVATE | MAP_ANON | MAP_SIZEALIGN, -1, 0);
	if (addr == MAP_FAILED) {
		return (NULL);
	}
	if (addr < baddr || addr + slab_size > eaddr) {
		munmap(addr, slab_size);
		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.
	 *
	 * BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB	block alignment
	 *   aaaaaaaaa aaaaaaaaaaa aa		mis-aligned allocation
	 *   xxxxxxxxx				final excess calculation
	 *   ^ returned address
	 */
	excess = (uintptr_t)addr & (slab_size - 1);
	while (excess) {
		excess = slab_size - excess;
		save = addr;

		munmap(save + excess, slab_size - excess);
		addr = _vmem_alloc(ri, slab_size);
		munmap(save, excess);
		if (addr == NULL)
			return (NULL);
		if (addr < baddr || addr + slab_size > eaddr) {
			munmap(addr, slab_size);
			return (NULL);
		}
		excess = (uintptr_t)addr & (slab_size - 1);
	}
	return (addr);
}

/*
 * _vmem_free()
 *
 *	Free a chunk of memory allocated with _vmem_alloc()
 */
static void
_vmem_free(void *ptr, 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();
}

__weak_reference(__aligned_alloc, aligned_alloc);
__weak_reference(__malloc, malloc);
__weak_reference(__calloc, calloc);
__weak_reference(__posix_memalign, posix_memalign);
__weak_reference(__realloc, realloc);
__weak_reference(__free, free);