🚀 go-pugleaf

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!
--