18. LO pool class¶
18.1. Introduction¶
.readership: Any MPS developer.
.intro: The LO (Leaf Object) pool class is a pool class developed for DylanWorks. It is designed to manage objects that have no references (leaf objects) such as strings, bit tables, etc. It is a garbage collected pool (in that objects allocated in the pool are automatically reclaimed when they are discovered to be unreachable.
Note
Need to sort out issue of alignment. Currently lo grabs alignment
from format, almost certainly “ought” to use the greater of the
format alignment and the MPS_ALIGN
value. David Jones,
1997-07-02.
18.2. Definitions¶
.def.leaf: A “leaf” object is an object that contains no references, or an object all of whose references refer to roots. That is, any references that the object has must refer to a priori alive objects that are guaranteed not to move, hence the references do not need fixing.
.def.grain: A grain (of some alignment) is a contiguous aligned area of memory of the smallest size possible (which is the same size as the alignment).
18.3. Requirements¶
.req.source: See req.dylan.fun.obj.alloc and req.dylan.prot.ffi.access.
.req.leaf: The pool must manage formatted leaf objects (see .def.leaf above for a definition). This is intended to encompass Dylan and C leaf objects. Dylan leaf objects have a reference to their wrapper, but are still leaf objects (in the sense of .def.leaf) because the wrapper will be a root.
.req.nofault: The memory containing objects managed by the pool must not be protected. The client must be allowed to access these objects without using the MPS trampoline (the exception mechanism, q.v.).
18.4. Overview¶
.overview.ms: The LO Pool is a non-moving mark-and-sweep collector.
.overview.ms.justify: Mark-and-sweep pools are simpler than moving pools.
.overview.alloc: Objects are allocated in the pool using the reserve/commit protocol on allocation points.
.overview.format: The pool is formatted. The format of the objects in the pool is specified at instantiation time, using an format object derived from a variant A format (using variant A is overkill, see .if.init below) (see design.mps.format for excuse about calling the variant ‘A’).
18.5. Interface¶
.if.init.args: The init method for this class takes one extra parameter in the vararg parameter list.
.if.init.format: The extra parameter should be an object of type Format and should describe the format of the objects that are to be allocated in the pool.
.if.init.format.use: The pool uses the skip and alignment slots of the format. The skip method is used to determine the length of objects (during reclaim). The alignment field is used to determine the granularity at which memory should be managed.
.if.init.format.a: Currently only format variant A is supported though clearly that is overkill as only skip and alignment are used.
18.6. Data structures¶
.sig: The signature for the LO Pool Class is 0x51970b07 (SIGLOPOoL).
.poolstruct: The class specific pool structure is:
typedef struct LOStruct {
PoolStruct poolStruct; /* generic pool structure */
PoolGenStruct pgenStruct; /* pool generation */
PoolGen pgen; /* NULL or pointer to pgenStruct */
Sig sig; /* <code/misc.h#sig> */
} LOStruct;
.loseg: Every segment is an instance of segment class
LOSegClass
, a subclass of MutatorSegClass
(see
design.mps.seg.over.hierarchy.mutatorseg), and is an object of type
LOSegStruct
.
.loseg.purpose: The purpose of the LOSeg
structure is to
associate the bit tables used for recording allocation and mark
information with the segment.
.loseg.decl: The declaration of the structure is as follows:
typedef struct LOSegStruct {
GCSegStruct gcSegStruct; /* superclass fields must come first */
BT mark; /* mark bit table */
BT alloc; /* alloc bit table */
Count freeGrains; /* free grains */
Count bufferedGrains; /* grains in buffers */
Count newGrains; /* grains allocated since last collection */
Count oldGrains; /* grains allocated prior to last collection */
Sig sig; /* <code/misc.h#sig> */
} LOSegStruct;
.loseg.sig: The signature for a loseg is 0x519705E9 (SIGLOSEG).
.loseg.lo: The lo field points to the LO structure that owns this segment.
.loseg.bit: Bit Tables (see design.mps.bt) are used to record allocation and mark information. This is relatively straightforward, but might be inefficient in terms of space in some circumstances.
.loseg.mark: This is a Bit Table that is used to mark objects
during a trace. Each grain in the segment is associated with 1 bit in
this table. When loSegFix()
(see .fun.fix below) is called the
address is converted to a grain within the segment and the
corresponding bit in this table is set.
.loseg.alloc: This is a Bit Table that is used to record which addresses are allocated. Addresses that are allocated and are not buffered have their corresponding bit in this table set. If a bit in this table is reset then either the address is free or is being buffered.
.loseg.diagram: The following diagram is now obsolete. It’s also not very interesting - but I’ve left the sources in case anyone ever gets around to updating it. tony 1999-12-16
[missing diagram]
18.7. Functions¶
18.7.1. External¶
Note
Explain way in which buffers interact with the alloc table and how it could be improved.
18.7.2. Internal¶
.fun.fix: Fix treats references of most ranks much the same. There
is one mark table that records all marks. A reference of rank
RankAMBIG
is first checked to see if it is aligned to the pool
alignment and discarded if not. The reference is converted to a grain
number within the segment (by subtracting the segments’ base from the
reference and then dividing by the grain size). The bit (the one
corresponding to the grain number) is set in the mark table.
Exception, for a weak reference (rank is RankWEAK
) the mark table
is checked and the reference is fixed to 0 if this address has not
been marked otherwise nothing happens. Note that there is no check
that the reference refers to a valid object boundary (which wouldn’t
be a valid check in the case of ambiguous references anyway).
.fun.segreclaim: For all the contiguous allocated regions in the
segment it locates the boundaries of all the objects in that region by
repeatedly skipping (by calling format->skip
) from the beginning
of the region (the beginning of the region is guaranteed to coincide
with the beginning of an object). For each object it examines the bit
in the mark bit table that corresponds to the beginning of the object.
If that bit is set then the object has been marked as a result of a
previous call to loSegFix()
, the object is preserved by doing
nothing. If that bit is not set then the object has not been marked
and should be reclaimed; the object is reclaimed by resetting the
appropriate range of bits in the segment’s free bit table.
Note
Special things happen for buffered segments.
Explain how the marked variable is used to free segments.
18.8. Attachment¶
[missing attachment “LOGROUP.CWK”]