5 ms·

I've never actually seen a production lock-free algorithm that uses SeqCst. I have a hard time even imagining an algorithm where SeqCst is the right choice. I

I've never actually seen a production lock-free algorithm that uses SeqCst. I have a hard time even imagining an algorithm where SeqCst is the right choice. It seems like SeqCst was chosen as a default to reduce the surprises and gotchas around lock-free programming. But lock-free programming is inherently tricky; if you're trying to avoid surprises and gotchas you should probably use a mutex.

senderista 3y ago
It is the right choice whenever you need linearizability. I can't believe you've never seen a (correct) production lock-free algorithm impl that used SeqCst. Many lock-free algorithms require SeqCst for correctness. Here's a trivial example: hazard pointers. Any thread publishing its hazard pointer must use a StoreLoad barrier (equivalent to SeqCst) to ensure any GC thread scanning the publication list sees its hazard pointer, before it deallocates pointers in the limbo list that didn't appear in the scan. MemSQL actually wrote a blog post on a nasty bug in their database arising from their use of AcqRel for this operation instead of SeqCst: https://www.singlestore.com/blog/common-pitfalls-in-writing-lock-free-algorithms/ https://www.singlestore.com/blog/common-pitfalls-in-writing-....
- loeg 3y ago
  This blog post leaves a lot to the imagination. > Here’s the case that broke our stack: Thread 1, in preparation for a Pop operation, reads the head of the stack. Thread 1 writes the current head to its hazard pointer (using only release semantics, which are weaker than sequentially consistent semantics). Thread 1 reads the head of the stack again. Thread 2 removes head from the stack, and passes it to the garbage collector thread (using sequentially consistent memory semantics). The garbage collector scans the hazard pointers,\ and (because the assignment was not done with sequentially consistent memory semantics) is not guaranteed to see thread 1’s hazard pointer pointing to the node. The garbage collector deletes the node Thread 1 dereferences the node, and segfaults. My interpretation is that with release semantics for the store, the 2nd read (load) in Thread 1 is actually allowed to be reordered before the release store to the hazard pointer. But they are not very explicit about it. > So if thread 2 removing the pointer happens first, thread 1 will see a different value on its second read and not attempt to dereference it. Thread 1 will see thread 2's remove even with release semantics for that store -- the store has a data dependency on the first load; they cannot be reordered. > If thread 1 writes to its hazard pointer first, the garbage collector is guaranteed to see that value and not delete the node. Yeah, this must be it. Thread 1 fails to notice the GC happened while it was writing its HP because its second load actually happened before the HP store. Folly's hazard pointer implementation uses a release store to update the hazard pointer (here: reset_protection()), but uses some sort of SeqCst barrier between the store and the 2nd load (with acquire semantics): https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrHolder.h#L120-L125 https://github.com/facebook/folly/blob/main/folly/synchroniz...
  - senderista 3y ago
    Yes, the store to the HP entry must happen-before both the second load of the global pointer in the publishing thread and any load of the HP entry in another (GC) thread. (The first load + store + second load emulates an atomic memory-to-memory copy of the global pointer to the HP entry.)
- gpderetta 3y ago
  You certainly need a #storeload to update the hazard pointer, but do you really need seq_cst? Is a total order of all updates really necessary? Wouldn't, say, an acq_rel exchange be sufficient? I need to read that article, it seems interesting.
  - loeg 3y ago
    To set a HP on Linux, Folly just does a relaxed load of the src pointer, release store of the HP, compiler-only barrier, and acquire load. (This prevents the compiler from reordering the 2nd load before the store, right? But to my understanding does not prevent a hypothetical CPU reordering of the 2nd load before the store, which seems potentially problematic!) Then on the GC/reclaim side of things, after protected object pointers are stored, it does a more expensive barrier[0] before acquire-loading the HPs. I'll admit, I am not confident I understand why this works. I mean, even on x86, loads can be reordered before earlier program-order stores. So it seems like the 2nd check on the protection side could be ineffective. (The non-Linux portable version just uses an atomic_thread_fence SeqCst on both sides, which seems more obviously correct.) And if they don't need the 2nd load on Linux, I'm unclear on why they do it. [0]: https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrDomain.h#L523 https://github.com/facebook/folly/blob/main/folly/synchroniz... (This uses either mprotect to force a TLB flush in process-relevant CPUs, or the newer Linux membarrier syscall if available.)
    - gpderetta 3y ago
      Ah, yes it uses an asynchronous barrier trick. Basically it promotes the compiler barrier to a full barrier. It makes sense for throughput if one side is executed significantly more often than the other like in this case. The cost is latency spikes.
      - loeg 3y ago
        I don't yet understand how the other side promotes a compiler barrier to a full barrier, but I'll take your word for it and try to read more about it later. :-)

senderista 3y ago

It is the right choice whenever you need linearizability. I can't believe you've never seen a (correct) production lock-free algorithm impl that used SeqCst. Many lock-free algorithms require SeqCst for correctness. Here's a trivial example: hazard pointers. Any thread publishing its hazard pointer must use a StoreLoad barrier (equivalent to SeqCst) to ensure any GC thread scanning the publication list sees its hazard pointer, before it deallocates pointers in the limbo list that didn't appear in the scan. MemSQL actually wrote a blog post on a nasty bug in their database arising from their use of AcqRel for this operation instead of SeqCst: https://www.singlestore.com/blog/common-pitfalls-in-writing-lock-free-algorithms/ https://www.singlestore.com/blog/common-pitfalls-in-writing-....

loeg 3y ago
This blog post leaves a lot to the imagination. > Here’s the case that broke our stack: Thread 1, in preparation for a Pop operation, reads the head of the stack. Thread 1 writes the current head to its hazard pointer (using only release semantics, which are weaker than sequentially consistent semantics). Thread 1 reads the head of the stack again. Thread 2 removes head from the stack, and passes it to the garbage collector thread (using sequentially consistent memory semantics). The garbage collector scans the hazard pointers,\ and (because the assignment was not done with sequentially consistent memory semantics) is not guaranteed to see thread 1’s hazard pointer pointing to the node. The garbage collector deletes the node Thread 1 dereferences the node, and segfaults. My interpretation is that with release semantics for the store, the 2nd read (load) in Thread 1 is actually allowed to be reordered before the release store to the hazard pointer. But they are not very explicit about it. > So if thread 2 removing the pointer happens first, thread 1 will see a different value on its second read and not attempt to dereference it. Thread 1 will see thread 2's remove even with release semantics for that store -- the store has a data dependency on the first load; they cannot be reordered. > If thread 1 writes to its hazard pointer first, the garbage collector is guaranteed to see that value and not delete the node. Yeah, this must be it. Thread 1 fails to notice the GC happened while it was writing its HP because its second load actually happened before the HP store. Folly's hazard pointer implementation uses a release store to update the hazard pointer (here: reset_protection()), but uses some sort of SeqCst barrier between the store and the 2nd load (with acquire semantics): https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrHolder.h#L120-L125 https://github.com/facebook/folly/blob/main/folly/synchroniz...
- senderista 3y ago
  Yes, the store to the HP entry must happen-before both the second load of the global pointer in the publishing thread and any load of the HP entry in another (GC) thread. (The first load + store + second load emulates an atomic memory-to-memory copy of the global pointer to the HP entry.)
gpderetta 3y ago
You certainly need a #storeload to update the hazard pointer, but do you really need seq_cst? Is a total order of all updates really necessary? Wouldn't, say, an acq_rel exchange be sufficient? I need to read that article, it seems interesting.
- loeg 3y ago
  To set a HP on Linux, Folly just does a relaxed load of the src pointer, release store of the HP, compiler-only barrier, and acquire load. (This prevents the compiler from reordering the 2nd load before the store, right? But to my understanding does not prevent a hypothetical CPU reordering of the 2nd load before the store, which seems potentially problematic!) Then on the GC/reclaim side of things, after protected object pointers are stored, it does a more expensive barrier[0] before acquire-loading the HPs. I'll admit, I am not confident I understand why this works. I mean, even on x86, loads can be reordered before earlier program-order stores. So it seems like the 2nd check on the protection side could be ineffective. (The non-Linux portable version just uses an atomic_thread_fence SeqCst on both sides, which seems more obviously correct.) And if they don't need the 2nd load on Linux, I'm unclear on why they do it. [0]: https://github.com/facebook/folly/blob/main/folly/synchronization/HazptrDomain.h#L523 https://github.com/facebook/folly/blob/main/folly/synchroniz... (This uses either mprotect to force a TLB flush in process-relevant CPUs, or the newer Linux membarrier syscall if available.)
  - gpderetta 3y ago
    Ah, yes it uses an asynchronous barrier trick. Basically it promotes the compiler barrier to a full barrier. It makes sense for throughput if one side is executed significantly more often than the other like in this case. The cost is latency spikes.
    - loeg 3y ago
      I don't yet understand how the other side promotes a compiler barrier to a full barrier, but I'll take your word for it and try to read more about it later. :-)