12292 retire libbc

Reviewed by: Peter Tribble <peter.tribble@gmail.com>
Reviewed by: Andy Stormont <astormont@racktopsystems.com>
Reviewed by: Alexander Eremin <aeremin@tintri.com>
Approved by: Garrett D'Amore <garrett@damore.org>

1 files changed, 0 insertions, 1444 deletions

diff --git a/usr/src/lib/libbc/libc/gen/common/malloc.c b/usr/src/lib/libbc/libc/gen/common/malloc.c
deleted file mode 100644
index 2d5891dd18..0000000000
--- a/usr/src/lib/libbc/libc/gen/common/malloc.c
+++ /dev/null
@@ -1,1444 +0,0 @@
-/*
- * 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	<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */