Crate flize

flize is an implementation of epoch-based lock-free resource reclamation. The core is based around the paper “Practical lock-freedom” by Keir Fraster although many modifications have been made to adapt the scheme to perform well on on modern hardware and scale to a high degree.

This crate is useful if you have resources that require destruction in a concurrent environment and you don’t want to pay the price of locking.

flize attempts to encourage simplicity and avoid implicit global state. Additionally we try to reduce the amount of hidden gotchas and ways to shoot yourself in the foot.

A basic understanding of the previously mentioned paper and lock-free memory management is assumed throughout this documentation. If it isn’t clearly explained here it’s probably well defined in the paper. If not, please submit an issue and we will try to add documentation.

The core workflow of this library involves a couple of different types. First up you’ve got Collector and Shield, they are the gateway to interacting with the core functionality. A collector keeps track of what threads are reading protected pointers and which aren’t. It does this by requiring allowing the user to create Shields which act as as sort of guard. The creation and destruction of this type interacts with the internal bookkeeping in the Collector. The existance of at least one Shield implies that the thread is in a critical section and may access protected pointers.

Shields are in turn needed to load Atomics which simply boil down to an atomic pointer. Upon loading an Atomic you get a Shared which is a pointer type bounded by the lifetime of the shield. This is an attempt to prevent you from using a pointer without being in a critical section. Atomic implements all the common atomic operations for reading and modification such as load, store and compare_and_swap. When you remove all pointers to an object from shared memory it will be safe to destroy after all threads that could possibly have a reference have exited their critical sections (dropped all their shields). This can be accomplished by calling Shield::defer and supplying a closure. This closure will then be executed once all threads currently in a critical section have exited it at least once.

flize also handles a couple of other things that vastly improves quality of life and simplicity for users compared to crossbeam-epoch. For example flize provides you with full support for low and high bit pointer tags. It takes this one step further and allows for arbitrary structs that can be serialized to an array of bits to be used as tags. The library will handle reading, writing and stripping these tags from and to pointers along with serialization for you with a set of helper methods on Shared for interacting with tags ergonomically.

By default we attempt to utilize OS memory barriers to improve bookkeeping performance on Windows and Linux. For other targets we fall back to a more general although slower implementation. To make this possible we conditionally depend on winapi on Windows targets and libc on Linux targets. This accelerated bookkeeping is controlled by the fast-barrier Cargo feature. This flag is enabled by default and disabling it will cause the more general implementation to be compiled on all targets.

Structs

Atomic

An Atomic represents a tagged atomic pointer protected by the collection system.

Backoff

CachePadded

This struct has a minimum alignment that matches the cache prefetch size on different platforms. This is often used to reduce false sharing in concurrent code by adding space between fields.

Collector

The Collector acts like the central bookkeeper, it stores all the retired functions that are queued for execution along with information on what each participant is doing, Participants are pretty much always thread specific as of now but cross-thread participants may be added in the future. This information can be used to determine approximately when a participant last was in in a critical section and relevant shield history. The collector uses this information to determine when it is safe to execute a retired function.

DefinitiveEpoch

FullShield

A FullShield is largely equivalent to ThinShield in terms of functionality. They’re both shields with the same guarantees and can be user interchangeably. The major difference is that FullShield implements Send and Sync while Shield does not. FullShield is provided for scenarios like asynchronous iteration over a datastructure which is a big pain if the iterator isn’t Send.

Local

A Local represents a participant in the epoch system with a local epoch and a counter of active shields. If you are going to be creating a lot of shields and can keep around a Local it will be faster than calling Collector::shield every time since it avoids a table lookup to find the correct Local.

NullTag

This tag is a placeholder type that has a size of 0 and stores no state. If you don’t have any tag with information you want to store, this is the default.

Shared

A Shared represents a tagged pointer. It provides various utility methods for type conversion and tag manipulation. In addition it is the only pointer type that can be used to interact with Atomic since this type enforces a lifetime based on the shield used to create it.

ThinShield

A ThinShield locks an epoch and is needed to manipulate protected atomic pointers. It is a type level contract so that you are forces to acquire one before manipulating pointers. This reduces common mistakes drastically since incorrect code will now fail at compile time.

UnprotectedShield

An UnprotectedShield is a shield that does not actually lock an epoch, but can still be used to manipulate protected atomic pointers. Obtaining an UnprotectedShield is unsafe, since it allows unsafe access to atomics, and is only possible through flize::unprotected.

Enums

CowShield

This is a utility type that allows you to either take a reference to a shield and be bound by the lifetime of it or take an owned shield use 'static.

Traits

Shield

Universal methods for any shield implementation.

Tag

The Tag trait represents any struct that can be serialized and packed into the unused bits of a pointer producing a so called “tagged” pointer. The amount of bits available are variable and the amount you can use depends on whether the tag is in in the low or high position.

Functions

unprotected^⚠

Returns a reference to a dummy shield that allows unprotected access to Atomics.