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" From: "Mark" 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> 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 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