Doug Gregor wrote:

On Tuesday 29 June 2004 8:00 am, Christopher Currie wrote:

...

...

The basic usages (covering about 80%) are:

scoped_lock l(m); // Block until it locks. scoped_try_lock l(m); // Try (!) to lock. I'll check the result.

I disagree here, as well. Say I want to program generically...

template <typename Mutex, typename Lock> class worker_class { Mutex m_;

public: do_work() { Lock l(m_); // Does this call block? // am I guarenteed to be locked here? } }

Yes, it's a contrived case,

I don't believe it is a contrived case. Certainly once we have read/write mutexes we're going to want to tell generic components which kind of lock they need to use.

I was going to ask if locks were likely to be used generically in this way; obviously they will, in your opinion. I appreciate your bringing up read/write locks; I was planning to bring them into the discussion as well.

...

but the point is that all locks should have the same behavior in the 1-argument constructor case, and that is to block until this lock is obtained. The is the only way the user can use the lock in a generic way.

Absolutely. This is *extremely* important to keep in mind when discussing any kind of concept taxonomy.

I would consider this more an argument for eliminating 1-argument constructors entirely (except for scoped_lock, where its meaning is completely unambiguous): there doesn't seem to be a way to define them that is both consistent within the lock class and consistent across lock classes (e.g. I agree with Vladimir that for consistency within the try_lock class, it should be non-blocking; but as Christopher pointed out, for consistency across lock classes, it should be blocking). And, if you consider the larger case, which also includes read/write locks, single-argument constructors are even harder to define (do the read-lock or write-lock?; do they block or not?).

Refinements of a concept can only add restrictions, they cannot remove them.

True. But it's not hard to define the concepts in such a way that the lock classes can have different constructors: Lock concept defines all lock operations except constructors. TryLock concept refines Lock by adding try_* methods. TimedLock concept refines TryLock by adding timed_* methods. ScopedLock refines Lock by adding appropriate constructors. ScopedTryLock refines TryLock by adding appropriate constructors. ScopedTimedLock refines TimedLock by adding appropriate constructors. Mike

Doug Gregor <dgregor@cs.indiana.edu> writes:

Right, so what we have (I think) are reasonably well-designed classes with incorrectly specified concepts. scoped_lock should really lock; try_lock should just try to lock.

I don't understand; are you addressing the concept problem above? scoped_lock refers to a class, right? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Doug Gregor wrote:

On Tuesday 29 June 2004 9:15 am, Michael Glassford wrote:

...

Doug Gregor wrote:

...

...

but the point is that all locks should have the same behavior in the 1-argument constructor case, and that is to block until this lock is obtained. The is the only way the user can use the lock in a generic way.

Absolutely. This is *extremely* important to keep in mind when discussing any kind of concept taxonomy.

I would consider this more an argument for eliminating 1-argument constructors entirely (except for scoped_lock, where its meaning is completely unambiguous): there doesn't seem to be a way to define them that is both consistent within the lock class and consistent across lock classes (e.g. I agree with Vladimir that for consistency within the try_lock class, it should be non-blocking; but as Christopher pointed out, for consistency across lock classes, it should be blocking).

Right, so what we have (I think) are reasonably well-designed classes with incorrectly specified concepts. scoped_lock should really lock; try_lock should just try to lock.

I'm not sure exactly what you're suggesting here. Are you talking about only the constructors, or would you completely eliminate all blocking functionality (e.g. the lock() method) from try_lock? And all non-timed functionality (e.g. the lock() and try_lock() methods) from timed_lock?

...

And, if you consider the larger case, which also includes read/write locks, single-argument constructors are even harder to define (do the read-lock or write-lock?; do they block or not?).

I'd expect scoped_*_read_lock and scoped_*_write_lock classes to be separate classes that model whatever locking concepts we come up with. Actually, the design of the read/write lock on the branch really surprised me, because it used the read_write_lock_state enum instead of distinct types.

There's a lot to be said for separate read-lock and write-lock types, and I was hoping to address that at some point; however, it would make lock promotion/demotion more difficult (unless maybe the read_lock class had a promote() method that returned a write_lock class or something like that, but that has some problems, too).

...

...

Refinements of a concept can only add restrictions, they cannot remove them.

True. But it's not hard to define the concepts in such a way that the lock classes can have different constructors:

Lock concept defines all lock operations except constructors. TryLock concept refines Lock by adding try_* methods. TimedLock concept refines TryLock by adding timed_* methods.

ScopedLock refines Lock by adding appropriate constructors. ScopedTryLock refines TryLock by adding appropriate constructors. ScopedTimedLock refines TimedLock by adding appropriate constructors.

Looks perfectly reasonable to me.

Doug

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Doug Gregor wrote:

On Tuesday 29 June 2004 10:55 am, Michael Glassford wrote:

...

Doug Gregor wrote:

[snip]

...

...

...

And, if you consider the larger case, which also includes read/write locks, single-argument constructors are even harder to define (do the read-lock or write-lock?; do they block or not?).

I'd expect scoped_*_read_lock and scoped_*_write_lock classes to be separate classes that model whatever locking concepts we come up with. Actually, the design of the read/write lock on the branch really surprised me, because it used the read_write_lock_state enum instead of distinct types.

There's a lot to be said for separate read-lock and write-lock types, and I was hoping to address that at some point; however, it would make lock promotion/demotion more difficult (unless maybe the read_lock class had a promote() method that returned a write_lock class or something like that, but that has some problems, too).

Could write_lock have a constructor/method that takes in the read lock to be promoted? I'm a little fuzzy on the implementation issues here.

I suppose it could, but if you needed to promote and demote a lock a couple of times it could get messy; and if you needed to promote conditionally, it could also get messy. Also, you could end up with some interesting situations like this: void f(read_write_mutex m) { read_write_mutex::read_lock r(m); if (...) { read_write_mutex::write_lock w(r); //lock promotion //... } //Point A } The most obvious implementation of promotion would be for the write lock to unlock the read lock if promotion succeeded, but leave it locked if promotion failed. But in the above code, this would mean that if promotion succeeds, neither lock will be locked at "Point A"; however if promotion fails, r will still be read-locked at point A. Another possibility is to define separate read_lock, write_lock, and read_write_lock classes, and only the last would allow promotion & demotion. The disadvantage of this is a proliferation of lock classes, but it may be the best option, all things considered. Mike

Peter Dimov wrote:

Michael Glassford wrote:

...

Also, you could end up with some interesting situations like this:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); if (...) { read_write_mutex::write_lock w(r); //lock promotion //... } //Point A }

The most obvious implementation of promotion would be for the write lock to unlock the read lock if promotion succeeded, but leave it locked if promotion failed. But in the above code, this would mean that if promotion succeeds, neither lock will be locked at "Point A"; however if promotion fails, r will still be read-locked at point A.

Not necessarily, ~write_lock can (should) demote the lock back to read (or whatever the initial condition of r was).

True. But then, in the reverse case: void f(read_write_mutex m) { read_write_mutex::write_lock w(m); if (...) { read_write_mutex::read_lock r(w); //lock demotion //... } //Point A } It may not be possible for r's destructor to re-obtain the write lock, which means that, at point A: 1) If the write lock can be re-obtained, w is write-locked. 2) Otherwise, w is either unlocked or read-locked. The idea of a write-lock being read-locked is pretty strange, but having it unlocked doesn't seem a good choice, either. I realize that a combined read-write lock has the same problem of possibly being unable to re-obtain the write-lock, but in that case it is at least more obvious that the lock state changed and what it changed to: void f(read_write_mutex m) { read_write_mutex::read_write_lock l(m, write_locked); if (...) { l.demote(); //lock demotion //... } //Point A: l is read-locked } Or: void f(read_write_mutex m) { read_write_mutex::read_write_lock l(m, write_locked); if (...) { l.demote(); //lock demotion //... l.try_promote(); //optional } //Point A: l is write-locked if try_promote() succeeded, //read-locked if it failed; never unlocked. } Finally, to take two more realistic use cases: void f(read_write_mutex m) { read_write_mutex::write_lock w(m); //... read_write_mutex::read_lock r(w); //lock promotion //... } And: void f(read_write_mutex m) { read_write_mutex::write_lock r(m); //... read_write_mutex::read_lock w(r); //lock demotion //... } The second lock does unnecessary work in demoting/promoting the lock for the first lock, which then immediately unlocks it. Don't get me wrong: I actually like the idea of separate read and write locks, but there seem to be some tricky problems to address to make them work with lock promotion/demotion. Mike

Anthony Williams wrote:

Michael Glassford <glassfordm@hotmail.com> writes:

...

Peter Dimov wrote:

...

Michael Glassford wrote:

...

Also, you could end up with some interesting situations like this:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); if (...) { read_write_mutex::write_lock w(r); //lock promotion //... } //Point A }

The most obvious implementation of promotion would be for the write lock to unlock the read lock if promotion succeeded, but leave it locked if promotion failed. But in the above code, this would mean that if promotion succeeds, neither lock will be locked at "Point A"; however if promotion fails, r will still be read-locked at point A.

Not necessarily, ~write_lock can (should) demote the lock back to read (or whatever the initial condition of r was).

True. But then, in the reverse case:

void f(read_write_mutex m) { read_write_mutex::write_lock w(m); if (...) { read_write_mutex::read_lock r(w); //lock demotion //... } //Point A }

It may not be possible for r's destructor to re-obtain the write lock

I don't think this usage should be allowed.

How would it be prevented?

Once you have a write lock (the "higher class" of lock), then you keep your write lock until you release it. If you want a read lock for the whole time, but only a write lock for a portion of that time, then you write code like the first example. Your "reverse case" actually fulfils that requirement, since there is a portion of the code that only needs a read lock. Therefore it should look like:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); // we need at least a read lock // for everything { read_write_mutex::write_lock w(r); // do stuff that needs the write lock here } if (...) { // we only need the read lock here //... } { read_write_mutex::write_lock w(r); // do more stuff that needs the write lock here } }

Again, this might be a better way to write it, but how do you prevent someone from writing it the first way? I think one of the most common use cases for lock demotion would be: obtain a write lock and make modifications to a resource; demote to a read lock to release other readers and use the resource, making sure that it is still in the state it was when we had the write lock (i.e., that no other thread obtained a write lock and changed it between the time we released our write lock and the time we obtained our read lock). With a read/write lock, this is expressed in a straightforward way: void f(read_write_mutex m) { read_write_mutex::write_lock l(m); //Modify the resource l.demote(); //Release other readers //Use the resource } With the separate read-lock and write-lock, how do you express this in a way that is straightforward, doesn't do unnecessary work when the locks are released, etc.? Mike

Anthony Williams wrote:

Michael Glassford <glassfordm@hotmail.com> writes:

...

Anthony Williams wrote:

...

Michael Glassford <glassfordm@hotmail.com> writes:

...

True. But then, in the reverse case:

void f(read_write_mutex m) { read_write_mutex::write_lock w(m); if (...) { read_write_mutex::read_lock r(w); //lock demotion //... } //Point A }

It may not be possible for r's destructor to re-obtain the write lock

I don't think this usage should be allowed.

How would it be prevented?

Don't allow a read_lock to be constructed from a write_lock.

Thinking about it some more after replying, I thought that's what you might mean; however, see my comment on your example below.

...

...

Once you have a write lock (the "higher class" of lock), then you keep your write lock until you release it. If you want a read lock for the whole time, but only a write lock for a portion of that time, then you write code like the first example. Your "reverse case" actually fulfils that requirement, since there is a portion of the code that only needs a read lock. Therefore it should look like:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); // we need at least a read lock // for everything { read_write_mutex::write_lock w(r); // do stuff that needs the write lock here } if (...) { // we only need the read lock here //... } { read_write_mutex::write_lock w(r); // do more stuff that needs the write lock here } }

Again, this might be a better way to write it, but how do you prevent someone from writing it the first way?

See above.

The above code has a problem, however. This: void f(read_write_mutex m) { read_write_mutex::read_lock w(m); //Block until we get read-lock //do stuff read_write_mutex::write_lock(r); //Convert to write-lock; may fail; then what? //do more stuff } Is not the same as this: void f(read_write_mutex m) { read_write_mutex::read_write_lock l(m, write_locked); //Block until we get write-lock //do stuff l.demote(); //Convert to read-lock; never fails //do more stuff } The reason is that the first example always succeeds in getting the write lock eventually, and lock demotion always succeeds as well, so we always get the lock we want. In the second example, we can always get the read-lock, but the lock promotion may fail, so we may never get the write lock. The reason lock promotion may fail is that if two threads holding read locks are both waiting for promotion to write-locks, neither will ever get the write lock (which can't be obtained until all other read-locks have been released) and they will deadlock. So, unless you know of a better solution, at most one thread must ever be allowed to wait for lock promotion and any other promotion attempts must fail.

...

I think one of the most common use cases for lock demotion would be: obtain a write lock and make modifications to a resource; demote to a read lock to release other readers and use the resource, making sure that it is still in the state it was when we had the write lock (i.e., that no other thread obtained a write lock and changed it between the time we released our write lock and the time we obtained our read lock).

With a read/write lock, this is expressed in a straightforward way:

void f(read_write_mutex m) { read_write_mutex::write_lock l(m);

//Modify the resource

l.demote(); //Release other readers

//Use the resource }

With the separate read-lock and write-lock, how do you express this in a way that is straightforward, doesn't do unnecessary work when the locks are released, etc.?

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); { read_write_mutex::write_lock l(r);

//Modify the resource } // release other readers

//Use the resource }

This has the same problem I mention above. Unless I'm missing something, it also performs unnecessary work (a promotion followed by a demotion, as opposed to only a demotion in my example). Mike

Anthony Williams wrote:

Michael Glassford <glassfordm@hotmail.com> writes:

...

Anthony Williams wrote:

...

...

Michael Glassford <glassfordm@hotmail.com> writes:

...

...

...

Anthony Williams wrote:

...

...

...

...

Once you have a write lock (the "higher class" of lock), then you keep your write lock until you release it. If you want a read lock for the whole time, but only a write lock for a portion of that time, then you write code like the first example. Your "reverse case" actually fulfils that requirement, since there is a portion of the code that only needs a read lock. Therefore it should look like:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); // we need at least a read lock // for everything { read_write_mutex::write_lock w(r); // do stuff that needs the write lock here } if (...) { // we only need the read lock here //... } { read_write_mutex::write_lock w(r); // do more stuff that needs the write lock here } }

Again, this might be a better way to write it, but how do you prevent someone from writing it the first way?

See above.

The above code has a problem, however. This:

void f(read_write_mutex m) { read_write_mutex::read_lock w(m); //Block until we get read-lock

//do stuff

read_write_mutex::write_lock(r); //Convert to write-lock; may fail; then what?

Don't allow it to fail --- block.

That's a bad idea because of deadlock issues, as I (and you) mention below. And in any case, the two pieces of code are still not the same. The first will often block or deadlock at the promotion, the second will never block at the demotion.

...

//do more stuff }

Is not the same as this:

void f(read_write_mutex m) { read_write_mutex::read_write_lock l(m, write_locked); //Block until we get write-lock

//do stuff

l.demote(); //Convert to read-lock; never fails

//do more stuff }

The reason is that the first example always succeeds in getting the write lock eventually, and lock demotion always succeeds as well, so we always get the lock we want. In the second example, we can always get the read-lock, but the lock promotion may fail, so we may never get the write lock.

Not an issue if promotion is blocking.

...

The reason lock promotion may fail is that if two threads holding read locks are both waiting for promotion to write-locks, neither will ever get the write lock (which can't be obtained until all other read-locks have been released) and they will deadlock. So, unless you know of a better solution, at most one thread must ever be allowed to wait for lock promotion and any other promotion attempts must fail.

In which case, don't do it like that.I see this as the fundamental problem of promotion

I agree. Which is why I recommended getting the write lock first and later demoting it, as opposed to the solution you originally suggested which requires getting the read-lock first and then promoting it.

if the idea of promotion is to ensure that no one has modified the data since you read it, then if two threads have read locks and try and promote them to write locks, either you deadlock or one will fail. If it fails, what do you do? You have to release your read lock to let the other thread do the write, and then try again.

There are times when even this could be useful for efficiency, I suppose--you try to promote first, then if it fails you release the read-lock, get a write-lock, redo (as little as possible of) the work you did when you had the read-lock, then do the writing. However... In my mind demotion is more important: you make modifications, then demote to a read-lock to allow other readers access to the resource while you continue to read from it yourself, with the guarantee that the changes you just made have not been modified by another thread before you use them.

This makes me think that such a feature is not particularly useful in the general case. Maybe a try_write_lock variant is in order?

Are you referring to one that implements something like try_promote()? If so, I agree to the point that I have so far provided only try_promote() and timed_promote() functions in Boost.Threads, but no promote() function at all due to the problems we both raised above.

I might code it so that the write_lock does the release/reacquire itself, but this is a difficult issue.

I have an experimental set_lock member in the read/write locks that does this (release/reacquire): it changes from one lock state to another, using the best option possible. For example, when changing from a read-lock to a write-lock, it first uses try_promote() (if available); if that fails, it unlocks then write-locks. I thought it also returned a value that indicated whether it had to release the lock first, but see that it doesn't; maybe I need to change that.

Allowing deadlocks is not a good thing, but I really don't like the idea of the try_xxx locks because it raises the issue of "have I got the lock or not?". I'm also not a fan of control by member functions --- this is a resource, so we should use RAII.

It is using RAII, at least as much as is commonly done. It's pretty common to acquire the resource in the constructor, change its state with a member function, and release it (if applicable) in the destructor. The lock() and unlock() methods of the Boost.Threads lock classes are another example of the same thing, as are smart pointer assignment operators, etc. It would be pretty limiting to remove all these.

...

...

...

I think one of the most common use cases for lock demotion would be: obtain a write lock and make modifications to a resource; demote to a read lock to release other readers and use the resource, making sure that it is still in the state it was when we had the write lock (i.e., that no other thread obtained a write lock and changed it between the time we released our write lock and the time we obtained our read lock).

With a read/write lock, this is expressed in a straightforward way:

void f(read_write_mutex m) { read_write_mutex::write_lock l(m);

//Modify the resource

l.demote(); //Release other readers

//Use the resource }

With the separate read-lock and write-lock, how do you express this in a way that is straightforward, doesn't do unnecessary work when the locks are released, etc.?

void f(read_write_mutex m) { read_write_mutex::read_lock r(m); { read_write_mutex::write_lock l(r); //Modify the resource } // release other readers //Use the resource }

This has the same problem I mention above. Unless I'm missing something, it also performs unnecessary work (a promotion followed by a demotion, as opposed to only a demotion in my example).

I agree there is the possibility for unnecessary work, but in my view it clearly marks the region where writing is done. With a read-write lock, I can write:

void g(read_write_mutex::read_write_lock& l);

void f(read_write_mutex& m) { read_write_mutex::read_write_lock l(m,write_locked); g(l); // Are we still locked for writing, or just reading? }

void f2(read_write_mutex& m) { read_write_mutex::read_write_lock l(m,read_locked); g(l); // Are we still locked for just reading, or for writing as well?

True. The same is true of the unlock(() and lock() members of lock classes, the assignment operator of smart pointers, and, in general, of any function that can modify its arguments. What if you write: void g(const read_write_mutex::read_write_lock& l); instead?

}

Whereas with separate locks it's clear what's happening when I write:

void g(read_write_mutex::read_lock& l); void g(read_write_mutex::write_lock& l);

void f(read_write_mutex& m) { read_write_mutex::read_lock l(m); g(l); // We're still locked for just reading, whether or not g did writing }

void f2(read_write_mutex& m) { read_write_mutex::write_lock l(m); g(l); // We're still locked for writing }

I agree completely that separate locks are a good idea in most cases, but don't think that they work very well with lock promotion or demotion. What I'm most inclined to do at the moment is to have separate read_lock and write_lock classes that don't support promotion or demotion, and a combined read_write_lock class that supports both for those cases where promotion and demotion are required. Mike

Peter Dimov wrote:

Michael Glassford wrote:

...

Finally, to take two more realistic use cases:

void f(read_write_mutex m) { read_write_mutex::write_lock w(m);

//...

read_write_mutex::read_lock r(w); //lock promotion

//... }

And:

void f(read_write_mutex m) { read_write_mutex::write_lock r(m);

//...

read_write_mutex::read_lock w(r); //lock demotion

//... }

The second lock does unnecessary work in demoting/promoting the lock for the first lock, which then immediately unlocks it.

This is a very good point, since in the second example the unnecessary promotion would block.

One thing that I haven't made clear is that (so far at least) the Boost.Threads read/write mutex doesn't support infinitely-blocking promotion, which has problems (e.g. if two threads with read locks block waiting to be promoted to write locks, they deadlock); it only supports try_promote() and timed_promote(). So there shouldn't be a problem with blocking, at least, in the second example.

This seems to suggest that read_write_lock is necessary in such a scenario.

Looks like I really messed up my examples; I'm glad you could see my point in spite of that. Of course, what I meant was this: void f(read_write_mutex m) { read_write_mutex::read_lock r(m); //... read_write_mutex::write_lock w(r); //lock promotion //... } And: void f(read_write_mutex m) { read_write_mutex::write_lock w(m); //... read_write_mutex::read_lock r(w); //lock demotion //... } Mike

Howard Hinnant wrote:

On Jun 29, 2004, at 12:30 PM, Michael Glassford wrote:

...

Also, you could end up with some interesting situations like this:

[...] Let's assume that the guarded entity is int x;

...

void f(read_write_mutex m) { read_write_mutex::read_lock r(m);

int y = x;

...

if (...) { read_write_mutex::write_lock w(r); //lock promotion

assert( x == y); // always holds, we had a read+ lock all the time

...

//... } //Point A }

How 'bout:

void f(read_write_mutex& m) { read_write_mutex::read_lock r(m);

int y = x;

if (...) { r.unlock();

Thread switch, write lock, write to x happens here.

read_write_mutex::write_lock w(m); //... m is write locked

assert( x == y); // may fail

w.transfer_to_read_lock(r); } //Point A ... m is read locked }

Howard Hinnant wrote:

I'm not following that x==y always holds. If two threads concurrently hold a read lock, and concurrently try to obtain a write lock, only one thread will get the write lock, the other will block. Assuming the one thread that got the write lock changes x, then the thread that blocked will fire its assert when it finally unblocks and gets the write lock.

What am I missing?

As I understand it, if two threads hold a read lock, no thread can obtain a write lock. Write lock == exclusive access. This corresponds to the POSIX memory model where write accesses must be exclusive, but read accesses can be shared with other read accesses. But I may be wrong. ;-)

Howard Hinnant <hinnant <at> twcny.rr.com> writes:

My take, depending upon how the w(r) constructor is implemented, is either:

1. deadlock. 2. one thread blocks and one thread gets the lock.

Imho choice 1 is a buggy implementation of the w(r) constructor.

Yes, there's no point creating a library facility that assists you in writing code that deadlocks.

And choice 2 results in the assert(x==y) possibly firing.

I think that in the second case, an exception should be thrown. Typically, if you fail to promote a rw lock from read to write, then you will have to repeat the part of the code that was read-protected after the other thread's write lock has been released: bool try_sale(rw_mutex& m) { read_lock rl(m); long balance = get_balance(); long cost = get_total_cost(); if (balance > cost) { write_lock wl(rl); set_balance(balance - cost); // ... return true; } return false } bool do_sale(rw_mutex& m) { bool succeeded = false; while (true) { try { return try_sale(m); catch (rw_promotion_error&) { // Try the whole thing again } } }

I believe choice 2 is the only reasonable path. And I also believe that the syntax above might lull a code reader into believing that assert(x==y) should always be true. And therefore I think the following (more explicit) syntax is superior:

void f(read_write_mutex m) { read_write_mutex::read_lock r(m);

int y = x;

if (...) { r.unlock(); read_write_mutex::write_lock w(m);

This is essentially how the w(r) ctor must be implemented, if it is to be implemented at all. One could try a try_lock on w if the read count is 1, and then fall back on the above if that doesn't work, but I'm unsure if that really provides a benefit.

But this doesn't achieve anything - if you release the read lock, then you don't know that what held true while it was read-locked is still true once you have acquired a write lock. If you choose to have lock promotion (having only lock demotion is a viable choice, except that there will be certain usage patterns that are more efficient with a fail-able promotion), then it must at least preserve known state across promotion. Matt.

Michael Glassford <glassfordm <at> hotmail.com> writes:

I agree. That's why I've so far only provided the Boost.Threads read/write lock try_promote() and timed_promote() methods (though you can, of course, get the latter to deadlock by using infinite times), and no promote() method. You could make a promote() method that throws if it can't promote, as you suggest below, but I don't like the idea much.

Why don't you like the exception? I'll admit immediately to not having given this much thought, but the exception seems appropriate to a coding pattern based on RAII, since it gives simple control flow back to a user-chosen failure handling point, freeing any previously taken locks. ALso, boost.thread already defines the lock_error exception for lock failure. Matt

Michael Glassford wrote:

To me, it just feels like the wrong way to be notified that a lock promotion failed so you have to do something else--a try_promote() seems much better for this. However, if people really wanted a throwing promote(), I'd add it.

The point is that the scoped_write_lock wr( rd ); syntax, if supported, should never "succeed" without giving you a write lock. scoped_try_write_lock wr( rd ); can do that, but not scoped_write_lock. That said, can you show an example that demonstrates how a 'try_promote' can be used? I'm curious.

Michael Glassford <glassfordm <at> hotmail.com> writes:

Translating this to the constructor model of promotion would have to look something like this, I guess:

void f(read_write_mutex& m) { read_write_mutex::try_read_lock r(m);

//do "read stuff"

read_write_mutex::try_write_lock w(r, /*maybe a parameter here to use try_promote() instead of promote()*/);

if (!w.locked()) { r.unlock(); w.lock(); //redo some of "read stuff" }

//do write stuff }

You could encapsulate some of that in the constructor of the write lock: void f(read_write_mutex& m) { read_write_mutex::read_lock r(m); do_read_stuff(); read_write_mutex::write_lock w(r); // Upgrade, releasing and re-acquiring // if necessary if (!w.atomically_promoted()) { do_read_stuff(); } do_write_stuff(); } It certainly looks error-prone, by requiring a test and the repetition of the earlier code. Makes you wonder if it should have a function to execute on non-atomic upgrade: { read_write_mutex::read_lock r(m); do_read_stuff(); read_write_mutex::write_lock w(r, bind(this, &class::do_read_stuff)); do_write_stuff(); } You could reduce further, but I'm sure it will collapse under the weight of real code :) Matt

On Jul 7, 2004, at 9:26 AM, Michael Glassford wrote:

However, I don't see any way to avoid re-trying after the write-lock is obtained when promotion fails, and I don't see a way to prevent promotion from failing except for the suggested latent-read-lock / upgradeable-read-lock. I agree that such a lock is a good idea, but it does have the drawback of serializing all upgradeable read locks, which could be quite undesirable in some circumstances.

I've been giving the fail-able read promotion more thought... The purpose of using read/write locks is presumably to allow concurrent reads. In such a design, concurrent reads are probably expected as the norm, else the cheaper and simpler scoped_lock is likely to be more appropriate. Given that concurrent reads are likely to be a normal occurrence, it follows that a failed read_lock promotion would also be a normal occurrence. In the event of a failed read_lock promotion, the typical strategy is to accept that you have to block for write access, and to reread (or recompute) whatever you obtained under the read lock. Given that the expected norm is fail-block-reread, is there any advantage to this approach? That is, in a design where you expect multiple concurrent read promotions, they have to be serialized no matter what. In a design where you expect multiple concurrent read promotions to be rare the upgradable_read_lock, or even the far simpler scoped_lock (in the case concurrent reads are rare) should not incur a performance hit. The big motivation that I see for the upgradable_read_lock is the scenario linked to by Alexander yesterday: On Jul 6, 2004, at 5:02 AM, Alexander Terekhov wrote:

Read this thread:

http://groups.google.com/groups?threadm=ijnd7a.3pb.ln%40tux.localdomain (Subject: upgradeable lock)

If you have multiple long read/compute then write threads, there is no other logic that solves the problem other than serialization, no matter how it is coded. The paragraph that David Butenhof wrote in response to the fail-able read promotion design (which Alexander also quoted here) summed up (and cemented) my thoughts as well. -Howard

Howard Hinnant wrote:

On Jul 7, 2004, at 9:26 AM, Michael Glassford wrote:

...

However, I don't see any way to avoid re-trying after the write-lock is obtained when promotion fails, and I don't see a way to prevent promotion from failing except for the suggested latent-read-lock / upgradeable-read-lock. I agree that such a lock is a good idea, but it does have the drawback of serializing all upgradeable read locks, which could be quite undesirable in some circumstances.

I've been giving the fail-able read promotion more thought...

The purpose of using read/write locks is presumably to allow concurrent reads. In such a design, concurrent reads are probably expected as the norm, else the cheaper and simpler scoped_lock is likely to be more appropriate. Given that concurrent reads are likely to be a normal occurrence, it follows that a failed read_lock promotion would also be a normal occurrence.

It would be a normal occurrence, but not necessarily because of concurrent reads. It would be easy for promotion from read-lock to write-lock to a) prevent any new read or write locks, b) wait until all current read-locks are released, and then c) obtain the write lock. The only time a promotion request needs to fail is when multiple threads request promotion simultaneously; all but one must fail and relinquish its read lock to prevent deadlock. Other than that, I agree with everything you've said. (Actually, re-reading what you've said below, I think maybe that's actually what you meant anyway).

In the event of a failed read_lock promotion, the typical strategy is to accept that you have to block for write access, and to reread (or recompute) whatever you obtained under the read lock.

Given that the expected norm is fail-block-reread, is there any advantage to this approach? That is, in a design where you expect multiple concurrent read promotions, they have to be serialized no matter what.

True. The only advantage I can see is in cases where you have many readers that have to read in order to see if they need write access, and only few of them ever actually need it. The many checks can happen simultaneously, and the time saved by the concurrency outweighs the cost of the few re-reads. Having said that, I'm not at all tied to that type of scheme. I've thought all along that lock demotion is more important than lock promotion (at least for my typical uses of a read/write lock).

In a design where you expect multiple concurrent read promotions to be rare the upgradable_read_lock, or even the far simpler scoped_lock (in the case concurrent reads are rare) should not incur a performance hit.

The big motivation that I see for the upgradable_read_lock is the scenario linked to by Alexander yesterday:

On Jul 6, 2004, at 5:02 AM, Alexander Terekhov wrote:

...

Read this thread:

http://groups.google.com/groups?threadm=ijnd7a.3pb.ln%40tux.localdomain (Subject: upgradeable lock)

If you have multiple long read/compute then write threads, there is no other logic that solves the problem other than serialization, no matter how it is coded.

The paragraph that David Butenhof wrote in response to the fail-able read promotion design (which Alexander also quoted here) summed up (and cemented) my thoughts as well.

All this makes sense to me. Again, I like the upgradeable lock agree that the that it's cleaner and easier to use. Mike

What about a latent_write_lock? It's semantics would be to block on contruction until it only shares the mutex with read_locks. A write_lock could be contructed from a latent_write_lock and this would always work, because another latent_write_lock would still be blocked in it's constructor. This kind of lock would be useful for situations in which you have to read a structure to know if you have to write on it. Bruno Martinez

On Tue, 6 Jul 2004 03:29:15 +0000 (UTC), Matthew Vogt <mvogt@juptech.com> wrote:

Bruno Martínez Aguerre <br1 <at> internet.com.uy> writes:

...

What about a latent_write_lock?

It's semantics would be to block on construction until it only shares the mutex with read_locks. A write_lock could be constructed from a latent_write_lock and this would always work, because another latent_write_lock would still be blocked in it's constructor. This kind of lock would be useful for situations in which you have to read a structure to know if you have to write on it.

Interesting, this divides read locks into promotable and non-promotable variants?

Yes.

If you have a design where a lot of threads take concurrent read locks, and the case of promotion is rare, then having them all use latent_write_locks will unnecessarily serialise them. Allowing promotion failure instead would only affect rare cases of promotion contention.

That's true. If promotion is uncommon, the best solution would be to unlock the read_lock and construct a normal write_lock. It's a rare situation, and the code is simpler this way than dealing with exceptions/retries.

If you have a case where promotion is common, then you probably won't gain much over simply using write locks, will you?

If promotion is common and the reading part is long, a latent_write_lock would be better than a write_lock because it wouldn't block normal readers until necesary. Trying to promote a read_lock and failing would be more expensive because the reading would have to be done again.

If you can mix a number of read-only locks with a small number of latent_write_locks for which promotion is uncommon, then you have an optimum result.

I'll have to think about this last sentence a little more. Bruno Martinez

I like the latent_write_lock / upgradeable lock idea proposed by Bruno / Alexander. I have been playing with the following interface: namespace detail { template <class RW_Mutex> class read_lock { public: typedef RW_Mutex mutex_type; explicit read_lock(mutex_type& m, bool lock_it = true); explicit read_lock(upgradable_read_lock<mutex_type>& r); explicit read_lock(write_lock<mutex_type>& w); ~read_lock(); void lock(); bool try_lock(); void unlock(); bool locked() const; operator int bool_type::* () const; private: read_lock(const read_lock&); read_lock& operator=(const read_lock&); }; template <class RW_Mutex> class upgradable_read_lock { public: typedef RW_Mutex mutex_type; explicit upgradable_read_lock(mutex_type& m, bool lock_it = true); explicit upgradable_read_lock(write_lock<mutex_type>& w); ~upgradable_read_lock(); void lock(); bool try_lock(); void unlock(); bool locked() const; operator int bool_type::* () const; void transfer_to(read_lock<mutex_type>& r); void transfer_to(write_lock<mutex_type>& w); private: upgradable_read_lock(const upgradable_read_lock&); upgradable_read_lock& operator=(const upgradable_read_lock&); }; template <class RW_Mutex> class write_lock { public: typedef RW_Mutex mutex_type; explicit write_lock(mutex_type& m, bool lock_it = true); explicit write_lock(upgradable_read_lock<mutex_type>& r); ~write_lock(); void lock(); bool try_lock(); void unlock(); bool locked() const; operator int bool_type::* () const; void transfer_to(read_lock<mutex_type>& r); void transfer_to(upgradable_read_lock<mutex_type>& r); private: write_lock(const write_lock&); write_lock& operator=(const write_lock&); }; } // detail class rw_mutex { public: typedef detail::read_lock<rw_mutex> read_lock; typedef detail::upgradable_read_lock<rw_mutex> upgradable_read_lock; typedef detail::write_lock<rw_mutex> write_lock; rw_mutex(); ~rw_mutex(); private: rw_mutex(const rw_mutex&); rw_mutex& operator=(const rw_mutex&); }; There are 3 types of locks: read_lock, upgradable_read_lock and write_lock. Conversions (transfer of mutex ownership) between these types will only occur in an atomic fashion (blocking when appropriate). Conversions that might result in a non-atomic operation are not allowed. Conversions take two forms: 1. Conversion constructor. 2. Member function: void transfer_to(...); The conversion ctor locks only if its argument was locked. The ctor argument is unlocked after the construction. The transfer_to function will throw a lock_error if the lock was not locked, or if the argument does not refer to the same underlying mutex. When s.transfer_to(d) returns (normally), s is unlocked and d is locked (atomically). Destructors unlock only themselves, and have no effect on other locks (there is no persistent linking implied by mutex ownership transfer). If such a link is desired, it is easily built on top of this framework. As described by others, read_locks can share ownership among themselves and not more than one upgradable_read_lock. write_locks maintain exclusive ownership. Here is how some recent code examples might look: void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { rw_mutex::write_lock w(r); //lock promotion //... w.transfer_to(r); } //Point A } If you wanted to catch exceptions at Point A thrown while writing, and still have the read_lock, a simple auxiliary RAII class could be employed: template <class Lock1, class Lock2> class helper { public: explicit helper(Lock2& l2) : l1_(l2), l2_(l2) {} ~helper() {l1_.transfer_to(l2_);} private: helper(const helper&); helper& operator=(const helper&); Lock1 l1_; Lock2& l2_; }; and then f would look like: void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { helper<rw_mutex::write_lock, rw_mutex::upgradable_read_lock> w(r); //... } //Point A } Note that if you don't catch exceptions at Point A, the helper class is needless complexity and transfer of the mutex. It would also be a needless transfer if there is no code at Point A, or if the write section returns early. That is why I like the locks to be unlinked. Linking them would add space overhead to the locks, and time overhead to the destructors, when it is not always desired. But linking is easily built on top with a helper class as shown (only pay for what you use). Another example: void f(rw_mutex& m) { rw_mutex::write_lock w(m); if (...) { rw_mutex::upgradable_read_lock r(w); //lock demotion //... r.transfer_to(w); } //Point A } Same notes about exceptions and helpers. If one accidently codes read_lock instead of upgradable_read_lock, then the transfer_to() call will fail at compile time. If the r.tranfer_to(w) is not needed however, then a read_lock will work just fine. The downside to all this is that the sizeof(rw_mutex) about doubled to support upgradable_read_lock (whether or not you use that functionality). The code size of the read and write locking/unlocking also swelled somewhat. I'm still contemplating the cost/functionality tradeoff, but my current feeling is that it is probably worth it. -Howard

Peter Dimov wrote:

Howard Hinnant wrote:

...

I like the latent_write_lock / upgradeable lock idea proposed by Bruno / Alexander. I have been playing with the following interface:

namespace detail {

template <class RW_Mutex> class read_lock { public: typedef RW_Mutex mutex_type;

explicit read_lock(mutex_type& m, bool lock_it = true); explicit read_lock(upgradable_read_lock<mutex_type>& r); explicit read_lock(write_lock<mutex_type>& w);

~read_lock();

void lock(); bool try_lock(); void unlock(); bool locked() const; operator int bool_type::* () const;

private: read_lock(const read_lock&); read_lock& operator=(const read_lock&); };

[...]

Seems very good to me. Also demonstrates a better lock taxonomy

Better compared to what? The current read/write lock taxonomy? One of the many suggestions in this discussion?

(which allows me to include some on-topic content ;-) ):

Lock

Lock( Mutex&, bool = true ); void lock(); void unlock(); bool locked() const; operator int bool_type::* () const;

TryLock: Lock

+bool try_lock();

TimedLock: TryLock

+bool timed_lock( xtime const & );

The point being that TryLock is a refinement of Lock, and TimedLock is a refinement of TryLock? If so, I agree that's better than TryLock and TimedLock both refining Lock. There are still the constructor issues to deal with in such a lock taxonomy, however. The main one: how do you define destructors that are consistent within a lock concept and also consistent between concepts. E.g., on the one hand it seems that a one-parameter constructor should do the same thing in all lock types--so it would have to block; on the other hand, it seems that TryLock constructors should not block unless instructed to do otherwise. Mike

Peter Dimov wrote:

Michael Glassford wrote:

...

Peter Dimov wrote:

...

Howard Hinnant wrote:

[ read/write mutexes and locks ]

Seems very good to me. Also demonstrates a better lock taxonomy

Better compared to what? The current read/write lock taxonomy? One of the many suggestions in this discussion?

Better compared to the current non-read-write lock taxonomy.

...

...

Lock

Lock( Mutex&, bool = true ); void lock(); void unlock(); bool locked() const; operator int bool_type::* () const;

TryLock: Lock

+bool try_lock();

TimedLock: TryLock

+bool timed_lock( xtime const & );

The point being that TryLock is a refinement of Lock, and TimedLock is a refinement of TryLock? If so, I agree that's better than TryLock and TimedLock both refining Lock. There are still the constructor issues to deal with in such a lock taxonomy, however.

I don't see any. There is one constructor, with the same behavior.

OK. I hadn't realized that you meant there to be literally only one constructor; I do now.

...

The main one: how do you define destructors that are consistent within a lock concept and also consistent between concepts.

~Lock { if( locked() ) unlock(); }

however it looks like you meant 'constructor'.

Sorry, I did mean constructor.

...

E.g., on the one hand it seems that a one-parameter constructor should do the same thing in all lock types--so it would have to block; on the other hand, it seems that TryLock constructors should not block unless instructed to do otherwise.

I meant what I said. There is a single constructor. Its behavior is consistent across all lock concepts (it it weren't, a TryLock would not be a Lock). A mutex exposes a single lock type, which is as refined as possible.

OK, that makes sense and is consistent (which I like). What about the following as an alternative? I retain the hierarchy (a TryLock is a Lock, a TimedLock is a TryLock) and resolve the conflict (of consistency within a concept and consistency across concepts) by the principle that a constructor always blocks unless you specifically tell it not to: Definitions ----------- M: appropriate mutex type namespace lock_state { typedef enum { unlocked=0, locked=1 } lock_state; } //namespace lock_state namespace read_write_lock_state { typedef enum { unlocked=0, read_locked=1, write_locked=2 } read_write_lock_state; } //namespace read_write_lock_state namespace blocking_mode { typedef enum { non_blocking=0, blocking=1 } blocking_mode; } //namespace blocking_mode ScopedLock / ScopedReadLock / ScopedWriteLock --------------------------------------------- lock(M) //always locking, blocking lock(M, lock_state) //blocking ScopedTryLock / ScopedTryReadLock / ScopedTryWriteLock ------------------------------------------------------ try_lock(M) //always locking, BLOCKING try_lock(M, lock_state) //BLOCKING try_lock(M, lock_state, blocking_mode) try_lock(M, blocking_mode) //always locking ScopedTimedLock / ScopedTimedReadLock / ScopedTimedWriteLock ------------------------------------------------------------ timed_lock(M) //always locking, blocking timed_lock(M, lock_state) //blocking timed_lock(M, lock_state, blocking_mode) timed_lock(M, blocking_mode) //always locking timed_lock(M, t) //always locking, blocking for time t

"Peter Dimov" <pdimov@mmltd.net> writes:

This is certainly possible, but I don't see what the additional complexity buys us.

TryLock l( m, false );

if( l.try_lock() ) { }

looks acceptable to me.

TryLock l( m, non_blocking );

if( l.locked() ) { }

doesn't seem much of an improvement.

It does to me. I like names that say what they mean; false could easily be misinterpreted. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Peter Dimov wrote:

compare:

TryLock l( m, unlocked );

if( l.try_lock() ) { }

with:

TryLock l( m, non_blocking );

if( l.locked() ) { }

(Jumping late, forgive me if this has been discussed already.) How about: if( ScopedLock l = try_lock( m ) ) { } where try_lock is function that returns a simple wrapper class: template< Mutex > struct try_locker { Mutex & m; ... }; template< Mutex > try_locker< Mutex > try_lock( Mutex & m ) { return try_locker< Mutex >( m ); }; and ScopedLock is some lockable type which has a constructor that accepts a try_locker. (It would also need a bool-ish conversion to allow the lock to be declared in the "if" statement, but that's not relevant to this discussion.) -- Eric Niebler Boost Consulting www.boost-consulting.com

Eric Niebler wrote:

Peter Dimov wrote:

...

compare:

TryLock l( m, unlocked );

if( l.try_lock() ) { }

with:

TryLock l( m, non_blocking );

if( l.locked() ) { }

(Jumping late, forgive me if this has been discussed already.)

How about:

if( ScopedLock l = try_lock( m ) ) { }

where try_lock is function that returns a simple wrapper class:

template< Mutex > struct try_locker { Mutex & m; ... };

template< Mutex > try_locker< Mutex > try_lock( Mutex & m ) { return try_locker< Mutex >( m ); };

and ScopedLock is some lockable type which has a constructor that accepts a try_locker. (It would also need a bool-ish conversion to allow the lock to be declared in the "if" statement, but that's not relevant to this discussion.)

Interesting idea. I suppose you could even do this: if (ScopedLock l(m, locker())) { } where locker() is a function object that defines operator()(LockType& l) which the lock calls in the constructor, passing *this. You could have locker(), try_locker(), timed_locker(t), etc. Mike

Eric Niebler wrote:

Michael Glassford wrote:

...

Eric Niebler wrote:

[snip]

...

Interesting idea. I suppose you could even do this:

if (ScopedLock l(m, locker())) { }

where locker() is a function object that defines

operator()(LockType& l)

which the lock calls in the constructor, passing *this. You could have locker(), try_locker(), timed_locker(t), etc.

Not quite. In order to declare and initialize a variable in an "if" statement, you need to use the "if( type var = fun() )" form, where the "=" is necessary.

Sorry, it was too late at night and I missed that. I suggest an alternate implementation in another message. Mike

On Jul 8, 2004, at 7:56 AM, Peter Dimov wrote:

One might argue that a lock is naturally moveable...

It is.

but I think that we should constrain ourselves to (fixing) the current noncopyable scoped_lock idiom.

Agreed. I don't particularly want to tackle truly moving locks until I have an rvalue-reference to do it with. The auto_ptr-like hacks are downright demotivating. ;-( -Howard

Michael Glassford wrote:

I agree that movable locks should wait. However, what about something like this, which doesn't require movable locks (concept only--there are probably errors):

[...] Looks like Comeau in strict mode would still not accept it; noncopyable objects cannot be copy-initialized. But let's get back to my original question:

...

...

...

...

This is certainly possible, but I don't see what the additional complexity buys us.

Eric Niebler wrote:

Should we consider alternate designs only after the fixed scoped_lock has achieved wide acceptance? After it has been proposed for standardization? After it has been accepted? If you're talking about making breaking changes to the threading library (aren't you?), isn't the time to consider alternate designs now?

We _are_ considering alternate designs now. As part of this effort I asked:

...

...

...

...

This is certainly possible, but I don't see what the additional complexity buys us.

Eric Niebler wrote:

1) a reduction in interface complexity. - one lock class, instead of a scoped_lock, try_lock, timed_lock, etc. - no bools or enums in constructors; instead, there are clearly named factory functions for customizing lock construction.

2) You can initialize a lock in the condition of an "if" statement.

3) You can return a lock from a function. (Benefit is debatable.)

After giving it some thought: - one lock class: tie; - no bools or enums in constructors: there is a bool argument, but it's (in my opinion) acceptable since there is a single constructor, and the argument participates directly in its postcondition: Lock( Mutex & m, bool l = true ); Post: locked() == l; - you can return a lock from a function: we can make the locks movable regardless of the interface, so it seems possible to ignore this bullet; - if( lock l = try_lock( m ) ) { } This is the main difference. Declarations in conditions are a nice idiom. The typical use is if( X x = f() ) { // do something with x } Our example doesn't fit the pattern, however, as the "// do something" part typically does not reference the lock itself. I don't have much experience with try locks, though. Pretty much the only example that comes to mind is Howard's lock_both: for(;;) { l1.lock(); if( l2.try_lock() ) return; l1.unlock(); l2.lock(); if( l1.try_lock() ) return; l2.unlock(); } (I hope I got that right) and I don't see how it can be improved by the if() idiom. But I may be missing some important use cases.

alnsn@yandex.ru wrote:

Peter Dimov wrote:

...

- you can return a lock from a function: we can make the locks movable regardless of the interface, so it seems possible to ignore this bullet;

- if( lock l = try_lock( m ) ) { }

This is the main difference.

Declarations in conditions are a nice idiom. The typical use is

if( X x = f() ) { // do something with x }

Our example doesn't fit the pattern, however, as the "// do something" part typically does not reference the lock itself.

This is a degenerate case of more general idea of passing lock reference to functions inside condition:

if(lock_ref l = scoped_lock(m)) { // do something with l: action1(l); action2(l); }

Apparently, action1 and action2 can't be called without prior obtaining of a lock. Plus, you get some sort of polymorphism because the functions can accept other locks as well:

action1(scoped_try_lock(m1)); // lock_ref is const reference action2(scoped_timed_lock(m2));

Oh yeah, I heard a talk by Andrei Alexandrescu in which he endorsed that idiom. (Google for "Honey I shrunk the threads".) I like it, but I've never used it. :-P Actually, in the design I was suggesting, there is only one lock type, so you don't have to mess with multiple types, temporaries bound to const references, or a common base class. This idiom becomes easier to use, IMO, with only one lock type. -- Eric Niebler Boost Consulting www.boost-consulting.com

If we continue with the upgradable_read_lock idea, I see one danger that needs to be clearly documented. Some "genius" is going to figure out that you can atomically convert a read_lock into a write_lock: rw_mutex m; void invitation_for_deadlock() { read_lock r(m); // ok to read upgradable_read_lock ur(m); r.unlock(); write_lock w(ur); // ok to write } And the next thing we'll know is that the entire NE US is falling into a blackout. ;-) It took me awhile to spot the deadlock in the above code. Does anyone else see the above code as scary? (scary as in looks ok but isn't). Or is the deadlock obvious to everyone else (and thus not scary)? -Howard

On Jul 9, 2004, at 4:11 PM, Peter Dimov wrote:

...

rw_mutex m;

void invitation_for_deadlock() { read_lock r(m); // ok to read upgradable_read_lock ur(m); r.unlock(); write_lock w(ur); // ok to write }

And the next thing we'll know is that the entire NE US is falling into a blackout. ;-)

It took me awhile to spot the deadlock in the above code. Does anyone else see the above code as scary? (scary as in looks ok but isn't). Or is the deadlock obvious to everyone else (and thus not scary)?

Not scary, IMO, even if not obvious, because it always deadlocks, as soon as you attempt the "idiom". You can't miss it.

I'm not following "always deadlocks". If only one thread enters, at what point does it deadlock (assuming no other thread playing with m)? Experimentally running through this on my prototype implementation with a single thread isn't deadlocking. But perhaps my prototype is buggy? -Howard

On Jul 9, 2004, at 6:05 PM, Peter Dimov wrote:

Howard Hinnant wrote:

...

On Jul 9, 2004, at 4:11 PM, Peter Dimov wrote:

...

...

rw_mutex m;

void invitation_for_deadlock() { read_lock r(m); // ok to read upgradable_read_lock ur(m); r.unlock(); write_lock w(ur); // ok to write }

And the next thing we'll know is that the entire NE US is falling into a blackout. ;-)

It took me awhile to spot the deadlock in the above code. Does anyone else see the above code as scary? (scary as in looks ok but isn't). Or is the deadlock obvious to everyone else (and thus not scary)?

Not scary, IMO, even if not obvious, because it always deadlocks, as soon as you attempt the "idiom". You can't miss it.

I'm not following "always deadlocks". If only one thread enters, at what point does it deadlock (assuming no other thread playing with m)? Experimentally running through this on my prototype implementation with a single thread isn't deadlocking. But perhaps my prototype is buggy?

I wouldn't bet on that. Can I change my opinion to "scary"? ;-)

<chuckle> Only fools and idiots *never* change their mind! :-) So that's two votes for scary. I'm still undecided if it is "too scary". I.e. will documentation make upgradable_read_lock sufficiently safe? I'm hoping so, because there seems to be a vocal need for that functionality, and I don't see a good alternative at the moment. A good rule of thumb for using rw_mutex seems to be that you should never hold more than one lock on it in the same thread. Now that I write that though, I'm wondering if holding a recursive read_lock might be safe enough.... haven't looked into yet. But holding a read_lock and an upgradable_read_lock in the same thread is definitely ill-advised, even if only for an instant. At great extra expense one could put a runtime check into rw_mutex for one thread owning both a read_mutex and an upgradable_read_mutex. It would require storing a vector<thread_id> for every thread sharing read ownership. That would probably make the rw_mutex so expensive as to be useless though. -Howard

On Jul 9, 2004, at 9:47 PM, Matt Hurd wrote:

From memory the use case was reading stuff and then if that said I needed to write something, write it by upgrading the lock.

However, you are not going to be able to escape the deadlock in this case _ever_. AFAICT was if two things read concurrently and need to change state, the both can't if the states are dependent and thus you always have a deadlock.

The upgradable_read_lock, not abused as in the case I showed, will not deadlock. The key (and the restriction) is that only one upgradable_read_lock can be active at a time, though it can share with any number of read_lock's. You are right about the 2-read-to-write promotion case. And that is exactly why upgradable_read_lock's are exclusive among themselves. And it is also why you can't "trick" a read_lock into a promotion (as my abuse-example showed). I believe the upgradable_read_lock is still a viable solution for a very special situation, but it requires suitable documentation to guide the programmer in how not to abuse it. -Howard

On Jul 10, 2004, at 10:38 PM, Matt Hurd wrote:

...

I believe the upgradable_read_lock is still a viable solution for a very special situation, but it requires suitable documentation to guide the programmer in how not to abuse it.

OK. I buy that, but perhaps as a separate mutex beyound the standared shareable (rw). I suspect some platforms will support rw_mutex like behaviour natively without the upradeable part.

<nod> Perhaps so. -Howard

Peter Dimov wrote:

Eric Niebler wrote:

...

1) a reduction in interface complexity. - one lock class, instead of a scoped_lock, try_lock, timed_lock, etc. - no bools or enums in constructors; instead, there are clearly named factory functions for customizing lock construction.

2) You can initialize a lock in the condition of an "if" statement.

3) You can return a lock from a function. (Benefit is debatable.)

After giving it some thought:

- one lock class: tie;

This seems both popular and reasonable. I presume it would be templated on the mutex type?

- no bools or enums in constructors: there is a bool argument, but it's (in my opinion) acceptable since there is a single constructor, and the argument participates directly in its postcondition:

Lock( Mutex & m, bool l = true ); Post: locked() == l;

No argument here, either. I would mildly prefer a couple more constructors, as you know, but I do see understand your arguments for a single constructor and see the advantages of that design.

- you can return a lock from a function: we can make the locks movable regardless of the interface, so it seems possible to ignore this bullet;

I agree.

- if( lock l = try_lock( m ) ) { }

This is the main difference.

Declarations in conditions are a nice idiom. The typical use is

if( X x = f() ) { // do something with x }

Our example doesn't fit the pattern, however, as the "// do something" part typically does not reference the lock itself.

I don't have much experience with try locks, though. Pretty much the only example that comes to mind is Howard's lock_both:

for(;;) { l1.lock(); if( l2.try_lock() ) return; l1.unlock();

l2.lock(); if( l1.try_lock() ) return; l2.unlock(); }

(I hope I got that right) and I don't see how it can be improved by the if() idiom.

This idiom becomes possible when locks become transferable / returnable anyway, so I don't think we need to worry about it now, either. Mike

Peter Dimov wrote:

Michael Glassford wrote:

...

Peter Dimov wrote:

...

After giving it some thought:

- one lock class: tie;

This seems both popular and reasonable. I presume it would be templated on the mutex type?

Seems entirely reasonable. Perhaps it's time to move to formal wording.

template<class M> class scoped_lock { public:

explicit scoped_lock( M & m, bool l = true ); // effects: if( l ) m.lock(); // post: locked() == l && mutex() == &m;

~scoped_lock(); // effects: if( locked() ) mutex()->unlock();

void lock(); // throws: lock_aready_locked if locked(); // effects: mutex()->lock(); // post: locked();

bool try_lock(); // throws: lock_aready_locked if locked(); // returns: mutex()->try_lock(); // post: locked() == (return value);

bool timed_lock( xtime xt ); // throws: lock_aready_locked if locked(); // returns: mutex()->timed_lock( xt ); // post: locked() == (return value);

void unlock(); // throws: lock_not_locked when !locked(); // effects: mutex()->unlock(); // post: !locked();

bool locked() const;

Mutex * mutex() const; // returns: the associated mutex;

operator unspecified-bool-type() const; // returns: locked(). };

Yes, this is much what I had in mind. The mutex type(s) would continue to supply a typedef, I presume (but only one): class some_mutex_type { public: typedef lock<some_mutex_type> scoped_lock; //... }; Also, although there may only be one lock class, there are still three lock concepts specifying which lock operations are supported by each of the three mutex concepts, right? (Unless we actually do combine all of the mutex types into one as well.)

I've added the mutex() accessor to support Andrei's lock idiom:

OK.

void f() { scoped_lock lock( my_mutex ); f( lock ); }

void f( scoped_lock & lock ) { // check for lock validity assert( lock.locked() && lock.mutex() == &my_mutex );

// proceed with operation }

Now that we got rid of the excess locks, how about doing the same with the mutexes?

I had considered this, but there does seem to be some benefit in having separate mutex types, which is what I assume led to there being three mutex types and three lock types in the original design. You've noted these reasons below, but I'll reiterate: * On pthreads, the timed mutex requires an additional data member, (condition variable) to handle cases when pthreads_timedlock isn't supported. * On WinNT, the timed mutex operations require a win32 mutex object, while the mutex and try mutex can use a win32 critical section. * On Win9x, the timed mutex and try mutex operations require a win32 mutex object, while the mutex can use a win32 critical section. In other words, on the most widely-used platforms, collapsing the mutex types into one imposes some penalty (larger mutex object or more limited implementation options) on users. Also (I ask, not as a hypothetical question, but as a request for information): is there another platform where combining the mutex types incurs a similar or worse penalty?

class mutex // DefaultConstructible { private:

void lock(); // pre: *this is not locked by the current thread // effects: blocks until *this is unlocked // post: *this is locked by the current thread

bool try_lock(); // returns: true iff *this was unlocked // post: if *this was unlocked, *this is now locked by the current thread

bool timed_lock( xtime xt ); // returns: true if *this is now locked by the current thread // effects: if *this is unlocked, returns immediately, otherwise blocks // until either *this is unlocked or xt has been reached // post: if *this was or became unlocked, *this is now locked by the // current thread

void unlock();

// pre: *this is locked by the current thread // post: *this is unlocked };

The main potential issue here is mutex::timed_lock; try_lock doesn't seem controversial. It is true that Windows 95 does not have TryEnterCriticalSection, but an implementation can use Alexander Terekhov's alternative:

The Boost.Threads try_mutex in CVS currently checks if TryEnterCriticalSection is available and uses it if it is. To me this seems a reasonable implementation for now, and if it proves not to be good enough, a TryEnterCriticalSection facsimile can be implemented for Win9x platforms, as you say.

http://lists.boost.org/MailArchives/boost/msg64648.php

The mutex::timed_lock situation is a bit more complicated. POSIX labels pthread_mutex_timedlock as part of the Timeouts option, and I don't know whether this is because many implementations deliberatley do not provide timed locks, or because this is a relatively new addition to pthreads. Does someone know?

My not-so-informed opinion at the moment is that we should provide timed_lock. I see that the current Boost.Threads implementation uses a mutex and a condition variable to implement a timed_lock-capable mutex, so we have a proof of concept that it can always be done, however there may be efficiency concerns.

OK.

My line of thought is that since a mutex (usually) has a fast path user space portion and a slow path kernel space portion, with the timed_lock baggage not affecting the fast path, it seems reasonable to always require timed_lock (remember we're in "next standard mode" now, thinking severals years ahead).

I think I'm being dense, but I'm not sure I understand what you mean by "require timed_lock" (require platform support for it?) or what this part of the paragraph is getting at.

Thoughts?

Some more random remarks regarding the state of Boost.Threads. Several files still seem to have incorrect line endings. This usually happens when checking in Windows line endings with a Unix CVS client. Please don't do that.

I don't. I typically use the VC++ 7.1 editor and TortoiseCVS. I seem to remember a problem like this being discussed in the Spirit mailing list with an earlier TortoiseCVS, but I'm using the latest version that was supposed to have fixed that problem.

I was somewhat surprised by the mutex/cv implementation. I expected a thin wrapper over pthreads, but this is not the case. At first sight it seems that the complexity is caused by the fact that boost::condition supports recursive mutexes that are locked more than once, whereas POSIX does not. I do not recall any discussions about this issue, and I'm not sure why this decision was made.

I can't comment on this since I haven't yet really looked at the condition variable implementation and had nothing to do with the original decisions.

It seems wrong (and the implementation seems buggy), but as usual, I may be missing something.

Alexander Terekhov has mentioned one problem with the Win32 condition variable implementation that I recall (I have the link somewhere but don't see it at the moment); do you have others in mind? Mike

Finally getting time to answering this: David Abrahams wrote:

Michael Glassford <glassfordm@hotmail.com> writes:

...

I had considered this, but there does seem to be some benefit in having separate mutex types, which is what I assume led to there being three mutex types and three lock types in the original design. You've noted these reasons below, but I'll reiterate:

* On pthreads, the timed mutex requires an additional data member, (condition variable) to handle cases when pthreads_timedlock isn't supported.

* On WinNT, the timed mutex operations require a win32 mutex object, while the mutex and try mutex can use a win32 critical section.

* On Win9x, the timed mutex and try mutex operations require a win32 mutex object, while the mutex can use a win32 critical section.

In other words, on the most widely-used platforms, collapsing the mutex types into one imposes some penalty (larger mutex object or more limited implementation options) on users. Also (I ask, not as a hypothetical question, but as a request for information): is there another platform where combining the mutex types incurs a similar or worse penalty?

If the difference is in the code that must be generated within the locking function, I'd guess that the differently-named functions can handle it. If the difference is in the data stored in the mutex and/or the lock, it could be an issue. You might be able to use boost::variant to minimize storage. It would be worth doing some experimentation to see whether optimizers can make the other overheads disappear.

The difference in the pthreads case is a difference in the data that must be stored in the Boost.Threads mutex object: each one needs to store both a mutex and a condition variable, though I suppose--at the expense of requiring the storage to be dynamically allocated--space for the condition variable could be allocated only on platforms that don't support pthreads_timedlock. In the Win32 cases, if you're going to use timed mutex functions (or, on Win9x, try mutex functions), the Boost.Threads mutex object needs to allocate a Win32 mutex object; if not, it can allocate a Win32 critical section. Currently Boost.Threads mutexes objects can tell whether you intend to use try or timed functions by whether you declare a try_mutex or timed_mutex, and allocate the appropriate Win32 synchronization object accordingly. But if all mutex types are combined into one there won't be any way for it to tell, and it will have to allocate a Win32 mutex object always. Another option in the Win32 case, which Peter already mentioned, is to write an alternate implementation of critical sections (such as the one Alexander Terekhov outlined an implementation for) that supports both try and timed functions. If done well, this would be desirable even if the mutex types are not combined. Mike

Peter Dimov wrote:

Michael Glassford wrote:

[...]

...

The difference in the pthreads case is a difference in the data that must be stored in the Boost.Threads mutex object: each one needs to store both a mutex and a condition variable, though I suppose--at the expense of requiring the storage to be dynamically allocated--space for the condition variable could be allocated only on platforms that don't support pthreads_timedlock.

No, no.

The goal of mutex::timed_lock is not to cripple the mutex by turning it into a monitor. This is unacceptable. The goal is to provide an efficient timed_lock. If there is no efficient timed lock available on the platform, there should be no mutex::timed_lock.

Sorry, the context doesn't make it clear but my paragraph above referred to the timed_mutex class which, according to what I remember of your discussions with Howard, you (?) suggested would implement a timed lock regardless of whether it was supported by the platform and regardless of whether it could be implemented efficiently. I wasn't referring to mutex::timed_lock at all.

The argument we had with Howard is not about the above, on which we - hopefully - agree. The argument was about whether, from standard point of view, an implementation that doesn't provide mutex::timed_lock should be conforming. It is mostly a specification/theory/philosophy issue. In practice, the rule is simple. Have _POSIX_TIMEOUTS -> will travel, er, will have pthread_mutex_timedlock and mutex::timed_lock.

I have to say that I'm not too keen on the idea of an optional timed_lock() member function that only exists if it can be implemented efficiently, but that's another discussion.

The idea is that our C++ mutex should always be competitive with the "best" native mutex available on the platform.

It's hard to disagree with this.

(Incidentally, on Windows, the best native mutex is neither CRITICAL_SECTION nor HMUTEX, it's Alexander's event-based thing. Or so he says. But he's usually right about these things.)

Yes, and I hope to look into it when I get time. Mike

Michael Glassford wrote:

...

The idea is that our C++ mutex should always be competitive with the "best" native mutex available on the platform.

It's hard to disagree with this.

...

(Incidentally, on Windows, the best native mutex is neither CRITICAL_SECTION nor HMUTEX, it's Alexander's event-based thing. Or so he says. But he's usually right about these things.)

Yes, and I hope to look into it when I get time.

I'm not a Windows programmer, so feel free to disregard anything that follows, but weren't events considered and rejected already? From http://www.boost.org/libs/thread/doc/rationale.html#events: "Experienced programmers using the Windows platform today report that event variables are a continuing source of errors, even after previous bad experiences caused them to be very careful in their use of event variables. Overt problems can be avoided, for example, by teaming the event variable with a mutex, but that may just convert a race condition into another problem, such as excessive resource use. One of the most distressing aspects of the experience reports is the claim that many defects are latent. That is, the programs appear to work correctly, but contain hidden timing dependencies which will cause them to fail when environmental factors or usage patterns change, altering relative thread timings. The decision to exclude event variables from Boost.Threads has been surprising to some Windows programmers. They have written programs which work using event variables, and wonder what the problem is. It seems similar to the "goto considered harmful" controversy of 30 years ago. It isn't that events, like gotos, can't be made to work, but rather that virtually all programs using alternatives will be easier to write, debug, read, maintain, and be less likely to contain latent defects." This is not to say that "Alexander's event-based thing" can't be done correctly, but I feel like this is covered ground. -- Christopher Currie <codemonkey@gmail.com>

David Abrahams wrote: [...]

Windows events have giant safety holes in 'em.

That's correct. The motto is "don't have sex with events without condoms." regards, alexander. -- post_pre<post_pre<post_pre<MostDerived, Base>, Derived>, MostDerived> o;

Peter Dimov wrote:

Michael Glassford wrote:

...

Peter Dimov wrote:

...

It seems wrong (and the implementation seems buggy), but as usual, I may be missing something.

Alexander Terekhov has mentioned one problem with the Win32 condition variable implementation that I recall (I have the link somewhere but don't see it at the moment); do you have others in mind?

For a condition being used with a recursive_mutex, condition::wait does:

typename lock_ops::lock_state state; lock_ops::unlock(mutex, state); m_impl.do_wait(...); lock_ops::lock(mutex, state);

The (Windows, for example) recursive mutex stores its lock count in state:

void recursive_mutex::do_unlock(cv_state& state) { state = m_count; m_count = 0;

if (m_critical_section) release_critical_section(m_mutex); else release_mutex(m_mutex); }

and restores it in do_lock( cv_state& ).

However, if there is a thread switch just after m_count = 0, and then the recursive_mutex is locked, its m_count would now be 1. After the do_wait, do_lock( cv_state& ) will restore the m_count to the original value, and the count update caused by the "extra" lock would be lost. Oder?

When I first read this it made sense to me, but now I'm not seeing it. It's not possible for another thread (thread B) to lock the recursive mutex just after thread A executes m_count = 0 because thread A still holds the m_mutex, right? Mike

On Jul 11, 2004, at 8:46 AM, Peter Dimov wrote:

Seems entirely reasonable. Perhaps it's time to move to formal wording.

template<class M> class scoped_lock { public:

explicit scoped_lock( M & m, bool l = true ); // effects: if( l ) m.lock(); // post: locked() == l && mutex() == &m;

~scoped_lock(); // effects: if( locked() ) mutex()->unlock();

void lock(); // throws: lock_aready_locked if locked(); // effects: mutex()->lock(); // post: locked();

bool try_lock(); // throws: lock_aready_locked if locked(); // returns: mutex()->try_lock(); // post: locked() == (return value);

bool timed_lock( xtime xt ); // throws: lock_aready_locked if locked(); // returns: mutex()->timed_lock( xt ); // post: locked() == (return value);

void unlock(); // throws: lock_not_locked when !locked(); // effects: mutex()->unlock(); // post: !locked();

bool locked() const;

Mutex * mutex() const; // returns: the associated mutex;

Why return a pointer instead of a reference? What about this instead? Mutex& mutex(); const Mutex& mutex() const; That would put to rest any questions about mutex() transferring mutex ownership, e.g.: delete lock.mutex();

operator unspecified-bool-type() const; // returns: locked(). };

I've added the mutex() accessor to support Andrei's lock idiom:

void f() { scoped_lock lock( my_mutex ); f( lock ); }

void f( scoped_lock & lock ) { // check for lock validity assert( lock.locked() && lock.mutex() == &my_mutex );

// proceed with operation }

Now that we got rid of the excess locks, how about doing the same with the mutexes?

That worries me a lot. We need several different flavors of mutex because the more functionality you put into a mutex, the more expensive it is both in terms of size and speed. Why pay for a recursive mutex if you don't need one? Why pay for a timed mutex? But when you need one of these more expensive types, then the price is worth it. We can get away with a scoped/try/timed lock precisely because lumping that functionality into these templated classes does not add overhead (the overhead is in the mutex).

I was somewhat surprised by the mutex/cv implementation. I expected a thin wrapper over pthreads, but this is not the case. At first sight it seems that the complexity is caused by the fact that boost::condition supports recursive mutexes that are locked more than once, whereas POSIX does not. I do not recall any discussions about this issue, and I'm not sure why this decision was made. It seems wrong (and the implementation seems buggy), but as usual, I may be missing something.

I can't speak for the boost implementation (haven't carefully studied it), but the Metrowerks implementation also supports conditions operating on a recursive mutex. Our implementation (and I strongly suspect boost's as well) also supports conditions operating on non-recursive mutexes. The condition::wait<NonRecursiveMutex> /is/ a thin wrapper around pthread_cond_wait (when implemented on pthreads). Overhead is only incurred for condtion::wait<RecursiveMutex>. On the other hand, our Windows implementation of condition::wait follows the algorithm laid out by Alexander Terekhov's "Algorithm 8a" posted in comp.programming.threads on April 27, 2001 (and noted as such in that file Alexander). In this case the wait() function does not differ depending upon the recursiveness of the mutex. This underscores the importance of having different types of mutexes. Adding functionality to a mutex (beyond a non-recursive, non-try, non-timed mutex) may well add significant overhead on some platforms, whether or not you actually use that added functionality. -Howard

Peter Dimov wrote: [... Mutex * mutex() const ...] And the Mutex thing (std0X::whatever) shall also provide something like pthread_mutex_t * c_mutex(); pthread_mutex_t const * c_mutex() const; That pthread_mutex_t shall be defined in <cthread> (and it shall of course also be available through *deprecated* <pthread.h>) and shall perform dynamic dispatching for "C-style" code (depending on "C++ mutex type"). Oder?

...

I can't speak for the boost implementation (haven't carefully studied it), but the Metrowerks implementation also supports conditions operating on a recursive mutex.

Interesting. I presume that this was a deliberate design decision.

It has a precondition "lock.mutex()->locked() && lock.mutex()-> lock_count() == 1" (or something like that... brrrr, so many "lock" things... "guard" would sound much better ;-) ) regards, alexander.

Peter Dimov wrote: [...]

Forget that <cthread> for a while, how about sharing your thoughts on the proposed elimination of the try/timed axis. ;-)

Oh yeah. ;-) In the past (before "swap_based_mutex"... having only something along the lines of old/current pthread-win32's mutex thing) and given PTHREAD_TIMEOUT_ALLOWED/PTHREAD_TIMEOUT_DISALLOWED (stuff that was proposed--among other interesting "military" things--in 1003.1d/D11 and was also ditched later), I had some reservations... http://groups.google.com/groups?selm=3F096C73.6A3DCA60%40web.de http://groups.google.com/groups?selm=3f0c0a3d%40usenet01.boi.hp.com http://groups.google.com/groups?selm=3F0C0F9E.FACB8EA3%40web.de (If you read this entire message read also 3F0E944B.68DB9DCA%40web.de) ---- The point is that a mere presence of timedlock() may slow down pthread_mutex_unlock(), for example. [reference to pthreads-win32] ---- but not now.

...

...

...

I can't speak for the boost implementation (haven't carefully studied it), but the Metrowerks implementation also supports conditions operating on a recursive mutex.

Interesting. I presume that this was a deliberate design decision.

It has a precondition "lock.mutex()->locked() && lock.mutex()-> lock_count() == 1" (or something like that... brrrr, so many "lock" things... "guard" would sound much better ;-) )

Does it? I think that the Boost implementation tries to operate "correctly" for lock_count() > 1, but I may have misread the code.

I meant windows thing that is used in Metrowerks [if I got Howard right] and pthread-win32. IIRC, I've "voiced objection" at the time the boost::condition and recursive locks were discussed here. Uhmm, can't find it... but here's something: ;-) http://groups.google.com/groups?selm=3D484233.AD1E26E8%40web.de regards, alexander.

Alexander Terekhov wrote:

Peter Dimov wrote: [...]

...

Forget that <cthread> for a while, how about sharing your thoughts on the proposed elimination of the try/timed axis. ;-)

Oh yeah. ;-) [...]

This is where it all started: http://lists.boost.org/MailArchives/boost/msg10142.php I have to admit, Bill Kempf had gotten many things in the original design right, including a single boost::mutex and a reference counted body + handle boost::thread class. I even participated in that discussion, sigh.

Howard Hinnant wrote:

On Jul 12, 2004, at 11:28 AM, Peter Dimov wrote:

...

Howard Hinnant wrote:

...

On Jul 11, 2004, at 8:46 AM, Peter Dimov wrote:

[...]

...

...

Mutex * mutex() const; // returns: the associated mutex;

Why return a pointer instead of a reference? What about this instead?

Mutex& mutex(); const Mutex& mutex() const;

Because of the use case shown below:

...

...

void f( scoped_lock & lock ) { // check for lock validity assert( lock.locked() && lock.mutex() == &my_mutex );

// proceed with operation }

A pointer makes it clear that it is the identity of the associated mutex that is being queried. A (const-"correct") reference return implies that the purpose of the accessor is to return, well, a reference to the mutex object, presumably so that the client can do something with it.

...

That would put to rest any questions about mutex() transferring mutex ownership, e.g.:

delete lock.mutex();

I considered

bool is_associated_with( Mutex const & m ) const;

but that's a bit too much of a handholding for my taste, and doesn't allow us to use mutex() in the Effects clauses. The kind of a person that would delete lock.mutex() would never get a multithreaded program correct anyway.

If we expose either a Mutex* or a Mutex&, and we standardize a public Mutex interface (with lock(), unlock(), etc.), then we are saying that one can call functions on the pointer or reference returned by mutex(). And now that I write that sentence my skin is beginning to crawl. ;-)

I have occasionally seen a need for using a mutex outside of a scoped_lock, when the lock/unlock pattern is not as neat as what scoped_lock provides. Alexander's read/write lock algorithm is a good example: http://groups.google.com/groups?selm=3B166244.F923B993%40web.de . And so I do not object to standardizing a public mutex interface so that they can be used outside of a scoped_lock. But allowing a mutex to be manipulated within a scoped_lock seems dangerous.

Brainstorming:

template <class Mutex> bool operator==(const scoped_lock<Mutex>&, const Mutex&);

template <class Mutex> bool operator==(const Mutex&, const scoped_lock<Mutex>&);

instead of Mutex* scoped_lock::mutex() const;

?

Might look like:

void f( scoped_lock & lock ) { // check for lock validity assert( lock.locked() && lock == my_mutex );

// proceed with operation }

Haven't even prototyped it, so I'm not even sure it will work. Just a thought.

If you don't want people messing with the mutex through the scoped_lock, use a void* disguised as a typedef: typedef void const* mutex_id_type; struct mutex { mutex_id_type id() const { return this; } ... }; template< class Mutex > { Mutex & m_; mutex_id_type mutex_id() const { return m_.id(); } }; Usage might look like: void f( scoped_lock & lock ) { // check for lock validity assert( lock.locked() && lock.mutex_id() == my_mutex.id() ); // proceed with operation } -- Eric Niebler Boost Consulting www.boost-consulting.com

Howard Hinnant wrote:

On Jul 12, 2004, at 11:28 AM, Peter Dimov wrote:

[...]

If we expose either a Mutex* or a Mutex&, and we standardize a public Mutex interface (with lock(), unlock(), etc.), then we are saying that one can call functions on the pointer or reference returned by mutex(). And now that I write that sentence my skin is beginning to crawl. ;-)

This is what 'class mutex' looks like in my original message: class mutex // DefaultConstructible { private: void lock(); bool try_lock(); bool timed_lock( xtime xt ); void unlock(); }; IOW, the function names are standardized, but they aren't public. The intent is to allow users to write a mutex class M that can be used with std::tr2::lock<M>. As a mutex doesn't have a public interface, the mutex() accessor cannot be used to manipulate a lock's associated mutex. It is, of course, possible to make this interface public, but I haven't proposed that. ;-) [...]

Brainstorming:

template <class Mutex> bool operator==(const scoped_lock<Mutex>&, const Mutex&);

template <class Mutex> bool operator==(const Mutex&, const scoped_lock<Mutex>&);

instead of Mutex* scoped_lock::mutex() const;

?

That's just my 'is_associated_with' with a different name. It's a bit more limited than mutex(); for example, you can't use a map<void*, ...> keyed on mutex(), and you can't compare l1.mutex() and l2.mutex() (using std::less<void*>) to derive a locking order.

...

Do you have data on whether your platforms support pthread_mutex_timedlock?

I have one platform to support where I preferred a different implementation for mutex and try_mutex: Win98. Admittedly that one is quickly going obsolete. Nevertheless I currently still need to support it.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/ dllproc/base/tryentercriticalsection.asp

...

TryEnterCriticalSection

Requires Windows XP, Windows 2000 Professional, or Windows NT Workstation 4.0.

Have you seen Alexander's 'swap-based' implementation? The link was in my original post, right after "It is true that Windows 95 does not have TryEnterCriticalSection, but an implementation can use Alexander Terekhov's alternative:" http://lists.boost.org/MailArchives/boost/msg64648.php

Mac OS X up through 10.3.4 (most current) does not appear to support pthread_mutex_timedlock, and so on this platform my mutex implementation differs from my timed_mutex implementation.

Not good. This means that you cannot be persuaded to abandon timed_mutex, which in turn means that the future standard will probably have a timed_mutex, even if at that future time Mac OS X does have pthread_mutex_timedlock. The alternative reality would have a mutex with timed_lock #ifdef'ed on _POSIX_TIMEOUTS until conformance arrives.

Howard Hinnant wrote:

On Jul 12, 2004, at 4:39 PM, Peter Dimov wrote:

...

The alternative reality would have a mutex with timed_lock #ifdef'ed on _POSIX_TIMEOUTS until conformance arrives.

<sigh> It isn't just Mac OS X either. There are other (embedded) platforms I've neglected to mention because I'm not positive exactly what my NDA is. But it can get pretty ugly out there in some cases. If OS's would just adopt the pthreads knowledge and experience the world would be such a better place. Multithreading is a tough area and OS designers aren't necessarily experts in that particular area (and I'm not claiming to be either). And without the proper OS functionality, add-on threading libraries are inherently limited. ... No point I'm trying to make. Just being grumpy. ;-)

I understand. However in this particular case I'm not sure that you're doing your users a favor. Let's say I'm a library/application developer that can take advantage of timed_lock to provide some enhancements as a QoI, but at the same time I most definitely don't want to sacrifice performance; i.e. performance is a priority that far outweighs the optional enhancements provided by timed_lock. So I'd prefer to use mutex::timed_lock, getting a compile-time error on platforms that do not support an overhead-free "timed mutex". If, on the other hand, the performance loss (~3-5x, I've read) is not a concern, I can simply emulate the timed mutex myself; your emulation is no better than mine.

Howard Hinnant wrote:

How do we serve the client who needs a timed mutex, on every platform, and would rather not implement it himself? If mutex::timed_lock sometimes compiles and sometimes doesn't, then that isn't the answer. And telling the client that he can just emulate this functionality himself is no different than telling him he can just emulate the STL himself. The emulation on platforms with non-native support requires a certain amount of expertise, careful coding, and most importantly, time. Must everyone who must have a timed mutex become an implementor of it?

Probably not, _if_ this hypothetical client exists. I don't doubt it that once you provide a timed_mutex, many will find it useful, with or without quotes. But the mutex+condition underneath will probably mean that these users are not getting their money's worth from the design. If they explicitly see the monitor pattern hidden under the opaque timed_mutex, they might be able to put it to better use.

I don't have a problem if mutex is allowed to optionally sport a timed_lock() member function (presumably only if it could do so with "acceptable" cost). I just don't want to require it to (in case the costs are deemed "unacceptable").

I want the standard to require mutex::timed_lock, because if there is no such requirement, no implementation will provide it. Why bother? No points are taken off conformance tests, and the users can't really demand it, because it's not required.

I'd rather there exist a timed_mutex class with that requirement. Would this not satisfy both of our hypothetical clients?

Yes, having both mutex and timed_mutex will satisfy our hypotheticals. However if mutex::timed_lock is required, timed_mutex makes no sense from specification point of view. Anyway, (mutex with try_lock and optional timed_lock + timed_mutex) * 2 + static_mutex would still be better than (mutex + try_mutex + timed_mutex) * 2.

Howard Hinnant wrote:

On Jul 13, 2004, at 12:06 PM, Peter Dimov wrote:

...

Yes, having both mutex and timed_mutex will satisfy our hypotheticals. However if mutex::timed_lock is required, timed_mutex makes no sense from specification point of view.

My bad. There are at least 3 important clients to consider:

1. Give me mutex::timed_lock(), but only if it doesn't cost much, else I want a compile time error.

2. Give me timed_mutex::timed_lock(). Gotta have it on every platform.

3. Give me mutex::lock(), and please make it as small and fast as possible. I'm putting this mutex into my objects, and I'll have container<my_object>, so minimal overhead in the mutex is important (I don't care about timed_lock(), never use it).

Almost. Client 1 is actually: 1a. Give me mutex::timed_lock that (if it) doesn't have a cost; that is, it is as fast as mutex::lock in the non-blocking case, and it doesn't impose performance penalties on mutex::lock, mutex::try_lock, mutex::unlock. This is effectively the same as POSIX. OK, it may be "almost doesn't have a cost", or "doesn't cost much", but the intent is clear. In a perfect world, all platforms will have such a timed_lock, and all clients would be happy. And our specification should not be suboptimal in this world. OTOH I appreciate your arguments. Even though pthread_mutex_timedlock may be implementable everywhere, it's a fact of life that some platforms do not, and will not, supply it. However if a platform has a timed lock that satisfies (1a) then it should be exposed as mutex::timed_lock. I don't know whether there's such a precedent in the standard library; nothing optional comes to mind. A problem with timed_mutex is that once it gets into the standard, it can't be removed, even if it turns out that type (2) clients are few, or that having a timed_mutex handy doesn't encourage careful design. Whereas the reverse situation - no std::tr2::timed_mutex and customer revolt - is easily fixable; you just provide it as an extension (something that Boost.Threads will also need to do, BTW, even if we redesign the mutexes and the locks). Since the interface is already specified by std::tr2::mutex, a hash_map situation should not occur. ;-) Hm. Where were we. Oh yes. - mutex::timed_lock: optional. - timed_mutex: in the std or not? - recursive_mutex: in the std? Seems so. - condition::wait with recursive_mutex: compiles? - condition::wait with recursive_mutex locked more than once: defined? if so, how?

Howard Hinnant wrote: [... cv.wait with recursively locked mutex ...]

This is the big question in my mind right now. I know how to make it work with a home-grown recursive mutex. But I don't know how to make it work with a native recursive mutex, combined with a native condition. I'm somewhat surprised that it doesn't just work.

It does just work. As long as you call cv.wait with a recursive mutex locked by the calling threads and its "lock count == 1". Calling it with "lock count != 1" is a bug (violation of a precondition in C++ terms).

Alexander, can we send a bug report to the pthreads guys?

http://www.opengroup.org/austin/defectform.html

Or would we just be laughed out of the room? I'm not educated enough to know what the problems are to making it work.

It is a philosophical issue, not technical. I wouldn't oppose if you would propose to add int pthread_mutex_setlockcount( // must be locked by the calling thread pthread_mutex_t * mutex, // must be positive (> 1 can be set on PTHREAD_MUTEX_RECURSIVE only) unsigned lockcount, // can be null unsigned * oldlockcount ); (or something like that, "get" aside for a moment) so that you could do [...] while (!predicate) { unsigned lockcount; pthread_mutex_setlockcount(&mutex, 1, &lockcount); pthread_cond_wait(&condvar, &mutex); pthread_mutex_setlockcount(&mutex, lockcount, 0); } [...] if/when you're ablsolutely 100% sure that what you're doing is OK.

And clearly it doesn't work today, so it's a problem whether or not it can be fixed. <sigh> That probably backs us into undefined behavior if the mutex is recursively locked,

Exactly. "may fail error" (in POSIX terms; optional "throws" that end up in std::unexpected with no return from the "failed" call). http://groups.google.com/groups?selm=3434E6BA.ABD%40zko.dec.com ---- The one omission in XSH5 recursive mutex support was a standard error code for the programming ERROR of trying to wait on a condition with a recursively locked mutex. If it's safe to release the recursive locks, the code should have done so. If it's not safe to release, then the runtime MUST NOT do so. ----

or refusing to compile at all with a recursive mutex.

No, that's not good. regards, alexander.

Howard Hinnant wrote:

On Jul 14, 2004, at 6:27 AM, Alexander Terekhov wrote:

...

It is a philosophical issue, not technical.

Thanks for your comments.

Speaking philosophically ... just wondering out loud, not trying to solve anything, I wonder if this doesn't boil down to an object oriented view vs a functional view. Because the few times I've felt the need for a recursive mutex is when I had an object, which contained a single mutex, which had several public member functions that just happened to call each other as an implementation detail. Something like:

class A { public: void foo1(); // calls foo2 and foo3 under the covers void foo2(); void foo3(); private: mutex mut_; };

Yep, classic. ;-) The solution is, of course: class A { public: void foo1() { scoped_lock<> lock(mut_); foo1_impl(); } void foo2() { scoped_lock<> lock(mut_); foo2_impl(); } void foo3() { scoped_lock<> lock(mut_); foo3_impl(); } private: void foo1_impl(); // calls foo2_impl & foo3_impl void foo2_impl(); void foo3_impl(); mutex mut_; }; I have a recursive_mutex use case that's not as trivial, though. Imagine a mutex pool with a fixed size N that protects an unbounded set of objects (hashing the object address mod N to determine the mutex to lock). Now when you need to protect two objects at the same time, due to the probability of a collision the mutexes need to be recursive. It's still not watertight, because if the two locks are removed from each other, this seems like a deadlock invitation; and if the two locks are made at the same time, the recursive lock can be avoided locally. [...]

Admittedly, I've never felt the need to wait on a recursively locked mutex, but it seems like it would be reasonable for foo2() in the above example to do so, whether or not it had been called from an external client, or from foo1().

That's exactly the problem. If foo2 waits, it will release not only its own lock, but also foo1's lock, which may not be safe to release (i.e. foo1 may have left the object in a broken state, expecting that nobody can see it since it holds a lock.) It's all in Butenhof's posts.

On Wed, 14 Jul 2004 15:27:08 -0400, David Abrahams <dave@boost-consulting.com> wrote:

"Peter Dimov" <pdimov@mmltd.net> writes:

...

I have a recursive_mutex use case that's not as trivial, though. Imagine a mutex pool with a fixed size N that protects an unbounded set of objects (hashing the object address mod N to determine the mutex to lock). Now when you need to protect two objects at the same time, due to the probability of a collision the mutexes need to be recursive. It's still not watertight, because if the two locks are removed from each other, this seems like a deadlock invitation; and if the two locks are made at the same time, the recursive lock can be avoided locally.

Can't you just check the hashes and only lock once in that case?

AFAICT, you'd have to record the objects to which the specific thread had the lock otherwise you can't discriminate on who owns the lock. You could do this either as TSS for which object or, alternatively, via an intrusive which_thread struct (bit field for # of threads?) in the object I guess. I don't have a good solution to this. The way I approach it is just to write code very carefully to avoid the deadlock, but I still get bitten from time to time. On the flip side, if I have a lock per object in a large collection, on win32 I get tens or hundreds of thousands of kernel objects, this made me uncomfortable so I went to a vector of mutexes for this puppy but only as it made me uncomfortable. Sure this was a bad thing for a win9X, but I have not been able to dig up, or see, any problems with doing this on win32 (i.e. it works) apart from the fact that it looks strange and no-one else seems to do it, which is enough to make me nervous. Any advice here? $AUD 0.02, Matt Hurd.

Matt Hurd <matt.hurd@gmail.com> writes:

On Wed, 14 Jul 2004 15:27:08 -0400, David Abrahams <dave@boost-consulting.com> wrote:

...

"Peter Dimov" <pdimov@mmltd.net> writes:

...

I have a recursive_mutex use case that's not as trivial, though. Imagine a mutex pool with a fixed size N that protects an unbounded set of objects (hashing the object address mod N to determine the mutex to lock). Now when you need to protect two objects at the same time, due to the probability of a collision the mutexes need to be recursive. It's still not watertight, because if the two locks are removed from each other, this seems like a deadlock invitation; and if the two locks are made at the same time, the recursive lock can be avoided locally.

Can't you just check the hashes and only lock once in that case?

AFAICT, you'd have to record the objects to which the specific thread had the lock otherwise you can't discriminate on who owns the lock.

That's only true if a given thread can lock more than two objects at the same time. Isn't that likely to lead to deadlock, regardless? If each thread is only limited to locking one pair you can lock the mutex for the first object, check the 2nd one to see if it's got the same hash, and if not, lock the 2nd object's mutex. I'm pretty sure, anyway ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

"Peter Dimov" <pdimov@mmltd.net> writes:

David Abrahams wrote:

...

Matt Hurd <matt.hurd@gmail.com> writes:

...

On Wed, 14 Jul 2004 15:27:08 -0400, David Abrahams <dave@boost-consulting.com> wrote:

...

"Peter Dimov" <pdimov@mmltd.net> writes:

Can't you just check the hashes and only lock once in that case?

AFAICT, you'd have to record the objects to which the specific thread had the lock otherwise you can't discriminate on who owns the lock.

That's only true if a given thread can lock more than two objects at the same time. Isn't that likely to lead to deadlock, regardless?

Yep, have you read the last sentence in the block you quoted?

Yes, but I don't see how it's relevant.

Anyway: consider this (oversimplified) situation:

// f.cpp

static object o;

void f() { lock( &o ); // do things unlock( &o ); }

// g.cpp

void f();

static object o2;

void g() { lock( &o2 ); f(); unlock( &o2 ); }

Since the f() lock is always nested within the g() lock, there can be no deadlock.

Sorry, I don't see more than two objects locked at the same time here. No big deal, I'm probably off base here so will relurk. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

On Wed, 14 Jul 2004 18:45:00 +0300, Peter Dimov <pdimov@mmltd.net> wrote:

Howard Hinnant wrote:

...

On Jul 14, 2004, at 6:27 AM, Alexander Terekhov wrote:

...

It is a philosophical issue, not technical.

Thanks for your comments.

Speaking philosophically ... just wondering out loud, not trying to solve anything, I wonder if this doesn't boil down to an object oriented view vs a functional view. Because the few times I've felt the need for a recursive mutex is when I had an object, which contained a single mutex, which had several public member functions that just happened to call each other as an implementation detail. Something like:

class A { public: void foo1(); // calls foo2 and foo3 under the covers void foo2(); void foo3(); private: mutex mut_; };

Yep, classic. ;-)

The solution is, of course:

class A { public:

void foo1() { scoped_lock<> lock(mut_); foo1_impl(); }

void foo2() { scoped_lock<> lock(mut_); foo2_impl(); }

void foo3() { scoped_lock<> lock(mut_); foo3_impl(); }

private:

void foo1_impl(); // calls foo2_impl & foo3_impl void foo2_impl(); void foo3_impl();

mutex mut_; };

Yes, that is the classic solution but it never strikes me as quite what I need. I've been struggling to find a cute solution I'm happy with. Mainly because I also typically want to expose the foo1_impl() for the cases when I wish to lock externally for multiple operations. One thing I've done is have the standard interface lock and have template methods that take true and false for locking and non-locking. do_this(); // locks - safety first do_this<true>(); // locks do_this<false>(); // no locking To do this I inherit a monitor class which exposes a guard() method that return a mutex reference which is used for locking. The messy part is being able to do it without lots of boilerplate code. Presently I use a macro for getter/setter attributes which implements the appropriate methods and also uses a compile time check for attribute size to determine if locking is truly necessary for the platform (some operations are atomic and need no locking, e.g. 32 bit ops on IA32 and 64 bit ops on IA64). This is fine. However this macro/specialisation approach falls apart when you have an arbitrary method as I don't know a neat way to encapsulate the passing of the parameters in the macro for replication. However, the named_params library does this nicely and I think I could use that for the arbitary method approach, I just can't quite find the time to do it. I've previously posted this stuff but can again if there is any interest. Regards, Matt Hurd. _______________ Here is a simple attribute only example: namespace te { template < class S = synch::shareable

class instrument : public synch::monitor<S> { SYNCH_SIMPLE_ATTRIBUTE( susquehanna_code, std::string ); SYNCH_SIMPLE_ATTRIBUTE( exchange_code, std::string ); SYNCH_SIMPLE_ATTRIBUTE( underlying, std::string ); SYNCH_SIMPLE_ATTRIBUTE( bid, double ); SYNCH_SIMPLE_ATTRIBUTE( bid_volume, double ); SYNCH_SIMPLE_ATTRIBUTE( ask, double ); SYNCH_SIMPLE_ATTRIBUTE( ask_volume, double ); SYNCH_SIMPLE_ATTRIBUTE( last, double ); SYNCH_SIMPLE_ATTRIBUTE( last_volume, double ); SYNCH_SIMPLE_ATTRIBUTE( prior_settlement, double ); public: instrument() : synch::monitor<S>() { } template < class T > instrument( const T & t) : synch::monitor<S>() { T::lock lk( t.guard(), synch::lock_status::shared ); susquehanna_code<false> ( t.susquehanna_code<false>() ); exchange_code<false> ( t.exchange_code<false>() ); underlying<false> ( t.underlying<false>() ); bid<false> ( t.bid<false>() ); bid_volume<false> ( t.bid_volume<false>() ); ask<false> ( t.ask<false>() ); ask_volume<false> ( t.ask_volume<false>() ); last<false> ( t.last<false>() ); last_volume<false> ( t.last_volume<false>() ); prior_settlement<false> ( t.prior_settlement<false>() ); } template< class T > instrument< S > & operator=( const T& rhs ) { if (&rhs != this) { lock lk_this( guard(), synch::lock_status::exclusive ); instrument<S> temp(rhs); swap(temp); } return *this; } template< class T> void swap( T& source) throw() { std::swap( susquehanna_code_, source.susquehanna_code_); std::swap( exchange_code_, source.exchange_code_); std::swap( underlying_, source.underlying_); std::swap( bid_, source.bid_); std::swap( bid_volume_, source.bid_volume_); std::swap( ask_, source.ask_); std::swap( ask_volume_, source.ask_volume_); std::swap( last_, source.last_); std::swap( last_volume_, source.last_volume_); std::swap( prior_settlement_, source.prior_settlement_); } }; } // namespace

On Thu, 15 Jul 2004 16:03:36 +0300, Peter Dimov <pdimov@mmltd.net> wrote:

Matt Hurd wrote:

...

Yes, that is the classic solution but it never strikes me as quite what I need.

I've been struggling to find a cute solution I'm happy with. Mainly because I also typically want to expose the foo1_impl() for the cases when I wish to lock externally for multiple operations.

Andrei Alexandrescu's suggestion is to make foo1_impl take a lock:

void foo1() { scoped_lock<> lock(mx_); foo1( lock ); }

void foo1( scoped_lock<> & l ) { assert( l.locked() ); assert( l.mutex() == &mx_ ); // or not, to allow ext. sync

// do things, incl. foo2( l ); }

This doesn't solve the boilerplate problem, though. Maybe something like

void foo1( scoped_lock<> * pl = 0 ) { assert( pl == 0 || pl->locked() ); scoped_lock<> internal_lock( mx_, pl == 0 ); if( pl == 0 ) pl = &internal_lock;

// do things, incl. foo2( pl ); }

where the boilerplate can be hidden in a class.

Been thinking a little about it. I see some pros and cons to this approach. Pro: discrimination at run-time to enable different states to support different locking strategies. Pro: doesn't mess up methods that require bool template parameterisation Con: run-time overhead (or needing better compilers for global optimization than we currently have) Con: defaults on parameters messes up the interface if you want to have other parameters that are optional too. Con: requires a lock abstraction when you might be able to get away without one for your use case in the state your are dealing with. That is, don't need a lock, don't require one. The case for not requiring a lock should have zero cost at runtime. Stroustrup's don't pay for what you don't use principle. The caveat is that with modern compile time programming this should probably translate to something like, "with most modern compilers' optimization capabilities... don't pay...". Maybe a hybrid / dual approach is better. I am still trying to see this in a holistic sense were blocking/polling and non-threaded/threaded can be parameterized as well as allowing dual use of the objects. Would be nice to consider this interface w.r.t. other resource acquisition, such as file and socket i/o as the blocking, try, timed argument is still relevant to these resources as well. Along these lines perhaps locking can be considered one of many potential run-time preconditions or predicates that you may want to pay for a single evaluation/use sometimes to minimize the cost of state transitions. Locking is just one very common example. On the flip side, perhaps we should forget about it or give up ;-) , just layer a simple api on top of the common posix, win32, dce abstractions, like ace does and worry about C++ niceness later. I'd rather get it nice though as there are other libraries that do this already. Regards, Matt Hurd.

On Jul 12, 2004, at 1:35 PM, Peter Dimov wrote:

...

On the other hand, our Windows implementation of condition::wait follows the algorithm laid out by Alexander Terekhov's "Algorithm 8a" posted in comp.programming.threads on April 27, 2001 (and noted as such in that file Alexander). In this case the wait() function does not differ depending upon the recursiveness of the mutex.

To clarify: does your implementation support waiting on a recursive mutex that has been locked more than once, temporarily decreasing its lock count to zero to allow other threads to acquire the mutex while the original thread is blocked by the wait?

That was the intent. But I stand corrected. I evidently got it wrong except on Mac OS X where I do explicitly decrement the count to 0 of the pthread_mutex during a wait (recursive mutex case only). Looks like I need to dig back into this on other platforms... -Howard

On Jul 12, 2004, at 4:51 PM, Peter Dimov wrote:

...

That was the intent. But I stand corrected. I evidently got it wrong except on Mac OS X where I do explicitly decrement the count to 0 of the pthread_mutex during a wait (recursive mutex case only). Looks like I need to dig back into this on other platforms...

Doesn't this impose some overhead on your recursive_mutex, even if the user never takes advantage of this feature? (I have to admit that I don't have the slightest idea how is this possible to implement correctly.)

I'm not familiar with how a native pthread_mutex is made recursive. But with a native non-recursive mutex, the added space overhead simply to handle recursive locking was also sufficient to negotiate use with condition variables without further space overhead needed just for the condition variables. To support the condition variables, a little more code is needed (maybe a dozen lines of C++) executed from within the wait function, and maybe a dozen or so bytes of stack space within the condition's wait function. Essentially the wait function saves the state of the mutex before the wait, then frees it for the wait, then restores the state of the mutex after the wait. With a non-recursive mutex you do the same thing, except that the state of the mutex is so much simpler: it is locked before and after the wait, and unlocked during. So there is no need to store mutex "state" on the stack for a non-recursive mutex. -Howard

Peter Dimov wrote: [...]

That's how Boost.Threads behaves, but (AFAICS) it doesn't protect itself against a thread switch and lock immediately after freeing the mutex for the wait, so it doesn't meet the "correctly" requirement. ;-)

I think it saves the lock count on the stack prior to releasing internal "real" [non-recursive, in a way, because it's never used recursively] mutex and restores the count on exit from cv.wait after acquiring the "real" mutex. In a way, the scheme is really similar to: http://groups.google.com/groups?selm=3BA5B950.6E21D198%40web.de http://groups.google.com/groups?selm=408E48E8.D67F1EA5%40web.de --- Per-thread flags can be used to turn nonrecursive locks into recursive ones. given: key - tsd flag key lock - mutex (non-recursive lock) count - unsigned init { tsd::init(&key); lock::init(&lock); count = 0; } destroy { lock::destroy(&lock); tsd::destroy(&key); } lock { if (!tsd::get(&key)) { tsd::set(&key, true); lock.acquire(); // assume throw()-nothing count = 1; } else { ++count; } } unlock { if (!--count ) { lock.release(); // throw()-nothing tsd::set(&key, false); } } Note that if you need "posix safety" with respect to unlock/destroy of this lock, "tsd::set(&key, false);" shall be done before "lock.release();" (and of course the underlying nonrecursive lock itself shall be safe with respect to unlock/destroy). --- where you just need to save-on-stack-and-reset/restore the lock count before-cv.enter_wait()/after-cv.exit_wait(). The problem I meant before was something else (don't recall now). regards, alexander.

Howard Hinnant wrote: [...]

If the OS provides a mutex that is recursive without documenting that fact, then that sounds like a docs bug to me. If I need a recursive mutex, I will gladly use an OS-supplied one if I can find such a beast. Otherwise I have to build it myself out of an OS-supplied non-recursive mutex. If I find that I've ended up paying for recursion overhead twice, or unnecessarily re-implemented recursive mutexes for that platform, I'll send a bug report to the OS vendor.

However in this case a recursive mutex has been provided by the OS, you just decided to not use it (in order to implement the recursive condition::wait). It seems that you have accepted the responsibility for the tradeoff. For some reason, it also seems that it's time for me to shut up.

Peter Dimov wrote: [...]

The mutex::timed_lock situation is a bit more complicated. POSIX labels pthread_mutex_timedlock as part of the Timeouts option, and I don't know whether this is because many implementations deliberatley do not provide timed locks, or because this is a relatively new addition to pthreads. Does someone know?

< Forward Quoted > David Butenhof wrote:

Alexander Terekhov wrote:

...

Pls read the message attached below. Perhaps you can answer the POSIX related (and also "thinking severals years ahead") question (to the newsgroup/list or to me -- I'll forward it then). I mean

...

The mutex::timed_lock situation is a bit more complicated. POSIX labels pthread_mutex_timedlock as part of the Timeouts option, and I don't know whether this is because many implementations deliberatley do not provide timed locks, or because this is a relatively new addition to pthreads.

Mutex timeout was devised for the "More realtime extensions" amendment, 1003.1d-1999. It's an option that is not required by the base standard or any profile (e.g., SUS), and that obviously was not in UNIX 98. I expect it is not widely implemented, nor to be a very high priority. (It's not in Tru64 or HP-UX, for example.)

In general, timed mutex operations are of relatively little use to general purpose applications in the first place. It's usually pretty hard to recover any shared data that may be corrupted because of unknown "bad behavior" on the part of the thread that failed to release the mutex. Because it's locked, you can't even unlock it, or reinitialize it; so you need to be able to dynamically switch to another mutex to continue operation. (As well as worrying about what the nonresponsive thread might be doing to your data.) As a result, there's usually not much you can do other than dump core in many cases. There are, of course, exceptions; but that's part of why the implementation priority has been relatively low on most systems.

This really was a feature desired by and intended for the truly "hard realtime" embedded system people, specifically for flight control systems and such that have no choice but to do "whatever is necessary".

(By the way, I've had this reply sitting in a buffer for days now, and just rediscovered it, entirely by coincidence, under a bunch of other windows. I've been having a lot of meetings and "stuff" lately, and this isn't the first time I've completely lost track of some message. Sorry. ;-) )

regards, alexander.

Michael Glassford <glassfordm@hotmail.com> writes:

Would Boost.Move (in the Sandbox, I guess) help with this?

Yes and yes. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Peter Dimov wrote:

Michael Glassford wrote:

...

I agree that movable locks should wait. However, what about something like this, which doesn't require movable locks (concept only--there are probably errors):

[...]

Looks like Comeau in strict mode would still not accept it; noncopyable objects cannot be copy-initialized. But let's get back to my original question:

...

...

...

...

...

This is certainly possible, but I don't see what the additional complexity buys us.

Well, in regards to simply choosing the right set of constructors, we appear to disagree on what's beneficial, so I guess I can't answer that. In regards to the alternative design Eric presented, or my responses to it, it would buy this syntax: if (try_lock l = ...) { } Not major, perhaps, but nice. Mike

On Jul 8, 2004, at 11:10 AM, David Abrahams wrote:

Are there really any repercussions from making a noncopyable type into a moveable type, other than that you might want to find ways to take advantage of the new moveability?

If I had an rvalue reference available today, I would design the interface of the read and write locks differently. For example, instead of: void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { rw_mutex::write_lock w(r); //... w.transfer_to(r); } //Point A } I would propose: void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { rw_mutex::write_lock w(move(r)); //... r = move(w); } //Point A } The original code would not compile: write_lock would not accept an lvalue upgradable_read_lock and transfer_to would not exist. This would allow, among other things, locks to be returned from functions (as long as they were auto-local within the function). It would also allow for containers of locks. So the major repercussion that I see is that we're designing an inferior interface today that is not forward compatible with what I would propose if move semantics were available. We could possibly fake the desired move syntax today, but the thought makes me tired. :-( Especially in the light that the proposed move syntax is by no means a sure deal. -Howard

Howard Hinnant <hinnant@twcny.rr.com> writes:

On Jul 8, 2004, at 11:10 AM, David Abrahams wrote:

...

Are there really any repercussions from making a noncopyable type into a moveable type, other than that you might want to find ways to take advantage of the new moveability?

If I had an rvalue reference available today, I would design the interface of the read and write locks differently. For example, instead of:

void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { rw_mutex::write_lock w(r); //... w.transfer_to(r); } //Point A }

I would propose:

void f(rw_mutex& m) { rw_mutex::upgradable_read_lock r(m); if (...) { rw_mutex::write_lock w(move(r)); //... r = move(w); } //Point A }

The original code would not compile: write_lock would not accept an lvalue upgradable_read_lock and transfer_to would not exist.

I believe you can have the latter syntax with or without moveability. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

Michael Glassford wrote:

Peter Dimov wrote:

[...]

...

This is certainly possible, but I don't see what the additional complexity buys us.

TryLock l( m, false );

if( l.try_lock() ) { }

looks acceptable to me.

TryLock l( m, non_blocking );

if( l.locked() ) { }

doesn't seem much of an improvement.

The two aren't equivalent (I'm not sure if you meant them to be): in your first example the constructor doesn't attempt to lock, and your second example it attempts a non-blocking lock.

I'm not sure where you think the two examples differ. Both attempt a non-blocking lock.

2) What it buys over your suggestion (at the cost of complexity):

* The ability to specify all applicable lock types (blocking, non-blocking, timed-blocking) in a constructor.

Why is that an improvement?

3) I'm proposing the use of enums rather than bools to indicate the initial state of the lock for these reasons: [...]

OK, let's leave the enum vs bool distinction aside for a while. The crucial difference is explicit try_lock() vs implicit try_lock (a constructor with the appropriate combination of arguments).

4) Which leads to a problem with both your proposal and mine: they both silently break existing code (by changing try_lock(M) from non-blocking to blocking); at least, I presume you meant that. Would eliminating the lock_type(M) constructor (perhaps only for a release or two) be a good idea, or is a prominent warning in the documentation enough?

My proposal (I'm not sure whether I should be credited for it; Howard posted locks that had these properties and I merely commented) can be made to break such code at compile time, simply by removing the nested TryMutex::scoped_try_lock typedef (as there is no longer a need for it, because ::scoped_lock is a TryLock or TimedLock, as appropriate).

Howard Hinnant wrote:

On Jul 7, 2004, at 1:45 PM, Peter Dimov wrote:

...

My proposal (I'm not sure whether I should be credited for it; Howard posted locks that had these properties and I merely commented) can be made to break such code at compile time, simply by removing the nested TryMutex::scoped_try_lock typedef (as there is no longer a need for it, because ::scoped_lock is a TryLock or TimedLock, as appropriate).

Interesting... I hadn't thought about doing that. But I think I see where you're headed. A lock is just a lock, those parts of it you need, you instantiate and use. Those parts you don't, you ignore and they don't hurt anything (unless you try to explicitly instantiate your lock). If you try to use something the templated mutex doesn't support, you get a compile time error. Giving that some more thought...

Yes, it's even possible to collapse all locks into one templated class. My point was weaker than that. I wanted to collapse all three locks exposed by a TimedMutex into one, since with the linear concept hierarchy, there is no longer any reason to expose separate locks. A single TimedLock - called TimedMutex::scoped_lock - will suffice. Generic code that only needs a Mutex or TryMutex can still operate on a TimedMutex.

Michael Glassford wrote:

Peter Dimov wrote:

[...]

...

...

...

This is certainly possible, but I don't see what the additional complexity buys us.

TryLock l( m, false );

if( l.try_lock() ) { }

looks acceptable to me.

TryLock l( m, non_blocking );

if( l.locked() ) { }

doesn't seem much of an improvement.

The two aren't equivalent (I'm not sure if you meant them to be): in your first example the constructor doesn't attempt to lock, and your second example it attempts a non-blocking lock.

I'm not sure where you think the two examples differ. Both attempt a non-blocking lock.

It doesn't really matter, but if you're talking about the way Boost.Threads works currently (in the 1.31.0 release), according to both the code and the documentation, TryLock(m, false) makes no attempt to lock. If you're talking about a new design, then of course it means whatever you want :)

I still don't see your point. Of course the constructor does not lock, but the try_lock() call in the if statement does.

That's one reason I prefer the enum: it's clear what the parameter actually means.

In this particular context, I don't think that the bool argument can be misinterpreted, and neither can the explicit 'l.try_lock()' call.

...

...

2) What it buys over your suggestion (at the cost of complexity):

* The ability to specify all applicable lock types (blocking, non-blocking, timed-blocking) in a constructor.

Why is that an improvement?

It seems reasonable that, if you're going to allow constructors to lock, you should allow them to lock in whatever ways are possible.

No, general principles say that it is usually unreasonable for a constructor to leave the object in a Heisenberg state. ;-) As a general rule, constructors establish invariants and therefore have postconditions (and throw if they fail to meet those postconditions). Operations that are expected to 'fail' are better expressed as (member) functions that return whether the operation succeeded.

The constructor locking is kind of nice for this syntax, though:

if (try_lock l(...)) //or timed_lock { //do something }

It is. Unfortunately the syntax is illegal. ;-)

I don't have strong feelings on the bool vs enum debate. But I do have some comments below... On Jul 7, 2004, at 10:31 AM, Michael Glassford wrote:

Definitions ----------- M: appropriate mutex type

namespace lock_state { typedef enum { unlocked=0, locked=1 } lock_state; } //namespace lock_state

ok.

namespace read_write_lock_state { typedef enum { unlocked=0, read_locked=1, write_locked=2 } read_write_lock_state; } //namespace read_write_lock_state

I'm not clear how these would be used. A read_lock is either locked or not, same with write_lock. I'm not seeing a need, nor a desire for a lock that can both read lock and write lock.

namespace blocking_mode { typedef enum { non_blocking=0, blocking=1 } blocking_mode; } //namespace blocking_mode

ok.

ScopedLock / ScopedReadLock / ScopedWriteLock --------------------------------------------- lock(M) //always locking, blocking lock(M, lock_state) //blocking

ok.

ScopedTryLock / ScopedTryReadLock / ScopedTryWriteLock ------------------------------------------------------ try_lock(M) //always locking, BLOCKING try_lock(M, lock_state) //BLOCKING

ok.

try_lock(M, lock_state, blocking_mode) try_lock(M, blocking_mode) //always locking

try_lock tl(M, unlocked, blocking); What does this mean? The same as: try_lock tl(M, unlocked); ? Similarly is not try_lock(M, locked, blocking_mode) the same as try_lock(M, blocking_mode)? If I'm interpreting this correctly, how about the following reduced list to eliminate redundancy: try_lock(M) //always locking, BLOCKING try_lock(M, lock_state) //BLOCKING (if attempting to lock) try_lock(M, blocking_mode) //always (attempt) locking Btw, this would require enums over bool.

ScopedTimedLock / ScopedTimedReadLock / ScopedTimedWriteLock ------------------------------------------------------------ timed_lock(M) //always locking, blocking timed_lock(M, lock_state) //blocking

timed_lock(M, lock_state, blocking_mode) timed_lock(M, blocking_mode) //always locking

timed_lock(M, t) //always locking, blocking for time t

Note that the addition of the try_lock stuff to ScopedTimedLock is a change. I don't disagree with that change. Just hilighting it. It is essentially alternative syntax for a timed_lock specified with a 0 delta time. Speaking of which, I've never been happy with "t" in the ScopedTimedLock docs. I've always felt it was ambiguous. Does t represent an absolute time, or a change in time? Both interpretations are useful. In the Metrowerks::threads lib I have: scoped_timed_lock(mutex_type& m, const universal_time& unv_time); scoped_timed_lock(mutex_type& m, const elapsed_time& elps_time); Where universal_time and elapsed_time are simplistic structs (like the boost time), but represent absolute and delta times respectively. They can also be added and subtracted as makes sense (e.g. you can add a universal_time and an elapsed_time, or two elapsed_time's, but you can't add two universal_time's). I took the Posix route and defined universal_time as the number of seconds and nanoseconds since midnight Jan. 1, 1970, UTC. The universal_time default constructor returns the current time. So how about: timed_lock(M) //always locking, blocking timed_lock(M, lock_state) //blocking timed_lock(M, blocking_mode) //always locking timed_lock(M, universal_time u) //always locking, blocking until u timed_lock(M, elapsed_time t) //always locking, blocking for elapsed time t ? -Howard

Howard Hinnant wrote:

Speaking of which, I've never been happy with "t" in the ScopedTimedLock docs. I've always felt it was ambiguous. Does t represent an absolute time, or a change in time? Both interpretations are useful.

It represents an absolute time. The main rationale for using absolute times is condition::timed_wait, which needs to be called in a loop. A relative time would need to be recalculated for each iteration. But relative times are useful, too.

In the Metrowerks::threads lib I have:

scoped_timed_lock(mutex_type& m, const universal_time& unv_time); scoped_timed_lock(mutex_type& m, const elapsed_time& elps_time);

Where universal_time and elapsed_time are simplistic structs (like the boost time), but represent absolute and delta times respectively. They can also be added and subtracted as makes sense (e.g. you can add a universal_time and an elapsed_time, or two elapsed_time's, but you can't add two universal_time's). I took the Posix route and defined universal_time as the number of seconds and nanoseconds since midnight Jan. 1, 1970, UTC. The universal_time default constructor returns the current time.

One problem with the UTC time is that it can jump backwards, if the system time changes. Maybe we should consider using (or adding) a monotonic time.