Atomically increment two integers with CAS

Question

Apparently, it is possible to atomically increment two integers with compare-and-swap instructions. This talk claims that such an algorithm exists but it does not detail what it looks like.

How can this be done?

(Note, that the obvious solution of incrementing the integers one after the other is not atomic. Also, stuffing multiple integers into one machine word does not count because it would restrict the possible range.)

Answer 1

Make me think of a sequence lock. Not very accurate (putting this from memory) but something along the lines of:

let x,y and s be 64 bit integers.

To increment:

atomic s++ (I mean atomic increment using 64 bit CAS op)

memory barrier
atomic x++
atomic y++
atomic s++
memory barrier

To read:

do {
    S1 = load s
    X = load x
    Y = load y
    memory barrier
    S2 = load s
} while (S1 != S2)

Also see https://en.wikipedia.org/wiki/Seqlock