An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 8:58 UTC (Sat) by kurogane (guest, #83248)
In reply to: An introduction to lockless algorithms by pbonzini
Parent article: An introduction to lockless algorithms

Thanks Paolo. If the processor instructions don't necessarily follow the higher-level language flow shown in the example, then it I get it I believe. Well, could you confim?

The instruction flow in the processor could end up like the below, as the C programmer mentally pictures it?

    thread 1                            thread 2
    --------------------------------    ------------------------
    message = &a;                       ...
                                        ...
    a.x = 1;                            ...

(Focusing just on thread 1 as that is the more likely jeopardy-maker.)

I think I finally understand what memory barriers are - temporal ones, not spatial.

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 9:13 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (5 responses)

Yes, exactly.

On one hand it may not happen on all processors, and details may vary depending on the microarchitecture. On x86 that reordering cannot happen, on ARM and PowerPC it might.

But on the other hand the compiler might always be reordering stuff behind your back. The big insight of the C++ committee was that the same abstraction could cover both processor-level and compiler-level reorderings.

An introduction to lockless algorithms

Posted Feb 20, 2021 11:04 UTC (Sat) by kurogane (guest, #83248) [Link] (1 responses)

(thumbs-up sign)

I appreciated this confirmation very much.

An introduction to lockless algorithms

Posted Feb 20, 2021 20:31 UTC (Sat) by danobi (subscriber, #102249) [Link]

Thanks for asking -- had the same questions myself.

An introduction to lockless algorithms

Posted Feb 21, 2021 19:13 UTC (Sun) by khim (subscriber, #9252) [Link] (2 responses)

> On x86 that reordering cannot happen, on ARM and PowerPC it might.

Tiny correction: on x86 it can and will happen. You need memory barriers there, too.

After reading the aforementioned article I was confused for some time: memory barriers arrived on x86 with SSE… yet SMP was supported for more than decade by that time! Some investigation showed that any instruction with lock prefix acts as a memory barrier on x86. But if there are not memory barriers at all… yes, it does happen on x86, too.

An introduction to lockless algorithms

Posted Feb 21, 2021 19:16 UTC (Sun) by khim (subscriber, #9252) [Link]

After looking on that article again I have realized that Jeff added addendum to the end which reveals all the gory details about lock and xchg. So there are no mystery anymore…

An introduction to lockless algorithms

Posted Feb 21, 2021 20:51 UTC (Sun) by pbonzini (subscriber, #60935) [Link]

It can't happen until part 3. :) This article and the next one are only concerned with load-load and store-store reordering, which are not possible on x86.