Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #17043 > unrolled thread

[OT] Buddy System Memory Allocator

Back to article view | Back to comp.lang.forth

Contents

  [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

Page 1 of 3  [1] 2 3  Next page →

#17043 — [OT] Buddy System Memory Allocator

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 

[toc] | [next] | [standalone]

#17044 — Re: Buddy System Memory Allocator

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?

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

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.

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.

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

[toc] | [prev] | [next] | [standalone]

#17053 — Re: Buddy System Memory Allocator

On Nov 4, 4:05 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> On Nov 4, 1:11 pm, "Mark" <m...@dibsco.co.uk> wrote:
> On most micro-controllers (including
> the MSP-430 which I presume you are working on) it is 1 word.

When I wrote this, I was thinking that you were Mark Wills, our brave
TI afficianado. Now I realize that you are a different Mark.

Can you tell us which Forth system you are working with? Is this for a
homebrew system, or a publicly-available one? Is this for a small 8-
bit or 16-bit micro-controller, or for a big 32-bit processor? What is
your ultimate goal?

[toc] | [prev] | [next] | [standalone]

#17214 — Re: Buddy System Memory Allocator

"Hugh Aguilar"  wrote in message 
news:d77f4ffe-1c80-45d9-8533-3696162237a4@jj5g2000pbc.googlegroups.com...

>On Nov 4, 4:05 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>> On Nov 4, 1:11 pm, "Mark" <m...@dibsco.co.uk> wrote:
>> On most micro-controllers (including
>> the MSP-430 which I presume you are working on) it is 1 word.
>
>When I wrote this, I was thinking that you were Mark Wills, our brave
>TI afficianado. Now I realize that you are a different Mark.

Yes, I am a different Mark.

>
>Can you tell us which Forth system you are working with? Is this for a
>homebrew system, or a publicly-available one? Is this for a small 8-
>bit or 16-bit micro-controller, or for a big 32-bit processor? What is
>your ultimate goal?

This is for my homebrew system. I've been dabbling in Forth for the last 30 
years or so, but never that seriously (former teenage Saturday assistant at 
Skywave Software  http://www.dibsco.co.uk/index.php/skywave-software ).

I decided to teach myself ARM assembler and writing a homebrew Forth system 
seemed like a good way of 'killing two birds with one stone'. I work 
professionally with embedded systems and embedded Linux, so my current 
target system is a Linux-based ARM9 system. I'm not quite sure what my 
ultimate goal is at the moment, although I do have the following current 
goals in mind:

- Full ANS-94 compliant system with all wordsets.
- Small footprint and fast operation (with some loss of portability).
- Flexible build options - inline or common NEXT, Linux or native, threading 
technique etc.

I have been developing and testing on a Linux-based PC using qemu to test my 
code. I just have the core, core extension, double and double extension 
wordsets completed at the moment. I have a number of longer terms goals in 
the back of my mind including:

- native Forth system, i.e. not running under Linux, that could be used for 
embedded control applications or as a board test/diagnostic suite and 
bootloader.
- as a CGI or general purpose scripting language.

Both of these goals come from ideas that would potentially make my 
professional development work a little easier.

[toc] | [prev] | [next] | [standalone]

#17218 — Re: Buddy System Memory Allocator

"Mark" <mark@dibsco.co.uk> wrote in message
news:r7sns.233489$A%.87153@fx26.am4...

> [...] I'm not quite sure what my
> ultimate goal is at the moment, although I do have the following current
> goals in mind:
>
> - Full ANS-94 compliant system with all wordsets.

Why?

My thought process says that there should only be a few ANS Forth systems
with all ANS wordsets implemented, e.g., commercial Forths and
maybe a few hobbyist Forths.  I.e., I think that there will be very few
Forth's that have much more than ANS CORE and CORE EXT implemented.
If my thinking is correct, then Forth code that needs more than just the
CORE and CORE EXT wordsets is likely to be scarce too.  I.e., if you're
going to use Forth code provided by others, you're probably fine without
a full Forth.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#17220 — Re: Buddy System Memory Allocator

Rod Pemberton wrote: <k7muil$93u$1@speranza.aioe.org>
> "Mark" <mark@dibsco.co.uk> wrote in message
> news:r7sns.233489$A%.87153@fx26.am4...
>
>> [...] I'm not quite sure what my
>> ultimate goal is at the moment, although I do have the following current
>> goals in mind:
>>
>> - Full ANS-94 compliant system with all wordsets.
>
> Why?
>
> My thought process says that there should only be a few ANS Forth systems
> with all ANS wordsets implemented, e.g., commercial Forths and
> maybe a few hobbyist Forths.  I.e., I think that there will be very few
> Forth's that have much more than ANS CORE and CORE EXT implemented.
> If my thinking is correct, then Forth code that needs more than just the
> CORE and CORE EXT wordsets is likely to be scarce too.  I.e., if you're
> going to use Forth code provided by others, you're probably fine without
> a full Forth.

I know of *very* few non-trivial Forth programs that use only CORE and
CORE EXT, and I don't think there are *any* Forth systems that provide
only that.  Most of the major Forth systems provide all wordsets, or at
least a most of most of the wordsets, and even toy systems usually
include some things from TOOLS and FILE and STRING.

--Josh

[toc] | [prev] | [next] | [standalone]

#17224 — Re: Buddy System Memory Allocator

Josh Grams wrote:
> I know of *very* few non-trivial Forth programs that use only CORE and
> CORE EXT, and I don't think there are *any* Forth systems that provide
> only that.  Most of the major Forth systems provide all wordsets, or
> at least a most of most of the wordsets, and even toy systems usually
> include some things from TOOLS and FILE and STRING.

Embedded Forth systems usually limit themselves to CORE plus a few 
things you need on these idiosyncratic processors.

I'd say that even the peg solitaire robot I did using the b16 is a "non-
trivial Forth program", and the b16 has just ~30 Forth words as 
instructions.  Far less than CORE.

On the other hand, on a PC or smartphone, I expect my Forth system to 
provide access to system libraries like OpenGL.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#17230 — Re: Buddy System Memory Allocator

Bernd Paysan wrote: <3845103.SMijO1arqN@sunwukong.fritz.box>
> Josh Grams wrote:
>> I know of *very* few non-trivial Forth programs that use only CORE and
>> CORE EXT, and I don't think there are *any* Forth systems that provide
>> only that.  Most of the major Forth systems provide all wordsets, or
>> at least a most of most of the wordsets, and even toy systems usually
>> include some things from TOOLS and FILE and STRING.
>
> Embedded Forth systems usually limit themselves to CORE plus a few 
> things you need on these idiosyncratic processors.
>
> I'd say that even the peg solitaire robot I did using the b16 is a "non-
> trivial Forth program", and the b16 has just ~30 Forth words as 
> instructions.  Far less than CORE.

Yeah, sorry; I was thinking desktop use, not embedded.

--Josh

[toc] | [prev] | [next] | [standalone]

#17225 — Re: Buddy System Memory Allocator

On 11/11/12 1:49 AM, Josh Grams wrote:
> Rod Pemberton wrote: <k7muil$93u$1@speranza.aioe.org>
>> "Mark" <mark@dibsco.co.uk> wrote in message
>> news:r7sns.233489$A%.87153@fx26.am4...
>>
>>> [...] I'm not quite sure what my
>>> ultimate goal is at the moment, although I do have the following current
>>> goals in mind:
>>>
>>> - Full ANS-94 compliant system with all wordsets.
>>
>> Why?
>>
>> My thought process says that there should only be a few ANS Forth systems
>> with all ANS wordsets implemented, e.g., commercial Forths and
>> maybe a few hobbyist Forths.  I.e., I think that there will be very few
>> Forth's that have much more than ANS CORE and CORE EXT implemented.
>> If my thinking is correct, then Forth code that needs more than just the
>> CORE and CORE EXT wordsets is likely to be scarce too.  I.e., if you're
>> going to use Forth code provided by others, you're probably fine without
>> a full Forth.
>
> I know of *very* few non-trivial Forth programs that use only CORE and
> CORE EXT, and I don't think there are *any* Forth systems that provide
> only that.  Most of the major Forth systems provide all wordsets, or at
> least a most of most of the wordsets, and even toy systems usually
> include some things from TOOLS and FILE and STRING.

It really depends on your objectives in developing the system. Some 
people want to write a Forth just for the experience of getting it up 
and running, and don't really plan to use it for applications. Why 
should they feel obligated to include wordsets they don't need? Others 
have specific application (or application domains) in mind, and should 
pick and choose those features and wordsets directly applicable to the 
intended use.

Those of us who are developing systems for general use obviously need to 
cover a broader spectrum of utility, and there's a distribution 
advantage to claiming not only full Standard coverage but also 
additional features (programmer aids, libraries, utilities, etc.), but 
we never forget that Forth is primarily a tool for application 
development and one that we use daily for that purpose.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#17064 — Re: Buddy System Memory Allocator

On Nov 4, 11:05 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> 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?

http://www.cs.purdue.edu/homes/hosking/690M/p421-peterson.pdf. It's
been around for half a century.

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

That sounds like a slab allocator.
http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps

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

See D.E. Knuth. The Art Of Computer Programming, Volume 1: Fundamental
Algorithms, Addison-Wesley, 1973 for an analysis of first fit vs best
fit in buddy systems.

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

A analysis of using binary trees is here; http://csrl.unt.edu/~kavi/Research/southeastcon.pdf.

In this paper we described the use of Binary
Trees for maintaining the available chunks of
memory. The Binary Tree is based on the starting
address of memory chunks. In addition, we keep
track of the sizes of largest blocks of memory in the
left and right sub-trees. This information is used
during allocation to find a suitable chunk of memory.
Our data shows that Best Fit (or Better Fit)
allocation policies can easily be implemented using
the chunk sizes in the left and right sub-trees. The
Binary Tree implementation permits immediate
coalescing of newly freed memory with other free
chunks of memory. Binary Tree naturally improves
the search for appropriate size blocks of memory over
Linear Linked lists.

[snip]

[toc] | [prev] | [next] | [standalone]

#17213 — Re: Buddy System Memory Allocator

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

[toc] | [prev] | [next] | [standalone]

#17259 — Re: Buddy System Memory Allocator

On Nov 10, 5:07 am, "Mark" <m...@dibsco.co.uk> wrote:
> "Hugh Aguilar"  wrote in message
> 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.

Okay, I'm aware of the idea of making all of the allocated blocks a
power-of-2 size. I hadn't known that was called "buddy system." I'll
read up it, starting with those articles that you mentioned.

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

Well, you don't need to keep track of the allocated blocks to do this.
You wouldn't want to anyway, as that would involve searching through a
list or whatever to find it, which is slow.

If you are going to support ALLOCATION (please do!), then you have
killed two birds with one stone. At the front of every allocated block
you have the size of the block (which is a power of two). This tells
you where the buddy is (immediately after it) and how big the buddy
is.

Note that it is okay to store the size of the memory-block (a power-
of-2 in your case) rather than the size that the user requested (which
is <= to what he got). I use ALLOCATION primarily for CLONE-NODE that
clones a node in a list (or a tree or whatever). This needs ALLOCATION
so that it knows how much data to CMOVE from the original node to the
clone. If it moves more than necessary (more than the user originally
requested, but the amount that he actually got) that is okay --- this
would be slightly slower because CMOVE is moving some garbage data at
the tail that it doesn't strictly need to, but the speed difference is
so small as to be meaningless.

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

You may want to look into Menuet. This is an OS written in NASM for
the x86. The 32-bit version is open-source and the 64-bit version does
not come with source-code but is freely available to use. I think
there is an ARM version also, but you would have to ask about this on
the forum:
http://www.menuetos.net/
I'm considering writing a Forth for Menuet --- that would be the first
high-level-language available for Menuet, as those guys normally write
everything in NASM and distain to use HLLs at all. They might use
Forth though, if I present Forth not as an HLL but rather as a wrapper
and a framework for assembly-language code (which is the way that I
thought of Forth in my Commodore-64 days).

Note that Menuet uses an old version of NASM.

[toc] | [prev] | [next] | [standalone]

#17048

"Mark" <mark@dibsco.co.uk> writes:
> 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. 

I wouldn't worry about this.  You'll lose mucm more memory to the
powers-of-two allocation units if the actual requests will be for blocks
of random size.  You're doing pretty good if your allocator's overhead
is a few percent of the total memory.  In a very small system, the
total number of blocks will be small so the bitmap will be small.  In a
larger system, you can afford a few kilobytes for bitmaps.

[toc] | [prev] | [next] | [standalone]

#17050 — Re: Buddy System Memory Allocator

On Nov 4, 5:55 pm, Paul Rubin <no.em...@nospam.invalid> wrote:
> You'll lose mucm more memory to the
> powers-of-two allocation units if the actual requests will be for blocks
> of random size.

They aren't for random sizes. In most applications, most of the
allocations are for records or for strings, both of which tend to be
pretty small (usually < 32 bytes). I don't think the problem of
"internal fragmentation" is very bad practically.

If you are really worried about this, then allow for arbitrary sizes.
Use a binary tree sorted by block size to hold the free blocks. When
allocating, you can search for the smallest block that will work, or
you can just use the largest block available (the rightmost leaf node)
--- either way you have to insert the freed remainder in the tree
afterward --- so you have one or two searches.

You also have two links rather than one for every node, because it is
a tree rather than a list (you could use a sorted list too, but your
searches would be a lot slower). Modern micro-controllers tend to be
faster than necessary, but to still have memory shortages --- so it is
generally more important to save memory than save time ---meaning that
a sorted list might be better than a tree (you are just comparing
integers, so the search is going to be pretty fast even with a list).
If you use a list, and you want to use the biggest block available,
then your list should be sorted backwards (large to small) to give you
easy access to the node of the biggest block.

[toc] | [prev] | [next] | [standalone]

#17106

"Paul Rubin"  wrote in message news:7xvcdkuavu.fsf@ruckus.brouhaha.com...

>"Mark" <mark@dibsco.co.uk> writes:
>> 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.
>
>I wouldn't worry about this.  You'll lose mucm more memory to the
>powers-of-two allocation units if the actual requests will be for blocks
>of random size.  You're doing pretty good if your allocator's overhead
>is a few percent of the total memory.  In a very small system, the
>total number of blocks will be small so the bitmap will be small.  In a
>larger system, you can afford a few kilobytes for bitmaps.

You are right, I guess that in the general scheme of things the bitmaps 
represent a low overhead compared to the internal fragmentation associated 
with the buddy system. It's just that the free list handling seems much more 
elegant/efficient because of the zero overhead associated with keeping the 
list pointers inside the empty blocks along with the fact that only 32 
pointers/lists will cover a huge range of memory. But then I suppose that 
you can't really store data about allocation inside an allocated block. 

[toc] | [prev] | [next] | [standalone]

#17054

On 11/04/2012 10:10 PM, Mark wrote:

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

You keep a bitmap multiple words long, depending on how you've balanced
block size vs available memory.  I did this once for a device-driver on
a no-disk device.

However, I would be carefully weigh alternatives such as preallocating
pools, rather than using the allocate/free model.  You don't say what
sort of application you are envisioning, that would make a difference as
well.

[toc] | [prev] | [next] | [standalone]

#17107

"Ron Aaron"  wrote in message news:k77lkv$g5h$1@dont-email.me...

>On 11/04/2012 10:10 PM, Mark wrote:
>
>> 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.
>
>You keep a bitmap multiple words long, depending on how you've balanced
>block size vs available memory.  I did this once for a device-driver on
>a no-disk device.
>
>However, I would be carefully weigh alternatives such as preallocating
>pools, rather than using the allocate/free model.  You don't say what
>sort of application you are envisioning, that would make a difference as
>well.

Pre-allocating pools? I haven't come across this - only the allocate/free 
model. I am trying to write a general purpose allocator that fulfils the 
requirements of the ANS memory allocation wordset.

[toc] | [prev] | [next] | [standalone]

#17073

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

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

[toc] | [prev] | [next] | [standalone]

#17079 — Re: Buddy System Memory Allocator

On Nov 5, 7:06 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
> "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.

Although that may superficially appear to be the case, file systems
are designed to solve a quite different problem; how do you minimize
file IO, reduce seeks to a minimum and parallelise operations across
many devices to decrease latency and increase bandwidth. Many file
systems are btree or b+tree based as those algorithms match well the
limitations of disks.

Memory allocators that use btrees can be found; http://locklessinc.com/
for example. But their domain is something like MPI (message passing)
where the interface benefits from a btree implementation; and even
this allocator reverts to a slab allocator for small allocations.

The OP needs to state the use case for his allocator.

[snip]

[toc] | [prev] | [next] | [standalone]

#17096 — Re: Buddy System Memory Allocator

"Alex McDonald" <blog@rivadpm.com> wrote in message
news:94819742-bce4-43d3-ae7c-55c553851580@a6g2000vbl.googlegroups.com...
> On Nov 5, 7:06 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
> wrote:
> > "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.
>
> Although that may superficially appear to be the case, [...]

It's not superficial.  It affects old and modern filesystems.  However, it
especially affects older, simple filesystems.

> [...] file systems are designed to solve a quite different problem;
> how do you minimize file IO, [...]

Minimizing the access time of blocks of memory is an issue for a memory
allocator too.

1) If the blocks of memory contain a file as raw sectors from the disk,
e.g., a ramdisk, you've got the same problem in memory as on disk.  You want
those sectors ordered and contiguous.  You don't want them randomly arranged
and distributed all across memory.

2) Many programs allocate and free large quantites of small sized memory
blocks.  After a while, the resulting memory fragmentation results in
various problems for the memory allocator.  Any one or perhaps all of which
can slow the allocator down dramatically.

> [...] reduce seeks to a minimum [...]

This only affects physical hard disks (HD) which have to physically move a
read/write head.  It doesn't affect solid state disks (SDD) which have the
same (near zero) seek time per sector.  For many years now, HDs have come
with cache's for minimizing that problem.  I'm not sure what improvement a
filesystem can offer over a large, fast cache in hardware on the hard disk.
I wouldn't doubt it if modern performance drives automatically moved sectors
around to boost performance, but I don't know if they do...  They do map and
lock out bad tracks.

Also, I'd think you'd want to 'reduce seek time' to a minimum for memory
allocation too, i.e., have good spatial locality.  Without it, it's possible
you could up with situations with unwanting "thrashing", possibly of the
memory allocator code, the microprocessor cache, or the swap space on disk.

> [...] and parallelise operations across many devices
> to decrease latency and increase bandwidth.

That would definately be true for certain RAID configurations, e.g., data
striping.  It'd also be true for multiple devices each with a portion of a
filesystem when mounted into a single filesystem, like for POSIX
environments.  However, some filesystems treat each device as having a
separate filesystem.  And, some hardware doesn't have hardware support
configuring multiple physical drives as one virtual drive.  I.e., this can
be true for more advanced modern hardware.

> The OP needs to state the use case for his allocator.

We're not expecting him to write a specialized allocator or world-class
allocator for Forth are we?  As I understood it, He just wanted something
simple and quick.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.forth

csiph-web