Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2343

Buddy System Memory Allocator

Show all headers | View raw

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 

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-10-13 17:32 +0100
  Re: Buddy System Memory Allocator "BartC" <bc@freeuk.com> - 2012-10-14 16:33 +0100
  Re: Buddy System Memory Allocator Pascal J. Bourguignon <pjb@informatimago.com> - 2012-10-19 12:24 +0000
    Re: Buddy System Memory Allocator "BartC" <bc@freeuk.com> - 2012-10-19 15:04 +0100
      Re: Buddy System Memory Allocator Pascal J. Bourguignon <pjb@informatimago.com> - 2012-10-19 16:37 +0000

csiph-web