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
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
.. highlight:: none


.. index::
   pair: strategy; design

.. _design-strategy:


MPS Strategy
============

.. mps:prefix:: design.mps.strategy


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

_`.intro` This is the design of collection strategy for the MPS.

_`.readership` MPS developers.


Overview
--------

_`.overview` The MPS uses "strategy" code to make three decisions:

- when to start a collection trace;

- what to condemn;

- how to schedule tracing work.

This document describes the current strategy, identifies some
weaknesses in it, and outlines some possible future development
directions.


Requirements
------------

[TODO: source some from req.dylan, or do an up-to-date requirements
analysis -- NB 2013-03-25]

Garbage collection is a trade-off between time and space: it consumes
some [CPU] time in order to save some [memory] space.  Strategy shifts
the balance point.  A better strategy will take less time to produce
more space.  Examples of good strategy might include:

- choosing segments to condemn which contain high proportions of dead
  objects;

- starting a trace when a large number of objects have just died;

- doing enough collection soon enough that the client program never
  suffers low-memory problems;

- using otherwise-idle CPU resources for tracing.

Conversely, it would be bad strategy to do the reverse of each of
these (condemning live objects; tracing when there's very little
garbage; not collecting enough; tracing when the client program is
busy).

Abstracting from these notions, requirements on strategy would
relate to:

- Maximum pause time and other utilization metrics (for example,
  bounded mutator utilization, minimum mutator utilization, total MPS
  CPU usage);

- Collecting enough garbage (for example: overall heap size;
  low-memory requirements).

- Allowing client control (for example, client recommendations for
  collection timing or condemnation).

There are other possible strategy considerations which are so far
outside the scope of current strategy and MPS design that this
document disregards them. For example, either inferring or allowing
the client to specify preferred relative object locations ("this
object should be kept in the same cache line as that one"), to improve
cache locality.


Generations
-----------

The largest part of the current MPS strategy implementation is the
support for generational garbage collections.


General data structures
.......................

The fundamental structure of generational garbage collection is the
:c:type:`Chain`, which describes a sequence of generations.

A chain specifies the "capacity" and "mortality" for each generation.
When creating an automatically collected pool, the client code may
specify the chain which will control collections for that pool. The
same chain may be used for multiple pools. If no chain is specified,
the pool uses the arena's default generation chain.

Each generation in a chain has a :c:type:`GenDesc` structure, allocated in
an array pointed to from the chain. In addition to the generations in
the chains, the arena has a unique :c:type:`GenDesc` structure, named
``topGen`` and described in comments as "the dynamic generation"
(misleadingly: in fact it is the *least* dynamic generation).

Each automatically collected pool has a set of :c:type:`PoolGen` structures,
one for each generation that it can allocate or promote into. The
:c:type:`PoolGen` structures for each generation point to the :c:type:`GenDesc`
for that generation, and are linked together in a ring on the
:c:type:`GenDesc`. These structures are used to gather accounting
information for strategy decisions.

The non-moving automatic pool classes (AMS, AWL and LO) do not support
generational collection, so they allocate into a single generation.
The moving automatic pool classes (AMC and AMCZ) have one pool
generations for each generation in the chain, plus one pool generation
for the arena's "top generation".


AMC data structures
...................

An AMC pool creates an array of pool generation structures of type
``amcGen`` (a subclass of :c:type:`PoolGen`). Each pool generation points to
the *forwarding buffer* for that generation: this is the buffer that
surviving objects are copied into.

AMC segments point to the AMC pool generation that the segment belongs
to, and AMC buffers point to the AMC pool generation that the buffer
will be allocating into.

The forwarding buffers are set up during AMC pool creation. Each
generation forwards into the next higher generation in the chain,
except for the top generation, which forwards to itself. Thus, objects
are "promoted" up the chain of generations until they end up in the
top generations, which is shared between all generational pools.


Collections
...........

Collections in the MPS start in one of two ways:

1. A collection of the world starts via :c:func:`TraceStartCollectAll()`.
   This simply condemns all segments in all automatic pools.

2. A collection of some set of generations starts via
   :c:func:`PolicyStartTrace()`. See :mps:ref:`.policy.start`.


Zones
.....

Each generation in each chain has a zoneset associated with it
(``gen->zones``); the condemned zoneset is the union of some number of
generation's zonesets.

An attempt is made to use distinct zonesets for different generations.
Segments in automatic pools are allocated using :c:func:`PoolGenAlloc()`
which creates a :c:type:`LocusPref` using the zoneset from the generation's
:c:type:`GenDesc`. The zoneset for each generation starts out empty. If the
zoneset is empty, an attempt is made to allocate from a free zone. The
:c:type:`GenDesc` zoneset is augmented with whichever zones the new segment
occupies.

Note that this zoneset can never shrink.


Parameters
..........

:mps:tag:`param.intro` A generation has two parameters, *capacity* and
*mortality*, specified by the client program.

:mps:tag:`param.capacity` The *capacity* of a generation is the amount of
*new* allocation in that generation (that is, allocation since the
last time the generation was condemned) that will cause the generation
to be collected by :c:func:`TracePoll()`.

:mps:tag:`param.capacity.misnamed` The name *capacity* is unfortunate since
it suggests that the total amount of memory in the generation will not
exceed this value. But that will only be the case for pool classes
that always promote survivors to another generation. When there is
*old* allocation in the generation (that is, prior to the last time
the generation was condemned), as there is in the case of non-moving
pool classes, the size of a generation is unrelated to its capacity.

:mps:tag:`param.mortality` The *mortality* of a generation is the proportion
(between 0 and 1) of memory in the generation that is expected to be
dead when the generation is collected. It is used in :c:func:`TraceStart()`
to estimate the amount of data that will have to be scanned in order
to complete the trace.


Accounting
..........

:mps:tag:`accounting.intro` Pool generations maintain the sizes of various
categories of data allocated in that generation for that pool. This
accounting information is reported via the event system, but also used
in two places:

:mps:tag:`accounting.poll` :c:func:`ChainDeferral()` uses the *new size* of
each generation to determine which generations in the chain are over
capacity and so might need to be collected by :c:func:`PolicyStartTrace()`.

:mps:tag:`accounting.condemn` :c:func:`PolicyStartTrace()` uses the *new size* of
each generation to determine which generations in the chain will be
collected; it also uses the *total size* of the generation to compute
the mortality.

:mps:tag:`accounting.check` Computing the new size for a pool generation is
far from straightforward: see job003772_ and job004007_ for some
(former) errors in this code. In order to assist with checking that
this has been computed correctly, the locus module uses a double-entry
book-keeping system to account for every byte in each pool generation.
This uses seven accounts:

.. _job003772: https://www.ravenbrook.com/project/mps/issue/job003772/
.. _job004007: https://www.ravenbrook.com/project/mps/issue/job004007/

:mps:tag:`account.total` Memory acquired from the arena.

:mps:tag:`account.total.negated` From the point of view of the double-entry
system, the *total* should be negative as it is owing to the arena,
but it is inconvenient to represent negative sizes, and so the
positive value is stored instead.

:mps:tag:`account.total.negated.justification` We don't have a type for
signed sizes; but if we represented it in two's complement using the
unsigned :c:type:`Size` type then Clang's unsigned integer overflow detector
would complain.

:mps:tag:`account.free` Memory that is not in use (free or lost to
fragmentation).

:mps:tag:`account.buffered` Memory in a buffer that was handed out to the
client program via :c:func:`BufferFill()`, and which has not yet been
condemned.

:mps:tag:`account.new` Memory in use by the client program, allocated
since the last time the generation was condemned.

:mps:tag:`account.old` Memory in use by the client program, allocated
prior to the last time the generation was condemned.

:mps:tag:`account.newDeferred` Memory in use by the client program,
allocated since the last time the generation was condemned, but which
should not cause collections via :c:func:`TracePoll()`. (Due to ramping; see
below.)

:mps:tag:`account.oldDeferred` Memory in use by the client program,
allocated prior to the last time the generation was condemned, but
which should not cause collections via :c:func:`TracePoll()`. (Due to
ramping; see below.)

:mps:tag:`accounting.op` The following operations are provided:

:mps:tag:`accounting.op.alloc` Allocate a segment in a pool generation.
Debit *total*, credit *free*. (But see :mps:ref:`.account.total.negated`.)

:mps:tag:`accounting.op.free` Free a segment. First, ensure that the
contents of the segment are accounted as free, by artificially ageing
any memory accounted as *new* or *newDeferred* (see
:mps:ref:`.accounting.op.age`) and then artifically reclaiming any memory
accounted as *old* or *oldDeferred* (see :mps:ref:`.accounting.op.reclaim`).
Finally, debit *free*, credit *total*. (But see
:mps:ref:`.account.total.negated`.)

:mps:tag:`accounting.op.fill` Fill a buffer. Debit *free*, credit *buffered*.

:mps:tag:`accounting.op.empty` Empty a buffer. Debit *buffered*, credit
*new* or *newDeferred* with the allocated part of the buffer, credit
*free* with the unused part of the buffer.

:mps:tag:`accounting.op.age` Condemn memory. Debit *buffered* (if part or
all of a buffer was condemned) and either *new* or *newDeferred*,
credit *old* or *oldDeferred*. Note that the condemned part of the
buffer remains part of the buffer until the buffer is emptied, but is
now accounted as *old* or *oldDeferred*. The uncondemned part of the
buffer, if any, remains accounted as *buffered* until it is either
emptied or condemned in its turn.

:mps:tag:`accounting.op.reclaim` Reclaim dead memory. Debit *old* or
*oldDeferred*, credit *free*.

:mps:tag:`accounting.op.undefer` Stop deferring the accounting of memory. Debit *oldDeferred*, credit *old*. Debit *newDeferred*, credit *new*.


Ramps
.....
The intended semantics of ramping are pretty simple.  It allows the
client to advise us of periods of large short-lived allocation on a
particular AP.  Stuff allocated using that AP during its "ramp" will
probably be dead when the ramp finishes.  How the MPS makes use of this
advice is up to us, but for instance we might segregate those objects,
collect them less enthusiastically during the ramp and then more
enthusiastically soon after the ramp finishes.  Ramps can nest.

A ramp is entered by calling::

    mps_ap_alloc_pattern_begin(ap, mps_alloc_pattern_ramp())

or similar, and left in a similar way.

This is implemented on a per-pool basis, for AMC only (it's ignored by
the other automatic pools).  PoolAMC throws away the identity of the AP
specified by the client.  The implementation is intended to work by
changing the generational forwarding behaviour, so that there is a "ramp
generation" - one of the regular AMC generations - which forwards to
itself if collected during a ramp (instead of promoting to an older
generation).  It also tweaks the strategy calculation code, in a way
with consequences I am documenting elsewhere.

Right now, the code sets this ramp generation to the last generation
specified in the pool's "chain": it ordinarily forwards to the
"after-ramp" generation, which is the "dynamic generation" (i.e. the
least dynamic generation, i.e. the arena-wide "top generation").  My
recollection, and some mentions in design/poolamc, suggests that the
ramp generation used to be chosen differently from this.

So far, it doesn't sound too ghastly, I guess, although the subversion
of the generational system seems a little daft.  Read on....

An AMC pool has a ``rampMode`` (which is really a state of a state
machine), taking one of five values: OUTSIDE, BEGIN, RAMPING, FINISH,
and COLLECTING (actually the enum values are called RampX for these
X). We initialize in OUTSIDE.  The pool also has a ``rampCount``,
which is the ramp nesting depth and is used to allow us to ignore ramp
transitions other than the outermost.  According to design/poolamc,
there's an invariant (in BEGIN or RAMPING, ``rampCount > 0``; in
COLLECTING or OUTSIDE, ``rampCount == 0``), but this isn't checked in
:c:func:`AMCCheck()` and in fact is false for COLLECTING (see below).

There is a small set of events causing state machine transitions:

- entering an outermost ramp;
- leaving an outermost ramp;
- condemning any segment of a ramp generation (detected in AMCWhiten);
- reclaiming any AMC segment.

Here's pseudo-code for all the transition events:

Entering an outermost ramp:
 if not FINISH, go to BEGIN.

Leaving an outermost ramp:
 if RAMPING, go to FINISH.   Otherwise, go to OUTSIDE.

Condemning a ramp generation segment:
 If BEGIN, go to RAMPING and make the ramp generation forward
 to itself (detach the forwarding buffer and reset its generation).
 If FINISH, go to COLLECTING and make the ramp generation
 forward to the after-ramp generation.

Reclaiming any AMC segment:
 If COLLECTING:
   if ``rampCount > 0``, go to BEGIN.  Otherwise go to OUTSIDE.

Now, some deductions:

#. When OUTSIDE, the count is always zero, because (a) it starts that
   way, and the only ways to go OUTSIDE are (b) by leaving an
   outermost ramp (count goes to zero) or (c) by reclaiming when the
   count is zero.

#. When BEGIN, the count is never zero (consider the transitions to
   BEGIN and the transition to zero).

#. When RAMPING, the count is never zero (again consider transitions
   to RAMPING and the transition to zero).

#. When FINISH, the count can be anything (the transition to FINISH
   has zero count, but the Enter transition when FINISH can change
   that and then it can increment to any value).

#. When COLLECTING, the count can be anything (from the previous fact,
   and the transition to COLLECTING).

#. *This is a bug!!* The ramp generation is not always reset (to
   forward to the after-ramp generation). If we get into FINISH and
   then see another ramp before the next condemnation of the ramp
   generation, we will Enter followed by Leave. The Enter will keep us
   in FINISH, and the Leave will take us back to OUTSIDE, skipping the
   transition to the COLLECTING state which is what resets the ramp
   generation forwarding buffer. [TODO: check whether I made an issue
   and/or fixed it; NB 2013-06-04]

The simplest change to fix this is to change the behaviour of the Leave
transition, which should only take us OUTSIDE if we are in BEGIN or
COLLECTING.  We should also update design/poolamc to tell the truth, and
check the invariants, which will be these:

     OUTSIDE => zero
     BEGIN => non-zero
     RAMPING => non-zero

A cleverer change might radically rearrange the state machine
(e.g. reduce the number of states to three) but that would require
closer design thought and should probably be postponed until we have a
clearer overall strategy plan.

While I'm writing pseudo-code versions of ramp-related code, I should
mention this other snippet, which is the only other code relating to
ramping (these notes are useful when thinking about the broader strategy
code):

    In :c:func:`AMCBufferFill()`, if we're RAMPING, and filling the forwarding
    buffer of the ramp generation, and the ramp generation is the
    forwarding buffer's generation, set ``amcSeg->new`` to FALSE.  Otherwise,
    add the segment size to ``poolGen.newSize``.

And since I've now mentioned the ``amcSeg->new`` flag, here are the only
other uses of that:

- it initializes as TRUE.

- When leaving an outermost ramp, go through all the segments in the
  pool.  Any non-white segment in the rampGen with new set to FALSE has
  its size added to ``poolGen->newSize`` and gets new set to TRUE.

- in :c:func:`amcSegWhiten()`, if new is TRUE, the segment size is deducted
  from ``poolGen.newSize`` and new is set to FALSE.


Policy
------

:mps:tag:`policy` Functions that make decisions about what action to take
are collected into the policy module (policy.c). The purpose of doing
so is to make it easier to understand this set of decisions and how
they interact, and to make it easier to maintain and update the policy.


Assignment of zones
...................

.. c:function:: Res PolicyAlloc(Tract *tractReturn, Arena arena, LocusPref pref, Size size, Pool pool)

:mps:tag:`policy.alloc` Allocate ``size`` bytes of memory on behalf of
``pool``, based on the preferences described by ``pref``. If
successful, update ``*tractReturn`` to point to the first tract in the
allocated memory and return ``ResOK``. Otherwise, return a result code
describing the problem, for example ``ResCOMMIT_LIMIT``.

:mps:tag:`policy.alloc.impl` This tries various methods in succession until
one succeeds. First, it tries to allocate from the arena's free land
in the requested zones. Second, it tries allocating from free zones.
Third, it tries extending the arena and then trying the first two
methods again. Fourth, it tries allocating from any zone that is not
blacklisted. Fifth, it tries allocating from any zone at all.

:mps:tag:`policy.alloc.issue` This plan performs poorly under stress. See
for example job003898_.

.. _job003898: https://www.ravenbrook.com/project/mps/issue/job003898/



Deciding whether to collect the world
.....................................

.. c:function:: Bool PolicyShouldCollectWorld(Arena arena, double availableTime, Clock now, Clock clocks_per_sec)

:mps:tag:`policy.world` Determine whether now is a good time for
:c:func:`mps_arena_step()` to start a collection of the world. Return
:c:macro:`TRUE` if so, :c:macro:`FALSE` if not. The ``availableTime`` argument is an
estimate of the time that's available for the collection, ``now`` is
the current time as returned by :c:func:`ClockNow()`, and ``clocks_per_sec``
is the result of calling :c:func:`ClocksPerSec()`.

:mps:tag:`policy.world.impl` There are two conditions: the estimate of the
available time must be enough to complete the collection, and the last
collection of the world must be long enough in the past that the
:c:func:`mps_arena_step()` won't be spending more than a certain fraction of
runtime in collections. (This fraction is given by the
:c:macro:`ARENA_MAX_COLLECT_FRACTION` configuration parameter.)



Starting a trace
................

.. c:function:: Bool PolicyStartTrace(Trace *traceReturn, Bool *collectWorldReturn, Arena arena, Bool collectWorldAllowed)

:mps:tag:`policy.start` Consider starting a trace. If a trace was started,
update ``*traceReturn`` to point to the trace and return TRUE.
Otherwise, leave ``*traceReturn`` unchanged and return FALSE.

:mps:tag:`policy.start.world` If ``collectWorldAllowed`` is TRUE, consider
starting a collection of the whole world, and if such a collection is
started, set ``*collectWorldReturn`` to TRUE.

This decision uses the "Lisp Machine" strategy, which tries to
schedule collections of the world so that the collector just keeps
pace with the mutator: that is, it starts a collection when the
predicted completion time of the collection is around the time when
the mutator is predicted to reach the current memory limit. See
[Pirinen]_.

:mps:tag:`policy.start.world.hack` The ``collectWorldAllowed`` flag was
added to fix job004011_ by ensuring that the MPS starts at most one
collection of the world in each call to :c:func:`ArenaPoll()`. But this is
is fragile and inelegant. Ideally the MPS would be able to deduce that
a collection of a set of generations can't possibly make progress
(because nothing that refers to this set of generations has changed),
and so not start such a collection.

.. _job004011: https://www.ravenbrook.com/project/mps/issue/job004011/

:mps:tag:`policy.start.chain` If ``collectWorldAllowed`` is FALSE, or if it
is not yet time to schedule a collection of the world,
:c:func:`PolicyStartTrace()` considers collecting a set of zones
corresponding to a set of generations on a chain.

It picks these generations by calling :c:func:`ChainDeferral()` for each
chain; this function indicates if the chain needs collecting, and if
so, how urgent it is to collect that chain. The most urgent chain in
need of collection (if any) is then condemned by calling
:c:func:`policyCondemnChain()`, which chooses the set of generations to
condemn, and condemns all the segments in those generations.


Trace progress
..............

.. c:function:: Bool PolicyPoll(Arena arena)

:mps:tag:`policy.poll` Return TRUE if the MPS should do some tracing work;
FALSE if it should return to the mutator.

.. c:function:: Bool PolicyPollAgain(Arena arena, Clock start, Bool moreWork, Work tracedWork)

:mps:tag:`policy.poll.again` Return TRUE if the MPS should do another unit
of work; FALSE if it should return to the mutator. ``start`` is the
clock time when the MPS was entered; ``moreWork`` and ``tracedWork``
are the results of the last call to :c:func:`TracePoll()`.

:mps:tag:`policy.poll.impl` The implementation keep doing work until either
the maximum pause time is exceeded (see `design.mps.arena.pause-time`_),
or there is no more work to do. Then it schedules the next collection
so that there is approximately one call to :c:func:`TracePoll()` for every
``ArenaPollALLOCTIME`` bytes of allocation.

.. _design.mps.arena.pause-time: arena.html#design.mps.arena.pause-time


References
----------

.. [Pirinen]
   "The Lisp Machine Strategy";
   Pekka Pirinin;
   1998-04-27;
   <https://info.ravenbrook.com/project/mps/doc/2002-06-18/obsolete-mminfo/mminfo/strategy/lisp-machine/>