lib/pvector.c

   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 #include <config.h>
  18 #include "pvector.h"
  19
  20 static struct pvector_impl *
  21 pvector_impl_get(const struct pvector *pvec)
  22 {
  23     return ovsrcu_get(struct pvector_impl *, &pvec->impl);
  24 }
  25
  26 static struct pvector_impl *
  27 pvector_impl_alloc(size_t size)
  28 {
  29     struct pvector_impl *impl;
  30
  31     impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
  32     impl->size = 0;
  33     impl->allocated = size;
  34
  35     return impl;
  36 }
  37
  38 static struct pvector_impl *
  39 pvector_impl_dup(struct pvector_impl *old)
  40 {
  41     return xmemdup(old, sizeof *old + old->allocated * sizeof old->vector[0]);
  42 }
  43
  44 /* Initializes 'pvec' as an empty concurrent priority vector. */
  45 void
  46 pvector_init(struct pvector *pvec)
  47 {
  48     ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
  49 }
  50
  51 /* Destroys 'pvec'.
  52  *
  53  * The client is responsible for destroying any data previously held in
  54  * 'pvec'. */
  55 void
  56 pvector_destroy(struct pvector *pvec)
  57 {
  58     ovsrcu_postpone(free, pvector_impl_get(pvec));
  59     ovsrcu_set(&pvec->impl, NULL); /* Poison. */
  60 }
  61
  62 /* Iterators for callers that need the 'index' afterward. */
  63 #define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL)          \
  64     for ((INDEX) = 0;                                      \
  65          (INDEX) < (IMPL)->size                            \
  66              && ((ENTRY) = &(IMPL)->vector[INDEX], true);  \
  67          (INDEX)++)
  68
  69 static int
  70 pvector_entry_cmp(const void *a_, const void *b_)
  71 {
  72     const struct pvector_entry *ap = a_;
  73     const struct pvector_entry *bp = b_;
  74     int a = ap->priority;
  75     int b = bp->priority;
  76
  77     return a > b ? -1 : a < b;
  78 }
  79
  80 static void
  81 pvector_impl_sort(struct pvector_impl *impl)
  82 {
  83     qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
  84 }
  85
  86 /* Returns the index with priority equal or lower than 'target_priority',
  87  * which will be one past the vector if none exists. */
  88 static int
  89 pvector_impl_find_priority(struct pvector_impl *impl,
  90                            int target_priority)
  91 {
  92     const struct pvector_entry *entry;
  93     int index;
  94
  95     PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
  96         if (entry->priority <= target_priority) {
  97             break;
  98         }
  99     }
 100     return index;
 101 }
 102
 103 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
 104 static int
 105 pvector_impl_find(struct pvector_impl *impl, void *target)
 106 {
 107     const struct pvector_entry *entry;
 108     int index;
 109
 110     PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
 111         if (entry->ptr == target) {
 112             return index;
 113         }
 114     }
 115     return -1;
 116 }
 117
 118 void
 119 pvector_insert(struct pvector *pvec, void *ptr, int priority)
 120 {
 121     struct pvector_impl *old, *new;
 122     int index;
 123
 124     ovs_assert(ptr != NULL);
 125
 126     old = pvector_impl_get(pvec);
 127
 128     /* Check if can add to the end without reallocation. */
 129     if (old->allocated > old->size &&
 130         (!old->size || priority <= old->vector[old->size - 1].priority)) {
 131         old->vector[old->size].ptr = ptr;
 132         old->vector[old->size].priority = priority;
 133         /* Size increment must not be visible to the readers before the new
 134          * entry is stored. */
 135         atomic_thread_fence(memory_order_release);
 136         ++old->size;
 137     } else {
 138         new = pvector_impl_alloc(old->size + 1 + PVECTOR_EXTRA_ALLOC);
 139
 140         index = pvector_impl_find_priority(old, priority);
 141         /* Now at the insertion index. */
 142         memcpy(new->vector, old->vector, index * sizeof old->vector[0]);
 143         new->vector[index].ptr = ptr;
 144         new->vector[index].priority = priority;
 145         memcpy(&new->vector[index + 1], &old->vector[index],
 146                (old->size - index) * sizeof old->vector[0]);
 147         new->size = old->size + 1;
 148
 149         ovsrcu_set(&pvec->impl, new);
 150         ovsrcu_postpone(free, old);
 151     }
 152 }
 153
 154 void
 155 pvector_remove(struct pvector *pvec, void *ptr)
 156 {
 157     struct pvector_impl *old, *new;
 158     int index;
 159
 160     old = pvector_impl_get(pvec);
 161
 162     ovs_assert(old->size > 0);
 163
 164     index = pvector_impl_find(old, ptr);
 165     ovs_assert(index >= 0);
 166     /* Now at the index of the entry to be deleted. */
 167
 168     /* We do not try to delete the last entry without reallocation so that
 169      * the readers can read the 'size' once in the beginning of each iteration.
 170      */
 171
 172     /* Keep extra space for insertions to the end. */
 173     new = pvector_impl_alloc(old->size - 1 + PVECTOR_EXTRA_ALLOC);
 174
 175     memcpy(new->vector, old->vector, index * sizeof old->vector[0]);
 176     memcpy(&new->vector[index], &old->vector[index + 1],
 177            (old->size - (index + 1)) * sizeof old->vector[0]);
 178
 179     new->size = old->size - 1;
 180
 181     ovsrcu_set(&pvec->impl, new);
 182     ovsrcu_postpone(free, old);
 183 }
 184
 185 /* Change entry's 'priority' and keep the vector ordered. */
 186 void
 187 pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
 188 {
 189     struct pvector_impl *old = pvector_impl_get(pvec);
 190     int index = pvector_impl_find(old, ptr);
 191
 192     ovs_assert(index >= 0);
 193     /* Now at the index of the entry to be updated. */
 194
 195     if ((priority > old->vector[index].priority && index > 0
 196          && priority > old->vector[index - 1].priority)
 197         || (priority < old->vector[index].priority && index < old->size - 1
 198             && priority < old->vector[index + 1].priority)) {
 199         /* Have to reallocate to reorder. */
 200         struct pvector_impl *new = pvector_impl_dup(old);
 201
 202         new->vector[index].priority = priority;
 203         pvector_impl_sort(new);
 204
 205         ovsrcu_set(&pvec->impl, new);
 206         ovsrcu_postpone(free, old);
 207     } else {
 208         /* Can update in place. Readers are free to use either value,
 209          * so we do not try to synchronize here. */
 210         old->vector[index].priority = priority;
 211     }
 212 }