[OT] Buddy System Memory Allocator

From	"Mark" <mark@dibsco.co.uk>
Newsgroups	comp.lang.forth
Subject	[OT] Buddy System Memory Allocator
Message-ID	<yZzls.238791$it2.2729@fx22.am4> (permalink)
Date	2012-11-04 20:10 +0000

Show all headers | View raw

Hello

I am looking at writing a buddy system memory allocator in assembler for a 
Forth system.

I 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. Is there any easier or alternative technique? I also 
imagine that I need a method of tracking the sizes of the allocated blocks 
(in addition to the bitmap) so that a 'free' knows how many bytes to 
de-allocate.

Any help would be much appreciated.

Thanks

Mark

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

Thread

[OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-04 20:10 +0000
  Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 15:05 -0800
    Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 22:02 -0800
      Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 12:53 +0000
        Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 20:25 -0500
          Re: Buddy System Memory Allocator Josh Grams <josh@qualdan.com> - 2012-11-11 11:49 +0000
            Re: Buddy System Memory Allocator Bernd Paysan <bernd.paysan@gmx.de> - 2012-11-11 17:43 +0100
              Re: Buddy System Memory Allocator Josh Grams <josh@qualdan.com> - 2012-11-12 01:55 +0000
            Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-11 07:06 -1000
    Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-05 06:33 -0800
    Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 12:05 +0000
      Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-13 19:49 -0800
  Re: [OT] Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-04 16:55 -0800
    Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-04 19:08 -0800
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 08:49 +0000
  Re: [OT] Buddy System Memory Allocator Ron Aaron <rambamist@gmail.com> - 2012-11-05 08:17 +0200
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 09:02 +0000
  Re: [OT] Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-05 14:10 -0500
    Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-05 12:58 -0800
      Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-06 20:54 -0500
        Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-06 21:50 -0800
          Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 08:36 +0000
          Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 19:49 -0500
            Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-08 04:42 -0800
            Re: Buddy System Memory Allocator Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-11-08 19:43 -0800
              Re: Buddy System Memory Allocator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2012-11-09 10:48 +0000
              Re: Buddy System Memory Allocator Bernd Paysan <bernd.paysan@gmx.de> - 2012-11-09 22:15 +0100
        Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-07 12:46 -0800
      Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 13:09 +0000
        Re: Buddy System Memory Allocator Alex McDonald <blog@rivadpm.com> - 2012-11-10 07:43 -0800
    Re: [OT] Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-07 09:34 +0000
      Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-07 04:07 -0800
        Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 19:44 -0500
          Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-07 16:57 -0800
            Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-07 20:14 -0500
              Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-07 17:32 -0800
                Re: Buddy System Memory Allocator anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-11-08 12:32 +0000
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-08 20:00 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-09 02:20 -0500
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-09 00:53 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-09 19:10 -0500
                Re: Buddy System Memory Allocator Paul Rubin <no.email@nospam.invalid> - 2012-11-09 18:47 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:16 -0500
                Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-09 17:51 -1000
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:51 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:26 -0500
                Re: Buddy System Memory Allocator "Elizabeth D. Rather" <erather@forth.com> - 2012-11-09 22:01 -1000
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:49 -0800
                Re: Buddy System Memory Allocator "Rod Pemberton" <do_not_have@notemailnotz.cnm> - 2012-11-10 02:15 -0500
                Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-09 22:57 -0800
            Re: Buddy System Memory Allocator Mark Wills <forthfreak@gmail.com> - 2012-11-08 00:22 -0800
        Re: Buddy System Memory Allocator "Mark" <mark@dibsco.co.uk> - 2012-11-10 13:43 +0000
  Re: [OT] Buddy System Memory Allocator Chris Hinsley <chris.hinsley@gmail.com> - 2012-11-07 13:10 +0000
    Re: [OT] Buddy System Memory Allocator Chris Hinsley <chris.hinsley@gmail.com> - 2012-11-07 13:31 +0000
  Re: [OT] Buddy System Memory Allocator Charles Mélice <charles.melice@gmail.com> - 2012-11-11 05:29 -0800

csiph-web