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 | /* Locking discipline for the nsync_note implementation: |
29 | |
30 | Each nsync_note has a lock "note_mu" which protects the "parent" pointer, |
31 | "waiters" list, and "disconnecting" count. It also protects the "children" |
32 | list; thus each node's "parent_child_link", which links together the |
33 | children of a single parent, is protected by the parent's "note_mu". |
34 | |
35 | To connect a parent to a child, or to disconnect one, the parent's lock must |
36 | be held to manipulate its child list, and the child's lock must be held to |
37 | change the parent pointer, so both must be held simultaneously. |
38 | The locking order is "parent before child". |
39 | |
40 | Operations like notify and free are given a node pointer n and must |
41 | disconnect *n from its parent n->parent. The call must hold n->note_mu to |
42 | read n->parent, but need to release n->note_mu to acquire |
43 | n->parent->note_mu. The parent could be disconnected and freed while |
44 | n->note_mu is not held. The n->disconnecting count handles this; the |
45 | operation acquires n->note_mu, increments n->disconnecting, and can then |
46 | release n->note_mu, and acquire n->parent->note_mu and n->note_mu is the |
47 | correct order. n->disconnecting!=0 indicates that a thread is already in |
48 | the processes of disconnecting n from n->parent. A thread freeing or |
49 | notifying the parent should not perform the disconnection of that child, but |
50 | should instead wait for the "children" list to become empty via |
51 | WAIT_FOR_NO_CHILDREN(). WAKEUP_NO_CHILDREN() should be used whenever this |
52 | condition could become true. */ |
53 | |
54 | /* Set the expiry time in *n to t */ |
55 | static void set_expiry_time (nsync_note n, nsync_time t) { |
56 | n->expiry_time = t; |
57 | n->expiry_time_valid = 1; |
58 | } |
59 | |
60 | /* Return a pointer to the note containing nsync_dll_element_ *e. */ |
61 | #define DLL_NOTE(e) ((nsync_note)((e)->container)) |
62 | |
63 | /* Return whether n->children is empty. Assumes n->note_mu held. */ |
64 | static int no_children (const void *v) { |
65 | return (nsync_dll_is_empty_ (((nsync_note)v)->children)); |
66 | } |
67 | |
68 | #define WAIT_FOR_NO_CHILDREN(pred_, n_) nsync_mu_wait (&(n_)->note_mu, &pred_, (n_), NULL) |
69 | #define WAKEUP_NO_CHILDREN(n_) do { } while (0) |
70 | |
71 | /* |
72 | // These lines can be used in place of those above if conditional critical |
73 | // sections have been removed from the source. |
74 | #define WAIT_FOR_NO_CHILDREN(pred_, n_) do { \ |
75 | while (!pred_ (n_)) { nsync_cv_wait (&(n_)->no_children_cv, &(n_)->note_mu); } \ |
76 | } while (0) |
77 | #define WAKEUP_NO_CHILDREN(n_) nsync_cv_broadcast (&(n_)->no_children_cv) |
78 | */ |
79 | |
80 | /* Notify *n and all its descendants that are not already disconnnecting. |
81 | n->note_mu is held. May release and reacquire n->note_mu. |
82 | parent->note_mu is held if parent != NULL. */ |
83 | static void note_notify_child (nsync_note n, nsync_note parent) { |
84 | nsync_time t; |
85 | t = NOTIFIED_TIME (n); |
86 | if (nsync_time_cmp (t, nsync_time_zero) > 0) { |
87 | nsync_dll_element_ *p; |
88 | nsync_dll_element_ *next; |
89 | ATM_STORE_REL (&n->notified, 1); |
90 | while ((p = nsync_dll_first_ (n->waiters)) != NULL) { |
91 | struct nsync_waiter_s *nw = DLL_NSYNC_WAITER (p); |
92 | n->waiters = nsync_dll_remove_ (n->waiters, p); |
93 | ATM_STORE_REL (&nw->waiting, 0); |
94 | nsync_mu_semaphore_v (nw->sem); |
95 | } |
96 | for (p = nsync_dll_first_ (n->children); p != NULL; p = next) { |
97 | nsync_note child = DLL_NOTE (p); |
98 | next = nsync_dll_next_ (n->children, p); |
99 | nsync_mu_lock (&child->note_mu); |
100 | if (child->disconnecting == 0) { |
101 | note_notify_child (child, n); |
102 | } |
103 | nsync_mu_unlock (&child->note_mu); |
104 | } |
105 | WAIT_FOR_NO_CHILDREN (no_children, n); |
106 | if (parent != NULL) { |
107 | parent->children = nsync_dll_remove_ (parent->children, |
108 | &n->parent_child_link); |
109 | WAKEUP_NO_CHILDREN (parent); |
110 | n->parent = NULL; |
111 | } |
112 | } |
113 | } |
114 | |
115 | /* Notify *n and all its descendants that are not already disconnnecting. |
116 | No locks are held. */ |
117 | static void notify (nsync_note n) { |
118 | nsync_time t; |
119 | nsync_mu_lock (&n->note_mu); |
120 | t = NOTIFIED_TIME (n); |
121 | if (nsync_time_cmp (t, nsync_time_zero) > 0) { |
122 | nsync_note parent; |
123 | n->disconnecting++; |
124 | parent = n->parent; |
125 | if (parent != NULL && !nsync_mu_trylock (&parent->note_mu)) { |
126 | nsync_mu_unlock (&n->note_mu); |
127 | nsync_mu_lock (&parent->note_mu); |
128 | nsync_mu_lock (&n->note_mu); |
129 | } |
130 | note_notify_child (n, parent); |
131 | if (parent != NULL) { |
132 | nsync_mu_unlock (&parent->note_mu); |
133 | } |
134 | n->disconnecting--; |
135 | } |
136 | nsync_mu_unlock (&n->note_mu); |
137 | } |
138 | |
139 | /* Return the deadline by which *n is certain to be notified, |
140 | setting it to zero if it already has passed that time. |
141 | Requires n->note_mu not held on entry. |
142 | |
143 | Not static; used in sem_wait.c */ |
144 | nsync_time nsync_note_notified_deadline_ (nsync_note n) { |
145 | nsync_time ntime; |
146 | if (ATM_LOAD_ACQ (&n->notified) != 0) { |
147 | ntime = nsync_time_zero; |
148 | } else { |
149 | nsync_mu_lock (&n->note_mu); |
150 | ntime = NOTIFIED_TIME (n); |
151 | nsync_mu_unlock (&n->note_mu); |
152 | if (nsync_time_cmp (ntime, nsync_time_zero) > 0) { |
153 | if (nsync_time_cmp (ntime, nsync_time_now ()) <= 0) { |
154 | notify (n); |
155 | ntime = nsync_time_zero; |
156 | } |
157 | } |
158 | } |
159 | return (ntime); |
160 | } |
161 | |
162 | int nsync_note_is_notified (nsync_note n) { |
163 | int result; |
164 | IGNORE_RACES_START (); |
165 | result = (nsync_time_cmp (nsync_note_notified_deadline_ (n), nsync_time_zero) <= 0); |
166 | IGNORE_RACES_END (); |
167 | return (result); |
168 | } |
169 | |
170 | nsync_note nsync_note_new (nsync_note parent, |
171 | nsync_time abs_deadline) { |
172 | nsync_note n = (nsync_note) malloc (sizeof (*n)); |
173 | if (n != NULL) { |
174 | memset ((void *) n, 0, sizeof (*n)); |
175 | nsync_dll_init_ (&n->parent_child_link, n); |
176 | set_expiry_time (n, abs_deadline); |
177 | if (!nsync_note_is_notified (n) && parent != NULL) { |
178 | nsync_time parent_time; |
179 | nsync_mu_lock (&parent->note_mu); |
180 | parent_time = NOTIFIED_TIME (parent); |
181 | if (nsync_time_cmp (parent_time, abs_deadline) < 0) { |
182 | set_expiry_time (n, parent_time); |
183 | } |
184 | if (nsync_time_cmp (parent_time, nsync_time_zero) > 0) { |
185 | n->parent = parent; |
186 | parent->children = nsync_dll_make_last_in_list_ (parent->children, |
187 | &n->parent_child_link); |
188 | } |
189 | nsync_mu_unlock (&parent->note_mu); |
190 | } |
191 | } |
192 | return (n); |
193 | } |
194 | |
195 | void nsync_note_free (nsync_note n) { |
196 | nsync_note parent; |
197 | nsync_dll_element_ *p; |
198 | nsync_dll_element_ *next; |
199 | nsync_mu_lock (&n->note_mu); |
200 | n->disconnecting++; |
201 | ASSERT (nsync_dll_is_empty_ (n->waiters)); |
202 | parent = n->parent; |
203 | if (parent != NULL && !nsync_mu_trylock (&parent->note_mu)) { |
204 | nsync_mu_unlock (&n->note_mu); |
205 | nsync_mu_lock (&parent->note_mu); |
206 | nsync_mu_lock (&n->note_mu); |
207 | } |
208 | for (p = nsync_dll_first_ (n->children); p != NULL; p = next) { |
209 | nsync_note child = DLL_NOTE (p); |
210 | next = nsync_dll_next_ (n->children, p); |
211 | nsync_mu_lock (&child->note_mu); |
212 | if (child->disconnecting == 0) { |
213 | n->children = nsync_dll_remove_ (n->children, |
214 | &child->parent_child_link); |
215 | if (parent != NULL) { |
216 | child->parent = parent; |
217 | parent->children = nsync_dll_make_last_in_list_ ( |
218 | parent->children, &child->parent_child_link); |
219 | } else { |
220 | child->parent = NULL; |
221 | } |
222 | } |
223 | nsync_mu_unlock (&child->note_mu); |
224 | } |
225 | WAIT_FOR_NO_CHILDREN (no_children, n); |
226 | if (parent != NULL) { |
227 | parent->children = nsync_dll_remove_ (parent->children, |
228 | &n->parent_child_link); |
229 | WAKEUP_NO_CHILDREN (parent); |
230 | n->parent = NULL; |
231 | nsync_mu_unlock (&parent->note_mu); |
232 | } |
233 | n->disconnecting--; |
234 | nsync_mu_unlock (&n->note_mu); |
235 | free (n); |
236 | } |
237 | |
238 | void nsync_note_notify (nsync_note n) { |
239 | IGNORE_RACES_START (); |
240 | if (nsync_time_cmp (nsync_note_notified_deadline_ (n), nsync_time_zero) > 0) { |
241 | notify (n); |
242 | } |
243 | IGNORE_RACES_END (); |
244 | } |
245 | |
246 | int nsync_note_wait (nsync_note n, nsync_time abs_deadline) { |
247 | struct nsync_waitable_s waitable; |
248 | struct nsync_waitable_s *pwaitable = &waitable; |
249 | waitable.v = n; |
250 | waitable.funcs = &nsync_note_waitable_funcs; |
251 | return (nsync_wait_n (NULL, NULL, NULL, abs_deadline, 1, &pwaitable) == 0); |
252 | } |
253 | |
254 | nsync_time nsync_note_expiry (nsync_note n) { |
255 | return (n->expiry_time); |
256 | } |
257 | |
258 | static nsync_time note_ready_time (void *v, struct nsync_waiter_s *nw UNUSED) { |
259 | return (nsync_note_notified_deadline_ ((nsync_note)v)); |
260 | } |
261 | |
262 | static int note_enqueue (void *v, struct nsync_waiter_s *nw) { |
263 | int waiting = 0; |
264 | nsync_note n = (nsync_note) v; |
265 | nsync_time ntime; |
266 | nsync_mu_lock (&n->note_mu); |
267 | ntime = NOTIFIED_TIME (n); |
268 | if (nsync_time_cmp (ntime, nsync_time_zero) > 0) { |
269 | n->waiters = nsync_dll_make_last_in_list_ (n->waiters, &nw->q); |
270 | ATM_STORE (&nw->waiting, 1); |
271 | waiting = 1; |
272 | } else { |
273 | ATM_STORE (&nw->waiting, 0); |
274 | waiting = 0; |
275 | } |
276 | nsync_mu_unlock (&n->note_mu); |
277 | return (waiting); |
278 | } |
279 | |
280 | static int note_dequeue (void *v, struct nsync_waiter_s *nw) { |
281 | int was_queued = 0; |
282 | nsync_note n = (nsync_note) v; |
283 | nsync_time ntime; |
284 | nsync_note_notified_deadline_ (n); |
285 | nsync_mu_lock (&n->note_mu); |
286 | ntime = NOTIFIED_TIME (n); |
287 | if (nsync_time_cmp (ntime, nsync_time_zero) > 0) { |
288 | n->waiters = nsync_dll_remove_ (n->waiters, &nw->q); |
289 | ATM_STORE (&nw->waiting, 0); |
290 | was_queued = 1; |
291 | } |
292 | nsync_mu_unlock (&n->note_mu); |
293 | return (was_queued); |
294 | } |
295 | |
296 | const struct nsync_waitable_funcs_s nsync_note_waitable_funcs = { |
297 | ¬e_ready_time, |
298 | ¬e_enqueue, |
299 | ¬e_dequeue |
300 | }; |
301 | |
302 | NSYNC_CPP_END_ |
303 | |