X-Git-Url: https://git.llucax.com/software/dgc/naive.git/blobdiff_plain/802aa7fc0eeb044538d371e936197752bbb53612..refs/heads/master:/gc/gc.d diff --git a/gc/gc.d b/gc/gc.d index 5f341f0..a10143a 100644 --- a/gc/gc.d +++ b/gc/gc.d @@ -3,23 +3,22 @@ * * 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 @@ -37,7 +36,6 @@ import gc.dynarray: DynArray; import gc.arch: push_registers, pop_registers; // Standard imports -import cstdlib = tango.stdc.stdlib; import cstring = tango.stdc.string; // Debug imports @@ -65,7 +63,7 @@ extern (C) void thread_scanAll(mark_function mark, void* stack_top=null); struct RootRange { - /// Start of the memory range + /// Beginning of the memory range void* from; /// End of the memory range @@ -152,8 +150,6 @@ struct BlkInfo struct GC { -// TODO: GC Lock - private: /// List of free cells. @@ -165,7 +161,7 @@ private: /// Single root pointers. DynArray!(void*) root_pointers; - /// Single root pointers. + /// Root ranges. DynArray!(RootRange) root_ranges; /** @@ -197,7 +193,7 @@ private: } /** - * Marks all live data (pausing all threads) + * Mark all live data (pausing all threads) * * This methods start marking following all the known roots: * @@ -253,8 +249,7 @@ private: * 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. @@ -271,7 +266,7 @@ private: } /** - * 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 @@ -400,7 +395,7 @@ public: * 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. @@ -439,17 +434,17 @@ public: { 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)) @@ -460,7 +455,7 @@ public: uint getAttr(void* ptr) { auto cell = this.live_list.find(ptr); - if (cell) + if (cell !is null) return cell.attr; return 0; } @@ -476,7 +471,7 @@ public: 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; @@ -495,7 +490,7 @@ public: 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; @@ -523,33 +518,33 @@ public: // 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; @@ -562,11 +557,12 @@ public: */ 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; @@ -580,7 +576,7 @@ public: * 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) { @@ -596,7 +592,7 @@ public: } 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) { @@ -606,8 +602,11 @@ public: // 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; @@ -642,29 +641,27 @@ public: * 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++). * @@ -678,7 +675,7 @@ public: return; auto cell = this.live_list.pop(ptr); - assert (cell); + assert (cell !is null); this.free_list.link(cell); } @@ -699,14 +696,14 @@ public: } 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 @@ -718,13 +715,13 @@ public: 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 @@ -737,7 +734,7 @@ public: 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; @@ -782,8 +779,8 @@ public: /** * 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() */ @@ -795,8 +792,8 @@ public: /** * 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() */