Adding reentrancy information to safety notes?

Adding reentrancy information to safety notes?

[Carlos O'Donell]

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Michael Kerrisk (man-pages)]

Hi Carlos,

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

On 12/30/2014 04:45 PM, Carlos O'Donell wrote:
> 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.

Sounds good to me.

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

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

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

Okay -- modulo preceding point

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

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

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 12/30/2014 02:53 PM, Michael Kerrisk (man-pages) wrote:
> You better turn on the spell checker in your mailer (or update
> its dictionary) ;-). ("Ree_n_tran*")

Spell checker? :-)

>> * 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.
> 
> Sounds good to me.
> 
>> * Add a "R-Safe" and "R-Unsafe" to indicate safety with respect
>>   to reetrancy.
> 
> Sounds odd to me. Why not just say "Reentrant" and "Nonreentrant",
> rather than add new terms?

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?

>> * Immediately annotate all AS-safe functions as R-Safe.
> 
> Okay -- modulo preceding point
> 
>> * Review all of the "_r" functions for reetrance safety.
> 
> Okay.
>  
>> Thoughts?
>>
>> My review of other Unices indicates this is probably the
>> last type of safety that documented by other systems.
> 
> I am not quite clear what you mean by "last...documented".
> Do you mean: few other systems document it?

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.

Re: Adding reentrancy information to safety notes?

[Michael Kerrisk (man-pages)]

On 12/30/2014 09:08 PM, Carlos O'Donell wrote:
> On 12/30/2014 02:53 PM, Michael Kerrisk (man-pages) wrote:
>> You better turn on the spell checker in your mailer (or update
>> its dictionary) ;-). ("Ree_n_tran*")
> 
> Spell checker? :-)
> 
>>> * 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.
>>
>> Sounds good to me.
>>
>>> * Add a "R-Safe" and "R-Unsafe" to indicate safety with respect
>>>   to reetrancy.
>>
>> Sounds odd to me. Why not just say "Reentrant" and "Nonreentrant",
>> rather than add new terms?
> 
> Sounds good to me.
> 
> The only down side is that both of those words are quite long.

<nod>

> This makes the safety notes visually long.
> 
> Any thoughts on a short form?

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

>>> * Immediately annotate all AS-safe functions as R-Safe.
>>
>> Okay -- modulo preceding point
>>
>>> * Review all of the "_r" functions for reetrance safety.
>>
>> Okay.
>>  
>>> Thoughts?
>>>
>>> My review of other Unices indicates this is probably the
>>> last type of safety that documented by other systems.
>>
>> I am not quite clear what you mean by "last...documented".
>> Do you mean: few other systems document it?
> 
> 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?

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 30, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:

>   Note that reetrant functions need not be AS-safe nor MT-safe.

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Rich Felker]

On Tue, Dec 30, 2014 at 08:55:11PM -0200, Alexandre Oliva wrote:
> On Dec 30, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> 
> >   Note that reetrant functions need not be AS-safe nor MT-safe.
> 
> 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?

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

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

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

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

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 30, 2014, Rich Felker <dalias-8zAoT0mYgF4@public.gmane.org> wrote:

> On Tue, Dec 30, 2014 at 08:55:11PM -0200, Alexandre Oliva wrote:

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

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?


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

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

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

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

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.


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

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

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

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

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 12/30/2014 08:43 PM, Alexandre Oliva wrote:
> On Dec 30, 2014, Rich Felker <dalias@libc.org> wrote:
> 
>> On Tue, Dec 30, 2014 at 08:55:11PM -0200, Alexandre Oliva wrote:
> 
>>> 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.
> 
> 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.

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

[snip]

> Or are these questions meaningless because this definition is not the
> one we want to use for Reentrancy?
 
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

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:

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

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?

> Hopefully that clarifies the definition of reentrancy.

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 12/31/2014 04:31 AM, Alexandre Oliva wrote:
> On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> 
>> 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).
> 
> 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?

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.

>> Hopefully that clarifies the definition of reentrancy.
> 
> Yes, thanks for all the effort into clarifying what you meant, even
> though just the definition would have been enough.

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:

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

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

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

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 ;-)

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

*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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 01/01/2015 02:05 AM, Alexandre Oliva wrote:
> On Dec 31, 2014, "Carlos O'Donell" <carlos@redhat.com> wrote:
> 
>> I did not know malloc was required to be AS-safe for POSIX compliance.
> 
> Ugh.  Sorry, my bad, it's not.  malloc's AS-safety goal seems to have
> jumped from "desirable" to "mandatory" in my mind :-(

No worries. That's why we work together.

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

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

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

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.

Re: Adding reentrancy information to safety notes?

[Rich Felker]

On Tue, Dec 30, 2014 at 11:12:40PM -0500, Carlos O'Donell wrote:
> That is not the definition of reentrancy that I had in mind.

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.

> [snip]
> 
> > Or are these questions meaningless because this definition is not the
> > one we want to use for Reentrancy?
>  
> We already use AS-safe to indicate that a function is safe to reenter
> from a signal handler.

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.

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

This agrees with my definition.

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

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 12/31/2014 07:19 PM, Rich Felker wrote:
> On Tue, Dec 30, 2014 at 11:12:40PM -0500, Carlos O'Donell wrote:
>> That is not the definition of reentrancy that I had in mind.
> 
> 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.
> 
>> [snip]
>>
>>> Or are these questions meaningless because this definition is not the
>>> one we want to use for Reentrancy?
>>  
>> We already use AS-safe to indicate that a function is safe to reenter
>> from a signal handler.
> 
> 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.
> 
>> 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.
> 
> This agrees with my definition.
> 
>> 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.
> 
> 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.

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 31, 2014, "Carlos O'Donell" <carlos@redhat.com> wrote:

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

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

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 12/31/2014 04:38 AM, Alexandre Oliva wrote:
> On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> 
>> That is not the definition of reentrancy that I had in mind.
> 
> 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.

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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:

> 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'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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Adding reentrancy information to safety notes?

[Carlos O'Donell]

On 01/01/2015 02:11 AM, Alexandre Oliva wrote:
> On Dec 31, 2014, "Carlos O'Donell" <carlos@redhat.com> wrote:
> 
>> 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'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.

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.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
>   [...]

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.

Re: Adding reentrancy information to safety notes?

[Alexandre Oliva]

On Jan  5, 2015, "Carlos O'Donell" <carlos@redhat.com> wrote:

> On 01/01/2015 02:11 AM, Alexandre Oliva wrote:
>> On Dec 31, 2014, "Carlos O'Donell" <carlos@redhat.com> wrote:
>> 
>>> 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'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.

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

>> but it's ok if foo is unsafe here:
>> 
>> foo
>> bar
>> [...]
>> <signal>
>> [...]
>> 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?

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.


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

  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

Re: Adding reentrancy information to safety notes?

[Michael Kerrisk (man-pages)]

On Wed, Dec 31, 2014 at 5:07 PM, Carlos O'Donell <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
> On 12/31/2014 04:38 AM, Alexandre Oliva wrote:
>> On Dec 31, 2014, "Carlos O'Donell" <carlos-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org> wrote:
>>
>>> That is not the definition of reentrancy that I had in mind.
>>
>> 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.
>
> Michael,
>
> Any suggestion for an alternate term?

>From what I've seen of the discussion, and not having thought about it
at great depth, Synchronously Reentrant + SR-Safe sound okay to me.

Cheers,

Michael


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



-- 
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 majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html