How do functions return unbounded arrays?

How do functions return unbounded arrays?

[Markus Kuhn]

One of the things that still puzzles me about Ada is: how do
compilers implement functions such as "&" that return variable
length strings or arrays.

To get such a functionality under C, I would have to malloc() the
memory for a String in the C function and then I am left with
the question of when to free this memory. Does an Ada function
such as "&" (concatenation of arrays) allocate secretly memory
on the heap to get a space to store the result?

If yes, when exactly is this memory deallocated? Are there Ada
programs that cause a heap overflow just by calling "&" in a long loop
and where this danger of a heap overflow is not explicit in the
program text as no allocator is visible? In other words, are there
any safety (heap overflow) risks associated with functions like "&"?

Is there a good paper that describes those things that silently
go on between the lines of an Ada program and that still keep me
from getting the warm fuzzy C programmer feeling that I really
know what exactly is going on when my code executes?

Also, is there any documentation around that describes the interface
that GNAT expects from the run-time library, i.e. whatever one
would need in order to write a new GNAT runtime library with all
the tasking, memory management, etc. (Again, just to get the feeling
that I know what is going on behind the scenes.)

Markus

-- 
Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK
email: mkuhn at acm.org,  home page: <http://www.cl.cam.ac.uk/~mgk25/>

Re: How do functions return unbounded arrays?

[Robert A Duff]

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> writes:

> One of the things that still puzzles me about Ada is: how do
> compilers implement functions such as "&" that return variable
> length strings or arrays.

Many compilers special-case predefined "&".

There are several ways to implement a user-defined function whose result
size is not known at the call site.

One is to use the heap -- do an implicit "new" at the point of the
return_statement, and do a Free in the caller when the value is no
longer needed.  Or skip the free, and do garbage collection.

Another is to leave the function result on the stack.  Do a funny sort
of return, which does not pop the stack, and return a pointer to the
result.  Then, at the call site, move the value down the stack to where
it belongs, and chop back the stack.

Another is to use a "secondary stack".  The normal stack ("primary
stack") stores the usual stuff, such as known-size locals, parameters
that don't fit in registers, and return addresses.  But store the
results of these fancy functions on the secondary stack.  Upon return
from such a function, pop the primary stack as usual, but leave the
result on the secondary stack, and don't pop.  At the call site, move
the result to where it belongs, and simultaneously chop back the
secondary stack.  In addition to caller-unknown-size function results,
the secondary stack might also contain all run-time-known-sized objects,
and/or large objects.

In the second and third techniques, the compiler might try to optimize
by avoiding unnecessary copies in various cases.

> To get such a functionality under C, I would have to malloc() the
> memory for a String in the C function and then I am left with
> the question of when to free this memory. Does an Ada function
> such as "&" (concatenation of arrays) allocate secretly memory
> on the heap to get a space to store the result?

It might.  I don't much like the implicit heap implementation (unless
you also have garbage collection).  But at least the compiler takes care
of figuring out when to free the storage (unlike the by-hand malloc you
would do in C).

> If yes, when exactly is this memory deallocated? Are there Ada
> programs that cause a heap overflow just by calling "&" in a long loop
> and where this danger of a heap overflow is not explicit in the
> program text as no allocator is visible? In other words, are there
> any safety (heap overflow) risks associated with functions like "&"?

I would consider such a storage leak to be a bug.

> Is there a good paper that describes those things that silently
> go on between the lines of an Ada program and that still keep me
> from getting the warm fuzzy C programmer feeling that I really
> know what exactly is going on when my code executes?

Ada is a bit higher level than C, so you get less of that particular
"warm fuzzy" -- there are several features of Ada that can be
implemented in various ways, and you just have to know what your
particular compiler does, or what "typical" compilers do.  I guess
that's just the price of using a high level language.  I don't know of
any useful papers about this; sorry.  When you program in C, you can
usually guess roughly what the compiler is going to do.  Less so in Ada.
More so in assembly language.

In C, you don't have to worry about whether the compiler does
code-sharing for generic bodies.  In C, you don't wonder whether the
compiler uses displays or static links for nested functions.

> Also, is there any documentation around that describes the interface
> that GNAT expects from the run-time library, i.e. whatever one
> would need in order to write a new GNAT runtime library with all
> the tasking, memory management, etc. (Again, just to get the feeling
> that I know what is going on behind the scenes.)

You can read the sources.  They're pretty well commented, IMHO.

- Bob

-- 
Change robert to bob to get my real email address.  Sorry.
-- 
Change robert to bob to get my real email address.  Sorry.

Re: How do functions return unbounded arrays?

[John Herro]

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk>
asks several questions, including
> Are there Ada programs that cause a heap
> overflow just by calling "&" in a long loop?

That question I can answer definitely.  The following program raises
Storage_Error on my machine when compiled with Open Ada (an Ada 83 compiler). 
The "with Text_IO;" is necessary with that compiler if the user is to see the
unhandled exception:

with Text_IO;
procedure Test is
   S : String(1 .. 18);
begin
   for L in Long_Integer range
        10_000_000 .. 99_999_998 loop
      S := Long_Integer'Image(L) &
           Long_Integer'Image(L + 1);
   end loop;
end Test;

- John Herro
You can download a shareware Ada Tutor from
http://members.aol.com/AdaTutor

Re: How do functions return unbounded arrays?

[Mark D. McKinney]

John Herro wrote:
> 
> with Text_IO;
> procedure Test is
>    S : String(1 .. 18);
> begin
>    for L in Long_Integer range
>         10_000_000 .. 99_999_998 loop

        -- This may work
        -- Some compilers deallocate the space when exiting the scope of
a block.
        Long_Integer_Conversion_Block:
        begin

   >       S := Long_Integer'Image(L) &
   >            Long_Integer'Image(L + 1);

        -- Memory dealloated when the block exits here.
        end Long_Integer_Conversion_Block;
      
>    end loop;
> end Test;
> 
 Meridian Ada (Perhaps thats what you're using) had this problem and
this was the solution recommended. Not all compilers do this.


MArk McKinney

Re: How do functions return unbounded arrays?

[Gavin Finnie]

In article <35865075.9D7DCBD@cl.cam.ac.uk>,
Markus Kuhn  <Markus.Kuhn@cl.cam.ac.uk> wrote:

>Are functions that return variable length arrays forbidden in
>Ada subsets for safety critical applications?

They are in general forbidden in SPARK.
However, the "&" operator is allowed on string literals as you would expect a
compiler to handle this case statically.

Gavin Finnie                             email:  gavin@praxis-cs.co.uk
Praxis Critical Systems Ltd                                       
20 Manvers Street                        phone: +44-225-466991
Bath BA1 1PX, England                    fax:   +44-225-469006 

Re: How do functions return unbounded arrays?

[Rod Chapman]

> They are in general forbidden in SPARK.
> However, the "&" operator is allowed on string literals as you would expect a
> compiler to handle this case statically.

Your mileage varies...

In Ada83, things which you "expect the compiler to handle statically" often
aren't.  Some compilers are better at spotting static expressions
above-and-beyond
what is strictly required by the Ada83 LRM (e.g. XD-Ada).  Some stick more
closely
to the letter of the law and generate more dynamic code for expressions even if
they
_could_ be evaluated statically (e.g. the "old" Alsys technology)

In Ada95 (and thus SPARK95), things are much better, since the definition
of "static" covers a much larger set of expressions, and the RM's implementation
advice gives you a pretty clear idea of what to expect.

For critical and real-time work, I _always_ check with the compiler vendor
and/or read the generated code for these bits of the language.
 -  Rod Chapman
   rod@praxis-cs.co.uk

Re: How do functions return unbounded arrays?

[Robert Dewar]

<<In Ada83, things which you "expect the compiler to handle statically" often
aren't.  Some compilers are better at spotting static expressions
above-and-beyond
what is strictly required by the Ada83 LRM (e.g. XD-Ada).  Some stick more
closely
to the letter of the law and generate more dynamic code for expressions even if
they
_could_ be evaluated statically (e.g. the "old" Alsys technology)
>>


Please do not use confusing terminbology. There are no "static expressions"
other than those defined in the RM (83 or 95). Both Ada 83 and Ada 95
compilers may recognize some expressions (e.g. 'Size applied to a simple
statically declared record type) as compile time evaluable, but these
should NOT under any circumstances be referred to as static expressions!

Re: How do functions return unbounded arrays?

[Robert Dewar]

Rod said

<<In Ada95 (and thus SPARK95), things are much better, since the definition
of "static" covers a much larger set of expressions, and the RM's implementatio
advice gives you a pretty clear idea of what to expect.
>>


I guess that means that Gavin misspoke when he mentioned that SPARK only
handles concatenation of string literals, as opposed to static string
expressions. Can we indeed assume that SPARK95 allows ALL static
expressions as defined in the RM (there is certainly no reason not to!)

Re: How do functions return unbounded arrays?

[Robert Dewar]

Gavin said

<<They are in general forbidden in SPARK.
However, the "&" operator is allowed on string literals as you would expect a
compiler to handle this case statically.
>>

That is really an Ada 83 comment (SPARK is still somewhat Ada 83 oriented!)
In Ada 95, it is a requirement of the language that & on string literals
(actually more accurately on static string expressions -- a useful 
extension not permitted as far as I remember by SPARK) are required to
be handled statically.

Re: How do functions return unbounded arrays?

[Matthew Heaney]

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> writes:

> Thanks for that example. That is exactly an implementation of
> of my bad gut feeling about the lack of a clear description in
> the RM that guarantees me when these secretly allocated heap
> blocks will be deallocated. Some guarantee that whatever a variable
> length function return secretly allocates does not survive the next
> semicolon would be very reassuring, otherwise programmers have
> little idea about what memory leaks their code might contain and
> this could be a safety risk. 

As I pointed out in my previous post, there needs to be an inner block,
containing the declaration of string S.  This will probably take care of
the memory "problem."

Re: How do functions return unbounded arrays?

[Robert Dewar]

Markus said

<<> Thanks for that example. That is exactly an implementation of
> of my bad gut feeling about the lack of a clear description in
> the RM that guarantees me when these secretly allocated heap
> blocks will be deallocated. Some guarantee that whatever a variable
> length function return secretly allocates does not survive the next
> semicolon would be very reassuring, otherwise programmers have
> little idea about what memory leaks their code might contain and
> this could be a safety risk.
>>


Any kind of dynamic allocation is a safety risk for most safety
critical purposes!

Re: How do functions return unbounded arrays?

[Mats Weber]

Markus Kuhn wrote:

> John Herro wrote:
> > The following program raises Storage_Error on my machine when
> > compiled with Open Ada (an Ada 83 compiler).
> 
> > with Text_IO;
> > procedure Test is
> >    S : String(1 .. 18);
> > begin
> >    for L in Long_Integer range
> >         10_000_000 .. 99_999_998 loop
> >       S := Long_Integer'Image(L) &
> >            Long_Integer'Image(L + 1);
> >    end loop;
> > end Test;

> Thanks for that example. That is exactly an implementation of
> of my bad gut feeling about the lack of a clear description in
> the RM that guarantees me when these secretly allocated heap
> blocks will be deallocated. Some guarantee that whatever a variable
> length function return secretly allocates does not survive the next
> semicolon would be very reassuring, otherwise programmers have
> little idea about what memory leaks their code might contain and
> this could be a safety risk.
> [...]

You seem to be considering this as expected behavior, but I think it's not.
It's a compiler bug. The compilers I have used do not leak storage on such
constructs. Leaking memory when allocators are called repeatedly without
deallocation is OK, but leaking storage on constructs that can be implemented
on the stack is not OK.

It is true that Ada 83 lacks specification in that respect (e.g.
Unchecked_Deallocation is not forced to do anything but set the pointer to
null). I do not know exactly what Ada 95 has to say on memory leaks for
stack-implementable constructs.

Re: How do functions return unbounded arrays?

[Robert Dewar]

Mats said

<<It is true that Ada 83 lacks specification in that respect (e.g.
Unchecked_Deallocation is not forced to do anything but set the pointer to
null). I do not know exactly what Ada 95 has to say on memory leaks for
stack-implementable constructs.
>>

It is in fact almost impossible to define formally when SE can or cannot
be raised, since it depends on implementation models which can vary
widely. But this does not mean that storage leaks are not a bug!

Re: How do functions return unbounded arrays?

[Matthew Heaney]

johnherro@aol.com (John Herro) writes:

> > Are there Ada programs that cause a heap
> > overflow just by calling "&" in a long loop?
> 
> That question I can answer definitely.  The following program raises
> Storage_Error on my machine when compiled with Open Ada (an Ada 83
> compiler).  [program example snipped]

This is hardly a definate answer.  All it proves is that in one Ada 83
implementation, storage error gets raised.

We could probably make the storage error go away by declaring the string
in a nested block:

procedure Test is
begin
   for L in Long_Integer range
        10_000_000 .. 99_999_998 loop

      declare
         S : constant String :=
           Long_Integer'Image(L) &
           Long_Integer'Image(L + 1);
      begin
         null;
      end;

   end loop;
end Test;

I think the memory will get cleaned up when the frame terminates (that
is, every pass through the loop), and therefore storage_error won't
happen.

Re: How do functions return unbounded arrays?

[Robert Dewar]

John Herro said

<<That question I can answer definitely.  The following program raises
Storage_Error on my machine when compiled with Open Ada (an Ada 83 compiler).
The "with Text_IO;" is necessary with that compiler if the user is to see the
unhandled exception:

with Text_IO;
procedure Test is
   S : String(1 .. 18);
begin
   for L in Long_Integer range
        10_000_000 .. 99_999_998 loop
      S := Long_Integer'Image(L) &
           Long_Integer'Image(L + 1);
   end loop;
end Test;
>>


This seems a clear bug to me, it is a storage leak! It should be reported
to the vendor as a bug (if they still care about their Ada 83 compiler!)

No decent compiler should raise SE due to storage leaks for temporary
allocations in loops.

(i.e. no compiler should accept such a situation as other than a bug
that needs fixing. Certainly that is the attitude we take with GNAT,
and we have indeed fixed a number of bugs of this type over the years!)