Tuesday, September 30, 2014

Deterministic Garbage Collection

Qore has had a big design problem in its memory management regarding object collection; basically it was possible to make circular references to objects, and those objects would not be destroyed automatically, resulting in a memory leak.

The reason for this is that Qore used a simple strong reference count for object scope, so if object A pointed to object B, object B pointed to object A, then a circular reference would exist and neither object would be destroyed (or collected) when the objects would otherwise go out of scope.  Note that Qore treats objects like Java does in that objects are always passed as a copy of a reference to the object instead of by value.  Weak references to objects are also supported, but weak object references do not affect object collection (ie when the destructor is run on the object); normally the object's destructor is run on the object only when the strong reference count reaches zero (or the object is manually deleted with the delete operator).

Also due to Qore's multi-threaded nature, objects can go out of scope at any time since they can be deleted in another thread at any time.  Qore objects are thread-safe and references to an objects are wrapped in a read-write lock - as are all shared lvalues in Qore - basically access to all lvalues in Qore are wrapped in read-write locks except accesses to "pure" local variables, which are local variables where references are not taken of them and also not used in a closure, either of which case makes it possible to use the local variable in another thread and therefore causes the local variable to be created specially so that accesses are wrapped in read-write locks.

I considered using something like Java's garbage collection approach with a dedicated thread that would scan and collect objects, but I always wanted to do a deterministic garbage collector so that Qore's resource management approach with objects could be applied deterministically.  I finally have an initial working implementation of a deterministic garbage collection algorithm for Qore that is thread-safe, does not require a dedicated collector thread, has a solid deadlock-avoidance mechanism, and exhibits acceptable performance (which I expect can be further improved).

With this new approach, objects are collected immediately when they only have strong references that belong to a recursive cycle; so resources managed by the object are released in a deterministic way even when the objects participate in a recursive reference cycle.

I would like to describe the algorithm here including the locking approach and the deadlock-avoidance mechanism.

Basically the idea is to determine the number of strong references to an object that belong to a circular reference.  In fact, it is more complicated than this, because you have to consider the entire recursive directed graph as a whole and not a single object.  The recursive directed graph in this case is the set of all objects participating in the recursive reference chain.  If any object is reachable in the chain and also contains link(s) (ie members) to other objects in the chain, then it is a member of the recursive directed graph.  So the idea is to maintain the recursive strong reference count of every object in the recursive directed graph and then, when any member of the graph is strongly dereferenced, then the entire graph is checked to see if it can be collected, meaning that each member of the graph is checked to see if the strong reference count is equal to its recursive reference count.  If any single member of the graph has non-recursive references, then no object in the graph can be collected; only when the strong reference count equals the recursive reference count for all objects in the graph can the objects in the graph be collected.

This is accomplished by performing a scan of all reachable objects whenever a potentially-relevant change is made to an object.  In this case the recursive reference counts are calculated for all objects in the graph.

To accomplish this, each object is locked specially.  In fact objects now have a special form of read-write lock that includes a special form of the read lock called an rsection lock.  The rsection lock in a Qore object is a read lock that is unique in that first the read lock is acquired and then only one thread can hold the rsection lock at a time.  This allows objects to be scanned for recursive graphs while also allowing them to be read in other threads to maximize concurrency.  Additionally, since multiple rsection locks are acquired when performing recursive scanning (one for each object) and held for the duration of the scan, and since holding multiple locks could lead to deadlocks, and since this can and is performed in multiple threads simultaneously in multi-threaded object-oriented Qore programs, and since otherwise Qore avoids holding multiple locks simultaneously, the deadlock avoidance approach here is to apply a transaction-handling approach to the rsection scan and if any rsection lock cannot be acquired, the transaction is rolled back and we wait for a confirmation from the other thread that the contentious rsection lock has been released.  Also a transaction counter in each object is maintained, and, after waiting for a contentious rsection lock to be released, we see that the transaction count for the root object has been changed, then we know that the rsection scan has already taken place, so we exit the scan immediately.

Basically all changes to objects are stored in temporary data structures and then only committed to the objects in the graph if all rsection locks are acquired.

Also all containers (lists, hashes, and objects) contain a reachable object count, which is a sum of the children (list elements, hash keys, or object members) that have at least one object reachable through them.  This turned out to be efficient to calculate.  This allows us to ignore any container that has no reachable objects when performing rsection scans.

Additionally if an rsection scan fails due to lock contention after an lvalue change, the scanned objects are marked with an invalid rsection so that a deterministic scan is made on the next strong dereference.  When performing rsection scans due to a strong dereference, the scan is repeated after an rsection rollback until it is successful to guarantee deterministic collection when only recursive references remain.

There is still certainly a lot of room for improvement to this algorithm.  For example, the rsection transaction could be compared to any existing rsection graph and left in place if identical results are found, or possibly a delta operation could be performed on an existing rsection graph.

While this algorithm is complicated, the goal of achieving deterministic garbage collection is a valid one in my opinion.

Knowing exactly when your objects will be collected even in the case of participation in recursive directed graphs of strong references provides an advantage to Qore programmers regarding resource management with objects.

Currently deterministic garbage collection is enabled by default in Qore trunk, and I plan on continuing to work on it.

Feedback on this subject would be appreciated.