Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at