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
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
.. _glossary-r:

=============================
Memory Management Glossary: R
=============================

.. include:: alphabet.txt

.. glossary::

    RAM

        .. aka:: *random access memory*.

        RAM (random access memory) is a type of :term:`physical memory
        (2)` that can be read from and written to.

        .. similar:: :term:`main memory`.

        .. seealso:: :term:`ROM`, :term:`static RAM`, :term:`dynamic RAM`.

    random access memory

        .. see:: :term:`RAM`.

    ramp allocation

        .. mps:specific::

            An :term:`allocation pattern` indicating to the MPS that
            most of the blocks allocated after the call to
            :c:func:`mps_ap_alloc_pattern_begin` are likely to be
            :term:`dead` by the time of the corresponding call to
            :c:func:`mps_ap_alloc_pattern_end`. See
            :ref:`topic-pattern-ramp`.

    rank

        .. mps:specific::

            A value of :c:type:`mps_rank_t` indicating whether a
            :term:`root` is :term:`ambiguous <ambiguous root>`
            (:c:func:`mps_rank_ambig`), :term:`exact <exact root>`
            (:c:func:`mps_rank_exact`) or :term:`weak <weak root>`
            (:c:func:`mps_rank_weak`).

    rash

        .. mps:specific::

            A :term:`variety` in which no MPS functions :term:`assert
            <assertion>` that their data structures are valid. Select
            it by defining :c:macro:`CONFIG_VAR_RASH`. Compare
            :term:`cool` and :term:`hot`.

    raw

        .. see:: :term:`unwrapped`.

    reachable

        An :term:`object` is *reachable* if it is :term:`referred
        <reference>` to by a :term:`root`, or is referred to by a
        reachable object; that is, if it can be reached from the roots
        by following :term:`references`.

        Reachability is used as an approximation to :term:`liveness
        <live>` in :term:`tracing garbage collection`.

        In :term:`Java`, the :term:`reference objects` together with
        ordinary references and :term:`finalization` generate a
        hierarchy of reachability that guides the :term:`collector
        (1)` on what to do when an object is about to :term:`die
        <dead>`. There are six strengths:

        1. :term:`strongly reachable`;
        2. :term:`softly reachable`;
        3. :term:`weakly reachable`;
        4. :term:`finalizable <finalization>`;
        5. :term:`phantom reachable`;
        6. :term:`unreachable`.

        Basically, an object is only as reachable as the weakest link
        in the strongest path from the roots. Note that the Java
        specification's description of the reachabilities is a bit
        patchy, but that's what it intends. It is unspecified where
        Java Native Interface's *weak global references* fit into
        this.

        .. similar:: :term:`live`.

        .. opposite:: :term:`unreachable`.

        .. link::

            `Package java.lang.ref <http://download.java.net/jdk8/docs/api/java/lang/ref/package-summary.html>`_, `Reference Objects and Garbage Collection <http://pawlan.com/monica/articles/refobjs/>`_.

    read barrier

        A read :term:`barrier (1)` is a block on reading from certain
        :term:`memory (2)` :term:`locations <memory location>` by
        certain threads or processes.

        .. relevance::

            Read barriers are used for :term:`incremental <incremental
            garbage collection>` or :term:`concurrent <parallel
            garbage collection>` :term:`garbage collection`.

        .. seealso:: :term:`write barrier`.

    read fault

        An exception which occurs when reading from an address in
        :term:`virtual memory`.

        This is probably either a :term:`page fault`, an
        :term:`invalid page fault` or a :term:`protection fault`.

        .. similar:: :term:`segmentation violation`.

        .. seealso:: :term:`write fault`.

    read-only memory

        .. see:: :term:`ROM`.

    real memory (1)

        A system with no :term:`virtual memory` capability can be
        said to have *real memory*.

        .. historical::

            On older architectures, programs could only directly
            access data in real memory. Where this was inefficient,
            they had to store data on disk, and sometimes had
            alternate portions of program image called *overlays*.

        .. opposite:: :term:`virtual memory`.

    real memory (2)

        .. see:: :term:`physical memory (1)`.

    reclaim

        *Reclaiming* an :term:`object` or the :term:`memory (1)`
        occupied by it is making it available for reuse after the
        object is no longer needed.

        This word is usually used only in connection with
        :term:`automatic memory management`.

        .. similar:: :term:`recycle`.

    recycle

        *Recycling* :term:`memory (1)` means making it available for
        reuse after it has been occupied by an :term:`object` that is
        no longer needed.

        In simple cases, this might simply involve adding a
        :term:`memory (2)` :term:`block` to the :term:`free list`.
        Another possibility is :term:`unmapping <unmapped>` memory so
        that the :term:`backing store` can be allocated to another
        process.

        .. similar:: :term:`reclaim`.

    reference

        In memory management, *a reference* is the general term for a
        link from one :term:`object` to another. Some programming
        languages have more specific meanings for the term.

        The terms ":term:`pointer`" and "reference" are often
        interchangeable, but some programming languages differentiate
        the two in subtle ways.

        .. similar:: :term:`address`, :term:`pointer`.

        .. mps:specific::

            A reference is represented in the :term:`C` interface by a
            value of type :c:type:`mps_addr_t` (an alias for ``void
            *``) which points to a :term:`memory location` within the
            object (typically the base of the object, but for objects
            with :term:`headers <in-band header>` this may not be the
            case). The pointer returned by :c:func:`mps_alloc` and
            :c:func:`mps_reserve` is a reference to the object
            allocated.

            The :term:`client program` is free to represent references
            as it chooses (for example, with :term:`tags <tagged
            reference>`), provided that during :term:`scanning <scan>`
            it is able to decode a reference from its representation
            into the MPS interface representation and encode a
            reference from the MPS into its representation.

    reference counting

        Reference counting systems perform :term:`automatic memory
        management` by keeping a count in each :term:`object`, usually
        in a :term:`header <in-band header>`, of how many
        :term:`references` there are to the object.
        Objects to which there are no references cannot be accessed by
        the :term:`mutator`; they are therefore :term:`dead` and may
        be :term:`reclaimed <reclaim>`.

        The reference count is incremented for each new reference, and
        is decremented if a reference is overwritten, or if the
        referring object is recycled. If a reference count falls to
        zero, then the object is no longer required and can be
        recycled.

        There are four main problems with simple reference counting:

        1. The reference count field usually has to have limited size,
           and the system therefore breaks down if the number of
           possible references to an object is unbounded;

        2. Reference counting involves an operation on every
           modification of a pointer, which increases code size,
           increases demand for :term:`memory bandwidth`, decreases
           :term:`locality of reference` and can be a serious
           performance penalty (especially in multi-threaded
           environments where reference count updates require
           synchronization);

        3. Every object needs to be slightly larger in order to store
           the reference count;

        4. If any objects are part of a :term:`cyclic data structure`
           then they will always have a non-zero reference count, and
           hence won't be reclaimed when they are dead.

        .. figure:: ../diagrams/refloop.svg
            :align: center
            :alt: Diagram: Garbage with non-zero reference counts.

            Garbage with non-zero reference counts.

        Reference counting has the advantage that it can reclaim
        objects promptly, and for this reason it is often used to
        reclaim non-cyclic data structures in file systems, databases
        and operating system kernels. When there is a possibility of
        cyclic data structures, reference counting is sometimes used
        together with a :term:`tracing garbage collector <tracing
        garbage collection>` that runs infrequently. Such combinations
        are generally less efficient than using a tracing collector by
        itself, but the promptness of reference counting may be
        important.

        Pauses due to reference counting are typically fairly short,
        and it may be appropriate as a form of :term:`incremental
        garbage collection`. But removing a single reference may cause
        the recycling of a large number of objects at once, so it is
        not suited to real-time systems where minimum pause times must
        be guaranteed. There are more complex variations of the
        technique that address this problem.

        Reference counting is often used because it can be implemented
        without any support from the language or compiler. In
        :term:`C++` this can be encapsulated in a class, using a
        :term:`smart pointer`. However, it would normally be more
        efficient to use a tracing garbage collector instead. The
        performance of reference counting can be improved
        substantially with compiler support, using refinements such as
        :term:`deferred reference counting`, which has been
        successfully used in :term:`Smalltalk` and other languages.

        Despite the problems, reference counting is often used for
        :term:`distributed garbage collection`. This is because
        refinements such as :term:`weighted reference counting`
        require less inter-process communication than :term:`tracing
        <trace>`.

        .. seealso:: :term:`limited-field reference count`, :term:`one-bit reference count`.

    reference object

        In :term:`Java`, a *reference object*
        (``java.lang.ref.Reference``) encapsulates a :term:`reference`
        to some other object, in order to make the :term:`garbage
        collector` handle it specially. In particular, a Java program
        can use this to detect when the referent becomes
        :term:`unreachable`.

        Basically, the encapsulated reference is a :term:`weak
        reference (1)`; it will be cleared by the :term:`collector
        (1)` when all other references to the referent have
        disappeared. However, in order to better control what happens
        at the end of an object's :term:`lifetime`, Java 1.2 provides
        three classes of reference objects, each with its own
        peculiarities: ``SoftReference``, ``WeakReference``, and
        ``PhantomReference``. Each of these classes has its uses in
        managing memory. The reference objects together with ordinary
        references and :term:`finalization` generate a hierarchy of
        :term:`reachability <reachable>` that guides the collector on
        what to do when an object is about to :term:`die <dead>`.

        A reference object can be *registered* with a queue, and it
        will be enqueued when the collector determines that the
        referent is :term:`softly <softly reachable>`, :term:`weakly
        <weakly reachable>` or :term:`phantom reachable`, as the case
        may be. A program can use these queues to perform some action
        when an object is dying. This allows finer control than the
        older :term:`finalization` mechanism alone.

        .. historical::

            This feature was introduced in Java 1.2 (confusingly, part
            of the Java 2 Platform).

        .. seealso:: :term:`soft reference`, :term:`weak reference (2)`, :term:`phantom reference`.

        .. link::

            `Package java.lang.ref <http://download.java.net/jdk8/docs/api/java/lang/ref/package-summary.html>`_, `Reference Objects and Garbage Collection <http://pawlan.com/monica/articles/refobjs/>`_.

        .. bibref:: :ref:`Dybvig et al. (1993) <DBE93>`.

    region inference

        Region inference is a technique for determining when
        :term:`objects` become :term:`dead` (even if they are
        :term:`reachable`) by a static analysis of the program.

        Region inference infers a *region* for each object. When a
        region dies, all the objects in it are known to be
        :term:`dead`, whether reachable or not. Regions obey a strict
        :term:`stack` discipline; that is, when a region dies, all
        younger regions also die. In this way, region inference
        occupies a middle ground between :term:`stack allocation` and
        :term:`heap allocation`.

        .. bibref:: :ref:`Tofte & Talpin (1997) <TT97>`.

    register

	A *register* is a small unit of :term:`memory (2)` that is
	attached to a processor and accessible very quickly. Registers
	typically form the highest level of a computer's
	:term:`storage hierarchy`.

        .. relevance::

            In some programs (for example, those compiled by typical
            :term:`C` or :term:`C++` compilers), a subset of the
            registers is always accessible by the :term:`mutator` and
            so forms a :term:`root`.

        .. mps:specific::

            The :term:`scan method` for the root containing the
            registers is hard to write (it depends on the operating
            system, the processor architecture, and in some cases the
            compiler), so the MPS provides (on its supported
            platforms) the function :c:func:`mps_stack_scan_ambig`.

    register set partitioning

        Run-time systems for :term:`garbage-collected <garbage
        collection>` languages sometimes partition the set of machine
        :term:`registers` *a priori* into two categories:
        those always :term:`traced <trace>` and updated by the
        :term:`garbage collector` and those ignored by it.

        The former are always maintained in a format understood by the
        collector; the latter are never used to hold
        :term:`references` to collectable :term:`objects`. More
        complicated schemes are also possible.

        This partitioning provides a separation of concerns between
        the compiler and the :term:`garbage collector`. The compiler
        can generate code that produces values the garbage collector
        would not be able to handle (say, because they have no
        :term:`tags`), as long as those values are kept in the
        ignored registers. The garbage collector can trust that the
        registers it looks at always contain valid data, and can
        perform :term:`exact garbage collection`.

        Register set partitioning increases the demand for registers
        (*register pressure*), but may reduce the amount of
        :term:`boxing <boxed>` needed.

    relocation

        *Relocating* means moving data from one location to another
        and updating all :term:`references`.

        Relocation is often performed to avoid :term:`external fragmentation`.

        Program loading sometimes relocates code and :term:`static
        <static allocation>` data.

        .. similar:: :term:`moving <moving garbage collector>`.

        .. seealso:: :term:`compaction`, :term:`moving memory manager`.

    remembered set

        A remembered set is the technique of keeping a separate list
        of interesting :term:`references` between two sets
        of :term:`objects`, so you don't have to find them by
        :term:`scanning <scan>`.

        Many :term:`memory management` algorithms depend on
        partitioning the objects and require special handling for
        references between partitions. Keeping track of such
        references in a remembered set eliminates the need to scan the
        originating partition to find them.

        A typical use in :term:`generational garbage collection` is
        remembering :term:`references` from an older
        :term:`generation` to a younger one.

        .. similar:: :term:`entry table (2)`.

        .. bibref:: :ref:`Ungar (1984) <UNGAR84>`, :ref:`Jones et al. (2012) <JONES12>`.

    remote reference

        .. mps:specific::

            A :term:`reference` that logically belongs to a
            :term:`formatted object` and so must be :term:`fixed` when
            the object is :term:`scanned <scan>`, but which is not
            stored within the block containing the object. (For
            example, in an auxiliary table of some sort.)

            The MPS does not generally support remote references
            because those references may be :term:`protected
            <protection>` and so if :term:`scan method` attempts to
            :term:`fix` them this will hit a :term:`barrier (1)` and
            cause a re-entrant call to the MPS.

    replicating garbage collector

        A variant of :term:`copying garbage collection`, which does
        not destroy the original :term:`object` when making a copy.

        This is useful in an :term:`incremental <incremental garbage
        collection>` or :term:`concurrent <parallel garbage
        collection>` :term:`collector (1)`, as no :term:`read barrier`
        is required; the :term:`mutator` can continue to use old
        objects. The collector uses a :term:`write barrier` to
        replicate the writes to the new copies.

        .. seealso:: :term:`copying garbage collection`, :term:`broken heart`.

        .. bibref:: :ref:`Nettles et al. (1992) <NOPH92>`, :ref:`Nettles & O'Toole (1993) <NO93>`, :ref:`Nettles & O'Toole (1993a) <NO93A>`, :ref:`O'Toole & Nettles (1994) <ON94>`.

    reserved

        In a :term:`virtual memory` system, it is usually possible
        to hold range of :term:`virtual addresses`
        *reserved* without making it :term:`mapped`.

        Reserving addresses prevents other components of the program
        using the same addresses, without consuming :term:`swap
        space`. This technique is often used in :term:`BIBOP` schemes,
        where one might want to reserve a large amount of
        :term:`address space` but only sparsely map it.

        On some systems there are special calls for reserving; on
        others one can create :term:`mappings` that don't
        need :term:`backing store`. For example, on some Unix systems,
        ``mmap /dev/zero`` with no access.

        .. seealso:: :term:`mapping`, :term:`mmap`.

    resident

        In a :term:`cache (2)` system, that part of the cached storage
        which currently has a copy in the cache is called *resident*.
        Ideally, the :term:`working set` should be resident.

        .. seealso:: :term:`cache (2)`, :term:`storage hierarchy`, :term:`resident set`.

    resident set

        In a :term:`virtual memory` system, a process' resident
        set is that part of a process' :term:`address space` which is
        currently in :term:`main memory`. If this does not include all
        of the process' :term:`working set`, the system may
        :term:`thrash`.

    result code

        .. mps:specific::

            A value returned from an MPS function, represented by the
            type :c:type:`mps_res_t`. The result code
            :c:macro:`MPS_RES_OK` indicates success; other values
            indicate errors. See :ref:`topic-error`.

    resurrection

        An object is said to have been *resurrected* if it was
        determined to be :term:`finalizable <finalization>` by the
        :term:`garbage collector` (that is, the only thing keeping it
        alive was the fact that it required finalization), but then a
        new :term:`strong reference` was created to it.

        This can happen via a :term:`weak reference (1)` or by the
        finalization procedure storing a permanent copy of its
        reference to the object.

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

    ROM

        .. aka:: *read-only memory*.

        ROM (read-only memory) is a type of :term:`physical memory
        (2)` that can be read from, but not written to. The contents
        of ROM are usually set in the factory.

        .. seealso:: :term:`RAM`.

    root

        In :term:`tracing garbage collection`, a root holds a
        :term:`reference` or set of references to :term:`objects` that
        are *a priori* :term:`reachable`. The :term:`root set` is used
        as the starting point in determining all reachable data.

        Roots basically comprise the references in the state of the
        :term:`mutator`. Typical roots are global variables, other
        :term:`static <static allocation>` data, and the
        :term:`control stack`.

        .. seealso:: :term:`weak root`, :term:`strong root`, :term:`ambiguous root`, :term:`exact root`.

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

    root description

        .. mps:specific::

            The :term:`arena` uses root descriptions to find
            :term:`references` within the :term:`client
            program's <client program>` :term:`roots`. Root
            descriptions belong to the type :c:type:`mps_root_t`.

    root mode

        .. mps:specific::

            A value of type :c:type:`mps_rm_t` describing whether a
            :term:`root` is :term:`constant <constant root>`,
            :term:`protectable <protectable root>`, or both. The root
            mode tells the MPS whether it may place a :term:`barrier
            (1)` on the root.

    root set

        The *root set* is the collection of :term:`roots` that
        the :term:`mutator` declares to the :term:`collector (2)`.

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