Skip to content

Commit 0cdc5dd

Browse files
author
Mandeep Singh Grang
committedMay 24, 2019
[Analyzer] Checker for non-determinism caused by iteration of unordered container of pointers
Summary: Added a checker for non-determinism caused by iterating unordered containers like std::unordered_set containing pointer elements. Reviewers: NoQ, george.karpenkov, whisperity, Szelethus, baloghadamsoftware Reviewed By: Szelethus Subscribers: mgorny, xazax.hun, baloghadamsoftware, szepet, rnkovacs, a.sidorin, mikhail.ramalho, donat.nagy, dkrupp, jdoerfert, Charusso, cfe-commits Tags: #clang Differential Revision: https://reviews.llvm.org/D59279 llvm-svn: 361664
·
llvmorg-21-initllvmorg-9.0.0-rc1
1 parent 3e8b9d4 commit 0cdc5dd

File tree

7 files changed

+228
-2
lines changed

7 files changed

+228
-2
lines changed
 

‎clang/docs/analyzer/checkers.rst

+16-2
Original file line numberDiff line numberDiff line change
@@ -211,8 +211,8 @@ Check for uninitialized values being returned to the caller.
211211
.. _cplusplus-checkers:
212212
213213
214-
cpluslus
215-
^^^^^^^^
214+
cplusplus
215+
^^^^^^^^^
216216
217217
C++ Checkers.
218218
@@ -1951,6 +1951,20 @@ Check for out-of-bounds access in string functions; applies to:`` strncopy, strn
19511951
int y = strlen((char *)&test); // warn
19521952
}
19531953
1954+
alpha.nondeterminism.PointerIteration (C++)
1955+
"""""""""""""""""""""""""""""""""""""""""""
1956+
Check for non-determinism caused by iterating unordered containers of pointers.
1957+
1958+
.. code-block:: c
1959+
1960+
void test() {
1961+
int a = 1, b = 2;
1962+
std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
1963+
1964+
for (auto i : UnorderedPtrSet) // warn
1965+
f(i);
1966+
}
1967+
19541968
alpha.nondeterminism.PointerSorting (C++)
19551969
"""""""""""""""""""""""""""""""""""""""""
19561970
Check for non-determinism caused by sorting of pointers.

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

+4
Original file line numberDiff line numberDiff line change
@@ -1340,6 +1340,10 @@ def UnixAPIPortabilityChecker : Checker<"UnixAPI">,
13401340

13411341
let ParentPackage = NonDeterminismAlpha in {
13421342

1343+
def PointerIterationChecker : Checker<"PointerIteration">,
1344+
HelpText<"Checks for non-determinism caused by iteration of unordered containers of pointers">,
1345+
Documentation<HasDocumentation>;
1346+
13431347
def PointerSortingChecker : Checker<"PointerSorting">,
13441348
HelpText<"Check for non-determinism caused by sorting of pointers">,
13451349
Documentation<HasDocumentation>;

‎clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,7 @@ add_clang_library(clangStaticAnalyzerCheckers
7575
OSObjectCStyleCast.cpp
7676
PaddingChecker.cpp
7777
PointerArithChecker.cpp
78+
PointerIterationChecker.cpp
7879
PointerSortingChecker.cpp
7980
PointerSubChecker.cpp
8081
PthreadLockChecker.cpp

‎clang/lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp

+100
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
//== PointerIterationChecker.cpp ------------------------------- -*- C++ -*--=//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
//
9+
// This file defines PointerIterationChecker which checks for non-determinism
10+
// caused due to iteration of unordered containers of pointer elements.
11+
//
12+
//===----------------------------------------------------------------------===//
13+
14+
#include "clang/ASTMatchers/ASTMatchFinder.h"
15+
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16+
#include "clang/StaticAnalyzer/Core/Checker.h"
17+
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
18+
19+
using namespace clang;
20+
using namespace ento;
21+
using namespace ast_matchers;
22+
23+
namespace {
24+
25+
// ID of a node at which the diagnostic would be emitted.
26+
constexpr llvm::StringLiteral WarnAtNode = "iter";
27+
28+
class PointerIterationChecker : public Checker<check::ASTCodeBody> {
29+
public:
30+
void checkASTCodeBody(const Decl *D,
31+
AnalysisManager &AM,
32+
BugReporter &BR) const;
33+
};
34+
35+
static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
36+
BugReporter &BR, AnalysisManager &AM,
37+
const PointerIterationChecker *Checker) {
38+
auto *ADC = AM.getAnalysisDeclContext(D);
39+
40+
const auto *MarkedStmt = Match.getNodeAs<Stmt>(WarnAtNode);
41+
assert(MarkedStmt);
42+
43+
auto Range = MarkedStmt->getSourceRange();
44+
auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
45+
BR.getSourceManager(),
46+
ADC);
47+
std::string Diagnostics;
48+
llvm::raw_string_ostream OS(Diagnostics);
49+
OS << "Iteration of pointer-like elements "
50+
<< "can result in non-deterministic ordering";
51+
52+
BR.EmitBasicReport(ADC->getDecl(), Checker,
53+
"Iteration of pointer-like elements", "Non-determinism",
54+
OS.str(), Location, Range);
55+
}
56+
57+
// Assumption: Iteration of ordered containers of pointers is deterministic.
58+
59+
// TODO: Currently, we only check for std::unordered_set. Other unordered
60+
// containers like std::unordered_map also need to be handled.
61+
62+
// TODO: Currently, we do not check what the for loop does with the iterated
63+
// pointer values. Not all iterations may cause non-determinism. For example,
64+
// counting or summing up the elements should not be non-deterministic.
65+
66+
auto matchUnorderedIterWithPointers() -> decltype(decl()) {
67+
68+
auto UnorderedContainerM = declRefExpr(to(varDecl(hasType(
69+
recordDecl(hasName("std::unordered_set")
70+
)))));
71+
72+
auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType())));
73+
74+
auto PointerIterM = stmt(cxxForRangeStmt(
75+
hasLoopVariable(PointerTypeM),
76+
hasRangeInit(UnorderedContainerM)
77+
)).bind(WarnAtNode);
78+
79+
return decl(forEachDescendant(PointerIterM));
80+
}
81+
82+
void PointerIterationChecker::checkASTCodeBody(const Decl *D,
83+
AnalysisManager &AM,
84+
BugReporter &BR) const {
85+
auto MatcherM = matchUnorderedIterWithPointers();
86+
87+
auto Matches = match(MatcherM, *D, AM.getASTContext());
88+
for (const auto &Match : Matches)
89+
emitDiagnostics(Match, D, BR, AM, this);
90+
}
91+
92+
} // end of anonymous namespace
93+
94+
void ento::registerPointerIterationChecker(CheckerManager &Mgr) {
95+
Mgr.registerChecker<PointerIterationChecker>();
96+
}
97+
98+
bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) {
99+
return LO.CPlusPlus;
100+
}

‎clang/test/Analysis/Inputs/system-header-simulator-cxx.h

+61
Original file line numberDiff line numberDiff line change
@@ -846,3 +846,64 @@ namespace std {
846846
template<class BidirIt, class UnaryPredicate>
847847
BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);
848848
}
849+
850+
namespace std {
851+
852+
template< class T = void >
853+
struct less;
854+
855+
template< class T >
856+
struct allocator;
857+
858+
template< class Key >
859+
struct hash;
860+
861+
template<
862+
class Key,
863+
class Compare = std::less<Key>,
864+
class Alloc = std::allocator<Key>
865+
> class set {
866+
public:
867+
set(initializer_list<Key> __list) {}
868+
869+
class iterator {
870+
public:
871+
iterator(Key *key): ptr(key) {}
872+
iterator operator++() { ++ptr; return *this; }
873+
bool operator!=(const iterator &other) const { return ptr != other.ptr; }
874+
const Key &operator*() const { return *ptr; }
875+
private:
876+
Key *ptr;
877+
};
878+
879+
public:
880+
Key *val;
881+
iterator begin() const { return iterator(val); }
882+
iterator end() const { return iterator(val + 1); }
883+
};
884+
885+
template<
886+
class Key,
887+
class Hash = std::hash<Key>,
888+
class Compare = std::less<Key>,
889+
class Alloc = std::allocator<Key>
890+
> class unordered_set {
891+
public:
892+
unordered_set(initializer_list<Key> __list) {}
893+
894+
class iterator {
895+
public:
896+
iterator(Key *key): ptr(key) {}
897+
iterator operator++() { ++ptr; return *this; }
898+
bool operator!=(const iterator &other) const { return ptr != other.ptr; }
899+
const Key &operator*() const { return *ptr; }
900+
private:
901+
Key *ptr;
902+
};
903+
904+
public:
905+
Key *val;
906+
iterator begin() const { return iterator(val); }
907+
iterator end() const { return iterator(val + 1); }
908+
};
909+
}

‎clang/test/Analysis/ptr-iter.cpp

+28
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
// RUN: %clang_analyze_cc1 %s -analyzer-output=text -verify \
2+
// RUN: -analyzer-checker=core,alpha.nondeterminism.PointerIteration
3+
4+
#include "Inputs/system-header-simulator-cxx.h"
5+
6+
template<class T>
7+
void f(T x);
8+
9+
void PointerIteration() {
10+
int a = 1, b = 2;
11+
std::set<int> OrderedIntSet = {a, b};
12+
std::set<int *> OrderedPtrSet = {&a, &b};
13+
std::unordered_set<int> UnorderedIntSet = {a, b};
14+
std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
15+
16+
for (auto i : OrderedIntSet) // no-warning
17+
f(i);
18+
19+
for (auto i : OrderedPtrSet) // no-warning
20+
f(i);
21+
22+
for (auto i : UnorderedIntSet) // no-warning
23+
f(i);
24+
25+
for (auto i : UnorderedPtrSet) // expected-warning {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration]
26+
// expected-note@-1 {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration]
27+
f(i);
28+
}

‎clang/www/analyzer/alpha_checks.html

+18
Original file line numberDiff line numberDiff line change
@@ -1067,6 +1067,24 @@ <h3 id="nondeterminism_alpha_checkers">Non-determinism Alpha Checkers</h3>
10671067
<colgroup><col class="namedescr"><col class="example"></colgroup>
10681068
<thead><tr><td>Name, Description</td><td>Example</td></tr></thead>
10691069

1070+
<tbody>
1071+
<tr><td><a id="alpha.nondeterminism.PointerIteration"><div class="namedescr expandable"><span class="name">
1072+
alpha.nondeterminism.PointerIteration</span><span class="lang">
1073+
(C++)</span><div class="descr">
1074+
Check for non-determinism caused by iterating unordered containers of pointers.</div></div></a></td>
1075+
<td><div class="exampleContainer expandable">
1076+
<div class="example"><pre>
1077+
// C++
1078+
void test() {
1079+
int a = 1, b = 2;
1080+
std::unordered_set<int *> UnorderedPtrSet = {&a, &b};
1081+
1082+
for (auto i : UnorderedPtrSet) // warn
1083+
f(i);
1084+
}
1085+
</pre></div></div></td></tr>
1086+
</tbody></table>
1087+
10701088
<tbody>
10711089
<tr><td><a id="alpha.nondeterminism.PointerSorting"><div class="namedescr expandable"><span class="name">
10721090
alpha.nondeterminism.PointerSorting</span><span class="lang">

0 commit comments

Comments
 (0)
Please sign in to comment.