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 3 of 3 — ← Prev page 1 2 [3]

#17203 — Re: Buddy System Memory Allocator

"Paul Rubin" <no.email@nospam.invalid> wrote in message
news:7xpq3njgwp.fsf@ruckus.brouhaha.com...
> "Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
...

> > At some point, an OS developer coding in a HLL (high-level language)
> > will likely create their own compiler, or attempt to bootstrap an
> > existing compiler.  The more complicated the compiler, the less likely
> > it is that they'll succeed.
>
> I don't understand this.  I don't see why someone writing an OS would
> write their own compiler, under normal circumstances.  If they were
> writing a general purpose OS then of course they'd have to target a
> toolchain to it (probably more about the linker etc. than the compiler
> proper).
>

Well, I started my OS using existing C compilers, none of which have ever
been used to produce an OS.  At first, development was very fast.  I didn't
have to create my own toolchain.  I didn't have to code in "primitive"
assembly.  However, C compilers are not completely independent of the
environment they were coded for.  Much of the C language is and many parts
of the C library can be.  But, there are still many things in the toolchain
that produce environment specific code, e.g., code for interrupts.  You
can't get around it, without rewriting the toolchain you're using.  Of
course, the toolchain is so large and complex, you're not going to waste
time doing that.  You just have to handle the problems such environment
specific code creates.  So, eventually, you become frustrated with the lack
of control.  Next, you find bugs in the compiler or library, which you have
to code around too.  Finally, you come to the conclusion that you should've
developed your own simple toolchain first, because you can't control
everything you need to control for your OS without total control of the
toolchain.

> > For my OS project, I really don't even want C.
>
> I thought you were writing a Forth.  You're writing an OS too?
>

Yes, I have an in-progress Forth interpreter.  Yes, I have an stalled OS
project too.  Also, x86 assembler, x86 interpreter, a bunch of different
attempts at C parsers and/or lexers, and C compilers, a simple C-like
programming language, etc.  None are entirely complete.  I have too many
projects for my time.

The OS project stalled after coming across two problems: computer with
needed IDE hardware died, and the "lack of control" toolchain problem above.

> > I want a very small C subset.  Technically, even that is a bit more
> > than I really want.  If assemblers could manage variables like C, I'd
> > probably use an assembler.
>
> Why not use the Forth you're writing?
>

I can't not offend Forth users by replying honestly to that.

Basically, I have yet to see Forth as being an effective language.
Although, I've only coded various Forth dictionary words so far.  However,
there are a few things I find negative or detrimental about Forth.  C or
PL/1 are far more powerful and effective than any other languages from what
I've seen.  C and Forth are noteworthy in that they are far more widespread
than other languages because of their minimal, simple machine models.
Pascal, Fortran, BASIC, etc just aren't that useful, i.e., generally
high-level, but no low-level, or other problematic features.

I'd also need a Forth compiler, not a Forth interpreter.  That would be
another project...  Generating code, even for very simple languages, is far
more complicated than creating address-lists used by DTC and ITC.


Rod Pemberton

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

#17204 — Re: Buddy System Memory Allocator

"Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
> C compilers are not completely independent of the environment they
> were coded for... there are still many things in the toolchain that
> produce environment specific code, e.g., code for interrupts. 

Right, you write an interrupt vector in assembler and have the
interrupts call a trampoline that calls a C function.  So you have to
know the calling conventions, and in the case of a few interrupts
needing very fast response, you might have to code the handler in
assembler, but the amount of asm code involved is generally pretty
small.

> Finally, you come to the conclusion that you should've developed your
> own simple toolchain first, because you can't control everything you
> need to control for your OS without total control of the toolchain.

Sounds like you are reinventing Forth ;-).  In practice other people
manage to use existing toolchains.

>> > For my OS project, I really don't even want C.

What kind of hardware is it for, if I may ask?

> I'd also need a Forth compiler, not a Forth interpreter.  That would be
> another project...  Generating code, even for very simple languages, is far
> more complicated than creating address-lists used by DTC and ITC.

It's true that compilers are more complicated.  I wonder how much time
is spent in OS functions on today's computers, though.  Writing the OS
in threaded Forth with a few asm words for critical loops is a
time-tested approach.  Traditional Forths are very well integrated with
assemblers, normally also written in Forth.

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

#17210 — Re: Buddy System Memory Allocator

"Paul Rubin" <no.email@nospam.invalid> wrote in message
news:7xpq3mdvi0.fsf@ruckus.brouhaha.com...
> "Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
...

> What kind of hardware is it for, if I may ask?
>

x86 PC


Rod Pemberton

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

#17205 — Re: Buddy System Memory Allocator

On 11/9/12 2:10 PM, Rod Pemberton wrote:
...
>
> Well, I started my OS using existing C compilers, none of which have ever
> been used to produce an OS.  At first, development was very fast.  I didn't
> have to create my own toolchain.  I didn't have to code in "primitive"
> assembly.  However, C compilers are not completely independent of the
> environment they were coded for.  Much of the C language is and many parts
> of the C library can be.  But, there are still many things in the toolchain
> that produce environment specific code, e.g., code for interrupts.  You
> can't get around it, without rewriting the toolchain you're using.  Of
> course, the toolchain is so large and complex, you're not going to waste
> time doing that.  You just have to handle the problems such environment
> specific code creates.  So, eventually, you become frustrated with the lack
> of control.  Next, you find bugs in the compiler or library, which you have
> to code around too.  Finally, you come to the conclusion that you should've
> developed your own simple toolchain first, because you can't control
> everything you need to control for your OS without total control of the
> toolchain.

Love it. This is exactly, precisely why Chuck invented Forth in the 
first place!

...
>> Why not use the Forth you're writing?
>>
>
> I can't not offend Forth users by replying honestly to that.
>
> Basically, I have yet to see Forth as being an effective language.
> Although, I've only coded various Forth dictionary words so far.  However,
> there are a few things I find negative or detrimental about Forth.  C or
> PL/1 are far more powerful and effective than any other languages from what
> I've seen.  C and Forth are noteworthy in that they are far more widespread
> than other languages because of their minimal, simple machine models.
> Pascal, Fortran, BASIC, etc just aren't that useful, i.e., generally
> high-level, but no low-level, or other problematic features.
>
> I'd also need a Forth compiler, not a Forth interpreter.  That would be
> another project...  Generating code, even for very simple languages, is far
> more complicated than creating address-lists used by DTC and ITC.

Yet another occasion to point out that you really should learn to 
program in Forth.... Those of us who do it regularly find it *more* 
powerful than C or PL/1, not less. And quite a few of us worked 
successfully for years on Forth OSs based on an ITC model (though one 
designed for efficiency with assembler primitives).

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]

#17207 — Re: Buddy System Memory Allocator

On Nov 10, 3:51 am, "Elizabeth D. Rather" <erat...@forth.com> wrote:
> On 11/9/12 2:10 PM, Rod Pemberton wrote:
> ...
>
>
>
>
>
>
>
>
>
>
>
> > Well, I started my OS using existing C compilers, none of which have ever
> > been used to produce an OS.  At first, development was very fast.  I didn't
> > have to create my own toolchain.  I didn't have to code in "primitive"
> > assembly.  However, C compilers are not completely independent of the
> > environment they were coded for.  Much of the C language is and many parts
> > of the C library can be.  But, there are still many things in the toolchain
> > that produce environment specific code, e.g., code for interrupts.  You
> > can't get around it, without rewriting the toolchain you're using.  Of
> > course, the toolchain is so large and complex, you're not going to waste
> > time doing that.  You just have to handle the problems such environment
> > specific code creates.  So, eventually, you become frustrated with the lack
> > of control.  Next, you find bugs in the compiler or library, which you have
> > to code around too.  Finally, you come to the conclusion that you should've
> > developed your own simple toolchain first, because you can't control
> > everything you need to control for your OS without total control of the
> > toolchain.
>
> Love it. This is exactly, precisely why Chuck invented Forth in the
> first place!
>
> ...
>
>
>
>
>
>
>
>
>
> >> Why not use the Forth you're writing?
>
> > I can't not offend Forth users by replying honestly to that.
>
> > Basically, I have yet to see Forth as being an effective language.
> > Although, I've only coded various Forth dictionary words so far.  However,
> > there are a few things I find negative or detrimental about Forth.  C or
> > PL/1 are far more powerful and effective than any other languages from what
> > I've seen.  C and Forth are noteworthy in that they are far more widespread
> > than other languages because of their minimal, simple machine models.
> > Pascal, Fortran, BASIC, etc just aren't that useful, i.e., generally
> > high-level, but no low-level, or other problematic features.
>
> > I'd also need a Forth compiler, not a Forth interpreter.  That would be
> > another project...  Generating code, even for very simple languages, is far
> > more complicated than creating address-lists used by DTC and ITC.
>
> Yet another occasion to point out that you really should learn to
> program in Forth.... Those of us who do it regularly find it *more*
> powerful than C or PL/1, not less. And quite a few of us worked
> successfully for years on Forth OSs based on an ITC model (though one
> designed for efficiency with assembler primitives).
>
> 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 90045http://www.forth.com
>
> "Forth-based products and Services for real-time
> applications since 1973."
> ==================================================

Ah! Sorry - should have read to the end first!

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

#17211 — Re: Buddy System Memory Allocator

"Elizabeth D. Rather" <erather@forth.com> wrote in message
news:BLSdna1LYZfSUgDNnZ2dnUVZ_r2dnZ2d@supernews.com...
> On 11/9/12 2:10 PM, Rod Pemberton wrote:
...

> > [RP's OS experience]
>
> Love it. This is exactly, precisely why Chuck invented Forth in the
> first place!

I recall he developed Forth for control of a radio telescope, and then there
is the apparent frustration he had with programming high-level languages on
memory constrained machines.  Given that scenario, I'm not sure how you see
my experience as being "exactly, precisely why Chuck invented Forth in the
first place!"  I.e., other than "frustration" with some issue or another, I
don't see the similarity.  I'm clearly not frustrated with coding
applications in C, just with the lack of control when coding an OS in C
using C compilers that weren't setup to do so.  Had I used an "appropriate"
C compiler, I might not have ever had those issues.  That was a mistake on
my part, but I chose them because of the environment, not the compiler's
capabilities.


Rod Pemberton

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

#17212 — Re: Buddy System Memory Allocator

On 11/9/12 9:26 PM, Rod Pemberton wrote:
>
> "Elizabeth D. Rather" <erather@forth.com> wrote in message
> news:BLSdna1LYZfSUgDNnZ2dnUVZ_r2dnZ2d@supernews.com...
>> On 11/9/12 2:10 PM, Rod Pemberton wrote:
> ...
>
>>> [RP's OS experience]
>>
>> Love it. This is exactly, precisely why Chuck invented Forth in the
>> first place!
>
> I recall he developed Forth for control of a radio telescope, and then there
> is the apparent frustration he had with programming high-level languages on
> memory constrained machines.  Given that scenario, I'm not sure how you see
> my experience as being "exactly, precisely why Chuck invented Forth in the
> first place!"  I.e., other than "frustration" with some issue or another, I
> don't see the similarity.  I'm clearly not frustrated with coding
> applications in C, just with the lack of control when coding an OS in C
> using C compilers that weren't setup to do so.  Had I used an "appropriate"
> C compiler, I might not have ever had those issues.  That was a mistake on
> my part, but I chose them because of the environment, not the compiler's
> capabilities.

Chuck's frustration wasn't limited to resource-constrained machines. At 
the time he developed Forth he also had virtually unlimited access to an 
IBM mainframe. It was frustration with the *tool chain*: the number of 
different programs (each of which had some sort of language) he had to 
use: OS control language, editor, compiler, assembler, etc. With every 
step it was necessary to move between these different programs, each 
with its own syntax, command set, rules, procedures, limitations, etc. 
And every time he had to move from one of these to another it was a 
break in his concentration on the actual problem he was trying to solve. 
What he wanted was a single, unified environment that he could control, 
and within which he was free to concentrate entirely on the program he 
was trying to write.

Forth was conceived as that single, unified environment incorporating 
its own OS, editor, compiler, assembler, etc., in which all were 
available all the time, with consistent syntax and rules, so that moving 
from one to another was transparent.

Since obviously he wasn't going to be permitted to replace IBM's OS, the 
opportunity presented by dedicated minicomputers was what he needed.

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]

#17206 — Re: Buddy System Memory Allocator

On Nov 10, 12:05 am, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
>
> Well, I started my OS using existing C compilers, none of which have ever
> been used to produce an OS.  At first, development was very fast.  I didn't
> have to create my own toolchain.  I didn't have to code in "primitive"
> assembly.  However, C compilers are not completely independent of the
> environment they were coded for.  Much of the C language is and many parts
> of the C library can be.  But, there are still many things in the toolchain
> that produce environment specific code, e.g., code for interrupts.  You
> can't get around it, without rewriting the toolchain you're using.  Of
> course, the toolchain is so large and complex, you're not going to waste
> time doing that.  You just have to handle the problems such environment
> specific code creates.  So, eventually, you become frustrated with the lack
> of control.  Next, you find bugs in the compiler or library, which you have
> to code around too.  Finally, you come to the conclusion that you should've
> developed your own simple toolchain first, because you can't control
> everything you need to control for your OS without total control of the
> toolchain.
>

You're aware of *why* Forth was invented, right?

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

#17209 — Re: Buddy System Memory Allocator

"Mark Wills" <forthfreak@gmail.com> wrote in message
news:100469c5-bd7b-4936-af56-0f590a985e1b@s12g2000vbw.googlegroups.com...
> On Nov 10, 12:05 am, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
> wrote:
...

> > Well, I started my OS using existing C compilers, none of which have
> > ever been used to produce an OS. At first, development was very fast. I
> > didn't have to create my own toolchain. I didn't have to code in
"primitive"
> > assembly. However, C compilers are not completely independent of the
> > environment they were coded for. Much of the C language is and many
> > parts of the C library can be. But, there are still many things in the
> > toolchain that produce environment specific code, e.g., code for
interrupts.
> > You can't get around it, without rewriting the toolchain you're using.
Of
> > course, the toolchain is so large and complex, you're not going to waste
> > time doing that. You just have to handle the problems such environment
> > specific code creates. So, eventually, you become frustrated with the
> > lack of control. Next, you find bugs in the compiler or library, which
you
> > have to code around too. Finally, you come to the conclusion that you
> > should've developed your own simple toolchain first, because you can't
> > control everything you need to control for your OS without total control
> > of the toolchain.
> >
>
> You're aware of *why* Forth was invented, right?

For interactive control of a radio telescope, or because CM was frustrated
with high-level languages on now ancient, memory constrained, machines.


RP

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

#17208 — Re: Buddy System Memory Allocator

> > > I want a very small C subset.  Technically, even that is a bit more
> > > than I really want.  If assemblers could manage variables like C, I'd
> > > probably use an assembler.

Well, just write your OS in assembler. Forth can be your entire tool-
chain.

My own Forth system has a TMS9900 assembler, written in Forth. It's
the most powerful assembler I've ever used, not because I wrote it or
there's anything particularly special about it, but because Forth is
available to you, even at the assembly language level. It's difficult
to describe until you have tried it and experienced it. Also, having
things like IF...THEN...ELSE and BEGIN...UNTIL etc. at the assembly
language level is lovely.

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

#17142 — Re: Buddy System Memory Allocator

On Nov 8, 12:57 am, Paul Rubin <no.em...@nospam.invalid> wrote:
> "Rod Pemberton" <do_not_h...@notemailnotz.cnm> writes:
> >> 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 "automagically" done for you in C too....
> > malloc() and free() ...
>
> I think "automagically" in HLL's these days means "garbage collected".
>
> I get the impression that in C++11, smart pointers (i.e. reference
> counted) are included in the standard library and generally considered
> preferable to manual allocation with new and delete (equivalent to
> malloc/free).

Correct. In .Net the garbage collector is actually a global-scoped
object that you can send messages to.

Can't remember the Java paradigm. IIRC Java's garbage collector is
fairly invisible and operates only behind the scenes. Correct me if
I'm wrong.

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

#17216 — Re: Buddy System Memory Allocator

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

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

#17113

I don't have a buddy allocator, but if you want to look at my version 
of a best fit, sorted by size of block allocator, based on a simple 
double linked freelist have a look here:

https://sites.google.com/site/chrishinsley/

You want the list.f and memory.f files from the Forth.zip.

Hope that gives you some ideas.

Best Regards

Chris

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

#17114

On 2012-11-07 13:10:42 +0000, Chris Hinsley said:

> I don't have a buddy allocator, but if you want to look at my version 
> of a best fit, sorted by size of block allocator, based on a simple 
> double linked freelist have a look here:
> 
> https://sites.google.com/site/chrishinsley/
> 
> You want the list.f and memory.f files from the Forth.zip.
> 
> Hope that gives you some ideas.
> 
> Best Regards
> 
> Chris

Only words that you need from the forth.f file (beyond the standard 
stuff, that your Forth will have anyways) are the structure definition 
words, and the >FIELD word makes use of a special I did in my kernel 
'ADD-IMMED,' which just compiles an immediate add. But you can do that 
instead as:

: >FIELD	\ ( s-addr 'name' -- f-addr )
	' EXECUTE
	?DUP
	IF
		POSTPONE LITERAL
		POSTPONE +
	THEN
; IMMEDIATE

Regards

Chris

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

#17222

Le dimanche 4 novembre 2012 21:11:10 UTC+1, Mark a écrit :
> 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

Here is a simpler system I have used:

base-memory dictionary-size + value heap-link

: heap  ( size -- addr )
	heap-link swap - 		( addr )
	heap-link over cell-	( addr link addr- ) 
	dup to heap-link ! ;

: release  ( -- )
	heap-link @ to heap-link ;
	
\ NB: release can be automated inside ';' -- then no more necessary


\ ---- SAMPLE TEST ----

: use-mem  ( addr -- )
	314 swap ! ;


: test
	cell heap use-mem
	...
		cell heap use-mem
		...
		release
	...
	release ;

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

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

csiph-web