Re: [boost] Lock unification (shared vs. upgradable)

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2004-08-07 11:54:13

Thanks for the thought and alternative suggestions.

On Aug 6, 2004, at 3:15 PM, Bronek Kozicki wrote:

> Indeed, there is a difference in semantics of lock operations. 
> However, this difference could be expressed with different means. I 
> can imagine two different designs:
>
> * single template class
> template <typename Mutex, bool Upgradable = false>
> class shared_lock {/* ... */};
>
> this design does not change current design much, but allows for easier 
> changes in code when shared lock needs to be updated to upgradable 
> one.

<nod>  This isn't the first time I've been faced with the question of:

Do you name it X and Y, or do you name it X<T> and X<U>?

And I've come down in favor of both answers at various times.  
Exploring...

A:

void read_write(rw_mutex& m)
{
     upgradable_lock<rw_mutex> read_lock(m);
     bool b = compute_expensve_result();
     if (b)
     {
         scoped_lock<rw_mutex> write_lock(move(read_lock));
         modify_state(b);
     }
}

or B:

void read_write(rw_mutex& m)
{
     sharable_lock<rw_mutex, true> read_lock(m);
     bool b = compute_expensve_result();
     if (b)
     {
         scoped_lock<rw_mutex> write_lock(move(read_lock));
         modify_state(b);
     }
}

And of course if the EWG gives us template aliasing, then we could have 
it both ways. :-)

I have a preference for A because it more explicitly says what is going 
on.  It is easier to search for A than for B in a large code base.  And 
the semantics between the upgradable functionality and the sharable 
functionality are subtly different enough that I think code should 
distinguish the two fairly clearly.

> * extended interface of shared_lock
> template <typename Mutex>
> class shared_lock
> {
> public:
> // new members only
>   shared_lock(Mutex&, const upgradable_t&);
>
>   void lock(const upgradable_t&);
>   bool try_lock(const upgradable_t&);
>   bool try_lock(const timespan&, const upgradable_t&);
>
>   bool upgradable() const;
>
>   scope_lock<Mutex> upgrade() throw (thread::non_upgradable);
>   scope_lock<Mutex> try_upgrade() throw (thread::non_upgradable);
>   scope_lock<Mutex> try_upgrade(const timespan&) throw 
> (thread::non_upgradable);
> }
>
> here decision to lock with ability to upgrade may be deffered to point 
> where mutex is actually locked, which does not have to be place where 
> lock object is created (assuming that you created deffered lock). It 
> also gives more flexibiliy in runtime. You may even create shared lock 
> (non-deffered), then release it and lock again, this time with ability 
> to upgrade - all in one shared_lock variable. Proposed interface does 
> not have atomic function to transform from shared non-upgradable lock 
> to upgradable one in order to avoid deadlocks.

Consider the following scenario:

A function takes two objects, needs read access to both, and then might 
need to atomically write to only the first:

void
foo(T& t, U& u)
{
     // lock t and u for reading
     T::mutex::upgradable_lock t_read_lock(t.mutex(), defer_lock);
     U::mutex::sharable_lock   u_read_lock(u.mutex(), defer_lock);
     lock(t_read_lock, u_read_lock);  // generic lock algorithm

     // read from t and u
     bool b = t.expensive_compute(u);
     if (b)
     {
         // unlock u and lock t for writing
         u_read_lock.unlock();
         T::mutex::scoped_lock t_write_lock(move(t_read_lock));

         // write to t with previously read state in b
         t.update(b);
     }
}

Now if upgradable_lock and sharable_lock are merged, then the merged 
lock needs different syntax for lock-sharable and lock-upgradable, as 
you show in your second proposal.  But when that happens, the generic 
lock(lock1,lock2) function no longer works:

template <class TryLock1, class TryLock2>
void
lock(TryLock1& l1, TryLock2& l2)
{
     while (true)
     {
         l1.lock();
         if (l2.try_lock())
             break;
         l1.unlock();
         l2.lock();
         if (l1.try_lock())
             break;
         l2.unlock();
     }
}

or if you prefer:

template <class TryLock1, class TryLock2>
void
lock(TryLock1& l1, TryLock2& l2)
{
     if (l1.mutex() < l2.mutex())
     {
         l1.lock();
         l2.lock();
     }
     else
     {
         l2.lock();
         l1.lock();
     }
}

Instead you would need a different lock(l1,l2) function for every 
combination of sharable/upgradable (and scoped too if that were also 
merged).  Or worse yet, you just replicate one of the above algorithms 
on the spot every time you need it.

Another advantage to the separate locks:  Consider the following 
potential mistake which could have been made in coding the above 
example:

    T::mutex::scoped_lock t_write_lock(move(u_read_lock)); // oops, 
should be t_read_lock!

If sharable and upgradable are merged, then the above mistake could 
transform itself from a compile time error into a run time error.  
Depending on how things are implemented, it might throw an exception, 
or it might deadlock, it might corrupt memory, or even worse, it might 
work most of the time.

-Howard