Log in

Another year, another release of Is Parallel Programming Hard, And, If So, What Can You Do About It?!

Updates include:

  1. More formatting and build-system improvements, along with many bibliography updates, courtesy of Akira Yokosawa.
  2. A great many grammar and typo fixes from Akira and SeongJae Park.
  3. Numerous changes and fixes from Balbir Singh, Boqun Feng, Mike Rapoport, Praveen Kumar, and Tobias Klauser.
  4. Added code for concurrent skiplists, with the hope for added text in a later release.
  5. Added a running example to the deferred-processing chapter.
  6. Merged “Synchronization Primitives” into “Tools of Trade” section.
  7. Updated control-dependency discussion in memory-barriers section.
As always, git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git will be updated in real time.

Another great Linux Plumbers Conference!

A big “thank you” to the program committee, to the microconference leads, to the refereed-track speakers, and, most of all, to the attendees! We had a great Linux Plumbers Conference this year, and we could not have done it without all of you!!!
The Linux kernel community has been using Git for more than a decade, but it is still under active development, with more than 2,000 non-merge git commits from almost 200 contributor over the past year. Rather than review this extensive history, this Micro Git Together instead focuses on what the next few years might bring. In addtion, Junio will present on the state of the Git Union, Josh Triplett will present on the git-series project, and Steve Rostedt will present "A Maze Of Git Scripts All Alike", in which Steve puts forward the radical notion that common function in various maintainers' scripts could be pulled into git itself. This should help lead into a festive discussion about the future of git.

Please join us for an important and festive discussion!
Audio is an increasingly important component of the Linux plumbing, given increased use of Linux for media workloads and of the Linux kernel for smartphones. Topics include low-latency audio, use of the clock API, propagating digital configuration through dynamic audio power management (DAPM), integration of HDA and ASoC, SoundWire ALSA use-case managemer (UCM) scalability, standardizing HDMI and DisplayPort interfaces, Media Controller API integration, and a number of topics relating to the multiple userspace users of Linux-kernel audio, including Android and ChromeOS as well as the various desktop-oriented Linux distributions.

As with many Linux-kernel components, upstreaming of vendor drivers and handling of stable and long-term-stable (LTS) trees are also important topics.

Please join us for a timely and important discussion!
It has been more than a decade since CPU core clock frequencies stopped doubling every 18 months, which has shifted the search for performance from the "hardware free lunch" to concurrency and, more recently, hardware accelerators. Beyond accelerating computational offload, field-programmable gate arrays (FPGAs) and programmable logic devices (PLDs) have long been used in the embedded space to provide ways to offload I/O or to implement timing-sensitive algorithms as close as possible to the pin.

Regardless of how they are used, however, there exists a common class of problems which accompany the use of FPGAs, accelerators, and PLDs on Linux. Perhaps most important are the probing, discovery, and enumeration of these devices, which can be a challenge given the wide variety of interconnects to which they may be attached.

The purpose of this microconference is to discuss these problems, and figure out what it would take to make these devices first-class citizens on Linux. We will be looking at important use cases, including the much-maligned network-offload case as well as the more general topic of workload acceleration.

For more details on coherent accelerators, FPGAs, and PLDs, please see this microconference's wiki page.

We hope to see you there!
The refereed talk deadline for Linux Plumbers Conference is only a few weeks off, September 1, 2016 at 11:59PM CET. So there is still some time to get your proposals in, but time is growing short.

Note that this year's Plumbers is co-located with Linux Kernel Summit rather than LinuxCon, so the refereed track is all Plumbers this year. We are therefore looking forward to seeing your all-Plumbers refereed-track submission!

As you might have noticed, earlybird registration has closed, but normal-rate registration will be opening up on August 27th—however, accepted refereed speaking proposals will receive a free pass.

The conference itself is in Santa Fe, New Mexico on November 1-4, 2016. Looking forward to seeing you there!
Although trusted platform modules (TPMs) have been the subject of some controversy over the years, it is quite likely that they have important roles to play in preventing firmware-based attacks, protecting user keys, and so on. However, some work is required to enable TPMs to successfully play these roles, including getting TPM support into bootloaders, securely distributing known-good hashes, and providing robust and repeatable handling of upgrades.

In short, given the ever-more-hostile environments that our systems must operate in, it seems quite likely that much help will be needed, including from TPMs. For more details, see the TPMs Microconference wiki page.

We hope to see you there!
It might well be that wireless networking recently made the transition from an ubiquitous networking technology to the dominant networking technology, at least from the viewpoint of end-user devices. Part of this trend is the use of wireless in automobiles, and this workshop will look at Wireless Access in Vehicular Environments (WAVE), also know as IEEE 802.11p. In addition, the bufferbloat problem is starting to focus on the more difficult wireless environment, and to that end, this workshop will discuss FQ/Codel integration, testing, and development. As usual, the workshop will encompass the full 802.11 stack, not just the kernel portions, and therefore wpa_supplicant will also be on the agenda.

Please join us for a timely and important discussion!

Parallel Programming: July 2016 Update

This release of Is Parallel Programming Hard, And, If So, What Can You Do About It? has some really nice updates:



  1. PDFs now have hyperlinks from each quick quiz to its answer, and each answer has hyperlinks to its quick quiz, courtesy of Paolo Bonzini with refinements by Akira Yokosawa.
  2. People building from the git archive will see some excellent improvements in the build system, which now does a much better job of determining whether or not a rebuild is necessary, and is also much better at displaying the relevant LaTeX errors in case of build failure. These changes were courtesy of Akira Yokosawa, who also greatly improved formatting by introducing a number of recent LaTeX features and capabilities.
  3. The deferred-processing chapter now has a running example that more clearly shows the performance tradeoffs. The reference-counting section within this chapter now avoids forward references, and the information about combining reference counting with other techniques now appears in the later putting-it-all-together chapter.
  4. The code samples were updated to eliminate a number of compiler warnings.
  5. SeongJae Park's translation efforts resulted in a number of fixes to the English version's spelling and grammar, and Akira made substantial contributions in this area as well.
  6. Andreea-Cristina Bernat, Andrew Donnellan, Balbir Singh, Dave Willmer, Dominik Dingel, Emilio G. Cota, and Namhyung Kim also provided many much-appreciated contributions.
As always, git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git will be updated in real time.

Stupid RCU Tricks: An Early-1970s Example

Up to now, I have been calling out Kung's and Lehman's classic 1980 “Concurrent Manipulation of Binary Search Trees” as the oldest mention of something vaguely resembling RCU.

However, while looking into the history of reference counting, I found Weizenbaum's postively antique 1963 “Symmetric List Processor (SLIP)”, which describes a list-processing library, written in FORTRAN, no less. One of its features was storage reclamation based on reference counting, in which newly reclaimed list items are added to the end of SLIP's list of available space.

And, on page 413 of his 1973 “The Art of Computer Programming: Fundamental Algorithms”, none other than Donald Knuth points out that this add-at-end implementation means that “incorrect programs run correctly for awhile”. Here, “incorrect programs” is presumably referring to readers traversing SLIP lists while failing to increment the needed SLIP reference counters.

So it is that the earliest known mention of RCU-based algorithms dismisses them all as buggy. And rightfully so, given that SLIP has no notion of anything like a grace period. Thus, Kung and Lehman remain the first known implementers of something vaguely resembling RCU—but no longer the first mention!