We explore here a memory management method that employs the disk
	  and works well with ~large databases.

	  A very straightforward method would be to rely on ~virtual
	  ~memory to handle the largeness.	This is covered in Chapter 36.
	  Recall however that the cost of a garbage collection is proportional
	  to the number of blocks in use, the ~size of the database.

	  The method we present now has no such cost dependency on the size of
	  the database, and so is more efficient overall.

	  This method has the disadvantage of requiring the programmer to be
	  aware of the disk, which can be minor enough (Section 23.9).

The Segregation Of Core And Disk

	  We will refer to real memory as ~core.	Data can thus reside in core
	  or on disk.

	  We envision a large database residing on disk.  As parts of the
	  database are accessed, they get swapped into core, as structures like
	  the ones we've seen.  Only the parts of the database actually needed
	will reside in core.  It may be that all the desired parts of the
	database fit in core all at once, in which case the slowness of the
	disk would be avoided altogether.

	We will garbage collect only core and not disk.  By keeping a limit
	on the size of core, the cost of a garbage collection will be limited.
	The number USED will have a small upper bound.  With core limited to
	half a million 8-byte blocks, we've observed GCs taking only 5 seconds
	  each.  This contrasts multi-hour garbage collections if we were to
	  garbage collect the disk as well.

	  We get by garbage collecting only core, avoiding the disk, by making
	  a fundamental distinction between core-resident and disk-resident data.
	  Disk-resident data ~can't point to core-resident data.  This means
	that if we ever followed pointers on the disk, we would never reach
	core-resident data.

	Core-resident data can point to other core-resident data, naturally,
	or to disk-resident data.  However, the disk resident data can point
	~only to other disk-resident data.

	We garbage collect core-resident data like we have done so far.  We
	follow all pointers within core, and ignore pointers to the disk.
	(Following those disk pointers would never wind up pointing back to a
	block in core).  Thus, even though we limit our garbage collection to
	core, we will in fact mark all blocks in core that are truly reachable,
	(since none are reachable from the disk).

	This efficient method works well with large databases.  Its only
	drawback is that some programmer attention is required to make it work.
	The programmer must specify ~where in his or her structures
	~fractures can be made.  Such fracture points are like hinges.  While
	one part of the overall structure may stay in core, other parts,
	connected by hinges, can evacuate from core onto disk.  The garbage
	collector can choose to swap out portions of structures in its effort
	to deliver more free memory.

Disk Nodes


	We introduce a new, third kind of block, called a ~disk ~node, beyond
	our D- and P-blocks introduced in the previous chapter.  Figure
	33.1(a) shows a disk node, whose associated data are presently core-
	resident.  Part (b) shows the situation when the disk node's
	  associated data are only disk-resident.	 The disk node here points to
	  no core-resident data.

	  A disk node may have ~associated ~core-resident ~data (ACRD for short),
	  in which case, we say that the disk node's contents are ~swapped ~in.

	A disk node is special in that our new MARK procedure will never
	pursue its ACRD.  That is, when MARK happens across a disk node, it
	marks it indeed, like any other block, but even if as figure 33.1(a)
	shows there is a pointer to the ACRD, that pointer will ~not be
	followed.  (Don't worry, we may later mark those blocks, if we
	  choose to retain the ACRD).


	  Thus, a disk node shields any associated core-resident data from
	  MARK, like in figure 33.2.	The umbrella protects the ACRD from the
	  rain, from MARK.


	  The ACRD of a disk node can themselves reference other disk nodes, as
	  shown in figure 33.3.

		    BOX:	Can the disk point into core?
		    BOX:	Can core point to the disk?
		    BOX:	Does MARK always mark a disk node's ACRD whenever
		BOX:	encountering the disk node itself?

The Initial Segment

	Our modified garbage collector accomodates disk nodes.  It doesn't
	  MARK any of their ACRD initially.	 Thus, upon completion of marking,
	  unmarked blocks are either free, like we're use to, or they are part
	of disk nodes' ACRD.

	  All that is marked at this point is called the ~initial ~segment.  With
	  our original garbage collector, without disk nodes, the initial segment
	  is ~all blocks in use.  What's new now is that disk nodes hide some

	After marking the initial segment, data under disk nodes, which are
	unmarked, could be freed.  In fact, they would be freed if we commenced
	with the sweep procedure immediately.  If we decide that no
	disk node's ACRD are to be kept, then invoking the sweep now would
	  be appropriate.

	  However, the garbage collector can pick and choose ~which disk nodes
	  should keep their ACRD.  If the initial segment, all blocks reachable
	  without going thru disk nodes, is not too big, then we might
	  decide to keep in core some disk nodes' ACRD.

	The initial segment is everything that we're stuck with, even if we
	  free up ~all disk nodes' ACRD.

Infant Disk Nodes - The I-Block


	There are three kinds of disk nodes, ~infant disk nodes, and ~mature
	~clean and ~dirty disk nodes.  Whenever a new disk node is requested
	(Section 23.9), an infant disk node is created.  Infant
	disk nodes are special in that they have no ~associated ~residence ~on
	~the ~disk.  Since they live no place on disk, the ACRD must always be
	present (figure 33.4).

	If one wanted to swap out the infant disk node's ACRD, one would first
	  force it to ~mature.	The act of maturing an infant associates finally
	  a location on disk for its data.	Now, for the first time, the mature
	  disk node's ACRD ~could be written out to disk, and then be freed from

Motivation For Infant Disk Nodes

	We've introduced the infant disk node with the following scenario in
	  mind.  It is possible, even probable, that a newly created disk node
	  will cease to be referenced in short order.  An infant disk node that
	  never matures has the delightful property that no disk allocation is
	  ever made, nor is any data ever written out to disk.

	  For example, it may be necessary to render data as a disk node
	  temporarily, to accomodate datatypes that require disk-resident data in
	  general.	Consider the following types:

					    CONTENTS:  BIG_TEXT	 ];


	  The type BOOK has its title held in core (type TEXT), whereas the
	  much larger ~contents is a disk-resident form of text, the type
	  BIG_TEXT.	 Now suppose there is a function READ:

		    DEFINE	READ( B: BOOK ) :


				CONTENTS:= B.CONTENTS;	"This swaps in B's contents"

				do something with CONTENTS



	  The assignment into CONTENTS swaps in the book B's contents TEXT (due
	to the coercion:


	from Section 23.9).  Thus CONTENTS holds the now core-resident data of
	type TEXT, from which the bulk of the READing can occur.

	Now it may be in some application that we create a new BOOK just to be
	READ once.  When we create the book, we have in hand its contents, of
	type TEXT.  We create the book via:

		BOOK :=  [ CONTENTS:   the_text \DISK   ] ;

	The "\DISK" creates a new (infant) disk node to hold the given text.
	The very next thing we do is:

		READ( BOOK ) ;

	Upon completion of READing, we no longer need that BOOK, and so we
	may perform:

		BOOK := NIL ;

	This scenario creates a disk node, uses it briefly, as is required
	in the type BOOK, and then is finally abandoned.  It is most likely
	that the infant is ~not forced to mature in this short time.  During
	its entire, brief lifetime, we never have to deal with the disk.

		BOX:	What is the initial segment?
		BOX:	Does an infant disk node have an associated disk
		BOX:	address?
		BOX:	What savings do infant disk nodes provide?

Mature Disk Nodes

	The garbage collector chooses to swap out some disk nodes' ACRD in
	  order to render more free blocks.	 In order to release a disk node's
	ACRD, a copy of those data must be written to disk.  Writing to disk
	requires that there be a place on disk to hold the data.

	A mature disk node has an associated place on disk to store its ACRD.
	Infant disk nodes are turned into mature disk nodes as soon as a disk
	address is required of the infant disk node.

	An infant matures when the garbage collector wants to write out its
	ACRD.  An infant may ~also be matured when some other disk node's ACRD
	  is written out.	 If that other disk node's ACRD references an infant
	disk node, then a disk address must be associated with that infant.
	Those data need a way to reference that infant on disk.  The now
	matured infant can be referenced on disk via its disk address.


	Mature disk nodes come in two varieties, clean and dirty.  Each of
	these two kinds of disk nodes have an associated disk address, which
	is held in the second bin (figure 33.5).
Clean Disk Nodes

	A clean disk node indicates that the disk-resident data is up to date.
	The clean disk node may or may not have ACRD (figure 33.5(a and b)).

	The garbage collector can free up a clean disk node's ACRD simply by
	  zeroing out the pointer in the first bin (figure 33.5(a)).  Of course,
	  once this is done, and when somebody wants the ACRD, the disk (which
	  is up to date) will have to be read so as to restore the ACRD (figure
Dirty Disk Nodes

	  In contrast, a dirty disk node indicates that the data on disk, if any,
	  is no longer up to date.  A dirty disk node always has ACRD.  (Where
	  else could the actual up to date data be represented)?

	  When infant disk nodes mature, they become ~dirty disk nodes.  There is
	  no data on the disk at this point, and so clearly the "disk-resident"
	  data is not up to date.

	  If the garbage collector wants to free up a dirty disk node's ACRD, it
	cannot simply zero the first bin, as was possible with clean disk
	nodes.  It must first write the ACRD out to disk, so that the disk
	will be up to date.  That writing to disk allows us to change this
	dirty disk node into a clean disk node.  At this point, the first
	bin's pointer can be zeroed safely, so as to free up the space taken
	  by the ACRD.

	  We've seen so far how infant disk nodes evolve to mature dirty disk
	nodes, and how dirty disk nodes become clean disk nodes. What we
	haven't seen yet is how clean disk nodes become dirty.  (Another
	  conceivable evolution, a mature disk node becoming an infant once
	  again, never happens).
The @-Operator Causes Dirtiness

	  In ICL, no existing data in blocks are ever modified, except by using
	  the @-operator, to make an objective modification (Section 22.1.11).
	  In LISP, the corresponding primitive operator is both RPLACA and


	  We introduce a new bit into ~all blocks, called the MODIFied bit
	  (figure 33.6(a)).  The @-operator, upon overwriting a block, sets this
	  MODIF bit in that block.  It indicates that data in
	  this block has been modified.  Figure 33.6(b) shows the block with the
	  MODIF bit on, and that it may be part of some disk node's ACRD.

	Since the disk node's ACRD has been modified, we want the disk node to
	  change into a dirty disk node (if it's not already a dirty disk node).
	The disk-resident data are no longer up to date.

	How does the disk node "see" that it is dirty?  How does the presence
	of a MODIF bit far below get transmitted up to the disk node?  We
	modify the MARK procedure so as to propogate MODIF bits upward.  Figure
	33.6(c) shows the situation where the MODIF bit has been propagated

	Upon marking a block, MARK looks at the block's pointer(s).	 If either
	  one of the blocks referenced has the MODIF bit set, then MARK sets
	  the MODIF bit in this block.  Thus, the MODIF bit propogates upward,
	  so that the top block in the disk node's ACRD has the MODIF bit set.

	The garbage collector turns clean disk nodes into dirty disk nodes
	when their ACRD have the MODIF bit set.

	The MODIF bit has served its purpose, rendering appropriate disk nodes
	dirty.  The garbage collector ultimately turns off ~all MODIF bits,
	during the sweep.  Thus, upon commencement of garbage collection, a
	set MODIF bit indicates that this block has been modified objectively
	since the previous garbage collection.

	Only those disk nodes' ACRD modified since the last garbage collection
	  need be rendered dirty, as modifications prior to this garbage
	  collection were rendered dirty during that previous garbage collection.

	  There is a cousin of MARK, called MARK'.  MARK' is like MARK except
	  that it doesn't set the mark bit.  (It uses another bit instead).
	MARK' is around to cause the upward propogation of MODIF bits ~without
	  ~marking ~the ~ACRD.

	  MARK' instead of MARK is used on disk nodes whose ACRD are to be
	relinquished (e.g., swapped out).  We can say that all accessible
	blocks will be processed by MARK or MARK', and thus all MODIF bits
	  will be propogated upward.

		    BOX:	What is the difference between infant and mature disk
		    BOX:	nodes?
		    BOX:	What is the difference between clean and dirty disk
		    BOX:	nodes?
		    BOX:	When an infant matures, does it become a clean or a 
		    BOX:	dirty mature disk node?
		    BOX:	What causes dirtiness?
		    BOX:	How is dirtiness propogated upward thru disk nodes'

Who To Swap Out

	Among all the disk nodes, the garbage collector needs to pick which
	ones are to be swapped out.  (Recall that "swapping out" means merely
	the zeroing of the disk node's first bin.	 It involves writing to the
	  disk only for ~dirty disk nodes).

	  The ideal choice would be to swap out the disk node which will in fact
	  be required furthest in the future.  This, however, may be impossible
	  to predict.

	  We consider two competing metrics for deciding who should swap out.


	  The first metric for deciding who to swap out is familiar.  It is
	  used within the usual, paged virtual memory systems: the age.  ~How
	  ~long ~has ~it ~been ~since ~the ~core-resident ~data ~was ~last ~used?
	  Data not used for a long time are best swapped out.

	  We can measure the age by counting the number of garbage collections
	  that have occured since a disk node's ACRD were last acquired from the
	disk node.  That is, how long has it been, measured in numbers of
	garbage collections, since the disk node's ACRD was last requested?


	  We associate with each disk node an age, as shown in figure 33.7.
	  Whenever the ACRD is grabbed from a disk node, we set its age to ~zero.
	  This means that it has been accessed recently.  (Such grabbing occurs
	  via the swap-in coercion, e.g., in our most recent example type
	  declaration, the coercion:

		    ~BIG_TEXT	  ->	    ~TEXT		  ).

	  Each garbage collection increments the age in ~all disk nodes.	Thus,
	  at any point in time, the age in a disk node tells the number of
	  garbage collections that have occured since the ACRD was last

Freeable Memory

	  Our second metric is new.  How much memory will ~actually ~be ~freed
	  if we swap out a disk node's ACRD?  In paged virtual memory systems,
	that size is identical no matter which page is selected for swap out.
	In our object oriented virtual memory, objects can be of different


	In addition, in our block space, some blocks may be shared, i.e.,
	referenced from ~multiple points of view.  It may be that ~not ~all of
	a disk node's ACRD can be freed.  Figure 33.8 shows a disk node with
	  its ACRD.	 Presently, a variable (X) references part of the disk node's

	If the garbage collector chooses to swap out this disk node's
	  ACRD, it ultimately zeros the disk node's first bin's pointer.	That
	  removes ~one reference.  As figure 33.8(b) shows, only part of the ACRD
	  will be freed.	The variable X still points to some of it, and that
	  portion will remain in use.

	  We choose to swap out disk nodes' ACRD that free up the most
	memory.  The leads us to swap out fewer but larger structures.
	Few large structures as opposed to many small structures improves
	communication with the disk, as less random access may be required.


	Imagine one long list consisting of all disk nodes referenced from
	core which are ~swapped ~in, i.e., have ACRDs.  Sort the list so that
	freeable memory increases.  That is, sort it so that the first disk
	node's amount of freeable memory is minimal, and the last disk node's
	freeable memory is maximal.  We would like to swap out disk nodes at
	the end of the list.


	We traverse this list with the intent of keeping in core disk nodes
	early in the list (figure 33.9).  We keep each disk node's ACRD in
	  turn, by MARKing the disk node's ACRD.  We keep a count of the total
	number of blocks marked.  We keep MARKing the next disk node's ACRD
	  until we've marked ~enough blocks.  (What "enough" is will be
	considered shortly).

	At this point, we've retained in core all disk nodes on an initial
	  portion of the list.	The rest of the disk nodes further down on the
	  list are not kept in memory.  They are all swapped out.  (This means
	  at least that those disk node's ACRD pointer is zeroed).  Thus, disk
	nodes towards the end of the list, those that can free up the most
	blocks, are swapped out.

	This list is called MEMORY_RESIDENT.  Between garbage collections, it
	always holds ~all disk nodes that have ACRD.  Some disk nodes are not
	on that list.  Those disk nodes have no ACRD.

Mixing Age And Freeable Memory

	To combine our two metrics, we scan the list MEMORY_RESIDENT several
	times.  Recall that that list holds all disk nodes with ACRD, those
	that we can possible choose to swap out.

	We scan the list once for each age, starting at age zero.  We consider
	only disk nodes that are a young as that age.  For the first scan,
	we consider only disk nodes with age zero, i.e., those whose ACRD were
	requested ~since the last garbage collection.  We keep those disk
	nodes' ACRD.  Then we scan again for disk nodes of age one.	 (Those
	  disk nodes had their ACRD requested some time ago, since just ~before
	  that last garbage collection).

	  We keep incrementing AGE and scanning the list MEMORY_RESIDENT.	 We
	  keep in core each encountered young disk node's ACRD, by MARKing the
	ACRD.  We stop this scanning and AGE incrementing process as soon as
	we've marked enough nodes.  (More about "enough" shortly).

	  All the unprocessed disk nodes on MEMORY_RESIDENT are left to be
	  swapped out.  Thus, we swap out disk nodes of greater age and greater
	  freeable memory.  However, the age dominates the situation.

Structures Locked In Core


	  It may be that the entirety of a disk node's ACRD is referenced, as
	X does in figure 33.10.  For such cases, ~no memory would be freed by
	swapping out the disk node's ACRD.	For such cases, we most definitely
	  keep the ACRD, always.

	  This agrees with Section 23.9, which mentioned that referencing the top
	  of a disk node's ACRD keeps it ~locked in memory.

		BOX:	What are two metrics for choosing who gets swapped
		BOX:	out?
		BOX:	When is a disk node's ACRD locked in memory?
		    BOX:	In what order is the list MEMORY_RESIDENT kept?
		    BOX:	What portion of the list MEMORY_RESIDENT references
		    BOX:	disk nodes whose ACRD will be kept?

The Six Phases Of Garbage Collection

	  The six phases of our new garbage collector are summarized:

	     1)   Mark the initial segment (stopping at disk nodes)
	     2)   Mark all disk nodes' ACRD that we choose to keep in core
	   3)	Release (swap out) the ACRD of all other disk nodes
	   4)	Discard unmarked disk nodes
	   5)	Form MEMORY_RESIDENT, to hold disk nodes with ACRD
	   6)	Sweep: form FREE_LIST

 Phase 1

	The first phase is:

		1)	MARK the ~initial ~segment

	This operation is identical to the marking phase of our original
	garbage collector.  However, marking stops at disk nodes.

		(Recall that marking begins at the roots, all the program's
		    variables.  The garbage collector's own variables, e.g.,
		MEMORY_RESIDENT, are ~not part of the roots).

 Phase 2

	The second phase follows:

	   2)	Choose the subset of all disk nodes whose ACRD will remain

		MARK those ACRDs so that they won't be freed during the sweep.

	  This is the process that scans the list MEMORY_RESIDENT for each age,
	  and stops when ~enough blocks are marked.  We remove each such
	  processed disk node from MEMORY_RESIDENT, and put it instead on one of
	  the 32 lists that will be read (and explained) in phase 5.

	  Disk nodes on MEMORY_RESIDENT that are as yet unmarked are ~not
	  considered.  (They may ultimately be discarded altogether).

	  However, some ~other disk nodes might be marked during the marking of
	  a given disk node's ACRD.  (The ACRD often references other disk
	nodes as in figure 33.3).

	Whenever a disk node becomes marked, restart the scan of
	MEMORY_RESIDENT immediately, keeping the age unchanged.  We
	had passed up this disk node earlier in the present scan, because then
	it wasn't marked.

 Phase 3

	  The third phase is:

	     3)   Release the ACRD for all other disk nodes (remaining on

	  That is, zero the pointer to the ACRD in each remaining disk node's
	first bin.  If the disk node happens to be an infant, mature it so that
	it will have a disk location to which to be swapped out.
	(Change the infant into a dirty disk node).  In either case, before
	zeroing the first bin, if the disk node is dirty, write the ACRD to

	We release all the disk nodes' ACRD (remaining on MEMORY_RESIDENT)
	  except for:

	     a)   ACRD that are locked in core (Section 33.3.5)
	     b)   unmarked infant disk nodes

	  Unmarked infant disk nodes have the peculiar property that they are
	  referenced from ~neither core (as they are not marked) nor disk.  (Only
	  mature disk nodes can be referenced from disk).

	  Note however that a swap out process can have a side effect.  As
	  we swap out a disk node's ACRD, infant disk nodes referenced in the
	ACRD will be forced to mature.  (They must be matured so that they can
	be referenced from disk, via disk address, within the disk-resident
	rendition of the swapped-out ACRD).

	Whenever an infant matures, we reconsider that infant disk node,
	even if it's not marked.  (We've skipped it so far in phase 3 - part(b)

 Phase 4

	The fourth phase is:

	   4)	Discard unmarked disk nodes

	It is possible that a disk node might no longer be referenced (from
	within core).  Such unreferenced disk nodes play no further role,
	and can be removed from the list MEMORY_RESIDENT and from another
	structure called MATURE, which will be introduced in Section 33.8.
	It may be that swapping out another disk node's ACRD releases the last
	  reference in core to this disk node, and so this disk node can be

	  Thus, we retain only disk nodes that are accessible from core-resident

 Phase 5

	  The fifth phase is:

	     5)   Collect up all disk nodes with ACRD (a subset of the list

		    Form a new list MEMORY_RESIDENT consisting of just those disk
		    nodes.	Sort is so that it goes from the least to the most
		    ~freeable memory.

	  This forms MEMORY_RESIDENT, all ready for use in the ~next garbage

	  The list MEMORY_RESIDENT used during this garbage
	  collection was actually formed as a by-product of the previous GC.  In
	  the previous GC, during phase 3 (the retaining of disk nodes' ACRD),
	the freeable memory under each disk node is naturally calculated, by
	counting the number of blocks marked within a disk node's ACRD.

	  However, it is possible that since the previous GC, references to
	  memory could have changed, thus rendering a not quite accurate
	  ordering on MEMORY_RESIDENT.  We accept this possible inaccuracy, which
	  is likely not very great.  It saves us from having to recompute
	  freeable memory an extra time, at the beginning of this GC, as opposed
	  to the previous GC's phase 3 where that information appeared for free.

	Other slight inaccuracies creep in during this phase 5, when we form
	the new list MEMORY_RESIDENT.  We don't take the time to sort that
	  list.  Instead, we form temporarily 32 different lists, whose union
	  will ultimately form MEMORY_RESIDENT.  The K'th of the 32 lists holds
	all disk nodes whose amount of freeable memory lies somewhere between
	2^K and 2^(K+1) blocks.  Distinction between varying sizes in that
	range are ignored.

	Upon the completion of phase 5, those lists are concatenated, in order,
	to form the one resulting list MEMORY_RESIDENT.

 Phase 6

	The final, sixth phase is our familiar sweep:

	   6)	Sweep: Gather onto FREE_LIST all unmarked blocks


	   1)	Mark the initial segment (stopping at disk nodes)
	   2)	Mark all disk nodes' ACRD that we choose to keep in core
	     3)   Release (swap out) the ACRD of all other disk nodes
	     4)   Discard unmarked disk nodes
	     5)   Form MEMORY_RESIDENT, to hold disk nodes with ACRD
	     6)   Sweep: form FREE_LIST

		    BOX:	Which phase actually marks the ACRD of disk nodes that
		    BOX:	will be kept in memory?
		    BOX:	Why must an infant be matured if we choose not to
		    BOX:	retain its ACRD?
		    BOX:	Why must an infant disk node be matured if it is
		    BOX:	referenced within a disk node's ACRD which is being
		BOX:	swapped out?
		BOX:	Why can we discard unmarked disk nodes?
		BOX:	When is the list MEMORY_RESIDENT rendered ordered
		BOX:	properly for use within this garbage collection?

When Have We Marked Enough Blocks?

	There are advantages both to swapping out and not swapping out data.
	The advantage of not swapping out is obvious:  Later, when the data
	may be required again, no swapping in is necessary.

	However, there is advantage to swapping out data even if it will be
	required again later.  Between now and then, if the data is not core-
	resident, each GC will free up more blocks.  ~The ~cost ~per ~freed
	~block ~goes ~down.

	If the ACRD are not needed for a long time, swapping the structure out
	in the interim is most efficient.  It may be more efficient even
	when we consider the cost of one future swap-in.

	We mentioned earlier that we rescan MEMORY_RESIDENT once for each age.
	We mark the ACRD of disk nodes whose ACRD are to be kept.  We keep a
	count of the total number of blocks MARKed.  We ~stop this scanning
	when "enough" blocks are marked.

	What is "enough"?  A lower number frees more blocks per GC, and a
	higher number retains more data in core.  We choose "enough" to be
	about half of all blocks (say 250000).

	The "enough" quota can be varied, so as to depend on age.  We can limit
	"enough" to be 250000 for blocks of age zero (those accessed most
	recently).  We can then reduce the quota for older disk nodes.  That
	is, while we're willing to keep up to 250000 blocks for age zero
	  disk nodes, we may be willing to keep only 175000 blocks total if we're
	considering disk nodes of age 1.  Less and less blocks will be allowed
	for the ACRD of older disk nodes.

Disk-Resident Representation Of Structures

	The disk resident format for any structure is necessarily linear in
	nature because disks are accessed most efficiently in a linear fashion.

	We will think of the disk, actually a single file on the disk, as
	being made up of a set of ~diskettes.  Different diskettes may have
	different lengths.  A diskette is logically one contiguous stream of
	disk, although the implementation may represent a diskette as smaller
	chunks of disk linked together.  Any in-core structure written to disk
	occupies exactly one diskette.

	The contiguous stream of bytes in a diskette is made of bytes (8-bits)
	and words (32-bits).  We will write:


	to denote a byte whose value is N.  Similarly:


	is a 32-bit word whose value is N.

	The format of a diskette, which holds a disk node's ACRD, is a NODE
	  followed by a zero byte:

		    NODE  byte(0)		    ->	a diskette

	  A NODE is any of the following.  A P-block, which has two pointers, is
	  represented by the following rule for a NODE:

		    byte(1)	 NODE	 NODE			->	  NODE

	  The "byte(1)" indicates that this is a P-block.  The two pointers in
	  a P-block are represented by two NODEs.	 The length of a NODE on disk
	  is variable.  If the P-block's pointers point to large structures, then
	the two NODEs here will be correspondingly large on disk.

		We have omitted the P-block's second bin's high-order byte.
		We do this for simplicity.  If one wanted to include that
		byte, then one should change this definition so as to insert a
		byte following the "byte(1)".

		Also for simplicity, we ignore the "free bits" in a
		block's first bin's high-order byte.  That information can be
		encoded in the first byte.

	A D-block is represented by:

		byte(2)  NODE  word(the_second_bin)		->	NODE

	The "byte(2)" indicates that this is a D-block.  The D-block's one
	  pointer (from bin #1) is represented by the NODE.  The second bin,
	  a non-pointer, is represented by the final ~word.

	  Infant disk nodes have no place on disk, and so there is no format
	  for them.	 A mature disk node can be resident on the disk.  A mature
	  disk node is represented by:

		    byte(3)	 word(the_disk_address)		  ->	    NODE

	  The disk node's disk address appears on disk as a word.  This kind of
	NODE acts as a pointer to another disk-resident structure, whose disk
	address is given.

	Notice how core-resident pointers are replaced on the disk by what
	they point to, a NODE.

	A NIL pointer is represented by:

		byte(4)			->	NODE


	Figure 33.11 shows some example structures and their disk-resident NODE

		BOX:	Does a pointer, or what it points to, get written to
		BOX:	disk?
		BOX:	What form of NODE represents a pointer to another
		BOX:	disk-resident structure?

Sharing Within A Disk-Resident Structure


	Figure 33.12(a) shows an example of sharing.  The two pointers from the
	first block point to the same place.  We need a way of representing
	~once on disk the shared block.

	Our present format can't represent this sharing.  We could write the
	  same NODE twice, once for each of the P-block's two pointers.  That
	representation would be indistinguishable from the structure shown in
	figure 33.12(b).  Two copies of the same NODE on disk render two copies
	of the shared block in core.

	To preserve sharing within a structure, we write out the shared sub-
	structure ~once, but refer to it twice.  The following new form of
	NODE associates an integer with the shared structure:

		byte(5)  word(integer)  NODE		->	NODE

	This form of NODE is called a ~definition.  It represents exactly
	the same structure as is represented by the NODE following the integer.
	The only difference here is a side effect.  The given integer is
	associated with that given NODE.

	That association of an integer with a NODE is used within our final
	form of NODE:

		byte(6)  word(integer)		->	NODE

	This form of NODE ~refers to the NODE previously associated with the
	given integer.  This is called a ~reference NODE.

	For example, the structure in figure 33.12(a) is represented by the
	following.  The second block by itself is represented by:

		byte(2)  byte(4)  word(A)

	It is a D-block (the "byte(2)") whose first bin's pointer is NIL
	  ("byte(4)"), and whose second bin is the number A.

	  We will want to refer to this block twice, so we associated the
	  integer, say 1, to this block by embedding this NODE in:

		    byte(5)	 word(1)  the_NODE

	  Altogether, this looks like:

		    byte(5)	 word(1)	byte(2)  byte(4)	word(A)

	  The NODE representation for the first block is:

		    byte(1)	 the_line_just_shown  byte(6)	 word(1)

	  That is, the first block is a P-block ("byte(1)").	Its first bin's
	pointer goes out as a NODE, the previous line just shown.  The
	P-block's second bin's pointer also goes out as a NODE, the NODE:

		byte(6)  word(1)

	This NODE refers to the previously defined NODE, the NODE associated
	with the integer 1.  Altogether, figure 33.12(a) goes out as:

		byte(1)  byte(5) word(1) byte(2) byte(4) word(A)  byte(6)

A Cycle


	Figure 33.13 shows a single block involved in a cycle.  Every reachable
	cycle has a shared block within it (Section  The shared block
	in this case is the one block.

	Since it is shared, we will naturally write it out as a ~definition
	(for the integer, say, 1):

		byte(5)  word(1)  that_block

	"That block" is a D-block, and so goes out as:

		byte(2)  a_reference_to_this_block  word(A)

	This D-block's first bin references itself, and so the NODE following
	  our byte(2) is actually a reference to this very block.  That reference

		    byte(6)	 word(1)

	  Altogether, this one block goes out as follows:

		    byte(5) word(1)   byte(2)	 byte(6) word(1)	word(A)

	  It defines the integer 1 (following "byte(5)") and simultaneously
	  refers to that definition, via a reference to the integer 1 (following
	  the "byte(6)").

		    BOX:	What byte-code is used to associate an integer with
		    BOX:	a shared block?
		    BOX:	What code is used to refer to a shared block via
		    BOX:	that integer?
		    BOX:	Is there a special code to deal with cycles?

Swap Out

	  The procedure to write out a block and all the blocks it references
	  follows.	For now, we ignore shared structures.  We issue no
	  definitions nor references:


				IF  B is NIL  THEN

				EF  B is a P-block  THEN
					  OUTPUT( B's first bin's pointer );
					  OUTPUT( B's second bin's pointer );

				EF  B is a D-block  THEN
					  OUTPUT( B's first bin's pointer );
					  output_word( B's second bin );

			EF  B is a disk node  THEN
				output_word( B's second bin
								"(the disk address)" );

	  This procedure relies on the two routines ~output_byte and
	  ~output_word to actually write data to the disk.  The procedure
	  OUTPUT refers to this new procedure.

	  Each call to OUTPUT corresponds to a NODE on disk.	This produces
	  the format shown earlier, devoid of definitions and references.


	  To detect sharing, we modify MARK so as to set a ~new bit resident
	  in each block.	The new bit is called the SHARE bit.  We want to set
	  the SHARE bit in a block if there is more than one pointer to it.

	  We modify MARK so that if it encounters a block that is already
	  marked, it sets the SHARE bit.  A block will be encountered once
	  for each pointer to it.  Thus, when two or more pointers point to the
	  same block, that block will be encountered two or more times.  Upon
	  the first encounter, MARK sets the mark bit.	Upon the second
	  encounter, MARK finds that mark bit set, and so MARK now sets the SHARE

	  The sweep phase will ultimately turn off all SHARE bits, like it turns
	  off all mark bits.


	We need to introduce a second MARK procedure, called MARK' (mark-
	  prime).  It is identical to MARK except that it deals not with the
	  mark bit, but with another new bit, called the MARK' bit.

	Why would we want to avoid using the mark bit?  Recall that during the
	sweep, all ~unmarked blocks are rendered free.  When we choose to swap
	out a structure, we need to MARK it, so that we can detect shared
	blocks.  However, we use MARK' instead of MARK so that when we're done,
	we've set no mark bits.	 (We set only MARK' and sometimes SHARE).
	These blocks, which we now output, will continue to be unmarked, and
	hence will be freed up during the sweep.

Swap Out With Sharing

	We modify our OUTPUT procedure so as to turn shared structures into
	definitions and references.  We would like to store in each shared
	block its definition number (the integer 1 in our previous examples).
	This way, whenever OUTPUT encounters a shared block, OUTPUT can simply
	write out this block as a reference, referring to the share block's
	  definition number:

		byte(6)  word( the_definition_number_stored_with_the_shared_block )


	  OUTPUT detects a shared block by noticing its set SHARE bit.  When
	  OUTPUT encounters such a shared block for the first time, it assigns
	  it a new integer definition number.  It turns figure 33.14(a) (a shared
	  block) into part (b) of the figure.  It indeed stores the newly
	  allocated definition number into the block's second bin, but it first
	~saves the old contents of the block.  Those original data are put
	into a newly allocated 4-bin block shown in the figure.  Thus, the
	encountered shared block's:

	     a)   second bin gets the definition number, and
	     b)   first bin gets a pointer to the 4-bin block, and
	     c)   first bin's high-order byte gets a special code.

	OUTPUT then outputs the ~definition:

		byte(5)  word( the_definition_number )

	and calls itself recursively so as to output the structure following
	these data, to form a complete definition.

	When OUTPUT encounters a shared block for the second time, it is
	looking at a block having the "special code".  For this second block,
	and all subsequent encounters, OUTPUT ~doesn't call itself recursivly,
	  rather, it outputs a reference:

		    byte(6)	 word( the_definition_number )

	  The definition number is conveniently available in the present block's
	second bin.

	Thus, OUTPUT now looks like:


			IF  B is NIL  THEN

			EF  B has the "special tag"  THEN
				output_word( B's second bin );

				EF  B has the SHARE bit set  THEN
					  DEFINITION_NUMBER:= a new number ;
					  output_word( DEFINITION_NUMBER );
					  render figure 33.14(a) as 33.14(b)
					  Let C be the address of the 4-bin block:
					    OUTPUT( C );

				EF  ... as before ...  FI


	  After the entire output is done, we need to make one pass thru all the
	  4-bin blocks (which are linked together via the fourth bin).  For each
	  4-bin block, we restore the original data (from bins 1 and 2) into
	  the shared block (referenced in bin 3).	 This completes the writing

	  The 4-bin blocks are ~not part of our 2-bin block space.	They are
	  allocated easily from another piece of memory.  They don't need any
	form of garbage collection, as we free ~all the 4-bin blocks
	precisely when we are done with the output procedure.

		BOX:	What is the SHARE bit for?
		BOX:	What does the OUTPUT procedure do upon seeing a block
		BOX:	with the SHARE bit on?
		BOX:	What is MARK' for?
		    BOX:	Where do we keep a shared block's definition integer?
		BOX:	What are the 4-bin temporary blocks used for?

Swap-In On Demand

	All swapping out occurs during garbage collection, as it tries to free
	up many blocks.  In contrast, swap-in occurs outside the garbage
	collector.  Swap-in occurs on demand, via the coercion introduced for
	DISK types in Section 23.9.  That coercion starts off with a disk node,
	and yields its ACRD.  If the ACRD are absent, then it brings them
	in off disk.

	The given disk node supplies the disk address.  The swap-in process
	reads the diskette starting there, and forms a corresponding structure
	in core consisting entirely of new blocks.  It stuffs the pointer to
	the top of the structure into the disk node's first bin, so that the
	  disk node has ACRD.

	  The heart of the input procedure reads in a NODE off the disk and
	  delivers	its implied structure in core.  It naturally calls itself
	  recursively when it needs to acquire a NODE (e.g., following the


			 DO	CODE:= input_byte;

				IF  CODE=1	"P-block"  THEN
					  A:= INPUT;
					  B:= INPUT;
					  ANSWER:=	a new P-block with A in its first
							bin and B in the second bin;

				EF  CODE=2	"D-block"  THEN
					  A:= INPUT;
					  B:= input_word;
					  ANSWER:=	a new D-block with A in its first
							bin and B in the second bin;

				EF  CODE=3	"Disk node"	 THEN
					  DISK_ADDRESS:=	input_word ;
					  ANSWER:= the disk node having this disk
						     address;  "(more about this later)"

				EF  CODE=4	"NIL"	 THEN
					  ANSWER:= NIL;

				EF  CODE=5	"a defintion"  THEN  see below
				EF  CODE=6	"a reference"  THEN  see below	FI



	  Codes 1, 2, and 4 are straightforward, as shown.

	  Code 3, a disk node, acquires the desired disk address from the disk
	  ("input_word").	 It then looks thru a structure in core called
	  MATURE.  MATURE references all mature disk nodes.  (When we input a
	  disk node off the disk, it is necessarily mature, as it has a disk

	  We search thru MATURE so as to find the disk node whose
	  disk address matches that one just taken in off the disk.	 We yield
	  that disk node as the result of INPUT (the variable ANSWER).

	  If there is presently no disk node in core that has that disk address,
	  we create a new disk node with that disk address.  The new disk node is
	  clean, and has no ACRD.  We deliver this new disk node as our ANSWER,
	  and put it onto the MATURE structure, which keeps track of all mature
	  disk nodes.

	  (For speed, MATURE is an array of lists of disk nodes.
	  Hashing on the disk address indexes into the array, and the list there
	  is then searched for the desired disk node).


	  The remaining two codes, the definition and reference codes, are
	  treated as follows.  We maintain a structure, called ALL_DEFINITIONS,
	  which associates integers (definition numbers) with core-resident

	  Here are the two clauses for those two codes:

		    EF  CODE=5  "definition"	THEN

				DEFINITION_NUMBER:= input_word ;

				ANSWER:= a new, empty block, which we call the "dummy";

				Insert into ALL_DEFINITIONS the association between

				THE_DEFINITION:= INPUT; "Bring in the body of the
								 definition, the NODE"

						    "Make the new, core-resident structure
						     reside at the block ANSWER points to"

		    EF  CODE=6  "reference"  THEN

				DEFINITION_NUMBER:= input_word;

				ANSWER:=  the core-resident structure associated with

	  For definitions (code 5), we introduce a new association into
	  ALL_DEFINITIONS.  Even before we read the NODE part of the definition,
	  we immediately create a dummy block (ANSWER).	 We associate the
	  definition number with the dummy block, ~as ~though ~the ~dummy ~block
	  ~were ~the ~result ~read ~off ~the ~disk.  Then we read the disk
	  resident NODE (via a recursive call to INPUT).

	  Now for the first time, we have the core-resident structure.  We move
	  its top block so as to live now at ANSWER (the dummy block).  This
	  final movement (@) renders honest the association in ALL_DEFINITIONS.

Is The Dummy Block Okay?

	  Fortunately, when ANSWER holds only the dummy, empty block, before
	  the @-assignment, nobody cares about the contents of that block.
	  Nobody cares about that until after the entire INPUT is done.  By then,
	  we've updated the dummy block so as to be the core-resident structure
	read off the disk.

	The need for a dummy block arises only because cyclic structures
	can exist (Section 33.6.2).  For a cyclic structure, there will be a
	~reference to this definition ~before we finish reading the definition.
	That early reference will come to reference the dummy block.

	When we finally @-assign over the dummy block, all cyclic references
	to that dummy will indeed be referencing now the core-resident
	structure built up for this definition.

	Finally, the reference (code 6) case is easy.  It just delivers the
	core-resident structure associated with the given defintion number
	(taken from disk).  That resulting block might be a dummy, within
	a cyclic structure for example.  That dummy block will nonetheless
	become the top block of the structure associated with the definition
	number in the end.

		BOX:	Does the garbage collector initiate swap-in?
		BOX:	Who initiates swap-out?
		BOX:	How is a disk address turned into a disk node?
		BOX:	For what reason do we use a dummy block immediately
		BOX:	upon bringing in a definition?
		BOX:	What happens if garbage collection occurs during the
		BOX:	swapping in of an object?