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


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

.. _design-poolmvff:


MVFF pool class
===============

.. mps:prefix:: design.mps.poolmvff
   pair: MVFF pool class; design
   single: pool class; MVFF design


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

:mps:tag:`intro` This is the design of the MVFF (Manual Variable First-Fit)
pool class. This pool implements a first (or last) fit policy for
variable-sized manually-managed objects, with control over first/last,
segment preference high/low, and slot fit low/high.

:mps:tag:`background` The pool was created in a response to a belief that
the ScriptWorks EPDL/EPDR's first fit policy is beneficial for some
classes of client behaviour, but the performance of a linear free list
was unacceptable.


Overview
--------

:mps:tag:`over` This pool implements certain variants of the address-ordered
first-fit policy. The implementation allows allocation across segment
boundaries.

:mps:tag:`over.buffer` Buffered allocation is also supported, but in that
case, the buffer-filling policy is worst-fit. Buffered and unbuffered
allocation can be used at the same time, but in that case, the first
ap must be created before any allocations.

:mps:tag:`over.buffer.class` The pool uses the simplest buffer class,
:c:type:`BufferClass`. This is appropriate since these buffers don't attach
to segments, and hence don't constrain buffered regions to lie within
segment boundaries.


Methods
-------

:mps:tag:`method.buffer` The buffer methods implement a worst-fit fill
strategy.


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

:mps:tag:`impl.alloc_list` The pool stores the address ranges that it has
acquired from the arena in a CBS (see design.mps.cbs_).

:mps:tag:`impl.free-list` The pool stores its free list in a CBS (see
design.mps.cbs_), failing over in emergencies to a Freelist (see
design.mps.freelist_) when the CBS cannot allocate new control
structures. This is the reason for the alignment restriction above.

.. _design.mps.cbs: cbs.html
.. _design.mps.freelist: freelist.html


Details
-------

:mps:tag:`design.acquire-size` When acquiring memory from the arena, we use
``extendBy`` as the unit of allocation unless the object won't fit, in
which case we use the object size (in both cases we align up to the
arena alignment).

:mps:tag:`design.acquire-fail` If allocating ``extendBy``, we try again with
an aligned size just large enough for the object we're allocating.
This is in response to request.mps.170186_.

.. _request.mps.170186: https://info.ravenbrook.com/project/mps/import/2001-11-05/mmprevol/request/mps/170186