malloc.c

操作系统SunOS 4.1.3版本的源码

#if !defined(lint) && defined(SCCSIDS)
static	char sccsid[] = "@(#)malloc.c 1.1 92/07/30 SMI";
#endif

/*
 * Copyright (c) 1986 by Sun Microsystems, Inc.
 */

/*
 * 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>

/* system interface */

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

static	int	nbpg = 0;	/* set by calling getpagesize() */
static	bool	morecore();	/* 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();
static	putfreehdr();
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	error();	/* sets errno; prints msg and aborts if DEBUG is on */

#ifdef	DEBUG		>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

int	malloc_debug(/*level*/);
int	malloc_verify();
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).
 */

static
insert(newblk, len)
	register Dblk newblk;		/* Ptr to the block to insert */
	register uint len;		/* Length of new node */
{
	register Freehdr *fpp;		/* Address of ptr to subtree */
	register Freehdr x;
	register Freehdr *left_hook;	/* Temp for insertion */
	register Freehdr *right_hook;	/* Temp for insertion */
	register 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
delete(p)
	register Freehdr *p;
{
	register Freehdr x;
	register Freehdr left_branch;	/* left subtree of deleted node */
	register Freehdr right_branch;	/* right subtree of deleted node */
	register uint left_weight;
	register 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
demote(p)
	register Freehdr *p;
{
	register Freehdr x;		/* addr of node to be demoted */
	register Freehdr left_branch;
	register Freehdr right_branch;
	register uint	left_weight;
	register uint	right_weight;
	register 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(nbytes)
	register uint	nbytes;
{
	register Freehdr allocp;	/* ptr to node to be allocated */
	register Freehdr *fpp;		/* for tree modifications */
	register Freehdr left_branch;
	register Freehdr right_branch;
	register uint	 left_weight;
	register 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.
		 */
		register Dblk nblk;