Buddy allocator combining adjectent holes

[NickJohnson]

I'm trying to write a heap for my userspace C library. I want speed and simplicity over memory use, so I'm pretty sure I want to use a buddy allocator for this. (Afaik) I understand how a buddy allocator works, except for this one thing. When a piece of memory is freed, and has an adjacent "buddy" hole that it can be combined with to reduce fragmentation, how can this fact be determined efficiently? Surely the entire list of holes of the same size is not searched on each free. I have a feeling it has to do with using a magic number, but I just wanted to be sure, because that seems like it would be unreliable.

Thanks!

[Hangin10]

In buddy allocators the sections of allocated memory are all aligned, so you'd just have to look at the series of bitmaps, see if the next (or previous) section is also free, and if freeing this new section makes the next larger unit completely free, etc.

You probably should not use a buddy allocator for your userspace malloc.

[NickJohnson]

In buddy allocators the sections of allocated memory are all aligned, so you'd just have to look at the series of bitmaps, see if the next (or previous) section is also free, and if freeing this new section makes the next larger unit completely free, etc.

Hmm... I was under the impression that a buddy allocator used a linked list of holes and a binary tree instead of a bitmap. It seems like a bitmap would create a lot of overhead - allocating n bytes would require setting n bits, which would take at least n/32 writes. Freeing and checking the way you suggested would require checking n bits: same deal.

[NickJohnson]

Okay, I think I've figured it out. If only the parts of the bitmap that correspond to the beginning of the blocks or holes are paid attention to, the algorithm regains its θ(logn) - θ(1) properties. That's what I needed to know - thanks!