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