*
* This module implements a Naive Garbage Collector. The idea behind this
* implementation is to document all the bookkeeping and considerations that
- * has to be taken in order to implement a garbage collector for D.
+ * have to be taken in order to implement a garbage collector for D.
*
- * The garbage collector algorithm itself is extremely simple so focus can be
- * held in the specifics of D, and not the algorithm. A completely naive mark
- * and sweep algorithm is used, with a recursive mark phase. The code is
- * extremely inefficient in order to keep the code clean and easy to read and
- * understand.
+ * The garbage collector algorithm itself is extremely simple to make it
+ * easier to focus on the specifics of D. A completely naive mark and sweep
+ * algorithm is used, with a recursive mark phase. The code is extremely
+ * inefficient in order to keep it clean, and easy to read and understand.
*
- * The implementation is split in several modules to ease even more the
- * lecture. All architecture/compiler specific code is done in the arch module,
- * in order to avoid confusing version statements all over the places. The cell
- * module has all the code related to the memory cells header. dynarray is
- * another support module which holds the implementation of a simple dynamic
- * array used to store root pointers and ranges. The list module holds a simple
- * singly linked list (of cells) implementation to store the live and free
- * lists. Finally, the iface module is the one with the C interface to comply
- * with the Tango/Druntime GC specification.
+ * The implementation is split in several modules to ease the reading even
+ * more. All architecture/compiler specific code is done in the arch module,
+ * in order to avoid confusing version statements all over the places. The
+ * cell module has all the code related to the memory cells header. dynarray
+ * is another support module which holds the implementation of a simple
+ * dynamic array used to store root pointers and ranges. The list module holds
+ * a simple singly linked list (of cells) implementation to store the live and
+ * free lists. Finally, the iface module is the one with the C interface to
+ * comply with the Tango/Druntime GC specification.
*
* Copyright: Public Domain
* License: Public Domain
import gc.arch: push_registers, pop_registers;
// Standard imports
-import cstdlib = tango.stdc.stdlib;
import cstring = tango.stdc.string;
// Debug imports
struct RootRange
{
- /// Start of the memory range
+ /// Beginning of the memory range
void* from;
/// End of the memory range
struct GC
{
-// TODO: GC Lock
-
private:
/// List of free cells.
/// Single root pointers.
DynArray!(void*) root_pointers;
- /// Single root pointers.
+ /// Root ranges.
DynArray!(RootRange) root_ranges;
/**
}
/**
- * Marks all live data (pausing all threads)
+ * Mark all live data (pausing all threads)
*
* This methods start marking following all the known roots:
*
* Wrapper for mark() over a range, needed by some runtime functions.
*
* This function is used as a delegate to be passed to rt_scanStaticData()
- * and thread_scanAll(), because they expects a function taking
- * 2 pointers.
+ * and thread_scanAll(), because they expect a function taking 2 pointers.
*
* This extremely inefficient on purpose. The goal of this implementation
* is simplicity, nor performance.
}
/**
- * Marks all cells accessible from a pointer.
+ * Mark all cells accessible from a pointer.
*
* This is the mark algorithm itself. It's recursive and dumb as a log. No
* care is taken in regards to stack overflows. This is the first example
* Run a GC collection in order to find unreferenced objects.
*
* This is the simplest stop-the-world mark-sweep algorithm ever. It first
- * removes the mark bit from all the live cells, then it mark the cells
+ * removes the mark bit from all the live cells, then it marks the cells
* that are reachable through the root set (static data, stack, registers
* and custom root), and finally sweeps the live list looking for unmarked
* cells to free.
{
foreach (cell; this.free_list) {
this.free_list.unlink(cell);
- cstdlib.free(cell);
+ Cell.free(cell);
}
}
/**
* Get attributes associated to the cell pointed by ptr.
*
- * Attributes is a bitmap that can have theses values:
+ * Attributes is a bitmap that can have these values:
*
* $(UL
- * $(LI 1: The object stored in the cell have to be finalized)
+ * $(LI 1: The object stored in the cell has to be finalized)
* $(LI 2: The cell should not be scanned for pointers)
* $(LI 4: The cell should not be moved during a collection
* (unimplemented))
uint getAttr(void* ptr)
{
auto cell = this.live_list.find(ptr);
- if (cell)
+ if (cell !is null)
return cell.attr;
return 0;
}
uint setAttr(void* ptr, uint attr)
{
auto cell = this.live_list.find(ptr);
- if (cell) {
+ if (cell !is null) {
auto old = cell.attr;
cell.attr |= attr;
return cell.attr;
uint clrAttr(void* ptr, uint attr)
{
auto cell = this.live_list.find(ptr);
- if (cell) {
+ if (cell !is null) {
auto old = cell.attr;
cell.attr &= ~attr;
return cell.attr;
// Find a free cell in the free list with enough space
auto cell = this.free_list.pop(size);
- if (cell)
- goto success;
+ if (cell !is null)
+ goto reuse;
// No room in the free list found, if the GC is enabled, trigger
// a collection and try again
if (!this.disabled) {
this.collect();
cell = this.free_list.pop(size);
- if (cell)
- goto success;
+ if (cell !is null)
+ goto reuse;
}
- // No luck still, allocate new memory
- cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
- if (cell)
- goto success;
+ // No luck still, allocate a new cell
+ cell = Cell.alloc(size, attr);
+ if (cell !is null)
+ goto link;
// No memory
onOutOfMemoryError();
return null;
- success:
+ reuse:
cell.size = size;
- if (cell.capacity == 0) // fresh cell
- cell.capacity = size;
cell.attr = cast(BlkAttr) attr;
+
+ link:
this.live_list.link(cell);
return cell.ptr;
*/
void* calloc(size_t size, uint attr=0)
{
+ if (size == 0)
+ return null;
+
void* ptr = this.malloc(size, attr);
- if (ptr is null)
- onOutOfMemoryError();
- else
+ if (ptr !is null) // in case onOutOfMemoryError didn't throw
cstring.memset(ptr, 0, size);
return ptr;
* returned. Otherwise a new cell is allocated using malloc() (this can
* trigger a collection), the contents are moved and the old cell is freed.
*
- * attr are the same as malloc().
+ * attr has the same meaning as in malloc().
*/
void* realloc(void* ptr, size_t size, uint attr=0)
{
}
auto cell = this.live_list.find(ptr);
- assert (cell);
+ assert (cell !is null);
// We have enough capacity already, just change the size
if (cell.capacity >= size) {
// We need to move the cell because of the lack of capacity, find
// a free cell with the requested capacity (at least)
- Cell* new_cell = Cell.from_ptr(this.malloc(size));
- assert (!(new_cell is null)); // out of memory is handled by malloc()
+ ptr = this.malloc(size, attr);
+ if (ptr is null) // in case onOutOfMemoryError didn't throw
+ return null;
+ Cell* new_cell = Cell.from_ptr(ptr);
+ assert (new_cell !is null);
// Move cell attributes and contents
new_cell.attr = cell.attr;
* Reserve memory to anticipate memory allocations.
*
* This implementation is really dumb, a single cell is allocated with
- * size bytes. If 2 mallocs() follows a call to reserve(size), requesting
- * size/2 bytes each, one allocation will be done still (and half the
- * memory of the first malloc will be wasted =) Since this is a trivial
+ * size bytes. If 2 malloc()s follow a call to reserve(size), requesting
+ * size/2 bytes each, one allocation will still be done (and half the
+ * memory of the first malloc will be wasted =). Since this is a trivial
* implementation, we don't care about this.
*
- * The actual number of bytes reserver are returned, or 0 on error.
+ * The actual number of bytes reserved are returned, or 0 on error.
*/
size_t reserve(size_t size)
{
assert (size > 0);
- auto cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
- if (!cell)
+ auto cell = Cell.alloc(size);
+ if (cell is null)
return 0;
- cell.size = size;
- cell.capacity = size;
this.free_list.link(cell);
- return size;
+ return cell.capacity;
}
/**
* Free unused memory.
*
- * This method tells the GC that a cell is not longer used. The GC don't
+ * This method tells the GC that a cell is not longer used. The GC doesn't
* perform any connectivity check, if the cell was referenced by others,
* nasty things will happen (much like C/C++).
*
return;
auto cell = this.live_list.pop(ptr);
- assert (cell);
+ assert (cell !is null);
this.free_list.link(cell);
}
}
auto cell = this.live_list.find(&in_range);
- if (cell)
+ if (cell !is null)
return cell.ptr;
return null;
}
/**
- * Return the real size (capacity) for the cell pointed by ptr.
+ * Return the real size (capacity) for the cell pointed to by ptr.
*
* ptr should be the base address of a heap allocated object, interior
* pointers are not supported (use addrOf() if you have an interior
size_t sizeOf(void* ptr)
{
auto cell = this.live_list.find(ptr);
- if (cell)
+ if (cell !is null)
return cell.capacity;
return 0;
}
/**
- * Get information about the cell pointed by ptr.
+ * Get information about the cell pointed to by ptr.
*
* ptr should be the base address of a heap allocated object, interior
* pointers are not supported (use addrOf() if you have an interior
BlkInfo blk_info;
auto cell = this.live_list.find(ptr);
- if (cell) {
+ if (cell !is null) {
blk_info.base = cell.ptr;
blk_info.size = cell.capacity;
blk_info.attr = cell.attr;
/**
* Remove a root pointer from the root set.
*
- * ptr has to be previously registered using addRoot(), in other case the
- * results of this method is undefined.
+ * ptr has to be previously registered using addRoot(), otherwise the
+ * results are undefined.
*
* See_Also: addRoot(), addRange(), removeRange()
*/
/**
* Remove a root range from the root set.
*
- * ptr has to be previously registered using addRange(), in other case the
- * results of this method is undefined.
+ * ptr has to be previously registered using addRange(), otherwise the
+ * results are undefined.
*
* See_Also: addRange(), addRoot(), removeRoot()
*/
projects / software / dgc / naive.git / blobdiff