]>
Commit | Line | Data |
---|---|---|
fe7cfa5c | 1 | /* |
3d0dc308 | 2 | * Copyright (c) 2014, 2016 Nicira, Inc. |
fe7cfa5c JR |
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 PVECTOR_H | |
18 | #define PVECTOR_H 1 | |
19 | ||
20 | #include <stdbool.h> | |
21 | #include <stdint.h> | |
802f84ff | 22 | #include <stdlib.h> |
fe7cfa5c JR |
23 | #include "ovs-rcu.h" |
24 | #include "util.h" | |
25 | ||
26 | /* Concurrent Priority Vector | |
27 | * ========================== | |
28 | * | |
ede44667 BP |
29 | * Concurrent priority vector holds non-NULL pointers to objects in a |
30 | * nondecreasing priority order and allows readers to traverse the vector | |
31 | * without being concerned about writers modifying the vector as they are | |
32 | * traversing it. | |
33 | * | |
34 | * Multiple elements of a given priority are allowed. | |
fe7cfa5c JR |
35 | * |
36 | * The priority order is maintained as a linear vector of elements to allow | |
37 | * for efficient memory prefetching. | |
38 | * | |
39 | * Concurrency is implemented with OVS RCU so that the readers can assume | |
40 | * that once they have taken a pointer to the vector with | |
41 | * pvector_cursor_init(), the 'size' member will not decrease, so that | |
42 | * they can safely read 'size' entries from 'vector', and find that each | |
43 | * entry has a valid, non-NULL 'ptr', and the vector is in order from highest | |
44 | * to lowest 'priority'. The 'priority' values can change any time, but only | |
45 | * so that the order of the entries does not change, so readers can use | |
46 | * 'priority' values read at any time after acquisition of the vector pointer. | |
47 | * | |
48 | * Writers can concurrently add entries to the end of the vector, incrementing | |
49 | * 'size', or update the 'priority' value of an entry, but only if that does | |
50 | * not change the ordering of the entries. Writers will never change the 'ptr' | |
51 | * values, or decrement the 'size' on a copy that readers have access to. | |
eb391b76 | 52 | * |
802f84ff | 53 | * Most modifications are internally staged at the 'temp' vector, from which |
da9cfca6 | 54 | * they can be published at 'impl' by calling pvector_publish(). This saves |
802f84ff JR |
55 | * unnecessary memory allocations when many changes are done back-to-back. |
56 | * 'temp' may contain NULL pointers and it may be in unsorted order. It is | |
57 | * sorted before it is published at 'impl', which also removes the NULLs from | |
58 | * the published vector. | |
ead94250 IM |
59 | * |
60 | * Since the vector is RCU protected, the entry destruction after removal must | |
61 | * be RCU postponed. Also, if it happens before changes published with | |
62 | * pvector_publish(), destruction must be double postponed, i.e., the second | |
63 | * ovsrcu_postpone() call to destruct the entry should be called from the first | |
64 | * RCU callback. This is required because readers could still obtain the | |
65 | * unmodified vector until updated version is published. | |
fe7cfa5c JR |
66 | */ |
67 | ||
68 | struct pvector_entry { | |
eb391b76 | 69 | int priority; |
fe7cfa5c JR |
70 | void *ptr; |
71 | }; | |
72 | ||
da9cfca6 | 73 | struct pvector_impl { |
4e1ce6f6 YW |
74 | atomic_size_t size; /* Number of entries in the vector. */ |
75 | size_t allocated; /* Number of allocated entries. */ | |
fe7cfa5c JR |
76 | struct pvector_entry vector[]; |
77 | }; | |
78 | ||
da9cfca6 JR |
79 | /* Concurrent priority vector. */ |
80 | struct pvector { | |
81 | OVSRCU_TYPE(struct pvector_impl *) impl; | |
82 | struct pvector_impl *temp; | |
83 | }; | |
84 | ||
85 | /* Initialization. */ | |
86 | void pvector_init(struct pvector *); | |
87 | void pvector_destroy(struct pvector *); | |
88 | ||
89 | /* Insertion and deletion. These work on 'temp'. */ | |
90 | void pvector_insert(struct pvector *, void *, int priority); | |
91 | void pvector_change_priority(struct pvector *, void *, int priority); | |
92 | void pvector_remove(struct pvector *, void *); | |
93 | ||
94 | /* Make the modified pvector available for iteration. */ | |
95 | static inline void pvector_publish(struct pvector *); | |
96 | ||
97 | /* Count. These operate on the published pvector. */ | |
98 | static inline size_t pvector_count(const struct pvector *); | |
99 | static inline bool pvector_is_empty(const struct pvector *); | |
802f84ff | 100 | |
fe7cfa5c JR |
101 | /* Iteration. |
102 | * | |
103 | * | |
104 | * Thread-safety | |
105 | * ============= | |
106 | * | |
da9cfca6 JR |
107 | * Iteration is safe even in a pvector that is changing concurrently. |
108 | * Multiple writers must exclude each other via e.g., a mutex. | |
fe7cfa5c JR |
109 | * |
110 | * Example | |
111 | * ======= | |
112 | * | |
113 | * struct my_node { | |
114 | * int data; | |
115 | * }; | |
116 | * | |
117 | * struct my_node elem1, elem2, *iter; | |
da9cfca6 | 118 | * struct pvector my_pvector; |
fe7cfa5c | 119 | * |
da9cfca6 | 120 | * pvector_init(&my_pvector); |
fe7cfa5c | 121 | * ...add data... |
da9cfca6 JR |
122 | * pvector_insert(&my_pvector, &elem1, 1); |
123 | * pvector_insert(&my_pvector, &elem2, 2); | |
fe7cfa5c | 124 | * ... |
da9cfca6 | 125 | * PVECTOR_FOR_EACH (iter, &my_pvector) { |
fe7cfa5c JR |
126 | * ...operate on '*iter'... |
127 | * ...elem2 to be seen before elem1... | |
128 | * } | |
129 | * ... | |
da9cfca6 | 130 | * pvector_destroy(&my_pvector); |
fe7cfa5c | 131 | * |
da9cfca6 JR |
132 | * There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU |
133 | * protected instance of the priority vector. Any concurrent modifications | |
134 | * that would be disruptive for readers (such as deletions), will be performed | |
135 | * on a new instance. To see any of the modifications, a new iteration loop | |
136 | * has to be started. | |
fe7cfa5c JR |
137 | * |
138 | * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher | |
93f25605 | 139 | * than or equal to the given priority and allows for object lookahead. |
da9cfca6 JR |
140 | * |
141 | * The iteration loop must be completed without entering the OVS RCU quiescent | |
142 | * period. That is, an old iteration loop must not be continued after any | |
143 | * blocking IO (VLOG is non-blocking, so that is OK). | |
fe7cfa5c JR |
144 | */ |
145 | struct pvector_cursor { | |
146 | size_t size; /* Number of entries in the vector. */ | |
147 | size_t entry_idx; /* Current index. */ | |
148 | const struct pvector_entry *vector; | |
149 | }; | |
150 | ||
151 | static inline struct pvector_cursor pvector_cursor_init(const struct pvector *, | |
152 | size_t n_ahead, | |
153 | size_t obj_size); | |
154 | static inline void *pvector_cursor_next(struct pvector_cursor *, | |
da9cfca6 | 155 | int lowest_priority, |
fe7cfa5c JR |
156 | size_t n_ahead, size_t obj_size); |
157 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *, | |
158 | int n, size_t size); | |
159 | ||
160 | #define PVECTOR_FOR_EACH(PTR, PVECTOR) \ | |
161 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \ | |
eb391b76 | 162 | ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; ) |
fe7cfa5c | 163 | |
93f25605 JR |
164 | /* Loop while priority is higher than or equal to 'PRIORITY' and prefetch |
165 | * objects of size 'SZ' 'N' objects ahead from the current object. */ | |
fe7cfa5c JR |
166 | #define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR) \ |
167 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \ | |
168 | ((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; ) | |
169 | ||
da9cfca6 JR |
170 | #define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR) \ |
171 | for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0); \ | |
de4ad4a2 JR |
172 | ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; ) |
173 | ||
174 | #define PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR) \ | |
175 | for (; ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; ) | |
176 | ||
fe7cfa5c JR |
177 | \f |
178 | /* Inline implementations. */ | |
179 | ||
180 | static inline struct pvector_cursor | |
da9cfca6 JR |
181 | pvector_cursor_init(const struct pvector *pvec, |
182 | size_t n_ahead, size_t obj_size) | |
fe7cfa5c | 183 | { |
da9cfca6 | 184 | const struct pvector_impl *impl; |
fe7cfa5c | 185 | struct pvector_cursor cursor; |
4e1ce6f6 | 186 | size_t size; |
fe7cfa5c | 187 | |
da9cfca6 | 188 | impl = ovsrcu_get(struct pvector_impl *, &pvec->impl); |
fe7cfa5c | 189 | |
4e1ce6f6 YW |
190 | /* Use memory_order_acquire to ensure entry access can not be |
191 | * reordered to happen before size read. */ | |
192 | atomic_read_explicit(&CONST_CAST(struct pvector_impl *, impl)->size, | |
193 | &size, memory_order_acquire); | |
194 | ovs_prefetch_range(impl->vector, size * sizeof impl->vector[0]); | |
da9cfca6 | 195 | |
4e1ce6f6 | 196 | cursor.size = size; |
da9cfca6 | 197 | cursor.vector = impl->vector; |
fe7cfa5c JR |
198 | cursor.entry_idx = -1; |
199 | ||
200 | for (size_t i = 0; i < n_ahead; i++) { | |
201 | /* Prefetch the first objects. */ | |
202 | pvector_cursor_lookahead(&cursor, i, obj_size); | |
203 | } | |
204 | return cursor; | |
205 | } | |
206 | ||
207 | static inline void *pvector_cursor_next(struct pvector_cursor *cursor, | |
93f25605 | 208 | int lowest_priority, |
fe7cfa5c JR |
209 | size_t n_ahead, size_t obj_size) |
210 | { | |
211 | if (++cursor->entry_idx < cursor->size && | |
93f25605 | 212 | cursor->vector[cursor->entry_idx].priority >= lowest_priority) { |
fe7cfa5c JR |
213 | if (n_ahead) { |
214 | pvector_cursor_lookahead(cursor, n_ahead, obj_size); | |
215 | } | |
216 | return cursor->vector[cursor->entry_idx].ptr; | |
217 | } | |
218 | return NULL; | |
219 | } | |
220 | ||
221 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor, | |
222 | int n, size_t size) | |
223 | { | |
224 | if (cursor->entry_idx + n < cursor->size) { | |
225 | ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size); | |
226 | } | |
227 | } | |
228 | ||
da9cfca6 | 229 | static inline size_t pvector_count(const struct pvector *pvec) |
fe7cfa5c | 230 | { |
da9cfca6 | 231 | return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size; |
fe7cfa5c JR |
232 | } |
233 | ||
da9cfca6 | 234 | static inline bool pvector_is_empty(const struct pvector *pvec) |
fe7cfa5c | 235 | { |
da9cfca6 | 236 | return pvector_count(pvec) == 0; |
fe7cfa5c JR |
237 | } |
238 | ||
da9cfca6 | 239 | void pvector_publish__(struct pvector *); |
802f84ff | 240 | |
da9cfca6 JR |
241 | /* Make the modified pvector available for iteration. */ |
242 | static inline void pvector_publish(struct pvector *pvec) | |
802f84ff | 243 | { |
da9cfca6 JR |
244 | if (pvec->temp) { |
245 | pvector_publish__(pvec); | |
802f84ff JR |
246 | } |
247 | } | |
248 | ||
fe7cfa5c | 249 | #endif /* pvector.h */ |