[ovs-dev] [PATCH] pvector: Expose non-concurrent priority vector.

Jarno Rajahalme jarno at ovn.org
Wed Jun 22 00:18:45 UTC 2016


PMD threads use pvectors but do not need the overhead of the
concurrent version.  Expose the internal non-concurrent version for
that use.

Signed-off-by: Jarno Rajahalme <jarno at ovn.org>
---
 lib/pvector.c | 71 +++++++++++++++++++++++++++++++++++------------------------
 lib/pvector.h | 13 +++++++++++
 2 files changed, 55 insertions(+), 29 deletions(-)

diff --git a/lib/pvector.c b/lib/pvector.c
index fd30819..00880bd 100644
--- a/lib/pvector.c
+++ b/lib/pvector.c
@@ -23,7 +23,7 @@ pvector_impl_get(const struct pvector *pvec)
     return ovsrcu_get(struct pvector_impl *, &pvec->impl);
 }
 
-static struct pvector_impl *
+struct pvector_impl *
 pvector_impl_alloc(size_t size)
 {
     struct pvector_impl *impl;
@@ -36,7 +36,7 @@ pvector_impl_alloc(size_t size)
 }
 
 static struct pvector_impl *
-pvector_impl_dup(struct pvector_impl *old)
+pvector_impl_dup(const struct pvector_impl *old)
 {
     struct pvector_impl *impl;
     size_t alloc = old->size + PVECTOR_EXTRA_ALLOC;
@@ -69,13 +69,6 @@ pvector_destroy(struct pvector *pvec)
     ovsrcu_set(&pvec->impl, NULL); /* Poison. */
 }
 
-/* Iterators for callers that need the 'index' afterward. */
-#define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL)          \
-    for ((INDEX) = 0;                                      \
-         (INDEX) < (IMPL)->size                            \
-             && ((ENTRY) = &(IMPL)->vector[INDEX], true);  \
-         (INDEX)++)
-
 static int
 pvector_entry_cmp(const void *a_, const void *b_)
 {
@@ -87,24 +80,26 @@ pvector_entry_cmp(const void *a_, const void *b_)
     return a > b ? -1 : a < b;
 }
 
-static void
+/* Also removes gaps marked by priority == INT_MIN. */
+void
 pvector_impl_sort(struct pvector_impl *impl)
 {
     qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
-    /* Trim gaps. */
+    /* Gaps have been sorted to the end, since they have the minimum possible
+     * priority.  Remove them. */
     while (impl->size && impl->vector[impl->size - 1].priority == INT_MIN) {
-        impl->size = impl->size - 1;
+        impl->size--;
     }
 }
 
 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
 static int
-pvector_impl_find(struct pvector_impl *impl, void *target)
+pvector_impl_find(const struct pvector_impl *impl, void *target)
 {
     const struct pvector_entry *entry;
     int index;
 
-    PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
+    PVECTOR_IMPL_FOR_EACH_ENTRY (entry, index, impl) {
         if (entry->ptr == target) {
             return index;
         }
@@ -112,6 +107,23 @@ pvector_impl_find(struct pvector_impl *impl, void *target)
     return -1;
 }
 
+/* May re-allocate 'impl' */
+void
+pvector_impl_push_back(struct pvector_impl **implp, void *ptr, int priority)
+{
+    struct pvector_impl *impl = *implp;
+
+    if (impl->size == impl->allocated) {
+        impl = pvector_impl_dup(impl);
+        free(*implp);
+        *implp = impl;
+    }
+    /* Insert at the end, will be sorted later. */
+    impl->vector[impl->size].ptr = ptr;
+    impl->vector[impl->size].priority = priority;
+    impl->size++;
+}
+
 void
 pvector_insert(struct pvector *pvec, void *ptr, int priority)
 {
@@ -133,35 +145,36 @@ pvector_insert(struct pvector *pvec, void *ptr, int priority)
         if (!temp) {
             temp = pvector_impl_dup(old);
             pvec->temp = temp;
-        } else if (temp->size == temp->allocated) {
-            temp = pvector_impl_dup(temp);
-            free(pvec->temp);
-            pvec->temp = temp;
         }
-        /* Insert at the end, publish will sort. */
-        temp->vector[temp->size].ptr = ptr;
-        temp->vector[temp->size].priority = priority;
-        temp->size += 1;
+
+        pvector_impl_push_back(&pvec->temp, ptr, priority);
     }
 }
 
 void
+pvector_impl_remove(struct pvector_impl *impl, void *ptr)
+{
+    int index;
+
+    index = pvector_impl_find(impl, ptr);
+    ovs_assert(index >= 0);
+    /* Now at the index of the entry to be deleted.
+     * Clear in place, sort will clean these off. */
+    impl->vector[index].ptr = NULL;
+    impl->vector[index].priority = INT_MIN;
+}
+
+void
 pvector_remove(struct pvector *pvec, void *ptr)
 {
     struct pvector_impl *temp = pvec->temp;
-    int index;
 
     if (!temp) {
         temp = pvector_impl_dup(pvector_impl_get(pvec));
         pvec->temp = temp;
     }
     ovs_assert(temp->size > 0);
-    index = pvector_impl_find(temp, ptr);
-    ovs_assert(index >= 0);
-    /* Now at the index of the entry to be deleted.
-     * Clear in place, publish will sort and clean these off. */
-    temp->vector[index].ptr = NULL;
-    temp->vector[index].priority = INT_MIN;
+    pvector_impl_remove(temp, ptr);
 }
 
 /* Change entry's 'priority' and keep the vector ordered. */
diff --git a/lib/pvector.h b/lib/pvector.h
index 7e2164c..d4bf23a 100644
--- a/lib/pvector.h
+++ b/lib/pvector.h
@@ -67,12 +67,25 @@ struct pvector_entry {
  * reallocations. */
 enum { PVECTOR_EXTRA_ALLOC = 4 };
 
+/* Non-concurrent priority vector. */
 struct pvector_impl {
     size_t size;       /* Number of entries in the vector. */
     size_t allocated;  /* Number of allocated entries. */
     struct pvector_entry vector[];
 };
 
+struct pvector_impl *pvector_impl_alloc(size_t);
+void pvector_impl_push_back(struct pvector_impl **, void *ptr, int priority);
+void pvector_impl_remove(struct pvector_impl *, void *ptr);
+void pvector_impl_sort(struct pvector_impl *);
+
+/* Iterators for callers that need the 'index' afterward. */
+#define PVECTOR_IMPL_FOR_EACH_ENTRY(ENTRY, INDEX, IMPL)    \
+    for ((INDEX) = 0;                                      \
+         (INDEX) < (IMPL)->size                            \
+             && ((ENTRY) = &(IMPL)->vector[INDEX], true);  \
+         (INDEX)++)
+
 /* Concurrent priority vector. */
 struct pvector {
     OVSRCU_TYPE(struct pvector_impl *) impl;
-- 
2.1.4




More information about the dev mailing list