Module std::lockfree

LockFreeMap, a fixed-size hash map many threads read and write at once without a lock. Every access goes through LockFreeMap::pin and the MapGuard it lends; removed entries are freed later, by LockFreeMap::collect, once no pinned thread can still see them.

Source: std/lockfree.weir; committed interface: std/lockfree.iface. Index

struct LfmEpoch

pub struct LfmEpoch<K, V>: forget {
    /* private fields */
}

The epoch collector's words of a LockFreeMap, kept together on their own cache lines. Its fields are private; public only so a type argument can name it (the corpus's R-UnsafeScope tests reach collector through it).

struct LockFreeMap

pub struct LockFreeMap<K, V>: destruct unsafe portable(K, V) {
    /* private fields */
} drop with Free in home

A hash map threads share and update concurrently without a lock; it never grows.

Reads and writes happen inside LockFreeMap::pin, through the MapGuard it lends, so a borrowed value cannot outlive the pin. MapGuard::remove only unlinks an entry; it is destroyed by a later LockFreeMap::collect on whichever thread calls it, once every thread pinned at the time has unpinned (epoch-based reclamation). Keys are hashed with std::cmp's Hash.

impl<K, V> LockFreeMap<K, V>

method new

pub fn new(n: usize) -> LockFreeMap<K, V> with Alloc

An empty map of at least n buckets (rounded up to a power of two); it never grows, so size it for the expected number of entries.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc any
may diverge
aborts: Alloc.alloc

method pin

pub fn pin(&self, f: fn(&MapGuard<K, V>) env {A}) with Alloc

Runs f pinned, lending it the MapGuard every read and write goes through.

with Alloc because a thread's first pin may allocate its record. f may not suspend (env {A}): a pin held across a suspension would hold back every collect meanwhile.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc any
may diverge
aborts: Alloc.alloc
holds what may not move at a scheduling point: always
enters the backing of self
callback f: envelope {A}; pinned: always; holds self

impl<K: drops {Free}, V: drops {Free}> LockFreeMap<K, V>

method collect

pub fn collect(&self) -> usize with Free

Destroys, on this thread, the removed entries no pinned thread can still reach, and answers how many. Call it periodically; an entry removed while some thread stays pinned waits for a later call.

Committed interface (std/lockfree.iface):

bound Free: Free any
may diverge
destroys values of K, V

struct MapGuard

pub struct MapGuard<K, V>: forget {
    /* private fields */
}

What a pinned thread reads and writes a LockFreeMap through, lent by LockFreeMap::pin: what it lends lives no longer than the pin.

impl<K: Hash + Eq, V> MapGuard<K, V>

method get

pub fn get(&self, k: &K) -> Option<&{self} V>

The value under k, lent for the pin; None when absent.

Committed interface (std/lockfree.iface):

bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
may diverge
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet | Hash not quiet
enters the backing of k
writes regions type K
loan of Hash across the backing of k
loan of Eq across the backing of k

method contains_key

pub fn contains_key(&self, k: &K) -> Bool

Whether k is present.

Committed interface (std/lockfree.iface):

bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
may diverge
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet | Hash not quiet
enters the backing of k
writes regions type K
loan of Hash across the backing of k
loan of Eq across the backing of k

method remove

pub fn remove(&self, k: &K) -> Bool

Removes k, answering whether it was present; the entry is destroyed by a later LockFreeMap::collect.

Committed interface (std/lockfree.iface):

bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
may diverge
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet | Hash not quiet
enters the backing of k
writes regions type K
loan of Hash across the backing of k
loan of Eq across the backing of k

impl<K: Hash + Eq + drops {Alloc}, V: drops {Alloc}> MapGuard<K, V>

method insert

pub fn insert(&self, k: K, v: V) -> Bool with Alloc

Adds k and v unless k is present, answering whether it added them; a pair it does not add it destroys. with Alloc for the new entry.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
may diverge
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet
destroys values of K, V
writes regions type K
loan of Hash across the backing of k

fn lfm_new

pub fn lfm_new<K, V, r>(n: usize) -> LockFreeMap<K, V> in r with Alloc in r

An empty map of at least n buckets (rounded up to a power of two, one at least); prefer LockFreeMap::new.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc[r] any
may diverge
aborts: Alloc.alloc

fn lfm_pin

pub fn lfm_pin<K, V, r>(m: &LockFreeMap<K, V> in r, f: fn(&MapGuard<K, V> in r) env {A}) with
    Alloc in r,

Runs f pinned to m, lending it the guard; the pin is released when f returns or unwinds. Prefer LockFreeMap::pin. with Alloc because a thread's first pin may add a record.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc[r] any
may diverge
aborts: Alloc.alloc
holds what may not move at a scheduling point: always
enters the backing of m
callback f: envelope {A}; pinned: always; holds m

fn lfm_get

pub fn lfm_get<K: Eq, V, r>(g: &MapGuard<K, V> in r, h: u64, k: &K) -> Option<&{g} V>

The value under key k with hash h, lent for the pin; None when absent. Prefer MapGuard::get, which hashes for you; h must be k's hash.

Committed interface (std/lockfree.iface):

bound Eq: Eq<K> any row {Diverge}
may diverge
scheduling point: Eq not quiet
holds what may not move at a scheduling point: Eq not quiet
enters the backing of k
writes regions type K
loan of Eq across the backing of k

fn lfm_insert

pub fn lfm_insert<K: Eq + drops {Alloc}, V: drops {Alloc}, r>(
    g: &MapGuard<K, V> in r,
    h: u64,
    k: K,
    v: V,
) -> Bool with Alloc in r

Adds k and v under hash h unless k is present, answering whether it added them; a pair it does not add it destroys. Prefer MapGuard::insert; h must be k's hash.

Committed interface (std/lockfree.iface):

bound Alloc: Alloc[r] any
bound Eq: Eq<K> any row {Diverge}
may diverge
aborts: Alloc.alloc
scheduling point: Eq not quiet
holds what may not move at a scheduling point: Eq not quiet
destroys values of K, V
writes regions type K

fn lfm_remove

pub fn lfm_remove<K: Eq, V, r>(g: &MapGuard<K, V> in r, h: u64, k: &K) -> Bool

Removes key k with hash h, answering whether it was present; the entry is destroyed by a later lfm_collect. Prefer MapGuard::remove; h must be k's hash.

Committed interface (std/lockfree.iface):

bound Eq: Eq<K> any row {Diverge}
may diverge
scheduling point: Eq not quiet
holds what may not move at a scheduling point: Eq not quiet
enters the backing of k
writes regions type K
loan of Eq across the backing of k

fn lfm_collect

pub fn lfm_collect<K: drops {Free}, V: drops {Free}, r>(m: &LockFreeMap<K, V> in r) -> usize with
    Free in r,

Frees, on this thread, the removed entries of m no pinned thread can still reach, and answers how many. Prefer LockFreeMap::collect.

Committed interface (std/lockfree.iface):

bound Free: Free[r] any
may diverge
destroys values of K, V