Re: Condition variable live lock - Mailing list pgsql-hackers

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

diff --git a/src/backend/storage/lmgr/condition_variable.c b/src/backend/storage/lmgr/condition_variable.c
index 41378d6..55275cf 100644
*** a/src/backend/storage/lmgr/condition_variable.c
--- b/src/backend/storage/lmgr/condition_variable.c
*************** int
*** 214,228 ****
  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;
  }
--- 214,300 ----
  ConditionVariableBroadcast(ConditionVariable *cv)
  {
      int            nwoken = 0;
+     int            pgprocno = MyProc->pgprocno;
+     PGPROC       *proc = NULL;
+     bool        have_sentinel = false;

      /*
!      * In some use-cases, it is common for awakened processes to immediately
!      * re-queue themselves.  If we just naively try to reduce the wakeup list
!      * to empty, we'll get into a potentially-indefinite loop against such a
!      * process.  The semantics we really want are just to be sure that we have
!      * wakened all processes that were in the list at entry.  We can use our
!      * own cvWaitLink as a sentinel to detect when we've finished.
!      *
!      * A seeming flaw in this approach is that someone else might signal the
!      * CV and in doing so remove our sentinel entry.  But that's fine: since
!      * CV waiters are always added and removed in order, that must mean that
!      * every previous waiter has been wakened, so we're done.  We'll get an
!      * extra "set" on our latch from the someone else's signal, which is
!      * slightly inefficient but harmless.
!      *
!      * We can't insert our cvWaitLink as a sentinel if it's already in use in
!      * some other proclist.  While that's not expected to be true for typical
!      * uses of this function, we can deal with it by simply canceling any
!      * prepared CV sleep.  The next call to ConditionVariableSleep will take
!      * care of re-establishing the lost state.
       */
!     ConditionVariableCancelSleep();
!
!     /*
!      * Inspect the state of the queue.  If it's empty, we have nothing to do.
!      * If there's exactly one entry, we need only remove and signal that
!      * entry.  Otherwise, remove the first entry and insert our sentinel.
!      */
!     SpinLockAcquire(&cv->mutex);
!     /* While we're here, let's assert we're not in the list. */
!     Assert(!proclist_contains(&cv->wakeup, pgprocno, cvWaitLink));
!
!     if (!proclist_is_empty(&cv->wakeup))
!     {
!         proc = proclist_pop_head_node(&cv->wakeup, cvWaitLink);
!         if (!proclist_is_empty(&cv->wakeup))
!         {
!             proclist_push_tail(&cv->wakeup, pgprocno, cvWaitLink);
!             have_sentinel = true;
!         }
!     }
!     SpinLockRelease(&cv->mutex);
!
!     /* Awaken first waiter, if there was one. */
!     if (proc != NULL)
!     {
!         SetLatch(&proc->procLatch);
          ++nwoken;
+     }
+
+     while (have_sentinel)
+     {
+         /*
+          * Each time through the loop, remove the first wakeup list entry, and
+          * signal it unless it's our sentinel.  Repeat as long as the sentinel
+          * remains in the list.
+          *
+          * Notice that if someone else removes our sentinel, we will waken one
+          * additional process before exiting.  That's intentional, because if
+          * someone else signals the CV, they may be intending to waken some
+          * third process that added itself to the list after we added the
+          * sentinel.  Better to give a spurious wakeup (which should be
+          * harmless beyond wasting some cycles) than to lose a wakeup.
+          */
+         proc = NULL;
+         SpinLockAcquire(&cv->mutex);
+         if (!proclist_is_empty(&cv->wakeup))
+             proc = proclist_pop_head_node(&cv->wakeup, cvWaitLink);
+         have_sentinel = proclist_contains(&cv->wakeup, pgprocno, cvWaitLink);
+         SpinLockRelease(&cv->mutex);
+
+         if (proc != NULL && proc != MyProc)
+         {
+             SetLatch(&proc->procLatch);
+             ++nwoken;
+         }
+     }

      return nwoken;
  }