Re: [OT] 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>
Subject	Re: [OT] Buddy System Memory Allocator
Message-ID	<WWpms.216705$Tf3.28710@fx12.am4> (permalink)
Date	2012-11-07 09:34 +0000

Show all headers | View raw

"Rod Pemberton"  wrote in message news:k792o8$c4l$1@speranza.aioe.org...

>"Mark" <mark@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.

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