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

Jarno Rajahalme jarno at ovn.org
Tue Aug 9 20:59:32 UTC 2016


This reverts commit 8bdfe1313894047d44349fa4cf4402970865950f.

I failed to see that lib/dpif-netdev.c actually needs the concurrency
provided by pvector prior to this change.  More specifically, when a
subtable is removed, concurrent lookups may skip over another subtable
swapped in to the place of the removed subtable in the vector.

Since this was the only use of the non-concurrent pvector, it is
cleaner to revert the whole patch.

Reported-by: Jan Scheurich <jan.scheurich at ericsson.com>
Signed-off-by: Jarno Rajahalme <jarno at ovn.org>
---
 lib/classifier.c        |  30 ++++----
 lib/classifier.h        |   6 +-
 lib/dpif-netdev.c       |  14 ++--
 lib/pvector.c           | 190 +++++++++++++++++++++++-------------------------
 lib/pvector.h           | 187 +++++++++++++++--------------------------------
 tests/test-classifier.c |  12 +--
 6 files changed, 182 insertions(+), 257 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index 8f195d5..0551146 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -325,7 +325,7 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments)
 {
     cls->n_rules = 0;
     cmap_init(&cls->subtables_map);
-    cpvector_init(&cls->subtables);
+    pvector_init(&cls->subtables);
     cls->n_flow_segments = 0;
     if (flow_segments) {
         while (cls->n_flow_segments < CLS_MAX_INDICES
@@ -359,7 +359,7 @@ classifier_destroy(struct classifier *cls)
         }
         cmap_destroy(&cls->subtables_map);
 
-        cpvector_destroy(&cls->subtables);
+        pvector_destroy(&cls->subtables);
     }
 }
 
@@ -658,20 +658,20 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
     if (n_rules == 1) {
         subtable->max_priority = rule->priority;
         subtable->max_count = 1;
-        cpvector_insert(&cls->subtables, subtable, rule->priority);
+        pvector_insert(&cls->subtables, subtable, rule->priority);
     } else if (rule->priority == subtable->max_priority) {
         ++subtable->max_count;
     } else if (rule->priority > subtable->max_priority) {
         subtable->max_priority = rule->priority;
         subtable->max_count = 1;
-        cpvector_change_priority(&cls->subtables, subtable, rule->priority);
+        pvector_change_priority(&cls->subtables, subtable, rule->priority);
     }
 
     /* Nothing was replaced. */
     cls->n_rules++;
 
     if (cls->publish) {
-        cpvector_publish(&cls->subtables);
+        pvector_publish(&cls->subtables);
     }
 
     return NULL;
@@ -803,12 +803,12 @@ check_priority:
                 }
             }
             subtable->max_priority = max_priority;
-            cpvector_change_priority(&cls->subtables, subtable, max_priority);
+            pvector_change_priority(&cls->subtables, subtable, max_priority);
         }
     }
 
     if (cls->publish) {
-        cpvector_publish(&cls->subtables);
+        pvector_publish(&cls->subtables);
     }
 
     /* free the rule. */
@@ -959,8 +959,8 @@ classifier_lookup__(const struct classifier *cls, ovs_version_t version,
 
     /* Main loop. */
     struct cls_subtable *subtable;
-    CPVECTOR_FOR_EACH_PRIORITY (subtable, hard_pri + 1, 2, sizeof *subtable,
-                                &cls->subtables) {
+    PVECTOR_FOR_EACH_PRIORITY (subtable, hard_pri + 1, 2, sizeof *subtable,
+                               &cls->subtables) {
         struct cls_conjunction_set *conj_set;
 
         /* Skip subtables with no match, or where the match is lower-priority
@@ -1231,8 +1231,8 @@ classifier_rule_overlaps(const struct classifier *cls,
     struct cls_subtable *subtable;
 
     /* Iterate subtables in the descending max priority order. */
-    CPVECTOR_FOR_EACH_PRIORITY (subtable, target->priority, 2,
-                                sizeof(struct cls_subtable), &cls->subtables) {
+    PVECTOR_FOR_EACH_PRIORITY (subtable, target->priority, 2,
+                               sizeof(struct cls_subtable), &cls->subtables) {
         struct {
             struct minimask mask;
             uint64_t storage[FLOW_U64S];
@@ -1350,8 +1350,8 @@ cls_cursor_start(const struct classifier *cls, const struct cls_rule *target,
     cursor.rule = NULL;
 
     /* Find first rule. */
-    CPVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
-                              &cursor.cls->subtables) {
+    PVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
+                             &cursor.cls->subtables) {
         const struct cls_rule *rule = search_subtable(subtable, &cursor);
 
         if (rule) {
@@ -1378,7 +1378,7 @@ cls_cursor_next(struct cls_cursor *cursor)
         }
     }
 
-    CPVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables) {
+    PVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables) {
         rule = search_subtable(subtable, cursor);
         if (rule) {
             cursor->subtable = subtable;
@@ -1510,7 +1510,7 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
 {
     int i;
 
-    cpvector_remove(&cls->subtables, subtable);
+    pvector_remove(&cls->subtables, subtable);
     cmap_remove(&cls->subtables_map, &subtable->cmap_node,
                 minimask_hash(&subtable->mask, 0));
 
diff --git a/lib/classifier.h b/lib/classifier.h
index 3ccf827..44185a3 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
+ * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -335,7 +335,7 @@ struct classifier {
     uint8_t flow_segments[CLS_MAX_INDICES]; /* Flow segment boundaries to use
                                              * for staged lookup. */
     struct cmap subtables_map;      /* Contains "struct cls_subtable"s.  */
-    struct cpvector subtables;
+    struct pvector subtables;
     struct cmap partitions;         /* Contains "struct cls_partition"s. */
     struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */
     unsigned int n_tries;
@@ -466,7 +466,7 @@ static inline void
 classifier_publish(struct classifier *cls)
 {
     cls->publish = true;
-    cpvector_publish(&cls->subtables);
+    pvector_publish(&cls->subtables);
 }
 
 #ifdef __cplusplus
diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 1541628..fe19b38 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -163,7 +163,7 @@ struct emc_cache {
 
 struct dpcls {
     struct cmap subtables_map;
-    struct pvector *subtables;
+    struct pvector subtables;
 };
 
 /* A rule to be inserted to the classifier. */
@@ -4770,13 +4770,13 @@ static void
 dpcls_init(struct dpcls *cls)
 {
     cmap_init(&cls->subtables_map);
-    cls->subtables = pvector_alloc(4);
+    pvector_init(&cls->subtables);
 }
 
 static void
 dpcls_destroy_subtable(struct dpcls *cls, struct dpcls_subtable *subtable)
 {
-    pvector_remove(cls->subtables, subtable);
+    pvector_remove(&cls->subtables, subtable);
     cmap_remove(&cls->subtables_map, &subtable->cmap_node,
                 subtable->mask.hash);
     cmap_destroy(&subtable->rules);
@@ -4797,7 +4797,7 @@ dpcls_destroy(struct dpcls *cls)
             dpcls_destroy_subtable(cls, subtable);
         }
         cmap_destroy(&cls->subtables_map);
-        free(cls->subtables);
+        pvector_destroy(&cls->subtables);
     }
 }
 
@@ -4812,7 +4812,8 @@ dpcls_create_subtable(struct dpcls *cls, const struct netdev_flow_key *mask)
     cmap_init(&subtable->rules);
     netdev_flow_key_clone(&subtable->mask, mask);
     cmap_insert(&cls->subtables_map, &subtable->cmap_node, mask->hash);
-    pvector_push_back(&cls->subtables, subtable, 0);
+    pvector_insert(&cls->subtables, subtable, 0);
+    pvector_publish(&cls->subtables);
 
     return subtable;
 }
@@ -4855,6 +4856,7 @@ dpcls_remove(struct dpcls *cls, struct dpcls_rule *rule)
     if (cmap_remove(&subtable->rules, &rule->cmap_node, rule->flow.hash)
         == 0) {
         dpcls_destroy_subtable(cls, subtable);
+        pvector_publish(&cls->subtables);
     }
 }
 
@@ -4918,7 +4920,7 @@ dpcls_lookup(const struct dpcls *cls, const struct netdev_flow_key keys[],
      * search-key against each subtable, but when a match is found for a
      * search-key, the search for that key can stop because the rules are
      * non-overlapping. */
-    PVECTOR_FOR_EACH (subtable, cls->subtables) {
+    PVECTOR_FOR_EACH (subtable, &cls->subtables) {
         const struct netdev_flow_key *mkeys = keys;
         struct dpcls_rule **mrules = rules;
         map_type remains = 0;
diff --git a/lib/pvector.c b/lib/pvector.c
index 5fb1899..aaeee92 100644
--- a/lib/pvector.c
+++ b/lib/pvector.c
@@ -21,30 +21,60 @@
  * reallocations. */
 enum { PVECTOR_EXTRA_ALLOC = 4 };
 
-struct pvector *
-pvector_alloc(size_t size)
+static struct pvector_impl *
+pvector_impl_get(const struct pvector *pvec)
 {
-    struct pvector *pvec;
+    return ovsrcu_get(struct pvector_impl *, &pvec->impl);
+}
+
+static struct pvector_impl *
+pvector_impl_alloc(size_t size)
+{
+    struct pvector_impl *impl;
 
-    pvec = xmalloc(sizeof *pvec + size * sizeof pvec->vector[0]);
-    pvec->size = 0;
-    pvec->allocated = size;
+    impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
+    impl->size = 0;
+    impl->allocated = size;
 
-    return pvec;
+    return impl;
+}
+
+static struct pvector_impl *
+pvector_impl_dup(struct pvector_impl *old)
+{
+    struct pvector_impl *impl;
+    size_t alloc = old->size + PVECTOR_EXTRA_ALLOC;
+
+    impl = xmalloc(sizeof *impl + alloc * sizeof impl->vector[0]);
+    impl->allocated = alloc;
+    impl->size = old->size;
+    memcpy(impl->vector, old->vector, old->size * sizeof old->vector[0]);
+    return impl;
 }
 
-static struct pvector *
-pvector_dup(const struct pvector *old)
+/* Initializes 'pvec' as an empty concurrent priority vector. */
+void
+pvector_init(struct pvector *pvec)
 {
-    struct pvector *pvec = pvector_alloc(old->size + PVECTOR_EXTRA_ALLOC);
+    ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
+    pvec->temp = NULL;
+}
 
-    pvec->size = old->size;
-    memcpy(pvec->vector, old->vector, old->size * sizeof old->vector[0]);
-    return pvec;
+/* Destroys 'pvec'.
+ *
+ * The client is responsible for destroying any data previously held in
+ * 'pvec'. */
+void
+pvector_destroy(struct pvector *pvec)
+{
+    free(pvec->temp);
+    pvec->temp = NULL;
+    ovsrcu_postpone(free, pvector_impl_get(pvec));
+    ovsrcu_set(&pvec->impl, NULL); /* Poison. */
 }
 
-/* Iterator for callers that need the 'index' afterward. */
-#define PVECTOR_FOR_EACH_ENTRY(ENTRY, INDEX, IMPL)         \
+/* 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);  \
@@ -61,20 +91,20 @@ pvector_entry_cmp(const void *a_, const void *b_)
     return a > b ? -1 : a < b;
 }
 
-void
-pvector_sort(struct pvector *pvec)
+static void
+pvector_impl_sort(struct pvector_impl *impl)
 {
-    qsort(pvec->vector, pvec->size, sizeof *pvec->vector, pvector_entry_cmp);
+    qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
 }
 
 /* Returns the index of the 'ptr' in the vector, or -1 if none is found. */
 static int
-pvector_find(const struct pvector *pvec, void *target)
+pvector_impl_find(struct pvector_impl *impl, void *target)
 {
     const struct pvector_entry *entry;
     int index;
 
-    PVECTOR_FOR_EACH_ENTRY (entry, index, pvec) {
+    PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
         if (entry->ptr == target) {
             return index;
         }
@@ -82,67 +112,11 @@ pvector_find(const struct pvector *pvec, void *target)
     return -1;
 }
 
-/* May re-allocate 'impl' */
-void
-pvector_push_back(struct pvector **pvecp, void *ptr, int priority)
-{
-    struct pvector *pvec = *pvecp;
-
-    if (pvec->size == pvec->allocated) {
-        pvec = pvector_dup(pvec);
-        free(*pvecp);
-        *pvecp = pvec;
-    }
-    /* Insert at the end, will be sorted later. */
-    pvec->vector[pvec->size].ptr = ptr;
-    pvec->vector[pvec->size].priority = priority;
-    pvec->size++;
-}
-
 void
-pvector_remove(struct pvector *pvec, void *ptr)
+pvector_insert(struct pvector *pvec, void *ptr, int priority)
 {
-    int index;
-
-    index = pvector_find(pvec, ptr);
-    ovs_assert(index >= 0);
-    /* Now at the index of the entry to be deleted.
-     * Swap another entry in if needed, can be sorted later. */
-    pvec->size--;
-    if (index != pvec->size) {
-        pvec->vector[index] = pvec->vector[pvec->size];
-    }
-}
-
-
-/* Concurrent version. */
-
-/* Initializes 'cpvec' as an empty concurrent priority vector. */
-void
-cpvector_init(struct cpvector *cpvec)
-{
-    ovsrcu_set(&cpvec->impl, pvector_alloc(PVECTOR_EXTRA_ALLOC));
-    cpvec->temp = NULL;
-}
-
-/* Destroys 'cpvec'.
- *
- * The client is responsible for destroying any data previously held in
- * 'pvec'. */
-void
-cpvector_destroy(struct cpvector *cpvec)
-{
-    free(cpvec->temp);
-    cpvec->temp = NULL;
-    ovsrcu_postpone(free, cpvector_get_pvector(cpvec));
-    ovsrcu_set(&cpvec->impl, NULL); /* Poison. */
-}
-
-void
-cpvector_insert(struct cpvector *cpvec, void *ptr, int priority)
-{
-    struct pvector *temp = cpvec->temp;
-    struct pvector *old = cpvector_get_pvector(cpvec);
+    struct pvector_impl *temp = pvec->temp;
+    struct pvector_impl *old = pvector_impl_get(pvec);
 
     ovs_assert(ptr != NULL);
 
@@ -157,37 +131,53 @@ cpvector_insert(struct cpvector *cpvec, void *ptr, int priority)
         ++old->size;
     } else {
         if (!temp) {
-            cpvec->temp = pvector_dup(old);
+            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;
         }
-        pvector_push_back(&cpvec->temp, ptr, priority);
+        /* Insert at the end, publish will sort. */
+        temp->vector[temp->size].ptr = ptr;
+        temp->vector[temp->size].priority = priority;
+        temp->size += 1;
     }
 }
 
 void
-cpvector_remove(struct cpvector *cpvec, void *ptr)
+pvector_remove(struct pvector *pvec, void *ptr)
 {
-    struct pvector *temp = cpvec->temp;
+    struct pvector_impl *temp = pvec->temp;
+    int index;
 
     if (!temp) {
-        temp = pvector_dup(cpvector_get_pvector(cpvec));
-        cpvec->temp = temp;
+        temp = pvector_impl_dup(pvector_impl_get(pvec));
+        pvec->temp = temp;
     }
     ovs_assert(temp->size > 0);
-    pvector_remove(temp, ptr);   /* Publish will sort. */
+    index = pvector_impl_find(temp, ptr);
+    ovs_assert(index >= 0);
+    /* Now at the index of the entry to be deleted.
+     * Swap another entry in if needed, publish will sort anyway. */
+    temp->size--;
+    if (index != temp->size) {
+        temp->vector[index] = temp->vector[temp->size];
+    }
 }
 
 /* Change entry's 'priority' and keep the vector ordered. */
 void
-cpvector_change_priority(struct cpvector *cpvec, void *ptr, int priority)
+pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
 {
-    struct pvector *old = cpvec->temp;
+    struct pvector_impl *old = pvec->temp;
     int index;
 
     if (!old) {
-        old = cpvector_get_pvector(cpvec);
+        old = pvector_impl_get(pvec);
     }
 
-    index = pvector_find(old, ptr);
+    index = pvector_impl_find(old, ptr);
 
     ovs_assert(index >= 0);
     /* Now at the index of the entry to be updated. */
@@ -198,10 +188,10 @@ cpvector_change_priority(struct cpvector *cpvec, void *ptr, int priority)
         || (priority < old->vector[index].priority && index < old->size - 1
             && priority < old->vector[index + 1].priority)) {
         /* Have to use a temp. */
-        if (!cpvec->temp) {
+        if (!pvec->temp) {
             /* Have to reallocate to reorder. */
-            cpvec->temp = pvector_dup(old);
-            old = cpvec->temp;
+            pvec->temp = pvector_impl_dup(old);
+            old = pvec->temp;
             /* Publish will sort. */
         }
     }
@@ -209,13 +199,13 @@ cpvector_change_priority(struct cpvector *cpvec, void *ptr, int priority)
 }
 
 /* Make the modified pvector available for iteration. */
-void cpvector_publish__(struct cpvector *cpvec)
+void pvector_publish__(struct pvector *pvec)
 {
-    struct pvector *temp = cpvec->temp;
+    struct pvector_impl *temp = pvec->temp;
 
-    cpvec->temp = NULL;
-    pvector_sort(temp); /* Also removes gaps. */
-    ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector *,
-                                               &cpvec->impl));
-    ovsrcu_set(&cpvec->impl, temp);
+    pvec->temp = NULL;
+    pvector_impl_sort(temp); /* Also removes gaps. */
+    ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector_impl *,
+                                               &pvec->impl));
+    ovsrcu_set(&pvec->impl, temp);
 }
diff --git a/lib/pvector.h b/lib/pvector.h
index 00cb757..b175b21 100644
--- a/lib/pvector.h
+++ b/lib/pvector.h
@@ -49,7 +49,7 @@
  * values, or decrement the 'size' on a copy that readers have access to.
  *
  * Most modifications are internally staged at the 'temp' vector, from which
- * they can be published at 'impl' by calling cpvector_publish().  This saves
+ * they can be published at 'impl' by calling pvector_publish().  This saves
  * unnecessary memory allocations when many changes are done back-to-back.
  * 'temp' may contain NULL pointers and it may be in unsorted order.  It is
  * sorted before it is published at 'impl', which also removes the NULLs from
@@ -61,17 +61,33 @@ struct pvector_entry {
     void *ptr;
 };
 
-/* Non-concurrent priority vector. */
-struct pvector {
+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 *pvector_alloc(size_t);
-void pvector_push_back(struct pvector **, void *ptr, int priority);
-void pvector_remove(struct pvector *, void *ptr);
-void pvector_sort(struct pvector *);
+/* Concurrent priority vector. */
+struct pvector {
+    OVSRCU_TYPE(struct pvector_impl *) impl;
+    struct pvector_impl *temp;
+};
+
+/* Initialization. */
+void pvector_init(struct pvector *);
+void pvector_destroy(struct pvector *);
+
+/* Insertion and deletion.  These work on 'temp'.  */
+void pvector_insert(struct pvector *, void *, int priority);
+void pvector_change_priority(struct pvector *, void *, int priority);
+void pvector_remove(struct pvector *, void *);
+
+/* Make the modified pvector available for iteration. */
+static inline void pvector_publish(struct pvector *);
+
+/* Count.  These operate on the published pvector. */
+static inline size_t pvector_count(const struct pvector *);
+static inline bool pvector_is_empty(const struct pvector *);
 
 /* Iteration.
  *
@@ -79,9 +95,8 @@ void pvector_sort(struct pvector *);
  * Thread-safety
  * =============
  *
- * These iterators operate on the non-concurrent pvector, and are not thread
- * safe.  Any entry may be skipped if entires are removed (with
- * pvector_remove()) during iteration.
+ * Iteration is safe even in a pvector that is changing concurrently.
+ * Multiple writers must exclude each other via e.g., a mutex.
  *
  * Example
  * =======
@@ -91,28 +106,32 @@ void pvector_sort(struct pvector *);
  *     };
  *
  *     struct my_node elem1, elem2, *iter;
- *     struct pvector *my_pvector;
+ *     struct pvector my_pvector;
  *
- *     my_pvector = pvector_alloc(0);
+ *     pvector_init(&my_pvector);
  *     ...add data...
- *     pvector_push_back(&my_pvector, &elem1, 1);
- *     pvector_push_back(&my_pvector, &elem2, 2);
- *     ...sort...
- *     pvector_sort(my_pvector);
+ *     pvector_insert(&my_pvector, &elem1, 1);
+ *     pvector_insert(&my_pvector, &elem2, 2);
  *     ...
- *     PVECTOR_FOR_EACH (iter, &my_cpvector) {
+ *     PVECTOR_FOR_EACH (iter, &my_pvector) {
  *         ...operate on '*iter'...
  *         ...elem2 to be seen before elem1...
  *     }
- *     ...remove entries...
- *     pvector_remove(my_pvector, &elem1);
  *     ...
- *     free(my_pvector);
+ *     pvector_destroy(&my_pvector);
  *
- * Currently there is no PVECTOR_FOR_EACH_SAFE variant.
+ * There is no PVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU
+ * protected instance of the priority vector.  Any concurrent modifications
+ * that would be disruptive for readers (such as deletions), will be performed
+ * on a new instance.  To see any of the modifications, a new iteration loop
+ * has to be started.
  *
  * The PVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
  * than or equal to the given priority and allows for object lookahead.
+ *
+ * The iteration loop must be completed without entering the OVS RCU quiescent
+ * period.  That is, an old iteration loop must not be continued after any
+ * blocking IO (VLOG is non-blocking, so that is OK).
  */
 struct pvector_cursor {
     size_t size;        /* Number of entries in the vector. */
@@ -124,7 +143,7 @@ static inline struct pvector_cursor pvector_cursor_init(const struct pvector *,
                                                         size_t n_ahead,
                                                         size_t obj_size);
 static inline void *pvector_cursor_next(struct pvector_cursor *,
-                                        int stop_at_priority,
+                                        int lowest_priority,
                                         size_t n_ahead, size_t obj_size);
 static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
                                             int n, size_t size);
@@ -139,109 +158,29 @@ static inline void pvector_cursor_lookahead(const struct pvector_cursor *,
     for (struct pvector_cursor cursor__ = pvector_cursor_init(PVECTOR, N, SZ); \
          ((PTR) = pvector_cursor_next(&cursor__, PRIORITY, N, SZ)) != NULL; )
 
-#define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR)                   \
-    for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0);                \
+#define PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, PVECTOR)                \
+    for (*(CURSOR) = pvector_cursor_init(PVECTOR, 0, 0);             \
          ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )
 
 #define PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR)                   \
     for (; ((PTR) = pvector_cursor_next(CURSOR, INT_MIN, 0, 0)) != NULL; )
 
 
-/* Concurrent priority vector. */
-struct cpvector {
-    OVSRCU_TYPE(struct pvector *) impl;
-    struct pvector *temp;
-};
-
-/* Initialization. */
-void cpvector_init(struct cpvector *);
-void cpvector_destroy(struct cpvector *);
-
-/* Insertion and deletion.  These work on 'temp'.  */
-void cpvector_insert(struct cpvector *, void *, int priority);
-void cpvector_change_priority(struct cpvector *, void *, int priority);
-void cpvector_remove(struct cpvector *, void *);
-
-/* Make the modified cpvector available for iteration. */
-static inline void cpvector_publish(struct cpvector *);
-
-/* Count.  These operate on the published cpvector. */
-static inline size_t cpvector_count(const struct cpvector *);
-static inline bool cpvector_is_empty(const struct cpvector *);
-
-static inline struct pvector *cpvector_get_pvector(const struct cpvector *);
-
-/* Iteration.
- *
- *
- * Thread-safety
- * =============
- *
- * Iteration is safe even in a cpvector that is changing concurrently.
- * Multiple writers must exclude each other via e.g., a mutex.
- *
- * Example
- * =======
- *
- *     struct my_node {
- *         int data;
- *     };
- *
- *     struct my_node elem1, elem2, *iter;
- *     struct cpvector my_cpvector;
- *
- *     cpvector_init(&my_cpvector);
- *     ...add data...
- *     cpvector_insert(&my_cpvector, &elem1, 1);
- *     cpvector_insert(&my_cpvector, &elem2, 2);
- *     ...
- *     CPVECTOR_FOR_EACH (iter, &my_cpvector) {
- *         ...operate on '*iter'...
- *         ...elem2 to be seen before elem1...
- *     }
- *     ...
- *     cpvector_destroy(&my_cpvector);
- *
- * There is no CPVECTOR_FOR_EACH_SAFE variant as iteration is performed on RCU
- * protected instance of the priority vector.  Any concurrent modifications
- * that would be disruptive for readers (such as deletions), will be performed
- * on a new instance.  To see any of the modifications, a new iteration loop
- * has to be started.
- *
- * The CPVECTOR_FOR_EACH_PRIORITY limits the iteration to entries with higher
- * than or equal to the given priority and allows for object lookahead.
- *
- * The iteration loop must be completed without entering the OVS RCU quiescent
- * period.  That is, an old iteration loop must not be continued after any
- * blocking IO (VLOG is non-blocking, so that is OK).
- */
-
-#define CPVECTOR_FOR_EACH(PTR, CPVECTOR)                \
-    PVECTOR_FOR_EACH(PTR, cpvector_get_pvector(CPVECTOR))
-
-#define CPVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ, CPVECTOR)      \
-    PVECTOR_FOR_EACH_PRIORITY(PTR, PRIORITY, N, SZ,                     \
-                              cpvector_get_pvector(CPVECTOR))
-
-#define CPVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, CPVECTOR)                 \
-    PVECTOR_CURSOR_FOR_EACH(PTR, CURSOR, cpvector_get_pvector(CPVECTOR))
-
-#define CPVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR)  \
-    PVECTOR_CURSOR_FOR_EACH_CONTINUE(PTR, CURSOR)
-
-
 /* Inline implementations. */
 
 static inline struct pvector_cursor
-pvector_cursor_init(const struct pvector *pvec, size_t n_ahead,
-                    size_t obj_size)
+pvector_cursor_init(const struct pvector *pvec,
+                    size_t n_ahead, size_t obj_size)
 {
+    const struct pvector_impl *impl;
     struct pvector_cursor cursor;
 
-    ovs_prefetch_range(pvec->vector, pvec->size * sizeof pvec->vector[0]);
+    impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);
 
-    cursor.size = pvec->size;
-    cursor.vector = pvec->vector;
+    ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]);
+
+    cursor.size = impl->size;
+    cursor.vector = impl->vector;
     cursor.entry_idx = -1;
 
     for (size_t i = 0; i < n_ahead; i++) {
@@ -273,29 +212,23 @@ static inline void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
     }
 }
 
-static inline struct pvector *
-cpvector_get_pvector(const struct cpvector *cpvec)
-{
-    return ovsrcu_get(struct pvector *, &cpvec->impl);
-}
-
-static inline size_t cpvector_count(const struct cpvector *cpvec)
+static inline size_t pvector_count(const struct pvector *pvec)
 {
-    return cpvector_get_pvector(cpvec)->size;
+    return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
 }
 
-static inline bool cpvector_is_empty(const struct cpvector *cpvec)
+static inline bool pvector_is_empty(const struct pvector *pvec)
 {
-    return cpvector_count(cpvec) == 0;
+    return pvector_count(pvec) == 0;
 }
 
-void cpvector_publish__(struct cpvector *);
+void pvector_publish__(struct pvector *);
 
-/* Make the modified cpvector available for iteration. */
-static inline void cpvector_publish(struct cpvector *cpvec)
+/* Make the modified pvector available for iteration. */
+static inline void pvector_publish(struct pvector *pvec)
 {
-    if (cpvec->temp) {
-        cpvector_publish__(cpvec);
+    if (pvec->temp) {
+        pvector_publish__(pvec);
     }
 }
 
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index cdd83f0..3a275b4 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
+ * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -472,12 +472,12 @@ destroy_classifier(struct classifier *cls)
 }
 
 static void
-cpvector_verify(const struct cpvector *cpvec)
+pvector_verify(const struct pvector *pvec)
 {
     void *ptr OVS_UNUSED;
     int prev_priority = INT_MAX;
 
-    CPVECTOR_FOR_EACH (ptr, cpvec) {
+    PVECTOR_FOR_EACH (ptr, pvec) {
         int priority = cursor__.vector[cursor__.entry_idx].priority;
         if (priority > prev_priority) {
             ovs_abort(0, "Priority vector is out of order (%u > %u)",
@@ -533,7 +533,7 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
     int found_visible_but_removable = 0;
     int found_rules2 = 0;
 
-    cpvector_verify(&cls->subtables);
+    pvector_verify(&cls->subtables);
     CMAP_FOR_EACH (table, cmap_node, &cls->subtables_map) {
         const struct cls_match *head;
         int max_priority = INT_MIN;
@@ -543,7 +543,7 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
         const struct cls_subtable *iter;
 
         /* Locate the subtable from 'subtables'. */
-        CPVECTOR_FOR_EACH (iter, &cls->subtables) {
+        PVECTOR_FOR_EACH (iter, &cls->subtables) {
             if (iter == table) {
                 if (found) {
                     ovs_abort(0, "Subtable %p duplicated in 'subtables'.",
@@ -647,7 +647,7 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
     }
 
     assert(found_tables == cmap_count(&cls->subtables_map));
-    assert(found_tables == cpvector_count(&cls->subtables));
+    assert(found_tables == pvector_count(&cls->subtables));
     assert(n_tables == -1 || n_tables == found_tables_with_visible_rules);
     assert(n_rules == -1 || found_rules == n_rules + found_invisible);
     assert(n_dups == -1 || found_dups == n_dups);
-- 
2.1.4




More information about the dev mailing list