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
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
.. highlight:: none


.. index::
   pair: MRG pool class; design
   single: pool class; MRG design

.. _design-poolmrg:


MRG pool class
==============

.. mps:prefix:: design.mps.poolmrg
   pair: MRG pool class; design
   single: pool class; MRG design


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

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

:mps:tag:`intro` This is the design of the MRG (Manual Rank Guardian) pool
class. The MRG pool class is part of the MPS. The MRG pool class is
internal to the MPS (has no client interface) and is used to implement
finalization.

:mps:tag:`source` Some of the techniques in paper.dbe93 ("Guardians in a
Generation-Based Garbage Collector") were used in this design. Some
analysis of this design (including various improvements and some more
in-depth justification) is in analysis.mps.poolmrg. That document
should be understood before changing this document. It is also helpful
to look at design.mps.finalize_ and design.mps.message_.

.. _design.mps.message: message.html
.. _design.mps.finalize: finalize.html


Goals
-----

:mps:tag:`goal.final` The MRG pool class should support all
requirements pertaining to finalization.


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

:mps:tag:`req` We have only one requirement pertaining to finalization:

:mps:tag:`req.dylan.fun.finalization` Support the Dylan language-level
implementation of finalized objects: objects are registered, and are
finalized in random order when they would otherwise have died. Cycles
are broken at random places. There is no guarantee of promptness.

:mps:tag:`req.general` However, finalization is a very common piece of
functionality that is provided by (sophisticated) memory managers, so
we can expect other clients to request this sort of functionality.

:mps:tag:`anti-req` Is it required that the MRG pool class return
unused segments to the arena? MFS, for example, does not do this. MRG
will not do this in its initial implementation.


Terminology
-----------

:mps:tag:`def.mrg` **MRG**: The MRG pool class's identifier will be MRG.
This stands for "Manual Rank Guardian". The pool is manually managed
and implements guardians for references of a particular rank
(currently just final).

:mps:tag:`def.final.ref` **final reference**: A reference of rank final (see
design.mps.type.rank).

:mps:tag:`def.final.object` **finalizable object**: An object is finalizable
with respect to a final reference if, since the creation of that
reference, there was a point in time when no references to the object
of lower (that is, stronger) rank were reachable from a root.

:mps:tag:`def.final.object.note` Note that this means an object can be
finalizable even if it is now reachable from the root via exact
references.

:mps:tag:`def.finalize` **finalize**: To finalize an object is to notify the
client that the object is finalizable. The client is presumed to be
interested in this information (typically it will apply some method to
the object).

:mps:tag:`def.guardian` **guardian**: An object allocated in the MRG
Pool. A guardian contains exactly one final reference, and some fields
for the pool's internal use. Guardians are used to implement a
finalization mechanism.


Overview
--------

:mps:tag:`over` The MRG pool class is a pool class in the MPS. It is
intended to provide the functionality of "finalization".

:mps:tag:`over.internal` The MRG pool class is internal to the MPM: it
is not intended to have a client interface. Clients are expected to
access the functionality provided by this pool (finalization) using a
separate MPS finalization interface (design.mps.finalize_).

.. _design.mps.finalize: finalize.html

:mps:tag:`over.one-size` The MRG pool class manages objects of a single
size, each object containing a single reference of rank final.

:mps:tag:`over.one-size.justify` This is all that is necessary to meet our
requirements for finalization. Whenever an object is registered for
finalization, it is sufficient to create a single reference of rank
final to it.

:mps:tag:`over.queue` A pool maintains a list of live guardian objects,
called (for historical reasons) the "entry" list.

:mps:tag:`over.queue.free` The pool also maintains a list of free guardian
objects called the "free" list.

:mps:tag:`over.queue.exit.not` There used to be an "exit" list, but this is
now historical and there shouldn't be any current references to it.

:mps:tag:`over.alloc` When guardians are allocated, they are placed on the
entry list. Guardians on the entry list refer to objects that have not
yet been shown to be finalizable (either the object has references of
lower rank than final to it, or the MPS has not yet got round to
determining that the object is finalizable).

:mps:tag:`over.message.create` When a guardian is discovered to refer to a
finalizable object it is removed from the entry list and becomes a
message on the arena's messages queue.

:mps:tag:`over.message.deliver` When the MPS client receives the message the
message system arranges for the message to be destroyed and the pool
reclaims the storage associated with the guardian/message.

:mps:tag:`over.scan` When the pool is scanned at rank final each reference
will be fixed. If the reference is to an unmarked object (before the
fix), then the object must now be finalizable. In this case the
containing guardian will be removed from the entry list and posted as
a message.

:mps:tag:`over.scan.justify` The scanning process is a crucial step
necessary for implementing finalization. It is the means by which the
MPS detects that objects are finalizable.

:mps:tag:`over.message` ``PoolClassMRG`` implements a :c:type:`MessageClass` (see
design.mps.message_). All the messages are of one :c:type:`MessageType`. This
type is ``MessageTypeFINALIZATION``. Messages are created when objects
are discovered to be finalizable and destroyed when the MPS client has
received the message.

.. _design.mps.message: message.html

:mps:tag:`over.message.justify` Messages provide a means for the MPS to
communicate with its client. Notification of finalization is just such
a communication. Messages allow the MPS to inform the client of
finalization events when it is convenient for the MPS to do so (i.e.
not in PageFault context).

:mps:tag:`over.manual` Objects in the MRG pool are manually managed.

:mps:tag:`over.manual.alloc` They are allocated by :c:func:`ArenaFinalize()` when
objects are registered for finalization.

:mps:tag:`over.manual.free` They are freed when the associated message is
destroyed.

:mps:tag:`over.manual.justify` The lifetime of a guardian object is very
easy to determine so manual memory management is appropriate.


Protocols
---------

Object Registration
...................

:mps:tag:`protocol.register` There is a protocol by which objects can be
registered for finalization. This protocol is handled by the arena
module on behalf of finalization. see
design.mps.finalize.int.finalize_.

.. _design.mps.finalize.int.finalize: finalize.html#design.mps.finalize.int.finalize


Finalizer execution
...................

:mps:tag:`protocol.finalizer` If an object is proven to be finalizable then
a message to this effect will eventually be posted. A client can
receive the message, determine what to do about it, and do it.
Typically this would involve calling the finalization method for the
object, and deleting the message. Once the message is deleted, the
object may become recyclable.


Setup / destroy
...............

:mps:tag:`protocol.life` An instance of PoolClassMRG is needed in order to
support finalization, it is called the "final" pool and is attached to
the arena (see design.mps.finalize.int.arena.struct_).

.. _design.mps.finalize.int.arena.struct: finalize.html#design.mps.finalize.int.arena.struct

:mps:tag:`protocol.life.birth` The final pool is created lazily by
:c:func:`ArenaFinalize()`.

:mps:tag:`protocol.life.death` The final pool is destroyed during
:c:func:`ArenaDestroy()`.


Data structures
---------------

:mps:tag:`guardian` The guardian

:mps:tag:`guardian.over` A guardian is an object used to manage the
references and other data structures that are used by the pool in
order to keep track of which objects are registered for finalization,
which ones have been finalized, and so on.

:mps:tag:`guardian.state` A guardian can be in one of four states:

:mps:tag:`guardian.state.enum` The states are Free, Prefinal, Final,
PostFinal (referred to as MRGGuardianFree, etc. in the
implementation).

#. :mps:tag:`guardian.state.free` The guardian is free, meaning that it is
   on the free list for the pool and available for allocation.

#. :mps:tag:`guardian.state.prefinal` The guardian is allocated, and refers
   to an object that has not yet been discovered to be finalizable. It
   is on the entry list for the pool.

#. :mps:tag:`guardian.state.final` The guardian is allocated, and refers to
   an object that has been shown to be finalizable; this state
   corresponds to the existence of a message.

#. :mps:tag:`guardian.state.postfinal` This state is only used briefly and
   is entirely internal to the pool; the guardian enters this state
   just after the associated message has been destroyed (which happens
   when the client receives the message) and will be freed immediately
   (whereupon it will enter the Free state). This state is used for
   checking only (so that MRGFree can check that only guardians in
   this state are being freed).

:mps:tag:`guardian.life-cycle` Guardians go through the following state life-cycle: Free ⟶ Prefinal ⟶ Final ⟶ Postfinal ⟶ Free.

:mps:tag:`guardian.two-part` A guardian is a structure consisting abstractly
of a link part and a reference part. Concretely, the link part is a
:c:type:`LinkPartStruct`, and the reference part is a :c:type:`RefPartStruct`
(which is just a :c:type:`Word`). The link part is used by the pool, the
reference part forms the object visible to clients of the pool. The
reference part is the reference of ``RankFINAL`` that refers to
objects registered for finalization and is how the MPS detects
finalizable objects.

:mps:tag:`guardian.two-part.union` The :c:type:`LinkPartStruct` is a discriminated
union of a :c:type:`RingStruct` and a :c:type:`MessageStruct`. The :c:type:`RingStruct`
is used when the guardian is either Free or Prefinal. The
MessageStruct is used when the guardian is Final. Neither part of the
union is used when the guardian is in the Postfinal state.

:mps:tag:`guardian.two-part.justify` This may seem a little profligate with
space, but this is okay as we are not required to make finalization
extremely space efficient.

:mps:tag:`guardian.parts.separate` The two parts will be stored in separate
segments.

:mps:tag:`guardian.parts.separate.justify` This is so that the data
structures the pool uses to manage the objects can be separated from
the objects themselves. This avoids the pool having to manipulate data
structures that are on shielded segments
(analysis.mps.poolmrg.hazard.shield).

:mps:tag:`guardian.assoc` Ref part number *n* (from the beginning of the
segment) in one segment will correspond with link part number *n* in
another segment. The association between the two segments will be
managed by the additional fields in pool-specific segment subclasses
(see :mps:ref:`.mrgseg`).

:mps:tag:`guardian.ref` Guardians that are either Prefinal or Final are live
and have valid references (possibly :c:macro:`NULL`) in their ref parts.
Guardians that are free are dead and always have :c:macro:`NULL` in their ref
parts (see :mps:ref:`.free.overwrite` and :mps:ref:`.scan.free`).

:mps:tag:`guardian.ref.free` When freeing an object, it is a pointer to the
reference part that will be passed (internally in the pool).

:mps:tag:`guardian.init` Guardians are initialized when the pool is grown
(:mps:ref:`.alloc.grow`). The initial state has the ref part :c:macro:`NULL` and the
link part is attached to the free ring. Freeing an object returns a
guardian to its initial state.

:mps:tag:`poolstruct` The Pool structure, :c:type:`MRGStruct` will have:

- :mps:tag:`poolstruct.entry` the head of the entry list.

- :mps:tag:`poolstruct.free` the head of the free list.

- :mps:tag:`poolstruct.rings` The entry list, the exit list, and the free
  list will each be implemented as a :c:type:`Ring`. Each ring will be
  maintained using the link part of the guardian.

  :mps:tag:`poolstruct.rings.justify` This is because rings are convenient to
  use and are well tested. It is possible to implement all three lists
  using a singly linked list, but the saving is certainly not worth
  making at this stage.

- :mps:tag:`poolstruct.refring` a ring of "ref" segments in use for links or
  messages (see .mrgseg.ref.mrgring below).

- :mps:tag:`poolstruct.extend` a precalculated ``extendBy`` field (see
  :mps:ref:`.init.extend`). This value is used to determine how large a
  segment should be requested from the arena for the reference part
  segment when the pool needs to grow (see :mps:ref:`.alloc.grow.size`).

  :mps:tag:`poolstruct.extend.justify` Calculating a reasonable value for this
  once and remembering it simplifies the allocation (:mps:ref:`.alloc.grow`).

:mps:tag:`poolstruct.init` poolstructs are initialized once for each pool
instance by :c:func:`MRGInit()` (:mps:ref:`.init`). The initial state has all the
rings initialized to singleton rings, and the ``extendBy`` field
initialized to some value (see :mps:ref:`.init.extend`).

:mps:tag:`mrgseg` The pool defines two segment subclasses:
:c:type:`MRGRefSegClass` and :c:type:`MRGLinkSegClass`. Segments of the former
class will be used to store the ref parts of guardians, segments of
the latter will be used to store the link parts of guardians (see
:mps:ref:`.guardian.two-part`). Segments are always allocated in pairs, with
one of each class, by the function :c:func:`MRGSegPairCreate()`. Each
segment contains a link to its pair.

:mps:tag:`mrgseg.ref` :c:type:`MRGRefSegClass` is a subclass of :c:type:`MutatorSegClass`.
Instances are of type ``MRGRefSeg``, and contain:

- :mps:tag:`mrgseg.ref.mrgring` a field for the ring of ref part segments in
  the pool.

- :mps:tag:`mrgseg.ref.linkseg` a pointer to the paired link segment.

- :mps:tag:`mrgseg.ref.grey` a set describing the greyness of the segment for each trace.

:mps:tag:`mrgseg.ref.init` A segment is created and initialized once every
time the pool is grown (:mps:ref:`.alloc.grow`). The initial state has the
segment ring node initialized and attached to the pool's segment ring,
the linkseg field points to the relevant link segment, the grey field
is initialized such that the segment is not grey for all traces.

:mps:tag:`mrgseg.link` :c:type:`MRGLinkSegClass` is a subclass of :c:type:`SegClass`.
Instances are of type ``MRGLinkSeg``, and contain:

- :mps:tag:`mrgseg.link.refseg` a pointer to the paired ref segment. This
  may be :c:macro:`NULL` during initialization, while the pairing is being
  established.

- :mps:tag:`mrgseg.link.init` The initial state has the ``linkseg`` field
  pointing to the relevant ref segment.


Functions
---------

.. c:function:: Bool MRGCheck(MRG mrg)

:mps:tag:`check` Check the signatures, the class, and each field of the
:c:type:`MRGStruct`. Each field is checked as being appropriate for its
type.

:mps:tag:`check.justify` There are no non-trivial invariants that can
be easily checked.

.. c:function:: Res MRGRegister(Pool pool, Ref ref)

:mps:tag:`alloc` Add a guardian for ``ref``.

:mps:tag:`alloc.grow` If the free list is empty then two new segments are
allocated and the free list filled up from them (note that the
reference fields of the new guardians will need to be overwritten with
:c:macro:`NULL`, see :mps:ref:`.free.overwrite`)

:mps:tag:`alloc.grow.size` The size of the reference part segment will be
the pool's ``extendBy`` (:mps:ref:`.poolstruct.extend`) value. The link part
segment will be whatever size is necessary to accommodate *N* link
parts, where *N* is the number of reference parts that fit in the
reference part segment.

:mps:tag:`alloc.error` If any of the requests for more resource (there are
two; one for each of two segments) fail then the successful requests
will be retracted and the result code from the failing request will be
returned.

:mps:tag:`alloc.pop` :c:func:`MRGRegister()` pops a ring node off the free list,
and add it to the entry list.

.. c:function:: Res MRGDeregister(Pool pool, Ref obj)

:mps:tag:`free` Remove the guardian from the message queue and add it to the
free list.

:mps:tag:`free.push` The guardian will simply be added to the front of the
free list (that is, no keeping the free list in address order or
anything like that).

:mps:tag:`free.inadequate` No attempt will be made to return unused free
segments to the arena (although see
analysis.mps.poolmrg.improve.free.* for suggestions).

:mps:tag:`free.overwrite` :c:func:`MRGDeregister()` also writes over the reference
with :c:macro:`NULL`. :mps:tag:`free.overwrite.justify` This is so that when the
segment is subsequently scanned (:mps:ref:`.scan.free`), the reference that
used to be in the object is not accidentally fixed.

.. c:function:: Res MRGInit(Pool pool, ArgList args)

:mps:tag:`init` Initializes the entry list, the free ring, the ref ring, and
the ``extendBy`` field.

:mps:tag:`init.extend` The ``extendBy`` field is initialized to the arena
grain size.

:mps:tag:`init.extend.justify` This is adequate as the pool is not expected
to grow very quickly.

.. c:function:: void MRGFinish(Pool pool)

:mps:tag:`finish` Iterate over all the segments, returning all the segments
to the arena.

.. c:function:: Res mrgRefSegScan(Bool *totalReturn, Pool pool, Seg seg, ScanState ss)

:mps:tag:`scan` :c:func:`mrgRefSegScan()` scans a segment of guardians.

:mps:tag:`scan.trivial` Scan will do nothing (that is, return immediately)
if the tracing rank is anything other than final.

.. note::

    This optimization is missing. impl.c.trace.scan.conservative is
    not a problem because there are no faults on these segs, because
    there are no references into them. But that's why :c:func:`TraceScan()`
    can't do it. Pekka P. Pirinen, 1997-09-19.

:mps:tag:`scan.trivial.justify` If the rank is lower than final then
scanning is detrimental, it will only delay finalization. If the rank
is higher than final there is nothing to do, the pool only contains
final references.

:mps:tag:`scan.guardians` :c:func:`mrgRefSegScan()` will iterate over all
guardians in the segment. Every guardian's reference will be fixed
(:mps:tag:`scan.free` note that guardians that are on the free list have
:c:macro:`NULL` in their reference part).

:mps:tag:`scan.wasold` If the object referred to had not been fixed
previously (that is, was unmarked) then the object is not referenced
by a reference of a lower rank (than ``RankFINAL``) and hence is
finalizable.

:mps:tag:`scan.finalize` The guardian will be finalized. This entails moving
the guardian from state Prefinal to Final; it is removed from the
entry list and initialized as a message and posted on the arena's
message queue.

:mps:tag:`scan.finalize.idempotent` In fact this will only happen if the
guardian has not already been finalized (which is determined by
examining the state of the guardian).

:mps:tag:`scan.unordered` Because scanning occurs a segment at a time, the
order in which objects are finalized is "random" (it cannot be
predicted by considering only the references between objects
registered for finalization). See
analysis.mps.poolmrg.improve.semantics for how this can be improved.

:mps:tag:`scan.unordered.justify` Unordered finalization is all that is
required.

See analysis.mps.poolmrg.improve.scan.nomove for a suggested
improvement that avoids redundant unlinking and relinking.

.. c:function:: Res MRGDescribe(Pool pool, mps_lib_FILE *stream, Count depth)

:mps:tag:`describe` Describes an MRG pool. Iterates along each of the entry
and exit lists and prints the guardians in each. The location of the
guardian and the value of the reference in it will be printed out.
Provided for debugging only.


Transgressions
--------------

:mps:tag:`trans.no-finish` The MRG pool does not trouble itself to tidy up
its internal rings properly when being destroyed.

:mps:tag:`trans.free-seg` No attempt is made to release free segments to the
arena. A suggested strategy for this is as follows:

- Add a count of free guardians to each segment, and maintain it in
  appropriate places.

- Add a free segment ring to the pool.

- In :c:func:`mrgRefSegScan()`, if the segment is entirely free, don't scan
  it, but instead detach its links from the free ring, and move the
  segment to the free segment ring.

- At some appropriate point, such as the end of :c:func:`MRGAlloc()`,
  destroy free segments.

- In :c:func:`MRGAlloc()`, if there are no free guardians, check the free
  segment ring before creating a new pair of segments. Note that this
  algorithm would give some slight measure of segment hysteresis. It
  is not the place of the pool to support general segment hysteresis.


Future
------

:mps:tag:`future.array` In future, for speed or simplicity, this pool could
be rewritten to use an array. See `mail.gavinm.1997-09-04.13-08`_.

.. _mail.gavinm.1997-09-04.13-08: https://info.ravenbrook.com/project/mps/mail/1997/09/04/13-08/0.txt


Tests
-----

.. note::

    This section is utterly out of date. Pekka P. Pirinen, 1997-09-19.

:mps:tag:`test` The test impl.c.finalcv is similar to the weakness test (see
design.mps.weakness, impl.c.weakcv).


Functionality
.............

This is the functionality to be tested:

- :mps:tag:`fun.alloc` Can allocate objects.
- :mps:tag:`fun.free` Can free objects that were allocated.
- :mps:tag:`prot.write` Can write a reference into an allocated object.
- :mps:tag:`prot.read` Can read the reference from an allocated object.
- :mps:tag:`promise.faithful` A reference stored in an allocated object will
  continue to refer to the same object.
- :mps:tag:`promise.live` A reference stored in an allocated object will
  preserve the object referred to.
- :mps:tag:`promise.unreachable` Any objects referred to in finalization
  messages are not (at the time of reading the message) reachable via
  a chain of ambiguous or exact references. (we will not be able to
  test this at first as there is no messaging interface)
- :mps:tag:`promise.try` The pool will make a "good faith" effort to
  finalize objects that are not reachable via a chain of ambiguous or
  exact references.

Attributes
..........

The following attributes will be tested:

- :mps:tag:`attr.none` There are no attribute requirements.

Implementation
..............

The test will simply allocate a number of objects in the AMC pool and
finalize each one, throwing away the reference to the objects. Churn.

:mps:tag:`test.mpm` The test will use the MPM interface (impl.h.mpm).

:mps:tag:`test.mpm.justify` This is because it is not intended to provide an
MPS interface to this pool directly, and the MPS interface to
finalization has not been written yet (impl.h.mps).

:mps:tag:`test.mpm.change` Later on it may use the MPS interface, in which
case, where the following text refers to allocating objects in the MRG
pool it will need adjusting.

:mps:tag:`test.two-pools` The test will use two pools, an AMC pool, and an
MRG pool.

:mps:tag:`test.alloc` A number of objects will be allocated in the MRG pool.

:mps:tag:`test.free` They will then be freed. This will test :mps:ref:`.fun.alloc`
and :mps:ref:`.fun.free`, although not very much.

:mps:tag:`test.rw.a` An object, "A", will be allocated in the AMC pool, a
reference to it will be kept in a root.

:mps:tag:`test.rw.alloc` A number of objects will be allocated in the MRG
pool.

:mps:tag:`test.rw.write` A reference to "A" will be written into each
object.

:mps:tag:`test.rw.read` The reference in each object will be read and
checked to see if it refers to "A".

:mps:tag:`test.rw.free` All the objects will be freed.

:mps:tag:`test.rw.drop` The reference to "A" will be dropped. This will test
:mps:ref:`.prot.write` and :mps:ref:`.prot.read`.

:mps:tag:`test.promise.fl.alloc` A number of objects will be allocated in
the AMC pool.

:mps:tag:`test.promise.fl.tag` Each object will be tagged uniquely.

:mps:tag:`test.promise.fl.refer` a reference to it will be stored in an
object allocated in the MRG pool.

:mps:tag:`test.promise.fl.churn` A large amount of garbage will be allocated
in the AMC pool. Regularly, whilst this garbage is being allocated, a
check will be performed that all the objects allocated in the MRG pool
refer to valid objects and that they still refer to the same objects.
All objects from the MRG pool will then be freed (thus dropping all
references to the AMC objects). This will test :mps:ref:`.promise.faithful`
and :mps:ref:`.promise.live`.

:mps:tag:`test.promise.ut.alloc` A number of objects will be allocated in
the AMC pool.

:mps:tag:`test.promise.ut.refer` Each object will be referred to by a root
and also referred to by an object allocated in the MRG pool.

:mps:tag:`test.promise.ut.drop` References to a random selection of the
objects from the AMC pool will be deleted from the root.

:mps:tag:`test.promise.ut.churn` A large amount of garbage will be allocated
in the AMC pool.

:mps:tag:`test.promise.ut.message` The message interface will be used to
receive finalization messages.

:mps:tag:`test.promise.ut.final.check` For each finalization message
received it will check that the object referenced in the message is
not referred to in the root.

:mps:tag:`test.promise.ut.nofinal.check` After some amount of garbage has
been allocated it will check to see if any objects are not in the root
and haven't been finalized. This will test :mps:ref:`.promise.unreachable` and
:mps:ref:`.promise.try`.


Notes
-----

:mps:tag:`access.inadequate` :c:func:`SegAccess()` will scan segments at
`RankEXACT``. Really it should be scanned at whatever the minimum rank
of all grey segments is (the trace rank phase), however there is no
way to find this out. As a consequence we will sometimes scan pages at
``RankEXACT`` when the pages could have been scanned at ``RankFINAL``.
This means that finalization of some objects may sometimes get
delayed.