Last Comment Bug 507711 - (callgraph) Produce mozilla-wide callgraph for static analyses
(callgraph)
: Produce mozilla-wide callgraph for static analyses
Status: RESOLVED FIXED
: dev-doc-complete
Product: Core
Classification: Components
Component: Rewriting and Analysis (show other bugs)
: unspecified
: x86 Linux
: -- normal (vote)
: ---
Assigned To: dwitte@gmail.com
:
Mentors:
Depends on: 511520 511261 512033 512887 588002
Blocks: analyses 583074 512868
  Show dependency treegraph
 
Reported: 2009-07-31 14:31 PDT by dwitte@gmail.com
Modified: 2011-03-10 10:09 PST (History)
16 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments

Description dwitte@gmail.com 2009-07-31 14:31:50 PDT
A mozilla-wide callgraph would be a generally awesome thing to have. It's the first (and sometimes sufficient) step to solving static analysis problems such as bug 506027, where we want to answer the question "is it possible to call a locking function, transitively or otherwise, from within function foo".

Building up a callgraph of simple static function calls is fairly simple using treehydra. There are two complications I can see so far:

1) The virtual method implementor-interface model of xpcom. Figuring out which implementor class is involved in a particular interface method call is in general a dynamic problem that we cannot answer exactly. However, we certainly can answer it conservatively, i.e. "for interface method nsIFoo::bar(), find all classes that could possibly implement it".

For some interfaces, this is a silly question to ask - how many classes implement nsISupports::AddRef()? For such cases, we can try to do a bit of static analysis, since often (in fact, almost always) we will be starting from a more specific interface pointer, such as nsIFoo, which gets cast to nsISupports for the AddRef() call. In general though, we can't get an exact answer, and we might have to exclude things like nsISupports from analysis. (It's not exactly an interesting class to analyze, anyway.)

2) Function pointers. Basically the same as 1), we can look for all possible implementors of a function signature. If we can't be conservative, then we could also annotate nodes in the callgraph as "calls a function pointer/virtual method - may not be exact". For analysis purposes, knowing that the graph might not be complete is important, and would let us go manually annotate functions if we need to.

I have a static callgraph in hand, and I'm working on these two problems. It's generated with a treehydra pass that sticks data into a sqlite db, which can then be analyzed directly or graphed using dot.
Comment 1 David Mandelin [:dmandelin] 2009-07-31 15:10:37 PDT
Very cool. I agree with this approach. A few notes that may or may not be of use:

- It makes sense to annotate call sites that humans can resolve with the known type or the known target methods (I'm not sure which is better). There are two basic kinds of annotations: 'assume', which simply tells the analysis to assume that the annotation is correct, and 'assert', which requires the annotation to be correct. It would be nice if we could use asserts when we really think we do know the type, but I don't know if it's possible in C++ without RTTI.

- I think you referred to an example like this:

  nsIFoo *foo = ...;
  static_cast<nsISupports*>(foo)->AddRef();

and you said that it would be possible to infer that the receiver of |AddRef| is actually an nsIFoo. I would consider that to be a type of limited local (intraprocedural) points-to (aka 'alias') analysis. I agree that's the right place to start if you want to refine the analysis. It might also be possible to expand it a little larger (if necessary later) by looking into function calls one level or so or looking up (to the caller) a level.
Comment 2 Joshua Cranmer [:jcranmer] 2009-07-31 19:58:33 PDT
(In reply to comment #0)
> For some interfaces, this is a silly question to ask - how many classes
> implement nsISupports::AddRef()? For such cases, we can try to do a bit of
> static analysis, since often (in fact, almost always) we will be starting from
> a more specific interface pointer, such as nsIFoo, which gets cast to
> nsISupports for the AddRef() call. In general though, we can't get an exact
> answer, and we might have to exclude things like nsISupports from analysis.
> (It's not exactly an interesting class to analyze, anyway.)

I think that if we have to blacklist functions to ignore, the three nsISupports methods, as well as nsCOMPtr and nsRefPtr and the magic helpers for the above, are the best candidates, since pretty much everybody calls them, and those who are interested in such details would probably be better off having some hackish stuff around it.

From experience with doxygen's class inheritance and reference graphs, I would be willing to bet that leaving these in dot outputs can quickly make the graph confusing or annoying to read (see http://mxr.mozilla.org/comm-central/source/mailnews/base/public/nsIMsgFolder.idl for an example).

> 2) Function pointers. Basically the same as 1), we can look for all possible
> implementors of a function signature.

Couldn't you handle this by looking at assignments? I think all use of function pointers in Mozilla would fall into two categories:
A. Direct assignment with method handle
B. Return value of dynamical loader functions (e.g., dlsym)

For case B, I think it's rather outside our ability to handle, although annotating it with the code that assigns the function pointer value(s) might be helpful. Case A we can treat in much the same manner as your 1).

> I have a static callgraph in hand, and I'm working on these two problems. It's
> generated with a treehydra pass that sticks data into a sqlite db, which can
> then be analyzed directly or graphed using dot.

How does your dot grapher work? I'd imagine that the full callgraph would take forever to generate and be too large to actually load with any tool, so how do you specify interesting portions?
Comment 3 Benjamin Smedberg AWAY UNTIL 2-AUG-2016 [:bsmedberg] 2009-08-01 21:54:39 PDT
I think it's important to keep addref/release/qi in the dataset because they are potential points where you can enter script or enter locks. Note that if you are calling channel->qi the potential number of functions is smaller than nsisupports->qi
Comment 4 dwitte@gmail.com 2009-08-28 15:17:04 PDT
I've committed a prototype of this work. It runs over mozilla-central and can produce a database of all function and method calls, including those involving function pointers. It generates a sqlite db about 80Mb in size, with about 100k nodes and 300k edges. I've written up some basic installation and usage docs at

https://developer.mozilla.org/en/Callgraph

The schema is pretty simple at the moment, and I'm open to suggestions on how to improve it. As cjones mentioned offline, having a jsctypes-based API to access the database from within dehydra itself would be nice, to allow static analyses to leverage the graph.

I have a mostly-working implementation of function-local typewalking stuff as described in comment 1 (for virtual methods and function pointers) in my local tree, however it's missing an alias/points-to analysis. I'll attack that problem at some point (hopefully soon!).
Comment 5 dwitte@gmail.com 2010-09-09 17:17:51 PDT
This was fixed ages ago!
Comment 6 Benjamin Smedberg AWAY UNTIL 2-AUG-2016 [:bsmedberg] 2010-09-09 17:28:45 PDT
Where's the data? dev-doc-needed! I want a dump of this to be regularly available for specialized querying.
Comment 7 dwitte@gmail.com 2010-09-09 17:43:47 PDT
There are some docs at https://developer.mozilla.org/en/Callgraph, but I haven't touched them in a year, so they may be out of date -- Ehren has been making some changes to callgraph since then.

This is going to be backing DXR, which will serve for basic queries. We could make that data available for download, perhaps. This could also be done if we have the static analysis tinderbox run the script and upload the data.
Comment 8 Eric Shepherd [:sheppy] 2011-03-10 10:09:24 PST
I've added the NeedsTechnicalReview tag to these articles and am marking this as documentation complete, even though I have no idea if the stuff is actually current. Hopefully a tech review will resolve this once and for all!

Note You need to log in before you can comment on or make changes to this bug.