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