malloc.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

#ifndef lint
static	char	*sccsid = "@(#)malloc.c	4.1	(ULTRIX)	7/2/90";
#endif lint

/************************************************************************
 *									*
 *			Copyright (c) 1985 by				*
 *		Digital Equipment Corporation, Maynard, MA		*
 *			All rights reserved.				*
 *									*
 *   This software is furnished under a license and may be used and	*
 *   copied  only  in accordance with the terms of such license and	*
 *   with the  inclusion  of  the  above  copyright  notice.   This	*
 *   software  or  any  other copies thereof may not be provided or	*
 *   otherwise made available to any other person.  No title to and	*
 *   ownership of the software is hereby transferred.			*
 *									*
 *   This software is  derived  from  software  received  from Bell	*
 *   Laboratories.  Use, duplication, or disclosure is  subject  to	*
 *   restrictions  under  license  agreements  with  AT&T.		*
 *									*
 *   The information in this software is subject to change  without	*
 *   notice  and should not be construed as a commitment by Digital	*
 *   Equipment Corporation.						*
 *									*
 *   Digital assumes no responsibility for the use  or  reliability	*
 *   of its software on equipment which is not supplied by Digital.	*
 *									*
 ************************************************************************/
/************************************************************************
 *			Modification History
 *
 *	David L Ballenger, 29-May-1985
 * 001	Include <stdio.h> to resolve references to stderr.
 *
 ************************************************************************/



#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include "mallint.h"

/*     use level memory allocater (malloc, free, realloc)

	-malloc, free, realloc and mallopt form a memory allocator
	similar to malloc, free, and realloc.  The routines
	here are much faster than the original, with slightly worse
	space usage (a few percent difference on most input).  They
	do not have the property that data in freed blocks is left
	untouched until the space is reallocated.

	-Memory is kept in the "arena", a singly linked list of blocks.
	These blocks are of 3 types.
		1. A free block.  This is a block not in use by the
		   user.  It has a 3 word header. (See description
		   of the free queue.)
		2. An allocated block.  This is a block the user has
		   requested.  It has only a 1 word header, pointing
		   to the next block of any sort.
		3. A permanently allocated block.  This covers space
		   aquired by the user directly through sbrk().  It
		   has a 1 word header, as does 2.
	Blocks of type 1 have the lower bit of the pointer to the
	nextblock = 0.  Blocks of type 2 and 3 have that bit set,
	to mark them busy.

	-Unallocated blocks are kept on an unsorted doubly linked
	free list.  

	-Memory is allocated in blocks, with sizes specified by the
	user.  A circular first-fit startegy is used, with a roving
	head of the free queue, which prevents bunching of small
	blocks at the head of the queue.

	-Compaction is performed at free time of any blocks immediately
	following the freed block.  The freed block will be combined
	with a preceding block during the search phase of malloc.
	Since a freed block is added at the front of the free queue,
	which is moved to the end of the queue if considered and
	rejected during the search, fragmentation only occurs if
	a block with a contiguious preceding block that is free is
	freed and reallocated on the next call to malloc.  The
	time savings of this strategy is judged to be worth the
	occasional waste of memory.

	-Small blocks (of size < MAXSIZE)  are not allocated directly.
	A large "holding" block is allocated via a recursive call to
	malloc.  This block contains a header and ?????? small blocks.
	Holding blocks for a given size of small block (rounded to the
	nearest ALIGNSZ bytes) are kept on a queue with the property that any
	holding block with an unused small block is in front of any without.
	A list of free blocks is kept within the holding block.
*/

#ifndef debug
#       define  NDEBUG
#endif
 

/*
	description of arena, free queue, holding blocks etc.
*/
static struct header arena[2];  /* the second word is a minimal block to
				   start the arena. The first is a busy
				   block to be pointed to by the last
				   block.       */
static struct header freeptr[2];/* first and last entry in free list */
static struct header *arenaend; /* ptr to block marking high end of arena */
static struct header *lastblk;  /* the highest block in the arena */
static struct holdblk **holdhead; /* pointer to array of head pointers
				     to holding block chains */
/* In order to save time calculating indices, the array is 1 too
   large, and the first element is unused */
/* 
	Variables controlling algorithm, esp. how holding blocs are
	used
*/
static int numlblks = NUMLBLKS;
static int minhead = MINHEAD;	
static int change = 0;		  /* != 0, once param changes
				     are no longer allowed */
static int fastct = FASTCT;
static int maxfast = MAXFAST;
/* number of small block sizes to map to one size */
static int grain = ALIGNSZ;

/*
	malloc(nbytes) - give a user nbytes to use
*/
void *
malloc(nbytes)
unsigned nbytes;
{
	register struct header *blk;
	register unsigned nb;      /* size of entire block we need */
	char *sbrk();

	/*      on first call, initialize       */
	if (freeptr->nextfree == GROUND) {

		/* initialize arena */
		arena[1].nextblk = (struct header *)BUSY;
		arena[0].nextblk = (struct header *)BUSY;
		lastblk = arenaend = &(arena[1]);
		/* initialize free queue */
		freeptr[0].nextfree = &(freeptr[1]);
		freeptr[1].nextblk = &(arena[0]);
		freeptr[1].prevfree = &(freeptr[0]);
		/* mark that small blocks not init yet */
	}
	if (nbytes == 0) return NULL;
	if (nbytes <= maxfast)  {
		/*
			We can allocate out of a holding block
		*/
		register struct holdblk *holdblk; /* head of right sized queue*/
		register struct lblk *lblk;     /* pointer to a little block */
		register struct holdblk *newhold;

		if (!change)  {
			register int i;
			/*
				This allocates space for hold block
				pointers by calling malloc recursively.
				Maxfast is temporarily set to 0, to
				avoid infinite recursion.  allocate
				space for an extra ptr so that an index
				is just ->blksz/grain, with the first
				ptr unused.
			*/
			change = 1;	/* change to algorithm params
					   no longer allowed */
			/* temporarily alter maxfast, to avoid
			   infinite recursion */
			maxfast = 0;
			holdhead = (struct holdblk **)
				   malloc(sizeof(struct holdblk *)*
				   (fastct + 1));
			for(i=1; i<fastct+1; i++)  {
				holdhead[i] = HGROUND;
			}
			maxfast = fastct*grain;
		}
		/*  Note that this uses the absolute min header size (MINHEAD)
		    unlike the large block case which uses minhead */
		/* round up to nearest multiple of grain */
		nb = (nbytes + grain - 1)/grain*grain;      /* align */
		holdblk = holdhead[nb/grain];
		nb = nb + MINHEAD;
		/*      look for space in the holding block.  Blocks with
			space will be in front of those without */
		if ((holdblk != HGROUND) && (holdblk->lfreeq != LGROUND))  {
			/* there is space */
			lblk = holdblk->lfreeq;
			/* Now make lfreeq point to a free block.
			   If lblk has been previously allocated and 
			   freed, it has a valid pointer to use.
			   Otherwise, lblk is at the beginning of
			   the unallocated blocks at the end of
			   the holding block, so, if there is room, take
			   the next space.  If not, mark holdblk full,
			   and move holdblk to the end of the queue
			*/
			if(lblk < holdblk->unused)  {
				/* move to next holdblk, if this one full */
				if((holdblk->lfreeq = 
				  CLRSMAL(lblk->header.nextfree)) == LGROUND) {
					holdhead[(nb-MINHEAD)/grain] =
							holdblk->nexthblk;
				}
			}  else  if (((char *)holdblk->unused + nb) <
				    ((char *)holdblk + HOLDSZ(nb)))  {
				holdblk->unused = (struct lblk *)
						 ((char *)holdblk->unused+nb);
				holdblk->lfreeq = holdblk->unused;
			}  else {
				holdblk->lfreeq = LGROUND;
				holdhead[(nb-MINHEAD)/grain] =
							holdblk->nexthblk;
			}
			/* mark as busy and small */
			lblk->header.holder = (struct holdblk *)SETALL(holdblk);
		}  else  {
			/* we need a new holding block */
			newhold = (struct holdblk *)
					malloc(HOLDSZ(nb));
			if ((char *)newhold == NULL)  {
				return NULL;
			}
			/* add to head of free queue */
			if (holdblk != HGROUND)  {
				newhold->nexthblk = holdblk;
				newhold->prevhblk = holdblk->prevhblk;
				holdblk->prevhblk = newhold;
				newhold->prevhblk->nexthblk = newhold;
			}  else  {
				newhold->nexthblk = newhold->prevhblk = newhold;
			}
			holdhead[(nb-MINHEAD)/grain] = newhold;
			/* set up newhold */
			lblk = (struct lblk *)(newhold->space);
			newhold->lfreeq = newhold->unused =
			     (struct lblk *)((char *)newhold->space+nb);
			lblk->header.holder= (struct holdblk *)SETALL(newhold);
			newhold->blksz = nb-MINHEAD;
		}
		return (char *)lblk + MINHEAD;
	}  else  {
		/*
			We need an ordinary block
		*/
		register struct header *newblk; /* used for creating a block */

		/* get number of bytes we need */
		nb = nbytes + minhead;
		nb = (nb + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ;	    /* align */
		nb = (nb > MINBLKSZ) ? nb : MINBLKSZ;
		/*
			see if there is a big enough block
			If none exists, you will get to freeptr[1].  
			freeptr[1].next = &arena[0], so when you do the test,
			the result is a large positive number, since arena[0]
			comes before all blocks.  Arena[0] is marked busy so
			that it will not be compacted.  This kludge is for the
			sake of the almighty efficiency.
		*/
		/*   check that a very large request won't cause an inf. loop */
		if ((freeptr[1].nextblk-&(freeptr[1])) < nb)  return NULL;
		{
		register struct header *next;  /* block following blk */
		register struct header *nextnext;  /* block after next*/

		blk = freeptr;
		do  {

			blk = blk->nextfree;
			/* see if we can compact */
			next = blk->nextblk;
			if (!TESTBUSY(nextnext = next->nextblk))  {
				do  {
					DELFREEQ(next);
					next = nextnext;
					nextnext = next->nextblk;
				}  while  (!TESTBUSY(nextnext));
				/* next will be at most == to lastblk, but I
				   think the >= test is faster */
				if (next >= arenaend)  lastblk = blk;
				blk->nextblk = next;
			}
		}  while (((char *)(next) - (char *)blk) < nb);
		}
		/* 
			if we didn't find a block, get more memory
		*/
		if (blk == &(freeptr[1]))  {
			register struct header *newend; /* new end of arena */
			register int nget;      /* number of words to get */

			/* Three cases - 1. There is space between arenaend
					    and the break value that will become
					    a permanently allocated block.
					 2. Case 1 is not true, and the last
					    block is allocated.
					 3. Case 1 is not true, and the last
					    block is free
			*/
			if ((newblk = (struct header *)sbrk(0)) != 
			   (struct header *)((char *)arenaend + HEADSZ))  {
				/* case 1 */
				/* get size to fetch */
				nget = nb+HEADSZ;
				/* round up to a block */
				nget = (nget+BLOCKSZ-1)/BLOCKSZ*BLOCKSZ;
				/* if not word aligned, get extra space */
				if ((int)newblk%ALIGNSZ != 0)  {
					nget += ALIGNSZ - (int)newblk%ALIGNSZ;
				}
#ifdef pdp11
				if (newblk + nget + 64 < newblk) {
					return NULL;
				}
#endif
				/* get memory */
				if ((struct header *)sbrk(nget) ==
				   (struct header *)-1) {
					return NULL;
				}
				/* add to arena */
				newend = (struct header *)((char *)newblk + nget
					 - HEADSZ);
				/*ignore some space to make block word aligned*/
				if ((int)newblk%ALIGNSZ != 0)  {
					newblk = (struct header *)
						 ((char *)newblk + ALIGNSZ -
						 (int)newblk%ALIGNSZ);
				}
				newend->nextblk = SETBUSY(&(arena[1]));
				newblk->nextblk = newend;
				arenaend->nextblk = SETBUSY(newblk);
				/* adjust other pointers */
				arenaend = newend;
				lastblk = newblk;
				blk = newblk;
			}  else  if (TESTBUSY(lastblk->nextblk))  {
				/* case 2 */
				nget = (nb+BLOCKSZ-1)/BLOCKSZ*BLOCKSZ;
#ifdef pdp11
				if (newblk + nget + 64 < newblk) {
					return NULL;
				}
#endif
				if(sbrk(nget) == (char *)-1)  {
					return NULL;
				}
				/* block must be word aligned */
				assert(((int)newblk%ALIGNSZ) == 0);
				newend =
				     (struct header *)((char *)arenaend+nget);
				newend->nextblk = SETBUSY(&(arena[1]));
				arenaend->nextblk = newend;
				lastblk = blk = arenaend;
				arenaend = newend;
			}  else  {
				/* case 3 */
				/* last block in arena is at end of memory and
				   is free */
				nget = nb - (lastblk - arenaend);
				nget = (nget+BLOCKSZ-1)/BLOCKSZ*BLOCKSZ;
#ifdef pdp11
				if (newblk + nget + 64 < newblk) {
					return NULL;
				}
#endif
				assert(((int)newblk%ALIGNSZ) == 0);
				if (sbrk(nget) == (char *)-1)  {
					return NULL;
				}
				/* combine with last block, put in arena */
				newend = (struct header *)((char *)arenaend +
					  nget);
				arenaend = lastblk->nextblk = newend;
				newend->nextblk = SETBUSY(&(arena[1]));
				/* set which block to use */
				blk = lastblk;
				DELFREEQ(blk);
			}
		}  else  {
			register struct header *nblk;      /* next block */

			/* take block found of free queue */