1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
.. highlight:: none


.. index::
   pair: bootstrap; design

.. _design-bootstrap:


Bootstrapping
=============

.. mps:prefix:: design.mps.bootstrap


Introduction
------------

:mps:tag:`intro` This explains how the MPS gets started.

:mps:tag:`readership` Any MPS developer.

:mps:tag:`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
.........................

:mps:tag:`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`_.

:mps:tag:`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`_.

.. _design.vm.req.bootstrap: vm#req.bootstrap
.. _design.vm.sol.bootstrap: vm#sol.bootstrap


Arena descriptor
................

:mps:tag:`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.

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


Arena's free land
.................

:mps:tag:`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.

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

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

:mps:tag:`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 :mps:ref:`.land.sol.alloc` to provide it with memory.