As an exercise, I'm trying to implement a concurrent data structure based on a paper, "Non-blocking hashtables with open addressing". I'm at a point where I have a working hashtable for keys of type
usize, since they can be updated atomically, and I'm in the process of adding support for larger keys as is detailed in section 3.3. Since they don't necessarily fit in a single machine word, they can't be updated atomically, and so the paper proposes a way to safely concurrently read and update the keys. Quoting from page 8:
... [A] cell’s key is only ever modified by a single writer, when the cell is in busy state.This means we only need to deal with concurrent single-writer multiple-reader access to the cell, rather than provide a general multi-word atomic update. We can therefore use Lamport’s version counters  (Figure 8).
This says that I can use a version number in conjunction with the value to ensure that the read is valid. It then goes on to describe how the version counter is used, which goes something like:
- (Atomically) Read and save the version counter value.
- Read the key value (assuming it is
Copy) from something like an
- Before using the value further, read and compare the version counter value to detect concurrent writes, and discard the key value if there is a mismatch.
However, the concurrent writer and readers don't mix well with the safety contract of pointer accesses as provided by
- All accesses performed by functions in this module are non-atomic in the sense of atomic operations used to synchronize between threads. This means it is undefined behavior to perform two concurrent accesses to the same location from different threads unless both accesses only read from memory.
This tells me that any concurrent read/write accesses to the given pointer is UB, even if I immediately detect and discard the invalid data.
Is my interpretation of this problem correct? If so, is there some alternative to raw pointers that would provide read/write operations with the stronger guarantees that I'm looking for? Specifically, writes must be well-defined in the presence of readers, correctly copying the original data and making those writes globally visible before returning control to the writer, and readers may read data in an invalid state during a concurrent write, relying on external mechanisms to prove the data's validity. Ideally, it would not involve locks, in the spirit of the original design, which rules out things like