The foothill wildflowers are more subdued than the ones that will cover the big mountains in July and August.

Four mountain ranges and the Great Salt Lake.

Looking down at the university.

I stopped a little below 7000′ and sat on a rock for 45 minutes waiting for sunset.

It was full night by the time I got home; should have brought a headlamp!

Recently I’ve started to notice a pattern where students who are having trouble getting their code to work often have not done enough procedural decomposition. That is, they have failed to appropriately break up a large, difficult programming problem into a collection of smaller ones. You are probably thinking to yourself that this is pretty basic stuff, and perhaps it is when we’re solving easy problems. On the other hand, I’ve come to believe that procedural decomposition for hard problems is probably one of those skills that we can keep getting better at for as long as we care to keep writing code.

An Example

In my operating systems class this spring, I asked the students to do a bit of hacking on Linux’s driver for the Minix filesystem. The Minix FS is a reasonable starting point because it’s about as simple as realistic filesystems get. The assignment was to change the code so that instead of representing a file as a tree of disk block numbers, a file is represented as a list of extents. An extent is a collection of contiguous disk blocks that can be represented as a (base, length) pair. For purposes of this assignment, we make the unrealistic assumption that indirect extents are not needed.

The crux of this assignment was rewriting the Minix FS driver’s get_block() function, which finds a block of a file on the disk and then maps it into the block cache; this is nontrivial because the requested block must be created if it doesn’t already exist (and a “create” flag is set). My first attempt at get_block() — as well as many students’ first attempts — was a monolithic function. However, the logic turns out to be just hairy enough that this is difficult to get right. On the other hand, the job can be broken down into several pieces:

• tiny utility functions for packing and unpacking the (base, length) pairs that are used to represent extents on disk
• a lookup function that finds a block of a file in the extent list if it exists, and fails otherwise
• an “extend file” function that makes a file bigger either by one block or by a specified number of blocks

Once these are available, get_block() needs only about a dozen lines of code. The tricky thing isn’t figuring out this particular decomposition — which is kind of obvious — but rather recognizing that it’s time to think about breaking up the problem rather than attacking it all at once. The temptation to keep banging on a function that seems to be almost correct is strong.

What’s Going On?

I asked some colleagues: Are we teaching procedural decomposition? And are we doing a good job? Well, of course we are teaching this and in fact one of the people who does that here, Matthew Flatt, is an author of How To Design Programs, one of the best books I know of for teaching abstraction and decomposition (and it’s free). But even so, the fact remains that in upper-division classes I’m getting a good number of students who are not performing procedural decomposition even in a situation where it is clearly necessary.

Since I’ve started thinking about procedural decomposition more, I’ve noticed that I don’t do enough of it either. When I catch myself writing poorly abstracted code, I try to analyze what I’m thinking and usually it boils down to a mixture of laziness (“if I can just get this stupid function to work, I won’t have to figure out how to break it up into pieces”) and overconfidence in my ability to deal with a complex case analysis all at once. I’m guessing that similar things are going on in students’ heads.

The purpose of the rest of this piece is to take a closer look at procedural decomposition and how we might be able to do a better job teaching it. But first, a quick note about terminology: the thing I’m calling procedural decomposition is also sometimes referred to as procedural abstraction, functional abstraction, or functional decomposition.

Reuse Isn’t the Main Thing

I think a lot of us were taught that the main reason we break code into functions is to facilitate reuse. In this view, we primarily write quicksort as a separate function so that we can call it from multiple locations in our program. It’s usually not too hard to notice when this kind of decomposition is necessary: we just get tired of writing quicksort from scratch after the second or third time. In contrast, procedural decomposition of a single problem is more difficult because it’s not as obvious where to introduce abstraction.

Decomposition and Problem Difficulty

I sometimes notice myself doing a much nicer job of procedural decomposition when solving simple problems than when solving complex ones. Of course if I were programming rationally it would be the other way around. Perhaps this effect can be understood by saying that I have a fixed amount of brain power to devote to a programming problem. In this case, when I’m totally overwhelmed by complexity I have no resources left for the added burden of figuring out how to best perform procedural decomposition. Of course, once I step back, delete some code, and find a good decomposition, I can surmount some sort of complexity barrier and probably find a nice landscape of simple code on the other side.

Years ago I heard Randy Pausch gave a talk describing how people who tried to fly a virtual magic carpet were overwhelmed by the many degrees of freedom offered by a prototype version of the controls. In order to simplify the situation, they left the carpet’s throttle at the maximum setting. This reduced the degrees of freedom by one, but with the unfortunate side effect of causing them to careen stupidly through the game running into everything. It seems like this might be a good analogy for how many of us approach a difficult programming problem.

Decomposition and Language Choice

There’s clearly a link between procedural decomposition and programming language choice. For example, I learned to program in early microcomputer BASIC dialects (TI BASIC, GW-BASIC, and Applesoft BASIC) where the support for procedural abstraction was not even as good as it is in assembly language. I sometimes fear that spending a few formative years writing BASIC may have stunted my capacity for abstraction.

One of the things that made the old BASIC implementations such turds is that they had no support for creating multiple namespaces. C is better, but the lack of nested functions and multiple return values can make it hard to perform elegant procedural decomposition there. C++ and Java don’t support nested functions either, but the object model seems to approximate them well enough for practical purposes. Modern languages with tuples, nested functions, and first-class functions seem to offer the best support for procedural decomposition.

Historically, we were discouraged from performing too much procedural decomposition because function calls added overhead. C/C++ programmers have been known to write horrific macros in order to get decomposition without increasing runtime. The modern wisdom — regardless of programming language — is that any performance-oriented compiler will do a pretty good job inlining functions that are small and that don’t have a ton of call sites. When the compiler has good dynamic information, such as a JIT compiler or an AOT compiler with access to profile data, it can do a considerably better job. However, even an AOT compiler without profile data can often do pretty well given good heuristics and perhaps some hints from developers. In any case, the days of allowing performance considerations to influence our procedural decomposition are mostly over.

Teaching Procedural Decomposition

I think that too often, our programming assignments are so canned that a solid grasp of procedural abstraction isn’t necessary to solve them. Moreover, we tend to not do a great job of grading on code quality — and of course the students are allowed to throw away their code after handing it in, so they have little incentive to do real software engineering. Of course there are plenty of students who write very good code because they can, and out of a general sense of pride in their work. But they’re not the ones I’m talking about trying to help here.

Maybe something we need to do is help students learn to recognize the danger signs where the complexity of a piece of code is starting to get out of control. Personally, I get sort of a panicky feeling where I become more and more certain that each fix that I add is breaking something else. I hate this so much that it’s making my skin prickle just writing about it. Usually, the best thing to do when this happens is step back and rethink the structure of the code, and probably also delete a bunch of what’s already written.

Finally, we probably need to do more code reading in classes. This is difficult or impossible for a large class, but probably can be done well with up to 10 or 15 students. As a random example, the Minix FS module for Linux kernel contains a rather nice decomposition of the functionality for managing the block tree for each file.

If the cost of memory safety bugs in C/C++ codes is significant, and if solutions are available, why aren’t we using them in production systems?

Here’s a previous blog post on the subject and a quick summary of the possible answers to my question:

• The cost of enforcement-related slowdowns is greater than the cost of vulnerabilities.
• The cost due to slowdown is not greater than the cost of vulnerabilities, but people act like it is because the performance costs are up-front whereas security costs are down the road.
• Memory safety tools are not ready for prime time for other reasons, like maybe they crash a lot or raise false alarms.
• Plain old inertia: unsafety was good enough 40 years ago and it’s good enough now.

I’m returning to this topic for two reasons. First, there’s a new paper SoK: Eternal War in Memory that provides a useful survey and analysis of current methods for avoiding memory safety bugs in legacy C/C++ code. (I’m probably being dense but can someone explain what “SoK” in the title refers to? In any case I like the core war allusion.)

When I say “memory safety” I’m referring to relatively comprehensive strategies for trapping the subset of undefined behaviors in C/C++ that are violations of the memory model and that frequently lead to RAM corruption (I say “relatively comprehensive” since even the strongest enforcement has holes, for example due to inline assembly or libraries that can’t be recompiled). The paper, on the other hand, is about a broader collection of solutions to memory safety problems including weak ones like ASLR, stack canaries, and NX bits that catch small but useful subsets of memory safety errors with very low overhead.

The SoK paper does two things. First, it analyzes the different pathways that begin with an untrapped undefined behavior and end with an exploit. This analysis is useful because it helps us understand the situations in which each kind of protection is helpful. Second, the paper evaluates a collection of modern protection schemes along the following axes:

• protection: what policy is enforced, and how effective is it at stopping memory-based attacks?
• cost: what is the resource cost in terms of slowdown and memory usage?
• compatibility: does the source code need to be changed? does it need to be recompiled? can protected and unprotected code interact freely?

As we might expect, stronger protection generally entails higher overhead and more severe compatibility problems.

The second reason for this post is that I’ve reached the conclusion that 30 years of research on memory safe C/C++ should be enough. It’s time to suck it up, take the best available memory safety solution, and just turn it on by default for a major open-source OS distribution such as Ubuntu. For those of us whose single-user machines are quad-core with 16 GB of RAM, the added resource usage is not going to make a difference. I promise to be an early adopter. People running servers might want to turn off safety for the more performance-critical parts of their workloads (though of course these might be where safety is most important). Netbook and Raspberry Pi users probably need to opt out of safety for now.

If the safe-by-default experiment succeeded, we would have (for the first time) a substantial user base for memory-safe C/C++. There would then be an excellent secondary payoff in research aimed at reducing the cost of safety, increasing the strength of the safety guarantees, and dealing with safety exceptions in interesting ways. My guess is that progress would be rapid. If the experiment failed, the new OS would fail to gain users and the vendor would have to back off to the unsafe baseline.

Please nobody leave a comment suggesting that it would be better to just stop using C/C++ instead of making them safe.

• the external view of the code: documentation, comments, APIs, white papers, information from developers, etc.
• the static view: reading the code like a book
• the dynamic view: reading the code as it executes, probably with help from a debugging tool

Of course these aren’t totally exclusive. For example, reading code like a book has a dynamic aspect because our brains serve as crude interpreters.

External View

Ideally we’ll be able to focus on a module that is small enough to understand all at once and that has relatively clean interfaces to the rest of the system. If the code seems too big or complicated to understand as a whole, perhaps it can be broken up. If the modularity that we want just isn’t there, we may be stuck trying to understand a piece of functionality that is buried is an ocean of complexity—not very fun.

We should be explicit about our goals. Are we reading the code for general enlightenment? In order to decide whether to hire the person who wrote the code? In order to begin refactoring or adding functionality? To look for bugs? Keep in mind that if we’re looking for bugs, code reviews are a whole separate thing.

Before reading any code we’ll certainly want to look over any documentation and also skim the comments in the code: sometimes there’s halfway-decent documentation hiding in the middle of a big source file. If the code is very well-known, like the Linux kernel, there’ll be plenty of books and web pages for us to look at. If not, perhaps there’s a specification, a white paper, a README, or similar. Often, even if there’s no documentation, the code will be implementing known algorithms that we can brush up on. Some kinds of domain-specific codes (signal processing, feedback control, storage management) will be very hard to understand if we lack basic domain knowledge, so again we may need to hit the books for a little while before getting back to the code.

Often it’s a good idea to build and run the code before starting to read it, or at least be sure that someone else has done it. This is because we often run across attractive-looking open source code on the web that isn’t worth reading because it’s not even finished—we might as well discover that fact as early as possible. Just the other day I got suckered by a Github project that promised to do exactly what I wanted, but that was badly broken.

Static View

Reading code is far easier if we come into it with an understanding of the patterns that are being used. Therefore, we can expect that in any given domain the first few pieces of code we read are going to require a lot of work and after that things should be easier. The tricky thing about patterns is that sometimes they are sitting there on the surface (like gotos in kernel code or explicit reference counts) but other times they are buried deeply enough that a lot of digging is needed in order to uncover them. Making matters worse, it’s not uncommon to see badly implemented patterns the author of the code didn’t even understand they were trying to implement. In systems code we sometimes see code that is half-assedly transactional. Also, see Greenspun’s 10th Rule of Programming.

It is important to learn to recognize code that contains little information. Java seems to be particularly prone to this (for example I assume this class is an obscure joke, but perhaps not…) but all languages have it. A pernicious kind of low-information code occurs in C where the verbose code is actually easy to get wrong, as in the well-known bug struct foo *x = (struct foo *) malloc (sizeof (struct foo *)).

One way to start reading a piece of code is to create an annotated call graph. If tool support is available then great, but if not this isn’t too much trouble to do by hand. Also, a by-hand callgraph is a good way to start getting a general feel for the code. Annotations on the call graph might include:

• potential trouble spots: extra-snarly code, inline assembly, code containing comments such as “you are not expected to understand this“
• entry points to the module we’re reading, and exit points from it
• resource allocations and deallocations
• error-handling paths
• accesses to important mutable global state

Putting together a good static callgraph may not be so easy if the code is functional, OO, event driven, or uses function pointers. In this case building the callgraph may become a dynamic problem.

With callgraph in hand (or without it) we should try to get a sense of the code’s control flow structure. Is it a library? An event loop? One out of a stack of layers? Does it use threads, and how? What sort of error handling does it use?

What are the main data structures used by the code we’re looking at? Which of these are shared with callers or callees? Where are they allocated, freed, and modified? What are the crucial data invariants? Are the data structures (and their algorithms) basically the textbook versions or are there interesting quirks in the implementations?

Dynamic View

Strictly speaking, we don’t need to run code in order to understand it. In practice, being able to run code is a lifesaver for several reasons. First, an actual execution follows a single path through the code, permitting us to ignore code not touched on that path. Second, if the computer is executing the code then the interpreter in our brains can take a rest and we can focus on other things. Third, if we have formed a bad hypothesis about the code, running the code is a good way to conclusively refute that hypothesis.

What is the dynamic view in practice? We can use a debugger to single-step through code, we can set breakpoints and watchpoints, we can add debugging printouts, we can add assertions corresponding to conjectured invariants, and we can write unit tests for the code to make sure we really understand it.

Finally, it’s often a good idea to change the code: add a bit of functionality, fix a bug, do some refactoring, etc. If we’ve successfully understood the code, we’ll be able to do this without too much trouble.

Conclusion

This has been a bit of a brain dump, not a checklist as much as a collection of things to keep in mind when starting out on a code-reading project. I’d be happy to get suggestions for improvement.

On the first day of this trip we explored upper Keg Spring Canyon, which was pretty but a bit nondescript as canyons go, which perhaps explains why we saw no evidence of recent human traffic. We camped for three nights off a 4wd track near the head of Keg Spring Canyon.

Generally this campsite was perfect, with a bit of shelter from the wind, soft dirt to sleep on, and a large area of flat slickrock for parking and cooking. However, on our last night some cows moved through and one of them woke me up around 4am by licking my tent. In a befuddled state I tried to scare it off without scaring it so much that it trampled me and the tent.

On the second day of this trip we drove down to Bluejohn Canyon. Although this is most often done as a technical canyoneering route, much of the canyon can be hiked. The hiking route, however, crosses some confusing terrain before dropping into the canyon; map and compass are definitely needed here.

The main fork of Bluejohn is maybe the best slot canyon I’ve seen so far. Here, a chockstone some 20′ above the canyon bottom has a bunch of tree limbs and other debris jammed around it due to flash floods.

This is another of Bill’s pictures; he’s a better photographer than I am and shooting in slot canyons is not so easy due to the enormous dynamic range. A lot of slot canyons have a sense of intimacy; Bluejohn is more about grandeur and this photo captures that aspect nicely. For reference, I believe the chockstone is the same 20′ one from the previous picture.

There were plenty of minor obstacles like this before we finally got stopped by technical climbing.

A little bit of snow and a little bit of sun.

Here’s John Veranth in the “cathedral” section of Bluejohn where it’s maybe 150′ deep and only 1-2′ wide at the top. For a very short time, sun makes it to the bottom.

Anyway, Bluejohn was fantastic. The next day we explored the area around Bowknot Bend, a huge meander in the Green River. Like many things in this part of the world, it was named by John Wesley Powell or another member of his expedition. One interesting feature in this area is a large arch with five openings.

This is Labyrinth Canyon with the La Sal mountains beyond. We didn’t see any boaters on the Green, perhaps March is too early.

Finally we are overlooking Bowknot Bend. If you’re floating the river, it’s 7 miles from the left side of this photo to the right side. Although it’s only ~4 miles hiking each way to this overlook from the end of the 4wd track, we made a full day out of it by taking a couple of detours and a couple of wrong turns.

On our last day we explored Moonshine Wash, another slot canyon. This one is supposed to be nontechnical but after downclimbing a couple of short drops like the one shown here, we got stopped by a 20′ drop that did not look super easy to reverse.

Moonshine is really pretty.

A sheep bridge crosses Moonshine Wash near its deepest, narrowest point. Given my general dislike of heights (probably more than 100′ to the bottom here) this is as close as I was able to get to the bridge, which is generally falling apart and unsafe.

The Labyrinth Rims area is relatively easy to get to given how remote it feels. Much of this area could be explored with a 2wd vehicle, although in that case you’d end up doing more walking.