How to read two 32bit counters as a 64bit integer without race condition

Question

At memory 0x100 and 0x104 are two 32-bit counters. They represent a 64-bit timer and are constantly incrementing.

How do I correctly read from two memory addresses and store the time as a 64-bit integer?

One incorrect solution:

x = High
y = Low
result =  x << 32 + y

(The program could be swapped out and in the meantime Low overflows...)

Additional requirements:
Use C only, no assembly
The bus is 32-bit, so no way to read them in one instruction.
Your program may get context switched at any time.
No mutex or locks available.

Some high-level explanation is okay. Code not necessary. Thanks!

Answer 1

I learned this from David L. Mills, who attributes it to Leslie Lamport:

1. Read the upper half of the timer into H.
2. Read the lower half of the timer into L.
3. Read the upper half of the timer again into H'.
4. If H == H' then return {H, L}, otherwise go back to 1.

Assuming that the timer itself updates atomically then this is guaranteed to work -- if L overflowed somewhere between steps 1 and 2, then H will have incremented between steps 1 and 3, and the test in step 4 will fail.

Answer 2

Given the nature of the memory (a timer), you should be able to read A, read B, read A' and compare A to A', if they match you have your answer. Otherwise repeat.

It sortof depends on what other constraints there are on this memory. If it's something like a system-clock, the above will handle the situation where 0x0000FFFF goes to 0x00010000, and, depending on the order you read it in, you would otherwise erroneously end up with 0x00000000 or 0x0001FFFF.