What Exactly Is a Reentrant Function

What exactly is a reentrant function?

1. How is safely defined?

Semantically. In this case, this is not a hard-defined term. It just mean "You can do that, without risk".

2. If a program can be safely executed concurrently, does it always mean that it is reentrant?

No.

For example, let's have a C++ function that takes both a lock, and a callback as a parameter:

#include <mutex>

typedef void (*callback)();
std::mutex m;

void foo(callback f)
{
    m.lock();
    // use the resource protected by the mutex

    if (f) {
        f();
    }

    // use the resource protected by the mutex
    m.unlock();
}

Another function could well need to lock the same mutex:

void bar()
{
    foo(nullptr);
}

At first sight, everything seems ok… But wait:

int main()
{
    foo(bar);
    return 0;
}

If the lock on mutex is not recursive, then here's what will happen, in the main thread:

main will call foo.
foo will acquire the lock.
foo will call bar, which will call foo.
the 2nd foo will try to acquire the lock, fail and wait for it to be released.
Deadlock.
Oops…

Ok, I cheated, using the callback thing. But it's easy to imagine more complex pieces of code having a similar effect.

3. What exactly is the common thread between the six points mentioned that I should keep in mind while checking my code for reentrant capabilities?

You can smell a problem if your function has/gives access to a modifiable persistent resource, or has/gives access to a function that smells.

(Ok, 99% of our code should smell, then… See last section to handle that…)

So, studying your code, one of those points should alert you:

The function has a state (i.e. access a global variable, or even a class member variable)
This function can be called by multiple threads, or could appear twice in the stack while the process is executing (i.e. the function could call itself, directly or indirectly). Function taking callbacks as parameters smell a lot.

Note that non-reentrancy is viral : A function that could call a possible non-reentrant function cannot be considered reentrant.

Note, too, that C++ methods smell because they have access to this, so you should study the code to be sure they have no funny interaction.

4.1. Are all recursive functions reentrant?

No.

In multithreaded cases, a recursive function accessing a shared resource could be called by multiple threads at the same moment, resulting in bad/corrupted data.

In singlethreaded cases, a recursive function could use a non-reentrant function (like the infamous strtok), or use global data without handling the fact the data is already in use. So your function is recursive because it calls itself directly or indirectly, but it can still be recursive-unsafe.

4.2. Are all thread-safe functions reentrant?

In the example above, I showed how an apparently threadsafe function was not reentrant. OK, I cheated because of the callback parameter. But then, there are multiple ways to deadlock a thread by having it acquire twice a non-recursive lock.

4.3. Are all recursive and thread-safe functions reentrant?

I would say "yes" if by "recursive" you mean "recursive-safe".

If you can guarantee that a function can be called simultaneously by multiple threads, and can call itself, directly or indirectly, without problems, then it is reentrant.

The problem is evaluating this guarantee… ^_^

5. Are the terms like reentrance and thread safety absolute at all, i.e. do they have fixed concrete definitions?

I believe they do, but then, evaluating a function is thread-safe or reentrant can be difficult. This is why I used the term smell above: You can find a function is not reentrant, but it could be difficult to be sure a complex piece of code is reentrant

6. An example

Let's say you have an object, with one method that needs to use a resource:

struct MyStruct
{
    P * p;

    void foo()
    {
        if (this->p == nullptr)
        {
            this->p = new P();
        }

        // lots of code, some using this->p

        if (this->p != nullptr)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

The first problem is that if somehow this function is called recursively (i.e. this function calls itself, directly or indirectly), the code will probably crash, because this->p will be deleted at the end of the last call, and still probably be used before the end of the first call.

Thus, this code is not recursive-safe.

We could use a reference counter to correct this:

struct MyStruct
{
    size_t c;
    P * p;

    void foo()
    {
        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        // lots of code, some using this->p
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

This way, the code becomes recursive-safe… But it is still not reentrant because of multithreading issues: We must be sure the modifications of c and of p will be done atomically, using a recursive mutex (not all mutexes are recursive):

#include <mutex>

struct MyStruct
{
    std::recursive_mutex m;
    size_t c;
    P * p;

    void foo()
    {
        m.lock();

        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        m.unlock();
        // lots of code, some using this->p
        m.lock();
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }

        m.unlock();
    }
};

And of course, this all assumes the lots of code is itself reentrant, including the use of p.

And the code above is not even remotely exception-safe, but this is another story… ^_^

7. Hey 99% of our code is not reentrant!

It is quite true for spaghetti code. But if you partition correctly your code, you will avoid reentrancy problems.

7.1. Make sure all functions have NO state

They must only use the parameters, their own local variables, other functions without state, and return copies of the data if they return at all.

7.2. Make sure your object is "recursive-safe"

An object method has access to this, so it shares a state with all the methods of the same instance of the object.

So, make sure the object can be used at one point in the stack (i.e. calling method A), and then, at another point (i.e. calling method B), without corrupting the whole object. Design your object to make sure that upon exiting a method, the object is stable and correct (no dangling pointers, no contradicting member variables, etc.).

7.3. Make sure all your objects are correctly encapsulated

No one else should have access to their internal data:

    // bad
    int & MyObject::getCounter()
    {
        return this->counter;
    }

    // good
    int MyObject::getCounter()
    {
        return this->counter;
    }

    // good, too
    void MyObject::getCounter(int & p_counter)
    {
        p_counter = this->counter;
    }

Even returning a const reference could be dangerous if the user retrieves the address of the data, as some other portion of the code could modify it without the code holding the const reference being told.

7.4. Make sure the user knows your object is not thread-safe

Thus, the user is responsible to use mutexes to use an object shared between threads.

The objects from the STL are designed to be not thread-safe (because of performance issues), and thus, if a user want to share a std::string between two threads, the user must protect its access with concurrency primitives;

7.5. Make sure your thread-safe code is recursive-safe

This means using recursive mutexes if you believe the same resource can be used twice by the same thread.

What is really re-entrant function?

Re-entrant means that the function can be interrupted at any point, and be able to correctly finish executing after the interruption, even in cases when the same function is called one or more times in the interrupted state.

The crucial part here is that the invocation of the function called in the interrupted state must finish before the original call state is restored. This is the main difference between re-entrancy and thread safety: in order to be thread-safe, a function must be able to proceed even if the interrupting invocation is unfinished before the control gets back to the original call.

That's why the second version of the swap is re-entrant: it always leaves t in an unchanged state upon exiting, so entering and exiting swap in the middle of an interrupted call will not alter the global state seen by the interrupted invocation.

Confusion regarding reentrant functions

The answer to your question:

that the main function calls the swap function, but then suddenly an interrupt occurs, then the output would surely get distorted as the swap wouldn't be proper, which in my mind makes this function non-reentrant.

Is no, it does not, because re-entrancy is (by definition) defined with respect to self. If isr calls swap, the other swap would be safe. However, swap is thread-unsafe, though.

The correct way of thinking depends on the precise definition of re-entrancy and thread-safety (See, say Threadsafe vs re-entrant)
Wikipedia, the source of the code in question, selected the definition of reentrant function to be "if it can be interrupted in the middle of its execution and then safely called again ("re-entered") before its previous invocations complete execution".

is this function reentrant?

Yes, this is a reentrant function. Reentrant functions are defined as those that can be called whilst they are themselves executing (either due to recursion, or concurrency). In this case, recursion is moot, and you are concurrently safe (assuming differing parameters).

Your argument is fine - there's no global or shared state being accessed either explicitly or implicitly, so reentrancy is ensured. This is a combination of both your explicit code and the semantics of C. Other languages and APIs may not have this property.

Edit: On double checking, the ISO C standard doesn't seem to force the thread safety of strlen. As such, there is a tiny possibility that you could be using a C standard library with a non-thread safe strlen and as such, inherit non-reentrancy from it.

Is this function re-entrant?

Yes.

From the tag excerpt of reentrancy:

A subroutine is considered reentrant if it can be safely called before a previous call has completed.

In your case, since the function only returns the address of a global (static) variable, which should remain constant after the program starts, the function is well re-entrant.

IMO, reentrant function can access global and static data, without changing any, so obtaining the address of a global variable isn't bad for a reentrant function.

What does reentrancy mean in JavaScript?

Reentrancy means the same in JS as in other languages: A routine is re-entered when it is called again while it is still running. It's called reentrant when it is safe to do so (where "safe" is a really broad term, usually meaning "everything works still as expected") - or more formally, the function still fulfills its contract when called in that manner.

There are a few scenarios where this is relevant in JS (where a function usually runs to completion without being "interrupted" by something else):

The function is asynchronous. Parts of the two calls might run interleaved with each other. If that interleaving happens in a way the developer didn't expect, it's called a race condition.
The function takes (and calls) a callback. The user-supplied callback might call the function again.
The function is a generator function. It is called multiple times and the generators are consumed alternately.

A function that uses only call-local state (or is completely pure) is always reentrant. Things get messy when your function modifies global state, and especially when it does break the invariants of your data structures "only during the function call".

Here's a simple example of a non-reentrant generator function:

var k = 0;
function* countTo(n) {
    while (k < n)
        yield k++;
    k = 0;
}
for (const x of countTo(3))
    console.log(x);
for (const y of countTo(7))
    console.log(y);

Works, right? No, it doesn't, as k is a global variable here. Just consider

for (const x of countTo(3))
    for (const y of countTo(7))
        console.log(x, y);

Oops. The same functionality written as a reentrant generator function:

function* countTo(n) {
    for (var k = 0; k < n; k++)
        yield k;
}

Reentrant Function

Note that do_something() can be called both from places where interrupts are enabled, and from places where interrupts are already disabled. Enabling interrupts on the second case goes against the expectations of the caller in a vary dangerous way.

What you really need is to save the previous state of interrupts while disabling them, and restore it afterwards.

So, a better version would be:

long i; 
void do_something(void){ 
    irq_state_t prev_int_state = disable_interrupts_save();
    i+=0x1234; 
    restore_interrupts(prev_int_state);
}

What Exactly Is a Reentrant Function