Reinventing the wheel with the circular reference resolver.

Today I have implemented a "circular reference resolver". In other words, it is a garbage collector, a very simple one.

My little framework uses reference counting (+ smart pointers) to manage memory. However, sometimes I need circular references. It is usually a parent-child relation. In my case, a parent contains a cached child object that again points to the parent.

A naive reference counting implementation can't deal with circular references at all. No matter what it does, an isolated island of objects will live on their own.

I also can't use "weak" references, i.e. without actually retaining references. Imagine the following scenario: a material contains a hard reference to a state, while the state contains a weak reference (no retaining) to the material.

copy to clipboardподсветка кода

1. TMaterial* mat = TMaterial::Load("stone.mat"); // material refCount = 1  
2. TMaterialState* matState = mat->CreateState(); // state refcount = 1;  
3. entity->SetMaterialState(matState);  // state refCount=2  
4. matState->Unref(); // state refCount=1  
5. mat->Unref(); // material refCount = 0  

Since the state references the material in a weak manner, the material may eventually get released, because the system thinks no one references it (it doesn't track "weak" references) and we're free to remove it. And then, when the state will try to reference material data, we'll get a crash :(
We also can't make them both reference each other in a hard manner because in that case a circular reference will prevent us from releasing the whole group at all.

TCircularReferenceResolver deals with it very simply: it just holds a big "parent => children" map which is regularly enumerated at a given interval (explicitly via TCircularReferenceResolver::Collect()). When a circular reference group is created, it should be explicitly added to the resolver (somewhere in the constructor), via ::AddParentChildRelation. A parent must explicitly remove its children in the destructor definition, however children should never try to unreference their parent, by having a weak reference (this prevents from infinite recursion).

TCircularReferenceResolver itself retains hard references to all such objects. So when user code forgets about these objects, their reference count is guaranteed to be: 1 for the parent (retained by the big map) and 2 for each children (one reference retained from the big map and one reference from the parent).

If at least one object in such group (parent => children) contains a bigger number of retained references than 1-2, then the whole group is reachable. If the parent has exactly 1 reference and its children have exactly 2 references each, then the group is supposed to be unreachable, and we can release it at once, simply unreferencing the parent which will recursively release all children.

We also can have multiple resolvers, and we can make resolvers current for specific threads.

Here is an example:

copy to clipboardподсветка кода

1. TStaticMaterial::TStaticMaterial(TTexture* texture) // ctor  
2. {  
3.     TCircularReferenceResolver* resolver = TCircularReferenceResolver::ForCurrentThread(); // this resolver is registered by the canvas  
4.     if(!resolver)  
5.         DA_THROW_WITH_MSG(EC_INVALID_STATE, "No circular reference resolver registered for the current thread. Probably called outside the Canvas thread.");  
6.     m_texture = texture;  
7.     texture->Ref();  
8.     m_cachedState = new TStaticMaterialState(this); // they reference each other  
9.     resolver->AddParentChildRelation(this, m_cachedState); // explicitly adds to the resolver  
10. }  

And I also have a canvas->m_contentMgr->CollectCircularReferences(curTicks); call in the rendering thread, which triggers collection each 5 seconds for the debug build, and each 15 seconds for the release build (it's not like the Java's collector which traces the whole heap, so it's a decent interval).

Then if I write something stupid like this:

copy to clipboardподсветка кода

1. // Loads the material (which is TStaticMaterial).  
2.   TMaterial* garbage = canvas->ContentManager()->LoadMaterial(TString::FromUtf8("default.dmat"), false);  
3.  // And immediately removes from the cache.  
4.   canvas->ContentManager()->RemoveMaterial(TString::FromUtf8("default.dmat"));   
5. // And also removes the last reference.  
6.   garbage->Unref();   

the log will print in 5 seconds:

[INFO!Main] Garbage collected 1 circular reference group(s).

Makes me feel so cozy when I see it :)

The resolver isn't probably fully thread-safe though: it doesn't stop the world. I didn't care about it very much, because 1) resolvers are supposed to be per-thread 2) i have only 2 working threads for the current project 3) ref/unref are atomic. Anyway, if we urgently need to synchronize it, the ::SyncRoot() mutex is supposed to be used.