Thread safety vs Re entrancy

Question

I know this has been discussed a lot in this forum. But one thing still confuses me. Wikipedia mentions that every re entrant code is thread safe. http://en.wikipedia.org/wiki/Reentrant_%28subroutine%29 And later on gives an example of a function which is re entrant but not thread safe.

int t;

void swap(int *x, int *y)
{
    int s;

    s = t;  // save global variable
    t = *x;
    *x = *y;
    // hardware interrupt might invoke isr() here!
    *y = t;
    t = s;  // restore global variable
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}

This confuses me. Are all re entrant codes thread safe? Also, are all recursive function thread safe. I am not able to visualize the difference.

Thanks

Answer 1

That function is not thread safe because it accesses a resource t that is outside of function scope (not allocated on the stack) without any protection mechanisms (e.g. a lock) to ensure that access to t is atomic.

The Wikipedia page actually states:

A reentrant subroutine can achieve thread-safety, but this condition alone might not be sufficient in all situations.

(My emphasis).

UPDATE:

Reentrant (as defined in the article) simply means that a single thread of execution (think DOS) can "rip the instruction pointer" out of the middle of the executing routine, put it somewhere else, and continue a linear flow through new code (e.g. an interrupt subroutine in the DOS days), and that same linear flow can go back into the function a second time. In this limited scenario, the second invocation of the function MUST complete before control is transferred away from the interrupt subroutine back to "regular" program execution, which would resume at the same point in the routine where the instruction pointer was originally ripped away. This scenario does not allow for arbitrary thread scheduling, but rather for an interruption that switches control to a new point, which then completes, and resumes back at the point it was interrupted.

Note that in real life, things may not be so simple. I'm not entirely sure anymore (been... 20 years?), but I think one interrupt routine can interrupt and interrupt routine already in progress (e.g. a soft debugger interrupt can interrupt the timer interrupt, etc).

Answer 2

The concepts of re-entrancy and thread safety are related, but not equivalent. You can write a re-entrant function that is not thread-safe, and a thread-safe function that is not re-entrant. I will use C# for my examples:

Re-entrant Function that is not Thread-Safe

This function reverses the entries of an array:

void Reverse(int[] data) {
    if (data == null || data.Length < 2) return;
    for (var i = 0 ; i != data.Length/2 ; i++) {
        int tmp = data[i];
        data[i] = data[data.Length-i-1];
        data[data.Length-i-1] = tmp;
    }
}

This function is clearly re-entrant, because it does not reference outside resources. Its thread safety, however, is conditional upon not passing it the same data from multiple threads. If several threads concurrently pass Reverse the same instance of an array, an incorrect result may be produced. One way of making this function unconditionally thread-safe would be an addition of a lock:

void Reverse(int[] data) {
    if (data == null || data.Length < 2) return;
    lock (data) {
        for (var i = 0 ; i != data.Length/2 ; i++) {
            int tmp = data[i];
            data[i] = data[data.Length-i-1];
            data[data.Length-i-1] = tmp;
        }
    }
}

Thread-Safe Function that is not Re-Entrant

This function calls function f() c times, and returns the value that has been returned more times than other values.

static int[] counts = new int[65536];

unsigned short MaxCount(Func<unsigned short> f, int c) {
    lock(counts) {
        Array.Clear(counts, 0, counts.Length);
        for (var i = 0 ; i != c ; i++) {
            counts[f()]++;
        }
        unsigned short res = 0;
        for (var i = 1 ; i != counts.Length ; i++) {
            if (counts[i] > counts[res]) {
                res = i;
            }
        }
        return res;
    }
}

This function is thread-safe, because it locks the static array that it uses to do the counting. However, it is not re-entrant: for example, if the functor f passed in were to call MaxCount, wrong results would be returned.

Answer 3

Are all re entrant codes thread safe?

No.

Later in the Wikipedia article: …The key for avoiding confusion is that reentrant refers to only one thread executing. It is a concept from the time when no multitasking operating systems existed.

In other words, the concept of reentrance is oblivious to multithreaded execution (as the most common example). Only if that is an actual constraint in your system, then yes, reentrant would qualify as thread safe (but there would also be only one thread in that environment).

IMO, the term "reentrant" should be used only in the context of qualifying systems (does not apply to your desktop OS, but would apply to some embedded systems).

Now, if you really want to force use of the word 'reentrance' into a multithreaded environment: You could enforce reentrance in a multithreaded system only if you also guaranteed that it is also threadsafe. Perhaps a better question to ask would be "In order to guarantee reentrance in a multithreaded context, would that imply the function and all data it refers to also needs to be threadsafe?" - A: Yes, the function and everything it refers to would also need to be threadsafe and reentrant for the function to be reentrant in that context. Achieving this quickly becomes complex, and is a reason global variables are not a good idea.

Also, are all recursive function thread safe.

No.

Answer 4

If your subroutine doesn't affect external variables (no side effects), you can say it is re-entrant. While this is not a rule of thumb, it is a good guideline.
If the subroutine uses external variables and saves state of external variables at the beginning and restores that state at the end, then the subroutine is re-entrant.

If a subroutine modifies external variables and it doesn't save their state first, and it is interrupted, the state of those external variables can be changed, thus when the call returns to the original location in the subroutine, the external variable is out of sync, which results in an inconsistent state for the subroutine.

Re-entrant functions save their state (on their local stack, within the thread's stack not using globals).

In your case, you access an external variable, t, but it is re-entrant because the variable is saved and restored at the end of the subroutine.

Normally thread safe implies re-entrant, but again not a rule more of a guideline. Note: Some locks in java are re-entrant so you can recursively call the method and not be blocked by previous calls. (re-entrance in this context means that a threads can access any section locked with the same lock - the thread can reenter any block of code for which it already holds the lock)

Solution/Answer:
If you protect t with atomics you should get a thread safe subroutine. Also, if you place t on each thread's stack (make it local) then the subroutine becomes thread safe since there is no global data.

Also, reentrant != recursive; you can just as well execute an ISR within a recursive subroutine. Thread-wise, if you call a recursive subroutine from 2 threads, you will get garbage. To make is thread safe, protect the recursive subroutine with re-entrant locks (other non re-entrant locks will result in deadlock/blocking).

Answer 5

The function "swap" is not reentrant, since it uses global state (to whit, the global variable "t").