2. Coalescing block structures

2.1. Introduction

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

.readership: This document is intended for any MM developer.

.source: design.mps.poolmvt, design.mps.poolmvff.

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

2.2. Requirements

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

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

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

2.3. Interface

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

2.3.1. External types

struct CBSStruct *CBS

.type.cbs: The type of coalescing block structures. A CBSStruct may be embedded in another structure, or you can create it using LandCreate().

2.3.2. External functions

LandClass CBSLandClassGet(void)

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

LandClass CBSFastLandClassGet(void)

.function.class: Returns a subclass of CBSLandClass that maintains, for each subtree, the size of the largest block in that subtree. This enables the LandFindFirst(), LandFindLast(), and LandFindLargest() generic functions.

LandClass CBSZonedLandClassGet(void)

.function.class: Returns a subclass of CBSFastLandClass that maintains, for each subtree, the union of the zone sets of all ranges in that subtree. This enables the LandFindInZones() generic function.

2.3.3. Keyword arguments

When initializing a CBS, LandCreate() and LandInit() take the following optional keyword arguments:

• CBSBlockPool (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.

• MPS_KEY_CBS_EXTEND_BY (type Size; default 4096) is passed as the MPS_KEY_EXTEND_BY keyword argument to 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 Bool; default TRUE) is passed to PoolCreate() if a block descriptor pool is created. If TRUE, the block descriptor pool automatically extends itself when out of space; if FALSE, the pool returns ResLIMIT in this case. (This feature is used by the arena to bootstrap its own CBS of free memory.)

2.3.4. Limitations

.limit.find: CBSLandClass does not support the LandFindFirst(), LandFindLast(), and LandFindLargest() generic functions (the subclasses do support these operations).

.limit.zones: CBSLandClass and CBSFastLandClass do not support the LandFindInZones() generic function (the subclass CBSZonedLandClass does support this operation).

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

.limit.flush: CBS cannot be used as the source in a call to LandFlush(). (Because of .limit.iterate.)

2.4. Implementation

2.4.1. Splay tree

.impl.splay: The CBS is implemented using a splay tree (see design.mps.splay). Each splay tree node is embedded in a block structure that represents a semi-open address range. The key passed for comparison is the base of another range.

.impl.splay.fast-find: In the CBSFastLandClass class, cbsFindFirst() and 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.

.impl.find-largest: cbsFindLargest() simply finds out the size of the largest block in the CBS from the root of the tree, using SplayRoot(), and does 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 cbsFindLargest().

.impl.splay.zones: In the CBSZonedLandClass class, 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.

2.4.2. Low memory behaviour

.impl.low-mem: When the CBS tries to allocate a new CBSBlock structure for a new isolated range as a result of either LandInsert() or 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 LandInsert() or LandDelete() returns ResMEMORY.

2.4.3. The CBS block

.impl.cbs.block: The block contains a base-limit pair and a splay tree node.

.impl.cbs.block.special: The base and limit may be equal if the block is halfway through being deleted.

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

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

2.6. Notes for future development

.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 .req.fast).

.future.hybrid: It would be possible to attenuate the problem of .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).

.future.iterate.and.delete: It would be possible to provide an implementation for the LandIterateAndDelete() generic function by calling TreeToVine() first, and then iterating over the vine (where deletion is straightforward).

2.7. Risks

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