Buddy System Memory Allocator

[Mark]

Hello

I am looking at writing a buddy system memory allocator and am not sure how
best to implement the tracking of allocated blocks. I've read lots of papers
and articles regarding buddy allocation and think that I understand the
concepts quite well. I am working with embedded systems so I want to keep
the memory and processing overheads as low as possible.

I understand how I am going to handle free blocks, i.e. using a linked-list
where, apart from the initial pointer, the free list pointers are contained
within the free blocks themselves. I am going to maintain a free list per
block size, so the only additional memory overhead is an initial pointer per
block size. In this case, for example, 32 free lists will cover up to a
total memory of 2^31 * (minimum block size), so I could quite easily operate
with a minimum block size of 1 byte if I so desired.

However, I'm not sure about the tracking of allocated blocks. I want a quick
and easy way of tracking allocated blocks and buddies using a method that
doesn't involve dynamically growing a linked-list or tree at run-time. It
seems that this is commonly done using a bitmap, but I don't understand how
you keep this manageable if you have a reasonable amount of memory and want
a relatively small minimum block size. A bitmap of 32 bits will only give me
coverage for 8k of memory if I use a minimum block size of 256 bytes. I am
trying to figure out how to avoid having a bitmap that is hundreds or
thousands of bits long. I'm sure that there must be a better way.

Any help would be much appreciated.

Thanks

Mark

[BartC]

"Mark" <ma...@dibsco.co.uk> wrote in message news:_Iges.3$jY...@fx25.am4...

>It seems that this is commonly done using a bitmap, but I don't understand
>how you keep this manageable if you have a reasonable amount of memory and
>want a relatively small minimum block size. A bitmap of 32 bits will only
>give me coverage for 8k of memory if I use a minimum block size of 256
>bytes. I am trying to figure out how to avoid having a bitmap that is
>hundreds or thousands of bits long. I'm sure that there must be a better
>way.

What would be the problem of a bitmap that large?

The memory overheads seem to be only 0.05% (512 bytes per 1MB), so it can't
be memory. Or do you need a bitmap for every block size? (But then, with the
other bitmaps getting smaller, the overhead just doubles in total.)

--
Bartc

[Pascal J. Bourguignon]

The simpliest is to keep the size with the allocated blocks: allocate a
word more than requested, to store the size, and return the addess of the
first byte after the size. You may want to still return aligned pointers
so you may want to store the size on a smaller alignment.

Another solution, you could use it for small blocks, is to allocate blocks
of specific sizes from specific "pages", or superblock, where you can keep
a block size and a bitmap of allocater blocks inside the superblock. I
would do that for blocks up two or three words.


--
__Pascal J. Bourguignon__

[BartC]

"Pascal J. Bourguignon" <p...@informatimago.com> wrote in message
news:1731845837372288843.910...@news.individual.net...

> "Mark" <ma...@dibsco.co.uk> wrote:

>> of memory and want a relatively small minimum block size. A bitmap of 32
>> bits will only give me coverage for 8k of memory if I use a minimum block
>> size of 256 bytes. I am trying to figure out how to avoid having a bitmap
>> that is hundreds or thousands of bits long. I'm sure that there must be a
>> better way.

> The simpliest is to keep the size with the allocated blocks: allocate a
> word more than requested, to store the size, and return the addess of the
> first byte after the size. You may want to still return aligned pointers
> so you may want to store the size on a smaller alignment.

He's complaining about having to use a 4 byte bitmap for every 8KB (1 bit
per 256 bytes).

Your way might need 4 bytes for every 256 bytes! And could introduce
alignment issues (260 bytes per block also sound as a bit awkward).

--
bartc

[Pascal J. Bourguignon]

You cut it too soon. My proposition has two limbs: use a size prefix for
big blocks, and use blocks of fixed small size allocated from common fixed
size block pools (superblocks).


--
__Pascal J. Bourguignon__