sbstr.c

操作系统源代码

}


/* SBX_SCPY(sd,sdl) - Copies given sbstring, returns ptr to new sbstring.
 *	Only goes as far as sdl (last copied blk); 0 for entire sbstring.
 */
struct sdblk *
sbx_scpy(sdp,sdlast)
struct sdblk *sdp, *sdlast;
{	register struct sdblk *sd, *sd2, *sdn;
	struct sdblk *sdr;

	if((sd = sdp) == 0) return((struct sdblk *)0);
	sdn = 0;
	do {
		sd->sdflags |= SD_LCK2;
		sd2 = sbx_sdcpy(sd);
		if(sd2->slback = sdn)
		  {	sdn->slforw = sd2;
			sdn->sdflags &= ~SD_LOCKS;
		  }
		else sdr = sd2;		/* Save 1st */
		sdn = sd2;
		sd->sdflags &= ~SD_LCK2;
	  } while(sd != sdlast && (sd = sd->slforw));
	sd2->slforw = 0;
	sd2->sdflags &= ~SD_LOCKS;
	return(sdr);
}


/* SBX_SDCPY(sd) - Copies given sdblk, returns ptr to new blk.
 *	Does not set locks, assumes caller does this (which it MUST,
 *	to avoid compaction lossage!)
 */

struct sdblk *
sbx_sdcpy(sdp)
struct sdblk *sdp;
{	register struct sdblk *sd, *sd2;
	register struct smblk *sm, *sm2;

	if((sd = sdp) == 0) return((struct sdblk *)0);
	sd2 = sbx_ndget();		/* Get a free sdblk */
	bcopy((SBMA)sd, (SBMA)sd2, sizeof(struct sdblk));	/* Copy sdblk data */
	sd2->slforw = 0;		/* Don't let it think it's on a list */
	sd2->slback = 0;
	if(sd2->sdfile)			/* If has disk copy, */
	  {	sd->sdforw = sd2;	/* Fix phys list ptrs */
		sd2->sdback = sd;
		if(sd2->sdforw)
			sd2->sdforw->sdback = sd2;
	  }
	if(sm = sd2->sdmem)		/* If has in-core copy, try to */
	  {	if(sm2 = sbm_mget(sm->smuse,sm->smuse))	/* get mem for it */
		  {	bcopy(sm->smaddr,sm2->smaddr,sm->smuse);
			sm2->smuse = sm->smuse;
			sd2->sdmem = sm2;	/* Point new sd to copy */
		  }
		else				/* Can't get mem... */
		  {	if(sd2->sdflags&SD_MOD)
				sbx_aout(sd2,1);	/* Swap out the blk */
			sd2->sdmem = 0;		/* Don't have incore copy */
		  }
	  }
	return(sd2);
}

/* SBX_XCIS(sbp,coff,&sdp2,adot) - Internal routine to excise a sbstring,
 *	defined as everything between current location and given offset.
 *	SD to first sdblk is returned (0 if error)
 *	SD2 (address passed as 3rd arg) is set to last sdblk.
 *	Both are locked with LCK2 to ensure that pointers are valid.
 *	The current location at time of call is also returned via adot.
 */
struct sdblk *
sbx_xcis(sbp,num,asd2,adot)
SBBUF *sbp;
chroff num, *adot;
struct sdblk **asd2;
{	register SBBUF *sb;
	register struct sdblk *sd, *sd2;
	int dirb;

	if((sb = sbp) == 0) return((struct sdblk *)0);
	dirb = 0;		/* Delete forward */
	if(num == 0) return((struct sdblk *)0);	/* Delete nothing */
	if(num < 0) dirb++;	/* Delete backward */

	if((sd = (struct sdblk *)
			sbx_ready(sb, (dirb ? SK_DELB : SK_DELF))) == 0)
		return((struct sdblk *)0);		/* Maybe nothing there */
	sd->sdflags |= SD_LCK2;		/* Lock up returned SD */
	*adot = sb->sbdot;		/* Save current location */
	sb->sboff += num;		/* Move to other end of range */

	if((sd2 = (struct sdblk *)
			sbx_ready(sb,(dirb ? SK_DELF : SK_DELB))) == 0)
	  {	sd->sdflags &= ~SD_LCK2;	/* This shd never happen if */
		return(				/* we got this far, but...  */
		  (struct sdblk *)sbx_err(0,"KILLN SD2 failed"));
	  }
	sd2->sdflags |= SD_LCK2;	/* Lock up other end of stuff */

	/* SD and SD2 now delimit bounds of stuff to excise.
	 * Now do direction dependent fixups
	 */
	if(dirb)
	  {	/* Backward, current sbdot is ok but must get SD/SD2
		 * into first/last order.  Also, due to nature of block
		 * splitups, a backward delete within single block will leave
		 * SD actually pointing at predecessor block.
		 */
		if(sd->slforw == sd2)	/* If SD became pred, fix things. */
		  {	sd->sdflags &= ~SD_LCK2;	/* Oops, unlock! */
			sd = sd2;
		  }
		else	/* Just need to swap SD, SD2 ptrs. */
		  {	/* Goddamit why doesn't C have an */
			/* exchange operator??? */
			*asd2 = sd;
			return(sd2);
		  }
	  }
	*asd2 = sd2;
	return(sd);
}

/* SBX_SPLIT(sd,chroff) - Splits block SD at point CHROFF (offset from
 *	start of block).  SD remains valid; it is left locked.
 *	The smblk is split too, if one exists, and SMUSE adjusted.
 *	If offset 0, or equal to block length, the 1st or 2nd SD respectively
 *	will not have a smblk and its sdlen will be 0.
 *	(Note that if a smblk exists, a zero sdlen doesn't indicate much)
 */
struct sdblk *
sbx_split(sdp, coff)
struct sdblk *sdp;
chroff coff;
{	register struct sdblk *sd, *sdf, *sdx;

	if((sd=sdp) == 0)
		return((struct sdblk *)0);
	sd->sdflags |= SD_LOCK;
	if(sd->sdflags&SD_MOD)		/* If block has been munged, */
		sbx_npdel(sd);		/* Flush from phys list now. */
	sdf = sbx_ndget();		/* Get a sdblk node */
	bcopy((SBMA)sd, (SBMA)sdf, (sizeof (struct sdblk)));	/* Copy node */
	/* Note that the flags are copied, so both sdblks are locked and
	 * safe from possible GC compaction during call to sbx_msplit...
	 */
	if(coff == 0)			/* If offset was 0, */
	  {				/* then 1st SD becomes null */
		if(sdf->sdfile)		/* Fix up phys links here */
		  {	if(sdx = sdf->sdback)
				sdx->sdforw = sdf;
			else sdf->sdfile->sfptr1 = sdf;
			if(sdx = sdf->sdforw)
				sdx->sdback = sdf;
		  }
		sdx = sd;
		goto nulsdx;
	  }
	else if(sd->sdmem)
		if(coff >= sd->sdmem->smuse)
			goto nulsdf;
		else sdf->sdmem = sbx_msplit(sd->sdmem, (SBMO)coff);
	else if(coff >= sd->sdlen)
nulsdf:	  {	sdx = sdf;
nulsdx:		sdx->sdforw = 0;
		sdx->sdback = 0;
		sdx->sdmem = 0;
		sdx->sdfile = 0;
		sdx->sdlen = 0;
		sdx->sdaddr = 0;
		goto nulskp;
	  }
	if(sd->sdfile)
	  {	sdf->sdlen -= coff;		/* Set size of remainder */
		sdf->sdaddr += coff;		/* and address */
		sd->sdlen = coff;		/* Set size of 1st part */

	/* Link 2nd block into proper place in physical sequence.
	 * 1st block is already in right place.	 Search forward until
	 * find a block with same or higher disk address, and insert
	 * in front of it.  If sdlen is zero, just flush the links,
	 * which is OK since the 1st block is what's pointed to anyway.
	 */
		if(sdf->sdlen > 0)
		  {	while((sdx = sd->sdforw) /* Find place to insert */
			  && sdf->sdaddr > sdx->sdaddr)
				sd = sdx;
			sdf->sdback = sd;	/* Link following sd. */
			if(sdf->sdforw = sd->sdforw)
				sdf->sdforw->sdback = sdf;
			sd->sdforw = sdf;
			sd = sdp;		/* Restore pointer */
		  }
		else
		  {	sdf->sdforw = 0;
			sdf->sdback = 0;
			sdf->sdfile = 0;	/* Say no disk */
		  }
	  }

nulskp:	sdf->slback = sd;		/* Link in logical sequence */
	if(sd->slforw)
		sd->slforw->slback = sdf;
	sd->slforw = sdf;

	sdf->sdflags &= ~SD_LOCKS;	/* Unlock 2nd but not 1st */
	return(sd);			/* Note sd, not sdf */
}

/* SBX_MSPLIT - Like sbm_split but never fails, and sets
 *	SMUSE values appropriately
 */
struct smblk *
sbx_msplit(smp, size)
struct smblk *smp;
SBMO size;
{	register struct smblk *sm, *smx;
	register int lev;

	lev = 0;
	while((smx = sbm_split((sm = smp), size)) == 0)
		sbx_comp(SB_BUFSIZ,lev++); /* Need to get some smblk nodes */
	if(sm->smlen >= sm->smuse)	/* Split across used portion? */
		smx->smuse = 0;		/* Nope, new blk is all free */
	else
	  {	smx->smuse = sm->smuse - sm->smlen;
		sm->smuse = sm->smlen;
	  }
	return(smx);
}

/* SBX_NDEL - flush a SD and associated SM.  Fixes up logical
 * and physical links properly.  Returns ptr to next logical SD.
 * NOTE: if sd->slback does not exist, the returned SD is your
 * only hold on the list, since the SD gets flushed anyway!
 */
struct sdblk *
sbx_ndel(sdp)
struct sdblk *sdp;
{	register struct sdblk *sd, *sdx;
	register struct smblk *sm;

	sd = sdp;
	if(sm = sd->sdmem)		/* If smblk exists, */
	  {	sbm_mfree(sm);		/* flush it. */
		sd->sdmem = 0;
	  }
	if(sdx = sd->slback)
		sdx->slforw = sd->slforw;
	if(sd->slforw)
		sd->slforw->slback = sdx;	/* May be zero */

	/* Logical links done, now hack phys links */
	if(sd->sdfile)			/* Have phys links? */
		sbx_npdel(sd);		/* Yes, flush from phys list */

	sdx = sd->slforw;
	sbx_ndfre(sd);
	return(sdx);
}

sbx_npdel(sdp)
struct sdblk *sdp;
{	register struct sdblk *sd, *sdx;
	register struct sbfile *sf;

	if((sf = (sd=sdp)->sdfile) == 0)
		return;
	if(sdx = sd->sdback)	/* Start of disk file? */
		sdx->sdforw = sd->sdforw;
	else
		sf->sfptr1 = sd->sdforw;
	if(sdx = sd->sdforw)
		sdx->sdback = sd->sdback;
	sd->sdfile = 0;
	sd->sdlen = 0;
}


struct sdblk *sbx_nfl;	/* Pointer to sdblk node freelist */

struct sdblk *
sbx_ndget()		/* Like sbm_nget but never fails! */
{	register struct sdblk *sd;
	register int lev;

	lev = 0;
	while((sd = sbx_nfl) == 0		/* Get a node */
						/* If fail, make more */
		&& (sd = sbm_nmak((sizeof (struct sdblk)),SM_DNODS)) == 0)
						/* If still fail, try GC */
			sbx_comp(sizeof(struct sdblk)*SM_DNODS,lev++);

	sbx_nfl = sd->slforw;		/* Take it off freelist */
	sd->sdflags = SD_NID;
	return(sd);			/* Return ptr to it */
}

sbx_ndfre(sdp)
struct sdblk *sdp;
{	register struct sdblk *sd;
	(sd = sdp)->sdflags = 0;
	sd->slforw = sbx_nfl;
	sbx_nfl = sd;
}

SBMA
sbx_malloc(size)
unsigned size;
{
	register int lev;
	register SBMA res;

	lev = 0;
	while((res = (SBMA)malloc(size)) == 0)
		sbx_comp(size,lev++);
	return(res);
}

struct smblk *
sbx_mget(cmin,cmax)     /* like sbm_mget but never fails! */
SBMO cmin, cmax;
{	register struct smblk *sm;
	register int lev, csiz;

	lev = 0;
	csiz = cmax;
	for(;;)
	  {	if(sm = sbm_mget(csiz,cmax))
			return(sm);		/* Won right off... */
		sbx_comp(csiz,lev++);		/* Barf, invoke GC */
		if(sm = sbm_mget(csiz,cmax))	/* Then try again */
			return(sm);
		if((csiz >>= 1) < cmin)		/* If still short, reduce */
			csiz = cmin;		/* request down to min */
	  }
}

chroff sbv_taddr;	/* Disk addr of place to write into (set by TSET) */
struct sdblk *sbv_tsd;	/* SD that disk addr comes after (set by TSET) */

#define sbx_qlk(sd)  (sd->sdflags&SD_LOCKS)

#if 0
	This is the compaction routine, which is the key to the
entire scheme.	Paging text to and from disk is trivial, but the
ability to merge blocks is the important thing since it allows
flushing the pointer information as well as the actual text!  This
eliminates fragmentation as a fatal problem.
	There are a variety of ways that storage can be reclaimed:

- "pure" in-core blocks can be flushed instantly.
- "impure" incore blocks can be written to tempfile storage and flushed.
- The SM node freelist can be compacted so as to flush memory which is
	used for nothing but holding free nodes.
- The SD node freelist can be compacted, ditto.
- SBBUFs can be compacted, by:
	- Merging logically & physically adjacent on-disk pieces
	- merging logically & physically adjacent in-core pieces
	- merging logically adjacent in-core pieces
	- merging logically adjacent disk pieces, by reading in
		and then writing out to tempfile storage.
		Worst case would reduce whole sbstr to single tempfile block.

Problems:
	What is "optimal" algorithm for typical usage?
	Must go over all code to make sure right things get locked
		and unlocked to avoid having rug pulled out from under.
	Could have optional "registration table" for sbstruc; if exist
		in table, can check during GC.	If find one, can first
		do sbx_smdisc and then repoint sbcur to 1st block,
		with sbdot of 0 and sboff of sb_tell().	 This allows
		reducing whole thing to one block even tho "locked".
		Never touch stuff locked with SD_LCK2, though.
		Also may need way to protect the sbstr SD actually being
		pointed to by current sbx routine processing.
	Could have count of # nodes free for SM and SD; don''t GC 
		unless # is some number greater than size of a node block!
	Have different levels of compaction; pass level # down thru calls
		so as to invoke progressively sterner compaction measures.
		Can invoke sbx_comp with any particular level!
	Must have list somewhere of SBBUFs?  or maybe OK to scan core
		for SM_DNODS, then scan sdblks?
	Screw: could happen that stuff gets flushed (cuz pure) or even
		written out to tempfile, and then we have to read it back
		in so as to compact more stuff into tempfile... how to avoid?
		If pure stuff small and next to impure stuff, merge?
	Some calls just want to get another free node and don''t need
		new core.  How to indicate this?  How to decide between
		freeing up used nodes, and creating new node freelist?
#endif /*COMMENT*/
/* Compact stuff.
 * General algorithm for getting storage is:
 *	1) allocate from freelist if enough there
 *	2) find unlocked pure smblk to free up
 *	3) find unlocked impure smblks, write out.
 *	4) Compact stuff by reducing # of sdblks.  This is key to scheme!
 *		Otherwise fragmentation will kill program.
 * Maybe put age cnt in each sbstr?  Bump global and set cntr each time
 * sbstr gets major hacking (not just getc/putc).
 */
extern struct smblk *sbm_list;
sbx_comp(cmin,lev)
int cmin, lev;
{	int sbx_sdgc();

	if(lev > 100)		/* If program has no way to handle this, */
		abort();	/* then simply blow up. */
	if(lev > 10)		/* Too many iterations? Try to warn. */
		return(sbx_err(0,"GC loop, cannot free block of size %d",
				cmin));

	/* Step thru core hunting for SD node blocks */
	sbm_nfor(SM_DNODS,sizeof(struct sdblk),sbx_sdgc,lev);
}

/* Do GC stuff on a sdblk.  Guaranteed to exist, but may be locked */
sbx_sdgc(sdp,lev)
struct sdblk *sdp;
int lev;
{	register struct sdblk *sd, *sdf;
	register struct smblk *sm;
	struct smblk *smf, *sbm_exp ();
	SBMO more;

	sd = sdp;
	if(sbx_qlk(sd)) return(0);
	sm = sd->sdmem;
	sdf = sd->slforw;
	if (lev < 4) goto lev3;