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