ovs-thread: Use fair (but nonrecursive) rwlocks on glibc.
[sliver-openvswitch.git] / lib / seq.h
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 #ifndef SEQ_H
18 #define SEQ_H 1
19
20 /* Thread-safe, pollable sequence number.
21  *
22  *
23  * Motivation
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  *
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  *
107  * Thread-safety
108  * =============
109  *
110  * Fully thread safe.
111  */
112
113 #include <stdint.h>
114
115 /* For implementation of an object with a sequence number attached. */
116 struct seq *seq_create(void);
117 void seq_destroy(struct seq *);
118 void seq_change(struct seq *);
119
120 /* For observers. */
121 uint64_t seq_read(const struct seq *);
122 void seq_wait(const struct seq *, uint64_t value);
123
124 /* For poll_block() internal use. */
125 void seq_woke(void);
126
127 #endif /* seq.h */