2 * Copyright (c) 2014 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
25 /* Concurrent Priority Vector
26 * ==========================
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
33 * The priority order is maintained as a linear vector of elements to allow
34 * for efficient memory prefetching.
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.
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.
50 * Clients should not use priority INT_MIN.
53 struct pvector_entry {
58 /* Writers will preallocate space for some entries at the end to avoid future
60 enum { PVECTOR_EXTRA_ALLOC = 4 };
63 size_t size; /* Number of entries in the vector. */
64 size_t allocated; /* Number of allocated entries. */
65 struct pvector_entry vector[];
68 /* Concurrent priority vector. */
70 OVSRCU_TYPE(struct pvector_impl *) impl;
74 void pvector_init(struct pvector *);
75 void pvector_destroy(struct pvector *);
78 static inline size_t pvector_count(const struct pvector *);
79 static inline bool pvector_is_empty(const struct pvector *);
81 /* Insertion and deletion. */
82 void pvector_insert(struct pvector *, void *, int priority);
83 void pvector_change_priority(struct pvector *, void *, int priority);
84 void pvector_remove(struct pvector *, void *);
92 * Iteration is safe even in a pvector that is changing concurrently.
93 * Multiple writers must exclude each other via e.g., a mutex.
102 * struct my_node elem1, elem2, *iter;
103 * struct pvector my_pvector;
105 * pvector_init(&my_pvector);
107 * pvector_insert(&my_pvector, &elem1, 1);
108 * pvector_insert(&my_pvector, &elem2, 2);
110 * PVECTOR_FOR_EACH (iter, &my_pvector) {
111 * ...operate on '*iter'...
112 * ...elem2 to be seen before elem1...
115 * pvector_destroy(&my_pvector);
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
123 * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
124 * than given priority and allows for object lookahead.
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).
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;
136 static inline struct pvector_cursor pvector_cursor_init(const struct pvector *,
139 static inline void *pvector_cursor_next(struct pvector_cursor *,
140 int stop_at_priority,
141 size_t n_ahead, size_t obj_size);
142 static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
145 #define PVECTOR_FOR_EACH(PTR, PVECTOR) \
146 for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, 0, 0); \
147 ((PTR) = pvector_cursor_next(&cursor__, INT_MIN, 0, 0)) != NULL; )
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; )
156 /* Inline implementations. */
158 static inline struct pvector_cursor
159 pvector_cursor_init(const struct pvector *pvec,
160 size_t n_ahead, size_t obj_size)
162 const struct pvector_impl *impl;
163 struct pvector_cursor cursor;
165 impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);
167 ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]);
169 cursor.size = impl->size;
170 cursor.vector = impl->vector;
171 cursor.entry_idx = -1;
173 for (size_t i = 0; i < n_ahead; i++) {
174 /* Prefetch the first objects. */
175 pvector_cursor_lookahead(&cursor, i, obj_size);
180 static inline void *pvector_cursor_next(struct pvector_cursor *cursor,
181 int stop_at_priority,
182 size_t n_ahead, size_t obj_size)
184 if (++cursor->entry_idx < cursor->size &&
185 cursor->vector[cursor->entry_idx].priority > stop_at_priority) {
187 pvector_cursor_lookahead(cursor, n_ahead, obj_size);
189 return cursor->vector[cursor->entry_idx].ptr;
194 static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
197 if (cursor->entry_idx + n < cursor->size) {
198 ovs_prefetch_range(cursor->vector[cursor->entry_idx + n].ptr, size);
202 static inline size_t pvector_count(const struct pvector *pvec)
204 return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
207 static inline bool pvector_is_empty(const struct pvector *pvec)
209 return pvector_count(pvec) == 0;
212 #endif /* pvector.h */