Talk:Reentrancy (computing)

Definition of "reentrant"

This definition is way too narrow. Wouter Lievens 09:46, 8 Apr 2005 (UTC)

Then what definition you think is more appropriate? -- Taku 20:50, Apr 8, 2005 (UTC)

I know the term is used outside of the context of concurrency, but I can't exactly say how and where :-) Wouter Lievens 15:44, 26 May 2005 (UTC)

Would be better if "can be called SAFELY" is explained in more detail. —Preceding unsigned comment added by T pradeepkumar (talk • contribs)

Narrow, wrong, without purpose, and not consistent with any usual definition (there are several incompatible ones).KiloByte (talk) 15:22, 26 November 2010 (UTC)

The mention of FreeBSD's VFS is relevant, however the follow up about DragonFlyBSD seems to me to be off-topic. —Preceding unsigned comment added by 62.253.64.17 (talk • contribs)

I don't think recursion is correct in this context. A function can be re-entered from more than one thread without being called recursively. Recursive implies the function calls itself. Peter Ritchie 19:48, 5 October 2006 (UTC)

"Recursive" may also mean that a function invokes a callback, which may re-call the function recursively without corruption or unexpected effects. Or when a function is temporarily interrupted by a signal, and the signal handler calls the function again within the context of the same thread. -- intgr 14:08, 10 November 2006 (UTC)

"Recursive" does in no case mean that "a function invokes a callback, which may re-call the function" or "when a function is temporarily interrupted by a signal, and the signal handler calls the function again within the context of the same thread". "Recursive" means that a function is defined (and relies) on the "output" of an anterior call to itself.

Indeed the cases where "a function invokes a callback, which may re-call the function" or "when a function is temporarily interrupted by a signal, and the signal handler calls the function again within the context of the same thread" are very good examples for the concept of reentrancy. Thus, in my opinion the term "recursive(ly)" should be removed entirely from this article. DvG 14:35, 13 August 2007 (UTC)

agree; removed it. it's not hard to imagine pathological situations where non-reentrant functions could still be used correctly and recursively by design. 12.219.83.157 06:08, 16 September 2007 (UTC)

Reentrancy is also an embedded systems development concern, but at a much lower level that does appeared to be addressed here. With respect to embedded systems reentrancy is at the assembly language level and is concerned with interrupts and there effects on the task and processes of the system when returning from an interrupt and the assmbly language genertaied by the complier/assembler pair (and linker). Just thought you should know this subject as presented here seems narrow. thanks EM1SS&CSE 18:08, 18 October 2007 (UTC)

Shouldn't it be "multiple threads" instead of "multiple processes"?

processes/threads are both orthogonal as the signal handler example above shows. a single-threaded task can still have re-entrancy bugs if it relies on interrupts. 12.219.83.157 06:15, 16 September 2007 (UTC)

Incorrect claim "Idempotence implies reentrancy, but the contrary is not necessary true."

Here is a function which is idempotent but not reentrant:

int global;
int f(int * i)
{
  global++;
  *i = global;
  global--;
}

Or am I misunderstanding something? —Preceding unsigned comment added by 199.172.169.86 (talk) 10:15, 25 February 2011 (UTC)

I believe you're correct. That seemed odd to me too. I've removed the claim. spikey (talk) 16:05, 15 April 2014 (UTC)

Functional programming

I don't know very much about functional programming, but aren't functional programming languages reentrant (variables and functions, and even syntax (in Scheme for example) ? —Preceding unsigned comment added by 83.214.221.148 (talk • contribs)

I don't know about Scheme, but I would say that purely functional languages like Haskell are inherently reentrant (except for the IO monad). --Pezezin 22:57, 19 March 2007 (UTC)

This article is inaccurate. Someone more generous than I should get out an OS textbook and revise it. JBW012307

The lisp dialects are re-entrant they just don't seem to have a need to call it other than recursion :). W/re the usage of re-entrant as presented here, isn't Scheme's call/cc an example of what is being discussed? If so, I don't understand why there is an implicit suggestion that re-entrant subrs are directly correlated with thread safety and `concurrency' issues i.e. w/ call/cc the stack is elsewhere thread or no.Lambda-mon key (talk) 01:05, 5 March 2010 (UTC)

Serially Reentrant

Back in the day, I remember the concept of serially reentrant. A subroutine was serially reentrant even though it manipulated global variables because a semaphore guaranteed at most one thread was actively executing in the subroutine at a given time. The global variables had to be protected by the semaphore in order for this work properly. Static local variables (those not allocated in a stack frame or from a heap) would similarly be protected. —Preceding unsigned comment added by 70.108.186.46 (talk • contribs)

sure sounds like plain old thread-safety to me. 12.219.83.157 06:09, 16 September 2007 (UTC)

Semaphores (basically locks and wait conditions) are used for thread-safety, where multiple independent threads access the same data (if at least one of them is also changing the data). This does not make it reentrant. If an interrupt is called while the semaphore is blocked by the main program, that interrupt cannot block the semaphore as well. The interrupt would have to wait for the semaphore to be released (which is what happens in multi-threading). But the interrupt is also blocking the main thread from executing, so the semaphore is never released. You get a dead-lock. You would need a semaphore-based data access by the operating system or the CPU, that is aware of interrupts, but that is beyond the scope of any (user space) programmer. 80.153.93.87 (talk) 15:28, 13 January 2016 (UTC)

Alternative

I think the definition is too sloppy: Consider the case of an object oriented language. An object x could refer to another object y. Now a method in the class of object x returns a value which depends on the state of object y. If the class of object y is mutable, then this is a side effect which influences the result of the method.

Now the problem with the definition is that in its strict sense, this method *is* re-entrant because there is no static data involved in this example. But I am led to believe that in its true meaning the method is *not* reentrant because the return value depends on side effects.

So I suggest the following definition: A reentrant piece of code is a pure function in mathematical terms, which means that its output solely depends on its input parameters, without any side effects.

This implies that the piece of code cannot use static, global or any other data which is not an input parameter. It also implies that the code cannot call other code which does not obeye these requirements. Finally, it implies that the piece of code is thread safe, because the code can only use variables which are local to the current thread (which are usually held on the stack by most programming languages). —Preceding unsigned comment added by 217.83.33.125 (talk • contribs)

But that is not what "reentrant" means in most contexts. While a function taking only immutable arguments is indeed reentrant by definition, it's not particularly useful in real life - passing references to complex mutable objects is much more efficient and useful in many cases. As far as I know, "reentrant" does not imply the complete lack of side-effects, but merely that the API is designed with reentrancy in mind. -- intgr 14:04, 10 November 2006 (UTC)

Java's String class is immutable. Its methods take other String objects and primitives as arguments. All these methods would be reentrant according to my definition. I don't think that they are not particularly useful - to the contrary: I couldn't do without them. Regarding the term "reentrancy in mind": Well, unless we have a clear definition of the term reentrant, we couldn't even argue what this term means. 217.83.74.51 10:23, 16 November 2006 (UTC)

The String class is an exception rather than the rule – nearly all methods taking Strings as arguments are bound to a mutable class anyway. My "reentrancy in mind" comment above relied on the original definition on the article: "[A] routine is described as reentrant if it can be safely called recursively or from multiple processes". -- intgr 15:40, 16 November 2006 (UTC)

I agree with intgr : functions whose output solely depends on its input parameters without any side effects is a sufficient requirement for reentrancy; however, it's not a necessary one. In fact, if that were necessary and sufficient, we wouldn't need all the other items on the list (not that the other items in the list hold all that much value either). As a counter-example to what's proposed, let's imagine that we have a processing queue that has a counter for how many items are in the queue. This counter can be read without a lock. You might get a slightly stale value if you read it when another thread is updating it (but all values are instantly stale anyway). A function that reads and returns the value of this counter is useful and reentrant, though it operates on global non-static data. Acertain (talk) 03:36, 28 December 2009 (UTC)

Why?

int f(int i)
{
  int priv = i;
  priv = priv + 2;
  return priv;
}

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

int main()
{
  g(1);
  return 0;
}

Why is this example reentrant? Is priv unique to each simultaneous process/thread or is it shared by all? --Abdull 10:40, 13 July 2007 (UTC)

priv is unique to each execution of f() and g() because priv is allocated on the stack of the current thread. Possibly this could be mentioned in the article, but I don't think it's necessary, either. -- Johngiors 06:50, 26 September 2007 (UTC)

Why not?

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

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

int main()
{
  g(1);
  return 0;
}

the parameter values are unique for each call. —Preceding unsigned comment added by 85.144.94.32 (talk) 13:59, 1 May 2008 (UTC)

Agreed. I have re-written the reentrant version without temporary variables, as I think they only served to obfuscate the code. TOGoS (talk) 23:00, 17 June 2008 (UTC)

the common misconception

"Despite a common misconception, this is not the same as being designed in such a way that a single copy of the program's instructions, in memory, can be shared."

So, what is the term/buzzword for that? Is it Thread safety? In which case, it should be added to the sentence, and the "See Also" section could be removed.

--Jerome Potts 17:16, 19 August 2007 (UTC)

removed that line bc it doesn't make sense; whether or not the executable code is physically shared among processes would only seem relevant for self-modifying code, which nobody uses. author probably meant the data on the heap, not the "instructions"... but still, its not useful. 12.219.83.157 06:05, 16 September 2007 (UTC)

Almost blatently copied

Sections of this article are almost redundant copies of the first external link: http://www.ibm.com/developerworks/linux/library/l-reent.html

Compare:

Reentrance and thread-safety are separate concepts: a function can be either reentrant, thread-safe, both, or neither...

and

Non-reentrant functions are thread-unsafe. Furthermore, it may be impossible to make a non-reentrant function thread-safe.

to: Don't confuse reentrance with thread-safety. From the programmer perspective, these two are separate concepts: a function can be reentrant, thread-safe, both, or neither. Non-reentrant functions cannot be used by multiple threads. Moreover, it may be impossible to make a non-reentrant function thread-safe.

TheShagg 20:26, 12 October 2007 (UTC)

Relation to thread safety

I don't think the following statement is correct:

"Non-reentrant functions are thread-unsafe. Furthermore, it may be impossible to make a non-reentrant function thread-safe."

I think you can have a thread safe function that is non reentrant. Maybe the write meant something like this?

"Thread-unsafe functions are non-reentrant. Furthermore, it may be [or even is] impossible to make a thread-unsafe function reentrant" —Preceding unsigned comment added by Hnassif (talk • contribs) 17:30, 19 October 2007 (UTC)

Right now it states "Non-reentrant functions are not thread-safe. Furthermore, it may be impossible to make a non-reentrant function thread-safe (quote?).". This does not make any sense at all, particularly coupled with the statement at the beginning "Reentrance is stronger property than thread-safety: a function can be thread-safe, both, or neither.". —Preceding unsigned comment added by 87.166.65.202 (talk) 17:54, 14 January 2008 (UTC)

The article seems to be assuming a different definition of reentrancy from the one with which I am familiar -- in particular, the definition with which I'm familiar says that a function is reentrant iff it's safe for the function to be called multiple times simultaneously from the same thread of execution. Using that definition, the notions of thread-safety and reentrancy are orthogonal (a function can be one, the other, both or neither). If this (useful!) notion is not called reentrancy, what /is/ it called? 212.44.26.44 (talk) 17:05, 24 August 2009 (UTC)

Async-signal-safe, maybe? 68.255.109.73 (talk) 18:18, 4 December 2010 (UTC)

(-) ads (+) added explanations (-) simplified intro (!) citation needed

Ad ads ;). There's been mentioned 2 guys for no aparent reason. It is nice they recomend something, sure. Your favourite OS teacher doesn't?

Explanations. I thought it might be nice to add some explanations for girls, who cram, and guys, who are just mildly curious. I also called it a derivation. It might not be a best name. Feel free to change mine mistakes ;).

Simplification. There we're 2 sentences which I thought would better be swapped. To me the second seemed more like natural explanation. Hmm

Citations. There are few claims in "derivation and explanation of rules" that I have no support. I am too lazy to look it up and ,hey, wiki-kids might practice google hunting. 86.61.232.26 (talk) 23:56, 26 April 2009 (UTC)

Reentrant interrupt handler

We are given two examples of best practise: 're-enable interrupts as soon as possible', and 'avoid early re-enabling of interrupts unless it is necessary'. These would appear to be mutually exclusive.

On a tangent: why does the article use 're-enable' and 're-entered', but then use the dubious 'reentrant'? Shouldn't it be re-entrant? —Preceding unsigned comment added by 59.95.22.6 (talk) 18:36, 20 November 2009 (UTC)

It does seem that the correct usage here is 're-entrant'. Lambda-mon key (talk) 00:51, 5 March 2010 (UTC)

Difference of "re-entrant" and "pure"

Is there a difference between the concepts of a re-entrant function a pure function? What about locks to singleton objects - is that a point of difference?

If they are the same, then this should be pointed out in both articles (see pure function). Otherwise, I think the difference ought to be explained, as it would make the definition richer.

Does anyone know the difference (and a few definitive sources to cite)? 203.171.122.38 (talk) 09:46, 23 October 2010 (UTC)

No idea about definitive sources, but:

• a reentrant function can have side-effects
• a reentrant function can access global state. Depending on your definition, it can even _modify_ global state in thread-unsafe ways, as long as everything is back to normal when it finishes.
• a pure function can be thread-unsafe and nonreentrant, provided its API indicates when it is appropriate to call it. Being pure is about being side effect-free and the output being a function of the input, nothing else.

Hope that helps. 68.255.109.73 (talk) 18:22, 4 December 2010 (UTC)

Italics

The long runs of italic text in the Derivations section is hard to read. Are these a quote? If so, that should be explicit. Normal text with perhaps a numbered list or bullet list would be easier to read. Sluggoster (talk) 17:51, 9 November 2010 (UTC)

Let's purge the entire article and start anew

The current version of this article is so factually wrong I can't fathom where it could be pulled from. Not to mention being completely unreferenced -- the only paragraph with references is unrelated to the rest of the article.

Let's start with debunking every single of the conditions listed:

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

 var counter:integer;
 
 function serial():integer; assembler;
 asm
   MOV EAX, 1
   LOCK XADD counter, EAX
 end;
 { like counter++ in C but atomic -- sorry for having no clue about AT&T syntax }

This function is re-entrant for every definition I am aware of.

• Must not return the address to static (or global) non-constant data.

 int get_queue(int i)
 {
     return &queues[i];
 }

• Must work only on the data provided to it by the caller.

Example 1.

• Must not rely on locks to singleton resources.

May use any such locks as long as it handles it being taken by other instances.

• Must not modify its own code. (unless executing in its own unique thread storage)

 void search_village_for_the_grail()
 {
   while(get_an_undug_spot())
   {
 start:
     do_the_digging();
     if (grail_found)
       *((char*)start) = RET;
   }
 }

This code works with both unthreaded and threaded reentrancy.

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

Or do it with proper care -- like queuing the calls and coordinating somehow. Users of the reentrant outer function don't need to know about the complexity.

Usual definitions

The definition I have been taught on MIM UW is concerned with a single thread. While the function is being executed, it may be called again, either normally or spontaneously (via an interrupt/signal/etc), and execution of the first call is completely blocked until the second finishes. In this case, there is no option of waiting for the first call to release any lock, it is often possible, though, to save any global state on the stack and restore it before returning.

This is especially important for Unix signals, when you cannot use non-reentrant functions like malloc() (in most implementations) which severely hinders what the program can try to do. Note that this definition does not imply thread safety.

Another definition some sources use is having the function calleable from different thread but not from the same one. This is equivalent to thread safety, and thus uninteresting.

The third possible definition is being both reentrant and thread-safe. This means that anyone can call the function in any case, regardless of which thread is executing. These concepts go largely orthogonal if efficiency is not vital -- and can be tricky to obtain together if it is.

In any case, the definition provided by the article is useless. It basically boils down to (mostly) pure functions with allowed output but not input.

KiloByte (talk) 15:22, 26 November 2010 (UTC)

A fourth definition is given in the Qt documentation: a function is reentrant if it can be called simultaneously from multiple threads, but only if each invocation uses its own data. As a remark on that page says, every thread-safe function (defined as a function which can be called simultaneously from multiple threads, even when the invocations use shared data) is thus reentrant, but not necessarily vice versa. The Wikipedia article should mention these alternative definitions and maybe provide unified terminology suggestions.

Jaan Vajakas (talk) 21:47, 27 November 2012 (UTC)

Reentrancy vs recursion

A yet another glaring factual error: this version claimed reentrancy is a requirement for recursion. It's not, for two reasons:

• recursive calls can happen only explicitely, unlike interrupts, so this code works:

 void f(int x)
 {
     acquire_global_data();
     mess_with_global_data(x);
     release_global_data();
     if (x > 0)
         f(x - 1);
 }

• possible arguments for a recursive call may be a subset of those called from the outside:

 void process_dir_and_parents(char *path)
 {
     if (!path || *path != '/')
         path = get_absolute_path(path); // not reentrant
     process_dir(path);
     chop_last_element(path);
     if (*path)
         process_dir_and_parents(path); // here, the path is always absolute
 }

KiloByte (talk) 13:36, 26 May 2012 (UTC)

While I don't want to defend the old text, your new wording is at best ambiguous with a possible interpretation that is factually inaccurate as well. I think it would have been better if you had simply removed the old statement. —Ruud 13:59, 26 May 2012 (UTC)

Good idea, I removed this, together with an unrelated vague statement about functional programming as well. KiloByte (talk) 22:45, 26 May 2012 (UTC)

What I assume the old text intended: non-reentrant functions usually break some invariant that is expected to hold on entry during execution, but re-establish it before exit. However if you make the recursive call while the invariant is broken things may go wrong. —Ruud 14:04, 26 May 2012 (UTC)

Further example is wrong

The page gives an example of a function.

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

f is not thread-safe. Then the article literally concludes from the non-thread-safety "Hence, f is not reentrant". First, the article itself explains that functions can be reentrant and not thread-safe. Second, Qt's page on reentrancy [1] gives basically the same code as an example of a reentrant function. It does not return the value, but that is not part of the definition of reentrancy, and the member variable might as well be global static if you use a static instance of the class.

class Counter
{
  int n;
public:
  void increment() { ++n; }
}

80.153.93.87 (talk) 15:46, 13 January 2016 (UTC)

Second example could avoid global variables

void swap(int *x, int *y)
{
    int s;

    s = *x;
    *x = *y;

    // hardware interrupt might invoke isr() here!
    *y = s;
}

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

This would make swap() a pure function without any side effects (as long as addresses of x and y are not shared). But with shared addresses consider

int x = 1, y = 2;

void swap(int *x, int *y)
{
    int s;

    s = *x;
    *x = *y;

    // hardware interrupt might invoke isr() here!
    *y = s;
}

void isr()
{
    int z = 3;
    swap(&x, &z);
}

main()
{
    swap(&x, &y);
}

When isr() finishes, x==3 and z==2. When then swap() finishes the second time, x==3 and y==1. Hardly what was expected as the result of swap() in main(). So I don't think this last code is an example of a reentrant routine, which does its task atomically.--H3xc0d3r (talk) 14:45, 26 January 2017 (UTC)

@H3xc0d3r: "So I don't think this last code is an example of a reentrant routine, which does its task atomically"

This is not true, as Yttril says in his answer on Stackoverflow:

"The point is that 'corruption' doesn't have to be messing up the memory on your computer with unserialised writes: corruption can still occur even if all individual operations are serialised. It follows that when you're asking if a function is thread-safe, or re-entrant, the question means for all appropriately separated arguments: using coupled arguments does not constitute a counter-example."

Maggyero (talk) 06:50, 25 June 2018 (UTC)

Incorrect rules for reentrancy

Reentrancy (computing)#Rules for reentrancy is incorrect in toto:

1. Reentrant routines may contain global data if they serialize access. Serialization can be done using either atomic instructions or operating facilities such as semaphores.
2. Reentrant code may modify itself; in fact, some of the reentrant code in OS/360 did just that, with appropriate serialization.
3. Reentrant code can call non reentrant code, with appropriate serialization.

Note: a refreshable procedure, or even a pure procedure, is not necessarily reentrant; it still needs appropriate serialization. - Shmuel (Seymour J.) Metz Username:Chatul (talk) 16:19, 25 May 2018 (UTC)

@Chatul: You seem to confuse reentrancy with thread safety. Reentrancy has nothing to do with multithreading and serialized access. A reentrant function may not be thread safe as the 3rd example of the article shows.

Maggyero (talk) 07:50, 25 June 2018 (UTC)

No, reentrant has meant safe for concurrent execution since the early 1960s. A wiki article can not be its own RS. Shmuel (Seymour J.) Metz Username:Chatul (talk) 21:42, 12 July 2018 (UTC)

Unnecessary atomicity requirement

@KiloByte: do you think that the last paragraph about the atomicity requirement in the current introduction of the article is correct? To me atomicity is not necessary, as demonstrated by the 3rd example in the article (Reentrant but not thread-safe), where tmp is a global variable that is not modified atomically.

Maggyero (talk) 07:39, 25 June 2018 (UTC)

Provenance of reentrancy

The claim It is a concept from the time when no multitasking operating systems existed. is false. The concept originated with OS/360 Shmuel (Seymour J.) Metz Username:Chatul (talk) 15:03, 20 August 2018 (UTC)

History

When was the concept of reentrant subroutines first developed? Was it before or after the widespread support for 1. hardware interrupts and 2. recursive subroutines? I'm guessing it preceded the introduction of preemptive multitasking OS. Cesiumfrog (talk) 06:42, 12 September 2019 (UTC)