lib/pvector.h

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