More code coverage treemap fun

Quite some time ago, I built a treemap visualization of code coverage. This had been inspired by the information visualization course I was taking then, and I have since found a less static version more useful for getting a feeling of code coverage than lcov's index pages. Back then, two years ago, the only decent toolkit I found for building treemaps was in Java, which would necessitate the use of applets if I tried to put it on the web. Since most of what I produced was just static images, using Java locally wasn't issue. Then again, I'm also a contributor to an organization that is pushing hard about being able to do things in pure JS. So I thought I might as well try to replicate it using a JS toolkit.

Two years has made quite a difference in terms of JS toolkits. Back in 2010, the only JS toolkit I found that had treemaps was protovis, which I found fairly unusable. Now, there are a few more higher-quality toolkits, but they've all had a fairly major problem of forcing you to shoehorn your data into a specific format instead of letting you customize how data is formatted. The JavaScript Infovis Toolkit is the one that both makes me happy in the results and annoyed to get it to work. Finally, I settled on D3, which is still too low-level to make me happy (don't ask me how painful getting animations working was).

The end result is here (the equivalent lcov result is also available). Every file is a rectangle in that represents a single file of source code. Hover over it, and you get details of coverage in that file. Click on it, and you can zoom in one level down in the source code hierarchy. If you ctrl-click, you zoom one level back. The size of the rectangles is indicative of how large the file is (you can configure it to be by number of lines or number of functions). Their color is indicative of what percentage of lines (or functions) is covered: a red color means very few are executed in tests, while a green color means most are. There is a scale that indicates what a given percentage of code looks like, and there is even internal code to affect the scale (so as to make the midpoint muddy red be not 50% but more like 70%), but this is disabled since the scale is more difficult to change. Changing parameters causes the treemap to animate to its new position, but the sheer number of elements here appears to give Gecko heartburn—it's much smoother if you zoom in to smaller directories! I do realize that this also results in a lot of boxes flying around each other, but a squarified treemap is unfortunately a very unstable algorithm.

The technology that underlies the visualization isn't complicated. I used lcov to produce a summary file, and then used a python script to convert the file into a summarized JSON version. Tooltips are provided using tipsy, which I don't particularly like all that much, but I haven't found anything that is as easy to use while also servicing my needs (most importantly, placing tooltips so they don't fall off the edge of the screen). As an aside, a visualization toolkit that doesn't have any tooltip support is extremely bad—details-on-demand is a critical component of information visualization.

There's some things I don't have: I don't scrape branch coverage yet, for example. And having a query parameter that lets you zoom into a specific directory immediately would be helpful, as would being able to cut off the tree before the leaves. I would also like to see a nice view of a single file, so I can completely kick the lcov output. Being able to select individual files would also be a boon. Another neat feature would be to select from multiple sources (e.g., different test suite coverages or even monitoring as code coverage changes through the years!).

As a postscript, let me give you a tour of top-level directories in the view. The tiny sliver in the uppper-left is, from top-to-bottom, the C++ source code of Thunderbird-specific code, lightning, and LDAP. Then there is a sizable block for mork, and the rest of the left column is mailnews code. Then there is a barely-noticeable column and another small but noticeable column which contain between them a lot of small top-level directories in mozilla. The next column (similar in width to the comm-central column) contains, from top-to-bottom, IPC, spellcheck, widget, security, accessibility, parser, and xpcom. The next column contains editor, toolkit, network, and DOM code. The right 40% of the diagram or so lacks definable columns. The upper-left of this portion (you'll notice it by the large red block with a lot of "S" letters peeking out) is the graphics code. To its right lies JS. Beneath both of these lies the code for layout, and beneath that and at the bottom is content.

And, no, my code is not on github yet because most of everything that matters is in that one HTML file. I also plan to integrate this view into DXR at some point in time.

A tour of libmime

Libmime (the C++ version, that is) exposes three services, not including the tight coupling it shares with compose code. These three services are a service that extracts headers (which many people probably didn't knew existed), a service that parses structured headers (in two place), and everything else. The first two are fairly straightforward to understand, so it's the complexity of the last one which is worth talking about here.

The first thing the astute programmer will notice is the apparent lack of a way to drive the MIME converter. This is because the converter also implements nsIStreamConverter, kind of. The MIME converter uses the fact that it derives from nsIStreamListener to receive data, and it uses the Init method to set itself up (while effectively ignoring half its parameters). There is logic to extract the URL to load from the context parameter, and this is where the fun and games begin. If no output type is manually selected, it is sniffed from the URL as follows:

1. No URL results in quoting
2. Finding part= (unless the desired type is application/vnd.mozilla.xul+xml) causes the output type to be raw, unless a type= parameter is present, which induces body display and uses that type for the stream's content-type.
3. Finding emitter=js causes a special case that is used to select gloda's JS MIME emitter
4. Finding header= does a lookup for the special mime output type; the values possible are filter, quotebody, print, only (uses header display), none (uses body display), quote, saveas, src, and raw, most of whose mappings to the appropriate value in nsMimeOutput are fairly obvious.
5. The default, if none of the above match, is to display the body.

With the URL and output format settled, the next step is choosing the emitter. The gloda hack obviously results in the gloda JS MIME emitter, and editor templates and drafts don't use an emitter, but, otherwise, either the raw emitter (attach, decrypt, raw, and source), XML emitter (header display), orHTML emitter (everybody else) is used.

After the emitter is initialized and constructed, a bridge stream is set up to actually pump the data into libmime. The output is handled differently in the case of things that get sent to compose and things that get driven by display. The former merely passes through some more options and then decomposes attachments into temporary files, while the latter is more interesting and complicated. The URL is parsed—again—and the following parts are noticed. If headers= is present and results in one of only, none, all, some, micro, cite, or citation, then opts->headers is set to signify the choice. The presence of part= sets opts->part_to_load, while rot13 enables rot13_p (did you know TB had that feature?). Some more hacks are enabled if emitter=js is present, and then the part number is checked to see if it might be an attempt to use the old (Netscape 2) MIME part numbering scheme. After all of this done, we set up charset overrides for the message if they need to be set up and then we can actually start pumping data.

The guts of libmime that actually do the parsing is in the polymorphic object system within libmime. The text initially gets fed to an instance of MimeMessage, but once the headers of one these containers gets parsed, the body is fed through another object. Going from a content-type to an object takes several lines of code, but a brief summary of the decisions should suffice. If no Content-Type header is present, the code chooses a default (ultimately, for children of MimeMessage, the default is untyped text, which sniffs for binhex, yEnc, and uuencode). Some parts can have their content-type sniffed by a found filename instead. The extension point that allows extensions to add their own content-type handlers gets run before anyone else, but, as far as I can tell, only enigmail leverages this. There is another subtle extension hook which allows people to convert any type to HTML (Lightning uses this). Some types are simple and always go to the same class: message/rfc822 and message/news both result in a MimeMessage, while message/external-body creates a MimeExternalBody. Other types get dispatched based mostly on preferences: text/html and multipart/* are the biggest cases here. Everything else (note that text/* defaults to text/plain and multipart/* to multipart/mixed) becomes a MimeExternalObject, and a paranoia preference can also turn half of the classes into a MimeExternalObject.

After creating classes, the next phase is the actual parsing logic. And this is where I'm stopping the tour for now. I've got more precise information laid out on virtual sticky notes on my laptop, but I don't think it's worth posting what amounts to several large switch statements in a brief tour.

A new JS MIME parser

Here is one of those guessing games whose answers will depress you: how many (partial) MIME parsers do we have in Thunderbird? If you guessed zero, ha-ha, very funny; now go sit in the corner. If you guessed one, you've obviously never worked with libmime before. The actual answer depends on how liberal you want to be. On the conservative end, there are no fewer than 5 parsers which go at least as far as parsing multipart messages (including two in a single file). If you choose to go liberally, counting everybody who attempts to split header values to look for a specific value, you gain an additional six that I am aware of… and I have no doubt that more are lurking behind them. I suppose this means that we now have more implementations of message header parsing than we do base64-decoding (although nowadays, it seems like most base64-decoding got stuffed into one method with several wrappers). The complete list as I know it:

• nsMsgBodyHandler
• nsMsgDBFolder::GetMsgTextFromStream
• libmime
• IMAP fakeserver (one for body parts, one for body structure, and another spot happily hunts down headers)
• NNTP fakeserver (hunts down headers)
• nsParseMailbox
• nsNNTPProtocol (hunts down headers)
• nsMsgLocalStoreUtils (hunts down headers)
• Somewhere in compose code. Probably, although it's not clear how much is being funneled back to libmime and how much is not.
• A class in necko implements in the RFC 2231 and RFC 2047 decoding.

Well, it's time for to increment that count by one. And then decrement it by at least three (two of the IMAP and the NNTP fakeserver decoders are switched over in a queued patch, and I hope to get the third IMAP fakeserver switched over). I've been working on a new JS MIME parser to Thunderbird for a bit at a time over the past several months, and I have local patches that start using it in tests (and as a replacement for nsIMimeHeaders).

So, why replace libmime instead of consolidating everyone onto it? The short answer is because libmime is a festering pile of crap. It uses an internal object system that can be summarized as "reimplementing C++ in C" and has existed largely in the same form since at least Netscape 5 (the Mozilla classic version gives a date of May 15, 1996). All of that would be manageable were it not for the fact that the architecture is clearly broken. Reliably parsing multipart MIME messages is not a trivial task (indeed, not only does one of the above do it incorrectly, but there is actually a test which may rely on it being wrong. Guess which one it is.), and the fact that so many people have variants on it is a clear indication that the API fails to expose what it ought to expose. This means that the code is in need of change, and the implementation is a form which makes changing things extremely difficult.

The choice to do it in JS was motivated mostly by Andrew Sutherland. There has been a long-term ideal in Thunderbird dating back to at least around 2008 to move more implementation of core code into JS, which would help avoid massive churn spurred on by mozilla-central; nowadays, there is the added benefit that it would aid in efforts like B2G or porting to platforms where native code is frowned upon. MIME code, being extremely self-contained (charset conversion and S/MIME encryption make up the biggest dependencies in the core parser). As of my current implementation, the only external dependency that the MIME parser has is atob, although charset conversion (via the proposed string encoding API) will be added when I get there. In other words, this code is usable by anyone who wants to write a mail client in JS, not just the internal mailnews code.

Another advantage to writing my own library is that it gives me a lot of time to lay out specifications in clearer terms. One called out in the spec are on how to handle seeing boundaries for the non-leaf-most part. My own brain went further and started musing on non-leaf parts getting QP or base64 content-transfer-encodings (which RFC 6532 went ahead and allowed anyways), or multiple nested parts having the same boundary (which the specification, in my view, hints at resolving in a particular fashion). Other developments include the fact that most MIME parsers do not permit as much CFWS as the specification indicates could be present ("Content-Type: multipart / mixed" would be unusable in every MIME parser source I read)I also produced a list of all the specifications that the parser will need to refer to that I have found so far (13 RFCs and a handful of non-RFCs, plus 9 obsoleted RFCs that may still warrant viewing). As for size? The JS implementation is about 600-700 lines right now (including over 300 lines of comments), while the equivalent C++ portions take over a thousand lines to do more or less the same thing.

As I said earlier, one of the problems with libmime is its oppressive architecture. It is primarily designed to drive the message pane while living as a streaming converter. However, it encompasses roughly three steps: the production of the raw MIME tree (or a tree that combine the raw MIME data with pseudo-MIME alternatives), conversion of that tree into a more traditional body-and-attachments view, and then the final driving of the UI. Getting it to stop any earlier is between difficult and impossible; what I have now, once it gets some more testing, can satisfy people who just need the first step. Doing the second step would require me to sit down and document how libmime makes its choices, which is not a task I look forward to doing.

Hate speech? Really?

One of my goals in life is to participate in a true political debate. Not a shouting match, but a true debate where both sides argue their points reasonably and, crucially, are open to the fact that they may be holding the wrong ideas and willing to change their beliefs. The Internet, allowing for an easy way to facilitate discussions across a very large, very diverse group of participants ought to have made this easier; alas, it seems that the past few years has only increased the vitriol and spitting bile in these shouting matches.

When I read news articles, sometimes I think "this sounds thought-provoking", and I turn to the online comments to see if it started one. Almost invariably, most of the comments turn out to be rants that are only distantly germane to the article (e.g., any article on the Middle East sets off a firestorm with ... well, you can guess; any article on Ron Paul sets off commenters screaming about how he's being "ignored" by the media, etc.). Sometimes, the ones I think are most thought-provoking have no comments (typically any article that mentions Africa). Go figure.

It is also surprising how many people you think ought to know better end up doing nothing but shouting. I went to a well-regarded selective-admissions public high school (the mean score for the standard college-admissions test in the US is not far from perfect) (and no, I did not get a perfect score on said test), but when we had a sponsored debate between the Democratic and Republican groups in our school, it still devolved into a (literal) shouting match.

Which brings me, in a roundabout manner, to the true topic of this post. Apparently, there is a firestorm currently brewing over a post on planet.mozilla.org that dealt with a political topic of current interest to some people. I discovered, years ago, that you catch a lot more flak if you write a post that goes to an aggregator that people disagree with than if you write one they agree with (I explained why I did not like the results of the 2008 presidential election, and caught more flak than the few posts earlier celebrating those results). I don't mind political discussion—indeed, as I described earlier, I'd love one. But I can understand why people might not like sensitive political topics being collected on a site which can be interpreted as official Mozilla policy.

However, there is one thing I don't like about it. Some people have taken it upon themselves to call the viewpoint presented as hate speech. I don't know what hate speech is exactly, but I don't think it should ever exist, no matter what one defines. That is because terming something as hate speech is an attempt to avoid discussing it: it is a way to say "that statement is so wrong I am not going to bother to refute it", or, equivalently, "I am so right that any opposition to my idea cannot be rationally argued." It is at best an insult to one's opponent and at worst an admission of outright arrogance.

Even worse, I think, are people who want to outlaw hate speech. Speech is, fundamentally, a reflection of one's belief. Attempting to outlaw the utterance of specific beliefs is nothing more than trying to outlaw those beliefs in the first place. Sure, some of them are injurious insults (such as those who deny that the Holocaust happened), but there is, to me, a steep slippery slope you start out on. Why outlaw denials of the Holocaust but not also outlaw denials of other historical religiously-motivated genocides? Hell, why stop there? We could outlaw any false statement: think how much more rational our discussions would be if people didn't state such lies as "Sharia law is invading the US legal system" or "the New Deal did nothing to bring us out of the Great Depression." Wait, maybe that's why.

I remember, when doing a project for a US Government class that involved redebating several key cases on freedom speech, that I found a Supreme Court decision which mentioned something to the effect of "Free speech is at its best when it causes discomfort" (I cannot find the exact quote right now, sadly enough). At that moment, I think, I solidified my stance on free speech to the following: all speech ought to be free, no matter how insulting, radical, or slanderous it may be. It may be that your speech causes injurious actions, but it's only the intent and the action that matters (e.g., falsely yelling "Fire!" in a crowded theater is grounds for manslaughter, but because the action was intended to create a stampede, not because you actually said "Fire"). Attempting to censor others' opinions—whether through legal means, or through attempts to shame them by calling their words "hate speech"—is not an action I can support.

And if you disagree with me, feel free to try to discuss it with me. Who knows, I may just change my mind.

How to use bugpoint

One of the problems with working with compilers is that you tend not to find some bugs until they get used on real code. And unlike most test suites, real code can involve some very large files, which is where you tend to find bugs. As luck would have it, my debugging fun today led to two bugs being found in the same function... which is only a 200 line function that hides infinite loops in macros and is written using continuations to boot. The LLVM IR for this function, after being compiled with -O3, was 4500 lines (and one block had 87 predecessors and several ϕ instructions as well). At such a size, finding out why my code crashes on such a function is impossible, let alone figuring out which optimizations I need to blame for it.

Fortunately, LLVM has a tool called bugpoint which can reduce this IR into a more manageable size of work. Doing manual reduction via an iterative process of "this doesn't look necessary; cut it out" the first time took me about an hour to produce a pile of code small enough to actually analyze. Doing it via bugpoint on the second bug took closer to 30 minutes. Unfortunately, the hard part is figuring out how to actually use the tool in the first place: none of the manuals give an example command line invocation, and they start playing games of "look at that documentation over there". So, I am going to remedy this situation by actually giving functional documentation.

In this case, I have an assert in an LLVM pass that is being triggered. This pass isn't being run as part of opt, but rather its own tool that takes as input an LLVM IR file. So the first step is to get the IR file (clang -cc1 -emit-llvm -O3 is sufficient for my needs). After that, it's time to prepare a shell script that actually compiles the code; you can skip this step if you don't actually need to provide arguments to the program. For example, my bugpoint.sh script would look like:

#!/bin/bash
/path/to/tool "$@" -arg1 -arg2 -arg3=bleargh -o /dev/null

After that, the next step is to actually invoke bugpoint. Here's the command line that's running as I write this post: bugpoint --compile-custom -compile-command ./bugpoint.sh io_lat4.ll. Since my program causes an assertion failure, bugpoint figures out that I'm trying to crash on code generation (it can also detect miscompilation errors). Hopefully, the first bit of output you get should look like the following:

Error running tool:
  ./bugpoint.sh bugpoint-test-program.bc-FB1NoU
Text indicating your program crashed
  *** Debugging code generator crash!

If you've seen this much (you may need to wait for it to crash; it can take a long time if you doing Debug+Asserts builds), you know that it's trying to find code that makes your tool crash. After that, bugpoint tries to first reduce global initializers and then tries to eliminate as many functions as possible. After that, it tries eliminating basic blocks and then goes to work eliminating instructions. You will see lots of streaming output telling you what stuff it's removing; the documentation says it's helpful to capture this output, but I've found it useless.

When everything is done, you should get several files of the form bugpoint-*.bc; the most useful one is bugpoint-reduced-simplified.bc, which is the most reduced testcase. What you get now is a nice, reduced testcase? Not quite. First, it gives you just a bitcode file (I'd prefer .ll files, simply because my first thought is to read them to figure out what's going on). Another problem I have with bugpoint is that it doesn't do things like attempt to eliminate unused struct entries, nor does it bother to clean up some of its names. Take a look at this struct monstrosity: %struct.su3_matrix.4.134.147.173.199.212.238.290.303.329.381.394.407.459.472.485.498.524.550.563.576.589.602.615.628.654.667.680.719.758.823.836.849.862.1044.1057.1096.1808 = type { [3 x [3 x %struct.complex.3.133.146.172.198.211.237.289.302.328.380.393.406.458.471.484.497.523.549.562.575.588.601.614.627.653.666.679.718.757.822.835.848.861.1043.1056.1095.1807]] }.

Anyways, I hope this helps anyone else who has looked at bugpoint before and wondered "How do I actually use this tool to do something useful?".

Fun and games with assembly

This is a problem that came up during my research. Suppose I have a function foo whose assembly looks like the following:

foo:
  mov global($rip), %rax
  mov (%rax), %rax
  retq

Are the following two lines of code equivalent?

  /* defines somewhere */
  int val;
  extern int foo(void);
  /* actual code */
  asm("callq foo" : "=a"(val));
  val = foo();

The answer, as you might guess by the fact that I'm writing this post, is "no." The reason why is a lot more complex. In the case that caused me endless toil and grief, the function foo is not located in the same executable as the caller; it is in an external library file. Now, the platform ABI allows functions to clobber a fair number of registers which callers must assume are unusable. If the loader needs to perform work when calling a global relocated function, then it is a good idea to use those registers where possible, since you don't need to bother saving those values. When the asm construct is invoked, we've declared that only the return register is clobbered, so the compiler is free to store some values over the call. When the function call is direct and doesn't need to go through the GOT or anything similar, this is perfectly fine and works as one would expect. But if you need to invoke the loader when calling through the GOT, then you now have registers whose values have suddenly mysteriously changed on you when calling a function which doesn't (appear to) use them. Hope you have more fun debugging those cases than I did!

Achievement Unlocked: Use 100GB of memory in a single process

I discovered that the compiler I was using last night managed to run out of memory while compiling some code. This was on our research group's server which has a whopping 128GB of memory. And by "ran out of memory", I literally watched in top as clang went from dozens of megabytes of memory to 120GB of memory, evict everything from the cache and thrash swap like crazy before the out-of-memory killer decided it ought to go.

What was I doing? No, I wasn't linking the source code to the universe; I was merely compiling a file in the Spec 2006 benchmarks. And this wasn't anything large--only 3700 lines of code or so in a single C++ file. And the pass that wasn't dying wasn't some horribly written pass that leaked memory like a leaky bucket. Indeed, LLVM tends to get you to free memory too quickly, judging by how many times I've chased down memory corruption. If you don't believe me, the offending code was this:

    Code = CloneBasicBlock(CodeOrig, ValMap, "", F, NULL);
    for (II = Code->begin(), EE = Code->end(); II != EE; ++II) {
      if (!isa(II))
        RemapInstruction(II, ValMap, RF_IgnoreMissingEntries);
    }

For those of you who don't know what the code is doing, it roughly amounts to this: make a copy of a basic block of a function, and then tell all of the instructions to use the new instructions instead. On some programs, though, this simple instruction seems to have compelled the code to eat up gigabytes of memory.

Fortunately, I am now proud to announce that I have reduced my memory consumption by 99%… with a one-line fix. So I guess I should get the achievement for "Fix the Memory Leak" as well?