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