source: branches/ithildin-1.1/source/malloc.c @ 589

/*
 * malloc.c: optimised memory allocation routines
 * 
 * Copyright 2003 the Ithildin Project.
 * See the COPYING file for more information on licensing and use.
 * 
 * this is an evolved version of my previous 'blockheap' allocator.  this is
 * intended to replace malloc in all calls and makes (hopefully) intelligent
 * decisions about how to allocate chunks of memory.  it is optimised for the
 * "thousands or more allocations of same-sized memory" case.
 */

#include <ithildin/stand.h>
#ifdef USE_INTERNAL_MALLOC

/* some options for the memory allocator.  tweaking these might be useful for
 * performance optimisation. */

/* the 'fuzziness' of allocated memory.  this is the factor by which memory
 * heaps are increased. */
#define MALLOC_FUZZ 16
/* the minimum memory size to allow allocations for.  setting it to MALLOC_FUZZ
 * is probably a fairly safe idea */
#define MALLOC_MIN_SIZE MALLOC_FUZZ
/* the maximum size (in terms of elements) to grab from the system.
 * allocation sizes begin small and ramp up to meet demand. */
#define MALLOC_MAX_ELEMS 1024
/* the maximum number of pages to get from the system.  this takes precedence
 * over MALLOC_MAX_ELEMS */
#define MALLOC_MAX_PAGES 64
/* the maximum size of allocation to handle.  allocations for memory larger
 * than this will always be one page or more because at this size it becomes
 * inefficient to try and wrangle these allocations into being any less
 * wasteful than that */
#define MALLOC_MAX_SIZE (MALLOC_PAGESIZE / 2)
/* number of blocks to 'cache' in the system.  if more blocks than this are
 * free the library will return the pages to the system. */
#define MALLOC_CACHE_BLOCKS 1
/* location of the configuration file we use. */
#define MALLOC_CONFIG_FILE "/etc/malloc.conf"

/* this structure contains the malloc options which are runtime tuneable.  the
 * runtime settings can be gotten from several places: a system file, an
 * environment variable, and a variable defined in the program.  this concept
 * was borrowed from Poul-Henning Kamp's malloc system, and in fact several of
 * the options in his allocator map to the options in this allocator. */
static struct {
    bool    wfatal;                /* warnings become fatal */
    bool    fill;                /* fill memory with 'fbyte' when allocated and
                                   freed. */
    char    fbyte;
    bool    force_realloc;        /* force a memory re-allocation even if the
                                   memory's current area is large enough to
                                   hold the new data without one */
    bool    sysv_compat;        /* 0-byte allocation returns NULL? */
    bool    nomem_fatal;        /* abort() if no memory is available. */
    int            page_cache;                /* number of pages to cache at the end of
                                   memory before returning memory to the
                                   system. */
    int            block_cache;        /* number of empty blocks to cache for each
                                   heap. <1 forces immediate return of these
                                   blocks to the system. */
    bool    sanity;                /* do extra sanity checking to better handle
                                   corrupted memory */
    bool    optimize;           /* optimize with "look-ahead" allocations */
} options;

static inline void malloc_debug(char *, ...);
static inline void malloc_error(char *, ...);
static inline void malloc_warn(char *, ...);

/*****************************************************************************
 * low-level memory management code                                             *
 *****************************************************************************/
/* this is the low-level malloc system code.  this code is used to track pages
 * used by malloc and to gain memory for the block structures.  further down is
 * the actual malloc code. */
/* this is the minimum number of pages we will ask the system for when
 * increasing the program's brk section */
#define MALLOC_PAGE_MINALLOC 16
/* this is the number of free pages we will cache *at the end of the heap area*
 * when looking to return data back to the system */
#define MALLOC_PAGE_CACHE MALLOC_PAGE_MINALLOC

/* flags in the page listing.  each page is represented by a single byte in an
 * array.  initially the array is allocated to handle MALLOC_PAGESIZE pages via
 * mmap.  we also store the offset of the first free page in the count so that
 * we can find free pages somewhat more quickly. */
#define MALLOC_PAGE_OTHER        0
#define MALLOC_PAGE_FREE        0x01
#define MALLOC_PAGE_BALLOC        0x02
#define MALLOC_PAGE_ALLOC        0x04
#define MALLOC_PAGE_START        (MALLOC_PAGE_BALLOC | MALLOC_PAGE_ALLOC)
#define MALLOC_PAGE_CONTINUED        0x08
static struct {
    char *start;                        /* start of memory */
    char *end;                                /* end of memory */

    char *parray;                        /* array of page descriptions */
    size_t size;                        /* size of the page array */
} page_desc;

/* find the next page boundary after 'addr'.  if addr is page-aligned then it
 * is returned unmodified. */
#define next_page_boundary(addr) ((long)(addr) % MALLOC_PAGESIZE != 0 ?        \
        (addr) + (MALLOC_PAGESIZE - (long)(addr) % MALLOC_PAGESIZE) : (addr))
/* macro to get the address of the character in the page map for a certain
 * address */
#define mem_to_pindex(mem)                                                \
    (((char *)(mem) - page_desc.start) / MALLOC_PAGESIZE)
#define pindex_to_mem(idx) (page_desc.start + (idx * MALLOC_PAGESIZE))

/* grow the heap by 'count' pages.  will return false if this fails */
static bool grow_heap(int count) {
    char *mem, *s;
    unsigned int len;

    mem = sbrk(0); /* see what our breakpoint is now... this may not be page
                      aligned.. */
    mem = next_page_boundary(mem);
    page_desc.end = mem;

    if (count < MALLOC_PAGE_MINALLOC)
        count = MALLOC_PAGE_MINALLOC;

    if (brk(page_desc.end + (count * MALLOC_PAGESIZE)) != 0)
        return false;
    page_desc.end += count * MALLOC_PAGESIZE;

    /* we've added at least another 'len' pages to the map. we need to do some
     * work to figure out if we need to increase the page array, and where it
     * should be filled in (because other people may call brk() on us.) */
    len = (page_desc.end - page_desc.start) / MALLOC_PAGESIZE;
    if (len > page_desc.size) {
        /* our array is too small, get a new one.. */
        s = page_desc.parray;
        if ((page_desc.parray = mmap(NULL, page_desc.size + MALLOC_PAGESIZE,
                PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0)) == NULL) {
            malloc_error("mmap(NULL, %d, ...): %s",
                    page_desc.size + MALLOC_PAGESIZE, strerror(errno));
        }
        memset(page_desc.parray, MALLOC_PAGE_OTHER,
                page_desc.size + MALLOC_PAGESIZE);
        if (s != NULL) {
            memcpy(page_desc.parray, s, page_desc.size);
            munmap(s, page_desc.size);
        }
        page_desc.size += MALLOC_PAGESIZE;
    }

    /* set our newly snagged pages free */
    s = page_desc.parray + ((mem - page_desc.start) / MALLOC_PAGESIZE);
    memset(s, MALLOC_PAGE_FREE, count);

    return true;
}

/* allocate 'count' pages.  for count>1 this gets increasingly expensive as we
 * traverse the page array.  if we have no free space to satisfy the request
 * then we increment the data size and return that memory */
static void *alloc_pages(int count) {
    int pages;
    int idx = 0, eidx;

    pages = (page_desc.end - page_desc.start) / MALLOC_PAGESIZE;
    while (idx < pages) {
        /* skip any non-free pages */
        while (idx < pages && page_desc.parray[idx] != MALLOC_PAGE_FREE)
            idx++;
        if (idx == pages)
            break;

        /* now see if this region is large enough */
        eidx = idx;
        while (eidx < pages && page_desc.parray[eidx] == MALLOC_PAGE_FREE)
            eidx++;
        if (eidx - idx >= count) {
            /* we have enough free pages, great!  mark them as allocated and
             * then return the memory from the pages. */
            page_desc.parray[idx] = MALLOC_PAGE_ALLOC;
            while (--count != 0)
                page_desc.parray[idx + count] = MALLOC_PAGE_CONTINUED;
            return page_desc.start + (MALLOC_PAGESIZE * idx);
        }
        /* maybe try again.. (eidx will be the page after the last free group
         * we found, or 'pages' */
        idx = eidx;
    }

    /* okay, we couldn't find a free section above, guess we need to increase
     * the break */
    if (grow_heap(count))
        return alloc_pages(count);
    errno = ENOMEM;
    return NULL;
}

static void free_pages(void *mem) {
    unsigned int idx, eidx;

    if ((long)mem % MALLOC_PAGESIZE != 0) {
        malloc_warn("free_pages(%p): memory is not page-aligned?", mem);
        return;
    }

    /* find out how many pages were allocated */
    idx = mem_to_pindex(mem);
    eidx = idx + 1;
    while (page_desc.parray[eidx] == MALLOC_PAGE_CONTINUED &&
            eidx < page_desc.size)
        eidx++;
    memset(page_desc.parray + idx, MALLOC_PAGE_FREE, eidx - idx);

    /* see if there are pages at the end of the cache that can be given back to
     * the system. */
    idx = eidx = ((page_desc.end - page_desc.start) / MALLOC_PAGESIZE) - 1;
    while (page_desc.parray[idx] == MALLOC_PAGE_FREE && idx > 0)
        idx--;
    if ((idx += options.page_cache) < eidx) {
        /* some leftovers (we think).  we see if the break is what we think it
         * is, and if it is, then we return this memory to the system */
        mem = page_desc.start + (MALLOC_PAGESIZE * idx);
        if (sbrk(0) == page_desc.end) {
            malloc_debug("free_pages(): returning %d pages to the system",
                    (eidx - idx));
            if (brk(mem) != 0)
                abort(); /* uh oh.. */
            page_desc.end = mem;
        }
    }
}

/*****************************************************************************
 * actual malloc code                                                             *
 *****************************************************************************/
/* the heap structure.  these are the top-level memory sources.  there is one
 * for each allocation size available.  using the defaults from above this
 * yields 47 separate heaps. */
#define MALLOC_HEAP_COUNT                                                \
(((MALLOC_MAX_SIZE - MALLOC_MIN_SIZE) / MALLOC_FUZZ) + 1)
struct heap {
    size_t size;                    /* size allocated to the heap */
    int etotal;                     /* total element count */
    int ealloc;                     /* allocated element count */

    int blocks;                     /* 'blocks' of memory allocated */
    int bpages;                     /* number of pages we're using for blocks, will
                                       increase until bpages > MALLOC_MAX_PAGES or
                                       the number of elements in a block would be >
                                       MALLOC_MAX_ELEMS */
    int bempty;                     /* blocks which are empty */
    int bfull;                      /* blockx which are full */

    int allocs;                     /* 'alloc' calls */
    int frees;                      /* 'free' calls */

    LIST_HEAD(, block) blist;       /* list of allocated blocks */
    LIST_HEAD(, block) oblist;      /* list of blocks with some free memory */
} heaps[MALLOC_HEAP_COUNT];

/* a block is a region of contiguous memory.  the size of a block may vary from
 * block to block, depending on how the heap allocator has tuned itself. */
struct block {
    struct heap *heap;              /* the heap this block belongs to */
    char *start;                    /* start of memory */
    char *end;                      /* end of memory.  this is the end in terms of
                                       where the last *element* ends, there may be
                                       unused memory beyond this point up to the
                                       next page boundary. */
    unsigned int used;              /* number of used elements */
    SLIST_HEAD(, block_elem) elist;

    LIST_ENTRY(block) lp;
    LIST_ENTRY(block) olp;
};
#define elems_in_block(block)                                                \
(((block)->end - (block)->start) / (block)->heap->size)

/* this is a single element in a block.  block elements are stored in a singly
 * linked list for quick allocation */
struct block_elem {
#define MALLOC_MAGIC (uint32_t)0xdeadc0de
    uint32_t magic;                /* the magic number.  set when this block
                                   should no longer be touched */
    SLIST_ENTRY(block_elem) lp;
};

/*****************************************************************************
 * initialization code                                                             *
 *****************************************************************************/
const char *_malloc_options = NULL;

/* parse the options contained in buf. */
static void malloc_init_options(const char *buf) {

    while (*buf != '\0') {
        switch (*buf) {
        case '>': options.page_cache <<= 1;                        break;
        case '<': options.page_cache >>= 1;                        break;
        case 'a': options.wfatal = false;                        break;
        case 'A': options.wfatal = true;                        break;
        case 'b': options.block_cache--;                        break;
        case 'B': options.block_cache++;                        break;
        case 'j': options.fill = false;                                break;
        case 'J': options.fill = true; options.fbyte = 0xd0;        break;
        case 'l': options.optimize = false;                     break;
        case 'L': options.optimize = true;                      break;
        case 'r': options.force_realloc = false;                break;
        case 'R': options.force_realloc = true;                        break;
        case 's': options.sanity = false;                        break;
        case 'S': options.sanity = true;                        break;
        case 'v': options.sysv_compat = false;                        break;
        case 'V': options.sysv_compat = true;                        break;
        case 'z': options.fill = false;                                break;
        case 'Z': options.fill = true; options.fbyte = 0x0;        break;
        }
        buf++;
    }
}

static int recursing;

/* output functions for warnings and such.  keeps us from trapping recursive
 * calls on accident. */
static inline void malloc_debug(char *msg, ...) {
#ifndef NDEBUG
    va_list vl;

    va_start(vl, msg);
    recursing--;
    log_vmsg(LOGTYPE_DEBUG, LOG_MODULENAME, msg, vl);
    va_end(vl);
    recursing++;
#endif
}

static inline void malloc_error(char *msg, ...) {
    va_list vl;

    va_start(vl, msg);
    recursing--;
    log_vmsg(LOGTYPE_ERROR, LOG_MODULENAME, msg, vl);
    abort();
    va_end(vl);
    recursing++;
}

static void malloc_warn(char *msg, ...) {
    va_list vl;

    va_start(vl, msg);
    recursing--;
    log_vmsg(LOGTYPE_WARN, LOG_MODULENAME, msg, vl);
    if (options.wfatal)
        abort();
    va_end(vl);
    recursing++;
}

/* initiate the malloc subsystem.  get the page size and then initiate each
 * entry in the heaps array. */
static bool malloc_initialized = false;
static void malloc_init(void) {
    int i;
    size_t sz;
#define BUFSIZE 64
    char buf[BUFSIZE];
    const char *s;

    options.page_cache = MALLOC_PAGE_CACHE;
    options.block_cache = MALLOC_CACHE_BLOCKS;
    options.optimize = true;

#ifdef HAVE_READLINK
    if ((i = readlink(MALLOC_CONFIG_FILE, buf, BUFSIZE)) >= BUFSIZE)
        i = BUFSIZE - 1;
    buf[i] = '\0';
    malloc_init_options(buf);
#endif
#ifdef HAVE_GETENV
    if ((s = getenv("MALLOC_OPTIONS")) != NULL)
        malloc_init_options(s);
#endif
    if ((s = _malloc_options) != NULL)
        malloc_init_options(s);

    page_desc.start = page_desc.end = sbrk(0);
    s = next_page_boundary(page_desc.start);
    if (brk((const void *)s) != 0)
        abort();
    page_desc.start = page_desc.end = (void *)s;

    for (i = 0, sz = MALLOC_MIN_SIZE; i < MALLOC_HEAP_COUNT;
            i++, sz += MALLOC_FUZZ) {
        heaps[i].size = sz;
        heaps[i].bpages = 1;
    }
    malloc_initialized = true;
}

/* these are the support functions.. */
static struct block *create_block(struct heap *);
static void destroy_block(struct block *);
static void *alloc_block(struct block *);
static void free_block(struct block *, void *);
static struct block *find_block(void *, size_t *);

/* do a 'sorted' insert into the open blocks list for a heap.  this ensures
 * that the blocks with the lowest memory addresses are used, which makes the
 * library more likely to wrangle free towards the end of memory. */
static void insert_open_block(struct block *blk) {
    struct block *bp;

    if (LIST_EMPTY(&blk->heap->oblist)) {
        LIST_INSERT_HEAD(&blk->heap->oblist, blk, olp);
        return;
    }

    LIST_FOREACH(bp, &blk->heap->oblist, olp) {
        if (bp > blk) {
            LIST_INSERT_BEFORE(bp, blk, olp);
            return;
        }
        else if (LIST_NEXT(bp, olp) == NULL)
            break;
    }
    LIST_INSERT_AFTER(bp, blk, olp);
}

/* create a block for the given heap and fill it in.  this handles the
 * incremental growth for the heap as well */
static struct block *create_block(struct heap *hp) {
    struct block *bp;
    struct block_elem *ep;
    int elems;
    char *mem;

    bp = alloc_pages(hp->bpages);
    /* tweak the start of the page allocation to be 'BALLOC' so we know memory
     * in this range is owned by a block */
    elems = mem_to_pindex(bp);
    page_desc.parray[elems] = MALLOC_PAGE_BALLOC;
    bp->heap = hp;
    mem = bp->start = (char *)bp + sizeof(struct block);
    /* there may be some leftover space at the end of the block,
     * unfortunately.. we calculate the number of actual full elements in this
     * block using size */
    elems = ((MALLOC_PAGESIZE * hp->bpages) - sizeof(struct block)) / hp->size;
    bp->end = bp->start + (hp->size * elems);
    bp->used = 0;

    SLIST_INIT(&bp->elist);
    while (mem < bp->end) {
        ep = (struct block_elem *)mem;
        ep->magic = MALLOC_MAGIC;
        SLIST_INSERT_HEAD(&bp->elist, ep, lp);

        mem += hp->size;
    }
    LIST_INSERT_HEAD(&bp->heap->blist, bp, lp);
    insert_open_block(bp);

    /* now do some accounting */
    bp->heap->etotal += elems;
    bp->heap->blocks++;
    bp->heap->bempty++;

    /* see if bpages needs to be grown (but we only do this if optimization is
     * left on) */
    if  (hp->bpages < MALLOC_MAX_PAGES && options.optimize) {
        hp->bpages *= 2;
        if (((MALLOC_PAGESIZE * hp->bpages) - sizeof(struct block)) /
                hp->size > MALLOC_MAX_ELEMS)
            hp->bpages /= 2; /* guess not */
    }

    return bp;
}

/* destroy a block.  usually done when the block is empty, or at shutdown time
 * by the program.  we are careful not to free the memory contained by the
 * block until after we have freed the block because the block could be
 * contained in that memory (yikes..) */
static void destroy_block(struct block *bp) {
    struct heap *hp = bp->heap;

    LIST_REMOVE(bp, lp);
    if (bp->used != elems_in_block(bp))
        LIST_REMOVE(bp, olp);
    else
        hp->bfull--;
    if (bp->used != 0)
        malloc_debug("destroying non-empty block");
    else
        hp->bempty--;
    free_pages(bp);
}

static void *alloc_block(struct block *bp) {
    struct block_elem *ep;

    if (options.sanity &&
            (bp->used == elems_in_block(bp) || SLIST_EMPTY(&bp->elist))) {
        malloc_error("alloc_block(): block has no free elements!");
        return NULL;
    }
    
    bp->heap->allocs++;

    if (bp->used == 0)
        bp->heap->bempty--;
    bp->used++;

    ep = SLIST_FIRST(&bp->elist);
    if (options.sanity && ep->magic != MALLOC_MAGIC)
        malloc_warn("alloc_block(%d): apparent memory corruption",
                bp->heap->size);
    SLIST_REMOVE_HEAD(&bp->elist, lp);
    if (SLIST_EMPTY(&bp->elist)) {
        LIST_REMOVE(bp, olp); /* take it off the open list */
        bp->heap->bfull++;
    }
    ep->magic = 0; /* wipe the magic number */
    return ep;
}

/* return 'mem' to the specified block.  this does some sanity checking on the
 * way. */
static void free_block(struct block *bp, void *mem) {
    struct block_elem *ep = mem;

    if (ep->magic == MALLOC_MAGIC) {
        malloc_warn("free_block(%d, %p): freeing already freed memroy?",
                bp->heap->size, mem);
        return;
    }
    bp->heap->frees++;

    if (options.fill)
        memset(mem, options.fbyte, bp->heap->size);

    ep->magic = MALLOC_MAGIC;
    SLIST_INSERT_HEAD(&bp->elist, ep, lp);
    if (bp->used == elems_in_block(bp)) {
        bp->heap->bfull--;
        insert_open_block(bp);
    }
    if (--bp->used == 0) {
        bp->heap->bempty++;
        if (bp->heap->bempty > MALLOC_CACHE_BLOCKS)
            destroy_block(bp);
    }
}

/* attempt to find the owning block of a memory address.  if it doesn't reside
 * in a block but is a page or multipage allocation we return NULL but set
 * 'size' to the size of the allocated pages.  whew. */
static struct block *find_block(void *mem, size_t *rsize) {
    struct block *bp;
    unsigned int idx, eidx;

    *rsize = 0;
    if ((char *)mem < page_desc.start ||
            (eidx = idx = mem_to_pindex(mem)) > page_desc.size) {
        malloc_warn("find_block(%p): pointer is outside of memory range", mem);
        return NULL;
    }
    while (page_desc.parray[idx] == MALLOC_PAGE_CONTINUED)
        idx--;
    if (page_desc.parray[idx] == MALLOC_PAGE_ALLOC) {
        /* if this was a normal allocation we just say it was the pagesize,
         * this might not be true but only actually matters for filling, and
         * free_pages will fill the whole allocation for us. */
        if (options.sanity && pindex_to_mem(idx) != mem)
            malloc_warn("find_block(%p): multipage allocation starts at %p",
                    pindex_to_mem(idx));
        *rsize = MALLOC_PAGESIZE;
        return NULL;
    } else if (page_desc.parray[idx] == MALLOC_PAGE_BALLOC)
        bp = (struct block *)pindex_to_mem(idx);
    else {
        malloc_warn("find_page(%p): pointer did not end up in an allocated "
                "range (actually in %s memory)",
                (page_desc.parray[idx] == MALLOC_PAGE_FREE ? "free" :
                 "unknown"));
        return NULL;
    }

    /* bp is valid.. */
    *rsize = bp->heap->size;
    return bp;
}

/* these are the four allocator functions.  in general they pass off work to
 * subsystem functions declared below. */
void *calloc(size_t count, size_t size) {
    void *mem;

    if ((mem = malloc(count * size)) != NULL)
        memset(mem, 0, count * size);
    return mem;
}

void free(void *mem) {
    struct block *bp;
    size_t size;

    if (recursing) {
        malloc_warn("free(%p): recursing in allocator", mem);
        return;
    }
    recursing++;

    if (!malloc_initialized) {
        malloc_warn("free(%p): no memory has been allocated", mem);
        recursing--;
        return;
    }
    bp = find_block(mem, &size);
    if (bp == NULL && size == 0) {
        malloc_warn("free(%p): memory not found", mem);
        recursing--;
        return;
    }
    
    if (bp == NULL) {
    if (options.fill)
        memset(mem, options.fbyte, size);
        free_pages(mem);
    } else
        free_block(bp, mem);

    recursing--;
}

void *malloc(size_t size) {
    struct block *bp;
    void *mem;

    if (recursing) {
        malloc_warn("malloc(%d): recursing in allocator", size);
        return NULL;
    }
    recursing++;

    if (!malloc_initialized)
        malloc_init();

    if (size == 0) {
        if (options.sysv_compat) {
            recursing--;
            return NULL;
        } else
            size = MALLOC_MIN_SIZE;
    }

    if (size > MALLOC_MAX_SIZE) {
        /* change 'size' to reflect the number of pages we want */
        if (size % MALLOC_PAGESIZE != 0)
            size = (size / MALLOC_PAGESIZE) + 1;
        else
            size /= MALLOC_PAGESIZE;
        recursing--;
        return alloc_pages(size);
    }

    /* adjust it for fuzz */
    if (size % MALLOC_FUZZ != 0)
        size += MALLOC_FUZZ - (size % MALLOC_FUZZ);
    /* size should never be smaller than MALLOC_MIN_SIZE now.. unless
     * MALLOC_FUZZ was mangled. :) */

    /* so it's of an appropriate size, now to figure out what heap it comes
     * from we just need to apply a simple algorithm.. */
    size -= MALLOC_MIN_SIZE;
    size /= MALLOC_FUZZ; /* and now 'size' is actually our heap */

    if ((bp = LIST_FIRST(&heaps[size].oblist)) == NULL) {
        if ((bp = create_block(&heaps[size])) == NULL) {
            if (options.nomem_fatal)
                malloc_error("malloc(%d): out of memory", heaps[size].size);
            recursing--;
            return NULL;
        }
    }
    mem = alloc_block(bp);
    if (options.fill)
        memset(mem, options.fbyte, heaps[size].size);

    recursing--;
    return mem; /* huzzah! */
}

/* realloc is fairly complicated (under the hood): we always frree mem, and we
 * always freshly allocate.  eh.  problem is we have to find the heap mem came
 * from because we need to know how big it is. */
void *realloc(void *mem, size_t newsize) {
    struct block *bp = NULL;
    size_t size = 0;
    void *newmem;
    
    if (recursing) {
        malloc_warn("realloc(%p, %d): recursing in allocator", mem, newsize);
        return NULL;
    }
    recursing++;

    if (!malloc_initialized) {
        if (mem != NULL) {
            malloc_warn("realloc(%p, %d): called before initial allocation",
                    mem, newsize);
            mem = NULL;
        }
        malloc_init();
    }
    if (mem == NULL) {
        recursing--;
        if (newsize == 0)
            return NULL;
        return malloc(newsize);
    }

    bp = find_block(mem, &size);
    if (bp == NULL && size == 0) {
        malloc_warn("realloc(%p, %d): could not find memory", mem, newsize);
        recursing--;
        return NULL;
    }

    /* unset recursing so we can manually call malloc.. */
    recursing--;
    if (!options.force_realloc && size >= newsize)
        return mem; /* no need to move any memory ... */

    if ((newmem = malloc(newsize)) == NULL)
        return NULL; /* oops.. */
    if (options.fill)
        memset(newmem, options.fbyte, newsize);
    /* we can't use 'size' verbatim because it might be bigger than the new
     * size, of course. */
    if (size > newsize)
        size = newsize;
    memcpy(newmem, mem, size);
    if (bp != NULL)
        free_block(bp, mem);
    else
        free_pages(mem);
    return newmem;
}

#endif
/* vi:set ts=8 sts=4 sw=4 tw=76 et: */