Thread Safety Analysis and the Linux kernel

Thread Safety Analysis and the Linux kernel

[Marco Elver]

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/20250304092417.2873893-1-elver@google.com/

Peter Zijlstra's feedback:
https://lore.kernel.org/all/20250305112041.GA16878@noisy.programming.kicks-ass.net/
-- 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

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.

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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
-- quote: "Fix the analyzer instead."]

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.

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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
]

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.

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

Thanks,
-- Marco

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

From: Marco Elver <elver@google.com>
> 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/20250304092417.2873893-1-elver@google.com/

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/20250305112041.GA16878@noisy.programming.kicks-ass.net/
> -- 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> -- 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> ]

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

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:

> > 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> > -- 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.

So one of the most important use cases from my perspective is the
interaction with __attribute__((cleanup())), which we use to build
scope based guards in C.

And most of that might be fine with using 'T * const', but the support
for conditional locks explicitly needs to set the pointer NULL when the
acquire fails.

We have a macro used like:

DEFINE_GUARD(mutex, struct mutex *, mutex_lock(_T), mutex_unlock(_T))

Which expands to:

static inline void class_mutex_destructor(struct mutex **p)
{
	struct mutex *_T = *p;
	if (_T) { mutex_unlock(_T); }
}

static inline struct mutex * class_mutex_constructor(struct mutex *_T)
{
	struct mutex * t = ({ mutex_lock(_T); _T; });
	return t;
}

This is then typically used like:

	scoped_guard (mutex, &my_lock) {
		...
	}

Which in turn expands to:

	for (struct mutex *scope __attribute__((cleanup(class_mutex_destructor))) =
	     class_mutex_constructor(&my_lock); scope; ({ goto _label; }))
		if (0) {
_label:
			break;
		} else {

		...
	}

And here I can probably make the guard() thing add const like:

		struct mutex * const __UNIQUE_ID_guard_123 
			__attribute__((cleanup(class_mutex_destructor) =
				class_mutex_constructor(&my_lock);

But note that _constructor() is still laundering this through a
non-const version, and while the above could have:

	struct mutex * t const = ...

That no longer works for the case of:

DEFINE_GUARD_COND(mutex, _try, mutex_trylock(_T))

which expands to have a constructor like:

static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
{
	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t = NULL; _t; });
	return t;
}

Notably that NULL assignment on lock failure is not happy with having
that const on.

Note that this combination of trylock and scoped_guard() results in not
taking the for-loop on failure. Eg:

	scoped_guard (mutex_trylock, &my_lock) {
		print("ponies\n");
	}

Will in fact only print 'ponies' when it got the lock.


And yes, all of this is fairly creative use of C, but hey, we get to
have scope based guards, which get rid of a lot of errors in error
paths.


So assuming we can annotate things like so:

static inline void class_mutex_destructor(struct mutex * const *p)
	__releases(*p) __no_capability_analysis
{
	struct mutex *_T = *p;
	if (_T) { mutex_unlock(_T); }
}

static inline struct mutex * class_mutex_constructor(struct mutex *_T)
	__acquires(_T) __no_capability_analysis
{
	struct mutex * t = ({ mutex_lock(_T); _T; });
	return t;
}

static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
	__const_acquires(nonnull, _T) __no_capability_analysis
{
	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t = NULL; _t; });
	return t;
}

the: struct mutex * const in the for() construct might just be enough.


Would this be sufficient consty for it to untangle this web?

Re: Thread Safety Analysis and the Linux kernel

[Bart Van Assche]

On 3/6/25 1:47 AM, Peter Zijlstra wrote:
> That no longer works for the case of:
> 
> DEFINE_GUARD_COND(mutex, _try, mutex_trylock(_T))
> 
> which expands to have a constructor like:
> 
> static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
> {
> 	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t = NULL; _t; });
> 	return t;
> }

Hi Peter,

Would it be acceptable to introduce variants of the conditional locking
functions that return the mutex pointer instead of a boolean to indicate
whether or not locking succeeded? Would that be sufficient to change the
type of 't' above from 'struct mutex *' into 'struct mutex *const'? Two
examples of what such functions could look like:

struct mutex *mutex_trylock_ptr(struct mutex *mutex)
	__cond_acquires(nonnull, mutex)
{
	return mutex_trylock(mutex) ? mutex : NULL;
}

struct mutex *mutex_lock_interruptible_ptr(struct mutex *mutex, int *res)
	__cond_acquires(nonnull, mutex)
{
	int ret = mutex_lock_interruptible(mutex);

	if (res)
		*res = ret;

	return ret == 0 ? mutex : NULL;
}

Thanks,

Bart.

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Thu, Mar 06, 2025 at 08:18:37AM -0800, Bart Van Assche wrote:
> On 3/6/25 1:47 AM, Peter Zijlstra wrote:
> > That no longer works for the case of:
> > 
> > DEFINE_GUARD_COND(mutex, _try, mutex_trylock(_T))
> > 
> > which expands to have a constructor like:
> > 
> > static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
> > {
> > 	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t = NULL; _t; });
> > 	return t;
> > }
> 
> Hi Peter,
> 
> Would it be acceptable to introduce variants of the conditional locking
> functions that return the mutex pointer instead of a boolean to indicate
> whether or not locking succeeded? 

So I don't think we need to do that. All that is important is that the
thing can track the return value of the constructor to the argument of
the destructor. What actually happens inside those functions is
immaterial.

(I got myself slightly confused when writing that earlier email).

Anyway, for DEFINE_GUARD_COND() we can do:

        EXTEND_CLASS(_name, _ext, \
-                    ({ void *_t = _T; if (_T && !(_condlock)) _t = NULL; _t; }), \
+                    ({ void *_t = (_condlock) ? _T : NULL; _t; }), \
                     class_##_name##_t _T) \

But it becomes a little more tricky for DEFINE_LOCK_GUARD_1_COND().

Still, like I argued above, I don't think it matters.

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Bart Van Assche <bvanassche@acm.org>
> Would it be acceptable to introduce variants of the conditional locking
> functions that return the mutex pointer instead of a boolean to indicate
> whether or not locking succeeded? Would that be sufficient to change the
> type of 't' above from 'struct mutex *' into 'struct mutex *const'? Two
> examples of what such functions could look like:
> 
> struct mutex *mutex_trylock_ptr(struct mutex *mutex)
> 	__cond_acquires(nonnull, mutex)
> {
> 	return mutex_trylock(mutex) ? mutex : NULL;
> }
> 
> struct mutex *mutex_lock_interruptible_ptr(struct mutex *mutex, int *res)
> 	__cond_acquires(nonnull, mutex)
> {
> 	int ret = mutex_lock_interruptible(mutex);
> 
> 	if (res)
> 		*res = ret;
> 
> 	return ret == 0 ? mutex : NULL;
> }

Assuming that __cond_acquires is your macro for __attribute__((try_acquire_capability)), this shouldn't be an issue. We don't look into try-acquire annotated function bodies, and we can't because they're probably doing conditional locking internally, which we don't support. (Yet somehow we support try-acquire... but we do so by delaying acquisition to a branch on the return value.)

But even if we did, adding no_thread_safety_analysis to some internal functions should not be an issue. The value of the warning comes from analyzing large parts of the code base. If you exclude some locking internals you're not losing much.

Just in case this isn't clear: the attribute doesn't affect callers, and we don't do inlining. It simply turns off the analysis for this one function body.

Aaron

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Peter Zijlstra <peterz@infradead.org>
> So one of the most important use cases from my perspective is the
> interaction with __attribute__((cleanup())), which we use to build
> scope based guards in C.
> 
> And most of that might be fine with using 'T * const', but the support
> for conditional locks explicitly needs to set the pointer NULL when the
> acquire fails.
> 
> We have a macro used like:
> 
> DEFINE_GUARD(mutex, struct mutex *, mutex_lock(_T), mutex_unlock(_T))
> 
> Which expands to:
> 
> static inline void class_mutex_destructor(struct mutex **p)
> {
> 	struct mutex *_T = *p;
> 	if (_T) { mutex_unlock(_T); }
> }
> 
> static inline struct mutex * class_mutex_constructor(struct mutex *_T)
> {
> 	struct mutex * t = ({ mutex_lock(_T); _T; });
> 	return t;
> }
> 
> This is then typically used like:
> 
> 	scoped_guard (mutex, &my_lock) {
> 		...
> 	}
> 
> Which in turn expands to:
> 
> 	for (struct mutex *scope
> __attribute__((cleanup(class_mutex_destructor))) =
> 	     class_mutex_constructor(&my_lock); scope; ({ goto _label; }))
> 		if (0) {
> _label:
> 			break;
> 		} else {
> 
> 		...
> 	}
> 
> And here I can probably make the guard() thing add const like:
> 
> 		struct mutex * const __UNIQUE_ID_guard_123
> 			__attribute__((cleanup(class_mutex_destructor) =
> 				class_mutex_constructor(&my_lock);

Yes, and the scope variable is hidden to the macro user, so it cannot be accessed anyway. So in that case we should also be fine.

> But note that _constructor() is still laundering this through a
> non-const version,

That's not an issue. Remember that we analyze function bodies in isolation. In the worst case we just put a "no_thread_safety_analysis" attribute on the constructor.

One problem though is that the constructor symbolically locks my_lock, while the destructor symbolically unlocks __UNIQUE_ID_guard_123. We need to be able to figure out that they're the same thing. I see three possibilities, without having tried any of them:

1. Annotate the constructor with __attribute__((return_capability(_T))).
2. Create an alias before we call the constructor, so that constructor and destructor get the same argument. But this wouldn't work for try_acquire: the alias couldn't be const.
3. We model the cleanup-annotated variable like a C++ scoped lock.

We model C++ scoped locks as objects that "manage" a fixed set of capabilities. In the example above, __UNIQUE_ID_guard_123 would be a scoped lock that manages my_lock. We have an attribute to indicate scope types. We could use that here by wrapping the pointer in an annotated struct:

struct __attribute__((scoped_capability)) mutex_scope {
	struct mutex * /*const? */ t;
};

Or we say that every variable is a scoped lock, if it has type "pointer to a capability-annotated type" and a cleanup attribute. But it could be an issue if being a scoped lock is no longer a type property. Or that we'll scoop up too much this way. We'll have to see.

> and while the above could have:
>
> 	struct mutex * t const = ...
> 
> That no longer works for the case of:
> 
> DEFINE_GUARD_COND(mutex, _try, mutex_trylock(_T))
> 
> which expands to have a constructor like:
> 
> static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
> {
> 	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t =
> NULL; _t; });
> 	return t;
> }
> 
> Notably that NULL assignment on lock failure is not happy with having
> that const on.

Same as above: what's important is the "const" where it's being used. If we have to put "no_thread_safety_analysis" on this one function, we don't lose much. You'll likely not even need that, because we don't attempt to analyze functions annotated with try-acquire attributes (try_acquire_capability and try_acquire_shared_capability). (Basically, we bail out on mutex implementation internals, which we recognize based on certain attributes.)

However, with try-acquire the wrapping might be counterproductive. We want the return value to be ("contextually" in C++) convertible to bool. Pointers are convertible to bool, but structs are not. So it seems like we need to "guess" scoped locks. Or we put an annotation on the constructor.

> Note that this combination of trylock and scoped_guard() results in not
> taking the for-loop on failure. Eg:
> 
> 	scoped_guard (mutex_trylock, &my_lock) {
> 		print("ponies\n");
> 	}
> 
> Will in fact only print 'ponies' when it got the lock.

This should in principle be supported. Once you branch on the return value of a try-acquire-annotated function, we introduce the capability in the correct branch. Because the destructor is unconditionally executed though, we likely need to model this as scoped capability, otherwise we get complaints that we release a lock that we don't hold. Although we could also add special treatment for cleanup function calls.

> static inline void class_mutex_destructor(struct mutex * const *p)
> 	__releases(*p) __no_capability_analysis
> {
> 	struct mutex *_T = *p;
> 	if (_T) { mutex_unlock(_T); }
> }
> 
> static inline struct mutex * class_mutex_constructor(struct mutex *_T)
> 	__acquires(_T) __no_capability_analysis
> {
> 	struct mutex * t = ({ mutex_lock(_T); _T; });
> 	return t;
> }
> 
> static inline struct mutex * class_mutex_try_constructor(struct mutex *_T)
> 	__const_acquires(nonnull, _T) __no_capability_analysis
> {
> 	struct mutex * t = ({ void *_t = _T; if (_T && !(mutex_trylock(_T))) _t =
> NULL; _t; });
> 	return t;
> }

That looks reasonable, assuming that __const_acquires is your macro for try_acquire_capability.

> the: struct mutex * const in the for() construct might just be enough.
> 
> 
> Would this be sufficient consty for it to untangle this web?

I think so. The cleanup function is going to be called on &__UNIQUE_ID_guard_123, and the annotation says we release *&__UNIQUE_ID_guard_123 = __UNIQUE_ID_guard_123. Then we check the type: is it a reference or const pointer? It is, so we look up the initializer in a map. We substitute that and get class_mutex_constructor(&my_lock). There are two ways of looking through the call: __attribute__((return_capability(...))) or the scoped locks idea. We don't look into the constructor, so it can do whatever it wants.

Aaron

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:

> > Peter Zijlstra's feedback:
> > https://lore.kernel.org/all/20250305112041.GA16878@noisy.programming.kicks-ass.net/
> > -- 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.

Right, so that construct came about trying to work around not being able
to reference the return value.

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

Yes, as far as I can follow, that should work nicely.

The thing I tried to work around yesterday, making clang ICE, was
something like this function:

struct rq *__task_rq_lock(struct task_struct *p)
	__must_hold(p->pi_lock)
	__acquires(_Return->__lock)
{
	struct rq *rq;

	lockdep_assert_held(&p->pi_lock);

	for (;;) {
		rq = task_rq(p);
		raw_spin_rq_lock(rq);
		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
			return rq;

		raw_spin_rq_unlock(rq);

		while (unlikely(task_on_rq_migrating(p)))
			cpu_relax();
	}
}

Except for not having that _Return / __builtin_return_value() thing, I
tried __acquires(task_rq(p)->__lock), and task_rq() expands into a pile
of gunk that made it go *boom*.

Users would typically look like:

try_to_wake_up(p, state)
{
	struct rq *rq;

	scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
		if (!ttwu_state_match(p, state))
			break;

		rq = __task_rq_lock(p);
		// go enqueue task
		raw_spin_rq_unlock(rq);
	}
}

Anyway, the whole 'find-and-lock' pattern is widely used.

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Peter Zijlstra <peterz@infradead.org>
> On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:
> > > 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.
> 
> Yes, as far as I can follow, that should work nicely.
> 
> The thing I tried to work around yesterday, making clang ICE, was
> something like this function:
> 
> struct rq *__task_rq_lock(struct task_struct *p)
>         __must_hold(p->pi_lock)
>         __acquires(_Return->__lock)
> {
>         struct rq *rq;
> 
>         lockdep_assert_held(&p->pi_lock);
> 
>         for (;;) {
>                 rq = task_rq(p);
>                 raw_spin_rq_lock(rq);
>                 if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
>                         return rq;
> 
>                 raw_spin_rq_unlock(rq);
> 
>                 while (unlikely(task_on_rq_migrating(p)))
>                         cpu_relax();
>         }
> }

This should fit well. We take the return expression "rq", plug it in for _Return in the attribute expression and get "rq->__lock". Then we compare this against the actual lockset, which should contain the same expression from the call "raw_spin_rq_lock(rq)".

> Users would typically look like:
> 
> try_to_wake_up(p, state)
> {
>         struct rq *rq;
> 
>         scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
>                 if (!ttwu_state_match(p, state))
>                         break;
> 
>                 rq = __task_rq_lock(p);
>                 // go enqueue task
>                 raw_spin_rq_unlock(rq);
>         }
> }

Can the return value be used as an initializer by moving the declaration into the scoped_guard block? Or do you have a style guide that wants all declarations at the beginning of a block?

We track capabilities as symbolic expressions, so something like "rq->__lock" in this case. If there is an assignment to "rq", that changes the meaning of the symbolic expression. The object referred to by the expression is then no longer reachable. Currently we don't look at assignments at all when it comes to tracking capabilities. We don't even warn, it's simply documented as not being supported. We only look at initializers, as in alias analysis. Having a separate variable being initialized with the return value gives us a unique name for the return value, which is good when we're working with symbolic expressions.

If there are cases where assignment is really needed, we can also check to which extent we can rewrite expressions or warn when the objects they point to become unreachable. (In the example that would be the case if someone assigned to "rq" again after the call to "__task_rq_lock ".)

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Thu, Mar 06, 2025 at 10:18:32PM +0000, Puchert, Aaron wrote:

> > Users would typically look like:
> > 
> > try_to_wake_up(p, state)
> > {
> >         struct rq *rq;
> > 
> >         scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
> >                 if (!ttwu_state_match(p, state))
> >                         break;
> > 
> >                 rq = __task_rq_lock(p);
> >                 // go enqueue task
> >                 raw_spin_rq_unlock(rq);
> >         }
> > }
> 
> Can the return value be used as an initializer by moving the
> declaration into the scoped_guard block? Or do you have a style guide
> that wants all declarations at the beginning of a block?

Yeah, we have a style guide that strongly suggests variables are
declared at the start. In fact, we used to have
-Wdeclaration-after-statement and only (finally) got rid of it in order
to allow for these scope guards.

> We track capabilities as symbolic expressions, so something like
> "rq->__lock" in this case. If there is an assignment to "rq", that
> changes the meaning of the symbolic expression. The object referred to
> by the expression is then no longer reachable. Currently we don't look
> at assignments at all when it comes to tracking capabilities. We don't
> even warn, it's simply documented as not being supported. We only look
> at initializers, as in alias analysis. Having a separate variable
> being initialized with the return value gives us a unique name for the
> return value, which is good when we're working with symbolic
> expressions.
> 
> If there are cases where assignment is really needed, we can also
> check to which extent we can rewrite expressions or warn when the
> objects they point to become unreachable. (In the example that would
> be the case if someone assigned to "rq" again after the call to
> "__task_rq_lock ".)

Right. I suspect we might need this if we want to minimize code churn.

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Fri, Mar 07, 2025 at 08:59:50AM +0100, Peter Zijlstra wrote:
> On Thu, Mar 06, 2025 at 10:18:32PM +0000, Puchert, Aaron wrote:
> 
> > > Users would typically look like:
> > > 
> > > try_to_wake_up(p, state)
> > > {
> > >         struct rq *rq;
> > > 
> > >         scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
> > >                 if (!ttwu_state_match(p, state))
> > >                         break;
> > > 
> > >                 rq = __task_rq_lock(p);
> > >                 // go enqueue task
> > >                 raw_spin_rq_unlock(rq);
> > >         }
> > > }
> > 
> > Can the return value be used as an initializer by moving the
> > declaration into the scoped_guard block? Or do you have a style guide
> > that wants all declarations at the beginning of a block?
> 
> Yeah, we have a style guide that strongly suggests variables are
> declared at the start. In fact, we used to have
> -Wdeclaration-after-statement and only (finally) got rid of it in order
> to allow for these scope guards.
> 
> > We track capabilities as symbolic expressions, so something like
> > "rq->__lock" in this case. If there is an assignment to "rq", that
> > changes the meaning of the symbolic expression. The object referred to
> > by the expression is then no longer reachable. Currently we don't look
> > at assignments at all when it comes to tracking capabilities. We don't
> > even warn, it's simply documented as not being supported. We only look
> > at initializers, as in alias analysis. Having a separate variable
> > being initialized with the return value gives us a unique name for the
> > return value, which is good when we're working with symbolic
> > expressions.
> > 
> > If there are cases where assignment is really needed, we can also
> > check to which extent we can rewrite expressions or warn when the
> > objects they point to become unreachable. (In the example that would
> > be the case if someone assigned to "rq" again after the call to
> > "__task_rq_lock ".)
> 
> Right. I suspect we might need this if we want to minimize code churn.

There is also a case where a guard wraps the pointer in a struct;
because we need to carry extra state, like IRQ flags and the like, or
because the lock doesn't have a native type (RCU).

In this case the constructor things will return this structure and we'll
get a local copy on stack, a pointer to which will then be handed to the
destructor thing.

It would be very nice if it could understand that pattern too.

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:

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

Version of this that came up were:

static __always_inline u32
bpf_prog_run_array_uprobe(const struct bpf_prog_array *array,
                          const void *ctx, bpf_prog_run_fn run_prog)
{
        const struct bpf_prog_array_item *item;
        const struct bpf_prog *prog;
        struct bpf_run_ctx *old_run_ctx;
        struct bpf_trace_run_ctx run_ctx;
        u32 ret = 1;

        might_fault();
        RCU_LOCKDEP_WARN(!rcu_read_lock_trace_held(), "no rcu lock held");

        if (unlikely(!array))
                return ret;

        migrate_disable();

        run_ctx.is_uprobe = true;

        old_run_ctx = bpf_set_run_ctx(&run_ctx.run_ctx);
        item = &array->items[0];
        while ((prog = READ_ONCE(item->prog))) {
                if (!prog->sleepable)
                        rcu_read_lock();

                run_ctx.bpf_cookie = item->bpf_cookie;
                ret &= run_prog(prog, ctx);
                item++;

                if (!prog->sleepable)
                        rcu_read_unlock();
        }
        bpf_reset_run_ctx(old_run_ctx);
        migrate_enable();
        return ret;
}

and

static void ath9k_hif_usb_firmware_fail(struct hif_device_usb *hif_dev)
{
        struct device *dev = &hif_dev->udev->dev;
        struct device *parent = dev->parent;

        complete_all(&hif_dev->fw_done);

        if (parent)
                device_lock(parent);

        device_release_driver(dev);

        if (parent)
                device_unlock(parent);
}

And I think we can expect a fair amount of resistance from maintainers
if we're going to go around rewriting their -- perfectly fine code,
thank you very much -- to please a static analyzer :/

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

One of the more common patterns that I've talked about with Marco is
where modification requires two locks, while access requires either
lock.

The current __guarded_by() annotation cannot express this.

One possible way would be to construct a fake / 0-size capability
structure and have each of these locks acquire it in 'shared' mode (but
then you run into the recursion thing) and have a special annotation
that upgrades it to exclusive.

struct phoney __attribute__((capability(phoney))) { } phoney;

struct task_struct {
	raw_spinlock_t	pi_lock;

	cpumask_t	cpus_allowed __guarded_by(phoney);
};

void raw_spin_pi_lock(struct task_struct *p)
	__acquires(p->pi_lock)
	__acquires_shared(phoney);

void raw_spin_rq_lock(struct rq *rq)
	__acquires(rq->__lock)
	__acquires_shared(phoney);

static inline void upgrade_phoney(struct task_struct *p, struct rq *rq)
	__must_hold(p->pi_lock)
	__must_hold(rq->__lock)
	__releases_shared(phoney)
	__releases_shared(phoney)
	__acquires(phoney)
{ }

So this doesn't work because the recursion thing, but it is also just
plain horrible to have to do.

I would much rather write something like:

struct task_struct {
	raw_spinlock_t pi_lock;

	cpumask_t	cpus_allowed __guarded_by(pi_lock, rq->__lock);
}

And now I realize this case is doubly annoying because (rq) isn't
something that is in lexical scope at this point :-( These are the
locking rules though, and it is vexing not being able to express things
like this.


I should've taken another example; same thing, simpler setup:

struct perf_event_context {
	struct mutex		mutex;
	raw_spinlock_t		lock;

	struct list_head	event_list __guarded_by(mutex, lock);
	int			nr_events  __guarded_by(mutex, lock);
};

This would allow me to iterate the list holding either lock, but only
modify the list while holding both.

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Peter Zijlstra <peterz@infradead.org>
> On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:
> > 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.
> 
> Version of this that came up were:
> 
> static __always_inline u32
> bpf_prog_run_array_uprobe(const struct bpf_prog_array *array,
>                           const void *ctx, bpf_prog_run_fn run_prog)
> {
>         const struct bpf_prog_array_item *item;
>         const struct bpf_prog *prog;
>         struct bpf_run_ctx *old_run_ctx;
>         struct bpf_trace_run_ctx run_ctx;
>         u32 ret = 1;
> 
>         might_fault();
>         RCU_LOCKDEP_WARN(!rcu_read_lock_trace_held(), "no rcu lock held");
> 
>         if (unlikely(!array))
>                 return ret;
> 
>         migrate_disable();
> 
>         run_ctx.is_uprobe = true;
> 
>         old_run_ctx = bpf_set_run_ctx(&run_ctx.run_ctx);
>         item = &array->items[0];
>         while ((prog = READ_ONCE(item->prog))) {
>                 if (!prog->sleepable)
>                         rcu_read_lock();
> 
>                 run_ctx.bpf_cookie = item->bpf_cookie;
>                 ret &= run_prog(prog, ctx);
>                 item++;
> 
>                 if (!prog->sleepable)
>                         rcu_read_unlock();
>         }
>         bpf_reset_run_ctx(old_run_ctx);
>         migrate_enable();
>         return ret;
> }
> 
> and
> 
> static void ath9k_hif_usb_firmware_fail(struct hif_device_usb *hif_dev)
> {
>         struct device *dev = &hif_dev->udev->dev;
>         struct device *parent = dev->parent;
> 
>         complete_all(&hif_dev->fw_done);
> 
>         if (parent)
>                 device_lock(parent);
> 
>         device_release_driver(dev);
> 
>         if (parent)
>                 device_unlock(parent);
> }

So it boils down to

if (expr)
	acquire(mutex);
do_something();
if (expr)
	release(mutex);

If the "do_something()" block is rather short, as in the second example, it might also be an alternative to write:

         if (parent) {
                 device_lock(parent);
                 device_release_driver(dev);
                 device_unlock(parent);
         } else {
                 device_release_driver(dev);
         }

In any event, since the lock is only conditionally held, the block cannot require the mutex. So we can't be trying to satisfy "guarded_by" or "requires" attributes. We're just trying to avoid warnings about conditionally held capabilities. So at this point you might also be using "no_thread_safety_analysis". That's what we have typically done when we had this pattern.

> And I think we can expect a fair amount of resistance from maintainers
> if we're going to go around rewriting their -- perfectly fine code,
> thank you very much -- to please a static analyzer :/

I think there are some good arguments outside of the static analyzer. The pattern repeats the "if (expr)", and especially if "expr" is a bit more complex, this can be a source of errors:

                 if (!prog->sleepable)
                         rcu_read_lock();
 
                 // ...
 
                 if (prog->sleepable)
                         rcu_read_unlock();

This might slip through in a review, and could easily happen by copy-and-paste. (Of course you'll notice when testing this.) If you build some kind of conditional scope, it might look like this:

        scoped_conditional_guard (<rcu lock>, !prog->sleepable) {
                // ...
        }

Another aspect is that even if the condition is symbolically the same, its value might change between locking and unlocking. If you write the condition once and evaluate it once, you can exclude both sources of errors.

> One of the more common patterns that I've talked about with Marco is
> where modification requires two locks, while access requires either
> lock.
> 
> The current __guarded_by() annotation cannot express this.
> 
> One possible way would be to construct a fake / 0-size capability
> structure and have each of these locks acquire it in 'shared' mode (but
> then you run into the recursion thing) and have a special annotation
> that upgrades it to exclusive.
> 
> [...]
> 
> I would much rather write something like:
> 
> struct task_struct {
>         raw_spinlock_t pi_lock;
> 
>         cpumask_t       cpus_allowed __guarded_by(pi_lock, rq->__lock);
> }

There were ideas to support arbitrary Boolean expressions, but they wouldn't have allowed different expressions for read and write. So this would have been both too broad and not broad enough for your use case.

Your idea on the other hand sounds pretty reasonable to me. We already support multiple arguments in many other attributes, so it seems like a consistent extension. And semantically it makes sense to me as well: if a writer is required to hold all capabilities, then a reader should be fine if they hold any one. I'll have to think a bit more about whether this is always the right thing to do, but if it is, we have an easy way out.

> And now I realize this case is doubly annoying because (rq) isn't
> something that is in lexical scope at this point :-( These are the
> locking rules though, and it is vexing not being able to express things
> like this.

If it's not in scope, how do we know we have the right thing? Is task_struct always contained in some larger object that also has "rq", and never outside of that?

The language doesn't really prevent you from having a lonely task_struct, and then it wouldn't be clear what we're referring to.

A way out might be to consider the task_struct field in the larger object as guarded_by, and find a way to exclude the contained mutex. We could also introduce some kind of guarded_by_member(lock, member) to be added in the larger object. This would say that "lock" guards only the "member" subfield of the field. However, both would only apply if we're accessing the member through the parent. If you hand the task_struct by itself to some function and let that access cpus_allowed, we don't know what you're talking about.

But maybe you can explain a bit how the objects are coupled before I speculate too much into this.

Aaron

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Thu, Mar 06, 2025 at 11:14:21PM +0000, Puchert, Aaron wrote:

> So it boils down to
> 
> if (expr)
> 	acquire(mutex);
> do_something();
> if (expr)
> 	release(mutex);
> 
> If the "do_something()" block is rather short, as in the second example, it might also be an alternative to write:
> 
>          if (parent) {
>                  device_lock(parent);
>                  device_release_driver(dev);
>                  device_unlock(parent);
>          } else {
>                  device_release_driver(dev);
>          }
> 
> In any event, since the lock is only conditionally held, the block
> cannot require the mutex. So we can't be trying to satisfy
> "guarded_by" or "requires" attributes. We're just trying to avoid
> warnings about conditionally held capabilities. So at this point you
> might also be using "no_thread_safety_analysis". That's what we have
> typically done when we had this pattern.
> 
> > And I think we can expect a fair amount of resistance from maintainers
> > if we're going to go around rewriting their -- perfectly fine code,
> > thank you very much -- to please a static analyzer :/
> 
> I think there are some good arguments outside of the static analyzer.
> The pattern repeats the "if (expr)", and especially if "expr" is a bit
> more complex, this can be a source of errors:
> 
>                  if (!prog->sleepable)
>                          rcu_read_lock();
>  
>                  // ...
>  
>                  if (prog->sleepable)
>                          rcu_read_unlock();
> 
> This might slip through in a review, and could easily happen by
> copy-and-paste. (Of course you'll notice when testing this.) If you
> build some kind of conditional scope, it might look like this:
> 
>         scoped_conditional_guard (<rcu lock>, !prog->sleepable) {
>                 // ...
>         }
> 
> Another aspect is that even if the condition is symbolically the same,
> its value might change between locking and unlocking. If you write the
> condition once and evaluate it once, you can exclude both sources of
> errors.

Yeah, so IIRC I once proposed a guard that takes a NULL pointer to mean
not take the lock, but people had a bit of a fit.

It would've allowed writing the thing like:

	{
		guard(device)(parent);
		device_release_driver(dev);
	}

Anyway, yes I mostly agree, but this isn't necessarily code I have much
to say over. And while I can argue with the relevant maintainers, at
some point its their call if they are willing to accept a code change.

> > One of the more common patterns that I've talked about with Marco is
> > where modification requires two locks, while access requires either
> > lock.
> > 
> > The current __guarded_by() annotation cannot express this.
> > 
> > One possible way would be to construct a fake / 0-size capability
> > structure and have each of these locks acquire it in 'shared' mode (but
> > then you run into the recursion thing) and have a special annotation
> > that upgrades it to exclusive.
> > 
> > [...]
> > 
> > I would much rather write something like:
> > 
> > struct task_struct {
> >         raw_spinlock_t pi_lock;
> > 
> >         cpumask_t       cpus_allowed __guarded_by(pi_lock, rq->__lock);
> > }
> 
> There were ideas to support arbitrary Boolean expressions, but they
> wouldn't have allowed different expressions for read and write. So
> this would have been both too broad and not broad enough for your use
> case.

Right, that would work if you then also introduce __guarded_shared_by()
to express the requirements for access, it then becomes:

	cpumask_t	cpus_allowed __guarded_by(pi_lock && rq->__lock)
				     __guarded_shared_by(pi_lock || rq->__lock);

Which is a little more verbose over all, but entirely more flexible.

+- naming, I'm occasionally rubbish at naming :-)

> Your idea on the other hand sounds pretty reasonable to me. We already
> support multiple arguments in many other attributes, so it seems like
> a consistent extension. And semantically it makes sense to me as well:
> if a writer is required to hold all capabilities, then a reader should
> be fine if they hold any one. I'll have to think a bit more about
> whether this is always the right thing to do, but if it is, we have an
> easy way out.

If not all required locks are exclusive it comes apart.

Say, it needs a shared capability to satisfy existence (refcount, rcu,
whatever) and an object internal lock to serialize state.

But for exclusive locks, yes, holding all for modification implies
stability while holding any (except the empty) subset.

> > And now I realize this case is doubly annoying because (rq) isn't
> > something that is in lexical scope at this point :-( These are the
> > locking rules though, and it is vexing not being able to express things
> > like this.
> 
> If it's not in scope, how do we know we have the right thing? Is
> task_struct always contained in some larger object that also has "rq",
> and never outside of that?

See that __task_rq_lock() example I used for the return value. A task is
always on _a_ runqueue, but unless we hold that rq's lock, the relation
is not stable.

> The language doesn't really prevent you from having a lonely
> task_struct, and then it wouldn't be clear what we're referring to.

Yeah, this isn't something that can be expressed.

> A way out might be to consider the task_struct field in the larger
> object as guarded_by, and find a way to exclude the contained mutex.

> We could also introduce some kind of guarded_by_member(lock, member)
> to be added in the larger object. This would say that "lock" guards
> only the "member" subfield of the field. However, both would only
> apply if we're accessing the member through the parent. If you hand
> the task_struct by itself to some function and let that access
> cpus_allowed, we don't know what you're talking about.
> 
> But maybe you can explain a bit how the objects are coupled before I
> speculate too much into this.

:-)

Right, so we have a per-cpu struct rq, and a task has a member
indicating which cpu it currently belongs to.

struct rq {
	raw_spinlock_t __lock;
};

DEFINE_PER_CPU(struct rq, runqueues);

#define cpu_rq(cpu)	(&per_cpu(runqueues, (cpu)))

/*
 * And I suppose we can imagine runqueues to simply be an array
 * and per_cpu() to index into said array. Although the reality is that
 * it is much more like thread-local-storage in userspace.
 */

struct task_struct {
	raw_spinlock_t pi_lock;
	int cpu;
}

int task_cpu(struct task_struct *p)
{
	return p->cpu;
}

#define task_rq(p) cpu_rq(task_cpu(p))

struct rq *__task_rq_lock(struct task_struct *p)
	__must_hold(p->pi_lock)
	__acquires(_Return->__lock)
{
	struct rq *rq;

	lockdep_assert_held(&p->pi_lock);

	for (;;) {
		rq = task_rq(p);
		raw_spin_rq_lock(rq);
		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
			return rq;
		raw_spin_rq_unlock(rq);

		while (unlikelt(task_on_rq_migrating(p)))
			cpu_relax();
	}
}

And then we have a pile of variables, like the allowed CPU mask, that
are only to be modified while holding both pi_lock and the correct
rq->lock.

And yes, this is all somewhat of a pain :-)

Now, luck will have it that I am in fact one of the scheduler
maintainers, so I can muck about with this a bit -- within reason.

One thing we could do is add a struct rq pointer -- duplicating the cpu
member state, like:

struct task_struct {
	raw_spinlock_t pikk
	int cpu;
	struct rq *rq;
};

Possibly just for verification builds, but migrations are expensive
enough that I don't think tracking this one extra variable is going to
be noticed much.

This would give us means of writing what we want:

	cpumask	cpus_allowed __guarded_by(pi_lock, rq->__lock);

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Fri, Mar 07, 2025 at 09:52:04AM +0100, Peter Zijlstra wrote:

> Yeah, so IIRC I once proposed a guard that takes a NULL pointer to mean
> not take the lock, but people had a bit of a fit.
> 
> It would've allowed writing the thing like:
> 
> 	{
> 		guard(device)(parent);
> 		device_release_driver(dev);
> 	}

So the below does compile... Greg, how revolted are you? :-)

diff --git a/drivers/base/core.c b/drivers/base/core.c
index 5a1f05198114..7c95e7800b89 100644
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -4796,33 +4796,30 @@ void device_shutdown(void)
 		spin_unlock(&devices_kset->list_lock);
 
 		/* hold lock to avoid race with probe/release */
-		if (parent)
-			device_lock(parent);
-		device_lock(dev);
-
-		/* Don't allow any more runtime suspends */
-		pm_runtime_get_noresume(dev);
-		pm_runtime_barrier(dev);
-
-		if (dev->class && dev->class->shutdown_pre) {
-			if (initcall_debug)
-				dev_info(dev, "shutdown_pre\n");
-			dev->class->shutdown_pre(dev);
-		}
-		if (dev->bus && dev->bus->shutdown) {
-			if (initcall_debug)
-				dev_info(dev, "shutdown\n");
-			dev->bus->shutdown(dev);
-		} else if (dev->driver && dev->driver->shutdown) {
-			if (initcall_debug)
-				dev_info(dev, "shutdown\n");
-			dev->driver->shutdown(dev);
+		{
+			guard(device_cond)(parent);
+			guard(device)(dev);
+
+			/* Don't allow any more runtime suspends */
+			pm_runtime_get_noresume(dev);
+			pm_runtime_barrier(dev);
+
+			if (dev->class && dev->class->shutdown_pre) {
+				if (initcall_debug)
+					dev_info(dev, "shutdown_pre\n");
+				dev->class->shutdown_pre(dev);
+			}
+			if (dev->bus && dev->bus->shutdown) {
+				if (initcall_debug)
+					dev_info(dev, "shutdown\n");
+				dev->bus->shutdown(dev);
+			} else if (dev->driver && dev->driver->shutdown) {
+				if (initcall_debug)
+					dev_info(dev, "shutdown\n");
+				dev->driver->shutdown(dev);
+			}
 		}
 
-		device_unlock(dev);
-		if (parent)
-			device_unlock(parent);
-
 		put_device(dev);
 		put_device(parent);
 
diff --git a/include/linux/cleanup.h b/include/linux/cleanup.h
index ec00e3f7af2b..bf72fec6f99b 100644
--- a/include/linux/cleanup.h
+++ b/include/linux/cleanup.h
@@ -300,7 +300,7 @@ static __maybe_unused const bool class_##_name##_is_conditional = _is_cond
 #define DEFINE_GUARD_COND(_name, _ext, _condlock) \
 	__DEFINE_CLASS_IS_CONDITIONAL(_name##_ext, true); \
 	EXTEND_CLASS(_name, _ext, \
-		     ({ void *_t = _T; if (_T && !(_condlock)) _t = NULL; _t; }), \
+		     ({ void *_t = (_condlock) ? _T : NULL; _t; }), \
 		     class_##_name##_t _T) \
 	static inline void * class_##_name##_ext##_lock_ptr(class_##_name##_t *_T) \
 	{ return class_##_name##_lock_ptr(_T); }
diff --git a/include/linux/device.h b/include/linux/device.h
index 80a5b3268986..4e7ebbb7fb64 100644
--- a/include/linux/device.h
+++ b/include/linux/device.h
@@ -1046,6 +1046,7 @@ static inline void device_unlock(struct device *dev)
 }
 
 DEFINE_GUARD(device, struct device *, device_lock(_T), device_unlock(_T))
+DEFINE_GUARD_COND(device, _cond, (_T ? (device_lock(_T), true) : false))
 
 static inline void device_lock_assert(struct device *dev)
 {

Re: Thread Safety Analysis and the Linux kernel

[Greg Kroah-Hartman]

On Fri, Mar 07, 2025 at 01:52:25PM +0100, Peter Zijlstra wrote:
> On Fri, Mar 07, 2025 at 09:52:04AM +0100, Peter Zijlstra wrote:
> 
> > Yeah, so IIRC I once proposed a guard that takes a NULL pointer to mean
> > not take the lock, but people had a bit of a fit.
> > 
> > It would've allowed writing the thing like:
> > 
> > 	{
> > 		guard(device)(parent);
> > 		device_release_driver(dev);
> > 	}
> 
> So the below does compile... Greg, how revolted are you? :-)

Eeek!  But why?

> diff --git a/drivers/base/core.c b/drivers/base/core.c
> index 5a1f05198114..7c95e7800b89 100644
> --- a/drivers/base/core.c
> +++ b/drivers/base/core.c
> @@ -4796,33 +4796,30 @@ void device_shutdown(void)
>  		spin_unlock(&devices_kset->list_lock);
>  
>  		/* hold lock to avoid race with probe/release */
> -		if (parent)
> -			device_lock(parent);
> -		device_lock(dev);
> -
> -		/* Don't allow any more runtime suspends */
> -		pm_runtime_get_noresume(dev);
> -		pm_runtime_barrier(dev);
> -
> -		if (dev->class && dev->class->shutdown_pre) {
> -			if (initcall_debug)
> -				dev_info(dev, "shutdown_pre\n");
> -			dev->class->shutdown_pre(dev);
> -		}
> -		if (dev->bus && dev->bus->shutdown) {
> -			if (initcall_debug)
> -				dev_info(dev, "shutdown\n");
> -			dev->bus->shutdown(dev);
> -		} else if (dev->driver && dev->driver->shutdown) {
> -			if (initcall_debug)
> -				dev_info(dev, "shutdown\n");
> -			dev->driver->shutdown(dev);
> +		{
> +			guard(device_cond)(parent);

This is just so subtle it's scary.  I don't like that.

> +			guard(device)(dev);

This is fine, but really, why is this even needed?  None of the code you
are indenting here breaks out of the loop early, so how/why is this even
needed?

> +
> +			/* Don't allow any more runtime suspends */
> +			pm_runtime_get_noresume(dev);
> +			pm_runtime_barrier(dev);
> +
> +			if (dev->class && dev->class->shutdown_pre) {
> +				if (initcall_debug)
> +					dev_info(dev, "shutdown_pre\n");
> +				dev->class->shutdown_pre(dev);
> +			}
> +			if (dev->bus && dev->bus->shutdown) {
> +				if (initcall_debug)
> +					dev_info(dev, "shutdown\n");
> +				dev->bus->shutdown(dev);
> +			} else if (dev->driver && dev->driver->shutdown) {
> +				if (initcall_debug)
> +					dev_info(dev, "shutdown\n");
> +				dev->driver->shutdown(dev);
> +			}
>  		}
>  
> -		device_unlock(dev);
> -		if (parent)
> -			device_unlock(parent);
> -

So we save 3 lines?  Again, feels like total overkill.


>  		put_device(dev);
>  		put_device(parent);
>  
> diff --git a/include/linux/cleanup.h b/include/linux/cleanup.h
> index ec00e3f7af2b..bf72fec6f99b 100644
> --- a/include/linux/cleanup.h
> +++ b/include/linux/cleanup.h
> @@ -300,7 +300,7 @@ static __maybe_unused const bool class_##_name##_is_conditional = _is_cond
>  #define DEFINE_GUARD_COND(_name, _ext, _condlock) \
>  	__DEFINE_CLASS_IS_CONDITIONAL(_name##_ext, true); \
>  	EXTEND_CLASS(_name, _ext, \
> -		     ({ void *_t = _T; if (_T && !(_condlock)) _t = NULL; _t; }), \
> +		     ({ void *_t = (_condlock) ? _T : NULL; _t; }), \
>  		     class_##_name##_t _T) \
>  	static inline void * class_##_name##_ext##_lock_ptr(class_##_name##_t *_T) \
>  	{ return class_##_name##_lock_ptr(_T); }
> diff --git a/include/linux/device.h b/include/linux/device.h
> index 80a5b3268986..4e7ebbb7fb64 100644
> --- a/include/linux/device.h
> +++ b/include/linux/device.h
> @@ -1046,6 +1046,7 @@ static inline void device_unlock(struct device *dev)
>  }
>  
>  DEFINE_GUARD(device, struct device *, device_lock(_T), device_unlock(_T))
> +DEFINE_GUARD_COND(device, _cond, (_T ? (device_lock(_T), true) : false))

As I really don't want others to be calling this, worst case, just put
it in the driver core C file.

But again, ick ick ick, I worry this is going to be very subtle and
cause problems over time.

But very cool hack :)

thanks,

greg k-h

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Fri, Mar 07, 2025 at 03:22:33PM +0100, Greg Kroah-Hartman wrote:
> On Fri, Mar 07, 2025 at 01:52:25PM +0100, Peter Zijlstra wrote:
> > On Fri, Mar 07, 2025 at 09:52:04AM +0100, Peter Zijlstra wrote:
> > 
> > > Yeah, so IIRC I once proposed a guard that takes a NULL pointer to mean
> > > not take the lock, but people had a bit of a fit.
> > > 
> > > It would've allowed writing the thing like:
> > > 
> > > 	{
> > > 		guard(device)(parent);
> > > 		device_release_driver(dev);
> > > 	}
> > 
> > So the below does compile... Greg, how revolted are you? :-)
> 
> Eeek!  But why?

Right; I forgot to tell. This clang Thread Safety Analyser can't deal
with conditional locks. Things like:

	if (parent)
		device_lock(parent)
	do_something();
	if (parent)
		device_unlock(parent)

make it quite upset. The above would, once it properly understands the
guards, make it think the parent lock was unconditionally taken. It
effectively hides the condition from the analyser.

But yes, first time I proposed something like this Linus had a wee bit
of a wobble too :-) I figured this one at least has a different name.

Trouble is, this kind of pattern is quite common -- lots of driver code
has it. The alternative is disabling analysis for the entire function,
with the obvious down-side it won't find anything else in there either.

So I'm currently exploring how far we can push changing the code to
suit the analyser, because Aaron (co-author of said clang feature) is
quite hesitant to even consider trying to fix this.

Fixing this in the analyser would be near turning it into an interpreter
and risk running into the halting problem at compile time -- not a
pretty thought either.

> > diff --git a/drivers/base/core.c b/drivers/base/core.c
> > index 5a1f05198114..7c95e7800b89 100644
> > --- a/drivers/base/core.c
> > +++ b/drivers/base/core.c
> > @@ -4796,33 +4796,30 @@ void device_shutdown(void)
> >  		spin_unlock(&devices_kset->list_lock);
> >  
> >  		/* hold lock to avoid race with probe/release */
> > -		if (parent)
> > -			device_lock(parent);
> > -		device_lock(dev);
> > -
> > -		/* Don't allow any more runtime suspends */
> > -		pm_runtime_get_noresume(dev);
> > -		pm_runtime_barrier(dev);
> > -
> > -		if (dev->class && dev->class->shutdown_pre) {
> > -			if (initcall_debug)
> > -				dev_info(dev, "shutdown_pre\n");
> > -			dev->class->shutdown_pre(dev);
> > -		}
> > -		if (dev->bus && dev->bus->shutdown) {
> > -			if (initcall_debug)
> > -				dev_info(dev, "shutdown\n");
> > -			dev->bus->shutdown(dev);
> > -		} else if (dev->driver && dev->driver->shutdown) {
> > -			if (initcall_debug)
> > -				dev_info(dev, "shutdown\n");
> > -			dev->driver->shutdown(dev);
> > +		{
> > +			guard(device_cond)(parent);
> 
> This is just so subtle it's scary.  I don't like that.

Yeah, I was afraid of that. It's basically, if parent, take the lock,
otherwise nop out.

I don't suppose its better when written like: guard(if_device)(parent);
? I mean, its just naming, but sometimes that's all it takes.

Re: Thread Safety Analysis and the Linux kernel

[Greg Kroah-Hartman]

On Fri, Mar 07, 2025 at 03:35:17PM +0100, Peter Zijlstra wrote:
> On Fri, Mar 07, 2025 at 03:22:33PM +0100, Greg Kroah-Hartman wrote:
> > On Fri, Mar 07, 2025 at 01:52:25PM +0100, Peter Zijlstra wrote:
> > > On Fri, Mar 07, 2025 at 09:52:04AM +0100, Peter Zijlstra wrote:
> > > 
> > > > Yeah, so IIRC I once proposed a guard that takes a NULL pointer to mean
> > > > not take the lock, but people had a bit of a fit.
> > > > 
> > > > It would've allowed writing the thing like:
> > > > 
> > > > 	{
> > > > 		guard(device)(parent);
> > > > 		device_release_driver(dev);
> > > > 	}
> > > 
> > > So the below does compile... Greg, how revolted are you? :-)
> > 
> > Eeek!  But why?
> 
> Right; I forgot to tell. This clang Thread Safety Analyser can't deal
> with conditional locks. Things like:
> 
> 	if (parent)
> 		device_lock(parent)
> 	do_something();
> 	if (parent)
> 		device_unlock(parent)
> 
> make it quite upset. The above would, once it properly understands the
> guards, make it think the parent lock was unconditionally taken. It
> effectively hides the condition from the analyser.
> 
> But yes, first time I proposed something like this Linus had a wee bit
> of a wobble too :-) I figured this one at least has a different name.
> 
> Trouble is, this kind of pattern is quite common -- lots of driver code
> has it. The alternative is disabling analysis for the entire function,
> with the obvious down-side it won't find anything else in there either.
> 
> So I'm currently exploring how far we can push changing the code to
> suit the analyser, because Aaron (co-author of said clang feature) is
> quite hesitant to even consider trying to fix this.
> 
> Fixing this in the analyser would be near turning it into an interpreter
> and risk running into the halting problem at compile time -- not a
> pretty thought either.

Ah, thanks for the explaination, that makes more sense.

> > > diff --git a/drivers/base/core.c b/drivers/base/core.c
> > > index 5a1f05198114..7c95e7800b89 100644
> > > --- a/drivers/base/core.c
> > > +++ b/drivers/base/core.c
> > > @@ -4796,33 +4796,30 @@ void device_shutdown(void)
> > >  		spin_unlock(&devices_kset->list_lock);
> > >  
> > >  		/* hold lock to avoid race with probe/release */
> > > -		if (parent)
> > > -			device_lock(parent);
> > > -		device_lock(dev);
> > > -
> > > -		/* Don't allow any more runtime suspends */
> > > -		pm_runtime_get_noresume(dev);
> > > -		pm_runtime_barrier(dev);
> > > -
> > > -		if (dev->class && dev->class->shutdown_pre) {
> > > -			if (initcall_debug)
> > > -				dev_info(dev, "shutdown_pre\n");
> > > -			dev->class->shutdown_pre(dev);
> > > -		}
> > > -		if (dev->bus && dev->bus->shutdown) {
> > > -			if (initcall_debug)
> > > -				dev_info(dev, "shutdown\n");
> > > -			dev->bus->shutdown(dev);
> > > -		} else if (dev->driver && dev->driver->shutdown) {
> > > -			if (initcall_debug)
> > > -				dev_info(dev, "shutdown\n");
> > > -			dev->driver->shutdown(dev);
> > > +		{
> > > +			guard(device_cond)(parent);
> > 
> > This is just so subtle it's scary.  I don't like that.
> 
> Yeah, I was afraid of that. It's basically, if parent, take the lock,
> otherwise nop out.
> 
> I don't suppose its better when written like: guard(if_device)(parent);
> ? I mean, its just naming, but sometimes that's all it takes.

Naming matters here, so yes, a better way would be essential if you want
to do this.  This last suggestion is better, but still odd.  How about
something like:
	guard(if_exists)(parent);

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Peter Zijlstra <peterz@infradead.org>
> Right, that would work if you then also introduce __guarded_shared_by()
> to express the requirements for access, it then becomes:
> 
> 	cpumask_t	cpus_allowed __guarded_by(pi_lock && rq->__lock)
> 				     __guarded_shared_by(pi_lock || rq->__lock);
> 
> Which is a little more verbose over all, but entirely more flexible.

Would be interesting to see if you have patterns that require this additional flexibility. So perhaps we should wait with implementing something until we've seen a bit more.

> > Your idea on the other hand sounds pretty reasonable to me. We already
> > support multiple arguments in many other attributes, so it seems like
> > a consistent extension. And semantically it makes sense to me as well:
> > if a writer is required to hold all capabilities, then a reader should
> > be fine if they hold any one. I'll have to think a bit more about
> > whether this is always the right thing to do, but if it is, we have an
> > easy way out.
> 
> If not all required locks are exclusive it comes apart.
> 
> Say, it needs a shared capability to satisfy existence (refcount, rcu,
> whatever) and an object internal lock to serialize state.

Currently we categorize accesses into reads and writes, and reads need shared capabilities while writes need exclusive capabilities. (Reads are "lvalue-to-rvalue conversions" in C++ or "lvalue conversions" in C, writes are assignments and a bit more.) Am I reading this correct that you have operations (read or write?) that need a shared capability and an exclusive capability? Although you can put whatever requirements you want on functions:

void f() __requires(m1) __requires_shared(m2);

One concept that we have though is separate capabilities for a pointer and pointee:

int *p __guarded_by(m1) __pt_guarded_by(m2);

p; // shared m1
*p; // shared m1 & m2
p = &x; // exclusive m1
*p = 5; // shared m1, exclusive m2

// With alias analysis:
int* const copy = p; // shared m1
*copy; // shared m2

> Right, so we have a per-cpu struct rq, and a task has a member
> indicating which cpu it currently belongs to.
> 
> struct rq {
> 	raw_spinlock_t __lock;
> };
> 
> DEFINE_PER_CPU(struct rq, runqueues);
> 
> #define cpu_rq(cpu)	(&per_cpu(runqueues, (cpu)))
> 
> /*
>  * And I suppose we can imagine runqueues to simply be an array
>  * and per_cpu() to index into said array. Although the reality is that
>  * it is much more like thread-local-storage in userspace.
>  */
> 
> struct task_struct {
> 	raw_spinlock_t pi_lock;
> 	int cpu;
> }
> 
> int task_cpu(struct task_struct *p)
> {
> 	return p->cpu;
> }
> 
> #define task_rq(p) cpu_rq(task_cpu(p))

Ok, so then we can refer to the member: where you wanted to write rq->__lock, we write cpu_rq(cpu)->__lock.

However, I suppose the macros go quite deep and then we can come across a statement expression (or worse).

Another issue is aliasing. Maybe the caller has obtained the runqueue in a different way, and then it's not clear that it equals cpu_rq(cpu).

> One thing we could do is add a struct rq pointer -- duplicating the cpu
> member state, like:
> 
> struct task_struct {
> 	raw_spinlock_t pik;
> 	int cpu;
> 	struct rq *rq;
> };

I don't think we need this. You can write expressions of some complexity, including opaque function calls. (Just avoid statement expressions.) They're compared symbolically, which in the case of function calls implies they're pure. To play a bit with your example:

                rq = task_rq(p);
                raw_spin_rq_lock(rq);
                p->cpus_allowed = 0; // let's pretend it's an integer.

The second line acquires rq.__lock, which expands to cpu_rq(task_cpu(p)).__lock once we have alias analysis. For the write to cpus_allowed we need an exclusive lock on cpu_rq(p->cpu)->__lock by substitution. Suppose we make task_cpu a macro and cpu_rq a function (for sake of exposition). Then our existing lock is cpu_rq(p->cpu)->__lock and matches what we need. If we want to leave task_cpu a function, an __attribute__((return_capability)) might work there. (It's not a capability, but I think we only use the attribute for substitution and don't check the type.)

It might need some playing around what needs to be transparent to the analysis and what better stay opaque.

Aaron

Re: Thread Safety Analysis and the Linux kernel

[Paul E. McKenney]

On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:
> From: Marco Elver <elver@google.com>
> > 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/20250304092417.2873893-1-elver@google.com/
> 
> 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/20250305112041.GA16878@noisy.programming.kicks-ass.net/
> > -- 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.

We do have macros that acquire locks and enter RCU read-side critical
sections.  Also, depending on exactly where the analysis is done, static
inline functions might cause this to happen.

These can easily result in a function with nested calls to (for example)
rcu_read_lock().

							Thanx, Paul

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Paul E. McKenney <paulmck@kernel.org>
> On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:
> > 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.
> 
> We do have macros that acquire locks and enter RCU read-side critical
> sections.  Also, depending on exactly where the analysis is done, static
> inline functions might cause this to happen.
> 
> These can easily result in a function with nested calls to (for example)
> rcu_read_lock().

Macros would be a problem, functions not. As long as the function doesn't have __attribute__((locks_excluded(...))), which would be pointless with re-entrant mutexes, we don't know when checking the caller that the callee acquires the lock a second time. Similarly, in the function itself we don't know where we're called from, so we don't know that the caller already holds the mutex (in some cases). We only know when we have an __attribute__((requires_capability(...))), but then it would be pointless to acquire in the function.

Aaron

Re: Thread Safety Analysis and the Linux kernel

[Paul E. McKenney]

On Thu, Mar 06, 2025 at 11:24:17PM +0000, Puchert, Aaron wrote:
> > From: Paul E. McKenney <paulmck@kernel.org>
> > On Wed, Mar 05, 2025 at 11:54:14PM +0000, Puchert, Aaron wrote:
> > > 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.
> > 
> > We do have macros that acquire locks and enter RCU read-side critical
> > sections.  Also, depending on exactly where the analysis is done, static
> > inline functions might cause this to happen.
> > 
> > These can easily result in a function with nested calls to (for example)
> > rcu_read_lock().
> 
> Macros would be a problem, functions not. As long as the function doesn't have __attribute__((locks_excluded(...))), which would be pointless with re-entrant mutexes, we don't know when checking the caller that the callee acquires the lock a second time. Similarly, in the function itself we don't know where we're called from, so we don't know that the caller already holds the mutex (in some cases). We only know when we have an __attribute__((requires_capability(...))), but then it would be pointless to acquire in the function.

Got it!

Until such time as the analysis is carried out after inlining.  ;-)

							Thanx, Paul

RE: Thread Safety Analysis and the Linux kernel

[Puchert, Aaron]

> From: Paul E. McKenney <paulmck@kernel.org>
> Until such time as the analysis is carried out after inlining.  ;-)

The idea behind requiring the attributes is that we'll never have to do that. We let the programmer specify interface preconditions/postconditions so that we don't have to inspect the function body.

Inlining has enough disadvantages that it will probably never work here:
* Since we're looking at individual translation units and not the whole program, we might not see function definitions. So the analysis would behave differently based on whether a function is defined in a header or source file, which is undesirable. Some definitions might be in external libraries and never be available. 
* Even if we could see all definitions, there are complexity issues with inlining. We'd have to draw a line somewhere, which would make the analysis unpredictable as well.

But these are just the reasons for the design decision. What matters is the decision itself to consider bodies of other functions as black boxes and only work with the attributes on their declaration. I guess we could also more clearly document this.

Aaron

Re: Thread Safety Analysis and the Linux kernel

[Paul E. McKenney]

On Fri, Mar 07, 2025 at 05:59:49PM +0000, Puchert, Aaron wrote:
> > From: Paul E. McKenney <paulmck@kernel.org>
> > Until such time as the analysis is carried out after inlining.  ;-)
> 
> The idea behind requiring the attributes is that we'll never have to do that. We let the programmer specify interface preconditions/postconditions so that we don't have to inspect the function body.
> 
> Inlining has enough disadvantages that it will probably never work here:
> * Since we're looking at individual translation units and not the whole program, we might not see function definitions. So the analysis would behave differently based on whether a function is defined in a header or source file, which is undesirable. Some definitions might be in external libraries and never be available. 
> * Even if we could see all definitions, there are complexity issues with inlining. We'd have to draw a line somewhere, which would make the analysis unpredictable as well.
> 
> But these are just the reasons for the design decision. What matters is the decision itself to consider bodies of other functions as black boxes and only work with the attributes on their declaration. I guess we could also more clearly document this.

As good a design decision as any, so fair enough!

							Thanx, Paul

Re: Thread Safety Analysis and the Linux kernel

[Marco Elver]

On Thu, 6 Mar 2025 at 01:09, Puchert, Aaron <aaron.puchert@sap.com> wrote:
> From: Marco Elver <elver@google.com>
> > 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/20250304092417.2873893-1-elver@google.com/
>
> 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.

Thanks for your detailed responses!

Besides the discussion in concurrent mail threads (pun intended), I
just wanted to also mention the issue of who/when/how: after all is
said and done, and we have narrowed down what is missing, the question
is who can help implement things on the Clang side?

I will offer what I've done so far: try to dig in and see how far I
get (like for -Wthread-safety-pointer), but it's going to be ~months
this way. Someone more familiar with the Clang frontend and
Wthread-safety might fare better.

Any additional help and guidance will be much appreciated.

Thanks,
-- Marco

Re: Thread Safety Analysis and the Linux kernel

[Marco Elver]

On Wed, 5 Mar 2025 at 12:47, Marco Elver <elver@google.com> wrote:
[...]
> 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.

FTR, reentrant locking support is taken care of:
https://github.com/llvm/llvm-project/pull/137133 (should land soon).

But I think we need at least #2 (basic alias analysis) as well for
things to become tolerable for the kernel side. And that one looks a
bit harder to implement in Clang, so it'll be a while.

Thanks,
-- Marco

> 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> -- quote: "Fix the analyzer instead."]
>
> 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.
>
> 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> ]
>
> 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.
[...]

Re: Thread Safety Analysis and the Linux kernel

[Marco Elver]

On Mon, 5 May 2025 at 15:44, Marco Elver <elver@google.com> wrote:
> On Wed, 5 Mar 2025 at 12:47, Marco Elver <elver@google.com> wrote:
> [...]
> > 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.
>
> FTR, reentrant locking support is taken care of:
> https://github.com/llvm/llvm-project/pull/137133 (should land soon).
>
> But I think we need at least #2 (basic alias analysis) as well for
> things to become tolerable for the kernel side. And that one looks a
> bit harder to implement in Clang, so it'll be a while.
[..]
> > 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> > -- quote: "Fix the analyzer instead."]

There is hope: https://github.com/llvm/llvm-project/pull/142955 - but
it turned out to be "too easy to be true", so who knows if that'll
stick.

> > 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.
> >
> > 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> > ]
> >
> > 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.
> [...]

Re: Thread Safety Analysis and the Linux kernel

[Marco Elver]

On Thu, 5 Jun 2025 at 14:44, Marco Elver <elver@google.com> wrote:
> On Mon, 5 May 2025 at 15:44, Marco Elver <elver@google.com> wrote:
> > On Wed, 5 Mar 2025 at 12:47, Marco Elver <elver@google.com> wrote:
> > [...]
> > > 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.
> >
> > FTR, reentrant locking support is taken care of:
> > https://github.com/llvm/llvm-project/pull/137133 (should land soon).
> >
> > But I think we need at least #2 (basic alias analysis) as well for
> > things to become tolerable for the kernel side. And that one looks a
> > bit harder to implement in Clang, so it'll be a while.
> [..]
> > > 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/569186c5-8663-43df-a01c-d543f57ce5ca@kernel.org/
> > > -- quote: "Fix the analyzer instead."]
>
> There is hope: https://github.com/llvm/llvm-project/pull/142955 - but
> it turned out to be "too easy to be true", so who knows if that'll
> stick.

This got merged and it seems to stick.
Intel test robot's bleeding-edge Clang version also picked it up
already, and if I expose it to this tree here:

  https://git.kernel.org/pub/scm/linux/kernel/git/melver/linux.git/log/?h=cap-analysis/dev

It seems happy.

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

I don't think this is going to happen, but with alias analysis we can
emulate this with a macro (see __acquire_ret helper).

So all in all, this might be as good as it gets for now from the Clang side.

Patch bomb away?

Re: Thread Safety Analysis and the Linux kernel

[Peter Zijlstra]

On Thu, Sep 18, 2025 at 12:37:15PM +0200, Marco Elver wrote:

> Patch bomb away?

Yeah, lets try again. Worst case we find something else that needs
fixing :-)