prmalloc.c (26496B)
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* This Source Code Form is subject to the terms of the Mozilla Public 3 * License, v. 2.0. If a copy of the MPL was not distributed with this 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 5 6 #include "primpl.h" 7 8 /* 9 ** We override malloc etc. on any platform which has preemption + 10 ** nspr20 user level threads. When we're debugging, we can make our 11 ** version of malloc fail occasionally. 12 */ 13 #ifdef _PR_OVERRIDE_MALLOC 14 15 /* 16 ** Thread safe version of malloc, calloc, realloc, free 17 */ 18 # include <stdarg.h> 19 20 # ifdef DEBUG 21 # define SANITY 22 # define EXTRA_SANITY 23 # else 24 # undef SANITY 25 # undef EXTRA_SANITY 26 # endif 27 28 /* Forward decls */ 29 void* _PR_UnlockedMalloc(size_t size); 30 void _PR_UnlockedFree(void* ptr); 31 void* _PR_UnlockedRealloc(void* ptr, size_t size); 32 void* _PR_UnlockedCalloc(size_t n, size_t elsize); 33 34 /************************************************************************/ 35 36 /* 37 * ---------------------------------------------------------------------------- 38 * "THE BEER-WARE LICENSE" (Revision 42): 39 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you 40 * can do whatever you want with this stuff. If we meet some day, and you think 41 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 42 * ---------------------------------------------------------------------------- 43 * 44 */ 45 46 /* 47 * Defining SANITY will enable some checks which will tell you if the users 48 * program did botch something 49 */ 50 51 /* 52 * Defining EXTRA_SANITY will enable some checks which are mostly related 53 * to internal conditions in malloc.c 54 */ 55 56 /* 57 * Very verbose progress on stdout... 58 */ 59 # if 0 60 # define TRACE(foo) printf foo 61 static int malloc_event; 62 # else 63 # define TRACE(foo) 64 # endif 65 66 /* XXX Pick a number, any number */ 67 # define malloc_pagesize 4096UL 68 # define malloc_pageshift 12UL 69 70 # ifdef XP_UNIX 71 # include <stdio.h> 72 # include <stdlib.h> 73 # include <unistd.h> 74 # include <string.h> 75 # include <errno.h> 76 # include <sys/types.h> 77 # include <sys/mman.h> 78 # endif 79 80 /* 81 * This structure describes a page's worth of chunks. 82 */ 83 84 struct pginfo { 85 struct pginfo* next; /* next on the free list */ 86 char* page; /* Pointer to the page */ 87 u_short size; /* size of this page's chunks */ 88 u_short shift; /* How far to shift for this size chunks */ 89 u_short free; /* How many free chunks */ 90 u_short total; /* How many chunk */ 91 u_long bits[1]; /* Which chunks are free */ 92 }; 93 94 struct pgfree { 95 struct pgfree* next; /* next run of free pages */ 96 struct pgfree* prev; /* prev run of free pages */ 97 char* page; /* pointer to free pages */ 98 char* end; /* pointer to end of free pages */ 99 u_long size; /* number of bytes free */ 100 }; 101 102 /* 103 * How many bits per u_long in the bitmap. 104 * Change only if not 8 bits/byte 105 */ 106 # define MALLOC_BITS (8 * sizeof(u_long)) 107 108 /* 109 * Magic values to put in the page_directory 110 */ 111 # define MALLOC_NOT_MINE ((struct pginfo*)0) 112 # define MALLOC_FREE ((struct pginfo*)1) 113 # define MALLOC_FIRST ((struct pginfo*)2) 114 # define MALLOC_FOLLOW ((struct pginfo*)3) 115 # define MALLOC_MAGIC ((struct pginfo*)4) 116 117 /* 118 * Set to one when malloc_init has been called 119 */ 120 static unsigned initialized; 121 122 /* 123 * The size of a page. 124 * Must be a integral multiplum of the granularity of mmap(2). 125 * Your toes will curl if it isn't a power of two 126 */ 127 # define malloc_pagemask ((malloc_pagesize) - 1) 128 129 /* 130 * The size of the largest chunk. 131 * Half a page. 132 */ 133 # define malloc_maxsize ((malloc_pagesize) >> 1) 134 135 /* 136 * malloc_pagesize == 1 << malloc_pageshift 137 */ 138 # ifndef malloc_pageshift 139 static unsigned malloc_pageshift; 140 # endif /* malloc_pageshift */ 141 142 /* 143 * The smallest allocation we bother about. 144 * Must be power of two 145 */ 146 # ifndef malloc_minsize 147 static unsigned malloc_minsize; 148 # endif /* malloc_minsize */ 149 150 /* 151 * The largest chunk we care about. 152 * Must be smaller than pagesize 153 * Must be power of two 154 */ 155 # ifndef malloc_maxsize 156 static unsigned malloc_maxsize; 157 # endif /* malloc_maxsize */ 158 159 # ifndef malloc_cache 160 static unsigned malloc_cache; 161 # endif /* malloc_cache */ 162 163 /* 164 * The offset from pagenumber to index into the page directory 165 */ 166 static u_long malloc_origo; 167 168 /* 169 * The last index in the page directory we care about 170 */ 171 static u_long last_index; 172 173 /* 174 * Pointer to page directory. 175 * Allocated "as if with" malloc 176 */ 177 static struct pginfo** page_dir; 178 179 /* 180 * How many slots in the page directory 181 */ 182 static unsigned malloc_ninfo; 183 184 /* 185 * Free pages line up here 186 */ 187 static struct pgfree free_list; 188 189 /* 190 * Abort() if we fail to get VM ? 191 */ 192 static int malloc_abort; 193 194 # ifdef SANITY 195 /* 196 * Are we trying to die ? 197 */ 198 static int suicide; 199 # endif 200 201 /* 202 * dump statistics 203 */ 204 static int malloc_stats; 205 206 /* 207 * always realloc ? 208 */ 209 static int malloc_realloc; 210 211 /* 212 * my last break. 213 */ 214 static void* malloc_brk; 215 216 /* 217 * one location cache for free-list holders 218 */ 219 static struct pgfree* px; 220 221 static int set_pgdir(void* ptr, struct pginfo* info); 222 static int extend_page_directory(u_long index); 223 224 # ifdef SANITY 225 void malloc_dump(FILE* fd) { 226 struct pginfo** pd; 227 struct pgfree* pf; 228 int j; 229 230 pd = page_dir; 231 232 /* print out all the pages */ 233 for (j = 0; j <= last_index; j++) { 234 fprintf(fd, "%08lx %5d ", (j + malloc_origo) << malloc_pageshift, j); 235 if (pd[j] == MALLOC_NOT_MINE) { 236 for (j++; j <= last_index && pd[j] == MALLOC_NOT_MINE; j++); 237 j--; 238 fprintf(fd, ".. %5d not mine\n", j); 239 } else if (pd[j] == MALLOC_FREE) { 240 for (j++; j <= last_index && pd[j] == MALLOC_FREE; j++); 241 j--; 242 fprintf(fd, ".. %5d free\n", j); 243 } else if (pd[j] == MALLOC_FIRST) { 244 for (j++; j <= last_index && pd[j] == MALLOC_FOLLOW; j++); 245 j--; 246 fprintf(fd, ".. %5d in use\n", j); 247 } else if (pd[j] < MALLOC_MAGIC) { 248 fprintf(fd, "(%p)\n", pd[j]); 249 } else { 250 fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n", pd[j], pd[j]->free, 251 pd[j]->total, pd[j]->size, pd[j]->page, pd[j]->next); 252 } 253 } 254 255 for (pf = free_list.next; pf; pf = pf->next) { 256 fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n", pf, pf->page, pf->end, 257 pf->size, pf->prev, pf->next); 258 if (pf == pf->next) { 259 fprintf(fd, "Free_list loops.\n"); 260 break; 261 } 262 } 263 264 /* print out various info */ 265 fprintf(fd, "Minsize\t%d\n", malloc_minsize); 266 fprintf(fd, "Maxsize\t%ld\n", malloc_maxsize); 267 fprintf(fd, "Pagesize\t%ld\n", malloc_pagesize); 268 fprintf(fd, "Pageshift\t%ld\n", malloc_pageshift); 269 fprintf(fd, "FirstPage\t%ld\n", malloc_origo); 270 fprintf(fd, "LastPage\t%ld %lx\n", last_index + malloc_pageshift, 271 (last_index + malloc_pageshift) << malloc_pageshift); 272 fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift); 273 } 274 275 static void wrterror(char* fmt, ...) { 276 char* q = "malloc() error: "; 277 char buf[100]; 278 va_list ap; 279 280 suicide = 1; 281 282 va_start(ap, fmt); 283 PR_vsnprintf(buf, sizeof(buf), fmt, ap); 284 va_end(ap); 285 fputs(q, stderr); 286 fputs(buf, stderr); 287 288 malloc_dump(stderr); 289 PR_Abort(); 290 } 291 292 static void wrtwarning(char* fmt, ...) { 293 char* q = "malloc() warning: "; 294 char buf[100]; 295 va_list ap; 296 297 va_start(ap, fmt); 298 PR_vsnprintf(buf, sizeof(buf), fmt, ap); 299 va_end(ap); 300 fputs(q, stderr); 301 fputs(buf, stderr); 302 } 303 # endif /* SANITY */ 304 305 /* 306 * Allocate a number of pages from the OS 307 */ 308 static caddr_t map_pages(int pages, int update) { 309 caddr_t result, tail; 310 311 result = ((caddr_t)sbrk(0)) + malloc_pagemask - 1; 312 result = (caddr_t)((u_long)result & ~malloc_pagemask); 313 tail = result + (pages << malloc_pageshift); 314 if (!brk(tail)) { 315 last_index = ((u_long)tail >> malloc_pageshift) - malloc_origo - 1; 316 malloc_brk = tail; 317 TRACE(("%6d S %p .. %p\n", malloc_event++, result, tail)); 318 if (!update || last_index < malloc_ninfo || 319 extend_page_directory(last_index)) { 320 return result; 321 } 322 } 323 TRACE(("%6d s %d %p %d\n", malloc_event++, pages, sbrk(0), errno)); 324 # ifdef EXTRA_SANITY 325 wrterror("map_pages fails\n"); 326 # endif 327 return 0; 328 } 329 330 # define set_bit(_pi, _bit) \ 331 (_pi)->bits[(_bit) / MALLOC_BITS] |= 1L << ((_bit) % MALLOC_BITS) 332 333 # define clr_bit(_pi, _bit) \ 334 (_pi)->bits[(_bit) / MALLOC_BITS] &= ~(1L << ((_bit) % MALLOC_BITS)); 335 336 # define tst_bit(_pi, _bit) \ 337 ((_pi)->bits[(_bit) / MALLOC_BITS] & (1L << ((_bit) % MALLOC_BITS))) 338 339 /* 340 * Extend page directory 341 */ 342 static int extend_page_directory(u_long index) { 343 struct pginfo **young, **old; 344 int i; 345 346 TRACE(("%6d E %lu\n", malloc_event++, index)); 347 348 /* Make it this many pages */ 349 i = index * sizeof *page_dir; 350 i /= malloc_pagesize; 351 i += 2; 352 353 /* Get new pages, if you used this much mem you don't care :-) */ 354 young = (struct pginfo**)map_pages(i, 0); 355 if (!young) { 356 return 0; 357 } 358 359 /* Copy the old stuff */ 360 memset(young, 0, i * malloc_pagesize); 361 memcpy(young, page_dir, malloc_ninfo * sizeof *page_dir); 362 363 /* register the new size */ 364 malloc_ninfo = i * malloc_pagesize / sizeof *page_dir; 365 366 /* swap the pointers */ 367 old = page_dir; 368 page_dir = young; 369 370 /* Mark the pages */ 371 index = ((u_long)young >> malloc_pageshift) - malloc_origo; 372 page_dir[index] = MALLOC_FIRST; 373 while (--i) { 374 page_dir[++index] = MALLOC_FOLLOW; 375 } 376 377 /* Now free the old stuff */ 378 _PR_UnlockedFree(old); 379 return 1; 380 } 381 382 /* 383 * Set entry in page directory. 384 * Extend page directory if need be. 385 */ 386 static int set_pgdir(void* ptr, struct pginfo* info) { 387 u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo; 388 389 if (index >= malloc_ninfo && !extend_page_directory(index)) { 390 return 0; 391 } 392 page_dir[index] = info; 393 return 1; 394 } 395 396 /* 397 * Initialize the world 398 */ 399 static void malloc_init(void) { 400 int i; 401 char* p; 402 403 TRACE(("%6d I\n", malloc_event++)); 404 # ifdef DEBUG 405 for (p = getenv("MALLOC_OPTIONS"); p && *p; p++) { 406 switch (*p) { 407 case 'a': 408 malloc_abort = 0; 409 break; 410 case 'A': 411 malloc_abort = 1; 412 break; 413 case 'd': 414 malloc_stats = 0; 415 break; 416 case 'D': 417 malloc_stats = 1; 418 break; 419 case 'r': 420 malloc_realloc = 0; 421 break; 422 case 'R': 423 malloc_realloc = 1; 424 break; 425 default: 426 wrtwarning("Unknown chars in MALLOC_OPTIONS\n"); 427 break; 428 } 429 } 430 # endif 431 432 # ifndef malloc_pagesize 433 /* determine our pagesize */ 434 malloc_pagesize = getpagesize(); 435 # endif /* malloc_pagesize */ 436 437 # ifndef malloc_pageshift 438 /* determine how much we shift by to get there */ 439 for (i = malloc_pagesize; i > 1; i >>= 1) { 440 malloc_pageshift++; 441 } 442 # endif /* malloc_pageshift */ 443 444 # ifndef malloc_cache 445 malloc_cache = 50 << malloc_pageshift; 446 # endif /* malloc_cache */ 447 448 # ifndef malloc_minsize 449 /* 450 * find the smallest size allocation we will bother about. 451 * this is determined as the smallest allocation that can hold 452 * it's own pginfo; 453 */ 454 i = 2; 455 for (;;) { 456 int j; 457 458 /* Figure out the size of the bits */ 459 j = malloc_pagesize / i; 460 j /= 8; 461 if (j < sizeof(u_long)) { 462 j = sizeof(u_long); 463 } 464 if (sizeof(struct pginfo) + j - sizeof(u_long) <= i) { 465 break; 466 } 467 i += i; 468 } 469 malloc_minsize = i; 470 # endif /* malloc_minsize */ 471 472 /* Allocate one page for the page directory */ 473 page_dir = (struct pginfo**)map_pages(1, 0); 474 # ifdef SANITY 475 if (!page_dir) { 476 wrterror("fatal: my first mmap failed. (check limits ?)\n"); 477 } 478 # endif 479 480 /* 481 * We need a maximum of malloc_pageshift buckets, steal these from the 482 * front of the page_directory; 483 */ 484 malloc_origo = (u_long)page_dir >> malloc_pageshift; 485 malloc_origo -= malloc_pageshift; 486 487 /* Clear it */ 488 memset(page_dir, 0, malloc_pagesize); 489 490 /* Find out how much it tells us */ 491 malloc_ninfo = malloc_pagesize / sizeof *page_dir; 492 493 /* Plug the page directory into itself */ 494 i = set_pgdir(page_dir, MALLOC_FIRST); 495 # ifdef SANITY 496 if (!i) { 497 wrterror("fatal: couldn't set myself in the page directory\n"); 498 } 499 # endif 500 501 /* Been here, done that */ 502 initialized++; 503 } 504 505 /* 506 * Allocate a number of complete pages 507 */ 508 static void* malloc_pages(size_t size) { 509 void *p, *delay_free = 0; 510 int i; 511 struct pgfree* pf; 512 u_long index; 513 514 /* How many pages ? */ 515 size += (malloc_pagesize - 1); 516 size &= ~malloc_pagemask; 517 518 p = 0; 519 /* Look for free pages before asking for more */ 520 for (pf = free_list.next; pf; pf = pf->next) { 521 # ifdef EXTRA_SANITY 522 if (pf->page == pf->end) { 523 wrterror("zero entry on free_list\n"); 524 } 525 if (pf->page > pf->end) { 526 TRACE(("%6d !s %p %p %p <%d>\n", malloc_event++, pf, pf->page, pf->end, 527 __LINE__)); 528 wrterror("sick entry on free_list\n"); 529 } 530 if ((void*)pf->page >= (void*)sbrk(0)) { 531 wrterror("entry on free_list past brk\n"); 532 } 533 if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo] != 534 MALLOC_FREE) { 535 TRACE(("%6d !f %p %p %p <%d>\n", malloc_event++, pf, pf->page, pf->end, 536 __LINE__)); 537 wrterror("non-free first page on free-list\n"); 538 } 539 if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo] != 540 MALLOC_FREE) { 541 wrterror("non-free last page on free-list\n"); 542 } 543 # endif /* EXTRA_SANITY */ 544 if (pf->size < size) { 545 continue; 546 } else if (pf->size == size) { 547 p = pf->page; 548 if (pf->next) { 549 pf->next->prev = pf->prev; 550 } 551 pf->prev->next = pf->next; 552 delay_free = pf; 553 break; 554 } else { 555 p = pf->page; 556 pf->page += size; 557 pf->size -= size; 558 break; 559 } 560 } 561 # ifdef EXTRA_SANITY 562 if (p && 563 page_dir[((u_long)p >> malloc_pageshift) - malloc_origo] != MALLOC_FREE) { 564 wrterror("allocated non-free page on free-list\n"); 565 } 566 # endif /* EXTRA_SANITY */ 567 568 size >>= malloc_pageshift; 569 570 /* Map new pages */ 571 if (!p) { 572 p = map_pages(size, 1); 573 } 574 575 if (p) { 576 /* Mark the pages in the directory */ 577 index = ((u_long)p >> malloc_pageshift) - malloc_origo; 578 page_dir[index] = MALLOC_FIRST; 579 for (i = 1; i < size; i++) { 580 page_dir[index + i] = MALLOC_FOLLOW; 581 } 582 } 583 if (delay_free) { 584 if (!px) { 585 px = (struct pgfree*)delay_free; 586 } else { 587 _PR_UnlockedFree(delay_free); 588 } 589 } 590 return p; 591 } 592 593 /* 594 * Allocate a page of fragments 595 */ 596 597 static int malloc_make_chunks(int bits) { 598 struct pginfo* bp; 599 void* pp; 600 int i, k, l; 601 602 /* Allocate a new bucket */ 603 pp = malloc_pages(malloc_pagesize); 604 if (!pp) { 605 return 0; 606 } 607 l = sizeof *bp - sizeof(u_long); 608 l += sizeof(u_long) * 609 (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS); 610 if ((1 << (bits)) <= l + l) { 611 bp = (struct pginfo*)pp; 612 } else { 613 bp = (struct pginfo*)_PR_UnlockedMalloc(l); 614 } 615 if (!bp) { 616 return 0; 617 } 618 bp->size = (1 << bits); 619 bp->shift = bits; 620 bp->total = bp->free = malloc_pagesize >> bits; 621 bp->next = page_dir[bits]; 622 bp->page = (char*)pp; 623 i = set_pgdir(pp, bp); 624 if (!i) { 625 return 0; 626 } 627 628 /* We can safely assume that there is nobody in this chain */ 629 page_dir[bits] = bp; 630 631 /* set all valid bits in the bits */ 632 k = bp->total; 633 i = 0; 634 /* 635 for(;k-i >= MALLOC_BITS; i += MALLOC_BITS) 636 bp->bits[i / MALLOC_BITS] = ~0; 637 */ 638 for (; i < k; i++) { 639 set_bit(bp, i); 640 } 641 642 if (bp != pp) { 643 return 1; 644 } 645 646 /* We may have used the first ones already */ 647 for (i = 0; l > 0; i++) { 648 clr_bit(bp, i); 649 bp->free--; 650 bp->total--; 651 l -= (1 << bits); 652 } 653 return 1; 654 } 655 656 /* 657 * Allocate a fragment 658 */ 659 static void* malloc_bytes(size_t size) { 660 size_t s; 661 int j; 662 struct pginfo* bp; 663 int k; 664 u_long *lp, bf; 665 666 /* Don't bother with anything less than this */ 667 if (size < malloc_minsize) { 668 size = malloc_minsize; 669 } 670 671 /* Find the right bucket */ 672 j = 1; 673 s = size - 1; 674 while (s >>= 1) { 675 j++; 676 } 677 678 /* If it's empty, make a page more of that size chunks */ 679 if (!page_dir[j] && !malloc_make_chunks(j)) { 680 return 0; 681 } 682 683 /* Find first word of bitmap which isn't empty */ 684 bp = page_dir[j]; 685 for (lp = bp->bits; !*lp; lp++); 686 687 /* Find that bit */ 688 bf = *lp; 689 k = 0; 690 while ((bf & 1) == 0) { 691 bf >>= 1; 692 k++; 693 } 694 695 *lp ^= 1L << k; /* clear it */ 696 bp->free--; 697 if (!bp->free) { 698 page_dir[j] = bp->next; 699 bp->next = 0; 700 } 701 k += (lp - bp->bits) * MALLOC_BITS; 702 return bp->page + (k << bp->shift); 703 } 704 705 void* _PR_UnlockedMalloc(size_t size) { 706 void* result; 707 708 /* Round up to a multiple of 8 bytes */ 709 if (size & 7) { 710 size = size + 8 - (size & 7); 711 } 712 713 if (!initialized) { 714 malloc_init(); 715 } 716 717 # ifdef SANITY 718 if (suicide) { 719 PR_Abort(); 720 } 721 # endif 722 723 if (size <= malloc_maxsize) { 724 result = malloc_bytes(size); 725 } else { 726 result = malloc_pages(size); 727 } 728 # ifdef SANITY 729 if (malloc_abort && !result) { 730 wrterror("malloc() returns NULL\n"); 731 } 732 # endif 733 TRACE(("%6d M %p %d\n", malloc_event++, result, size)); 734 735 return result; 736 } 737 738 void* _PR_UnlockedMemalign(size_t alignment, size_t size) { 739 void* result; 740 741 /* 742 * alignment has to be a power of 2 743 */ 744 745 if ((size <= alignment) && (alignment <= malloc_maxsize)) { 746 size = alignment; 747 } else { 748 size += alignment - 1; 749 } 750 751 /* Round up to a multiple of 8 bytes */ 752 if (size & 7) { 753 size = size + 8 - (size & 7); 754 } 755 756 if (!initialized) { 757 malloc_init(); 758 } 759 760 # ifdef SANITY 761 if (suicide) { 762 abort(); 763 } 764 # endif 765 766 if (size <= malloc_maxsize) { 767 result = malloc_bytes(size); 768 } else { 769 result = malloc_pages(size); 770 } 771 # ifdef SANITY 772 if (malloc_abort && !result) { 773 wrterror("malloc() returns NULL\n"); 774 } 775 # endif 776 TRACE(("%6d A %p %d\n", malloc_event++, result, size)); 777 778 if ((u_long)result & (alignment - 1)) { 779 return ((void*)(((u_long)result + alignment) & ~(alignment - 1))); 780 } else { 781 return result; 782 } 783 } 784 785 void* _PR_UnlockedCalloc(size_t n, size_t nelem) { 786 void* p; 787 788 /* Compute total size and then round up to a double word amount */ 789 n *= nelem; 790 if (n & 7) { 791 n = n + 8 - (n & 7); 792 } 793 794 /* Get the memory */ 795 p = _PR_UnlockedMalloc(n); 796 if (p) { 797 /* Zero it */ 798 memset(p, 0, n); 799 } 800 return p; 801 } 802 803 /* 804 * Change an allocation's size 805 */ 806 void* _PR_UnlockedRealloc(void* ptr, size_t size) { 807 void* p; 808 u_long osize, page, index, tmp_index; 809 struct pginfo** mp; 810 811 if (!initialized) { 812 malloc_init(); 813 } 814 815 # ifdef SANITY 816 if (suicide) { 817 PR_Abort(); 818 } 819 # endif 820 821 /* used as free() */ 822 TRACE(("%6d R %p %d\n", malloc_event++, ptr, size)); 823 if (ptr && !size) { 824 _PR_UnlockedFree(ptr); 825 return _PR_UnlockedMalloc(1); 826 } 827 828 /* used as malloc() */ 829 if (!ptr) { 830 p = _PR_UnlockedMalloc(size); 831 return p; 832 } 833 834 /* Find the page directory entry for the page in question */ 835 page = (u_long)ptr >> malloc_pageshift; 836 index = page - malloc_origo; 837 838 /* 839 * check if memory was allocated by memalign 840 */ 841 tmp_index = index; 842 while (page_dir[tmp_index] == MALLOC_FOLLOW) { 843 tmp_index--; 844 } 845 if (tmp_index != index) { 846 /* 847 * memalign-allocated memory 848 */ 849 index = tmp_index; 850 page = index + malloc_origo; 851 ptr = (void*)(page << malloc_pageshift); 852 } 853 TRACE(("%6d R2 %p %d\n", malloc_event++, ptr, size)); 854 855 /* make sure it makes sense in some fashion */ 856 if (index < malloc_pageshift || index > last_index) { 857 # ifdef SANITY 858 wrtwarning("junk pointer passed to realloc()\n"); 859 # endif 860 return 0; 861 } 862 863 /* find the size of that allocation, and see if we need to relocate */ 864 mp = &page_dir[index]; 865 if (*mp == MALLOC_FIRST) { 866 osize = malloc_pagesize; 867 while (mp[1] == MALLOC_FOLLOW) { 868 osize += malloc_pagesize; 869 mp++; 870 } 871 if (!malloc_realloc && size < osize && size > malloc_maxsize && 872 size > (osize - malloc_pagesize)) { 873 return ptr; 874 } 875 } else if (*mp >= MALLOC_MAGIC) { 876 osize = (*mp)->size; 877 if (!malloc_realloc && size < osize && 878 (size > (*mp)->size / 2 || (*mp)->size == malloc_minsize)) { 879 return ptr; 880 } 881 } else { 882 # ifdef SANITY 883 wrterror("realloc() of wrong page.\n"); 884 # endif 885 } 886 887 /* try to reallocate */ 888 p = _PR_UnlockedMalloc(size); 889 890 if (p) { 891 /* copy the lesser of the two sizes */ 892 if (osize < size) { 893 memcpy(p, ptr, osize); 894 } else { 895 memcpy(p, ptr, size); 896 } 897 _PR_UnlockedFree(ptr); 898 } 899 # ifdef DEBUG 900 else if (malloc_abort) { 901 wrterror("realloc() returns NULL\n"); 902 } 903 # endif 904 905 return p; 906 } 907 908 /* 909 * Free a sequence of pages 910 */ 911 912 static void free_pages(char* ptr, u_long page, int index, struct pginfo* info) { 913 int i; 914 struct pgfree *pf, *pt; 915 u_long l; 916 char* tail; 917 918 TRACE(("%6d FP %p %d\n", malloc_event++, ptr, page)); 919 /* Is it free already ? */ 920 if (info == MALLOC_FREE) { 921 # ifdef SANITY 922 wrtwarning("freeing free page at %p.\n", ptr); 923 # endif 924 return; 925 } 926 927 # ifdef SANITY 928 /* Is it not the right place to begin ? */ 929 if (info != MALLOC_FIRST) { 930 wrterror("freeing wrong page.\n"); 931 } 932 933 /* Is this really a pointer to a page ? */ 934 if ((u_long)ptr & malloc_pagemask) { 935 wrterror("freeing messed up page pointer.\n"); 936 } 937 # endif 938 939 /* Count how many pages it is anyway */ 940 page_dir[index] = MALLOC_FREE; 941 for (i = 1; page_dir[index + i] == MALLOC_FOLLOW; i++) { 942 page_dir[index + i] = MALLOC_FREE; 943 } 944 945 l = i << malloc_pageshift; 946 947 tail = ptr + l; 948 949 /* add to free-list */ 950 if (!px) { 951 px = (struct pgfree*)_PR_UnlockedMalloc(sizeof *pt); 952 } 953 /* XXX check success */ 954 px->page = ptr; 955 px->end = tail; 956 px->size = l; 957 if (!free_list.next) { 958 px->next = free_list.next; 959 px->prev = &free_list; 960 free_list.next = px; 961 pf = px; 962 px = 0; 963 } else { 964 tail = ptr + l; 965 for (pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next); 966 for (; pf; pf = pf->next) { 967 if (pf->end == ptr) { 968 /* append to entry */ 969 pf->end += l; 970 pf->size += l; 971 if (pf->next && pf->end == pf->next->page) { 972 pt = pf->next; 973 pf->end = pt->end; 974 pf->size += pt->size; 975 pf->next = pt->next; 976 if (pf->next) { 977 pf->next->prev = pf; 978 } 979 _PR_UnlockedFree(pt); 980 } 981 } else if (pf->page == tail) { 982 /* prepend to entry */ 983 pf->size += l; 984 pf->page = ptr; 985 } else if (pf->page > ptr) { 986 px->next = pf; 987 px->prev = pf->prev; 988 pf->prev = px; 989 px->prev->next = px; 990 pf = px; 991 px = 0; 992 } else if (!pf->next) { 993 px->next = 0; 994 px->prev = pf; 995 pf->next = px; 996 pf = px; 997 px = 0; 998 } else { 999 continue; 1000 } 1001 break; 1002 } 1003 } 1004 if (!pf->next && pf->size > malloc_cache && pf->end == malloc_brk && 1005 malloc_brk == (void*)sbrk(0)) { 1006 pf->end = pf->page + malloc_cache; 1007 pf->size = malloc_cache; 1008 TRACE(("%6d U %p %d\n", malloc_event++, pf->end, pf->end - pf->page)); 1009 brk(pf->end); 1010 malloc_brk = pf->end; 1011 /* Find the page directory entry for the page in question */ 1012 page = (u_long)pf->end >> malloc_pageshift; 1013 index = page - malloc_origo; 1014 /* Now update the directory */ 1015 for (i = index; i <= last_index;) { 1016 page_dir[i++] = MALLOC_NOT_MINE; 1017 } 1018 last_index = index - 1; 1019 } 1020 } 1021 1022 /* 1023 * Free a chunk, and possibly the page it's on, if the page becomes empty. 1024 */ 1025 1026 static void free_bytes(void* ptr, u_long page, int index, struct pginfo* info) { 1027 int i; 1028 struct pginfo** mp; 1029 void* vp; 1030 1031 /* Make sure that pointer is multiplum of chunk-size */ 1032 # ifdef SANITY 1033 if ((u_long)ptr & (info->size - 1)) { 1034 wrterror("freeing messed up chunk pointer\n"); 1035 } 1036 # endif 1037 1038 /* Find the chunk number on the page */ 1039 i = ((u_long)ptr & malloc_pagemask) >> info->shift; 1040 1041 /* See if it's free already */ 1042 if (tst_bit(info, i)) { 1043 # ifdef SANITY 1044 wrtwarning("freeing free chunk at %p\n", ptr); 1045 # endif 1046 return; 1047 } 1048 1049 /* Mark it free */ 1050 set_bit(info, i); 1051 info->free++; 1052 1053 /* If the page was full before, we need to put it on the queue now */ 1054 if (info->free == 1) { 1055 mp = page_dir + info->shift; 1056 while (*mp && (*mp)->next && (*mp)->next->page < info->page) { 1057 mp = &(*mp)->next; 1058 } 1059 info->next = *mp; 1060 *mp = info; 1061 return; 1062 } 1063 1064 /* If this page isn't empty, don't do anything. */ 1065 if (info->free != info->total) { 1066 return; 1067 } 1068 1069 /* We may want to keep at least one page of each size chunks around. */ 1070 mp = page_dir + info->shift; 1071 if (0 && (*mp == info) && !info->next) { 1072 return; 1073 } 1074 1075 /* Find & remove this page in the queue */ 1076 while (*mp != info) { 1077 mp = &((*mp)->next); 1078 # ifdef EXTRA_SANITY 1079 if (!*mp) { 1080 TRACE(("%6d !q %p\n", malloc_event++, info)); 1081 wrterror("Not on queue\n"); 1082 } 1083 # endif 1084 } 1085 *mp = info->next; 1086 1087 /* Free the page & the info structure if need be */ 1088 set_pgdir(info->page, MALLOC_FIRST); 1089 if ((void*)info->page == (void*)info) { 1090 _PR_UnlockedFree(info->page); 1091 } else { 1092 vp = info->page; 1093 _PR_UnlockedFree(info); 1094 _PR_UnlockedFree(vp); 1095 } 1096 } 1097 1098 void _PR_UnlockedFree(void* ptr) { 1099 u_long page; 1100 struct pginfo* info; 1101 int index, tmp_index; 1102 1103 TRACE(("%6d F %p\n", malloc_event++, ptr)); 1104 /* This is legal */ 1105 if (!ptr) { 1106 return; 1107 } 1108 1109 # ifdef SANITY 1110 /* There wouldn't be anything to free */ 1111 if (!initialized) { 1112 wrtwarning("free() called before malloc() ever got called\n"); 1113 return; 1114 } 1115 # endif 1116 1117 # ifdef SANITY 1118 if (suicide) { 1119 PR_Abort(); 1120 } 1121 # endif 1122 1123 /* Find the page directory entry for the page in question */ 1124 page = (u_long)ptr >> malloc_pageshift; 1125 index = page - malloc_origo; 1126 1127 /* 1128 * check if memory was allocated by memalign 1129 */ 1130 tmp_index = index; 1131 while (page_dir[tmp_index] == MALLOC_FOLLOW) { 1132 tmp_index--; 1133 } 1134 if (tmp_index != index) { 1135 /* 1136 * memalign-allocated memory 1137 */ 1138 index = tmp_index; 1139 page = index + malloc_origo; 1140 ptr = (void*)(page << malloc_pageshift); 1141 } 1142 /* make sure it makes sense in some fashion */ 1143 if (index < malloc_pageshift) { 1144 # ifdef SANITY 1145 wrtwarning("junk pointer %p (low) passed to free()\n", ptr); 1146 # endif 1147 return; 1148 } 1149 if (index > last_index) { 1150 # ifdef SANITY 1151 wrtwarning("junk pointer %p (high) passed to free()\n", ptr); 1152 # endif 1153 return; 1154 } 1155 1156 /* handle as page-allocation or chunk allocation */ 1157 info = page_dir[index]; 1158 if (info < MALLOC_MAGIC) { 1159 free_pages((char*)ptr, page, index, info); 1160 } else { 1161 free_bytes(ptr, page, index, info); 1162 } 1163 return; 1164 } 1165 #endif /* _PR_OVERRIDE_MALLOC */