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