CODEWITHSUNDEEP
cmultithreading
Yifan Zhang
Yifan Zhang

Reputation: 1501

Why is this code reentrant but not thread-safe

I used to think all reentrant functions are thread-safe. But I read Reentrancy page in Wiki, it posts code that is "perfectly reentrant, but not thread-safe. because it does not ensure the global data is in a consistent state during execution"

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);
}

I don't understand its explanation. Why is this function not thread-safe? Is it because the global variable int t will be changed during threads execution?

Upvotes: 19

Views: 4622

Answers (6)

Gaurav Saxena
Gaurav Saxena

Reputation: 729

Assume Thread A and Thread B. Thread A has two local variables a = 5, b = 10 and Thread B has two local variables p = 20, q = 30.

Thread A calls : swap (&a, &b) ;

Thread B calls : swap (&p, &q) ;

I am assuming that both the threads are running on different cores and belong to the same process. Variable t is global and int x, int y are local to the function as given. The following scheduling of threads show how the value of 't' can vary depending on scheduling of threads and hence making the code thread unsafe. Say global t = 100;

 Thread A         Thread B
 1) int s;        int s;
 2) s = 100;      s = 100;
 3) t = 5;        no operation(nop);
 4) nop;          t = 20;  // t is global so Thread A also sees the value as t = 20
 5) x = 10;       x = 30;
 6) y = 20;       y = 20;  // Thread A exchange is wrong, Thread B exchange is OK

Now try to imagine what would have happened if statements 3 and 4 are in different order above. t would then get the value 5 and exchange in thread B would be wrong. The situation is even easier if the two threads are on the same processor. Then none of the operations above be simultaneous. I have just shown interleaving in steps 3 and 4 as these are the most important ones.

Upvotes: 3

gcbenison
gcbenison

Reputation: 11963

I'm going to attempt to offer another (perhaps less contrived) example of a function which is reentrant, but not thread-safe.

Here is an implementation of the "Towers of Hanoi", using a shared global "temp" stack:

stack_t tmp;

void hanoi_inner(stack_t src, stack_t dest, stack_t tmp, int n)
{
   if (n == 1) move(src, dest)
   else {
     hanoi_inner(src, tmp, dest, n - 1);
     move(src, dest);
     hanoi_inner(tmp, dest, src, n - 1);
   }
}

void hanoi(stack_t src, stack_t dest, int n) { hanoi_inner(src, dest, tmp, n); }

The function hanoi() is reentrant because it leaves the state of the global buffer tmp unchanged when it returns (one caveat: the usual constraint of having an increasing size of discs on tmp may be violated during a reentrant call.) However hanoi() is not thread-safe.

Here is an example which is both thread-safe and reentrant if the increment operator n++ is atomic:

int buf[MAX_SIZE];  /* global, shared buffer structure */
int n;              /* global, shared counter */

int* alloc_int() { return &buf[n++]; }

You really could use this as an allocator for one-integer cells (doesn't check for overflow; I know). If n++ is not an atomic operation, two threads or two reentrant calls could easily end up being allocated the same cell.

Upvotes: 2

Secure
Secure

Reputation: 4368

The trick with this type of reentrancy is that the execution of the first call stops while the second call is executed. Just like a subfunction call. The first call continues after the second call completely finished. Because the function saves the state of t at entry and restores it at exit, nothing has changed for the first call when it continues. Therefore you always have a defined and strict order of execution, no matter where exactly the first call is interrupted.

When this function runs in multiple threads, all executions are done in parallel, even in true parallel with a multicore CPU. There is no defined order of execution over all threads, only within a single thread. So the value of t can be changed at any time by one of the other threads.

Upvotes: 10

Patrick Schlüter
Patrick Schlüter

Reputation: 11821

To give a more generic answer, reentrance is only at the function level. It means that one call of the function does not change a state on which can alter the functioning of a second call.

In the example given, the global variable is not changed between two calls of the function. What happens inside of the function has no influence on each call of the function.

An example of the a non reentrant function is strtok

It's for instance not possible to nest 2 parsing loops with it:

 /* To read a several lines of comma separated numbers */
 char buff[WHATEVER], *p1, *p2;

  p1 = strtok(buff, "\n");
  while(p1) {
    p2 = strtok(p1, ",");
    while(p2) {
      atoi(p2);
      p2 = strtok(NULL, ",");
      }
    }
    p1 = strtok(NULL, "\n");
  }

This doesn't work, because the state of the outer strtok loop is clobbered by the second call (one has to use the reentrant variant strtok_r).

Upvotes: 6

Scott Hunter
Scott Hunter

Reputation: 49805

If you had 2 instances (each on a different thread) executing it, one could step on the other's toes: if one got interrupted at the "hardware interrupt" comment, and another executed, it could change t, so that switching back to the first would have it produce incorrect results.

Upvotes: 1

David Grayson
David Grayson

Reputation: 87376

Thus function messes with a global variable named t for some bizarre reason. If this function gets called from two different threads at the same time, it's possible that you will get unexpected, incorrect results because one instance will overwrite the value in t that was written by the other instance.

Upvotes: 0

Related Questions