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
24NSYNC_CPP_START_
25
26struct nsync_dll_element_s_;
27struct 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 (&mu;)
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. */
86typedef 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 }
95void 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. */
100void nsync_cv_signal (nsync_cv *cv);
101
102/* Wake all threads currently blocked on *cv. */
103void 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. */
112void 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. */
134int 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. */
140int 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
145NSYNC_CV_CPP_OVERLOAD_
146NSYNC_CPP_END_
147
148#endif /*NSYNC_PUBLIC_NSYNC_CV_H_*/
149