May 31, 2012
On 2012-05-31 10:01, Andrei Alexandrescu wrote:

> I understand how frustrating this is. In fact even the way you consider
> "good" is not nearly good enough. What we need is really more
> formalization of the language design, something that we're sorely
> missing. I am sometimes frustrated out of my mind at the lack of rigor
> and discipline in the process. On the other hand, we march with the
> troops we have.

Yeah, "good" should have been "better". I'm not sure what you mean with "we march with the troops we have" but it would be fairly easy to at least improve the process somewhat. It would require any extra manpower. It's just that you, Walter and the community needs to be willing to do the changes.

-- 
/Jacob Carlborg
May 31, 2012
Le 31/05/2012 13:13, Andrei Alexandrescu a écrit :
> On 5/31/12 3:27 AM, Regan Heath wrote:
>> I think
>> the mutex is "available for locking and unlocking" <- need a word for
>> that, which is not "exposed". How about accessible, available, usable,
>> or just plain lockable .. So, the problem here is that the mutex is
>> lockable by external code via synchronized() and this means a certain
>> type of deadlock is possible.
>
> But this is a protection/visibility issue, which is orthogonal on the
> locking capability. It's as if you say "int is not good because anyone
> can overflow it." Okay! Make it private inside a CheckedInt class.
>
>> Moving on..
>>
>> I think the change mentioned in TDPL to restrict synchronized to
>> synchronized classes is a step in the right direction WRT wasted monitor
>> space and people freely locking anything. But, it is exactly the case
>> which results in more possible deadlocks (the cause of this thread) AND
>> I think it's actually far more likely people will want to use a
>> synchronized statement on a class which is not itself synchronized, like
>> for example an existing container class.
>>
>> Given that, restricting synchronized statements to synchronized classes
>> seems entirely wrong to me.
>
> So where's the mutex that would be used to synchronize objects that are
> not synchronizable?
>
>> In fact, I would say you almost want to stop
>> people using synchronized statements on synchronized classes because:
>> 1. If a synchronized class is written correctly it should not be
>> necessary in the general case(*)
>> 2. It raises the chances of deadlocks (the cause of this thread).
>> 3. It means that classes in general will be simpler to write (no need to
>> worry about synchronization) and also more lightweight for use in
>> non-threaded/non-shared cases. (because we'd provide a template wrapper
>> to make them synchronizable)
>
> There are cases in which you want to do multiple operations under a
> single critical section, even though the API is otherwise well-designed.
> That may be for correctness, efficiency, or both. I don't see why we'd
> want to disallow that, it's a good idiom.
>

Because it is now unclear who is controlling the lock.

The solution consisting in passing a delegate as parameter or as template is superior, because it is now clear who is in charge of the synchronization, reducing greatly chances of deadlock.
May 31, 2012
On Thu, 31 May 2012 12:13:00 +0100, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> On 5/31/12 3:27 AM, Regan Heath wrote:
>> I think
>> the mutex is "available for locking and unlocking" <- need a word for
>> that, which is not "exposed". How about accessible, available, usable,
>> or just plain lockable .. So, the problem here is that the mutex is
>> lockable by external code via synchronized() and this means a certain
>> type of deadlock is possible.
>
> But this is a protection/visibility issue, which is orthogonal on the locking capability. It's as if you say "int is not good because anyone can overflow it." Okay! Make it private inside a CheckedInt class.

Sorry, that's a bad comparison.  CheckedInt is to int, what CheckedMutex is to mutex - but I'm not suggesting anything like a CheckedMutex.  I'm suggesting "mutex" but kept private inside the class /that it locks/.  Yes, it's a visibility issue, the issue is that the mutex used by synchronized classes/methods is too visible/accessible and this opens it up for deadlocks which are otherwise impossible.

>> I think the change mentioned in TDPL to restrict synchronized to
>> synchronized classes is a step in the right direction WRT wasted monitor
>> space and people freely locking anything. But, it is exactly the case
>> which results in more possible deadlocks (the cause of this thread) AND
>> I think it's actually far more likely people will want to use a
>> synchronized statement on a class which is not itself synchronized, like
>> for example an existing container class.
>>
>> Given that, restricting synchronized statements to synchronized classes
>> seems entirely wrong to me.
>
> So where's the mutex that would be used to synchronize objects that are not synchronizable?

In the wrapper class/struct/object which derives a synchronized class/struct from the original.  My D foo is not strong enough to just come up with valid D code for the idiom on the fly, but essentially you wrap the original object in a new object using a template which adds the mutex member and the interface methods (lock, tryLock, and unlock) required.  No, this doesn't work with "final" classes.. but it shouldn't, they're final after all.  For them you need to add/manage the mutex manually - the price you pay for "final".

>> In fact, I would say you almost want to stop
>> people using synchronized statements on synchronized classes because:
>> 1. If a synchronized class is written correctly it should not be
>> necessary in the general case(*)
>> 2. It raises the chances of deadlocks (the cause of this thread).
>> 3. It means that classes in general will be simpler to write (no need to
>> worry about synchronization) and also more lightweight for use in
>> non-threaded/non-shared cases. (because we'd provide a template wrapper
>> to make them synchronizable)
>
> There are cases in which you want to do multiple operations under a single critical section, even though the API is otherwise well-designed. That may be for correctness, efficiency, or both. I don't see why we'd want to disallow that, it's a good idiom.

Who suggested disallowing this?  No-one.  There are 3 main use cases I see for this;

1. Several disparate objects locked by a single mutex - in which case the correct solution is a separate mutex/monitor object.
2. A single object, locked for serveral method calls - in which case the method-passed-a-delegate idea (mentioned below/ described in a separate thread) works, unless..
3. The calls span several scopes, in which case good-old manual lock/unlock is required (synchronized blocks don't help here)

>> So, more and more I'm thinking it would be better to provide a
>> library/runtime co-operative solution where we have an interface which
>> is required for synchronized statements, and a wrapper template to
>> implement that interface for any existing non-synchronized class.
>> Meaning, the choice is either to write a synchronized class (rare) or a
>> non-synchronized class - knowing it can easily be synchronized if/when
>> needed.
>
> Looking forward for a fleshed out proposal. Make sure you motivate it properly.

Sorry, I have no spare time to spare.  You're getting free ideas/thoughts from me, feel free to ignore them.

>> The "liquid lock" problem mentioned earlier is an interesting one that I
>> have not personally experienced, perhaps because I don't lock anything
>> but mutex primitives and I never to re-assign these.
>>
>> (*) Locking on a larger scope can be achieved by providing a method
>> taking a delegate (see earlier thread/replies) and/or exposing
>> lock/unlock for those few situations where the delegate method cannot be
>> used. These are the few cases in which this cannot be avoided as the
>> lock/unlock are separated by more than a single scope (so synchronized
>> statements don't help in these cases either).
>
> On first look, the inversion of control using delegates delegates has similar liabilities as straight scoped locking.

True, it's basically the same as a synchronized block in that respect.  What we actually want is a way to limit the calls made by the delegate to methods of the object itself.  If it could not call a synchronized method on a 2nd object, you could not possibly deadlock.  Except, that is to say, unless you held a separate lock beforehand - but, the important point here is that you would have to take both locks explicitly, rather than by an implicit synchronized method call, making the bug far more obvious to code inspection.

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
May 31, 2012
Le 31/05/2012 16:01, Regan Heath a écrit :
> True, it's basically the same as a synchronized block in that respect.
> What we actually want is a way to limit the calls made by the delegate
> to methods of the object itself. If it could not call a synchronized
> method on a 2nd object, you could not possibly deadlock. Except, that is
> to say, unless you held a separate lock beforehand - but, the important
> point here is that you would have to take both locks explicitly, rather
> than by an implicit synchronized method call, making the bug far more
> obvious to code inspection.
>
> R
>

I'm not sure I follow you here. Can you elaborate on that ?
May 31, 2012
On Thu, 31 May 2012 15:06:14 +0100, deadalnix <deadalnix@gmail.com> wrote:

> Le 31/05/2012 16:01, Regan Heath a écrit :
>> True, it's basically the same as a synchronized block in that respect.
>> What we actually want is a way to limit the calls made by the delegate
>> to methods of the object itself. If it could not call a synchronized
>> method on a 2nd object, you could not possibly deadlock. Except, that is
>> to say, unless you held a separate lock beforehand - but, the important
>> point here is that you would have to take both locks explicitly, rather
>> than by an implicit synchronized method call, making the bug far more
>> obvious to code inspection.
>>
>> R
>>
>
> I'm not sure I follow you here. Can you elaborate on that ?

Apologies in advance, my D code skillz have rusted significantly..

class A
{
  synchronized void foo()
  {
  }
}

class B {}

void main()
{
  A a = new A();
  B b = new B();

  synchronized(b)  // locks B
  {
    a.foo();       // locks A
  }
}

.. this deadlocks if another thread locks A then B anywhere.  The "problem" is that this can be hard to spot and easy to do accidentally as a.foo() does not scream "I'm going to lock something".

This is the same problem with the synchronized method calling a supplied delegate..

class A
{
  synchronized void foo()
  {
  }
}

class B
{
  synchronized void syncDelegate(void delegate(void) dg) { .. }
}

void main()
{
  A a = new A();
  B b = new B();

  b.syncDelegate(.. code which calls a.foo() .. );  // locks B (syncDelegate), then locks A (a.foo)
}

The only way to avoid the deadlock is to prevent calls to synchronized methods inside the delegate.

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
May 31, 2012
>>
>> But this is a protection/visibility issue, which is orthogonal on the
>> locking capability. It's as if you say "int is not good because anyone
>> can overflow it." Okay! Make it private inside a CheckedInt class.
>
> Sorry, that's a bad comparison. CheckedInt is to int, what CheckedMutex
> is to mutex - but I'm not suggesting anything like a CheckedMutex. I'm
> suggesting "mutex" but kept private inside the class /that it locks/.
> Yes, it's a visibility issue, the issue is that the mutex used by
> synchronized classes/methods is too visible/accessible and this opens it
> up for deadlocks which are otherwise impossible.
>

Sure it's awful comparison.


>>
>> So where's the mutex that would be used to synchronize objects that
>> are not synchronizable?
>
> In the wrapper class/struct/object which derives a synchronized
> class/struct from the original. My D foo is not strong enough to just
> come up with valid D code for the idiom on the fly, but essentially you
> wrap the original object in a new object using a template which adds the
> mutex member and the interface methods (lock, tryLock, and unlock)
> required. No, this doesn't work with "final" classes.. but it shouldn't,
> they're final after all. For them you need to add/manage the mutex
> manually - the price you pay for "final".
>

OK let me land you a hand here. My proposal, that I think fits your ideas quite favorably.

I'll enumerate certain assumptions beforehand since it's one of most confusing threads I ever followed.

1. synchronized class means: always allocate hidden monitor mutex, lock it on every public method of this class.

2. synchronized(x,y,z) is lowered to (I use Steven's idea):
	auto sorted = total_order(x,y,z);//conceptual, sorted is tuple of x,y,z sorted
	FOR EACH item IN sorted tuple add code in [[ ... ]]
	[[// conceptual
		item.__lock();
		scope(exit) item.__unlock();
	]]
In other words it works for every object that defines lock/unlock. Multiple object version works only if there is opCmp defined. (by address whatever, any total ordering should work)


Per definition above synchronized classes AS IS can't be *synchronized* on. Instead their public methods are implicitly synchronized.

The end result is:

User can synchronize on various synchronization entities and even plug in custom synchronization primitives (say OS Y provides have this fancy lock type Z). It's explicit in as sense that object supports it via __lock__/unlock. Obviously one still can use __lock/__unlock explicitly just don't forget to wear big HERE BE DRAGONS banner.

Synchronized class encapsulate mutex completely - nobody aside from designer of the class may (a)use it.

Does it makes sense?

-- 
Dmitry Olshansky
May 31, 2012
On Thu, 31 May 2012 15:49:52 +0100, Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
> OK let me land you a hand here. My proposal, that I think fits your ideas quite favorably.
>
> I'll enumerate certain assumptions beforehand since it's one of most confusing threads I ever followed.
>
> 1. synchronized class means: always allocate hidden monitor mutex, lock it on every public method of this class.
>
> 2. synchronized(x,y,z) is lowered to (I use Steven's idea):
> 	auto sorted = total_order(x,y,z);//conceptual, sorted is tuple of x,y,z sorted
> 	FOR EACH item IN sorted tuple add code in [[ ... ]]
> 	[[// conceptual
> 		item.__lock();
> 		scope(exit) item.__unlock();
> 	]]
> In other words it works for every object that defines lock/unlock. Multiple object version works only if there is opCmp defined. (by address whatever, any total ordering should work)
>
>
> Per definition above synchronized classes AS IS can't be *synchronized* on. Instead their public methods are implicitly synchronized.
>
> The end result is:
>
> User can synchronize on various synchronization entities and even plug in custom synchronization primitives (say OS Y provides have this fancy lock type Z). It's explicit in as sense that object supports it via __lock__/unlock. Obviously one still can use __lock/__unlock explicitly just don't forget to wear big HERE BE DRAGONS banner.
>
> Synchronized class encapsulate mutex completely - nobody aside from designer of the class may (a)use it.
>
> Does it makes sense?

Yes, and it's all more intentional/flexible than what we have now, but.. :)

Does it address what I thought was the main "problem" case.  That is, as soon as you lock 2 objects, one via a synchronized() statement and the other via a synchronized method you can get a non-obvious deadlock. e.g.

synchronized class A
{
  void foo() {} // implicitly locks instance of A
}

class B
{
  void __lock() {}   // locks instance of B
  void __unlock() {} // unlocks instance of B
}

shared A a;
shared B b;

void main()
{
  a = new shared(A)();
  b = new shared(B)();
  ..start thread which locks a then b..
  synchronized(b)  // locks b 'explicitly'
  {
    a.foo();       // locks a 'implicitly'
  }
}

.. but, hang on, can a thread actually lock a and then b?  If 'a' cannot participate in a synchronized statement (which it can't under this proposal) then no, there is no way to lock 'a' except by calling a member.  So, provided 'a' does not have a member which locks 'b' - were deadlock safe!

So.. problem solved; by preventing external/public lock/unlock on a synchronized class.  (I think the proposal should enforce this restriction; synchronized classes cannot define __lock/__unlock).

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
May 31, 2012
On Thu, 31 May 2012 10:49:52 -0400, Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
> OK let me land you a hand here. My proposal, that I think fits your ideas quite favorably.

[snip]

> Does it makes sense?

Everything but the ordering.  I like the idea of ordering the locks based on an intrinsic value, but opCmp isn't it.  Objects can mutate, and opCmp may produce different results.  Imagine:

synchronized(a, b) // at this point a < b
{
   a.makeGreaterThan(b);
   assert(a > b);
}

You *never* want the ordering to change.

But I think we can probably work that out.  What about comparing handles of the mutexes?  So you sort based on some property __mutex_id() which must return a unique size_t that can be used to always define an ordering of locking mutexes?  Most mutexes are allocated by the OS, and so their handles won't be affected by a moving GC, so you likely will use the handle value.

-Steve
May 31, 2012
On 31.05.2012 19:11, Steven Schveighoffer wrote:
> On Thu, 31 May 2012 10:49:52 -0400, Dmitry Olshansky
> <dmitry.olsh@gmail.com> wrote:
>> OK let me land you a hand here. My proposal, that I think fits your
>> ideas quite favorably.
>
> [snip]
>
>> Does it makes sense?
>
> Everything but the ordering. I like the idea of ordering the locks based
> on an intrinsic value, but opCmp isn't it. Objects can mutate, and opCmp
> may produce different results. Imagine:
>
> synchronized(a, b) // at this point a < b
> {
> a.makeGreaterThan(b);
> assert(a > b);
> }
>

No way! I live in world where victim's hand is cut off as a punishment for mutating a lock after creation ;)

> You *never* want the ordering to change.
>
> But I think we can probably work that out. What about comparing handles
> of the mutexes? So you sort based on some property __mutex_id() which
> must return a unique size_t that can be used to always define an
> ordering of locking mutexes? Most mutexes are allocated by the OS, and
> so their handles won't be affected by a moving GC, so you likely will
> use the handle value.
>

This could work. In fact I imagined comparing handles ...
As with math at large you may either project (biject) your domain to a well-known one (like numbers, mutex_id in your case) and work with it or define all relevant properties for whatever your values in this domain are (providing custom ordering for user defined types).



-- 
Dmitry Olshansky
May 31, 2012
On May 31, 2012, at 2:48 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 5/31/12 2:36 AM, Regan Heath wrote:
>> On Wed, 30 May 2012 19:29:39 +0100, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>> You can have deadlocks but with synchronized you can't leak locks or doubly-unlock them. With free mutexes you have all of the above.
>> 
>> I'm not suggesting using free mutexes. I'm suggesting keeping the mutex private inside the object.
> 
> Ergo, you are suggesting using free mutexes. Your second sentence destroys the first.

To be fair:

auto m = new Mutex;
synchronized (m) {...}

Free mutexes but still safe. Scope guards obviously work too. That said, I think the point of contention here is that because synchronized can take an arbitrary object, it's possible to lock on a class for stuff completely unrelated to what the class does internally. It's certainly bad form though, and I don't know a good way to prevent it without crippling synchronized.