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