1 /* 2 * ---------------------------------------------------------------------------- 3 * "THE BEER-WARE LICENSE" (Revision 42): 4 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you 5 * can do whatever you want with this stuff. If we meet some day, and you think 6 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 7 * ---------------------------------------------------------------------------- 8 */ 9 10 #if defined(LIBC_SCCS) && !defined(lint) 11 static char rcsid[] = "$OpenBSD: malloc.c,v 1.58 2003/07/19 23:52:27 tdeval Exp $"; 12 #endif /* LIBC_SCCS and not lint */ 13 14 /* 15 * Defining MALLOC_EXTRA_SANITY will enable extra checks which are 16 * related to internal conditions and consistency in malloc.c. This has 17 * a noticeable runtime performance hit, and generally will not do you 18 * any good unless you fiddle with the internals of malloc or want 19 * to catch random pointer corruption as early as possible. 20 */ 21 #ifndef MALLOC_EXTRA_SANITY 22 #undef MALLOC_EXTRA_SANITY 23 #endif 24 25 /* 26 * Defining MALLOC_STATS will enable you to call malloc_dump() and set 27 * the [dD] options in the MALLOC_OPTIONS environment variable. 28 * It has no run-time performance hit, but does pull in stdio... 29 */ 30 #ifndef MALLOC_STATS 31 #undef MALLOC_STATS 32 #endif 33 34 /* 35 * What to use for Junk. This is the byte value we use to fill with 36 * when the 'J' option is enabled. 37 */ 38 #define SOME_JUNK 0xd0 /* as in "Duh" :-) */ 39 40 #include <sys/types.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 52 #include "thread_private.h" 53 54 /* 55 * The basic parameters you can tweak. 56 * 57 * malloc_pageshift pagesize = 1 << malloc_pageshift 58 * It's probably best if this is the native 59 * page size, but it shouldn't have to be. 60 * 61 * malloc_minsize minimum size of an allocation in bytes. 62 * If this is too small it's too much work 63 * to manage them. This is also the smallest 64 * unit of alignment used for the storage 65 * returned by malloc/realloc. 66 * 67 */ 68 69 #if defined(__OpenBSD__) && defined(__sparc__) 70 # define malloc_pageshift 13U 71 #endif /* __OpenBSD__ */ 72 73 /* 74 * No user serviceable parts behind this point. 75 * 76 * This structure describes a page worth of chunks. 77 */ 78 79 struct pginfo { 80 struct pginfo *next; /* next on the free list */ 81 void *page; /* Pointer to the page */ 82 u_short size; /* size of this page's chunks */ 83 u_short shift; /* How far to shift for this size chunks */ 84 u_short free; /* How many free chunks */ 85 u_short total; /* How many chunk */ 86 u_long bits[1]; /* Which chunks are free */ 87 }; 88 89 /* 90 * This structure describes a number of free pages. 91 */ 92 93 struct pgfree { 94 struct pgfree *next; /* next run of free pages */ 95 struct pgfree *prev; /* prev run of free pages */ 96 void *page; /* pointer to free pages */ 97 void *end; /* pointer to end of free pages */ 98 u_long size; /* number of bytes free */ 99 }; 100 101 /* 102 * How many bits per u_long in the bitmap. 103 * Change only if not 8 bits/byte 104 */ 105 #define MALLOC_BITS (8*sizeof(u_long)) 106 107 /* 108 * Magic values to put in the page_directory 109 */ 110 #define MALLOC_NOT_MINE ((struct pginfo*) 0) 111 #define MALLOC_FREE ((struct pginfo*) 1) 112 #define MALLOC_FIRST ((struct pginfo*) 2) 113 #define MALLOC_FOLLOW ((struct pginfo*) 3) 114 #define MALLOC_MAGIC ((struct pginfo*) 4) 115 116 #ifndef malloc_pageshift 117 #define malloc_pageshift (PGSHIFT) 118 #endif 119 120 #ifndef malloc_minsize 121 #define malloc_minsize 16U 122 #endif 123 124 #ifndef malloc_pageshift 125 #error "malloc_pageshift undefined" 126 #endif 127 128 #if !defined(malloc_pagesize) 129 #define malloc_pagesize (1UL<<malloc_pageshift) 130 #endif 131 132 #if ((1UL<<malloc_pageshift) != malloc_pagesize) 133 #error "(1UL<<malloc_pageshift) != malloc_pagesize" 134 #endif 135 136 #ifndef malloc_maxsize 137 #define malloc_maxsize ((malloc_pagesize)>>1) 138 #endif 139 140 /* A mask for the offset inside a page. */ 141 #define malloc_pagemask ((malloc_pagesize)-1) 142 143 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask))) 144 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo) 145 146 /* fd of /dev/zero */ 147 #ifdef USE_DEV_ZERO 148 static int fdzero; 149 #define MMAP_FD fdzero 150 #define INIT_MMAP() \ 151 { if ((fdzero=open("/dev/zero", O_RDWR, 0000)) == -1) \ 152 wrterror("open of /dev/zero"); } 153 #else 154 #define MMAP_FD (-1) 155 #define INIT_MMAP() 156 #endif 157 158 /* Set when initialization has been done */ 159 static unsigned int malloc_started; 160 161 /* Number of free pages we cache */ 162 static unsigned int malloc_cache = 16; 163 164 /* The offset from pagenumber to index into the page directory */ 165 static u_long malloc_origo; 166 167 /* The last index in the page directory we care about */ 168 static u_long last_index; 169 170 /* Pointer to page directory. Allocated "as if with" malloc */ 171 static struct pginfo **page_dir; 172 173 /* How many slots in the page directory */ 174 static size_t malloc_ninfo; 175 176 /* Free pages line up here */ 177 static struct pgfree free_list; 178 179 /* Abort(), user doesn't handle problems. */ 180 static int malloc_abort; 181 182 /* Are we trying to die ? */ 183 static int suicide; 184 185 #ifdef MALLOC_STATS 186 /* dump statistics */ 187 static int malloc_stats; 188 #endif 189 190 /* avoid outputting warnings? */ 191 static int malloc_silent; 192 193 /* always realloc ? */ 194 static int malloc_realloc; 195 196 #if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE)) 197 /* pass the kernel a hint on free pages ? */ 198 static int malloc_hint; 199 #endif 200 201 /* xmalloc behaviour ? */ 202 static int malloc_xmalloc; 203 204 /* zero fill ? */ 205 static int malloc_zero; 206 207 /* junk fill ? */ 208 static int malloc_junk; 209 210 #ifdef __FreeBSD__ 211 /* utrace ? */ 212 static int malloc_utrace; 213 214 struct ut { void *p; size_t s; void *r; }; 215 216 void utrace(struct ut *, int); 217 218 #define UTRACE(a, b, c) \ 219 if (malloc_utrace) \ 220 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);} 221 #else /* !__FreeBSD__ */ 222 #define UTRACE(a,b,c) 223 #endif 224 225 /* my last break. */ 226 static void *malloc_brk; 227 228 /* one location cache for free-list holders */ 229 static struct pgfree *px; 230 231 /* compile-time options */ 232 char *malloc_options; 233 234 /* Name of the current public function */ 235 static char *malloc_func; 236 237 /* Macro for mmap */ 238 #define MMAP(size) \ 239 mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \ 240 MMAP_FD, (off_t)0) 241 242 /* 243 * Necessary function declarations 244 */ 245 static int extend_pgdir(u_long index); 246 static void *imalloc(size_t size); 247 static void ifree(void *ptr); 248 static void *irealloc(void *ptr, size_t size); 249 static void *malloc_bytes(size_t size); 250 251 #ifdef MALLOC_STATS 252 void 253 malloc_dump(fd) 254 FILE *fd; 255 { 256 struct pginfo **pd; 257 struct pgfree *pf; 258 int j; 259 260 pd = page_dir; 261 262 /* print out all the pages */ 263 for(j=0;j<=last_index;j++) { 264 fprintf(fd, "%08lx %5d ", (j+malloc_origo) << malloc_pageshift, j); 265 if (pd[j] == MALLOC_NOT_MINE) { 266 for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++) 267 ; 268 j--; 269 fprintf(fd, ".. %5d not mine\n", j); 270 } else if (pd[j] == MALLOC_FREE) { 271 for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++) 272 ; 273 j--; 274 fprintf(fd, ".. %5d free\n", j); 275 } else if (pd[j] == MALLOC_FIRST) { 276 for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++) 277 ; 278 j--; 279 fprintf(fd, ".. %5d in use\n", j); 280 } else if (pd[j] < MALLOC_MAGIC) { 281 fprintf(fd, "(%p)\n", pd[j]); 282 } else { 283 fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n", 284 pd[j], pd[j]->free, pd[j]->total, 285 pd[j]->size, pd[j]->page, pd[j]->next); 286 } 287 } 288 289 for(pf=free_list.next; pf; pf=pf->next) { 290 fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n", 291 pf, pf->page, pf->end, pf->size, pf->prev, pf->next); 292 if (pf == pf->next) { 293 fprintf(fd, "Free_list loops.\n"); 294 break; 295 } 296 } 297 298 /* print out various info */ 299 fprintf(fd, "Minsize\t%d\n", malloc_minsize); 300 fprintf(fd, "Maxsize\t%d\n", malloc_maxsize); 301 fprintf(fd, "Pagesize\t%lu\n", (u_long)malloc_pagesize); 302 fprintf(fd, "Pageshift\t%d\n", malloc_pageshift); 303 fprintf(fd, "FirstPage\t%ld\n", malloc_origo); 304 fprintf(fd, "LastPage\t%ld %lx\n", last_index+malloc_pageshift, 305 (last_index + malloc_pageshift) << malloc_pageshift); 306 fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift); 307 } 308 #endif /* MALLOC_STATS */ 309 310 extern char *__progname; 311 312 static void 313 wrterror(p) 314 char *p; 315 { 316 char *q = " error: "; 317 struct iovec iov[4]; 318 319 iov[0].iov_base = __progname; 320 iov[0].iov_len = strlen(__progname); 321 iov[1].iov_base = malloc_func; 322 iov[1].iov_len = strlen(malloc_func); 323 iov[2].iov_base = q; 324 iov[2].iov_len = strlen(q); 325 iov[3].iov_base = p; 326 iov[3].iov_len = strlen(p); 327 writev(STDERR_FILENO, iov, 4); 328 329 suicide = 1; 330 #ifdef MALLOC_STATS 331 if (malloc_stats) 332 malloc_dump(stderr); 333 #endif /* MALLOC_STATS */ 334 abort(); 335 } 336 337 static void 338 wrtwarning(p) 339 char *p; 340 { 341 char *q = " warning: "; 342 struct iovec iov[4]; 343 344 if (malloc_abort) 345 wrterror(p); 346 else if (malloc_silent) 347 return; 348 349 iov[0].iov_base = __progname; 350 iov[0].iov_len = strlen(__progname); 351 iov[1].iov_base = malloc_func; 352 iov[1].iov_len = strlen(malloc_func); 353 iov[2].iov_base = q; 354 iov[2].iov_len = strlen(q); 355 iov[3].iov_base = p; 356 iov[3].iov_len = strlen(p); 357 writev(STDERR_FILENO, iov, 4); 358 } 359 360 #ifdef MALLOC_STATS 361 static void 362 malloc_exit() 363 { 364 FILE *fd = fopen("malloc.out", "a"); 365 char *q = "malloc() warning: Couldn't dump stats.\n"; 366 if (fd != NULL) { 367 malloc_dump(fd); 368 fclose(fd); 369 } else 370 write(STDERR_FILENO, q, strlen(q)); 371 } 372 #endif /* MALLOC_STATS */ 373 374 375 /* 376 * Allocate a number of pages from the OS 377 */ 378 static void * 379 map_pages(pages) 380 size_t pages; 381 { 382 caddr_t result, tail; 383 384 result = (caddr_t)pageround((u_long)sbrk(0)); 385 pages <<= malloc_pageshift; 386 if (pages > SIZE_T_MAX - (size_t)result) { 387 #ifdef MALLOC_EXTRA_SANITY 388 wrtwarning("(ES): overflow in map_pages fails\n"); 389 #endif /* MALLOC_EXTRA_SANITY */ 390 errno = ENOMEM; 391 return (NULL); 392 } 393 tail = result + pages; 394 395 if (brk(tail) == (char *)-1) { 396 #ifdef MALLOC_EXTRA_SANITY 397 wrtwarning("(ES): map_pages fails\n"); 398 #endif /* MALLOC_EXTRA_SANITY */ 399 return (NULL); 400 } 401 402 last_index = ptr2index(tail) - 1; 403 malloc_brk = tail; 404 405 if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index)) 406 return (NULL); 407 408 return (result); 409 } 410 411 /* 412 * Extend page directory 413 */ 414 static int 415 extend_pgdir(index) 416 u_long index; 417 { 418 struct pginfo **new, **old; 419 size_t i, oldlen; 420 421 /* Make it this many pages */ 422 i = index * sizeof *page_dir; 423 i /= malloc_pagesize; 424 i += 2; 425 426 /* remember the old mapping size */ 427 oldlen = malloc_ninfo * sizeof *page_dir; 428 429 /* 430 * NOTE: we allocate new pages and copy the directory rather than tempt 431 * fate by trying to "grow" the region.. There is nothing to prevent 432 * us from accidently re-mapping space that's been allocated by our caller 433 * via dlopen() or other mmap(). 434 * 435 * The copy problem is not too bad, as there is 4K of page index per 436 * 4MB of malloc arena. 437 * 438 * We can totally avoid the copy if we open a file descriptor to associate 439 * the anon mappings with. Then, when we remap the pages at the new 440 * address, the old pages will be "magically" remapped.. But this means 441 * keeping open a "secret" file descriptor..... 442 */ 443 444 /* Get new pages */ 445 new = (struct pginfo**) MMAP(i * malloc_pagesize); 446 if (new == MAP_FAILED) 447 return (0); 448 449 /* Copy the old stuff */ 450 memcpy(new, page_dir, 451 malloc_ninfo * sizeof *page_dir); 452 453 /* register the new size */ 454 malloc_ninfo = i * malloc_pagesize / sizeof *page_dir; 455 456 /* swap the pointers */ 457 old = page_dir; 458 page_dir = new; 459 460 /* Now free the old stuff */ 461 munmap(old, oldlen); 462 return (1); 463 } 464 465 /* 466 * Initialize the world 467 */ 468 static void 469 malloc_init () 470 { 471 char *p, b[64]; 472 int i, j; 473 int save_errno = errno; 474 475 _MALLOC_LOCK_INIT(); 476 477 INIT_MMAP(); 478 479 #ifdef MALLOC_EXTRA_SANITY 480 malloc_junk = 1; 481 #endif /* MALLOC_EXTRA_SANITY */ 482 483 for (i = 0; i < 3; i++) { 484 if (i == 0) { 485 j = readlink("/etc/malloc.conf", b, sizeof b - 1); 486 if (j <= 0) 487 continue; 488 b[j] = '\0'; 489 p = b; 490 } else if (i == 1) { 491 if (issetugid() == 0) 492 p = getenv("MALLOC_OPTIONS"); 493 else 494 continue; 495 } else if (i == 2) { 496 p = malloc_options; 497 } 498 for (; p != NULL && *p != '\0'; p++) { 499 switch (*p) { 500 case '>': malloc_cache <<= 1; break; 501 case '<': malloc_cache >>= 1; break; 502 case 'a': malloc_abort = 0; break; 503 case 'A': malloc_abort = 1; break; 504 #ifdef MALLOC_STATS 505 case 'd': malloc_stats = 0; break; 506 case 'D': malloc_stats = 1; break; 507 #endif /* MALLOC_STATS */ 508 #if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE)) 509 case 'h': malloc_hint = 0; break; 510 case 'H': malloc_hint = 1; break; 511 #endif /* __FreeBSD__ */ 512 case 'r': malloc_realloc = 0; break; 513 case 'R': malloc_realloc = 1; break; 514 case 'j': malloc_junk = 0; break; 515 case 'J': malloc_junk = 1; break; 516 case 'n': malloc_silent = 0; break; 517 case 'N': malloc_silent = 1; break; 518 #ifdef __FreeBSD__ 519 case 'u': malloc_utrace = 0; break; 520 case 'U': malloc_utrace = 1; break; 521 #endif /* __FreeBSD__ */ 522 case 'x': malloc_xmalloc = 0; break; 523 case 'X': malloc_xmalloc = 1; break; 524 case 'z': malloc_zero = 0; break; 525 case 'Z': malloc_zero = 1; break; 526 default: 527 j = malloc_abort; 528 malloc_abort = 0; 529 wrtwarning("unknown char in MALLOC_OPTIONS\n"); 530 malloc_abort = j; 531 break; 532 } 533 } 534 } 535 536 UTRACE(0, 0, 0); 537 538 /* 539 * We want junk in the entire allocation, and zero only in the part 540 * the user asked for. 541 */ 542 if (malloc_zero) 543 malloc_junk=1; 544 545 #ifdef MALLOC_STATS 546 if (malloc_stats && (atexit(malloc_exit) == -1)) 547 wrtwarning("atexit(2) failed. Will not be able to dump malloc stats on exit.\n"); 548 #endif /* MALLOC_STATS */ 549 550 /* Allocate one page for the page directory */ 551 page_dir = (struct pginfo **) MMAP(malloc_pagesize); 552 553 if (page_dir == MAP_FAILED) 554 wrterror("mmap(2) failed, check limits.\n"); 555 556 /* 557 * We need a maximum of malloc_pageshift buckets, steal these from the 558 * front of the page_directory; 559 */ 560 malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift; 561 malloc_origo -= malloc_pageshift; 562 563 malloc_ninfo = malloc_pagesize / sizeof *page_dir; 564 565 /* Been here, done that */ 566 malloc_started++; 567 568 /* Recalculate the cache size in bytes, and make sure it's nonzero */ 569 570 if (!malloc_cache) 571 malloc_cache++; 572 573 malloc_cache <<= malloc_pageshift; 574 575 /* 576 * This is a nice hack from Kaleb Keithly (kaleb@x.org). 577 * We can sbrk(2) further back when we keep this on a low address. 578 */ 579 px = (struct pgfree *) imalloc (sizeof *px); 580 errno = save_errno; 581 } 582 583 /* 584 * Allocate a number of complete pages 585 */ 586 static void * 587 malloc_pages(size) 588 size_t size; 589 { 590 void *p, *delay_free = NULL; 591 int i; 592 struct pgfree *pf; 593 u_long index; 594 595 size = pageround(size); 596 597 p = NULL; 598 /* Look for free pages before asking for more */ 599 for(pf = free_list.next; pf; pf = pf->next) { 600 601 #ifdef MALLOC_EXTRA_SANITY 602 if (pf->size & malloc_pagemask) 603 wrterror("(ES): junk length entry on free_list\n"); 604 if (!pf->size) 605 wrterror("(ES): zero length entry on free_list\n"); 606 if (pf->page == pf->end) 607 wrterror("(ES): zero entry on free_list\n"); 608 if (pf->page > pf->end) 609 wrterror("(ES): sick entry on free_list\n"); 610 if ((void*)pf->page >= (void*)sbrk(0)) 611 wrterror("(ES): entry on free_list past brk\n"); 612 if (page_dir[ptr2index(pf->page)] != MALLOC_FREE) 613 wrterror("(ES): non-free first page on free-list\n"); 614 if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE) 615 wrterror("(ES): non-free last page on free-list\n"); 616 #endif /* MALLOC_EXTRA_SANITY */ 617 618 if (pf->size < size) 619 continue; 620 621 if (pf->size == size) { 622 p = pf->page; 623 if (pf->next != NULL) 624 pf->next->prev = pf->prev; 625 pf->prev->next = pf->next; 626 delay_free = pf; 627 break; 628 } 629 630 p = pf->page; 631 pf->page = (char *)pf->page + size; 632 pf->size -= size; 633 break; 634 } 635 636 #ifdef MALLOC_EXTRA_SANITY 637 if (p != NULL && page_dir[ptr2index(p)] != MALLOC_FREE) 638 wrterror("(ES): allocated non-free page on free-list\n"); 639 #endif /* MALLOC_EXTRA_SANITY */ 640 641 size >>= malloc_pageshift; 642 643 /* Map new pages */ 644 if (p == NULL) 645 p = map_pages(size); 646 647 if (p != NULL) { 648 649 index = ptr2index(p); 650 page_dir[index] = MALLOC_FIRST; 651 for (i=1;i<size;i++) 652 page_dir[index+i] = MALLOC_FOLLOW; 653 654 if (malloc_junk) 655 memset(p, SOME_JUNK, size << malloc_pageshift); 656 } 657 658 if (delay_free) { 659 if (px == NULL) 660 px = delay_free; 661 else 662 ifree(delay_free); 663 } 664 665 return (p); 666 } 667 668 /* 669 * Allocate a page of fragments 670 */ 671 672 static __inline__ int 673 malloc_make_chunks(bits) 674 int bits; 675 { 676 struct pginfo *bp; 677 void *pp; 678 int i, k, l; 679 680 /* Allocate a new bucket */ 681 pp = malloc_pages((size_t)malloc_pagesize); 682 if (pp == NULL) 683 return (0); 684 685 /* Find length of admin structure */ 686 l = sizeof *bp - sizeof(u_long); 687 l += sizeof(u_long) * 688 (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS); 689 690 /* Don't waste more than two chunks on this */ 691 /* 692 * If we are to allocate a memory protected page for the malloc(0) 693 * case (when bits=0), it must be from a different page than the 694 * pginfo page. 695 * --> Treat it like the big chunk alloc, get a second data page. 696 */ 697 if (bits != 0 && (1UL<<(bits)) <= l+l) { 698 bp = (struct pginfo *)pp; 699 } else { 700 bp = (struct pginfo *)imalloc(l); 701 if (bp == NULL) { 702 ifree(pp); 703 return (0); 704 } 705 } 706 707 /* memory protect the page allocated in the malloc(0) case */ 708 if (bits == 0) { 709 710 bp->size = 0; 711 bp->shift = 1; 712 i = malloc_minsize-1; 713 while (i >>= 1) 714 bp->shift++; 715 bp->total = bp->free = malloc_pagesize >> bp->shift; 716 bp->page = pp; 717 718 k = mprotect(pp, malloc_pagesize, PROT_NONE); 719 if (k < 0) { 720 ifree(pp); 721 ifree(bp); 722 return (0); 723 } 724 } else { 725 bp->size = (1UL<<bits); 726 bp->shift = bits; 727 bp->total = bp->free = malloc_pagesize >> bits; 728 bp->page = pp; 729 } 730 731 /* set all valid bits in the bitmap */ 732 k = bp->total; 733 i = 0; 734 735 /* Do a bunch at a time */ 736 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS) 737 bp->bits[i / MALLOC_BITS] = ~0UL; 738 739 for(; i < k; i++) 740 bp->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS); 741 742 if (bp == bp->page) { 743 /* Mark the ones we stole for ourselves */ 744 for(i=0;l > 0;i++) { 745 bp->bits[i/MALLOC_BITS] &= ~(1UL<<(i%MALLOC_BITS)); 746 bp->free--; 747 bp->total--; 748 l -= (1 << bits); 749 } 750 } 751 752 /* MALLOC_LOCK */ 753 754 page_dir[ptr2index(pp)] = bp; 755 756 bp->next = page_dir[bits]; 757 page_dir[bits] = bp; 758 759 /* MALLOC_UNLOCK */ 760 761 return (1); 762 } 763 764 /* 765 * Allocate a fragment 766 */ 767 static void * 768 malloc_bytes(size) 769 size_t size; 770 { 771 int i,j; 772 u_long u; 773 struct pginfo *bp; 774 int k; 775 u_long *lp; 776 777 /* Don't bother with anything less than this */ 778 /* unless we have a malloc(0) requests */ 779 if (size != 0 && size < malloc_minsize) 780 size = malloc_minsize; 781 782 /* Find the right bucket */ 783 if (size == 0) 784 j=0; 785 else { 786 j = 1; 787 i = size-1; 788 while (i >>= 1) 789 j++; 790 } 791 792 /* If it's empty, make a page more of that size chunks */ 793 if (page_dir[j] == NULL && !malloc_make_chunks(j)) 794 return (NULL); 795 796 bp = page_dir[j]; 797 798 /* Find first word of bitmap which isn't empty */ 799 for (lp = bp->bits; !*lp; lp++) 800 ; 801 802 /* Find that bit, and tweak it */ 803 u = 1; 804 k = 0; 805 while (!(*lp & u)) { 806 u += u; 807 k++; 808 } 809 *lp ^= u; 810 811 /* If there are no more free, remove from free-list */ 812 if (!--bp->free) { 813 page_dir[j] = bp->next; 814 bp->next = NULL; 815 } 816 817 /* Adjust to the real offset of that chunk */ 818 k += (lp-bp->bits)*MALLOC_BITS; 819 k <<= bp->shift; 820 821 if (malloc_junk && bp->size != 0) 822 memset((char *)bp->page + k, SOME_JUNK, bp->size); 823 824 return ((u_char *)bp->page + k); 825 } 826 827 /* 828 * Allocate a piece of memory 829 */ 830 static void * 831 imalloc(size) 832 size_t size; 833 { 834 void *result; 835 836 if (!malloc_started) 837 malloc_init(); 838 839 if (suicide) 840 abort(); 841 842 if ((size + malloc_pagesize) < size) { /* Check for overflow */ 843 result = NULL; 844 errno = ENOMEM; 845 } 846 else if (size <= malloc_maxsize) 847 result = malloc_bytes(size); 848 else 849 result = malloc_pages(size); 850 851 if (malloc_abort && result == NULL) 852 wrterror("allocation failed.\n"); 853 854 if (malloc_zero && result != NULL) 855 memset(result, 0, size); 856 857 return (result); 858 } 859 860 /* 861 * Change the size of an allocation. 862 */ 863 static void * 864 irealloc(ptr, size) 865 void *ptr; 866 size_t size; 867 { 868 void *p; 869 u_long osize, index; 870 struct pginfo **mp; 871 int i; 872 873 if (suicide) 874 abort(); 875 876 if (!malloc_started) { 877 wrtwarning("malloc() has never been called.\n"); 878 return (NULL); 879 } 880 881 index = ptr2index(ptr); 882 883 if (index < malloc_pageshift) { 884 wrtwarning("junk pointer, too low to make sense.\n"); 885 return (NULL); 886 } 887 888 if (index > last_index) { 889 wrtwarning("junk pointer, too high to make sense.\n"); 890 return (NULL); 891 } 892 893 mp = &page_dir[index]; 894 895 if (*mp == MALLOC_FIRST) { /* Page allocation */ 896 897 /* Check the pointer */ 898 if ((u_long)ptr & malloc_pagemask) { 899 wrtwarning("modified (page-) pointer.\n"); 900 return (NULL); 901 } 902 903 /* Find the size in bytes */ 904 for (osize = malloc_pagesize; *(++mp) == MALLOC_FOLLOW;) 905 osize += malloc_pagesize; 906 907 if (!malloc_realloc && /* Unless we have to, */ 908 size <= osize && /* .. or are too small, */ 909 size > (osize - malloc_pagesize)) { /* .. or can free a page, */ 910 if (malloc_junk) 911 memset((char *)ptr + size, SOME_JUNK, osize-size); 912 return (ptr); /* ..don't do anything else. */ 913 } 914 915 } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */ 916 917 /* Check the pointer for sane values */ 918 if ((u_long)ptr & ((1UL<<((*mp)->shift))-1)) { 919 wrtwarning("modified (chunk-) pointer.\n"); 920 return (NULL); 921 } 922 923 /* Find the chunk index in the page */ 924 i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift; 925 926 /* Verify that it isn't a free chunk already */ 927 if ((*mp)->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) { 928 wrtwarning("chunk is already free.\n"); 929 return (NULL); 930 } 931 932 osize = (*mp)->size; 933 934 if (!malloc_realloc && /* Unless we have to, */ 935 size <= osize && /* ..or are too small, */ 936 (size > osize/2 || /* ..or could use a smaller size, */ 937 osize == malloc_minsize)) { /* ..(if there is one) */ 938 if (malloc_junk) 939 memset((char *)ptr + size, SOME_JUNK, osize-size); 940 return (ptr); /* ..don't do anything else. */ 941 } 942 943 } else { 944 wrtwarning("pointer to wrong page.\n"); 945 return (NULL); 946 } 947 948 p = imalloc(size); 949 950 if (p != NULL) { 951 /* copy the lesser of the two sizes, and free the old one */ 952 /* Don't move from/to 0 sized region !!! */ 953 if (osize != 0 && size != 0) { 954 if (osize < size) 955 memcpy(p, ptr, osize); 956 else 957 memcpy(p, ptr, size); 958 } 959 ifree(ptr); 960 } 961 return (p); 962 } 963 964 /* 965 * Free a sequence of pages 966 */ 967 968 static __inline__ void 969 free_pages(ptr, index, info) 970 void *ptr; 971 int index; 972 struct pginfo *info; 973 { 974 int i; 975 struct pgfree *pf, *pt=NULL; 976 u_long l; 977 void *tail; 978 979 if (info == MALLOC_FREE) { 980 wrtwarning("page is already free.\n"); 981 return; 982 } 983 984 if (info != MALLOC_FIRST) { 985 wrtwarning("pointer to wrong page.\n"); 986 return; 987 } 988 989 if ((u_long)ptr & malloc_pagemask) { 990 wrtwarning("modified (page-) pointer.\n"); 991 return; 992 } 993 994 /* Count how many pages and mark them free at the same time */ 995 page_dir[index] = MALLOC_FREE; 996 for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++) 997 page_dir[index + i] = MALLOC_FREE; 998 999 l = i << malloc_pageshift; 1000 1001 if (malloc_junk) 1002 memset(ptr, SOME_JUNK, l); 1003 1004 #if defined(__FreeBSD__) || (defined(__OpenBSD__) && defined(MADV_FREE)) 1005 if (malloc_hint) 1006 madvise(ptr, l, MADV_FREE); 1007 #endif 1008 1009 tail = (char *)ptr+l; 1010 1011 /* add to free-list */ 1012 if (px == NULL) 1013 px = imalloc(sizeof *px); /* This cannot fail... */ 1014 px->page = ptr; 1015 px->end = tail; 1016 px->size = l; 1017 1018 if (free_list.next == NULL) { 1019 1020 /* Nothing on free list, put this at head */ 1021 px->next = free_list.next; 1022 px->prev = &free_list; 1023 free_list.next = px; 1024 pf = px; 1025 px = NULL; 1026 1027 } else { 1028 1029 /* Find the right spot, leave pf pointing to the modified entry. */ 1030 1031 for(pf = free_list.next; pf->end < ptr && pf->next != NULL; 1032 pf = pf->next) 1033 ; /* Race ahead here */ 1034 1035 if (pf->page > tail) { 1036 /* Insert before entry */ 1037 px->next = pf; 1038 px->prev = pf->prev; 1039 pf->prev = px; 1040 px->prev->next = px; 1041 pf = px; 1042 px = NULL; 1043 } else if (pf->end == ptr ) { 1044 /* Append to the previous entry */ 1045 pf->end = (char *)pf->end + l; 1046 pf->size += l; 1047 if (pf->next != NULL && pf->end == pf->next->page ) { 1048 /* And collapse the next too. */ 1049 pt = pf->next; 1050 pf->end = pt->end; 1051 pf->size += pt->size; 1052 pf->next = pt->next; 1053 if (pf->next != NULL) 1054 pf->next->prev = pf; 1055 } 1056 } else if (pf->page == tail) { 1057 /* Prepend to entry */ 1058 pf->size += l; 1059 pf->page = ptr; 1060 } else if (pf->next == NULL) { 1061 /* Append at tail of chain */ 1062 px->next = NULL; 1063 px->prev = pf; 1064 pf->next = px; 1065 pf = px; 1066 px = NULL; 1067 } else { 1068 wrterror("freelist is destroyed.\n"); 1069 } 1070 } 1071 1072 /* Return something to OS ? */ 1073 if (pf->next == NULL && /* If we're the last one, */ 1074 pf->size > malloc_cache && /* ..and the cache is full, */ 1075 pf->end == malloc_brk && /* ..and none behind us, */ 1076 malloc_brk == sbrk(0)) { /* ..and it's OK to do... */ 1077 1078 /* 1079 * Keep the cache intact. Notice that the '>' above guarantees that 1080 * the pf will always have at least one page afterwards. 1081 */ 1082 pf->end = (char *)pf->page + malloc_cache; 1083 pf->size = malloc_cache; 1084 1085 brk(pf->end); 1086 malloc_brk = pf->end; 1087 1088 index = ptr2index(pf->end); 1089 1090 for(i=index;i <= last_index;) 1091 page_dir[i++] = MALLOC_NOT_MINE; 1092 1093 last_index = index - 1; 1094 1095 /* XXX: We could realloc/shrink the pagedir here I guess. */ 1096 } 1097 if (pt != NULL) 1098 ifree(pt); 1099 } 1100 1101 /* 1102 * Free a chunk, and possibly the page it's on, if the page becomes empty. 1103 */ 1104 1105 /* ARGSUSED */ 1106 static __inline__ void 1107 free_bytes(ptr, index, info) 1108 void *ptr; 1109 int index; 1110 struct pginfo *info; 1111 { 1112 int i; 1113 struct pginfo **mp; 1114 void *vp; 1115 1116 /* Find the chunk number on the page */ 1117 i = ((u_long)ptr & malloc_pagemask) >> info->shift; 1118 1119 if ((u_long)ptr & ((1UL<<(info->shift))-1)) { 1120 wrtwarning("modified (chunk-) pointer.\n"); 1121 return; 1122 } 1123 1124 if (info->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) { 1125 wrtwarning("chunk is already free.\n"); 1126 return; 1127 } 1128 1129 if (malloc_junk && info->size != 0) 1130 memset(ptr, SOME_JUNK, info->size); 1131 1132 info->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS); 1133 info->free++; 1134 1135 if (info->size != 0) 1136 mp = page_dir + info->shift; 1137 else 1138 mp = page_dir; 1139 1140 if (info->free == 1) { 1141 1142 /* Page became non-full */ 1143 1144 /* Insert in address order */ 1145 while (*mp && (*mp)->next && (*mp)->next->page < info->page) 1146 mp = &(*mp)->next; 1147 info->next = *mp; 1148 *mp = info; 1149 return; 1150 } 1151 1152 if (info->free != info->total) 1153 return; 1154 1155 /* Find & remove this page in the queue */ 1156 while (*mp != info) { 1157 mp = &((*mp)->next); 1158 #ifdef MALLOC_EXTRA_SANITY 1159 if (!*mp) 1160 wrterror("(ES): Not on queue\n"); 1161 #endif /* MALLOC_EXTRA_SANITY */ 1162 } 1163 *mp = info->next; 1164 1165 /* Free the page & the info structure if need be */ 1166 page_dir[ptr2index(info->page)] = MALLOC_FIRST; 1167 1168 /* If the page was mprotected, unprotect it before releasing it */ 1169 if (info->size == 0) { 1170 mprotect(info->page, malloc_pagesize, PROT_READ|PROT_WRITE); 1171 /* Do we have to care if mprotect succeeds here ? */ 1172 } 1173 1174 vp = info->page; /* Order is important ! */ 1175 if(vp != (void*)info) 1176 ifree(info); 1177 ifree(vp); 1178 } 1179 1180 static void 1181 ifree(ptr) 1182 void *ptr; 1183 { 1184 struct pginfo *info; 1185 int index; 1186 1187 /* This is legal */ 1188 if (ptr == NULL) 1189 return; 1190 1191 if (!malloc_started) { 1192 wrtwarning("malloc() has never been called.\n"); 1193 return; 1194 } 1195 1196 /* If we're already sinking, don't make matters any worse. */ 1197 if (suicide) 1198 return; 1199 1200 index = ptr2index(ptr); 1201 1202 if (index < malloc_pageshift) { 1203 wrtwarning("junk pointer, too low to make sense.\n"); 1204 return; 1205 } 1206 1207 if (index > last_index) { 1208 wrtwarning("junk pointer, too high to make sense.\n"); 1209 return; 1210 } 1211 1212 info = page_dir[index]; 1213 1214 if (info < MALLOC_MAGIC) 1215 free_pages(ptr, index, info); 1216 else 1217 free_bytes(ptr, index, info); 1218 return; 1219 } 1220 1221 /* 1222 * These are the public exported interface routines. 1223 */ 1224 1225 static int malloc_active; 1226 1227 void * 1228 malloc(size_t size) 1229 { 1230 register void *r; 1231 1232 malloc_func = " in malloc():"; 1233 _MALLOC_LOCK(); 1234 if (malloc_active++) { 1235 wrtwarning("recursive call.\n"); 1236 malloc_active--; 1237 _MALLOC_UNLOCK(); 1238 return (NULL); 1239 } 1240 r = imalloc(size); 1241 UTRACE(0, size, r); 1242 malloc_active--; 1243 _MALLOC_UNLOCK(); 1244 if (malloc_xmalloc && r == NULL) 1245 wrterror("out of memory.\n"); 1246 return (r); 1247 } 1248 1249 void 1250 free(void *ptr) 1251 { 1252 malloc_func = " in free():"; 1253 _MALLOC_LOCK(); 1254 if (malloc_active++) { 1255 wrtwarning("recursive call.\n"); 1256 malloc_active--; 1257 _MALLOC_UNLOCK(); 1258 return; 1259 } 1260 ifree(ptr); 1261 UTRACE(ptr, 0, 0); 1262 malloc_active--; 1263 _MALLOC_UNLOCK(); 1264 return; 1265 } 1266 1267 void * 1268 realloc(void *ptr, size_t size) 1269 { 1270 register void *r; 1271 1272 malloc_func = " in realloc():"; 1273 _MALLOC_LOCK(); 1274 if (malloc_active++) { 1275 wrtwarning("recursive call.\n"); 1276 malloc_active--; 1277 _MALLOC_UNLOCK(); 1278 return (NULL); 1279 } 1280 if (ptr == NULL) { 1281 r = imalloc(size); 1282 } else { 1283 r = irealloc(ptr, size); 1284 } 1285 UTRACE(ptr, size, r); 1286 malloc_active--; 1287 _MALLOC_UNLOCK(); 1288 if (malloc_xmalloc && r == NULL) 1289 wrterror("out of memory.\n"); 1290 return (r); 1291 } 1292