ir@cel.co.uk (ian reid) (10/25/90)
Hi,
Just seeking a bit of historical perspective here on alloca and malloc. Forgive
me if this has already been discussed, but occassionaly we suffer breaks in news
at this site, usually after I have posted an article or question :-(.
There seems to me to be a fundamental flaw in the implementation of malloc, as I
can determine the implementation from TFM.
As I understand it malloc(3) manages an area of memory in the data segment, if
there is insufficient space in the data segment a call to sbrk(2) is made to
increase the size of the data segment, and hence the memory available for malloc
to manage. The size of the application therefore grows by the amount of memory
added to the data segment.
The problem is that there is no way that this memory can be returned to the
operating system, at least no way documented on the sbrk(2) manual page which is
where I would expect to find it, after all free(3) is documented on the malloc
page. free simply returns the memory to the pool managed by malloc not to the
operating system, the documented behaviour.
Well imagine this, an application mallocs (insert a number here which is a large
amount of memory for system), this is a one-off occurrence and this much memory
is never needed again. But the application size can never shrink, therefore a
lot of memory which is not being used is unavailable to the system.
I'm specualting that alloca(3) which allocates memory on the stack frame was
invented for two reasons. Firstly to overcome the above flaw in malloc, and
secondly for speed. alloca has it's own flaws though, it's operating system,
compiler and architecture dependant (I think this means it's not portable:-))
, and as if this weren't enough there is no documented way to grow the stack
segment so there's less chance of being able to get the memory you want.
Is this a fair summary. email, flames welcome.
--
Ian Reid #include <std/disclaimer.h>
UUCP: ir@cel.uucp or ir@cel.co.uk or ...!{ukc,mcsun,uunet}!cel!ir
"Computers..proof positive that no-one yet understands how to describe any real
world situation in 0's and 1's."kaleb@thyme.jpl.nasa.gov (Kaleb Keithley ) (10/25/90)
In article <6793@suns302.cel.co.uk> ir@cel.co.uk (ian reid) writes: > >The problem is that there is no way that this memory can be returned to the >operating system, at least no way documented on the sbrk(2) manual page which is >where I would expect to find it, after all free(3) is documented on the malloc >page. free simply returns the memory to the pool managed by malloc not to the >operating system, the documented behaviour. sbrk may be passed a negative number, effectively shrinking the data segment size, although no implementation of malloc/free that I know of will do this. You could always roll your own malloc/free that does return free'd memory to the system this way. Good starting points are any of the malloc/free sources in gnu emacs, perl, or gwm. All three of these are based on the 4.3 bsd malloc/free, massaged by Caltech, and then polished by Stallman, Wall, and Nahaboo respectively. -- Kaleb Keithley Jet Propulsion Labs kaleb@thyme.jpl.nasa.gov causing trouble again.
richard@aiai.ed.ac.uk (Richard Tobin) (10/26/90)
In article <6793@suns302.cel.co.uk> ir@cel.co.uk (ian reid) writes: >The problem is that there is no way that this memory can be returned to the >operating system This is true, at least in most unixes. Hence it can hardly be a flaw in malloc() (or rather free()) that it doesn't do it. Even if sbrk() did allow memory to be returned, it probably wouldn't be right for malloc() to do it by default. Most programs (sorry, no evidence for this claim) don't do one large malloc() and then throw it away - they either don't free memory at all, or they malloc() and free() at random times. Programs of this last type would suffer heavily if malloc() had to get its memory by a system call each time. >I'm specualting that alloca(3) which allocates memory on the stack frame was >invented for two reasons. Firstly to overcome the above flaw in malloc, and Alloca() has the same problem. Stack memory isn't returned to the system either. >secondly for speed. Alloca() will indeed quite possibly be faster - maybe just changing the stack pointer. But its main advantage is that you don't need to free it - it goes away by itself, as if it were a dynamically-sized local array. >and as if this weren't enough there is no documented way to grow the stack >segment so there's less chance of being able to get the memory you want. Alloca() has this problem to exactly the same extent that local (auto) variables have it. In unix, the stack grows automatically when the process tries to access space beyond the end of it. -- Richard -- Richard Tobin, JANET: R.Tobin@uk.ac.ed AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin
rwelch@diana.cair.du.edu (RANDY S WELCH) (10/26/90)
In article <6793@suns302.cel.co.uk> ir@cel.co.uk (ian reid) writes:
The problem is that there is no way that this memory can be returned to
the operating system, at least no way documented on the sbrk(2) manual
page which is where I would expect to find it, after all free(3) is
documented on the malloc page. free simply returns the memory to the
pool managed by malloc not to the operating system, the documented
behaviour.
Well imagine this, an application mallocs (insert a number here which
is a large amount of memory for system), this is a one-off occurrence
and this much memory is never needed again. But the application size
can never shrink, therefore a lot of memory which is not being used is
unavailable to the system.
Ian Reid #include <std/disclaimer.h>
UUCP: ir@cel.uucp or ir@cel.co.uk or ...!{ukc,mcsun,uunet}!cel!ir
"Computers..proof positive that no-one yet understands how to describe any real
world situation in 0's and 1's."
You might want take a look at the malloc that is on prep.ai.mit.edu. It
is capable of returning memory back to the system. And it does seem to
work. I am currently using as the malloc when compiling GNU Emacs. And
it seems to work rather well. Worth looking at.
-randy
--
Randy Welch Mail to : ...!ncar!scicom!bldr!randy or rwelch@du.edu
Boulder, CO VOICE : 303-442-6717
"Unfortunately, life contains an unavoidable element of unpredictability"
-David Lynch "The Angriest Dog in the World"gwyn@smoke.brl.mil (Doug Gwyn) (10/26/90)
In article <6793@suns302.cel.co.uk> ir@cel.co.uk (ian reid) writes: >There seems to me to be a fundamental flaw in the implementation of malloc, >as I can determine the implementation from TFM. No, malloc() is okay. >As I understand it malloc(3) manages an area of memory in the data segment, >if there is insufficient space in the data segment a call to sbrk(2) is made >to increase the size of the data segment, and hence the memory available for >malloc to manage. The size of the application therefore grows by the amount >of memory added to the data segment. Essentially correct. >The problem is that there is no way that this memory can be returned to the >operating system, at least no way documented on the sbrk(2) manual page ... Theoretically, brk()/sbrk() can be used to reduce the program break as well as increase it. However, most malloc() implementations don't bother to try to detect the opportuntity to do this, because it isn't really very useful. >Well imagine this, an application mallocs (insert a number here which is a >large amount of memory for system), this is a one-off occurrence and this >much memory is never needed again. But the application size can never >shrink, therefore a lot of memory which is not being used is unavailable to >the system. In practice this seldom matters, particularly in a demand-paged virtual memory environment, which is used by most UNIX implementations on "real" computers these days. >I'm specualting that alloca(3) which allocates memory on the stack frame was >invented for two reasons. Firstly to overcome the above flaw in malloc, and >secondly for speed. alloca has it's own flaws though, it's operating system, >compiler and architecture dependant (I think this means it's not portable:-)) >, and as if this weren't enough there is no documented way to grow the stack >segment so there's less chance of being able to get the memory you want. alloca()'s main raison d'etre is to automatically garbage collect the allocated storage when the containing function's dynamic scope terminates. Of course auto variables have this property too, but they require that the needed space be known precisely in advance, whereas alloca() steals space as requested and is thus more flexible. There are architectures for which implementing alloca() is impractical, and you should simply not count on its being universally available. I published a "mostly portable" public-domain implementation that has seen wide distribution, but I'll be among the first to admit that it has its flaws. I intended it only as an aid for people trying to port already- written code that relied unduly heavily on alloca(), not for new code. Note also that machine machines have much more stringent limits on the total amount of stack space allocated than on malloc()ed heap space.