generation-compare-and-swap, or GCAS, in CTries

Question

The data structure is used for example in Scala: https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala

More details in this paper: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

The logic I'm confused about is on line 139 in Figure 11 on page 6 of ctries-snapshot.pdf

The code checks if the generation of the root node is the same as the current node before proceeding. To quote the paper,

The idea is to communicate the intent of replacing the value in the I-node and check the generation field in the root before committing to the new value

This is the last sentence of the second paragraph in section 4.1 on page 6. The root generation is changed for example when a snapshot is taken (Figure 7 on page 15).

The question is, I don't see any synchronization mechanism that would prevent updates to the root right after the generation check. To use the papers own words, how is "the intent of replacing the value in the I-node" communicated to other threads attempting to update the root node through snapshots? From what I can tell, the root and the I-node in question can be two distinct nodes, and I'm not sure how the CAS's surrounding the generation check can prevent a race.

Answer 1

Nice observation.

To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying the root. Any modification of the root is only successful if the value below the main I-node did not change.

All reads of the root location are in the actual code calls to RDCSS_READ_ROOT:

https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/concurrent/TrieMap.scala#L694

And all CASes to the root are similarly replaced with an RDCSS. More details about this instruction in this paper:

https://timharris.uk/papers/2002-disc.pdf

I guess this important detail that you noticed (and in fact, you are maybe even the first person to notice so far, besides myself) was left out of the paper to keep the text clear.