.. highlight:: none


.. index::
   pair: AWL pool class; design
   single: pool class; AWL design

.. _design-poolawl:


AWL pool class
==============

.. mps:prefix:: design.mps.poolawl
   pair: AWL pool class; design
   single: pool class; AWL design


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

:mps:tag:`readership` Any MPS developer.

:mps:tag:`intro` The AWL (Automatic Weak Linked) pool is used to manage
Dylan Weak Tables (see req.dylan.fun.weak). Currently the design is
specialised for Dylan Weak Tables, but it could be generalised in the
future.


Requirements
------------

See req.dylan.fun.weak.

See meeting.dylan.1997-02-27(0) where many of the requirements for
this pool were first sorted out.

Must satisfy request.dylan.170123_.

.. _request.dylan.170123: https://info.ravenbrook.com/project/mps/import/2001-11-05/mmprevol/request/dylan/170123

:mps:tag:`req.obj-format` Only objects of a certain format need be
supported. This format is a subset of the Dylan Object Format. The
pool uses the first slot in the fixed part of an object to store an
association. See `mail.drj.1997-03-11.12-05`_.

.. _mail.drj.1997-03-11.12-05: https://info.ravenbrook.com/project/mps/mail/1997/03/11/12-05/0.txt


Definitions
-----------

:mps:tag:`def.grain` alignment grain, grain. A grain is a range of addresses
where both the base and the limit of the range are aligned and the
size of range is equal to the (same) alignment. In this context the
alignment is the pool's alignment (``pool->alignment``). The grain is
the unit of allocation, marking, scanning, etc.


Overview
--------

:mps:tag:`overview`

:mps:tag:`overview.ms` The pool is mark and sweep. :mps:tag:`overview.ms.justify`
Mark-sweep pools are slightly easier to write (than moving pools), and
there are no requirements (yet) that this pool be high performance or
moving or anything like that.

:mps:tag:`overview.alloc` It is possible to allocate weak or exact objects
using the normal reserve/commit AP protocol.
:mps:tag:`overview.alloc.justify` Allocation of both weak and exact objects
is required to implement Dylan Weak Tables. Objects are formatted; the
pool uses format A.

:mps:tag:`overview.scan` The pool handles the scanning of weak objects
specially so that when a weak reference is deleted the corresponding
reference in an associated object is deleted. The associated object is
determined by using information stored in the object itself (see
:mps:ref:`.req.obj-format`).


Interface
---------

:mps:tag:`if.init` The init method takes one extra parameter in the vararg
list. This parameter should have type :c:type:`Format` and be a format
object that describes the format of the objects to be allocated in
this pool. The format should support scan and skip methods. There is
an additional restriction on the layout of objects, see
:mps:ref:`.req.obj-format`.

:mps:tag:`if.buffer` The :c:func:`BufferInit()` method takes one extra parameter
in the vararg list. This parameter should be either ``RankEXACT`` or
``RankWEAK``. It determines the rank of the objects allocated using
that buffer.


Data structures
---------------

:mps:tag:`sig` This signature for this pool will be 0x519bla3l (SIGPooLAWL).

:mps:tag:`poolstruct` The class specific pool structure is::

    struct AWLStruct {
      PoolStruct poolStruct;
      PoolGenStruct pgenStruct; /* pool generation */
      PoolGen pgen;             /* NULL or pointer to pgenStruct */
      Count succAccesses;       /* number of successive single accesses */
      FindDependentFunction findDependent; /*  to find a dependent object */
      awlStatTotalStruct stats;
      Sig sig;                  /* <code/misc.h#sig> */
    }

:mps:tag:`awlseg` The pool defines a segment class :c:type:`AWLSegClass`, which is
a subclass of :c:type:`MutatorSegClass` (see
design.mps.seg.over.hierarchy.mutatorseg_). All segments allocated by
the pool are instances of this class, and are of type ``AWLSeg``, for
which the structure is::

    struct AWLSegStruct {
      GCSegStruct gcSegStruct;  /* superclass fields must come first */
      BT mark;
      BT scanned;
      BT alloc;
      Count grains;
      Count freeGrains;         /* free grains */
      Count bufferedGrains;     /* grains in buffers */
      Count newGrains;          /* grains allocated since last collection */
      Count oldGrains;          /* grains allocated prior to last collection */
      Count singleAccesses;     /* number of accesses processed singly */
      awlStatSegStruct stats;
      Sig sig;                  /* <code/misc.h#sig> */
    }

.. _design.mps.seg.over.hierarchy.mutatorseg: seg.html#design.mps.seg.over.hierarchy.mutatorseg

:mps:tag:`awlseg.bt` The ``mark``, ``alloc``, and ``scanned`` fields are
bit-tables (see design.mps.bt_). Each bit in the table corresponds to
a single alignment grain in the pool.

.. _design.mps.bt: bt.html

:mps:tag:`awlseg.mark` The ``mark`` bit table is used to record mark bits
during a trace. :c:func:`awlSegWhiten()` (see :mps:ref:`.fun.whiten` below) sets all
the bits of this table to zero. Fix will read and set bits in this
table. Currently there is only one mark bit table. This means that the
pool can only be condemned for one trace.

:mps:tag:`awlseg.mark.justify` This is simple, and can be improved later
when we want to run more than one trace.

:mps:tag:`awlseg.scanned` The ``scanned`` bit-table is used to note which
objects have been scanned. Scanning (see :mps:ref:`.fun.scan` below) a segment
will find objects that are marked but not scanned, scan each object
found and set the corresponding bits in the scanned table.

:mps:tag:`awlseg.alloc` The ``alloc`` bit table is used to record which
portions of a segment have been allocated. Ranges of bits in this
table are set in :c:func:`awlSegBufferFill()` when a buffer is attached to
the segment. When a buffer is flushed (that is,
:c:func:`awlSegBufferEmpty()` is called) from the segment, the bits
corresponding to the unused portion at the end of the buffer are
reset.

:mps:tag:`awlseg.alloc.invariant` A bit is set in the alloc table if and
only if the corresponding address is currently being buffered, or the
corresponding address lies within the range of an allocated object.

:mps:tag:`awlseg.grains` The ``grains`` field is the number of grains that
fit in the segment. Strictly speaking this is not necessary as it can
be computed from ``SegSize`` and AWL's alignment, however,
precalculating it and storing it in the segment makes the code simpler
by avoiding lots of repeated calculations.

:mps:tag:`awlseg.freeGrains` A conservative estimate of the number of free
grains in the segment. It is always guaranteed to be greater than or
equal to the number of free grains in the segment, hence can be used
during allocation to quickly pass over a segment.

.. note::

    Maintained by blah and blah. Unfinished obviously.


Functions
---------

.. note::

    How will pool collect? It needs an action structure.

External
........

.. c:function:: Res AWLInit(Pool pool, va_list arg)

:mps:tag:`fun.init` :c:type:`AWLStruct` has four fields, each one needs initializing.

:mps:tag:`fun.init.poolstruct` The ``poolStruct`` field has already been
initialized by generic code (impl.c.pool).

:mps:tag:`fun.init.sig` The ``sig`` field will be initialized with the
signature for this pool.

.. c:function:: Res AWLFinish(Pool pool)

:mps:tag:`fun.finish` Iterates over all segments in the pool and destroys
each segment (by calling :c:func:`SegFree()`). Overwrites the sig field in
the :c:type:`AWLStruct`. Finishing the generic pool structure is done by the
generic pool code (impl.c.pool).

:mps:tag:`fun.alloc` :c:func:`PoolNoAlloc()` will be used, as this class does not
implement alloc.

:mps:tag:`fun.free` :c:func:`PoolNoFree()` will be used, as this class does not
implement free.

.. c:function:: Res AWLBufferFill(Seg *segReturn, Addr *baseReturn, Pool pool, Buffer buffer, Size size)

:mps:tag:`fun.fill` This zips round all the segments applying
:c:func:`SegBufferFill()` to each segment. :c:func:`awlSegBufferFill()` attempts
to find a large-enough free range; if it finds one then it may be
bigger than the actual request, in which case the remainder can be
used to "fill" the rest of the buffer. If no free range can be found
in an existing segment then a new segment will be created (which is at
least large enough). The range of buffered addresses is marked as
allocated in the segment's alloc table.

.. c:function:: Res AWLDescribe(Pool pool, mps_lib_FILE *stream, Count depth)

:mps:tag:`fun.describe`


Internal
........

.. c:function:: Res AWLSegCreate(AWLSeg *awlsegReturn, Size size)

:mps:tag:`fun.awlsegcreate` Creates a segment of class :c:type:`AWLSegClass` of size at least ``size``.

:mps:tag:`fun.awlsegcreate.size.round` ``size`` is rounded up to the arena
grain size before requesting the segment.

:mps:tag:`fun.awlsegcreate.size.round.justify` The arena requires that all
segment sizes are rounded up to the arena grain size.

:mps:tag:`fun.awlsegcreate.where` The segment is allocated using a
generation preference, using the generation number stored in the
:c:type:`AWLStruct` (the ``gen`` field), see :mps:ref:`.poolstruct` above.

.. c:function:: Res awlSegInit(Seg seg, Pool pool, Addr base, Size size, ArgList args)

:mps:tag:`fun.awlseginit` Init method for :c:type:`AWLSegClass`, called for
:c:func:`SegAlloc()` whenever an ``AWLSeg`` is created (see
:mps:ref:`.fun.awlsegcreate` above).

:mps:tag:`fun.awlseginit.tables` The segment's mark scanned and alloc tables
(see :mps:ref:`.awlseg.bt` above) are allocated and initialised. The segment's
grains field is computed and stored.

.. c:function:: void awlSegFinish(Seg seg)

:mps:tag:`fun.awlsegfinish` Finish method for :c:type:`AWLSegClass`, called from
:c:func:`SegFree()`. Will free the segment's tables (see :mps:ref:`.awlseg.bt`).

.. c:function:: Bool awlSegBufferFill(Addr *baseReturn, Addr *limitReturn, Seg seg, Size size, RankSet rankSet)

:mps:tag:`fun.seg.buffer-fill` Searches for a free block in the segment that
is at least ``size`` bytes long. The base address of the block is
returned in ``*baseReturn``, the limit of the entire free block (which
must be at least as large as ``size`` and may be bigger) is returned
in ``*limitReturn``. The requested size is converted to a number of
grains, :c:func:`BTFindResRange()` is called to find a run of this length in
the alloc bit-table (:mps:ref:`.awlseg.alloc`). The results (if it is
successful) from :c:func:`BTFindResRange()` are in terms of grains, they are
converted back to addresses before returning the relevant values from
this function.

.. c:function:: void awlSegBufferEmpty(Seg seg, Buffer buffer)

:mps:tag:`fun.seg.buffer-empty` Locates the free portion of the buffer, that
is the memory between the init and the limit of the buffer and records
these locations as being free in the alloc table.

.. c:function:: Res awlSegWhiten(Seg seg, Trace trace)

:mps:tag:`fun.whiten` The current design only permits each segment to be
condemned for one trace (see :mps:ref:`.awlseg.mark`). This function checks
that the segment is not white for any trace (``seg->white ==
TraceSetEMPTY``). The segment's mark bit-table is reset, and the
whiteness of the seg (``seg->white``) has the current trace added to
it.

.. c:function:: void awlSegGreyen(Seg seg, Trace trace)

:mps:tag:`fun.grey` If the segment is not white for this trace, the
segment's mark table is set to all 1s and the segment is recorded as
being grey.

.. c:function:: Res awlSegScan(Bool *totalReturn, Seg seg, ScanState ss)

:mps:tag:`fun.scan`

:mps:tag:`fun.scan.overview` The scanner performs a number of passes over
the segment, scanning each marked and unscanned (grey) object that is
finds.

:mps:tag:`fun.scan.overview.finish` It keeps perform a pass over the segment
until it is finished.

:mps:tag:`fun.scan.overview.finish.condition` A condition for finishing is
that no new marks got placed on objects in this segment during the
pass.

:mps:tag:`fun.scan.overview.finish.approximation` We use an even stronger
condition for finishing that assumes that scanning any object may
introduce marks onto this segment. It is finished when a pass results
in scanning no objects (that is, all objects were either unmarked or
both marked and scanned).

:mps:tag:`fun.scan.overview.finished-flag` There is a flag called
``finished`` which keeps track of whether we should finish or not. We
only ever finish at the end of a pass. At the beginning of a pass the
flag is set. During a pass if any objects are scanned then the
``finished`` flag is reset. At the end of a pass if the ``finished``
flag is still set then we are finished. No more passes take place and
the function returns.

:mps:tag:`fun.scan.pass` A pass consists of a setup phase and a repeated
phase.

:mps:tag:`fun.scan.pass.buffer` The following assumes that in the general
case the segment is buffered; if the segment is not buffered then the
actions that mention buffers are not taken (they are unimportant if
the segment is not buffered).

:mps:tag:`fun.scan.pass.p` The pass uses a cursor called ``p`` to progress
over the segment. During a pass ``p`` will increase from the base
address of the segment to the limit address of the segment. When ``p``
reaches the limit address of the segment, the pass in complete.

:mps:tag:`fun.scan.pass.setup` ``p`` initially points to the base address of
the segment.

:mps:tag:`fun.scan.pass.repeat` The following comprises the repeated phase.
The repeated phase is repeated until the pass completion condition is
true (that is, ``p`` has reached the limit of the segment, see
:mps:ref:`.fun.scan.pass.p` above and :mps:ref:`.fun.scan.pass.repeat.complete`
below).

:mps:tag:`fun.scan.pass.repeat.complete` If ``p`` is equal to the segment's
limit then we are done. We proceed to check whether any further passes
need to be performed (see :mps:ref:`.fun.scan.pass.more` below).

:mps:tag:`fun.scan.pass.repeat.free` If ``!alloc(p)`` (the grain is free)
then increment ``p`` and return to the beginning of the loop.

:mps:tag:`fun.scan.pass.repeat.buffer` If ``p`` is equal to the buffer's
ScanLimit, as returned by :c:func:`BufferScanLimit()`, then set ``p`` equal
to the buffer's Limit, as returned by :c:func:`BufferLimit()` and return to
the beginning of the loop.

:mps:tag:`fun.scan.pass.repeat.object-end` The end of the object is located
using the ``format->skip`` method.

:mps:tag:`fun.scan.pass.repeat.object` if ``mark(p) && !scanned(p)`` then
the object pointed at is marked but not scanned, which means we must
scan it, otherwise we must skip it.

:mps:tag:`fun.scan.pass.repeat.object.dependent` To scan the object the
object we first have to determine if the object has a dependent object (see
:mps:ref:`.req.obj-format`).

:mps:tag:`fun.scan.pass.repeat.object.dependent.expose` If it has a
dependent object then we must expose the segment that the dependent
object is on (only if the dependent object actually points to MPS
managed memory) prior to scanning and cover the segment subsequent to
scanning.

:mps:tag:`fun.scan.pass.repeat.object.dependent.summary` The summary of the
dependent segment must be set to ``RefSetUNIV`` to reflect the fact
that we are allowing it to be written to (and we don't know what gets
written to the segment).

:mps:tag:`fun.scan.pass.repeat.object.scan` The object is then scanned by
calling the format's scan method with base and limit set to the
beginning and end of the object (:mps:tag:`fun.scan.scan.improve.single` A
scan1 format method would make it slightly simpler here). Then the
finished flag is cleared and the bit in the segment's scanned table is
set.

:mps:tag:`fun.scan.pass.repeat.advance` ``p`` is advanced past the object
and we return to the beginning of the loop.

:mps:tag:`fun.scan.pass.more` At the end of a pass the finished flag is
examined.

:mps:tag:`fun.scan.pass.more.not` If the finished flag is set then we are
done (see :mps:ref:`.fun.scan.overview.finished-flag` above), :c:func:`awlSegScan()`
returns.

:mps:tag:`fun.scan.pass.more.so` Otherwise (the finished flag is reset) we
perform another pass (see :mps:ref:`.fun.scan.pass` above).

.. c:function:: Res awlSegFix(Seg seg, ScanState ss, Ref *refIO)

:mps:tag:`fun.fix` If the rank (``ss->rank``) is ``RankAMBIG`` then fix
returns immediately unless the reference is in the segment bounds,
aligned to the pool alignment, and allocated.

The bit in the marked table corresponding to the referenced grain will
be read. If it is already marked then fix returns. Otherwise (the
grain is unmarked), ``ss->wasMarked`` is set to :c:macro:`FALSE` (see
design.mps.fix.was-marked.not_), the remaining actions depend on
whether the rank (``ss->rank``) is ``RankWEAK`` or not. If the rank is
weak then the reference is adjusted to 0 (see design.mps.weakness) and
fix returns. If the rank is something else then the mark bit
corresponding to the referenced grain is set, and the segment is
greyed using :c:func:`SegSetGrey()`.

.. _design.mps.fix.was-marked.not: fix.html#design.mps.fix.was-marked.not

.. c:function:: void awlSegReclaim(Seg seg, Trace trace)

:mps:tag:`fun.reclaim` This iterates over all allocated objects in the
segment and frees objects that are not marked. When this iteration is
complete the marked array is completely reset.

``p`` points to base of segment. Then::

    while(p < SegLimit(seg) {
      if(!alloc(p)) { ++p;continue; }
      q = skip(p) /* q points to just past the object pointed at by p */
      if !marked(p) free(p, q); /* reset the bits in the alloc table from p to q-1 inclusive. */
      p = q
    }

Finally, reset the entire marked array using :c:func:`BTResRange()`.

:mps:tag:`fun.reclaim.improve.pad` Consider filling free ranges with padding
objects. Now reclaim doesn't need to check that the objects are
allocated before skipping them. There may be a corresponding change
for scan as well.

.. c:function:: Bool AWLDependentObject(Addr *objReturn, Addr parent)

:mps:tag:`fun.dependent-object` This function abstracts the association
between an object and its linked dependent (see :mps:ref:`.req.obj-format`).
It currently assumes that objects are Dylan Object formatted according
to design.dylan.container (see analysis.mps.poolawl.dependent.abstract
for suggested improvements). An object has a dependent object iff the
second word of the object, that is, ``((Word *)parent)[1]``, is
non-:c:macro:`NULL`. The dependent object is the object referenced by the
second word and must be a valid object.

This function assumes objects are in Dylan Object Format (see
design.dylan.container). It will check that the first word looks like
a Dylan wrapper pointer. It will check that the wrapper indicates that
the wrapper has a reasonable format (namely at least one fixed field).
If the second word is :c:macro:`NULL` it will return :c:macro:`FALSE`. If the second
word is non-:c:macro:`NULL` then the contents of it will be assigned to
``*objReturn``, and it will return :c:macro:`TRUE`.


Test
----

- must create Dylan objects.
- must create Dylan vectors with at least one fixed field.
- must allocate weak thingies.
- must allocate exact tables.
- must link tables together.
- must populate tables with junk.
- some junk must die.

Use an LO pool and an AWL pool. Three buffers. One buffer for the LO
pool, one exact buffer for the AWL pool, one weak buffer for the AWL
pool.

Initial test will allocate one object from each buffer and then
destroy all buffers and pools and exit