Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!udel!ee.udel.edu
From: new@ee.udel.edu (Darren New)
Newsgroups: comp.lang.modula3
Subject: Re: NEW out of memory
Message-ID: <44648@nigel.ee.udel.edu>
Date: 14 Feb 91 17:09:14 GMT
References: <91Feb14.074224pst.16323@alpha.xerox.com>
Sender: usenet@ee.udel.edu
Organization: University of Delaware
Lines: 121
Nntp-Posting-Host: estelle.ee.udel.edu


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 ... +=+=+=