Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2014, 2016 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 <stdlib.h>
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.
50 : : *
51 : : * Most modifications are internally staged at the 'temp' vector, from which
52 : : * they can be published at 'impl' by calling pvector_publish(). This saves
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.
57 : : */
58 : :
59 : : struct pvector_entry {
60 : : int priority;
61 : : void *ptr;
62 : : };
63 : :
64 : : struct pvector_impl {
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 : :
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 *);
91 : :
92 : : /* Iteration.
93 : : *
94 : : *
95 : : * Thread-safety
96 : : * =============
97 : : *
98 : : * Iteration is safe even in a pvector that is changing concurrently.
99 : : * Multiple writers must exclude each other via e.g., a mutex.
100 : : *
101 : : * Example
102 : : * =======
103 : : *
104 : : * struct my_node {
105 : : * int data;
106 : : * };
107 : : *
108 : : * struct my_node elem1, elem2, *iter;
109 : : * struct pvector my_pvector;
110 : : *
111 : : * pvector_init(&my_pvector);
112 : : * ...add data...
113 : : * pvector_insert(&my_pvector, &elem1, 1);
114 : : * pvector_insert(&my_pvector, &elem2, 2);
115 : : * ...
116 : : * PVECTOR_FOR_EACH (iter, &my_pvector) {
117 : : * ...operate on '*iter'...
118 : : * ...elem2 to be seen before elem1...
119 : : * }
120 : : * ...
121 : : * pvector_destroy(&my_pvector);
122 : : *
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.
128 : : *
129 : : * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
130 : : * than or equal to the given priority and allows for object lookahead.
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).
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 *,
146 : : int lowest_priority,
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); \
153 : : ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; )
154 : :
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. */
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 : :
161 : : #define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR) \
162 : : for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0); \
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 : :
168 : :
169 : : /* Inline implementations. */
170 : :
171 : : static inline struct pvector_cursor
172 : 83771769 : pvector_cursor_init(const struct pvector *pvec,
173 : : size_t n_ahead, size_t obj_size)
174 : : {
175 : : const struct pvector_impl *impl;
176 : : struct pvector_cursor cursor;
177 : :
178 : 83771769 : impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);
179 : :
180 : 83771769 : ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]);
181 : :
182 : 83771771 : cursor.size = impl->size;
183 : 83771771 : cursor.vector = impl->vector;
184 : 83771771 : cursor.entry_idx = -1;
185 : :
186 [ + + ]: 249085951 : for (size_t i = 0; i < n_ahead; i++) {
187 : : /* Prefetch the first objects. */
188 : 165314182 : pvector_cursor_lookahead(&cursor, i, obj_size);
189 : : }
190 : 83771769 : return cursor;
191 : : }
192 : :
193 : 171132093 : static inline void *pvector_cursor_next(struct pvector_cursor *cursor,
194 : : int lowest_priority,
195 : : size_t n_ahead, size_t obj_size)
196 : : {
197 [ + + ][ + + ]: 171132093 : if (++cursor->entry_idx < cursor->size &&
198 : 91338524 : cursor->vector[cursor->entry_idx].priority >= lowest_priority) {
199 [ + + ]: 87366221 : if (n_ahead) {
200 : 86784282 : pvector_cursor_lookahead(cursor, n_ahead, obj_size);
201 : : }
202 : 87366221 : return cursor->vector[cursor->entry_idx].ptr;
203 : : }
204 : 83765872 : return NULL;
205 : : }
206 : :
207 : 252098456 : static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
208 : : int n, size_t size)
209 : : {
210 [ + + ]: 252098456 : if (cursor->entry_idx + n < cursor->size) {
211 : 76633730 : ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size);
212 : : }
213 : 252098456 : }
214 : :
215 : 50792 : static inline size_t pvector_count(const struct pvector *pvec)
216 : : {
217 : 50792 : return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
218 : : }
219 : :
220 : : static inline bool pvector_is_empty(const struct pvector *pvec)
221 : : {
222 : : return pvector_count(pvec) == 0;
223 : : }
224 : :
225 : : void pvector_publish__(struct pvector *);
226 : :
227 : : /* Make the modified pvector available for iteration. */
228 : 884984 : static inline void pvector_publish(struct pvector *pvec)
229 : : {
230 [ + + ]: 884984 : if (pvec->temp) {
231 : 389567 : pvector_publish__(pvec);
232 : : }
233 : 884984 : }
234 : :
235 : : #endif /* pvector.h */
|
