lib/libc/stdlib/malloc.c

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