May 31, 2012
On Thu, 31 May 2012 11:39:06 -0400, Sean Kelly <sean@invisibleduck.org> wrote:

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

See my suggestion and Dmitry's in other parts of this thread.  The idea is that you still allow synchronized(x), but only if the author of x allows it.

If we use lowering, and make the lock and unlock methods of some entity, then you can also use attributes to limit scope of synchronized.

For example, if we make synchronized(x) equivalent to calling x.lock() and x.unlock() correctly, if lock() and unlock() are private, then you can only call synchronized(x) from inside the instance.

-Steve
May 31, 2012
On 31.05.2012 19:05, Regan Heath wrote:
> 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).
>

Surprisingly it is. And if A can't access B it's fool-proof.
As to __lock/__unlock defined for synchronized classes, yes I believe compiler should catch it.


-- 
Dmitry Olshansky
May 31, 2012
On Thu, 31 May 2012 16:23:29 +0100, Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:

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

This is related to the "liquid lock" problem raised/mentioned elsewhere in the thread.  If the reference you lock can change, then one thread/iteration may lock one instance, the lock instance mutates, and a 2nd thread/iteration locks the new instance and both execute more or less in parallel over code which was supposed to be serialized.  It's not a problem if the lock object is the object being mutated/used by the code, but it is a problem if the lock object is protecting other shared objects.  It's not something I have ever bumped into myself, because the bulk of my locking experience is in C/C++ and I use a locking primitive which is initialised once and never mutates.

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

This ordering idea is present in TDPL.. have you both read the link Andrei posted?
http://goo.gl/ZhPM2
(see 13.15)


R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/
May 31, 2012
On 31.05.2012 20:54, Regan Heath wrote:

>> No way! I live in world where victim's hand is cut off as a punishment
>> for mutating a lock after creation ;)
>
> This is related to the "liquid lock" problem raised/mentioned elsewhere
> in the thread. If the reference you lock can change, then one
> thread/iteration may lock one instance, the lock instance mutates, and a
> 2nd thread/iteration locks the new instance and both execute more or
> less in parallel over code which was supposed to be serialized. It's not
> a problem if the lock object is the object being mutated/used by the
> code, but it is a problem if the lock object is protecting other shared
> objects. It's not something I have ever bumped into myself, because the
> bulk of my locking experience is in C/C++ and I use a locking primitive
> which is initialised once and never mutates.
>

Yup, C/C++, locking only special OS provided stuff, it's my background exactly.

>>> 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).
>
> This ordering idea is present in TDPL.. have you both read the link
> Andrei posted?
> http://goo.gl/ZhPM2
> (see 13.15)
>
>

Yes, in fact I was going by TDPL. I just propose to extend it to entities other then class instances ( more specifically only those with __lock/__unlock ).

-- 
Dmitry Olshansky
May 31, 2012
On Thu, 31 May 2012 12:54:07 -0400, Regan Heath <regan@netmail.co.nz> wrote:

> On Thu, 31 May 2012 16:23:29 +0100, Dmitry Olshansky <dmitry.olsh@gmail.com> wrote:
>
>> 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 ;)
>
> This is related to the "liquid lock" problem raised/mentioned elsewhere in the thread.  If the reference you lock can change, then one thread/iteration may lock one instance, the lock instance mutates, and a 2nd thread/iteration locks the new instance and both execute more or less in parallel over code which was supposed to be serialized.  It's not a problem if the lock object is the object being mutated/used by the code, but it is a problem if the lock object is protecting other shared objects.  It's not something I have ever bumped into myself, because the bulk of my locking experience is in C/C++ and I use a locking primitive which is initialised once and never mutates.

Well, I thought the original proposal was to use the opCmp of the *data*, i.e. the object being protected.  At least that's what it seems like from the example.

Apologies if this was not the case.

>>> 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).
>
> This ordering idea is present in TDPL.. have you both read the link Andrei posted?
> http://goo.gl/ZhPM2
> (see 13.15)

No, I haven't read it yet.  I did review an early version of TDPL, but I have not re-read the released version (though I do have a copy).  Whether it was in there or not, it's been a while :)

-Steve
May 31, 2012
On Thursday, 31 May 2012 at 11:24:56 UTC, Steven Schveighoffer wrote:
> On Wed, 30 May 2012 17:45:32 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 5/30/12 1:31 PM, Steven Schveighoffer wrote:
>>> On Wed, 30 May 2012 15:48:47 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>> synchronized (object) {
>>>> writeln("about to unlock the object");
>>>> XXX
>>>> writeln("unlocked the object");
>>>> }
>>>>
>>>> Replace "XXX" with a construct that unlocks the object.
>>>
>>> This is not what we are talking about.
>>
>> Oh yes it is. "Expose the mutex" means "make the two mutex primitive operations lock() and unlock() freely usable against the mutex object".
>
> Stop that!  You are blatantly arguing minutia when you should be trying to understand what we are saying!  This is like dealing with a stubborn child.
[snip]
> -Steve

This reminds me one of my favorite Zen stories:

Nan-in, a Japanese master during the Meiji era (1868-1912), received a university professor who came to inquire about Zen.

Nan-in served tea. He poured his visitor's cup full, and then kept on pouring.

The professor watched the overflow until he no longer could restrain himself. "It is overfull. No more will go in!"

"Like this cup," Nan-in said, "you are full of your own opinions and speculations. How can I show you Zen unless you first empty your cup?"
May 31, 2012
On 5/31/12 5:19 AM, deadalnix wrote:
> 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.

It can also be a lot clunkier for certain abstractions. Say I want a ProducerConsumerQueue. It's much more convenient to simply make it a synchronized class with the classic primitives, instead of primitives that accept delegates etc.

Nevertheless I think there's merit in this idea. One thing to point out is that the idiom can easily be done today with a regular class holding a synchronized class private member.

So we got everything we need.


Andrei
May 31, 2012
On 5/31/12 7:01 AM, Regan Heath wrote:
> 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.

You're suggesting an idiom based on an unrestricted abstraction ("mutex") combined with a language feature ("private"). That's no progress because:

1. People can still misuse the unrestricted "mutex" as they have for the past 50 years.

2. The idiom can be done TODAY with a regular class that has a member of type synchronized class. Alternatively, you could use the mutex type in core directly.

So your suggestion actually makes the language worse and adds no power. Your impression being that "synchronized" is too deadlock-prone, and you believe the solution is taking one step BACK and eliminate it in favor of the "private"-based idiom in conjunction with the "mutex" type which is deadlock-prone PLUS prone to a variety of other issues.

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

Is there anything here that can't be done today, and pronto?

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

There's also "13.14.3 Forcing Identical Mutexes" in TDPL.

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

Here the synchronized-based idiom works well if the cost of reacquiring an already-owned mutex is sufficiently low.

> 3. The calls span several scopes, in which case good-old manual
> lock/unlock is required (synchronized blocks don't help here)

Right. In these rare cases core.sync.mutex would be recommendable.

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

Thanks. Let me know if I understand correctly that your idea boils down to "I don't like synchronized, let's deprecate it and get back to core.sync.mutex and recommend the private thingamaroo." In that case, I disagree. I believe synchronized has good merits that are being ignored.

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

Right. This is very D-unlike. I don't see anything in the current language that can limit the things a lambda/delegate can do.


Andrei

May 31, 2012
On 5/31/12 7:49 AM, Dmitry Olshansky wrote:
>>>
>>> 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.

It's a great comparison.

Andrei

May 31, 2012
On 5/31/12 7:49 AM, Dmitry Olshansky wrote:
> 1. synchronized class means: always allocate hidden monitor mutex, lock
> it on every public method of this class.

Great.

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

Great. What are regular calls to synchronized class methods lowered into?

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

It does make sense, but I think we need a Lock struct type that makes sure code cannot screw up the number of lock and unlock calls. We shouldn't just expose bare lock() and unlock().


Andrei