C compilers exploiting undefined behavior

It's getting out of hand the way C compilers exploit undefined behavior. I see via John Regehr's blog that there is a SPEC benchmark being turned into a noop via an undefined-behavior argument.

This isn't what the spec writers had in mind when they added undefined behavior. To fix it, Regehr's idea of having extra checkers to find such problems is a plausible one, though it will take a dedicated effort to get there.

An easier thing to do would be for gcc and Clang to stop the madness! If they see an undefined behavior bullet in their control-flow graphs, then they should leave it there, rather than assuming it won't happen and reasoning backward. This will cause some optimizations to stop working, but really, C compilers were already plenty good 10 years ago. The extra level of optimizations is not a net win for developers. Developers want speed, sure, but above all they want their programs to do what they look like they do.

It should also be possible to improve the spec around this, to pin down what undefined behavior means a little more specifically. For example, left-shifting into the sign bit of a signed integer is undefined behavior. That's way underspecified. The only real options are: shift into the sign bit as expected, turn the integer into unpredictable garbage, or throw an exception. As things stand, a C compiler is allowed to observe a bad left shift and then turn your whole program into a noop.

The "magic moment" for IPv6

The Internet has undergone many large changes in the protocols it uses. A few examples are: the use of MIME email, the replacement of Gopher by HTTP, and the use of gzip compression within HTTP. In all three of these examples, the designers of the protocol upgrades were careful to provide a transition plan. In two out of the three examples (sorry, Gopher), the old protocol is still practical to use today, if you can live with its limitations.

Things are going differently for IPv6. In thinking about why, I like Dan Bernstein's description of a "magic moment" for IPv6. It goes like this:

The magic moment for IPv6 will be the moment when people can start relying on public IPv6 addresses as replacements for public IPv4 addresses. That's the moment when the Internet will no longer be threatened by the IPv4 address crunch.

Note that Dan focuses on the address crunch. Despite claims to the contrary, I believe most people are interested in IPv6 for its very large address space. While there are other cool things in IPv6, such as built-in encryption and simplified fragmentation, they are not enough that people would continue to lobby for IPv6 after all these years. The address crunch is where it's at.

While I like Dan's concept of a magic moment, I think the above quote asks for too much. There are some easier magic moments for individual kinds of nodes on the computer, and some might well happen before others. Let me focus on two particular kinds of Internet nodes: public web sites and home Internet users.

How close is the magic moment for web sites? Well, web servers can discard their IPv4 addresses just as soon as the bulk of the people connecting to them all have IPv6 connectivity. I do not know how to gather data on that, but as a spot point, I have good networking hardware but cannot personally connect to IPv6 sites. My reason is both mundane and common: I am behind a Linksys NATing router, and that router does not support IPv6. Even if it did, it does not support any sort of tunneling that would allow my local computer to connect to an IPv6-only web server. To the extent people are using plain old Linksys routers, we are a long way away from the magic moment for web servers.

How about for home users? Well, it's the other way around for home users: home users can switch once the majority of public web sites have an IPv6 address. This status is easier to gather data on. I just looked up the top ten web sites (according to Alexa's Top 500 Web Sites) and checked them with a publicly available IPv6 validation site (http://ipv6-test.com/validate.php). Of the top ten web sites, only four can be reached from an IPv6-only client: Google, Facebook, YouTube, and Wikipedia. The other six still require IPv4: Yahoo, Baidu, Live.com, Amazon, QQ.com, and Twitter. As things stand, we are also a long way from when home users can switch to IPv6-only.

Overall, this was a cursory analysis, but I think these "magic moments" are a helpful framework for thinking about the IPv6 changeover. Unfortunately, this framework currently indicates that we are nowhere close.

Virtual classes

Gilad Bracha has a great post up on virtual classes:

I wanted to share a nice example of class hierarchy inheritance....All we need then, is a slight change to ThreadSubject so it knows how to filter out the synthetic frames from the list of frames. One might be able to engineer this in a more conventional setting by subclassing ThreadSubject and relying on dependency injection to weave the new subclass into the existing framework - assuming we had the foresight and stamina to use a DI framework in the first place.

I looked into virtual classes in the past, as part of my work at Google to support web app developers. Bruce Johnson put out the call to support problems like Gilad describes above, and a lot of us thought hard on it. Just replace "ThreadSubject" by some bit of browser arcana such as "WorkerThread". You want it to work one way on App Engine, and a different way on Internet Explorer, and you want to allow people to subclass your base class on each platform.

Nowadays I'd call the problem one of "product lines", having had the benefit of talking it over with Kurt Stirewalt. It turns out that software engineering and programming languages have something to do with each other. In the PL world, thinking about "product lines" leads you to coloring, my vote for one of the most overlooked ideas in PL design.

Here is my reply on Gilad's blog:

I'd strengthen your comment about type checking, Gilad: if you try to type check virtual classes, you end up wanting to make the virtual classes very restrictive, thus losing much of the benefit. Virtual classes and type checking are in considerable tension.

Also agreed about the overemphasis on type checking in PL research. Conceptual analysis matters, but it's hard to do, and it's even harder for a paper committee to review it.

I last looked into virtual classes as part of GWT and JS' (the efforts tended to go in tandem). Allow me to add to the motivation you provide. A real problem faced by Google engineers is to develop code bases that run on multiple platforms (web browsers, App engine, Windows machines) and share most of the code. The challenge is to figure out how to swap out the non-shared code on the appropriate platform. While you can use factories and interfaces in Java, it is conceptually cleaner if you can replace classes rather than subclass them. More prosaically, this comes up all the time in regression testing; how many times have we all written an interface and a factory just so that we could stub something out for unit testing?

I found type checking virtual classes to be problematic, despite having delved into a fair amount of prior work on the subject. From what I recall, you end up wanting to have *class override* as a distinct concept from *subclassing*, and for override to be much more restrictive. Unlike with subclassing, you can't refine the type signature of a method from the class being overridden. In fact, even *adding* a new method is tricky; you have to be very careful about method dispatch for it to work.

To see where the challenges come from, imagine class Node having both an override and a subclass. Let's call these classes Node, Node', and LocalizedNode, respectively. Think about what virtual classes mean: at run time, Node' should, in the right circumstances, completely replace class Node. That "replacement" includes replacing the base class of LocalizedNode!

That much is already unsettling. In OO type checking, you must verify that a subclass conforms to its superclass. How do you do this if you can't see the real superclass?

To complete the trap, imagine Node has a method "name" that returns a String. Node' overrides this and--against my rules--returns type AsciiString, because its names only have 7-bit characters in them. LocalizedNode, meanwhile, overrides the name method to look up names in a translation dictionary, so it's very much using Unicode strings. Now imagine calling "name" on a variable of static type Node'. Statically, you expect to get an AsciiString back. However, at run time, this variable might hold a LocalizedNode, in which case you'll get a String. Boom.

Given all this, if you want type checking, then virtual classes are in the research frontier. One reasonable response is to ditch type checking and write code the way you like. Another approach is to explore alternatives to virtual classes. One possible alternative is to look into "coloring", as in Colored FJ.

Andreas Raab

It seems we had a bad week for programmers. I learned via James Robinson that Andreas Raab has died. There is an outpouring of messages on the Squeak mailing list.

I worked with Andreas on the Squeak project several years ago, where I got to see first-hand his outstanding work. Among many other tasks, he played a leading role in actually implementing the Croquet system for eventual consistency. At the time I worked with him, he was developing Tweak, a self-initiated project for rapid GUI development.

On a selfish note, I learned a lot working with Andreas. You only get better in this industry by practicing with good people. Andreas was one of the best.

I'd be remiss not to say he was also a blast to work with. He was always laughing, yet always insightful. He always found ways to get the people around him on a better path. He always found ways to tell them that they were happy to hear.

Rest in peace, Andreas. We are lucky to have had you, for as long as you could stay.

Does IPv6 mean the end of NAT?

I frequently encounter a casual mention that, with the larger address space in IPv6, Net Address Translation (NAT)--a mainstay of wireless routers everywhere--will go away. I don't think so. There are numerous reasons to embrace path-based routing, and I believe the anti-NAT folks are myopically focusing on just one of them.

As background, what a NAT router does is allow multiplexing multiple private IP addresses behind a single, public IP address. From outside the subnet, it looks like the NAT router is a single machine. From inside the subnet, there are a number of machines, each with its own IP address. The NAT router allows communication between the inside and outside worlds by swizzling IP addresses and ports as connections go through the router. That's why it is a "net address translator" -- it translates between public IPs and private IPs.

My first encounter with NAT was to connect multiple machines to a residential ISP. It was either a cable company or a phone company; I forget which. The ISP in question wanted to charge extra for each device connected within the residential network. That is, if you connect two computers, you should pay more than if you connect one computer. I felt, and still feel, that this is a poor business arrangement. The ISP should concern itself with where I impose costs on it, which is via bandwidth. If I take a print server from one big box and move it onto its own smaller computer, then I need a new IP address, but that shouldn't matter at all to the ISP. By using NAT--in my case, Linux's "masquerading" support--the ISP doesn't even know.

This example broadens to a concern one could call privacy. What an organization does within its own network is its own business. Its communication with the outside world should be through pre-agreed protocols that, to the extent feasible, do not divulge decisions that are internal to the organization. It shouldn't matter to the general public whether each resident has their own machine, or whether they are sharing, or whether the residents have all bought iPads to augment their other devices.

For larger organizations, privacy leads to security. If you want to break into an organization's computer infrastructure, one of the first things you want to do is to feel out the topology of the network. Unless you use NAT at the boundary between your organization's network and the general internet, then you are exposing your internal network topology to the world. You are giving an attacker an unnecessary leg up.

You could also view these concerns from the point of view of modularity. The public network protocol of an organization is an interface. The internal decisions within the organization are an implementation. If you want everything to hook up reliably, then components should depend on interfaces, not implementations.

Given these concerns, I see no reason to expect NAT to go away, even given an Internet with a larger address space. It's just sensible network design. Moreover, I wish that the IETF would put more effort into direct support for NAT. In particular, the NAT of today is unnecessarily weak when it comes to computers behind different NATing routers making a direct connections with each other.

It is an understatement to say that not everyone agrees with me. Vint Cerf gave an interview earlier this year where he repeatedly expressed disdain for NAT.

"But people had not run out of IPv4 and NAT boxes [network address translation lets multiple devices share a single IP address] were around (ugh), so the delay is understandable but inexcusable."

Here we see what I presume is Cerf's main viewpoint on NAT: it's an ugly mechanism that is mainly used to avoid address exhaustion.

One of the benefits of IPv6 is a more direct architecture that's not obfuscated by the address-sharing of network address translation (NAT). How will that change the Internet? And how seriously should we take security concerns of those who like to have that NAT as a layer of defense? Machine to machine [communication] will be facilitated by IPv6. Security is important; NAT is not a security measure in any real sense. Strong, end-to-end authentication and encryption are needed. Two-factor passwords also ([which use] one-time passwords).

I respectfully disagree with the comment about security. I suspect his point of view is that you can just as well use firewall rules to block incoming connections. Speaking as someone who has set up multiple sets of firewall rules, I can attest that they are fiddly and error prone. You get a much more reliable guarantee against incoming connections if you use a NAT router.

In parting, let me note a comment in the same interview:

Might it have been possible to engineer some better forwards compatibility into IPv4 or better backwards compatibility into IPv6 to make this transition easier? We might have used an option field in IPv4 to achieve the desired effect, but at the time options were slow to process, and in any case we would have to touch the code in every host to get the option to be processes... Every IPv4 and IPv6 packet can have fields in the packet that are optional -- but that carry additional information (e.g. for security)... We concluded (perhaps wrongly) that if we were going to touch every host anyway we should design an efficient new protocol that could be executed as the mainline code rather than options.

It is not too late.

Windows 8 first impressions

An acquaintance of mine got a Windows 8 machine for Christmas, and so I got a chance to take a brief look at it. Here are some first impressions.

Windows 8 uses a tile-based UI that was called "Metro" during development. As a brief overview, the home page on Windows 8 is no longer a desktop, but instead features a number of tiles, one for each of the machine's most featured applications. Double-clicking on a tile causes it to maximize and take the whole display. There is no visible toolbar, no visible taskbar, no overlapping of windows. In general, the overall approach looks very reasonable to me.

The execution is another story. Let me hit a few highlights.

First, the old non-tiled desktop interface is still present, and Windows drops you into it from time to time. You really can't avoid it, because even the file browser uses the old mode. I suppose Microsoft shipped this way due to concerns about legacy software, but it's really bad for users. They have to learn not only the new tiles-based user interface but also the old desktop one. Thus it's a doubly steep learning curve compared to other operating systems, and it's a jarring user experience as the user goes from one UI to the other.

An additional problem is a complete lack of guide posts. When you switch to an app, you really switch to the app. The tiles-based home page goes away, and the new app fills the entire screen, every single pixel. There is no title bar, no application bar, nothing. You don't know what the current app is except by studying it's current screen and trying to recognize it. You have no way at all to know which tile on the home page got you here; you just have to remember. The UI really needs some sort of guide posts to tell you where you are.

The install process is bad. When you start it, it encourages you to create a Microsoft account and log in using that. It's a long process, including an unnecessary CAPTCHA; this process is on the critical path and should be made short and simple. Worse, though, I saw it outright crash at the end. After a hard reboot, it went back into the "create a new account" sequence, but after entering all the information from before, it hits a dead end and says the account is already being used on this computer. This error state is bad in numerous ways. It shouldn't have evened jumped into the create-account sequence with an account already present. Worse, the error message indicates that the software knows exactly what the user is trying to do. Why provide an error message rather than simply logging them in?

Aside from those three biggies, there are also a myriad of small UI details that seem pointlessly bad:

• The UI uses a lot of pullouts, but those pullouts are completely invisible unless you know the magic gesture and the magic place on the screen to do it. Why not include a little grab handle off on the edge? It uses a little screen space, and it adds some clutter, but for the main pullouts the user really needs to know they are there.
• In the web browser, they have moved the navigation bar to the bottom of the screen. This breaks all expectations of anyone that has used another computer or smart phone ever in their life. In exchange for those broken expectations, I can see no benefit; it's the same amount of screen space either way.
• The "support" tile is right on the home page, which is a nice touch for new users. However, when you click it the first time, it dumps you into the machine registration wizard. Thus, it interrupts your already interrupted work flow with another interruption. It reminds me of an old Microsoft help program that, the first time you ran it, asked you about the settings you wanted to use for the search index.

On the whole, I know I am not saying anything new, but it strikes me that Microsoft would benefit from more time spent on their user interfaces. The problems I'm describing don't require any deep expertise in UIs. All you have to do is try the system out and then fix the more horrific traps that you find. I'm guessing the main issue here is in internal budgeting. There is a temptation to treat "code complete" as the target and to apportion your effort toward getting there. Code complete should not be the final state, though; if you think of it that way, you'll inevitably ship UIs that technically work but are full of land mines.

Okay, I've tried to give a reasonable overview of first impressions. Forgive me if I close with something a little more fun: Windows 8 while drunk.

Recursive Maven considered harmful

I have been strongly influenced by Peter Miller's article Recursive Make Considered Harmful. Peter showed that if you used the language of make carefully, you could achieve two very useful properties:

• You never need to run make clean.
• You can pick any make target, in your entire tree of code, and confidently tell make just to build that one target.

Most people don't use make that way, but they should. More troubling, they're making the same mistakes with newer build tools.

What most people do with Maven, to name one example, is to add a build file for each component of their software. To build the whole code base, you go through each component, build it, and put the resulting artifacts into what is called an artifact repository. Subsequent builds pull their inputs from the artifact repository. My understanding of Ant and Ivy, and of SBT and Ivy, is that those build-tool combinations are typically used in the same way.

This arrangement is just like recursive make, and it leads to just the same problems. Developers rebuild more than they need to, because they can't trust the tool to build just the right stuff, so they waste time waiting on builds they didn't really need to run. Worse, these defensive rebuilds get checked into the build scripts, so as to "help" other programmers, making build times bad for everyone. On top of it all, even for all this defensiveness, developers will sometimes fail to rebuild something they needed to, in which case they'll end up debugging with stale software and wondering what's going on.

On top of the other problems, these manually sequenced builds are impractical to parallelize. You can't run certain parts of the build until certain other parts are finished, but the tool doesn't know what the dependencies are. Thus the tool can't parallelize it for you, not on your local machine, not using a build farm. Using a standard Maven or Ivy build, the best, most expensive development machine will peg just one CPU while the others sit idle.

Fixing the problem

Build tools should use a build cache, emphasis on the cache, for propagating results from one component to another. A cache is an abstraction that allows computing a function more quickly based on partial results computed in the past. The function, in this case, is for turning source code into a binary.

A cache does nothing except speed things up. You could remove a cache entirely and the surrounding system would work the same, just more slowly. A cache has no side effects, either. No matter what you've done with a cache in the past, a given query to the cache will give back the same value to the same query in the future.

The Maven experience is very different from what I describe! Maven repositories are used like caches, but without having the properties of caches. When you ask for something from a Maven repository, it very much matters what you have done in the past. It returns the most recent thing you put into it. It can even fail, if you ask for something before you put it in.

What you want is a build cache. Whereas a Maven repository is keyed by component name and version number (and maybe a few more things), a build cache is keyed by a hash code over the input files and a command line. If you rebuild the same source code but with a slightly different command, you'll get a different hash code even though the component name and version are the same.

To make use of such a cache, the build tool needs to be able to deal sensibly with cache misses. To do that, it needs a way to see through the cache and run recursive build commands for things that aren't already present in the cache. There are a variety of ways to implement such a build tool. A simple approach, as a motivating example, is to insist that the organization put all source code into one large repository. This approach easily scales to a few dozen developers. For larger groups, you likely want some form of two-layer scheme, where a local check-out of part of the code is virtually overlaid over a remote repository.

Hall of fame

While the most popular build tools do not have a proper build cache, there are a couple of lesser known ones that do. One such is the internal Google Build System. Google uses a couple of tricks to get the approach working well for themselves. First, they use Perforce, which allows having all code in one repository without all developers having to check the whole thing out. Second, they use a FUSE filesystem that allows quickly computing hash codes over large numbers of input files.

Another build tool that gets this right is the Nix build system. Nix is a fledgling build tool built as a Ph.D. project at the University of Delft. It's available open source, so you can play with it right now. My impression is that it has a good core but that it is not very widely used, and thus that you might well run into sharp corners.

How we got here

Worth pondering is how decades of build tool development have left us all using such impoverished tools. OS kernels have gotten better. C compilers have gotten better. Editors have gotten better. IDEs have gotten worlds better. Build tools? Build tools are still poor.

When I raise that question, a common response I get is that build tools are simply a fundamentally miserable problem. I disagree. I've worked with build tools that don't have these problems, and they simply haven't caught on.

My best guess is that, in large part, developers don't know what they are missing. There's no equivalent, for build tools, of using Linux in college and then spreading the word once you graduate. Since developers don't even know what a build tool can be like, they instead work on adding features. Thus you see build tool authors advertising that they support Java and Scala and JUnit and Jenkins and on and on and on with a very long feature list.

Who really cares about features in a build tool, though? What I want in a build tool is what I wrote to begin with, what was described over a decade ago by Peter Miller: never run a clean build, and reliably build any sub-target you like. These are properties, not features, and you don't get properties by accumulating more code.