sbm.c

操作系统源代码

/* SB - Copyright 1982 by Ken Harrenstien, SRI International
 *	This software is quasi-public; it may be used freely with
 *	like software, but may NOT be sold or made part of licensed
 *	products without permission of the author.  In all cases
 *	the source code and any modifications thereto must remain
 *	available to any user.
 *
 *	This is part of the SB library package.
 *	Any software using the SB library must likewise be made
 *	quasi-public, with freely available sources.
 */

#if 0
	This file contains the low-level memory allocation
subroutines which are used by the SBLK routines.  The code here
is quite machine-dependent, and the definitions in "sb.h" should be
carefully checked to verify that they are correct for the target
machine.

	The ultimate low-level routine is "sbrk()" which must be
provided by the system''s C library.  SBM expects that successive calls
to sbrk() will return contiguous areas of memory with progressively
higher addresses.  Also, the very first call to sbrk() is assumed to
return a word-aligned address.
#endif /*COMMENT*/

#include "sb.h"

#define FUDGE (sizeof(struct smblk))	/* Allow this much fudge in
				allocation, to prevent undue fragmentation */

char *(*sbm_debug)();           /* Debug switch - user-furnished routine */

struct smblk *sbm_nfl;          /* Pointer to node freelist */
struct smblk *sbm_nxtra;	/* Reserved extra free node */
struct smblk *sbm_list;         /* Pointer to smblk memory alloc list.
				 * ALL smblks are strung onto this list
				 * except for the freelist!
				 */
SBMA sbm_lowaddr;		/* Lowest word-aligned address we know about.*/

/* If compiling with debug switch set, use special routine in place of
 * sbrk so we can pretend we have a very limited area of free memory.
 */
#ifdef DBG_SIZE
#define SBM_SBRK sbm_brk
char *sbm_brk();
#else
#define SBM_SBRK sbrk
#endif /*DBG_SIZE*/

/* Forward routine declarations */
char *sbrk();
struct smblk *sbm_nmak(), *sbm_nget(), *sbm_mget(), *sbm_split();
struct smblk *sbm_lmak(), *sbm_err();

/* SBM_INIT - Initialize storage management.
 *	If args are zero, normal initialization is done.  Otherwise,
 *	args are understood to be pointers to an area of memory allocated
 *	on the stack (eg by an "int mem[2000]" declaration in MAIN) and
 *	initialization will include this area in addition to the
 *	unused space between "_end" and the start of the stack segment.
 *	This is mostly of use for PDP11s which would otherwise waste a lot
 *	of address space.
 *	Maybe should have a SBM_RESET() function?
 */

struct smblk *
sbm_init(xaddr,xlen)
SBMA xaddr;		/* Address of allocated stack area if any */
SBMO xlen;		/* Size of this area */
{       register struct smblk *sm, *sml;
	register char *cp;

	/* Get initial chunk of memory from standard system rtn */
	if((cp = SBM_SBRK(SMNODES*sizeof(struct smblk))) == 0
	  || (int) cp == -1)
		return(sbm_err(0,"Can't sbrk"));
	sm = (struct smblk *)cp;		/* Better be word-aligned! */
	sbm_lmak(sm,(SBMO)sizeof(struct smblk),SMNODES);      /* Make list */
	sbm_nfl = sm;				/* Point freelist at it */
	sbm_lowaddr = (SBMA)sm;			/* Remember lowest addr seen */

	/* Set up 1st node pointing to all memory from here on up.
	 * We don't know exactly how much will be available at this point,
	 * so we just pretend we have the maximum possible.
	 */
	sbm_list = sml = sbm_nget();
	sml->smforw = sml->smback = 0;
	sml->smflags = SM_USE|SM_NID;		/* Initial flags */
	sml->smaddr = (SBMA) sml;
	sml->smlen = MAXSBMO;			/* Pretend we have lots */
	sml->smuse = (SMNODES * sizeof(struct smblk));

	/* Now split off everything above initial allocation as NXM. */
	sm = sbm_split(sml, sm->smuse);
	sml->smflags |= SM_MNODS;	/* Mark 1st node as having SM nodes */
	sm->smflags  |= SM_NXM;		/* Mark 2nd node as NXM */

	/* Now possibly set up extra nodes, if stack mem is being allocated
	 * (From our viewpoint it looks as if a chunk in the middle of
	 * the initial NXM section has been declared usable)
	 */
	if(xlen)
	  {     /* Allow for "extra" static stack memory */
		/* Will lose if xaddr <= 1st NXM! */
		sml = sbm_split(sm, (SBMO)(xaddr - sm->smaddr));
		sbm_split(sml, xlen);		/* Split off following NXM */
		sml->smflags &= ~(SM_USE|SM_NXM); /* This node is free mem! */
	  }

	/* Now set up a small additional node which points to the NXM
	 * that we cannot get from SBRK.  At this stage, this is just
	 * a place-holder, to reserve the node so we don't have to
	 * worry about running out of nodes at the same time sbrk stops
	 * returning memory.
	 * SM points to the NXM that we expect SBRK to dig into.
	 */
	sbm_split(sm, sm->smlen - WDSIZE); /* Chop off teensy bit */
	sm->smflags &= ~SM_USE;		/* Now mark NXM "free"!! */

	/* Finally, reserve an "extra" SM node for use by sbm_nget
	 * when it is allocating more freelist node chunks.
	 */
	sbm_nxtra = sbm_nget();

	return(sbm_list);
}

/* SBM_NGET() - Get a free SM node.
 *	Note the hair to provide a spare SM node when
 *	we are allocating memory for more SM nodes.  This is necessary
 *	because sbm_mget and sbm_nget call each other recursively and
 *	sbm_mget cannot create any new memory without a SM node to point
 *	at the allocated chunk.
 */
struct smblk *
sbm_nget()
{       register struct smblk *sm, *sml;

	if(!(sm = sbm_nfl))		/* Get a node from freelist */
	  {	/* Freelist is empty, try to allocate more nodes. */

		/* Put our "spare" smblk on freelist temporarily so that
		 * sbm_mget has a chance of winning.
		 * Infinite recursion is avoided by a test
		 * in sbm_mget which checks sbm_nfl and sbm_nxtra.
		 */
		if(!(sm = sbm_nxtra))
			return(sbm_err(0,"Zero sbm_nxtra!"));
		sm->smforw = 0;
		sbm_nfl = sm;
		sbm_nxtra = 0;

		/* Try to allocate another chunk of SM nodes. */
		sml = sbm_nmak(sizeof(struct smblk),SM_MNODS);

		/* Put the new free nodes (if any) on freelist.
		 * Done this way because freelist may have had one or two
		 * nodes added to it by sbm_mget, so can't just stick
		 * a new pointer in sbm_nfl.
		 */
		while(sm = sml)
		  {	sml = sm->smforw;
			sbm_nfre(sm);
		  }

		/* Now reserve an extra node again.
		 * It is an error if there is nothing on freelist here,
		 * because even if sbm_mget failed the "extra node" should
		 * still be on freelist.  The check for a zero sbm_nxtra
		 * above will catch such an error.
		 */
		sbm_nxtra = sbm_nget();

		/* Now see if anything to return */
		if(!(sm = sbm_nfl))		/* If freelist empty again, */
			return(0);		/* give up. */
	  }
	sbm_nfl = sm->smforw;   /* If win, take it off freelist */
	return(sm);		/* Return ptr or 0 if none */
}

/* SBM_NFRE(sm) - Return a SM node to the SM freelist.
 */
sbm_nfre(smp)
struct smblk *smp;
{       register struct smblk *sm;
	(sm = smp)->smflags = 0;
	sm->smforw = sbm_nfl;
	sbm_nfl = sm;
}

/* SBM_NMAK(elsize, flag) - Make (allocate & build) a typeless node freelist.
 */
struct smblk *
sbm_nmak(elsize, flag)
SBMO elsize;
unsigned flag;
{       register struct smblk *sm, *smp;
	register int cnt;

	if((sm = sbm_mget(SMNODES*elsize,SMNODES*elsize)) == 0)
		return(0);

	sm->smflags |= flag;            /* Indicate type of nodes */
	cnt = sm->smlen/elsize;		/* Find # nodes that will fit */
	sm->smuse = cnt * elsize;	/* Actual size used */
	smp = (struct smblk *)(sm->smaddr);	/* Ptr to 1st loc of mem */
	sbm_lmak(smp, (SBMO)elsize, cnt);	/* Build freelist */
	return(smp);            /* Return 1st free node. Caller is */
				/* responsible for setting freelist ptr. */
}

/* SBM_LMAK - Build freelist of typeless nodes.
 *	Note this does not allocate memory, it just converts an already
 *	allocated memory area.
 */
struct smblk *
sbm_lmak(addr, elsize, num)
SBMA addr;
SBMO elsize;
int num;
{	register struct smblk *sm, *smp;
	register int cnt;

	smp = (struct smblk *) addr;
	if((cnt = num) <= 0)
		return(0);
	do {	sm = smp;       /* Save ptr */
		sm->smforw = (smp = (struct smblk *) ((SBMA)smp + elsize));
		sm->smflags = 0;
	  } while(--cnt);
	sm->smforw = 0;         /* Last node points to nothing */
	return(sm);		/* Return ptr to last node */
}

/* SBM_NMOV(sm1, sm2, begp, elsize) - Move a typeless node.
 *	Copy sm1 to sm2, adjust ptrs, leave sm1 free.
 */
sbm_nmov(smp1,smp2,begp,elsize)
struct smblk *smp1, *smp2, **begp;
int elsize;
{       register struct smblk *sm;

	bcopy((SBMA)smp1,(SBMA)(sm = smp2), elsize);     /* Copy the stuff */
	if(sm->smforw) sm->smforw->smback = sm; /* Fix up links */
	if(sm->smback) sm->smback->smforw = sm;
	else *begp = sm;
}

/* SBM_MGET(min,max) - Get a SMBLK with specified amount of memory.
 *      Returns 0 if none available.
 *      Memory is guaranteed to start on word boundary, but may not
 *              end on one.  Note that sbm_mfree is responsible for
 *              ensuring that free mem starts word-aligned.
 *	A subtle but major concern of this code is the number of freelist
 * nodes gobbled by a single call.  If the freelist happens to not have
 * enough nodes, then a recursive call to sbm_mget is made (via sbm_nget)
 * in order to allocate a new batch of freelist nodes!  sbm_nget will
 * always provide a single "spare" node during such an allocation, but
 * there is only one and it is essential that sbm_mget gobble only ONE
 * (if any) during such a call, which is indicated by sbm_nxtra==0.
 *	The maximum # of freelist nodes that sbm_mget can gobble is
 * 2, when (1) NXM memory is obtained, and a SM is needed to point at
 * the new free mem, plus (2) the resulting SM is too big, and has to
 * be split up, which requires another SM for the remainder.
 *	The "used-NXM" smblk is set up at init time precisely in order to
 * avoid the necessity of creating it here when sbrk stops winning, since
 * that would require yet another freelist node and make it possible for
 * sbm_mget to gobble 3 during one call -- too many.
 *	Further note: the sbm_nfl checks are necessary in order
 * to ensure that a SM node is available for use by sbm_split.  Otherwise
 * the calls to sbm_split might create a new SM freelist by gobbling the
 * very memory which we are hoping to return!
 */
SBMO sbm_chksiz = SMCHUNKSIZ;	/* Current chunk size to feed sbrk */

struct smblk *
sbm_mget(cmin,cmax)
SBMO cmin,cmax;
{       register struct smblk *sm, *sml;
	register SBMO csiz;
	register SBMA addr, xaddr;

	if((sm = sbm_list) == 0         /* If never done, */
	  && (sm = sbm_init((SBMA)0,(SBMO)0)) == 0)	/* initialize mem alloc stuff. */
		return(0);		/* Can't init??? */

	/* Round up sizes to word boundary */
	if(rndrem(cmin)) cmin = rndup(cmin);
	if(rndrem(cmax)) cmax = rndup(cmax);

	/* Search for a free block having enough memory.
	 * If run into a free-NXM block, always "win", since there may be
	 * a combination of preceding free-mem and new mem which will satisfy
	 * the request.  If it turns out this didn't work, we'll just fail
	 * a little farther on.
	 */
retry:	csiz = cmin;			/* Set size that will satisfy us */
	do {
		if(  ((sm->smflags&SM_USE) == 0)
		  && ((sm->smlen >= csiz) || (sm->smflags&SM_NXM)) )
			break;
	  } while(sm = sm->smforw);
	if(sm == 0)