lib/libc/stdlib/nmalloc.c

   1 /*
   2  * NMALLOC.C    - New Malloc (ported from kernel slab allocator)
   3  *
   4  * Copyright (c) 2003,2004,2009,2010 The DragonFly Project. All rights reserved.
   5  *
   6  * This code is derived from software contributed to The DragonFly Project
   7  * by Matthew Dillon <dillon@backplane.com> and by
   8  * Venkatesh Srinivas <me@endeavour.zapto.org>.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in
  18  *    the documentation and/or other materials provided with the
  19  *    distribution.
  20  * 3. Neither the name of The DragonFly Project nor the names of its
  21  *    contributors may be used to endorse or promote products derived
  22  *    from this software without specific, prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  25  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  27  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  28  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  29  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  30  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  32  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  33  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  34  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35  * SUCH DAMAGE.
  36  *
  37  * $Id: nmalloc.c,v 1.37 2010/07/23 08:20:35 vsrinivas Exp $
  38  */
  39 /*
  40  * This module implements a slab allocator drop-in replacement for the
  41  * libc malloc().
  42  *
  43  * A slab allocator reserves a ZONE for each chunk size, then lays the
  44  * chunks out in an array within the zone.  Allocation and deallocation
  45  * is nearly instantaneous, and overhead losses are limited to a fixed
  46  * worst-case amount.
  47  *
  48  * The slab allocator does not have to pre-initialize the list of
  49  * free chunks for each zone, and the underlying VM will not be
  50  * touched at all beyond the zone header until an actual allocation
  51  * needs it.
  52  *
  53  * Slab management and locking is done on a per-zone basis.
  54  *
  55  *      Alloc Size      Chunking        Number of zones
  56  *      0-127           8               16
  57  *      128-255         16              8
  58  *      256-511         32              8
  59  *      512-1023        64              8
  60  *      1024-2047       128             8
  61  *      2048-4095       256             8
  62  *      4096-8191       512             8
  63  *      8192-16383      1024            8
  64  *      16384-32767     2048            8
  65  *
  66  *      Allocations >= ZoneLimit (16K) go directly to mmap and a hash table
  67  *      is used to locate for free.  One and Two-page allocations use the
  68  *      zone mechanic to avoid excessive mmap()/munmap() calls.
  69  *
  70  *                         API FEATURES AND SIDE EFFECTS
  71  *
  72  *    + power-of-2 sized allocations up to a page will be power-of-2 aligned.
  73  *      Above that power-of-2 sized allocations are page-aligned.  Non
  74  *      power-of-2 sized allocations are aligned the same as the chunk
  75  *      size for their zone.
  76  *    + malloc(0) returns a special non-NULL value
  77  *    + ability to allocate arbitrarily large chunks of memory
  78  *    + realloc will reuse the passed pointer if possible, within the
  79  *      limitations of the zone chunking.
  80  *
  81  * Multithreaded enhancements for small allocations introduced August 2010.
  82  * These are in the spirit of 'libumem'. See:
  83  *      Bonwick, J.; Adams, J. (2001). "Magazines and Vmem: Extending the
  84  *      slab allocator to many CPUs and arbitrary resources". In Proc. 2001
  85  *      USENIX Technical Conference. USENIX Association.
  86  *
  87  * Oversized allocations employ the BIGCACHE mechanic whereby large
  88  * allocations may be handed significantly larger buffers, allowing them
  89  * to avoid mmap/munmap operations even through significant realloc()s.
  90  * The excess space is only trimmed if too many large allocations have been
  91  * given this treatment.
  92  *
  93  * TUNING
  94  *
  95  * The value of the environment variable MALLOC_OPTIONS is a character string
  96  * containing various flags to tune nmalloc.
  97  *
  98  * 'U'   / ['u']        Generate / do not generate utrace entries for ktrace(1)
  99  *                      This will generate utrace events for all malloc,
 100  *                      realloc, and free calls. There are tools (mtrplay) to
 101  *                      replay and allocation pattern or to graph heap structure
 102  *                      (mtrgraph) which can interpret these logs.
 103  * 'Z'   / ['z']        Zero out / do not zero all allocations.
 104  *                      Each new byte of memory allocated by malloc, realloc, or
 105  *                      reallocf will be initialized to 0. This is intended for
 106  *                      debugging and will affect performance negatively.
 107  * 'H'  /  ['h']        Pass a hint to the kernel about pages unused by the
 108  *                      allocation functions.
 109  */
 110
 111 /* cc -shared -fPIC -g -O -I/usr/src/lib/libc/include -o nmalloc.so nmalloc.c */
 112
 113 #include "libc_private.h"
 114
 115 #include <sys/param.h>
 116 #include <sys/types.h>
 117 #include <sys/mman.h>
 118 #include <sys/queue.h>
 119 #include <sys/uio.h>
 120 #include <sys/ktrace.h>
 121 #include <stdio.h>
 122 #include <stdint.h>
 123 #include <stdlib.h>
 124 #include <stdarg.h>
 125 #include <stddef.h>
 126 #include <unistd.h>
 127 #include <string.h>
 128 #include <fcntl.h>
 129 #include <errno.h>
 130 #include <pthread.h>
 131 #include <machine/atomic.h>
 132
 133 #include "spinlock.h"
 134 #include "un-namespace.h"
 135
 136
 137 /*
 138  * Linked list of large allocations
 139  */
 140 typedef struct bigalloc {
 141         struct bigalloc *next;  /* hash link */
 142         void    *base;          /* base pointer */
 143         u_long  active;         /* bytes active */
 144         u_long  bytes;          /* bytes allocated */
 145 } *bigalloc_t;
 146
 147 /*
 148  * Note that any allocations which are exact multiples of PAGE_SIZE, or
 149  * which are >= ZALLOC_ZONE_LIMIT, will fall through to the kmem subsystem.
 150  */
 151 #define ZALLOC_ZONE_LIMIT       (16 * 1024)     /* max slab-managed alloc */
 152 #define ZALLOC_MIN_ZONE_SIZE    (32 * 1024)     /* minimum zone size */
 153 #define ZALLOC_MAX_ZONE_SIZE    (128 * 1024)    /* maximum zone size */
 154 #define ZALLOC_ZONE_SIZE        (64 * 1024)
 155 #define ZALLOC_SLAB_MAGIC       0x736c6162      /* magic sanity */
 156 #define ZALLOC_SLAB_SLIDE       20              /* L1-cache skip */
 157
 158 #if ZALLOC_ZONE_LIMIT == 16384
 159 #define NZONES                  72
 160 #elif ZALLOC_ZONE_LIMIT == 32768
 161 #define NZONES                  80
 162 #else
 163 #error "I couldn't figure out NZONES"
 164 #endif
 165
 166 /*
 167  * Chunk structure for free elements
 168  */
 169 typedef struct slchunk {
 170         struct slchunk *c_Next;
 171 } *slchunk_t;
 172
 173 /*
 174  * The IN-BAND zone header is placed at the beginning of each zone.
 175  */
 176 struct slglobaldata;
 177
 178 typedef struct slzone {
 179         int32_t         z_Magic;        /* magic number for sanity check */
 180         int             z_NFree;        /* total free chunks / ualloc space */
 181         struct slzone *z_Next;          /* ZoneAry[] link if z_NFree non-zero */
 182         int             z_NMax;         /* maximum free chunks */
 183         char            *z_BasePtr;     /* pointer to start of chunk array */
 184         int             z_UIndex;       /* current initial allocation index */
 185         int             z_UEndIndex;    /* last (first) allocation index */
 186         int             z_ChunkSize;    /* chunk size for validation */
 187         int             z_FirstFreePg;  /* chunk list on a page-by-page basis */
 188         int             z_ZoneIndex;
 189         int             z_Flags;
 190         struct slchunk *z_PageAry[ZALLOC_ZONE_SIZE / PAGE_SIZE];
 191 #if defined(INVARIANTS)
 192         __uint32_t      z_Bitmap[];     /* bitmap of free chunks / sanity */
 193 #endif
 194 } *slzone_t;
 195
 196 typedef struct slglobaldata {
 197         spinlock_t      Spinlock;
 198         slzone_t        ZoneAry[NZONES];/* linked list of zones NFree > 0 */
 199         int             JunkIndex;
 200 } *slglobaldata_t;
 201
 202 #define SLZF_UNOTZEROD          0x0001
 203
 204 #define FASTSLABREALLOC         0x02
 205
 206 /*
 207  * Misc constants.  Note that allocations that are exact multiples of
 208  * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module.
 209  * IN_SAME_PAGE_MASK is used to sanity-check the per-page free lists.
 210  */
 211 #define MIN_CHUNK_SIZE          8               /* in bytes */
 212 #define MIN_CHUNK_MASK          (MIN_CHUNK_SIZE - 1)
 213 #define IN_SAME_PAGE_MASK       (~(intptr_t)PAGE_MASK | MIN_CHUNK_MASK)
 214
 215 /*
 216  * The WEIRD_ADDR is used as known text to copy into free objects to
 217  * try to create deterministic failure cases if the data is accessed after
 218  * free.
 219  *
 220  * WARNING: A limited number of spinlocks are available, BIGXSIZE should
 221  *          not be larger then 64.
 222  */
 223 #define WEIRD_ADDR      0xdeadc0de
 224 #define MAX_COPY        sizeof(weirdary)
 225 #define ZERO_LENGTH_PTR ((void *)&malloc_dummy_pointer)
 226
 227 #define BIGHSHIFT       10                      /* bigalloc hash table */
 228 #define BIGHSIZE        (1 << BIGHSHIFT)
 229 #define BIGHMASK        (BIGHSIZE - 1)
 230 #define BIGXSIZE        (BIGHSIZE / 16)         /* bigalloc lock table */
 231 #define BIGXMASK        (BIGXSIZE - 1)
 232
 233 /*
 234  * BIGCACHE caches oversized allocations.  Note that a linear search is
 235  * performed, so do not make the cache too large.
 236  *
 237  * BIGCACHE will garbage-collect excess space when the excess exceeds the
 238  * specified value.  A relatively large number should be used here because
 239  * garbage collection is expensive.
 240  */
 241 #define BIGCACHE        16
 242 #define BIGCACHE_MASK   (BIGCACHE - 1)
 243 #define BIGCACHE_LIMIT  (1024 * 1024)           /* size limit */
 244 #define BIGCACHE_EXCESS (16 * 1024 * 1024)      /* garbage collect */
 245
 246 #define SAFLAG_ZERO     0x0001
 247 #define SAFLAG_PASSIVE  0x0002
 248
 249 /*
 250  * Thread control
 251  */
 252
 253 #define arysize(ary)    (sizeof(ary)/sizeof((ary)[0]))
 254
 255 #define MASSERT(exp)    do { if (__predict_false(!(exp)))       \
 256                                 _mpanic("assertion: %s in %s",  \
 257                                 #exp, __func__);                \
 258                             } while (0)
 259
 260 /*
 261  * Magazines
 262  */
 263
 264 #define M_MAX_ROUNDS    64
 265 #define M_ZONE_ROUNDS   64
 266 #define M_LOW_ROUNDS    32
 267 #define M_INIT_ROUNDS   8
 268 #define M_BURST_FACTOR  8
 269 #define M_BURST_NSCALE  2
 270
 271 #define M_BURST         0x0001
 272 #define M_BURST_EARLY   0x0002
 273
 274 struct magazine {
 275         SLIST_ENTRY(magazine) nextmagazine;
 276
 277         int             flags;
 278         int             capacity;       /* Max rounds in this magazine */
 279         int             rounds;         /* Current number of free rounds */
 280         int             burst_factor;   /* Number of blocks to prefill with */
 281         int             low_factor;     /* Free till low_factor from full mag */
 282         void            *objects[M_MAX_ROUNDS];
 283 };
 284
 285 SLIST_HEAD(magazinelist, magazine);
 286
 287 static spinlock_t zone_mag_lock;
 288 static struct magazine zone_magazine = {
 289         .flags = M_BURST | M_BURST_EARLY,
 290         .capacity = M_ZONE_ROUNDS,
 291         .rounds = 0,
 292         .burst_factor = M_BURST_FACTOR,
 293         .low_factor = M_LOW_ROUNDS
 294 };
 295
 296 #define MAGAZINE_FULL(mp)       (mp->rounds == mp->capacity)
 297 #define MAGAZINE_NOTFULL(mp)    (mp->rounds < mp->capacity)
 298 #define MAGAZINE_EMPTY(mp)      (mp->rounds == 0)
 299 #define MAGAZINE_NOTEMPTY(mp)   (mp->rounds != 0)
 300
 301 /*
 302  * Each thread will have a pair of magazines per size-class (NZONES)
 303  * The loaded magazine will support immediate allocations, the previous
 304  * magazine will either be full or empty and can be swapped at need
 305  */
 306 typedef struct magazine_pair {
 307         struct magazine *loaded;
 308         struct magazine *prev;
 309 } magazine_pair;
 310
 311 /* A depot is a collection of magazines for a single zone. */
 312 typedef struct magazine_depot {
 313         struct magazinelist full;
 314         struct magazinelist empty;
 315         spinlock_t      lock;
 316 } magazine_depot;
 317
 318 typedef struct thr_mags {
 319         magazine_pair   mags[NZONES];
 320         struct magazine *newmag;
 321         int             init;
 322 } thr_mags;
 323
 324 /*
 325  * With this attribute set, do not require a function call for accessing
 326  * this variable when the code is compiled -fPIC. Empty for libc_rtld
 327  * (like __thread).
 328  */
 329 #ifdef __LIBC_RTLD
 330 #define TLS_ATTRIBUTE
 331 #else
 332 #define TLS_ATTRIBUTE __attribute__ ((tls_model ("initial-exec")))
 333 #endif
 334
 335 static int mtmagazine_free_live;
 336 static __thread thr_mags thread_mags TLS_ATTRIBUTE;
 337 static pthread_key_t thread_mags_key;
 338 static pthread_once_t thread_mags_once = PTHREAD_ONCE_INIT;
 339 static magazine_depot depots[NZONES];
 340
 341 /*
 342  * Fixed globals (not per-cpu)
 343  */
 344 static const int ZoneSize = ZALLOC_ZONE_SIZE;
 345 static const int ZoneLimit = ZALLOC_ZONE_LIMIT;
 346 static const int ZonePageCount = ZALLOC_ZONE_SIZE / PAGE_SIZE;
 347 static const int ZoneMask = ZALLOC_ZONE_SIZE - 1;
 348
 349 static int opt_madvise = 0;
 350 static int opt_utrace = 0;
 351 static int g_malloc_flags = 0;
 352 static struct slglobaldata      SLGlobalData;
 353 static bigalloc_t bigalloc_array[BIGHSIZE];
 354 static spinlock_t bigspin_array[BIGXSIZE];
 355 static volatile void *bigcache_array[BIGCACHE];         /* atomic swap */
 356 static volatile size_t bigcache_size_array[BIGCACHE];   /* SMP races ok */
 357 static volatile int bigcache_index;                     /* SMP races ok */
 358 static int malloc_panic;
 359 static int malloc_dummy_pointer;
 360 static size_t excess_alloc;                             /* excess big allocs */
 361
 362 static const int32_t weirdary[16] = {
 363         WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
 364         WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
 365         WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR,
 366         WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR
 367 };
 368
 369 static void *_slaballoc(size_t size, int flags);
 370 static void *_slabrealloc(void *ptr, size_t size);
 371 static void _slabfree(void *ptr, int, bigalloc_t *);
 372 static void *_vmem_alloc(size_t bytes, size_t align, int flags);
 373 static void _vmem_free(void *ptr, size_t bytes);
 374 static void *magazine_alloc(struct magazine *, int *);
 375 static int magazine_free(struct magazine *, void *);
 376 static void *mtmagazine_alloc(int zi);
 377 static int mtmagazine_free(int zi, void *);
 378 static void mtmagazine_init(void);
 379 static void mtmagazine_destructor(void *);
 380 static slzone_t zone_alloc(int flags);
 381 static void zone_free(void *z);
 382 static void _mpanic(const char *ctl, ...) __printflike(1, 2);
 383 static void malloc_init(void) __constructor(101);
 384 #if defined(INVARIANTS)
 385 static void chunk_mark_allocated(slzone_t z, void *chunk);
 386 static void chunk_mark_free(slzone_t z, void *chunk);
 387 #endif
 388
 389 struct nmalloc_utrace {
 390         void *p;
 391         size_t s;
 392         void *r;
 393 };
 394
 395 #define UTRACE(a, b, c)                                         \
 396         if (opt_utrace) {                                       \
 397                 struct nmalloc_utrace ut = {                    \
 398                         .p = (a),                               \
 399                         .s = (b),                               \
 400                         .r = (c)                                \
 401                 };                                              \
 402                 utrace(&ut, sizeof(ut));                        \
 403         }
 404
 405 #ifdef INVARIANTS
 406 /*
 407  * If enabled any memory allocated without M_ZERO is initialized to -1.
 408  */
 409 static int  use_malloc_pattern;
 410 #endif
 411
 412 static void
 413 malloc_init(void)
 414 {
 415         const char *p = NULL;
 416
 417         if (issetugid() == 0)
 418                 p = getenv("MALLOC_OPTIONS");
 419
 420         for (; p != NULL && *p != '\0'; p++) {
 421                 switch(*p) {
 422                 case 'u':       opt_utrace = 0; break;
 423                 case 'U':       opt_utrace = 1; break;
 424                 case 'h':       opt_madvise = 0; break;
 425                 case 'H':       opt_madvise = 1; break;
 426                 case 'z':       g_malloc_flags = 0; break;
 427                 case 'Z':       g_malloc_flags = SAFLAG_ZERO; break;
 428                 default:
 429                         break;
 430                 }
 431         }
 432
 433         UTRACE((void *) -1, 0, NULL);
 434 }
 435
 436 /*
 437  * We have to install a handler for nmalloc thread teardowns when
 438  * the thread is created.  We cannot delay this because destructors in
 439  * sophisticated userland programs can call malloc() for the first time
 440  * during their thread exit.
 441  *
 442  * This routine is called directly from pthreads.
 443  */
 444 void
 445 _nmalloc_thr_init(void)
 446 {
 447         thr_mags *tp;
 448
 449         /*
 450          * Disallow mtmagazine operations until the mtmagazine is
 451          * initialized.
 452          */
 453         tp = &thread_mags;
 454         tp->init = -1;
 455
 456         if (mtmagazine_free_live == 0) {
 457                 mtmagazine_free_live = 1;
 458                 pthread_once(&thread_mags_once, mtmagazine_init);
 459         }
 460         pthread_setspecific(thread_mags_key, tp);
 461         tp->init = 1;
 462 }
 463
 464 /*
 465  * Thread locks.
 466  */
 467 static __inline void
 468 slgd_lock(slglobaldata_t slgd)
 469 {
 470         if (__isthreaded)
 471                 _SPINLOCK(&slgd->Spinlock);
 472 }
 473
 474 static __inline void
 475 slgd_unlock(slglobaldata_t slgd)
 476 {
 477         if (__isthreaded)
 478                 _SPINUNLOCK(&slgd->Spinlock);
 479 }
 480
 481 static __inline void
 482 depot_lock(magazine_depot *dp)
 483 {
 484         if (__isthreaded)
 485                 _SPINLOCK(&dp->lock);
 486 }
 487
 488 static __inline void
 489 depot_unlock(magazine_depot *dp)
 490 {
 491         if (__isthreaded)
 492                 _SPINUNLOCK(&dp->lock);
 493 }
 494
 495 static __inline void
 496 zone_magazine_lock(void)
 497 {
 498         if (__isthreaded)
 499                 _SPINLOCK(&zone_mag_lock);
 500 }
 501
 502 static __inline void
 503 zone_magazine_unlock(void)
 504 {
 505         if (__isthreaded)
 506                 _SPINUNLOCK(&zone_mag_lock);
 507 }
 508
 509 static __inline void
 510 swap_mags(magazine_pair *mp)
 511 {
 512         struct magazine *tmp;
 513         tmp = mp->loaded;
 514         mp->loaded = mp->prev;
 515         mp->prev = tmp;
 516 }
 517
 518 /*
 519  * bigalloc hashing and locking support.
 520  *
 521  * Return an unmasked hash code for the passed pointer.
 522  */
 523 static __inline int
 524 _bigalloc_hash(void *ptr)
 525 {
 526         int hv;
 527
 528         hv = ((int)(intptr_t)ptr >> PAGE_SHIFT) ^
 529               ((int)(intptr_t)ptr >> (PAGE_SHIFT + BIGHSHIFT));
 530
 531         return(hv);
 532 }
 533
 534 /*
 535  * Lock the hash chain and return a pointer to its base for the specified
 536  * address.
 537  */
 538 static __inline bigalloc_t *
 539 bigalloc_lock(void *ptr)
 540 {
 541         int hv = _bigalloc_hash(ptr);
 542         bigalloc_t *bigp;
 543
 544         bigp = &bigalloc_array[hv & BIGHMASK];
 545         if (__isthreaded)
 546                 _SPINLOCK(&bigspin_array[hv & BIGXMASK]);
 547         return(bigp);
 548 }
 549
 550 /*
 551  * Lock the hash chain and return a pointer to its base for the specified
 552  * address.
 553  *
 554  * BUT, if the hash chain is empty, just return NULL and do not bother
 555  * to lock anything.
 556  */
 557 static __inline bigalloc_t *
 558 bigalloc_check_and_lock(void *ptr)
 559 {
 560         int hv = _bigalloc_hash(ptr);
 561         bigalloc_t *bigp;
 562
 563         bigp = &bigalloc_array[hv & BIGHMASK];
 564         if (*bigp == NULL)
 565                 return(NULL);
 566         if (__isthreaded) {
 567                 _SPINLOCK(&bigspin_array[hv & BIGXMASK]);
 568         }
 569         return(bigp);
 570 }
 571
 572 static __inline void
 573 bigalloc_unlock(void *ptr)
 574 {
 575         int hv;
 576
 577         if (__isthreaded) {
 578                 hv = _bigalloc_hash(ptr);
 579                 _SPINUNLOCK(&bigspin_array[hv & BIGXMASK]);
 580         }
 581 }
 582
 583 /*
 584  * Find a bigcache entry that might work for the allocation.  SMP races are
 585  * ok here except for the swap (that is, it is ok if bigcache_size_array[i]
 586  * is wrong or if a NULL or too-small big is returned).
 587  *
 588  * Generally speaking it is ok to find a large entry even if the bytes
 589  * requested are relatively small (but still oversized), because we really
 590  * don't know *what* the application is going to do with the buffer.
 591  */
 592 static __inline
 593 bigalloc_t
 594 bigcache_find_alloc(size_t bytes)
 595 {
 596         bigalloc_t big = NULL;
 597         size_t test;
 598         int i;
 599
 600         for (i = 0; i < BIGCACHE; ++i) {
 601                 test = bigcache_size_array[i];
 602                 if (bytes <= test) {
 603                         bigcache_size_array[i] = 0;
 604                         big = atomic_swap_ptr(&bigcache_array[i], NULL);
 605                         break;
 606                 }
 607         }
 608         return big;
 609 }
 610
 611 /*
 612  * Free a bigcache entry, possibly returning one that the caller really must
 613  * free.  This is used to cache recent oversized memory blocks.  Only
 614  * big blocks smaller than BIGCACHE_LIMIT will be cached this way, so try
 615  * to collect the biggest ones we can that are under the limit.
 616  */
 617 static __inline
 618 bigalloc_t
 619 bigcache_find_free(bigalloc_t big)
 620 {
 621         int i;
 622         int j;
 623         int b;
 624
 625         b = ++bigcache_index;
 626         for (i = 0; i < BIGCACHE; ++i) {
 627                 j = (b + i) & BIGCACHE_MASK;
 628                 if (bigcache_size_array[j] < big->bytes) {
 629                         bigcache_size_array[j] = big->bytes;
 630                         big = atomic_swap_ptr(&bigcache_array[j], big);
 631                         break;
 632                 }
 633         }
 634         return big;
 635 }
 636
 637 static __inline
 638 void
 639 handle_excess_big(void)
 640 {
 641         int i;
 642         bigalloc_t big;
 643         bigalloc_t *bigp;
 644
 645         if (excess_alloc <= BIGCACHE_EXCESS)
 646                 return;
 647
 648         for (i = 0; i < BIGHSIZE; ++i) {
 649                 bigp = &bigalloc_array[i];
 650                 if (*bigp == NULL)
 651                         continue;
 652                 if (__isthreaded)
 653                         _SPINLOCK(&bigspin_array[i & BIGXMASK]);
 654                 for (big = *bigp; big; big = big->next) {
 655                         if (big->active < big->bytes) {
 656                                 MASSERT((big->active & PAGE_MASK) == 0);
 657                                 MASSERT((big->bytes & PAGE_MASK) == 0);
 658                                 munmap((char *)big->base + big->active,
 659                                        big->bytes - big->active);
 660                                 atomic_add_long(&excess_alloc,
 661                                                 big->active - big->bytes);
 662                                 big->bytes = big->active;
 663                         }
 664                 }
 665                 if (__isthreaded)
 666                         _SPINUNLOCK(&bigspin_array[i & BIGXMASK]);
 667         }
 668 }
 669
 670 /*
 671  * Calculate the zone index for the allocation request size and set the
 672  * allocation request size to that particular zone's chunk size.
 673  */
 674 static __inline int
 675 zoneindex(size_t *bytes, size_t *chunking)
 676 {
 677         size_t n = (unsigned int)*bytes;        /* unsigned for shift opt */
 678
 679         /*
 680          * This used to be 8-byte chunks and 16 zones for n < 128.
 681          * However some instructions may require 16-byte alignment
 682          * (aka SIMD) and programs might not request an aligned size
 683          * (aka GCC-7), so change this as follows:
 684          *
 685          * 0-15 bytes   8-byte alignment in two zones   (0-1)
 686          * 16-127 bytes 16-byte alignment in four zones (3-10)
 687          * zone index 2 and 11-15 are currently unused.
 688          */
 689         if (n < 16) {
 690                 *bytes = n = (n + 7) & ~7;
 691                 *chunking = 8;
 692                 return(n / 8 - 1);              /* 8 byte chunks, 2 zones */
 693                 /* zones 0,1, zone 2 is unused */
 694         }
 695         if (n < 128) {
 696                 *bytes = n = (n + 15) & ~15;
 697                 *chunking = 16;
 698                 return(n / 16 + 2);             /* 16 byte chunks, 8 zones */
 699                 /* zones 3-10, zones 11-15 unused */
 700         }
 701         if (n < 256) {
 702                 *bytes = n = (n + 15) & ~15;
 703                 *chunking = 16;
 704                 return(n / 16 + 7);
 705         }
 706         if (n < 8192) {
 707                 if (n < 512) {
 708                         *bytes = n = (n + 31) & ~31;
 709                         *chunking = 32;
 710                         return(n / 32 + 15);
 711                 }
 712                 if (n < 1024) {
 713                         *bytes = n = (n + 63) & ~63;
 714                         *chunking = 64;
 715                         return(n / 64 + 23);
 716                 }
 717                 if (n < 2048) {
 718                         *bytes = n = (n + 127) & ~127;
 719                         *chunking = 128;
 720                         return(n / 128 + 31);
 721                 }
 722                 if (n < 4096) {
 723                         *bytes = n = (n + 255) & ~255;
 724                         *chunking = 256;
 725                         return(n / 256 + 39);
 726                 }
 727                 *bytes = n = (n + 511) & ~511;
 728                 *chunking = 512;
 729                 return(n / 512 + 47);
 730         }
 731 #if ZALLOC_ZONE_LIMIT > 8192
 732         if (n < 16384) {
 733                 *bytes = n = (n + 1023) & ~1023;
 734                 *chunking = 1024;
 735                 return(n / 1024 + 55);
 736         }
 737 #endif
 738 #if ZALLOC_ZONE_LIMIT > 16384
 739         if (n < 32768) {
 740                 *bytes = n = (n + 2047) & ~2047;
 741                 *chunking = 2048;
 742                 return(n / 2048 + 63);
 743         }
 744 #endif
 745         _mpanic("Unexpected byte count %zu", n);
 746         return(0);
 747 }
 748
 749 /*
 750  * malloc() - call internal slab allocator
 751  */
 752 void *
 753 malloc(size_t size)
 754 {
 755         void *ptr;
 756
 757         ptr = _slaballoc(size, 0);
 758         if (ptr == NULL)
 759                 errno = ENOMEM;
 760         else
 761                 UTRACE(0, size, ptr);
 762         return(ptr);
 763 }
 764
 765 #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
 766
 767 /*
 768  * calloc() - call internal slab allocator
 769  */
 770 void *
 771 calloc(size_t number, size_t size)
 772 {
 773         void *ptr;
 774
 775         if ((number >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
 776              number > 0 && SIZE_MAX / number < size) {
 777                 errno = ENOMEM;
 778                 return(NULL);
 779         }
 780
 781         ptr = _slaballoc(number * size, SAFLAG_ZERO);
 782         if (ptr == NULL)
 783                 errno = ENOMEM;
 784         else
 785                 UTRACE(0, number * size, ptr);
 786         return(ptr);
 787 }
 788
 789 /*
 790  * realloc() (SLAB ALLOCATOR)
 791  *
 792  * We do not attempt to optimize this routine beyond reusing the same
 793  * pointer if the new size fits within the chunking of the old pointer's
 794  * zone.
 795  */
 796 void *
 797 realloc(void *ptr, size_t size)
 798 {
 799         void *ret;
 800         ret = _slabrealloc(ptr, size);
 801         if (ret == NULL)
 802                 errno = ENOMEM;
 803         else
 804                 UTRACE(ptr, size, ret);
 805         return(ret);
 806 }
 807
 808 /*
 809  * posix_memalign()
 810  *
 811  * Allocate (size) bytes with a alignment of (alignment), where (alignment)
 812  * is a power of 2 >= sizeof(void *).
 813  *
 814  * The slab allocator will allocate on power-of-2 boundaries up to
 815  * at least PAGE_SIZE.  We use the zoneindex mechanic to find a
 816  * zone matching the requirements, and _vmem_alloc() otherwise.
 817  */
 818 int
 819 posix_memalign(void **memptr, size_t alignment, size_t size)
 820 {
 821         bigalloc_t *bigp;
 822         bigalloc_t big;
 823         size_t chunking;
 824         int zi __unused;
 825
 826         /*
 827          * OpenGroup spec issue 6 checks
 828          */
 829         if ((alignment | (alignment - 1)) + 1 != (alignment << 1)) {
 830                 *memptr = NULL;
 831                 return(EINVAL);
 832         }
 833         if (alignment < sizeof(void *)) {
 834                 *memptr = NULL;
 835                 return(EINVAL);
 836         }
 837
 838         /*
 839          * Our zone mechanism guarantees same-sized alignment for any
 840          * power-of-2 allocation.  If size is a power-of-2 and reasonable
 841          * we can just call _slaballoc() and be done.  We round size up
 842          * to the nearest alignment boundary to improve our odds of
 843          * it becoming a power-of-2 if it wasn't before.
 844          */
 845         if (size <= alignment)
 846                 size = alignment;
 847         else
 848                 size = (size + alignment - 1) & ~(size_t)(alignment - 1);
 849         if (size < PAGE_SIZE && (size | (size - 1)) + 1 == (size << 1)) {
 850                 *memptr = _slaballoc(size, 0);
 851                 return(*memptr ? 0 : ENOMEM);
 852         }
 853
 854         /*
 855          * Otherwise locate a zone with a chunking that matches
 856          * the requested alignment, within reason.   Consider two cases:
 857          *
 858          * (1) A 1K allocation on a 32-byte alignment.  The first zoneindex
 859          *     we find will be the best fit because the chunking will be
 860          *     greater or equal to the alignment.
 861          *
 862          * (2) A 513 allocation on a 256-byte alignment.  In this case
 863          *     the first zoneindex we find will be for 576 byte allocations
 864          *     with a chunking of 64, which is not sufficient.  To fix this
 865          *     we simply find the nearest power-of-2 >= size and use the
 866          *     same side-effect of _slaballoc() which guarantees
 867          *     same-alignment on a power-of-2 allocation.
 868          */
 869         if (size < PAGE_SIZE) {
 870                 zi = zoneindex(&size, &chunking);
 871                 if (chunking >= alignment) {
 872                         *memptr = _slaballoc(size, 0);
 873                         return(*memptr ? 0 : ENOMEM);
 874                 }
 875                 if (size >= 1024)
 876                         alignment = 1024;
 877                 if (size >= 16384)
 878                         alignment = 16384;
 879                 while (alignment < size)
 880                         alignment <<= 1;
 881                 *memptr = _slaballoc(alignment, 0);
 882                 return(*memptr ? 0 : ENOMEM);
 883         }
 884
 885         /*
 886          * If the slab allocator cannot handle it use vmem_alloc().
 887          *
 888          * Alignment must be adjusted up to at least PAGE_SIZE in this case.
 889          */
 890         if (alignment < PAGE_SIZE)
 891                 alignment = PAGE_SIZE;
 892         if (size < alignment)
 893                 size = alignment;
 894         size = (size + PAGE_MASK) & ~(size_t)PAGE_MASK;
 895         *memptr = _vmem_alloc(size, alignment, 0);
 896         if (*memptr == NULL)
 897                 return(ENOMEM);
 898
 899         big = _slaballoc(sizeof(struct bigalloc), 0);
 900         if (big == NULL) {
 901                 _vmem_free(*memptr, size);
 902                 *memptr = NULL;
 903                 return(ENOMEM);
 904         }
 905         bigp = bigalloc_lock(*memptr);
 906         big->base = *memptr;
 907         big->active = size;
 908         big->bytes = size;              /* no excess */
 909         big->next = *bigp;
 910         *bigp = big;
 911         bigalloc_unlock(*memptr);
 912
 913         return(0);
 914 }
 915
 916 /*
 917  * free() (SLAB ALLOCATOR) - do the obvious
 918  */
 919 void
 920 free(void *ptr)
 921 {
 922         UTRACE(ptr, 0, 0);
 923         _slabfree(ptr, 0, NULL);
 924 }
 925
 926 /*
 927  * _slaballoc() (SLAB ALLOCATOR)
 928  *
 929  *      Allocate memory via the slab allocator.  If the request is too large,
 930  *      or if it page-aligned beyond a certain size, we fall back to the
 931  *      KMEM subsystem
 932  */
 933 static void *
 934 _slaballoc(size_t size, int flags)
 935 {
 936         slzone_t z;
 937         slchunk_t chunk;
 938         slglobaldata_t slgd;
 939         size_t chunking;
 940         int zi;
 941 #ifdef INVARIANTS
 942         int i;
 943 #endif
 944         int off;
 945         void *obj;
 946
 947         /*
 948          * Handle the degenerate size == 0 case.  Yes, this does happen.
 949          * Return a special pointer.  This is to maintain compatibility with
 950          * the original malloc implementation.  Certain devices, such as the
 951          * adaptec driver, not only allocate 0 bytes, they check for NULL and
 952          * also realloc() later on.  Joy.
 953          */
 954         if (size == 0)
 955                 return(ZERO_LENGTH_PTR);
 956
 957         /* Capture global flags */
 958         flags |= g_malloc_flags;
 959
 960         /*
 961          * Handle large allocations directly.  There should not be very many
 962          * of these so performance is not a big issue.
 963          *
 964          * The backend allocator is pretty nasty on a SMP system.   Use the
 965          * slab allocator for one and two page-sized chunks even though we
 966          * lose some efficiency.
 967          */
 968         if (size >= ZoneLimit ||
 969             ((size & PAGE_MASK) == 0 && size > PAGE_SIZE*2)) {
 970                 bigalloc_t big;
 971                 bigalloc_t *bigp;
 972
 973                 /*
 974                  * Page-align and cache-color in case of virtually indexed
 975                  * physically tagged L1 caches (aka SandyBridge).  No sweat
 976                  * otherwise, so just do it.
 977                  *
 978                  * (don't count as excess).
 979                  */
 980                 size = (size + PAGE_MASK) & ~(size_t)PAGE_MASK;
 981                 if ((size & (PAGE_SIZE * 2 - 1)) == 0)
 982                         size += PAGE_SIZE;
 983
 984                 /*
 985                  * Try to reuse a cached big block to avoid mmap'ing.  If it
 986                  * turns out not to fit our requirements we throw it away
 987                  * and allocate normally.
 988                  */
 989                 big = NULL;
 990                 if (size <= BIGCACHE_LIMIT) {
 991                         big = bigcache_find_alloc(size);
 992                         if (big && big->bytes < size) {
 993                                 _slabfree(big->base, FASTSLABREALLOC, &big);
 994                                 big = NULL;
 995                         }
 996                 }
 997                 if (big) {
 998                         chunk = big->base;
 999                         if (flags & SAFLAG_ZERO)
1000                                 bzero(chunk, size);
1001                 } else {
1002                         chunk = _vmem_alloc(size, PAGE_SIZE, flags);
1003                         if (chunk == NULL)
1004                                 return(NULL);
1005
1006                         big = _slaballoc(sizeof(struct bigalloc), 0);
1007                         if (big == NULL) {
1008                                 _vmem_free(chunk, size);
1009                                 return(NULL);
1010                         }
1011                         big->base = chunk;
1012                         big->bytes = size;
1013                 }
1014                 big->active = size;
1015
1016                 bigp = bigalloc_lock(chunk);
1017                 if (big->active < big->bytes) {
1018                         atomic_add_long(&excess_alloc,
1019                                         big->bytes - big->active);
1020                 }
1021                 big->next = *bigp;
1022                 *bigp = big;
1023                 bigalloc_unlock(chunk);
1024                 handle_excess_big();
1025
1026                 return(chunk);
1027         }
1028
1029         /* Compute allocation zone; zoneindex will panic on excessive sizes */
1030         zi = zoneindex(&size, &chunking);
1031         MASSERT(zi < NZONES);
1032
1033         obj = mtmagazine_alloc(zi);
1034         if (obj != NULL) {
1035                 if (flags & SAFLAG_ZERO)
1036                         bzero(obj, size);
1037                 return (obj);
1038         }
1039
1040         slgd = &SLGlobalData;
1041         slgd_lock(slgd);
1042
1043         /*
1044          * Attempt to allocate out of an existing zone.  If all zones are
1045          * exhausted pull one off the free list or allocate a new one.
1046          */
1047         if ((z = slgd->ZoneAry[zi]) == NULL) {
1048                 z = zone_alloc(flags);
1049                 if (z == NULL)
1050                         goto fail;
1051
1052                 /*
1053                  * How big is the base structure?
1054                  */
1055 #if defined(INVARIANTS)
1056                 /*
1057                  * Make room for z_Bitmap.  An exact calculation is
1058                  * somewhat more complicated so don't make an exact
1059                  * calculation.
1060                  */
1061                 off = offsetof(struct slzone,
1062                                 z_Bitmap[(ZoneSize / size + 31) / 32]);
1063                 bzero(z->z_Bitmap, (ZoneSize / size + 31) / 8);
1064 #else
1065                 off = sizeof(struct slzone);
1066 #endif
1067
1068                 /*
1069                  * Align the storage in the zone based on the chunking.
1070                  *
1071                  * Guarantee power-of-2 alignment for power-of-2-sized
1072                  * chunks.  Otherwise align based on the chunking size
1073                  * (typically 8 or 16 bytes for small allocations).
1074                  *
1075                  * NOTE: Allocations >= ZoneLimit are governed by the
1076                  * bigalloc code and typically only guarantee page-alignment.
1077                  *
1078                  * Set initial conditions for UIndex near the zone header
1079                  * to reduce unecessary page faults, vs semi-randomization
1080                  * to improve L1 cache saturation.
1081                  */
1082                 if ((size | (size - 1)) + 1 == (size << 1))
1083                         off = roundup2(off, size);
1084                 else
1085                         off = roundup2(off, chunking);
1086                 z->z_Magic = ZALLOC_SLAB_MAGIC;
1087                 z->z_ZoneIndex = zi;
1088                 z->z_NMax = (ZoneSize - off) / size;
1089                 z->z_NFree = z->z_NMax;
1090                 z->z_BasePtr = (char *)z + off;
1091                 z->z_UIndex = z->z_UEndIndex = 0;
1092                 z->z_ChunkSize = size;
1093                 z->z_FirstFreePg = ZonePageCount;
1094                 z->z_Next = slgd->ZoneAry[zi];
1095                 slgd->ZoneAry[zi] = z;
1096                 if ((z->z_Flags & SLZF_UNOTZEROD) == 0) {
1097                         flags &= ~SAFLAG_ZERO;  /* already zero'd */
1098                         flags |= SAFLAG_PASSIVE;
1099                 }
1100
1101                 /*
1102                  * Slide the base index for initial allocations out of the
1103                  * next zone we create so we do not over-weight the lower
1104                  * part of the cpu memory caches.
1105                  */
1106                 slgd->JunkIndex = (slgd->JunkIndex + ZALLOC_SLAB_SLIDE)
1107                                         & (ZALLOC_MAX_ZONE_SIZE - 1);
1108         }
1109
1110         /*
1111          * Ok, we have a zone from which at least one chunk is available.
1112          *
1113          * Remove us from the ZoneAry[] when we become empty
1114          */
1115         MASSERT(z->z_NFree > 0);
1116
1117         if (--z->z_NFree == 0) {
1118                 slgd->ZoneAry[zi] = z->z_Next;
1119                 z->z_Next = NULL;
1120         }
1121
1122         /*
1123          * Locate a chunk in a free page.  This attempts to localize
1124          * reallocations into earlier pages without us having to sort
1125          * the chunk list.  A chunk may still overlap a page boundary.
1126          */
1127         while (z->z_FirstFreePg < ZonePageCount) {
1128                 if ((chunk = z->z_PageAry[z->z_FirstFreePg]) != NULL) {
1129 #ifdef DIAGNOSTIC
1130                         /*
1131                          * Diagnostic: c_Next is not total garbage.
1132                          */
1133                         MASSERT(chunk->c_Next == NULL ||
1134                             ((intptr_t)chunk->c_Next & IN_SAME_PAGE_MASK) ==
1135                             ((intptr_t)chunk & IN_SAME_PAGE_MASK));
1136 #endif
1137 #ifdef INVARIANTS
1138                         chunk_mark_allocated(z, chunk);
1139 #endif
1140                         MASSERT((uintptr_t)chunk & ZoneMask);
1141                         z->z_PageAry[z->z_FirstFreePg] = chunk->c_Next;
1142                         goto done;
1143                 }
1144                 ++z->z_FirstFreePg;
1145         }
1146
1147         /*
1148          * No chunks are available but NFree said we had some memory,
1149          * so it must be available in the never-before-used-memory
1150          * area governed by UIndex.  The consequences are very
1151          * serious if our zone got corrupted so we use an explicit
1152          * panic rather then a KASSERT.
1153          */
1154         chunk = (slchunk_t)(z->z_BasePtr + z->z_UIndex * size);
1155
1156         if (++z->z_UIndex == z->z_NMax)
1157                 z->z_UIndex = 0;
1158         if (z->z_UIndex == z->z_UEndIndex) {
1159                 if (z->z_NFree != 0)
1160                         _mpanic("slaballoc: corrupted zone");
1161         }
1162
1163         if ((z->z_Flags & SLZF_UNOTZEROD) == 0) {
1164                 flags &= ~SAFLAG_ZERO;
1165                 flags |= SAFLAG_PASSIVE;
1166         }
1167 #if defined(INVARIANTS)
1168         chunk_mark_allocated(z, chunk);
1169 #endif
1170
1171 done:
1172         slgd_unlock(slgd);
1173         if (flags & SAFLAG_ZERO) {
1174                 bzero(chunk, size);
1175 #ifdef INVARIANTS
1176         } else if ((flags & (SAFLAG_ZERO|SAFLAG_PASSIVE)) == 0) {
1177                 if (use_malloc_pattern) {
1178                         for (i = 0; i < size; i += sizeof(int)) {
1179                                 *(int *)((char *)chunk + i) = -1;
1180                         }
1181                 }
1182                 /* avoid accidental double-free check */
1183                 chunk->c_Next = (void *)-1;
1184 #endif
1185         }
1186         return(chunk);
1187 fail:
1188         slgd_unlock(slgd);
1189         return(NULL);
1190 }
1191
1192 /*
1193  * Reallocate memory within the chunk
1194  */
1195 static void *
1196 _slabrealloc(void *ptr, size_t size)
1197 {
1198         bigalloc_t *bigp;
1199         void *nptr;
1200         slzone_t z;
1201         size_t chunking;
1202
1203         if (ptr == NULL || ptr == ZERO_LENGTH_PTR) {
1204                 return(_slaballoc(size, 0));
1205         }
1206
1207         if (size == 0) {
1208                 free(ptr);
1209                 return(ZERO_LENGTH_PTR);
1210         }
1211
1212         /*
1213          * Handle oversized allocations.
1214          */
1215         if ((bigp = bigalloc_check_and_lock(ptr)) != NULL) {
1216                 bigalloc_t big;
1217                 size_t bigbytes;
1218
1219                 while ((big = *bigp) != NULL) {
1220                         if (big->base == ptr) {
1221                                 size = (size + PAGE_MASK) & ~(size_t)PAGE_MASK;
1222                                 bigbytes = big->bytes;
1223
1224                                 /*
1225                                  * If it already fits determine if it makes
1226                                  * sense to shrink/reallocate.  Try to optimize
1227                                  * programs which stupidly make incremental
1228                                  * reallocations larger or smaller by scaling
1229                                  * the allocation.  Also deal with potential
1230                                  * coloring.
1231                                  */
1232                                 if (size >= (bigbytes >> 1) &&
1233                                     size <= bigbytes) {
1234                                         if (big->active != size) {
1235                                                 atomic_add_long(&excess_alloc,
1236                                                                 big->active -
1237                                                                 size);
1238                                         }
1239                                         big->active = size;
1240                                         bigalloc_unlock(ptr);
1241                                         return(ptr);
1242                                 }
1243
1244                                 /*
1245                                  * For large reallocations, allocate more space
1246                                  * than we need to try to avoid excessive
1247                                  * reallocations later on.
1248                                  */
1249                                 chunking = size + (size >> 3);
1250                                 chunking = (chunking + PAGE_MASK) &
1251                                            ~(size_t)PAGE_MASK;
1252
1253                                 /*
1254                                  * Try to allocate adjacently in case the
1255                                  * program is idiotically realloc()ing a
1256                                  * huge memory block just slightly bigger.
1257                                  * (llvm's llc tends to do this a lot).
1258                                  *
1259                                  * (MAP_TRYFIXED forces mmap to fail if there
1260                                  *  is already something at the address).
1261                                  */
1262                                 if (chunking > bigbytes) {
1263                                         char *addr;
1264                                         int errno_save = errno;
1265
1266                                         addr = mmap((char *)ptr + bigbytes,
1267                                                     chunking - bigbytes,
1268                                                     PROT_READ|PROT_WRITE,
1269                                                     MAP_PRIVATE|MAP_ANON|
1270                                                     MAP_TRYFIXED,
1271                                                     -1, 0);
1272                                         errno = errno_save;
1273                                         if (addr == (char *)ptr + bigbytes) {
1274                                                 atomic_add_long(&excess_alloc,
1275                                                                 big->active -
1276                                                                 big->bytes +
1277                                                                 chunking -
1278                                                                 size);
1279                                                 big->bytes = chunking;
1280                                                 big->active = size;
1281                                                 bigalloc_unlock(ptr);
1282
1283                                                 return(ptr);
1284                                         }
1285                                         MASSERT((void *)addr == MAP_FAILED);
1286                                 }
1287
1288                                 /*
1289                                  * Failed, unlink big and allocate fresh.
1290                                  * (note that we have to leave (big) intact
1291                                  * in case the slaballoc fails).
1292                                  */
1293                                 *bigp = big->next;
1294                                 bigalloc_unlock(ptr);
1295                                 if ((nptr = _slaballoc(size, 0)) == NULL) {
1296                                         /* Relink block */
1297                                         bigp = bigalloc_lock(ptr);
1298                                         big->next = *bigp;
1299                                         *bigp = big;
1300                                         bigalloc_unlock(ptr);
1301                                         return(NULL);
1302                                 }
1303                                 if (size > bigbytes)
1304                                         size = bigbytes;
1305                                 bcopy(ptr, nptr, size);
1306                                 atomic_add_long(&excess_alloc, big->active -
1307                                                                big->bytes);
1308                                 _slabfree(ptr, FASTSLABREALLOC, &big);
1309
1310                                 return(nptr);
1311                         }
1312                         bigp = &big->next;
1313                 }
1314                 bigalloc_unlock(ptr);
1315                 handle_excess_big();
1316         }
1317
1318         /*
1319          * Get the original allocation's zone.  If the new request winds
1320          * up using the same chunk size we do not have to do anything.
1321          *
1322          * NOTE: We don't have to lock the globaldata here, the fields we
1323          * access here will not change at least as long as we have control
1324          * over the allocation.
1325          */
1326         z = (slzone_t)((uintptr_t)ptr & ~(uintptr_t)ZoneMask);
1327         MASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC);
1328
1329         /*
1330          * Use zoneindex() to chunk-align the new size, as long as the
1331          * new size is not too large.
1332          */
1333         if (size < ZoneLimit) {
1334                 zoneindex(&size, &chunking);
1335                 if (z->z_ChunkSize == size) {
1336                         return(ptr);
1337                 }
1338         }
1339
1340         /*
1341          * Allocate memory for the new request size and copy as appropriate.
1342          */
1343         if ((nptr = _slaballoc(size, 0)) != NULL) {
1344                 if (size > z->z_ChunkSize)
1345                         size = z->z_ChunkSize;
1346                 bcopy(ptr, nptr, size);
1347                 _slabfree(ptr, 0, NULL);
1348         }
1349
1350         return(nptr);
1351 }
1352
1353 /*
1354  * free (SLAB ALLOCATOR)
1355  *
1356  * Free a memory block previously allocated by malloc.  Note that we do not
1357  * attempt to uplodate ks_loosememuse as MP races could prevent us from
1358  * checking memory limits in malloc.
1359  *
1360  * flags:
1361  *      FASTSLABREALLOC         Fast call from realloc, *rbigp already
1362  *                              unlinked.
1363  *
1364  * MPSAFE
1365  */
1366 static void
1367 _slabfree(void *ptr, int flags, bigalloc_t *rbigp)
1368 {
1369         slzone_t z;
1370         slchunk_t chunk;
1371         bigalloc_t big;
1372         bigalloc_t *bigp;
1373         slglobaldata_t slgd;
1374         size_t size;
1375         int zi;
1376         int pgno;
1377
1378         /* Fast realloc path for big allocations */
1379         if (flags & FASTSLABREALLOC) {
1380                 big = *rbigp;
1381                 goto fastslabrealloc;
1382         }
1383
1384         /*
1385          * Handle NULL frees and special 0-byte allocations
1386          */
1387         if (ptr == NULL)
1388                 return;
1389         if (ptr == ZERO_LENGTH_PTR)
1390                 return;
1391
1392         /*
1393          * Handle oversized allocations.
1394          */
1395         if ((bigp = bigalloc_check_and_lock(ptr)) != NULL) {
1396                 while ((big = *bigp) != NULL) {
1397                         if (big->base == ptr) {
1398                                 *bigp = big->next;
1399                                 atomic_add_long(&excess_alloc, big->active -
1400                                                                big->bytes);
1401                                 bigalloc_unlock(ptr);
1402
1403                                 /*
1404                                  * Try to stash the block we are freeing,
1405                                  * potentially receiving another block in
1406                                  * return which must be freed.
1407                                  */
1408 fastslabrealloc:
1409                                 if (big->bytes <= BIGCACHE_LIMIT) {
1410                                         big = bigcache_find_free(big);
1411                                         if (big == NULL)
1412                                                 return;
1413                                 }
1414                                 ptr = big->base;        /* reload */
1415                                 size = big->bytes;
1416                                 _slabfree(big, 0, NULL);
1417 #ifdef INVARIANTS
1418                                 MASSERT(sizeof(weirdary) <= size);
1419                                 bcopy(weirdary, ptr, sizeof(weirdary));
1420 #endif
1421                                 _vmem_free(ptr, size);
1422                                 return;
1423                         }
1424                         bigp = &big->next;
1425                 }
1426                 bigalloc_unlock(ptr);
1427                 handle_excess_big();
1428         }
1429
1430         /*
1431          * Zone case.  Figure out the zone based on the fact that it is
1432          * ZoneSize aligned.
1433          */
1434         z = (slzone_t)((uintptr_t)ptr & ~(uintptr_t)ZoneMask);
1435         MASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC);
1436
1437         size = z->z_ChunkSize;
1438         zi = z->z_ZoneIndex;
1439
1440         if (g_malloc_flags & SAFLAG_ZERO)
1441                 bzero(ptr, size);
1442
1443         if (mtmagazine_free(zi, ptr) == 0)
1444                 return;
1445
1446         pgno = ((char *)ptr - (char *)z) >> PAGE_SHIFT;
1447         chunk = ptr;
1448         slgd = &SLGlobalData;
1449         slgd_lock(slgd);
1450
1451 #ifdef INVARIANTS
1452         /*
1453          * Attempt to detect a double-free.  To reduce overhead we only check
1454          * if there appears to be link pointer at the base of the data.
1455          */
1456         if (((intptr_t)chunk->c_Next - (intptr_t)z) >> PAGE_SHIFT == pgno) {
1457                 slchunk_t scan;
1458
1459                 for (scan = z->z_PageAry[pgno]; scan; scan = scan->c_Next) {
1460                         if (scan == chunk)
1461                                 _mpanic("Double free at %p", chunk);
1462                 }
1463         }
1464         chunk_mark_free(z, chunk);
1465 #endif
1466
1467         /*
1468          * Put weird data into the memory to detect modifications after
1469          * freeing, illegal pointer use after freeing (we should fault on
1470          * the odd address), and so forth.
1471          */
1472 #ifdef INVARIANTS
1473         if (z->z_ChunkSize < sizeof(weirdary))
1474                 bcopy(weirdary, chunk, z->z_ChunkSize);
1475         else
1476                 bcopy(weirdary, chunk, sizeof(weirdary));
1477 #endif
1478
1479         /*
1480          * Add this free non-zero'd chunk to a linked list for reuse, adjust
1481          * z_FirstFreePg.
1482          */
1483         chunk->c_Next = z->z_PageAry[pgno];
1484         z->z_PageAry[pgno] = chunk;
1485         if (z->z_FirstFreePg > pgno)
1486                 z->z_FirstFreePg = pgno;
1487
1488         /*
1489          * Bump the number of free chunks.  If it becomes non-zero the zone
1490          * must be added back onto the appropriate list.
1491          */
1492         if (z->z_NFree++ == 0) {
1493                 z->z_Next = slgd->ZoneAry[z->z_ZoneIndex];
1494                 slgd->ZoneAry[z->z_ZoneIndex] = z;
1495         }
1496
1497         /*
1498          * If the zone becomes totally free then release it.
1499          */
1500         if (z->z_NFree == z->z_NMax) {
1501                 slzone_t *pz;
1502
1503                 pz = &slgd->ZoneAry[z->z_ZoneIndex];
1504                 while (z != *pz)
1505                         pz = &(*pz)->z_Next;
1506                 *pz = z->z_Next;
1507                 z->z_Magic = -1;
1508                 z->z_Next = NULL;
1509                 zone_free(z);
1510                 /* slgd lock released */
1511                 return;
1512         }
1513         slgd_unlock(slgd);
1514 }
1515
1516 #if defined(INVARIANTS)
1517 /*
1518  * Helper routines for sanity checks
1519  */
1520 static
1521 void
1522 chunk_mark_allocated(slzone_t z, void *chunk)
1523 {
1524         int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize;
1525         __uint32_t *bitptr;
1526
1527         MASSERT(bitdex >= 0 && bitdex < z->z_NMax);
1528         bitptr = &z->z_Bitmap[bitdex >> 5];
1529         bitdex &= 31;
1530         MASSERT((*bitptr & (1 << bitdex)) == 0);
1531         *bitptr |= 1 << bitdex;
1532 }
1533
1534 static
1535 void
1536 chunk_mark_free(slzone_t z, void *chunk)
1537 {
1538         int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize;
1539         __uint32_t *bitptr;
1540
1541         MASSERT(bitdex >= 0 && bitdex < z->z_NMax);
1542         bitptr = &z->z_Bitmap[bitdex >> 5];
1543         bitdex &= 31;
1544         MASSERT((*bitptr & (1 << bitdex)) != 0);
1545         *bitptr &= ~(1 << bitdex);
1546 }
1547
1548 #endif
1549
1550 /*
1551  * Allocate and return a magazine.  NULL is returned and *burst is adjusted
1552  * if the magazine is empty.
1553  */
1554 static __inline void *
1555 magazine_alloc(struct magazine *mp, int *burst)
1556 {
1557         void *obj;
1558
1559         if (mp == NULL)
1560                 return(NULL);
1561         if (MAGAZINE_NOTEMPTY(mp)) {
1562                 obj = mp->objects[--mp->rounds];
1563                 return(obj);
1564         }
1565
1566         /*
1567          * Return burst factor to caller along with NULL
1568          */
1569         if ((mp->flags & M_BURST) && (burst != NULL)) {
1570                 *burst = mp->burst_factor;
1571         }
1572         /* Reduce burst factor by NSCALE; if it hits 1, disable BURST */
1573         if ((mp->flags & M_BURST) && (mp->flags & M_BURST_EARLY) &&
1574             (burst != NULL)) {
1575                 mp->burst_factor -= M_BURST_NSCALE;
1576                 if (mp->burst_factor <= 1) {
1577                         mp->burst_factor = 1;
1578                         mp->flags &= ~(M_BURST);
1579                         mp->flags &= ~(M_BURST_EARLY);
1580                 }
1581         }
1582         return (NULL);
1583 }
1584
1585 static __inline int
1586 magazine_free(struct magazine *mp, void *p)
1587 {
1588         if (mp != NULL && MAGAZINE_NOTFULL(mp)) {
1589                 mp->objects[mp->rounds++] = p;
1590                 return 0;
1591         }
1592
1593         return -1;
1594 }
1595
1596 static void *
1597 mtmagazine_alloc(int zi)
1598 {
1599         thr_mags *tp;
1600         struct magazine *mp, *emptymag;
1601         magazine_depot *d;
1602         void *obj;
1603
1604         /*
1605          * Do not try to access per-thread magazines while the mtmagazine
1606          * is being initialized or destroyed.
1607          */
1608         tp = &thread_mags;
1609         if (tp->init < 0)
1610                 return(NULL);
1611
1612         /*
1613          * Primary per-thread allocation loop
1614          */
1615         for (;;) {
1616                 /*
1617                  * If the loaded magazine has rounds, allocate and return
1618                  */
1619                 mp = tp->mags[zi].loaded;
1620                 obj = magazine_alloc(mp, NULL);
1621                 if (obj)
1622                         break;
1623
1624                 /*
1625                  * If the prev magazine is full, swap with the loaded
1626                  * magazine and retry.
1627                  */
1628                 mp = tp->mags[zi].prev;
1629                 if (mp && MAGAZINE_FULL(mp)) {
1630                         MASSERT(mp->rounds != 0);
1631                         swap_mags(&tp->mags[zi]);       /* prev now empty */
1632                         continue;
1633                 }
1634
1635                 /*
1636                  * Try to get a full magazine from the depot.  Cycle
1637                  * through depot(full)->loaded->prev->depot(empty).
1638                  * Retry if a full magazine was available from the depot.
1639                  *
1640                  * Return NULL (caller will fall through) if no magazines
1641                  * can be found anywhere.
1642                  */
1643                 d = &depots[zi];
1644                 depot_lock(d);
1645                 emptymag = tp->mags[zi].prev;
1646                 if (emptymag)
1647                         SLIST_INSERT_HEAD(&d->empty, emptymag, nextmagazine);
1648                 tp->mags[zi].prev = tp->mags[zi].loaded;
1649                 mp = SLIST_FIRST(&d->full);     /* loaded magazine */
1650                 tp->mags[zi].loaded = mp;
1651                 if (mp) {
1652                         SLIST_REMOVE_HEAD(&d->full, nextmagazine);
1653                         MASSERT(MAGAZINE_NOTEMPTY(mp));
1654                         depot_unlock(d);
1655                         continue;
1656                 }
1657                 depot_unlock(d);
1658                 break;
1659         }
1660
1661         return (obj);
1662 }
1663
1664 static int
1665 mtmagazine_free(int zi, void *ptr)
1666 {
1667         thr_mags *tp;
1668         struct magazine *mp, *loadedmag;
1669         magazine_depot *d;
1670         int rc = -1;
1671
1672         /*
1673          * Do not try to access per-thread magazines while the mtmagazine
1674          * is being initialized or destroyed.
1675          */
1676         tp = &thread_mags;
1677         if (tp->init < 0)
1678                 return(-1);
1679
1680         /*
1681          * Primary per-thread freeing loop
1682          */
1683         for (;;) {
1684                 /*
1685                  * Make sure a new magazine is available in case we have
1686                  * to use it.  Staging the newmag allows us to avoid
1687                  * some locking/reentrancy complexity.
1688                  *
1689                  * Temporarily disable the per-thread caches for this
1690                  * allocation to avoid reentrancy and/or to avoid a
1691                  * stack overflow if the [zi] happens to be the same that
1692                  * would be used to allocate the new magazine.
1693                  */
1694                 if (tp->newmag == NULL) {
1695                         tp->init = -1;
1696                         tp->newmag = _slaballoc(sizeof(struct magazine),
1697                                                 SAFLAG_ZERO);
1698                         tp->init = 1;
1699                         if (tp->newmag == NULL) {
1700                                 rc = -1;
1701                                 break;
1702                         }
1703                 }
1704
1705                 /*
1706                  * If the loaded magazine has space, free directly to it
1707                  */
1708                 rc = magazine_free(tp->mags[zi].loaded, ptr);
1709                 if (rc == 0)
1710                         break;
1711
1712                 /*
1713                  * If the prev magazine is empty, swap with the loaded
1714                  * magazine and retry.
1715                  */
1716                 mp = tp->mags[zi].prev;
1717                 if (mp && MAGAZINE_EMPTY(mp)) {
1718                         MASSERT(mp->rounds == 0);
1719                         swap_mags(&tp->mags[zi]);       /* prev now full */
1720                         continue;
1721                 }
1722
1723                 /*
1724                  * Try to get an empty magazine from the depot.  Cycle
1725                  * through depot(empty)->loaded->prev->depot(full).
1726                  * Retry if an empty magazine was available from the depot.
1727                  */
1728                 d = &depots[zi];
1729                 depot_lock(d);
1730
1731                 if ((loadedmag = tp->mags[zi].prev) != NULL)
1732                         SLIST_INSERT_HEAD(&d->full, loadedmag, nextmagazine);
1733                 tp->mags[zi].prev = tp->mags[zi].loaded;
1734                 mp = SLIST_FIRST(&d->empty);
1735                 if (mp) {
1736                         tp->mags[zi].loaded = mp;
1737                         SLIST_REMOVE_HEAD(&d->empty, nextmagazine);
1738                         MASSERT(MAGAZINE_NOTFULL(mp));
1739                 } else {
1740                         mp = tp->newmag;
1741                         tp->newmag = NULL;
1742                         mp->capacity = M_MAX_ROUNDS;
1743                         mp->rounds = 0;
1744                         mp->flags = 0;
1745                         tp->mags[zi].loaded = mp;
1746                 }
1747                 depot_unlock(d);
1748         }
1749
1750         return rc;
1751 }
1752
1753 static void
1754 mtmagazine_init(void)
1755 {
1756         int error;
1757
1758         error = pthread_key_create(&thread_mags_key, mtmagazine_destructor);
1759         if (error)
1760                 abort();
1761 }
1762
1763 /*
1764  * This function is only used by the thread exit destructor
1765  */
1766 static void
1767 mtmagazine_drain(struct magazine *mp)
1768 {
1769         void *obj;
1770
1771         while (MAGAZINE_NOTEMPTY(mp)) {
1772                 obj = magazine_alloc(mp, NULL);
1773                 _slabfree(obj, 0, NULL);
1774         }
1775 }
1776
1777 /*
1778  * mtmagazine_destructor()
1779  *
1780  * When a thread exits, we reclaim all its resources; all its magazines are
1781  * drained and the structures are freed.
1782  *
1783  * WARNING!  The destructor can be called multiple times if the larger user
1784  *           program has its own destructors which run after ours which
1785  *           allocate or free memory.
1786  */
1787 static void
1788 mtmagazine_destructor(void *thrp)
1789 {
1790         thr_mags *tp = thrp;
1791         struct magazine *mp;
1792         int i;
1793
1794         /*
1795          * Prevent further use of mtmagazines while we are destructing
1796          * them, as well as for any destructors which are run after us
1797          * prior to the thread actually being destroyed.
1798          */
1799         tp->init = -1;
1800
1801         for (i = 0; i < NZONES; i++) {
1802                 mp = tp->mags[i].loaded;
1803                 tp->mags[i].loaded = NULL;
1804                 if (mp) {
1805                         if (MAGAZINE_NOTEMPTY(mp))
1806                                 mtmagazine_drain(mp);
1807                         _slabfree(mp, 0, NULL);
1808                 }
1809
1810                 mp = tp->mags[i].prev;
1811                 tp->mags[i].prev = NULL;
1812                 if (mp) {
1813                         if (MAGAZINE_NOTEMPTY(mp))
1814                                 mtmagazine_drain(mp);
1815                         _slabfree(mp, 0, NULL);
1816                 }
1817         }
1818
1819         if (tp->newmag) {
1820                 mp = tp->newmag;
1821                 tp->newmag = NULL;
1822                 _slabfree(mp, 0, NULL);
1823         }
1824 }
1825
1826 /*
1827  * zone_alloc()
1828  *
1829  * Attempt to allocate a zone from the zone magazine; the zone magazine has
1830  * M_BURST_EARLY enabled, so honor the burst request from the magazine.
1831  */
1832 static slzone_t
1833 zone_alloc(int flags)
1834 {
1835         slglobaldata_t slgd = &SLGlobalData;
1836         int burst = 1;
1837         int i, j;
1838         slzone_t z;
1839
1840         zone_magazine_lock();
1841         slgd_unlock(slgd);
1842
1843         z = magazine_alloc(&zone_magazine, &burst);
1844         if (z == NULL && burst == 1) {
1845                 zone_magazine_unlock();
1846                 z = _vmem_alloc(ZoneSize * burst, ZoneSize, flags);
1847         } else if (z == NULL) {
1848                 z = _vmem_alloc(ZoneSize * burst, ZoneSize, flags);
1849                 if (z) {
1850                         for (i = 1; i < burst; i++) {
1851                                 j = magazine_free(&zone_magazine,
1852                                                   (char *) z + (ZoneSize * i));
1853                                 MASSERT(j == 0);
1854                         }
1855                 }
1856                 zone_magazine_unlock();
1857         } else {
1858                 z->z_Flags |= SLZF_UNOTZEROD;
1859                 zone_magazine_unlock();
1860         }
1861         slgd_lock(slgd);
1862         return z;
1863 }
1864
1865 /*
1866  * zone_free()
1867  *
1868  * Release a zone and unlock the slgd lock.
1869  */
1870 static void
1871 zone_free(void *z)
1872 {
1873         slglobaldata_t slgd = &SLGlobalData;
1874         void *excess[M_ZONE_ROUNDS - M_LOW_ROUNDS] = {};
1875         int i, j;
1876
1877         zone_magazine_lock();
1878         slgd_unlock(slgd);
1879
1880         bzero(z, sizeof(struct slzone));
1881
1882         if (opt_madvise)
1883                 madvise(z, ZoneSize, MADV_FREE);
1884
1885         i = magazine_free(&zone_magazine, z);
1886
1887         /*
1888          * If we failed to free, collect excess magazines; release the zone
1889          * magazine lock, and then free to the system via _vmem_free. Re-enable
1890          * BURST mode for the magazine.
1891          */
1892         if (i == -1) {
1893                 j = zone_magazine.rounds - zone_magazine.low_factor;
1894                 for (i = 0; i < j; i++) {
1895                         excess[i] = magazine_alloc(&zone_magazine, NULL);
1896                         MASSERT(excess[i] !=  NULL);
1897                 }
1898
1899                 zone_magazine_unlock();
1900
1901                 for (i = 0; i < j; i++)
1902                         _vmem_free(excess[i], ZoneSize);
1903
1904                 _vmem_free(z, ZoneSize);
1905         } else {
1906                 zone_magazine_unlock();
1907         }
1908 }
1909
1910 /*
1911  * _vmem_alloc()
1912  *
1913  *      Directly map memory in PAGE_SIZE'd chunks with the specified
1914  *      alignment.
1915  *
1916  *      Alignment must be a multiple of PAGE_SIZE.
1917  *
1918  *      Size must be >= alignment.
1919  */
1920 static void *
1921 _vmem_alloc(size_t size, size_t align, int flags)
1922 {
1923         char *addr;
1924         char *save;
1925         size_t excess;
1926
1927         /*
1928          * Map anonymous private memory.
1929          */
1930         addr = mmap(NULL, size, PROT_READ|PROT_WRITE,
1931                     MAP_PRIVATE|MAP_ANON, -1, 0);
1932         if (addr == MAP_FAILED)
1933                 return(NULL);
1934
1935         /*
1936          * Check alignment.  The misaligned offset is also the excess
1937          * amount.  If misaligned unmap the excess so we have a chance of
1938          * mapping at the next alignment point and recursively try again.
1939          *
1940          * BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB  block alignment
1941          *   aaaaaaaaa aaaaaaaaaaa aa           mis-aligned allocation
1942          *   xxxxxxxxx                          final excess calculation
1943          *   ^ returned address
1944          */
1945         excess = (uintptr_t)addr & (align - 1);
1946
1947         if (excess) {
1948                 excess = align - excess;
1949                 save = addr;
1950
1951                 munmap(save + excess, size - excess);
1952                 addr = _vmem_alloc(size, align, flags);
1953                 munmap(save, excess);
1954         }
1955         return((void *)addr);
1956 }
1957
1958 /*
1959  * _vmem_free()
1960  *
1961  *      Free a chunk of memory allocated with _vmem_alloc()
1962  */
1963 static void
1964 _vmem_free(void *ptr, size_t size)
1965 {
1966         munmap(ptr, size);
1967 }
1968
1969 /*
1970  * Panic on fatal conditions
1971  */
1972 static void
1973 _mpanic(const char *ctl, ...)
1974 {
1975         va_list va;
1976
1977         if (malloc_panic == 0) {
1978                 malloc_panic = 1;
1979                 va_start(va, ctl);
1980                 vfprintf(stderr, ctl, va);
1981                 fprintf(stderr, "\n");
1982                 fflush(stderr);
1983                 va_end(va);
1984         }
1985         abort();
1986 }