1/* Copyright 2016 Google Inc.
2
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License. */
14
15#include "nsync_cpp.h"
16#include "platform.h"
17#include "compiler.h"
18#include "cputype.h"
19#include "nsync.h"
20#include "dll.h"
21#include "sem.h"
22#include "wait_internal.h"
23#include "common.h"
24#include "atomic.h"
25
26NSYNC_CPP_START_
27
28/* Attempt to remove waiter *w from *mu's
29 waiter queue. If successful, leave the lock held in mode *l_type, and
30 return non-zero; otherwise return zero. Requires that the current thread
31 hold neither *mu nor its spinlock, that remove_count be the value of
32 w.remove_count when *w was inserted into the queue (which it will still be if
33 it has not been removed).
34
35 This is a tricky part of the design. Here is the rationale.
36
37 When a condition times out or is cancelled, we must "turn off" the
38 condition, making it always true, so the lock will be acquired in the normal
39 way. The naive approach would be to set a field atomically to tell future
40 waiters to ignore the condition. Unfortunately, that would violate the
41 same_condition list invariants, and the same_condition optimization is
42 probably worth keeping.
43
44 To fixup the same_condition list, we must have mutual exclusion with the loop
45 in nsync_mu_unlock_slow_() that is examining waiters, evaluating their conditions, and
46 removing them from the queue. That loop uses both the spinlock (to allow
47 queue changes), and the mutex itself (to allow condition evaluation).
48 Therefore, to "turn off" the condition requires acquiring both the spinlock
49 and the mutex. This has two consequences:
50 - If we must acquire *mu to "turn off" the condition, we might as well give
51 the lock to this waiter and return from nsync_cv_wait_with_deadline() after we've
52 done so. It would be wasted work to put it back on the waiter queue, and
53 have it wake up and acquire yet again. (There are possibilities for
54 starvation here that we ignore, under the assumption that the client
55 avoids timeouts that are extremely short relative to the durations of his
56 section durations.)
57 - We can't use *w to wait for the lock to be free, because *w is already on
58 the waiter queue with the wrong condition; we now want to wait with no
59 condition. So either we must spin to acquire the lock, or we must
60 allocate _another_ waiter object. The latter option is feasible, but
61 delicate: the thread would have two waiter objects, and would have to
62 handle being woken by either one or both, and possibly removing one that
63 was not awoken. For the moment, we spin, because it's easier, and seems
64 not to cause problems in practice, since the spinloop backs off
65 aggressively. */
66static int mu_try_acquire_after_timeout_or_cancel (nsync_mu *mu, lock_type *l_type,
67 waiter *w, uint32_t remove_count) {
68 int success = 0;
69 unsigned spin_attempts = 0;
70 uint32_t old_word = ATM_LOAD (&mu->word);
71 /* Spin until we can acquire the spinlock and a writer lock on *mu. */
72 while ((old_word&(MU_WZERO_TO_ACQUIRE|MU_SPINLOCK)) != 0 ||
73 !ATM_CAS_ACQ (&mu->word, old_word,
74 (old_word+MU_WADD_TO_ACQUIRE+MU_SPINLOCK) &
75 ~MU_WCLEAR_ON_ACQUIRE)) {
76 /* Failed to acquire. If we can, set the MU_WRITER_WAITING bit
77 to avoid being starved by readers. */
78 if ((old_word & (MU_WRITER_WAITING | MU_SPINLOCK)) == 0) {
79 /* If the following CAS succeeds, it effectively
80 acquires and releases the spinlock atomically, so
81 must be both an acquire and release barrier.
82 MU_WRITER_WAITING will be cleared via
83 MU_WCLEAR_ON_ACQUIRE when this loop succeeds.
84 An optimization; failures are ignored. */
85 ATM_CAS_RELACQ (&mu->word, old_word,
86 old_word|MU_WRITER_WAITING);
87 }
88 spin_attempts = nsync_spin_delay_ (spin_attempts);
89 old_word = ATM_LOAD (&mu->word);
90 }
91 /* Check that w wasn't removed from the queue after our caller checked,
92 but before we acquired the spinlock.
93 The check of remove_count confirms that the waiter *w is still
94 governed by *mu's spinlock. Otherwise, some other thread may be
95 about to set w.waiting==0. */
96 if (ATM_LOAD (&w->nw.waiting) != 0 && remove_count == ATM_LOAD (&w->remove_count)) {
97 /* This thread's condition is now irrelevant, and it
98 holds a writer lock. Remove it from the queue,
99 and possibly convert back to a reader lock. */
100 mu->waiters = nsync_remove_from_mu_queue_ (mu->waiters, &w->nw.q);
101 ATM_STORE (&w->nw.waiting, 0);
102
103 /* Release spinlock but keep desired lock type. */
104 ATM_STORE_REL (&mu->word, old_word+l_type->add_to_acquire); /* release store */
105 success = 1;
106 } else {
107 /* Release spinlock and *mu. */
108 ATM_STORE_REL (&mu->word, old_word); /* release store */
109 }
110 return (success);
111}
112
113/* Return when at least one of: the condition is true, the
114 deadline expires, or cancel_note is notified. It may unlock and relock *mu
115 while blocked waiting for one of these events, but always returns with *mu
116 held. It returns 0 iff the condition is true on return, and otherwise
117 either ETIMEDOUT or ECANCELED, depending on why the call returned early. Use
118 abs_deadline==nsync_time_no_deadline for no deadline, and cancel_note==NULL for no
119 cancellation.
120
121 Requires that *mu be held on entry.
122 Requires that condition.eval() neither modify state protected by *mu, nor
123 return a value dependent on state not protected by *mu. To depend on time,
124 use the abs_deadline parameter.
125 (Conventional use of condition variables have the same restrictions on the
126 conditions tested by the while-loop.)
127 The implementation calls condition.eval() only with *mu held, though not
128 always from the calling thread, and may elect to hold only a read lock
129 during the call, even if the client is attempting to acquire only write
130 locks.
131
132 The nsync_mu_wait() and nsync_mu_wait_with_deadline() calls can be used instead of condition
133 variables. In many straightforward situations they are of equivalent
134 performance and are somewhat easier to use, because unlike condition
135 variables, they do not require that the waits be placed in a loop, and they
136 do not require explicit wakeup calls. In the current implementation, use of
137 nsync_mu_wait() and nsync_mu_wait_with_deadline() can take longer if many distinct
138 wait conditions are used. In such cases, use an explicit condition variable
139 per wakeup condition for best performance. */
140int nsync_mu_wait_with_deadline (nsync_mu *mu,
141 int (*condition) (const void *condition_arg),
142 const void *condition_arg,
143 int (*condition_arg_eq) (const void *a, const void *b),
144 nsync_time abs_deadline, nsync_note cancel_note) {
145 lock_type *l_type;
146 int first_wait;
147 int condition_is_true;
148 waiter *w;
149 int outcome;
150 /* Work out in which mode the lock is held. */
151 uint32_t old_word;
152 IGNORE_RACES_START ();
153 old_word = ATM_LOAD (&mu->word);
154 if ((old_word & MU_ANY_LOCK) == 0) {
155 nsync_panic_ ("nsync_mu not held in some mode when calling "
156 "nsync_mu_wait_with_deadline()\n");
157 }
158 l_type = nsync_writer_type_;
159 if ((old_word & MU_RHELD_IF_NON_ZERO) != 0) {
160 l_type = nsync_reader_type_;
161 }
162
163 first_wait = 1; /* first time through the loop below. */
164 condition_is_true = (condition == NULL || (*condition) (condition_arg));
165
166 /* Loop until either the condition becomes true, or "outcome" indicates
167 cancellation or timeout. */
168 w = NULL;
169 outcome = 0;
170 while (outcome == 0 && !condition_is_true) {
171 uint32_t has_condition;
172 uint32_t remove_count;
173 uint32_t add_to_acquire;
174 int had_waiters;
175 int sem_outcome;
176 unsigned attempts;
177 int have_lock;
178 if (w == NULL) {
179 w = nsync_waiter_new_ (); /* get a waiter struct if we need one. */
180 }
181
182 /* Prepare to wait. */
183 w->cv_mu = NULL; /* not a condition variable wait */
184 w->l_type = l_type;
185 w->cond.f = condition;
186 w->cond.v = condition_arg;
187 w->cond.eq = condition_arg_eq;
188 has_condition = 0; /* set to MU_CONDITION if condition is non-NULL */
189 if (condition != NULL) {
190 has_condition = MU_CONDITION;
191 }
192 ATM_STORE (&w->nw.waiting, 1);
193 remove_count = ATM_LOAD (&w->remove_count);
194
195 /* Acquire spinlock. */
196 old_word = nsync_spin_test_and_set_ (&mu->word, MU_SPINLOCK,
197 MU_SPINLOCK|MU_WAITING|has_condition, MU_ALL_FALSE);
198 had_waiters = ((old_word & (MU_DESIG_WAKER | MU_WAITING)) == MU_WAITING);
199 /* Queue the waiter. */
200 if (first_wait) {
201 nsync_maybe_merge_conditions_ (nsync_dll_last_ (mu->waiters),
202 &w->nw.q);
203 /* first wait goes to end of queue */
204 mu->waiters = nsync_dll_make_last_in_list_ (mu->waiters,
205 &w->nw.q);
206 first_wait = 0;
207 } else {
208 nsync_maybe_merge_conditions_ (&w->nw.q,
209 nsync_dll_first_ (mu->waiters));
210 /* subsequent waits go to front of queue */
211 mu->waiters = nsync_dll_make_first_in_list_ (mu->waiters,
212 &w->nw.q);
213 }
214 /* Release spinlock and *mu. */
215 do {
216 old_word = ATM_LOAD (&mu->word);
217 add_to_acquire = l_type->add_to_acquire;
218 if (((old_word-l_type->add_to_acquire)&MU_ANY_LOCK) == 0 && had_waiters) {
219 add_to_acquire = 0; /* release happens in nsync_mu_unlock_slow_ */
220 }
221 } while (!ATM_CAS_REL (&mu->word, old_word,
222 (old_word - add_to_acquire) & ~MU_SPINLOCK));
223 if (add_to_acquire == 0) {
224 /* The lock will be fully released, there are waiters, and
225 no designated waker, so wake waiters. */
226 nsync_mu_unlock_slow_ (mu, l_type);
227 }
228
229 /* wait until awoken or a timeout. */
230 sem_outcome = 0;
231 attempts = 0;
232 have_lock = 0;
233 while (ATM_LOAD_ACQ (&w->nw.waiting) != 0) { /* acquire load */
234 if (sem_outcome == 0) {
235 sem_outcome = nsync_sem_wait_with_cancel_ (w, abs_deadline,
236 cancel_note);
237 if (sem_outcome != 0 && ATM_LOAD (&w->nw.waiting) != 0) {
238 /* A timeout or cancellation occurred, and no wakeup.
239 Acquire the spinlock and mu, and confirm. */
240 have_lock = mu_try_acquire_after_timeout_or_cancel (
241 mu, l_type, w, remove_count);
242 if (have_lock) { /* Successful acquire. */
243 outcome = sem_outcome;
244 }
245 }
246 }
247
248 if (ATM_LOAD (&w->nw.waiting) != 0) {
249 attempts = nsync_spin_delay_ (attempts); /* will ultimately yield */
250 }
251 }
252
253 if (!have_lock) {
254 /* If we didn't reacquire due to a cancellation/timeout, acquire now. */
255 nsync_mu_lock_slow_ (mu, w, MU_DESIG_WAKER, l_type);
256 }
257 condition_is_true = (condition == NULL || (*condition) (condition_arg));
258 }
259 if (w != NULL) {
260 nsync_waiter_free_ (w); /* free waiter if we allocated one. */
261 }
262 if (condition_is_true) {
263 outcome = 0; /* condition is true trumps other outcomes. */
264 }
265 IGNORE_RACES_END ();
266 return (outcome);
267}
268
269/* Return when the condition is true. Perhaps unlock and relock *mu
270 while blocked waiting for the condition to become true. It is equivalent to
271 a call to nsync_mu_wait_with_deadline() with abs_deadline==nsync_time_no_deadline, and
272 cancel_note==NULL.
273
274 Requires that *mu be held on entry.
275 Calls condition.eval() only with *mu held, though not always from the
276 calling thread.
277 See wait_with_deadline() for the restrictions on condition and performance
278 considerations. */
279void nsync_mu_wait (nsync_mu *mu, int (*condition) (const void *condition_arg),
280 const void *condition_arg,
281 int (*condition_arg_eq) (const void *a, const void *b)) {
282 if (nsync_mu_wait_with_deadline (mu, condition, condition_arg, condition_arg_eq,
283 nsync_time_no_deadline, NULL) != 0) {
284 nsync_panic_ ("nsync_mu_wait woke but condition not true\n");
285 }
286}
287
288/* Unlock *mu, which must be held in write mode, and wake waiters, if
289 appropriate. Unlike nsync_mu_unlock(), this call is not required to wake
290 nsync_mu_wait/nsync_mu_wait_with_deadline calls on conditions that were
291 false before this thread acquired the lock. This call should be used only
292 at the end of critical sections for which:
293 - nsync_mu_wait/nsync_mu_wait_with_deadline are in use on the same mutex,
294 - this critical section cannot make the condition true for any of those
295 nsync_mu_wait/nsync_mu_wait_with_deadline waits, and
296 - when performance is significantly improved by doing so. */
297void nsync_mu_unlock_without_wakeup (nsync_mu *mu) {
298 IGNORE_RACES_START ();
299 /* See comment in nsync_mu_unlock(). */
300 if (!ATM_CAS_REL (&mu->word, MU_WLOCK, 0)) {
301 uint32_t old_word = ATM_LOAD (&mu->word);
302 uint32_t new_word = old_word - MU_WLOCK;
303 if ((new_word & (MU_RLOCK_FIELD | MU_WLOCK)) != 0) {
304 if ((old_word & MU_RLOCK_FIELD) != 0) {
305 nsync_panic_ ("attempt to nsync_mu_unlock() an nsync_mu "
306 "held in read mode\n");
307 } else {
308 nsync_panic_ ("attempt to nsync_mu_unlock() an nsync_mu "
309 "not held in write mode\n");
310 }
311 } else if ((old_word & (MU_WAITING | MU_DESIG_WAKER | MU_ALL_FALSE)) ==
312 MU_WAITING || !ATM_CAS_REL (&mu->word, old_word, new_word)) {
313 nsync_mu_unlock_slow_ (mu, nsync_writer_type_);
314 }
315 }
316 IGNORE_RACES_END ();
317}
318
319NSYNC_CPP_END_
320