Re: [boost] [thread] On shared_mutex

Subject: Re: [boost] [thread] On shared_mutex
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2010-11-29 12:10:04

On Nov 29, 2010, at 5:05 AM, Anthony Williams wrote:

>> 4.  boost allows implicit conversions between the lock types.  N2406
>> made these conversions explicit.  Rationale: changing the ownership
>> mode of a mutex is something that should be well documented in the
>> code.
> 
> If it does, this is a bug --- the conversions are supposed to require
> explicit move operations.

I think we still have a difference here.  With boost you can:

(disclaimer:  I'm coding without testing against my better judgement! :-))

upgrade_mutex mut;
...
upgrade_lock<upgrade_mutex> ul(mut);
...
unique_lock<upgrade_mutex> lk;
...
lk = move(ul);   // here is the difference

And in the ting version the last line looks like:

lk = unique_lock<upgrade_mutex>(move(ul));

I.e. The type-change must be called out explicitly.  Perhaps it is just my paranoia, but this library is novel in its ability to change the ownership mode of the mutex, and so people may not be expecting it.  So I'm trying to make the change of ownership explicit.  Note that this also makes the syntax more consistent when you want to do a timed- or try-conversion:

lk = unique_lock<upgrade_mutex>(move(ul), milliseconds(30));

The difference is mainly visible in assignment.  For construction the difference is more stylistic:

boost:

unique_lock<upgrade_mutex> lk = move(ul);

ting:

unique_lock<upgrade_mutex> lk(move(ul));

However allowing the former leads to the implicit assignment expression.

>> I have an updated implementation of <shared_mutex> (under the boost
>> license) here:
>> 
>> http://home.roadrunner.com/~hinnant/mutexes/shared_mutex
>> http://home.roadrunner.com/~hinnant/mutexes/shared_mutex.cpp
>> 
>> There is a tutorial-style description of this library here:
>> 
>> http://home.roadrunner.com/~hinnant/mutexes/locking.html
> 
> Firstly, thank you for providing an updated implementation and rationale
> under the BSL.

And thank you for reviewing it! :-)

> Secondly, though I have some comments on the design choices (which I
> will outline below), I am less convinced of the utility of the
> shared_mutex functionality in its entirety, and quite glad we didn't
> standardize it. Before commenting on the design choices, I will attempt
> to outline why I am less convinced of its utility overall.
> 
> The cost of locking a shared_mutex is higher than that of locking a
> plain std::mutex, even for the reader threads. This is a necessary part
> of the functionality --- there are more possible states of a
> shared_mutex than a mutex, and the code must handle them correctly. This
> cost comes in both the size of the object (which in both your
> implementation and my POSIX implementation includes both a plain mutex
> and a condition variable), and in the performance of the lock and unlock
> operations.
> 
> Also, the shared_mutex is a point of contention, and thus not
> scalable. Locking a shared_mutex necessarily modifies the state of the
> mutex, even for a read lock. Consequently, the cache line holding the
> shared_mutex state must be transferred to whichever processor is
> performing a lock or unlock operation.
> 
> If you have a lot of threads performing frequent, short read operations,
> then on a multiprocessor system this can lead to a lot of cache
> ping-pong, which will considerably impact the performance of the
> system. In this case, you may as well adopt the simpler design of just
> using a plain mutex, as the readers are essentially serialized anyway.
> 
> If the reads are not frequent, then there is no contention, so you don't
> need to worry about concurrent readers, and a plain mutex will suffice
> for that scenario anyway.
> 
> If the read operations are time consuming, then the consequence of this
> contention is less visible, since it is dwarfed by the time spent whilst
> holding the read lock. However, performing time consuming operations
> whilst holding a lock is a design smell.
> 
> In the vast majority of cases, I think that there are better
> alternatives to a shared_mutex. These may be a plain mutex, the atomic
> support of shared_ptr, the use of a carefully constructed concurrent
> container, or something else, depending on context.

Like recursive mutexes I've tried to leave the goodness or badness of shared mutexes out of the discussion.  Also like recursive mutexes I've seen enough use of shared mutexes in other languages and libraries to know that people want them and will use them (e.g. pthread_rwlock_t).  So I've just started with a given that we need shared mutexes, and am trying to make them as useful as possible.  Because of Joaquín's post about a recursive shared mutex (on boost-users), I find myself wondering if we shouldn't provide that as well, though I personally avoid recursive locking.  Allowing recursion of the shared ownership looks really expensive to me.  But I digress...

> Now for the design comments.
> 
> I can see why you chose to separate shared_mutex and upgrade_mutex both
> in the original design and this one, but I felt that the benefits were
> not worth the proliferation of mutex types. I'm not so strongly attached
> to that feeling as I was, so you may yet convince me ;-)

Working on it. :-)  I think for me it is because of the novelty of the ownership change.  Though this feature was motivated by people asking to convert shared ownership to exclusive ownership (and being repeatedly and correctly told it would cause deadlock), I've not seen this feature implemented elsewhere.  Thus the lack of conversion functionality in shared_mutex is a pre-emptive defense against those who will see "conversion" and immediately condemn the entire library.  My response to that hypothetical objection is:  just use shared_mutex then, you're safe.

> However, the omission of shared_lock -> upgrade_lock conversion was
> deliberate. Just as you clearly feel that shared_mutex and upgrade_mutex
> deserve to be distinct types, I feel that a shared_lock should always
> remain a shared_lock. This is why upgrade_lock is a distinct type. If
> you allow a shared_lock -> upgrade_lock transition then you might as
> well allow shared_lock -> unique_lock and omit upgrade_lock
> entirely. I see from the diagram that you actually consider the lack of
> a conversion from shared_lock -> unique_lock a problem; I consider it a
> feature.

Here I think we need to be very careful about distinguishing locking ownership modes (exclusive, upgrade and shared), and lock types (unique_lock, upgrade_lock and shared_lock).  Your paragraph above appears to mix these two to the point that I'm not positive I completely understand your point (and I really need to).

For example I agree that upgrade_lock should be distinct type, and have made it so.  However I disagree that allowing an upgrade_mutex to change ownership modes from shared to upgrade (in try- and timed- operations only) impacts the design to have separate types for shared_lock and upgrade_lock.  Here is the syntax I'm using for this ownership change:

ting::upgrade_mutex mut;
...
ting::shared_lock<ting::upgrade_mutex> S(mut);
...
// Try to change ownership of mut from shared to upgrade
ting::upgrade_lock<ting::upgrade_mutex> U(std::move(S), std::try_to_lock);
if (U.owns_lock())
   // ...

(which involves both upgrade_lock and shared_lock for the ownership conversion)

> 
> There is essentially no difference between a blocking lock and a
> try_lock_for(std::chrono::seconds(1000000000)), or repeated calls to
> try_lock in a loop. I think such operations should therefore be omitted
> in the cases that a blocking lock is not provided.

I agree 100% about there being no difference.  But I disagree that the lack of a blocking operation indicates there should be no try- or timed-operation in order to prevent abuse.  Even in the presence of a blocking operation, one can still create this kind of abuse and hang one's self just as quickly and subtly.  For example:

typedef ting::upgrade_mutex            mutex_type;
typedef ting::shared_lock<mutex_type>  SharedLock;
typedef ting::upgrade_lock<mutex_type> UpgradeLock;
typedef std::unique_lock<mutex_type>   ExclusiveLock;

void bad(mutex_type& mut1, mutex_type& mut2)
{
    UpgradeLock u1(mut1, std::defer_lock);
    SharedLock  s2(mut2, std::defer_lock);
    std::lock(u1, s2);
    // mut1 is upgrade locked and mut2 is share-locked

    ExclusiveLock e1(std::move(u1));
    // mut1 is exclusive locked and mut2 is share-locked
}

The above code looks reasonable.  However upon testing the author discovers that the conversion from u1 to e1 sometimes deadlocks.  And without understanding why (*Footnote), he changes the code to:

void bad(mutex_type& mut1, mutex_type& mut2)
{
    UpgradeLock u1(mut1, std::defer_lock);
    SharedLock  s2(mut2, std::defer_lock);
    std::lock(u1, s2);
    // mut1 is upgrade locked and mut2 is share-locked

    ExclusiveLock e1(std::move(u1), std::try_to_lock);
    while (!e1.owns_lock())
        e1 = ExclusiveLock(std::move(u1), std::try_to_lock);
    // mut1 is exclusive locked and mut2 is share-locked
}

This code is just as dead-locked.  The conversion from upgrade to exclusive has a blocking operation, and in the paragraph below you say that therefore this operation should have a timed (and presumably try) variant (and I agree).  But the presence   of the blocking operation hasn't prevented the abuse of the try-operation (or I could make it an abused timed-operation).

> On the other hand. the omission of the timed operations where the
> blocking operation is provided was merely that: an omission. Some of the
> operations are present in boost on either POSIX or Windows but not both
> --- they should probably all be provided on both platforms.

Thanks, I believe this means we're down to only two red arrows! :-)

*Footnote:  I'm speaking to the wider audience here, not to Anthony who I'm sure understands why bad() is bad.

bad() deadlocks when simultaneously called with bad(m1, m2) and bad(m2, m1).  The reason it deadlocks boils down to the violation of a very simple rule:

Once you're holding a lock, do not attempt to obtain a second lock when there is no ordering or hierarchy separating the second lock from the first.

The first lock obtained is the combination: (u1, s2).  The second lock obtained is the conversion: u1->e1.  The second lock blocks indefinitely for thread A when thread B is holding a shared lock on mut1 and is waiting for thread A to release its shared lock on mut2 so that it can upgrade mut2 from shared to exclusive.  Once this is understood, the correct rewrite is:

void ok(mutex_type& mut1, mutex_type& mut2)
{
    UpgradeLock u1(mut1, std::defer_lock);
    SharedLock  s2(mut2, std::defer_lock);
    std::lock(u1, s2);
    // mut1 is upgrade locked and mut2 is share-locked

    // Prepare to upgrade u1 by unlocking s2
    s2.unlock();
    ExclusiveLock e1(std::move(u1));
    // mut1 is exclusive locked and mut2 is unlocked
}

I.e. one has to unlock mut2 first.

If this is unacceptable then the routine must exclusive-lock both mut1 and mut2 at the beginning:  shared/upgrade locking is not appropriate for such an application.

If you are now terrified of converting locking modes, then just use shared_mutex and you'll be safe.  If you are now terrified of shared locking period, then just use mutex and you'll be safe.  And if you think this stuff is scary, have a look at std::memory_order in <atomic>.  Here's the rope, use it wisely. ;-)

Fortunately, properly designed low-level dangerous tools can be both useful and safe when encapsulated in higher-level tools.  This is a very low level library.  Just like it is a bad idea to have un-encapsulated memory allocations all over the place, memory allocation is still quite useful!  And I believe these mutexes are useful too.

-Howard