From e503cc1993970ef27882a9b922efbd365d9da2be Mon Sep 17 00:00:00 2001 From: Simon Horman Date: Tue, 15 Jan 2013 13:20:57 +0900 Subject: [PATCH] ofproto: Optimise OpenFlow flow expiry 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 Signed-off-by: Ben Pfaff --- 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 d75a63ccc..1d08bafb8 100644 --- a/ofproto/ofproto-dpif.c +++ b/ofproto/ofproto-dpif.c @@ -3805,8 +3805,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) { @@ -3821,13 +3820,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 f2274ef13..95bda33a1 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 b6cd0829c..bc2707986 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); @@ -3164,6 +3165,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; @@ -4826,6 +4828,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 @@ -4837,6 +4842,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) { -- 2.43.0