<p>I'm reading the <a href="https://gchandbook.org/" rel="nofollow noreferrer">GC Handbook</a> and trying to implement the first collector type described there, a basic <a href="https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na%C3%AFve_mark-and-sweep" rel="nofollow noreferrer">mark and sweep</a>. I know this is not the greatest way to implement a garbage collector, but I want to start with something simple, and improve from there.</p>
<p>I understand the basic algorithm, but I'm not sure how to stop the other threads. Are there some standard techniques for this?</p>
<p>It looks like SBCL uses  <code>pthread_kill</code> to send a signal to the other threads, in it's <a href="https://github.com/sbcl/sbcl/blob/4649d1ca419c5820bb7a1df19dca9c4f7be119c4/src/runtime/thread.c#L1230" rel="nofollow noreferrer"><code>gc_stop_the_world</code> function</a>. Are there other ways?</p>
<p>For context, if it matters: I'm working on a language interpreter that is similar to Lisp or Python, written in C++. And as I've seen in Python world, my goal is to write most application code in the target language, but be able to use C or C++ for the few parts that need to be faster.</p>

<garbage-collection>
How does a simple mark-and-sweep GC stop the other threads?
CC BY-SA 4.0
2024-08-08T15:54:07.733Z
TBH, my proposal would have been exactly what you have in your question. Why do you wan'T alternatives? I mean checkpoint where you explicitly check for gc state should be more expensive and also somewhat tricke because there must be a finite WCET between them.
feldentm
CC BY-SA 4.0
2024-08-08T19:10:42.617Z
@feldentm I'm trying to understand the problem and the possible options, before I get further into implementing things. BTW, I wasn't sure Windows had pthreads, but I guess it does, since SBCL works there.
Rob N
<p>It's possible to ask the threads to stop nicely, <a href="https://blog.stenmans.org/theBeamBook/#_preemptive_multitasking_in_erts_cooperating_in_c" rel="nofollow noreferrer">BEAM</a> style or <a href="https://github.com/golang/go/issues/17831" rel="nofollow noreferrer">old Go</a> style.</p>
<p>In BEAM, each green thread starts with a counter that is slowly exhausted at each safe point. When completely exhausted, the thread executor stops executing the green thread, and starts executing another thread <em>or</em> runs services like IO and GC.</p>
<p>In Go, where the stack is growable, it was possible to have thread stopping in safe points almost for free, by doubling the stack overflow check into a cooperative thread stop: by simply outside changing the stack &quot;maximum&quot; into a invalid small value, the thread would stop in next code that tries to create a new stack frame.</p>
<p>So keeping things simple, the answer is really where the threaded code will check if it is asked to stop into a safe enough point for the garbage collector. From a global <code>volatile</code> variable, from a <code>thread_local</code> variable, or from a named <code>register</code>. The stop the word code needs only to modify these arranged locations, directly  if in shared memory, or indirectly via thread signaling, and wait for all threads to stop in safe points.</p>
<p>Non-cooperative thread suspension for garbage collection, where safe points are a fiction, would need a lot more code mapping or a conservative garbage collector (see, for example <a href="https://github.com/golang/go/issues/24543" rel="nofollow noreferrer">new Go non-cooperative thread preemption</a>)</p>

CC BY-SA 4.0
2024-08-09T23:50:20.763Z
2024-08-11T14:21:51.183Z
2024-08-11T14:21:51.183Z
André L F S Bacci
<p>The simplest and cross platform way is to have the compiler insert regular checks on an atomic for &quot;is GC starting up&quot; and then join a barrier which unlocks after the GC is done. Those checks can be during allocations, on the back edge of loops, and function calls/returns.</p>
<p>Bonus points if those checks also make sure each local variable pointer that is subject to gc is saved to the stack. This concept is known as checkpoints. It puts each thread in a known state so its root is easily checkable by the GC and avoids race conditions in case you (or the compiler) are trying to be clever with the pointers. It also can allow the GC to move allocations and update all the pointers to that allocation.</p>
<p>On windows there is the SuspendThread function (and pthread_suspend in posix) that will stop a thread. However it does not put the thread in any known state it just halts it. That requires that you structure code execution such that every pointer being manipulated by the thread is accessible from the stack root at all times.</p>
<p>The third option is a concurrent mark phase where the threads continue running as the GC is checking all the pointers. This is a more involved solution as it requires that the &quot;mutator&quot; threads (aka the threads executing your code) cooperate as they read and write pointer fields. Marking the objects and values they are reading and writing as alive and pushing them to the queue for further marking.</p>

CC BY-SA 4.0
2024-08-09T06:57:59.567Z
2024-08-09T06:57:59.567Z
ratchet freak
CC BY-SA 4.0
2024-08-09T11:38:56.250Z
'concurrent' gc usually still has a (short/constant time) stw/sync
Moonchild
CC BY-SA 4.0
2024-08-09T11:39:15.200Z
'regular checks'  this is called 'safepointing'
Moonchild
CC BY-SA 4.0
2024-08-09T18:04:42.200Z
I don't see a `pthread_suspend` here: https://www.man7.org/linux/man-pages/man7/pthreads.7.html
I guess the `pthread_kill`, with `SIGUSR2`, as I linked to in the SBCL code, accomplishes the same thing?
Rob N
CC BY-SA 4.0
2024-08-09T19:52:38.877Z
Looks like AIX has it (https://www.ibm.com/docs/en/aix/7.2?topic=p-pthread-suspend-np-pthread-unsuspend-np-pthread-continue-np-subroutine) but Linux does not. pthread_kill needs more work; I don't think it carries any promise that the signal has been delivered before it returns, so you need some other synchronization mechanism to know that the other thread is waiting in its signal handler.
Nate Eldredge
# How does a simple mark-and-sweep GC stop the other threads?
Posted by: username_0 on 2024-08-08
I'm reading the [GC Handbook](https://gchandbook.org/) and trying to implement the first collector type described there, a basic [mark and sweep](https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na%C3%AFve_mark-and-sweep). I know this is not the greatest way to implement a garbage collector, but I want to start with something simple, and improve from there.

I understand the basic algorithm, but I'm not sure how to stop the other threads. Are there some standard techniques for this?

It looks like SBCL uses `pthread_kill` to send a signal to the other threads, in it's [`gc_stop_the_world` function](https://github.com/sbcl/sbcl/blob/4649d1ca419c5820bb7a1df19dca9c4f7be119c4/src/runtime/thread.c#L1230). Are there other ways?

For context, if it matters: I'm working on a language interpreter that is similar to Lisp or Python, written in C++. And as I've seen in Python world, my goal is to write most application code in the target language, but be able to use C or C++ for the few parts that need to be faster.
**Tags:** garbage-collection
> **Comments:**
> **username_1**: TBH, my proposal would have been exactly what you have in your question. Why do you wan'T alternatives? I mean checkpoint where you explicitly check for gc state should be more expensive and also somewhat tricke because there must be a finite WCET between them.  
> **username_0**: @feldentm I'm trying to understand the problem and the possible options, before I get further into implementing things. BTW, I wasn't sure Windows had pthreads, but I guess it does, since SBCL works there.  
---
## 2 answers
### Answer by username_3 on 2024-08-09. Score: 3 | Accepted answer
The simplest and cross platform way is to have the compiler insert regular checks on an atomic for "is GC starting up" and then join a barrier which unlocks after the GC is done. Those checks can be during allocations, on the back edge of loops, and function calls/returns.

Bonus points if those checks also make sure each local variable pointer that is subject to gc is saved to the stack. This concept is known as checkpoints. It puts each thread in a known state so its root is easily checkable by the GC and avoids race conditions in case you (or the compiler) are trying to be clever with the pointers. It also can allow the GC to move allocations and update all the pointers to that allocation.

On windows there is the SuspendThread function (and pthread\_suspend in posix) that will stop a thread. However it does not put the thread in any known state it just halts it. That requires that you structure code execution such that every pointer being manipulated by the thread is accessible from the stack root at all times.

The third option is a concurrent mark phase where the threads continue running as the GC is checking all the pointers. This is a more involved solution as it requires that the "mutator" threads (aka the threads executing your code) cooperate as they read and write pointer fields. Marking the objects and values they are reading and writing as alive and pushing them to the queue for further marking.
> **Comments:**
> **username_4** (2024-08-09): 'concurrent' gc usually still has a (short/constant time) stw/sync  
> **username_4** (2024-08-09): 'regular checks'  this is called 'safepointing'  
> **username_0** (2024-08-09): I don't see a `pthread_suspend` here: https://www.man7.org/linux/man-pages/man7/pthreads.7.html
I guess the `pthread_kill`, with `SIGUSR2`, as I linked to in the SBCL code, accomplishes the same thing?  
> **username_5** (2024-08-09): Looks like AIX has it (https://www.ibm.com/docs/en/aix/7.2?topic=p-pthread-suspend-np-pthread-unsuspend-np-pthread-continue-np-subroutine) but Linux does not. pthread_kill needs more work; I don't think it carries any promise that the signal has been delivered before it returns, so you need some other synchronization mechanism to know that the other thread is waiting in its signal handler.  
---
### Answer by username_2 on 2024-08-09. Score: 2
It's possible to ask the threads to stop nicely, [BEAM](https://blog.stenmans.org/theBeamBook/#_preemptive_multitasking_in_erts_cooperating_in_c) style or [old Go](https://github.com/golang/go/issues/17831) style.

In BEAM, each green thread starts with a counter that is slowly exhausted at each safe point. When completely exhausted, the thread executor stops executing the green thread, and starts executing another thread *or* runs services like IO and GC.

In Go, where the stack is growable, it was possible to have thread stopping in safe points almost for free, by doubling the stack overflow check into a cooperative thread stop: by simply outside changing the stack "maximum" into a invalid small value, the thread would stop in next code that tries to create a new stack frame.

So keeping things simple, the answer is really where the threaded code will check if it is asked to stop into a safe enough point for the garbage collector. From a global `volatile` variable, from a `thread_local` variable, or from a named `register`. The stop the word code needs only to modify these arranged locations, directly if in shared memory, or indirectly via thread signaling, and wait for all threads to stop in safe points.

Non-cooperative thread suspension for garbage collection, where safe points are a fiction, would need a lot more code mapping or a conservative garbage collector (see, for example [new Go non-cooperative thread preemption](https://github.com/golang/go/issues/24543))
---
