LWN: Comments on "What is RCU? Part 2: Usage"

What is RCU? Part 2: Usage

baiwfg2 — Thu, 02 Jun 2022 08:56:00 +0000

Hi, Paul. I know it's a very old article, and it's still useful to me. I really want to repeat what you did to get those performance comparison graphs, because only if I experiment by myself, I would understand RCU better and recommand RCU to my team with greater confidence. Could you provide the exact demo source file for me to get those graphs (including what you measure and how you measure) ? If I write by myself, I'm afraid that I may not get same results as you got.

Reader-to-updater upgrade?

ik335 — Mon, 03 Dec 2018 17:30:05 +0000

Thank you so much for the discussion below. Obviously, we can have reader-to-updater upgrade to check ABA property-- compare exchange pointers -- in the read critical section. However, I have been trying to come up with a good example for reader-to-updater upgrading from memory-safety perspective. Is there a good example/reason where we see reader threads upgraded to the writer thread and allocates-publishes/unlinks a heap node without violating the fundamental RCU property?

[OT] JPEG + graphs == hideous

PaulMcKenney — Tue, 15 Jan 2008 06:13:10 +0000

Cool!  I just installed pngcrush, will try it out!

[OT] JPEG + graphs == hideous

roelofs — Fri, 11 Jan 2008 06:42:20 +0000

For xfig, how about this .gif, as opposed to the six-times-bigger .jpg?

Indeed--and notice how the red dashed line is so much brighter now, and the black-on-green text is far sharper? JPEG hates sharp boundaries. (Gibbs' phenomenon and all.)

For gnuplot, how about this .gif, as opposed to the nine-times-bigger .jpg?

You (or gnuplot) must have used a very high quality setting for the JPEG, because that nine-times-bigger JPEG is actually grayscale (i.e., nominally one-third the raw data, or at least one-half given the usual YCbCr subsampling of the color channels in a three-component JPEG). Indeed, it's so high-quality that it has only four gray shades in it (two white, two black) and is visibly flawless even to my eye.

Just for jollies, I converted your images to PNG (gif2png -s rwlock*.gif) and then ran them through pngcrush (pngcrush -brute -e -crb.png -rem alla rwlock*.png). Here are the results:

 44965 Jan 10 21:13 rwlockRCUupdate.jpg             // 24-bit, 504 x 350 (xfig)
  7266 Jan 10 21:10 rwlockRCUupdate.gif             // 3-bit palette
  3350 Jan 10 22:13 rwlockRCUupdate.png             // 4-bit palette (gif2png)
  2867 Jan 10 22:13 rwlockRCUupdate-crb.png         // 4-bit palette (pngcrush)

 45664 Jan 10 21:22 rwlockRCUperfwtPREEMPT.jpg      // 8-bit, 640 x 480 (gnuplot)
  4940 Jan 10 21:22 rwlockRCUperfwtPREEMPT.gif      // 1-bit palette
  3326 Jan 10 22:13 rwlockRCUperfwtPREEMPT.png      // 1-bit grayscale (gif2png)
  2967 Jan 10 22:13 rwlockRCUperfwtPREEMPT-crb.png  // 1-bit grayscale (pngcrush)

In short, more than a factor of 15 smaller than the JPEGs, yet perfect quality. (These are the kinds of images for which PNG was designed.)

Greg

[OT] JPEG + graphs == hideous

PaulMcKenney — Fri, 11 Jan 2008 05:35:06 +0000

Well, there certainly still are geographies where the bandwidth is quite restricted, so I cannot complain.

For xfig, how about this .gif, as opposed to the six-times-bigger .jpg?

For gnuplot, how about this .gif, as opposed to the nine-times-bigger .jpg?

Now I just have to remember to cut-and-paste from the right set of scripts for next time!

[OT] JPEG + graphs == hideous

roelofs — Fri, 11 Jan 2008 03:12:51 +0000

No apologies necessary! Sorry if I was a little strident, but this comes up over and over again, and it seemed like the time was ripe for a public-service announcement. ;-) (And while bandwidth is far less of an issue these days than it was 15 years ago, I'm still an efficiency geek. Why use 3 KB when 1 KB would suffice?)

Anyway, I'm most familiar with gnuplot, which has both "png" and "gif" terminal types; a simple set terminal png or set terminal gif command will select one of them, and you can set the filename with set out 'foo.png', for example. Then replot or whatever you normally do.

xfig is a vector editor that uses its own .fig format by default, but it can export to all sorts of things, including PNG and GIF, if you've got the requisite helper apps installed. I think I've used it about once--and more than a decade ago at that--but according to the manual, you just bring up the export menu and select "Language" (a.k.a. output format) from the dropdown at the top. Alternatively, you can set the Fig.exportLanguage resource in your .Xdefaults file. Or you could just save to PostScript and use Ghostscript to convert to PNG or GIF, or ps2pdf and your favorite PDF viewer, or use a screen-capture utility.

I haven't used GNOME's screenshot function and don't actually have a GNOME desktop handy anymore (Slackware dropped it :-) ), but I'd bet it's based on imlib2, which has had PNG support pretty much forever. Alternatively, if you've got PBMPLUS/NetPBM installed, you can do xwd -out foo.xwd (and click on relevant window) and then xwdtopnm foo.xwd | pnmtopng > foo.png (or similar). No doubt ImageMagick/GraphicsMagick are also capable of doing such conversions. And then there's XV, which I currently sort of maintain (for loose definitions of "maintain"); it's not Free software, but it's really well written and can capture screenshots and write them out in many formats.

Greg

[OT] JPEG + graphs == hideous

PaulMcKenney — Fri, 11 Jan 2008 01:24:56 +0000

(You have to understand that I started out doing character-graphics plots on machines that
didn't even support lower-case alphabetic characters.  So I cannot trust my own judgement and
aesthetics with these new-fangled bit-map plots.  Even the jpegs look wonderful to me!)

Reader-to-updater upgrade?

PaulMcKenney — Thu, 10 Jan 2008 21:02:12 +0000

1. Indeed, the upgrade-to-update change would be visible to the remainder of the RCU read-side
critical section.  However, in a surprisingly large number of cases, there is no need for
additional verification steps (though verification can be used when needed).  This is a key
difference between RCU and non-blocking synchronization (NBS) -- NBS would absolutely require
the validation steps in order to avoid memory corruption.

2. Good point -- although rcu_assign_pointer(head, NULL) is superfluous, it is good practice,
and there is no performance penalty.

3. Good eyes!!!

[OT] JPEG + graphs == hideous

PaulMcKenney — Thu, 10 Jan 2008 20:08:56 +0000

Please accept my apologies for the excessive bandwidth and low quality!  For my future
reference, if you have a recommended sequence of commands to get xfig, gnuplot, and Gnome's
screenshot capability to generate optimal images, please let me know.

Reader-to-updater upgrade?

jarkao2 — Thu, 10 Jan 2008 13:58:14 +0000

1. "However, a separate synchronization mechanism must be supplied to keep the writers from
destructively interfering with each other, as noted in the first list above."
Maybe I miss or repeat something, but serious downsize of this upgrade-to-write seems to be in
this possibly stale value of the search got as an RCU reader, which would always(?) require
additional verification.

2. This example:
"RCU is a Restricted Reference-Counting Mechanism
 [...]
 Regardless of these restrictions, the following code can safely delete p:

  1 spin_lock(&mylock);
  2 p = head;
  3 head = NULL;
  4 spin_unlock(&mylock);
  5 synchronize_rcu();  /* Wait for all references to be released. */
  6 kfree(p);
 [...]"
 
should probably promote rcu_assign_pointer() more...

3. "And" maybe one more tiny fix:
"RCU is a Bulk Reference-Counting Mechanism
 [...]
 starting and I/O and released [...]"

Many thanks!

[OT] JPEG + graphs == hideous

roelofs — Wed, 09 Jan 2008 22:11:26 +0000

Please avoid using JPEG for anything but continuous-tone or photographic images. Of the common image formats, it is, by far, the worst possible choice for simple graphics like your diagrams and graphs. (Use PNG or GIF instead.) Leaving aside the visible flaws (e.g., note the splotchy green boxes with black text), you're also necessarily increasing the data size by an order of magnitude before compressing it, and I'm not aware of any compression algorithm that can make up the difference--certainly JPEG can't. In other words, not only is the quality worse, the files are bigger, too.

Btw, in case it wasn't obvious--and it's not to some people--don't convert your JPEGs to PNG or GIF to do the comparisons; the damage is already done. Save to a lossless format from the start. Virtually all Linux graphing and diagramming tools support PNG natively, and most now support GIF again, too. (Also make sure you save to "8-bit"/colormapped PNG, not 24-bit/RGB; zlib can't recover from the 3x-12x increase in size any more than JPEG can.)

Greg

Reader-to-updater upgrade?

PaulMcKenney — Fri, 04 Jan 2008 17:28:24 +0000

Good question! As far as I know, the semantics of an RCU read-to-write upgrade have never been formalized. But the informal properties are well understood.

As a general rule, writers will serialize if necessary, but any such serialization will be entirely contained within the RCU read-side critical section. Therefore, a synchronize_rcu() call that started after a pair of upgrade-to-write RCU read-side critical sections would wait for the entire RCU read-side critical sections to complete, including the writes and any required write-side serialization.

However, the exact semantics will depend on the synchronization mechanism used by the writers. Here are some possibilities:

Writers use a single spinlock. This matches your second sentence: "all writers were serialized, and readers never block with respect to each others or writers". In addition, as you say, if a pair of RCU readers try to upgrade concurrently, one of them will go first and the other will spin waiting for the first to complete before starting its update. But both writers will complete unconditionally.
Writers use multiple spinlocks, for example, one spinlock per hash-table bucket. In this case, only writers accessing the same hash-table bucket will be serialized, and writers accessing different hash-table buckets can run in parallel.
Writers use atomic operations, for example, your atomic-increment example (assuming that I understand it correctly). In this case, as long as the atomic increments are being used correctly (all modifications to the variable in question are atomic, etc.), all the atomic operations on the variable will be serialized in hardware -- none of the atomic operations will be dropped.
Allow only a single designated task to perform updates. In this case, the reader would need to check to see if it was this designated task before doing the update. But because there is but one writer, no writer-to-writer serialization is required.

Of course, if the writers' synchronization is buggy, the overall algorithm will still be buggy. For example, suppose that writers atomically increment a given variable, but that readers (erroneously) non-atomically increment that same variable. Some of the writers' increments might be lost, just as they might be if you were not using RCU.

So the fundamental guarantees of RCU are those listed in What is RCU, Fundamentally?:

Subscribers see a completely-initialized version of published data structures.
The synchronize_rcu() primitive (and friends) will wait for all pre-existing readers to complete.
Providing multiple versions permits readers to safely run concurrently with updaters.

However, a separate synchronization mechanism must be supplied to keep the writers from destructively interfering with each other, as noted in the first list above.

Does this answer your question, or did I miss your point?

sample code buggy?

PaulMcKenney — Fri, 04 Jan 2008 16:53:17 +0000

Hmmm...  Too early in the morning, I guess.  Make that the two declarations of the pointer "p"
rather than "buf".  :-/

sample code buggy?

PaulMcKenney — Fri, 04 Jan 2008 16:50:45 +0000

Good catch!  As you no doubt guessed, s/atomic_t/struct profile_buffer/ in the declaration of
"buf".

Reader-to-updater upgrade?

jzbiciak — Thu, 03 Jan 2008 12:44:50 +0000

What exactly are the semantics of this unconditional reader-to-updater upgrade? I thought all writers were serialized, and readers never block with respect to each others or writers. Writers, once finished, updated the "current version" pointer atomically, so earlier readers see an older copy, and later readers and writers see a newer copy.

What happens when a reader wants to become an updater when another writer is already active? To me it seems like that that thread needs to get in line behind the existing writer.

For example, consider a monotonically increasing event counter, protected by RCU. All readers will see a monotonically increasing count. Writers, which must do a read-modify-write cycle to increment the count, work correctly as long as they serialize. What happens if a reader decides to write an incremented count all of the sudden? If there are other updaters in parallel, does the increment get dropped?

Am I misunderstanding the guarantees offered by RCU?

sample code buggy?

johill — Thu, 03 Jan 2008 10:46:47 +0000

The sample code looks a bit odd with

struct profile_buffer {
  long size;
  atomic_t entry[0];
};
static struct profile_buffer *buf = NULL;

[...]

atomic_t *p = buf;

Unless I'm totally misunderstanding something here it looks like the pointer assignment can't possibly be compatible?