Skip to main content
Be Bitwise

Race Conditions

Concurrency & Race Conditions · VR Foundations track

5 min read

Part ofSystems Programming Companion, week 12

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:

  1. Thread A loads counter (value: 5)
  2. Thread B loads counter (value: 5)
  3. Thread A stores 6
  4. 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?

T1
  1. 0r1 = counter;// counter++ reads
  2. 1r1 = r1 + 1;// adds
  3. 2counter = r1;// writes back
Registers
  • r1 = 0
T2
  1. 0r1 = counter;// counter++ reads
  2. 1r1 = r1 + 1;// adds
  3. 2counter = r1;// writes back
Registers
  • r1 = 0
Shared memory
  • counter = 0
0 steps
Every possible schedule

18 of 20 possible schedules lose an update.

Final resultSchedules
counter = 118
counter = 22

Worked Example: Losing Updates for Real

Here's the race in about fifteen lines of C with POSIX threads:

c
#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:

asm
mov eax, DWORD PTR counter[rip] ; LOAD
add eax, 1 ; ADD
mov DWORD PTR counter[rip], eax ; STORE

A 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.

Data Race vs Race Condition

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.

T1
  1. 0r1 = balance;// check
  2. 1if (r1 < 100) goto 5;// too little: skip to the end
  3. 2r1 = r1 - 100;// act
  4. 3balance = r1;
  5. 4paid = 100;// hand over the cash
Registers
  • r1 = 0
  • paid = 0
T2
  1. 0r1 = balance;// check
  2. 1if (r1 < 100) goto 5;// too little: skip to the end
  3. 2r1 = r1 - 100;// act
  4. 3balance = r1;
  5. 4paid = 100;// hand over the cash
Registers
  • r1 = 0
  • paid = 0
Shared memory
  • balance = 100
0 steps
Every possible schedule

240 of 246 possible schedules pay out twice.

Final resultSchedules
balance = 0, paid out 200240
balance = 0, paid out 1006

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.