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

At memory 0x100 and 0x104 are two 32-bit counters. They represent a 64-bit 开发者_StackOverflow社区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!

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.

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.

In addition to what has already been said, you won't get more accurate timing reads than your interrupt / context switch jitter allows. If you fear an interrupt / context switch in the middle of a timer polling, the solution is not to adapt some strange read-read-read-compare algorithm, nor is it to use memory barriers or semaphores.

The solution is to use a hardware interrupt for the timer, with an interrupt service routine that cannot be interrupted when executed. This will give the highest possible accuracy, if you actually have need of such.

The obvious and presumably intended answer is already given by Hobbs and jkerian:

1. sample High
2. sample Low
3. read High again - if it differs from the sample from step 1, return to step 1

On some multi-CPU/core hardware, this doesn't actually work properly. Unless you have a memory barrier to ensure that you're not reading High and Low from your own core's cache, then updates from another core - even if 64-bit atomic and flushed to some shared memory - aren't guaranteed to be visible in your core a timely fashion. While High and Low must be volatile-qualified, this is not sufficient.

The higher the frequency of updates, the more probable and significant the errors due to this issue.

There is no portable way to do this without some C wrappers for OS/CPU-specific memory barriers, mutexes, atomic operations etc..

Brooks' comment below mentions that this does work for certain CPUs, such as modern AMDs.

If you can guarantee that the maximum time of context switch is significantly less than half the low word rollover period, you can use that fact to decide whether the Low value was read before or after its rollover, and choose the correct high word accordingly.

H1=High;L=Low;H2=High;
if (H2!=H1 && L < 0x7FFFFFF) { H1=H2;}
result= H1<<32+L;

This avoids the 'repeat' phase of other solutions.

The problem statement didn't include whether the counters could roll over all 64-bits several times between reads. So I might try alternating reading both 32-bit words a few thousand times, more if needed, store them in 2 vector arrays, run a linear regression fit modulo 2^32 against both vectors, and apply slope matching contraints of that ratio to the possible results, then use the estimated regression fit to predict the count value back to the desired reference time.