Adding reentrancy information to safety notes?

Michael, Peng, Alex,

We have had some recent discussions about reetrancy safety of dlopen. My goal is going to be to ensure that dlopen and in general the intefaces in libdl remain reetrant to allow user implemented malloc to use these interfaces to load libraries that themselves may have reetrant helper functions.

This raises the question: How do we clearly document which functions are reetrant?

My thoughts are as follows:
* Add some introductory text about reetrancy in the safety section. This text will discuss that AS-safe functions are reetrant because they must be to be AS-safe. Note that reetrant functions need not be AS-safe nor MT-safe.

* Add a "R-Safe" and "R-Unsafe" to indicate safety with respect to reetrancy.

* Immediately annotate all AS-safe functions as R-Safe.

* Review all of the "_r" functions for reetrance safety.

Thoughts?

My review of other Unices indicates this is probably the last type of safety that documented by other systems.

Cheers,
Carlos.
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

Hi Carlos,

You better turn on the spell checker in your mailer (or update its dictionary) ;-). ("Ree_n_tran*")

Sounds good to me.

Sounds odd to me. Why not just say "Reentrant" and "Nonreentrant", rather than add new terms?

Okay -- modulo preceding point

Okay.

I am not quite clear what you mean by "last...documented". Do you mean: few other systems document it?

Thanks,

Michael

Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Spell checker? :-)

Sounds good to me.

The only down side is that both of those words are quite long.

This makes the safety notes visually long.

Any thoughts on a short form?

I mean to imply that I hope we need not add any other safety notations aside from thread safety, signal safety, cancellation safety, and reentrancy. I have not seen any other notes in other Unices with the exception of fork1-safe in Solaris. Have you seen any other kinds of notes we might prepare to need in the future?

Cheers,
Carlos.

<nod>

Well, I'd say at least keep it to a recognizable abbreviation. ("Reent", "Nonreent"?)

Okay -- gotcha now. No, I think those four are the main one to worry about.

Cheers,

Michael

Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

How?

I suppose it might depend on the definition of reentrant, but if you can reenter it in multiple threads, and you can reenter it within a thread in which it is active (e.g., in a signal handler that may have interrupted its own execution), then it definitely is reentrant.

Conversely, if it is reentrant, then you can safely reenter it in multiple threads (MT-Safe) and within signal handlers (AS-Safe), no?

What definition of reentrant could make a function be reentrant without being both MT- and AS-Safe, or be both MT- and AS-Safe without being reentrant?

I suppose there might be scenarios in which a function doesn't qualify for AS-Safe because it doesn't support async recursion, but it could still be reentered by means of (indirect?) recursion safely. However, I can't see how this could be the case without the function being at least MT-Safe. It looks like any window that could bring trouble for async signals would also do so for other threads. Unless... Recursive locks? Those would avoid trouble for other threads (making the function MT-Safe), but not for async signals (so AS-Unsafe), and sync recursion could enable reentrancy while avoid pitfalls that async signals would bring about and that recursive locks wouldn't aovid. Is this the case you had in mind? Is it the only one in which a function can be Reentrant, MT-Safe and AS-Unsafe?

Can you think of any that is AS-Safe, MT-Unsafe and Reentrant?

Can you think of any that is AS-Unsafe, MT-Unsafe and Reentrant?

Can you think of any that is non-Reentrant but that is MT-Safe or AS-Safe?

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Anything written without memory barriers but that has proper compiler barriers for AS-safety/reentrancy.

Anything written without memory or compiler barriers but that uses global state in a reentrant way.

Non-reentrant but MT-safe: anything with non-recursive locks.

Non-reentrant but AS-safe: anything that achieves AS-safety by blocking signals for the duration of the operation or any operation that accesses the same data.

Rich
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

I guess I got too carried away on this bit, but there are various other uncertainties as to the meaning of Reentrant, and current POSIX doesn't provide us with any definition AFAICT. Earlier versions defined Reentrant Function as "A function whose effect, when called by two or more threads, is guaranteed to be as if the threads each executed the function one after another in an undefined order, even if the actual execution is interleaved." This is a stronger requirement than MT-Safety, and it is completely unrelated to AS-Safety and Recursion-Safety, so I guess that's not what Carlos meant.

After some more research to try and find some alternate but consensual definition compatible with what Carlos wrote, but instead of consensus I found various meanings that are similar but different in various ways, sometimes minor, sometimes huge.

For example, I found definitions of reentrant that apply only to single-threaded programs, with variants as to whether it equates to recursion-safety or it must tolerate asynchronous interrupts also.

A pretty common (if misinformed IMHO) one equates reentrancy with thread-safety; others state the concepts are related, but neither one implies the other. I find this a bit disturbing, for I don't see how a function that cannot be safely reentered in a separate thread (while already running on one thread) could qualify as reentrant.

Likewise, I don see how a funciton that cannot be safely reentered in the same thread, both within a signal and by means of (possibly indirect) recursion, could qualify as reentrant.

The most natural (to me) definition is that the function is safe to call even if it is already running, upstack on the same thread, or on other threads. This implies both AS-Safety (upstack of a signal handler) and MT-Safety (no problem with other threads), and this is enough AFAICT to make it recursive-safe as well.

Under this understanding, that Reentrant implies MT- and AS-Safe, these are both necessary conditions for Reentrancy under my understanding of the term. But are MT- and AS-Safety, taken together, both necessary and sufficient conditions for Reentrancy? Or are there other necessary conditions, on top of MT- and AS-Safe? (I believe AS-Safe implies Recursive-Safe, but if it doesn't, it would be an additional requirement)

Or are these questions meaningless because this definition is not the one we want to use for Reentrancy?

Clearly you're using a different definition of Reentrancy. Unfortunately you have not provided a definition, and I can't derive one from your statements above to as much as tell what they mean, since "reentrancy" and "reentrant way" both refer back to the unknown-to-me definition.

*nod*. Non-recursive locks are AS-Unsafe, thus (?) Reentrant-Unsafe.

Ok, so it looks like blocking signals for AS-Safety and taking recursive locks for MT-Safety still a non-Reentrant function could make, if the function is not a leaf, and functions it calls could possibly call it back. Now, how could any such arising problems, that render such a function Recursion-Unsafe, not make it also AS-Unsafe or MT-Unsafe?

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

That is not the definition of reentrancy that I had in mind.

[snip]

We already use AS-safe to indicate that a function is safe to reenter from a signal handler.

We already use MT-safe to indicate that a function is safe to reenter from another thread.

The only definition of reentrancy I had in mind is that which is derived from the original definition of single-threaded program reetrancy, with the exclusion of signals.

The reason I want to use this definition is to more formally describe those functions which are safe to call from a user provided malloc. A user provided malloc can be called from almost anywhere in glibc, it interrupts core glibc code, it only synchronously interrupts core glibc code (when malloc is called), and limiting a user provided malloc to AS-safe functions would be punative (though that is what we'll be doing in the initial documentation pass).

Definition of reentrancy:
=========================
~~~~
A function is reentrant if the one thread may safely call the function before a previous call to the same function by the same thread completes, but need not be safe if the second or subsequent calls are made while handling a signal.
~~~~
Safely implies no data loss.

By definition all AS-safe functions are reetrant.

A reetrant function may be AS-unsafe and MT-unsafe.

A reetrant function may be AS-unsafe and MT-safe.

A reetrant function may be AS-safe (makes it reetrant by definition) and MT-unsafe.

A reetrant function may be AS-safe (") and MT-safe.

Examples:
=========

The function __as_mt_safe_malloc_r is a AS-Safe, MT-safe, and reetrant malloc that falls back to a simple and provably safe allocator when recursion is detected (thus allowing it to return some memory after a first recursion).

A reentrant function can be AS-unsafe and MT-unsafe:
~~~
int *t;

void swap_r(int *x, int *y)
{
if (t == NULL)

    t = __as_mt_safe_malloc_r (sizeof(int));

*t = *x;
*x = *y;
*y = *t;
}
~~~
MT-unsafe: Race with multiple writers writing to t.
AS-unsafe: Overwrites global state t.
Reetrant: The function can only be reentered when it calls another
function e.g. __as_mt_safe_malloc_r. It is safe to reenter at this point, but will leak sizeof(int) during initialization.

A reetrant function can be AS-unsafe and MT-safe:
~~~
__thread int *t;

void swap_r(int *x, int *y)
{
if (t == NULL)

    t = __as_mt_safe_malloc_r (sizeof(int));

*t = *x;
*x = *y;
*y = *t;
}
~~~
MT-safe: Uses thread local storage to hold t.
AS-unsafe: Overwrites global state t.
Reentrant: Yes.

A reentrant function can be AS-safe and MT-unsafe:
~~~
int *t;

void swap_r(int *x, int *y)
{
int s;
s = *t; /* Save global. */
if (t == NULL)

    t = __as_mt_safe_malloc_r (sizeof(int));

*t = *x;
*x = *y;
*y = *t;
*t = s; /* Restore global. */
}
~~~
MT-unsafe: Race with multiple writers writing to t.
AS-safe: Saves and restores the global state.
Note: Assumes the loads and stores are atomic wrt to signals.
Just pretend they are without me needing to use C11 atomics.
Reentrant: Yes.

A reentrant function can be AS-safe and MT-safe:
~~~
__thread int *t;

void swap_r(int *x, int *y)
{
int s;
s = *t; /* Save global. */
if (t == NULL)

    t = __as_mt_safe_malloc_r (sizeof(int));

*t = *x;
*x = *y;
*y = *t;
*t = s; /* Restore global. */
}
~~~
MT-safe: Uses thread local storage to hold t.
AS-safe: Saves and restores global state.
Reentrant: Yes.

The examples are toy examples, but it shows that a reetrant function can be completely orthogonal to MT-safe and AS-safe.

It is much harder to come up with more complex examples that call other functions, but it should be possible with more work.

Hopefully that clarifies the definition of reentrancy.

Cheers,
Carlos.

Note:
- The wikipedia article on reentrancy has a lot of confused terms.
https://en.wikipedia.org/wiki/Talk:Reentrancy_%28computing%29

Hmm... Given that making malloc AS-Safe is reuqired POSIX compliance, what would we gain by enabling malloc implementations to call functions beyond other AS-Safe functions? I mean, a malloc implementation cannot be AS-Safe if it calls AS-Unsafe functions, nor can it be MT-Safe if it calls MT-Unsafe functions, even if they are Reentrant under the definition you provided, so... Wouldn't enabling malloc to call them making sure we won't ever be able to make malloc AS-Safe, and thus POSIX-compliant?

Yes, thanks for all the effort into clarifying what you meant, even though just the definition would have been enough.

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

I did not know malloc was required to be AS-safe for POSIX compliance.

Could you please quote the relevant part of the issue 7 standard?

See: http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_04.html
2.4.3 Signal Actions.

The list of functions does not list malloc.

My pleasure. A list of examples helps not just you but future readers.

Cheers,
Carlos.

--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

Ugh. Sorry, my bad, it's not. malloc's AS-safety goal seems to have jumped from "desirable" to "mandatory" in my mind :-(

Beware, that's a very old version of POSIX that you referenced above. What led me to realize it was the use of the term "reentrant" there ;-)

Anyway, the corresponding table in current POSIX fails to list malloc as AS-Safe just the same ;-)

*nod*

Thanks, and happy GNU year to all!

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

No worries. That's why we work together.

You are correct, issue 6 is old, issue 7 is the most recent, with text here:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/V2_chap02.html#tag_15_04_03

So to recap:

We would complicate a user malloc implementation by forcing them to use only AS-safe functions.

We want to expand the list of usable functions the user can call from their malloc without requiring it be all functions.

The tentative initial list is "all AS-Safe and SR-safe function." Where SR-safe stands for synchronously reentrant e.g. can be reentered by the same thread, but not from asynchronous contexts.

Cheers,
Carlos.

Indeed. To me, "reentrancy" means the ability to enter the code again while one or more instances of the same function are already running in the same thread. In my view this doesn't necessarily include asynchronous reentrancy unless explicitly stated, and it doesn't have anything to do with the concept of reentrancy in the obsolete POSIX 2001 that was removed and replaced with "thread safety" in later editions of POSIX.

AS-safety means more than that. It means that it's safe to use the function from a signal handler no matter what function the signal handler interrupted, and that it's safe to call any standard function from a signal handler that interrupted the AS-safe function. Note that the latter part can be vacuously true if AS-safety is achieved by blocking signals for the duration of the function.

This agrees with my definition.

No, AS-safe does not imply reentrant. Consider a function that invokes a callback but blocks signals during its execution. It's vacuously AS-safe but instead of via a signal handler it can be re-entered via the callback, and whether such reentrancy is safe is a non-trivial question.

Rich
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

You are correct. Thank you for the contradicting example.

The correction should read:

"A reentrant function may be AS-safe and MT-unsafe."

Thus the safety note is entirely orthogonal to AS and MT safety.

Cheers,
Carlos.

--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

Since reentrant is such an overloaded term, how about using the term Recursion-Safe, that AFAICT covers only the concept you have in mind. Another possible term that occurs to me is Synchronously Reentrant, to indicate it doesn't cover asynchronous reentrancy out of signals or multiple threads. We could then shorten it as SR-Safe.

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer

Michael,

Any suggestion for an alternate term?

Alex,

In hindsight I see that reetrancy is an overloaded term. The POSIX standard uses "reentrant by signals" to mean AS-Safe. Several authors seem to use "reetrant by another thread" to mean MT-safe. Thus without some kind of qualifier the term reentrant seems ambiguous at best.

You suggest "synchronously reentrant", and that might be the best and most flexible definition. You have to define at what points the function might be synchronously reentered, much like synchronous cancellation defines such points. In the case of glibc internals you can be synchronously reentered only if you call a function that might directly or indirectly call malloc, calloc, realloc, or free. AFAIK these are the only functions that allow users to synchronously interrupt glibc internal operations and call back into the runtime. Application calls to core runtime functions may be interposed and in those cases the interposing function must follow the standard requirements, but for maximum compatibility may need to adhere to the preliminary safety notes along with the new SR notes.

Note that synchronously reetrant would still follow the definition I gave in the previous email. Restated here with some slight rewording:
~~~~
A function is synchronously reentrant if a thread may safely call the function before a previous call to the same function by the same thread completes, but need not be safe if the second or subsequent calls are made while handling an asynchronous signal or by another thread.
~~~~

I amended the definition to say "asynchronous signal" since it is possible for user code to synchronously handle signals and that such synchronous signal handlers could make effective use of SR-safe functions since such handlers would be known not to be asynchronously interrupting any such previous calls to the SR-safe functions. Similarly synchronous cancellation handlers should be able to call SR-safe functions?

Cheers,
Carlos.
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

I'd qualify the asynchronous signal to state that it need not be safe only if the signal interrupted asynchronously the execution of the previous call, otherwise it would also allow a(n indirectly) recursive function, called from the signal handler for the first time, to be unsafe when called recursively.

I.e., stack traces such as:

foo
bar
foo
[...]
<signal>
[...no foo...]
main

should be just as safe as:

foo
bar
foo
[...no foo...]
main

but it's ok if foo is unsafe here:

foo
bar
[...]
<signal>
[...]
foo
[...]

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

That is true. I considered this in the context of synchronous signal delivery but couldn't come up with a real way to assure myself that the signal didn't interrupt foo.

I agree that this can happen. The question I have is: Is it worth allowing this if you can't prove that foo wasn't being executed?

I guess you can prove it by assuring that you're only calling AS-safe functions, of which foo isn't one of them, and if it is, then it's safe to call anyway.

How would you rewrite the original definition to include this case?

Cheers,
Carlos.

Well... I guess an application that implements a function and sets up a signal handler that might call it could always arrange for the function to test some property very early in its execution, and unset just before the end of its execution, so that the signal handler can tell whether it is safe to call such an SR-Safe but AS-Unsafe function, or whether it has to take some other path.

A function is synchronously reentrant if a thread may safely call the function before a previous call to the same function by the same thread completes, but need not be safe if the second or subsequent calls are made by another thread, or while handling an asynchronous signal that interrupts the execution of the function.

Here's another somewhat more formal definition, that defines invocations rather than functions as (a)synchronously reentrant, and defines SR-Safe as a property equivalent to the definition above:

An invocation of a function F is a direct part of an execution of a function G iff G calls F, or G accepts a synchronous signal whose handler is F. The execution of function G may encompass other direct parts that are not function invocations.

An indirect part of an execution of a function F is any direct part of the execution of a function G, whose invocation is in turn a direct or indirect part of the execution of F.

An invocation of a function F is synchronously reentrant iff it is a direct or indirect part of another execution of F.

An invocation of a function F is asynchronously reentrant iff it occurs in one thread while another thread carries out a direct or indirect part of an execution of F, or in an asynchronous signal handler that interrupted any direct or indirect part of another execution of F.

A function F is SR-Safe iff it is safe for any direct or indirect part of an execution of F to be a synchronously reentrant invocation of F, absent any asynchronously reentrant invocation of F.

Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer

at great depth, Synchronously Reentrant + SR-Safe sound okay to me.

Cheers,

Michael

Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-man" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html