Buddy System Memory Allocator

Path	csiph.com!usenet.pasdenom.info!news.albasani.net!feeder.erje.net!eweka.nl!lightspeed.eweka.nl!69.16.177.246.MISMATCH!cyclone03.ams2.highwinds-media.com!news.highwinds-media.com!voer-me.highwinds-media.com!npeersf03.am4!fx25.am4.POSTED!not-for-mail
Reply-To	"Mark" <mark@dibsco.co.uk>
From	"Mark" <mark@dibsco.co.uk>
Newsgroups	comp.programming
Subject	Buddy System Memory Allocator
Lines	2
MIME-Version	1.0
Content-Type	text/plain; format=flowed; charset="iso-8859-1"; reply-type=original
Content-Transfer-Encoding	7bit
X-Priority	3
X-MSMail-Priority	Normal
Importance	Normal
X-Newsreader	Microsoft Windows Live Mail 15.4.3555.308
X-MimeOLE	Produced By Microsoft MimeOLE V15.4.3555.308
Message-ID	<_Iges.3$jY.2@fx25.am4> (permalink)
NNTP-Posting-Host	83.104.45.51
X-Complaints-To	abuse@demon.net
X-Trace	1350145978 83.104.45.51 (Sat, 13 Oct 2012 16:32:58 UTC)
NNTP-Posting-Date	Sat, 13 Oct 2012 16:32:58 UTC
Date	Sat, 13 Oct 2012 17:32:53 +0100
X-Received-Bytes	2454
Xref	csiph.com comp.programming:2343

Show key headers only | 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