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