2 * Copyright (c) 2013, 2014 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
27 #include "openvswitch/list.h"
28 #include "ovs-thread.h"
29 #include "poll-loop.h"
31 COVERAGE_DEFINE(seq_change);
33 /* A sequence number object. */
35 uint64_t value OVS_GUARDED;
36 struct hmap waiters OVS_GUARDED; /* Contains 'struct seq_waiter's. */
39 /* A thread waiting on a particular seq. */
41 struct seq *seq OVS_GUARDED; /* Seq being waited for. */
42 struct hmap_node hmap_node OVS_GUARDED; /* In 'seq->waiters'. */
43 unsigned int ovsthread_id OVS_GUARDED; /* Key in 'waiters' hmap. */
45 struct seq_thread *thread OVS_GUARDED; /* Thread preparing to wait. */
46 struct ovs_list list_node OVS_GUARDED; /* In 'thread->waiters'. */
48 uint64_t value OVS_GUARDED; /* seq->value we're waiting to change. */
51 /* A thread that might be waiting on one or more seqs. */
53 struct ovs_list waiters OVS_GUARDED; /* Contains 'struct seq_waiter's. */
54 struct latch latch OVS_GUARDED; /* Wakeup latch for this thread. */
55 bool waiting OVS_GUARDED; /* True if latch_wait() already called. */
58 static struct ovs_mutex seq_mutex = OVS_MUTEX_INITIALIZER;
60 static uint64_t seq_next OVS_GUARDED_BY(seq_mutex) = 1;
62 static pthread_key_t seq_thread_key;
64 static void seq_init(void);
65 static struct seq_thread *seq_thread_get(void) OVS_REQUIRES(seq_mutex);
66 static void seq_thread_exit(void *thread_) OVS_EXCLUDED(seq_mutex);
67 static void seq_thread_woke(struct seq_thread *) OVS_REQUIRES(seq_mutex);
68 static void seq_waiter_destroy(struct seq_waiter *) OVS_REQUIRES(seq_mutex);
69 static void seq_wake_waiters(struct seq *) OVS_REQUIRES(seq_mutex);
71 /* Creates and returns a new 'seq' object. */
72 struct seq * OVS_EXCLUDED(seq_mutex)
79 seq = xmalloc(sizeof *seq);
81 COVERAGE_INC(seq_change);
83 ovs_mutex_lock(&seq_mutex);
84 seq->value = seq_next++;
85 hmap_init(&seq->waiters);
86 ovs_mutex_unlock(&seq_mutex);
91 /* Destroys 'seq', waking up threads that were waiting on it, if any. */
93 seq_destroy(struct seq *seq)
94 OVS_EXCLUDED(seq_mutex)
96 ovs_mutex_lock(&seq_mutex);
97 seq_wake_waiters(seq);
98 hmap_destroy(&seq->waiters);
100 ovs_mutex_unlock(&seq_mutex);
106 return ovs_mutex_trylock(&seq_mutex);
111 OVS_ACQUIRES(seq_mutex)
113 ovs_mutex_lock(&seq_mutex);
118 OVS_RELEASES(seq_mutex)
120 ovs_mutex_unlock(&seq_mutex);
123 /* Increments 'seq''s sequence number, waking up any threads that are waiting
126 seq_change_protected(struct seq *seq)
127 OVS_REQUIRES(seq_mutex)
129 COVERAGE_INC(seq_change);
131 seq->value = seq_next++;
132 seq_wake_waiters(seq);
135 /* Increments 'seq''s sequence number, waking up any threads that are waiting
138 seq_change(struct seq *seq)
139 OVS_EXCLUDED(seq_mutex)
141 ovs_mutex_lock(&seq_mutex);
142 seq_change_protected(seq);
143 ovs_mutex_unlock(&seq_mutex);
146 /* Returns 'seq''s current sequence number (which could change immediately).
148 * seq_read() and seq_wait() can be used together to yield a race-free wakeup
149 * when an object changes, even without an ability to lock the object. See
150 * Usage in seq.h for details. */
152 seq_read_protected(const struct seq *seq)
153 OVS_REQUIRES(seq_mutex)
158 /* Returns 'seq''s current sequence number (which could change immediately).
160 * seq_read() and seq_wait() can be used together to yield a race-free wakeup
161 * when an object changes, even without an ability to lock the object. See
162 * Usage in seq.h for details. */
164 seq_read(const struct seq *seq)
165 OVS_EXCLUDED(seq_mutex)
169 ovs_mutex_lock(&seq_mutex);
170 value = seq_read_protected(seq);
171 ovs_mutex_unlock(&seq_mutex);
177 seq_wait__(struct seq *seq, uint64_t value, const char *where)
178 OVS_REQUIRES(seq_mutex)
180 unsigned int id = ovsthread_id_self();
181 uint32_t hash = hash_int(id, 0);
182 struct seq_waiter *waiter;
184 HMAP_FOR_EACH_IN_BUCKET (waiter, hmap_node, hash, &seq->waiters) {
185 if (waiter->ovsthread_id == id) {
186 if (waiter->value != value) {
187 /* The current value is different from the value we've already
189 poll_immediate_wake_at(where);
191 /* Already waiting on 'value', nothing more to do. */
197 waiter = xmalloc(sizeof *waiter);
199 hmap_insert(&seq->waiters, &waiter->hmap_node, hash);
200 waiter->ovsthread_id = id;
201 waiter->value = value;
202 waiter->thread = seq_thread_get();
203 ovs_list_push_back(&waiter->thread->waiters, &waiter->list_node);
205 if (!waiter->thread->waiting) {
206 latch_wait_at(&waiter->thread->latch, where);
207 waiter->thread->waiting = true;
211 /* Causes the following poll_block() to wake up when 'seq''s sequence number
212 * changes from 'value'. (If 'seq''s sequence number isn't 'value', then
213 * poll_block() won't block at all.)
215 * seq_read() and seq_wait() can be used together to yield a race-free wakeup
216 * when an object changes, even without an ability to lock the object. See
217 * Usage in seq.h for details.
219 * ('where' is used in debug logging. Commonly one would use seq_wait() to
220 * automatically provide the caller's source file and line number for
223 seq_wait_at(const struct seq *seq_, uint64_t value, const char *where)
224 OVS_EXCLUDED(seq_mutex)
226 struct seq *seq = CONST_CAST(struct seq *, seq_);
228 ovs_mutex_lock(&seq_mutex);
229 if (value == seq->value) {
230 seq_wait__(seq, value, where);
232 poll_immediate_wake_at(where);
234 ovs_mutex_unlock(&seq_mutex);
237 /* Called by poll_block() just before it returns, this function destroys any
238 * seq_waiter objects associated with the current thread. */
241 OVS_EXCLUDED(seq_mutex)
243 struct seq_thread *thread;
247 thread = pthread_getspecific(seq_thread_key);
249 ovs_mutex_lock(&seq_mutex);
250 seq_thread_woke(thread);
251 thread->waiting = false;
252 ovs_mutex_unlock(&seq_mutex);
259 static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
261 if (ovsthread_once_start(&once)) {
262 xpthread_key_create(&seq_thread_key, seq_thread_exit);
263 ovsthread_once_done(&once);
267 static struct seq_thread *
269 OVS_REQUIRES(seq_mutex)
271 struct seq_thread *thread = pthread_getspecific(seq_thread_key);
273 thread = xmalloc(sizeof *thread);
274 ovs_list_init(&thread->waiters);
275 latch_init(&thread->latch);
276 thread->waiting = false;
278 xpthread_setspecific(seq_thread_key, thread);
284 seq_thread_exit(void *thread_)
285 OVS_EXCLUDED(seq_mutex)
287 struct seq_thread *thread = thread_;
289 ovs_mutex_lock(&seq_mutex);
290 seq_thread_woke(thread);
291 latch_destroy(&thread->latch);
293 ovs_mutex_unlock(&seq_mutex);
297 seq_thread_woke(struct seq_thread *thread)
298 OVS_REQUIRES(seq_mutex)
300 struct seq_waiter *waiter, *next_waiter;
302 LIST_FOR_EACH_SAFE (waiter, next_waiter, list_node, &thread->waiters) {
303 ovs_assert(waiter->thread == thread);
304 seq_waiter_destroy(waiter);
306 latch_poll(&thread->latch);
310 seq_waiter_destroy(struct seq_waiter *waiter)
311 OVS_REQUIRES(seq_mutex)
313 hmap_remove(&waiter->seq->waiters, &waiter->hmap_node);
314 ovs_list_remove(&waiter->list_node);
319 seq_wake_waiters(struct seq *seq)
320 OVS_REQUIRES(seq_mutex)
322 struct seq_waiter *waiter, *next_waiter;
324 HMAP_FOR_EACH_SAFE (waiter, next_waiter, hmap_node, &seq->waiters) {
325 latch_set(&waiter->thread->latch);
326 seq_waiter_destroy(waiter);