[cfe-dev] Removing "TransferFuncs" from the analyzer

[Ted Kremenek]

Hi Jordy,

Sorry I took so long to reply to this.  As you know I've been occupied these last few weeks.  This email also touched on some really core topics in the analyzer's design, so I wanted to take the proper time to respond to it in detail.

Comments inline.

On Jun 27, 2011, at 7:35 PM, Jordy Rose wrote:

> Hi Ted and cfe-dev. In my free time I've been looking into the issue of "transfer functions" in the analyzer — a supposedly swappable implementation of logic for evaluating function calls and Objective-C messages, among other things. As the Checker infrastructure has grown, almost all of the once-unique transfer function logic can now be implemented using essentially-pluggable Checkers.
> 
> That wouldn't be such a problem, except that in reality the implementation of TransferFuncs in the analyzer is CFRefCount, which mixes in a whole bunch of logic for tracking retain counts and Cocoa conventions. We shouldn't need to run that with every run of the analyzer (though most of the code will early-exit when it realizes it's not relevant). Some of the code has already been extracted to a class called RetainReleaseChecker, but at this point we can do a lot more.

A bit of history first.

GRTransferFuncs was the original "checker" interface.  It was the plugin callback logic from GRExprEngine to something outside that defined the domain-specific checker logic.  I knew it would one day grow into something else, but I wanted to keep the checker logic separate from the core analysis engine, and GRTransferFuncs was a nice abstraction that serviced to provide the hooks for abstracting out checker logic.

Now we have the Checker interface, would allows us to define multiple checkers that run together.  The Checker interface doesn't fully replace GRTransferFuncs, but I don't think it should.  I see two possible directions:

(a) Move all retain/release checker logic out of a GRTransferFuncs subclass (where it is now) into RetainReleaseChecker.  The remaining logic, which really concerns core analysis logic (e.g., ivar invalidation), gets moved to GRExprEngine.  We then remove GRTransferFuncs entirely.

(b) Move all retain/release checker logic out of a GRTransferFuncs subclass into RetainReleaseChecker.  Instead of moving the remaining logic into GRExprEngine, however, we keep a simplified GRTransferFuncs around.

Personally, I think we should move in the direction of (a), because what will be left in the GRTransferFuncs subclass after we move all the retain/release logic out of it will be fairly fundamental stuff to the analyzer.  I also think (b) adds another conceptual entity to the codebase that isn't necessarily needed.

That said, let's explore more what you propose, and go from there.

> 
> This e-mail is recording my thoughts on this and how far I got; it's not intended as an immediate call to action.
> 
> In fact, the behavior of a hypothetical SimpleTransferFuncs only includes this:
> - Invalidating ivars of ObjC message receiver
> - Invalidating ivars of 'this' for C++ method call
> - Invalidating function/method args
> - Invalidating globals if necessary
> - Conjuring return values
> 
> And these effects only happen if no checker claims "evalCall" for a given function call.

Indeed, but why not just move these into GRExprEngine entirely?  Why do we even need a SimpleTransferFuncs?  The only reason to have a GRTransferFuncs interface is if we want the option to swap something else in its place in the future.

So why might we want to do this?  Well, there is the open issue of inter-procedural analysis.  One way to do that would be to swap in a different GRTransferFuncs.  But I honestly don't think that's the right direction.  I think inter-procedural analysis will be a core part of the analyzer engine.  Yes, we will likely modularize it, perhaps making the inter-procedural analysis configurable, but GRTransferFuncs isn't that mechanism.  GRTransferFuncs was meant to capture domain-specific checker reasoning, and we have something better for that now: the Checker interface.

> 
> 
> On the other hand, a fully-fledged RetainReleaseChecker with all existing functionality isn't quite possible because of four things:
> 
> - CFBugReports use function call summaries to show the retain/release history of a leaked object. Function summaries are currently associated with ExplodedNodes in a DenseMap. In addition to being somewhat inefficient (summaries for calls that have nothing to do with ref-counting are also saved), Checkers are const, and so can't store summaries in a mutable data structure. (Marking the map 'mutable' doesn't feel like the right solution.) I don't have a solution for this.

I don't actually see an issue here, but I recognize your concerns.  Let's separate your two statements.

First, the primary and original role of the function summaries is to memoize the behavior of a function/method call for quick application during evalCall.  It's a computational hack.  I should add that Checkers are not strictly const.  They are allowed to contain data.  What they shouldn't record is data specific to analyzing a given function or path.  All that data should be in GRState.  There is no reason, however, that Checkers cannot have any on-the-side data to cache computation that they do over and over again, particularly if it has nothing to do with a specific path.

Note that we will likely continue to add new ways for Checkers to have on-the-side *context-sensitive* data without having to include them in the Checker object itself.  In the case of path-specific data, Checker state is stored in GRStates via the GDM.  There is no reason we couldn't extend this concept to allowing checkers to associate data with (say) LocationContexts if we wanted them to be able to cache some data local to the analysis of a specific function or method.  We haven't needed that yet, but we have all sorts of ways for Checkers to potentially store data.  Data that goes into the Checker object, however, really should be something general that is useful for the entire lifetime of the checker.  The function summaries used by CFRefCount fall into that category.  So from the perspective of a design argument, there is no reason why these couldn't be moved to the RetainReleaseChecker.

Now what about the mapping of ExplodedNodes to function summaries?  That is indeed a hack, because we don't have ways to annotate ExplodedNodes with information that checkers could use to reconstruct critical information for generating diagnostics.  If we had proper annotations for ExplodedNodes, we would be able to attach this information in a structured way to nodes.  That said, what would those annotations look like?  All the summaries do is record what transfer function logic was used at a given point.  That might not be the most efficient annotation, but that's a fairly basic one.  Moreover, summaries are reused, so we don't necessarily create many of them.  In the end you are just talking about a mapping from ExplodedNodes to a handful of commonly used summaries.  I'm not convinced that is a serious scalability issue.

> 
> - There's no evalObjCMessage, for the very sensible reason that overriding a method can make its behavior totally different. Nevertheless, there are a few messages we /do/ want to model in a RetainReleaseChecker: -[NSAutoreleasePool init], -[NSAutoreleasePool addObject:], -retain, -release, and -autorelease. Fortunately, pretty much everything else would fit in a PostObjCMessage implementation.

I'm not convinced that these couldn't be modeled using a PostObjCMessage implementation as well.  There's nothing really special about them, and really we want to move to a place where all domain-specific knowledge can be modeled in checkers.

Consider -retain.  All it does is add a +1 retain count.  That could easily be a post condition.  The only other thing that is hard here is that -retain returns an alias to the receiver.  We don't have a good way right now for a checker to articulate that except with an evalObjCMessage, but I can envision other strategies.  For example, a checker should be able to say (for many reasons) that the return value aliases the receiver, and articulate that as a /constraint/ to the ConstraintManager.  This requires the ability to possibly unify symbols (i.e., the symbol for the receiver's value and the symbol for the return value), but it is really powerful.  I also think this generalizes well to inter-procedural analysis.  For example, suppose we had *both* domain-specific knowledge from a checker about a given function as well as information garnered from analyzing the function's implementation.  That means we have two sources of information about the return value of the function call.  The ability to articulate domain-specific knowledge using *declarative* constraints is really the only way to naturally unify such information.

In the absence of symbol unification, however, we can probably special case the aliasing issue, at least for this specific case.  For example, we can create another (perhaps transient) Checker callback that asks: does this function/method return an alias?  Then ExprEngine can get in the business of doing the aliasing, and the checker just handles the truly checker-specific stuff (e.g., the reference counts).

> - When function/method arguments are invalidated, their reference counts persist. But any other sort of invalidation does destroy reference count records. Currently this uses a whitelist built before invalidating the various regions referenced in a call, but with no special consideration given to RetainReleaseChecker, that'd be a little strange. I can think of two ways around this: reconstruct the whitelist on every region invalidation if we're in a function call (probably not a good idea) and reconstruct the reference bindings in a post-call check (by walking backwards through ExplodedNodes to the pre-call state).

I think reconstructing the bindings would be extremely gross.  You'd basically be hacking on semantics in what's in the Store.  Unless the checker is trying to simulate a function call that has "writes" in the background, we shouldn't go this way.

I have a conflicting opinion, in that I think we just don't have the right APIs right now to express a dialog between the invalidation and the checker logic.  In the case of the RetainReleaseChecker, we have information when we desire not to invalidate specific symbol values, and we do that with a whitelist.  But region invalidation should only happen in a few contexts.  When we invalidate regions, we can make it a cooperative process between the StoreManager and the checkers.  The checkers are told what regions are being invalidated, and *why*, and the checkers should have enough information to determine if that reason is sufficient to invalidate whatever checker-specific state they are tracking.

For example, suppose we have:

  id x = [[… alloc] init]
  foo(x)

In the RetainReleaseChecker, currently we whitelist the parameter value of 'x' because it is a top-level parameter value, and we know the retain/release conventions.  Thus even though the transitive values reachable through 'x' are invalidated (e.g., containing ivars), we don't need to drop the refcount information on that symbol.

However, consider:

  y->x = [… alloc] init]
  bar(y)

In this case, the value in the field 'x' wouldn't be whitelisted.  This is because it is a nested value, and we really have no idea what bar() will do to it.

So what's the purpose of the whitelist?  It's to capture context-specific information of how values were being used in a function call when they (or their sub values) were invalidated.  But this is all just context.  I don't have a concrete proposal, but essentially if the region invalidation logic communicated to the checkers what was getting invalidated, and in what contexts, the checkers could make the appropriate decision on whether or not to invalidate their associated state.

Anyhow, this is just a brain dump, but I really think this just comes down to having more declarative APIs: we are invalidating a region, so tell the checkers we are invalidating it, and the checkers are given enough context to decide what they want to do with that and modify the state accordingly.  The whitelist is just a hack to construct this context.  While this is similar to what you propose, there is no back-patching of the reference bindings, and the checkers stay completely out of the business of manipulating the symbolic store.

> 
> - CFRefCount currently registers a GRState::Printer for printing the retain count info in a state. Checkers currently have no way to register printers for custom state info, and that should probably be fixed anyway.

Agreed.

> 
> Everything else that CFRefCount currently does can be done using the current Checker architecture. (For more detailed but less structured notes on this, see attached <CFRefCount.txt>.)

Absolutely.

I'll follow up on your notes in a separate email (possibly off the list).  I don't want to derail the focus of this first high-level response before diving into more details.

> 
> 
> As for what I /did/ accomplish, evalBind and evalAssume can be migrated to RetainReleaseChecker almost without changes: <CFRefCount.1.patch>

This looks good.

> 
> Everything /other/ than evalCall, evalObjCMessage, and evalSummary can be moved to RetainReleaseChecker, but that leaves plenty of hackery behind: <CFRefCount.2.patch>

This also looks great.

The hackery that remains looks like it falls into the talking points above: essentially what to do with GRTransferFuncs.  I personally believe with the right additional APIs, we can migrate this logic to the analyzer core, and give checkers the right tools to do what they want without needing to implement these methods or have a GRTransferFuncs class at all.

I'm interested in hearing more of your opinions here.

> I'm going to stop this work here...it's where it crosses the line from "simple migration" to "design decisions". Once the four issues above are resolved, it should actually be pretty straightforward to eliminate TransferFuncs and CFRefCount from the analyzer and make RetainReleaseChecker optional. Which would be great, right?

Agreed whole-heartedly.  Thanks so much for spear heading this!