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


.. index::
   pair: coalescing block structures; design

.. _design-cbs:


Coalescing block structures
===========================

.. mps:prefix:: design.mps.cbs


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

:mps:tag:`intro` This is the design for impl.c.cbs, which implements a data
structure for the management of non-intersecting memory ranges, with
eager coalescence.

:mps:tag:`readership` This document is intended for any MM developer.

:mps:tag:`source` design.mps.poolmvt_, design.mps.poolmvff_.

.. _design.mps.poolmvt: poolmvt.html
.. _design.mps.poolmvff: poolmvff.html

:mps:tag:`overview` The "coalescing block structure" is a set of addresses
(or a subset of address space), with provision for efficient
management of contiguous ranges, including insertion and deletion,
high level communication with the client about the size of contiguous
ranges, and detection of protocol violations.


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

In addition to the generic land requirements (see
design.mps.land_), the CBS must satisfy:

.. _design.mps.land: land.html

:mps:tag:`req.fast` Common operations must have a low amortized cost.

:mps:tag:`req.small` Must have a small space overhead for the storage of
typical subsets of address space and not have abysmal overhead for the
storage of any subset of address space.


Interface
---------

:mps:tag:`land` CBS is an implementation of the *land* abstract data type,
so the interface consists of the generic functions for lands. See
design.mps.land_.


External types
..............

.. c:type:: struct CBSStruct *CBS

:mps:tag:`type.cbs` The type of coalescing block structures. A :c:type:`CBSStruct`
is typically embedded in another structure.


External classes
................

:mps:tag:`class.cbs` ``CLASS(CBS)`` is the CBS class, a subclass of
``CLASS(Land)`` suitable for passing to :c:func:`LandInit()`.

:mps:tag:`class.fast` ``CLASS(CBSFast)`` is subclass of ``CLASS(CBS)`` that
maintains, for each subtree, the size of the largest block in that
subtree. This enables the :c:func:`LandFindFirst()`, :c:func:`LandFindLast()`, and
:c:func:`LandFindLargest()` generic functions.

:mps:tag:`class.zoned` ``CLASS(CBSZoned)`` is a subclass of
``CLASS(CBSFast)`` that maintains, for each subtree, the union of the
zone sets of all ranges in that subtree. This enables the
:c:func:`LandFindInZones()` generic function.


Keyword arguments
.................

When initializing a CBS, :c:func:`LandInit()` takes the following optional
keyword arguments:

* ``CBSBlockPool`` (type :c:type:`Pool`) is the pool from which the CBS
  block descriptors will be allocated. If omitted, a new MFS pool is
  created for this purpose.

* :c:macro:`MPS_KEY_CBS_EXTEND_BY` (type :c:type:`Size`; default 4096) is passed as
  the :c:macro:`MPS_KEY_EXTEND_BY` keyword argument to :c:func:`PoolCreate()` if a
  block descriptor pool is created. It specifies the size of segment
  that the block descriptor pool will request from the arena.

* ``MFSExtendSelf`` (type :c:type:`Bool`; default :c:macro:`TRUE`) is passed to
  :c:func:`PoolCreate()` if a block descriptor pool is created. If :c:macro:`TRUE`,
  the block descriptor pool automatically extends itself when out of
  space; if :c:macro:`FALSE`, the pool returns ``ResLIMIT`` in this case.
  (This feature is used by the arena to bootstrap its own CBS of free
  memory. See design.mps.bootstrap.land.sol.pool_.)

  .. _design.mps.bootstrap.land.sol.pool: bootstrap.html#design.mps.bootstrap.land.sol.pool


Limitations
...........

:mps:tag:`limit.find` :c:type:`CBSLandClass` does not support the
:c:func:`LandFindFirst()`, :c:func:`LandFindLast()`, and :c:func:`LandFindLargest()`
generic functions (the subclasses do support these operations).

:mps:tag:`limit.zones` :c:type:`CBSLandClass` and :c:type:`CBSFastLandClass` do not
support the :c:func:`LandFindInZones()` generic function (the subclass
:c:type:`CBSZonedLandClass` does support this operation).

:mps:tag:`limit.iterate` CBS does not provide an implementation for the
:c:func:`LandIterateAndDelete()` generic function. This is because
:c:func:`TreeTraverse()` does not permit modification, for speed and to
avoid perturbing the splay tree balance.

:mps:tag:`limit.flush` CBS cannot be used as the source in a call to
:c:func:`LandFlush()`. (Because of :mps:ref:`.limit.iterate`.)


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

Splay tree
..........

:mps:tag:`impl.splay` The CBS is implemented using a splay tree (see
design.mps.splay_). Each splay tree node is embedded in a block
structure with a semi-open address range (design.mps.range_). The
splay tree is ordered by the range base address.

.. _design.mps.splay: splay.html
.. _design.mps.range: range.html

:mps:tag:`impl.splay.fast-find` In the :c:type:`CBSFastLandClass` class,
:c:func:`cbsFindFirst()` and :c:func:`cbsFindLast()` use the update/refresh
facility of splay trees to store, in each block, an accurate summary
of the maximum block size in the tree rooted at the corresponding
splay node. This allows rapid location of the first or last suitable
block, and very rapid failure if there is no suitable block.  For
example, this is used in the implementation of allocation in the MVFF
pool class (design.mps.poolmvff_).

.. _design.mps.poolmvff: poolmvff.html

:mps:tag:`impl.find-largest` :c:func:`cbsFindLargest()` simply finds out the size
of the largest block in the CBS from the root of the tree, using
:c:func:`SplayRoot()`, and does :c:func:`SplayFindFirst()` for a block of that
size. This takes time proportional to the logarithm of the size of the
free list, so it's about the best you can do without maintaining a
separate priority queue, just to do :c:func:`cbsFindLargest()`.  For
example, this is used in the implementation of allocation buffers in
the MVFF pool class (design.mps.poolmvff_).

:mps:tag:`impl.splay.zones` In the :c:type:`CBSZonedLandClass` class,
:c:func:`cbsFindInZones()` uses the update/refresh facility of splay trees
to store, in each block, the union of the zones of the ranges in the
tree rooted at the corresponding splay node. This allows rapid
location of a block in a set of zones.  For example, this is used to
allocate segments in particular zones in the arena to optimised
garbage collection (see design.mps.critical-path_).

.. _design.mps.critical-path: critical-path.html


Low memory behaviour
....................

:mps:tag:`impl.low-mem` When the CBS tries to allocate a new ``CBSBlock``
structure for a new isolated range as a result of either
:c:func:`LandInsert()` or :c:func:`LandDelete()`, and there is insufficient memory
to allocate the block structure, then the range is not added to the
CBS or deleted from it, and the call to :c:func:`LandInsert()` or
:c:func:`LandDelete()` returns ``ResMEMORY``.


The CBS block
.............

:mps:tag:`impl.cbs.block` The block contains a non-empty range and a splay
tree node.

:mps:tag:`impl.cbs.block.special` The range may be empty if the block is
halfway through being deleted.

:mps:tag:`impl.cbs.block.special.just` This conflates values and status, but
is justified because block size is very important.


Testing
-------

:mps:tag:`test` The following testing will be performed on this module:

:mps:tag:`test.land` A generic test for land implementations. See
design.mps.land.test_.

.. _design.mps.land.test: land.html#design.mps.land.test

:mps:tag:`test.pool` The arena and two pools (MVT_ and MVFF_) are
implemented on top of a CBS. These are subject to testing in
development, QA, and are heavily exercised by customers.

.. _MVT: poolmvt
.. _MVFF: poolmvff


Notes for future development
----------------------------

:mps:tag:`future.not-splay` The implementation of CBSs is based on splay
trees. It could be revised to use other data structures that meet the
requirements (especially :mps:ref:`.req.fast`).

:mps:tag:`future.hybrid` It would be possible to attenuate the problem of
:mps:ref:`.risk.overhead` (below) by using a single word bit set to represent
the membership in a (possibly aligned) word-width of grains. This
might be used for block sizes less than a word-width of grains,
converting them when they reach all free in the bit set. Note that
this would make coalescence slightly less eager, by up to
``(word-width - 1)``.

:mps:tag:`future.iterate.and.delete` It would be possible to provide an
implementation for the :c:func:`LandIterateAndDelete()` generic function
using :c:func:`TreeTraverseAndDelete()`, which calls :c:func:`TreeToVine()` first,
iterates over the vine (where deletion is straightforward), and then
rebalances the tree. Note that this is little better than using
:c:func:`SplayFirst()` and :c:func:`SplayNext()`.

:mps:tag:`future.lazy-coalesce` It's long been observed that small blocks
are often freed and then reallocated, so that coalescing them is a
waste of time.  It might be worth considering how a splay tree could
implement a lazy coalescing scheme, where blocks are coalesced with
their adjacent neighbours during the search only if they aren't big
enough.  This would break :mps:ref:`.impl.find-largest` and so might be best
done as a different kind of land.  On the other hand, since the MPS
does not use client memory to store the tree, eager coalescing avoids
allocation.


Risks
-----

:mps:tag:`risk.overhead` Clients should note that the current implementation
of CBSs has a space overhead proportional to the number of isolated
contiguous ranges. [Four words per range.] If the CBS contains every
other grain in an area, then the overhead will be large compared to
the size of that area. [Four words per two grains.] The CBS structure
is thus suitable only for managing large enough ranges.