Give us a spin! Would absolutely love more feedback, it has had a big impact for us already. It’s free for open-source projects.
The tool for ASAN/etc... is just a few weeks old but we have been doing crash / error reporting and custom debuggers (built-in static analysis) for the last 5 years.
I'm referring to the FIFO implementation. On the definition of QSBR though, frankly, I think the term gets overloaded in some of the more recent literature in this area. Both EBR and QSBR require that no hazardous references get carried over across "protected sections" (EBR is explicit read-side protected sections and in QSBR, across a quiescent point).
Great write-up! A few notes worth mentioning (IMO) below:
Garbage collection:
This is only true in absence of garbage collection. If you're paying garbage collection cost to begin with, this is not an issue. Also, note things such as http://web.mit.edu/willtor/www/res/threadscan-spaa-15.pdf
This only applies to dynamic lock-free data structures:
Or, data structures requiring memory allocation. If you're using bounded buffers and don't require memory allocation, this isn't an issue.
Taxonomy:
Not all passive schemes are quiescent-state-based. In QSBR, quiescent points are a first-class entity while that is not the case in EBR (you have only 3 distinct states). Absent extensions you are unable to differentiate one quiescent point from another, which has real implications on being able to implement things like deferred / non-blocking reclamation efficiently. There are some advantages to this, a while ago Paul Khuong contributed a reference counting scheme to epoch reclamation allowing for overlapping protected sections (bounded epoch makes reference counting practical, something you can't do with unbounded quiescent points). It's pretty great and note, it doesn't require a strict notion of quiescence! You'll find this in Concurrency Kit.
It is also worth noting the HP, etc... (pointer-based schemes) can be used to implement QSBR.
For these reasons, I prefer to classify these techniques into two primary families (based on the semantics of the interface rather than the implementation): "passive schemes" and "active schemes". Passive schemes do not require cooperation from the algorithms requiring safe memory reclamation (EBR, QSBR, etc...) while "active schemes" do (HP, PTB, etc... in their textbook form require modification to the algorithm).
On blocking for passive schemes:
It is worth noting that QSBR, EBR and other "passive schemes" do have "non-blocking" (informally) interfaces (rcu_call, text-book EBR utilizes limbo lists, etc...) such that writers do not have to block on the fast path, but of course, there is the cost of memory accumulating until a grace period is detected (so, not non-blocking in the formal sense but if you've the memory to spare and sufficient forward progress, becomes a non-issue). In my implementations, I typically use a dedicated thread for forward progress / epoch detection, ensuring the writer has forward progress.
You have much higher granularity and the lock-free progress guarantee in hazard pointers, because it is pointer-based (tied to the forward progress guarantees of the underlying algorithm).
Under-appreciated recent development:
An interesting thing to note here is there are schemes such as https://www2.seas.gwu.edu/~seotest/publications/eurosys16ps.... which do not necessitate the same heavy-weight barriers in the presence of invariant TSC+TSO and with a sufficiently high granularity TSC, can provide the same forward progress guarantees as hazard pointers.
On hazard pointers being slow:
One interesting thing to note is hazard pointers can also be used to implement "passive" schemes such as proxy collection, to give similar performance properties as EBR and QSBR.
This is quiescent-state-based reclamation, other implementations exist that are cheap. I have seen the technique you're talking about used in K42 (after I had also thought I invented something novel, when I used the same approach as you :-P).
Glad you liked it. Unfortunately, core files can be massive and require you to have a lot of the assets from the environment the fault occurred in to debug. Last but not least, it would be good if they gave us more of a head-start on root cause. These are all things we're directly tackling at Backtrace.
Code duplication can also mean more errors and a lot more work for porters. You'll also see plenty of other examples in popular open-source projects such as the Linux and FreeBSD kernel. The reduction in amount of duplication is significant.
For example:
For SPARCv9 for example, the macro system generates 138 functions from only the 25 or so the developer provides. To top it off, this would work across memory models as well.
I agree. Such an article would be more emphasizing use-cases for different advanced synchronization techniques in context of Concurrency Kit. You may just not have a use for it too.
I'll put up a presentation soon that may be helpful in these regards.
It's used in a lot of mission-critical commercial applications which I think is a stronger indicator. It just so happens those aren't open-source. This ranges from mission-critical enterprise software to internal infrastructure tied directly to revenue generation. There is a serious cost to failure there (money, liability, jobs, etc...).
Few software uses these advanced techniques in general, and it isn't so much about Concurrency Kit. There is a barrier to entry as folks have to invest non-trivial amounts of time in learning more about these techniques.
They are. As Alex points out, a fair number are a mixture of single-reader many-writer or many-writer single-writer, and a few are many-writer many-reader.
MPMC: ck_stack, ck_fifo, ck_ring (in the works), ck_disruptor (pending push), ck_bitmap (but not linearized) and ck_hp*
And in some cases, these are just building blocks for more complex structures.
Specialized:
- Everything else, including ck_[r]h{s,t}*.
The synchronization primitives are all generalized to multiple writers (exception is ck_swlock which is specialized). The manual pages should point out bounded concurrency.
RCU is a higher-level abstraction. You can implement RCU with epoch reclamation, typically there are more performant ways to detect grace periods in kernel space.