datapath: handle recirculation loop detection
[sliver-openvswitch.git] / lib / seq.c
1 /*
2  * Copyright (c) 2013 Nicira, Inc.
3  *
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:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <config.h>
18
19 #include "seq.h"
20
21 #include <stdbool.h>
22
23 #include "hash.h"
24 #include "hmap.h"
25 #include "latch.h"
26 #include "list.h"
27 #include "ovs-thread.h"
28 #include "poll-loop.h"
29
30 /* A sequence number object. */
31 struct seq {
32     uint64_t value OVS_GUARDED;
33     struct hmap waiters OVS_GUARDED; /* Contains 'struct seq_waiter's. */
34 };
35
36 /* A thread waiting on a particular seq. */
37 struct seq_waiter {
38     struct seq *seq OVS_GUARDED;            /* Seq being waited for. */
39     struct hmap_node hmap_node OVS_GUARDED; /* In 'seq->waiters'. */
40     unsigned int ovsthread_id OVS_GUARDED;  /* Key in 'waiters' hmap. */
41
42     struct seq_thread *thread OVS_GUARDED; /* Thread preparing to wait. */
43     struct list list_node OVS_GUARDED;     /* In 'thread->waiters'. */
44
45     uint64_t value OVS_GUARDED; /* seq->value we're waiting to change. */
46 };
47
48 /* A thread that might be waiting on one or more seqs. */
49 struct seq_thread {
50     struct list waiters OVS_GUARDED; /* Contains 'struct seq_waiter's. */
51     struct latch latch OVS_GUARDED;  /* Wakeup latch for this thread. */
52     bool waiting OVS_GUARDED;        /* True if latch_wait() already called. */
53 };
54
55 static struct ovs_mutex seq_mutex = OVS_MUTEX_INITIALIZER;
56
57 static uint64_t seq_next OVS_GUARDED_BY(seq_mutex) = 1;
58
59 static pthread_key_t seq_thread_key;
60
61 static void seq_init(void);
62 static struct seq_thread *seq_thread_get(void) OVS_REQUIRES(seq_mutex);
63 static void seq_thread_exit(void *thread_) OVS_EXCLUDED(seq_mutex);
64 static void seq_thread_woke(struct seq_thread *) OVS_REQUIRES(seq_mutex);
65 static void seq_waiter_destroy(struct seq_waiter *) OVS_REQUIRES(seq_mutex);
66 static void seq_wake_waiters(struct seq *) OVS_REQUIRES(seq_mutex);
67
68 /* Creates and returns a new 'seq' object. */
69 struct seq * OVS_EXCLUDED(seq_mutex)
70 seq_create(void)
71 {
72     struct seq *seq;
73
74     seq_init();
75
76     seq = xmalloc(sizeof *seq);
77     ovs_mutex_lock(&seq_mutex);
78     seq->value = seq_next++;
79     hmap_init(&seq->waiters);
80     ovs_mutex_unlock(&seq_mutex);
81
82     return seq;
83 }
84
85 /* Destroys 'seq', waking up threads that were waiting on it, if any. */
86 void
87 seq_destroy(struct seq *seq)
88      OVS_EXCLUDED(seq_mutex)
89 {
90     ovs_mutex_lock(&seq_mutex);
91     seq_wake_waiters(seq);
92     hmap_destroy(&seq->waiters);
93     free(seq);
94     ovs_mutex_unlock(&seq_mutex);
95 }
96
97 /* Increments 'seq''s sequence number, waking up any threads that are waiting
98  * on 'seq'. */
99 void
100 seq_change(struct seq *seq)
101     OVS_EXCLUDED(seq_mutex)
102 {
103     ovs_mutex_lock(&seq_mutex);
104     seq->value = seq_next++;
105     seq_wake_waiters(seq);
106     ovs_mutex_unlock(&seq_mutex);
107 }
108
109 /* Returns 'seq''s current sequence number (which could change immediately).
110  *
111  * seq_read() and seq_wait() can be used together to yield a race-free wakeup
112  * when an object changes, even without an ability to lock the object.  See
113  * Usage in seq.h for details. */
114 uint64_t
115 seq_read(const struct seq *seq)
116     OVS_EXCLUDED(seq_mutex)
117 {
118     uint64_t value;
119
120     ovs_mutex_lock(&seq_mutex);
121     value = seq->value;
122     ovs_mutex_unlock(&seq_mutex);
123
124     return value;
125 }
126
127 static void
128 seq_wait__(struct seq *seq, uint64_t value)
129     OVS_REQUIRES(seq_mutex)
130 {
131     unsigned int id = ovsthread_id_self();
132     uint32_t hash = hash_int(id, 0);
133     struct seq_waiter *waiter;
134
135     HMAP_FOR_EACH_IN_BUCKET (waiter, hmap_node, hash, &seq->waiters) {
136         if (waiter->ovsthread_id == id) {
137             if (waiter->value != value) {
138                 /* The current value is different from the value we've already
139                  * waited for, */
140                 poll_immediate_wake();
141             } else {
142                 /* Already waiting on 'value', nothing more to do. */
143             }
144             return;
145         }
146     }
147
148     waiter = xmalloc(sizeof *waiter);
149     waiter->seq = seq;
150     hmap_insert(&seq->waiters, &waiter->hmap_node, hash);
151     waiter->ovsthread_id = id;
152     waiter->value = value;
153     waiter->thread = seq_thread_get();
154     list_push_back(&waiter->thread->waiters, &waiter->list_node);
155
156     if (!waiter->thread->waiting) {
157         latch_wait(&waiter->thread->latch);
158         waiter->thread->waiting = true;
159     }
160 }
161
162 /* Causes the following poll_block() to wake up when 'seq''s sequence number
163  * changes from 'value'.  (If 'seq''s sequence number isn't 'value', then
164  * poll_block() won't block at all.)
165  *
166  * seq_read() and seq_wait() can be used together to yield a race-free wakeup
167  * when an object changes, even without an ability to lock the object.  See
168  * Usage in seq.h for details. */
169 void
170 seq_wait(const struct seq *seq_, uint64_t value)
171     OVS_EXCLUDED(seq_mutex)
172 {
173     struct seq *seq = CONST_CAST(struct seq *, seq_);
174
175     ovs_mutex_lock(&seq_mutex);
176     if (value == seq->value) {
177         seq_wait__(seq, value);
178     } else {
179         poll_immediate_wake();
180     }
181     ovs_mutex_unlock(&seq_mutex);
182 }
183
184 /* Called by poll_block() just before it returns, this function destroys any
185  * seq_waiter objects associated with the current thread. */
186 void
187 seq_woke(void)
188     OVS_EXCLUDED(seq_mutex)
189 {
190     struct seq_thread *thread;
191
192     seq_init();
193
194     thread = pthread_getspecific(seq_thread_key);
195     if (thread) {
196         ovs_mutex_lock(&seq_mutex);
197         seq_thread_woke(thread);
198         thread->waiting = false;
199         ovs_mutex_unlock(&seq_mutex);
200     }
201 }
202 \f
203 static void
204 seq_init(void)
205 {
206     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
207
208     if (ovsthread_once_start(&once)) {
209         xpthread_key_create(&seq_thread_key, seq_thread_exit);
210         ovsthread_once_done(&once);
211     }
212 }
213
214 static struct seq_thread *
215 seq_thread_get(void)
216     OVS_REQUIRES(seq_mutex)
217 {
218     struct seq_thread *thread = pthread_getspecific(seq_thread_key);
219     if (!thread) {
220         thread = xmalloc(sizeof *thread);
221         list_init(&thread->waiters);
222         latch_init(&thread->latch);
223         thread->waiting = false;
224
225         xpthread_setspecific(seq_thread_key, thread);
226     }
227     return thread;
228 }
229
230 static void
231 seq_thread_exit(void *thread_)
232     OVS_EXCLUDED(seq_mutex)
233 {
234     struct seq_thread *thread = thread_;
235
236     ovs_mutex_lock(&seq_mutex);
237     seq_thread_woke(thread);
238     latch_destroy(&thread->latch);
239     free(thread);
240     ovs_mutex_unlock(&seq_mutex);
241 }
242
243 static void
244 seq_thread_woke(struct seq_thread *thread)
245     OVS_REQUIRES(seq_mutex)
246 {
247     struct seq_waiter *waiter, *next_waiter;
248
249     LIST_FOR_EACH_SAFE (waiter, next_waiter, list_node, &thread->waiters) {
250         ovs_assert(waiter->thread == thread);
251         seq_waiter_destroy(waiter);
252     }
253     latch_poll(&thread->latch);
254 }
255
256 static void
257 seq_waiter_destroy(struct seq_waiter *waiter)
258     OVS_REQUIRES(seq_mutex)
259 {
260     hmap_remove(&waiter->seq->waiters, &waiter->hmap_node);
261     list_remove(&waiter->list_node);
262     free(waiter);
263 }
264
265 static void
266 seq_wake_waiters(struct seq *seq)
267     OVS_REQUIRES(seq_mutex)
268 {
269     struct seq_waiter *waiter, *next_waiter;
270
271     HMAP_FOR_EACH_SAFE (waiter, next_waiter, hmap_node, &seq->waiters) {
272         latch_set(&waiter->thread->latch);
273         seq_waiter_destroy(waiter);
274     }
275 }