  We consider the verification of lock-free data structures that manually
manage their memory with the help of a safe memory reclamation (SMR) algorithm.
Our first contribution is a type system that checks whether a program properly
manages its memory. If the type check succeeds, it is safe to ignore the SMR
algorithm and consider the program under garbage collection. Intuitively, our
types track the protection of pointers as guaranteed by the SMR algorithm.
There are two design decisions. The type system does not track any shape
information, which makes it extremely lightweight. Instead, we rely on
invariant annotations that postulate a protection by the SMR. To this end, we
introduce angels, ghost variables with an angelic semantics. Moreover, the SMR
algorithm is not hard-coded but a parameter of the type system definition. To
achieve this, we rely on a recent specification language for SMR algorithms.
Our second contribution is to automate the type inference and the invariant
check. For the type inference, we show a quadratic-time algorithm. For the
invariant check, we give a source-to-source translation that links our programs
to off-the-shelf verification tools. It compiles away the angelic semantics.
This allows us to infer appropriate annotations automatically in a
guess-and-check manner. To demonstrate the effectiveness of our type-based
verification approach, we check linearizability for various list and set
implementations from the literature with both hazard pointers and epoch-based
memory reclamation. For many of the examples, this is the first time they are
verified automatically. For the ones where there is a competitor, we obtain a
speed-up of up to two orders of magnitude.
