[Analyzer][MallocChecker] No warning for kfree of ZERO_SIZE_PTR.

[balazske]

Summary

The kernel kmalloc function may return a constant value ZERO_SIZE_PTR
if a zero-sized block is allocated. This special value is allowed to
be passed to kfree and should produce no warning.

This is a simple version but should be no problem. The macro is always
detected independent of if this is a kernel source code or any other
code. And it is recognized in any kind of free function, not only kfree.
(These functions are used already intermixed, at least in the tests.)

[balazske]

FIXME: There is a test file "kmalloc-linux.c" but it seems to be non-maintained and buggy (has no -verify option so it passes always but produces multiple warnings).

[balazske]

clang/lib/StaticAnalyzer/Core/CheckerHelpers.cpp

146

The function was changed to get the numeric value from the end of the macro in any case. This way it recognizes a (void *)16 as 16 (but maybe 16+16 too as 16).

[martong]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

396

Which one is referred to the lazy initialization? The inner or the outer?
These questions actually made me to come up with a more explanatory construct here:
Could we do something like this?

using LazyInitialized = Optional<int>;
mutable Optional<LazyInitialized> KernelZeroSizePtrValue; // Or Lazy<Optional<...>>

1696

This is a bit confusing for me. Perhaps alternatively we could have a free function isInitialized(KernelZero...) instead. Or maybe having a separate bool variable to indicate whether it was initialized could be cleaner?

clang/lib/StaticAnalyzer/Core/CheckerHelpers.cpp

146

Ok.

[martong]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

Another idea: Adding a helper struct to contain the bool initialized? E.g. (draft):

struct LazyOptional {
  bool initialized = false;
  Opt<int> value;
  Opt& get();
  void set(const Opt&);
};

[balazske]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

396

Probably use a std::unique_ptr<Optional<int>> instead (like at the bug types, they could be optional too)?
If there is a code like

bool IsSomethingInitialized;
int Something;

that looks as a clear case to use an optional (or unique_ptr)? And if yes, is a reason for not using this construct if int is replaced by Optional<int>?

1696

It may be OK to have a function lazyInitKernelZeroSizePtrValue?

[martong]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

396

Now I see that the lazy initialization is represented by the outer optional.
So IMHO a using template could be the best to describe cleanly this construct:

template <class T>
using LazyInitialized = Optional<T>;
mutable LazyInitialized<Optional<int>> KernelZeroSizePtrValue;

[martong]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

I don't insist, given we have a better described type for KernelZeroSizePtrValue (e.g. having a using template)

[balazske]

Improved documentation and handling of KernelZeroSizePtrValue.

[balazske]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

396

With this I would wait for opinion of somebody else.

[martong]

LGTM!

clang/test/Analysis/kmalloc-linux-1.c

15

Do you plan to sniff around a bit about the arguments (as part of another patch)? Would be good to handle both old and new signature kernel allocation functions.

[Szelethus]

In D76830#1943133, @balazske wrote:

FIXME: There is a test file "kmalloc-linux.c" but it seems to be non-maintained and buggy (has no -verify option so it passes always but produces multiple warnings).

Crap, even I did some changes on that file, and never noticed the lack of verify, or the lack of -analyzer-checker flags.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1690–1700

I found this article on the subject:

https://lwn.net/Articles/236920/

That brings us to the third possibility: this patch from Christoph Lameter which causes kmalloc(0) to return a special ZERO_SIZE_PTR value. It is a non-NULL value which looks like a legitimate pointer, but which causes a fault on any attempt at dereferencing it. Any attempt to call kfree() with this special value will do the right thing, of course.

But I would argue that using delete on such a pointer might still be a sign of code smell. Granted, if the source code is hacking the kernel this is very unlikely, but still, I think this code should be placed...

1696

AnalysisManager has access to the Preprocessor, and it is also responsible for the construction of the CheckerManager object. This would make moving such code to the checker registry function! I'll gladly take this issue off your hand and patch it in once rG2aac0c47aed8d1eff7ab6d858173c532b881d948 settles :)

1707–1708

...here!

bool isArgZERO_SIZE_PTR(ArgVal) const {
  const llvm::APSInt *ArgValKnown =
      C.getSValBuilder().getKnownValue(State, ArgVal);
  if (ArgValKnown) {
    initKernelZeroSizePtrValue(C.getPreprocessor());
    if (*KernelZeroSizePtrValue &&
        ArgValKnown->getSExtValue() == **KernelZeroSizePtrValue)
      return true;
  }
  return false;
}

// ...

if (ArgVal has no associated MemRegion)
  // If there is a macro called ZERO_SIZE_PTR, it could be a kernel source code
  // and this value indicates a special value used for a zero-sized memory
  // block. It is a constant value that is allowed to be freed.
  if (!isArgZERO_SIZE_PTR(ArgVal)
    ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr, Family);
    return nullptr;
  }
  // Still check for incorrect deallocator usage, etc.
}

Or something like this. WDYT?

clang/test/Analysis/kmalloc-linux-1.c

15

I'll take a quick look as well, I am quite familiar with MallocChecker.

[balazske]

clang/test/Analysis/kmalloc-linux-1.c

15

I found that kfree has one argument, not two (even in the 2.6 kernel). Probably argument count was wrong in the last change when CallDescription was introduced.

[Szelethus]

clang/test/Analysis/kmalloc-linux-1.c

15

Yup, you're totally right, this was on me :) I'll get that fixed.

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

Just pushed rG4dc8472942ce60f29de9587b9451cc3d49df7abf. It it settles (no buildbots complain), you could rebase and the lazy initialization could be a thing of the past! :)

[balazske]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

This makes it possible to have a generic one-time initialization function in the checker (CheckerBase)? The functionality is needed in more than one checker, at least for the bug types it can be used in almost every checker (that has bugtypes).

[Szelethus]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

I'm not sure I understand what you mean -- do you want to add CheckerManager to CheckerBase's constructor?

In any case, I remember reading something around CheckerBase's or BugType's implementation the way the checker receives its name is a bit tricky and not a part of the construction.

[balazske]

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

1696

Initialization in register function does not work: The MacroInfo is not found in the preprocessor. Probably the code is not parsed normally at that time. For now only the lazy initialization is working.

[balazske]

Checking for the macro value only if no memory region was found.

[balazske]

Applied the code reformattings.

[Szelethus]

LGTM! Mind that I just published D76917, you can, if you prefer, rebase on top of that. Also, a test case for deleteing a ZERO_SIZE_PTR valued pointer might be nice :)

If you prefer, feel free to commit without another round of reviews.

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

396

What @martong is saying is indeed nice, but the comments explain whats happening as well -- I'll leave it up to you how you want to commit this.

1696

Initialization in register function does not work: The MacroInfo is not found in the preprocessor. Probably the code is not parsed normally at that time. For now only the lazy initialization is working.

Well that is super annoying. I don't object to the lazy initialization then.

1708–1710

Just a bit of word smithing :)

If the macro ZERO_SIZE_PTR is defined, this could be a kernel source code. In that case, the ZERO_SIZE_PTR defines indicates a special value used for a zero-sized memory block which is allowed to be freed, despite not being a null pointer.

[balazske]

clang/test/Analysis/kmalloc-linux-1.c

15

Is it better to add these tests to kmalloc-linux.c?

[Szelethus]

clang/test/Analysis/kmalloc-linux-1.c

15

I think so, yea.

[balazske]

• Removed test file malloc-linux-1.c
• Prevent warning only if "malloc family" free is done (Do not recognize ZERO_SIZE_PTR at a delete call.)

[Szelethus]

LGTM, thanks!

clang/test/Analysis/kmalloc-linux-1.c

2

Oh, I almost forgot, the core package is supposed to be present :)

clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp

 #include "clang/Lex/Lexer.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/CommonBugCategories.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/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/ErrorHandling.h"
private:
   mutable std::unique_ptr<BugType> BT_FreeAlloca[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_MismatchedDealloc;
   mutable std::unique_ptr<BugType> BT_OffsetFree[CK_NumCheckKinds];
   mutable std::unique_ptr<BugType> BT_UseZerroAllocated[CK_NumCheckKinds];
 
   // TODO: Remove mutable by moving the initializtaion to the registry function.
   mutable Optional<uint64_t> KernelZeroFlagVal;
 
+  // This type stores obtained value of macro `ZERO_SIZE_PTR`, and if it could
+  // be obtained.
+  using KernelZeroSizePtrValueTy = Optional<int>;
+  /// Store the optional value of macro called `ZERO_SIZE_PTR`.
+  /// The value is initialized at first use.
+  mutable Optional<KernelZeroSizePtrValueTy> KernelZeroSizePtrValue;
+
   /// Process C++ operator new()'s allocation, which is the part of C++
   /// new-expression that goes before the constructor.
   void processNewAllocation(const CXXNewExpr *NE, CheckerContext &C,
                             SVal Target, AllocationFamily Family) const;
 
   /// Perform a zero-allocation check.
   ///
   /// \param [in] E The expression that allocates memory.
void ReportFunctionPointerFree(CheckerContext &C, SVal ArgVal,
                                  AllocationFamily Family) const;
 
   /// Find the location of the allocation for Sym on the path leading to the
   /// exploded node N.
   static LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym,
                                     CheckerContext &C);
 
   void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const;
+
+  void initKernelZeroSizePtrValue(Preprocessor &PP) const {
+    // If not initialized yet,
+    if (!KernelZeroSizePtrValue)
+      // try to get the value.
+      KernelZeroSizePtrValue = tryExpandAsInteger("ZERO_SIZE_PTR", PP);
+  }
 };
 
 //===----------------------------------------------------------------------===//
 // Definition of MallocBugVisitor.
 //===----------------------------------------------------------------------===//
 
 /// The bug visitor which allows us to print extra diagnostics along the
 /// BugReport path. For example, showing the allocation site of the leaked
ProgramStateRef MallocChecker::FreeMemAux(
   if (nullState && !notNullState)
     return nullptr;
 
   // Unknown values could easily be okay
   // Undefined values are handled elsewhere
   if (ArgVal.isUnknownOrUndef())
     return nullptr;
 
+  // If there is a macro called ZERO_SIZE_PTR, it could be a kernel source code
+  // and this value indicates a special value used for a zero-sized memory
+  // block. It is a constant value that is allowed to be freed.
+  const llvm::APSInt *ArgValKnown =
+      C.getSValBuilder().getKnownValue(State, ArgVal);
+  if (ArgValKnown) {
+    initKernelZeroSizePtrValue(C.getPreprocessor());
+    if (*KernelZeroSizePtrValue &&
+        ArgValKnown->getSExtValue() == **KernelZeroSizePtrValue)
+      return nullptr;
+  }
+
   const MemRegion *R = ArgVal.getAsRegion();
 
   // Nonlocs can't be freed, of course.
   // Non-region locations (labels and fixed addresses) also shouldn't be freed.
   if (!R) {
     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr, Family);
     return nullptr;
   }
 
   R = R->StripCasts();
 
   // Blocks might show up as heap data, but should not be free()d
   if (isa<BlockDataRegion>(R)) {
     ReportBadFree(C, ArgVal, ArgExpr->getSourceRange(), ParentExpr, Family);
     return nullptr;
   }
 

clang/lib/StaticAnalyzer/Core/CheckerHelpers.cpp

llvm::Optional<int> tryExpandAsInteger(StringRef Macro,
 
   // Filter out parens.
   std::vector<Token> FilteredTokens;
   FilteredTokens.reserve(MI->tokens().size());
   for (auto &T : MI->tokens())
     if (!T.isOneOf(tok::l_paren, tok::r_paren))
       FilteredTokens.push_back(T);
 
-  if (FilteredTokens.size() > 2)
-    return llvm::None;
-
   // Parse an integer at the end of the macro definition.
   const Token &T = FilteredTokens.back();
   if (!T.isLiteral())
     return llvm::None;
   StringRef ValueStr = StringRef(T.getLiteralData(), T.getLength());
   llvm::APInt IntValue;
   constexpr unsigned AutoSenseRadix = 0;
   if (ValueStr.getAsInteger(AutoSenseRadix, IntValue))
     return llvm::None;
 
   // Parse an optional minus sign.
-  if (FilteredTokens.size() == 2) {
-    if (FilteredTokens.front().is(tok::minus))
+  size_t Size = FilteredTokens.size();
+  if (Size >= 2) {
+    if (FilteredTokens[Size - 2].is(tok::minus))
       IntValue = -IntValue;
-    else
-      return llvm::None;
   }
 
   return IntValue.getSExtValue();
 }
 
 } // namespace ento
 } // namespace clang

clang/test/Analysis/kmalloc-linux-1.c

+// RUN: %clang_analyze_cc1 -triple x86_64-unknown-linux -analyzer-checker=unix.Malloc -verify %s
+
+#define ZERO_SIZE_PTR ((void *)16)
+
+void *__kmalloc(int size, int flags);
+
+// Linux kmalloc looks like this.
+// (simplified)
+void *kmalloc(int size, int flags) {
+  if (size == 0)
+    return ZERO_SIZE_PTR;
+  return __kmalloc(size, flags);
+}
+
+// FIXME: malloc checker expects kfree with 2 arguments, is this correct?
+// (recent kernel source code contains a `kfree(const void *)`)
+void kfree(void *, int);
+
+void test_kmalloc_zero_sized_block_fixed_value_address() {
+  void *ptr = kmalloc(0, 0); // kmalloc returns a constant address
+  kfree(ptr, 0);             // no warning about freeing a constant value
+}
+
+void test_kfree_constant_value() {
+  void *ptr = (void *)1;
+  kfree(ptr, 0); // expected-warning{{Argument to kfree() is a constant address (1)}}
+}