Received: by 10.180.105.198 with SMTP id go6mr2028612wib.2.1352375926084;
        Thu, 08 Nov 2012 03:58:46 -0800 (PST)
MIME-Version: 1.0
From: "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
Newsgroups: comp.lang.forth
Subject: Re: [OT] Buddy System Memory Allocator
Date: Mon, 5 Nov 2012 14:10:56 -0500
Organization: Aioe.org NNTP Server
Lines: 59
Message-ID: <k792o8$c4l$1@speranza.aioe.org>
References: <yZzls.238791$it2.2729@fx22.am4>
NNTP-Posting-Host: CNsg4fVcCsvs3UaOgZtQCw.user.speranza.aioe.org
X-Complaints-To: abuse@aioe.org
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.2001
X-Notice: Filtered by postfilter v. 0.8.2
X-Newsreader: Microsoft Outlook Express 6.00.2800.2001
X-Priority: 3
X-MSMail-Priority: Normal
Path: ha8ni169399wib.1!nntp.google.com!feeder3.cambriumusenet.nl!82.197.223.108.MISMATCH!feeder2.cambriumusenet.nl!feed.tweaknews.nl!209.197.12.242.MISMATCH!nx01.iad01.newshosting.com!newshosting.com!216.196.98.144.MISMATCH!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!news.mccarragher.com!news.grnet.gr!newsfeed.CARNet.hr!aioe.org!.POSTED!not-for-mail
Bytes: 3699

"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.

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.


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


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


Rod Pemberton