A Race Condition, Made to Happen

Making the machine show its hand

The three steps are the same three steps. Written out, with the thread giving up the processor between reading and writing, the interleaving the machine is allowed to produce at any moment is produced every time.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <sched.h>

#define EACH 20000

static long counter;

static void *bump(void *unused)
{
    (void)unused;
    for (long i = 0; i < EACH; i++) {
        long seen = counter;              /* 1. load  */
        sched_yield();                    /*    the switch that is always allowed */
        counter = seen + 1;               /* 2. add and 3. store */
    }
    return NULL;
}

int main(void)
{
    pthread_t a, b;

    pthread_create(&a, NULL, bump, NULL);
    pthread_create(&b, NULL, bump, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);

    long should_be = 2 * (long)EACH;
    printf("expected %ld, got %ld, lost %ld\n",
        should_be, counter, should_be - counter);
    printf("the answer is %s\n", counter == should_be ? "RIGHT" : "WRONG");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -pthread -o race-shown race-shown.c
$ ./race-shown
expected 40000, got 20000, lost 20000
the answer is WRONG
$ for i in $(seq 5); do ./race-shown | tail -1; done | sort | uniq -c
      5 the answer is WRONG

Half the increments vanished, five runs out of five.

sched_yield changed nothing about what the program computes. It asks the scheduler to run somebody else now, which the scheduler was free to do at that point anyway, and at a thousand other points besides. The two programs are the same program: one hides the bug and one shows it.

So the lesson is the opposite of a demonstration. A race condition is not something you can decide is absent by running the program. Chapter thirty two's shape.c, with a lock, gave 200000 five times out of five and is correct; race.c gave 2000000 five times out of five and is wrong. The two transcripts look the same. Only the code tells you which is which.

And the part that makes it dangerous

Run the second program with far fewer increments.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <sched.h>

#define EACH 50

static long counter;

static void *bump(void *unused)
{
    (void)unused;
    for (long i = 0; i < EACH; i++) {
        long seen = counter;
        sched_yield();
        counter = seen + 1;
    }
    return NULL;
}

int main(void)
{
    pthread_t a, b;

    pthread_create(&a, NULL, bump, NULL);
    pthread_create(&b, NULL, bump, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("%s\n", counter == 2 * (long)EACH ? "right" : "wrong");
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -pthread -o race-small race-small.c
$ bad=$(for i in $(seq 20); do ./race-small; done | grep -c wrong)
$ echo "fifty increments each: $bad of twenty runs wrong, $((20 - bad)) right"
fifty increments each: 11 of twenty runs wrong, 9 right

Fifty increments each is enough to go wrong, and not enough to go wrong every time. The size of the loop is not what decides it. Whether the two threads overlap is, and that is the scheduler's business and not the programmer's.

That is the whole danger of a race condition, and it is what an examination answer should say. The bug is not in the program's logic, it is in the program's timing, so:

• it passes testing, as race.c did five times over;
• it works on the developer's machine and fails on the customer's;
• it appears under load, which is when it costs most;
• it can disappear when you add a print statement to look for it, because the print changes the

timing;

• and it can sit for years in code everybody believes is correct.

The interleaving, written out

Two threads, one counter, starting at 5. The correct answer is 7.

The counter ends at 6 and should be 7. Neither thread did anything wrong. A question that asks you to demonstrate a race condition wants exactly this table, with the shared value in the last column.

Note that the ordering 1, 3, 5, 2, 4, 6, where A finishes before B starts, gives 7. Both orderings are allowed and only one is right, which is the definition.

A race is not only a counter

The last one has a name, time of check to time of use, and it is a security bug rather than a counting bug: a program that checks it may write a file and then writes it can be tricked by anybody who changes the file in between.

Distinctions that carry marks

What it does not mean

A race condition is not a compiler bug. The compiler did what the language allows.

It is not solved by making the variable volatile. volatile stops the compiler caching the value in a register across statements. It does nothing about two threads doing load, add and store at the same time, and a student who offers it as the answer has not understood the problem.

It is not solved by making the loop shorter, or by hoping. The small version above was right twenty times and is exactly as wrong as the large one.

It is not limited to threads. Two processes sharing memory (Chapter twenty two) race in the same way, and so do two programs appending to one file.

Quick revision

• A race condition is when several processes touch the same data at once and the outcome

depends on the order.

• counter++ is load, add, store. A switch or a second core between any two of them loses an

update.

• One million increments each, two threads, no protection: the answer was wrong on every run and

nearly a million increments disappeared.

• One thousand each: right twenty times out of twenty, because the threads never overlapped.

A race that does not appear is still there.

• It is a bug in timing, so it survives testing, appears under load, and vanishes when you

add a print to look for it.

• volatile does not fix it. Mutual exclusion does.
• The examinable demonstration is the interleaving table with the shared value in the last

column.

Test yourself

1. Define a race condition. A situation in which several processes access and change shared

data concurrently and the result depends on the order in which the accesses happen.

1. Why is counter++ unsafe for two threads? It is three machine steps, load, add and store,

and two threads can both load the same value before either stores, so one increment is lost.

1. Draw the interleaving that loses an increment. Both threads load the same value, both add

one to their own register, both store the same result. Two increments, one effect.

1. A program with a race was tested a hundred times and passed. Is it correct? No. A race is

a timing bug; passing a test means the bad interleaving did not happen, not that it cannot.

1. Does volatile fix a race condition? No. It affects how the compiler keeps the value, not

whether two threads can be inside load, add and store at the same time.

1. Why does adding a print statement often make a race disappear? Printing takes time and

changes the timing, so the window in which the two threads overlap moves or closes.

1. Name a race that is a security problem rather than a counting problem. Time of check to

time of use: a program checks that it may write a file and the file is changed between the check and the write.