On Nov 28, 2010, at 6:38 PM, Jeffrey Lee Hellrung, Jr. wrote:

On 11/28/2010 12:52 PM, Howard Hinnant wrote:

...

Three years ago I wrote N2406 "Mutex, Lock, Condition Variable Rationale" (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2406.html) for the C++ committee in an attempt to explain the combined proposed std::mutex/std::unique_lock package and how it fit together with the tr2-targeted shared_mutex/shared_lock package. This paper also proposed an upgrade_mutex and upgrade_lock.

Since that time, the std-proposed stuff has been accepted with some name changes, and a reworking of the timed-locking interface. Additionally Anthony Williams has implemented much of the shared-locking functionality in boost (and done a very nice job with it).

That being said, I disagree with some fairly major design changes between N2406 and what is now in the boost library. Four of the major changes are: [...] There is a tutorial-style description of this library here:

http://home.roadrunner.com/~hinnant/mutexes/locking.html [...]

In the section "Upgrade Locking", where you list the member functions of ting::upgrade_mutex that are called in the (first) average function, I'm not sure the list is complete, and I want to make sure I understand what's going on.

I agree that mut_.lock() and a.mut_.lock_upgrade() are called upon construction of this_lock and share_that_lock, respectively.

I'd only expect mut_.unlock() and a.mut_.unlock_upgrade() to be called if an exception is thrown in the for-loop. Is that correct? If so, it might be helpful to make this more explicit; if not, please explain why.

I agree that mut_.unlock_and_lock_shared() and a.mut_.unlock_upgrade_and_lock() are called upon construction of share_this_lock and that_lock, respectively.

Finally, a.mut_.unlock() and mut_.unlock_shared() will be called, and in that order, upon destruction of that_lock and share_this_lock, respectively.

I believe you're missing a final unlock() function call.

The exposition could also be improved slightly if you indicate on *which* mutex (mut_ or a.mut_) the locking and unlocking member functions are invoked. But primarily, I just want to make sure I got this right ;)

I think you've got it right (nice job). I'm a little hesitant to get more detailed here. The intent was to do a bit of hand waving to motivate the reader into using the locks and not the mutex member functions. Diving deeper I think one could argue that nothing is ever going to throw in this function, though we could make another example that could throw to demonstrate the point. I haven't listed any function twice as this is meant to be a list of functions that are called, and not necessarily which function that is called in which order (which may vary depending on whether an exception is throw and where). I'm hoping to keep this section as short as possible and for the take-away message to be: Don't use mutex member functions!!! (unless you're doing something low-level like implementing a lock) :-) -Howard

On Nov 28, 2010, at 7:07 PM, Jeffrey Lee Hellrung, Jr. wrote:

Next topic:

I'm now confused with the implementation of try_lock_until...let's start with the first line:

std::unique_lock<L0> u0(l0, t)

So...L0 is itself a lock (specifically an ExclusiveLock, I would guess, although the second implementation of average is using a "Lock"...typo?),

Yes, type-o. Thanks for catching that! Each of those Lock's should be ExclusiveLock. My intent was to reuse A's typedefs from a few paragraphs above. I've updated: http://home.roadrunner.com/~hinnant/mutexes/locking.html#Upgrade

so I don't think this makes sense. Should be something like l0.try_lock_until(t) ???

Actually no. This is one of the things that makes generic locking algorithms so cool. L0 is what we now call Lockable (thanks to Anthony), or maybe more correctly TimedLockable. L0 could be a mutex, or could be a lock. This algorithm doesn't know or care. Either way it creates the lock: std::unique_lock<L0>. And the constructor called by: std::unique_lock<L0> u0(l0, t); will internally call l0.try_lock_until(t). Both std::unique_lock, and std::timed_mutex support this syntax, as do also ting::shared_lock, ting::shared_mutex, etc. The reason to wrap L0 up in std::unique_lock<L0> is exception safety. If l1.try_lock_until(t) either returns false or throws, then u0.~std::unique_lock<L0>() unlocks l0 on the way out. That way you get either all or none L's locked on normal or exceptional return of try_lock_until.

Also, there a few references to "diagrams to the right" throughout the text that aren't showing up in my firefox browser. Any suggestions?

Ouch! Do you see any pdf's with the title "Ownership Modes"? If your window width is simply wider or narrow than I'm estimating then these pdfs may be higher or lower in the text flow. However if there is something about firefox that won't display these pdfs at all then I need to do something else (maybe convert them to jpegs). -Howard

On Nov 28, 2010, at 9:27 PM, Jeffrey Lee Hellrung, Jr. wrote:

Please excuse the basic concurrent programming questions, I just want to make sure I understand the exposition correctly...

It looks like this implementation of try_lock_until could "fail" under contention, i.e., neither contending thread would perform the averaging computation. Suppose thread 1 calls a1.average(a2) and, simultaneously, thread 2 calls a2.average(a1). It could happen that thread 1 locks a1.mut_ in the first line of try_lock_until, and thread 2 similarly locks a2.mut_, and then each thread is waiting to acquire the other mutex. Now they both time out waiting for the other mutex before either is able to unlock their held mutex, so neither thread enters the average computation. Is this accurate?

Yes, I believe so.

If so, this seems undesirable, though it isn't nearly as bad as a deadlock scenario. Is it possible to guarantee this won't happen?

Yes, use std::lock instead (as done in the first version of average). std::lock will keep trying as long as it needs to to get both locks locked, and it will not deadlock. -Howard

On 11/28/2010 5:07 PM, Howard Hinnant wrote:

On Nov 28, 2010, at 7:07 PM, Jeffrey Lee Hellrung, Jr. wrote:

...

Also, there a few references to "diagrams to the right" throughout the text that aren't showing up in my firefox browser. Any suggestions?

Ok, I downloaded firefox and tested with it (as I should've done in the first place). Apparently the pdf images I was using didn't sit well with firefox. I've changed to jpgs and I can now view the diagrams with firefox. Thanks for reporting this. If anyone else has trouble viewing the diagrams please let me know.

-Howard

Great, thanks. I confirm that I can see the diagrams now. Now to get back to the text during the Sunday Night Football commercials... - Jeff

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

On Nov 29, 2010, at 1:16 PM, Anthony Williams wrote:

...

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

I've updated: http://home.roadrunner.com/~hinnant/mutexes/locking.html to color only the two disputed arrows red (the omissions are now purple). And I've updated the example code showing use of a disputed try-conversion from shared to exclusive locking. The newer example is I hope more motivating for the existence of the conversion. -Howard

On Nov 29, 2010, at 10:28 PM, Marsh Ray wrote:

The facility I used did not use have a different lock type for 'upgradable', all shared locks were upgradeable (of course we called them read and write locks).

An upgrade operation would always succeed if you were willing to wait long enough. The way the deadlock issue was handled was simple: it didn't guarantee that the upgrade would be performed atomically in every case. Sometimes a different thread would get his exclusive ownership in between your shared and exclusive locks. Of course, whether or not your upgrade happened atomically was indicated in the return value.

This allowed a common pattern:

shareable_mutex g_mut;

// Ensure color is made blue, if it isn't already. // get_color() and set_color() are nontrivial operations. void ensure_blue() { lock l(g_mut, shared, forever); if (get_color() != blue) { bool upgrade_was_atomic = l.upgrade_to_exclusive(forever); if (upgrade_was_atomic || get_color() != blue) set_color(blue); } }

So the code didn't need to call get_color() twice when the lock was upgraded atomically. That was the usual case. I'm sure there's similar code with your interface.

There were some things I liked about this pattern: * The code is simple. There's only one lock. The code doesn't have error conditions to test for, or exceptions being thrown, unless something else is broken. * There is one condition that must be checked, but even if you forgot to check it, it was probably just a missed optimization. You still had an exclusive lock at that point. * There was no such thing as a 'lock' object that wasn't actually locking a mutex.

Interestingly: * This avoids a context switch over the "upgrade fails, calling code loops and tries again" methods. The thread asks for an upgrade and he doesn't resume execution until he has an exclusive.

These days I probably wouldn't block forever on a single lock acquisition like that. I'm always waiting on at least two objects, one of them being a global event to signal application shutdown.

Thanks for sharing your experience. It helps to know that others have needed and successfully used ownership converting mutexes. For completeness for everyone I've translated your example to ting::syntax: ting::upgrade_mutex g_mut; // Ensure color is made blue, if it isn't already. // get_color() and set_color() are nontrivial operations. void ensure_blue() { ting::shared_lock<ting::upgrade_mutex> l(g_mut); if (get_color() != blue) { std::unique_mutex<ting::upgrade_mutex> lk(std::move(l), std::try_to_lock); if (lk.owns_lock()) set_color(blue); // upgrade is atomic else { l.unlock(); lk.lock(); // upgrade is not atomic if (get_color() != blue) set_color(blue); } } } I believe it would be easy to build a user-defined lock type which took a ting::upgrade_mutex which had exactly the syntax and semantics of your lock. One would essentially put the logic I have in the outer if() statement inside the conversion function: class lock { ting::upgrade_mutex g_mut; ... }; bool lock::upgrade_to_exclusive() { if (g_mut.try_unlock_shared_and_lock()) return true; g_mut.unlock_shared(); g_mut.lock(); return false; } If you wanted a timed version you could: template <class Rep, class Period> bool lock::upgrade_to_exclusive(std::chrono::duration<Rep, Period> t) { if (g_mut.try_unlock_shared_and_lock_for(t)) return true; g_mut.unlock_shared(); g_mut.lock(); return false; } You could not write any of the above 3 functions with boost::shared_mutex. -Howard