McKenney: So You Want to Rust the Linux Kernel?

This reminds me of a queuing-theory class I took some decades back, though more than 50 years after the passing of Agner Karup Erlang, who laid the foundations for modern queuing theory. The professor explained one aspect of queuing theory (I forget which, sorry!). Then explained it again. And again. At which point, I raised my hand and asked why we were going over this so many times. The professor complimented me on understanding that aspect so quickly and then asked me to be quiet while he continued getting it across to the remainder of the class. I eventually figured out that he was explaining that aspect of queuing theory from different viewpoints, so it could be understood by different mindsets. I just happened to be lucky in that he happened to pick my mindset first.

I thought nothing of this incident at the time, but have had many occasions to recall it since Jack and I invented RCU.

And this is because of the wide gap between RCU's base-level semantics and typical use cases. And the base semantic really is "waiting for pre-existing things to finish", as you can see from the LKMM formalization of both RCU and SRCU. And because of this wide gap, I am not at all surprised at your discomfort with this description. It is a good place to start only for those few people who like building up from the fundamentals (not me!), and is in many cases worse than useless for the many people who prefer thinking in terms of tools to take on particular use cases.

To your later "deferred destruction" point, Maged Michael and I group Hazard Pointers and RCU under the "deferred reclamation" heading, along with reference counting. But not all RCU use cases involve reclamation. Plus this loses much of the connection to replacements for reader-writer locking. (The reason we don't say "deferred destruction" has to do with C++ destructors, in case you were wondering.)

So it is necessary to present multiple views of RCU, just as it was necessary for that professor to present multiple views of that aspect of queuing theory, whatever it might have been.

And your reference-coiunting view is a most excellent view, which is why it has its own section in perfbook. More than one, in fact: 9.5.4.3 "RCU is a Restricted Reference-Counting Mechanism" and 9.5.4.4 "RCU is a Bulk Reference-Counting Mechanism". But to your point, it does not seem to be well represented in Documentation/RCU. Would you like to add it? (Not as a replacement for the reader-writer-locking analogy, but as an additional view.)

Yes, RCU and hazard pointers overlap quite a bit. See Tables 9.6 and 9.7 in perfbook for Maged's and my view of the advantages and drawbacks of each. The point I am trying to make is that if your code already uses reference counts and already handles reference-count acquisition failure, the software-engineering disadvantages of hazard pointers don't matter so much to you. Yes, you might simplify your code by switching to RCU, but there might not be so much incentive to do so. Similarly, if your code already uses reader-writer locking, you will have kept your read-side critical sections reasonably short, so the memory-footprint disadvantages of RCU don't matter so much to you. But it is all just software, and thus can all be changed. In theory, anyway. ;-)

A common RCU use case resembling reader-writer locking avoids changing data (as opposed to list pointers). This use case has readers seeing constant data, just as they would with classic reader-writer locking (but not with some of the more esoteric use cases that cause some people to not unreasonably object to the name "reader-writer locking"). And to your point, one reason why the C++ committee was interested in both RCU and hazard pointers was that they saw them as ways of taming many classes of lockless algorithms. And the C++ community is one reason why I shy away from describing RCU in terms of reference counting. Once someone in that community dives down the smart-pointer rabbit hole, it is extremely difficult for them to understand RCU. And almost impossible to haul them back out of that hole.

To people claiming that RCU is difficult, I go back further in time, to a late 1970s lecture by the late Edsger Dijkstra that I had the privilege of attending. He claimed that "while" loops were difficult and that the typical programmer could not be trusted to write one correctly. This claim resonated with much of the audience (though not with my then-young and arrogant self), but probably would not resonate today. So part of the perception of RCU's difficulty is cultural, and the culture is changing. Me, I have had quite a number of people tell me that they had heard that RCU was really difficult, and were surprised to find that not only was it reasonably easy, but that it simplified things (deadlock avoidance being the source of simplification that is usually cited).

So from what I can see, the trick is to get a given developer pointed at the view of RCU that best matches the use case at hand. Thoughts on attacking that problem?

And again, can I interest you in adding an "RCU as reference counter" .rst file to Documentation/RCU?