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

Groups > comp.programming > #2343 > unrolled thread

Buddy System Memory Allocator

Back to article view | Back to comp.programming

Contents

  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

#2343 — Buddy System Memory Allocator

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 

[toc] | [next] | [standalone]

#2345

"Mark" <mark@dibsco.co.uk> wrote in message news:_Iges.3$jY.2@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 

[toc] | [prev] | [next] | [standalone]

#2356

"Mark" <mark@dibsco.co.uk> wrote:
> 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.

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__

[toc] | [prev] | [next] | [standalone]

#2358

"Pascal J. Bourguignon" <pjb@informatimago.com> wrote in message 
news:1731845837372288843.910496pjb-informatimago.com@news.individual.net...
> "Mark" <mark@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 

[toc] | [prev] | [next] | [standalone]

#2361

"BartC" <bc@freeuk.com> wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com> wrote in message
> news:1731845837372288843.910496pjb-informatimago.com@news.individual.net...
>> "Mark" <mark@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).

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__

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web