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

[Ken Garlington <garlingtonke@lmtas.lmco.com>]

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"