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)

There are multiple serialization mechanisms. Interrupt handlers in a multiprocessor need lower level synchronization, e.g., Compare-And-Swap (CS) on an IBM System/370. For tasks (analogous to threads), OS services like ENQ/DEQ and semaphores are adequate for ensuring reentrancy. For both interrupt handlers and user code, deadlocks are an issue if the serialization is not properly thought out. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:15, 3 June 2022 (UTC)

the IBM term (back in time starting with OS/360) was "serial reusable" as a given attribute at linking time (Linkage Editor). --Pqz602 (talk) 18:52, 19 May 2022 (UTC)

Yes, and the serialization for a serially reusable module was within a job, not globally. You could not share a serially reusable module between jobs. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:15, 3 June 2022 (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)

That is basically correct. Reentrancy was usually used by OS/360 service rotines, even of Uni-CPU. The main reason was to save mainstorage and also performance (load time). A reentrant program could be made resident in storage and accessed by all users (tasks). Main storage was expensive, slow (magnetic cores in the 60ies) and a 512kB System was a very big system at this time. Also using online service (TSO, IMS, DB2, CICS, ....) the most common used programs could be made resident, if, and only if they are "reentrant". The above 3 rules are not precise:

• reentrant routines may use global data using serialization. The global data are not allowed to be inside the routine itself.
• reentrant code may never change its own coding. I have serviced some nightmares at customers systems at the time of first multiprocessor systems, where those common mistake blow up the system. See Shmuel (Seymour J.) Metz Username:Chatul ref to IBMs Linkage Editor Manual in next section "Provenance of reentrancy", last sentence.
• if reentrant code calls non-reentrant routines, you need not only serialization in common sense, i.e. lock shared data, but you have to mask (disable) interrupts and pin this execution to only one processor until return. That is a very very bad option and sometimes used during migration processes. Those programmers would not be very happy if such coding was detected and they had to answer for a reason of such procedure..

--Pqz602 (talk) 16:29, 20 May 2022 (UTC)

It's a bit more complicated than that.

OS/360 has reentrant routines that modify themselves with appropriate serialization. That's generally considered bad form and, AFAIK, IBM has cleaned up all such code in current (z/OS) MVS.

There is no requirement to disable interrupts, although that is one way to serialize in OS/360 with 65MP support. Typically, MVS replaced code that used SSM with code that acquired and released locks.

In OS/360, a reentrant routine can safely invoke a serially reusable routing via the LINK macro with no explicit serialization; LINK provides the required serialization.

In MVS (end of text added from Shmuel (Seymour J.) Metz Username:Chatul)

ENQ/DEQ is more close to application/subtask serialization. If I remember correct you are not allowed within interrupt-handling (always reentrant code) to use any SVC already at OS/360-time (MFT/MVT). For some minimum time within that interrupt-handling you have to avoid a CPU-switch, solved by running disabled for housekeeping. It is a real hack with those crossmemory/cross-cpu posting or unlocking. Starting with MP IBMs S/W-teams had to rewrite "some" code .... --Pqz602 (talk) 18:31, 22 May 2022 (UTC)

ENQ and DEQ are used by both application code and OS code. As with any SVC other than ABEND, they are not allowed in an interrupt handler or in a type 1 SVC. In MVS terms, they are only allowed in TCB mode.

In OS/360 through z/OS, interrupt handlers always run disabled and each CPU has its own prefixed storage area (PSA), so there is no need for additional serialization at entry. Once other code is involved, e.g., Dispatcher, I/O Supervisor, storage management, then of course those routines need to do additional serialization.

65MP support uses the test and set (TS) instruction for low level serialization, and set system mask causes a program check so the program interrupt handler can serialize and deserialize; that is certainly a hack, and I would even call it a kludge, but it did minimize the code that IBM had to change. MVS uses the newer instruction compare and swap (CDS) and compare double and swap (CDS), and uses locks rather than SSM; that required more of a code change than 65MP had.

In MVS there are two broad categories of locks; spin locks are for brief low level activities, run disabled and do not allow switching the CPU to other work. Suspend locks have more overhead, but allow other work to proceed if the lock is not available. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:29, 23 May 2022 (UTC)

just one more complaint to the article itsself: Rule 2 has written

• ...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). ...

The bold text is exactly the definition of "serial reusable" from OS/360 time and later. You are NOT re-entering the original code (which is never reentrant originally due to its self-modification). "reentrant" code will always be able to run as one physical code for muliple tasks (and CPUs). --Pqz602 (talk) 14:18, 21 May 2022 (UTC)

Notes

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)

Reentrancy came in with IBM Operating System/360 (OS/360) and Time Sharing System/360 (TSS/360) in the 1960s, long after the Univac 1103A, LISP and Algol 60. IBM introduced the concept for the multiprogramming options of OS/360, eventually known as MFT and MVT, both of which were preemptive, although initially only MVT allowed an application to ATTACH subtasks until OS/360 Release 15/16.. Shmuel (Seymour J.) Metz Username:Chatul (talk) 17:16, 12 September 2019 (UTC)

We should separate in History between OS/360 and TSS until ~1970, when TSO was implemented within OS/360. Until this time OS/360 was a "Batch-System". Around 1971 TSO substitutes TSS functions into MVS (MFT/MVT,...). The virtual storage concept of TSS was added a bit later, VS1/VS2 and some years later MVS. I don't dig just now to the time scale, but supported this S/W since 1969, H/W /360 some years before. Also UNIX was implemented later on within MVS. So .... we should also differ between UNIX and those IBM Architecture using examples and requirements for reentrancy. I will add a z/OS 2.3.0 ref to Linkage- Editor/Binder Options from Program Management users's Guide. It is a bit complicated to seperate on time-line, but the basics are still used since the 60ies from TSS via OS/3xx to z/OS, mixing a bit with UNIX's implementations.

Reentrant executable machine-code was basically not changed (se TSS ref), but ... special addressing allowed using parts of reentrant programs in areas dedicated and unique to each task (dynamically loaded/attached). In this case there is no need for serialization. If common (global) areas would be modified, of course - needs serialization.

I don't know UNIX, but further on PL/I and Fortran in these times had an "Checkout" version, producing object-code (intermediate code) which may be changed at run-time. The Checkout-compilers themselves have been reentrant, but this should not be mixed with native executed machine-code-programs. The "Checkout-source-code" will be interpreted (first by source to intermediate code, and then this intermediate code). Those interpreted source code (attributes) should not be mixed with compiled and loaded machine-code. Using C or Java samples don't make it better - Reentrancy is based on the machinecode of a processing system. Compiler/Interpreter options may already define or inhibit this reentrant attribute for machine loaded code. --Pqz602 (talk) 11:05, 26 May 2022 (UTC)

TSO does not substitute TSS function into MVT, SVS or MVS. Rather, TSO provides time sharing with its own syntax and API. While TSS supports some OS/360 facilities for compatibility, it has new access methods and is very different from both base OS/360 and TSO, especially as regards reentrant programs; OS/360 has no equivalent to the Protye Section (PSECT) of TSS. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:03, 27 May 2022 (UTC)

I know those differences and discussions since start of TSO. I have written "substitutes TSS functions, means conceptual the timesharing of online-users in seperate address-spaces in opposite to the batch-processing at this time. TSS introduced also already virtual storage (years before VS1 and VS2) and my VM-collegues at the time of first VM-Systems referred to TSS as the first VM-System. Those comparisons are a bit dangerous in details, but useful for general understanding. --Pqz602 (talk) 10:01, 3 June 2022 (UTC)

I have been IBM-CE in the 60ies, with beginning of OS/360 for those CPUs too, and later teached MFT/MVT (+Compiler) Lessons some years starting 1969/70. Until the first true Multi-CPU-Systems IBM had two main-definitions for executable programs, running in separate storage regions (variable size, MVT) or storage partitions (fixed size, MFT), each program-work named as task:

• serial reusable, those programs need to be loaded only once, could be used again without loading again. If you started a subtask (within same region/partition) using those programs, they had to be loaded with one copy for each task.
• reentrant, those programs could be used with one loaded Program-code by more than one task.

Just at this early years, remember, all interrupts have been handled by only one CPU without problems until sometime at end 70ies the first (tightly coupled) MP-Systems had been delivered - 2 CPUs. Any interrupt handler did the houskeeping via some standard (minor) register conventions. The interrupt handler routines must have been reentrant, because stored within operating system and serving all tasks.

With multiple CPUs each code not bounded to one processor has to be reentrant, because after each interrupt the next free CPU continues running that program. After teaching years (rotation job) and moving to service at customer locations i had some mightmares of first installations to serve running programms on Dual-Processor systems which have been linked with attribute reentrant, but did not regard reentrant-rules. The most common error was the use of (register-)save-areas in static storage inside program instead of dynamically allocations. Each processor has its own register-set, so .... results in garbage if save-areas get mixed. This relates to subtasks as well as to programs(tasks) in different partitions/regions.

In first time of small /360 Systems Customer are running programs within 8 to 16kiloBytes without operating system one program at a time. So common coding uses the initialization code later for data-workarea. Those coding was later on also kept for a while with small storage systems. A 512kB Mainstorage /360 was a big system, and MVT/MFT has to handle Programs within this "big" storage. This changes with first virtuell storage systems, but storage constraints are always real until today, just only other measures. Those spare-storage-programs are neither "serial reusable" nor "reentrant", but ..... they are still living somewhere .....

BTW: just pointing it here - "serial reentrant" ist not a correct term and was never used in old times. Either a program is reentrant and interruptable anywhere (from anyone) or otherwise it is no more reentrant. Serial reusable means - scrap the old copy and reload again, start always at defined entrypoint. serial reusable has to be locked on one processor only, but is still interruptable. Recurrency is just an other independent term, but if you run a recurrent function with non-reentrant code, you will get the code and work-areas multiplied with each (single) run of the loop, which will kill your system very quickly running out of storage.

Just a bit history, sorry if already known. It's just for sorting some of the terminologie discussed here by their original meaning. regards Peter --Pqz602 (talk) 18:24, 19 May 2022 (UTC)

Sorry, just an add-on: "task" as used in my post means the same as "thread" in these wiki-programming posts. Thread was at least not used by the former time main frame programmers. (and task is still used in Win10, most NT based Windows Systems are using the architecture similar to OS/360 and follower) --Pqz602 (talk) 18:56, 19 May 2022 (UTC):

A serially reusable module only needs to be loaded once within a partition (region), but each partition (region) had its own copy. Only reentrant modules are eligiible to be included in the shared Link Pack Area (LPA).

Only in a multiprocessor is reentrancy relevant for an interrupt handler in OS/360. Interrupt handlers ran disabled except for a few special points where they briefly enabled a recursiv e interrupt.

Neither reentrant nor serially reusable routines are bound to a single CPU, other than interrupt handlers, and doing so would not have accomplished anything.

In a multiprocessor, reentrancy is relevant to both enabled and disabled code.

In the 1960s, IBM already had tightly coupled multiprocessing on the 9020 and 360/67, not just on the 360/65.

In a few places you wrote serially reusable when non reusable is appropriate, e.g., recurrent invocation of serially reusable routine does not cause memory exhaustion but recurrent loading of non reusable code may. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:03, 27 May 2022 (UTC)

Notes

References

The code in Reentrant and thread-safe is not reentrant

The code in Reentrancy (computing)#Reentrant and thread-safe is not reentrant; it can execute concurrently on two different processors.

void swap(int* x, int* y)
{
    int tmp;
    tmp = *x;
    *x = *y;     /* if the other processor is running swap concurrently, you'll get incorrect results */
    *y = tmp;    /* Hardware interrupt might invoke isr() here. */
}

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

The code needs serialization to be reentrant. Shmuel (Seymour J.) Metz Username:Chatul (talk) 20:17, 15 September 2019 (UTC)

No, it doesn't need serialization. If this is running on two separate processors, a call to isr() on the second processor will create separate stack-based instances of x and y than those for the first processor. Thus, no two invocations of void swap(int* x, int* y) will ever (unless swap is used incorrectly elsewhere) operate on pointers to the same memory locations.

Benjamin J. Crawford (talk) 11:07, 3 October 2019 (UTC)

In other words, a reentrant function is "dumb" in that it assumes it is allowed to operate on memory which it is explicitly passed (through pointers in this case). It is the responsibility of the caller to ensure thread-safety. Reentrancy only makes the guarantee that the function doesn't depend on "external"/globally shared state. Benjamin J. Crawford (talk) 11:07, 3 October 2019 (UTC)

Reentrancy is not an issue for routines that operate only on local data in the stack, but it is an issue when shared data are involved; interrupt routines normally need to deal with shared data. You can write a reentrant routine to swap two words, but it requires some sort of serialization. On some processors there are atomic instructions that serialize storage access, on others you need to use a lock or similar mechanism. The location of the serialization is part of the design of the software; typically interface documentation will require that certain locks be held and require that other locks not be held. YMMV. Shmuel (Seymour J.) Metz Username:Chatul (talk) 22:28, 2 October 2019 (UTC)

I agree that in the typically useful case, memory access serialisation through some atomic operation is necessary for an ISR. I also agree that, by design, swap() is not inherently reentrant, which isn't completely clear from the description given on the page. From reading the passage however, it clearly implies later on that x and y are taken to be unshared local to a single isr invokation. If you consider inlining the swap() function, the snippet is reentrant. I suppose in this instance, it's important to limit your analysis to the code given, and not consider a general case. Perhaps it would be useful to explain which of the Rules for reentrancy you believe this violates and why. Benjamin J. Crawford (talk) 11:07, 3 October 2019 (UTC)

The problem is the sentence An implementation of swap() that allocates tmp on the stack instead of on the heap is both thread-safe and reentrant. That implementation is not reentrant when two invocations refer to the same variable. The usage of swap by isr is reentrant, but swap itself is not. Shmuel (Seymour J.) Metz Username:Chatul (talk) 16:51, 3 October 2019 (UTC)

Do you mean that a function might be swapping two values, at least one of which is static and defined outside a function? The caller might call swap() but an interrupt could invoke the caller a second time, and that would cause swap() to give invalid results? Wouldn't that be an example of the fact that it is always possible to break something if you try hard enough? Johnuniq (talk) 02:02, 4 October 2019 (UTC)

I completely agree with Johnuniq here. The mistake you're making is in abusing the swap function by not otherwise adhering to parallel processing mandates. If you pass in pointers to data used in overlapping invocations, that's the programmer's fault. The idea of reentrancy is solely to express that you don't need to worry that swap is "behind-the-scenes" shared-state dependent. Benjamin J. Crawford (talk) 02:26, 5 October 2019 (UTC)

There is no parallel processing mandate that requires that an ISR operate only on local data, and an ISR normally needs to manipulate global data. BTDT,GTTS. In this case, you do need to worry, because the swap function is not coded to operate correctly when, e.g., doing a swap to update the head of a queue. Shmuel (Seymour J.) Metz Username:Chatul (talk) 20:33, 6 October 2019 (UTC)

Again, you're not staying true to the example given. Sure, an ISR may very well need to operate on global data, but this isn't the case here. If the ISR indeed does need to swap two values in memory where race conditions may arise, locking (serialisation) can be done in the ISR itself, before and after calling the swap function. This does not change the fact that this example is both reentrant and thread-safe. Benjamin J. Crawford (talk) 13:35, 7 October 2019 (UTC)

Again, you're not reading the first sentence of the article: An implementation of swap() that allocates tmp on the stack instead of on the heap is both thread-safe and reentrant. The fact that the author code contrived code that didn't expose the lack of reentrancy doesn't make it reentrant. The contrived example of isr() is irrelevant unless the previous text establishes it as part of the context for claiming reentrancy.

I must say that this example is perhaps too contrived to be sufficiently confusing, and requires clarification. I will say in closing that the example does explicitly state that there is no dependence on shared data so it's difficult to assert that this is incorrect in any real way as it stands. I believe you have the sufficient fluency to add appropriate serialisation to this section of the article. I'd look forward to seeing that if you have the time. Benjamin J. Crawford (talk) 13:52, 15 October 2019 (UTC)

No, that wouldn't be an example of the fact that it is always possible to break something, nor do I agree that it is a fact. It's an example of failing to properly serialize a function. Shmuel (Seymour J.) Metz Username:Chatul (talk) 20:33, 6 October 2019 (UTC)

Notes

Confusing

I haven't contributed to Wikipedia in forever, so hopefully I'm doing this Talk thing correctly (and if not, it's an honest mistake!), but...

This article confuses the heck out of me. I'm not a computer scientist, but perhaps for that very reason I can be helpful. My observation is that most confusion and frustration comes about when there is a misunderstanding about the common ground. It's like when you don't quite hear everything your wife/husband/partner says, all you hear is "blah blah blah grocery store blah blah blah" and you ask them to repeat it, and they say "blah blah blah GROCERY STORE!!! blah blah," … and you are like, look, I got the GROCERY STORE part, I didn't get what came before and after that!!!

So, just to begin:

After fifteen minutes, I still have no idea what the first two sentences even mean. Take sentence one:

"In computing, a computer program or subroutine is called reentrant if multiple invocations can safely run concurrently."

I don't know what does this means. What is an "invocation?" Is an "invocation" the same as a "thread"? If so, does that mean we're just talking about multi-threaded programming? If not, how does this apply to other situations I might encounter?

How about "concurrently"? What does that mean? "Concurrently" can not mean "at the same time" (as in time on a wall clock), because the next sentence says "The concept applies even on a single processor system." Obviously, a single processor can't possibly be executing one machine-level instruction at a time, therefore, logically, "concurrently" must not mean "at the same time."

Next, still in sentence two, a re-entrant procedure is interrupted in the middle of its execution and then called again. What does this mean? Interrupted how? You mean by the OS or by something internal to the code itself? How can it be called again if it was interrupted? In my little universe, if I interrupt a running code by typing ^C, that's it. Game over, there's no picking back up. So what does "interrupt" mean here? Is it the same as pausing? And when we say it can be called again, do we mean, called again by the same thread, after it comes back and finishes the first time? Or a different thread? Or a different process?

I'm sure all of this is very basic and fundamental stuff, but at the moment it leaves me thinking that the underlying concepts probably aren't nearly as complex or confusing as the terms being used to try to describe them. I hope that my comments are taken at intended, which is to explain - to people who actually know this stuff and who might be baffled why this article is confusing - why it is, in fact, confusing, at least to some people. Thanks.Petwil (talk) 13:38, 7 February 2020 (UTC)

It is very basic and fundamental stuff, but that doesn't mean that more explanatory text is not in order. I'll try to address your questions, in no particular order.

Concurrently refers to both time actually running on a CPU and time waiting for a CPU.

An invocation means that something called it, whether s part of a process, a thread within a process or some other context. The requirement is that regradless of the invocation contexts, two instances running concurrently produce correct results.

Let me give a concrete example of concurrency, once on a single CPU and once on multiple CPUs.

1. Process A calls foo
2. An interrupt causes higher priority process B to become ready before the first invocation of foo completes
3. Process B calls foo
4. Process B, while running foo, waits for some event
5. The CPU is now available to continue running the instance of foo in Process A
6. There may be multiple waits in both processes

With multiple CPUs

1. Process A calls foo
2. Process B calls foo before the first invocation of foo completes
3. Either process A or Process B may need to wait for an event to complete, but in this example we are assuming that there are enough available CPUs that they begin running as soon as eligible.

To a first approximation you need the same code to make foo reentrant whether the first (single CPU) or second (multiple CPU) scenario applies. Shmuel (Seymour J.) Metz Username:Chatul (talk) 18:32, 7 February 2020 (UTC)

It's a bit "computer slang": a program (thread, task) is said "running" from the time it is started (invoked, called) until it's final completion (stop, return). A reentrant program-code may be used/entered from multiple callers/tasks at time, anyone else is already using this program-code (and still "running" concurrently). On a single-CPU System this happens for example, if caller1 waits for I/O response of 6msec, meanwhile caller2 runs some CPU-instructions of the same code (until he must also wait), and so on until program end.

Interrupt: as long as interrupts are allowed (they may be suppressed, "masked" by the CPU), typically any ended I/O operation is signaled to the cpu(s), which decides then to interrupt current processing and call an interrupt-handler (service-code of op-system), which does housekeeping and gives control to that task/thread, which requested the I/O-operation and was waiting for I/O-completion. There are other interrupt-possibilities, but that's the most common.--Pqz602 (talk) 21:23, 19 May 2022 (UTC)

The self-contradiction in the "Reentrant but not thread-safe" example should be fixed

I have a computer science background but am new to this concept. I found Reentrancy_(computing)#Reentrant_but_not_thread-safe to be unnecessarily confusing because of the recently added comment in the code: /*If hardware interrupt occurs here then it will fail to keep the value of tmp. So this is also not a reentrant example*/

This is self-contradictory because the name of the section and the description preceding the code example say that it is reentrant. I see in the edit history that this comment was added, removed, readded within the last few months.

I think we can agree that the article as a whole would be better if there isn't a part that says two opposing things simultaneously, right? Rather than leaving it as it is now, someone who knows this stuff better than me should clarify the ambiguities so that it's no longer possible to interpret the description and example in different "contexts" to arrive at different conclusions about whether it's reentrant or not. Maybe adding to the description something like "assuming that the ISR itself can't be interrupted and there is only 1 processor, so the ISR will finish and swap its 2 ints correctly before restoring tmp so that the interrupted instance will still see the value it expects in tmp"

Citizenofinfinity (talk) 11:11, 19 February 2021 (UTC)

The code in Reentrant but not thread-safe is not reentrant

The code in #Reentrant but not thread-safe is not reentrant unless it is running on a uniprocessor with interrupts disabled.

int tmp;

void swap(int* x, int* y)
{
    /* Save global variable. */
    int s;
    s = tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;     /* Hardware interrupt might invoke isr() here. */

    /* Restore global variable. */
    tmp = s;
}

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

There is no serialization on the global variable tmp between s = tmp; and tmp = s;. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 18:03, 13 February 2022 (UTC)

Notes; A program that serializes self-modification may be reentrant,.....

I cannot believe this sentence. If a program once is modified in its code, a second caller will never get the original coding. Serialization does not prohibit the code-change nor restores the original code. Those code may even not be "serial reusable", must be refreshed by reloading und always start "initially" again.

A selfmodifying code will never be reentrant in terms of reentrant's original meaning. --Pqz602 (talk) 22:05, 19 May 2022 (UTC)

Would like to add a main "protest": the whole "thread-safe" stories should not discussed her together with reentrancy. There is also too much reference to the Unix-world and C-Language belongings. The serialization of shared variables is a complete other stuff and has nothing to do with reentrant code. I agree basically with the reentrancy description, but thread-safe used in this context generates more confusion than understanding.

The point is: all processors (old /360 and new PC-CPUs) are using a set of (former) called base-registers. At least min. two registers are dedicated: one for execution-address and one for data-address (stack or dynamically allocated storage -- unique use for each task). As long as those conventions are used - by operating-system via interrupt-handler and the task-coding those programs are reentrant, because each interrupt returns to the interrupted execution-address and ISR restores the tasks data-pointer. Those data are commonly also use a register-save area, at OS/360+ times all 16 baseregisters chained with each call of further subroutines. Any change of shared variables outside the tasks ownership should be serialized, whether the code is "reentrant" or not.

I'm just speaking on machine-code-level. Whether C-Compilers issuing static or dynamic allocation of data-areas at initialization and protect static from changes is just an other business. Any change of task-internal coding or static-data inhibits the attribute "reentrant" for this portion of coding. Elder /360 Compilers will issue warnings at compilation time, if you try to modify internal code or static areas (using the corresponding compiler-options).

The thread-safe story should be discussed separately.--Pqz602 (talk) 09:32, 20 May 2022 (UTC)

A program is reentrant if it executes correctly when two invocations run concurrently. Serialization pf shared data, including data within the program, is very much relevant. A read-only program may fail to be reentrant it it modifies shared data without proper serialization, and a program that modifies itself may still be reentrant if it has proper serialization, although I would discourage the latter. The use of base registers and truncatated addressing doesn't really change that. --Shmuel (Seymour J.) Metz Username:Chatul (talk) 11:29, 20 May 2022 (UTC)

"a program that modifies itself may still be reentrant if it has proper serialization" ...is pure theory and practical nonsense. For what reason should I put (n) processors in a serialization lock (where they - with a bit of luck - never get out from wait), just to force them using all the same code instead of making such code "serial reusable" (in old terms). This other attribute forces the operating system to load the code again for each call and let all processors run that function equally , but in separated (duplicated) code. The sense of "reentrant" is making code resident for use by one copy only from all processors simultaneously, per definition running all the the same code.

Its own Code changing at execution is a very old and strange storage saving technique, which was banned at least with using virtual storage in mid-70ies. With multi-processors there is normally no control on flow of executions and interrupts. Also serialization requires a minimum of disabling interupts and wait states. It is horrible to use the attribute "reentrant" with code forcing total (for all using tasks) waitstates and may result in some kind of "russian roulette".

The same is valid for " A read-only program may fail to be reentrant it it modifies shared data without proper serialization,". A read-only program has to change nothing, otherwhise it is not read-only. "Modifying shared data" is no problem, as long as those data are not static (inside) that program - see before. Shared data outside that code will be locked for modification time only, whereas its own code-manipulation (as before) needs to lock the whole programcode putting every processor using the same code into waitstate (otherwhise you will get unpredictable results).

The program attribute "reentrant" has a special meaning and consequences, not only just that 2 guys may call the code at same time, and hopefully get the same result. --Pqz602 (talk) 10:59, 21 May 2022 (UTC)

Short description

@OlliverWithDoubleL: A recent edit added an incorrect short description. I was going to correct it but then I realized that I had come up with text that was much two long. So, the question is, how to word it so that it covers both scenarios below without being verbose?

1. Foo calls Baz on CPU A and at approximately the same time Bar calls Baz on CPU B. No interrupt is involved.
2. Foo calls Baz on CPU A, Foo is interrupted, Bar is dispatched on CPU A, Bar calls Baz, periodically interrupts cause alternating dispatches of Foo and Bar, with the two invocations of Baz interleaved on a coarse time frame.

In both cases Baz has to deal with serialization of data. Shmuel (Seymour J.) Metz Username:Chatul (talk) 13:57, 19 February 2023 (UTC)

@Chatul:

I’m ashamed to say I’m not a computer scientist, I just skimmed the introduction and tried to summarize it as best I could. If the concept is that complicated it's probably better to just set the short description as "concept in computer programming" and leave it at that OlliverWithDoubleL (talk) 23:24, 19 February 2023 (UTC)