lib/pvector.c

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