src/ext/OpenBSD_malloc_Linux.c

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