1/* $OpenBSD: malloc.c,v 1.35 2022/01/18 21:59:29 deraadt Exp $ */ 2/* 3 * Copyright (c) 2008, 2010, 2011 Otto Moerbeek <otto@drijf.net> 4 * Copyright (c) 2012 Matthew Dempsky <matthew@openbsd.org> 5 * Copyright (c) 2008 Damien Miller <djm@openbsd.org> 6 * Copyright (c) 2000 Poul-Henning Kamp <phk@FreeBSD.org> 7 * 8 * Permission to use, copy, modify, and distribute this software for any 9 * purpose with or without fee is hereby granted, provided that the above 10 * copyright notice and this permission notice appear in all copies. 11 * 12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 19 */ 20 21/* 22 * If we meet some day, and you think this stuff is worth it, you 23 * can buy me a beer in return. Poul-Henning Kamp 24 */ 25 26#include <sys/types.h> 27#include <sys/queue.h> 28#include <sys/time.h> 29#include <sys/mman.h> 30#include <stdint.h> 31 32#include "syscall.h" 33#include "util.h" 34#include "resolve.h" /* for lock_cb */ 35 36#define MALLOC_PAGESHIFT _MAX_PAGE_SHIFT 37#define MALLOC_MINSHIFT 4 38#define MALLOC_MAXSHIFT (MALLOC_PAGESHIFT - 1) 39#define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT) 40#define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT) 41#define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1) 42#define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK)) 43 44#define MALLOC_MAXCHUNK (1 << MALLOC_MAXSHIFT) 45#define MALLOC_MAXCACHE 256 46#define MALLOC_DELAYED_CHUNK_MASK 15 47#define MALLOC_INITIAL_REGIONS (MALLOC_PAGESIZE / sizeof(struct region_info)) 48#define MALLOC_DEFAULT_CACHE 64 49#define MALLOC_CHUNK_LISTS 4 50#define CHUNK_CHECK_LENGTH 32 51 52/* 53 * We move allocations between half a page and a whole page towards the end, 54 * subject to alignment constraints. This is the extra headroom we allow. 55 * Set to zero to be the most strict. 56 */ 57#define MALLOC_LEEWAY 0 58 59#define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK) 60 61/* 62 * What to use for Junk. This is the byte value we use to fill with 63 * when the 'J' option is enabled. Use SOME_JUNK right after alloc, 64 * and SOME_FREEJUNK right before free. 65 */ 66#define SOME_JUNK 0xdb /* deadbeef */ 67#define SOME_FREEJUNK 0xdf /* dead, free */ 68 69#define MMAP(sz) _dl_mmap(NULL, (size_t)(sz), PROT_READ | PROT_WRITE, \ 70 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0) 71 72#define MMAPNONE(sz) _dl_mmap(NULL, (size_t)(sz), PROT_NONE, \ 73 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0) 74 75#define MMAP_ERROR(p) (_dl_mmap_error(p) ? MAP_FAILED : (p)) 76 77struct region_info { 78 void *p; /* page; low bits used to mark chunks */ 79 uintptr_t size; /* size for pages, or chunk_info pointer */ 80}; 81 82LIST_HEAD(chunk_head, chunk_info); 83 84struct dir_info { 85 u_int32_t canary1; 86 int active; /* status of malloc */ 87 struct region_info *r; /* region slots */ 88 size_t regions_total; /* number of region slots */ 89 size_t regions_free; /* number of free slots */ 90 /* lists of free chunk info structs */ 91 struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1]; 92 /* lists of chunks with free slots */ 93 struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS]; 94 size_t free_regions_size; /* free pages cached */ 95 /* free pages cache */ 96 u_int rotor; 97 struct region_info free_regions[MALLOC_MAXCACHE]; 98 /* delayed free chunk slots */ 99 void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1]; 100 size_t rbytesused; /* random bytes used */ 101 char *func; /* current function */ 102 u_char rbytes[256]; /* random bytes */ 103 u_int32_t canary2; 104}; 105#define DIR_INFO_RSZ ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \ 106 ~MALLOC_PAGEMASK) 107 108/* 109 * This structure describes a page worth of chunks. 110 * 111 * How many bits per u_short in the bitmap 112 */ 113#define MALLOC_BITS (NBBY * sizeof(u_short)) 114struct chunk_info { 115 LIST_ENTRY(chunk_info) entries; 116 void *page; /* pointer to the page */ 117 u_short canary; 118 u_short size; /* size of this page's chunks */ 119 u_short shift; /* how far to shift for this size */ 120 u_short free; /* how many free chunks */ 121 u_short total; /* how many chunk */ 122 u_short offset; /* requested size table offset */ 123 /* which chunks are free */ 124 u_short bits[1]; 125}; 126 127#define MALLOC_FREEUNMAP 0 128#define MALLOC_JUNK 1 129#define CHUNK_CANARIES 1 130#define MALLOC_GUARD ((size_t)MALLOC_PAGESIZE) 131#define MALLOC_CACHE MALLOC_DEFAULT_CACHE 132 133struct malloc_readonly { 134 struct dir_info *g_pool; /* Main bookkeeping information */ 135 u_int32_t malloc_canary; /* Matched against ones in g_pool */ 136}; 137 138/* 139 * malloc configuration 140 */ 141static struct malloc_readonly mopts __relro; 142 143#define g_pool mopts.g_pool 144 145static u_char getrbyte(struct dir_info *d); 146 147/* low bits of r->p determine size: 0 means >= page size and p->size holding 148 * real size, otherwise r->size is a shift count, or 1 for malloc(0) 149 */ 150#define REALSIZE(sz, r) \ 151 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \ 152 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1)))) 153 154static inline size_t 155hash(void *p) 156{ 157 size_t sum; 158 uintptr_t u; 159 160 u = (uintptr_t)p >> MALLOC_PAGESHIFT; 161 sum = u; 162 sum = (sum << 7) - sum + (u >> 16); 163#ifdef __LP64__ 164 sum = (sum << 7) - sum + (u >> 32); 165 sum = (sum << 7) - sum + (u >> 48); 166#endif 167 return sum; 168} 169 170static __dead void 171wrterror(char *msg) 172{ 173 if (g_pool != NULL && g_pool->func != NULL) 174 _dl_die("%s error: %s", g_pool->func, msg); 175 else 176 _dl_die("%s", msg); 177} 178 179static void 180rbytes_init(struct dir_info *d) 181{ 182 _dl_arc4randombuf(d->rbytes, sizeof(d->rbytes)); 183 /* add 1 to account for using d->rbytes[0] */ 184 d->rbytesused = 1 + d->rbytes[0] % (sizeof(d->rbytes) / 2); 185} 186 187static inline u_char 188getrbyte(struct dir_info *d) 189{ 190 u_char x; 191 192 if (d->rbytesused >= sizeof(d->rbytes)) 193 rbytes_init(d); 194 x = d->rbytes[d->rbytesused++]; 195 return x; 196} 197 198/* 199 * Initialize the malloc subsystem before relro processing. 200 */ 201void 202_dl_malloc_init(void) 203{ 204 char *p; 205 int i, j; 206 size_t d_avail, regioninfo_size, tmp; 207 struct dir_info *d; 208 209 do { 210 _dl_arc4randombuf(&mopts.malloc_canary, 211 sizeof(mopts.malloc_canary)); 212 } while (mopts.malloc_canary == 0); 213 214 /* 215 * Allocate dir_info with a guard page on either side. Also 216 * randomise offset inside the page at which the dir_info 217 * lies (subject to alignment by 1 << MALLOC_MINSHIFT) 218 */ 219 p = MMAPNONE(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2)); 220 p = MMAP_ERROR(p); 221 if (p == MAP_FAILED) 222 wrterror("malloc init mmap failed"); 223 _dl_mprotect(p + MALLOC_PAGESIZE, DIR_INFO_RSZ, PROT_READ | PROT_WRITE); 224 d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT; 225 226 _dl_arc4randombuf(&tmp, sizeof(tmp)); 227 d = (struct dir_info *)(p + MALLOC_PAGESIZE + 228 ((tmp % d_avail) << MALLOC_MINSHIFT)); /* not uniform */ 229 230 rbytes_init(d); 231 d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS; 232 regioninfo_size = d->regions_total * sizeof(struct region_info); 233 d->r = MMAP(regioninfo_size); 234 d->r = MMAP_ERROR(d->r); 235 if (d->r == MAP_FAILED) 236 wrterror("malloc init mmap failed"); 237 for (i = 0; i <= MALLOC_MAXSHIFT; i++) { 238 LIST_INIT(&d->chunk_info_list[i]); 239 for (j = 0; j < MALLOC_CHUNK_LISTS; j++) 240 LIST_INIT(&d->chunk_dir[i][j]); 241 } 242 d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d; 243 d->canary2 = ~d->canary1; 244 245 g_pool = d; 246} 247 248static int 249omalloc_grow(struct dir_info *d) 250{ 251 size_t newtotal; 252 size_t newsize; 253 size_t mask; 254 size_t i; 255 struct region_info *p; 256 257 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2) 258 return 1; 259 260 newtotal = d->regions_total * 2; 261 newsize = newtotal * sizeof(struct region_info); 262 mask = newtotal - 1; 263 264 p = MMAP(newsize); 265 p = MMAP_ERROR(p); 266 if (p == MAP_FAILED) 267 return 1; 268 269 for (i = 0; i < d->regions_total; i++) { 270 void *q = d->r[i].p; 271 if (q != NULL) { 272 size_t index = hash(q) & mask; 273 while (p[index].p != NULL) { 274 index = (index - 1) & mask; 275 } 276 p[index] = d->r[i]; 277 } 278 } 279 /* avoid pages containing meta info to end up in cache */ 280 if (_dl_munmap(d->r, d->regions_total * sizeof(struct region_info))) 281 wrterror("munmap"); 282 d->regions_free = d->regions_free + d->regions_total; 283 d->regions_total = newtotal; 284 d->r = p; 285 return 0; 286} 287 288/* 289 * The hashtable uses the assumption that p is never NULL. This holds since 290 * non-MAP_FIXED mappings with hint 0 start at BRKSIZ. 291 */ 292static int 293insert(struct dir_info *d, void *p, size_t sz) 294{ 295 size_t index; 296 size_t mask; 297 void *q; 298 299 if (d->regions_free * 4 < d->regions_total) { 300 if (omalloc_grow(d)) 301 return 1; 302 } 303 mask = d->regions_total - 1; 304 index = hash(p) & mask; 305 q = d->r[index].p; 306 while (q != NULL) { 307 index = (index - 1) & mask; 308 q = d->r[index].p; 309 } 310 d->r[index].p = p; 311 d->r[index].size = sz; 312 d->regions_free--; 313 return 0; 314} 315 316static struct region_info * 317find(struct dir_info *d, void *p) 318{ 319 size_t index; 320 size_t mask = d->regions_total - 1; 321 void *q, *r; 322 323 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 324 d->canary1 != ~d->canary2) 325 wrterror("internal struct corrupt"); 326 p = MASK_POINTER(p); 327 index = hash(p) & mask; 328 r = d->r[index].p; 329 q = MASK_POINTER(r); 330 while (q != p && r != NULL) { 331 index = (index - 1) & mask; 332 r = d->r[index].p; 333 q = MASK_POINTER(r); 334 } 335 return (q == p && r != NULL) ? &d->r[index] : NULL; 336} 337 338static void 339delete(struct dir_info *d, struct region_info *ri) 340{ 341 /* algorithm R, Knuth Vol III section 6.4 */ 342 size_t mask = d->regions_total - 1; 343 size_t i, j, r; 344 345 if (d->regions_total & (d->regions_total - 1)) 346 wrterror("regions_total not 2^x"); 347 d->regions_free++; 348 349 i = ri - d->r; 350 for (;;) { 351 d->r[i].p = NULL; 352 d->r[i].size = 0; 353 j = i; 354 for (;;) { 355 i = (i - 1) & mask; 356 if (d->r[i].p == NULL) 357 return; 358 r = hash(d->r[i].p) & mask; 359 if ((i <= r && r < j) || (r < j && j < i) || 360 (j < i && i <= r)) 361 continue; 362 d->r[j] = d->r[i]; 363 break; 364 } 365 366 } 367} 368 369/* 370 * Cache maintenance. We keep at most malloc_cache pages cached. 371 * If the cache is becoming full, unmap pages in the cache for real, 372 * and then add the region to the cache 373 * Opposed to the regular region data structure, the sizes in the 374 * cache are in MALLOC_PAGESIZE units. 375 */ 376static void 377unmap(struct dir_info *d, void *p, size_t sz, int junk) 378{ 379 size_t psz = sz >> MALLOC_PAGESHIFT; 380 size_t rsz; 381 struct region_info *r; 382 u_int i, offset, mask; 383 384 if (sz != PAGEROUND(sz)) 385 wrterror("munmap round"); 386 387 rsz = MALLOC_CACHE - d->free_regions_size; 388 389 if (psz > MALLOC_CACHE) { 390 if (_dl_munmap(p, sz)) 391 wrterror("munmap"); 392 return; 393 } 394 offset = getrbyte(d); 395 mask = MALLOC_CACHE - 1; 396 if (psz > rsz) { 397 size_t tounmap = psz - rsz; 398 for (i = 0; ; i++) { 399 r = &d->free_regions[(i + offset) & mask]; 400 if (r->p != NULL) { 401 rsz = r->size << MALLOC_PAGESHIFT; 402 if (_dl_munmap(r->p, rsz)) 403 wrterror("munmap"); 404 r->p = NULL; 405 if (tounmap > r->size) 406 tounmap -= r->size; 407 else 408 tounmap = 0; 409 d->free_regions_size -= r->size; 410 if (tounmap == 0) { 411 offset = i; 412 break; 413 } 414 } 415 } 416 } 417 for (i = 0; ; i++) { 418 r = &d->free_regions[(i + offset) & mask]; 419 if (r->p == NULL) { 420 if (junk && !MALLOC_FREEUNMAP) { 421 size_t amt = junk == 1 ? MALLOC_MAXCHUNK : sz; 422 _dl_memset(p, SOME_FREEJUNK, amt); 423 } 424 if (MALLOC_FREEUNMAP) 425 _dl_mprotect(p, sz, PROT_NONE); 426 r->p = p; 427 r->size = psz; 428 d->free_regions_size += psz; 429 break; 430 } 431 } 432 if (d->free_regions_size > MALLOC_CACHE) 433 wrterror("malloc cache overflow"); 434} 435 436static void * 437map(struct dir_info *d, size_t sz, int zero_fill) 438{ 439 size_t psz = sz >> MALLOC_PAGESHIFT; 440 struct region_info *r, *big = NULL; 441 u_int i; 442 void *p; 443 444 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 445 d->canary1 != ~d->canary2) 446 wrterror("internal struct corrupt"); 447 if (sz != PAGEROUND(sz)) { 448 wrterror("map round"); 449 return MAP_FAILED; 450 } 451 if (psz > d->free_regions_size) { 452 p = MMAP(sz); 453 p = MMAP_ERROR(p); 454 /* zero fill not needed */ 455 return p; 456 } 457 for (i = 0; i < MALLOC_CACHE; i++) { 458 r = &d->free_regions[(i + d->rotor) & (MALLOC_CACHE - 1)]; 459 if (r->p != NULL) { 460 if (r->size == psz) { 461 p = r->p; 462 if (MALLOC_FREEUNMAP) 463 _dl_mprotect(p, sz, PROT_READ | PROT_WRITE); 464 r->p = NULL; 465 d->free_regions_size -= psz; 466 if (zero_fill) 467 _dl_memset(p, 0, sz); 468 else if (MALLOC_JUNK == 2 && 469 MALLOC_FREEUNMAP) 470 _dl_memset(p, SOME_FREEJUNK, sz); 471 d->rotor += i + 1; 472 return p; 473 } else if (r->size > psz) 474 big = r; 475 } 476 } 477 if (big != NULL) { 478 r = big; 479 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT); 480 if (MALLOC_FREEUNMAP) 481 _dl_mprotect(p, sz, PROT_READ | PROT_WRITE); 482 r->size -= psz; 483 d->free_regions_size -= psz; 484 if (zero_fill) 485 _dl_memset(p, 0, sz); 486 else if (MALLOC_JUNK == 2 && MALLOC_FREEUNMAP) 487 _dl_memset(p, SOME_FREEJUNK, sz); 488 return p; 489 } 490 p = MMAP(sz); 491 p = MMAP_ERROR(p); 492 if (d->free_regions_size > MALLOC_CACHE) 493 wrterror("malloc cache"); 494 /* zero fill not needed */ 495 return p; 496} 497 498static void 499init_chunk_info(struct dir_info *d, struct chunk_info *p, int bits) 500{ 501 int i; 502 503 if (bits == 0) { 504 p->shift = MALLOC_MINSHIFT; 505 p->total = p->free = MALLOC_PAGESIZE >> p->shift; 506 p->size = 0; 507 p->offset = 0xdead; 508 } else { 509 p->shift = bits; 510 p->total = p->free = MALLOC_PAGESIZE >> p->shift; 511 p->size = 1U << bits; 512 p->offset = howmany(p->total, MALLOC_BITS); 513 } 514 p->canary = (u_short)d->canary1; 515 516 /* set all valid bits in the bitmap */ 517 i = p->total - 1; 518 _dl_memset(p->bits, 0xff, sizeof(p->bits[0]) * (i / MALLOC_BITS)); 519 p->bits[i / MALLOC_BITS] = (2U << (i % MALLOC_BITS)) - 1; 520} 521 522static struct chunk_info * 523alloc_chunk_info(struct dir_info *d, int bits) 524{ 525 struct chunk_info *p; 526 527 if (LIST_EMPTY(&d->chunk_info_list[bits])) { 528 size_t size, count, i; 529 char *q; 530 531 if (bits == 0) 532 count = MALLOC_PAGESIZE / MALLOC_MINSIZE; 533 else 534 count = MALLOC_PAGESIZE >> bits; 535 536 size = howmany(count, MALLOC_BITS); 537 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short); 538 if (CHUNK_CANARIES) 539 size += count * sizeof(u_short); 540 size = _ALIGN(size); 541 542 q = MMAP(MALLOC_PAGESIZE); 543 q = MMAP_ERROR(q); 544 if (q == MAP_FAILED) 545 return NULL; 546 count = MALLOC_PAGESIZE / size; 547 548 for (i = 0; i < count; i++, q += size) 549 LIST_INSERT_HEAD(&d->chunk_info_list[bits], 550 (struct chunk_info *)q, entries); 551 } 552 p = LIST_FIRST(&d->chunk_info_list[bits]); 553 LIST_REMOVE(p, entries); 554 if (p->shift == 0) 555 init_chunk_info(d, p, bits); 556 return p; 557} 558 559/* 560 * Allocate a page of chunks 561 */ 562static struct chunk_info * 563omalloc_make_chunks(struct dir_info *d, int bits, int listnum) 564{ 565 struct chunk_info *bp; 566 void *pp; 567 568 /* Allocate a new bucket */ 569 pp = map(d, MALLOC_PAGESIZE, 0); 570 if (pp == MAP_FAILED) 571 return NULL; 572 573 bp = alloc_chunk_info(d, bits); 574 if (bp == NULL) 575 goto err; 576 /* memory protect the page allocated in the malloc(0) case */ 577 if (bits == 0 && _dl_mprotect(pp, MALLOC_PAGESIZE, PROT_NONE) < 0) 578 goto err; 579 580 bp->page = pp; 581 582 if (insert(d, (void *)((uintptr_t)pp | (bits + 1)), (uintptr_t)bp)) 583 goto err; 584 LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries); 585 return bp; 586 587err: 588 unmap(d, pp, MALLOC_PAGESIZE, MALLOC_JUNK); 589 return NULL; 590} 591 592static int 593find_chunksize(size_t size) 594{ 595 int r; 596 597 /* malloc(0) is special */ 598 if (size == 0) 599 return 0; 600 601 if (size < MALLOC_MINSIZE) 602 size = MALLOC_MINSIZE; 603 size--; 604 605 r = MALLOC_MINSHIFT; 606 while (size >> r) 607 r++; 608 return r; 609} 610 611static void 612fill_canary(char *ptr, size_t sz, size_t allocated) 613{ 614 size_t check_sz = allocated - sz; 615 616 if (check_sz > CHUNK_CHECK_LENGTH) 617 check_sz = CHUNK_CHECK_LENGTH; 618 _dl_memset(ptr + sz, SOME_JUNK, check_sz); 619} 620 621/* 622 * Allocate a chunk 623 */ 624static void * 625malloc_bytes(struct dir_info *d, size_t size) 626{ 627 u_int i, r; 628 int j, listnum; 629 size_t k; 630 u_short *lp; 631 struct chunk_info *bp; 632 void *p; 633 634 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 635 d->canary1 != ~d->canary2) 636 wrterror("internal struct corrupt"); 637 638 j = find_chunksize(size); 639 640 r = ((u_int)getrbyte(d) << 8) | getrbyte(d); 641 listnum = r % MALLOC_CHUNK_LISTS; 642 /* If it's empty, make a page more of that size chunks */ 643 if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) { 644 bp = omalloc_make_chunks(d, j, listnum); 645 if (bp == NULL) 646 return NULL; 647 } 648 649 if (bp->canary != (u_short)d->canary1) 650 wrterror("chunk info corrupted"); 651 652 i = (r / MALLOC_CHUNK_LISTS) & (bp->total - 1); 653 654 /* start somewhere in a short */ 655 lp = &bp->bits[i / MALLOC_BITS]; 656 if (*lp) { 657 j = i % MALLOC_BITS; 658 k = __builtin_ffs(*lp >> j); 659 if (k != 0) { 660 k += j - 1; 661 goto found; 662 } 663 } 664 /* no bit halfway, go to next full short */ 665 i /= MALLOC_BITS; 666 for (;;) { 667 if (++i >= bp->total / MALLOC_BITS) 668 i = 0; 669 lp = &bp->bits[i]; 670 if (*lp) { 671 k = __builtin_ffs(*lp) - 1; 672 break; 673 } 674 } 675found: 676 *lp ^= 1 << k; 677 678 /* If there are no more free, remove from free-list */ 679 if (--bp->free == 0) 680 LIST_REMOVE(bp, entries); 681 682 /* Adjust to the real offset of that chunk */ 683 k += (lp - bp->bits) * MALLOC_BITS; 684 685 if (CHUNK_CANARIES && size > 0) 686 bp->bits[bp->offset + k] = size; 687 688 k <<= bp->shift; 689 690 p = (char *)bp->page + k; 691 if (bp->size > 0) { 692 if (MALLOC_JUNK == 2) 693 _dl_memset(p, SOME_JUNK, bp->size); 694 else if (CHUNK_CANARIES) 695 fill_canary(p, size, bp->size); 696 } 697 return p; 698} 699 700static void 701validate_canary(u_char *ptr, size_t sz, size_t allocated) 702{ 703 size_t check_sz = allocated - sz; 704 u_char *p, *q; 705 706 if (check_sz > CHUNK_CHECK_LENGTH) 707 check_sz = CHUNK_CHECK_LENGTH; 708 p = ptr + sz; 709 q = p + check_sz; 710 711 while (p < q) 712 if (*p++ != SOME_JUNK) 713 wrterror("chunk canary corrupted"); 714} 715 716static uint32_t 717find_chunknum(struct dir_info *d, struct region_info *r, void *ptr, int check) 718{ 719 struct chunk_info *info; 720 uint32_t chunknum; 721 722 info = (struct chunk_info *)r->size; 723 if (info->canary != (u_short)d->canary1) 724 wrterror("chunk info corrupted"); 725 726 /* Find the chunk number on the page */ 727 chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift; 728 if (check && info->size > 0) { 729 validate_canary(ptr, info->bits[info->offset + chunknum], 730 info->size); 731 } 732 733 if ((uintptr_t)ptr & ((1U << (info->shift)) - 1)) { 734 wrterror("modified chunk-pointer"); 735 return -1; 736 } 737 if (info->bits[chunknum / MALLOC_BITS] & 738 (1U << (chunknum % MALLOC_BITS))) 739 wrterror("chunk is already free"); 740 return chunknum; 741} 742 743/* 744 * Free a chunk, and possibly the page it's on, if the page becomes empty. 745 */ 746static void 747free_bytes(struct dir_info *d, struct region_info *r, void *ptr) 748{ 749 struct chunk_head *mp; 750 struct chunk_info *info; 751 uint32_t chunknum; 752 int listnum; 753 754 info = (struct chunk_info *)r->size; 755 chunknum = find_chunknum(d, r, ptr, 0); 756 757 info->bits[chunknum / MALLOC_BITS] |= 1U << (chunknum % MALLOC_BITS); 758 info->free++; 759 760 if (info->free == 1) { 761 /* Page became non-full */ 762 listnum = getrbyte(d) % MALLOC_CHUNK_LISTS; 763 if (info->size != 0) 764 mp = &d->chunk_dir[info->shift][listnum]; 765 else 766 mp = &d->chunk_dir[0][listnum]; 767 768 LIST_INSERT_HEAD(mp, info, entries); 769 return; 770 } 771 772 if (info->free != info->total) 773 return; 774 775 LIST_REMOVE(info, entries); 776 777 if (info->size == 0 && !MALLOC_FREEUNMAP) 778 _dl_mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE); 779 unmap(d, info->page, MALLOC_PAGESIZE, 0); 780 781 delete(d, r); 782 if (info->size != 0) 783 mp = &d->chunk_info_list[info->shift]; 784 else 785 mp = &d->chunk_info_list[0]; 786 LIST_INSERT_HEAD(mp, info, entries); 787} 788 789static void * 790omalloc(size_t sz, int zero_fill) 791{ 792 void *p; 793 size_t psz; 794 795 if (sz > MALLOC_MAXCHUNK) { 796 if (sz >= SIZE_MAX - MALLOC_GUARD - MALLOC_PAGESIZE) { 797 return NULL; 798 } 799 sz += MALLOC_GUARD; 800 psz = PAGEROUND(sz); 801 p = map(g_pool, psz, zero_fill); 802 if (p == MAP_FAILED) { 803 return NULL; 804 } 805 if (insert(g_pool, p, sz)) { 806 unmap(g_pool, p, psz, 0); 807 return NULL; 808 } 809 if (MALLOC_GUARD) { 810 if (_dl_mprotect((char *)p + psz - MALLOC_GUARD, 811 MALLOC_GUARD, PROT_NONE)) 812 wrterror("mprotect"); 813 } 814 815 if (sz - MALLOC_GUARD < MALLOC_PAGESIZE - MALLOC_LEEWAY) { 816 /* fill whole allocation */ 817 if (MALLOC_JUNK == 2) 818 _dl_memset(p, SOME_JUNK, psz - MALLOC_GUARD); 819 /* shift towards the end */ 820 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_LEEWAY - 821 (sz - MALLOC_GUARD)) & ~(MALLOC_MINSIZE-1)); 822 /* fill zeros if needed and overwritten above */ 823 if (zero_fill && MALLOC_JUNK == 2) 824 _dl_memset(p, 0, sz - MALLOC_GUARD); 825 } else { 826 if (MALLOC_JUNK == 2) { 827 if (zero_fill) 828 _dl_memset((char *)p + sz - MALLOC_GUARD, 829 SOME_JUNK, psz - sz); 830 else 831 _dl_memset(p, SOME_JUNK, 832 psz - MALLOC_GUARD); 833 } else if (CHUNK_CANARIES) 834 fill_canary(p, sz - MALLOC_GUARD, 835 psz - MALLOC_GUARD); 836 } 837 838 } else { 839 /* takes care of SOME_JUNK */ 840 p = malloc_bytes(g_pool, sz); 841 if (zero_fill && p != NULL && sz > 0) 842 _dl_memset(p, 0, sz); 843 } 844 845 return p; 846} 847 848/* 849 * Common function for handling recursion. Only 850 * print the error message once, to avoid making the problem 851 * potentially worse. 852 */ 853static void 854malloc_recurse(void) 855{ 856 static int noprint; 857 858 if (noprint == 0) { 859 noprint = 1; 860 wrterror("recursive call"); 861 } 862 g_pool->active--; 863} 864 865void * 866_dl_malloc(size_t size) 867{ 868 void *r = NULL; 869 lock_cb *cb; 870 871 cb = _dl_thread_kern_stop(); 872 g_pool->func = "malloc():"; 873 if (g_pool->active++) { 874 malloc_recurse(); 875 goto ret; 876 } 877 r = omalloc(size, 0); 878 g_pool->active--; 879ret: 880 _dl_thread_kern_go(cb); 881 return r; 882} 883 884static void 885validate_junk(struct dir_info *pool, void *p) 886{ 887 struct region_info *r; 888 size_t byte, sz; 889 890 if (p == NULL) 891 return; 892 r = find(pool, p); 893 if (r == NULL) 894 wrterror("bogus pointer in validate_junk"); 895 REALSIZE(sz, r); 896 if (sz > CHUNK_CHECK_LENGTH) 897 sz = CHUNK_CHECK_LENGTH; 898 for (byte = 0; byte < sz; byte++) { 899 if (((unsigned char *)p)[byte] != SOME_FREEJUNK) 900 wrterror("use after free"); 901 } 902} 903 904static void 905ofree(void *p) 906{ 907 struct region_info *r; 908 size_t sz; 909 910 r = find(g_pool, p); 911 if (r == NULL) 912 wrterror("bogus pointer (double free?)"); 913 REALSIZE(sz, r); 914 if (sz > MALLOC_MAXCHUNK) { 915 if (sz - MALLOC_GUARD >= MALLOC_PAGESIZE - 916 MALLOC_LEEWAY) { 917 if (r->p != p) 918 wrterror("bogus pointer"); 919 if (CHUNK_CANARIES) 920 validate_canary(p, 921 sz - MALLOC_GUARD, 922 PAGEROUND(sz - MALLOC_GUARD)); 923 } else { 924#if notyetbecause_of_realloc 925 /* shifted towards the end */ 926 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE - 927 MALLOC_MINSIZE - sz - MALLOC_GUARD) & 928 ~(MALLOC_MINSIZE-1))) { 929 } 930#endif 931 p = r->p; 932 } 933 if (MALLOC_GUARD) { 934 if (sz < MALLOC_GUARD) 935 wrterror("guard size"); 936 if (!MALLOC_FREEUNMAP) { 937 if (_dl_mprotect((char *)p + PAGEROUND(sz) - 938 MALLOC_GUARD, MALLOC_GUARD, 939 PROT_READ | PROT_WRITE)) 940 wrterror("mprotect"); 941 } 942 } 943 unmap(g_pool, p, PAGEROUND(sz), MALLOC_JUNK); 944 delete(g_pool, r); 945 } else { 946 void *tmp; 947 int i; 948 struct chunk_info *info = (struct chunk_info *)r->size; 949 950 if (info->size != sz) 951 wrterror("internal struct corrupt"); 952 find_chunknum(g_pool, r, p, CHUNK_CANARIES); 953 for (i = 0; i <= MALLOC_DELAYED_CHUNK_MASK; i++) { 954 if (p == g_pool->delayed_chunks[i]) 955 wrterror("double free"); 956 } 957 if (MALLOC_JUNK && sz > 0) 958 _dl_memset(p, SOME_FREEJUNK, sz); 959 i = getrbyte(g_pool) & MALLOC_DELAYED_CHUNK_MASK; 960 tmp = p; 961 p = g_pool->delayed_chunks[i]; 962 g_pool->delayed_chunks[i] = tmp; 963 if (MALLOC_JUNK) 964 validate_junk(g_pool, p); 965 if (p != NULL) { 966 r = find(g_pool, p); 967 if (r == NULL) 968 wrterror("bogus pointer (double free?)"); 969 free_bytes(g_pool, r, p); 970 } 971 } 972} 973 974void 975_dl_free(void *ptr) 976{ 977 lock_cb *cb; 978 979 /* This is legal. */ 980 if (ptr == NULL) 981 return; 982 983 cb = _dl_thread_kern_stop(); 984 if (g_pool == NULL) 985 wrterror("free() called before allocation"); 986 g_pool->func = "free():"; 987 if (g_pool->active++) { 988 malloc_recurse(); 989 goto ret; 990 } 991 ofree(ptr); 992 g_pool->active--; 993ret: 994 _dl_thread_kern_go(cb); 995} 996 997 998/* 999 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX 1000 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW 1001 */ 1002#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4)) 1003 1004void * 1005_dl_calloc(size_t nmemb, size_t size) 1006{ 1007 void *r = NULL; 1008 lock_cb *cb; 1009 1010 cb = _dl_thread_kern_stop(); 1011 g_pool->func = "calloc():"; 1012 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1013 nmemb > 0 && SIZE_MAX / nmemb < size) { 1014 goto ret; 1015 } 1016 1017 if (g_pool->active++) { 1018 malloc_recurse(); 1019 goto ret; 1020 } 1021 1022 size *= nmemb; 1023 r = omalloc(size, 1); 1024 g_pool->active--; 1025ret: 1026 _dl_thread_kern_go(cb); 1027 return r; 1028} 1029 1030 1031static void * 1032orealloc(void *p, size_t newsz) 1033{ 1034 struct region_info *r; 1035 void *q; 1036 size_t oldsz; 1037 1038 q = omalloc(newsz, 0); 1039 if (p == NULL || q == NULL) 1040 return q; 1041 r = find(g_pool, p); 1042 if (r == NULL) 1043 wrterror("bogus pointer (double free?)"); 1044 REALSIZE(oldsz, r); 1045 if (oldsz > MALLOC_MAXCHUNK) { 1046 if (oldsz < MALLOC_GUARD) 1047 wrterror("guard size"); 1048 oldsz -= MALLOC_GUARD; 1049 } 1050 _dl_bcopy(p, q, oldsz < newsz ? oldsz : newsz); 1051 ofree(p); 1052 return q; 1053} 1054 1055 1056void * 1057_dl_realloc(void *ptr, size_t size) 1058{ 1059 void *r = NULL; 1060 lock_cb *cb; 1061 1062 cb = _dl_thread_kern_stop(); 1063 g_pool->func = "realloc():"; 1064 if (g_pool->active++) { 1065 malloc_recurse(); 1066 goto ret; 1067 } 1068 r = orealloc(ptr, size); 1069 g_pool->active--; 1070ret: 1071 _dl_thread_kern_go(cb); 1072 return r; 1073} 1074 1075static void * 1076mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill) 1077{ 1078 char *p, *q; 1079 1080 if (alignment < MALLOC_PAGESIZE || ((alignment - 1) & alignment) != 0) 1081 wrterror("mapalign bad alignment"); 1082 if (sz != PAGEROUND(sz)) 1083 wrterror("mapalign round"); 1084 1085 /* Allocate sz + alignment bytes of memory, which must include a 1086 * subrange of size bytes that is properly aligned. Unmap the 1087 * other bytes, and then return that subrange. 1088 */ 1089 1090 /* We need sz + alignment to fit into a size_t. */ 1091 if (alignment > SIZE_MAX - sz) 1092 return MAP_FAILED; 1093 1094 p = map(d, sz + alignment, zero_fill); 1095 if (p == MAP_FAILED) 1096 return MAP_FAILED; 1097 q = (char *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1)); 1098 if (q != p) { 1099 if (_dl_munmap(p, q - p)) 1100 wrterror("munmap"); 1101 } 1102 if (_dl_munmap(q + sz, alignment - (q - p))) 1103 wrterror("munmap"); 1104 1105 return q; 1106} 1107 1108static void * 1109omemalign(size_t alignment, size_t sz, int zero_fill) 1110{ 1111 size_t psz; 1112 void *p; 1113 1114 /* If between half a page and a page, avoid MALLOC_MOVE. */ 1115 if (sz > MALLOC_MAXCHUNK && sz < MALLOC_PAGESIZE) 1116 sz = MALLOC_PAGESIZE; 1117 if (alignment <= MALLOC_PAGESIZE) { 1118 /* 1119 * max(size, alignment) is enough to assure the requested 1120 * alignment, since the allocator always allocates 1121 * power-of-two blocks. 1122 */ 1123 if (sz < alignment) 1124 sz = alignment; 1125 return omalloc(sz, zero_fill); 1126 } 1127 1128 if (sz >= SIZE_MAX - MALLOC_GUARD - MALLOC_PAGESIZE) { 1129 return NULL; 1130 } 1131 1132 sz += MALLOC_GUARD; 1133 psz = PAGEROUND(sz); 1134 1135 p = mapalign(g_pool, alignment, psz, zero_fill); 1136 if (p == MAP_FAILED) { 1137 return NULL; 1138 } 1139 1140 if (insert(g_pool, p, sz)) { 1141 unmap(g_pool, p, psz, 0); 1142 return NULL; 1143 } 1144 1145 if (MALLOC_GUARD) { 1146 if (_dl_mprotect((char *)p + psz - MALLOC_GUARD, 1147 MALLOC_GUARD, PROT_NONE)) 1148 wrterror("mprotect"); 1149 } 1150 1151 if (MALLOC_JUNK == 2) { 1152 if (zero_fill) 1153 _dl_memset((char *)p + sz - MALLOC_GUARD, 1154 SOME_JUNK, psz - sz); 1155 else 1156 _dl_memset(p, SOME_JUNK, psz - MALLOC_GUARD); 1157 } else if (CHUNK_CANARIES) 1158 fill_canary(p, sz - MALLOC_GUARD, 1159 psz - MALLOC_GUARD); 1160 1161 return p; 1162} 1163 1164void * 1165_dl_aligned_alloc(size_t alignment, size_t size) 1166{ 1167 void *r = NULL; 1168 lock_cb *cb; 1169 1170 /* Make sure that alignment is a large enough power of 2. */ 1171 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) 1172 return NULL; 1173 1174 cb = _dl_thread_kern_stop(); 1175 g_pool->func = "aligned_alloc():"; 1176 if (g_pool->active++) { 1177 malloc_recurse(); 1178 goto ret; 1179 } 1180 r = omemalign(alignment, size, 0); 1181 g_pool->active--; 1182ret: 1183 _dl_thread_kern_go(cb); 1184 return r; 1185} 1186