10. Free list allocator

10.1. Introduction

.intro: This is the design of the free list allocator.

.readership: Any MPS developer.

10.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:

  1. operations on the free list take time proportional to the number of free blocks;

  2. the data structures are stored in client memory and so are vulnerable to corruption;

  3. 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.

10.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.

10.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.

10.4.1. Types

struct FreelistStruct *Freelist

.type.freelist: The type of free lists. A FreelistStruct may be embedded in another structure, or you can create it using LandCreate().

10.4.2. External functions

LandClass FreelistLandClassGet(void)

.function.class: The function FreelistLandClassGet() returns the free list class, a subclass of LandClass suitable for passing to LandCreate() or LandInit().

10.4.3. Keyword arguments

When initializing a free list, LandCreate() and LandInit() take no keyword arguments. Pass mps_args_none.

10.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.)

10.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.

10.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.