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
.. index::
   pair: nailboard; design

.. _design-nailboard:


Nailboards for ambiguously referenced segments
==============================================

.. mps:prefix:: design.mps.nailboard


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

:mps:tag:`intro` This document describes the nailboard design for the Memory
Pool System.

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

:mps:tag:`overview` A nailboard represents a set of addresses to which
ambiguous references have been found. It is implemented as a
specialized bit table that maps addresses within a range to *nails*.
The mapping has granularity, so that all addresses within a word, say,
will map to the same nail.

:mps:tag:`purpose` Nailboards are used by the AMC pool class to record
ambiguous references to grains within a segment. See
design.mps.poolamc.nailboard.


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

:mps:tag:`req.granularity` A nailboard must be able to set nails for
addresses down to the grain size of the segment. (Because individual
objects may be this small, and we must be able to preserve or reclaim
individual objects.)

:mps:tag:`req.set` A nailboard must be able to set a nail corresponding to
any aligned address in the range covered. (Because ambiguous
references may have arbitrary values.)

:mps:tag:`req.reset.not` A nailboard is *not* required to be able to reset a
nail. (Because resetting a nail would correspond to proving that there
is *no* ambiguous reference to that address, but that can only be
established when the trace is complete.)

:mps:tag:`req.range` A nailboard must be able to determine if any nail is
set in a continguous range. (Because we must preserve the whole object
if there is any ambiguous reference to it.)

:mps:tag:`req.range.cost` Determining if any nail is set in a continuous
range must be cheap. That is, it must take time that is no more than
logarithmic in the size of the range. (Because scanning overhead must
be proportional to the number of objects, not to their size.)


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

:mps:tag:`impl.table` The nailboard consists of a header structure and one
or more bit tables. Each bit table covers the whole range of
addresses, but at a different level of detail.

:mps:tag:`impl.table.level0` The level 0 bit table has one bit for each
aligned address in the range.

:mps:tag:`impl.align` The alignment of the nailboard need not be the same as
the pool alignment. This is because nailboards are per-segment, and
the pool may know the minimum size of an object in a particular
segment.

:mps:tag:`impl.table.k` The level *k* bit table has one bit for each ``scale``
bits in the level *k*\−1 bit table (this bit is set if any bit in the
corresponding word in the level *k*\−1 table is set).

:mps:tag:`impl.scale` Here ``scale`` is an arbitrary scale factor that must
be a power of 2. It could in future be supplied as a parameter when
creating a nailboard, but in the current implementation it is always
:c:macro:`MPS_WORD_WIDTH`.

:mps:tag:`impl.table.last` The last bit table is always shorter than one
word. This is slightly wasteful in some cases (for example, a
nailboard with 64 nails and ``scale`` 64 will have two levels, the
second level having just one bit), but allows the code to support
small nailboards without special cases in the code (consider the case
of a nailboard with just one nail).

:mps:tag:`impl.size` The size of the level *i* bit table is the ceiling of

   (``limit`` − ``base``) / (``align`` × ``scale``\ :superscript:`i`\ )

where ``base`` and ``limit`` are the bounds of the address range being
represented in the nailboard and ``align`` is the alignment.

:mps:tag:`impl.address` The address *a* may be looked up in the level *i*
bit table at the bit

   (*a* − ``base``) / (``align`` × ``scale``\ :superscript:`i`\ )

and since ``align`` and ``scale`` are powers of 2, that's

   (*a* − ``base``) >> (log\ :subscript:`2`\ ``align`` + *i* log\ :subscript:`2`\ ``scale``)

:mps:tag:`impl.set` Setting a nail for an address *a* in a nailboard is on
the critical path: it is called for every fix of an ambiguous
reference to an address in an AMC pool. When setting a nail, we set
the corresponding bit in every level of the nailboard.

:mps:tag:`impl.isresrange` Testing a range of addresses to see if any nails
are set is also on the critical path: it is called for every object in
any AMC segment with a nailboard when the segment is scanned and when
it is reclaimed.

:mps:tag:`impl.isresrange.strategy` The strategy for testing to see if any
nails are set in a range is to handle the cases that are expected to
be common first. In particular, we expect that there will only be few
nails in a nailboard, so most calls to :c:func:`NailboardIsResRange()` will
return :c:macro:`TRUE`.

:mps:tag:`impl.isresrange.alignment` When testing a range against a level of
a nailboard, the base and limit of the range will typically not align
exactly to the bits of that level. Therefore we test against a
slightly larger range, as shown in the diagram:

.. figure:: nailboard-1.svg
    :align: center
    :alt: Diagram: Testing a range against a level of a nailboard.

    Testing a range against a level of a nailboard.

:mps:tag:`impl.isresrange.empty` If all bits in the range [``ibase``,
``ilimit``) are reset, as shown above, then there are no nails in the
range of addresses [``base``, ``limit``). This provides an early exit
with result :c:macro:`TRUE`.

:mps:tag:`impl.isresrange.level0` If the "empty" early exit is not taken,
and we are looking at the level 0 bit table, then the range is not
empty. This provides an early exit with result :c:macro:`FALSE`.

:mps:tag:`impl.isresrange.inner` If any bit in the range [``ibase``\+1,
``ilimit``\−1) is set, as shown below, then there is a nail in the
range of addresses [``base``, ``limit``). This provides an early exit
with result :c:macro:`FALSE`.

.. figure:: nailboard-2.svg
    :align: center
    :alt: Diagram: a nail is set in this range.

    A nail is set in this range.

:mps:tag:`impl.isresrange.splinter` If none of the three early exits is
taken, then we are in a situation like the one shown below, with one
or two *splinters*. In this situation we know that there is a nail,
but it is not clear whether the nail is inside the splinter or not. We
handle this situation by moving up to the previous level and looking
at the range of addresses covered by the splinter.

.. figure:: nailboard-3.svg
    :align: center
    :alt: Diagram: it is not clear if a nail is set in this range.

    It is not clear if a nail is set in this range.

:mps:tag:`impl.isresrange.splinter.recurse` When looking at a splinter, we
might reach the same situation: namely, that the interior of the
splinter is empty, but the edge of the splinter is set. We handle this
by reducing the size of the splinter and moving up to the previous
level.

:mps:tag:`impl.isresrange.splinter.one-sided` This splinter-of-a-splinter is
one-sided: that is, we don't need to look at the right splinter of a
left splinter or vice versa, because we know that it is empty.


Future
------

:mps:tag:`future.tune` The implementation makes heavy use of
``BTIsResRange``, but this function is not well tuned for scanning
small arrays (which we expect to be the common case for nailboards).
Performance might be improved by special-casing the small levels.

:mps:tag:`future.limit` In C and C++, a pointer to "one past the last
element of an array object" (the limit of the object in our
terminology) is a valid pointer and can be used in pointer arithmetic.
See §6.5.6.8–9 of [C1999]_. So in theory a programmer could have such
a pointer as the only reference keeping an object alive, and still
expect to be able to subtract from it to get back to the object. The
current nailboard implementation does not support this use case.


References
----------

.. [C1999]
   International Standard ISO/IEC 9899:1999;
   "Programming languages — C";
   <http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf>