[comp.lang.c] Buddy system allocator?

rtm@grenada.UUCP (Richard Minner) (10/21/89)

From Doug Gwyn:
|In article <1175@svx.SV.DG.COM> gary@svx.SV.DG.COM () writes:
|>The correct answer is "malloc/free is somewhat broken in Sunos 4.0.1-3".
|>This has been mentioned before, in a Feb. Sun Spots article - here it is...
|
| That sounds more like a "buddy system" allocator working normally.

I'll bite, how does a "buddy system" allocator work, normally?
I can imagine why free'd blocks might "shrink" a bit but I'd
appreciate an overview from someone who actually knows.  Also,
if such a system can normally produce what I consider to be
counter-intuitive results (and gary@svx.SV.DG.COM considers
"somewhat broken"), what are its advantages?

If it's overly complex, a good reference would be nice.
Thanks.


-- 
Richard Minner  || {uunet,sun,well}!island!rtm     (916) 447-7081 ||
                || Island Graphics Corporation     Sacramento, CA ||

moraes@cs.toronto.edu (Mark Moraes) (10/22/89)

rtm@grenada.UUCP (Richard Minner) writes:
>I'll bite, how does a "buddy system" allocator work, normally?

It maintains free lists of blocks in sizes of powers of two. When
satisfying a request, it finds the smallest power of two larger than
the request and returns that block. If it can't find a block in that
free list, it goes to the free list for the next higher size and
splits a block there into two "buddies" and returns one, putting the
other in the appropriate free list. (The process recurses to higher
sizes if till a free list with a free block is found or till it
becomes necessary to get more memory from the system). The buddy's
address can be computed cheaply. When you free a block, it is easy to
coalesce -- check if the block's buddy is free, if so, coalesce them,
check if the resulting coalesced block's buddy is free and so on.

Since all blocks are powers of two, this can waste a fair bit of
memory for large blocks. (Especially as most people seem to
malloc(power of 2), which gets rounded up to the next power of two
since the allocator stores some size and debugging information in the
block as well)

The BSD4.3 malloc (Chris Kingsley's malloc, Caltech malloc -- it goes by
various names) is often called a buddy system allocator since it
splits blocks by powers of two when allocating, even though it doesn't
do the coalescing on free. (This lack of coalescing can lead to nasty
behaviour under some allocation patterns -- for the usual allocation
pattern where a program continuously allocates blocks in a few sizes,
this is not a problem. For applications that handle dynamically
allocated strings that vary in size over a wide range, this allocator
sometimes runs the machine out of memory)

>If it's overly complex, a good reference would be nice.

It's not overly complex, but anyway:

%V 1
%A Knuth, Donald E.
%T The art of computer programming: Fundamental Algorithms
%C Reading, Mass.
%I Addison-Wesley Pub. Co.
%D [1968-]

There's a section devoted to dynamic memory allocation -- describes a
simple first fit algorithm, a boundary tags first fit algorithm and a
buddy system. I usually prefer the boundary tags algorithm with some
of the mods he describes suggests in the Exercises --it gives good
performance over a wider range of allocation patterns and wastes less
space, something I think is important for any application doing a lot
of allocation. He's got a simple random simulation that stresses
allocators.

A good comparative study of mallocs is:

%A David G. Korn
%A Kiem-Phong Vo
%T In search of a better malloc
%J Proceedings of the USENIX 1985 Summer Conference
%C Portland, Oregon
%D June 1985
%K usenix85s
%P 489-506

They implement the simulation Knuth describes and test numerous
mallocs with it.

gwyn@smoke.BRL.MIL (Doug Gwyn) (10/23/89)

In article <426@grenada.UUCP> rtm@grenada.UUCP (Richard Minner) writes:
>If it's overly complex, a good reference would be nice.

Knuth Vol. 1.

gwyn@smoke.BRL.MIL (Doug Gwyn) (10/23/89)

In article <89Oct22.120811edt.3343@neat.cs.toronto.edu> moraes@cs.toronto.edu (Mark Moraes) writes:
>I usually prefer the boundary tags algorithm with some of the mods
>[Kunth] describes suggests in the Exercises ...

That's also the one I usually choose when I have to implement a general
memory allocator.  If anyone is going to implement this, note that the
solution to exercise 2.5-19 given in the Second Edition has a bug in it:
upon allocation failure, one must not leave ROVER pointing to the
collapsed tail; set it to LOC(AVAIL).  Also, the algorithm given in the
solution to exercise 1.5-12 can be improved upon.  I won't say how,
since you should study this stuff before implementing it, to the point
that you should be able to figure it out yourself.