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