Re: Buddy System Memory Allocator

From	"Mark" <mark@dibsco.co.uk>
Newsgroups	comp.lang.forth
References	<yZzls.238791$it2.2729@fx22.am4> <60a11b41-caa8-42b8-a7ef-2e911f1955c1@n2g2000pbp.googlegroups.com>
Subject	Re: Buddy System Memory Allocator
Message-ID	<Orrns.212175$g62.198969@fx06.am4> (permalink)
Date	2012-11-10 12:05 +0000

Show all headers | View raw

"Hugh Aguilar"  wrote in message 
news:60a11b41-caa8-42b8-a7ef-2e911f1955c1@n2g2000pbp.googlegroups.com...

>On Nov 4, 1:11 pm, "Mark" <m...@dibsco.co.uk> wrote:
>> 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've never heard of a "buddy system" memory allocator. Can you provide
>any links to discussions of this?

Here are a few of the articles that I have looked at:

http://en.wikipedia.org/wiki/Buddy_memory_allocation
http://www.memorymanagement.org/articles/alloc.html
https://umdrive.memphis.edu/blstuart/htdocs/excerpt3.pdf
http://courses.engr.illinois.edu/cs241/sp2012/lectures/09-malloc.pdf
http://ssw.jku.at/Misc/SSW/01.MemoryManagement.pdf

>
>> 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.
>
>This seems pretty straight-forward. When you want to allocate some
>memory, you find the smallest (or maybe the largest) block that will
>work, and use that. Whatever is left over gets moved to the
>appropriate list.

Buddy systems work with blocks that are powers of two in size. All I need to 
do to allocate N bytes is to round N up to the next nearest power of two and 
look in the free list for that size. If there are no free blocks of that 
size, you look at the next block size up and split it in half and so on.

>
>I wouldn't use a minimum of 1 byte as that is a waste of memory
>considering that the link field is one word in size. Also, a lot of
>processors have a "paragraph" that can be worked with efficiently. On
>the 16-bit x86 it is 16 bytes. On most micro-controllers (including
>the MSP-430 which I presume you are working on) it is 1 word.

You are right, a 1 byte block size would be a little wasteful. I was merely 
trying to show the flexible range of block sizes that you can have with 32 
free lists.

>
>On a processor with data caching, I would use trees rather than lists,
>and sort them by their address. If you always prefer the lowest (or
>the highest) address, your blocks will tend to be close together. This
>might help somewhat in that if you are accessing several blocks at the
>same time, all of them might be close enough together to be in the
>cache together.
>
>Be sure to provide support for my ALLOCATION word! That is a huge help
>to the user. See my novice package for more on this. Also, read this
>article:
>http://www.forth.org/novice.pdf
>
>> 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.
>
>Why do you want to track allocated blocks??? The only reason would be
>for GC, but that is very un-Forth-like. You really don't have a good
>way to track what blocks are still in use (neither a reference count
>nor yet searching through the allocated blocks for any that aren't
>referenced), as Forth doesn't distinguish pointers in any way --- they
>are just a value on the stack, and they can't be distinguished from
>integers.
>
>I wouldn't mess with tracking allocated blocks at all --- just leave
>it up to the user to deallocate memory blocks when they are no longer
>in use.

I need to track allocated blocks so that I know how much memory to free and 
which buddies to merge if any.

When the user calls a 'free' word with a single address of the allocated 
region, the memory allocator needs to know how big the memory block is so 
that it can return the correct amount of memory to the free list(s). With a 
buddy system the memory allocator also needs to calculate the address of the 
memory block's buddy so that the two blocks can be merged if necessary. You 
need to know the size of the block so that you can work out where the buddy 
block starts.

>
>For debugging purposes, it might be useful to have a word that
>determines if any memory is allocated, or if everything is free (but
>doesn't tell you when or where the memory got allocated). Sometimes,
>at certain points in your program, you know that everything should be
>free. If anything isn't, then there must be a leak somewhere. For
>example, in a micro-controller you might have a paced-loop. Some tasks
>will be spread out over several iterations of the loop, and they will
>hold data in the heap while they are active. You can determine,
>however, if nothing is active, at which time you can do your check.

I agree that some debugging words would be useful. They'll probably come 
from debugging words written as part of the development process.

>You don't have to track the allocated blocks at all --- just traverse
>all of your free nodes and build a sorted list of allocated blocks ---
>that is somewhat slow, but it is just for debugging purposes and it
>can be removed from the production release of the program so the micro-
>controller doesn't have any awkward moments when it freezes up.
>
>Because Straight Forth will support ALLOCATION (which Forth-200x
>won't), I will need to write my own heap. I'll definitely be
>interested in seeing what you come up with, and perhaps incorporating
>it directly into Straight Forth. :-) I don't know enough about the
>subject right now to dive into it, not without some research first.

I am going to be writing the allocator in ARM assembler, but I'm sure that I 
could back-port the algorithm to Forth if others would find it useful.

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