From 9cbaa4a3180163f6966de2ee31bcef84df5bfdb3 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sat, 18 Apr 2009 16:53:22 -0300 Subject: [PATCH] Initial import All is pretty functional. The alloc module will probably have to go (we don't want that kind of complexity here). --- alloc.d | 124 ++++++++++++++ arch.d | 159 ++++++++++++++++++ cell.d | 87 ++++++++++ dynarray.d | 89 ++++++++++ gc.d | 480 +++++++++++++++++++++++++++++++++++++++++++++++++++++ iface.d | 175 +++++++++++++++++++ ldc.mak | 101 +++++++++++ list.d | 120 ++++++++++++++ 8 files changed, 1335 insertions(+) create mode 100644 alloc.d create mode 100644 arch.d create mode 100644 cell.d create mode 100644 dynarray.d create mode 100644 gc.d create mode 100644 iface.d create mode 100644 ldc.mak create mode 100644 list.d diff --git a/alloc.d b/alloc.d new file mode 100644 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 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 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 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 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 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 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 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 : -- 2.43.0