Here's a testcase that may result in a deadlock (happens when playing live
ogg/theora streams using totem):

create a mainbin which outputs data (fakesrc ! queue), have an output thread ({
fakesink }), run the mainbin, add the thread to the bin, set to playing and only
then link queue to fakesink (all in mainbin context). Inside
gstoptimalscheduler.c:2128, it will hang on the lock. The thread iterates, tries
to get data but since it's not linked yet, it will fail to do so:

LOG   (0xa347730 - 307931:51:17.236616000)       scheduler(20745)
gstoptimalscheduler.c(1271):gst_opt_scheduler_schedule_run_queue:<GstOptScheduler@0xa33a798>
scheduling group 0xa346690
INFO  (0xa347730 - 307931:51:17.236736000)       scheduler(20745)
gstoptimalscheduler.c(1183):schedule_group: not scheduling group 0xa346690
without entry
LOG   (0xa347730 - 307931:51:17.236839000)       scheduler(20745)
gstoptimalscheduler.c(1284):gst_opt_scheduler_schedule_run_queue:<GstOptScheduler@0xa33a798>
done scheduling group 0xa346690

During this, apparently the lock is held in some way, because the other thread
will hang after this log message (easily traceable by searching for the
thread-ID in the logfile):

INFO  (0xa2dce10 - 307931:51:17.234590000)       scheduler(20745)
gstoptimalscheduler.c(2123):gst_opt_scheduler_pad_link: scheduling link between
preroll_audio_src0:src and aconv:sink

Here's a partial backtrace:

+ Trace 55766

Currently still working on valgrinding, since that last line doesn't look too
good, but it does seem to hang in the static mutex in opt. Once valgrind is
complete, I'll try to prepare a testcase to reproduce in lab settings.