Crate housekeeping 

Cleaning up while you’re away.

Reference counting (e.g. via Arc) is a common strategy for cleaning up resources shared between threads. However, it has limitations; reference counted objects cannot be (easily) stored in atomic variables, due to subtle race conditions. housekeeping is a concurrent memory reclaimer; it helps manage atomically-swappable resources and clean them up safely.

housekeeping is designed to run periodically, e.g. in between batches of executed tasks. It is inspired by seize and crossbeam_epoch, but is simpler and offers lower-level interfaces.

Use Cases

Here is a simple example demonstrating the need for concurrent memory reclaimers when writing data structures. Consider implementing an atomically swappable container type Swappable<T>. A value of type T can be stored in such a container, then atomically swapped for another value. Some threads may continue using the old value after a swap, but only for a short while.

When a swap occurs, the old value of T needs to be cleaned up, but it might be in use by other threads. A typical solution here is reference counting, e.g. with Arc. So, every value of T would be stored in an Arc, and Swappable<T> would contain an atomic pointer which would be cast to and from Arc automatically.

Unfortunately, this is unsound. With such an implementation, a thread would load the current value of the Swappable by fetching the current pointer value, casting it to Arc<T>, then incrementing its reference count. But the Arc could be deallocated in between the fetch and the increment; the increment operation would then access deallocated memory, causing UB. This is a common issue that complicates all atomic swapping of resources.

housekeeping provides a different approach: it maintains a handle on every thread to track accessed resources. Handles are periodically refreshed, during which time the thread cannot access shared resources. During a refresh, the thread will be synchronized with global state, ensuring that it cannot observe recently removed values. This guarantees that a thread is only using “recent” values after a refresh.

When a value is removed from global visibility (e.g. when it is swapped out of an atomic variable), its cleanup is deferred. The cleanup function is tracked relative to all known threads; once every thread has refreshed since the value was swapped, the value is guaranteed not to be used, and it can be safely deallocated.

This approach has many benefits: it eliminates per-object reference counting (which can be expensive for large numbers of small objects) and allows more diverse kinds of resources (e.g. integer IDs) to be safely cleaned up.

Algorithm

housekeeping implements quiescent state based reclamation (QSBR), which is quite similar to the conventional epoch-based reclamation. It operates as follows:

During the execution of the program, objects may be shared; they may be part of a global view. For example, a concurrent hash table can be shared between threads, in which case it and its elements are globally visible. Sharing is transitive: anything accessible from a shared object is also considered shared.

Removing a shared object is non-trivial; multiple threads may be accessing it concurrently. The object cannot be dropped or recycled until all threads are guaranteed not to observe it. First, the object will be detached from the global view, so that any threads known to observe the updated global view cannot access it. Then, the object is retired (its drop/recycle is deferred) until a point where all threads are known not to observe it.

Every thread will periodically go through a quiescent state (QS), where it is guaranteed not to observe any shared objects. Quiescent states cause synchronization between threads: if thread A undergoes a QS after thread B, thread A will observe thread B’s global view (at the time of QS), and will not be able to access any objects removed before thread B’s QS.

An epoch is a period of time, across threads (potentially a different period of time for every thread) during which objects are retired. Every thread refers to a particular epoch, and adds its retires there. During a QS, epochs are cycled: if all threads are on the same epoch, a new epoch is created (which the current thread moves to), or if a new epoch has been created already, it is moved to. This results in at most two epochs being used at any time.

For efficiency, objects are collected in thread-local batches before being added to their epoch. Epochs have a linked list of batches. Batches are themselves heap allocations, and are carefully reused. For this reason, a third epoch (the most recently cleared one) is also tracked; when a thread needs a new batch, it will try to take one from the third epoch. This is the moment when the deferred drop/recycle actions in the batch are executed.

Rationale

seize and crossbeam_epoch have different goals and limitations from housekeeping. seize only supports atomic pointers, and prioritizes tail latency over average throughput. crossbeam_epoch is more generic, but it has a complex implementation and does not support MIRI.

housekeeping has a very simple implementation, allows arbitrary resources to be cleaned up, and is compatible with MIRI and Loom. It offers flexible low-level interfaces (e.g. RawHandle) which give the user more control, e.g. with how cleanup actions are batched and stored.

Structs

Cleanups

Deferred cleanup actions.

Handle

A handle for deferring cleanups.

RawHandle

A raw handle for deferring cleanups.

SimpleBatch

A batch of simple cleanup functions.