[PATCH] ofproto: Optimise OpenFlow flow expiry

[Simon Horman]

Optimise OpenFlow flow expiry by placing expirable flows on a list.
This optimises scanning of flows for expiry in two ways:

* Flows that will never expire are not traversed.

  This addresses a case seen in the field.  With 1,000,000 flows that
  are not expirable, this dramatically reduces CPU utilization to
  approximately zero.

* Empirically list traversal appears faster than the code it replaces.

  With 1,000,000 expirable flows present an otherwise idle system I
  observed CPU utilisation of around 20% with the existing code but
  around 10% with this new code.

Signed-off-by: Simon Horman <horms at verge.net.au>
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
 ofproto/ofproto-dpif.c     |   13 ++++---------
 ofproto/ofproto-provider.h |    8 ++++++++
 ofproto/ofproto.c          |   10 ++++++++++
 3 files changed, 22 insertions(+), 9 deletions(-)

diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 2c216fe..69da618 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -3726,8 +3726,7 @@ 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;
+        struct rule *rule, *next_rule;
         int dp_max_idle;
 
         if (ofproto->backer != backer) {
@@ -3742,13 +3741,9 @@ 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;
-
-            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,
+                            &ofproto->up.expirable) {
+            rule_expire(rule_dpif_cast(rule));
         }
 
         /* All outstanding data in existing flows has been accounted, so it's a
diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
index f2274ef..95bda33 100644
--- a/ofproto/ofproto-provider.h
+++ b/ofproto/ofproto-provider.h
@@ -71,6 +71,10 @@ struct ofproto {
     struct oftable *tables;
     int n_tables;
 
+    /* Optimisation for flow expiry.
+     * These flows should all be present in tables. */
+    struct list expirable;      /* Expirable 'struct rule"s in all tables. */
+
     /* OpenFlow connections. */
     struct connmgr *connmgr;
 
@@ -221,6 +225,10 @@ struct rule {
     enum nx_flow_monitor_flags monitor_flags;
     uint64_t add_seqno;         /* Sequence number when added. */
     uint64_t modify_seqno;      /* Sequence number when changed. */
+
+    /* Optimisation for flow expiry. */
+    struct list expirable;      /* In ofproto's 'expirable' list if this rule
+                                 * is expirable, otherwise empty. */
 };
 
 static inline struct rule *
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index 9bae971..cd9d328 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -419,6 +419,7 @@ ofproto_create(const char *datapath_name, const char *datapath_type,
     ofproto->max_ports = OFPP_MAX;
     ofproto->tables = NULL;
     ofproto->n_tables = 0;
+    list_init(&ofproto->expirable);
     ofproto->connmgr = connmgr_create(ofproto, datapath_name, datapath_name);
     ofproto->state = S_OPENFLOW;
     list_init(&ofproto->pending);
@@ -3162,6 +3163,7 @@ add_flow(struct ofproto *ofproto, struct ofconn *ofconn,
     rule->ofpacts_len = fm->ofpacts_len;
     rule->evictable = true;
     rule->eviction_group = NULL;
+    list_init(&rule->expirable);
     rule->monitor_flags = 0;
     rule->add_seqno = 0;
     rule->modify_seqno = 0;
@@ -4824,6 +4826,9 @@ oftable_remove_rule(struct rule *rule)
 
     classifier_remove(&table->cls, &rule->cr);
     eviction_group_remove_rule(rule);
+    if (!list_is_empty(&rule->expirable)) {
+        list_remove(&rule->expirable);
+    }
 }
 
 /* Inserts 'rule' into its oftable.  Removes any existing rule from 'rule''s
@@ -4835,6 +4840,11 @@ oftable_replace_rule(struct rule *rule)
     struct ofproto *ofproto = rule->ofproto;
     struct oftable *table = &ofproto->tables[rule->table_id];
     struct rule *victim;
+    bool may_expire = rule->hard_timeout || rule->idle_timeout;
+
+    if (may_expire) {
+        list_insert(&ofproto->expirable, &rule->expirable);
+    }
 
     victim = rule_from_cls_rule(classifier_replace(&table->cls, &rule->cr));
     if (victim) {
-- 
1.7.10.4