39. Write barrier

39.1. 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.

39.2. 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.

39.3. 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.]

39.4. 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.

39.5. 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.

39.6. References

job003975

Richard Brooksby. Ravenbrook Limited. 2016-03-11. “Poor performance due to imbalance between protection and scanning costs”.