23. LO pool class

23.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.

23.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).

23.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.).

23.4. Overview

.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’).

23.5. Interface

.if.init:

.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.

23.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 */
  Format format;                /* format for allocated objects */
  Shift alignShift;
  Sig sig;                      /* impl.h.misc.sig */
} LOStruct;

.poolstruct.format: This is the format of the objects that are allocated in the pool.

.poolstruct.alignShift: This is shift used in alignment computations. It is SizeLog2(pool->alignment). It can be used on the right of a shift operator (<< or >>) to convert between a number of bytes and a number of grains.

.loseg: Every segment is an instance of segment class LOSegClass, a subclass of GCSegClass, 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 */
  LO lo;                    /* owning LO */
  BT mark;                  /* mark bit table */
  BT alloc;                 /* alloc bit table */
  Count free;               /* number of free grains */
  Sig sig;                  /* impl.h.misc.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 LOFix() (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]

23.7. Functions

23.7.1. External

.fun.init:

.fun.destroy:

.fun.buffer-fill:

Note

Explain way in which buffers interact with the alloc table and how it could be improved.

.fun.buffer-empty:

.fun.condemn:

Res LOFix(Pool pool, ScanState ss, Seg seg, Ref *refIO)

.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).

void LOReclaim(Pool pool, Trace trace, Seg seg)

.fun.reclaim: Derives the loseg from the seg, and calls loSegReclaim() (see .fun.segreclaim below).

23.7.2. Internal

void loSegReclaim(LOSeg loseg, Trace trace)

.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 LOFix(), 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.

23.8. Attachment

[missing attachment “LOGROUP.CWK”]