[ntp:hackers] [Gpsd-dev] Single-writer/many-reader consistency

Terje Mathisen terje at tmsw.no
Sat Mar 26 21:49:14 UTC 2011

Dave Hart wrote:
> On Sat, Mar 26, 2011 at 7:36 PM, Eric Raymond<esr at thyrsus.com>  wrote:
>> It's the same painful tradeoff that tz and I and other discussants
>> have been grappling with for the last week in one way or another. Â The
>> methods that provably prevent corrupt data have nasty blocking failure
>> modes; the methods that don't have scary worst-case behavior may
>> produce intermittent data corruption in the *normal* case if the underlying
>> hardware messes with operation order enough.
>> I am by no means sure I know where to land. Â I have working seqlocks
>> now and am oscillating back and forth about whether to scrap that and go
>> with semaphores. Â I was almost ready to do it until two things happened:
>> (a) tz pointed out correctly that in a semaphore-based approach, readers
>> have to assert as well as writers - otherwise writer can start an update while
>> reader is still reading.
>> (b) I then realized that under a correct semaphore implementation,
>> anybody dying while semaphore is asserted starves everybody else
>> (which we should have remembered from Operating Systems 101). Â This is
>> a very practical problem because while we haven't had a crash bug in
>> gpsd since something like 2005, I can't say the same thing about all
>> the clients out there!
> Thanks for your clear summary of the dilemma.
>> This is pushing me back towards sticking with the working seqlock.
>> But *that* means I have to either deal with the pile of nonportable
>> hair that is memory barriers or expensively checksum the data.
> If you do checksum, ISTR CRC32 isn't terribly strong for 8k.  MD5 is
> widely-available and reasonably fast, and for this purpose, I beieve
> its cryptographic weakness is any reason to avoid it.
>> Yes, I've been listening to Terje too. Â The problem is that his proposal
>> is complicated enough to make my head hurt - and I plain don't trust
>> complicated algorithms in cases like this, they tend to have holes
>> where nobody is looking and be difficult to *maintain* correctness of
>> even if they started out correct.
> The cost of 4 payload copies is trivial for refclock_shm.c, and CRC32
> is more than sufficient to detect corruption and could be layered in
> for belt-and-suspenders detection of problems with the lock-free ring
> buffer approach.  The tradeoffs for gpsd are different.
> Personally, my head isn't hurting thinking about the approach Terje
> describes for refclock_shm.  I have used similar approaches for
> producer/consumer lockless queueing repeatedly in the past.  That was
> usually solving a slightly different problem, with a single or several
> consumers that dequeue items, but it's easier with a more
> broadcast-like arrangement of single writer, multiple readers who
> never change shared memory, only examine.

I started writing hw interrupt drivers in 1982, at that time I had to 
"compile" them in DEBUG.EXE, then embed the resulting hex bytes in my 
Modula2 source code. :-)

I got the idea for a 32-bit counter that is used to index into a small 
power-of-two array from work I've been discussing in UseNet, on comp.arch:

Using a locked fetch_and_adds (XADD on x86) makes it possible to have 
multiple writers and multiple readers, and as long as the buffer size is 
larger than the number of readers/writers, you can setup a queue where 
nobody ever has to spin, where a hung reader or writer will only affect 
the single entry being read/written by that process, and as long as the 
queue is neither full nor empty, no process ever has to go to sleep.

(BTW, XADD [ebx],eax will fetch the current value in [EBX] and return it 
in EAX, while [EBX] ends up being incremented by the incoming value in 
EAX. I.e. with EAX = 1 you increment the memory counter.)

AFAIR we came up with a total of 6 separate counters needed (write ptr, 
read ptr, valid entries, free entries plus two more which I don't recall 
just now but were needed to guard against special failure modes...

What we have here in shm with a single writer and one or multiple shared 
readers is much, much simpler.

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

More information about the hackers mailing list