Reentrancy (computing)

In computing, a computer program or subroutine is called reentrant if it can be interrupted in the middle of its execution and then safely called again ("re-entered") before its previous invocations complete executing. The interruption could be caused by an internal action such as a jump or call or by an external action such as a hardware interrupt or signal. Once the reentered invocation completes, the previous invocations will resume correct execution.

This definition originates from single-threaded programming environments where the flow of control could be interrupted by a hardware interrupt and transferred to an interrupt service routine (ISR). Any subroutine used by the ISR that could potentially have been executing when the interrupt was triggered should be reentrant. Often, subroutines accessible via the operating system kernel are in fact not reentrant. Hence, interrupt service routines are limited in the actions they can perform and usually restricted from accessing the file system or even from allocating memory.

A subroutine that is directly or indirectly recursive should be reentrant. This policy is partially enforced by structured programming languages. However a subroutine can fail to be reentrant if it relies on a global variable to remain unchanged but that variable is modified when the subroutine is recursively invoked.

The definition of reentrancy originated in single-threaded environments and differs from that of thread-safety in multi-threaded environments. A reentrant subroutine can achieve thread-safety, but this condition alone might not be sufficient in all situations. Conversely, thread-safe code does not necessarily have to be reentrant (see below for examples).

Example

This is an example of a swap() function which fails to be reentrant (as well as thread-safe). As such, it should not have been used in the interrupt service routine isr():

int t;
 
void swap(int *x, int *y)
{
        t = *x;
        *x = *y;
        // hardware interrupt might invoke isr() here!
        *y = t;
}
 
void isr()
{
        int x = 1, y = 2;
        swap(&x, &y);
}

swap() could be made thread-safe by making t thread-local. It still fails to be reentrant and this will continue to cause problems if isr() is called in the same context as a thread already executing swap().

The following, somewhat contrived, modification of the swap function, which is careful to leave the global data in a consistent state at the time it exits, 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);
}

Derivation and explanation of rules

Reentrancy is not the same thing as idempotence (meaning that the function may be called more than once, yet generate exactly the same output as if it had only been called once). Generally speaking, a function produces output data based on some input data (though both are optional, in general). Shared data could be accessed by anybody at any time. If data can be changed by anybody (and nobody keeps track of those changes) then there's no guarantee for those who share a datum whether that datum is the same as at any time before. Idempotence implies reentrancy, but the converse is not necessarily true.

Data are of global (outside the scope of any function and with an indefinite extent) or local (created each time a function is called and destroyed upon exit) scope.

Local data are not shared by any, re-entering or not, routines; therefore they don't affect re-entrance. Global data are either shared by any function, called global variables, or shared by all functions of the same name, called static variables; therefore they can affect it.

• Must hold no static (or global) non-constant data.

Reentrant functions can use global data to work with. For example, a reentrant interrupt service routine could grab a piece of hardware status to work with (e.g. serial port read buffer) which is not only global, but volatile. Still typical use of static variables and global data is not advised, in the sense of no non-atomic-read-modify-write instructions should be used in these variables

• Must not modify its own code.

The operating system might allow a process to modify its code. There are various reasons for this (blitting graphics quickly, ignorance of OS programmers) but the fact is that code might not be the same next time. It may modify itself if it resides in its own unique memory. That is, if each new invocation uses a different physical machine code location where a copy of the original code is made, it will not affect other invocations even if it then modifies itself during execution of that particular thread).

• Must not call non-reentrant computer programs or routines.

Multiple levels of 'user/object/process priority' and/or multiprocessing usually complicate the control of reentrant code. It is important to keep track of any access and or side effects that are done inside a routine designed to be reentrant.

Reentrancy is a key feature of functional programming.

Any recursive subroutines need to be reentrant.

Also, subroutines that are directly or indirectly called from an interrupt handler must to be reentrant if there is need to service an interrupt before the previous is already served.

Reentrant interrupt handler

A "reentrant interrupt handler" is an interrupt handler that re-enables interrupts early in the interrupt handler. This may reduce interrupt latency. In general, while programming interrupt service routines, it is recommended to re-enable interrupts as soon as possible in the interrupt handler. This helps to avoid losing interrupts.

Examples

In the following piece of C code, neither functions f nor g are reentrant.

int g_var = 1;
 
int f()
{
        g_var = g_var + 2;
        return g_var;
}
 
int g()
{
        return f() + 2;
}

In the above, f depends on a non-constant global variable g_var; thus, if two threads execute it and access g_var concurrently, then the result varies depending on the timing of the execution. Hence, f is not reentrant. Neither is g; it calls f, which is not reentrant.

These slightly altered versions are reentrant:

int f(int i)
{
        return i + 2;
}
 
int g(int i)
{
        return f(i) + 2;
}

In the following piece of C code, the function is thread-safe, but not reentrant

int function()
{
        mutex_lock();
        ...
        function body
        ...
        mutex_unlock();
}

In the above, function can be called by different threads without any problem. But if the function is used in a reentrant interrupt handler and a second interrupt arises inside the function, the second routine will hang forever. As interrupt servicing can disable other interrupts, the whole system could suffer.

Relation to thread safety

This concept is distinct from, but closely related to, thread-safe. A function can be thread-safe and still not reentrant. For example, a function could be wrapped all around with a mutex (which avoids problems in multithreading environments), and if that function is used as a reentrant function in an interrupt service routine, it could starve waiting for the first execution to release the mutex. 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.

See also

• Referential transparency

References

• Kerrisk, Michael (2010). The Linux Programming Interface. No Starch Press. 

External links

• Article "Use reentrant functions for safer signal handling" by Dipak K Jha
• "Writing Reentrant and Thread-Safe Code," from AIX Version 4.3 General Programming Concepts: Writing and Debugging Programs, 2nd edition, 1999.
• Jack Ganssle (2001). "Introduction to Reentrancy". EE Times.
• Raymond Chen (2004). The difference between thread-safety and re-entrancy. The Old New Thing.