CHAPTER 33
AUTOMATIC MEMORY MANAGEMENT
IN CONJUNCTION WITH THE DISK
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).
33.1
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.
33.2
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:
BOX: Can core point to the disk?
BOX:
BOX: Does MARK always mark a disk node's ACRD whenever
BOX: encountering the disk node itself?
33.2.1
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
data.
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.
33.2.2
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
core.
33.2.3
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:
TYPE BOOK = [ TITLE: TEXT
CONTENTS: BIG_TEXT ];
TYPE BIG_TEXT = DISK 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 ) :
BEGIN VAR CONTENTS = TEXT;
CONTENTS:= B.CONTENTS; "This swaps in B's contents"
do something with CONTENTS
END
ENDDEFN
The assignment into CONTENTS swaps in the book B's contents TEXT (due
to the coercion:
~BIG_TEXT -> ~TEXT
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:
BOX: Does an infant disk node have an associated disk
BOX: address?
BOX:
BOX: What savings do infant disk nodes provide?
33.2.4
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).
33.2.4.1
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
33.5(b)).
33.2.4.2
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).
33.2.4.3
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
RPLACD.
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
upward.
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:
BOX: What is the difference between clean and dirty disk
BOX: nodes?
BOX:
BOX: When an infant matures, does it become a clean or a
BOX: dirty mature disk node?
BOX:
BOX: What causes dirtiness?
BOX:
BOX: How is dirtiness propogated upward thru disk nodes'
BOX: ACRD?
33.3
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.
33.3.1
Age
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
requested.
33.3.2
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
sizes.
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
ACRD.
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.
33.3.3
The List MEMORY_RESIDENT
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.
33.3.4
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.
33.3.5
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:
BOX: When is a disk node's ACRD locked in memory?
BOX:
BOX: In what order is the list MEMORY_RESIDENT kept?
BOX:
BOX: What portion of the list MEMORY_RESIDENT references
BOX: disk nodes whose ACRD will be kept?
33.4
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
core-resident.
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
MEMORY_RESIDENT).
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
disk.
We release all the disk nodes' ACRD (remaining on MEMORY_RESIDENT)
except for:
a) ACRD that are locked in core (Section 33.3.5)
and
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)
above).
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
discarded.
Thus, we retain only disk nodes that are accessible from core-resident
data.
Phase 5
The fifth phase is:
5) Collect up all disk nodes with ACRD (a subset of the list
MEMORY_RESIDENT).
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
collection.
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
Summary
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:
BOX: Why must an infant be matured if we choose not to
BOX: retain its ACRD?
BOX:
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:
BOX: Why can we discard unmarked disk nodes?
BOX:
BOX: When is the list MEMORY_RESIDENT rendered ordered
BOX: properly for use within this garbage collection?
33.5
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.
33.6
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:
byte(N)
to denote a byte whose value is N. Similarly:
word(N)
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
representations.
BOX: Does a pointer, or what it points to, get written to
BOX: disk?
BOX:
BOX: What form of NODE represents a pointer to another
BOX: disk-resident structure?
33.6.1
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)
word(1)
33.6.2
A Cycle
Figure 33.13 shows a single block involved in a cycle. Every reachable
cycle has a shared block within it (Section 9.7.3.1). 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
is:
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:
BOX: What code is used to refer to a shared block via
BOX: that integer?
BOX:
BOX: Is there a special code to deal with cycles?
33.7
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:
DEFINE OUTPUT( B: BLOCK ):
IF B is NIL THEN
output_byte(4);
EF B is a P-block THEN
output_byte(1);
OUTPUT( B's first bin's pointer );
OUTPUT( B's second bin's pointer );
EF B is a D-block THEN
output_byte(2);
OUTPUT( B's first bin's pointer );
output_word( B's second bin );
EF B is a disk node THEN
output_byte(3);
output_word( B's second bin
"(the disk address)" );
FI
ENDDEFN
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.
33.7.1
The SHARE Bit
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
bit.
The sweep phase will ultimately turn off all SHARE bits, like it turns
off all mark bits.
33.7.2
MARK'
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.
33.7.3
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:
DEFINE OUTPUT( B: BLOCK ):
IF B is NIL THEN
output_byte(4);
EF B has the "special tag" THEN
output_byte(6);
output_word( B's second bin );
EF B has the SHARE bit set THEN
output_byte(5);
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
ENDDEFN
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
process.
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:
BOX: What does the OUTPUT procedure do upon seeing a block
BOX: with the SHARE bit on?
BOX:
BOX: What is MARK' for?
BOX:
BOX: Where do we keep a shared block's definition integer?
BOX:
BOX: What are the 4-bin temporary blocks used for?
33.8
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
"byte(1)").:
DEFINE INPUT = BLOCK:
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
GIVE ANSWER
ENDDEFN
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
address).
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).
33.8.1
ALL_DEFINITIONS
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
structures.
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
DEFINITION_NUMBER and ANSWER
THE_DEFINITION:= INPUT; "Bring in the body of the
definition, the NODE"
@(ANSWER) := THE_DEFINITION;
"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
DEFINITION_NUMBER, taken from ALL_DEFINITIONS
FI
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.
33.8.2
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:
BOX: Who initiates swap-out?
BOX:
BOX: How is a disk address turned into a disk node?
BOX:
BOX: For what reason do we use a dummy block immediately
BOX: upon bringing in a definition?
BOX:
BOX: What happens if garbage collection occurs during the
BOX: swapping in of an object?