Re: Changing discriminants at run-time: erroneous execution?

Re: Changing discriminants at run-time: erroneous execution?

[Robert A Duff]

In article <lhmg25z8v2x.fsf@berlin.berlin.informatik.uni-stuttgart.de>,
Andre Spiegel  <spiegel@berlin.informatik.uni-stuttgart.de> wrote:
>The following program prints a strange result (using GNAT 3.05 under
>Ultrix), as indicated in the comments.  I know that this is not the
>recommended way to create dynamic arrays, but I'm actually surprised
>that the program passes the compiler (warning at line 8: "creation of
>object of this type may raise Storage_Error"), and then silently
>produces a wrong result at runtime.

You probably have stack overflow (Storage_Error) checking turned off.  I
think it's off by default -- check the docs.  The warning isn't kidding
-- GNAT will allocate the max size for this sort of record.  Since the
RM doesn't say anything about how much storage is allocated for
anything, GNAT is well within its rights to allocate the max.

And if you have a check turned off, and violate that check, it's
erroneous.

So long as GNAT provides some way of turning on the checks, it is OK.
(I would prefer that all checks be on by default, but the ACT folks say
it's too inefficient.  In any case, the RM doesn't say anything about
that.)

You probably already know this, but you might want to check out the
Strings.Bounded package.

>       type Buffer (Size : Natural := 3) is

Declare a more reasonable size here.  E.g.:

    type Size_Type is range 0..100;
    type Buffer (Size: Size_Type := 3) is ...

>          record
>             Value : String (1..Size);
>          end record;
>
>       Message : Buffer;

>But 3.7.2(4) goes on to say
>
>    The execution of a construct is erroneous if the construct has a
>    constituent that is a name denoting a subcomponent that depends on
>    discriminants, and the value of any of these discriminants is changed
>    by this execution between evaluating the name and the last use 
>    (within this execution) of the subcomponent denoted by the name.
>
>Does this apply in the above situation?

No.  This is a much more obscure case -- things like:

   function F return Character is
   begin
      Message := (Size => 2, Value => "xx"); -- Evil side effect!
      return '*';
   end F;

   Message.Value(3) := F; -- Erroneous.
    
>...  It is clear that the run-time
>system would have to do silent heap allocation to support "resizing"
>the array, but if it is not prepared to do so (as GNAT seems to be),
>why is the erroneous execution permitted by the RM?

Some compilers do the silent heap allocation, some do not.  GNAT does
not.  In portable code, you will have to assume an allocate-the-max
implementation.  There have been discussions in the past about which
implementation approach is better.

>The interesting thing is that Barnes' Ada 95 book has examples that
>use this precise "feature" (dynamic resizing of arrays, pp. 340).  It
>doesn't note any potential problems.  Also, the example RM 3.7.1 (15) 
>at least *suggests* that "resizing" such arrays should work:
>
>       Message : Buffer;    --  unconstrained, initially 100 characters
>                            --   (default discriminant value)

In your example, the max size is 2**31-1 characters.  In this RM
example, the maximum size of the inner array is 500 characters.  So it's
not surprising that one raises S_E and the other doesn't.  ;-)  I don't
have Barnes' book in front of me, but it should have a similar limit.

By the way, the RM example is scattered across four sections: 3.3.2(10),
3.5.4(35), 3.7(33), and 3.7.1(15).  I tracked it all down using the
Index.

- Bob

Re: Changing discriminants at run-time: erroneous execution?

[Robert Dewar]

Andre asks about the program

    with Ada.Text_IO;
    use  Ada.Text_IO;

    procedure Example is

       type Buffer (Size : Natural := 3) is
          record
             Value : String (1..Size);
          end record;

       Message : Buffer;
       X       : Integer;

    begin
       Message := (5, "abcde");
       Put_Line (Message.Value);  -- prints "abcde"
       X := 1;
       Put_Line (Message.Value);  -- prints "abcd"
    end Example;

The warning should not be ignored. Creating of a value of type Buffer requires
4 gigabytes of storage. This might work on some 64 bit machines, but will
surely not work on a 32-bit machine.

So why don't you get the storage error -- that's easily explained, you
are using one of the versions of GNAT that does not yet support stack
checking, and so of course this object overflowed the stack.

This behavior is not justified by the RM! This is a simply a matter of
a (documented) missing feature in some implementations of GNAT (we are
gradually adding stack checking to additional verisons of GNAT, it's
one of the hard things to do for a highly portable technology like this,
because stack checking tends to be extremely target dependent).

Always read the file "features" to find out what is implemented and
what is not!

Re: Changing discriminants at run-time: erroneous execution?

[Robert Dewar]

iBob said

"So long as GNAT provides some way of turning on the checks, it is OK.
(I would prefer that all checks be on by default, but the ACT folks say
it's too inefficient.  In any case, the RM doesn't say anything about
that.)"

Wrong tree!

This is not a matter of a check that is off by default, it is a matter of
an unimplemented check. In implementations of GNAT which support stack
checking, stack checking is always turned on, and in fact cannot be turned
off at all (since it has essentially no overhead, there is no point in letting
it be turned off).

Changing discriminants at run-time: erroneous execution?

[Andre Spiegel]

The following program prints a strange result (using GNAT 3.05 under
Ultrix), as indicated in the comments.  I know that this is not the
recommended way to create dynamic arrays, but I'm actually surprised
that the program passes the compiler (warning at line 8: "creation of
object of this type may raise Storage_Error"), and then silently
produces a wrong result at runtime.


    with Ada.Text_IO;
    use  Ada.Text_IO;

    procedure Example is

       type Buffer (Size : Natural := 3) is
          record
             Value : String (1..Size);
          end record;

       Message : Buffer;
       X       : Integer;

    begin
       Message := (5, "abcde");
       Put_Line (Message.Value);  -- prints "abcde"
       X := 1;
       Put_Line (Message.Value);  -- prints "abcd"
    end Example;


Is this behaviour justified by the RM?  Relevant passages are

3.7.2(1)

    If a discriminated type has default_expressions for its discriminants,
    then unconstrained variables of the type are permitted, and the
    discriminants of such a variable can be changed by assignment to the
    variable.

But 3.7.2(4) goes on to say

    The execution of a construct is erroneous if the construct has a
    constituent that is a name denoting a subcomponent that depends on
    discriminants, and the value of any of these discriminants is changed
    by this execution between evaluating the name and the last use 
    (within this execution) of the subcomponent denoted by the name.

Does this apply in the above situation?  It is clear that the run-time
system would have to do silent heap allocation to support "resizing"
the array, but if it is not prepared to do so (as GNAT seems to be),
why is the erroneous execution permitted by the RM?

The interesting thing is that Barnes' Ada 95 book has examples that
use this precise "feature" (dynamic resizing of arrays, pp. 340).  It
doesn't note any potential problems.  Also, the example RM 3.7.1 (15) 
at least *suggests* that "resizing" such arrays should work:

       Message : Buffer;    --  unconstrained, initially 100 characters
                            --   (default discriminant value)

What do the language lawyers say?

Re: Changing discriminants at run-time: erroneous execution?

[Andre Spiegel]

Thanks to all who replied to my question, both here and in private
e-mail.  I think I understand the issue now.  In summary, it *is*
possible to "resize" arrays via discriminants, but compilers normally
achieve this by allocating an object of the maximum possible size.  So
using an array index of type Natural almost certainly fails, leading
to a stack overflow.  I should use a subtype, maybe of range 1..500 or
some such.

We got bitten by a yet-unimplemented feature in GNAT; so that the
problem was not reported by the run-time system -- which should
normally happen.

Anyway, I normally allocate dynamic arrays on the heap, or declare
them only after the bounds are known, so I hadn't come across this
problem yet.  Also, for dynamic _strings_, the standard libraries
Ada.Strings.Bounded/Unbounded are the way to go, of course.  The issue
was raised by programs that somebody else in our group had written; I
looked at these programs, and I really had no idea why they failed so
mysteriously.

Thanks again to everyone,

Andre Spiegel
University of Stuttgart, Germany

Re: Mandatory stack check (was: Changing discriminants...)

[Robert A Duff]

In article <3209AC29.3E21@lmtas.lmco.com>,
Ken Garlington  <garlingtonke@lmtas.lmco.com> wrote:
>Interesting. Does stack checking typically introduce an extra branch in the
>object code?

I think the implementation Robert is talking about is one that relies on
page-level protection done by the hardware (and hence near-zero cost).
I.e. set the protection of the page just beyond the stack to "no
access", so any reference to it will trap.  So no, it's not an explicit
branch instruction.

The reason this is not implemented in all versions of GNAT is, no doubt,
the fact that the mechanisms for accessing the page tables and whatnot
is different across different operating systems, and across different
hardware.  And gcc, and therefore GNAT, are very reluctant to do damage
to portability (else, how could they support so many targets?).

Also, the code generator has to be pretty careful to get it right.
Suppose, for example, I reference Some_Array(I), and I happens to be
10**9.  Well, that might well get past the protected page, and write
upon some other task's stack.

>... If so, then someone with a requirement to test every object-code
>branch point would have to introduce a test to force a stack overflow for each
>affected code segment (including elaboration), or have to justify why the
>overflow check didn't need to be tested. That could be a little annoying...

Well, this is true in any case.  It doesn't really matter (for testing)
whether stack overflow is detected by an explcit instruction, or by page
protection (causing an implicit jump into the OS).  Either way, if you
want to test all possibilities, you have to worry about it.

The RM says *anything* can raise Storage_Error, which means the amount
of testing involved would be infeasible.  Instead, I think people who
really care about that sort of thing do low-level analysis of the object
code to ensure that Storage_Error is impossible.  This requires using a
subset of the full Ada language.

Note that handling Storage_Error and trying to recover is rather
questionable.  Since anything can raise S_E, and since 11.6 allows the
compiler to play all kinds of tricks, you essentially have to assume
that lots of data structures will be destroyed (see "abnormal" in the
RM) in case of S_E.  And if your data structures are destroyed, what can
you do safely after handling S_E?  It is probably possible to write it
correctly, but most programmers don't understand 11.6(6) deeply enough
to do so, and most programmers are not inclined to worry about it, since
for most programs, it's fine to consider S_E to be a catastrophic
failure that just kills the program.

- Bob

Mandatory stack check (was: Changing discriminants...)

[Ken Garlington]

Robert Dewar wrote:
> 
> This is not a matter of a check that is off by default, it is a matter of
> an unimplemented check. In implementations of GNAT which support stack
> checking, stack checking is always turned on, and in fact cannot be turned
> off at all (since it has essentially no overhead, there is no point in letting
> it be turned off).

Interesting. Does stack checking typically introduce an extra branch in the
object code? If so, then someone with a requirement to test every object-code
branch point would have to introduce a test to force a stack overflow for each
affected code segment (including elaboration), or have to justify why the
overflow check didn't need to be tested. That could be a little annoying...

-- 
LMTAS - "Our Brand Means Quality"

Re: Mandatory stack check (was: Changing discriminants...)

[Robert Dewar]

Ken said

"Interesting. Does stack checking typically introduce an extra branch in the
object code? If so, then someone with a requirement to test every object-code
branch point would have to introduce a test to force a stack overflow for each
affected code segment (including elaboration), or have to justify why the
overflow check didn't need to be tested. That could be a little annoying..."

Right, that would be a real disadvantage of the branch based approach. Our
approach is to map out a page at the end of the stack and catch the
reference (there are quite a few fine points to get this to work right, and
it tends to be quite taget dependent).

I would have thought that anyone with a requirement to test every object-code
branch point would also include requirements to verify that the stack cannot
overflow, but perhaps not!

Re: Changing discriminants at run-time: erroneous execution?

[Robert Dewar]

Andre said

"We got bitten by a yet-unimplemented feature in GNAT; so that the
problem was not reported by the run-time system -- which should
normally happen."

Quite true, although GNAT *did* print a big warning message, which you
ignored! The warnings in GNAT should not usually be ignored :-)

Re: Mandatory stack check (was: Changing discriminants...)

[Ken Garlington]

Robert A Duff (and Robert Dewar) wrote:
> 
> I think the implementation Robert is talking about is one that relies on
> page-level protection done by the hardware (and hence near-zero cost).
> I.e. set the protection of the page just beyond the stack to "no
> access", so any reference to it will trap.  So no, it's not an explicit
> branch instruction.

Does this mean that the check could be suppressed on CPUs that didn't have
this feature? If so, then I wouldn't see a problem.

I assume also that the stacks have to be aligned on a page boundary. Is this
automatic in GNAT?

Just out of curiosity, how is the heap checked?

> >... If so, then someone with a requirement to test every object-code
> >branch point would have to introduce a test to force a stack overflow for each
> >affected code segment (including elaboration), or have to justify why the
> >overflow check didn't need to be tested. That could be a little annoying...
> 
> Well, this is true in any case.  It doesn't really matter (for testing)
> whether stack overflow is detected by an explcit instruction, or by page
> protection (causing an implicit jump into the OS).  Either way, if you
> want to test all possibilities, you have to worry about it.

Actually, there's a subtle distinction here:

1. You do have to analyze for the possibility of stack overflow in all cases. 
However, if you know the calling sequence, and the stack frame allocated by each 
call (I'm assuming no heap calls, which is usually the case for our applications), 
and if you can bound the sequence in all cases, you can do a global analysis for 
the program threads and show that no stack overflow can occur. Tools are a good 
thing to have to support this analysis, BTW.

2. Even if there is a possibility of stack overflow, if you are using hardware
mechanisms to implement stack checks (no software involved), you can usually do
a global-level analysis to show that the hardware mechanism will work reliably.

3. The problem occurs when you are using a software mechanism that is embedded in 
individual program units (e.g. elaboration code for a package, or body code for a 
subprogram). There's no way to do a single global analysis to show that this code 
works, as in either of the cases shown above. You have to slog through each 
instance of that code in each unit, to make sure it calls the right handler at the 
right time. What's worse, if you've done the analysis in #1, and you are confident 
that no stack overflow can occur, then you still have to show that this code is not 
activated for any reason other than a real stack overflow. Also, if you have a 
requirement to test all branch points in the object code, you either have to test 
that the code in each unit would handle the stack overflow (that will never occur), 
or go through the process to document that the test is not necessary. In the case 
where (a) no stack overflow will occur and/or (b) you have a hardware mechanism to 
catch any overflow, it is sometimes desirable to suppress the check and eliminate 
the code, to allow the test team to concentrate on other, higher-payoff tests.

> The RM says *anything* can raise Storage_Error, which means the amount
> of testing involved would be infeasible.  Instead, I think people who
> really care about that sort of thing do low-level analysis of the object
> code to ensure that Storage_Error is impossible.  This requires using a
> subset of the full Ada language.

Yes, I am talking about object-level analysis here. We do quite a bit of this.

> Note that handling Storage_Error and trying to recover is rather
> questionable.  Since anything can raise S_E, and since 11.6 allows the
> compiler to play all kinds of tricks, you essentially have to assume
> that lots of data structures will be destroyed (see "abnormal" in the
> RM) in case of S_E.  And if your data structures are destroyed, what can
> you do safely after handling S_E?  It is probably possible to write it
> correctly, but most programmers don't understand 11.6(6) deeply enough
> to do so, and most programmers are not inclined to worry about it, since
> for most programs, it's fine to consider S_E to be a catastrophic
> failure that just kills the program.

Actually, with some knowledge of how the specific Ada implementation causes
Storage_Error, and by subsetting the language, you _might_ implement some 
(non-portable) recovery actions. And, as the Ariane 5 failure points out,
recovery _may_ be a Good Thing :)

Of course, if there's _nothing_ you can do to handle Storage_Error, then
why have code lurking in your application that raises it (possibly when
you _don't_ want it raised)?

-- 
LMTAS - "Our Brand Means Quality"

Re: Mandatory stack check (was: Changing discriminants...)

[Robert A Duff]

In article <320F0DD1.7A66@lmtas.lmco.com>,
Ken Garlington  <garlingtonke@lmtas.lmco.com> wrote:
>Does this mean that the check could be suppressed on CPUs that didn't have
>this feature? If so, then I wouldn't see a problem.

I'm not sure what you're asking.  Yes, you can suppress the checks.
Whether or not the implementation actually does anything about it, is up
to the implementation.  As Robert explained, GNAT doesn't do these
checks at all (yet) on most targets, so there's nothing to suppress.

I don't know if GNAT runs on any CPU's that don't have hardware memory
mapping support.

>I assume also that the stacks have to be aligned on a page boundary. Is this
>automatic in GNAT?

Probably.

>Just out of curiosity, how is the heap checked?

That's typically done using explicit code, I think.  As usual, I'm not
talking about GNAT in particlar here -- just what I know about how these
things are done in various compilers.

>2. Even if there is a possibility of stack overflow, if you are using
>hardware mechanisms to implement stack checks (no software involved),
>you can usually do a global-level analysis to show that the hardware
>mechanism will work reliably.

You can easily show that the mechanism jumps to the handler it's
supposed to, and cleans up the stack properly.  However, it seems to me
that it's a bit harder to prove anything about what that handler code
does -- its precondition is essentially "false".  That is, the handler
can't assume much of anything about the state of the program variables.
I suppose it could just zero memory and start the program over, which
might be appropriate in *some* cases.

>Of course, if there's _nothing_ you can do to handle Storage_Error, then
>why have code lurking in your application that raises it (possibly when
>you _don't_ want it raised)?

Well, there's one thing that you can do -- kill the program.  This is
the default behavior, and for most programs, is vastly superior to
overwriting random memory and so forth.  For a rocket, though, killing
the program and overwriting memory might well both be unacceptable.

- Bob

Re: Mandatory stack check (was: Changing discriminants...)

[Ken Garlington]

Robert A Duff wrote:
> 
> I'm not sure what you're asking.  Yes, you can suppress the checks.
> Whether or not the implementation actually does anything about it, is up
> to the implementation.  As Robert explained, GNAT doesn't do these
> checks at all (yet) on most targets, so there's nothing to suppress.

Perhaps I misunderstood. I thought that when GNAT implemented this check,
it would implement it using hardware memory mapping support and thus
suppressing it would have no effect AFTER implementation, either. My
question was: what happens for GNAT running on a CPU where code is needed
to do the check? Will such implementations support supressing the generation
of this code?

> I don't know if GNAT runs on any CPU's that don't have hardware memory
> mapping support.

Possibly not today - but I assume GNAT attempts to minimize hardware-specific
assumptions in its interface to the GNU back end. Would, for example, this mean 
that porting GNAT to an architecture that already had GNU support, but
did not have hardware support for stack overflow, would be more complicated
(require more GNAT changes) than porting to an architecture with such hardware
support?

> You can easily show that the mechanism jumps to the handler it's
> supposed to, and cleans up the stack properly.

Easy for you, maybe! In my experience, you have to locate the checks,
see if they set up any parameters to the handler correctly, and then do
the jump correctly. And, you have to do this for each unit, and regression
test it for each change to that unit. Most importantly, you have to do this at 
the object code level. No fun at all!

> However, it seems to me
> that it's a bit harder to prove anything about what that handler code
> does -- its precondition is essentially "false".  That is, the handler
> can't assume much of anything about the state of the program variables.
> I suppose it could just zero memory and start the program over, which
> might be appropriate in *some* cases.

At least with the compiler I'm faimilar with, the handler for Storage_Error
is a single unit of code in the RTS. It's usually a pretty simple piece of
code, at that. So, testing the handler is not the issue. It's making sure
that the handler isn't called when it shouldn't be, or an attempt to call it
ends up actually calling something else, or a call to the handler passes
bad data, etc. that's the trickier part. And, usually, that stuff is sprinkled
throughout the application, unless you suppress the check (or the check takes
no code in the first place to be raised).

> >Of course, if there's _nothing_ you can do to handle Storage_Error, then
> >why have code lurking in your application that raises it (possibly when
> >you _don't_ want it raised)?
> 
> Well, there's one thing that you can do -- kill the program.

Right -- but that means there is _something_ you can do! If you can't
reasonably kill/restart the program, and you can't reliably react to it in any 
other way, then it seems to me a better use of resources to attempt to avoid the
condition in the first place, rather than attempt to handle the
unhandle-able.

For example, I've seen systems that do the following:

1. Suppress range checking.
2. Put in a handler for the hardware overflow interrupt that simply returns
   to the next instruction.

What this effectively does is ignore range checking. If an out-of-range value
is generated, that bad value is used in subsequent calculations, memory accesses,
etc. This may sound stupid, but having an incorrect output generated in one
calculation cycle (assuming the error is due to a hardware glitch, not a software 
fault) might be preferable to attempting to provide a "safe" value, or 
killing/restarting the program, etc. This is particularly true if there is an 
operator in the loop who can distinguish a "hard" failure from a transient.

Of course, the key to doing something like this is performing adequate analysis.
You have to convince yourself that this is preferable to attempting to handle the 
error using Ada exceptions.

-- 
LMTAS - "Our Brand Means Quality"