lib/pvector.h

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