8322 nl: misleading-indentation

[unleashed/tickless.git] / usr / src / lib / libbc / libc / gen / common / malloc.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 1986 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I%     %E% SMI"

/*
 * file: malloc.c
 * description:
 *      Yet another memory allocator, this one based on a method
 *      described in C.J. Stephenson, "Fast Fits"
 *
 *      The basic data structure is a "Cartesian" binary tree, in which
 *      nodes are ordered by ascending addresses (thus minimizing free
 *      list insertion time) and block sizes decrease with depth in the
 *      tree (thus minimizing search time for a block of a given size).
 *
 *      In other words: for any node s, let D(s) denote the set of
 *      descendents of s; for all x in D(left(s)) and all y in
 *      D(right(s)), we have:
 *
 *      a. addr(x) <  addr(s) <  addr(y)
 *      b. len(x)  <= len(s)  >= len(y)
 */

#include "mallint.h"
#include <errno.h>
#include <stdlib.h>
#include <stdarg.h>

/* system interface */

extern  char    *sbrk();
extern  int     getpagesize();

static  int     nbpg = 0;       /* set by calling getpagesize() */
static  bool    morecore(uint); /* get more memory into free space */

#ifdef  S5EMUL
#define ptr_t           void *  /* ANSI C says these are voids */
#define free_t          void    /* ANSI says void free(ptr_t ptr) */
#define free_return(x)  return
#else
#define ptr_t           char *  /* BSD still (4.3) wants char*'s */
#define free_t          int     /* BSD says int free(ptr_t ptr) */
#define free_return(x)  return(x)
#endif

/* SystemV-compatible information structure */
#define INIT_MXFAST 0
#define INIT_NLBLKS 100
#define INIT_GRAIN ALIGNSIZ

struct  mallinfo __mallinfo = {
        0,0,0,0,0,0,0,0,0,0,                    /* basic info */
        INIT_MXFAST, INIT_NLBLKS, INIT_GRAIN,   /* mallopt options */
        0,0,0
};

/* heap data structures */

Freehdr _root   = NIL;                  /* root of free space list */
char    *_lbound = NULL;                /* lower bound of heap */
char    *_ubound = NULL;                /* upper bound of heap */

/* free header list management */

static  Freehdr getfreehdr(void);
static  void    putfreehdr(Freehdr);
static  Freehdr freehdrptr = NIL;       /* ptr to block of available headers */
static  int     nfreehdrs = 0;          /* # of headers in current block */
static  Freehdr freehdrlist = NIL;      /* List of available headers */

/* error checking */
static void     error(char *, ...);
/* sets errno; prints msg and aborts if DEBUG is on */

static int      reclaim(Dblk, uint, int);

#ifdef  DEBUG   /*      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */

int     malloc_debug(int);
int     malloc_verify(void);
static  int debug_level = 1;

/*
 * A block with a negative size, a size that is not a multiple
 * of ALIGNSIZ, a size greater than the current extent of the
 * heap, or a size which extends beyond the end of the heap is
 * considered bad.
 */

#define badblksize(p,size)\
( (size) < SMALLEST_BLK \
        || (size) & (ALIGNSIZ-1) \
        || (size) > heapsize() \
        || ((char*)(p))+(size) > _ubound )

#else   /* !DEBUG       ================================================= */

#define malloc_debug(level) 0
#define malloc_verify() 1
#define debug_level 0
#define badblksize(p,size) 0

#endif  /* !DEBUG       <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */


/*
 * insert (newblk, len)
 *      Inserts a new node in the free space tree, placing it
 *      in the correct position with respect to the existing nodes.
 *
 * algorithm:
 *      Starting from the root, a binary search is made for the new
 *      node. If this search were allowed to continue, it would
 *      eventually fail (since there cannot already be a node at the
 *      given address); but in fact it stops when it reaches a node in
 *      the tree which has a length less than that of the new node (or
 *      when it reaches a null tree pointer).
 *
 *      The new node is then inserted at the root of the subtree for
 *      which the shorter node forms the old root (or in place of the
 *      null pointer).
 *
 * Arguments
 *      newblk: Ptr to the block to insert
 *      len:    Length of new node
 */

static void
insert(Dblk newblk, uint len)
{
        Freehdr *fpp;           /* Address of ptr to subtree */
        Freehdr x;
        Freehdr *left_hook;     /* Temp for insertion */
        Freehdr *right_hook;    /* Temp for insertion */
        Freehdr newhdr;

        /*
         * check for bad block size.
         */
        if ( badblksize(newblk,len) ) {
                error("insert: bad block size (%d) at %#x\n", len, newblk);
                return;
        }

        /*
         * Search for the first node which has a weight less
         *      than that of the new node; this will be the
         *      point at which we insert the new node.
         */
        fpp = &_root;
        x = *fpp;
        while (weight(x) >= len) {      
                if (newblk < x->block)
                        fpp = &x->left;
                else
                        fpp = &x->right;
                x = *fpp;
        }

        /*
         * Perform root insertion. The variable x traces a path through
         *      the fpp, and with the help of left_hook and right_hook,
         *      rewrites all links that cross the territory occupied
         *      by newblk.
         */ 

        if ((newhdr = getfreehdr()) == NIL) {
                /* Error message returned by getfreehdr() */
                return;
        }
        *fpp = newhdr;

        newhdr->left = NIL;
        newhdr->right = NIL;
        newhdr->block = newblk;
        newhdr->size = len;

        /*
         * set length word in the block for consistency with the header.
         */

        newblk->size = len;

        left_hook = &newhdr->left;
        right_hook = &newhdr->right;

        while (x != NIL) {
                /*
                 * Remark:
                 *      The name 'left_hook' is somewhat confusing, since
                 *      it is always set to the address of a .right link
                 *      field.  However, its value is always an address
                 *      below (i.e., to the left of) newblk. Similarly
                 *      for right_hook. The values of left_hook and
                 *      right_hook converge toward the value of newblk,
                 *      as in a classical binary search.
                 */
                if (x->block < newblk) {
                        /*
                         * rewrite link crossing from the left
                         */
                        *left_hook = x;
                        left_hook = &x->right;
                        x = x->right;
                } else {
                        /*
                         * rewrite link crossing from the right
                         */
                        *right_hook = x;
                        right_hook = &x->left;
                        x = x->left;
                } /*else*/
        } /*while*/

        *left_hook = *right_hook = NIL;         /* clear remaining hooks */

} /*insert*/

/*
 * delete(p)
 *      deletes a node from a cartesian tree. p is the address of
 *      a pointer to the node which is to be deleted.
 *
 * algorithm:
 *      The left and right branches of the node to be deleted define two
 *      subtrees which are to be merged and attached in place of the
 *      deleted node.  Each node on the inside edges of these two
 *      subtrees is examined and longer nodes are placed above the
 *      shorter ones.
 *
 * On entry:
 *      *p is assumed to be non-null.
 */
static void
delete(Freehdr *p)
{
        Freehdr x;
        Freehdr left_branch;    /* left subtree of deleted node */
        Freehdr right_branch;   /* right subtree of deleted node */
        uint left_weight;
        uint right_weight;

        x = *p;
        left_branch = x->left;
        left_weight = weight(left_branch);
        right_branch = x->right;
        right_weight = weight(right_branch);

        while (left_branch != right_branch) {   
                /*
                 * iterate until left branch and right branch are
                 * both NIL.
                 */
                if ( left_weight >= right_weight ) {
                        /*
                         * promote the left branch
                         */
                        if (left_branch != NIL) {
                                if (left_weight == 0) {
                                        /* zero-length block */
                                        error("blocksize=0 at %#x\n",
                                                (int)left_branch->block->data);
                                        break;
                                }
                                *p = left_branch;
                                p = &left_branch->right;
                                left_branch = *p;
                                left_weight = weight(left_branch);
                        }
                } else {
                        /*
                         * promote the right branch
                         */
                        if (right_branch != NIL) {
                                if (right_weight == 0) {
                                        /* zero-length block */
                                        error("blocksize=0 at %#x\n",
                                                (int)right_branch->block->data);
                                        break;
                                }
                                *p = right_branch;
                                p = &right_branch->left;
                                right_branch = *p;
                                right_weight = weight(right_branch);
                        }
                }/*else*/
        }/*while*/
        *p = NIL;
        putfreehdr(x);
} /*delete*/


/*
 * demote(p)
 *      Demotes a node in a cartesian tree, if necessary, to establish
 *      the required vertical ordering.
 *
 * algorithm:
 *      The left and right subtrees of the node to be demoted are to
 *      be partially merged and attached in place of the demoted node.
 *      The nodes on the inside edges of these two subtrees are
 *      examined and the longer nodes are placed above the shorter
 *      ones, until a node is reached which has a length no greater
 *      than that of the node being demoted (or until a null pointer
 *      is reached).  The node is then attached at this point, and
 *      the remaining subtrees (if any) become its descendants.
 *
 * on entry:
 *   a. All the nodes in the tree, including the one to be demoted,
 *      must be correctly ordered horizontally;
 *   b. All the nodes except the one to be demoted must also be
 *      correctly positioned vertically.  The node to be demoted
 *      may be already correctly positioned vertically, or it may
 *      have a length which is less than that of one or both of
 *      its progeny.
 *   c. *p is non-null
 */

static void
demote(Freehdr *p)
{
        Freehdr x;              /* addr of node to be demoted */
        Freehdr left_branch;
        Freehdr right_branch;
        uint    left_weight;
        uint    right_weight;
        uint    x_weight;

        x = *p;
        x_weight = weight(x);
        left_branch = x->left;
        right_branch = x->right;
        left_weight = weight(left_branch);
        right_weight = weight(right_branch);

        while (left_weight > x_weight || right_weight > x_weight) {
                /*
                 * select a descendant branch for promotion
                 */
                if (left_weight >= right_weight) {
                        /*
                         * promote the left branch
                         */
                        *p = left_branch;
                        p = &left_branch->right;
                        left_branch = *p;
                        left_weight = weight(left_branch);
                } else {
                        /*
                         * promote the right branch
                         */
                        *p = right_branch;
                        p = &right_branch->left;
                        right_branch = *p;
                        right_weight = weight(right_branch);
                } /*else*/
        } /*while*/

        *p = x;                         /* attach demoted node here */
        x->left = left_branch;
        x->right = right_branch;

} /*demote*/


/*
 * char*
 * malloc(nbytes)
 *      Allocates a block of length specified in bytes.  If nbytes is
 *      zero, a valid pointer (that should not be dereferenced) is returned.
 *
 * algorithm:
 *      The freelist is searched by descending the tree from the root
 *      so that at each decision point the "better fitting" branch node
 *      is chosen (i.e., the shorter one, if it is long enough, or
 *      the longer one, otherwise).  The descent stops when both
 *      branch nodes are too short.
 *
 * function result:
 *      Malloc returns a pointer to the allocated block. A null
 *      pointer indicates an error.
 *
 * diagnostics:
 *
 *      ENOMEM: storage could not be allocated.
 *
 *      EINVAL: either the argument was invalid, or the heap was found
 *      to be in an inconsistent state.  More detailed information may
 *      be obtained by enabling range checks (cf., malloc_debug()).
 *
 * Note: In this implementation, each allocated block includes a
 *      length word, which occurs before the address seen by the caller.
 *      Allocation requests are rounded up to a multiple of wordsize.
 */

ptr_t
malloc(uint nbytes)
{
        Freehdr allocp; /* ptr to node to be allocated */
        Freehdr *fpp;           /* for tree modifications */
        Freehdr left_branch;
        Freehdr right_branch;
        uint     left_weight;
        uint     right_weight;
        Dblk     retblk;                /* block returned to the user */

        /*
         * if rigorous checking was requested, do it.
         */
        if (debug_level >= 2) {
                malloc_verify();
        }

        /*
         * add the size of a length word to the request, and
         * guarantee at least one word of usable data.
         */
        nbytes += ALIGNSIZ;
        if (nbytes < SMALLEST_BLK) {
                nbytes = SMALLEST_BLK;
        } else {
                nbytes = roundup(nbytes, ALIGNSIZ);
        }

        /*
         * ensure that at least one block is big enough to satisfy
         *      the request.
         */

        if (weight(_root) < nbytes) {
                /*
                 * the largest block is not enough. 
                 */
                if(!morecore(nbytes))
                        return 0;
        }

        /*
         * search down through the tree until a suitable block is
         *      found.  At each decision point, select the better
         *      fitting node.
         */

        fpp = &_root;
        allocp = *fpp;
        left_branch = allocp->left;
        right_branch = allocp->right;
        left_weight = weight(left_branch);
        right_weight = weight(right_branch);

        while (left_weight >= nbytes || right_weight >= nbytes) {
                if (left_weight <= right_weight) {
                        if (left_weight >= nbytes) {
                                fpp = &allocp->left;
                                allocp = left_branch;
                        } else {
                                fpp = &allocp->right;
                                allocp = right_branch;
                        }
                } else {
                        if (right_weight >= nbytes) {
                                fpp = &allocp->right;
                                allocp = right_branch;
                        } else {
                                fpp = &allocp->left;
                                allocp = left_branch;
                        }
                }
                left_branch = allocp->left;
                right_branch = allocp->right;
                left_weight = weight(left_branch);
                right_weight = weight(right_branch);
        } /*while*/     

        /*
         * allocate storage from the selected node.
         */
        
        if (allocp->size - nbytes <= SMALLEST_BLK) {
                /*
                 * not big enough to split; must leave at least
                 * a dblk's worth of space.
                 */
                retblk = allocp->block;
                delete(fpp);
        } else {

                /*
                 * Split the selected block n bytes from the top. The
                 * n bytes at the top are returned to the caller; the
                 * remainder of the block goes back to free space.
                 */
                Dblk nblk;

                retblk = allocp->block;
                nblk = nextblk(retblk, nbytes);         /* ^next block */
                nblk->size =  allocp->size = retblk->size - nbytes; 
                __mallinfo.ordblks++;                   /* count fragments */

                /*
                 * Change the selected node to point at the newly split
                 * block, and move the node to its proper place in
                 * the free space list.
                 */
                allocp->block = nblk;
                demote(fpp);

                /*
                 * set the length field of the allocated block; we need
                 * this because free() does not specify a length.
                 */
                retblk->size = nbytes;
        }
        /* maintain statistics */
        __mallinfo.uordbytes += retblk->size;           /* bytes allocated */
        __mallinfo.allocated++;                         /* frags allocated */
        if (nbytes < __mallinfo.mxfast)
                __mallinfo.smblks++;    /* kludge to pass the SVVS */

        return((ptr_t)retblk->data);

} /*malloc*/

/*
 * free(p)
 *      return a block to the free space tree.
 * 
 * algorithm:
 *      Starting at the root, search for and coalesce free blocks
 *      adjacent to one given.  When the appropriate place in the
 *      tree is found, insert the given block.
 *
 * Some sanity checks to avoid total confusion in the tree.
 *      If the block has already been freed, return.
 *      If the ptr is not from the sbrk'ed space, return.
 *      If the block size is invalid, return.
 */
free_t
free(ptr_t ptr)
{
        uint     nbytes;        /* Size of node to be released */
        Freehdr *fpp;           /* For deletion from free list */
        Freehdr neighbor;       /* Node to be coalesced */
        Dblk     neighbor_blk;  /* Ptr to potential neighbor */
        uint     neighbor_size; /* Size of potential neighbor */
        Dblk     oldblk;        /* Ptr to block to be freed */

        /*
         * if rigorous checking was requested, do it.
         */
        if (debug_level >= 2) {
                malloc_verify();
        }

        /*
         * Check the address of the old block.
         */
        if ( misaligned(ptr) ) {
                error("free: illegal address (%#x)\n", ptr);
                free_return(0);
        }

        /*
         * Freeing something that wasn't allocated isn't
         * exactly kosher, but fclose() does it routinely.
         */
        if( ptr < (ptr_t)_lbound || ptr > (ptr_t)_ubound ) {
                errno = EINVAL;
                free_return(0);
        }

        /*
         * Get node length by backing up by the size of a header.
         * Check for a valid length.  It must be a positive 
         * multiple of ALIGNSIZ, at least as large as SMALLEST_BLK,
         * no larger than the extent of the heap, and must not
         * extend beyond the end of the heap.
         */
        oldblk = (Dblk)((char*)ptr - ALIGNSIZ);
        nbytes = oldblk->size;
        if (badblksize(oldblk,nbytes)) {
                error("free: bad block size (%d) at %#x\n",
                        (int)nbytes, (int)oldblk );
                free_return(0);
        }

        /* maintain statistics */
        __mallinfo.uordbytes -= nbytes;         /* bytes allocated */
        __mallinfo.allocated--;                 /* frags allocated */

        /*
         * Search the tree for the correct insertion point for this
         *      node, coalescing adjacent free blocks along the way.
         */
        fpp = &_root;
        neighbor = *fpp;
        while (neighbor != NIL) {
                neighbor_blk = neighbor->block;
                neighbor_size = neighbor->size;
                if (oldblk < neighbor_blk) {
                        Dblk nblk = nextblk(oldblk,nbytes);
                        if (nblk == neighbor_blk) {
                                /*
                                 * Absorb and delete right neighbor
                                 */
                                nbytes += neighbor_size;
                                __mallinfo.ordblks--;
                                delete(fpp);
                        } else if (nblk > neighbor_blk) {
                                /*
                                 * The block being freed overlaps
                                 * another block in the tree.  This
                                 * is bad news.  Return to avoid
                                 * further fouling up the the tree.
                                 */
                                 error("free: blocks %#x, %#x overlap\n",
                                                (int)oldblk, (int)neighbor_blk);
                                 free_return(0);
                        } else {
                                /*
                                 * Search to the left
                                 */
                                fpp = &neighbor->left;
                        }
                } else if (oldblk > neighbor_blk) {
                        Dblk nblk = nextblk(neighbor_blk, neighbor_size);
                        if (nblk == oldblk) {
                                /*
                                 * Absorb and delete left neighbor
                                 */
                                oldblk = neighbor_blk;
                                nbytes += neighbor_size;
                                __mallinfo.ordblks--;
                                delete(fpp);
                        } else if (nblk > oldblk) {
                                /*
                                 * This block has already been freed
                                 */
                                error("free: block %#x was already free\n",
                                        (int)ptr);
                                free_return(0);
                        } else {
                                /*
                                 * search to the right
                                 */
                                fpp = &neighbor->right;
                        }
                } else {
                        /*
                         * This block has already been freed
                         * as "oldblk == neighbor_blk"
                         */
                        error("free: block %#x was already free\n", (int)ptr);
                        free_return(0);
                } /*else*/

                /*
                 * Note that this depends on a side effect of
                 * delete(fpp) in order to terminate the loop!
                 */
                neighbor = *fpp;

        } /*while*/

        /*
         * Insert the new node into the free space tree
         */
        insert( oldblk, nbytes );
        free_return(1);

} /*free*/


/*
 * char*
 * shrink(oldblk, oldsize, newsize)
 *      Decreases the size of an old block to a new size.
 *      Returns the remainder to free space.  Returns the
 *      truncated block to the caller.
 */

static char *
shrink(Dblk oldblk, uint oldsize, uint newsize)
{
        Dblk remainder;
        if (oldsize - newsize >= SMALLEST_BLK) {
                /*
                 * Block is to be contracted. Split the old block
                 * and return the remainder to free space.
                 */
                remainder = nextblk(oldblk, newsize);
                remainder->size = oldsize - newsize;
                oldblk->size = newsize;

                /* maintain statistics */
                __mallinfo.ordblks++;           /* count fragments */
                __mallinfo.allocated++;         /* negate effect of free() */

                free(remainder->data);
        }
        return(oldblk->data);
}

/*
 * char*
 * realloc(ptr, nbytes)
 *
 * Reallocate an old block with a new size, returning the old block
 * if possible. The block returned is guaranteed to preserve the
 * contents of the old block up to min(size(old block), newsize).
 *
 * For backwards compatibility, ptr is allowed to reference
 * a block freed since the LAST call of malloc().  Thus the old
 * block may be busy, free, or may even be nested within a free
 * block. 
 *
 * Some old programs have been known to do things like the following,
 * which is guaranteed not to work:
 *
 *      free(ptr);
 *      free(dummy);
 *      dummy = malloc(1);
 *      ptr = realloc(ptr,nbytes);
 *
 * This atrocity was found in the source for diff(1).
 */
ptr_t
realloc(ptr_t ptr, uint nbytes)
{
        Freehdr *fpp;
        Freehdr fp;
        Dblk    oldblk;
        Dblk    freeblk;
        Dblk    oldneighbor;
        uint    oldsize;
        uint    newsize;
        uint    oldneighborsize;

        /*
         * Add SVR4 semantics for OS 5.x so /usr/lib librarys
         * work correctly when running in BCP mode
         */
        if (ptr == NULL) {
                return (malloc(nbytes));
        }

        /*
         * if rigorous checking was requested, do it.
         */
        if (debug_level >= 2) {
                malloc_verify();
        }

        /*
         * Check the address of the old block.
         */
        if ( misaligned(ptr) || 
            ptr < (ptr_t)_lbound || 
            ptr > (ptr_t)_ubound ) {
                error("realloc: illegal address (%#x)\n", ptr);
                return(NULL);
        }

        /*
         * check location and size of the old block and its
         * neighboring block to the right.  If the old block is
         * at end of memory, the neighboring block is undefined.
         */
        oldblk = (Dblk)((char*)ptr - ALIGNSIZ);
        oldsize = oldblk->size;
        if (badblksize(oldblk,oldsize)) {
                error("realloc: bad block size (%d) at %#x\n",
                        oldsize, oldblk);
                return(NULL);
        }
        oldneighbor = nextblk(oldblk,oldsize);

        /* *** tree search code pulled into separate subroutine *** */
        if (reclaim(oldblk, oldsize, 1) == -1) {
                return(NULL);           /* internal error */
        }

        /*
         * At this point, we can guarantee that oldblk is out of free
         * space. What we do next depends on a comparison of the size
         * of the old block and the requested new block size.  To do
         * this, first round up the new size request.
         */
        newsize = nbytes + ALIGNSIZ;            /* add size of a length word */
        if (newsize < SMALLEST_BLK) {
                newsize = SMALLEST_BLK;
        } else {
                newsize = roundup(newsize, ALIGNSIZ);
        }

        /*
         * Next, examine the size of the old block, and compare it
         * with the requested new size.
         */

        if (oldsize >= newsize) {
                /*
                 * Block is to be made smaller.
                 */
                return(shrink(oldblk, oldsize, newsize));
        }

        /*
         * Block is to be expanded.  Look for adjacent free memory.
         */
        if ( oldneighbor < (Dblk)_ubound ) {
                /*
                 * Search for the adjacent block in the free
                 * space tree.  Note that the tree may have been
                 * modified in the earlier loop.
                 */
                fpp = &_root;
                fp = *fpp;
                oldneighborsize = oldneighbor->size;
                if ( badblksize(oldneighbor, oldneighborsize) ) {
                        error("realloc: bad blocksize(%d) at %#x\n",
                                oldneighborsize, oldneighbor);
                        return(NULL);
                }
                while ( weight(fp) >= oldneighborsize ) {
                        freeblk = fp->block;
                        if (oldneighbor < freeblk) {
                                /*
                                 * search to the left
                                 */
                                fpp = &(fp->left);
                                fp = *fpp;
                        }
                        else if (oldneighbor > freeblk) {
                                /*
                                 * search to the right
                                 */
                                fpp = &(fp->right);
                                fp = *fpp;
                        }
                        else {          /* oldneighbor == freeblk */
                                /*
                                 * neighboring block is free; is it big enough?
                                 */
                                if (oldsize + oldneighborsize >= newsize) {
                                        /*
                                         * Big enough. Delete freeblk, join
                                         * oldblk to neighbor, return newsize
                                         * bytes to the caller, and return the
                                         * remainder to free storage.
                                         */
                                        delete(fpp);

                                        /* maintain statistics */
                                        __mallinfo.ordblks--;
                                        __mallinfo.uordbytes += oldneighborsize;

                                        oldsize += oldneighborsize;
                                        oldblk->size = oldsize;
                                        return(shrink(oldblk, oldsize, newsize));
                                } else {
                                        /*
                                         * Not big enough. Stop looking for a
                                         * free lunch.
                                         */
                                        break;
                                } /*else*/
                        } /*else*/
                }/*while*/
        } /*if*/

        /*
         * At this point, we know there is no free space in which to
         * expand. Malloc a new block, copy the old block to the new,
         * and free the old block, IN THAT ORDER.
         */
        ptr = malloc(nbytes);
        if (ptr != NULL) {
                bcopy(oldblk->data, ptr, oldsize-ALIGNSIZ);
                free(oldblk->data);
        }
        return(ptr);

} /* realloc */


/*
 * *** The following code was pulled out of realloc() ***
 *
 * int
 * reclaim(oldblk, oldsize, flag)
 *      If a block containing 'oldsize' bytes from 'oldblk'
 *      is in the free list, remove it from the free list.
 *      'oldblk' and 'oldsize' are assumed to include the free block header.
 *
 *      Returns 1 if block was successfully removed.
 *      Returns 0 if block was not in free list.
 *      Returns -1 if block spans a free/allocated boundary (error() called
 *                                              if 'flag' == 1).
 */
static int
reclaim(Dblk oldblk, uint oldsize, int flag)
{
        Dblk oldneighbor;
        Freehdr *fpp;
        Freehdr fp;
        Dblk            freeblk;
        uint            size;

        /*
         * Search the free space list for a node describing oldblk,
         * or a node describing a block containing oldblk.  Assuming
         * the size of blocks decreases monotonically with depth in
         * the tree, the loop may terminate as soon as a block smaller
         * than oldblk is encountered.
         */

        oldneighbor = nextblk(oldblk, oldsize);

        fpp = &_root;
        fp = *fpp;
        while ( (size = weight(fp)) >= oldsize ) {
                freeblk = fp->block;
                if (badblksize(freeblk,size)) {
                        error("realloc: bad block size (%d) at %#x\n",
                                size, freeblk);
                        return(-1);
                }
                if ( oldblk == freeblk ) {
                        /*
                         * |<-- freeblk ...
                         * _________________________________
                         * |<-- oldblk ...
                         * ---------------------------------
                         * Found oldblk in the free space tree; delete it.
                         */
                        delete(fpp);

                        /* maintain statistics */
                        __mallinfo.uordbytes += oldsize;
                        __mallinfo.allocated++;
                        return(1);
                }
                else if (oldblk < freeblk) {
                        /*
                         *              |<-- freeblk ...
                         * _________________________________
                         * |<--oldblk ...
                         * ---------------------------------
                         * Search to the left for oldblk
                         */
                        fpp = &fp->left;
                        fp = *fpp;
                }
                else { 
                        /*
                         * |<-- freeblk ...
                         * _________________________________
                         * |                    |<--oldblk--->|<--oldneighbor
                         * ---------------------------------
                         * oldblk is somewhere to the right of freeblk.
                         * Check to see if it lies within freeblk.
                         */
                        Dblk freeneighbor;
                        freeneighbor =  nextblk(freeblk, freeblk->size); 
                        if (oldblk >= freeneighbor) {
                                /*
                                 * |<-- freeblk--->|<--- freeneighbor ...
                                 * _________________________________
                                 * |                  |<--oldblk--->|
                                 * ---------------------------------
                                 * no such luck; search to the right.
                                 */
                                fpp =  &fp->right;
                                fp = *fpp;
                        }
                        else { 
                                /*
                                 * freeblk < oldblk < freeneighbor;
                                 * i.e., oldblk begins within freeblk.
                                 */
                                if (oldneighbor > freeneighbor) {
                                        /*
                                         * |<-- freeblk--->|<--- freeneighbor
                                         * _________________________________
                                         * |     |<--oldblk--->|<--oldneighbor
                                         * ---------------------------------
                                         * oldblk straddles a block boundary!
                                         */
                                        if (flag) {
            error("realloc: block %#x straddles free block boundary\n", oldblk);
                                        }
                                        return(-1);
                                }
                                else if (  oldneighbor == freeneighbor ) {
                                        /*
                                         * |<-------- freeblk------------->|
                                         * _________________________________
                                         * |                 |<--oldblk--->|
                                         * ---------------------------------
                                         * Oldblk is on the right end of
                                         * freeblk. Delete freeblk, split
                                         * into two fragments, and return
                                         * the one on the left to free space.
                                         */
                                        delete(fpp);

                                        /* maintain statistics */
                                        __mallinfo.ordblks++;
                                        __mallinfo.uordbytes += oldsize;
                                        __mallinfo.allocated += 2;

                                        freeblk->size -= oldsize;
                                        free(freeblk->data);
                                        return(1);
                                }
                                else {
                                        /*
                                         * |<-------- freeblk------------->|
                                         * _________________________________
                                         * |        |oldblk  | oldneighbor |
                                         * ---------------------------------
                                         * Oldblk is in the middle of freeblk.
                                         * Delete freeblk, split into three
                                         * fragments, and return the ones on
                                         * the ends to free space.
                                         */
                                        delete(fpp);

                                        /* maintain statistics */
                                        __mallinfo.ordblks += 2;
                                        __mallinfo.uordbytes += freeblk->size;
                                        __mallinfo.allocated += 3;

                                        /*
                                         * split the left fragment by
                                         * subtracting the size of oldblk
                                         * and oldblk's neighbor
                                         */
                                        freeblk->size -=
                                                ( (char*)freeneighbor
                                                        - (char*)oldblk );
                                        /*
                                         * split the right fragment by
                                         * setting oldblk's neighbor's size
                                         */
                                        oldneighbor->size = 
                                                (char*)freeneighbor
                                                        - (char*)oldneighbor;
                                        /*
                                         * return the fragments to free space
                                         */
                                        free(freeblk->data);
                                        free(oldneighbor->data);
                                        return(1);
                                } /*else*/
                        } /*else*/
                } /* else */
        } /*while*/

        return(0);              /* free block not found */
}

/*
 * bool
 * morecore(nbytes)
 *      Add a block of at least nbytes from end-of-memory to the
 *      free space tree.
 *
 * return value:
 *      true    if at least n bytes can be allocated
 *      false   otherwise
 *
 * remarks:
 *
 *   -- free space (delimited by the extern variable _ubound) is 
 *      extended by an amount determined by rounding nbytes up to
 *      a multiple of the system page size.
 *
 *   -- The lower bound of the heap is determined the first time
 *      this routine is entered. It does NOT necessarily begin at
 *      the end of static data space, since startup code (e.g., for
 *      profiling) may have invoked sbrk() before we got here. 
 */

static bool
morecore(uint nbytes)
{
        Dblk p;
        Freehdr newhdr;

        if (nbpg == 0) {
                nbpg = getpagesize();
                /* hack to avoid fragmenting the heap with the first
                   freehdr page */
                if ((newhdr = getfreehdr()) == NIL) {
                        /* Error message returned by getfreehdr() */
                        return(false);
                }
                (void)putfreehdr(newhdr);
        }
        nbytes = roundup(nbytes, nbpg);
        p = (Dblk) sbrk((int)nbytes);
        if (p == (Dblk) -1) {
                if (errno == EAGAIN) errno = ENOMEM;
                return(false);  /* errno = ENOMEM */
        }
        if (_lbound == NULL)    /* set _lbound the first time through */
                _lbound = (char*) p;
        _ubound = (char *) p + nbytes;
        p->size = nbytes;

        /* maintain statistics */
        __mallinfo.arena = _ubound - _lbound;
        __mallinfo.uordbytes += nbytes;
        __mallinfo.ordblks++;
        __mallinfo.allocated++;

        free(p->data);
        return(true);

} /*morecore*/


/*
 * Get a free block header from the free header list.
 * When the list is empty, allocate an array of headers.
 * When the array is empty, allocate another one.
 * When we can't allocate another array, we're in deep weeds.
 */
static  Freehdr
getfreehdr(void)
{
        Freehdr r;
        Dblk    blk;
        uint    size;

        if (freehdrlist != NIL) {
                r = freehdrlist;
                freehdrlist = freehdrlist->left;
                return(r);
        }
        if (nfreehdrs <= 0) {
                size = NFREE_HDRS*sizeof(struct freehdr) + ALIGNSIZ;
                blk = (Dblk) sbrk(size);
                if ((int)blk == -1) {
                        malloc_debug(1);
                        error("getfreehdr: out of memory");
                        if (errno == EAGAIN) errno = ENOMEM;
                        return(NIL);
                }
                if (_lbound == NULL)    /* set _lbound on first allocation */
                        _lbound = (char*)blk;
                blk->size = size;
                freehdrptr = (Freehdr)blk->data;
                nfreehdrs = NFREE_HDRS;
                _ubound = (char*) nextblk(blk,size);

                /* maintain statistics */
                __mallinfo.arena = _ubound - _lbound;
                __mallinfo.treeoverhead += size;
        }
        nfreehdrs--;
        return(freehdrptr++);
}

/*
 * Free a free block header
 * Add it to the list of available headers.
 */
static void
putfreehdr(Freehdr p)
{
        p->left = freehdrlist;
        freehdrlist = p;
}

#ifndef DEBUG   /*      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */

/*
 * stubs for error handling and diagnosis routines. These are what
 * you get in the standard C library; for non-placebo diagnostics
 * load /usr/lib/malloc.debug.o with your program.
 */
/*ARGSUSED*/
static void
error(char *fmt, ...)
{
        errno = EINVAL;
}

#endif  /* !DEBUG       <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */


#ifdef  DEBUG   /*      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */

/*
 * malloc_debug(level)
 *
 * description:
 *
 *      Controls the level of error diagnosis and consistency checking
 *      done by malloc() and free(). level is interpreted as follows:
 *
 *      0:  malloc() and free() return 0 if error detected in arguments
 *          (errno is set to EINVAL)
 *      1:  malloc() and free() abort if errors detected in arguments
 *      2:  same as 1, but scan entire heap for errors on every call
 *          to malloc() or free()
 *
 * function result:
 *      returns the previous level of error reporting.
 */
int
malloc_debug(int level)
{
        int old_level;
        old_level = debug_level;
        debug_level = level;
        return (old_level);
}

/*
 * check a free space tree pointer. Should be in
 * the static free pool or somewhere in the heap.
 */

#define chkblk(p)\
        if ( misaligned(p)\
                || ((Dblk)(p) < (Dblk)_lbound || (Dblk)(p) > (Dblk)_ubound)){\
                blkerror(p);\
                return 0;\
        }

#define chkhdr(p) chkblk(p)

static
blkerror(Freehdr p)
{
        error("Illegal block address (%#x)\n", (p));
}

/*
 * cartesian(p)
 *      returns 1 if free space tree p satisfies internal consistency
 *      checks.
 */

static int
cartesian(Freehdr p)
{
        Freehdr probe;
        Dblk db,pdb;

        if (p == NIL)                           /* no tree to test */
                return 1;
        /*
         * check that root has a data block
         */
        chkhdr(p);
        pdb = p->block;
        chkblk(pdb);

        /*
         * check that the child blocks are no larger than the parent block.
         */
        probe = p->left;
        if (probe != NIL) {
                chkhdr(probe);
                db = probe->block;
                chkblk(db);
                if (probe->size > p->size)      /* child larger than parent */
                        return 0;
        }
        probe = p->right;
        if (probe != NIL) {
                chkhdr(probe);
                db = probe->block;
                chkblk(db);
                if (probe->size > p->size)      /* child larger than parent */
                        return 0;
        }
        /*
         * test data addresses in the left subtree,
         * starting at the left subroot and probing to
         * the right.  All data addresses must be < p->block.
         */
        probe = p->left;
        while (probe != NIL) {
                chkhdr(probe);
                db = probe->block;
                chkblk(db);
                if ( nextblk(db, probe->size) >= pdb )  /* overlap */
                        return 0;
                probe = probe->right;
        }
        /*
         * test data addresses in the right subtree,
         * starting at the right subroot and probing to
         * the left.  All addresses must be > nextblk(p->block).
         */
        pdb = nextblk(pdb, p->size);
        probe = p->right;
        while (probe != NIL) {
                chkhdr(probe);
                db = probe->block;
                chkblk(db);
                if (db == NULL || db <= pdb)            /* overlap */
                        return 0;
                probe = probe->left;
        }
        return (cartesian(p->left) && cartesian(p->right));
}

/*
 * malloc_verify()
 *
 * This is a verification routine.  It walks through all blocks
 * in the heap (both free and busy) and checks for bad blocks.
 * malloc_verify returns 1 if the heap contains no detectably bad
 * blocks; otherwise it returns 0.
 */

int
malloc_verify(void)
{
        int     maxsize;
        int     hdrsize;
        int     size;
        Dblk    p;
        uint    lb,ub;

        extern  char    end[];

        if (_lbound == NULL)    /* no allocation yet */
                return 1;

        /*
         * first check heap bounds pointers
         */
        lb = (uint)end;
        ub = (uint)sbrk(0);

        if ((uint)_lbound < lb || (uint)_lbound > ub) {
                error("malloc_verify: illegal heap lower bound (%#x)\n",
                        _lbound);
                return 0;
        }
        if ((uint)_ubound < lb || (uint)_ubound > ub) {
                error("malloc_verify: illegal heap upper bound (%#x)\n",
                        _ubound);
                return 0;
        }
        maxsize = heapsize();
        p = (Dblk)_lbound;
        while (p < (Dblk) _ubound) {
                size = p->size;
                if ( (size) < SMALLEST_BLK 
                        || (size) & (ALIGNSIZ-1)
                        || (size) > heapsize()
                        || ((char*)(p))+(size) > _ubound ) {
                        error("malloc_verify: bad block size (%d) at %#x\n",
                                size, p);
                        return(0);              /* Badness */
                }
                p = nextblk(p, size);
        }
        if (p > (Dblk) _ubound) {
                error("malloc_verify: heap corrupted\n");
                return(0);
        }
        if (!cartesian(_root)){
                error("malloc_verify: free space tree corrupted\n");
                return(0);
        }
        return(1);
}

/*
 * The following is a kludge to avoid dependency on stdio, which
 * uses malloc() and free(), one of which probably got us here in
 * the first place.
 */

#define putchar(c) (*buf++ = (c))
extern  int     fileno();       /*bletch*/
#define stderr 2                /*bletch*/
#define LBUFSIZ 256

static  char    stderrbuf[LBUFSIZ];

/*
 * Error routine.
 * If debug_level == 0, does nothing except set errno = EINVAL.
 * Otherwise, prints an error message to stderr and generates a
 * core image.
 */
static void
error(char *fmt, ...)
{
        static int n = 0; /* prevents infinite recursion when using stdio */
        int nbytes;
        va_list ap;

        errno = EINVAL;
        if (debug_level == 0)
                return;
        if (!n++) {
                va_start(ap, fmt);
                nbytes = vsprintf(stderrbuf, fmt, ap);
                va_end(ap);
                stderrbuf[nbytes++] = '\n';
                stderrbuf[nbytes] = '\0';
                write(fileno(stderr), stderrbuf, nbytes);
        }
        abort();
}

#endif  /* DEBUG        <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */