Re: [HACKERS] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

On 2016-10-07 17:12:45 -0400, Tom Lane wrote:
> Andres Freund  writes:
> > It's not quite there yet, unfortunately. At the moment
> > pg_atomic_write_u32() is used for local buffers - and we explicitly
> > don't want that to be locking for temp buffers
> > (c.f. 6b93fcd149329d4ee7319561b30fc15a573c6307).
> 
> Hm.
> 
> > Don't really have a great idea about addressing this, besides either
> > just living with the lock for temp buffers on fallback platforms (which
> > don't have much of a practical relevance), or introduce
> > pg_atomic_unlocked_write_u32() or something. Neither seems great.
> 
> Maybe we could hack it with some macro magic that would cause
> pg_atomic_write_u32() to be expanded into a simple assignment in
> localbuf.c only?

I think it's just as well to add a variant that's globally documented to
have no locking, there might be further uses of it. It's already in two
files (bufmgr.c/localbuf.c), and I don't think it's impossible that
further usages will crop up.

Patch that I intend to push soon-ish attached.

Andres
>From b0779abb3add11d4dd745779dd81ea8ecdd00a1d Mon Sep 17 00:00:00 2001
From: Andres Freund 
Date: Fri, 7 Oct 2016 16:55:15 -0700
Subject: [PATCH] Fix fallback implementation of pg_atomic_write_u32().

I somehow had assumed that in the spinlock (in turn possibly using
semaphores) based fallback atomics implementation 32 bit writes could be
done without a lock. As far as the write goes that's correct, since
postgres supports only platforms with single-copy atomicity for aligned
32bit writes.  But writing without holding the spinlock breaks
read-modify-write operations like pg_atomic_compare_exchange_u32(),
since they'll potentially "miss" a concurrent write, which can't happen
in actual hardware implementations.

In 9.6+ when using the fallback atomics implementation this could lead
to buffer header locks not being properly marked as released, and
potentially some related state corruption.  I don't see a related danger
in 9.5 (earliest release with the API), because pg_atomic_write_u32()
wasn't used in a concurrent manner there.

The state variable of local buffers, before this change, were
manipulated using pg_atomic_write_u32(), to avoid unnecessary
synchronization overhead. As that'd not be the case anymore, introduce
and use pg_atomic_unlocked_write_u32(), which does not correctly
interact with RMW operations.

This bug only caused issues when postgres is compiled on platforms
without atomics support (i.e. no common new platform), or when compiled
with --disable-atomics, which explains why this wasn't noticed in
testing.

Reported-By: Tom Lane
Discussion: <14947.1475690...@sss.pgh.pa.us>
Backpatch: 9.5-, where the atomic operations API was introduced.
---
 src/backend/port/atomics.c| 13 +
 src/backend/storage/buffer/bufmgr.c   |  6 +++---
 src/backend/storage/buffer/localbuf.c | 16 
 src/include/port/atomics.h| 25 +++--
 src/include/port/atomics/fallback.h   |  3 +++
 src/include/port/atomics/generic.h|  9 +
 src/include/storage/buf_internals.h   |  3 ++-
 7 files changed, 61 insertions(+), 14 deletions(-)

diff --git a/src/backend/port/atomics.c b/src/backend/port/atomics.c
index 42169a3..d5970e4 100644
--- a/src/backend/port/atomics.c
+++ b/src/backend/port/atomics.c
@@ -104,6 +104,19 @@ pg_atomic_init_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val_)
 	ptr->value = val_;
 }
 
+void
+pg_atomic_write_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val)
+{
+	/*
+	 * One might think that an unlocked write doesn't need to acquire the
+	 * spinlock, but one would be wrong. Even an unlocked write has to cause a
+	 * concurrent pg_atomic_compare_exchange_u32() (et al) to fail.
+	 */
+	SpinLockAcquire((slock_t *) >sema);
+	ptr->value = val;
+	SpinLockRelease((slock_t *) >sema);
+}
+
 bool
 pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,
 	uint32 *expected, uint32 newval)
diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c
index 2b63cd3..df4c9d7 100644
--- a/src/backend/storage/buffer/bufmgr.c
+++ b/src/backend/storage/buffer/bufmgr.c
@@ -821,7 +821,7 @@ ReadBuffer_common(SMgrRelation smgr, char relpersistence, ForkNumber forkNum,
 
 			Assert(buf_state & BM_VALID);
 			buf_state &= ~BM_VALID;
-			pg_atomic_write_u32(>state, buf_state);
+			pg_atomic_unlocked_write_u32(>state, buf_state);
 		}
 		else
 		{
@@ -941,7 +941,7 @@ ReadBuffer_common(SMgrRelation smgr, char relpersistence, ForkNumber forkNum,
 		uint32		buf_state = pg_atomic_read_u32(>state);
 
 		buf_state |= BM_VALID;
-		pg_atomic_write_u32(>state, buf_state);
+		pg_atomic_unlocked_write_u32(>state, buf_state);
 	}
 	else
 	{
@@ -3167,7 +3167,7 @@ FlushRelationBuffers(Relation rel)
 		  false);
 
 buf_state &= ~(BM_DIRTY | BM_JUST_DIRTIED);
-pg_atomic_write_u32(>state, buf_state);
+

Re: [HACKERS] Our "fallback" atomics implementation doesn't actually work

[Tom Lane]

Andres Freund  writes:
> It's not quite there yet, unfortunately. At the moment
> pg_atomic_write_u32() is used for local buffers - and we explicitly
> don't want that to be locking for temp buffers
> (c.f. 6b93fcd149329d4ee7319561b30fc15a573c6307).

Hm.

> Don't really have a great idea about addressing this, besides either
> just living with the lock for temp buffers on fallback platforms (which
> don't have much of a practical relevance), or introduce
> pg_atomic_unlocked_write_u32() or something. Neither seems great.

Maybe we could hack it with some macro magic that would cause
pg_atomic_write_u32() to be expanded into a simple assignment in
localbuf.c only?

regards, tom lane


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

On 2016-10-06 00:06:33 -0400, Tom Lane wrote:
> Andres Freund  writes:
> > Hm. After a long battle of head vs. wall I think I see what the problem
> > is.  For the fallback atomics implementation I somehow had assumed that
> > pg_atomic_write_u32() doesn't need to lock, as it's just an unlocked
> > write.  But that's not true, because it has to cause
> > pg_atomic_compare_exchange_u32 to fail.
> 
> Hah ... obvious once you see it.
> 
> > For me the problem often takes a lot longer to reproduce (once only
> > after 40min), could you run with the attached patch, and see whether
> > that fixes things for you?
> 
> For me, with the described test case, HEAD fails within a minute,
> two times out of three or so.  I've not reproduced it after half an
> hour of beating on this patch.  Looks good.

It's not quite there yet, unfortunately. At the moment
pg_atomic_write_u32() is used for local buffers - and we explicitly
don't want that to be locking for temp buffers
(c.f. 6b93fcd149329d4ee7319561b30fc15a573c6307).

Don't really have a great idea about addressing this, besides either
just living with the lock for temp buffers on fallback platforms (which
don't have much of a practical relevance), or introduce
pg_atomic_unlocked_write_u32() or something. Neither seems great.

Regards,

Andres


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Tom Lane]

Andres Freund  writes:
> Hm. After a long battle of head vs. wall I think I see what the problem
> is.  For the fallback atomics implementation I somehow had assumed that
> pg_atomic_write_u32() doesn't need to lock, as it's just an unlocked
> write.  But that's not true, because it has to cause
> pg_atomic_compare_exchange_u32 to fail.

Hah ... obvious once you see it.

> For me the problem often takes a lot longer to reproduce (once only
> after 40min), could you run with the attached patch, and see whether
> that fixes things for you?

For me, with the described test case, HEAD fails within a minute,
two times out of three or so.  I've not reproduced it after half an
hour of beating on this patch.  Looks good.

regards, tom lane


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

On 2016-10-05 15:02:09 -0400, Tom Lane wrote:
> Andres Freund  writes:
> > Without yet having analyzed this deeply, could it actually be that the
> > reason is that sem_post/wait aren't proper memory barriers?  On a glance
> > the symptoms look like values have been modified without proper locks...
>
> Hmm, possible ...

Hm. After a long battle of head vs. wall I think I see what the problem
is.  For the fallback atomics implementation I somehow had assumed that
pg_atomic_write_u32() doesn't need to lock, as it's just an unlocked
write.  But that's not true, because it has to cause
pg_atomic_compare_exchange_u32 to fail.  The lack of this can cause a
"leftover" lockbit, when UnlockBufHdr() occurs concurrently an operation
using compare_exchange.

For me the problem often takes a lot longer to reproduce (once only
after 40min), could you run with the attached patch, and see whether
that fixes things for you?

Andres
diff --git a/src/backend/port/atomics.c b/src/backend/port/atomics.c
index 42169a3..aa649b7 100644
--- a/src/backend/port/atomics.c
+++ b/src/backend/port/atomics.c
@@ -104,6 +104,19 @@ pg_atomic_init_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val_)
 	ptr->value = val_;
 }
 
+void
+pg_atomic_write_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val)
+{
+	/*
+	 * One might think that an unlocked write doesn't need a lock, but one
+	 * would be wrong. Even an unlocked write has to cause
+	 * pg_atomic_compare_exchange_u32() (et al) to fail.
+	 */
+	SpinLockAcquire((slock_t *) >sema);
+	ptr->value = val;
+	SpinLockRelease((slock_t *) >sema);
+}
+
 bool
 pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,
 	uint32 *expected, uint32 newval)
diff --git a/src/include/port/atomics/fallback.h b/src/include/port/atomics/fallback.h
index bdaa795..2290fff 100644
--- a/src/include/port/atomics/fallback.h
+++ b/src/include/port/atomics/fallback.h
@@ -133,6 +133,9 @@ pg_atomic_unlocked_test_flag_impl(volatile pg_atomic_flag *ptr)
 #define PG_HAVE_ATOMIC_INIT_U32
 extern void pg_atomic_init_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val_);
 
+#define PG_HAVE_ATOMIC_WRITE_U32
+extern void pg_atomic_write_u32_impl(volatile pg_atomic_uint32 *ptr, uint32 val);
+
 #define PG_HAVE_ATOMIC_COMPARE_EXCHANGE_U32
 extern bool pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,
 uint32 *expected, uint32 newval);

-- 
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] Our "fallback" atomics implementation doesn't actually work

[Tom Lane]

Andres Freund  writes:
> Without yet having analyzed this deeply, could it actually be that the
> reason is that sem_post/wait aren't proper memory barriers?  On a glance
> the symptoms look like values have been modified without proper locks...

Hmm, possible ...

regards, tom lane


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

Hi,

I was able to reproduce it in a read-write workload, instead of the
read-only workload you'd proposed.

On 2016-10-05 14:01:05 -0400, Tom Lane wrote:
> Curiously, I did not see such a hang with regular SysV semaphores.
> That may be just a timing thing, or it may have something to do with
> POSIX semaphores being actually futexes on this platform (so that there
> is state inside the process not outside it).

Without yet having analyzed this deeply, could it actually be that the
reason is that sem_post/wait aren't proper memory barriers?  On a glance
the symptoms look like values have been modified without proper locks...

Greetings,

Andres Freund


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Tom Lane]

Andres Freund  writes:
> On 2016-10-05 14:01:05 -0400, Tom Lane wrote:
>> configure USE_UNNAMED_POSIX_SEMAPHORES=1 --disable-cassert 
>> --disable-spinlocks --disable-atomics

> Pretty independent from the complaint at hand, but if I just do that I get
> undefined reference to symbol 'sem_post@@GLIBC_2.2.5'

> I needed to add -pthread -lrt to LDFLAGS to make it work.

Yeah, on my machine man sem_init specifies "Link with -lrt or -pthread".
But I see -lrt getting added into the backend link anyway, presumably
as a result of one of these configure calls:

AC_SEARCH_LIBS(shm_open, rt)
AC_SEARCH_LIBS(shm_unlink, rt)
AC_SEARCH_LIBS(sched_yield, rt)

If we were to try to support USE_UNNAMED_POSIX_SEMAPHORES as default
(which is where I'm thinking about going) we'd have to tweak configure
to check sem_init similarly.

regards, tom lane


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Tom Lane]

Andres Freund  writes:
> On 2016-10-05 14:01:05 -0400, Tom Lane wrote:
>> I think what is happening is that there are circular assumptions that end
>> up trying to implement a spinlock in terms of a spinlock, or otherwise
>> somehow recursively use the process's semaphore.  It's a bit hard to tell
>> though because the atomics code is such an underdocumented rat's nest of
>> #ifdefs.

> I don't think that should be the case, but I'll look into it.  How long
> did it take for you to reproduce the issue?

It hangs up within 10 or 20 seconds for me.  I didn't try hard to get a
census of where, but at least some of the callers are trying to acquire
buffer partition locks.

regards, tom lane


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

On 2016-10-05 14:01:05 -0400, Tom Lane wrote:
> I was trying to measure whether unnamed POSIX semaphores are any faster
> or slower than the SysV kind.  Plain pgbench is not very helpful for
> determining this, because we've optimized the system to the point that
> you don't hit semop waits all that often.  So I tried this:
> 
> configure USE_UNNAMED_POSIX_SEMAPHORES=1 --disable-cassert 
> --disable-spinlocks --disable-atomics

Pretty independent from the complaint at hand, but if I just do that I get
undefined reference to symbol 'sem_post@@GLIBC_2.2.5'

I needed to add -pthread -lrt to LDFLAGS to make it work.

Andres


-- 
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] Our "fallback" atomics implementation doesn't actually work

[Andres Freund]

Hi,

On 2016-10-05 14:01:05 -0400, Tom Lane wrote:
> I think what is happening is that there are circular assumptions that end
> up trying to implement a spinlock in terms of a spinlock, or otherwise
> somehow recursively use the process's semaphore.  It's a bit hard to tell
> though because the atomics code is such an underdocumented rat's nest of
> #ifdefs.

I don't think that should be the case, but I'll look into it.  How long
did it take for you to reproduce the issue?

Greetings,

Andres Freund


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