Simple revert, looks good to me, thanks
Acked-by: Daniele Di Proietto <diproiet...@vmware.com>
2016-08-09 13:59 GMT-07:00 Jarno Rajahalme <ja...@ovn.org>:
> 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.scheur...@ericsson.com>
> Signed-off-by: Jarno Rajahalme <ja...@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
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
