.. mode: -*- rst -*-

Write barrier
=============

:Tag: design.mps.write-barrier
:Author: Richard Brooksby
:Date: 2016-03-18
:Status: incomplete design
:Revision: $Id$
:Copyright: See `Copyright and License`_.
:Index terms: pair: write barrier; design


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

_`.intro`: This document explains the design of the write barrier of the
Memory Pool System (MPS).

_`.readership`: This document is intended for developers of the MPS.

_`.source`: This is based on [job003975]_.


Overview
--------

_`.overview`: The MPS uses a combination of hardware memory protection
and BIBOP techniques to maintain an approximate remembered set.  The
remembered set keeps track of areas of memory that refer to each
other, so that the MPS can avoid scanning areas that are irrelevant
during a garbage collection.  The MPS write barrier is implemented by
a one-word "summary" of the zones referenced by a segment.  That
summary can be compared with the "white set" of a trace by a simple
logical AND operation.


Write Barrier Processes
-----------------------

_`.scan.summary`: As the MPS scans a segment during garbage collection,
it accumulates a summary of references.  This summary is represented
by single word ``ZoneSet``, derived from the bit patterns of the
references.  After the scan the MPS can decide to store the summary
with the segment, and use it in future garbage collections to avoid
future scans.

If the summary does not intersect any of the zones containing
condemned objects, the MPS does not have to scan them in order to
determine if those objects are live.

The mutator could update the references in a segment and make the
summary invalid.  To avoid this, when the MPS stores a summary, it
raises a write barrier on the segment memory.  If the mutator does
update the segment, the barrier is hit, and the MPS resets the
summary, so that the segment will be scanned in future.


[At this point I was interrupted by a man from Porlock.]


Write barrier deferral
----------------------

_`.deferral`: Both scanning and the write barrier cost CPU time, and
these must be balanced.  There is no point spending 1000 CPU units
raising a write barrier to avoid 10 CPU units of scanning cost.
Therefore we do not raise the write barrier immediately.

_`.deferral.heuristic`: We apply a simple heuristic: A segment which was
found to be "interesting" while scanning is likely to be interesting
again, and so raising the write barrier is not worthwhile.  If we scan
a segment several times and find it "boring" then we raise the barrier
to avoid future boring scans.

_`.def.boring`: A scan is "boring" if it was unnecessary for a garbage
collection because it found no references to condemned objects.

_`.def.interesting`: A scan is "interesting" if it was not boring
(`.def.boring`_).  Note that this does not mean it preserved comdemned
objects, only that we would have scanned it even if we had had the
scan summary beforehand.

_`.deferral.count`: We store a deferral count with the segment.  The
count is decremented after each boring scan (`.def.boring`_).  The write
barrier is raised only when the count reaches zero.

_`.deferral.reset`: The count is reset after three events:

  1. segment creation (``WB_DEFER_INIT``)

  2. an interesting scan (``WB_DEFER_DELAY``)

  3. a barrier hit (``WB_DEFER_HIT``)

_`.deferral.dabble`: The set of objects condemned by the garbage
collector changes, and so does what is interesting or boring.  For
example, a collection of a nursery space in zone 3 might be followed
by a collection of a top generation in zone 7.  This will upset
`.deferral.heuristic`_ somewhat.  We assume that the garbage collector
will spend most of its time repeatedly collecting the same zones.


Improvements
------------

_`.improv.by-os`: The overheads hardware barriers varies widely between
operating systems.  On Windows it is very cheap to change memory
protection and to handle protection faults.  On macOS it is very
expensive.  The balance between barriers and scanning work is
different.  We should measure the relative costs and tune the deferral
for each separately.

_`.improv.balance`: Hardware costs of write barriers vary by OS, but
scanning costs vary depending on many factors including client code.
The MPS could dynamically measure these costs, perhaps using fast
cycle counters such as RDTSC, and use this to dynamically balance the
write barrier deferral.


References
----------

.. [job003975] "Poor performance due to imbalance between protection
               and scanning costs"; Richard Brooksby; Ravenbrook
               Limited; 2016-03-11;
               <https://www.ravenbrook.com/project/mps/issue/job003975>.


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

- 2016-03-19 RB_ Created during preparation of
  branch/2016-03-13/defer-write-barrier for [job003975]_.

.. _RB: https://www.ravenbrook.com/consultants/rb/


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

Copyright © 2016–2020 `Ravenbrook Limited <https://www.ravenbrook.com/>`_.

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.

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 AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDER OR 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.
