Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents

Memory Pool System Project

                             LEAF OBJECT POOL CLASS
                               design.mps.poollo
                                 incomplete doc
                                 drj 1997-03-07

    INTRODUCTION

    .readership: Any MPS developer.

    .intro: The Leaf Object Pool Class (LO for short) 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.

    [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 -- @@ drj 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 using
    the MPS trampoline (the exception mechanism, q.v.).

    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 format A variant (using variant A is overkill, see
    .if.init below) (see design.mps.format for excuse about calling the variant
    '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.

    DATASTRUCTURES

    .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

    FUNCTIONS

    External

    .fun.init:

    .fun.destroy:

    .fun.buffer-fill:

    [explain way in which buffers interact with the alloc table and how it could be
    improved]

    .fun.buffer-empty:

    .fun.condemn:

    .fun.fix:

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

    [sketch]
    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.reclaim:

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

    LOReclaim derives the loseg from the seg, and calls loSegReclaim (see
    .fun.segreclaim below).

    Internal

    .fun.segreclaim:

    static void loSegReclaim(LOSeg loseg, Trace trace)

    [sketch]
    for all the contiguous allocated regions in the segment it locates the
    boundaries of all the objects in that region by repeatedly skipping (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.

    [special things happen for buffered segments]

    [explain how the marked variable is used to free segments]

    ATTACHMENT
       "LOGROUP.CWK"

## A. References

## B. Document History

2002-06-07 | RB | Converted from MMInfo database design document.

## C. Copyright and License

This document is copyright © 1995-2002 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.

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.
3. Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

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, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and 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.

`$Id: //info.ravenbrook.com/project/mps/version/1.111/design/poollo/index.html#2 $`

Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents