[ovs-dev] [PATCH v4 2/5] classifier: Lockless and robust classifier iteration.
Jarno Rajahalme
jrajahalme at nicira.com
Thu Nov 13 19:56:14 UTC 2014
Previously, accurate iteration required writers to be excluded during
iteration. This patch adds an rculist to struct cls_subtable, and a
corresponding list node to struct cls_rule, which makes iteration more
straightforward, and allows the iterators to remain ignorant of the
internals of the cls_match. This new list allows iteration of rules
in the classifier by traversing the RCU-friendly subtables vector, and
the rculist of rules in each subtable.
Classifier modifications may be performed concurrently, but whether or
not the concurrent iterator sees those changes depends on the timing
of change. More specifically, an concurrent iterator:
- May or may not see a rule that is being inserted or removed.
- Will see either the new or the old version of a rule that is replaced.
- Will see all the other rules (that are not being modified).
Finally, The subtable's rculist also allows to make
classifier_rule_overlaps() lockless, which this patch also does.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier-private.h | 10 ++--
lib/classifier.c | 137 +++++++++++++++++++++++-----------------------
lib/classifier.h | 48 +++++++---------
lib/flow.c | 4 +-
lib/ovs-router.c | 2 +-
lib/pvector.h | 7 +++
ofproto/ofproto-dpif.c | 2 +-
ofproto/ofproto.c | 2 +-
tests/test-classifier.c | 11 ++--
utilities/ovs-ofctl.c | 10 ++--
10 files changed, 115 insertions(+), 118 deletions(-)
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index 441aaff..4716f2f 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -27,13 +27,15 @@
/* A set of rules that all have the same fields wildcarded. */
struct cls_subtable {
- /* The fields are only used by writers and iterators. */
- struct cmap_node cmap_node; /* Within struct classifier 'subtables_map'. */
-
- /* The fields are only used by writers. */
+ /* These fields are only used by writers. */
+ struct cmap_node cmap_node OVS_GUARDED; /* Within struct classifier's
+ * 'subtables_map'. */
int max_priority OVS_GUARDED; /* Max priority of any rule in subtable. */
unsigned int max_count OVS_GUARDED; /* Count of max_priority rules. */
+ /* Accessed by iterators. */
+ struct rculist rules_list; /* Unordered. */
+
/* Identical, but lower priority rules are not inserted to any of the
* following data structures. */
diff --git a/lib/classifier.c b/lib/classifier.c
index 5b01a69..d4345cd 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -132,6 +132,15 @@ static bool mask_prefix_bits_set(const struct flow_wildcards *,
/* cls_rule. */
+static inline void
+cls_rule_init__(struct cls_rule *rule, unsigned int priority)
+ OVS_NO_THREAD_SAFETY_ANALYSIS
+{
+ rculist_init(&rule->node);
+ rule->priority = priority;
+ rule->cls_match = NULL;
+}
+
/* Initializes 'rule' to match packets specified by 'match' at the given
* 'priority'. 'match' must satisfy the invariant described in the comment at
* the definition of struct match.
@@ -143,9 +152,8 @@ static bool mask_prefix_bits_set(const struct flow_wildcards *,
void
cls_rule_init(struct cls_rule *rule, const struct match *match, int priority)
{
+ cls_rule_init__(rule, priority);
minimatch_init(&rule->match, match);
- rule->priority = priority;
- rule->cls_match = NULL;
}
/* Same as cls_rule_init() for initialization from a "struct minimatch". */
@@ -153,9 +161,8 @@ void
cls_rule_init_from_minimatch(struct cls_rule *rule,
const struct minimatch *match, int priority)
{
+ cls_rule_init__(rule, priority);
minimatch_clone(&rule->match, match);
- rule->priority = priority;
- rule->cls_match = NULL;
}
/* Initializes 'dst' as a copy of 'src'.
@@ -164,20 +171,21 @@ cls_rule_init_from_minimatch(struct cls_rule *rule,
void
cls_rule_clone(struct cls_rule *dst, const struct cls_rule *src)
{
+ cls_rule_init__(dst, src->priority);
minimatch_clone(&dst->match, &src->match);
- dst->priority = src->priority;
- dst->cls_match = NULL;
}
/* 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_NO_THREAD_SAFETY_ANALYSIS
{
+ ovs_assert(!src->cls_match); /* Must not be in a classifier. */
+ cls_rule_init__(dst, src->priority);
minimatch_move(&dst->match, &src->match);
- dst->priority = src->priority;
- dst->cls_match = NULL;
}
/* Frees memory referenced by 'rule'. Doesn't free 'rule' itself (it's
@@ -186,8 +194,16 @@ cls_rule_move(struct cls_rule *dst, struct cls_rule *src)
* ('rule' must not currently be in a classifier.) */
void
cls_rule_destroy(struct cls_rule *rule)
+ OVS_NO_THREAD_SAFETY_ANALYSIS
{
- ovs_assert(!rule->cls_match);
+ ovs_assert(!rule->cls_match); /* Must not be in a classifier. */
+
+ /* Check that the rule has been properly removed from the classifier and
+ * that the destruction only happens after the RCU grace period, or that
+ * the rule was never inserted to the classifier in the first place. */
+ ovs_assert(rculist_next_protected(&rule->node) == RCULIST_POISON
+ || rculist_is_empty(&rule->node));
+
minimatch_destroy(&rule->match);
}
@@ -611,6 +627,9 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
/* No change in subtable's max priority or max count. */
+ /* Make rule visible to iterators. */
+ rculist_replace(&rule->node, &old->node);
+
/* Return displaced rule. Caller is responsible for keeping it
* around until all threads quiesce. */
ovs_mutex_unlock(&cls->mutex);
@@ -618,6 +637,9 @@ classifier_replace(struct classifier *cls, struct cls_rule *rule)
}
}
+ /* Make rule visible to iterators. */
+ rculist_push_back(&subtable->rules_list, &rule->node);
+
/* Rule was added, not replaced. Update 'subtable's 'max_priority' and
* 'max_count', if necessary.
*
@@ -686,6 +708,9 @@ classifier_remove(struct classifier *cls, const struct cls_rule *rule)
/* Mark as removed. */
CONST_CAST(struct cls_rule *, rule)->cls_match = NULL;
+ /* Remove 'rule' from the subtable's rules list. */
+ rculist_remove(&CONST_CAST(struct cls_rule *, rule)->node);
+
INIT_CONTAINER(prev, rculist_back_protected(&cls_match->list), list);
INIT_CONTAINER(next, rculist_next(&cls_match->list), list);
@@ -924,41 +949,35 @@ classifier_find_match_exactly(const struct classifier *cls,
/* Checks if 'target' would overlap any other rule in 'cls'. Two rules are
* considered to overlap if both rules have the same priority and a packet
- * could match both. */
+ * could match both.
+ *
+ * A trivial example of overlapping rules is two rules matching disjoint sets
+ * of fields. E.g., if one rule matches only on port number, while another only
+ * on dl_type, any packet from that specific port and with that specific
+ * dl_type could match both, if the rules also have the same priority. */
bool
classifier_rule_overlaps(const struct classifier *cls,
const struct cls_rule *target)
- OVS_EXCLUDED(cls->mutex)
{
struct cls_subtable *subtable;
- ovs_mutex_lock(&cls->mutex);
/* Iterate subtables in the descending max priority order. */
PVECTOR_FOR_EACH_PRIORITY (subtable, target->priority - 1, 2,
sizeof(struct cls_subtable), &cls->subtables) {
uint32_t storage[FLOW_U32S];
struct minimask mask;
- struct cls_match *head;
+ const struct cls_rule *rule;
minimask_combine(&mask, &target->match.mask, &subtable->mask, storage);
- CMAP_FOR_EACH (head, cmap_node, &subtable->rules) {
- struct cls_match *rule;
- FOR_EACH_RULE_IN_LIST_PROTECTED (rule, head) {
- if (rule->priority < target->priority) {
- break; /* Rules in descending priority order. */
- }
- if (rule->priority == target->priority
- && miniflow_equal_in_minimask(&target->match.flow,
- &rule->flow, &mask)) {
- ovs_mutex_unlock(&cls->mutex);
- return true;
- }
+ RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
+ if (rule->priority == target->priority
+ && miniflow_equal_in_minimask(&target->match.flow,
+ &rule->match.flow, &mask)) {
+ return true;
}
}
}
-
- ovs_mutex_unlock(&cls->mutex);
return false;
}
@@ -1007,24 +1026,23 @@ cls_rule_is_loose_match(const struct cls_rule *rule,
/* Iteration. */
static bool
-rule_matches(const struct cls_match *rule, const struct cls_rule *target)
+rule_matches(const struct cls_rule *rule, const struct cls_rule *target)
{
return (!target
- || miniflow_equal_in_minimask(&rule->flow,
+ || miniflow_equal_in_minimask(&rule->match.flow,
&target->match.flow,
&target->match.mask));
}
-static const struct cls_match *
+static const struct cls_rule *
search_subtable(const struct cls_subtable *subtable,
struct cls_cursor *cursor)
{
if (!cursor->target
|| !minimask_has_extra(&subtable->mask, &cursor->target->match.mask)) {
- const struct cls_match *rule;
+ const struct cls_rule *rule;
- CMAP_CURSOR_FOR_EACH (rule, cmap_node, &cursor->rules,
- &subtable->rules) {
+ RCULIST_FOR_EACH (rule, node, &subtable->rules_list) {
if (rule_matches(rule, cursor->target)) {
return rule;
}
@@ -1043,67 +1061,49 @@ search_subtable(const struct cls_subtable *subtable,
*
* Ignores target->priority. */
struct cls_cursor cls_cursor_start(const struct classifier *cls,
- const struct cls_rule *target,
- bool safe)
- OVS_NO_THREAD_SAFETY_ANALYSIS
+ const struct cls_rule *target)
{
struct cls_cursor cursor;
struct cls_subtable *subtable;
- cursor.safe = safe;
cursor.cls = cls;
cursor.target = target && !cls_rule_is_catchall(target) ? target : NULL;
cursor.rule = NULL;
/* Find first rule. */
- ovs_mutex_lock(&cursor.cls->mutex);
- CMAP_CURSOR_FOR_EACH (subtable, cmap_node, &cursor.subtables,
- &cursor.cls->subtables_map) {
- const struct cls_match *rule = search_subtable(subtable, &cursor);
+ PVECTOR_CURSOR_FOR_EACH (subtable, &cursor.subtables,
+ &cursor.cls->subtables) {
+ const struct cls_rule *rule = search_subtable(subtable, &cursor);
if (rule) {
cursor.subtable = subtable;
- cursor.rule = rule->cls_rule;
+ cursor.rule = rule;
break;
}
}
- /* Leave locked if requested and have a rule. */
- if (safe || !cursor.rule) {
- ovs_mutex_unlock(&cursor.cls->mutex);
- }
return cursor;
}
static const struct cls_rule *
cls_cursor_next(struct cls_cursor *cursor)
- OVS_NO_THREAD_SAFETY_ANALYSIS
{
- const struct cls_match *rule = cursor->rule->cls_match;
+ const struct cls_rule *rule;
const struct cls_subtable *subtable;
- const struct cls_match *next;
-
- next = next_rule_in_list__(rule);
- if (next->priority < rule->priority) {
- return next->cls_rule;
- }
- /* 'next' is the head of the list, that is, the rule that is included in
- * the subtable's map. (This is important when the classifier contains
- * rules that differ only in priority.) */
- rule = next;
- CMAP_CURSOR_FOR_EACH_CONTINUE (rule, cmap_node, &cursor->rules) {
+ rule = cursor->rule;
+ subtable = cursor->subtable;
+ RCULIST_FOR_EACH_CONTINUE (rule, node, &subtable->rules_list) {
if (rule_matches(rule, cursor->target)) {
- return rule->cls_rule;
+ return rule;
}
}
- subtable = cursor->subtable;
- CMAP_CURSOR_FOR_EACH_CONTINUE (subtable, cmap_node, &cursor->subtables) {
+ PVECTOR_CURSOR_FOR_EACH_CONTINUE (subtable, &cursor->subtables) {
rule = search_subtable(subtable, cursor);
if (rule) {
cursor->subtable = subtable;
- return rule->cls_rule;
+ return rule;
}
}
@@ -1114,15 +1114,8 @@ cls_cursor_next(struct cls_cursor *cursor)
* or to null if all matching rules have been visited. */
void
cls_cursor_advance(struct cls_cursor *cursor)
- OVS_NO_THREAD_SAFETY_ANALYSIS
{
- if (cursor->safe) {
- ovs_mutex_lock(&cursor->cls->mutex);
- }
cursor->rule = cls_cursor_next(cursor);
- if (cursor->safe || !cursor->rule) {
- ovs_mutex_unlock(&cursor->cls->mutex);
- }
}
static struct cls_subtable *
@@ -1201,6 +1194,9 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
*CONST_CAST(int *, &subtable->ports_mask_len)
= 32 - ctz32(ntohl(MINIFLOW_GET_BE32(&mask->masks, tp_src)));
+ /* List of rules. */
+ rculist_init(&subtable->rules_list);
+
cmap_insert(&cls->subtables_map, &subtable->cmap_node, hash);
return subtable;
@@ -1220,6 +1216,7 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
ovs_assert(ovsrcu_get_protected(struct trie_node *, &subtable->ports_trie)
== NULL);
ovs_assert(cmap_is_empty(&subtable->rules));
+ ovs_assert(rculist_is_empty(&subtable->rules_list));
for (i = 0; i < subtable->n_indices; i++) {
cmap_destroy(&subtable->indices[i]);
diff --git a/lib/classifier.h b/lib/classifier.h
index a884e24..9a5ca4e 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -218,6 +218,7 @@
#include "meta-flow.h"
#include "ovs-thread.h"
#include "pvector.h"
+#include "rculist.h"
#ifdef __cplusplus
extern "C" {
@@ -257,9 +258,10 @@ struct classifier {
/* A rule to be inserted to the classifier. */
struct cls_rule {
- struct minimatch match; /* Matching rule. */
+ struct rculist node; /* In struct cls_subtable 'rules_list'. */
int priority; /* Larger numbers are higher priorities. */
- struct cls_match *cls_match; /* NULL if rule is not in a classifier. */
+ struct cls_match *cls_match OVS_GUARDED; /* NULL if not in a classifier. */
+ struct minimatch match; /* Matching rule. */
};
void cls_rule_init(struct cls_rule *, const struct match *, int priority);
@@ -305,48 +307,40 @@ const struct cls_rule *classifier_find_match_exactly(const struct classifier *,
const struct match *,
int priority);
-/* Iteration. */
-
+/* Iteration.
+ *
+ * Iteration is lockless and RCU-protected. Concurrent threads may perform all
+ * kinds of concurrent modifications without ruining the iteration. Obviously,
+ * any modifications may or may not be visible to the concurrent iterator, but
+ * all the rules not deleted are visited by the iteration. The iterating
+ * thread may also modify the classifier rules itself.
+ *
+ * 'TARGET' iteration only iterates rules matching the 'TARGET' criteria.
+ * Rather than looping through all the rules and skipping ones that can't
+ * match, 'TARGET' iteration skips whole subtables, if the 'TARGET' happens to
+ * be more specific than the subtable. */
struct cls_cursor {
const struct classifier *cls;
const struct cls_subtable *subtable;
const struct cls_rule *target;
- struct cmap_cursor subtables;
- struct cmap_cursor rules;
+ struct pvector_cursor subtables;
const struct cls_rule *rule;
- bool safe;
};
-/* Iteration requires mutual exclusion of writers. We do this by taking
- * a mutex for the duration of the iteration, except for the
- * 'SAFE' variant, where we release the mutex for the body of the loop. */
struct cls_cursor cls_cursor_start(const struct classifier *cls,
- const struct cls_rule *target,
- bool safe);
-
+ const struct cls_rule *target);
void cls_cursor_advance(struct cls_cursor *);
-#define CLS_FOR_EACH(RULE, MEMBER, CLS) \
+#define CLS_FOR_EACH(RULE, MEMBER, CLS) \
CLS_FOR_EACH_TARGET(RULE, MEMBER, CLS, NULL)
#define CLS_FOR_EACH_TARGET(RULE, MEMBER, CLS, TARGET) \
- for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET, false); \
- (cursor__.rule \
- ? (INIT_CONTAINER(RULE, cursor__.rule, MEMBER), \
- true) \
- : false); \
- cls_cursor_advance(&cursor__))
-
-/* These forms allows classifier_remove() to be called within the loop. */
-#define CLS_FOR_EACH_SAFE(RULE, MEMBER, CLS) \
- CLS_FOR_EACH_TARGET_SAFE(RULE, MEMBER, CLS, NULL)
-#define CLS_FOR_EACH_TARGET_SAFE(RULE, MEMBER, CLS, TARGET) \
- for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET, true); \
+ for (struct cls_cursor cursor__ = cls_cursor_start(CLS, TARGET); \
(cursor__.rule \
? (INIT_CONTAINER(RULE, cursor__.rule, MEMBER), \
cls_cursor_advance(&cursor__), \
true) \
: false); \
- ) \
+ )
#ifdef __cplusplus
}
diff --git a/lib/flow.c b/lib/flow.c
index 7f28b4d..8c379f6 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -2012,8 +2012,8 @@ miniflow_equal(const struct miniflow *a, const struct miniflow *b)
return true;
}
-/* Returns true if 'a' and 'b' are equal at the places where there are 1-bits
- * in 'mask', false if they differ. */
+/* Returns false if 'a' and 'b' differ at the places where there are 1-bits
+ * in 'mask', true otherwise. */
bool
miniflow_equal_in_minimask(const struct miniflow *a, const struct miniflow *b,
const struct minimask *mask)
diff --git a/lib/ovs-router.c b/lib/ovs-router.c
index ba51614..696d7ec 100644
--- a/lib/ovs-router.c
+++ b/lib/ovs-router.c
@@ -258,7 +258,7 @@ ovs_router_flush(void)
{
struct ovs_router_entry *rt;
- CLS_FOR_EACH_SAFE(rt, cr, &cls) {
+ CLS_FOR_EACH(rt, cr, &cls) {
if (rt->priority == rt->plen) {
classifier_remove(&cls, &rt->cr);
}
diff --git a/lib/pvector.h b/lib/pvector.h
index 40c8e93..0d94b56 100644
--- a/lib/pvector.h
+++ b/lib/pvector.h
@@ -152,6 +152,13 @@ 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); \
+ ((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; )
+
/* Inline implementations. */
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index df963f8..12cc69c 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -1402,7 +1402,7 @@ destruct(struct ofproto *ofproto_)
hmap_remove(&all_ofproto_dpifs, &ofproto->all_ofproto_dpifs_node);
OFPROTO_FOR_EACH_TABLE (table, &ofproto->up) {
- CLS_FOR_EACH_SAFE (rule, up.cr, &table->cls) {
+ CLS_FOR_EACH (rule, up.cr, &table->cls) {
ofproto_rule_delete(&ofproto->up, &rule->up);
}
}
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 95f2905..c35bc3a 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -1391,7 +1391,7 @@ ofproto_flush__(struct ofproto *ofproto)
continue;
}
- CLS_FOR_EACH_SAFE (rule, cr, &table->cls) {
+ CLS_FOR_EACH (rule, cr, &table->cls) {
ofproto_rule_delete__(rule, OFPRR_DELETE);
}
}
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index d42de06..5bdb523 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -453,7 +453,7 @@ destroy_classifier(struct classifier *cls)
{
struct test_rule *rule;
- CLS_FOR_EACH_SAFE (rule, cls_rule, cls) {
+ CLS_FOR_EACH (rule, cls_rule, cls) {
if (classifier_remove(cls, &rule->cls_rule)) {
ovsrcu_postpone(free_rule, rule);
}
@@ -562,20 +562,18 @@ check_tables(const struct classifier *cls, int n_tables, int n_rules,
}
found_rules++;
- ovs_mutex_lock(&cls->mutex);
RCULIST_FOR_EACH (rule, list, &head->list) {
assert(rule->priority < prev_priority);
+ ovs_mutex_lock(&cls->mutex);
assert(rule->priority <= table->max_priority);
+ ovs_mutex_unlock(&cls->mutex);
prev_priority = rule->priority;
found_rules++;
found_dups++;
- ovs_mutex_unlock(&cls->mutex);
assert(classifier_find_rule_exactly(cls, rule->cls_rule)
== rule->cls_rule);
- ovs_mutex_lock(&cls->mutex);
}
- ovs_mutex_unlock(&cls->mutex);
}
ovs_mutex_lock(&cls->mutex);
assert(table->max_priority == max_priority);
@@ -1076,8 +1074,7 @@ test_many_rules_in_n_tables(int n_tables)
target = clone_rule(tcls.rules[random_range(tcls.n_rules)]);
- CLS_FOR_EACH_TARGET_SAFE (rule, cls_rule, &cls,
- &target->cls_rule) {
+ CLS_FOR_EACH_TARGET (rule, cls_rule, &cls, &target->cls_rule) {
if (classifier_remove(&cls, &rule->cls_rule)) {
ovsrcu_postpone(free_rule, rule);
}
diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c
index 21da4db..c039026 100644
--- a/utilities/ovs-ofctl.c
+++ b/utilities/ovs-ofctl.c
@@ -2368,9 +2368,9 @@ fte_free_all(struct classifier *cls)
{
struct fte *fte;
- CLS_FOR_EACH_SAFE (fte, rule, cls) {
+ CLS_FOR_EACH (fte, rule, cls) {
classifier_remove(cls, &fte->rule);
- fte_free(fte);
+ ovsrcu_postpone(fte_free, fte);
}
classifier_destroy(cls);
}
@@ -2392,10 +2392,10 @@ fte_insert(struct classifier *cls, const struct match *match,
old = fte_from_cls_rule(classifier_replace(cls, &fte->rule));
if (old) {
- fte_version_free(old->versions[index]);
fte->versions[!index] = old->versions[!index];
- cls_rule_destroy(&old->rule);
- free(old);
+ old->versions[!index] = NULL;
+
+ ovsrcu_postpone(fte_free, old);
}
}
--
1.7.10.4
More information about the dev
mailing list