  Logical atomicity has been widely accepted as a specification format for data
structures in concurrent separation logic. While both lock-free and lock-based
data structures have been verified against logically atomic specifications,
most of the latter start with atomic specifications for the locks as well. In
this paper, we compare this approach with one based on older
lock-invariant-based specifications for locks. We show that we can still prove
logically atomic specifications for data structures with fine-grained locking
using these older specs, but the proofs are significantly more complicated than
those that use atomic lock specifications. Our proof technique is implemented
in the Verified Software Toolchain, which relies on older lock specifications
for its soundness proof, and applied to C implementations of lock-based
concurrent data structures.

Programming Languages