Channels ▼
RSS

Design

Weak References as Object Accessors


Now let's look at the implementation. The repeated motif here will be the reference counting, wrapped in the class Hold, whose interface is in the Listing Three. It takes care of all its internal synchronization.

class Hold {
public:
    Hold();
    ~Hold();
    void getHold(); // increase the reference count
    void releaseHold(); // decrease the reference count
    void wait(); // wait until the reference count drops to 0
};
Listing Three

The WeakRef can use a Hold to keep track of the grabs on it. It would nicely provide the recursive grabbing. Later, when the RefTarget invalidates the WeakRef and needs to make sure that nobody has any grabs any more, it would wait on that Hold.

What else is needed? Obviously, RefTarget needs to keep track of its WeakRefs, allowing to invalidate them later. This can be done with an STL list, or with just a classic old-fashioned list. RefTarget would have the head of the list and each WeakRef would have a pointer to the next WeakRef. For convenience of removal of elements from the list, an "one-and-a-half-linked list" would do well: essentially a double-linked list but with the back pointer pointing to the pointer to this element, instead of being a pointer to the previous element. It doesn't allow going back through the list easily but gives enough information to delete the elements in place.

RefTarget would also need to keep a pointer to the owner object, and a flag whether the object is still valid. Once the object enters its destructor, the RefTarget::invalidate() method would reset this flag and prevent the creation of the new references. Then it can go at a leisure and invalidate the existing references. Otherwise it could be a potentially endless race of new references created while trying to collect the old ones.

The WeakRef needs to keep a pointer to its RefTarget, for two purposes. First, when it gets deleted, it must tell the RefTarget about that and be removed from the list. Second, when it gets copied, it must ask RefTarget to issue a new WeakRef.

Both RefTarget and WeakRef must have a mutex to protect their contents during concurrent access. And the last non-trivial item is the synchronization on deletion. It will be done through another instance of Hold and discussed in detail below. In the end, the class members amount to what is in Listing Four.

class RefTarget {
    ...
protected:
    pthread_mutex_t mutex_; // controls all access
    Hold hold_;
    bool valid_; // gets reset on invalidation
    WeakRef *rlist_; // head of the list of references
    void *owner_; // value to pass to the weak refs
    ...
};
class WeakRef {
    ...
protected:
    // a sort-of-double-linked list, access controlled by target's mutex
    WeakRef *next_;
    WeakRef **prevp_;
    pthread_mutex_t mutex_; // controls all access
    Hold hold_; // keeps track of holds from RefTarget
    Hold grabs_; // keep track of the grabs
    RefTarget *target_; // reset to 0 on invalidation
    ...
};
Listing Four

The creation and grabbing of references is straightforward; see Listing Five. The only important thing to remember is the avoidance of deadlocks due to circular dependencies. When RefTarget manipulates its list of references, it must keep its own mutex and when it calls the operations on WeakRef, they may acquire the WeakRef mutex. This means that when WeakRef holds its mutex, it must never call back into RefTarget. It must release its mutex first.

RefTarget::RefTarget(void *owner) : // this pointer will be held in the weak references
    valid_(true), rlist_(0), owner_(owner)
{
    pthread_mutex_init(&mutex_, NULL);
}
WeakRef *RefTarget::newWeakRef() // create a new weak reference
{
    WeakRef *wr;
    wr = new WeakRef(this);
    pthread_mutex_lock(&mutex_);
    if (!valid_) {
        if (wr->invalidate1())
            wr->invalidate2();
    } else { // add to the list
        if (rlist_) {
            rlist_->prevp_ = &wr->next_;
        }
        wr->next_ = rlist_;
        wr->prevp_ = &rlist_;
        rlist_ = wr;
    }
    pthread_mutex_unlock(&mutex_);
    return wr;
}
WeakRef::WeakRef(RefTarget *target) : // called from copy() and from RefTarget
    next_(0), prevp_(0), target_(target)
{
    pthread_mutex_init(&mutex_, NULL);
}
WeakRef *WeakRef::copy() // create a copy of this reference
{
    WeakRef *nwr;
    grab();
    pthread_mutex_lock(&mutex_);
    RefTarget *t = target_;
    pthread_mutex_unlock(&mutex_);
    if (t)
        nwr = t->newWeakRef();
    else
        nwr = new WeakRef(0);
    release();
    return nwr;
}
void *WeakRef::grab() // make the reference strong, return its current value
{
    grabs_.getHold();
    pthread_mutex_lock(&mutex_);
    void *owner = target_? target_->owner_ : 0;
    pthread_mutex_unlock(&mutex_);
    return owner;
}
void WeakRef::release() { // release the reference back to weak
    grabs_.releaseHold();
}
Listing Five

The new weak references are always created by RefTarget::newWeakRef(), which keeps thack of all of them on its list. Even the copy() method calls there. Except in case when the reference has been invalidated; then the copy simply creates and returns another invalid reference. RefTarget::newWeakRef() does the same: if the target has already been invalidated, the returned new reference is invalid too. This approach is a little more tricky to implement but from the API standpoint it's better than returning a NULL instead of the new reference. This way there is no need to check the result of creation or copying. It would always be an object. The contents of that object would need to be checked during grabbing it but that check must be done anyway. Even if a valid reference had been created, it may get invalidated before it gets grabbed.

Invalidation is a more interesting task. It is shown in the Listing Six. As mentioned before, the actual destruction of the target's contents is done in the function invalidate() that must be called at the start of the child class destructor. The target's destructor only checks that the invalidation has been done, and aborts the process if it was not.

RefTarget::~RefTarget()
{
    if (valid_) {
        fprintf(stderr, "~RefTarget: not invalidated!\n");
        abort();
    }
    pthread_mutex_destroy(&mutex_);
}
void RefTarget::invalidate() // called from the subclass destructor
{
    pthread_mutex_lock(&mutex_);
    valid_ = false;
    while (rlist_) {
        WeakRef *wr = rlist_;
        rlist_ = rlist_->next_;
        if (rlist_)
            rlist_->prevp_ = &rlist_;
        wr->prevp_ = 0;
        wr->next_ = 0;
        bool code = wr->invalidate1();
        if (code) {
            pthread_mutex_unlock(&mutex_);
            wr->invalidate2();
            pthread_mutex_lock(&mutex_);
        }
    }
    pthread_mutex_unlock(&mutex_);
    hold_.wait();
}
void RefTarget::freeWeakRef(WeakRef *wr) // notification from a WeakRef that it gets destroyed
{
    // remove the ref from the list
    pthread_mutex_lock(&mutex_);
    if (wr->prevp_) {
        *wr->prevp_ = wr->next_;
        if (wr->next_)
            wr->next_->prevp_ = wr->prevp_;
        wr->prevp_ = 0;
        wr->next_ = 0;
    }
    pthread_mutex_unlock(&mutex_);
}
WeakRef::~WeakRef()
{
    pthread_mutex_lock(&mutex_);
    RefTarget *t = target_;
    target_ = 0;
    if (t)
        t->hold_.getHold();
    pthread_mutex_unlock(&mutex_);
    hold_.wait();
    if (t) {
        t->freeWeakRef(this);
        t->hold_.releaseHold();
    }
    pthread_mutex_destroy(&mutex_);
}
bool WeakRef::invalidate1() // called from RefTarget invalidation
{
    pthread_mutex_lock(&mutex_);
    RefTarget *t = target_;
    target_ = 0;
    if (t)
        hold_.getHold();
    pthread_mutex_unlock(&mutex_);
    return (t != 0);
}
void WeakRef::invalidate2() // called if invalidate1() returned true
{
    grabs_.wait();
    hold_.releaseHold();
}
Listing Six

The complication on destruction is that the target may get destroyed before the reference, of the reference may be destroyed before the target, or they may be destroyed at the same time. It makes the synchronization tricky. Getting this right in production took me a few attempts. Hopefully, things stayed right when transferring from the production to the example code.

Because of this, all the destruction in both directions is done in stages:

  1. Mark own object as not being valid any more, clear (but remember) any links to the peer object.
  2. If the links to the peer object were already cleared, then the tie with the peer is already broken though the break-up might be still in progress (then the peer will currently have a hold on this object). Otherwise get a hold on the peer, then ask the peer to clear the link on its side.
  3. At this point the links are cleared both ways. If keeping a hold on the peer, release that hold.
  4. Wait for any peer's holds on this object to be released.

This disentangles two objects while making sure that none of the objects gets freed while still being used. Of course, the target and the reference are in an asymmetric relationship, and their destruction sequences are somewhat different.

The differences have to do mostly with the different character of the links and with the lock ordering to prevent the deadlocks. The weak reference has to release its own mutex before calling any operation that acquires the target mutex. On the other hand, the target must not get stuck for indefinite time while holding its mutex. This last requirement leads to the WeakRef invalidation being done in two steps. Invalidate1() does the invalidation as such and returns the boolean value showing whether it has any ongoing grabs. If so, invalidate2() is called to wait for any grabs to be released. The target releases its mutex while calling invalidate2().

Note that if the target object is already invalid, RefTarget::newWeakRef() invalidates the newly created reference without releasing its own mutex. This is fine because there are guaranteed to be no grabs, and no open-ended wait would be involved.

Listing Seven provides the complete implementation of the techniques presented here. This pattern was tricky to implement, but once done, all the complexity is hidden inside and the complicated multithreaded programs become less complex.

 #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

class RefTarget;
class WeakRef;

class Hold {
public:
	Hold() : count_(0), waiting_(0)
	{ 
		pthread_mutex_init(&mutex_, NULL);
		pthread_cond_init(&cond_, NULL);
	}
	
	~Hold()
	{
		pthread_mutex_destroy(&mutex_);
		pthread_cond_destroy(&cond_);
	}

	void getHold() 
	{
		pthread_mutex_lock(&mutex_);
		++count_;
		pthread_mutex_unlock(&mutex_);
	}

	void releaseHold() 
	{
		pthread_mutex_lock(&mutex_);
		if (--count_ == 0 && waiting_ != 0)
			pthread_cond_broadcast(&cond_);
		pthread_mutex_unlock(&mutex_);
	}

	void wait()
	{
		pthread_mutex_lock(&mutex_);
		while(count_ != 0) {
			++waiting_;
			pthread_cond_wait(&cond_, &mutex_);
			--waiting_;
		}
		pthread_mutex_unlock(&mutex_);
	}

protected:
	pthread_mutex_t mutex_; // access to count_
	pthread_cond_t cond_; // signalled when count_ drops to 0
	int count_; // count of holds
	int waiting_; // count of threads waiting for release

private: // prevent the copy constructors and assignments
	Hold(const Hold&);
	void operator=(const Hold&);
};

class RefTarget {
	friend class WeakRef;
public:
	RefTarget(void *owner); // this pointer will be held in the weak references
	~RefTarget();

	WeakRef *newWeakRef(); // create a new weak reference

protected:
	void invalidate(); // called from the subclass destructor
	void freeWeakRef(WeakRef *wr); // notification from a WeakRef that it gets destroyed

	pthread_mutex_t mutex_; // controls all access
	Hold hold_;
	bool valid_; // gets reset on invalidation
	WeakRef *rlist_; // head of the list of references
	void *owner_; // value to pass to the weak refs

private: // prevent the default and copy constructors and assignments
	RefTarget();
	RefTarget(const RefTarget&);
	void operator=(const RefTarget&);
};

class WeakRef {
	friend class RefTarget;
public:
	~WeakRef();

	WeakRef *copy(); // create a copy of this reference

	void *grab(); // make the reference strong, return its current value
	void release(); // release the reference back to weak
	
protected:
	WeakRef(RefTarget *target); // called from copy() and from RefTarget

	bool invalidate1(); // called from RefTarget invalidation
	void invalidate2(); // called if invalidate1() returned true

	// a sort-of-double-linked list, access controlled by target's mutex
	WeakRef *next_;
	WeakRef **prevp_;

	pthread_mutex_t mutex_; // controls all access
	Hold hold_; // keeps track of holds from RefTarget
	Hold grabs_; // keep track of the grabs
	RefTarget *target_; // reset to 0 on invalidation

private: // prevent the default and copy constructors and assignments
	// (they may be added but the code is simpler without them)
	WeakRef();
	WeakRef(const WeakRef&);
	void operator=(const WeakRef&);
};

// ------------------ methods --------------------------

RefTarget::RefTarget(void *owner) : // this pointer will be held in the weak references
	valid_(true), rlist_(0), owner_(owner)
{
	pthread_mutex_init(&mutex_, NULL);
}

RefTarget::~RefTarget()
{
	if (valid_) {
		fprintf(stderr, "~RefTarget: not invalidated!\n");
		abort();
	}
	pthread_mutex_destroy(&mutex_);
}

WeakRef *RefTarget::newWeakRef() // create a new weak reference
{
	WeakRef *wr;
	wr = new WeakRef(this);
	pthread_mutex_lock(&mutex_);
	if (!valid_) {
		if (wr->invalidate1())
			wr->invalidate2();
	} else { // add to the list
		if (rlist_) {
			rlist_->prevp_ = &wr->next_;
		}
		wr->next_ = rlist_;
		wr->prevp_ = &rlist_;
		rlist_ = wr;
	}
	pthread_mutex_unlock(&mutex_);
	return wr;
}

void RefTarget::invalidate() // called from the subclass destructor
{
	pthread_mutex_lock(&mutex_);
	valid_ = false;
	while (rlist_) {
		WeakRef *wr = rlist_;
		rlist_ = rlist_->next_;
		if (rlist_)
			rlist_->prevp_ = &rlist_;
		wr->prevp_ = 0;
		wr->next_ = 0;
		bool code = wr->invalidate1();
		if (code) {
			pthread_mutex_unlock(&mutex_);
			wr->invalidate2();
			pthread_mutex_lock(&mutex_);
		}
	}
	pthread_mutex_unlock(&mutex_);
	hold_.wait();
}

void RefTarget::freeWeakRef(WeakRef *wr) // notification from a WeakRef that it gets destroyed
{
	// remove the ref from the list
	pthread_mutex_lock(&mutex_);
	if (wr->prevp_) {
		*wr->prevp_ = wr->next_;
		if (wr->next_)
			wr->next_->prevp_ = wr->prevp_;
		wr->prevp_ = 0;
		wr->next_ = 0;
	}
	pthread_mutex_unlock(&mutex_);
}

WeakRef::~WeakRef()
{
	pthread_mutex_lock(&mutex_);
	RefTarget *t = target_;
	target_ = 0;
	if (t)
		t->hold_.getHold();
	pthread_mutex_unlock(&mutex_);
	hold_.wait();
	if (t) {
		t->freeWeakRef(this);
		t->hold_.releaseHold();
	}
	pthread_mutex_destroy(&mutex_);
}

WeakRef *WeakRef::copy() // create a copy of this reference
{
	WeakRef *nwr;
	grab();
	pthread_mutex_lock(&mutex_);
	RefTarget *t = target_;
	pthread_mutex_unlock(&mutex_);
	if (t)
		nwr = t->newWeakRef();
	else
		nwr = new WeakRef(0);
	release();
	return nwr;
}

void *WeakRef::grab() // make the reference strong, return its current value
{
	grabs_.getHold();
	pthread_mutex_lock(&mutex_);
	void *owner = target_? target_->owner_ : 0;
	pthread_mutex_unlock(&mutex_);
	return owner;
}
void WeakRef::release() { // release the reference back to weak
	grabs_.releaseHold();
}

WeakRef::WeakRef(RefTarget *target) : // called from copy() and from RefTarget
	next_(0), prevp_(0), target_(target)
{
	pthread_mutex_init(&mutex_, NULL);
}

bool WeakRef::invalidate1() // called from RefTarget invalidation
{
	pthread_mutex_lock(&mutex_);
	RefTarget *t = target_;
	target_ = 0;
	if (t)
		hold_.getHold();
	pthread_mutex_unlock(&mutex_);
	return (t != 0);
}

void WeakRef::invalidate2() // called if invalidate1() returned true
{
	grabs_.wait();
	hold_.releaseHold();
}

// ------------------------- test -------------------------

pthread_mutex_t mutex; // for deletion

class Worker : public RefTarget {
public:
	Worker() : RefTarget(this)
	{ }

	~Worker()
	{
		RefTarget::invalidate();
		fprintf(stderr, "Worker: destroying %p\n", this);
	}

	static void *execute(void *arg)
	{
		Worker *w = (Worker *)arg;
		fprintf(stderr, "Worker: waiting %p\n", w);
		pthread_mutex_lock(&mutex);
		pthread_mutex_unlock(&mutex);
		delete w;
	}
};

void *
client1(void *arg)
{
	WeakRef *ref = (WeakRef *)arg;
	fprintf(stderr, "client1: weak ref %p\n", ref);
	for (int i = 0; i < 5; i++) {
		void *w = ref->grab();
		fprintf(stderr, "client1: got %p\n", w);
		sleep(1);
		fprintf(stderr, "client1: release\n");
		ref->release();
		sched_yield(); // Linux mutexes aren't honest...
	}
	delete ref;
}

void *
client2(void *arg)
{
	WeakRef *ref = (WeakRef *)arg;
	fprintf(stderr, "client2: weak ref %p\n", ref);
	fprintf(stderr, "client2: waiting\n");
	pthread_mutex_lock(&mutex);
	pthread_mutex_unlock(&mutex);
	delete ref;
	fprintf(stderr, "client2: deleted ref\n");
}

int main()
{
	pthread_t tw, tc1, tc2;

	pthread_mutex_init(&mutex, NULL);

	Worker *w = new Worker;
	WeakRef *ref = w->newWeakRef();

	pthread_mutex_lock(&mutex);

	pthread_create(&tw, NULL, Worker::execute, (void *)w);
	pthread_create(&tc1, NULL, client1, (void *)ref->copy());
	pthread_create(&tc2, NULL, client2, (void *)ref->copy());
	delete ref;

	sleep(3);
	pthread_mutex_unlock(&mutex);

	fprintf(stderr, "joining threads\n");
	pthread_join(tw, NULL);
	pthread_join(tc1, NULL);
	pthread_join(tc2, NULL);

	return 0;
}

/* 
The test output may vary depending on the scheduling order
but in general should be like:

Worker: waiting 0x503010
client1: weak ref 0x503300
client1: got 0x503010
client2: weak ref 0x503540
client2: waiting
client1: release
client1: got 0x503010
client1: release
client1: got 0x503010
joining threads
client2: deleted ref
client1: release
Worker: destroying 0x503010
client1: got (nil)
client1: release
client1: got (nil)
client1: release

*/
Listing Seven


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video