libc - Bring dmalloc in for x86-64
authorMatthew Dillon <dillon@apollo.backplane.com>
Sun, 13 Nov 2011 17:31:01 +0000 (09:31 -0800)
committerMatthew Dillon <dillon@apollo.backplane.com>
Sun, 13 Nov 2011 17:31:01 +0000 (09:31 -0800)
* Bring in a much faster allocator for x86-64.  DMalloc is a slab alloctor
  with dynamic slab sizing capabilities, allowing slabs to be used for
  all allocation sizes.  This simplifies the code paths considerably.

* DMalloc is optimized for heavy-use situations but will still retain a
  run size similar to the old nmalloc code.  The VSZ is going to be quite
  a bit bigger, though.  The best test is w/mysqld as mysql[d] allocates
  and frees memory at a very high rate.

* DMalloc is almost completely lockless.  Slabs become owned by threads
  which can then manipulate them trivially.  Frees can operate on foreign
  slabs in a lockless manner.  A depot is used primarily as a catch-all
  for thread exits.

Written-by: Matthew Dillon
lib/libc/stdlib/Makefile.inc
lib/libc/stdlib/dmalloc.c [new file with mode: 0644]

index d174603..a8c8842 100644 (file)
@@ -8,12 +8,18 @@
 MISRCS+=a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
        bsearch.c div.c exit.c getenv.c getopt.c getopt_long.c \
        getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \
-       insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c nmalloc.c \
+       insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \
        merge.c ptsname.c qsort.c qsort_r.c radixsort.c rand.c random.c \
        reallocf.c realpath.c remque.c strfmon.c strtoimax.c \
        strtol.c strtoll.c strtonum.c strtoq.c strtoul.c strtoull.c \
        strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c
 
+.if ${MACHINE_ARCH} == "x86_64"
+MISRCS+= dmalloc.c
+.else
+MISRCS+= nmalloc.c
+.endif
+
 # machine-dependent stdlib sources
 .if exists(${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib/Makefile.inc)
 .include "${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib/Makefile.inc"
diff --git a/lib/libc/stdlib/dmalloc.c b/lib/libc/stdlib/dmalloc.c
new file mode 100644 (file)
index 0000000..04d60ca
--- /dev/null
@@ -0,0 +1,1524 @@
+/*
+ * DMALLOC.C   - Dillon's malloc
+ *
+ * Copyright (c) 2011 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 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 the point where
+ * allocations, caching, and freeing, is screaming fast.
+ *
+ * There is very little interaction between threads.  A global depot accessed
+ * via atomic cmpxchg instructions (only! no spinlocks!) is used as a
+ * catch-all and to deal with thread exits and such.
+ *
+ * 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 unlimited ...     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.
+ *    + malloc(0) returns a special non-NULL value
+ *    + ability to allocate arbitrarily large chunks of memory
+ *    + realloc will reuse the passed pointer if possible, within the
+ *     limitations of the zone chunking.
+ *
+ *                             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/uio.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;
+};
+
+/*
+ * per-thread data
+ */
+struct slglobaldata {
+       struct zoneinfo {
+               slab_t  avail_base;
+               slab_t  empty_base;
+               int     best_region;
+               int     empty_count;
+       } zone[NZONES];
+       struct slab_list full_zones;            /* via entry */
+       int             masked;
+       int             biggest_index;
+       size_t          nslabs;
+       slglobaldata_t  sldepot;
+};
+
+#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.
+ */
+#define WEIRD_ADDR      0xdeadc0de
+#define MAX_COPY        sizeof(weirdary)
+
+#define arysize(ary)   (sizeof(ary)/sizeof((ary)[0]))
+
+/*
+ * 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 */
+#define TLS_ATTRIBUTE __attribute__ ((tls_model ("initial-exec")));
+
+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 sldepots[NDEPOTS];
+
+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;
+
+static const int32_t weirdary[16] = {
+       WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
+       WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
+       WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
+       WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR
+};
+
+static void *memalloc(size_t size, int flags);
+static void *memrealloc(void *ptr, size_t size);
+static void memfree(void *ptr, int);
+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(0);
+#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;
+
+       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);
+       _nmalloc_thr_init();
+}
+
+/*
+ * 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;
+       static int SLGI;
+       int slgi;
+
+       slgi = SLGI++;
+       cpu_ccfence();
+       TAILQ_INIT(&slglobal.full_zones);
+       slglobal.sldepot = &sldepots[slgi & (NDEPOTS - 1)];
+
+       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;
+}
+
+/*
+ * 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;
+       slab_t slab;
+       int i;
+
+       slgd->masked = 1;
+
+       for (i = 0; i <= slgd->biggest_index; i++) {
+               while ((slab = slgd->zone[i].empty_base) != NULL) {
+                       slgd->zone[i].empty_base = slab->next;
+                       slabterm(slgd, slab);
+               }
+
+               while ((slab = slgd->zone[i].avail_base) != NULL) {
+                       slgd->zone[i].avail_base = slab->next;
+                       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.
+ */
+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) {
+               *bytes = n = (n + 7) & ~7;
+               *chunking = 8;
+               return(n / 8);                  /* 8 byte chunks, 16 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 = (n + c - 1) & ~(c - 1);
+       *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);
+}
+
+/*
+ * posix_memalign()
+ *
+ * Allocate (size) bytes with a alignment of (alignment), where (alignment)
+ * is a power of 2 >= sizeof(void *).
+ *
+ * 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.
+ */
+int
+posix_memalign(void **memptr, size_t alignment, size_t size)
+{
+       size_t chunking;
+       int zi;
+
+       /*
+        * OpenGroup spec issue 6 checks
+        */
+       if ((alignment | (alignment - 1)) + 1 != (alignment << 1)) {
+               *memptr = NULL;
+               return(EINVAL);
+       }
+       if (alignment < sizeof(void *)) {
+               *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
+       size_t off;
+       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);
+
+       /*
+        * 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:
+       slgd = &slglobal;
+       zinfo = &slgd->zone[zi];
+       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;
+                       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;
+                       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;
+               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;
+       slglobaldata_t slgd;
+       slab_t slab;
+       size_t osize;
+       char *obj;
+       int flags;
+
+       /*
+        * 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;
+       char *obj;
+       int bmi;
+       int bno;
+       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
+
+       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);
+       atomic_add_int(&slab->navail, 1);
+
+       /*
+        * We can only do the following if we own the slab
+        */
+       slgd = &slglobal;
+       if (slab->slgd == slgd) {
+               struct zoneinfo *zinfo;
+
+               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 will move it to the
+                * available list.  If the available list already has a
+                * slab we terminate the full slab instead, moving it to
+                * the depot.
+                */
+               if (slab->state == FULL) {
+                       TAILQ_REMOVE(&slgd->full_zones, slab, entry);
+                       if (zinfo->avail_base == NULL) {
+                               slab->state = AVAIL;
+                               stmp = zinfo->avail_base;
+                               slab->next = stmp;
+                               zinfo->avail_base = slab;
+                       } else {
+                               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;
+
+                       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;
+                       }
+               }
+       }
+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;
+       slab_t stmp;
+       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 = slgd->sldepot;
+       zinfo = &sldepot->zone[zi];
+
+       while ((slab = zinfo->avail_base) != NULL) {
+               if ((void *)slab == LOCKEDPTR) {
+                       cpu_pause();
+                       continue;
+               }
+               if (atomic_cmpset_ptr(&zinfo->avail_base, slab, LOCKEDPTR)) {
+                       MASSERT(slab->slgd == NULL);
+                       slab->slgd = slgd;
+                       zinfo->avail_base = slab->next;
+                       return(slab);
+               }
+       }
+
+       /*
+        * 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 ^ (chunk_size - 1)) == (chunk_size << 1) - 1) {
+               ispower2 = 1;
+               chunk_offset = (sizeof(*slab) + (chunk_size - 1)) &
+                              ~(chunk_size - 1);
+       } 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 = slgd->sldepot;
+       struct zoneinfo *zinfo;
+       slab_t dnext;
+       int zi = slab->zone_index;
+
+       slab->slgd = NULL;
+       --slgd->nslabs;
+       zinfo = &sldepot->zone[zi];
+
+       /*
+        * If the slab can be freed and the depot is either locked or not
+        * empty, then free the slab.
+        */
+       if (slab->navail == slab->nmax && zinfo->avail_base) {
+               slab->state = UNKNOWN;
+               slabfree(slab);
+               return;
+       }
+       slab->state = AVAIL;
+
+       /*
+        * Link the slab into the depot
+        */
+       for (;;) {
+               dnext = zinfo->avail_base;
+               cpu_ccfence();
+               if ((void *)dnext == LOCKEDPTR) {
+                       cpu_pause();
+                       continue;
+               }
+               slab->next = dnext;
+               if (atomic_cmpset_ptr(&zinfo->avail_base, dnext, slab))
+                       break;
+       }
+}
+
+/*
+ * _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();
+}