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 | #ifndef NSYNC_PUBLIC_NSYNC_CV_H_ |
16 | #define NSYNC_PUBLIC_NSYNC_CV_H_ |
17 | |
18 | #include <inttypes.h> |
19 | #include "nsync_cpp.h" |
20 | #include "nsync_mu.h" |
21 | #include "nsync_atomic.h" |
22 | #include "nsync_time.h" |
23 | |
24 | NSYNC_CPP_START_ |
25 | |
26 | struct nsync_dll_element_s_; |
27 | struct nsync_note_s_; |
28 | |
29 | /* An nsync_cv is a condition variable in the style of Mesa, Java, POSIX, and Go's sync.Cond. |
30 | It allows a thread to wait for a condition on state protected by a mutex, |
31 | and to proceed with the mutex held and the condition true. |
32 | |
33 | See also nsync_mu_wait() and nsync_mu_wait_with_deadline(), which implement conditional |
34 | critical sections. In many cases, they are easier to use than condition |
35 | variables. |
36 | |
37 | Usage: |
38 | |
39 | after making the desired predicate true, call: |
40 | nsync_cv_signal (&cv); // If at most one thread can make use of the predicate becoming true. |
41 | or |
42 | nsync_cv_broadcast (&cv); // If multiple threads can make use of the predicate becoming true. |
43 | |
44 | To wait for a predicate with no deadline (assuming nsync_cv_broadcast() or |
45 | nsync_cv_signal() is called whenever the predicate becomes true): |
46 | nsync_mu_lock (μ) |
47 | while (!some_predicate_protected_by_mu) { // the while-loop is required. |
48 | nsync_cv_wait (&cv, &mu); |
49 | } |
50 | // predicate is now true |
51 | nsync_mu_unlock (&mu); |
52 | |
53 | To wait for a predicate with a deadline (assuming nsync_cv_broadcast() or |
54 | nsync_cv_signal() is called whenever the predicate becomes true): |
55 | nsync_mu_lock (&mu); |
56 | while (!some_predicate_protected_by_mu && |
57 | nsync_cv_wait_with_deadline (&cv, &mu, abs_deadline, cancel_note) == 0) { |
58 | } |
59 | if (some_predicate_protected_by_mu) { // predicate is true |
60 | } else { // predicate is false, and deadline expired, or cancel_note was notified. |
61 | } |
62 | nsync_mu_unlock (&mu); |
63 | or, if the predicate is complex and you wish to write it just once and |
64 | inline, you could use the following instead of the for-loop above: |
65 | nsync_mu_lock (&mu); |
66 | int pred_is_true = 0; |
67 | int outcome = 0; |
68 | while (!(pred_is_true = some_predicate_protected_by_mu) && outcome == 0) { |
69 | outcome = nsync_cv_wait_with_deadline (&cv, &mu, abs_deadline, cancel_note); |
70 | } |
71 | if (pred_is_true) { // predicate is true |
72 | } else { // predicate is false, and deadline expired, or cancel_note was notified. |
73 | } |
74 | nsync_mu_unlock (&mu); |
75 | |
76 | As the examples show, Mesa-style condition variables require that waits use |
77 | a loop that tests the predicate anew after each wait. It may be surprising |
78 | that these are preferred over the precise wakeups offered by the condition |
79 | variables in Hoare monitors. Imprecise wakeups make more efficient use of |
80 | the critical section, because threads can enter it while a woken thread is |
81 | still emerging from the scheduler, which may take thousands of cycles. |
82 | Further, they make the programme easier to read and debug by making the |
83 | predicate explicit locally at the wait, where the predicate is about to be |
84 | assumed; the reader does not have to infer the predicate by examining all |
85 | the places where wakeups may occur. */ |
86 | typedef struct nsync_cv_s_ { |
87 | nsync_atomic_uint32_ word; /* see bits below */ |
88 | struct nsync_dll_element_s_ *waiters; /* points to tail of list of waiters; under mu. */ |
89 | } nsync_cv; |
90 | |
91 | /* An nsync_cv should be zeroed to initialize, which can be accomplished by |
92 | initializing with static initializer NSYNC_CV_INIT, or by setting the entire |
93 | struct to 0, or using nsync_cv_init(). */ |
94 | #define NSYNC_CV_INIT { NSYNC_ATOMIC_UINT32_INIT_, 0 } |
95 | void nsync_cv_init (nsync_cv *cv); |
96 | |
97 | /* Wake at least one thread if any are currently blocked on *cv. If |
98 | the chosen thread is a reader on an nsync_mu, wake all readers and, if |
99 | possible, a writer. */ |
100 | void nsync_cv_signal (nsync_cv *cv); |
101 | |
102 | /* Wake all threads currently blocked on *cv. */ |
103 | void nsync_cv_broadcast (nsync_cv *cv); |
104 | |
105 | /* Atomically release "mu" (which must be held on entry) and block the caller |
106 | on *cv. Wait until awakened by a call to nsync_cv_signal() or |
107 | nsync_cv_broadcast(), or a spurious wakeup; then reacquire "mu", and return. |
108 | Equivalent to a call to nsync_mu_wait_with_deadline() with |
109 | abs_deadline==nsync_time_no_deadline, and cancel_note==NULL. Callers should use |
110 | nsync_cv_wait() in a loop, as with all standard Mesa-style condition |
111 | variables. See examples above. */ |
112 | void nsync_cv_wait (nsync_cv *cv, nsync_mu *mu); |
113 | |
114 | /* Atomically release "mu" (which must be held on entry) |
115 | and block the calling thread on *cv. It then waits until awakened by a |
116 | call to nsync_cv_signal() or nsync_cv_broadcast() (or a spurious wakeup), or by the time |
117 | reaching abs_deadline, or by cancel_note being notified. In all cases, it |
118 | reacquires "mu", and returns the reason for the call returned (0, ETIMEDOUT, |
119 | or ECANCELED). Use abs_deadline==nsync_time_no_deadline for no deadline, and |
120 | cancel_note==NULL for no cancellation. wait_with_deadline() should be used in a |
121 | loop, as with all Mesa-style condition variables. See examples above. |
122 | |
123 | There are two reasons for using an absolute deadline, rather than a relative |
124 | timeout---these are why pthread_cond_timedwait() also uses an absolute |
125 | deadline. First, condition variable waits have to be used in a loop; with |
126 | an absolute times, the deadline does not have to be recomputed on each |
127 | iteration. Second, in most real programmes, some activity (such as an RPC |
128 | to a server, or when guaranteeing response time in a UI), there is a |
129 | deadline imposed by the specification or the caller/user; relative delays |
130 | can shift arbitrarily with scheduling delays, and so after multiple waits |
131 | might extend beyond the expected deadline. Relative delays tend to be more |
132 | convenient mostly in tests and trivial examples than they are in real |
133 | programmes. */ |
134 | int nsync_cv_wait_with_deadline (nsync_cv *cv, nsync_mu *mu, |
135 | nsync_time abs_deadline, |
136 | struct nsync_note_s_ *cancel_note); |
137 | |
138 | /* Like nsync_cv_wait_with_deadline(), but allow an arbitrary lock *v to be used, |
139 | given its (*lock)(mu) and (*unlock)(mu) routines. */ |
140 | int nsync_cv_wait_with_deadline_generic (nsync_cv *cv, |
141 | void *mu, void (*lock) (void *), void (*unlock) (void *), |
142 | nsync_time abs_deadline, |
143 | struct nsync_note_s_ *cancel_note); |
144 | |
145 | NSYNC_CV_CPP_OVERLOAD_ |
146 | NSYNC_CPP_END_ |
147 | |
148 | #endif /*NSYNC_PUBLIC_NSYNC_CV_H_*/ |
149 | |