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 <ho...@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 <ho...@verge.net.au>
> Signed-off-by: Ben Pfaff <b...@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
>
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
