bibopmalloc.c

/*
**
** This is a special purpose malloc for lpmud.
** It is geared towards the special needs of the game driver:
**   - most allocations (>98%) are of small objects (<100 byte)
**   - very few allocations (< 0.03%) are large (>64k)
**
** This has lead to a malloc using three different strategies:
** small, medium, and large.
** All allocation is based on pages (typical page size is 32K).
** Pages are allocated on pages boundaries.  This makes it possible
** to store information about a page and its objects just at the
** beginning of a page.  Given a pointer in the middle of a page
** the address is just masked to page boundary and the page information
** is available there.
**
** Small objects:
** Objects with a size smaller than a threshold will
** be allocated in BIBOP (big bag of pages) style.
** A page consists of some information about the page in the
** beginning followed by a bitmap indicating the usage
** of objects and an array of objects.  Within a page
** all objects have the same size.
** To get to the information given a pointer to an
** object you mask off the lower part of the address.
** This method gives a very small space overhead (<2 bits) per object.
**
** Medium objects:
** Medium sized objects are allocated within a page.
** All the pages are linked, and the objects are linked
** within a page.  All free space is linked into doubly
** linked lists.  There are a number of list headers for different
** sizes of the free object.  The allocation uses best fit
** among the headers, and first fit in the doubly linked list.
** Free objects are coalesced when being freed.
**
** Large objects:
** Large objects are given several consecutive pages.
** Large requests are always rounded to a multiple of
** pages.
**
** Free pages (from freeing large or medium requests) are kept
** on a free list where best fit is used to do allocation.
**
** The current tuning of the allocation parameters seems to indicate
** that the space overhead is around 15%.
*/

/* #define BIBOP_DEBUG */
/* #define FREESTAT */
/* #define PARANOIA */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <unistd.h>
#include <string.h>
#include "config.h"
#include <math.h>

#include "lint.h"
#ifdef DEBUG
#include "mstring.h"
#include "simulate.h"
#endif

#define SMALL_SIZE 0x80         /* smaller than this is uses bibop */
#define PAGE_SIZE 0x20000       /* 128k pages MUST!! be a power of 2 */
#define SIZE_SLOP 0x80          /* don't split a free space if leftover is less than this */
#define NFREE 20                /* number of headers for medium blocks */

typedef double aligntype;
#define ALIGNMENT (sizeof(aligntype)) /* alignment requirement for this platform */
typedef unsigned long mapword;  /* should be the largest possible unsigned type */

#define BITS_PER_BYTE 8         /* bits per unit in sizeof */

#define CEIL(x) (((x)+ALIGNMENT-1) & ~(ALIGNMENT-1))
#define PAGEMASK (~(PAGE_SIZE-1))

#define PTR_SIZE (sizeof(void *))

#define BITS_PER_MAPWORD (sizeof(mapword) * BITS_PER_BYTE)

struct bibop {
    int objsize;                /* Size of the objects (rounded) */
    int objfree;                /* Number of free objects */
    int maxobjfree;             /* Maximum objects that fit on the page */
    mapword *freemap;           /* Bitmap for free objects */
    int nextfree;               /* (Cached) index to look for free object */
    int maxfree;                /* Max index into freemap */
    void *objs;                 /* Pointer to first object */
};
#define BIBOPMAGIC 0x55AA5A01
static long long p_bibop, m_bibop, f_bibop;
static long long s_bibop;

struct medium {
    aligntype data;
};
#define ALLOCMAGIC 0x55AA5A02
static long long p_alloc, m_alloc, f_alloc;
static long long s_alloc;
#define OBJSIZE(cur) ((char *)cur->next - (char *)OBJ_TO_DATA(cur))

struct freeblk {
    struct freeblk *fwd, *bwd;
#ifdef FREESTAT
    struct freehead *head;
#endif
};
struct freehead {
    struct freeblk h;
    int maxsize;
    int nalloc, nreal, nsplit, nfree, njoin, njoin1, njoin2, ndrop, nwhy, nskip;
};
static struct freehead freehead[NFREE];
#define FDEL(p) { (p)->bwd->fwd = (p)->fwd; (p)->fwd->bwd = (p)->bwd; }
#define FINS(p, q) { (p)->fwd = (q)->fwd; (q)->fwd = (p); (p)->bwd = (q); (p)->fwd->bwd = (p); }

struct big {
    int npages;
    aligntype data;
};
#define BIGMAGIC 0x55AA5A03
static long long p_big, m_big, f_big;
static long long s_big;

struct descr {
    int magic;                  /* magic number for different page types */
    struct descr *dnext;        /* next page in whatever list it happens to be in */
    union {
        struct bibop bibop;
        struct medium medium;
        struct big big;
    } u;
};


static struct descr *bibops[(SMALL_SIZE+ALIGNMENT-1)/ALIGNMENT]; /* start of bibop chains */

static struct descr *newbibop(unsigned int);

static struct descr *firstpage;

typedef uintptr_t PTR;  /* same size as a pointer */

static struct descr *freepage = 0;
static long long p_free;

struct block {
#ifdef BIBOP_DEBUG
    int bmagic;
#endif
    int busy;
    struct block *next;
    union {
        aligntype data;
        struct freeblk fb;
    } u;
};
#define DATA_TO_OBJ(p) ((struct block *)( (char *)p - (long)&((struct block *)0)->u.data ))
#define OBJ_TO_DATA(p) ((void *)&p->u.data)
#define BMAGIC 0x19930921

static char *nextpage, *firstsbrk;

static int initdone = 0;

char *dump_malloc_data(void);
static void bibop_init(void);

#define OFFSET(t,f) ((long) &(((t *)0)->f))

/* Insert pages on free list, coalescing pages if possible */
static void
insertfreepage(struct descr *p)
{
    struct descr **fp;

#ifdef BIBOP_DEBUG
    (void)fprintf(stderr, "freeing %d pages at %lx", p->u.big.npages, p);
#endif
    /* find position */
    for(fp = &freepage; *fp && p > *fp; fp = &(*fp)->dnext)
        ;
    /* insert into chain */
    p->dnext = *fp;
    *fp = p;
    /* check for adjecent following page */
    if ((char *)p->dnext == (char *)p + p->u.big.npages * PAGE_SIZE) {
        p->u.big.npages += p->dnext->u.big.npages;
        p->dnext = p->dnext->dnext;
#ifdef BIBOP_DEBUG
    (void)fprintf(stderr, ", join with next block");
#endif
    }
    /* check for adjecent preceding page */
    if (fp != &freepage) {
        struct descr *q;
        q = (struct descr *)((char *)fp - OFFSET(struct descr, dnext));
        if ((char *)q->dnext == (char *)q + q->u.big.npages * PAGE_SIZE) {
            q->u.big.npages += q->dnext->u.big.npages;
            q->dnext = q->dnext->dnext;
#ifdef BIBOP_DEBUG
    (void)fprintf(stderr, ", join with previous block");
#endif
        }
    }
#ifdef BIBOP_DEBUG
    {
        struct descr *f;
        (void)fprintf(stderr, "\nfree page list (nextpage=%lx):\n", nextpage);
        for(f = freepage; f; f = f->dnext) {
            (void)fprintf(stderr, "    %lx (%lx) %d\n", f, (char *)f + f->u.big.npages * PAGE_SIZE, f->u.big.npages);
        }
    }
#endif
}

/* Allocate n pages. */
static void *
pages(unsigned int n)
{
    void *r;

#ifdef BIBOP_DEBUG
    (void)fprintf(stderr, "allocating %d pages", n);
#endif

    if (freepage) {
        /* try to find something on the free list */
        /* use best fit, slower but better */
        struct descr **p, **last = 0, **best = 0, *b;
        for(p = &freepage; *p; last = p, p = &(*p)->dnext) {
            if ((*p)->u.big.npages == n) {
                best = p;
                break;
            } else if ((*p)->u.big.npages > n) {
                if (!best || (*p)->u.big.npages < (*best)->u.big.npages)
                    best = p;
            }
        }
        if (!best) {
            /* couldn't find anything, try extending last block */
            if ((char *)(*last) + (*last)->u.big.npages * PAGE_SIZE == nextpage) {
                int k = n - (*last)->u.big.npages;
                r = sbrk(k*PAGE_SIZE);
                if (!r || (intptr_t)r == -1) {
                    (void)fprintf(stderr, "sbrk(%ld) failed %ld(0x%lx) with return value %p\n", 
                            (long) k*PAGE_SIZE, (long)(nextpage - firstsbrk),
                            (unsigned long)(nextpage - firstsbrk), r);
                    return 0;
                }
                nextpage += k*PAGE_SIZE;
                (*last)->u.big.npages += k;
                best = last;
                p_free += k;
#ifdef BIBOP_DEBUG
                (void)fprintf(stderr, ", extending %d", k);
#endif
            } else
                goto notfound;
        }
#ifdef BIBOP_DEBUG
        (void)fprintf(stderr, ", from free list");
#endif
        /* best points at something usable */
        b = *best;
        r = b;
        if (b->u.big.npages > n) {
            /* split the block */
            *best = (struct descr *)((char *)b + n * PAGE_SIZE);
            (*best)->magic = b->magic;
            (*best)->u.big.npages = b->u.big.npages - n;
            (*best)->dnext = b->dnext;
#ifdef BIBOP_DEBUG
        (void)fprintf(stderr, ", split it %d %d", b->u.big.npages, n);
#endif
        } else {
            *best = b->dnext;   /* remove block */
        }
        p_free -= n;
#ifdef BIBOP_DEBUG
    {
        struct descr *f;
        (void)fprintf(stderr, "\nfree page list (nextpage=%lx):\n", nextpage);
        for(f = freepage; f; f = f->dnext) {
            (void)fprintf(stderr, "    %lx (%lx) %d\n", f, (char *)f + f->u.big.npages * PAGE_SIZE, f->u.big.npages);
        }
    }
#endif
        return r;
    }

 notfound:
#ifdef BIBOP_DEBUG
    (void)fprintf(stderr, " fresh\n");
#endif
    r = sbrk(n*PAGE_SIZE);
    if (!r || (intptr_t)r == -1)
    {
        (void)fprintf(stderr, "sbrk failed %ld with return value %p\n", (long)(nextpage - firstsbrk), r);
        return 0;
    }
    if (!(nextpage - PAGE_SIZE <= (char *)r && (char *)r <= nextpage + PAGE_SIZE))
    {
        (void)fprintf(stderr, "bad sbrk %p %p\n", r,
                nextpage);
    }
    r = nextpage;
    nextpage += n*PAGE_SIZE;
    return r;
}

/* Insert a (medium) block into the appropriate free list */
static void
insfree(struct block *b, int how)
{
    int s = OBJSIZE(b);
    int i;

    for(i = 0; i < NFREE && freehead[i].maxsize <= s; i++)
        ;
#ifdef PARANOIA
    if (i == NFREE) {
        (void)fprintf(stderr, "insfree %d\n", s);
        abort();
    }
#endif
    FINS(&b->u.fb, &freehead[i].h);
#ifdef FREESTAT
    if (how == 1) freehead[i].nsplit++;
    if (how == 2) freehead[i].nfree++;
    if (how == 3) freehead[i].njoin++;
    b->u.fb.head = &freehead[i];
#elif defined(lint)
    how--;
#endif
}

/* Initialize a new medium page */
static void
init_allocpage(struct descr *p)
{
    struct block *first, *last;

    p->magic = ALLOCMAGIC;
    p->dnext = 0;
    first = (struct block *)&p->u.medium.data;
    last = (struct block *)((char *)p + PAGE_SIZE - sizeof(struct block));
#ifdef BIBOP_DEBUG
    first->bmagic = BMAGIC;
    last->bmagic = BMAGIC;
#endif    
    first->busy = 0;
    first->next = last;
    last->busy = 0;
    last->next = 0;
    insfree(first, 0);
}

/* Do a non-small allocation */
static void *
bigmalloc(unsigned int size)
{
    struct descr *p;
    struct block *cur, *next;
    int cursize, i;

    if (size > PAGE_SIZE - sizeof(struct descr) - ALIGNMENT - PTR_SIZE) {
        /* really big! */
        unsigned int n = (size + sizeof(struct descr) + PAGE_SIZE - 1) / PAGE_SIZE;
        struct descr *bigp = pages(n);
        if (!bigp)
            return 0;
        p_big += n;
        bigp->magic = BIGMAGIC;
        bigp->u.big.npages = n;
        m_big++;
        s_big += size;
        return (void *)&bigp->u.big.data;
    }
        
    /* find first block which is big enough */
    for(i = 0; i < NFREE; i++) {
        if (freehead[i].maxsize > size) {
            struct freeblk *fp;
            for(fp = freehead[i].h.fwd; fp != &freehead[i].h; fp = fp->fwd) {
                cur = DATA_TO_OBJ(fp);
                cursize = OBJSIZE(cur);
                if (cursize >= size) {
                    p = (struct descr *)((PTR)cur & PAGEMASK);
                    goto found;
                }
            }
            freehead[i].nskip++;
        }
    }

    /* No page had a block that was big enough, get a new one. */
    p = pages(1);
    if (!p)
        return 0;
    p_alloc++;
    init_allocpage(p);
    p->dnext = firstpage;
    firstpage = p;
    cur = (struct block *)&p->u.medium.data;
    cursize = OBJSIZE(cur);
 found:
#ifdef BIBOP_DEBUG
    if (cur->bmagic != BMAGIC) {
        (void)fprintf(stderr, "bad magic 2\n");
        abort();
    }
#endif
    FDEL(&cur->u.fb);                   /* remove from free lists */
#ifdef FREESTAT
    cur->u.fb.head->nalloc++;
    {
        int i;
        for(i = 0; i < NFREE && freehead[i].maxsize < size; i++)
            ;
#ifdef PARANOIA
        if (i == NFREE)
            abort();
#endif
        freehead[i].nreal++;
        if (cur == (struct block *)&p->u.medium.data && cur->next->next == 0)
            freehead[i].nwhy++;
    }
#endif
    if (size + SIZE_SLOP < cursize) {
        /* we have to split the current block */
        next = (struct block *)((char *)cur + size + sizeof(struct block));
#ifdef BIBOP_DEBUG
        next->bmagic = BMAGIC;
#endif
        next->busy = 0;
#ifdef PARANOIA
        if ((struct descr *)((PTR)cur->next & PAGEMASK) != p) 
            abort();
#endif
        next->next = cur->next;
        cur->next = next;
#ifdef PARANOIA
        if ((struct descr *)((PTR)cur->next & PAGEMASK) != p) 
            abort();
#endif
        insfree(next, 1);               /* insert second half */
    }
    cur->busy = 1;
    m_alloc++;
    s_alloc += size;
    return (void *)&cur->u.data;
}

/* Table of the bit number of the last bit set in a byte. */
static int flsb[] = {
-1,0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
};

#ifdef DEBUG
static void
missaligned_free(void *ptr, void *should_be)
{
    if (mstring_magic(should_be + mstring_header) == MSTRING_MAGIC)
        fatal("freeing m-magic string: %s\n", (char *)should_be + mstring_header);
    if (sstring_magic(should_be + sstring_header) == SSTRING_MAGIC)
        fatal("freeing s-magic string: %s\n", (char *)should_be + sstring_header);
    fatal("Freeing different pointer than malloced is %p should be %p.\n", ptr, should_be);
    
}
#endif

/* External interface */
void *
malloc(size_t size)
{
    register struct descr *bp;
    register int i, j;
    register mapword m;

    size = CEIL(size);
    if (!initdone)
        bibop_init();
    if (size >= SMALL_SIZE)
        return bigmalloc(size);
    for(bp = bibops[size/ALIGNMENT - 1]; bp && bp->u.bibop.objfree == 0; bp = bp->dnext)
        ;
    if (!bp) {
        /* Add a new page */
        bp = newbibop(size);
        if (!bp)
            return 0;
        bp->dnext = bibops[size/ALIGNMENT - 1];
        bibops[size/ALIGNMENT - 1] = bp;
    }
    /* locate word with free block */
    for(i = bp->u.bibop.nextfree; ;) {
        m = bp->u.bibop.freemap[i];
        if (m)
            break;
        if (++i >= bp->u.bibop.maxfree)
            i = 0;
#ifdef PARANOIA
        if (i == bp->u.bibop.nextfree) {
            /* Help!  We've wrapped around without finding the promised free block! */
            (void)fprintf(stderr, "bmalloc wrapped around, size = %ld\n", (long)size);
            abort();
        }
#endif
    }
    bp->u.bibop.nextfree = i;
    /* locate bit within the word */
#define ONES (~(mapword)0)
    j = 0;
    if ((m & (ONES >> (BITS_PER_MAPWORD/2))) == 0) 
        j += BITS_PER_MAPWORD/2, m >>= BITS_PER_MAPWORD/2; 
    else 
        m &= (ONES >> (BITS_PER_MAPWORD/2));
    if ((m & (ONES >> (3*BITS_PER_MAPWORD/4))) == 0) 
        j += BITS_PER_MAPWORD/4, m >>= BITS_PER_MAPWORD/4; 
    else 
        m &= (ONES >> (3*BITS_PER_MAPWORD/4));
    if ((m & (ONES >> (7*BITS_PER_MAPWORD/8))) == 0) 
        j += BITS_PER_MAPWORD/8, m >>= BITS_PER_MAPWORD/8; 
    else 
        m &= (ONES >> (7*BITS_PER_MAPWORD/8));
    /* We're down to at most 8 bits now (if there are <= 64 bits in a word).
       Use a table to look up the last bit set.
    */
    j += flsb[(int)m];
    bp->u.bibop.freemap[i] &= ~ ((mapword)1<<j);        /* mark as allocated */
    bp->u.bibop.objfree--;              /* one less free */
    m_bibop++;
    s_bibop += size;
    return (void *) ((char *)bp->u.bibop.objs + (i * BITS_PER_MAPWORD + j) * size);
}

/* External interface */
void *
calloc(size_t nmemb, size_t size)
{
    void *p;

    p = malloc(nmemb * size);
    if (p != NULL)
        memset(p, '\0', nmemb * size);
    return p;
}

/* External interface */
void
free(void *ptr)
{
    register struct descr *bp;
    register unsigned int offs;
    int i, j;

    if (!ptr)
        return;

    if (!initdone)
        return;
    bp = (struct descr *)((PTR)ptr & PAGEMASK);
    if (bp->magic == BIGMAGIC) {
        /* freeing really big block, stuff all pages on free list */
        int n = bp->u.big.npages;
#ifdef DEBUG
        if (ptr != &bp->u.big.data)
            missaligned_free(ptr, &bp->u.big.data);
#endif

        insertfreepage(bp);
        f_big++;
        p_big -= n;
        p_free += n;
    } else if (bp->magic == ALLOCMAGIC) {
        /* freeing part of a page */
        struct block *this, *cur, *next;

        this = DATA_TO_OBJ(ptr);
#ifdef DEBUG
        if (ptr != &this->u.data)
            missaligned_free(ptr, &this->u.data);
#endif
            
#ifdef BIBOP_DEBUG
        if (DATA_TO_OBJ(ptr)->bmagic != BMAGIC) {
            (void)fprintf(stderr, "bad magic 3\n");
            abort();
        }
#endif
#ifdef PARANOIA
        if (!this->busy)
            abort();
#endif
        this->busy = 0;
        insfree(this, 2);
        /* coalescing is tedious since we don't have back pointers */
        for(cur = (struct block *)&bp->u.medium.data; cur->next; cur = cur->next)
            if (cur == this || (cur->next == this && !cur->busy))
                break;
#ifdef PARANOIA
        if (!cur->next || cur->busy)
            abort();
#endif
        /* coalesce free blocks (max 3) */
        for(;;) {
            next = cur->next;
#ifdef BIBOP_DEBUG
            if (next->bmagic != BMAGIC) {
                (void)fprintf(stderr, "bad magic 1\n");
                abort();
            }
#endif
            if (!next->next || next->busy)
                break;
            cur->next = next->next;
#ifdef BIBOP_DEBUG
            next->bmagic = 0;
#endif
#ifdef PARANOIA
            if ((struct descr *)((PTR)cur->next & PAGEMASK) != bp)
                abort();
#endif
#ifdef FREESTAT
            cur->u.fb.head->njoin1++;
            next->u.fb.head->njoin2++;
#endif
            FDEL(&cur->u.fb);
            FDEL(&next->u.fb);
            insfree(cur, 3);
        }

        if (((struct block *)&bp->u.medium.data)->next->next == 0) {
            /* The whole page is free now, move it to free list */
            struct descr **p;
            struct block *blk = (struct block *)&bp->u.medium.data;
            FDEL(&blk->u.fb);
#ifdef FREESTAT
            blk->u.fb.head->ndrop++;
#endif
            for(p = &firstpage; *p != bp; p = &(*p)->dnext)
                ;
            *p = (*p)->dnext;
            bp->u.big.npages = 1;
            insertfreepage(bp);
            p_free++;
            p_alloc--;
        }
        f_alloc++;
    } else if (bp->magic == BIBOPMAGIC) {
        offs = ((char *)ptr - (char *)bp->u.bibop.objs) / bp->u.bibop.objsize; /* block offset from first block */
        i = offs / BITS_PER_MAPWORD;
        j = offs % BITS_PER_MAPWORD;
#ifdef DEBUG
        if (ptr != (char *)bp->u.bibop.objs + (offs * bp->u.bibop.objsize))
            missaligned_free(ptr, (char *)bp->u.bibop.objs + (offs * bp->u.bibop.objsize));
#endif
#ifdef PARANOIA
        if (bp->u.bibop.freemap[i] & (mapword)1<<j)
            abort();
#endif
        bp->u.bibop.freemap[i] |= (mapword)1<<j;        /* mark as free */
        bp->u.bibop.nextfree = i;       /* we have a free block here */
        bp->u.bibop.objfree++;          /* one more free */
        f_bibop++;
    } else {
        /* Happens when freeing prematurely allocated objects. */
        (void)fprintf(stderr, "Warning, bad magic number in free %x (%p)\n",
                bp->magic, ptr);
    }
}

/* External interface */
void
cfree(void *ptr)
{
    free(ptr);
}

/* External interface */
void *
realloc(void *old, size_t size)
{
    struct descr *bp;
    size_t osize;
    void *new;
    
    if (!old)
        return malloc(size);
    bp = (struct descr *)((PTR)old & PAGEMASK);
    switch (bp->magic)
    {
    case BIGMAGIC:
        osize = bp->u.big.npages * PAGE_SIZE;
        break;
    case ALLOCMAGIC:
        osize = OBJSIZE(DATA_TO_OBJ(old));
        break;
    case BIBOPMAGIC:
        osize = bp->u.bibop.objsize;
        break;
    default:
        (void)fprintf(stderr, "Bad magic number in realloc %x\n", bp->magic);
        osize = 0;
        break;
    }
    if (osize > size)
        osize = size;
    else if (osize == size)
        return old;

    /* Always assume the worst and allocate&copy */
    new = malloc(size);
    if (!new)
        return 0;
    
    (void)memcpy(new, old, osize);

    free(old);
    return new;
}

/* Allocate and initialize a new bibop page. */
static struct descr *
newbibop(size)
unsigned int size;
{
    struct descr *bp;
    int nobj, nmap, nnmap;
    int i, j;

/*  (void)fprintf(stderr, "newbibop %d\n", size);*/
    bp = pages(1);
    if (!bp)
        return 0;
    p_bibop++;
    /* I'm to lazy to figure out the exact formula.  Iterate at runtime instead. */
    for(nmap = 0, nnmap = -1; nmap != nnmap;) {
        nobj = (PAGE_SIZE - sizeof(struct descr) - nmap * sizeof(mapword) - 2 * ALIGNMENT) / size;
        nnmap = nmap;
        nmap = (nobj + BITS_PER_MAPWORD - 1) / BITS_PER_MAPWORD;
    }
    bp->magic = BIBOPMAGIC;
    bp->u.bibop.objsize = size;
    bp->u.bibop.objfree = nobj;
    bp->u.bibop.maxobjfree = nobj;
    bp->u.bibop.freemap = (void *) ((char *)bp + CEIL(sizeof(struct descr)));
    bp->u.bibop.nextfree = 0;
    bp->u.bibop.maxfree = nmap;
    bp->u.bibop.objs = (void *) ((char *)bp->u.bibop.freemap + CEIL(nmap * sizeof(mapword)));
    bp->dnext = 0;

    /* fill the freemap */
    for(i = 0; i < nmap-1; i++)
        bp->u.bibop.freemap[i] = (mapword)~0;
    j = nobj % BITS_PER_MAPWORD; /* no of bits needed in last word, or 0 all are needed */
    if (j)
        bp->u.bibop.freemap[i] = ((mapword)~0) >> (BITS_PER_MAPWORD - j);
    else
        bp->u.bibop.freemap[i] = (mapword)~0;
    return bp;
}

/* External interface.  Should be called before first malloc. */
static void
bibop_init()
{
    int mins, maxs;
    double sfact, smult, s;
    int i;

    if (initdone)
        return;
    initdone++;
    /* set up nextpage to point to space at a page boundary */
    firstsbrk = nextpage = (char *)( ( (PTR)sbrk(PAGE_SIZE+1) & PAGEMASK) + PAGE_SIZE );

    mins = SMALL_SIZE;
    maxs = PAGE_SIZE;
    sfact = (double)maxs / mins;
    smult = exp(log(sfact) / NFREE);
    for(s = smult, i = 0; i < NFREE; i++, s *= smult) {
        freehead[i].h.fwd = &freehead[i].h;
        freehead[i].h.bwd = &freehead[i].h;
        freehead[i].maxsize = (int) (mins * s + 0.5);
        /*(void)fprintf(stderr, "bucket %d holds size <%d\n", i, freehead[i].maxsize);*/
#ifdef FREESTAT
        freehead[i].h.head = &freehead[i];
#endif
    }
}

/* External interface.  Show statistics. */
char *
dump_malloc_data()
{
    static char mbuf[3000];
    long long u_bibop, u_alloc, u_big, n_bibop, n_alloc, n_big, a_bibop, a_alloc, a_big;
    struct descr *p;
    int i, n;

    u_bibop = u_alloc = u_big = n_bibop = n_alloc = n_big = a_bibop = a_alloc = a_big = 0;
    for(i = 0; i < (SMALL_SIZE+ALIGNMENT-1)/ALIGNMENT; i++) {
        for(p = bibops[i]; p; p = p->dnext) {
            n = p->u.bibop.objfree * p->u.bibop.objsize;
            n_bibop += n;
            u_bibop += PAGE_SIZE - n;
            a_bibop += p->u.bibop.objfree;
        }
    }
    for(p = firstpage; p; p = p->dnext) {
        struct block *q;
        for(q = (struct block *)&p->u.medium.data; q->next; q = q->next) {
            if (q->busy)
                u_alloc += OBJSIZE(q);
            else
                n_alloc += OBJSIZE(q), a_alloc++;
        }
    }
    u_big = PAGE_SIZE * p_big;
    (void)sprintf(mbuf, "\
%-17s %13s %13s %13s %13s\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s (%lld in free pages)\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s (%lld free) = %lld bytes (page=%lld)\n\
\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s %13lld %13lld %13lld %13lld\n\
%-17s %13lld %13lld %13lld %13lld\n\
\n\
sbrk requests: %lld %lld (a) \n\
", 
            "",            "small", "medium", "large", "total",
            "used memory", u_bibop, u_alloc, u_big, u_bibop+u_alloc+u_big, 
            "free memory", n_bibop, n_alloc, n_big, n_bibop+n_alloc+n_big+p_free*PAGE_SIZE,
            " ", p_free*PAGE_SIZE, 
            "used blocks", m_bibop-f_bibop, m_alloc-f_alloc, m_big-f_big, m_bibop+m_alloc+m_big-(f_bibop+f_alloc+f_big),
            "free blocks", a_bibop, a_alloc, a_big, a_bibop + a_alloc + a_big,
            "allocated pages", p_bibop, p_alloc, p_big, p_bibop+p_alloc+p_big+p_free+1,
            " ", p_free, (p_bibop+p_alloc+p_big+p_free+1)*PAGE_SIZE, (long long)PAGE_SIZE,

            "# of malloc()", m_bibop, m_alloc, m_big, m_bibop+m_alloc+m_big,
            "# of free()", f_bibop, f_alloc, f_big, f_bibop+f_alloc+f_big,
            "total allocation", s_bibop, s_alloc, s_big, s_bibop+s_alloc+s_big,
            p_bibop+p_alloc+p_big+p_free+1, (p_bibop+p_alloc+p_big+p_free+1)*PAGE_SIZE);
#ifdef FREESTAT
    {
        char xxxxx[2000];
        int k, tf;
        (void)strcpy(xxxxx, "medium sizes:\n size unus  split   free   join  alloc join1 join2 drop  real why  skip\n");
        for(tf = 0, k = 0; k < NFREE; k++) {
            struct freeblk *p;
            int s;
            for(s = 0, p = freehead[k].h.fwd; p != &freehead[k].h; p = p->fwd, s++)
                ;
            (void)sprintf(xxxxx+strlen(xxxxx), "%5d %4d %6d %6d %6d %6d %5d %5d %4d %5d %3d %5d\n",
                    freehead[k].maxsize, s, 
                    freehead[k].nsplit, freehead[k].nfree, freehead[k].njoin,
                    freehead[k].nalloc, freehead[k].njoin1, freehead[k].njoin2, freehead[k].ndrop, 
                    freehead[k].nreal, freehead[k].nwhy, freehead[k].nskip);
            tf += s;
        }
        (void)sprintf(xxxxx+strlen(xxxxx), "tot=%d(%d)\n", tf, a_alloc);
        (void)strcat(mbuf, xxxxx);
    }
#endif
    return mbuf;
}