Re: [boost] [thread] upgrading read lock to write lock

Subject: Re: [boost] [thread] upgrading read lock to write lock
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-02-06 22:34:31

On Feb 6, 2011, at 7:04 PM, Edd Dawson wrote:

> What I'm trying to achieve is to be able to turn a read lock in to a write lock without forfeiting my 'turn'.
> 
> Specifically, I'm implementing a kind of thread-local storage. In order to do so, I have a map whose keys are thread::ids. I'd like to take a read lock while looking to see if there's something in the map for the current thread and if so, return the associated value. Otherwise, I want to upgrade to a write lock so I can fill in a value for the current thread before returning it.
> 
> I guess I'd like to know:
> 
> 1. Is this a realistic thing to expect to be able to achieve? I'm under the impression that this is the purpose of an upgradable locking facility. Perhaps this isn't the case, though?

I'm not positive if upgradable locks fit your use case or not, mainly because I don't know enough about your use case.  If *every* thread follows the algorithm you describe, then it probably won't work (except maybe as described below).  The problem is that if you have more than one thread holding a shared lock, you can only promise one of those threads that they can upgrade to a unique lock without forfeiting their shared lock.  Otherwise you get deadlock when two of the threads holding shared locks each wait for the other to release their shared lock so that they can upgrade to unique ownership.

The way the upgrade_lock is meant to work is that a bunch of threads are able to obtain a shared_lock, and at the same time *one* thread obtains an upgrade_lock, which shares ownership with the other threads holding a shared_lock.  Then if and when the thread with the upgrade_lock wants unique ownership, then he converts the upgrade_lock to a unique_lock.  This operation blocks until all of the threads with the shared_locks give up their ownership.  And then the conversion from upgrade to unique completes.

A compromise solution (which boost doesn't support, but http://home.roadrunner.com/~hinnant/mutexes/locking.html does), is for a bunch of threads to hold shared_locks, and they can *all* /try/ to convert their shared_locks to either upgrade_locks or unique_locks.  The conversion to upgrade_lock can succeed for only one thread.  The conversion to unique_lock will succeed only if no other threads are currently holding a shared_lock (or upgrade_lock), and no thread is already blocked waiting for a unique_lock.  In this scenario, the logic has to have something to do if the attempted conversion from shared fails.  Simply turning around and trying again is simply going to implement an expensive spin lock at best, and deadlock at worst.

Bringing this back to your problem, upgradeable locks will only work if there are some threads which need read access and don't ever want to upgrade to write access, or can at least choose to do something else if a try-conversion fails.  A thread with an upgrade_lock can share threads holding shared_locks.  But a thread with an upgrade_lock can not share with another thread needing an upgrade_lock.

> 
> 2. The boost-centric code that I posted was my attempt at doing this. What makes it wrong?

int main()
{
   using namespace boost;

   shared_mutex m;
   shared_lock<shared_mutex> readlock(m);
   // reads go here
   // ...

   // Ah, need to write actually.
   // Upgrade to a write lock now.
   upgrade_lock<shared_mutex> uglock(m);

----
You have called m.lock_shared() followed by m.lock_upgrade().  I haven't even thought about what this does to a mutex, but it can't be good.  It is like calling m.lock() twice on a non-recursive mutex.  It is going to put it into an undefined state.
There is no unconditional conversion from shared_lock to upgrade_lock (in either implementation), though in my implementation their are try- and timed-versions of this conversion.  But it would be done with this syntax:
   // use upgrade_mutex everywhere, shared_mutex can't change ownership modes
   ...
   // Ah, need to write actually.
   // Upgrade to a write lock now.
   upgrade_lock<upgrade_mutex> uglock(std::move(readlock), std::try_to_lock);
   if (uglock.owns_lock())
   {
       // has upgrade ownership
       // this shares with other shared ownerships, but not with other upgrade or unique ownerships
       unique_lock<upgrade_mutex> writelock(std::move(uglock)); // blocks until all shared_locks are unlocked
       // has unique access now
   }
   else
       // unable to convert to upgrade ownership, still has shared ownership
-Howard