Function atomic_try_update 

pub unsafe fn atomic_try_update<T, U, F, R>(state: &Atom<T, U>, func: F) -> R
where
    F: Fn(&mut T) -> (bool, R),
    U: Copy + Eq,

This function is used to implement lock free synchronization primitives.

It is a special compare-and-swap loop that performs a hardware-level atomic integer load from a piece of memory that it manages, casts the byte representation of the integer that it read to a caller-provided type, and then passes the result into a caller-provided lambda.

The lambda optionally updates the fields of the struct that were passed into it. If the lambda returns false, the loop terminates. If it returns true, then atomic_try_update attempts to compare-and-swap the new version of the struct with the old version (by first casting it back to an integer).

The lambda actually returns a tuple of type (bool, R). The first field is used to decide whether or not to perform a compare and swap. The second is passed back to the caller. This allows the lambda to pass information to its calling environment without sharing mutable references with other invocations of itself or doing other things that the borrow checker disallows.

atomic_try_update is powerful for two reasons:

First, 128 bits is quite a lot of state and modern machines support 128-bit CAS. Pointers on 64-bit machines are ~ 40-48 bits wide, so it is enough space for two or three pointers with some bits left over to encode additional state. If even more bits are needed, you can play tricks such as storing offsets into an array instead of memory addresses. This allows you to pack state machines and simple data structure (including stacks, registers, and even simple allocators) into a single integer value, then to atomically modify your data structures and state machines.

Second, simple, cursory reviews of the lambda code are enough to verify that the resulting algorithm is linearizable: i.e., that all concurrent executions are equivalent to some single-threaded execution of the same code, and that all observers agree on the schedule.

The rules are described in the safety section. There is no way for the rust compiler to check that your lambda obeys the provided rules, and violations of them can lead to memory corruption, borrow checker invariant violations, and other unsound behavior. Therefore, we annotate the function “unsafe”.

In particular, if T is a Box<…>, and the lambda overwrites its argument, then the old value in the Box could be double-freed.

Safety

In order to use atomic_try_update safely, make sure your lambda follows the following two rules:

1. It must implement read set equivalence.
2. It must be a pure (side-effect-free) function.

Rule 1: Read set equivalence

Read set equivalence is the invariant that if the current value of the Atom matches the pre-value read by atomic_try_update, then all data read by the lambda has the same value as it had when the lambda read it.

This concept is closely related to, but distinct from approaches used in database concurrency control algorithms.

Read set equivalence trivially holds if the lambda only reads the data that was passed directly into it, and doesn’t follow pointers, references, or otherwise observe other non-local state in the system.

It is also fine for the lambda to read data from its caller’s stack frame, as long as that data is immutable while atomic_try_update is running. This is most easily achieved by only capturing shared references, and not capturing references to things that make use of interior mutability (such as Mutex, or any of the atomic integer types).

Another common approach involves using some extra mechanism to ensure read set equivalence. For instance, some data structures include a nonce in the data stored by Atom, and increment it on each operation. As long as the nonce does not wrap back around to exactly the same value just in time for the compare and swap to run, then we know that no other operations on this Atom have modified any state that we read in race with us.

The examples in the stack module explain read set equivalence in more detail.

Comparison with database concurrency control algorithms

Read set equivalence allows more schedules than typical database concurrency control algorithms. In particular, it allows write-write and read-write conflicts in the case where the read set of the lambda (“transactions”, in their context) has been changed, but then changed back to the value the transaction observed. Two phase locking prevents such schedules by blocking execution of conflicting logic, and multi-version concurrency control prevents them by only examining the version number of the read set, and not its contents. (The nonce trick we mentioned above is analogous to multi-version concurrency control.)

Rule 2: Pure functions

There are a few common ways for lambdas to fail to be pure functions, ordered from most to least likely:

The value that is stored in the the Atom could implicitly interact with global state. For instance, it could be a Box and talk to the allocator, or it could attempt to perform I/O.

The lambda could speculatively read a value after it has been freed. Even if the lambda then discards the result without acting on it (which would be safe in a garbage collected language), the act of loading the freed value could read from memory that has been returned to the operating system, leading to a segmentation fault. This is generally avoidable using an epoch based garbage collector, such as crossbeam_epoch, or by maintaining a pool of reused, but never freed objects for use by the data structure.

The lambda could speculatively read a value, store it on the heap or in a captured stack variable, and then return true. If the compare and swap fails, the lambda runs again, and then fails to overwrite the state from the failed speculative read, then it violates linearizability.

Thanks to the borrow checker, it is fairly difficult to implement such a bug. In particular, if your lambda attempts to capture a shared reference (&mut), it will fail to compile. However, you could defeat this check via internal mutability.

Finally, the lambda could crash or exhibit undefined behavior. Other versions of atomic_try_update include an “unsafe” (not in the rust sense) variant that allows torn reads. This means that the bit representation of the object that is passed into your lambda could be invalid, violating Rust’s safety guarantees, or causing sanity checks to fail, leading to panics. Similarly, if the lambda follows a pointer to something that has been marked for reuse (and therefore, the compare and swap will fail), some other thread could modify that object in race with the current thread’s failed speculative lambda invocation.