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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
.. highlight:: none


.. index::
   pair: virtual memory arena; design
   pair: VM arena; design

.. _design-arenavm:


Virtual Memory Arena
====================

.. mps:prefix:: design.mps.arena.vm
   pair: virtual memory arena; design
   pair: VM arena; design


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

:mps:tag:`intro` This is the design of the Virtual Memory Arena Class of the
Memory Pool System. The VM Arena Class is just one class available in
the MPS. The generic arena part is described in design.mps.arena_.

.. _design.mps.arena: arena.html


Overview
--------

:mps:tag:`overview` VM arenas provide blocks of memory to all other parts of
the MPS in the form of "tracts" using the virtual mapping interface
(design.mps.vm_) to the operating system. The VM Arena Class is not
expected to be provided on platforms that do not have virtual memory
(for example, Macintosh System 7).

.. _design.mps.vm: vm.html

:mps:tag:`overview.gc` The VM Arena Class provides some special services on
these blocks in order to facilitate garbage collection:

:mps:tag:`overview.gc.zone` Allocation of blocks with specific zones. This
means that the generic fix function (design.mps.fix_) can use a fast
refset test to eliminate references to addresses that are not in the
condemned set. This assumes that a pool class that uses this placement
appropriately is being used (such as the generation placement policy
used by AMC: see design.mps.poolamc_) and that the pool selects the
condemned sets to coincide with zone stripes.

.. _design.mps.fix: fix.html
.. _design.mps.poolamc: poolamc.html

:mps:tag:`overview.gc.tract` A fast translation from addresses to tract.
(See design.mps.arena.req.fun.trans_.)

.. _design.mps.arena.req.fun.trans: arena.html#design.mps.arena.req.fun.trans


Notes
-----

:mps:tag:`note.refset` Some of this document simply assumes that RefSets
(see design.mps.collections.refsets_) have been chosen as the solution for
design.mps.arena.req.fun.set_. It's a lot simpler that way. Both to
write and understand.

.. _design.mps.collections.refsets: collections.html#design.mps.collections.refsets
.. _design.mps.arena.req.fun.set: arena.html#design.mps.arena.req.fun.set


Requirements
------------

Most of the requirements are in fact on the generic arena (see
design.mps.arena.req_). However, many of those requirements can only
be met by a suitable arena class design.

.. _design.mps.arena.req: arena.html#design.mps.arena.req

Requirements particular to this arena class:

Placement
.........

:mps:tag:`req.fun.place` It must be possible for pools to obtain tracts at
particular addresses. Such addresses shall be declared by the pool
specifying what refset zones the tracts should lie in and what refset
zones the tracts should not lie in. It is acceptable for the arena to
not always honour the request in terms of placement if it has run out
of suitable addresses.

Arena partition
...............

:mps:tag:`req.fun.set` See design.mps.arena.req.fun.set_. The
approximation to sets of address must cooperate with the placement
mechanism in the way required by :mps:ref:`.req.fun.place` (above).


Architecture
------------

:mps:tag:`arch.memory` The underlying memory is obtained from whatever
Virtual Memory interface (see design.mps.vm_). @@@@ Explain why this
is used.


Solution ideas
--------------

:mps:tag:`idea.grain` Set the arena granularity to the grain provided by the
virtual mapping module.

:mps:tag:`idea.mem` Get a single large contiguous address area from the
virtual mapping interface and divide that up.

:mps:tag:`idea.table` Maintain a table with one entry per grain in order to
provide fast mapping (shift and add) between addresses and table
entries.

:mps:tag:`idea.table.figure` [missing figure]

:mps:tag:`idea.map` Store the pointers (design.arena.req.fun.trans) in the
table directly for every grain.

:mps:tag:`idea.zones` Partition the managed address space into zones (see
idea.zones) and provide the set approximation as a reference
signature.

:mps:tag:`idea.first-fit` Use a simple first-fit allocation policy for
tracts within each zone (:mps:ref:`.idea.zones`). Store the freelist in the
table (:mps:ref:`.idea.table`).

:mps:tag:`idea.base` Store information about each contiguous area (allocated
of free) in the table entry (:mps:ref:`.idea.table`) corresponding to the base
address of the area.

:mps:tag:`idea.shadow` Use the table (:mps:ref:`.idea.table`) as a "shadow" of the
operating system's page table. Keep information such as last access,
protection, etc. in this table, since we can't get at this information
otherwise.

:mps:tag:`idea.barrier` Use the table (:mps:ref:`.idea.table`) to implement the
software barrier. Each segment can have a read and/or write barrier
placed on it by each process. (:mps:tag:`idea.barrier.bits` Store a
bit-pattern which remembers which process protected what.) This will
give a fast translation from a barrier-protected address to the
barrier handler via the process table.

:mps:tag:`idea.demand-table` For a 1 GiB managed address space with a 4 KiB
page size, the table will have 256K-entries. At, say, four words per
entry, this is 4 MiB of table. Although this is only an 0.4%, the
table shouldn't be preallocated or initially it is an infinite
overhead, and with 1 MiB active, it is a 300% overhead! The address
space for the table should be reserved, but the pages for it mapped
and unmapped on demand. By storing the table in a tract, the status of
the table's pages can be determined by looking at it's own entries in
itself, and thus the translation lookup (design.arena.req.fun.trans)
is slowed to two lookups rather than one.

:mps:tag:`idea.pool` Make the Arena Manager a pool class. Arena
initialization becomes pool creation. Tract allocation becomes
:c:func:`PoolAlloc()`. Other operations become class-specific operations on
the "arena pool".


Data structures
---------------

:mps:tag:`tables` There are two table data structures: a page table, and an
alloc table.

:mps:tag:`table.page.map` Each page in the VM has a corresponding page table
entry.

:mps:tag:`table.page.linear` The table is a linear array of PageStruct
entries; there is a simple mapping between the index in the table and
the base address in the VM. Namely:

- index to base address: ``base-address = arena-base + (index * page-size)``
- base address to index: ``index = (base-address - arena-base) / page-size``

:mps:tag:`table.page.partial` The table is partially mapped on an
"as-needed" basis using the SparseArray abstract type.

:mps:tag:`table.page.tract` Each page table entry contains a tract, which is
only valid if it is allocated to a pool. If it is not allocated to a
pool, the fields of the tract are used for other purposes. (See
design.mps.arena.tract.field.pool_)

.. _design.mps.arena.tract.field.pool: arena.html#design.mps.arena.tract.field.pool

:mps:tag:`table.alloc` The alloc table is a simple bit table (implemented
using the BT module, design.mps.bt_).

.. _design.mps.bt: bt.html

:mps:tag:`table.alloc.map` Each page in the VM has a corresponding alloc
table entry.

:mps:tag:`table.alloc.semantics` The bit in the alloc table is set iff the
corresponding page is allocated (to a pool).


Notes
-----

:mps:tag:`fig.page` How the pages in the arena area are represented in the
tables.

[missing figure]

:mps:tag:`fig.count` How a count table can be used to partially map the page
table, as proposed in request.dylan.170049.sol.map_.

.. _request.dylan.170049.sol.map: https://info.ravenbrook.com/project/mps/import/2001-11-05/mmprevol/request/dylan/170049

[missing figure]