1 /* 2 * DMALLOC.C - Dillon's malloc 3 * 4 * Copyright (c) 2011 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>. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 3. Neither the name of The DragonFly Project nor the names of its 20 * contributors may be used to endorse or promote products derived 21 * from this software without specific, prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 /* 37 * This module implements a modified slab allocator drop-in replacement for 38 * the libc malloc(). The slab algorithm has been adjusted to support dynamic 39 * sizing of slabs which effectively allows slabs to be used for allocations of 40 * any size. Because of this we neither have a small-block allocator or a 41 * big-block allocator and the code paths are simplified to the point where 42 * allocations, caching, and freeing, is screaming fast. 43 * 44 * There is very little interaction between threads. A global depot accessed 45 * via atomic cmpxchg instructions (only! no spinlocks!) is used as a 46 * catch-all and to deal with thread exits and such. 47 * 48 * To support dynamic slab sizing available user virtual memory is broken 49 * down into ~1024 regions. Each region has fixed slab size whos value is 50 * set when the region is opened up for use. The free() path simply applies 51 * a mask based on the region to the pointer to acquire the base of the 52 * governing slab structure. 53 * 54 * Regions[NREGIONS] (1024) 55 * 56 * Slab management and locking is done on a per-zone basis. 57 * 58 * Alloc Size Chunking Number of zones 59 * 0-127 8 16 60 * 128-255 16 8 61 * 256-511 32 8 62 * 512-1023 64 8 63 * 1024-2047 128 8 64 * 2048-4095 256 8 65 * 4096-8191 512 8 66 * 8192-16383 1024 8 67 * 16384-32767 2048 8 68 * 32768-65535 4096 8 69 * ... continues unlimited ... 4 zones 70 * 71 * For a 2^63 memory space each doubling >= 64K is broken down into 72 * 4 chunking zones, so we support 88 + (48 * 4) = 280 zones. 73 * 74 * API FEATURES AND SIDE EFFECTS 75 * 76 * + power-of-2 sized allocations up to a page will be power-of-2 aligned. 77 * Above that power-of-2 sized allocations are page-aligned. Non 78 * power-of-2 sized allocations are aligned the same as the chunk 79 * size for their zone. 80 * + malloc(0) returns a special non-NULL value 81 * + ability to allocate arbitrarily large chunks of memory 82 * + realloc will reuse the passed pointer if possible, within the 83 * limitations of the zone chunking. 84 * 85 * FUTURE FEATURES 86 * 87 * + [better] garbage collection 88 * + better initial sizing. 89 * 90 * TUNING 91 * 92 * The value of the environment variable MALLOC_OPTIONS is a character string 93 * containing various flags to tune nmalloc. Upper case letters enabled 94 * or increase the feature, lower case disables or decreases the feature. 95 * 96 * U Enable UTRACE for all operations, observable with ktrace. 97 * Diasbled by default. 98 * 99 * Z Zero out allocations, otherwise allocations (except for 100 * calloc) will contain garbage. 101 * Disabled by default. 102 * 103 * H Pass a hint with madvise() about unused pages. 104 * Disabled by default. 105 * Not currently implemented. 106 * 107 * F Disable local per-thread caching. 108 * Disabled by default. 109 * 110 * C Increase (decrease) how much excess cache to retain. 111 * Set to 4 by default. 112 */ 113 114 /* cc -shared -fPIC -g -O -I/usr/src/lib/libc/include -o dmalloc.so dmalloc.c */ 115 116 #ifndef STANDALONE_DEBUG 117 #include "libc_private.h" 118 #endif 119 120 #include <sys/param.h> 121 #include <sys/types.h> 122 #include <sys/mman.h> 123 #include <sys/queue.h> 124 #include <sys/uio.h> 125 #include <sys/ktrace.h> 126 #include <stdio.h> 127 #include <stdint.h> 128 #include <stdlib.h> 129 #include <stdarg.h> 130 #include <stddef.h> 131 #include <unistd.h> 132 #include <string.h> 133 #include <fcntl.h> 134 #include <errno.h> 135 #include <pthread.h> 136 #include <limits.h> 137 138 #include <machine/atomic.h> 139 #include <machine/cpufunc.h> 140 141 #ifdef STANDALONE_DEBUG 142 void _nmalloc_thr_init(void); 143 #else 144 #include "spinlock.h" 145 #include "un-namespace.h" 146 #endif 147 148 #ifndef MAP_SIZEALIGN 149 #define MAP_SIZEALIGN 0 150 #endif 151 152 #if SSIZE_MAX == 0x7FFFFFFF 153 #define ADDRBITS 32 154 #define UVM_BITS 32 /* worst case */ 155 #else 156 #define ADDRBITS 64 157 #define UVM_BITS 48 /* worst case XXX */ 158 #endif 159 160 #if LONG_MAX == 0x7FFFFFFF 161 #define LONG_BITS 32 162 #define LONG_BITS_SHIFT 5 163 #else 164 #define LONG_BITS 64 165 #define LONG_BITS_SHIFT 6 166 #endif 167 168 #define LOCKEDPTR ((void *)(intptr_t)-1) 169 170 /* 171 * Regions[] 172 */ 173 #define NREGIONS_BITS 10 174 #define NREGIONS (1 << NREGIONS_BITS) 175 #define NREGIONS_MASK (NREGIONS - 1) 176 #define NREGIONS_SHIFT (UVM_BITS - NREGIONS_BITS) 177 #define NREGIONS_SIZE (1LU << NREGIONS_SHIFT) 178 179 typedef struct region *region_t; 180 typedef struct slglobaldata *slglobaldata_t; 181 typedef struct slab *slab_t; 182 183 struct region { 184 uintptr_t mask; 185 slab_t slab; /* conditional out of band slab */ 186 }; 187 188 static struct region Regions[NREGIONS]; 189 190 /* 191 * Number of chunking zones available 192 */ 193 #define CHUNKFACTOR 8 194 #if ADDRBITS == 32 195 #define NZONES (16 + 9 * CHUNKFACTOR + 16 * CHUNKFACTOR) 196 #else 197 #define NZONES (16 + 9 * CHUNKFACTOR + 48 * CHUNKFACTOR) 198 #endif 199 200 static int MaxChunks[NZONES]; 201 202 #define NDEPOTS 8 /* must be power of 2 */ 203 204 /* 205 * Maximum number of chunks per slab, governed by the allocation bitmap in 206 * each slab. The maximum is reduced for large chunk sizes. 207 */ 208 #define MAXCHUNKS (LONG_BITS * LONG_BITS) 209 #define MAXCHUNKS_BITS (LONG_BITS_SHIFT * LONG_BITS_SHIFT) 210 #define LITSLABSIZE (32 * 1024) 211 #define NOMSLABSIZE (2 * 1024 * 1024) 212 #define BIGSLABSIZE (128 * 1024 * 1024) 213 214 #define ZALLOC_SLAB_MAGIC 0x736c6162 /* magic sanity */ 215 216 TAILQ_HEAD(slab_list, slab); 217 218 /* 219 * A slab structure 220 */ 221 struct slab { 222 struct slab *next; /* slabs with available space */ 223 TAILQ_ENTRY(slab) entry; 224 int32_t magic; /* magic number for sanity check */ 225 u_int navail; /* number of free elements available */ 226 u_int nmax; 227 u_int free_bit; /* free hint bitno */ 228 u_int free_index; /* free hint index */ 229 u_long bitmap[LONG_BITS]; /* free chunks */ 230 size_t slab_size; /* size of entire slab */ 231 size_t chunk_size; /* chunk size for validation */ 232 int zone_index; 233 enum { UNKNOWN, AVAIL, EMPTY, FULL } state; 234 int flags; 235 region_t region; /* related region */ 236 char *chunks; /* chunk base */ 237 slglobaldata_t slgd; 238 }; 239 240 /* 241 * per-thread data 242 */ 243 struct slglobaldata { 244 struct zoneinfo { 245 slab_t avail_base; 246 slab_t empty_base; 247 int best_region; 248 int empty_count; 249 } zone[NZONES]; 250 struct slab_list full_zones; /* via entry */ 251 int masked; 252 int biggest_index; 253 size_t nslabs; 254 slglobaldata_t sldepot; 255 }; 256 257 #define SLAB_ZEROD 0x0001 258 259 /* 260 * Misc constants. Note that allocations that are exact multiples of 261 * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module. 262 * IN_SAME_PAGE_MASK is used to sanity-check the per-page free lists. 263 */ 264 #define MIN_CHUNK_SIZE 8 /* in bytes */ 265 #define MIN_CHUNK_MASK (MIN_CHUNK_SIZE - 1) 266 267 #define SAFLAG_ZERO 0x00000001 268 269 /* 270 * The WEIRD_ADDR is used as known text to copy into free objects to 271 * try to create deterministic failure cases if the data is accessed after 272 * free. 273 * 274 * WARNING: A limited number of spinlocks are available, BIGXSIZE should 275 * not be larger then 64. 276 */ 277 #define WEIRD_ADDR 0xdeadc0de 278 #define MAX_COPY sizeof(weirdary) 279 280 #define arysize(ary) (sizeof(ary)/sizeof((ary)[0])) 281 282 /* 283 * Thread control 284 */ 285 286 #define MASSERT(exp) do { if (__predict_false(!(exp))) \ 287 _mpanic("assertion: %s in %s", \ 288 #exp, __func__); \ 289 } while (0) 290 291 /* With this attribute set, do not require a function call for accessing 292 * this variable when the code is compiled -fPIC */ 293 #define TLS_ATTRIBUTE __attribute__ ((tls_model ("initial-exec"))); 294 295 static __thread struct slglobaldata slglobal TLS_ATTRIBUTE; 296 static pthread_key_t thread_malloc_key; 297 static pthread_once_t thread_malloc_once = PTHREAD_ONCE_INIT; 298 static struct slglobaldata sldepots[NDEPOTS]; 299 300 static int opt_madvise = 0; 301 static int opt_free = 0; 302 static int opt_cache = 4; 303 static int opt_utrace = 0; 304 static int g_malloc_flags = 0; 305 static int malloc_panic; 306 307 static const int32_t weirdary[16] = { 308 WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, 309 WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, 310 WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, 311 WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR, WEIRD_ADDR 312 }; 313 314 static void *memalloc(size_t size, int flags); 315 static void *memrealloc(void *ptr, size_t size); 316 static void memfree(void *ptr, int); 317 static slab_t slaballoc(int zi, size_t chunking, size_t chunk_size); 318 static void slabfree(slab_t slab); 319 static void slabterm(slglobaldata_t slgd, slab_t slab); 320 static void *_vmem_alloc(int ri, size_t slab_size); 321 static void _vmem_free(void *ptr, size_t slab_size); 322 static void _mpanic(const char *ctl, ...) __printflike(1, 2); 323 #ifndef STANDALONE_DEBUG 324 static void malloc_init(void) __constructor(0); 325 #else 326 static void malloc_init(void) __constructor(101); 327 #endif 328 329 struct nmalloc_utrace { 330 void *p; 331 size_t s; 332 void *r; 333 }; 334 335 #define UTRACE(a, b, c) \ 336 if (opt_utrace) { \ 337 struct nmalloc_utrace ut = { \ 338 .p = (a), \ 339 .s = (b), \ 340 .r = (c) \ 341 }; \ 342 utrace(&ut, sizeof(ut)); \ 343 } 344 345 #ifdef INVARIANTS 346 /* 347 * If enabled any memory allocated without M_ZERO is initialized to -1. 348 */ 349 static int use_malloc_pattern; 350 #endif 351 352 static void 353 malloc_init(void) 354 { 355 const char *p = NULL; 356 357 Regions[0].mask = -1; /* disallow activity in lowest region */ 358 359 if (issetugid() == 0) 360 p = getenv("MALLOC_OPTIONS"); 361 362 for (; p != NULL && *p != '\0'; p++) { 363 switch(*p) { 364 case 'u': 365 opt_utrace = 0; 366 break; 367 case 'U': 368 opt_utrace = 1; 369 break; 370 case 'h': 371 opt_madvise = 0; 372 break; 373 case 'H': 374 opt_madvise = 1; 375 break; 376 case 'c': 377 if (opt_cache > 0) 378 --opt_cache; 379 break; 380 case 'C': 381 ++opt_cache; 382 break; 383 case 'f': 384 opt_free = 0; 385 break; 386 case 'F': 387 opt_free = 1; 388 break; 389 case 'z': 390 g_malloc_flags = 0; 391 break; 392 case 'Z': 393 g_malloc_flags = SAFLAG_ZERO; 394 break; 395 default: 396 break; 397 } 398 } 399 400 UTRACE((void *) -1, 0, NULL); 401 _nmalloc_thr_init(); 402 } 403 404 /* 405 * We have to install a handler for nmalloc thread teardowns when 406 * the thread is created. We cannot delay this because destructors in 407 * sophisticated userland programs can call malloc() for the first time 408 * during their thread exit. 409 * 410 * This routine is called directly from pthreads. 411 */ 412 static void _nmalloc_thr_init_once(void); 413 static void _nmalloc_thr_destructor(void *thrp); 414 415 void 416 _nmalloc_thr_init(void) 417 { 418 static int did_init; 419 static int SLGI; 420 int slgi; 421 422 slgi = SLGI++; 423 cpu_ccfence(); 424 TAILQ_INIT(&slglobal.full_zones); 425 slglobal.sldepot = &sldepots[slgi & (NDEPOTS - 1)]; 426 427 slglobal.masked = 1; 428 if (did_init == 0) { 429 did_init = 1; 430 pthread_once(&thread_malloc_once, _nmalloc_thr_init_once); 431 } 432 pthread_setspecific(thread_malloc_key, &slglobal); 433 slglobal.masked = 0; 434 } 435 436 /* 437 * Called just once 438 */ 439 static void 440 _nmalloc_thr_init_once(void) 441 { 442 int error; 443 444 error = pthread_key_create(&thread_malloc_key, _nmalloc_thr_destructor); 445 if (error) 446 abort(); 447 } 448 449 /* 450 * Called for each thread undergoing exit 451 * 452 * Move all of the thread's slabs into a depot. 453 */ 454 static void 455 _nmalloc_thr_destructor(void *thrp) 456 { 457 slglobaldata_t slgd = thrp; 458 slab_t slab; 459 int i; 460 461 slgd->masked = 1; 462 463 for (i = 0; i <= slgd->biggest_index; i++) { 464 while ((slab = slgd->zone[i].empty_base) != NULL) { 465 slgd->zone[i].empty_base = slab->next; 466 slabterm(slgd, slab); 467 } 468 469 while ((slab = slgd->zone[i].avail_base) != NULL) { 470 slgd->zone[i].avail_base = slab->next; 471 slabterm(slgd, slab); 472 } 473 474 while ((slab = TAILQ_FIRST(&slgd->full_zones)) != NULL) { 475 TAILQ_REMOVE(&slgd->full_zones, slab, entry); 476 slabterm(slgd, slab); 477 } 478 } 479 } 480 481 /* 482 * Calculate the zone index for the allocation request size and set the 483 * allocation request size to that particular zone's chunk size. 484 */ 485 static __inline int 486 zoneindex(size_t *bytes, size_t *chunking) 487 { 488 size_t n = (size_t)*bytes; 489 size_t x; 490 size_t c; 491 int i; 492 493 if (n < 128) { 494 *bytes = n = (n + 7) & ~7; 495 *chunking = 8; 496 return(n / 8); /* 8 byte chunks, 16 zones */ 497 } 498 if (n < 4096) { 499 x = 256; 500 c = x / (CHUNKFACTOR * 2); 501 i = 16; 502 } else { 503 x = 8192; 504 c = x / (CHUNKFACTOR * 2); 505 i = 16 + CHUNKFACTOR * 5; /* 256->512,1024,2048,4096,8192 */ 506 } 507 while (n >= x) { 508 x <<= 1; 509 c <<= 1; 510 i += CHUNKFACTOR; 511 if (x == 0) 512 _mpanic("slaballoc: byte value too high"); 513 } 514 *bytes = n = (n + c - 1) & ~(c - 1); 515 *chunking = c; 516 return (i + n / c - CHUNKFACTOR); 517 #if 0 518 *bytes = n = (n + c - 1) & ~(c - 1); 519 *chunking = c; 520 return (n / c + i); 521 522 if (n < 256) { 523 *bytes = n = (n + 15) & ~15; 524 *chunking = 16; 525 return(n / (CHUNKINGLO*2) + CHUNKINGLO*1 - 1); 526 } 527 if (n < 8192) { 528 if (n < 512) { 529 *bytes = n = (n + 31) & ~31; 530 *chunking = 32; 531 return(n / (CHUNKINGLO*4) + CHUNKINGLO*2 - 1); 532 } 533 if (n < 1024) { 534 *bytes = n = (n + 63) & ~63; 535 *chunking = 64; 536 return(n / (CHUNKINGLO*8) + CHUNKINGLO*3 - 1); 537 } 538 if (n < 2048) { 539 *bytes = n = (n + 127) & ~127; 540 *chunking = 128; 541 return(n / (CHUNKINGLO*16) + CHUNKINGLO*4 - 1); 542 } 543 if (n < 4096) { 544 *bytes = n = (n + 255) & ~255; 545 *chunking = 256; 546 return(n / (CHUNKINGLO*32) + CHUNKINGLO*5 - 1); 547 } 548 *bytes = n = (n + 511) & ~511; 549 *chunking = 512; 550 return(n / (CHUNKINGLO*64) + CHUNKINGLO*6 - 1); 551 } 552 if (n < 16384) { 553 *bytes = n = (n + 1023) & ~1023; 554 *chunking = 1024; 555 return(n / (CHUNKINGLO*128) + CHUNKINGLO*7 - 1); 556 } 557 if (n < 32768) { /* 16384-32767 */ 558 *bytes = n = (n + 2047) & ~2047; 559 *chunking = 2048; 560 return(n / (CHUNKINGLO*256) + CHUNKINGLO*8 - 1); 561 } 562 if (n < 65536) { 563 *bytes = n = (n + 4095) & ~4095; /* 32768-65535 */ 564 *chunking = 4096; 565 return(n / (CHUNKINGLO*512) + CHUNKINGLO*9 - 1); 566 } 567 568 x = 131072; 569 c = 8192; 570 i = CHUNKINGLO*10 - 1; 571 572 while (n >= x) { 573 x <<= 1; 574 c <<= 1; 575 i += CHUNKINGHI; 576 if (x == 0) 577 _mpanic("slaballoc: byte value too high"); 578 } 579 *bytes = n = (n + c - 1) & ~(c - 1); 580 *chunking = c; 581 return (n / c + i); 582 #endif 583 } 584 585 /* 586 * malloc() - call internal slab allocator 587 */ 588 void * 589 malloc(size_t size) 590 { 591 void *ptr; 592 593 ptr = memalloc(size, 0); 594 if (ptr == NULL) 595 errno = ENOMEM; 596 else 597 UTRACE(0, size, ptr); 598 return(ptr); 599 } 600 601 /* 602 * calloc() - call internal slab allocator 603 */ 604 void * 605 calloc(size_t number, size_t size) 606 { 607 void *ptr; 608 609 ptr = memalloc(number * size, SAFLAG_ZERO); 610 if (ptr == NULL) 611 errno = ENOMEM; 612 else 613 UTRACE(0, number * size, ptr); 614 return(ptr); 615 } 616 617 /* 618 * realloc() (SLAB ALLOCATOR) 619 * 620 * We do not attempt to optimize this routine beyond reusing the same 621 * pointer if the new size fits within the chunking of the old pointer's 622 * zone. 623 */ 624 void * 625 realloc(void *ptr, size_t size) 626 { 627 void *ret; 628 629 if (ptr == NULL) 630 ret = memalloc(size, 0); 631 else 632 ret = memrealloc(ptr, size); 633 if (ret == NULL) 634 errno = ENOMEM; 635 else 636 UTRACE(ptr, size, ret); 637 return(ret); 638 } 639 640 /* 641 * posix_memalign() 642 * 643 * Allocate (size) bytes with a alignment of (alignment), where (alignment) 644 * is a power of 2 >= sizeof(void *). 645 * 646 * The slab allocator will allocate on power-of-2 boundaries up to at least 647 * PAGE_SIZE. Otherwise we use the zoneindex mechanic to find a zone 648 * matching the requirements. 649 */ 650 int 651 posix_memalign(void **memptr, size_t alignment, size_t size) 652 { 653 size_t chunking; 654 int zi; 655 656 /* 657 * OpenGroup spec issue 6 checks 658 */ 659 if ((alignment | (alignment - 1)) + 1 != (alignment << 1)) { 660 *memptr = NULL; 661 return(EINVAL); 662 } 663 if (alignment < sizeof(void *)) { 664 *memptr = NULL; 665 return(EINVAL); 666 } 667 668 /* 669 * XXX for now just find the nearest power of 2 >= size and also 670 * >= alignment and allocate that. 671 */ 672 while (alignment < size) { 673 alignment <<= 1; 674 if (alignment == 0) 675 _mpanic("posix_memalign: byte value too high"); 676 } 677 *memptr = memalloc(alignment, 0); 678 return(*memptr ? 0 : ENOMEM); 679 } 680 681 /* 682 * free() (SLAB ALLOCATOR) - do the obvious 683 */ 684 void 685 free(void *ptr) 686 { 687 if (ptr) { 688 UTRACE(ptr, 0, 0); 689 memfree(ptr, 0); 690 } 691 } 692 693 /* 694 * memalloc() (SLAB ALLOCATOR) 695 * 696 * Allocate memory via the slab allocator. 697 */ 698 static void * 699 memalloc(size_t size, int flags) 700 { 701 slglobaldata_t slgd; 702 struct zoneinfo *zinfo; 703 slab_t slab; 704 size_t chunking; 705 int bmi; 706 int bno; 707 u_long *bmp; 708 int zi; 709 #ifdef INVARIANTS 710 int i; 711 #endif 712 size_t off; 713 char *obj; 714 715 /* 716 * If 0 bytes is requested we have to return a unique pointer, allocate 717 * at least one byte. 718 */ 719 if (size == 0) 720 size = 1; 721 722 /* Capture global flags */ 723 flags |= g_malloc_flags; 724 725 /* Compute allocation zone; zoneindex will panic on excessive sizes */ 726 zi = zoneindex(&size, &chunking); 727 MASSERT(zi < NZONES); 728 if (size == 0) 729 return(NULL); 730 731 /* 732 * Locate a slab with available space. If no slabs are available 733 * back-off to the empty list and if we still come up dry allocate 734 * a new slab (which will try the depot first). 735 */ 736 retry: 737 slgd = &slglobal; 738 zinfo = &slgd->zone[zi]; 739 if ((slab = zinfo->avail_base) == NULL) { 740 if ((slab = zinfo->empty_base) == NULL) { 741 /* 742 * Still dry 743 */ 744 slab = slaballoc(zi, chunking, size); 745 if (slab == NULL) 746 return(NULL); 747 slab->next = zinfo->avail_base; 748 zinfo->avail_base = slab; 749 slab->state = AVAIL; 750 if (slgd->biggest_index < zi) 751 slgd->biggest_index = zi; 752 ++slgd->nslabs; 753 } else { 754 /* 755 * Pulled from empty list 756 */ 757 zinfo->empty_base = slab->next; 758 slab->next = zinfo->avail_base; 759 zinfo->avail_base = slab; 760 slab->state = AVAIL; 761 --zinfo->empty_count; 762 } 763 } 764 765 /* 766 * Allocate a chunk out of the slab. HOT PATH 767 * 768 * Only the thread owning the slab can allocate out of it. 769 * 770 * NOTE: The last bit in the bitmap is always marked allocated so 771 * we cannot overflow here. 772 */ 773 bno = slab->free_bit; 774 bmi = slab->free_index; 775 bmp = &slab->bitmap[bmi]; 776 if (*bmp & (1LU << bno)) { 777 atomic_clear_long(bmp, 1LU << bno); 778 obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) * size; 779 slab->free_bit = (bno + 1) & (LONG_BITS - 1); 780 atomic_add_int(&slab->navail, -1); 781 if (flags & SAFLAG_ZERO) 782 bzero(obj, size); 783 return (obj); 784 } 785 786 /* 787 * Allocate a chunk out of a slab. COLD PATH 788 */ 789 if (slab->navail == 0) { 790 zinfo->avail_base = slab->next; 791 slab->state = FULL; 792 TAILQ_INSERT_TAIL(&slgd->full_zones, slab, entry); 793 goto retry; 794 } 795 796 while (bmi < LONG_BITS) { 797 bmp = &slab->bitmap[bmi]; 798 if (*bmp) { 799 bno = bsflong(*bmp); 800 atomic_clear_long(bmp, 1LU << bno); 801 obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) * 802 size; 803 slab->free_index = bmi; 804 slab->free_bit = (bno + 1) & (LONG_BITS - 1); 805 atomic_add_int(&slab->navail, -1); 806 if (flags & SAFLAG_ZERO) 807 bzero(obj, size); 808 return (obj); 809 } 810 ++bmi; 811 } 812 bmi = 0; 813 while (bmi < LONG_BITS) { 814 bmp = &slab->bitmap[bmi]; 815 if (*bmp) { 816 bno = bsflong(*bmp); 817 atomic_clear_long(bmp, 1LU << bno); 818 obj = slab->chunks + ((bmi << LONG_BITS_SHIFT) + bno) * 819 size; 820 slab->free_index = bmi; 821 slab->free_bit = (bno + 1) & (LONG_BITS - 1); 822 atomic_add_int(&slab->navail, -1); 823 if (flags & SAFLAG_ZERO) 824 bzero(obj, size); 825 return (obj); 826 } 827 ++bmi; 828 } 829 _mpanic("slaballoc: corrupted zone: navail %d", slab->navail); 830 /* not reached */ 831 return NULL; 832 } 833 834 /* 835 * Reallocate memory within the chunk 836 */ 837 static void * 838 memrealloc(void *ptr, size_t nsize) 839 { 840 region_t region; 841 slglobaldata_t slgd; 842 slab_t slab; 843 size_t osize; 844 char *obj; 845 int flags; 846 847 /* 848 * If 0 bytes is requested we have to return a unique pointer, allocate 849 * at least one byte. 850 */ 851 if (nsize == 0) 852 nsize = 1; 853 854 /* Capture global flags */ 855 flags |= g_malloc_flags; 856 857 /* 858 * Locate the zone by looking up the dynamic slab size mask based 859 * on the memory region the allocation resides in. 860 */ 861 region = &Regions[((uintptr_t)ptr >> NREGIONS_SHIFT) & NREGIONS_MASK]; 862 if ((slab = region->slab) == NULL) 863 slab = (void *)((uintptr_t)ptr & region->mask); 864 MASSERT(slab->magic == ZALLOC_SLAB_MAGIC); 865 osize = slab->chunk_size; 866 if (nsize <= osize) { 867 if (osize < 32 || nsize >= osize / 2) { 868 obj = ptr; 869 if ((flags & SAFLAG_ZERO) && nsize < osize) 870 bzero(obj + nsize, osize - nsize); 871 return(obj); 872 } 873 } 874 875 /* 876 * Otherwise resize the object 877 */ 878 obj = memalloc(nsize, 0); 879 if (obj) { 880 if (nsize > osize) 881 nsize = osize; 882 bcopy(ptr, obj, nsize); 883 memfree(ptr, 0); 884 } 885 return (obj); 886 } 887 888 /* 889 * free (SLAB ALLOCATOR) 890 * 891 * Free a memory block previously allocated by malloc. 892 * 893 * MPSAFE 894 */ 895 static void 896 memfree(void *ptr, int flags) 897 { 898 region_t region; 899 slglobaldata_t slgd; 900 slab_t slab; 901 slab_t stmp; 902 slab_t *slabp; 903 char *obj; 904 int bmi; 905 int bno; 906 u_long *bmp; 907 908 /* 909 * Locate the zone by looking up the dynamic slab size mask based 910 * on the memory region the allocation resides in. 911 * 912 * WARNING! The slab may be owned by another thread! 913 */ 914 region = &Regions[((uintptr_t)ptr >> NREGIONS_SHIFT) & NREGIONS_MASK]; 915 if ((slab = region->slab) == NULL) 916 slab = (void *)((uintptr_t)ptr & region->mask); 917 MASSERT(slab != NULL); 918 MASSERT(slab->magic == ZALLOC_SLAB_MAGIC); 919 920 #ifdef INVARIANTS 921 /* 922 * Put weird data into the memory to detect modifications after 923 * freeing, illegal pointer use after freeing (we should fault on 924 * the odd address), and so forth. 925 */ 926 if (slab->chunk_size < sizeof(weirdary)) 927 bcopy(weirdary, ptr, slab->chunk_size); 928 else 929 bcopy(weirdary, ptr, sizeof(weirdary)); 930 #endif 931 932 bno = ((uintptr_t)ptr - (uintptr_t)slab->chunks) / slab->chunk_size; 933 bmi = bno >> LONG_BITS_SHIFT; 934 bno &= (LONG_BITS - 1); 935 bmp = &slab->bitmap[bmi]; 936 937 MASSERT(bmi >= 0 && bmi < slab->nmax); 938 MASSERT((*bmp & (1LU << bno)) == 0); 939 atomic_set_long(bmp, 1LU << bno); 940 atomic_add_int(&slab->navail, 1); 941 942 /* 943 * We can only do the following if we own the slab 944 */ 945 slgd = &slglobal; 946 if (slab->slgd == slgd) { 947 struct zoneinfo *zinfo; 948 949 if (slab->free_index > bmi) { 950 slab->free_index = bmi; 951 slab->free_bit = bno; 952 } else if (slab->free_index == bmi && 953 slab->free_bit > bno) { 954 slab->free_bit = bno; 955 } 956 zinfo = &slgd->zone[slab->zone_index]; 957 958 /* 959 * Freeing an object from a full slab will move it to the 960 * available list. If the available list already has a 961 * slab we terminate the full slab instead, moving it to 962 * the depot. 963 */ 964 if (slab->state == FULL) { 965 TAILQ_REMOVE(&slgd->full_zones, slab, entry); 966 if (zinfo->avail_base == NULL) { 967 slab->state = AVAIL; 968 stmp = zinfo->avail_base; 969 slab->next = stmp; 970 zinfo->avail_base = slab; 971 } else { 972 slabterm(slgd, slab); 973 goto done; 974 } 975 } 976 977 /* 978 * If the slab becomes completely empty dispose of it in 979 * some manner. By default each thread caches up to 4 980 * empty slabs. Only small slabs are cached. 981 */ 982 if (slab->navail == slab->nmax && slab->state == AVAIL) { 983 /* 984 * Remove slab from available queue 985 */ 986 slabp = &zinfo->avail_base; 987 while ((stmp = *slabp) != slab) 988 slabp = &stmp->next; 989 *slabp = slab->next; 990 991 if (opt_free || opt_cache == 0) { 992 /* 993 * If local caching is disabled cache the 994 * slab in the depot (or free it). 995 */ 996 slabterm(slgd, slab); 997 } else if (slab->slab_size > BIGSLABSIZE) { 998 /* 999 * We do not try to retain large slabs 1000 * in per-thread caches. 1001 */ 1002 slabterm(slgd, slab); 1003 } else if (zinfo->empty_count > opt_cache) { 1004 /* 1005 * We have too many slabs cached, but 1006 * instead of freeing this one free 1007 * an empty slab that's been idle longer. 1008 * 1009 * (empty_count does not change) 1010 */ 1011 stmp = zinfo->empty_base; 1012 slab->state = EMPTY; 1013 slab->next = stmp->next; 1014 zinfo->empty_base = slab; 1015 slabterm(slgd, stmp); 1016 } else { 1017 /* 1018 * Cache the empty slab in our thread local 1019 * empty list. 1020 */ 1021 ++zinfo->empty_count; 1022 slab->state = EMPTY; 1023 slab->next = zinfo->empty_base; 1024 zinfo->empty_base = slab; 1025 } 1026 } 1027 } 1028 done: 1029 ; 1030 } 1031 1032 /* 1033 * Allocate a new slab holding objects of size chunk_size. 1034 */ 1035 static slab_t 1036 slaballoc(int zi, size_t chunking, size_t chunk_size) 1037 { 1038 slglobaldata_t slgd; 1039 slglobaldata_t sldepot; 1040 struct zoneinfo *zinfo; 1041 region_t region; 1042 void *save; 1043 slab_t slab; 1044 slab_t stmp; 1045 size_t slab_desire; 1046 size_t slab_size; 1047 size_t region_mask; 1048 uintptr_t chunk_offset; 1049 ssize_t maxchunks; 1050 ssize_t tmpchunks; 1051 int ispower2; 1052 int power; 1053 int ri; 1054 int rx; 1055 int nswath; 1056 int j; 1057 1058 /* 1059 * First look in the depot. Any given zone in the depot may be 1060 * locked by being set to -1. We have to do this instead of simply 1061 * removing the entire chain because removing the entire chain can 1062 * cause racing threads to allocate local slabs for large objects, 1063 * resulting in a large VSZ. 1064 */ 1065 slgd = &slglobal; 1066 sldepot = slgd->sldepot; 1067 zinfo = &sldepot->zone[zi]; 1068 1069 while ((slab = zinfo->avail_base) != NULL) { 1070 if ((void *)slab == LOCKEDPTR) { 1071 cpu_pause(); 1072 continue; 1073 } 1074 if (atomic_cmpset_ptr(&zinfo->avail_base, slab, LOCKEDPTR)) { 1075 MASSERT(slab->slgd == NULL); 1076 slab->slgd = slgd; 1077 zinfo->avail_base = slab->next; 1078 return(slab); 1079 } 1080 } 1081 1082 /* 1083 * Nothing in the depot, allocate a new slab by locating or assigning 1084 * a region and then using the system virtual memory allocator. 1085 */ 1086 slab = NULL; 1087 1088 /* 1089 * Calculate the start of the data chunks relative to the start 1090 * of the slab. 1091 */ 1092 if ((chunk_size ^ (chunk_size - 1)) == (chunk_size << 1) - 1) { 1093 ispower2 = 1; 1094 chunk_offset = (sizeof(*slab) + (chunk_size - 1)) & 1095 ~(chunk_size - 1); 1096 } else { 1097 ispower2 = 0; 1098 chunk_offset = sizeof(*slab) + chunking - 1; 1099 chunk_offset -= chunk_offset % chunking; 1100 } 1101 1102 /* 1103 * Calculate a reasonable number of chunks for the slab. 1104 * 1105 * Once initialized the MaxChunks[] array can only ever be 1106 * reinitialized to the same value. 1107 */ 1108 maxchunks = MaxChunks[zi]; 1109 if (maxchunks == 0) { 1110 /* 1111 * First calculate how many chunks would fit in 1/1024 1112 * available memory. This is around 2MB on a 32 bit 1113 * system and 128G on a 64-bit (48-bits available) system. 1114 */ 1115 maxchunks = (ssize_t)(NREGIONS_SIZE - chunk_offset) / 1116 (ssize_t)chunk_size; 1117 if (maxchunks <= 0) 1118 maxchunks = 1; 1119 1120 /* 1121 * A slab cannot handle more than MAXCHUNKS chunks, but 1122 * limit us to approximately MAXCHUNKS / 2 here because 1123 * we may have to expand maxchunks when we calculate the 1124 * actual power-of-2 slab. 1125 */ 1126 if (maxchunks > MAXCHUNKS / 2) 1127 maxchunks = MAXCHUNKS / 2; 1128 1129 /* 1130 * Try to limit the slabs to BIGSLABSIZE (~128MB). Larger 1131 * slabs will be created if the allocation does not fit. 1132 */ 1133 if (chunk_offset + chunk_size * maxchunks > BIGSLABSIZE) { 1134 tmpchunks = (ssize_t)(BIGSLABSIZE - chunk_offset) / 1135 (ssize_t)chunk_size; 1136 if (tmpchunks <= 0) 1137 tmpchunks = 1; 1138 if (maxchunks > tmpchunks) 1139 maxchunks = tmpchunks; 1140 } 1141 1142 /* 1143 * If the slab calculates to greater than 2MB see if we 1144 * can cut it down to ~2MB. This controls VSZ but has 1145 * no effect on run-time size or performance. 1146 * 1147 * This is very important in case you core dump and also 1148 * important to reduce unnecessary region allocations. 1149 */ 1150 if (chunk_offset + chunk_size * maxchunks > NOMSLABSIZE) { 1151 tmpchunks = (ssize_t)(NOMSLABSIZE - chunk_offset) / 1152 (ssize_t)chunk_size; 1153 if (tmpchunks < 1) 1154 tmpchunks = 1; 1155 if (maxchunks > tmpchunks) 1156 maxchunks = tmpchunks; 1157 } 1158 1159 /* 1160 * If the slab calculates to greater than 128K see if we 1161 * can cut it down to ~128K while still maintaining a 1162 * reasonably large number of chunks in each slab. This 1163 * controls VSZ but has no effect on run-time size or 1164 * performance. 1165 * 1166 * This is very important in case you core dump and also 1167 * important to reduce unnecessary region allocations. 1168 */ 1169 if (chunk_offset + chunk_size * maxchunks > LITSLABSIZE) { 1170 tmpchunks = (ssize_t)(LITSLABSIZE - chunk_offset) / 1171 (ssize_t)chunk_size; 1172 if (tmpchunks < 32) 1173 tmpchunks = 32; 1174 if (maxchunks > tmpchunks) 1175 maxchunks = tmpchunks; 1176 } 1177 1178 MaxChunks[zi] = maxchunks; 1179 } 1180 MASSERT(maxchunks > 0 && maxchunks <= MAXCHUNKS); 1181 1182 /* 1183 * Calculate the actual slab size. maxchunks will be recalculated 1184 * a little later. 1185 */ 1186 slab_desire = chunk_offset + chunk_size * maxchunks; 1187 slab_size = 8 * MAXCHUNKS; 1188 power = 3 + MAXCHUNKS_BITS; 1189 while (slab_size < slab_desire) { 1190 slab_size <<= 1; 1191 ++power; 1192 } 1193 1194 /* 1195 * Do a quick recalculation based on the actual slab size but not 1196 * yet dealing with whether the slab header is in-band or out-of-band. 1197 * The purpose here is to see if we can reasonably reduce slab_size 1198 * to a power of 4 to allow more chunk sizes to use the same slab 1199 * size. 1200 */ 1201 if ((power & 1) && slab_size > 32768) { 1202 maxchunks = (slab_size - chunk_offset) / chunk_size; 1203 if (maxchunks >= MAXCHUNKS / 8) { 1204 slab_size >>= 1; 1205 --power; 1206 } 1207 } 1208 if ((power & 2) && slab_size > 32768 * 4) { 1209 maxchunks = (slab_size - chunk_offset) / chunk_size; 1210 if (maxchunks >= MAXCHUNKS / 4) { 1211 slab_size >>= 2; 1212 power -= 2; 1213 } 1214 } 1215 /* 1216 * This case occurs when the slab_size is larger than 1/1024 available 1217 * UVM. 1218 */ 1219 nswath = slab_size / NREGIONS_SIZE; 1220 if (nswath > NREGIONS) 1221 return (NULL); 1222 1223 1224 /* 1225 * Try to allocate from our current best region for this zi 1226 */ 1227 region_mask = ~(slab_size - 1); 1228 ri = slgd->zone[zi].best_region; 1229 if (Regions[ri].mask == region_mask) { 1230 if ((slab = _vmem_alloc(ri, slab_size)) != NULL) 1231 goto found; 1232 } 1233 1234 /* 1235 * Try to find an existing region to allocate from. The normal 1236 * case will be for allocations that are less than 1/1024 available 1237 * UVM, which fit into a single Regions[] entry. 1238 */ 1239 while (slab_size <= NREGIONS_SIZE) { 1240 rx = -1; 1241 for (ri = 0; ri < NREGIONS; ++ri) { 1242 if (rx < 0 && Regions[ri].mask == 0) 1243 rx = ri; 1244 if (Regions[ri].mask == region_mask) { 1245 slab = _vmem_alloc(ri, slab_size); 1246 if (slab) { 1247 slgd->zone[zi].best_region = ri; 1248 goto found; 1249 } 1250 } 1251 } 1252 1253 if (rx < 0) 1254 return(NULL); 1255 1256 /* 1257 * This can fail, retry either way 1258 */ 1259 atomic_cmpset_ptr((void **)&Regions[rx].mask, 1260 NULL, 1261 (void *)region_mask); 1262 } 1263 1264 for (;;) { 1265 rx = -1; 1266 for (ri = 0; ri < NREGIONS; ri += nswath) { 1267 if (Regions[ri].mask == region_mask) { 1268 slab = _vmem_alloc(ri, slab_size); 1269 if (slab) { 1270 slgd->zone[zi].best_region = ri; 1271 goto found; 1272 } 1273 } 1274 if (rx < 0) { 1275 for (j = nswath - 1; j >= 0; --j) { 1276 if (Regions[ri+j].mask != 0) 1277 break; 1278 } 1279 if (j < 0) 1280 rx = ri; 1281 } 1282 } 1283 1284 /* 1285 * We found a candidate, try to allocate it backwards so 1286 * another thread racing a slaballoc() does not see the 1287 * mask in the base index position until we are done. 1288 * 1289 * We can safely zero-out any partial allocations because 1290 * the mask is only accessed from the base index. Any other 1291 * threads racing us will fail prior to us clearing the mask. 1292 */ 1293 if (rx < 0) 1294 return(NULL); 1295 for (j = nswath - 1; j >= 0; --j) { 1296 if (!atomic_cmpset_ptr((void **)&Regions[rx+j].mask, 1297 NULL, (void *)region_mask)) { 1298 while (++j < nswath) 1299 Regions[rx+j].mask = 0; 1300 break; 1301 } 1302 } 1303 /* retry */ 1304 } 1305 1306 /* 1307 * Fill in the new slab in region ri. If the slab_size completely 1308 * fills one or more region slots we move the slab structure out of 1309 * band which should optimize the chunking (particularly for a power 1310 * of 2). 1311 */ 1312 found: 1313 region = &Regions[ri]; 1314 MASSERT(region->slab == NULL); 1315 if (slab_size >= NREGIONS_SIZE) { 1316 save = slab; 1317 slab = memalloc(sizeof(*slab), 0); 1318 bzero(slab, sizeof(*slab)); 1319 slab->chunks = save; 1320 for (j = 0; j < nswath; ++j) 1321 region[j].slab = slab; 1322 chunk_offset = 0; 1323 } else { 1324 bzero(slab, sizeof(*slab)); 1325 slab->chunks = (char *)slab + chunk_offset; 1326 } 1327 1328 /* 1329 * Calculate the start of the chunks memory and recalculate the 1330 * actual number of chunks the slab can hold. 1331 */ 1332 maxchunks = (slab_size - chunk_offset) / chunk_size; 1333 if (maxchunks > MAXCHUNKS) 1334 maxchunks = MAXCHUNKS; 1335 1336 /* 1337 * And fill in the rest 1338 */ 1339 slab->magic = ZALLOC_SLAB_MAGIC; 1340 slab->navail = maxchunks; 1341 slab->nmax = maxchunks; 1342 slab->slab_size = slab_size; 1343 slab->chunk_size = chunk_size; 1344 slab->zone_index = zi; 1345 slab->slgd = slgd; 1346 slab->state = UNKNOWN; 1347 slab->region = region; 1348 1349 for (ri = 0; ri < maxchunks; ri += LONG_BITS) { 1350 if (ri + LONG_BITS <= maxchunks) 1351 slab->bitmap[ri >> LONG_BITS_SHIFT] = ULONG_MAX; 1352 else 1353 slab->bitmap[ri >> LONG_BITS_SHIFT] = 1354 (1LU << (maxchunks - ri)) - 1; 1355 } 1356 return (slab); 1357 } 1358 1359 /* 1360 * Free a slab. 1361 */ 1362 static void 1363 slabfree(slab_t slab) 1364 { 1365 int nswath; 1366 int j; 1367 1368 if (slab->region->slab == slab) { 1369 /* 1370 * Out-of-band slab. 1371 */ 1372 nswath = slab->slab_size / NREGIONS_SIZE; 1373 for (j = 0; j < nswath; ++j) 1374 slab->region[j].slab = NULL; 1375 slab->magic = 0; 1376 _vmem_free(slab->chunks, slab->slab_size); 1377 memfree(slab, 0); 1378 } else { 1379 /* 1380 * In-band slab. 1381 */ 1382 slab->magic = 0; 1383 _vmem_free(slab, slab->slab_size); 1384 } 1385 } 1386 1387 /* 1388 * Terminate a slab's use in the current thread. The slab may still have 1389 * outstanding allocations and thus not be deallocatable. 1390 */ 1391 static void 1392 slabterm(slglobaldata_t slgd, slab_t slab) 1393 { 1394 slglobaldata_t sldepot = slgd->sldepot; 1395 struct zoneinfo *zinfo; 1396 slab_t dnext; 1397 int zi = slab->zone_index; 1398 1399 slab->slgd = NULL; 1400 --slgd->nslabs; 1401 zinfo = &sldepot->zone[zi]; 1402 1403 /* 1404 * If the slab can be freed and the depot is either locked or not 1405 * empty, then free the slab. 1406 */ 1407 if (slab->navail == slab->nmax && zinfo->avail_base) { 1408 slab->state = UNKNOWN; 1409 slabfree(slab); 1410 return; 1411 } 1412 slab->state = AVAIL; 1413 1414 /* 1415 * Link the slab into the depot 1416 */ 1417 for (;;) { 1418 dnext = zinfo->avail_base; 1419 cpu_ccfence(); 1420 if ((void *)dnext == LOCKEDPTR) { 1421 cpu_pause(); 1422 continue; 1423 } 1424 slab->next = dnext; 1425 if (atomic_cmpset_ptr(&zinfo->avail_base, dnext, slab)) 1426 break; 1427 } 1428 } 1429 1430 /* 1431 * _vmem_alloc() 1432 * 1433 * Directly map memory in PAGE_SIZE'd chunks with the specified 1434 * alignment. 1435 * 1436 * Alignment must be a multiple of PAGE_SIZE. 1437 * 1438 * Size must be >= alignment. 1439 */ 1440 static void * 1441 _vmem_alloc(int ri, size_t slab_size) 1442 { 1443 char *baddr = (void *)((uintptr_t)ri << NREGIONS_SHIFT); 1444 char *eaddr; 1445 char *addr; 1446 char *save; 1447 uintptr_t excess; 1448 1449 if (slab_size < NREGIONS_SIZE) 1450 eaddr = baddr + NREGIONS_SIZE; 1451 else 1452 eaddr = baddr + slab_size; 1453 1454 /* 1455 * This usually just works but might not. 1456 */ 1457 addr = mmap(baddr, slab_size, PROT_READ|PROT_WRITE, 1458 MAP_PRIVATE | MAP_ANON | MAP_SIZEALIGN, -1, 0); 1459 if (addr == MAP_FAILED) { 1460 return (NULL); 1461 } 1462 if (addr < baddr || addr + slab_size > eaddr) { 1463 munmap(addr, slab_size); 1464 return (NULL); 1465 } 1466 1467 /* 1468 * Check alignment. The misaligned offset is also the excess 1469 * amount. If misaligned unmap the excess so we have a chance of 1470 * mapping at the next alignment point and recursively try again. 1471 * 1472 * BBBBBBBBBBB BBBBBBBBBBB BBBBBBBBBBB block alignment 1473 * aaaaaaaaa aaaaaaaaaaa aa mis-aligned allocation 1474 * xxxxxxxxx final excess calculation 1475 * ^ returned address 1476 */ 1477 excess = (uintptr_t)addr & (slab_size - 1); 1478 while (excess) { 1479 excess = slab_size - excess; 1480 save = addr; 1481 1482 munmap(save + excess, slab_size - excess); 1483 addr = _vmem_alloc(ri, slab_size); 1484 munmap(save, excess); 1485 if (addr == NULL) 1486 return (NULL); 1487 if (addr < baddr || addr + slab_size > eaddr) { 1488 munmap(addr, slab_size); 1489 return (NULL); 1490 } 1491 excess = (uintptr_t)addr & (slab_size - 1); 1492 } 1493 return (addr); 1494 } 1495 1496 /* 1497 * _vmem_free() 1498 * 1499 * Free a chunk of memory allocated with _vmem_alloc() 1500 */ 1501 static void 1502 _vmem_free(void *ptr, size_t size) 1503 { 1504 munmap(ptr, size); 1505 } 1506 1507 /* 1508 * Panic on fatal conditions 1509 */ 1510 static void 1511 _mpanic(const char *ctl, ...) 1512 { 1513 va_list va; 1514 1515 if (malloc_panic == 0) { 1516 malloc_panic = 1; 1517 va_start(va, ctl); 1518 vfprintf(stderr, ctl, va); 1519 fprintf(stderr, "\n"); 1520 fflush(stderr); 1521 va_end(va); 1522 } 1523 abort(); 1524 } 1525