From: Leandro Lucarella Date: Sat, 25 Apr 2009 23:37:44 +0000 (-0300) Subject: Remove alloc module, move all other modules to gc/ and document X-Git-Tag: v0.9 X-Git-Url: https://git.llucax.com/software/dgc/naive.git/commitdiff_plain/802aa7fc0eeb044538d371e936197752bbb53612 Remove alloc module, move all other modules to gc/ and document There are another bugfixes and restructuration (like debug prints removal). This version should be the initial commit, the previos version is keeped only because the alloc module can be useful in the future for other implementations. --- diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..85e82fa --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +*.bc +*.o +libtango-gc-naive.a diff --git a/alloc.d b/alloc.d deleted file mode 100644 index 19aceaa..0000000 --- a/alloc.d +++ /dev/null @@ -1,124 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module alloc; - -version (Win32) -{ - private import tango.sys.win32.UserGdi; -} -else version (Posix) -{ - private import tango.stdc.posix.sys.mman; - private import tango.stdc.stdlib; -} -else -{ - private import tango.stdc.stdlib; -} - -static if (is(typeof(VirtualAlloc))) -{ - - void* mem_alloc(size_t size) - { - return VirtualAlloc(null, size, MEM_RESERVE, PAGE_READWRITE); - } - - /** - * Free memory allocated with alloc(). - * Returns: - * 0 success - * !=0 failure - */ - int mem_free(void* ptr, size_t size) - { - return cast(int)(VirtualFree(ptr, 0, MEM_RELEASE) == 0); - } - -} -else static if (is(typeof(mmap))) -{ - - void* mem_alloc(size_t size) - { - void* ptr = mmap(null, size, PROT_READ | PROT_WRITE, - MAP_PRIVATE | MAP_ANON, -1, 0); - if (ptr == MAP_FAILED) - ptr = null; - return ptr; - } - - int mem_free(void* ptr, size_t size) - { - return munmap(ptr, size); - } - -} -else static if (is(typeof(valloc))) -{ - - void* mem_alloc(size_t size) - { - return valloc(size); - } - - int mem_free(void* ptr, size_t size) - { - free(ptr); - return 0; - } -} -else static if (is(typeof(malloc))) -{ - - // NOTE: This assumes malloc granularity is at least size_t.sizeof. If - // (req_size + PAGESIZE) is allocated, and the pointer is rounded up - // to PAGESIZE alignment, there will be space for a void* at the end - // after PAGESIZE bytes used by the GC. - - - enum { PAGESIZE = 4096 } - - const size_t PAGE_MASK = PAGESIZE - 1; - - void* mem_alloc(size_t size) - { - byte* p, q; - p = cast(byte *) malloc(size + PAGESIZE); - q = p + ((PAGESIZE - ((cast(size_t) p & PAGE_MASK))) & PAGE_MASK); - * cast(void**)(q + size) = p; - return q; - } - - int mem_free(void* ptr, size_t size) - { - free(*cast(void**)(cast(byte*) ptr + size)); - return 0; - } - -} -else -{ - - static assert(false, "No supported allocation methods available."); - -} - -// vim: set et sw=4 sts=4 : diff --git a/arch.d b/arch.d deleted file mode 100644 index fbfa40f..0000000 --- a/arch.d +++ /dev/null @@ -1,159 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module arch; - -// TODO: explain why the functions return strings to use as string mixins - -/* - * Small hack to define the string alias if not defined - * - * Tango don't define this alias in object.d, but Phobos 1 and 2 does. - */ -// XXX: this doesnt work: -// static if (!is(string)) -// alias char[] string; -// See: http://d.puremagic.com/issues/show_bug.cgi?id=2848 -version (Tango) - alias char[] string; - -/* - * Functions dependant on the direction in which the stack grows - * - * By default, stack is considered to grow down, as in x86 architectures. - */ - -version = STACK_GROWS_DOWN; - -bool stack_smaller(void* ptr1, void* ptr2) -{ - version (STACK_GROWS_DOWN) - return ptr1 > ptr2; - else - return ptr1 < ptr2; -} - -// Functions to push/pop registers into/from the stack - -version (GNU) -{ - - /* - * GCC has an intrinsic function that does the job of pushing the registers - * into the stack, we use that function if available because it should work - * in all GCC supported architectures. - */ - - string push_registers(string sp_name) - { - return " - __builtin_unwind_init(); - " ~ sp_name ~ " = &" ~ sp_name ~ "; - "; - } - - string pop_registers(string sp_name) - { - return ""; - } - -} -else version (X86) -{ - - /* - * For X86 PUSHAD/POPAD are not used because they are too fragile to - * compiler optimizations (like ommitting the frame pointer). - * - * This method should work safely with all optimizations because it doesn't - * works behind the compilers back. - */ - - string push_registers(string sp_name) - { - return " - size_t eax, ecx, edx, ebx, ebp, esi, edi; - asm - { - mov eax[EBP], EAX; - mov ecx[EBP], ECX; - mov edx[EBP], EDX; - mov ebx[EBP], EBX; - mov ebp[EBP], EBP; - mov esi[EBP], ESI; - mov edi[EBP], EDI; - mov " ~ sp_name ~ "[EBP], ESP; - } - "; - } - - string pop_registers(string sp_name) - { - return ""; - } - -} -else version (X86_64) -{ - - /* - * See X86 comment above. - */ - - string push_registers(string sp_name) - { - return " - size_t rax, rbx, rcx, rdx, rbp, rsi, rdi, - r10, r11, r12, r13, r14, r15; - asm - { - movq rax[RBP], RAX; - movq rbx[RBP], RBX; - movq rcx[RBP], RCX; - movq rdx[RBP], RDX; - movq rbp[RBP], RBP; - movq rsi[RBP], RSI; - movq rdi[RBP], RDI; - movq r10[RBP], R10; - movq r11[RBP], R11; - movq r12[RBP], R12; - movq r13[RBP], R13; - movq r14[RBP], R14; - movq r15[RBP], R15; - movq " ~ sp_name ~ "[RBP], RSP; - } - "; - } - - string pop_registers(string sp_name) - { - return ""; - } - -} -else // Unkown compiler/architecture -{ - - pragma(msg, "Don't know how to push registers into the stack for this " - "compiler/architecture"); - static assert(false); - -} - -// vim: set et sw=4 sts=4 : diff --git a/cell.d b/cell.d deleted file mode 100644 index 5c26205..0000000 --- a/cell.d +++ /dev/null @@ -1,87 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module cell; - -package: - -enum BlkAttr : uint -{ - FINALIZE = 0b0000_0001, - NO_SCAN = 0b0000_0010, - NO_MOVE = 0b0000_0100, - ALL_BITS = 0b1111_1111, -} - -struct Cell -{ - - size_t size = 0; - - size_t capacity = 0; - - bool marked = true; - - BlkAttr attr = cast(BlkAttr) 0; - - Cell* next = null; - - static Cell* from_ptr(void* ptr) - { - if (ptr is null) - return null; - return cast(Cell*) (cast(byte*) ptr - Cell.sizeof); - } - - void* ptr() - { - return cast(void*) (cast(byte*) this + Cell.sizeof); - } - - bool finalize() - { - return cast(bool) (this.attr & BlkAttr.FINALIZE); - } - - bool has_pointers() - { - return !(this.attr & BlkAttr.NO_SCAN); - } - - int opApply(int delegate(ref void*) dg) - { - int result = 0; - auto from = cast(void**) this.ptr; - auto to = cast(void**) this.ptr + this.size; - // TODO: alignment. The range should be aligned and the size - // should be a multiple of the word size. If the later does - // not hold, the last bytes that are not enough to build - // a complete word should be ignored. Right now we are - // doing invalid reads in that cases. - for (auto current = from; current < to; current++) { - result = dg(*current); - if (result) - break; - } - return result; - } - -} - -// vim: set et sw=4 sts=4 : diff --git a/dynarray.d b/dynarray.d deleted file mode 100644 index b7e5059..0000000 --- a/dynarray.d +++ /dev/null @@ -1,89 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module dynarray; - -private import tango.stdc.stdlib: realloc; -private import tango.stdc.string: memmove; -private extern (C) void onOutOfMemoryError(); - -package: - -struct DynArray(T) -{ - - T* data = null; - - size_t capacity = 0; - - size_t size = 0; - - invariant - { - assert (this.data); - assert (this.capacity >= this.size); - } - - void append(T x) - { - if (this.size == this.capacity) - this.expand(); - this.data[this.size] = x; - this.size++; - } - - void remove(T x) - { - for (size_t i = 0; i < this.size; i++) { - if (this.data[i] == x) { - this.size--; - memmove(this.data + i, this.data + i + T.sizeof, - (this.size - i) * T.sizeof); - return; - } - } - } - - void expand(size_t new_capacity=0) - { - if (new_capacity == 0) - new_capacity = this.size * 2; - if (new_capacity == 0) - new_capacity = 4; - T* new_data = cast(T*) realloc(this.data, new_capacity); - if (new_data is null) - onOutOfMemoryError(); - this.data = new_data; - this.capacity = new_capacity; - } - - int opApply(int delegate(ref T) dg) - { - int result = 0; - for (size_t i = 0; i < this.size; i++) { - result = dg(this.data[i]); - if (result) - break; - } - return result; - } - -} - -// vim: set et sw=4 sts=4 : diff --git a/gc.d b/gc.d deleted file mode 100644 index 67b2d56..0000000 --- a/gc.d +++ /dev/null @@ -1,480 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module gc; - -private { - - import cell: Cell, BlkAttr; - import list: List; - import dynarray: DynArray; - import arch: stack_smaller, push_registers, pop_registers; - import alloc: mem_alloc, mem_free; - - import stdc = tango.stdc.stdlib; - import tango.stdc.string: memset, memcpy; - debug import tango.stdc.stdio: printf; - - alias void delegate(void*, void*) mark_function; - extern (C) void onOutOfMemoryError(); - extern (C) void rt_finalize(void* p, bool det=true); - extern (C) void rt_scanStaticData(mark_function mark); - extern (C) void thread_init(); - extern (C) bool thread_needLock(); - extern (C) void thread_suspendAll(); - extern (C) void thread_resumeAll(); - extern (C) void thread_scanAll(mark_function mark, void* stack_top=null); - - struct RootRange - { - - void* from; - - void* to; - - int opApply(int delegate(ref void*) dg) - { - int result = 0; - auto from = cast(void**) this.from; - auto to = cast(void**) this.to; - // TODO: alignment. The range should be aligned and the size - // should be a multiple of the word size. If the later does - // not hold, the last bytes that are not enough to build - // a complete word should be ignored. Right now we are - // doing invalid reads in that cases. - for (void** current = from; current < to; current++) { - result = dg(*current); - if (result) - break; - } - return result; - } - - } - -} - -struct BlkInfo -{ - void* base; - size_t size; - uint attr; -} - -// TODO: ver bien donde desmarkcar/marcar celdas (probablemente en malloc) - -struct NaiveGC -{ - -private: - - List free_list; - - List live_list; - - DynArray!(void*) root_pointers; - - DynArray!(RootRange) root_ranges; - - uint enabled; - - void unmark() - { - debug (gc_naive_gc_collect) - printf("gc.unmark()\n"); - foreach (cell; this.live_list) - cell.marked = false; - } - - void mark_all() - { - debug (gc_naive_gc_collect) - printf("gc.mark_all()\n"); - void* stack_top; - mixin (push_registers("stack_top")); - thread_suspendAll(); - debug (gc_naive_gc_collect) - printf("gc.mark_all() - scanning static data\n"); - rt_scanStaticData(&mark_range); - debug (gc_naive_gc_collect) - printf("gc.mark_all() - scanning threads stack\n"); - thread_scanAll(&mark_range, stack_top); - debug (gc_naive_gc_collect) - printf("gc.mark_all() - scanning root pointers:"); - foreach (ptr; this.root_pointers) { - debug (gc_naive_gc_collect) - printf(" %p", ptr); - this.mark(ptr); - } - debug (gc_naive_gc_collect) - printf("\ngc.mark_all() - scanning root ranges:"); - foreach (range; this.root_ranges) { - debug (gc_naive_gc_collect) - printf(" %p-%p", range.from, range.to); - this.mark_range(range.from, range.to); - } - debug (gc_naive_gc_collect) - printf("\n"); - thread_resumeAll(); - mixin (pop_registers("stack_top")); - } - - void mark_range(void* from, void* to) - { - debug (gc_naive_gc_collect) - printf("gc.mark_range(%p, %p)\n", from, to); - foreach (ptr; RootRange(from, to)) - mark(ptr); - } - - void mark(void* ptr) - { - debug (gc_naive_gc_collect_extra) - printf("gc.mark(%p)\n", ptr); - Cell* cell = Cell.from_ptr(this.addrOf(ptr)); - if (cell is null) - return; - debug (gc_naive_gc_collect) - printf("gc.mark() - %p cell=%p\n", cell.ptr, cell); - if (!cell.marked) { - cell.marked = true; - debug (gc_naive_gc_collect) - printf("gc.mark() - cell=%p marked\n", cell); - if (cell.has_pointers) { - foreach (ptr; *cell) - mark(ptr); - } - } - } - - void sweep() - { - debug (gc_naive_gc_collect) { - printf("gc.sweep()\n\tfree:"); - foreach (cell; this.free_list) - printf(" %p", cell); - printf("\n\tlive:"); - foreach (cell; this.live_list) - printf(" %s%p", cell.marked ? "*\0".ptr : "\0".ptr, cell); - printf("\n\tfreed:"); - } - foreach (cell; this.live_list) { - if (!cell.marked) { - debug (gc_naive_gc_collect) - printf(" %p", cell); - this.live_list.unlink(cell); - if (cell.finalize()) - rt_finalize(cell.ptr, false); - this.free_list.link(cell); - } - } - debug (gc_naive_gc_collect) { - printf("\n\tfree:"); - foreach (cell; this.free_list) - printf(" %p", cell); - printf("\n\tlive:"); - foreach (cell; this.live_list) - printf(" %p", cell); - printf("\n"); - } - } - -public: - - void init() - { - // NOTE: The GC must initialize the thread library before its first - // collection, and always before returning from gc_init(). - this.enabled = true; - thread_init(); - } - - void term() - { - // Finalization of unreferenced cells is not mandatory by the specs. - // This implementation guarantees that all live data gets finalized, - // referenced or unreferenced, at the end of the program. - //foreach (cell; this.live_list) - // if (cell.finalize) - // rt_finalize(cell.ptr, false); - } - - void enable() - { - this.enabled++; - assert (this.enabled > 0); - } - - void disable() - { - assert (this.enabled > 0); - this.enabled--; - } - - void collect() - { - this.unmark(); - this.mark_all(); - this.sweep(); - } - - void minimize() - { - foreach (cell; this.free_list) { - this.free_list.unlink(cell); - mem_free(cell, cell.capacity + Cell.sizeof); - } - } - - uint getAttr(void* ptr) - { - auto cell = this.live_list.find(ptr); - if (cell) - return cell.attr; - return 0; - } - - // return the old value - uint setAttr(void* ptr, uint attr) - { - auto cell = this.live_list.find(ptr); - if (cell) { - auto old = cell.attr; - cell.attr |= attr; - return cell.attr; - } - return 0; - } - - uint clrAttr(void* ptr, uint attr) - { - auto cell = this.live_list.find(ptr); - if (cell) { - auto old = cell.attr; - cell.attr &= ~attr; - return cell.attr; - } - return 0; - } - - void* malloc(size_t size, uint attr=0) - { - debug (gc_naive_gc_malloc) - printf("gc.malloc(%u, %u)\n", size, attr); - if (size == 0) - return null; - - // Find a free cell in the free list with enough space - auto cell = this.free_list.pop(size); - if (cell) - goto success; - debug (gc_naive_gc_malloc) - printf("gc.malloc() - no cell available in the free list\n"); - - // No room in the free list found, trigger a collection - this.collect(); - - // Try again in the free list - cell = this.free_list.pop(size); - if (cell) - goto success; - debug (gc_naive_gc_malloc) - printf("gc.malloc() - after collection, still no free cell\n"); - - // No luck still, allocate new memory - cell = cast(Cell*) mem_alloc(size + Cell.sizeof); - if (cell) - goto success; - debug (gc_naive_gc_malloc) - printf("gc.malloc() - can't malloc() from the OS\n"); - - // No memory - onOutOfMemoryError(); - - return null; - - success: - cell.size = size; - if (cell.capacity == 0) // fresh cell - cell.capacity = size; - cell.attr = cast(BlkAttr) attr; - cell.marked = false; - this.live_list.link(cell); - - debug (gc_naive_gc_collect) { - printf("gc.malloc() -> %p (cell=%p)\n\tfree:", cell.ptr, cell); - foreach (cell; this.free_list) - printf(" %p", cell); - printf(" | live:"); - foreach (cell; this.live_list) - printf(" %p", cell); - printf("\n"); - } - - return cell.ptr; - } - - void* calloc(size_t size, uint attr=0) - { - void* ptr = this.malloc(size, attr); - - if (ptr is null) - onOutOfMemoryError(); - else - memset(ptr, 0, size); - - return ptr; - } - - void* realloc(void* ptr, size_t size, uint attr=0) - { - if (ptr is null) - return this.malloc(size, attr); - - if (size == 0) { - this.free(ptr); - return null; - } - - auto cell = this.live_list.find(ptr); - assert (cell); - - if (cell.capacity >= size) { - cell.size = size; - return cell; - } - - Cell* new_cell = cast(Cell*) mem_alloc(size + Cell.sizeof); - if (new_cell is null) - onOutOfMemoryError(); - - memcpy(new_cell, cell, size + Cell.sizeof); - new_cell.size = size; - new_cell.capacity = size; - - this.live_list.link(new_cell); - - this.free(cell); - - return new_cell.ptr; - } - - size_t extend(void* ptr, size_t min_size, size_t max_size) - { - assert (min_size <= max_size); - // There is no possible extension of the capacity for this - // implementation. - return 0; - } - - size_t reserve(size_t size) - { - assert (size > 0); - auto cell = cast(Cell*) mem_alloc(size + Cell.sizeof); - if (!cell) - return 0; - cell.size = size; - cell.capacity = size; - this.free_list.link(cell); - return size; - } - - void free(void* ptr) - { - if (ptr is null) - return; - - auto cell = this.live_list.pop(ptr); - assert (cell); - - this.free_list.link(cell); - } - - void* addrOf(void* ptr) - { - if (ptr is null) - return null; - - bool in_range(Cell* cell) - { - return ptr >= cell.ptr && ptr < (cell.ptr + cell.size); - } - - auto cell = this.live_list.find(&in_range); - if (cell) - return cell.ptr; - - return null; - } - - // TODO: acepta un address que no sea el base? - // es valido aceptar un ptr que no pertenezca al heap? - // (contestado en basic/gcx.d, pero es estandar?) - size_t sizeOf(void* ptr) - { - auto cell = this.live_list.find(ptr); - if (cell) - return cell.capacity; - return 0; - } - - // TODO: acepta un address que no sea el base? - // es valido aceptar un ptr que no pertenezca al heap? - BlkInfo query(void* ptr) - { - BlkInfo blk_info; - - auto cell = this.live_list.find(ptr); - if (cell) { - blk_info.base = cell.ptr; - blk_info.size = cell.capacity; - blk_info.attr = cell.attr; - } - - return blk_info; - } - - void addRoot(void* ptr) - { - this.root_pointers.append(ptr); - } - - void addRange(void* ptr, size_t size) - { - this.root_ranges.append(RootRange(ptr, ptr + size)); - } - - void removeRoot(void* ptr) - { - this.root_pointers.remove(ptr); - } - - void removeRange(void* ptr) - { - foreach (range; this.root_ranges) { - if (range.from is ptr) { - this.root_ranges.remove(range); - break; - } - } - } - -} - -// vim: set et sw=4 sts=4 : diff --git a/gc/arch.d b/gc/arch.d new file mode 100644 index 0000000..9bf4444 --- /dev/null +++ b/gc/arch.d @@ -0,0 +1,188 @@ +/** + * Architecture (and compiler) dependent functions. + * + * This is a support module for the Naive Garbage Collector. All the code that + * depends on the architecture (or compiler) is in this module. + * + * See_Also: gc module + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.arch; + + +package: + +/** + * Small hack to define the string alias if not defined + * + * Tango don't define this alias in object.d, but Phobos 1 and 2 does. + */ +/* + * XXX: this (more general approach) doesn't work: + * + * static if (!is(string)) + * private alias char[] string; + * + * See: http://d.puremagic.com/issues/show_bug.cgi?id=2848 + */ +version (Tango) + private alias char[] string; + + +version (D_Ddoc) +{ + + /** + * Push the registers into the stack. + * + * Note that this function should be used as a string mixin because if + * a regular function call would be done, the stack would be unwound at + * function exit and the register will not longer be in the stack. + * + * A pointer to the top of the stack is stored in a variable with the name + * 'sp_name' (which is expected to be a void*). + * + * Example: + * ----------------------------------------------------------------------- + * void some_function() + * { + * void* sp; + * mixin(push_registers("sp")); + * // Do something + * mixin(pop_registers("sp")); + * } + * ----------------------------------------------------------------------- + * + * See_Also: pop_registers() + * + */ + string push_registers(string sp_name); + + /** + * Pop the registers out the stack. + * + * Note that this function should be used as a string mixin (see + * push_registers() for more details). + * + * A pointer to the top of the stack can be obtained from a variable with + * the name 'sp_name' (which is expected to be a void*). + * + * See_Also: push_registers() + */ + string pop_registers(string sp_name); + +} + + +// Implementation(s) + +version (GNU) +{ + + /* + * GCC has an intrinsic function that does the job of pushing the + * registers into the stack, we use that function if available because it + * should work in all GCC supported architectures. + * + * Nothing needs to be done to pop the registers from the stack. + */ + + string push_registers(string sp_name) + { + return " + __builtin_unwind_init(); + " ~ sp_name ~ " = &" ~ sp_name ~ "; + "; + } + + string pop_registers(string sp_name) + { + return ""; + } + +} +else version (X86) +{ + + /* + * For X86 PUSHAD/POPAD are not used because they are too susceptible to + * compiler optimizations (like omitting the frame pointer). + * + * This method should work safely with all optimizations because it doesn't + * work behind the compilers back. + */ + + string push_registers(string sp_name) + { + return " + size_t eax, ecx, edx, ebx, ebp, esi, edi; + asm + { + mov eax[EBP], EAX; + mov ecx[EBP], ECX; + mov edx[EBP], EDX; + mov ebx[EBP], EBX; + mov ebp[EBP], EBP; + mov esi[EBP], ESI; + mov edi[EBP], EDI; + mov " ~ sp_name ~ "[EBP], ESP; + } + "; + } + + string pop_registers(string sp_name) + { + return ""; + } + +} +else version (X86_64) +{ + + /* + * See X86 comment above, X86_64 uses the same trick. + */ + + string push_registers(string sp_name) + { + return " + size_t rax, rbx, rcx, rdx, rbp, rsi, rdi, + r10, r11, r12, r13, r14, r15; + asm + { + movq rax[RBP], RAX; + movq rbx[RBP], RBX; + movq rcx[RBP], RCX; + movq rdx[RBP], RDX; + movq rbp[RBP], RBP; + movq rsi[RBP], RSI; + movq rdi[RBP], RDI; + movq r10[RBP], R10; + movq r11[RBP], R11; + movq r12[RBP], R12; + movq r13[RBP], R13; + movq r14[RBP], R14; + movq r15[RBP], R15; + movq " ~ sp_name ~ "[RBP], RSP; + } + "; + } + + string pop_registers(string sp_name) + { + return ""; + } + +} +else // Unknown compiler/architecture +{ + + static assert(false, "Don't know how to push registers into the stack " + "for this compiler/architecture"); + +} + +// vim: set et sw=4 sts=4 : diff --git a/gc/cell.d b/gc/cell.d new file mode 100644 index 0000000..d196f60 --- /dev/null +++ b/gc/cell.d @@ -0,0 +1,175 @@ +/** + * Memory Cell header manipulation. + * + * This module has the Cell header definition and other support stuff (like + * BlkAttr) for the Naive Garbage Collector implementation. The Cell header has + * all the information needed for the bookkeeping of the GC allocated memory, + * like the mark bit, if the cell contents should be finalized or if it has + * pointers that should be scanned, etc. + * + * See_Also: gc module + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.cell; + +package: + +/** + * Iterates a range of memory interpreting it as an array of void*. + * + * This function is designed to be used as a opApply implementation. + */ +int op_apply_ptr_range(void* from, void* to, int delegate(ref void*) dg) +{ + int result = 0; + auto start = cast(void**) from; + auto end = cast(void**) to; + // since we sweep the memory range in word-sized steps, we need to make + // sure we don't scan for pointers beyond the end of the memory range + for (auto current = start; current + 1 <= end; current++) { + result = dg(*current); + if (result) + break; + } + return result; +} + +/// Memory block (cell) attributes. +enum BlkAttr : uint +{ + /// All attributes disabled. + NONE = 0b0000_0000, + /// The cell is an object with a finalizer. + FINALIZE = 0b0000_0001, + /// The cell has no pointers. + NO_SCAN = 0b0000_0010, + /// The cell should not be moved (unimplemented). + NO_MOVE = 0b0000_0100, + /// All attributes enabled. + ALL = 0b1111_1111, +} + +/** + * Memory block (cell) header. + * + * All memory cells in the GC heap has this header. + */ +struct Cell +{ + + /// Size of the object stored in this memory cell. + size_t size = 0; + + /// Real size of the memory cell. + size_t capacity = 0; + + /// Mark bit. + bool marked = true; + + /// Cell attributes. + BlkAttr attr = BlkAttr.NONE; + + /// Next cell (this is used for free/live lists linking). + Cell* next = null; + + invariant() + { + assert (this.size > 0); + assert (this.capacity >= this.size); + } + + /** + * Get a cell pointer for the cell that stores the object pointed by ptr. + * + * If ptr is null, null is returned. + */ + static Cell* from_ptr(void* ptr) + { + if (ptr is null) + return null; + return cast(Cell*) (cast(byte*) ptr - Cell.sizeof); + } + + /// Get the base address of the object stored in the cell. + void* ptr() + { + return cast(void*) (cast(byte*) this + Cell.sizeof); + } + + /// Return true if the cell should be finalized, false otherwise. + bool has_finalizer() + { + return cast(bool) (this.attr & BlkAttr.FINALIZE); + } + + /// Return true if the cell should may have pointers, false otherwise. + bool has_pointers() + { + return !(this.attr & BlkAttr.NO_SCAN); + } + + /** + * Iterates over the objects pointers. + * + * Current implementation interprets the whole object as if it were + * an array of void*. + */ + int opApply(int delegate(ref void*) dg) + { + return op_apply_ptr_range(this.ptr, this.ptr + this.size, dg); + } + +} + +debug (UnitTest) +{ + +private: + + import tango.stdc.stdlib: malloc; + + unittest // op_apply_ptr_range() + { + size_t[10] v; + int i = 5; + foreach (ref x; v) + x = i++; + i = 5; + int r = op_apply_ptr_range(v.ptr, v.ptr + 10, + (ref void* ptr) { + assert (cast (size_t) ptr == i++); + return 0; + }); + } + + unittest // Cell + { + auto N = 10; + auto size = N * size_t.sizeof; + auto cell = cast(Cell*) malloc(size + Cell.sizeof); + assert (cell); + assert (cell.ptr is cell + 1); + cell.size = size; + cell.capacity = size; + cell.attr = BlkAttr.FINALIZE | BlkAttr.NO_SCAN; + cell.marked = true; + for (int i = 0; i < N; ++i) { + auto ptr = cast(size_t*) cell.ptr + i; + *ptr = i + N; + } + size_t i = N; + foreach (void* ptr; *cell) { + assert (cast(size_t) ptr == i++); + } + assert (*(cast(size_t*) cell.ptr) == N); + assert (cell.has_finalizer()); + assert (!cell.has_pointers()); + assert (cell is Cell.from_ptr(cell.ptr)); + } + +} // debug (UnitTest) + +// vim: set et sw=4 sts=4 : diff --git a/gc/dynarray.d b/gc/dynarray.d new file mode 100644 index 0000000..f0d5218 --- /dev/null +++ b/gc/dynarray.d @@ -0,0 +1,195 @@ +/** + * Dynamic array. + * + * This module contains a simple dynamic array implementation for use in the + * Naive Garbage Collector. Standard D dynamic arrays can't be used because + * they rely on the GC itself. + * + * See_Also: gc module + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.dynarray; + +// Standard imports +private import tango.stdc.stdlib: realloc; +private import tango.stdc.string: memmove; + +// External runtime functions +private extern (C) void onOutOfMemoryError(); + + +package: + +/** + * Dynamic array. + * + * This is a simple dynamic array implementation. D dynamic arrays can't be + * used because they rely on the GC, and we are implementing the GC. + */ +struct DynArray(T) +{ + +private: + + /// Memory block to hold the array. + T* data = null; + + /// Total array capacity, in number of elements. + size_t capacity = 0; + + /// Current array size, in number of elements. + size_t size = 0; + + invariant() + { + assert ((this.data && this.capacity) + || ((this.data is null) && (this.capacity == 0))); + assert (this.capacity >= this.size); + } + + +public: + + /** + * Append a copy of the element x at the end of the array. + * + * This can trigger an allocation if the array is not big enough. + */ + void append(in T x) + { + if (this.size == this.capacity) + this.expand(); + this.data[this.size] = x; + this.size++; + } + + /** + * Remove the first element for which predicate(element) is true. + */ + void remove_if(bool delegate(ref T) predicate) + { + for (size_t i = 0; i < this.size; i++) { + if (predicate(this.data[i])) { + this.size--; + // move the rest of the items one place to the front + memmove(this.data + i, this.data + i + 1, + (this.size - i) * T.sizeof); + return; + } + } + } + + /** + * Remove the first occurrence of the element x from the array. + */ + void remove(in T x) + { + this.remove_if((ref T e) { return e == x; }); + } + + /** + * Change the current capacity of the array to new_capacity. + * + * This can enlarge or shrink the array, depending on the current capacity. + * If new_capacity is 0, the array is enlarged to hold double the current + * size. If new_capacity is less than the current size, the current size is + * truncated, and the (size - new_capacity) elements at the end are lost. + */ + void expand(in size_t new_capacity=0) + { + // adjust new_capacity if necessary + if (new_capacity == 0) + new_capacity = this.size * 2; + if (new_capacity == 0) + new_capacity = 4; + // reallocate the memory with the new_capacity + T* new_data = cast(T*) realloc(this.data, new_capacity); + if (new_data is null) + onOutOfMemoryError(); + this.data = new_data; + this.capacity = new_capacity; + // truncate the size if necessary + if (this.size > this.capacity) + this.size = this.capacity; + } + + /** + * Remove all the elements of the array and set the capacity to 0. + */ + void clear() + { + this.data = cast(T*) realloc(this.data, 0); + assert (this.data is null); + this.size = 0; + this.capacity = 0; + } + + /** + * Iterate over the array elements. + */ + int opApply(int delegate(ref T) dg) + { + int result = 0; + for (size_t i = 0; i < this.size; i++) { + result = dg(this.data[i]); + if (result) + break; + } + return result; + } + +} + +debug (UnitTest) +{ + +private: + + unittest // DynArray + { + DynArray!(int) array; + assert (array.size == 0); + assert (array.capacity == 0); + assert (array.data == null); + foreach (x; array) + assert (false, "there should be no elements in the array"); + array.append(5); + assert (array.size == 1); + assert (array.capacity >= 1); + assert (array.data); + foreach (x; array) + assert (x == 5); + array.append(6); + assert (array.size == 2); + assert (array.capacity >= 2); + assert (array.data); + int i = 0; + foreach (x; array) + assert (x == 5 + i++); + assert (i == 2); + array.remove(5); + assert (array.size == 1); + assert (array.capacity >= 1); + assert (array.data); + foreach (x; array) + assert (x == 6); + array.expand(100); + assert (array.size == 1); + assert (array.capacity >= 100); + assert (array.data); + foreach (x; array) + assert (x == 6); + array.clear(); + assert (array.size == 0); + assert (array.capacity == 0); + assert (array.data == null); + foreach (x; array) + assert (false, "there should be no elements in the array"); + } + +} // debug (UnitTest) + +// vim: set et sw=4 sts=4 : diff --git a/gc/gc.d b/gc/gc.d new file mode 100644 index 0000000..5f341f0 --- /dev/null +++ b/gc/gc.d @@ -0,0 +1,812 @@ +/** + * Naive Garbage Collector implementation. + * + * 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. + * + * 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 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. + * + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.gc; + +private: + +// Internal imports +import gc.cell: Cell, BlkAttr, op_apply_ptr_range; +import gc.list: List; +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 + +/* + * These are external functions coming from the D/Tango runtime. It's pretty + * intuitive what they do based on their names, for more details please + * refer to the functions documentation. + */ +alias void delegate(void*, void*) mark_function; +extern (C) void onOutOfMemoryError(); +extern (C) void rt_finalize(void* p, bool det=true); +extern (C) void rt_scanStaticData(mark_function mark); +extern (C) void thread_init(); +extern (C) bool thread_needLock(); +extern (C) void thread_suspendAll(); +extern (C) void thread_resumeAll(); +extern (C) void thread_scanAll(mark_function mark, void* stack_top=null); + +/** + * A range of memory that should be scanned for pointers. + * + * This object is iterable, yielding a pointer (void*) for each iteration. + */ +struct RootRange +{ + + /// Start of the memory range + void* from; + + /// End of the memory range + void* to; + + /// Iterate over a memory range applying dg to its elements + int opApply(int delegate(ref void*) dg) + { + return op_apply_ptr_range(this.from, this.to, dg); + } + +} + + +package: + + +/** + * Information on a block of memory. + * + * This is part of the GC specification, it's used for the query() method. + * + * Standards: Tango/Druntime specs + */ +struct BlkInfo +{ + + /// Base address of the block + void* base; + + /// Size of the block (this is the total capacity, not the requested size) + size_t size; + + /** + * Memory block attributes + * + * See_Also: cell.BlkAttr for possible values + */ + uint attr; + +} + + +/** + * GC implementation. + * + * This object contains the whole GC implementation. This is instantiated in + * the iface module as a global variable to provide the GC services. + * + * This implementation is designed to be extremely simple. The algorithm + * implemented is the most basic stop-the-world mark-sweep known. + * + * Memory is organized in cells. Each cell has a header where all the + * bookkeeping information is stored (like the mark bit, cell attributes, + * capacity, etc.), and the memory allocated for the requested memory itself. + * + * Two lists of cells are kept: free list and live list. + * + * The free list store cells known not to be referenced by the program. The + * live list stores cells that were referenced by the program at the end of + * the last collection (and just allocated cells). + * + * The root set is composed by several elements: + * + * $(UL + * $(LI Static data) + * $(LI Threads stack) + * $(LI Registers) + * $(LI Root pointers) + * $(LI Root ranges) + * ) + * + * Root pointers and ranges are user-defined. + * + * See_Also: + * + * $(UL + * $(LI cell.Cell for the cell header layout) + * $(LI collect() for the main collection algorithm) + * $(LI ) + * ) + * + */ +struct GC +{ + +// TODO: GC Lock + +private: + + /// List of free cells. + List free_list; + + /// List of live cells. + List live_list; + + /// Single root pointers. + DynArray!(void*) root_pointers; + + /// Single root pointers. + DynArray!(RootRange) root_ranges; + + /** + * "Flag" to indicate when the GC is disabled. + * + * This is a number because calls to enable() and disable() can be + * recursive. The number of calls to enable() should match the number of + * calls to disable(), though, if you want the GC to be effectively + * enabled again. + */ + uint disabled = 0; + + /** + * Remove the mark bit to all the live cells. + * + * This is done before starting the mark phase. + * + * See_Also: + * + * $(UL + * $(LI collect() for the main collect algorithm) + * $(LI mark_all() for details on the marking phase) + * ) + */ + void unmark() + { + foreach (cell; this.live_list) + cell.marked = false; + } + + /** + * Marks all live data (pausing all threads) + * + * This methods start marking following all the known roots: + * + * $(UL + * $(LI Static data) + * $(LI Threads stack) + * $(LI Registers) + * $(LI Root pointers) + * $(LI Root ranges) + * ) + * + * Note that the registers are pushed into the stack to get scanned. + * + * This is the complete mark phase. The algorithm roughly does: + * + * $(OL + * $(LI Push registers into the stack) + * $(LI Pause all threads (but the current one, of course)) + * $(LI Scan the static data) + * $(LI Scan all threads stack) + * $(LI Scan the root pointers and ranges) + * $(LI Resume all threads) + * $(LI Pop the registers from the stack) + * ) + * + * + * See_Also: + * + * $(UL + * $(LI collect() for the main collect algorithm) + * $(LI mark() for details on the marking algorithm) + * $(LI sweep() for details on the sweep phase) + * ) + */ + void mark_all() + { + void* stack_top; + mixin (push_registers("stack_top")); + thread_suspendAll(); + rt_scanStaticData(&mark_range); + thread_scanAll(&mark_range, stack_top); + foreach (ptr; this.root_pointers) { + this.mark(ptr); + } + foreach (range; this.root_ranges) { + this.mark_range(range.from, range.to); + } + thread_resumeAll(); + mixin (pop_registers("stack_top")); + } + + /** + * 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. + * + * This extremely inefficient on purpose. The goal of this implementation + * is simplicity, nor performance. + * + * See_Also: + * $(UL + * $(LI mark() for details on the marking algorithm) + * ) + */ + void mark_range(void* from, void* to) + { + foreach (ptr; RootRange(from, to)) + mark(ptr); + } + + /** + * Marks 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 + * in text books. + * + * Marking is done with all threads stopped. + * + * See_Also: + * $(UL + * $(LI collect() for the main collect algorithm) + * $(LI mark_all() for details on the marking phase) + * $(LI sweep() for details on the sweep phase) + * ) + */ + void mark(void* ptr) + { + Cell* cell = Cell.from_ptr(this.addrOf(ptr)); + if (cell is null) + return; + if (!cell.marked) { + cell.marked = true; + if (cell.has_pointers) { + foreach (ptr; *cell) + mark(ptr); + } + } + } + + /** + * Move unreferenced live objects to the free list (calling finalizers). + * + * This is the sweep phase. It's very simple, it just searches the live + * list and move unmarked cells to the free list. This function is in + * charge of calling finalizers too, through the rt_finalize() runtime + * function. + * + * Sweeping is done concurrently with the mutator threads. + * + * See_Also: + * $(UL + * $(LI collect() for the main collect algorithm) + * $(LI mark_all() for details on the marking phase) + * ) + */ + void sweep() + { + foreach (cell; this.live_list) { + if (!cell.marked) { + this.live_list.unlink(cell); + if (cell.has_finalizer) + rt_finalize(cell.ptr, false); + this.free_list.link(cell); + } + } + } + + +public: + + /** + * Initialize the GC. + * + * This initializes the thread library too, as requested by the + * Tango/Druntime specs. + */ + void init() + { + this.disabled = 0; + thread_init(); + } + + /** + * Terminate the GC. + * + * Finalization of unreferenced cells is not mandatory by the specs. + * This implementation guarantees that all finalizers are called, at least + * at program exit (i.e. at GC termination). + * + * The specs says that "objects referenced from the data segment never get + * collected by the GC". While this is true for this implementation, + * finalizers are called for objects referenced from the data segment at + * program exit. + * + * There could be some problems with this, in very strange situations. For + * a more complete discussion about the topic please take a look at the + * bug 2858: http://d.puremagic.com/issues/show_bug.cgi?id=2858 + */ + void term() + { + foreach (cell; this.live_list) + if (cell.has_finalizer) + rt_finalize(cell.ptr, false); + // Let the OS free the memory on exit. + } + + /** + * Enable the GC. + * + * When the GC is enabled, a collection is triggered when malloc() can't + * find room in the free list to fulfill the requested size. + * + * enable() and disable() can be called recursively. The number of calls + * to enable() should match the number of calls to disable(), though, if + * you want the GC to be effectively enabled again. + * + * See_Also: disable() + */ + void enable() + { + assert (this.disabled > 0); + this.disabled--; + } + + /** + * Disable the GC. + * + * See_Also: enable() + */ + void disable() + { + this.disabled++; + assert (this.disabled > 0); + } + + /** + * 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 + * 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. + * + * The world is stopped only for the mark phase. + * + * See_Also: + * $(UL + * $(LI mark_all() for details on the marking phase) + * $(LI sweep() for details on the sweep phase) + * ) + */ + void collect() + { + this.unmark(); + this.mark_all(); + this.sweep(); + } + + /** + * Minimize free space usage. + * + * This method returns to the OS memory that is not longer used by + * the program. Usually calling this method manually is not + * necessary, because unused cells are recycled for future + * allocations. But if there is some small part of the program that + * requires a lot of memory and it's known that it won't be used + * further, calling this can reduce the memory footprint of the program + * considerably (at the expense of some performance lost in future + * allocations). + * + * This implementation just return to the OS all the cells in the free + * list. + */ + void minimize() + { + foreach (cell; this.free_list) { + this.free_list.unlink(cell); + cstdlib.free(cell); + } + } + + /** + * Get attributes associated to the cell pointed by ptr. + * + * Attributes is a bitmap that can have theses values: + * + * $(UL + * $(LI 1: The object stored in the cell have 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)) + * ) + * + * See_Also: cell.BlkAttr, setAttr(), clrAttr() + */ + uint getAttr(void* ptr) + { + auto cell = this.live_list.find(ptr); + if (cell) + return cell.attr; + return 0; + } + + /** + * Set the attributes of the cell pointed by ptr. + * + * All bits present in attr are set, other bits are untouched. The old + * attributes are returned. + * + * See_Also: cell.BlkAttr, getAttr(), clrAttr() + */ + uint setAttr(void* ptr, uint attr) + { + auto cell = this.live_list.find(ptr); + if (cell) { + auto old = cell.attr; + cell.attr |= attr; + return cell.attr; + } + return 0; + } + + /** + * Clear the attributes of the cell pointed by ptr. + * + * All bits present in attr are cleared, other bits are untouched. The old + * attributes are returned. + * + * See_Also: cell.BlkAttr, getAttr(), setAttr() + */ + uint clrAttr(void* ptr, uint attr) + { + auto cell = this.live_list.find(ptr); + if (cell) { + auto old = cell.attr; + cell.attr &= ~attr; + return cell.attr; + } + return 0; + } + + /** + * Allocate memory. + * + * This is the main allocator of the GC. The algorithm is really + * simple. It does a first-fit search in the free list, if no free cell is + * found with enough room, it runs a collection and retry (unless the GC + * is disabled). If there is no room still, it uses C malloc to allocate + * a new cell. If all that fails, then onOutOfMemoryError() runtime + * function is called to handle the error. + * + * attr are the attributes to associate to the new cell (see getAttr() for + * details). + */ + void* malloc(size_t size, uint attr=0) + { + if (size == 0) + return null; + + // Find a free cell in the free list with enough space + auto cell = this.free_list.pop(size); + if (cell) + goto success; + + // 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; + } + + // No luck still, allocate new memory + cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof); + if (cell) + goto success; + + // No memory + onOutOfMemoryError(); + + return null; + + success: + cell.size = size; + if (cell.capacity == 0) // fresh cell + cell.capacity = size; + cell.attr = cast(BlkAttr) attr; + this.live_list.link(cell); + + return cell.ptr; + } + + /** + * Allocate memory (set memory to zero). + * + * Same as malloc() but set the allocated memory cell to zero. + */ + void* calloc(size_t size, uint attr=0) + { + void* ptr = this.malloc(size, attr); + + if (ptr is null) + onOutOfMemoryError(); + else + cstring.memset(ptr, 0, size); + + return ptr; + } + + /** + * Reallocate memory. + * + * This implementation is very simple, if size less or equals than the + * cells capacity, the cell's size is changed and the same address is + * 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(). + */ + void* realloc(void* ptr, size_t size, uint attr=0) + { + + // Undercover malloc() + if (ptr is null) + return this.malloc(size, attr); + + // Undercover free() + if (size == 0) { + this.free(ptr); + return null; + } + + auto cell = this.live_list.find(ptr); + assert (cell); + + // We have enough capacity already, just change the size + if (cell.capacity >= size) { + cell.size = size; + return cell.ptr; + } + + // 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() + + // Move cell attributes and contents + new_cell.attr = cell.attr; + cstring.memcpy(new_cell.ptr, cell.ptr, cell.size); + + // Free the old cell + this.free(cell); + + return new_cell.ptr; + } + + /** + * Attempt to in-place enlarge a memory block pointed to by ptr. + * + * The memory should be enlarged to at least min_size beyond its current + * capacity, up to a maximum of max_size. This does not attempt to move + * the memory block (like realloc() does). + * + * Returns: + * 0 if could not extend ptr, total size of entire memory block if + * successful. + */ + size_t extend(void* ptr, size_t min_size, size_t max_size) + { + assert (min_size <= max_size); + // There is no possible extension of the capacity for this + // implementation. + return 0; + } + + /** + * 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 + * implementation, we don't care about this. + * + * The actual number of bytes reserver 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) + return 0; + cell.size = size; + cell.capacity = size; + this.free_list.link(cell); + return size; + } + + /** + * Free unused memory. + * + * This method tells the GC that a cell is not longer used. The GC don't + * perform any connectivity check, if the cell was referenced by others, + * nasty things will happen (much like C/C++). + * + * Note that finalizers are not called by this method. Finalizers are + * called by the runtime when the delete operator is used, and the delete + * operator calls this method through the runtime. + */ + void free(void* ptr) + { + if (ptr is null) + return; + + auto cell = this.live_list.pop(ptr); + assert (cell); + + this.free_list.link(cell); + } + + /** + * Get the base address of an interior pointer into the GC heap. + * + * If ptr is not pointing into the GC heap null is returned. + */ + void* addrOf(void* ptr) + { + if (ptr is null) + return null; + + bool in_range(Cell* cell) + { + return ptr >= cell.ptr && ptr < (cell.ptr + cell.size); + } + + auto cell = this.live_list.find(&in_range); + if (cell) + return cell.ptr; + + return null; + } + + /** + * Return the real size (capacity) for the cell pointed 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 + * pointer). If this is not true, this method returns 0. + * + * realloc(ptr, sizeOf(ptr), attr) is guaranteed not to allocate/move + * memory. + */ + size_t sizeOf(void* ptr) + { + auto cell = this.live_list.find(ptr); + if (cell) + return cell.capacity; + return 0; + } + + /** + * Get information about the cell pointed 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 + * pointer). If this is not true, this method returns BlkInfo.init. + * + * See BlkInfo for the information provided by this method. + */ + BlkInfo query(void* ptr) + { + BlkInfo blk_info; + + auto cell = this.live_list.find(ptr); + if (cell) { + blk_info.base = cell.ptr; + blk_info.size = cell.capacity; + blk_info.attr = cell.attr; + } + + return blk_info; + } + + /** + * Add a root pointer to the root set. + * + * This method can be used to register new root to the GC heap. This is + * only needed when the user has custom memory that has pointers into the + * GC heap (for example for interfacing with C programs, which allocates + * memory using malloc() directly). + * + * See_Also: removeRoot(), addRange(), removeRange() + */ + void addRoot(void* ptr) + { + this.root_pointers.append(ptr); + } + + /** + * Add a root range to the root set. + * + * This method can be used to register new root range (a memory chunk + * that should be scanned for pointers into the GC heap). This is + * only needed when the user has custom memory that has pointers into the + * GC heap (for example for interfacing with C programs, which allocates + * memory using malloc() directly). + * + * Pointers will be scanned assuming they are aligned. + * + * See_Also: removeRange(), addRoot(), removeRoot() + */ + void addRange(void* ptr, size_t size) + { + this.root_ranges.append(RootRange(ptr, ptr + size)); + } + + /** + * 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. + * + * See_Also: addRoot(), addRange(), removeRange() + */ + void removeRoot(void* ptr) + { + this.root_pointers.remove(ptr); + } + + /** + * 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. + * + * See_Also: addRange(), addRoot(), removeRoot() + */ + void removeRange(void* ptr) + { + this.root_ranges.remove_if((ref RootRange range) { + return range.from is ptr; + }); + } + +} // struct GC + +// vim: set et sw=4 sts=4 : diff --git a/gc/iface.d b/gc/iface.d new file mode 100644 index 0000000..4b71b06 --- /dev/null +++ b/gc/iface.d @@ -0,0 +1,365 @@ +/** + * Naive Garbage Collector (Tango/Druntime compliant) C interface. + * + * This module contains the C interface of the Naive Garbage Collector + * implementation to comply with the Tango/Druntime specification. + * + * See_Also: gc module + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.iface; + +private { + + // Internal imports + import gc.gc: GC, BlkInfo; + + // Standard imports + import tango.stdc.stdlib; + + /// GC implementation instance. + GC gc; + + /// Dummy class for the GC lock. + class GCLock {} + + /** + * The GC lock. + * + * This is a ClassInfo instance because is an easy way to get an object + * instance that is not allocated in the GC heap (which is not an option + * for implementing the GC). + * + * This avoids using OS-specific mutex. + */ + ClassInfo lock; + +} + +/** + * Initialize the GC. + * + * This function initializes the thread library too. This is a requirement + * imposed by the current implementation, it's not in the D runtime specs. + * + * This method should be called before any other call to the GC. + */ +extern (C) void gc_init() +{ + lock = GCLock.classinfo; + gc.init(); +} + +/** + * Terminate the GC. + * + * After this function is called, no other GC methods should be called, except + * for gc_init(), which should initialize the GC again. + */ +extern (C) void gc_term() +{ + gc.term(); +} + +/** + * Enable the GC. + * + * When the GC is enabled, collections can happen at any time in the program. + * Different implementations can trigger a collection for different reasons. + * + * gc_enable() and gc_disable() can be called recursively. The number of calls + * to gc_enable() should match the number of calls to gc_disable(), though. + * + * If gc_disable() is called more times than gc_enable(), the GC will stay + * disabled. If gc_enable() is called more times than gc_disable(), the + * results of this function are undefined. + * + * See_Also: gc_disable() + */ +extern (C) void gc_enable() +{ + synchronized (lock) + gc.enable(); +} + +/** + * Disable the GC. + * + * See_Also: gc_enable() for details. + */ +extern (C) void gc_disable() +{ + synchronized (lock) + gc.disable(); +} + +/** + * Run a GC collection in order to free unreferenced objects. + * + * The gc_enable() and gc_disable() functions don't affect this function, the + * collection will happen even if the GC is disabled. + */ +extern (C) void gc_collect() +{ + synchronized (lock) + gc.collect(); +} + +/** + * Minimize free space usage. + * + * This function tries to minimize the programs memory footprint returning + * free memory to the OS. + * + * This should be used with care, because it would impose a performance + * penalty for further allocations. + */ +extern (C) void gc_minimize() +{ + synchronized (lock) + gc.minimize(); +} + +/** + * Get the attributes of the cell pointed by ptr. + * + * Bit significance of the uint value used for block attribute passing is as + * follows, by position: + * + * $(UL + * $(LI 1: The object stored in the cell have to be finalized) + * $(LI 2: The cell should not be scanned for pointers) + * $(LI 4: The cell should not be moved during a collection) + * $(LI 3-15: Reserved for future use by the D standard library) + * $(LI 16-31: Reserved for internal use by the garbage collector and + * compiler) + * ) + * + * See_Also: BlkAttr, gc_setAttr(), gc_clrAttr() + */ +extern (C) uint gc_getAttr(void* ptr) +{ + synchronized (lock) + return gc.getAttr(ptr); +} + +/** + * Set the attributes of the memory block pointed by ptr. + * + * All bits present in attr are set, other bits are untouched. The old + * attributes are returned. + * + * See_Also: BlkAttr, gc_getAttr(), gc_clrAttr() + */ +extern (C) uint gc_setAttr(void* ptr, uint attr) +{ + synchronized (lock) + return gc.setAttr(ptr, attr); +} + +/** + * Clear the attributes of the cell pointed by ptr. + * + * All bits present in attr are cleared, other bits are untouched. The old + * attributes are returned. + * + * See_Also: BlkAttr, gc_getAttr(), gc_setAttr() + */ +extern (C) uint gc_clrAttr(void* ptr, uint attr) +{ + synchronized (lock) + return gc.clrAttr(ptr, attr); +} + +/** + * Allocate memory with attributes attr. + * + * See_Also: BlkAttr, gc_getAttr() for attr details. + */ +extern (C) void* gc_malloc(size_t size, uint attr=0) +{ + synchronized (lock) + return gc.malloc(size, attr); +} + +/** + * Allocate memory (set memory to zero). + * + * Same as gc_malloc() but set the allocated memory block to zero. + */ +extern (C) void* gc_calloc(size_t size, uint attr=0) +{ + synchronized (lock) + return gc.calloc(size, attr); +} + +/** + * Reallocate memory. + * + * This function attempts to extend the current memory block to size. If ptr + * is null, then this function behaves exactly the same as gc_malloc(). If + * size is 0, then this function behaves exactly like gc_free(). Otherwise + * this function can resize the memory block in-place or it can move the + * memory block to another address, in which case the new memory address is + * returned (if the memory block is not moved, the return address is the same + * as ptr). + * + * attr are the same as malloc(). + */ +extern (C) void* gc_realloc(void* ptr, size_t size, uint attr=0) +{ + synchronized (lock) + return gc.realloc(ptr, size, attr); +} + +/** + * Attempt to in-place enlarge a memory block pointed to by ptr. + * + * The memory is enlarged to at least min_size beyond its current capacity, up + * to a maximum of max_size. This does not attempt to move the memory block + * (like gc_realloc() does). + * + * The total size of entire memory block is returned on success, 0 is returned + * if the memory block could not be extended. + */ +extern (C) size_t gc_extend(void* ptr, size_t min_size, size_t max_size) +{ + synchronized (lock) + return gc.extend(ptr, min_size, max_size); +} + +/** + * Reserve memory to anticipate memory allocations. + * + * This method instructs the GC to pre-allocate at least size bytes of memory + * in anticipation of future gc_malloc()s. + * + * The actual number of bytes reserver are returned, or 0 on error. + */ +extern (C) size_t gc_reserve(size_t size) +{ + synchronized (lock) + return gc.reserve(size); +} + +/** + * Free unused memory. + * + * This method tells the GC that a cell is not longer used. If the memory was + * actually still used the effects of this function is undefined (but memory + * corruption will probably happen). + * + * Note that finalizers are not called by this function. Finalizers are called + * by the runtime when the delete operator is used, and the delete operator + * calls this method through the runtime. + */ +extern (C) void gc_free(void* ptr) +{ + synchronized (lock) + gc.free(ptr); +} + +/** + * Get the base address of an interior pointer into the GC heap. + * + * If ptr is not pointing into the GC heap null is returned. + */ +extern (C) void* gc_addrOf(void* ptr) +{ + synchronized (lock) + return gc.addrOf(ptr); +} + +/** + * Return the real size (capacity) of the memory block pointed by ptr. + * + * ptr should be the base address of a heap allocated object, interior + * pointers are not supported (use gc_addrOf() if you have an interior + * pointer). If ptr is not the base address of a heap allocated object this + * function returns 0. + * + * realloc(ptr, sizeOf(ptr), attr) is guaranteed not to allocate/move memory. + */ +extern (C) size_t gc_sizeOf(void* ptr) +{ + synchronized (lock) + return gc.sizeOf(ptr); +} + +/** Get information about the memory block pointed by ptr. + * + * ptr should be the base address of a heap allocated object, interior + * pointers are not supported (use gc_addrOf() if you have an interior + * pointer). If ptr is not the base address of a heap allocated object this + * function returns a BlkInfo structure with all zeros. + * + * See BlkInfo for the information provided by this method. + */ +extern (C) BlkInfo gc_query(void* ptr) +{ + synchronized (lock) + return gc.query(ptr); +} + +/** Add a root pointer to the root set. + * + * This method can be used to register new root to the GC heap. This is only + * needed when the user has custom memory that has pointers into the GC heap + * (for example for interfacing with C programs, which allocates memory using + * malloc() directly). + * + * See_Also: gc_removeRoot(), gc_addRange(), gc_removeRange() + */ +extern (C) void gc_addRoot(void* ptr) +{ + synchronized (lock) + gc.addRoot(ptr); +} + +/** + * Add a root range to the root set. + * + * This method can be used to register new root range (a memory chunk that + * should be scanned for pointers into the GC heap). Pointers will be scanned + * assuming they are aligned. + * + * See_Also: gc_removeRange(), gc_addRoot(), gc_removeRoot() + */ +extern (C) void gc_addRange(void* ptr, size_t size) +{ + synchronized (lock) + gc.addRange(ptr, size); +} + +/** + * Remove a root pointer from the root set. + * + * ptr has to be previously registered using gc_addRoot(), in other case the + * results of this function is undefined. + * + * See_Also: gc_addRoot(), gc_addRange(), gc_removeRange() + */ +extern (C) void gc_removeRoot(void* ptr) +{ + synchronized (lock) + gc.removeRoot(ptr); +} + +/** + * Remove a root range from the root set. + * + * ptr has to be previously registered using gc_addRange(), in other case the + * results of this function is undefined. + * + * See_Also: gc_addRange(), gc_addRoot(), gc_removeRoot() + */ +extern (C) void gc_removeRange(void* ptr) +{ + synchronized (lock) + gc.removeRange(ptr); +} + +// vim: set et sw=4 sts=4 : diff --git a/gc/list.d b/gc/list.d new file mode 100644 index 0000000..7c0af0b --- /dev/null +++ b/gc/list.d @@ -0,0 +1,172 @@ +/** + * Singly linked list of Cells. + * + * This module implements a simple singly linked list of Cells to be used as + * live/free list in the Naive Garbage Collector implementation. + * + * See_Also: gc module + * Copyright: Public Domain + * License: Public Domain + * Authors: Leandro Lucarella + */ + +module gc.list; + +// Internal imports +private import gc.cell: Cell; + + +package: + +/** + * Singly linked list of Cells. + * + * This is used for live and free lists. + */ +struct List +{ + + /// First element in the list. + Cell* first = null; + + /** + * Find the first cell for which predicate(cell) is true. + * + * Returns a pointer to the cell if found, null otherwise. + */ + Cell* find(bool delegate(Cell*) predicate) + { + auto cell = this.first; + while (cell) { + if (predicate(cell)) + return cell; + cell = cell.next; + } + return null; + } + + /** + * Find the cell that holds the object pointed by ptr. + * + * Returns a pointer to the cell if found, null otherwise. + */ + Cell* find(void* ptr) + { + return this.find((Cell* cell) { return cell.ptr == ptr; }); + } + + /** + * Link a new cell into the list. + */ + void link(Cell* cell) + { + cell.next = this.first; + this.first = cell; + } + + /** + * Find and remove the first cell for which predicate(cell) is true. + * + * If no cell is found, no cell is removed. + * + * Returns a pointer to the removed cell if found, null otherwise. + */ + Cell* pop(bool delegate(Cell*) predicate) + { + Cell* prev = null; + auto cell = this.first; + while (cell) { + if (predicate(cell)) { + if (prev) + prev.next = cell.next; + else + this.first = cell.next; + return cell; + } + prev = cell; + cell = cell.next; + } + return null; + } + + /** + * Find and remove the cell that holds the object pointed by ptr. + * + * If no cell is found, no cell is removed. + * + * Returns a pointer to the removed cell if found, null otherwise. + */ + Cell* pop(void* ptr) + { + return this.pop((Cell* cell) { return cell.ptr == ptr; }); + } + + /** + * Find and remove the first cell with a capacity of at least min_size. + * + * If no cell is found, no cell is removed. + * + * Returns a pointer to the removed cell if found, null otherwise. + */ + Cell* pop(size_t min_size) + { + return this.pop((Cell* cell) { return cell.capacity >= min_size; }); + } + + /** + * Remove a cell from the list. + * + * If the cell was not linked into the list, this method has no effect. + */ + void unlink(Cell* cell) + { + this.pop((Cell* cell2) { return cell is cell2; }); + } + + /** + * Iterate over the cells in the list. + * + * unlink()ing cells from the list while iterating is supported, but + * link()ing may not work. + */ + int opApply(int delegate(ref Cell*) dg) + { + int result = 0; + auto cell = this.first; + while (cell) { + // this is necessary to allow removing a node while iterating + auto next = cell.next; + result = dg(cell); + if (result) + break; + cell = next; + } + return result; + } + +} + +debug (UnitTest) +{ + +private: + + import tango.stdc.stdlib: malloc; + + unittest // List + { + List l; + assert (l.first == null); + assert (l.find(cast(void*) null) is null); + assert (l.find(cast(void*) &l) is null); + Cell[5] cells; + foreach (ref c; cells) + l.link(&c); + size_t i = 5; + foreach (c; l) + assert (c is &cells[--i]); + } + +} // debug (UnitTest) + +// vim: set et sw=4 sts=4 : diff --git a/iface.d b/iface.d deleted file mode 100644 index ddc5953..0000000 --- a/iface.d +++ /dev/null @@ -1,175 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module iface; - -private { - - import gc: NaiveGC, BlkInfo; - - import tango.stdc.stdlib; - debug (gc_naive_iface) import tango.stdc.stdio; - - NaiveGC gc; - - class GCLock {} // TODO - -} - -extern (C) void gc_init() -{ - debug (gc_naive_iface) printf("gc_init()\n"); - gc.init(); -} - -extern (C) void gc_term() -{ - debug (gc_naive_iface) printf("gc_term()\n"); - gc.term(); -} - -extern (C) void gc_enable() -{ - debug (gc_naive_iface) printf("gc_enable()\n"); - gc.enable(); -} - -extern (C) void gc_disable() -{ - debug (gc_naive_iface) printf("gc_disable()\n"); - gc.disable(); -} - -extern (C) void gc_collect() -{ - debug (gc_naive_iface) printf("gc_collect()\n"); - gc.collect(); -} - -extern (C) void gc_minimize() -{ - debug (gc_naive_iface) printf("gc_minimize()\n"); - gc.minimize(); -} - -extern (C) uint gc_getAttr(void* ptr) -{ - debug (gc_naive_iface) printf("gc_getAttr(%p)\n", ptr); - return gc.getAttr(ptr); -} - -// return the old value -extern (C) uint gc_setAttr(void* ptr, uint attr) -{ - debug (gc_naive_iface) printf("gc_setAttr(%p, %u)\n", ptr, attr); - return gc.setAttr(ptr, attr); -} - -extern (C) uint gc_clrAttr(void* ptr, uint attr) -{ - debug (gc_naive_iface) printf("gc_clrAttr(%p, %u)\n", ptr, attr); - return gc.clrAttr(ptr, attr); -} - -extern (C) void* gc_malloc(size_t size, uint attr=0) -{ - debug (gc_naive_iface) printf("gc_malloc(%u, %u)\n", size, attr); - auto p = gc.malloc(size, attr); - debug (gc_naive_iface) printf("gc_malloc() -> %p\n", p); - return p; -} - -extern (C) void* gc_calloc(size_t size, uint attr=0) -{ - debug (gc_naive_iface) printf("gc_calloc(%u, %u)\n", size, attr); - return gc.calloc(size, attr); -} - -extern (C) void* gc_realloc(void* ptr, size_t size, uint attr=0) -{ - debug (gc_naive_iface) printf("gc_realloc(%p, %u, %u)\n", ptr, size, attr); - return gc.realloc(ptr, size, attr); -} - -extern (C) size_t gc_extend(void* ptr, size_t min_size, size_t max_size) -{ - debug (gc_naive_iface) - printf("gc_extend(%p, %u, %u)\n", ptr, min_size, max_size); - return gc.extend(ptr, min_size, max_size); -} - -extern (C) size_t gc_reserve(size_t size) -{ - debug (gc_naive_iface) printf("gc_reserve(%u)\n", size); - return gc.reserve(size); -} - -extern (C) void gc_free(void* ptr) -{ - debug (gc_naive_iface) printf("gc_free(%p)\n", ptr); - gc.free(ptr); -} - -extern (C) void* gc_addrOf(void* ptr) -{ - debug (gc_naive_iface) printf("gc_addrOf(%p)\n", ptr); - return gc.addrOf(ptr); -} - -// TODO: acepta un address que no sea el base? -// es valido aceptar un ptr que no pertenezca al heap? -extern (C) size_t gc_sizeOf(void* ptr) -{ - debug (gc_naive_iface) printf("gc_sizeOf(%p)\n", ptr); - return gc.sizeOf(ptr); -} - -// TODO: acepta un address que no sea el base? -// es valido aceptar un ptr que no pertenezca al heap? -extern (C) BlkInfo gc_query(void* ptr) -{ - debug (gc_naive_iface) printf("gc_query(%p)\n", ptr); - return gc.query(ptr); -} - -extern (C) void gc_addRoot(void* ptr) -{ - debug (gc_naive_iface) printf("gc_addRoot(%p)\n", ptr); - gc.addRoot(ptr); -} - -extern (C) void gc_addRange(void* ptr, size_t size) -{ - debug (gc_naive_iface) printf("gc_addRange(%p, %u)\n", ptr, size); - gc.addRange(ptr, size); -} - -extern (C) void gc_removeRoot(void* ptr) -{ - debug (gc_naive_iface) printf("gc_removeRoot(%p)\n", ptr); - gc.removeRoot(ptr); -} - -extern (C) void gc_removeRange(void* ptr) -{ - debug (gc_naive_iface) printf("gc_removeRange(%p)\n", ptr); - gc.removeRange(ptr); -} - -// vim: set et sw=4 sts=4 : diff --git a/ldc.mak b/ldc.mak index ee300f4..1124806 100644 --- a/ldc.mak +++ b/ldc.mak @@ -1,4 +1,4 @@ -# Makefile to build the garbage collector D library for Posix +# Makefile to build the garbage collector D library for LDC # Designed to work with GNU make # Targets: # make @@ -10,8 +10,10 @@ # make clean # Delete unneeded files created by build process -LIB_TARGET=libtango-gc-naive.a -LIB_MASK=libtango-gc-naive*.a +LIB_TARGET_BC=libtango-gc-naive-bc.a +LIB_TARGET_NATIVE=libtango-gc-naive.a +LIB_TARGET_SHARED=libtango-gc-naive-shared.so +LIB_MASK=libtango-gc-naive*.* CP=cp -f RM=rm -f @@ -23,16 +25,20 @@ ADD_DFLAGS= #CFLAGS=-O3 $(ADD_CFLAGS) CFLAGS=$(ADD_CFLAGS) -#DFLAGS=-release -O3 -inline -w $(ADD_DFLAGS) -DFLAGS=$(ADD_DFLAGS) +#DFLAGS=-release -O3 -inline -w -nofloat $(ADD_DFLAGS) +DFLAGS=-w -disable-invariants $(ADD_DFLAGS) -#TFLAGS=-O3 -inline $(ADD_DFLAGS) -TFLAGS=$(ADD_DFLAGS) +#TFLAGS=-O3 -inline -w -nofloat $(ADD_DFLAGS) +TFLAGS=-w -disable-invariants $(ADD_DFLAGS) DOCFLAGS=-version=DDoc CC=gcc LC=llvm-ar rsv +LCC=llc +LLINK=llvm-link +CLC=ar rsv +LD=llvm-ld DC=ldc LIB_DEST=.. @@ -51,27 +57,36 @@ LIB_DEST=.. .cpp.o: g++ -c $(CFLAGS) $< -o$@ -.d.bc: - $(DC) -c $(DFLAGS) $< -of$@ +.d.o: + $(DC) -c $(DFLAGS) $< -of$@ -output-bc .d.html: $(DC) -c -o- $(DOCFLAGS) -Df$*.html $< # $(DC) -c -o- $(DOCFLAGS) -Df$*.html dmd.ddoc $< -targets : lib doc -all : lib doc -lib : naive.lib +targets : lib sharedlib doc +all : lib sharedlib doc +lib : naive.lib naive.nlib +sharedlib : naive.sharedlib doc : naive.doc ###################################################### -ALL_OBJS= \ - gc.bc \ - list.bc \ - cell.d \ - dynarray.d \ - arch.d \ - iface.d +ALL_OBJS_BC= \ + gc/iface.bc \ + gc/gc.bc \ + gc/arch.bc \ + gc/list.bc \ + gc/cell.bc \ + gc/dynarray.bc + +ALL_OBJS_O= \ + gc/iface.o \ + gc/gc.o \ + gc/arch.o \ + gc/list.o \ + gc/cell.o \ + gc/dynarray.o ###################################################### @@ -79,11 +94,23 @@ ALL_DOCS= ###################################################### -naive.lib : $(LIB_TARGET) +naive.lib : $(LIB_TARGET_BC) +naive.nlib : $(LIB_TARGET_NATIVE) +naive.sharedlib : $(LIB_TARGET_SHARED) -$(LIB_TARGET) : $(ALL_OBJS) +$(LIB_TARGET_BC) : $(ALL_OBJS_O) $(RM) $@ - $(LC) $@ $(ALL_OBJS) + $(LC) $@ $(ALL_OBJS_BC) + + +$(LIB_TARGET_NATIVE) : $(ALL_OBJS_O) + $(RM) $@ + $(CLC) $@ $(ALL_OBJS_O) + + +$(LIB_TARGET_SHARED) : $(ALL_OBJS_O) + $(RM) $@ + $(CC) -shared -o $@ $(ALL_OBJS_O) naive.doc : $(ALL_DOCS) echo No documentation available. @@ -92,8 +119,11 @@ naive.doc : $(ALL_DOCS) clean : find . -name "*.di" | xargs $(RM) - $(RM) $(ALL_OBJS) + $(RM) $(ALL_OBJS_BC) + $(RM) $(ALL_OBJS_O) $(RM) $(ALL_DOCS) + +clean-all: clean $(RM) $(LIB_MASK) install : diff --git a/list.d b/list.d deleted file mode 100644 index 6b45808..0000000 --- a/list.d +++ /dev/null @@ -1,120 +0,0 @@ -/** - * This module contains a minimal garbage collector implementation according to - * Tango requirements. This library is mostly intended to serve as an example, - * but it is usable in applications which do not rely on a garbage collector - * to clean up memory (ie. when dynamic array resizing is not used, and all - * memory allocated with 'new' is freed deterministically with 'delete'). - * - * Please note that block attribute data must be tracked, or at a minimum, the - * FINALIZE bit must be tracked for any allocated memory block because calling - * rt_finalize on a non-object block can result in an access violation. In the - * allocator below, this tracking is done via a leading uint bitmask. A real - * allocator may do better to store this data separately, similar to the basic - * GC normally used by Tango. - * - * Copyright: Public Domain - * License: BOLA - * Authors: Leandro Lucarella - */ - -module list; - -private import cell: Cell; -private import alloc: mem_free; - -struct List -{ - - Cell* first; - - Cell* find(bool delegate(Cell*) predicate) - { - auto cell = this.first; - while (cell) { - if (predicate(cell)) - return cell; - cell = cell.next; - } - return null; - } - - Cell* find(void* ptr) - { - return this.find((Cell* cell) { return cell.ptr == ptr; }); - } - - void link(Cell* cell) - { - cell.next = this.first; - this.first = cell; - } - - Cell* pop(bool delegate(Cell*) predicate) - { - Cell* prev = null; - auto cell = this.first; - while (cell) { - if (predicate(cell)) { - if (prev) - prev.next = cell.next; - else - this.first = cell.next; - return cell; - } - prev = cell; - cell = cell.next; - } - return null; - } - - Cell* pop(void* ptr) - { - return this.pop((Cell* cell) { return cell.ptr == ptr; }); - } - - Cell* pop(size_t min_size) - { - return this.pop((Cell* cell) { return cell.capacity >= min_size; }); - } - - void unlink(Cell* cell) - { - this.pop((Cell* cell2) { return cell is cell2; }); - } - - void swap(Cell* old_cell, Cell* new_cell) - { - Cell* prev = null; - auto cell = this.first; - while (cell) { - if (cell is old_cell) { - new_cell.next = cell.next; - if (prev) - prev.next = new_cell; - else - this.first = new_cell; - return; - } - prev = cell; - cell = cell.next; - } - } - - int opApply(int delegate(ref Cell*) dg) - { - int result = 0; - auto cell = this.first; - while (cell) { - // this is necessary to allow removing node while iterating - auto next = cell.next; - result = dg(cell); - if (result) - break; - cell = next; - } - return result; - } - -} - -// vim: set et sw=4 sts=4 : diff --git a/posix.mak b/posix.mak new file mode 100644 index 0000000..cf8cd13 --- /dev/null +++ b/posix.mak @@ -0,0 +1,127 @@ +# Makefile to build the garbage collector D library for Posix +# Designed to work with GNU make +# Targets: +# make +# Same as make all +# make lib +# Build the garbage collector library +# make doc +# Generate documentation +# make clean +# Delete unneeded files created by build process + +LIB_BASE=libtango-gc-naive +LIB_BUILD= +LIB_TARGET=$(LIB_BASE)$(LIB_BUILD).a +LIB_MASK=$(LIB_BASE)*.a + +CP=cp -f +RM=rm -f +MD=mkdir -p + +ADD_CFLAGS= +ADD_DFLAGS= +SYSTEM_VERSION= + +CFLAGS_RELEASE=-O $(ADD_CFLAGS) +CFLAGS_DEBUG=-g $(ADD_CFLAGS) +DFLAGS_RELEASE=-release -version=Tango -O -inline -w -nofloat $(SYSTEM_VERSION) $(ADD_DFLAGS) -I../../common -I../../.. +DFLAGS_DEBUG=-g -w -nofloat -version=Tango$(SYSTEM_VERSION) $(ADD_DFLAGS) -I../../common -I../../.. +TFLAGS_RELEASE=-O -inline -w -nofloat $(SYSTEM_VERSION) $(ADD_DFLAGS) +TFLAGS_DEBUG=-g -w -nofloat $(SYSTEM_VERSION) $(ADD_DFLAGS) +DOCFLAGS=-version=DDoc $(SYSTEM_VERSION) + +ifeq ($(VERSION),debug) +CFLAGS=$(CFLAGS_DEBUG) +DFLAGS=$(DFLAGS_DEBUG) +TFLAGS=$(TFLAGS_DEBUG) +else +CFLAGS=$(CFLAGS_RELEASE) +DFLAGS=$(DFLAGS_RELEASE) +TFLAGS=$(TFLAGS_RELEASE) +endif + +CC=gcc +LC=$(AR) -qsv +DC=dmd + +LIB_DEST=.. + +.SUFFIXES: .s .S .c .cpp .d .html .o +.PHONY : lib lib-release lib-debug unittest all doc clean install clean-all + +.s.o: + $(CC) -c $(CFLAGS) $< -o$@ + +.S.o: + $(CC) -c $(CFLAGS) $< -o$@ + +.c.o: + $(CC) -c $(CFLAGS) $< -o$@ + +.cpp.o: + g++ -c $(CFLAGS) $< -o$@ + +.d.o: + $(DC) -c $(DFLAGS) $< -of$@ + +.d.html: + $(DC) -c -o- $(DOCFLAGS) -Df$*.html $< +# $(DC) -c -o- $(DOCFLAGS) -Df$*.html dmd.ddoc $< + +targets : lib doc +all : lib-release lib-debug doc + +###################################################### + +ALL_OBJS= \ + gc/iface.o \ + gc/gc.o \ + gc/arch.o \ + gc/list.o \ + gc/cell.o \ + gc/dynarray.o + +###################################################### + +ALL_DOCS= + +###################################################### +unittest : + make -fposix.mak clean DC="$(DC)" LIB_BUILD="" VERSION="$(VERSION)" + make -fposix.mak lib DC="$(DC)" LIB_BUILD="" VERSION="$(VERSION)" \ + ADD_CFLAGS="$(ADD_CFLAGS)" ADD_DFLAGS="$(ADD_DFLAGS) -unittest -debug=UnitTest" \ + SYSTEM_VERSION="$(SYSTEM_VERSION)" +lib-release : + make -fposix.mak clean DC="$(DC)" LIB_BUILD="" VERSION="$(VERSION)" + make -fposix.mak DC="$(DC)" LIB_BUILD="" VERSION=release lib \ + ADD_CFLAGS="$(ADD_CFLAGS)" ADD_DFLAGS="$(ADD_DFLAGS)" SYSTEM_VERSION="$(SYSTEM_VERSION)" +lib-debug : + make -fposix.mak clean DC="$(DC)" LIB_BUILD="" VERSION="$(VERSION)" + make -fposix.mak DC="$(DC)" LIB_BUILD="-d" VERSION=debug lib \ + ADD_CFLAGS="$(ADD_CFLAGS)" ADD_DFLAGS="$(ADD_DFLAGS)" SYSTEM_VERSION="$(SYSTEM_VERSION)" + +###################################################### + +lib : $(LIB_TARGET) + +$(LIB_TARGET) : $(ALL_OBJS) + $(RM) $@ + $(LC) $@ $(ALL_OBJS) + +doc : $(ALL_DOCS) + echo No documentation available. + +###################################################### + +clean : + find . -name "*.di" | xargs $(RM) + $(RM) $(ALL_OBJS) + $(RM) $(ALL_DOCS) + +clean-all : clean + $(RM) $(LIB_MASK) + +install : + $(MD) $(LIB_DEST) + $(CP) $(LIB_MASK) $(LIB_DEST)/. diff --git a/win32.mak b/win32.mak new file mode 100644 index 0000000..7e50af2 --- /dev/null +++ b/win32.mak @@ -0,0 +1,102 @@ +# Makefile to build the garbage collector D library for Win32 +# Designed to work with DigitalMars make +# Targets: +# make +# Same as make all +# make lib +# Build the garbage collector library +# make doc +# Generate documentation +# make clean +# Delete unneeded files created by build process + +LIB_BASE=tango-gc-naive +LIB_BUILD= +LIB_TARGET=$(LIB_BASE)$(LIB_BUILD).lib +LIB_MASK=$(LIB_BASE)*.lib + +CP=xcopy /y +RM=del /f +MD=mkdir + +ADD_CFLAGS= +ADD_DFLAGS= + +CFLAGS_RELEASE=-mn -6 -r $(ADD_CFLAGS) +CFLAGS_DEBUG=-g -mn -6 -r $(ADD_CFLAGS) +DFLAGS_RELEASE=-release -O -inline -w -nofloat -I. -I../shared -I../../.. $(ADD_DFLAGS) +DFLAGS_DEBUG=-g -w -nofloat -I. -I../shared -I../../.. $(ADD_DFLAGS) +TFLAGS_RELEASE=-O -inline -w -nofloat $(ADD_DFLAGS) +TFLAGS_DEBUG=-g -w -nofloat $(ADD_DFLAGS) + +CFLAGS=$(CFLAGS_RELEASE) +DFLAGS=$(DFLAGS_RELEASE) +TFLAGS=$(TFLAGS_RELEASE) + +DOCFLAGS=-version=DDoc + +CC=dmc +LC=lib +DC=dmd + +LIB_DEST=.. + +.DEFAULT: .asm .c .cpp .d .html .obj + +.asm.obj: + $(CC) -c $< + +.c.obj: + $(CC) -c $(CFLAGS) $< -o$@ + +.cpp.obj: + $(CC) -c $(CFLAGS) $< -o$@ + +.d.obj: + $(DC) -c $(DFLAGS) $< -of$@ + +.d.html: + $(DC) -c -o- $(DOCFLAGS) -Df$*.html $< +# $(DC) -c -o- $(DOCFLAGS) -Df$*.html dmd.ddoc $< + +targets : lib doc +all : lib doc +lib : naive.lib +doc : naive.doc + +###################################################### + +ALL_OBJS= \ + gc/iface.obj \ + gc/gc.obj \ + gc/arch.obj \ + gc/list.obj \ + gc/cell.obj \ + gc/dynarray.obj + +###################################################### + +ALL_DOCS= + +###################################################### + +naive.lib : $(LIB_TARGET) + +$(LIB_TARGET) : $(ALL_OBJS) + $(RM) $@ + $(LC) -c -n $@ $(ALL_OBJS) + +naive.doc : $(ALL_DOCS) + @echo No documentation available. + +###################################################### + +clean : + $(RM) /s *.di + $(RM) $(ALL_OBJS) + $(RM) $(ALL_DOCS) + $(RM) $(LIB_MASK) + +install : + $(MD) $(LIB_DEST) + $(CP) $(LIB_MASK) $(LIB_DEST)\.