1 /* $OpenBSD: malloc.c,v 1.228 2017/07/10 09:44:16 otto Exp $ */ 2 /* 3 * Copyright (c) 2008, 2010, 2011, 2016 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 /* #define MALLOC_STATS */ 27 28 #include <sys/types.h> 29 #include <sys/param.h> /* PAGE_SHIFT ALIGN */ 30 #include <sys/queue.h> 31 #include <sys/mman.h> 32 #include <sys/uio.h> 33 #include <errno.h> 34 #include <stdarg.h> 35 #include <stdint.h> 36 #include <stdlib.h> 37 #include <string.h> 38 #include <stdio.h> 39 #include <unistd.h> 40 41 #ifdef MALLOC_STATS 42 #include <sys/tree.h> 43 #include <fcntl.h> 44 #endif 45 46 #include "thread_private.h" 47 #include <tib.h> 48 49 #if defined(__mips64__) 50 #define MALLOC_PAGESHIFT (14U) 51 #else 52 #define MALLOC_PAGESHIFT (PAGE_SHIFT) 53 #endif 54 55 #define MALLOC_MINSHIFT 4 56 #define MALLOC_MAXSHIFT (MALLOC_PAGESHIFT - 1) 57 #define MALLOC_PAGESIZE (1UL << MALLOC_PAGESHIFT) 58 #define MALLOC_MINSIZE (1UL << MALLOC_MINSHIFT) 59 #define MALLOC_PAGEMASK (MALLOC_PAGESIZE - 1) 60 #define MASK_POINTER(p) ((void *)(((uintptr_t)(p)) & ~MALLOC_PAGEMASK)) 61 62 #define MALLOC_MAXCHUNK (1 << MALLOC_MAXSHIFT) 63 #define MALLOC_MAXCACHE 256 64 #define MALLOC_DELAYED_CHUNK_MASK 15 65 #define MALLOC_INITIAL_REGIONS 512 66 #define MALLOC_DEFAULT_CACHE 64 67 #define MALLOC_CHUNK_LISTS 4 68 #define CHUNK_CHECK_LENGTH 32 69 70 /* 71 * We move allocations between half a page and a whole page towards the end, 72 * subject to alignment constraints. This is the extra headroom we allow. 73 * Set to zero to be the most strict. 74 */ 75 #define MALLOC_LEEWAY 0 76 #define MALLOC_MOVE_COND(sz) ((sz) - mopts.malloc_guard < \ 77 MALLOC_PAGESIZE - MALLOC_LEEWAY) 78 #define MALLOC_MOVE(p, sz) (((char *)(p)) + \ 79 ((MALLOC_PAGESIZE - MALLOC_LEEWAY - \ 80 ((sz) - mopts.malloc_guard)) & \ 81 ~(MALLOC_MINSIZE - 1))) 82 83 #define PAGEROUND(x) (((x) + (MALLOC_PAGEMASK)) & ~MALLOC_PAGEMASK) 84 85 /* 86 * What to use for Junk. This is the byte value we use to fill with 87 * when the 'J' option is enabled. Use SOME_JUNK right after alloc, 88 * and SOME_FREEJUNK right before free. 89 */ 90 #define SOME_JUNK 0xdb /* deadbeef */ 91 #define SOME_FREEJUNK 0xdf /* dead, free */ 92 93 #define MMAP(sz) mmap(NULL, (sz), PROT_READ | PROT_WRITE, \ 94 MAP_ANON | MAP_PRIVATE, -1, 0) 95 96 #define MMAPA(a,sz) mmap((a), (sz), PROT_READ | PROT_WRITE, \ 97 MAP_ANON | MAP_PRIVATE, -1, 0) 98 99 #define MQUERY(a, sz) mquery((a), (sz), PROT_READ | PROT_WRITE, \ 100 MAP_ANON | MAP_PRIVATE | MAP_FIXED, -1, 0) 101 102 struct region_info { 103 void *p; /* page; low bits used to mark chunks */ 104 uintptr_t size; /* size for pages, or chunk_info pointer */ 105 #ifdef MALLOC_STATS 106 void *f; /* where allocated from */ 107 #endif 108 }; 109 110 LIST_HEAD(chunk_head, chunk_info); 111 112 struct dir_info { 113 u_int32_t canary1; 114 int active; /* status of malloc */ 115 struct region_info *r; /* region slots */ 116 size_t regions_total; /* number of region slots */ 117 size_t regions_free; /* number of free slots */ 118 /* lists of free chunk info structs */ 119 struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1]; 120 /* lists of chunks with free slots */ 121 struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS]; 122 size_t free_regions_size; /* free pages cached */ 123 /* free pages cache */ 124 struct region_info free_regions[MALLOC_MAXCACHE]; 125 /* delayed free chunk slots */ 126 void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1]; 127 size_t rbytesused; /* random bytes used */ 128 char *func; /* current function */ 129 int mutex; 130 u_char rbytes[32]; /* random bytes */ 131 u_short chunk_start; 132 #ifdef MALLOC_STATS 133 size_t inserts; 134 size_t insert_collisions; 135 size_t finds; 136 size_t find_collisions; 137 size_t deletes; 138 size_t delete_moves; 139 size_t cheap_realloc_tries; 140 size_t cheap_reallocs; 141 size_t malloc_used; /* bytes allocated */ 142 size_t malloc_guarded; /* bytes used for guards */ 143 #define STATS_ADD(x,y) ((x) += (y)) 144 #define STATS_SUB(x,y) ((x) -= (y)) 145 #define STATS_INC(x) ((x)++) 146 #define STATS_ZERO(x) ((x) = 0) 147 #define STATS_SETF(x,y) ((x)->f = (y)) 148 #else 149 #define STATS_ADD(x,y) /* nothing */ 150 #define STATS_SUB(x,y) /* nothing */ 151 #define STATS_INC(x) /* nothing */ 152 #define STATS_ZERO(x) /* nothing */ 153 #define STATS_SETF(x,y) /* nothing */ 154 #endif /* MALLOC_STATS */ 155 u_int32_t canary2; 156 }; 157 #define DIR_INFO_RSZ ((sizeof(struct dir_info) + MALLOC_PAGEMASK) & \ 158 ~MALLOC_PAGEMASK) 159 160 /* 161 * This structure describes a page worth of chunks. 162 * 163 * How many bits per u_short in the bitmap 164 */ 165 #define MALLOC_BITS (NBBY * sizeof(u_short)) 166 struct chunk_info { 167 LIST_ENTRY(chunk_info) entries; 168 void *page; /* pointer to the page */ 169 u_int32_t canary; 170 u_short size; /* size of this page's chunks */ 171 u_short shift; /* how far to shift for this size */ 172 u_short free; /* how many free chunks */ 173 u_short total; /* how many chunks */ 174 u_short offset; /* requested size table offset */ 175 /* which chunks are free */ 176 u_short bits[1]; 177 }; 178 179 struct malloc_readonly { 180 struct dir_info *malloc_pool[_MALLOC_MUTEXES]; /* Main bookkeeping information */ 181 int malloc_mt; /* multi-threaded mode? */ 182 int malloc_freenow; /* Free quickly - disable chunk rnd */ 183 int malloc_freeunmap; /* mprotect free pages PROT_NONE? */ 184 int malloc_junk; /* junk fill? */ 185 int malloc_realloc; /* always realloc? */ 186 int malloc_xmalloc; /* xmalloc behaviour? */ 187 int chunk_canaries; /* use canaries after chunks? */ 188 int internal_funcs; /* use better recallocarray/freezero? */ 189 u_int malloc_cache; /* free pages we cache */ 190 size_t malloc_guard; /* use guard pages after allocations? */ 191 #ifdef MALLOC_STATS 192 int malloc_stats; /* dump statistics at end */ 193 #endif 194 u_int32_t malloc_canary; /* Matched against ones in malloc_pool */ 195 }; 196 197 /* This object is mapped PROT_READ after initialisation to prevent tampering */ 198 static union { 199 struct malloc_readonly mopts; 200 u_char _pad[MALLOC_PAGESIZE]; 201 } malloc_readonly __attribute__((aligned(MALLOC_PAGESIZE))); 202 #define mopts malloc_readonly.mopts 203 204 char *malloc_options; /* compile-time options */ 205 206 static u_char getrbyte(struct dir_info *d); 207 static __dead void wrterror(struct dir_info *d, char *msg, ...) 208 __attribute__((__format__ (printf, 2, 3))); 209 static void fill_canary(char *ptr, size_t sz, size_t allocated); 210 211 #ifdef MALLOC_STATS 212 void malloc_dump(int, int, struct dir_info *); 213 PROTO_NORMAL(malloc_dump); 214 void malloc_gdump(int); 215 PROTO_NORMAL(malloc_gdump); 216 static void malloc_exit(void); 217 #define CALLER __builtin_return_address(0) 218 #else 219 #define CALLER NULL 220 #endif 221 222 /* low bits of r->p determine size: 0 means >= page size and r->size holding 223 * real size, otherwise low bits are a shift count, or 1 for malloc(0) 224 */ 225 #define REALSIZE(sz, r) \ 226 (sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \ 227 (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1)))) 228 229 static inline void 230 _MALLOC_LEAVE(struct dir_info *d) 231 { 232 if (mopts.malloc_mt) { 233 d->active--; 234 _MALLOC_UNLOCK(d->mutex); 235 } 236 } 237 238 static inline void 239 _MALLOC_ENTER(struct dir_info *d) 240 { 241 if (mopts.malloc_mt) { 242 _MALLOC_LOCK(d->mutex); 243 d->active++; 244 } 245 } 246 247 static inline size_t 248 hash(void *p) 249 { 250 size_t sum; 251 uintptr_t u; 252 253 u = (uintptr_t)p >> MALLOC_PAGESHIFT; 254 sum = u; 255 sum = (sum << 7) - sum + (u >> 16); 256 #ifdef __LP64__ 257 sum = (sum << 7) - sum + (u >> 32); 258 sum = (sum << 7) - sum + (u >> 48); 259 #endif 260 return sum; 261 } 262 263 static inline 264 struct dir_info *getpool(void) 265 { 266 if (!mopts.malloc_mt) 267 return mopts.malloc_pool[0]; 268 else 269 return mopts.malloc_pool[TIB_GET()->tib_tid & 270 (_MALLOC_MUTEXES - 1)]; 271 } 272 273 static __dead void 274 wrterror(struct dir_info *d, char *msg, ...) 275 { 276 struct iovec iov[3]; 277 char pidbuf[80]; 278 char buf[80]; 279 int saved_errno = errno; 280 va_list ap; 281 282 iov[0].iov_base = pidbuf; 283 snprintf(pidbuf, sizeof(pidbuf), "%s(%d) in %s(): ", __progname, 284 getpid(), (d != NULL && d->func) ? d->func : "unknown"); 285 iov[0].iov_len = strlen(pidbuf); 286 iov[1].iov_base = buf; 287 va_start(ap, msg); 288 vsnprintf(buf, sizeof(buf), msg, ap); 289 va_end(ap); 290 iov[1].iov_len = strlen(buf); 291 iov[2].iov_base = "\n"; 292 iov[2].iov_len = 1; 293 writev(STDERR_FILENO, iov, 3); 294 295 #ifdef MALLOC_STATS 296 if (mopts.malloc_stats) { 297 int i; 298 299 for (i = 0; i < _MALLOC_MUTEXES; i++) 300 malloc_dump(STDERR_FILENO, i, mopts.malloc_pool[i]); 301 } 302 #endif /* MALLOC_STATS */ 303 304 errno = saved_errno; 305 306 abort(); 307 } 308 309 static void 310 rbytes_init(struct dir_info *d) 311 { 312 arc4random_buf(d->rbytes, sizeof(d->rbytes)); 313 /* add 1 to account for using d->rbytes[0] */ 314 d->rbytesused = 1 + d->rbytes[0] % (sizeof(d->rbytes) / 2); 315 } 316 317 static inline u_char 318 getrbyte(struct dir_info *d) 319 { 320 u_char x; 321 322 if (d->rbytesused >= sizeof(d->rbytes)) 323 rbytes_init(d); 324 x = d->rbytes[d->rbytesused++]; 325 return x; 326 } 327 328 /* 329 * Cache maintenance. We keep at most malloc_cache pages cached. 330 * If the cache is becoming full, unmap pages in the cache for real, 331 * and then add the region to the cache 332 * Opposed to the regular region data structure, the sizes in the 333 * cache are in MALLOC_PAGESIZE units. 334 */ 335 static void 336 unmap(struct dir_info *d, void *p, size_t sz, int clear) 337 { 338 size_t psz = sz >> MALLOC_PAGESHIFT; 339 size_t rsz, tounmap; 340 struct region_info *r; 341 u_int i, offset; 342 343 if (sz != PAGEROUND(sz)) 344 wrterror(d, "munmap round"); 345 346 rsz = mopts.malloc_cache - d->free_regions_size; 347 348 /* 349 * normally the cache holds recently freed regions, but if the region 350 * to unmap is larger than the cache size or we're clearing and the 351 * cache is full, just munmap 352 */ 353 if (psz > mopts.malloc_cache || (clear && rsz == 0)) { 354 i = munmap(p, sz); 355 if (i) 356 wrterror(d, "munmap %p", p); 357 STATS_SUB(d->malloc_used, sz); 358 return; 359 } 360 tounmap = 0; 361 if (psz > rsz) 362 tounmap = psz - rsz; 363 offset = getrbyte(d); 364 for (i = 0; tounmap > 0 && i < mopts.malloc_cache; i++) { 365 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 366 if (r->p != NULL) { 367 rsz = r->size << MALLOC_PAGESHIFT; 368 if (munmap(r->p, rsz)) 369 wrterror(d, "munmap %p", r->p); 370 r->p = NULL; 371 if (tounmap > r->size) 372 tounmap -= r->size; 373 else 374 tounmap = 0; 375 d->free_regions_size -= r->size; 376 r->size = 0; 377 STATS_SUB(d->malloc_used, rsz); 378 } 379 } 380 if (tounmap > 0) 381 wrterror(d, "malloc cache underflow"); 382 for (i = 0; i < mopts.malloc_cache; i++) { 383 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 384 if (r->p == NULL) { 385 if (clear) 386 memset(p, 0, sz - mopts.malloc_guard); 387 if (mopts.malloc_junk && !mopts.malloc_freeunmap) { 388 size_t amt = mopts.malloc_junk == 1 ? 389 MALLOC_MAXCHUNK : sz; 390 memset(p, SOME_FREEJUNK, amt); 391 } 392 if (mopts.malloc_freeunmap) 393 mprotect(p, sz, PROT_NONE); 394 r->p = p; 395 r->size = psz; 396 d->free_regions_size += psz; 397 break; 398 } 399 } 400 if (i == mopts.malloc_cache) 401 wrterror(d, "malloc free slot lost"); 402 if (d->free_regions_size > mopts.malloc_cache) 403 wrterror(d, "malloc cache overflow"); 404 } 405 406 static void 407 zapcacheregion(struct dir_info *d, void *p, size_t len) 408 { 409 u_int i; 410 struct region_info *r; 411 size_t rsz; 412 413 for (i = 0; i < mopts.malloc_cache; i++) { 414 r = &d->free_regions[i]; 415 if (r->p >= p && r->p <= (void *)((char *)p + len)) { 416 rsz = r->size << MALLOC_PAGESHIFT; 417 if (munmap(r->p, rsz)) 418 wrterror(d, "munmap %p", r->p); 419 r->p = NULL; 420 d->free_regions_size -= r->size; 421 r->size = 0; 422 STATS_SUB(d->malloc_used, rsz); 423 } 424 } 425 } 426 427 static void * 428 map(struct dir_info *d, void *hint, size_t sz, int zero_fill) 429 { 430 size_t psz = sz >> MALLOC_PAGESHIFT; 431 struct region_info *r, *big = NULL; 432 u_int i, offset; 433 void *p; 434 435 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 436 d->canary1 != ~d->canary2) 437 wrterror(d, "internal struct corrupt"); 438 if (sz != PAGEROUND(sz)) 439 wrterror(d, "map round"); 440 441 if (!hint && psz > d->free_regions_size) { 442 _MALLOC_LEAVE(d); 443 p = MMAP(sz); 444 _MALLOC_ENTER(d); 445 if (p != MAP_FAILED) 446 STATS_ADD(d->malloc_used, sz); 447 /* zero fill not needed */ 448 return p; 449 } 450 offset = getrbyte(d); 451 for (i = 0; i < mopts.malloc_cache; i++) { 452 r = &d->free_regions[(i + offset) & (mopts.malloc_cache - 1)]; 453 if (r->p != NULL) { 454 if (hint && r->p != hint) 455 continue; 456 if (r->size == psz) { 457 p = r->p; 458 r->p = NULL; 459 r->size = 0; 460 d->free_regions_size -= psz; 461 if (mopts.malloc_freeunmap) 462 mprotect(p, sz, PROT_READ | PROT_WRITE); 463 if (zero_fill) 464 memset(p, 0, sz); 465 else if (mopts.malloc_junk == 2 && 466 mopts.malloc_freeunmap) 467 memset(p, SOME_FREEJUNK, sz); 468 return p; 469 } else if (r->size > psz) 470 big = r; 471 } 472 } 473 if (big != NULL) { 474 r = big; 475 p = r->p; 476 r->p = (char *)r->p + (psz << MALLOC_PAGESHIFT); 477 if (mopts.malloc_freeunmap) 478 mprotect(p, sz, PROT_READ | PROT_WRITE); 479 r->size -= psz; 480 d->free_regions_size -= psz; 481 if (zero_fill) 482 memset(p, 0, sz); 483 else if (mopts.malloc_junk == 2 && mopts.malloc_freeunmap) 484 memset(p, SOME_FREEJUNK, sz); 485 return p; 486 } 487 if (hint) 488 return MAP_FAILED; 489 if (d->free_regions_size > mopts.malloc_cache) 490 wrterror(d, "malloc cache"); 491 _MALLOC_LEAVE(d); 492 p = MMAP(sz); 493 _MALLOC_ENTER(d); 494 if (p != MAP_FAILED) 495 STATS_ADD(d->malloc_used, sz); 496 /* zero fill not needed */ 497 return p; 498 } 499 500 static void 501 omalloc_parseopt(char opt) 502 { 503 switch (opt) { 504 case '>': 505 mopts.malloc_cache <<= 1; 506 if (mopts.malloc_cache > MALLOC_MAXCACHE) 507 mopts.malloc_cache = MALLOC_MAXCACHE; 508 break; 509 case '<': 510 mopts.malloc_cache >>= 1; 511 break; 512 case 'c': 513 mopts.chunk_canaries = 0; 514 break; 515 case 'C': 516 mopts.chunk_canaries = 1; 517 break; 518 #ifdef MALLOC_STATS 519 case 'd': 520 mopts.malloc_stats = 0; 521 break; 522 case 'D': 523 mopts.malloc_stats = 1; 524 break; 525 #endif /* MALLOC_STATS */ 526 case 'f': 527 mopts.malloc_freenow = 0; 528 mopts.malloc_freeunmap = 0; 529 break; 530 case 'F': 531 mopts.malloc_freenow = 1; 532 mopts.malloc_freeunmap = 1; 533 break; 534 case 'g': 535 mopts.malloc_guard = 0; 536 break; 537 case 'G': 538 mopts.malloc_guard = MALLOC_PAGESIZE; 539 break; 540 case 'j': 541 if (mopts.malloc_junk > 0) 542 mopts.malloc_junk--; 543 break; 544 case 'J': 545 if (mopts.malloc_junk < 2) 546 mopts.malloc_junk++; 547 break; 548 case 'r': 549 mopts.malloc_realloc = 0; 550 break; 551 case 'R': 552 mopts.malloc_realloc = 1; 553 break; 554 case 'u': 555 mopts.malloc_freeunmap = 0; 556 break; 557 case 'U': 558 mopts.malloc_freeunmap = 1; 559 break; 560 case 'x': 561 mopts.malloc_xmalloc = 0; 562 break; 563 case 'X': 564 mopts.malloc_xmalloc = 1; 565 break; 566 default: { 567 static const char q[] = "malloc() warning: " 568 "unknown char in MALLOC_OPTIONS\n"; 569 write(STDERR_FILENO, q, sizeof(q) - 1); 570 break; 571 } 572 } 573 } 574 575 static void 576 omalloc_init(void) 577 { 578 char *p, *q, b[64]; 579 int i, j; 580 581 /* 582 * Default options 583 */ 584 mopts.malloc_junk = 1; 585 mopts.malloc_cache = MALLOC_DEFAULT_CACHE; 586 587 for (i = 0; i < 3; i++) { 588 switch (i) { 589 case 0: 590 j = readlink("/etc/malloc.conf", b, sizeof b - 1); 591 if (j <= 0) 592 continue; 593 b[j] = '\0'; 594 p = b; 595 break; 596 case 1: 597 if (issetugid() == 0) 598 p = getenv("MALLOC_OPTIONS"); 599 else 600 continue; 601 break; 602 case 2: 603 p = malloc_options; 604 break; 605 default: 606 p = NULL; 607 } 608 609 for (; p != NULL && *p != '\0'; p++) { 610 switch (*p) { 611 case 'S': 612 for (q = "CGJ"; *q != '\0'; q++) 613 omalloc_parseopt(*q); 614 mopts.malloc_cache = 0; 615 break; 616 case 's': 617 for (q = "cgj"; *q != '\0'; q++) 618 omalloc_parseopt(*q); 619 mopts.malloc_cache = MALLOC_DEFAULT_CACHE; 620 break; 621 default: 622 omalloc_parseopt(*p); 623 break; 624 } 625 } 626 } 627 628 #ifdef MALLOC_STATS 629 if (mopts.malloc_stats && (atexit(malloc_exit) == -1)) { 630 static const char q[] = "malloc() warning: atexit(2) failed." 631 " Will not be able to dump stats on exit\n"; 632 write(STDERR_FILENO, q, sizeof(q) - 1); 633 } 634 #endif /* MALLOC_STATS */ 635 636 while ((mopts.malloc_canary = arc4random()) == 0) 637 ; 638 } 639 640 /* 641 * Initialize a dir_info, which should have been cleared by caller 642 */ 643 static void 644 omalloc_poolinit(struct dir_info **dp) 645 { 646 void *p; 647 size_t d_avail, regioninfo_size; 648 struct dir_info *d; 649 int i, j; 650 651 /* 652 * Allocate dir_info with a guard page on either side. Also 653 * randomise offset inside the page at which the dir_info 654 * lies (subject to alignment by 1 << MALLOC_MINSHIFT) 655 */ 656 if ((p = MMAP(DIR_INFO_RSZ + (MALLOC_PAGESIZE * 2))) == MAP_FAILED) 657 wrterror(NULL, "malloc init mmap failed"); 658 mprotect(p, MALLOC_PAGESIZE, PROT_NONE); 659 mprotect((char *)p + MALLOC_PAGESIZE + DIR_INFO_RSZ, 660 MALLOC_PAGESIZE, PROT_NONE); 661 d_avail = (DIR_INFO_RSZ - sizeof(*d)) >> MALLOC_MINSHIFT; 662 d = (struct dir_info *)((char *)p + MALLOC_PAGESIZE + 663 (arc4random_uniform(d_avail) << MALLOC_MINSHIFT)); 664 665 rbytes_init(d); 666 d->regions_free = d->regions_total = MALLOC_INITIAL_REGIONS; 667 regioninfo_size = d->regions_total * sizeof(struct region_info); 668 d->r = MMAP(regioninfo_size); 669 if (d->r == MAP_FAILED) { 670 d->regions_total = 0; 671 wrterror(NULL, "malloc init mmap failed"); 672 } 673 for (i = 0; i <= MALLOC_MAXSHIFT; i++) { 674 LIST_INIT(&d->chunk_info_list[i]); 675 for (j = 0; j < MALLOC_CHUNK_LISTS; j++) 676 LIST_INIT(&d->chunk_dir[i][j]); 677 } 678 STATS_ADD(d->malloc_used, regioninfo_size); 679 d->canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d; 680 d->canary2 = ~d->canary1; 681 682 *dp = d; 683 } 684 685 static int 686 omalloc_grow(struct dir_info *d) 687 { 688 size_t newtotal; 689 size_t newsize; 690 size_t mask; 691 size_t i; 692 struct region_info *p; 693 694 if (d->regions_total > SIZE_MAX / sizeof(struct region_info) / 2 ) 695 return 1; 696 697 newtotal = d->regions_total * 2; 698 newsize = newtotal * sizeof(struct region_info); 699 mask = newtotal - 1; 700 701 p = MMAP(newsize); 702 if (p == MAP_FAILED) 703 return 1; 704 705 STATS_ADD(d->malloc_used, newsize); 706 STATS_ZERO(d->inserts); 707 STATS_ZERO(d->insert_collisions); 708 for (i = 0; i < d->regions_total; i++) { 709 void *q = d->r[i].p; 710 if (q != NULL) { 711 size_t index = hash(q) & mask; 712 STATS_INC(d->inserts); 713 while (p[index].p != NULL) { 714 index = (index - 1) & mask; 715 STATS_INC(d->insert_collisions); 716 } 717 p[index] = d->r[i]; 718 } 719 } 720 /* avoid pages containing meta info to end up in cache */ 721 if (munmap(d->r, d->regions_total * sizeof(struct region_info))) 722 wrterror(d, "munmap %p", (void *)d->r); 723 else 724 STATS_SUB(d->malloc_used, 725 d->regions_total * sizeof(struct region_info)); 726 d->regions_free = d->regions_free + d->regions_total; 727 d->regions_total = newtotal; 728 d->r = p; 729 return 0; 730 } 731 732 static struct chunk_info * 733 alloc_chunk_info(struct dir_info *d, int bits) 734 { 735 struct chunk_info *p; 736 size_t size, count; 737 738 if (bits == 0) 739 count = MALLOC_PAGESIZE / MALLOC_MINSIZE; 740 else 741 count = MALLOC_PAGESIZE >> bits; 742 743 size = howmany(count, MALLOC_BITS); 744 size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short); 745 if (mopts.chunk_canaries) 746 size += count * sizeof(u_short); 747 size = ALIGN(size); 748 749 if (LIST_EMPTY(&d->chunk_info_list[bits])) { 750 char *q; 751 int i; 752 753 q = MMAP(MALLOC_PAGESIZE); 754 if (q == MAP_FAILED) 755 return NULL; 756 STATS_ADD(d->malloc_used, MALLOC_PAGESIZE); 757 count = MALLOC_PAGESIZE / size; 758 for (i = 0; i < count; i++, q += size) 759 LIST_INSERT_HEAD(&d->chunk_info_list[bits], 760 (struct chunk_info *)q, entries); 761 } 762 p = LIST_FIRST(&d->chunk_info_list[bits]); 763 LIST_REMOVE(p, entries); 764 memset(p, 0, size); 765 p->canary = d->canary1; 766 return p; 767 } 768 769 770 /* 771 * The hashtable uses the assumption that p is never NULL. This holds since 772 * non-MAP_FIXED mappings with hint 0 start at BRKSIZ. 773 */ 774 static int 775 insert(struct dir_info *d, void *p, size_t sz, void *f) 776 { 777 size_t index; 778 size_t mask; 779 void *q; 780 781 if (d->regions_free * 4 < d->regions_total) { 782 if (omalloc_grow(d)) 783 return 1; 784 } 785 mask = d->regions_total - 1; 786 index = hash(p) & mask; 787 q = d->r[index].p; 788 STATS_INC(d->inserts); 789 while (q != NULL) { 790 index = (index - 1) & mask; 791 q = d->r[index].p; 792 STATS_INC(d->insert_collisions); 793 } 794 d->r[index].p = p; 795 d->r[index].size = sz; 796 #ifdef MALLOC_STATS 797 d->r[index].f = f; 798 #endif 799 d->regions_free--; 800 return 0; 801 } 802 803 static struct region_info * 804 find(struct dir_info *d, void *p) 805 { 806 size_t index; 807 size_t mask = d->regions_total - 1; 808 void *q, *r; 809 810 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 811 d->canary1 != ~d->canary2) 812 wrterror(d, "internal struct corrupt"); 813 p = MASK_POINTER(p); 814 index = hash(p) & mask; 815 r = d->r[index].p; 816 q = MASK_POINTER(r); 817 STATS_INC(d->finds); 818 while (q != p && r != NULL) { 819 index = (index - 1) & mask; 820 r = d->r[index].p; 821 q = MASK_POINTER(r); 822 STATS_INC(d->find_collisions); 823 } 824 return (q == p && r != NULL) ? &d->r[index] : NULL; 825 } 826 827 static void 828 delete(struct dir_info *d, struct region_info *ri) 829 { 830 /* algorithm R, Knuth Vol III section 6.4 */ 831 size_t mask = d->regions_total - 1; 832 size_t i, j, r; 833 834 if (d->regions_total & (d->regions_total - 1)) 835 wrterror(d, "regions_total not 2^x"); 836 d->regions_free++; 837 STATS_INC(d->deletes); 838 839 i = ri - d->r; 840 for (;;) { 841 d->r[i].p = NULL; 842 d->r[i].size = 0; 843 j = i; 844 for (;;) { 845 i = (i - 1) & mask; 846 if (d->r[i].p == NULL) 847 return; 848 r = hash(d->r[i].p) & mask; 849 if ((i <= r && r < j) || (r < j && j < i) || 850 (j < i && i <= r)) 851 continue; 852 d->r[j] = d->r[i]; 853 STATS_INC(d->delete_moves); 854 break; 855 } 856 857 } 858 } 859 860 /* 861 * Allocate a page of chunks 862 */ 863 static struct chunk_info * 864 omalloc_make_chunks(struct dir_info *d, int bits, int listnum) 865 { 866 struct chunk_info *bp; 867 void *pp; 868 int i, k; 869 870 /* Allocate a new bucket */ 871 pp = map(d, NULL, MALLOC_PAGESIZE, 0); 872 if (pp == MAP_FAILED) 873 return NULL; 874 875 bp = alloc_chunk_info(d, bits); 876 if (bp == NULL) { 877 unmap(d, pp, MALLOC_PAGESIZE, 0); 878 return NULL; 879 } 880 881 /* memory protect the page allocated in the malloc(0) case */ 882 if (bits == 0) { 883 bp->size = 0; 884 bp->shift = 1; 885 i = MALLOC_MINSIZE - 1; 886 while (i >>= 1) 887 bp->shift++; 888 bp->total = bp->free = MALLOC_PAGESIZE >> bp->shift; 889 bp->offset = 0xdead; 890 bp->page = pp; 891 892 k = mprotect(pp, MALLOC_PAGESIZE, PROT_NONE); 893 if (k < 0) { 894 unmap(d, pp, MALLOC_PAGESIZE, 0); 895 LIST_INSERT_HEAD(&d->chunk_info_list[0], bp, entries); 896 return NULL; 897 } 898 } else { 899 bp->size = 1U << bits; 900 bp->shift = bits; 901 bp->total = bp->free = MALLOC_PAGESIZE >> bits; 902 bp->offset = howmany(bp->total, MALLOC_BITS); 903 bp->page = pp; 904 } 905 906 /* set all valid bits in the bitmap */ 907 k = bp->total; 908 i = 0; 909 910 /* Do a bunch at a time */ 911 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS) 912 bp->bits[i / MALLOC_BITS] = (u_short)~0U; 913 914 for (; i < k; i++) 915 bp->bits[i / MALLOC_BITS] |= (u_short)1U << (i % MALLOC_BITS); 916 917 LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries); 918 919 bits++; 920 if ((uintptr_t)pp & bits) 921 wrterror(d, "pp & bits %p", pp); 922 923 insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp, NULL); 924 return bp; 925 } 926 927 static int 928 find_chunksize(size_t size) 929 { 930 int i, j; 931 932 /* Don't bother with anything less than this */ 933 /* unless we have a malloc(0) requests */ 934 if (size != 0 && size < MALLOC_MINSIZE) 935 size = MALLOC_MINSIZE; 936 937 /* Find the right bucket */ 938 if (size == 0) 939 j = 0; 940 else { 941 j = MALLOC_MINSHIFT; 942 i = (size - 1) >> (MALLOC_MINSHIFT - 1); 943 while (i >>= 1) 944 j++; 945 } 946 return j; 947 } 948 949 /* 950 * Allocate a chunk 951 */ 952 static void * 953 malloc_bytes(struct dir_info *d, size_t size, void *f) 954 { 955 int i, j, listnum; 956 size_t k; 957 u_short u, *lp; 958 struct chunk_info *bp; 959 960 if (mopts.malloc_canary != (d->canary1 ^ (u_int32_t)(uintptr_t)d) || 961 d->canary1 != ~d->canary2) 962 wrterror(d, "internal struct corrupt"); 963 964 j = find_chunksize(size); 965 966 listnum = getrbyte(d) % MALLOC_CHUNK_LISTS; 967 /* If it's empty, make a page more of that size chunks */ 968 if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) { 969 bp = omalloc_make_chunks(d, j, listnum); 970 if (bp == NULL) 971 return NULL; 972 } 973 974 if (bp->canary != d->canary1) 975 wrterror(d, "chunk info corrupted"); 976 977 i = d->chunk_start; 978 if (bp->free > 1) 979 i += getrbyte(d); 980 if (i >= bp->total) 981 i &= bp->total - 1; 982 for (;;) { 983 for (;;) { 984 lp = &bp->bits[i / MALLOC_BITS]; 985 if (!*lp) { 986 i += MALLOC_BITS; 987 i &= ~(MALLOC_BITS - 1); 988 if (i >= bp->total) 989 i = 0; 990 } else 991 break; 992 } 993 k = i % MALLOC_BITS; 994 u = 1 << k; 995 if (*lp & u) 996 break; 997 if (++i >= bp->total) 998 i = 0; 999 } 1000 d->chunk_start += i + 1; 1001 #ifdef MALLOC_STATS 1002 if (i == 0) { 1003 struct region_info *r = find(d, bp->page); 1004 r->f = f; 1005 } 1006 #endif 1007 1008 *lp ^= u; 1009 1010 /* If there are no more free, remove from free-list */ 1011 if (!--bp->free) 1012 LIST_REMOVE(bp, entries); 1013 1014 /* Adjust to the real offset of that chunk */ 1015 k += (lp - bp->bits) * MALLOC_BITS; 1016 1017 if (mopts.chunk_canaries && size > 0) 1018 bp->bits[bp->offset + k] = size; 1019 1020 k <<= bp->shift; 1021 1022 if (bp->size > 0) { 1023 if (mopts.malloc_junk == 2) 1024 memset((char *)bp->page + k, SOME_JUNK, bp->size); 1025 else if (mopts.chunk_canaries) 1026 fill_canary((char *)bp->page + k, size, bp->size); 1027 } 1028 return ((char *)bp->page + k); 1029 } 1030 1031 static void 1032 fill_canary(char *ptr, size_t sz, size_t allocated) 1033 { 1034 size_t check_sz = allocated - sz; 1035 1036 if (check_sz > CHUNK_CHECK_LENGTH) 1037 check_sz = CHUNK_CHECK_LENGTH; 1038 memset(ptr + sz, SOME_JUNK, check_sz); 1039 } 1040 1041 static void 1042 validate_canary(struct dir_info *d, u_char *ptr, size_t sz, size_t allocated) 1043 { 1044 size_t check_sz = allocated - sz; 1045 u_char *p, *q; 1046 1047 if (check_sz > CHUNK_CHECK_LENGTH) 1048 check_sz = CHUNK_CHECK_LENGTH; 1049 p = ptr + sz; 1050 q = p + check_sz; 1051 1052 while (p < q) { 1053 if (*p++ != SOME_JUNK) { 1054 wrterror(d, "chunk canary corrupted %p %#tx@%#zx", 1055 ptr, p - ptr - 1, sz); 1056 } 1057 } 1058 } 1059 1060 static uint32_t 1061 find_chunknum(struct dir_info *d, struct region_info *r, void *ptr, int check) 1062 { 1063 struct chunk_info *info; 1064 uint32_t chunknum; 1065 1066 info = (struct chunk_info *)r->size; 1067 if (info->canary != d->canary1) 1068 wrterror(d, "chunk info corrupted"); 1069 1070 /* Find the chunk number on the page */ 1071 chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift; 1072 if (check && info->size > 0) { 1073 validate_canary(d, ptr, info->bits[info->offset + chunknum], 1074 info->size); 1075 } 1076 1077 if ((uintptr_t)ptr & ((1U << (info->shift)) - 1)) 1078 wrterror(d, "modified chunk-pointer %p", ptr); 1079 if (info->bits[chunknum / MALLOC_BITS] & 1080 (1U << (chunknum % MALLOC_BITS))) 1081 wrterror(d, "chunk is already free %p", ptr); 1082 return chunknum; 1083 } 1084 1085 /* 1086 * Free a chunk, and possibly the page it's on, if the page becomes empty. 1087 */ 1088 static void 1089 free_bytes(struct dir_info *d, struct region_info *r, void *ptr) 1090 { 1091 struct chunk_head *mp; 1092 struct chunk_info *info; 1093 uint32_t chunknum; 1094 int listnum; 1095 1096 info = (struct chunk_info *)r->size; 1097 chunknum = find_chunknum(d, r, ptr, 0); 1098 1099 info->bits[chunknum / MALLOC_BITS] |= 1U << (chunknum % MALLOC_BITS); 1100 info->free++; 1101 1102 if (info->free == 1) { 1103 /* Page became non-full */ 1104 listnum = getrbyte(d) % MALLOC_CHUNK_LISTS; 1105 if (info->size != 0) 1106 mp = &d->chunk_dir[info->shift][listnum]; 1107 else 1108 mp = &d->chunk_dir[0][listnum]; 1109 1110 LIST_INSERT_HEAD(mp, info, entries); 1111 return; 1112 } 1113 1114 if (info->free != info->total) 1115 return; 1116 1117 LIST_REMOVE(info, entries); 1118 1119 if (info->size == 0 && !mopts.malloc_freeunmap) 1120 mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE); 1121 unmap(d, info->page, MALLOC_PAGESIZE, 0); 1122 1123 delete(d, r); 1124 if (info->size != 0) 1125 mp = &d->chunk_info_list[info->shift]; 1126 else 1127 mp = &d->chunk_info_list[0]; 1128 LIST_INSERT_HEAD(mp, info, entries); 1129 } 1130 1131 1132 1133 static void * 1134 omalloc(struct dir_info *pool, size_t sz, int zero_fill, void *f) 1135 { 1136 void *p; 1137 size_t psz; 1138 1139 if (sz > MALLOC_MAXCHUNK) { 1140 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1141 errno = ENOMEM; 1142 return NULL; 1143 } 1144 sz += mopts.malloc_guard; 1145 psz = PAGEROUND(sz); 1146 p = map(pool, NULL, psz, zero_fill); 1147 if (p == MAP_FAILED) { 1148 errno = ENOMEM; 1149 return NULL; 1150 } 1151 if (insert(pool, p, sz, f)) { 1152 unmap(pool, p, psz, 0); 1153 errno = ENOMEM; 1154 return NULL; 1155 } 1156 if (mopts.malloc_guard) { 1157 if (mprotect((char *)p + psz - mopts.malloc_guard, 1158 mopts.malloc_guard, PROT_NONE)) 1159 wrterror(pool, "mprotect"); 1160 STATS_ADD(pool->malloc_guarded, mopts.malloc_guard); 1161 } 1162 1163 if (MALLOC_MOVE_COND(sz)) { 1164 /* fill whole allocation */ 1165 if (mopts.malloc_junk == 2) 1166 memset(p, SOME_JUNK, psz - mopts.malloc_guard); 1167 /* shift towards the end */ 1168 p = MALLOC_MOVE(p, sz); 1169 /* fill zeros if needed and overwritten above */ 1170 if (zero_fill && mopts.malloc_junk == 2) 1171 memset(p, 0, sz - mopts.malloc_guard); 1172 } else { 1173 if (mopts.malloc_junk == 2) { 1174 if (zero_fill) 1175 memset((char *)p + sz - mopts.malloc_guard, 1176 SOME_JUNK, psz - sz); 1177 else 1178 memset(p, SOME_JUNK, 1179 psz - mopts.malloc_guard); 1180 } 1181 else if (mopts.chunk_canaries) 1182 fill_canary(p, sz - mopts.malloc_guard, 1183 psz - mopts.malloc_guard); 1184 } 1185 1186 } else { 1187 /* takes care of SOME_JUNK */ 1188 p = malloc_bytes(pool, sz, f); 1189 if (zero_fill && p != NULL && sz > 0) 1190 memset(p, 0, sz); 1191 } 1192 1193 return p; 1194 } 1195 1196 /* 1197 * Common function for handling recursion. Only 1198 * print the error message once, to avoid making the problem 1199 * potentially worse. 1200 */ 1201 static void 1202 malloc_recurse(struct dir_info *d) 1203 { 1204 static int noprint; 1205 1206 if (noprint == 0) { 1207 noprint = 1; 1208 wrterror(d, "recursive call"); 1209 } 1210 d->active--; 1211 _MALLOC_UNLOCK(d->mutex); 1212 errno = EDEADLK; 1213 } 1214 1215 void 1216 _malloc_init(int from_rthreads) 1217 { 1218 int i, max; 1219 struct dir_info *d; 1220 1221 _MALLOC_LOCK(0); 1222 if (!from_rthreads && mopts.malloc_pool[0]) { 1223 _MALLOC_UNLOCK(0); 1224 return; 1225 } 1226 if (!mopts.malloc_canary) 1227 omalloc_init(); 1228 1229 max = from_rthreads ? _MALLOC_MUTEXES : 1; 1230 if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0) 1231 mprotect(&malloc_readonly, sizeof(malloc_readonly), 1232 PROT_READ | PROT_WRITE); 1233 for (i = 0; i < max; i++) { 1234 if (mopts.malloc_pool[i]) 1235 continue; 1236 omalloc_poolinit(&d); 1237 d->mutex = i; 1238 mopts.malloc_pool[i] = d; 1239 } 1240 1241 if (from_rthreads) 1242 mopts.malloc_mt = 1; 1243 else 1244 mopts.internal_funcs = 1; 1245 1246 /* 1247 * Options have been set and will never be reset. 1248 * Prevent further tampering with them. 1249 */ 1250 if (((uintptr_t)&malloc_readonly & MALLOC_PAGEMASK) == 0) 1251 mprotect(&malloc_readonly, sizeof(malloc_readonly), PROT_READ); 1252 _MALLOC_UNLOCK(0); 1253 } 1254 DEF_STRONG(_malloc_init); 1255 1256 void * 1257 malloc(size_t size) 1258 { 1259 void *r; 1260 struct dir_info *d; 1261 int saved_errno = errno; 1262 1263 d = getpool(); 1264 if (d == NULL) { 1265 _malloc_init(0); 1266 d = getpool(); 1267 } 1268 _MALLOC_LOCK(d->mutex); 1269 d->func = "malloc"; 1270 1271 if (d->active++) { 1272 malloc_recurse(d); 1273 return NULL; 1274 } 1275 r = omalloc(d, size, 0, CALLER); 1276 d->active--; 1277 _MALLOC_UNLOCK(d->mutex); 1278 if (r == NULL && mopts.malloc_xmalloc) 1279 wrterror(d, "out of memory"); 1280 if (r != NULL) 1281 errno = saved_errno; 1282 return r; 1283 } 1284 /*DEF_STRONG(malloc);*/ 1285 1286 static void 1287 validate_junk(struct dir_info *pool, void *p) 1288 { 1289 struct region_info *r; 1290 size_t byte, sz; 1291 1292 if (p == NULL) 1293 return; 1294 r = find(pool, p); 1295 if (r == NULL) 1296 wrterror(pool, "bogus pointer in validate_junk %p", p); 1297 REALSIZE(sz, r); 1298 if (sz > CHUNK_CHECK_LENGTH) 1299 sz = CHUNK_CHECK_LENGTH; 1300 for (byte = 0; byte < sz; byte++) { 1301 if (((unsigned char *)p)[byte] != SOME_FREEJUNK) 1302 wrterror(pool, "use after free %p", p); 1303 } 1304 } 1305 1306 static void 1307 ofree(struct dir_info *argpool, void *p, int clear, int check, size_t argsz) 1308 { 1309 struct dir_info *pool; 1310 struct region_info *r; 1311 size_t sz; 1312 int i; 1313 1314 pool = argpool; 1315 r = find(pool, p); 1316 if (r == NULL) { 1317 if (mopts.malloc_mt) { 1318 for (i = 0; i < _MALLOC_MUTEXES; i++) { 1319 if (i == argpool->mutex) 1320 continue; 1321 pool->active--; 1322 _MALLOC_UNLOCK(pool->mutex); 1323 pool = mopts.malloc_pool[i]; 1324 _MALLOC_LOCK(pool->mutex); 1325 pool->active++; 1326 r = find(pool, p); 1327 if (r != NULL) 1328 break; 1329 } 1330 } 1331 if (r == NULL) 1332 wrterror(pool, "bogus pointer (double free?) %p", p); 1333 } 1334 1335 REALSIZE(sz, r); 1336 if (check) { 1337 if (sz <= MALLOC_MAXCHUNK) { 1338 if (mopts.chunk_canaries && sz > 0) { 1339 struct chunk_info *info = 1340 (struct chunk_info *)r->size; 1341 uint32_t chunknum = 1342 find_chunknum(pool, r, p, 0); 1343 1344 if (info->bits[info->offset + chunknum] < 1345 argsz) 1346 wrterror(pool, "recorded size %hu" 1347 " < %zu", 1348 info->bits[info->offset + chunknum], 1349 argsz); 1350 } else { 1351 if (sz < argsz) 1352 wrterror(pool, "chunk size %zu < %zu", 1353 sz, argsz); 1354 } 1355 } else if (sz - mopts.malloc_guard < argsz) { 1356 wrterror(pool, "recorded size %zu < %zu", 1357 sz - mopts.malloc_guard, argsz); 1358 } 1359 } 1360 if (sz > MALLOC_MAXCHUNK) { 1361 if (!MALLOC_MOVE_COND(sz)) { 1362 if (r->p != p) 1363 wrterror(pool, "bogus pointer %p", p); 1364 if (mopts.chunk_canaries) 1365 validate_canary(pool, p, 1366 sz - mopts.malloc_guard, 1367 PAGEROUND(sz - mopts.malloc_guard)); 1368 } else { 1369 /* shifted towards the end */ 1370 if (p != MALLOC_MOVE(r->p, sz)) 1371 wrterror(pool, "bogus moved pointer %p", p); 1372 p = r->p; 1373 } 1374 if (mopts.malloc_guard) { 1375 if (sz < mopts.malloc_guard) 1376 wrterror(pool, "guard size"); 1377 if (!mopts.malloc_freeunmap) { 1378 if (mprotect((char *)p + PAGEROUND(sz) - 1379 mopts.malloc_guard, mopts.malloc_guard, 1380 PROT_READ | PROT_WRITE)) 1381 wrterror(pool, "mprotect"); 1382 } 1383 STATS_SUB(pool->malloc_guarded, mopts.malloc_guard); 1384 } 1385 unmap(pool, p, PAGEROUND(sz), clear); 1386 delete(pool, r); 1387 } else { 1388 void *tmp; 1389 int i; 1390 1391 /* Delayed free or canaries? Extra check */ 1392 if (!mopts.malloc_freenow || mopts.chunk_canaries) 1393 find_chunknum(pool, r, p, mopts.chunk_canaries); 1394 if (!clear && !mopts.malloc_freenow) { 1395 if (mopts.malloc_junk && sz > 0) 1396 memset(p, SOME_FREEJUNK, sz); 1397 i = getrbyte(pool) & MALLOC_DELAYED_CHUNK_MASK; 1398 tmp = p; 1399 p = pool->delayed_chunks[i]; 1400 if (tmp == p) 1401 wrterror(pool, "double free %p", tmp); 1402 if (mopts.malloc_junk) 1403 validate_junk(pool, p); 1404 pool->delayed_chunks[i] = tmp; 1405 } else { 1406 if ((clear || mopts.malloc_junk) && sz > 0) 1407 memset(p, clear ? 0 : SOME_FREEJUNK, sz); 1408 } 1409 if (p != NULL) { 1410 r = find(pool, p); 1411 if (r == NULL) 1412 wrterror(pool, 1413 "bogus pointer (double free?) %p", p); 1414 free_bytes(pool, r, p); 1415 } 1416 } 1417 1418 if (argpool != pool) { 1419 pool->active--; 1420 _MALLOC_UNLOCK(pool->mutex); 1421 _MALLOC_LOCK(argpool->mutex); 1422 argpool->active++; 1423 } 1424 } 1425 1426 void 1427 free(void *ptr) 1428 { 1429 struct dir_info *d; 1430 int saved_errno = errno; 1431 1432 /* This is legal. */ 1433 if (ptr == NULL) 1434 return; 1435 1436 d = getpool(); 1437 if (d == NULL) 1438 wrterror(d, "free() called before allocation"); 1439 _MALLOC_LOCK(d->mutex); 1440 d->func = "free"; 1441 if (d->active++) { 1442 malloc_recurse(d); 1443 return; 1444 } 1445 ofree(d, ptr, 0, 0, 0); 1446 d->active--; 1447 _MALLOC_UNLOCK(d->mutex); 1448 errno = saved_errno; 1449 } 1450 /*DEF_STRONG(free);*/ 1451 1452 static void 1453 freezero_p(void *ptr, size_t sz) 1454 { 1455 explicit_bzero(ptr, sz); 1456 free(ptr); 1457 } 1458 1459 void 1460 freezero(void *ptr, size_t sz) 1461 { 1462 struct dir_info *d; 1463 int saved_errno = errno; 1464 1465 /* This is legal. */ 1466 if (ptr == NULL) 1467 return; 1468 1469 if (!mopts.internal_funcs) 1470 return freezero_p(ptr, sz); 1471 1472 d = getpool(); 1473 if (d == NULL) 1474 wrterror(d, "freezero() called before allocation"); 1475 _MALLOC_LOCK(d->mutex); 1476 d->func = "freezero"; 1477 if (d->active++) { 1478 malloc_recurse(d); 1479 return; 1480 } 1481 ofree(d, ptr, 1, 1, sz); 1482 d->active--; 1483 _MALLOC_UNLOCK(d->mutex); 1484 errno = saved_errno; 1485 } 1486 DEF_WEAK(freezero); 1487 1488 static void * 1489 orealloc(struct dir_info *argpool, void *p, size_t newsz, void *f) 1490 { 1491 struct dir_info *pool; 1492 struct region_info *r; 1493 struct chunk_info *info; 1494 size_t oldsz, goldsz, gnewsz; 1495 void *q, *ret; 1496 int i; 1497 uint32_t chunknum; 1498 1499 pool = argpool; 1500 1501 if (p == NULL) 1502 return omalloc(pool, newsz, 0, f); 1503 1504 r = find(pool, p); 1505 if (r == NULL) { 1506 if (mopts.malloc_mt) { 1507 for (i = 0; i < _MALLOC_MUTEXES; i++) { 1508 if (i == argpool->mutex) 1509 continue; 1510 pool->active--; 1511 _MALLOC_UNLOCK(pool->mutex); 1512 pool = mopts.malloc_pool[i]; 1513 _MALLOC_LOCK(pool->mutex); 1514 pool->active++; 1515 r = find(pool, p); 1516 if (r != NULL) 1517 break; 1518 } 1519 } 1520 if (r == NULL) 1521 wrterror(pool, "bogus pointer (double free?) %p", p); 1522 } 1523 if (newsz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1524 errno = ENOMEM; 1525 ret = NULL; 1526 goto done; 1527 } 1528 1529 REALSIZE(oldsz, r); 1530 if (mopts.chunk_canaries && oldsz <= MALLOC_MAXCHUNK) { 1531 chunknum = find_chunknum(pool, r, p, 0); 1532 info = (struct chunk_info *)r->size; 1533 } 1534 1535 goldsz = oldsz; 1536 if (oldsz > MALLOC_MAXCHUNK) { 1537 if (oldsz < mopts.malloc_guard) 1538 wrterror(pool, "guard size"); 1539 oldsz -= mopts.malloc_guard; 1540 } 1541 1542 gnewsz = newsz; 1543 if (gnewsz > MALLOC_MAXCHUNK) 1544 gnewsz += mopts.malloc_guard; 1545 1546 if (newsz > MALLOC_MAXCHUNK && oldsz > MALLOC_MAXCHUNK && 1547 !mopts.malloc_realloc) { 1548 /* First case: from n pages sized allocation to m pages sized 1549 allocation, m > n */ 1550 size_t roldsz = PAGEROUND(goldsz); 1551 size_t rnewsz = PAGEROUND(gnewsz); 1552 1553 if (rnewsz > roldsz) { 1554 /* try to extend existing region */ 1555 if (!mopts.malloc_guard) { 1556 void *hint = (char *)r->p + roldsz; 1557 size_t needed = rnewsz - roldsz; 1558 1559 STATS_INC(pool->cheap_realloc_tries); 1560 q = map(pool, hint, needed, 0); 1561 if (q == hint) 1562 goto gotit; 1563 zapcacheregion(pool, hint, needed); 1564 q = MQUERY(hint, needed); 1565 if (q == hint) 1566 q = MMAPA(hint, needed); 1567 else 1568 q = MAP_FAILED; 1569 if (q == hint) { 1570 gotit: 1571 STATS_ADD(pool->malloc_used, needed); 1572 if (mopts.malloc_junk == 2) 1573 memset(q, SOME_JUNK, needed); 1574 r->size = gnewsz; 1575 if (r->p != p) { 1576 /* old pointer is moved */ 1577 memmove(r->p, p, oldsz); 1578 p = r->p; 1579 } 1580 if (mopts.chunk_canaries) 1581 fill_canary(p, newsz, 1582 PAGEROUND(newsz)); 1583 STATS_SETF(r, f); 1584 STATS_INC(pool->cheap_reallocs); 1585 ret = p; 1586 goto done; 1587 } else if (q != MAP_FAILED) { 1588 if (munmap(q, needed)) 1589 wrterror(pool, "munmap %p", q); 1590 } 1591 } 1592 } else if (rnewsz < roldsz) { 1593 /* shrink number of pages */ 1594 if (mopts.malloc_guard) { 1595 if (mprotect((char *)r->p + roldsz - 1596 mopts.malloc_guard, mopts.malloc_guard, 1597 PROT_READ | PROT_WRITE)) 1598 wrterror(pool, "mprotect"); 1599 if (mprotect((char *)r->p + rnewsz - 1600 mopts.malloc_guard, mopts.malloc_guard, 1601 PROT_NONE)) 1602 wrterror(pool, "mprotect"); 1603 } 1604 unmap(pool, (char *)r->p + rnewsz, roldsz - rnewsz, 0); 1605 r->size = gnewsz; 1606 if (MALLOC_MOVE_COND(gnewsz)) { 1607 void *pp = MALLOC_MOVE(r->p, gnewsz); 1608 memmove(pp, p, newsz); 1609 p = pp; 1610 } else if (mopts.chunk_canaries) 1611 fill_canary(p, newsz, PAGEROUND(newsz)); 1612 STATS_SETF(r, f); 1613 ret = p; 1614 goto done; 1615 } else { 1616 /* number of pages remains the same */ 1617 void *pp = r->p; 1618 1619 r->size = gnewsz; 1620 if (MALLOC_MOVE_COND(gnewsz)) 1621 pp = MALLOC_MOVE(r->p, gnewsz); 1622 if (p != pp) { 1623 memmove(pp, p, oldsz < newsz ? oldsz : newsz); 1624 p = pp; 1625 } 1626 if (p == r->p) { 1627 if (newsz > oldsz && mopts.malloc_junk == 2) 1628 memset((char *)p + newsz, SOME_JUNK, 1629 rnewsz - mopts.malloc_guard - 1630 newsz); 1631 if (mopts.chunk_canaries) 1632 fill_canary(p, newsz, PAGEROUND(newsz)); 1633 } 1634 STATS_SETF(r, f); 1635 ret = p; 1636 goto done; 1637 } 1638 } 1639 if (oldsz <= MALLOC_MAXCHUNK && oldsz > 0 && 1640 newsz <= MALLOC_MAXCHUNK && newsz > 0 && 1641 1 << find_chunksize(newsz) == oldsz && !mopts.malloc_realloc) { 1642 /* do not reallocate if new size fits good in existing chunk */ 1643 if (mopts.malloc_junk == 2) 1644 memset((char *)p + newsz, SOME_JUNK, oldsz - newsz); 1645 if (mopts.chunk_canaries) { 1646 info->bits[info->offset + chunknum] = newsz; 1647 fill_canary(p, newsz, info->size); 1648 } 1649 STATS_SETF(r, f); 1650 ret = p; 1651 } else if (newsz != oldsz || mopts.malloc_realloc) { 1652 /* create new allocation */ 1653 q = omalloc(pool, newsz, 0, f); 1654 if (q == NULL) { 1655 ret = NULL; 1656 goto done; 1657 } 1658 if (newsz != 0 && oldsz != 0) 1659 memcpy(q, p, oldsz < newsz ? oldsz : newsz); 1660 ofree(pool, p, 0, 0, 0); 1661 ret = q; 1662 } else { 1663 /* oldsz == newsz */ 1664 if (newsz != 0) 1665 wrterror(pool, "realloc internal inconsistency"); 1666 STATS_SETF(r, f); 1667 ret = p; 1668 } 1669 done: 1670 if (argpool != pool) { 1671 pool->active--; 1672 _MALLOC_UNLOCK(pool->mutex); 1673 _MALLOC_LOCK(argpool->mutex); 1674 argpool->active++; 1675 } 1676 return ret; 1677 } 1678 1679 void * 1680 realloc(void *ptr, size_t size) 1681 { 1682 struct dir_info *d; 1683 void *r; 1684 int saved_errno = errno; 1685 1686 d = getpool(); 1687 if (d == NULL) { 1688 _malloc_init(0); 1689 d = getpool(); 1690 } 1691 _MALLOC_LOCK(d->mutex); 1692 d->func = "realloc"; 1693 if (d->active++) { 1694 malloc_recurse(d); 1695 return NULL; 1696 } 1697 r = orealloc(d, ptr, size, CALLER); 1698 1699 d->active--; 1700 _MALLOC_UNLOCK(d->mutex); 1701 if (r == NULL && mopts.malloc_xmalloc) 1702 wrterror(d, "out of memory"); 1703 if (r != NULL) 1704 errno = saved_errno; 1705 return r; 1706 } 1707 /*DEF_STRONG(realloc);*/ 1708 1709 1710 /* 1711 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX 1712 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW 1713 */ 1714 #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4)) 1715 1716 void * 1717 calloc(size_t nmemb, size_t size) 1718 { 1719 struct dir_info *d; 1720 void *r; 1721 int saved_errno = errno; 1722 1723 d = getpool(); 1724 if (d == NULL) { 1725 _malloc_init(0); 1726 d = getpool(); 1727 } 1728 _MALLOC_LOCK(d->mutex); 1729 d->func = "calloc"; 1730 if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1731 nmemb > 0 && SIZE_MAX / nmemb < size) { 1732 _MALLOC_UNLOCK(d->mutex); 1733 if (mopts.malloc_xmalloc) 1734 wrterror(d, "out of memory"); 1735 errno = ENOMEM; 1736 return NULL; 1737 } 1738 1739 if (d->active++) { 1740 malloc_recurse(d); 1741 return NULL; 1742 } 1743 1744 size *= nmemb; 1745 r = omalloc(d, size, 1, CALLER); 1746 1747 d->active--; 1748 _MALLOC_UNLOCK(d->mutex); 1749 if (r == NULL && mopts.malloc_xmalloc) 1750 wrterror(d, "out of memory"); 1751 if (r != NULL) 1752 errno = saved_errno; 1753 return r; 1754 } 1755 /*DEF_STRONG(calloc);*/ 1756 1757 static void * 1758 orecallocarray(struct dir_info *argpool, void *p, size_t oldsize, 1759 size_t newsize, void *f) 1760 { 1761 struct dir_info *pool; 1762 struct region_info *r; 1763 void *newptr; 1764 size_t sz; 1765 int i; 1766 1767 pool = argpool; 1768 1769 if (p == NULL) 1770 return omalloc(pool, newsize, 1, f); 1771 1772 if (oldsize == newsize) 1773 return p; 1774 1775 r = find(pool, p); 1776 if (r == NULL) { 1777 if (mopts.malloc_mt) { 1778 for (i = 0; i < _MALLOC_MUTEXES; i++) { 1779 if (i == argpool->mutex) 1780 continue; 1781 pool->active--; 1782 _MALLOC_UNLOCK(pool->mutex); 1783 pool = mopts.malloc_pool[i]; 1784 _MALLOC_LOCK(pool->mutex); 1785 pool->active++; 1786 r = find(pool, p); 1787 if (r != NULL) 1788 break; 1789 } 1790 } 1791 if (r == NULL) 1792 wrterror(pool, "bogus pointer (double free?) %p", p); 1793 } 1794 1795 REALSIZE(sz, r); 1796 if (sz <= MALLOC_MAXCHUNK) { 1797 if (mopts.chunk_canaries && sz > 0) { 1798 struct chunk_info *info = (struct chunk_info *)r->size; 1799 uint32_t chunknum = find_chunknum(pool, r, p, 0); 1800 1801 if (info->bits[info->offset + chunknum] != oldsize) 1802 wrterror(pool, "recorded old size %hu != %zu", 1803 info->bits[info->offset + chunknum], 1804 oldsize); 1805 } 1806 } else if (oldsize != sz - mopts.malloc_guard) 1807 wrterror(pool, "recorded old size %zu != %zu", 1808 sz - mopts.malloc_guard, oldsize); 1809 1810 newptr = omalloc(pool, newsize, 0, f); 1811 if (newptr == NULL) 1812 goto done; 1813 1814 if (newsize > oldsize) { 1815 memcpy(newptr, p, oldsize); 1816 memset((char *)newptr + oldsize, 0, newsize - oldsize); 1817 } else 1818 memcpy(newptr, p, newsize); 1819 1820 ofree(pool, p, 1, 0, 0); 1821 1822 done: 1823 if (argpool != pool) { 1824 pool->active--; 1825 _MALLOC_UNLOCK(pool->mutex); 1826 _MALLOC_LOCK(argpool->mutex); 1827 argpool->active++; 1828 } 1829 1830 return newptr; 1831 } 1832 1833 static void * 1834 recallocarray_p(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size) 1835 { 1836 size_t oldsize, newsize; 1837 void *newptr; 1838 1839 if (ptr == NULL) 1840 return calloc(newnmemb, size); 1841 1842 if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1843 newnmemb > 0 && SIZE_MAX / newnmemb < size) { 1844 errno = ENOMEM; 1845 return NULL; 1846 } 1847 newsize = newnmemb * size; 1848 1849 if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1850 oldnmemb > 0 && SIZE_MAX / oldnmemb < size) { 1851 errno = EINVAL; 1852 return NULL; 1853 } 1854 oldsize = oldnmemb * size; 1855 1856 /* 1857 * Don't bother too much if we're shrinking just a bit, 1858 * we do not shrink for series of small steps, oh well. 1859 */ 1860 if (newsize <= oldsize) { 1861 size_t d = oldsize - newsize; 1862 1863 if (d < oldsize / 2 && d < MALLOC_PAGESIZE) { 1864 memset((char *)ptr + newsize, 0, d); 1865 return ptr; 1866 } 1867 } 1868 1869 newptr = malloc(newsize); 1870 if (newptr == NULL) 1871 return NULL; 1872 1873 if (newsize > oldsize) { 1874 memcpy(newptr, ptr, oldsize); 1875 memset((char *)newptr + oldsize, 0, newsize - oldsize); 1876 } else 1877 memcpy(newptr, ptr, newsize); 1878 1879 explicit_bzero(ptr, oldsize); 1880 free(ptr); 1881 1882 return newptr; 1883 } 1884 1885 void * 1886 recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size) 1887 { 1888 struct dir_info *d; 1889 size_t oldsize = 0, newsize; 1890 void *r; 1891 int saved_errno = errno; 1892 1893 if (!mopts.internal_funcs) 1894 return recallocarray_p(ptr, oldnmemb, newnmemb, size); 1895 1896 d = getpool(); 1897 if (d == NULL) { 1898 _malloc_init(0); 1899 d = getpool(); 1900 } 1901 1902 _MALLOC_LOCK(d->mutex); 1903 d->func = "recallocarray"; 1904 1905 if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1906 newnmemb > 0 && SIZE_MAX / newnmemb < size) { 1907 _MALLOC_UNLOCK(d->mutex); 1908 if (mopts.malloc_xmalloc) 1909 wrterror(d, "out of memory"); 1910 errno = ENOMEM; 1911 return NULL; 1912 } 1913 newsize = newnmemb * size; 1914 1915 if (ptr != NULL) { 1916 if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && 1917 oldnmemb > 0 && SIZE_MAX / oldnmemb < size) { 1918 _MALLOC_UNLOCK(d->mutex); 1919 errno = EINVAL; 1920 return NULL; 1921 } 1922 oldsize = oldnmemb * size; 1923 } 1924 1925 if (d->active++) { 1926 malloc_recurse(d); 1927 return NULL; 1928 } 1929 1930 r = orecallocarray(d, ptr, oldsize, newsize, CALLER); 1931 1932 d->active--; 1933 _MALLOC_UNLOCK(d->mutex); 1934 if (r == NULL && mopts.malloc_xmalloc) 1935 wrterror(d, "out of memory"); 1936 if (r != NULL) 1937 errno = saved_errno; 1938 return r; 1939 } 1940 DEF_WEAK(recallocarray); 1941 1942 1943 static void * 1944 mapalign(struct dir_info *d, size_t alignment, size_t sz, int zero_fill) 1945 { 1946 char *p, *q; 1947 1948 if (alignment < MALLOC_PAGESIZE || ((alignment - 1) & alignment) != 0) 1949 wrterror(d, "mapalign bad alignment"); 1950 if (sz != PAGEROUND(sz)) 1951 wrterror(d, "mapalign round"); 1952 1953 /* Allocate sz + alignment bytes of memory, which must include a 1954 * subrange of size bytes that is properly aligned. Unmap the 1955 * other bytes, and then return that subrange. 1956 */ 1957 1958 /* We need sz + alignment to fit into a size_t. */ 1959 if (alignment > SIZE_MAX - sz) 1960 return MAP_FAILED; 1961 1962 p = map(d, NULL, sz + alignment, zero_fill); 1963 if (p == MAP_FAILED) 1964 return MAP_FAILED; 1965 q = (char *)(((uintptr_t)p + alignment - 1) & ~(alignment - 1)); 1966 if (q != p) { 1967 if (munmap(p, q - p)) 1968 wrterror(d, "munmap %p", p); 1969 } 1970 if (munmap(q + sz, alignment - (q - p))) 1971 wrterror(d, "munmap %p", q + sz); 1972 STATS_SUB(d->malloc_used, alignment); 1973 1974 return q; 1975 } 1976 1977 static void * 1978 omemalign(struct dir_info *pool, size_t alignment, size_t sz, int zero_fill, 1979 void *f) 1980 { 1981 size_t psz; 1982 void *p; 1983 1984 /* If between half a page and a page, avoid MALLOC_MOVE. */ 1985 if (sz > MALLOC_MAXCHUNK && sz < MALLOC_PAGESIZE) 1986 sz = MALLOC_PAGESIZE; 1987 if (alignment <= MALLOC_PAGESIZE) { 1988 /* 1989 * max(size, alignment) is enough to assure the requested 1990 * alignment, since the allocator always allocates 1991 * power-of-two blocks. 1992 */ 1993 if (sz < alignment) 1994 sz = alignment; 1995 return omalloc(pool, sz, zero_fill, f); 1996 } 1997 1998 if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) { 1999 errno = ENOMEM; 2000 return NULL; 2001 } 2002 2003 sz += mopts.malloc_guard; 2004 psz = PAGEROUND(sz); 2005 2006 p = mapalign(pool, alignment, psz, zero_fill); 2007 if (p == NULL) { 2008 errno = ENOMEM; 2009 return NULL; 2010 } 2011 2012 if (insert(pool, p, sz, f)) { 2013 unmap(pool, p, psz, 0); 2014 errno = ENOMEM; 2015 return NULL; 2016 } 2017 2018 if (mopts.malloc_guard) { 2019 if (mprotect((char *)p + psz - mopts.malloc_guard, 2020 mopts.malloc_guard, PROT_NONE)) 2021 wrterror(pool, "mprotect"); 2022 STATS_ADD(pool->malloc_guarded, mopts.malloc_guard); 2023 } 2024 2025 if (mopts.malloc_junk == 2) { 2026 if (zero_fill) 2027 memset((char *)p + sz - mopts.malloc_guard, 2028 SOME_JUNK, psz - sz); 2029 else 2030 memset(p, SOME_JUNK, psz - mopts.malloc_guard); 2031 } 2032 else if (mopts.chunk_canaries) 2033 fill_canary(p, sz - mopts.malloc_guard, 2034 psz - mopts.malloc_guard); 2035 2036 return p; 2037 } 2038 2039 int 2040 posix_memalign(void **memptr, size_t alignment, size_t size) 2041 { 2042 struct dir_info *d; 2043 int res, saved_errno = errno; 2044 void *r; 2045 2046 /* Make sure that alignment is a large enough power of 2. */ 2047 if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *)) 2048 return EINVAL; 2049 2050 d = getpool(); 2051 if (d == NULL) { 2052 _malloc_init(0); 2053 d = getpool(); 2054 } 2055 _MALLOC_LOCK(d->mutex); 2056 d->func = "posix_memalign"; 2057 if (d->active++) { 2058 malloc_recurse(d); 2059 goto err; 2060 } 2061 r = omemalign(d, alignment, size, 0, CALLER); 2062 d->active--; 2063 _MALLOC_UNLOCK(d->mutex); 2064 if (r == NULL) { 2065 if (mopts.malloc_xmalloc) 2066 wrterror(d, "out of memory"); 2067 goto err; 2068 } 2069 errno = saved_errno; 2070 *memptr = r; 2071 return 0; 2072 2073 err: 2074 res = errno; 2075 errno = saved_errno; 2076 return res; 2077 } 2078 /*DEF_STRONG(posix_memalign);*/ 2079 2080 #ifdef MALLOC_STATS 2081 2082 struct malloc_leak { 2083 void (*f)(); 2084 size_t total_size; 2085 int count; 2086 }; 2087 2088 struct leaknode { 2089 RBT_ENTRY(leaknode) entry; 2090 struct malloc_leak d; 2091 }; 2092 2093 static inline int 2094 leakcmp(const struct leaknode *e1, const struct leaknode *e2) 2095 { 2096 return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f; 2097 } 2098 2099 static RBT_HEAD(leaktree, leaknode) leakhead; 2100 RBT_PROTOTYPE(leaktree, leaknode, entry, leakcmp); 2101 RBT_GENERATE(leaktree, leaknode, entry, leakcmp); 2102 2103 static void 2104 putleakinfo(void *f, size_t sz, int cnt) 2105 { 2106 struct leaknode key, *p; 2107 static struct leaknode *page; 2108 static int used; 2109 2110 if (cnt == 0 || page == MAP_FAILED) 2111 return; 2112 2113 key.d.f = f; 2114 p = RBT_FIND(leaktree, &leakhead, &key); 2115 if (p == NULL) { 2116 if (page == NULL || 2117 used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) { 2118 page = MMAP(MALLOC_PAGESIZE); 2119 if (page == MAP_FAILED) 2120 return; 2121 used = 0; 2122 } 2123 p = &page[used++]; 2124 p->d.f = f; 2125 p->d.total_size = sz * cnt; 2126 p->d.count = cnt; 2127 RBT_INSERT(leaktree, &leakhead, p); 2128 } else { 2129 p->d.total_size += sz * cnt; 2130 p->d.count += cnt; 2131 } 2132 } 2133 2134 static struct malloc_leak *malloc_leaks; 2135 2136 static void 2137 writestr(int fd, const char *p) 2138 { 2139 write(fd, p, strlen(p)); 2140 } 2141 2142 static void 2143 dump_leaks(int fd) 2144 { 2145 struct leaknode *p; 2146 char buf[64]; 2147 int i = 0; 2148 2149 writestr(fd, "Leak report\n"); 2150 writestr(fd, " f sum # avg\n"); 2151 /* XXX only one page of summary */ 2152 if (malloc_leaks == NULL) 2153 malloc_leaks = MMAP(MALLOC_PAGESIZE); 2154 if (malloc_leaks != MAP_FAILED) 2155 memset(malloc_leaks, 0, MALLOC_PAGESIZE); 2156 RBT_FOREACH(p, leaktree, &leakhead) { 2157 snprintf(buf, sizeof(buf), "%18p %7zu %6u %6zu\n", p->d.f, 2158 p->d.total_size, p->d.count, p->d.total_size / p->d.count); 2159 write(fd, buf, strlen(buf)); 2160 if (malloc_leaks == MAP_FAILED || 2161 i >= MALLOC_PAGESIZE / sizeof(struct malloc_leak)) 2162 continue; 2163 malloc_leaks[i].f = p->d.f; 2164 malloc_leaks[i].total_size = p->d.total_size; 2165 malloc_leaks[i].count = p->d.count; 2166 i++; 2167 } 2168 } 2169 2170 static void 2171 dump_chunk(int fd, struct chunk_info *p, void *f, int fromfreelist) 2172 { 2173 char buf[64]; 2174 2175 while (p != NULL) { 2176 snprintf(buf, sizeof(buf), "chunk %18p %18p %4d %d/%d\n", 2177 p->page, ((p->bits[0] & 1) ? NULL : f), 2178 p->size, p->free, p->total); 2179 write(fd, buf, strlen(buf)); 2180 if (!fromfreelist) { 2181 if (p->bits[0] & 1) 2182 putleakinfo(NULL, p->size, p->total - p->free); 2183 else { 2184 putleakinfo(f, p->size, 1); 2185 putleakinfo(NULL, p->size, 2186 p->total - p->free - 1); 2187 } 2188 break; 2189 } 2190 p = LIST_NEXT(p, entries); 2191 if (p != NULL) 2192 writestr(fd, " "); 2193 } 2194 } 2195 2196 static void 2197 dump_free_chunk_info(int fd, struct dir_info *d) 2198 { 2199 char buf[64]; 2200 int i, j, count; 2201 struct chunk_info *p; 2202 2203 writestr(fd, "Free chunk structs:\n"); 2204 for (i = 0; i <= MALLOC_MAXSHIFT; i++) { 2205 count = 0; 2206 LIST_FOREACH(p, &d->chunk_info_list[i], entries) 2207 count++; 2208 for (j = 0; j < MALLOC_CHUNK_LISTS; j++) { 2209 p = LIST_FIRST(&d->chunk_dir[i][j]); 2210 if (p == NULL && count == 0) 2211 continue; 2212 snprintf(buf, sizeof(buf), "%2d) %3d ", i, count); 2213 write(fd, buf, strlen(buf)); 2214 if (p != NULL) 2215 dump_chunk(fd, p, NULL, 1); 2216 else 2217 write(fd, "\n", 1); 2218 } 2219 } 2220 2221 } 2222 2223 static void 2224 dump_free_page_info(int fd, struct dir_info *d) 2225 { 2226 char buf[64]; 2227 int i; 2228 2229 snprintf(buf, sizeof(buf), "Free pages cached: %zu\n", 2230 d->free_regions_size); 2231 write(fd, buf, strlen(buf)); 2232 for (i = 0; i < mopts.malloc_cache; i++) { 2233 if (d->free_regions[i].p != NULL) { 2234 snprintf(buf, sizeof(buf), "%2d) ", i); 2235 write(fd, buf, strlen(buf)); 2236 snprintf(buf, sizeof(buf), "free at %p: %zu\n", 2237 d->free_regions[i].p, d->free_regions[i].size); 2238 write(fd, buf, strlen(buf)); 2239 } 2240 } 2241 } 2242 2243 static void 2244 malloc_dump1(int fd, int poolno, struct dir_info *d) 2245 { 2246 char buf[100]; 2247 size_t i, realsize; 2248 2249 snprintf(buf, sizeof(buf), "Malloc dir of %s pool %d at %p\n", __progname, poolno, d); 2250 write(fd, buf, strlen(buf)); 2251 if (d == NULL) 2252 return; 2253 snprintf(buf, sizeof(buf), "Region slots free %zu/%zu\n", 2254 d->regions_free, d->regions_total); 2255 write(fd, buf, strlen(buf)); 2256 snprintf(buf, sizeof(buf), "Finds %zu/%zu\n", d->finds, 2257 d->find_collisions); 2258 write(fd, buf, strlen(buf)); 2259 snprintf(buf, sizeof(buf), "Inserts %zu/%zu\n", d->inserts, 2260 d->insert_collisions); 2261 write(fd, buf, strlen(buf)); 2262 snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes, 2263 d->delete_moves); 2264 write(fd, buf, strlen(buf)); 2265 snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n", 2266 d->cheap_reallocs, d->cheap_realloc_tries); 2267 write(fd, buf, strlen(buf)); 2268 snprintf(buf, sizeof(buf), "In use %zu\n", d->malloc_used); 2269 write(fd, buf, strlen(buf)); 2270 snprintf(buf, sizeof(buf), "Guarded %zu\n", d->malloc_guarded); 2271 write(fd, buf, strlen(buf)); 2272 dump_free_chunk_info(fd, d); 2273 dump_free_page_info(fd, d); 2274 writestr(fd, 2275 "slot) hash d type page f size [free/n]\n"); 2276 for (i = 0; i < d->regions_total; i++) { 2277 if (d->r[i].p != NULL) { 2278 size_t h = hash(d->r[i].p) & 2279 (d->regions_total - 1); 2280 snprintf(buf, sizeof(buf), "%4zx) #%4zx %zd ", 2281 i, h, h - i); 2282 write(fd, buf, strlen(buf)); 2283 REALSIZE(realsize, &d->r[i]); 2284 if (realsize > MALLOC_MAXCHUNK) { 2285 putleakinfo(d->r[i].f, realsize, 1); 2286 snprintf(buf, sizeof(buf), 2287 "pages %18p %18p %zu\n", d->r[i].p, 2288 d->r[i].f, realsize); 2289 write(fd, buf, strlen(buf)); 2290 } else 2291 dump_chunk(fd, 2292 (struct chunk_info *)d->r[i].size, 2293 d->r[i].f, 0); 2294 } 2295 } 2296 dump_leaks(fd); 2297 write(fd, "\n", 1); 2298 } 2299 2300 void 2301 malloc_dump(int fd, int poolno, struct dir_info *pool) 2302 { 2303 int i; 2304 void *p; 2305 struct region_info *r; 2306 int saved_errno = errno; 2307 2308 if (pool == NULL) 2309 return; 2310 for (i = 0; i < MALLOC_DELAYED_CHUNK_MASK + 1; i++) { 2311 p = pool->delayed_chunks[i]; 2312 if (p == NULL) 2313 continue; 2314 r = find(pool, p); 2315 if (r == NULL) 2316 wrterror(pool, "bogus pointer in malloc_dump %p", p); 2317 free_bytes(pool, r, p); 2318 pool->delayed_chunks[i] = NULL; 2319 } 2320 /* XXX leak when run multiple times */ 2321 RBT_INIT(leaktree, &leakhead); 2322 malloc_dump1(fd, poolno, pool); 2323 errno = saved_errno; 2324 } 2325 DEF_WEAK(malloc_dump); 2326 2327 void 2328 malloc_gdump(int fd) 2329 { 2330 int i; 2331 int saved_errno = errno; 2332 2333 for (i = 0; i < _MALLOC_MUTEXES; i++) 2334 malloc_dump(fd, i, mopts.malloc_pool[i]); 2335 2336 errno = saved_errno; 2337 } 2338 DEF_WEAK(malloc_gdump); 2339 2340 static void 2341 malloc_exit(void) 2342 { 2343 static const char q[] = "malloc() warning: Couldn't dump stats\n"; 2344 int save_errno = errno, fd, i; 2345 char buf[100]; 2346 2347 fd = open("malloc.out", O_RDWR|O_APPEND); 2348 if (fd != -1) { 2349 snprintf(buf, sizeof(buf), "******** Start dump %s *******\n", 2350 __progname); 2351 write(fd, buf, strlen(buf)); 2352 snprintf(buf, sizeof(buf), 2353 "MT=%d I=%d F=%d U=%d J=%d R=%d X=%d C=%d cache=%u G=%zu\n", 2354 mopts.malloc_mt, mopts.internal_funcs, 2355 mopts.malloc_freenow, 2356 mopts.malloc_freeunmap, mopts.malloc_junk, 2357 mopts.malloc_realloc, mopts.malloc_xmalloc, 2358 mopts.chunk_canaries, mopts.malloc_cache, 2359 mopts.malloc_guard); 2360 write(fd, buf, strlen(buf)); 2361 2362 for (i = 0; i < _MALLOC_MUTEXES; i++) 2363 malloc_dump(fd, i, mopts.malloc_pool[i]); 2364 snprintf(buf, sizeof(buf), "******** End dump %s *******\n", 2365 __progname); 2366 write(fd, buf, strlen(buf)); 2367 close(fd); 2368 } else 2369 write(STDERR_FILENO, q, sizeof(q) - 1); 2370 errno = save_errno; 2371 } 2372 2373 #endif /* MALLOC_STATS */ 2374