Initial import

All is pretty functional. The alloc module will probably have to go (we
don't want that kind of complexity here).

diff --git a/alloc.d b/alloc.d
new file mode 100644 (file)
index 0000000..19aceaa
--- /dev/null
+++ b/alloc.d
@@ -0,0 +1,124 @@
+/**
+ * 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
new file mode 100644 (file)
index 0000000..fbfa40f
--- /dev/null
+++ b/arch.d
@@ -0,0 +1,159 @@
+/**
+ * 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
new file mode 100644 (file)
index 0000000..5c26205
--- /dev/null
+++ b/cell.d
@@ -0,0 +1,87 @@
+/**
+ * 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
new file mode 100644 (file)
index 0000000..b7e5059
--- /dev/null
+++ b/dynarray.d
@@ -0,0 +1,89 @@
+/**
+ * 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
new file mode 100644 (file)
index 0000000..67b2d56
--- /dev/null
+++ b/gc.d
@@ -0,0 +1,480 @@
+/**
+ * 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/iface.d b/iface.d
new file mode 100644 (file)
index 0000000..ddc5953
--- /dev/null
+++ b/iface.d
@@ -0,0 +1,175 @@
+/**
+ * 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
new file mode 100644 (file)
index 0000000..ee300f4
--- /dev/null
+++ b/ldc.mak
@@ -0,0 +1,101 @@
+# 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_TARGET=libtango-gc-naive.a
+LIB_MASK=libtango-gc-naive*.a
+
+CP=cp -f
+RM=rm -f
+MD=mkdir -p
+
+ADD_CFLAGS=
+ADD_DFLAGS=
+
+#CFLAGS=-O3 $(ADD_CFLAGS)
+CFLAGS=$(ADD_CFLAGS)
+
+#DFLAGS=-release -O3 -inline -w $(ADD_DFLAGS)
+DFLAGS=$(ADD_DFLAGS)
+
+#TFLAGS=-O3 -inline $(ADD_DFLAGS)
+TFLAGS=$(ADD_DFLAGS)
+
+DOCFLAGS=-version=DDoc
+
+CC=gcc
+LC=llvm-ar rsv
+DC=ldc
+
+LIB_DEST=..
+
+.SUFFIXES: .s .S .c .cpp .d .html .o .bc
+
+.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.bc:
+       $(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.bc \
+    list.bc \
+    cell.d \
+    dynarray.d \
+    arch.d \
+    iface.d
+
+######################################################
+
+ALL_DOCS=
+
+######################################################
+
+naive.lib : $(LIB_TARGET)
+
+$(LIB_TARGET) : $(ALL_OBJS)
+       $(RM) $@
+       $(LC) $@ $(ALL_OBJS)
+
+naive.doc : $(ALL_DOCS)
+       echo No documentation available.
+
+######################################################
+
+clean :
+       find . -name "*.di" | xargs $(RM)
+       $(RM) $(ALL_OBJS)
+       $(RM) $(ALL_DOCS)
+       $(RM) $(LIB_MASK)
+
+install :
+       $(MD) $(LIB_DEST)
+       $(CP) $(LIB_MASK) $(LIB_DEST)/.

diff --git a/list.d b/list.d
new file mode 100644 (file)
index 0000000..6b45808
--- /dev/null
+++ b/list.d
@@ -0,0 +1,120 @@
+/**
+ * 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 :