2 * Naive Garbage Collector implementation.
4 * This module implements a Naive Garbage Collector. The idea behind this
5 * implementation is to document all the bookkeeping and considerations that
6 * have to be taken in order to implement a garbage collector for D.
8 * The garbage collector algorithm itself is extremely simple to make it
9 * easier to focus on the specifics of D. A completely naive mark and sweep
10 * algorithm is used, with a recursive mark phase. The code is extremely
11 * inefficient in order to keep it clean, and easy to read and understand.
13 * The implementation is split in several modules to ease the reading even
14 * more. All architecture/compiler specific code is done in the arch module,
15 * in order to avoid confusing version statements all over the places. The
16 * cell module has all the code related to the memory cells header. dynarray
17 * is another support module which holds the implementation of a simple
18 * dynamic array used to store root pointers and ranges. The list module holds
19 * a simple singly linked list (of cells) implementation to store the live and
20 * free lists. Finally, the iface module is the one with the C interface to
21 * comply with the Tango/Druntime GC specification.
23 * Copyright: Public Domain
24 * License: Public Domain
25 * Authors: Leandro Lucarella <llucax@gmail.com>
33 import gc.cell: Cell, BlkAttr, op_apply_ptr_range;
35 import gc.dynarray: DynArray;
36 import gc.arch: push_registers, pop_registers;
39 import cstring = tango.stdc.string;
44 * These are external functions coming from the D/Tango runtime. It's pretty
45 * intuitive what they do based on their names, for more details please
46 * refer to the functions documentation.
48 alias void delegate(void*, void*) mark_function;
49 extern (C) void onOutOfMemoryError();
50 extern (C) void rt_finalize(void* p, bool det=true);
51 extern (C) void rt_scanStaticData(mark_function mark);
52 extern (C) void thread_init();
53 extern (C) bool thread_needLock();
54 extern (C) void thread_suspendAll();
55 extern (C) void thread_resumeAll();
56 extern (C) void thread_scanAll(mark_function mark, void* stack_top=null);
59 * A range of memory that should be scanned for pointers.
61 * This object is iterable, yielding a pointer (void*) for each iteration.
66 /// Beginning of the memory range
69 /// End of the memory range
72 /// Iterate over a memory range applying dg to its elements
73 int opApply(int delegate(ref void*) dg)
75 return op_apply_ptr_range(this.from, this.to, dg);
85 * Information on a block of memory.
87 * This is part of the GC specification, it's used for the query() method.
89 * Standards: Tango/Druntime specs
94 /// Base address of the block
97 /// Size of the block (this is the total capacity, not the requested size)
101 * Memory block attributes
103 * See_Also: cell.BlkAttr for possible values
113 * This object contains the whole GC implementation. This is instantiated in
114 * the iface module as a global variable to provide the GC services.
116 * This implementation is designed to be extremely simple. The algorithm
117 * implemented is the most basic stop-the-world mark-sweep known.
119 * Memory is organized in cells. Each cell has a header where all the
120 * bookkeeping information is stored (like the mark bit, cell attributes,
121 * capacity, etc.), and the memory allocated for the requested memory itself.
123 * Two lists of cells are kept: free list and live list.
125 * The free list store cells known not to be referenced by the program. The
126 * live list stores cells that were referenced by the program at the end of
127 * the last collection (and just allocated cells).
129 * The root set is composed by several elements:
133 * $(LI Threads stack)
135 * $(LI Root pointers)
139 * Root pointers and ranges are user-defined.
144 * $(LI cell.Cell for the cell header layout)
145 * $(LI collect() for the main collection algorithm)
155 /// List of free cells.
158 /// List of live cells.
161 /// Single root pointers.
162 DynArray!(void*) root_pointers;
165 DynArray!(RootRange) root_ranges;
168 * "Flag" to indicate when the GC is disabled.
170 * This is a number because calls to enable() and disable() can be
171 * recursive. The number of calls to enable() should match the number of
172 * calls to disable(), though, if you want the GC to be effectively
178 * Remove the mark bit to all the live cells.
180 * This is done before starting the mark phase.
185 * $(LI collect() for the main collect algorithm)
186 * $(LI mark_all() for details on the marking phase)
191 foreach (cell; this.live_list)
196 * Mark all live data (pausing all threads)
198 * This methods start marking following all the known roots:
202 * $(LI Threads stack)
204 * $(LI Root pointers)
208 * Note that the registers are pushed into the stack to get scanned.
210 * This is the complete mark phase. The algorithm roughly does:
213 * $(LI Push registers into the stack)
214 * $(LI Pause all threads (but the current one, of course))
215 * $(LI Scan the static data)
216 * $(LI Scan all threads stack)
217 * $(LI Scan the root pointers and ranges)
218 * $(LI Resume all threads)
219 * $(LI Pop the registers from the stack)
226 * $(LI collect() for the main collect algorithm)
227 * $(LI mark() for details on the marking algorithm)
228 * $(LI sweep() for details on the sweep phase)
234 mixin (push_registers("stack_top"));
236 rt_scanStaticData(&mark_range);
237 thread_scanAll(&mark_range, stack_top);
238 foreach (ptr; this.root_pointers) {
241 foreach (range; this.root_ranges) {
242 this.mark_range(range.from, range.to);
245 mixin (pop_registers("stack_top"));
249 * Wrapper for mark() over a range, needed by some runtime functions.
251 * This function is used as a delegate to be passed to rt_scanStaticData()
252 * and thread_scanAll(), because they expect a function taking 2 pointers.
254 * This extremely inefficient on purpose. The goal of this implementation
255 * is simplicity, nor performance.
259 * $(LI mark() for details on the marking algorithm)
262 void mark_range(void* from, void* to)
264 foreach (ptr; RootRange(from, to))
269 * Mark all cells accessible from a pointer.
271 * This is the mark algorithm itself. It's recursive and dumb as a log. No
272 * care is taken in regards to stack overflows. This is the first example
275 * Marking is done with all threads stopped.
279 * $(LI collect() for the main collect algorithm)
280 * $(LI mark_all() for details on the marking phase)
281 * $(LI sweep() for details on the sweep phase)
286 Cell* cell = Cell.from_ptr(this.addrOf(ptr));
291 if (cell.has_pointers) {
299 * Move unreferenced live objects to the free list (calling finalizers).
301 * This is the sweep phase. It's very simple, it just searches the live
302 * list and move unmarked cells to the free list. This function is in
303 * charge of calling finalizers too, through the rt_finalize() runtime
306 * Sweeping is done concurrently with the mutator threads.
310 * $(LI collect() for the main collect algorithm)
311 * $(LI mark_all() for details on the marking phase)
316 foreach (cell; this.live_list) {
318 this.live_list.unlink(cell);
319 if (cell.has_finalizer)
320 rt_finalize(cell.ptr, false);
321 this.free_list.link(cell);
332 * This initializes the thread library too, as requested by the
333 * Tango/Druntime specs.
344 * Finalization of unreferenced cells is not mandatory by the specs.
345 * This implementation guarantees that all finalizers are called, at least
346 * at program exit (i.e. at GC termination).
348 * The specs says that "objects referenced from the data segment never get
349 * collected by the GC". While this is true for this implementation,
350 * finalizers are called for objects referenced from the data segment at
353 * There could be some problems with this, in very strange situations. For
354 * a more complete discussion about the topic please take a look at the
355 * bug 2858: http://d.puremagic.com/issues/show_bug.cgi?id=2858
359 foreach (cell; this.live_list)
360 if (cell.has_finalizer)
361 rt_finalize(cell.ptr, false);
362 // Let the OS free the memory on exit.
368 * When the GC is enabled, a collection is triggered when malloc() can't
369 * find room in the free list to fulfill the requested size.
371 * enable() and disable() can be called recursively. The number of calls
372 * to enable() should match the number of calls to disable(), though, if
373 * you want the GC to be effectively enabled again.
375 * See_Also: disable()
379 assert (this.disabled > 0);
391 assert (this.disabled > 0);
395 * Run a GC collection in order to find unreferenced objects.
397 * This is the simplest stop-the-world mark-sweep algorithm ever. It first
398 * removes the mark bit from all the live cells, then it marks the cells
399 * that are reachable through the root set (static data, stack, registers
400 * and custom root), and finally sweeps the live list looking for unmarked
403 * The world is stopped only for the mark phase.
407 * $(LI mark_all() for details on the marking phase)
408 * $(LI sweep() for details on the sweep phase)
419 * Minimize free space usage.
421 * This method returns to the OS memory that is not longer used by
422 * the program. Usually calling this method manually is not
423 * necessary, because unused cells are recycled for future
424 * allocations. But if there is some small part of the program that
425 * requires a lot of memory and it's known that it won't be used
426 * further, calling this can reduce the memory footprint of the program
427 * considerably (at the expense of some performance lost in future
430 * This implementation just return to the OS all the cells in the free
435 foreach (cell; this.free_list) {
436 this.free_list.unlink(cell);
442 * Get attributes associated to the cell pointed by ptr.
444 * Attributes is a bitmap that can have these values:
447 * $(LI 1: The object stored in the cell has to be finalized)
448 * $(LI 2: The cell should not be scanned for pointers)
449 * $(LI 4: The cell should not be moved during a collection
453 * See_Also: cell.BlkAttr, setAttr(), clrAttr()
455 uint getAttr(void* ptr)
457 auto cell = this.live_list.find(ptr);
464 * Set the attributes of the cell pointed by ptr.
466 * All bits present in attr are set, other bits are untouched. The old
467 * attributes are returned.
469 * See_Also: cell.BlkAttr, getAttr(), clrAttr()
471 uint setAttr(void* ptr, uint attr)
473 auto cell = this.live_list.find(ptr);
475 auto old = cell.attr;
483 * Clear the attributes of the cell pointed by ptr.
485 * All bits present in attr are cleared, other bits are untouched. The old
486 * attributes are returned.
488 * See_Also: cell.BlkAttr, getAttr(), setAttr()
490 uint clrAttr(void* ptr, uint attr)
492 auto cell = this.live_list.find(ptr);
494 auto old = cell.attr;
504 * This is the main allocator of the GC. The algorithm is really
505 * simple. It does a first-fit search in the free list, if no free cell is
506 * found with enough room, it runs a collection and retry (unless the GC
507 * is disabled). If there is no room still, it uses C malloc to allocate
508 * a new cell. If all that fails, then onOutOfMemoryError() runtime
509 * function is called to handle the error.
511 * attr are the attributes to associate to the new cell (see getAttr() for
514 void* malloc(size_t size, uint attr=0)
519 // Find a free cell in the free list with enough space
520 auto cell = this.free_list.pop(size);
524 // No room in the free list found, if the GC is enabled, trigger
525 // a collection and try again
526 if (!this.disabled) {
528 cell = this.free_list.pop(size);
533 // No luck still, allocate a new cell
534 cell = Cell.alloc(size, attr);
539 onOutOfMemoryError();
545 cell.attr = cast(BlkAttr) attr;
548 this.live_list.link(cell);
554 * Allocate memory (set memory to zero).
556 * Same as malloc() but set the allocated memory cell to zero.
558 void* calloc(size_t size, uint attr=0)
563 void* ptr = this.malloc(size, attr);
565 if (ptr !is null) // in case onOutOfMemoryError didn't throw
566 cstring.memset(ptr, 0, size);
574 * This implementation is very simple, if size less or equals than the
575 * cells capacity, the cell's size is changed and the same address is
576 * returned. Otherwise a new cell is allocated using malloc() (this can
577 * trigger a collection), the contents are moved and the old cell is freed.
579 * attr has the same meaning as in malloc().
581 void* realloc(void* ptr, size_t size, uint attr=0)
584 // Undercover malloc()
586 return this.malloc(size, attr);
594 auto cell = this.live_list.find(ptr);
595 assert (cell !is null);
597 // We have enough capacity already, just change the size
598 if (cell.capacity >= size) {
603 // We need to move the cell because of the lack of capacity, find
604 // a free cell with the requested capacity (at least)
605 ptr = this.malloc(size, attr);
606 if (ptr is null) // in case onOutOfMemoryError didn't throw
608 Cell* new_cell = Cell.from_ptr(ptr);
609 assert (new_cell !is null);
611 // Move cell attributes and contents
612 new_cell.attr = cell.attr;
613 cstring.memcpy(new_cell.ptr, cell.ptr, cell.size);
622 * Attempt to in-place enlarge a memory block pointed to by ptr.
624 * The memory should be enlarged to at least min_size beyond its current
625 * capacity, up to a maximum of max_size. This does not attempt to move
626 * the memory block (like realloc() does).
629 * 0 if could not extend ptr, total size of entire memory block if
632 size_t extend(void* ptr, size_t min_size, size_t max_size)
634 assert (min_size <= max_size);
635 // There is no possible extension of the capacity for this
641 * Reserve memory to anticipate memory allocations.
643 * This implementation is really dumb, a single cell is allocated with
644 * size bytes. If 2 malloc()s follow a call to reserve(size), requesting
645 * size/2 bytes each, one allocation will still be done (and half the
646 * memory of the first malloc will be wasted =). Since this is a trivial
647 * implementation, we don't care about this.
649 * The actual number of bytes reserved are returned, or 0 on error.
651 size_t reserve(size_t size)
654 auto cell = Cell.alloc(size);
657 this.free_list.link(cell);
658 return cell.capacity;
662 * Free unused memory.
664 * This method tells the GC that a cell is not longer used. The GC doesn't
665 * perform any connectivity check, if the cell was referenced by others,
666 * nasty things will happen (much like C/C++).
668 * Note that finalizers are not called by this method. Finalizers are
669 * called by the runtime when the delete operator is used, and the delete
670 * operator calls this method through the runtime.
677 auto cell = this.live_list.pop(ptr);
678 assert (cell !is null);
680 this.free_list.link(cell);
684 * Get the base address of an interior pointer into the GC heap.
686 * If ptr is not pointing into the GC heap null is returned.
688 void* addrOf(void* ptr)
693 bool in_range(Cell* cell)
695 return ptr >= cell.ptr && ptr < (cell.ptr + cell.size);
698 auto cell = this.live_list.find(&in_range);
706 * Return the real size (capacity) for the cell pointed to by ptr.
708 * ptr should be the base address of a heap allocated object, interior
709 * pointers are not supported (use addrOf() if you have an interior
710 * pointer). If this is not true, this method returns 0.
712 * realloc(ptr, sizeOf(ptr), attr) is guaranteed not to allocate/move
715 size_t sizeOf(void* ptr)
717 auto cell = this.live_list.find(ptr);
719 return cell.capacity;
724 * Get information about the cell pointed to by ptr.
726 * ptr should be the base address of a heap allocated object, interior
727 * pointers are not supported (use addrOf() if you have an interior
728 * pointer). If this is not true, this method returns BlkInfo.init.
730 * See BlkInfo for the information provided by this method.
732 BlkInfo query(void* ptr)
736 auto cell = this.live_list.find(ptr);
738 blk_info.base = cell.ptr;
739 blk_info.size = cell.capacity;
740 blk_info.attr = cell.attr;
747 * Add a root pointer to the root set.
749 * This method can be used to register new root to the GC heap. This is
750 * only needed when the user has custom memory that has pointers into the
751 * GC heap (for example for interfacing with C programs, which allocates
752 * memory using malloc() directly).
754 * See_Also: removeRoot(), addRange(), removeRange()
756 void addRoot(void* ptr)
758 this.root_pointers.append(ptr);
762 * Add a root range to the root set.
764 * This method can be used to register new root range (a memory chunk
765 * that should be scanned for pointers into the GC heap). This is
766 * only needed when the user has custom memory that has pointers into the
767 * GC heap (for example for interfacing with C programs, which allocates
768 * memory using malloc() directly).
770 * Pointers will be scanned assuming they are aligned.
772 * See_Also: removeRange(), addRoot(), removeRoot()
774 void addRange(void* ptr, size_t size)
776 this.root_ranges.append(RootRange(ptr, ptr + size));
780 * Remove a root pointer from the root set.
782 * ptr has to be previously registered using addRoot(), otherwise the
783 * results are undefined.
785 * See_Also: addRoot(), addRange(), removeRange()
787 void removeRoot(void* ptr)
789 this.root_pointers.remove(ptr);
793 * Remove a root range from the root set.
795 * ptr has to be previously registered using addRange(), otherwise the
796 * results are undefined.
798 * See_Also: addRange(), addRoot(), removeRoot()
800 void removeRange(void* ptr)
802 this.root_ranges.remove_if((ref RootRange range) {
803 return range.from is ptr;
809 // vim: set et sw=4 sts=4 :