Dynamic allocation in the predefined language environment

Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[G.B.]

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.

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

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

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[G.B.]

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.)

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

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

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

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

Re: Dynamic allocation in the predefined language environment

[Simon Wright]

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!

Re: Dynamic allocation in the predefined language environment

[Jeffrey R. Carter]

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

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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.

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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.

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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.

Re: Dynamic allocation in the predefined language environment

[Simon Wright]

"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.

Re: Dynamic allocation in the predefined language environment

[Dmitry A. Kazakov]

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

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[Dmitry A. Kazakov]

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

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[Matthias-Christian Ott]

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

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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.

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

Matthias-Christian Ott <ott@mirix.org> writes:

> You have fully convinced me.

That's good to know.

- Bob

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

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

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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 

Re: Dynamic allocation in the predefined language environment

[Bob Duff]

"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

Re: Dynamic allocation in the predefined language environment

[Dmitry A. Kazakov]

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

Re: Dynamic allocation in the predefined language environment

[Randy Brukardt]

"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.