.. _glossary-t: ============================= Memory Management Glossary: T ============================= .. include:: alphabet.txt .. glossary:: tabling .. see:: :term:`caching (3)`. tag A tag is a piece of information associated with an :term:`object` or :term:`reference` that allows the representation of the object to be determined. Tags are often used to represent types in the implementation of a dynamically-typed language. In statically-typed languages, types are usually implicit and not permitted to change at run-time, so tagging is rarely required. One of the simplest forms of tag is a :term:`word` at the beginning of the object that points to a block of information about the object's :term:`format`. .. figure:: ../diagrams/tag-word.svg :align: center :alt: Diagram: Example of a tag-word at the start of an object. Example of a tag-word at the start of an object. Another common form of tagging is to :term:`align ` objects and keep information in the least significant bits of the reference. .. figure:: ../diagrams/tag-ref.svg :align: center :alt: Diagram: Example of reference tagging, using the least significant bits. Example of reference tagging, with objects aligned to addresses that are multiples of four, and the tag stored in the least significant two bits of the reference. In :term:`C`, when a structure contains a union, it is common to add a field to the structure to indicate which union member is currently being used. This field is known as a *discriminator*, and is a form of tag. Analogues occur in other languages, sometimes with compiler or run-time support. .. seealso:: :term:`tagged architecture`, :term:`in-band header`. .. bibref:: :ref:`Gudeman (1993) `. .. mps:specific:: See :ref:`topic-scanning-tag`. tagged architecture A tagged architecture is a hardware architecture where each memory :term:`word` is divided into a "data" and a :term:`tag` section. The data section is sufficiently large to contain a memory :term:`address` and the tag section is used to describe how the data section is to be interpreted (that is, it encodes the type of the data). .. relevance:: Tagged architectures greatly simplify the implementation of a memory manager because each word of memory is self-describing. .. historical:: The :term:`Lisp Machine` was an example of a tagged architecture. tagged reference A :term:`reference` containing a :term:`tag` in part of its address, for example by :term:`aligning ` objects and keeping the tag in the least significant bits of the address. .. mps:specific:: See :ref:`topic-scanning-tag`. TB (1) .. see:: :term:`terabyte`. TB (2) .. see:: :term:`translation lookaside buffer`. telemetry filter .. mps:specific:: A :term:`bitmap` indicating which events the MPS should include in the :term:`telemetry stream`. It can be read or changed by calling :c:func:`mps_telemetry_control`. telemetry label .. mps:specific:: An indentifier representing a string, returned from :c:func:`mps_telemetry_intern`, that can be associated with certain :term:`addresses`, and so appear in the :term:`telemetry stream` attached to events concerning those addresses. See :ref:`topic-telemetry`. telemetry stream .. mps:specific:: A sequence of events reported by the MPS to assist with debugging and profiling. The events that appear in the stream can be configured by setting the :term:`telemetry filter`. See :ref:`topic-telemetry`. tenuring .. see:: :term:`promotion`. terabyte .. aka:: *TB*. A terabyte is 1024 :term:`gigabytes`, or 1099511627776 :term:`bytes (1)`. See :term:`byte (1)` for general information on this and related quantities. termination .. see:: :term:`finalization`. thrash A :term:`cache (2)` is said to :term:`thrash` when its :term:`miss rate` is too high, and it spends most of its time servicing :term:`misses`. Thrashing is bad for performance, particularly :term:`virtual memory` thrashing, because the relative cost of a miss is so high: it may slow a machine down by a factor of a hundred or more. Thrashing is typically caused by a process or system having a :term:`working set` which is larger than its :term:`cache (1)` or :term:`main memory`. It may also be caused by a failure of :term:`cache policy`. A system with an inflexible cache policy may thrash even when the working set is quite small. For instance, a virtual memory system which has four megabytes of :term:`physical memory (1)` but which has a working set of ten megabytes will :term:`thrash` badly. .. bibref:: :ref:`Denning (1968) `, :ref:`Denning (1970) `, :ref:`Denning & Schwartz (1972) `. thread A thread of execution is a sequence of instructions that take place sequentially. In a multi-threaded program, multiple threads of execution operate in parallel, and are generally asynchronous with respect to each other. .. relevance:: Access to shared resources such as memory management interface must be thread-safe. Each thread has its own :term:`control stack` which may contain :term:`references` to blocks on the heap. .. mps:specific:: Threads are represented by values of type :c:type:`mps_thr_t`, created by calling :c:func:`mps_thread_reg`. In order for the MPS to find references on the control of the thread, the thread must be also be registered as a root by calling :c:func:`mps_root_create_reg`. See :ref:`topic-thread`. threatened set .. see:: :term:`condemned set`. TLB .. see:: :term:`translation lookaside buffer`. to space tospace .. aka:: *new space*, *newspace*. In :term:`copying garbage collection`, the space to which :term:`live` object are copied. .. opposite:: :term:`fromspace`. trace In :term:`tracing garbage collection`, tracing is the process of following the :term:`graph` from all :term:`roots` to all :term:`reachable` data. .. similar:: :term:`scan`. tracing garbage collection Tracing garbage collection is :term:`garbage collection` based on :term:`reachability `. Tracing garbage collection relies on the fact that if an :term:`object` is not :term:`reachable`, there is no way the :term:`mutator` could ever access it, and therefore it cannot be :term:`live`. In each :term:`collection cycle`, some or all of the objects are :term:`condemned ` and the :term:`graph` is :term:`traced` to find which of the condemned objects are reachable. Those that were not reachable may be :term:`reclaimed`. translation buffer translation lookaside buffer .. aka:: , *address translation cache*, *ATC*, *TB*. The *translation lookaside buffer* or *address translation cache* is small piece of associative :term:`memory (1)` within a processor which caches part of the translation from :term:`virtual addresses` to :term:`physical addresses`. In a :term:`virtual memory` system there is a translation from :term:`virtual addresses` to :term:`physical addresses`. This translation can often be very large and complex and the data structures that implement the translation (often a :term:`page table`) can be too large to store efficiently on the processor. Instead, a few elements of the translation are stored in the TLB; the processor can access the TLB extremely quickly. If a required translation for a particular virtual address is not present in the TLB then *a TLB miss* is taken and the address is resolved using the more general mechanism. transparent alias transparent type .. mps:specific:: In the MPS interface, a *transparent type* is an alias defined using ``typedef``, and this is documented so that the :term:`client program` can rely on that fact. For example, :c:type:`mps_addr_t` is a transparent alias for ``void *``. See :ref:`topic-interface`. .. opposite:: :term:`derived type`, :term:`opaque type`. transport In a :term:`copying collector `, transporting is preventing an :term:`object` in the :term:`condemned set` from being collected by copying it and adjusting the :term:`reference` by which it was discovered to point to the new copy. .. seealso:: :term:`scavenging `, :term:`snap-out`. transport snap-out .. see:: :term:`snap-out`. treadmill Henry Baker devised an :term:`incremental ` non-:term:`moving ` :term:`garbage collector` that uses a circular doubly-linked list, called the *treadmill*, to implement :term:`tri-color marking`. Every :term:`object` is on the list. The list has four sections corresponding to :term:`colors`. The :term:`black`, :term:`gray` and :term:`white` sections are used for tri-color marking, and an additional :term:`off-white` section is used for :term:`free (3)` objects. The color of an object is changed by unlinking it from the list and relinking it to a different part of the list. .. figure:: ../diagrams/treadmill.svg :align: center :alt: Diagram: A treadmill. A treadmill. (Based on :ref:`Jones (2012) `.) .. bibref:: :ref:`Baker (1992c) `. tri-color invariant tri-colour invariant tricolor invariant tricolour invariant The term "tri-color invariant" is used to refer to any of a number of properties of a :term:`reference` :term:`graph` that are preserved throughout a :term:`tri-color marking` algorithm to ensure the correctness. There are two important ones: the :term:`strong tri-color invariant` and the :term:`weak tri-color invariant`. When people say "the tri-color invariant" they probably mean the strong one. .. bibref:: :ref:`Johnstone (1997) `, :ref:`Pirinen (1998) `. tri-color marking tri-colour marking tricolor marking tricolour marking Tri-color marking is a :term:`tracing garbage collection` algorithm that assigns a :term:`color` (:term:`black`, :term:`white`, or :term:`gray`) to each :term:`node` in the :term:`graph`. It is basic to :term:`incremental garbage collection`. Initially all nodes are colored white. The distinguished :term:`root set` is colored gray. The :term:`collector (2)` proceeds to discover the :term:`reachable` nodes by finding an :term:`edge` from a gray node to a white node and coloring the white node gray. Hence each tracing step involves choosing a gray node and graying its white children. When all the edges from a gray node lead only to other gray (or black) nodes, the node is colored black. When no gray nodes remain, the reachable part of the graph has been discovered and any nodes that are still white may be :term:`recycled`. The :term:`mutator` is free to access any part of the graph and allocate new nodes while the :term:`collector (2)` is determining the reachable nodes, provided the :term:`tri-color invariant` is maintained, by changing the colors of the nodes affected, if necessary. .. historical:: "Tri-color marking" is the term used to describe an algorithm developed in 1975 by E. W. Dijkstra and others, as an exercise in proving cooperating programs correct. They chose as their problem a :term:`parallel garbage collector `, with the intent of illustrating cooperating sequential processes with a large shared data space but minimal exclusion and synchronization constraints. Although the algorithm developed in the paper is not necessarily the most efficient algorithm for a :term:`collector (1)`, it has been generally accepted to be correct: an important feature that not all garbage collectors can claim. A number of other garbage collection algorithms have been shown to be isomorphic to the tri-color marking algorithm and thus are also believed to be correct. .. seealso:: :term:`barrier (1)`. .. bibref:: :ref:`Dijkstra et al. (1976) `. two-space collector two space collector .. aka:: *semi-space collector*. A two-space :term:`collector (1)` is a simple form of a :term:`copying garbage collector `. The available :term:`memory (2)` is divided into two halves, called :term:`semi-spaces`. :term:`Objects` are allocated in one semi-space until it is full. The :term:`reachable` objects are then copied into the other semi-space (usually using a :term:`Cheney scan`) and the old semi-space is :term:`reclaimed`. :term:`Allocation ` continues in the new semi-space until it is full, at which point the process is repeated in reverse. The main disadvantage of a two-space collector is that it only makes use of half of the available memory. This can be tolerable in a :term:`virtual memory` system if the :term:`garbage collector` is written carefully to preserve :term:`locality of reference`. Other forms of copying garbage collector, such as :term:`generational garbage collectors `, have much lower overheads. .. figure:: ../diagrams/two-space.svg :align: center :alt: Diagram: Two-space collector. Two-space collector. .. seealso:: :term:`flip`. type-accurate garbage collection .. see:: :term:`exact garbage collection`. type punning Interpreting a value of one type as if it were a value of another (for example, via a type cast in :term:`C`), especially if such interpretation is not defined by the language standard. For example, interpreting a value of type ``T**`` (pointer to pointer to ``T``) as ``U**`` is undefined. .. mps:specific:: See :ref:`topic-interface`.