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

Simon Horman horms at verge.net.au
Fri Jan 25 04:46:15 UTC 2013


On Wed, Jan 23, 2013 at 09:48:17AM -0800, Ben Pfaff wrote:
> On Thu, Jan 17, 2013 at 09:42:29AM +0900, Simon Horman wrote:
> > On Wed, Jan 16, 2013 at 01:59:21PM -0800, Ben Pfaff wrote:
> > > On Tue, Jan 15, 2013 at 01:20:57PM +0900, Simon Horman wrote:
> > > > 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.
> > > 
> > > This version looks better.  I still have a few comments, but before
> > > that, may I ask a little bit about the situation in which the
> > > performance improvement was observed?  In this situation, about how
> > > many of the 1,000,000 flows were actually expirable, that is, had
> > > either a hard timeout or an idle timeout?  That is, is the performance
> > > improvement due more to the first or the second bullet you list above?
> > > If none of the flows were expirable, then I guess it was the second;
> > > if all of them were, then I guess it was the first; and otherwise it
> > > is something in between.
> > > 
> > > Basically I'm wondering if we should do something to make flow table
> > > traversal faster, independent of expiration.
> > 
> > Hi Ben,
> > 
> > the primary aim of this patch was to address a performance issue that
> > was noticed when inserting 100,000 flows none of which were expirable.
> > I have been told this is representative of an expected use-case.
> > 
> > During my testing I used 1,000,000 flows instead of 100,000 in order to
> > make the CPU utilisation more pronounced and easier to observe.
> > 
> > In the course of my testing I tested 1,000,000 flows none of which were
> > expirable and in that case CPU utilisation was dramatically reduced to
> > approximately 0. This seems to be a good outcome for the use-case
> > originally reported.
> > 
> > In the course of testing I also tested 1,000,000 flows all of which
> > were expirable. This was primarily to see if there were any regressions.
> > In the course of this test I noticed that there seemed to be some
> > reduction in CPU utilisation. However this was just a side effect and
> > not an aim of my work. I should have placed it as the second bullet
> > in my commit message and noted that it was a side effect.
> 
> OK, I made a few stylistic and comment changes to the patch, and I've
> updated the commit message to reflect what you said above.  I'm happy
> with it now, but I don't want to apply it without your approval since I
> changed the meaning of your commit message.  Please review?

Looks good. Please feel free to apply.

> --8<--------------------------cut here-------------------------->8--
> 
> >From 5eee5262555b30c03676975c31543e19e893b1b7 Mon Sep 17 00:00:00 2001
> From: Simon Horman <horms at verge.net.au>
> 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 <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
> 



More information about the dev mailing list