Editing Reentrancy (computing)

{{short description|Concept in computer programming}}
{{Use dmy dates|date=March 2020|cs1-dates=y}}

'''Reentrancy''' is a programming concept where a function or subroutine can be interrupted and then resumed before it finishes executing. This means that the function can be called again before it completes its previous execution. Reentrant code is designed to be safe and predictable when multiple instances of the same function are called simultaneously or in quick succession. A [[computer program]] or [[subroutine]] is called reentrant if multiple invocations can safely run [[Concurrent computing|concurrently]] on [[Multiprocessing|multiple processors]], or if on a [[Uniprocessor system|single-processor system]] its [[Execution (computing)|execution]] can be [[interrupt]]ed and a new execution of it can be safely started (it can be "re-entered"). The interruption could be caused by an internal action such as a [[Branch (computer science)|jump]] or call (which might be a [[Recursion (computer science)|recursive]] call; reentering a function is a generalization of recursion), or by an external action such as an interrupt or [[signal (computing)|signal]]. 

This definition originates from [[multiprogramming]] environments, where multiple processes may be active concurrently and where the flow of control could be interrupted by an interrupt and transferred to an [[interrupt service routine]] (ISR) or "handler" subroutine. Any subroutine used by the handler that could potentially have been executing when the interrupt was triggered should be reentrant. Similarly, code shared by two processors accessing shared data should be reentrant. Often, subroutines accessible via the operating system [[kernel (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 [[Memory management|allocating memory]].

Reentrancy is neither necessary nor sufficient for [[thread-safety]] in multi-threaded environments. In other words, a reentrant subroutine can be thread-safe,{{sfn|Kerrisk|2010|p=[https://books.google.com/books?id=2SAQAQAAQBAJ&pg=PA657 657]}} but is not guaranteed to be.<ref>{{cite web |title=Writing reentrant and threadsafe code |url=https://www.ibm.com/docs/en/aix/7.2.0?topic=programming-writing-reentrant-threadsafe-code |website=Programming for AIX |publisher=IBM |access-date=12 May 2025}}</ref> Conversely, thread-safe code need not be reentrant (see below for examples).

Other terms used for reentrant programs include "sharable code".{{sfn|Ralston|2000|p=1514–1515}} Reentrant subroutines are sometimes marked in reference material as being "signal safe".<ref>{{cite web |title=pthread_cond_init()--Initialize Condition Variable |url=https://www.ibm.com/support/knowledgecenter/en/ssw_ibm_i_74/apis/users_75.htm |website=IBM Knowledge Center |access-date=5 October 2019}}</ref> Reentrant programs are often{{efn|A program that serializes self-modification may be reentrant, and a pure procedure that updates global data without proper serialization may fail to be reentrant.}} "pure procedures".

==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 any function at any time. If data can be changed by any function (and none keep track of those changes), there is no guarantee to those that share a datum that that datum is the same as at any time before.

Data has a characteristic called [[Scope and extent|scope]], which describes where in a program the data may be used. Data scope is either [[global variable|global]] (outside the [[variable scope|scope]] of any function and with an indefinite extent) or [[Local variables, recursion and reentrancy|local]] (created each time a function is called and destroyed upon exit).

Local data is not shared by any routines, re-entering or not; therefore, it does not affect re-entrance. Global data is defined outside functions and can be accessed by more than one function, either in the form of [[global variable]]s (data shared between all functions), or as [[static variable]]s (data shared by all invocations of the same function). 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 variable]]s, 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 were 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  without [[Synchronization (computer science)|synchronization]].
: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, except in sections of code that are [[Synchronization (computer science)|synchronized]], only [[atomic (computer science)|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). Note that in C, even a read or write is not guaranteed to be atomic; it may be split into several reads or writes.{{r|Preshing (2013)}} The C standard and SUSv3 provide <code>sig_atomic_t</code> for this purpose, although with guarantees only for simple reads and writes, not for incrementing or decrementing.{{sfn|Kerrisk|2010|p=[https://books.google.com/books?id=2SAQAQAAQBAJ&pg=PA428 428]}} More complex atomic operations are available in [[C11 (C standard revision)|C11]], which provides <code>stdatomic.h</code>.
;Reentrant code may not [[self-modifying code|modify itself]] without synchronization.
:The operating system might allow a process to modify its code. There are various reasons for this (e.g., [[blitting]] graphics quickly) but this generally requires synchronization to avoid problems with reentrancy.<!--
 --><p>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).</p>
;Reentrant code may not call non-reentrant [[computer program]]s or [[Subroutine|routines]] without synchronization.
:Multiple levels of user, object, or process [[Priority queue|priority]] or [[multiprocessing]] usually complicate the control of reentrant code. It is important to keep track of any access or side effects that are done inside a routine designed to be reentrant.

Reentrancy of a subroutine that operates on operating-system resources or non-local data depends on the [[atomicity (programming)|atomicity]] of the respective operations. For example, if the 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 while executing, and called again from the interrupt handler, the global variable may be in a state where only 32 bits have been updated. The programming language might provide atomicity guarantees for interruption caused by an internal action such as a jump or call. Then the function {{code|f}} in an expression like <code>(global:=1) + (f())</code>, where the order of evaluation of the subexpressions might be arbitrary in a programming language, would see the global variable either set to 1 or to its previous value, but not in an intermediate state where only part has been updated. (The latter can happen in [[C (programming language)|C]], because the expression has no [[sequence point]].) The operating system might provide atomicity guarantees for [[signal (computing)|signals]], such as a system call interrupted by a signal not having a partial effect. The processor hardware might provide atomicity guarantees for [[interrupt]]s, such as interrupted processor instructions not having partial effects.

==Examples==
To illustrate reentrancy, this article uses as an example a [[C (programming language)|C]] utility function, {{code|swap()}}, that takes two pointers and transposes their values, and an interrupt-handling routine that also calls the swap function.

===Neither reentrant nor thread-safe===
This is an example swap function that fails to be reentrant or thread-safe. Since the <code>tmp</code> variable is globally shared, without synchronization, among any concurrent instances of the function, one instance may interfere with the data relied upon by another. As such, it should not have been used in the interrupt service routine <code>isr()</code>:

<syntaxhighlight lang="c">
int tmp;

void swap(int* x, int* y)
{
    tmp = *x;
    *x = *y;
    /* Hardware interrupt might invoke isr() here. */
    *y = tmp;    
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}
</syntaxhighlight>

===Thread-safe but not reentrant===
The function {{code|swap()}} in the preceding example can be made thread-safe by making {{code|tmp}} [[Thread-local storage|thread-local]]. It still fails to be reentrant, and this will continue to cause problems if {{code|isr()}} is called in the same context as a thread already executing {{code|swap()}}:

<syntaxhighlight lang="c">
_Thread_local int tmp;

void swap(int* x, int* y)
{
    tmp = *x;
    *x = *y;
    /* Hardware interrupt might invoke isr() here. */
    *y = tmp;    
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}
</syntaxhighlight>

===Reentrant and thread-safe===
An implementation of {{code|swap()}} that allocates {{code|tmp}} on the [[call stack|stack]] instead of globally and that is called only with unshared variables as parameters{{efn|If isr() called swap() with one or two global variables as parameters then swap() would not be reentrant}} is both thread-safe and reentrant. Thread-safe because the stack is local to a thread and a function acting just on local data will always produce the expected result. There is no access to shared data therefore no data race.

<syntaxhighlight lang="c">
void swap(int* x, int* y)
{
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;    /* Hardware interrupt might invoke isr() here. */
}

void isr()
{
    int x = 1, y = 2;
    swap(&x, &y);
}
</syntaxhighlight>

==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]].{{sfn|Sloss|Symes|Wright|Rayfield|2004|p=[https://books.google.com/books?id=vdk4ZGRqMskC&pg=PA342 342]}} 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.{{r|Regehr (2006)}}

==Further examples==
In the following code, neither <code>f</code> nor <code>g</code> functions is reentrant.

<syntaxhighlight lang="c">
int v = 1;

int f()
{
    v += 2;
    return v;
}

int g()
{
    return f() + 2;
}
</syntaxhighlight>

In the above, {{code|f()}} depends on a non-constant global variable {{code|v}}; thus, if {{code|f()}} is interrupted during execution by an ISR which modifies {{code|v}}, then reentry into {{code|f()}} will return the wrong value of {{code|v}}. The value of {{code|v}} and, therefore, the return value of {{code|f}}, cannot be predicted with confidence: they will vary depending on whether an interrupt modified {{code|v}} during {{code|f}}'s execution. Hence, {{code|f}} is not reentrant. Neither is {{code|g}}, because it calls {{code|f}}, which is not reentrant.

These slightly altered versions ''are'' reentrant:

<syntaxhighlight lang="c">
int f(int i)
{
    return i + 2;
}

int g(int i)
{
    return f(i) + 2;
}
</syntaxhighlight>

In the following, the function is thread-safe, but not (necessarily) reentrant:

<syntaxhighlight lang="c">
int function()
{
    mutex_lock();

    // ...
    // function body
    // ...

    mutex_unlock();
}
</syntaxhighlight>

In the above, {{code|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.

==Notes==
{{Notelist}}

==See also==
* [[Referential transparency]]

==References==
{{reflist|refs=
<ref name="Preshing (2013)">
  {{cite web
  |last = Preshing
  |first = Jeff
  |title = Atomic vs. Non-Atomic Operations
  |date = June 18, 2013
  |website = Preshing on Programming
  |url = http://preshing.com/20130618/atomic-vs-non-atomic-operations/
  |access-date = April 24, 2018
  |archive-url = https://archive.today/20141203145131/http://preshing.com/20130618/atomic-vs-non-atomic-operations/
  |archive-date = December 3, 2014
  |url-status = live
  }}
</ref>
<ref name="Regehr (2006)">
{{cite encyclopedia
  |last = Regehr
  |first = John
  |author-link = John Regehr
  |title = Safe and Structured Use of Interrupts in Real-time and Embedded Software
  |encyclopedia = Handbook of Real-Time and Embedded Systems
  |publisher = [[CRC Press]]
  |date = 2006
  |url = http://www.cs.utah.edu/~regehr/papers/interrupt_chapter.pdf
  |via = the author's website at the University of Utah School of Computing
  |archive-url = https://web.archive.org/web/20070824025205/http://www.cs.utah.edu/~regehr/papers/interrupt_chapter.pdf
  |archive-date = August 24, 2007
  |url-status = live
  }}
</ref>
<!-- <ref name="Barron_1968_Recursive">{{cite book |author-first=David William |author-last=Barron |author-link=David W. Barron |editor-first=Stanley |editor-last=Gill |editor-link=Stanley Gill |title=Recursive techniques in programming |url=https://archive.org/details/recursivetechniq00barr_223 |url-access=limited |chapter=3.2. Ad Hoc Methods |series=Macdonald Computer Monographs |date=1968 |orig-year=1967 |edition=1 |publisher=[[Macdonald & Co. (Publishers) Ltd.]] |publication-place=London, UK |location=Cambridge, UK |sbn=356-02201-3 |page=[https://archive.org/details/recursivetechniq00barr_223/page/n40 35]}} (viii+64 pages)</ref> --><!-- This is only relevant for recursion, not for reentrancy. -->
}}

===Works cited===
{{refbegin}}
* {{cite book
  |last = Kerrisk
  |first = Michael
  |author-link = Michael Kerrisk
  |title = The Linux Programming Interface
  |title-link = The Linux Programming Interface
  |publisher = [[No Starch Press]]
  |date = 2010
  }}
* {{cite encyclopedia
  |editor-last = Ralston
  |editor-first = Anthony
  |title = Reentrant Program
  |encyclopedia = Encyclopedia of Computer Science
  |edition = 4th
  |publisher = [[Nature Publishing Group]]
  |date = 2000
  }}
* {{cite book
  |last1 = Sloss
  |first1 = Andrew N.
  |last2 = Symes
  |first2 = Dominic
  |last3 = Wright
  |first3 = Chris
  |author-link3 = Chris Wright (programmer)
  |last4 = Rayfield
  |first4 = John
  |title = ARM System Developer's Guide
  |publisher = Morgan Kaufmann Publishers
  |date = 2004
  |isbn = 9780080490496
 |url = https://books.google.com/books?id=vdk4ZGRqMskC
  }}
{{refend}}

==Further reading==
{{refbegin|}}
* {{cite web|last=Chen|first=Raymond|author-link=Raymond Chen (Microsoft)|title=The Difference Between Thread-safety and Re-entrancy|date=June 29, 2004|work=The Old New Thing|publisher=[[Microsoft Developer Network]]|url=https://devblogs.microsoft.com/oldnewthing/20040629-00/?p=38643|access-date=April 24, 2018|archive-url=https://archive.today/20180424132803/https://blogs.msdn.microsoft.com/oldnewthing/20040629-00/?p=38643|archive-date=April 24, 2018|url-status=live}}
* {{cite web|last=Ganssle|first=Jack|title=Introduction to Reentrancy|date=March 15, 2001|website=[[Embedded.com]]|url=https://www.embedded.com/electronics-blogs/beginner-s-corner/4023308/Introduction-to-Reentrancy|access-date=April 24, 2018|archive-url=https://archive.today/20130121232653/http://www.embedded.com/electronics-blogs/beginner-s-corner/4023308/Introduction-to-Reentrancy|archive-date=January 21, 2013|url-status=live}}
* {{cite encyclopedia
  |author = IBM
  |title = General Programming Concepts
  |encyclopedia = AIX Version 7.2 Manual
  |date = 2018
  |pages = 636–641
  |url = http://public.dhe.ibm.com/systems/power/docs/aix/72/genprogc_pdf.pdf#page=646
  |format = PDF
  <!-- Available as HTML at: https://www.ibm.com/support/knowledgecenter/en/ssw_aix_72/com.ibm.aix.genprogc/writing_reentrant_thread_safe_code.htm -->
  |access-date = April 24, 2018
  }}
* {{cite web|last=Jha|first=Dipak|title=Use Reentrant Functions for Safer Signal Handling|date=January 20, 2005|website=IBM DeveloperWorks|url=https://www.ibm.com/developerworks/library/l-reent/|access-date=April 24, 2018|archive-url=https://archive.today/20140707081013/http://www.ibm.com/developerworks/library/l-reent/|archive-date=July 7, 2014|url-status=live}}
{{refend}}

[[Category:Concurrency (computer science)]]
[[Category:Recursion]]
[[Category:Subroutines]]
[[Category:Articles with example C code]]