Anatomy of a Software Bug

Chris Mason is the person who hired me to work at Microsoft. By the time he hired me, he’d already spent a great deal of time looking into the issue of general software quality, and had written a memo (known as the “Zero Defects” memo) that underlies much of our software practices today. The ideas have been refined since then, but they haven’t changed much in terms of the basic concepts.

One of my favorite Chris Mason quotes comes from that memo, “Since human beings themselves are not fully debugged yet, there will be bugs in your code no matter what you do.” We work to minimize the bugs in the software we ship, but they’ll always be there.

The problem stems from the overall complexity of the software. In this context, “complexity” doesn’t refer to the code itself. Rather, we’re talking about the shear volume of things the user can do. In Word, for example, we have:

  • More than 850 command functions (e.g. Bold and Italic are the same command function)
  • More than 1600 distinct commands (e.g. Bold and Italic are distinct commands)
  • At any given time roughly 50% of these commands are enabled (conservative estimate)
  • With just 3 steps, the possible combinations of code execution paths exceeds 500 million

Now, there’s a philosophical issue about the desirability of increasingly complex software, but I’m not going to discuss it here. For all practical purposes, I don’t think there’s much benefit to getting into a discussion about it. It may be an interesting question on some level, but it’s one we’ll never fully resolve. And I’m just not all that interested in getting bogged down in an endless debate without the possibility of resolution.

I mention the issue of complexity because it leads to subtle interactions that can be difficult to track down. To illustrate the point even further, I thought I’d discuss the anatomy of one of the more famous bugs we’ve had in Word: the “Disk is full” on save error. Before I do, however, I should point out that Pierre Igot, after some prodding on my part, did provide us with a sample document that helped us to track down one of the more subtle interactions involved in this particular problem. For that, Pierre, I thank you and so do Word users everywhere.

The story of this problem begins with a basic design decision made when Richard Brodie was Word’s primary software architect. Brodie came to Microsoft along with Charles Simonyi after working at the Xerox PARC where he’d worked on Bravo—their version of the GUI word processor. A number of the ideas used in Word came from that early effort. Brodie joined Microsoft in 1981, began work on Word in the summer of 1982, and finished version 1.0 in October of 1983. You can read about much of the story in Microsoft First Generation by Cheryl Tsang.

Brodie figured out that a document is really just a collection of pieces of text, and that it didn’t really matter where each piece of text is physically located within the document’s file. For that matter, you could have one piece of text that came from one file and another piece of text that came from another file. We refer to this collection of pieces of text as the “piece table.” This design has a number of benefits. For example, if you copy text from one document to another, you don’t have to actually copy the text from one file to another—at least not right away. All you really need to do is copy the appropriate entries in the piece table in the source document to the piece table in the destination document. Of course, you do need to copy the physical text and formatting from one file to the other when you save the destination document, but delaying that physical copy until save time meant that the actual copy/paste could be done very quickly.

This design also made implementing undo rather simple. In fact, according to Brodie, implementing undo was the primary reason to use this design. With this design, all you have to do is create an internal undo document. When the user deletes some text from the current document, for example, you copy the deleted entries from the piece table to the undo document and save some information about where those piece-table entries had been located in the original document. To undo the delete, you just copy the piece-table entries from the undo document back to the original document.

This design does have one problem: where do you put the text that the user types into the document if it doesn’t go into the file that’s behind the document? To solve that, Brodie added something called a “scratch” file, and the scratch file remains a core part of Word’s design to this day. On the Mac, Word creates this file in your TemporaryItems folder. On Mac OS X, this folder is located at /private/tmp/<UID>/TemporaryItems, where “UID” is your user ID number (for most people, that’s 501, but it can be a different number altogether depending on how your user account was created). If start up Word, open the terminal window and get a listing of your TemporaryItems folder, you’ll see a file named something like “Word Work File S_.” There may be a number after the “_” character. That’s Word’s scratch file (the “S” standing for scratch). You might also see one or more files named “Word Work File D_” with some number after the “_” character. This is a back-up copy of a document file (the “D” standing for “Document”).

At this point, we need to fast-forward the story by a decade to the next major feature that brought this problem to the fore: multiple undo. For ten years, Word had undo, but it was just a single-level undo. For Word 6, we added the ability to go back and undo every change you’d made to the document since you first started editing it. And, with Word’s document/file architecture, this wasn’t all that difficult to do: just make the undo document contain multiple records with one record for each change to the main document. It’s a very cool feature, and most of us couldn’t think of how we’d survive without it. But it leads to a problem.

It’s not uncommon for users to make a few edits to a document, save the document, make a few more edits, save the document again, make a few more changes, and continue this process of edit/save for hours on end. Each time you delete text, however, the actual text itself exists in the last-saved file for the document you’re editing, and, with multiple levels of undo, the undo records for text deletions still point back to the last-saved version of the document’s file before you deleted the text. The next time you save, Word can’t close the last-saved version of the file, because the undo document still contains a reference to it. So, if you keep editing and saving, you’ll eventually hit an open file limit. At least this was true of Word 6. It’s changed quite a bit since then.

Arguably, this is something we should have figured out before we shipped Word 6, but, as Chris Mason pointed out, we humans haven’t been fully debugged yet. Moreover, it’s easy to say that one should have thought of a particular interaction in a complex piece of software, but that’s way easier said than done. When you’re implementing any given feature, you’re totally focused on the basic problems involved in the feature itself. To put this into perspective, the person who implemented multiple undo in Word is one of the best developers who has ever worked on Word, and has, since, been recognized as a Microsoft Distinguished Engineer.

The reality is, that we hadn’t realized we’d created this situation when we added multiple levels of undo. Moreover, this problem has several different variations on the basic theme. At this point, the story involves our efforts to understand the nature and scope of the problem, and to come up with the “best” way to fix it. Because of the variations, however, the problem has been like an onion. We’d peel away one layer of the onion, only to find some other variation that we hadn’t, for various reasons, figured out before.

As we weave our way through the rest of the story, there are some important points to keep in mind. The first is that I can’t fix what I can’t see, and, where software bugs are concerned, “seeing” means being able to watch the program execute, via some debugging tool, at the key point in the execution of the code where the problem occurs. In order to do this, I have to have a precise set of steps that consistently reproduces the problem. This not all that different from the problem a mechanic faces when trying to figure out the cause of that mysterious engine noise that only occurs after you’ve been driving the car around town for a few hours.

The second is that this particular problem is a developer’s worst nightmare. The fundamental cause is a basic design decision that you made more than a decade ago, and the only way to really fix it for certain is to rewrite the entire application from the ground up. Since that’s simply not an option for a product that you’ve shipped several times, you’re left with trying to make the problem difficult for most users to run into while trying to also minimize the negative effects if the user should ever run into the problem. This approach can, unfortunately, lead you to believe that you’ve come up with an “optimal” fix only to discover later that there’s another facet you haven’t taken into consideration (because you didn’t even know it existed until you peeled away the previous layer of the onion).

The third point to keep in mind is that we in Mac BU have relatively limited resources. When there’s a problem that’s fundamental to Word itself, we tend to let our Win Word siblings focus on that problem. Our efforts tend to have little chance of adding to their efforts, and this frees us up to focus on problems specific to Mac users. In general, this is the most efficient way to handle problems that our users are having, but there can be instances where there’s a Mac-specific dimension to a problem. As we’ll see soon enough, this particular problem had a Mac-specific dimension that complicated our efforts to fix it, and it took us a while to find that Mac-specific dimension.

Lastly, the fact that Mac Word’s code base has been forked from Win Word’s means that the Win Word people can make a change in the code for one reason, and that change can have other side-effects that we won’t see in the Mac version until we run into some very specific circumstances that show us the different behaviors caused by this change. In this particular case, Win Word added two lines of code in a routine that would seemingly be completely unrelated to this problem, but also made this problem much more difficult for users to run into in Win Word than it was in Mac Word. This one is the last piece (maybe I should say latest piece) in the puzzle that we discovered only a few months ago.

Whew! That’s a lot to keep in the back of our heads, but, nonetheless, let’s rewind back about ten years. Word 6.0 has just shipped on Windows, and we’re pretty happy with people’s reactions to the product. It doesn’t take long, though, for us to figure out that there’s a fly in the ointment. Reports start trickling in about people editing their documents “for a while” at which point they try to save their document and they get a “Disk is full” error. We’d ask people what they were doing, and the response was always some form of vague notion that they’d just been editing their document “for a while.” The precise measurement of “for a while” varied from user to user. For some folks, it was a little over an hour. For others, it was several hours. Reproducing the problem appeared to be highly dependant upon the user’s work habits.

After several months of trying to figure out the problem, someone in testing wrote a macro that inserted a large amount of text into the document and then, in a loop, replace successive words within the document saving it after each replace. Run this macro for a while, and you get a “Disk is full” error on one of the saves, at which point you can no longer save your document. Cool! We now have steps that reproduce the problem.

So, this document got handed off to a developer, who then fired up Word under the debugger, opened the document and ran the macro. The problem “reproduced,” but, for reasons that weren’t apparent at the time, the error that the developer ran into was subtly different from the error that the tester ran into. The developer thought about the problem he was seeing, and came up with one of those “optimal” fixes I mentioned above. It was the “right” fix in terms of the problem the developer saw, but it wasn’t the “right” fix for the problem that the tester saw.

What was this subtle difference between what the developer saw and what the tester saw? As I mentioned above, the basic theme of the problem is to hit an open file limit. In this case, there are two limits: Word’s internal open file limit and the OS’ open file limit. It turns out that the debugger bumps the OS’ open file limit from what it would normally be when you run Word outside the debugger. When the tester ran the macro, Word hit the OS’ open file limit. When the developer ran the macro, with Word running under the debugger, Word ran into its own, internal, file limit.

After a few iterations of the tester saying, “Sorry, but the bug’s not fixed yet,” and the developer saying, “What are you talking about? I don’t see the problem!” they both figured out that they were seeing different errors. Crap! The problem only reproduces when you’re not running under the debugger, which removes the one case where the developer can actually see what’s going on. At this point, we have yet to figure out that the problem involves hitting the OS’ open file limit. At this point, though, the developer isn’t completely in the dark, and comes up with a fix for the tester’s problem.

As I pointed out, the problem involves the undo document having a reference to the previously saved-version of the document’s file. The developer’s original fix was to add some code, in the case where Word hit its internal open file limit, that would basically remove everything from the undo document (what we refer to as “nuking the undo stack”). Nuking the undo stack allows the save to proceed, because Word can now close the open files that were referenced by the undo document. However, since the tester was seeing a different error, the developer’s fix didn’t handle that case.

Nonetheless, the developer took a different approach. Knowing that the undo document was very likely to be involved, one could walk through the undo document, and copy the text for any pieces that pointed to the previously-saved version of the document’s file to the scratch file. He coded up the solution, and handed a buddy-build off to the tester. The tester ran the macro, and the problem was fixed. The first layer of the onion had been peeled away, but the fix still wasn’t an “optimal” fix. As it stood, the chances that a user would run into the problem had been greatly reduced, but we still hadn’t dealt with the “minimize the damage if they do hit it” side of the issue. That’s because, at this point, we had yet to understand that the problem outside the debugger had to do with the OS’ open file limit. Because this problem wouldn’t reproduce under the debugger, the developer had no way of knowing exactly where the failure was occurring. Without knowing that, the developer didn’t know where to add the code that would “nuke the undo stack.”

To give you a sense of the time frame, this fix was ported from Win Word to Mac Word during the Office 2001 development cycle, and was back-ported into Word 98 for a service release that was done not too long after that. It’s also at this point where the Win Word and Mac Word stories diverge. There are two reasons for this. The first is that this was the point in time where Win Word got that two-line code change that I mentioned above. The second is that the open file limit under Mac OS is different than it is under Windows. I might be mistaken on this point, but I think the open file limit under Mac OS X is different from the limit under Mac OS 9 as well.

At this point, we still didn’t know that the basic problem involved hitting the OS’ open file limit. After a while, though, we did know that Mac Word users were seeing this problem way more often than Win Word users. In fact, the difference was enough for Mac Word testers to start investigating the problem directly. One of the things we did know is that the problem involved file references in the undo document. So, we came up with a variation of the original fix.

In order to understand this, we have to understand a basic principle of fixes. You make the simplest code change required to fix the problem. This reduces the chances that the fix will cause some other problem that is, potentially, worse than the one you’re trying to fix. When you’re mucking about with the locations where data is stored in files, the potential for catastrophic problems resulting from your fix is high. In that sense, the original fix for this problem was limited to copying what might be known as “simple” pieces. A “simple” piece has only text. A “complex” piece might have a graphic, or it might involve a field in the document, both of which are likely to have data in the file in addition to the text itself.

With this in mind, for Mac Word X, we modified the notion of what would be a “simple” piece of text for the sake of deciding whether or not to copy a piece from the previously-saved document’s file over to the scratch file. To view this in a slightly different way, we made the code that copies undo document referents more aggressive. This resolved another test case that the Mac Word testers had developed, again using a slightly different macro that would eventually cause the “Disk is full” error to occur. This fix didn’t actually make it into the shipping release of Mac Office X, but it was included in a subsequent SR (I don’t recall specifically which one).

At this point, we still don’t know that the problem involves the OS’ open file limit. That discovery didn’t happen until this past summer when, through the very persistent efforts of Mac Word’s current lead tester, we were able to use some tools on Mac OS X to figure out exactly what was happening. While we were able to verify this, we still didn’t know the exact location where Word was failing to open a file due to having hit the OS’ open file limit. Again, we still can’t get this to reproduce under the debugger, and there are a couple of places in the save process where it can fail because the OS won’t let Word open the file. So, rather than scatter fixes all over the place, we went with the sure fix: lower Word’s internal open file limit so we hit it before we hit the OS’ open file limit. This allows the code that nukes the undo stack to kick in, and then save the succeeds.

This brings us to late February/early March of this year, and the discussion I’d had with Pierre. While we still can’t reproduce the actual file open failure under the debugger, we now have enough information about what causes the problem to be able to predict when the failure will eventually occur. From that, we knew enough about the bug for me to believe that Pierre shouldn’t still be hitting that “Disk is full” save error in the version of Word he was using. Yet, he was still running into the problem.

That was the bad news: there was something about this problem that we still didn’t fully understand. However, armed with a sample document and the ability to predict when the error will occur, I could do something we’d never been able to do before: set up Word under the debugger, perform some steps in Word to see if those steps caused the predictive condition to occur, and set breakpoints that would tell me exactly why we weren’t able to copy pieces from the undo document over to the scratch file.

This is where I discovered those two lines of code that had been added to Win Word so long ago, yet hadn’t been added to Mac Word. When Word lays out a page in page layout view and a header or footer is visible, it updates any fields in the header or footer. If you have, say, a page field in the visible header/footer, Word will update that field. This is particularly necessary when you have the footer of one page and the header of the following page both visible in the document window. Word has to layout two pages in the same update, so it updates fields for the first page footer, lays out that page, then updates the fields for the next page header and lays out that page.

Now, why would this result in a field being copied over to the undo document? Well, Word has something called “auto undo tracking.” Basically, when you’re typing, Word automatically tracks the changes you’re making until you do something that causes Word to close out the “typing” undo record. You can see this when you click on the “Undo” dropdown on the standard toolbar. You’ll see “Typing <text you typed>” at various locations in the dropdown interspersed with other actions you’ve taken.

The two lines of code that were added to Win Word paused automatic undo tracking while updating these fields in the header or footer during page layout, then un-paused automatic undo tracking once the field update was finished. Ugh! How, on earth, were we to ever figure out that these two lines of code were the primary reason Win Word users weren’t seeing this problem nearly as often as Mac Word users? In any event, if you’ve stayed with me long enough, here’s a tip you can use until we release an SR of Word X (or earlier) with this fix. If you have a document that has headers and footers with page fields in them, do your editing in Normal view, and you’ll likely never hit the “Disk is full” save error.

Right about now, you’re probably asking, “Why did it take so long to figure out what was up with this?” Well, you might as well ask why police departments continue to have a large number of unsolved crimes on the books. The issue is the same: the investigation stalls for the lack of any further leads to follow. For the same reason that the police can’t just go out and start arresting anyone who might be a suspect, we can’t go scattering potential fixes throughout the code. Until we figure out what the precise nature of the problem is, we need leads that we can follow. The mere fact that you’re running into a particular problem isn’t a lead that I can follow. Specific details about potential suspects, however, are leads I can follow. When it comes to software problems, leads I can follow consist of information that helps me to reproduce the problems consistently.

And, always remember that I can’t fix what I can’t see. I have to be able to reproduce the problem while being able to run some kind of diagnostic tool. The key to fixing a bug is predictability. Without predictability, I can’t fix it, because without predictability I have no way to understand how the complex interactions in modern software cause the specific problem to occur.

 

Rick