Race Conditions and Check-Then-Act

Bug Classes and PrimitivesLesson 8 of 875 minutesLessonNo lab next

The same program, twice, two answers

Suppose two loaders share a tally and each adds one whenever a crate arrives. Either loader’s code looks reasonable on its own: read the total, add one, and store it back. But while one loader is doing that arithmetic, the other can be working from the same old total. Two arrivals can then leave the tally only one higher.

We can give both loaders exactly the same amount of work and still get different totals between runs, because the input doesn’t determine how their operations overlap. We’ll first follow a lost update, then put the same shared counter behind a stock limit and see what it takes to keep the check true until the stock is taken.

Learning objectives

By the end of this lesson

• Observe how repeated runs with the same input can produce different totals.
• Read the three instructions that one line of C compiles to, and say where the other thread gets in.
• Separate a data race from a check-then-act bug by fixing one and watching the other survive.
• Explain why a race detector reports a bug in a run that produced the right answer.

Two loaders and one tally

In the Ubuntu terminal, create the working directory if needed and move into it:

mkdir -p ~/underdunn-course/bug-classes ~/underdunn-course/notes
cd ~/underdunn-course/bug-classes

Save the complete program below as yard.c. Keep the terminal in this directory for the build commands; no source file from an earlier lesson is needed.

/*
 * Night yard. Two loaders keep one tally; two couriers draw on one
 * stock of seals.  Run it as  ./yard tally  or  ./yard shift
 */
#include <stdio.h>
#include <string.h>
#include <threads.h>

#define ROUNDS 200000
#define SEALS  100000

static int  tally;
static int  remaining;
static long handed[2];

static int loader(void *arg)
{
    (void)arg;
    for (int i = 0; i < ROUNDS; i++)
        tally = tally + 1;
    return 0;
}

static int courier(void *arg)
{
    int me = *(int *)arg;

    for (;;) {
        if (remaining <= 0)              /* check */
            break;
        remaining = remaining - 1;       /* act */
        handed[me] = handed[me] + 1;
    }
    return 0;
}

static void run_tally(void)
{
    thrd_t a, b;

    tally = 0;
    thrd_create(&a, loader, NULL);
    thrd_create(&b, loader, NULL);
    thrd_join(a, NULL);
    thrd_join(b, NULL);
    printf("tally %d, expected %d\n", tally, 2 * ROUNDS);
}

static void run_shift(void)
{
    thrd_t a, b;
    int ids[2] = { 0, 1 };

    remaining = SEALS;
    handed[0] = handed[1] = 0;
    thrd_create(&a, courier, &ids[0]);
    thrd_create(&b, courier, &ids[1]);
    thrd_join(a, NULL);
    thrd_join(b, NULL);
    printf("seals %d, handed out %ld, remaining reads %d\n",
           SEALS, handed[0] + handed[1], remaining);
}

int main(int argc, char **argv)
{
    if (argc > 1 && strcmp(argv[1], "shift") == 0)
        run_shift();
    else
        run_tally();
    return 0;
}

Two functions from the C thread API control when the loaders run:

• thrd_create starts another thread running the supplied function. Both calls in run_tally use loader, so two threads execute that loop.
• thrd_join waits for a thread to finish. Joining both before printing keeps the final display from running while either loader is still working.

Each loader has its own loop variable and registers, but both use the same global tally. A store to that global changes the shared value.

The couriers in run_shift also have a mixture of private and shared work:

• Each receives a different entry from ids and increments only its own element of handed.
• Both compete for the same remaining counter.

The ids array stays alive until both joins finish. We use the API from <threads.h> on the course’s Linux toolchain, and this example assumes both thread creations succeed.

Build it the usual way:

gcc -std=c11 -g -O0 -fno-omit-frame-pointer -Wall -Wextra -pthread yard.c -o yard

-pthread asks the compiler and linker for the thread support used by <threads.h>. It does not make the shared variables atomic or add synchronization around them; those decisions remain in the source.

No warnings. Two loaders each add one to tally two hundred thousand times, so the total should be four hundred thousand.

Run ./yard tally five times and compare the totals:

tally 200000, expected 400000
tally 220054, expected 400000
tally 210548, expected 400000
tally 208636, expected 400000
tally 200000, expected 400000

Twenty runs on this machine gave twenty numbers between 200000 and 308451, and never the right one. The first and last lines above are worth a second look, because 200000 is not the program half working. It is one loader’s entire two hundred thousand additions disappearing.

Why one line is not one step

tally = tally + 1 looks like a single action. Ask the compiler:

gdb -q -batch -ex 'disassemble /s loader' ./yard

20          tally = tally + 1;
   0x00000000000011de <+21>:  mov    0x2e3c(%rip),%eax        # 0x4020 <tally>
   0x00000000000011e4 <+27>:  add    $0x1,%eax
   0x00000000000011e7 <+30>:  mov    %eax,0x2e33(%rip)        # 0x4020 <tally>

Three instructions, rather than one indivisible action:

1. Read tally into a register.
2. Add one to the register.
3. Write the register back.

Between the read and the write the value lives in a register belonging to one thread alone, where the other thread cannot see it.

So when both loaders read 41 at the same moment, both compute 42, and both store 42. Two additions happened, but the tally advanced by one. That is the lost update, and repeating it across four hundred thousand rounds is where the missing hundred and eighty thousand went.

That sequence explains the lost update in this unoptimized build. Unsynchronized conflicting accesses to this non-atomic object are a data race, which C treats as undefined behavior, so these instructions aren’t a promise about every compiler’s translation.

The total changes between runs

Repeating the same input doesn’t guarantee the same overlap. A correct total may mean the threads happened to avoid a damaging order, while a low total shows one of the possible failures.

Run twenty trials and keep the individual results, including any correct ones:

for n in $(seq 1 20); do ./yard tally; done

The range you observe describes those trials, not a proven best or worst case. If all twenty print the expected total, the unsynchronized accesses in the source still need an explanation.

The same fault against a limit

A miscounted tally is an accounting error. Point the identical fault at a resource and it becomes something else.

The yard holds a hundred thousand seals. Each courier checks whether any remain, and if so takes one. Read by itself, that sequence appears to prevent overdraw. The missing question is whether the other courier can take the last seal after this courier checks but before it decrements:

        if (remaining <= 0)              /* check */
            break;
        remaining = remaining - 1;       /* act */

The yard has a hundred thousand seals, so the couriers between them should hand out a hundred thousand. Let’s see what they report:

./yard shift

seals 100000, handed out 175584, remaining reads 0
seals 100000, handed out 186491, remaining reads 0
seals 100000, handed out 179311, remaining reads 0
seals 100000, handed out 189658, remaining reads 0
seals 100000, handed out 196580, remaining reads -1

The yard issued roughly eighty thousand seals it did not have.

Four of those runs finish with remaining reading zero, which looks reasonable if you inspect only that counter. The separately recorded number handed out tells a different story: the yard issued more seals than it started with. The fifth run also leaves a negative remainder, making the violation visible in both quantities.

The check above the decrement may make -1 look impossible when we follow one courier alone. It doesn’t exclude the other courier changing the counter after that test. To understand how much of the overdraw comes from lost updates and how much comes from that gap, we’ll remove one problem at a time.

Time of check, time of use

There are two things going wrong with the seals: updates can be lost, and a decision can become stale before the courier acts on it.

The tally contains a data race, within the broader concurrency problems covered by CWE-362: conflicting accesses to a shared non-atomic location are not ordered by synchronization.

The plain seals example has that problem too. Its decrements can be lost before we even consider whether checking and taking a seal belong together.

The separate check and decrement create a time-of-check to time-of-use bug, CWE-367, usually shortened to TOCTOU. The fault is in the gap between two operations:

1. Courier A tests remaining > 0 and is correct at the moment it tests.
2. Courier B takes the last seal.
3. Courier A acts on a decision that was true when it was made.

The same gap appears in other operations:

• A program checks that a path is safe, then opens it after the path has changed.
• It checks a file’s owner, then writes to a file whose ownership has changed.
• It validates a request, then uses a buffer another thread can still change.

In each case, the check answered a question about an earlier state.

Both bugs need concurrency, though not necessarily threads. Anything that can change shared state between your check and your act will do, including another process, a signal handler, or a user with a symbolic link and good timing.

Fixing one and watching the other survive

An atomic operation is indivisible with respect to competing accesses to that atomic object. We can use an atomic decrement to stop the couriers losing each other’s updates, while deliberately leaving the availability check separate. Start a new variant:

cp yard.c yard-atomic.c

Add the header below beside the other includes and replace static int remaining; with the atomic declaration. Keep tally unchanged; we will run this variant in shift mode only.

#include <stdatomic.h>

static atomic_int remaining;

        if (atomic_load(&remaining) <= 0)   /* check */
            break;
        atomic_fetch_sub(&remaining, 1); /* act */

Replace the check and decrement inside courier with the two operations above, leaving its increment of handed[me] in place.

In run_shift, replace the initial assignment with atomic_store(&remaining, SEALS);, and replace the final remaining argument to printf with atomic_load(&remaining).

Now each decrement updates the shared atomic value without losing another decrement. Does that also prevent an extra seal from being issued? Build it and compare the runs:

gcc -std=c11 -g -O0 -Wall -Wextra -pthread yard-atomic.c -o yard-atomic
for n in $(seq 1 10); do ./yard-atomic shift; done

Here’s a recorded set of ten runs:

seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1
seals 100000, handed out 100001, remaining reads -1

The large overdraw disappears in this recorded set of runs, but eight of them still issue one extra seal.

In shift mode the accesses to remaining are now atomic, and each thread has its own handed element. That removes the data race there; it doesn’t make the earlier availability decision stay valid.

Follow the last seal with both couriers:

1. A loads 1 and passes its test.
2. B also loads 1 and passes.
3. A subtracts one, taking the count to zero.
4. B subtracts one, taking it to minus one.

Both increments of handed are recorded correctly. The arithmetic is now reliable, but it reliably records two decisions made against the same last seal.

Changing the counter type fixed one defect without closing the gap between the check and the act. To close that gap, a courier needs exclusive access while it makes and carries out the decision.

Copy the original, non-atomic yard.c to yard-locked.c. A mutex lets one thread enter a protected region while another waits for the same lock. Declare one beside the counter:

cp yard.c yard-locked.c

static mtx_t counter_lock;

    for (;;) {
        mtx_lock(&counter_lock);
        if (remaining <= 0) {            /* check */
            mtx_unlock(&counter_lock);
            break;
        }
        remaining = remaining - 1;       /* act */
        handed[me] = handed[me] + 1;
        mtx_unlock(&counter_lock);
    }

Replace the loop in courier with the loop above. Add mtx_init(&counter_lock, mtx_plain); at the start of run_shift, before creating threads, and mtx_destroy(&counter_lock); after both joins.

Notice the unlock before break: leaving while still holding the mutex would strand the other courier. Build and test this variant in shift mode:

gcc -std=c11 -g -O0 -Wall -Wextra -pthread yard-locked.c -o yard-locked
for n in $(seq 1 5); do ./yard-locked shift; done

The recorded runs were:

seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100000, remaining reads 0
seals 100000, handed out 100000, remaining reads 0

Exactly right, five times out of five. The reason is in the locked region: the other courier can’t change remaining between this courier’s test and subtraction. The repeated total agrees with that explanation, but the lock is what keeps the decision valid.

What the tools say

valgrind --tool=helgrind is the race detector available here. Point it at the shift:

valgrind --tool=helgrind ./yard shift

==31857== Possible data race during read of size 4 at 0x10C024 by thread #3
==31857== Locks held: none
==31857==    at 0x109216: courier (yard.c:29)
==31857==
==31857== This conflicts with a previous write of size 4 by thread #2
==31857== Locks held: none
==31857==    at 0x109229: courier (yard.c:31)
==31857==  Address 0x10c024 is 0 bytes inside data symbol "remaining"

Read what it named. Line 29 is the check, line 31 is the act, and the address resolves to remaining by symbol. Helgrind has reported the bug by pointing at both halves of it and at the variable they disagree about.

Now look at the rest of that run’s output, because it contains a surprise:

seals 100000, handed out 100000, remaining reads 0
==31857== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 1 from 1)

The program printed the correct answer even though Helgrind reported conflicting accesses. Valgrind changes execution timing, and these recorded runs did not display the overdraw seen outside it. That doesn’t mean the accesses were synchronized, or that running under the tool guarantees a correct total.

Helgrind isn’t comparing the answer with SEALS. It tracks synchronization relationships between accesses and reports conflicting accesses that aren’t ordered appropriately. This ordering is often called happens-before: a lock or another synchronization operation establishes which access must precede another. A lost update needn’t appear in the final total for those accesses to reveal a data race.

Locks are one way to establish that order, but not the only one. The Helgrind manual explains its happens-before model.

Run it against the locked build to see the other half of the claim:

valgrind --tool=helgrind ./yard-locked shift

==32109== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 8 from 8)

Clean, because the lock discipline is now consistent.

The recorded AddressSanitizer/UndefinedBehaviorSanitizer run also produced no diagnostic while overissuing seals. Those checks aren’t a substitute for race detection: the relevant accesses name real shared objects, and the problem is how competing operations are ordered. You can compare that result with:

gcc -std=c11 -g -O0 -pthread -fsanitize=address,undefined yard.c -o yard-san
./yard-san shift

Safety note

ThreadSanitizer on the course VM

GCC’s -fsanitize=thread supplies another race detector. It failed to start in the recorded WSL2 environment with this message:

FATAL: ThreadSanitizer: unexpected memory mapping 0x5a491553b000-0x5a491553c000

That is a tool-startup failure, not a finding about yard, and it isn’t a claim about every WSL2 installation. Use Helgrind for the comparison here rather than changing the program to chase this environment error.

What the bug hands you

The atomic variant can grant one more seal than the available stock in the two-courier example. It doesn’t need a chosen address or an oversized input: both couriers act on an availability check that was true when read but no longer protects the later subtraction.

The result depends on timing rather than a chosen address. In these runs we observe the bad overlap; we don’t select exactly when it occurs. The program applies its own logic using a decision that no longer describes the available stock.

Compare that with Logic Bugs:

• The depot omitted a required ownership decision.
• The yard makes the availability decision, but allows its premise to change before acting.

Both violate an application rule. For the yard, we have to follow two executions together to see how it happens.

Knowledge check

Question 1 of 3

Twenty runs of ./yard tally gave twenty different numbers. What is the best description of what one run tells you?

It establishes the worst possible total if it is the lowest result observedIt shows one outcome, not the full range of results the scheduling permitsIt establishes correctness if the printed total matches the number of additions

Check answer

When the results don’t match

• If ./yard tally prints 400000 every time, verify the original build and try more runs or a larger ROUNDS. Scheduling can hide the visible lost update, even though the source still has conflicting unsynchronized accesses. A single core does not make those accesses safe.
• If the build fails on <threads.h>, the C library is older than the one this course uses. Confirm with gcc --version and ldd --version rather than switching to POSIX threads, since the rest of the page depends on this file.
• If the shift hands out exactly 100000 on a plain build, check that you are running ./yard shift and not ./yard, and that you have not left the mutex edit in place.
• If helgrind reports races inside thrd_create and nothing else, read further down. Those entries come from the library’s own startup, and the ones that matter name loader or courier.
• If the disassembly shows something other than three instructions, note what you have instead and use it. The claim that matters is that the line is more than one step, not that it is exactly three.

To recover a known state, rebuild from the listing. Keep the three builds under separate names so you can rerun any of them.

Check your understanding

Work through two questions:

1. Give the atomic variant one seal and the same two couriers. Trace an interleaving that hands out two seals, then explain which step the locked variant prevents. A run can help check your reasoning, but follow the order even if that run doesn’t overdraw.
2. For the original runs, what would a reconciliation job miss if it kept only remaining and discarded both handed counters?

Compare your reasoning

With one seal, both atomic loads can read 1 before either subtraction runs. Both couriers then subtract and record a grant. Under the mutex, the second courier can’t perform its check until the first has finished the protected region, so it sees zero and exits without taking a seal.

If reconciliation examines only remaining, a negative value exposes the problem while zero can hide it. The total handed[0] + handed[1] shows how many seals actually went out, so keeping it lets us detect the discrepancy in either case. Zero isn’t inherently a worse result; it just looks reassuring if we throw away the other counters.

What this section adds up to

The examples gave us several ways to reach an unwanted result without redirecting a return address. Some still used the familiar buffer overflow, but changed a decision or counter instead of taking over execution.

Each example broke a different assumption:

• The depot exposed an unchecked ownership rule and then an unchecked index.
• The consignment board admitted negative indices.
• The ticket printer and visitor register let input bytes supply a pointer.
• The yard granted extra stock through a decision that no longer described what was available.

Calling each of these a vulnerability doesn’t tell us what it allows. An indexed read has a stride; a format-string write has a count; the yard’s extra grant depends on an overlap between two operations. Those details are what let us compare their capabilities.

These examples used the program’s own arrays, structures and counters. Dynamically allocated storage adds another participant: the allocator deciding where an object goes and what happens to its storage after release. That requires a separate look at the chosen allocator and build, just as our frame and global layouts required measurements rather than assumptions.