1 /* $OpenBSD: malloc.c,v 1.86 2007/02/12 20:00:14 otto Exp $ */ 2 3 /* 4 * ---------------------------------------------------------------------------- 5 * "THE BEER-WARE LICENSE" (Revision 42): 6 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you 7 * can do whatever you want with this stuff. If we meet some day, and you think 8 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 9 * ---------------------------------------------------------------------------- 10 */ 11 12 /* 13 * Defining MALLOC_EXTRA_SANITY will enable extra checks which are 14 * related to internal conditions and consistency in malloc.c. This has 15 * a noticeable runtime performance hit, and generally will not do you 16 * any good unless you fiddle with the internals of malloc or want 17 * to catch random pointer corruption as early as possible. 18 */ 19 #ifndef MALLOC_EXTRA_SANITY 20 #undef MALLOC_EXTRA_SANITY 21 #endif 22 23 /* 24 * Defining MALLOC_STATS will enable you to call malloc_dump() and set 25 * the [dD] options in the MALLOC_OPTIONS environment variable. 26 * It has no run-time performance hit, but does pull in stdio... 27 */ 28 #ifndef MALLOC_STATS 29 #undef MALLOC_STATS 30 #endif 31 32 /* 33 * What to use for Junk. This is the byte value we use to fill with 34 * when the 'J' option is enabled. 35 */ 36 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */ 37 38 #include <sys/types.h> 39 #include <sys/time.h> 40 #include <sys/resource.h> 41 #include <sys/param.h> 42 #include <sys/mman.h> 43 #include <sys/uio.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <unistd.h> 48 #include <fcntl.h> 49 #include <limits.h> 50 #include <errno.h> 51 #include <err.h> 52 53 #include "thread_private.h" 54 55 /* 56 * The basic parameters you can tweak. 57 * 58 * malloc_pageshift pagesize = 1 << malloc_pageshift 59 * It's probably best if this is the native 60 * page size, but it shouldn't have to be. 61 * 62 * malloc_minsize minimum size of an allocation in bytes. 63 * If this is too small it's too much work 64 * to manage them. This is also the smallest 65 * unit of alignment used for the storage 66 * returned by malloc/realloc. 67 * 68 */ 69 70 #if defined(__sparc__) 71 #define malloc_pageshift 13U 72 #endif /* __sparc__ */ 73 74 #ifndef malloc_pageshift 75 #define malloc_pageshift (PGSHIFT) 76 #endif 77 78 #ifndef malloc_minsize 79 #define malloc_minsize 16UL 80 #endif 81 82 #if !defined(malloc_pagesize) 83 #define malloc_pagesize (1UL<<malloc_pageshift) 84 #endif 85 86 /* How many bits per u_long in the bitmap */ 87 #define MALLOC_BITS (NBBY * sizeof(u_long)) 88 89 90 /* 91 * No user serviceable parts behind this point. 92 * 93 * This structure describes a page worth of chunks. 94 */ 95 struct pginfo { 96 struct pginfo *next; /* next on the free list */ 97 void *page; /* Pointer to the page */ 98 u_short size; /* size of this page's chunks */ 99 u_short shift; /* How far to shift for this size chunks */ 100 u_short free; /* How many free chunks */ 101 u_short total; /* How many chunk */ 102 u_long bits[(malloc_pagesize / malloc_minsize) / MALLOC_BITS];/* Which chunks are free */ 103 }; 104 105 /* 106 * This structure describes a number of free pages. 107 */ 108 struct pgfree { 109 struct pgfree *next; /* next run of free pages */ 110 struct pgfree *prev; /* prev run of free pages */ 111 void *page; /* pointer to free pages */ 112 void *pdir; /* pointer to the base page's dir */ 113 size_t size; /* number of bytes free */ 114 }; 115 116 /* 117 * Magic values to put in the page_directory 118 */ 119 #define MALLOC_NOT_MINE ((struct pginfo*) 0) 120 #define MALLOC_FREE ((struct pginfo*) 1) 121 #define MALLOC_FIRST ((struct pginfo*) 2) 122 #define MALLOC_FOLLOW ((struct pginfo*) 3) 123 #define MALLOC_MAGIC ((struct pginfo*) 4) 124 125 #if ((1UL<<malloc_pageshift) != malloc_pagesize) 126 #error "(1UL<<malloc_pageshift) != malloc_pagesize" 127 #endif 128 129 #ifndef malloc_maxsize 130 #define malloc_maxsize ((malloc_pagesize)>>1) 131 #endif 132 133 /* A mask for the offset inside a page. */ 134 #define malloc_pagemask ((malloc_pagesize)-1) 135 136 #define pageround(foo) (((foo) + (malloc_pagemask)) & ~malloc_pagemask) 137 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift) 138 #define index2ptr(idx) ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift)) 139 140 /* Set when initialization has been done */ 141 static unsigned int malloc_started; 142 143 /* Number of free pages we cache */ 144 static unsigned int malloc_cache = 16; 145 146 /* Structure used for linking discrete directory pages. */ 147 struct pdinfo { 148 struct pginfo **base; 149 struct pdinfo *prev; 150 struct pdinfo *next; 151 u_long dirnum; 152 }; 153 static struct pdinfo *last_dir; /* Caches to the last and previous */ 154 static struct pdinfo *prev_dir; /* referenced directory pages. */ 155 156 static size_t pdi_off; 157 static u_long pdi_mod; 158 #define PD_IDX(num) ((num) / (malloc_pagesize/sizeof(struct pginfo *))) 159 #define PD_OFF(num) ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1)) 160 #define PI_IDX(index) ((index) / pdi_mod) 161 #define PI_OFF(index) ((index) % pdi_mod) 162 163 /* The last index in the page directory we care about */ 164 static u_long last_index; 165 166 /* Pointer to page directory. Allocated "as if with" malloc */ 167 static struct pginfo **page_dir; 168 169 /* Free pages line up here */ 170 static struct pgfree free_list; 171 172 /* Abort(), user doesn't handle problems. */ 173 static int malloc_abort = 2; 174 175 /* Are we trying to die ? */ 176 static int suicide; 177 178 #ifdef MALLOC_STATS 179 /* dump statistics */ 180 static int malloc_stats; 181 #endif 182 183 /* avoid outputting warnings? */ 184 static int malloc_silent; 185 186 /* always realloc ? */ 187 static int malloc_realloc; 188 189 /* mprotect free pages PROT_NONE? */ 190 static int malloc_freeprot; 191 192 /* use guard pages after allocations? */ 193 static size_t malloc_guard = 0; 194 static size_t malloc_guarded; 195 /* align pointers to end of page? */ 196 static int malloc_ptrguard; 197 198 static int malloc_hint; 199 200 /* xmalloc behaviour ? */ 201 static int malloc_xmalloc; 202 203 /* zero fill ? */ 204 static int malloc_zero; 205 206 /* junk fill ? */ 207 static int malloc_junk; 208 209 #ifdef __FreeBSD__ 210 /* utrace ? */ 211 static int malloc_utrace; 212 213 struct ut { 214 void *p; 215 size_t s; 216 void *r; 217 }; 218 219 void utrace(struct ut *, int); 220 221 #define UTRACE(a, b, c) \ 222 if (malloc_utrace) \ 223 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);} 224 #else /* !__FreeBSD__ */ 225 #define UTRACE(a,b,c) 226 #endif 227 228 /* Status of malloc. */ 229 static int malloc_active; 230 231 /* Allocated memory. */ 232 static size_t malloc_used; 233 234 /* My last break. */ 235 static caddr_t malloc_brk; 236 237 /* One location cache for free-list holders. */ 238 static struct pgfree *px; 239 240 /* Compile-time options. */ 241 char *malloc_options; 242 243 /* Name of the current public function. */ 244 static char *malloc_func; 245 246 #define MMAP(size) \ 247 mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \ 248 -1, (off_t)0) 249 250 /* 251 * Necessary function declarations. 252 */ 253 static void *imalloc(size_t size); 254 static void ifree(void *ptr); 255 static void *irealloc(void *ptr, size_t size); 256 static void *malloc_bytes(size_t size); 257 258 static struct pginfo *pginfo_list; 259 260 static struct pgfree *pgfree_list; 261 262 static struct pgfree * 263 alloc_pgfree() 264 { 265 struct pgfree *p; 266 int i; 267 268 if (pgfree_list == NULL) { 269 p = MMAP(malloc_pagesize); 270 if (p == MAP_FAILED) 271 return NULL; 272 for (i = 0; i < malloc_pagesize / sizeof(*p); i++) { 273 p[i].next = pgfree_list; 274 pgfree_list = &p[i]; 275 } 276 } 277 p = pgfree_list; 278 pgfree_list = p->next; 279 memset(p, 0, sizeof *p); 280 return p; 281 } 282 283 static struct pginfo * 284 alloc_pginfo() 285 { 286 struct pginfo *p; 287 int i; 288 289 if (pginfo_list == NULL) { 290 p = MMAP(malloc_pagesize); 291 if (p == MAP_FAILED) 292 return NULL; 293 for (i = 0; i < malloc_pagesize / sizeof(*p); i++) { 294 p[i].next = pginfo_list; 295 pginfo_list = &p[i]; 296 } 297 } 298 p = pginfo_list; 299 pginfo_list = p->next; 300 memset(p, 0, sizeof *p); 301 return p; 302 } 303 304 static void 305 put_pgfree(struct pgfree *p) 306 { 307 p->next = pgfree_list; 308 pgfree_list = p; 309 } 310 311 static void 312 put_pginfo(struct pginfo *p) 313 { 314 p->next = pginfo_list; 315 pginfo_list = p; 316 } 317 318 /* 319 * Function for page directory lookup. 320 */ 321 static int 322 pdir_lookup(u_long index, struct pdinfo ** pdi) 323 { 324 struct pdinfo *spi; 325 u_long pidx = PI_IDX(index); 326 327 if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx) 328 *pdi = last_dir; 329 else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx) 330 *pdi = prev_dir; 331 else if (last_dir != NULL && prev_dir != NULL) { 332 if ((PD_IDX(last_dir->dirnum) > pidx) ? 333 (PD_IDX(last_dir->dirnum) - pidx) : 334 (pidx - PD_IDX(last_dir->dirnum)) 335 < (PD_IDX(prev_dir->dirnum) > pidx) ? 336 (PD_IDX(prev_dir->dirnum) - pidx) : 337 (pidx - PD_IDX(prev_dir->dirnum))) 338 *pdi = last_dir; 339 else 340 *pdi = prev_dir; 341 342 if (PD_IDX((*pdi)->dirnum) > pidx) { 343 for (spi = (*pdi)->prev; 344 spi != NULL && PD_IDX(spi->dirnum) > pidx; 345 spi = spi->prev) 346 *pdi = spi; 347 if (spi != NULL) 348 *pdi = spi; 349 } else 350 for (spi = (*pdi)->next; 351 spi != NULL && PD_IDX(spi->dirnum) <= pidx; 352 spi = spi->next) 353 *pdi = spi; 354 } else { 355 *pdi = (struct pdinfo *) ((caddr_t) page_dir + pdi_off); 356 for (spi = *pdi; 357 spi != NULL && PD_IDX(spi->dirnum) <= pidx; 358 spi = spi->next) 359 *pdi = spi; 360 } 361 362 return ((PD_IDX((*pdi)->dirnum) == pidx) ? 0 : 363 (PD_IDX((*pdi)->dirnum) > pidx) ? 1 : -1); 364 } 365 366 #ifdef MALLOC_STATS 367 void 368 malloc_dump(int fd) 369 { 370 char buf[1024]; 371 struct pginfo **pd; 372 struct pgfree *pf; 373 struct pdinfo *pi; 374 u_long j; 375 376 pd = page_dir; 377 pi = (struct pdinfo *) ((caddr_t) pd + pdi_off); 378 379 /* print out all the pages */ 380 for (j = 0; j <= last_index;) { 381 snprintf(buf, sizeof buf, "%08lx %5lu ", j << malloc_pageshift, j); 382 write(fd, buf, strlen(buf)); 383 if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) { 384 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) { 385 if (!PI_OFF(++j)) { 386 if ((pi = pi->next) == NULL || 387 PD_IDX(pi->dirnum) != PI_IDX(j)) 388 break; 389 pd = pi->base; 390 j += pdi_mod; 391 } 392 } 393 j--; 394 snprintf(buf, sizeof buf, ".. %5lu not mine\n", j); 395 write(fd, buf, strlen(buf)); 396 } else if (pd[PI_OFF(j)] == MALLOC_FREE) { 397 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FREE;) { 398 if (!PI_OFF(++j)) { 399 if ((pi = pi->next) == NULL || 400 PD_IDX(pi->dirnum) != PI_IDX(j)) 401 break; 402 pd = pi->base; 403 j += pdi_mod; 404 } 405 } 406 j--; 407 snprintf(buf, sizeof buf, ".. %5lu free\n", j); 408 write(fd, buf, strlen(buf)); 409 } else if (pd[PI_OFF(j)] == MALLOC_FIRST) { 410 for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FOLLOW;) { 411 if (!PI_OFF(++j)) { 412 if ((pi = pi->next) == NULL || 413 PD_IDX(pi->dirnum) != PI_IDX(j)) 414 break; 415 pd = pi->base; 416 j += pdi_mod; 417 } 418 } 419 j--; 420 snprintf(buf, sizeof buf, ".. %5lu in use\n", j); 421 write(fd, buf, strlen(buf)); 422 } else if (pd[PI_OFF(j)] < MALLOC_MAGIC) { 423 snprintf(buf, sizeof buf, "(%p)\n", pd[PI_OFF(j)]); 424 write(fd, buf, strlen(buf)); 425 } else { 426 snprintf(buf, sizeof buf, "%p %d (of %d) x %d @ %p --> %p\n", 427 pd[PI_OFF(j)], pd[PI_OFF(j)]->free, 428 pd[PI_OFF(j)]->total, pd[PI_OFF(j)]->size, 429 pd[PI_OFF(j)]->page, pd[PI_OFF(j)]->next); 430 write(fd, buf, strlen(buf)); 431 } 432 if (!PI_OFF(++j)) { 433 if ((pi = pi->next) == NULL) 434 break; 435 pd = pi->base; 436 j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod; 437 } 438 } 439 440 for (pf = free_list.next; pf; pf = pf->next) { 441 snprintf(buf, sizeof buf, "Free: @%p [%p...%p[ %ld ->%p <-%p\n", 442 pf, pf->page, (char *)pf->page + pf->size, 443 pf->size, pf->prev, pf->next); 444 write(fd, buf, strlen(buf)); 445 if (pf == pf->next) { 446 snprintf(buf, sizeof buf, "Free_list loops\n"); 447 write(fd, buf, strlen(buf)); 448 break; 449 } 450 } 451 452 /* print out various info */ 453 snprintf(buf, sizeof buf, "Minsize\t%lu\n", malloc_minsize); 454 write(fd, buf, strlen(buf)); 455 snprintf(buf, sizeof buf, "Maxsize\t%lu\n", malloc_maxsize); 456 write(fd, buf, strlen(buf)); 457 snprintf(buf, sizeof buf, "Pagesize\t%lu\n", malloc_pagesize); 458 write(fd, buf, strlen(buf)); 459 snprintf(buf, sizeof buf, "Pageshift\t%u\n", malloc_pageshift); 460 write(fd, buf, strlen(buf)); 461 snprintf(buf, sizeof buf, "In use\t%lu\n", (u_long) malloc_used); 462 write(fd, buf, strlen(buf)); 463 snprintf(buf, sizeof buf, "Guarded\t%lu\n", (u_long) malloc_guarded); 464 write(fd, buf, strlen(buf)); 465 } 466 #endif /* MALLOC_STATS */ 467 468 extern char *__progname; 469 470 static void 471 wrterror(char *p) 472 { 473 char *q = " error: "; 474 struct iovec iov[5]; 475 476 iov[0].iov_base = __progname; 477 iov[0].iov_len = strlen(__progname); 478 iov[1].iov_base = malloc_func; 479 iov[1].iov_len = strlen(malloc_func); 480 iov[2].iov_base = q; 481 iov[2].iov_len = strlen(q); 482 iov[3].iov_base = p; 483 iov[3].iov_len = strlen(p); 484 iov[4].iov_base = "\n"; 485 iov[4].iov_len = 1; 486 writev(STDERR_FILENO, iov, 5); 487 488 suicide = 1; 489 #ifdef MALLOC_STATS 490 if (malloc_stats) 491 malloc_dump(STDERR_FILENO); 492 #endif /* MALLOC_STATS */ 493 malloc_active--; 494 if (malloc_abort) 495 abort(); 496 } 497 498 static void 499 wrtwarning(char *p) 500 { 501 char *q = " warning: "; 502 struct iovec iov[5]; 503 504 if (malloc_abort) 505 wrterror(p); 506 else if (malloc_silent) 507 return; 508 509 iov[0].iov_base = __progname; 510 iov[0].iov_len = strlen(__progname); 511 iov[1].iov_base = malloc_func; 512 iov[1].iov_len = strlen(malloc_func); 513 iov[2].iov_base = q; 514 iov[2].iov_len = strlen(q); 515 iov[3].iov_base = p; 516 iov[3].iov_len = strlen(p); 517 iov[4].iov_base = "\n"; 518 iov[4].iov_len = 1; 519 520 writev(STDERR_FILENO, iov, 5); 521 } 522 523 #ifdef MALLOC_STATS 524 static void 525 malloc_exit(void) 526 { 527 char *q = "malloc() warning: Couldn't dump stats\n"; 528 int save_errno = errno, fd; 529 530 fd = open("malloc.out", O_RDWR|O_APPEND); 531 if (fd != -1) { 532 malloc_dump(fd); 533 close(fd); 534 } else 535 write(STDERR_FILENO, q, strlen(q)); 536 errno = save_errno; 537 } 538 #endif /* MALLOC_STATS */ 539 540 /* 541 * Allocate a number of pages from the OS 542 */ 543 static void * 544 map_pages(size_t pages) 545 { 546 struct pdinfo *pi, *spi; 547 struct pginfo **pd; 548 u_long idx, pidx, lidx; 549 caddr_t result, tail; 550 u_long index, lindex; 551 void *pdregion = NULL; 552 size_t dirs, cnt; 553 554 pages <<= malloc_pageshift; 555 result = MMAP(pages + malloc_guard); 556 if (result == MAP_FAILED) { 557 #ifdef MALLOC_EXTRA_SANITY 558 wrtwarning("(ES): map_pages fails"); 559 #endif /* MALLOC_EXTRA_SANITY */ 560 errno = ENOMEM; 561 return (NULL); 562 } 563 index = ptr2index(result); 564 tail = result + pages + malloc_guard; 565 lindex = ptr2index(tail) - 1; 566 if (malloc_guard) 567 mprotect(result + pages, malloc_guard, PROT_NONE); 568 569 pidx = PI_IDX(index); 570 lidx = PI_IDX(lindex); 571 572 if (tail > malloc_brk) { 573 malloc_brk = tail; 574 last_index = lindex; 575 } 576 577 dirs = lidx - pidx; 578 579 /* Insert directory pages, if needed. */ 580 if (pdir_lookup(index, &pi) != 0) 581 dirs++; 582 583 if (dirs > 0) { 584 pdregion = MMAP(malloc_pagesize * dirs); 585 if (pdregion == MAP_FAILED) { 586 munmap(result, tail - result); 587 #ifdef MALLOC_EXTRA_SANITY 588 wrtwarning("(ES): map_pages fails"); 589 #endif 590 errno = ENOMEM; 591 return (NULL); 592 } 593 } 594 595 cnt = 0; 596 for (idx = pidx, spi = pi; idx <= lidx; idx++) { 597 if (pi == NULL || PD_IDX(pi->dirnum) != idx) { 598 pd = (struct pginfo **)((char *)pdregion + 599 cnt * malloc_pagesize); 600 cnt++; 601 memset(pd, 0, malloc_pagesize); 602 pi = (struct pdinfo *) ((caddr_t) pd + pdi_off); 603 pi->base = pd; 604 pi->prev = spi; 605 pi->next = spi->next; 606 pi->dirnum = idx * (malloc_pagesize / 607 sizeof(struct pginfo *)); 608 609 if (spi->next != NULL) 610 spi->next->prev = pi; 611 spi->next = pi; 612 } 613 if (idx > pidx && idx < lidx) { 614 pi->dirnum += pdi_mod; 615 } else if (idx == pidx) { 616 if (pidx == lidx) { 617 pi->dirnum += (u_long)(tail - result) >> 618 malloc_pageshift; 619 } else { 620 pi->dirnum += pdi_mod - PI_OFF(index); 621 } 622 } else { 623 pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1; 624 } 625 #ifdef MALLOC_EXTRA_SANITY 626 if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > idx) { 627 wrterror("(ES): pages directory overflow"); 628 errno = EFAULT; 629 return (NULL); 630 } 631 #endif /* MALLOC_EXTRA_SANITY */ 632 if (idx == pidx && pi != last_dir) { 633 prev_dir = last_dir; 634 last_dir = pi; 635 } 636 spi = pi; 637 pi = spi->next; 638 } 639 #ifdef MALLOC_EXTRA_SANITY 640 if (cnt > dirs) 641 wrtwarning("(ES): cnt > dirs"); 642 #endif /* MALLOC_EXTRA_SANITY */ 643 if (cnt < dirs) 644 munmap((char *)pdregion + cnt * malloc_pagesize, 645 (dirs - cnt) * malloc_pagesize); 646 647 return (result); 648 } 649 650 /* 651 * Initialize the world 652 */ 653 static void 654 malloc_init(void) 655 { 656 char *p, b[64]; 657 int i, j, save_errno = errno; 658 659 _MALLOC_LOCK_INIT(); 660 661 #ifdef MALLOC_EXTRA_SANITY 662 malloc_junk = 1; 663 #endif /* MALLOC_EXTRA_SANITY */ 664 665 for (i = 0; i < 3; i++) { 666 switch (i) { 667 case 0: 668 j = readlink("/etc/malloc.conf", b, sizeof b - 1); 669 if (j <= 0) 670 continue; 671 b[j] = '\0'; 672 p = b; 673 break; 674 case 1: 675 if (issetugid() == 0) 676 p = getenv("MALLOC_OPTIONS"); 677 else 678 continue; 679 break; 680 case 2: 681 p = malloc_options; 682 break; 683 default: 684 p = NULL; 685 } 686 687 for (; p != NULL && *p != '\0'; p++) { 688 switch (*p) { 689 case '>': 690 malloc_cache <<= 1; 691 break; 692 case '<': 693 malloc_cache >>= 1; 694 break; 695 case 'a': 696 malloc_abort = 0; 697 break; 698 case 'A': 699 malloc_abort = 1; 700 break; 701 #ifdef MALLOC_STATS 702 case 'd': 703 malloc_stats = 0; 704 break; 705 case 'D': 706 malloc_stats = 1; 707 break; 708 #endif /* MALLOC_STATS */ 709 case 'f': 710 malloc_freeprot = 0; 711 break; 712 case 'F': 713 malloc_freeprot = 1; 714 break; 715 case 'g': 716 malloc_guard = 0; 717 break; 718 case 'G': 719 malloc_guard = malloc_pagesize; 720 break; 721 case 'h': 722 malloc_hint = 0; 723 break; 724 case 'H': 725 malloc_hint = 1; 726 break; 727 case 'j': 728 malloc_junk = 0; 729 break; 730 case 'J': 731 malloc_junk = 1; 732 break; 733 case 'n': 734 malloc_silent = 0; 735 break; 736 case 'N': 737 malloc_silent = 1; 738 break; 739 case 'p': 740 malloc_ptrguard = 0; 741 break; 742 case 'P': 743 malloc_ptrguard = 1; 744 break; 745 case 'r': 746 malloc_realloc = 0; 747 break; 748 case 'R': 749 malloc_realloc = 1; 750 break; 751 #ifdef __FreeBSD__ 752 case 'u': 753 malloc_utrace = 0; 754 break; 755 case 'U': 756 malloc_utrace = 1; 757 break; 758 #endif /* __FreeBSD__ */ 759 case 'x': 760 malloc_xmalloc = 0; 761 break; 762 case 'X': 763 malloc_xmalloc = 1; 764 break; 765 case 'z': 766 malloc_zero = 0; 767 break; 768 case 'Z': 769 malloc_zero = 1; 770 break; 771 default: 772 j = malloc_abort; 773 malloc_abort = 0; 774 wrtwarning("unknown char in MALLOC_OPTIONS"); 775 malloc_abort = j; 776 break; 777 } 778 } 779 } 780 781 UTRACE(0, 0, 0); 782 783 /* 784 * We want junk in the entire allocation, and zero only in the part 785 * the user asked for. 786 */ 787 if (malloc_zero) 788 malloc_junk = 1; 789 790 #ifdef MALLOC_STATS 791 if (malloc_stats && (atexit(malloc_exit) == -1)) 792 wrtwarning("atexit(2) failed." 793 " Will not be able to dump malloc stats on exit"); 794 #endif /* MALLOC_STATS */ 795 796 /* Allocate one page for the page directory. */ 797 page_dir = (struct pginfo **)MMAP(malloc_pagesize); 798 799 if (page_dir == MAP_FAILED) { 800 wrterror("mmap(2) failed, check limits"); 801 errno = ENOMEM; 802 return; 803 } 804 pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1); 805 pdi_mod = pdi_off / sizeof(struct pginfo *); 806 807 last_dir = (struct pdinfo *) ((caddr_t) page_dir + pdi_off); 808 last_dir->base = page_dir; 809 last_dir->prev = last_dir->next = NULL; 810 last_dir->dirnum = malloc_pageshift; 811 812 /* Been here, done that. */ 813 malloc_started++; 814 815 /* Recalculate the cache size in bytes, and make sure it's nonzero. */ 816 if (!malloc_cache) 817 malloc_cache++; 818 malloc_cache <<= malloc_pageshift; 819 errno = save_errno; 820 } 821 822 /* 823 * Allocate a number of complete pages 824 */ 825 static void * 826 malloc_pages(size_t size) 827 { 828 void *p, *tp; 829 int i; 830 struct pginfo **pd; 831 struct pdinfo *pi; 832 u_long pidx, index; 833 struct pgfree *pf, *delay_free = NULL; 834 835 size = pageround(size) + malloc_guard; 836 837 p = NULL; 838 /* Look for free pages before asking for more */ 839 for (pf = free_list.next; pf; pf = pf->next) { 840 841 #ifdef MALLOC_EXTRA_SANITY 842 if (pf->size & malloc_pagemask) { 843 wrterror("(ES): junk length entry on free_list"); 844 errno = EFAULT; 845 return (NULL); 846 } 847 if (!pf->size) { 848 wrterror("(ES): zero length entry on free_list"); 849 errno = EFAULT; 850 return (NULL); 851 } 852 if (pf->page > (pf->page + pf->size)) { 853 wrterror("(ES): sick entry on free_list"); 854 errno = EFAULT; 855 return (NULL); 856 } 857 if ((pi = pf->pdir) == NULL) { 858 wrterror("(ES): invalid page directory on free-list"); 859 errno = EFAULT; 860 return (NULL); 861 } 862 if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) { 863 wrterror("(ES): directory index mismatch on free-list"); 864 errno = EFAULT; 865 return (NULL); 866 } 867 pd = pi->base; 868 if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) { 869 wrterror("(ES): non-free first page on free-list"); 870 errno = EFAULT; 871 return (NULL); 872 } 873 pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1); 874 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx; 875 pi = pi->next) 876 ; 877 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 878 wrterror("(ES): last page not referenced in page directory"); 879 errno = EFAULT; 880 return (NULL); 881 } 882 pd = pi->base; 883 if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) { 884 wrterror("(ES): non-free last page on free-list"); 885 errno = EFAULT; 886 return (NULL); 887 } 888 #endif /* MALLOC_EXTRA_SANITY */ 889 890 if (pf->size < size) 891 continue; 892 893 if (pf->size == size) { 894 p = pf->page; 895 pi = pf->pdir; 896 if (pf->next != NULL) 897 pf->next->prev = pf->prev; 898 pf->prev->next = pf->next; 899 delay_free = pf; 900 break; 901 } 902 p = pf->page; 903 pf->page = (char *) pf->page + size; 904 pf->size -= size; 905 pidx = PI_IDX(ptr2index(pf->page)); 906 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx; 907 pi = pi->next) 908 ; 909 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 910 wrterror("(ES): hole in directories"); 911 errno = EFAULT; 912 return (NULL); 913 } 914 tp = pf->pdir; 915 pf->pdir = pi; 916 pi = tp; 917 break; 918 } 919 920 size -= malloc_guard; 921 922 #ifdef MALLOC_EXTRA_SANITY 923 if (p != NULL && pi != NULL) { 924 pidx = PD_IDX(pi->dirnum); 925 pd = pi->base; 926 } 927 if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) { 928 wrterror("(ES): allocated non-free page on free-list"); 929 errno = EFAULT; 930 return (NULL); 931 } 932 #endif /* MALLOC_EXTRA_SANITY */ 933 934 if (p != NULL && (malloc_guard || malloc_freeprot)) 935 mprotect(p, size, PROT_READ | PROT_WRITE); 936 937 size >>= malloc_pageshift; 938 939 /* Map new pages */ 940 if (p == NULL) 941 p = map_pages(size); 942 943 if (p != NULL) { 944 index = ptr2index(p); 945 pidx = PI_IDX(index); 946 pdir_lookup(index, &pi); 947 #ifdef MALLOC_EXTRA_SANITY 948 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 949 wrterror("(ES): mapped pages not found in directory"); 950 errno = EFAULT; 951 return (NULL); 952 } 953 #endif /* MALLOC_EXTRA_SANITY */ 954 if (pi != last_dir) { 955 prev_dir = last_dir; 956 last_dir = pi; 957 } 958 pd = pi->base; 959 pd[PI_OFF(index)] = MALLOC_FIRST; 960 for (i = 1; i < size; i++) { 961 if (!PI_OFF(index + i)) { 962 pidx++; 963 pi = pi->next; 964 #ifdef MALLOC_EXTRA_SANITY 965 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 966 wrterror("(ES): hole in mapped pages directory"); 967 errno = EFAULT; 968 return (NULL); 969 } 970 #endif /* MALLOC_EXTRA_SANITY */ 971 pd = pi->base; 972 } 973 pd[PI_OFF(index + i)] = MALLOC_FOLLOW; 974 } 975 if (malloc_guard) { 976 if (!PI_OFF(index + i)) { 977 pidx++; 978 pi = pi->next; 979 #ifdef MALLOC_EXTRA_SANITY 980 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 981 wrterror("(ES): hole in mapped pages directory"); 982 errno = EFAULT; 983 return (NULL); 984 } 985 #endif /* MALLOC_EXTRA_SANITY */ 986 pd = pi->base; 987 } 988 pd[PI_OFF(index + i)] = MALLOC_FIRST; 989 } 990 malloc_used += size << malloc_pageshift; 991 malloc_guarded += malloc_guard; 992 993 if (malloc_junk) 994 memset(p, SOME_JUNK, size << malloc_pageshift); 995 } 996 if (delay_free) { 997 if (px == NULL) 998 px = delay_free; 999 else 1000 put_pgfree(delay_free); 1001 } 1002 return (p); 1003 } 1004 1005 /* 1006 * Allocate a page of fragments 1007 */ 1008 1009 static int 1010 malloc_make_chunks(int bits) 1011 { 1012 struct pginfo *bp, **pd; 1013 struct pdinfo *pi; 1014 #ifdef MALLOC_EXTRA_SANITY 1015 u_long pidx; 1016 #endif /* MALLOC_EXTRA_SANITY */ 1017 void *pp; 1018 long i, k; 1019 1020 /* Allocate a new bucket */ 1021 pp = malloc_pages((size_t)malloc_pagesize); 1022 if (pp == NULL) 1023 return (0); 1024 1025 /* Find length of admin structure */ 1026 1027 /* Don't waste more than two chunks on this */ 1028 1029 /* 1030 * If we are to allocate a memory protected page for the malloc(0) 1031 * case (when bits=0), it must be from a different page than the 1032 * pginfo page. 1033 * --> Treat it like the big chunk alloc, get a second data page. 1034 */ 1035 bp = alloc_pginfo(); 1036 if (bp == NULL) { 1037 ifree(pp); 1038 return (0); 1039 } 1040 1041 /* memory protect the page allocated in the malloc(0) case */ 1042 if (bits == 0) { 1043 bp->size = 0; 1044 bp->shift = 1; 1045 i = malloc_minsize - 1; 1046 while (i >>= 1) 1047 bp->shift++; 1048 bp->total = bp->free = malloc_pagesize >> bp->shift; 1049 bp->page = pp; 1050 1051 k = mprotect(pp, malloc_pagesize, PROT_NONE); 1052 if (k < 0) { 1053 ifree(pp); 1054 put_pginfo(bp); 1055 return (0); 1056 } 1057 } else { 1058 bp->size = (1UL << bits); 1059 bp->shift = bits; 1060 bp->total = bp->free = malloc_pagesize >> bits; 1061 bp->page = pp; 1062 } 1063 1064 /* set all valid bits in the bitmap */ 1065 k = bp->total; 1066 i = 0; 1067 1068 /* Do a bunch at a time */ 1069 for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS) 1070 bp->bits[i / MALLOC_BITS] = ~0UL; 1071 1072 for (; i < k; i++) 1073 bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS); 1074 1075 pdir_lookup(ptr2index(pp), &pi); 1076 #ifdef MALLOC_EXTRA_SANITY 1077 pidx = PI_IDX(ptr2index(pp)); 1078 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 1079 wrterror("(ES): mapped pages not found in directory"); 1080 errno = EFAULT; 1081 return (0); 1082 } 1083 #endif /* MALLOC_EXTRA_SANITY */ 1084 if (pi != last_dir) { 1085 prev_dir = last_dir; 1086 last_dir = pi; 1087 } 1088 pd = pi->base; 1089 pd[PI_OFF(ptr2index(pp))] = bp; 1090 1091 bp->next = page_dir[bits]; 1092 page_dir[bits] = bp; 1093 1094 /* MALLOC_UNLOCK */ 1095 return (1); 1096 } 1097 1098 /* 1099 * Allocate a fragment 1100 */ 1101 static void * 1102 malloc_bytes(size_t size) 1103 { 1104 int i, j; 1105 size_t k; 1106 u_long u, *lp; 1107 struct pginfo *bp; 1108 1109 /* Don't bother with anything less than this */ 1110 /* unless we have a malloc(0) requests */ 1111 if (size != 0 && size < malloc_minsize) 1112 size = malloc_minsize; 1113 1114 /* Find the right bucket */ 1115 if (size == 0) 1116 j = 0; 1117 else { 1118 j = 1; 1119 i = size - 1; 1120 while (i >>= 1) 1121 j++; 1122 } 1123 1124 /* If it's empty, make a page more of that size chunks */ 1125 if (page_dir[j] == NULL && !malloc_make_chunks(j)) 1126 return (NULL); 1127 1128 bp = page_dir[j]; 1129 1130 /* Find first word of bitmap which isn't empty */ 1131 for (lp = bp->bits; !*lp; lp++); 1132 1133 /* Find that bit, and tweak it */ 1134 u = 1; 1135 k = 0; 1136 while (!(*lp & u)) { 1137 u += u; 1138 k++; 1139 } 1140 1141 if (malloc_guard) { 1142 /* Walk to a random position. */ 1143 i = arc4random() % bp->free; 1144 while (i > 0) { 1145 u += u; 1146 k++; 1147 if (k >= MALLOC_BITS) { 1148 lp++; 1149 u = 1; 1150 k = 0; 1151 } 1152 #ifdef MALLOC_EXTRA_SANITY 1153 if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) { 1154 wrterror("chunk overflow"); 1155 errno = EFAULT; 1156 return (NULL); 1157 } 1158 #endif /* MALLOC_EXTRA_SANITY */ 1159 if (*lp & u) 1160 i--; 1161 } 1162 } 1163 *lp ^= u; 1164 1165 /* If there are no more free, remove from free-list */ 1166 if (!--bp->free) { 1167 page_dir[j] = bp->next; 1168 bp->next = NULL; 1169 } 1170 /* Adjust to the real offset of that chunk */ 1171 k += (lp - bp->bits) * MALLOC_BITS; 1172 k <<= bp->shift; 1173 1174 if (malloc_junk && bp->size != 0) 1175 memset((char *)bp->page + k, SOME_JUNK, (size_t)bp->size); 1176 1177 return ((u_char *) bp->page + k); 1178 } 1179 1180 /* 1181 * Magic so that malloc(sizeof(ptr)) is near the end of the page. 1182 */ 1183 #define PTR_GAP (malloc_pagesize - sizeof(void *)) 1184 #define PTR_SIZE (sizeof(void *)) 1185 #define PTR_ALIGNED(p) (((unsigned long)p & malloc_pagemask) == PTR_GAP) 1186 1187 /* 1188 * Allocate a piece of memory 1189 */ 1190 static void * 1191 imalloc(size_t size) 1192 { 1193 void *result; 1194 int ptralloc = 0; 1195 1196 if (!malloc_started) 1197 malloc_init(); 1198 1199 if (suicide) 1200 abort(); 1201 1202 /* does not matter if malloc_bytes fails */ 1203 if (px == NULL) 1204 px = malloc_bytes(sizeof *px); 1205 1206 if (malloc_ptrguard && size == PTR_SIZE) { 1207 ptralloc = 1; 1208 size = malloc_pagesize; 1209 } 1210 if ((size + malloc_pagesize) < size) { /* Check for overflow */ 1211 result = NULL; 1212 errno = ENOMEM; 1213 } else if (size <= malloc_maxsize) 1214 result = malloc_bytes(size); 1215 else 1216 result = malloc_pages(size); 1217 1218 if (malloc_abort == 1 && result == NULL) 1219 wrterror("allocation failed"); 1220 1221 if (malloc_zero && result != NULL) 1222 memset(result, 0, size); 1223 1224 if (result && ptralloc) 1225 return ((char *) result + PTR_GAP); 1226 return (result); 1227 } 1228 1229 /* 1230 * Change the size of an allocation. 1231 */ 1232 static void * 1233 irealloc(void *ptr, size_t size) 1234 { 1235 void *p; 1236 size_t osize; 1237 u_long index, i; 1238 struct pginfo **mp; 1239 struct pginfo **pd; 1240 struct pdinfo *pi; 1241 #ifdef MALLOC_EXTRA_SANITY 1242 u_long pidx; 1243 #endif /* MALLOC_EXTRA_SANITY */ 1244 1245 if (suicide) 1246 abort(); 1247 1248 if (!malloc_started) { 1249 wrtwarning("malloc() has never been called"); 1250 return (NULL); 1251 } 1252 if (malloc_ptrguard && PTR_ALIGNED(ptr)) { 1253 if (size <= PTR_SIZE) 1254 return (ptr); 1255 1256 p = imalloc(size); 1257 if (p) 1258 memcpy(p, ptr, PTR_SIZE); 1259 ifree(ptr); 1260 return (p); 1261 } 1262 index = ptr2index(ptr); 1263 1264 if (index < malloc_pageshift) { 1265 wrtwarning("junk pointer, too low to make sense"); 1266 return (NULL); 1267 } 1268 if (index > last_index) { 1269 wrtwarning("junk pointer, too high to make sense"); 1270 return (NULL); 1271 } 1272 pdir_lookup(index, &pi); 1273 #ifdef MALLOC_EXTRA_SANITY 1274 pidx = PI_IDX(index); 1275 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 1276 wrterror("(ES): mapped pages not found in directory"); 1277 errno = EFAULT; 1278 return (NULL); 1279 } 1280 #endif /* MALLOC_EXTRA_SANITY */ 1281 if (pi != last_dir) { 1282 prev_dir = last_dir; 1283 last_dir = pi; 1284 } 1285 pd = pi->base; 1286 mp = &pd[PI_OFF(index)]; 1287 1288 if (*mp == MALLOC_FIRST) { /* Page allocation */ 1289 1290 /* Check the pointer */ 1291 if ((u_long) ptr & malloc_pagemask) { 1292 wrtwarning("modified (page-) pointer"); 1293 return (NULL); 1294 } 1295 /* Find the size in bytes */ 1296 i = index; 1297 if (!PI_OFF(++i)) { 1298 pi = pi->next; 1299 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i)) 1300 pi = NULL; 1301 if (pi != NULL) 1302 pd = pi->base; 1303 } 1304 for (osize = malloc_pagesize; 1305 pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) { 1306 osize += malloc_pagesize; 1307 if (!PI_OFF(++i)) { 1308 pi = pi->next; 1309 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i)) 1310 pi = NULL; 1311 if (pi != NULL) 1312 pd = pi->base; 1313 } 1314 } 1315 1316 if (!malloc_realloc && size <= osize && 1317 size > osize - malloc_pagesize) { 1318 if (malloc_junk) 1319 memset((char *)ptr + size, SOME_JUNK, osize - size); 1320 return (ptr); /* ..don't do anything else. */ 1321 } 1322 } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */ 1323 1324 /* Check the pointer for sane values */ 1325 if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) { 1326 wrtwarning("modified (chunk-) pointer"); 1327 return (NULL); 1328 } 1329 /* Find the chunk index in the page */ 1330 i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift; 1331 1332 /* Verify that it isn't a free chunk already */ 1333 if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) { 1334 wrtwarning("chunk is already free"); 1335 return (NULL); 1336 } 1337 osize = (*mp)->size; 1338 1339 if (!malloc_realloc && size <= osize && 1340 (size > osize / 2 || osize == malloc_minsize)) { 1341 if (malloc_junk) 1342 memset((char *) ptr + size, SOME_JUNK, osize - size); 1343 return (ptr); /* ..don't do anything else. */ 1344 } 1345 } else { 1346 wrtwarning("irealloc: pointer to wrong page"); 1347 return (NULL); 1348 } 1349 1350 p = imalloc(size); 1351 1352 if (p != NULL) { 1353 /* copy the lesser of the two sizes, and free the old one */ 1354 /* Don't move from/to 0 sized region !!! */ 1355 if (osize != 0 && size != 0) { 1356 if (osize < size) 1357 memcpy(p, ptr, osize); 1358 else 1359 memcpy(p, ptr, size); 1360 } 1361 ifree(ptr); 1362 } 1363 return (p); 1364 } 1365 1366 /* 1367 * Free a sequence of pages 1368 */ 1369 static void 1370 free_pages(void *ptr, u_long index, struct pginfo * info) 1371 { 1372 u_long i, pidx, lidx; 1373 size_t l, cachesize = 0; 1374 struct pginfo **pd; 1375 struct pdinfo *pi, *spi; 1376 struct pgfree *pf, *pt = NULL; 1377 caddr_t tail; 1378 1379 if (info == MALLOC_FREE) { 1380 wrtwarning("page is already free"); 1381 return; 1382 } 1383 if (info != MALLOC_FIRST) { 1384 wrtwarning("free_pages: pointer to wrong page"); 1385 return; 1386 } 1387 if ((u_long) ptr & malloc_pagemask) { 1388 wrtwarning("modified (page-) pointer"); 1389 return; 1390 } 1391 /* Count how many pages and mark them free at the same time */ 1392 pidx = PI_IDX(index); 1393 pdir_lookup(index, &pi); 1394 #ifdef MALLOC_EXTRA_SANITY 1395 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 1396 wrterror("(ES): mapped pages not found in directory"); 1397 errno = EFAULT; 1398 return; 1399 } 1400 #endif /* MALLOC_EXTRA_SANITY */ 1401 1402 spi = pi; /* Save page index for start of region. */ 1403 1404 pd = pi->base; 1405 pd[PI_OFF(index)] = MALLOC_FREE; 1406 i = 1; 1407 if (!PI_OFF(index + i)) { 1408 pi = pi->next; 1409 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) 1410 pi = NULL; 1411 else 1412 pd = pi->base; 1413 } 1414 while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) { 1415 pd[PI_OFF(index + i)] = MALLOC_FREE; 1416 i++; 1417 if (!PI_OFF(index + i)) { 1418 if ((pi = pi->next) == NULL || 1419 PD_IDX(pi->dirnum) != PI_IDX(index + i)) 1420 pi = NULL; 1421 else 1422 pd = pi->base; 1423 } 1424 } 1425 1426 l = i << malloc_pageshift; 1427 1428 if (malloc_junk) 1429 memset(ptr, SOME_JUNK, l); 1430 1431 malloc_used -= l; 1432 malloc_guarded -= malloc_guard; 1433 if (malloc_guard) { 1434 #ifdef MALLOC_EXTRA_SANITY 1435 if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) { 1436 wrterror("(ES): hole in mapped pages directory"); 1437 errno = EFAULT; 1438 return; 1439 } 1440 #endif /* MALLOC_EXTRA_SANITY */ 1441 pd[PI_OFF(index + i)] = MALLOC_FREE; 1442 l += malloc_guard; 1443 } 1444 tail = (caddr_t)ptr + l; 1445 1446 if (malloc_hint) 1447 madvise(ptr, l, MADV_FREE); 1448 1449 if (malloc_freeprot) 1450 mprotect(ptr, l, PROT_NONE); 1451 1452 /* Add to free-list. */ 1453 if (px == NULL && (px = alloc_pgfree()) == NULL) 1454 goto not_return; 1455 px->page = ptr; 1456 px->pdir = spi; 1457 px->size = l; 1458 1459 if (free_list.next == NULL) { 1460 /* Nothing on free list, put this at head. */ 1461 px->next = NULL; 1462 px->prev = &free_list; 1463 free_list.next = px; 1464 pf = px; 1465 px = NULL; 1466 } else { 1467 /* 1468 * Find the right spot, leave pf pointing to the modified 1469 * entry. 1470 */ 1471 1472 /* Race ahead here, while calculating cache size. */ 1473 for (pf = free_list.next; 1474 (caddr_t)ptr > ((caddr_t)pf->page + pf->size) 1475 && pf->next != NULL; 1476 pf = pf->next) 1477 cachesize += pf->size; 1478 1479 /* Finish cache size calculation. */ 1480 pt = pf; 1481 while (pt) { 1482 cachesize += pt->size; 1483 pt = pt->next; 1484 } 1485 1486 if ((caddr_t)pf->page > tail) { 1487 /* Insert before entry */ 1488 px->next = pf; 1489 px->prev = pf->prev; 1490 pf->prev = px; 1491 px->prev->next = px; 1492 pf = px; 1493 px = NULL; 1494 } else if (((caddr_t)pf->page + pf->size) == ptr) { 1495 /* Append to the previous entry. */ 1496 cachesize -= pf->size; 1497 pf->size += l; 1498 if (pf->next != NULL && 1499 pf->next->page == ((caddr_t)pf->page + pf->size)) { 1500 /* And collapse the next too. */ 1501 pt = pf->next; 1502 pf->size += pt->size; 1503 pf->next = pt->next; 1504 if (pf->next != NULL) 1505 pf->next->prev = pf; 1506 } 1507 } else if (pf->page == tail) { 1508 /* Prepend to entry. */ 1509 cachesize -= pf->size; 1510 pf->size += l; 1511 pf->page = ptr; 1512 pf->pdir = spi; 1513 } else if (pf->next == NULL) { 1514 /* Append at tail of chain. */ 1515 px->next = NULL; 1516 px->prev = pf; 1517 pf->next = px; 1518 pf = px; 1519 px = NULL; 1520 } else { 1521 wrterror("freelist is destroyed"); 1522 errno = EFAULT; 1523 return; 1524 } 1525 } 1526 1527 if (pf->pdir != last_dir) { 1528 prev_dir = last_dir; 1529 last_dir = pf->pdir; 1530 } 1531 1532 /* Return something to OS ? */ 1533 if (pf->size > (malloc_cache - cachesize)) { 1534 1535 /* 1536 * Keep the cache intact. Notice that the '>' above guarantees that 1537 * the pf will always have at least one page afterwards. 1538 */ 1539 if (munmap((char *) pf->page + (malloc_cache - cachesize), 1540 pf->size - (malloc_cache - cachesize)) != 0) 1541 goto not_return; 1542 tail = (caddr_t)pf->page + pf->size; 1543 lidx = ptr2index(tail) - 1; 1544 pf->size = malloc_cache - cachesize; 1545 1546 index = ptr2index((caddr_t)pf->page + pf->size); 1547 1548 pidx = PI_IDX(index); 1549 if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx) 1550 prev_dir = NULL; /* Will be wiped out below ! */ 1551 1552 for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx; 1553 pi = pi->next) 1554 ; 1555 1556 spi = pi; 1557 if (pi != NULL && PD_IDX(pi->dirnum) == pidx) { 1558 pd = pi->base; 1559 1560 for (i = index; i <= lidx;) { 1561 if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) { 1562 pd[PI_OFF(i)] = MALLOC_NOT_MINE; 1563 #ifdef MALLOC_EXTRA_SANITY 1564 if (!PD_OFF(pi->dirnum)) { 1565 wrterror("(ES): pages directory underflow"); 1566 errno = EFAULT; 1567 return; 1568 } 1569 #endif /* MALLOC_EXTRA_SANITY */ 1570 pi->dirnum--; 1571 } 1572 #ifdef MALLOC_EXTRA_SANITY 1573 else 1574 wrtwarning("(ES): page already unmapped"); 1575 #endif /* MALLOC_EXTRA_SANITY */ 1576 i++; 1577 if (!PI_OFF(i)) { 1578 /* 1579 * If no page in that dir, free 1580 * directory page. 1581 */ 1582 if (!PD_OFF(pi->dirnum)) { 1583 /* Remove from list. */ 1584 if (spi == pi) 1585 spi = pi->prev; 1586 if (pi->prev != NULL) 1587 pi->prev->next = pi->next; 1588 if (pi->next != NULL) 1589 pi->next->prev = pi->prev; 1590 pi = pi->next; 1591 munmap(pd, malloc_pagesize); 1592 } else 1593 pi = pi->next; 1594 if (pi == NULL || 1595 PD_IDX(pi->dirnum) != PI_IDX(i)) 1596 break; 1597 pd = pi->base; 1598 } 1599 } 1600 if (pi && !PD_OFF(pi->dirnum)) { 1601 /* Resulting page dir is now empty. */ 1602 /* Remove from list. */ 1603 if (spi == pi) /* Update spi only if first. */ 1604 spi = pi->prev; 1605 if (pi->prev != NULL) 1606 pi->prev->next = pi->next; 1607 if (pi->next != NULL) 1608 pi->next->prev = pi->prev; 1609 pi = pi->next; 1610 munmap(pd, malloc_pagesize); 1611 } 1612 } 1613 if (pi == NULL && malloc_brk == tail) { 1614 /* Resize down the malloc upper boundary. */ 1615 last_index = index - 1; 1616 malloc_brk = index2ptr(index); 1617 } 1618 1619 /* XXX: We could realloc/shrink the pagedir here I guess. */ 1620 if (pf->size == 0) { /* Remove from free-list as well. */ 1621 if (px) 1622 put_pgfree(px); 1623 if ((px = pf->prev) != &free_list) { 1624 if (pi == NULL && last_index == (index - 1)) { 1625 if (spi == NULL) { 1626 malloc_brk = NULL; 1627 i = 11; 1628 } else { 1629 pd = spi->base; 1630 if (PD_IDX(spi->dirnum) < pidx) 1631 index = 1632 ((PD_IDX(spi->dirnum) + 1) * 1633 pdi_mod) - 1; 1634 for (pi = spi, i = index; 1635 pd[PI_OFF(i)] == MALLOC_NOT_MINE; 1636 i--) { 1637 #ifdef MALLOC_EXTRA_SANITY 1638 if (!PI_OFF(i)) { 1639 pi = pi->prev; 1640 if (pi == NULL || i == 0) 1641 break; 1642 pd = pi->base; 1643 i = (PD_IDX(pi->dirnum) + 1) * pdi_mod; 1644 } 1645 #endif /* MALLOC_EXTRA_SANITY */ 1646 } 1647 malloc_brk = index2ptr(i + 1); 1648 } 1649 last_index = i; 1650 } 1651 if ((px->next = pf->next) != NULL) 1652 px->next->prev = px; 1653 } else { 1654 if ((free_list.next = pf->next) != NULL) 1655 free_list.next->prev = &free_list; 1656 } 1657 px = pf; 1658 last_dir = prev_dir; 1659 prev_dir = NULL; 1660 } 1661 } 1662 not_return: 1663 if (pt != NULL) 1664 put_pgfree(pt); 1665 } 1666 1667 /* 1668 * Free a chunk, and possibly the page it's on, if the page becomes empty. 1669 */ 1670 1671 /* ARGSUSED */ 1672 static void 1673 free_bytes(void *ptr) 1674 { 1675 u_int8_t __arc4_getbyte(void); 1676 struct pginfo **mp, **pd, *info; 1677 struct pdinfo *pi; 1678 #ifdef MALLOC_EXTRA_SANITY 1679 u_long pidx; 1680 #endif /* MALLOC_EXTRA_SANITY */ 1681 u_long index; 1682 void *vp; 1683 long i; 1684 void *tmpptr; 1685 unsigned int tmpidx; 1686 /* pointers that we will want to free at some future time */ 1687 static void *chunk_buffer[16]; 1688 1689 1690 /* delay return, returning a random something from before instead */ 1691 tmpidx = __arc4_getbyte() % 16; 1692 tmpptr = chunk_buffer[tmpidx]; 1693 chunk_buffer[tmpidx] = ptr; 1694 ptr = tmpptr; 1695 if (!ptr) 1696 return; 1697 1698 index = ptr2index(ptr); 1699 1700 pdir_lookup(index, &pi); 1701 if (pi != last_dir) { 1702 prev_dir = last_dir; 1703 last_dir = pi; 1704 } 1705 pd = pi->base; 1706 info = pd[PI_OFF(index)]; 1707 1708 1709 /* Find the chunk number on the page */ 1710 i = ((u_long) ptr & malloc_pagemask) >> info->shift; 1711 1712 if ((u_long) ptr & ((1UL << (info->shift)) - 1)) { 1713 wrtwarning("modified (chunk-) pointer"); 1714 return; 1715 } 1716 if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) { 1717 wrtwarning("chunk is already free"); 1718 return; 1719 } 1720 if (malloc_junk && info->size != 0) 1721 memset(ptr, SOME_JUNK, (size_t)info->size); 1722 1723 info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS); 1724 info->free++; 1725 1726 if (info->size != 0) 1727 mp = page_dir + info->shift; 1728 else 1729 mp = page_dir; 1730 1731 if (info->free == 1) { 1732 /* Page became non-full */ 1733 1734 /* Insert in address order */ 1735 while (*mp != NULL && (*mp)->next != NULL && 1736 (*mp)->next->page < info->page) 1737 mp = &(*mp)->next; 1738 info->next = *mp; 1739 *mp = info; 1740 return; 1741 } 1742 if (info->free != info->total) 1743 return; 1744 1745 /* Find & remove this page in the queue */ 1746 while (*mp != info) { 1747 mp = &((*mp)->next); 1748 #ifdef MALLOC_EXTRA_SANITY 1749 if (!*mp) { 1750 wrterror("(ES): Not on queue"); 1751 errno = EFAULT; 1752 return; 1753 } 1754 #endif /* MALLOC_EXTRA_SANITY */ 1755 } 1756 *mp = info->next; 1757 1758 /* Free the page & the info structure if need be */ 1759 pdir_lookup(ptr2index(info->page), &pi); 1760 #ifdef MALLOC_EXTRA_SANITY 1761 pidx = PI_IDX(ptr2index(info->page)); 1762 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 1763 wrterror("(ES): mapped pages not found in directory"); 1764 errno = EFAULT; 1765 return; 1766 } 1767 #endif /* MALLOC_EXTRA_SANITY */ 1768 if (pi != last_dir) { 1769 prev_dir = last_dir; 1770 last_dir = pi; 1771 } 1772 pd = pi->base; 1773 pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST; 1774 1775 /* If the page was mprotected, unprotect it before releasing it */ 1776 if (info->size == 0) 1777 mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE); 1778 1779 vp = info->page; 1780 put_pginfo(info); 1781 ifree(vp); 1782 } 1783 1784 static void 1785 ifree(void *ptr) 1786 { 1787 struct pginfo *info, **pd; 1788 u_long index; 1789 #ifdef MALLOC_EXTRA_SANITY 1790 u_long pidx; 1791 #endif /* MALLOC_EXTRA_SANITY */ 1792 struct pdinfo *pi; 1793 1794 if (!malloc_started) { 1795 wrtwarning("malloc() has never been called"); 1796 return; 1797 } 1798 /* If we're already sinking, don't make matters any worse. */ 1799 if (suicide) 1800 return; 1801 1802 if (malloc_ptrguard && PTR_ALIGNED(ptr)) 1803 ptr = (char *)ptr - PTR_GAP; 1804 1805 index = ptr2index(ptr); 1806 1807 if (index < malloc_pageshift) { 1808 warnx("(%p)", ptr); 1809 wrtwarning("ifree: junk pointer, too low to make sense"); 1810 return; 1811 } 1812 if (index > last_index) { 1813 warnx("(%p)", ptr); 1814 wrtwarning("ifree: junk pointer, too high to make sense"); 1815 return; 1816 } 1817 1818 pdir_lookup(index, &pi); 1819 #ifdef MALLOC_EXTRA_SANITY 1820 pidx = PI_IDX(index); 1821 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) { 1822 wrterror("(ES): mapped pages not found in directory"); 1823 errno = EFAULT; 1824 return; 1825 } 1826 #endif /* MALLOC_EXTRA_SANITY */ 1827 if (pi != last_dir) { 1828 prev_dir = last_dir; 1829 last_dir = pi; 1830 } 1831 pd = pi->base; 1832 info = pd[PI_OFF(index)]; 1833 1834 if (info < MALLOC_MAGIC) 1835 free_pages(ptr, index, info); 1836 else 1837 free_bytes(ptr); 1838 1839 /* does not matter if malloc_bytes fails */ 1840 if (px == NULL) 1841 px = alloc_pgfree(); 1842 1843 return; 1844 } 1845 1846 /* 1847 * Common function for handling recursion. Only 1848 * print the error message once, to avoid making the problem 1849 * potentially worse. 1850 */ 1851 static void 1852 malloc_recurse(void) 1853 { 1854 static int noprint; 1855 1856 if (noprint == 0) { 1857 noprint = 1; 1858 wrtwarning("recursive call"); 1859 } 1860 malloc_active--; 1861 _MALLOC_UNLOCK(); 1862 errno = EDEADLK; 1863 } 1864 1865 /* 1866 * These are the public exported interface routines. 1867 */ 1868 void * 1869 malloc(size_t size) 1870 { 1871 void *r; 1872 1873 _MALLOC_LOCK(); 1874 malloc_func = " in malloc():"; 1875 if (malloc_active++) { 1876 malloc_recurse(); 1877 return (NULL); 1878 } 1879 r = imalloc(size); 1880 UTRACE(0, size, r); 1881 malloc_active--; 1882 _MALLOC_UNLOCK(); 1883 if (malloc_xmalloc && r == NULL) { 1884 wrterror("out of memory"); 1885 errno = ENOMEM; 1886 } 1887 return (r); 1888 } 1889 1890 void 1891 free(void *ptr) 1892 { 1893 /* This is legal. XXX quick path */ 1894 if (ptr == NULL) 1895 return; 1896 1897 _MALLOC_LOCK(); 1898 malloc_func = " in free():"; 1899 if (malloc_active++) { 1900 malloc_recurse(); 1901 return; 1902 } 1903 ifree(ptr); 1904 UTRACE(ptr, 0, 0); 1905 malloc_active--; 1906 _MALLOC_UNLOCK(); 1907 return; 1908 } 1909 1910 void * 1911 realloc(void *ptr, size_t size) 1912 { 1913 void *r; 1914 1915 _MALLOC_LOCK(); 1916 malloc_func = " in realloc():"; 1917 if (malloc_active++) { 1918 malloc_recurse(); 1919 return (NULL); 1920 } 1921 1922 if (ptr == NULL) 1923 r = imalloc(size); 1924 else 1925 r = irealloc(ptr, size); 1926 1927 UTRACE(ptr, size, r); 1928 malloc_active--; 1929 _MALLOC_UNLOCK(); 1930 if (malloc_xmalloc && r == NULL) { 1931 wrterror("out of memory"); 1932 errno = ENOMEM; 1933 } 1934 return (r); 1935 } 1936