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