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/* 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 */
55static 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. */
64static 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. */
83static 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. */
117static 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 */
144nsync_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
162int 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
170nsync_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
195void 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
238void 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
246int 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
254nsync_time nsync_note_expiry (nsync_note n) {
255 return (n->expiry_time);
256}
257
258static nsync_time note_ready_time (void *v, struct nsync_waiter_s *nw UNUSED) {
259 return (nsync_note_notified_deadline_ ((nsync_note)v));
260}
261
262static 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
280static 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
296const struct nsync_waitable_funcs_s nsync_note_waitable_funcs = {
297 &note_ready_time,
298 &note_enqueue,
299 &note_dequeue
300};
301
302NSYNC_CPP_END_
303