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
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
.. _glossary-f:

=============================
Memory Management Glossary: F
=============================

.. include:: alphabet.txt

.. glossary::

    fencepost
    fence post

        A fencepost is spare :term:`memory (1)` between
        :term:`allocated` :term:`blocks` for checking purposes.

        Some :term:`memory management` systems leave spare memory
        between allocated blocks and store special values in it. If a
        checking routine finds that these memory :term:`locations
        <memory location>` have been modified, this probably indicates
        an :term:`overwriting error` in the application that was
        allocated the adjacent block.

        Such checking can help application programmers to find bugs
        that would otherwise be difficult to reproduce and track down.

        .. similar:: :term:`in-band header`.

    fencepost error
    fence post error

        The term *fencepost error* refers to errors arising from the
        fact that, to enclose *n* consecutive intervals, you need
        *n* + 1 end-points, from the number of posts required to
        support fence rails.

        An example of a fencepost error would be, in :term:`C`::

            void f(void)
            {
              int i;
              int a[10];
              for(i = 0; i <= 10; i++)
                a[i] = 0;
            }

        because the declaration ``int a[10];`` creates an array of ten
        integers, with indices from 0 to 9, but the ``for`` loop index
        ``i`` runs from 0 to 10.

    Fibonacci buddies

        A common :term:`buddy system` :term:`allocation mechanism`, in
        which block sizes form a Fibonacci series (each block size is
        the sum of the two previous sizes). Each block can therefore
        be :term:`split` to form two blocks of valid sizes, and the
        sizes are more closely spaced than in :term:`binary buddies`.
        However, if the same size is allocated repeatedly, performance
        may suffer as the remainder blocks may have to be split again
        (or become fragments).

        .. seealso:: :term:`buddy system`, :term:`allocation mechanism`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    FIFO-ordered first fit

        The :term:`allocation policy` that always uses the
        least-recently :term:`freed (1)` suitable :term:`free
        block`. Commonly implemented by adding freed blocks to the end
        of a :term:`free block chain`, and then using :term:`first
        fit` allocation on this chain. :term:`free (1)` can be very
        quick, depending on the :term:`coalescing <coalesce>` policy.

        According to :ref:`Wilson et al. (1995) <WIL95>`, this policy
        controls fragmentation quite well, better than
        :term:`LIFO-ordered first fit` and as well as
        :term:`address-ordered first fit` in some cases, although
        :term:`locality <locality of reference>` may be worse.

    file mapping

        .. see:: :term:`memory mapping`.

    finalization

        .. aka:: *termination*.

        In :term:`garbage-collected <garbage collection>` languages,
        it is often necessary to perform actions on some
        :term:`objects` after they are no longer in use and
        before their :term:`memory (2)` can be :term:`recycled
        <recycle>`. These actions are known as *finalization* or
        *termination*.

        A common use of finalization is to release resources when the
        corresponding "proxy" object dies. For example, an open file
        might be represented by a stream object. When this object has
        been proven :term:`dead` by the :term:`collector (1)`, it is
        certain that the file is no longer in use by the program, and
        it can and should be closed before the stream is recycled.

        Note that finalization is not, in general, guaranteed to be
        prompt, and this can cause problems if it is used to manage
        scarce operating system resources such as file descriptors.

        Many object-oriented languages provide support for
        finalization, for example, Cedar, :term:`Java`, :term:`Perl`
        5, and :term:`Smalltalk`.

        The term *finalization* is sometimes used to refer to the use
        of :term:`destructors (1)`, for example in Ada.

        .. mps:specific:: See :ref:`topic-finalization`.

    finalized block

        .. mps:specific::

           A :term:`block` that has been registered for finalization
           using :c:func:`mps_finalize`, and which the MPS has
           determined is :term:`dead`, but whose finalization message
           has not been discarded. See
           :c:func:`mps_message_type_finalization`.

    first fit

        First fit is a :term:`sequential fit` :term:`allocation
        mechanism`.

        To quote :ref:`Wilson et al. (1995) <WIL95>`:

            First fit simply searches the :term:`free list` from the
            beginning, and uses the first :term:`free block` large
            enough to satisfy the request. If the block is larger than
            necessary, it is split and the remainder is put on the
            free list.

        The first fit mechanism provides a class of first fit
        :term:`allocation policies`, depending on the order in which
        the free list is stored. :term:`Address-ordered first fit`
        stores the list in order of (usually increasing) address.
        :term:`LIFO-ordered first fit` puts blocks on the front of the
        free list when they are :term:`freed (1)`. :term:`FIFO-ordered
        first fit` puts blocks on the end of the free list when they
        are :term:`freed (1)`.

        .. seealso:: :term:`address-ordered first fit`, :term:`LIFO-ordered first fit`, :term:`FIFO-ordered first fit`, :term:`sequential fit`, :term:`next fit`, :term:`best fit`, :term:`worst fit`.

    fix

        .. mps:specific::

            To *fix* a :term:`reference` from one :term:`block` to
            another is to declare it to the MPS by calling
            :c:func:`MPS_FIX1` and :c:func:`MPS_FIX2` within a
            :term:`scan method`. In a :term:`moving <moving garbage
            collector>` :term:`pool`, fixing a reference may also
            update it to point to the new location of the block. See
            :ref:`topic-scanning`.

    flip

        The instant in a :term:`two-space collector` when the roles of
        the two :term:`semi-spaces` are reversed. What
        was the :term:`tospace` is now marked as :term:`fromspace` and
        :term:`condemned <condemned set>`. What was the fromspace
        becomes the site for all new :term:`allocations
        <allocate>`. Also used in a more general sense to mean the
        initiation of a new :term:`collection cycle`.

        .. figure:: ../diagrams/two-space.svg
            :align: center
            :alt: Diagram: In a two-space collector, the *flip* occurs just before the fromspace is condemned and copying starts.

            In a two-space collector, the *flip* occurs just before the
            fromspace is condemned and copying starts.

    floating garbage

        Floating garbage is :term:`garbage` that is not
        :term:`recycled` promptly due to some approximation
        or optimization in the :term:`garbage collector`.

        Floating garbage results from conservatively estimating an
        :term:`object` that is really :term:`unreachable` to be
        :term:`reachable` for the purposes of a particular
        :term:`collection cycle`. Using estimates can have
        considerable performance benefits but also result in higher
        :term:`memory (2)` consumption.

        Typical estimates that cause floating garbage are:

        1. Every register or :term:`activation frame` slot holds a
           reachable value: this is not always true, as objects stored
           in dead registers or slots may be otherwise unreachable.
           This estimate can simplify the compiler as well as the
           interface between the compiler and the garbage collector.

        2. Every object in a :term:`remembered set` is reachable: this
           is not always true, because remembered objects can have
           become unreachable since they were added to the remembered
           set. This estimate allows remembered sets to be effective;
           the alternative—determining whether each remembered object
           is reachable—is equivalent to a full garbage collection.

        3. Anything that looks like a :term:`reference` is one: this
           is not generally true, because random data can have the
           same bit pattern as a pointer. :term:`Conservative garbage
           collectors <conservative garbage collection>` use this
           estimate.

        4. Any object referenced from another is reachable: this is
           not generally true, because garbage can reference other
           garbage. :term:`Reference counting` collectors use this
           estimate, resulting in their not being able to reclaim
           self-referential structures.

        5. Any object reached during collection remains live until the
           next collection: this may not be true when the garbage
           collector runs interleaved with the mutator, as do
           :term:`incremental <incremental garbage collection>` and
           :term:`concurrent <parallel garbage collection>`
           collectors.

        A more subtle kind of floating garbage is an unreachable data
        structure that spans multiple regions that are never
        :term:`condemned <condemned set>` together.

    foreign code

        .. mps:specific::

            From the point of view of the :term:`client program`,
            *foreign code* is external code (not part of the client
            program, or the MPS), which is not aware of and does not
            co-operate with the MPS. The client program must take care
            when passing the address of a block in a :term:`moving
            <moving memory manager>` :term:`pool` to foreign code.

            The :ref:`pool-lo` :term:`pool class` is designed for this
            use case: blocks allocated from this pool do not move and
            are never protected, and so may be passed safely to
            foreign code.

    format

        A format describes the representation of an :term:`object`;
        that is, how the object is laid out in memory.

        A format usually specifies where the fields of the objects are
        located and what their type is.

        .. relevance::

            If formats are provided by a language or the application
            program, :term:`exact garbage collection` can be used,
            because the :term:`collector (1)` can determine which
            fields are :term:`references`.

        .. seealso:: :term:`conservative garbage collection`.

    format method

        .. mps:specific::

            One of the methods in an :term:`object format`, defined by
            the :term:`client program` in order to describe its
            objects to the MPS. May be a :term:`scan method`,
            :term:`skip method`, :term:`forward method`,
            :term:`is-forwarded method`, or :term:`padding method`.

    formatted object

        .. mps:specific::

            An allocated :term:`block` that belongs to an
            :term:`object format` and may be :term:`scanned <scan>` by
            the :term:`garbage collector`. See :ref:`topic-format`.

    forward method
    
        .. mps:specific::

            A :term:`format method` that is called by a :term:`moving
            <moving garbage collector>` :term:`pool <pool>` when it
            has moved an object. The forward method replaces the old
            object with a :term:`forwarding marker` that points to the
            new location of the object. See :c:type:`mps_fmt_fwd_t`.

    forwarding marker
    forwarding object
    forwarding pointer

        Some :term:`garbage collectors`
        :term:`move <moving garbage collector>` :term:`reachable`
        :term:`objects` into another space. They leave a
        forwarding pointer, a special :term:`reference` pointing to
        the new :term:`location <memory location>`, in the old
        location.

        .. similar:: :term:`broken heart`.

        .. seealso:: :term:`copying garbage collection`, :term:`two-space collector`.

        .. mps:specific::

            The term *forwarding object* is used. This is a
            :term:`formatted object` that has been replaced by a
            :term:`forwarding marker`. One of three types of formatted
            objects, the other two being :term:`client objects` and
            :term:`padding objects`.

    fragmentation

        Fragmentation is the inability to use :term:`memory (1)`
        because of the arrangement of memory already in use. It is
        usually divided into :term:`external fragmentation` and
        :term:`internal fragmentation`.

        .. bibref:: :ref:`Johnstone & Wilson (1998) <JW98>`.

    frame

        .. see:: :term:`in-band header`.

    free (1)

        .. aka:: *deallocate*.

        In :term:`manual memory management`, to free or deallocate an
        :term:`object` is to tell the :term:`memory manager` that it
        is no longer needed. The :term:`memory (1)` may then be
        :term:`recycled` by being used for subsequent
        :term:`allocation <allocate>`, or by being returned to the
        operating system.

        .. opposite:: :term:`allocate`.

        .. seealso:: :term:`free (2)`, :term:`destructor (1)`.

    free (2)

        In :term:`C`, the system function used for explicit
        :term:`deallocation <free (1)>` is called ``free``.

    free (3)

        :term:`Memory (2)` is *free* if it is not currently
        :term:`allocated`.

        .. historical::

            The term *available* was commonly used to mean "free".

        .. opposite:: :term:`allocated`.

        .. seealso:: :term:`free (1)`.

    free (4)

        .. see:: :term:`unmapped`.

    free block

        A single contiguous area of :term:`memory (2)` available to
        satisfy an :term:`allocation <allocate>` request.

        For the purpose of discussing :term:`allocation mechanisms`,
        two adjacent free blocks are not considered to be a single
        free block, until they are :term:`coalesced`. Free blocks may
        be :term:`split`.

        .. seealso:: :term:`allocation mechanism`, :term:`free list`.

        .. bibref:: :ref:`Wilson et al. (1995) <WIL95>`.

    free block chain

        Some systems store the :term:`free list` as a linked list, or
        chain.

        Usually the links are stored within the :term:`free (3)`
        :term:`blocks`. This means that all :term:`allocated` blocks
        must be large enough to store these, and implies a minimum
        size.

        Sometimes, the free block chain is ordered by :term:`address`.
        This makes :term:`coalescence <coalesce>` considerably
        cheaper, but :term:`deallocation <free (1)>` more expensive.

        .. seealso:: :term:`free list`.

    free list

        The free list is the set of :term:`free blocks`.

        Originally this term meant the single linked list of all free
        blocks, but as :term:`allocation mechanisms` have become more
        varied, it has become more generic, and now may be implemented
        as a tree or other data structure rather than a linked list.
        If the implementation actually is a linked list of free
        blocks, this is called a :term:`free block chain` to
        distinguish it from the abstract term.

        There may be several free lists, classed by size or other
        characteristic. For instance, :term:`segregated free list`
        systems classify free lists by block size.

        .. seealso:: :term:`free block`, :term:`free block chain`.

    free store

        .. see:: :term:`heap`.

    freestore

        .. see:: :term:`heap`.

    from space
    fromspace

        .. aka:: *old space*, *oldspace*.

        In :term:`copying garbage collection`, the space containing a
        mixture of :term:`live` and :term:`dead` objects, out of which
        the former are copied.

        .. opposite:: :term:`tospace`.

    function pointer

        In the :term:`C` programming language, a :term:`pointer` to an
        function, as distinct from a :term:`object pointer`. The C
        programming language does not guarantee that function and
        object pointers are the same size, or that a pointer of one
        type can be cast to a pointer of the the other type without
        losing information (but on every mainstream C implementation,
        including all those supported by the MPS, they are in fact the
        same).

        .. opposite:: :term:`object pointer`.

    function record

        .. see:: :term:`activation record`.