tst-cond18 hang analysis

[Jakub Jelinek]

Hi!

This is posted mainly for archival purposes.
It documents a nptl/tst-cond18.c hang with NPTL CVS as of 2004-05-16.

This ought to be fixed in current CVS (after the 2004-05-18 CVS
commits to nptl/) by introducing broadcast_seq.

thr1    thr2    thr3    thr4    thr5    thr6
pthread_mutex_lock (&m);
pthread_cond_wait (&c, &m);
        pthread_mutex_lock (&m);
        pthread_cond_wait (&c, &m);
                pthread_mutex_lock (&m);
                        pthread_mutex_lock (&m);
                                pthread_mutex_lock (&m);
                                        pthread_mutex_lock (&m);
                pthread_cond_broadcast (&c);
                pthread_mutex_unlock (&m);
                        pthread_cond_wait (&c, &m);
                                pthread_cond_wait (&c, &m);
                                        pthread_cond_signal (&c);
                                        pthread_mutex_unlock (&m);
                pthread_mutex_lock (&m);
                                        pthread_mutex_lock (&m);
[hang]

Detailed:
tao	thread	action
000	1	locks m
000	1	enters cond_wait
000	1	locks c->__data.__lock
000	1	unlocks m
100	1	++total_seq, thr1's seq = 0
100	1	unlocks c->__data.__lock
100	1	futex_wait (&wakeup_seq)
100	2	locks m
100	2	enters cond_wait
100	2	locks c->__data.__lock
100	2	unlocks m
200	2	++total_seq, thr2's seq = 0
200	2	unlocks c->__data.__lock
200	2	futex_wait (&wakeup_seq)
200	3	locks m
200	4	attempts to lock m
200	4	futex_wait (&m->__data.__lock)
200	5	attempts to lock m
200	5	futex_wait (&m->__data.__lock)
200	6	attempts to lock m
200	6	futex_wait (&m->__data.__lock)
200	3	enters cond_broadcast
200	3	locks c->__data.__lock
220	3	wakeup_seq = total_seq
220	3	unlocks c->__data.__lock
220	3	futex_requeue (&wakeup_seq)
[ thr1 awaken, thr2 requeued to mutex ]
220	3	leaves cond_broadcast
220	1	locks c->__data.__lock
220	1	val = 2; val != seq (0) && val != woken_seq (0), no looping
221	1	++woken_seq
221	1	unlocks c->__data.__lock
221	1	attempts to lock m
221	1	futex_wait (&m->__data.__lock)
221	3	unlocks m
221	3	futex_wake (&m->__data.__lock)
[ thr4 awaken ]
221	4	enters cond_wait
221	4	locks c->__data.__lock
221	4	unlocks m
221	4	futex_wake (&m->__data.__lock)
[ thr5 awaken ]
321	4	++total_seq, thr4's seq = 2
321	4	unlocks c->__data.__lock
321	5	enters cond_wait
321	5	locks c->__data.__lock
321	5	unlocks m
321	5	futex_wake (&m->__data.__lock)
[ thr6 awaken ]
421	5	++total_seq, thr5's seq = 2
421	5	unlocks c->__data.__lock
421	6	enters cond_broadcast
421	6	locks c->__data.__lock
431	6	++wakeup_seq
431	6	futex_wake (&wakeup_seq)
[ nobody awaken ]
431	6	unlocks c->__data.__lock
431	4	futex_wait (&wakeup_seq), returns -EWOULDBLOCK immediately
431	4	locks c->__data.__lock
431	4	val = 3; val != seq (2) && val != woken_seq (1), no looping
432	4	++woken_seq
432	4	unlocks c->__data.__lock
432	4	attempts to lock m
432	4	futex_wait (&m->__data.__lock)
432	5	futex_wait (&wakeup_seq), returns -EWOULDBLOCK immediately
432	4	locks c->__data.__lock
432	4	val = 3; val != seq (2) && val != woken_seq (2), no looping
433	4	++woken_seq
433	4	unlocks c->__data.__lock
433	4	attempts to lock m
433	4	futex_wait (&m->__data.__lock)
433	6	unlocks m
433	6	futex_wake (&m->__data.__lock)
[ thr2 awaken ]
433	2	locks c->__data.__lock
433	2	val = 3; val != seq (0), but val == woken_seq (3), therefore loop
433	2	unlocks c->__data.__lock
433	2	futex_wait (&wakeup_seq)
433	3	attempts to lock m
433	3	futex_wait (&m->__data.__lock)
433	6	attempts to lock m
433	6	futex_wait (&m->__data.__lock)
[ hang ]
# thr{1,3,4,5,6} waiting on m->__data.__lock, thr2 waiting on wakeup_seq

Legend:
tao     - total_seq/wakeup_seq/woken_seq

	Jakub