[Analyzer] Checker for non-determinism caused by iteration of unordered container of pointers

[mgrang]

Summary

Added a checker for non-determinism caused by iterating unordered containers like std::unordered_set containing pointer elements.

[mgrang]

Following are the assumptions/limitations of this patch:

1. The assumption is that iteration of ordered containers of pointers is not non-deterministic.

2. Currently we only detect std::unordered_set. Detection of unordered_map can be added later.

3. Currently, we also do not check for what happens inside the for loop. Not all iterations may causes non-determinism. For example, counting or summing up the elements should not be non-deterministic.

[Szelethus]

Code is great, idea's great, so green light on my part, but maybe we should allow some folks who are more knowledgeable on AST matching to have a say in this.

The obvious question, why not implement this in clang-tidy? I have nothing against landing this in the static analyzer, just curious.

Please also add some doc to docs/analyzer/checkers.rst.

lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp

5–6 ↗

(On Diff #190363)

Uh-oh, we changed licence not long ago, and your last patch also landed with the incorrect header -- could you please fix them?

test/Analysis/ptr-iter.cpp

1 ↗

(On Diff #190363)

// RUN: %clang_analyze_cc1 %s -analyzer-output=text -verify \
// RUN:   -analyzer-checker=core,alpha.nondeterminism.PointerIteration

[Szelethus]

In D59279#1427017, @mgrang wrote:

3. Currently, we also do not check for what happens inside the for loop. Not all iterations may causes non-determinism. For example, counting or summing up the elements should not be non-deterministic.

Could you please add a TODO then to the code? We definitely wouldn't want to forget this before moving out of alpha.

[mgrang]

The obvious question, why not implement this in clang-tidy?

Going forward I would like to make these non-determinism checks more precise by reasoning about what happens inside the loop, for example. I am not sure if clang-tidy has support for such deeper reasoning. I thought clang-tidy is more of a pattern matcher?

[mgrang]

Also, what is the difference between these two: https://clang.llvm.org/docs/analyzer/checkers.html, https://clang-analyzer.llvm.org/available_checks.html. It seems they document similar stuff. Should we add the doc for each new checker in both of these?

[Szelethus]

Could you please add a commit that changes the top of the file on your previous commit? Feel free to do that without review (I can't commit it myself atm).

In D59279#1427803, @mgrang wrote:

Also, what is the difference between these two: https://clang.llvm.org/docs/analyzer/checkers.html, https://clang-analyzer.llvm.org/available_checks.html. It seems they document similar stuff. Should we add the doc for each new checker in both of these?

Umm, yea, we're in the middle of moving from the HTML format to the new sphinx format, so I think it's fine to ignore the latter, and only extend docs/analyzer/checkers.rst. Since the moving is a lot of manual labor, we haven't gotten around getting rid of it entirely just yet. But of course, it's welcome to have that maintained for the time being too!

In D59279#1427798, @mgrang wrote:

The obvious question, why not implement this in clang-tidy?

Going forward I would like to make these non-determinism checks more precise by reasoning about what happens inside the loop, for example. I am not sure if clang-tidy has support for such deeper reasoning. I thought clang-tidy is more of a pattern matcher?

Yup, I'm sold on that.

[mgrang]

Could you please add a commit that changes the top of the file on your previous commit? Feel free to do that without review (I can't commit it myself atm).

Done in https://reviews.llvm.org/rC356086.

[mgrang]

I was trying to write another checker for hashing of pointers. Basically, I wanted to match all instances where the keys of std::map are pointers. Writing an AST matcher for std::map is straightforward. However, I am not sure how to check for pointer keys after matching std::map.

The following matches std::map<K, V>. But I need to match std::map<int *, V>. So I was thinking something on the lines of templateArgument(hasType(pointerType())).

auto ContainersM = anyOf(
                     hasName("std::map"),
                     hasName("std::unordered_map")
                   );

auto HashContainerM = varDecl(hasType(cxxRecordDecl(ContainersM)))

[mgrang]

Ping for reviews please.

[rnkovacs]

In D59279#1427017, @mgrang wrote:

Following are the assumptions/limitations of this patch:

1. The assumption is that iteration of ordered containers of pointers is not non-deterministic.

Could you please explain which type of non-determinism we are addressing here? If our issue is that iteration order is not consistent across runs, then an unordered set of integers seems just as non-deterministic as an unordered set of pointers. On the other hand, if our issue is that pointer values vary between runs, then an ordered set of pointers seems just as non-deterministic as an unordered set of pointers. Are unordered sets of pointers distinguished because they lie in the intersection of these categories and thus avoid the most false positive cases? If so, for someone debugging non-deterministic behavior in their code, would it be useful to add a strict option that shows other cases too? If not, maybe we could document our reasons somewhere.

[mgrang]

In D59279#1438500, @rnkovacs wrote:

In D59279#1427017, @mgrang wrote:

Following are the assumptions/limitations of this patch:

1. The assumption is that iteration of ordered containers of pointers is not non-deterministic.

Could you please explain which type of non-determinism we are addressing here? If our issue is that iteration order is not consistent across runs, then an unordered set of integers seems just as non-deterministic as an unordered set of pointers. On the other hand, if our issue is that pointer values vary between runs, then an ordered set of pointers seems just as non-deterministic as an unordered set of pointers. Are unordered sets of pointers distinguished because they lie in the intersection of these categories and thus avoid the most false positive cases? If so, for someone debugging non-deterministic behavior in their code, would it be useful to add a strict option that shows other cases too? If not, maybe we could document our reasons somewhere.

Yes, the reason we limit the checks only to unordered containers is to reduce the false positive rate. Although, as you rightly pointed out that ordered sets of pointers are as non-deterministic as unordered ones. Once our checks have the capability to detect what happens inside the loop maybe we can add ordered sets too. I will add this to the TODO. Thanks.

[Szelethus]

In D59279#1438514, @mgrang wrote:

Although, as you rightly pointed out that ordered sets of pointers are as non-deterministic as unordered ones.

What if you store pointers to the elements of an array? In that case, it should be deterministic.

-----------
|1|2|3|5|6|
-----------
 ^     ^ 
 p     q

In the above example, pointer p's memory address will always be less then q's, so in an ordered set, iterating over them would be deterministic. When hashing algorithms come into the picture, than it wouldn't be :^)

[mgrang]

In D59279#1439014, @Szelethus wrote:

In D59279#1438514, @mgrang wrote:

Although, as you rightly pointed out that ordered sets of pointers are as non-deterministic as unordered ones.

What if you store pointers to the elements of an array? In that case, it should be deterministic.

-----------
|1|2|3|5|6|
-----------
 ^     ^ 
 p     q

In the above example, pointer p's memory address will always be less then q's, so in an ordered set, iterating over them would be deterministic. When hashing algorithms come into the picture, than it wouldn't be :^)

Yes, by containers here I mean hashing containers.

[Szelethus]

Other than that, LGTM, thanks! Please, again, let @NoQ have the final say.

[rnkovacs]

In D59279#1438514, @mgrang wrote:

Yes, the reason we limit the checks only to unordered containers is to reduce the false positive rate. Although, as you rightly pointed out that ordered sets of pointers are as non-deterministic as unordered ones. Once our checks have the capability to detect what happens inside the loop maybe we can add ordered sets too. I will add this to the TODO. Thanks.

Great, thanks!

[Szelethus]

I think you can commit this. Thanks!

cfe/trunk/docs/analyzer/checkers.rst

  int test() {
    int x;
    return x; // warn
  }
 
 .. _cplusplus-checkers:
 
 
-cpluslus
-^^^^^^^^
+cplusplus
+^^^^^^^^^
 
 C++ Checkers.
 
 cplusplus.InnerPointer
 """"""""""""""""""""""
 Check for inner pointers of C++ containers used after re/deallocation.
 
 cplusplus.NewDelete (C++)

 
 
 .. code-block:: c
 
  void test() {
    int y = strlen((char *)&test); // warn
  }
 
+alpha.nondeterminism.PointerIteration (C++)
+"""""""""""""""""""""""""""""""""""""""""""
+Check for non-determinism caused by iterating unordered containers of pointers.
+
+.. code-block:: c
+
+ void test() {
+  int a = 1, b = 2;
+  std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
+
+  for (auto i : UnorderedPtrSet) // warn
+    f(i);
+ }
+
 alpha.nondeterminism.PointerSorting (C++)
 """""""""""""""""""""""""""""""""""""""""
 Check for non-determinism caused by sorting of pointers.
 
 .. code-block:: c
 
  void test() {
   int a = 1, b = 2;

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

 } // end optin.portability
 
 //===----------------------------------------------------------------------===//
 // NonDeterminism checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = NonDeterminismAlpha in {
 
+def PointerIterationChecker : Checker<"PointerIteration">,
+  HelpText<"Checks for non-determinism caused by iteration of unordered containers of pointers">,
+  Documentation<HasDocumentation>;
+
 def PointerSortingChecker : Checker<"PointerSorting">,
   HelpText<"Check for non-determinism caused by sorting of pointers">,
   Documentation<HasDocumentation>;
 
 } // end alpha.nondeterminism

cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   ObjCMissingSuperCallChecker.cpp
   ObjCPropertyChecker.cpp
   ObjCSelfInitChecker.cpp
   ObjCSuperDeallocChecker.cpp
   ObjCUnusedIVarsChecker.cpp
   OSObjectCStyleCast.cpp
   PaddingChecker.cpp
   PointerArithChecker.cpp
+  PointerIterationChecker.cpp
   PointerSortingChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp
   RetainCountChecker/RetainCountChecker.cpp
   RetainCountChecker/RetainCountDiagnostics.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   RunLoopAutoreleaseLeakChecker.cpp

cfe/trunk/lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp

+//== PointerIterationChecker.cpp ------------------------------- -*- C++ -*--=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines PointerIterationChecker which checks for non-determinism
+// caused due to iteration of unordered containers of pointer elements.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+using namespace ast_matchers;
+
+namespace {
+
+// ID of a node at which the diagnostic would be emitted.
+constexpr llvm::StringLiteral WarnAtNode = "iter";
+
+class PointerIterationChecker : public Checker<check::ASTCodeBody> {
+public:
+  void checkASTCodeBody(const Decl *D,
+                        AnalysisManager &AM,
+                        BugReporter &BR) const;
+};
+
+static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
+                            BugReporter &BR, AnalysisManager &AM,
+                            const PointerIterationChecker *Checker) {
+  auto *ADC = AM.getAnalysisDeclContext(D);
+
+  const auto *MarkedStmt = Match.getNodeAs<Stmt>(WarnAtNode);
+  assert(MarkedStmt);
+
+  auto Range = MarkedStmt->getSourceRange();
+  auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
+                                                      BR.getSourceManager(),
+                                                      ADC);
+  std::string Diagnostics;
+  llvm::raw_string_ostream OS(Diagnostics);
+  OS << "Iteration of pointer-like elements "
+     << "can result in non-deterministic ordering";
+
+  BR.EmitBasicReport(ADC->getDecl(), Checker,
+                     "Iteration of pointer-like elements", "Non-determinism",
+                     OS.str(), Location, Range);
+}
+
+// Assumption: Iteration of ordered containers of pointers is deterministic.
+
+// TODO: Currently, we only check for std::unordered_set. Other unordered
+// containers like std::unordered_map also need to be handled.
+
+// TODO: Currently, we do not check what the for loop does with the iterated
+// pointer values. Not all iterations may cause non-determinism. For example,
+// counting or summing up the elements should not be non-deterministic.
+
+auto matchUnorderedIterWithPointers() -> decltype(decl()) {
+
+  auto UnorderedContainerM = declRefExpr(to(varDecl(hasType(
+                               recordDecl(hasName("std::unordered_set")
+                             )))));
+
+  auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType())));
+
+  auto PointerIterM = stmt(cxxForRangeStmt(
+                             hasLoopVariable(PointerTypeM),
+                             hasRangeInit(UnorderedContainerM)
+                      )).bind(WarnAtNode);
+
+  return decl(forEachDescendant(PointerIterM));
+}
+
+void PointerIterationChecker::checkASTCodeBody(const Decl *D,
+                                             AnalysisManager &AM,
+                                             BugReporter &BR) const {
+  auto MatcherM = matchUnorderedIterWithPointers();
+
+  auto Matches = match(MatcherM, *D, AM.getASTContext());
+  for (const auto &Match : Matches)
+    emitDiagnostics(Match, D, BR, AM, this);
+}
+
+} // end of anonymous namespace
+
+void ento::registerPointerIterationChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<PointerIterationChecker>();
+}
+
+bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) {
+  return LO.CPlusPlus;
+}

cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h

namespace std {
   void stable_sort(RandomIt first, RandomIt last);
 
   template<class BidirIt, class UnaryPredicate>
   BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p);
 
   template<class BidirIt, class UnaryPredicate>
   BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);
 }
+
+namespace std {
+
+template< class T = void >
+struct less;
+
+template< class T >
+struct allocator;
+
+template< class Key >
+struct hash;
+
+template<
+  class Key,
+  class Compare = std::less<Key>,
+  class Alloc = std::allocator<Key>
+> class set {
+  public:
+    set(initializer_list<Key> __list) {}
+
+    class iterator {
+    public:
+      iterator(Key *key): ptr(key) {}
+      iterator operator++() { ++ptr; return *this; }
+      bool operator!=(const iterator &other) const { return ptr != other.ptr; }
+      const Key &operator*() const { return *ptr; }
+    private:
+      Key *ptr;
+    };
+
+  public:
+    Key *val;
+    iterator begin() const { return iterator(val); }
+    iterator end() const { return iterator(val + 1); }
+};
+
+template<
+  class Key,
+  class Hash = std::hash<Key>,
+  class Compare = std::less<Key>,
+  class Alloc = std::allocator<Key>
+> class unordered_set {
+  public:
+    unordered_set(initializer_list<Key> __list) {}
+
+    class iterator {
+    public:
+      iterator(Key *key): ptr(key) {}
+      iterator operator++() { ++ptr; return *this; }
+      bool operator!=(const iterator &other) const { return ptr != other.ptr; }
+      const Key &operator*() const { return *ptr; }
+    private:
+      Key *ptr;
+    };
+
+  public:
+    Key *val;
+    iterator begin() const { return iterator(val); }
+    iterator end() const { return iterator(val + 1); }
+};
+}

cfe/trunk/test/Analysis/ptr-iter.cpp

+// RUN: %clang_analyze_cc1 %s -analyzer-output=text -verify \
+// RUN: -analyzer-checker=core,alpha.nondeterminism.PointerIteration
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+template<class T>
+void f(T x);
+
+void PointerIteration() {
+  int a = 1, b = 2;
+  std::set<int> OrderedIntSet = {a, b};
+  std::set<int *> OrderedPtrSet = {&a, &b};
+  std::unordered_set<int> UnorderedIntSet = {a, b};
+  std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
+
+  for (auto i : OrderedIntSet) // no-warning
+    f(i);
+
+  for (auto i : OrderedPtrSet) // no-warning
+    f(i);
+
+  for (auto i : UnorderedIntSet) // no-warning
+    f(i);
+
+  for (auto i : UnorderedPtrSet) // expected-warning {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration]
+// expected-note@-1 {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration]
+    f(i);
+}

cfe/trunk/www/analyzer/alpha_checks.html

 
 <!-- =========================== nondeterminism alpha =========================== -->
 <h3 id="nondeterminism_alpha_checkers">Non-determinism Alpha Checkers</h3>
 <table class="checkers">
 <colgroup><col class="namedescr"><col class="example"></colgroup>
 <thead><tr><td>Name, Description</td><td>Example</td></tr></thead>
 
 <tbody>
+<tr><td><a id="alpha.nondeterminism.PointerIteration"><div class="namedescr expandable"><span class="name">
+alpha.nondeterminism.PointerIteration</span><span class="lang">
+(C++)</span><div class="descr">
+Check for non-determinism caused by iterating unordered containers of pointers.</div></div></a></td>
+<td><div class="exampleContainer expandable">
+<div class="example"><pre>
+// C++
+void test() {
+ int a = 1, b = 2;
+ std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
+
+ for (auto i : UnorderedPtrSet) // warn
+   f(i);
+}
+</pre></div></div></td></tr>
+</tbody></table>
+
+<tbody>
 <tr><td><a id="alpha.nondeterminism.PointerSorting"><div class="namedescr expandable"><span class="name">
 alpha.nondeterminism.PointerSorting</span><span class="lang">
 (C++)</span><div class="descr">
 Check for non-determinism caused by sorting of pointers.</div></div></a></td>
 <td><div class="exampleContainer expandable">
 <div class="example"><pre>
 // C++
 void test() {