Re: [boost] interest poll: smart pointers that handle circularreferences

From: Ariane van der Steldt (ariane_at_[hidden])
Date: 2007-04-10 20:29:20

Jarrad Waterloo wrote:
> I am very interested in such a family of smart pointers as I deeply believe
> that weak_ptr isn't a real solution to cyclical references as your scenario
> illustrates.
> Some questions if you don't mind.
> Will resources be cleaned up in a deterministic manner ie. When the last
> master of A or B is deleted on the stack will it immediately cleanup A and
> B? If that is not the case, is there a gc_cleanup() method that would have
> to be called in code or in a background thread?

The code I have tries to perform a direct removal. If there are no 
circular references in the pointer, this is trivial and simply a case of 
calling the delete operator. In the case that the last reference to 
class A from the execution thread is erased, but at least one other 
class still refers to this class A, the cleanup() function is invoked. 
This function attempts to remove the class if it has indeed become 
unreachable. The cleanup function is potentially very expensive: o(n^2) 
though this can be optimized to o(n * log(n)) which is on my todo.

Because of the expensiveness, there are ways to control the cleanup() 
function, by temporary suspending it or choosing a different policy 
(immediate = run cleanup immediately, thread = run cleanup in separate 
thread, oom = don't run cleanup unless an out of memory condition occurs 
via std::new_handler). The cleanup function has many points where it 
releases locks, to allow other threads to continue creating and 
modifying references while a cleanup is running. The cleanup() function 
can be manually called, with a force flag, which forces the cleanup() to 
happen even if a batch is active. The cleanup() does not run if a 
cleanup is already active.

 > Can it handle object graphs of arbitrary/any complexity or does it
 > only work with hierarchies?

The code can handle any complexity, basically the garbage collector 
traverses the list of references between the objects. At the start of a 
cleanup, each pointer starts out marked white. Every pointer with a 
parent that is directly reachable (i.e. has at least one intrusive_ptr 
pointing to it, has been allocated on the stack or has not ever been 
reachable before) is marked grey. Then the garbage collector loops 
through the grey elements one at a time, marks it black and marks any 
pointers originating from objects pointed to by this pointer grey. It 
repeats until no more grey marked pointers are available, at which point 
the white list contains only unreachable pointers.

The garbage collector does not allocate any heap memory, apart from 
memory allocated by an empty std::list class and 
boost::mutex::scoped_lock, both of which are none as far as I know.

Since the garbage collector can't make an educated guess about where to 
start breaking down a cycle, what it does is make every pointer in the 
cycle point to null, which brings down the reference_counters on the 
pointed-to objects to 0, causing them to be deleted. Code using this 
pointer type may therefore never assume pointers are still valid during 
their destructor.

 > Please don't keep me, the boost user community, waiting.

I'll prepare the current code to be uploaded in the vault, so people can 
have a look at the current implementation (which means I have to change 
the make (bsd make using openbsd make includes) to a gmake (gnu make) 
and have to include copyright notices on the code). Currently, the code 
still lacks (proper) documentation and some code is a bit ad-hoc, so the 
code is not submission ready. I should be ready in a couple of hours to 
post the code and will post a reply in this thread when it is up.

Ariane