Buddy system allocator?

[Mark Moraes]

rtm at 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.