Re: Spinlocks and compiler/memory barriers

On Thu, Jun 26, 2014 at 5:01 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> But a) isn't really avoidable because it'll otherwise generate compiler
> warnings and b) is done that way all over the tree. E.g. lwlock.c has
> several copies of (note the nonvolatility of proc):
> volatile LWLock *lock = l;
> PGPROC *proc = MyProc;
> ...
> proc->lwWaiting = true;
> proc->lwWaitMode = LW_WAIT_UNTIL_FREE;
> proc->lwWaitLink = NULL;
>
> /* waiters are added to the front of the queue */
> proc->lwWaitLink = lock->head;
> if (lock->head == NULL)
> lock->tail = proc;
> lock->head = proc;
>
> /* Can release the mutex now */
> SpinLockRelease(&lock->mutex);
> There's nothing forcing the compiler to not move any of the proc->*
> assignments past the SpinLockRelease(). And indeed in my case it was
> actually the store to lwWaitLink that was moved across the lock.
>
> I think it's just pure luck that there's no active bug (that we know of)
> caused by this. I wouldn't be surprised if some dubious behaviour we've
> seen would be caused by similar issues.
>
> Now, we can fix this and similar cases by more gratuitous use of
> volatile. But for one we're never going to find all cases. For another
> it won't help *at all* for architectures with looser CPU level memory
> ordering guarantees.
> I think we finally need to bite the bullet and make all S_UNLOCKs
> compiler/write barriers.

There are two separate issues here:

1. SpinLockAcquire and SpinLockRelease are not guaranteed to be
compiler barriers, so all relevant memory accesses in the critical
section need to be done using volatile pointers. Failing to do this
is an easy mistake to make, and we've fixed numerous bugs of this type
over the years (most recently, to my knowledge, in
4bc15a8bfbc7856bc3426dc9ab99567eebbb64d3). Forcing SpinLockAcquire()
and SpinLockRelease() to serve as compiler barriers would let us
dispense with a whole lot of volatile calls and make writing future
code correctly a lot easier.

2. Some of our implementations of SpinLockAcquire and/or
SpinLockRelease, but in particular SpinLockRelease, may not actually
provide the memory-ordering semantics which they are required to
provide. In particular, ...

> I'd previously, in
> http://www.postgresql.org/message-id/20130920151110.GA8508@awork2.anarazel.de,
> gone through the list of S_UNLOCKs and found several that were
> lacking. Most prominently the default S_UNLOCK is just
> #define S_UNLOCK(lock) (*((volatile slock_t *) (lock)) = 0)
> which allows the compiler to move non volatile access across and does
> nothing for CPU level cache coherency.

...this default implementation of S_UNLOCK() is pretty sketchy. Even
on a platform that enforces reads in program order and writes in
program order, this is still unsafe because a read within the critical
section might get postponed until after this write. Now, x86 happens
to have an additional constraint, which is that it can reorder loads
before stores but not stores before loads; so that coding happens to
provide release semantics. But that need not be true on every
architecture, and the trend seems to be toward weaker memory ordering.
As you pointed out to me on chat, the non-intrinsics based ARM
implementation brokenly relies on the default S_UNLOCK(), which
clearly isn't adequate.

Now, in terms of solving these problems:

I tend to think that we should try to think about these two problems
somewhat separately. As to #1, in the back-branches, I think further
volatile-izing the LWLock* routines is probably the only realistic
solution. In master, I fully support moving the goalposts such that
we require SpinLockAcquire() and SpinLockRelease() are compiler
barriers. Once we do this, I think we should go back and rip out all
the places where we've used volatile-ized pointers to provide compiler
ordering. That way, if we haven't actually managed to provide
compiler ordering everywhere, it's more likely that something will
fall over and warn us about the problem; plus, that avoids keeping
around a coding pattern which isn't actually the one we want people to
copy. However, I think your proposed S_UNLOCKED_UNLOCK() hack is
plain ugly, probably cripplingly slow, and there's no guarantee that's
even correct; see for example the comments about Itanium's tas
implementation possibly being only an acquire barrier (blech).

On gcc and icc, which account for lines 99 through 700 of spin.h, it
should be simple and mechanical to use compiler intrinsics to make
sure that every S_UNLOCK implementation includes a compiler barrier.
However, lines 710 through 895 support non-gcc, non-icc compilers, and
some of those we may not know how to implement a compiler barrier - in
particular, Univel CC, the Tru64 Alpha compiler, HPPA, AIX, or Sun's
compilers. Except for Sun, we have no buildfarm support for those
platforms, so we could consider just dropping support entirely, but
I'd be inclined to do something cheesy and hope it works:

void fake_compiler_barrier(void) { }
void (*fake_compiler_barrier_hook) = fake_compiler_barrier;
#define pg_compiler_barrier() ((*fake_compiler_barrier_hook)())

Now, this doesn't remove the circular dependency between s_lock.h and
barrier.h, because we still don't have a fallback method, other than
acquiring and releasing a spinlock, of implementing a barrier that
blocks both compiler reordering and CPU reordering. But it is enough
to solve problem #1, and doesn't require that we drop support for
anything that works now.

A more radical step would be simply desupport those architectures
instead of trying to create a fake compiler barrier for them. It
would be worth it to me to drop support for Univel CC, Alpha, and HPPA
to get this problem fixed, but we might have to do something about
AIX, and I'm sure we'd have to do something about Sun Studio.

Now, #2 is a different problem. I'm not sure there's a better option
than fixing whatever bugs exist there on a case-by-case basis.

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