Initialize capacity to 0 when allocating a new cell
[software/dgc/naive.git] / gc / gc.d
1 /**
2  * Naive Garbage Collector implementation.
3  *
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.
7  *
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.
12  *
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.
22  *
23  * Copyright: Public Domain
24  * License:   Public Domain
25  * Authors:   Leandro Lucarella <llucax@gmail.com>
26  */
27
28 module gc.gc;
29
30 private:
31
32 // Internal imports
33 import gc.cell: Cell, BlkAttr, op_apply_ptr_range;
34 import gc.list: List;
35 import gc.dynarray: DynArray;
36 import gc.arch: push_registers, pop_registers;
37
38 // Standard imports
39 import cstdlib = tango.stdc.stdlib;
40 import cstring = tango.stdc.string;
41
42 // Debug imports
43
44 /*
45  * These are external functions coming from the D/Tango runtime. It's pretty
46  * intuitive what they do based on their names, for more details please
47  * refer to the functions documentation.
48  */
49 alias void delegate(void*, void*) mark_function;
50 extern (C) void onOutOfMemoryError();
51 extern (C) void rt_finalize(void* p, bool det=true);
52 extern (C) void rt_scanStaticData(mark_function mark);
53 extern (C) void thread_init();
54 extern (C) bool thread_needLock();
55 extern (C) void thread_suspendAll();
56 extern (C) void thread_resumeAll();
57 extern (C) void thread_scanAll(mark_function mark, void* stack_top=null);
58
59 /**
60  * A range of memory that should be scanned for pointers.
61  *
62  * This object is iterable, yielding a pointer (void*) for each iteration.
63  */
64 struct RootRange
65 {
66
67     /// Beginning of the memory range
68     void* from;
69
70     /// End of the memory range
71     void* to;
72
73     /// Iterate over a memory range applying dg to its elements
74     int opApply(int delegate(ref void*) dg)
75     {
76         return op_apply_ptr_range(this.from, this.to, dg);
77     }
78
79 }
80
81
82 package:
83
84
85 /**
86  * Information on a block of memory.
87  *
88  * This is part of the GC specification, it's used for the query() method.
89  *
90  * Standards: Tango/Druntime specs
91  */
92 struct BlkInfo
93 {
94
95     /// Base address of the block
96     void* base;
97
98     /// Size of the block (this is the total capacity, not the requested size)
99     size_t size;
100
101     /**
102      * Memory block attributes
103      *
104      * See_Also: cell.BlkAttr for possible values
105      */
106     uint attr;
107
108 }
109
110
111 /**
112  * GC implementation.
113  *
114  * This object contains the whole GC implementation. This is instantiated in
115  * the iface module as a global variable to provide the GC services.
116  *
117  * This implementation is designed to be extremely simple. The algorithm
118  * implemented is the most basic stop-the-world mark-sweep known.
119  *
120  * Memory is organized in cells. Each cell has a header where all the
121  * bookkeeping information is stored (like the mark bit, cell attributes,
122  * capacity, etc.), and the memory allocated for the requested memory itself.
123  *
124  * Two lists of cells are kept: free list and live list.
125  *
126  * The free list store cells known not to be referenced by the program. The
127  * live list stores cells that were referenced by the program at the end of
128  * the last collection (and just allocated cells).
129  *
130  * The root set is composed by several elements:
131  *
132  * $(UL
133  *      $(LI Static data)
134  *      $(LI Threads stack)
135  *      $(LI Registers)
136  *      $(LI Root pointers)
137  *      $(LI Root ranges)
138  * )
139  *
140  * Root pointers and ranges are user-defined.
141  *
142  * See_Also:
143  *
144  *  $(UL
145  *      $(LI cell.Cell for the cell header layout)
146  *      $(LI collect() for the main collection algorithm)
147  *      $(LI )
148  * )
149  *
150  */
151 struct GC
152 {
153
154 private:
155
156     /// List of free cells.
157     List free_list;
158
159     /// List of live cells.
160     List live_list;
161
162     /// Single root pointers.
163     DynArray!(void*) root_pointers;
164
165     /// Root ranges.
166     DynArray!(RootRange) root_ranges;
167
168     /**
169      * "Flag" to indicate when the GC is disabled.
170      *
171      * This is a number because calls to enable() and disable() can be
172      * recursive. The number of calls to enable() should match the number of
173      * calls to disable(), though, if you want the GC to be effectively
174      * enabled again.
175      */
176     uint disabled = 0;
177
178     /**
179      * Remove the mark bit to all the live cells.
180      *
181      * This is done before starting the mark phase.
182      *
183      * See_Also:
184      *
185      *  $(UL
186      *      $(LI collect() for the main collect algorithm)
187      *      $(LI mark_all() for details on the marking phase)
188      *  )
189      */
190     void unmark()
191     {
192         foreach (cell; this.live_list)
193             cell.marked = false;
194     }
195
196     /**
197      * Mark all live data (pausing all threads)
198      *
199      * This methods start marking following all the known roots:
200      *
201      *  $(UL
202      *      $(LI Static data)
203      *      $(LI Threads stack)
204      *      $(LI Registers)
205      *      $(LI Root pointers)
206      *      $(LI Root ranges)
207      *  )
208      *
209      * Note that the registers are pushed into the stack to get scanned.
210      *
211      * This is the complete mark phase. The algorithm roughly does:
212      *
213      *  $(OL
214      *      $(LI Push registers into the stack)
215      *      $(LI Pause all threads (but the current one, of course))
216      *      $(LI Scan the static data)
217      *      $(LI Scan all threads stack)
218      *      $(LI Scan the root pointers and ranges)
219      *      $(LI Resume all threads)
220      *      $(LI Pop the registers from the stack)
221      *  )
222      *
223      *
224      * See_Also:
225      *
226      *  $(UL
227      *      $(LI collect() for the main collect algorithm)
228      *      $(LI mark() for details on the marking algorithm)
229      *      $(LI sweep() for details on the sweep phase)
230      *  )
231      */
232     void mark_all()
233     {
234         void* stack_top;
235         mixin (push_registers("stack_top"));
236         thread_suspendAll();
237         rt_scanStaticData(&mark_range);
238         thread_scanAll(&mark_range, stack_top);
239         foreach (ptr; this.root_pointers) {
240             this.mark(ptr);
241         }
242         foreach (range; this.root_ranges) {
243             this.mark_range(range.from, range.to);
244         }
245         thread_resumeAll();
246         mixin (pop_registers("stack_top"));
247     }
248
249     /**
250      * Wrapper for mark() over a range, needed by some runtime functions.
251      *
252      * This function is used as a delegate to be passed to rt_scanStaticData()
253      * and thread_scanAll(), because they expect a function taking 2 pointers.
254      *
255      * This extremely inefficient on purpose. The goal of this implementation
256      * is simplicity, nor performance.
257      *
258      * See_Also:
259      *  $(UL
260      *      $(LI mark() for details on the marking algorithm)
261      *  )
262      */
263     void mark_range(void* from, void* to)
264     {
265         foreach (ptr; RootRange(from, to))
266             mark(ptr);
267     }
268
269     /**
270      * Mark all cells accessible from a pointer.
271      *
272      * This is the mark algorithm itself. It's recursive and dumb as a log. No
273      * care is taken in regards to stack overflows. This is the first example
274      * in text books.
275      *
276      * Marking is done with all threads stopped.
277      *
278      * See_Also:
279      *  $(UL
280      *      $(LI collect() for the main collect algorithm)
281      *      $(LI mark_all() for details on the marking phase)
282      *      $(LI sweep() for details on the sweep phase)
283      *  )
284      */
285     void mark(void* ptr)
286     {
287         Cell* cell = Cell.from_ptr(this.addrOf(ptr));
288         if (cell is null)
289             return;
290         if (!cell.marked) {
291             cell.marked = true;
292             if (cell.has_pointers) {
293                 foreach (ptr; *cell)
294                     mark(ptr);
295             }
296         }
297     }
298
299     /**
300      * Move unreferenced live objects to the free list (calling finalizers).
301      *
302      * This is the sweep phase. It's very simple, it just searches the live
303      * list and move unmarked cells to the free list. This function is in
304      * charge of calling finalizers too, through the rt_finalize() runtime
305      * function.
306      *
307      * Sweeping is done concurrently with the mutator threads.
308      *
309      * See_Also:
310      *  $(UL
311      *      $(LI collect() for the main collect algorithm)
312      *      $(LI mark_all() for details on the marking phase)
313      *  )
314      */
315     void sweep()
316     {
317         foreach (cell; this.live_list) {
318             if (!cell.marked) {
319                 this.live_list.unlink(cell);
320                 if (cell.has_finalizer)
321                     rt_finalize(cell.ptr, false);
322                 this.free_list.link(cell);
323             }
324         }
325     }
326
327
328 public:
329
330     /**
331      * Initialize the GC.
332      *
333      * This initializes the thread library too, as requested by the
334      * Tango/Druntime specs.
335      */
336     void init()
337     {
338         this.disabled = 0;
339         thread_init();
340     }
341
342     /**
343      * Terminate the GC.
344      *
345      * Finalization of unreferenced cells is not mandatory by the specs.
346      * This implementation guarantees that all finalizers are called, at least
347      * at program exit (i.e. at GC termination).
348      *
349      * The specs says that "objects referenced from the data segment never get
350      * collected by the GC". While this is true for this implementation,
351      * finalizers are called for objects referenced from the data segment at
352      * program exit.
353      *
354      * There could be some problems with this, in very strange situations. For
355      * a more complete discussion about the topic please take a look at the
356      * bug 2858: http://d.puremagic.com/issues/show_bug.cgi?id=2858
357      */
358     void term()
359     {
360         foreach (cell; this.live_list)
361             if (cell.has_finalizer)
362                 rt_finalize(cell.ptr, false);
363         // Let the OS free the memory on exit.
364     }
365
366     /**
367      * Enable the GC.
368      *
369      * When the GC is enabled, a collection is triggered when malloc() can't
370      * find room in the free list to fulfill the requested size.
371      *
372      * enable() and disable() can be called recursively. The number of calls
373      * to enable() should match the number of calls to disable(), though, if
374      * you want the GC to be effectively enabled again.
375      *
376      * See_Also: disable()
377      */
378     void enable()
379     {
380         assert (this.disabled > 0);
381         this.disabled--;
382     }
383
384     /**
385      * Disable the GC.
386      *
387      * See_Also: enable()
388      */
389     void disable()
390     {
391         this.disabled++;
392         assert (this.disabled > 0);
393     }
394
395     /**
396      * Run a GC collection in order to find unreferenced objects.
397      *
398      * This is the simplest stop-the-world mark-sweep algorithm ever. It first
399      * removes the mark bit from all the live cells, then it marks the cells
400      * that are reachable through the root set (static data, stack, registers
401      * and custom root), and finally sweeps the live list looking for unmarked
402      * cells to free.
403      *
404      * The world is stopped only for the mark phase.
405      *
406      * See_Also:
407      *  $(UL
408      *      $(LI mark_all() for details on the marking phase)
409      *      $(LI sweep() for details on the sweep phase)
410      *  )
411      */
412     void collect()
413     {
414         this.unmark();
415         this.mark_all();
416         this.sweep();
417     }
418
419     /**
420      * Minimize free space usage.
421      *
422      * This method returns to the OS memory that is not longer used by
423      * the program. Usually calling this method manually is not
424      * necessary, because unused cells are recycled for future
425      * allocations. But if there is some small part of the program that
426      * requires a lot of memory and it's known that it won't be used
427      * further, calling this can reduce the memory footprint of the program
428      * considerably (at the expense of some performance lost in future
429      * allocations).
430      *
431      * This implementation just return to the OS all the cells in the free
432      * list.
433      */
434     void minimize()
435     {
436         foreach (cell; this.free_list) {
437             this.free_list.unlink(cell);
438             cstdlib.free(cell);
439         }
440     }
441
442     /**
443      * Get attributes associated to the cell pointed by ptr.
444      *
445      * Attributes is a bitmap that can have these values:
446      *
447      *  $(UL
448      *      $(LI 1: The object stored in the cell has to be finalized)
449      *      $(LI 2: The cell should not be scanned for pointers)
450      *      $(LI 4: The cell should not be moved during a collection
451      *           (unimplemented))
452      *  )
453      *
454      * See_Also: cell.BlkAttr, setAttr(), clrAttr()
455      */
456     uint getAttr(void* ptr)
457     {
458         auto cell = this.live_list.find(ptr);
459         if (cell)
460             return cell.attr;
461         return 0;
462     }
463
464     /**
465      * Set the attributes of the cell pointed by ptr.
466      *
467      * All bits present in attr are set, other bits are untouched. The old
468      * attributes are returned.
469      *
470      * See_Also: cell.BlkAttr, getAttr(), clrAttr()
471      */
472     uint setAttr(void* ptr, uint attr)
473     {
474         auto cell = this.live_list.find(ptr);
475         if (cell) {
476             auto old = cell.attr;
477             cell.attr |= attr;
478             return cell.attr;
479         }
480         return 0;
481     }
482
483     /**
484      * Clear the attributes of the cell pointed by ptr.
485      *
486      * All bits present in attr are cleared, other bits are untouched. The old
487      * attributes are returned.
488      *
489      * See_Also: cell.BlkAttr, getAttr(), setAttr()
490      */
491     uint clrAttr(void* ptr, uint attr)
492     {
493         auto cell = this.live_list.find(ptr);
494         if (cell) {
495             auto old = cell.attr;
496             cell.attr &= ~attr;
497             return cell.attr;
498         }
499         return 0;
500     }
501
502     /**
503      * Allocate memory.
504      *
505      * This is the main allocator of the GC. The algorithm is really
506      * simple. It does a first-fit search in the free list, if no free cell is
507      * found with enough room, it runs a collection and retry (unless the GC
508      * is disabled). If there is no room still, it uses C malloc to allocate
509      * a new cell. If all that fails, then onOutOfMemoryError() runtime
510      * function is called to handle the error.
511      *
512      * attr are the attributes to associate to the new cell (see getAttr() for
513      * details).
514      */
515     void* malloc(size_t size, uint attr=0)
516     {
517         if (size == 0)
518             return null;
519
520         // Find a free cell in the free list with enough space
521         auto cell = this.free_list.pop(size);
522         if (cell)
523             goto success;
524
525         // No room in the free list found, if the GC is enabled, trigger
526         // a collection and try again
527         if (!this.disabled) {
528             this.collect();
529             cell = this.free_list.pop(size);
530             if (cell)
531                 goto success;
532         }
533
534         // No luck still, allocate new memory
535         cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
536         cell.capacity = 0; // so we can later tell it's new
537         if (cell)
538             goto success;
539
540         // No memory
541         onOutOfMemoryError();
542
543         return null;
544
545     success:
546         cell.size = size;
547         if (cell.capacity == 0) // fresh cell
548             cell.capacity = size;
549         cell.attr = cast(BlkAttr) attr;
550         this.live_list.link(cell);
551
552         return cell.ptr;
553     }
554
555     /**
556      * Allocate memory (set memory to zero).
557      *
558      * Same as malloc() but set the allocated memory cell to zero.
559      */
560     void* calloc(size_t size, uint attr=0)
561     {
562         void* ptr = this.malloc(size, attr);
563
564         if (ptr is null)
565             onOutOfMemoryError();
566         else
567             cstring.memset(ptr, 0, size);
568
569         return ptr;
570     }
571
572     /**
573      * Reallocate memory.
574      *
575      * This implementation is very simple, if size less or equals than the
576      * cells capacity, the cell's size is changed and the same address is
577      * returned. Otherwise a new cell is allocated using malloc() (this can
578      * trigger a collection), the contents are moved and the old cell is freed.
579      *
580      * attr has the same meaning as in malloc().
581      */
582     void* realloc(void* ptr, size_t size, uint attr=0)
583     {
584
585         // Undercover malloc()
586         if (ptr is null)
587             return this.malloc(size, attr);
588
589         // Undercover free()
590         if (size == 0) {
591             this.free(ptr);
592             return null;
593         }
594
595         auto cell = this.live_list.find(ptr);
596         assert (cell);
597
598         // We have enough capacity already, just change the size
599         if (cell.capacity >= size) {
600             cell.size = size;
601             return cell.ptr;
602         }
603
604         // We need to move the cell because of the lack of capacity, find
605         // a free cell with the requested capacity (at least)
606         Cell* new_cell = Cell.from_ptr(this.malloc(size));
607         assert (!(new_cell is null)); // out of memory is handled by malloc()
608
609         // Move cell attributes and contents
610         new_cell.attr = cell.attr;
611         cstring.memcpy(new_cell.ptr, cell.ptr, cell.size);
612
613         // Free the old cell
614         this.free(cell);
615
616         return new_cell.ptr;
617     }
618
619     /**
620      * Attempt to in-place enlarge a memory block pointed to by ptr.
621      *
622      * The memory should be enlarged to at least min_size beyond its current
623      * capacity, up to a maximum of max_size. This does not attempt to move
624      * the memory block (like realloc() does).
625      *
626      * Returns:
627      *  0 if could not extend ptr, total size of entire memory block if
628      *  successful.
629      */
630     size_t extend(void* ptr, size_t min_size, size_t max_size)
631     {
632         assert (min_size <= max_size);
633         // There is no possible extension of the capacity for this
634         // implementation.
635         return 0;
636     }
637
638     /**
639      * Reserve memory to anticipate memory allocations.
640      *
641      * This implementation is really dumb, a single cell is allocated with
642      * size bytes. If 2 malloc()s follow a call to reserve(size), requesting
643      * size/2 bytes each, one allocation will still be done (and half the
644      * memory of the first malloc will be wasted =). Since this is a trivial
645      * implementation, we don't care about this.
646      *
647      * The actual number of bytes reserved are returned, or 0 on error.
648      */
649     size_t reserve(size_t size)
650     {
651         assert (size > 0);
652         auto cell = cast(Cell*) cstdlib.malloc(size + Cell.sizeof);
653         if (!cell)
654             return 0;
655         cell.size = size;
656         cell.capacity = size;
657         this.free_list.link(cell);
658         return size;
659     }
660
661     /**
662      * Free unused memory.
663      *
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++).
667      *
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.
671      */
672     void free(void* ptr)
673     {
674         if (ptr is null)
675             return;
676
677         auto cell = this.live_list.pop(ptr);
678         assert (cell);
679
680         this.free_list.link(cell);
681     }
682
683     /**
684      * Get the base address of an interior pointer into the GC heap.
685      *
686      * If ptr is not pointing into the GC heap null is returned.
687      */
688     void* addrOf(void* ptr)
689     {
690         if (ptr is null)
691             return null;
692
693         bool in_range(Cell* cell)
694         {
695             return ptr >= cell.ptr && ptr < (cell.ptr + cell.size);
696         }
697
698         auto cell = this.live_list.find(&in_range);
699         if (cell)
700             return cell.ptr;
701
702         return null;
703     }
704
705     /**
706      * Return the real size (capacity) for the cell pointed to by ptr.
707      *
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.
711      *
712      * realloc(ptr, sizeOf(ptr), attr) is guaranteed not to allocate/move
713      * memory.
714      */
715     size_t sizeOf(void* ptr)
716     {
717         auto cell = this.live_list.find(ptr);
718         if (cell)
719             return cell.capacity;
720         return 0;
721     }
722
723     /**
724      * Get information about the cell pointed to by ptr.
725      *
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.
729      *
730      * See BlkInfo for the information provided by this method.
731      */
732     BlkInfo query(void* ptr)
733     {
734         BlkInfo blk_info;
735
736         auto cell = this.live_list.find(ptr);
737         if (cell) {
738             blk_info.base = cell.ptr;
739             blk_info.size = cell.capacity;
740             blk_info.attr = cell.attr;
741         }
742
743         return blk_info;
744     }
745
746     /**
747      * Add a root pointer to the root set.
748      *
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).
753      *
754      * See_Also: removeRoot(), addRange(), removeRange()
755      */
756     void addRoot(void* ptr)
757     {
758         this.root_pointers.append(ptr);
759     }
760
761     /**
762      * Add a root range to the root set.
763      *
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).
769      *
770      * Pointers will be scanned assuming they are aligned.
771      *
772      * See_Also: removeRange(), addRoot(), removeRoot()
773      */
774     void addRange(void* ptr, size_t size)
775     {
776         this.root_ranges.append(RootRange(ptr, ptr + size));
777     }
778
779     /**
780      * Remove a root pointer from the root set.
781      *
782      * ptr has to be previously registered using addRoot(), otherwise the
783      * results are undefined.
784      *
785      * See_Also: addRoot(), addRange(), removeRange()
786      */
787     void removeRoot(void* ptr)
788     {
789         this.root_pointers.remove(ptr);
790     }
791
792     /**
793      * Remove a root range from the root set.
794      *
795      * ptr has to be previously registered using addRange(), otherwise the
796      * results are undefined.
797      *
798      * See_Also: addRange(), addRoot(), removeRoot()
799      */
800     void removeRange(void* ptr)
801     {
802         this.root_ranges.remove_if((ref RootRange range) {
803                     return range.from is ptr;
804                 });
805     }
806
807 } // struct GC
808
809 // vim: set et sw=4 sts=4 :