Manual Pages  — SMR

#include <sys/smr.h>

Safe Memory Reclamation (SMR) is a facility which enables the implementation of memory-safe lock-free data structures. In typical usage, read accesses to an SMR-protected data structure, such as a hash table or tree, are performed in a "read section" consisting of code bracketed by smr_enter() and smr_exit() calls, while mutations of the data structure are serialized by a traditional mutex such as mutex(9). In contrast with reader-writer locks such as rwlock(9), rmlock(9), and sx(9), SMR allows readers and writers to access the data structure concurrently. Readers can always enter a read section immediately ( smr_enter() never blocks ), so mutations do not introduce read latency. Furthermore, smr_enter() and smr_exit() operate only on per-CPU data and thus avoid some of the performance problems inherent in the implementation of traditional reader-writer mutexes. SMR can therefore be a useful building block for data structures which are accessed frequently but are only rarely modified.

Note that any SMR-protected data structure must be implemented carefully such that operations behave correctly in the absence of mutual exclusion between readers and writers. The data structure must be designed to be lock-free; SMR merely facilitates the implementation, for example by making it safe to follow dangling pointers and by helping avoid the ABA problem.

When shared accesses to and mutations of a data structure can proceed concurrently, writers must take care to ensure that any items removed from the structure are not freed and recycled while readers are accessing them in parallel. This requirement results in a two-phase approach to the removal of items: first, the item is unlinked such that all pointers to the item are removed from the structure, preventing any new readers from observing the item. Then, the writer waits until some mechanism guarantees that no existing readers are still accessing the item. At that point the memory for that item can be freed and reused safely. SMR provides this mechanism: readers may access a lock-free data structure in between calls to the smr_enter() and smr_exit() functions, which together create a read section, and the smr_advance(), smr_poll(), smr_wait(), and smr_synchronize() functions can be used to wait for threads in read sections to finish. All of these functions operate on a smr_t state block which holds both per-CPU and global state. Readers load global state and modify per-CPU state, while writers must scan all per-CPU states to detect active readers. SMR is designed to amortize this cost by batching to give acceptable performance in write-heavy workloads.

Threads enter a read section by calling smr_enter(). Read sections should be short, and many operations are not permitted while in a read section. Specifically, context switching is disabled, and thus readers may not acquire blocking mutexes such as mutex(9). Another consequence of this is that the thread is pinned to the current CPU for the duration of the read section. Furthermore, read sections may not be nested: it is incorrect to call smr_enter() with a given smr_t state block when already in a read section for that state block.

To simplify the integration of SMR into consumers, the uma(9) kernel memory allocator provides some SMR-specified facilities. This eliminates a good deal of complexity from the implementation of consumers and automatically batches write operations.

In typical usage, a UMA zone (created with the UMA_ZONE_SMR flag or initialized with the uma_zone_set_smr() function) is coupled with a smr_t state block. To insert an item into an SMR-protected data structure, memory is allocated from the zone using the uma_zalloc_smr() function. Insertions and removals are serialized using traditional mutual exclusion and items are freed using the uma_zfree_smr() function. Read-only lookup operations are performed in SMR read sections. uma_zfree_smr() waits for all active readers which may be accessing the freed item to finish their read sections before recycling that item's memory.

If the zone has an associated per-item destructor, it will be invoked at some point when no readers can be accessing a given item. The destructor can be used to release additional resources associated with the item. Note however that there is no guarantee that the destructor will be invoked in a bounded time period.

The smr_enter() function has acquire semantics, and the smr_exit() function has release semantics. The smr_advance(), smr_poll(), smr_wait(), and smr_synchronize() functions should not be assumed to have any guarantees with respect to memory ordering. In practice, some of these functions have stronger ordering semantics than is stated here, but this is specific to the implementation and should not be relied upon. See atomic(9) for more details.

atomic(9), locking(9), uma(9)