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


.. index::
   pair: free list allocator; design

.. _design-freelist:


Free list allocator
===================

.. mps:prefix:: design.mps.freelist


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

:mps:tag:`intro` This is the design of the free list allocator.

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


Overview
--------

:mps:tag:`overview` The free list allocator is an "emergency" allocator. It
is intended for use as a fallback allocation strategy in low memory
situations, when memory is not available for the control structures
needed by other allocators. In these situations the free list allocator
ensures that memory is not lost, but with several disadvantages:

#. operations on the free list take time proportional to the number of
   free blocks;
#. the data structures are stored in client memory and so are
   vulnerable to corruption;
#. the data structures have poor locality (and thus potentially poor
   cache performance).

When memory becomes available again to allocate control structures,
the free lists can be "flushed" back into the more efficient data
structures.


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

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

.. _design.mps.land: land.html

:mps:tag:`req.zero-overhead` Must have zero space overhead for the storage
of any set of free blocks, so that it can be used to manage memory
when no memory can be allocated for control structures.


Interface
---------

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


Types
.....

.. c:type:: struct FreelistStruct *Freelist

:mps:tag:`type.freelist` The type of free lists. A :c:type:`FreelistStruct` is
typically embedded in another structure.


Classes
.......

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


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

When initializing a free list, :c:func:`LandInit()` takes no keyword
arguments. Pass ``mps_args_none``.


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

:mps:tag:`impl.list` The isolated contiguous free address ranges are kept on
an address-ordered singly linked free list. (As in traditional
:c:func:`malloc()` implementations.)

:mps:tag:`impl.block` If the free address range is large enough to contain
an inline block descriptor consisting of two pointers, then the two
pointers stored are to the next free range in address order (or
``freelistEND`` if there are no more ranges), and to the limit of the
current free address range, in that order.

:mps:tag:`impl.grain` Otherwise, the free address range must be large enough
to contain a single pointer. The pointer stored is to the next free
range in address order, or ``freelistEND`` if there are no more
ranges.

:mps:tag:`impl.tag` Grains and blocks are distinguished by a one-bit tag in
the low bit of the first word (the one containing the pointer to the
next range). Grains have this bit set; blocks have this bit reset.

:mps:tag:`impl.invariant` The ranges stored in the free list are *isolated*:
no two ranges are adjacent or overlapping.

:mps:tag:`impl.merge` When a free address range is added to the free list,
it is merged with adjacent ranges so as to maintain
:mps:ref:`.impl.invariant`.

:mps:tag:`impl.rule.break` The use of ``freelistEND`` to mark the end of the
list violates the rule that exceptional values should not be used to
distinguish exeptional situations. This infraction allows the
implementation to meet :mps:ref:`.req.zero-overhead`. (There are other ways to
do this, such as using another tag to indicate the last block in the
list, but these would be more complicated.)


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` Two pools (MVT_ and MVFF_) use free lists as a fallback
when low on memory. These are subject to testing in development, QA,
and are heavily exercised by customers.

.. _MVT: poolmvt
.. _MVFF: poolmvff



Opportunities for improvement
-----------------------------

:mps:tag:`improve.length` When iterating over the list, we could check that
the number of elements visited in the course of the iteration does not
exceed the recorded size of the list.

:mps:tag:`improve.maxsize` We could maintain the maximum size of any range
on the list, and use that to make an early exit from
:c:func:`freelistFindLargest()`. It's not clear that this would actually be
an improvement.