Using dollar references, we can implement GC similar to Python. This should be optional feature.
There are few new things:
Classes that can be involved into cycles, must publicly inherit class that has void gcTraverse() and calls gc::step(ref) for each reference owned by this object. There should be two classes, one with virtual method and one with not virtual.
The objects requires gcDispose method that is responsible for breaking any cycles. It can also call gc::unref(...) to set reference to its initial state (which is impossible normally).
The gc::step should be overloaded by references types that requires more complicated handling e.g. Array.
Array must be overloaded in the step function, so only the arrays of objects with gcTraverse will be traveled.
There should be some way to run GC manually and automatically inside allocator/deallocator.
The gc::Object and gc::VirtualObject will have pointers used by doubly-linked queue of all objects (or a generation) and one or two additional fields used internally be GC.
gcTraverse and gcDispose do not care about references that are not involved into cycles, but it is safer to do so.
Destructor must be aware that gcDispose may mess up the references.
When GC is disabled, the API should be available to avoid #ifdefs.
Example:
DOLLAR_CLASS(Foo);
class FooClass: public gc::Object /* or gc::VirtualObject */ {
Array<int> ints;
Array<Bar$> bars;
Bar$N ref;
Bar$ staticBars[16];
void gcTraverse() {
gc::step(ints); // step will actually not travel this array
gc::step(bars); // step will enumerate the array
gc::step(ref); // pretty obvious
for (auto bar : staticBars) {
gc::step(bar);
}
}
void gcDispose() {
gc::unref(ints);
gc::unref(bars);
gc::unref(ref);
for (auto& bar : staticBars) {
gc::unref(bar);
}
}
// if there are just "simple" refs (no staticBars) then all of this can be replaced by:
GC_OBJECT(ints, bars, ref);
}
The algorithm:
clear tmp on all GCObjects
travel the graph incrementing tmp on each reference
GCObjects with tmp != refcounter are reachable
propagate reachable flag over the graph: tmp = size_t(-1), if it is already set, do not go further
take all unreachable objects
increment its refcounter
call gcDispose on them
decrement its refcounter
move remaining objects to the next generation
Maybe following points are not needed:
increment its refcounter
decrement its refcounter
Breaking references in the gcDispose causes deallocation of objects, so they will be removed from unreachable objects set (doubly-linked list). It will reduce number of gcDispose calls. To avoid list enumerator corruption, the object is removed from the list and added to a different one before call to gcDispose.
At the end, if the new list is non-empty, then it means that unreachable objects are not deallocates which indicates memory leak, we should call FAULT in this case.
Using dollar references, we can implement GC similar to Python. This should be optional feature.
There are few new things:
void gcTraverse()and callsgc::step(ref)for each reference owned by this object. There should be two classes, one with virtual method and one with not virtual.gcDisposemethod that is responsible for breaking any cycles. It can also callgc::unref(...)to set reference to its initial state (which is impossible normally).gc::stepshould be overloaded by references types that requires more complicated handling e.g.Array.Arraymust be overloaded in thestepfunction, so only the arrays of objects with gcTraverse will be traveled.gc::Objectandgc::VirtualObjectwill have pointers used by doubly-linked queue of all objects (or a generation) and one or two additional fields used internally be GC.gcTraverseandgcDisposedo not care about references that are not involved into cycles, but it is safer to do so.gcDisposemay mess up the references.#ifdefs.Example:
The algorithm:
tmpon all GCObjectstmpon each referencetmp != refcounterare reachabletmp = size_t(-1), if it is already set, do not go furtherrefcountergcDisposeon themrefcounterMaybe following points are not needed:
refcounterrefcounterBreaking references in the
gcDisposecauses deallocation of objects, so they will be removed from unreachable objects set (doubly-linked list). It will reduce number ofgcDisposecalls. To avoid list enumerator corruption, the object is removed from the list and added to a different one before call togcDispose.At the end, if the new list is non-empty, then it means that unreachable objects are not deallocates which indicates memory leak, we should call FAULT in this case.