]> git.llucax.com Git - software/dgc/naive.git/blob - gc/gc.d
Compare pointers explicitly against null using is and !is
[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 cstring = tango.stdc.string;
40
41 // Debug imports
42
43 /*
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.
47  */
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);
57
58 /**
59  * A range of memory that should be scanned for pointers.
60  *
61  * This object is iterable, yielding a pointer (void*) for each iteration.
62  */
63 struct RootRange
64 {
65
66     /// Beginning of the memory range
67     void* from;
68
69     /// End of the memory range
70     void* to;
71
72     /// Iterate over a memory range applying dg to its elements
73     int opApply(int delegate(ref void*) dg)
74     {
75         return op_apply_ptr_range(this.from, this.to, dg);
76     }
77
78 }
79
80
81 package:
82
83
84 /**
85  * Information on a block of memory.
86  *
87  * This is part of the GC specification, it's used for the query() method.
88  *
89  * Standards: Tango/Druntime specs
90  */
91 struct BlkInfo
92 {
93
94     /// Base address of the block
95     void* base;
96
97     /// Size of the block (this is the total capacity, not the requested size)
98     size_t size;
99
100     /**
101      * Memory block attributes
102      *
103      * See_Also: cell.BlkAttr for possible values
104      */
105     uint attr;
106
107 }
108
109
110 /**
111  * GC implementation.
112  *
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.
115  *
116  * This implementation is designed to be extremely simple. The algorithm
117  * implemented is the most basic stop-the-world mark-sweep known.
118  *
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.
122  *
123  * Two lists of cells are kept: free list and live list.
124  *
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).
128  *
129  * The root set is composed by several elements:
130  *
131  * $(UL
132  *      $(LI Static data)
133  *      $(LI Threads stack)
134  *      $(LI Registers)
135  *      $(LI Root pointers)
136  *      $(LI Root ranges)
137  * )
138  *
139  * Root pointers and ranges are user-defined.
140  *
141  * See_Also:
142  *
143  *  $(UL
144  *      $(LI cell.Cell for the cell header layout)
145  *      $(LI collect() for the main collection algorithm)
146  *      $(LI )
147  * )
148  *
149  */
150 struct GC
151 {
152
153 private:
154
155     /// List of free cells.
156     List free_list;
157
158     /// List of live cells.
159     List live_list;
160
161     /// Single root pointers.
162     DynArray!(void*) root_pointers;
163
164     /// Root ranges.
165     DynArray!(RootRange) root_ranges;
166
167     /**
168      * "Flag" to indicate when the GC is disabled.
169      *
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
173      * enabled again.
174      */
175     uint disabled = 0;
176
177     /**
178      * Remove the mark bit to all the live cells.
179      *
180      * This is done before starting the mark phase.
181      *
182      * See_Also:
183      *
184      *  $(UL
185      *      $(LI collect() for the main collect algorithm)
186      *      $(LI mark_all() for details on the marking phase)
187      *  )
188      */
189     void unmark()
190     {
191         foreach (cell; this.live_list)
192             cell.marked = false;
193     }
194
195     /**
196      * Mark all live data (pausing all threads)
197      *
198      * This methods start marking following all the known roots:
199      *
200      *  $(UL
201      *      $(LI Static data)
202      *      $(LI Threads stack)
203      *      $(LI Registers)
204      *      $(LI Root pointers)
205      *      $(LI Root ranges)
206      *  )
207      *
208      * Note that the registers are pushed into the stack to get scanned.
209      *
210      * This is the complete mark phase. The algorithm roughly does:
211      *
212      *  $(OL
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)
220      *  )
221      *
222      *
223      * See_Also:
224      *
225      *  $(UL
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)
229      *  )
230      */
231     void mark_all()
232     {
233         void* stack_top;
234         mixin (push_registers("stack_top"));
235         thread_suspendAll();
236         rt_scanStaticData(&mark_range);
237         thread_scanAll(&mark_range, stack_top);
238         foreach (ptr; this.root_pointers) {
239             this.mark(ptr);
240         }
241         foreach (range; this.root_ranges) {
242             this.mark_range(range.from, range.to);
243         }
244         thread_resumeAll();
245         mixin (pop_registers("stack_top"));
246     }
247
248     /**
249      * Wrapper for mark() over a range, needed by some runtime functions.
250      *
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.
253      *
254      * This extremely inefficient on purpose. The goal of this implementation
255      * is simplicity, nor performance.
256      *
257      * See_Also:
258      *  $(UL
259      *      $(LI mark() for details on the marking algorithm)
260      *  )
261      */
262     void mark_range(void* from, void* to)
263     {
264         foreach (ptr; RootRange(from, to))
265             mark(ptr);
266     }
267
268     /**
269      * Mark all cells accessible from a pointer.
270      *
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
273      * in text books.
274      *
275      * Marking is done with all threads stopped.
276      *
277      * See_Also:
278      *  $(UL
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)
282      *  )
283      */
284     void mark(void* ptr)
285     {
286         Cell* cell = Cell.from_ptr(this.addrOf(ptr));
287         if (cell is null)
288             return;
289         if (!cell.marked) {
290             cell.marked = true;
291             if (cell.has_pointers) {
292                 foreach (ptr; *cell)
293                     mark(ptr);
294             }
295         }
296     }
297
298     /**
299      * Move unreferenced live objects to the free list (calling finalizers).
300      *
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
304      * function.
305      *
306      * Sweeping is done concurrently with the mutator threads.
307      *
308      * See_Also:
309      *  $(UL
310      *      $(LI collect() for the main collect algorithm)
311      *      $(LI mark_all() for details on the marking phase)
312      *  )
313      */
314     void sweep()
315     {
316         foreach (cell; this.live_list) {
317             if (!cell.marked) {
318                 this.live_list.unlink(cell);
319                 if (cell.has_finalizer)
320                     rt_finalize(cell.ptr, false);
321                 this.free_list.link(cell);
322             }
323         }
324     }
325
326
327 public:
328
329     /**
330      * Initialize the GC.
331      *
332      * This initializes the thread library too, as requested by the
333      * Tango/Druntime specs.
334      */
335     void init()
336     {
337         this.disabled = 0;
338         thread_init();
339     }
340
341     /**
342      * Terminate the GC.
343      *
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).
347      *
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
351      * program exit.
352      *
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
356      */
357     void term()
358     {
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.
363     }
364
365     /**
366      * Enable the GC.
367      *
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.
370      *
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.
374      *
375      * See_Also: disable()
376      */
377     void enable()
378     {
379         assert (this.disabled > 0);
380         this.disabled--;
381     }
382
383     /**
384      * Disable the GC.
385      *
386      * See_Also: enable()
387      */
388     void disable()
389     {
390         this.disabled++;
391         assert (this.disabled > 0);
392     }
393
394     /**
395      * Run a GC collection in order to find unreferenced objects.
396      *
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
401      * cells to free.
402      *
403      * The world is stopped only for the mark phase.
404      *
405      * See_Also:
406      *  $(UL
407      *      $(LI mark_all() for details on the marking phase)
408      *      $(LI sweep() for details on the sweep phase)
409      *  )
410      */
411     void collect()
412     {
413         this.unmark();
414         this.mark_all();
415         this.sweep();
416     }
417
418     /**
419      * Minimize free space usage.
420      *
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
428      * allocations).
429      *
430      * This implementation just return to the OS all the cells in the free
431      * list.
432      */
433     void minimize()
434     {
435         foreach (cell; this.free_list) {
436             this.free_list.unlink(cell);
437             Cell.free(cell);
438         }
439     }
440
441     /**
442      * Get attributes associated to the cell pointed by ptr.
443      *
444      * Attributes is a bitmap that can have these values:
445      *
446      *  $(UL
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
450      *           (unimplemented))
451      *  )
452      *
453      * See_Also: cell.BlkAttr, setAttr(), clrAttr()
454      */
455     uint getAttr(void* ptr)
456     {
457         auto cell = this.live_list.find(ptr);
458         if (cell !is null)
459             return cell.attr;
460         return 0;
461     }
462
463     /**
464      * Set the attributes of the cell pointed by ptr.
465      *
466      * All bits present in attr are set, other bits are untouched. The old
467      * attributes are returned.
468      *
469      * See_Also: cell.BlkAttr, getAttr(), clrAttr()
470      */
471     uint setAttr(void* ptr, uint attr)
472     {
473         auto cell = this.live_list.find(ptr);
474         if (cell !is null) {
475             auto old = cell.attr;
476             cell.attr |= attr;
477             return cell.attr;
478         }
479         return 0;
480     }
481
482     /**
483      * Clear the attributes of the cell pointed by ptr.
484      *
485      * All bits present in attr are cleared, other bits are untouched. The old
486      * attributes are returned.
487      *
488      * See_Also: cell.BlkAttr, getAttr(), setAttr()
489      */
490     uint clrAttr(void* ptr, uint attr)
491     {
492         auto cell = this.live_list.find(ptr);
493         if (cell !is null) {
494             auto old = cell.attr;
495             cell.attr &= ~attr;
496             return cell.attr;
497         }
498         return 0;
499     }
500
501     /**
502      * Allocate memory.
503      *
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.
510      *
511      * attr are the attributes to associate to the new cell (see getAttr() for
512      * details).
513      */
514     void* malloc(size_t size, uint attr=0)
515     {
516         if (size == 0)
517             return null;
518
519         // Find a free cell in the free list with enough space
520         auto cell = this.free_list.pop(size);
521         if (cell !is null)
522             goto reuse;
523
524         // No room in the free list found, if the GC is enabled, trigger
525         // a collection and try again
526         if (!this.disabled) {
527             this.collect();
528             cell = this.free_list.pop(size);
529             if (cell !is null)
530                 goto reuse;
531         }
532
533         // No luck still, allocate a new cell
534         cell = Cell.alloc(size, attr);
535         if (cell !is null)
536             goto link;
537
538         // No memory
539         onOutOfMemoryError();
540
541         return null;
542
543     reuse:
544         cell.size = size;
545         cell.attr = cast(BlkAttr) attr;
546
547     link:
548         this.live_list.link(cell);
549
550         return cell.ptr;
551     }
552
553     /**
554      * Allocate memory (set memory to zero).
555      *
556      * Same as malloc() but set the allocated memory cell to zero.
557      */
558     void* calloc(size_t size, uint attr=0)
559     {
560         if (size == 0)
561             return null;
562
563         void* ptr = this.malloc(size, attr);
564
565         if (ptr !is null) // in case onOutOfMemoryError didn't throw
566             cstring.memset(ptr, 0, size);
567
568         return ptr;
569     }
570
571     /**
572      * Reallocate memory.
573      *
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.
578      *
579      * attr has the same meaning as in malloc().
580      */
581     void* realloc(void* ptr, size_t size, uint attr=0)
582     {
583
584         // Undercover malloc()
585         if (ptr is null)
586             return this.malloc(size, attr);
587
588         // Undercover free()
589         if (size == 0) {
590             this.free(ptr);
591             return null;
592         }
593
594         auto cell = this.live_list.find(ptr);
595         assert (cell !is null);
596
597         // We have enough capacity already, just change the size
598         if (cell.capacity >= size) {
599             cell.size = size;
600             return cell.ptr;
601         }
602
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
607             return null;
608         Cell* new_cell = Cell.from_ptr(ptr);
609         assert (new_cell !is null);
610
611         // Move cell attributes and contents
612         new_cell.attr = cell.attr;
613         cstring.memcpy(new_cell.ptr, cell.ptr, cell.size);
614
615         // Free the old cell
616         this.free(cell);
617
618         return new_cell.ptr;
619     }
620
621     /**
622      * Attempt to in-place enlarge a memory block pointed to by ptr.
623      *
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).
627      *
628      * Returns:
629      *  0 if could not extend ptr, total size of entire memory block if
630      *  successful.
631      */
632     size_t extend(void* ptr, size_t min_size, size_t max_size)
633     {
634         assert (min_size <= max_size);
635         // There is no possible extension of the capacity for this
636         // implementation.
637         return 0;
638     }
639
640     /**
641      * Reserve memory to anticipate memory allocations.
642      *
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.
648      *
649      * The actual number of bytes reserved are returned, or 0 on error.
650      */
651     size_t reserve(size_t size)
652     {
653         assert (size > 0);
654         auto cell = Cell.alloc(size);
655         if (cell is null)
656             return 0;
657         this.free_list.link(cell);
658         return cell.capacity;
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 !is null);
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 !is null)
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 !is null)
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 !is null) {
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 :