Optimise OpenFlow flow expiry by placing expirable flows on a list.
This optimises scanning of flows for expiry in two ways:
* Empirically list traversal appears faster than the code it replaces.
With 1,000,000 flows present an otherwise idle system I observed CPU
utilisation of around 20% with the existing code but around 10% with
this new code.
* Flows that will never expire are not traversed.
This addresses a case seen in the field.
Signed-off-by: Simon Horman <ho...@verge.net.au>
---
lib/classifier.c | 13 +++++++++++--
lib/classifier.h | 5 ++++-
ofproto/ofproto-dpif.c | 9 ++++-----
ofproto/ofproto-provider.h | 7 +++++++
ofproto/ofproto.c | 2 +-
tests/test-classifier.c | 4 ++--
utilities/ovs-ofctl.c | 11 +++++++----
7 files changed, 36 insertions(+), 15 deletions(-)
diff --git a/lib/classifier.c b/lib/classifier.c
index d1fe524..48699a0 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -66,6 +66,7 @@ cls_rule_init(struct cls_rule *rule,
const struct match *match, unsigned int priority)
{
minimatch_init(&rule->match, match);
+ list_init(&rule->expirable);
rule->priority = priority;
}
@@ -135,6 +136,7 @@ classifier_init(struct classifier *cls)
{
cls->n_rules = 0;
hmap_init(&cls->tables);
+ list_init(&cls->expirable);
}
/* Destroys 'cls'. Rules within 'cls', if any, are not freed; this is the
@@ -180,7 +182,8 @@ classifier_count(const struct classifier *cls)
* rule, even rules that cannot have any effect because the new rule matches a
* superset of their flows and has higher priority. */
struct cls_rule *
-classifier_replace(struct classifier *cls, struct cls_rule *rule)
+classifier_replace(struct classifier *cls, struct cls_rule *rule,
+ bool may_expire)
{
struct cls_rule *old_rule;
struct cls_table *table;
@@ -195,6 +198,9 @@ classifier_replace(struct classifier *cls, struct cls_rule
*rule)
table->n_table_rules++;
cls->n_rules++;
}
+ if (may_expire) {
+ list_insert(&cls->expirable, &rule->expirable);
+ }
return old_rule;
}
@@ -207,7 +213,7 @@ classifier_replace(struct classifier *cls, struct cls_rule
*rule)
void
classifier_insert(struct classifier *cls, struct cls_rule *rule)
{
- struct cls_rule *displaced_rule = classifier_replace(cls, rule);
+ struct cls_rule *displaced_rule = classifier_replace(cls, rule, false);
assert(!displaced_rule);
}
@@ -238,6 +244,9 @@ classifier_remove(struct classifier *cls, struct cls_rule
*rule)
destroy_table(cls, table);
}
+ if (!list_is_empty(&rule->expirable))
+ list_remove(&rule->expirable);
+
cls->n_rules--;
}
diff --git a/lib/classifier.h b/lib/classifier.h
index bc9db33..5a6d894 100644
--- a/lib/classifier.h
+++ b/lib/classifier.h
@@ -41,6 +41,7 @@ extern "C" {
struct classifier {
int n_rules; /* Total number of rules. */
struct hmap tables; /* Contains "struct cls_table"s. */
+ struct list expirable; /* Contains expirable rules. */
};
/* A set of rules that all have the same fields wildcarded. */
@@ -64,6 +65,7 @@ struct cls_rule {
struct hmap_node hmap_node; /* Within struct cls_table 'rules'. */
struct list list; /* List of identical, lower-priority rules. */
struct minimatch match; /* Matching rule. */
+ struct list expirable; /* Entry in struct classifier 'expirable'. */
unsigned int priority; /* Larger numbers are higher priorities. */
};
@@ -89,7 +91,8 @@ void classifier_destroy(struct classifier *);
bool classifier_is_empty(const struct classifier *);
int classifier_count(const struct classifier *);
void classifier_insert(struct classifier *, struct cls_rule *);
-struct cls_rule *classifier_replace(struct classifier *, struct cls_rule *);
+struct cls_rule *classifier_replace(struct classifier *, struct cls_rule *,
+ bool may_expire);
void classifier_remove(struct classifier *, struct cls_rule *);
struct cls_rule *classifier_lookup(const struct classifier *,
const struct flow *);
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index bc54122..6aba16e 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -3725,7 +3725,6 @@ expire(struct dpif_backer *backer)
update_stats(backer);
HMAP_FOR_EACH (ofproto, all_ofproto_dpifs_node, &all_ofproto_dpifs) {
- struct rule_dpif *rule, *next_rule;
struct oftable *table;
int dp_max_idle;
@@ -3742,11 +3741,11 @@ expire(struct dpif_backer *backer)
/* Expire OpenFlow flows whose idle_timeout or hard_timeout
* has passed. */
OFPROTO_FOR_EACH_TABLE (table, &ofproto->up) {
- struct cls_cursor cursor;
+ struct cls_rule *rule, *next_rule;
- cls_cursor_init(&cursor, &table->cls, NULL);
- CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, up.cr, &cursor) {
- rule_expire(rule);
+ LIST_FOR_EACH_SAFE(rule, next_rule, expirable,
+ &table->cls.expirable) {
+ rule_expire(rule_dpif_cast(rule_from_cls_rule(rule)));
}
}
diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
index f2274ef..1169538 100644
--- a/ofproto/ofproto-provider.h
+++ b/ofproto/ofproto-provider.h
@@ -229,6 +229,13 @@ rule_from_cls_rule(const struct cls_rule *cls_rule)
return cls_rule ? CONTAINER_OF(cls_rule, struct rule, cr) : NULL;
}
+static inline struct rule *
+rule_replace(struct classifier *cls, struct rule *rule)
+{
+ bool may_expire = rule->hard_timeout || rule->idle_timeout;
+ return rule_from_cls_rule(classifier_replace(cls, &rule->cr, may_expire));
+}
+
void ofproto_rule_update_used(struct rule *, long long int used);
void ofproto_rule_expire(struct rule *, uint8_t reason);
void ofproto_rule_destroy(struct rule *);
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 98515c2..60fb545 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -4848,7 +4848,7 @@ oftable_replace_rule(struct rule *rule)
struct oftable *table = &ofproto->tables[rule->table_id];
struct rule *victim;
- victim = rule_from_cls_rule(classifier_replace(&table->cls, &rule->cr));
+ victim = rule_replace(&table->cls, rule);
if (victim) {
eviction_group_remove_rule(victim);
}
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
index b1461ff..5519574 100644
--- a/tests/test-classifier.c
+++ b/tests/test-classifier.c
@@ -671,7 +671,7 @@ test_rule_replacement(int argc OVS_UNUSED, char *argv[]
OVS_UNUSED)
tcls_init(&tcls);
tcls_insert(&tcls, rule2);
assert(test_rule_from_cls_rule(
- classifier_replace(&cls, &rule2->cls_rule)) == rule1);
+ classifier_replace(&cls, &rule2->cls_rule, false)) ==
rule1);
free_rule(rule1);
check_tables(&cls, 1, 1, 0);
compare_classifiers(&cls, &tcls);
@@ -782,7 +782,7 @@ test_many_rules_in_one_list (int argc OVS_UNUSED, char
*argv[] OVS_UNUSED)
tcls_rules[j] = tcls_insert(&tcls, rules[j]);
displaced_rule = test_rule_from_cls_rule(
- classifier_replace(&cls, &rules[j]->cls_rule));
+ classifier_replace(&cls, &rules[j]->cls_rule, false));
if (pri_rules[pris[j]] >= 0) {
int k = pri_rules[pris[j]];
assert(displaced_rule != NULL);
diff --git a/utilities/ovs-ofctl.c b/utilities/ovs-ofctl.c
index 239f317..fa855c5 100644
--- a/utilities/ovs-ofctl.c
+++ b/utilities/ovs-ofctl.c
@@ -1848,7 +1848,8 @@ fte_free_all(struct classifier *cls)
* Takes ownership of 'version'. */
static void
fte_insert(struct classifier *cls, const struct match *match,
- unsigned int priority, struct fte_version *version, int index)
+ unsigned int priority, struct fte_version *version, int index,
+ bool may_expire)
{
struct fte *old, *fte;
@@ -1856,7 +1857,7 @@ fte_insert(struct classifier *cls, const struct match
*match,
cls_rule_init(&fte->rule, match, priority);
fte->versions[index] = version;
- old = fte_from_cls_rule(classifier_replace(cls, &fte->rule));
+ old = fte_from_cls_rule(classifier_replace(cls, &fte->rule, may_expire));
if (old) {
fte_version_free(old->versions[index]);
fte->versions[!index] = old->versions[!index];
@@ -1885,6 +1886,7 @@ read_flows_from_file(const char *filename, struct
classifier *cls, int index)
while (!ds_get_preprocessed_line(&s, file)) {
struct fte_version *version;
struct ofputil_flow_mod fm;
+ bool may_expire = fm.idle_timeout || fm.hard_timeout;
parse_ofp_str(&fm, OFPFC_ADD, ds_cstr(&s), true);
@@ -1898,7 +1900,7 @@ read_flows_from_file(const char *filename, struct
classifier *cls, int index)
usable_protocols &= ofputil_usable_protocols(&fm.match);
- fte_insert(cls, &fm.match, fm.priority, version, index);
+ fte_insert(cls, &fm.match, fm.priority, version, index, may_expire);
}
ds_destroy(&s);
@@ -1990,6 +1992,7 @@ read_flows_from_switch(struct vconn *vconn,
ofpbuf_init(&ofpacts, 0);
while (recv_flow_stats_reply(vconn, send_xid, &reply, &fs, &ofpacts)) {
struct fte_version *version;
+ bool may_expire = fs.idle_timeout || fs.hard_timeout;
version = xmalloc(sizeof *version);
version->cookie = fs.cookie;
@@ -1999,7 +2002,7 @@ read_flows_from_switch(struct vconn *vconn,
version->ofpacts_len = fs.ofpacts_len;
version->ofpacts = xmemdup(fs.ofpacts, fs.ofpacts_len);
- fte_insert(cls, &fs.match, fs.priority, version, index);
+ fte_insert(cls, &fs.match, fs.priority, version, index, may_expire);
}
ofpbuf_uninit(&ofpacts);
}
--
1.7.10.4
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
