[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