RE: Thread Safety Analysis and the Linux kernel

From: Marco Elver <[email protected]>
> Hi Aaron ^ 2,
> 
> [+Cc a bunch of folks that were involved in discussions.]
> 
> After sending v2 of the -Wthread-safety / Capability Analysis patches
> for the Linux kernel [1], a number of concrete improvements to
> -Wthread-safety will be required sooner or later. It is unclear if
> they are blockers to the Linux kernel's adoption because the feature
> is currently designed as "opt-in per subsystem", but it's clear the
> current state of things is not ideal.
> 
> [1] https://lore.kernel.org/all/[email protected]/

First of all, in addition to the documentation at https://clang.llvm.org/docs/ThreadSafetyAnalysis.html that you're already aware of, I can also recommend the paper by some of the original authors at https://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/42958.pdf.

> Peter Zijlstra's feedback:
> https://lore.kernel.org/all/[email protected]/
> -- much of which led to the below requests. Peter also managed to
> crash Clang, but that's probably unrelated to -Wthread-safety
> directly: https://github.com/llvm/llvm-project/issues/129873

Technically a parser issue and not in the analysis itself. But to my knowledge expressions in attributes were originally introduced for the analysis, so in some sense it is related.

> More straightforward requests:
> 
> 1. Re-entrant acquires: rcu_read_lock(), preempt_disable(), etc. are
> all re-entrant locks. My proposal is to introduce an attribute that
> can be added to "ACQUIRE(..)" annotated functions to indicate they are
> re-entrant. Release-count needs to then match acquire-count to fully
> release a capability.

We initially thought that this might be a problem for us as well, because we also use re-entrant locks. However, until now, it hasn't been an issue and I'm almost convinced that it never will be.

In essence, the analysis derives the set of statically known-to-be-held capabilities at every point in the program text. What does this mean? If you run the program, and stop it at any (time) point, you get the actual set of capabilities held at this point. However, a function might be called from different places, and depending on the caller, different capabilities might be held at the same point in the program text. The set that we compute does not and cannot contain all those capabilities, but only those that are held regardless of where execution comes from. So we generally don't know about capabilities held by callers, unless there is an annotation on the function, which is then checked at the call site.

Re-entrant locks are thus not necessarily an impediment: if one function acquires a lock and calls another function that also acquires it, the analysis won't complain. It analyzes functions in isolation. You'll only get a warning if you acquire a lock twice in one function without releasing it in between, or if the function is annotated as requiring the lock and acquires it again. However, in both cases the second acquisition can always be dropped. You can argue that this isn't a deadlock and hence not a bug, but the acquisition is unnecessary because the lock is already known to be held.

In theory I could construct cases where there are still problems: maybe we're locking twice because we're calling another function that unlocks once, but we still want the lock to be held afterwards. However, I've never seen this. In our code, re-entrant locks are only used because the caller might already hold the lock for some reason. The sophisticated patterns that I could think of never appeared. If this is different in the kernel, I'd be curious how it looks like.

> 2. Basic alias analysis, e.g. when storing a pointer to a lock in a
> function-local variable. [Complaint in:
> https://lore.kernel.org/all/[email protected]/
> -- quote: "Fix the analyzer instead."]

We already do this analysis for C++ references, and we might extend it to pointers, but with one restriction: an important aspect of references that we're relying on is that they're essentially immutable pointers, i.e. "T&" semantically behaves like "T* const". This makes references behave like SSA values, meaning we can just symbolically substitute the initializer. If we can ask the user to mimic references by making the local variable "const", we can apply the same logic. (I know that using "const" is a bit tricky in C, e.g. "T**" doesn't implicitly convert to "const T* const*" as it does in C++. However, I would hope that you can always add top-level "const".)

With "non-const" pointers we're unfortunately opening a can of worms:

struct S { int a, b; };

void f(struct S *s)
{
	int *val = &s->a;

	while (...) {
		do_something(val);
		val = &s->b;
	};
}

The analysis walks the control-flow graph (CFG), and it wants to walk it only once. (We handle back edges by checking that the set of capabilities matches the set that we previously computed.) Here we have val == &s->a when we encounter the call to do_something. But then we see a new assignment and a back edge, so our assumption was wrong!

I don't think we want to make multiple rounds over the CFG. We're not trying to do symbolic execution. There are performance implications, reliability implications, and depending on how far we want to go, we might even run into the halting problem.

So if we can restrict this to "T* const", I don't see an issue with it, and it should arise naturally from the existing alias analysis for references.

Perhaps we can emit notes on -Wthread-safety-precise that suggest using "const" pointers or references in case we suspect alias analysis has fallen short.

> 3. Ability to refer to locks in returned reference/pointer. For example:
>     struct foo *ret_lock_struct(void) ACQUIRE(return->somelock);
>     struct foo *try_ret_lock_struct(void) TRY_ACQUIRE(1,
> return->somelock); // locked if non-NULL
> I expect this also requires basic alias analysis to work so that
> assigning the returned pointer to a function-local variable and then
> later use in an unlock function works as expected.

We had a discussion about this, maybe I can find it later. The idea was to introduce a builtin for the return value. A rough outline:
* Introduce the builtin to the parser, say __builtin_return_value(). This shouldn't be hard.
* Add handling to Sema: we can only accept the builtin in attributes on functions. The return type is the return type of the function.
* In the caller we might not need alias analysis: there are no variables that alias. We already produce S-expressions for some return values from functions, and then handle a DeclStmt with initializer. (I introduced that for some C++ patterns in https://reviews.llvm.org/D129755.)
* In the function itself we need to substitute the return expression for the builtin before checking the exit set. (I assume this restricts the possible attributes to acquire-type attributes.)

We can also discuss this in more detail if you want to pick it up. It might be quite a bit of work, but it should fit nicely into the existing framework.

> More complex requests:
> 
> 4. The ability to deal with conditional locking with return values
> that are not just true/non-zero and false/zero. A concrete case here
> is that a lot of functions return error codes, and if the error code
> is < 0, no lock is taken. If the error code is >= 0, the lock is
> taken. [ Source:
> https://lore.kernel.org/all/[email protected]/
> ]

Not an issue in principle, but it could get ugly. The current notation doesn't seem to leave room for something like that. How do we extend it? I don't have a good idea here. I guess it would also be nice to have more than one example to base this on.

> 5. Better control-flow handling. Basic understanding of conditional
> locking, which is explicitly ruled out in:
> https://clang.llvm.org/docs/ThreadSafetyAnalysis.html#conditional-locks
> - however, if there's some way to even get basic support, would vastly
> improve things for the kernel.

The paper goes into some detail why this is tricky with the current design. We don't want to explore execution paths, because that obviously results in a combinatorial explosion. The Clang static analyzer deals with that by limiting exploration, but that makes it fuzzy and of course slow. As a warning flag we're part of the compiler itself, and the recommended practice is -Werror=thread-safety, so both of these are highly problematic. We want the analysis to be predictable and fast.

It would be interesting to see some patterns. One "trick" that I have played with is to move the conditional locking into the capability itself: it is then unconditionally acquired or released, but the underlying mutex is only acquired or released based on some global state or member. Something like this:

struct __attribute__((capability("mutex"))) conditional_mutex
{
	struct mutex mu;
	bool active;
}

void acquire_conditional_mutex(struct conditional_mutex* cmu)
	__attribute__((acquire_capability(cmu)))
{
	if (cmu->active)
		acquire_mutex(&cmu->mu);
}

However, I realize that might be a difficult proposal for the kernel community.

> Some of these are more complex than others, and any hints how we might
> go about this are appreciated. I'm happy to try and implement some of
> them, but if you find that you already know exactly how you'd like an
> implementation to look like, rough drafts that we can take over and
> polish would be very very helpful, too!
> 
> In general, the Linux kernel has some of the most complex
> synchronization patterns with numerous synchronization primitives.
> Getting this to work for a good chunk of the more complex
> synchronization code in the kernel will be quite the achievement if we
> get there. :-)

Examples are always welcome!

Aaron