lib/libc/stdlib/malloc.c

   1 /*      $NetBSD: malloc.c,v 1.56 2014/09/18 13:58:20 christos Exp $     */
   2
   3 /*
   4  * ----------------------------------------------------------------------------
   5  * "THE BEER-WARE LICENSE" (Revision 42):
   6  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
   7  * can do whatever you want with this stuff. If we meet some day, and you think
   8  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   9  * ----------------------------------------------------------------------------
  10  *
  11  * From FreeBSD: malloc.c,v 1.91 2006/01/12 07:28:20 jasone
  12  *
  13  */
  14
  15 #if defined(__minix)
  16 #include "extern.h"
  17 #ifdef _LIBSYS
  18 #include <minix/sysutil.h>
  19 #include <machine/param.h>
  20 #include <machine/vmparam.h>
  21 #define MALLOC_NO_SYSCALLS
  22 #define wrtwarning(w) printf("libminc malloc warning: %s\n", w)
  23 #define wrterror(w) panic("libminc malloc error: %s\n", w)
  24 #endif
  25 #endif /* defined(__minix) */
  26
  27 /*
  28  * Defining MALLOC_EXTRA_SANITY will enable extra checks which are related
  29  * to internal conditions and consistency in malloc.c. This has a
  30  * noticeable runtime performance hit, and generally will not do you
  31  * any good unless you fiddle with the internals of malloc or want
  32  * to catch random pointer corruption as early as possible.
  33  */
  34 #ifndef MALLOC_EXTRA_SANITY
  35 #undef MALLOC_EXTRA_SANITY
  36 #endif
  37
  38 /*
  39  * What to use for Junk.  This is the byte value we use to fill with
  40  * when the 'J' option is enabled.
  41  */
  42 #define SOME_JUNK       0xd0            /* as in "Duh" :-) */
  43
  44 /*
  45  * The basic parameters you can tweak.
  46  *
  47  * malloc_minsize       minimum size of an allocation in bytes.
  48  *                      If this is too small it's too much work
  49  *                      to manage them.  This is also the smallest
  50  *                      unit of alignment used for the storage
  51  *                      returned by malloc/realloc.
  52  *
  53  */
  54
  55 #include "namespace.h"
  56 #if defined(__FreeBSD__)
  57 #   if defined(__i386__)
  58 #       define malloc_minsize           16U
  59 #   endif
  60 #   if defined(__ia64__)
  61 #       define malloc_pageshift         13U
  62 #       define malloc_minsize           16U
  63 #   endif
  64 #   if defined(__alpha__)
  65 #       define malloc_pageshift         13U
  66 #       define malloc_minsize           16U
  67 #   endif
  68 #   if defined(__sparc64__)
  69 #       define malloc_pageshift         13U
  70 #       define malloc_minsize           16U
  71 #   endif
  72 #   if defined(__amd64__)
  73 #       define malloc_pageshift         12U
  74 #       define malloc_minsize           16U
  75 #   endif
  76 #   if defined(__arm__)
  77 #       define malloc_pageshift         12U
  78 #       define malloc_minsize           16U
  79 #   endif
  80 #   define HAS_UTRACE
  81 #   define UTRACE_LABEL
  82
  83 #include <sys/cdefs.h>
  84 void utrace(struct ut *, int);
  85
  86     /*
  87      * Make malloc/free/realloc thread-safe in libc for use with
  88      * kernel threads.
  89      */
  90 #   include "libc_private.h"
  91 #   include "spinlock.h"
  92     static spinlock_t thread_lock       = _SPINLOCK_INITIALIZER;
  93 #   define _MALLOC_LOCK()               if (__isthreaded) _SPINLOCK(&thread_lock);
  94 #   define _MALLOC_UNLOCK()             if (__isthreaded) _SPINUNLOCK(&thread_lock);
  95 #endif /* __FreeBSD__ */
  96
  97 #if defined(__minix)
  98 /* #undef these things so that malloc uses the non-internal symbols.
  99  * This is necessary for VM to be able to define its own versions, and
 100  * use this malloc.
 101  */
 102 #undef mmap
 103 #undef munmap
 104 #endif /* defined(__minix) */
 105
 106 #include <sys/types.h>
 107 #if defined(__NetBSD__)
 108 #   define malloc_minsize               16U
 109 #   define HAS_UTRACE
 110 #   define UTRACE_LABEL "malloc",
 111 #include <sys/cdefs.h>
 112 #include "extern.h"
 113 #if defined(LIBC_SCCS) && !defined(lint)
 114 __RCSID("$NetBSD: malloc.c,v 1.56 2014/09/18 13:58:20 christos Exp $");
 115 #endif /* LIBC_SCCS and not lint */
 116 int utrace(const char *, void *, size_t);
 117
 118 #include <reentrant.h>
 119 extern int __isthreaded;
 120 static mutex_t thread_lock = MUTEX_INITIALIZER;
 121 #define _MALLOC_LOCK()  if (__isthreaded) mutex_lock(&thread_lock);
 122 #define _MALLOC_UNLOCK()        if (__isthreaded) mutex_unlock(&thread_lock);
 123 #endif /* __NetBSD__ */
 124
 125 #if defined(__sparc__) && defined(sun)
 126 #   define malloc_minsize               16U
 127 #   define MAP_ANON                     (0)
 128     static int fdzero;
 129 #   define MMAP_FD      fdzero
 130 #   define INIT_MMAP() \
 131         { if ((fdzero = open(_PATH_DEVZERO, O_RDWR | O_CLOEXEC, 0000)) == -1) \
 132             wrterror("open of /dev/zero"); }
 133 #endif /* __sparc__ */
 134
 135 /* Insert your combination here... */
 136 #if defined(__FOOCPU__) && defined(__BAROS__)
 137 #   define malloc_minsize               16U
 138 #endif /* __FOOCPU__ && __BAROS__ */
 139
 140 #ifndef ZEROSIZEPTR
 141 #define ZEROSIZEPTR     ((void *)(uintptr_t)(1UL << (malloc_pageshift - 1)))
 142 #endif
 143
 144 /*
 145  * No user serviceable parts behind this point.
 146  */
 147 #include <sys/types.h>
 148 #include <sys/mman.h>
 149 #include <errno.h>
 150 #include <fcntl.h>
 151 #include <paths.h>
 152 #include <stddef.h>
 153 #include <stdio.h>
 154 #include <stdlib.h>
 155 #include <string.h>
 156 #include <unistd.h>
 157
 158 /*
 159  * This structure describes a page worth of chunks.
 160  */
 161
 162 struct pginfo {
 163     struct pginfo       *next;  /* next on the free list */
 164     void                *page;  /* Pointer to the page */
 165     u_short             size;   /* size of this page's chunks */
 166     u_short             shift;  /* How far to shift for this size chunks */
 167     u_short             free;   /* How many free chunks */
 168     u_short             total;  /* How many chunk */
 169     u_int               bits[1]; /* Which chunks are free */
 170 };
 171
 172 /*
 173  * This structure describes a number of free pages.
 174  */
 175
 176 struct pgfree {
 177     struct pgfree       *next;  /* next run of free pages */
 178     struct pgfree       *prev;  /* prev run of free pages */
 179     void                *page;  /* pointer to free pages */
 180     void                *end;   /* pointer to end of free pages */
 181     size_t              size;   /* number of bytes free */
 182 };
 183
 184 /*
 185  * How many bits per u_int in the bitmap.
 186  * Change only if not 8 bits/byte
 187  */
 188 #define MALLOC_BITS     ((int)(8*sizeof(u_int)))
 189
 190 /*
 191  * Magic values to put in the page_directory
 192  */
 193 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
 194 #define MALLOC_FREE     ((struct pginfo*) 1)
 195 #define MALLOC_FIRST    ((struct pginfo*) 2)
 196 #define MALLOC_FOLLOW   ((struct pginfo*) 3)
 197 #define MALLOC_MAGIC    ((struct pginfo*) 4)
 198
 199 /*
 200  * Page size related parameters, computed at run-time.
 201  */
 202 static size_t malloc_pagesize;
 203 static size_t malloc_pageshift;
 204 static size_t malloc_pagemask;
 205
 206 #ifndef malloc_minsize
 207 #define malloc_minsize                  16U
 208 #endif
 209
 210 #ifndef malloc_maxsize
 211 #define malloc_maxsize                  ((malloc_pagesize)>>1)
 212 #endif
 213
 214 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
 215 #define ptr2idx(foo) \
 216     (((size_t)(uintptr_t)(foo) >> malloc_pageshift)-malloc_origo)
 217
 218 #ifndef _MALLOC_LOCK
 219 #define _MALLOC_LOCK()
 220 #endif
 221
 222 #ifndef _MALLOC_UNLOCK
 223 #define _MALLOC_UNLOCK()
 224 #endif
 225
 226 #ifndef MMAP_FD
 227 #define MMAP_FD (-1)
 228 #endif
 229
 230 #ifndef INIT_MMAP
 231 #define INIT_MMAP()
 232 #endif
 233
 234 #if !defined(__minix)
 235 #ifndef MADV_FREE
 236 #define MADV_FREE MADV_DONTNEED
 237 #endif
 238 #else
 239 #undef MADV_FREE
 240 #endif /* !defined(__minix) */
 241
 242 /* Number of free pages we cache */
 243 static size_t malloc_cache = 16;
 244
 245 /* The offset from pagenumber to index into the page directory */
 246 static size_t malloc_origo;
 247
 248 /* The last index in the page directory we care about */
 249 static size_t last_idx;
 250
 251 /* Pointer to page directory. Allocated "as if with" malloc */
 252 static struct   pginfo **page_dir;
 253
 254 /* How many slots in the page directory */
 255 static size_t   malloc_ninfo;
 256
 257 /* Free pages line up here */
 258 static struct pgfree free_list;
 259
 260 /* Abort(), user doesn't handle problems.  */
 261 static int malloc_abort;
 262
 263 /* Are we trying to die ?  */
 264 static int suicide;
 265
 266 /* always realloc ?  */
 267 static int malloc_realloc;
 268
 269 /* pass the kernel a hint on free pages ?  */
 270 #if defined(MADV_FREE)
 271 static int malloc_hint = 0;
 272 #endif
 273
 274 /* xmalloc behaviour ?  */
 275 static int malloc_xmalloc;
 276
 277 /* sysv behaviour for malloc(0) ?  */
 278 static int malloc_sysv;
 279
 280 /* zero fill ?  */
 281 static int malloc_zero;
 282
 283 /* junk fill ?  */
 284 static int malloc_junk;
 285
 286 #ifdef HAS_UTRACE
 287
 288 /* utrace ?  */
 289 static int malloc_utrace;
 290
 291 struct ut { void *p; size_t s; void *r; };
 292
 293 #define UTRACE(a, b, c) \
 294         if (malloc_utrace) {                    \
 295                 struct ut u;                    \
 296                 u.p=a; u.s = b; u.r=c;          \
 297                 utrace(UTRACE_LABEL (void *) &u, sizeof u);     \
 298         }
 299 #else /* !HAS_UTRACE */
 300 #define UTRACE(a,b,c)
 301 #endif /* HAS_UTRACE */
 302
 303 /* my last break. */
 304 static void *malloc_brk;
 305
 306 /* one location cache for free-list holders */
 307 static struct pgfree *px;
 308
 309 /* compile-time options */
 310 const char *_malloc_options;
 311
 312 /* Name of the current public function */
 313 static const char *malloc_func;
 314
 315 /* Macro for mmap */
 316 #define MMAP(size) \
 317         mmap(NULL, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
 318             MMAP_FD, (off_t)0);
 319
 320 /*
 321  * Necessary function declarations
 322  */
 323 static int extend_pgdir(size_t idx);
 324 static void *imalloc(size_t size);
 325 static void ifree(void *ptr);
 326 static void *irealloc(void *ptr, size_t size);
 327
 328 #ifndef MALLOC_NO_SYSCALLS
 329 static void
 330 wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4)
 331 {
 332
 333     write(STDERR_FILENO, p1, strlen(p1));
 334     write(STDERR_FILENO, p2, strlen(p2));
 335     write(STDERR_FILENO, p3, strlen(p3));
 336     write(STDERR_FILENO, p4, strlen(p4));
 337 }
 338
 339 void (*_malloc_message)(const char *p1, const char *p2, const char *p3,
 340             const char *p4) = wrtmessage;
 341 static void
 342 wrterror(const char *p)
 343 {
 344
 345     suicide = 1;
 346     _malloc_message(getprogname(), malloc_func, " error: ", p);
 347     abort();
 348 }
 349
 350 static void
 351 wrtwarning(const char *p)
 352 {
 353
 354     /*
 355      * Sensitive processes, somewhat arbitrarily defined here as setuid,
 356      * setgid, root and wheel cannot afford to have malloc mistakes.
 357      */
 358     if (malloc_abort || issetugid() || getuid() == 0 || getgid() == 0)
 359         wrterror(p);
 360 }
 361 #endif
 362
 363 /*
 364  * Allocate a number of pages from the OS
 365  */
 366 static void *
 367 map_pages(size_t pages)
 368 {
 369     caddr_t result, rresult, tail;
 370     intptr_t bytes = pages << malloc_pageshift;
 371
 372     if (bytes < 0 || (size_t)bytes < pages) {
 373         errno = ENOMEM;
 374         return NULL;
 375     }
 376
 377     if ((result = sbrk(bytes)) == (void *)-1)
 378         return NULL;
 379
 380     /*
 381      * Round to a page, in case sbrk(2) did not do this for us
 382      */
 383     rresult = (caddr_t)pageround((size_t)(uintptr_t)result);
 384     if (result < rresult) {
 385         /* make sure we have enough space to fit bytes */
 386         if (sbrk((intptr_t)(rresult - result)) == (void *) -1) {
 387             /* we failed, put everything back */
 388             if (brk(result)) {
 389                 wrterror("brk(2) failed [internal error]\n");
 390             }
 391         }
 392     }
 393     tail = rresult + (size_t)bytes;
 394
 395     last_idx = ptr2idx(tail) - 1;
 396     malloc_brk = tail;
 397
 398     if ((last_idx+1) >= malloc_ninfo && !extend_pgdir(last_idx)) {
 399         malloc_brk = result;
 400         last_idx = ptr2idx(malloc_brk) - 1;
 401         /* Put back break point since we failed. */
 402         if (brk(malloc_brk))
 403             wrterror("brk(2) failed [internal error]\n");
 404         return 0;
 405     }
 406
 407     return rresult;
 408 }
 409
 410 /*
 411  * Extend page directory
 412  */
 413 static int
 414 extend_pgdir(size_t idx)
 415 {
 416     struct  pginfo **new, **old;
 417     size_t newlen, oldlen;
 418
 419     /* check for overflow */
 420     if ((((~(1UL << ((sizeof(size_t) * NBBY) - 1)) / sizeof(*page_dir)) + 1)
 421         + (malloc_pagesize / sizeof *page_dir)) < idx) {
 422         errno = ENOMEM;
 423         return 0;
 424     }
 425
 426     /* Make it this many pages */
 427     newlen = pageround(idx * sizeof *page_dir) + malloc_pagesize;
 428
 429     /* remember the old mapping size */
 430     oldlen = malloc_ninfo * sizeof *page_dir;
 431
 432     /*
 433      * NOTE: we allocate new pages and copy the directory rather than tempt
 434      * fate by trying to "grow" the region.. There is nothing to prevent
 435      * us from accidentally re-mapping space that's been allocated by our caller
 436      * via dlopen() or other mmap().
 437      *
 438      * The copy problem is not too bad, as there is 4K of page index per
 439      * 4MB of malloc arena.
 440      *
 441      * We can totally avoid the copy if we open a file descriptor to associate
 442      * the anon mappings with.  Then, when we remap the pages at the new
 443      * address, the old pages will be "magically" remapped..  But this means
 444      * keeping open a "secret" file descriptor.....
 445      */
 446
 447     /* Get new pages */
 448     new = MMAP(newlen);
 449     if (new == MAP_FAILED)
 450         return 0;
 451
 452     /* Copy the old stuff */
 453     memcpy(new, page_dir, oldlen);
 454
 455     /* register the new size */
 456     malloc_ninfo = newlen / sizeof *page_dir;
 457
 458     /* swap the pointers */
 459     old = page_dir;
 460     page_dir = new;
 461
 462     /* Now free the old stuff */
 463     munmap(old, oldlen);
 464     return 1;
 465 }
 466
 467 /*
 468  * Initialize the world
 469  */
 470 static void
 471 malloc_init(void)
 472 {
 473 #ifndef MALLOC_NO_SYSCALLS
 474     const char *p;
 475     char b[64];
 476     size_t i;
 477     ssize_t j;
 478 #endif
 479     int serrno = errno;
 480 #ifndef MALLOC_NO_SYSCALLS
 481
 482     /*
 483      * Compute page-size related variables.
 484      */
 485     malloc_pagesize = (size_t)sysconf(_SC_PAGESIZE);
 486 #else
 487     malloc_pagesize = PAGE_SIZE;
 488 #endif
 489     malloc_pagemask = malloc_pagesize - 1;
 490     for (malloc_pageshift = 0;
 491          (1UL << malloc_pageshift) != malloc_pagesize;
 492          malloc_pageshift++)
 493         /* nothing */ ;
 494
 495     INIT_MMAP();
 496
 497 #ifdef MALLOC_EXTRA_SANITY
 498     malloc_junk = 1;
 499 #endif /* MALLOC_EXTRA_SANITY */
 500
 501 #ifndef MALLOC_NO_SYSCALLS
 502     for (i = 0; i < 3; i++) {
 503         if (i == 0) {
 504             j = readlink("/etc/malloc.conf", b, sizeof b - 1);
 505             if (j == -1)
 506                 continue;
 507             b[j] = '\0';
 508             p = b;
 509         } else if (i == 1 && issetugid() == 0) {
 510             p = getenv("MALLOC_OPTIONS");
 511         } else if (i == 1) {
 512             continue;
 513         } else {
 514             p = _malloc_options;
 515         }
 516         for (; p != NULL && *p != '\0'; p++) {
 517             switch (*p) {
 518                 case '>': malloc_cache   <<= 1; break;
 519                 case '<': malloc_cache   >>= 1; break;
 520                 case 'a': malloc_abort   = 0; break;
 521                 case 'A': malloc_abort   = 1; break;
 522 #if !defined(__minix)
 523                 case 'h': malloc_hint    = 0; break;
 524                 case 'H': malloc_hint    = 1; break;
 525 #endif /* !defined(__minix) */
 526                 case 'r': malloc_realloc = 0; break;
 527                 case 'R': malloc_realloc = 1; break;
 528                 case 'j': malloc_junk    = 0; break;
 529                 case 'J': malloc_junk    = 1; break;
 530 #ifdef HAS_UTRACE
 531                 case 'u': malloc_utrace  = 0; break;
 532                 case 'U': malloc_utrace  = 1; break;
 533 #endif
 534                 case 'v': malloc_sysv    = 0; break;
 535                 case 'V': malloc_sysv    = 1; break;
 536                 case 'x': malloc_xmalloc = 0; break;
 537                 case 'X': malloc_xmalloc = 1; break;
 538                 case 'z': malloc_zero    = 0; break;
 539                 case 'Z': malloc_zero    = 1; break;
 540                 default:
 541                     _malloc_message(getprogname(), malloc_func,
 542                          " warning: ", "unknown char in MALLOC_OPTIONS\n");
 543                     break;
 544             }
 545         }
 546     }
 547 #endif
 548
 549     UTRACE(0, 0, 0);
 550
 551     /*
 552      * We want junk in the entire allocation, and zero only in the part
 553      * the user asked for.
 554      */
 555     if (malloc_zero)
 556         malloc_junk = 1;
 557
 558     /* Allocate one page for the page directory */
 559     page_dir = MMAP(malloc_pagesize);
 560
 561     if (page_dir == MAP_FAILED)
 562         wrterror("mmap(2) failed, check limits.\n");
 563
 564     /*
 565      * We need a maximum of malloc_pageshift buckets, steal these from the
 566      * front of the page_directory;
 567      */
 568     malloc_origo = pageround((size_t)(uintptr_t)sbrk((intptr_t)0))
 569         >> malloc_pageshift;
 570     malloc_origo -= malloc_pageshift;
 571
 572     malloc_ninfo = malloc_pagesize / sizeof *page_dir;
 573
 574     /* Recalculate the cache size in bytes, and make sure it's nonzero */
 575
 576     if (!malloc_cache)
 577         malloc_cache++;
 578
 579     malloc_cache <<= malloc_pageshift;
 580
 581     /*
 582      * This is a nice hack from Kaleb Keithly (kaleb@x.org).
 583      * We can sbrk(2) further back when we keep this on a low address.
 584      */
 585     px = imalloc(sizeof *px);
 586
 587     errno = serrno;
 588 }
 589
 590 /*
 591  * Allocate a number of complete pages
 592  */
 593 static void *
 594 malloc_pages(size_t size)
 595 {
 596     void *p, *delay_free = NULL;
 597     size_t i;
 598     struct pgfree *pf;
 599     size_t idx;
 600
 601     idx = pageround(size);
 602     if (idx < size) {
 603         errno = ENOMEM;
 604         return NULL;
 605     } else
 606         size = idx;
 607
 608     p = NULL;
 609
 610     /* Look for free pages before asking for more */
 611     for(pf = free_list.next; pf; pf = pf->next) {
 612
 613 #ifdef MALLOC_EXTRA_SANITY
 614         if (pf->size & malloc_pagemask)
 615             wrterror("(ES): junk length entry on free_list.\n");
 616         if (!pf->size)
 617             wrterror("(ES): zero length entry on free_list.\n");
 618         if (pf->page == pf->end)
 619             wrterror("(ES): zero entry on free_list.\n");
 620         if (pf->page > pf->end)
 621             wrterror("(ES): sick entry on free_list.\n");
 622         if ((void*)pf->page >= (void*)sbrk(0))
 623             wrterror("(ES): entry on free_list past brk.\n");
 624         if (page_dir[ptr2idx(pf->page)] != MALLOC_FREE)
 625             wrterror("(ES): non-free first page on free-list.\n");
 626         if (page_dir[ptr2idx(pf->end)-1] != MALLOC_FREE)
 627             wrterror("(ES): non-free last page on free-list.\n");
 628 #endif /* MALLOC_EXTRA_SANITY */
 629
 630         if (pf->size < size)
 631             continue;
 632
 633         if (pf->size == size) {
 634             p = pf->page;
 635             if (pf->next != NULL)
 636                     pf->next->prev = pf->prev;
 637             pf->prev->next = pf->next;
 638             delay_free = pf;
 639             break;
 640         }
 641
 642         p = pf->page;
 643         pf->page = (char *)pf->page + size;
 644         pf->size -= size;
 645         break;
 646     }
 647
 648 #ifdef MALLOC_EXTRA_SANITY
 649     if (p != NULL && page_dir[ptr2idx(p)] != MALLOC_FREE)
 650         wrterror("(ES): allocated non-free page on free-list.\n");
 651 #endif /* MALLOC_EXTRA_SANITY */
 652
 653     size >>= malloc_pageshift;
 654
 655     /* Map new pages */
 656     if (p == NULL)
 657         p = map_pages(size);
 658
 659     if (p != NULL) {
 660
 661         idx = ptr2idx(p);
 662         page_dir[idx] = MALLOC_FIRST;
 663         for (i=1;i<size;i++)
 664             page_dir[idx+i] = MALLOC_FOLLOW;
 665
 666         if (malloc_junk)
 667             memset(p, SOME_JUNK, size << malloc_pageshift);
 668     }
 669
 670     if (delay_free) {
 671         if (px == NULL)
 672             px = delay_free;
 673         else
 674             ifree(delay_free);
 675     }
 676
 677     return p;
 678 }
 679
 680 /*
 681  * Allocate a page of fragments
 682  */
 683
 684 static inline int
 685 malloc_make_chunks(int bits)
 686 {
 687     struct  pginfo *bp;
 688     void *pp;
 689     int i, k;
 690     long l;
 691
 692     /* Allocate a new bucket */
 693     pp = malloc_pages(malloc_pagesize);
 694     if (pp == NULL)
 695         return 0;
 696
 697     /* Find length of admin structure */
 698     l = (long)offsetof(struct pginfo, bits[0]);
 699     l += (long)sizeof bp->bits[0] *
 700         (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
 701
 702     /* Don't waste more than two chunks on this */
 703     if ((1<<(bits)) <= l+l) {
 704         bp = (struct  pginfo *)pp;
 705     } else {
 706         bp = imalloc((size_t)l);
 707         if (bp == NULL) {
 708             ifree(pp);
 709             return 0;
 710         }
 711     }
 712
 713     bp->size = (1<<bits);
 714     bp->shift = bits;
 715     bp->total = bp->free = (u_short)(malloc_pagesize >> bits);
 716     bp->page = pp;
 717
 718     /* set all valid bits in the bitmap */
 719     k = bp->total;
 720     i = 0;
 721
 722     /* Do a bunch at a time */
 723     for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
 724         bp->bits[i / MALLOC_BITS] = ~0U;
 725
 726     for(; i < k; i++)
 727         bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
 728
 729     if (bp == bp->page) {
 730         /* Mark the ones we stole for ourselves */
 731         for(i = 0; l > 0; i++) {
 732             bp->bits[i / MALLOC_BITS] &= ~(1 << (i % MALLOC_BITS));
 733             bp->free--;
 734             bp->total--;
 735             l -= (long)(1 << bits);
 736         }
 737     }
 738
 739     /* MALLOC_LOCK */
 740
 741     page_dir[ptr2idx(pp)] = bp;
 742
 743     bp->next = page_dir[bits];
 744     page_dir[bits] = bp;
 745
 746     /* MALLOC_UNLOCK */
 747
 748     return 1;
 749 }
 750
 751 /*
 752  * Allocate a fragment
 753  */
 754 static void *
 755 malloc_bytes(size_t size)
 756 {
 757     size_t i;
 758     int j;
 759     u_int u;
 760     struct  pginfo *bp;
 761     size_t k;
 762     u_int *lp;
 763
 764     /* Don't bother with anything less than this */
 765     if (size < malloc_minsize)
 766         size = malloc_minsize;
 767
 768
 769     /* Find the right bucket */
 770     j = 1;
 771     i = size-1;
 772     while (i >>= 1)
 773         j++;
 774
 775     /* If it's empty, make a page more of that size chunks */
 776     if (page_dir[j] == NULL && !malloc_make_chunks(j))
 777         return NULL;
 778
 779     bp = page_dir[j];
 780
 781     /* Find first word of bitmap which isn't empty */
 782     for (lp = bp->bits; !*lp; lp++)
 783         ;
 784
 785     /* Find that bit, and tweak it */
 786     u = 1;
 787     k = 0;
 788     while (!(*lp & u)) {
 789         u += u;
 790         k++;
 791     }
 792     *lp ^= u;
 793
 794     /* If there are no more free, remove from free-list */
 795     if (!--bp->free) {
 796         page_dir[j] = bp->next;
 797         bp->next = NULL;
 798     }
 799
 800     /* Adjust to the real offset of that chunk */
 801     k += (lp-bp->bits)*MALLOC_BITS;
 802     k <<= bp->shift;
 803
 804     if (malloc_junk)
 805         memset((u_char*)bp->page + k, SOME_JUNK, (size_t)bp->size);
 806
 807     return (u_char *)bp->page + k;
 808 }
 809
 810 /*
 811  * Allocate a piece of memory
 812  */
 813 static void *
 814 imalloc(size_t size)
 815 {
 816     void *result;
 817
 818     if (suicide)
 819         abort();
 820
 821     if ((size + malloc_pagesize) < size)        /* Check for overflow */
 822         result = NULL;
 823 #ifndef __minix
 824     else if ((size + malloc_pagesize) >= (uintptr_t)page_dir)
 825         result = NULL;
 826 #endif /* !__minix */
 827     else if (size <= malloc_maxsize)
 828         result = malloc_bytes(size);
 829     else
 830         result = malloc_pages(size);
 831
 832     if (malloc_abort && result == NULL)
 833         wrterror("allocation failed.\n");
 834
 835     if (malloc_zero && result != NULL)
 836         memset(result, 0, size);
 837
 838     return result;
 839 }
 840
 841 /*
 842  * Change the size of an allocation.
 843  */
 844 static void *
 845 irealloc(void *ptr, size_t size)
 846 {
 847     void *p;
 848     size_t osize, idx;
 849     struct pginfo **mp;
 850     size_t i;
 851
 852     if (suicide)
 853         abort();
 854
 855     idx = ptr2idx(ptr);
 856
 857     if (idx < malloc_pageshift) {
 858         wrtwarning("junk pointer, too low to make sense.\n");
 859         return 0;
 860     }
 861
 862     if (idx > last_idx) {
 863         wrtwarning("junk pointer, too high to make sense.\n");
 864         return 0;
 865     }
 866
 867     mp = &page_dir[idx];
 868
 869     if (*mp == MALLOC_FIRST) {                  /* Page allocation */
 870
 871         /* Check the pointer */
 872         if ((size_t)(uintptr_t)ptr & malloc_pagemask) {
 873             wrtwarning("modified (page-) pointer.\n");
 874             return NULL;
 875         }
 876
 877         /* Find the size in bytes */
 878         for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;)
 879             osize += malloc_pagesize;
 880
 881         if (!malloc_realloc &&                  /* unless we have to, */
 882           size <= osize &&                      /* .. or are too small, */
 883           size > (osize - malloc_pagesize)) {   /* .. or can free a page, */
 884             if (malloc_junk)
 885                 memset((u_char *)ptr + size, SOME_JUNK, osize-size);
 886             return ptr;                         /* don't do anything. */
 887         }
 888
 889     } else if (*mp >= MALLOC_MAGIC) {           /* Chunk allocation */
 890
 891         /* Check the pointer for sane values */
 892         if (((size_t)(uintptr_t)ptr & ((*mp)->size-1))) {
 893             wrtwarning("modified (chunk-) pointer.\n");
 894             return NULL;
 895         }
 896
 897         /* Find the chunk index in the page */
 898         i = ((size_t)(uintptr_t)ptr & malloc_pagemask) >> (*mp)->shift;
 899
 900         /* Verify that it isn't a free chunk already */
 901         if ((*mp)->bits[i/MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
 902             wrtwarning("chunk is already free.\n");
 903             return NULL;
 904         }
 905
 906         osize = (*mp)->size;
 907
 908         if (!malloc_realloc &&          /* Unless we have to, */
 909           size <= osize &&              /* ..or are too small, */
 910           (size > osize / 2 ||          /* ..or could use a smaller size, */
 911           osize == malloc_minsize)) {   /* ..(if there is one) */
 912             if (malloc_junk)
 913                 memset((u_char *)ptr + size, SOME_JUNK, osize-size);
 914             return ptr;                 /* ..Don't do anything */
 915         }
 916
 917     } else {
 918         wrtwarning("pointer to wrong page.\n");
 919         return NULL;
 920     }
 921
 922     p = imalloc(size);
 923
 924     if (p != NULL) {
 925         /* copy the lesser of the two sizes, and free the old one */
 926         if (!size || !osize)
 927             ;
 928         else if (osize < size)
 929             memcpy(p, ptr, osize);
 930         else
 931             memcpy(p, ptr, size);
 932         ifree(ptr);
 933     }
 934     return p;
 935 }
 936
 937 /*
 938  * Free a sequence of pages
 939  */
 940
 941 static inline void
 942 free_pages(void *ptr, size_t idx, struct pginfo *info)
 943 {
 944     size_t i;
 945     struct pgfree *pf, *pt=NULL;
 946     size_t l;
 947     void *tail;
 948
 949     if (info == MALLOC_FREE) {
 950         wrtwarning("page is already free.\n");
 951         return;
 952     }
 953
 954     if (info != MALLOC_FIRST) {
 955         wrtwarning("pointer to wrong page.\n");
 956         return;
 957     }
 958
 959     if ((size_t)(uintptr_t)ptr & malloc_pagemask) {
 960         wrtwarning("modified (page-) pointer.\n");
 961         return;
 962     }
 963
 964     /* Count how many pages and mark them free at the same time */
 965     page_dir[idx] = MALLOC_FREE;
 966     for (i = 1; page_dir[idx+i] == MALLOC_FOLLOW; i++)
 967         page_dir[idx + i] = MALLOC_FREE;
 968
 969     l = i << malloc_pageshift;
 970
 971     if (malloc_junk)
 972         memset(ptr, SOME_JUNK, l);
 973
 974 #if !defined(__minix)
 975     if (malloc_hint)
 976         madvise(ptr, l, MADV_FREE);
 977 #endif /* !defined(__minix) */
 978
 979     tail = (char *)ptr+l;
 980
 981     /* add to free-list */
 982     if (px == NULL)
 983         px = imalloc(sizeof *px);       /* This cannot fail... */
 984     px->page = ptr;
 985     px->end =  tail;
 986     px->size = l;
 987     if (free_list.next == NULL) {
 988
 989         /* Nothing on free list, put this at head */
 990         px->next = free_list.next;
 991         px->prev = &free_list;
 992         free_list.next = px;
 993         pf = px;
 994         px = NULL;
 995
 996     } else {
 997
 998         /* Find the right spot, leave pf pointing to the modified entry. */
 999         tail = (char *)ptr+l;
1000
1001         for(pf = free_list.next; pf->end < ptr && pf->next != NULL;
1002             pf = pf->next)
1003             ; /* Race ahead here */
1004
1005         if (pf->page > tail) {
1006             /* Insert before entry */
1007             px->next = pf;
1008             px->prev = pf->prev;
1009             pf->prev = px;
1010             px->prev->next = px;
1011             pf = px;
1012             px = NULL;
1013         } else if (pf->end == ptr ) {
1014             /* Append to the previous entry */
1015             pf->end = (char *)pf->end + l;
1016             pf->size += l;
1017             if (pf->next != NULL && pf->end == pf->next->page ) {
1018                 /* And collapse the next too. */
1019                 pt = pf->next;
1020                 pf->end = pt->end;
1021                 pf->size += pt->size;
1022                 pf->next = pt->next;
1023                 if (pf->next != NULL)
1024                     pf->next->prev = pf;
1025             }
1026         } else if (pf->page == tail) {
1027             /* Prepend to entry */
1028             pf->size += l;
1029             pf->page = ptr;
1030         } else if (pf->next == NULL) {
1031             /* Append at tail of chain */
1032             px->next = NULL;
1033             px->prev = pf;
1034             pf->next = px;
1035             pf = px;
1036             px = NULL;
1037         } else {
1038             wrterror("freelist is destroyed.\n");
1039         }
1040     }
1041
1042     /* Return something to OS ? */
1043     if (pf->next == NULL &&                     /* If we're the last one, */
1044       pf->size > malloc_cache &&                /* ..and the cache is full, */
1045       pf->end == malloc_brk &&                  /* ..and none behind us, */
1046       malloc_brk == sbrk((intptr_t)0)) {        /* ..and it's OK to do... */
1047
1048         /*
1049          * Keep the cache intact.  Notice that the '>' above guarantees that
1050          * the pf will always have at least one page afterwards.
1051          */
1052         pf->end = (char *)pf->page + malloc_cache;
1053         pf->size = malloc_cache;
1054
1055         brk(pf->end);
1056         malloc_brk = pf->end;
1057
1058         idx = ptr2idx(pf->end);
1059
1060         for(i=idx;i <= last_idx;)
1061             page_dir[i++] = MALLOC_NOT_MINE;
1062
1063         last_idx = idx - 1;
1064
1065         /* XXX: We could realloc/shrink the pagedir here I guess. */
1066     }
1067     if (pt != NULL)
1068         ifree(pt);
1069 }
1070
1071 /*
1072  * Free a chunk, and possibly the page it's on, if the page becomes empty.
1073  */
1074
1075 static inline void
1076 free_bytes(void *ptr, size_t idx, struct pginfo *info)
1077 {
1078     size_t i;
1079     struct pginfo **mp;
1080     void *vp;
1081
1082     /* Find the chunk number on the page */
1083     i = ((size_t)(uintptr_t)ptr & malloc_pagemask) >> info->shift;
1084
1085     if (((size_t)(uintptr_t)ptr & (info->size-1))) {
1086         wrtwarning("modified (chunk-) pointer.\n");
1087         return;
1088     }
1089
1090     if (info->bits[i/MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
1091         wrtwarning("chunk is already free.\n");
1092         return;
1093     }
1094
1095     if (malloc_junk)
1096         memset(ptr, SOME_JUNK, (size_t)info->size);
1097
1098     info->bits[i/MALLOC_BITS] |= (u_int)(1UL << (i % MALLOC_BITS));
1099     info->free++;
1100
1101     mp = page_dir + info->shift;
1102
1103     if (info->free == 1) {
1104
1105         /* Page became non-full */
1106
1107         mp = page_dir + info->shift;
1108         /* Insert in address order */
1109         while (*mp && (*mp)->next && (*mp)->next->page < info->page)
1110             mp = &(*mp)->next;
1111         info->next = *mp;
1112         *mp = info;
1113         return;
1114     }
1115
1116     if (info->free != info->total)
1117         return;
1118
1119     /* Find & remove this page in the queue */
1120     while (*mp != info) {
1121         mp = &((*mp)->next);
1122 #ifdef MALLOC_EXTRA_SANITY
1123         if (!*mp)
1124                 wrterror("(ES): Not on queue.\n");
1125 #endif /* MALLOC_EXTRA_SANITY */
1126     }
1127     *mp = info->next;
1128
1129     /* Free the page & the info structure if need be */
1130     page_dir[idx] = MALLOC_FIRST;
1131     vp = info->page;            /* Order is important ! */
1132     if(vp != (void*)info)
1133         ifree(info);
1134     ifree(vp);
1135 }
1136
1137 static void
1138 ifree(void *ptr)
1139 {
1140     struct pginfo *info;
1141     size_t idx;
1142
1143     /* This is legal */
1144     if (ptr == NULL)
1145         return;
1146
1147     /* If we're already sinking, don't make matters any worse. */
1148     if (suicide)
1149         return;
1150
1151     idx = ptr2idx(ptr);
1152
1153     if (idx < malloc_pageshift) {
1154         wrtwarning("junk pointer, too low to make sense.\n");
1155         return;
1156     }
1157
1158     if (idx > last_idx) {
1159         wrtwarning("junk pointer, too high to make sense.\n");
1160         return;
1161     }
1162
1163     info = page_dir[idx];
1164
1165     if (info < MALLOC_MAGIC)
1166         free_pages(ptr, idx, info);
1167     else
1168         free_bytes(ptr, idx, info);
1169     return;
1170 }
1171
1172 static int malloc_active; /* Recursion flag for public interface. */
1173 static unsigned malloc_started; /* Set when initialization has been done */
1174
1175 static void *
1176 pubrealloc(void *ptr, size_t size, const char *func)
1177 {
1178     void *r;
1179     int err = 0;
1180
1181     /*
1182      * If a thread is inside our code with a functional lock held, and then
1183      * catches a signal which calls us again, we would get a deadlock if the
1184      * lock is not of a recursive type.
1185      */
1186     _MALLOC_LOCK();
1187     malloc_func = func;
1188     if (malloc_active > 0) {
1189         if (malloc_active == 1) {
1190             wrtwarning("recursive call\n");
1191             malloc_active = 2;
1192         }
1193         _MALLOC_UNLOCK();
1194         errno = EINVAL;
1195         return (NULL);
1196     }
1197     malloc_active = 1;
1198
1199     if (!malloc_started) {
1200         if (ptr != NULL) {
1201             wrtwarning("malloc() has never been called\n");
1202             malloc_active = 0;
1203             _MALLOC_UNLOCK();
1204             errno = EINVAL;
1205             return (NULL);
1206         }
1207         malloc_init();
1208         malloc_started = 1;
1209     }
1210
1211     if (ptr == ZEROSIZEPTR)
1212         ptr = NULL;
1213     if (malloc_sysv && !size) {
1214         if (ptr != NULL)
1215             ifree(ptr);
1216         r = NULL;
1217     } else if (!size) {
1218         if (ptr != NULL)
1219             ifree(ptr);
1220         r = ZEROSIZEPTR;
1221     } else if (ptr == NULL) {
1222         r = imalloc(size);
1223         err = (r == NULL);
1224     } else {
1225         r = irealloc(ptr, size);
1226         err = (r == NULL);
1227     }
1228     UTRACE(ptr, size, r);
1229     malloc_active = 0;
1230     _MALLOC_UNLOCK();
1231     if (malloc_xmalloc && err)
1232         wrterror("out of memory\n");
1233     if (err)
1234         errno = ENOMEM;
1235     return (r);
1236 }
1237
1238 /*
1239  * These are the public exported interface routines.
1240  */
1241
1242 void *
1243 malloc(size_t size)
1244 {
1245
1246     return pubrealloc(NULL, size, " in malloc():");
1247 }
1248
1249 int
1250 posix_memalign(void **memptr, size_t alignment, size_t size)
1251 {
1252     int err;
1253     void *result;
1254
1255     if (!malloc_started) {
1256             malloc_init();
1257             malloc_started = 1;
1258     }
1259     /* Make sure that alignment is a large enough power of 2. */
1260     if (((alignment - 1) & alignment) != 0 || alignment < sizeof(void *) ||
1261         alignment > malloc_pagesize)
1262             return EINVAL;
1263
1264     /*
1265      * (size | alignment) is enough to assure the requested alignment, since
1266      * the allocator always allocates power-of-two blocks.
1267      */
1268     err = errno; /* Protect errno against changes in pubrealloc(). */
1269     result = pubrealloc(NULL, (size | alignment), " in posix_memalign()");
1270     errno = err;
1271
1272     if (result == NULL)
1273         return ENOMEM;
1274
1275     *memptr = result;
1276     return 0;
1277 }
1278
1279 void *
1280 calloc(size_t num, size_t size)
1281 {
1282     void *ret;
1283
1284     if (size != 0 && (num * size) / size != num) {
1285         /* size_t overflow. */
1286         errno = ENOMEM;
1287         return (NULL);
1288     }
1289
1290     ret = pubrealloc(NULL, num * size, " in calloc():");
1291
1292     if (ret != NULL)
1293         memset(ret, 0, num * size);
1294
1295     return ret;
1296 }
1297
1298 void
1299 free(void *ptr)
1300 {
1301
1302     pubrealloc(ptr, 0, " in free():");
1303 }
1304
1305 void *
1306 realloc(void *ptr, size_t size)
1307 {
1308
1309     return pubrealloc(ptr, size, " in realloc():");
1310 }
1311
1312 /*
1313  * Begin library-private functions, used by threading libraries for protection
1314  * of malloc during fork().  These functions are only called if the program is
1315  * running in threaded mode, so there is no need to check whether the program
1316  * is threaded here.
1317  */
1318
1319 void
1320 _malloc_prefork(void)
1321 {
1322
1323         _MALLOC_LOCK();
1324 }
1325
1326 void
1327 _malloc_postfork(void)
1328 {
1329
1330         _MALLOC_UNLOCK();
1331 }