sbstr.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
Todo stuff:
	New definitions:
		sbbuffer - old sbstr.  Abbrev & struct "sbbuff".  Macro SBBUFF
			(or SBBUF?)
		sbstring - list of sds.  Abbrev sbstr.  Macro SBSTR.
			Should *sbstr == *sdblk?  Yeah.
		sbfile - as before.  Macro SBFILE. (or SBFIL?)

	Try to get zero-length sdblks flushed on the fly,
		rather than waiting for moby GC.  Also, need to set
		up compaction of SD freelist, as well as SM freelist.
		Make SM freelist compact self-invoked by SBM_MGET?
	Any need for phys disk ptrs other than for tempfile?
		Can do sbm_forn through SDblks to find active sdfiles
		so list isn''t needed for that.
	Can sdback be flushed?  (not needed for keeping list sorted,
		or for searching it -- only used when linking
		blocks in or out of list.)  Perhaps use circular list?
		If list only used for tmpfile, then to link in/out could
		always start from sfptr1 of tmpfile? Sure, but slow?
		Last SD on phys list could belong to no logical list,
		and denote free space on tmpfile?

	--------------------------

	An "open" SBBUFFER will allow one to read, write, insert into,
and delete from a sbstring (a logical character string).  "Dot" refers
to the current logical character position, which is where all
operations must happen; sb_fseek must be used to change this location.
There are several states that the I/O can be in:
!SBCUR		----CLOSED----
		All other elements, including SBIOP, should also be 0.
		Dot is 0.
SBCUR && !SBIOP	----OPEN/IDLE----
		SBCUR points to a SD block (its SDMEM may or may not exist)
		SBIOP==0 (otherwise it would be open/ready)
		Dot is SBDOT + SBOFF.
		R/Wleft must be 0.
SBCUR && SBIOP	----OPEN/READY----
		SBCUR points to a SDBLK (SDMEM must exist!)
		SBIOP exists.
		Dot is SBDOT + offset into SMBLK.  SBOFF is ignored!
		SB_WRIT flag is set if "smuse" must be updated.
		The R/Wleft counts are set up:
		1. Rleft 0, Wleft 0 -- Since SBIOP is set, must assume
			counts are too.
			So this means at end of text, no room left.
			Otherwise would imply that setup needs doing.
		2. Rleft N, Wleft 0 -- At beg or middle of text
		3. Rleft 0, Wleft N -- At end of text
		4. Rleft N, Wleft N -- Shouldn''t ever happen

		Note that Rleft is always correct.  Wleft is sometimes
		set 0 in order to force a call to determine real state.

Note that SBIOP alone is a sufficient test for being OPEN/READY.

The important thing about updating the smblk is to ensure that the "smuse"
field is correct.  This can only be changed by writing or deleting.  We assume
that deletions always update immediately, thus to determine if an update
is necessary, see if SB_WRIT is set.  If so, update smuse before doing
anything but more writing!!!!

The SDBLK must be marked "modified" whenever a write operation is
done.  We try to do this only the first time, by keeping Wleft zero
until after the first write.  This is also when SB_WRIT gets set.
However, if in overwrite mode, Wleft must be kept zero in order to
force the proper actions; SB_WRIT is also not turned on since smuse
will not change.  Note that at EOF, overwrite becomes the same thing
as insert and is treated identically...

	If a SBLK has an in-core copy but no disk copy, it can be
freely modified.  Otherwise, modifications should preferably split
the block so as to retain "pure" blocks as long as possible.  "Pure" blocks
can always have their in-core versions flushed immediately (unless for
compaction purposes they''ll need to be written out in the same GC pass).
Alternatively, mods can simply mark the disk copy "free" and go
ahead as if no such copy existed.
	No additions or changes to a pure block are allowed, but
deletions from the end or beginning are always allowed.  All other
changes must split or insert new blocks to accomplish the changes.

Locking:
	SDBLKs are subject to unpredictable relocation, compaction,
and garbage collecting.  There are three ways in which a SDBLK can
remain fixed:

	1. The SDBLK has the SD_LOCK flag set.  This flag is used whenever
		a SBBUF''s SBCUR is pointing to this SDBLK.
	2. The SDBLK has the SD_LCK2 flag set.  This flag is used only
		during execution of various internal routines and should
		not be seen anywhere during execution of user code.
	3. The SDBLK has no back-pointer (is first block in a sbstring).
		Such SDBLKs cannot be relocated (since it is not known
		what may be pointing to them) but unlike the other 2 cases
		they are still subject to compaction with succeeding SDBLKs.

The SDBLK must be locked with SD_LOCK for as long as it is being
pointed to by SBCUR.  The sole exception is when a SBBUF in the
OPEN/IDLE state is pointing to the first SDBLK of a sbstring; this
sdblk is guaranteed not to be moved, since sdblks without a
back-pointer are never moved.  SD_LOCK is asserted as soon as the state
changes to OPEN/READY, of course.  The internal routines take pains to
always move SD_LOCK as appropriate.  Note that only one SD in a
sbstring can ever have SD_LOCK turned on.  SD_LCK2 is an auxiliary flag
which may appear in more than one SDBLK, for use by low-level routines
for various temporary reasons; either will prevent the SDBLK from being
modified in any way by the storage compactor.

SEEKs are a problem because it''s unclear at seek time what will happen
next, so the excision of the smblk can''t be optimized.  If the seek
happens to land in a sdblk with an existing smblk, there''s no problem;
but if it''s a sdblk alone, how to decide which part of it to read in???
If next action is:
	write - split up sdblk and create new one.  Read nothing in.
	read - read in 512 bytes starting at disk blk boundary if possible
		else read in 128 bytes starting with selected char
		(include beg of sdblk if less than 64 chars away)
	overwrite - as for read.
	backread - like read but position at end of sdblk.
	delete - split up sdblk, read nothing in.

We solve this through the OPEN/IDLE state, where SBIOP == 0 means SBOFF
points to logical offset from start of current sdblk, so that the seek
need not take any action.  Only when a specific operation is requested
will the transition to OPEN/READY take place, at which time we''ll know
what the optimal excision strategy is.  The routine SBX_READY performs
this function.

The physical links (SDFORW and SDBACK) are only valid when SDFILE is
set (likewise for SDLEN and SDADDR).  In other words, mungs to a sdblk
must check SDFILE to see whether or not the phys links should be
altered.  Normally they aren''t except during sdblk creation, deletion,
or swapout, no matter how much the sdblk gets shuffled around
logically.  The disk physical list is kept sorted in order of starting
addresses.  The text blocks indicated can overlap.  When a GC is
necessary, the code must figure out how much space is actually free.

-------------- Old woolgathering, ignore rest of this page ---------------

Question: should 512-byte buffers be maintained, one for each SBFILE?
Or should the in-core text be hacked up to serve for buffering?
Question is where to point the READ/WRITE system calls.  Currently,
they are pointed directly at the in-core text, and there are no
auxiliary buffers.

If use auxiliary buffers:
	How to handle flushing, when changing location etc?
	Could be clever about reading from large disk block, only
	get part of it into buffer instead of splitting up in order to
	read a "whole" block.
	Problem: sbstrings can include pieces of several different files.
		Hard to maintain just one buffer per FD without hacking
		done on one sbstring screwing that on another.
If don''t use buffers:
	Need to have a "chars-left" field in mem blocks, so know how
	much more can be added.  Will need heuristics for how much
	extra space to allocate.
#endif /*COMMENT*/

/* Includes, initial definitions */

#include <stdio.h>
#include "sb.h"

#ifndef V6
#define V6 0
#endif

#if V6
#include <stat.h>
#else
#include <sys/types.h>
#include <sys/stat.h>
#if MINIX
#include <fcntl.h>	/* For open() flags */
#else
#include <sys/file.h>	/* For open() flags */
#endif /* MINIX */
#endif /*-V6*/

extern int errno;
extern char *strerror();	/* From ANSI <string.h> */

/* Allocation decls */
SBFILE sbv_tf;		/* SBFILE for temp swapout file */
int (*sbv_debug)();	/* Error handler address */


/* SBX_READY argument flags (internal to SBSTR routines only)
 * The following values should all be unique; the exact value
 * doesn't matter as long as the right SKM flags are given.
 */
#define SK_READF 0			/* 0-skip fwd,  align BOB */
#define SK_READB (0|SKM_0BACK|SKM_EOB)	/* 0-skip bkwd, align EOB */
#define SK_WRITEF (0|SKM_EOB)		/* 0-skip fwd,  align EOB */
#define SK_DELF (4|SKM_0BACK)		/* 0-skip bkwd, align BOB */
#define SK_DELB (4|SKM_EOB)		/* 0-skip fwd,  align EOB */
#define SKM_0BACK 01	/* Zero-skip direction: 0 = fwd, set = backwd
			 * Don't ever change this value! See SBX_NORM. */
#define SKM_EOB	  02	/* Alignment: 0 = Beg-Of-Buf, set = End-Of-Buf */

/* Note on routine names:
 *	"SB_" 	User callable, deals with sbbufs (usually).
 *	"SBS_"	User callable, deals with sbstrings only.
 *	"SBX_"	Internal routine, not meant for external use.
 *	"SBM_"	Routine handling mem alloc, usually user callable.
 */

/* SBBUF Opening, Closing, Mode setting */

/* SB_OPEN(sb,sd) - Sets up SBBUF given pointer to first SD of a sbstring.
 * 	If SD == 0 then creates null sbstring.
 *	Any previous contents of SBBUF are totally ignored!!!  If you
 *		want to save the stuff, use SB_UNSET.
 *	Sets I/O ptr to start of sbstring.
 *	Returns 0 if error, else the given SB.
 */
SBBUF *
sb_open(sbp,sdp)
SBBUF *sbp;
SBSTR *sdp;
{	register struct sdblk *sd;
	register int cnt;
	register WORD *clrp;

	if(!sbp) return((SBBUF *)0);
	if((sd = sdp) == 0)
	  {	sd = sbx_ndget();	/* Get a fresh node */
		clrp = (WORD *) sd;	/* Clear it all */
		cnt = rnddiv(sizeof(struct sdblk));
		do { *clrp++ = 0; } while(--cnt);
		sd->sdflags = SD_NID;	/* Except flags of course */
	  }
	else if(sd->slback)		/* Must be first thing in sbstring */
		return((SBBUF *)0);		/* Perhaps could normalize tho */

	clrp = (WORD *) sbp;		/* Clear sbbuffer stuff */
	cnt = rnddiv(sizeof(SBBUF));
	do { *clrp++ = 0; } while(--cnt);

	sbp->sbcur = sd;
	/* Note that SD_LOCK need not be set, because first SDBLK has no
	 * backptr.  This is desirable to allow storage compactor maximum
	 * freedom in merging sdblks.
	 */
	/*	sd->sdflags |= SD_LOCK; */	/* Lock this one */
	return(sbp);
}


/* SB_CLOSE(sb)	- Close a SBBUF.
 *	Returns pointer to start of sbstring (first SD).
 *	Returns 0 if error.
 */
SBSTR *
sb_close(sbp)
SBBUF *sbp;
{	register SBBUF *sb;
	register struct sdblk *sd;

	if((sb = sbp) == 0)	/* Verify pointer */
		return((SBSTR *)0);
	sb_rewind(sb);		/* Do most of the work, including unlock */
	sd = sb->sbcur;		/* Save ptr to sbstring */
	sb->sbcur = 0;		/* Now reset the sbbuffer structure */
	sb->sbflags = 0;
	return(sd);
}


/* SB_SETOVW(sbp) - Set SBBUF Over-write mode for PUTC's.
 * SB_CLROVW(sbp) - Clear ditto.
 */
sb_setovw(sbp)
SBBUF *sbp;
{	register SBBUF *sb;
	if(sb=sbp)
	  {	sb->sbflags |= SB_OVW;
		sb->sbwleft = 0;
	  }
}

sb_clrovw(sbp)
SBBUF *sbp;
{	register SBBUF *sb;
	if(sb=sbp) sb->sbflags &= ~SB_OVW;
}

/* SBSTRING file system operations (see also sb_fsave) */

/* SB_FDUSE(fd) - Make a sbstring for given file.
 * 	FD is an open file descriptor.
 *	Returns pointer to a SBSTR containing the given file, or 0 if error.
 *	The FD must not be closed until a SB_FDCLS is done to
 *	purge memory of any blocks pointing at the file.
 * ** Maybe allocate sbfile structs with sbx_ndget, i.e. overlay on
 * ** top of sdblk node??  Wd this screw verify, GC, etc? Maybe not if
 * ** SD_LCK2 set...
 */

struct sbfile *sbv_ftab[SB_NFILES];

chroff
sbx_fdlen(fd)
int fd;
{
#if !V6
	struct stat statb;
#else
	struct statb statb;
	chroff len;
	struct {int hiwd ; int lowd;} foo;
#endif /*V6*/

	if(fstat(fd,&statb) < 0) return((chroff)-1);
#if V6
	len = statb.i_size1;
	len.hiwd = statb.i_size0 & 0377;
	return(len);
#else
	return((chroff)statb.st_size);
#endif /*-V6*/
}

SBSTR *
sb_fduse(ifd)
int ifd;
{	register struct sdblk *sd;
	register struct sbfile *sf;
	register int fd;
	chroff len;

	if((fd = ifd) < 0 || SB_NFILES <= fd	/* Check for absurd FD */
	  || sbv_ftab[fd])			/* and slot already in use */
		return((SBSTR *)0);
	if((len = sbx_fdlen(fd)) < 0) return((SBSTR *)0);
	sbv_ftab[fd]= sf = (struct sbfile *)sbx_malloc(sizeof(struct sbfile));
	sf->sffd = fd;
	sf->sfptr1 = sd = sbx_ndget();
	sf->sflen = len;
	sd->slforw = 0;
	sd->slback = 0;
	sd->sdforw = 0;
	sd->sdback = 0;
	sd->sdmem = 0;
	sd->sdfile = sf;
	sd->sdlen = len;
	sd->sdaddr = 0;
	return(sd);
}

/* SB_FDCLS(fd) - Close a file descriptor being used by sbstrings.
 *	If arg is -1, closes all FD's that are unused (a "sweep").
 *	For specific arg, returns 0 if couldn't close FD because still in use.
 *	Perhaps later version of routine could have option to copy
 *	still-used SD's to tempfile, and force the FD closed?
 */
sb_fdcls(ifd)
int ifd;
{	register int fd;

	if((fd = ifd) >= 0)
	  {	if(fd >= SB_NFILES) return(0);	/* Error of sorts */
		return(sbx_fcls(sbv_ftab[fd]));
	  }
	fd = SB_NFILES-1;
	do {
		sbx_fcls(sbv_ftab[fd]);
	  } while(--fd);	/* Doesn't try FD 0 ! */
	return(1);
}

sbx_fcls(sfp)
struct sbfile *sfp;
{	register struct sbfile *sf;
	register int fd;

	if((sf = sfp)==0		/* Ignore null args */
	  || sf == &sbv_tf)		/* and never close our tempfile! */
		return(0);
	fd = sf->sffd;			/* Find sys file descriptor */
	if(sbv_ftab[fd] != sf)		/* Ensure consistency */
		return(sbx_err(0,"SF table inconsistency"));
	if(sf->sfptr1)			/* Any phys list still exists? */
		return(0);		/* Yes, still in use, can't close */
	close(fd);			/* Maybe do this when list gone? */
	sbv_ftab[fd] = 0;		/* Remove from table */
	free(sf);			/* Remove sbfile struct from mem */
}

/* SB_FDINP(sb,fd) - Returns TRUE if specified fd is still in use
 *	by specified sbbuffer.
 */
sb_fdinp(sb, fd)
register SBBUF *sb;
int fd;
{	register struct sdblk *sd;
	register struct sbfile *sf;

	if((sf = sbv_ftab[fd]) == 0
	  || (sd = sb->sbcur) == 0)
		return(0);
	sd = sbx_beg(sd);		/* Move to beginning of sbstring */
	for(; sd; sd = sd->slforw)	/* Scan thru all blocks in string */
		if(sd->sdfile == sf)	/* If any of them match, */
			return(1);	/* Return tally-ho */
	return(0); 
}

/* SB_FSAVE(sb,fd) - Write entire SBBUF out to specified FD.
 *	Returns 0 if successful, else system call error number.
 */
sb_fsave(sb,fd)		/* Write all of given sbbuf to given fd */
register SBBUF *sb;
int fd;
{
	sbx_smdisc(sb);
	return(sbx_aout(sbx_beg(sb->sbcur), 2, fd));
}

/* SBBUF Character Operations */