Re: memory barriers (was: Yes, WaitLatch is vulnerable to weak-memory-ordering bugs)

On Wed, Sep 21, 2011 at 3:39 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:
> Robert Haas <robertmhaas@gmail.com> wrote:
>> On Wed, Sep 21, 2011 at 2:48 PM, Kevin Grittner
>> <Kevin.Grittner@wicourts.gov> wrote:
>>> Robert Haas <robertmhaas@gmail.com> wrote:
>>>> But even a full explanation of that case seems like almost too
>>>> much for the comment of a header file, and there are certainly
>>>> far more complex cases.  I think anyone who is using these
>>>> primitives is going to have to do some independent reading...
>>>
>>> Maybe a URL or two in the header comments, pointing to relevant
>>> papers for the techniques used?  After all, years from now
>>> someone might be familiar with other techniques from newer papers
>>> and wonder what the techniques in the code are based on.
>>
>> If there are any academic papers on this topic, I haven't found
>> them.  Mostly, I've found lots of articles written by people who
>> were coding for the Linux kernel, and a lot of those articles are
>> extremely Linux-specific (you could use the smb_rb() macro here,
>> but it's better to instead use this RCU-related macro, because
>> it'll do it for you, blah blah).  I'm happy to link to any sources
>> anyone thinks we ought to link to, but I've mostly had to piece
>> this together bit by bit from blog posts and (sometimes buggy)
>> examples.  It hasn't been a particularly thrilling exercise.
>
> Well, if it really is that hard to piece together the relevant
> techniques, it seems cruel not to check in the results of your
> efforts to work it out somewhere.  Perhaps a README file?

I don't know if techniques is the right word.  I mean, there are three
questions that you might want to answer here:

1. I have a new architecture and I want barrier.h to support it.  What
do I need to do?
2. What is the behavior of the various constructs provided by barrier.h?
3. Why would I want that behavior and how can I use it to do cool stuff?

I intended the comment in that file to be enough to answer questions
#1 and #2.  What you and Heikki are asking about is really #3, and
that seems to me to be setting the bar awfully high.  I mean, lwlock.c
explains what a lightweight lock does, but it doesn't explain all of
the ways that a lightweight lock can be used to solve performance
problems, nor should it.  That would be recapitulating the
documentation that is hopefully present everywhere that LWLocks are
used as well as speculating about future applications.  It just
doesn't seem sensible to me to try to enumerate all the ways that a
fundamental primitive can potentially be used down the line.

What I found hard about memory barriers is basically this: I didn't
understand that the CPU is allowed to perform operations out of order.And I couldn't understand what the consequences
ofthat fact were.  I 
sort of understood - but hadn't really internalized - the idea that
execution is highly pipelined, so the single moment at which an
execution is performed is not well defined.  Before I really got my
head around it, I had to read the explanations of what a memory
barrier actually does over and over again.  I probably read ten
different explanations saying the same thing in different words about
twenty times a piece, and slowly the light dawned.  I did my best to
explain that in the existing comment; I'm happy to expand the comment
if people have suggestions for what to put in there; but basically I
think this is a hard concept and if you haven't done this stuff before
it's going to take a while to get up to speed.

> On the other hand, a search turned up these two papers (which I
> haven't yet read, but will):
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.2397&rep=rep1&type=pdf
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153.6657&rep=rep1&type=pdf
>
> On a quick scan, they both look promising in themselves, and
> reference a lot of other promising-sounding papers.

I'm not sure these are much help for learning how to program with
memory barriers, but if somebody really wants them (or something else)
included, I'm not going to fight too hard.  I don't expect this to be
perfect the first time through; I am just trying to get a basic
infrastructure in place.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company