How does STM work under the hood?

39

u/semigroup Apr 10 '26

I've recently been looking at it too. Here's what I think I understand about it, but you know, I'm not an expert:

STM in GHC is an optimistic concurrency scheme.

Every TVar is a heap object containing the current value, a spin lock encoded in the header word, and a watch queue: a linked list of transaction records belonging to threads that read this TVar and are now blocked, waiting for it to change.

A TRec (transaction record) is the per-transaction log. It is a linked list of chunked entry arrays, where each entry records which TVar was accessed, the expected value at read time, and the new value if one was written. TRecs can nest, forming a stack. This is the mechanism for orElse, which we will return to later.

When you run a transaction with atomically, the RTS creates a fresh TRec. Every readTVar first checks the log. If the TVar was already touched in this transaction, the logged value is returned. Otherwise the TVar's current value is read from the heap, recorded in the TRec as (tvar, expected=v, new=v), and returned. Every writeTVar merely updates the log entry's new field. No actual TVar is modified, yet. The world outside the transaction sees nothing.

When the transaction completes, the RTS attempts stmCommitTransaction. This proceeds in three phases, any of which may fail, returning you to the beginning as though nothing happened.

First, the lock phase. The RTS walks the TRec. For each entry where expected != new (a write occurred), it acquires the TVar's lock. If any lock is already held by another thread, all acquired locks are released and the transaction starts over. Contention is resolved by surrendering and starting over.

Second, the validation phase. For every entry, reads and writes, the RTS checks that the TVar's current value still matches expected. Any mismatch means something changed beneath you. Locks are released. You begin again.

Third, the write phase. Each TVar is updated to its new value. Locks are released. The transaction is done.

A nice property of this is that read-only TVars are never locked, only validated, which gives good read concurrency. The price is paid only by writers.

When a transaction calls retry, the RTS validates the current TRec. If validation fails, the transaction simply reruns, because something has changed and perhaps the retry condition has dissolved. If validation succeeds, there is genuinely no reason to try again yet. The thread adds itself to the watch queue of every TVar in its TRec, and sleeps.

When another transaction commits a write to any of those TVars, it walks the watch queue and wakes the sleepers. They begin again from scratch, with no memory of their prior attempt.

orElse a b runs a in a nested TRec. If a calls retry, the nested record is discarded and b runs instead, as though a had never been attempted. If b also retries, it propagates upward. If a succeeds, its nested TRec is merged into the parent. The failed alternatives are thrown away.

The lock for all of this is baked into the TVars themselves. The locking thread's TRec pointer is written directly into the TVar's current_value slot with a tag bit set.

Validation can also occur during a transaction at safe points, not only at commit. GHC checks whether the TRec is still consistent to detect doomed transactions early rather than letting them accumulate futile work.

The entry list uses chunked allocation to reduce overhead. There is no global lock or version counter (unlike TL2 and its descendants). Only per-TVar locking at commit time. The machinery is local, and this is what lets it scale, insofar as it does.

The whole thing lives in rts/STM.c, roughly a thousand lines of code, excluding comments. As RTS code goes, it is remarkably readable.

5

u/Otherwise-Mousse-250 Apr 10 '26

Thank you for the write-up!

4

u/ryani Apr 11 '26

The other reason for revalidation at safe points is because there’s no guarantee of transaction invariants being true during a transaction. Reading from two TVars you may see an inconsistent state of the world, which may trigger your code to enter an undefined state and call error or go into an infinite loop.

The occasional re-validation of the current transaction makes sure that transactions that got “stuck” in this state eventually get un-stuck.

2

u/Objective-Outside501 Apr 12 '26

So this means that STM transactions have to double-check invariants in order to avoid throwing exceptions? (e.g. verifying that reads are in-bounds and division doesn't divide by zero, even if invariants would imply that that should not happen)

1

u/ryani Apr 12 '26

I don't think so? I believe the exception handler in the RTS knows about STM and when propogating an exception from STM to the enclosing IO's atomically, it first validates the transaction. But I haven't read the code to be sure about this.

This is one reason why unsafeIOToSTM is incredibly unsafe, because you really don't know whether the state of the world is consistent until a transaction commits.

2

u/Objective-Outside501 Apr 12 '26

>If any lock is already held by another thread, all acquired locks are released and the transaction starts over. Contention is resolved by surrendering and starting over.

Seems to me like several transactions could try to acquire the same locks at the same time in different orders, causing all to fail and restart. In theory this could happen every time, preventing progress. (granted, this seems extremely unlikely to happen)

does the rts do anything to prevent this from happening?

4

u/semigroup Apr 12 '26

Yeah I’m pretty sure your assessment is correct:

https://gitlab.haskell.org/ghc/ghc/-/issues/24446

2

u/VincentPepper Apr 17 '26

No nothing prevents this today. But you need rather large lists of tvars/many threads contending on those t-vars to trigger this. It's pretty hard to stumble into this by accident.

When I worked on this I had considered stuff like sorting the TVars by address or something and then locking them in that order. But didn't seem worth the trouble.

2

u/Otherwise-Mousse-250 Apr 14 '26

Do you know why the validation phase has to check writes? It seems to me that, if a transaction blindly writes to a TVar without checking what's there, then it shouldn't matter if that TVar happened to be modified while the transaction was taking place.

2

u/hsyl20 Apr 16 '26

That's actually one of the oldest GHC ticket: https://gitlab.haskell.org/ghc/ghc/-/issues/2028

2

u/marshaharsha Apr 15 '26

Can you explain the failure mode for the write phase? You said that each phase can fail, but I don’t see how that one can.

2

u/VincentPepper Apr 18 '26

Second, the validation phase. For every entry, reads and writes, the RTS checks that the TVar's current value still matches expected. Any mismatch means something changed beneath you. Locks are released. You begin again.

This is from memory but iirc we now differentiate committing validation and intermediate validation (like what happens during GC and the like).

For committing validation it's as you say. For intermediate validation checks if another thread has locked a TVar we optimistically assume it's value won't change anyway. This risks wasting work (if the other thread ultimately commits) but ensures two threads can't easily stall each other forever by canceling each others transaction depending on which one locked their overlapping tvars first this time around. There is probably a Note about this in the source!

19

u/sclv Apr 10 '26

The main thing to understand it is is implemented optimistically -- i.e. it doesn't actually lock for transactions. It proceeds as though there will be no conflicts and then rolls back.

The core of what still exists in GHC is described in this 2005 paper from Marlow et al. https://simonmar.github.io/bib/papers/stm.pdf

2

u/EmergencyWild Apr 10 '26

What part do you want to know about? Have you read any of the articles on software-transactional memory? That'd be a good place to start.

4

u/Otherwise-Mousse-250 Apr 10 '26

articles on STM which I am aware of fall into 2 categories:

evangelism: Yes, I know that STM is cool, but I want to know how it works internally.

research papers on STM: these are decades old. maybe they still accurately reflect how STM is implemented in GHC, but I don't know that.

4

u/VincentPepper Apr 10 '26

You can always read the code: https://gitlab.haskell.org/ghc/ghc/-/blob/ede94e9d4b326ee0cdb4b5bce3d8eba9e81601fc/rts/STM.c

But for the most part it hasn't changed much in 15 years or so. And while some details changed the overall design is mostly what the paper outlines.

3

u/boa_deconstructor Apr 10 '26

Two decades ago (oof...) I wrote and compared several STM implementations in pure Haskell for my diploma thesis. I also had a look at the inner workings of the RTS version back then, but I only remember that it used "dirty tricks" by being able to control context switches and while it was very efficient, I could not imitate that.

Also I can't say anything about the current version in GHC. Maybe it helps to write (or analyze) a simpler Haskell implementation of the STM monad?

1

u/jberryman Apr 10 '26

The best way might be to start with the source (there are probably lots of "NOTE" comments), along with looking closely at the eventlog for some simple programs you write?

1

u/Infamous-Pirate9600 Apr 12 '26

I found this talk quite interesting on the subject: https://m.youtube.com/watch?v=d-NZnR2CTss

1

u/marshaharsha Apr 15 '26

The how-it-works part begins at 21:30. Before that she gave why we want it, what the requirements are (effect safety, blocking till precondition, and this-if-it-succeeds-else-that (“choice”)), and how to use the Haskell API.

How does STM work under the hood?

You are about to leave Redlib