Capability analysis for the kernel

One of the advantages of the Rust type system is its ability to encapsulate requirements about the state of the program in the type system; often, this state includes which locks must be held to be able to carry out specific operations. C lacks the ability to express these requirements, but there would be obvious benefits if that kind of feature could be grafted onto the language. The Clang compiler has made some strides in that direction with its thread-safety analysis feature; two developers have been independently working to take advantage of that work for the kernel.

The Clang feature is based on the concept of "capabilities" that a program can be determined — at compile time — to hold (or not) at any given point. Capabilities are typically the address of a data structure; for example, the address of a specific spinlock can be designated as a capability that a program can acquire with a lock operation. Functions can be annotated to indicate that they acquire or release a capability; developers can also indicate that callers of a function must hold (or not hold) a specific capability.

Adding analysis to the kernel

Bart Van Assche posted a patch series on February 6 showing how Clang's thread-safety feature could be used with the kernel's mutex type. The core of this work can be found in this patch, which annotates the various mutex-related functions; for example, the prototype for mutex_lock() and mutex_unlock() are modified to be:

    void mutex_lock(struct mutex *lock) ACQUIRE(*lock);
    void mutex_unlock(struct mutex *lock) RELEASE(*lock);

The first line says that a call to mutex_lock() will gain a capability in the form of the pointed-to mutex, while calling mutex_unlock() will give up that capability. The ACQUIRE() and RELEASE() macros are built on top of Clang's lower-level macros; there are quite a few other macros in the set. With that infrastructure in place, any function that requires a specific mutex to be held can be annotated accordingly; for example:

     static struct devfreq_governor *try_then_request_governor(const char *name)
	REQUIRES(devfreq_list_lock);

The compiler will then warn on any call to that function if the possession of the indicated lock (devfreq_list_lock) cannot be determined. There is also a series of macros with names like GUARDED_BY() to document that access to specific data (a structure member, for example) requires that a certain mutex be held. Those macros are not actually used in the posted series, though.

Van Assche's patch set is focused on the mutex type, and attempts to annotate usage throughout the entire kernel (though many of the annotations are NO_THREAD_SAFETY_ANALYSIS, which disables the analysis because the locking is too complicated for Clang to figure out — a situation that arises frequently). This work culminates in a massive patch touching over 800 files, which is a significant amount of code churn. The work has already found a number of locking bugs, the fixes for which are included in the series.

An alternative approach

On the same day, Marco Elver posted a patch set of his own with a slightly different approach to using the same feature; that series has since been updated, adopting the term "capability analysis" in place of "thread-safety analysis". While Van Assche used a breadth-first approach with mutexes, Elver has gone depth-first with a series that adds annotations for several locking primitives, but which is only active in subsystems that explicitly opt into it. In that way, warnings can be turned on for code where the maintainers and developers are interested in them (and will act on them), while being left off for the rest of the kernel.

The syntax of the annotations is a little different from Van Assche's approach, but the intent is clearly the same:

    void mutex_lock(struct mutex *lock) __acquires(lock);
    void mutex_unlock(struct mutex *lock) __releases(lock);

Elver's series, though, goes beyond mutexes to add annotations for spinlocks, reader-writer locks, seqlocks, single-bit spinlocks, read-copy-update, local locks, and wait/wound mutexes. In many cases, the annotations that already exist for the kernel's locking correctness validator (lockdep) have been reworked to add the needed capability declarations. There is a __guarded_by() annotation to document that a lock that must be held to access a specific structure member; its use can be seen in this patch instrumenting the kfence subsystem. The capability_unsafe() marker disables checking for a block of code. Most of the new annotations, along with documentation, can be found in this patch.

The other difference found in Elver's approach is the explicit opt-in design, which allows each subsystem to enable or disable the feature. By default, any given subsystem will not be covered by this analysis; that can be changed by adding one or more lines to the subsystem's makefile:

    CAPABILITY_ANALYSIS := y
    CAPABILITY_ANALYSIS_foo := y

The first line will enable analysis for all code compiled by way of that makefile, while the second will enable it only for the compilation creating foo.o. The patch set enables the feature for a number of kernel subsystems, including debugfs, kernel fences, rhashtables, tty drivers, the TOMOYO security module, the crypto subsystem, and more.

What next?

It would appear that the community has a wealth of riches here: two competing patch sets that aim to use the same compiler feature to improve correctness checking within the kernel. Either series can increase confidence that locking is being handled correctly, and both work entirely at compile time, with no run-time overhead. The reception for this work has been quite positive, with the only open question seemingly being which series would be accepted, or whether the kernel might adopt a combination of the two.

There are no definitive answers to that question, but a clue can be found in the fact that Van Assche has been posting comments (and Reviewed-by tags) for Elver's patch set. Peter Zijlstra has also tried his hand with Elver's work in the scheduler subsystem, saying that "this is all awesome". That attempt pointed to some needed changes; it seems Zijlstra also managed to crash the Clang compiler. He later pointed out that the capability analysis works in simple cases, but for "anything remotely interesting, where you actually want the help, it falls over".

Real use in the kernel (and beyond) may well help to drive development work in the Clang community to improve this analysis feature to the point that it can be routinely used to verify locking patterns. Some of that work may need to happen before support for this kind of capability analysis can be added to the kernel. But, since it is an opt-in, compile-time feature, there may well be value to adding it relatively soon, even if it needs further work. The kernel community seems to be hungry for this kind of support.

Index entries for this article
Kernel	Development tools/Static analysis

---

to post comments

if (need_lock)
    acquire_lock();

simple_code_like_an_assignment = 1;

if (need_lock)
    release_lock();

	struct device *parent = dev->parent;

	if (parent)
		device_lock(parent);

	device_release_driver(dev);

	if (parent)
		device_unlock(parent);

     // We probably have Weak reference to parent so need to upgrade.
     let maybe_parent = dev.parent.upgrade();
     let guard;
     // If we have parent then we need to lock it.
     if let(parent) = maybe_parent {
         guard = parent.lock();
     }
     device_release_driver(dev);

// callsite
let handle = lock_make_parent_handle(dev);
device_release_driver(handle);

// lock_make_parent_handle() definition
pub fn lock_make_parent_handle<'a>(dev: &'a mut Device) -> ParentHandle<'a, MutexGuard<'a, Device>>{
    ParentHandle{
        dev: dev,
        parent: dev.parent.upgrade().map(|parent| parent.lock().unwrap()),  // PoisonError handling elided for brevity
    }
}

pub fn make_parent_handle_unlocked<'a, P>(dev: &'a mut Device, maybe_parent: Option<P>) -> Result<ParentHandle<'a, P>, WrongParentError>
where P: 'a + DerefMut<Device>
{
    let maybe_dev_parent = dev.parent.upgrade();
    if maybe_parent.is_some() != maybe_dev_parent.is_some() {
        return Err(WrongParentError{});
    }
    if let (Some(parent), Some(dev_parent)) = maybe_parent, maybe_dev_parent {
        /* We cannot directly compare parent and dev_parent with PartialEq or the like, because by assumption,
         * dev_parent is already locked (or at least, it should be if the caller is using the function correctly).
         * Test whether parent points somewhere inside of dev_parent by doing pointer comparisons:
         */
        if (&*dev_parent as *const u8) > (&*parent as *const u8){
            return Err(WrongParentError{});
        }
        if (std::ptr::from_ref(&*dev_parent).wrapping_add(1) as *const u8) <= (&*parent as *const u8){
            // Can't wrap, Rust's memory model guarantees that base + size does not overflow usize.
            return Err(WrongParentError{});
        }
    }
    Ok(ParentHandle{
        dev: dev,
        parent: maybe_parent,
    })
}

// ParentHandle definition
struct ParentHandle<'a, P>
where P: 'a + DerefMut<Device>{
    dev: &'a mut Device,
    parent: Option<P>,
}
// This struct and the above two constructors are in a separate crate or module so that
// you can't manufacture your own instances from scratch.

// device_release_driver() definition
fn device_release_driver<'a, P>(handle: &mut ParentHandle<'a, P>)
where P: 'a + DerefMut<Device>
{
    // use handle.dev here... probably needs get() and get_mut() methods, and also for parent, etc.
}