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

On Thu, Sep 22, 2011 at 10:45 PM, Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> +    for (i = 0; i < num_items; ++i)
> +        /* do something with q->items[i] */
> +
> +This code turns out to be unsafe, because the writer might increment
> +q->num_items before it finishes storing the new item into the
> appropriate slot.
> +More subtly, the reader might prefetch the contents of the q->items
> array
> +before reading q->num_items.
>
> How would the reader prefetch the contents of the items array, without
> knowing how big it is?

I don't think this is as mysterious as it sounds. Imagine the compiler
unrolled the loop so that it does something like

fetch num_items into register
if register > 0 fetch q[0], process it
if register > 1 fetch q[1], process it
...

Then the cpu could easily do branch prediction on the ifs and fetch
q[0] while the fetch of num_items was still in progress. If it turns
out that num_items is 0 then it would invalidate the operations
initiated after the branch prediction but if it sees 1 (ie after the
increment in the other process) then it's not so it doesn't.

So you have two memory fetches which I guess I still imagine have to
be initiated in the right order but they're both in flight at the same
time. I have no idea how the memory controller works and I could
easily imagine either one grabbing the value before the other.

I'm not even clear how other processors can reasonably avoid this. It
must be fantastically expensive to keep track of which branch
predictions depended on which registers and which memory fetches the
value of those registers depended on. And then it would have to
somehow inform the memory controller of those old memory fetches that
this new memory fetch is dependent on and have it ensure that the
fetches are read the right order?

--
greg