[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
dcoughlin added a comment. In https://reviews.llvm.org/D26340#590882, @khazem wrote: > Devin, based on Artem's review of the other checker that I have posted [1] I > am wondering about merging both this SpinLockChecker and the MutexChecker > into PthreadLockChecker. Do you think it is still worth landing this > SpinLockChecker, or do you suppose that abandoning this patch and working on > merging all the checkers would be a good idea? I've noted how the checkers > might be merged in my reply to Artem: [2]. Merging seems reasonable to me. It is also a good way to make it less likely that the Magenta checkers accidentally regress since the main logic of the checker will be exercised when checking a much more common API. https://reviews.llvm.org/D26340 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
dcoughlin added a comment.
Thanks for adding the path notes and adopting CallDescription. I've added some
additional comments inline, which are mostly minor nits.
Two additional important changes -- and I should have noted these in the
initial review -- is that it would be good to remove a MemRegion mapping from
the program state when a MemRegion escapes and also when it becomes dead. These
should both be small changes.
**Escaping**
Removing the mapping when the lock escapes will avoid false positives when the
lock is passed to a function that the analyzer doesn't inline (for example, if
it is in another translation unit) that unlocks it:
void foo(lock_t *l) {
spin_lock(l);
...
do_stuff_and_unlock(l);
..
spin_lock();
}
If `do_stuff_and_unlock()` is in another translation unit the analyzer won't
see the unlock and so will report a false positive if you don't remove the
mapping when the lock escapes.
If you remove the mapping when the lock escapes, the analyzer will
optimistically assume the best-case scenario the next time it sees a lock or
unlock operation. There is an example of how to do this in
`ObjCContainersChecker::checkPointerEscape()`
**Removing Dead Symbols**
It is also important for performance to remove mappings that are no longer
relevant. There is a cost to keep around mappings in the program state: both
memory (because the analyzer keeps some states around for use in the bug
reporter visitor) and time (because the analyzer has to iterate over the map
when determining whether two states are the same). There is an example of how
to do this in `ObjCLoopChecker::checkDeadSymbols`.
Comment at: include/clang/StaticAnalyzer/Checkers/Checkers.td:728
+//===--===//
+// Magenta checkers.
+//===--===//
Nit: I think it would good to add a little bit more context to disambiguate so
that future maintainers will be able to do a web search to learn about what
these checkers are for. For example, maybe something like "Checkers for the
Magenta kernel"?
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:208
+ *DoubleUnlockBugType,
+ "Execution path found where spinlock is unlocked twice in a row", Node);
+ Report->markInteresting(SpinLockLocation);
Nit: it is enough to have the message be "Spinlock is unlocked twice in a row".
I don't think it is necessary to explicitly mention the execution path
(especially now that you have a path note for the first unlock).
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:224
+ *DoubleLockBugType,
+ "Execution path found where spinlock is locked twice in a row", Node);
+ Report->addRange(Call.getSourceRange());
Nit: Same here.
Comment at: test/Analysis/spinlock_correct.c:1
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
Nit: Typically in the analyzer codebase we try to keep the number of test files
to a minimum. Can these three test files all be combined into one?
Comment at: test/Analysis/spinlock_correct.c:1
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
dcoughlin wrote:
> Nit: Typically in the analyzer codebase we try to keep the number of test
> files to a minimum. Can these three test files all be combined into one?
Another nit: The analyzer relies on always having core checkers enabled because
they model important aspects of the language. You should change this to `...
-analyzer-checker=core,magenta.SpinLock ...`
https://reviews.llvm.org/D26340
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
khazem marked 4 inline comments as done. khazem added a comment. Devin, based on Artem's review of the other checker that I have posted [1] I am wondering about merging both this SpinLockChecker and the MutexChecker into PthreadLockChecker. Do you think it is still worth landing this SpinLockChecker, or do you suppose that abandoning this patch and working on merging all the checkers would be a good idea? I've noted how the checkers might be merged in my reply to Artem: [2]. [1] https://reviews.llvm.org/D26342 [2] https://reviews.llvm.org/D26342#590881 https://reviews.llvm.org/D26340 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
khazem updated this revision to Diff 77277.
khazem added a comment.
If a double-lock or double-release is detected, path notes are now emitted on
the _first_ lock or release event. Also updated the tests to check for these
notes.
https://reviews.llvm.org/D26340
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
test/Analysis/spinlock_correct.c
test/Analysis/spinlock_double_lock.c
test/Analysis/spinlock_double_release.c
Index: test/Analysis/spinlock_double_release.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_release.c
@@ -0,0 +1,38 @@
+// RUN: %clang_cc1 -analyze -analyzer-output=text -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+typedef struct S {
+ int a;
+ lock_t l;
+} S_t;
+
+static S_t st;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+void bar1(lock_t *y) {
+ spin_unlock(y); // expected-note {{First unlocked here}}
+}
+
+void bar2(lock_t *x) {
+ spin_unlock(x); // expected-warning{{Execution path found where spinlock is unlocked twice in a row}}
+ // expected-note@-1 0+ {{Execution path found where spinlock is unlocked twice in a row}}
+}
+
+int foo() {
+ int a = bar();
+ if (a > 0) { // expected-note {{Assuming 'a' is > 0}} \
+// expected-note {{Taking true branch}}
+spin_lock();
+bar1(); // expected-note {{Calling 'bar1'}} \
+expected-note {{Returning from 'bar1'}}
+ }
+
+ lock_t *c =
+ bar2(c); // expected-note {{Calling 'bar2'}}
+ return 0;
+}
+
Index: test/Analysis/spinlock_double_lock.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_lock.c
@@ -0,0 +1,26 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -analyzer-output=text -verify %s
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) // expected-note{{Assuming 'a' is > 0}} \
+expected-note{{Taking true branch}}
+
+spin_lock(); // expected-note{{First locked here}}
+ if (a > 10) // expected-note{{Assuming 'a' is > 10}} \
+ expected-note{{Taking true branch}}
+
+spin_lock(); // expected-warning{{Execution path found where spinlock is locked twice in a row}}
+// expected-note@-1 0+ {{Execution path found where spinlock is locked twice in a row}}
+
+
+ return 0;
+}
+
Index: test/Analysis/spinlock_correct.c
===
--- /dev/null
+++ test/Analysis/spinlock_correct.c
@@ -0,0 +1,30 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+spin_lock();
+ }
+
+ if (a < -10) {
+spin_lock();
+ }
+
+ if (a > 0)
+spin_unlock();
+
+ if (a < -10)
+spin_unlock();
+
+ return 0;
+}
+
Index: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
===
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
@@ -0,0 +1,262 @@
+//== SpinLockChecker.cpp - SpinLock checker -*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This defines SpinLockChecker, a check for the Magenta kernel. It
+// checks that there are no execution paths where spinlocks are locked
+// twice in a row, or unlocked twice in a row.
+//
+//===--===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+struct LockInfo {
+
+ enum Kind { Locked, Released } K;
+
+ LockInfo(Kind kind) : K(kind) {}
+
+ bool operator==(const LockInfo ) const { return K == LI.K; }
+
+ void Profile(llvm::FoldingSetNodeID ) const { ID.AddInteger(K); }
+
+ bool isLocked() const { return K == Locked; }
+
+ bool isReleased() const { return K == Released; }
+
+ static LockInfo getLocked() { return LockInfo(Locked); }
+
+ static LockInfo getReleased() { return LockInfo(Released); }
+
+};
+
+// When we detect a double-lock or double-release, we
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
khazem updated this revision to Diff 77275.
khazem added a comment.
The strings for Spin{Unl,L}ockFuncName and LockErrorCategory are now
initialized when constructing a SpinLockChecker object rather than being static
globals, in order to avoid adverse effects on startup time.
Also, the Spin*FuncName variables are now of type CallDescription. This is to
enable pointer rather than string comparisons of the function name.
https://reviews.llvm.org/D26340
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
test/Analysis/spinlock_correct.c
test/Analysis/spinlock_double_lock.c
test/Analysis/spinlock_double_release.c
Index: test/Analysis/spinlock_double_release.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_release.c
@@ -0,0 +1,35 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+typedef struct S {
+ int a;
+ lock_t l;
+} S_t;
+
+static S_t st;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+void bar1(lock_t *y) {
+ spin_unlock(y);
+}
+
+void bar2(lock_t *x) {
+ spin_unlock(x); // expected-warning{{Execution path found where spinlock is unlocked twice in a row}}
+}
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+spin_lock();
+bar1();
+ }
+
+ lock_t *c =
+ bar2(c);
+ return 0;
+}
+
Index: test/Analysis/spinlock_double_lock.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_lock.c
@@ -0,0 +1,20 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0)
+spin_lock();
+ if (a > 10)
+spin_lock(); // expected-warning{{Execution path found where spinlock is locked twice in a row}}
+
+ return 0;
+}
+
Index: test/Analysis/spinlock_correct.c
===
--- /dev/null
+++ test/Analysis/spinlock_correct.c
@@ -0,0 +1,30 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+spin_lock();
+ }
+
+ if (a < -10) {
+spin_lock();
+ }
+
+ if (a > 0)
+spin_unlock();
+
+ if (a < -10)
+spin_unlock();
+
+ return 0;
+}
+
Index: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
===
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
@@ -0,0 +1,187 @@
+//== SpinLockChecker.cpp - SpinLock checker -*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This defines SpinLockChecker, a check for the Magenta kernel. It
+// checks that there are no execution paths where spinlocks are locked
+// twice in a row, or unlocked twice in a row.
+//
+//===--===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+struct LockInfo {
+
+ enum Kind { Locked, Released } K;
+
+ LockInfo(Kind kind) : K(kind) {}
+
+ bool operator==(const LockInfo ) const { return K == LI.K; }
+
+ void Profile(llvm::FoldingSetNodeID ) const { ID.AddInteger(K); }
+
+ bool isLocked() const { return K == Locked; }
+
+ bool isReleased() const { return K == Released; }
+
+ static LockInfo getLocked() { return LockInfo(Locked); }
+
+ static LockInfo getReleased() { return LockInfo(Released); }
+
+};
+
+}
+
+/// We keep track of the locks in a map. SpinLockMap maps the
+/// memory region of a spinlock to its status (locked, released).
+/// The reason that we keep track of spinlocks as memory region is
+/// that the lock/unlock functions take lock arguments as pointers.
+REGISTER_MAP_WITH_PROGRAMSTATE(SpinLockMap, const MemRegion *, LockInfo)
+
+namespace {
+
+class SpinLockChecker : public Checker {
+
+ /// When facing a spin_unlock function call, check the record of the
+ /// corresponding lock in SpinLockMap and make sure that there are no
+ /// problems such as double unlocks.
+ void
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
khazem added a comment. Good to meet you too, thanks for the useful comments and pointers to helpful examples! I'm going to update the diff twice: the first one to address your first two comments, and the second one to address your last two. https://reviews.llvm.org/D26340 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
dcoughlin added a comment.
Thanks for upstreaming this! (And it was great to meet you at the developer
conference.)
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:61
+
+const ErrorCategoryStr LockInfo::LockErrCategory("Lock Error");
+const FunctionNameStr LockInfo::SpinLockFuncName("spin_lock");
In the LLVM/clang codebase we try very hard to avoid running constructors for
globals, as this can have adverse effects on startup time. Typically we try to
lazily initialize things like these or have them refer to constant data that
the linker will handle automatically (such as a c string constant).
Can these be a C string constant instead? Or can they be instance members of
the SpinLockChecker class? (See the note about `CallDescription` below, which
may be helpful.)
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:118
+
+ FunctionNameStr CalleeName = Call.getCalleeIdentifier()->getName();
+ if (CalleeName != LockInfo::getSpinLockFuncName() &&
In the analyzer codebase we try to use IdentifierInfo pointers to compare
identifiers. Since these are interned it lets us perform pointer comparisons
rather than expensive string comparisons.
There is a `CallDescription` class in `CallEvent.h` that encapsulates this
logic. You can see an example of how it is used in SimpleStreamChecker.cpp.
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:182
+ Report->markInteresting(SpinLockLocation);
+ C.emitReport(std::move(Report));
+}
For these kinds of diagnostics it is often very helpful to emit a path note
indicating where the first unlock was.
To do this, you can add a custom bug report visitor that will get called on
each node in the path to a diagnostic and emit a note, if appropriate. In this
case you would look for nodes with calls to unlock taking the same region as
the one you are now reporting for.
There is an example of how to implement a bug report visitor in
'SuperDeallocBRVisitor'.
Comment at: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp:192
+
+ auto Report = llvm::make_unique(
+ *DoubleLockBugType,
It would be good to emit a path note for the first lock, too.
https://reviews.llvm.org/D26340
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D26340: [analyzer] Add SpinLockChecker for the Magenta kernel
khazem updated this revision to Diff 77005.
khazem added a comment.
Minor edit, the list of libraries in CMakeLists.txt is now in alphabetical
order.
https://reviews.llvm.org/D26340
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
test/Analysis/spinlock_correct.c
test/Analysis/spinlock_double_lock.c
test/Analysis/spinlock_double_release.c
Index: test/Analysis/spinlock_double_release.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_release.c
@@ -0,0 +1,35 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+typedef struct S {
+ int a;
+ lock_t l;
+} S_t;
+
+static S_t st;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+void bar1(lock_t *y) {
+ spin_unlock(y);
+}
+
+void bar2(lock_t *x) {
+ spin_unlock(x); // expected-warning{{Execution path found where spinlock is unlocked twice in a row}}
+}
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+spin_lock();
+bar1();
+ }
+
+ lock_t *c =
+ bar2(c);
+ return 0;
+}
+
Index: test/Analysis/spinlock_double_lock.c
===
--- /dev/null
+++ test/Analysis/spinlock_double_lock.c
@@ -0,0 +1,20 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0)
+spin_lock();
+ if (a > 10)
+spin_lock(); // expected-warning{{Execution path found where spinlock is locked twice in a row}}
+
+ return 0;
+}
+
Index: test/Analysis/spinlock_correct.c
===
--- /dev/null
+++ test/Analysis/spinlock_correct.c
@@ -0,0 +1,30 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=magenta.SpinLock -verify %s
+// expected-no-diagnostics
+
+typedef unsigned int lock_t;
+
+static lock_t l;
+
+void spin_lock(lock_t *lock);
+void spin_unlock(lock_t *lock);
+int bar();
+
+int foo() {
+ int a = bar();
+ if (a > 0) {
+spin_lock();
+ }
+
+ if (a < -10) {
+spin_lock();
+ }
+
+ if (a > 0)
+spin_unlock();
+
+ if (a < -10)
+spin_unlock();
+
+ return 0;
+}
+
Index: lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
===
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
@@ -0,0 +1,198 @@
+//== SpinLockChecker.cpp - SpinLock checker -*- C++ -*--==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+//
+// This defines SpinLockChecker, a check for the Magenta kernel. It
+// checks that there are no execution paths where spinlocks are locked
+// twice in a row, or unlocked twice in a row.
+//
+//===--===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+typedef llvm::SmallString<16> ErrorCategoryStr;
+typedef llvm::SmallString<32> FunctionNameStr;
+
+struct LockInfo {
+
+ enum Kind { Locked, Released } K;
+
+ LockInfo(Kind kind) : K(kind) {}
+
+ bool operator==(const LockInfo ) const { return K == LI.K; }
+
+ void Profile(llvm::FoldingSetNodeID ) const { ID.AddInteger(K); }
+
+ bool isLocked() const { return K == Locked; }
+
+ bool isReleased() const { return K == Released; }
+
+ static LockInfo getLocked() { return LockInfo(Locked); }
+
+ static LockInfo getReleased() { return LockInfo(Released); }
+
+ static ErrorCategoryStr getLockErrorCategory() { return LockErrCategory; }
+
+ static FunctionNameStr getSpinLockFuncName() { return SpinLockFuncName; }
+
+ static FunctionNameStr getSpinUnlockFuncName() { return SpinUnlockFuncName; }
+
+private:
+ static const ErrorCategoryStr LockErrCategory;
+ static const FunctionNameStr SpinLockFuncName;
+ static const FunctionNameStr SpinUnlockFuncName;
+};
+
+const ErrorCategoryStr LockInfo::LockErrCategory("Lock Error");
+const FunctionNameStr LockInfo::SpinLockFuncName("spin_lock");
+const FunctionNameStr LockInfo::SpinUnlockFuncName("spin_unlock");
+}
+
+/// We keep track of the locks in a map. SpinLockMap maps the
+/// memory region of a spinlock to its status (locked, released).
+/// The reason that we keep track of
