Lecture
A computer program as a whole, or one of its individual procedures, is called reentrant if it is designed in such a way that the same copy of the program's instructions in memory can be shared among several users or processes. In this case a second user may invoke the reentrant code before the first user has finished with it, and this must, at the very least, not lead to an error, while with a correct implementation it must not cause any loss of computation (that is, there must be no need to re-execute fragments of code that have already been executed).
Reentrancy is closely related to the safety of a function in a multithreaded environment (thread-safety); nevertheless, these are different concepts. Ensuring reentrancy is a key point when programming multitasking systems, in particular operating systems.
To ensure reentrancy, several conditions must be met:
In the general case, to ensure reentrancy the calling process or function must pass all the necessary data to the invoked process each time. Thus, a function that depends only on its parameters, does not use global and static variables, and calls only reentrant functions will be reentrant. If a function uses global or static variables, it is necessary to ensure that each user keeps its own local copy of these variables.
In the following code fragment, the functions f() and g() are not reentrant.
int g_var = 1;
int f ()
{
g_var = g_var + 2;
return g_var;
}
int g ()
{
return f () + 2;
}
Here f() depends on the global variable g_var, so if two processes call f() at the same time, the result is unpredictable. Therefore, f() is not reentrant. But g() is not reentrant either, since it uses the non-reentrant function f().
In the following code fragment, the function accum() is also not reentrant.
int accum(int b)
{
static int a = 0;
++a;
return (a+b);
}
Here accum is a function that accumulates the value a, which is held by a static variable. If accum is called by different processes, the result will likewise be unpredictable. As in the previous example, a is shared by all the processes that call it.
A loss of reentrancy can also occur when the same variable is used more than once in an expression.
#define SQR(x) ((x)*(x))
void func (void)
{
int x, y;
x = SQR (y);
}
In this case the macro SQR(x) will work incorrectly if the argument changes on each reference to it.
Reentrancy is not the same thing as idempotency, in which a function may be called more than once yet generate exactly the same result as if it had been called only once. Generally speaking, a function produces output data based on some input data (although both are usually optional). Shared data can be accessed by any function at any time. If the data can be modified by any function (and none of them tracks these changes), then for those sharing the data there is no guarantee that this data is the same as it was at any prior time.
Data has a characteristic called scope, which describes where in the program the data can be used. The scope of data can be global (outside the scope of any function and of indefinite extent) or local (created each time a function is called and destroyed on exit).
Local data is not used by any procedures, whether they are reentered or not; consequently, it does not affect reentrancy. Global data is defined outside functions and can be accessed by more than one function, either in the form of global variables (data shared by all functions) or as static variables (data shared by all functions with the same name). In object-oriented programming, global data is defined within the scope of a class and can be private, which makes it accessible only to the functions of that class. There is also the concept of instance variables, where a class variable is bound to an instance of the class. For these reasons, in object-oriented programming this distinction is usually reserved for data accessible outside the class (public) and for data that is independent of class instances (static).
Reentrancy differs from thread safety, but is closely related to it. A function can be thread-safe and yet not reentrant. For example, a function may be wrapped around a mutex (which avoids problems in multithreaded environments), but if this function were used in an interrupt service routine it could starve while waiting for the first execution to release the mutex. The key to avoiding confusion is that reentrancy refers to the execution of only one thread. It is a concept from the days when multitasking operating systems did not yet exist.
Reentrant code may not contain static or global non-constant data.
Reentrant functions may work with global data. For example, a reentrant interrupt service routine may capture part of the hardware state to work with (for instance, a serial port read buffer), which is not only global but also volatile. Nevertheless, the typical use of static variables and global data is not recommended, in the sense that only atomic read-modify-write instructions should be used on these variables (an interrupt or signal must not arrive during the execution of such an instruction). Note that in C even a read or a write is not guaranteed to be atomic; it may be split into several reads or writes. The C standard and SUSv3 provide sig_atomic_t for this purpose, although with guarantees only for simple reads and writes, and not for increment or decrement. More complex atomic operations are available in C11, which provides stdatomic.h.
Reentrant code may not modify itself.
An operating system may allow a process to modify its own code. There are various reasons for this (for example, fast graphics copying), but it can cause reentrancy problems, since the code may be different the next time.
However, it may be modified if it resides in its own unique memory. That is, if each new call uses a different location of physical machine code in which a copy of the original code is created, it will not affect other calls even if it changes during the execution of that particular call (thread).
Reentrant code may not call non-reentrant computer programs or subroutines.
Multiple levels of user, object, or process priority, or of multiprocessing, usually complicate the management of reentrant code. It is important to track any access or side effects that occur within a procedure intended for reentrancy.
The reentrancy of a subroutine that operates on operating system resources or non-local data depends on the atomicity of the corresponding operations. For example, if a subroutine modifies a 64-bit global variable on a 32-bit machine, the operation may be split into two 32-bit operations, and thus, if the subroutine is interrupted during execution and called again from an interrupt handler, the global variable may be in a state in which only 32 bits have been updated. A programming language may provide atomicity guarantees for an interrupt caused by an internal action, such as a jump or a call. Then the function f in an expression such as (global:=1) + (f()), where the order of evaluation of the subexpressions may be arbitrary in the programming language, the global variable will either be set to 1 or to its previous value, but not to an intermediate state in which only part of it has been updated. (The latter may happen in C, because the expression has no sequence point.) An operating system may provide atomicity guarantees for signals, such as a system call interrupted by a signal having no partial effect. Processor hardware may provide atomicity guarantees for interrupts, such as interrupted processor instructions having no partial effects.
To illustrate reentrancy, this article uses as an example a C utility function, swap(), which takes two pointers and swaps their values, together with an interrupt handling routine that also calls the swap function.
This is an example of a swap function that can be neither reentrant nor thread-safe. Because the tmp variable is used globally, without serialization, among any concurrent instances of the function, one instance can interfere with the data another relies on. Thus, it should not have been used in the interrupt service routine isr():
int tmp ;
void swap( int * x , int * y )
{
tmp = * x ;
* x = * y ;
/* A hardware interrupt may invoke isr() here. */
* y = tmp ;
}
void isr ()
{
int x = 1 , y = 2 ;
swap( & x , & y );
}
The swap() function in the previous example can be made thread-safe by making tmp thread-local. It still cannot be reentrant, and this will continue to cause problems if isr() is called in the same context as an already executing swap() thread:
_Thread_local int tmp ;
void swap( int * x , int * y )
{
tmp = * x ;
* x = * y ;
/* A hardware interrupt may invoke isr() here. */
* y = tmp ;
}
void isr ()
{
int x = 1 , y = 2 ;
swap( & x , & y );
}
The following (somewhat contrived) modification of the swap function, which takes care that the global data remains in a consistent state at the moment of exit, is reentrant; however, it is not thread-safe, because no locks are used and it can be interrupted at any moment:
int tmp ;
void swap ( int * x , int * y )
{
/* Save the global variable. */
int s ;
s = tmp ;
tmp = * x ;
* x = * y ; /* If a hardware interrupt occurs here, it will not be able to save the value of tmp. So this is not a reentrant example either. */
* y = tmp ; /* A hardware interrupt may invoke isr() here. */
/* Restore the global variable. */
tmp = s ;
}
void isr ()
{
int x = 1 , y = 2 ;
swap( & x , & y );
}
This implementation of swap() allocates tmp on the stack rather than globally and is called only with unshared variables as parameters, [a] and is at the same time thread-safe and reentrant. Thread-safe, because the stack is local to the thread, and a function that operates only on local data will always give the expected result. There is no access to shared data, so there is no data race.
void swap ( int * x , int * y )
{
int tmp ;
tmp = * x ;
* x = * y ;
* y = tmp ; /* A hardware interrupt may invoke isr() here. */
}
void isr ()
{
int x = 1 , y = 2 ;
swap( & x , & y );
}
A reentrant interrupt handler is an interrupt handler that re-enables interrupts early in the interrupt handler. This can reduce interrupt latency. In general, when programming interrupt service routines, it is recommended to re-enable interrupts in the interrupt handler as soon as possible. This practice helps to avoid losing interrupts.
In the following code, neither the f nor the g functions are reentrant.
int v = 1 ;
int f ()
{
v += 2 ;
return v ;
}
int g ()
{
return f () + 2 ;
}
In the example above, f() depends on the non-constant global variable v; thus, if f() execution is interrupted during the run of an ISR that modifies v, then reentering f() will return an incorrect value of v. The value of v, and therefore the return value of f, cannot be predicted with certainty: they will vary depending on whether the interrupt modified v during the execution of f. Consequently, f is not reentrant. Nor is g, because it calls f, which is not reentrant.
These slightly modified versions are reentrant:
int f ( int i )
{
return i + 2 ;
}
int g ( int i )
{
return f ( i ) + 2 ;
}
Next, the function is thread-safe but not reentrant:
int function ()
{
mutex_lock ();
// ...
// function body
// ...
mutex_unlock ();
}
In the example above, function() can be called by different threads without problems. But if the function is used in a reentrant interrupt handler and a second interrupt occurs inside the function, the second routine will hang forever. Since interrupt service may disable other interrupts, the whole system may suffer.
Comments