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 | |
26 | NSYNC_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. */ |
66 | static 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. */ |
140 | int 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. */ |
279 | void 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. */ |
297 | void 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 | |
319 | NSYNC_CPP_END_ |
320 | |