sbahra

Also up on https://engineering.backtrace.io/2021-01-11-stuff-your-logs/

Thanks for sharing!

For single-writer multi-reader scenario this requires no atomic fences or operations on TSO: http://concurrencykit.org/presentations/lpc2015.pdf

Works on any open-addressed scheme (there is also a robin hood implementation).

overthewire.org

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.

Welcome to also shoot me a mail at sbahra@backtrace.io.

Whoops, good catch! I will fix, thanks.

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.

On real world implementations: It is worth mentioning http://concurrencykit.org :-P

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).

Or use backtrace.io to deal with it. It'll transfer the core dump or a derivative to a centralized server.

Transparency: co-founder.

Can confirm.

It reverts to a bus lock in this split transaction case, not cache line locking (thus stalling whole system).

Yes, it is possible. We are hiring, learn more at http://Backtrace.io

Oh, cool! We hope to publish something soon on this. ;-)

It would be great to learn more about the work you're doing.

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.

Is there a "Cotton Eye Joe" reference here?

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.

Some open-source examples: http://www.machinekit.io/ https://labs.omniti.com/labs/reconnoiter https://github.com/Litres/turboxsl Aerospike

I'm sure there are others, if there's anything I'm missing, would love to hear.

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.

HP is much more granular and a stuck thread does not inhibit system wide progress (yes, the slots won't be reclaimed but other entries will continue to be reclaimed).

Note that epoch reclamation is only competitive with amortization, otherwise you may as well use hazard pointers for simple structures to benefit from stronger progress guarantees. Of course, QSBR is best if you have quiescent points.

Stand-alone EBR also available at http://concurrencykit.org

Paul has been doing great work here: http://repnop.org/pd/slides/bsearch.pdf

Pulltheplug

Not comparing to HP/PTB/LFRC, just RCU and similar schemes. You're right in that the first class are easy to beat given appropriate workload.

RCU is being conflated, the (Hart) paper I linked to will addresses your questions (sorry phone).

More efficient than using garbage collection, if you're working with a language where you can operate in an unmanaged mode (barring FFI). I do expect this gap to start closing based on some literature some friends have shared with me...

With most managed languages I've played with, I haven't found a compelling reason to use RCU-like mechanisms (except if it involves some FFI boundary or embedded language in unmanaged system).

What you're doing sounds like a seqlock pattern (see ck_sequence) or generation counter, not RCU. Fundamental to all RCU implementations is "grace period detection" (detection of the point in which it is safe to free memory) occurring without any read-side delays. With RCU, a reader never has to retry due to RCU itself.

RCU is really special in an unmanaged language, but I'm not sure it's that interesting for developers working in a managed language (unless they happen to be solving safe memory reclamation).

The magic of RCU definitely is the safety guarantee on read-side with little to no overhead and an easy to approach API. Traditional copy-on-write systems do not provide this guarantee as there would be synchronization and / or blocking on the fast path (barriers / atomic operations / locks).

Cores versus threads is a detail of the execution environment which may affect RCU implementation but not the actual magic. For example, a lot of work was necessary to get RCU to scale to many hundreds of cores in the kernel (http://lwn.net/Articles/305782/ is one example).

For ck_epoch, we had to implement a proxy collection-like pattern for workloads involving thousands of concurrent events that required longer-lived hazardous references (thanks to John Esmet for this work)...this will hit upstream as ck_epc and is sitting in a pull request on the github page (http://github.com/concurrencykit/ck).

re:Efficiency, magnitudes more efficient on read-side in all ways (including throughput and latency) assuming that delete frequency is not too heavy and that you can afford write-side blocking. Consider that the read-side has few to none atomic operations on the fast path, and if so, is typically on exclusively written memory and it does not block in any fashion. This means readers scale and are very fast. You might enjoy the paper I linked to which exposes some of the performance characteristics (it isn't exhaustive, it doesn't explore real-world implications on memory usage as update frequency increases, for example, but it's a great start). Paul also has some refreshed performance analysis in his ACM Queue article. If you couple this with specialized concurrently readable data structures (like http://backtrace.io/blog/blog/2015/03/13/workload-specializa...), you get super sexy performance for readers.

You might also be interested in "passive reader-writer locks", which provide similar costs on the fast path to RCU for TSO architectures while still providing read-write lock semantics...but at the cost of exceptionally more expensive write-side synchronization (and user-space support requires some kernel modifications).

1) Efficiency of algorithms stems from disabling interrupts

The efficiency stems from having little to zero synchronization cost for readers in a read-mostly workload or workload that just isn't update-intensive. In addition to that, note that a deferral interface is available so writers basically never have to block until it is actually safe to free memory. URCU and ck_epoch all share those desirable qualities.

2) "RCU algorithm I've seen ... protects with a read-write"

The synchronize portion of RCU and RCU-like systems is almost always heavy-weight. Applications that adopt URCU can typically afford this.

3) "no algorithm more efficient than a general purpose GC"

All the blocking schemes are magnitudes more efficient but the trade-off is that it isn't generally applicable. However, they're still applicable for plenty of workloads. We are starting to see more GC mechanisms adopt SMR-like techniques so that may change.

4) "Common authorship, BTW, says little"

Not in this case.

If you would like to learn more about the performance trade-off with the various mechanisms, I suggest http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf and the URCU paper as a start. I've some additional numbers on something similar at http://concurrencykit.org/presentations/ebr.pdf

Paul also has a good introduction up at https://queue.acm.org/detail.cfm?id=2488549

What makes you say this?

RCU refers to a wide array of reclamation implementations and some URCU implementations do indeed have a lot in common with kernel-space RCU (which also has a myriad of implementations).

Speaking of liburcu in specific, the "brittleness" is a function of your workload and your selection of the URCU implementation. The various implementations have different trade-offs, and it is definitely possible to livelock write-side or degrade read-side if you make the wrong design decisions. For example, there are major differences between signal-based URCU and QSBR URCU. No reclamation mechanism (whether one backed by RCU or something like hazard pointers) is a silver bullet and each will suck in fantastic ways with the right workload.

As far as userspace RCU algorithms in general being "experimental", plenty of people are using RCU or RCU-like mechanisms in user-space for production systems as a scalable synchronization solution. For example, the Concurrency Kit library (http://concurrencykit.org) has an RCU-like system called ck_epoch, and it sees at least billions of transactions in production a day without fail, and even supports freestanding environments.