Module bitvec::store[−][src]

Memory modeling.

This module provides the BitStore trait, which contains all of the logic required to perform memory accesses from a data structure handle.

bitvec Memory Model

bitvec considers all memory within BitSlice regions as if it were composed of discrete bits, each divisible and indipendent from its neighbors, just as the Rust memory model considers elements T in a slice [T]. Much as ordinary byte slices [u8] provide an API where each byte is distinct and independent from its neighbors, but the underlying processor silicon clusters them in words and cachelines, both the processor silicon and the Rust compiler require that bits in a BitSlice be grouped into memory elements, and collectively subjected to aliasing rules within their batch.

bitvec manages this through the BitStore trait. It is implemented on three type families available from the Rust standard libraries:

bitvec receives a memory region typed with one of these three families and wraps it in one of its data structures based on BitSlice. The target processor is responsible for handling any contention between memory elements; this is irrelevant to the bitvec model. bitvec is solely responsible for proving to the Rust compiler that all memory accesses through its types are correctly managed according to the &/&mut shared/exclusion reference model, and the UnsafeCell shared-mutation model.

Through BitStore, bitvec is able to demonstrate that &mut BitSlice references to a region of bits have no other BitSlice references capable of viewing those bits. However, &mut BitSlice references may have other &BitSlice references capable of viewing the memory elements at locations that it modifies, and the Rust compiler considers it undefined behavior for such conditions to allow racing writes and reads without synchronization.

As such, BitStore provides a closed type-system graph that the BitSlice API uses to mark events that can induce aliases to memory locations. When a &mut BitSlice<_, T> typed with an ordinary unsigned integer use any of the APIs that call .split_at_mut(), it transitions to &mut BitSlice<_, T::Alias>. The ::Alias associated type is always a type that manages aliasing references to a single memory location: either an atomic unsigned integer T or a Cell of the unsigned integer T. The Rust standard library guarantees that these types will behave correctly when multiple references to a single location attempt to read from and write to it.

The atomic and Cell types stay as themselves when BitSlice introduces aliasing conditions, as they are already alias-aware.

Lastly, the bitvec memory description model as implemented in the domain module is able to perform the inverse transition: where it can demonstrate a static awareness that the &/&mut exclusion rules are satisfied for a particular element slice [T], it may apply the ::Unalias marker to undo any ::Aliasing, and present a type that has no more aliasing protection than that with which the memory region was initially declared.

Namely, this means that the atomic and Cell wrappers will never be removed from a region that had them before it was given to bitvec, while a region of ordinary integers may regain the ability to be viewed without synchrony guards if bitvec can prove safety in the domain module.

In order to retain bitvec’s promise that an &mut BitSlice<_, T> has the sole right of observation for all bits in its region, the unsigned integers alias to a crate-internal wrapper over the alias-capable standard-library types. This wrapper forbids mutation through shared references, so two BitSlice references that alias a memory location, but do not overlap in bits, may not be coërced to interfere with each other.

Traits

BitStore

Common interface for memory regions.