* Dynamic allocation in the predefined language environment @ 2015-07-06 11:13 Matthias-Christian Ott 2015-07-06 13:04 ` G.B. ` (3 more replies) 0 siblings, 4 replies; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-06 11:13 UTC (permalink / raw) I need to store strings of unknown length. For security reasons I set limits for the types of strings the software handles and I used bounded-length strings to store them. However, it turned out that bounded-length strings do not fit the use case very well because the software sometimes has to convert between bounded-length strings of various types which makes the code verbose and hard to read and more importantly the limits are quite high so that I'm in trouble running out of stack space. In order to avoid the limitations of bounded-length data structures I'm currently looking for alternatives. Unbounded-length strings do not have this limitation but requires dynamic memory allocation (or at least I see no other way to implement it) which in turn requires error handling of memory allocation errors. However, if I'm not mistaken neither Ada 95, nor Ada 2005, nor Ada 2012 specify how memory allocation errors are to be reported or handled and do not allow one to specify the storage pool from which unbounded-length strings are allocated. The same seems to be true for other unbounded/infinite data-structures. I suppose most implementations will raise a Storage_Error exception but the standard does not specify how the packages are to implemented so a program could simply crash and would still conform to the standard. I looked at the implementation of unbounded-length strings in GNAT and it seems to be impossible to change to storage pool for unbounded-length strings because the Shared_String type is private. Moreover, I don't want depend on implementation details. At a certain point every complex embedded system that deals with user or network inputs has to use dynamic memory allocation and I can't imagine that not handling memory allocations errors in some way is an option for such systems. So there has to be a way to achieve what I want without writing larger parts of the predefined language environment yourself or relying on implementation details of a specific compiler. Even the C++ STL has some crippled way to use custom memory allocators for dynamic data structures and I thought Ada is able to handle memory allocation errors better than just crashing or terminating the program like some functional programming languages do. Has somebody encountered the same problem and perhaps solved it? Is there an alternative solution to the problem that I have not considered? - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 11:13 Dynamic allocation in the predefined language environment Matthias-Christian Ott @ 2015-07-06 13:04 ` G.B. 2015-07-06 14:21 ` Matthias-Christian Ott 2015-07-06 14:06 ` Bob Duff ` (2 subsequent siblings) 3 siblings, 1 reply; 27+ messages in thread From: G.B. @ 2015-07-06 13:04 UTC (permalink / raw) On 06.07.15 13:13, Matthias-Christian Ott wrote: > Unbounded-length strings do not have this limitation but requires > dynamic memory allocation (or at least I see no other way to implement > it) which in turn requires error handling of memory allocation errors. > However, if I'm not mistaken neither Ada 95, nor Ada 2005, nor Ada 2012 > specify how memory allocation errors are to be reported or handled and > do not allow one to specify the storage pool from which unbounded-length > strings are allocated. I think that LRM 13.11 might apply here (coming from LRM 4.8), "If Storage_Pool is not specified for a type defined by an access_to_object_definition, then the implementation chooses a standard storage pool for it in an implementation-defined manner. In this case, the exception Storage_Error is raised by an allocator if there is not enough storage." A handler then, if possible, could be of the kind that does not require additional resources for its execution. It might be more tricky to use one with tasks, but IIUC, one can attach termination handlers. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 13:04 ` G.B. @ 2015-07-06 14:21 ` Matthias-Christian Ott 0 siblings, 0 replies; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-06 14:21 UTC (permalink / raw) On 06/07/15 13:04, G.B. wrote: > On 06.07.15 13:13, Matthias-Christian Ott wrote: > >> Unbounded-length strings do not have this limitation but requires >> dynamic memory allocation (or at least I see no other way to implement >> it) which in turn requires error handling of memory allocation errors. >> However, if I'm not mistaken neither Ada 95, nor Ada 2005, nor Ada 2012 >> specify how memory allocation errors are to be reported or handled and >> do not allow one to specify the storage pool from which unbounded-length >> strings are allocated. > > I think that LRM 13.11 might apply here (coming from LRM 4.8), > > "If Storage_Pool is not specified for a type defined by an > access_to_object_definition, then the implementation chooses > a standard storage pool for it in an implementation-defined > manner. In this case, the exception Storage_Error is raised > by an allocator if there is not enough storage." > > A handler then, if possible, could be of the kind that > does not require additional resources for its execution. > It might be more tricky to use one with tasks, but IIUC, > one can attach termination handlers. That should work. But what if the implementation does not use access types or storage pools to implement unbounded-length strings? The standard simply doesn't specify the behaviour or implementation of the package with regards to memory management. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 11:13 Dynamic allocation in the predefined language environment Matthias-Christian Ott 2015-07-06 13:04 ` G.B. @ 2015-07-06 14:06 ` Bob Duff 2015-07-06 14:16 ` Matthias-Christian Ott ` (2 more replies) 2015-07-06 18:45 ` Jeffrey R. Carter 2015-07-07 7:42 ` Dmitry A. Kazakov 3 siblings, 3 replies; 27+ messages in thread From: Bob Duff @ 2015-07-06 14:06 UTC (permalink / raw) Matthias-Christian Ott <ott@mirix.org> writes: > Unbounded-length strings do not have this limitation but requires > dynamic memory allocation (or at least I see no other way to implement > it) which in turn requires error handling of memory allocation errors. > However, if I'm not mistaken neither Ada 95, nor Ada 2005, nor Ada 2012 > specify how memory allocation errors are to be reported or handled and > do not allow one to specify the storage pool from which unbounded-length > strings are allocated. The same seems to be true for other > unbounded/infinite data-structures. Yes, the predefined containers packages unfortunately don't allow you to specify the storage pool. >...I suppose most implementations will > raise a Storage_Error exception but the standard does not specify how > the packages are to implemented so a program could simply crash and > would still conform to the standard. No, running out of memory raises Storage_Error. The implementation cannot "simply crash". It's true that the standard does not specify how the packages are implemented, but they still have to be implemented correctly. There's nothing in the RM that says they can crash, so they can't. - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:06 ` Bob Duff @ 2015-07-06 14:16 ` Matthias-Christian Ott 2015-07-06 14:23 ` G.B. 2015-07-06 14:45 ` Bob Duff 2015-07-06 15:29 ` Simon Wright 2015-07-06 20:22 ` Randy Brukardt 2 siblings, 2 replies; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-06 14:16 UTC (permalink / raw) On 06/07/15 14:06, Bob Duff wrote: > Matthias-Christian Ott <ott@mirix.org> writes: >> ...I suppose most implementations will >> raise a Storage_Error exception but the standard does not specify how >> the packages are to implemented so a program could simply crash and >> would still conform to the standard. > > No, running out of memory raises Storage_Error. The implementation > cannot "simply crash". It could be implemented in C or assembly language and than it could definitely crash. The point is: If the standard specifies how to implement a package, you have to assume anything when reasoning about the correctness of code. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:16 ` Matthias-Christian Ott @ 2015-07-06 14:23 ` G.B. 2015-07-06 14:43 ` Matthias-Christian Ott 2015-07-06 14:45 ` Bob Duff 1 sibling, 1 reply; 27+ messages in thread From: G.B. @ 2015-07-06 14:23 UTC (permalink / raw) On 06.07.15 16:16, Matthias-Christian Ott wrote: > On 06/07/15 14:06, Bob Duff wrote: >> Matthias-Christian Ott <ott@mirix.org> writes: >>> ...I suppose most implementations will >>> raise a Storage_Error exception but the standard does not specify how >>> the packages are to implemented so a program could simply crash and >>> would still conform to the standard. >> >> No, running out of memory raises Storage_Error. The implementation >> cannot "simply crash". > > It could be implemented in C or assembly language and than it could > definitely crash. It could be written in C or assembly, but then if it crashed on out of memory, it is not an implementation. (I'll trust co-author of the Ada LRM, Bob Duff, on this.) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:23 ` G.B. @ 2015-07-06 14:43 ` Matthias-Christian Ott 2015-07-06 14:56 ` Bob Duff 0 siblings, 1 reply; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-06 14:43 UTC (permalink / raw) On 06/07/15 14:23, G.B. wrote: > On 06.07.15 16:16, Matthias-Christian Ott wrote: >> On 06/07/15 14:06, Bob Duff wrote: >>> Matthias-Christian Ott <ott@mirix.org> writes: >>>> ...I suppose most implementations will >>>> raise a Storage_Error exception but the standard does not specify how >>>> the packages are to implemented so a program could simply crash and >>>> would still conform to the standard. >>> >>> No, running out of memory raises Storage_Error. The implementation >>> cannot "simply crash". >> >> It could be implemented in C or assembly language and than it could >> definitely crash. > > It could be written in C or assembly, but then if it crashed > on out of memory, it is not an implementation. (I'll trust > co-author of the Ada LRM, Bob Duff, on this.) Then to finish this discussion: If it is required to raise Storage_Error, then it should be in the standard. There are only a handful of Ada compilers which most likely all raise Storage_Error but I think the history of C shows that if there is an ambiguity in the standard, both compiler writers and software developers will interpret it differently, so that both different compilers and the assumptions of software developers about these compilers will differ. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:43 ` Matthias-Christian Ott @ 2015-07-06 14:56 ` Bob Duff 2015-07-07 8:46 ` Matthias-Christian Ott 0 siblings, 1 reply; 27+ messages in thread From: Bob Duff @ 2015-07-06 14:56 UTC (permalink / raw) Matthias-Christian Ott <ott@mirix.org> writes: > Then to finish this discussion: If it is required to raise > Storage_Error, then it should be in the standard. It is in the standard. See 11.1(6): 6 The execution of any construct raises Storage_Error if there is insufficient storage for that execution. The amount of storage needed for the execution of constructs is unspecified. >... There are only a > handful of Ada compilers which most likely all raise Storage_Error but I > think the history of C shows that if there is an ambiguity in the > standard, both compiler writers and software developers will interpret > it differently, so that both different compilers and the assumptions of > software developers about these compilers will differ. Yes, all true, but 11.1(6) seems pretty unambiguous to me. Actually handling Storage_Error can be tricky, though. For one thing, in theory, the handler itself could raise Storage_Error, defeating the purpose. More importantly, since Storage_Error can be raised by anything, it is essentially asynchronous with the rest of the program, so can leave data structures in a corrupted state. - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:56 ` Bob Duff @ 2015-07-07 8:46 ` Matthias-Christian Ott 2015-07-07 22:32 ` Bob Duff 0 siblings, 1 reply; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-07 8:46 UTC (permalink / raw) On 06/07/15 14:56, Bob Duff wrote: > Matthias-Christian Ott <ott@mirix.org> writes: > >> Then to finish this discussion: If it is required to raise >> Storage_Error, then it should be in the standard. > > It is in the standard. See 11.1(6): > > 6 The execution of any construct raises Storage_Error if there is > insufficient storage for that execution. The amount of storage needed for the > execution of constructs is unspecified. I think that answers the first part of my question adequately, although its in a surprising part of the specification and the "any construct" is a bit ambiguous because it's in the dynamic semantics section of exception declarations but seems to refer to any construct in the language. >> ... There are only a >> handful of Ada compilers which most likely all raise Storage_Error but I >> think the history of C shows that if there is an ambiguity in the >> standard, both compiler writers and software developers will interpret >> it differently, so that both different compilers and the assumptions of >> software developers about these compilers will differ. > > Yes, all true, but 11.1(6) seems pretty unambiguous to me. > > Actually handling Storage_Error can be tricky, though. For one thing, > in theory, the handler itself could raise Storage_Error, defeating the > purpose. More importantly, since Storage_Error can be raised by > anything, it is essentially asynchronous with the rest of the program, > so can leave data structures in a corrupted state. If you follow the strong exception safety principle from C++, corrupted data structures should not be a problem. However, you can only do this in code that is under your control. You can somewhat avoid Storage_Error exception while handling Storage_Error exceptions by having "spare" memory that you free directly after the exception handler is invoked. Otherwise there are many application-specific possibilities on how to deal with memory allocation errors in a spectrum ranging from simply aborting to degradation of service/user experience. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-07 8:46 ` Matthias-Christian Ott @ 2015-07-07 22:32 ` Bob Duff 2015-07-08 19:47 ` Randy Brukardt 0 siblings, 1 reply; 27+ messages in thread From: Bob Duff @ 2015-07-07 22:32 UTC (permalink / raw) Matthias-Christian Ott <ott@mirix.org> writes: > On 06/07/15 14:56, Bob Duff wrote: >> 6 The execution of any construct raises Storage_Error if there is >> insufficient storage for that execution. The amount of storage needed for the >> execution of constructs is unspecified. > > I think that answers the first part of my question adequately, although > its in a surprising part of the specification... Well, it's hard to know where to put a rule that applies to pretty-much every feature of the language. I wouldn't want to duplicate it in every section. You were wondering about Unbounded_Strings, if I recall correctly. But I wouldn't want to say (in the section on Unbounded_Strings) "operations in this package raise Storage_Error if they run out of memory, and it's implementation dependent whether they do", because there's nothing special about Unbounded_Strings in that regard. Perhaps Storage_Error should get its own section. But with the language as it is, it would be a pretty short section. (I'd actually like to add some functionality: a way to ensure that certain procedures do NOT run out of memory.) >... and the "any construct" is > a bit ambiguous because it's in the dynamic semantics section of > exception declarations but seems to refer to any construct in the language. It says "execution of...", so it applies only to those constructs that are executed (which includes "evaluated" and "elaborated"). Yes, that's pretty-much "any construct". And for sure it belongs under Dynamic Semantics, because it happens at run time. > If you follow the strong exception safety principle from C++, corrupted > data structures should not be a problem. I don't see how. Storage_Error as defined by the language is like an asynchronous interrupt. When programming with asynchronous interrupts, you need a way to disable interrupts in usually-short sections of code. When programming with Storage_Error, you need a way to "disable" running out of memory. Ada lacks such a feature (and so does every other programming language I know). >...However, you can only do this > in code that is under your control. > > You can somewhat avoid Storage_Error exception while handling > Storage_Error exceptions by having "spare" memory that you free directly > after the exception handler is invoked. Yes, but Storage_Error is raised when running out of stack memory as well as heap/pool memory. Stack memory is the more "interesting" issue, IMHO. Imagine a "when Storage_Error" handler that simply prints a message "Memory exhausted while processing line N of the input". No heap-allocation involved, but in theory it can still raise Storage_Error. >...Otherwise there are many > application-specific possibilities on how to deal with memory allocation > errors in a spectrum ranging from simply aborting to degradation of > service/user experience. - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-07 22:32 ` Bob Duff @ 2015-07-08 19:47 ` Randy Brukardt 2015-07-08 21:08 ` Bob Duff 2015-07-08 21:16 ` Dmitry A. Kazakov 0 siblings, 2 replies; 27+ messages in thread From: Randy Brukardt @ 2015-07-08 19:47 UTC (permalink / raw) "Bob Duff" <bobduff@theworld.com> wrote in message news:87fv4zvbsf.fsf@theworld.com... > Matthias-Christian Ott <ott@mirix.org> writes: ... >> If you follow the strong exception safety principle from C++, corrupted >> data structures should not be a problem. > > I don't see how. Storage_Error as defined by the language is like an > asynchronous interrupt. When programming with asynchronous interrupts, > you need a way to disable interrupts in usually-short sections of code. > When programming with Storage_Error, you need a way to "disable" running > out of memory. Ada lacks such a feature (and so does every other > programming language I know). It's hard to imagine how any programming language (or language implementation) could protect against running out of memory. At best, one can try to contain the damage, but the usage/availability of memory is pretty much out of the hands of the implementer (unless they're targeting a bare machine). >>...However, you can only do this >> in code that is under your control. >> >> You can somewhat avoid Storage_Error exception while handling >> Storage_Error exceptions by having "spare" memory that you free directly >> after the exception handler is invoked. > > Yes, but Storage_Error is raised when running out of stack memory as > well as heap/pool memory. Stack memory is the more "interesting" issue, > IMHO. Imagine a "when Storage_Error" handler that simply prints a > message "Memory exhausted while processing line N of the input". > No heap-allocation involved, but in theory it can still raise > Storage_Error. Indeed, it often does -- Put_Line is relatively expensive in terms of stack and/or heap memory. On our old 16-bit compilers, the stack for the environment task and the heap grew together -- that way, we could maximize the use of the address space - no fixed size was needed for either the stack or the heap. The net effect though was that when you ran out of memory it was *all* gone. We had a lot of trouble with the exception handling mechanism itself failing because of a lack of memory, and when we fixed that, only the memory freed by unwinding the stack was available -- depending where the handler was, that might not have been much. We added a one-time hack to the runtime to make that a bit less of a problem -- we added a "leeway" setting that triggered Storage_Error a bit too early (if the distance between the top of the heap and top of the stack (stacks growing downwards on Intel machines) is less than Leeway, then Storage_Error is raised), and the setting was decreased after the first triggering of Storage_Error. Of course, that only works once; it's hardly worthwhile for programs that run a long time (like a web server). So Storage_Error handlers are a crap-shoot. I recall one Ada person (Dave Emery, I think) saying the Storage_Error is like a parachute that opens on impact -- it works, but it's very useful. Our compiler has a handler for Storage_Error: when Storage_Error => J2Error.Fatal_Error (128); which is supposed to report the error and then clean up. But it almost never works because there usually isn't enough memory to do the file operations that are used by the error handler and the clean-up that follows. Luckily, modern hosts rarely run out of memory during a compile (that used to be a common problem on CP/M and MS-DOS). The best Storage_Error handlers do as little as possible to recover (or report), because most likely you are in deep trouble. Depending on the compiler's memory model and how your program is structured, it may be impossible to get out of it. Randy. >>...Otherwise there are many >> application-specific possibilities on how to deal with memory allocation >> errors in a spectrum ranging from simply aborting to degradation of >> service/user experience. > > - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-08 19:47 ` Randy Brukardt @ 2015-07-08 21:08 ` Bob Duff 2015-07-10 21:58 ` Randy Brukardt 2015-07-08 21:16 ` Dmitry A. Kazakov 1 sibling, 1 reply; 27+ messages in thread From: Bob Duff @ 2015-07-08 21:08 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > "Bob Duff" <bobduff@theworld.com> wrote in message >> I don't see how. Storage_Error as defined by the language is like an >> asynchronous interrupt. When programming with asynchronous interrupts, >> you need a way to disable interrupts in usually-short sections of code. >> When programming with Storage_Error, you need a way to "disable" running >> out of memory. Ada lacks such a feature (and so does every other >> programming language I know). > > It's hard to imagine how any programming language (or language > implementation) could protect against running out of memory. At best, one > can try to contain the damage, but the usage/availability of memory is > pretty much out of the hands of the implementer (unless they're targeting a > bare machine). Of course you can write a program (in pretty much any language) that will use up more and more memory, and will eventually run out. The language can't very well prevent that. But that's not what I meant. Here's what I have in mind: The programmer may mark a procedure (or region of code?) as "doesn't run out of stack memory". The implementation calculates a worst-case (compile-time-known) stack usage for that procedure (including everything it calls that has the same property). This is always possible, because it can never be bigger than the size of the address space. On a call to that procedure, enough stack memory is reserved so that it can't run out. If that's not possible, Storage_Error is raised. The point is that Storage_Error can't be raised in the middle of that procedure -- only on entry. S_E is like an interrupt -- if an interrupt happens in while it's disabled, then it occurs at the end of the disabled region. Here, the S_E is moved to the START of the S_E-disabled region. Of course, if you use unbounded recursion or potentially-large arrays, the "worst-case" is going to be something like 2**64 bytes, so every call to that procedure will raise S_E. But for things that are "simple", it would work fine. Then for something like: procedure P (...) is begin ... -- use lots of stack exception when Storage_Error => Report_Error_And_Quit; end P; you want it to reserve enough stack space on entry to P, so Report_Error_And_Quit can be guaranteed to work without running out of stack. So P is a no-Storage_Error procedure, but the "use lots of stack" code is not. This wouldn't fit in well with the usual Ada compilation model, which wants to generate code without looking at the transitive closure of the call graph. I can think of various designs, suitable for a from-scratch compiler implementation -- I wouldn't want to retrofit this feature into an existing compiler. >> Yes, but Storage_Error is raised when running out of stack memory as >> well as heap/pool memory. Stack memory is the more "interesting" issue, >> IMHO. Imagine a "when Storage_Error" handler that simply prints a >> message "Memory exhausted while processing line N of the input". >> No heap-allocation involved, but in theory it can still raise >> Storage_Error. > > Indeed, it often does -- Put_Line is relatively expensive in terms of stack > and/or heap memory. That's OK, so long as it's bounded. It's not that hard to implement Put_Line without using heap, and using fixed-size locals that are not huge. > On our old 16-bit compilers, the stack for the environment task and the heap > grew together -- that way, we could maximize the use of the address space - > no fixed size was needed for either the stack or the heap. The net effect > though was that when you ran out of memory it was *all* gone. We had a lot > of trouble with the exception handling mechanism itself failing because of a > lack of memory, and when we fixed that, only the memory freed by unwinding > the stack was available -- depending where the handler was, that might not > have been much. > > We added a one-time hack to the runtime to make that a bit less of a > problem -- we added a "leeway" setting that triggered Storage_Error a bit > too early (if the distance between the top of the heap and top of the stack > (stacks growing downwards on Intel machines) is less than Leeway, then > Storage_Error is raised), and the setting was decreased after the first > triggering of Storage_Error. Of course, that only works once; it's hardly > worthwhile for programs that run a long time (like a web server). I don't see why it should work only once. You reserve enough stack space so that S_E can be raised. The "raise S_E" uses that reserve, then when it jumps to the handler, the reserved space is again reserved. When the GNAT front end runs out of memory, it doesn't seem to have trouble printing a message saying what line it was on. > So Storage_Error handlers are a crap-shoot. Indeed, in Ada as it is. >...I recall one Ada person (Dave > Emery, I think) saying the Storage_Error is like a parachute that opens on > impact -- it works, but it's very useful. ;-) I'll assume a missing "not" there. Anyway, it's better than languages that allow running out of stack to overwrite arbitary memory locations (like stacks belonging to other tasks). - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-08 21:08 ` Bob Duff @ 2015-07-10 21:58 ` Randy Brukardt 0 siblings, 0 replies; 27+ messages in thread From: Randy Brukardt @ 2015-07-10 21:58 UTC (permalink / raw) "Bob Duff" <bobduff@theworld.com> wrote in message news:87bnfmuzl0.fsf@theworld.com... ... > Here's what I have in mind: The programmer may mark a procedure (or > region of code?) as "doesn't run out of stack memory". The > implementation calculates a worst-case (compile-time-known) stack usage > for that procedure (including everything it calls that has the same > property). This is always possible, because it can never be bigger than > the size of the address space. Interesting. ... > This wouldn't fit in well with the usual Ada compilation model, > which wants to generate code without looking at the transitive > closure of the call graph. I can think of various designs, > suitable for a from-scratch compiler implementation -- I > wouldn't want to retrofit this feature into an existing > compiler. You could implement it rather like inlining. The effect would be the same. For Janus/Ada, which aggresively tries to avoid unnecessary dependence on other units (the primary reason we used generic code sharing, for example), this would be a lousy model. But one could argue that such avoidance isn't as necessary as it once was. Or one could use link-time fill-ins of the memory sizes in the pre-checks (that would be much more in keeping with Janus/Ada). Anyway, I agree: not that easy to retrofit. ... >> We added a one-time hack to the runtime to make that a bit less of a >> problem -- we added a "leeway" setting that triggered Storage_Error a bit >> too early (if the distance between the top of the heap and top of the >> stack >> (stacks growing downwards on Intel machines) is less than Leeway, then >> Storage_Error is raised), and the setting was decreased after the first >> triggering of Storage_Error. Of course, that only works once; it's hardly >> worthwhile for programs that run a long time (like a web server). > > I don't see why it should work only once. You reserve enough stack > space so that S_E can be raised. The "raise S_E" uses that reserve, > then when it jumps to the handler, the reserved space is again > reserved. The extra space is needed so that the handlers execute without raising S_E (mainly so Put_Line would work). We don't have any runtime call at the end of handlers (they return using the normal subprogram mechanism), so there isn't any sensible way to know when to reset the leeway value. I spent a looonnnngggg time thinking about this problem before I gave up (adding runtime overhead to fix that was a non-starter). [For instance, I considered using the next registration of an exception handler to reset the leeway. But that didn't work because the handler could call something that uses an exception handler internally. Indeed, Put_Line does that, so that didn't work at all.] ... >>...I recall one Ada person (Dave >> Emery, I think) saying the Storage_Error is like a parachute that opens >> on >> impact -- it works, but it's very useful. > > ;-) > > I'll assume a missing "not" there. Yup. Too fast writing CLA messages, I guess. > Anyway, it's better than languages that allow running out of stack to > overwrite arbitary memory locations (like stacks belonging to other > tasks). Surely. Randy. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-08 19:47 ` Randy Brukardt 2015-07-08 21:08 ` Bob Duff @ 2015-07-08 21:16 ` Dmitry A. Kazakov 1 sibling, 0 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2015-07-08 21:16 UTC (permalink / raw) On Wed, 8 Jul 2015 14:47:22 -0500, Randy Brukardt wrote: > It's hard to imagine how any programming language (or language > implementation) could protect against running out of memory. By using contracts? E.g. the post-condition: stack has more than n free storage units elements AND whatever normal completion does. OR stack has less than n free storage units elements AND Storage_Error raised With such contracts you could prove that Storage_Error is not raised if the client has more than m free storage units of the stack. > At best, one can try to contain the damage, It is usually too late at this point and useless for any practical purpose anyway. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:16 ` Matthias-Christian Ott 2015-07-06 14:23 ` G.B. @ 2015-07-06 14:45 ` Bob Duff 2015-07-06 20:28 ` Randy Brukardt 2015-07-07 8:49 ` Matthias-Christian Ott 1 sibling, 2 replies; 27+ messages in thread From: Bob Duff @ 2015-07-06 14:45 UTC (permalink / raw) Matthias-Christian Ott <ott@mirix.org> writes: > It could be implemented in C or assembly language and than it could > definitely crash. Yes, it could be implemented in any language. But it still has to be implemented correctly. If it crashes, then it's not a conforming implementation of Ada. (And of course, "conforming implementation of Ada" is synonymous with "implementation of Ada"!) If you think the RM says otherwise, then either you are misunderstanding the RM, or else the RM has an error. The latter is possible, but for sure the INTENT of the RM is that running out of memory raises Storage_Error, and does not "simply crash". I mean, consider a simple addition: X + Y The RM requires this to compute the sum of X and Y, or raise Constraint_Error on overflow (or (unlikely) raise Storage_Error -- anything can raise Storage_Error). The implementer doesn't get to say, "Well the RM doesn't specify HOW '+' is implemented, and I'm choosing to implement it wrong." >...The point is: If the standard specifies how to > implement a package, you have to assume anything when reasoning about > the correctness of code. I don't understand that sentence. Are you missing a "not" or something? Anyway, your original complaint (that the language doesn't let you choose the storage pool used for containers) is quite correct. I think it was considered, but I don't remember the details. - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:45 ` Bob Duff @ 2015-07-06 20:28 ` Randy Brukardt 2015-07-07 8:49 ` Matthias-Christian Ott 1 sibling, 0 replies; 27+ messages in thread From: Randy Brukardt @ 2015-07-06 20:28 UTC (permalink / raw) "Bob Duff" <bobduff@theworld.com> wrote in message news:87y4itbb0z.fsf@theworld.com... > Matthias-Christian Ott <ott@mirix.org> writes: ... > Anyway, your original complaint (that the language doesn't let you > choose the storage pool used for containers) is quite correct. > I think it was considered, but I don't remember the details. The problem was that it isn't very useful unless one very seriously constrains how the implementation can implement the containers. Without such constraints, any pattern of allocations has to be supported (as the implementation of the container could do anything), whereas most of the interesting storage pools put some sorts of limits on the sizes and/or numbers of allocations to get more deterministic memory management than the default storage pool. The original consideration was an alternative to the bounded containers for deterministic memory management, and allowing user-defined storage pools didn't really help with that. Thus they were not pursued further for Ada 2012. There are other possible uses, of course, and perhaps we'll revisit this someday (they came up briefly during the recent ARG meeting, although I forget why). Randy. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:45 ` Bob Duff 2015-07-06 20:28 ` Randy Brukardt @ 2015-07-07 8:49 ` Matthias-Christian Ott 2015-07-07 22:14 ` Bob Duff 1 sibling, 1 reply; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-07 8:49 UTC (permalink / raw) On 06/07/15 14:45, Bob Duff wrote: > Matthias-Christian Ott <ott@mirix.org> writes: > >> It could be implemented in C or assembly language and than it could >> definitely crash. > > Yes, it could be implemented in any language. But it still has to be > implemented correctly. If it crashes, then it's not a conforming > implementation of Ada. (And of course, "conforming implementation of > Ada" is synonymous with "implementation of Ada"!) > > If you think the RM says otherwise, then either you are misunderstanding > the RM, or else the RM has an error. The latter is possible, but for > sure the INTENT of the RM is that running out of memory raises > Storage_Error, and does not "simply crash". > > I mean, consider a simple addition: > > X + Y > > The RM requires this to compute the sum of X and Y, or raise > Constraint_Error on overflow (or (unlikely) raise Storage_Error -- > anything can raise Storage_Error). The implementer doesn't get to say, > "Well the RM doesn't specify HOW '+' is implemented, and I'm choosing to > implement it wrong." You have fully convinced me. >> ...The point is: If the standard specifies how to >> implement a package, you have to assume anything when reasoning about >> the correctness of code. > > I don't understand that sentence. Are you missing a "not" or something? Yes. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-07 8:49 ` Matthias-Christian Ott @ 2015-07-07 22:14 ` Bob Duff 0 siblings, 0 replies; 27+ messages in thread From: Bob Duff @ 2015-07-07 22:14 UTC (permalink / raw) Matthias-Christian Ott <ott@mirix.org> writes: > You have fully convinced me. That's good to know. - Bob ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:06 ` Bob Duff 2015-07-06 14:16 ` Matthias-Christian Ott @ 2015-07-06 15:29 ` Simon Wright 2015-07-06 20:31 ` Randy Brukardt 2015-07-06 20:22 ` Randy Brukardt 2 siblings, 1 reply; 27+ messages in thread From: Simon Wright @ 2015-07-06 15:29 UTC (permalink / raw) Bob Duff <bobduff@theworld.com> writes: > Yes, the predefined containers packages unfortunately don't allow you > to specify the storage pool. An advantage of the Booch Components! ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 15:29 ` Simon Wright @ 2015-07-06 20:31 ` Randy Brukardt 2015-07-06 21:35 ` Simon Wright 0 siblings, 1 reply; 27+ messages in thread From: Randy Brukardt @ 2015-07-06 20:31 UTC (permalink / raw) "Simon Wright" <simon@pushface.org> wrote in message news:lytwthxq1t.fsf@pushface.org... > Bob Duff <bobduff@theworld.com> writes: > >> Yes, the predefined containers packages unfortunately don't allow you >> to specify the storage pool. > > An advantage of the Booch Components! Which works because there is only a single implementation of both the specs and bodies. If you don't specify the contents of the bodies, specifying the storage pool is nearly useless (the main use would be to use some sort of debugging pool), as the only pool implementations would have the same properties as the global default storage pool. Randy. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 20:31 ` Randy Brukardt @ 2015-07-06 21:35 ` Simon Wright 2015-07-07 18:29 ` Randy Brukardt 0 siblings, 1 reply; 27+ messages in thread From: Simon Wright @ 2015-07-06 21:35 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > "Simon Wright" <simon@pushface.org> wrote in message > news:lytwthxq1t.fsf@pushface.org... >> Bob Duff <bobduff@theworld.com> writes: >> >>> Yes, the predefined containers packages unfortunately don't allow you >>> to specify the storage pool. >> >> An advantage of the Booch Components! > > Which works because there is only a single implementation of both the > specs and bodies. If you don't specify the contents of the bodies, > specifying the storage pool is nearly useless (the main use would be > to use some sort of debugging pool), as the only pool implementations > would have the same properties as the global default storage pool. Come to think, the time we used this was as the storage pool for fixed-size objects, pointers to which were held in a bounded container. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 21:35 ` Simon Wright @ 2015-07-07 18:29 ` Randy Brukardt 0 siblings, 0 replies; 27+ messages in thread From: Randy Brukardt @ 2015-07-07 18:29 UTC (permalink / raw) "Simon Wright" <simon@pushface.org> wrote in message news:ly4mlhx94q.fsf@pushface.org... > "Randy Brukardt" <randy@rrsoftware.com> writes: > >> "Simon Wright" <simon@pushface.org> wrote in message >> news:lytwthxq1t.fsf@pushface.org... >>> Bob Duff <bobduff@theworld.com> writes: >>> >>>> Yes, the predefined containers packages unfortunately don't allow you >>>> to specify the storage pool. >>> >>> An advantage of the Booch Components! >> >> Which works because there is only a single implementation of both the >> specs and bodies. If you don't specify the contents of the bodies, >> specifying the storage pool is nearly useless (the main use would be >> to use some sort of debugging pool), as the only pool implementations >> would have the same properties as the global default storage pool. > > Come to think, the time we used this was as the storage pool for > fixed-size objects, pointers to which were held in a bounded container. Exactly, that's what you want to do. But unless you put severe constraints on the implementation, you can't assume anything about the size of the objects allocated, so such techniques don't work (portably at least). Randy. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 14:06 ` Bob Duff 2015-07-06 14:16 ` Matthias-Christian Ott 2015-07-06 15:29 ` Simon Wright @ 2015-07-06 20:22 ` Randy Brukardt 2 siblings, 0 replies; 27+ messages in thread From: Randy Brukardt @ 2015-07-06 20:22 UTC (permalink / raw) "Bob Duff" <bobduff@theworld.com> wrote in message news:873811cre5.fsf@theworld.com... > Matthias-Christian Ott <ott@mirix.org> writes: ... >>...I suppose most implementations will >> raise a Storage_Error exception but the standard does not specify how >> the packages are to implemented so a program could simply crash and >> would still conform to the standard. > > No, running out of memory raises Storage_Error. The implementation > cannot "simply crash". > > It's true that the standard does not specify how the packages are > implemented, but they still have to be implemented correctly. > There's nothing in the RM that says they can crash, so they > can't. Right. Formally, only program executions that are erroneous can crash. So unless the Standard declares doing something erroneous, crashing is not an option. (Modulo compiler or runtime bugs, of course.) Running out of memory has to raise some exception, and since the only exception defined for that case is Storage_Error, and there isn't any other exception defined for most of the operations in question, there really isn't any other choice for a correct implementation of a library. No matter what it does under the covers. Randy. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 11:13 Dynamic allocation in the predefined language environment Matthias-Christian Ott 2015-07-06 13:04 ` G.B. 2015-07-06 14:06 ` Bob Duff @ 2015-07-06 18:45 ` Jeffrey R. Carter 2015-07-07 7:42 ` Dmitry A. Kazakov 3 siblings, 0 replies; 27+ messages in thread From: Jeffrey R. Carter @ 2015-07-06 18:45 UTC (permalink / raw) On 07/06/2015 04:13 AM, Matthias-Christian Ott wrote: > I need to store strings of unknown length. For security reasons I set > limits for the types of strings the software handles and I used > bounded-length strings to store them. However, it turned out that > bounded-length strings do not fit the use case very well because the > software sometimes has to convert between bounded-length strings of > various types which makes the code verbose and hard to read and more > importantly the limits are quite high so that I'm in trouble running out > of stack space. > > In order to avoid the limitations of bounded-length data structures I'm > currently looking for alternatives. > > Unbounded-length strings do not have this limitation but requires > dynamic memory allocation (or at least I see no other way to implement > it) which in turn requires error handling of memory allocation errors. > However, if I'm not mistaken neither Ada 95, nor Ada 2005, nor Ada 2012 > specify how memory allocation errors are to be reported or handled and > do not allow one to specify the storage pool from which unbounded-length > strings are allocated. The same seems to be true for other > unbounded/infinite data-structures. I suppose most implementations will > raise a Storage_Error exception but the standard does not specify how > the packages are to implemented so a program could simply crash and > would still conform to the standard. As Duff has pointed out, the language requires that Storage_Error be raised. Unbounded_String is essentially an instantiation of Vectors with Positive as the index type and Character as the element, with some added operations. As with all of the standard library, they are general purpose and may not be suitable where the S/W has specific needs. In this case, if knowing that Storage_Error will be raised doesn't help, you may need to create a version of variable-length strings that meets your requirements. -- Jeff Carter "It's symbolic of his struggle against reality." Monty Python's Life of Brian 78 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-06 11:13 Dynamic allocation in the predefined language environment Matthias-Christian Ott ` (2 preceding siblings ...) 2015-07-06 18:45 ` Jeffrey R. Carter @ 2015-07-07 7:42 ` Dmitry A. Kazakov 2015-07-07 8:23 ` Matthias-Christian Ott 3 siblings, 1 reply; 27+ messages in thread From: Dmitry A. Kazakov @ 2015-07-07 7:42 UTC (permalink / raw) On Mon, 06 Jul 2015 11:13:17 +0000, Matthias-Christian Ott wrote: > I need to store strings of unknown length. For security reasons I set > limits for the types of strings the software handles and I used > bounded-length strings to store them. Why don't you use plain strings allocated in an arena pool? Usually this covers most of cases where you need controlled allocation of constant and semi-constant strings. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-07 7:42 ` Dmitry A. Kazakov @ 2015-07-07 8:23 ` Matthias-Christian Ott 2015-07-07 8:46 ` Dmitry A. Kazakov 0 siblings, 1 reply; 27+ messages in thread From: Matthias-Christian Ott @ 2015-07-07 8:23 UTC (permalink / raw) On 07/07/15 07:42, Dmitry A. Kazakov wrote: > On Mon, 06 Jul 2015 11:13:17 +0000, Matthias-Christian Ott wrote: > >> I need to store strings of unknown length. For security reasons I set >> limits for the types of strings the software handles and I used >> bounded-length strings to store them. > > Why don't you use plain strings allocated in an arena pool? Usually this > covers most of cases where you need controlled allocation of constant and > semi-constant strings. I could this, but then I would have to implement reference counting as well or do manual memory management with all its disadvantages. - Matthias-Christian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Dynamic allocation in the predefined language environment 2015-07-07 8:23 ` Matthias-Christian Ott @ 2015-07-07 8:46 ` Dmitry A. Kazakov 0 siblings, 0 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2015-07-07 8:46 UTC (permalink / raw) On Tue, 07 Jul 2015 08:23:25 +0000, Matthias-Christian Ott wrote: > On 07/07/15 07:42, Dmitry A. Kazakov wrote: >> On Mon, 06 Jul 2015 11:13:17 +0000, Matthias-Christian Ott wrote: >> >>> I need to store strings of unknown length. For security reasons I set >>> limits for the types of strings the software handles and I used >>> bounded-length strings to store them. >> >> Why don't you use plain strings allocated in an arena pool? Usually this >> covers most of cases where you need controlled allocation of constant and >> semi-constant strings. > > I could this, but then I would have to implement reference counting as > well or do manual memory management with all its disadvantages. and advantages. An arena or LIFO pool assumes that you deallocate strings by groups. There are very few cases when strings are deallocated at all and even fewer ones when they are deallocated randomly. If you indeed have safety concerns, then that must certainly apply to your case. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
end of thread, other threads:[~2015-07-10 21:58 UTC | newest] Thread overview: 27+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-07-06 11:13 Dynamic allocation in the predefined language environment Matthias-Christian Ott 2015-07-06 13:04 ` G.B. 2015-07-06 14:21 ` Matthias-Christian Ott 2015-07-06 14:06 ` Bob Duff 2015-07-06 14:16 ` Matthias-Christian Ott 2015-07-06 14:23 ` G.B. 2015-07-06 14:43 ` Matthias-Christian Ott 2015-07-06 14:56 ` Bob Duff 2015-07-07 8:46 ` Matthias-Christian Ott 2015-07-07 22:32 ` Bob Duff 2015-07-08 19:47 ` Randy Brukardt 2015-07-08 21:08 ` Bob Duff 2015-07-10 21:58 ` Randy Brukardt 2015-07-08 21:16 ` Dmitry A. Kazakov 2015-07-06 14:45 ` Bob Duff 2015-07-06 20:28 ` Randy Brukardt 2015-07-07 8:49 ` Matthias-Christian Ott 2015-07-07 22:14 ` Bob Duff 2015-07-06 15:29 ` Simon Wright 2015-07-06 20:31 ` Randy Brukardt 2015-07-06 21:35 ` Simon Wright 2015-07-07 18:29 ` Randy Brukardt 2015-07-06 20:22 ` Randy Brukardt 2015-07-06 18:45 ` Jeffrey R. Carter 2015-07-07 7:42 ` Dmitry A. Kazakov 2015-07-07 8:23 ` Matthias-Christian Ott 2015-07-07 8:46 ` Dmitry A. Kazakov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox