[cfe-dev] CFRefCount Problem #4: Hybrid GC

[Ted Kremenek]

Hi Jordy,

Thank you for tackling this.  I think this is a good analysis, but I have a sharp disagreement with the conclusion.

I think we should go with #3.  I have comments inline on each specific item, but my rationale is this:

(a) GC versus non-GC is more than just running a checker in a specific mode.  It is an alternate memory model.  While the only thing this currently impacts is the retain/release checker, it could potentially be used when modeling other things, including basic expressions.  The memory model is just as fundamental as the architecture, e.g. i386 versus x86_64.

(b) Since the memory mode really impacts the semantics of all code, all checkers need to run in a consistent memory mode.  That means it needs to be part of the state in some way, because we don't want to be inter-mixing semantics of different memory models in the same program state.

(c) Complexity.  Most checker writers don't want to distinguish between different memory models, and those that do should have the simplest abstraction for doing this work.

(d) Scalability.  Running the analysis twice is likely to be more scalable than running the analysis with dual-memory modes combined into the same ExplodedGraph.  More on this later.

(e) Cost: most code is not compiled to be in dual-GC mode, so the overhead doesn't impact most programs.

More comments inline.

On Aug 28, 2011, at 2:37 PM, Jordy Rose wrote:

> [Background: Currently we're trying to eliminate the concept of "transfer functions" from the static analyzer, which has gradually been supplanted by the Checker interface. The only implementation of the transfer functions, CFRefCount, has two roles: general-purpose function and method evaluator, and retain-count checking for the Cocoa and CoreFoundation frameworks. The former is being moved to ExprEngine*, the latter to a regular checker called RetainReleaseChecker. Of course, there are always design issues; I'm trying to make sure they get cleared up on-list one by one.]
> 
> Almost done! This hasn't been nearly as bad as I've feared.
> 
> The last major issue with CFRefCount is the option to compile Objective-C code as "optionally garbage-collected", or "Hybrid GC" mode. For "GC required" and "non-GC" modes, we just look in the LangOptions and all is good. But for HybridGC, we have to analyze the code whether it ends up in a GC environment or not. Since HybridGC is the problem, the rest of this e-mail assumes we're analyzing in hybrid-GC mode.
> 
> Currently, the way analyses are run on each function/method looks like this:
> 
> - non-path-sensitive checks
> - path-sensitive, GC off
> - path-sensitive, GC on
> 
> In order to get RetainReleaseChecker to switch back and forth between GC and non-GC modes (which alternate, because there may be many functions/methods), CFRefCount is being (ab)used as a non-const "beginAnalysis" callback.
> 
> As discussed off-list, we're not really trying to optimize for the hybrid-GC case--analyzing a hybrid-GC codebase is basically the same to analyzing two different codebases, because the frameworks behave differently. Still, there's not one clear solution to make RetainReleaseChecker unprivileged. I came up with three different high-level approaches to the problem:
> 
> 1. One hybrid path-sensitive run
> - Advantage: the frontend doesn't care about the GC mode.
> 
> 1A) Have two checkers that share code (like NSErrorChecker and CFErrorChecker), but use different GDM tags.
> - Disadvantage: higher peak memory usage due to less state unification.
> - Disadvantage (?): fatal errors in one checker's model will stop analysis of the other model. But if you have fatal errors, you'll have to re-run again anyway.
> - Disadvantage: doesn't make any allowances for /other/ checkers that might care if we're running in GC mode.
> - With arbitrary checkers this could cause a state explosion due to a Cartesian product, but RetainReleaseChecker rarely bifurcates the state, if ever; 1*1 is still 1.

I think the Cartestian product will actually be a real problem.  As soon as you see a -release message, the states will bifurcate.

> 
> 1B) Bifurcate the state on demand with a GCEnabled tag. After the tag is set, just follow that mode.
> - This /is/ essentially doing the analysis twice, but might cost us some memory.
> - Possibly accessible to other checkers, especially if the bifurcation happens in ExprEngine(ObjC) and not RetainReleaseChecker.

I think this is actually less scalable then running the analysis twice under different memory models.  By modeling two memory models in the same ExplodedGraph, we have the potential to (say) double the memory footprint of an ExplodedGraph.

We will also have non-linear effects.  The worklist algorithm may "time out" sooner because we have exhausted the number of worklist units we want to take, just because we are really running the analysis twice.  This means we will actually explore less of the state space then if we ran the analysis twice.

Doing the dual analysis is also potentially really complex for checker writers.  If any of them screw it up, we could get a mixture of semantics in the ExplodedGraph.

> 
> 
> 2. Two runs, with a proper beginAnalysis callback that includes the GC mode.
> - ...but who actually knows about the GC mode? ExprEngine? CheckerManager? AnalysisContext?
> - do path-insensitive checks also need to run twice?

I think #3 is strictly better than this one.  It is simpler and accomplishes the same goal.

> 2A) One checker that alters its behavior
> - Essentially what happens now.
> - Advantage (?): RetainReleaseChecker's SummaryLog could also benefit from a beginAnalysis callback.
> 
> 2B) Two checkers that share code, but only one is enabled each run
> - Can't think of any advantages over 2A, really.

Puts more burden on the checker writer.

> 
> 
> 3. Two runs over the entire /translation unit/, since a checker's lifetime is at least as long as a translation unit.

I think this is the best one.  It puts all the control in AnalysisConsumer.  AnalysisConsumer can distinguish between GC and non-GC, and set the appropriate information in AnalysisContext.

> - Advantage: no resetting between runs

Yes, it's very simple.

> - Disadvantage: bug reports will be out of order. This is pretty bad.

This is actually a non-issue.

First, the real output from the analyzer that we care about is what goes to the PathDiagnosticClients.  Currently that is the HTML output and Plists (for tools such as Xcode).  It is up to the clients to sort out issues (if any) with reports being generated out of order.  For the HTML client this isn't an issue, since each report results in a separate html file.  For the Plist output, all of the diagnostics are sorted at the end when the plist file is generated.

Second, the output to the terminal is really meant for debugging.  It is not meant to be the primary way to consume analysis results.  Out-of-order diagnostics is not great, but it's not really the desired workflow to use the analyzer anyway.

Third, the out-of-order diagnostics are a problem once we (say) do out-of-order, parallel, analysis of functions.  If we want to serialize the order of text diagnostics, we'll need to do that as a post-process step anyway.  So this is just an inherit issue if we even care about it.

> - Still have the "who knows about the GC mode" problem.

AnalysisConsumer, which is the "driver", can handle this.

> 
> 
> Personally, I think 1A is the cleanest solution, but not very extensible. 1B is what I'd actually go with: it knocks consideration of the GC mode down to the ExprEngine, it reuses the mechanisms we already have to deal with "two runs", and it's accessible to any checker who cares. I'm thinking a special ExprEngine::assumeObjCGC() or ProgramState::assumeObjCGC, which returns a pair of states for "GC off" and "GC on" (if feasible). It's a little heavy-handed, but it minimizes the impact on the rest of the analyzer, which shouldn't have to think about GC.

Not to be critical, but I think 1A is the worst solution.  The higher peak memory usage is a real concern.  The fatal errors in one checker's model stomping on others is a huge concern.  It is loaded with hidden complexity, and I think it inherently makes the analyzer less scalable.  I also think it makes it harder for checker writers.

> 
> On the other hand, maybe it's /too/ heavy compared to what we have now.

If I had to boil it down to one single objection, that would be it.

> A beginAnalysis callback would be fairly simple to implement, and the GC mode isn't too hard to thread through ExprEngine instead of CFRefCount.
> 
> Not sure which way to go on this one.

My suggestion is we run the analyses twice in AnalysisConsumer, having the resulting AnalysisContext's indicate the memory model.  Then ExprEngine is not in the business completely of even reasoning about the memory model.

The result is something that is trivially simple.

The downside?  Yes, all analyses (including path-insensitve ones) get run twice.  I'm not concerned about this for two reasons:

1) Dual GC mode is an exception, and not the norm.  It's not worth optimizing for.

2) Keeps things simple.  Everywhere we introduce unnecessarily inherently complexity into the analyzer I think we really lose in the long run.

I also think the "running things twice" can be potentially mitigated by other means, say using multiple cores for analyzing a translation unit.