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