6/lib/libc/stdlib/malloc.c

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