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