.. mode: -*- rst -*-

MRG pool class
==============

:Tag: design.mps.poolmrg
:Author: David Jones
:Date: 1997-02-03
:Status: incomplete document
:Revision: $Id: //info.ravenbrook.com/project/mps/version/1.113/design/poolmrg.txt#1 $
:Copyright: See `Copyright and License`_.
:Index terms:
   pair: MRG pool class; design
   single: pool class; MRG design


Introduction
------------

_`.readership`: Any MPS developer.

_`.intro`: This is the design of the MRG (Manual Rank Guardian) pool
class. The MRG pool class is part of the MPS. The MRG pool class 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 MRG pool class 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 MRG pool class return
unused segments to the arena? MFS, for example, does not do this. MRG
will not do this in its initial implementation.


Terminology
-----------

_`.def.mrg`: **MRG**: The MRG 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 MRG
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 MRG pool class is a pool class in the MPS. It is
intended to provide the functionality of "finalization".

_`.over.internal`: The MRG pool class 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 MRG pool class manages objects of a single
size, each object containing 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 list of live guardian objects,
called (for historical reasons) the "entry" list.

_`.over.queue.free`: The pool also maintains a list of free guardian
objects called the "free" list.

_`.over.queue.exit.not`: There used to be an "exit" list, 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 list. Guardians on the entry list 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 list and becomes a
message on the arena's messages queue.

_`.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 unmarked object (before the
fix), then the object must now be finalizable. In this case the
containing guardian will be removed from the entry list 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 MRG 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 data structures 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. It
   is on the entry list for the pool.

#. _`.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 is a
``LinkPartStruct``, and the reference part is a ``RefPartStruct``
(which is just 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 ``RankFINAL`` 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`: Ref part number *n* (from the beginning of the
segment) in one segment will correspond with link part number *n* 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 list.

- _`.poolstruct.free`: the head of the free list.

- _`.poolstruct.rings`: The entry list, the exit list, and the free
  list will each be implemented as a ``Ring``. 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 the 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
---------

``Bool MRGCheck(MRG mrg)``

_`.check`: 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.

``Res MRGRegister(Pool pool, Ref ref)``

_`.alloc`: Add a guardian for ``ref``.

_`.alloc.grow`: If the free list is empty then two new segments are
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`: ``MRGRegister()`` pops a ring node off the free list,
and add it to the entry list.

``Res MRGDeregister(Pool pool, Ref obj)``

_`.free`: 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 (that is, 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`: ``MRGDeregister()`` 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.

``Res MRGInit(Pool pool, ArgList args)``

_`.init`: Initializes the entry list, 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.

``void MRGFinish(Pool pool)``

_`.finish`: Iterate over all the segments, returning all the segments
to the arena.

``Res MRGScan(Bool *totalReturn, ScanState ss, Pool pool, Seg seg)``

_`.scan`: ``MRGScan()`` scans a segment.

_`.scan.trivial`: Scan will do nothing (that is, return immediately)
if the tracing rank is anything other than final.

.. note::

    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 P. Pirinen, 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`: ``MRGScan()`` 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 (that is, was unmarked) then the object is not referenced
by a reference of a lower rank (than ``RankFINAL``) 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 list 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.

``Res MRGDescribe(Pool pool, mps_lib_FILE *stream)``

_`.describe`: Describes an MRG pool. Iterates along each of the entry
and exit lists and prints the guardians in each. The location of the
guardian and the value of the reference in it will be printed out.

_`.functions.unused`: All of these will be unused: ``BufferInit()``,
``BufferFill()``, ``BufferEmpty()``, ``BufferFinish()``,
``TraceBegin()``, ``TraceCondemn()``, ``PoolFix()``, ``PoolReclaim()``, ``TraceEnd()``.

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

.. note::

    This section is utterly out of date. Pekka P. Pirinen, 1997-09-19.

_`.test`: 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
..............

The 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
`RankEXACT``. 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
``RankEXACT`` when the pages could have been scanned at ``RankFINAL``.
This means that finalization of some objects may sometimes get
delayed.


Document History
----------------

- 1997-02-03 David Jones. Incomplete document.

- 2002-06-07 RB_ Converted from MMInfo database design document.

- 2013-05-23 GDR_ Converted to reStructuredText; some modernization
  (``MRGAlloc()`` and ``MRGFree()`` are now ``MRGRegister()`` and
  ``MRGDeregister()`` respectively; write "list" for "queue").

.. _RB: http://www.ravenbrook.com/consultants/rb/
.. _GDR: http://www.ravenbrook.com/consultants/gdr/


Copyright and License
---------------------

Copyright © 2013-2014 Ravenbrook Limited. All rights reserved.
<http://www.ravenbrook.com/>. 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:

#. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

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

#. Redistributions in any form must be accompanied by information on how
   to obtain complete source code for 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.**
