CFRefCount Problem #2: Region Invalidation

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

After recent patches, I've managed to separate the generic evaluation of functions and Objective-C messages -- basically, invalidating the arguments, implicit 'this' or message receiver, and globals -- from the specific retain-count-related effects of a couple functions. This felt like quite a major step forwards in the transition; everything else is just a sort of extrication and working out couplings that shouldn't exist.

One of those couplings, however, is that the /reference counts/ of arguments and message receivers should /not/ be invalidated on a call...but the reference counts of any /members/ should be. This is currently accomplished by use of a private shared "whitelist" of top-level symbols in a function call, set up by the transfer functions and then used by the RetainReleaseChecker. If the RetainReleaseChecker is to lose its privileged status, it won't be able to know which symbols should have their bindings preserved.

I'm pretty stuck on this one, but I came up with a few possibilities:

1. Restore bindings in a post-call check by walking backwards in the graph to before the call's return value is set.

2. Add the current statement to the checkRegionChanges callback, which would enable RetainReleaseChecker to skip arguments and receivers.

3. Instead of using checkRegionChanges to handle bindings of objects passed by reference, just explicitly stop tracking anything passed by reference in a post-call check. Needs fleshing out for structs, C++ constructors, etc though.

I think the first way is the cleanest, but it's certainly extra work.

Thoughts?
Jordy

I think (1) goes against the spirit of what we want to accomplish. The region invalidation logic is driven by core logic for handling the "unknown effects" of a function/method call. That should be preserved unless we have a reason not to do so. Tampering with the bindings is against the spirit of doing that. I also don't think this is simple because region invalidation can tamper with the internal representation of a Store in many ways. I also think invalidation of the values of the ivars/field of an object is separate from the invalidation of the reference count.

I'm not certain what (3) means. checkRegionChanges() includes the transitive closure of everything that get's invalidated. That's the whole point of this callback.

I think (2) is reasonable, although not complete. It allows checkers to see what values were passed as parameters/receivers, and do anything special that they'd like. That seems like a very clean solution, and it leaves checkers in charge of deciding the policy they want to have. However, it doesn't handle the following case:

@interface Foo {
   Foo *fooRef;
}
...
@end

...
Foo *x = ... // now tracking 'x'
...
x-> fooRef = x;
...
unknownFunction(x);

In this example, 'Foo' is a recursive data structure. Here the value of 'x' is passed to unknownFunction(), and given (2) the checker could distinguish that 'x' was invalidated because it was a parameter and thus we should preserve the reference count information. But we have a cyclic reference here? Because the object referenced by 'x' appears elsewhere in the visited object graph other than just being a function parameter, we should probably invalidate the reference count here as well.

To make this clearer, consider:

  ...
  Foo *x = ... // now tracking 'x'
  ...
  Foo *y = ... // now tracking 'y'
  ...
  y->fooRef = x;
  ...
  unknownFunction(y);

In this case, we will unambiguously invalidate the reference count of the object tracked by 'x', but how is this really any different than the first case? We really don't have any special knowledge here of how the reference count of the object referred to by 'x' should be handled since it is nested in the object graph. Both cases are the same in this regard.

So, (2) is not enough. In order to make (2) actionable, we will also need to keep a count of the number of times a region was invalidated, and report that in the callback. If a region was invalidated once, and appears as parameter in the argument list, then we known unambiguously that the function argument was the sole reference to the object and thus we don't need to stop tracking it's reference count. The logic on the client side for reasoning about this is simple.

That said, I think (2) *without* the invalidation counts is good enough to get started.

Is there a particular reason you were advocating (1)?

One of those couplings, however, is that the /reference counts/ of arguments and message receivers should /not/ be invalidated on a call...but the reference counts of any /members/ should be. This is currently accomplished by use of a private shared "whitelist" of top-level symbols in a function call, set up by the transfer functions and then used by the RetainReleaseChecker. If the RetainReleaseChecker is to lose its privileged status, it won't be able to know which symbols should have their bindings preserved.

I'm pretty stuck on this one, but I came up with a few possibilities:

1. Restore bindings in a post-call check by walking backwards in the graph to before the call's return value is set.

2. Add the current statement to the checkRegionChanges callback, which would enable RetainReleaseChecker to skip arguments and receivers.

3. Instead of using checkRegionChanges to handle bindings of objects passed by reference, just explicitly stop tracking anything passed by reference in a post-call check. Needs fleshing out for structs, C++ constructors, etc though.

I think the first way is the cleanest, but it's certainly extra work.

I think (1) goes against the spirit of what we want to accomplish. The region invalidation logic is driven by core logic for handling the "unknown effects" of a function/method call. That should be preserved unless we have a reason not to do so. Tampering with the bindings is against the spirit of doing that. I also don't think this is simple because region invalidation can tamper with the internal representation of a Store in many ways. I also think invalidation of the values of the ivars/field of an object is separate from the invalidation of the reference count.

I'm not certain what (3) means. checkRegionChanges() includes the transitive closure of everything that get's invalidated. That's the whole point of this callback.

Yeah, never mind. It sounded better in my head and I didn't manage to think it through before writing the e-mail.

I think (2) is reasonable, although not complete. It allows checkers to see what values were passed as parameters/receivers, and do anything special that they'd like. That seems like a very clean solution, and it leaves checkers in charge of deciding the policy they want to have. However, it doesn't handle the following case:

...
Foo *x = ... // now tracking 'x'
...
x-> fooRef = x;
...
unknownFunction(x);

In this example, 'Foo' is a recursive data structure. [snip]

So, (2) is not enough. In order to make (2) actionable, we will also need to keep a count of the number of times a region was invalidated, and report that in the callback. If a region was invalidated once, and appears as parameter in the argument list, then we known unambiguously that the function argument was the sole reference to the object and thus we don't need to stop tracking it's reference count. The logic on the client side for reasoning about this is simple.

That said, I think (2) *without* the invalidation counts is good enough to get started.

It's worth noting that the current implementation doesn't handle this either, so at least it won't be a regression.

Is there a particular reason you were advocating (1)?

(1) is the least intrusive implementation, and it's an implementation that doesn't impose additional semantics on invalidateRegion(s). What I didn't realize is that invalidateRegions is /only/ used for parameters. That means that passing the top-level parameters isn't really changing any semantics. So I'm good with (2).

Is it best to pass a list of SVals? A list of top-level regions? A list of expressions? A list of symbols? A CallOrObjCMessage? The last is clearly most flexible, but I'm not sure that's what we need. I feel like the list of SVals (ArrayRef<SVal>) is probably the way to go.

Is there a particular reason you were advocating (1)?

(1) is the least intrusive implementation, and it’s an implementation that doesn’t impose additional semantics on invalidateRegion(s).

I don’t think I quite understand (1). Could you explain a bit more what you had in mind? To me, restoring bindings in the store has nothing to do with whether or not a symbol gets invalidated.

What I didn’t realize is that invalidateRegions is /only/ used for parameters.

I’m not certain what you mean. It’s a general API, that is meant to be used to invalidate any set of regions, starting with region roots. invalidateRegions is also used to invalidate globals. Yes, we use it right now to invalidate parameters, but it could certainly be used in other cases.

That means that passing the top-level parameters isn’t really changing any semantics. So I’m good with (2).

Ah, you mean by extending the API and making it too specialized?

Is it best to pass a list of SVals? A list of top-level regions? A list of expressions? A list of symbols? A CallOrObjCMessage? The last is clearly most flexible, but I’m not sure that’s what we need. I feel like the list of SVals (ArrayRef) is probably the way to go.

Maybe just the list of MemRegion roots and an optional ProgramPoint? The latter could be used to tailor the behavior of the callback. SVals are really one level too high, since this API really is about regions.

Is there a particular reason you were advocating (1)?

(1) is the least intrusive implementation, and it's an implementation that doesn't impose additional semantics on invalidateRegion(s).

I don't think I quite understand (1). Could you explain a bit more what you had in mind? To me, restoring bindings in the store has nothing to do with whether or not a symbol gets invalidated.

Oh! I meant RefBindings (i.e. ref count state), not store bindings. Sorry!

Basic idea was this:
- invalidation (without whitelist) wipes out reference counts
- in postCall, walk backwards in the graph to before the call is evaluated (using the ProgramPoint)
- look up each argument's refcount in the old node and copy it to the new node
- apply the call's ArgEffects to its arguments (as is done now)

This doesn't handle the recursive data structure case, but even if an object has a strong reference to itself it's probably /still/ following retain-count conventions. I think it's okay for RetainReleaseChecker not to handle that case.

What I didn't realize is that invalidateRegions is /only/ used for parameters.

I'm not certain what you mean. It's a general API, that is meant to be used to invalidate any set of regions, starting with region roots. invalidateRegions is also used to invalidate globals. Yes, we use it right now to invalidate parameters, but it could certainly be used in other cases.

Sorry, I meant "only for function/method calls", i.e. running code we can't see. I'm not sure if /that's/ supposed to be in the contract either, but it makes passing around a list of "arguments" not as bad to me, since there /will/ always be arguments.

That means that passing the top-level parameters isn't really changing any semantics. So I'm good with (2).

Ah, you mean by extending the API and making it too specialized?

I don't mind specialization, I just mind having exceptional cases that have to leave fields blank. That makes me think the abstraction's at the wrong level.

Is it best to pass a list of SVals? A list of top-level regions? A list of expressions? A list of symbols? A CallOrObjCMessage? The last is clearly most flexible, but I'm not sure that's what we need. I feel like the list of SVals (ArrayRef<SVal>) is probably the way to go.

Maybe just the list of MemRegion roots and an *optional* ProgramPoint? The latter could be used to tailor the behavior of the callback. SVals are really one level too high, since this API really is about regions.

I guess so. What RetainReleaseChecker needs is the symbols, but the API shouldn't be tailored to RetainReleaseChecker, and it's not /that/ hard to extract symbols from MemRegions, some of which are SymbolicRegions.

Ah, ok. That makes a lot more sense.

In general, I’m not a fan of such post-processing. I’d rather design an API where the checker can make the right decision upfront instead of separating the logic in such a disjoint way between the callback for invalidateRegions and the callback for post-visiting a CallExpr.

Here are the problems I see:

(1) The logic is disjoint.

(2) It is error prone and messy. Checkers generally shouldn’t need to grovel through the predecessors in the ExplodedGraph in order to implement basic functionality. Generally speaking, checkers should be written so that the transfer functions are “memoryless”. They should take the current expression, the current ProgramState, and produce a new ProgramState. That’s it. Anything else is a departure from that clean model.

(3) It introduces semantic inconsistencies. Say two checkers consult the same checker meta-data associated with symbols. If one callback we invalidate the symbols, and then the other checker possibly sees no checker meta-data before the other checker adds it back.

What I didn’t realize is that invalidateRegions is /only/ used for parameters.

I’m not certain what you mean. It’s a general API, that is meant to be used to invalidate any set of regions, starting with region roots. invalidateRegions is also used to invalidate globals. Yes, we use it right now to invalidate parameters, but it could certainly be used in other cases.

Sorry, I meant “only for function/method calls”, i.e. running code we can’t see. I’m not sure if /that’s/ supposed to be in the contract either, but it makes passing around a list of “arguments” not as bad to me, since there /will/ always be arguments.

I can see invalidateRegions() possibly being used for other cases than just the standard conservative behavior of invalidating globals/parameters. The uses would all be similar, but I don’t see a reason why they would need to be restricted to parameters being invalidated.

That means that passing the top-level parameters isn’t really changing any semantics. So I’m good with (2).

Ah, you mean by extending the API and making it too specialized?

I don’t mind specialization, I just mind having exceptional cases that have to leave fields blank. That makes me think the abstraction’s at the wrong level.

That’s true.

Is it best to pass a list of SVals? A list of top-level regions? A list of expressions? A list of symbols? A CallOrObjCMessage? The last is clearly most flexible, but I’m not sure that’s what we need. I feel like the list of SVals (ArrayRef) is probably the way to go.

Maybe just the list of MemRegion roots and an optional ProgramPoint? The latter could be used to tailor the behavior of the callback. SVals are really one level too high, since this API really is about regions.

I guess so. What RetainReleaseChecker needs is the symbols, but the API shouldn’t be tailored to RetainReleaseChecker, and it’s not /that/ hard to extract symbols from MemRegions, some of which are SymbolicRegions.

The invalidated symbols can all be queried from the SymbolReaper. The regions represent the actual locations that were used as parameters (or whatever we used for the “roots” of the invalidation). Symbols aren’t all locations, but some regions are (essentially) symbols. Since invalidation stems from locations, regions seems a more natural starting point to me, while SVals cover too much.

Okay, here's what I've come up with:

The checkRegionChanges callback now looks like this:

const ProgramState *
checkRegionChanges(const ProgramState *state,
                   const StoreManager::InvalidatedSymbols *invalidated,
                   ArrayRef<const MemRegion *> ExplicitRegions,
                   ArrayRef<const MemRegion *> Regions) const;

...where ExplicitRegions contains the regions specifically requested for invalidation. (An ArrayRef also seems better than the begin/end pair we currently use.)

This is enough to manually recreate the whitelist in /almost/ the same way as before. What's missing is the invalidation of arguments to C++ constructors (and C++ new-expressions), which now show up as "top-level arguments". To fix this, I added CXXConstructExpr to CallOrObjCMessage and added another post-statement check to RetainReleaseChecker. (Currently we just stop tracking ObjC objects that get passed into C++-land, but that could change in the future.)

Amusingly, this passed the limit on the number of checks allowed per Checker, so I increased that as well.

Consequently, this is a rather ugly patch. I can try to separate it into smaller pieces if you want.

Jordy

CFRefCount-NoWhitelist.patch (34.1 KB)

Amusingly, this passed the limit on the number of checks allowed per Checker, so I increased that as well.

Where are the variadic templates when you need them..

At some point in the near future, we can re-evaluate what subsets of C++'0X we can use for Clang, and possibly a larger set for the analyzer.

Amusingly, this passed the limit on the number of checks allowed per Checker, so I increased that as well.

Where are the variadic templates when you need them…

At some point in the near future, we can re-evaluate what subsets of C++'0X we can use for Clang, and possibly a larger set for the analyzer.

Problem with doing is that clang build will be limited to those compilers which have implemented those subsets.

  • fariborz

Of course, but there are versions of GCC, Clang, and Visual Studio which support a subset of C++'0X features. Picking the subset that they all support would likely be adequate. We can revisit that discussion later.

This looks great. I understand the need to handle CXXConstructExprs in checkRegionChanges(), but why do we need checkPostStmt() for CXXConstructExprs? We'll never have a summary to evaluate for those.

This looks great. I understand the need to handle CXXConstructExprs in checkRegionChanges(), but why do we need checkPostStmt() for CXXConstructExprs? We'll never have a summary to evaluate for those.

It's to handle the "stop tracking" aspect of C++ constructors. checkRegionChanges() actually /doesn't/ invalidate the arguments to C++ constructors, because it treats them as top-level arguments, which maintain their retain counts. It's the postStmt check that currently stops tracking the arguments to C++ methods.

I think it would actually be /great/ to allow annotations on C++ constructors, so that we could do retain-count checks for something like:

{
  LocalObject x([[Foo alloc] init]);
  [*x doSomething];
} // *x is released by LocalObject's destructor
{
  LocalObject y([[[Foo alloc] init] autorelease]);
} // expected-warning{{over-release of object}}

This is certainly a ways off (at the very least we need better destructor support, cf. PR3888), but including this post-statement check means that constructors are treated like any other C++ method calls -- they get a stop-tracking summary from the summary manager, and that's that. If we add support for method calls, it'll apply to constructors for free.

If that's not what we want, we /still/ need to have a post-statement check for CXXConstructExprs to stop tracking all the arguments. Or we need to add the current Expr (or ProgramPoint, as you mentioned) to checkRegionChanges. Which do you think is better here?

Jordy

P.S. I just realized that NewExprs are not implemented in terms of ConstructExprs. If they were, it would make things easier. I don't really want to add NewExprs to CallOrObjCMessage too! Guess that's a new patch to work on, in a completely different part of the system.

P.P.S. I am also totally ignoring placement-args for 'new', which also won't have their reference counts invalidated, on the grounds that I can't think of a good design where using an object as a placement-argument for 'new' should change the local view of its reference count.

Uh, combining NewExprs and ConstructExprs doesn't seem to actually make sense outside of the analyzer. Oh well.

OTOH, there are /no/ pre- or post-statement hooks for NewExprs right now, so to even get a stop-tracking result for arguments to NewExprs we either need to add a callback or include an Expr or ProgramPoint in checkRegionChanges.

It’s to handle the “stop tracking” aspect of C++ constructors. checkRegionChanges() actually /doesn’t/ invalidate the arguments to C++ constructors, because it treats them as top-level arguments, which maintain their retain counts.

Ah yes. Makes perfect sense!

It’s the postStmt check that currently stops tracking the arguments to C++ methods.

I think it would actually be /great/ to allow annotations on C++ constructors, so that we could do retain-count checks for something like:

{
LocalObject x([[Foo alloc] init]);
[*x doSomething];
} // *x is released by LocalObject’s destructor
{
LocalObject y([[[Foo alloc] init] autorelease]);
} // expected-warning{{over-release of object}}

This is certainly a ways off (at the very least we need better destructor support, cf. PR3888), but including this post-statement check means that constructors are treated like any other C++ method calls – they get a stop-tracking summary from the summary manager, and that’s that.

WRM.

If we add support for method calls, it’ll apply to constructors for free.

If that’s not what we want, we /still/ need to have a post-statement check for CXXConstructExprs to stop tracking all the arguments. Or we need to add the current Expr (or ProgramPoint, as you mentioned) to checkRegionChanges. Which do you think is better here?

I like the approach you have taken. Keeps everything consistent.

Great observation. I suggest we table this issue for now so we can continue to make progress. Let's file a PR and tackle it in later in follow-up. I think we should make progress on the core retain/release checker changes first. What do you think?

Sounds good, shouldn't be hard to add later.

Filed as PR10794.