Re: Dynamic allocation in the predefined language environment

[Bob Duff <bobduff@theworld.com>]

"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