.. mode: -*- rst -*- LO pool class ============= :Tag: design.mps.poollo :Author: David Jones :Date: 1997-03-07 :Status: incomplete document :Revision: $Id: //info.ravenbrook.com/project/mps/master/design/poollo.txt#13 $ :Copyright: See `Copyright and License`_. :Index terms: pair: LO pool class; design single: pool class; LO design 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. 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). 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 hitting an MPS barrier. 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 a 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'). 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. 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; /* */ } 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``. .. _design.mps.seg.over.hierarchy.mutatorseg: seg#.over.hierarchy.mutatorseg _`.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; /* */ } 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. .. _design.mps.bt: bt _`.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] Functions --------- 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`: Internal ........ ``Res loSegFix(Seg seg, ScanState ss, 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 loSegReclaim(Seg seg, 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 ``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. Attachment ---------- [missing attachment "LOGROUP.CWK"] Document History ---------------- - 1997-03-07 David Jones. Incomplete document. - 2002-06-07 RB_ Converted from MMInfo database design document. - 2013-05-23 GDR_ Converted to reStructuredText. .. _RB: https://www.ravenbrook.com/consultants/rb/ .. _GDR: https://www.ravenbrook.com/consultants/gdr/ Copyright and License --------------------- Copyright © 2013–2020 `Ravenbrook Limited `_. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.