This patch allows classifier rules to become visible and invisible in
specific versions. A 'version' is defined as a positive monotonically
increasing integer, which never wraps around.
The new 'visibility' attribute replaces the prior 'to_be_removed' and
'visible' attributes.
When versioning is not used, the 'version' parameter should be passed
as 'CLS_NO_VERSION'.
This feature enables the support for atomic OpenFlow bundles without
significant performance penalty on 64-bit systems. There is a
performance decrease in 32-bit systems due to 64-bit atomics used.
Signed-off-by: Jarno Rajahalme <jrajaha...@nicira.com>
---
lib/classifier-private.h | 52 +++++++++++++-
lib/classifier.c | 179 ++++++++++++++++++++++++++++++----------------
lib/classifier.h | 112 ++++++++++++++++++-----------
lib/ovs-router.c | 2 +-
lib/tnl-ports.c | 9 +--
ofproto/ofproto-dpif.c | 2 +-
ofproto/ofproto.c | 46 +++++-------
tests/test-classifier.c | 13 ++--
utilities/ovs-ofctl.c | 1 -
9 files changed, 272 insertions(+), 144 deletions(-)
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index a7edbe9..51cb8cc 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -79,13 +79,63 @@ struct cls_match {
* 'indices'. */
/* Accessed by all readers. */
struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
- bool visible;
+
+ /* Controls rule's visibility to lookups.
+ *
+ * When 'visibility' is:
+ *
+ * > 0 - rule is visible starting from version 'visibility'
+ * <= 0 - rule is visible upto version '-visibility'
+ *
+ * The minimum version number used in lookups is 1 (== CLS_NO_VERSION),
+ * which implies that when 'visibility' is:
+ *
+ * 1 - rule is visible in all lookup versions
+ * 0 - rule is invisible in all lookup versions. */
+ atomic_llong visibility;
+
const struct cls_rule *cls_rule;
OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
/* 'flow' must be the last field. */
};
+static inline void
+cls_match_set_visibility(struct cls_match *rule, long long version)
+{
+ atomic_store_relaxed(&rule->visibility, version);
+}
+
+static inline bool
+cls_match_visible_in_version(const struct cls_match *rule, long long version)
+{
+ long long visibility;
+
+ /* clang does not want to read from a const atomic. */
+ atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
+ &visibility);
+
+ if (OVS_LIKELY(visibility > 0)) {
+ /* Rule is visible starting from version 'visibility'. */
+ return version >= visibility;
+ } else {
+ /* Rule is visible upto version '-visibility'. */
+ return version <= -visibility;
+ }
+}
+
+static inline bool
+cls_match_is_to_be_removed(const struct cls_match *rule)
+{
+ long long visibility;
+
+ /* clang does not want to read from a const atomic. */
+ atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility,
+ &visibility);
+
+ return visibility <= 0;
+}
+
/* A longest-prefix match tree. */
struct trie_node {
uint32_t prefix; /* Prefix bits for this node, MSB first. */
diff --git a/lib/classifier.c b/lib/classifier.c
index 6075cf7..6e657a6 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -99,7 +99,7 @@ cls_match_alloc(const struct cls_rule *rule,
rculist_init(&cls_match->list);
*CONST_CAST(const struct cls_rule **, &cls_match->cls_rule) = rule;
*CONST_CAST(int *, &cls_match->priority) = rule->priority;
- cls_match->visible = false;
+ atomic_init(&cls_match->visibility, 0); /* By default INvisibile. */
miniflow_clone_inline(CONST_CAST(struct miniflow *, &cls_match->flow),
&rule->match.flow, count);
ovsrcu_set_hidden(&cls_match->conj_set,
@@ -115,6 +115,7 @@ static struct cls_subtable *insert_subtable(struct
classifier *cls,
static void destroy_subtable(struct classifier *cls, struct cls_subtable *);
static const struct cls_match *find_match_wc(const struct cls_subtable *,
+ long long version,
const struct flow *,
struct trie_ctx *,
unsigned int n_tries,
@@ -139,12 +140,12 @@ next_rule_in_list(const struct cls_match *rule, const
struct cls_match *head)
/* Return the next lower-priority rule in the list that is visible. Multiple
* identical rules with the same priority may exist transitionally. In that
- * case the first rule of a given priority has been marked as 'to_be_removed',
- * and the later rules are marked as '!visible'. This gets a bit complex if
- * there are two rules of the same priority in the list, as in that case the
- * head and tail of the list will have the same priority. */
+ * case the first rule of a given priority has been marked as visible in one
+ * version and the later rules are marked as visible on the other version.
+ * This makes it possible to for the head and tail of the list have the same
+ * priority. */
static inline const struct cls_match *
-next_visible_rule_in_list(const struct cls_match *rule)
+next_visible_rule_in_list(const struct cls_match *rule, long long version)
{
const struct cls_match *next = rule;
@@ -154,7 +155,7 @@ next_visible_rule_in_list(const struct cls_match *rule)
/* We have reached the head of the list, stop. */
return NULL;
}
- } while (!next->visible);
+ } while (!cls_match_visible_in_version(next, version));
return next;
}
@@ -210,7 +211,6 @@ cls_rule_init__(struct cls_rule *rule, unsigned int
priority)
{
rculist_init(&rule->node);
rule->priority = priority;
- rule->to_be_removed = false;
rule->cls_match = NULL;
}
@@ -249,13 +249,13 @@ cls_rule_clone(struct cls_rule *dst, const struct
cls_rule *src)
}
/* Initializes 'dst' with the data in 'src', destroying 'src'.
+ *
* 'src' must be a cls_rule NOT in a classifier.
*
* The caller must eventually destroy 'dst' with cls_rule_destroy(). */
void
cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
{
- ovs_assert(!src->cls_match); /* Must not be in a classifier. */
cls_rule_init__(dst, src->priority);
minimatch_move(&dst->match, &src->match);
}
@@ -327,15 +327,57 @@ cls_rule_is_catchall(const struct cls_rule *rule)
return minimask_is_catchall(&rule->match.mask);
}
-/* Rules inserted during classifier_defer() need to be made visible before
- * calling classifier_publish().
+/* Prepare a rule for removal. This makes a rule invisible after
+ * 'version'. Once that version is made invisible (by changing the version
+ * parameter used in lookups), the rule should be actually removed via
+ * ovsrcu_postpone().
+ *
+ * 'rule_' must be in a classifier. */
+void
+cls_rule_make_removable_after_version(const struct cls_rule *rule_,
+ long long version)
+{
+ struct cls_match *rule = rule_->cls_match;
+
+ ovs_assert(version > 0);
+
+ /* Normally, we call this when deleting a rule that is already visible.
+ * However, sometimes a bundle transaction will add a rule and then delete
+ * it before the rule has ever become visible. If we set such a rule to
+ * become invisible in a future 'version', it would become visible to all
+ * prior versions. So, in this case we must set the rule visibility to 0
+ * (== never visible). */
+ if (cls_match_visible_in_version(rule, version)) {
+ /* Make invisible after this version. */
+ atomic_store_relaxed(&rule->visibility, -version);
+ } else {
+ /* Make invisible in all version. */
+ atomic_store_relaxed(&rule->visibility, 0);
+ }
+}
+
+/* This undoes the change made by cls_rule_make_removable_after_version().
+ * Should only be called for rules that have been visible in the current
+ * version.
*
* 'rule' must be in a classifier. */
-void cls_rule_make_visible(const struct cls_rule *rule)
+void
+cls_rule_restore_version(const struct cls_rule *rule,
+ long long original_version)
{
- rule->cls_match->visible = true;
+ ovs_assert(original_version > 0);
+
+ atomic_store_relaxed(&rule->cls_match->visibility, original_version);
}
+/* Return true if the rule has been marked for removal in any version.
+ *
+ * 'rule' must be in a classifier. */
+bool
+cls_rule_is_to_be_removed(const struct cls_rule *rule)
+{
+ return cls_match_is_to_be_removed(rule->cls_match);
+}
/* Initializes 'cls' as a classifier that initially contains no classification
* rules. */
@@ -579,23 +621,10 @@ subtable_replace_head_rule(struct classifier *cls
OVS_UNUSED,
cmap_replace(&subtable->rules, &head->cmap_node, &new->cmap_node, hash);
}
-/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
- * must not modify or free it.
- *
- * If 'cls' already contains an identical rule (including wildcards, values of
- * fixed fields, and priority), replaces the old rule by 'rule' and returns the
- * rule that was replaced. The caller takes ownership of the returned rule and
- * is thus responsible for destroying it with cls_rule_destroy(), after RCU
- * grace period has passed (see ovsrcu_postpone()).
- *
- * Returns NULL if 'cls' does not contain a rule with an identical key, after
- * inserting the new rule. In this case, no rules are displaced by the new
- * rule, even rules that cannot have any effect because the new rule matches a
- * superset of their flows and has higher priority.
- */
-const struct cls_rule *
-classifier_replace(struct classifier *cls, const struct cls_rule *rule,
- const struct cls_conjunction *conjs, size_t n_conjs)
+static const struct cls_rule *
+classifier_replace__(struct classifier *cls, long long version,
+ const struct cls_rule *rule,
+ const struct cls_conjunction *conjs, size_t n_conjs)
{
struct cls_match *new = cls_match_alloc(rule, conjs, n_conjs);
struct cls_subtable *subtable;
@@ -607,6 +636,8 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
uint32_t hash;
int i;
+ ovs_assert(version > 0);
+
CONST_CAST(struct cls_rule *, rule)->cls_match = new;
subtable = find_subtable(cls, &rule->match.mask);
@@ -678,7 +709,7 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
FOR_EACH_RULE_IN_LIST_PROTECTED (iter, head) {
if (rule->priority > iter->priority
|| (rule->priority == iter->priority
- && !iter->cls_rule->to_be_removed)) {
+ && !cls_match_is_to_be_removed(iter))) {
break;
}
}
@@ -716,8 +747,8 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
/* No change in subtable's max priority or max count. */
- /* Make rule visible to lookups? */
- new->visible = cls->publish;
+ /* When to make rule visible to lookups? */
+ cls_match_set_visibility(new, version);
/* Make rule visible to iterators (immediately). */
rculist_replace(CONST_CAST(struct rculist *, &rule->node),
@@ -732,8 +763,8 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
}
}
- /* Make rule visible to lookups? */
- new->visible = cls->publish;
+ /* When to make rule visible to lookups? */
+ cls_match_set_visibility(new, version);
/* Make rule visible to iterators (immediately). */
rculist_push_back(&subtable->rules_list,
@@ -770,15 +801,39 @@ classifier_replace(struct classifier *cls, const struct
cls_rule *rule,
/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
* must not modify or free it.
*
+ * If 'cls' already contains an identical rule (including wildcards, values of
+ * fixed fields, and priority), replaces the old rule by 'rule' and returns the
+ * rule that was replaced. The caller takes ownership of the returned rule and
+ * is thus responsible for destroying it with cls_rule_destroy(), after RCU
+ * grace period has passed (see ovsrcu_postpone()).
+ *
+ * Returns NULL if 'cls' does not contain a rule with an identical key, after
+ * inserting the new rule. In this case, no rules are displaced by the new
+ * rule, even rules that cannot have any effect because the new rule matches a
+ * superset of their flows and has higher priority.
+ */
+const struct cls_rule *
+classifier_replace(struct classifier *cls, const struct cls_rule *rule,
+ const struct cls_conjunction *conjs, size_t n_conjs)
+{
+ /* Replacement rule becomes visible immediately. */
+ return classifier_replace__(cls, CLS_NO_VERSION, rule, conjs, n_conjs);
+}
+
+/* Inserts 'rule' into 'cls'. Until 'rule' is removed from 'cls', the caller
+ * must not modify or free it. The rule becomes visible to lookups in
+ * 'version'.
+ *
* 'cls' must not contain an identical rule (including wildcards, values of
* fixed fields, and priority). Use classifier_find_rule_exactly() to find
* such a rule. */
void
-classifier_insert(struct classifier *cls, const struct cls_rule *rule,
+classifier_insert(struct classifier *cls, long long version,
+ const struct cls_rule *rule,
const struct cls_conjunction conj[], size_t n_conj)
{
const struct cls_rule *displaced_rule
- = classifier_replace(cls, rule, conj, n_conj);
+ = classifier_replace__(cls, version, rule, conj, n_conj);
ovs_assert(!displaced_rule);
}
@@ -1026,8 +1081,9 @@ free_conjunctive_matches(struct hmap *matches,
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
static const struct cls_rule *
-classifier_lookup__(const struct classifier *cls, struct flow *flow,
- struct flow_wildcards *wc, bool allow_conjunctive_matches)
+classifier_lookup__(const struct classifier *cls, long long version,
+ struct flow *flow, struct flow_wildcards *wc,
+ bool allow_conjunctive_matches)
{
const struct cls_partition *partition;
struct trie_ctx trie_ctx[CLS_MAX_TRIES];
@@ -1094,7 +1150,8 @@ classifier_lookup__(const struct classifier *cls, struct
flow *flow,
/* Skip subtables with no match, or where the match is lower-priority
* than some certain match we've already found. */
- match = find_match_wc(subtable, flow, trie_ctx, cls->n_tries, wc);
+ match = find_match_wc(subtable, version, flow, trie_ctx, cls->n_tries,
+ wc);
if (!match || match->priority <= hard_pri) {
continue;
}
@@ -1218,7 +1275,7 @@ classifier_lookup__(const struct classifier *cls, struct
flow *flow,
const struct cls_rule *rule;
flow->conj_id = id;
- rule = classifier_lookup__(cls, flow, wc, false);
+ rule = classifier_lookup__(cls, version, flow, wc, false);
flow->conj_id = saved_conj_id;
if (rule) {
@@ -1246,7 +1303,7 @@ classifier_lookup__(const struct classifier *cls, struct
flow *flow,
}
/* Find next-lower-priority flow with identical flow match. */
- match = next_visible_rule_in_list(soft[i]->match);
+ match = next_visible_rule_in_list(soft[i]->match, version);
if (match) {
soft[i] = ovsrcu_get(struct cls_conjunction_set *,
&match->conj_set);
@@ -1271,9 +1328,10 @@ classifier_lookup__(const struct classifier *cls, struct
flow *flow,
return hard ? hard->cls_rule : NULL;
}
-/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
- * Returns a null pointer if no rules in 'cls' match 'flow'. If multiple rules
- * of equal priority match 'flow', returns one arbitrarily.
+/* Finds and returns the highest-priority rule in 'cls' that matches 'flow' and
+ * that is visible in 'version'. Returns a null pointer if no rules in 'cls'
+ * match 'flow'. If multiple rules of equal priority match 'flow', returns one
+ * arbitrarily.
*
* If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
* set of bits that were significant in the lookup. At some point
@@ -1283,10 +1341,10 @@ classifier_lookup__(const struct classifier *cls,
struct flow *flow,
* 'flow' is non-const to allow for temporary modifications during the lookup.
* Any changes are restored before returning. */
const struct cls_rule *
-classifier_lookup(const struct classifier *cls, struct flow *flow,
- struct flow_wildcards *wc)
+classifier_lookup(const struct classifier *cls, long long version,
+ struct flow *flow, struct flow_wildcards *wc)
{
- return classifier_lookup__(cls, flow, wc, true);
+ return classifier_lookup__(cls, version, flow, wc, true);
}
/* Finds and returns a rule in 'cls' with exactly the same priority and
@@ -1318,7 +1376,7 @@ classifier_find_rule_exactly(const struct classifier *cls,
break; /* Not found. */
}
if (rule->priority == target->priority
- && !rule->cls_rule->to_be_removed) {
+ && !cls_match_is_to_be_removed(rule)) {
return rule->cls_rule;
}
}
@@ -1371,7 +1429,7 @@ classifier_rule_overlaps(const struct classifier *cls,
RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
if (rule->priority == target->priority
- && !rule->to_be_removed
+ && !cls_rule_is_to_be_removed(rule)
&& miniflow_equal_in_minimask(&target->match.flow,
&rule->match.flow, &mask)) {
return true;
@@ -1430,7 +1488,7 @@ rule_matches(const struct cls_rule *rule, const struct
cls_rule *target)
{
/* Iterators never see rules that have been marked for removal.
* This allows them to be oblivious of duplicate rules. */
- return (!rule->to_be_removed &&
+ return (!cls_rule_is_to_be_removed(rule) &&
(!target
|| miniflow_equal_in_minimask(&rule->match.flow,
&target->match.flow,
@@ -1722,8 +1780,8 @@ miniflow_and_mask_matches_flow(const struct miniflow
*flow,
}
static inline const struct cls_match *
-find_match(const struct cls_subtable *subtable, const struct flow *flow,
- uint32_t hash)
+find_match(const struct cls_subtable *subtable, long long version,
+ const struct flow *flow, uint32_t hash)
{
const struct cls_match *head, *rule;
@@ -1733,7 +1791,7 @@ find_match(const struct cls_subtable *subtable, const
struct flow *flow,
flow))) {
/* Return highest priority rule that is visible. */
FOR_EACH_RULE_IN_LIST(rule, head) {
- if (OVS_LIKELY(rule->visible)) {
+ if (OVS_LIKELY(cls_match_visible_in_version(rule, version))) {
return rule;
}
}
@@ -1791,9 +1849,9 @@ fill_range_wc(const struct cls_subtable *subtable, struct
flow_wildcards *wc,
}
static const struct cls_match *
-find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
- struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
- struct flow_wildcards *wc)
+find_match_wc(const struct cls_subtable *subtable, long long version,
+ const struct flow *flow, struct trie_ctx trie_ctx[CLS_MAX_TRIES],
+ unsigned int n_tries, struct flow_wildcards *wc)
{
uint32_t basis = 0, hash;
const struct cls_match *rule = NULL;
@@ -1801,7 +1859,7 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
struct range ofs;
if (OVS_UNLIKELY(!wc)) {
- return find_match(subtable, flow,
+ return find_match(subtable, version, flow,
flow_hash_in_minimask(flow, &subtable->mask, 0));
}
@@ -1842,7 +1900,8 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
flow, wc)) {
/* Return highest priority rule that is visible. */
FOR_EACH_RULE_IN_LIST(rule, head) {
- if (OVS_LIKELY(rule->visible)) {
+ if (OVS_LIKELY(cls_match_visible_in_version(rule,
+ version))) {
return rule;
}
}
@@ -1859,7 +1918,7 @@ find_match_wc(const struct cls_subtable *subtable, const
struct flow *flow,
}
hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
ofs.end, &basis);
- rule = find_match(subtable, flow, hash);
+ rule = find_match(subtable, version, flow, hash);
if (!rule && subtable->ports_mask_len) {
/* Ports are always part of the final range, if any.
* No match was found for the ports. Use the ports trie to figure out
diff --git a/lib/classifier.h b/lib/classifier.h
index d69c201..2798752 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -210,39 +210,72 @@
* Each eliminated subtable lookup also reduces the amount of un-wildcarding.
*
*
- * Tentative Modifications
- * =======================
- *
- * When a new rule is added to a classifier, it can optionally be "invisible".
- * That means that lookups won't find the rule, although iterations through
- * the classifier will see it.
- *
- * Similarly, deletions from a classifier can be "tentative", by setting
- * 'to_be_removed' to true within the rule. A rule that is tentatively deleted
- * will not appear in iterations, although it will still be found by lookups.
+ * Classifier Versioning
+ * =====================
+ *
+ * Classifier lookups are always done in a specific classifier version, where
+ * a version is defined to be a natural number.
+ *
+ * When a new rule is added to a classifier, it is set to become visible in a
+ * specific version. If the version number used at insert time is larger than
+ * any version number currently used in lookups, the new rule is said to be
+ * invisible to lookups. This means that lookups won't find the rule, but the
+ * rule is immediately available to classifier iterations.
+ *
+ * Similarly, a rule can be marked as to be deleted in a future version, or
+ * more precisely, to be visible upto a given version number. To delete a rule
+ * in a way to not remove the rule before all ongoing lookups are finished, the
+ * rule should be marked as "to be deleted" by setting the rule's visibility to
+ * the negation of the last version number in which it should be visible.
+ * Then, when all the lookups use that future version number, the rule can be
+ * actually deleted from the classifier. A rule that is marked for deletion in
+ * a future version will not appear in iterations, although it will still be
+ * found by lookups using an earlier lookup version number.
*
* Classifiers can hold duplicate rules (rules with the same match criteria and
- * priority) when tentative modifications are involved: one (or more) identical
- * tentatively deleted rules can coexist in a classifier with at most one
- * identical invisible rule.
- *
- * The classifier supports tentative modifications for two reasons:
- *
- * 1. Performance: Adding (or deleting) a rule can, in pathological cases,
- * have a cost proportional to the number of rules already in the
- * classifier. When multiple rules are being added (or deleted) in one
- * go, though, this cost can be paid just once, not once per addition
- * (or deletion), as long as it is OK for any new rules to be invisible
- * until the batch change is complete.
- *
- * 2. Staging additions and deletions: Invisibility allows a rule to be
- * added tentatively, to possibly be modified or removed before it
- * becomes visible. Tentatively deletion allows a rule to be scheduled
- * for deletion before it is certain that the deletion is desirable.
+ * priority) when at most one of the duplicates is visible in any given lookup
+ * version. The caller responsible for classifier modifications must maintain
+ * this invariant.
+ *
+ * The classifier supports versioning for two reasons:
+ *
+ * 1. Support for versioned modifications makes it possible to support
+ * an arbitraty series of classifier changes as one atomic transaction,
+ * where intermediate versions of the classifier are not visible to any
+ * lookups. Also, when a rule is added for a future version, or marked
+ * for removal in a future version, such modifications can be reverted
+ * without any visible effects to any of the current lookup versions.
+ *
+ * 2. Performance: Adding (or deleting) a large set of rules can, in
+ * pathological cases, have a cost proportional to the number of rules
+ * already in the classifier. When multiple rules are being added (or
+ * deleted) in one go, though, this pathological case cost can be
+ * typically avoided, as long as it is OK for any new rules to be
+ * invisible until the batch change is complete.
+ *
+ *
+ * Deferred Publication
+ * ====================
+ *
+ * Removing large number of rules from classifier can be costly, as the
+ * supporting data structures are teared down, just to be re-instantiated right
+ * after. In the worst case, as when each rule has a different match pattern
+ * (mask), the maintenance of the match pattern can have cost O(N^2), where N
+ * is the number of different match patterns. To alleviate this, the
+ * classifier supports a "deferred mode", in which changes in internal data
+ * structures used for lookups may not be fully computed yet. The computation
+ * is finalized when the deferred mode is turned off.
+ *
+ * This feature can be used with versioning such that all changes to future
+ * versions are made in the deferred mode. Then, right before making the new
+ * version visible to lookups, the deferred mode is turned off so that all the
+ * data structures are ready for lookups.
*
* To use deferred publication, first call classifier_defer(). Then, modify
- * the classifier via additions and deletions. Call cls_rule_make_visible() on
- * each new rule at an appropriate time. Finally, call classifier_publish().
+ * the classifier via additions (classifier_insert() with a specific, future
+ * version number) and deletions (use cls_rule_make_removable_after_version()).
+ * Then call classifier_publish(), and after that, announce the new version
+ * number to be used in lookups.
*
*
* Thread-safety
@@ -275,6 +308,7 @@ struct cls_trie {
};
enum {
+ CLS_NO_VERSION = 1, /* Default version number to use. */
CLS_MAX_INDICES = 3, /* Maximum number of lookup indices per subtable. */
CLS_MAX_TRIES = 3 /* Maximum number of prefix trees per classifier. */
};
@@ -303,13 +337,6 @@ struct cls_conjunction {
struct cls_rule {
struct rculist node; /* In struct cls_subtable 'rules_list'. */
int priority; /* Larger numbers are higher priorities. */
- bool to_be_removed; /* Rule will be deleted.
- * This is the only field that may be
- * modified after the rule has been added to
- * a classifier. Modifications are to be
- * done only under same locking as all other
- * classifier modifications. This field may
- * not be examined by lookups. */
struct cls_match *cls_match; /* NULL if not in a classifier. */
struct minimatch match; /* Matching rule. */
};
@@ -330,7 +357,11 @@ void cls_rule_format(const struct cls_rule *, struct ds *);
bool cls_rule_is_catchall(const struct cls_rule *);
bool cls_rule_is_loose_match(const struct cls_rule *rule,
const struct minimatch *criteria);
-void cls_rule_make_visible(const struct cls_rule *rule);
+void cls_rule_make_removable_after_version(const struct cls_rule *,
+ long long version);
+void cls_rule_restore_version(const struct cls_rule *,
+ long long original_version);
+bool cls_rule_is_to_be_removed(const struct cls_rule *);
/* Constructor/destructor. Must run single-threaded. */
void classifier_init(struct classifier *, const uint8_t *flow_segments);
@@ -340,8 +371,9 @@ void classifier_destroy(struct classifier *);
bool classifier_set_prefix_fields(struct classifier *,
const enum mf_field_id *trie_fields,
unsigned int n_trie_fields);
-void classifier_insert(struct classifier *, const struct cls_rule *,
- const struct cls_conjunction *, size_t n_conjunctions);
+void classifier_insert(struct classifier *, long long version,
+ const struct cls_rule *, const struct cls_conjunction *,
+ size_t n_conjunctions);
const struct cls_rule *classifier_replace(struct classifier *,
const struct cls_rule *,
const struct cls_conjunction *,
@@ -354,7 +386,7 @@ static inline void classifier_publish(struct classifier *);
/* Lookups. These are RCU protected and may run concurrently with modifiers
* and each other. */
const struct cls_rule *classifier_lookup(const struct classifier *,
- struct flow *,
+ long long version, struct flow *,
struct flow_wildcards *);
bool classifier_rule_overlaps(const struct classifier *,
const struct cls_rule *);
diff --git a/lib/ovs-router.c b/lib/ovs-router.c
index bf205d6..35749b1 100644
--- a/lib/ovs-router.c
+++ b/lib/ovs-router.c
@@ -68,7 +68,7 @@ ovs_router_lookup(ovs_be32 ip_dst, char output_bridge[],
ovs_be32 *gw)
const struct cls_rule *cr;
struct flow flow = {.nw_dst = ip_dst};
- cr = classifier_lookup(&cls, &flow, NULL);
+ cr = classifier_lookup(&cls, CLS_NO_VERSION, &flow, NULL);
if (cr) {
struct ovs_router_entry *p = ovs_router_entry_cast(cr);
diff --git a/lib/tnl-ports.c b/lib/tnl-ports.c
index 759d6ba..6d2859c 100644
--- a/lib/tnl-ports.c
+++ b/lib/tnl-ports.c
@@ -84,7 +84,7 @@ tnl_port_map_insert(odp_port_t port, ovs_be32 ip_dst,
ovs_be16 udp_port,
ovs_mutex_lock(&mutex);
do {
- cr = classifier_lookup(&cls, &match.flow, NULL);
+ cr = classifier_lookup(&cls, CLS_NO_VERSION, &match.flow, NULL);
p = tnl_port_cast(cr);
/* Try again if the rule was released before we get the reference. */
} while (p && !ovs_refcount_try_ref_rcu(&p->ref_cnt));
@@ -103,7 +103,7 @@ tnl_port_map_insert(odp_port_t port, ovs_be32 ip_dst,
ovs_be16 udp_port,
ovs_refcount_init(&p->ref_cnt);
ovs_strlcpy(p->dev_name, dev_name, sizeof p->dev_name);
- classifier_insert(&cls, &p->cr, NULL, 0);
+ classifier_insert(&cls, CLS_NO_VERSION, &p->cr, NULL, 0);
}
ovs_mutex_unlock(&mutex);
}
@@ -130,7 +130,7 @@ tnl_port_map_delete(ovs_be32 ip_dst, ovs_be16 udp_port)
tnl_port_init_flow(&flow, ip_dst, udp_port);
- cr = classifier_lookup(&cls, &flow, NULL);
+ cr = classifier_lookup(&cls, CLS_NO_VERSION, &flow, NULL);
tnl_port_unref(cr);
}
@@ -139,7 +139,8 @@ tnl_port_map_delete(ovs_be32 ip_dst, ovs_be16 udp_port)
odp_port_t
tnl_port_map_lookup(struct flow *flow, struct flow_wildcards *wc)
{
- const struct cls_rule *cr = classifier_lookup(&cls, flow, wc);
+ const struct cls_rule *cr = classifier_lookup(&cls, CLS_NO_VERSION, flow,
+ wc);
return (cr) ? tnl_port_cast(cr)->portno : ODPP_NONE;
}
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index c1daa1d..83ba003 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -3717,7 +3717,7 @@ rule_dpif_lookup_in_table(struct ofproto_dpif *ofproto,
uint8_t table_id,
struct rule_dpif *rule;
do {
- cls_rule = classifier_lookup(cls, flow, wc);
+ cls_rule = classifier_lookup(cls, CLS_NO_VERSION, flow, wc);
rule = rule_dpif_cast(rule_from_cls_rule(cls_rule));
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 9f43034..e23335d 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -3784,7 +3784,7 @@ rule_collection_destroy(struct rule_collection *rules)
* function verifies most of the criteria in 'c' itself, but the caller must
* check 'c->cr' itself.
*
- * Rules that have already been marked as 'to_be_removed' are not collected.
+ * Rules that have already been marked for removal are not collected.
*
* Increments '*n_readonly' if 'rule' wasn't added because it's read-only (and
* 'c' only includes modifiable rules). */
@@ -3798,7 +3798,7 @@ collect_rule(struct rule *rule, const struct
rule_criteria *c,
&& ofproto_rule_has_out_group(rule, c->out_group)
&& !((rule->flow_cookie ^ c->cookie) & c->cookie_mask)
&& (!rule_is_hidden(rule) || c->include_hidden)
- && !rule->cr.to_be_removed) {
+ && !cls_rule_is_to_be_removed(&rule->cr)) {
/* Rule matches all the criteria... */
if (!rule_is_readonly(rule) || c->include_readonly) {
/* ...add it. */
@@ -4406,7 +4406,7 @@ add_flow_start(struct ofproto *ofproto, struct
ofputil_flow_mod *fm,
cls_rule_init(&cr, &fm->match, fm->priority);
/* Check for the existence of an identical rule.
- * This will not return rules earlier marked as 'to_be_removed'. */
+ * This will not return rules earlier marked for removal. */
rule = rule_from_cls_rule(classifier_find_rule_exactly(&table->cls, &cr));
if (rule) {
/* Transform "add" into "modify" of an existing identical flow. */
@@ -4451,7 +4451,8 @@ add_flow_start(struct ofproto *ofproto, struct
ofputil_flow_mod *fm,
/* Make the new rule invisible for classifier lookups. */
classifier_defer(&table->cls);
get_conjunctions(fm, &conjs, &n_conjs);
- classifier_insert(&table->cls, &rule->cr, conjs, n_conjs);
+ classifier_insert(&table->cls, CLS_NO_VERSION, &rule->cr, conjs,
+ n_conjs);
free(conjs);
error = ofproto->ofproto_class->rule_insert(rule);
@@ -4505,7 +4506,6 @@ add_flow_finish(struct ofproto *ofproto, struct
ofputil_flow_mod *fm,
} else {
struct oftable *table = &ofproto->tables[rule->table_id];
- cls_rule_make_visible(&rule->cr);
classifier_publish(&table->cls);
learned_cookies_inc(ofproto, rule_get_actions(rule));
@@ -4825,11 +4825,12 @@ delete_flows__(const struct rule_collection *rules,
struct ovs_list dead_cookies = OVS_LIST_INITIALIZER(&dead_cookies);
struct ofproto *ofproto = rules->rules[0]->ofproto;
struct rule *rule, *next;
+ uint8_t prev_table = UINT8_MAX;
size_t i;
for (i = 0, next = rules->rules[0];
rule = next, next = (++i < rules->n) ? rules->rules[i] : NULL,
- rule; ) {
+ rule; prev_table = rule->table_id) {
struct classifier *cls = &ofproto->tables[rule->table_id].cls;
uint8_t next_table = next ? next->table_id : UINT8_MAX;
@@ -4839,7 +4840,8 @@ delete_flows__(const struct rule_collection *rules,
req ? req->ofconn : NULL,
req ? req->request->xid : 0, NULL);
- if (next_table == rule->table_id) {
+ /* Defer once for each new table. */
+ if (rule->table_id != prev_table) {
classifier_defer(cls);
}
classifier_remove(cls, &rule->cr);
@@ -4882,7 +4884,9 @@ delete_flows_start_loose(struct ofproto *ofproto,
for (size_t i = 0; i < rules->n; i++) {
struct rule *rule = rules->rules[i];
- CONST_CAST(struct cls_rule *, &rule->cr)->to_be_removed = true;
+ cls_rule_make_removable_after_version(CONST_CAST(struct cls_rule *,
+ &rule->cr),
+ CLS_NO_VERSION);
}
}
@@ -4896,7 +4900,7 @@ delete_flows_revert(struct rule_collection *rules)
for (size_t i = 0; i < rules->n; i++) {
struct rule *rule = rules->rules[i];
- CONST_CAST(struct cls_rule *, &rule->cr)->to_be_removed = false;
+ cls_rule_restore_version(&rule->cr, CLS_NO_VERSION);
}
rule_collection_destroy(rules);
}
@@ -4933,7 +4937,9 @@ delete_flow_start_strict(struct ofproto *ofproto,
for (size_t i = 0; i < rules->n; i++) {
struct rule *rule = rules->rules[i];
- CONST_CAST(struct cls_rule *, &rule->cr)->to_be_removed = true;
+ cls_rule_make_removable_after_version(CONST_CAST(struct cls_rule *,
+ &rule->cr),
+ CLS_NO_VERSION);
}
}
@@ -6515,26 +6521,6 @@ do_bundle_flow_mod_finish(struct ofproto *ofproto,
struct ofputil_flow_mod *fm,
}
}
-/* Commit phases (all while locking ofproto_mutex):
- *
- * 1. Gather resources - do not send any events or notifications.
- *
- * add: Check conflicts, check for a displaced flow. If no displaced flow
- * exists, add the new flow, but mark it as "invisible".
- * mod: Collect affected flows, Do not modify yet.
- * del: Collect affected flows, Do not delete yet.
- *
- * 2a. Fail if any errors are found. After this point no errors are possible.
- * No visible changes were made, so rollback is minimal (remove added invisible
- * flows, revert 'to_be_removed' status of flows).
- *
- * 2b. Commit the changes
- *
- * add: if have displaced flow, modify it, otherwise mark the new flow as
- * "visible".
- * mod: Modify the collected flows.
- * del: Delete the collected flows.
- */
static enum ofperr
do_bundle_commit(struct ofconn *ofconn, uint32_t id, uint16_t flags)
{
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index a615438..28b711a 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -433,7 +433,7 @@ compare_classifiers(struct classifier *cls, struct tcls
*tcls)
/* This assertion is here to suppress a GCC 4.9 array-bounds warning */
ovs_assert(cls->n_tries <= CLS_MAX_TRIES);
- cr0 = classifier_lookup(cls, &flow, &wc);
+ cr0 = classifier_lookup(cls, CLS_NO_VERSION, &flow, &wc);
cr1 = tcls_lookup(tcls, &flow);
assert((cr0 == NULL) == (cr1 == NULL));
if (cr0 != NULL) {
@@ -443,7 +443,7 @@ compare_classifiers(struct classifier *cls, struct tcls
*tcls)
assert(cls_rule_equal(cr0, cr1));
assert(tr0->aux == tr1->aux);
}
- cr2 = classifier_lookup(cls, &flow, NULL);
+ cr2 = classifier_lookup(cls, CLS_NO_VERSION, &flow, NULL);
assert(cr2 == cr0);
}
}
@@ -736,7 +736,7 @@ test_single_rule(struct ovs_cmdl_context *ctx OVS_UNUSED)
tcls_init(&tcls);
tcls_rule = tcls_insert(&tcls, rule);
- classifier_insert(&cls, &rule->cls_rule, NULL, 0);
+ classifier_insert(&cls, CLS_NO_VERSION, &rule->cls_rule, NULL, 0);
compare_classifiers(&cls, &tcls);
check_tables(&cls, 1, 1, 0);
@@ -773,7 +773,7 @@ test_rule_replacement(struct ovs_cmdl_context *ctx
OVS_UNUSED)
set_prefix_fields(&cls);
tcls_init(&tcls);
tcls_insert(&tcls, rule1);
- classifier_insert(&cls, &rule1->cls_rule, NULL, 0);
+ classifier_insert(&cls, CLS_NO_VERSION, &rule1->cls_rule, NULL, 0);
compare_classifiers(&cls, &tcls);
check_tables(&cls, 1, 1, 0);
tcls_destroy(&tcls);
@@ -1002,7 +1002,8 @@ test_many_rules_in_one_table(struct ovs_cmdl_context *ctx
OVS_UNUSED)
rules[i] = make_rule(wcf, priority, value_pats[i]);
tcls_rules[i] = tcls_insert(&tcls, rules[i]);
- classifier_insert(&cls, &rules[i]->cls_rule, NULL, 0);
+ classifier_insert(&cls, CLS_NO_VERSION, &rules[i]->cls_rule, NULL,
+ 0);
compare_classifiers(&cls, &tcls);
check_tables(&cls, 1, i + 1, 0);
@@ -1061,7 +1062,7 @@ test_many_rules_in_n_tables(int n_tables)
int value_pat = random_uint32() & ((1u << CLS_N_FIELDS) - 1);
rule = make_rule(wcf, priority, value_pat);
tcls_insert(&tcls, rule);
- classifier_insert(&cls, &rule->cls_rule, NULL, 0);
+ classifier_insert(&cls, CLS_NO_VERSION, &rule->cls_rule, NULL, 0);
compare_classifiers(&cls, &tcls);
check_tables(&cls, -1, i + 1, -1);
}
diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c
index be0f149..2e2f308 100644
--- a/utilities/ovs-ofctl.c
+++ b/utilities/ovs-ofctl.c
@@ -2483,7 +2483,6 @@ fte_insert(struct classifier *cls, const struct match
*match,
ovsrcu_postpone(fte_free, old);
}
- cls_rule_make_visible(&fte->rule);
}
/* Reads the flows in 'filename' as flow table entries in 'cls' for the version
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
