--- /dev/null
+*.bc
+*.o
+libtango-gc-naive.a
+++ /dev/null
-/**
- * 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 :
+++ /dev/null
-/**
- * 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 :
+++ /dev/null
-/**
- * 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 :
+++ /dev/null
-/**
- * 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 :
+++ /dev/null
-/**
- * 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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
--- /dev/null
+/**
+ * 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 <llucax@gmail.com>
+ */
+
+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 :
+++ /dev/null
-/**
- * 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 :
-# 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
# 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
#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=..
.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
######################################################
######################################################
-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.
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 :
+++ /dev/null
-/**
- * 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 :
--- /dev/null
+# 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)/.
--- /dev/null
+# 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)\.
projects / software / dgc / naive.git / commitdiff