From 4249b5470e65e1665d448f471356a144accdea47 Mon Sep 17 00:00:00 2001 From: Jeroen van Bemmel Date: Mon, 6 Jul 2015 12:58:24 -0500 Subject: [PATCH] hash: Add symmetric L3/L4 hash functions for multipath, bundle hashing. Signed-off-by: Jeroen van Bemmel [blp@nicira.com made code style fixes, expanded documentation] Signed-off-by: Ben Pfaff --- AUTHORS | 1 + NEWS | 1 + include/openflow/nicira-ext.h | 23 +++++++++++- lib/bundle.c | 4 ++ lib/flow.c | 71 ++++++++++++++++++++++++++++++++++- lib/flow.h | 2 + lib/multipath.c | 4 ++ utilities/ovs-ofctl.8.in | 32 ++++++++++++++-- 8 files changed, 132 insertions(+), 6 deletions(-) diff --git a/AUTHORS b/AUTHORS index 14574a11c..93d7dc5e5 100644 --- a/AUTHORS +++ b/AUTHORS @@ -86,6 +86,7 @@ Jason Kölker jason@koelker.net Jasper Capel jasper@capel.tv Jean Tourrilhes jt@hpl.hp.com Jeremy Stribling strib@nicira.com +Jeroen van Bemmel jvb127@gmail.com Jesse Gross jesse@nicira.com Jing Ai jinga@google.com Joe Perches joe@perches.com diff --git a/NEWS b/NEWS index 59f25527f..b08919b5b 100644 --- a/NEWS +++ b/NEWS @@ -11,6 +11,7 @@ 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' hash functions. v2.4.0 - xx xxx xxxx diff --git a/include/openflow/nicira-ext.h b/include/openflow/nicira-ext.h index 22325aa40..9154800a4 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 ee8079c81..f1b1478e5 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 6bfe73864..366922820 100644 --- a/lib/flow.c +++ b/lib/flow.c @@ -1347,6 +1347,40 @@ 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, + bool 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, + (OVS_FORCE uint32_t) (flow->nw_src ^ flow->nw_dst)); + } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) { + /* IPv6 addresses are 64-bit aligned inside struct flow. */ + const uint64_t *a = ALIGNED_CAST(uint64_t *, flow->ipv6_src.s6_addr); + const uint64_t *b = ALIGNED_CAST(uint64_t *, flow->ipv6_dst.s6_addr); + + for (int 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, + (OVS_FORCE uint16_t) (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) @@ -1414,6 +1448,30 @@ flow_mask_hash_fields(const struct flow *flow, struct flow_wildcards *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, false); + + case NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP: + return flow_hash_symmetric_l3l4(flow, basis, true); + } 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 ""; } } @@ -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 a1c6e9751..97790859b 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, + bool 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 355ef4b47..0a58c062c 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 0a40efa1f..fc5f2921c 100644 --- a/utilities/ovs-ofctl.8.in +++ b/utilities/ovs-ofctl.8.in @@ -1619,8 +1619,32 @@ 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, +\fIfields\fR must be one of the following: +.RS +.IP \fBeth_src\fR +Hashes Ethernet source address only. +.IP \fBsymmetric_l4\fR +Hashes Ethernet source, destination, and type, VLAN ID, IPv4/IPv6 +source, destination, and protocol, and TCP or SCTP (but not UDP) +ports. The hash is computed so that pairs of corresponding flows in +each direction hash to the same value, in environments where L2 paths +are the same in each direction. UDP ports are not included in the +hash to support protocols such as VXLAN that use asymmetric ports in +each direction. +.IP \fBsymmetric_l3l4\fR +Hashes IPv4/IPv6 source, destination, and protocol, and TCP or SCTP +(but not UDP) ports. Like \fBsymmetric_l4\fR, this is a symmetric +hash, but by excluding L2 headers it is more effective in environments +with asymmetric L2 paths (e.g. paths involving VRRP IP addresses on a +router). Not an effective hash function for protocols other than IPv4 +and IPv6, which hash to a constant zero. +.IP \fBsymmetric_l3l4+udp\fR +Like \fBsymmetric_l3l4+udp\fR, but UDP ports are included in the hash. +This is a more effective hash when asymmetric UDP protocols such as +VXLAN are not a consideration. +.RE +.IP +\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 +1657,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 -- 2.20.1