/*
 * 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)
{
        /* ignore error from stub if not threaded */
        pthread_key_create(&thread_malloc_key, _nmalloc_thr_destructor);
}

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