🚀 go-pugleaf

jem@bii.bruker.com (Joe Meier) wrote:
>   We have a problem with a program running under UNIX (SGI IRIX 5.x).  
>It uses X11 for a graphical user interface.  
>The program allocates and frees large amounts of memory for data 
>(sometimes chunks as big as 20M).  The problem is that in a relatively
>short time the system runs out of swap sapce and we have to kill the program.
>We have investigated the problem and it seems to be that the allocated memory
>is getting segmented, so that even though the memory is freed by calls to
>"free", the next malloc does not necessairly use the freed space because it
>cannot find a large enough contiguous block and instead allocates more from
>the system.  When we were working with smaller data sizes this was not a 
>problem, but the bigger data sizes is causing some svere problems.  The 
>first question is whether anyone else has encountered similar problems
>and what caused them and how they solved it?  Also, I wanted to know if 
>there exists any intelligant memory managers that will move memory blocks
>in order to keep all the free space in on contiguous location?  I think this
>would go a long way towards solving our problems???  Of-course if anyone 
>has other sugestions for what the cause of our problems are, they would be
>greatly appreciated.
>
>   Since, I am cross posting this to several news groups, I ask that
>responses be e-mailed directly to me (at jem@bruker.com) so that I can more
>eaisly keep track of them.  I will post a summary (for those interested) once
>I have complied the responses.
>
>Thanks for the help,
>
>Joe Meier

Seems like a while ago there was a discussion about freed memory not really
shrinking a process data segment. The pitfall being memory that was idle could
continue to tie up swap space. 

Jeff
jdickson@vtol.jpl.nasa.gov

jem@bii.bruker.com (Joe Meier) writes:

>   We have a problem with a program running under UNIX (SGI IRIX 5.x).  
>It uses X11 for a graphical user interface.  
>The program allocates and frees large amounts of memory for data 
>(sometimes chunks as big as 20M).  The problem is that in a relatively
>short time the system runs out of swap sapce and we have to kill the program.
>We have investigated the problem and it seems to be that the allocated memory
>is getting segmented, so that even though the memory is freed by calls to
>"free", the next malloc does not necessairly use the freed space because it
>cannot find a large enough contiguous block and instead allocates more from
>the system.  When we were working with smaller data sizes this was not a 
>problem, but the bigger data sizes is causing some svere problems.  The 
>first question is whether anyone else has encountered similar problems
>and what caused them and how they solved it?

The cause is most probably heap fragmentation.  Conventional malloc()/free()
implementations can only release contiguous regions of memory at the top of
the heap, not anything in the middle.

You might want to check out the `Free memory:  Why isn't it doing anything ?'
thread on comp.sys.sgi.misc.  In short, try:

ftp://g.oswego.edu:pub/misc/malloc-2.6.2.c

and see if it makes a difference.  This implementation uses mmap() on
large chunks, which can be returned to the system immediately on a
call to free().

Regards,
Wolfram.

It sounds like you have specialized memory management needs that malloc wasn't
designed to handle.  Writing your own memory management is the way to go.  Without
knowing more about the behavior of your program I couldn't tell you much more, 
except that memory management is a well understood subset of computer science with
extensive documentation.  Many computer science texts in algorithms or operating
systems speak extensively on these issues.  If you're lucky your memory requests
come in fixed sizes for at least a subset of the requests...it's quite efficient
to manage pools of fixed size memory.  For variable sizes, you'll have to use
something like a closest fit with coalescence.  Another good source of information
are magazines like Dr. Dobbs.  I'd bet the Dr. has run at least a couple of articles
about memory management a year for years and years.  I seem to remember an issue
devoted to it within the last couple of years.

-- 
Patrick J. Horgan         Broadvision Inc.
phorgan@broadvision.com   333 Distel Circle          Have horse
Phone : (415)943-3677     Los Altos, CA 94022-1404   will ride.
FAX   : (415)934-3701  Opinions mine, not my employers except by coincidence.

In article <DM0Jv9.9F4@bii.bruker.com>, Joe Meier <jem@bii.bruker.com> wrote:
>   We have a problem with a program running under UNIX (SGI IRIX 5.x).  
>It uses X11 for a graphical user interface.  
>The program allocates and frees large amounts of memory for data 
>(sometimes chunks as big as 20M).  The problem is that in a relatively
>short time the system runs out of swap sapce and we have to kill the program.
>We have investigated the problem and it seems to be that the allocated memory
>is getting segmented, so that even though the memory is freed by calls to
>"free", the next malloc does not necessairly use the freed space because it
>cannot find a large enough contiguous block and instead allocates more from
>the system.  When we were working with smaller data sizes this was not a 
>problem, but the bigger data sizes is causing some svere problems.  The 
>first question is whether anyone else has encountered similar problems
>and what caused them and how they solved it?  Also, I wanted to know if 
>there exists any intelligant memory managers that will move memory blocks
>in order to keep all the free space in on contiguous location?  I think this
>would go a long way towards solving our problems???  Of-course if anyone 
>has other sugestions for what the cause of our problems are, they would be
>greatly appreciated.

These problems have been researched since the dope-smoking 60's and probably
earlier.

There are two ways to do dynamic memory allocation. (This is what we are talking
about. "Memory Mangement" refers to the strategies implemented in the operating
system for assigning memory to tasks and OS procedures. )

You can allocate in such a way that the address of a block does not change, or
you can use an extra level of indirection that allows you to perform "heap
compaction" to coalesce unused free areas into one big free block. THis is not
the same as "garbage collection". The latter refers to an allocation scheme in
which free blocks are _never_ reused, nor kept track of. When the heap runs out
of space, the garbage compactor loops over the allocated blocks and squeezes
them together to take up the slack in between. There is never a list of free
blocks, that's why these areas are called "garbage".

If you don't allow for heap compaction, there is no general method to avoid
fragmentation. In a JACM article appearing in, I think, vol. 18 of the JACM
(circa 1971), a fellow by the name of J. M. Robson published a proof that
a program which allocates and frees blocks that are up to 2^b cells in size
such that the total memory allocated never exceeds N cells will, in the worst
case, grow to occupy a footprint of  N * (1+b) cells, such that any further
requests for a block that is 1..2^b large will fail and require that the heap
increase further.

Robson proved this result only for block sizes that are dyadic powers: 1, 2, 4,
8, 16, ... 2^b.

Still, it is serious. If you are allocating blocks up to 4KB (2^12 bytes) and
over the lifetime of your program, a maximum of only 1MB is claimed at any one
time, you could end up at a situation where the program has a 13MB heap and yet
cannot satisfy the largest possible request (4KB), which also means that it's
unlikely that "holes" in the heap can be returned to the OS in the form of
discrete pages, if your OS uses 4KB pages or larger.

Since you are allocating about 20MB blocks, you are looking at, say, a max
block size of 2^25 (the next highest power of two for the sake of convenience).
Expect your worst case allocation behaviour to consume 16x as much memory as it
is supposed to. For example, if your program uses 50MB, you could eat 800MB
(assuming you have it). This is assuming that you can have very small
allocations all the way down to one byte. Say that you never allocate less than
a megabyte. You can then work in megabyte units. You allocate blocks of up to
2^5 (32) megabytes, and could claim up to six times as much memory as you ask
for, or 300MB out with only 50MB allocated. 

Of course, the worst case scenario is accomplished by an optimal "attacker"
(requestor) going against an optimal "defender" (allocator strategy). The
actual results in a real application may be better, and can be improved by
using a different allocator strategy.

I suggest you look for alternative libraries, and don't count out heap
compaction. It's possible to design allocators that allow for heap compaction,
yet have entry points that are backward-compatible with malloc() and friends
(these will "lock" the allocated chunk in place so that it cannot be moved
during compaction, satisfying the malloc() paradigm that the address of a block
doesn't change).

There are all kinds of strategies for malloc-type allocation: best fit, quick
fit, binary buddies, fibonacci buddies, etc.

Check out the Knuth volumes as well as that JACM article if you want to read
Robson's gloomy number-theoretical proof.

Look at the design of your program and see if you can't improve the behavior by
restructuring the way it does allocation. The order of allocations matters. A
strategic "attacker" wishing to maximize memory waste (with constraints on
total memory and maximum block size) depends on a devilish order of allocations
which forces the defending player to helplessly dole out memory.



>   Since, I am cross posting this to several news groups, I ask that
>responses be e-mailed directly to me (at jem@bruker.com) so that I can more
>eaisly keep track of them.  I will post a summary (for those interested) once
>I have complied the responses.

Also, consider enlisting the aid of the UNIX operating system. Since you are
working with large blocks, your heap will contain some large holes. These holes
_can_ be returned to the operating system so that they are only virtual holes
and don't use up any (or hardly any) memory. 


Have you considered using anonymous memory maps via the mmap()/munmap() system
calls? When you munmap() a mmap()ed region, it is truly _gone_. Your OS has a
large virtual address space in which to place memory mapped objects. Even if
you waste a half a page on each one (due to the alignment of mapped regions),
you will still win by eliminating the heap problem.

Try mmap!
--