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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
.. highlight:: none


.. index::
   pair: LO pool class; design
   single: pool class; LO design

.. _design-poollo:


LO pool class
=============

.. mps:prefix:: design.mps.poollo
   pair: LO pool class; design
   single: pool class; LO design


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

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

:mps:tag:`intro` The LO (Leaf Object) pool class is a pool class developed
for DylanWorks. It is designed to manage objects that have no
references (leaf objects) such as strings, bit tables, etc. It is a
garbage collected pool (in that objects allocated in the pool are
automatically reclaimed when they are discovered to be unreachable.

.. note::

    Need to sort out issue of alignment. Currently lo grabs alignment
    from format, almost certainly "ought" to use the greater of the
    format alignment and the :c:macro:`MPS_ALIGN` value. David Jones,
    1997-07-02.


Definitions
-----------

:mps:tag:`def.leaf` A "leaf" object is an object that contains no
references, or an object all of whose references refer to roots. That
is, any references that the object has must refer to a priori alive
objects that are guaranteed not to move, hence the references do not
need fixing.

:mps:tag:`def.grain` A grain (of some alignment) is a contiguous aligned
area of memory of the smallest size possible (which is the same size
as the alignment).


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

:mps:tag:`req.source` See req.dylan.fun.obj.alloc and
req.dylan.prot.ffi.access.

:mps:tag:`req.leaf` The pool must manage formatted leaf objects (see
:mps:ref:`.def.leaf` above for a definition). This is intended to encompass
Dylan and C leaf objects. Dylan leaf objects have a reference to their
wrapper, but are still leaf objects (in the sense of :mps:ref:`.def.leaf`)
because the wrapper will be a root.

:mps:tag:`req.nofault` The memory containing objects managed by the pool
must not be protected. The client must be allowed to access these
objects without hitting an MPS barrier.


Overview
--------

:mps:tag:`overview`

:mps:tag:`overview.ms` The LO Pool is a non-moving mark-and-sweep collector.

:mps:tag:`overview.ms.justify` Mark-and-sweep pools are simpler than moving
pools.

:mps:tag:`overview.alloc` Objects are allocated in the pool using the
reserve/commit protocol on allocation points.

:mps:tag:`overview.format` The pool is formatted. The format of the objects
in the pool is specified at instantiation time, using a format object
derived from a variant A format (using variant A is overkill, see
:mps:ref:`.if.init` below) (see design.mps.format for excuse about calling the
variant 'A').


Interface
---------

:mps:tag:`if.init`

:mps:tag:`if.init.args` The init method for this class takes one extra
parameter in the vararg parameter list.

:mps:tag:`if.init.format` The extra parameter should be an object of type
Format and should describe the format of the objects that are to be
allocated in the pool.

:mps:tag:`if.init.format.use` The pool uses the skip and alignment slots of
the format. The skip method is used to determine the length of objects
(during reclaim). The alignment field is used to determine the
granularity at which memory should be managed.

:mps:tag:`if.init.format.a` Currently only format variant A is supported
though clearly that is overkill as only skip and alignment are used.


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

:mps:tag:`sig` The signature for the LO Pool Class is 0x51970b07
(SIGLOPOoL).

:mps:tag:`poolstruct` The class specific pool structure is::

    typedef struct LOStruct {
      PoolStruct poolStruct;        /* generic pool structure */
      PoolGenStruct pgenStruct;     /* pool generation */
      PoolGen pgen;                 /* NULL or pointer to pgenStruct */
      Sig sig;                      /* <code/misc.h#sig> */
    } LOStruct;

:mps:tag:`loseg` Every segment is an instance of segment class
:c:type:`LOSegClass`, a subclass of :c:type:`MutatorSegClass` (see
design.mps.seg.over.hierarchy.mutatorseg_), and is an object of type
:c:type:`LOSegStruct`.

.. _design.mps.seg.over.hierarchy.mutatorseg: seg.html#design.mps.seg.over.hierarchy.mutatorseg

:mps:tag:`loseg.purpose` The purpose of the ``LOSeg`` structure is to
associate the bit tables used for recording allocation and mark
information with the segment.

:mps:tag:`loseg.decl` The declaration of the structure is as follows::

    typedef struct LOSegStruct {
      GCSegStruct gcSegStruct;  /* superclass fields must come first */
      BT mark;                  /* mark bit table */
      BT alloc;                 /* alloc bit table */
      Count freeGrains;         /* free grains */
      Count bufferedGrains;     /* grains in buffers */
      Count newGrains;          /* grains allocated since last collection */
      Count oldGrains;          /* grains allocated prior to last collection */
      Sig sig;                  /* <code/misc.h#sig> */
    } LOSegStruct;

:mps:tag:`loseg.sig` The signature for a loseg is 0x519705E9 (SIGLOSEG).

:mps:tag:`loseg.lo` The lo field points to the LO structure that owns this
segment.

:mps:tag:`loseg.bit` Bit Tables (see design.mps.bt_) are used to record
allocation and mark information. This is relatively straightforward,
but might be inefficient in terms of space in some circumstances.

.. _design.mps.bt: bt.html

:mps:tag:`loseg.mark` This is a Bit Table that is used to mark objects
during a trace. Each grain in the segment is associated with 1 bit in
this table. When :c:func:`loSegFix()` (see :mps:ref:`.fun.fix` below) is called the
address is converted to a grain within the segment and the
corresponding bit in this table is set.

:mps:tag:`loseg.alloc` This is a Bit Table that is used to record which
addresses are allocated. Addresses that are allocated and are not
buffered have their corresponding bit in this table set. If a bit in
this table is reset then either the address is free or is being
buffered.

:mps:tag:`loseg.diagram` The following diagram is now obsolete. It's also
not very interesting - but I've left the sources in case anyone ever
gets around to updating it. tony 1999-12-16

[missing diagram]


Functions
---------

External
........

:mps:tag:`fun.init`

:mps:tag:`fun.destroy`

:mps:tag:`fun.buffer-fill`

.. note::

    Explain way in which buffers interact with the alloc table and how
    it could be improved.

:mps:tag:`fun.buffer-empty`

:mps:tag:`fun.condemn`


Internal
........

.. c:function:: Res loSegFix(Seg seg, ScanState ss, Ref *refIO)

:mps:tag:`fun.fix` Fix treats references of most ranks much the same. There
is one mark table that records all marks. A reference of rank
``RankAMBIG`` is first checked to see if it is aligned to the pool
alignment and discarded if not. The reference is converted to a grain
number within the segment (by subtracting the segments' base from the
reference and then dividing by the grain size). The bit (the one
corresponding to the grain number) is set in the mark table.
Exception, for a weak reference (rank is ``RankWEAK``) the mark table
is checked and the reference is fixed to 0 if this address has not
been marked otherwise nothing happens. Note that there is no check
that the reference refers to a valid object boundary (which wouldn't
be a valid check in the case of ambiguous references anyway).

.. c:function:: void loSegReclaim(Seg seg, Trace trace)

:mps:tag:`fun.segreclaim` For all the contiguous allocated regions in the
segment it locates the boundaries of all the objects in that region by
repeatedly skipping (by calling ``format->skip``) from the beginning
of the region (the beginning of the region is guaranteed to coincide
with the beginning of an object). For each object it examines the bit
in the mark bit table that corresponds to the beginning of the object.
If that bit is set then the object has been marked as a result of a
previous call to :c:func:`loSegFix()`, the object is preserved by doing
nothing. If that bit is not set then the object has not been marked
and should be reclaimed; the object is reclaimed by resetting the
appropriate range of bits in the segment's free bit table.

.. note::

    Special things happen for buffered segments.

    Explain how the marked variable is used to free segments.


Attachment
----------

[missing attachment "LOGROUP.CWK"]