This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Get construction into `operator new` running in simple cases.
ClosedPublic

Authored by NoQ on Nov 28 2017, 8:00 AM.

Details

Summary

Under the assumption of -analyzer-config c++-allocator-inlining=true, which enables evaluation of operator new as a regular function call, this patch shows what it takes to actually inline the constructor into the return value of such operator call.

The CFG for a new C() expression looks like:

  • CXXNewAllocator new C() (a special kind of CFGElement on which operator new is being evaluated)
  • CXXConstructExpr C() (a regular CFGStmt element on which we call the constructor)
  • CXXNewExpr new C() (a regular CFGStmt element on which we should ideally have nothing to do)

What i did here is:

  1. First, i relax the requirements for constructor regions, as discussed on the mailing list (http://lists.llvm.org/pipermail/cfe-dev/2017-November/056095.html). We can now construct into ElementRegion unless it actually represents an array element (we're not dealing with operator new[] yet). Also we remove the explicit bailout for constructions that correspond to operator new parent expressions, as long as -analyzer-config c++-allocator-inlining is enabled. See changes in mayInlineCallKind().
  1. Then, when the constructor is being modeled, we're trying to get back the value returned by operator new. This is done similarly to other construction cases - by finding the next (!!) element in the CFG, figuring out that it's a CXXNewExpr, and then taking the respective region to construct into from the Environment. The CXXNewAllocator element is not relied upon on this phase - for now it only triggers the evaluation of operator new at the right moment, so that we had the return value. See changes in getRegionForConstructedObject() and canHaveDirectConstructor().
  1. When we reach the actual CXXNewExpr CFG element (the third one), we need to preserve the value we already have for the CXXNewExpr in the environment. The old code that's conjuring a (heap) pointer here would probably still remain to handle the case when an inlined operator new has actually returned an UnknownVal. Still, this needs polishing, as the FIXME at the top of VisitCXXNewExpr() suggests. See the newly added hack in VisitCXXNewExpr().
  1. Finally, the CXXNewExpr value keeps dying in the Environment. From the point of view of the current liveness analysis, the new-expression is dead (or rather not yet born) until the CXXNewExpr statement element is reached, so it immediately gets purged on every step. The really dirty code that prevents this, that should never be committed, is in shouldRemoveDeadBindings(): for the sake of this proof-of-concept, i've crudely disabled garbage collection on the respective moments of time. I believe that the proper fix would be on the liveness analysis side: mark the new-expression as live between the CXXNewAllocator element and CXXNewExpr statement element.

My todo list before committing this would be:

  1. Fix the live expressions hack.
  2. See how reliable is findElementDirectlyInitializedByCurrentConstructor() in this case.
  3. Understand how my code works for non-object constructors (eg. new int).
  4. See how much VisitCXXNewExpr can be refactored.

Once this lands, i think we should be looking into enabling -analyzer-config c++-allocator-inlining by default.

Diff Detail

Repository
rL LLVM

Event Timeline

NoQ created this revision.Nov 28 2017, 8:00 AM
NoQ added a comment.Nov 28 2017, 8:13 AM

for the sake of this proof-of-concept, i've crudely disabled garbage collection on the respective moments of time

Forgot to mention that this breaks tests in NewDeleteLeaks-PR19102.cpp, which are still failing in the present revision. Leak warnings get delayed to much later lines of code here. This example shows that this liveness hack may delay garbage collection indefinitely.

NoQ updated this revision to Diff 125850.Dec 6 2017, 5:08 PM

Replaced the live expression hack with a slightly better approach. It doesn't update the live variables analysis to take CFGNewAllocator into account, but at least tests now pass.

In order to keep the return value produced by the operator new() call around until CXXNewExpr is evaluated, i added a program state trait, CXXNewAllocatorValueStack:

  1. Upon evaluating CFGNewAllocator, the return SVal of the evaluated allocator call is put here;
  2. Upon evaluating CXXConstructExpr, that return value is retrieved from here;
  3. Upon evaluating CXXNewExpr, the return value is retrieved from here again and then wiped.

In order to support nested allocator calls, this state trait is organized as a stack/FIFO, with push in CFGNewAllocator and pop in CXXNewExpr. The llvm::ImmutableList thing offers some asserts for warning us when we popped more times than we pushed; we might want to add more asserts here to detect other mismatches, but i don't see a need for implementing this as an environment-like map from (Expr, LocationContext) to SVal.

Why SVal and not MemRegion? Because i believe that ideally we want to produce constructor calls with null or undefined this-arguments. Constructors into null pointers should be skipped - this is how operator new(std::nothrow) works, for instance. Constructors into garbage pointers should be immediately caught by the checkers (to throw a warning and generate a sink), but we still need to produce them so that the checkers could catch them. But for now CXXConstructorCall has room only for one pointer, which is currently const MemRegion *, so this still remains to be tackled.

Also we need to make sure that not only the expression lives, but also its value lives, with all the various traits attached to it. Hence the new facility in ExprEngine::removeDead() to mark the values in CXXNewAllocatorValueStack as live. Test included in new-ctor-inlined.cpp (the one with s != 0) covers this situation.

Some doxygen comments updated.

MTC added a subscriber: MTC.Dec 8 2017, 7:06 PM
In D40560#947514, @NoQ wrote:

Replaced the live expression hack with a slightly better approach. It doesn't update the live variables analysis to take CFGNewAllocator into account, but at least tests now pass.

In order to keep the return value produced by the operator new() call around until CXXNewExpr is evaluated, i added a program state trait, CXXNewAllocatorValueStack:

  1. Upon evaluating CFGNewAllocator, the return SVal of the evaluated allocator call is put here;
  2. Upon evaluating CXXConstructExpr, that return value is retrieved from here;
  3. Upon evaluating CXXNewExpr, the return value is retrieved from here again and then wiped.

In order to support nested allocator calls, this state trait is organized as a stack/FIFO, with push in CFGNewAllocator and pop in CXXNewExpr. The llvm::ImmutableList thing offers some asserts for warning us when we popped more times than we pushed; we might want to add more asserts here to detect other mismatches, but i don't see a need for implementing this as an environment-like map from (Expr, LocationContext) to SVal.

I think it would be great to have tests for such cases to make it apparent it is not trivial to do this only based on the cfg.
Maybe something like:

A *a = new A(new B, coin ? new C : new D, inlinedCallWithMoreAllocs());

Or in case it turns out to be an easy problem to match these from CFG, I prefer avoiding the state.

Also having a new expression within an overloaded operator new might be interesting.

Why SVal and not MemRegion? Because i believe that ideally we want to produce constructor calls with null or undefined this-arguments. Constructors into null pointers should be skipped - this is how operator new(std::nothrow) works, for instance. Constructors into garbage pointers should be immediately caught by the checkers (to throw a warning and generate a sink), but we still need to produce them so that the checkers could catch them. But for now CXXConstructorCall has room only for one pointer, which is currently const MemRegion *, so this still remains to be tackled.

Are you sure we need to produce undef vals? Couldn't a checker subscribe to the post allocator call and check for the undefined value and generate a sink before the constructor call? I am not opposed to using SVals there, just curious.

Also we need to make sure that not only the expression lives, but also its value lives, with all the various traits attached to it. Hence the new facility in ExprEngine::removeDead() to mark the values in CXXNewAllocatorValueStack as live. Test included in new-ctor-inlined.cpp (the one with s != 0) covers this situation.

Some doxygen comments updated.

Hi Artem. This patch looks OK, just stylish issues.

lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
112 ↗(On Diff #125850)

constructors

474 ↗(On Diff #125850)

Space after ':'? (Same below and upper)

522 ↗(On Diff #125850)

Should this be under 'if' as well?

NoQ updated this revision to Diff 127420.Dec 18 2017, 3:39 PM
  • Fix pop from empty stack.
  • Add recursive operator new tests.
    • Disable argument invalidation when the allocator was inlined (needed for those tests to work)

I think it would be great to have tests for such cases to make it apparent it is not trivial to do this only based on the cfg.
Maybe something like:

A *a = new A(new B, coin ? new C : new D, inlinedCallWithMoreAllocs());

Or in case it turns out to be an easy problem to match these from CFG, I prefer avoiding the state.

Also having a new expression within an overloaded operator new might be interesting.

Yeah, that's an excellent idea, thanks! I totally forgot about it.

Note, however, that neither chaining operator new as new(new) C(...) nor calling new from within the allocator actually makes our stack grow. In the former case, inner new-expression is fully evaluated before the outer new-expression even starts. In the latter case, the value for the outer allocator will only be put on stack after the outer allocator exits, after the inner new-expression is fully evaluated.

So in order to actually make use of the stack, we need to call operator new within a constructor that constructs into an outer operator new. In this case we first evaluate the outer allocator and put its results on the stack, then we evaluate the constructor and the operator new within it and put another value on the stack, and only then we pop both values.

See newly added tests for more details.

Are you sure we need to produce undef vals? Couldn't a checker subscribe to the post allocator call and check for the undefined value and generate a sink before the constructor call? I am not opposed to using SVals there, just curious.

Yep, you're totally right. Now that we understand how these work, we can actually catch the undefined operator new return value in or just after the allocator. Other reasons still stand though.

NoQ added a comment.Dec 18 2017, 3:39 PM
lib/StaticAnalyzer/Core/ExprEngineCXX.cpp
522 ↗(On Diff #125850)

Whooooooooops!! Thanks!

Apparently, ImmutableList::getTail() doesn't crash when the list is empty. And i thought we're catching this sort of bugs.

Added the relevant assertion into popCXXNewAllocatorValue().

NoQ retitled this revision from [analyzer] WIP: Get construction into `operator new` running in simple cases. to [analyzer] Get construction into `operator new` running in simple cases..Dec 18 2017, 3:41 PM

I think this commit starts to make sense, so i removed the "WIP" marker. I guess it's better to leave todos 2 and 4 to follow-up commits, and 1 and 3 are already addressed.

NoQ updated this revision to Diff 127436.Dec 18 2017, 5:13 PM
  • Actually fix the comment about why we need to act on null or undefined values.
  • Fix for(:) whitespace.
NoQ updated this revision to Diff 127437.Dec 18 2017, 5:16 PM
  • Fix more for(:) whitespace.
NoQ marked 2 inline comments as done.Dec 18 2017, 5:17 PM

Sorry for the spam.

NoQ added a comment.Dec 20 2017, 6:31 PM
  1. Devin suggested a fantastic idea: it may be great to have a new LocationContext for whatever happens within the big-new-expression. This would help immensely with CFG look-aheads and look-behinds and reduce parent map usage - not only for operator new, but for other constructors (into initializer lists, probably into function arguments). Let's call it ConstructionTriggerContext for now. We can also store our "_this" value in a program state map from ConstructionTriggerContext into SVal.
  1. My reaction was that we can instead store our "_this" value in some sort of "CXX_ThisRegion" within the StackLocalsSpaceRegion that corresponds to ConstructionTriggerContext, and then copy it over to CXXThisRegion that corresponds to the StackFrameContext of the constructor. This would kinda make sense given the pseudocode that we're imagine here for the new-expression. However, this sounds a bit over-engineered because we're using the Store to just temporarily stash the value. Well, right now we're using Environment for that, but it's equally dirty.
  1. Now, it might actually be better to store "_this" value directly into CXXThisRegion that corresponds to the StackFrameContext of the constructor (rather than stash it in another place and eventually copy), even if that stack frame has not been entered yet. Because the stack frame would anyway be entered almost immediately, we already know the parameters of the stack frame (parent location context, call site, block count, block id, element id), and location contexts are uniqued, so we can add the store binding now to the stack frame of the future, and whenever we actually enter the stack frame, when formerly we'd have bound the value to CXXThisRegion, we'd see that the value is already there. In this case we don't immediately need ConstructionTriggerContext - we can still add it later to refactor look-aheads and stuff. The binding would anyway be garbage-collected once the constructor exits.

I'd be glad to implement approach 3. instead of the stack of values if it sounds reasonable.

NoQ added a comment.Dec 20 2017, 7:08 PM

A slower explanation of the approach in '3.' in the previous message:

(1) Evaluate operator new() aka the allocator call as usual.
(2) Take the return value of (1) as usual.
(3) Take CXXConstructExpr which is the child of the CXXNewExpr that triggered the allocator call on (1).
(4) Construct a StackFrameContext with CXXConstructExpr from (3).
(5) Don't put the newly constructed StackFrameContext on the location context stack.
(6) Construct the StackArgumentsSpaceRegion for the StackFrameContext from (4).
(7) Construct the CXXThisRegion for the StackArgumentsSpaceRegion from (6).
(8) Bind the return value from (2) to CXXThisRegion from (7) in the Store.
(9) Put the node with the state from (8) to the worklist as usual.
(10) CoreEngine says it's time to evaluate CXXConstructExpr from (3) as usual.
(11) Make sure that the binding we made in (8) survives garbage collection*.
(11) Construct StackFrameContext for the CXXConstructExpr from (3) as usual.
(12) LocationContextManager ensures that on (4) and on (11) we get the same StackFrameContext.
(13) Don't bind CXXThisRegion while entering the stack frame - it was already done in (8).
(14) Finally enter the stack frame we've constructed twice on (4) and on (11), as usual.
(15) Evaluate the constructor, as usual.
(16) Bind this-value to CXXConstructExpr after evaluation (as usual? not sure).
(17) Allow the binding in the Store we made on (8) to be garbage-colllected as usual.
(18) When evaluating CXXNewExpr, take value of CXXConstructExpr and bind it to CXXNewExpr.

__
*We may modify SymbolReaper::isLiveRegion() for this purpose. Sounds easy.

NoQ updated this revision to Diff 129210.Jan 9 2018, 7:23 PM

That thing didn't immediately work, because there are a lot of other places where we need to put the value, not just the Store, before entering the constructor - such as our constructor call events for checker callbacks. It'd be hard for the call event to extract the target region by looking at their caller stack frame and program state, and perhaps they shouldn't be doing this, and it's actually fine that they receive the target region directly, because if we want to reconstruct the call event after the fact, we'd anyway be able to do this only from within the constructor call, because later the value would disappear from the program state anyway.

The idea with the new location context class still stands. For now i made a simple map from (CallerStackFrameContext, CXXNewExpr) pairs to SVal. This map can be trivially refactored into a map from OurNewLocationContext to SVal, because CallerStackFrame would be its parent context, and CXXNewExpr would be its parameter. Note that it's not possible to use only CallerStackFrameContext as the key because multiple CXXNewExprs might be active simultaneously, eg. new X(new Y()) - respective test case added. But with CXXNewExpr as part of the key, the key is indeed unique in the sense that by the time we encounter the same CXXNewExpr again we'd be done with the old CXXNewExpr - respective assertion added. With these assertions i guess it's more reliable than the stack approach.

I think i'm getting done with these patches, so they can be treated as in sort of final shape, i.e. i have no planned changes for these myself anymore (but i'd definitely gladly address any review comments).

NoQ updated this revision to Diff 129362.Jan 10 2018, 4:04 PM

Rename getters and setters for the new state trait (i.e. "push" -> "set", etc., because we no longer have a stack).

Also make them static, so that it was potentially possible to access them from elsewhere, eg. from CallEvent, if deemed necessary.

NoQ updated this revision to Diff 129552.Jan 11 2018, 4:16 PM

Add a stronger assertion: when ending an inlined call, assert that no stale allocator values remain.

dcoughlin accepted this revision.Jan 12 2018, 4:47 PM

LGTM with the TODO and the test case I requested inline.

lib/StaticAnalyzer/Core/ExprEngine.cpp
487 ↗(On Diff #129552)

Do we have a test for the MemRegion case? Commenting it out doesn't seem to affect the tests.

lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
607 ↗(On Diff #127437)

Can you add a TODO saying that we really shouldn't be using the parent map here? That is fragile and is a sign we're not providing enough context.

This revision is now accepted and ready to land.Jan 12 2018, 4:47 PM
NoQ updated this revision to Diff 130243.Jan 17 2018, 11:54 AM
NoQ marked 2 inline comments as done.

Address the final comments.

lib/StaticAnalyzer/Core/ExprEngine.cpp
487 ↗(On Diff #129552)

Right, added one (new-ctor-symbolic.cpp).

NoQ updated this revision to Diff 130249.Jan 17 2018, 12:28 PM

Remove pointer casts from the newly added symbolic index test, because once we properly perform the cast of the allocated value (as in D41250), our solver would blow up.

This revision was automatically updated to reflect the committed changes.