Implementing Multi-word Atomic Snapshots on Current Hardware (short)

We present an algorithm that takes an atomic snapshot of a section of memory, without support from other code, using only read accesses to memory. Our goal is to ensure simultaneous read operations do not conflict at any point in the memory hierarchy, without inflating memory usage. Mutual-exclusion, even \multiple-reader single-writer” variants, and reference counting demand exclusive access to shared reader counts of some form. Systems using only local memory require frequent use of expensive read-after-write memory barriers, constraining their optimisation both in the CPU and the memory hierarchy. Other algorithms rely on an external garbage collector, delaying memory reuse and increasing their footprint in memory. Our algorithm relies on the following observation: if a series of read instructions complete without needing to load memory into the cache, and without an intervening local write operation, then the reads can be viewed as occurring atomically at the start of the series. It is thus trivial to see that such a series of read instructions forms a multiword snapshot. The snapshot algorithm simply loops until all reads hit in the cache. This is verified using values from the processor’s internal cache-miss counter. To prevent an intervening local write by a pre-empting thread, we also count user/supervisor mode switches, which must occur during pre-emption.