Re: [boost] read_write_mutex fundamentally broken in 1.33?

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-09-08 11:43:35

On Sep 8, 2005, at 6:45 AM, John Maddock wrote:

> I've been trying to solve the deadlock problem reported here: 
> http://lists.boost.org/Archives/boost/2005/08/92307.php  but I've 
> simply run into more and more problems, and just about every operation 
> I've tried will deadlock if you try hard enough.
>
> THIS IS NOT GOOD.
>
> Applying Roland Swartz's suggested fix everywhere that looked 
> appropriate initially seemed to fix the issue, but once you move to 
> more complex situations (both readers and writers) then the deadlocks 
> simply come back again.  At this point I've exhausted my understanding 
> of the problem and the design of the lock.  As an aside: it is *very* 
> hard to implement something like this correctly: no amount of 
> debugging will ever get you a reliable system, only a clearly 
> understood design backed up by a solid theoretical understanding of 
> the implementation method (formal methods anyone?).  To be honest I 
> have to question whether it's even a good idea for this to be in Boost 
> (no slur intended towards the implementers of that class, it's the 
> difficulty of the problem that's the issue).
>
> In case anyone wants to pursue this further I'm attaching my current 
> test case, and the current patches I have to the implementation, 
> however, please note that neither this test case, nor the current 
> regression tests are anything like comprehensive, THEY WILL NOT CATCH 
> ALL POSSIBLE PROBLEMS.
>
> Sorry about the capital letters folks, but I suspect we have a 
> "Huston, we have a problem" moment here :-(

I've taken a look at thread_scap.cpp, but not read_write_mutex.cpp.

I don't have any suggestions on why the deadlock except to say that I 
see nothing wrong with your test, and have run it without any 
significant problems on a Freescale implementation of read/write locks.

I do have a comment about the interface of the read/write mutex/lock 
though.

I have a use case that looks like:

class A
{
public:
     // ...
     A& operator=(const A& a);
     // ...
private:
     typedef ... Mutex;
     typedef Mutex::... WriteLock;
     typedef Mutex::... ReadLock;

     mutable Mutex mut_;
     // ...
};

A&
A::operator=(const A& a)
{
     if (this != &a)
     {
         // Here I want to read-lock "a" and write-lock "*this", and
         // of course not dead-lock.  How do I do this?
     }
     return *this;
}

A naive (incorrect) implementation using the interface I gleaned from 
thread_scap.cpp would look like:

class A
{
public:
     // ...
     A& operator=(const A& a);
     // ...
private:
     typedef timed_read_write_mutex Mutex;
     typedef Mutex::scoped_timed_read_write_lock WriteLock;
     typedef Mutex::scoped_timed_read_write_lock ReadLock;

     mutable Mutex mut_;
     // ...
};

A&
A::operator=(const A& a)
{
     if (this != &a)
     {
         ReadLock  rlock(a.mut_, read_write_lock_state::unlocked);
         WriteLock wlock(mut_, read_write_lock_state::unlocked);
         rlock.read_lock();
         wlock.write_lock();
         // OOPS! DEADLOCK!
     }
     return *this;
}

You can't lock two locks willy-nilly like this.  So ideally what I'd 
like to do is create a generic lock function that will lock multiple 
locks without danger of deadlock:

template <class TryLock1, class TryLock2>
void
lock(TryLock1& l1, TryLock2& l2);

and maybe also:

template <class TryLock1, class TryLock2, class TryLock3>
void
lock(TryLock1& l1, TryLock2& l2, TryLock3& l3);

and etc.

And then call that:

A&
A::operator=(const A& a)
{
     if (this != &a)
     {
         ReadLock  rlock(a.mut_, read_write_lock_state::unlocked);
         WriteLock wlock(mut_, read_write_lock_state::unlocked);
         lock(rlock, wlock);  // won't deadlock
         // Ok!
     }
     return *this;
}

Now I can solve my two-lock locking algorithm once and for all in 
generic code, and reuse it whenever, wherever.

Problem:  With the current interface, my "generic" lock algorithm is no 
longer generic.  It has to know about read_lock() and write_lock(), 
even though these concepts have absolutely nothing to do with how you 
lock two locks while avoiding deadlock.

Here is how I've solved this problem:

class A
{
public:
     // ...
     A& operator=(const A& a);
     // ...
private:
     typedef Metrowerks::rw_mutex Mutex;
     typedef Mutex::scoped_lock WriteLock;
     typedef Mutex::sharable_lock ReadLock;

     mutable Mutex mut_;
     // ...
};

A&
A::operator=(const A& a)
{
     if (this != &a)
     {
         ReadLock rlock(a.mut_, defer_lock);
         WriteLock wlock(mut_, defer_lock);
         lock(rlock, wlock);
         // Ok!
     }
     return *this;
}

That is, there is a read-lock and there is a write-lock, and they are 
not the same type.  These two different types have a generic locking 
interface: lock(), unlock(), try_lock(), etc.  That is, they meet a 
"lock concept".  Now my two-lock-deadlock-avoiding function doesn't 
need to know about read locks and write locks.  All it has to know is 
the generic interface of locks (the lock concept).  It will work with 
two read locks, two write locks, a read lock and a write lock, or any 
other two types of locks that meet the lock concept.

See http://home.twcny.rr.com/hinnant/cpp_extensions/threads_move.html

for details of this interface.  The important part (for this 
discussion) is that there are several types of locks, but they all have 
this interface (or a subset of it):

     void lock();
     bool try_lock();
     bool timed_lock(const elapsed_time& elps_time);
     void unlock();

I'm arguably missing:

     bool timed_lock(const universal_time& unv_time);

but that's beside the point.

The point is that generic locking code is going to be important, 
especially when read/write locks are thrown into the mix (upgradable 
locks too anyone?).  Without a generic interface, generic locking code 
is going to be overly cumbersome to write.  The use case I have above 
is most basic (surely there will be many classes with a per-object lock 
that want to write a thread-safe assignment operator?), and it already 
begs for a generic lock algorithm.

Sorry, but:  Houston, we have an even bigger problem...

-Howard