[ntp:hackers] [Gpsd-dev] A lightweight synchronization mechanism for shared memory

Terje Mathisen terje at tmsw.no
Fri Mar 25 07:04:24 UTC 2011


Eric Raymond wrote:
> tz<thomas at mich.com>:
>> Anyway it won't work if memcpy is interruptable.
>>
>> Reader starts the memcpy, copies the start sentinel and half the payload.
>> Writer increments the start sentinel. and writes into the payload.
>> Reader continues the memcpy where it left off through the end sentinel.
>>
>> Both sentinels are equal, yet the bottom part of the payload is invalid.
>
> Hm.  You're right.  The copy has to be uninterruptible.
>
>> The only way I can think of is a single writer sets a bool to safe to
>> read - unsafe to write, and a single reader sets it back to safe to
>> read - unsafe to write.
>
> Doesn't help the multiple-readers case.

I've been reading the source code for this shm interface, and to me it 
seems almost like a no-brainer to go to a circular buffer of 2^N 
entries, along with a single (write-update only) counter at the front 
end which indicates where the latest valid entry is located.

The readers (one or more) can then always read the last valid entry, it 
might be a re-read of what they read on the previous iteration, but that 
is something which it is easy for the reader to guard against:

   unsigned cnt = shm->count;
   if (cnt == prev_cnt) return;

When the counter is valid you mask it with the buffer count mask to 
bring it into range:

   prev_cnt = cnt;
   cnt &= shm->count_mask; // Bring it into [0..7] range?

Copy the current entry into local vars:

     tvr.tv_sec=shm->[cnt].receiveTimeStampSec;
     tvr.tv_usec=shm->[cnt].receiveTimeStampUSec;
     tvt.tv_sec=shm->[cnt].clockTimeStampSec;
     tvt.tv_usec=shm->[cnt].clockTimeStampUSec;

This is of course still not absolutely bulletproof, in that a reader 
process which starts to read an entry, then gets put to sleep for N(=8?) 
seconds, can wake up again and read the last half of an updated record.

This is easy to guard against by re-reading the shm->count value: Since 
this counter is explicitly allowed to wrap around at 2^32 or 2^64, you 
cannot sleep for that many seconds.

a) You can always read the last valid entry.
b) The only sync barrier needed is in the producer (gpsd) which should 
have a write barrier between the last write to the new record, and the 
increment of the shm->count variable.
c) The protocol is _very_ similar to the current shm->mode == 1 code.

Terje

-- 
- <Terje at tmsw.no>
"almost all programming can be viewed as an exercise in caching"


More information about the hackers mailing list