]>
Commit | Line | Data |
---|---|---|
55b40355 | 1 | /* |
21138472 | 2 | * Copyright (c) 2013, 2014 Nicira, Inc. |
55b40355 BP |
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 | #ifndef SEQ_H | |
18 | #define SEQ_H 1 | |
19 | ||
20 | /* Thread-safe, pollable sequence number. | |
21 | * | |
22 | * | |
5d389d55 | 23 | * Motivation |
55b40355 BP |
24 | * ========== |
25 | * | |
26 | * It is sometimes desirable to take an action whenever an object changes. | |
27 | * Suppose we associate a sequence number with an object and increment the | |
28 | * sequence number whenver we change the object. An observer can then record | |
29 | * the sequence number it sees. Later on, if the current sequence number | |
30 | * differs from the one it saw last, then the observer knows to examine the | |
31 | * object for changes. | |
32 | * | |
33 | * Code that wants to run when a sequence number changes is challenging to | |
34 | * implement in a multithreaded environment. A naive implementation, that | |
35 | * simply checks whether the sequence number changed and, if so, calls | |
36 | * poll_immediate_wake(), will fail when another thread increments the sequence | |
37 | * number after the check (including during poll_block()). | |
38 | * | |
39 | * struct seq is a solution. It implements a sequence number along with enough | |
40 | * internal infrastructure so that a thread waiting on a particular value will | |
41 | * wake up if the sequence number changes, or even if the "struct seq" is | |
42 | * destroyed. | |
43 | * | |
44 | * | |
45 | * Usage | |
46 | * ===== | |
47 | * | |
48 | * The object that includes a sequence number should use seq_create() and | |
49 | * seq_destroy() at creation and destruction, and seq_change() whenever the | |
50 | * object's observable state changes. | |
51 | * | |
52 | * An observer may seq_read() to read the current sequence number and | |
53 | * seq_wait() to cause poll_block() to wake up when the sequence number changes | |
54 | * from a specified value. | |
55 | * | |
56 | * To avoid races, observers should use seq_read() to check for changes, | |
57 | * process any changes, and then use seq_wait() to wait for a change from the | |
58 | * previously read value. That is, a correct usage looks something like this: | |
59 | * | |
60 | * new_seq = seq_read(seq); | |
61 | * if (new_seq != last_seq) { | |
62 | * ...process changes... | |
63 | * last_seq = new_seq; | |
64 | * } | |
65 | * seq_wait(seq, new_seq); | |
66 | * poll_block(); | |
67 | * | |
68 | * | |
5d389d55 BP |
69 | * Alternate Usage |
70 | * =============== | |
71 | * | |
72 | * struct seq can also be used as a sort of pollable condition variable. | |
73 | * Suppose that we want a thread to process items in a queue, and thus to be | |
74 | * able to wake up whenever the queue is nonempty. This requires a lock to | |
75 | * protect the queue and a seq to signal that the queue has become nonempty, | |
76 | * e.g.: | |
77 | * | |
78 | * struct ovs_mutex mutex; | |
79 | * struct list queue OVS_GUARDED_BY(mutex); | |
80 | * struct seq nonempty_seq; | |
81 | * | |
82 | * To add an element to the queue: | |
83 | * | |
84 | * ovs_mutex_lock(&mutex); | |
85 | * list_push_back(&queue, ...element...); | |
86 | * if (list_is_singleton(&queue)) { // The 'if' test here is optional. | |
87 | * seq_change(&nonempty_seq); | |
88 | * } | |
89 | * ovs_mutex_unlock(&mutex); | |
90 | * | |
91 | * To wait for the queue to become nonempty: | |
92 | * | |
93 | * ovs_mutex_lock(&mutex); | |
94 | * if (list_is_empty(&queue)) { | |
95 | * seq_wait(&nonempty_seq, seq_read(&nonempty_seq)); | |
96 | * } else { | |
97 | * poll_immediate_wake(); | |
98 | * } | |
99 | * ovs_mutex_unlock(&mutex); | |
100 | * | |
101 | * (In the above code 'mutex' prevents the queue from changing between | |
102 | * seq_read() and seq_wait(). Otherwise, it would be necessary to seq_read(), | |
103 | * check for a nonempty queue, and then seq_wait() on the previously read | |
104 | * sequence number, as under Usage above.) | |
105 | * | |
106 | * | |
55b40355 BP |
107 | * Thread-safety |
108 | * ============= | |
109 | * | |
ab355e67 JR |
110 | * Fully thread safe. seq_change() synchronizes with seq_read() and |
111 | * seq_wait() on the same variable in release-acquire fashion. That | |
112 | * is, all effects of the memory accesses performed by a thread prior | |
113 | * to seq_change() are visible to the threads returning from | |
114 | * seq_read() or seq_wait() observing that change. | |
55b40355 BP |
115 | */ |
116 | ||
117 | #include <stdint.h> | |
21138472 | 118 | #include "util.h" |
55b40355 BP |
119 | |
120 | /* For implementation of an object with a sequence number attached. */ | |
121 | struct seq *seq_create(void); | |
122 | void seq_destroy(struct seq *); | |
123 | void seq_change(struct seq *); | |
124 | ||
125 | /* For observers. */ | |
126 | uint64_t seq_read(const struct seq *); | |
21138472 BP |
127 | |
128 | void seq_wait_at(const struct seq *, uint64_t value, const char *where); | |
8f3676cf | 129 | #define seq_wait(seq, value) seq_wait_at(seq, value, OVS_SOURCE_LOCATOR) |
55b40355 BP |
130 | |
131 | /* For poll_block() internal use. */ | |
132 | void seq_woke(void); | |
133 | ||
134 | #endif /* seq.h */ |