* How do functions return unbounded arrays? @ 1998-06-14 0:00 Markus Kuhn 1998-06-14 0:00 ` Robert A Duff 1998-06-15 0:00 ` John Herro 0 siblings, 2 replies; 15+ messages in thread From: Markus Kuhn @ 1998-06-14 0:00 UTC (permalink / raw) 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/> ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-14 0:00 How do functions return unbounded arrays? Markus Kuhn @ 1998-06-14 0:00 ` Robert A Duff 1998-06-15 0:00 ` John Herro 1 sibling, 0 replies; 15+ messages in thread From: Robert A Duff @ 1998-06-14 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-14 0:00 How do functions return unbounded arrays? Markus Kuhn 1998-06-14 0:00 ` Robert A Duff @ 1998-06-15 0:00 ` John Herro [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> ` (3 more replies) 1 sibling, 4 replies; 15+ messages in thread From: John Herro @ 1998-06-15 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
[parent not found: <35865075.9D7DCBD@cl.cam.ac.uk>]
* Re: How do functions return unbounded arrays? [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> @ 1998-06-17 0:00 ` Matthew Heaney 1998-06-21 0:00 ` Robert Dewar 1998-06-17 0:00 ` Gavin Finnie 1998-06-18 0:00 ` Mats Weber 2 siblings, 1 reply; 15+ messages in thread From: Matthew Heaney @ 1998-06-17 0:00 UTC (permalink / raw) 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." ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-17 0:00 ` Matthew Heaney @ 1998-06-21 0:00 ` Robert Dewar 0 siblings, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) 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! ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> 1998-06-17 0:00 ` Matthew Heaney @ 1998-06-17 0:00 ` Gavin Finnie 1998-06-17 0:00 ` Rod Chapman 1998-06-21 0:00 ` Robert Dewar 1998-06-18 0:00 ` Mats Weber 2 siblings, 2 replies; 15+ messages in thread From: Gavin Finnie @ 1998-06-17 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-17 0:00 ` Gavin Finnie @ 1998-06-17 0:00 ` Rod Chapman 1998-06-21 0:00 ` Robert Dewar 1998-06-21 0:00 ` Robert Dewar 1998-06-21 0:00 ` Robert Dewar 1 sibling, 2 replies; 15+ messages in thread From: Rod Chapman @ 1998-06-17 0:00 UTC (permalink / raw) > 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-17 0:00 ` Rod Chapman @ 1998-06-21 0:00 ` Robert Dewar 1998-06-21 0:00 ` Robert Dewar 1 sibling, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) 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!) ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-17 0:00 ` Rod Chapman 1998-06-21 0:00 ` Robert Dewar @ 1998-06-21 0:00 ` Robert Dewar 1 sibling, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) <<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! ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-17 0:00 ` Gavin Finnie 1998-06-17 0:00 ` Rod Chapman @ 1998-06-21 0:00 ` Robert Dewar 1 sibling, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> 1998-06-17 0:00 ` Matthew Heaney 1998-06-17 0:00 ` Gavin Finnie @ 1998-06-18 0:00 ` Mats Weber 1998-06-21 0:00 ` Robert Dewar 2 siblings, 1 reply; 15+ messages in thread From: Mats Weber @ 1998-06-18 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-18 0:00 ` Mats Weber @ 1998-06-21 0:00 ` Robert Dewar 0 siblings, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) 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! ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-15 0:00 ` John Herro [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> @ 1998-06-17 0:00 ` Mark D. McKinney 1998-06-17 0:00 ` Matthew Heaney 1998-06-21 0:00 ` Robert Dewar 3 siblings, 0 replies; 15+ messages in thread From: Mark D. McKinney @ 1998-06-17 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-15 0:00 ` John Herro [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> 1998-06-17 0:00 ` Mark D. McKinney @ 1998-06-17 0:00 ` Matthew Heaney 1998-06-21 0:00 ` Robert Dewar 3 siblings, 0 replies; 15+ messages in thread From: Matthew Heaney @ 1998-06-17 0:00 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: How do functions return unbounded arrays? 1998-06-15 0:00 ` John Herro ` (2 preceding siblings ...) 1998-06-17 0:00 ` Matthew Heaney @ 1998-06-21 0:00 ` Robert Dewar 3 siblings, 0 replies; 15+ messages in thread From: Robert Dewar @ 1998-06-21 0:00 UTC (permalink / raw) 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!) ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~1998-06-21 0:00 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1998-06-14 0:00 How do functions return unbounded arrays? Markus Kuhn 1998-06-14 0:00 ` Robert A Duff 1998-06-15 0:00 ` John Herro [not found] ` <35865075.9D7DCBD@cl.cam.ac.uk> 1998-06-17 0:00 ` Matthew Heaney 1998-06-21 0:00 ` Robert Dewar 1998-06-17 0:00 ` Gavin Finnie 1998-06-17 0:00 ` Rod Chapman 1998-06-21 0:00 ` Robert Dewar 1998-06-21 0:00 ` Robert Dewar 1998-06-21 0:00 ` Robert Dewar 1998-06-18 0:00 ` Mats Weber 1998-06-21 0:00 ` Robert Dewar 1998-06-17 0:00 ` Mark D. McKinney 1998-06-17 0:00 ` Matthew Heaney 1998-06-21 0:00 ` Robert Dewar
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox