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

#17101 — Re: Buddy System Memory Allocator

On Nov 6, 6:50 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
> "Alex McDonald" <b...@rivadpm.com> wrote in message
> > 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.

Why not write a world-class allocator for Forth? :-) You make it sound
like there is a rule somewhere that Forth software has to suck.

Actually, I think our OP has wandered off. It was pretty exciting
there for a while, as we thought that somebody other than the usual
gang of idiots was going to write some Forth code --- but then nothing
came of it. :-(

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

#17105 — Re: Buddy System Memory Allocator

"Hugh Aguilar"  wrote in message 
news:f6aa048c-66f8-4b54-83ea-79abed66321d@v9g2000pbi.googlegroups.com...

>On Nov 6, 6:50 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
>wrote:
>> "Alex McDonald" <b...@rivadpm.com> wrote in message
>> > 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.
>
>Why not write a world-class allocator for Forth? :-) You make it sound
>like there is a rule somewhere that Forth software has to suck.
>
>Actually, I think our OP has wandered off. It was pretty exciting
>there for a while, as we thought that somebody other than the usual
>gang of idiots was going to write some Forth code --- but then nothing
>came of it. :-(

I haven't wandered off, I've just got very little free time at the moment. 

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

#17131 — Re: Buddy System Memory Allocator

"Hugh Aguilar" <hughaguilar96@yahoo.com> wrote in message
news:f6aa048c-66f8-4b54-83ea-79abed66321d@v9g2000pbi.googlegroups.com...
> On Nov 6, 6:50 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
> wrote:
> > "Alex McDonald" <b...@rivadpm.com> wrote in message
...

> > > 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.
>
> Why not write a world-class allocator for Forth? :-)

Hey, you know what?  You're elected!

> You make it sound like there is a rule somewhere
> that Forth software has to suck.

No, that wasn't intended.  Freudian-slip interpretation?  ;-)

I just thought Marcel (the OP) said he wanted something easy.

Alex seemed to be heading towards a discussion of the full
technical merits of different memory allocators.


Rod Pemberton

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

#17146 — Re: Buddy System Memory Allocator

On Nov 8, 12:45 am, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:

>
> Alex seemed to be heading towards a discussion of the full
> technical merits of different memory allocators.

You keep heading towards filesystems; I'm dragging you back to where
Mark started.

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

#17185 — Re: Buddy System Memory Allocator

On Nov 7, 5:45 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
> "Hugh Aguilar" <hughaguila...@yahoo.com> wrote in message
> > Why not write a world-class allocator for Forth? :-)
>
> Hey, you know what?  You're elected!

Well, I said in my very first response that I don't know enough about
the subject to dive in --- not without some research. I have only a
rudimentary understanding of the subject. I still don't know what this
"buddy" system is.

Eventually I will have to dive in though --- Straight Forth will need
a memory allocator, and it can't use GLIBC because I need to have
ALLOCATION --- this, according to Anton, is why Forth-200x won't have
ALLOCATION (because Forth-200x depends upon GLIBC which doesn't have
ALLOCATION).

I'm definitely interested in seeing what this guy comes up with. If it
works, and it is public-domain, I may just use it in Straight Forth

> I just thought Marcel (the OP) said he wanted something easy.

Marcel? I thought his name was "Mark" (although "Marcel" is the French
equivalent of "Mark"). Do you know more about Mark/Marcel than is
apparent in this thread? This isn't a sock-puppet for Marcel Hendrix
is it?

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

#17198 — Re: Buddy System Memory Allocator

In article <0efea753-0396-4bb0-902c-b47ebd0b4a0c@qi8g2000pbb.googlegroups.com>,
Hugh Aguilar  <hughaguilar96@yahoo.com> wrote:
>On Nov 7, 5:45 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
>wrote:
>> "Hugh Aguilar" <hughaguila...@yahoo.com> wrote in message
>> > Why not write a world-class allocator for Forth? :-)
>>
>> Hey, you know what?  You're elected!
>
>Well, I said in my very first response that I don't know enough about
>the subject to dive in --- not without some research. I have only a
>rudimentary understanding of the subject. I still don't know what this
>"buddy" system is.
>
>Eventually I will have to dive in though --- Straight Forth will need
>a memory allocator, and it can't use GLIBC because I need to have
>ALLOCATION --- this, according to Anton, is why Forth-200x won't have
>ALLOCATION (because Forth-200x depends upon GLIBC which doesn't have
>ALLOCATION).

You can steal the memory words from the ciforth version 5.
It has no ALLOCATION, but it can be trivially added.
(like   DUP 1 CELLS - @ SWAP - or some such).

>
>I'm definitely interested in seeing what this guy comes up with. If it
>works, and it is public-domain, I may just use it in Straight Forth
>
>> I just thought Marcel (the OP) said he wanted something easy.
>
>Marcel? I thought his name was "Mark" (although "Marcel" is the French
>equivalent of "Mark"). Do you know more about Mark/Marcel than is
>apparent in this thread? This isn't a sock-puppet for Marcel Hendrix
>is it?

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#17202 — Re: Buddy System Memory Allocator

Hugh Aguilar wrote:
> Eventually I will have to dive in though --- Straight Forth will need
> a memory allocator, and it can't use GLIBC because I need to have
> ALLOCATION --- this, according to Anton, is why Forth-200x won't have
> ALLOCATION (because Forth-200x depends upon GLIBC which doesn't have
> ALLOCATION).

It doesn't have it as public exported function.  And the argument of 
Anton was that a number of Forth systems don't have their own allocater 
implemented, and therefore would require such an interface.

If you want to rely on "undocumented features" that change whenever 
Ulrich Drepper feels like to change it (and he won't tell you), this is 
ALLOCATION for glibc:

: allocation ( addr -- len )  1 cells - @ 1 cells - 1- ;

You could test if this gives reasonable values, and if not, use a 
wrapper around malloc() and free() that allocates one cell more and 
stores the allocation value in the first cell.

No real need to write your own allocator.

BTW: If you make an RFC, you will create a *discussion*.  Arguments are 
exchanged, and a flame-proof suit is considered minimum requirement for 
starting such a discussion.  You don't have one, so you withdraw your 
proposals after the first round, pretending they were knocked out.

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

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

#17128 — Re: Buddy System Memory Allocator

On Nov 7, 1:50 am, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
> "Alex McDonald" <b...@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.

If I read a fragmented disk file, are you claiming that the memory is
fragmented? No file system I'm aware of does that. They all either
read to buffers under program management, or map to contiguous memory;
for example, mmap over a file.

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

Yes, but that's not a good reason to use a filesystem as a starting
point. It's a quite separate problem, and many memory allocators use
different algorithms to satisfy small requests than those used to
satisfy large requests.

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

SSDs suffer from random write problems; it's called stutter, due to
the fact that SSD pages are managed in large 100s of KB lumps. It is
most apparent when an SSD has been aged; that is, when the SSD has
written to every page at least once. Seeking and writing on SSDs is as
bad as seeking on HDs. No, drives do not move sectors around to
improve performance; it would have the reverse effect. Motto: Never
fix a global problem at the local level.

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

With a very poor allocator, thrashing can be a problem. Page size on
an x86 in 32bit mode is 4K. Expecting an allocator to understand that
a specific request is best satisfied in the same 4K block as some
previous request, because they're referenced by *time* locality, is a
very tough nut to crack. Compacting memory can help, but that implies
garbage collection and some way of modifying pointers. This kind of
activity is best left to the application. If it knows that structure A
is generally followed by a reference to structure B, then allocate
them from a single request for A and B.

In other words, spatial locality is important on disks for fast
reading and writing sequentially, but it's time locality that's
important in random access virtual memory systems.

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

Then a slab allocator would seem to be appropriate. It is relatively
easy to implement and has well understood characteristics, but it is
not like a filesystem.

>
> Rod Pemberton

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

#17215 — Re: Buddy System Memory Allocator

"Alex McDonald"  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, 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.

I am trying to implement a general purpose memory allocator to provide the 
ANS-94 memory allocation wordset features for an embedded ARM Forth. Speed 
and simplicity are the most important factors. The buddy system seems to 
offer this, possibly at the expense of internal fragmentation. I don't want 
to have to spend a lot of time walking through lists and I don't want to 
have any dynamic structures that need to grow or shrink at runtime.

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

#17217 — Re: Buddy System Memory Allocator

On Nov 10, 1:10 pm, "Mark" <m...@dibsco.co.uk> wrote:
> "Alex McDonald"  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, 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.
>
> I am trying to implement a general purpose memory allocator to provide the
> ANS-94 memory allocation wordset features for an embedded ARM Forth. Speed
> and simplicity are the most important factors. The buddy system seems to
> offer this, possibly at the expense of internal fragmentation. I don't want
> to have to spend a lot of time walking through lists and I don't want to
> have any dynamic structures that need to grow or shrink at runtime.

The buddy system is fine as long as you realise that you need to be
able to tell if a buddy is free or allocated when coalescing blocks.
That takes a marker; either something in the buddy itself, or a tree
of pointers to allocations. The marker technique means that you need
something unique in a free block that an allocated block can't
contain. Some memory systems have special tags associated with each
word that can store this information, much like an ECC bit. But most
don't, which means building and handling trees; and they too need to
live somewhere in memory.

A slab allocator can be much simpler and more efficient. For optimal
memory use it requires that you (roughly) know the size and number of
allocations in advance. Running the code and logging allocations and
frees can provide the information you need. Even without making it
tunable or worrying about optimal use, it's still a fairly simple
programming exercise, and by using bitmaps, the memory overhead of
maintaining free & allocated blocks is minimized.

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

#17108

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

>"Mark" <mark@dibsco.co.uk> wrote in message
>news:yZzls.238791$it2.2729@fx22.am4...
>...
>
>> However, I'm not sure about the tracking of allocated blocks. I want a
>> quick and easy way of tracking allocated blocks and buddies using a
>> method that doesn't involve dynamically growing a linked-list or tree
>> at run-time. It seems that this is commonly done using a bitmap, but
>> I don't understand how you keep this manageable if you have a reasonable
>> amount of memory and want a relatively small minimum block size. A
>> bitmap of 32 bits will only give me coverage for 8k of memory if I use
>> a minimum block size of 256 bytes. I am trying to figure out how to
>> avoid having a bitmap that is hundreds or thousands of bits long. Is
>> there any easier or alternative technique?
>
>This issue affects file systems too.  So, you may wish to think of your
>memory allocator as a type of in-memory file-system or read up on how file
>systems to understand how they solve the problem.

Thanks, I'll take a look at the subject.

>
>Bitmaps are good for known and fixed sizes since they're so compact.  But,
>like everything else, they do consume space.  I'm not sure that there is an
>"easy" solution of a small bitmap with small allocation sizes when being
>used to map a large amount of memory.  You're going to need alot of bits.
>Of course, the total size of system memory depends on how much was 
>installed
>by the user.  This is unlike removable media which is always fixed, or
>multiple sizes with one maximum size.  For an embedded system or OS, you
>could pick a maximum size of memory for which the code will work, then
>calculate backwards for what you need to implement ...  In the future, the
>code may need to be 'fixed' to handle more memory.
>

I had assumed that I would work with a fixed memory size, number of blocks 
etc. as most embedded boards probably ship with a fixed (soldered) amount of 
RAM. It is not a problem to have a few '#defines' or equivalent somewhere to 
configure these things at build time.

>
>E.g., you're likely familiar with Microsoft's FAT12/16 use FATs (File
>Allocation Table) to keep track of files or perhaps Unix's inodes.  You're
>likely unfamiliar with CBM (Commodore Business Machines) filesystem, which
>used bitmaps.  CBM's PC's (personal computers) like the C64's and Vic 20's,
>used CBM disk drives, such as the 1541, that ran CBM's DOS (Disk Operating
>System).  CBM's DOS used bitmaps called BAMs (Block Availability Map) to
>keep track of allocated sectors.  The linked-list of sectors for the
>ordering of a file's sectors was stored in the sectors with the data, 
>unlike
>FATs.  If interested, the D64 format documents 1541's format:
>http://ist.uwaterloo.ca/~schepers/formats/D64.TXT
>

Thanks, I'll take a look.

>
>As for memory allocators, there are a few to be found on the internet, none
>of which are coded in Forth.  They may provide you with some ideas, e.g.:
>
>"A Memory Allocator," by Doug Lea
>http://g.oswego.edu/dl/html/malloc.html
>
>"The BGET Memory Allocator," by John Walker
>http://www.fourmilab.ch/bget/
>
>"Dynamic Storage Allocator," Richard Harter, comp.lang.c, Nov. 11, 1990
>http://groups.google.com/group/comp.lang.c/msg/7da27dcbc6e2ace1
>

I've looked at a lot of papers on memory allocators, including your first 
link above. I had settled on the buddy system approach because it seemed to 
offer a good trade-off between speed and fragmentation.

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

#17112 — Re: Buddy System Memory Allocator

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?

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.

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

#17130 — Re: Buddy System Memory Allocator

"Mark Wills" <forthfreak@gmail.com> wrote in message
news:1b12d69b-ae6e-4a1a-821a-1badbb0100ed@k6g2000vbr.googlegroups.com...
...

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

It's "automagically" done for you in C too.  In C, it's hidden behind C
functions.  At some point, these call the host OS' memory allocator.  E.g.,
malloc() and free() are the easiest C functions to notice.  But, the file
I/O functions also use the host OS' memory allocator too.  Technically,
they allocate and free file storage space, but the file I/O is usually
buffered in memory.  Some functions, like tmpfile(), are commonly
implemented in memory only.  So, you can use file I/O functions to do
"memory" allocation in C.  From the programming perspective with C,
it doesn't really matter if the data is in a file or memory.


Rod Pemberton

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

#17134 — Re: Buddy System Memory Allocator

"Rod Pemberton" <do_not_have@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).

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

#17135 — Re: Buddy System Memory Allocator

"Paul Rubin" <no.email@nospam.invalid> wrote in message
news:7xhap0di7e.fsf@ruckus.brouhaha.com...
> "Rod Pemberton" <do_not_have@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".
>

Ah, that'd be a different meaning ...

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

Just how "equivalent" is equivalent?

It's my understanding from what I've read that coding an operating system in
C++ is very difficult, primarily because of new and delete.  It's not
difficult to code an OS in C.  I.e., they are not equivalent.

I'll take it that you mean that new and delete are used in C++ for memory
allocation, whereas malloc and free are used in C for memory allocation.


Rod Pemberton

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

#17136 — Re: Buddy System Memory Allocator

"Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
> It's my understanding from what I've read that coding an operating system in
> C++ is very difficult, primarily because of new and delete.  It's not
> difficult to code an OS in C.  I.e., they are not equivalent.

That makes no sense at all; lots of OS's are coded in C++, and C++ is
almost exactly a superset of C (that is, C programs can be compiled and
run under C++ with very little if any modification).  C++'s new and
delete operators give class instances instead of raw pointers, but in
the case of an OS you probably want some kind of block allocator even
lower level than malloc/free, so the difference between new and malloc
is irrelevant.

> I'll take it that you mean that new and delete are used in C++ for memory
> allocation, whereas malloc and free are used in C for memory allocation.

Yes.  You can still use malloc/free in C++ if you have to, though it
would be considered bad style unless you had a clear reason to do it.

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

#17145 — Re: Buddy System Memory Allocator

Paul Rubin <no.email@nospam.invalid> writes:
>"Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
>> It's my understanding from what I've read that coding an operating system in
>> C++ is very difficult, primarily because of new and delete.  It's not
>> difficult to code an OS in C.  I.e., they are not equivalent.
>
>That makes no sense at all; lots of OS's are coded in C++

Really?  Please name a lot.

>and C++ is
>almost exactly a superset of C (that is, C programs can be compiled and
>run under C++ with very little if any modification).

That may be the view of some "C" compiler maintainers, which may explain
why "C" compilers like to miscompile C programs.

I particular, I remember reading about a discussion of a GNU C
extension that the GCC maintainers did not want to support properly
anymore because it does not combine well with some C++ features.  As a
GNU C programmer, I don't care about C++ and don't see why GNU C
should be maimed because of C++.

>Yes.  You can still use malloc/free in C++ if you have to, though it
>would be considered bad style unless you had a clear reason to do it.

Which shows that C++ is not a superset of C idiomatically, and it's
certainly not a superset formally (e.g., a C++ compiler does not
compile C programs that contain a variable called "this").

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

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

#17187 — Re: Buddy System Memory Allocator

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>That makes no sense at all; lots of OS's are coded in C++
> Really?  Please name a lot.

http://www.google.com/search?q="operating+system+written+in+c%2B%2B"

> Which shows that C++ is not a superset of C idiomatically, and it's
> certainly not a superset formally (e.g., a C++ compiler does not
> compile C programs that contain a variable called "this").

It's never claimed to be a formal superset, just pretty close to one.
You'd have to rename any variable called "this".  There is a list of
further such issues on Stroustrup's web site and they are all pretty
minor iirc.

Of course it's idiomatically different, that's the point.  I'd also say
Forth with files and locals is idiomatically different from Forth with
blocks and stackrobatics.  I'm not exactly a C++ fan and I haven't used
it a whole lot, but in my limited experience it is improves
substantially on C.  Of course I'm not a fan of C either.

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

#17193 — Re: Buddy System Memory Allocator

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

> > It's my understanding from what I've read that coding an operating
> > system in C++ is very difficult, primarily because of new and delete.
> > It's not difficult to code an OS in C.  I.e., they are not equivalent.
>
> That makes no sense at all;

Well, I've read that more than a few times from various sources.  So, I'm
assuming there is some truth to it.  Someone coding an OS (operating system)
in C++ must implement new and delete - custom to their OS.  Perhaps, that's
were the problem is.  Personally, I've got no familiarity with new, delete,
or an OS in C++, so it's possible it's a myth.  But, I can't imagine why
people would intentionally spread such a myth ...  Who opposes using C++
for OS development?  There are enough C++ programmers that I'm sure a few
have tried.

> [...] lots of OS's are coded in C++, [...]

No offense, but I seriously doubt that.  I wouldn't doubt that a few exist
though.

I've seen people attempt OSes in all sorts of languages.  But, I've not come
across a single OS on the Internet coded in C++.  Nor do I recall anyone
posting about using C++ for their OS to alt.os.development.

C and the host's assembly still seem to be the predominant languages that
OSes are coded in.

I wouldn't doubt it that a "C++" OS is mostly coded in C with a bit of
trivial C++ usage, just as many C++ programs aren't actually C++ either but
C masquerading as C++.

I can't imagine an OS developer wanting to deal with additional complexities
within their OS, such as inheritance, object oriented programming,
polymorphism, classes and overloading of C++.  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.
Simplicity is needed initially.  Complexity can be added at a later time.

For my OS project, I really don't even want C.  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.
Today, most are powerful enough that they can handle structures, control
flow, macro's, procedures, etc.  I.e., many are almost HLLs.

> [...] and C++ is almost exactly a superset of C (that is, C programs
> can be compiled and run under C++ with very little if any modification).

Well, I've never coded C++.  AIR (as I recall), C is a subset of C++.  From
what I've seen, "pure" C++ programs appear very different syntactically from
C programs and C treated as C++.  E.g., from Wikipedia's C++ page:
'std::cout << "..."'   AIUI, std class, cout function, i.e., functionally
equivalent to C's printf().  Clearly, that's not a 'superset' of C.  That's
purely C++.  No C programmer recognizes that without being provided an
explanation.  A superset would extend the existing C functionality and
syntax, e.g., printf::file.  A C programmer would recognize printf and might
be able to guess that '::file' makes printf function similar to fprintf.


Rod Pemberton

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

#17195 — Re: Buddy System Memory Allocator

"Rod Pemberton" <do_not_have@notemailnotz.cnm> writes:
> Well, I've read that more than a few times from various sources.  So,
> I'm assuming there is some truth to it.  Someone coding an OS
> (operating system) in C++ must implement new and delete - custom to
> their OS.  Perhaps, that's were the problem is.

new and delete are basically syntax sugar for a typed version of malloc
and free.  The API is here:

  http://en.cppreference.com/w/cpp/memory/new/operator_new

so instead of saying
   p = (struct foo *) malloc(sizeof (struct foo));
you'd say
   p = new foo;  

The default action of "new" is to call a malloc-like library routine but
you can override it to call some code of your own, and (it occurs to me)
this might be a reasonable way to handle something like kernel buffers
in linux.  

> Who opposes using C++ for OS development?  There are enough C++
> programmers that I'm sure a few have tried.

Haiku (successor to BeOS) and Symbian were written in C++; Haiku is
trendy in a certain crowd and Symbian was highly successful for a long
time (though now pretty much crushed under the Android/iOS juggernaut).
According to Wikipedia, MacOS now contains some C++ though I don't know
specifics.

>> [...] lots of OS's are coded in C++, [...]
> No offense, but I seriously doubt that.  I wouldn't doubt that a few
> exist though.
Try a web search.  Lots are there that are not very famous.

> C and the host's assembly still seem to be the predominant languages that
> OSes are coded in.

There has to be a little bit of low-level asm in any OS, but if the OS
is more than a toy, for the past 30 years it's (almost) always written
predominantly in a HLL.  As with compilers, for projects started before
the 1990's, a lot of the time the HLL was C.  The OS's that we've heard
of (Linux, BSD, etc.) are all quite old so they fit that pattern.  

> I can't imagine an OS developer wanting to deal with additional
> complexities within their OS, such as inheritance, object oriented
> programming, polymorphism, classes and overloading of C++.

http://okmij.org/ftp/cpp-digest/toy_OS.txt

And anyway, OS's in C usually have dispatch tables for device drivers
etc. that amount to manually implemented OOP.

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

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

I thought you were writing a Forth.  You're writing an OS too?

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

> Well, I've never coded C++.  AIR (as I recall), C is a subset of C++.  

Pretty much so.  There are some minor deviations, like some more
keywords, so in C++ you possibly can't have a variable called "new".

> From what I've seen, "pure" C++ programs appear very different
> syntactically from C programs and C treated as C++.  E.g., from
> Wikipedia's C++ page: 'std::cout << "..."'  AIUI, std class, cout
> function, i.e., functionally equivalent to C's printf().  

cout is like stdout.  << is operator overloading, so cout << x is the
equivalent of something like fwrite(stdout,x).  It's specialized on
various datatypes so if cout << n (for an int n) prints n in decimal,
while cout << s (for string s) prints s directly, etc.  

If you write a new class, you can specify what << is supposed to do with
it, so it's better than printf in the sense that you can extend it easily.
It's uglier and clumsier in some other ways.  You can still use printf if
you want, and I sometimes do that.

> Clearly, that's not a 'superset' of C.  That's purely C++.  No C
> programmer recognizes that without being provided an explanation.

Of course it's a (near) superset.  It's just like today if you want to
go somewhere, you can walk, drive, take a taxi, buy a plane ticket, ride
a horse, etc.; while if you lived in the 18th century your choices would
have been walk or horse.  We would say your options today are a superset
of the 18th century options.  That doesn't mean an 18th century person
would understand airplanes without an explanation, and it doesn't mean
that the choices an 18th century person would have made are sensible
choices now (riding a horse in a town where cars are available would
usually be silly).  But they're still available if that's what a given
situation calls for.

> A superset would extend the existing C functionality and syntax, e.g.,
> printf::file.  A C programmer would recognize printf and might be able
> to guess that '::file' makes printf function similar to fprintf.

It's not like that--using it idiomatically really has a completely
different feeling than writing in C.  It's actually pretty easy to get
used to though; it's "well-worn" if that makes any sense.  I mean
something like: the people who designed it had clearly written a lot of
C code and the stuff that went into C++ was all invented to solve real
problems.

At least for 21st century PC-class computers (that would include things
like smartphones, which are equivalent to PC's of the early 2000's) I just
don't see much point of writing anything in pure C.  You do get code bloat
if you use idiomatic C++ and its template library, but you gain
convenience, and with some care you can avoid taking any performance hit.

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

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

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

csiph-web