[analyzer][Review request] Partial fix for PR19102.

[ayartsev]

Summary

Attached patch is a partial fix for PR19102. The idea is to assume the unused operator new as not a leak if the following requirement is met:

• The invoked constructor has a parameter - pointer or reference to a record that has a public method (any access level , if a constructed record is a friend of a parameter record), that accepts a pointer to the type of the constructed record or one of its bases.

The analysis can be much more precise if the analyzer can analyze the body of the constructor, but for now the criteria above can be used regardless of whether the body of the constructor is accessible to the analyzer or not.
Please review.

[jordan_rose]

This is searching all the methods on the class being passed, but what about its superclasses?

You should definitely be caching this information. I'm also just still worried that this is a very expensive search for every record parameter of every constructor, even if you collected all the types referenced by each class instead of just looking for a particular one.

[ayartsev]

Now searching on the class and all superclasses that has methods accessible from the constructed record. Referenced types are now cached.

The search is expensive, but the case is very rare I hope. Only unassigned new are analyzed this way.

[jordan_rose]

Now that I'm paging this back in...I'm not convinced. People who use unassigned new usually know what they're doing. The false positives come when someone uses new while storing the result, but they also escape the variable into storage somewhere.

For the unused result case, I wonder if a -Wunused-like warning would cover this: warn on un-consumed new, silence it by casting to void, and assume any un-consumed new has already escaped (unless we inlined the constructor or can see it is trivial).

I'd be tempted to ignore the used case except that that's blocking adoption in LLVM. We'd have to get sign-on from llvmdev if we wanted to change the new Value(module, ...) idiom they have going on there (e.g. to something like Value::create(module, ...).)

[ayartsev]

Simplified the check, an un-consumed new is now treated a leak unless the constructor has a parameter of a pointer-to-record type. The check is not expensive and covers LLVM cases.

Did not added -Wunused-like new warning for now. Do you think this warning is needed apart from the checker? Doubt it ever be used. Anyway I think it is better to implement the warning as a separate patch as the change is not analyzer specific.

Is there a way to get the constructor inlined when it is called from a new expression? ExprEngine::VisitCXXConstructExpr() always left 'wasInlined' equal 'false'.

[ayartsev]

Ping!

[jordan_rose]

IIRC, constructors are never inlined for 'new' right now because we never got the right region, and I was always hoping we'd implement proper allocator support first (http://llvm.org/bugs/show_bug.cgi?id=12014). Karthik Bhat was working on this but I don't remember how far he got. We also didn't have destructor support for 'delete' until last fall (also thanks to Karthik).

Other than that this is looking pretty good. More tests would be nice, and possibly a test on a real code base that would otherwise have false positives. Unfortunately the only one I can think of is LLVM itself, but even that could tell us how many false positives we've gone down by.

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

781

Style nitpick: * next to the variable name.

785–786

getAsCXXRecordDecl will call getCanonicalType for you, so you can skip that step.

789

Please make this const (and move the *).

798–799

I don't think you need to worry about either canonicalizing the type or stripping qualifiers.

[ayartsev]

Done! Ok to commit?
Just ran the updated NewDeleteLeaks checker over LLVM codebase with -analyzer-opt-analyze-headers option turned on. Failed to attach reports in Phabricator, I'll send them with the next mail.

[ayartsev]

Attached are leak reports generated by NewDeleteLeaks checker ran over
the LLVM codebase with -analyzer-opt-analyze-headers option turned on.
Haven't addressed them yet. Looking at suspicious leak reports generated
from headers (e.g. reports from TinyPtrVector.h).

• NewDeleteLeaks_reports.zip423 KBDownload

[jordan_rose]

You're still missing tests that show that the leaks are reported no matter what the arguments are if the newly-created instance is consumed. But other than that this looks good; please commit once you've added those!

(Yes, I know they're present elsewhere in the test suite, but it's good to have some explicit ones here.)

[ayartsev]

Committed as r214909.

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

 // This file defines malloc/free checker, which checks for potential memory
 // leaks, double free, and use-after-free problems.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.h"
 #include "InterCheckerAPI.h"
 #include "clang/AST/Attr.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/AST/DeclFriend.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
struct ReallocPair {
   bool operator==(const ReallocPair &X) const {
     return ReallocatedSym == X.ReallocatedSym &&
            Kind == X.Kind;
   }
 };
 
 typedef std::pair<const ExplodedNode*, const MemRegion*> LeakInfo;
 
+typedef llvm::SmallDenseMap<const CXXRecordDecl *, bool, 8> RecordDeclToBoolMap;
+
 class MallocChecker : public Checker<check::DeadSymbols,
                                      check::PointerEscape,
                                      check::ConstPointerEscape,
                                      check::PreStmt<ReturnStmt>,
                                      check::PreCall,
                                      check::PostStmt<CallExpr>,
                                      check::PostStmt<CXXNewExpr>,
                                      check::PreStmt<CXXDeleteExpr>,
private:
   mutable std::unique_ptr<BugType> BT_BadFree[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_MismatchedDealloc;
   mutable std::unique_ptr<BugType> BT_OffsetFree[CK_NumCheckKinds];
   mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc,
                          *II_valloc, *II_reallocf, *II_strndup, *II_strdup,
                          *II_kmalloc;
   mutable Optional<uint64_t> KernelZeroFlagVal;
 
+  typedef llvm::DenseMap<const CXXRecordDecl *, 
+                         llvm::SmallPtrSet<QualType, 32>> RecToReferencedTypesMapTy;
+  // Cache used to speed up unusedNewCanEscape.
+  mutable RecToReferencedTypesMapTy RecToReferencedTypesMap;
+
+
   void initIdentifierInfo(ASTContext &C) const;
 
   /// \brief Determine family of a deallocation expression.
   AllocationFamily getAllocationFamily(CheckerContext &C, const Stmt *S) const;
 
   /// \brief Print names of allocators and deallocators.
   ///
   /// \returns true on success.
private:
   ///@{
   /// Check if this is one of the functions which can allocate/reallocate memory 
   /// pointed to by one of its arguments.
   bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const;
   bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const;
   bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const;
   bool isStandardNewDelete(const FunctionDecl *FD, ASTContext &C) const;
   ///@}
+
+  /// \brief Check if a given unassigned new can potentially escape.
+  bool unusedNewCanEscape(const CXXNewExpr *NE) const;
+
   ProgramStateRef MallocMemReturnsAttr(CheckerContext &C,
                                        const CallExpr *CE,
                                        const OwnershipAttr* Att) const;
   static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE,
                                      const Expr *SizeEx, SVal Init,
                                      ProgramStateRef State,
                                      AllocationFamily Family = AF_Malloc) {
     return MallocMemAux(C, CE,
if (FD->hasAttrs())
           State = FreeMemAttr(C, CE, I);
           break;
         }
       }
   }
   C.addTransition(State);
 }
 
+static QualType getDeepPointeeType(QualType T) {
+  QualType Result = T, PointeeType = T->getPointeeType();
+  while (!PointeeType.isNull()) {
+    Result = PointeeType;
+    PointeeType = PointeeType->getPointeeType();
+  }
+  return Result;
+}
+
+// Tells if Ty is a friend of RD.
+static bool isFriendOfRD(const CXXRecordDecl *RD, QualType Ty) {
+  for (const auto *FriendOfRD : RD->friends()) {
+    if (TypeSourceInfo *FriendType = FriendOfRD->getFriendType()) {
+      if (FriendType->getType().getCanonicalType() == Ty) {
+        return true;
+      }
+    }
+  }
+
+  return false;
+};
+
+// Collect RD and all superclasses with exception of those whose methods are
+// guaranteed inaccessible from the ConstructedTy record.
+static void 
+collectRecordsWithAccessibleMethods(RecordDeclToBoolMap &Records,
+                                    const CXXRecordDecl *RD,
+                                    QualType ConstructedTy) {
+  if (!Records.count(RD))
+    Records[RD] = isFriendOfRD(RD, ConstructedTy);
+
+  for (const auto &Base : RD->bases()) {
+    if (Base.getAccessSpecifier() != AS_public && !Records[RD])
+      continue;
+
+    if (const CXXRecordDecl *BaseRD = Base.getType()->getAsCXXRecordDecl())
+        collectRecordsWithAccessibleMethods(Records, BaseRD, ConstructedTy);
+  }
+}
+
+bool MallocChecker::unusedNewCanEscape(const CXXNewExpr *NE) const {
+  // There are cases when the result of a call to nonplacement operator new is
+  // not used, but nevertheless, the memory may not be leaked. The memory can
+  // escape in the constructor of the constructed object. For example:
+  //
+  // void f(B* b) {
+  //   new A(b);
+  // }
+  //
+  // 'A's constructor:
+  // A(B *b) {
+  //   b->escapeA(this); // memory escapes!
+  // }
+  //
+  // (PR19102 is devoted to the problem and contain a full example).
+  // To reduce the number of false-positives we assume the unused operator new
+  // as not a leak if the following requirement is met:
+  // * The invoked constructor has a parameter - pointer or reference to a
+  //   record that has a public method (any access level , if a constructed
+  //   record is a friend of parameter record), that accepts a pointer to the
+  //   type of the constructed record or one of its bases.
+
+  const CXXConstructExpr* ConstructE = NE->getConstructExpr();
+  if (!ConstructE)
+    return false;
+
+  QualType ConstructedTy = NE->getAllocatedType().getCanonicalType();
+  const CXXRecordDecl *ConstructedRD = ConstructedTy->getAsCXXRecordDecl();
+  if (!ConstructedRD)
+    return false;
+
+  CXXConstructorDecl* CtorD = ConstructE->getConstructor();
+
+  // Iterate over the constructor parameters.
+  for (const auto *CtorParam : CtorD->params()) {
+
+    QualType CtorParamPointeeT = CtorParam->getType()->getPointeeType();
+    if (CtorParamPointeeT.isNull())
+      continue;
+
+    CtorParamPointeeT = getDeepPointeeType(CtorParamPointeeT).
+                        getCanonicalType().getUnqualifiedType();
+
+    const CXXRecordDecl *RD = CtorParamPointeeT->getAsCXXRecordDecl();
+    if (!RD)
+      continue;
+    // Found a parameter of the pointer-to-a-record type.
+
+    // Collect the record and all its superclasses that have methods accessible
+    // from a constructed record.
+    RecordDeclToBoolMap recordsWithAccessibleMethods;
+    collectRecordsWithAccessibleMethods(recordsWithAccessibleMethods, RD,
+                                        ConstructedTy);
+
+    // Lookup for a method that accepts a pointer to a constructed record type 
+    // among the collected records. If the method is found we do not consider an
+    // unassigned memory as a leak as the memory ('this' pointer) could 
+    // potentially be passed to the method and escape.
+    for (const auto &Record : recordsWithAccessibleMethods) {
+      
+      // First lookup in the cache.
+      if (RecToReferencedTypesMap.count(Record.first)) {
+        auto const &ReferencedTypes = RecToReferencedTypesMap[Record.first];
+
+        if (ReferencedTypes.count(ConstructedTy))
+          return true;
+
+        // Iterate over bases of a constructed class.
+        for (const auto &ConstructedBase : ConstructedRD->bases()) {
+          QualType CBTy = ConstructedBase.getType();
+          if (!CBTy.isNull() && ReferencedTypes.count(CBTy.getUnqualifiedType()))
+            return true;
+        }
+
+        continue;
+      }
+
+      // We collect record types referenced by methods of a record being 
+      // processed to speed up lookup next time.
+      RecToReferencedTypesMapTy::mapped_type ReferencedTypesCollector;
+
+      // Types referenced by a records methods were not cached, lookup among 
+      // all parameters of all accessible methods.
+      for (const auto *Method : Record.first->methods()) {
+
+        if (!Record.second && Method->getAccess() != AS_public)
+          // Method access level is not public and constructed record is
+          // not a friend of a processed record - the method is inaccessible 
+          // from a constructed record.
+          continue;
+
+        // Iterate over method parameters, try to find one of a type of a 
+        // constructed record or one of its bases.
+        for (const auto *MethodParam : Method->params()) {
+          QualType MPPointeeT = MethodParam->getType()->getPointeeType();
+          if (MPPointeeT.isNull())
+            continue;
+
+          MPPointeeT = getDeepPointeeType(MPPointeeT).getCanonicalType();
+          if (!isa<RecordType>(MPPointeeT))
+            continue;
+
+          ReferencedTypesCollector.insert(MPPointeeT);
+
+          if (MPPointeeT == ConstructedTy)
+            return true;
+
+          // Iterate over bases of a constructed class.
+          for (const auto &ConstructedBase : ConstructedRD->bases()) {
+            QualType CBTy = ConstructedBase.getType();
+            if (!CBTy.isNull() && MPPointeeT == CBTy.getUnqualifiedType())
+              return true;
+          }
+        }
+      }
+      // Cache referenced types.
+      RecToReferencedTypesMap[Record.first] = ReferencedTypesCollector;
+    }
+  }
+
+  return false;
+}
+
 void MallocChecker::checkPostStmt(const CXXNewExpr *NE, 
                                   CheckerContext &C) const {
 
   if (NE->getNumPlacementArgs())
     for (CXXNewExpr::const_arg_iterator I = NE->placement_arg_begin(),
          E = NE->placement_arg_end(); I != E; ++I)
       if (SymbolRef Sym = C.getSVal(*I).getAsSymbol())
         checkUseAfterFree(Sym, C, *I);
 
   if (!isStandardNewDelete(NE->getOperatorNew(), C.getASTContext()))
     return;
 
+  ParentMap &PM = C.getLocationContext()->getParentMap();
+  if (!PM.isConsumedExpr(NE) && unusedNewCanEscape(NE))
+    return;
+
   ProgramStateRef State = C.getState();
   // The return value from operator new is bound to a specified initialization 
   // value (if any) and we don't want to loose this value. So we call 
   // MallocUpdateRefState() instead of MallocMemAux() which breakes the 
   // existing binding.
   State = MallocUpdateRefState(C, NE, State, NE->isArray() ? AF_CXXNewArray 
                                                            : AF_CXXNew);
   C.addTransition(State);

test/Analysis/NewDeleteLeaks-PR19102.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.cplusplus.NewDeleteLeaks -std=c++11 -verify %s
+
+class B1;
+
+class A0 {
+public:
+  // Parameter is passed by value, b1 is not treated escaped.
+  void SetB1(B1 b1);
+};
+
+class A1 {
+public:
+  void SetB1(B1* b1);
+};
+
+class A2 {
+  // SetB1 is private and A2 is not a friend of B1, b1 is not treated escaped.
+  void SetB1(B1* b1);
+};
+
+class A3 {
+protected:
+  // SetB1 is protected and A2 is not a friend of B1, b1 is not treated escaped.
+  void SetB1(B1* b1);
+};
+
+class A4 {
+  friend class B1;
+  void SetB1(B1* b1);
+};
+
+class A5 {
+protected:
+  friend class B1;
+  void SetB1(int, B1& b1);
+};
+
+class A6 {
+public:
+  void SetB1(B1* &b1);
+};
+
+class AA_base0 {
+  void SetB1(B1* b1);
+};
+
+class AA_base1 {
+public:
+  void SetB1(B1* b1);
+};
+
+class AA_base2 {
+friend class B1;
+  void SetB1(B1* b1);
+};
+
+class AA_base3 : public AA_base2 {};
+
+class AA0 : public AA_base0 {}; // SetB1 is private, inaccessible from outside.
+
+class AA1 : public AA_base1 {};
+
+class AA2 : public AA_base2 {};
+
+class AA3 : AA_base1 {}; // private inheritance, SetB1 is inaccessible from outside.
+
+class AA4 : protected AA_base1 {}; // protected inheritance, SetB1 is inaccessible from outside.
+
+class AA5 : private AA_base2 {}; // private inheritance, SetB1 is inaccessible from outside.
+
+class AA6 : private AA_base1 {
+friend class B1;
+};
+
+class AA7 : private AA_base3 {
+friend class B1;
+};
+
+class AA8 : public AA_base0, public AA_base1 {};
+
+class AA9 : public AA_base0, protected AA_base1 {}; // SetB1 is inaccessible from outside.
+
+class AA10 : virtual AA_base0, virtual protected AA_base2, virtual public AA_base3 {};
+
+class B1 {
+public:
+  B1(A0 &a0);
+  B1(int);
+  B1(A1 a1);
+  B1(A1* a1);
+  B1(int, A1& a1);
+
+  B1(A2 &a2);
+
+  B1(A3 &a3);
+
+  B1(A4 &a4);
+
+  B1(A5 &a5);
+
+  B1(A6 &a6);
+  B1(A6 **a6);
+
+  B1(AA0 &aa0);
+
+  B1(AA1 &aa1);
+
+  B1(AA2 &aa2);
+
+  B1(AA3 &aa3);
+
+  B1(AA4 &aa4);
+
+  B1(AA5 &aa5);
+
+  B1(AA6 &aa6);
+
+  B1(AA7 &aa7);
+
+  B1(AA8 &aa8);
+
+  B1(AA9 &aa9);
+
+  B1(AA10 &aa10);
+};
+
+class B2: public B1 {
+public:
+  B2(A1 &a1);
+};
+
+void f() {
+  A0 a0;
+  new B1(a0); // expected-warning@+2 {{Potential memory leak}}
+
+  A1 a1;
+  new B1(1); // expected-warning@+1 {{Potential memory leak}}
+  new B1(a1); // expected-warning@+1 {{Potential memory leak}}
+  new B1(&a1); // no warning
+  new B1(1, a1); // no warning
+  new B2(a1); // no warning
+
+  A2 a2;
+  new B1(a2); // expected-warning@+2 {{Potential memory leak}}
+
+  A3 a3;
+  new B1(a3); // expected-warning@+2 {{Potential memory leak}}
+
+  A4 a4;
+  new B1(a4); // no warning
+
+  A5 a5;
+  new B1(a5); // no warning
+
+  A6 a6, *a6p = &a6;
+  new B1(a6); // no warning
+  new B1(&a6p); // no warning
+
+  AA0 aa0;
+  new B1(aa0); // expected-warning@+2 {{Potential memory leak}}
+
+  AA1 aa1;
+  new B1(aa1); // no warning
+
+  AA2 aa2;
+  new B1(aa2); // no warning
+
+  AA3 aa3;
+  new B1(aa3); // expected-warning@+2 {{Potential memory leak}}
+
+  AA4 aa4;
+  new B1(aa4); // expected-warning@+2 {{Potential memory leak}}
+
+  AA5 aa5;
+  new B1(aa5); // expected-warning@+2 {{Potential memory leak}}
+
+  AA6 aa6;
+  new B1(aa6); // no warning
+
+  AA7 aa7;
+  new B1(aa7); // no warning
+
+  AA8 aa8;
+  new B1(aa8); // no warning
+
+  AA9 aa9;
+  new B1(aa9); // expected-warning@+2 {{Potential memory leak}}
+
+  AA10 aa10;
+  new B1(aa10);
+}