[gst-devel] Multi-threaded queueing locking issues

[Erik Walthinsen]

OK, I think I've got the locking code to work properly, and even be quite
efficient.  This is accomplished with the use of interleaved signals and
cond-waits.  You have something like this:

thread A:				thread B:
g_mutex_lock(lock);			g_mutex_lock(lock);
g_cond_signal(cond);			g_cond_wait(cond,lock);
g_cond_wait(cond,lock);			g_cond_signal(lock);
g_mutex_unlock(lock);			g_mutex_unlock(lock);

This is the best way to do interlocking sync points, afaict.  Thanks to
matth for teaching me about it!  How exactly it works is left as an
excercise for the reader <g>

Anyway, that's one problem down, a few more to tackle.  Specifically, I've
run into the fact that if you have any queue's in your thread, they are
generally going to be stuck waiting on a condition variable for the other
side of the queue to put something in or take something out.

When a change_state happens on the thread, it must tell the thread to stop
spinning and change the state of all the children.  This is done by simply
clearing the SPINNING flag on the thread and waiting for it to change
state and signal back.  This only works if the while(SPINNING) loop has a
chance to exit, which means that the bin_iterate() function must exit at
some point.

When you have queues on thread boundaries, you're going to end up stuck in
a cond-wait such that the iterate() will never exit.  This is a
significant problem, because this puts us in deadlock.

The solution I've developed in my head is this:  after setting the state
to !SPINNING, do a cond_timed_wait with some reasonable, configurable
timeout.  If this timed-wait times out, we could assume that the thread is
stuck somewhere.  This can be clarified by having the elements that might
block set a flag on the thread during the event that might block, so we
know whether it's blocking or just taking a long time.

When we find ourselves stuck with a blocked thread, we have to somehow
unblock it in a way that doesn't cause significant pain.  My thought would
be to fire a signal() at it, which the thread would catch with a custom
signal handler.  This handler would simply cause a cothread_switch() back
to the 0th thread, which puts it right back into the middle of
bin_iterate().  A flag can tell iterate() to stop everything and return
from that point.

Now, there are quite a few concerns here.  First of all, this signal is
going to come right in the middle of the queue's cond_wait.  From my quick
look through the linuxthreads code and minimal understanding of POSIX
signals, I really can't say whether this is a problem or not.  I'd guess
not.

Next, doing a cothread switch in the middle of this mangled context could
be very scary.  I've noticed sigsetjmp(3), which claims to save the
blocked-signals state.  This seems apropos, since the linuxthreads code
for a suspend is:

  sigdelset(&mask, __pthread_sig_restart); /* Unblock the restart signal */
  do {
    sigsuspend(&mask);                   /* Wait for signal */
  } ...

If setjmp/longjmp mangle the blocked-signals list, this could cause
significant problems.  If the restart signal (SIGUSR1) ends up blocked
when we switch back from the setjmp to cothread 0, we'll be stuck in the
cond_wait forever (possibly even beyond parent death, ick).
Experimentation is needed to determine if we have to do
sigsetjmp/siglongjmp in these cases.  If so, we need to determine the
overhead of sigsetjmp/siglongjmp every time vs. checking to see if we need
to use it for each jump.

Next comes the question of what happens if when we try to perform a
cond-wait in the thread-interlock code in cothread 0 while we have an
interrupted cond-wait sitting there waiting for the queue to signal.  Is
the thread cond-wait going to somehow trigger the queue's cond-wait, and
if so I really don't want to think about the mayhem that will cause when
it comes back on the wrong stack.  I'm guessing it will work though,
because linuxthreads uses queues internally, and afaik the signal handler
installed for the thread's cond-wait will always trigger and remove itself
before the thread's cond-wait even has a chance to pop back to the top of
the signal-handler stack.

Then, when we restart the thread, we want to jump right back where we came
from, which would be the signal handler that interrupted the queue's
cond-wait in the first place.  I would assume that the signal context
would cleanly unwrap, and the code would end up back in the middle of the
sigsuspend in the code shown above.  It may do a cycle through the
do/while, but that's what it's there for.

The problem is: what if the other side of the queue signals while the
thread is shut down?  First thing is that it's going to trigger the
cond-wait signal handler that actually belongs to the thread at that
point.  This isn't such a big deal from the thread's point of view, since
it's just a spurious wakeup.  It'll go back to sleep since it wasn't woken
up for the reason it was waiting for.  The side-effect of this is that the
signal that the queue was waiting for to unblock itself gets lost.  The
other side of the queue has no idea that this is the case, and since the
queue is no longer either empty or full, it won't *ever* signal again.
Oops.

That means that somehow we have to work in an interlock in queue
signaling, such that the signaling side knows whether the waiting side has
actually woken up.  So we end up with a protected boolean that the waiting
side sets before it goes to sleep, and unsets as it wakes up.  The
signaling side would keep signaling until it sees that this boolean has
been cleared, indicating that the waiting side got what it wanted.

This fails quite rapidly, since when the thread is sitting waiting to
start spinning again, it'll be doing cond-waits.  Since the signaling side
of the queue presumably could signal during this, and it does so with the
same SIGUSR1 that the thread's parent would, it would spuriously awaken
the thread.  Since the signal succeeded, but the 'waiting' boolean doesn't
get reset, the signaling side of the queue tries again.  And again.  And
again.  The machine grinds to a halt with massive switching and
mis-signaling.

On solution is for the signaling side of the queue to wait for some amount
of time after each failed signal.  This would have the effect of
limiting, if not eliminating, the spurious wakeups.  Another solution is
to make the queue smarter, and if the signal comes back without the
'waiting' boolean having been cleared, it checks the state of the queue
before trying again.

Hrm, that's an interesting problem, that extends outside the scope of this
issue, but may also solve it.  The queue only has one state variable,
since it's only a single element.  This also means that there's only one
parent, which could either be the thread or its parent.  This element
state could be sufficient to keep the signaling of the queue from
happening when it might get lost.

If the queue is inside the thread, it will get interrupted, and set to
!PLAYING.  If the other side of the queue gets called at that point and
has reason to signal, it can simply check the state of the element.  It
would still want to check the 'waiting' boolean after signaling, in case
there's a race (or some other locking can be done).  The problem then is
what to wait on?  One possiblity is to just give up and finish the push or
pull and leave the 'waiting' boolean set.  This would mean that every push
or pull after that would cause another attempt to wake up the other half
of the thread.  This isn't so bad, necessarily.

If the queue is outside the thread in question, we have a harder problem.
The state of the queue won't change when the thread leaves PLAYING, but at
least the queue can still check the state of the thread in a very
roundabout way by checking the state of the element peered to the other
side of the queue.  Hmmmm...

You'll notice that I never suggested that we simply trick the queue into
waking up and just go from there.  We have to interrupt it in the middle
for one simple reason: the queue isn't the only thing that might block.
Anything that talks to the kernel could theoretically block.  This mostly
includes things that go over the network, or even to disk in some cases
(though I'd rather assume that disk accesses are reasonably bounded).
Unless we also have a way of dealing with these kinds of elements and
interrupting their reads or writes, we can't special-case the queue.  And
besides, that starts to put a lot more smarts into these kinds of
elements.

Another option might be to require that anything that might block be
written with a timeout on any block-able call.  This could work, but again
puts the burden on the plugin-writer to check with the scheduler (or
something, the problem is: what exactly?) and see if it should continue or
punt, and if it punts, how does it punt?

Anyway, I need to go to sleep now.  If anyone can follow that whole mess
and has comments, please write them up.  If I'm making stupid assumptions,
tell me <g>

      Erik Walthinsen <omega at temple-baptist.com> - System Administrator
        __
       /  \                GStreamer - The only way to stream!
      |    | M E G A        ***** http://gstreamer.net/ *****
      _\  /_