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 execution. 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 not reentrant. Hence, interrupt service routines are limited in the actions they can perform; for instance, they are usually restricted from accessing the file system and sometimes 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.

This definition of reentrancy differs from that of thread-safety in multi-threaded environments. A reentrant subroutine can achieve thread-safety,[1] but being reentrant alone might not be sufficient to be thread-safe in all situations. Conversely, thread-safe code does not necessarily have to be reentrant (see below for examples).

Other terms used for reentrant programs include "pure procedure" or "sharable code".[2]

Example

This is an example of a swap() function that fails to be reentrant (as well as failing to be 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 ; however, it is not thread-safe since 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);
}

Background

Reentrancy is not the same thing as idempotence, in which 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 is no guarantee for those who share a datum whether that datum is the same as at any time before.

Data has a characteristic called a scope, which describes where in a program the data may be used. Data scope is either 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).

Local data is not shared by any, re-entering or not, routines; therefore, they do not affect re-entrance. Global data is defined outside functions, and can be accessed by more than one function, either in form of global variables (data shared between all functions), or as static variables (data shared by all functions of the same name). In object-oriented programming, global data is defined in the scope of a class and can be private, making it accessible only to functions of that class. There is also the concept of instance variables, where a class variable is bound to a class instance. For these reasons, in object-oriented programming this distinction is usually reserved for the data accessible outside of the class (public), and for the data independent of class instances (static).

Reentrancy is distinct from, but closely related to, thread-safety. 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), but if that function is used 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.

Rules for reentrancy

Reentrant code may not hold any static (or global) non-constant data.
Reentrant functions can work with global data. 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 that only atomic read-modify-write instructions should be used in these variables (it should not be possible for an interrupt or signal to come during the execution of such an instruction).
Reentrant code may not modify its own code.
The operating system might allow a process to modify its code. There are various reasons for this (e.g., blitting graphics quickly) but this would cause a problem with reentrancy, since the code might not be the same next time.
It may, however, 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 modifies itself during execution of that particular invocation (thread).
Reentrant code may 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.

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.[3] In general, while programming interrupt service routines, it is recommended to re-enable interrupts as soon as possible in the interrupt handler. This practice helps to avoid losing interrupts.[4]

Further examples

In the following piece of C code, neither f nor g functions 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.

See also

References

  1. ↑ Kerrisk 2010, p. 657.
  2. ↑ Ralston, Anthony, ed. (2000). "Reentrant program". Encyclopedia of Computer Science. Fourth edition. Nature publishing group. pp. 1514–1515.
  3. ↑ Andrew N. Sloss, Dominic Symes, Chris Wright, John Rayfield (2004). ARM System Developer's Guide. p. 342.
  4. ↑ John Regehr (2006). Safe and structured use of interrupts in real-time and embedded software (PDF).

Further reading

External links

This article is issued from Wikipedia - version of the Wednesday, April 20, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.