Skip to contentSkip to conversation

Allow configuration of multipath hash seed

PATCH Applied Petr Machata 4 participants 9 messages Jun 7, 2024 – Jun 13, 2024

Subsystems (6)
lore
Share & tools
lore

Petr Machata

author maintainer
#0 lore raw

v2 cover Allow configuration of multipath hash seed

Let me just quote the commit message of patch #2 here to inform the motivation and some of the implementation:

When calculating hashes for the purpose of multipath forwarding, both IPv4 and IPv6 code currently fall back on flow_hash_from_keys(). That uses a randomly-generated seed. That's a fine choice by default, but unfortunately some deployments may need a tighter control over the seed used.

In this patchset, make the seed configurable by adding a new sysctl key, net.ipv4.fib_multipath_hash_seed to control the seed. This seed is used specifically for multipath forwarding and not for the other concerns that flow_hash_from_keys() is used for, such as queue selection. Expose the knob as sysctl because other such settings, such as headers to hash, are also handled that way.

Despite being placed in the net.ipv4 namespace, the multipath seed sysctl is used for both IPv4 and IPv6, similarly to e.g. a number of TCP variables. Like those, the multipath hash seed is a per-netns variable.

The seed used by flow_hash_from_keys() is a 128-bit quantity. However it seems that usually the seed is a much more modest value. 32 bits seem typical (Cisco, Cumulus), some systems go even lower. For that reason, and to decouple the user interface from implementation details, go with a 32-bit quantity, which is then quadruplicated to form the siphash key.

One example of use of this interface is avoiding hash polarization, where two ECMP routers, one behind the other, happen to make consistent hashing decisions, and as a result, part of the ECMP space of the latter router is never used. Another is a load balancer where several machines forward traffic to one of a number of leaves, and the forwarding decisions need to be made consistently. (This is a case of a desired hash polarization, mentioned e.g. in chapter 6.3 of [0].)

There has already been a proposal to include a hash seed control interface in the past[1].

- Patches #1-#2 contain the substance of the work
- Patch #3 is an mlxsw offload
- Patches #4 and #5 are a selftest

[0] https://www.usenix.org/system/files/conference/nsdi18/nsdi18-araujo.pdf
[1] https://lore.kernel.org/netdev/YIlVpYMCn%2F8WfE1P@rnd/

v2:
- Patch #2:
- Instead of precomputing the siphash key, construct it in place of use thus obviating the need to use RCU.
- Instead of dispatching to the flow dissector for cases where user seed is 0, maintain a separate random seed. Initialize it early so that we can avoid a branch at the seed reader.
- In documentation, s/only valid/only present/ (when CONFIG_IP_ROUTE_MULTIPATH). Also mention the algorithm is unspecified and unstable in principle.
- Patch #3:
- Update to match changes in patch #2.
- Patch #4:
- New patch.
- Patch #5:
- Do not set seed on test init and run the stability tests first to catch the cases of a missed pernet seed init.

Petr Machata (5):
net: ipv4,ipv6: Pass multipath hash computation through a helper
net: ipv4: Add a sysctl to set multipath hash seed
mlxsw: spectrum_router: Apply user-defined multipath hash seed
selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()
selftests: forwarding: router_mpath_hash: Add a new selftest

 Documentation/networking/ip-sysctl.rst        |  14 +
 .../ethernet/mellanox/mlxsw/spectrum_router.c |   6 +-
 include/net/flow_dissector.h                  |   2 +
 include/net/ip_fib.h                          |  28 ++
 include/net/netns/ipv4.h                      |   8 +
 net/core/flow_dissector.c                     |   7 +
 net/ipv4/route.c                              |  12 +-
 net/ipv4/sysctl_net_ipv4.c                    |  66 ++++
 net/ipv6/route.c                              |  12 +-
 .../testing/selftests/net/forwarding/Makefile |   1 +
 tools/testing/selftests/net/forwarding/lib.sh |   9 +-
 .../net/forwarding/router_mpath_seed.sh       | 333 ++++++++++++++++++
 12 files changed, 484 insertions(+), 14 deletions(-)
 create mode 100755 tools/testing/selftests/net/forwarding/router_mpath_seed.sh
Signature · 1 line
2.45.0
author maintainer
#1 lore raw

PATCH v2 1/5 net: ipv4,ipv6: Pass multipath hash computation through a helper

The following patches will add a sysctl to control multipath hash seed. In order to centralize the hash computation, add a helper, fib_multipath_hash_from_keys(), and have all IPv4 and IPv6 route.c invocations of flow_hash_from_keys() go through this helper instead.

---
 include/net/ip_fib.h |  7 +++++++
 net/ipv4/route.c     | 12 ++++++------
 net/ipv6/route.c     | 12 ++++++------
 3 files changed, 19 insertions(+), 12 deletions(-)
include/net/ip_fib.h +7 -0
index 9b2f69ba5e49..b8b3c07e8f7b 100644
@@ -521,6 +521,13 @@ void fib_nhc_update_mtu(struct fib_nh_common *nhc, u32 new, u32 orig);
 int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
 		       const struct sk_buff *skb, struct flow_keys *flkeys);
 #endif
+
+static inline u32 fib_multipath_hash_from_keys(const struct net *net,
+					       struct flow_keys *keys)
+{
+	return flow_hash_from_keys(keys);
+}
+
 int fib_check_nh(struct net *net, struct fib_nh *nh, u32 table, u8 scope,
 		 struct netlink_ext_ack *extack);
 void fib_select_multipath(struct fib_result *res, int hash);
net/ipv4/route.c +6 -6
index cb0bdf34ed50..54512acbead7 100644
@@ -1923,7 +1923,7 @@ static u32 fib_multipath_custom_hash_outer(const struct net *net,
 		hash_keys.ports.dst = keys.ports.dst;
 
 	*p_has_inner = !!(keys.control.flags & FLOW_DIS_ENCAPSULATION);
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 static u32 fib_multipath_custom_hash_inner(const struct net *net,
@@ -1972,7 +1972,7 @@ static u32 fib_multipath_custom_hash_inner(const struct net *net,
 	if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_DST_PORT)
 		hash_keys.ports.dst = keys.ports.dst;
 
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 static u32 fib_multipath_custom_hash_skb(const struct net *net,
@@ -2009,7 +2009,7 @@ static u32 fib_multipath_custom_hash_fl4(const struct net *net,
 	if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_PORT)
 		hash_keys.ports.dst = fl4->fl4_dport;
 
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 /* if skb is set it will be used and fl4 can be NULL */
@@ -2030,7 +2030,7 @@ int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
 			hash_keys.addrs.v4addrs.src = fl4->saddr;
 			hash_keys.addrs.v4addrs.dst = fl4->daddr;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 1:
 		/* skb is currently provided only when forwarding */
@@ -2064,7 +2064,7 @@ int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
 			hash_keys.ports.dst = fl4->fl4_dport;
 			hash_keys.basic.ip_proto = fl4->flowi4_proto;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 2:
 		memset(&hash_keys, 0, sizeof(hash_keys));
@@ -2095,7 +2095,7 @@ int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
 			hash_keys.addrs.v4addrs.src = fl4->saddr;
 			hash_keys.addrs.v4addrs.dst = fl4->daddr;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 3:
 		if (skb)
net/ipv6/route.c +6 -6
index ad5fff5a210c..1916de615398 100644
@@ -2372,7 +2372,7 @@ static u32 rt6_multipath_custom_hash_outer(const struct net *net,
 		hash_keys.ports.dst = keys.ports.dst;
 
 	*p_has_inner = !!(keys.control.flags & FLOW_DIS_ENCAPSULATION);
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 static u32 rt6_multipath_custom_hash_inner(const struct net *net,
@@ -2421,7 +2421,7 @@ static u32 rt6_multipath_custom_hash_inner(const struct net *net,
 	if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_DST_PORT)
 		hash_keys.ports.dst = keys.ports.dst;
 
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 static u32 rt6_multipath_custom_hash_skb(const struct net *net,
@@ -2460,7 +2460,7 @@ static u32 rt6_multipath_custom_hash_fl6(const struct net *net,
 	if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_PORT)
 		hash_keys.ports.dst = fl6->fl6_dport;
 
-	return flow_hash_from_keys(&hash_keys);
+	return fib_multipath_hash_from_keys(net, &hash_keys);
 }
 
 /* if skb is set it will be used and fl6 can be NULL */
@@ -2482,7 +2482,7 @@ u32 rt6_multipath_hash(const struct net *net, const struct flowi6 *fl6,
 			hash_keys.tags.flow_label = (__force u32)flowi6_get_flowlabel(fl6);
 			hash_keys.basic.ip_proto = fl6->flowi6_proto;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 1:
 		if (skb) {
@@ -2514,7 +2514,7 @@ u32 rt6_multipath_hash(const struct net *net, const struct flowi6 *fl6,
 			hash_keys.ports.dst = fl6->fl6_dport;
 			hash_keys.basic.ip_proto = fl6->flowi6_proto;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 2:
 		memset(&hash_keys, 0, sizeof(hash_keys));
@@ -2551,7 +2551,7 @@ u32 rt6_multipath_hash(const struct net *net, const struct flowi6 *fl6,
 			hash_keys.tags.flow_label = (__force u32)flowi6_get_flowlabel(fl6);
 			hash_keys.basic.ip_proto = fl6->flowi6_proto;
 		}
-		mhash = flow_hash_from_keys(&hash_keys);
+		mhash = fib_multipath_hash_from_keys(net, &hash_keys);
 		break;
 	case 3:
 		if (skb)
Signature · 1 line
2.45.0
author maintainer
#2 lore raw

PATCH v2 2/5 net: ipv4: Add a sysctl to set multipath hash seed

In reply to Petr Machata

When calculating hashes for the purpose of multipath forwarding, both IPv4 and IPv6 code currently fall back on flow_hash_from_keys(). That uses a randomly-generated seed. That's a fine choice by default, but unfortunately some deployments may need a tighter control over the seed used.

In this patch, make the seed configurable by adding a new sysctl key, net.ipv4.fib_multipath_hash_seed to control the seed. This seed is used specifically for multipath forwarding and not for the other concerns that flow_hash_from_keys() is used for, such as queue selection. Expose the knob as sysctl because other such settings, such as headers to hash, are also handled that way. Like those, the multipath hash seed is a per-netns variable.

Despite being placed in the net.ipv4 namespace, the multipath seed sysctl is used for both IPv4 and IPv6, similarly to e.g. a number of TCP variables.

The seed used by flow_hash_from_keys() is a 128-bit quantity. However it seems that usually the seed is a much more modest value. 32 bits seem typical (Cisco, Cumulus), some systems go even lower. For that reason, and to decouple the user interface from implementation details, go with a 32-bit quantity, which is then quadruplicated to form the siphash key.

---
Cc: Jonathan Corbet <[email protected]>
Cc: [email protected]
Cc: Simon Horman <[email protected]>

Notes:
v2:
- Instead of precomputing the siphash key, construct it in place of use thus obviating the need to use RCU.
- Instead of dispatching to the flow dissector for cases where user seed is 0, maintain a separate random seed. Initialize it early so that we can avoid a branch at the seed reader.
- In documentation, s/only valid/only present/ (when CONFIG_IP_ROUTE_MULTIPATH). Also mention the algorithm is unspecified and unstable in principle.

 Documentation/networking/ip-sysctl.rst | 14 ++++++
 include/net/flow_dissector.h           |  2 +
 include/net/ip_fib.h                   | 23 ++++++++-
 include/net/netns/ipv4.h               |  8 ++++
 net/core/flow_dissector.c              |  7 +++
 net/ipv4/sysctl_net_ipv4.c             | 66 ++++++++++++++++++++++++++
 6 files changed, 119 insertions(+), 1 deletion(-)
Documentation/networking/ip-sysctl.rst +14 -0
index 6e99eccdb837..3616389c8c2d 100644
@@ -131,6 +131,20 @@ fib_multipath_hash_fields - UNSIGNED INTEGER
 
 	Default: 0x0007 (source IP, destination IP and IP protocol)
 
+fib_multipath_hash_seed - UNSIGNED INTEGER
+	The seed value used when calculating hash for multipath routes. Applies
+	to both IPv4 and IPv6 datapath. Only present for kernels built with
+	CONFIG_IP_ROUTE_MULTIPATH enabled.
+
+	When set to 0, the seed value used for multipath routing defaults to an
+	internal random-generated one.
+
+	The actual hashing algorithm is not specified -- there is no guarantee
+	that a next hop distribution effected by a given seed will keep stable
+	across kernel versions.
+
+	Default: 0 (random)
+
 fib_sync_mem - UNSIGNED INTEGER
 	Amount of dirty memory from fib entries that can be backlogged before
 	synchronize_rcu is forced.
include/net/flow_dissector.h +2 -0
index 99626475c3f4..3e47e123934d 100644
@@ -442,6 +442,8 @@ static inline bool flow_keys_have_l4(const struct flow_keys *keys)
 }
 
 u32 flow_hash_from_keys(struct flow_keys *keys);
+u32 flow_hash_from_keys_seed(struct flow_keys *keys,
+			     const siphash_key_t *keyval);
 void skb_flow_get_icmp_tci(const struct sk_buff *skb,
 			   struct flow_dissector_key_icmp *key_icmp,
 			   const void *data, int thoff, int hlen);
include/net/ip_fib.h +22 -1
index b8b3c07e8f7b..6e7984bfb986 100644
@@ -520,13 +520,34 @@ void fib_nhc_update_mtu(struct fib_nh_common *nhc, u32 new, u32 orig);
 #ifdef CONFIG_IP_ROUTE_MULTIPATH
 int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
 		       const struct sk_buff *skb, struct flow_keys *flkeys);
-#endif
 
+static void
+fib_multipath_hash_construct_key(siphash_key_t *key, u32 mp_seed)
+{
+	u64 mp_seed_64 = mp_seed;
+
+	key->key[0] = (mp_seed_64 << 32) | mp_seed_64;
+	key->key[1] = key->key[0];
+}
+
+static inline u32 fib_multipath_hash_from_keys(const struct net *net,
+					       struct flow_keys *keys)
+{
+	siphash_aligned_key_t hash_key;
+	u32 mp_seed;
+
+	mp_seed = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_seed).mp_seed;
+	fib_multipath_hash_construct_key(&hash_key, mp_seed);
+
+	return flow_hash_from_keys_seed(keys, &hash_key);
+}
+#else
 static inline u32 fib_multipath_hash_from_keys(const struct net *net,
 					       struct flow_keys *keys)
 {
 	return flow_hash_from_keys(keys);
 }
+#endif
 
 int fib_check_nh(struct net *net, struct fib_nh *nh, u32 table, u8 scope,
 		 struct netlink_ext_ack *extack);
include/net/netns/ipv4.h +8 -0
index a91bb971f901..5fcd61ada622 100644
@@ -40,6 +40,13 @@ struct inet_timewait_death_row {
 
 struct tcp_fastopen_context;
 
+#ifdef CONFIG_IP_ROUTE_MULTIPATH
+struct sysctl_fib_multipath_hash_seed {
+	u32 user_seed;
+	u32 mp_seed;
+};
+#endif
+
 struct netns_ipv4 {
 	/* Cacheline organization can be found documented in
 	 * Documentation/networking/net_cachelines/netns_ipv4_sysctl.rst.
@@ -246,6 +253,7 @@ struct netns_ipv4 {
 #endif
 #endif
 #ifdef CONFIG_IP_ROUTE_MULTIPATH
+	struct sysctl_fib_multipath_hash_seed sysctl_fib_multipath_hash_seed;
 	u32 sysctl_fib_multipath_hash_fields;
 	u8 sysctl_fib_multipath_use_neigh;
 	u8 sysctl_fib_multipath_hash_policy;
net/core/flow_dissector.c +7 -0
index 59fe46077b3c..fcd584588baa 100644
@@ -1806,6 +1806,13 @@ u32 flow_hash_from_keys(struct flow_keys *keys)
 }
 EXPORT_SYMBOL(flow_hash_from_keys);
 
+u32 flow_hash_from_keys_seed(struct flow_keys *keys,
+			     const siphash_key_t *keyval)
+{
+	return __flow_hash_from_keys(keys, keyval);
+}
+EXPORT_SYMBOL(flow_hash_from_keys_seed);
+
 static inline u32 ___skb_get_hash(const struct sk_buff *skb,
 				  struct flow_keys *keys,
 				  const siphash_key_t *keyval)
net/ipv4/sysctl_net_ipv4.c +66 -0

90 lines not on this page · raw message

Signature · 1 line
2.45.0
author maintainer
#3 lore raw

PATCH v2 3/5 mlxsw: spectrum_router: Apply user-defined multipath hash seed

In reply to Petr Machata

When Spectrum machines compute hash for the purposes of ECMP routing, they use a seed specified through RECR_v2 (Router ECMP Configuration Register). Up until now mlxsw computed the seed by hashing the machine's base MAC. Now that we can optionally have a user-provided seed, use that if possible.

---

Notes:
v2:
- Update to match changes in patch #2.

 drivers/net/ethernet/mellanox/mlxsw/spectrum_router.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
drivers/net/ethernet/mellanox/mlxsw/spectrum_router.c +5 -1
index 40ba314fbc72..800dfb64ec83 100644
@@ -11450,12 +11450,16 @@ static int mlxsw_sp_mp_hash_init(struct mlxsw_sp *mlxsw_sp)
 {
 	bool old_inc_parsing_depth, new_inc_parsing_depth;
 	struct mlxsw_sp_mp_hash_config config = {};
+	struct net *net = mlxsw_sp_net(mlxsw_sp);
 	char recr2_pl[MLXSW_REG_RECR2_LEN];
 	unsigned long bit;
 	u32 seed;
 	int err;
 
-	seed = jhash(mlxsw_sp->base_mac, sizeof(mlxsw_sp->base_mac), 0);
+	seed = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_seed).user_seed;
+	if (!seed)
+		seed = jhash(mlxsw_sp->base_mac, sizeof(mlxsw_sp->base_mac), 0);
+
 	mlxsw_reg_recr2_pack(recr2_pl, seed);
 	mlxsw_sp_mp4_hash_init(mlxsw_sp, &config);
 	mlxsw_sp_mp6_hash_init(mlxsw_sp, &config);
Signature · 1 line
2.45.0
author maintainer
#4 lore raw

PATCH v2 4/5 selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()

In reply to Petr Machata

In order to be able to save the current value of a sysctl without changing it, split the relevant bit out of sysctl_set() into a new helper.

---
Cc: Shuah Khan <[email protected]>
Cc: [email protected]

Notes:
v2:
- New patch.

 tools/testing/selftests/net/forwarding/lib.sh | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
tools/testing/selftests/net/forwarding/lib.sh +8 -1
index eabbdf00d8ca..9086d2015296 100644
@@ -1134,12 +1134,19 @@ bridge_ageing_time_get()
 }
 
 declare -A SYSCTL_ORIG
+sysctl_save()
+{
+	local key=$1; shift
+
+	SYSCTL_ORIG[$key]=$(sysctl -n $key)
+}
+
 sysctl_set()
 {
 	local key=$1; shift
 	local value=$1; shift
 
-	SYSCTL_ORIG[$key]=$(sysctl -n $key)
+	sysctl_save "$key"
 	sysctl -qw $key="$value"
 }
 
Signature · 1 line
2.45.0
author maintainer
#5 lore raw

PATCH v2 5/5 selftests: forwarding: router_mpath_hash: Add a new selftest

In reply to Petr Machata

Add a selftest that exercises the sysctl added in the previous patches.

Test that set/get works as expected; that across seeds we eventually hit all NHs (test_mpath_seed_*); and that a given seed keeps hitting the same NHs even across seed changes (test_mpath_seed_stability_*).

---
Cc: Shuah Khan <[email protected]>
Cc: [email protected]

Notes:
v2:
- Do not set seed on test init and run the stability tests first to catch the cases of a missed pernet seed init.

 .../testing/selftests/net/forwarding/Makefile |   1 +
 .../net/forwarding/router_mpath_seed.sh       | 333 ++++++++++++++++++
 2 files changed, 334 insertions(+)
 create mode 100755 tools/testing/selftests/net/forwarding/router_mpath_seed.sh
tools/testing/selftests/net/forwarding/Makefile +1 -0
index fa7b59ff4029..99576d7ecbf6 100644
@@ -70,6 +70,7 @@ TEST_PROGS = bridge_fdb_learning_limit.sh \
 	router_broadcast.sh \
 	router_mpath_nh_res.sh \
 	router_mpath_nh.sh \
+	router_mpath_seed.sh \
 	router_multicast.sh \
 	router_multipath.sh \
 	router_nh.sh \
tools/testing/selftests/net/forwarding/router_mpath_seed.sh new file +333 -0

333 lines not on this page · raw message

Signature · 1 line
2.45.0
Reviewed-by on the v2 series
#6 lore raw
In reply to Petr Machata
Quoted 71 lines · Petr Machata

Let me just quote the commit message of patch #2 here to inform the motivation and some of the implementation:

When calculating hashes for the purpose of multipath forwarding, both IPv4 and IPv6 code currently fall back on flow_hash_from_keys(). That uses a randomly-generated seed. That's a fine choice by default, but unfortunately some deployments may need a tighter control over the seed used.

In this patchset, make the seed configurable by adding a new sysctl key, net.ipv4.fib_multipath_hash_seed to control the seed. This seed is used specifically for multipath forwarding and not for the other concerns that flow_hash_from_keys() is used for, such as queue selection. Expose the knob as sysctl because other such settings, such as headers to hash, are also handled that way.

Despite being placed in the net.ipv4 namespace, the multipath seed sysctl is used for both IPv4 and IPv6, similarly to e.g. a number of TCP variables. Like those, the multipath hash seed is a per-netns variable.

The seed used by flow_hash_from_keys() is a 128-bit quantity. However it seems that usually the seed is a much more modest value. 32 bits seem typical (Cisco, Cumulus), some systems go even lower. For that reason, and to decouple the user interface from implementation details, go with a 32-bit quantity, which is then quadruplicated to form the siphash key.

One example of use of this interface is avoiding hash polarization, where two ECMP routers, one behind the other, happen to make consistent hashing decisions, and as a result, part of the ECMP space of the latter router is never used. Another is a load balancer where several machines forward traffic to one of a number of leaves, and the forwarding decisions need to be made consistently. (This is a case of a desired hash polarization, mentioned e.g. in chapter 6.3 of [0].)

There has already been a proposal to include a hash seed control interface in the past[1].

- Patches #1-#2 contain the substance of the work
- Patch #3 is an mlxsw offload
- Patches #4 and #5 are a selftest

[0] https://www.usenix.org/system/files/conference/nsdi18/nsdi18-araujo.pdf
[1] https://lore.kernel.org/netdev/YIlVpYMCn%2F8WfE1P@rnd/

v2:
- Patch #2:
- Instead of precomputing the siphash key, construct it in place of use thus obviating the need to use RCU.
- Instead of dispatching to the flow dissector for cases where user seed is 0, maintain a separate random seed. Initialize it early so that we can avoid a branch at the seed reader.
- In documentation, s/only valid/only present/ (when CONFIG_IP_ROUTE_MULTIPATH). Also mention the algorithm is unspecified and unstable in principle.
- Patch #3:
- Update to match changes in patch #2.
- Patch #4:
- New patch.
- Patch #5:
- Do not set seed on test init and run the stability tests first to catch the cases of a missed pernet seed init.

Petr Machata (5):
net: ipv4,ipv6: Pass multipath hash computation through a helper
net: ipv4: Add a sysctl to set multipath hash seed
mlxsw: spectrum_router: Apply user-defined multipath hash seed
selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()
selftests: forwarding: router_mpath_hash: Add a new selftest

Quoted 15 lines
 Documentation/networking/ip-sysctl.rst        |  14 +
 .../ethernet/mellanox/mlxsw/spectrum_router.c |   6 +-
 include/net/flow_dissector.h                  |   2 +
 include/net/ip_fib.h                          |  28 ++
 include/net/netns/ipv4.h                      |   8 +
 net/core/flow_dissector.c                     |   7 +
 net/ipv4/route.c                              |  12 +-
 net/ipv4/sysctl_net_ipv4.c                    |  66 ++++
 net/ipv6/route.c                              |  12 +-
 .../testing/selftests/net/forwarding/Makefile |   1 +
 tools/testing/selftests/net/forwarding/lib.sh |   9 +-
 .../net/forwarding/router_mpath_seed.sh       | 333 ++++++++++++++++++
 12 files changed, 484 insertions(+), 14 deletions(-)
 create mode 100755 tools/testing/selftests/net/forwarding/router_mpath_seed.sh

Looks good to me, thank you!
For the set,

maintainer Reviewed-by on the v2 series
#7 lore raw
In reply to Petr Machata
Quoted 71 lines · Petr Machata

Let me just quote the commit message of patch #2 here to inform the motivation and some of the implementation:

When calculating hashes for the purpose of multipath forwarding, both IPv4 and IPv6 code currently fall back on flow_hash_from_keys(). That uses a randomly-generated seed. That's a fine choice by default, but unfortunately some deployments may need a tighter control over the seed used.

In this patchset, make the seed configurable by adding a new sysctl key, net.ipv4.fib_multipath_hash_seed to control the seed. This seed is used specifically for multipath forwarding and not for the other concerns that flow_hash_from_keys() is used for, such as queue selection. Expose the knob as sysctl because other such settings, such as headers to hash, are also handled that way.

Despite being placed in the net.ipv4 namespace, the multipath seed sysctl is used for both IPv4 and IPv6, similarly to e.g. a number of TCP variables. Like those, the multipath hash seed is a per-netns variable.

The seed used by flow_hash_from_keys() is a 128-bit quantity. However it seems that usually the seed is a much more modest value. 32 bits seem typical (Cisco, Cumulus), some systems go even lower. For that reason, and to decouple the user interface from implementation details, go with a 32-bit quantity, which is then quadruplicated to form the siphash key.

One example of use of this interface is avoiding hash polarization, where two ECMP routers, one behind the other, happen to make consistent hashing decisions, and as a result, part of the ECMP space of the latter router is never used. Another is a load balancer where several machines forward traffic to one of a number of leaves, and the forwarding decisions need to be made consistently. (This is a case of a desired hash polarization, mentioned e.g. in chapter 6.3 of [0].)

There has already been a proposal to include a hash seed control interface in the past[1].

- Patches #1-#2 contain the substance of the work
- Patch #3 is an mlxsw offload
- Patches #4 and #5 are a selftest

[0] https://www.usenix.org/system/files/conference/nsdi18/nsdi18-araujo.pdf
[1] https://lore.kernel.org/netdev/YIlVpYMCn%2F8WfE1P@rnd/

v2:
- Patch #2:
- Instead of precomputing the siphash key, construct it in place of use thus obviating the need to use RCU.
- Instead of dispatching to the flow dissector for cases where user seed is 0, maintain a separate random seed. Initialize it early so that we can avoid a branch at the seed reader.
- In documentation, s/only valid/only present/ (when CONFIG_IP_ROUTE_MULTIPATH). Also mention the algorithm is unspecified and unstable in principle.
- Patch #3:
- Update to match changes in patch #2.
- Patch #4:
- New patch.
- Patch #5:
- Do not set seed on test init and run the stability tests first to catch the cases of a missed pernet seed init.

Petr Machata (5):
net: ipv4,ipv6: Pass multipath hash computation through a helper
net: ipv4: Add a sysctl to set multipath hash seed
mlxsw: spectrum_router: Apply user-defined multipath hash seed
selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()
selftests: forwarding: router_mpath_hash: Add a new selftest

Quoted 15 lines
 Documentation/networking/ip-sysctl.rst        |  14 +
 .../ethernet/mellanox/mlxsw/spectrum_router.c |   6 +-
 include/net/flow_dissector.h                  |   2 +
 include/net/ip_fib.h                          |  28 ++
 include/net/netns/ipv4.h                      |   8 +
 net/core/flow_dissector.c                     |   7 +
 net/ipv4/route.c                              |  12 +-
 net/ipv4/sysctl_net_ipv4.c                    |  66 ++++
 net/ipv6/route.c                              |  12 +-
 .../testing/selftests/net/forwarding/Makefile |   1 +
 tools/testing/selftests/net/forwarding/lib.sh |   9 +-
 .../net/forwarding/router_mpath_seed.sh       | 333 ++++++++++++++++++
 12 files changed, 484 insertions(+), 14 deletions(-)
 create mode 100755 tools/testing/selftests/net/forwarding/router_mpath_seed.sh

For the set:

#8 lore raw
In reply to Petr Machata
This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:

Hello:

This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:

Quoted 10 lines · On Fri, 7 Jun 2024 17:13:52 +0200 you wrote:

Let me just quote the commit message of patch #2 here to inform the motivation and some of the implementation:

When calculating hashes for the purpose of multipath forwarding, both IPv4 and IPv6 code currently fall back on flow_hash_from_keys(). That uses a randomly-generated seed. That's a fine choice by default, but unfortunately some deployments may need a tighter control over the seed used.

[...]

Here is the summary with links:
- [net-next,v2,1/5] net: ipv4,ipv6: Pass multipath hash computation through a helper

    https://git.kernel.org/netdev/net-next/c/3e453ca122d4
  - [net-next,v2,2/5] net: ipv4: Add a sysctl to set multipath hash seed
    https://git.kernel.org/netdev/net-next/c/4ee2a8cace3f
  - [net-next,v2,3/5] mlxsw: spectrum_router: Apply user-defined multipath hash seed
    https://git.kernel.org/netdev/net-next/c/60bcfede3f9f
  - [net-next,v2,4/5] selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()
    https://git.kernel.org/netdev/net-next/c/6f51aed38a4f
  - [net-next,v2,5/5] selftests: forwarding: router_mpath_hash: Add a new selftest
    https://git.kernel.org/netdev/net-next/c/5f90d93b6108

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html