re-entrant function????????

[Guillaume]

Usage varies, but re-entrant is commonly used to refer to code that

can safely be re-entered at any time (subject perhaps to locks). A
function that re-enters itself from certain fixed points (ie a recursive
function) may not be safely callable from another thread, and so may
not be re-entrant by this definition.

Ok with that, I think we weren't using the same definition. Now this is
clearer.

By that definition, non-reentrant recursive functions are often
ill-written (making too much assumptions about how they are going to
run), but that could lead to another debate.

 

[Chris Croughton]

Ok with that, I think we weren't using the same definition. Now this is
clearer.

The implied word is 'safely', any function by your definition is
re-entrant but only some are safely re-entrant (have predictable
and defined behaviour even if they are called before they complete). In
the standard library, for instance, strtok and qsort are two which are
not safely re-entrant (strtok is even worse, it can't be called safely
even if it has completed execution, it's a terrible function). The
strerror function isn't safely re-entrant because it uses a static
buffer to store the returned string.

By that definition, non-reentrant recursive functions are often
ill-written (making too much assumptions about how they are going to
run), but that could lead to another debate.

If they aren't designed and documented as such, it can lead to errors.
However, there are a number of situations where that functionality is
desired. A number of top-down recursive parsers, for instance, use
global data because the overhead in complexity of passing the
environment around is not worth it.

Chris C

 

[Lawrence Kirby]

On Tue, 11 Jan 2005 17:27:00 -0800, E. Robert Tisdale wrote:

....

The ANSI/ISO standards do *not* guarantee
that the first example above will be reentrant.

It does to the extent that signal handlers create reentrancy issues and
code that follows the rules still has to work when executed in a signal
handler.

Implementations are allowed to copy local variables into static storage
where they may be corrupted by other threads but, to my knowledge, there
are no viable ANSI/ISO compliant implementations which do so. So the
first example is, in *fact*, thread safe.

The possibility of recursion/mutual recursion also limits the compiler's
freedom in doing this. The fact is though that standard C doesn't support
miltithreading. It only makes sense to talk about reentrancy issues for
multithreading in the context of a particular multithreading environment.
For example there is nothing to stop a threading environment making all
normal C static objects per thread objects and limiting normal C
pointers to objects created in that thread. This makes everything
thread safe including strtok() with just some issues for shared external
resources like files. Such a threading implementation would presumably
provide a different mechanism for shared objects. Processes (in the Unix
sense) do that, but it could also be done in an environment where threads
share the same address space. This may not happen much in practice but
shows why thread safety in a standard C context is a meaningless
discussion, it is all down to the details of the multithreading
environment.

Lawrence

 

[Guillaume]

the standard library, for instance, strtok and qsort are two which are
not safely re-entrant (strtok is even worse, it can't be called safely

Thanks for pointing that out! I did know about strtok, but I didn't know
qsort was not safely reentrant... (I guess on some particular
implementation, it can be.)

That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!

desired. A number of top-down recursive parsers, for instance, use
global data because the overhead in complexity of passing the
environment around is not worth it.

That's true, although I've written parsers before that did pass the
whole "parsing environment" as a pointer to a dynamically-allocated
structure. The overhead is not that bad.

 

[Lawrence Kirby]

Thanks for pointing that out! I did know about strtok, but I didn't know
qsort was not safely reentrant... (I guess on some particular
implementation, it can be.)

That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!

No, it means you have to look to the guarantees provided by the
multithreading environment to see if it is. That is true for nearly all of
the standard C library functions, if not all of them.

Lawrence

 

[Chris Croughton]

Thanks for pointing that out! I did know about strtok, but I didn't know
qsort was not safely reentrant... (I guess on some particular
implementation, it can be.)

The spec. doesn't say anything about it, so it may or may not be safe.

That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!

There is probably either a multithreading version of the library, or if
any function (in that implementation) is unsafe by default there should
be a xorresponding safe one (often with -r appended to the name).

That's true, although I've written parsers before that did pass the
whole "parsing environment" as a pointer to a dynamically-allocated
structure. The overhead is not that bad.

Oh, certainly, it depends what the parser is doing. If it's only
building a tree then it may well be easiest to pass a pointer to the
current node into each function, for instance. If it's a one-pass
compiler doing object generation then the environment may well be very
messy (and having to dereference a structure pointer clutter the code
too much).

Of course, there may well be other reasons to make a parser reentrant.
Personally I'd rather write parsers in C++ these days where I can use a
string type without having to worry about memory allocation all the
time and can "pass the environment" implicitly in the class...

Chris C

 

[Giorgos Keramidas]

Thanks for pointing that out! I did know about strtok, but I didn't know
qsort was not safely reentrant... (I guess on some particular
implementation, it can be.)

That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!

qsort() is very often used to sort an array of some sort. It is not
safe to use qsort() in threaded applications because qsort() itself may
be entirely thread-agnostic.

Using a mutex to protect the array while it's being sorted may work
wonders though. The details shouldn't be too hard, but are a bit OT
as they depend on non-portable implementation details of the thread
library being used

- Giorgos

 

[Michael Wojcik]

It's not particularly useful to speculate about what standard library
functions may or may not be reentrant. That's what implementation
documentation is for.

I find qsort often is an option, if what I'm sorting is amenable
to qsort (that is, it's in an array, and sort performance isn't
so critical that calling a callback for every comparison isn't an
issue, and so forth).

qsort() is very often used to sort an array of some sort.

What else would it be used for?

It is not
safe to use qsort() in threaded applications because qsort() itself may
be entirely thread-agnostic.

This is entirely an implementation issue. There are implementations
which are both threaded and provide a thread-safe qsort (provided
no other thread alters the array duing sorting).

Using a mutex to protect the array while it's being sorted may work
wonders though. The details shouldn't be too hard, but are a bit OT
as they depend on non-portable implementation details of the thread
library being used

They're entirely OT for comp.lang.c. They're also irrelevant in many
cases, where "protecting the array" is not an issue, but that too is
OT.

--
Michael Wojcik (e-mail address removed)

Unlikely predition o' the day:
Eventually, every programmer will have to write a Java or distributed
object program.
-- Orfali and Harkey, _Client / Server Programming with Java and CORBA_

 

[Albert van der Horst]

<snip>

Minor nitpick:

Reentrancy is not just a multi-threading (lightweight processes) issue, but
arises whenever two threads of execution have access to some common
function. Apart from the example given, this may also happen in Interrupt
Service Routines (ISR's) or multitasking environments wich allow concurrent
access to a shared resource.

And the most important one, shared libraries. All functions in
unix .so files and windows .DLL files must be re-entrant, because they
are used by different processes at the same time.
So while re-entrancy is not theoretically needed for standard-conformance,
for library builders it is an important practical constraint.
So it is a good thing, and a quality of implementation issue, that
C-implementations mostly allow to build re-entrant functions.

 

[Keith Thompson]

And the most important one, shared libraries. All functions in
unix .so files and windows .DLL files must be re-entrant, because they
are used by different processes at the same time.
So while re-entrancy is not theoretically needed for standard-conformance,
for library builders it is an important practical constraint.
So it is a good thing, and a quality of implementation issue, that
C-implementations mostly allow to build re-entrant functions.

This is a bit OT, but I don't think it's correct. A non-reentrant
function in a shared library might be used by two different processes,
but the two copies of the function aren't going to share data, just
code. In particular, on at least one system I use, the strtok()
function is in /usr/lib/libc.so.

 

[Guillaume]

This is a bit OT, but I don't think it's correct. A non-reentrant

function in a shared library might be used by two different processes,
but the two copies of the function aren't going to share data, just
code.

That's true!

On most systems using shared libraries, data is allocated on the current
heap/stack and is in no way shared, unless otherwise specified.

 

[BGreene]

The correct terminology is "recursive" function. Reentrant
means something else entirely.

I agree the intent here was to ask about recursion not re-entrancy.

Barry