[ovs-dev] [PATCH 3/3] ofproto-dpif: Use dp_hash as default selection method

Jan Scheurich jan.scheurich at ericsson.com
Tue Mar 20 18:16:18 UTC 2018


The dp_hash selection method for select groups overcomes the scalability
problems of the current default selection method which, due to L2-L4
hashing during xlation and un-wildcarding of the hashed fields,
basically requires an upcall to the slow path to load-balance every
L4 connection. The consequence are an explosion of datapath flows
(megaflows degenerate to miniflows) and a limitation of connection
setup rate OVS can handle.

This commit changes the default selection method to dp_hash, provided the
bucket configuration is such that the dp_hash method can accurately
represent the bucket weights with up to 64 hash values. Otherwise we
stick to original default hash method.

We use the new dp_hash algorithm OVS_HASH_L4_SYMMETRIC to maintain the
symmetry property of the old default hash method.

A controller can explicitly request the old default hash selection method
by specifying selection method "hash" with an empty list of fields in the
Group properties of the OpenFlow 1.5 Group Mod message.

Signed-off-by: Jan Scheurich <jan.scheurich at ericsson.com>
Signed-off-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
Co-authored-by: Nitin Katiyar <nitin.katiyar at ericsson.com>
---
 lib/ofp-group.c            | 15 +++++++----
 ofproto/ofproto-dpif.c     | 18 +++++++++++--
 ofproto/ofproto-dpif.h     |  1 +
 ofproto/ofproto-provider.h |  2 +-
 tests/mpls-xlate.at        | 26 +++++++++++-------
 tests/ofproto-dpif.at      | 66 ++++++++++++++++++++++++++++++----------------
 6 files changed, 88 insertions(+), 40 deletions(-)

diff --git a/lib/ofp-group.c b/lib/ofp-group.c
index 31b0437..c5ddc65 100644
--- a/lib/ofp-group.c
+++ b/lib/ofp-group.c
@@ -1518,12 +1518,17 @@ parse_group_prop_ntr_selection_method(struct ofpbuf *payload,
         return OFPERR_OFPBPC_BAD_VALUE;
     }
 
-    error = oxm_pull_field_array(payload->data, fields_len,
-                                 &gp->fields);
-    if (error) {
-        OFPPROP_LOG(&rl, false,
+    if (fields_len > 0) {
+        error = oxm_pull_field_array(payload->data, fields_len,
+                &gp->fields);
+        if (error) {
+            OFPPROP_LOG(&rl, false,
                     "ntr selection method fields are invalid");
-        return error;
+            return error;
+        }
+    } else {
+        /* Selection_method "hash: w/o fields means default hash method. */
+        gp->fields.values_size = 0;
     }
 
     return 0;
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 383d04e..1801670 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -4812,8 +4812,21 @@ group_set_selection_method(struct group_dpif *group)
 
     if (selection_method[0] == '\0') {
         VLOG_INFO("No selection method specified.");
-        group->selection_method = SEL_METHOD_DEFAULT;
-
+        /* If the controller has not specified a selection method, check if
+         * the dp_hash selection method with max 64 hash values is appropriate
+         * for the given bucket configuration. */
+        if (group_setup_dp_hash_table(group, 64)) {
+            /* Use dp_hash selection method with symmetric L4 hash. */
+            VLOG_INFO("  Use dp_hash with %d hash values.",
+                      group->hash_mask + 1);
+            group->selection_method = SEL_METHOD_DP_HASH;
+            group->hash_alg = OVS_HASH_ALG_SYM_L4;
+            group->hash_basis = 0xdeadbeef;
+        } else {
+            /* Fall back to original default hashing in slow path. */
+            VLOG_INFO("  Falling back to default hash method.");
+            group->selection_method = SEL_METHOD_DEFAULT;
+        }
     } else if (!strcmp(selection_method, "dp_hash")) {
         VLOG_INFO("Selection method specified: dp_hash.");
         /* Try to use dp_hash if possible at all. */
@@ -4831,6 +4844,7 @@ group_set_selection_method(struct group_dpif *group)
             VLOG_INFO("  Falling back to default hash method.");
             group->selection_method = SEL_METHOD_DEFAULT;
         }
+
     } else if (!strcmp(selection_method, "hash")) {
         VLOG_INFO("Selection method specified: hash.");
         if (props->fields.values_size > 0) {
diff --git a/ofproto/ofproto-dpif.h b/ofproto/ofproto-dpif.h
index 6a58b48..b1972aa 100644
--- a/ofproto/ofproto-dpif.h
+++ b/ofproto/ofproto-dpif.h
@@ -61,6 +61,7 @@ struct ofproto_async_msg;
 struct ofproto_dpif;
 struct uuid;
 struct xlate_cache;
+struct xlate_ctx;
 
 /* Number of implemented OpenFlow tables. */
 enum { N_TABLES = 255 };
diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
index 92d4622..fd5b249 100644
--- a/ofproto/ofproto-provider.h
+++ b/ofproto/ofproto-provider.h
@@ -572,7 +572,7 @@ struct ofgroup {
     const struct ovs_list buckets;    /* Contains "struct ofputil_bucket"s. */
     const uint32_t n_buckets;
 
-    const struct ofputil_group_props props;
+    struct ofputil_group_props props;
 
     struct rule_collection rules OVS_GUARDED;   /* Referring rules. */
 };
diff --git a/tests/mpls-xlate.at b/tests/mpls-xlate.at
index 9bbf22a..686fa35 100644
--- a/tests/mpls-xlate.at
+++ b/tests/mpls-xlate.at
@@ -68,12 +68,18 @@ AT_CHECK([tail -1 stdout], [0],
 dnl Test MPLS pop then select group output (group type triggers recirculation)
 AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x8847),mpls(label=22,tc=0,ttl=64,bos=1)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: pop_mpls(eth_type=0x800),recirc(0x2)
+  [Datapath actions: pop_mpls(eth_type=0x800),hash(hash_l4(0)),recirc(0x2)
 ])
 
-AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(2),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
-AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: 100
+for d in 0 1 2 3; do
+    pkt="in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x8847),mpls(label=22,tc=0,ttl=64,bos=1)"
+    AT_CHECK([ovs-appctl netdev-dummy/receive p0 $pkt])
+done
+
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0XXXX\/0xf)/' |  sed 's/packets.*actions:1/actions:1/' | strip_used | strip_ufid | sort], [0], [dnl
+flow-dump from non-dpdk interfaces:
+recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x8847),mpls(label=22/0xfffff,tc=0/0,ttl=64/0x0,bos=1/1), packets:3, bytes:54, used:0.0s, actions:pop_mpls(eth_type=0x800),hash(hash_l4(0)),recirc(0x3)
+recirc_id(0x3),dp_hash(0XXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:100
 ])
 
 dnl Test MPLS pop then all group output (bucket actions do not trigger recirculation)
@@ -85,10 +91,10 @@ AT_CHECK([tail -1 stdout], [0],
 dnl Test MPLS pop then all group output (bucket actions trigger recirculation)
 AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x8847),mpls(label=24,tc=0,ttl=64,bos=1)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: pop_mpls(eth_type=0x800),recirc(0x3)
+  [Datapath actions: pop_mpls(eth_type=0x800),recirc(0x4)
 ])
 
-AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(3),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
+AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(4),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
   [Datapath actions: set(ipv4(ttl=63)),100
 ])
@@ -96,10 +102,10 @@ AT_CHECK([tail -1 stdout], [0],
 dnl Test MPLS pop then all output to patch port
 AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x8847),mpls(label=25,tc=0,ttl=64,bos=1)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: pop_mpls(eth_type=0x800),recirc(0x4)
+  [Datapath actions: pop_mpls(eth_type=0x800),recirc(0x5)
 ])
 
-AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(4),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
+AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(5),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
   [Datapath actions: 101
 ])
@@ -124,10 +130,10 @@ AT_CHECK([tail -1 stdout], [0],
 dnl Double MPLS pop
 AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x8847),mpls(label=60,tc=0,ttl=64,bos=0,label=50,tc=0,ttl=64,bos=1)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: pop_mpls(eth_type=0x8847),pop_mpls(eth_type=0x800),recirc(0x5)
+  [Datapath actions: pop_mpls(eth_type=0x8847),pop_mpls(eth_type=0x800),recirc(0x7)
 ])
 
-AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(5),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
+AT_CHECK([ovs-appctl ofproto/trace ovs-dummy 'recirc_id(7),in_port(1),eth(src=f8:bc:12:44:34:b6,dst=f8:bc:12:46:58:e0),eth_type(0x0800),ipv4(src=1.1.2.92,dst=1.1.2.88,proto=47,tos=0,ttl=64,frag=no)'], [0], [stdout])
 AT_CHECK([tail -1 stdout], [0],
   [Datapath actions: set(ipv4(ttl=10)),100
 ])
diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at
index d2058ed..e227f71 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -337,10 +337,18 @@ OVS_VSWITCHD_START
 add_of_ports br0 1 10
 AT_CHECK([ovs-ofctl -O OpenFlow12 add-group br0 'group_id=1234,type=select,bucket=set_field:192.168.3.90->ip_src,output:10'])
 AT_CHECK([ovs-ofctl -O OpenFlow12 add-flow br0 'ip actions=group:1234,output:10'])
-AT_CHECK([ovs-appctl ofproto/trace br0 'in_port=1,dl_src=50:54:00:00:00:05,dl_dst=50:54:00:00:00:07,dl_type=0x0800,nw_src=192.168.0.1,nw_dst=192.168.0.2,nw_proto=1,nw_tos=0,nw_ttl=128,icmp_type=8,icmp_code=0'], [0], [stdout])
-AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: set(ipv4(src=192.168.3.90,dst=192.168.0.2)),10,set(ipv4(src=192.168.0.1,dst=192.168.0.2)),10
+
+for d in 0 1 2 3; do
+    pkt="in_port(1),eth(src=50:54:00:00:00:07,dst=50:54:00:00:00:1),eth_type(0x0800),ipv4(src=192.168.0.1,dst=192.168.1.2,proto=1,tos=0,ttl=128,frag=no),icmp(type=8,code=0)"
+    AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt])
+done
+
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' |  sed 's/packets.*actions:/actions:/' | strip_ufid | strip_used | sort], [0], [dnl
+flow-dump from non-dpdk interfaces:
+recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:hash(hash_l4(0)),recirc(0x1)
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), actions:set(ipv4(src=192.168.3.90)),10,set(ipv4(src=192.168.0.1)),10
 ])
+
 OVS_VSWITCHD_STOP
 AT_CLEANUP
 
@@ -403,16 +411,21 @@ AT_CHECK([ovs-ofctl -O OpenFlow12 add-group br0 'group_id=1234,type=select,bucke
 AT_CHECK([ovs-ofctl -O OpenFlow12 add-flow br0 'ip actions=write_actions(group:1234)'])
 
 # Try a bunch of different flows and make sure that they get distributed
-# at least somewhat.
-for d in 0 1 2 3 4 5 6 7 8 9 a b c d e f; do
-    AT_CHECK([ovs-appctl ofproto/trace br0 "in_port=1,dl_src=50:54:00:00:00:07,dl_dst=50:54:00:00:00:0$d,dl_type=0x0800,nw_src=192.168.0.1,nw_dst=192.168.0.2,nw_proto=1,nw_tos=0,nw_ttl=128,icmp_type=8,icmp_code=0"], [0], [stdout])
-    tail -1 stdout >> results
+# # at least somewhat.
+for d in 0 1 2 3; do
+    for i in 1 2 ; do
+        pkt="in_port(1),eth(src=50:54:00:00:00:07,dst=50:54:00:00:00:1),eth_type(0x0800),ipv4(src=192.168.0.1,dst=192.168.1.$i,proto=1,tos=0,ttl=128,frag=no),icmp(type=8,code=0)"
+        AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt])
+    done
 done
-sort results | uniq -c
-AT_CHECK([sort results | uniq], [0],
-  [Datapath actions: 10
-Datapath actions: 11
+
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' |  sed 's/packets.*actions:1/actions:1/' | strip_ufid | strip_used | sort], [0], [dnl
+flow-dump from non-dpdk interfaces:
+recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:7, bytes:742, used:0.0s, actions:hash(hash_l4(0)),recirc(0x1)
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:10
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11
 ])
+
 OVS_VSWITCHD_STOP
 AT_CLEANUP
 
@@ -421,9 +434,16 @@ OVS_VSWITCHD_START
 add_of_ports br0 1 10 11
 AT_CHECK([ovs-ofctl -O OpenFlow12 add-group br0 'group_id=1234,type=select,bucket=watch_port:10,output:10,bucket=output:11'])
 AT_CHECK([ovs-ofctl -O OpenFlow12 add-flow br0 'ip actions=write_actions(group:1234)'])
-AT_CHECK([ovs-appctl ofproto/trace br0 'in_port=1,dl_src=50:54:00:00:00:07,dl_dst=50:54:00:00:00:07,dl_type=0x0800,nw_src=192.168.0.1,nw_dst=192.168.0.2,nw_proto=1,nw_tos=0,nw_ttl=128,icmp_type=8,icmp_code=0'], [0], [stdout])
-AT_CHECK([tail -1 stdout], [0],
-  [Datapath actions: 11
+
+for d in 0 1 2 3; do
+        pkt="in_port(1),eth(src=50:54:00:00:00:07,dst=50:54:00:00:00:1),eth_type(0x0800),ipv4(src=192.168.0.1,dst=192.168.0.2,proto=1,tos=0,ttl=128,frag=no),icmp(type=8,code=0)"
+        AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt])
+done
+
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' |  sed 's/packets.*actions:1/actions:1/' | strip_ufid | strip_used | sort], [0], [dnl
+flow-dump from non-dpdk interfaces:
+recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:3, bytes:318, used:0.0s, actions:hash(hash_l4(0)),recirc(0x1)
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11
 ])
 OVS_VSWITCHD_STOP
 AT_CLEANUP
@@ -495,16 +515,18 @@ AT_CHECK([ovs-ofctl -O OpenFlow15 add-flow br0 'ip,nw_src=192.168.0.1 actions=gr
 
 # Try a bunch of different flows and make sure that they get distributed
 # at least somewhat.
-for d in 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; do
-    pkt="in_port(1),eth(src=50:54:00:00:00:07,dst=50:54:00:00:00:01),eth_type(0x0800),ipv4(src=192.168.0.1,dst=192.168.1.$d,proto=1,tos=0,ttl=128,frag=no),icmp(type=8,code=0)"
+for d in 0 1 2 3; do
+  for i in 1 2 ; do
+    pkt="in_port(1),eth(src=50:54:00:00:00:07,dst=50:54:00:00:00:1),eth_type(0x0800),ipv4(src=192.168.0.1,dst=192.168.1.$i,proto=1,tos=0,ttl=128,frag=no),icmp(type=8,code=0)"
     AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt])
+  done
 done
 
-AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0x1)/dp_hash(0xXXXX\/0x1)/' | sed 's/packets.*actions:1/actions:1/' | strip_ufid | strip_used | sort], [0], [dnl
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' |  sed 's/packets.*actions:1/actions:1/' | strip_ufid | strip_used | sort], [0], [dnl
 flow-dump from non-dpdk interfaces:
-recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(hash_l4(0)),recirc(0x1)
-recirc_id(0x1),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:10
-recirc_id(0x1),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11
+recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:7, bytes:742, used:0.0s, actions:hash(hash_l4(0)),recirc(0x1)
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:10
+recirc_id(0x1),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), actions:11
 ])
 
 AT_CHECK([ovs-appctl revalidator/purge], [0])
@@ -516,10 +538,10 @@ for d in 0 1 2 3 4 5 6 7 8 9 a b c d e f; do
     AT_CHECK([ovs-appctl netdev-dummy/receive p1 $pkt])
 done
 
-AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0x1)/dp_hash(0xXXXX\/0x1)/' | sed 's/\(actions:1\)[[01]]/\1X/' | strip_ufid | strip_used | sort], [0], [dnl
+AT_CHECK([ovs-appctl dpctl/dump-flows | sed 's/dp_hash(.*\/0xf)/dp_hash(0xXXXX\/0xf)/' | sed 's/\(actions:1\)[[01]]/\1X/' | strip_ufid | strip_used | sort], [0], [dnl
 flow-dump from non-dpdk interfaces:
 recirc_id(0),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(src=192.168.0.1,frag=no), packets:15, bytes:1590, used:0.0s, actions:hash(hash_l4(0)),recirc(0x2)
-recirc_id(0x2),dp_hash(0xXXXX/0x1),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:15, bytes:1590, used:0.0s, actions:1X
+recirc_id(0x2),dp_hash(0xXXXX/0xf),in_port(1),packet_type(ns=0,id=0),eth_type(0x0800),ipv4(frag=no), packets:15, bytes:1590, used:0.0s, actions:1X
 ])
 
 OVS_VSWITCHD_STOP
-- 
1.9.1



More information about the dev mailing list