Race Conditions
Concurrency & Race Conditions · VR Foundations track
5 min read
In this module
When Timing Breaks Correctness
A race condition occurs when program correctness hinges on the relative timing of concurrent operations. Two or more threads are racing. Whichever one finishes first decides the outcome, and if the wrong one wins, the program misbehaves.
The Classic Read-Modify-Write Race
Consider two threads both incrementing a shared counter. At the assembly level (Assembly Language), incrementing a memory value requires three steps: LOAD the value into a register, ADD one, and STORE the result back. If both threads execute these steps interleaved, updates get lost:
- Thread A loads counter (value: 5)
- Thread B loads counter (value: 5)
- Thread A stores 6
- Thread B stores 6
After two increments the counter should read 7. It reads 6. Thread B trampled Thread A's update because it loaded the stale value before Thread A finished writing.
Play the scheduler yourself. Each counter++ is a load, an add and a store, and you decide which thread runs next. Find an order that loses an update, then open the list of every possible schedule and count how few of them get it right.
Two threads, one counter
Each thread runs counter++, which the compiler splits into a load, an add and a store. Pick the order. Can you end with counter = 1?
- 0r1 = counter;// counter++ reads
- 1r1 = r1 + 1;// adds
- 2counter = r1;// writes back
- r1 = 0
- 0r1 = counter;// counter++ reads
- 1r1 = r1 + 1;// adds
- 2counter = r1;// writes back
- r1 = 0
- counter = 0
Every possible schedule
18 of 20 possible schedules lose an update.
| Final result | Schedules |
|---|---|
| counter = 1 | 18 |
| counter = 2 | 2 |
Worked Example: Losing Updates for Real
Here's the race in about fifteen lines of C with POSIX threads:
#include <pthread.h>#include <stdio.h>
int counter = 0;
void *work(void *arg) { for (int i = 0; i < 1000000; i++) counter++; return NULL;}
int main(void) { pthread_t a, b; pthread_create(&a, NULL, work, NULL); pthread_create(&b, NULL, work, NULL); pthread_join(a, NULL); pthread_join(b, NULL); printf("%d\n", counter);}Two threads, a million increments each, so the answer ought to be 2,000,000. Build it with gcc -O0 -pthread and run it a few times on a multi-core machine. You'll get a different number almost every run, usually well short of two million.
The reason is that one innocent counter++ compiles to three separate instructions at -O0:
mov eax, DWORD PTR counter[rip] ; LOADadd eax, 1 ; ADDmov DWORD PTR counter[rip], eax ; STOREA thread can be interrupted, or simply overtaken by another core, between any two of those lines. Turn on -O2 and the numbers change, sometimes landing exactly on 2,000,000, because the optimiser rearranges the loop. It's still a data race, and the C standard says a program with one has undefined behaviour. A correct-looking answer proves nothing.
Predict: in this program, what's the smallest final value counter could possibly end on?
2, which surprises nearly everyone. Thread A loads 0 and stalls. Thread B runs all but one of its increments, then A stores its 1, wiping out B's work. B loads that 1 and stalls. A runs all its remaining increments, then B stores its 2 on top. You'll never see it in practice, but the fact that it's possible tells you how little an unsynchronised result is worth.
A data race is a specific technical term: two threads access the same memory location, at least one is a write, and there is no synchronisation between them. A race condition is the broader concept that program correctness depends on timing. You can have a race condition without a data race (using only atomic operations but in the wrong order) and a data race without a visible race condition (if the value happens not to matter). In practice, data races almost always indicate a race condition.
TOCTOU: Time of Check, Time of Use
The nastiest race pattern goes by the name TOCTOU. A program checks a condition, then later acts on it, blindly assuming nothing changed in between. An attacker who slips into that gap can invalidate the assumption before the program gets there.
File access is the textbook case. A program calls access() to check whether a user can read a file, then calls open() to actually read it. In the sliver of time between those calls, an attacker swaps the file for a symlink pointing at /etc/shadow. The check passed on the original file. The open reads the sensitive replacement.
The fix is to stop checking one thing and using another. Open the file first, then make your checks against the open file descriptor with fstat(), so whatever you inspected is exactly what you'll read. Flags such as O_NOFOLLOW refuse to follow a symlink in the last path component, which closes the swap trick above. For a privileged program, dropping privileges before opening the file is better still, because then the kernel does the permission check for you, atomically.
The same race in a bank account: both threads check the balance, then both withdraw. Find a schedule that pays out twice.
Check, then act
Both threads run if (balance >= 100) balance -= 100 on an account holding 100. Only one withdrawal should succeed. The register paid records the cash each thread handed out.
- 0r1 = balance;// check
- 1if (r1 < 100) goto 5;// too little: skip to the end
- 2r1 = r1 - 100;// act
- 3balance = r1;
- 4paid = 100;// hand over the cash
- r1 = 0
- paid = 0
- 0r1 = balance;// check
- 1if (r1 < 100) goto 5;// too little: skip to the end
- 2r1 = r1 - 100;// act
- 3balance = r1;
- 4paid = 100;// hand over the cash
- r1 = 0
- paid = 0
- balance = 100
Every possible schedule
240 of 246 possible schedules pay out twice.
| Final result | Schedules |
|---|---|
| balance = 0, paid out 200 | 240 |
| balance = 0, paid out 100 | 6 |
Why Race Conditions Hide
Race conditions are infamously hard to reproduce. They hinge on exact timing that drifts with system load, CPU frequency, kernel scheduler quirks, and even ambient temperature. Slot in a print statement to debug, and the timing shifts enough that the bug vanishes: the dreaded Heisenbug. Tools like ThreadSanitizer (TSan) catch data races dynamically, but only the ones that actually occur during a given test run. Static analysers try to reason about every possible interleaving and run into scalability walls on real codebases.
Try the Simulations
Race Condition: Lost Update
Two 'threads' increment a shared counter, but interleaving causes a lost update. Thread B reads the old value before Thread A finishes writing, so one increment is lost.
Atomic Increment: No Lost Update
The same two-thread counter scenario, but this time each thread completes its full LOAD-ADD-STORE sequence before the other begins. No interleaving means no lost updates.