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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
.. highlight:: none


.. index::
   pair: shield; design

.. _design-shield:


Shield
======

.. mps:prefix:: design.mps.shield


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

:mps:tag:`intro` This document contains a guide to the MPS Shield. There is
no historical initial design, but in its place there are some early
ideas and discussions: see :mps:ref:`.ideas`.

:mps:tag:`readership` Any MPS developer. Not confidential.


Overview
--------

:mps:tag:`overview` The MPS implements incremental garbage collection using
memory barriers implemented by a combination of hardware memory
protection and thread control.  The MPS needs *separate control* of
collector access and mutator (client) access to memory: the collector
must be able to incrementally scan objects, without the mutator being
able to see them yet.

Unfortunately common operating systems do not support different access
levels (protection maps) for different parts of the same process.

The MPS Shield is an abstraction that does extra work to overcome this
limitation, and give the rest of the MPS the illusion that we can
control collector and mutator access separately.


Interface
---------


Mutator access
..............

The shield provides :c:func:`ShieldRaise()` and :c:func:`ShieldLower()` to forbid
or permit the mutator access to object memory segments. Between these
two, a segment is said to have the shield *raised* (:mps:ref:`.def.raised`).

.. c:function:: void ShieldRaise(Arena arena, Seg seg, AccessSet mode)

    Prevent the mutator accessing the memory segment in the specified
    mode (``AccessREAD``, ``AccessWRITE``, or both).

.. c:function:: void ShieldLower(Arena arena, Seg seg, AccessSet mode)

    Allow the mutator to access the memory segment in the specified
    mode (``AccessREAD``, ``AccessWRITE``, or both).

If the mutator attempts an access that hits the shield, the MPS gets
an OS-specific hardware protection fault which reaches
:c:func:`ArenaAccess()`, does whatever work is necessary, then lowers the
shield and returns to the mutator.

:c:func:`ShieldRaise()` and :c:func:`ShieldLower()` do *not* nest.


Entering the shield
...................

The MPS can only gain exclusive access from *inside* the shield
(:mps:ref:`.def.inside`). To enter the shield, the MPS must call
:c:func:`ShieldEnter()`, and to leave it, the MPS must call
:c:func:`ShieldLeave()`.

:c:func:`ShieldEnter()` and :c:func:`ShieldLeave()` are called by :c:func:`ArenaEnter()`
and :c:func:`ArenaLeave()` so almost all of the MPS is is inside the
shield.


Collector access to segments
............................

When the MPS wants to access object memory segments from inside the
shield, it must wrap any accesses with a :c:func:`ShieldExpose()` and
:c:func:`ShieldCover()` pair. These calls nest. After a call to
:c:func:`ShieldExpose()` a segment is said to be *exposed* until the last
nested call to :c:func:`ShieldCover()`. The shield arranges that the MPS can
access the memory while it is exposed.

A segment might for example be exposed during:

  - format-scan (when scanning);
  - format-skip (when marking grains in a non-moving fix);
  - format-isMoved and :c:func:`AddrCopy()` (during a copying fix);
  - format-pad (during reclaim).

Note that there is no need to call :c:func:`ShieldExpose()` when accessing
pool management memory such as bit tables. This is not object memory,
is never (legally) accessed by the mutator, and so is never shielded.

Similarly, a pool class that never raises the shield on its segments
need never expose them to gain access.


Collector access to the unprotectable
.....................................

When the MPS wants to access an unprotectable object from inside the
shield, it must wrap any accesses with a :c:func:`ShieldHold()` and
:c:func:`ShieldRelease()` pair. This allows access to objects which cannot
be shielded by :c:func:`ShieldRaise()`, such as:

  - the stack and registers of mutator threads,
  - lockless allocation point structures,
  - areas of memory that can't be protected by operating system calls,
  - unprotectable roots.

.. c:function:: void ShieldHold(Arena arena)

    Get exclusive access to the unprotectable.

.. c:function:: void ShieldRelease(Arena arena)

    Declare that exclusive access is no longer needed.


Mechanism
---------

On common operating systems, the only way to allow the MPS access is
to allow access from the whole process, including the mutator. So
:c:func:`ShieldExpose()` will suspend all mutator threads to prevent any
mutator access, and so will :c:func:`ShieldRaise()` on an unexposed segment.
The shield handles suspending and resuming threads, and so the rest of
the MPS does not need to worry about it.

The MPS can make multiple sequential, overlapping, or nested calls to
:c:func:`ShieldExpose()` on the same segment, as long as each is balanced by
a corresponding :c:func:`ShieldCover()` before :c:func:`ShieldLeave()` is called.
A usage count is maintained on each segment in ``seg->depth``. When
the usage count reaches zero, there is no longer any reason the
segment should be unprotected, and the shield may reinstate hardware
protection at any time.

However, as a performance-improving hysteresis, the shield defers
re-protection, maintaining a queue of segments that require attention
before mutator threads are resumed (:mps:ref:`.impl.delay`). While a segment
is in the queue, it has ``seg->queued`` set true.

This hysteresis allows the MPS to proceed with garbage collection
during a pause without actually setting hardware protection until it
returns to the mutator. This is particularly important on operating
systems where the protection is expensive and poorly implemented, such
as macOS.

The queue also ensures that no memory protection system calls will be
needed for incremental garbage collection if a complete collection
cycle occurs during one pause.


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

:mps:tag:`impl.delay` The implementation of the shield avoids suspending
threads for as long as possible. When threads are suspended, it
maintains a queue of segments where the desired and actual protection
do not match. This queue is flushed on leaving the shield.


Definitions
...........

:mps:tag:`def.raised` A segment has the shield *raised* for an access mode
after a call to :c:func:`ShieldRaise()` and before a call to
:c:func:`ShieldLower()` with that mode.

:mps:tag:`def.exposed` A segment is *exposed* after a call to
:c:func:`ShieldExpose()` and before a call to :c:func:`ShieldLower()`.

:mps:tag:`def.synced` A segment is *synced* if the prot and shield modes are
the same, and unsynced otherwise.

:mps:tag:`def.depth` The *depth* of a segment is defined as:

  | depth ≔ #exposes − #covers, where
  |    #exposes = the number of calls to :c:func:`ShieldExpose()` on the segment
  |    #covers  = the number of calls to :c:func:`ShieldCover()` on the segment

:c:func:`ShieldCover()` must not be called without a matching
:c:func:`ShieldExpose()`, so this figure must always be non-negative.

:mps:tag:`def.total.depth` The total depth is the sum of the depth over all
segments.

:mps:tag:`def.outside` Being outside the shield is being between calls to
:c:func:`ShieldLeave()` and :c:func:`ShieldEnter()`, and similarly :mps:tag:`def.inside`
being inside the shield is being between calls to :c:func:`ShieldEnter()`
and :c:func:`ShieldLeave()`. [In a multi-threaded MPS this would be
per-thread. RB 2016-03-18]

:mps:tag:`def.shielded` A segment is shielded if the shield mode is
non-zero. [As set by ShieldRaise.]


Properties
..........

:mps:tag:`prop.outside.running` The mutator may not be suspended while outside
the shield.

:mps:tag:`prop.mutator.access` An attempt by the mutator to access shielded
memory must be pre-empted by a call to :c:func:`ArenaAccess()`.

:mps:tag:`prop.inside.access` Inside the shield the MPS must be able to access
all unshielded segments and all exposed segments.


Invariants
..........

:mps:tag:`inv.outside.running` The mutator is not suspended while outside the
shield.

:mps:tag:`inv.unsynced.suspended` If any segment is not synced, the mutator is
suspended.

:mps:tag:`inv.unsynced.depth` All unsynced segments have positive depth or are
in the queue.

:mps:tag:`inv.outside.depth` The total depth is zero while outside the shield.

:mps:tag:`inv.prot.shield` The prot mode is never more than the shield mode.

:mps:tag:`inv.expose.depth` An exposed segment's depth is greater than zero.

:mps:tag:`inv.expose.prot` An exposed segment is not protected in the mode
it was exposed with.


Proof Hints
...........

Hints at proofs of properties from invariants.

:mps:tag:`proof.outside` :mps:ref:`.inv.outside.running` directly ensures
:mps:ref:`.prop.outside.running`.

:mps:tag:`proof.sync` As the depth of a segment cannot be negative

  | total depth = 0
  |   ⇒ for all segments, depth = 0
  |   ⇒ all segments are synced (by :mps:ref:`.inv.unsynced.depth`)

:mps:tag:`proof.access` If the mutator is running then all segments must be
synced (:mps:ref:`.inv.unsynced.suspended`). Which means that the hardware
protection (protection mode) must reflect the software protection
(shield mode). Hence all shielded memory will be hardware protected
while the mutator is running. This ensures :mps:ref:`.prop.mutator.access`.

:mps:tag:`proof.inside` :mps:ref:`.inv.prot.shield` and :mps:ref:`.inv.expose.prot` ensure
:mps:ref:`.prop.inside.access`.


Initial ideas
-------------

:mps:tag:`ideas` There never was an initial design document, but
[RB_1995-11-29]_ and [RB_1995-11-30]_ contain some initial ideas.


Improvement Ideas
-----------------


Mass exposure
.............

:mps:tag:`improv.mass-expose` If protection calls have a high overhead it might
be good to pre-emptively unprotect large ranges of memory when we
expose one segment.  With the current design this would mean
discovering adjacent shielded segments and adding them to the queue.
The collector should take advantage of this by preferentially scanning
exposed segments during a pause.


Segment independence
....................

:mps:tag:`improv.noseg` The shield is implemented in terms of segments, using
fields in the segment structure to represent its state. This forces us
to (for example) flush the shield queue when deleting a segment. The
shield could keep track of protection and shielding independently,
possibly allowing greater coalescing and more efficient and flexible
use of system calls (see :mps:ref:`.improv.mass-expose`).


Concurrent collection
.....................

:mps:tag:`improv.concurrent` The MPS currently does not collect
concurrently, however the only thing that makes it not-concurrent is a
critical point in the Shield abstraction where the MPS seeks to gain
privileged access to memory (usually in order to scan it). The
critical point is where :c:func:`ShieldExpose()` in shield.c has to call
:c:func:`ShieldHold()` to preserve the shield invariants. This is the only
point in the MPS that prevents concurrency, and the rest of the MPS is
designed to support it.

The restriction could be removed if either:

 * the MPS could use a different set of protections to the mutator
   program

 * the mutator program uses a software barrier

The first one is tricky, and the second one just hasn't come up in any
implementation we've been asked to make yet. Given a VM, it could
happen, and the MPS would be concurrent.

So, I believe there's nothing fundamentally non-concurrent about the
MPS design. It's kind of waiting to happen.

(Originally written at <http://news.ycombinator.com/item?id=4524036>.)


Early Resume
............

:mps:tag:`improv.resume` There is a tradeoff between delaying flushing the
shield queue (preventing unnecessary protection and allowing us to
coalesce) and resuming mutator threads. We could resume threads
earlier under some circumstances, such as before reclaim (which does
not need to interact with the mutator). Basically, it might be worth
resuming the mutator early in a pause if we know that we're unlikely
to suspend it again (no more calls to :c:func:`ShieldRaise()` or
:c:func:`ShieldExpose()` on shielded segments).


Expose modes
............

:mps:tag:`improv.expose-modes` Would it be a good idea for
:c:func:`ShieldExpose()` to take an :c:type:`AccessSet`? It might be good if we
didn't have to raise a write barrier unless we want to write. When
scanning (for instance), we may not need to write, so when scanning a
segment behind a write barrier we shouldn't have to call
:c:func:`mprotect()`. That's a bit speculative: how often do we scan a
segment and not write to it. Alternatively, and more speculatively, we
could keep the write barrier up, handle the (possibly nested) trap and
*then* expose the shield. I'm just scraping around for ways to reduce
calls to :c:func:`mprotect()`.

Theoretically we can do this, but:

 1. We're mostly a moving collector so we'll almost always want to
    write to segments we scan.  That could change if we do more
    non-moving collection.

 2. The main cost of protection is changing it at all, not whether we
    change just read or write.  On macOS, the main cost seems to be the
    TLB flush, which affects wall-clock time of everything on the
    processor!


References
----------

.. [RB_1995-11-29] Richard Brooksby. Harlequin. 1995-11-29. "`Shield protocol for barriers <https://info.ravenbrook.com/project/mps/doc/2002-06-18/obsolete-mminfo/mminfo/idea/shield/index.txt>`__".

.. [RB_1995-11-30] Richard Brooksby. Harlequin. 1995-11-30. "`Exegesis of Incremental Tracing <https://info.ravenbrook.com/project/mps/mail/1995/11/30/15-07/0.txt>`__".