From f70b94debcce380d3d67e346b7eaf47749e23005 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 3 Jul 2015 08:45:15 -0700 Subject: [PATCH] ofproto: Use OF1.4+ "importance" as part of eviction criteria. The "importance" field is considered before flow timeout because I figure that if you set the importance, you think it's important. Signed-off-by: Ben Pfaff Co-authored-by: Saloni Jain Signed-off-by: Saloni Jain Acked-by: Jarno Rajahalme --- NEWS | 1 + ofproto/ofproto.c | 42 +++++++++++++++++------------- tests/ofproto.at | 62 ++++++++++++++++++++++++++++++++++++++++++++ vswitchd/vswitch.xml | 19 +++++++++++--- 4 files changed, 102 insertions(+), 22 deletions(-) diff --git a/NEWS b/NEWS index d6db7d068..3da7cfd11 100644 --- a/NEWS +++ b/NEWS @@ -6,6 +6,7 @@ Post-v2.4.0 - OpenFlow: * Group chaining (where one OpenFlow group triggers another) is now supported. + * OpenFlow 1.4+ "importance" is now considered for flow eviction. - Support for matching and generating options with Geneve tunnels. - Support Multicast Listener Discovery (MLDv1 and MLDv2). diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c index c6fbf9f38..4aa844e5c 100644 --- a/ofproto/ofproto.c +++ b/ofproto/ofproto.c @@ -115,8 +115,8 @@ struct eviction_group { static bool choose_rule_to_evict(struct oftable *table, struct rule **rulep) OVS_REQUIRES(ofproto_mutex); -static uint32_t rule_eviction_priority(struct ofproto *ofproto, struct rule *) - OVS_REQUIRES(ofproto_mutex);; +static uint64_t rule_eviction_priority(struct ofproto *ofproto, struct rule *) + OVS_REQUIRES(ofproto_mutex); static void eviction_group_add_rule(struct rule *) OVS_REQUIRES(ofproto_mutex); static void eviction_group_remove_rule(struct rule *) @@ -7384,23 +7384,21 @@ eviction_group_find(struct oftable *table, uint32_t id) } /* Returns an eviction priority for 'rule'. The return value should be - * interpreted so that higher priorities make a rule more attractive candidates - * for eviction. - * Called only if have a timeout. */ -static uint32_t + * interpreted so that higher priorities make a rule a more attractive + * candidate for eviction. */ +static uint64_t rule_eviction_priority(struct ofproto *ofproto, struct rule *rule) OVS_REQUIRES(ofproto_mutex) { + /* Calculate absolute time when this flow will expire. If it will never + * expire, then return 0 to make it unevictable. */ long long int expiration = LLONG_MAX; - long long int modified; - uint32_t expiration_offset; - - /* 'modified' needs protection even when we hold 'ofproto_mutex'. */ - ovs_mutex_lock(&rule->mutex); - modified = rule->modified; - ovs_mutex_unlock(&rule->mutex); - if (rule->hard_timeout) { + /* 'modified' needs protection even when we hold 'ofproto_mutex'. */ + ovs_mutex_lock(&rule->mutex); + long long int modified = rule->modified; + ovs_mutex_unlock(&rule->mutex); + expiration = modified + rule->hard_timeout * 1000; } if (rule->idle_timeout) { @@ -7412,7 +7410,6 @@ rule_eviction_priority(struct ofproto *ofproto, struct rule *rule) idle_expiration = used + rule->idle_timeout * 1000; expiration = MIN(expiration, idle_expiration); } - if (expiration == LLONG_MAX) { return 0; } @@ -7422,10 +7419,19 @@ rule_eviction_priority(struct ofproto *ofproto, struct rule *rule) * * This should work OK for program runs that last UINT32_MAX seconds or * less. Therefore, please restart OVS at least once every 136 years. */ - expiration_offset = (expiration >> 10) - (time_boot_msec() >> 10); + uint32_t expiration_ofs = (expiration >> 10) - (time_boot_msec() >> 10); - /* Invert the expiration offset because we're using a max-heap. */ - return UINT32_MAX - expiration_offset; + /* Combine expiration time with OpenFlow "importance" to form a single + * priority value. We want flows with relatively low "importance" to be + * evicted before even considering expiration time, so put "importance" in + * the most significant bits and expiration time in the least significant + * bits. + * + * Small 'priority' should be evicted before those with large 'priority'. + * The caller expects the opposite convention (a large return value being + * more attractive for eviction) so we invert it before returning. */ + uint64_t priority = ((uint64_t) rule->importance << 32) + expiration_ofs; + return UINT64_MAX - priority; } /* Adds 'rule' to an appropriate eviction group for its oftable's diff --git a/tests/ofproto.at b/tests/ofproto.at index a564c8156..c4556f719 100644 --- a/tests/ofproto.at +++ b/tests/ofproto.at @@ -1864,6 +1864,68 @@ OFPST_FLOW reply (OF1.2): OVS_VSWITCHD_STOP AT_CLEANUP +AT_SETUP([ofproto - eviction using importance upon table overflow (OpenFlow 1.4)]) +OVS_VSWITCHD_START +# Configure a maximum of 4 flows. +AT_CHECK( + [ovs-vsctl \ + -- --id=@t0 create Flow_Table name=evict flow-limit=4 overflow-policy=evict \ + -- set bridge br0 flow_tables:0=@t0 \ + | ${PERL} $srcdir/uuidfilt.pl], + [0], [<0> +]) +# Add 4 flows. +for in_port in 4 3 2 1; do + ovs-ofctl -O Openflow14 add-flow br0 importance=$((in_port + 30)),priority=$((in_port + 5)),hard_timeout=$((in_port + 500)),actions=drop +done +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl + hard_timeout=501, importance=31, priority=6 actions=drop + hard_timeout=502, importance=32, priority=7 actions=drop + hard_timeout=503, importance=33, priority=8 actions=drop + hard_timeout=504, importance=34, priority=9 actions=drop +OFPST_FLOW reply (OF1.4): +]) +# Adding another flow will cause the one with lowest importance to be evicted. +AT_CHECK([ovs-ofctl -O Openflow14 add-flow br0 hard_timeout=505,importance=35,priority=10,in_port=2,actions=drop]) +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl + hard_timeout=502, importance=32, priority=7 actions=drop + hard_timeout=503, importance=33, priority=8 actions=drop + hard_timeout=504, importance=34, priority=9 actions=drop + hard_timeout=505, importance=35, priority=10,in_port=2 actions=drop +OFPST_FLOW reply (OF1.4): +]) +# Disable the Eviction configuration. +AT_CHECK([ovs-vsctl set Flow_Table evict overflow-policy=refuse]) +# Adding another flow will cause the system to give error for FULL TABLE. +AT_CHECK([ovs-ofctl -O Openflow14 add-flow br0 hard_timeout=506,importance=36,priority=11,actions=drop],[1], [], [stderr]) +AT_CHECK([head -n 1 stderr | ofctl_strip], [0], + [OFPT_ERROR (OF1.4): OFPFMFC_TABLE_FULL +]) +#Dump flows. It should show only the old values +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl + hard_timeout=502, importance=32, priority=7 actions=drop + hard_timeout=503, importance=33, priority=8 actions=drop + hard_timeout=504, importance=34, priority=9 actions=drop + hard_timeout=505, importance=35, priority=10,in_port=2 actions=drop +OFPST_FLOW reply (OF1.4): +]) +# mod-flow that would modify a flow will be done successfully. +AT_CHECK([ovs-ofctl -O Openflow14 mod-flows br0 in_port=2,actions=NORMAL]) +AT_CHECK([ovs-ofctl -O Openflow14 dump-flows br0 | ofctl_strip | sort], [0], [dnl + hard_timeout=502, importance=32, priority=7 actions=drop + hard_timeout=503, importance=33, priority=8 actions=drop + hard_timeout=504, importance=34, priority=9 actions=drop + hard_timeout=505, importance=35, priority=10,in_port=2 actions=NORMAL +OFPST_FLOW reply (OF1.4): +]) +# Also a mod-flow that would add a flow will be refused. +AT_CHECK([ovs-ofctl mod-flows br0 in_port=5,actions=drop], [1], [], [stderr]) +AT_CHECK([head -n 1 stderr | ofctl_strip], [0], + [OFPT_ERROR: OFPFMFC_TABLE_FULL +]) +OVS_VSWITCHD_STOP +AT_CLEANUP + AT_SETUP([ofproto - eviction upon table overflow, with fairness (OpenFlow 1.0)]) OVS_VSWITCHD_START # Configure a maximum of 4 flows. diff --git a/vswitchd/vswitch.xml b/vswitchd/vswitch.xml index b1d30f656..9f108f0cc 100644 --- a/vswitchd/vswitch.xml +++ b/vswitchd/vswitch.xml @@ -3082,15 +3082,18 @@

When a flow must be evicted due to overflow, the flow to evict is - chosen through an approximation of the following algorithm: + chosen through an approximation of the following algorithm. This + algorithm is used regardless of how eviction was enabled:

  1. Divide the flows in the table into groups based on the values of the - specified fields or subfields, so that all of the flows in a given - group have the same values for those fields. If a flow does not - specify a given field, that field's value is treated as 0. + fields or subfields specified in the column, + so that all of the flows in a given group have the same values for + those fields. If a flow does not specify a given field, that field's + value is treated as 0. If is empty, then all + of the flows in the flow table are treated as a single group.
  2. @@ -3100,6 +3103,14 @@ those groups.
    3. +
  3. + If the flows under consideration have different importance values, + eliminate from consideration any flows except those with the lowest + importance. (``Importance,'' a 16-bit integer value attached to each + flow, was introduced in OpenFlow 1.4. Flows inserted with older + versions of OpenFlow always have an importance of 0.) +
    4. +
  4. Among the flows under consideration, choose the flow that expires soonest for eviction. -- 2.20.1