An introduction to lockless algorithms

Posted Feb 20, 2021 7:11 UTC (Sat) by pbonzini (subscriber, #60935)
In reply to: An introduction to lockless algorithms by mss
Parent article: An introduction to lockless algorithms

The C11 model has some quirks of its own that make it sometimes harder to use than the Linux kernel memory model. I had a half-baked idea of a sixth article on the topic of C11 atomics for kernel programmers, based on the comments here it seems like there's interest.

An introduction to lockless algorithms

Posted Feb 20, 2021 16:11 UTC (Sat) by mss (subscriber, #138799) [Link]

It's a nice topic bordering between theoretical CS stuff and real world software engineering.

By the way, you said in a comment under the July article to steer clear of the C11 "sequentially consistent" loads and stores since they are incredibly easy to get wrong.
I assume you mean that people have misconceptions about the ordering guarantees that sequentially consistent semantics give?
After all, they provide acquire and release semantics, too, so any algorithm that's valid under acq/rel will be valid under sequentially consistent semantics, too (just maybe slower).

For me personally the most surprising thing with C11 atomics is that a relaxed operation on a variable plus a barrier of X memory order (before or after that operation) is not the same thing as just performing the same operation but with the X memory order, even though the semantics are very close.

In general, the C11 atomics seem to be tailored more for using atomic operations of particular memory order rather than barriers, while most of the kernel code seems to prefer using ordinary memory accesses with barriers instead.