1#include "pthread_impl.h"
2
3/*
4 * struct waiter
5 *
6 * Waiter objects have automatic storage on the waiting thread, and
7 * are used in building a linked list representing waiters currently
8 * waiting on the condition variable or a group of waiters woken
9 * together by a broadcast or signal; in the case of signal, this is a
10 * degenerate list of one member.
11 *
12 * Waiter lists attached to the condition variable itself are
13 * protected by the lock on the cv. Detached waiter lists are never
14 * modified again, but can only be traversed in reverse order, and are
15 * protected by the "barrier" locks in each node, which are unlocked
16 * in turn to control wake order.
17 *
18 * Since process-shared cond var semantics do not necessarily allow
19 * one thread to see another's automatic storage (they may be in
20 * different processes), the waiter list is not used for the
21 * process-shared case, but the structure is still used to store data
22 * needed by the cancellation cleanup handler.
23 */
24
25struct waiter {
26	struct waiter *prev, *next;
27	volatile int state, barrier;
28	volatile int *notify;
29};
30
31/* Self-synchronized-destruction-safe lock functions */
32
33static inline void lock(volatile int *l)
34{
35	if (a_cas(l, 0, 1)) {
36		a_cas(l, 1, 2);
37		do __wait(l, 0, 2, 1);
38		while (a_cas(l, 0, 2));
39	}
40}
41
42static inline void unlock(volatile int *l)
43{
44	if (a_swap(l, 0)==2)
45		__wake(l, 1, 1);
46}
47
48static inline void unlock_requeue(volatile int *l, volatile int *r, int w)
49{
50	a_store(l, 0);
51	if (w) __wake(l, 1, 1);
52	else __syscall(SYS_futex, l, FUTEX_REQUEUE|FUTEX_PRIVATE, 0, 1, r) != -ENOSYS
53		|| __syscall(SYS_futex, l, FUTEX_REQUEUE, 0, 1, r);
54}
55
56enum {
57	WAITING,
58	SIGNALED,
59	LEAVING,
60};
61
62int __pthread_cond_timedwait(pthread_cond_t *restrict c, pthread_mutex_t *restrict m, const struct timespec *restrict ts)
63{
64	struct waiter node = { 0 };
65	int e, seq, clock = c->_c_clock, cs, shared=0, oldstate, tmp;
66	volatile int *fut;
67
68	if ((m->_m_type&15) && (m->_m_lock&INT_MAX) != __pthread_self()->tid)
69		return EPERM;
70
71	if (ts && ts->tv_nsec >= 1000000000UL)
72		return EINVAL;
73
74	__pthread_testcancel();
75
76	if (c->_c_shared) {
77		shared = 1;
78		fut = &c->_c_seq;
79		seq = c->_c_seq;
80		a_inc(&c->_c_waiters);
81	} else {
82		lock(&c->_c_lock);
83
84		seq = node.barrier = 2;
85		fut = &node.barrier;
86		node.state = WAITING;
87		node.next = c->_c_head;
88		c->_c_head = &node;
89		if (!c->_c_tail) c->_c_tail = &node;
90		else node.next->prev = &node;
91
92		unlock(&c->_c_lock);
93	}
94
95	__pthread_mutex_unlock(m);
96
97	__pthread_setcancelstate(PTHREAD_CANCEL_MASKED, &cs);
98	if (cs == PTHREAD_CANCEL_DISABLE) __pthread_setcancelstate(cs, 0);
99
100	do e = __timedwait_cp(fut, seq, clock, ts, !shared);
101	while (*fut==seq && (!e || e==EINTR));
102	if (e == EINTR) e = 0;
103
104	if (shared) {
105		/* Suppress cancellation if a signal was potentially
106		 * consumed; this is a legitimate form of spurious
107		 * wake even if not. */
108		if (e == ECANCELED && c->_c_seq != seq) e = 0;
109		if (a_fetch_add(&c->_c_waiters, -1) == -0x7fffffff)
110			__wake(&c->_c_waiters, 1, 0);
111		oldstate = WAITING;
112		goto relock;
113	}
114
115	oldstate = a_cas(&node.state, WAITING, LEAVING);
116
117	if (oldstate == WAITING) {
118		/* Access to cv object is valid because this waiter was not
119		 * yet signaled and a new signal/broadcast cannot return
120		 * after seeing a LEAVING waiter without getting notified
121		 * via the futex notify below. */
122
123		lock(&c->_c_lock);
124
125		if (c->_c_head == &node) c->_c_head = node.next;
126		else if (node.prev) node.prev->next = node.next;
127		if (c->_c_tail == &node) c->_c_tail = node.prev;
128		else if (node.next) node.next->prev = node.prev;
129
130		unlock(&c->_c_lock);
131
132		if (node.notify) {
133			if (a_fetch_add(node.notify, -1)==1)
134				__wake(node.notify, 1, 1);
135		}
136	} else {
137		/* Lock barrier first to control wake order. */
138		lock(&node.barrier);
139	}
140
141relock:
142	/* Errors locking the mutex override any existing error or
143	 * cancellation, since the caller must see them to know the
144	 * state of the mutex. */
145	if ((tmp = pthread_mutex_lock(m))) e = tmp;
146
147	if (oldstate == WAITING) goto done;
148
149	if (!node.next && !(m->_m_type & 8))
150		a_inc(&m->_m_waiters);
151
152	/* Unlock the barrier that's holding back the next waiter, and
153	 * either wake it or requeue it to the mutex. */
154	if (node.prev) {
155		int val = m->_m_lock;
156		if (val>0) a_cas(&m->_m_lock, val, val|0x80000000);
157		unlock_requeue(&node.prev->barrier, &m->_m_lock, m->_m_type & (8|128));
158	} else if (!(m->_m_type & 8)) {
159		a_dec(&m->_m_waiters);
160	}
161
162	/* Since a signal was consumed, cancellation is not permitted. */
163	if (e == ECANCELED) e = 0;
164
165done:
166	__pthread_setcancelstate(cs, 0);
167
168	if (e == ECANCELED) {
169		__pthread_testcancel();
170		__pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, 0);
171	}
172
173	return e;
174}
175
176int __private_cond_signal(pthread_cond_t *c, int n)
177{
178	struct waiter *p, *first=0;
179	volatile int ref = 0;
180	int cur;
181
182	lock(&c->_c_lock);
183	for (p=c->_c_tail; n && p; p=p->prev) {
184		if (a_cas(&p->state, WAITING, SIGNALED) != WAITING) {
185			ref++;
186			p->notify = &ref;
187		} else {
188			n--;
189			if (!first) first=p;
190		}
191	}
192	/* Split the list, leaving any remainder on the cv. */
193	if (p) {
194		if (p->next) p->next->prev = 0;
195		p->next = 0;
196	} else {
197		c->_c_head = 0;
198	}
199	c->_c_tail = p;
200	unlock(&c->_c_lock);
201
202	/* Wait for any waiters in the LEAVING state to remove
203	 * themselves from the list before returning or allowing
204	 * signaled threads to proceed. */
205	while ((cur = ref)) __wait(&ref, 0, cur, 1);
206
207	/* Allow first signaled waiter, if any, to proceed. */
208	if (first) unlock(&first->barrier);
209
210	return 0;
211}
212
213weak_alias(__pthread_cond_timedwait, pthread_cond_timedwait);
214