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

2011-09-24 Thread Martijn van Oosterhout
On Fri, Sep 23, 2011 at 04:22:09PM +0100, Greg Stark wrote:
 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.

That's easy. If one is in cache and the other isn't then the results
will come back out of order.

 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?

I think memory accesses are also fantastically expensive, so it's worth
some effort to optimise that.

I found the Linux kernel document on this topic quite readable. I think
the main lesson here is that processors track data dependancies (other
than the Alpha apparently), but not control dependancies.  So in the
example, the value of i is dependant on num_items, but not via any
calculation.  IThat control dependancies are not tracked makes some
sense, since branches depend on flags bit, and just about any
calculation changes the flag bits, but most of the time these changes
are not used.

It also not a question of the knowing the address either, since the
first load, if any, will be *q-items, irrespective of the precise
value of num_items.  This address may be calculated long in advance.

Have a nice day,
-- 
Martijn van Oosterhout   klep...@svana.org   http://svana.org/kleptog/
 He who writes carelessly confesses thereby at the very outset that he does
 not attach much importance to his own thoughts.
   -- Arthur Schopenhauer


signature.asc
Description: Digital signature


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

2011-09-24 Thread Robert Haas
On Sat, Sep 24, 2011 at 9:45 AM, Martijn van Oosterhout
klep...@svana.org wrote:
 I think memory accesses are also fantastically expensive, so it's worth
 some effort to optimise that.

This is definitely true.

 I found the Linux kernel document on this topic quite readable. I think
 the main lesson here is that processors track data dependancies (other
 than the Alpha apparently), but not control dependancies.  So in the
 example, the value of i is dependant on num_items, but not via any
 calculation.  IThat control dependancies are not tracked makes some
 sense, since branches depend on flags bit, and just about any
 calculation changes the flag bits, but most of the time these changes
 are not used.

Oh, that's interesting.  So that implies that a read-barrier would be
needed here even on non-Alpha.

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

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


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

2011-09-24 Thread Martijn van Oosterhout
On Sat, Sep 24, 2011 at 12:46:48PM -0400, Robert Haas wrote:
  I found the Linux kernel document on this topic quite readable. I think
  the main lesson here is that processors track data dependancies (other
  than the Alpha apparently), but not control dependancies.  So in the
  example, the value of i is dependant on num_items, but not via any
  calculation.  IThat control dependancies are not tracked makes some
  sense, since branches depend on flags bit, and just about any
  calculation changes the flag bits, but most of the time these changes
  are not used.
 
 Oh, that's interesting.  So that implies that a read-barrier would be
 needed here even on non-Alpha.

That is my understanding. At source code level the address being
referenced is dependant on i, but at assembly level it's possible i has
been optimised away altogether.

I think the relevent example is here:
http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt (line 725)

Where A = q-items[0] and B = q-num_items.

There is no data dependancy here, so inserting such a barrier won't
help. You need a normal read barrier.

OTOH, if the list already has an entry in it, the problem (probably)
goes away, although with loop unrolling you can't really be sure.

Have a nice day,
-- 
Martijn van Oosterhout   klep...@svana.org   http://svana.org/kleptog/
 He who writes carelessly confesses thereby at the very outset that he does
 not attach much importance to his own thoughts.
   -- Arthur Schopenhauer


signature.asc
Description: Digital signature


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

2011-09-23 Thread Greg Stark
On Thu, Sep 22, 2011 at 10:45 PM, Jeff Davis pg...@j-davis.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

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers