Make the double-checked lock idiom broken on x86

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Make the double-checked lock idiom broken on x86

Yubin Ruan
Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
broken. Bill Pugh gave an example:

    // Broken multithreaded version
    // "Double-Checked Locking" idiom
    class Foo {
      private Helper helper = null;
      public Helper getHelper() {
        if (helper == null)
          synchronized(this) {
            if (helper == null)
              helper = new Helper();
        }    
        return helper;
      }
      // other functions and members...
    }

His analysis is convincing, but the code he gave[2] work *well* on x86.
That is expected to break sometimes. But, running it from time to time,
I never see it break.

How to verify that the double-check lock idiom will break on x86?

---
Yubin

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Alex Otenko
I’d start with using the same version and brand of the JVM Bill used at the time of writing the article, which was probably written over 15 years ago.

Alex

> On 8 May 2017, at 15:22, Yubin Ruan <[hidden email]> wrote:
>
> Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
> broken. Bill Pugh gave an example:
>
>    // Broken multithreaded version
>    // "Double-Checked Locking" idiom
>    class Foo {
>      private Helper helper = null;
>      public Helper getHelper() {
>        if (helper == null)
>          synchronized(this) {
>            if (helper == null)
>              helper = new Helper();
>        }    
>        return helper;
>      }
>      // other functions and members...
>    }
>
> His analysis is convincing, but the code he gave[2] work *well* on x86.
> That is expected to break sometimes. But, running it from time to time,
> I never see it break.
>
> How to verify that the double-check lock idiom will break on x86?
>
> ---
> Yubin
>
> [1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
> [2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Mohan Radhakrishnan

On 8 May 2017 at 14:25, Alex Otenko <[hidden email]> wrote:
I’d start with using the same version and brand of the JVM Bill used at the time of writing the article, which was probably written over 15 years ago.

Alex

> On 8 May 2017, at 15:22, Yubin Ruan <[hidden email]> wrote:
>
> Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
> broken. Bill Pugh gave an example:
>
>    // Broken multithreaded version
>    // "Double-Checked Locking" idiom
>    class Foo {
>      private Helper helper = null;
>      public Helper getHelper() {
>        if (helper == null)
>          synchronized(this) {
>            if (helper == null)
>              helper = new Helper();
>        }
>        return helper;
>      }
>      // other functions and members...
>    }
>
> His analysis is convincing, but the code he gave[2] work *well* on x86.
> That is expected to break sometimes. But, running it from time to time,
> I never see it break.
>
> How to verify that the double-check lock idiom will break on x86?
>
> ---
> Yubin
>
> [1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
> [2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Millies, Sebastian
In reply to this post by Yubin Ruan
You may find the following article by Aleksey Shipilev extremely helpful in understanding DCL (and related idioms)
http://shipilev.net/blog/2014/safe-public-construction
It has been sometimes mentioned on the list.

-- Sebastian

-----Original Message-----
From: Concurrency-interest [mailto:[hidden email]] On Behalf Of Yubin Ruan
Sent: Monday, May 08, 2017 4:22 PM
To: [hidden email]
Subject: [concurrency-interest] Make the double-checked lock idiom broken on x86

Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is broken. Bill Pugh gave an example:

    // Broken multithreaded version
    // "Double-Checked Locking" idiom
    class Foo {
      private Helper helper = null;
      public Helper getHelper() {
        if (helper == null)
          synchronized(this) {
            if (helper == null)
              helper = new Helper();
        }
        return helper;
      }
      // other functions and members...
    }

His analysis is convincing, but the code he gave[2] work *well* on x86.
That is expected to break sometimes. But, running it from time to time, I never see it break.

How to verify that the double-check lock idiom will break on x86?

---
Yubin

[1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt, Dr. Stefan Sigg; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Yubin Ruan
In reply to this post by Alex Otenko
On Mon, May 08, 2017 at 09:55:53AM +0100, Alex Otenko wrote:
> I’d start with using the same version and brand of the JVM Bill used at the time of writing the article, which was probably written over 15 years ago.

Hmm...You mean what he said is not correct now? We don't need the `volatile'
keyword?

--
Yubin

>
> > On 8 May 2017, at 15:22, Yubin Ruan <[hidden email]> wrote:
> >
> > Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
> > broken. Bill Pugh gave an example:
> >
> >    // Broken multithreaded version
> >    // "Double-Checked Locking" idiom
> >    class Foo {
> >      private Helper helper = null;
> >      public Helper getHelper() {
> >        if (helper == null)
> >          synchronized(this) {
> >            if (helper == null)
> >              helper = new Helper();
> >        }    
> >        return helper;
> >      }
> >      // other functions and members...
> >    }
> >
> > His analysis is convincing, but the code he gave[2] work *well* on x86.
> > That is expected to break sometimes. But, running it from time to time,
> > I never see it break.
> >
> > How to verify that the double-check lock idiom will break on x86?
> >
> > ---
> > Yubin
> >
> > [1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
> > [2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
> > _______________________________________________
> > Concurrency-interest mailing list
> > [hidden email]
> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Alex Otenko
No, I mean that the VM + execution environment may no longer produce the same side-effects that would quickly fail the reproducer in the olden days - so the published reproducer would need modification to demonstrate the problem on the modern hardware and the VM.

For example, if the cost of synchronized is totally different, the threads no longer race in a way they used to. Suppose, the locks are biased now - one thread does the job, the rest of the threads are catching up, and after upgrade of the lock they all have to yield. When they wake up, the race effects are gone. So one thread does the job, and the others sleep.

Not saying that’s what happens, but just to give an idea how the evolution of the JVM could affect the reproducer (but not the claim).

Alex

> On 8 May 2017, at 19:56, Yubin Ruan <[hidden email]> wrote:
>
> On Mon, May 08, 2017 at 09:55:53AM +0100, Alex Otenko wrote:
>> I’d start with using the same version and brand of the JVM Bill used at the time of writing the article, which was probably written over 15 years ago.
>
> Hmm...You mean what he said is not correct now? We don't need the `volatile'
> keyword?
>
> --
> Yubin
>
>>
>>> On 8 May 2017, at 15:22, Yubin Ruan <[hidden email]> wrote:
>>>
>>> Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
>>> broken. Bill Pugh gave an example:
>>>
>>>   // Broken multithreaded version
>>>   // "Double-Checked Locking" idiom
>>>   class Foo {
>>>     private Helper helper = null;
>>>     public Helper getHelper() {
>>>       if (helper == null)
>>>         synchronized(this) {
>>>           if (helper == null)
>>>             helper = new Helper();
>>>       }    
>>>       return helper;
>>>     }
>>>     // other functions and members...
>>>   }
>>>
>>> His analysis is convincing, but the code he gave[2] work *well* on x86.
>>> That is expected to break sometimes. But, running it from time to time,
>>> I never see it break.
>>>
>>> How to verify that the double-check lock idiom will break on x86?
>>>
>>> ---
>>> Yubin
>>>
>>> [1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
>>> [2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> [hidden email]
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Make the double-checked lock idiom broken on x86

Michael Kuhlmann
@Yubin:

BTW I'm suspicious that the mentioned Helper class isn't mutable at all.
At least that would be surprising, I wouldn't expect a stateful helper
class (but I wouldn't even expect helper classes to be instantiable).

If Helper has no instance variables, or at least one of them is final,
then your code is already correct. At least since Java 5.

-Michael

Am 08.05.2017 um 14:00 schrieb Alex Otenko:

> No, I mean that the VM + execution environment may no longer produce the same side-effects that would quickly fail the reproducer in the olden days - so the published reproducer would need modification to demonstrate the problem on the modern hardware and the VM.
>
> For example, if the cost of synchronized is totally different, the threads no longer race in a way they used to. Suppose, the locks are biased now - one thread does the job, the rest of the threads are catching up, and after upgrade of the lock they all have to yield. When they wake up, the race effects are gone. So one thread does the job, and the others sleep.
>
> Not saying that’s what happens, but just to give an idea how the evolution of the JVM could affect the reproducer (but not the claim).
>
> Alex
>
>> On 8 May 2017, at 19:56, Yubin Ruan <[hidden email]> wrote:
>>
>> On Mon, May 08, 2017 at 09:55:53AM +0100, Alex Otenko wrote:
>>> I’d start with using the same version and brand of the JVM Bill used at the time of writing the article, which was probably written over 15 years ago.
>>
>> Hmm...You mean what he said is not correct now? We don't need the `volatile'
>> keyword?
>>
>> --
>> Yubin
>>
>>>
>>>> On 8 May 2017, at 15:22, Yubin Ruan <[hidden email]> wrote:
>>>>
>>>> Hi, from Bill Pugh's website[1] I read that the double-checked lock idiom is
>>>> broken. Bill Pugh gave an example:
>>>>
>>>>   // Broken multithreaded version
>>>>   // "Double-Checked Locking" idiom
>>>>   class Foo {
>>>>     private Helper helper = null;
>>>>     public Helper getHelper() {
>>>>       if (helper == null)
>>>>         synchronized(this) {
>>>>           if (helper == null)
>>>>             helper = new Helper();
>>>>       }    
>>>>       return helper;
>>>>     }
>>>>     // other functions and members...
>>>>   }
>>>>
>>>> His analysis is convincing, but the code he gave[2] work *well* on x86.
>>>> That is expected to break sometimes. But, running it from time to time,
>>>> I never see it break.
>>>>
>>>> How to verify that the double-check lock idiom will break on x86?
>>>>
>>>> ---
>>>> Yubin
>>>>
>>>> [1]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
>>>> [2]: https://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckTest.java
>>>> _______________________________________________
>>>> Concurrency-interest mailing list
>>>> [hidden email]
>>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Loading...