[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