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
.. highlight:: none


.. index::
   pair: walk; design

.. _design-walk:


Walking formatted objects
=========================

.. mps:prefix:: design.mps.walk


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

:mps:tag:`intro` This is the design of the formatted objects walk interface.
The intended audience is MPS developers.

:mps:tag:`source` Based on [GDR_2020-08-30]_.


Use cases
---------

:mps:tag:`case.reload` A language runtime that offers hot reloading of code
will need to walk all objects belonging to a class (say) in order to
modify the references in the objects so they refer to the updated
class definition. [Strömbäck_2020-08-20]_

:mps:tag:`case.serialize` A language runtime that offers serialization and
deserialization of the heap will need to walk all formatted objects in
order to identify references to globals (during serialization) and
modify references to refer to the new locations of the globals (after
deserialization). [GDR_2018-08-30]_


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

:mps:tag:`req.walk.all` It must be possible for the client program to visit
all automatically managed formatted objects using a callback.

:mps:tag:`req.walk.assume-format` The callback should not need to switch on
the format, as this may be awkward in a program which has modules
using different pools with different formats.

:mps:tag:`req.walk.examine` It must be possible for the callback to examine
other automatically managed memory while walking the objects.

:mps:tag:`req.walk.modify` It must be possible for the callback to modify
the references in the objects.

:mps:tag:`req.walk.overhead` The overhead of calling the callback should be
minimized.

:mps:tag:`req.walk.perf` The performance of subsequent collections should
not be affected.

:mps:tag:`req.walk.closure` The callback must have access to arbitrary data
from the caller.

:mps:tag:`req.walk.maint` The interface should be easy to implement and
maintain.


Design
------

A new public function :c:func:`mps_pool_walk()` visits the live formatted
objects in an automatically managed pool.

:mps:tag:`sol.walk.all` The client program must know which pools it has
created so it can call :c:func:`mps_pool_walk()` for each pool.

:mps:tag:`sol.walk.assume-format` All objects in a pool share the same
format, so the callback does not need to switch on the format.

:mps:tag:`sol.walk.examine` :c:func:`mps_pool_walk()` must only be called when the
arena is parked, and so there is no read barrier on any object.

:mps:tag:`sol.walk.modify` :c:func:`mps_pool_walk()` arranges for write-protection
to be removed from each segment while it is being walked and restored
afterwards if necessary.

:mps:tag:`sol.walk.overhead` The callback is called for contiguous regions
of formatted objects (not just for each object) where possible so that
the per-object function call overhead is minimized.

:mps:tag:`sol.walk.perf` The callback uses the scanning protocol so that
every reference is fixed and the summary is maintained.

:mps:tag:`sol.walk.closure` :c:func:`mps_pool_walk()` takes a closure pointer
which is stored in the :c:type:`ScanState` and passed to the callback.

:mps:tag:`sol.walk.maint` We reuse the scanning protocol and provide a
generic implementation that iterates over the ring of segments in the
pool. We set up an empty white set in the :c:type:`ScanState` so that the
:c:func:`MPS_FIX1()` test always fails and ``_mps_fix2()`` is never called.
This avoids any per-pool code to support the interface.


References
----------

.. [GDR_2018-08-30] Gareth Rees. 2018-08-30. "`Save/restore draft proposal <https://info.ravenbrook.com/mail/2018/08/30/12-57-09/0/>`__".

.. [GDR_2020-08-30] Gareth Rees. 2020-08-30. "`Re: Modifying objects during mps_formatted_objects_walk <https://info.ravenbrook.com/mail/2020/08/31/19-17-03/0/>`__".

.. [Strömbäck_2020-08-20] Filip Strömbäck. 2020-08-20. "`Modifying objects during mps_formatted_objects_walk <https://info.ravenbrook.com/mail/2020/08/20/21-01-34/0/>`__".