gc/cell.d

   1 /**
   2  * Memory Cell header manipulation.
   3  *
   4  * This module has the Cell header definition and other support stuff (like
   5  * BlkAttr) for the Naive Garbage Collector implementation. The Cell header has
   6  * all the information needed for the bookkeeping of the GC allocated memory,
   7  * like the mark bit, if the cell contents should be finalized or if it has
   8  * pointers that should be scanned, etc.
   9  *
  10  * See_Also:  gc module
  11  * Copyright: Public Domain
  12  * License:   Public Domain
  13  * Authors:   Leandro Lucarella <llucax@gmail.com>
  14  */
  15
  16 module gc.cell;
  17
  18 import cstdlib = tango.stdc.stdlib;
  19
  20 package:
  21
  22 /**
  23  * Iterates a range of memory interpreting it as an array of void*.
  24  *
  25  * This function is designed to be used as a opApply implementation.
  26  */
  27 int op_apply_ptr_range(void* from, void* to, int delegate(ref void*) dg)
  28 {
  29     int result = 0;
  30     auto start = cast(void**) from;
  31     auto end = cast(void**) to;
  32     // since we sweep the memory range in word-sized steps, we need to make
  33     // sure we don't scan for pointers beyond the end of the memory range
  34     for (auto current = start; current + 1 <= end; current++) {
  35         result = dg(*current);
  36         if (result)
  37             break;
  38     }
  39     return result;
  40 }
  41
  42 /// Memory block (cell) attributes.
  43 enum BlkAttr : uint
  44 {
  45     /// All attributes disabled.
  46     NONE     = 0b0000_0000,
  47     /// The cell is an object with a finalizer.
  48     FINALIZE = 0b0000_0001,
  49     /// The cell has no pointers.
  50     NO_SCAN  = 0b0000_0010,
  51     /// The cell should not be moved (unimplemented).
  52     NO_MOVE  = 0b0000_0100,
  53     /// All attributes enabled.
  54     ALL      = 0b1111_1111,
  55 }
  56
  57 /**
  58  * Memory block (cell) header.
  59  *
  60  * All memory cells in the GC heap have this header.
  61  */
  62 struct Cell
  63 {
  64
  65     /// Size of the object stored in this memory cell.
  66     size_t size = 0;
  67
  68     /// Real size of the memory cell.
  69     size_t capacity = 0;
  70
  71     /// Mark bit.
  72     bool marked = true;
  73
  74     /// Cell attributes.
  75     BlkAttr attr = BlkAttr.NONE;
  76
  77     /// Next cell (this is used for free/live lists linking).
  78     Cell* next = null;
  79
  80     /**
  81      * Address to the start of the malloc()ed memory block.
  82      *
  83      * This is mostly needed because memory should be aligned to the word
  84      * size, so we have to adjust data pointers to start at an address
  85      * multiple of the word size. Then, our header could not be at the start
  86      * of the block. We need to keep the beginning of the block address to be
  87      * able to free() it.
  88      */
  89     void* block_start = null;
  90
  91     invariant()
  92     {
  93         assert (this.size > 0);
  94         assert (this.capacity >= this.size);
  95     }
  96
  97     /**
  98      * Allocate a new cell.
  99      *
 100      * Allocate a new cell (asking for fresh memory to the OS). The cell is
 101      * initialized with the provided size and attributes. The capacity can be
 102      * larger than the requested size, though. The attribute marked is set to
 103      * true (assuming the cell will be used as soon as allocated) and next is
 104      * set to null.
 105      *
 106      * Returns a pointer to the new cell or null if it can't allocate new
 107      * memory.
 108      */
 109     static Cell* alloc(size_t size, uint attr = 0)
 110     {
 111         size_t word_size = size_t.sizeof;
 112         size_t block_size = size + Cell.sizeof + word_size;
 113         auto block_start = cast(byte*) cstdlib.malloc(block_size + word_size);
 114         if (block_start is null)
 115             return null;
 116         byte* data_start = block_start + block_size - size - size % word_size;
 117         auto cell = Cell.from_ptr(data_start);
 118         cell.block_start = block_start;
 119         cell.capacity = block_size - (data_start - block_start);
 120         cell.size = size;
 121         cell.attr = cast(BlkAttr) attr;
 122         cell.marked = true;
 123         cell.next = null;
 124         return cell;
 125     }
 126
 127     /// Free a cell allocated by Cell.alloc().
 128     static void free(Cell* cell)
 129     {
 130         cstdlib.free(cell.block_start);
 131     }
 132
 133     /**
 134      * Get a cell pointer for the cell that stores the object pointed to by
 135      * ptr.
 136      *
 137      * If ptr is null, null is returned.
 138      */
 139     static Cell* from_ptr(void* ptr)
 140     {
 141         if (ptr is null)
 142             return null;
 143         return cast(Cell*) (cast(byte*) ptr - Cell.sizeof);
 144     }
 145
 146     /// Get the base address of the object stored in the cell.
 147     void* ptr()
 148     {
 149         return cast(void*) (cast(byte*) this + Cell.sizeof);
 150     }
 151
 152     /// Return true if the cell should be finalized, false otherwise.
 153     bool has_finalizer()
 154     {
 155         return cast(bool) (this.attr & BlkAttr.FINALIZE);
 156     }
 157
 158     /// Return true if the cell should may have pointers, false otherwise.
 159     bool has_pointers()
 160     {
 161         return !(this.attr & BlkAttr.NO_SCAN);
 162     }
 163
 164     /**
 165      * Iterates over the objects pointers.
 166      *
 167      * Current implementation interprets the whole object as if it were
 168      * an array of void*.
 169      */
 170     int opApply(int delegate(ref void*) dg)
 171     {
 172         return op_apply_ptr_range(this.ptr, this.ptr + this.size, dg);
 173     }
 174
 175 }
 176
 177 debug (UnitTest)
 178 {
 179
 180 private:
 181
 182     unittest // op_apply_ptr_range()
 183     {
 184         size_t[10] v;
 185         int i = 5;
 186         foreach (ref x; v)
 187             x = i++;
 188         i = 5;
 189         int r = op_apply_ptr_range(v.ptr, v.ptr + 10,
 190                 (ref void* ptr) {
 191                     assert (cast (size_t) ptr == i++);
 192                     return 0;
 193                 });
 194     }
 195
 196     unittest // Cell
 197     {
 198         auto size = 27;
 199         auto cell = Cell.alloc(size, BlkAttr.FINALIZE | BlkAttr.NO_SCAN);
 200         assert (cell !is null);
 201         assert (cell.ptr is cell + 1);
 202         for (int i = 0; i < size; ++i) {
 203             auto ptr = cast(ubyte*) cell.ptr + i;
 204             *ptr = i + size;
 205         }
 206         size_t i = size;
 207         foreach (void* ptr; *cell) {
 208             for (int j = 0; j < size_t.sizeof; ++j)
 209                 assert ((cast(ubyte*) ptr)[j] == i++);
 210         }
 211         assert (cell.has_finalizer());
 212         assert (!cell.has_pointers());
 213         assert (cell is Cell.from_ptr(cell.ptr));
 214     }
 215
 216 } // debug (UnitTest)
 217
 218 // vim: set et sw=4 sts=4 :