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