Log in

No account? Create an account
Testing, fuzzing, and other diagnostics have greatly increased the robustness of the Linux ecosystem, but embarrassing bugs still escape to end users. Furthermore, a million-year bug would happen several tens of times per day across Linux's installed base (said to number more than 20 billion), so the best we can possibly do is hardly good enough.

The Testing and Fuzzing Microconference intends to raise the bar with further progress on syzbot/syzkaller, distribution/stable testing, kernel continuous integration, and unit testing. The best evidence of progress in these efforts will of course be the plethora of bug reports produced by these and similar tools!

Join us for an important and spirited discussion!
We are pleased to announce that the RDMA Microconference has been accepted into the 2018 Linux Plumbers Conference!

RDMA (remote direct memory access) is a well-established technology that is used in environments requiring both maximum throughputs and minimum latencies. For a long time, this technology was used primary in high-performance computing, high frequency trading, and supercomputing. For example, the three most powerful computers are based on Linux and RDMA (in the guise of Infiniband).

However, the latest trends in cloud computing (more bandwidth at larger scales) and storage (more IOPS) makes RDMA increasingly important outside of its initial niches. Therefore, clean integration between RDMA and various kernel susbsystems is paramount. We are therefore looking to build on previous years' successful RDMA microconferences, this year discussing our 2018-2019 plans and roadmap.

Topics proposed for this year's event include the interaction between RDMA and DAX (direct access for files), how to solve the get_user_pages() problem (see https://lwn.net/Articles/753027/ and https://lwn.net/Articles/753272/), IOMMU and PCI-E issues, continuous integration, python integration, and Syzkaller testing.
There was a time when I felt that Linux-kernel RCU was too low-level to possibly be the subject of a security exploit, but Rowhammer put paid to that naive notion. And it finally happened earlier this year. Now, I could claim that I did nothing wrong. After all, RCU worked as advertised. The issue was instead that RCU has multiple flavors:


  1. RCU-bh for code that is subject to network-based denial-of-service attacks.
  2. RCU-sched for code that must interact with interrupt/NMI handlers or with preemption-disabled regions of code, and for general-purpose use in CONFIG_PREEMPT=n kernels.
  3. RCU-preempt for general-purpose use in CONFIG_PREEMPT=y kernels.

The real problem was that someone used one flavor in one part of their RCU algorithm, and another flavor in another part. This has roughly the same effect on your kernel's health and well-being as does acquiring the wrong lock. And, as luck would have it, the resulting bug proved to be exploitable. To his credit, Linus Torvalds noted that having multiple RCU flavors was a root cause, and so he asked that I do something to prevent future similar security-exploitable confusion. After some discussion, it was decided that I try to merge the three flavors of RCU into “one flavor to rule them all”.

Which I have now done in the relative privacy of my -rcu git tree (as in “git clone https://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git” followed by “git checkout dev”).

So what has this got to do with validation in general or formal verification in particular?

Just this: Over the past few months, I have taken a meataxe to Linux-kernel RCU, which implies the injection of any number of bugs. If you would like your formal-verification tool/methodology to be the first to find a bug in Linux-kernel RCU that I don't already know about, this would be an excellent time to give it a try. And yes, all those qualifiers are necessary, as several groups have used formal-verification tools to find bugs in Linux-kernel RCU that I did already know about.

More generally, given the large number of swings I took with said meataxe, if your formal verification tool cannot find bugs in the current dev version of RCU, you might need to entertain the possibility that your formal verification tool cannot find bugs!
The -rcu tree also takes LKMM patches, and I have been handling these completely separately, with one branch for RCU and another for LKMM. But this can be a bit inconvenient, and more important, can delay my response to patches to (say) LKMM if I am doing (say) extended in-tree RCU testing. So it is time to try something a bit different.

My current thought is continue to have separate LKMM and RCU branches (or more often, sets of branches) containing the commits to be offered up to the next merge window. The -rcu branch lkmm would flag the LKMM branch (or, more often, merge commit) and a new -rcu branch rcu would flag the RCU branch (or, again more often, merge commit). Then the lkmm and rcu merge commits would be merged, with new commits on top. These new commits would be intermixed RCU and LKMM commits.

The tip of the -rcu development effort (both LKMM and RCU) would be flagged with a new dev branch, with the old rcu/dev branch being retired. The rcu/next branch will continue to mark the commit to be pulled into the -next tree, and will point to the merge of the rcu and lkmm branches during the merge window.

I will create the next-merge-window branches sometime around -rc1 or -rc2, as I have in the past. I will send RFC patches to LKML shortly thereafter. I will send a pull request for the rcu branch around -rc5, and will send final patches from the lkmm branch at about that same time.

Should continue to be fun! :–)
Referred-track, microconference, and BoF proposals all welcome, see below!

Submissions close: September 2, 2018
Speakers notified: September 23, 2018
Slides due: November 9, 2018

Microconference slots often fill before the deadline (so don't wait to submit yours!) but BoF submissions can come late.

Call for Refereed-Track Proposals

We are pleased to announce the Call for Refereed-Track Proposals for the 2018 edition of the Linux Plumbers Conference, which will held be in Vancouver, BC, Canada on November 13-15 in conjunction with the Linux Kernel Summit.

Refereed track presentations are 50 minutes in length (which includes time for questions and discussion) and should focus on a specific aspect of the "plumbing" in the Linux system. Examples of Linux plumbing include core kernel subsystems, toolchains, container runtimes, core libraries, windowing systems, management tools, device support, media creation/playback, and so on. The best presentations are not about finished work, but rather problems, proposals, or proof-of-concept solutions that require face-to-face discussions and debate.

Given that Plumbers is not colocated with Open Source Summit this year, we are spreading the refereed-track talks over all three days. This provides a change of pace and also provides a conflict-free schedule for the refereed-track talks. (Yes, this does result in more conflicts between the refereed-track talks and the Microconferences, but we never claimed that the world was perfect.)

Linux Plumbers Conference Program Committee members will be reviewing all submitted sessions. High-quality submisssion that cannot be accepted due to the limited number of slots will be forwarded to the Microconference leads for further consideration. We also encourage submitters to consider BoF sessions and the unconference.

To submit a refereed track talk proposal follow the instructions at this website.

Please note that we have a completely different submission system than last year, so please do not let your muscle memory take over.

Submissions are due on or before Friday September 2, 2018 at noon Mountain Time. Since this is after the closure of early registration, speakers may register before this date and we'll refund the registration for any selected presentation's speaker, but for only one speaker per presentation.

Call for Microconference Proposals

We are pleased to announce the Call for Microconferences for the 2018 edition of the Linux Plumbers Conference, which will be held in Vancouver BC, Canada on November 13-15 in conjunction with the Linux Kernel Summit.

A microconference is a collection of collaborative sessions focused on problems in a particular area of the Linux plumbing, which includes the kernel, libraries, utilities, UI, and so forth, but can also focus on cross-cutting concerns such as security, scaling, energy efficiency, toolchains, container runtimes, or a particular use case. Good microconferences result in solutions to these problems and concerns, while the best microconferences result in patches that implement those solutions. For more information on submitting a microconference proposal, see this website.

Again, please note that we have a completely different submission system than last year, so please do not let your muscle memory take over. In particular, unlike last year, there is no wiki. So instead of creating an entry for you microconference on a wiki, you submit it using the above URL.

Call for Bird of a Feather (BoF) Session Proposals

Last, but by no means least, we are also pleased to announce a call for BoF sessions. These are free-form get-togethers for people wishing to discuss a particular topic. As always, you only need to submit proposals for BoFs you want to hold on-site. In contrast, and again as always, informal BoFs may be held at local drinking establishments or in the “hallway track” at your convenience.

A Linux-kernel memory model!

A big “thank you” to all my partners in LKMM crime, most especially to Jade, Luc, Andrea, and Alan! Jade presented our paper (slides, supplementary material) at ASPLOS, which was well-received. A number of people asked how they could learn more about LKMM, which is what much of this blog post is about.

Approaches to learning LKMM include:

  1. Read the documentation, starting with explanation.txt. This documentation replaces most of the older LWN series.
  2. Go through Ted Cooper's coursework for Portland State University's CS510 Advanced Topics in Concurrency class, taught by Jon Walpole.
  3. Those interested in the history of LKMM might wish to look at my 2017 linux.conf.au presentation (video).
  4. Play with the actual model.
The first three options are straightforward, but playing with the model requires some installation. However, playing with the model is probably key to gaining a full understanding of LKMM, so this installation step is well worth the effort.

Installation instructions may be found here (see the “REQUIREMENTS” section). The ocaml language is a prerequisite, which is fortunately included in many Linux distros. If you choose to install ocaml from source (for example, because you need a more recent version), do yourself a favor and read the instructions completely before starting the build process! Otherwise, you will find yourself learning of the convenient one-step build process only after carrying out the laborious five-step process, which can be a bit frustrating.

Of course, if you come across better methods to quickly, easily, and thoroughly learn LKMM, please do not keep them a secret!

Those wanting a few rules of thumb safely approximating LKMM should look at slide 96 (PDF page 78) of the aforementioned linux.conf.au presentation. Please note that material earlier in the presentation is required to make sense of the three rules of thumb.

We also got some excellent questions during Jade's ASPLOS talk, mainly from the renowned and irrepressible Sarita Adve:

  • Question: How do we know that the model is correct?
    Answer: We verified the model socially and experimentally. [ Ed. note: See Section 1 and Table 5 of the paper and the “Detailed hardware results” from the supplementary materials. ]
  • Question: What is the intuition behind the model?
    Answer: There are a number of axioms, for example, the RCU axiom, that correspond to various intuitions. Additional axioms correspond to the load buffering and store buffering intuitions.
  • Question: How did you decide what to provide? For example, what about one of Paul's favorite primitives, sequence locking?
    Answer: The paper shows memory barrier, loads and stores, acquire and release, and read-modify-write atomic operations. We have since added locking, which in combination with some of the other operations allows sequence locking to be easily implemented within litmus tests. [ Ed. note: Not sure that sequence locking makes my list of favorites, but we do have a pair of sequence-locking litmus tests in preparation. ]
There were of course a great many other excellent presentations at ASPLOS, but that is a topic for another post!

Exit Libris

I have only so many bookshelves, and I have not yet bought into ereaders, so from time to time books must leave. Here is the current batch:

  • 50 Simple Ways to Save Your House, Bruce Johnson. Yes, I did get this book before Youtube was invented. Why do you ask?
  • Algorithms to Live By: The Computer Science of Human Decisions, Brian Christian and Tom Griffiths. An OK introduction to probability and related ideas, but I am keeping Taleb's Incerto series in preference over this one. Oh, and Feller's classic textbooks as well.
  • Animals of East Africa, Louis S. B. Leakey. A book from my childhood, but time to let it go.
  • Edge of a Continent: The Pacific Coast from Alaska to Baja, Don Greame Kelley. Rossi & David C. Hunt. A book from my childhood, but time to let it go.
  • Freedom Manifesto: Why Free Markets are Moral and Big Government Isn't, Steve Forbes and Elizabeth Ames. If you read the title and say “But of course!”, you should avoid this book. But if you choke and sputter at the title, you should most definitely read this book. ;–)
  • Indian & Eskimo Artifacts of North America, Charles Miles. A book from my childhood, but time to let it go.
  • Just for Fun: The Story of an Accidental Revolutionary, Linus Torvalds and David Diamond. This is the hardback. The paperback takes less space, plus it is autographed. And I won the paperback in a coding contest at a long-ago linux.conf.au!
  • Leadership and Crisis, Bobby Jindal. Not everyone's cup of tea, but worth it for the anecdote about career day. You see, his son was bitterly disappointed that his dad was merely the governor of Louisiana instead of something really cool, like a policeman or fireman.
  • New Complete Do-It-Yourself Manual, Reader's Digest. Yes, I did get this book before Youtube was invented. Why do you ask?
  • Our Culture, What's Left of it, Theodore Dalrymple. His “Life at the Bottom” is a classic and worthwhile old-man rant, but this sequel suffers a bit by comparison.
  • Patent Failure: How Judges, Bureaucrats, and Lawyers Put Innovators at Risk, Jesse Bessen & Michael J. Meurer.
  • Plato, Not Prozac! Applying Eternal Wisdom to Everyday Problems, Lou Marinoff. I have no problem with Plato being considered better than prozac, but exercise works even better for me. Not bad as an introduction to various schools of philosophy, but I prefer “Plato and a Platypus Walk into a Bar... Understanding Philosophy Through Jokes”. Not that I can rattle off any of the schools of philosophy, so maybe I am just a philistine.
  • Snoop: What Your Stuff Says About You, Sam Gosling.
  • The Art of the Old West, Paul A. Rossi & David C. Hunt. A book from my childhood, but time to let it go.
  • The Halo Effect: How Managers Let Themselves be Deceived, Phil Rosenweig. A good book, though I never did figure the focus on managers in the title. Seems to me to apply to everyone.
  • The Hunger Games, Suzanne Collins.
  • The Inscrutable Americans, Anurag Mathur. Adventures at an American University for a kid from India.
  • The Lexus and the Olive Tree: Understanding Globalization, Thomas L. Friedman. Not a bad read, but a bit dated. Also, it seemed to me that he had traveled the world, but not so much his own country.
  • The Liberty Amendments, Mark R. Levin. If you feel the urge to run out and amend the USA constitution, you might want to read a few books like this one first. You see, other people just might have rather different ideas than you as to which direction the amendments should go.
  • The Millionaire Mind, Thomas J. Stanley. OK, but suffers from the sequel effect: “The Millionaire Next Door” is much better.
  • The Will to Meaning, Viktor E. Frankl. Actually not at all bad, but suffers by comparison to “Man's Search for Meaning”.
  • Tomorrow's Table: Organic Farming, Genetics, and the Future of Food, Pamela C. Ronald & Raoul W. Adamchak. A good thing to read if you labor under the delusion that farming is trivial. But I grew up in a farming community, so...

It is a bit sad to abandon some old friends, but such is life with physical books!


2017 Year-End Advice

One of the occupational hazard of being an old man is the urge to provide unsolicited advice on any number of topics. This time, the topic is weight lifting.

Some years ago, I decided to start lifting weights. My body no longer tolerated running, so I had long since substituted various low-impact mechanical means of aerobic exercise. But there was growing evidence that higher muscle mass is a good thing as one ages, so I figured I should give it a try. This posting lists a couple of my mistakes, which could enable you to avoid them, which in turn could enable you to make brand-spanking new mistakes of your very own design!

The first mistake resulted in sporadic pains in my left palm and wrist, which appeared after many months of upper-body weight workouts. In my experience, at my age, any mention of this sort of thing to medical professionals will result in a tentative diagnosis of arthritis, with the only prescription being continued observation. This experience motivated me to do a bit of self-debugging beforehand, which led me to notice that the pain was only in my left wrist and only in the center of my left palm. This focused my attention on my two middle fingers, especially the one on which I have been wearing a wedding ring pretty much non-stop since late 1985. (Of course, those prone to making a certain impolite hand gesture might have reason to suspect their middle finger.)

So I tried removing my wedding ring. I was unable to do so, even after soaking my hand for some minutes in a bath of water, soap, and ice. This situation seemed like a very bad thing, regardless of what might be causing the pain. I therefore consulted my wife, who suggested a particular jewelry store. Shortly thereafter, I was sitting in a chair while a gentleman used a tiny but effective hand-cranked circular saw to cut through the ring and a couple pairs of pliers to open it up. The gentleman was surprised that it took more than ten turns of the saw to cut through the ring, in contrast to the usual three turns. Apparently wearing a ring for more than 30 years can cause it to work harden.

The next step was for me to go without a ring for a few weeks to allow my finger to decide what size it wanted to be, now that it had a choice. They gave me back the cut-open ring, which I carried in my pocket. Coincidence or not, during that time, the pains in my wrists and palms vanished. Later, jewelry store resized the ring.

I now remove my ring every night. If you take up any sort of weight lifting involving use of your hands, I recommend that you also remove any rings you might wear, just to verify that you still can.

My second mistake was to embark upon a haphazard weight-lifting regime. I felt that this was OK because I wasn't training for anything other than advanced age, so that any imbalances should be fairly easily addressed.

My body had other ideas, especially in connection with the bout of allergy/asthma/sinitus/brochitis/whatever that I have (knock on wood) mostly recovered from. This condition of course results in coughing, in which the muscles surrounding your chest work together to push air out of your lungs as abruptly and quickly as humanly possible. (Interestingly enough, the maximum velocity of cough-driven air seems to be subject to great dispute, perhaps because it is highly variable and because there are so many different places you could measure it.)

The maximum-effort nature of a cough is just fine if your various chest muscles are reasonably evenly matched. Unfortunately, I had not concerned myself with the effects of my weight-lifting regime on my ability to cough, so I learned the hard way that the weaker muscles might object to this treatment, and make their objections known by going into spasms. Spasms involving one's back can be surprisingly difficult to pin down, but for me, otherwise nonsensical shooting pains involving the neck and head are often due to something in my back. I started some simple and gentle back exercises, and also indulged in Warner Brothers therapy, which involves sitting in an easy chair watching Warner Brothers cartoons, assisted by a heating pad lent by my wife.

In summary, if you are starting weight training, (1) take an organized approach and (2) remove any rings you are wearing at least once a week.

Other than that, have a very happy new year!!!
I believe that Charles T. Porter's “Engineering Reminiscences“ was a gift from my grandfather, who was himself a machinist. Porter's most prominent contribution was the high-speed steam engine, that is to say, a steam engine operating at more than about 100 RPM. Although steam engines and their governors proved to be somewhat of a dead end, some of his dynamic balancing techniques are still in use.

Technology changes, people and organizations not so much. Chapter XVII starting on page 189 describes a demonstration of two of his new high-speed steam engines (on operating at 150 RPM the other at 300 RPM) along with one of his colleague's new boilers at the 1870 Fair of the American Institute in New York. The boiler ran slanted water tubes through the firebox to more efficiently separate steam from the remaining water. The engines were small by 1870s standards, one having 16-inch diameter cylinders with a 30-inch stroke and the other having 6-inch diameter cylinders with a 12-inch stroke.

Other exhibitors also had boilers and steam engines, and yet other exhibitors had equipment driven by steam engines. All the boilers and steam engines where connected, but given that steam engines were, then as now, considered to be way cooler than mere boilers, it should not be too surprising that the boilers could not produce enough steam to keep all the engines running. In fact, by the end of the day, the steam pressure had dropped by half, resulting in great consternation and annoyance all around. The finger of suspicion quickly pointed at Porter's two high-speed steam engines—after all, great speed clearly must imply equally great consumption of steam, right?

Porter had anticipated this situation, and had therefore installed a shutoff valve that isolated the boiler and his two high-speed steam engines from the rest of the Fair's equipment. Porter therefore closed his valve, with the result that the steam pressure within his little steam network immediately rose to 70 PSI and the pressure to the rest of the network dropped to 25 PSI. In fact, the boiler generated excess steam even at 70 PSI, so that the fireman had to leave the firebox door slightly open to artificially lower the boiler temperature.

The steam pressure to the rest of the fair continued to decrease until it was but 15 PSI. Over the noon hour, an additional boiler was installed, which brought the pressure up to 70 PSI. Restarting the steam engines of course reduced the pressure, but at 5PM it was still 25 PSI.

The superintendent of the machinery department had repeatedly asked Porter to reopen the valve, but each time Porter had refused. At 5PM, the superintendent made it clear that his request was now a demand, and that if Porter would not open the valve, the superintendent would open it for him. Porter finally agreed to open the valve, but only on the condition that the other managers of the institute verify that the boiler was in fact generating more than enough steam for both engines. These managers were summoned forthwith, and they agreed that the boiler had been producing most of the show's steam and that the pair of high-speed steam engines had been consuming very little. Porter opened the valve, and there was no further trouble with low-pressure steam.

It is all too easy to imagine a roughly similar story unfolding in today's world. ;–)

Porter went on to develop steam engines capable of running well in excess of 1,000 RPM, with one key challenge being convincing onlookers that the motion-blurred engine really was running that fast.

Interestingly enough, steam engines were Porter's third career. He was a lawyer for several years, but became disgusted with legal practice. At about that same time, he became quite interested in the problem of facing stone, that is, producing a machine that would take a rough-cut stone and give it a smooth planar face (smooth by the standards of the mid-1800s, anyway). After a couple of years of experimentation, he produced a steam-powered machine that efficiently faced stone. Unfortunately, at about that same time, others realized that saws could even more efficiently face stone, so his invention was what we might now call a technical success and a business failure.

Oddly enough, we have recently learned that the application of saws to stone was not an invention of the mid-1800s, but rather a re-invention of a technique used heavily in the ancient Roman Empire, and suspected of having been used as early as the 13th century BC. This is one of many interesting nuggets on life in the Roman Empire brought out by the historical novel “Tears of Stone” by Vannoy and Zeiglar. This novel is informed by Zeigler's application of Cold War remote-sensing technology to interesting areas of the Italian landscape, a fact that I had the privilege of learning directly from Zeigler himself.

On the other hand, perhaps Porter's ghost can console himself with the fact that the earliest stone saws were hand-powered, and those of the Roman Empire were water powered. Porter's stone-facing machine was instead powered by modern steam engines. Yes, the ancient Egyptians also made some use of steam power, but as far as we know they never applied it industrially, and never via a reciprocating engine driving a rotary shaft. And yes, all of the qualifiers in the preceding sentence are necessary.

As we learn more about ancient civilizations, it will be interesting to see what other “modern inventions” turn out to have deep roots in ancient times!


Book review: "Make Trouble"

This book, by John Waters of “Hairspray” fame, was an impulse purchase. After all, who could fail to notice a small pink book with large white textured letters saying “Make Trouble”? It is a transcription of Waters's commencement address to the Rhode Institute School of Design's Class of 2015. Those who have known me over several decades might be surprised by this purchase, but what old man could resist a book whose flyleaf states “Anyone embarking on a creative path, he tells us, would do well to realize that pragmatism and discipline are as important as talent and that rejection is nothing to fear.”

They might be even more surprised that I agree with much of his advice. For but three examples:

  1. “A career in the arts is like a hitchhiking trip: All you need is one person to say ‘get in,’ and off you go.” Not really any different from my advising people to use the “high-school boy” algorithm when submitting papers and proposals.
  2. “Keep up with what's causing chaos in your field.” Not really any different from my “Go where there is trouble!”
  3. “Listen to your political enemies, particularly the smart ones”. Me, I would omit the word “political”, but close enough.
The book is mostly pictures, so if you are short of money, you do have the option of just reading it in the bookstore. See, I am making trouble already! ;–)