[ovs-dev] [PATCH] ofproto: Optimise OpenFlow flow expiry

Simon Horman horms at verge.net.au
Mon Jan 14 01:06:13 UTC 2013


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 <horms at 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



More information about the dev mailing list