lib/libc/stdlib/malloc.c

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