]>
Commit | Line | Data |
---|---|---|
fe7cfa5c JR |
1 | /* |
2 | * Copyright (c) 2014 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 PVECTOR_H | |
18 | #define PVECTOR_H 1 | |
19 | ||
20 | #include <stdbool.h> | |
21 | #include <stdint.h> | |
22 | #include "ovs-rcu.h" | |
23 | #include "util.h" | |
24 | ||
25 | /* Concurrent Priority Vector | |
26 | * ========================== | |
27 | * | |
28 | * Concurrent priority vector holds non-NULL pointers to objects in an | |
29 | * increasing priority order and allows readers to traverse the vector without | |
30 | * being concerned about writers modifying the vector as they are traversing | |
31 | * it. | |
32 | * | |
33 | * The priority order is maintained as a linear vector of elements to allow | |
34 | * for efficient memory prefetching. | |
35 | * | |
36 | * Concurrency is implemented with OVS RCU so that the readers can assume | |
37 | * that once they have taken a pointer to the vector with | |
38 | * pvector_cursor_init(), the 'size' member will not decrease, so that | |
39 | * they can safely read 'size' entries from 'vector', and find that each | |
40 | * entry has a valid, non-NULL 'ptr', and the vector is in order from highest | |
41 | * to lowest 'priority'. The 'priority' values can change any time, but only | |
42 | * so that the order of the entries does not change, so readers can use | |
43 | * 'priority' values read at any time after acquisition of the vector pointer. | |
44 | * | |
45 | * Writers can concurrently add entries to the end of the vector, incrementing | |
46 | * 'size', or update the 'priority' value of an entry, but only if that does | |
47 | * not change the ordering of the entries. Writers will never change the 'ptr' | |
48 | * values, or decrement the 'size' on a copy that readers have access to. | |
eb391b76 BP |
49 | * |
50 | * Clients should not use priority INT_MIN. | |
fe7cfa5c JR |
51 | */ |
52 | ||
53 | struct pvector_entry { | |
eb391b76 | 54 | int priority; |
fe7cfa5c JR |
55 | void *ptr; |
56 | }; | |
57 | ||
58 | /* Writers will preallocate space for some entries at the end to avoid future | |
59 | * reallocations. */ | |
60 | enum { PVECTOR_EXTRA_ALLOC = 4 }; | |
61 | ||
62 | struct pvector_impl { | |
63 | size_t size; /* Number of entries in the vector. */ | |
64 | size_t allocated; /* Number of allocated entries. */ | |
65 | struct pvector_entry vector[]; | |
66 | }; | |
67 | ||
68 | /* Concurrent priority vector. */ | |
69 | struct pvector { | |
70 | OVSRCU_TYPE(struct pvector_impl *) impl; | |
71 | }; | |
72 | ||
73 | /* Initialization. */ | |
74 | void pvector_init(struct pvector *); | |
75 | void pvector_destroy(struct pvector *); | |
76 | ||
77 | /* Count. */ | |
78 | static inline size_t pvector_count(const struct pvector *); | |
79 | static inline bool pvector_is_empty(const struct pvector *); | |
80 | ||
81 | /* Insertion and deletion. */ | |
eb391b76 BP |
82 | void pvector_insert(struct pvector *, void *, int priority); |
83 | void pvector_change_priority(struct pvector *, void *, int priority); | |
fe7cfa5c JR |
84 | void pvector_remove(struct pvector *, void *); |
85 | ||
86 | /* Iteration. | |
87 | * | |
88 | * | |
89 | * Thread-safety | |
90 | * ============= | |
91 | * | |
92 | * Iteration is safe even in a pvector that is changing concurrently. | |
93 | * Multiple writers must exclude each other via e.g., a mutex. | |
94 | * | |
95 | * Example | |
96 | * ======= | |
97 | * | |
98 | * struct my_node { | |
99 | * int data; | |
100 | * }; | |
101 | * | |
102 | * struct my_node elem1, elem2, *iter; | |
103 | * struct pvector my_pvector; | |
104 | * | |
105 | * pvector_init(&my_pvector); | |
106 | * ...add data... | |
107 | * pvector_insert(&my_pvector, &elem1, 1); | |
108 | * pvector_insert(&my_pvector, &elem2, 2); | |
109 | * ... | |
110 | * PVECTOR_FOR_EACH (iter, &my_pvector) { | |
111 | * ...operate on '*iter'... | |
112 | * ...elem2 to be seen before elem1... | |
113 | * } | |
114 | * ... | |
115 | * pvector_destroy(&my_pvector); | |
116 | * | |
117 | * There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU | |
118 | * protected instance of the priority vector. Any concurrent modifications | |
119 | * that would be disruptive for readers (such as deletions), will be performed | |
120 | * on a new instance. To see any of the modifications, a new iteration loop | |
121 | * has to be started. | |
122 | * | |
123 | * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher | |
124 | * than given priority and allows for object lookahead. | |
125 | * | |
126 | * The iteration loop must be completed without entering the OVS RCU quiescent | |
127 | * period. That is, an old iteration loop must not be continued after any | |
128 | * blocking IO (VLOG is non-blocking, so that is OK). | |
129 | */ | |
130 | struct pvector_cursor { | |
131 | size_t size; /* Number of entries in the vector. */ | |
132 | size_t entry_idx; /* Current index. */ | |
133 | const struct pvector_entry *vector; | |
134 | }; | |
135 | ||
136 | static inline struct pvector_cursor pvector_cursor_init(const struct pvector *, | |
137 | size_t n_ahead, | |
138 | size_t obj_size); | |
139 | static inline void *pvector_cursor_next(struct pvector_cursor *, | |
eb391b76 | 140 | int stop_at_priority, |
fe7cfa5c JR |
141 | size_t n_ahead, size_t obj_size); |
142 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *, | |
143 | int n, size_t size); | |
144 | ||
145 | #define PVECTOR_FOR_EACH(PTR, PVECTOR) \ | |
146 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \ | |
eb391b76 | 147 | ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; ) |
fe7cfa5c JR |
148 | |
149 | /* Loop while priority is higher than 'PRIORITY' and prefetch objects | |
150 | * of size 'SZ' 'N' objects ahead from the current object. */ | |
151 | #define PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, PVECTOR) \ | |
152 | for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \ | |
153 | ((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; ) | |
154 | ||
155 | \f | |
156 | /* Inline implementations. */ | |
157 | ||
158 | static inline struct pvector_cursor | |
159 | pvector_cursor_init(const struct pvector *pvec, | |
160 | size_t n_ahead, size_t obj_size) | |
161 | { | |
162 | const struct pvector_impl *impl; | |
163 | struct pvector_cursor cursor; | |
164 | ||
165 | impl = ovsrcu_get(struct pvector_impl *, &pvec->impl); | |
166 | ||
167 | ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]); | |
168 | ||
169 | cursor.size = impl->size; | |
170 | cursor.vector = impl->vector; | |
171 | cursor.entry_idx = -1; | |
172 | ||
173 | for (size_t i = 0; i < n_ahead; i++) { | |
174 | /* Prefetch the first objects. */ | |
175 | pvector_cursor_lookahead(&cursor, i, obj_size); | |
176 | } | |
177 | return cursor; | |
178 | } | |
179 | ||
180 | static inline void *pvector_cursor_next(struct pvector_cursor *cursor, | |
eb391b76 | 181 | int stop_at_priority, |
fe7cfa5c JR |
182 | size_t n_ahead, size_t obj_size) |
183 | { | |
184 | if (++cursor->entry_idx < cursor->size && | |
185 | cursor->vector[cursor->entry_idx].priority > stop_at_priority) { | |
186 | if (n_ahead) { | |
187 | pvector_cursor_lookahead(cursor, n_ahead, obj_size); | |
188 | } | |
189 | return cursor->vector[cursor->entry_idx].ptr; | |
190 | } | |
191 | return NULL; | |
192 | } | |
193 | ||
194 | static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor, | |
195 | int n, size_t size) | |
196 | { | |
197 | if (cursor->entry_idx + n < cursor->size) { | |
198 | ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size); | |
199 | } | |
200 | } | |
201 | ||
202 | static inline size_t pvector_count(const struct pvector *pvec) | |
203 | { | |
204 | return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size; | |
205 | } | |
206 | ||
207 | static inline bool pvector_is_empty(const struct pvector *pvec) | |
208 | { | |
209 | return pvector_count(pvec) == 0; | |
210 | } | |
211 | ||
212 | #endif /* pvector.h */ |