3 ms·
I tried to write a lock free ringbuffer with weak atomics, I haven't proved it right with TLA+ yet but I started writing a model in it. I use tagging to avoid t
by samsquire 3y ago
I tried to write a lock free ringbuffer with weak atomics, I haven't proved it right with TLA+ yet but I started writing a model in it. I use tagging to avoid the ABA problem.
they're all on https://github.com/samsquire/assembly https://github.com/samsquire/assembly, i tried to write multiple disruptor with multiple consumers, then one with multiple producers then one with multiple consumers AND multiple producers, inspired by LMAX Disruptor. (There's files for each of them and table in the repo. it's not proven yet!)
the contention on the same memory address (the read/write index) is the thing that seems difficult to address.
One thing I've learned about thread safety:
I think if you have thread-owned values then you can be thread safe with a simple semaphore, providing that you have unique, DISTINCT values for each thread.
If you have two threads that have this in a hot loop in parallel:
// thread 0
if buffer[x].available == 1:
// do stuff
buffer[x].available = 0
// thread 1
if buffer[x].available == 0:
// do stuff
buffer[x].available = 1
Due to causality, no matter the interleaving, thread 0 owns the buffer[x].available and body of the if statement when it is 1 and thread 1 owns the body of the if statement buffer[x].available when it is 0.
The CMP is a cheap mutex with distinct valued memory locations.
Even though thread 1 is writing to buffer[x].available and thread 0 is writing to buffer[x].available it doesn't matter because the causality is mutually exclusive. There is no interleaving of buffer[x].available = x because of the if statement.
The buffer[x].available = 0 will never run while buffer[x].available is equal to 0 overwriting or causing a data race when setting buffer[x].available to 1. So the second line cannot happen in parallel.
I need to write a TLA model to assert its safety.
If you have more than 2 threads, then you need different tokens to provide admissability to the if statement.
Remember to use compiler memory barrier
asm volatile ("" ::: "memory");
so you don't need volatile struct values.
- loeg 3y ago> The buffer[x].available = 0 will never run while buffer[x].available is equal to 0 overwriting or causing a data race when setting buffer[x].available to 1. In particular, because loads and stores of the same variable cannot be reordered out of program order. Once your algorithm involves other variables, you would (likely) need to be a little careful about loading/storing with acquire/release semantics to prevent reordering other accesses relative to this protocol. > Remember to use compiler memory barrier I would highly recommend using the language atomic types (and barriers if truly needed) instead of gcc inline assembly syntax.
- samsquire 3y agoThanks for your reply. This subject is still new to me. My understanding of that syntax is that it is a compiler memory barrier, not a CPU memory barrier because the asm block is empty (no sfence or mfence).
- loeg 3y agoHey, no problem. > My understanding of that syntax is that it is a compiler memory barrier, not a CPU memory barrier because the asm block is empty (no sfence or mfence). In C11, you can write compiler-only fences with atomic_signal_fence: https://en.cppreference.com/w/c/atomic/atomic_signal_fence https://en.cppreference.com/w/c/atomic/atomic_signal_fence (In practice, though, I think it is rare that you actually want a compiler-only fence. Instead, correct use of acquire/release operations prevents reorderings.)
- samsquire 3y agoThank you loeg, I appreciate you and information you brought that TIL. I've been using a compiler fence to force reloads from memory to prevent -O3 from optimising away my variables/structs changing by other threads and keeping data in registers rather than reloading from memory each time. I saw the volatile recommended against from the Linux kernel programmers. such as my thread->running == 1 in my event loops for my threads. https://www.kernel.org/doc/html/latest/process/volatile-considered-harmful.html https://www.kernel.org/doc/html/latest/process/volatile-cons...
- loeg 3y ago> I've been using a compiler fence to force reloads from memory to prevent -O3 from optimising away my variables/structs changing by other threads I would highly recommend using the language standard atomic primitives instead.
- samsquire 3y agoWhen you check available, you might have to do it as a (__atomic_load_n(&sender->realend, __ATOMIC_SEQ_CST) and do __atomic_store_n when setting available. rather than just a plain load.
- gpderetta 3y agoThe problem here is the [1] // Do stuff [2] Buffer[X]. available = Y There is no explicit nor implicit ordering between 1 and 2, so the compiler or cpu can reorder them. You need a release barrier between the two. Also while most CPUs preserve the control dependency, not all do (famously Alpha), and certainly not compilers. You would need a consume barrier, except that c++11 consume is only for data dependencies and unimplemented anyway. Edit: with the correct barriers in place, you can prove correctness by similitude to two size 1 SPSC queues used to exchange a mutual exclusion token, with the added quirk that as the queues are never used at the same time, they can actually be physically colocated in memory.
- samsquire 3y agoThank you for you and for sharing your knowledge gpderetta, appreciated, TIL.
- anonymousDan 3y agoRegarding the contention, one thing that's important is to cache a local copy of the shared head and tail variables every time you access them. Then for subsequent operations you can first check the local cached copy to see if you can perform the read or write without needing to check the shared variables.