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