19
Sep 08

Outparamdelling this way comes

Recently I dusted off outparamdel to see if I can get some refactorings landed. About a year ago, with the great QueryInterface outparamdelling experiment we ended up with a smaller binary footprint and tiny performance gain, but that never landed due to us not wanting to break compatability yet. Ever since, outparamdel has been patiently bitrotting within Pork waiting for the day it’s allowed to break APIs.

Recently jst listed some private API candidates for deCOMtamination and I have been letting outparamdel loose on them for the past week. So far only one such change has been committed, the rest are sitting in jst’s review queue. It’s exciting, as it’s the first ever application of outparamdel that didn’t get canned. For the whole list see the most recent bugs blocking my analysis metabug.

Cool part about these patches is that after various outparamdel special-casing and manual cleanup the line count is reduced by 10-30% while maintaining existing functionality!

So far I haven’t touched much outside of content/, so if you know of any APIs that could have the outparam rotated into the return value, file some rewriting bugs against me.

Rewriting with Mercurial

Mercurial is now my favourite python program ever. It makes rewrites so easy. Here is my typical workflow:


# Write an outparamdel input file specifying functions to rewrite..run outparamdel with pork-barrel to generate patch
hg qimport -f autopatch.diff && hg qpush && hg qref #make the patch nice and readable
hg qnew manual.diff #create a manual cleanup patch for cosmetic touchups and rewrites screwed up by macros#of course to submit patch for review, those two patches need to be combined
#do manual stuff
hg diff -r 19277 #produce a combined diff without loosing ability to edit each applied patch individually! For example, can regenerate the autopatch.diff with different outparamdel parameters or a bugfixed outparamdel. 19277 is a revision that has to be looked up with hg log, unfortunately there isn't a relative syntax to do hg diff -r "tip - 2"

This is a huge improvement over the ad-hoc workflow prior to hg switch when I was prototyping my tools. CVS + quilt don’t hold a candle to a modern revision control system.

Prcheck

I also have been doing another round of prbool corrections. Somehow I didn’t notice that the system stopped working due to the CVS->hg switch. Once again when reviving my nightly checker scripts, it was a pleasure to substitute all of the CVS hacks with mercurial commands.

I am waiting for the few remaining largeish (ie 3-4 bugs per file) patches to land before I can start submitting whackamole bugs with a single prbool correction per module.

It also seems that cairo and every other pre-C99 project have the same set of issues as Mozilla with their typedefed-int boolean types. Perhaps prcheck isn’t mozilla-specific at all.


28
Dec 07

Recent Progress

Looks like pork is slowly going to get merged back into oink. This makes me happy as it will result in decreased merging headaches and gives more visibility to my work outside of Mozilla. My elkhound changes are already in!

Recently I added support for retaining gnu attributes to elsa and corresponding features dehydra and garburator. Now dehydra can verify things based on attributes and  garburator gained a way to rewrite special cases like classes that are always allocated on the stack. Elsa still drops most attributes, but at least classes, methods and variable declarations are covered.

I also spent a couple of days investigating gcc plugins. Turns out modifying gcc to support plugins is dead easy, but getting anything useful done in GCC requires a steep learning curve. I tried to find how to enumerate all of the toplevel declarations in the source, but I couldn’t find the correct global variable that corresponds to the toplevel scope(aka the Translation Unit?). I have a few more ideas of what to try next. Once I do that, it shouldn’t take much work to make a basic gcc-hosted version of dehydra. There is also a gcc plugin branch hosted in the gcc svn, but I can’t find any example code for it. It isn’t a big deal since none of the plugins I’ve seen mentioned venture outside of intra-function analyses.

I am still pondering on how to tackle rewriting Mozilla to use exceptions. It is the key to improving overall readability/perf of Moz C++, but the logistics of writing the corresponding analyses+rewrites followed by a parallel manual correction step are still making my head spin. All I’m sure about is that the first step to exceptions would be to enable the OOM exceptions and do the corresponding exception safe analysis+rewrite.


11
Dec 07

Switching to Exceptions: Makes Head Spin

Typical

It seems that there are 3 stages to doing a rewrite in Moz:

  1. Start a new tool. Make sure that it can rewrite some trivial testcases. Add lots of asserts for cases you are unsure about.
  2. Run tool on Mozilla and fix crashes caused by above asserts. Get 80% of the code rewriting correctly.
  3. Get the other 20% rewriting. This often involves major overhauls to rewriting logic due to patterns that weren’t expected when the spec was written

Usually stage 3 is a few times harder than 2. For garburator rewriting got really hard in stage 3. 90% of my time ended up being spent in stage 3 due to fun issues like figuring out what to do with unforeseen(in spec) combination of references and nsCOMPtr<>s.

Exceptions

With exceptions step 2 is already getting hard. So far I’ve had to extend elsa to support pattern matching,  and reworked the code patcher to support recursive rewriting.

Now looks like I’ll need to do some flow-sensitive analysis to rewrite cases like nsMemoryImpl::FlushMemory. I’m not sure if it is possible to automatically deal with functions like nsExceptionService::DoGetExceptionFromProvider.

Also, I’m not yet rewriting code to be bugfree, just trying to get it to compile. Once exceptioned code compiles, step two will be to statically check code to verify that it is exception-safe and convert it to RAII or something.

Here is an current patch for xpcom/ produced by thrower. At the moment there are still a lot of pattern matches to be added. It mostly handles rv = foo(); if (NS_FAILED(rv)) and a few other simple cases.

This is exciting stuff, but really hard, so if anyone has exciting problem solving ideas feel free to ping me.


05
Dec 07

Exceptional Circumstances

My previous post on outparam rewriting described the wealth of functions that can be rewritten. Unfortunately, most functions in Mozilla are declared in XPIDL interfaces.

I have been convinced that my plan to rewrite xpidlgen to avoid outparameters wont be possible because most XPIDLinterfaces can be implemented by JavaScript in a few different ways. That is problematic because in addition to return values, JavaScript can also have an exception thrown at any point and have that converted to an nsresult error code by XPConnect. That means that the getters implemented in JavaScript are not in the set of functions that only return NS_OK+outparam/someerror. I wouldn’t be at all disappointed if someone proved me wrong here.

nsexception

There is one other way to rid the code of outparameters (including getter_AddRefs and friends). Time to face my greatest reluctance: rewriting Mozilla to use exceptions. Brendan has been talking about it for a long time, but I have been skeptical until now, mostly due to the complexity of rewriting that much code. However, I have more confidence in rewriting huge amounts of code now since the XPCOMGC rewrite which touched most functions in Mozilla without too much trouble (in relative terms).

Motivation

There are some obvious benefits to be gained from switching to exceptions other than a reduction in code-size (and footprint?) and having code that looks more like common C++.

We would like to modify tamarin to use C++ exceptions such that an exception thrown from JavaScript would unroll the mixed C++/JS stack. This would simplify and enable significant optimizations for XPConnect.

I am dreaming of JITed marshaling code for C++->JS calls and having a low level FFI interface(ie being able to call most C/C++ methods directly) on the JavaScript side such that tracing JIT could automatically optimize common XPConnect calls. This an exciting area and there are lots of details to be worked out, so I’d love to see some feedback (or better yet proof of concept code!) on this.

The Plan – Rewriting

I have started implementing thrower (I am not a great namer), a tool for converting various code patterns involving nsresult into something that uses an nsexception wrapper.

Since this rewrite requires a lot more scanning for code patterns I added an elsa feature to allow pattern matching on AST nodes in C++ (also using exceptions). Since there are lot of patterns to transform, for documentation I will be writing many minimal testcases documenting(and testing) exactly what gets rewritten. Any interested parties are welcome to contribute Mozilla error handling patterns as testcases.

Verifying the Result

Just like in the XPCOMGC rewrite, code will have to be scanned to verify that it fits in the “new world order”. Unlike XPCOMGC, there are additional flow-sensitive issues to scan for to ensure that the code is thread-safe. The scans are at a lower level than dehydra currently works at, so it’s a perfect opportunity to either extend dehydra or write the new tool.

It would be especially cool to implement the code analysis tool as a gcc plugin.  Sean Callanan’s “Extending GCC with Modular GIMPLE Optimizations” paper in the GCC summit proceedings should be an excellent starting point.

This is an exciting experiment. I look forward to reducing speculation on the risks/benefits of switching the codebase to use exceptions with some concrete data.


12
Oct 07

Rewriting Tools for Mozilla 2: Moving Forward as Planned

In the Beginning There Was a Void

Approximately a year ago, Brendan discussed with me the crazy possibility of rewriting most of the Mozilla code automatically to modernize the codebase. The benefits were huge. Gecko would use the C++ standard library to improve code readability and reducing size, XPCOM would be ripped out of the core to improve performance and decrease footprint, etc.

It seemed like a good idea, but in reality no other giant C++ project has attempted this before so we were not sure of how realistic it was. I spent a year in a lonely corner of Mozilla trying to materialize the idea.

Brendan & Graydon pointed me to elsa, the C++ parser that supposedly could parse Mozilla. However, it turned out that it was only able to parse an old version of Mozilla and rejected the new source. One of the elsa maintainers even tried to convince us to it was not designed for source-to-source transformations and wouldn’t work that way.

After I patched up elsa and started devising ways to use it for source rewriting I ran into more pain. After a few false starts, I realized that C++ in Mozilla is actually a mix of CPP and C++ and one can not rewrite C++ without dealing with the mess that is macro expansion. MCPP was pointed out to me as a good starting point for hacking on a preprocessor. So I designed an inline log for macro expansion. To my surprise the maintainer of MCPP, Kiyoshi MATSUI, volunteered to implement the spec and thus saved me from a world of pain. (For which I am eternally grateful as I can’t imagine a more depressing pastime than working on the root of all evil: the C preprocessor).

In parallel with Kiyoshi’s work I modified elkhound & elsa to make the C++ parser a lot more suitable for source transformations. I learned about LR & GLR parsing and confirmed my suspicion that I don’t want to write parser generators for a living.

Happy Conclusion

All this work finally got us what we discussed last September: a framework for doing lots of boring code rewrites.

The first big Moz2 task is switching from reference counting to garbage collection. Today, garburator produced a gigantic patch for subset of the content/ module and all of the affected files compiled. Hopefully next week I’ll have a multi-megabyte patch for the whole of Mozilla that compiles and possibly runs.


10
Sep 07

Automatic DeCOMtamination: Roadmap For Automated Refactorings

This is an update on the ongoing deCOMtamination work from the automated rewriting perspective. I think it’s pretty exciting that Mozilla is the first large-scale C++ project to attempt automated large scale source code cleanups and optimizations. I think the tools are finally getting mature enough for the job.

The downside is that there isn’t a published roadmap of what we are planning to achieve with deCOMtamination as we are still in the planning stages. The upside is that there is still time for any interested parties to think up the next great improvement on how things are done, checkout the refactoring toolchain and either extend an existing tool or implement a new one.

Below is a list of things that I plan to have working in the near future. The idea is to try to implement various optimizations that would be impractical(or impossible?) to do manually and see if they yield the expected performance and code quality benefits.

Step 1: Outparam Elimination

QueryInterface() and other ok/fail methods have a redundant nsresult value which can be eliminated without changing any logic in the code. The QueryInterface() rewrite is my first serious tree-wide refactoring attempt. QueryInterface() is probably the most well known and frequently-used method within Mozilla. It also one of the most CPP-encumbered methods in the tree, so it made for a good test of my CPP-aware elsa work.

The getting code to compile phase is over. Currently Benjamin is working on getting the modified code to run which requires XPConnect changes, debugging the manually-rewritten macros and verifying that the generated patch is correct.

The next step will be to eliminate local nsresult variables in the callees when they are used to store & check return values of QueryInteface(). This is basically a make-resulting-source-look-prettier optimization.

I hope to measure a speed-up and slight footprint decrease with the new QueryInterface call.

Step 2: Try Mozilla Without Reference Counting?

In my mind the most exciting part of Moz2 is Tamarin. Few things are cooler than an elegant JIT VM.

Tamarin comes with a modern garbage collector.

The goal of this rewrite is to aid Jason and Benjamin with switching XPCOM from reference counting to garbage collection. This might end up in gigantic patches to rid the stack of nsCOMPtr objects. This might be hard as it will be affecting a lot of code and might reveal more shortcomings in my version of elsa and MCPP. Details are in the wiki.

Step 3: Try C++ Exceptions

This is the most ambitious rewrite I know of for Mozilla 2. It’s similar to step 1 in that the goal is to eliminate outparameters and nsresult error codes, except in this case it would happen for all functions. Brendan mentioned this is in his blog.

The idea is that exceptions in Mozilla happen in exceptional circumstances, thus most of the time the return value will be NS_OK and the outparameter will have something valid in it. So we should rewrite all methods that return nsresult to return the outparameter value through the return value and have the errors thrown as exceptions.

In the simplest case this would involve rewriting return statements into throw statements and rewrite callers to use try/catch. Instead of

rv = bla(&outparam)…if(rv == foo) .. else if(rv == boo) return rv

the code would be

try{ outparam=bla() } catch(foo) {…} catch(boo) {throw boo}

Note this is still inefficient since the code would be manually unrolling the stack instead of letting the exceptions do that. So the next iteration of the rewrite would get rid of the

catch(boo) {throw boo}

code to streamline the execution path. Ideally this would provide a significant reduction of footprint (due to getting rid of the error propagation code) and provide a speed boost.

However, there are a lot of issues that need to be solved. How to ensure that the C++ code is exception-safe (everything has destructors to do appropriate cleanup)? How to deal with the case of the stack being a mix of platform C, C++, JavaScript, Python, etc? Most runtimes are not aware of C++ exceptions.

Infrastructure Work

Unfortunately, not all of the automated refactoring work is about exciting rewrites. Elsa is still tied to the stone-age gcc 3.4 as it can’t yet process C++ headers from the newer gcc releases due to template complexity.

There is also work that needs to be done to get OSX supported as well as Linux by elsa & mcpp. I think very little work remains there.

Another big issue is getting elsa/mcpp to work on Windows. This may involve teaching elsa about the Microsoft windows flavour of C++ or getting Mozilla to reliably build with mingw and merely teaching elsa about mingw’s flavour of windows C++.

There is also an issue of maturity. Mozilla is probably the biggest codebase to make use of elsa and mcpp, so there are teething issues to solve. Having said that, the current version of MCPP in svn should be able to compile Mozilla. Elsa can process all of Mozilla with a small patch to two files attached in the QueryInterface() bug.

Overall I’m doing less and less infrastructure work as time goes by, hopefully the tools will mostly just work from now on.


30
Aug 07

Pork: The Brave New World

It doesn’t look like my oink patches are going to reach upstream anytime soon. In fact, in the past year no patches have landed in the oink tree. I think this is unfortunate, but I have my own repository at http://hg.mozilla.org and will continue working on my fork. So allow me to introduce Pork, the Oink fork. So if anyone has any exciting source location, pretty printing or other elsa improvements, I hope to eventually see those land in pork.

Note, pork is just an informal name for the fork, I am not currently planning to do any source renaming or repository renaming.

Pork: Now in a VMware flavour

bsmedberg pointed out that oink seems a bit intimidating to setup and it would be nice if it came in virtual machine. So I have oink/mcpp/etc packaged up in a virtual machine that can build Mozilla with gcc3.4, run dehydra analyses and produce automated patches. If you want to play with that, post a comment and I’ll reply with a download link.

A couple of people asked me about some simple code-scans to see for problems and optimization opportunities. Next week I am going to post few simple dehydra recipes on how to look for patterns in the code. It’s dead simple with JavaScript and some minimal shell knowledge to aggregate the results. The VM should provide a good way to get started.

Outparams: QueryInterface Rewrite Milestone Reached

I finally got Mozilla to compile with the outparam-less qi call. The outparamdel part of that was surprisingly easy and straightforward. I   also learned all kinds of fun details about multiple inheritance and fun ways to construct functions out of macro segments. The next step is to get the code to run. I’ll also have to look into a few minor MCPP issues that the rewrite uncovered. See QI bug for the gory details.


06
Aug 07

Outparams: Take 2

Will Rid Code of Outparams!

I resumed my outparam rewriting work last week. Having fixed the CPP induced architectural limitation that I ran into, it was quite straight-forward to factor out squash’s rewriting code into a new tool. Unlike squash, outparamdel (creatively named new tool), can rewrite code precisely and reliably. I still don’t have end-of-ast-node information in every Elsa AST member, but I think I have added position info to enough AST nodes to be able to do most of the Mozilla 2 rewrites.

Continue reading →


01
May 07

Status Report

Automated Analyses and Rewrites

Dehydra and Squash are now mature enough to assist with mundane tasks like renames and various kinds of tedious code inspection. If you ever suspect that part of the Mozilla hacking you are doing could be done by a tool, contact me to see if I have a suitable tool for you.

Also, these tools are in no way limited to working with Mozilla source code. I would be happy to see people use them for other projects too.

Short-term Plans

For the next week or two I plan to focus on out-parameter rewriting and the Mozilla-wide C++ callgraph.

Mozilla-wide Callgraph
This is proving to be a little painful. Things work for basic test-cases, but I am running into scalability issues with Mozilla (as expected). My current approach of serializing everything into a giant JSON graph blows the 32bit address space after a few hundred files. Even doing a Mozilla-wide inheritance graph causes out of memory errors, but that runs almost to competition. The best solution to this will be to break up the graph into as many smaller JSON files as possible and only load ones that are absolutely required into memory.

The callgraph will be a useful starting point for many other useful analyses (dead code one is going to be lots of fun) and it’s a good test of dehydra’s scalability, but I have suspended work on it for a few days to focus on more productive tasks.

Out-parameter Rewriting

Due to XPCOM, Mozilla getters typically return an error code and a value via an out parameter. This requires checking the error code and likely propagating it at the callsite.

For many places in the code there are performance and aesthetical reasons to stop using error codes. Brendan talks discusses some reasons here. This would be cool stuff, but switching to exceptions isn’t going to happen right away. However, I can already start working on my tools to assist with simpler cases (like nsBidiPresUtils::GetBidiEngine?). I’m focusing on getters that return NS_OK/(some error) and a value and rewriting them to return NULL on error and non-NULL on success. This could be ready in time for Firefox 3. Once I’m done with the tool, I’ll just need someone to help me figure which functions are ok to simplify like that.

I suspended work on out-param rewriting some time ago. It was proving to be too complicated to do within squash. Now that I can use dehydra to verify the control flow graph, things are a lot simpler. Current plan is to have the dehydra script produce a list of candidates for out-param surgery and have squash consume that list and produce the appropriate patches. Currently, the script works for some very simple cases and I am working on the squash side.

Smaller Tasks

  • Sayrer’s uninitialized member analysis: added more complete constructor support to dehyra, wrote a sample script to get sayrer started. Fixed dehydra’s 64bit support. Bug 378763
  • Made some squash-generated patches for bz, helped me find a bug in squash. Bug 378780
  • Pushing squash upstream into oink. This is time consuming because it is a combination of legal and many minor technical issues. Dehydra will follow later.

02
Apr 07

Automated Code Refactoring

Squash

If you are working on any C++ refactoring, especially if it involves function calls, spans multiple files or feels like you need a compiler in your head to help you, drop me a note to see if squash can help. Squash provides a great deal of control over the refactoring process because it is not tied to a particular IDE and can be customized to accommodate for special cases.

On Friday, two squash-produced patches landed:

  1. A 212K patch to rename nsIFrame::GetPresContext to PresContext. It took a couple of minutes to produce a patch for mac & linux, and then some manual labour to complete it so it builds on Windows too. Unfortunately, Microsoft C++ is not yet supported by Oink. Windows-specific code will require magnitudes more of human labour until such support is contributed.
  2. A much simpler patch to calls to remove uses of the deprecated ::Recycle(). This took a few minutes once I added support for renaming global functions to squash.

Dehydra

C++ support in dehydra is coming along splendidly. I started working on cross-function analysis support. Currently my goal is to allow the user to build callgraphs of Mozilla. The first application of that is going to be dead code detection.

In the meantime, contact me if you are looking for patterns in the code that grep wont help with : control flow-sensitive code, type & syntax-aware matching, API misuse, etc. Dehydra can probably help.