Changes between Version 4 and Version 5 of Commentary/Rts/Storage


Ignore:
Timestamp:
Sep 12, 2006 2:54:26 PM (8 years ago)
Author:
simonmar
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Rts/Storage

    v4 v5  
    99== The Block Allocator == 
    1010 
    11 Source: [[GhcFile(includes/Block.h)]], [[GhcFile(rts/BlockAlloc.h)]], [[GhcFile(rts/BlockAlloc.c)]]. 
     11Source: [[GhcFile(includes/Block.h)]], [[GhcFile(rts/BlockAlloc.h)]], [[GhcFile(rts/BlockAlloc.c)]], [[GhcFile(rts/MBlock.h)]], [[GhcFile(rts/MBlock.c)]]. 
    1212 
    1313The block allocator is where the storage manager derives much of its flexibilty.  Rather than keep our heap in a single contiguous region of memory, or one contiguous region per generation, we manage linked lists of memory blocks.  Managing contiguous regions is difficult, especially when you want to change the size of some of the areas.  A block-structured storage arrangement has several advantages: 
     
    4242[[Image(sm-block.png)]] 
    4343 
    44 We currently have megablocks of 1Mb in size with blocks of 4k in size, but these sizes are easy to change ([[GhcFile(includes/Constants.h)]]). 
     44We currently have megablocks of 1Mb in size (m = 20) with blocks of 4k in size (k = 12), and these sizes are easy to change  ([[GhcFile(includes/Constants.h)]]).  Block descriptors are currently 32 or 64 bytes depending on the word size (d = 5 or 6). 
    4545 
     46So the block allocator has a little more structure: 
    4647 
     48 * At the bottom, talking to the OS, is the megablock allocator ([[GhcFile(rts/MBlock.c)]], [[GhcFile(rts/MBlock.h)]]). 
     49   It is responsible for delivering megablocks, correctly aligned, to the upper layers.  It is also responsible for 
     50   implementing `HEAP_ALLOCED()`: the predicate that tests whether a pointer points to dynamically allocated memory 
     51   or not.  This is implemented as a simple bitmap lookup on a 32-bit machine, and something more complex on 
     52   64-bit addressed machines.  See [[GhcFile(rts/MBlock.h)]] for details. 
     53   [[br]][[br]] 
     54   Currently, megablocks are never freed back to the OS, except at the end of the program.  This is a potential 
     55   improvement that could be made. 
     56 
     57 * Sitting on top of the megablock allocator is the block layer ([[GhcFile(includes/Block.h)]], [[GhcFile(rts/BlockAlloc.c)]]). 
     58   This layer is responsible for providing: 
     59   * `void *allocGroup(int)` 
     60   * `void freeGroup(void *)` 
     61   These functions allocate and deallocate a block ''group'': a contiguous sequence of blocks (the degenerate, and common, case 
     62   is a single block).  The block allocator is responsible for keeping track of free blocks.  Currently it does this by 
     63   maintaining an ordered (by address) list of free blocks, with contiguous blocks coallesced.  However this is certanly 
     64   not optimal, and has been shown to be a bottleneck in certain cases - improving this allocation scheme would be good. 
    4765 
    4866== The Garbage Collector ==