Re: [boost] [lockfree] Review

Subject: Re: [boost] [lockfree] Review
From: Helge Bahmann (hcb_at_[hidden])
Date: 2011-08-03 07:06:08

On Wednesday 03 August 2011 12:30:14 Grund, Holger wrote:
> > > I'm not really sure how you would implement a fully correct lock-free
> > > atomic<int128_t> on x64. A cmpxchg16b requires the underlying page to
> >
> > be
> >
> > > writable.
> >
> > if the page is not writable, then why would you need an
> > atomic<int128_t> in
> > the first place?
> >
> > - if the data is unchanging, then is doesn't matter
>
> Well as I understand the current wording requires this to work:
> const atomic<int128_t> x;
> void foo() { int128_t y = x; }

which is correct, but since "atomic" has a constructor, the variable wouldn't 
go into the rodata section anyway; even if it did, I do not see too many use 
cases for this (in case of shared mappings with one side being read-only you 
are strictly speaking already operating out-of-spec, but you don't need DCAS 
then in any case, see below).

> Surely, you wouldn't want to revert to a lock implementation just because
> of this rather academic case.
>
> > - if the data is changing (through a writable mapping by someone else
> > to the
> > page), then you have some sort of producer-/consumer-problem and that
> > is
> > trivialley solvable with word-sized atomic operations
>
> Really?

yes, really

keep an "even" and an "odd" copy of your data structure, keep an atomically 
readable "generation counter" -- on access, read the generation counter, read 
the data (depending on parity of generation counter), read the generation 
counter again

if it changed, start over. if it didn't change, you have your data; on 
modification, update generation counter as appropriate (if you are paranoid 
about counter overflows, you can repeat a similar trick with the counter 
itself)

no need for anything larger than word-sized atomics here, size of shared 
read-only data structure does not matter

> I don't think you want misaligned data with atomics -- ever. How would you
> ensure not to cross a cacheline or even a page?

you don't -- if an x86 processor detects the access to be misaligned, it will 
issue a bus lock instead of doing RMW in cache