1 files changed, 1242 insertions, 0 deletions

diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c
new file mode 100644
index 0000000000..d1d8759791
--- /dev/null
+++ b/src/lib/libc/stdlib/malloc.c
@@ -0,0 +1,1242 @@
+/*
+ * ----------------------------------------------------------------------------
+ * "THE BEER-WARE LICENSE" (Revision 42):
+ * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
+ * can do whatever you want with this stuff. If we meet some day, and you think
+ * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
+ * ----------------------------------------------------------------------------
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char rcsid[] = "$OpenBSD: malloc.c,v 1.32 1998/08/06 16:26:32 millert Exp $";
+#endif /* LIBC_SCCS and not lint */
+
+/*
+ * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
+ * related to internal conditions and consistency in malloc.c. This has
+ * a noticeable runtime performance hit, and generally will not do you
+ * any good unless you fiddle with the internals of malloc or want
+ * to catch random pointer corruption as early as possible.
+ */
+#ifndef MALLOC_EXTRA_SANITY
+#undef MALLOC_EXTRA_SANITY
+#endif
+
+/*
+ * Defining MALLOC_STATS will enable you to call malloc_dump() and set
+ * the [dD] options in the MALLOC_OPTIONS environment variable.
+ * It has no run-time performance hit, but does pull in stdio...
+ */
+#ifndef MALLOC_STATS
+#undef MALLOC_STATS
+#endif
+
+/*
+ * What to use for Junk.  This is the byte value we use to fill with
+ * when the 'J' option is enabled.
+ */
+#define SOME_JUNK       0xd0            /* as in "Duh" :-) */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <sys/types.h>
+#include <sys/param.h>
+#include <sys/mman.h>
+
+/*
+ * The basic parameters you can tweak.
+ *
+ * malloc_pageshift     pagesize = 1 << malloc_pageshift
+ *                      It's probably best if this is the native
+ *                      page size, but it shouldn't have to be.
+ *
+ * malloc_minsize       minimum size of an allocation in bytes.
+ *                      If this is too small it's too much work
+ *                      to manage them.  This is also the smallest
+ *                      unit of alignment used for the storage
+ *                      returned by malloc/realloc.
+ *
+ */
+
+#if defined(__i386__) && defined(__FreeBSD__)
+#   define malloc_pageshift             12U
+#   define malloc_minsize               16U
+#endif /* __i386__ && __FreeBSD__ */
+
+#if defined(__sparc__) && !defined(__OpenBSD__)
+#   define malloc_pageshirt             12U
+#   define malloc_minsize               16U
+#   define MAP_ANON                     (0)
+#   define USE_DEV_ZERO
+#   define MADV_FREE                    MADV_DONTNEED
+#endif /* __sparc__ */
+
+/* Insert your combination here... */
+#if defined(__FOOCPU__) && defined(__BAROS__)
+#   define malloc_pageshift             12U
+#   define malloc_minsize               16U
+#endif /* __FOOCPU__ && __BAROS__ */
+
+#if defined(__OpenBSD__) && !defined(__sparc__)
+#   define      malloc_pageshift        (PGSHIFT)
+#   define      malloc_minsize          16U
+#endif /* __OpenBSD__ */
+
+#ifdef _THREAD_SAFE
+#include <pthread.h>
+static pthread_mutex_t malloc_lock;
+#define THREAD_LOCK()           pthread_mutex_lock(&malloc_lock)
+#define THREAD_UNLOCK()         pthread_mutex_unlock(&malloc_lock)
+#define THREAD_LOCK_INIT()      pthread_mutex_init(&malloc_lock, 0);
+#else
+#define THREAD_LOCK()
+#define THREAD_UNLOCK()
+#define THREAD_LOCK_INIT()
+#endif
+
+/*
+ * No user serviceable parts behind this point.
+ *
+ * This structure describes a page worth of chunks.
+ */
+
+struct pginfo {
+    struct pginfo       *next;  /* next on the free list */
+    void                *page;  /* Pointer to the page */
+    u_short             size;   /* size of this page's chunks */
+    u_short             shift;  /* How far to shift for this size chunks */
+    u_short             free;   /* How many free chunks */
+    u_short             total;  /* How many chunk */
+    u_long              bits[1]; /* Which chunks are free */
+};
+
+/*
+ * This structure describes a number of free pages.
+ */
+
+struct pgfree {
+    struct pgfree       *next;  /* next run of free pages */
+    struct pgfree       *prev;  /* prev run of free pages */
+    void                *page;  /* pointer to free pages */
+    void                *end;   /* pointer to end of free pages */
+    u_long              size;   /* number of bytes free */
+};
+
+/*
+ * How many bits per u_long in the bitmap.
+ * Change only if not 8 bits/byte
+ */
+#define MALLOC_BITS     (8*sizeof(u_long))
+
+/*
+ * Magic values to put in the page_directory
+ */
+#define MALLOC_NOT_MINE ((struct pginfo*) 0)
+#define MALLOC_FREE     ((struct pginfo*) 1)
+#define MALLOC_FIRST    ((struct pginfo*) 2)
+#define MALLOC_FOLLOW   ((struct pginfo*) 3)
+#define MALLOC_MAGIC    ((struct pginfo*) 4)
+
+#ifndef malloc_pageshift
+#define malloc_pageshift                12U
+#endif
+
+#ifndef malloc_minsize
+#define malloc_minsize                  16U
+#endif
+
+#ifndef malloc_pageshift
+#error  "malloc_pageshift undefined"
+#endif
+
+#if !defined(malloc_pagesize)
+#define malloc_pagesize                 (1UL<<malloc_pageshift)
+#endif
+
+#if ((1UL<<malloc_pageshift) != malloc_pagesize)
+#error  "(1UL<<malloc_pageshift) != malloc_pagesize"
+#endif
+
+#ifndef malloc_maxsize
+#define malloc_maxsize                  ((malloc_pagesize)>>1)
+#endif
+
+/* A mask for the offset inside a page.  */
+#define malloc_pagemask ((malloc_pagesize)-1)
+
+#define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
+#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo)
+
+/* fd of /dev/zero */
+#ifdef USE_DEV_ZERO
+static int fdzero;
+#define MMAP_FD fdzero
+#define INIT_MMAP() \
+        { if ((fdzero=open("/dev/zero", O_RDWR, 0000)) == -1) \
+            wrterror("open of /dev/zero"); }
+#else
+#define MMAP_FD (-1)
+#define INIT_MMAP()
+#endif
+
+/* Set when initialization has been done */
+static unsigned malloc_started; 
+
+/* Number of free pages we cache */
+static unsigned malloc_cache = 16;
+
+/* The offset from pagenumber to index into the page directory */
+static u_long malloc_origo;
+
+/* The last index in the page directory we care about */
+static u_long last_index;
+
+/* Pointer to page directory. Allocated "as if with" malloc */
+static struct   pginfo **page_dir;
+
+/* How many slots in the page directory */
+static size_t   malloc_ninfo;
+
+/* Free pages line up here */
+static struct pgfree free_list;
+
+/* Abort(), user doesn't handle problems.  */
+static int malloc_abort;
+
+/* Are we trying to die ?  */
+static int suicide;
+
+#ifdef MALLOC_STATS
+/* dump statistics */
+static int malloc_stats;
+#endif
+
+/* avoid outputting warnings?  */
+static int malloc_silent;
+
+/* always realloc ?  */
+static int malloc_realloc;
+
+#ifdef __FreeBSD__
+/* pass the kernel a hint on free pages ?  */
+static int malloc_hint;
+#endif
+
+/* xmalloc behaviour ?  */
+static int malloc_xmalloc;
+
+/* zero fill ?  */
+static int malloc_zero;
+
+/* junk fill ?  */
+static int malloc_junk;
+
+#ifdef __FreeBSD__
+/* utrace ?  */
+static int malloc_utrace;
+
+struct ut { void *p; size_t s; void *r; };
+
+void utrace __P((struct ut *, int));
+
+#define UTRACE(a, b, c) \
+        if (malloc_utrace) \
+                {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
+#else /* !__FreeBSD__ */
+#define UTRACE(a,b,c)
+#endif
+
+/* my last break. */
+static void *malloc_brk;
+
+/* one location cache for free-list holders */
+static struct pgfree *px;
+
+/* compile-time options */
+char *malloc_options;
+
+/* Name of the current public function */
+static char *malloc_func;
+
+/* Macro for mmap */
+#define MMAP(size) \
+        mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
+            MMAP_FD, (off_t)0);
+
+/*
+ * Necessary function declarations
+ */
+static int extend_pgdir(u_long index);
+static void *imalloc(size_t size);
+static void ifree(void *ptr);
+static void *irealloc(void *ptr, size_t size);
+static void *malloc_bytes(size_t size);
+
+#ifdef MALLOC_STATS
+void
+malloc_dump(fd)
+    FILE *fd;
+{
+    struct pginfo **pd;
+    struct pgfree *pf;
+    int j;
+
+    pd = page_dir;
+
+    /* print out all the pages */
+    for(j=0;j<=last_index;j++) {
+        fprintf(fd, "%08lx %5d ", (j+malloc_origo) << malloc_pageshift, j);
+        if (pd[j] == MALLOC_NOT_MINE) {
+            for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++)
+                ;
+            j--;
+            fprintf(fd, ".. %5d not mine\n",    j);
+        } else if (pd[j] == MALLOC_FREE) {
+            for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++)
+                ;
+            j--;
+            fprintf(fd, ".. %5d free\n", j);
+        } else if (pd[j] == MALLOC_FIRST) {
+            for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++)
+                ;
+            j--;
+            fprintf(fd, ".. %5d in use\n", j);
+        } else if (pd[j] < MALLOC_MAGIC) {
+            fprintf(fd, "(%p)\n", pd[j]);
+        } else {
+            fprintf(fd, "%p %d (of %d) x %d @ %p --> %p\n",
+                pd[j], pd[j]->free, pd[j]->total,
+                pd[j]->size, pd[j]->page, pd[j]->next);
+        }
+    }
+
+    for(pf=free_list.next; pf; pf=pf->next) {
+        fprintf(fd, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
+                pf, pf->page, pf->end, pf->size, pf->prev, pf->next);
+        if (pf == pf->next) {
+                fprintf(fd, "Free_list loops.\n");
+                break;
+        }
+    }
+
+    /* print out various info */
+    fprintf(fd, "Minsize\t%d\n", malloc_minsize);
+    fprintf(fd, "Maxsize\t%d\n", malloc_maxsize);
+    fprintf(fd, "Pagesize\t%lu\n", (u_long)malloc_pagesize);
+    fprintf(fd, "Pageshift\t%d\n", malloc_pageshift);
+    fprintf(fd, "FirstPage\t%ld\n", malloc_origo);
+    fprintf(fd, "LastPage\t%ld %lx\n", last_index+malloc_pageshift,
+        (last_index + malloc_pageshift) << malloc_pageshift);
+    fprintf(fd, "Break\t%ld\n", (u_long)sbrk(0) >> malloc_pageshift);
+}
+#endif /* MALLOC_STATS */
+
+extern char *__progname;
+
+static void
+wrterror(p)
+    char *p;
+{
+    char *q = " error: ";
+    write(2, __progname, strlen(__progname));
+    write(2, malloc_func, strlen(malloc_func));
+    write(2, q, strlen(q));
+    write(2, p, strlen(p));
+    suicide = 1;
+#ifdef MALLOC_STATS
+    if (malloc_stats)
+        malloc_dump(stderr);
+#endif /* MALLOC_STATS */
+    abort();
+}
+
+static void
+wrtwarning(p)
+    char *p;
+{
+    char *q = " warning: ";
+    if (malloc_abort)
+        wrterror(p);
+    else if (malloc_silent)
+        return;
+    write(2, __progname, strlen(__progname));
+    write(2, malloc_func, strlen(malloc_func));
+    write(2, q, strlen(q));
+    write(2, p, strlen(p));
+}
+
+#ifdef MALLOC_STATS
+static void
+malloc_exit()
+{
+    FILE *fd = fopen("malloc.out", "a");
+    char *q = "malloc() warning: Couldn't dump stats.\n";
+    if (fd) {
+        malloc_dump(fd);
+        fclose(fd);
+    } else
+        write(2, q, strlen(q));
+}
+#endif /* MALLOC_STATS */
+
+
+/*
+ * Allocate a number of pages from the OS
+ */
+static void *
+map_pages(pages)
+    int pages;
+{
+    caddr_t result, tail;
+
+    result = (caddr_t)pageround((u_long)sbrk(0));
+    tail = result + (pages << malloc_pageshift);
+
+    if (brk(tail)) {
+#ifdef MALLOC_EXTRA_SANITY
+        wrterror("(ES): map_pages fails\n");
+#endif /* MALLOC_EXTRA_SANITY */
+        return 0;
+    }
+
+    last_index = ptr2index(tail) - 1;
+    malloc_brk = tail;
+
+    if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index))
+        return 0;
+
+    return result;
+}
+
+/*
+ * Extend page directory
+ */
+static int
+extend_pgdir(index)
+    u_long index;
+{
+    struct  pginfo **new, **old;
+    size_t i, oldlen;
+
+    /* Make it this many pages */
+    i = index * sizeof *page_dir;
+    i /= malloc_pagesize;
+    i += 2;
+
+    /* remember the old mapping size */
+    oldlen = malloc_ninfo * sizeof *page_dir;
+
+    /*
+     * NOTE: we allocate new pages and copy the directory rather than tempt
+     * fate by trying to "grow" the region.. There is nothing to prevent
+     * us from accidently re-mapping space that's been allocated by our caller
+     * via dlopen() or other mmap().
+     *
+     * The copy problem is not too bad, as there is 4K of page index per
+     * 4MB of malloc arena.
+     *
+     * We can totally avoid the copy if we open a file descriptor to associate
+     * the anon mappings with.  Then, when we remap the pages at the new
+     * address, the old pages will be "magically" remapped..  But this means
+     * keeping open a "secret" file descriptor.....
+     */
+
+    /* Get new pages */
+    new = (struct pginfo**) MMAP(i * malloc_pagesize);
+    if (new == (struct pginfo **)-1)
+        return 0;
+
+    /* Copy the old stuff */
+    memcpy(new, page_dir,
+            malloc_ninfo * sizeof *page_dir);
+
+    /* register the new size */
+    malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
+
+    /* swap the pointers */
+    old = page_dir;
+    page_dir = new;
+
+    /* Now free the old stuff */
+    munmap(old, oldlen);
+    return 1;
+}
+
+/*
+ * Initialize the world
+ */
+static void
+malloc_init ()
+{
+    char *p, b[64];
+    int i, j;
+    int save_errno = errno;
+
+    THREAD_LOCK_INIT();
+
+    INIT_MMAP();
+
+#ifdef MALLOC_EXTRA_SANITY
+    malloc_junk = 1;
+#endif /* MALLOC_EXTRA_SANITY */
+
+    for (i = 0; i < 3; i++) {
+        if (i == 0) {
+            j = readlink("/etc/malloc.conf", b, sizeof b - 1);
+            if (j <= 0)
+                continue;
+            b[j] = '\0';
+            p = b;
+        } else if (i == 1) {
+            if (issetugid() == 0)
+                p = getenv("MALLOC_OPTIONS");
+            else
+                continue;
+        } else if (i == 2) {
+            p = malloc_options;
+        }
+        for (; p && *p; p++) {
+            switch (*p) {
+                case '>': malloc_cache   <<= 1; break;
+                case '<': malloc_cache   >>= 1; break;
+                case 'a': malloc_abort   = 0; break;
+                case 'A': malloc_abort   = 1; break;
+#ifdef MALLOC_STATS
+                case 'd': malloc_stats   = 0; break;
+                case 'D': malloc_stats   = 1; break;
+#endif /* MALLOC_STATS */
+#ifdef __FreeBSD__
+                case 'h': malloc_hint    = 0; break;
+                case 'H': malloc_hint    = 1; break;
+#endif /* __FreeBSD__ */
+                case 'r': malloc_realloc = 0; break;
+                case 'R': malloc_realloc = 1; break;
+                case 'j': malloc_junk    = 0; break;
+                case 'J': malloc_junk    = 1; break;
+                case 'n': malloc_silent  = 0; break;
+                case 'N': malloc_silent  = 1; break;
+#ifdef __FreeBSD__
+                case 'u': malloc_utrace  = 0; break;
+                case 'U': malloc_utrace  = 1; break;
+#endif /* __FreeBSD__ */
+                case 'x': malloc_xmalloc = 0; break;
+                case 'X': malloc_xmalloc = 1; break;
+                case 'z': malloc_zero    = 0; break;
+                case 'Z': malloc_zero    = 1; break;
+                default:
+                    j = malloc_abort;
+                    malloc_abort = 0;
+                    wrtwarning("unknown char in MALLOC_OPTIONS\n");
+                    malloc_abort = j;
+                    break;
+            }
+        }
+    }
+
+    UTRACE(0, 0, 0);
+
+    /*
+     * We want junk in the entire allocation, and zero only in the part
+     * the user asked for.
+     */
+    if (malloc_zero)
+        malloc_junk=1;
+
+#ifdef MALLOC_STATS
+    if (malloc_stats)
+        atexit(malloc_exit);
+#endif /* MALLOC_STATS */
+
+    /* Allocate one page for the page directory */
+    page_dir = (struct pginfo **) MMAP(malloc_pagesize);
+
+    if (page_dir == (struct pginfo **) -1)
+        wrterror("mmap(2) failed, check limits.\n");
+
+    /*
+     * We need a maximum of malloc_pageshift buckets, steal these from the
+     * front of the page_directory;
+     */
+    malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift;
+    malloc_origo -= malloc_pageshift;
+
+    malloc_ninfo = malloc_pagesize / sizeof *page_dir;
+
+    /* Been here, done that */
+    malloc_started++;
+
+    /* Recalculate the cache size in bytes, and make sure it's nonzero */
+
+    if (!malloc_cache)
+        malloc_cache++;
+
+    malloc_cache <<= malloc_pageshift;
+
+    /*
+     * This is a nice hack from Kaleb Keithly (kaleb@x.org).
+     * We can sbrk(2) further back when we keep this on a low address.
+     */
+    px = (struct pgfree *) imalloc (sizeof *px);
+    errno = save_errno;
+}
+
+/*
+ * Allocate a number of complete pages
+ */
+static void *
+malloc_pages(size)
+    size_t size;
+{
+    void *p, *delay_free = 0;
+    int i;
+    struct pgfree *pf;
+    u_long index;
+
+    size = pageround(size);
+
+    p = 0;
+    /* Look for free pages before asking for more */
+    for(pf = free_list.next; pf; pf = pf->next) {
+
+#ifdef MALLOC_EXTRA_SANITY
+        if (pf->size & malloc_pagemask)
+            wrterror("(ES): junk length entry on free_list\n");
+        if (!pf->size)
+            wrterror("(ES): zero length entry on free_list\n");
+        if (pf->page == pf->end)
+            wrterror("(ES): zero entry on free_list\n");
+        if (pf->page > pf->end) 
+            wrterror("(ES): sick entry on free_list\n");
+        if ((void*)pf->page >= (void*)sbrk(0))
+            wrterror("(ES): entry on free_list past brk\n");
+        if (page_dir[ptr2index(pf->page)] != MALLOC_FREE) 
+            wrterror("(ES): non-free first page on free-list\n");
+        if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE)
+            wrterror("(ES): non-free last page on free-list\n");
+#endif /* MALLOC_EXTRA_SANITY */
+
+        if (pf->size < size)
+            continue;
+
+        if (pf->size == size) {
+            p = pf->page;
+            if (pf->next)
+                    pf->next->prev = pf->prev;
+            pf->prev->next = pf->next;
+            delay_free = pf;
+            break;
+        } 
+
+        p = pf->page;
+        pf->page = (char *)pf->page + size;
+        pf->size -= size;
+        break;
+    }
+
+#ifdef MALLOC_EXTRA_SANITY
+    if (p && page_dir[ptr2index(p)] != MALLOC_FREE)
+        wrterror("(ES): allocated non-free page on free-list\n");
+#endif /* MALLOC_EXTRA_SANITY */
+
+    size >>= malloc_pageshift;
+
+    /* Map new pages */
+    if (!p)
+        p = map_pages(size);
+
+    if (p) {
+
+        index = ptr2index(p);
+        page_dir[index] = MALLOC_FIRST;
+        for (i=1;i<size;i++)
+            page_dir[index+i] = MALLOC_FOLLOW;
+
+        if (malloc_junk)
+            memset(p, SOME_JUNK, size << malloc_pageshift);
+    }
+
+    if (delay_free) {
+        if (!px)
+            px = delay_free;
+        else
+            ifree(delay_free);
+    }
+
+    return p;
+}
+
+/*
+ * Allocate a page of fragments
+ */
+
+static __inline__ int
+malloc_make_chunks(bits)
+    int bits;
+{
+    struct  pginfo *bp;
+    void *pp;
+    int i, k, l;
+
+    /* Allocate a new bucket */
+    pp = malloc_pages((size_t)malloc_pagesize);
+    if (!pp)
+        return 0;
+
+    /* Find length of admin structure */
+    l = sizeof *bp - sizeof(u_long);
+    l += sizeof(u_long) *
+        (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
+
+    /* Don't waste more than two chunks on this */
+    if ((1UL<<(bits)) <= l+l) {
+        bp = (struct  pginfo *)pp;
+    } else {
+        bp = (struct  pginfo *)imalloc(l);
+        if (!bp) {
+            ifree(pp);
+            return 0;
+        }
+    }
+
+    bp->size = (1UL<<bits);
+    bp->shift = bits;
+    bp->total = bp->free = malloc_pagesize >> bits;
+    bp->page = pp;
+
+    /* set all valid bits in the bitmap */
+    k = bp->total;
+    i = 0;
+
+    /* Do a bunch at a time */
+    for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
+        bp->bits[i / MALLOC_BITS] = ~0UL;
+
+    for(; i < k; i++)
+        bp->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
+
+    if (bp == bp->page) {
+        /* Mark the ones we stole for ourselves */
+        for(i=0;l > 0;i++) {
+            bp->bits[i/MALLOC_BITS] &= ~(1UL<<(i%MALLOC_BITS));
+            bp->free--;
+            bp->total--;
+            l -= (1 << bits);
+        }
+    }
+
+    /* MALLOC_LOCK */
+
+    page_dir[ptr2index(pp)] = bp;
+
+    bp->next = page_dir[bits];
+    page_dir[bits] = bp;
+
+    /* MALLOC_UNLOCK */
+
+    return 1;
+}
+
+/*
+ * Allocate a fragment
+ */
+static void *
+malloc_bytes(size)
+    size_t size;
+{
+    int i,j;
+    u_long u;
+    struct  pginfo *bp;
+    int k;
+    u_long *lp;
+
+    /* Don't bother with anything less than this */
+    if (size < malloc_minsize)
+        size = malloc_minsize;
+
+    /* Find the right bucket */
+    j = 1;
+    i = size-1;
+    while (i >>= 1)
+        j++;
+
+    /* If it's empty, make a page more of that size chunks */
+    if (!page_dir[j] && !malloc_make_chunks(j))
+        return 0;
+
+    bp = page_dir[j];
+
+    /* Find first word of bitmap which isn't empty */
+    for (lp = bp->bits; !*lp; lp++)
+        ;
+
+    /* Find that bit, and tweak it */
+    u = 1;
+    k = 0;
+    while (!(*lp & u)) {
+        u += u;
+        k++;
+    }
+    *lp ^= u;
+
+    /* If there are no more free, remove from free-list */
+    if (!--bp->free) {
+        page_dir[j] = bp->next;
+        bp->next = 0;
+    }
+
+    /* Adjust to the real offset of that chunk */
+    k += (lp-bp->bits)*MALLOC_BITS;
+    k <<= bp->shift;
+
+    if (malloc_junk)
+        memset((char *)bp->page + k, SOME_JUNK, bp->size);
+
+    return (u_char *)bp->page + k;
+}
+
+/*
+ * Allocate a piece of memory
+ */
+static void *
+imalloc(size)
+    size_t size;
+{
+    void *result;
+
+    if (!malloc_started)
+        malloc_init();
+
+    if (suicide)
+        abort();
+
+    if ((size + malloc_pagesize) < size)       /* Check for overflow */
+        result = 0;
+    else if (size <= malloc_maxsize)
+        result =  malloc_bytes(size);
+    else
+        result =  malloc_pages(size);
+
+    if (malloc_abort && !result)
+        wrterror("allocation failed.\n");
+
+    if (malloc_zero && result)
+        memset(result, 0, size);
+
+    return result;
+}
+
+/*
+ * Change the size of an allocation.
+ */
+static void *
+irealloc(ptr, size)
+    void *ptr;
+    size_t size;
+{
+    void *p;
+    u_long osize, index;
+    struct pginfo **mp;
+    int i;
+
+    if (suicide)
+        abort();
+
+    if (!malloc_started) {
+        wrtwarning("malloc() has never been called.\n");
+        return 0;
+    }
+
+    index = ptr2index(ptr);
+
+    if (index < malloc_pageshift) {
+        wrtwarning("junk pointer, too low to make sense.\n");
+        return 0;
+    }
+
+    if (index > last_index) {
+        wrtwarning("junk pointer, too high to make sense.\n");
+        return 0;
+    }
+
+    mp = &page_dir[index];
+
+    if (*mp == MALLOC_FIRST) {                  /* Page allocation */
+
+        /* Check the pointer */
+        if ((u_long)ptr & malloc_pagemask) {
+            wrtwarning("modified (page-) pointer.\n");
+            return 0;
+        }
+
+        /* Find the size in bytes */
+        for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;)
+            osize += malloc_pagesize;
+
+        if (!malloc_realloc &&                  /* unless we have to, */
+          size <= osize &&                      /* .. or are too small, */
+          size > (osize - malloc_pagesize)) {   /* .. or can free a page, */
+            return ptr;                         /* don't do anything. */
+        }
+
+    } else if (*mp >= MALLOC_MAGIC) {           /* Chunk allocation */
+
+        /* Check the pointer for sane values */
+        if (((u_long)ptr & ((*mp)->size-1))) {
+            wrtwarning("modified (chunk-) pointer.\n");
+            return 0;
+        }
+
+        /* Find the chunk index in the page */
+        i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
+
+        /* Verify that it isn't a free chunk already */
+        if ((*mp)->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
+            wrtwarning("chunk is already free.\n");
+            return 0;
+        }
+
+        osize = (*mp)->size;
+
+        if (!malloc_realloc &&          /* Unless we have to, */
+          size < osize &&               /* ..or are too small, */
+          (size > osize/2 ||            /* ..or could use a smaller size, */
+          osize == malloc_minsize)) {   /* ..(if there is one) */
+            return ptr;                 /* ..Don't do anything */
+        }
+
+    } else {
+        wrtwarning("pointer to wrong page.\n");
+        return 0;
+    }
+
+    p = imalloc(size);
+
+    if (p) {
+        /* copy the lesser of the two sizes, and free the old one */
+        if (osize < size)
+            memcpy(p, ptr, osize);
+        else
+            memcpy(p, ptr, size);
+        ifree(ptr);
+    } 
+    return p;
+}
+
+/*
+ * Free a sequence of pages
+ */
+
+static __inline__ void
+free_pages(ptr, index, info)
+    void *ptr;
+    int index;
+    struct pginfo *info;
+{
+    int i;
+    struct pgfree *pf, *pt=0;
+    u_long l;
+    void *tail;
+
+    if (info == MALLOC_FREE) {
+        wrtwarning("page is already free.\n");
+        return;
+    }
+
+    if (info != MALLOC_FIRST) {
+        wrtwarning("pointer to wrong page.\n");
+        return;
+    }
+
+    if ((u_long)ptr & malloc_pagemask) {
+        wrtwarning("modified (page-) pointer.\n");
+        return;
+    }
+
+    /* Count how many pages and mark them free at the same time */
+    page_dir[index] = MALLOC_FREE;
+    for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
+        page_dir[index + i] = MALLOC_FREE;
+
+    l = i << malloc_pageshift;
+
+    if (malloc_junk)
+        memset(ptr, SOME_JUNK, l);
+
+#ifdef __FreeBSD__
+    if (malloc_hint)
+        madvise(ptr, l, MADV_FREE);
+#endif
+
+    tail = (char *)ptr+l;
+
+    /* add to free-list */
+    if (!px)
+        px = imalloc(sizeof *px);       /* This cannot fail... */
+    px->page = ptr;
+    px->end =  tail;
+    px->size = l;
+    if (!free_list.next) {
+
+        /* Nothing on free list, put this at head */
+        px->next = free_list.next;
+        px->prev = &free_list;
+        free_list.next = px;
+        pf = px;
+        px = 0;
+
+    } else {
+
+        /* Find the right spot, leave pf pointing to the modified entry. */
+        tail = (char *)ptr+l;
+
+        for(pf = free_list.next; pf->end < ptr && pf->next; pf = pf->next)
+            ; /* Race ahead here */
+
+        if (pf->page > tail) {
+            /* Insert before entry */
+            px->next = pf;
+            px->prev = pf->prev;
+            pf->prev = px;
+            px->prev->next = px;
+            pf = px;
+            px = 0;
+        } else if (pf->end == ptr ) {
+            /* Append to the previous entry */
+            pf->end = (char *)pf->end + l;
+            pf->size += l;
+            if (pf->next && pf->end == pf->next->page ) {
+                /* And collapse the next too. */
+                pt = pf->next;
+                pf->end = pt->end;
+                pf->size += pt->size;
+                pf->next = pt->next;
+                if (pf->next)
+                    pf->next->prev = pf;
+            }
+        } else if (pf->page == tail) {
+            /* Prepend to entry */
+            pf->size += l;
+            pf->page = ptr;
+        } else if (!pf->next) {
+            /* Append at tail of chain */
+            px->next = 0;
+            px->prev = pf;
+            pf->next = px;
+            pf = px;
+            px = 0;
+        } else {
+            wrterror("freelist is destroyed.\n");
+        }
+    }
+    
+    /* Return something to OS ? */
+    if (!pf->next &&                            /* If we're the last one, */
+      pf->size > malloc_cache &&                /* ..and the cache is full, */
+      pf->end == malloc_brk &&                  /* ..and none behind us, */
+      malloc_brk == sbrk(0)) {                  /* ..and it's OK to do... */
+
+        /*
+         * Keep the cache intact.  Notice that the '>' above guarantees that
+         * the pf will always have at least one page afterwards.
+         */
+        pf->end = (char *)pf->page + malloc_cache;
+        pf->size = malloc_cache;
+
+        brk(pf->end);
+        malloc_brk = pf->end;
+
+        index = ptr2index(pf->end);
+        last_index = index - 1;
+
+        for(i=index;i <= last_index;)
+            page_dir[i++] = MALLOC_NOT_MINE;
+
+        /* XXX: We could realloc/shrink the pagedir here I guess. */
+    }
+    if (pt)
+        ifree(pt);
+}
+
+/*
+ * Free a chunk, and possibly the page it's on, if the page becomes empty.
+ */
+
+/* ARGSUSED */
+static __inline__ void
+free_bytes(ptr, index, info)
+    void *ptr;
+    int index;
+    struct pginfo *info;
+{
+    int i;
+    struct pginfo **mp;
+    void *vp;
+
+    /* Find the chunk number on the page */
+    i = ((u_long)ptr & malloc_pagemask) >> info->shift;
+
+    if (((u_long)ptr & (info->size-1))) {
+        wrtwarning("modified (chunk-) pointer.\n");
+        return;
+    }
+
+    if (info->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
+        wrtwarning("chunk is already free.\n");
+        return;
+    }
+
+    if (malloc_junk)
+        memset(ptr, SOME_JUNK, info->size);
+
+    info->bits[i/MALLOC_BITS] |= 1UL<<(i%MALLOC_BITS);
+    info->free++;
+
+    mp = page_dir + info->shift;
+
+    if (info->free == 1) {
+
+        /* Page became non-full */
+
+        mp = page_dir + info->shift;
+        /* Insert in address order */
+        while (*mp && (*mp)->next && (*mp)->next->page < info->page)
+            mp = &(*mp)->next;
+        info->next = *mp;
+        *mp = info;
+        return;
+    }
+
+    if (info->free != info->total)
+        return;
+
+    /* Find & remove this page in the queue */
+    while (*mp != info) {
+        mp = &((*mp)->next);
+#ifdef MALLOC_EXTRA_SANITY
+        if (!*mp)
+                wrterror("(ES): Not on queue\n");
+#endif /* MALLOC_EXTRA_SANITY */
+    }
+    *mp = info->next;
+
+    /* Free the page & the info structure if need be */
+    page_dir[ptr2index(info->page)] = MALLOC_FIRST;
+    vp = info->page;            /* Order is important ! */
+    if(vp != (void*)info) 
+        ifree(info);
+    ifree(vp);
+}
+
+static void
+ifree(ptr)
+    void *ptr;
+{
+    struct pginfo *info;
+    int index;
+
+    /* This is legal */
+    if (!ptr)
+        return;
+
+    if (!malloc_started) {
+        wrtwarning("malloc() has never been called.\n");
+        return;
+    }
+
+    /* If we're already sinking, don't make matters any worse. */
+    if (suicide)
+        return;
+
+    index = ptr2index(ptr);
+
+    if (index < malloc_pageshift) {
+        wrtwarning("junk pointer, too low to make sense.\n");
+        return;
+    }
+
+    if (index > last_index) {
+        wrtwarning("junk pointer, too high to make sense.\n");
+        return;
+    }
+
+    info = page_dir[index];
+
+    if (info < MALLOC_MAGIC)
+        free_pages(ptr, index, info);
+    else
+        free_bytes(ptr, index, info);
+    return;
+}
+
+/*
+ * These are the public exported interface routines.
+ */
+
+static int malloc_active;
+
+void *
+malloc(size_t size)
+{
+    register void *r;
+
+    malloc_func = " in malloc():";
+    THREAD_LOCK();
+    if (malloc_active++) {
+        wrtwarning("recursive call.\n");
+        malloc_active--;
+        return (0);
+    }
+    r = imalloc(size);
+    UTRACE(0, size, r);
+    malloc_active--;
+    THREAD_UNLOCK();
+    if (malloc_xmalloc && !r)
+        wrterror("out of memory.\n");
+    return (r);
+}
+
+void
+free(void *ptr)
+{
+    malloc_func = " in free():";
+    THREAD_LOCK();
+    if (malloc_active++) {
+        wrtwarning("recursive call.\n");
+        malloc_active--;
+        return;
+    }
+    ifree(ptr);
+    UTRACE(ptr, 0, 0);
+    malloc_active--;
+    THREAD_UNLOCK();
+    return;
+}
+
+void *
+realloc(void *ptr, size_t size)
+{
+    register void *r;
+
+    malloc_func = " in realloc():";
+    THREAD_LOCK();
+    if (malloc_active++) {
+        wrtwarning("recursive call.\n");
+        malloc_active--;
+        return (0);
+    }
+    if (!ptr) {
+        r = imalloc(size);
+    } else {
+        r = irealloc(ptr, size);
+    }
+    UTRACE(ptr, size, r);
+    malloc_active--;
+    THREAD_UNLOCK();
+    if (malloc_xmalloc && !r)
+        wrterror("out of memory.\n");
+    return (r);
+}