author Gareth Rees
date 2015-09-01
index terms pair: bootstrap; design
revision //
status incomplete design
tag design.mps.bootstrap


.intro: This explains how the MPS gets started.

.readership: Any MPS developer.

.overview: The job of the MPS is to allocate memory to a program. Before it can allocate memory, the MPS needs to create data structures to represent its internal state. But before it can create those data structures, it needs to allocate memory to store them in. This bootstrapping problem affects the MPS at several points, which are listed here, together with their solutions.

Bootstrapping problems

Virtual memory descriptor

.vm: Before address space can be mapped into main memory, the virtual memory descriptor must be initialized. But before the virtual memory descriptor can be initialized, some address space must be mapped into main memory in order to store it. See design.vm.req.bootstrap.

.vm.sol: The virtual memory descriptor is allocated initially on the stack, and then copied into its place in the chunk after the memory for it has been mapped. See design.vm.sol.bootstrap.

Arena descriptor

.arena: Before chunks of address space can be reserved and mapped, the virtual memory arena descriptor must be initialized (so that the chunks can be added to the arena's chunk tree). But before a virtual memory arena descriptor can be initialized, address space must be reserved and mapped in order to store it.

.arena.sol: A small amount of address space is reserved and mapped directly via VMInit() and VMMap() (not via the chunk system) in order to provide enough memory for the arena descriptor.

Arena's free land

.land: Before the arena can allocate memory, a range of addresses must be inserted into the arena's free land (so that the free land can hand out memory from this range). But before addresses can be inserted into the arena's free land, the free land's block pool must have memory from the arena to store the nodes in the tree representing those addresses.

.land.sol: The arena has two "back door" mechanisms and uses them in combination.

.land.sol.alloc: First, there is a mechanism for allocating a page of memory directly from a chunk, bypassing the free land.

.land.sol.pool: Second, the free land's block pool has an option to prevent it extending itself by allocating memory from the arena. Instead, it fails allocations with ResLIMIT. The free land's block pool also has a mechanism, MFSExtend to extend it with a block of memory. When the free land fails with ResLIMIT the arena uses .land.sol.alloc to provide it with memory.

Document History

  • 2015-09-01 GDR Initial draft.
  • 2016-02-25 RB Improving description of arena free land bootstrap and cross-referencing from source code.