Allow configuration of multipath hash seed
Subsystems (6)
Petr Machata
maintainerv2 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
Petr Machata
maintainerPATCH 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
@@ -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
@@ -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
@@ -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
Petr Machata
maintainerPATCH v2 2/5 net: ipv4: Add a sysctl to set multipath hash seed
In reply to Petr MachataWhen 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
Petr Machata
maintainerPATCH v2 3/5 mlxsw: spectrum_router: Apply user-defined multipath hash seed
In reply to Petr MachataWhen 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
@@ -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
Petr Machata
maintainerPATCH v2 4/5 selftests: forwarding: lib: Split sysctl_save() out of sysctl_set()
In reply to Petr MachataIn 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
@@ -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
Petr Machata
maintainerPATCH v2 5/5 selftests: forwarding: router_mpath_hash: Add a new selftest
In reply to Petr MachataAdd 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
@@ -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
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/ (whenCONFIG_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: Splitsysctl_save()out ofsysctl_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,
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/ (whenCONFIG_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: Splitsysctl_save()out ofsysctl_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:
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