tst-cond16 hang analysis

[Jakub Jelinek]

Hi!

This is posted mainly for archival purposes.
It describes what happens with NPTL CVS as of 2004-05-19 (i.e. after
broadcast_seq has been added; the analysis would be slightly different
before broadcast_seq has been introduced, but the hang has been there
as well (simply remove the b column, ", bc_seq = N" assignments,
++broadcast_seq line and bc_seq == broadcast_seq comparison).

thr1	thr2	thr3
pthread_mutex_lock (&m);
pthread_cond_wait (&c, &m);
	pthread_mutex_lock (&m);
	pthread_mutex_unlock (&m);
	pthread_cond_broadcast (&c);
		pthread_mutex_lock (&m);
		pthread_cond_wait (&c);
	pthread_mutex_lock &m);
	pthread_cond_wait (&c, &m);
[ hang ]
# Normally following would happen afterwards:
pthread_mutex_unlock (&m);
pthread_mutex_lock (&m);
pthread_mutex_unlock (&m);
pthread_cond_broadcast (&c);
and the waiters would be awaken.

Detailed:
taob	thread	action
0000	1	locks m
0000	1	enters cond_wait
0000	1	locks c->__data.__lock
0000	1	unlocks m
1000	1	++total_seq, thr1's seq = 0, bc_seq = 0
1000	1	unlocks c->__data.__lock
1000	2	locks m
1000	2	unlocks m
1000	2	enters cond_broadcast
1000	2	locks c->__data.__lock
1110	2	wakeup_seq = woken_seq = total_seq
1111	2	++broadcast_seq
1111	2	unlocks c->__data.__lock
1111	3	locks m
1111	3	enters cond_wait
1111	3	locks c->__data.__lock
1111	3	unlocks m
2111	3	++total_seq, thr3's seq = 1, bc_seq = 1
2111	3	unlocks c->__data.__lock
2111	3	futex_wait (&wakeup_seq)
2111	1	futex_wait (&wakeup_seq)
2111	2	futex_requeue
[ thr3 awaken, thr1 requeued to mutex ]
2111	3	locks c->__data.__lock
2111	3	bc_seq (1) == broadcast_seq, no early exit
2111	3	val = 1; val == seq (1), val (1) == woken_seq (1), therefore loop
2111	3	unlocks c->__data.__lock
2111	3	futex_wait (&wakeup_seq)
2111	2	locks m
[ note, m->__data.__lock went from 0 to 1 ]
2111	2	enters cond_wait
2111	2	locks c->__data.__lock
2111	2	unlocks m
[ note, m->__data.__lock went from 1 to 0, so thr1 has not been awaken ]
3111	2	++total_seq, thr1's seq = 1, bc_seq = 1
3111	2	unlocks c->__data.__lock
3111	1	futex_wait (&wakeup_seq)
[ hang ]

Legend:
taob	total_seq/wakeup_seq/woken_seq/broadcast_seq

	Jakub