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.11 2006/02/12 21:19:07 dillon 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 'x': malloc_xmalloc  = 0; break;
 656                 case 'X': malloc_xmalloc  = 1; break;
 657                 case 'z': malloc_zero     = 0; break;
 658                 case 'Z': malloc_zero     = 1; break;
 659                 default:
 660                     j = malloc_abort;
 661                     malloc_abort = 0;
 662                     wrtwarning("unknown char in MALLOC_OPTIONS");
 663                     malloc_abort = j;
 664                     break;
 665             }
 666         }
 667     }
 668
 669     UTRACE(0, 0, 0);
 670
 671     /*
 672      * We want junk in the entire allocation, and zero only in the part
 673      * the user asked for.
 674      */
 675     if (malloc_zero)
 676         malloc_junk = 1;
 677
 678 #ifdef MALLOC_STATS
 679     if (malloc_stats && (atexit(malloc_exit) == -1))
 680         wrtwarning("atexit(2) failed."
 681                     "  Will not be able to dump malloc stats on exit");
 682 #endif /* MALLOC_STATS */
 683
 684     /* Allocate one page for the page directory. */
 685     page_dir = (struct pginfo **)MMAP(malloc_pagesize);
 686
 687     if (page_dir == MAP_FAILED) {
 688         wrterror("mmap(2) failed, check limits");
 689         errno = ENOMEM;
 690         return;
 691     }
 692     pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
 693     pdi_mod = pdi_off / sizeof(struct pginfo *);
 694
 695     last_dir = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
 696     last_dir->base = page_dir;
 697     last_dir->prev = last_dir->next = NULL;
 698     last_dir->dirnum = malloc_pageshift;
 699
 700     /* Been here, done that. */
 701     malloc_started++;
 702
 703     /* Recalculate the cache size in bytes, and make sure it's nonzero. */
 704     if (!malloc_cache)
 705         malloc_cache++;
 706     malloc_cache <<= malloc_pageshift;
 707     errno = save_errno;
 708 }
 709
 710 /*
 711  * Allocate a number of complete pages
 712  */
 713 static void *
 714 malloc_pages(size_t size)
 715 {
 716     void                *p, *delay_free = NULL, *tp;
 717     int                 i;
 718     struct pginfo       **pd;
 719     struct pdinfo       *pi;
 720     u_long              pidx, index;
 721     struct pgfree       *pf;
 722
 723     size = pageround(size) + malloc_guard;
 724
 725     p = NULL;
 726     /* Look for free pages before asking for more */
 727     for (pf = free_list.next; pf; pf = pf->next) {
 728
 729 #ifdef MALLOC_EXTRA_SANITY
 730     if (pf->size & malloc_pagemask) {
 731         wrterror("(ES): junk length entry on free_list");
 732         errno = EFAULT;
 733         return (NULL);
 734     }
 735     if (!pf->size) {
 736         wrterror("(ES): zero length entry on free_list");
 737         errno = EFAULT;
 738         return (NULL);
 739     }
 740     if (pf->page > (pf->page + pf->size)) {
 741         wrterror("(ES): sick entry on free_list");
 742         errno = EFAULT;
 743         return (NULL);
 744     }
 745     if ((pi = pf->pdir) == NULL) {
 746         wrterror("(ES): invalid page directory on free-list");
 747         errno = EFAULT;
 748         return (NULL);
 749     }
 750     if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
 751         wrterror("(ES): directory index mismatch on free-list");
 752         errno = EFAULT;
 753         return (NULL);
 754     }
 755     pd = pi->base;
 756     if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
 757         wrterror("(ES): non-free first page on free-list");
 758         errno = EFAULT;
 759         return (NULL);
 760     }
 761     pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1);
 762     for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
 763             pi = pi->next)
 764                 ;
 765     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 766         wrterror("(ES): last page not referenced in page directory");
 767         errno = EFAULT;
 768         return (NULL);
 769     }
 770     pd = pi->base;
 771     if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) {
 772         wrterror("(ES): non-free last page on free-list");
 773         errno = EFAULT;
 774         return (NULL);
 775     }
 776 #endif /* MALLOC_EXTRA_SANITY */
 777
 778     if (pf->size < size)
 779         continue;
 780
 781     if (pf->size == size) {
 782         p = pf->page;
 783         pi = pf->pdir;
 784         if (pf->next != NULL)
 785             pf->next->prev = pf->prev;
 786             pf->prev->next = pf->next;
 787             delay_free = pf;
 788             break;
 789         }
 790         p = pf->page;
 791         pf->page = (char *) pf->page + size;
 792         pf->size -= size;
 793         pidx = PI_IDX(ptr2index(pf->page));
 794         for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
 795             pi = pi->next)
 796                 ;
 797         if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 798             wrterror("(ES): hole in directories");
 799             errno = EFAULT;
 800             return (NULL);
 801         }
 802         tp = pf->pdir;
 803         pf->pdir = pi;
 804         pi = tp;
 805         break;
 806     }
 807
 808     size -= malloc_guard;
 809
 810 #ifdef MALLOC_EXTRA_SANITY
 811     if (p != NULL && pi != NULL) {
 812         pidx = PD_IDX(pi->dirnum);
 813         pd = pi->base;
 814     }
 815     if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
 816         wrterror("(ES): allocated non-free page on free-list");
 817         errno = EFAULT;
 818         return (NULL);
 819     }
 820 #endif /* MALLOC_EXTRA_SANITY */
 821
 822     if (p != NULL && (malloc_guard || malloc_freeprot))
 823         mprotect(p, size, PROT_READ | PROT_WRITE);
 824
 825     size >>= malloc_pageshift;
 826
 827     /* Map new pages */
 828     if (p == NULL)
 829         p = map_pages(size);
 830
 831     if (p != NULL) {
 832         index = ptr2index(p);
 833         pidx = PI_IDX(index);
 834         pdir_lookup(index, &pi);
 835 #ifdef MALLOC_EXTRA_SANITY
 836         if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 837             wrterror("(ES): mapped pages not found in directory");
 838             errno = EFAULT;
 839             return (NULL);
 840         }
 841 #endif /* MALLOC_EXTRA_SANITY */
 842         if (pi != last_dir) {
 843             prev_dir = last_dir;
 844             last_dir = pi;
 845         }
 846         pd = pi->base;
 847         pd[PI_OFF(index)] = MALLOC_FIRST;
 848         for (i = 1; i < size; i++) {
 849             if (!PI_OFF(index + i)) {
 850                 pidx++;
 851                 pi = pi->next;
 852 #ifdef MALLOC_EXTRA_SANITY
 853                 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 854                     wrterror("(ES): hole in mapped pages directory");
 855                     errno = EFAULT;
 856                     return (NULL);
 857                 }
 858 #endif /* MALLOC_EXTRA_SANITY */
 859                 pd = pi->base;
 860             }
 861             pd[PI_OFF(index + i)] = MALLOC_FOLLOW;
 862         }
 863         if (malloc_guard) {
 864             if (!PI_OFF(index + i)) {
 865                 pidx++;
 866                 pi = pi->next;
 867 #ifdef MALLOC_EXTRA_SANITY
 868                 if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 869                     wrterror("(ES): hole in mapped pages directory");
 870                     errno = EFAULT;
 871                     return (NULL);
 872                 }
 873 #endif /* MALLOC_EXTRA_SANITY */
 874                 pd = pi->base;
 875             }
 876             pd[PI_OFF(index + i)] = MALLOC_FIRST;
 877         }
 878         malloc_used += size << malloc_pageshift;
 879         malloc_guarded += malloc_guard;
 880
 881         if (malloc_junk)
 882             memset(p, SOME_JUNK, size << malloc_pageshift);
 883     }
 884     if (delay_free) {
 885         if (px == NULL)
 886             px = delay_free;
 887         else
 888             ifree(delay_free);
 889     }
 890     return (p);
 891 }
 892
 893 /*
 894  * Allocate a page of fragments
 895  */
 896
 897 static __inline__ int
 898 malloc_make_chunks(int bits)
 899 {
 900     struct pginfo       *bp, **pd;
 901     struct pdinfo       *pi;
 902     u_long              pidx;
 903     void                *pp;
 904     int                 i, k, l;
 905
 906     /* Allocate a new bucket */
 907     pp = malloc_pages((size_t) malloc_pagesize);
 908     if (pp == NULL)
 909         return (0);
 910
 911     /* Find length of admin structure */
 912     l = sizeof *bp - sizeof(u_long);
 913     l += sizeof(u_long) *
 914             (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);
 915
 916     /* Don't waste more than two chunks on this */
 917
 918     /*
 919      * If we are to allocate a memory protected page for the malloc(0)
 920      * case (when bits=0), it must be from a different page than the
 921      * pginfo page.
 922      * --> Treat it like the big chunk alloc, get a second data page.
 923      */
 924     if (bits != 0 && (1UL << (bits)) <= l + l) {
 925         bp = (struct pginfo *) pp;
 926     } else {
 927         bp = (struct pginfo *) imalloc(l);
 928         if (bp == NULL) {
 929             ifree(pp);
 930             return (0);
 931         }
 932     }
 933     /* memory protect the page allocated in the malloc(0) case */
 934     if (bits == 0) {
 935         bp->size = 0;
 936         bp->shift = 1;
 937         i = malloc_minsize - 1;
 938         while (i >>= 1)
 939             bp->shift++;
 940         bp->total = bp->free = malloc_pagesize >> bp->shift;
 941         bp->page = pp;
 942
 943         k = mprotect(pp, malloc_pagesize, PROT_NONE);
 944         if (k < 0) {
 945             ifree(pp);
 946             ifree(bp);
 947             return (0);
 948         }
 949     } else {
 950         bp->size = (1UL << bits);
 951         bp->shift = bits;
 952         bp->total = bp->free = malloc_pagesize >> bits;
 953         bp->page = pp;
 954     }
 955     /* set all valid bits in the bitmap */
 956     k = bp->total;
 957     i = 0;
 958
 959     /* Do a bunch at a time */
 960     for (; k - i >= MALLOC_BITS; i += MALLOC_BITS)
 961         bp->bits[i / MALLOC_BITS] = ~0UL;
 962
 963     for (; i < k; i++)
 964         bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
 965
 966     if (bp == bp->page) {
 967         /* Mark the ones we stole for ourselves */
 968         for (i = 0; l > 0; i++) {
 969             bp->bits[i / MALLOC_BITS] &= ~(1UL << (i % MALLOC_BITS));
 970             bp->free--;
 971             bp->total--;
 972             l -= (1 << bits);
 973         }
 974     }
 975     /* MALLOC_LOCK */
 976
 977     pidx = PI_IDX(ptr2index(pp));
 978     pdir_lookup(ptr2index(pp), &pi);
 979 #ifdef MALLOC_EXTRA_SANITY
 980     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
 981         wrterror("(ES): mapped pages not found in directory");
 982         errno = EFAULT;
 983         return (0);
 984     }
 985 #endif /* MALLOC_EXTRA_SANITY */
 986     if (pi != last_dir) {
 987         prev_dir = last_dir;
 988         last_dir = pi;
 989     }
 990     pd = pi->base;
 991     pd[PI_OFF(ptr2index(pp))] = bp;
 992
 993     bp->next = page_dir[bits];
 994     page_dir[bits] = bp;
 995
 996     /* MALLOC_UNLOCK */
 997     return (1);
 998 }
 999
1000 /*
1001  * Allocate a fragment
1002  */
1003 static void *
1004 malloc_bytes(size_t size)
1005 {
1006     int             i, j, k;
1007     u_long          u, *lp;
1008     struct pginfo   *bp;
1009
1010     /* Don't bother with anything less than this */
1011     /* unless we have a malloc(0) requests */
1012     if (size != 0 && size < malloc_minsize)
1013         size = malloc_minsize;
1014
1015     /* Find the right bucket */
1016     if (size == 0)
1017         j = 0;
1018     else {
1019         j = 1;
1020         i = size - 1;
1021         while (i >>= 1)
1022             j++;
1023     }
1024
1025     /* If it's empty, make a page more of that size chunks */
1026     if (page_dir[j] == NULL && !malloc_make_chunks(j))
1027         return (NULL);
1028
1029     bp = page_dir[j];
1030
1031     /* Find first word of bitmap which isn't empty */
1032     for (lp = bp->bits; !*lp; lp++);
1033
1034     /* Find that bit, and tweak it */
1035     u = 1;
1036     k = 0;
1037     while (!(*lp & u)) {
1038         u += u;
1039         k++;
1040     }
1041
1042     if (malloc_guard) {
1043         /* Walk to a random position. */
1044         i = arc4random() % bp->free;
1045         while (i > 0) {
1046             u += u;
1047             k++;
1048             if (k >= MALLOC_BITS) {
1049                 lp++;
1050                 u = 1;
1051                 k = 0;
1052             }
1053 #ifdef MALLOC_EXTRA_SANITY
1054             if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
1055                 wrterror("chunk overflow");
1056                 errno = EFAULT;
1057                 return (NULL);
1058             }
1059 #endif /* MALLOC_EXTRA_SANITY */
1060             if (*lp & u)
1061                 i--;
1062         }
1063     }
1064     *lp ^= u;
1065
1066     /* If there are no more free, remove from free-list */
1067     if (!--bp->free) {
1068         page_dir[j] = bp->next;
1069         bp->next = NULL;
1070     }
1071     /* Adjust to the real offset of that chunk */
1072     k += (lp - bp->bits) * MALLOC_BITS;
1073     k <<= bp->shift;
1074
1075     if (malloc_junk && bp->size != 0)
1076         memset((char *) bp->page + k, SOME_JUNK, bp->size);
1077
1078     return ((u_char *) bp->page + k);
1079 }
1080
1081 /*
1082  * Magic so that malloc(sizeof(ptr)) is near the end of the page.
1083  */
1084 #define PTR_GAP         (malloc_pagesize - sizeof(void *))
1085 #define PTR_SIZE        (sizeof(void *))
1086 #define PTR_ALIGNED(p)  (((unsigned long)p & malloc_pagemask) == PTR_GAP)
1087
1088 /*
1089  * Allocate a piece of memory
1090  */
1091 static void *
1092 imalloc(size_t size)
1093 {
1094     void        *result;
1095     int         ptralloc = 0;
1096
1097     if (!malloc_started)
1098         malloc_init();
1099
1100     if (suicide)
1101         abort();
1102
1103     if (malloc_ptrguard && size == PTR_SIZE) {
1104         ptralloc = 1;
1105         size = malloc_pagesize;
1106     }
1107     if ((size + malloc_pagesize) < size) {      /* Check for overflow */
1108         result = NULL;
1109         errno = ENOMEM;
1110     } else if (size <= malloc_maxsize)
1111         result = malloc_bytes(size);
1112     else
1113         result = malloc_pages(size);
1114
1115     if (malloc_abort == 1 && result == NULL)
1116         wrterror("allocation failed");
1117
1118     if (malloc_zero && result != NULL)
1119         memset(result, 0, size);
1120
1121     if (result && ptralloc)
1122         return ((char *) result + PTR_GAP);
1123     return (result);
1124 }
1125
1126 /*
1127  * Change the size of an allocation.
1128  */
1129 static void *
1130 irealloc(void *ptr, size_t size)
1131 {
1132     void                *p;
1133     u_long              osize, index, i;
1134     struct pginfo       **mp;
1135     struct pginfo       **pd;
1136     struct pdinfo       *pi;
1137     u_long              pidx;
1138
1139     if (suicide)
1140         abort();
1141
1142     if (!malloc_started) {
1143         wrtwarning("malloc() has never been called");
1144         return (NULL);
1145     }
1146     if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
1147         if (size <= PTR_SIZE)
1148             return (ptr);
1149
1150         p = imalloc(size);
1151         if (p)
1152             memcpy(p, ptr, PTR_SIZE);
1153         ifree(ptr);
1154         return (p);
1155     }
1156     index = ptr2index(ptr);
1157
1158     if (index < malloc_pageshift) {
1159         wrtwarning("junk pointer, too low to make sense");
1160         return (NULL);
1161     }
1162
1163     if (index > last_index) {
1164         wrtwarning("junk pointer, too high to make sense");
1165         return (NULL);
1166     }
1167
1168     pidx = PI_IDX(index);
1169     pdir_lookup(index, &pi);
1170
1171 #ifdef MALLOC_EXTRA_SANITY
1172     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1173         wrterror("(ES): mapped pages not found in directory");
1174         errno = EFAULT;
1175         return (NULL);
1176     }
1177 #endif /* MALLOC_EXTRA_SANITY */
1178
1179     if (pi != last_dir) {
1180         prev_dir = last_dir;
1181         last_dir = pi;
1182     }
1183     pd = pi->base;
1184     mp = &pd[PI_OFF(index)];
1185
1186     if (*mp == MALLOC_FIRST) {  /* Page allocation */
1187
1188         /* Check the pointer */
1189         if ((u_long) ptr & malloc_pagemask) {
1190             wrtwarning("modified (page-) pointer");
1191             return (NULL);
1192         }
1193         /* Find the size in bytes */
1194         i = index;
1195         if (!PI_OFF(++i)) {
1196             pi = pi->next;
1197             if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1198                 pi = NULL;
1199             if (pi != NULL)
1200                 pd = pi->base;
1201         }
1202         for (osize = malloc_pagesize;pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
1203             osize += malloc_pagesize;
1204             if (!PI_OFF(++i)) {
1205                 pi = pi->next;
1206                 if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
1207                     pi = NULL;
1208                 if (pi != NULL)
1209                     pd = pi->base;
1210             }
1211         }
1212
1213         if (!malloc_realloc && size <= osize &&
1214             size > osize - malloc_pagesize) {
1215
1216             if (malloc_junk)
1217                 memset((char *)ptr + size, SOME_JUNK, osize - size);
1218                 return (ptr);   /* ..don't do anything else. */
1219         }
1220     } else if (*mp >= MALLOC_MAGIC) {   /* Chunk allocation */
1221
1222         /* Check the pointer for sane values */
1223         if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
1224             wrtwarning("modified (chunk-) pointer");
1225             return (NULL);
1226         }
1227         /* Find the chunk index in the page */
1228         i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;
1229
1230         /* Verify that it isn't a free chunk already */
1231         if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1232             wrtwarning("chunk is already free");
1233             return (NULL);
1234         }
1235         osize = (*mp)->size;
1236
1237         if (!malloc_realloc && size <= osize &&
1238             (size > osize / 2 || osize == malloc_minsize)) {
1239             if (malloc_junk)
1240                 memset((char *) ptr + size, SOME_JUNK, osize - size);
1241                 return (ptr);   /* ..don't do anything else. */
1242         }
1243     } else {
1244         wrtwarning("irealloc: pointer to wrong page");
1245         return (NULL);
1246     }
1247
1248     p = imalloc(size);
1249
1250     if (p != NULL) {
1251         /* copy the lesser of the two sizes, and free the old one */
1252         /* Don't move from/to 0 sized region !!! */
1253         if (osize != 0 && size != 0) {
1254             if (osize < size)
1255                 memcpy(p, ptr, osize);
1256             else
1257                 memcpy(p, ptr, size);
1258         }
1259         ifree(ptr);
1260     }
1261     return (p);
1262 }
1263
1264 /*
1265  * Free a sequence of pages
1266  */
1267 static __inline__ void
1268 free_pages(void *ptr, u_long index, struct pginfo * info)
1269 {
1270     u_long              i, l, cachesize = 0, pidx, lidx;
1271     struct pginfo       **pd;
1272     struct pdinfo       *pi, *spi;
1273     struct pgfree       *pf, *pt = NULL;
1274     void                *tail;
1275
1276     if (info == MALLOC_FREE) {
1277         wrtwarning("page is already free");
1278         return;
1279     }
1280     if (info != MALLOC_FIRST) {
1281         wrtwarning("free_pages: pointer to wrong page");
1282         return;
1283     }
1284     if ((u_long) ptr & malloc_pagemask) {
1285         wrtwarning("modified (page-) pointer");
1286         return;
1287     }
1288     /* Count how many pages and mark them free at the same time */
1289     pidx = PI_IDX(index);
1290     pdir_lookup(index, &pi);
1291
1292 #ifdef MALLOC_EXTRA_SANITY
1293     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1294         wrterror("(ES): mapped pages not found in directory");
1295         errno = EFAULT;
1296         return;
1297     }
1298 #endif /* MALLOC_EXTRA_SANITY */
1299
1300     spi = pi;           /* Save page index for start of region. */
1301
1302     pd = pi->base;
1303     pd[PI_OFF(index)] = MALLOC_FREE;
1304     i = 1;
1305     if (!PI_OFF(index + i)) {
1306         pi = pi->next;
1307         if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
1308             pi = NULL;
1309         else
1310             pd = pi->base;
1311     }
1312     while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
1313         pd[PI_OFF(index + i)] = MALLOC_FREE;
1314         i++;
1315         if (!PI_OFF(index + i)) {
1316             if ((pi = pi->next) == NULL ||
1317                 PD_IDX(pi->dirnum) != PI_IDX(index + i))
1318                     pi = NULL;
1319             else
1320                 pd = pi->base;
1321         }
1322     }
1323
1324     l = i << malloc_pageshift;
1325
1326     if (malloc_junk)
1327         memset(ptr, SOME_JUNK, l);
1328
1329     malloc_used -= l;
1330     malloc_guarded -= malloc_guard;
1331     if (malloc_guard) {
1332
1333 #ifdef MALLOC_EXTRA_SANITY
1334         if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) {
1335             wrterror("(ES): hole in mapped pages directory");
1336             errno = EFAULT;
1337             return;
1338         }
1339 #endif /* MALLOC_EXTRA_SANITY */
1340
1341         pd[PI_OFF(index + i)] = MALLOC_FREE;
1342         l += malloc_guard;
1343     }
1344     tail = (char *) ptr + l;
1345
1346     if (malloc_hint)
1347         madvise(ptr, l, MADV_FREE);
1348
1349     if (malloc_freeprot)
1350         mprotect(ptr, l, PROT_NONE);
1351
1352     /* Add to free-list. */
1353     if (px == NULL)
1354         px = imalloc(sizeof *px);       /* This cannot fail... */
1355     px->page = ptr;
1356     px->pdir = spi;
1357     px->size = l;
1358
1359     if (free_list.next == NULL) {
1360         /* Nothing on free list, put this at head. */
1361         px->next = NULL;
1362         px->prev = &free_list;
1363         free_list.next = px;
1364         pf = px;
1365         px = NULL;
1366     } else {
1367         /*
1368          * Find the right spot, leave pf pointing to the modified
1369          * entry.
1370          */
1371
1372         /* Race ahead here, while calculating cache size. */
1373         for (pf = free_list.next;
1374             pf->page + pf->size < ptr && pf->next != NULL;
1375             pf = pf->next)
1376                 cachesize += pf->size;
1377
1378         /* Finish cache size calculation. */
1379         pt = pf;
1380         while (pt) {
1381             cachesize += pt->size;
1382             pt = pt->next;
1383         }
1384
1385         if (pf->page > tail) {
1386             /* Insert before entry */
1387             px->next = pf;
1388             px->prev = pf->prev;
1389             pf->prev = px;
1390             px->prev->next = px;
1391             pf = px;
1392             px = NULL;
1393         } else if ((pf->page + pf->size) == ptr) {
1394             /* Append to the previous entry. */
1395             cachesize -= pf->size;
1396             pf->size += l;
1397             if (pf->next != NULL &&
1398                 pf->page + pf->size == pf->next->page) {
1399                     /* And collapse the next too. */
1400                     pt = pf->next;
1401                     pf->size += pt->size;
1402                     pf->next = pt->next;
1403                     if (pf->next != NULL)
1404                         pf->next->prev = pf;
1405             }
1406         } else if (pf->page == tail) {
1407             /* Prepend to entry. */
1408             cachesize -= pf->size;
1409             pf->size += l;
1410             pf->page = ptr;
1411             pf->pdir = spi;
1412         } else if (pf->next == NULL) {
1413             /* Append at tail of chain. */
1414             px->next = NULL;
1415             px->prev = pf;
1416             pf->next = px;
1417             pf = px;
1418             px = NULL;
1419         } else {
1420             wrterror("freelist is destroyed");
1421             errno = EFAULT;
1422             return;
1423         }
1424     }
1425
1426     if (pf->pdir != last_dir) {
1427         prev_dir = last_dir;
1428         last_dir = pf->pdir;
1429     }
1430
1431     /* Return something to OS ? */
1432     if (pf->size > (malloc_cache - cachesize)) {
1433
1434         /*
1435          * Keep the cache intact.  Notice that the '>' above guarantees that
1436          * the pf will always have at least one page afterwards.
1437          */
1438         if (munmap((char *) pf->page + (malloc_cache - cachesize),
1439             pf->size - (malloc_cache - cachesize)) != 0)
1440                 goto not_return;
1441         tail = pf->page + pf->size;
1442         lidx = ptr2index(tail) - 1;
1443         pf->size = malloc_cache - cachesize;
1444
1445         index = ptr2index(pf->page + pf->size);
1446
1447         pidx = PI_IDX(index);
1448         if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
1449             prev_dir = NULL;    /* Will be wiped out below ! */
1450
1451         for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
1452             pi = pi->next)
1453                 ;
1454
1455         spi = pi;
1456         if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
1457             pd = pi->base;
1458
1459             for (i = index; i <= lidx;) {
1460                 if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
1461                     pd[PI_OFF(i)] = MALLOC_NOT_MINE;
1462
1463 #ifdef MALLOC_EXTRA_SANITY
1464                     if (!PD_OFF(pi->dirnum)) {
1465                         wrterror("(ES): pages directory underflow");
1466                         errno = EFAULT;
1467                         return;
1468                     }
1469 #endif /* MALLOC_EXTRA_SANITY */
1470                     pi->dirnum--;
1471                 }
1472 #ifdef MALLOC_EXTRA_SANITY
1473                 else
1474                     wrtwarning("(ES): page already unmapped");
1475 #endif /* MALLOC_EXTRA_SANITY */
1476                 i++;
1477                 if (!PI_OFF(i)) {
1478                     /*
1479                      * If no page in that dir, free
1480                      * directory page.
1481                      */
1482                     if (!PD_OFF(pi->dirnum)) {
1483                         /* Remove from list. */
1484                         if (spi == pi)
1485                         spi = pi->prev;
1486                         if (pi->prev != NULL)
1487                             pi->prev->next = pi->next;
1488                         if (pi->next != NULL)
1489                             pi->next->prev = pi->prev;
1490                         pi = pi->next;
1491                         munmap(pd, malloc_pagesize);
1492                     } else
1493                         pi = pi->next;
1494                     if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(i))
1495                         break;
1496                         pd = pi->base;
1497                     }
1498                 }
1499                 if (pi && !PD_OFF(pi->dirnum)) {
1500                     /* Resulting page dir is now empty. */
1501                     /* Remove from list. */
1502                     if (spi == pi)      /* Update spi only if first. */
1503                         spi = pi->prev;
1504                     if (pi->prev != NULL)
1505                         pi->prev->next = pi->next;
1506                     if (pi->next != NULL)
1507                         pi->next->prev = pi->prev;
1508                     pi = pi->next;
1509                     munmap(pd, malloc_pagesize);
1510                 }
1511             }
1512             if (pi == NULL && malloc_brk == tail) {
1513                 /* Resize down the malloc upper boundary. */
1514                 last_index = index - 1;
1515                 malloc_brk = index2ptr(index);
1516             }
1517
1518             /* XXX: We could realloc/shrink the pagedir here I guess. */
1519             if (pf->size == 0) {        /* Remove from free-list as well. */
1520                 if (px)
1521                     ifree(px);
1522                 if ((px = pf->prev) != &free_list) {
1523                     if (pi == NULL && last_index == (index - 1)) {
1524                         if (spi == NULL) {
1525                             malloc_brk = NULL;
1526                             i = 11;
1527                         } else {
1528                             pd = spi->base;
1529                         if (PD_IDX(spi->dirnum) < pidx)
1530                             index = ((PD_IDX(spi->dirnum) + 1) * pdi_mod) - 1;
1531                         for (pi = spi, i = index;pd[PI_OFF(i)] == MALLOC_NOT_MINE;i--)
1532 #ifdef MALLOC_EXTRA_SANITY
1533                             if (!PI_OFF(i)) {
1534                                 pi = pi->prev;
1535                                 if (pi == NULL || i == 0)
1536                                     break;
1537                                 pd = pi->base;
1538                                 i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
1539                             }
1540 #else /* !MALLOC_EXTRA_SANITY */
1541                             {
1542                         }
1543 #endif /* MALLOC_EXTRA_SANITY */
1544                         malloc_brk = index2ptr(i + 1);
1545                     }
1546                     last_index = i;
1547                 }
1548                 if ((px->next = pf->next) != NULL)
1549                     px->next->prev = px;
1550             } else {
1551                 if ((free_list.next = pf->next) != NULL)
1552                     free_list.next->prev = &free_list;
1553             }
1554             px = pf;
1555             last_dir = prev_dir;
1556             prev_dir = NULL;
1557         }
1558     }
1559 not_return:
1560     if (pt != NULL)
1561         ifree(pt);
1562 }
1563
1564 /*
1565  * Free a chunk, and possibly the page it's on, if the page becomes empty.
1566  */
1567
1568 /* ARGSUSED */
1569 static __inline__ void
1570 free_bytes(void *ptr, int index, struct pginfo * info)
1571 {
1572     struct pginfo       **mp, **pd;
1573     struct pdinfo       *pi;
1574     u_long              pidx;
1575     void                *vp;
1576     int         i;
1577
1578     /* Find the chunk number on the page */
1579     i = ((u_long) ptr & malloc_pagemask) >> info->shift;
1580
1581     if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
1582         wrtwarning("modified (chunk-) pointer");
1583         return;
1584     }
1585     if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1586         wrtwarning("chunk is already free");
1587         return;
1588     }
1589     if (malloc_junk && info->size != 0)
1590         memset(ptr, SOME_JUNK, info->size);
1591
1592     info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
1593     info->free++;
1594
1595     if (info->size != 0)
1596         mp = page_dir + info->shift;
1597     else
1598         mp = page_dir;
1599
1600     if (info->free == 1) {
1601         /* Page became non-full */
1602
1603         /* Insert in address order */
1604         while (*mp != NULL && (*mp)->next != NULL &&
1605             (*mp)->next->page < info->page)
1606                 mp = &(*mp)->next;
1607         info->next = *mp;
1608         *mp = info;
1609         return;
1610     }
1611     if (info->free != info->total)
1612         return;
1613
1614     /* Find & remove this page in the queue */
1615     while (*mp != info) {
1616         mp = &((*mp)->next);
1617 #ifdef MALLOC_EXTRA_SANITY
1618         if (!*mp) {
1619             wrterror("(ES): Not on queue");
1620             errno = EFAULT;
1621             return;
1622         }
1623 #endif /* MALLOC_EXTRA_SANITY */
1624     }
1625     *mp = info->next;
1626
1627     /* Free the page & the info structure if need be */
1628     pidx = PI_IDX(ptr2index(info->page));
1629     pdir_lookup(ptr2index(info->page), &pi);
1630 #ifdef MALLOC_EXTRA_SANITY
1631     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1632         wrterror("(ES): mapped pages not found in directory");
1633         errno = EFAULT;
1634         return;
1635     }
1636 #endif /* MALLOC_EXTRA_SANITY */
1637     if (pi != last_dir) {
1638         prev_dir = last_dir;
1639         last_dir = pi;
1640     }
1641     pd = pi->base;
1642     pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
1643
1644     /* If the page was mprotected, unprotect it before releasing it */
1645     if (info->size == 0)
1646         mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);
1647
1648     vp = info->page;    /* Order is important ! */
1649     if (vp != (void *) info)
1650         ifree(info);
1651     ifree(vp);
1652 }
1653
1654 static void
1655 ifree(void *ptr)
1656 {
1657     struct pginfo       *info, **pd;
1658     u_long              pidx, index;
1659     struct pdinfo       *pi;
1660
1661     /* This is legal */
1662     if (ptr == NULL)
1663         return;
1664
1665     if (!malloc_started) {
1666         wrtwarning("malloc() has never been called");
1667         return;
1668     }
1669     /* If we're already sinking, don't make matters any worse. */
1670     if (suicide)
1671         return;
1672
1673     if (malloc_ptrguard && PTR_ALIGNED(ptr))
1674         ptr = (char *) ptr - PTR_GAP;
1675
1676     index = ptr2index(ptr);
1677
1678     if (index < malloc_pageshift) {
1679         warnx("(%p)", ptr);
1680         wrtwarning("ifree: junk pointer, too low to make sense");
1681         return;
1682     }
1683     if (index > last_index) {
1684         warnx("(%p)", ptr);
1685         wrtwarning("ifree: junk pointer, too high to make sense");
1686         return;
1687     }
1688     pidx = PI_IDX(index);
1689     pdir_lookup(index, &pi);
1690 #ifdef MALLOC_EXTRA_SANITY
1691     if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
1692         wrterror("(ES): mapped pages not found in directory");
1693         errno = EFAULT;
1694         return;
1695     }
1696 #endif /* MALLOC_EXTRA_SANITY */
1697     if (pi != last_dir) {
1698         prev_dir = last_dir;
1699         last_dir = pi;
1700     }
1701     pd = pi->base;
1702     info = pd[PI_OFF(index)];
1703
1704     if (info < MALLOC_MAGIC)
1705         free_pages(ptr, index, info);
1706     else
1707         free_bytes(ptr, index, info);
1708     return;
1709 }
1710
1711 /*
1712  * Common function for handling recursion.  Only
1713  * print the error message once, to avoid making the problem
1714  * potentially worse.
1715  */
1716 static void
1717 malloc_recurse(void)
1718 {
1719     static int  noprint;
1720
1721     if (noprint == 0) {
1722         noprint = 1;
1723         wrtwarning("recursive call");
1724     }
1725     malloc_active--;
1726     THREAD_UNLOCK();
1727     errno = EDEADLK;
1728 }
1729
1730 /*
1731  * These are the public exported interface routines.
1732  */
1733 void *
1734 malloc(size_t size)
1735 {
1736     void *r;
1737
1738     THREAD_LOCK();
1739     malloc_func = " in malloc():";
1740     if (malloc_active++) {
1741         malloc_recurse();
1742         return (NULL);
1743     }
1744     r = imalloc(size);
1745     UTRACE(0, size, r);
1746     malloc_active--;
1747     THREAD_UNLOCK();
1748     if (malloc_xmalloc && r == NULL) {
1749         wrterror("out of memory");
1750         errno = ENOMEM;
1751     }
1752     return (r);
1753 }
1754
1755 void
1756 free(void *ptr)
1757 {
1758     THREAD_LOCK();
1759     malloc_func = " in free():";
1760     if (malloc_active++) {
1761         malloc_recurse();
1762         return;
1763     }
1764     ifree(ptr);
1765     UTRACE(ptr, 0, 0);
1766     malloc_active--;
1767     THREAD_UNLOCK();
1768     return;
1769 }
1770
1771 void *
1772 realloc(void *ptr, size_t size)
1773 {
1774     void *r;
1775
1776     THREAD_LOCK();
1777     malloc_func = " in realloc():";
1778     if (malloc_active++) {
1779         malloc_recurse();
1780         return (NULL);
1781     }
1782
1783     if (ptr == NULL)
1784         r = imalloc(size);
1785     else
1786         r = irealloc(ptr, size);
1787
1788     UTRACE(ptr, size, r);
1789     malloc_active--;
1790     THREAD_UNLOCK();
1791     if (malloc_xmalloc && r == NULL) {
1792         wrterror("out of memory");
1793         errno = ENOMEM;
1794     }
1795     return (r);
1796 }