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

Groups > comp.lang.forth > #14669

Power of two bucket allocator

Show all headers | View raw

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

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web