.. highlight:: none


.. index::
   pair: arena; design

.. _design-arena:


Arena
=====

.. mps:prefix:: design.mps.arena


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

:mps:tag:`intro` This is the design of the arena structure.

:mps:tag:`readership` MPS developers.


Overview
--------

:mps:tag:`overview` The arena serves two purposes. It is a structure that is
the top-level state of the MPS, and as such contains a lot of fields
which are considered "global". And it provides raw memory to pools.

An arena belongs to a particular arena class. The class is selected
when the arena is created. Classes encapsulate both policy (such as
how pool placement preferences map into actual placement) and
mechanism (such as where the memory originates: operating system
virtual memory, client provided, or via malloc). Some behaviour
(mostly serving the "top-level datastructure" purpose) is implemented
by generic arena code, and some by arena class code.


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

:mps:tag:`def.grain` The arena manages memory in units called *arena
grains*, whose size is returned by the macro :c:func:`ArenaGrainSize()`.
Memory allocated by :c:func:`ArenaAlloc()` is a contiguous sequence of arena
grains, whose base address and size are multiples of the arena grain
size.

:mps:tag:`def.tract` A tract is a data structure containing information
about a region of address space: which pool it belongs to (if any),
which segment contains it, and so on. Tracts are the hook on which the
segment module is implemented. Pools which don't use segments may use
tracts for associating their own data with ranges of address.



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

.. note::

    Where do these come from? Need to identify and document the
    sources of requirements so that they are traceable to client
    requirements. Most of these come from the architectural design
    (design.mps.architecture) or the fix function design
    (design.mps.fix_). Richard Brooksby, 1995-08-28.

    They were copied from design.mps.arena.vm_ and edited slightly.
    David Jones, 1999-06-23.

    .. _design.mps.fix: fix.html
    .. _design.mps.arena.vm: arenavm.html


Block management
................

:mps:tag:`req.fun.block.alloc` The arena must provide allocation of
contiguous blocks of memory.

:mps:tag:`req.fun.block.free` It must also provide freeing of contiguously
allocated blocks owned by a pool, whether or not the block was
allocated via a single request.

:mps:tag:`req.attr.block.size.min` The arena must support management of
blocks down to the larger of (i) the grain size of the virtual mapping
interface (if a virtual memory interface is being used); and (ii) the
grain size of the memory protection interface (if protection is used).

.. note::

    On all the operating systems we support, these grain sizes are the
    same and are equal to the operating system page size. But we want
    the MPS to remain flexible enough to be ported to operating
    systems where these are different.

:mps:tag:`req.attr.block.size.max` It must also support management of blocks
up to the maximum size allowed by the combination of operating system
and architecture. This is derived from req.dylan.attr.obj.max (at
least).

:mps:tag:`req.attr.block.align.min` The alignment of blocks shall not be less
than :c:macro:`MPS_PF_ALIGN` for the architecture. This is so that pool
classes can conveniently guarantee pool allocated blocks are aligned
to :c:macro:`MPS_PF_ALIGN`. (A trivial requirement.)


Address translation
...................

:mps:tag:`req.fun.trans` The arena must provide a translation from any
address to the following information:

:mps:tag:`req.fun.trans.arena` Whether the address is managed by the arena.

:mps:tag:`req.fun.trans.pool` Whether the address is managed by a pool
within the arena, and if it is, the pool.

:mps:tag:`req.fun.trans.arbitrary` If the address is managed by a pool, an
arbitrary pointer value that the pool can associate with a group of
contiguous addresses at any time.

:mps:tag:`req.fun.trans.white` If the address is managed by an automatic
pool, the set of traces for which the address is white. This is
required so that the second-stage fix protocol can reject non-white
addresses quickly. See design.mps.critical-path_.

.. _design.mps.critical-path: critical-path.html

:mps:tag:`req.attr.trans.time` The translation shall take no more than @@@@
[something not very large -- drj 1999-06-23]


Arena partition
...............

:mps:tag:`req.fun.set` The arena must provide a method for approximating
sets of addresses.

:mps:tag:`req.fun.set.time` The determination of membership shall take no
more than @@@@ [something very small indeed]. (the non-obvious
solution is refsets)


Constraints
...........

:mps:tag:`req.attr.space.overhead` req.dylan.attr.space.struct implies that
the arena must limit the space overhead. The arena is not the only
part that introduces an overhead (pool classes being the next most
obvious), so multiple parts must cooperate in order to meet the
ultimate requirements.

:mps:tag:`req.attr.time.overhead` Time overhead constraint?

.. note::

    How can there be a time "overhead" on a necessary component? David
    Jones, 1999-06-23.


Architecture
------------

Statics
.......

:mps:tag:`static` There is no higher-level data structure than a arena, so in
order to support several arenas, we have to have some static data in
impl.c.arena. See impl.c.arena.static.

:mps:tag:`static.init` All the static data items are initialized when the
first arena is created.

:mps:tag:`static.serial` ``arenaSerial`` is a static :c:type:`Serial`, containing
the serial number of the next arena to be created. The serial of any
existing arena is less than this.

:mps:tag:`static.ring` ``arenaRing`` is the sentinel of the ring of arenas.

:mps:tag:`static.ring.init` ``arenaRingInit`` is a :c:type:`Bool` showing whether
the ring of arenas has been initialized.

:mps:tag:`static.ring.lock` The ring of arenas has to be locked when
traversing the ring, to prevent arenas being added or removed. This is
achieved by using the (non-recursive) global lock facility, provided
by the lock module.

:mps:tag:`static.check` The statics are checked each time any arena is
checked.


Arena classes
.............

.. c:type:: mps_arena_s *Arena

:mps:tag:`class` The :c:type:`Arena` data structure is designed to be subclassable
(see design.mps.protocol_). Clients can select what arena class
they'd like when instantiating one with :c:func:`mps_arena_create_k()`. The
arguments to :c:func:`mps_arena_create_k()` are class-dependent.

.. _design.mps.protocol: protocol.html

:mps:tag:`class.fields` The ``grainSize`` (for allocation and freeing) and
``zoneShift`` (for computing zone sizes and what zone an address is
in) fields in the arena are the responsibility of the each class, and
are initialized by the ``init`` method. The responsibility for
maintaining the ``commitLimit``, ``spareCommitted``, and
``spareCommitLimit`` fields is shared between the (generic) arena and
the arena class. ``commitLimit`` (see :mps:ref:`.commit-limit`) is changed by
the generic arena code, but arena classes are responsible for ensuring
the semantics. For ``spareCommitted`` and ``spareCommitLimit`` see
:mps:ref:`.spare-committed` below.

:mps:tag:`class.abstract` The basic arena class (:c:type:`AbstractArenaClass`) is
abstract and must not be instantiated. It provides little useful
behaviour, and exists primarily as the root of the tree of arena
classes. Each concrete class must specialize each of the class method
fields, with the exception of the describe method (which has a trivial
implementation) and the ``extend``, ``retract`` and
``spareCommitExceeded`` methods which have non-callable methods for
the benefit of arena classes which don't implement these features.


Chunks
......

:mps:tag:`chunk` Each contiguous region of address space managed by the MPS
is represented by a *chunk*.

:mps:tag:`chunk.tracts` A chunk contains a table of tracts. See
:mps:ref:`.tract.table`.

:mps:tag:`chunk.lookup` Looking of the chunk of an address is the first
step in the second-stage fix operation, and so on the critical path.
See design.mps.critical-path_.

:mps:tag:`chunk.tree` For efficient lookup, chunks are stored in a balanced
tree; ``arena->chunkTree`` points to the root of the tree. Operations
on this tree must ensure that the tree remains balanced, otherwise
performance degrades badly with many chunks.

:mps:tag:`chunk.insert` New chunks are inserted into the tree by calling
:c:func:`ArenaChunkInsert()`. This calls :c:func:`TreeInsert()`, followed by
:c:func:`TreeBalance()` to ensure that the tree is balanced.

:mps:tag:`chunk.delete` There is no corresponding function
:c:func:`ArenaChunkDelete()`. Instead, deletions from the chunk tree are
carried out by calling :c:func:`TreeToVine()`, iterating over the vine
(where deletion is possible, if care is taken) and then calling
:c:func:`TreeBalance()` on the remaining tree. The function
:c:func:`TreeTraverseAndDelete()` implements this.

:mps:tag:`chunk.delete.justify` This is because we don't have a function
that deletes an item from a balanced tree efficiently, and because all
functions that delete chunks do so in a loop over the chunks (so the
best we can do is O(*n*) time in any case).

:mps:tag:`chunk.delete.tricky` Deleting chunks from the chunk tree is tricky
in the virtual memory arena because :c:func:`vmChunkDestroy()` unmaps the
memory containing the chunk, which includes the tree node. So the next
chunk must be looked up before deleting the current chunk. The function
:c:func:`TreeTraverseAndDelete()` ensures that this is done.


Tracts
......

:mps:tag:`tract.table` The arena maintains tables of tract structures such
that every address managed by the arena belongs to exactly one tract.

:mps:tag:`tract.size` Each tract covers exactly one arena grain. This is an
implementation detail, not a requirement.

:mps:tag:`tract.structure` The tract structure definition looks like this::

    typedef struct TractStruct { /* Tract structure */
      Pool pool;      /* MUST BE FIRST <design/arena#.tract.field.pool> */
      Seg seg;                     /* NULL or segment containing tract */
      Addr base;                   /* Base address of the tract */
    } TractStruct;

:mps:tag:`tract.field.pool` The pool field indicates to which pool the tract
has been allocated (:mps:ref:`.req.fun.trans.pool`). Tracts are only valid
when they are allocated to pools. When tracts are not allocated to
pools, arena classes are free to reuse tract objects in undefined
ways. A standard technique is for arena class implementations to
internally describe the objects as a union type of :c:type:`TractStruct` and
some private representation, and to set the pool field to :c:macro:`NULL`
when the tract is not allocated. The pool field must come first so
that the private representation can share a common prefix with
:c:type:`TractStruct`. This permits arena classes to determine from their
private representation whether such an object is allocated or not,
without requiring an extra field.

:mps:tag:`tract.field.seg` The seg field is a pointer to the segment
containing the tract, or :c:macro:`NULL` if the tract is not contained in any
segment.

:mps:tag:`tract.field.base` The base field contains the base address of the
memory represented by the tract.

:mps:tag:`tract.limit` The limit of the tract's memory may be determined by
adding the arena grain size to the base address.

:mps:tag:`tract.iteration` Iteration over tracts is described in
design.mps.arena.tract-iter(0).

.. c:function:: Bool TractOfAddr(Tract *tractReturn, Arena arena, Addr addr)

:mps:tag:`tract.if.tractofaddr` The function :c:func:`TractOfAddr()` finds the
tract corresponding to an address in memory. (See :mps:ref:`.req.fun.trans`.)
If ``addr`` is an address which has been allocated to some pool, then
:c:func:`TractOfAddr()` returns :c:macro:`TRUE`, and sets ``*tractReturn`` to the
tract corresponding to that address. Otherwise, it returns :c:macro:`FALSE`.
This function is similar to :c:func:`TractOfBaseAddr()` (see
design.mps.arena.tract-iter.if.contig-base) but serves a more general
purpose and is less efficient.


Control pool
............

:mps:tag:`pool` Each arena has a "control pool",
``arena->controlPoolStruct``, which is used for allocating MPS control
data structures by calling :c:func:`ControlAlloc()`.


Polling
.......

:mps:tag:`poll` :c:func:`ArenaPoll()` is called "often" by other code (for instance,
on buffer fill or allocation). It is the entry point for doing tracing
work. If the polling clock exceeds a set threshold, and we're not
already doing some tracing work (that is, ``insidePoll`` is not set),
it calls :c:func:`TracePoll()` on all busy traces.

:mps:tag:`poll.size` The actual clock is ``arena->fillMutatorSize``. This is
because internal allocation is only significant when copy segments are
being allocated, and we don't want to have the pause times to shrink
because of that. There is no current requirement for the trace rate to
guard against running out of memory.

.. note::

    Clearly it really ought to: we have a requirement to not run out
    of memory (see req.dylan.prot.fail-alloc, req.dylan.prot.consult),
    and emergency tracing should not be our only story. David Jones,
    1999-06-22.

:c:func:`BufferEmpty()` is not taken into account, because the splinter will
rarely be useable for allocation and we are wary of the clock running
backward.

:mps:tag:`poll.clamp` Polling is disabled when the arena is "clamped", in
which case ``arena->clamped`` is :c:macro:`TRUE`. Clamping the arena prevents
background tracing work, and further new garbage collections from
starting. Clamping and releasing are implemented by the :c:func:`ArenaClamp()`
and :c:func:`ArenaRelease()` methods.

:mps:tag:`poll.park` The arena is "parked" by clamping it, then polling until
there are no active traces. This finishes all the active collections
and prevents further collection. Parking is implemented by the
:c:func:`ArenaPark()` method.


Commit limit
............

:mps:tag:`commit-limit` The arena supports a client configurable "commit
limit" which is a limit on the total amount of committed memory. The
generic arena structure contains a field to hold the value of the
commit limit and the implementation provides two functions for
manipulating it: :c:func:`ArenaCommitLimit()` to read it, and
:c:func:`ArenaSetCommitLimit()` to set it. Actually abiding by the contract of
not committing more memory than the commit limit is left up to the
individual arena classes.

:mps:tag:`commit-limit.err` When allocation from the arena would otherwise
succeed but cause the MPS to use more committed memory than specified
by the commit limit :c:func:`ArenaAlloc()` should refuse the request and
return ``ResCOMMIT_LIMIT``.

:mps:tag:`commit-limit.err.multi` In the case where an :c:func:`ArenaAlloc()` request
cannot be fulfilled for more than one reason including exceeding the
commit limit then class implementations should strive to return a
result code other than ``ResCOMMIT_LIMIT``. That is,
``ResCOMMIT_LIMIT`` should only be returned if the *only* reason for
failing the :c:func:`ArenaAlloc()` request is that the commit limit would be
exceeded. The client documentation allows implementations to be
ambiguous with respect to which result code in returned in such a
situation however.


Spare committed (aka "hysteresis")
..................................

:mps:tag:`spare-committed` See :c:func:`mps_arena_spare_committed()`. The generic
arena structure contains two fields for the spare committed memory
fund: ``spareCommitted`` records the total number of spare committed
bytes; ``spareCommitLimit`` records the limit (set by the user) on the
amount of spare committed memory. ``spareCommitted`` is modified by
the arena class but its value is used by the generic arena code. There
are two uses: a getter function for this value is provided through the
MPS interface (:c:func:`mps_arena_spare_commit_limit()`), and by the
:c:func:`ArenaSetSpareCommitLimit()` function to determine whether the
amount of spare committed memory needs to be reduced.
``spareCommitLimit`` is manipulated by generic arena code, however the
associated semantics are the responsibility of the class. It is the
class's responsibility to ensure that it doesn't use more spare
committed bytes than the value in ``spareCommitLimit``.

:mps:tag:`spare-commit-limit` The function :c:func:`ArenaSetSpareCommitLimit()` sets
the ``spareCommitLimit`` field. If the limit is set to a value lower
than the amount of spare committed memory (stored in
``spareCommitted``) then the class specific function
``spareCommitExceeded`` is called.


Pause time control
..................

:mps:tag:`pause-time` The generic arena structure contains the field
``pauseTime`` for the maximum time any operation in the arena may take
before returning to the mutator. This value is used by
:c:func:`PolicyPollAgain()` to decide whether to do another unit of tracing
work. The MPS interface provides getter (:c:func:`mps_arena_pause_time()`)
and setter (:c:func:`mps_arena_pause_time_set()`) functions.


Locks
.....

:mps:tag:`lock.ring` :c:func:`ArenaAccess()` is called when we fault on a barrier.
The first thing it does is claim the non-recursive global lock to
protect the arena ring (see design.mps.lock(0)).

:mps:tag:`lock.arena` After the arena ring lock is claimed, :c:func:`ArenaEnter()` is
called on one or more arenas. This claims the lock for that arena.
When the correct arena is identified or we run out of arenas, the lock
on the ring is released.

:mps:tag:`lock.avoid` Deadlocking is avoided as described below:

:mps:tag:`lock.avoid.mps` Firstly we require the MPS not to fault (that is,
when any of these locks are held by a thread, that thread does not
fault).

:mps:tag:`lock.avoid.thread` Secondly, we require that in a multi-threaded
system, memory fault handlers do not suspend threads (although the
faulting thread will, of course, wait for the fault handler to
finish).

:mps:tag:`lock.avoid.conflict` Thirdly, we avoid conflicting deadlock between
the arena and global locks by ensuring we never claim the arena lock
when the recursive global lock is already held, and we never claim the
binary global lock when the arena lock is held.


Location dependencies
.....................

:mps:tag:`ld` Location dependencies use fields in the arena to maintain a
history of summaries of moved objects, and to keep a notion of time,
so that the staleness of location dependency can be determined.


Finalization
............

:mps:tag:`final` There is a pool which is optionally (and dynamically)
instantiated to implement finalization. The fields ``finalPool`` and
``isFinalPool`` are used.


Implementation
--------------


Tract cache
...........

:mps:tag:`impl.tract.cache` When tracts are allocated to pools by :c:func:`ArenaAlloc()`,
the first tract of the block and it's base address are cached in arena
fields ``lastTract`` and ``lastTractBase``. The function
:c:func:`TractOfBaseAddr()` (see design.mps.arena.tract-iter.if.block-base(0))
checks against these cached values and only calls the class method on
a cache miss. This optimizes for the common case where a pool
allocates a block and then iterates over all its tracts (for example,
to attach them to a segment).

:mps:tag:`impl.tract.uncache` When blocks of memory are freed by pools,
:c:func:`ArenaFree()` checks to see if the cached value for the most
recently allocated tract (see :mps:ref:`.impl.tract.cache`) is being freed. If
so, the cache is invalid, and must be reset. The ``lastTract`` and
``lastTractBase`` fields are set to :c:macro:`NULL`.


Control pool
............

:mps:tag:`impl.pool.init` The control pool is initialized by a call to
:c:func:`PoolInit()` during :c:func:`ArenaCreate()`.

:mps:tag:`impl.pool.ready` All the other fields in the arena are made
checkable before calling :c:func:`PoolInit()`, so :c:func:`PoolInit()` can call
``ArenaCheck(arena)``. The pool itself is, of course, not checkable,
so we have a field ``arena->poolReady``, which is false until after
the return from :c:func:`PoolInit()`. :c:func:`ArenaCheck()` only checks the pool
if ``poolReady``.


Traces
......

:mps:tag:`impl.trace` ``arena->trace[ti]`` is valid if and only if
``TraceSetIsMember(arena->busyTraces, ti)``.

:mps:tag:`impl.trace.create` Since the arena created by :c:func:`ArenaCreate()`
has ``arena->busyTraces = TraceSetEMPTY``, none of the traces are
meaningful.

:mps:tag:`impl.trace.invalid` Invalid traces have signature ``SigInvalid``,
which can be checked.


Polling
.......

:mps:tag:`impl.poll.fields` There are three fields of a arena used for
polling: ``pollThreshold``, ``insidePoll``, and ``clamped`` (see
above). ``pollThreshold`` is the threshold for the next poll: it is
set at the end of :c:func:`ArenaPoll()` to the current polling time plus
:c:macro:`ARENA_POLL_MAX`.


Location dependencies
.....................

:mps:tag:`impl.ld` The ``historyStruct`` contains fields used to maintain a
history of garbage collection and in particular object motion in order
to implement location dependency.

:mps:tag:`impl.ld.epoch` The ``epoch`` is the "current epoch". This is the number
of "flips" of traces, in which objects might have moved, in the arena
since it was created. From the mutator's point of view, locations
change atomically at flip.

:mps:tag:`impl.ld.history` The ``history`` is a circular buffer of
``LDHistoryLENGTH`` elements of type :c:type:`RefSet`. These are the
summaries of moved objects since the last ``LDHistoryLENGTH`` epochs.
If ``e`` is one of these recent epochs, then ::

    history->history[e % LDHistoryLENGTH]

is a summary of (the original locations of) objects moved since epoch
``e``.

:mps:tag:`impl.ld.prehistory` The ``prehistory`` is a :c:type:`RefSet` summarizing
the original locations of all objects ever moved. When considering
whether a really old location dependency is stale, it is compared with
this summary.


Roots
.....

:mps:tag:`impl.root-ring` The arena holds a member of a ring of roots in the
arena. It holds an incremental serial which is the serial of the next
root.