Re: [boost] [thread] On shared_mutex

Subject: Re: [boost] [thread] On shared_mutex
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2010-11-29 13:16:36

Howard Hinnant <howard.hinnant_at_[hidden]> writes:

> 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:
>
> 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 see. It's a minor but potentially important difference.

>>> 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
>> 
>> 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.

[snip my description of why shared_mutex is a bad choice]
 
>> 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...

People want things that aren't good for them, and will use them if they
are provided under the assumption that such usage has been "blessed" in
some way.

I feel that "encouraging" people to use shared_mutex is a bad idea, but
agree that people seem to want it. I was one of those people once! That
doesn't mean we should provide them.

I'm not going to take shared_mutex out of boost, if only for backwards
compatibility sake, but I don't think we want it in TR2.

>> 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.

I understand. Still not convinced though ;-)

>> 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).

My point is this: allowing shared_lock -> unique_lock conversions is
deadlock prone, because there may be a large number of shared_locks in
existence, and all could attempt to do a shared_lock -> unique_lock
conversion, whereupon none will succeed. 

This is why we have upgrade_lock --- there can be only one of those, so
upgrading is not deadlock prone in the same way (though your example
shows it can still deadlock, as can any mutex lock).

Since we seem agreed that there is no conceptual difference between a
blocking upgrade and a try_upgrade in a loop, allowing a try_upgrade
from shared_lock to unique_lock has the same problems as a block upgrade.

e.g.

void f(upgrade_mutex& m)
{
   shared_lock<upgrade_mutex> sl(m);
   unique_lock<upgrade_mutex> ul(std::move(sl), std::try_to_lock);
   while (!ul.owns_lock())
       ul = unique_lock<upgrade_mutex>(std::move(sl), std::try_to_lock);
}

Now call f() from multiple threads....

Allowing ownership transfers from shared_lock to upgrade_lock suffers
from exactly the same problem --- we don't even have to actually upgrade
the lock, since we can only have one upgrade_lock per upgrade_mutex.

Though I've described this problem in terms of
shared_lock/upgrade_lock/unique_lock, the basic issue is with regard to
the ownership modes of the mutex --- you should not allow any
transitions from shared ownership to a higher level; this is the reserve
of upgrade ownership.

> But I disagree that the lack of a blocking operation indicates there
> should be no try- or timed-operation in order to prevent abuse.  

Given the equivalence of try-operations to blocking operations, if we
decide the blocking operation is unsafe we shouldn't provide the
try-operation either.

> 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.  

Oh yes. Totally agreed there.

[snip example]

> 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).

This isn't an argument against a blocking upgrade; it's just an argument
against unordered lock acquisition, as you describe in your footnote.

>> 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! :-)

And those are the two arrows I think we should not allow (S->U and
S->E).

Anthony
-- 
Author of C++ Concurrency in Action     http://www.stdthread.co.uk/book/
just::thread C++0x thread library             http://www.stdthread.co.uk
Just Software Solutions Ltd       http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976