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

[thesushant]

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant

[Yan]

th********@rediffmail.com wrote:

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant

that becomes an issue when using/writing multi-threading code. If a
function relies on static data, and is called while another thread has
already called it and is executing, that static data may be changed by
different threads and produce unexpected results

[CBFalconer]

th********@rediffmail.com wrote:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

#include <stdio.h>

int putword(unsigned long w, FILE *f)
{
if (w > 9)
if (0 > putword(w / 10, f)) return EOF;
return putc((w % 10) + '0', f);
} /* putword */

/* --------------- */

#ifdef TESTING

#include <stdlib.h>

int main(void)
{
int i;

for (i = 0; i < 10; i++) {
putword(i, stdout);
putc(' ', stdout);
putword(rand(), stdout);
putc('\n', stdout);
}
return 0;
} /* main */
#endif
--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Trent Buck]

Up spake th********@rediffmail.com:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

This is re-entrant

int
f (int x)
{
int y;

y = x * x;
return y;
}

This is not

int y;

int
f (int x)
{
y = x * x;
return y;
}

Another example of re-entrant vs. non-reentrant functions is strtok_r
vs. strtok.

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.

The canonical example is

int x;
void f (void) { x++; }

with two threads executing f(). The ++ operation (typically) resolves
into three assembly instructions: copy-memory-to-register,
increment-register, and copy-register-to-memory.

Consider, for example, the situation where first thread executes the
first two instructions, then the second thread executes all three, then
the first thread executes the last instruction. The second thread's
change will be lost, and the contents of memory at that address will be
incorrect.

This class of bugs are a PITA to locate, because symptoms are
intermittent and therefore difficult to reproduce.

--
-trent
How, Joe wondered, can a man have courage without faith, without belief?
Burroughs believed in nothing, and yet there he sat stubborn as Luther.

[pete]

CBFalconer wrote:

th********@rediffmail.com wrote:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

#include <stdio.h>

int putword(unsigned long w, FILE *f)
{
if (w > 9)
if (0 > putword(w / 10, f)) return EOF;
return putc((w % 10) + '0', f);
} /* putword */

Standard library functions aren't guaranteed to be reentrant, so,
a function which calls putc can't be guaranteed to be reentrant.

--
pete

[Thomas Stegen]

pete wrote:

CBFalconer wrote:

th********@rediffmail.com wrote:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

#include <stdio.h>

int putword(unsigned long w, FILE *f)
{
if (w > 9)
if (0 > putword(w / 10, f)) return EOF;
return putc((w % 10) + '0', f);
} /* putword */

Standard library functions aren't guaranteed to be reentrant, so,
a function which calls putc can't be guaranteed to be reentrant.

More importantly imo is that putc has a side effect on the file and so
the function is not reentrant even on an implementation where putc is
reentrant.

--
Thomas.

[dandelion]

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.

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

[Eltee]

dandelion wrote:

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.

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

Pardon me but ... are reentrancy, multi-threading, ISR's and multitasking really
a part of ISO C specification?

[dandelion]

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.
<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.

Pardon me but ... are reentrancy, multi-threading, ISR's and multitasking

really a part of ISO C specification?

Reentrancy is, for the simple reason that the standard lib is not guaranteed
to be reentrant (and that is, IIRC, part of the standard). A further
discussion of "reentrancy" brings on the other subjects.

So while not being part of the standard, they (multithreading, ISR's and
shared resources) are topical in this limited treatment.

[Eltee]

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.

<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.
Pardon me but ... are reentrancy, multi-threading, ISR's and multitasking

really

a part of ISO C specification?

Reentrancy is,

Would you point some fingers, please? Where can I find the ISO C specification
and, specificaly, where does it say anything about reentrancy?
for the simple reason that the standard lib is not guaranteed
to be reentrant (and that is, IIRC, part of the standard). A further
discussion of "reentrancy" brings on the other subjects.

So while not being part of the standard, they (multithreading, ISR's and
shared resources) are topical in this limited treatment.

[dandelion]

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

>As the OP said, it becomes an issue when you have multiple threads
>(lightweight processes) in a single process, because (some) state is
>shared between multiple threads of execution.

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

Pardon me but ... are reentrancy, multi-threading, ISR's and

multitasking
really

a part of ISO C specification?

Reentrancy is,

Would you point some fingers, please? Where can I find the ISO C

specification and, specificaly, where does it say anything about reentrancy?

http://www.iso.org, the costs are 340 swiss franks.

<quote 5.2.3>
[#1] Functions shall be implemented such that they may be
interrupted at any time by a signal, or may be called by a
signal handler, or both, with no alteration to earlier, but
still active, invocations' control flow (after the
interruption), function return values, or objects with
automatic storage duration. All such objects shall be
maintained outside the function image (the instructions that
compose the executable representation of a function) on a
per-invocation basis.
</quote>

<quote 7.1.4>
[#4] The functions in the standard library are not
guaranteed to be reentrant and may modify objects with
static storage duration.146)
</quote>

[Xenos]

"dandelion" <da*******@meadow.net> wrote in message
news:41***********************@dreader8.news.xs4al l.nl...

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.

You are getting too caught up in terminology. An interrupt *is* a thread of
execution.

DrX

[Richard Tobin]

In article <cs*********@cui1.lmms.lmco.com>,
Xenos <do**********@spamhate.com> wrote:

You are getting too caught up in terminology. An interrupt *is* a thread of
execution.

Maybe. Or maybe it's just an involuntary function call. It depends
on your interrupts.

-- Richard

[CBFalconer]

pete wrote:

CBFalconer wrote:

th********@rediffmail.com wrote:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

#include <stdio.h>

int putword(unsigned long w, FILE *f)
{
if (w > 9)
if (0 > putword(w / 10, f)) return EOF;
return putc((w % 10) + '0', f);
} /* putword */

Standard library functions aren't guaranteed to be reentrant, so,
a function which calls putc can't be guaranteed to be reentrant.

True. Which points out that we need a putc call guaranteed to be
atomic, i.e. non-interuptable. All of which is OT here.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[CBFalconer]

Thomas Stegen wrote:

pete wrote:

CBFalconer wrote:

th********@rediffmail.com wrote:

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

#include <stdio.h>

int putword(unsigned long w, FILE *f)
{
if (w > 9)
if (0 > putword(w / 10, f)) return EOF;
return putc((w % 10) + '0', f);
} /* putword */

Standard library functions aren't guaranteed to be reentrant, so,
a function which calls putc can't be guaranteed to be reentrant.

More importantly imo is that putc has a side effect on the file
and so the function is not reentrant even on an implementation
where putc is reentrant.

That side effect is under control, since f is a parameter.
putword, and even for that matter putc, can be interrupted and
called again, provided only that the parameters are different.
However if the function used putchar the criticism is valid.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[dandelion]

"Xenos" <do**********@spamhate.com> wrote in message
news:cs*********@cui1.lmms.lmco.com...
<snip>

You are getting too caught up in terminology. An interrupt *is* a thread of execution.

That was the point. I was responding to a post which seemed to suggest only
lightweight processes have reentrancy issues.

[Xenos]

"Richard Tobin" <ri*****@cogsci.ed.ac.uk> wrote in message
news:cs**********@pc-news.cogsci.ed.ac.uk...

In article <cs*********@cui1.lmms.lmco.com>,
Xenos <do**********@spamhate.com> wrote:

You are getting too caught up in terminology. An interrupt *is* a thread ofexecution.

Maybe. Or maybe it's just an involuntary function call. It depends
on your interrupts.

Again, it doesn't matter. It's still a particular order of executing
instructions. What you choose to call it or how it is implemented is
relevant. It is still a thread of execution. A thread of execution is not
exclusive to a so called multi-threaded environment, or the use of "thread"
for a light-weight process. A process, interrupt, or even the execution of
a C signal or C++ exception, are all threads of execution, that may or may
not execute within the context of a given process, process thread, process
fiber, or whatever.

[Eltee]

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...
dandelion wrote:
>"Trent Buck" <ge*******@tznvy.pbz> wrote in message
>news:20*********************@harpo.marx...
><snip>
>
>>As the OP said, it becomes an issue when you have multiple threads
>>(lightweight processes) in a single process, because (some) state is
>>shared between multiple threads of execution.
>
><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.

Pardon me but ... are reentrancy, multi-threading, ISR's and
multitasking
really
a part of ISO C specification?
Reentrancy is,

Would you point some fingers, please? Where can I find the ISO C

specification

and, specificaly, where does it say anything about reentrancy?

http://www.iso.org, the costs are 340 swiss franks.

<quote 5.2.3>
[#1] Functions shall be implemented such that they may be
interrupted at any time by a signal, or may be called by a
signal handler, or both, with no alteration to earlier, but
still active, invocations' control flow (after the
interruption), function return values, or objects with
automatic storage duration. All such objects shall be
maintained outside the function image (the instructions that
compose the executable representation of a function) on a
per-invocation basis.
</quote>

<quote 7.1.4>
[#4] The functions in the standard library are not
guaranteed to be reentrant and may modify objects with
static storage duration.146)
</quote>

Thanks.

Now, as we established that reentrancy is not entirely off topic, may I inquire
as to which implementations of a standard library are, in fact, reentrant
inspite of the above ISO "not guaranteed" guideline? GNU? Intel? M$? Borland? etc?

[dandelion]

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...
<snip>

Thanks.
My pleasure.
Now, as we established that reentrancy is not entirely off topic, may I inquire as to which implementations of a standard library are, in fact, reentrant
inspite of the above ISO "not guaranteed" guideline? GNU? Intel? M$?

Borland? etc?

Dunno. Frankly I would not count on any of them being reentrant. If you _do_
find a reentrant version and count on that, someone, somewhere, sometime is
going to compile your program with some other (non-reentrant) library.

And that's when the big, ugly brutes of bugs crawl out of the woodwork. So
(privately) I'll treat them *all* as being 'non-reentrant', which has not
been a major problem.

[Eltee]

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...
<snip>

Thanks.

My pleasure.

Now, as we established that reentrancy is not entirely off topic, may I

inquire

as to which implementations of a standard library are, in fact, reentrant
inspite of the above ISO "not guaranteed" guideline? GNU? Intel? M$?

Borland? etc?

Dunno. Frankly I would not count on any of them being reentrant. If you _do_
find a reentrant version and count on that, someone, somewhere, sometime is
going to compile your program with some other (non-reentrant) library.

And that's when the big, ugly brutes of bugs crawl out of the woodwork. So
(privately) I'll treat them *all* as being 'non-reentrant', which has not
been a major problem.

So you guys always use synchronized wrappers around stdlib functions? I mean,
common "operations" such as malloc, sprintf? That's news to me, cause I haven't
written a synchronized wrapper around a malloc, yet. Consequently, my entire "c
opus" ;-) is useless as far as multi-threadedness is concerned? Bummer!

[dandelion]

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net...
<snip>

Thanks.

My pleasure.

Now, as we established that reentrancy is not entirely off topic, may I

inquire

as to which implementations of a standard library are, in fact, reentrantinspite of the above ISO "not guaranteed" guideline? GNU? Intel? M$?

Borland? etc?

Dunno. Frankly I would not count on any of them being reentrant. If you _do_ find a reentrant version and count on that, someone, somewhere, sometime is going to compile your program with some other (non-reentrant) library.

And that's when the big, ugly brutes of bugs crawl out of the woodwork. So (privately) I'll treat them *all* as being 'non-reentrant', which has not been a major problem.

So you guys always use synchronized wrappers around stdlib functions? I

mean, common "operations" such as malloc, sprintf?
Nope. I try to avoid calling them alltogether in any part of the system that
is eligable to have multiple threads of execution running.
That's news to me, cause I haven't written a synchronized wrapper around a malloc, yet. Consequently, my entire "c opus" ;-) is useless as far as multi-threadedness is concerned? Bummer!

Hmmm... Without knowing your "Magnus Opus", not all is lost.

Writing wrappers for the functions you need isn't all that hard and usually
a multithreaded app has one main thread taking care of all the mallocing,
sprintffing etc. and a number of "small" threads with a very limited task .

That makes it easy to avoid calling the standard lib in the "small" threads
and thus, reentrancy is not really a problem.

[CBFalconer]

Eltee wrote:

.... snip ...
Now, as we established that reentrancy is not entirely off topic,
may I inquire as to which implementations of a standard library
are, in fact, reentrant inspite of the above ISO "not guaranteed"
guideline? GNU? Intel? M$? Borland? etc?

Who knows. You would have to examine each function of each
library. What we can say is that some are inherently
non-reentrant, e.g. strtok. putchar specifies a file, and thus is
non-reentrant, while putc does not, and thus can be reentrant. The
better implementations will make everything possible reentrant.

When you have the library source you can make these decisions, if
you know what you are doing and can spend the time.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Lawrence Kirby]

On Tue, 11 Jan 2005 16:43:03 +0100, Eltee wrote:

....

So you guys always use synchronized wrappers around stdlib functions? I mean,
common "operations" such as malloc, sprintf? That's news to me, cause I haven't
written a synchronized wrapper around a malloc, yet. Consequently, my entire "c
opus" ;-) is useless as far as multi-threadedness is concerned? Bummer!

If you use threads you will be using an environment that supports them as
an extension. That environment is also likely to support reentrant use of
various standard library functions as a related extension.

Lawrence

[Robert Gamble]

On Tue, 11 Jan 2005 16:43:03 +0100, Eltee wrote:

dandelion wrote:

"Eltee" <el***@hotmail.com> wrote in message
news:34*************@individual.net... <snip>

Thanks.

My pleasure.

Now, as we established that reentrancy is not entirely off topic, may I

inquire

as to which implementations of a standard library are, in fact,
reentrant inspite of the above ISO "not guaranteed" guideline? GNU?
Intel? M$?

Borland? etc?

Dunno. Frankly I would not count on any of them being reentrant. If you
_do_ find a reentrant version and count on that, someone, somewhere,
sometime is going to compile your program with some other
(non-reentrant) library.

And that's when the big, ugly brutes of bugs crawl out of the woodwork.
So (privately) I'll treat them *all* as being 'non-reentrant', which
has not been a major problem.

So you guys always use synchronized wrappers around stdlib functions? I
mean, common "operations" such as malloc, sprintf? That's news to me,
cause I haven't written a synchronized wrapper around a malloc, yet.
Consequently, my entire "c opus" ;-) is useless as far as
multi-threadedness is concerned? Bummer!

If you are writing multi-threaded programs you will probably be trying to
adhere to a standard such a POSIX threads. If this is the case you will
probably be working with a pthreads complaint standard c library in which
case you won't need wrapper functions for most standard functions the
library provides. GNU provides a posix-compliant standard library
including pthreads.

Rob Gamble

[xarax]

<th********@rediffmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com...

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant

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

[Robert Gamble]

On Tue, 11 Jan 2005 18:34:41 +0000, xarax wrote:

<th********@rediffmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com...

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant

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

And exactly what makes you think that he meant recursive?

Rob Gamble

[Richard Tobin]

In article <cs*********@cui1.lmms.lmco.com>,
Xenos <do**********@spamhate.com> wrote:

Maybe. Or maybe it's just an involuntary function call. It depends
on your interrupts.

Again, it doesn't matter. It's still a particular order of executing
instructions.

So is a function call a "thread of execution"? If so, you're just
referring to something different from the rest of us.

-- Richard

[E. Robert Tisdale]

Trent Buck wrote:

Sushant wrote:

Can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

This is re-entrant

int f(int x) {
int y = x*x;
return y;
}

This is not

int y;

int f (int x) {
y = x*x;
return y;
}

Another example of re-entrant vs. non-reentrant functions
is strtok_r vs. strtok.

As the OP said, it becomes an issue
when you have multiple threads (lightweight processes)
in a single process, because (some) state is shared
between multiple threads of execution.

The canonical example is

int x;
void f (void) { x++; }

with two threads executing f(). The ++ operation (typically) resolves
into three assembly instructions: copy-memory-to-register,
increment-register, and copy-register-to-memory.

Consider, for example, the situation where first thread executes
the first two instructions, then the second thread executes all three,
then the first thread executes the last instruction.
The second thread's change will be lost
and the contents of memory at that address will be incorrect.

This class of bugs are a PITA to locate
because symptoms are intermittent
and therefore difficult to reproduce.

The ANSI/ISO standards do *not* guarantee
that the first example above will be reentrant.
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.

[Neil Kurzman]

th********@rediffmail.com wrote:

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant

Look up the "tower of Honoi " The computer solution is very simple if
recursion is used.
recursive function are re-entrant.

Otherwise function used by multitasking, multithread, and interrupts
may have to be re-entrant.
since they may be paused in the middle and then call again.

[Eltee]

Lawrence Kirby wrote:

On Tue, 11 Jan 2005 16:43:03 +0100, Eltee wrote:

...

So you guys always use synchronized wrappers around stdlib functions? I mean,
common "operations" such as malloc, sprintf? That's news to me, cause I haven't
written a synchronized wrapper around a malloc, yet. Consequently, my entire "c
opus" ;-) is useless as far as multi-threadedness is concerned? Bummer!

If you use threads you will be using an environment that supports them as
an extension. That environment is also likely to support reentrant use of
various standard library functions as a related extension.

What worries me is something else. I have a lot of utility functions packed in
.... <cough /> ... shared objects. Those functions in turn, utilize standard
library functions, but without taking any care of (non)reentrancy. Now, I make
it a rule not to use any variables (dynamic or static) outside those functions.
Everything in a particular <cough /> so (dll) is either a parameter or a local
variable. Bottom line: if someone calls my functions from multiple threads
without synchronizing, the outcome might not be as expected. I'll have to take
care of synchronizing myself and not leave it to the caller.

[Lawrence Kirby]

On Wed, 12 Jan 2005 02:42:29 +0000, Neil Kurzman wrote:

th********@rediffmail.com wrote:

hi,

can anyone of C masters siting out there suggest any 1 example of
re-entrnt function just to show what is the significance of that
property and how we can exploit it ....

sushant
Look up the "tower of Honoi " The computer solution is very simple if
recursion is used.
recursive function are re-entrant.

Sometimes they are, but not always. Recursive functions call themselves
under very controlled circumstances. Reentrancy is a more general
principle than that.
Otherwise function used by multitasking, multithread, and interrupts
may have to be re-entrant.
since they may be paused in the middle and then call again.

Or maybe executed my multiple threads simultaneously.

Lawrence

[Guillaume]

>>recursive function are re-entrant.

Sometimes they are, but not always.
Huh? Give me one example of a recursive function that is not reentrant.
By definition, a recursive function will call itself at one point;
which makes it reentrant.
Recursive functions call themselves
under very controlled circumstances.
Which doesn't make them any more non-reentrant. ;-)
Reentrancy is a more general
principle than that.

That's right, of course! You named the multithreading case.
But there is more. A function can become recursive in a non-obvious
way (and that is one pitfall that some programmers will fall into
at one point or another): if it calls a function that calls another
function that... that ends up calling the first function.

In some programming languages, it could also be as simple as a
function calling itself in one of its arguments, such as:

array(array(1, 2), 3)

in some language that would construct a multi-dimensional array.

C does evaluate all of the arguments before calling the function, but
not all languages are like that.

[Xenos]

"Guillaume" <"grsNOSPAM at NOTTHATmail dot com"> wrote in message
news:41***********************@news.club-internet.fr...

recursive function are re-entrant.

Sometimes they are, but not always.

Huh? Give me one example of a recursive function that is not reentrant.
By definition, a recursive function will call itself at one point;
which makes it reentrant.

void foo()
{
static int i = 10;

/* do wacky stuff here */

if (--i > 0)
foo();
}

this ugly function is recursive, but not reentrant.

[Chris Torek]

In article <41***********************@news.club-internet.fr>
Guillaume <"grsNOSPAM at NOTTHATmail dot com"> wrote:

Huh? Give me one example of a recursive function that is not reentrant.
It is easy to construct an artificial example, although this sort
of thing is much less likely to occur in real code.
By definition, a recursive function will call itself at one point;
which makes it reentrant.
Not necessarily. Here is one example:

void pointless(int recurselevel, unsigned char c) {
static char *p;

if (recurselevel == 0)
p = malloc(UCHAR_MAX + 1);
if (c == 'Z') {
p[recurselevel] = '\0';
puts(p);
free(p);
} else {
p[recurselevel] = c;
pointless(recurselevel + 1, c + 1);
}
}

Recursive functions call themselves
under very controlled circumstances.

Which doesn't make them any more non-reentrant. ;-)

Unless, by accident or (as above) on purpose, they do something
"non-reentrant" at certain recursion levels.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Guillaume]

> void foo()

{
static int i = 10;

/* do wacky stuff here */

if (--i > 0)
foo();
}

this ugly function is recursive, but not reentrant.

It is reentrant, since it will reenter itself while still being inside
itself at a higher level. Whether it's harmful or not in this special
case is another story entirely. I don't see your point?

What is your definition of reentrancy?

[Alan Balmer]

On Wed, 12 Jan 2005 22:10:50 +0100, Guillaume <"grsNOSPAM at
NOTTHATmail dot com"> wrote:

void foo()
{
static int i = 10;

/* do wacky stuff here */

if (--i > 0)
foo();
}

this ugly function is recursive, but not reentrant.
It is reentrant, since it will reenter itself while still being inside
itself at a higher level.

Sounds like a definition of recursive, not reentrant.
Whether it's harmful or not in this special
case is another story entirely. I don't see your point?
By that definition, all functions are reentrant, since they can be
called twice.
What is your definition of reentrancy?

http://en.wikipedia.org/wiki/Reentrant

--
Al Balmer
Balmer Consulting
re************************@att.net

[Xenos]

"Guillaume" <"grsNOSPAM at NOTTHATmail dot com"> wrote in message
news:41***********************@news.club-internet.fr...

void foo()
{
static int i = 10;

/* do wacky stuff here */

if (--i > 0)
foo();
}

this ugly function is recursive, but not reentrant.

It is reentrant, since it will reenter itself while still being inside
itself at a higher level. Whether it's harmful or not in this special
case is another story entirely. I don't see your point?

What is your definition of reentrancy?

Just because the function calls itself does not make it reentrant. If it
were, it could be called by multiple threads, interrupts or whatever without
them affecting any other invocation. That is not the same as recursion.

[Keith Thompson]

Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes:

recursive function are re-entrant.

Sometimes they are, but not always.

Huh? Give me one example of a recursive function that is not reentrant.
By definition, a recursive function will call itself at one point;
which makes it reentrant.

Here's a contrived example:

#include <stdio.h>

static int recursive_but_not_reentrant(int n)
{
static int count = 0;
if (n <= 0) {
return count;
}
else {
count ++;
return recursive_but_not_reentrant(n - 1);
}
}

int main(void)
{
printf("recursive_but_not_reentrant(10) = %d\n",
recursive_but_not_reentrant(10));
printf("recursive_but_not_reentrant(10) = %d\n",
recursive_but_not_reentrant(10));
return 0;
}

Output:

recursive_but_not_reentrant(10) = 10
recursive_but_not_reentrant(10) = 20

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

Alan Balmer <al******@att.net> writes:

On Wed, 12 Jan 2005 22:10:50 +0100, Guillaume <"grsNOSPAM at
NOTTHATmail dot com"> wrote:

[...]

What is your definition of reentrancy?

http://en.wikipedia.org/wiki/Reentrant

<http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?query=reentrant&action=Search>
is also a good definition (and probably more relevant to the current
discussion).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Tobin]

In article <41***********************@news.club-internet.fr>,
Guillaume <"grsNOSPAM at NOTTHATmail dot com"> wrote:

It is reentrant, since it will reenter itself while still being inside
itself at a higher level.

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.

There doesn't even need another thread to be involved. Consider
a function sort() that works recursively, by calling itself on parts
of the array of items to sort. Such a function might not be designed
to work if the user-supplied comparison function itself calls sort(),
in which case it would not be re-entrant.

-- Richard

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

On Thu, 13 Jan 2005 02:13:07 +0100, Guillaume
<> wrote:

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.

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]

Chris Croughton wrote:

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]

On Thu, 13 Jan 2005 17:35:05 +0100, Guillaume wrote:

Chris Croughton wrote:

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!

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]

On Thu, 13 Jan 2005 17:35:05 +0100, Guillaume
<> wrote:

Chris Croughton wrote:

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

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

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.

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]

Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes:

Chris Croughton wrote:

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!

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]

In article <86************@gothmog.gr>, Giorgos Keramidas <ke******@ceid.upatras.gr> writes:

Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes:

Chris Croughton wrote:

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.)
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.
That means if we need to sort stuff in a multithreading application,
qsort is usually not an option? Bummers!

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 mi************@microfocus.com

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]

In article <41***********************@dreader8.news.xs4all.nl >,
dandelion <da*******@meadow.net> wrote:

"Trent Buck" <ge*******@tznvy.pbz> wrote in message
news:20*********************@harpo.marx...
<snip>

As the OP said, it becomes an issue when you have multiple threads
(lightweight processes) in a single process, because (some) state is
shared between multiple threads of execution.

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

--
Groetjes Albert
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.

[Keith Thompson]

Albert van der Horst <al****@spenarnc.xs4all.nl> writes:
[...]

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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.