Paul E. McKenney (paulmck) wrote,
Paul E. McKenney

Rusting the Linux Kernel: Compiler Writers Hate Dependencies (Control)

At the assembly language level on many weakly ordered architectures, a conditional branch acts as a very weak, very cheap, but very useful memory-barrier instruction. It orders any load whose return value feeds into the condition codes before all stores that execute after the branch instruction completes, whether the branch is taken or not. ARMv8 also has a conditional-move instruction (CSEL) that provides similar ordering.

Because the ordering properties of the conditional branch involve dependencies from the load to the branch and from the branch to the store, and because the branch is a control-flow instruction, this ordering is said to be due to a control dependency.

Because compilers do not understand them, control dependencies are quite fragile, as documented by the many cautionary tales in the Linux kernel's memory-barriers.txt documentation (search for the "CONTROL DEPENDENCIES" heading). But they are very low cost, so they are used on a few critically important fastpaths in the Linux kernel.

Rust could deal with control dependencies in a number of ways:

  1. The trivial solution is to promote the loads heading the control dependencies to smp_load_acquire(). This works, but adds instruction overhead on some architectures and needlessly limits compiler optimizations on all architectures (but to be fair, ARMv8 does exactly this when built with link-time optimizations). Another difficulty is identifying (whether manually or automatically) exactly which READ_ONCE() calls need to be promoted.
  2. An even more trivial solution is to classify code containing control dependencies as core Linux-kernel code that is outside of Rust's scope. Because there are very few uses of control dependencies in the Linux kernel, Rust would not lose much by taking this approach. In addition, there is the possibility of creating higher-level C-language primitives containing the needed control dependencies which are then wrappered for Rust-language use.
  3. The best approach from the Linux-kernel-in-Rust developer's viewpoint is for Rust to enforce the code style restrictions documented in memory-barriers.txt. However, there is some chance that this approach might prove to be non-trivial.
  4. Wait for compiler backends to learn about control dependencies. This might be a bit of a wait, especially given the difficulty even defining control dependencies within the current nomenclature of the C/C++ standards.

More information on control dependencies may be found in Section 15.3.3 ("Control-Dependency Calamities") of perfbook.


October 12, 2021: Self-review.
Tags: linux, lkmm, rust

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.