[analyzer] Add PlacementNewChecker

[martong]

Summary

This checker verifies if default placement new is provided with pointers
to sufficient storage capacity.

Noncompliant Code Example:

#include <new>
void f() {
  short s;
  long *lp = ::new (&s) long;
}

Based on SEI CERT rule MEM54-CPP
https://wiki.sei.cmu.edu/confluence/display/cplusplus/MEM54-CPP.+Provide+placement+new+with+properly+aligned+pointers+to+sufficient+storage+capacity
This patch does not implement checking of the alignment.

[whisperity]

Are buffers otherwise modelled by the Analyser, such as results of the malloc family and alloca intentionally not matched, or are there some tests missing regarding this?

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

115–117

This message might be repeating phrases too much, and seems long. Also, I would expect things like default placement new or argument of placement new to be confusing. Not every person running Clang SA knows the nitty-gritty of the standard by heart...

More nitpicking: even the "default" (what does this even mean, again?) placement new takes two arguments, albeit written in a weird grammar, so there is no "argument of" by the looks of it. I really think this is confusing.

Something more concise, simpler, still getting the meaning across:

Storage provided to placement new is only N bytes, whereas allocating a T requires M bytes

[xazax.hun]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

22

I think now it is safe to have the bugtype by value and use member initialization.

35

Add braces here.

40

Hmm, I think this logic might need some more testing. Could you add some tests with multi dimensional arrays?

44

This query will only check if you know the exact value of the target of placement you.

What you actually care about if the size is at least as big as the placed object.

So instead of getting a known value I think it might be a better idea to evaluate a less than or equal operator with evalBinOp.

64

When do you see a null state?

72

Probably you could just return the size without building a more complex symbolic expression in this case? I.e. just put the right value in the makeIntVal.

79

You could:

Optional<NonLoc> NL = ElementCount.getAs<NonLoc>();

And later you could replace the castAs with a deref of the optional.

81

Prefer to use evalBinOp over evalBinOpNN.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

40

Yeah, this code is scary because at this point literally nobody knows when exactly do we an have element region wrapping the pointer (https://bugs.llvm.org/show_bug.cgi?id=43364).

MemRegion represents a segment of memory, whereas loc::MemRegionVal represents the point that is the left-hand side of that segment. I recommend using C.getSVal(Place).getAsRegion() only as a reference to that point, not the whole segment. Then you could decompose the region into a base region and an offset (i.e., MemRegion::getAsOffset()), and subtract the offset from the base region's extent to see how much space is there in the region.

65

That produces an UndefinedVal. I think you'd much rather have UnknownVal.

115–117

Having long messages is usually not a problem for us (instead, we'd much rather have full sentences properly explaining what's going on), but i agree that your text is much neater and on point.

clang/test/Analysis/placement-new.cpp

6

Wow, somebody actually remembers to add a target triple for tests that depend on the target triple! My respect, sir.

11

I'm legit curious what's hidden behind the regex.

[NoQ]

I wonder if this checker will find any misuses of placement into llvm::TrailingObjects.

[martong]

Thank you guys for the assiduous review!

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

22

Ok, I've made it to be a simple member. Also could remove the mutable specifier.

40

Thanks! I've done the decomposition of Place to base region and offset. This way handling of multi-dimensional arrays is also looking good.

44

I removed this hunk, because it is no longer needed once we work with the base region and with the offset.

64

Ok, I removed it.
(I think I got the idea of checking the state from the MallocChecker ... but I accept that it can never be null in my case).

65

I removed the check and with it the return, since @xazax.hun suggests that the state can never be null.

72

Ok, I changed that to return directly with the size of the type.

79

Ok, I've done that.

115–117

Ok, changed it.

clang/test/Analysis/placement-new.cpp

11

Ok, I removed the regexes.
But keep in mind that, this note is coming from trackExpressionValue and is changing if the initializer of s is changing.
I did not want to formulate expectations on a note that is coming from an implementation detail and can change easily. Also, If trackExpressionValue changes than we need to rewrite all these tests, unless a regex is used, perhaps just a simple expected-note {{}} would be the best from this point of view.

[martong]

• Bugtype by value
• Decompose Place to base region and offset
• Add test for type hierarchy
• Remove State check
• Return directly with the size of the type in case of non-array new
• Use Optional for ElementCount
• Update warning message

[martong]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

33

This assertion fails on real code quite often (e.g. on LLVM/Clang code). I don't really understand why. @NoQ what is you understanding on this? Perhaps I could try to reduce a case from the real code to see an example.

[martong]

• Better handling of unknown values

[xazax.hun]

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

472

Probably you want to add documentation to clang/docs/analyzer/checkers.rst as well for better visibility.

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

52

A very minor nit, but checker APIs tend to have CheckerContext as the last parameter. Maybe following this guideline within the checkers as well makes them a bit more natural.

60

You can move this line into the if condition.

92

Here, instead of getting SizeOfTarget and SizeOfPlace as ConcreteInts, I think you should rather use evalBinOp to compare them. That method is more future proof as if we cannot constraint these values down to a single integer but we still have some information about them a sufficiently smart solver could prove the relationship between the symbolic values.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

22

And use a default initializer instead of constructor >.>
BuiltinBug BT_Placement{this, "Insufficient storage BB"}

(also i don't understand BuiltinBug and i'm afraid of using it, can we just have BugType with explicit description and category?)

33

RegionOffset cannot really represent symbolic offsets :( You should be able to re-add the assertion after checking for symbolic offsets.

And, yeah, you can always easily reduce any crash with creduce.

clang/test/Analysis/placement-new.cpp

11

Because it's up to the checker whether to use trackExpressionValue or provide its own visitor, i'd rather keep the notes tested. If the notes provided by trackExpressionValue aren't good enough, it's ultimately the checker's problem (which may or may not be fixed by improving trackExpressionValue).

[martong]

• Add documentation to checkers.rst
• Pass CheckerContext as last param
• Use BugType and default member initializer

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

33

I think protecting with if (Offset.hasSymbolicOffset()) is just fine, instead of the assertion.

92

I am not sure if evalBinOp is that useful here, because we need the concrete values anyway when we issue the diagnostics. We'd like to present the concrete sizes in bytes.

clang/test/Analysis/placement-new.cpp

6

Thanks! :)

[martong]

In D71612#1790045, @NoQ wrote:

I wonder if this checker will find any misuses of placement into llvm::TrailingObjects.

I've evaluated this checker on LLVM/Clang source and it did not find any results, though there are many placement new calls there. I think this is good, because there are no false positives.

[INFO 2019-12-21 00:15] - ----==== Summary ====----
[INFO 2019-12-21 00:15] - Successfully analyzed
[INFO 2019-12-21 00:15] -   clangsa: 2975
[INFO 2019-12-21 00:15] - Failed to analyze
[INFO 2019-12-21 00:15] -   clangsa: 2

The two failures are caused by non existing .inc files, e.g.:

/mnt/ssd/egbomrt/WORK/llvm1/git/llvm-project/llvm/unittests/Option/OptionParsingTest.cpp:23:10: fatal error: 'Opts.inc' file not found
#include "Opts.inc"
         ^~~~~~~~~~
1 error generated.

[xazax.hun]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

92

The reason why evalbinop might be useful because we might have symbolic sizes:

void f(int a) {
 char *buffer = new char[a];
}

So in the code snippet above you cannot get a concrete integer for the size of the buffer. But in case we already have some constraints about the value of a, the constraint solver might be able to tell if we are sure that the type will not fit into the buffer. I can imagine that this scenario is relatively rare, but I think we need relatively little code to support this.

So you could potentially warn when:

void f(int a) {
  char *buffer = new char[a];
  if (a > 3)
    return;
  int *p = new (buffer) int;
}

I know, this is silly code, but we might not know if there are reasonable code that has similar patterns.

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

92

For this sort of stuff i'd strongly recommend

1. explaining the range constraints for the buffer size in the warning message and
2. making a bug visitor that'll explain how these constraints change across the path.

I.e., "Assuming that 'a' is less than or equal to 3" => "Buffer size is constrained to [0, 3]" => "Storage provided to placement new is at most 3 bytes, whereas the allocated type requires 4 bytes".

The same applies to our alpha array bound checkers. We really need this stuff explained in them. Without such facilities i'd rather stick to concrete values.

[xazax.hun]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

92

This makes sense. How about committing this only supporting concrete values and introduce the visitor/symbolic support in a follow-up? (If Gabor Marton is motivated to implement it :) I am also ok if this will not get implemented for now.)

[NoQ]

In D71612#1812036, @martong wrote:

In D71612#1790045, @NoQ wrote:

I wonder if this checker will find any misuses of placement into llvm::TrailingObjects.

I've evaluated this checker on LLVM/Clang source and it did not find any results, though there are many placement new calls there. I think this is good, because there are no false positives.

In such cases it's usually a good idea to verify that the checker works correctly by artificially injecting a bug into the codebase. If the bug is not found, the checker is probably not working. If the bug is found, change it to be more and more realistic, so that to see what limitations does the checker have in terms of false negatives. Monitor analyzer stats closely (max-nodes limits, block count limits, inlining limits) in order to see what exactly goes wrong (or debug on the Exploded Graph as usual, depending on how it goes wrong). This exercise often uncovers interesting omissions :)

Can we enable the check by default then? What pieces are missing? Like, the symbolic extent/offset case is not a must. I think we have everything except maybe some deeper testing. I'd rather spend some time on the above exercise, but then enable by default if it goes well.

The two failures are caused by non existing .inc files, e.g.:

/mnt/ssd/egbomrt/WORK/llvm1/git/llvm-project/llvm/unittests/Option/OptionParsingTest.cpp:23:10: fatal error: 'Opts.inc' file not found
#include "Opts.inc"
         ^~~~~~~~~~
1 error generated.

I've seen these errors with scan-build-py as well. It looks like LLVM's build system cannot be correctly reduced to a compilation database (though it's just one place - maybe it can be easily fixed).

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

61–62

Let's combine these two lines into a single if-statement:

if (auto ElementCountNL = ElementCount.getAs<NonLoc>()) {
  ...
}

(also, yeah, this is one of the blessed use cases for auto)

76

Soo why not use makeArrayIndex here as well?

92

Technically, there's also a chance of the object size being symbolic (i.e., "placement new[]"), however placement new[] is already very weird due to the requirement to store the "allocated" size within the storage together with the actual buffer (IIRC the size of such header is implementation-defined and the operator almost always returns an updated pointer which should be later passed to delete[]).

How about committing this only supporting concrete values and introduce the visitor/symbolic support in a follow-up?

Sure!

[martong]

Can we enable the check by default then? What pieces are missing? Like, the symbolic extent/offset case is not a must. I think we have everything except maybe some deeper testing. I'd rather spend some time on the above exercise, but then enable by default if it goes well.

I am going to execute the analysis on LLVM/Clang as you suggested, so then we'll see what the experiment will bring us. And then we could enable it by default I think. BTW how can we do that? I could not find any default enablement related config in Checkers.td ...

[martong]

• Declare ElementCountNL in if stmt
• Use makeArrayIndex instead makeIntVal

[NoQ]

In D71612#1813937, @martong wrote:

I am going to execute the analysis on LLVM/Clang as you suggested, so then we'll see what the experiment will bring us. And then we could enable it by default I think. BTW how can we do that? I could not find any default enablement related config in Checkers.td ...

Enabling checkers by default is controlled by the messy code in RenderAnalyzerOptions() in the Driver.

Wait, you already made it on-by-default. Checkers that are currently under development go into the alpha package.

[martong]

In D71612#1814225, @NoQ wrote:

In D71612#1813937, @martong wrote:

I am going to execute the analysis on LLVM/Clang as you suggested, so then we'll see what the experiment will bring us. And then we could enable it by default I think. BTW how can we do that? I could not find any default enablement related config in Checkers.td ...

Enabling checkers by default is controlled by the messy code in RenderAnalyzerOptions() in the Driver.

Wait, you already made it on-by-default. Checkers that are currently under development go into the alpha package.

Ups, I am sorry. Now I am creating another commit which moves it to alpha. (So then, If I understand it correctly then the cplusplus is enabled by default, but alpha is not.)

[NoQ]

In D71612#1814410, @martong wrote:

Ups, I am sorry. Now I am creating another commit which moves it to alpha. (So then, If I understand it correctly then the cplusplus is enabled by default, but alpha is not.)

Aha, yup.

[martong]

Related commit that moves to alpha:
https://github.com/llvm/llvm-project/commit/13ec473b9d4bd4f7a558272932b7c0806171c666

[martong]

In D71612#1812476, @NoQ wrote:

In D71612#1812036, @martong wrote:

In D71612#1790045, @NoQ wrote:

I wonder if this checker will find any misuses of placement into llvm::TrailingObjects.

I've evaluated this checker on LLVM/Clang source and it did not find any results, though there are many placement new calls there. I think this is good, because there are no false positives.

In such cases it's usually a good idea to verify that the checker works correctly by artificially injecting a bug into the codebase. If the bug is not found, the checker is probably not working. If the bug is found, change it to be more and more realistic, so that to see what limitations does the checker have in terms of false negatives. Monitor analyzer stats closely (max-nodes limits, block count limits, inlining limits) in order to see what exactly goes wrong (or debug on the Exploded Graph as usual, depending on how it goes wrong). This exercise often uncovers interesting omissions :)

Can we enable the check by default then? What pieces are missing? Like, the symbolic extent/offset case is not a must. I think we have everything except maybe some deeper testing. I'd rather spend some time on the above exercise, but then enable by default if it goes well.

Artem, I've made some more experiments with this checker. I searched for default placement new call expressions in the LLVM codebase and slightly modified the checker's code to log if we have concrete values for both sizes (target and place).

@@ -95,6 +96,15 @@ void PlacementNewChecker::checkPreStmt(const CXXNewExpr *NE,
   if (!SizeOfPlaceCI)
     return;

+  //auto& SM = C.getASTContext().getSourceManager();
+  //NE->dump();
+  //NE->getBeginLoc().dump(SM);
+  //NE->getOperatorNew()->dump();
+  //SizeOfTarget.dump();
+  //llvm::errs() << "\n";
+  //SizeOfPlace.dump();
+  //llvm::errs() << "\n";
+

This way I could pick one specific file for analysis: DeclBase.cpp.
Based on the logs, I modified two LLVM headers, thus introducing bugs, which should be found by this checker:

diff --git a/llvm/include/llvm/ADT/APFloat.h b/llvm/include/llvm/ADT/APFloat.h
index ed25b2cd89f..3a2c2df383d 100644
--- a/llvm/include/llvm/ADT/APFloat.h
+++ b/llvm/include/llvm/ADT/APFloat.h
@@ -744,11 +744,11 @@ class APFloat : public APFloatBase {

     Storage(Storage &&RHS) {
       if (usesLayout<IEEEFloat>(*RHS.semantics)) {
-        new (this) IEEEFloat(std::move(RHS.IEEE));
+        new ((char*)this+9) IEEEFloat(std::move(RHS.IEEE));
         return;
       }
       if (usesLayout<DoubleAPFloat>(*RHS.semantics)) {
-        new (this) DoubleAPFloat(std::move(RHS.Double));
+        new ((char*)this+9) DoubleAPFloat(std::move(RHS.Double));
         return;
       }
       llvm_unreachable("Unexpected semantics");
diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h
index 148d319c860..d0b23ed531b 100644
--- a/llvm/include/llvm/ADT/DenseMap.h
+++ b/llvm/include/llvm/ADT/DenseMap.h
@@ -1024,8 +1024,8 @@ public:
             !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
           assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
                  "Too many inline buckets!");
-          ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
-          ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
+          ::new ((char*)(&TmpEnd->getFirst())+1) KeyT(std::move(P->getFirst()));
+          ::new ((char*)(&TmpEnd->getSecond())+1) ValueT(std::move(P->getSecond()));
           ++TmpEnd;
           P->getSecond().~ValueT();
         }

And the results were what we expect, the checker did find the bugs:

) CodeChecker parse --print-steps reports
Found no defects in DeclBase.cpp
[LOW] /usr/include/c++/7/bits/atomic_base.h:188:20: Value stored to '__b' during its initialization is never read [deadcode.DeadStores]
      memory_order __b = __m & __memory_order_mask;
                   ^
  Report hash: 311a73855b3f4477ee6a4d02482e7c09
  Steps:
    1, atomic_base.h:188:20: Value stored to '__b' during its initialization is never read

[LOW] /usr/include/c++/7/bits/atomic_base.h:199:20: Value stored to '__b' during its initialization is never read [deadcode.DeadStores]
      memory_order __b = __m & __memory_order_mask;
                   ^
  Report hash: 890f61293b984671c6bf407dbbf4352a
  Steps:
    1, atomic_base.h:199:20: Value stored to '__b' during its initialization is never read

Found 2 defect(s) in atomic_base.h

[UNSPECIFIED] /home/egbomrt/WORK/llvm3/git/llvm-project/llvm/include/llvm/ADT/DenseMap.h:1027:11: Storage provided to placement new is only 7 bytes, whereas the allocated type requires 8 bytes [alpha.cplusplus.PlacementNew]
          ::new ((char*)(&TmpEnd->getFirst())+1) KeyT(std::move(P->getFirst()));
          ^
  Report hash: f071e20e8c91262aa78711a1707638aa
  Macro expansions:
    1, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
    2, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
  Steps:
     1, DenseMap.h:1009:9: Assuming 'AtLeast' is <= 2
     2, DenseMap.h:1012:9: Assuming field 'Small' is not equal to 0
     3, DenseMap.h:1022:63: Entering loop body
     4, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
     5, DenseMapInfo.h:56:3: Entered call from 'SmallDenseMap::grow'
     6, DenseMapInfo.h:56:60: Assuming 'LHS' is not equal to 'RHS'
     7, DenseMapInfo.h:56:53: Returning zero, which participates in a condition later
     8, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
     9, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    10, DenseMapInfo.h:56:3: Entered call from 'SmallDenseMap::grow'
    11, DenseMapInfo.h:56:60: Assuming 'LHS' is not equal to 'RHS'
    12, DenseMapInfo.h:56:53: Returning zero, which participates in a condition later
    13, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    14, DenseMap.h:1022:7: Looping back to the head of the loop
    15, DenseMap.h:1022:63: Entering loop body
    16, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
    17, DenseMapInfo.h:56:3: Entered call from 'SmallDenseMap::grow'
    18, DenseMapInfo.h:56:60: Assuming 'LHS' is not equal to 'RHS'
    19, DenseMapInfo.h:56:53: Returning zero, which participates in a condition later
    20, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
    21, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    22, DenseMapInfo.h:56:3: Entered call from 'SmallDenseMap::grow'
    23, DenseMapInfo.h:56:60: Assuming 'LHS' is not equal to 'RHS'
    24, DenseMapInfo.h:56:53: Returning zero, which participates in a condition later
    25, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    26, DenseMap.h:1027:11: Storage provided to placement new is only 7 bytes, whereas the allocated type requires 8 bytes

[UNSPECIFIED] /home/egbomrt/WORK/llvm3/git/llvm-project/llvm/include/llvm/ADT/DenseMap.h:1028:11: Storage provided to placement new is only 7 bytes, whereas the allocated type requires 8 bytes [alpha.cplusplus.PlacementNew]
          ::new ((char*)(&TmpEnd->getSecond())+1) ValueT(std::move(P->getSecond()));
          ^
  Report hash: 55397aa7482521d0220a1d7a1e943e68
  Macro expansions:
    1, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
    2, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
    3, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
    4, DenseMap.h:1025:11: Macro 'assert' expanded to '(static_cast <bool> (size_t(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!") ? void (0) : __assert_fail ("size_t"(TmpEnd - TmpBegin) < InlineBuckets && "Too many inline buckets!",,,__extension__ __PRETTY_FUNCTION__))'
  Steps:
     1, DenseMap.h:1009:9: Assuming 'AtLeast' is <= 4
     2, DenseMap.h:1012:9: Assuming field 'Small' is not equal to 0
     3, DenseMap.h:1022:63: Entering loop body
     4, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
     5, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
     6, DeclarationName.h:856:12: Calling 'operator=='
     7, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
     8, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
     9, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    10, DeclarationName.h:856:12: Returning from 'operator=='
    11, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    12, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
    13, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    14, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    15, DeclarationName.h:856:12: Calling 'operator=='
    16, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    17, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    18, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    19, DeclarationName.h:856:12: Returning from 'operator=='
    20, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    21, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    22, DenseMap.h:1022:7: Looping back to the head of the loop
    23, DenseMap.h:1022:63: Entering loop body
    24, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
    25, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    26, DeclarationName.h:856:12: Calling 'operator=='
    27, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    28, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    29, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    30, DeclarationName.h:856:12: Returning from 'operator=='
    31, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    32, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
    33, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    34, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    35, DeclarationName.h:856:12: Calling 'operator=='
    36, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    37, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    38, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    39, DeclarationName.h:856:12: Returning from 'operator=='
    40, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    41, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    42, DenseMap.h:1022:7: Looping back to the head of the loop
    43, DenseMap.h:1022:63: Entering loop body
    44, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
    45, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    46, DeclarationName.h:856:12: Calling 'operator=='
    47, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    48, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    49, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    50, DeclarationName.h:856:12: Returning from 'operator=='
    51, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    52, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
    53, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    54, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    55, DeclarationName.h:856:12: Calling 'operator=='
    56, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    57, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    58, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    59, DeclarationName.h:856:12: Returning from 'operator=='
    60, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    61, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    62, DenseMap.h:1022:7: Looping back to the head of the loop
    63, DenseMap.h:1022:63: Entering loop body
    64, DenseMap.h:1023:14: Calling 'DenseMapInfo::isEqual'
    65, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    66, DeclarationName.h:856:12: Calling 'operator=='
    67, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    68, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    69, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    70, DeclarationName.h:856:12: Returning from 'operator=='
    71, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    72, DenseMap.h:1023:14: Returning from 'DenseMapInfo::isEqual'
    73, DenseMap.h:1024:14: Calling 'DenseMapInfo::isEqual'
    74, DeclarationName.h:854:3: Entered call from 'SmallDenseMap::grow'
    75, DeclarationName.h:856:12: Calling 'operator=='
    76, DeclarationName.h:508:3: Entered call from 'DenseMapInfo::isEqual'
    77, DeclarationName.h:509:12: Assuming 'LHS.Ptr' is not equal to 'RHS.Ptr'
    78, DeclarationName.h:509:5: Returning zero, which participates in a condition later
    79, DeclarationName.h:856:12: Returning from 'operator=='
    80, DeclarationName.h:856:5: Returning zero, which participates in a condition later
    81, DenseMap.h:1024:14: Returning from 'DenseMapInfo::isEqual'
    82, DenseMap.h:1028:11: Storage provided to placement new is only 7 bytes, whereas the allocated type requires 8 bytes

Found 2 defect(s) in DenseMap.h

[UNSPECIFIED] /home/egbomrt/WORK/llvm3/git/llvm-project/llvm/include/llvm/ADT/APFloat.h:747:9: Storage provided to placement new is only 15 bytes, whereas the allocated type requires 24 bytes [alpha.cplusplus.PlacementNew]
        new ((char*)this+9) IEEEFloat(std::move(RHS.IEEE));
        ^
  Report hash: 9133b47ccf3bf5f13d39a52ecfdcf6c9
  Steps:
    1, APValue.h:302:41: Calling defaulted move constructor for 'APFloat'
    2, APFloat.h:866:3: Calling move constructor for 'Storage'
    3, APFloat.h:745:5: Entered call from move constructor for 'APFloat'
    4, APFloat.h:746:11: Calling 'APFloat::usesLayout'
    5, APFloat.h:786:25: Entered call from move constructor for 'Storage'
    6, APFloat.h:792:12: Assuming the condition is true
    7, APFloat.h:792:5: Returning the value 1, which participates in a condition later
    8, APFloat.h:746:11: Returning from 'APFloat::usesLayout'
    9, APFloat.h:747:9: Storage provided to placement new is only 15 bytes, whereas the allocated type requires 24 bytes

[UNSPECIFIED] /home/egbomrt/WORK/llvm3/git/llvm-project/llvm/include/llvm/ADT/APFloat.h:751:9: Storage provided to placement new is only 15 bytes, whereas the allocated type requires 16 bytes [alpha.cplusplus.PlacementNew]
        new ((char*)this+9) DoubleAPFloat(std::move(RHS.Double));
        ^
  Report hash: 211361aa54ffb5efef56661583f29ee5
  Steps:
    1, APValue.h:302:41: Calling defaulted move constructor for 'APFloat'
    2, APFloat.h:866:3: Calling move constructor for 'Storage'
    3, APFloat.h:745:5: Entered call from move constructor for 'APFloat'
    4, APFloat.h:746:11: Calling 'APFloat::usesLayout'
    5, APFloat.h:786:25: Entered call from move constructor for 'Storage'
    6, APFloat.h:792:12: Assuming the condition is false
    7, APFloat.h:792:5: Returning zero, which participates in a condition later
    8, APFloat.h:746:11: Returning from 'APFloat::usesLayout'
    9, APFloat.h:751:9: Storage provided to placement new is only 15 bytes, whereas the allocated type requires 16 bytes

Found 2 defect(s) in APFloat.h


----==== Summary ====----
----------------------------
Filename      | Report count
----------------------------
atomic_base.h |            2
APFloat.h     |            2
DenseMap.h    |            2
----------------------------
--------------------------
Severity    | Report count
--------------------------
UNSPECIFIED |            4
LOW         |            2
--------------------------
----=================----
Total number of reports: 6
----=================----

I didn't check the statistics, because it seems that for the first run the checker did not find any results simply because there were none in the LLVM codebase. So I am not sure what data could be useful from the statistics in this case.
Anyway, this kind of experiment makes me confident with this checker. Is there anything else you think is worth for testing before making the checker default enabled? Thanks!

[NoQ]

This looks fantastic. Let's enable by it default!

[martong]

In D71612#1828059, @NoQ wrote:

This looks fantastic. Let's enable by it default!

Ok, I've done that: https://github.com/llvm/llvm-project/commit/bc29069dc40

[NoQ]

🎉🎉🎉

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

2

Header blurb is missing :) Could you sneak it in there?

[martong]

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

2

Sure, I am getting right on it.

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

def NewDeleteChecker : Checker<"NewDelete">,
   Dependencies<[DynamicMemoryModeling]>,
   Documentation<HasDocumentation>;
 
 def NewDeleteLeaksChecker : Checker<"NewDeleteLeaks">,
   HelpText<"Check for memory leaks. Traces memory managed by new/delete.">,
   Dependencies<[NewDeleteChecker]>,
   Documentation<HasDocumentation>;
 
+def PlacementNewChecker : Checker<"PlacementNew">,
+  HelpText<"Check if default placement new is provided with pointers to "
+           "sufficient storage capacity">,
+  Dependencies<[NewDeleteChecker]>,
+  Documentation<HasDocumentation>;
+
 def CXXSelfAssignmentChecker : Checker<"SelfAssignment">,
   HelpText<"Checks C++ copy and move assignment operators for self assignment">,
   Documentation<NotDocumented>,
   Hidden;
 
 def SmartPtrModeling: Checker<"SmartPtr">,
   HelpText<"Model behavior of C++ smart pointers">,
   Documentation<NotDocumented>,

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   CStringChecker.cpp
   CStringSyntaxChecker.cpp
   CallAndMessageChecker.cpp
   CastSizeChecker.cpp
   CastToStructChecker.cpp
   CastValueChecker.cpp
   CheckObjCDealloc.cpp
   CheckObjCInstMethSignature.cpp
+  CheckPlacementNew.cpp
   CheckSecuritySyntaxOnly.cpp
   CheckSizeofPointer.cpp
   CheckerDocumentation.cpp
   ChrootChecker.cpp
   CloneChecker.cpp
   ConversionChecker.cpp
   CXXSelfAssignmentChecker.cpp
   DeadStoresChecker.cpp

clang/lib/StaticAnalyzer/Checkers/CheckPlacementNew.cpp

+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/Support/FormatVariadic.h"
+
+using namespace clang;
+using namespace ento;
+
+class PlacementNewChecker : public Checker<check::PreStmt<CXXNewExpr>> {
+public:
+  void checkPreStmt(const CXXNewExpr *NE, CheckerContext &C) const;
+
+private:
+  // Returns the size of the target in a placement new expression.
+  // E.g. in "new (&s) long" it returns the size of `long`.
+  SVal getExtentSizeOfNewTarget(CheckerContext &C, const CXXNewExpr *NE,
+                                ProgramStateRef State) const;
+  // Returns the size of the place in a placement new expression.
+  // E.g. in "new (&s) long" it returns the size of `s`.
+  SVal getExtentSizeOfPlace(CheckerContext &C, const Expr *NE,
+                            ProgramStateRef State) const;
+  mutable std::unique_ptr<BuiltinBug> BT_Placement;
+};
+
+SVal PlacementNewChecker::getExtentSizeOfPlace(CheckerContext &C,
+                                               const Expr *Place,
+                                               ProgramStateRef State) const {
+  SVal SV = C.getSVal(Place);
+  const MemRegion *MRegion = SV.getAsRegion();
+  SValBuilder &svalBuilder = C.getSValBuilder();
+
+  // Handle pointers that point into an array. E.g.:
+  //   char *buf = new char[2];
+  //   long *lp = ::new (buf) long;
+  if (const auto *TVRegion = dyn_cast<TypedValueRegion>(MRegion))
+    // FIXME Handle offset other than 0. E.g.:
+    //   char *buf = new char[8];
+    //   long *lp = ::new (buf + 1) long;
+    if (const auto *ERegion = dyn_cast<ElementRegion>(TVRegion)) {
+      const auto *SRegion = cast<SubRegion>(ERegion->getSuperRegion());
+      DefinedOrUnknownSVal Extent = SRegion->getExtent(svalBuilder);
+      // Get the known size of the heap allocated storage.
+      // This is modelled by the MallocChecker.
+      const llvm::APSInt *ExtentInt = svalBuilder.getKnownValue(State, Extent);
+      if (!ExtentInt)
+        return UnknownVal();
+      return svalBuilder.makeIntVal(ExtentInt->getExtValue(),
+                                    svalBuilder.getArrayIndexType());
+    }
+
+  // Pointer to an array, e.g.:
+  //   char *buf = new char[2];
+  //   long *lp = ::new (&buf) long;
+  // Or pointer to a simple variable:
+  //   short s;
+  //   long *lp = ::new (&s) long;
+  const auto *SRegion = MRegion->castAs<SubRegion>();
+  DefinedOrUnknownSVal Extent = SRegion->getExtent(svalBuilder);
+  return Extent;
+}
+
+SVal PlacementNewChecker::getExtentSizeOfNewTarget(
+    CheckerContext &C, const CXXNewExpr *NE, ProgramStateRef State) const {
+  if (!State)
+    return SVal();
+  SValBuilder &svalBuilder = C.getSValBuilder();
+  SVal ElementCount;
+  if (NE->isArray()) {
+    const Expr *SizeExpr = *NE->getArraySize();
+    ElementCount = C.getSVal(SizeExpr);
+  } else {
+    ElementCount = svalBuilder.makeIntVal(1, true);
+  }
+
+  QualType ElementType = NE->getAllocatedType();
+  ASTContext &AstContext = C.getASTContext();
+  CharUnits TypeSize = AstContext.getTypeSizeInChars(ElementType);
+
+  if (ElementCount.getAs<NonLoc>()) {
+    // size in Bytes = ElementCount*TypeSize
+    SVal SizeInBytes = svalBuilder.evalBinOpNN(
+        State, BO_Mul, ElementCount.castAs<NonLoc>(),
+        svalBuilder.makeArrayIndex(TypeSize.getQuantity()),
+        svalBuilder.getArrayIndexType());
+    return SizeInBytes;
+  }
+  return SVal();
+}
+
+void PlacementNewChecker::checkPreStmt(const CXXNewExpr *NE,
+                                       CheckerContext &C) const {
+  // Check only the default placement new.
+  if (!NE->getOperatorNew()->isReservedGlobalPlacementOperator())
+    return;
+  if (NE->getNumPlacementArgs() == 0)
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal SizeOfTarget = getExtentSizeOfNewTarget(C, NE, State);
+  const Expr *Place = NE->getPlacementArg(0);
+  SVal SizeOfPlace = getExtentSizeOfPlace(C, Place, State);
+  const auto SizeOfTargetCI = SizeOfTarget.getAs<nonloc::ConcreteInt>();
+  if (!SizeOfTargetCI)
+    return;
+  const auto SizeOfPlaceCI = SizeOfPlace.getAs<nonloc::ConcreteInt>();
+  if (!SizeOfPlaceCI)
+    return;
+
+  if (SizeOfPlaceCI->getValue() < SizeOfTargetCI->getValue()) {
+    if (ExplodedNode *N = C.generateErrorNode(State)) {
+      if (!BT_Placement)
+        BT_Placement.reset(new BuiltinBug(this, "Insufficient storage BB"));
+
+      std::string Msg =
+          llvm::formatv("Argument of default placement new provides storage "
+                        "capacity of {0} bytes, but the allocated type "
+                        "requires storage capacity of {1} bytes",
+                        SizeOfPlaceCI->getValue(), SizeOfTargetCI->getValue());
+
+      auto R = std::make_unique<PathSensitiveBugReport>(*BT_Placement, Msg, N);
+      bugreporter::trackExpressionValue(N, Place, *R);
+      C.emitReport(std::move(R));
+      return;
+    }
+  }
+}
+
+void ento::registerPlacementNewChecker(CheckerManager &mgr) {
+  mgr.registerChecker<PlacementNewChecker>();
+}
+
+bool ento::shouldRegisterPlacementNewChecker(const LangOptions &LO) {
+  return true;
+}

clang/test/Analysis/placement-new-user-defined.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 %s \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-checker=cplusplus.NewDelete \
+// RUN:   -analyzer-checker=cplusplus.PlacementNew \
+// RUN:   -analyzer-output=text -verify \
+// RUN:   -triple x86_64-unknown-linux-gnu
+
+// expected-no-diagnostics
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+struct X {
+  static void *operator new(std::size_t sz, void *b) {
+    return ::operator new(sz, b);
+  }
+  long l;
+};
+void f() {
+  short buf;
+  X *p1 = new (&buf) X;
+  (void)p1;
+}

clang/test/Analysis/placement-new.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 %s \
+// RUN:   -analyzer-checker=core \
+// RUN:   -analyzer-checker=cplusplus.NewDelete \
+// RUN:   -analyzer-checker=cplusplus.PlacementNew \
+// RUN:   -analyzer-output=text -verify \
+// RUN:   -triple x86_64-unknown-linux-gnu
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void f() {
+  short s; // expected-note-re {{'s' declared{{.*}}}}
+  long *lp = ::new (&s) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 3 {{}}
+  (void)lp;
+}
+
+namespace testArrayNew {
+void f() {
+  short s; // expected-note-re {{'s' declared{{.*}}}}
+  char *buf = ::new (&s) char[8]; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 3 {{}}
+  (void)buf;
+}
+} // namespace testArrayNew
+
+namespace testBufferInOtherFun {
+void f(void *place) {
+  long *lp = ::new (place) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+void g() {
+  short buf; // expected-note-re {{'buf' declared{{.*}}}}
+  f(&buf); // expected-note 2 {{}}
+}
+} // namespace testBufferInOtherFun
+
+namespace testArrayBuffer {
+void f(void *place) {
+  long *lp = ::new (place) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+void g() {
+  char buf[2]; // expected-note-re {{'buf' initialized{{.*}}}}
+  f(&buf); // expected-note 2 {{}}
+}
+} // namespace testArrayBuffer
+
+namespace testGlobalPtrAsPlace {
+void *gptr = nullptr;
+short gs;
+void f() {
+  gptr = &gs; // expected-note {{Value assigned to 'gptr'}}
+}
+void g() {
+  f(); // expected-note 2 {{}}
+  long *lp = ::new (gptr) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+} // namespace testGlobalPtrAsPlace
+
+namespace testRvalue {
+short gs;
+void *f() {
+  return &gs;
+}
+void g() {
+  long *lp = ::new (f()) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+} // namespace testRvalue
+
+namespace testNoWarning {
+void *f();
+void g() {
+  long *lp = ::new (f()) long;
+  (void)lp;
+}
+} // namespace testNoWarning
+
+namespace testPtrToArrayAsPlace {
+void f() {
+  //char *st = new char [8];
+  char buf[3]; // expected-note-re {{'buf' initialized{{.*}}}}
+  void *st = buf; // expected-note-re {{'st' initialized{{.*}}}}
+  long *lp = ::new (st) long; // expected-warning{{Argument of default placement new provides storage capacity of 3 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+} // namespace testPtrToArrayAsPlace
+
+namespace testHeapAllocatedBuffer {
+void g2() {
+  char *buf = new char[2]; // expected-note-re {{'buf' initialized{{.*}}}}
+  long *lp = ::new (buf) long; // expected-warning{{Argument of default placement new provides storage capacity of 2 bytes, but the allocated type requires storage capacity of 8 bytes}} expected-note 1 {{}}
+  (void)lp;
+}
+} // namespace testHeapAllocatedBuffer