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