Verifying and Optimizing Compact NUMA-Aware Locks on Weak Memory Models

Developing concurrent software is challenging, specially if it has to run on modern architectures with Weak Memory Models (WMMs) such as Armv8 and RISC-V. For the sake of performance, WMMs allow hardware and compilers to aggressively reorder memory accesses. To guarantee correctness, developers have to carefully place memory barriers in the code to enforce ordering among critical memory operations. While WMM architectures are growing in popularity, it is notoriously difficult to identify the necessary and sufficient barriers of complex synchronization primitives. Unfortunately, recent publications often consider barriers just implementation details and omit them. In this technical note, we report our efforts in verifying the correctness of the Compact NUMA-Aware (CNA) lock algorithm on WMMs, inserting a correct and efficient set of barriers in the implementation. The CNA lock is of special interest because it is being integrated in Linux qspinlock, and this integration process has produced several reviews of the algorithm. We intend to contribute to this process by verifying the correctness of the latest patch (v15) on WMMs.