1 /* $OpenBSD: malloc.c,v 1.146 2012/07/09 08:39:24 deraadt Exp $ */ 2 /* 3 * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 /* 19 * Parts of this code, mainly the sub page sized chunk management code is 20 * derived from the malloc implementation with the following license: 21 */ 22 /* 23 * ---------------------------------------------------------------------------- 24 * "THE BEER-WARE LICENSE" (Revision 42): 25 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you 26 * can do whatever you want with this stuff. If we meet some day, and you think 27 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 28 * ---------------------------------------------------------------------------- 29 */ 30 31 /* #define MALLOC_STATS */ 32 33 #include <sys/types.h> 34 #include <sys/param.h> 35 #include <sys/queue.h> 36 #include <sys/mman.h> 37 #include <sys/uio.h> 38 #include <errno.h> 39 #include <stdint.h> 40 #include <stdlib.h> 41 #include <string.h> 42 #include <stdio.h> 43 #include <unistd.h> 44 45 #ifdef MALLOC_STATS 46 #include <sys/tree.h> 47 #include <fcntl.h> 48 #endif 49 50 #include "thread_private.h" 51 52 #if defined(__sparc__) && !defined(__sparcv9__) 53 #define MALLOC_PAGESHIFT (13U) 54 #elif defined(__mips64__) 55 #define MALLOC_PAGESHIFT (14U) 56 #else 57 #define MALLOC_PAGESHIFT (PAGE_SHIFT) 58 #endif 59 60 #define MALLOC_MINSHIFT 4 61 #define MALLOC_MAXSHIFT (MALLOC_PAGESHIFT - 1) 62 #define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT) 63 #define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT) 64 #define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1) 65 #define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK)) 66 67 #define MALLOC_MAXCHUNK (1 << MALLOC_MAXSHIFT) 68 #define MALLOC_MAXCACHE 256 69 #define MALLOC_DELAYED_CHUNKS 15 /* max of getrnibble() */ 70 #define MALLOC_INITIAL_REGIONS 512 71 #define MALLOC_DEFAULT_CACHE 64 72 73 /* 74 * When the P option is active, we move allocations between half a page 75 * and a whole page towards the end, subject to alignment constraints. 76 * This is the extra headroom we allow. Set to zero to be the most 77 * strict. 78 */ 79 #define MALLOC_LEEWAY 0 80 81 #define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK) 82 83 /* 84 * What to use for Junk. This is the byte value we use to fill with 85 * when the 'J' option is enabled. Use SOME_JUNK right after alloc, 86 * and SOME_FREEJUNK right before free. 87 */ 88 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */ 89 #define SOME_FREEJUNK 0xdf 90 91 #define MMAP(sz) mmap(NULL, (size_t)(sz), PROT_READ | PROT_WRITE, \ 92 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0) 93 94 #define MMAPA(a,sz) mmap((a), (size_t)(sz), PROT_READ | PROT_WRITE, \ 95 MAP_ANON | MAP_PRIVATE, -1, (off_t) 0) 96 97 #define MQUERY(a, sz) mquery((a), (size_t)(sz), PROT_READ | PROT_WRITE, \ 98 MAP_ANON | MAP_PRIVATE | MAP_FIXED, -1, (off_t)0) 99 100 struct region_info { 101 void *p; /* page; low bits used to mark chunks */ 102 uintptr_t size; /* size for pages, or chunk_info pointer */ 103 #ifdef MALLOC_STATS 104 void *f; /* where allocated from */ 105 #endif 106 }; 107 108 LIST_HEAD(chunk_head, chunk_info); 109 110 struct dir_info { 111 u_int32_t canary1; 112 struct region_info *r; /* region slots */ 113 size_t regions_total; /* number of region slots */ 114 size_t regions_free; /* number of free slots */ 115 /* lists of free chunk info structs */ 116 struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1]; 117 /* lists of chunks with free slots */ 118 struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1]; 119 size_t free_regions_size; /* free pages cached */ 120 /* free pages cache */ 121 struct region_info free_regions[MALLOC_MAXCACHE]; 122 /* delayed free chunk slots */ 123 void *delayed_chunks[MALLOC_DELAYED_CHUNKS + 1]; 124 u_short chunk_start; 125 #ifdef MALLOC_STATS 126 size_t inserts; 127 size_t insert_collisions; 128 size_t finds; 129 size_t find_collisions; 130 size_t deletes; 131 size_t delete_moves; 132 size_t cheap_realloc_tries; 133 size_t cheap_reallocs; 134 #define STATS_INC(x) ((x)++) 135 #define STATS_ZERO(x) ((x) = 0) 136 #define STATS_SETF(x,y) ((x)->f = (y)) 137 #else 138 #define STATS_INC(x) /* nothing */ 139 #define STATS_ZERO(x) /* nothing */ 140 #define STATS_SETF(x,y) /* nothing */ 141 #endif /* MALLOC_STATS */ 142 u_int32_t canary2; 143 }; 144 #define DIR_INFO_RSZ ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \ 145 ~MALLOC_PAGEMASK) 146 147 /* 148 * This structure describes a page worth of chunks. 149 * 150 * How many bits per u_short in the bitmap 151 */ 152 #define MALLOC_BITS (NBBY * sizeof(u_short)) 153 struct chunk_info { 154 LIST_ENTRY(chunk_info) entries; 155 void *page; /* pointer to the page */ 156 u_int32_t canary; 157 u_short size; /* size of this page's chunks */ 158 u_short shift; /* how far to shift for this size */ 159 u_short free; /* how many free chunks */ 160 u_short total; /* how many chunk */ 161 /* which chunks are free */ 162 u_short bits[1]; 163 }; 164 165 struct malloc_readonly { 166 struct dir_info *g_pool; /* Main bookkeeping information */ 167 int malloc_abort; /* abort() on error */ 168 int malloc_freeprot; /* mprotect free pages PROT_NONE? */ 169 int malloc_hint; /* call madvice on free pages? */ 170 int malloc_junk; /* junk fill? */ 171 int malloc_move; /* move allocations to end of page? */ 172 int malloc_realloc; /* always realloc? */ 173 int malloc_xmalloc; /* xmalloc behaviour? */ 174 int malloc_zero; /* zero fill? */ 175 size_t malloc_guard; /* use guard pages after allocations? */ 176 u_int malloc_cache; /* free pages we cache */ 177 #ifdef MALLOC_STATS 178 int malloc_stats; /* dump statistics at end */ 179 #endif 180 u_int32_t malloc_canary; /* Matched against ones in g_pool */ 181 }; 182 183 /* This object is mapped PROT_READ after initialisation to prevent tampering */ 184 static union { 185 struct malloc_readonly mopts; 186 u_char _pad[MALLOC_PAGESIZE]; 187 } malloc_readonly __attribute__((aligned(MALLOC_PAGESIZE))); 188 #define mopts malloc_readonly.mopts 189 #define g_pool mopts.g_pool 190 191 char *malloc_options; /* compile-time options */ 192 193 static char *malloc_func; /* current function */ 194 static int malloc_active; /* status of malloc */ 195 196 static size_t malloc_guarded; /* bytes used for guards */ 197 static size_t malloc_used; /* bytes allocated */ 198 199 static size_t rnibblesused; /* random nibbles used */ 200 static u_char rbytes[512]; /* random bytes */ 201 static u_char getrnibble(void); 202 203 extern char *__progname; 204 205 #ifdef MALLOC_STATS 206 void malloc_dump(int); 207 static void malloc_exit(void); 208 #define CALLER __builtin_return_address(0) 209 #else 210 #define CALLER NULL 211 #endif 212 213 /* low bits of r->p determine size: 0 means >= page size and p->size holding 214 * real size, otherwise r->size is a shift count, or 1 for malloc(0) 215 */ 216 #define REALSIZE(sz, r) \ 217 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \ 218 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1)))) 219 220 static inline size_t 221 hash(void *p) 222 { 223 size_t sum; 224 union { 225 uintptr_t p; 226 unsigned short a[sizeof(void *) / sizeof(short)]; 227 } u; 228 u.p = (uintptr_t)p >> MALLOC_PAGESHIFT; 229 sum = u.a[0]; 230 sum = (sum << 7) - sum + u.a[1]; 231 #ifdef __LP64__ 232 sum = (sum << 7) - sum + u.a[2]; 233 sum = (sum << 7) - sum + u.a[3]; 234 #endif 235 return sum; 236 } 237 238 static void 239 wrterror(char *msg, void *p) 240 { 241 char *q = " error: "; 242 struct iovec iov[6]; 243 char buf[20]; 244 int saved_errno = errno; 245 246 iov[0].iov_base = __progname; 247 iov[0].iov_len = strlen(__progname); 248 iov[1].iov_base = malloc_func; 249 iov[1].iov_len = strlen(malloc_func); 250 iov[2].iov_base = q; 251 iov[2].iov_len = strlen(q); 252 iov[3].iov_base = msg; 253 iov[3].iov_len = strlen(msg); 254 iov[4].iov_base = buf; 255 if (p == NULL) 256 iov[4].iov_len = 0; 257 else { 258 snprintf(buf, sizeof(buf), " %p", p); 259 iov[4].iov_len = strlen(buf); 260 } 261 iov[5].iov_base = "\n"; 262 iov[5].iov_len = 1; 263 writev(STDERR_FILENO, iov, 6); 264 265 #ifdef MALLOC_STATS 266 if (mopts.malloc_stats) 267 malloc_dump(STDERR_FILENO); 268 #endif /* MALLOC_STATS */ 269 270 errno = saved_errno; 271 if (mopts.malloc_abort) 272 abort(); 273 } 274 275 static void 276 rbytes_init(void) 277 { 278 arc4random_buf(rbytes, sizeof(rbytes)); 279 rnibblesused = 0; 280 } 281 282 static inline u_char 283 getrnibble(void) 284 { 285 u_char x; 286 287 if (rnibblesused >= 2 * sizeof(rbytes)) 288 rbytes_init(); 289 x = rbytes[rnibblesused++ / 2]; 290 return (rnibblesused & 1 ? x & 0xf : x >> 4); 291 } 292 293 /* 294 * Cache maintenance. We keep at most malloc_cache pages cached. 295 * If the cache is becoming full, unmap pages in the cache for real, 296 * and then add the region to the cache 297 * Opposed to the regular region data structure, the sizes in the 298 * cache are in MALLOC_PAGESIZE units. 299 */ 300 static void 301 unmap(struct dir_info *d, void *p, size_t sz) 302 { 303 size_t psz = sz >> MALLOC_PAGESHIFT; 304 size_t rsz, tounmap; 305 struct region_info *r; 306 u_int i, offset; 307 308 if (sz != PAGEROUND(sz)) { 309 wrterror("munmap round", NULL); 310 return; 311 } 312 313 if (psz > mopts.malloc_cache) { 314 if (munmap(p, sz)) 315 wrterror("munmap", p); 316 malloc_used -= sz; 317 return; 318 } 319 tounmap = 0; 320 rsz = mopts.malloc_cache - d->free_regions_size; 321 if (psz > rsz) 322 tounmap = psz - rsz; 323 offset = getrnibble() + getrnibble() << 4; 324 for (i = 0; tounmap > 0 && i < mopts.malloc_cache; i++) { 325 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 326 if (r->p != NULL) { 327 rsz = r->size << MALLOC_PAGESHIFT; 328 if (munmap(r->p, rsz)) 329 wrterror("munmap", r->p); 330 r->p = NULL; 331 if (tounmap > r->size) 332 tounmap -= r->size; 333 else 334 tounmap = 0; 335 d->free_regions_size -= r->size; 336 r->size = 0; 337 malloc_used -= rsz; 338 } 339 } 340 if (tounmap > 0) 341 wrterror("malloc cache underflow", NULL); 342 for (i = 0; i < mopts.malloc_cache; i++) { 343 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 344 if (r->p == NULL) { 345 if (mopts.malloc_hint) 346 madvise(p, sz, MADV_FREE); 347 if (mopts.malloc_freeprot) 348 mprotect(p, sz, PROT_NONE); 349 r->p = p; 350 r->size = psz; 351 d->free_regions_size += psz; 352 break; 353 } 354 } 355 if (i == mopts.malloc_cache) 356 wrterror("malloc free slot lost", NULL); 357 if (d->free_regions_size > mopts.malloc_cache) 358 wrterror("malloc cache overflow", NULL); 359 } 360 361 static void 362 zapcacheregion(struct dir_info *d, void *p, size_t len) 363 { 364 u_int i; 365 struct region_info *r; 366 size_t rsz; 367 368 for (i = 0; i < mopts.malloc_cache; i++) { 369 r = &d->free_regions[i]; 370 if (r->p >= p && r->p <= (void *)((char *)p + len)) { 371 rsz = r->size << MALLOC_PAGESHIFT; 372 if (munmap(r->p, rsz)) 373 wrterror("munmap", r->p); 374 r->p = NULL; 375 d->free_regions_size -= r->size; 376 r->size = 0; 377 malloc_used -= rsz; 378 } 379 } 380 } 381 382 static void * 383 map(struct dir_info *d, size_t sz, int zero_fill) 384 { 385 size_t psz = sz >> MALLOC_PAGESHIFT; 386 struct region_info *r, *big = NULL; 387 u_int i, offset; 388 void *p; 389 390 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 391 d->canary1 != ~d->canary2) 392 wrterror("internal struct corrupt", NULL); 393 if (sz != PAGEROUND(sz)) { 394 wrterror("map round", NULL); 395 return MAP_FAILED; 396 } 397 if (psz > d->free_regions_size) { 398 p = MMAP(sz); 399 if (p != MAP_FAILED) 400 malloc_used += sz; 401 /* zero fill not needed */ 402 return p; 403 } 404 offset = getrnibble() + getrnibble() << 4; 405 for (i = 0; i < mopts.malloc_cache; i++) { 406 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 407 if (r->p != NULL) { 408 if (r->size == psz) { 409 p = r->p; 410 if (mopts.malloc_freeprot) 411 mprotect(p, sz, PROT_READ | PROT_WRITE); 412 if (mopts.malloc_hint) 413 madvise(p, sz, MADV_NORMAL); 414 r->p = NULL; 415 r->size = 0; 416 d->free_regions_size -= psz; 417 if (zero_fill) 418 memset(p, 0, sz); 419 else if (mopts.malloc_junk && 420 mopts.malloc_freeprot) 421 memset(p, SOME_FREEJUNK, sz); 422 return p; 423 } else if (r->size > psz) 424 big = r; 425 } 426 } 427 if (big != NULL) { 428 r = big; 429 p = (char *)r->p + ((r->size - psz) << MALLOC_PAGESHIFT); 430 if (mopts.malloc_freeprot) 431 mprotect(p, sz, PROT_READ | PROT_WRITE); 432 if (mopts.malloc_hint) 433 madvise(p, sz, MADV_NORMAL); 434 r->size -= psz; 435 d->free_regions_size -= psz; 436 if (zero_fill) 437 memset(p, 0, sz); 438 else if (mopts.malloc_junk && mopts.malloc_freeprot) 439 memset(p, SOME_FREEJUNK, sz); 440 return p; 441 } 442 p = MMAP(sz); 443 if (p != MAP_FAILED) 444 malloc_used += sz; 445 if (d->free_regions_size > mopts.malloc_cache) 446 wrterror("malloc cache", NULL); 447 /* zero fill not needed */ 448 return p; 449 } 450 451 /* 452 * Initialize a dir_info, which should have been cleared by caller 453 */ 454 static int 455 omalloc_init(struct dir_info **dp) 456 { 457 char *p, b[64]; 458 int i, j; 459 size_t d_avail, regioninfo_size; 460 struct dir_info *d; 461 462 rbytes_init(); 463 464 /* 465 * Default options 466 */ 467 mopts.malloc_abort = 1; 468 mopts.malloc_move = 1; 469 mopts.malloc_cache = MALLOC_DEFAULT_CACHE; 470 471 for (i = 0; i < 3; i++) { 472 switch (i) { 473 case 0: 474 j = readlink("/etc/malloc.conf", b, sizeof b - 1); 475 if (j <= 0) 476 continue; 477 b[j] = '\0'; 478 p = b; 479 break; 480 case 1: 481 if (issetugid() == 0) 482 p = getenv("MALLOC_OPTIONS"); 483 else 484 continue; 485 break; 486 case 2: 487 p = malloc_options; 488 break; 489 default: 490 p = NULL; 491 } 492 493 for (; p != NULL && *p != '\0'; p++) { 494 switch (*p) { 495 case '>': 496 mopts.malloc_cache <<= 1; 497 if (mopts.malloc_cache > MALLOC_MAXCACHE) 498 mopts.malloc_cache = MALLOC_MAXCACHE; 499 break; 500 case '<': 501 mopts.malloc_cache >>= 1; 502 break; 503 case 'a': 504 mopts.malloc_abort = 0; 505 break; 506 case 'A': 507 mopts.malloc_abort = 1; 508 break; 509 #ifdef MALLOC_STATS 510 case 'd': 511 mopts.malloc_stats = 0; 512 break; 513 case 'D': 514 mopts.malloc_stats = 1; 515 break; 516 #endif /* MALLOC_STATS */ 517 case 'f': 518 mopts.malloc_freeprot = 0; 519 break; 520 case 'F': 521 mopts.malloc_freeprot = 1; 522 break; 523 case 'g': 524 mopts.malloc_guard = 0; 525 break; 526 case 'G': 527 mopts.malloc_guard = MALLOC_PAGESIZE; 528 break; 529 case 'h': 530 mopts.malloc_hint = 0; 531 break; 532 case 'H': 533 mopts.malloc_hint = 1; 534 break; 535 case 'j': 536 mopts.malloc_junk = 0; 537 break; 538 case 'J': 539 mopts.malloc_junk = 1; 540 break; 541 case 'n': 542 case 'N': 543 break; 544 case 'p': 545 mopts.malloc_move = 0; 546 break; 547 case 'P': 548 mopts.malloc_move = 1; 549 break; 550 case 'r': 551 mopts.malloc_realloc = 0; 552 break; 553 case 'R': 554 mopts.malloc_realloc = 1; 555 break; 556 case 's': 557 mopts.malloc_freeprot = mopts.malloc_junk = 0; 558 mopts.malloc_guard = 0; 559 mopts.malloc_cache = MALLOC_DEFAULT_CACHE; 560 break; 561 case 'S': 562 mopts.malloc_freeprot = mopts.malloc_junk = 1; 563 mopts.malloc_guard = MALLOC_PAGESIZE; 564 mopts.malloc_cache = 0; 565 break; 566 case 'x': 567 mopts.malloc_xmalloc = 0; 568 break; 569 case 'X': 570 mopts.malloc_xmalloc = 1; 571 break; 572 case 'z': 573 mopts.malloc_zero = 0; 574 break; 575 case 'Z': 576 mopts.malloc_zero = 1; 577 break; 578 default: { 579 static const char q[] = "malloc() warning: " 580 "unknown char in MALLOC_OPTIONS\n"; 581 write(STDERR_FILENO, q, sizeof(q) - 1); 582 break; 583 } 584 } 585 } 586 } 587 588 /* 589 * We want junk in the entire allocation, and zero only in the part 590 * the user asked for. 591 */ 592 if (mopts.malloc_zero) 593 mopts.malloc_junk = 1; 594 595 #ifdef MALLOC_STATS 596 if (mopts.malloc_stats && (atexit(malloc_exit) == -1)) { 597 static const char q[] = "malloc() warning: atexit(2) failed." 598 " Will not be able to dump stats on exit\n"; 599 write(STDERR_FILENO, q, sizeof(q) - 1); 600 } 601 #endif /* MALLOC_STATS */ 602 603 while ((mopts.malloc_canary = arc4random()) == 0) 604 ; 605 606 /* 607 * Allocate dir_info with a guard page on either side. Also 608 * randomise offset inside the page at which the dir_info 609 * lies (subject to alignment by 1 << MALLOC_MINSHIFT) 610 */ 611 if ((p = MMAP(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2))) == MAP_FAILED) 612 return -1; 613 mprotect(p, MALLOC_PAGESIZE, PROT_NONE); 614 mprotect(p + MALLOC_PAGESIZE + DIR_INFO_RSZ, 615 MALLOC_PAGESIZE, PROT_NONE); 616 d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT; 617 d = (struct dir_info *)(p + MALLOC_PAGESIZE + 618 (arc4random_uniform(d_avail) << MALLOC_MINSHIFT)); 619 620 d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS; 621 regioninfo_size = d->regions_total * sizeof(struct region_info); 622 d->r = MMAP(regioninfo_size); 623 if (d->r == MAP_FAILED) { 624 wrterror("malloc init mmap failed", NULL); 625 d->regions_total = 0; 626 return 1; 627 } 628 for (i = 0; i <= MALLOC_MAXSHIFT; i++) { 629 LIST_INIT(&d->chunk_info_list[i]); 630 LIST_INIT(&d->chunk_dir[i]); 631 } 632 malloc_used += regioninfo_size; 633 d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d; 634 d->canary2 = ~d->canary1; 635 636 *dp = d; 637 638 /* 639 * Options have been set and will never be reset. 640 * Prevent further tampering with them. 641 */ 642 if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0) 643 mprotect(&malloc_readonly, sizeof(malloc_readonly), PROT_READ); 644 645 return 0; 646 } 647 648 static int 649 omalloc_grow(struct dir_info *d) 650 { 651 size_t newtotal; 652 size_t newsize; 653 size_t mask; 654 size_t i; 655 struct region_info *p; 656 657 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 ) 658 return 1; 659 660 newtotal = d->regions_total * 2; 661 newsize = newtotal * sizeof(struct region_info); 662 mask = newtotal - 1; 663 664 p = MMAP(newsize); 665 if (p == MAP_FAILED) 666 return 1; 667 668 malloc_used += newsize; 669 memset(p, 0, newsize); 670 STATS_ZERO(d->inserts); 671 STATS_ZERO(d->insert_collisions); 672 for (i = 0; i < d->regions_total; i++) { 673 void *q = d->r[i].p; 674 if (q != NULL) { 675 size_t index = hash(q) & mask; 676 STATS_INC(d->inserts); 677 while (p[index].p != NULL) { 678 index = (index - 1) & mask; 679 STATS_INC(d->insert_collisions); 680 } 681 p[index] = d->r[i]; 682 } 683 } 684 /* avoid pages containing meta info to end up in cache */ 685 if (munmap(d->r, d->regions_total * sizeof(struct region_info))) 686 wrterror("munmap", d->r); 687 else 688 malloc_used -= d->regions_total * sizeof(struct region_info); 689 d->regions_free = d->regions_free + d->regions_total; 690 d->regions_total = newtotal; 691 d->r = p; 692 return 0; 693 } 694 695 static struct chunk_info * 696 alloc_chunk_info(struct dir_info *d, int bits) 697 { 698 struct chunk_info *p; 699 size_t size, count; 700 701 if (bits == 0) 702 count = MALLOC_PAGESIZE / MALLOC_MINSIZE; 703 else 704 count = MALLOC_PAGESIZE >> bits; 705 706 size = howmany(count, MALLOC_BITS); 707 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short); 708 size = ALIGN(size); 709 710 if (LIST_EMPTY(&d->chunk_info_list[bits])) { 711 void *q; 712 int i; 713 714 q = MMAP(MALLOC_PAGESIZE); 715 if (q == MAP_FAILED) 716 return NULL; 717 malloc_used += MALLOC_PAGESIZE; 718 count = MALLOC_PAGESIZE / size; 719 for (i = 0; i < count; i++, q += size) 720 LIST_INSERT_HEAD(&d->chunk_info_list[bits], 721 (struct chunk_info *)q, entries); 722 } 723 p = LIST_FIRST(&d->chunk_info_list[bits]); 724 LIST_REMOVE(p, entries); 725 memset(p, 0, size); 726 p->canary = d->canary1; 727 return p; 728 } 729 730 731 /* 732 * The hashtable uses the assumption that p is never NULL. This holds since 733 * non-MAP_FIXED mappings with hint 0 start at BRKSIZ. 734 */ 735 static int 736 insert(struct dir_info *d, void *p, size_t sz, void *f) 737 { 738 size_t index; 739 size_t mask; 740 void *q; 741 742 if (d->regions_free * 4 < d->regions_total) { 743 if (omalloc_grow(d)) 744 return 1; 745 } 746 mask = d->regions_total - 1; 747 index = hash(p) & mask; 748 q = d->r[index].p; 749 STATS_INC(d->inserts); 750 while (q != NULL) { 751 index = (index - 1) & mask; 752 q = d->r[index].p; 753 STATS_INC(d->insert_collisions); 754 } 755 d->r[index].p = p; 756 d->r[index].size = sz; 757 #ifdef MALLOC_STATS 758 d->r[index].f = f; 759 #endif 760 d->regions_free--; 761 return 0; 762 } 763 764 static struct region_info * 765 find(struct dir_info *d, void *p) 766 { 767 size_t index; 768 size_t mask = d->regions_total - 1; 769 void *q, *r; 770 771 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 772 d->canary1 != ~d->canary2) 773 wrterror("internal struct corrupt", NULL); 774 p = MASK_POINTER(p); 775 index = hash(p) & mask; 776 r = d->r[index].p; 777 q = MASK_POINTER(r); 778 STATS_INC(d->finds); 779 while (q != p && r != NULL) { 780 index = (index - 1) & mask; 781 r = d->r[index].p; 782 q = MASK_POINTER(r); 783 STATS_INC(d->find_collisions); 784 } 785 return (q == p && r != NULL) ? &d->r[index] : NULL; 786 } 787 788 static void 789 delete(struct dir_info *d, struct region_info *ri) 790 { 791 /* algorithm R, Knuth Vol III section 6.4 */ 792 size_t mask = d->regions_total - 1; 793 size_t i, j, r; 794 795 if (d->regions_total & (d->regions_total - 1)) 796 wrterror("regions_total not 2^x", NULL); 797 d->regions_free++; 798 STATS_INC(g_pool->deletes); 799 800 i = ri - d->r; 801 for (;;) { 802 d->r[i].p = NULL; 803 d->r[i].size = 0; 804 j = i; 805 for (;;) { 806 i = (i - 1) & mask; 807 if (d->r[i].p == NULL) 808 return; 809 r = hash(d->r[i].p) & mask; 810 if ((i <= r && r < j) || (r < j && j < i) || 811 (j < i && i <= r)) 812 continue; 813 d->r[j] = d->r[i]; 814 STATS_INC(g_pool->delete_moves); 815 break; 816 } 817 818 } 819 } 820 821 /* 822 * Allocate a page of chunks 823 */ 824 static struct chunk_info * 825 omalloc_make_chunks(struct dir_info *d, int bits) 826 { 827 struct chunk_info *bp; 828 void *pp; 829 int i, k; 830 831 /* Allocate a new bucket */ 832 pp = map(d, MALLOC_PAGESIZE, 0); 833 if (pp == MAP_FAILED) 834 return NULL; 835 836 bp = alloc_chunk_info(d, bits); 837 if (bp == NULL) { 838 unmap(d, pp, MALLOC_PAGESIZE); 839 return NULL; 840 } 841 842 /* memory protect the page allocated in the malloc(0) case */ 843 if (bits == 0) { 844 bp->size = 0; 845 bp->shift = 1; 846 i = MALLOC_MINSIZE - 1; 847 while (i >>= 1) 848 bp->shift++; 849 bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift; 850 bp->page = pp; 851 852 k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE); 853 if (k < 0) { 854 unmap(d, pp, MALLOC_PAGESIZE); 855 LIST_INSERT_HEAD(&d->chunk_info_list[0], bp, entries); 856 return NULL; 857 } 858 } else { 859 bp->size = 1U << bits; 860 bp->shift = bits; 861 bp->total = bp->free = MALLOC_PAGESIZE >> bits; 862 bp->page = pp; 863 } 864 865 /* set all valid bits in the bitmap */ 866 k = bp->total; 867 i = 0; 868 869 /* Do a bunch at a time */ 870 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS) 871 bp->bits[i / MALLOC_BITS] = (u_short)~0U; 872 873 for (; i < k; i++) 874 bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS); 875 876 LIST_INSERT_HEAD(&d->chunk_dir[bits], bp, entries); 877 878 bits++; 879 if ((uintptr_t)pp & bits) 880 wrterror("pp & bits", pp); 881 882 insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp, NULL); 883 return bp; 884 } 885 886 887 /* 888 * Allocate a chunk 889 */ 890 static void * 891 malloc_bytes(struct dir_info *d, size_t size, void *f) 892 { 893 int i, j; 894 size_t k; 895 u_short u, *lp; 896 struct chunk_info *bp; 897 898 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 899 d->canary1 != ~d->canary2) 900 wrterror("internal struct corrupt", NULL); 901 /* Don't bother with anything less than this */ 902 /* unless we have a malloc(0) requests */ 903 if (size != 0 && size < MALLOC_MINSIZE) 904 size = MALLOC_MINSIZE; 905 906 /* Find the right bucket */ 907 if (size == 0) 908 j = 0; 909 else { 910 j = MALLOC_MINSHIFT; 911 i = (size - 1) >> (MALLOC_MINSHIFT - 1); 912 while (i >>= 1) 913 j++; 914 } 915 916 /* If it's empty, make a page more of that size chunks */ 917 if (LIST_EMPTY(&d->chunk_dir[j])) { 918 bp = omalloc_make_chunks(d, j); 919 if (bp == NULL) 920 return NULL; 921 } else 922 bp = LIST_FIRST(&d->chunk_dir[j]); 923 924 if (bp->canary != d->canary1) 925 wrterror("chunk info corrupted", NULL); 926 927 i = d->chunk_start; 928 if (bp->free > 1) 929 i += getrnibble(); 930 if (i >= bp->total) 931 i &= bp->total - 1; 932 for (;;) { 933 for (;;) { 934 lp = &bp->bits[i / MALLOC_BITS]; 935 if (!*lp) { 936 i += MALLOC_BITS; 937 i &= ~(MALLOC_BITS - 1); 938 if (i >= bp->total) 939 i = 0; 940 } else 941 break; 942 } 943 k = i % MALLOC_BITS; 944 u = 1 << k; 945 if (*lp & u) 946 break; 947 if (++i >= bp->total) 948 i = 0; 949 } 950 d->chunk_start += i + 1; 951 #ifdef MALLOC_STATS 952 if (i == 0) { 953 struct region_info *r = find(d, bp->page); 954 r->f = f; 955 } 956 #endif 957 958 *lp ^= u; 959 960 /* If there are no more free, remove from free-list */ 961 if (!--bp->free) 962 LIST_REMOVE(bp, entries); 963 964 /* Adjust to the real offset of that chunk */ 965 k += (lp - bp->bits) * MALLOC_BITS; 966 k <<= bp->shift; 967 968 if (mopts.malloc_junk && bp->size > 0) 969 memset((char *)bp->page + k, SOME_JUNK, bp->size); 970 return ((char *)bp->page + k); 971 } 972 973 974 /* 975 * Free a chunk, and possibly the page it's on, if the page becomes empty. 976 */ 977 static void 978 free_bytes(struct dir_info *d, struct region_info *r, void *ptr) 979 { 980 struct chunk_head *mp; 981 struct chunk_info *info; 982 int i; 983 984 info = (struct chunk_info *)r->size; 985 if (info->canary != d->canary1) 986 wrterror("chunk info corrupted", NULL); 987 988 /* Find the chunk number on the page */ 989 i = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift; 990 991 if ((uintptr_t)ptr & ((1U << (info->shift)) - 1)) { 992 wrterror("modified chunk-pointer", ptr); 993 return; 994 } 995 if (info->bits[i / MALLOC_BITS] & (1U << (i % MALLOC_BITS))) { 996 wrterror("chunk is already free", ptr); 997 return; 998 } 999 1000 info->bits[i / MALLOC_BITS] |= 1U << (i % MALLOC_BITS); 1001 info->free++; 1002 1003 if (info->size != 0) 1004 mp = d->chunk_dir + info->shift; 1005 else 1006 mp = d->chunk_dir; 1007 1008 if (info->free == 1) { 1009 /* Page became non-full */ 1010 LIST_INSERT_HEAD(mp, info, entries); 1011 return; 1012 } 1013 if (info->free != info->total) 1014 return; 1015 1016 LIST_REMOVE(info, entries); 1017 1018 if (info->size == 0 && !mopts.malloc_freeprot) 1019 mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE); 1020 unmap(d, info->page, MALLOC_PAGESIZE); 1021 1022 delete(d, r); 1023 if (info->size != 0) 1024 mp = &d->chunk_info_list[info->shift]; 1025 else 1026 mp = &d->chunk_info_list[0]; 1027 LIST_INSERT_HEAD(mp, info, entries); 1028 } 1029 1030 1031 1032 static void * 1033 omalloc(size_t sz, int zero_fill, void *f) 1034 { 1035 void *p; 1036 size_t psz; 1037 1038 if (sz > MALLOC_MAXCHUNK) { 1039 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1040 errno = ENOMEM; 1041 return NULL; 1042 } 1043 sz += mopts.malloc_guard; 1044 psz = PAGEROUND(sz); 1045 p = map(g_pool, psz, zero_fill); 1046 if (p == MAP_FAILED) { 1047 errno = ENOMEM; 1048 return NULL; 1049 } 1050 if (insert(g_pool, p, sz, f)) { 1051 unmap(g_pool, p, psz); 1052 errno = ENOMEM; 1053 return NULL; 1054 } 1055 if (mopts.malloc_guard) { 1056 if (mprotect((char *)p + psz - mopts.malloc_guard, 1057 mopts.malloc_guard, PROT_NONE)) 1058 wrterror("mprotect", NULL); 1059 malloc_guarded += mopts.malloc_guard; 1060 } 1061 1062 if (mopts.malloc_move && 1063 sz - mopts.malloc_guard < MALLOC_PAGESIZE - 1064 MALLOC_LEEWAY) { 1065 /* fill whole allocation */ 1066 if (mopts.malloc_junk) 1067 memset(p, SOME_JUNK, psz - mopts.malloc_guard); 1068 /* shift towards the end */ 1069 p = ((char *)p) + ((MALLOC_PAGESIZE - MALLOC_LEEWAY - 1070 (sz - mopts.malloc_guard)) & ~(MALLOC_MINSIZE-1)); 1071 /* fill zeros if needed and overwritten above */ 1072 if (zero_fill && mopts.malloc_junk) 1073 memset(p, 0, sz - mopts.malloc_guard); 1074 } else { 1075 if (mopts.malloc_junk) { 1076 if (zero_fill) 1077 memset((char *)p + sz - mopts.malloc_guard, 1078 SOME_JUNK, psz - sz); 1079 else 1080 memset(p, SOME_JUNK, 1081 psz - mopts.malloc_guard); 1082 } 1083 } 1084 1085 } else { 1086 /* takes care of SOME_JUNK */ 1087 p = malloc_bytes(g_pool, sz, f); 1088 if (zero_fill && p != NULL && sz > 0) 1089 memset(p, 0, sz); 1090 } 1091 1092 return p; 1093 } 1094 1095 /* 1096 * Common function for handling recursion. Only 1097 * print the error message once, to avoid making the problem 1098 * potentially worse. 1099 */ 1100 static void 1101 malloc_recurse(void) 1102 { 1103 static int noprint; 1104 1105 if (noprint == 0) { 1106 noprint = 1; 1107 wrterror("recursive call", NULL); 1108 } 1109 malloc_active--; 1110 _MALLOC_UNLOCK(); 1111 errno = EDEADLK; 1112 } 1113 1114 static int 1115 malloc_init(void) 1116 { 1117 if (omalloc_init(&g_pool)) { 1118 _MALLOC_UNLOCK(); 1119 if (mopts.malloc_xmalloc) 1120 wrterror("out of memory", NULL); 1121 errno = ENOMEM; 1122 return -1; 1123 } 1124 return 0; 1125 } 1126 1127 void * 1128 malloc(size_t size) 1129 { 1130 void *r; 1131 int saved_errno = errno; 1132 1133 _MALLOC_LOCK(); 1134 malloc_func = " in malloc():"; 1135 if (g_pool == NULL) { 1136 if (malloc_init() != 0) 1137 return NULL; 1138 } 1139 if (malloc_active++) { 1140 malloc_recurse(); 1141 return NULL; 1142 } 1143 r = omalloc(size, mopts.malloc_zero, CALLER); 1144 malloc_active--; 1145 _MALLOC_UNLOCK(); 1146 if (r == NULL && mopts.malloc_xmalloc) { 1147 wrterror("out of memory", NULL); 1148 errno = ENOMEM; 1149 } 1150 if (r != NULL) 1151 errno = saved_errno; 1152 return r; 1153 } 1154 1155 static void 1156 ofree(void *p) 1157 { 1158 struct region_info *r; 1159 size_t sz; 1160 1161 r = find(g_pool, p); 1162 if (r == NULL) { 1163 wrterror("bogus pointer (double free?)", p); 1164 return; 1165 } 1166 REALSIZE(sz, r); 1167 if (sz > MALLOC_MAXCHUNK) { 1168 if (sz - mopts.malloc_guard >= MALLOC_PAGESIZE - 1169 MALLOC_LEEWAY) { 1170 if (r->p != p) { 1171 wrterror("bogus pointer", p); 1172 return; 1173 } 1174 } else { 1175 #if notyetbecause_of_realloc 1176 /* shifted towards the end */ 1177 if (p != ((char *)r->p) + ((MALLOC_PAGESIZE - 1178 MALLOC_MINSIZE - sz - mopts.malloc_guard) & 1179 ~(MALLOC_MINSIZE-1))) { 1180 } 1181 #endif 1182 p = r->p; 1183 } 1184 if (mopts.malloc_guard) { 1185 if (sz < mopts.malloc_guard) 1186 wrterror("guard size", NULL); 1187 if (!mopts.malloc_freeprot) { 1188 if (mprotect((char *)p + PAGEROUND(sz) - 1189 mopts.malloc_guard, mopts.malloc_guard, 1190 PROT_READ | PROT_WRITE)) 1191 wrterror("mprotect", NULL); 1192 } 1193 malloc_guarded -= mopts.malloc_guard; 1194 } 1195 if (mopts.malloc_junk && !mopts.malloc_freeprot) 1196 memset(p, SOME_FREEJUNK, 1197 PAGEROUND(sz) - mopts.malloc_guard); 1198 unmap(g_pool, p, PAGEROUND(sz)); 1199 delete(g_pool, r); 1200 } else { 1201 void *tmp; 1202 int i; 1203 1204 if (mopts.malloc_junk && sz > 0) 1205 memset(p, SOME_FREEJUNK, sz); 1206 if (!mopts.malloc_freeprot) { 1207 i = getrnibble(); 1208 tmp = p; 1209 p = g_pool->delayed_chunks[i]; 1210 g_pool->delayed_chunks[i] = tmp; 1211 } 1212 if (p != NULL) { 1213 r = find(g_pool, p); 1214 if (r == NULL) { 1215 wrterror("bogus pointer (double free?)", p); 1216 return; 1217 } 1218 free_bytes(g_pool, r, p); 1219 } 1220 } 1221 } 1222 1223 void 1224 free(void *ptr) 1225 { 1226 int saved_errno = errno; 1227 1228 /* This is legal. */ 1229 if (ptr == NULL) 1230 return; 1231 1232 _MALLOC_LOCK(); 1233 malloc_func = " in free():"; 1234 if (g_pool == NULL) { 1235 _MALLOC_UNLOCK(); 1236 wrterror("free() called before allocation", NULL); 1237 return; 1238 } 1239 if (malloc_active++) { 1240 malloc_recurse(); 1241 return; 1242 } 1243 ofree(ptr); 1244 malloc_active--; 1245 _MALLOC_UNLOCK(); 1246 errno = saved_errno; 1247 } 1248 1249 1250 static void * 1251 orealloc(void *p, size_t newsz, void *f) 1252 { 1253 struct region_info *r; 1254 size_t oldsz, goldsz, gnewsz; 1255 void *q; 1256 1257 if (p == NULL) 1258 return omalloc(newsz, 0, f); 1259 1260 r = find(g_pool, p); 1261 if (r == NULL) { 1262 wrterror("bogus pointer (double free?)", p); 1263 return NULL; 1264 } 1265 if (newsz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1266 errno = ENOMEM; 1267 return NULL; 1268 } 1269 1270 REALSIZE(oldsz, r); 1271 goldsz = oldsz; 1272 if (oldsz > MALLOC_MAXCHUNK) { 1273 if (oldsz < mopts.malloc_guard) 1274 wrterror("guard size", NULL); 1275 oldsz -= mopts.malloc_guard; 1276 } 1277 1278 gnewsz = newsz; 1279 if (gnewsz > MALLOC_MAXCHUNK) 1280 gnewsz += mopts.malloc_guard; 1281 1282 if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK && p == r->p && 1283 !mopts.malloc_realloc) { 1284 size_t roldsz = PAGEROUND(goldsz); 1285 size_t rnewsz = PAGEROUND(gnewsz); 1286 1287 if (rnewsz > roldsz) { 1288 if (!mopts.malloc_guard) { 1289 void *hint = (char *)p + roldsz; 1290 size_t needed = rnewsz - roldsz; 1291 1292 STATS_INC(g_pool->cheap_realloc_tries); 1293 zapcacheregion(g_pool, hint, needed); 1294 q = MQUERY(hint, needed); 1295 if (q == hint) 1296 q = MMAPA(hint, needed); 1297 else 1298 q = MAP_FAILED; 1299 if (q == hint) { 1300 malloc_used += needed; 1301 if (mopts.malloc_junk) 1302 memset(q, SOME_JUNK, needed); 1303 r->size = newsz; 1304 STATS_SETF(r, f); 1305 STATS_INC(g_pool->cheap_reallocs); 1306 return p; 1307 } else if (q != MAP_FAILED) { 1308 if (munmap(q, needed)) 1309 wrterror("munmap", q); 1310 } 1311 } 1312 } else if (rnewsz < roldsz) { 1313 if (mopts.malloc_guard) { 1314 if (mprotect((char *)p + roldsz - 1315 mopts.malloc_guard, mopts.malloc_guard, 1316 PROT_READ | PROT_WRITE)) 1317 wrterror("mprotect", NULL); 1318 if (mprotect((char *)p + rnewsz - 1319 mopts.malloc_guard, mopts.malloc_guard, 1320 PROT_NONE)) 1321 wrterror("mprotect", NULL); 1322 } 1323 unmap(g_pool, (char *)p + rnewsz, roldsz - rnewsz); 1324 r->size = gnewsz; 1325 STATS_SETF(r, f); 1326 return p; 1327 } else { 1328 if (newsz > oldsz && mopts.malloc_junk) 1329 memset((char *)p + newsz, SOME_JUNK, 1330 rnewsz - mopts.malloc_guard - newsz); 1331 r->size = gnewsz; 1332 STATS_SETF(r, f); 1333 return p; 1334 } 1335 } 1336 if (newsz <= oldsz && newsz > oldsz / 2 && !mopts.malloc_realloc) { 1337 if (mopts.malloc_junk && newsz > 0) 1338 memset((char *)p + newsz, SOME_JUNK, oldsz - newsz); 1339 STATS_SETF(r, f); 1340 return p; 1341 } else if (newsz != oldsz || mopts.malloc_realloc) { 1342 q = omalloc(newsz, 0, f); 1343 if (q == NULL) 1344 return NULL; 1345 if (newsz != 0 && oldsz != 0) 1346 memcpy(q, p, oldsz < newsz ? oldsz : newsz); 1347 ofree(p); 1348 return q; 1349 } else { 1350 STATS_SETF(r, f); 1351 return p; 1352 } 1353 } 1354 1355 void * 1356 realloc(void *ptr, size_t size) 1357 { 1358 void *r; 1359 int saved_errno = errno; 1360 1361 _MALLOC_LOCK(); 1362 malloc_func = " in realloc():"; 1363 if (g_pool == NULL) { 1364 if (malloc_init() != 0) 1365 return NULL; 1366 } 1367 if (malloc_active++) { 1368 malloc_recurse(); 1369 return NULL; 1370 } 1371 r = orealloc(ptr, size, CALLER); 1372 1373 malloc_active--; 1374 _MALLOC_UNLOCK(); 1375 if (r == NULL && mopts.malloc_xmalloc) { 1376 wrterror("out of memory", NULL); 1377 errno = ENOMEM; 1378 } 1379 if (r != NULL) 1380 errno = saved_errno; 1381 return r; 1382 } 1383 1384 1385 #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4)) 1386 1387 void * 1388 calloc(size_t nmemb, size_t size) 1389 { 1390 void *r; 1391 int saved_errno = errno; 1392 1393 _MALLOC_LOCK(); 1394 malloc_func = " in calloc():"; 1395 if (g_pool == NULL) { 1396 if (malloc_init() != 0) 1397 return NULL; 1398 } 1399 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1400 nmemb > 0 && SIZE_MAX / nmemb < size) { 1401 _MALLOC_UNLOCK(); 1402 if (mopts.malloc_xmalloc) 1403 wrterror("out of memory", NULL); 1404 errno = ENOMEM; 1405 return NULL; 1406 } 1407 1408 if (malloc_active++) { 1409 malloc_recurse(); 1410 return NULL; 1411 } 1412 1413 size *= nmemb; 1414 r = omalloc(size, 1, CALLER); 1415 1416 malloc_active--; 1417 _MALLOC_UNLOCK(); 1418 if (r == NULL && mopts.malloc_xmalloc) { 1419 wrterror("out of memory", NULL); 1420 errno = ENOMEM; 1421 } 1422 if (r != NULL) 1423 errno = saved_errno; 1424 return r; 1425 } 1426 1427 static void * 1428 mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill) 1429 { 1430 void *p, *q; 1431 1432 if (alignment < MALLOC_PAGESIZE || alignment & (alignment - 1) != 0) { 1433 wrterror("mapalign bad alignment", NULL); 1434 return MAP_FAILED; 1435 } 1436 if (sz != PAGEROUND(sz)) { 1437 wrterror("mapalign round", NULL); 1438 return MAP_FAILED; 1439 } 1440 1441 /* Allocate sz + alignment bytes of memory, which must include a 1442 * subrange of size bytes that is properly aligned. Unmap the 1443 * other bytes, and then return that subrange. 1444 */ 1445 1446 /* We need sz + alignment to fit into a size_t. */ 1447 if (alignment > SIZE_MAX - sz) 1448 return MAP_FAILED; 1449 1450 p = map(d, sz + alignment, zero_fill); 1451 if (p == MAP_FAILED) 1452 return MAP_FAILED; 1453 q = (void *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1)); 1454 if (q != p) { 1455 if (munmap(p, q - p)) 1456 wrterror("munmap", p); 1457 } 1458 if (munmap(q + sz, alignment - (q - p))) 1459 wrterror("munmap", q + sz); 1460 malloc_used -= alignment; 1461 1462 return q; 1463 } 1464 1465 static void * 1466 omemalign(size_t alignment, size_t sz, int zero_fill, void *f) 1467 { 1468 size_t psz; 1469 void *p; 1470 1471 if (alignment <= MALLOC_PAGESIZE) { 1472 /* 1473 * max(size, alignment) is enough to assure the requested alignment, 1474 * since the allocator always allocates power-of-two blocks. 1475 */ 1476 if (sz < alignment) 1477 sz = alignment; 1478 return omalloc(sz, zero_fill, f); 1479 } 1480 1481 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1482 errno = ENOMEM; 1483 return NULL; 1484 } 1485 1486 sz += mopts.malloc_guard; 1487 psz = PAGEROUND(sz); 1488 1489 p = mapalign(g_pool, alignment, psz, zero_fill); 1490 if (p == NULL) { 1491 errno = ENOMEM; 1492 return NULL; 1493 } 1494 1495 if (insert(g_pool, p, sz, f)) { 1496 unmap(g_pool, p, psz); 1497 errno = ENOMEM; 1498 return NULL; 1499 } 1500 1501 if (mopts.malloc_guard) { 1502 if (mprotect((char *)p + psz - mopts.malloc_guard, 1503 mopts.malloc_guard, PROT_NONE)) 1504 wrterror("mprotect", NULL); 1505 malloc_guarded += mopts.malloc_guard; 1506 } 1507 1508 if (mopts.malloc_junk) { 1509 if (zero_fill) 1510 memset((char *)p + sz - mopts.malloc_guard, 1511 SOME_JUNK, psz - sz); 1512 else 1513 memset(p, SOME_JUNK, psz - mopts.malloc_guard); 1514 } 1515 1516 return p; 1517 } 1518 1519 int 1520 posix_memalign(void **memptr, size_t alignment, size_t size) 1521 { 1522 int res, saved_errno = errno; 1523 void *r; 1524 1525 /* Make sure that alignment is a large enough power of 2. */ 1526 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) 1527 return EINVAL; 1528 1529 _MALLOC_LOCK(); 1530 malloc_func = " in posix_memalign():"; 1531 if (g_pool == NULL) { 1532 if (malloc_init() != 0) 1533 goto err; 1534 } 1535 if (malloc_active++) { 1536 malloc_recurse(); 1537 goto err; 1538 } 1539 r = omemalign(alignment, size, mopts.malloc_zero, CALLER); 1540 malloc_active--; 1541 _MALLOC_UNLOCK(); 1542 if (r == NULL) { 1543 if (mopts.malloc_xmalloc) { 1544 wrterror("out of memory", NULL); 1545 errno = ENOMEM; 1546 } 1547 goto err; 1548 } 1549 errno = saved_errno; 1550 *memptr = r; 1551 return 0; 1552 1553 err: 1554 res = errno; 1555 errno = saved_errno; 1556 return res; 1557 } 1558 1559 #ifdef MALLOC_STATS 1560 1561 struct malloc_leak { 1562 void (*f)(); 1563 size_t total_size; 1564 int count; 1565 }; 1566 1567 struct leaknode { 1568 RB_ENTRY(leaknode) entry; 1569 struct malloc_leak d; 1570 }; 1571 1572 static int 1573 leakcmp(struct leaknode *e1, struct leaknode *e2) 1574 { 1575 return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f; 1576 } 1577 1578 static RB_HEAD(leaktree, leaknode) leakhead; 1579 RB_GENERATE_STATIC(leaktree, leaknode, entry, leakcmp) 1580 1581 static void 1582 putleakinfo(void *f, size_t sz, int cnt) 1583 { 1584 struct leaknode key, *p; 1585 static struct leaknode *page; 1586 static int used; 1587 1588 if (cnt == 0) 1589 return; 1590 1591 key.d.f = f; 1592 p = RB_FIND(leaktree, &leakhead, &key); 1593 if (p == NULL) { 1594 if (page == NULL || 1595 used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) { 1596 page = MMAP(MALLOC_PAGESIZE); 1597 if (page == MAP_FAILED) 1598 return; 1599 used = 0; 1600 } 1601 p = &page[used++]; 1602 p->d.f = f; 1603 p->d.total_size = sz * cnt; 1604 p->d.count = cnt; 1605 RB_INSERT(leaktree, &leakhead, p); 1606 } else { 1607 p->d.total_size += sz * cnt; 1608 p->d.count += cnt; 1609 } 1610 } 1611 1612 static struct malloc_leak *malloc_leaks; 1613 1614 static void 1615 dump_leaks(int fd) 1616 { 1617 struct leaknode *p; 1618 char buf[64]; 1619 int i = 0; 1620 1621 snprintf(buf, sizeof(buf), "Leak report\n"); 1622 write(fd, buf, strlen(buf)); 1623 snprintf(buf, sizeof(buf), " f sum # avg\n"); 1624 write(fd, buf, strlen(buf)); 1625 /* XXX only one page of summary */ 1626 if (malloc_leaks == NULL) 1627 malloc_leaks = MMAP(MALLOC_PAGESIZE); 1628 if (malloc_leaks != MAP_FAILED) 1629 memset(malloc_leaks, 0, MALLOC_PAGESIZE); 1630 RB_FOREACH(p, leaktree, &leakhead) { 1631 snprintf(buf, sizeof(buf), "%12p %7zu %6u %6zu\n", p->d.f, 1632 p->d.total_size, p->d.count, p->d.total_size / p->d.count); 1633 write(fd, buf, strlen(buf)); 1634 if (malloc_leaks == MAP_FAILED || 1635 i >= MALLOC_PAGESIZE / sizeof(struct malloc_leak)) 1636 continue; 1637 malloc_leaks[i].f = p->d.f; 1638 malloc_leaks[i].total_size = p->d.total_size; 1639 malloc_leaks[i].count = p->d.count; 1640 i++; 1641 } 1642 } 1643 1644 static void 1645 dump_chunk(int fd, struct chunk_info *p, void *f, int fromfreelist) 1646 { 1647 char buf[64]; 1648 1649 while (p != NULL) { 1650 snprintf(buf, sizeof(buf), "chunk %12p %12p %4d %d/%d\n", 1651 p->page, ((p->bits[0] & 1) ? NULL : f), 1652 p->size, p->free, p->total); 1653 write(fd, buf, strlen(buf)); 1654 if (!fromfreelist) { 1655 if (p->bits[0] & 1) 1656 putleakinfo(NULL, p->size, p->total - p->free); 1657 else { 1658 putleakinfo(f, p->size, 1); 1659 putleakinfo(NULL, p->size, 1660 p->total - p->free - 1); 1661 } 1662 break; 1663 } 1664 p = LIST_NEXT(p, entries); 1665 if (p != NULL) { 1666 snprintf(buf, sizeof(buf), " "); 1667 write(fd, buf, strlen(buf)); 1668 } 1669 } 1670 } 1671 1672 static void 1673 dump_free_chunk_info(int fd, struct dir_info *d) 1674 { 1675 char buf[64]; 1676 int i, count; 1677 1678 snprintf(buf, sizeof(buf), "Free chunk structs:\n"); 1679 write(fd, buf, strlen(buf)); 1680 for (i = 0; i <= MALLOC_MAXSHIFT; i++) { 1681 struct chunk_info *p; 1682 1683 count = 0; 1684 LIST_FOREACH(p, &d->chunk_info_list[i], entries) 1685 count++; 1686 p = LIST_FIRST(&d->chunk_dir[i]); 1687 if (p == NULL && count == 0) 1688 continue; 1689 snprintf(buf, sizeof(buf), "%2d) %3d ", i, count); 1690 write(fd, buf, strlen(buf)); 1691 if (p != NULL) 1692 dump_chunk(fd, p, NULL, 1); 1693 else 1694 write(fd, "\n", 1); 1695 } 1696 1697 } 1698 1699 static void 1700 dump_free_page_info(int fd, struct dir_info *d) 1701 { 1702 char buf[64]; 1703 int i; 1704 1705 snprintf(buf, sizeof(buf), "Free pages cached: %zu\n", 1706 d->free_regions_size); 1707 write(fd, buf, strlen(buf)); 1708 for (i = 0; i < mopts.malloc_cache; i++) { 1709 if (d->free_regions[i].p != NULL) { 1710 snprintf(buf, sizeof(buf), "%2d) ", i); 1711 write(fd, buf, strlen(buf)); 1712 snprintf(buf, sizeof(buf), "free at %p: %zu\n", 1713 d->free_regions[i].p, d->free_regions[i].size); 1714 write(fd, buf, strlen(buf)); 1715 } 1716 } 1717 } 1718 1719 static void 1720 malloc_dump1(int fd, struct dir_info *d) 1721 { 1722 char buf[64]; 1723 size_t i, realsize; 1724 1725 snprintf(buf, sizeof(buf), "Malloc dir of %s at %p\n", __progname, d); 1726 write(fd, buf, strlen(buf)); 1727 if (d == NULL) 1728 return; 1729 snprintf(buf, sizeof(buf), "Region slots free %zu/%zu\n", 1730 d->regions_free, d->regions_total); 1731 write(fd, buf, strlen(buf)); 1732 snprintf(buf, sizeof(buf), "Finds %zu/%zu\n", d->finds, 1733 d->find_collisions); 1734 write(fd, buf, strlen(buf)); 1735 snprintf(buf, sizeof(buf), "Inserts %zu/%zu\n", d->inserts, 1736 d->insert_collisions); 1737 write(fd, buf, strlen(buf)); 1738 snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes, 1739 d->delete_moves); 1740 write(fd, buf, strlen(buf)); 1741 snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n", 1742 d->cheap_reallocs, d->cheap_realloc_tries); 1743 write(fd, buf, strlen(buf)); 1744 dump_free_chunk_info(fd, d); 1745 dump_free_page_info(fd, d); 1746 snprintf(buf, sizeof(buf), 1747 "slot) hash d type page f size [free/n]\n"); 1748 write(fd, buf, strlen(buf)); 1749 for (i = 0; i < d->regions_total; i++) { 1750 if (d->r[i].p != NULL) { 1751 size_t h = hash(d->r[i].p) & 1752 (d->regions_total - 1); 1753 snprintf(buf, sizeof(buf), "%4zx) #%4zx %zd ", 1754 i, h, h - i); 1755 write(fd, buf, strlen(buf)); 1756 REALSIZE(realsize, &d->r[i]); 1757 if (realsize > MALLOC_MAXCHUNK) { 1758 putleakinfo(d->r[i].f, realsize, 1); 1759 snprintf(buf, sizeof(buf), 1760 "pages %12p %12p %zu\n", d->r[i].p, 1761 d->r[i].f, realsize); 1762 write(fd, buf, strlen(buf)); 1763 } else 1764 dump_chunk(fd, 1765 (struct chunk_info *)d->r[i].size, 1766 d->r[i].f, 0); 1767 } 1768 } 1769 snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used); 1770 write(fd, buf, strlen(buf)); 1771 snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded); 1772 write(fd, buf, strlen(buf)); 1773 dump_leaks(fd); 1774 write(fd, "\n", 1); 1775 } 1776 1777 void 1778 malloc_dump(int fd) 1779 { 1780 int i; 1781 void *p; 1782 struct region_info *r; 1783 int saved_errno = errno; 1784 1785 for (i = 0; i <= MALLOC_DELAYED_CHUNKS; i++) { 1786 p = g_pool->delayed_chunks[i]; 1787 if (p == NULL) 1788 continue; 1789 r = find(g_pool, p); 1790 if (r == NULL) 1791 wrterror("bogus pointer in malloc_dump", p); 1792 free_bytes(g_pool, r, p); 1793 g_pool->delayed_chunks[i] = NULL; 1794 } 1795 /* XXX leak when run multiple times */ 1796 RB_INIT(&leakhead); 1797 malloc_dump1(fd, g_pool); 1798 errno = saved_errno; 1799 } 1800 1801 static void 1802 malloc_exit(void) 1803 { 1804 static const char q[] = "malloc() warning: Couldn't dump stats\n"; 1805 int save_errno = errno, fd; 1806 1807 fd = open("malloc.out", O_RDWR|O_APPEND); 1808 if (fd != -1) { 1809 malloc_dump(fd); 1810 close(fd); 1811 } else 1812 write(STDERR_FILENO, q, sizeof(q) - 1); 1813 errno = save_errno; 1814 } 1815 1816 #endif /* MALLOC_STATS */ 1817