|
|
Boost : |
From: Greg Colvin (gcolvin_at_[hidden])
Date: 1999-11-30 21:41:57
I have finally got my "weak pointer" ideas into presentable shape.
I got delayed by too much other work, and by some long-delayed
experiments in mixing garbage collection and reference counting.
Comments and criticism are welcome.
------------------------------------------------------------------
Greg Colvin greg_at_[hidden] gcolvin_at_[hidden]
The collection algorithm here is based on Jones' and Lins' description of an old
Fortran algorithm from Christopher. The idea is to use reference counting as the
primary collection technique, but provide a mark-sweep collector as a backup for
objects that form cycles of pointers. I present here a cyclic_ptr class template
modeled on the shared_ptr at www.boost.org.
The idea of a "weak pointer" in most garbage collected systems is that it does
not prevent an object from being collected, but does provide some sort of signal
when the object is collected. The implementation here I called weak_ptr, and it
has an interface much like cyclic_ptr. Its get() function, and thus its T*
conversions, returns 0 if the pointed to object has been collected.
My implementation is based on a recycler handle class that holds the counts, a
pointer to an object, and a pointer to a function for recycling the object. I
would have preferred to use virtual functions, but I needed the handle class to
be a fixed size. Smart pointers hold a pointer to a handle and a pointer to the
object held. You do a mark-sweep collection by calling recycle().
struct recycler {
static void recycle() throw();
private:
template<typename> friend struct recyclable_base;
template<typename> friend struct cyclic_ptr;
template<typename> friend struct weak_ptr;
recycler() : p(0),n(0),n_weak(0),action(0) {}
void* p;
long n, n_weak;
typedef void (*action_fun)(recycler*,bool);
action_fun action;
void do_it();
void decrement();
void decrement_weak();
static recycler* alloc(void*,action_fun);
static void free(recycler*);
};
The recycler handles are allocated and initialized by a recyclable_base class
which holds the pointers to the handle and to the object held.
template<typename T> class recyclable_base {
template<typename> friend struct cyclic_ptr;
template<typename> friend struct weak_ptr;
private:
recycler* ph;
T* p;
recycler* new_handle(T* q) { return recycler::alloc(q,recycle_action); }
static void recycle_action(recycler* ph, bool free);
};
From this base class I derive cyclic_ptr and weak_ptr templates. Note that the
interfaces are based on the current shared_ptr, without the recent improvements
now being discussed. An open question is whether the cyclic_ptr should replace
or supplement shared_ptr.
template<typename T> struct cyclic_ptr : recyclable_base<T> {
typedef T element_type;
long use_count() const throw() { return ph->n; }
bool unique() const throw() { return use_count() == 1; }
explicit cyclic_ptr(T* q=0) { p = q, ph = new_handle(q), ph->n = 1; }
cyclic_ptr(const cyclic_ptr& r) throw() { p = r.p, ph = r.ph, ++ph->n; }
~cyclic_ptr() { ph->decrement(); }
cyclic_ptr& operator=(const cyclic_ptr& r) throw() {
copy(r);
return *this;
}
template<typename U> cyclic_ptr(const cyclic_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n;
}
template<typename U> cyclic_ptr& operator=(const cyclic_ptr<U>& r) throw() {
copy(r);
return *this;
}
template<typename U> cyclic_ptr(std::auto_ptr<U>& r) {
p = r.release(), ph = new_handle(p), ph->n = 1;
}
template<typename U> cyclic_ptr& operator=(std::auto_ptr<U>& r) {
p = r.release(), ph = new_handle(p), ph->n = 1;
return *this;
}
template<typename U> cyclic_ptr(const weak_ptr<U>&) throw();
template<typename U> cyclic_ptr& operator=(const weak_ptr<U>&) throw();
void reset(T* p=0) {
if (--ph->n == 0)
ph->action(ph,true);
ph = new_handle(p), ph->n = 1;
}
T* get() const throw() { return p; }
T& operator*() const throw() { return *get(); }
T* operator->() const throw() { return get(); }
operator T*() const throw() { return get(); }
private:
template<typename> friend struct weak_ptr;
template<typename U> void copy(const recyclable_base<U>&);
};
The weak_ptr interface is the same as cyclic_ptr, except that a weak_ptr can
only be constructed only from a cyclic_ptr or another weak pointer. Note the
test in the get() function.
template<typename T> struct weak_ptr : recyclable_base<T> {
typedef T element_type;
weak_ptr() { p = 0, ph = new_handle(p), ph->n_weak = 1; }
weak_ptr(const weak_ptr& r) throw() { p = r.p, ph = r.ph, ++ph->n_weak; }
~weak_ptr() { ph->decrement_weak(); }
weak_ptr& operator=(const weak_ptr& r) throw() {
copy(r);
return *this;
}
template<typename U> weak_ptr(const weak_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n_weak;
}
template<typename U> weak_ptr& operator=(const weak_ptr<U>& r) throw() {
copy(r);
return *this;
}
template<typename U> weak_ptr(const cyclic_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n_weak;
}
template<typename U> weak_ptr& operator=(const cyclic_ptr<U>& r) throw() {
copy(r);
return *this;
}
void reset(T* p=0) {
if (--ph->n_weak == 0 && ph->n == 0)
ph->action(ph,true);
ph = new_handle(p), ph->n_weak = 1;
}
T* get() const throw() { return ph->n ? p : 0; }
T& operator*() const throw() { return *get(); }
T* operator->() const throw() { return get(); }
operator T*() const throw() { return get(); }
private:
template<typename U> void copy(const recyclable_base<U>&);
};
template<typename T> template<typename U>
inline cyclic_ptr<T>::cyclic_ptr(const weak_ptr<U>& r) throw() {
p = r.p, ph = r.ph, ++ph->n;
}
template<typename T> template<typename U>
cyclic_ptr<T>& cyclic_ptr<T>::operator=(const weak_ptr<U>& r) throw() {
copy(r);
return *this;
}
The actual implementation of the garbage collector is, IMHO, remarkably compact
and reasonably efficient. Some careful hand inlining could help, but would
obscure the logic, so I will wait on that. Handles are pooled in a deque (thus
the need for a fixed-size handle) so that I can efficiently traverse all the
handles in the recycle() function. Note that the handle is not deallocated
until there are no more weak pointers using it.
namespace {
enum { DONE, SCAN, MARK, SWEEP } phase = DONE;
std::deque<recycler> handles;
recycler* free_handle = 0;
}
// maintain pool of available handles in a deque
recycler* recycler::alloc(void* p,action_fun fun) {
recycler* ph;
if (free_handle) {
ph = free_handle;
free_handle = reinterpret_cast<recycler*>(ph->p);
} else {
handles.push_back(recycler());
ph = &*(handles.end() - 1);
}
ph->p = p;
ph->action = fun;
return ph;
}
void recycler::free(recycler* ph) {
delete ph->p;
if (ph->n_weak == 0) {
ph->p = free_handle;
free_handle = ph;
ph->action = 0;
} else
ph->p = 0;
}
The collection proceeds in three phases, SCAN, MARK, and SWEEP. In the SCAN
phase counts are decremented, such that a count will go to zero unless there
is at least one cyclic_ptr to an object that was not dynamically allocated.
The remaining handles with non-zero counts serve as the roots for the MARK
phase in which we mark all roots, and all handles reachable from the roots,
by setting their count to -1. Finally, in the SWEEP phase, we delete objects
with zero counts and restore the counts of the marked objects.
// traverse all handles in deque three times to collect garbage
void recycler::recycle() throw() {
std::deque<recycler>::iterator p, q=handles.end();
// reduce counts to find root pointers
phase = SCAN;
for (p=handles.begin(); p != q; ++p)
if (p->action)
p->action(&*p,false);
// recursively mark all handles accessible from roots
phase = MARK;
for (p=handles.begin(); p != q; ++p)
if (p->action && p->n > 0)
p->action(&*p,false);
// free unreachable objects and restore counts for the rest
phase = SWEEP;
for (p=handles.begin(); p != q; ++p)
if (p->action)
p->action(&*p,p->n == 0);
phase = DONE;
}
The magic in this whole approach is the cyclic_ptr::copy() function, which
implements assignment and also, in case of self-assignment, calls the handle's
do_it() function, which has no effect except during the recycle phases. For
this magic to work we require that objects pointed to by cyclic_ptr have the
expected do-nothing behavior for self-asignment.
template<typename T> template<typename U>
void cyclic_ptr<T>::copy(const recyclable_base<U>& r) {
if (ph != r.ph) {
this->~cyclic_ptr();
p = r.p;
ph = r.ph;
++ph->n;
} else
ph->do_it(); // has no effect except during recycler::recycle()
}
The weak_ptr::copy() is not magic.
template<typename T> template<typename U>
void weak_ptr<T>::copy(const recyclable_base<U>& r) {
this->~weak_ptr();
p = r.p;
ph = r.ph;
++ph->n_weak;
}
The recycler::do_it() function implements the per-handle actions of the recycle
phases. Note the call to action() in the mark phase, which causes the recursive
marking of handles reachable from the marked object.
void recycler::do_it() {
switch (phase) {
case DONE:
break;
case SCAN:
--n; // reduce count
break;
case MARK:
n = -1; // mark as root or reachable from root
action(this,false); // recurse for cyclic_ptr members of this
break;
case SWEEP:
if (n < 0)
n = 1; // restore count for marked object
else if (n > 0)
++n; // restore count
break;
}
}
The action function for a handle does the actual freeing of objects and handles,
and also does the self-assignment that causes the magic required by the SCAN and
MARK phase.
template<typename T>
void recyclable_base<T>::recycle_action(recycler* ph, bool free) {
if (free)
recycler::free(ph);
else if (T* p = reinterpret_cast<T*>(ph->p))
*p = *p; // magically run do_it() on cyclic_ptr members
}
Decrementing the counters is done with these functions, which prevent unwanted
decrementing by destructors called during the SWEEP phase.
void recycler::decrement() {
if (phase == DONE && --n == 0)
action(this,true);
}
void recycler::decrement_weak() {
if (phase == DONE && --n_weak == 0 && n == 0)
action(this,true);
}
So there you have it. All the simplicity of shared_ptr for applications that
don't create cycles, and garbage collection for applications that do, at the
cost of two extra pointers in the handle structure and a small amount of code
for doing the collection, which need not be called by applications that don't
need it.
References:
Richard Jones and Rafael Lins. Garbage Collection.
John Wiley and Sons, 1996.
T. W. Christopher. Reference count garbage collection.
Sofware Practice and Experience, 14(6):503-507, June 1984.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk