Memory overwrite?

Memory overwrite?

[Rick Wouters]

	An Ada program which compiles correctly and which does not produce
	run-time errors seems to overwrite memory.
	No dynamic allocation is used nor are address types used.
	Some records are defined with a length clause.

	Environment: VADS 6.0 on Sun4

	Does anyone know a reason which might result in overwriting memory
	in a correctly compiled program?


Because I'm posting this for a good friend, please send reply to:

	dc691@hgl.signaal.nl


Thanks,

Rick.

Re: Memory overwrite?

[Mark A Biggar]

In article <3fe5cp$fnq@theopolis.orl.mmc.com> "Theodore E. Dennison" <dennison@escmail.mmc.orl.com> writes:
>wouters@ict.nl (Rick Wouters) wrote:
>> 	An Ada program which compiles correctly and which does not produce
>> 	run-time errors seems to overwrite memory.
>> 	No dynamic allocation is used nor are address types used.
>> 	Some records are defined with a length clause.
>> 	Does anyone know a reason which might result in overwriting memory
>> 	in a correctly compiled program?
>Tons. Most of the time when this happens it is because someone 
>screwed up a "for use at" clause or an "UNCHECKED_CONVERSION" from
>System.ADDRESS.

Actually the most likely reason for this is an uninitialized variable used
as an array index.  In Ada 83 the following code fragment can write anywhere
in memory and may well not raise an exception:

declare
	subtype index is integer range 1..10;
	type table is array (index) of integer;
	a: table;
	i: index;
begin
	a(i) := 0;
end;

An aggressive optimizer will eliminate any checks from the above code.
Even putting an explisit if statement around it doesn't help:

	if i in index then
		a(i) := 0;
	else
		raise constraint_error;
	end if;

because an aggressive optimizer will notice that the if test is always true
(in the absence of uninitialized variables, but uninitialized variables
are erroneous, which allow any behaviour, so it can ignore the problem)
and eliminate the test and the else branch completely.

Ada95 add the 'valid attribute to handle this problem.

--
Mark Biggar
mab@wdl.lroal.com

Re: Memory overwrite?

[Robert Dewar]

In response to Mark, worrying about out of array stores in Ada 83, this
is fixed in Ada 95, where the check cannot be elided in the case he
worries about.

Memory overwrite?

[R.A.L Williams]

In article <1995Jan18.182039.7324@wdl.loral.com> Mark Biggar wrote:

[original post and a reply deleted]

: Actually the most likely reason for this is an uninitialized variable used
: as an array index.  In Ada 83 the following code fragment can write anywhere
: in memory and may well not raise an exception:

: declare
: 	subtype index is integer range 1..10;
: 	type table is array (index) of integer;
: 	a: table;
: 	i: index;
: begin
: 	a(i) := 0;
: end;

: An aggressive optimizer will eliminate any checks from the above code.
: Even putting an explisit if statement around it doesn't help:

OK, I can see how an optimiser *could* do that, and, of course, RM9x
section 3.3.1 says that 'There is no implicit initial value defined
for a scalar subtype ... might have a value which does not belong to
that subtype' (para 21). I'm a little suprised, however, that the
compiler isn't expected to perform a simple data flow analysis and
generate a warning about use of uninitialised variables. You're quite
right though, I can't find anything in RM9x which says it should, and
I'm pretty sure there was nothing in the Ada83 LRM.

: 	if i in index then
: 		a(i) := 0;
: 	else
: 		raise constraint_error;
: 	end if;

: because an aggressive optimizer will notice that the if test is always true
: (in the absence of uninitialized variables, but uninitialized variables
: are erroneous, which allow any behaviour, so it can ignore the problem)
: and eliminate the test and the else branch completely.

GCC can tell me about the possible use of uninitialised variables. It 
produces a warning because the analysis is not sophisticated enough to
follow all the possible paths. Can GNAT do this as well ? Perhaps I'll
try your example out with GNAT and see what it does.

: Ada95 add the 'valid attribute to handle this problem.

Yes, this is a good idea. In another thread I've been gently pushing
the notion that use of Ada does not eliminate the use of good SWE principles.
It looks like you've found another example of where the sort of error
that other languages are always being blamed for can occur in Ada.

: --
: Mark Biggar
: mab@wdl.lroal.com

Bill Williams

Re: Memory overwrite?

[Robert A Duff]

In article <3g2stg$i0u@miranda.gmrc.gecm.com>,
R.A.L Williams <bill@valiant> wrote:
>In article <1995Jan18.182039.7324@wdl.loral.com> Mark Biggar wrote:
>: 	if i in index then
>: 		a(i) := 0;
>: 	else
>: 		raise constraint_error;
>: 	end if;
>
>: because an aggressive optimizer will notice that the if test is always true
>: (in the absence of uninitialized variables, but uninitialized variables
>: are erroneous, which allow any behaviour, so it can ignore the problem)
>: and eliminate the test and the else branch completely.

I just want to emphasize that this is no longer true in Ada 95.  In Ada
95, the above will raise an exception if i is not in index, even if its
because i is not initialized.

>: Ada95 add the 'valid attribute to handle this problem.

Not really.  'Valid is mainly for checking data that comes from
Unchecked_Conversion, input, or from another language.  These are
isolated cases, and the programmer can use 'Valid as appropriate.

But variables occur all over the place.  It would not be feasible to put
'Valid checks all over the place, just to make sure you didn't forget to
initialize a variable.

Note the difference in these two cases: using an uninitialized variable
is a bug, and there are numerous places where it *might* happen in any
given program.  Input data, on the other hand, is not under control of
the programmer.  Bad input data is not a program bug.  And the number of
places in a program that do input is relatively small.

Again, using an uninitialized variable is *not* erroneous is Ada 95, so
if an optimizer wants to eliminate a check, it has to prove that the
check will not fail, even in the presence of uninitialized variables.

There's also a feature in the Safety and Security annex that tells the
compiler to initialize things to an out-of-range value (if it fits in
the bits of the object), to increase the likelihood that using an
uninitialized variable will cause the program to trip over a constraint
check.

- Bob

Re: Memory overwrite?

[Tucker Taft]

In article <3g2stg$i0u@miranda.gmrc.gecm.com>,
R.A.L Williams <bill@valiant> wrote:
>In article <1995Jan18.182039.7324@wdl.loral.com> Mark Biggar wrote:
>
>[original post and a reply deleted]
>
>: Actually the most likely reason for this is an uninitialized variable used
>: as an array index.  In Ada 83 the following code fragment can write anywhere
>: in memory and may well not raise an exception:
>
>: declare
>: 	subtype index is integer range 1..10;
>: 	type table is array (index) of integer;
>: 	a: table;
>: 	i: index;
>: begin
>: 	a(i) := 0;
>: end;
>
>: An aggressive optimizer will eliminate any checks from the above code.
>: Even putting an explisit if statement around it doesn't help:
>
>OK, I can see how an optimiser *could* do that, and, of course, RM9x
>section 3.3.1 says that 'There is no implicit initial value defined
>for a scalar subtype ... might have a value which does not belong to
>that subtype' (para 21). I'm a little suprised, however, that the
>compiler isn't expected to perform a simple data flow analysis and
>generate a warning about use of uninitialised variables. You're quite
>right though, I can't find anything in RM9x which says it should, and
>I'm pretty sure there was nothing in the Ada83 LRM.

Actually, the words in RM95 are explicitly designed to require
that the optimizer *not* assume an uninitialized variable is
in range.  In Ada 83, an optimizer was allowed to assume
that uninitialized variables were within their declared subtype,
resulting in possible erroneous execution via wild stores.
Because an Ada 95 optimizer is required to recognize the
case when a scalar variable might be uninitialized, it seems
likely that such an optimizer will be in a good position
to produce a warning.

> ...
>
>: Ada95 add the 'valid attribute to handle this problem.
>
>Yes, this is a good idea. In another thread I've been gently pushing
>the notion that use of Ada does not eliminate the use of good SWE principles.
>It looks like you've found another example of where the sort of error
>that other languages are always being blamed for can occur in Ada.

No, actually in Ada 95, an uninitialized variable cannot lead
to erroneous execution.  If the variable has a "wild" value
in it, the run-time is required to raise a Constraint_Error.
If you are unlucky enough for the uninitialized variable to have
a reasonable in-range value, then the run-time need not complain.

>: Mark Biggar
>: mab@wdl.lroal.com
>
>Bill Williams

-Tucker Taft  stt@inmet.com
Intermetrics, Inc.
Cambridge, MA  02138

Re: Memory overwrite?

[Robert Dewar]

Mark asks if GNAT can also find uninitialized variables, like GCC.

GNAT IS GCC! Use the GCC option, and you will get the output you want!
\x1a

Memory overwrite?

[R.A.L Williams]

In article <3g6fi6$fuv@gnat.cs.nyu.edu> Robert Dewar wrote:
: Mark asks if GNAT can also find uninitialized variables, like GCC.

No, actually it was me

: GNAT IS GCC! Use the GCC option, and you will get the output you want!
: \x1a

Well, no! I used these two programs...

with GNAT.IO; 
use GNAT.IO;

procedure CRASH is
  subtype CONSTRAINED_INT is INTEGER range 2 .. 5;
  I : INTEGER;
  J : CONSTRAINED_INT;
  X : array(CONSTRAINED_INT) of INTEGER;
begin
  for I in CONSTRAINED_INT'RANGE loop
    X(I) := I * 2;
    PUT(I); PUT(" : "); PUT(X(I)); NEW_LINE;
  end loop;
  PUT_LINE("The next command may cause a CONSTRAINT_ERROR");
  PUT(J); PUT(" : "); PUT(X(J)); NEW_LINE;
end;

compiled with 'gnat -c -O -Wuninitialized crash.adb' gave no
errors and no warnings; whereas

#include <stdio.h>

main()
{
  int i, j, x[4];

  for (i = 0; i < sizeof(x)/sizeof(int); i++)
  {
    x[i] = (i + 2) * 2;
    printf("%d : %d\n", i, x[i]);
  }
  printf("The next statement may cause a crash\n");
  printf("%d : %d\n", j, x[j]);
}

compiled with 'gcc -O -Wuninitialized -o crash-c crash-c.c'
told me:
  crash-c.c: In function `main':
  crash-c.c:5: warning: `j' might be used uninitialized in this function

Obviously this is a compiler issue, NOT a language issue. There is
no reason that I know of why future versions of GNAT shouldn't generate
similar warnings in these circumstances.

Interestingly, the -Wuninitialized option only works when optimization
is enabled. Does this imply that there isn't much optimization in
GNAT yet. (Can't complain, it is free and available and you cant say that
about any other Ada95 compilers).

Bill Williams

Re: Memory overwrite?

[Robert A Duff]

In article <3g86nm$mj3@miranda.gmrc.gecm.com>,
R.A.L Williams <bill@valiant> wrote:
>procedure CRASH is
>  subtype CONSTRAINED_INT is INTEGER range 2 .. 5;
>  I : INTEGER;
>  J : CONSTRAINED_INT;
>  X : array(CONSTRAINED_INT) of INTEGER;
>begin
>  for I in CONSTRAINED_INT'RANGE loop

GNAT also ought to warn that this I is different from the one declared
above, since the for loop automatically declares a new I!  ;-)

- Bob

Re: Memory overwrite?

[Robert Dewar]

"Does this imply there isn't much optimization in GNAT yet"

If you write C level code, then you will get exactly the same level of
optimization you would from C.

If you write code full of tagged types, pointers to unconstrained arrays,
slices, aggregates etc. then of course you can't really compare the
generated code with C.

There are many improvements we can make to the code quality for these
higher level Ada constructs, and we are working away on them :-)

I don't know why you didn't get the warning about an uninitialized
variable, I have certainly see
n this working in some cases. Perhaps Richard Kenner can explain this.

Re: Memory overwrite?

[Robert Dewar]

Bob Duff says:

>procedure CRASH is
>  subtype CONSTRAINED_INT is INTEGER range 2 .. 5;
>  I : INTEGER;
>  J : CONSTRAINED_INT;
>  X : array(CONSTRAINED_INT) of INTEGER;
>begin
>  for I in CONSTRAINED_INT'RANGE loop

GNAT also ought to warn that this I is different from the one declared
above, since the for loop automatically declares a new I!  ;-)

Robert asks Bob:

do you *really* want a warning here? I could see a warning saying that
the outer I is unreferenced if it was (but in fact it was referenced),
or that it was uninitialized (which it was, and in fact I think we 
should have been able to give the usual warning for this, I didn't
check, because I don't have the whole original post).

But just the fact that you are using two different I's does not seem
to warrant a warning to me!

Bob, what exactly did you have in mind?

Re: Memory overwrite?

[Robert A Duff]

In article <3gehlo$i05@gnat.cs.nyu.edu>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>But just the fact that you are using two different I's does not seem
>to warrant a warning to me!

This mistake is so common, I think it deserves a warning.  You've got
nothing better to do, right?  ;-)

If you have a variable that is never initialized (whether it's used or
not), and an inner for loop index of the same name, that's when I would
give a warning about not needing to declare the for loop index.  Of
course, a variable never initialized (or used) might deserve a warning
anyway, but if you just say "variable I never used", you will confuse
someone who thought you needed to declare I outside the for loop.  To
me, it seems friendy to give a more specific message in the for-loop
case.

- Bob

Re: Memory overwrite?

[Theodore E. Dennison]

bill@valiant (R.A.L Williams) wrote:
>
> In article <1995Jan18.182039.7324@wdl.loral.com> Mark Biggar wrote:
> 
> [original post and a reply deleted]
> 
> : Actually the most likely reason for this is an uninitialized variable used

> OK, I can see how an optimiser *could* do that, and, of course, RM9x
> section 3.3.1 says that 'There is no implicit initial value defined
> for a scalar subtype ... might have a value which does not belong to
> that subtype' (para 21). I'm a little suprised, however, that the
> compiler isn't expected to perform a simple data flow analysis and
> generate a warning about use of uninitialised variables. You're quite
> right though, I can't find anything in RM9x which says it should, and
> I'm pretty sure there was nothing in the Ada83 LRM.

You are right that Ada 83 did not REQUIRE this. Howerver, all four Ada
compilers that I have used generated warnings when uninitialized
variables were read or passed as "in" or "in out" parameters. Unless
you are the type that ignores compiler warnings, this situation is 
unlikely to arise. It is still worth checking out, but I would hardly
call it the "most likely reason" for the crashing behavior.  My vote
is still on misuse of either a "for use at" clause or address-access
UNCHECKED_CONVERSION.

Did you ever figure it out, Mark?

T.E.D.

Re: Memory overwrite?

[Robert Dewar]

T.E.D. says that all four Ada compilers he has used generate warnings if
uninitialized variables are passed as in parameters.

Just so that no one gets confused, it is *impossible* to generate such
warnings in all cases (to do so would require:

   (a) telepathy on the part of the compiler to guess the input in advance
   (b) a solution to the halting problem

otherwise, no sweat :-)

Of course warnings can be generated in some simple cases. But it is not the
case that worrying about the semantic effects of uninitialized variables
is unimportant because warnings can be generated.

Some obvious examples where the compiler cannot check is for the case of
array elements, references to dynamically allocated values (x.all), and
global variables where the compiler cannot tell who might have initialized
them.

So T.E.D. is I am afraid operating from a sense of false security (it is
in fact one disadvantage of the generation of such error messages, it
sometimes lulls people into this sense of false security). It is true
that the warnings are very useful, but don't depend on them!

Re: Memory overwrite?

[Matt Kennel]

Robert A Duff (bobduff@world.std.com) wrote:
: In article <3gehlo$i05@gnat.cs.nyu.edu>, Robert Dewar <dewar@cs.nyu.edu> wrote:
: >But just the fact that you are using two different I's does not seem
: >to warrant a warning to me!

: This mistake is so common, I think it deserves a warning.  You've got
: nothing better to do, right?  ;-)

: If you have a variable that is never initialized (whether it's used or
: not), and an inner for loop index of the same name, that's when I would
: give a warning about not needing to declare the for loop index.  Of
: course, a variable never initialized (or used) might deserve a warning
: anyway, but if you just say "variable I never used", you will confuse
: someone who thought you needed to declare I outside the for loop.  To
: me, it seems friendy to give a more specific message in the for-loop
: case.

This is gettting a little off topic but...

Sather has an interesting take on this issue:  you can declare and
initialize variables anywhere an assignment is legal, but scopes are NOT
nested.  So if you try to do it again to the same identifier it will
complain and not allow it.

It allows you to "Put your declaration close to the use" (and thus lower the
chance of uninitialized variables, and minimize confusion over things
declared before there is any logical need or use for them) but lower the
chance of "calling different things the same name adding to confusion" that
a declaration close to use with nested scopes would often imply.

example:

loop
	e ::= collection.elt!;	-- return elements of collection in sequence.
	process(e);

-- a nested loop:
	loop
--	     e ::= something_else.elt!;	-- NOT LEGAL, redeclares "e".
	end;
end;


----

The "::=" means "declare static type of variable on left to be the
same as static type of right side, and then perform the assignment.

This is useful in situations like the above. You don't really
want to denote the type of "e".  All that you care is that "e" is compatible
with the return type of the "elt!" call so that it can hold/reference
a legal object.

What's wrong with declaring it explicitly?  Nothing. {You could have
said e:TYPE:= right_hand_side just as easily}.  Just that when you're
in the early stages of development where the actual types that will be
returned are undergoing big changes as the design evolves you don't 
have to spend time just mechanically changing the names of types in
a billion places.

: - Bob


cheers
Matt

--
-Matt Kennel  		mbk@inls1.ucsd.edu
-Institute for Nonlinear Science, University of California, San Diego
-*** AD: Archive for nonlinear dynamics papers & programs: FTP to
-***     lyapunov.ucsd.edu, username "anonymous".