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