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

Memory Pool System Project

                               GUARDIAN POOLCLASS
                               design.mps.poolmrg
                                 incomplete doc
                                 drj 1997-02-03

    INTRODUCTION

    .readership: Any MPS developer.

    .intro: This is the design of the Guardian PoolClass.  The Guardian PoolClass
    is part of the MPS.  The Guardian PoolClass is internal to the MPS (has no
    client interface) and is used to implement finalization.

    .source: Some of the techniques in paper.dbe93 ("Guardians in a
    Generation-Based Garbage Collector") were used in this design.  Some analysis
    of this design (including various improvements and some more in-depth
    justification) is in analysis.mps.poolmrg.  That document should be understood
    before changing this document.

    It is also helpful to look at design.mps.finalize and design.mps.message.

    GOALS

    .goal.final: The Guardian Pool should support all requirements pertaining to
    finalization.

    REQUIREMENTS

    .req: We have only one requirement pertaining to finalization:

    req.dylan.fun.finalization: Support the Dylan language-level implementation of
    finalized objects: objects are registered, and are finalized in random order
    when they would otherwise have died.  Cycles are broken at random places.
    There is no guarantee of promptness.

    .req.general: However, finalization is a very common piece of functionality
    that is provided by (sophisticated) memory managers, so we can expect other
    clients to request this sort of functionality.

    .anti-req: Is it required that the Guardian Pool return unused segments to the
    arena? (PoolMFS does not do this) (PoolMRG will not do this in its initial
    implementation)

    TERMINOLOGY

    .def.mrg: MRG: The Pool Class's identifier will be MRG.  This stands for
    "Manual Rank Guardian".  The pool is manually managed and implements guardians
    for references of a particular rank (currently just final).

    .def.final.ref: final reference: A reference of rank final (see
    design.mps.type.rank).

    .def.final.object: finalizable object: An object is finalizable with respect to
    a final reference if, since the creation of that reference, there was a point
    in time when no references to the object of lower (that is, stronger) rank were
    reachable from a root.

    .def.final.object.note: Note that this means an object can be finalizable even
    if it is now reachable from the root via exact references.

    .def.finalize: finalize: To finalize an object is to notify the client that the
    object is finalizable.  The client is presumed to be interested in this
    information (typically it will apply some method to the object).

    .def.guardian: guardian: An object allocated in the Guardian Pool.  A guardian
    contains exactly one final reference, and some fields for the pool's internal
    use.  Guardians are used to implement a finalization mechanism.

    OVERVIEW

    .over: The Guardian Pool Class is a PoolClass in the MPS.  It is intended to
    provide the functionality of "finalization".

    .over.internal: The Guardian PoolClass is internal to the MPM, it is not
    intended to have a client interface.  Clients are expected to access the
    functionality provided by this pool (finalization) using a separate MPS
    finalization interface (design.mps.finalize).

    .over.one-size: The Guardian Pool manages objects of a single certain size,
    each object contains a single reference of rank final.

    .over.one-size.justify: This is all that is necessary to meet our requirements
    for finalization.  Whenever an object is registered for finalization, it is
    sufficient to create a single reference of rank final to it.

    .over.queue: A pool maintains a queue of live guardian objects, called (for
    historical reasons) the "entry" queue.  .over.queue.free: The pool also
    maintains a queue of free guardian objects called the "free" queue.
    .over.queue.exit.not: There used to be an "exit" queue, but this is now
    historical and there shouldn't be any current references to it.

    .over.alloc: When guardians are allocated, they are placed on the entry queue.
    Guardians on the entry queue refer to objects that have not yet been shown to
    be finalizable (either the object has references of lower rank than final to
    it, or the MPS has not yet got round to determining that the object is
    finalizable).  .over.message.create: When a guardian is discovered to refer to
    a finalizable object it is removed from the entry queue and becomes a message
    on the space's queue of messages.  .over.message.deliver: When the MPS client
    receives the message the message system arranges for the message to be
    destroyed and the pool reclaims the storage associated with the
    guardian/message.

    .over.scan: When the pool is scanned at rank final each reference will be
    fixed.  If the reference is to an object that was in old arena (before the
    fix), then the object must now be finalizable.  In this case the containing
    guardian will be removed from the entry queue and posted as a message.

    .over.scan.justify: The scanning process is a crucial step necessary for
    implementing finalization.  It is the means by which the MPS detects that
    objects are finalizable.

    .over.message: PoolClassMRG implements a MessageClass (see
    design.mps.message).  All the messages are of one MessageType.  This type is
    MessageTypeFinalization.  Messages are created when objects are discovered to
    be finalizable and destroyed when the MPS client has received the message.

    .over.message.justify: Messages provide a means for the MPS to communicate with
    its client.  Notification of finalization is just such a communication.
    Messages allow the MPS to inform the client of finalization events when it is
    convenient for the MPS to do so (i.e. not in PageFault context).

    .over.manual: Objects in the Guardian Pool are manually managed.
    .over.manual.alloc: They are allocated (by ArenaFinalize when objects are
    registered for finalization.  .over.manual.free: They are freed when the
    associated message is destroyed.
    .over.manual.justify: The lifetime of a guardian object is very easy to
    determine so manual memory management is appropriate.

    PROTOCOLS

    Object Registration

    .protocol.register: There is a protocol by which objects can be registered for
    finalization.  This protocol is handled by the arena module on behalf of
    finalization.  see design.mps.finalize.int.finalize.

    Finalizer Execution

    .protocol.finalizer: If an object is proven to be finalizable then a message to
    this effect will eventually be posted.  A client can receive the message,
    determine what to do about it, and do it.  Typically this would involve calling
    the finalization method for the object, and deleting the message.  Once the
    message is deleted, the object may become recyclable.

    Setup / Destroy

    .protocol.life: An instance of PoolClassMRG is needed in order to support
    finalization, it is called the "final" pool and is attached to the arena (see
    design.mps.finalize.int.arena.struct).  .protocol.life.birth: The final pool is
    created lazily by ArenaFinalize.  .protocol.life.death: The final pool is
    destroyed during ArenaDestroy.

    DATA STRUCTURES

    .guardian:

    The guardian

    .guardian.over: A guardian is an object used to manage the references and other
    datastructures that are used by the pool in order to keep track of which
    objects are registered for finalization, which ones have been finalized, and so
    on.  .guardian.state: A guardian can be in one of four states:
    .guardian.state.enum: The states are Free, Prefinal, Final, PostFinal (referred
    to as MRGGuardianFree, etc. in the implementation).  .guardian.state.free: The
    guardian is free, meaning that it is on the free list for the pool and
    available for allocation.  .guardian.state.prefinal: The guardian is allocated,
    and refers to an object that has not yet been discovered to be finalizable.
    .guardian.state.final: The guardian is allocated, and refers to an object that
    has been shown to be finalizable; this state corresponds to the existence of a
    message.  .guardian.state.postfinal: This state is only used briefly and is
    entirely internal to the pool; the guardian enters this state just after the
    associated message has been destroyed (which happens when the client receives
    the message) and will be freed immediately (whereupon it will enter the Free
    state).  This state is used for checking only (so that MRGFree can check that
    only guardians in this state are being freed).

    .guardian.life-cycle: Guardians go through the following state life-cycle:

    Free -> Prefinal -> Final -> Postfinal -> Free.

    .guardian.two-part: A guardian is a structure consisting abstractly of a link
    part and a reference part.  Concretely, the link part will be a LinkPartStruct,
    and the reference part will be a Word.  The link part is used by the pool, the
    reference part forms the object visible to clients of the pool.  The reference
    part is the reference of Rank FINAL that refers to objects registered for
    finalization and is how the MPS detects finalizable objects.
    .guardian.two-part.union: The LinkPartStruct is a discriminated union of a
    RingStruct and a MessageStruct.  The RingStruct is used when the guardian is
    either Free or Prefinal.  The MessageStruct is used when the guardian is
    Final.  Neither part of the union is used when the guardian is in the Postfinal
    state.
    .guardian.two-part.justify: This may seem a little profligate with space, but
    this is okay as we are not required to make finalization extremely space
    efficient.

    .guardian.parts.separate: The two parts will be stored in separate segments.
    .guardian.parts.separate.justify: This is so that the data structures the pool
    uses to manage the objects can be separated from the objects themselves.  This
    avoids the pool having to manipulate data structures that are on shielded
    segments (analysis.mps.poolmrg.hazard.shield).

    .guardian.assoc: The nth (from the beginning of the segment) ref part in one
    segment will correspond with the nth link part in another segment.  The
    association between the two segments will be managed by the additional fields
    in pool-specific segment subclasses (see .mrgseg).  .guardian.ref: Guardians
    that are either Prefinal or Final are live and have valid references (possibly
    NULL) in their ref parts.  Guardians that are free are dead and always have
    NULL in their ref parts (see .free.overwrite and .scan.free)
    .guardian.ref.free: When freeing an object, it is a pointer to the reference
    part that will be passed (internally in the pool).

    .guardian.init: Guardians are initialized when the pool is grown
    (.alloc.grow).  The initial state has the ref part NULL and the link part is
    attached to the free ring.  Freeing an object returns a guardian to its initial
    state.

    .poolstruct:
    The Pool structure, MRGStruct will have

    .poolstruct.entry: the head of the entry queue.

    .poolstruct.exit: the head of the exit queue.

    .poolstruct.free: a free list.

    .poolstruct.rings: The entry queue, the exit queue, and the free list will all
    use Rings.  Each Ring will be maintained using the link part of the guardian.
    .poolstruct.rings.justify: This is because Rings are convenient to use and are
    well tested.  It is possible to implement all three lists using a singly linked
    list, but the saving is certainly not worth making at this stage.

    .poolstruct.refring: a ring of "ref" segments in use for links or messages (see
    .mrgseg.ref.mrgring below).

    .poolstruct.extend: a precalculated extendby field (see .init.extend).  This
    value is used to determine how large a segment should be requested from the
    Arena for the reference part segment when the pool needs to grow (see
    .alloc.grow.size).  .poolstruct.extend.justify: Calculating a reasonable value
    for this once and remembering it simplifies the allocation (.alloc.grow).

    .poolstruct.init: poolstructs are initialized once for each pool instance by
    MRGInit (.init).  The initial state has all the rings initialized to singleton
    rings, and the extendBy field initialized to some value (see .init.extend).

    .mrgseg:

    The pool defines two segment subclasses: MRGRefSegClass and MRGLinkSegClass.
    Segments of the former class will be used to store the ref parts of guardians,
    segments of the latter will be used to store the link parts of guardians (see
    .guardian.two-part). Segments are always allocated in pairs, with one of each
    class (by function MRGSegPairCreate).  Each segment contains a link to its pair.

    .mrgseg.ref: MRGRefSegClass is a subclass of GCSegClass. Instances are of type
    MRGRefSeg, and contain:

    .mrgseg.ref.mrgring: a field for the ring of ref part segments in the pool.

    .mrgseg.ref.linkseg: a pointer to the paired link segment.

    .mrgseg.ref.grey: a set describing the greyness of the segment for each trace.

    .mrgseg.ref.init: A segment is created and initialized once every time the pool
    is grown (.alloc.grow).  The initial state has the segment ring node
    initialized and attached to the pool's segment ring, the linkseg field points
    to the relevant link segment, the grey field is initialized such that the
    segment is not grey for all traces.

    .mrgseg.link: MRGLinkSegClass is a subclass of SegClass. Instances are of type
    MRGLinkSeg, and contain:

    .mrgseg.link.refseg: a pointer to the paired ref segment. This may be NULL
    during initialization, while the pairing is being established.

    .mrgseg.link.init: The initial state has the linkseg field pointing to the
    relevant ref segment.

    FUNCTIONS

    .check: MRGCheck

      Will check the signatures, the class, and each field of the MRGStruct.  Each
    field is checked as being appropriate for its type.  .check.justify: There are
    no non-trivial invariants that can be easily checked.

    .alloc: [these apply to MRGRegister now. - Pekka 1997-09-19]

    .alloc.grow: If the free list is empty then two new segments will be allocated
    and the free list filled up from them (note that the reference fields of the
    new guardians will need to be overwritten with NULL, see .free.overwrite)
    .alloc.grow.size: The size of the reference part segment will be the pool's
    extendBy (.poolstruct.extend) value.  The link part segment will be whatever
    size is necessary to accommodate N link parts, where N is the number of
    reference parts that fit in the reference part segment.

    .alloc.error: If any of the requests for more resource (there are two; one for
    each of two segments) fail then the successful requests will be retracted and
    the result code from the failing request will be returned.

    .alloc.pop: MRGAlloc will pop a ring node off the free list, and add it to the
    entry queue.

    .free: MRGFree

      MRGFree will remove the guardian from the message queue and add it to the
    free list.  .free.push: The guardian will simply be added to the front of the
    free list (i.e. no keeping the free list in address order or anything like
    that).  .free.inadequate: No attempt will be made to return unused free
    segments to the Arena (although see analysis.mps.poolmrg.improve.free.* for
    suggestions).

    .free.overwrite:
      MRGFree also writes over the reference with NULL.  .free.overwrite.justify:
    This is so that when the segment is subsequently scanned (.scan.free), the
    reference that used to be in the object is not accidentally fixed.

    .init: MRGInit

      Has to initialize the two queues, the free ring, the ref ring, and the
    extendBy field.  .init.extend: The extendBy field is initialized to one
    ArenaAlign() (usually a page).  .init.extend.justify: This is adequate as the
    pool is not expected to grow very quickly.

    .finish: MRGFinish

      Iterate over all the segments, returning all the segments to the Arena.

    .scan: MRGScan

    .scan.trivial: Scan will do nothing (i.e. return immediately) if the tracing
    rank is anything other than final.  [This optimization is missing.
    impl.c.trace.scan.conservative is not a problem because there are no faults on
    these segs, because there are no references into them.  But that's why
    TraceScan can't do it.  - Pekka 1997-09-19]  .scan.trivial.justify:  If the
    rank is lower than final then scanning is detrimental, it will only delay
    finalization.  If the rank is higher than final there is nothing to do, the
    pool only contains final references.

    .scan.guardians: Scan will iterate over all guardians in the segment.  Every
    guardian's reference will be fixed (.scan.free: note that guardians that are on
    the free list have NULL in their reference part).  .scan.wasold: If the object
    referred to had not been fixed previously (i.e. was unmarked) then the object
    is not referenced by a reference of a lower rank (than FINAL) and hence is
    finalizable.  .scan.finalize: The guardian will be finalized.  This entails
    moving the guardian from state Prefinal to Final; it is removed from the entry
    queue and initialized as a message and posted on the arena's message queue.
    .scan.finalize.idempotent: In fact this will only happen if the guardian has
    not already been finalized (which is determined by examining the state of the
    guardian).

    .scan.unordered: Because scanning occurs a segment at a time, the order in
    which objects are finalized is "random" (it cannot be predicted by considering
    only the references between objects registered for finalization).  See
    analysis.mps.poolmrg.improve.semantics for how this can be improved.
    .scan.unordered.justify: Unordered finalization is all that is required.

    (see analysis.mps.poolmrg.improve.scan.nomove for a suggested improvement that
    avoids redundant unlinking and relinking).

    .describe: MRGDescribe

      Will print out the usual blurb.
      Will iterate along each of the entry and exit queues and printout the
    guardians in each.  The location of the guardian and the value of the reference
    in it will be printed out.

    .functions.unused: BufferInit, BufferFill, BufferEmpty, BufferFinish,
    TraceBegin, Condemn, Fix, Reclaim, TraceEnd, Benefit.

      All of these will be unused.

    .functions.trivial: The Grey method of the pool class will be PoolTrivGrey,
    this pool has no further bookkeeping to perform for grey segments.

    TRANSGRESSIONS

    .trans.no-finish: The MRG pool does not trouble itself to tidy up its internal
    rings properly when being destroyed.

    .trans.free-seg: No attempt is made to release free segments to the arena.  A
    suggested strategy for this is as follows:
      - Add a count of free guardians to each segment, and maintain it in
    appropriate places.
      - Add a free segment ring to the pool.
      - In MRGRefSegScan, if the segment is entirely free, don't scan it, but
    instead detach its links from the free ring, and move the segment to the free
    segment ring.
      - At some appropriate point (such as the end of MRGAlloc), destroy free
    segments.
      - In MRGAlloc, if there are no free guardians, check the free segment ring
    before creating a new pair of segments.
    Note that this algorithm would give some slight measure of segment hysteresis.
    It is not the place of the pool to support general segment hysteresis.

    FUTURE

    .future.array: In future, for speed or simplicity, this pool could be rewritten
    to use an array.  See mail.gavinm.1997-09-04.13-08(0).

    TESTS

    .test: [This section is utterly out of date. -- Pekka 1997-09-19] The test
    impl.c.finalcv is similar to the weakness test (see design.mps.weakness,
    impl.c.weakcv [???]).

    Functionality

      This is the functionality to be tested:

      .fun.alloc: Can allocate objects.

      .fun.free: Can free objects that were allocated.

      .prot.write: Can write a reference into an allocated object.

      .prot.read: Can read the reference from an allocated object.

      .promise.faithful: A reference stored in an allocated object will continue to
    refer to the same object.

      .promise.live: A reference stored in an allocated object will preserve the
    object referred to.

      .promise.unreachable: Any objects referred to in finalization messages are
    not (at the time of reading the message) reachable via a chain of ambiguous or
    exact references.  (we will not be able to test this at first as there is no
    messaging interface)

      .promise.try: The Pool will make a "good faith" effort to finalize objects
    that are not reachable via a chain of ambiguous or exact references.

    Attributes

      The following attributes will be tested:

    .attr.none: There are no attribute requirements.

    Implementation

    [New test]
    new test will simply allocate a number of objects in the AMC pool and finalize
    each one, throwing away the reference to the objects.  Churn.

      .test.mpm: The test will use the MPM interface (impl.h.mpm).
    .test.mpm.justify: This is because it is not intended to provide an MPS
    interface to this pool directly, and the MPS interface to finalization has not
    been written yet (impl.h.mps).  .test.mpm.change: Later on it may use the MPS
    interface, in which case, where the following text refers to allocating objects
    in the MRG pool it will need adjusting.

      .test.two-pools: The test will use two pools, an AMC pool, and an MRG pool.

      .test.alloc: A number of objects will be allocated in the MRG pool.
    .test.free: They will then be freed.  This will test .fun.alloc and .fun.free,
    although not very much.

      .test.rw.a: An object, 'A', will be allocated in the AMC pool, a reference to
    it will be kept in a root.  .test.rw.alloc: A number of objects will be
    allocated in the MRG pool.  .test.rw.write: A reference to A will be written
    into each object.  .test.rw.read: The reference in each object will be read and
    checked to see if it refers to A.  .test.rw.free: All the objects will be
    freed.  .test.rw.drop: The reference to A will be dropped.  This will test
    .prot.write and .prot.read.

      .test.promise.fl.alloc: A number of objects will be allocated in the AMC
    pool.  .test.promise.fl.tag: Each object will be tagged uniquely.
    .test.promise.fl.refer: a reference to it will be stored in an object allocated
    in the MRG pool.  .test.promise.fl.churn: A large amount of garbage will be
    allocated in the AMC pool.  Regularly, whilst this garbage is being allocated,
    a check will be performed that all the objects allocated in the MRG pool refer
    to valid objects and that they still refer to the same objects.  All objects
    from the MRG pool will then be freed (thus dropping all references to the AMC
    objects).  This will test .promise.faithful and .promise.live.

      .test.promise.ut.not: The following part of the test has not implemented.
    This is because the messaging system has not yet been implemented.
      .test.promise.ut.alloc: A number of objects will be allocated in the AMC
    pool.  .test.promise.ut.refer: Each object will be referred to by a root and
    also referred to by an object allocated in the MRG pool.  .test.promise.ut.drop
    : References to a random selection of the objects from the AMC pool will be
    deleted from the root.  .test.promise.ut.churn: A large amount of garbage will
    be allocated in the AMC pool.  .test.promise.ut.message: The message interface
    will be used to receive finalization messages.  .test.promise.ut.final.check:
    For each finalization message received it will check that the object referenced
    in the message is not referred to in the root.  .test.promise.ut.nofinal.check:
    After some amount of garbage has been allocated it will check to see if any
    objects are not in the root and haven't been finalized.  This will test
    .promise.unreachable and .promise.try.

    NOTES

    .access.inadequate: PoolAccess will scan segments at Rank Exact.  Really it
    should be scanned at whatever the minimum rank of all grey segments is (the
    trace rank phase), however there is no way to find this out.  As a consequence
    we will sometimes scan pages at Rank exact when the pages could have been
    scanned at Rank final.  This means that finalization of some objects may
    sometimes get delayed.

## 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/poolmrg/index.html#2 $`

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