Main menu:

Site search

Categories

Archive

nothrow/NS_OK-always

Yay, my first Mozilla blog post! Brief background: I’m working on static analysis-related Mozilla projects with tglek. In fact, I seem to have already become a maintainer of Pork-Oink and Dehydra Classic.

Anyway, right now I’m trying to finish up a static analysis that will list all the nsresult-returning methods that always return NS_OK (i.e., “never” “fail”) and will also say for each nsresult-yielding call site in Firefox whether that call site always returns NS_OK. The initial purpose was to help determine the feasibility of switching Firefox to use C++ exceptions instead of nsresults. If a method returns NS_OK, the switch is easy, because no exception handling is needed at all. This work also overlaps with the outparamdel project, which will convert methods that return a value in an out parameter and always return NS_OK  into methods that return a value directly. As a final application, I hope to be able to get a reasonably accurate list for each method of which error codes it can return.

Here’s an outline of how it works. I started by solving a simplified version of the problem, which is to get all the NS_OK-always methods that don’t call other methods. This is a lot easier than the general problem because each procedure can be analyzed in isolation. To solve this simple version, I used a flow-insensitive analysis, which is just a fancy way of saying the analysis doesn’t care about control flow paths or the order in which statements are executed, which is in turn just a fancy way of saying I used what most people think of as a type checker. The type system applies to nsresults only, so a type is just a set of nsresult values. Based on that type system, I wrote a simple type inference, and the type inferred for the return value of the method tells me what nsresults can be returned.

The next step is extending the analysis to cover the case where method foo() returns the result of calling method bar(). The way to do this, of course, is to first analyze bar(), then assign the return type of bar() to the call inside foo(), then analyze foo() normally. But this won’t actually work until 2 problems are solved.

First, many methods in Firefox are virtual, so when you see a call to Base::foo, the method being called could be Derived::foo, Derived2::foo, etc. So there might be more than one target method, and it’s not obvious what the targets are. The solution is to start by building a call graph for Firefox, which just means a mapping from each call site to the set of possible target methods. There are many ways of building call graphs, but I started with the simplest, which is just to look at the inheritance hiearchy. (More powerful analyses analyze the code around the call site to try to figure out exactly which derived classes can actually show up there. But that’s too hard for now.) So, as a byproduct of the NS_OK analysis, I also have data that can be used to build a call graph for Firefox, which might be useful for cross-reference documentation. (I didn’t bother building the call graph yet because for this analysis all I need is a database that I can query to get call graph information for nsresult methods only.) It might be nice to have a web app that gives call-graph cross-references and results of other program analyses we devise.

The second problem is that methods can be mutually recursive: foo() might return the result of bar(), which can return the result of foo().  Clearly, my suggestion above of analyzing one of the methods first won’t actually work in this case, and this case is common in Firefox, so I have to do something else. The something else I have in mind is to express the problem as a subset-based constraint system, which I can explain best by an example. Let’s say we have foo() and bar() as above, and foo() can directly return NS_OK and NS_ERROR1, and bar() can directly return NS_OK and NS_ERROR2. The key thing about foo() returning the value of bar is that whatever the set of results foo() can return actually is, it has to contain the set of results that bar() can return. We can express everything we know as a constraint system:

foo_results contains { NS_OK, NS_ERROR1 }

foo_results contains bar_results

bar_results contains { NS_OK, NS_ERROR2 }

bar_results contains foo_results

The answer to our original question, what values can these methods return, is the least solution of this constraint system. (Least means with the smallest sets in the answer.) We can read off the answer here by hand, but for Firefox, the system will be much bigger and so we need an automatic solver.  The basic solver algorithm is very elegant:

  initialize solution to empty set for every return-value set
  repeat
    for each constraint C:
      if C is not satisfied in the current solution:
        add elements from contained set to the other to satisfy C
  until all constraints are satisfied.

The proof that this algorithm is correct is also elegant: (a) Clearly, if it terminates, all constraints are satisfied. (b) If we ever reach the point where every return-value set contains every possible error value, all constraints are satisfied, because they’re all “contains” constraints, so the algorithm terminates. (c) Each time around the loop, we add at least one element to some answer set, so can go at most a finite number of steps before reaching the all-value solution, where the algorithm stops.

It took me all of 15 minutes to code this algorithm in Python, and it works (after I fixed a bug with having the termination condition be the opposite of what it should be). But will it work on all of Firefox? If there are N nsresult methods (N~=30000, by the way), M constraints, and K possible error values, then we can go around the loop up to NK times and the inner loop NMK times. Each time through there we have to do a binary set operation on sets of size K, which we’ll pretend is O(K). Thus, the algorithm is O(NMK^2). That might be a big number for Firefox.

I know a few tricks for speeding up the basic solver, but my goal here is to analyze and refactor Firefox, not write awesome constraint solvers, so I’ll try the simple stuff first and use the easiest thing I can get away with.  In particular, there’s an existing solver called Banshee. Or maybe the Python program will be fast enough after all.

The long-term goals here are to remove nsresults from Firefox and replace them with C++ exceptions. (See also outparamdel.)  (And of course we’ll have to test exceptions in various ways to demonstrate that they actually are a good idea. But I’ve been told several times exceptions would make life easier for Firefox hackers.) There’s a lot more to be done to reach that goal, which will hopefully be the subject of future blog posts.

Comments

Pingback from Taras’ Blog » Blog Archives » GCC + SpiderMonkey = GCC Dehydra
Time: January 17, 2008, 4:16 pm

[...] tuned for more exciting developments regarding regaining control over source code here and on Dave Mandelin’s blog. Posted in dehydra | Trackback | del.icio.us | Top Of [...]

Comment from Joshua Cranmer
Time: January 17, 2008, 5:33 pm

Considering that I’m looking at writing a zealous static analyzer for Java involving keeping tight bounds on the values of inputs, I’ve thought about how best to deal with such recursive loops. This is the scheme I’ve come up with:

1. Initialize the parameters to the empty set for input values and the default value for output values for each function.
2. Create a processing queue for all functions.
3. While the queue is not empty, for the next function:
3a. Update the possible values for the function based off of the values we see.
3b. If the output values have changed, then we add to the queue (if not already there) all functions which rely on the current function.

(For analysis, N = function #, M = function calls/function, K = output values/function)
Steps 3a and 3b should be O(M) for each function (assuming that we have an O(1) function f is in the queue); steps 1 and 2 can be combined into one O(N) operation. I count that the maximum number of times a function can be pushed into the queue is O(N*K), so that the total runtime comes to be O(N*K*M), an improvement by one power of K, which I expect is less than 10 anyways.

Pingback from GCC + SpiderMonkey = GCC Dehydra · Get Latest Mozilla Firefox Browsers
Time: January 17, 2008, 6:58 pm

[...] tuned for more exciting developments regarding regaining control over source code here and on Dave Mandelin’s blog. addthis_url = ‘http%3A%2F%2Fgetfirefoxbrowsers.com%2F2008%2F01%2Fgcc-spidermonkey-gcc-dehydra'; [...]

Pingback from GCC + SpiderMonkey = GCC Dehydra · Get Latest Mozilla Firefox Browsers
Time: January 23, 2008, 5:06 am

[...] tuned for more exciting developments regarding regaining control over source code here and on Dave Mandelin’s blog. addthis_url = ‘http%3A%2F%2Fgetfirefoxbrowsers.com%2F2008%2F01%2Fgcc-spidermonkey-gcc-dehydra-2′; [...]

Comment from travesti
Time: November 13, 2009, 11:52 am

THANKS

Comment from escort bayan
Time: December 17, 2009, 7:12 pm

thanks admin

escort bayan

escort bayan

Comment from Escort Bayan
Time: January 19, 2010, 5:16 pm

Thanks admin

[url=http://www.escortbayanlariz.biz/]Escort Bayan[/url]

Comment from Escort Bayan
Time: January 19, 2010, 5:17 pm

THANKS

Comment from escort bayan
Time: February 23, 2010, 12:43 pm

thanks all admin

Comment from escort bayan
Time: February 23, 2010, 12:44 pm

Thanks admin

[url=http://www.escortbayanlariz.biz/]Escort Bayan[/url]

Comment from unutulmaz
Time: February 28, 2010, 6:37 pm

Considering that I’m looking at writing a zealous static analyzer for Java involving keeping tight bounds on the values of inputs, I’ve thought about how best to deal with such recursive loops. This is the scheme I’ve come up with:

Comment from Rahim Ağzı Kanseri
Time: March 24, 2010, 10:15 am

Thank you for the services you offer

Comment from escort bayan
Time: April 18, 2010, 5:09 pm

thanks so much all admin

Comment from bayan escort
Time: April 25, 2010, 2:01 pm

thanksss admın

Comment from Indonesia Furniture Handicraft Wholesale Marketplace
Time: June 1, 2010, 1:23 am

Good….

Comment from tracker
Time: July 14, 2010, 9:30 pm

I like your article. its very beneficial.

Comment from unblock drain Berkshire
Time: July 20, 2010, 8:22 am

I get your idea.

Comment from Gezonde Voeding
Time: July 24, 2010, 2:58 am

This Information is very useful for me coz i was looking for this information this all week :)
Thanks david.

Comment from adult adhd treatment
Time: July 29, 2010, 1:50 pm

great! thank you david for this another helpful post.

Comment from Bastrop Club
Time: August 6, 2010, 10:06 pm

I want to say gracious for an interesting place about a something I have had an interest in for many years now. I have been lurking and reading the posts frequently and just wanted to thank you for providing me with some very good articles. I anticipate more, and taking a more active role in the conversations on your site.

Comment from psychologue
Time: August 15, 2010, 3:30 am

very nice post, thanks

Comment from Voeding
Time: August 21, 2010, 11:07 pm

Thanks for this valuable information, many thanks to you for sharing this to us.

Comment from indonesia furniture handicraft wholesale marketplace
Time: August 30, 2010, 5:00 pm

This is a really good read for me, Must admit that you are one of the best bloggers I ever saw.Thanks for posting this informative article

Comment from Chiptuning Box
Time: September 2, 2010, 12:28 am

thanks so much all admin

Comment from bwin
Time: September 10, 2010, 7:30 am

Excellent post, thanks for information.

Comment from cna classes
Time: September 14, 2010, 12:27 am

I started by solving a simplified version of the problem, which is to get all the NS_OK-always methods that don’t call other methods.

Comment from local jobs
Time: September 15, 2010, 11:54 pm

I hope to be able to get a reasonably accurate list for each method of which error codes it can return.

Comment from paris en ligne
Time: September 16, 2010, 4:20 am

Nice post very interesting, thanks.

Comment from Las Vegas Real Estate
Time: September 16, 2010, 10:07 pm

While the queue is not empty, for the next function:
3a. Update the possible values for the function based off of the values we see.

Comment from sajoo bonus
Time: September 17, 2010, 12:17 pm

Great news, some has to be still improved but hiwever very nice.

Comment from Chiptuning
Time: September 21, 2010, 11:12 pm

thank you david

Comment from sports betting online
Time: September 23, 2010, 5:40 am

Great web page! I don`t imagine Ive seen every one of the angles of this theme the way in which you`ve pointed them out. You`re a accurate star, a rock star guy. You`ve got a great deal to say and know so much about the subject that i think you ought to just teach a class about it.

Comment from binary option
Time: September 25, 2010, 11:39 am

Fantastic and I’m pretty very much pleased to get all that at a time as the web log has just outmatched my anticipations and prospects on all the imaginable life asoects.

Comment from Sonneries Gratuies
Time: September 27, 2010, 6:06 pm

I admit, I have not been on this webpage in a long time… however it was another joy to see It is such an important topic and ignored by so many, even professionals. professionals. I thank you to help making people more aware of possible issues.Please click here: Sonneries Gratuies

Comment from Mobile broadband uk
Time: September 29, 2010, 8:48 pm

When we talk about the nsl selection, this interface allow you to manipulate and querying the selected range of nodes with in the document. It is scriptable.

Comment from online degrees
Time: October 10, 2010, 8:07 am

the result of calling method bar(). The way to do this, of course, is to first analyze bar(), then assign the return type of bar() to the call inside foo(), then analyze foo() normally.

Comment from HTML background color
Time: October 10, 2010, 11:19 am

Hi, nice post. I’ve been wondering about this issue, so thanks for posting. I’ll definitely return to your site.I like how you sent your information with excellent detail. Keep up the great work here.

Comment from Links to Las Vegas Carpet Cleaning
Time: October 10, 2010, 11:20 am

This article gives the light in which we can observe the reality. This is very nice one and gives in depth information. Thanks for this nice article. Good post Valuable information for all.

Comment from natural skin care products
Time: October 11, 2010, 9:44 pm

I’m looking at writing a zealous static analyzer for Java involving keeping tight bounds on the values of inputs, I’ve thought about how best to deal with such recursive loops. This is the scheme I’ve come up with:

Comment from san diego injury attorneys
Time: October 12, 2010, 10:26 am

Pretty good post. I just found your site and wanted to say that I have really enjoyed browsing your posts.In any case I’ll be subscribing to your blog and I hope you post again soon

Comment from TV Reparatur Berlin
Time: October 13, 2010, 12:43 pm

A Very interessting Article. Thank you for this Admin

Comment from TV Reparatur Berlin
Time: October 13, 2010, 12:47 pm

Thanks Admin

Comment from Jura Reparatur Berlin
Time: October 13, 2010, 12:49 pm

This article gives more than a light

Comment from luxury townhomes jacksonville
Time: October 14, 2010, 9:25 pm

Nice to be here.. I started by solving a simplified version of the problem, which is to get all the NS_OK-always methods that don’t call other methods.

Comment from Pari Mutuel Urbain
Time: October 20, 2010, 11:12 am

This article gives a lighthouse ;) (to Jura Reparatur Berlin)

Comment from Betclic france
Time: October 20, 2010, 11:14 am

Hello world section… lol

Comment from Dental Marketing
Time: October 21, 2010, 12:52 pm

This is a really good read for me, Must admit that you are one of the best bloggers I ever saw.Thanks for posting this informative article.

Comment from Las Vegas Carpet Cleaning
Time: October 21, 2010, 1:44 pm

This post shows the information which is close to standard.
Hope next You will again post a nice Artical/Information

Comment from Notebook Reparatur
Time: October 22, 2010, 3:57 pm

This blog is very very interesting for me. Thank you Admin.

Comment from Delonghi Kaffeemaschinen Reparatur
Time: October 22, 2010, 4:05 pm

We need more posts like this. Good work admin.

Comment from Gebrauchte Waschmaschine
Time: October 23, 2010, 5:42 pm

This is true. We can express everything we know as a constraint system!

Comment from LCD TV Reparatur Berlin
Time: October 23, 2010, 5:45 pm

Thr Article about working on static analysis-related Mozilla projects with tglek is very good. Thats good work Admin

Comment from woodworking plans
Time: October 24, 2010, 2:25 pm

very nice article

Comment from payday loans online
Time: October 24, 2010, 3:33 pm

Thanks for such a useful article here. I must say that your blog is the first one where I have found something like this. Thanks for publishing this one here and keep posting such a great stuff in the nearest future too. Good luck!

Comment from resume writing
Time: October 25, 2010, 2:32 am

I did like your first mozilla blog post. It is important to choose a perfect writer for your resumes and we have professionals working with us.

Comment from bingoonline
Time: October 25, 2010, 7:17 am

This is a good post. This post give truly quality information.I’m definitely going to look into it.Really very useful tips are provided here.thank you so much.Keep up the good works

Comment from Dental Marketing
Time: October 25, 2010, 8:27 am

Took me time to read all the comments, but I really enjoyed the article. It proved to be very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed…..

Comment from wireless intercom system
Time: October 25, 2010, 9:10 am

I can feel the passion of poet with this poem where as I don’t like to compare this poem with any other poem because comparing it could lose the value of it.

Comment from best seo firm
Time: October 25, 2010, 8:47 pm

Thanks for the amazing article here. I was searching for something like that for quite a long time and at last I have found it here. Your blog is better than others because of useful and meaningful posts. Keep posting them in the future too, I will be waiting for that!

Comment from Dental Marketing
Time: October 26, 2010, 11:31 am

I am happy to find this post very useful for me, as it contains lot of information. I always prefer to read the quality content and this thing I found in you post. Thanks for sharing

Comment from pakistan law
Time: October 27, 2010, 9:05 am

nice to first post of wordpress in this blog, have fun

Comment from Norwesco Tanks
Time: October 28, 2010, 6:19 am

I am very happy to find this blog and want to thank you for giving me opportunities to say over it. I liked this useful blog. thanking you….

Comment from buy tramadol no prescription
Time: October 30, 2010, 3:53 pm

The experience and learning from being a medical assistant is useful in pursuing a career track for nurses.

Comment from rachat de credit
Time: November 1, 2010, 1:23 am

this website is very interesting. Continue

Comment from car games
Time: November 1, 2010, 6:19 am

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts.Any way Ill be subscribing to your feed and I hope you post again soon

Comment from escort bayan
Time: November 5, 2010, 4:14 pm

individuals and agencies in the province of Alberta.

Comment from hosting
Time: November 5, 2010, 9:50 pm

You also know how to make people rally behind it, obviously from the responses taking time and real effort to make a good article !!

Comment from sesli sohbet
Time: November 6, 2010, 11:52 am

Hello world section… lol

Comment from website icons
Time: November 7, 2010, 3:42 pm

Your post is rocking and knowledgeable. I really appreciate the way you write to mention nothrow/NS_OK-always . It is pretty big . I would like to read more from you.

Comment from Essay
Time: November 7, 2010, 9:37 pm

An informative post. I like it because of the quality writing.

Comment from free icon maker
Time: November 10, 2010, 8:19 am

Interesting post and thanks for sharing. Some things in here I have not thought about before.Thanks for making such a cool post which is really very well written.will be referring a lot of friends about this.Keep blogging

Comment from dui lawyer nevada
Time: November 12, 2010, 4:59 am

Hey everyone. Interesting idea for a blog. I have been checking out a lot of blogs and forums recently. Some are really informative some are entertaining and some are a real crack up. I’ve got to admit it, good job on this blog, I’ll be sure to look in again real soon.

Comment from organic recipes
Time: November 12, 2010, 5:33 am

Thank you so much for your work on keeping the site together and keeping these post flowing.

Comment from Fussbodenheizung
Time: November 12, 2010, 3:12 pm

Thanks for the good information.

Comment from medical training
Time: November 15, 2010, 3:38 am

There’s a lot more to be done to reach that goal, which will hopefully be the subject of future blog posts.

Comment from medical training
Time: November 15, 2010, 3:39 am

thanks for sharing the lots of info..

Comment from free icon maker
Time: November 15, 2010, 9:26 am

This post shows the information which is close to standard.
Hope next You will again post a nice Artical/Information

Comment from hiiiiiii
Time: November 15, 2010, 10:03 am

ggggggggggggg

Comment from global
Time: November 15, 2010, 12:38 pm

I am happy to find this post very useful for me, as it contains lot of information. I always prefer to read the quality content and this thing I found in you post. Thanks for sharing
Sweet pick up lines

Comment from seminyak villas
Time: November 15, 2010, 2:25 pm

The post is written in very a good manner and it entails many useful information for me. I am happy to find your distinguished way of writing the post. Now you make it easy for me to understand and implement the concept. Thank you for the post.

Comment from kratom powder
Time: November 15, 2010, 11:28 pm

Great site…..

Comment from link building services
Time: November 16, 2010, 2:47 am

Few lines that i read more than one time apart from the lines describing the actual moment of aforesaid article.

Comment from GLOBAL
Time: November 16, 2010, 4:50 am

I recently came across your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading aluminum 2014

Comment from aluminum 2014
Time: November 16, 2010, 4:51 am

I am happy to find this post very useful for me, as it contains lot of information. I always prefer to read the quality content and this thing I found in you post. Thanks for sharingaluminum 2014

Comment from icon editor
Time: November 16, 2010, 7:13 am

Interesting post and thanks for sharing. Some things in here I have not thought about before.Thanks for making such a cool post which is really very well written.will be referring a lot of friends about this.Keep blogging

Comment from mens ties
Time: November 16, 2010, 8:32 am

Yes i also do love bloging and found it really interested to read posts related to blogs, well i dont have a blog, i do work for blog and i wish i may have a blog, like this.

Comment from seamless tubing
Time: November 16, 2010, 10:38 am

Hey everyone. Interesting idea for a blog. I have been checking out a lot of blogs and forums recently. Some are really informative some are entertaining and some are a real crack up. I’ve got to admit it, good job on this blog, I’ll be sure to look in again real soon.

Comment from Garage Cabinets
Time: November 16, 2010, 7:19 pm

I remembered my first blog post, I was so happy, it is amazing when you look back over your blog how much your writing style will develop and improve.

Comment from Mercedes limo Chicago
Time: November 17, 2010, 10:53 pm

I high appreciate this post. It’s hard to find the good from the bad sometimes, but I think you’ve nailed it! would you mind updating your blog with more information?

Comment from adult products
Time: November 20, 2010, 5:46 am

Very useful and informative publication indeed. I have to admit that I always follow your blog because it is full of various and useful information about everything. Well, it was quite interesting to read this your article about the Firefox and its components. Actually, I am very interested in this sphere and reading this post I have known many new things, which I have not known before. Thanks for publishing this great article here, without you I would never known about such a thing ever. Mike.

Comment from mens ties
Time: November 20, 2010, 8:31 am

I am glad to find this blog and great information , david u r great, good knowledgeable man, keep it upp

Comment from Pay as you go cell Phones
Time: November 21, 2010, 9:10 pm

The example above is something that I worry about as well, how to show your own genuine enthusiasm and share the fact that your product is useful in that case

Comment from roxxky
Time: November 22, 2010, 12:36 am

This post shows the information which is close to standard. Hope next You will again post a nice Article/Information.
link building services. seo

Comment from seo
Time: November 22, 2010, 12:37 am

I always follow all your news but this one I have missed. It is really a new fact for me about Trojans and I will definitely try to find more publications about her. Well, I have to admit that she is really a beautiful woman and personally I think that she is very similar like Alexis Texas! Look at her. Anyway thanks a lot for sharing these wonderful news. seo

Comment from pasadena plumber
Time: November 22, 2010, 4:03 pm

Congratulations on your first post. WordPress and Mozilla need to team up, to become a superplatform that results in Technological singularity….SO WE BECOME THE COMPUTER

Comment from Saeco Reparatur Berlin
Time: November 22, 2010, 4:22 pm

Vielen Dank aus Berlin an die macher. Gute Arbeit

Comment from Online Casinos
Time: November 23, 2010, 11:59 am

Thank to the post. I really loved reading your blog. It was very well authored and easy to understand. Unlike additional blogs I have read which are really not good. I also found your posts very interesting. In fact after reading, I had to go show it to my friend and he enjoyed it as well!

Comment from porn stars
Time: November 24, 2010, 12:14 pm

Great job on this post man! I haven’t read a very informative article like this. Amazing.!

Comment from burbank plumber
Time: November 24, 2010, 4:10 pm

Here’s to you, the first post ever!

Comment from Sample Customer Services Resume
Time: November 25, 2010, 8:16 am

Thank to the post. I really loved reading your blog. It was very well authored and easy to understand. Unlike additional blogs I have read which are really not good. I also found your posts very interesting. In fact after reading, I had to go show it to my friend and he enjoyed it as well!

Comment from business analyst
Time: November 25, 2010, 12:54 pm

I recently came across your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading

Comment from aluminum 7075
Time: November 26, 2010, 10:43 pm

Nice post to hang on..I really loved it the way of the stuff provided in this article..This has given very useful information..

Comment from Mensagens para orkut
Time: November 27, 2010, 3:45 am

Great nice to know!