]>
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. | |
fe7cfa5c JR |
57 | */ |
58 | ||
59 | struct pvector_entry { | |
eb391b76 | 60 | int priority; |
fe7cfa5c JR |
61 | void *ptr; |
62 | }; | |
63 | ||
da9cfca6 | 64 | struct pvector_impl { |
fe7cfa5c JR |
65 | size_t size; /* Number of entries in the vector. */ |
66 | size_t allocated; /* Number of allocated entries. */ | |
67 | struct pvector_entry vector[]; | |
68 | }; | |
69 | ||
da9cfca6 JR |
70 | /* Concurrent priority vector. */ |
71 | struct pvector { | |
72 | OVSRCU_TYPE(struct pvector_impl *) impl; | |
73 | struct pvector_impl *temp; | |
74 | }; | |
75 | ||
76 | /* Initialization. */ | |
77 | void pvector_init(struct pvector *); | |
78 | void pvector_destroy(struct pvector *); | |
79 | ||
80 | /* Insertion and deletion. These work on 'temp'. */ | |
81 | void pvector_insert(struct pvector *, void *, int priority); | |
82 | void pvector_change_priority(struct pvector *, void *, int priority); | |
83 | void pvector_remove(struct pvector *, void *); | |
84 | ||
85 | /* Make the modified pvector available for iteration. */ | |
86 | static inline void pvector_publish(struct pvector *); | |
87 | ||
88 | /* Count. These operate on the published pvector. */ | |
89 | static inline size_t pvector_count(const struct pvector *); | |
90 | static inline bool pvector_is_empty(const struct pvector *); | |
802f84ff | 91 | |
fe7cfa5c JR |
92 | /* Iteration. |
93 | * | |
94 | * | |
95 | * Thread-safety | |
96 | * ============= | |
97 | * | |
da9cfca6 JR |
98 | * Iteration is safe even in a pvector that is changing concurrently. |
99 | * Multiple writers must exclude each other via e.g., a mutex. | |
fe7cfa5c JR |
100 | * |
101 | * Example | |
102 | * ======= | |
103 | * | |
104 | * struct my_node { | |
105 | * int data; | |
106 | * }; | |
107 | * | |
108 | * struct my_node elem1, elem2, *iter; | |
da9cfca6 | 109 | * struct pvector my_pvector; |
fe7cfa5c | 110 | * |
da9cfca6 | 111 | * pvector_init(&my_pvector); |
fe7cfa5c | 112 | * ...add data... |
da9cfca6 JR |
113 | * pvector_insert(&my_pvector, &elem1, 1); |
114 | * pvector_insert(&my_pvector, &elem2, 2); | |
fe7cfa5c | 115 | * ... |
da9cfca6 | 116 | * PVECTOR_FOR_EACH (iter, &my_pvector) { |
fe7cfa5c JR |
117 | * ...operate on '*iter'... |
118 | * ...elem2 to be seen before elem1... | |
119 | * } | |
120 | * ... | |
da9cfca6 | 121 | * pvector_destroy(&my_pvector); |
fe7cfa5c | 122 | * |
da9cfca6 JR |
123 | * There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU |
124 | * protected instance of the priority vector. Any concurrent modifications | |
125 | * that would be disruptive for readers (such as deletions), will be performed | |
126 | * on a new instance. To see any of the modifications, a new iteration loop | |
127 | * has to be started. | |
fe7cfa5c JR |
128 | * |
129 | * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher | |
93f25605 | 130 | * than or equal to the given priority and allows for object lookahead. |
da9cfca6 JR |
131 | * |
132 | * The iteration loop must be completed without entering the OVS RCU quiescent | |
133 | * period. That is, an old iteration loop must not be continued after any | |
134 | * blocking IO (VLOG is non-blocking, so that is OK). | |
fe7cfa5c JR |
135 | */ |
136 | struct pvector_cursor { | |
137 | size_t size; /* Number of entries in the vector. */ | |
138 | size_t entry_idx; /* Current index. */ | |
139 | const struct pvector_entry *vector; | |
140 | }; | |
141 | ||
142 | static inline struct pvector_cursor pvector_cursor_init(const struct pvector *, | |
143 | size_t n_ahead, | |
144 | size_t obj_size); | |
145 | static inline void *pvector_cursor_next(struct pvector_cursor *, | |
da9cfca6 | 146 | int lowest_priority, |
fe7cfa5c JR |
147 | size_t n_ahead, size_t obj_size); |
148 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *, | |
149 | int n, size_t size); | |
150 | ||
151 | #define PVECTOR_FOR_EACH(PTR, PVECTOR) \ | |
152 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \ | |
eb391b76 | 153 | ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; ) |
fe7cfa5c | 154 | |
93f25605 JR |
155 | /* Loop while priority is higher than or equal to 'PRIORITY' and prefetch |
156 | * objects of size 'SZ' 'N' objects ahead from the current object. */ | |
fe7cfa5c JR |
157 | #define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR) \ |
158 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \ | |
159 | ((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; ) | |
160 | ||
da9cfca6 JR |
161 | #define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR) \ |
162 | for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0); \ | |
de4ad4a2 JR |
163 | ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; ) |
164 | ||
165 | #define PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR) \ | |
166 | for (; ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; ) | |
167 | ||
fe7cfa5c JR |
168 | \f |
169 | /* Inline implementations. */ | |
170 | ||
171 | static inline struct pvector_cursor | |
da9cfca6 JR |
172 | pvector_cursor_init(const struct pvector *pvec, |
173 | size_t n_ahead, size_t obj_size) | |
fe7cfa5c | 174 | { |
da9cfca6 | 175 | const struct pvector_impl *impl; |
fe7cfa5c JR |
176 | struct pvector_cursor cursor; |
177 | ||
da9cfca6 | 178 | impl = ovsrcu_get(struct pvector_impl *, &pvec->impl); |
fe7cfa5c | 179 | |
da9cfca6 JR |
180 | ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]); |
181 | ||
182 | cursor.size = impl->size; | |
183 | cursor.vector = impl->vector; | |
fe7cfa5c JR |
184 | cursor.entry_idx = -1; |
185 | ||
186 | for (size_t i = 0; i < n_ahead; i++) { | |
187 | /* Prefetch the first objects. */ | |
188 | pvector_cursor_lookahead(&cursor, i, obj_size); | |
189 | } | |
190 | return cursor; | |
191 | } | |
192 | ||
193 | static inline void *pvector_cursor_next(struct pvector_cursor *cursor, | |
93f25605 | 194 | int lowest_priority, |
fe7cfa5c JR |
195 | size_t n_ahead, size_t obj_size) |
196 | { | |
197 | if (++cursor->entry_idx < cursor->size && | |
93f25605 | 198 | cursor->vector[cursor->entry_idx].priority >= lowest_priority) { |
fe7cfa5c JR |
199 | if (n_ahead) { |
200 | pvector_cursor_lookahead(cursor, n_ahead, obj_size); | |
201 | } | |
202 | return cursor->vector[cursor->entry_idx].ptr; | |
203 | } | |
204 | return NULL; | |
205 | } | |
206 | ||
207 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor, | |
208 | int n, size_t size) | |
209 | { | |
210 | if (cursor->entry_idx + n < cursor->size) { | |
211 | ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size); | |
212 | } | |
213 | } | |
214 | ||
da9cfca6 | 215 | static inline size_t pvector_count(const struct pvector *pvec) |
fe7cfa5c | 216 | { |
da9cfca6 | 217 | return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size; |
fe7cfa5c JR |
218 | } |
219 | ||
da9cfca6 | 220 | static inline bool pvector_is_empty(const struct pvector *pvec) |
fe7cfa5c | 221 | { |
da9cfca6 | 222 | return pvector_count(pvec) == 0; |
fe7cfa5c JR |
223 | } |
224 | ||
da9cfca6 | 225 | void pvector_publish__(struct pvector *); |
802f84ff | 226 | |
da9cfca6 JR |
227 | /* Make the modified pvector available for iteration. */ |
228 | static inline void pvector_publish(struct pvector *pvec) | |
802f84ff | 229 | { |
da9cfca6 JR |
230 | if (pvec->temp) { |
231 | pvector_publish__(pvec); | |
802f84ff JR |
232 | } |
233 | } | |
234 | ||
fe7cfa5c | 235 | #endif /* pvector.h */ |