Re: Thread Safety Analysis and the Linux kernel

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.