<p>I know some garbage collectors (conservative GC) treat every word in the stack as a potential pointer to a live object in the heap (provided that the word actually points to somewhere inside an allocated object).</p>
<p>If I understand correctly, precise garbage collectors know to only look at values in the stack that are actually pointers. It seems like this might be easy enough for stack slots that are used to store local variables because something could record the type of each local variable and which stack slot it is stored in (for each function). The harder part is the evaluation stack, where a given stack location could be either a pointer or some other kind of value depending on what part of an expression has been evaluated thus far.</p>
<p>How do precise GCs know where pointers are in the stack?</p>

<garbage-collection>
How do precise garbage collectors find roots in the stack?
<h3>Box all the things</h3>
<p>One way is to make the problem trivial: ensure that the stack only ever contains pointers. You can do that by making all data in your runtime <em>boxed</em>: all values are represented by a pointer to a block of data that starts with a header describing the content of the block (often with a few spare bits for the GC). This description includes the length of the block as well as a way to know, for each word in the block, whether it's a pointer or not.</p>
<p>For example, a boolean would be represented by a pointer to a block of two words: one header word that encodes the information “there is 1 data word, which is not a pointer”, and one data word that contains 0 or 1. This is expensive if you have mutable values, but relatively cheap if you don't have mutable values (you can still have mutable <em>variables</em>): you can have a single copy of False and a single copy of True in your system, and all boolean variables point to either one or the other.</p>
<p>As far as I know this is a common approach in Lisp implementations.</p>
<h3>Separate the pointers from the chaff</h3>
<p>You can have separate memory areas (including separate stacks) for pointers and non-pointers. Then the GC knows whether an memory location contains a pointer by looking at the address of that location, without needing to look at the content.</p>
<p>A limitation of this approach is that a function has to know whether it's getting a boxed value or an unboxed value. This reduces the opportunities for polymorphism: you can't have a generic list or dictionary implementation that indifferently supports all element types.</p>
<p>GHC mostly follows this approach. Normal values are boxed, but it has <a href="https://downloads.haskell.org/%7Eghc/6.12.1/docs/html/users_guide/primitives.html" rel="noreferrer">limited support for unboxed types</a>. The limitations on polymorphism are due to the need to separate boxed and unboxed values in memory.</p>
<h3>Pointers are not odd</h3>
<p>On almost all computer architectures in use today, pointers store byte addresses, and most elementary data (word-sized integers, floating point values, pointers) uses 2, 4 or 8 bytes and has to be aligned on its size. (Many popular architectures tolerate non-aligned data but at a performance cost so there's little incentive to take advantage of that except to run some legacy code.) Thus any pointer to data that's larger than a byte will be a multiple of 2 (often even a multiple of 4 or even 8).</p>
<p>This allows an implementation trick: if you need to store up to 15 bits of data (up to 31 bits on a 32-bit processor, up to 63 bits on a 64-bit processor), use an odd number as the representation. If you need to store more than that, allocate memory for the data and store a pointer to it: the pointer will be an even number. Thus, small values are unboxed, and large values are boxed.</p>
<p>This approach requires a bit of extra work in integer arithmetic: if $x$ and $y$ are small values with unboxed representations <code>x</code> and <code>y</code>, then $x+y$ is represented by <code>x+y-1</code>, not by <code>x+y</code>. But the extra cost of an addition is small compared to the extra cost of a memory access, so this is typically a performance win compared to systematically boxing integers.</p>
<p>Floating point values typically require a whole machine word or two, so they have to remain boxed. Efficient numerical code often requires having special-purpose data structures such as arrays that directly contain floats, rather than polymorphic arrays that contain pointers to floats.</p>
<p>Note in particular that the size of an object in memory fits in an unboxed value as long as the object does not occupy more than half of the total address space.</p>
<p>This is a common approach in ML dialects (including Ocaml).</p>

CC BY-SA 4.0
2023-06-27T21:12:46.527Z
2023-06-27T21:26:31.063Z
2023-06-27T21:26:31.063Z
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-06-27T21:45:19.540Z
Can’t pointers to single bytes be odd? I know that `malloc` will never return one, but if nothing else a pointer to the second character in a C string will likely be odd.
Bbrk24
CC BY-SA 4.0
2023-06-27T22:17:26.360Z
The first approach is also taken by the JVM, though it looks like value classes will be added soonish
Seggan
CC BY-SA 4.0
2023-06-27T22:22:01.147Z
@Bbrk24 What you're asking about is commonly referred to as a "derived pointer". The language mentioned, OCaml, has no language feature (except Obj.magic and calling into C) that could produce such a pointer that would ever be traversed by the GC. These kinds of pointers are a concern and languages like Java, OCaml, etc. will typically try to make it impossible for any language feature to be able to produce one. It's not a major issue though, you can imagine that such derived pointers as a language feature could be lowered as a base + offset pair (like a "view" of a string).
Colin James
CC BY-SA 4.0
2023-06-28T15:23:19.350Z
Most non-toy Lisp implementations also use the "pointers are not odd" approach for storing fixnums.
Barmar
<p><a href="https://www.haskell.org/ghc/" rel="noreferrer">GHC</a> uses a strategy for this that I think is fairly cute: every stack frame is essentially laid out in precisely the same way as a heap object.</p>
<p>Within the GHC runtime system (RTS), every heap object begins with a pointer to a statically-allocated <em>infotable</em>. This pointer is then followed by a <em>payload</em>, which contains the data stored in the heap. This is illustrated by the following diagram <a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/storage/heap-objects" rel="noreferrer">from the GHC wiki</a>:</p>
<p><a href="https://i.sstatic.net/NsNYg.png" rel="noreferrer"><img src="https://i.sstatic.net/NsNYg.png" alt="heap object layout" /></a></p>
<p>Infotables contain, among other things, bitmaps that describe the layout of the heap object. For example, the Haskell datatype declaration</p>
<pre><code>data T = D String Bool Int#
</code></pre>
<p>defines a structure that contains two pointers (a string and a boolean) and one non-pointer (an unboxed integer). Therefore, the compiler will generate an infotable that says “heap objects of this type have two pointers followed by one nonpointer”.</p>
<p>For function closures, the infotable also includes a pointer to the compiled code, and the payload just contains the closed-over values. A bitmap is used to keep track of which of the closed-over values are pointers (to GC-managed memory) and which are not. On most platforms, an additional optimization is used: the code is placed directly adjacent to the infotable, so only one pointer dereference is needed to access both the infotable and the code.</p>
<p>This finally brings us to stack layout. It turns out that a stack frame is actually an awful lot like a function closure! It contains a pointer to some code to run when the stack frame is returned to (the return address) and a payload containing some stack-allocated values. Therefore, <a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/storage/stack" rel="noreferrer">GHC essentially represents stack frames as a stack-allocated heap object</a>: an infotable followed by a payload.</p>
<p>These infotables allow the garbage collector to walk the stack in just the same way that it walks pointers within heap objects. In GHC, the stack grows towards lower addresses, so it just starts at the top of the stack and traverses each stack frame until it reaches the bottom. This eliminates the need for individual values to be tagged in any way (though in practice GHC <a href="https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/pointer-tagging" rel="noreferrer">does use a pointer tagging scheme</a> for some other things).</p>

CC BY-SA 4.0
2023-06-28T04:03:35.777Z
2023-06-28T04:03:35.777Z
Alexis King
<p>This is not a full answer, but a few notes on cooperative garbage collection. Implementing it can get subtle, and there are some points that you should know about if you're planning to go down this route.</p>
<h2>The current stack frame</h2>
<p>If the generated code cooperates with the GC, then for the current stack frame, it can explicitly inform the GC of where the roots are. This doesn't work for the stack frames of callers, of course, but it may be useful to think about, because sequence points are more common than calls.</p>
<h2>Callee-save registers</h2>
<p>When using cooperative GC, compilers can't use callee-save registers to store heap references unless the compiler can prove that they are safe (i.e. it knows they are referenced, possibly indirectly, from some other root). Callees don't, by definition, know or care what callee-save registers contain.</p>
<p>Note that this is very similar to stack unwinding in a non-GC language. In C++, for example, destructible objects can't be stored in registers across calls.</p>
<h2>The operating system interface</h2>
<p>Modern operating systems occasionally hijack a user thread to run code. Some examples are signal handlers in Unix, asynchronous procedure calls in Windows, and asynchronous system traps in Mach (and therefore iOS/macOS/etc). These only happen if the thread is at a &quot;safe point&quot;, such as waiting on a synchronisation object or for file I/O.</p>
<p>This is an important consideration, because the OS doesn't necessarily &quot;obey&quot; the same ABI that your language does, with respect to whatever stack discipline you are trying to maintain for GC purposes.</p>
<p>Modern operating systems do allow the user to control which threads receive OS interventions and which do not, at least for those raised by the OS. A common solution is to spawn one &quot;operating system thread&quot; and direct all signals/APCs/ASTs there. This thread may of course serve other runtime purposes, such as an OS/GUI event loop or a concurrent GC.</p>
<p>Synchronous traps such as floating point exceptions and division by zero may need special care.</p>

CC BY-SA 4.0
2023-06-29T00:30:18.550Z
2023-06-29T00:42:58.077Z
2023-06-29T00:42:58.077Z
Pseudonym
<h2>Runtime type tags</h2>
<p>You already have this if the language is dynamically typed, but you could also do it in a statically-typed language for the part of the stack that doesn't have a fixed layout for the whole duration of the function call.</p>
<p>If the type tags are only used by the garbage collector, then you only need a single boolean value to indicate whether each slot is a reference or not.</p>
<h2>Store references on a separate evaluation stack</h2>
<p>Two separate stacks are used for evaluating expressions, one for non-reference values and another for references. Each intermediate result is stored in the correct stack, depending on its static type. The garbage collector only needs to look at the stack of references.</p>
<p>In a bytecode language, this may require having more opcodes, e.g. <code>dup_value</code> and <code>dup_reference</code> for the two stacks instead of just <code>dup</code> when there is one stack.</p>
<h2>Shadow stack</h2>
<p>A separate stack is maintained, which contains the stack offsets at which references are currently stored. When a reference is pushed or popped from the stack, also push or pop its offset from the shadow stack.</p>
<p>See the <a href="https://llvm.org/docs/GarbageCollection.html#the-shadow-stack-gc" rel="noreferrer">LLVM docs</a> for more information.</p>
<h2>Cooperative garbage collection</h2>
<p>The garbage collector is invoked at specific sequence points, on the same thread. The stack layout at these sequence points is known at compile-time, even if they occur in the middle of evaluating an expression.</p>
<p>Each stack frame's layout can be described by some data with a fixed offset in the frame. Each function can only be &quot;paused&quot; for garbage collection at specific points (either at sequence points, or during function calls if those functions transitively invoke the GC), so the compiler only needs to ensure that the layout data will be correct at those points.</p>
<p>To find the roots in the stack, the garbage collector looks at each stack frame, finds the layout data for that frame, and then knows the offsets of the roots in that stack frame. The layout data could be a bitmask, particularly if each stack frame has at most 64 slots at each sequence point; otherwise it could be an index into a constant array of known stack layouts.</p>
<p>This layout data needs to be updated at sequence points, and before most function calls, but it does not need to be updated every time the evaluation stack layout changes. The performance cost of updating the layout data can be tuned further by reducing the number of sequence points.</p>

CC BY-SA 4.0
2023-06-27T18:34:09.493Z
2023-06-29T16:23:02.707Z
2023-06-29T16:23:02.707Z
kaya3
CC BY-SA 4.0
2023-06-29T12:37:54.307Z
Can you expand on "*the stack layout at these sequence points is known at compile-time*", please? Wouldn't function calls complicate this a lot?
Bergi
CC BY-SA 4.0
2023-06-29T14:50:42.953Z
@Bergi I've expanded that section. Hopefully this makes the idea clear.
kaya3
CC BY-SA 4.0
2023-06-30T00:02:18.700Z
@Bergi Often languages compile to machine code/bytecode which permits stack unwinding.  This typically means that you have a pointer to the start of the current frame, and a linked list like structure of frames below it.  This reduces the problem to only having to find pointers within any given frame.
Cort Ammon
# How do precise garbage collectors find roots in the stack?
Posted by: username_0 on 2023-06-27
I know some garbage collectors (conservative GC) treat every word in the stack as a potential pointer to a live object in the heap (provided that the word actually points to somewhere inside an allocated object).

If I understand correctly, precise garbage collectors know to only look at values in the stack that are actually pointers. It seems like this might be easy enough for stack slots that are used to store local variables because something could record the type of each local variable and which stack slot it is stored in (for each function). The harder part is the evaluation stack, where a given stack location could be either a pointer or some other kind of value depending on what part of an expression has been evaluated thus far.

How do precise GCs know where pointers are in the stack?
**Tags:** garbage-collection
---
## 4 answers
### Answer by username_8 on 2023-06-27. Score: 21 | Accepted answer
## Runtime type tags

You already have this if the language is dynamically typed, but you could also do it in a statically-typed language for the part of the stack that doesn't have a fixed layout for the whole duration of the function call.

If the type tags are only used by the garbage collector, then you only need a single boolean value to indicate whether each slot is a reference or not.

## Store references on a separate evaluation stack

Two separate stacks are used for evaluating expressions, one for non-reference values and another for references. Each intermediate result is stored in the correct stack, depending on its static type. The garbage collector only needs to look at the stack of references.

In a bytecode language, this may require having more opcodes, e.g. `dup_value` and `dup_reference` for the two stacks instead of just `dup` when there is one stack.

## Shadow stack

A separate stack is maintained, which contains the stack offsets at which references are currently stored. When a reference is pushed or popped from the stack, also push or pop its offset from the shadow stack.

See the [LLVM docs](https://llvm.org/docs/GarbageCollection.html#the-shadow-stack-gc) for more information.

## Cooperative garbage collection

The garbage collector is invoked at specific sequence points, on the same thread. The stack layout at these sequence points is known at compile-time, even if they occur in the middle of evaluating an expression.

Each stack frame's layout can be described by some data with a fixed offset in the frame. Each function can only be "paused" for garbage collection at specific points (either at sequence points, or during function calls if those functions transitively invoke the GC), so the compiler only needs to ensure that the layout data will be correct at those points.

To find the roots in the stack, the garbage collector looks at each stack frame, finds the layout data for that frame, and then knows the offsets of the roots in that stack frame. The layout data could be a bitmask, particularly if each stack frame has at most 64 slots at each sequence point; otherwise it could be an index into a constant array of known stack layouts.

This layout data needs to be updated at sequence points, and before most function calls, but it does not need to be updated every time the evaluation stack layout changes. The performance cost of updating the layout data can be tuned further by reducing the number of sequence points.
> **Comments:**
> **username_9** (2023-06-29): Can you expand on "*the stack layout at these sequence points is known at compile-time*", please? Wouldn't function calls complicate this a lot?  
> **username_8** (2023-06-29): @Bergi I've expanded that section. Hopefully this makes the idea clear.  
> **username_10** (2023-06-30): @Bergi Often languages compile to machine code/bytecode which permits stack unwinding.  This typically means that you have a pointer to the start of the current frame, and a linked list like structure of frames below it.  This reduces the problem to only having to find pointers within any given frame.  
---
### Answer by username_6 on 2023-06-28. Score: 20
GHC uses a strategy for this that I think is fairly cute: every stack frame is essentially laid out in precisely the same way as a heap object.
Within the GHC runtime system (RTS), every heap object begins with a pointer to a statically-allocated infotable. This pointer is then followed by a payload, which contains the data stored in the heap. This is illustrated by the following diagram from the GHC wiki:

Infotables contain, among other things, bitmaps that describe the layout of the heap object. For example, the Haskell datatype declaration
data T = D String Bool Int#

defines a structure that contains two pointers (a string and a boolean) and one non-pointer (an unboxed integer). Therefore, the compiler will generate an infotable that says “heap objects of this type have two pointers followed by one nonpointer”.
For function closures, the infotable also includes a pointer to the compiled code, and the payload just contains the closed-over values. A bitmap is used to keep track of which of the closed-over values are pointers (to GC-managed memory) and which are not. On most platforms, an additional optimization is used: the code is placed directly adjacent to the infotable, so only one pointer dereference is needed to access both the infotable and the code.
This finally brings us to stack layout. It turns out that a stack frame is actually an awful lot like a function closure! It contains a pointer to some code to run when the stack frame is returned to (the return address) and a payload containing some stack-allocated values. Therefore, GHC essentially represents stack frames as a stack-allocated heap object: an infotable followed by a payload.
These infotables allow the garbage collector to walk the stack in just the same way that it walks pointers within heap objects. In GHC, the stack grows towards lower addresses, so it just starts at the top of the stack and traverses each stack frame until it reaches the bottom. This eliminates the need for individual values to be tagged in any way (though in practice GHC does use a pointer tagging scheme for some other things).
---
### Answer by username_1 on 2023-06-27. Score: 13
### Box all the things

One way is to make the problem trivial: ensure that the stack only ever contains pointers. You can do that by making all data in your runtime *boxed*: all values are represented by a pointer to a block of data that starts with a header describing the content of the block (often with a few spare bits for the GC). This description includes the length of the block as well as a way to know, for each word in the block, whether it's a pointer or not.

For example, a boolean would be represented by a pointer to a block of two words: one header word that encodes the information “there is 1 data word, which is not a pointer”, and one data word that contains 0 or 1. This is expensive if you have mutable values, but relatively cheap if you don't have mutable values (you can still have mutable *variables*): you can have a single copy of False and a single copy of True in your system, and all boolean variables point to either one or the other.

As far as I know this is a common approach in Lisp implementations.

### Separate the pointers from the chaff

You can have separate memory areas (including separate stacks) for pointers and non-pointers. Then the GC knows whether an memory location contains a pointer by looking at the address of that location, without needing to look at the content.

A limitation of this approach is that a function has to know whether it's getting a boxed value or an unboxed value. This reduces the opportunities for polymorphism: you can't have a generic list or dictionary implementation that indifferently supports all element types.

GHC mostly follows this approach. Normal values are boxed, but it has [limited support for unboxed types](https://downloads.haskell.org/%7Eghc/6.12.1/docs/html/users_guide/primitives.html). The limitations on polymorphism are due to the need to separate boxed and unboxed values in memory.

### Pointers are not odd

On almost all computer architectures in use today, pointers store byte addresses, and most elementary data (word-sized integers, floating point values, pointers) uses 2, 4 or 8 bytes and has to be aligned on its size. (Many popular architectures tolerate non-aligned data but at a performance cost so there's little incentive to take advantage of that except to run some legacy code.) Thus any pointer to data that's larger than a byte will be a multiple of 2 (often even a multiple of 4 or even 8).

This allows an implementation trick: if you need to store up to 15 bits of data (up to 31 bits on a 32-bit processor, up to 63 bits on a 64-bit processor), use an odd number as the representation. If you need to store more than that, allocate memory for the data and store a pointer to it: the pointer will be an even number. Thus, small values are unboxed, and large values are boxed.

This approach requires a bit of extra work in integer arithmetic: if $x$ and $y$ are small values with unboxed representations `x` and `y`, then $x+y$ is represented by `x+y-1`, not by `x+y`. But the extra cost of an addition is small compared to the extra cost of a memory access, so this is typically a performance win compared to systematically boxing integers.

Floating point values typically require a whole machine word or two, so they have to remain boxed. Efficient numerical code often requires having special-purpose data structures such as arrays that directly contain floats, rather than polymorphic arrays that contain pointers to floats.

Note in particular that the size of an object in memory fits in an unboxed value as long as the object does not occupy more than half of the total address space.

This is a common approach in ML dialects (including Ocaml).
> **Comments:**
> **username_2** (2023-06-27): Can’t pointers to single bytes be odd? I know that `malloc` will never return one, but if nothing else a pointer to the second character in a C string will likely be odd.  
> **username_3** (2023-06-27): The first approach is also taken by the JVM, though it looks like value classes will be added soonish  
> **username_4** (2023-06-27): @Bbrk24 What you're asking about is commonly referred to as a "derived pointer". The language mentioned, OCaml, has no language feature (except Obj.magic and calling into C) that could produce such a pointer that would ever be traversed by the GC. These kinds of pointers are a concern and languages like Java, OCaml, etc. will typically try to make it impossible for any language feature to be able to produce one. It's not a major issue though, you can imagine that such derived pointers as a language feature could be lowered as a base + offset pair (like a "view" of a string).  
> **username_5** (2023-06-28): Most non-toy Lisp implementations also use the "pointers are not odd" approach for storing fixnums.  
---
### Answer by username_7 on 2023-06-29. Score: 4
This is not a full answer, but a few notes on cooperative garbage collection. Implementing it can get subtle, and there are some points that you should know about if you're planning to go down this route.

## The current stack frame

If the generated code cooperates with the GC, then for the current stack frame, it can explicitly inform the GC of where the roots are. This doesn't work for the stack frames of callers, of course, but it may be useful to think about, because sequence points are more common than calls.

## Callee-save registers

When using cooperative GC, compilers can't use callee-save registers to store heap references unless the compiler can prove that they are safe (i.e. it knows they are referenced, possibly indirectly, from some other root). Callees don't, by definition, know or care what callee-save registers contain.

Note that this is very similar to stack unwinding in a non-GC language. In C++, for example, destructible objects can't be stored in registers across calls.

## The operating system interface

Modern operating systems occasionally hijack a user thread to run code. Some examples are signal handlers in Unix, asynchronous procedure calls in Windows, and asynchronous system traps in Mach (and therefore iOS/macOS/etc). These only happen if the thread is at a "safe point", such as waiting on a synchronisation object or for file I/O.

This is an important consideration, because the OS doesn't necessarily "obey" the same ABI that your language does, with respect to whatever stack discipline you are trying to maintain for GC purposes.

Modern operating systems do allow the user to control which threads receive OS interventions and which do not, at least for those raised by the OS. A common solution is to spawn one "operating system thread" and direct all signals/APCs/ASTs there. This thread may of course serve other runtime purposes, such as an OS/GUI event loop or a concurrent GC.

Synchronous traps such as floating point exceptions and division by zero may need special care.
---
