11. Free list allocator¶
11.1. Introduction¶
.intro: This is the design of the free list allocator.
.readership: Any MPS developer.
11.2. Overview¶
.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.
11.3. Requirements¶
In addition to the generic land requirements (see design.mps.land), free lists must satisfy:
.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.
11.4. Interface¶
.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.
11.4.1. Types¶
-
struct FreelistStruct *
Freelist¶
.type.freelist: The type of free lists. A FreelistStruct is
typically embedded in another structure.
11.4.2. Classes¶
.class: CLASS(Freelist) is the free list class, a subclass of
CLASS(Land) suitable for passing to LandInit().
11.4.3. Keyword arguments¶
When initializing a free list, LandInit() takes no keyword
arguments. Pass mps_args_none.
11.5. Implementation¶
.impl.list: The isolated contiguous free address ranges are kept on
an address-ordered singly linked free list. (As in traditional
malloc() implementations.)
.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.
.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.
.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.
.impl.invariant: The ranges stored in the free list are isolated: no two ranges are adjacent or overlapping.
.impl.merge: When a free address range is added to the free list, it is merged with adjacent ranges so as to maintain .impl.invariant.
.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 .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.)
11.6. Testing¶
.test: The following testing will be performed on this module:
.test.land: A generic test for land implementations. See design.mps.land.test.
.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.
11.7. Opportunities for improvement¶
.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.
.improve.maxsize: We could maintain the maximum size of any range
on the list, and use that to make an early exit from
freelistFindLargest(). It’s not clear that this would actually be
an improvement.
