A Fast Wait-Free Solution to Read-Reclaim Races in Reference Counting

Abstract

Reference counting is a safe alternative to manual memory management for multithreaded programs, and is supported by the standard libraries of several major programming languages (e.g., Arc in Rust, shared_ptr and atomic<shared_ptr> in C++). In concurrent reference counting, read-reclaim races, where a read of a mutable variable races with a write that deallocates the old value, require special handling: use-after-free errors occur if the object is deallocated by the writing thread before the reading thread can increment the reference count. Existing solutions are not wait-free, have a space overhead and/or take time linear in the number of threads for updates. We introduce an implementation for concurrent reference counting with no delayed reclamation, which is wait-free, easy to implement and fast in practice. Writes operate in constant time and reads usually in constant time, and in the worst-case, linear with respect to the number of threads that actually work with the variable. Our algorithm is based on the split reference count technique, which is used in production but is only lock-free. We re-explain this technique as a special case of weighted reference counting, to arrive at a simpler explanation of this technique that is often claimed to be difficult. We show that our algorithm works well in practice by benchmarking it against other implementations.