[ovs-dev] [PATCH v2 3/3] pvector: Expose non-concurrent priority vector.
Jan Scheurich
jan.scheurich at ericsson.com
Mon Aug 8 22:10:57 UTC 2016
Hi Jarno,
While trying to rebase my "dpcls per in_port" patch to your updated pvector/cpvector implementation, I have stumbled over a threading issue in your patch.
I believe that dpcls_destroy_subtable(), which may be invoked from revalidater threads at flow removal, should not simply call the new non-concurrent pvector_remove() function as this may destroy the priority order of the vector when it swaps in the last element.
In this particular case the damage done to the concurrently iterating PMD thread might not be fatal, but I believe using the non-concurrent API from two different threads is not OK. Seizing the pmd->flow_mutex for flow removal does not suffice as it does not prevent the PMD thread from iterating the pvector at lookup.
In my view we should revert dpcls to use the concurrent cpvector API. I would also use that approach for v3 of my "dpcls per in_port with sorted subtables" patch.
BR, Jan
> -----Original Message-----
> From: dev [mailto:dev-bounces at openvswitch.org] On Behalf Of Jarno
> Rajahalme
> Sent: Wednesday, 06 July, 2016 14:26
> To: dev at openvswitch.org
> Subject: [ovs-dev] [PATCH v2 3/3] pvector: Expose non-concurrent priority
> vector.
>
> PMD threads use pvectors but do not need the overhead of the concurrent
> version. Expose the non-concurrent version for that use.
>
> Note that struct pvector is renamed as struct cpvector (for concurrent priority
> vector), and the former struct pvector_impl is now struct pvector.
>
> 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, 257 insertions(+), 182 deletions(-)
>
> diff --git a/lib/classifier.c b/lib/classifier.c index 54941ed..8af1cb6 100644
> --- a/lib/classifier.c
> +++ b/lib/classifier.c
> @@ -326,7 +326,7 @@ classifier_init(struct classifier *cls, const uint8_t
> *flow_segments) {
> cls->n_rules = 0;
> cmap_init(&cls->subtables_map);
> - pvector_init(&cls->subtables);
> + cpvector_init(&cls->subtables);
> cls->n_flow_segments = 0;
> if (flow_segments) {
> while (cls->n_flow_segments < CLS_MAX_INDICES @@ -360,7 +360,7 @@
> classifier_destroy(struct classifier *cls)
> }
> cmap_destroy(&cls->subtables_map);
>
> - pvector_destroy(&cls->subtables);
> + cpvector_destroy(&cls->subtables);
> }
> }
>
> @@ -659,20 +659,20 @@ classifier_replace(struct classifier *cls, const struct
> cls_rule *rule,
> if (n_rules == 1) {
> subtable->max_priority = rule->priority;
> subtable->max_count = 1;
> - pvector_insert(&cls->subtables, subtable, rule->priority);
> + cpvector_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;
> - pvector_change_priority(&cls->subtables, subtable, rule->priority);
> + cpvector_change_priority(&cls->subtables, subtable,
> + rule->priority);
> }
>
> /* Nothing was replaced. */
> cls->n_rules++;
>
> if (cls->publish) {
> - pvector_publish(&cls->subtables);
> + cpvector_publish(&cls->subtables);
> }
>
> return NULL;
> @@ -804,12 +804,12 @@ check_priority:
> }
> }
> subtable->max_priority = max_priority;
> - pvector_change_priority(&cls->subtables, subtable, max_priority);
> + cpvector_change_priority(&cls->subtables, subtable,
> + max_priority);
> }
> }
>
> if (cls->publish) {
> - pvector_publish(&cls->subtables);
> + cpvector_publish(&cls->subtables);
> }
>
> /* free the rule. */
> @@ -960,8 +960,8 @@ classifier_lookup__(const struct classifier *cls,
> cls_version_t version,
>
> /* Main loop. */
> struct cls_subtable *subtable;
> - PVECTOR_FOR_EACH_PRIORITY (subtable, hard_pri + 1, 2, sizeof *subtable,
> - &cls->subtables) {
> + CPVECTOR_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 @@
> -1232,8 +1232,8 @@ classifier_rule_overlaps(const struct classifier *cls,
> struct cls_subtable *subtable;
>
> /* Iterate subtables in the descending max priority order. */
> - PVECTOR_FOR_EACH_PRIORITY (subtable, target->priority, 2,
> - sizeof(struct cls_subtable), &cls->subtables) {
> + CPVECTOR_FOR_EACH_PRIORITY (subtable, target->priority, 2,
> + sizeof(struct cls_subtable),
> + &cls->subtables) {
> struct {
> struct minimask mask;
> uint64_t storage[FLOW_U64S]; @@ -1351,8 +1351,8 @@
> cls_cursor_start(const struct classifier *cls, const struct cls_rule *target,
> cursor.rule = NULL;
>
> /* Find first rule. */
> - PVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
> - &cursor.cls->subtables) {
> + CPVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
> + &cursor.cls->subtables) {
> const struct cls_rule *rule = search_subtable(subtable, &cursor);
>
> if (rule) {
> @@ -1379,7 +1379,7 @@ cls_cursor_next(struct cls_cursor *cursor)
> }
> }
>
> - PVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables) {
> + CPVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables)
> {
> rule = search_subtable(subtable, cursor);
> if (rule) {
> cursor->subtable = subtable; @@ -1511,7 +1511,7 @@
> destroy_subtable(struct classifier *cls, struct cls_subtable *subtable) {
> int i;
>
> - pvector_remove(&cls->subtables, subtable);
> + cpvector_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 6247350..f058071 100644
> --- a/lib/classifier.h
> +++ b/lib/classifier.h
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
> + * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
> *
> * Licensed under the Apache License, Version 2.0 (the "License");
> * you may not use this file except in compliance with the License.
> @@ -340,7 +340,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 pvector subtables;
> + struct cpvector subtables;
> struct cmap partitions; /* Contains "struct cls_partition"s. */
> struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */
> unsigned int n_tries;
> @@ -471,7 +471,7 @@ static inline void
> classifier_publish(struct classifier *cls) {
> cls->publish = true;
> - pvector_publish(&cls->subtables);
> + cpvector_publish(&cls->subtables);
> }
>
> #ifdef __cplusplus
> diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 37c2631..5abc363 100644
> --- a/lib/dpif-netdev.c
> +++ b/lib/dpif-netdev.c
> @@ -151,7 +151,7 @@ struct emc_cache {
>
> struct dpcls {
> struct cmap subtables_map;
> - struct pvector subtables;
> + struct pvector *subtables;
> };
>
> /* A rule to be inserted to the classifier. */ @@ -4381,13 +4381,13 @@ static
> void dpcls_init(struct dpcls *cls) {
> cmap_init(&cls->subtables_map);
> - pvector_init(&cls->subtables);
> + cls->subtables = pvector_alloc(4);
> }
>
> 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);
> @@ -4408,7 +4408,7 @@ dpcls_destroy(struct dpcls *cls)
> dpcls_destroy_subtable(cls, subtable);
> }
> cmap_destroy(&cls->subtables_map);
> - pvector_destroy(&cls->subtables);
> + free(cls->subtables);
> }
> }
>
> @@ -4423,8 +4423,7 @@ 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_insert(&cls->subtables, subtable, 0);
> - pvector_publish(&cls->subtables);
> + pvector_push_back(&cls->subtables, subtable, 0);
>
> return subtable;
> }
> @@ -4467,7 +4466,6 @@ 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);
> }
> }
>
> @@ -4521,7 +4519,7 @@ dpcls_lookup(const struct dpcls *cls, const struct
> netdev_flow_key keys[],
> }
> memset(rules, 0, cnt * sizeof *rules);
>
> - 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 aaeee92..5fb1899 100644
> --- a/lib/pvector.c
> +++ b/lib/pvector.c
> @@ -21,60 +21,30 @@
> * reallocations. */
> enum { PVECTOR_EXTRA_ALLOC = 4 };
>
> -static struct pvector_impl *
> -pvector_impl_get(const struct pvector *pvec)
> +struct pvector *
> +pvector_alloc(size_t size)
> {
> - return ovsrcu_get(struct pvector_impl *, &pvec->impl);
> -}
> -
> -static struct pvector_impl *
> -pvector_impl_alloc(size_t size)
> -{
> - struct pvector_impl *impl;
> + struct pvector *pvec;
>
> - impl = xmalloc(sizeof *impl + size * sizeof impl->vector[0]);
> - impl->size = 0;
> - impl->allocated = size;
> + pvec = xmalloc(sizeof *pvec + size * sizeof pvec->vector[0]);
> + pvec->size = 0;
> + pvec->allocated = size;
>
> - 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;
> + return pvec;
> }
>
> -/* Initializes 'pvec' as an empty concurrent priority vector. */ -void -
> pvector_init(struct pvector *pvec)
> +static struct pvector *
> +pvector_dup(const struct pvector *old)
> {
> - ovsrcu_set(&pvec->impl, pvector_impl_alloc(PVECTOR_EXTRA_ALLOC));
> - pvec->temp = NULL;
> -}
> + struct pvector *pvec = pvector_alloc(old->size +
> + PVECTOR_EXTRA_ALLOC);
>
> -/* 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. */
> + pvec->size = old->size;
> + memcpy(pvec->vector, old->vector, old->size * sizeof old->vector[0]);
> + return pvec;
> }
>
> -/* Iterators for callers that need the 'index' afterward. */
> -#define PVECTOR_IMPL_FOR_EACH(ENTRY, INDEX, IMPL) \
> +/* Iterator for callers that need the 'index' afterward. */
> +#define PVECTOR_FOR_EACH_ENTRY(ENTRY, INDEX, IMPL) \
> for ((INDEX) = 0; \
> (INDEX) < (IMPL)->size \
> && ((ENTRY) = &(IMPL)->vector[INDEX], true); \ @@ -91,20 +61,20
> @@ pvector_entry_cmp(const void *a_, const void *b_)
> return a > b ? -1 : a < b;
> }
>
> -static void
> -pvector_impl_sort(struct pvector_impl *impl)
> +void
> +pvector_sort(struct pvector *pvec)
> {
> - qsort(impl->vector, impl->size, sizeof *impl->vector, pvector_entry_cmp);
> + qsort(pvec->vector, pvec->size, sizeof *pvec->vector,
> + pvector_entry_cmp);
> }
>
> /* 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_find(const struct pvector *pvec, void *target)
> {
> const struct pvector_entry *entry;
> int index;
>
> - PVECTOR_IMPL_FOR_EACH (entry, index, impl) {
> + PVECTOR_FOR_EACH_ENTRY (entry, index, pvec) {
> if (entry->ptr == target) {
> return index;
> }
> @@ -112,11 +82,67 @@ pvector_impl_find(struct pvector_impl *impl, 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_insert(struct pvector *pvec, void *ptr, int priority)
> +pvector_remove(struct pvector *pvec, void *ptr)
> {
> - struct pvector_impl *temp = pvec->temp;
> - struct pvector_impl *old = pvector_impl_get(pvec);
> + 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);
>
> ovs_assert(ptr != NULL);
>
> @@ -131,53 +157,37 @@ pvector_insert(struct pvector *pvec, void *ptr, int
> priority)
> ++old->size;
> } else {
> 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;
> + cpvec->temp = pvector_dup(old);
> }
> - /* Insert at the end, publish will sort. */
> - temp->vector[temp->size].ptr = ptr;
> - temp->vector[temp->size].priority = priority;
> - temp->size += 1;
> + pvector_push_back(&cpvec->temp, ptr, priority);
> }
> }
>
> void
> -pvector_remove(struct pvector *pvec, void *ptr)
> +cpvector_remove(struct cpvector *cpvec, void *ptr)
> {
> - struct pvector_impl *temp = pvec->temp;
> - int index;
> + struct pvector *temp = cpvec->temp;
>
> if (!temp) {
> - temp = pvector_impl_dup(pvector_impl_get(pvec));
> - pvec->temp = temp;
> + temp = pvector_dup(cpvector_get_pvector(cpvec));
> + cpvec->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.
> - * Swap another entry in if needed, publish will sort anyway. */
> - temp->size--;
> - if (index != temp->size) {
> - temp->vector[index] = temp->vector[temp->size];
> - }
> + pvector_remove(temp, ptr); /* Publish will sort. */
> }
>
> /* Change entry's 'priority' and keep the vector ordered. */ void -
> pvector_change_priority(struct pvector *pvec, void *ptr, int priority)
> +cpvector_change_priority(struct cpvector *cpvec, void *ptr, int
> +priority)
> {
> - struct pvector_impl *old = pvec->temp;
> + struct pvector *old = cpvec->temp;
> int index;
>
> if (!old) {
> - old = pvector_impl_get(pvec);
> + old = cpvector_get_pvector(cpvec);
> }
>
> - index = pvector_impl_find(old, ptr);
> + index = pvector_find(old, ptr);
>
> ovs_assert(index >= 0);
> /* Now at the index of the entry to be updated. */ @@ -188,10 +198,10 @@
> pvector_change_priority(struct pvector *pvec, 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 (!pvec->temp) {
> + if (!cpvec->temp) {
> /* Have to reallocate to reorder. */
> - pvec->temp = pvector_impl_dup(old);
> - old = pvec->temp;
> + cpvec->temp = pvector_dup(old);
> + old = cpvec->temp;
> /* Publish will sort. */
> }
> }
> @@ -199,13 +209,13 @@ pvector_change_priority(struct pvector *pvec, void
> *ptr, int priority) }
>
> /* Make the modified pvector available for iteration. */ -void
> pvector_publish__(struct pvector *pvec)
> +void cpvector_publish__(struct cpvector *cpvec)
> {
> - struct pvector_impl *temp = pvec->temp;
> + struct pvector *temp = cpvec->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);
> + cpvec->temp = NULL;
> + pvector_sort(temp); /* Also removes gaps. */
> + ovsrcu_postpone(free, ovsrcu_get_protected(struct pvector *,
> + &cpvec->impl));
> + ovsrcu_set(&cpvec->impl, temp);
> }
> diff --git a/lib/pvector.h b/lib/pvector.h index b175b21..00cb757 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 pvector_publish(). This saves
> + * they can be published at 'impl' by calling cpvector_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,33 +61,17 @@ struct pvector_entry {
> void *ptr;
> };
>
> -struct pvector_impl {
> +/* Non-concurrent priority vector. */
> +struct pvector {
> size_t size; /* Number of entries in the vector. */
> size_t allocated; /* Number of allocated entries. */
> struct pvector_entry vector[];
> };
>
> -/* 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 *);
> +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 *);
>
> /* Iteration.
> *
> @@ -95,8 +79,9 @@ static inline bool pvector_is_empty(const struct pvector
> *);
> * Thread-safety
> * =============
> *
> - * Iteration is safe even in a pvector that is changing concurrently.
> - * Multiple writers must exclude each other via e.g., a mutex.
> + * 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.
> *
> * Example
> * =======
> @@ -106,32 +91,28 @@ static inline bool pvector_is_empty(const struct
> pvector *);
> * };
> *
> * struct my_node elem1, elem2, *iter;
> - * struct pvector my_pvector;
> + * struct pvector *my_pvector;
> *
> - * pvector_init(&my_pvector);
> + * my_pvector = pvector_alloc(0);
> * ...add data...
> - * pvector_insert(&my_pvector, &elem1, 1);
> - * pvector_insert(&my_pvector, &elem2, 2);
> + * pvector_push_back(&my_pvector, &elem1, 1);
> + * pvector_push_back(&my_pvector, &elem2, 2);
> + * ...sort...
> + * pvector_sort(my_pvector);
> * ...
> - * PVECTOR_FOR_EACH (iter, &my_pvector) {
> + * PVECTOR_FOR_EACH (iter, &my_cpvector) {
> * ...operate on '*iter'...
> * ...elem2 to be seen before elem1...
> * }
> + * ...remove entries...
> + * pvector_remove(my_pvector, &elem1);
> * ...
> - * pvector_destroy(&my_pvector);
> + * free(my_pvector);
> *
> - * 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.
> + * Currently there is no PVECTOR_FOR_EACH_SAFE variant.
> *
> * 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. */
> @@ -143,7 +124,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 lowest_priority,
> + int stop_at_priority,
> size_t n_ahead, size_t obj_size); static inline void
> pvector_cursor_lookahead(const struct pvector_cursor *,
> int n, size_t size); @@ -158,29 +139,109 @@ 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;
>
> - impl = ovsrcu_get(struct pvector_impl *, &pvec->impl);
> + ovs_prefetch_range(pvec->vector, pvec->size * sizeof
> + pvec->vector[0]);
>
> - ovs_prefetch_range(impl->vector, impl->size * sizeof impl->vector[0]);
> -
> - cursor.size = impl->size;
> - cursor.vector = impl->vector;
> + cursor.size = pvec->size;
> + cursor.vector = pvec->vector;
> cursor.entry_idx = -1;
>
> for (size_t i = 0; i < n_ahead; i++) { @@ -212,23 +273,29 @@ static inline
> void pvector_cursor_lookahead(const struct pvector_cursor *cursor,
> }
> }
>
> -static inline size_t pvector_count(const struct pvector *pvec)
> +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)
> {
> - return ovsrcu_get(struct pvector_impl *, &pvec->impl)->size;
> + return cpvector_get_pvector(cpvec)->size;
> }
>
> -static inline bool pvector_is_empty(const struct pvector *pvec)
> +static inline bool cpvector_is_empty(const struct cpvector *cpvec)
> {
> - return pvector_count(pvec) == 0;
> + return cpvector_count(cpvec) == 0;
> }
>
> -void pvector_publish__(struct pvector *);
> +void cpvector_publish__(struct cpvector *);
>
> -/* Make the modified pvector available for iteration. */ -static inline void
> pvector_publish(struct pvector *pvec)
> +/* Make the modified cpvector available for iteration. */ static inline
> +void cpvector_publish(struct cpvector *cpvec)
> {
> - if (pvec->temp) {
> - pvector_publish__(pvec);
> + if (cpvec->temp) {
> + cpvector_publish__(cpvec);
> }
> }
>
> diff --git a/tests/test-classifier.c b/tests/test-classifier.c index c74c440..3ec2269
> 100644
> --- a/tests/test-classifier.c
> +++ b/tests/test-classifier.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
> + * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 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
> -pvector_verify(const struct pvector *pvec)
> +cpvector_verify(const struct cpvector *cpvec)
> {
> void *ptr OVS_UNUSED;
> int prev_priority = INT_MAX;
>
> - PVECTOR_FOR_EACH (ptr, pvec) {
> + CPVECTOR_FOR_EACH (ptr, cpvec) {
> 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;
>
> - pvector_verify(&cls->subtables);
> + cpvector_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'. */
> - PVECTOR_FOR_EACH (iter, &cls->subtables) {
> + CPVECTOR_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 == pvector_count(&cls->subtables));
> + assert(found_tables == cpvector_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 at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
More information about the dev
mailing list