[ovs-dev] V2: Hashing: Add truly symmetric L3+L4 fields option for multipath and bundle hashing

Jeroen van Bemmel jvb127 at gmail.com
Sat Jul 4 21:47:37 UTC 2015


The symmetric_l4 function implements a hash over various fields
including L2 fields such as ethernet source and destination MAC.
Inspite of its name, there are situations in which this hash does not
yield symmetric results ( e.g. when using VRRP, where the router
receives packets on a virtual MAC but responds from its physical MAC )

This patch (v2) adds new 'symmetric_l3l4' and 'symmetric_l3l4+udp' functions
using murmur3 hashing. They are identical, except that the latter also includes
UDP src/dst ports in the hash.

Signed-off-by:Jeroen van Bemmel <jvb127 at gmail.com>
Suggested-by: Ben Pfaff <blp at nicira.com>

diff --git a/NEWS b/NEWS
index 59f2552..5d48208 100644
--- a/NEWS
+++ b/NEWS
@@ -11,6 +11,11 @@ Post-v2.4.0
      * OpenFlow 1.4+ OFPMP_TABLE_DESC is now implemented.
    - Support for matching and generating options with Geneve tunnels.
    - Support Multicast Listener Discovery (MLDv1 and MLDv2).
+   - Add 'symmetric_l3l4' and 'symmetric_l3l4+udp' as fields options for
+     multipath and bundle, to enable truly symmetric hashing excluding
+     L2 headers, with optional inclusion of UDP ports. The original
+     'symmetric_l3' remains available, and is still used internally for
+     backwards compatibility


 v2.4.0 - xx xxx xxxx
diff --git a/include/openflow/nicira-ext.h b/include/openflow/nicira-ext.h
index 22325aa..9154800 100644
--- a/include/openflow/nicira-ext.h
+++ b/include/openflow/nicira-ext.h
@@ -109,7 +109,28 @@ enum nx_hash_fields {
      *  - NXM_OF_IP_SRC / NXM_OF_IP_DST
      *  - NXM_OF_TCP_SRC / NXM_OF_TCP_DST
      */
-    NX_HASH_FIELDS_SYMMETRIC_L4
+    NX_HASH_FIELDS_SYMMETRIC_L4,
+
+    /* L3+L4 only, including the following fields:
+     *
+     *  - NXM_OF_IP_PROTO
+     *  - NXM_OF_IP_SRC / NXM_OF_IP_DST
+     *  - NXM_OF_SCTP_SRC / NXM_OF_SCTP_DST
+     *  - NXM_OF_TCP_SRC / NXM_OF_TCP_DST
+     */
+    NX_HASH_FIELDS_SYMMETRIC_L3L4,
+
+    /* L3+L4 only with UDP ports, including the following fields:
+     *
+     *  - NXM_OF_IP_PROTO
+     *  - NXM_OF_IP_SRC / NXM_OF_IP_DST
+     *  - NXM_OF_SCTP_SRC / NXM_OF_SCTP_DST
+     *  - NXM_OF_TCP_SRC / NXM_OF_TCP_DST
+     *  - NXM_OF_UDP_SRC / NXM_OF_UDP_DST
+     */
+    NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP
+
+
 };

 /* This command enables or disables an Open vSwitch extension that allows a
diff --git a/lib/bundle.c b/lib/bundle.c
index ee8079c..f1b1478 100644
--- a/lib/bundle.c
+++ b/lib/bundle.c
@@ -186,6 +186,10 @@ bundle_parse__(const char *s, char **save_ptr,
         bundle->fields = NX_HASH_FIELDS_ETH_SRC;
     } else if (!strcasecmp(fields, "symmetric_l4")) {
         bundle->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
+    } else if (!strcasecmp(fields, "symmetric_l3l4")) {
+        bundle->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4;
+    } else if (!strcasecmp(fields, "symmetric_l3l4+udp")) {
+        bundle->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP;
     } else {
         return xasprintf("%s: unknown fields `%s'", s, fields);
     }
diff --git a/lib/flow.c b/lib/flow.c
index 6bfe738..5d518de 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1347,6 +1347,41 @@ flow_hash_symmetric_l4(const struct flow *flow,
uint32_t basis)
     return jhash_bytes(&fields, sizeof fields, basis);
 }

+/* Hashes 'flow' based on its L3 through L4 protocol information */
+uint32_t
+flow_hash_symmetric_l3l4(const struct flow *flow, uint32_t basis,
+                         int inc_udp_ports )
+{
+    uint32_t hash = basis;
+
+    /* UDP source and destination port are also taken into account */
+    if ( flow->dl_type == htons(ETH_TYPE_IP)) {
+        hash = hash_add( hash, flow->nw_src ^ flow->nw_dst );
+    } else if ( flow->dl_type == htons(ETH_TYPE_IPV6)) {
+        //
+        // IPv6 addresses are 64-bit aligned
+        //
+        const uint64_t *a = (const uint64_t*) &flow->ipv6_src.s6_addr[0];
+        const uint64_t *b = (const uint64_t*) &flow->ipv6_dst.s6_addr[0];
+        int i;
+
+        for (i=0; i<4; ++i) {
+            hash = hash_add64( hash, a[i] ^ b[i] );
+        }
+    } else {
+        // Cannot hash non-IP flows
+        return 0;
+    }
+
+    hash = hash_add( hash, flow->nw_proto );
+    if ( flow->nw_proto == IPPROTO_TCP || flow->nw_proto == IPPROTO_SCTP ||
+         ( inc_udp_ports && (flow->nw_proto == IPPROTO_UDP))) {
+        hash = hash_add( hash, flow->tp_src ^ flow->tp_dst );
+    }
+
+    return hash_finish( hash, basis );
+}
+
 /* Initialize a flow with random fields that matter for nx_hash_fields. */
 void
 flow_random_hash_fields(struct flow *flow)
@@ -1409,11 +1444,34 @@ flow_mask_hash_fields(const struct flow *flow,
struct flow_wildcards *wc,
         }
         if (is_ip_any(flow)) {
             memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
+            // XXX hash does not include UDP ports, is this correct?
             flow_unwildcard_tp_ports(flow, wc);
         }
         wc->masks.vlan_tci |= htons(VLAN_VID_MASK | VLAN_CFI);
         break;

+    case NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP:
+        if ( is_ip_any(flow) && ( flow->nw_proto == IPPROTO_UDP ) ) {
+            memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
+            memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
+        }
+        // no break
+    case NX_HASH_FIELDS_SYMMETRIC_L3L4:
+            if (flow->dl_type == htons(ETH_TYPE_IP)) {
+                memset(&wc->masks.nw_src, 0xff, sizeof wc->masks.nw_src);
+                memset(&wc->masks.nw_dst, 0xff, sizeof wc->masks.nw_dst);
+            } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
+                memset(&wc->masks.ipv6_src, 0xff, sizeof wc->masks.ipv6_src);
+                memset(&wc->masks.ipv6_dst, 0xff, sizeof wc->masks.ipv6_dst);
+            } else break; // non-IP flow
+
+            memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
+            if (( flow->nw_proto == IPPROTO_TCP )||( flow->nw_proto
== IPPROTO_SCTP )) {
+                memset(&wc->masks.tp_src, 0xff, sizeof wc->masks.tp_src);
+                memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
+            }
+            break;
+
     default:
         OVS_NOT_REACHED();
     }
@@ -1431,6 +1489,13 @@ flow_hash_fields(const struct flow *flow, enum
nx_hash_fields fields,

     case NX_HASH_FIELDS_SYMMETRIC_L4:
         return flow_hash_symmetric_l4(flow, basis);
+
+    case NX_HASH_FIELDS_SYMMETRIC_L3L4:
+        return flow_hash_symmetric_l3l4(flow, basis, 0);
+
+    case NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP:
+        return flow_hash_symmetric_l3l4(flow, basis, 1);
+
     }

     OVS_NOT_REACHED();
@@ -1443,6 +1508,8 @@ flow_hash_fields_to_str(enum nx_hash_fields fields)
     switch (fields) {
     case NX_HASH_FIELDS_ETH_SRC: return "eth_src";
     case NX_HASH_FIELDS_SYMMETRIC_L4: return "symmetric_l4";
+    case NX_HASH_FIELDS_SYMMETRIC_L3L4: return "symmetric_l3l4";
+    case NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP: return "symmetric_l3l4+udp";
     default: return "<unknown>";
     }
 }
@@ -1452,7 +1519,9 @@ bool
 flow_hash_fields_valid(enum nx_hash_fields fields)
 {
     return fields == NX_HASH_FIELDS_ETH_SRC
-        || fields == NX_HASH_FIELDS_SYMMETRIC_L4;
+        || fields == NX_HASH_FIELDS_SYMMETRIC_L4
+        || fields == NX_HASH_FIELDS_SYMMETRIC_L3L4
+        || fields == NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP;
 }

 /* Returns a hash value for the bits of 'flow' that are active based on
diff --git a/lib/flow.h b/lib/flow.h
index a1c6e97..ea73e01 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -341,6 +341,8 @@ bool flow_wildcards_equal(const struct flow_wildcards *,
                           const struct flow_wildcards *);
 uint32_t flow_hash_5tuple(const struct flow *flow, uint32_t basis);
 uint32_t flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis);
+uint32_t flow_hash_symmetric_l3l4(const struct flow *flow, uint32_t basis,
+                         int inc_udp_ports );

 /* Initialize a flow with random fields that matter for nx_hash_fields. */
 void flow_random_hash_fields(struct flow *);
diff --git a/lib/multipath.c b/lib/multipath.c
index 355ef4b..0a58c06 100644
--- a/lib/multipath.c
+++ b/lib/multipath.c
@@ -162,6 +162,10 @@ multipath_parse__(struct ofpact_multipath *mp,
const char *s_, char *s)
         mp->fields = NX_HASH_FIELDS_ETH_SRC;
     } else if (!strcasecmp(fields, "symmetric_l4")) {
         mp->fields = NX_HASH_FIELDS_SYMMETRIC_L4;
+    } else if (!strcasecmp(fields, "symmetric_l3l4")) {
+        mp->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4;
+    } else if (!strcasecmp(fields, "symmetric_l3l4+udp")) {
+        mp->fields = NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP;
     } else {
         return xasprintf("%s: unknown fields `%s'", s_, fields);
     }
diff --git a/utilities/ovs-ofctl.8.in b/utilities/ovs-ofctl.8.in
index 0a40efa..84d2dd5 100644
--- a/utilities/ovs-ofctl.8.in
+++ b/utilities/ovs-ofctl.8.in
@@ -1619,8 +1619,11 @@ numbered 0 through \fIn_links\fR minus 1, and
stores the link into
 \fIdst\fB[\fIstart\fB..\fIend\fB]\fR, which must be an NXM field as
 described above.
 .IP
-Currently, \fIfields\fR must be either \fBeth_src\fR or
-\fBsymmetric_l4\fR and \fIalgorithm\fR must be one of \fBmodulo_n\fR,
+Currently, \fIfields\fR must be either \fBeth_src\fR,
\fBsymmetric_l4\fR, \fBsymmetric_l3l4\fR, or \fBsymmetric_l3l4+udp\fR.
+\fBsymmetric_l4\fR includes L2 headers but not UDP ports, which may
not result in symmetric flows in some situations.
+\fBsymmetric_l3l4\fR only includes L3 and L4 headers but not UDP
ports, and \fBsymmetric_l3l4+udp\fR includes UDP ports too.
+
+\fIalgorithm\fR must be one of \fBmodulo_n\fR,
 \fBhash_threshold\fR, \fBhrw\fR, and \fBiter_hash\fR.  Only
 the \fBiter_hash\fR algorithm uses \fIarg\fR.
 .IP
@@ -1633,8 +1636,8 @@ slaves represented as \fIslave_type\fR.
Currently the only supported
 \fIslave_type\fR is \fBofport\fR.  Thus, each \fIs1\fR through \fIsN\fR should
 be an OpenFlow port number. Outputs to the selected slave.
 .IP
-Currently, \fIfields\fR must be either \fBeth_src\fR or \fBsymmetric_l4\fR and
-\fIalgorithm\fR must be one of \fBhrw\fR and \fBactive_backup\fR.
+Currently, \fIfields\fR must be either \fBeth_src\fR,
\fBsymmetric_l4\fR, \fBsymmetric_l3l4\fR, or \fBsymmetric_l3l4+udp\fR,
+and \fIalgorithm\fR must be one of \fBhrw\fR and \fBactive_backup\fR.
 .IP
 Example: \fBbundle(eth_src,0,hrw,ofport,slaves:4,8)\fR uses an Ethernet source
 hash with basis 0, to select between OpenFlow ports 4 and 8 using the Highest



More information about the dev mailing list