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     invariant()
  81     {
  82         assert (this.size > 0);
  83         assert (this.capacity >= this.size);
  84     }
  85
  86     /**
  87      * Allocate a new cell.
  88      *
  89      * Allocate a new cell (asking for fresh memory to the OS). The cell is
  90      * initialized with the provided size and attributes. The capacity can be
  91      * larger than the requested size, though. The attribute marked is set to
  92      * true (assuming the cell will be used as soon as allocated) and next is
  93      * set to null.
  94      *
  95      * Returns a pointer to the new cell or null if it can't allocate new
  96      * memory.
  97      */
  98     static Cell* alloc(size_t size, uint attr = 0)
  99     {
 100         auto cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
 101         if (cell is null)
 102             return null;
 103         cell.capacity = size;
 104         cell.size = size;
 105         cell.attr = cast(BlkAttr) attr;
 106         cell.marked = true;
 107         cell.next = null;
 108         return cell;
 109     }
 110
 111     /// Free a cell allocated by Cell.alloc().
 112     static void free(Cell* cell)
 113     {
 114         cstdlib.free(cell);
 115     }
 116
 117     /**
 118      * Get a cell pointer for the cell that stores the object pointed to by
 119      * ptr.
 120      *
 121      * If ptr is null, null is returned.
 122      */
 123     static Cell* from_ptr(void* ptr)
 124     {
 125         if (ptr is null)
 126             return null;
 127         return cast(Cell*) (cast(byte*) ptr - Cell.sizeof);
 128     }
 129
 130     /// Get the base address of the object stored in the cell.
 131     void* ptr()
 132     {
 133         return cast(void*) (cast(byte*) this + Cell.sizeof);
 134     }
 135
 136     /// Return true if the cell should be finalized, false otherwise.
 137     bool has_finalizer()
 138     {
 139         return cast(bool) (this.attr & BlkAttr.FINALIZE);
 140     }
 141
 142     /// Return true if the cell should may have pointers, false otherwise.
 143     bool has_pointers()
 144     {
 145         return !(this.attr & BlkAttr.NO_SCAN);
 146     }
 147
 148     /**
 149      * Iterates over the objects pointers.
 150      *
 151      * Current implementation interprets the whole object as if it were
 152      * an array of void*.
 153      */
 154     int opApply(int delegate(ref void*) dg)
 155     {
 156         return op_apply_ptr_range(this.ptr, this.ptr + this.size, dg);
 157     }
 158
 159 }
 160
 161 debug (UnitTest)
 162 {
 163
 164 private:
 165
 166     unittest // op_apply_ptr_range()
 167     {
 168         size_t[10] v;
 169         int i = 5;
 170         foreach (ref x; v)
 171             x = i++;
 172         i = 5;
 173         int r = op_apply_ptr_range(v.ptr, v.ptr + 10,
 174                 (ref void* ptr) {
 175                     assert (cast (size_t) ptr == i++);
 176                     return 0;
 177                 });
 178     }
 179
 180     unittest // Cell
 181     {
 182         auto N = 10;
 183         auto size = N * size_t.sizeof;
 184         auto cell = Cell.alloc(size, BlkAttr.FINALIZE | BlkAttr.NO_SCAN);
 185         assert (cell);
 186         assert (cell.ptr is cell + 1);
 187         for (int i = 0; i < N; ++i) {
 188             auto ptr = cast(size_t*) cell.ptr + i;
 189             *ptr = i + N;
 190         }
 191         size_t i = N;
 192         foreach (void* ptr; *cell) {
 193             assert (cast(size_t) ptr == i++);
 194         }
 195         assert (*(cast(size_t*) cell.ptr) == N);
 196         assert (cell.has_finalizer());
 197         assert (!cell.has_pointers());
 198         assert (cell is Cell.from_ptr(cell.ptr));
 199     }
 200
 201 } // debug (UnitTest)
 202
 203 // vim: set et sw=4 sts=4 :