Why is it important to manage address space?

1. Trace differentiability

   Carefully chosen addresses are used by reference tracing systems (ie. automatic pools), to categorise objects into clumps; and to summarise and cheaply find references between clumps.

   Different clumps will become worth collecting at different times (the classic example, of course, is generations in a generational collector). For these partial collections to be efficient, it must be cheap to keep these clumps differentiable, cheap to condemn (Whiten) a particular clump, and cheap to find a good conservative approximation to all inward references to a clump (both initially to construct the Grey set, and to make scanning the Grey set efficient).

   This is what the MPS zone mechanism is all about.

   The locus manager manages the mapping from clumps to zones.

   To specify a clump, pools can pass LocusPrefZONESET and a set of zones to LocusPrefExpress().

2. Prevent address space fragmentation (within the arena)

   Address space is not infinite.

   In some use cases, the MPS is required to remain efficient when using very nearly all available address space and storage. For example, with the client-arena class, where the only address space available is that of the storage available.

   Even with the VM arena class, typical storage sizes (as of 2007) can make 32-bit address space constrained: the client may need several gigabytes, which leaves little spare address space.

   Address space fragmentation incurs failure when there is no way to allocate a big block of address space. The big block may be requested via the MPS (by the client), or by something else in the same process, such as a third-party graphics library, image library, etc.

   Address space fragmentation incurs cost when:

   • desired large-block requests (such as for buffering) are denied, causing them to be re-requested as a smaller block, or as several smaller blocks;
   • possible operating-system costs in maintaining a fragmented mapping?

3. Prevent storage fragmentation (within tracts and segments)

   Storage is not infinite: it is allocated in multiples of a fixed-size tract. Small lonely objects, each retaining a whole tract, cause storage fragmentation.

   Non-moving pools manage this fragmentation with placement strategies that use:

   • co-located death (in space and time);
   • segment merging and splitting.

   These pool-level strategies always care about contiguity of object storage. They also often care about the ordering of addresses, because pool code uses an address-ordered search when choosing where to place a new object. For these two reasons, the address chosen (by the locus manager and arena) for new tracts is important.

   Certain specialised pools, and/or some client programs that use them, have carefully tuned segment sizes, positioning, and search order. Be careful: seemingly inconsequential changes can catastrophically break this tuning.

   Pools can specify a preference for High and Low ends of address space, which implies a search-order. Pools could also specify clumping, using LocusPrefZONESET.

Discovering the layout

The locus manager is not given advance notice of how much address space will be required with what preferences. Instead, the locus manager starts with an empty layout, and adapts it as more requests come in over time. It is attempting to discover a suitable layout by successive refinement. This is ambitious.

Loci

Res LocusCreate(Locus *locusReturn, LocusAttrs attrs, ZoneGroup zg, LocusAllocDesc adesc)

.function.create: A function to create a locus: adesc contains the information about the allocation sequences in the locus, zg is used for zone differentiability, and attrs encodes the following:

• .locus.contiguity: A locus can be contiguous. This means performing as required in .req.contiguity, non-contiguous allocations can be freely placed anywhere (but efficiency dictates that similar allocations are placed close together and apart from others).
• .locus.blacklist: Allocations in the locus will avoid blacklisted pages (for collectable segments).
• .locus.zero: Allocations in the locus are zero-filled.

.interface.zone-group: The locus can be made a member of a zone group. Passing ZoneGroupNONE means it's not a member of any group (allocations will be placed without regard to zone, except to keep them out of stripes likely to be needed for some group).

.interface.size: An allocation descriptor (LocusAllocDesc) contains various descriptions of how the locus will develop over time (inconsistent specifications are forbidden, of course):

• .interface.size.typical-alloc: Size of a typical allocation in this locus, in bytes. This will mainly affect the grouping of non-contiguous loci.

• .interface.size.large-alloc: Typical large allocation that the manager should try to allow for (this allows some relief from .req.counter.objects), in bytes. This will mainly affect the size of gaps that will be allotted adjoining this locus.

• .interface.size.direction: Direction of growth: up/down/none.

  Only useful if the locus is contiguous.

• .interface.size.lifetime: Some measure of the lifetime of tracts (not objects) in the cohort.

  Note

  Don't know the details yet, probably only useful for placing similar cohorts next to each other, so the details don't actually matter. Pekka P. Pirinen, 2000-01-17.

• .interface.size.deathtime: Some measure of the deathtime of tracts (not objects) in the cohort.

  Note

  Ditto. Pekka P. Pirinen, 2000-01-17.

.function.init: LocusInit() is like LocusCreate(), but without the allocation. This is the usual interface, since most loci are embedded in a pool or something.

.function.alloc: ArenaAlloc() to take a locus argument. ArenaAllocHere() is like it, plus it takes a tract and a specification to place the new allocation immediately above/below a given tract; if that is not possible, it returns ResFAIL (this will make it useful for reallocation functionality).

void ArenaSetTotalLoci(Arena arena, Size nLoci, Size nZoneGroups)

.function.set-total: A function to tell the arena the expected number of (non-miscible client) loci, and of zone groups.

Peaks

mps_res_t mps_peak_create(mps_peak_t*, mps_arena_t)

.function.peak.create: A function to create a peak. A newly-created peak is open, and will not be used to guide the strategy of the locus manager.

mps_res_t mps_peak_describe_pool(mps_peak_t, mps_pool_t, mps_size_desc_t)

.function.peak.add: A function to add a description of the state of one pool into the peak. Calling this function again for the same peak and pool instance will replace the earlier description.

.function.peak.add.size: The size descriptor contains a total size in bytes or percent of arena size.

.function.peak.add.remove: Specifying a NULL size will remove the pool from the peak. The client is not allowed to destroy a pool that is mentioned in any peak; it must be first removed from the peak, or the peak must be destroyed. This is to ensure that the client adjusts the peaks in a manner that makes sense to the application; the locus manager can't know how to do that.

mps_res_t mps_peak_close(mps_peak_t)

.function.peak.close: A function to indicate that all the significant pools have been added to the peak, and it can now be used to guide the locus manager. For any pool not described in the peak, the locus manager will take its current size at any given moment as the best prediction of its size at the peak.

.function.peak.close.after: It is legal to add more descriptions to the peak after closing, but this will reopen the peak, and it will have to be closed before the locus manager will use it again. The locus manager uses the previous closed state of the peak, while this is going on.

void mps_peak_destroy(mps_peak_t)

.function.peak.destroy: A function to destroy a peak.

.interface.ep-style: This satisfies .req.ep-style by allowing SW to specify zero size for most pools (which will cause them to be place next to other loci with the same growth direction).

Data objects

.arch.locus: To represent the cohorts, we have locus objects. Usually a locus is embedded in a pool instance, but generations are separate loci.

.arch.locus.attr: contiguity, blacklist, zg, current region, @@@@

.arch.locus.attr.exceptional: The client can define a typical large allocation for the locus. Requests substantially larger than that are deemed exceptional.

.arch.zone-group: To satisfy .req.differentiable, we offer zone groups. Each locus can be a member of a zone group, and the locus manager will attempt to place allocations in this locus in different zones from all the other zone groups. A zone-group is represented as @@@@.

.arch.page-table: A page table is maintained by the arena, as usual to track association between tracts, pools and segments, and mapping status for VM arenas.

.arch.region: All of the address space is divided into disjoint regions, represented by region objects. These objects store their current limits, and high and low watermarks of currently allocated tracts (we hope there's usually a gap of empty space between regions). The limits are actually quite porous and flexible.

.arch.region.assoc: Each region is associated with one contiguous locus or any number of non-contiguous loci (or none). We call the first kind of region "contiguous". .arch.locus.assoc: Each locus remembers all regions where it has tracts currently, excepting the badly-placed allocations (see below). It is not our intention that any locus would have very many, or that loci that share regions would have any reason to stop doing do.

.arch.region.more: Various quantities used by the placement computation are also stored in the regions and the loci. Regions are created (and destroyed) by the placement recomputation. Regions are located in stripes (if it's a zoned region), but they can extend into neighboring stripes if an exceptionally large tract allocation is requested (to allow for large objects).

.arch.chunk: Arenas may allocate more address space in additional chunks, which may be disjoint from the existing chunks. Inter-chunk space will be represented by dummy regions. There are also sentinel regions at both ends of the address space. See design.mps.arena.chunk.

Overview of strategy

.arch.strategy.delay: The general strategy is to delay placement decisions until they have to be made, but no later.

.arch.strategy.delay.until: Hence, the locus manager only makes placement decisions when an allocation is requested (frees and other operations might set a flag to cause the next allocation to redecide). This also allows the client to change the peak and pool configuration in complicated ways without causing a lot of recomputation, by doing all the changes without allocating in the middle (unless the control pool needs more space because of the changes).

.arch.strategy.normal: While we want the placement to be sophisticated, we do not believe it is worth the effort to consider all the data at each allocation. Hence, allocations are usually just placed in one of the regions used previously (see .arch.alloc) without reconsidering the issues.

.arch.strategy.normal.limit: However, the manager sets precautionary limits on the regions to ensure that the placement decisions are revisited when an irrevocable placement is about to be made.

.arch.strategy.create: The manager doesn't create new regions until they are needed for allocation (but it might compute where they could be placed to accommodate a peak).

Allocation

.arch.alloc: Normally, each allocation to a locus is placed in its current region. New regions are only sought when necessary to fulfill an allocation request or when there is reason to think the situation has changed significantly (see .arch.significant).

.arch.alloc.same: An allocation is first attempted next to the previous allocation in the same locus, respecting growth direction. If that is not possible, a good place in the current region is sought. .arch.alloc.same.hole: At the moment, for finding a good place within a region, we just use the current algorithm, limited to the region. In future, the placement within regions will be more clever.

.arch.alloc.extend: If there's no adequate hole in the current region and the request is not exceptional, the neighboring regions are examined to see if the region could be extended at one border. (This will basically only be done if the neighbor has shrunk since the last placement recomputation, because the limit was set on sophisticated criteria, and should not be changed without justification.) .arch.alloc.extend.here: When an allocation is requested next to a specific tract (ArenaAllocHere()), we try to extend a little harder (at least for change_size, perhaps not for locality).

.arch.alloc.other: If no way can be found to allocate in the current region, other regions used for this locus are considered in the same way, to see if space can be found there. [Or probably look at other regions before trying to extend anything?]

.arch.alloc.recompute: When no region of this locus has enough space for the request, or when otherwise required, region placement is recomputed to find a new region for the request (which might be the same region, after extension).

.arch.alloc.current: This region where the allocation was placed then becomes the current region for this locus, except when the request was exceptional, or when the region chosen was "bad" (see @@@@).

.arch.significant: Significant changes to the parameters affecting placement are deemed to have happened at certain client calls and when the total allocation has changed substantially since the last recomputation. Such conditions set a flag that causes the next allocation to recompute even if its current region is not full (possibly second-guess the decision to recompute after some investigation of the current state?).

Deallocation

.arch.free: Deallocation simply updates the counters in the region and the locus. For some loci, it will make the region of the deallocation the current region. .arch.free.remove: If a region becomes entirely empty, it is deleted (and the neighbors limits might be adjusted).

Region placement recomputation

.arch.gap: When doing placement computations, we view the arena as a sequence of alternating region cores and gaps (which can be small, even zero-sized). Initially, we'll take the core of a region to be the area between the high and low watermark, but in the future we might be more flexible about that.

.arch.reach: The gap between two cores could potentially end up being allocated to either region, if they grow in that direction, or one or neither, if they don't. The set of states that the region assignment could reach by assigning the gaps to their neighbors is called the reach of the current configuration.

.arch.placement.object: The object of the recomputation is to find a configuration of regions that is not too far from the current configuration and that keeps all the peaks inside its reach; if that is not possible, keep the nearest ones in the reach and then minimize the total distance from the rest.

.arch.placement.hypothetical: The configurations that are considered will include hypothetical placements for new regions for loci that cannot fit in their existing regions at the peak. This is necessary to avoid choosing a bad alternative.

.arch.placement.interesting: The computation will only consider new regions of loci that are deemed interesting, that is, far from their peak state. This will reduce the computational burden and avoid jittering near a peak.