1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 
  22 /*
  23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26 
  27 #include <mtmalloc.h>
  28 #include "mtmalloc_impl.h"
  29 #include <unistd.h>
  30 #include <synch.h>
  31 #include <thread.h>
  32 #include <pthread.h>
  33 #include <stdio.h>
  34 #include <limits.h>
  35 #include <errno.h>
  36 #include <string.h>
  37 #include <strings.h>
  38 #include <sys/param.h>
  39 #include <sys/sysmacros.h>
  40 
  41 /*
  42  * To turn on the asserts just compile -DDEBUG
  43  */
  44 
  45 #ifndef DEBUG
  46 #define NDEBUG
  47 #endif
  48 
  49 #include <assert.h>
  50 
  51 /*
  52  * The MT hot malloc implementation contained herein is designed to be
  53  * plug-compatible with the libc version of malloc. It is not intended
  54  * to replace that implementation until we decide that it is ok to break
  55  * customer apps (Solaris 3.0).
  56  *
  57  * For requests up to 2^^16, the allocator initializes itself into NCPUS
  58  * worth of chains of caches. When a memory request is made, the calling thread
  59  * is vectored into one of NCPUS worth of caches.  The LWP id gives us a cheap,
  60  * contention-reducing index to use, eventually, this should be replaced with
  61  * the actual CPU sequence number, when an interface to get it is available.
  62  *
  63  * Once the thread is vectored into one of the list of caches the real
  64  * allocation of the memory begins. The size is determined to figure out which
  65  * bucket the allocation should be satisfied from. The management of free
  66  * buckets is done via a bitmask. A free bucket is represented by a 1. The
  67  * first free bit represents the first free bucket. The position of the bit,
  68  * represents the position of the bucket in the arena.
  69  *
  70  * When the memory from the arena is handed out, the address of the cache
  71  * control structure is written in the word preceeding the returned memory.
  72  * This cache control address is used during free() to mark the buffer free
  73  * in the cache control structure.
  74  *
  75  * When all available memory in a cache has been depleted, a new chunk of memory
  76  * is allocated via sbrk(). The new cache is allocated from this chunk of memory
  77  * and initialized in the function create_cache(). New caches are installed at
  78  * the front of a singly linked list of the same size memory pools. This helps
  79  * to ensure that there will tend to be available memory in the beginning of the
  80  * list.
  81  *
  82  * Long linked lists hurt performance. To decrease this effect, there is a
  83  * tunable, requestsize, that bumps up the sbrk allocation size and thus
  84  * increases the number of available blocks within an arena.  We also keep
  85  * a "hint" for each cache list, which is the last cache in the list allocated
  86  * from.  This lowers the cost of searching if there are a lot of fully
  87  * allocated blocks at the front of the list.
  88  *
  89  * For requests greater than 2^^16 (oversize allocations), there are two pieces
  90  * of overhead. There is the OVERHEAD used to hold the cache addr
  91  * (&oversize_list), plus an oversize_t structure to further describe the block.
  92  *
  93  * The oversize list is kept as defragmented as possible by coalescing
  94  * freed oversized allocations with adjacent neighbors.
  95  *
  96  * Addresses handed out are stored in a hash table, and are aligned on
  97  * MTMALLOC_MIN_ALIGN-byte boundaries at both ends. Request sizes are rounded-up
  98  * where necessary in order to achieve this. This eases the implementation of
  99  * MTDEBUGPATTERN and MTINITPATTERN, particularly where coalescing occurs.
 100  *
 101  * A memalign allocation takes memalign header overhead.  There's two
 102  * types of memalign headers distinguished by MTMALLOC_MEMALIGN_MAGIC
 103  * and MTMALLOC_MEMALIGN_MIN_MAGIC.  When the size of memory taken to
 104  * get to the aligned address from malloc'ed address is the minimum size
 105  * OVERHEAD, we create a header taking only one OVERHEAD space with magic
 106  * number MTMALLOC_MEMALIGN_MIN_MAGIC, and we know by subtracting OVERHEAD
 107  * from memaligned address, we can get to the malloc'ed address. Otherwise,
 108  * we create a memalign header taking two OVERHEAD space, one stores
 109  * MTMALLOC_MEMALIGN_MAGIC magic number, the other one points back to the
 110  * malloc'ed address.
 111  */
 112 
 113 #if defined(__i386) || defined(__amd64)
 114 #include <arpa/inet.h>    /* for htonl() */
 115 #endif
 116 
 117 static void * morecore(size_t);
 118 static void create_cache(cache_t *, size_t bufsize, uint_t hunks);
 119 static void * malloc_internal(size_t, percpu_t *);
 120 static void * oversize(size_t);
 121 static oversize_t *find_oversize(size_t);
 122 static void add_oversize(oversize_t *);
 123 static void copy_pattern(uint32_t, void *, size_t);
 124 static void * verify_pattern(uint32_t, void *, size_t);
 125 static void reinit_cpu_list(void);
 126 static void reinit_cache(cache_t *);
 127 static void free_oversize(oversize_t *);
 128 static oversize_t *oversize_header_alloc(uintptr_t, size_t);
 129 
 130 /*
 131  * oversize hash table stuff
 132  */
 133 #define NUM_BUCKETS     67      /* must be prime */
 134 #define HASH_OVERSIZE(caddr)    ((uintptr_t)(caddr) % NUM_BUCKETS)
 135 oversize_t *ovsz_hashtab[NUM_BUCKETS];
 136 
 137 #define ALIGN(x, a)     ((((uintptr_t)(x) + ((uintptr_t)(a) - 1)) \
 138                         & ~((uintptr_t)(a) - 1)))
 139 
 140 /* need this to deal with little endianess of x86 */
 141 #if defined(__i386) || defined(__amd64)
 142 #define FLIP_EM(x)      htonl((x))
 143 #else
 144 #define FLIP_EM(x)      (x)
 145 #endif
 146 
 147 #define INSERT_ONLY                     0
 148 #define COALESCE_LEFT                   0x00000001
 149 #define COALESCE_RIGHT                  0x00000002
 150 #define COALESCE_WITH_BOTH_SIDES        (COALESCE_LEFT | COALESCE_RIGHT)
 151 
 152 #define OVERHEAD        8       /* size needed to write cache addr */
 153 #define HUNKSIZE        8192    /* just a multiplier */
 154 
 155 #define MAX_CACHED_SHIFT        16      /* 64K is the max cached size */
 156 #define MAX_CACHED              (1 << MAX_CACHED_SHIFT)
 157 #define MIN_CACHED_SHIFT        4       /* smaller requests rounded up */
 158 #define MTMALLOC_MIN_ALIGN      8       /* min guaranteed alignment */
 159 
 160 /* maximum size before overflow */
 161 #define MAX_MTMALLOC    (SIZE_MAX - (SIZE_MAX % MTMALLOC_MIN_ALIGN) \
 162                         - OVSZ_HEADER_SIZE)
 163 
 164 #define NUM_CACHES      (MAX_CACHED_SHIFT - MIN_CACHED_SHIFT + 1)
 165 #define CACHELIST_SIZE  ALIGN(NUM_CACHES * sizeof (cache_head_t), \
 166     CACHE_COHERENCY_UNIT)
 167 
 168 #define MINSIZE         9       /* for requestsize, tunable */
 169 #define MAXSIZE         256     /* arbitrary, big enough, for requestsize */
 170 
 171 #define FREEPATTERN     0xdeadbeef /* debug fill pattern for free buf */
 172 #define INITPATTERN     0xbaddcafe /* debug fill pattern for new buf */
 173 
 174 #define misaligned(p)   ((unsigned)(p) & (sizeof (int) - 1))
 175 #define IS_OVERSIZE(x, y)       (((x) < (y)) && (((x) > MAX_CACHED)? 1 : 0))
 176 
 177 static long requestsize = MINSIZE; /* 9 pages per cache; tunable; 9 is min */
 178 
 179 static uint_t cpu_mask;
 180 static curcpu_func curcpu;
 181 
 182 static int32_t debugopt;
 183 static int32_t reinit;
 184 
 185 static percpu_t *cpu_list;
 186 static oversize_t oversize_list;
 187 static mutex_t oversize_lock = DEFAULTMUTEX;
 188 
 189 static int ncpus = 0;
 190 
 191 #define MTMALLOC_OVERSIZE_MAGIC         ((uintptr_t)&oversize_list)
 192 #define MTMALLOC_MEMALIGN_MAGIC         ((uintptr_t)&oversize_list + 1)
 193 #define MTMALLOC_MEMALIGN_MIN_MAGIC     ((uintptr_t)&oversize_list + 2)
 194 
 195 /*
 196  * We require allocations handed out to be aligned on MTMALLOC_MIN_ALIGN-byte
 197  * boundaries. We round up sizeof (oversize_t) (when necessary) to ensure that
 198  * this is achieved.
 199  */
 200 #define OVSZ_SIZE               (ALIGN(sizeof (oversize_t), MTMALLOC_MIN_ALIGN))
 201 #define OVSZ_HEADER_SIZE        (OVSZ_SIZE + OVERHEAD)
 202 
 203 /*
 204  * memalign header takes 2 OVERHEAD space.  One for memalign magic, and the
 205  * other one points back to the start address of originally allocated space.
 206  */
 207 #define MEMALIGN_HEADER_SIZE    2 * OVERHEAD
 208 #define MEMALIGN_HEADER_ALLOC(x, shift, malloc_addr)\
 209         if (shift == OVERHEAD)\
 210                 *((uintptr_t *)((caddr_t)x - OVERHEAD)) = \
 211                         MTMALLOC_MEMALIGN_MIN_MAGIC; \
 212         else {\
 213                 *((uintptr_t *)((caddr_t)x - OVERHEAD)) = \
 214                         MTMALLOC_MEMALIGN_MAGIC; \
 215                 *((uintptr_t *)((caddr_t)x - 2 * OVERHEAD)) = \
 216                         (uintptr_t)malloc_addr; \
 217         }
 218 
 219 /*
 220  * Add big to the oversize hash table at the head of the relevant bucket.
 221  */
 222 static void
 223 insert_hash(oversize_t *big)
 224 {
 225         caddr_t ret = big->addr;
 226         int bucket = HASH_OVERSIZE(ret);
 227 
 228         assert(MUTEX_HELD(&oversize_lock));
 229         big->hash_next = ovsz_hashtab[bucket];
 230         ovsz_hashtab[bucket] = big;
 231 }
 232 
 233 void *
 234 malloc(size_t bytes)
 235 {
 236         percpu_t *list_rotor;
 237         uint_t  list_index;
 238 
 239         if (bytes > MAX_CACHED)
 240                 return (oversize(bytes));
 241 
 242         list_index = (curcpu() & cpu_mask);
 243 
 244         list_rotor = &cpu_list[list_index];
 245 
 246         return (malloc_internal(bytes, list_rotor));
 247 }
 248 
 249 void *
 250 realloc(void * ptr, size_t bytes)
 251 {
 252         void *new, *data_ptr;
 253         cache_t *cacheptr;
 254         caddr_t mem;
 255         size_t shift = 0;
 256 
 257         if (ptr == NULL)
 258                 return (malloc(bytes));
 259 
 260         if (bytes == 0) {
 261                 free(ptr);
 262                 return (NULL);
 263         }
 264 
 265         data_ptr = ptr;
 266         mem = (caddr_t)ptr - OVERHEAD;
 267 
 268         /*
 269          * Optimization possibility :
 270          *      p = malloc(64);
 271          *      q = realloc(p, 64);
 272          * q can be same as p.
 273          * Apply this optimization for the normal
 274          * sized caches for now.
 275          */
 276         if (*(uintptr_t *)mem < MTMALLOC_OVERSIZE_MAGIC ||
 277             *(uintptr_t *)mem > MTMALLOC_MEMALIGN_MIN_MAGIC) {
 278                 cacheptr = (cache_t *)*(uintptr_t *)mem;
 279                 if (bytes <= (cacheptr->mt_size - OVERHEAD))
 280                         return (ptr);
 281         }
 282 
 283         new = malloc(bytes);
 284 
 285         if (new == NULL)
 286                 return (NULL);
 287 
 288         /*
 289          * If new == ptr, ptr has previously been freed. Passing a freed pointer
 290          * to realloc() is not allowed - unless the caller specifically states
 291          * otherwise, in which case we must avoid freeing ptr (ie new) before we
 292          * return new. There is (obviously) no requirement to memcpy() ptr to
 293          * new before we return.
 294          */
 295         if (new == ptr) {
 296                 if (!(debugopt & MTDOUBLEFREE))
 297                         abort();
 298                 return (new);
 299         }
 300 
 301         if (*(uintptr_t *)mem == MTMALLOC_MEMALIGN_MAGIC) {
 302                 mem -= OVERHEAD;
 303                 ptr = (void *)*(uintptr_t *)mem;
 304                 mem = (caddr_t)ptr - OVERHEAD;
 305                 shift = (size_t)((uintptr_t)data_ptr - (uintptr_t)ptr);
 306         } else if (*(uintptr_t *)mem == MTMALLOC_MEMALIGN_MIN_MAGIC) {
 307                 ptr = (void *) mem;
 308                 mem -= OVERHEAD;
 309                 shift = OVERHEAD;
 310         }
 311 
 312         if (*(uintptr_t *)mem == MTMALLOC_OVERSIZE_MAGIC) {
 313                 oversize_t *old;
 314 
 315                 old = (oversize_t *)(mem - OVSZ_SIZE);
 316                 (void) memcpy(new, data_ptr, MIN(bytes, old->size - shift));
 317                 free(ptr);
 318                 return (new);
 319         }
 320 
 321         cacheptr = (cache_t *)*(uintptr_t *)mem;
 322 
 323         (void) memcpy(new, data_ptr,
 324             MIN(cacheptr->mt_size - OVERHEAD - shift, bytes));
 325         free(ptr);
 326 
 327         return (new);
 328 }
 329 
 330 void *
 331 calloc(size_t nelem, size_t bytes)
 332 {
 333         void * ptr;
 334         size_t size;
 335 
 336         if (nelem == 0 || bytes == 0) {
 337                 size = 0;
 338         } else {
 339                 size = nelem * bytes;
 340 
 341                 /* check for overflow */
 342                 if ((size / nelem) != bytes) {
 343                         errno = ENOMEM;
 344                         return (NULL);
 345                 }
 346         }
 347 
 348         ptr = malloc(size);
 349         if (ptr == NULL)
 350                 return (NULL);
 351         (void) memset(ptr, 0, size);
 352 
 353         return (ptr);
 354 }
 355 
 356 void
 357 free(void * ptr)
 358 {
 359         cache_t *cacheptr;
 360         caddr_t mem;
 361         int32_t i;
 362         caddr_t freeblocks;
 363         uintptr_t offset;
 364         uchar_t mask;
 365         int32_t which_bit, num_bytes;
 366 
 367         if (ptr == NULL)
 368                 return;
 369 
 370         mem = (caddr_t)ptr - OVERHEAD;
 371 
 372         if (*(uintptr_t *)mem == MTMALLOC_MEMALIGN_MAGIC) {
 373                 mem -= OVERHEAD;
 374                 ptr = (void *)*(uintptr_t *)mem;
 375                 mem = (caddr_t)ptr - OVERHEAD;
 376         } else if (*(uintptr_t *)mem == MTMALLOC_MEMALIGN_MIN_MAGIC) {
 377                 ptr = (void *) mem;
 378                 mem -= OVERHEAD;
 379         }
 380 
 381         if (*(uintptr_t *)mem == MTMALLOC_OVERSIZE_MAGIC) {
 382                 oversize_t *big, **opp;
 383                 int bucket;
 384 
 385                 big = (oversize_t *)(mem - OVSZ_SIZE);
 386                 (void) mutex_lock(&oversize_lock);
 387 
 388                 bucket = HASH_OVERSIZE(big->addr);
 389                 for (opp = &ovsz_hashtab[bucket]; *opp != NULL;
 390                     opp = &(*opp)->hash_next)
 391                         if (*opp == big)
 392                                 break;
 393 
 394                 if (*opp == NULL) {
 395                         if (!(debugopt & MTDOUBLEFREE))
 396                                 abort();
 397                         (void) mutex_unlock(&oversize_lock);
 398                         return;
 399                 }
 400 
 401                 *opp = big->hash_next;       /* remove big from the hash table */
 402                 big->hash_next = NULL;
 403 
 404                 if (debugopt & MTDEBUGPATTERN)
 405                         copy_pattern(FREEPATTERN, ptr, big->size);
 406                 add_oversize(big);
 407                 (void) mutex_unlock(&oversize_lock);
 408                 return;
 409         }
 410 
 411         cacheptr = (cache_t *)*(uintptr_t *)mem;
 412         freeblocks = cacheptr->mt_freelist;
 413 
 414         /*
 415          * This is the distance measured in bits into the arena.
 416          * The value of offset is in bytes but there is a 1-1 correlation
 417          * between distance into the arena and distance into the
 418          * freelist bitmask.
 419          */
 420         offset = mem - cacheptr->mt_arena;
 421 
 422         /*
 423          * i is total number of bits to offset into freelist bitmask.
 424          */
 425 
 426         i = offset / cacheptr->mt_size;
 427 
 428         num_bytes = i >> 3;
 429 
 430         /*
 431          * which_bit is the bit offset into the byte in the freelist.
 432          * if our freelist bitmask looks like 0xf3 and we are freeing
 433          * block 5 (ie: the 6th block) our mask will be 0xf7 after
 434          * the free. Things go left to right that's why the mask is 0x80
 435          * and not 0x01.
 436          */
 437         which_bit = i - (num_bytes << 3);
 438 
 439         mask = 0x80 >> which_bit;
 440 
 441         freeblocks += num_bytes;
 442 
 443         if (debugopt & MTDEBUGPATTERN)
 444                 copy_pattern(FREEPATTERN, ptr, cacheptr->mt_size - OVERHEAD);
 445 
 446         (void) mutex_lock(&cacheptr->mt_cache_lock);
 447 
 448         if (*freeblocks & mask) {
 449                 if (!(debugopt & MTDOUBLEFREE))
 450                         abort();
 451         } else {
 452                 *freeblocks |= mask;
 453                 cacheptr->mt_nfree++;
 454         }
 455 
 456         (void) mutex_unlock(&cacheptr->mt_cache_lock);
 457 }
 458 
 459 void *
 460 memalign(size_t alignment, size_t size)
 461 {
 462         size_t alloc_size;
 463         uintptr_t offset;
 464         void *alloc_buf;
 465         void *ret_buf;
 466 
 467         if (size == 0 || alignment == 0 || misaligned(alignment) ||
 468             (alignment & (alignment - 1)) != 0) {
 469                 errno = EINVAL;
 470                 return (NULL);
 471         }
 472 
 473         /* <= MTMALLOC_MIN_ALIGN, malloc can provide directly */
 474         if (alignment <= MTMALLOC_MIN_ALIGN)
 475                 return (malloc(size));
 476 
 477         alloc_size = size + alignment - MTMALLOC_MIN_ALIGN;
 478 
 479         if (alloc_size < size) { /* overflow */
 480                 errno = ENOMEM;
 481                 return (NULL);
 482         }
 483 
 484         alloc_buf = malloc(alloc_size);
 485 
 486         if (alloc_buf == NULL)
 487                 /* malloc sets errno */
 488                 return (NULL);
 489 
 490         /*
 491          * If alloc_size > MAX_CACHED, malloc() will have returned a multiple of
 492          * MTMALLOC_MIN_ALIGN, having rounded-up alloc_size if necessary. Since
 493          * we will use alloc_size to return the excess fragments to the free
 494          * list, we also round-up alloc_size if necessary.
 495          */
 496         if ((alloc_size > MAX_CACHED) &&
 497             (alloc_size & (MTMALLOC_MIN_ALIGN - 1)))
 498                 alloc_size = ALIGN(alloc_size, MTMALLOC_MIN_ALIGN);
 499 
 500         if ((offset = (uintptr_t)alloc_buf & (alignment - 1)) == 0) {
 501                 /* aligned correctly */
 502 
 503                 size_t frag_size = alloc_size -
 504                     (size + MTMALLOC_MIN_ALIGN + OVSZ_HEADER_SIZE);
 505 
 506                 /*
 507                  * If the leftover piece of the memory > MAX_CACHED,
 508                  * split off the piece and return it back to the freelist.
 509                  */
 510                 if (IS_OVERSIZE(frag_size, alloc_size)) {
 511                         oversize_t *orig, *tail;
 512                         uintptr_t taddr;
 513                         size_t data_size;
 514                         taddr = ALIGN((uintptr_t)alloc_buf + size,
 515                             MTMALLOC_MIN_ALIGN);
 516                         data_size = taddr - (uintptr_t)alloc_buf;
 517                         orig = (oversize_t *)((uintptr_t)alloc_buf -
 518                             OVSZ_HEADER_SIZE);
 519                         frag_size = orig->size - data_size -
 520                             OVSZ_HEADER_SIZE;
 521                         orig->size = data_size;
 522                         tail = oversize_header_alloc(taddr, frag_size);
 523                         free_oversize(tail);
 524                 }
 525                 ret_buf = alloc_buf;
 526         } else {
 527                 uchar_t oversize_bits = 0;
 528                 size_t  head_sz, data_sz, tail_sz;
 529                 uintptr_t ret_addr, taddr, shift, tshift;
 530                 oversize_t *orig, *tail, *big;
 531                 size_t tsize;
 532 
 533                 /* needs to be aligned */
 534                 shift = alignment - offset;
 535 
 536                 assert(shift >= MTMALLOC_MIN_ALIGN);
 537 
 538                 ret_addr = ((uintptr_t)alloc_buf + shift);
 539                 ret_buf = (void *)ret_addr;
 540 
 541                 if (alloc_size <= MAX_CACHED) {
 542                         MEMALIGN_HEADER_ALLOC(ret_addr, shift, alloc_buf);
 543                         return (ret_buf);
 544                 }
 545 
 546                 /*
 547                  * Only check for the fragments when the memory is allocted
 548                  * from oversize_list.  Split off a fragment and return it
 549                  * to the oversize freelist when it's > MAX_CACHED.
 550                  */
 551 
 552                 head_sz = shift - MAX(MEMALIGN_HEADER_SIZE, OVSZ_HEADER_SIZE);
 553 
 554                 tail_sz = alloc_size -
 555                     (shift + size + MTMALLOC_MIN_ALIGN + OVSZ_HEADER_SIZE);
 556 
 557                 oversize_bits |= IS_OVERSIZE(head_sz, alloc_size) |
 558                     IS_OVERSIZE(size, alloc_size) << DATA_SHIFT |
 559                     IS_OVERSIZE(tail_sz, alloc_size) << TAIL_SHIFT;
 560 
 561                 switch (oversize_bits) {
 562                         case NONE_OVERSIZE:
 563                         case DATA_OVERSIZE:
 564                                 MEMALIGN_HEADER_ALLOC(ret_addr, shift,
 565                                     alloc_buf);
 566                                 break;
 567                         case HEAD_OVERSIZE:
 568                                 /*
 569                                  * If we can extend data > MAX_CACHED and have
 570                                  * head still > MAX_CACHED, we split head-end
 571                                  * as the case of head-end and data oversized,
 572                                  * otherwise just create memalign header.
 573                                  */
 574                                 tsize = (shift + size) - (MAX_CACHED + 8 +
 575                                     MTMALLOC_MIN_ALIGN + OVSZ_HEADER_SIZE);
 576 
 577                                 if (!IS_OVERSIZE(tsize, alloc_size)) {
 578                                         MEMALIGN_HEADER_ALLOC(ret_addr, shift,
 579                                             alloc_buf);
 580                                         break;
 581                                 } else {
 582                                         tsize += OVSZ_HEADER_SIZE;
 583                                         taddr = ALIGN((uintptr_t)alloc_buf +
 584                                             tsize, MTMALLOC_MIN_ALIGN);
 585                                         tshift = ret_addr - taddr;
 586                                         MEMALIGN_HEADER_ALLOC(ret_addr, tshift,
 587                                             taddr);
 588                                         ret_addr = taddr;
 589                                         shift = ret_addr - (uintptr_t)alloc_buf;
 590                                 }
 591                                 /* FALLTHROUGH */
 592                         case HEAD_AND_DATA_OVERSIZE:
 593                                 /*
 594                                  * Split off the head fragment and
 595                                  * return it back to oversize freelist.
 596                                  * Create oversize header for the piece
 597                                  * of (data + tail fragment).
 598                                  */
 599                                 orig = (oversize_t *)((uintptr_t)alloc_buf -
 600                                     OVSZ_HEADER_SIZE);
 601                                 big = oversize_header_alloc(ret_addr -
 602                                     OVSZ_HEADER_SIZE, (orig->size - shift));
 603                                 (void) mutex_lock(&oversize_lock);
 604                                 insert_hash(big);
 605                                 (void) mutex_unlock(&oversize_lock);
 606                                 orig->size = shift - OVSZ_HEADER_SIZE;
 607 
 608                                 /* free up the head fragment */
 609                                 free_oversize(orig);
 610                                 break;
 611                         case TAIL_OVERSIZE:
 612                                 /*
 613                                  * If we can extend data > MAX_CACHED and have
 614                                  * tail-end still > MAX_CACHED, we split tail
 615                                  * end, otherwise just create memalign header.
 616                                  */
 617                                 orig = (oversize_t *)((uintptr_t)alloc_buf -
 618                                     OVSZ_HEADER_SIZE);
 619                                 tsize =  orig->size - (MAX_CACHED + 8 +
 620                                     shift + OVSZ_HEADER_SIZE +
 621                                     MTMALLOC_MIN_ALIGN);
 622                                 if (!IS_OVERSIZE(tsize, alloc_size)) {
 623                                         MEMALIGN_HEADER_ALLOC(ret_addr, shift,
 624                                             alloc_buf);
 625                                         break;
 626                                 } else {
 627                                         size = MAX_CACHED + 8;
 628                                 }
 629                                 /* FALLTHROUGH */
 630                         case DATA_AND_TAIL_OVERSIZE:
 631                                 /*
 632                                  * Split off the tail fragment and
 633                                  * return it back to oversize freelist.
 634                                  * Create memalign header and adjust
 635                                  * the size for the piece of
 636                                  * (head fragment + data).
 637                                  */
 638                                 taddr = ALIGN(ret_addr + size,
 639                                     MTMALLOC_MIN_ALIGN);
 640                                 data_sz = (size_t)(taddr -
 641                                     (uintptr_t)alloc_buf);
 642                                 orig = (oversize_t *)((uintptr_t)alloc_buf -
 643                                     OVSZ_HEADER_SIZE);
 644                                 tsize = orig->size - data_sz;
 645                                 orig->size = data_sz;
 646                                 MEMALIGN_HEADER_ALLOC(ret_buf, shift,
 647                                     alloc_buf);
 648                                 tsize -= OVSZ_HEADER_SIZE;
 649                                 tail = oversize_header_alloc(taddr,  tsize);
 650                                 free_oversize(tail);
 651                                 break;
 652                         case HEAD_AND_TAIL_OVERSIZE:
 653                                 /*
 654                                  * Split off the head fragment.
 655                                  * We try to free up tail-end when we can
 656                                  * extend data size to (MAX_CACHED + 8)
 657                                  * and remain tail-end oversized.
 658                                  * The bottom line is all split pieces
 659                                  * should be oversize in size.
 660                                  */
 661                                 orig = (oversize_t *)((uintptr_t)alloc_buf -
 662                                     OVSZ_HEADER_SIZE);
 663                                 tsize =  orig->size - (MAX_CACHED + 8 +
 664                                     OVSZ_HEADER_SIZE + shift +
 665                                     MTMALLOC_MIN_ALIGN);
 666 
 667                                 if (!IS_OVERSIZE(tsize, alloc_size)) {
 668                                         /*
 669                                          * If the chunk is not big enough
 670                                          * to make both data and tail oversize
 671                                          * we just keep them as one piece.
 672                                          */
 673                                         big = oversize_header_alloc(ret_addr -
 674                                             OVSZ_HEADER_SIZE,
 675                                             orig->size - shift);
 676                                         (void) mutex_lock(&oversize_lock);
 677                                         insert_hash(big);
 678                                         (void) mutex_unlock(&oversize_lock);
 679                                         orig->size = shift - OVSZ_HEADER_SIZE;
 680                                         free_oversize(orig);
 681                                         break;
 682                                 } else {
 683                                         /*
 684                                          * extend data size > MAX_CACHED
 685                                          * and handle it as head, data, tail
 686                                          * are all oversized.
 687                                          */
 688                                         size = MAX_CACHED + 8;
 689                                 }
 690                                 /* FALLTHROUGH */
 691                         case ALL_OVERSIZE:
 692                                 /*
 693                                  * split off the head and tail fragments,
 694                                  * return them back to the oversize freelist.
 695                                  * Alloc oversize header for data seg.
 696                                  */
 697                                 orig = (oversize_t *)((uintptr_t)alloc_buf -
 698                                     OVSZ_HEADER_SIZE);
 699                                 tsize = orig->size;
 700                                 orig->size = shift - OVSZ_HEADER_SIZE;
 701                                 free_oversize(orig);
 702 
 703                                 taddr = ALIGN(ret_addr + size,
 704                                     MTMALLOC_MIN_ALIGN);
 705                                 data_sz = taddr - ret_addr;
 706                                 assert(tsize > (shift + data_sz +
 707                                     OVSZ_HEADER_SIZE));
 708                                 tail_sz = tsize -
 709                                     (shift + data_sz + OVSZ_HEADER_SIZE);
 710 
 711                                 /* create oversize header for data seg */
 712                                 big = oversize_header_alloc(ret_addr -
 713                                     OVSZ_HEADER_SIZE, data_sz);
 714                                 (void) mutex_lock(&oversize_lock);
 715                                 insert_hash(big);
 716                                 (void) mutex_unlock(&oversize_lock);
 717 
 718                                 /* create oversize header for tail fragment */
 719                                 tail = oversize_header_alloc(taddr, tail_sz);
 720                                 free_oversize(tail);
 721                                 break;
 722                         default:
 723                                 /* should not reach here */
 724                                 assert(0);
 725                 }
 726         }
 727         return (ret_buf);
 728 }
 729 
 730 
 731 void *
 732 valloc(size_t size)
 733 {
 734         static unsigned pagesize;
 735 
 736         if (size == 0)
 737                 return (NULL);
 738 
 739         if (!pagesize)
 740                 pagesize = sysconf(_SC_PAGESIZE);
 741 
 742         return (memalign(pagesize, size));
 743 }
 744 
 745 void
 746 mallocctl(int cmd, long value)
 747 {
 748         switch (cmd) {
 749 
 750         case MTDEBUGPATTERN:
 751                 /*
 752                  * Reinitialize free blocks in case malloc() is called prior
 753                  * to mallocctl().
 754                  */
 755                 if (value && !(debugopt & cmd)) {
 756                         reinit++;
 757                         debugopt |= cmd;
 758                         reinit_cpu_list();
 759                 }
 760                 /*FALLTHRU*/
 761         case MTDOUBLEFREE:
 762         case MTINITBUFFER:
 763                 if (value)
 764                         debugopt |= cmd;
 765                 else
 766                         debugopt &= ~cmd;
 767                 break;
 768         case MTCHUNKSIZE:
 769                 if (value >= MINSIZE && value <= MAXSIZE)
 770                         requestsize = value;
 771                 break;
 772         default:
 773                 break;
 774         }
 775 }
 776 
 777 /*
 778  * Initialization function, called from the init section of the library.
 779  * No locking is required here because we are single-threaded during
 780  * library initialization.
 781  */
 782 static void
 783 setup_caches(void)
 784 {
 785         uintptr_t oldbrk;
 786         uintptr_t newbrk;
 787 
 788         size_t cache_space_needed;
 789         size_t padding;
 790 
 791         curcpu_func new_curcpu;
 792         uint_t new_cpu_mask;
 793         percpu_t *new_cpu_list;
 794 
 795         uint_t i, j;
 796         uintptr_t list_addr;
 797 
 798         /*
 799          * Get a decent "current cpu identifier", to be used to reduce
 800          * contention.  Eventually, this should be replaced by an interface
 801          * to get the actual CPU sequence number in libthread/liblwp.
 802          */
 803         new_curcpu = (curcpu_func)thr_self;
 804         if ((ncpus = 2 * sysconf(_SC_NPROCESSORS_CONF)) <= 0)
 805                 ncpus = 4; /* decent default value */
 806 
 807         /* round ncpus up to a power of 2 */
 808         while (ncpus & (ncpus - 1))
 809                 ncpus++;
 810 
 811         new_cpu_mask = ncpus - 1;       /* create the cpu mask */
 812 
 813         /*
 814          * We now do some magic with the brk.  What we want to get in the
 815          * end is a bunch of well-aligned stuff in a big initial allocation.
 816          * Along the way, we do sanity checks to make sure no one else has
 817          * touched the brk (which shouldn't happen, but it's always good to
 818          * check)
 819          *
 820          * First, make sure sbrk is sane, and store the current brk in oldbrk.
 821          */
 822         oldbrk = (uintptr_t)sbrk(0);
 823         if ((void *)oldbrk == (void *)-1)
 824                 abort();        /* sbrk is broken -- we're doomed. */
 825 
 826         /*
 827          * Now, align the brk to a multiple of CACHE_COHERENCY_UNIT, so that
 828          * the percpu structures and cache lists will be properly aligned.
 829          *
 830          *   2.  All hunks will be page-aligned, assuming HUNKSIZE >= PAGESIZE,
 831          *      so they can be paged out individually.
 832          */
 833         newbrk = ALIGN(oldbrk, CACHE_COHERENCY_UNIT);
 834         if (newbrk != oldbrk && (uintptr_t)sbrk(newbrk - oldbrk) != oldbrk)
 835                 abort();        /* sbrk is broken -- we're doomed. */
 836 
 837         /*
 838          * For each cpu, there is one percpu_t and a list of caches
 839          */
 840         cache_space_needed = ncpus * (sizeof (percpu_t) + CACHELIST_SIZE);
 841 
 842         new_cpu_list = (percpu_t *)sbrk(cache_space_needed);
 843 
 844         if (new_cpu_list == (percpu_t *)-1 ||
 845             (uintptr_t)new_cpu_list != newbrk)
 846                 abort();        /* sbrk is broken -- we're doomed. */
 847 
 848         /*
 849          * Finally, align the brk to HUNKSIZE so that all hunks are
 850          * page-aligned, to avoid edge-effects.
 851          */
 852 
 853         newbrk = (uintptr_t)new_cpu_list + cache_space_needed;
 854 
 855         padding = ALIGN(newbrk, HUNKSIZE) - newbrk;
 856 
 857         if (padding > 0 && (uintptr_t)sbrk(padding) != newbrk)
 858                 abort();        /* sbrk is broken -- we're doomed. */
 859 
 860         list_addr = ((uintptr_t)new_cpu_list + (sizeof (percpu_t) * ncpus));
 861 
 862         /* initialize the percpu list */
 863         for (i = 0; i < ncpus; i++) {
 864                 new_cpu_list[i].mt_caches = (cache_head_t *)list_addr;
 865                 for (j = 0; j < NUM_CACHES; j++) {
 866                         new_cpu_list[i].mt_caches[j].mt_cache = NULL;
 867                         new_cpu_list[i].mt_caches[j].mt_hint = NULL;
 868                 }
 869 
 870                 (void) mutex_init(&new_cpu_list[i].mt_parent_lock,
 871                     USYNC_THREAD, NULL);
 872 
 873                 /* get the correct cache list alignment */
 874                 list_addr += CACHELIST_SIZE;
 875         }
 876 
 877         /*
 878          * Initialize oversize listhead
 879          */
 880         oversize_list.next_bysize = &oversize_list;
 881         oversize_list.prev_bysize = &oversize_list;
 882         oversize_list.next_byaddr = &oversize_list;
 883         oversize_list.prev_byaddr = &oversize_list;
 884         oversize_list.addr = NULL;
 885         oversize_list.size = 0;         /* sentinal */
 886 
 887         /*
 888          * Now install the global variables.
 889          */
 890         curcpu = new_curcpu;
 891         cpu_mask = new_cpu_mask;
 892         cpu_list = new_cpu_list;
 893 }
 894 
 895 static void
 896 create_cache(cache_t *cp, size_t size, uint_t chunksize)
 897 {
 898         long nblocks;
 899 
 900         (void) mutex_init(&cp->mt_cache_lock, USYNC_THREAD, NULL);
 901         cp->mt_size = size;
 902         cp->mt_freelist = ((caddr_t)cp + sizeof (cache_t));
 903         cp->mt_span = chunksize * HUNKSIZE - sizeof (cache_t);
 904         cp->mt_hunks = chunksize;
 905         /*
 906          * rough calculation. We will need to adjust later.
 907          */
 908         nblocks = cp->mt_span / cp->mt_size;
 909         nblocks >>= 3;
 910         if (nblocks == 0) { /* less than 8 free blocks in this pool */
 911                 int32_t numblocks = 0;
 912                 long i = cp->mt_span;
 913                 size_t sub = cp->mt_size;
 914                 uchar_t mask = 0;
 915 
 916                 while (i > sub) {
 917                         numblocks++;
 918                         i -= sub;
 919                 }
 920                 nblocks = numblocks;
 921                 cp->mt_arena = (caddr_t)ALIGN(cp->mt_freelist + 8, 8);
 922                 cp->mt_nfree = numblocks;
 923                 while (numblocks--) {
 924                         mask |= 0x80 >> numblocks;
 925                 }
 926                 *(cp->mt_freelist) = mask;
 927         } else {
 928                 cp->mt_arena = (caddr_t)ALIGN((caddr_t)cp->mt_freelist +
 929                     nblocks, 32);
 930                 /* recompute nblocks */
 931                 nblocks = (uintptr_t)((caddr_t)cp->mt_freelist +
 932                     cp->mt_span - cp->mt_arena) / cp->mt_size;
 933                 cp->mt_nfree = ((nblocks >> 3) << 3);
 934                 /* Set everything to free */
 935                 (void) memset(cp->mt_freelist, 0xff, nblocks >> 3);
 936         }
 937 
 938         if (debugopt & MTDEBUGPATTERN)
 939                 copy_pattern(FREEPATTERN, cp->mt_arena, cp->mt_size * nblocks);
 940 
 941         cp->mt_next = NULL;
 942 }
 943 
 944 static void
 945 reinit_cpu_list(void)
 946 {
 947         oversize_t *wp = oversize_list.next_bysize;
 948         percpu_t *cpuptr;
 949         cache_t *thiscache;
 950         cache_head_t *cachehead;
 951 
 952         /* Reinitialize free oversize blocks. */
 953         (void) mutex_lock(&oversize_lock);
 954         if (debugopt & MTDEBUGPATTERN)
 955                 for (; wp != &oversize_list; wp = wp->next_bysize)
 956                         copy_pattern(FREEPATTERN, wp->addr, wp->size);
 957         (void) mutex_unlock(&oversize_lock);
 958 
 959         /* Reinitialize free blocks. */
 960         for (cpuptr = &cpu_list[0]; cpuptr < &cpu_list[ncpus]; cpuptr++) {
 961                 (void) mutex_lock(&cpuptr->mt_parent_lock);
 962                 for (cachehead = &cpuptr->mt_caches[0]; cachehead <
 963                     &cpuptr->mt_caches[NUM_CACHES]; cachehead++) {
 964                         for (thiscache = cachehead->mt_cache; thiscache != NULL;
 965                             thiscache = thiscache->mt_next) {
 966                                 (void) mutex_lock(&thiscache->mt_cache_lock);
 967                                 if (thiscache->mt_nfree == 0) {
 968                                         (void) mutex_unlock(
 969                                             &thiscache->mt_cache_lock);
 970                                         continue;
 971                                 }
 972                                 if (thiscache != NULL)
 973                                         reinit_cache(thiscache);
 974                                 (void) mutex_unlock(&thiscache->mt_cache_lock);
 975                         }
 976                 }
 977                 (void) mutex_unlock(&cpuptr->mt_parent_lock);
 978         }
 979         reinit = 0;
 980 }
 981 
 982 static void
 983 reinit_cache(cache_t *thiscache)
 984 {
 985         uint32_t *freeblocks; /* not a uintptr_t on purpose */
 986         int32_t i, n;
 987         caddr_t ret;
 988 
 989         freeblocks = (uint32_t *)thiscache->mt_freelist;
 990         while (freeblocks < (uint32_t *)thiscache->mt_arena) {
 991                 if (*freeblocks & 0xffffffff) {
 992                         for (i = 0; i < 32; i++) {
 993                                 if (FLIP_EM(*freeblocks) & (0x80000000 >> i)) {
 994                                         n = (uintptr_t)(((freeblocks -
 995                                             (uint32_t *)thiscache->mt_freelist)
 996                                             << 5) + i) * thiscache->mt_size;
 997                                         ret = thiscache->mt_arena + n;
 998                                         ret += OVERHEAD;
 999                                         copy_pattern(FREEPATTERN, ret,
1000                                             thiscache->mt_size);
1001                                 }
1002                         }
1003                 }
1004                 freeblocks++;
1005         }
1006 }
1007 
1008 static void *
1009 malloc_internal(size_t size, percpu_t *cpuptr)
1010 {
1011         cache_head_t *cachehead;
1012         cache_t *thiscache, *hintcache;
1013         int32_t i, n, logsz, bucket;
1014         uint32_t index;
1015         uint32_t *freeblocks; /* not a uintptr_t on purpose */
1016         caddr_t ret;
1017 
1018         logsz = MIN_CACHED_SHIFT;
1019 
1020         while (size > (1 << logsz))
1021                 logsz++;
1022 
1023         bucket = logsz - MIN_CACHED_SHIFT;
1024 
1025         (void) mutex_lock(&cpuptr->mt_parent_lock);
1026 
1027         /*
1028          * Find a cache of the appropriate size with free buffers.
1029          *
1030          * We don't need to lock each cache as we check their mt_nfree count,
1031          * since:
1032          *      1.  We are only looking for caches with mt_nfree > 0.  If a
1033          *         free happens during our search, it will increment mt_nfree,
1034          *         which will not effect the test.
1035          *      2.  Allocations can decrement mt_nfree, but they can't happen
1036          *         as long as we hold mt_parent_lock.
1037          */
1038 
1039         cachehead = &cpuptr->mt_caches[bucket];
1040 
1041         /* Search through the list, starting at the mt_hint */
1042         thiscache = cachehead->mt_hint;
1043 
1044         while (thiscache != NULL && thiscache->mt_nfree == 0)
1045                 thiscache = thiscache->mt_next;
1046 
1047         if (thiscache == NULL) {
1048                 /* wrap around -- search up to the hint */
1049                 thiscache = cachehead->mt_cache;
1050                 hintcache = cachehead->mt_hint;
1051 
1052                 while (thiscache != NULL && thiscache != hintcache &&
1053                     thiscache->mt_nfree == 0)
1054                         thiscache = thiscache->mt_next;
1055 
1056                 if (thiscache == hintcache)
1057                         thiscache = NULL;
1058         }
1059 
1060 
1061         if (thiscache == NULL) { /* there are no free caches */
1062                 int32_t thisrequest = requestsize;
1063                 int32_t buffer_size = (1 << logsz) + OVERHEAD;
1064 
1065                 thiscache = (cache_t *)morecore(thisrequest * HUNKSIZE);
1066 
1067                 if (thiscache == (cache_t *)-1) {
1068                         (void) mutex_unlock(&cpuptr->mt_parent_lock);
1069                         errno = EAGAIN;
1070                         return (NULL);
1071                 }
1072                 create_cache(thiscache, buffer_size, thisrequest);
1073 
1074                 /* link in the new block at the beginning of the list */
1075                 thiscache->mt_next = cachehead->mt_cache;
1076                 cachehead->mt_cache = thiscache;
1077         }
1078 
1079         /* update the hint to the cache we found or created */
1080         cachehead->mt_hint = thiscache;
1081 
1082         /* thiscache now points to a cache with available space */
1083         (void) mutex_lock(&thiscache->mt_cache_lock);
1084 
1085         freeblocks = (uint32_t *)thiscache->mt_freelist;
1086         while (freeblocks < (uint32_t *)thiscache->mt_arena) {
1087                 if (*freeblocks & 0xffffffff)
1088                         break;
1089                 freeblocks++;
1090                 if (freeblocks < (uint32_t *)thiscache->mt_arena &&
1091                     *freeblocks & 0xffffffff)
1092                         break;
1093                 freeblocks++;
1094                 if (freeblocks < (uint32_t *)thiscache->mt_arena &&
1095                     *freeblocks & 0xffffffff)
1096                         break;
1097                 freeblocks++;
1098                 if (freeblocks < (uint32_t *)thiscache->mt_arena &&
1099                     *freeblocks & 0xffffffff)
1100                         break;
1101                 freeblocks++;
1102         }
1103 
1104         /*
1105          * the offset from mt_freelist to freeblocks is the offset into
1106          * the arena. Be sure to include the offset into freeblocks
1107          * of the bitmask. n is the offset.
1108          */
1109         for (i = 0; i < 32; ) {
1110                 if (FLIP_EM(*freeblocks) & (0x80000000 >> i++))
1111                         break;
1112                 if (FLIP_EM(*freeblocks) & (0x80000000 >> i++))
1113                         break;
1114                 if (FLIP_EM(*freeblocks) & (0x80000000 >> i++))
1115                         break;
1116                 if (FLIP_EM(*freeblocks) & (0x80000000 >> i++))
1117                         break;
1118         }
1119         index = 0x80000000 >> --i;
1120 
1121 
1122         *freeblocks &= FLIP_EM(~index);
1123 
1124         thiscache->mt_nfree--;
1125 
1126         (void) mutex_unlock(&thiscache->mt_cache_lock);
1127         (void) mutex_unlock(&cpuptr->mt_parent_lock);
1128 
1129         n = (uintptr_t)(((freeblocks - (uint32_t *)thiscache->mt_freelist) << 5)
1130             + i) * thiscache->mt_size;
1131         /*
1132          * Now you have the offset in n, you've changed the free mask
1133          * in the freelist. Nothing left to do but find the block
1134          * in the arena and put the value of thiscache in the word
1135          * ahead of the handed out address and return the memory
1136          * back to the user.
1137          */
1138         ret = thiscache->mt_arena + n;
1139 
1140         /* Store the cache addr for this buf. Makes free go fast. */
1141         *(uintptr_t *)ret = (uintptr_t)thiscache;
1142 
1143         /*
1144          * This assert makes sure we don't hand out memory that is not
1145          * owned by this cache.
1146          */
1147         assert(ret + thiscache->mt_size <= thiscache->mt_freelist +
1148             thiscache->mt_span);
1149 
1150         ret += OVERHEAD;
1151 
1152         assert(((uintptr_t)ret & 7) == 0); /* are we 8 byte aligned */
1153 
1154         if (reinit == 0 && (debugopt & MTDEBUGPATTERN))
1155                 if (verify_pattern(FREEPATTERN, ret, size))
1156                         abort();        /* reference after free */
1157 
1158         if (debugopt & MTINITBUFFER)
1159                 copy_pattern(INITPATTERN, ret, size);
1160         return ((void *)ret);
1161 }
1162 
1163 static void *
1164 morecore(size_t bytes)
1165 {
1166         void * ret;
1167 
1168         if (bytes > LONG_MAX) {
1169                 intptr_t wad;
1170                 /*
1171                  * The request size is too big. We need to do this in
1172                  * chunks. Sbrk only takes an int for an arg.
1173                  */
1174                 if (bytes == ULONG_MAX)
1175                         return ((void *)-1);
1176 
1177                 ret = sbrk(0);
1178                 wad = LONG_MAX;
1179                 while (wad > 0) {
1180                         if (sbrk(wad) == (void *)-1) {
1181                                 if (ret != sbrk(0))
1182                                         (void) sbrk(-LONG_MAX);
1183                                 return ((void *)-1);
1184                         }
1185                         bytes -= LONG_MAX;
1186                         wad = bytes;
1187                 }
1188         } else
1189                 ret = sbrk(bytes);
1190 
1191         return (ret);
1192 }
1193 
1194 
1195 static void *
1196 oversize(size_t size)
1197 {
1198         caddr_t ret;
1199         oversize_t *big;
1200 
1201         /* make sure we will not overflow */
1202         if (size > MAX_MTMALLOC) {
1203                 errno = ENOMEM;
1204                 return (NULL);
1205         }
1206 
1207         /*
1208          * Since we ensure every address we hand back is
1209          * MTMALLOC_MIN_ALIGN-byte aligned, ALIGNing size ensures that the
1210          * memory handed out is MTMALLOC_MIN_ALIGN-byte aligned at both ends.
1211          * This eases the implementation of MTDEBUGPATTERN and MTINITPATTERN,
1212          * particularly where coalescing occurs.
1213          */
1214         size = ALIGN(size, MTMALLOC_MIN_ALIGN);
1215 
1216         /*
1217          * The idea with the global lock is that we are sure to
1218          * block in the kernel anyway since given an oversize alloc
1219          * we are sure to have to call morecore();
1220          */
1221         (void) mutex_lock(&oversize_lock);
1222 
1223         if ((big = find_oversize(size)) != NULL) {
1224                 if (reinit == 0 && (debugopt & MTDEBUGPATTERN))
1225                         if (verify_pattern(FREEPATTERN, big->addr, size))
1226                                 abort();        /* reference after free */
1227         } else {
1228                 /* Get more 8-byte aligned memory from heap */
1229                 ret = morecore(size + OVSZ_HEADER_SIZE);
1230                 if (ret == (caddr_t)-1) {
1231                         (void) mutex_unlock(&oversize_lock);
1232                         errno = ENOMEM;
1233                         return (NULL);
1234                 }
1235                 big = oversize_header_alloc((uintptr_t)ret, size);
1236         }
1237         ret = big->addr;
1238 
1239         insert_hash(big);
1240 
1241         if (debugopt & MTINITBUFFER)
1242                 copy_pattern(INITPATTERN, ret, size);
1243 
1244         (void) mutex_unlock(&oversize_lock);
1245         assert(((uintptr_t)ret & 7) == 0); /* are we 8 byte aligned */
1246         return ((void *)ret);
1247 }
1248 
1249 static void
1250 insert_oversize(oversize_t *op, oversize_t *nx)
1251 {
1252         oversize_t *sp;
1253 
1254         /* locate correct insertion point in size-ordered list */
1255         for (sp = oversize_list.next_bysize;
1256             sp != &oversize_list && (op->size > sp->size);
1257             sp = sp->next_bysize)
1258                 ;
1259 
1260         /* link into size-ordered list */
1261         op->next_bysize = sp;
1262         op->prev_bysize = sp->prev_bysize;
1263         op->prev_bysize->next_bysize = op;
1264         op->next_bysize->prev_bysize = op;
1265 
1266         /*
1267          * link item into address-ordered list
1268          * (caller provides insertion point as an optimization)
1269          */
1270         op->next_byaddr = nx;
1271         op->prev_byaddr = nx->prev_byaddr;
1272         op->prev_byaddr->next_byaddr = op;
1273         op->next_byaddr->prev_byaddr = op;
1274 
1275 }
1276 
1277 static void
1278 unlink_oversize(oversize_t *lp)
1279 {
1280         /* unlink from address list */
1281         lp->prev_byaddr->next_byaddr = lp->next_byaddr;
1282         lp->next_byaddr->prev_byaddr = lp->prev_byaddr;
1283 
1284         /* unlink from size list */
1285         lp->prev_bysize->next_bysize = lp->next_bysize;
1286         lp->next_bysize->prev_bysize = lp->prev_bysize;
1287 }
1288 
1289 static void
1290 position_oversize_by_size(oversize_t *op)
1291 {
1292         oversize_t *sp;
1293 
1294         if (op->size > op->next_bysize->size ||
1295             op->size < op->prev_bysize->size) {
1296 
1297                 /* unlink from size list */
1298                 op->prev_bysize->next_bysize = op->next_bysize;
1299                 op->next_bysize->prev_bysize = op->prev_bysize;
1300 
1301                 /* locate correct insertion point in size-ordered list */
1302                 for (sp = oversize_list.next_bysize;
1303                     sp != &oversize_list && (op->size > sp->size);
1304                     sp = sp->next_bysize)
1305                         ;
1306 
1307                 /* link into size-ordered list */
1308                 op->next_bysize = sp;
1309                 op->prev_bysize = sp->prev_bysize;
1310                 op->prev_bysize->next_bysize = op;
1311                 op->next_bysize->prev_bysize = op;
1312         }
1313 }
1314 
1315 static void
1316 add_oversize(oversize_t *lp)
1317 {
1318         int merge_flags = INSERT_ONLY;
1319         oversize_t *nx;         /* ptr to item right of insertion point */
1320         oversize_t *pv;         /* ptr to item left of insertion point */
1321         uint_t size_lp, size_pv, size_nx;
1322         uintptr_t endp_lp, endp_pv, endp_nx;
1323 
1324         /*
1325          * Locate insertion point in address-ordered list
1326          */
1327 
1328         for (nx = oversize_list.next_byaddr;
1329             nx != &oversize_list && (lp->addr > nx->addr);
1330             nx = nx->next_byaddr)
1331                 ;
1332 
1333         /*
1334          * Determine how to add chunk to oversize freelist
1335          */
1336 
1337         size_lp = OVSZ_HEADER_SIZE + lp->size;
1338         endp_lp = ALIGN((uintptr_t)lp + size_lp, MTMALLOC_MIN_ALIGN);
1339         size_lp = endp_lp - (uintptr_t)lp;
1340 
1341         pv = nx->prev_byaddr;
1342 
1343         if (pv->size) {
1344 
1345                 size_pv = OVSZ_HEADER_SIZE + pv->size;
1346                 endp_pv = ALIGN((uintptr_t)pv + size_pv,
1347                     MTMALLOC_MIN_ALIGN);
1348                 size_pv = endp_pv - (uintptr_t)pv;
1349 
1350                 /* Check for adjacency with left chunk */
1351                 if ((uintptr_t)lp == endp_pv)
1352                         merge_flags |= COALESCE_LEFT;
1353         }
1354 
1355         if (nx->size) {
1356 
1357                 /* Check for adjacency with right chunk */
1358                 if ((uintptr_t)nx == endp_lp) {
1359                         size_nx = OVSZ_HEADER_SIZE + nx->size;
1360                         endp_nx = ALIGN((uintptr_t)nx + size_nx,
1361                             MTMALLOC_MIN_ALIGN);
1362                         size_nx = endp_nx - (uintptr_t)nx;
1363                         merge_flags |= COALESCE_RIGHT;
1364                 }
1365         }
1366 
1367         /*
1368          * If MTDEBUGPATTERN==1, lp->addr will have been overwritten with
1369          * FREEPATTERN for lp->size bytes. If we can merge, the oversize
1370          * header(s) that will also become part of the memory available for
1371          * reallocation (ie lp and/or nx) must also be overwritten with
1372          * FREEPATTERN or we will SIGABRT when this memory is next reallocated.
1373          */
1374         switch (merge_flags) {
1375 
1376         case INSERT_ONLY:               /* Coalescing not possible */
1377                 insert_oversize(lp, nx);
1378                 break;
1379         case COALESCE_LEFT:
1380                 pv->size += size_lp;
1381                 position_oversize_by_size(pv);
1382                 if (debugopt & MTDEBUGPATTERN)
1383                         copy_pattern(FREEPATTERN, lp, OVSZ_HEADER_SIZE);
1384                 break;
1385         case COALESCE_RIGHT:
1386                 unlink_oversize(nx);
1387                 lp->size += size_nx;
1388                 insert_oversize(lp, pv->next_byaddr);
1389                 if (debugopt & MTDEBUGPATTERN)
1390                         copy_pattern(FREEPATTERN, nx, OVSZ_HEADER_SIZE);
1391                 break;
1392         case COALESCE_WITH_BOTH_SIDES:  /* Merge (with right) to the left */
1393                 pv->size += size_lp + size_nx;
1394                 unlink_oversize(nx);
1395                 position_oversize_by_size(pv);
1396                 if (debugopt & MTDEBUGPATTERN) {
1397                         copy_pattern(FREEPATTERN, lp, OVSZ_HEADER_SIZE);
1398                         copy_pattern(FREEPATTERN, nx, OVSZ_HEADER_SIZE);
1399                 }
1400                 break;
1401         }
1402 }
1403 
1404 /*
1405  * Find memory on our list that is at least size big. If we find a block that is
1406  * big enough, we break it up and return the associated oversize_t struct back
1407  * to the calling client. Any leftover piece of that block is returned to the
1408  * freelist.
1409  */
1410 static oversize_t *
1411 find_oversize(size_t size)
1412 {
1413         oversize_t *wp = oversize_list.next_bysize;
1414         while (wp != &oversize_list && size > wp->size)
1415                 wp = wp->next_bysize;
1416 
1417         if (wp == &oversize_list) /* empty list or nothing big enough */
1418                 return (NULL);
1419         /* breaking up a chunk of memory */
1420         if ((long)((wp->size - (size + OVSZ_HEADER_SIZE + MTMALLOC_MIN_ALIGN)))
1421             > MAX_CACHED) {
1422                 caddr_t off;
1423                 oversize_t *np;
1424                 size_t osize;
1425                 off = (caddr_t)ALIGN(wp->addr + size,
1426                     MTMALLOC_MIN_ALIGN);
1427                 osize = wp->size;
1428                 wp->size = (size_t)(off - wp->addr);
1429                 np = oversize_header_alloc((uintptr_t)off,
1430                     osize - (wp->size + OVSZ_HEADER_SIZE));
1431                 if ((long)np->size < 0)
1432                         abort();
1433                 unlink_oversize(wp);
1434                 add_oversize(np);
1435         } else {
1436                 unlink_oversize(wp);
1437         }
1438         return (wp);
1439 }
1440 
1441 static void
1442 copy_pattern(uint32_t pattern, void *buf_arg, size_t size)
1443 {
1444         uint32_t *bufend = (uint32_t *)((char *)buf_arg + size);
1445         uint32_t *buf = buf_arg;
1446 
1447         while (buf < bufend - 3) {
1448                 buf[3] = buf[2] = buf[1] = buf[0] = pattern;
1449                 buf += 4;
1450         }
1451         while (buf < bufend)
1452                 *buf++ = pattern;
1453 }
1454 
1455 static void *
1456 verify_pattern(uint32_t pattern, void *buf_arg, size_t size)
1457 {
1458         uint32_t *bufend = (uint32_t *)((char *)buf_arg + size);
1459         uint32_t *buf;
1460 
1461         for (buf = buf_arg; buf < bufend; buf++)
1462                 if (*buf != pattern)
1463                         return (buf);
1464         return (NULL);
1465 }
1466 
1467 static void
1468 free_oversize(oversize_t *ovp)
1469 {
1470         assert(((uintptr_t)ovp->addr & 7) == 0); /* are we 8 byte aligned */
1471         assert(ovp->size > MAX_CACHED);
1472 
1473         ovp->next_bysize = ovp->prev_bysize = NULL;
1474         ovp->next_byaddr = ovp->prev_byaddr = NULL;
1475         (void) mutex_lock(&oversize_lock);
1476         add_oversize(ovp);
1477         (void) mutex_unlock(&oversize_lock);
1478 }
1479 
1480 static oversize_t *
1481 oversize_header_alloc(uintptr_t mem, size_t size)
1482 {
1483         oversize_t *ovsz_hdr;
1484 
1485         assert(size > MAX_CACHED);
1486 
1487         ovsz_hdr = (oversize_t *)mem;
1488         ovsz_hdr->prev_bysize = NULL;
1489         ovsz_hdr->next_bysize = NULL;
1490         ovsz_hdr->prev_byaddr = NULL;
1491         ovsz_hdr->next_byaddr = NULL;
1492         ovsz_hdr->hash_next = NULL;
1493         ovsz_hdr->size = size;
1494         mem += OVSZ_SIZE;
1495         *(uintptr_t *)mem = MTMALLOC_OVERSIZE_MAGIC;
1496         mem += OVERHEAD;
1497         assert(((uintptr_t)mem & 7) == 0); /* are we 8 byte aligned */
1498         ovsz_hdr->addr = (caddr_t)mem;
1499         return (ovsz_hdr);
1500 }
1501 
1502 static void
1503 malloc_prepare()
1504 {
1505         percpu_t *cpuptr;
1506         cache_head_t *cachehead;
1507         cache_t *thiscache;
1508 
1509         (void) mutex_lock(&oversize_lock);
1510         for (cpuptr = &cpu_list[0]; cpuptr < &cpu_list[ncpus]; cpuptr++) {
1511                 (void) mutex_lock(&cpuptr->mt_parent_lock);
1512                 for (cachehead = &cpuptr->mt_caches[0];
1513                     cachehead < &cpuptr->mt_caches[NUM_CACHES];
1514                     cachehead++) {
1515                         for (thiscache = cachehead->mt_cache;
1516                             thiscache != NULL;
1517                             thiscache = thiscache->mt_next) {
1518                                 (void) mutex_lock(
1519                                     &thiscache->mt_cache_lock);
1520                         }
1521                 }
1522         }
1523 }
1524 
1525 static void
1526 malloc_release()
1527 {
1528         percpu_t *cpuptr;
1529         cache_head_t *cachehead;
1530         cache_t *thiscache;
1531 
1532         for (cpuptr = &cpu_list[ncpus - 1]; cpuptr >= &cpu_list[0]; cpuptr--) {
1533                 for (cachehead = &cpuptr->mt_caches[NUM_CACHES - 1];
1534                     cachehead >= &cpuptr->mt_caches[0];
1535                     cachehead--) {
1536                         for (thiscache = cachehead->mt_cache;
1537                             thiscache != NULL;
1538                             thiscache = thiscache->mt_next) {
1539                                 (void) mutex_unlock(
1540                                     &thiscache->mt_cache_lock);
1541                         }
1542                 }
1543                 (void) mutex_unlock(&cpuptr->mt_parent_lock);
1544         }
1545         (void) mutex_unlock(&oversize_lock);
1546 }
1547 
1548 #pragma init(malloc_init)
1549 static void
1550 malloc_init(void)
1551 {
1552         /*
1553          * This works in the init section for this library
1554          * because setup_caches() doesn't call anything in libc
1555          * that calls malloc().  If it did, disaster would ensue.
1556          *
1557          * For this to work properly, this library must be the first
1558          * one to have its init section called (after libc) by the
1559          * dynamic linker.  If some other library's init section
1560          * ran first and called malloc(), disaster would ensue.
1561          * Because this is an interposer library for malloc(), the
1562          * dynamic linker arranges for its init section to run first.
1563          */
1564         (void) setup_caches();
1565 
1566         (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
1567 }