CFRefCount Problem #4: Hybrid GC

[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.

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.

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?

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.

3. Two runs over the entire /translation unit/, since a checker's lifetime is at least as long as a translation unit.
- Advantage: no resetting between runs
- Disadvantage: bug reports will be out of order. This is pretty bad.
- Still have the "who knows about the GC mode" problem.

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.

On the other hand, maybe it's /too/ heavy compared to what we have now. 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.

Jordy

P.S. Everything would get simpler if we stopped distinguishing between "hybrid, non-GC" and "non-GC", and "hybrid, GC on" and "GC only", because then we could just change the LangOptions before they got to the checkers. But those are nice distinctions to make, and I think they're worth keeping.

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.

[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.

Okay. Your reasoning makes sense, and you've got a stronger sense of how the analyzer pieces fit together. TBH if output order isn't a factor, then #3 (two passes over the entire translation unit) requires the least from the actual checking. It's a fully top-down solution, rather than a bottom-up solution. (What we have now is somewhere in the middle.)

My concern now is that storing the GC mode in the analysis context implies that it could change between code bodies. Currently this isn't something we can cope with...but worse, it means that checkers are created before they know what the GC mode is. Unfortunately, checker registration functions only have access to a CheckerManager. CheckerManager does have a LangOptions reference, so maybe the GC flag should be there?

(Currently there are a lot of checkers that fail if the /AST context/ changes between code bodies...mostly those that still cache IdentifierInfos. This isn't correct behavior, but it's roughly equivalent to the case here, which is essentially changing LangOptions between code bodies.)

For checkers that might want to make incidental checks, rather than change their whole behavior, we could put a shortcut method in CheckerContext that just expands to getAnalysisManager().getCheckerManager()->isGCEnabled().

Jordy

[snip]

Okay. Your reasoning makes sense, and you’ve got a stronger sense of how the analyzer pieces fit together. TBH if output order isn’t a factor, then #3 (two passes over the entire translation unit) requires the least from the actual checking. It’s a fully top-down solution, rather than a bottom-up solution. (What we have now is somewhere in the middle.)

Just to be clear, all I’m proposing is doing essentially what we do now, except pull it up one level so that the change applies to all checkers, and not just how we create ExprEngines.

My concern now is that storing the GC mode in the analysis context implies that it could change between code bodies.

By running the analysis twice, that’s essentially what we are doing.

AnalysisContext implies just that: the “context” in which an analysis gets run. No more and no less. If GC is part of the context, that seems like a reasonable place to put it.

Currently this isn’t something we can cope with…

I’m not certain what that means. Can you clarify?

but worse, it means that checkers are created before they know what the GC mode is.

I don’t anticipate that most checkers care, so I’m not certain if this is an issue.

Unfortunately, checker registration functions only have access to a CheckerManager. CheckerManager does have a LangOptions reference, so maybe the GC flag should be there?

What problem are you trying to solve? Checkers conditionally registering themselves depending on whether GC is enabled? They can check the LangOptions reference for that. If the GC or GC-hybrid mode is in LangOptions, it means GC-checking will happen.

(Currently there are a lot of checkers that fail if the /AST context/ changes between code bodies…mostly those that still cache IdentifierInfos. This isn’t correct behavior, but it’s roughly equivalent to the case here, which is essentially changing LangOptions between code bodies.)

I’m not suggesting we change the LangOptions. I’m suggesting that we run analyses with different AnalysisContexts. We already do this, as right now each AnalysisContext encapsulates a separate function we want to analyze. I’m suggesting we take that one step further, and have AnalysisContext also record the GC bit.

For checkers that might want to make incidental checks, rather than change their whole behavior, we could put a shortcut method in CheckerContext that just expands to getAnalysisManager().getCheckerManager()->isGCEnabled().

I’m thinking AnalysisContext::isGCEnabled(). I don’t see this a property of CheckerManager at all.

My concern now is that storing the GC mode in the analysis context implies that it could change between code bodies.

By running the analysis twice, that's essentially what we are doing.

AnalysisContext implies just that: the "context" in which an analysis gets run. No more and no less. If GC is part of the context, that seems like a reasonable place to put it.

[snip]

Unfortunately, checker registration functions only have access to a CheckerManager. CheckerManager does have a LangOptions reference, so maybe the GC flag should be there?

What problem are you trying to solve? Checkers conditionally registering themselves depending on whether GC is enabled? They can check the LangOptions reference for that. If the GC or GC-hybrid mode is in LangOptions, it means GC-checking will happen.

Ah. I was thinking something like this:

1. GC Disabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses
2. GC Enabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses

It sounds like you're thinking:

1. Create CheckerManager and register checkers
2. Mgr->setGCEnabled(true)
a) run non-path-sensitive analyses
b) run path-sensitive analyses
3. GC Enabled
a) run non-path-sensitive analyses
b) run path-sensitive analyses

...and then checkers check if GC is enabled every time it's interesting, instead of once at registration time.

I'm okay with this, but what's your reasoning for preferring it?

Jordy

Ah. I was thinking something like this:

  1. GC Disabled
    a) create CheckerManager and register checkers
    b) run non-path-sensitive analyses
    c) run path-sensitive analyses
  2. GC Enabled
    a) create CheckerManager and register checkers
    b) run non-path-sensitive analyses
    c) run path-sensitive analyses

Let’s call this plan A.

It sounds like you’re thinking:

  1. Create CheckerManager and register checkers
  2. Mgr->setGCEnabled(true)
    a) run non-path-sensitive analyses
    b) run path-sensitive analyses
  3. GC Enabled
    a) run non-path-sensitive analyses
    b) run path-sensitive analyses

Let’s call this plan B.

…and then checkers check if GC is enabled every time it’s interesting, instead of once at registration time.

That’s clearer. I think your plan sounds cleaner (plan A). Couple concerns:

(1) I still want checkers to be written so that if they want GC-specific logic, they don’t need to be written as a separate checker. For the Retain/Release checker, we can still keep conditional behavior just by passing the “GC enabled” flag to the checker at construction time.

(2) While I’m fine with checkers being run multiple times, we’re still going to want to merge duplicate diagnostics.

For (2), I’m thinking we need a step 0. e.g.:

  1. Create a single PathDiagnosticClient that batches all results and uniques them. Use this PathDiagnosticClient for everything. We can put this logic into the PathDiagnosticClient base class.
  2. GC Disabled
    a) create CheckerManager and register checkers
    b) run non-path-sensitive analyses
    c) run path-sensitive analyses
  3. GC Enabled
    a) create CheckerManager and register checkers
    b) run non-path-sensitive analyses
    c) run path-sensitive analyses

Currently BugReporter does some uniquing of reports, and that’s fine to keep (it serves a different purpose), but I think we’ll want an easy way to unique all the diagnostics from all checkers. That also can be used as a mechanism to solve the problem of printing all diagnostics in SourceLocation order to the terminal.

Of course, we can add step 0 later, but we need to account for it in the design.

What do you think?

(comments inline and at the end)

Ah. I was thinking something like this:

1. GC Disabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses
2. GC Enabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses

Let's call this plan A.

It sounds like you're thinking:

1. Create CheckerManager and register checkers
2. Mgr->setGCEnabled(true)
a) run non-path-sensitive analyses
b) run path-sensitive analyses
3. GC Enabled
a) run non-path-sensitive analyses
b) run path-sensitive analyses

Let's call this plan B.

...and then checkers check if GC is enabled every time it's interesting, instead of once at registration time.

That's clearer. I think your plan sounds cleaner (plan A). Couple concerns:

(1) I still want checkers to be written so that if they want GC-specific logic, they don't need to be written as a separate checker. For the Retain/Release checker, we can still keep conditional behavior just by passing the "GC enabled" flag to the checker at construction time.

The only thing I'm a little concerned about (again) is that if the flag lives on the CheckerManager it's not easily accessible (you have to go through the AnalysisManager). Is a shortcut in CheckerContext good enough? Not all callbacks include CheckerContexts, but many do.

(2) While I'm fine with checkers being run multiple times, we're still going to want to merge duplicate diagnostics.

For (2), I'm thinking we need a step 0. e.g.:

0. Create a single PathDiagnosticClient that batches all results and uniques them. Use this PathDiagnosticClient for everything. We can put this logic into the PathDiagnosticClient base class.
1. GC Disabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses
2. GC Enabled
a) create CheckerManager and register checkers
b) run non-path-sensitive analyses
c) run path-sensitive analyses

Currently BugReporter does some uniquing of reports, and that's fine to keep (it serves a different purpose), but I think we'll want an easy way to unique all the diagnostics from all checkers. That also can be used as a mechanism to solve the problem of printing all diagnostics in SourceLocation order to the terminal.

Of course, we can add step 0 later, but we need to account for it in the design.

What do you think?

It seems easy enough to move the PathDiagnosticClient from the AnalysisManager to the AnalysisConsumer. Currently we do something like this:

AnalysisConsumer -> [Translation Unit] -> AnalysisManager/CheckerManager/PDC -> [Decl] -> [GC/non-GC] -> ExprEngine

...but if the same analysis consumer was used for multiple TUs, it'll break anyway, because it only ever creates one PathDiagnosticClient. Except that's not how ASTConsumers work.

What I'm working with looks something like this:

AnalysisConsumer -> PDC -> [TU] -> [GC/non-GC] -> AnalysisManager/CheckerManager -> [Decl] -> ExprEngine

...and that should make it easy to have the PathDiagnosticClient manage multiple analysis runs. Right? (Really the PDC should still be below the TU, but it's easier just to change ownership to the AnalysisConsumer and not change how it's created.)

I didn't think about duplicate bugs before because none of our tests check for non-retain-count errors under hybrid GC. But I can't actually reproduce it, either before or after my changes.

int duplicate_bugs (int x) {
   if (x) return 0;
   return 5 / x;
}

This generates one warning whether I have -fobjc-gc, -fobjc-gc-only, or neither. Which is what we want, but I wonder where the uniquing's happening.

What is different is if I have, say, a "use-after-release" for a CF object, which has a different description in GC vs. non-GC but the same bug type. I'm not sure that's wrong though -- in the case of anything that does discriminate on GC, even just to provide different descriptions, there's an implication that one error or the other could appear on its own. (Which it could, e.g. if the release was performed with CFMakeCollectable.)

Anyway, here's a possible implementation?

Jordy

HybridGC-AnalysisConsumerPlan.patch (10.1 KB)

Whoops, last version is missing a null check.

HybridGC-AnalysisConsumerPlan.patch (10.2 KB)

Ah. I was thinking something like this:

  1. GC Disabled

a) create CheckerManager and register checkers

b) run non-path-sensitive analyses

c) run path-sensitive analyses

  1. GC Enabled

a) create CheckerManager and register checkers

b) run non-path-sensitive analyses

c) run path-sensitive analyses

Let’s call this plan A.

It sounds like you’re thinking:

  1. Create CheckerManager and register checkers
  1. Mgr->setGCEnabled(true)

a) run non-path-sensitive analyses

b) run path-sensitive analyses

  1. GC Enabled

a) run non-path-sensitive analyses

b) run path-sensitive analyses

Let’s call this plan B.

…and then checkers check if GC is enabled every time it’s interesting, instead of once at registration time.

That’s clearer. I think your plan sounds cleaner (plan A). Couple concerns:

(1) I still want checkers to be written so that if they want GC-specific logic, they don’t need to be written as a separate checker. For the Retain/Release checker, we can still keep conditional behavior just by passing the “GC enabled” flag to the checker at construction time.

The only thing I’m a little concerned about (again) is that if the flag lives on the CheckerManager it’s not easily accessible (you have to go through the AnalysisManager). Is a shortcut in CheckerContext good enough? Not all callbacks include CheckerContexts, but many do.

I thought about this a bit over the last couple days. I really hate the idea of CheckerManager having any notion of this flag. It doesn’t feel right at all. CheckerManager should just be managing checkers. It shouldn’t be in the business of changing fundamental ways in how the checkers are run.

What I’m working with looks something like this:

AnalysisConsumer → PDC → [TU] → [GC/non-GC] → AnalysisManager/CheckerManager → [Decl] → ExprEngine

Following on this, I had another thought (and I’m going to backpedal on what I said earlier). There is no need for all checkers to get rerun between GC/non-GC. For the non-ExprEngine analyses, we only need to call them once. They have access to the LangOptions, so if they want to do something GC-specific, they can.

For the ExprEngine analyses, how about:

AnalysisConsumer → PDC → [TU] → AnalysisManager/CheckerManager → [Decl] → [GC/non-GC] → ExprEngine

We can just keep the flag in ExprEngine, and have CheckerContext consult that. At some point, all checker callbacks should have a CheckerContext object, so this eventually lead to a nice clean API. There is also no analysis waste here.

The reason I prefer this approach is that ExprEngine is special when it comes to the hybrid GC mode. We know that GC-semantics can change how the whole analysis works, so we need to run it twice. Other non-ExprEngine analyses (if they care), can do the same thing.

That's pretty much what we do now with CFRefCount...though I guess it makes the GC mode available to other checkers. Shouldn't be too hard to implement.

Jordy

Here's my latest implementation:

HybridGC-ExprEnginePlan.patch (20.5 KB)

HybridGC.3.patch (40.6 KB)

Looks awesome.