An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 20, 2021 3:47 UTC (Sat) by kurogane (guest, #83248)
Parent article: An introduction to lockless algorithms

I'm afraid I keep on interpreting the message example as being code that will only read datum->x once x was already assigned.

    thread 1                            thread 2
    --------------------------------    ------------------------
    a.x = 1;
    message = &a;                       datum = message;
                                        if (datum != NULL)
                                          printk("%d\n", datum->x);

That is that thread 2 will do nothing if "message" and hence "datum" pointer is still null, or receive a pointer to "a" after it already has its x member assigned.

Is the point that thread 2 was supposed to printk(), i.e. wait until datum is non-null? When I first saw this code it seemed natural to me that thread 2 was meant to be a 'just do nothing if object was not ready' thread though.

Or is the point there might be reordering, that CPU instruction-wise the stores and loads might not be not ordered as the C code above is?

to post comments

An introduction to lockless algorithms

Posted Feb 20, 2021 7:17 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (8 responses)

Yes, the point is that there might be reordering unless the store and load have release and acquire semantics respectively.

In theory the reordering could be on both sides, in practice (except on the Alpha) only the release side might be assigning a.x after message. Even on non-Alpha processors you need to inform the compiler not to do any reordering.

However you could have for example "ready=1" on the producer side and "if (ready) printk("%x", a.x)" on the consumer side. In that case both sides need to be protected against reordering at the processor level (in addition to the compiler level).

An introduction to lockless algorithms

Posted Feb 20, 2021 8:58 UTC (Sat) by kurogane (guest, #83248) [Link] (6 responses)

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.

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.

An introduction to lockless algorithms

Posted Mar 20, 2021 19:18 UTC (Sat) by guzh (subscriber, #140551) [Link]

Can we say that, in this case, the "happens before" effect is just a result of the fact that reordering is disallowed?
And only if the load *actually* happens after the store, we can say "a.x = 1" happens before "datum->x".
(If thread 2 runs really fast and completes before thead 1 starts, it sure won't get the proper value in x.)