Page MenuHomePhabricator

[analyzer] Add SpinLockChecker for the Magenta kernel
Needs ReviewPublic

Authored by khazem on Nov 6 2016, 6:32 PM.

Details

Summary

This patch adds a new Static Analyzer checker for the correct use of spin locks in the Magenta kernel. The checker checks that a lock is not locked twice in a row, nor unlocked twice in a row.

The checker was authored by Farid Molazem Tabrizi.

Diff Detail

Event Timeline

khazem updated this revision to Diff 77000.Nov 6 2016, 6:32 PM
khazem retitled this revision from to [analyzer] Add SpinLockChecker for the Magenta kernel.
khazem updated this object.
khazem added subscribers: phosek, seanklein.
khazem updated this revision to Diff 77005.Nov 6 2016, 8:11 PM

Minor edit, the list of libraries in CMakeLists.txt is now in alphabetical order.

NoQ added a subscriber: NoQ.Nov 7 2016, 9:17 AM
dcoughlin edited edge metadata.Nov 7 2016, 10:03 AM

Thanks for upstreaming this! (And it was great to meet you at the developer conference.)

lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
62

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.)

119

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.

183

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'.

193

It would be good to emit a path note for the first lock, too.

khazem added a comment.Nov 8 2016, 3:19 PM

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.

khazem updated this revision to Diff 77275.Nov 8 2016, 3:21 PM
khazem edited edge metadata.

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.

khazem updated this revision to Diff 77277.Nov 8 2016, 3:23 PM

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.

khazem marked 4 inline comments as done.Nov 9 2016, 12:30 PM

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

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.

include/clang/StaticAnalyzer/Checkers/Checkers.td
728

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"?

lib/StaticAnalyzer/Checkers/SpinLockChecker.cpp
208

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).

224

Nit: Same here.

test/Analysis/spinlock_correct.c
1

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?

1

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 ...

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.