I403%DMAFHT1.BITNET@CUNYVM.CUNY.EDU (Marc Wachowitz) (02/12/91)
There were several articles proposing various schemes how to deal with NEW running out of memory. Most of them only considered "polite abortion" of the program. I think it has to be possible to control the effect of every single invocation of NEW; sometimes an application may be able just to ignore the failure of a (in these cases usually large) allocation attempt. Termination handlers are no serious help in this case. For the benefit of existing & innocent programs, one might let the current behavious of NEW unchanged (but extend the language definition to define failure as a checked runtime error, which may be reported in an implemenation-dependent way). A new procedure (say TRYNEW) would be defined to be equivalent to NEW, except that it raises an exception (say NEWFAILURE) on failure. This exception should not be implicitly included in raises clauses, but should for convenience be directly visible (instead of needing to be imported from some interface) in every scope (i.e. be a predefined name). Considering the proposed features to install termination: I do strongly suggest that at least a simple variant be made part of the language spec. It should at least allow each module to register one procedure, which may then take care of data managed by the module (e.g. keeping a list of opened files and closing them on exit; I prefer that over the current scheme of auto-flushing writers).
jch@dyfed.rdg.dec.com (John Haxby) (02/14/91)
Checking for lack of memory doesn't really help in two out of three cases that I can think of. The good case is when the program has simply run up against the heap limit (eg 32Mb on ULTRIX 4.1) in which case, the program should abort gracefully--there are problems with this that I'll get to in a minute. The bad cases are two variants of the system running out of resources for (virtual) memory. In simple VM schema (like ULTRIX's) where space is pre-allocated or pre-reseved, running out is fairly serious as programs start failing all over the place; to be honest, in this scenario, system managers are likely to treat large processes (eg editors written in modula 3 consuming lots of memory) as fair game and any attempt by the program to struggle on is going to be fruitless. Admitedly, the user could choose to terminate gracefully, apart from the problem that I'll get to in a minute. The second variant of running out of VM resources is found in systems that do lazy allocation of resources (eg Mach) where the ru nning program is happily allocating memory, but when it tries to use that memory it gets peremptorily killed. The problem that I have been getting on to in a minute is what happens when the running process gets an exception to say that no more memory is available. What can it do? The answer is anything that doesn't involve allocating memory. In practice, I suspect, this wouldn't even including the editor writing files out to disk and freeing up associated buffers (at least not without some very careful programming). In any language where storage allocation is cheap and easy, there is a lot of it (although I don't know exactly how this affects Modula 3), and when you run out you may as well give up. The question arises: how much care *should* you take to deal with lack of VM resource? Well, how often do you run out? The attitude that Mach takes is "almost never, so you can allow deliberate over-allocation". Experience bears this out: I have been using an editor (admitedly not written in Modula anything) for several years that simply dies on lack of memory, and it has never died on me unless the system has gone down as well. So why go to all that trouble? It is *possible* to run out of VM, but it d oesn't happen all that often, and when it does, the consequences are so serious for everything that the odd application keeling over makes little difference. Reading that last paragraph again, the begging question is "under what circumstances *must* you deal with lack of memory?" The answer seems to be "when the application is critical". Under these circumstances, the application must take steps to ensure that it doesn't run short of memory when it needs it. The obvious way to do this is to ask the operating system how much memory can be allocated to this process before before it runs out of space. This, obviously, is highly O/S dependent, and some VM systems ( eg Mach's) may not even know how much space can be allocated before resources become a problem. The way *not* to do this is to introduce a "TRYNEW" request--this is too late. You need to know if VM shortfall is going to be a problem soon, not right now. If you need to allocate space to deal with the kidney dialysis (or however you spell it) in order to keep the patient alive, then "I'm sorry, I can't allocate enough memory is going to help" You need to know well in advance that in order to allocate enoug h memory for what you might need to do that you need to kill that emacs or that motif application. This problem gets to the stage where we no longer deal with language constructs, but operating system services and application requirements to *avoid* the lack of memory exceptions, not to do something sensible when you get them, because nothing sensible can be done at that late stage. [Sorry if all this is garbled, it's written in a bit of a rush and I haven't had time to review it properly (to all those who say that I shouldn't have written it in the first place, I am inclined to agree] -- John Haxby, Definitively Wrong. Digital <jch@wessex.rdg.dec.com> Reading, England <...!ukc!wessex!jch>
Mike_Spreitzer.PARC@xerox.com (02/14/91)
Indeed, it seems that the way for a careful program to avoid allocating itself into a corner involves a two-level allocation scheme. At the lower level, where NEW works, there must be multiple heaps; let's call these ZONEs. Each invocation of NEW is given the ZONE from which the object is to be allocated. At the upper level, ZONEs are created with specific sizes, and associated with specific user requests. The necessary size of a ZONE is computed by the program from the user request. If the ZONE creation fails, the user is told his request can't be satisfied. If the ZONE creation succeeds, the request is granted and worked on. The idea is that the programmer has estimated, calculated, or measured a relation between user requests and the amount of memory needed to satisfy those requests. This brings the failure point forward to the time at which refusal of service is reasonable. In the dialysis example, the user request would be something like "maintain a new patient of such-and-such a weight, blood type, etc". If there isn't enough memory to do that, the user finds out about it up front, and has a chance to take plausible corrective action (try a different ward, kick off some other users, whatever). I know estimating and measuring are not really good enough in critical applications. And calculating can be very tedious or outright impossible, depending on the structure of the application. But what choice is there, really? I take comfort in the philosophy that abstractions are for programmers to make and compilers (and other tools) to break, and thus the hope that I won't have to do such calculations by hand. Mike
new@ee.udel.edu (Darren New) (02/15/91)
Here's some more ideas on the subject:
The idea that a non-portable interface is needed to have a
failure-proof NEW seems to me as silly as a non-portable end-of-file
indication and as dangerous as an "open" call that crashes when the
file doesn't exist. I feel that every run-time error should be able to
be caught/avoided by a program; how else does one make "robust"
programs? The argument that "If there just isn't any more memory then
there just isn't anything you can do" seems invalid given that plenty
of C, Smalltalk, Ada, etc programs seem to handle the problem just
fine.
I therefore throw out the following ideas for discussion. The main idea
is that there is a "safe" allocator called TRYNEW and a "dangerous"
allocator called NEW. TRYNEW will fail before NEW does, allowing
applications written with TRYNEW to stop allocating memory while still
leaving enough for routines to use NEW.
WHEREAS changing the semantics of NEW is unacceptable, except possibly
to require that running out of memory raise an exception,
WHEREAS running out of stack space is probably going to be difficult to
catch, even with an exception handler,
WHEREAS different threads can request allocations concurrently, making
check-then-allocate designs awkward,
WHEREAS different implementation modules may need different amounts of
memory even for the same interface module,
WHEREAS the OS may not provide any way of finding out how much memory
is left except via failed allocations,
WHEREAS NEW() has a syntax impossible for the user to duplicate in
his/her own interface module,
WHEREAS running out of memory should not cause one to be unable to
allocate more memory
WITNESSETH the following proposed interface, in which "Traced" can be
replaced by "Untraced" and duplicated in order to handle both heaps.
TYPE ReserveStatusType = {Unreserved, Reserved, Exhausted};
EXCEPTION NOMEM(size : INTEGER);
Size is the number of kilobytes in the request that caused the failure.
PROCEDURE SetTracedRequirements(minimum, maximum : INTEGER := 0) RAISES {NOMEM};
This sets the minimum and maximum reservation amounts atomically.
This will reserve memory for NEW, not TRYNEW.
A -1 means no change. Here and everywhere, measurements are in KBytes.
Clears an "Exhausted" error if one exists and enough memory is now available.
PROCEDURE IncTracedRequirements(minimum, maximum : INTEGER := 0) RAISES {NOMEM};
This increments the minimum and maximum reservation amounts by the
indicated amounts atomically. Typically, this would be used to reserve
memory by calling it during the body of a library module. Can be called
with (0,0) to determine if enough memory is available.
Clears an "Exhausted" error if one exists and enough memory is now available.
PROCEDURE DecTracedRequirements(minimum, maximum : INTEGER := 0) RAISES {NOMEM};
This decrements the minimum and maximum reservation amounts by the
indicated amounts atomically, handy when a module stops needing memory.
Clears an "Exhausted" error if one exists and enough memory is now available.
PROCEDURE GetTracedRequirements(VAR maximum, maximum : INTEGER);
This returns the current minimum and maximum reservation amounts
atomically.
PROCEDURE GetTracedReserveStatus() : ReserveType;
This returns one of three statuses: Unreserved means that
either the maximum reserve is zero or that TRYNEW has not
been called or there is enough memory left and the runtime
system knows that. Reserved means that some memory has
actually been allocated. Exhausted means that an allocation
has failed since last time the requirements were set.
PROCEDURE RegisterTraced(PROCEDURE P(size : INTEGER) RAISES {NOMEM},
priority : INTEGER);
P will be one of the procedures called in an attempt to free up memory.
It will be called after all procedures of a lower priority
have been called and failed.
PROCEDURE DeregisterTraced(PROCEDURE P(size : INTEGER) RAISES {NOMEM});
P will no longer be called in an attempt to free up memory.
Then "TRYNEW" (whose name I don't like but I can't think of anything
better, maybe MALLOC?) would behave as follows:
Initially, no memory is reserved and GetTracedReserveStatus returns
Unreserved. No procedures are registered. TRYNEW will always succeed if
(maximum <= available). TRYNEW will always fail if (available <
minimum) or (ReservedStatus = Exhausted).
If TRYNEW fails, it first calls each registered procedure repeatedly
with the amount of memory it is trying to allocate. If the procedure
does not raise an exception, it retries. If the procedure does raise an
exception, it tries the next procedure. When all procedures have raised
exceptions, it sets the reserved status to Exhausted and raises NOMEM.
Maybe we would want a TRYNEW that does not call the procedures, or only
calls some (up to a certain priority), allowing (for example) caches of
disk information to not be flushed by attempts to allocate caches for
in-RAM information. But this seems to be getting excessive.
Hence, libraries that cache could use RegisterTraced to free buffers
and such. Libraries that use NEW (especially during cleanup) could use
IncTracedRequirements at the start of the module body. Libraries that
don't really care could simply continue to use NEW. Attempts to
allocate the last little bit of memory via NEW would work but via
TRYNEW would fail. If the runtime system cannot determine how much
memory is available easily or quickly, this could be implemented by
actually allocating the maximum amount of memory and then when NEW
fails, deallocating that memory and trying again.
-- Darren
--
--- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
----- Network Protocols, Graphics, Programming Languages,
Formal Description Techniques (esp. Estelle), Coffee, Amigas -----
=+=+=+ Let GROPE be an N-tuple where ... +=+=+=jonb@vector.Dallas.TX.US (Jon Buller) (02/15/91)
This situation has been known to occur often on 128K Macs (sometimes on larger ones too 8-). What is usually done there, is to pre-allocate a block of memory (10KB seems good for many apps, adjust to taste). When New fails, deallocate the block, clean up, and shut down (or, let the user close some files, windows, and what-have-you, and keep running). If this is done, an exception from New is about the best thing I would want to happen, since I can go into my rainy-day store of memory when I get the exception, and quit. Or, if I'm careful, clean up memory, re-allocate my emergency memory block, and keep going. In any case, I like getting exceptions better than simply getting NIL, or getting my program killed and losing everything. I can handle getting NIL back, but I would probably just use My_New which calls New, and raises an exception if it failed. I once had to write code that checked each allocation, and jumped out of 5 or so procedure calls to return to a main loop on failure, and try to recover. It was in a Pascal without inter-block goto's, so I had to resort to large if-then's in every procedure. The result was MUCH more difficult to read, debug, and look at. I wish I had this kind of stuff back then... -- Jon Buller jonb@vector.dallas.tx.us ..!texsun!vector!jonb FROM Fortune IMPORT Quote; FROM Lawyers IMPORT Disclaimer;
new@ee.udel.edu (Darren New) (02/20/91)
I tried to mail this, but it bounced.
=> EXCEPTION NOMEM(size : INTEGER);
=> Size is the number of kilobytes in the request that caused
=> the failure.
=>
=> Huh? Why kilobytes? Suppose I run out of memory requesting 10 bytes.
=> That's closer to 0K than 1K--it's conceptually unclean to run out of
=> memory when requesting none of it. Is there some sort of good reason
=> for this unnecessary factor of 1000?
Well, I was thinking that integers may not be big enough to hold an
address. That is, you could have more addressable units than integers,
making large allocations difficult to describe. (I believe I saw
something like this in libraries somewhere, where the base-2 log of a
size was used instead of the actual size.) Naturally, the request would
be rounded up to the next 1024 unit. The intention of giving the size
was to allow the program freeing memory to only free what was needed by
somebody else. For example, a disk cache could only flush and free 20
buffers instead of all 600. Freeing too much would not be a problem.
(Nor would freeing too little in my scheme, due to the retries.)
-- Darren
--
--- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
----- Network Protocols, Graphics, Programming Languages,
Formal Description Techniques (esp. Estelle), Coffee, Amigas -----
=+=+=+ Let GROPE be an N-tuple where ... +=+=+=