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