PairLock

A reader-writer lock for scenarios with frequent reads and infrequent writes.

Reads are wait-free, and writes are not starved by reads thet started after the previous write. Writes block each other.

This is accomplished by storing two values of T and marking one of them as active: Reads see the active value, while writes mutate the inactive one before switching the active status.

I'm no expert on lock-free programming, and I've only tested on x86_64, however the code makes liberal use of fence(SeqCst).

It can be used with any (sized) type, but wrapping them in a Box or Arc might improve performance by reducing false sharing.

Does not have poisoning.

Implementation details

PairLock is a variation of differential reference counting that doesn't require double-word atomics:

One AtomicUsize stores the index of the active slot and the all-time number of started reads of that slot. A slot-specific AtomicUsize stores the all-time number of finished reads of that slot. The current read count is the difference between those variables. Wrap-around is OK as long as there are no more than usize::MAX/2 current reads. The number of started reads of the inactive slot is stored in a mutex only used used by writes.

Reads start by incrementing the first variable, and finish by incrementing the second one. Writes start by locking the mutex and waiting untill all reads of the inactive slot have finished, and finish by swapping the value of the first variable with the one in the mutex.

The algorithm is similar to left-right locking, but simpler and not as efficient: Left-right reduces sharing by having multiple counters, and readers only needing to modify one of them.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.