dwitte@gmail.com Assignee
	Description • 15 years ago

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.

	David Mandelin [:dmandelin]
	Comment 1 • 15 years ago

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.

	Joshua Cranmer [:jcranmer]
	Comment 2 • 15 years ago

(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?

	Benjamin Smedberg
	Comment 3 • 15 years ago

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

	dwitte@gmail.com Assignee
	Comment 4 • 15 years ago

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!).

	dwitte@gmail.com Assignee
	Comment 5 • 14 years ago

This was fixed ages ago!

	Benjamin Smedberg
	Comment 6 • 14 years ago

Where's the data? dev-doc-needed! I want a dump of this to be regularly available for specialized querying.

	dwitte@gmail.com Assignee
	Comment 7 • 14 years ago

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.

	Eric Shepherd [:sheppy]
	Comment 8 • 14 years ago

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!