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

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

Power of two bucket allocator

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

Contents

  Power of two bucket allocator vandys@vsta.org - 2012-08-02 20:22 +0000
    Re: Power of two bucket allocator anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-03 14:55 +0000
      Re: Power of two bucket allocator vandys@vsta.org - 2012-08-03 15:35 +0000
        Re: Power of two bucket allocator Alex McDonald <blog@rivadpm.com> - 2012-08-03 08:44 -0700
          Re: Power of two bucket allocator vandys@vsta.org - 2012-08-03 16:07 +0000
        Re: Power of two bucket allocator anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-03 15:45 +0000
      Re: Power of two bucket allocator vandys@vsta.org - 2012-08-03 15:40 +0000

#14669 — Power of two bucket allocator

Here's the power-of-two bucket allocator I use(d) in ForthOS.
The idea is the classic heap grows upward from base of free
memory, and the memory for this allocator grows downward from
the top of the free memory.  By rounding to powers of two, it
greatly reduces fragmentation.

The source lives in a block filesystem (4k blocks), I've posted
the source followed by its shadow screen.

\ Power-of-two bucket memory allocator                               vandys
20 dup dup constant (#BKS)   ( #bks #bks )
32 dup constant (BKMINSZ)   ( #bks #bks bkmin )
    swap lshift constant (BKMAXSZ)
create (bks)   ( #bks ) cells allot
variable (bkheap)   variable (bkheapStart)
: (bkallot) ( u -- a )   negate (bkheap) +!   (bkheap) @ ;
: empty-bks ( -- )   (bks)   (#BKS) cells erase
   (bkheapStart) @ (bkheap) ! ;
: (>bk) ( u -- bkptr u' )   >r (bks) (BKMINSZ) begin
   r@ over >   while   2* swap cell+ swap   repeat   r> drop ;
: bkalloc ( u -- ptr )   cell+ dup (BKMAXSZ) >= abort" Too big"
   (>bk)   over @ ?dup if ( bk u mem )
      nip tuck @ ( mem bk next )   swap !   exit then
   ( bk u )   (bkallot) ( bk mem )   tuck !   cell+ ;
: bkfree ( ptr -- )   ?dup 0= if exit then
   dup (bkheap) @ u< abort" Bad bkfree ptr"
   dup cell- @ ( ptr bk )
   dup @ ( ptr bk oldhead )   rot tuck ! ( bk ptr )   swap ! ;


Maximum number of buckets
Smallest bucket size
 Maximum allocation size
Buckets, one word for allocation chain off each bucket size
Memory is carved from here, downward
: (bkallot) Carve some memory from our bucket heap
: empty-bks Empty out contents of buckets (if any)

: (>bk) Convert size to bucket pointer and size of that bucket

: bkalloc Allocate memory



: bkfree Free previously allocated memory





\ Power-of-two bucket based memory allocator                         vandys
: (bk>size) ( bk -- u )   (bks) -   1 cells /
   (BKMINSZ) swap lshift cell- ;
: bkrealloc ( ptr u -- ptr' )   over 0= if   nip bkalloc exit   then
   over cell- @ (bk>size)   2dup <= if
      2drop exit   then   ( old newsize oldsize )
   over bkalloc -rot min   ( old new size )
   >r 2dup r> move   swap bkfree ;
: bkzalloc ( u -- ptr )   dup bkalloc   tuck swap erase ;


: (bk>size) Turn bucket pointer into its storage size

: bkrealloc Resize memory storage, possibly returning new location
      New size fits in old allocation
   Calculate how much of old to copy to new
   Move to new memory, free old memory, return new memory pointer
: bkzalloc Return memory initialized to zeroes


Notes on implementation: free memory is chained off the bucket
pointer header under (bks).  The slot in (bks) points at the 2nd word
of the memory block; the first word points at the bucket header, and
the 2nd is a next pointer for the chain of free elements under this
bucket.  What this means is that a memory element taken off the bucket
is already set up with its state so it can be freed back to this
bucket.                                                                        


--
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

[toc] | [next] | [standalone]

#14689

vandys@vsta.org writes:
>
>Here's the power-of-two bucket allocator I use(d) in ForthOS.
>The idea is the classic heap grows upward from base of free
>memory, and the memory for this allocator grows downward from
>the top of the free memory.  By rounding to powers of two, it
>greatly reduces fragmentation.

It greatly increases internal fragmentation.

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

#14690

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> It greatly increases internal fragmentation.

I'm not familiar with the term?

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

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

#14693

On Aug 3, 4:35 pm, van...@vsta.org wrote:
> Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
> > It greatly increases internal fragmentation.
>
> I'm not familiar with the term?

The allocated but unused and unusable space in the returned bucket.
Think Swiss cheese; most of it is holes.

>
> --
> Andy Valencia
> Home page:http://www.vsta.org/andy/
> To contact me:http://www.vsta.org/contact/andy.html

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

#14696

Alex McDonald <blog@rivadpm.com> wrote:
>> I'm not familiar with the term?
> The allocated but unused and unusable space in the returned bucket.
> Think Swiss cheese; most of it is holes.

I see.  Powers of two allocated out of page quanta really bound this in
practice--McKusick's experience has been born out in my experience, both in
actual UNIX kernels (HP-UX, PTX) as well as in ForthOS.  Of course, the
resource efficiency of Forth (and ForthOS) intersecting with modern bounty of
RAM means it's easy to have "plenty".

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

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

#14694

vandys@vsta.org writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> It greatly increases internal fragmentation.
>
>I'm not familiar with the term?

<http://en.wikipedia.org/wiki/Fragmentation_(computing)#Internal_fragmentation>

It's the memory wasted for each allocation, in particular because more
memory is allocated than is requested.

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

#14692

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> It greatly increases internal fragmentation.

BTW, this paper was my starting point, although I haven't (yet) added the
virtual memory aspects:

    http://docs.freebsd.org/44doc/papers/kernmalloc.pdf

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

[toc] | [prev] | [standalone]

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

csiph-web