Horton

Thread

Commits

  1. Add WL_EXIT_ON_PM_DEATH pseudo-event.

  2. While waiting for a condition variable, detect postmaster death.

  3. Fix race condition during replication origin drop.

  4. Allow ConditionVariable[PrepareTo]Sleep to auto-switch between CVs.

  5. Cosmetic improvements in condition_variable.[hc].

  6. Improve error detection capability in proclists.

  7. Remove return values of ConditionVariableSignal/Broadcast.

  8. Reorder steps in ConditionVariablePrepareToSleep for more safety.

  9. Rewrite ConditionVariableBroadcast() to avoid live-lock.

  10. Add parallel-aware hash joins.

  1. Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2017-12-22T03:46:21Z

    Hi hackers,

While debugging a build farm assertion failure after commit 18042840,
and with the assumption that the problem is timing/scheduling
sensitive, I tried hammering the problem workload on a few different
machines and noticed that my slow 2-core test machine fairly regularly
got into a live lock state for tens to millions of milliseconds at a
time when there were 3+ active processes, in here:

int
ConditionVariableBroadcast(ConditionVariable *cv)
{
        int                     nwoken = 0;

        /*
         * Let's just do this the dumbest way possible.  We could try to dequeue
         * all the sleepers at once to save spinlock cycles, but it's a bit hard
         * to get that right in the face of possible sleep cancelations, and we
         * don't want to loop holding the mutex.
         */
        while (ConditionVariableSignal(cv))
                ++nwoken;

        return nwoken;
}

The problem is that another backend can be woken up, determine that it
would like to wait for the condition variable again, and then get
itself added to the back of the wait queue *before the above loop has
finished*, so this interprocess ping-pong isn't guaranteed to
terminate.  It seems that we'll need something slightly smarter than
the above to avoid that.

I don't currently suspect this phenomenon of being responsible for the
problem I'm hunting, even though it occurs on the only machine I've
been able to reproduce my real problem on.  AFAICT the problem
described in this email should deliver arbitrary numbers of spurious
wake-ups wasting arbitrary CPU time but cause no harm that would
affect program correctness.  So I didn't try to write a patch to fix
that just yet.  I think we should probably back patch a fix when we
have one though, because it could bite Parallel Index Scan in
REL_10_STABLE.

-- 
Thomas Munro
http://www.enterprisedb.com

  2. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2017-12-28T23:16:20Z

    On Fri, Dec 22, 2017 at 4:46 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
>         while (ConditionVariableSignal(cv))
>                 ++nwoken;
>
> The problem is that another backend can be woken up, determine that it
> would like to wait for the condition variable again, and then get
> itself added to the back of the wait queue *before the above loop has
> finished*, so this interprocess ping-pong isn't guaranteed to
> terminate.  It seems that we'll need something slightly smarter than
> the above to avoid that.

Here is one way to fix it: track the wait queue size and use that
number to limit the wakeup loop.  See attached.

That's unbackpatchable though, because it changes the size of struct
ConditionVariable, potentially breaking extensions compiled against an
earlier point release.  Maybe this problem won't really cause problems
in v10 anyway?  It requires a particular interaction pattern that
barrier.c produces but more typical client code might not: the awoken
backends keep re-adding themselves because they're waiting for
everyone (including the waker) to do something, but the waker is stuck
in that broadcast loop.

Thoughts?

-- 
Thomas Munro
http://www.enterprisedb.com

  3. Re: Condition variable live lock

    Andres Freund <andres@anarazel.de> — 2017-12-29T19:38:43Z

    On 2017-12-29 12:16:20 +1300, Thomas Munro wrote:
> Here is one way to fix it: track the wait queue size and use that
> number to limit the wakeup loop.  See attached.
>
> That's unbackpatchable though, because it changes the size of struct
> ConditionVariable, potentially breaking extensions compiled against an
> earlier point release.  Maybe this problem won't really cause problems
> in v10 anyway?  It requires a particular interaction pattern that
> barrier.c produces but more typical client code might not: the awoken
> backends keep re-adding themselves because they're waiting for
> everyone (including the waker) to do something, but the waker is stuck
> in that broadcast loop.

Hm, I'm not quite convinced by this approach. Partially because of the
backpatch issue you mention, partially because using the list length as
a limit doesn't seem quite nice.

Given that the proclist_contains() checks in condition_variable.c are
already racy, I think it might be feasible to collect all procnos to
signal while holding the spinlock, and then signal all of them in one
go.

Obviously it'd be nicer to not hold a spinlock while looping, but that
seems like something we can't fix in the back branches. [insert rant
about never using spinlocks unless there's very very clear convicing
reasons].

- Andres

  4. Re: Condition variable live lock

    Robert Haas <robertmhaas@gmail.com> — 2018-01-04T17:39:47Z

    On Fri, Dec 29, 2017 at 2:38 PM, Andres Freund <andres@anarazel.de> wrote:
> Hm, I'm not quite convinced by this approach. Partially because of the
> backpatch issue you mention, partially because using the list length as
> a limit doesn't seem quite nice.

Seems OK to me.  Certainly better than your competing proposal.

> Given that the proclist_contains() checks in condition_variable.c are
> already racy, I think it might be feasible to collect all procnos to
> signal while holding the spinlock, and then signal all of them in one
> go.

That doesn't seem very nice at all.  Not only does it violate the
coding rule against looping while holding a spinlock, but it seems
that it would require allocating memory while holding one, which is a
non-starter.

> Obviously it'd be nicer to not hold a spinlock while looping, but that
> seems like something we can't fix in the back branches. [insert rant
> about never using spinlocks unless there's very very clear convicing
> reasons].

I don't think that's a coding rule that I'd be prepared to endorse.
We've routinely used spinlocks for years in cases where the critical
section was very short, just to keep the overhead down.  I think it
works fine in that case, although I admit that I failed to appreciate
how unpleasant the livelock possibilities were in this case.

It's not clear to me that we entirely need a back-patchable fix for
this.  It could be that parallel index scan can have the same issue,
but I'm not aware of any user complaints.  Parallel bitmap heap only
ever waits once so it's probably fine.  If we do need a back-patchable
fix, I suppose slock_t mutex could be replaced by pg_atomic_uint32
state.  I think that would avoid changing the size of the structure on
common platforms, though obscure systems with spinlocks > 4 bytes
might be affected.

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

  5. Re: Condition variable live lock

    Andres Freund <andres@anarazel.de> — 2018-01-04T20:54:47Z

    On 2018-01-04 12:39:47 -0500, Robert Haas wrote:
> > Given that the proclist_contains() checks in condition_variable.c are
> > already racy, I think it might be feasible to collect all procnos to
> > signal while holding the spinlock, and then signal all of them in one
> > go.
> 
> That doesn't seem very nice at all.  Not only does it violate the
> coding rule against looping while holding a spinlock, but it seems
> that it would require allocating memory while holding one, which is a
> non-starter.

We could just use a sufficiently sized buffer beforehand. There's an
obvious upper boundary, so that shouldn't be a big issue.


> > Obviously it'd be nicer to not hold a spinlock while looping, but that
> > seems like something we can't fix in the back branches. [insert rant
> > about never using spinlocks unless there's very very clear convicing
> > reasons].
> 
> I don't think that's a coding rule that I'd be prepared to endorse.
> We've routinely used spinlocks for years in cases where the critical
> section was very short, just to keep the overhead down.

The problem is that due to the contention handling they really don't
keep the overhead that low unless you're absolutely absolutely
maximizing for low number of cycles and have very little
contention. Which isn't actually common.  I think part of the
conventional wisdom when to use spinlock vs lwlocks went out of the
window once we got better scaling lwlocks.


> It's not clear to me that we entirely need a back-patchable fix for
> this.  It could be that parallel index scan can have the same issue,
> but I'm not aware of any user complaints.

I don't think many users are going to be able to diagnose this one, and
it's probably not easily diagnosable even if they complain about
performance.

Greetings,

Andres Freund

  6. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T04:27:09Z

    Andres Freund <andres@anarazel.de> writes:
> On 2018-01-04 12:39:47 -0500, Robert Haas wrote:
>>> Given that the proclist_contains() checks in condition_variable.c are
>>> already racy, I think it might be feasible to collect all procnos to
>>> signal while holding the spinlock, and then signal all of them in one
>>> go.

>> That doesn't seem very nice at all.  Not only does it violate the
>> coding rule against looping while holding a spinlock, but it seems
>> that it would require allocating memory while holding one, which is a
>> non-starter.

> We could just use a sufficiently sized buffer beforehand. There's an
> obvious upper boundary, so that shouldn't be a big issue.

I share Robert's discomfort with that solution, but it seems to me there
might be a better way.  The attached patch uses our own cvWaitLink as a
sentinel to detect when we've woken everybody who was on the wait list
before we arrived.  That gives exactly the desired semantics, not just an
approximation to them.

Now, the limitation with this is that we can't be waiting for any *other*
condition variable, because then we'd be trashing our state about that
variable.  As coded, we can't be waiting for the target CV either, but
that case could actually be handled if we needed to, as per the comment.
I do not know if this is likely to be a problematic limitation
... discuss.  (The patch does survive check-world, FWIW.)

			regards, tom lane

  7. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-05T05:47:54Z

    On Fri, Jan 5, 2018 at 5:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I share Robert's discomfort with that solution, but it seems to me there
> might be a better way.  The attached patch uses our own cvWaitLink as a
> sentinel to detect when we've woken everybody who was on the wait list
> before we arrived.  That gives exactly the desired semantics, not just an
> approximation to them.

Very clever.  It works correctly for my test case.

> Now, the limitation with this is that we can't be waiting for any *other*
> condition variable, because then we'd be trashing our state about that
> variable.  As coded, we can't be waiting for the target CV either, but
> that case could actually be handled if we needed to, as per the comment.
> I do not know if this is likely to be a problematic limitation
> ... discuss.  (The patch does survive check-world, FWIW.)

I think that restriction is probably OK.  Even if you have some kind
of chain of CVs where you get woken up, check your interesting
condition and discover that it's now true so you exit you loop and
immediately want to broadcast a signal to some other CV, you'd simply
have to make sure that you put ConditionVariableCancelSleep() before
ConditionVariableBroadcast():

   ConditionVariablePrepareToSleep(cv1);
   while (condition for which we are waiting is not true)
       ConditionVariableSleep(cv1, wait_event_info);
   ConditionVariableCancelSleep();
   ConditionVariableBroadcast(cv2);

It would only be a problem if you are interested in broadcasting to
cv2 when you've been woken up and the condition is *still not true*,
that is, when you've been spuriously woken.  But why would anyone want
to forward spurious wakeups to another CV?

But if that seems too arbitrary, one way to lift the restriction would
be to teach ConditionVariableBroadcast() to call
ConditionVariableCancelSleep() if cv_sleep_target is non-NULL where
you have the current assertion.  Code that is still waiting for a CV
must be in a loop that will eventually re-add it in
ConditionVariableSleep(), and it won't miss any signals that it can't
afford to miss because the first call to ConditionVariableSleep() will
return immediately so the caller will recheck its condition.

-- 
Thomas Munro
http://www.enterprisedb.com

  8. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T06:10:57Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Fri, Jan 5, 2018 at 5:27 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Now, the limitation with this is that we can't be waiting for any *other*
>> condition variable, because then we'd be trashing our state about that
>> variable.  As coded, we can't be waiting for the target CV either, but
>> that case could actually be handled if we needed to, as per the comment.
>> I do not know if this is likely to be a problematic limitation
>> ... discuss.  (The patch does survive check-world, FWIW.)

> ... one way to lift the restriction would
> be to teach ConditionVariableBroadcast() to call
> ConditionVariableCancelSleep() if cv_sleep_target is non-NULL where
> you have the current assertion.  Code that is still waiting for a CV
> must be in a loop that will eventually re-add it in
> ConditionVariableSleep(), and it won't miss any signals that it can't
> afford to miss because the first call to ConditionVariableSleep() will
> return immediately so the caller will recheck its condition.

Oh, of course, very simple.

I thought of another possible issue, though.  In the situation where
someone else has removed our sentinel (presumably, by issuing
ConditionVariableSignal just before we were about to remove the
sentinel), my patch assumes we can just do nothing.  But it seems
like that amounts to losing one signal.  Whoever the someone else
was probably expected to awaken a waiter, and now that won't happen.
Should we rejigger the logic so that it awakens one additional waiter
(if there is one) after detecting that someone else has removed the
sentinel?  Obviously, this trades a risk of loss of wakeup for a risk
of spurious wakeup, but presumably the latter is something we can
cope with.

			regards, tom lane

  9. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-05T06:33:10Z

    On Fri, Jan 5, 2018 at 7:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I thought of another possible issue, though.  In the situation where
> someone else has removed our sentinel (presumably, by issuing
> ConditionVariableSignal just before we were about to remove the
> sentinel), my patch assumes we can just do nothing.  But it seems
> like that amounts to losing one signal.  Whoever the someone else
> was probably expected to awaken a waiter, and now that won't happen.

Yeah, that's bad.

> Should we rejigger the logic so that it awakens one additional waiter
> (if there is one) after detecting that someone else has removed the
> sentinel?  Obviously, this trades a risk of loss of wakeup for a risk
> of spurious wakeup, but presumably the latter is something we can
> cope with.

One detail is that the caller of ConditionVariableSignal() got a true
return value when it took out the sentinel (indicating that someone
received the signal), and now when you call ConditionVariableSignal()
because !aminlist there may be no one there.  I'm not sure if that's a
problem.  For comparison, pthread_cond_signal() doesn't tell you if
you actually signalled anyone.  Maybe the only reason we have that
return code is so that ConditionVariableBroadcast() can use it the way
it does in master...

An alternative would be to mark sentinel entries somehow so that
signallers can detect them and signal again, but that's not
backpatchable.

-- 
Thomas Munro
http://www.enterprisedb.com

  10. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T06:42:55Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Fri, Jan 5, 2018 at 7:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Should we rejigger the logic so that it awakens one additional waiter
>> (if there is one) after detecting that someone else has removed the
>> sentinel?  Obviously, this trades a risk of loss of wakeup for a risk
>> of spurious wakeup, but presumably the latter is something we can
>> cope with.

> One detail is that the caller of ConditionVariableSignal() got a true
> return value when it took out the sentinel (indicating that someone
> received the signal), and now when you call ConditionVariableSignal()
> because !aminlist there may be no one there.  I'm not sure if that's a
> problem.  For comparison, pthread_cond_signal() doesn't tell you if
> you actually signalled anyone.  Maybe the only reason we have that
> return code is so that ConditionVariableBroadcast() can use it the way
> it does in master...

Indeed, it looks like no other caller is paying attention to the result.
We could live with the uncertainty in the back branches, and redefine
ConditionVariableSignal as returning void in master.

			regards, tom lane

  11. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-05T10:14:25Z

    On Fri, Jan 5, 2018 at 7:42 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Indeed, it looks like no other caller is paying attention to the result.
> We could live with the uncertainty in the back branches, and redefine
> ConditionVariableSignal as returning void in master.

+1

Could we install the sentinel and pop the first entry at the same
time, so that we're not adding an extra spinlock acquire/release?

-- 
Thomas Munro
http://www.enterprisedb.com

  12. Re: Condition variable live lock

    Alvaro Herrera <alvherre@alvh.no-ip.org> — 2018-01-05T12:05:42Z

    Tom Lane wrote:

> Obviously, this trades a risk of loss of wakeup for a risk
> of spurious wakeup, but presumably the latter is something we can
> cope with.

I wonder if it'd be useful to have a test mode for condition variables
that spurious wakups happen randomly, to verify that every user is
prepared to cope correctly.

-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  13. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T15:28:10Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> Could we install the sentinel and pop the first entry at the same
> time, so that we're not adding an extra spinlock acquire/release?

Hm, maybe.  Other ideas in that space:

* if queue is empty when we first acquire the spinlock, we don't
have to do anything at all.

* if queue is empty after we pop the first entry, we needn't bother
installing our sentinel, just signal that proc and we're done.

It's a question of how complicated you're willing to make this
logic, and whether you trust that we'll be able to test all the
code paths.

			regards, tom lane

  14. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T17:33:13Z

    I wrote:
> It's a question of how complicated you're willing to make this
> logic, and whether you trust that we'll be able to test all the
> code paths.

Attached is a patch incorporating all the ideas mentioned in this thread,
except that I think in HEAD we should change both ConditionVariableSignal
and ConditionVariableBroadcast to return void rather than a possibly
misleading wakeup count.  This could be back-patched as is, though.

As I feared, the existing regression tests are not really adequate for
this: gcov testing shows that the sentinel-inserting code path is
never entered, meaning ConditionVariableBroadcast never sees more
than one waiter.  What's more, it's now also apparent that no outside
caller of ConditionVariableSignal ever actually awakens anything.
So I think it'd be a good idea to expand the regression tests if we
can do so cheaply.  Anybody have ideas about that?  Perhaps a new
module under src/test/modules would be the best way?  Alternatively,
we could drop some of the optimization ideas.

BTW, at least on gaur, this does nothing for the runtime of the join
test, meaning I'd still like to see some effort put into reducing that.

			regards, tom lane

  15. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T19:38:37Z

    I wrote:
> As I feared, the existing regression tests are not really adequate for
> this: gcov testing shows that the sentinel-inserting code path is
> never entered, meaning ConditionVariableBroadcast never sees more
> than one waiter.

Hmm ... adding tracing log printouts in BarrierArriveAndWait disproves
that: the regression tests do, repeatedly, call ConditionVariableBroadcast
when there are two waiters to be woken (and you can get it to be more if
you raise the number of parallel workers specified in the PHJ tests).
It just doesn't happen with --enable-coverage.  Heisenberg wins again!

I am not sure why coverage tracking changes the behavior so much, but
it's clear from my results that if you change all the PHJ test cases in
join.sql to use 4 parallel workers, then you get plenty of barrier release
events with 4 or 5 barrier participants --- but running the identical test
under --enable-coverage results in only a very small number of releases
with even as many as 2 participants, let alone more.  Perhaps the PHJ test
cases don't run long enough to let slow-starting workers join in?

Anyway, that may or may not indicate something we should tune at a higher
level, but I'm now satisfied that the patch as presented works and does
get tested by our existing tests.  So barring objection I'll commit that
shortly.

There are some other things I don't like about condition_variable.c:

* I think the Asserts in ConditionVariablePrepareToSleep and
ConditionVariableSleep ought to be replaced by full-fledged test and
elog(ERROR), so that they are enforced even in non-assert builds.
I don't have a lot of confidence that corner cases that could violate
those usage restrictions would get caught during developer testing.
Nor do I see an argument that we can't afford the cycles to check.

* ConditionVariablePrepareToSleep needs to be rearranged so that failure
to create the WaitEventSet doesn't leave us in an invalid state.

* A lot of the comments could be improved, IMHO.

Barring objection I'll go deal with those things, too.

			regards, tom lane

  16. Re: Condition variable live lock

    Robert Haas <robertmhaas@gmail.com> — 2018-01-05T19:52:38Z

    On Fri, Jan 5, 2018 at 2:38 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> * I think the Asserts in ConditionVariablePrepareToSleep and
> ConditionVariableSleep ought to be replaced by full-fledged test and
> elog(ERROR), so that they are enforced even in non-assert builds.
> I don't have a lot of confidence that corner cases that could violate
> those usage restrictions would get caught during developer testing.
> Nor do I see an argument that we can't afford the cycles to check.

I think those usage restrictions are pretty basic, and I think this
might be used in some places where performance does matter.  So -1
from me for this change.

> * ConditionVariablePrepareToSleep needs to be rearranged so that failure
> to create the WaitEventSet doesn't leave us in an invalid state.

+1.

> * A lot of the comments could be improved, IMHO.

No opinion without seeing what you propose to change.

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

  17. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-05T20:03:19Z

    Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Jan 5, 2018 at 2:38 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> * I think the Asserts in ConditionVariablePrepareToSleep and
>> ConditionVariableSleep ought to be replaced by full-fledged test and
>> elog(ERROR), so that they are enforced even in non-assert builds.
>> I don't have a lot of confidence that corner cases that could violate
>> those usage restrictions would get caught during developer testing.
>> Nor do I see an argument that we can't afford the cycles to check.

> I think those usage restrictions are pretty basic, and I think this
> might be used in some places where performance does matter.  So -1
> from me for this change.

Really?  We're about to do a process sleep, and we can't afford a single
test and branch to make sure we're doing it sanely?

>> * A lot of the comments could be improved, IMHO.

> No opinion without seeing what you propose to change.

OK, will put out a proposal.

			regards, tom lane

  18. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-05T21:25:27Z

    On Sat, Jan 6, 2018 at 6:33 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> As I feared, the existing regression tests are not really adequate for
> this: gcov testing shows that the sentinel-inserting code path is
> never entered, meaning ConditionVariableBroadcast never sees more
> than one waiter.  What's more, it's now also apparent that no outside
> caller of ConditionVariableSignal ever actually awakens anything.
> So I think it'd be a good idea to expand the regression tests if we
> can do so cheaply.  Anybody have ideas about that?  Perhaps a new
> module under src/test/modules would be the best way?  Alternatively,
> we could drop some of the optimization ideas.

I think I might have a suitable test module already.  I'll tidy it up
and propose it in a few days.

> BTW, at least on gaur, this does nothing for the runtime of the join
> test, meaning I'd still like to see some effort put into reducing that.

Will do.

-- 
Thomas Munro
http://www.enterprisedb.com

  19. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-06T21:00:24Z

    I wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> No opinion without seeing what you propose to change.

> OK, will put out a proposal.

I began with the intention of making no non-cosmetic changes, but then
I started to wonder why ConditionVariablePrepareToSleep bothers with a
!proclist_contains test, when the calling process surely ought not be
in the list -- or any other list -- since it wasn't prepared to sleep.
And that led me down a different rabbit hole ending in the conclusion
that proclist.h could stand some improvements too.  I do not like the
fact that it's impossible to tell whether a proclist_node is in any
proclist or not.  Initially, a proclist_node contains zeroes which is
a distinguishable state, but proclist_delete_offset resets it to
next = prev = INVALID_PGPROCNO which looks the same as a node that's in a
singleton list.  We should have it reset to the initial state of zeroes
instead, and then we can add assertions to proclist_push_xxx that the
supplied node is not already in a list.  Hence, I propose the first
attached patch which tightens things up in proclist.h and then removes
the !proclist_contains test in ConditionVariablePrepareToSleep; the
assertion in proclist_push_tail supersedes that.

The second attached patch is the cosmetic changes I want to make in
condition_variable.c/.h.

I still think that we ought to change the Asserts on cv_sleep_target in
ConditionVariablePrepareToSleep and ConditionVariableSleep to be full
test-and-elog tests.  Those are checking a global correctness property
("global" meaning "interactions between completely unrelated modules can
break this"), and they'd be extremely cheap compared to the rest of what
those functions are doing, so I think insisting that they be Asserts is
penny wise and pound foolish.  Anybody besides Robert want to vote on
that?

Another loose end that I'm seeing here is that while a process waiting on
a condition variable will respond to a cancel or die interrupt, it will
not notice postmaster death.  This seems unwise to me.  I think we should
adjust the WaitLatch call to include WL_POSTMASTER_DEATH as a wake
condition and just do a summary proc_exit(1) if it sees that.  I'd even
argue that that is a back-patchable bug fix.

			regards, tom lane

  20. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-06T21:43:58Z

    I wrote:
> I still think that we ought to change the Asserts on cv_sleep_target in
> ConditionVariablePrepareToSleep and ConditionVariableSleep to be full
> test-and-elog tests.  Those are checking a global correctness property
> ("global" meaning "interactions between completely unrelated modules can
> break this"), and they'd be extremely cheap compared to the rest of what
> those functions are doing, so I think insisting that they be Asserts is
> penny wise and pound foolish.

Actually ... perhaps a better design would be to have
ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
a different condition variable, analogously to what we just did in
ConditionVariableBroadcast, on the same theory that whenever control
returns to the other CV wait loop it can re-establish the relevant
state easily enough.  I have to think that if the use of CVs grows
much, the existing restriction is going to become untenable anyway,
so why not just get rid of it?

			regards, tom lane

  21. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-07T23:38:36Z

    I wrote:
> Actually ... perhaps a better design would be to have
> ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
> a different condition variable, analogously to what we just did in
> ConditionVariableBroadcast, on the same theory that whenever control
> returns to the other CV wait loop it can re-establish the relevant
> state easily enough.  I have to think that if the use of CVs grows
> much, the existing restriction is going to become untenable anyway,
> so why not just get rid of it?

Concretely, as per attached.

			regards, tom lane

  22. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-08T02:21:30Z

    On Mon, Jan 8, 2018 at 12:38 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
>> Actually ... perhaps a better design would be to have
>> ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
>> a different condition variable, analogously to what we just did in
>> ConditionVariableBroadcast, on the same theory that whenever control
>> returns to the other CV wait loop it can re-establish the relevant
>> state easily enough.  I have to think that if the use of CVs grows
>> much, the existing restriction is going to become untenable anyway,
>> so why not just get rid of it?
>
> Concretely, as per attached.

+1 for the idea.  Haven't looked at the code yet but I'll review this
and the proclist patch shortly.

-- 
Thomas Munro
http://www.enterprisedb.com

  23. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-08T02:34:11Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Mon, Jan 8, 2018 at 12:38 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Concretely, as per attached.

> +1 for the idea.  Haven't looked at the code yet but I'll review this
> and the proclist patch shortly.

Thanks.  BTW, I realized that there is a second (and perhaps more
important) reason why we can only prepare one CV sleep at a time:
we only have one cvWaitLink in our PGPROC.  So I'm now inclined
to word the revised comment in ConditionVariablePrepareToSleep as

    /*
     * If some other sleep is already prepared, cancel it; this is necessary
     * because we have just one static variable tracking the prepared sleep,
     * and also only one cvWaitLink in our PGPROC.  It's okay to do this
     * because whenever control does return to the other test-and-sleep loop,
     * its ConditionVariableSleep call will just re-establish that sleep as
     * the prepared one.
     */

			regards, tom lane

  24. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-08T04:25:53Z

    On Sun, Jan 7, 2018 at 10:00 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I began with the intention of making no non-cosmetic changes, but then
> I started to wonder why ConditionVariablePrepareToSleep bothers with a
> !proclist_contains test, when the calling process surely ought not be
> in the list -- or any other list -- since it wasn't prepared to sleep.
> And that led me down a different rabbit hole ending in the conclusion
> that proclist.h could stand some improvements too.  I do not like the
> fact that it's impossible to tell whether a proclist_node is in any
> proclist or not.  Initially, a proclist_node contains zeroes which is
> a distinguishable state, but proclist_delete_offset resets it to
> next = prev = INVALID_PGPROCNO which looks the same as a node that's in a
> singleton list.  We should have it reset to the initial state of zeroes
> instead, and then we can add assertions to proclist_push_xxx that the
> supplied node is not already in a list.  Hence, I propose the first
> attached patch which tightens things up in proclist.h and then removes
> the !proclist_contains test in ConditionVariablePrepareToSleep; the
> assertion in proclist_push_tail supersedes that.

+1

> The second attached patch is the cosmetic changes I want to make in
> condition_variable.c/.h.

+1

> I still think that we ought to change the Asserts on cv_sleep_target in
> ConditionVariablePrepareToSleep and ConditionVariableSleep to be full
> test-and-elog tests.  Those are checking a global correctness property
> ("global" meaning "interactions between completely unrelated modules can
> break this"), and they'd be extremely cheap compared to the rest of what
> those functions are doing, so I think insisting that they be Asserts is
> penny wise and pound foolish.  Anybody besides Robert want to vote on
> that?

I liked your follow-up idea better (see below).

> Another loose end that I'm seeing here is that while a process waiting on
> a condition variable will respond to a cancel or die interrupt, it will
> not notice postmaster death.  This seems unwise to me.  I think we should
> adjust the WaitLatch call to include WL_POSTMASTER_DEATH as a wake
> condition and just do a summary proc_exit(1) if it sees that.  I'd even
> argue that that is a back-patchable bug fix.

Yeah.  As far as I know so far, every place where we wait on a
WaitEventSet falls into one of 4 categories when it comes to
postmaster death:

1.  We proc_exit(1) if WL_POSTMASTER_DEATH is returned.
2.  We ereport(FATAL) if WL_POSTMASTER_DEATH is returned.
3.  We asked for WL_POSTMASTER_DEATH in the WaitEventSet, but we don't
actually bother checking for it in the returned value.  Instead we
call PostmasterIsAlive() every time through the loop (pgarch.c,
syncrep.c, walsender.c and walreceiver.c).
4.  We didn't ask for WL_POSTMASTER_DEATH.

Do I have that right?  I guess category 3 is suboptimal especially on
some clunky but loveable kernels[1] and all cases of 4 including this
one are probably bugs.  That makes me wonder why we don't change the
WaitEventSet API so that it calls proc_exit(1) for you by default if
you didn't ask to receive WL_POSTMASTER_DEATH explicitly, to handle
category 1 for free.  If you asked for WL_POSTMASTER_DEATH explicitly
then we could return it, to support category 2 callers that want to do
something different.  Just a thought.

Another possibility for this particular case would be that the client
of ConditionVariable would like to be able to chose how to handle
postmaster death, and in turn the client of Barrier (a client) might
like to be able to choose too.  But in every case I'm aware of today
proc_exit(1) is the right thing to do, so teaching
ConditionVariableSleep() to do that seems OK to me.

On Sun, Jan 7, 2018 at 10:43 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Actually ... perhaps a better design would be to have
> ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
> a different condition variable, analogously to what we just did in
> ConditionVariableBroadcast, on the same theory that whenever control
> returns to the other CV wait loop it can re-establish the relevant
> state easily enough.  I have to think that if the use of CVs grows
> much, the existing restriction is going to become untenable anyway,
> so why not just get rid of it?

+1

It's a more robust API this way.

On Mon, Jan 8, 2018 at 3:34 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Thanks.  BTW, I realized that there is a second (and perhaps more
> important) reason why we can only prepare one CV sleep at a time:
> we only have one cvWaitLink in our PGPROC.  So I'm now inclined
> to word the revised comment in ConditionVariablePrepareToSleep as
>
>     /*
>      * If some other sleep is already prepared, cancel it; this is necessary
>      * because we have just one static variable tracking the prepared sleep,
>      * and also only one cvWaitLink in our PGPROC.  It's okay to do this
>      * because whenever control does return to the other test-and-sleep loop,
>      * its ConditionVariableSleep call will just re-establish that sleep as
>      * the prepared one.
>      */

+1

[1] https://www.postgresql.org/message-id/flat/CAEepm%3D0qQ6DO-u%3D25ny5EJAUbWeHbAQgJj1UJFAL1NWJNxC%2Bgg%40mail.gmail.com

-- 
Thomas Munro
http://www.enterprisedb.com

  25. Re: Condition variable live lock

    Thomas Munro <thomas.munro@enterprisedb.com> — 2018-01-08T11:41:36Z

    On Mon, Jan 8, 2018 at 5:25 PM, Thomas Munro
<thomas.munro@enterprisedb.com> wrote:
> On Sun, Jan 7, 2018 at 10:43 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Actually ... perhaps a better design would be to have
>> ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
>> a different condition variable, analogously to what we just did in
>> ConditionVariableBroadcast, on the same theory that whenever control
>> returns to the other CV wait loop it can re-establish the relevant
>> state easily enough.  I have to think that if the use of CVs grows
>> much, the existing restriction is going to become untenable anyway,
>> so why not just get rid of it?
>
> +1
>
> It's a more robust API this way.

One very small thing after another look:

-       Assert(cv_sleep_target == NULL);
+       if (cv_sleep_target != NULL)
+               ConditionVariableCancelSleep();

The test for cv_sleep_target != NULL is redundant since
ConditionVariableCancelSleep() would return early.
ConditionVariableBroadcast() doesn't do that.

-- 
Thomas Munro
http://www.enterprisedb.com

  26. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-08T14:57:05Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> One very small thing after another look:

> -       Assert(cv_sleep_target == NULL);
> +       if (cv_sleep_target != NULL)
> +               ConditionVariableCancelSleep();

> The test for cv_sleep_target != NULL is redundant since
> ConditionVariableCancelSleep() would return early.

True.  I did that because Robert was already objecting to the cost
of an added test-and-branch here, so I figured he'd be really
unhappy with the cost of a function call plus test-and-branch ;-)

> ConditionVariableBroadcast() doesn't do that.

Yup.  I considered removing the discrepancy by adding a similar
if-guard in ConditionVariableBroadcast().  The internal test in
ConditionVariableCancelSleep would then be only for the benefit
of outside callers such as AbortTransaction, but that seems fine
and per its documentation.

Or we could remove those if's and save a few bytes at the
cost of some cycles.  I don't care much.

			regards, tom lane

  27. Re: Condition variable live lock

    Robert Haas <robertmhaas@gmail.com> — 2018-01-08T20:27:35Z

    On Sun, Jan 7, 2018 at 6:38 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Actually ... perhaps a better design would be to have
>> ConditionVariable[PrepareTo]Sleep auto-cancel any prepared sleep for
>> a different condition variable, analogously to what we just did in
>> ConditionVariableBroadcast, on the same theory that whenever control
>> returns to the other CV wait loop it can re-establish the relevant
>> state easily enough.  I have to think that if the use of CVs grows
>> much, the existing restriction is going to become untenable anyway,
>> so why not just get rid of it?
>
> Concretely, as per attached.

I guess my aversion to converting the existing Assert-test into an
elog test was really a concern that we'd be countenancing the use of
CVs in any coding pattern more complicated than a very simple
test-and-wait loop.  Suppose someone were to propose adding runtime
checks that when we release a spinlock, it is held by the process that
tried to release it.  Someone might reply that such a check ought to
be unnecessary because the code protected by a spinlock ought to be a
short, straight-line critical section and therefore we should be able
to spot any such coding error by inspection.

And I wonder if the same isn't true here.  Is it really sensible,
within a CV-wait loop, to call some other function that contains its
own CV-wait loop?  Is that really a use case we want to support?  If
you do have such a thing, with the present coding, you don't *need* an
Assert() at runtime; you just need to run the code with assertions
enabled AT LEAST ONCE.  If the code flow is so complex that it doesn't
reliably fail an assertion in test environments, maybe it's just too
complex.  Perhaps our answer to that, or so my thinking went, ought to
be "don't write code like that in the first place".

Now, that may be myopic on my part.  If we want to support complex
control flows involving CVs, the approach here has a lot to recommend
it.  Instead of making it the caller's problem to work it out, we do
it automatically.  There is some loss of efficiency, perhaps, since
when control returns to the outer CV-wait loop it will have to recheck
the condition twice before potentially waiting, but maybe that doesn't
matter.  It's often the case that mechanisms like this end up getting
used profitably in a lot of places not imagined by their original
creator, and that might be the case here.

I think an extremely *likely* programming error when programming with
CVs is to have a code path where ConditionVariableCancelSleep() does
not get called.  The proposed change could make such mistakes much
less noticeable.

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

  28. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-08T20:45:02Z

    Robert Haas <robertmhaas@gmail.com> writes:
> I guess my aversion to converting the existing Assert-test into an
> elog test was really a concern that we'd be countenancing the use of
> CVs in any coding pattern more complicated than a very simple
> test-and-wait loop.  Suppose someone were to propose adding runtime
> checks that when we release a spinlock, it is held by the process that
> tried to release it.  Someone might reply that such a check ought to
> be unnecessary because the code protected by a spinlock ought to be a
> short, straight-line critical section and therefore we should be able
> to spot any such coding error by inspection.

Right, *because* we have the rule that spinlock-protected code must be
short straight-line segments.  There is certainly no such rule for
LWLocks, and I'm not sure why you think that CVs have more restricted
use-cases than LWLocks.

There is a potential issue, if you call random code inside the wait loop,
that that code might reset the process latch and thereby lose a signal for
the CV.  As far as I can see at the moment, that'd only be a hazard for
code executed before the loop's ConditionVariableSleep, not after, so even
that can be avoided if you code properly.  In any case, the proposed
generalization of CVs poses no such hazard: yes, we might reset the latch,
but if so the outer CV loop will see that it's lost its prepared sleep
state and will be forced to recheck its exit condition.

> It's often the case that mechanisms like this end up getting
> used profitably in a lot of places not imagined by their original
> creator, and that might be the case here.

Yeah, that's exactly my expectation.  If I thought we were only going to
have five uses of condition variables forevermore, I wouldn't be putting
much time into them.

> I think an extremely *likely* programming error when programming with
> CVs is to have a code path where ConditionVariableCancelSleep() does
> not get called.  The proposed change could make such mistakes much
> less noticeable.

Actually, the proposed change would turn it into barely an error at all.
The only advantage of cancelling a sleep immediately is that you avoid
possibly getting a no-longer-useful latch event later.

			regards, tom lane

  29. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-08T23:50:33Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Sun, Jan 7, 2018 at 10:00 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I began with the intention of making no non-cosmetic changes, but then
>> I started to wonder why ConditionVariablePrepareToSleep bothers with a
>> !proclist_contains test, when the calling process surely ought not be
>> in the list -- or any other list -- since it wasn't prepared to sleep.
>> And that led me down a different rabbit hole ending in the conclusion
>> that proclist.h could stand some improvements too.

> +1

>> The second attached patch is the cosmetic changes I want to make in
>> condition_variable.c/.h.

> +1

I pushed these, with an addition to ConditionVariablePrepareToSleep's
comment emphasizing that you're supposed to call it before the loop test;
this because some desultory digging found that one of the existing callers
is violating that rule.  replorigin_drop() in replication/logical/origin.c
has

                cv = &state->origin_cv;

                LWLockRelease(ReplicationOriginLock);
                ConditionVariablePrepareToSleep(cv);
                ConditionVariableSleep(cv, WAIT_EVENT_REPLICATION_ORIGIN_DROP);
                ConditionVariableCancelSleep();
                goto restart;

and unless I'm much mistaken, that is flat broken.  Somebody could
change the ReplicationState's acquired_by before we reach
ConditionVariablePrepareToSleep, in which case we won't get any signal
for that and will just sleep here indefinitely.

It would still be broken if we removed the PrepareToSleep call, but
at least it'd be a busy-wait not a hang.

Not sure about a convenient fix.  One idea is to move the
PrepareToSleep call inside the hold on ReplicationOriginLock, which
would fix things only if the various signallers of origin_cv did the
signalling while holding that lock, which they do not.  It's not clear
to me whether making them do so inside that lock would be problematic
for performance.

We can't just move the prepare/cancel sleep calls to around this whole
loop, because we do not know outside the loop which CV is to be waited
on.  So another idea is to get rid of that and have just one CV for all
ReplicationStates.

Or (and I'm sure Robert sees this coming), if we applied my proposed
patch to let ConditionVariableSleep auto-switch to a different CV,
then we could fix this code by simply removing the PrepareToSleep and
moving the ConditionVariableCancelSleep call to below the loop.
This would work even in the perhaps-unlikely case where the slot as
identified by roident changed positions, though you'd get an additional
trip through the loop (a/k/a test of the exit condition) if that
happened.

>> Another loose end that I'm seeing here is that while a process waiting on
>> a condition variable will respond to a cancel or die interrupt, it will
>> not notice postmaster death.

> Yeah.

I'll respond to that separately to keep it from getting confused with
this replorigin_drop() bug.

			regards, tom lane

  30. Re: Condition variable live lock

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-01-09T00:02:23Z

    Thomas Munro <thomas.munro@enterprisedb.com> writes:
> On Sun, Jan 7, 2018 at 10:00 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Another loose end that I'm seeing here is that while a process waiting on
>> a condition variable will respond to a cancel or die interrupt, it will
>> not notice postmaster death.  This seems unwise to me.  I think we should
>> adjust the WaitLatch call to include WL_POSTMASTER_DEATH as a wake
>> condition and just do a summary proc_exit(1) if it sees that.  I'd even
>> argue that that is a back-patchable bug fix.

> Yeah.  As far as I know so far, every place where we wait on a
> WaitEventSet falls into one of 4 categories when it comes to
> postmaster death:

> 1.  We proc_exit(1) if WL_POSTMASTER_DEATH is returned.
> 2.  We ereport(FATAL) if WL_POSTMASTER_DEATH is returned.
> 3.  We asked for WL_POSTMASTER_DEATH in the WaitEventSet, but we don't
> actually bother checking for it in the returned value.  Instead we
> call PostmasterIsAlive() every time through the loop (pgarch.c,
> syncrep.c, walsender.c and walreceiver.c).
> 4.  We didn't ask for WL_POSTMASTER_DEATH.

> Do I have that right?  I guess category 3 is suboptimal especially on
> some clunky but loveable kernels[1] and all cases of 4 including this
> one are probably bugs.  That makes me wonder why we don't change the
> WaitEventSet API so that it calls proc_exit(1) for you by default if
> you didn't ask to receive WL_POSTMASTER_DEATH explicitly, to handle
> category 1 for free.  If you asked for WL_POSTMASTER_DEATH explicitly
> then we could return it, to support category 2 callers that want to do
> something different.  Just a thought.

Yeah, that's worth thinking about, because I'm pretty sure that we have
had this type of bug before.  We have to be a bit careful because
Andres is thinking of using the WaitEventState support in the postmaster
loop, where it definitely shouldn't check WL_POSTMASTER_DEATH, and it
is probably also possible to reach some of those calls in standalone
backends, which shouldn't either.  So I'm imagining:

1. The WaitEventSet code always includes WL_POSTMASTER_DEATH checking
if IsUnderPostmaster --- and conversely, if !IsUnderPostmaster, it should
ignore any caller request for that.

2. If caller specifies WL_POSTMASTER_DEATH then we'll return that
flag bit, otherwise just exit(1) --- or should the default be
ereport(FATAL)?

3. Remove explicit specification of WL_POSTMASTER_DEATH anywhere that
the default handling is OK, which is probably almost everywhere.
Get rid of those now-redundant PostmasterIsAlive checks, too.

I'm not real sure BTW why we have some callers that ereport and some
that just exit(1).  Seems like it would be better to be consistent,
though I'm not entirely sure which behavior to standardize on.

(Of course, this would only be an appropriate thing to do in HEAD.
In v10 I think we should do the narrow fix I suggested up top.)

			regards, tom lane

  31. Re: Condition variable live lock

    Robert Haas <robertmhaas@gmail.com> — 2018-01-09T04:02:32Z

    On Mon, Jan 8, 2018 at 7:02 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I'm not real sure BTW why we have some callers that ereport and some
> that just exit(1).  Seems like it would be better to be consistent,
> though I'm not entirely sure which behavior to standardize on.

I think at one point we had an idea that regular backends would FATAL
if the postmaster fell over and other processes (e.g. checkpointer,
bgwriter) would exit silently.  Whether that was the right idea, and
whether it's still is/was ever what the code did, I'm not sure.

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