Page MenuHomePhabricator

[Sema] Thread Safety Analysis: Make negative capability typeless.
Needs RevisionPublic

Authored by ziangwan on Jul 23 2019, 7:41 PM.

Details

Summary

Re-purpose this revision to make negative capability typeless for clang's thread safety analysis. This is a larger effort so it will take a little bit more time on me.

Diff Detail

Repository
rL LLVM

Event Timeline

ziangwan created this revision.Jul 23 2019, 7:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 23 2019, 7:42 PM
lebedev.ri edited subscribers, added: cfe-commits; removed: llvm-commits.Jul 24 2019, 12:11 AM
ziangwan retitled this revision from [Sema] Fix negative capability's LockKind representation. to [Sema] Thread Safety Analysis: Fix negative capability's LockKind representation..Jul 24 2019, 2:21 PM
clang/lib/Analysis/ThreadSafety.cpp
2219–2221

The double check of LDat1->kind() == LK_Generic is fishy to me. Particularly the case where LDat1->kind() == LK_Generic is false but LDat2->kind() == LK_Generic is true.

This might be clearer as:

if (LDat2->kind() == LK_Generic)
  continue;
else if (LDat1->kind() == LK_Generic && Modify)
  *Iter1 = Fact;
else {
  ...

Or is there something else to this logic I'm missing?

clang/test/SemaCXX/thread-safety-annotations.h
47

Is this test suite run with other compilers? If not, I think we can remove the case?

aaronpuchert added a subscriber: aaronpuchert.

What distinguishes a shared from an exclusive negative capability? Negative capabilities (as I understand them) express the mutex not being held at all, meaning neither in shared nor in exclusive mode.

clang/lib/Analysis/ThreadSafety.cpp
2188–2190

What do these lines mean? That we accept if a lock is shared in one branch and exclusive in the other, and that we make it exclusive after the merge point?

clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

Why would I want these warnings here? This code seems fine to me.

However, I don't see why we don't get acquiring mutex 'mu' requires negative capability '!mu' at line 138, or does that disappear because of the assertion?

ziangwan marked 4 inline comments as done.Jul 26 2019, 10:54 AM
ziangwan added inline comments.
clang/lib/Analysis/ThreadSafety.cpp
2188–2190

Yes. If at CFG merge point, one path holds type1 lock and the other path holds type2 lock.

We do a type1 + type2 = merged_type and issue warnings if we are doing shared + exclusive merge.

2219–2221

I think your suggestion is to refactor the if statements. What I am thinking is that there are two cases.

  1. One of the two locks is generic
    • If so, then take the type of the other non-generic lock (shared or exclusive).
  2. Neither of the two locks is generic.

My if statement is trying express that. I am afraid the refactoring is going to lose the logic (as stated in my comment above).

clang/test/SemaCXX/thread-safety-annotations.h
47

Yeah, you are right. I just copied the header definitions from clang thread safety analysis doc.

clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

Showing acquiring mutex 'mu' requires negative capability '!mu' is not in the scope of this patch. Please notice thread safety analysis is still under development.

The reason is that, in one path we have ASSERT_SHARED_CAPABILITY(!mu), and in the other path we have RELEASE(mu). The assertion leads to negative shared capability but the release leads to negative exclusive capability. A merge of the two capabilities (merging "I am not trying to read" versus "I am not trying to write") leads to a warning.

Without my patch, clang will issue a warning for the merge point in test1() but not the merge point in test2().

aaronpuchert added inline comments.Jul 28 2019, 4:14 AM
clang/test/SemaCXX/thread-safety-annotations.h
47

Why aren't you using the existing macros? The idea was to run the tests with both old and new terminology, and for the time being, I think we should maintain both.

clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

But ASSERT_SHARED_CAPABILITY(!mu) implies that we also don't have an exclusive lock (an exclusive lock is stronger than a shared lock), and RELEASE(mu) without ACQUIRE_SHARED(mu) implies that we have neither a shared nor an exclusive lock as well.

In the end, I have the same question as above: Why do we want two kinds of negative capabilities? Isn't the idea that negative capabilities express the lock not being held at all?

This comment was removed by ziangwan.
ziangwan marked an inline comment as done.Jul 30 2019, 11:25 AM
ziangwan added inline comments.
clang/test/SemaCXX/thread-safety-annotations.h
47

There are already tests on existing macros. I want to introduce tests about the new macros as well.

ziangwan marked an inline comment as done.Jul 30 2019, 11:26 AM
ziangwan added inline comments.
clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

The problem is: by the current state of the thread safety analysis, ASSERT_SHARED_CAPABILTIY(!mu) introduces a shared negative capability, whereas RELEASE(mu) and RELEASE_SHARED(mu) introduce an exclusive negative capability, and UNLOCK_FUNCTION(mu) introduces a generic negative capability. All three are different. At merge points, warnings will be issued if different types of negative capability are merged. The current thread safety analysis produces bogus false positive in our code base.

The solution I propose is that we should at least make RELEASE_SHARED(mu) produce a shared negative capability.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read. In other words, "exclusive !mu" does not imply "shared !mu", and the code can still hold the lock in shared state. Without the types of negative capability, we wouldn't be able to express the situation described above.

aaronpuchert added inline comments.Jul 30 2019, 1:35 PM
clang/test/SemaCXX/thread-safety-annotations.h
47

There are no old and new macros, there are only old and new attributes. The existing macros use both sets of attributes, depending on the value of USE_CAPABILITY with which the tests are run. Using other macro names is just window dressing.

clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

I'm not doubting that there is a bug, but I don't think this is the right solution.

ASSERT_SHARED_CAPABILTIY(!mu) introduces a shared negative capability

We should disallow using "shared" attributes with negative capabilities, and I'm surprised this isn't already the case.

whereas RELEASE(mu) and RELEASE_SHARED(mu) introduce an exclusive negative capability [...] The solution I propose is that we should at least make RELEASE_SHARED(mu) produce a shared negative capability.

Clearly both leave mu in the same (unlocked) state, so why distinguish between them? After the lock is released, whichever mode it has been in before is ancient history. We want to track the current state of the lock.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read.

Negative capabilites aren't about what you are not doing with protected resources, in fact nothing is checked about that. Their purpose is to answer this question: can I draw this lock, or might it already been held? If you are holding a negative capability, that means you can acquire the lock. And when you can acquire the lock, you can do so in either mode. If the lock is currently held in any mode (and hence you're not holding a negative capability), then you can't acquire it in any mode, you have to release it first.

So there is no use in having two kinds of negative capabilities. An "exclusive !mu" should be either "!mu" or "shared(mu)", depending on what the functions expects. The attributes encode state transitions, as I mentioned in D49355#1191544, and there is simply no way to go from "either having no lock or a shared lock" to anywhere else, because all attributes assume a certain previous state.

ziangwan marked 2 inline comments as done.Jul 30 2019, 2:13 PM
ziangwan added inline comments.
clang/test/SemaCXX/thread-safety-annotations.h
47

Gotcha.

clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

IIUC, if the only type of negative capability we are introducing is exclusive negative capability, ASSERT_SHARED_CAPABILITY(!mu) should introduce an exclusive negative capability as well, right?

The current state of the thread safety analysis is:

  1. UNLOCK_FUNCTION(!mu) and RELEASE_GENERIC_CAPABILITY(!mu) -> generic negative capability
  2. ASSERT_SHARED_CAPABILITY(!mu) -> shared negative capability.
  3. All others -> exclusive negative capability.

A fix would be to let all three produce exclusive negative capability, which essentially means there is no type associated with negative capability. This fix could also fix my bug.

The reason why I am still calling it "exclusive" is that there is a flag IsShared() associated with capability objects no matter whether it is positive or negative.

The primary purpose of Thread Safety Analysis is to make sure that accesses to shared resources are protected. That's why we only track whether a lock is available by default (i.e. without -Wthread-safety-negative), locks that we don't know anything about are assumed to be unlocked. As a side effect, we can detect double unlocks and lock/unlock-kind mismatches.

But we cannot detect double locks (and deadlocks) over function boundaries. This is why negative capabilities were introduced. But because not everybody cares about that enough to warrant more annotations, it's not on by default.

Regarding why we should have types for negative capability, thinking about "exclusive !mu" in a reader-writer lock situation, which means "I am not trying to write". However, the code can still read.

Negative capabilities don't declare that we're not reading/writing: we can't do that without holding the actual (positive) capability anyway!

Having the capability !mu just means that we can assume mu is not locked. We will then usually acquire the mu (otherwise the annotation wouldn't be needed).

aaronpuchert added inline comments.Jul 30 2019, 2:35 PM
clang/test/SemaCXX/warn-thread-safety-negative.cpp
135–140

Yes, that sounds right. In the long-term I would want negative capabilities to be neither exclusive nor shared, but for now I would take them to be exclusive, to be consistent with the kinds of attributes we use them with.

In my opinion we should also warn about ASSERT_SHARED_CAPABILITY(!mu) in -Wthread-safety-attributes.

ziangwan retitled this revision from [Sema] Thread Safety Analysis: Fix negative capability's LockKind representation. to [Sema] Thread Safety Analysis: Make negative capability typeless..Jul 31 2019, 6:46 PM
ziangwan edited the summary of this revision. (Show Details)

This is a larger effort so it will take a little bit more time on me.

This is fine, but could you add a "Plan changes" action then? This will make the revision disappear from the active review queue.

aaronpuchert requested changes to this revision.Mon, Jan 13, 11:31 AM

A fix would be to let all three produce exclusive negative capability, which essentially means there is no type associated with negative capability. This fix could also fix my bug.

As discussed, this is how it should be solved. I'm changing the state so that it's clear there is nothing to review here currently.

This revision now requires changes to proceed.Mon, Jan 13, 11:31 AM