[Q] how to break a concurrent program without proper use of MB

[Q] how to break a concurrent program without proper use of MB

[Yubin Ruan]

Hi,
As mentioned in the perfbook, without proper use of memory barrier, concurrent
program will be error prone. For example, in this program:

    int a=0;
    int b=0;
    
    void* T1(void* dummy)
    {
        a = 1;
        b = 1;
        return NULL;
    }
    
    void* T2(void* dummy)
    {
        while(0 == b)
            ;
        assert(1 == a);
        return NULL;
    }
    
    int main()
    {
        pthread_t threads[2] = {PTHREAD_ONCE_INIT, PTHREAD_ONCE_INIT};

        pthread_create(&threads[0], NULL, T1, NULL);
        pthread_create(&threads[1], NULL, T2, NULL);

        pthread_join(threads[0], NULL);
        pthread_join(threads[1], NULL);

        return 0;
    }

there is chances that the assertion in T2 would fail, because there is no MB used
in the program.

However, after testing it so many times, the assertion never get throwed.

Adding a loop to increase the chance:

        for(int i=0; i< 500; i++){
            a = b = 0;
    
            pthread_create(&threads[0], NULL, T1, NULL);
            pthread_create(&threads[1], NULL, T2, NULL);
    
            pthread_join(threads[0], NULL);
            pthread_join(threads[1], NULL);
        }

the result is the same.

How can I make the assertion fail? Any trick?
(and I am using a X64 laptop)

Thanks,
Yubin

Re: [Q] how to break a concurrent program without proper use of MB

[Yubin Ruan]

On Fri, May 05, 2017 at 09:18:21PM +0800, Yubin Ruan wrote:
> Hi,
> As mentioned in the perfbook, without proper use of memory barrier, concurrent
> program will be error prone. For example, in this program:
> 
>     int a=0;
>     int b=0;
>     
>     void* T1(void* dummy)
>     {
>         a = 1;
>         b = 1;
>         return NULL;
>     }
>     
>     void* T2(void* dummy)
>     {
>         while(0 == b)
>             ;
>         assert(1 == a);
>         return NULL;
>     }
>     
>     int main()
>     {
>         pthread_t threads[2] = {PTHREAD_ONCE_INIT, PTHREAD_ONCE_INIT};
> 
>         pthread_create(&threads[0], NULL, T1, NULL);
>         pthread_create(&threads[1], NULL, T2, NULL);
> 
>         pthread_join(threads[0], NULL);
>         pthread_join(threads[1], NULL);
> 
>         return 0;
>     }
> 
> there is chances that the assertion in T2 would fail, because there is no MB used
> in the program.
> 
> However, after testing it so many times, the assertion never get throwed.
> 
> Adding a loop to increase the chance:
> 
>         for(int i=0; i< 500; i++){
>             a = b = 0;
>     
>             pthread_create(&threads[0], NULL, T1, NULL);
>             pthread_create(&threads[1], NULL, T2, NULL);
>     
>             pthread_join(threads[0], NULL);
>             pthread_join(threads[1], NULL);
>         }
> 
> the result is the same.
> 
> How can I make the assertion fail? Any trick?
> (and I am using a X64 laptop)

I think I find the solution. :)
The problem with the approach above is that on X86/X64
    "Stores are not reordered with other stores"

After changing to this schema:

    processor 1 |  processor 2
    -------------------------
    mov [x], 1  | mov [y], 1
    mov r1, [y] | mov r2, [x]

I can demonstrate the re-odering issue, because according to the Intel arch'
manual[1], "Loads may be reordered with older stores to different locations"

Regards,
Yubin

[1]: https://software.intel.com/en-us/articles/intel-sdm

Re: [Q] how to break a concurrent program without proper use of MB

[Paul E. McKenney]

On Sat, May 06, 2017 at 07:40:40PM +0800, Yubin Ruan wrote:
> On Fri, May 05, 2017 at 09:18:21PM +0800, Yubin Ruan wrote:
> > Hi,
> > As mentioned in the perfbook, without proper use of memory barrier, concurrent
> > program will be error prone. For example, in this program:
> > 
> >     int a=0;
> >     int b=0;
> >     
> >     void* T1(void* dummy)
> >     {
> >         a = 1;
> >         b = 1;
> >         return NULL;
> >     }
> >     
> >     void* T2(void* dummy)
> >     {
> >         while(0 == b)
> >             ;
> >         assert(1 == a);
> >         return NULL;
> >     }
> >     
> >     int main()
> >     {
> >         pthread_t threads[2] = {PTHREAD_ONCE_INIT, PTHREAD_ONCE_INIT};
> > 
> >         pthread_create(&threads[0], NULL, T1, NULL);
> >         pthread_create(&threads[1], NULL, T2, NULL);
> > 
> >         pthread_join(threads[0], NULL);
> >         pthread_join(threads[1], NULL);
> > 
> >         return 0;
> >     }
> > 
> > there is chances that the assertion in T2 would fail, because there is no MB used
> > in the program.
> > 
> > However, after testing it so many times, the assertion never get throwed.
> > 
> > Adding a loop to increase the chance:
> > 
> >         for(int i=0; i< 500; i++){
> >             a = b = 0;
> >     
> >             pthread_create(&threads[0], NULL, T1, NULL);
> >             pthread_create(&threads[1], NULL, T2, NULL);
> >     
> >             pthread_join(threads[0], NULL);
> >             pthread_join(threads[1], NULL);
> >         }
> > 
> > the result is the same.
> > 
> > How can I make the assertion fail? Any trick?
> > (and I am using a X64 laptop)
> 
> I think I find the solution. :)
> The problem with the approach above is that on X86/X64
>     "Stores are not reordered with other stores"
> 
> After changing to this schema:
> 
>     processor 1 |  processor 2
>     -------------------------
>     mov [x], 1  | mov [y], 1
>     mov r1, [y] | mov r2, [x]
> 
> I can demonstrate the re-odering issue, because according to the Intel arch'
> manual[1], "Loads may be reordered with older stores to different locations"

Exactly!

The compiler might reorder the stores, but it would be deterministic.

Alternatively, you could run on ARM, PowerPC, IA64, Alpha, or MIPS and
have both loads and stores be reordered.

							Thanx, Paul

> Regards,
> Yubin
> 
> [1]: https://software.intel.com/en-us/articles/intel-sdm
> --
> To unsubscribe from this list: send the line "unsubscribe perfbook" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>