Re: Buddy System Memory Allocator

From	"Mark" <mark@dibsco.co.uk>
Newsgroups	comp.lang.forth
References	<yZzls.238791$it2.2729@fx22.am4> <k792o8$c4l$1@speranza.aioe.org> <WWpms.216705$Tf3.28710@fx12.am4> <1b12d69b-ae6e-4a1a-821a-1badbb0100ed@k6g2000vbr.googlegroups.com>
Subject	Re: Buddy System Memory Allocator
Message-ID	<ASsns.273327$pg2.92198@fx18.am4> (permalink)
Date	2012-11-10 13:43 +0000

Show all headers | View raw

"Mark Wills"  wrote in message 
news:1b12d69b-ae6e-4a1a-821a-1badbb0100ed@k6g2000vbr.googlegroups.com...

>On Nov 7, 9:34 am, "Mark" <m...@dibsco.co.uk> wrote:
>> "Rod Pemberton"  wrote in messagenews:k792o8$c4l$1@speranza.aioe.org...
>> >"Mark" <m...@dibsco.co.uk> wrote in message
>> >news:yZzls.238791$it2.2729@fx22.am4...
>> >...
>>
>> >> 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?
>>
>> >This issue affects file systems too.  So, you may wish to think of your
>> >memory allocator as a type of in-memory file-system or read up on how 
>> >file
>> >systems to understand how they solve the problem.
>>
>> Thanks, I'll take a look at the subject.
>>
>>
>>
>> >Bitmaps are good for known and fixed sizes since they're so compact. 
>> >But,
>> >like everything else, they do consume space.  I'm not sure that there is 
>> >an
>> >"easy" solution of a small bitmap with small allocation sizes when being
>> >used to map a large amount of memory.  You're going to need alot of 
>> >bits.
>> >Of course, the total size of system memory depends on how much was
>> >installed
>> >by the user.  This is unlike removable media which is always fixed, or
>> >multiple sizes with one maximum size.  For an embedded system or OS, you
>> >could pick a maximum size of memory for which the code will work, then
>> >calculate backwards for what you need to implement ...  In the future, 
>> >the
>> >code may need to be 'fixed' to handle more memory.
>>
>> I had assumed that I would work with a fixed memory size, number of 
>> blocks
>> etc. as most embedded boards probably ship with a fixed (soldered) amount 
>> of
>> RAM. It is not a problem to have a few '#defines' or equivalent somewhere 
>> to
>> configure these things at build time.
>>
>>
>>
>> >E.g., you're likely familiar with Microsoft's FAT12/16 use FATs (File
>> >Allocation Table) to keep track of files or perhaps Unix's inodes. 
>> >You're
>> >likely unfamiliar with CBM (Commodore Business Machines) filesystem, 
>> >which
>> >used bitmaps.  CBM's PC's (personal computers) like the C64's and Vic 
>> >20's,
>> >used CBM disk drives, such as the 1541, that ran CBM's DOS (Disk 
>> >Operating
>> >System).  CBM's DOS used bitmaps called BAMs (Block Availability Map) to
>> >keep track of allocated sectors.  The linked-list of sectors for the
>> >ordering of a file's sectors was stored in the sectors with the data,
>> >unlike
>> >FATs.  If interested, the D64 format documents 1541's format:
>> >http://ist.uwaterloo.ca/~schepers/formats/D64.TXT
>>
>> Thanks, I'll take a look.
>>
>>
>>
>> >As for memory allocators, there are a few to be found on the internet, 
>> >none
>> >of which are coded in Forth.  They may provide you with some ideas, 
>> >e.g.:
>>
>> >"A Memory Allocator," by Doug Lea
>> >http://g.oswego.edu/dl/html/malloc.html
>>
>> >"The BGET Memory Allocator," by John Walker
>> >http://www.fourmilab.ch/bget/
>>
>> >"Dynamic Storage Allocator," Richard Harter, comp.lang.c, Nov. 11, 1990
>> >http://groups.google.com/group/comp.lang.c/msg/7da27dcbc6e2ace1
>>
>> I've looked at a lot of papers on memory allocators, including your first
>> link above. I had settled on the buddy system approach because it seemed 
>> to
>> offer a good trade-off between speed and fragmentation.- Hide quoted 
>> text -
>>
>> - Show quoted text -
>
>What is the definition of 'buddy' in this context? Are two more
>consecutive memory blocks that are assigned to the same object
>considered to be buddies?

The buddy system memory allocator handles memory blocks that are always 
powers of two in size. A request for N bytes will be rounded up to the next 
power of two. If a block of that size exists, it will be allocated. If it 
doesn't exist, larger blocks will be split into two pieces until a block of 
the correct size exists. Each time a block is split the other half becomes 
it's buddy.

For example, if your total memory (heap) is 64 bytes and you want to 
allocate 12 bytes...

12 is rounded up to 16 bytes. No blocks of 16 bytes exist. The 64 bytes (A) 
are split into two blocks of 32 bytes (B and C are buddies). There are still 
no blocks of 16 bytes. Block B is split into two blocks of 16 bytes (D and E 
are buddies). Block D is allocated.

A: 64 bytes
B: 32 bytes C: 32 bytes
D: 16 bytes E: 16 bytes C: 32 bytes
D: [16 bytes] E: 16 bytes C: 32 bytes

When a block is freed it is merged with it's buddy if it is also free. This 
process is repeated until a block cannot be merged with it's buddy.

Using powers of two makes it easy to locate a block's buddy without having 
to search any lists.

See:
http://en.wikipedia.org/wiki/Buddy_memory_allocation

>
>I've yet to study dynamic memory allocation in any detail, as in my
>assembler and C days we relied on static allocation (which worked
>perfectly) and in my later higher-level language (VB and .Net) it was
>handled automagically. It's a very interesting subject.

There was a time in my life too when the projects that I worked on avoided 
dynamic allocation at all costs.

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