1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
.. highlight:: none


.. index::
   pair: write barrier; design

.. _design-write-barrier:


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

.. mps:prefix:: design.mps.write-barrier


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

:mps:tag:`intro` This document explains the design of the write barrer of the
Memory Pool System (MPS).

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

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


Overview
--------

:mps:tag:`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
-----------------------

:mps:tag:`scan.summary` As the MPS scans a segment during garbage collection,
it accumulates a summary of references.  This summary is represented
by single word :c:type:`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
----------------------

:mps:tag:`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.

:mps:tag:`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.

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

:mps:tag:`def.interesting` A scan is "interesting" if it was not boring
(:mps:ref:`.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.

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

:mps:tag:`deferral.reset` The count is reset after three events:

  1. segment creation (:c:macro:`WB_DEFER_INIT`)

  2. an interesting scan (:c:macro:`WB_DEFER_DELAY`)

  3. a barrier hit (:c:macro:`WB_DEFER_HIT`)

:mps:tag:`deferral.dabble` The set of objects condemend 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
:mps:ref:`.deferral.heuristic` somewhat.  We assume that the garbage collector
will spend most of its time repeatedly collecting the same zones.


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

:mps:tag:`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 protecion 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.

:mps:tag:`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] Richard Brooksby. Ravenbrook Limited. 2016-03-11. "`Poor performance due to imbalance between protection and scanning costs <https://www.ravenbrook.com/project/mps/issue/job003975>`__".