System tasks are not re-entrant?

[Jonathan Bromley]

I got a nasty shock today when I found that system
functions such as $sformat are not re-entrant.
This is somewhat inconvenient. Consider, for
example, this simple recursive string reverser
in SystemVerilog:

function automatic string str_rev(string s);
string r;
if (s.len() < 2) return s;
$sformat(r, "%s%s",
s[s.len()-1],
str_rev(s.substr(0, s.len()-2)));
return r;
endfunction : str_rev

Two simulators silently give erroneous results;
a third sometimes reports the re-entrancy as an
error and sometimes segfaults, depending on the
exact details of the function. Moving the
recursive call of str_rev outside the call to
$sformat restores sanity at the cost of an
extra variable.

I can't find, anywhere in the 1364 or 1800 standards,
anything that says that these TFs are static. What
have I missed? Is this a shortcoming in the LRM, an
intentional piece of language definition for some
implementation-related reason, or a tool bug?
Is it, perhaps, that they are in effect PLI calls
and such calls have static storage for arguments
and return values?

Insights gratefully received.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jason Zheng]

Jonathan,

I don't see how this is a re-entrant problem of $sformat. $sformat is
never called recursively, rather, it's called in the following order:

$sformat(r, "%s%s", s[1], str_rev(s.substr(0, 0))
$sformat(r, "%s%s", s[2], str_rev(s.substr(0, 1))
$sformat(r, "%s%s", s[3], str_rev(s.substr(0, 2))
$sformat(r, "%s%s", s[4], str_rev(s.substr(0, 3))

(the exact substr parameter is probably not accurate, but you get the
idea).

On other words, you never had a $sformat call were you would depend on
re-entrant property of $sformat. You do, however, depend on the
re-entrant property of str_rev function itself. I think any sensible
simulator would do either of the two:

1. Make all system functions re-entrant
2. Make sure that no two instances of the same system function executes
at the same time.

Finally, I believe that your problem can be much better addressed by an
iteratively approach as opposed to a recursive approach. It's just more
efficient in execution and less confusing.

hth,

Jason Zheng

On Tue, 08 Apr 2008 16:31:11 +0100 Jonathan
Bromley <jonathan.bromley@MYCOMPANY.com> wrote:

I got a nasty shock today when I found that system
functions such as $sformat are not re-entrant.
This is somewhat inconvenient. Consider, for
example, this simple recursive string reverser
in SystemVerilog:

function automatic string str_rev(string s);
string r;
if (s.len() < 2) return s;
$sformat(r, "%s%s",
s[s.len()-1],
str_rev(s.substr(0, s.len()-2)));
return r;
endfunction : str_rev

Two simulators silently give erroneous results;
a third sometimes reports the re-entrancy as an
error and sometimes segfaults, depending on the
exact details of the function. Moving the
recursive call of str_rev outside the call to
$sformat restores sanity at the cost of an
extra variable.

I can't find, anywhere in the 1364 or 1800 standards,
anything that says that these TFs are static. What
have I missed? Is this a shortcoming in the LRM, an
intentional piece of language definition for some
implementation-related reason, or a tool bug?
Is it, perhaps, that they are in effect PLI calls
and such calls have static storage for arguments
and return values?

Insights gratefully received.

--
One doesn't have a sense of humor. It has you.
-- Larry Gelbart

 

[Jonathan Bromley]

On Tue, 8 Apr 2008 09:02:30 -0700, Jason Zheng wrote:

I don't see how this is a re-entrant problem of $sformat. $sformat is
never called recursively, rather, it's called in the following order:

But $sformat *is* called in a re-entrant manner, because
str_rev calls it again in order to evaluate arguments
for the call to $sformat that's further down the stack.

, str_rev(s.substr(0, 0))
$sformat(r, "%s%s", s[2], str_rev(s.substr(0, 1))
$sformat(r, "%s%s", s[3], str_rev(s.substr(0, 2))
$sformat(r, "%s%s", s[4], str_rev(s.substr(0, 3))

But $sformat will unwind the recursion correctly,
as you described, only if its argument storage
is automatic. I'm pretty sure it *is* the
argument storage that's causing trouble, because
re-ordering the arguments to $sformat can make
the problem appear to go away.

On other words, you never had a $sformat call were you would depend on
re-entrant property of $sformat.

The evidence is to the contrary.

You do, however, depend on the
re-entrant property of str_rev function itself.

Indeed so; but it *is* re-entrant because I declared it
automatic. A simple rewrite that leaves str_rev
calling itself recursively, but provides separate
storage for the result of the call to str_rev
rather than passing it directly as an argument to
$sformat, yields correct results because it explicitly
unwinds the $sformat calls precisely as you described.

I think any sensible
simulator would do either of the two:

1. Make all system functions re-entrant
2. Make sure that no two instances of the same system function executes
at the same time.

I totally agree, but two simulators fail to do either, and a
third does (2) unreliably.

Finally, I believe that your problem can be much better addressed by an
iteratively approach as opposed to a recursive approach.

Of course; I pruned the example to keep it small. I discovered
the trouble when coding a problem that lent itself much more
naturally to a recursive solution.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jason Zheng]

Jonathan,

I think there's a confusion in how this recursive call is unrolled.
Here's what I think:

1. call str_rev("abcd"), s="abcd"
2. s.substr(0, 2) is called, and returns "abc"
3. str_rev is called with s="abc"
4. s.substr(0, 1) is called, and returns "ab"
5. str_rev is called with s="ab"
6. s.substr(0, 0) is called and returns "a"
7. str_rev is called with s="a"
8. str_rev retuns "a", str_rev("a") finishes
9. $sformat is called, and returns, str_rev("ab") finishes
10. $sformat is called, and returns, str_rev("abc") finishes
11. $sformat is called, and returns, str_rev("abcd") finishes

As you can see, all calls to $sformat must evaluate their call
arguments BOFORE $sformat is invoked, therefore $sformat do not need to
be re-entrant. The key point is that if you want to make $sformat
recursive, you must call $sformat within the definition of $sformat.

hth,

Jason Zheng

On Tue, 08 Apr 2008 18:24:59 +0100 Jonathan Bromley
<jonathan.bromley@MYCOMPANY.com> wrote:

On Tue, 8 Apr 2008 09:02:30 -0700, Jason Zheng wrote:

I don't see how this is a re-entrant problem of $sformat. $sformat is
never called recursively, rather, it's called in the following order:

But $sformat *is* called in a re-entrant manner, because
str_rev calls it again in order to evaluate arguments
for the call to $sformat that's further down the stack.

$sformat(r, "%s%s", s[1], str_rev(s.substr(0, 0))
$sformat(r, "%s%s", s[2], str_rev(s.substr(0, 1))
$sformat(r, "%s%s", s[3], str_rev(s.substr(0, 2))
$sformat(r, "%s%s", s[4], str_rev(s.substr(0, 3))

But $sformat will unwind the recursion correctly,
as you described, only if its argument storage
is automatic. I'm pretty sure it *is* the
argument storage that's causing trouble, because
re-ordering the arguments to $sformat can make
the problem appear to go away.

On other words, you never had a $sformat call were you would depend
on re-entrant property of $sformat.

The evidence is to the contrary.

You do, however, depend on the
re-entrant property of str_rev function itself.

Indeed so; but it *is* re-entrant because I declared it
automatic. A simple rewrite that leaves str_rev
calling itself recursively, but provides separate
storage for the result of the call to str_rev
rather than passing it directly as an argument to
$sformat, yields correct results because it explicitly
unwinds the $sformat calls precisely as you described.

I think any sensible
simulator would do either of the two:

1. Make all system functions re-entrant
2. Make sure that no two instances of the same system function
executes
at the same time.

I totally agree, but two simulators fail to do either, and a
third does (2) unreliably.

Finally, I believe that your problem can be much better addressed by
an iteratively approach as opposed to a recursive approach.

Of course; I pruned the example to keep it small. I discovered
the trouble when coding a problem that lent itself much more
naturally to a recursive solution.

--
One doesn't have a sense of humor. It has you.
-- Larry Gelbart

 

[Jason Zheng]

On Tue, 08 Apr 2008 18:24:59 +0100
Jonathan Bromley <jonathan.bromley@MYCOMPANY.com> wrote:

On other words, you never had a $sformat call were you would depend
on re-entrant property of $sformat.

The evidence is to the contrary.

I believe that your evidence points to not a problem with $sformat, but
to the automatic keyword for str_rev. In other words, your simulators
does not have 100% re-entrance support. Remember $sformat doesn't
allocate r; it is your task str_rev that allocates the string variable
r.

I think all three of the simulators that you run share the common
trait: they cannot dynamically allocate strings on stacks. They either
don't support it or are not supporting it correctly due to the nature
of string being arrays. Arrays are sometimes too big to fit in a stack
frame due to frame size limitations of the compiler. Some common
approaches include using heaps to allocate arrays and storing pointers
on the stacks only.

~Jason

--
One doesn't have a sense of humor. It has you.
-- Larry Gelbart

 

[Jason Zheng]

Thanks for that explanation! I didn't realize that $sformat could use
callbacks. So if that's causing the problem, I propose the following
test case:

function automatic string str_rev(string s);
string r;
string tmp;
if (s.len() < 2) return s;
tmp = str_rev(s.substr(0, s.len()-2);
$sformat(r, "%s%s",s[s.len()-1], tmp);
return r;
endfunction : str_rev

If the new test case eliminates the problem, then I concede my point.
Sorry I can't run this test myself, since 1) I don't have access to the
same simulators that Jonanthan used and 2) I don't have access to any
SystemVerilog simulator.

~Jason Zheng

On Tue, 8 Apr 2008 17:35:31 -0700 (PDT) sharp@cadence.com wrote:

On Apr 8, 1:46 pm, Jason Zheng <Xin.Zh...@jpl.nasa.gov> wrote:

As you can see, all calls to $sformat must evaluate their call
arguments BOFORE $sformat is invoked, therefore $sformat do not
need to be re-entrant. The key point is that if you want to make
$sformat recursive, you must call $sformat within the definition of
$sformat.

For a normal function call, I would agree with you. This would not be
an example of recursion, just an example of function composition with
itself. The arguments would all be evaluated first, and then be
passed to the call. This can still lead to trouble if the
implementation tries to pass each argument into a static formal as
soon as it is computed, instead of computing them all first before
passing any, but the problem is not due to recursion.

However, this is a Verilog system function. It is likely that
implementations are using the same PLI infrastructure that is used for
user-defined system functions. One feature of PLI user-defined system
tasks/functions is that arguments are not evaluated until the task/
function implementation requests it. This is essential in some
cases. A system task/function can save a handle to an argument
expression somewhere, and PLI code executing later can ask for the
*current* value of that argument, not the value when it was first
passed. The task may do things with the argument other than asking
for its value, such as setting callbacks on variables to get notified
if the variable changes.

As an example, consider trying to write your own version of the
$monitor task. It would only be called once to set up the
monitoring. The task would have to set up callbacks on all the
objects being monitored. Then each time a value change callback
occurred, it would have to request a callback at the end of the time
slice, and then print out the current value of the arguments. There
is no way this could be made to work if the task were just passed the
values of the actual arguments at the time it was called.

With this assumption that the arguments are being evaluated when
requested by the function implementation, this usage DOES involve
recursive calls to the function implementation. The recursion will
involve calling PLI code, which requests an evaluation that requires
going back into the simulator, which then has to call the system task
recursively, going back out of the simulator into PLI code, making a
nested request for an evaluation that requires going back into the
simulator before the last request has finished, etc. I am not at all
surprised that this is causing problems. The infrastructure to
support exiting and re-entering the simulators were probably never
designed to be re-entrant. Recall that the Verilog function could not
have been re-entrant at the time that the infrastructure was probably
designed, so such usage would have run into trouble on the Verilog
side anyway.

--
One doesn't have a sense of humor. It has you.
-- Larry Gelbart

 

On Apr 8, 1:46 pm, Jason Zheng <Xin.Zh...@jpl.nasa.gov> wrote:

As you can see, all calls to $sformat must evaluate their call
arguments BOFORE $sformat is invoked, therefore $sformat do not need to
be re-entrant. The key point is that if you want to make $sformat
recursive, you must call $sformat within the definition of $sformat.

For a normal function call, I would agree with you. This would not be
an example of recursion, just an example of function composition with
itself. The arguments would all be evaluated first, and then be
passed to the call. This can still lead to trouble if the
implementation tries to pass each argument into a static formal as
soon as it is computed, instead of computing them all first before
passing any, but the problem is not due to recursion.

However, this is a Verilog system function. It is likely that
implementations are using the same PLI infrastructure that is used for
user-defined system functions. One feature of PLI user-defined system
tasks/functions is that arguments are not evaluated until the task/
function implementation requests it. This is essential in some
cases. A system task/function can save a handle to an argument
expression somewhere, and PLI code executing later can ask for the
*current* value of that argument, not the value when it was first
passed. The task may do things with the argument other than asking
for its value, such as setting callbacks on variables to get notified
if the variable changes.

As an example, consider trying to write your own version of the
$monitor task. It would only be called once to set up the
monitoring. The task would have to set up callbacks on all the
objects being monitored. Then each time a value change callback
occurred, it would have to request a callback at the end of the time
slice, and then print out the current value of the arguments. There
is no way this could be made to work if the task were just passed the
values of the actual arguments at the time it was called.

With this assumption that the arguments are being evaluated when
requested by the function implementation, this usage DOES involve
recursive calls to the function implementation. The recursion will
involve calling PLI code, which requests an evaluation that requires
going back into the simulator, which then has to call the system task
recursively, going back out of the simulator into PLI code, making a
nested request for an evaluation that requires going back into the
simulator before the last request has finished, etc. I am not at all
surprised that this is causing problems. The infrastructure to
support exiting and re-entering the simulators were probably never
designed to be re-entrant. Recall that the Verilog function could not
have been re-entrant at the time that the infrastructure was probably
designed, so such usage would have run into trouble on the Verilog
side anyway.

 

[Jonathan Bromley]

On Tue, 8 Apr 2008 18:22:48 -0700, Jason Zheng wrote:

Thanks for that explanation! I didn't realize that $sformat could use
callbacks. So if that's causing the problem, I propose the following
test case:

function automatic string str_rev(string s);
string r;
string tmp;
if (s.len() < 2) return s;
tmp = str_rev(s.substr(0, s.len()-2);
$sformat(r, "%s%s",s[s.len()-1], tmp);
return r;
endfunction : str_rev

If the new test case eliminates the problem

It does; that's exactly what I meant when I spoke of
evaluating str_rev independently of the arguments to
$sformat.

I think you (and Steven) are exactly right in saying
that $sformat is not strictly called recursively,
but note that - in at least some of the possible
orderings of evaluation - the problem I describe
could be explained simply by $sformat having
statically allocated argument variables, like
any other traditional Verilog function.

So, my apologies for the red herring about
recursion of $sformat - you are surely correct that
the *body* of $sformat cannot be recursive. But
the function preamble - the evaluation of its
arguments, and the planting of them into wherever
the function expects to see them - definitely
suffers from lack of re-entrancy.

I absolutely do not believe Jason's hypothesis
about automatic functions not handling strings
correctly - I can't find any evidence for such
an issue, and it would be bizarre if three quite
independent implementations were all to suffer the
same problem.

Thanks to you both for the interesting input.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Jonathan Bromley]

On Tue, 8 Apr 2008 17:35:31 -0700 (PDT), sharp@cadence.com wrote:

[the code I presented]

can still lead to trouble if the
implementation tries to pass each argument into a static formal as
soon as it is computed, instead of computing them all first before
passing any, but the problem is not due to recursion.

Indeed. I should have been more careful in my mention of
"recursion". The problem is lack of re-entrancy, which is
not exactly the same thing.

However, this is a Verilog system function. It is likely that
implementations are using the same PLI infrastructure that is
used for user-defined system functions.

OK, that's what I feared. Thanks.

With this assumption that the arguments are being evaluated when
requested by the function implementation, this usage DOES involve
recursive calls to the function implementation. The recursion will
involve calling PLI code, which requests an evaluation that requires
going back into the simulator, which then has to call the system task
recursively, going back out of the simulator into PLI code, making a
nested request for an evaluation that requires going back into the
simulator before the last request has finished, etc. I am not at all
surprised that this is causing problems. The infrastructure to
support exiting and re-entering the simulators were probably never
designed to be re-entrant. Recall that the Verilog function could not
have been re-entrant at the time that the infrastructure was probably
designed, so such usage would have run into trouble on the Verilog
side anyway.

Yes indeed, but things have moved on and it may be appropriate
to revisit these issues at some point. Given that $sformat and
many others look like innocent function calls, and given that
much SystemVerilog code (notably, that in classes) defaults
to "automatic" behaviour, and given that at least two simulators
(not yours) appear to make no attempt to detect the re-entrant
invocation of $sformat, this at least rates a mention as a "gotcha".

Thanks
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.