[PATCH net 0/2] ipv6: Multipath routing fixes

[PATCH net 0/2] ipv6: Multipath routing fixes

[Ido Schimmel]

This patchset contains two fixes for IPv6 multipath routing. See the
commit messages for more details.

Ido Schimmel (2):
  ipv6: Start path selection from the first nexthop
  ipv6: Do not consider link down nexthops in path selection

 net/ipv6/route.c | 42 ++++++++++++++++++++++++++++++++++++++----
 1 file changed, 38 insertions(+), 4 deletions(-)

-- 
2.49.0

[PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Ido Schimmel]

Cited commit transitioned IPv6 path selection to use hash-threshold
instead of modulo-N. With hash-threshold, each nexthop is assigned a
region boundary in the multipath hash function's output space and a
nexthop is chosen if the calculated hash is smaller than the nexthop's
region boundary.

Hash-threshold does not work correctly if path selection does not start
with the first nexthop. For example, if fib6_select_path() is always
passed the last nexthop in the group, then it will always be chosen
because its region boundary covers the entire hash function's output
space.

Fix this by starting the selection process from the first nexthop and do
not consider nexthops for which rt6_score_route() provided a negative
score.

Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
Signed-off-by: Ido Schimmel <idosch@nvidia.com>
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index c3406a0d45bd..864f0002034b 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
 	return false;
 }
 
+static struct fib6_info *
+rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
+{
+	struct fib6_info *iter;
+	struct fib6_node *fn;
+
+	fn = rcu_dereference(rt->fib6_node);
+	if (!fn)
+		goto out;
+	iter = rcu_dereference(fn->leaf);
+	if (!iter)
+		goto out;
+
+	while (iter) {
+		if (iter->fib6_metric == rt->fib6_metric &&
+		    rt6_qualify_for_ecmp(iter))
+			return iter;
+		iter = rcu_dereference(iter->fib6_next);
+	}
+
+out:
+	return NULL;
+}
+
 void fib6_select_path(const struct net *net, struct fib6_result *res,
 		      struct flowi6 *fl6, int oif, bool have_oif_match,
 		      const struct sk_buff *skb, int strict)
 {
-	struct fib6_info *match = res->f6i;
+	struct fib6_info *first, *match = res->f6i;
 	struct fib6_info *sibling;
 
 	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
@@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
 		return;
 	}
 
-	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
+	first = rt6_multipath_first_sibling_rcu(match);
+	if (!first)
 		goto out;
 
-	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
+	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
+	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
+			    strict) >= 0) {
+		match = first;
+		goto out;
+	}
+
+	list_for_each_entry_rcu(sibling, &first->fib6_siblings,
 				fib6_siblings) {
 		const struct fib6_nh *nh = sibling->fib6_nh;
 		int nh_upper_bound;
-- 
2.49.0

Re: [PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Willem de Bruijn]

Ido Schimmel wrote:
> Cited commit transitioned IPv6 path selection to use hash-threshold
> instead of modulo-N. With hash-threshold, each nexthop is assigned a
> region boundary in the multipath hash function's output space and a
> nexthop is chosen if the calculated hash is smaller than the nexthop's
> region boundary.
> 
> Hash-threshold does not work correctly if path selection does not start
> with the first nexthop. For example, if fib6_select_path() is always
> passed the last nexthop in the group, then it will always be chosen
> because its region boundary covers the entire hash function's output
> space.
> 
> Fix this by starting the selection process from the first nexthop and do
> not consider nexthops for which rt6_score_route() provided a negative
> score.
> 
> Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
> Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
> Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> ---
>  net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
>  1 file changed, 35 insertions(+), 3 deletions(-)
> 
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index c3406a0d45bd..864f0002034b 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
>  	return false;
>  }
>  
> +static struct fib6_info *
> +rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
> +{
> +	struct fib6_info *iter;
> +	struct fib6_node *fn;
> +
> +	fn = rcu_dereference(rt->fib6_node);
> +	if (!fn)
> +		goto out;
> +	iter = rcu_dereference(fn->leaf);
> +	if (!iter)
> +		goto out;
> +
> +	while (iter) {
> +		if (iter->fib6_metric == rt->fib6_metric &&
> +		    rt6_qualify_for_ecmp(iter))
> +			return iter;
> +		iter = rcu_dereference(iter->fib6_next);
> +	}
> +
> +out:
> +	return NULL;
> +}

The rcu counterpart to rt6_multipath_first_sibling, which is used when
computing the ranges in rt6_multipath_rebalance.

> +
>  void fib6_select_path(const struct net *net, struct fib6_result *res,
>  		      struct flowi6 *fl6, int oif, bool have_oif_match,
>  		      const struct sk_buff *skb, int strict)
>  {
> -	struct fib6_info *match = res->f6i;
> +	struct fib6_info *first, *match = res->f6i;
>  	struct fib6_info *sibling;
>  
>  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> @@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
>  		return;
>  	}
>  
> -	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
> +	first = rt6_multipath_first_sibling_rcu(match);
> +	if (!first)
>  		goto out;
>  
> -	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
> +	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> +	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> +			    strict) >= 0) {

Does this fix address two issues in one patch: start from the first
sibling, and check validity of the sibling?

The behavior on negative score for the first_sibling appears
different from that on subsequent siblings in the for_each below:
in that case the loop breaks, while for the first it skips?

                if (fl6->mp_hash > nh_upper_bound)
                        continue;
                if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
                        break;
                match = sibling;
                break;

Am I reading that correct and is that intentional?

> +		match = first;
> +		goto out;
> +	}
> +
> +	list_for_each_entry_rcu(sibling, &first->fib6_siblings,
>  				fib6_siblings) {
>  		const struct fib6_nh *nh = sibling->fib6_nh;
>  		int nh_upper_bound;
> -- 
> 2.49.0
> 

Re: [PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Ido Schimmel]

Hi Willem,

Thanks for taking a look

On Fri, Apr 04, 2025 at 10:40:32AM -0400, Willem de Bruijn wrote:
> Ido Schimmel wrote:
> > Cited commit transitioned IPv6 path selection to use hash-threshold
> > instead of modulo-N. With hash-threshold, each nexthop is assigned a
> > region boundary in the multipath hash function's output space and a
> > nexthop is chosen if the calculated hash is smaller than the nexthop's
> > region boundary.
> > 
> > Hash-threshold does not work correctly if path selection does not start
> > with the first nexthop. For example, if fib6_select_path() is always
> > passed the last nexthop in the group, then it will always be chosen
> > because its region boundary covers the entire hash function's output
> > space.
> > 
> > Fix this by starting the selection process from the first nexthop and do
> > not consider nexthops for which rt6_score_route() provided a negative
> > score.
> > 
> > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
> > Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
> > Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> > ---
> >  net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
> >  1 file changed, 35 insertions(+), 3 deletions(-)
> > 
> > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > index c3406a0d45bd..864f0002034b 100644
> > --- a/net/ipv6/route.c
> > +++ b/net/ipv6/route.c
> > @@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
> >  	return false;
> >  }
> >  
> > +static struct fib6_info *
> > +rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
> > +{
> > +	struct fib6_info *iter;
> > +	struct fib6_node *fn;
> > +
> > +	fn = rcu_dereference(rt->fib6_node);
> > +	if (!fn)
> > +		goto out;
> > +	iter = rcu_dereference(fn->leaf);
> > +	if (!iter)
> > +		goto out;
> > +
> > +	while (iter) {
> > +		if (iter->fib6_metric == rt->fib6_metric &&
> > +		    rt6_qualify_for_ecmp(iter))
> > +			return iter;
> > +		iter = rcu_dereference(iter->fib6_next);
> > +	}
> > +
> > +out:
> > +	return NULL;
> > +}
> 
> The rcu counterpart to rt6_multipath_first_sibling, which is used when
> computing the ranges in rt6_multipath_rebalance.

Right

> 
> > +
> >  void fib6_select_path(const struct net *net, struct fib6_result *res,
> >  		      struct flowi6 *fl6, int oif, bool have_oif_match,
> >  		      const struct sk_buff *skb, int strict)
> >  {
> > -	struct fib6_info *match = res->f6i;
> > +	struct fib6_info *first, *match = res->f6i;
> >  	struct fib6_info *sibling;
> >  
> >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> > @@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> >  		return;
> >  	}
> >  
> > -	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
> > +	first = rt6_multipath_first_sibling_rcu(match);
> > +	if (!first)
> >  		goto out;
> >  
> > -	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
> > +	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > +	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> > +			    strict) >= 0) {
> 
> Does this fix address two issues in one patch: start from the first
> sibling, and check validity of the sibling?

The loop below will only choose a nexthop ('match = sibling') if its
score is not negative. The purpose of the check here is to do the same
for the first nexthop. That is, only choose a nexthop when calculated
hash is smaller than the nexthop's region boundary and the nexthop has a
non negative score.

This was not done before for 'match' because the caller already chose
'match' based on its score.

> The behavior on negative score for the first_sibling appears
> different from that on subsequent siblings in the for_each below:
> in that case the loop breaks, while for the first it skips?
> 
>                 if (fl6->mp_hash > nh_upper_bound)
>                         continue;
>                 if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
>                         break;
>                 match = sibling;
>                 break;
> 
> Am I reading that correct and is that intentional?

Hmm, I see. I think it makes sense to have the same behavior for all
nexthops. That is, if nexthop fits in terms of hash but has a negative
score, then fallback to 'match'. How about the following diff?

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index ab12b816ab94..210b84cecc24 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -470,10 +470,10 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
                goto out;
 
        hash = fl6->mp_hash;
-       if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
-           rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
-                           strict) >= 0) {
-               match = first;
+       if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound)) {
+               if (rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
+                                   strict) >= 0)
+                       match = first;
                goto out;
        }

Re: [PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Willem de Bruijn]

Ido Schimmel wrote:
> Hi Willem,
> 
> Thanks for taking a look
> 
> On Fri, Apr 04, 2025 at 10:40:32AM -0400, Willem de Bruijn wrote:
> > Ido Schimmel wrote:
> > > Cited commit transitioned IPv6 path selection to use hash-threshold
> > > instead of modulo-N. With hash-threshold, each nexthop is assigned a
> > > region boundary in the multipath hash function's output space and a
> > > nexthop is chosen if the calculated hash is smaller than the nexthop's
> > > region boundary.
> > > 
> > > Hash-threshold does not work correctly if path selection does not start
> > > with the first nexthop. For example, if fib6_select_path() is always
> > > passed the last nexthop in the group, then it will always be chosen
> > > because its region boundary covers the entire hash function's output
> > > space.
> > > 
> > > Fix this by starting the selection process from the first nexthop and do
> > > not consider nexthops for which rt6_score_route() provided a negative
> > > score.
> > > 
> > > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > > Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
> > > Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
> > > Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> > > ---
> > >  net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
> > >  1 file changed, 35 insertions(+), 3 deletions(-)
> > > 
> > > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > > index c3406a0d45bd..864f0002034b 100644
> > > --- a/net/ipv6/route.c
> > > +++ b/net/ipv6/route.c
> > > @@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
> > >  	return false;
> > >  }
> > >  
> > > +static struct fib6_info *
> > > +rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
> > > +{
> > > +	struct fib6_info *iter;
> > > +	struct fib6_node *fn;
> > > +
> > > +	fn = rcu_dereference(rt->fib6_node);
> > > +	if (!fn)
> > > +		goto out;
> > > +	iter = rcu_dereference(fn->leaf);
> > > +	if (!iter)
> > > +		goto out;
> > > +
> > > +	while (iter) {
> > > +		if (iter->fib6_metric == rt->fib6_metric &&
> > > +		    rt6_qualify_for_ecmp(iter))
> > > +			return iter;
> > > +		iter = rcu_dereference(iter->fib6_next);
> > > +	}
> > > +
> > > +out:
> > > +	return NULL;
> > > +}
> > 
> > The rcu counterpart to rt6_multipath_first_sibling, which is used when
> > computing the ranges in rt6_multipath_rebalance.
> 
> Right
> 
> > 
> > > +
> > >  void fib6_select_path(const struct net *net, struct fib6_result *res,
> > >  		      struct flowi6 *fl6, int oif, bool have_oif_match,
> > >  		      const struct sk_buff *skb, int strict)
> > >  {
> > > -	struct fib6_info *match = res->f6i;
> > > +	struct fib6_info *first, *match = res->f6i;
> > >  	struct fib6_info *sibling;
> > >  
> > >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> > > @@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > >  		return;
> > >  	}
> > >  
> > > -	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
> > > +	first = rt6_multipath_first_sibling_rcu(match);
> > > +	if (!first)
> > >  		goto out;
> > >  
> > > -	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
> > > +	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > > +	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> > > +			    strict) >= 0) {
> > 
> > Does this fix address two issues in one patch: start from the first
> > sibling, and check validity of the sibling?
> 
> The loop below will only choose a nexthop ('match = sibling') if its
> score is not negative. The purpose of the check here is to do the same
> for the first nexthop. That is, only choose a nexthop when calculated
> hash is smaller than the nexthop's region boundary and the nexthop has a
> non negative score.
> 
> This was not done before for 'match' because the caller already chose
> 'match' based on its score.
> 
> > The behavior on negative score for the first_sibling appears
> > different from that on subsequent siblings in the for_each below:
> > in that case the loop breaks, while for the first it skips?
> > 
> >                 if (fl6->mp_hash > nh_upper_bound)
> >                         continue;
> >                 if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
> >                         break;
> >                 match = sibling;
> >                 break;
> > 
> > Am I reading that correct and is that intentional?
> 
> Hmm, I see. I think it makes sense to have the same behavior for all
> nexthops. That is, if nexthop fits in terms of hash but has a negative
> score, then fallback to 'match'. How about the following diff?

That unifies the behavior.

Is match guaranteed to be an acceptable path, i.e., having a positive
score?

Else just the first valid sibling after the matching, but invalid,
sibling, may be the most robust solution.

> 
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index ab12b816ab94..210b84cecc24 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -470,10 +470,10 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
>                 goto out;
>  
>         hash = fl6->mp_hash;
> -       if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> -           rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> -                           strict) >= 0) {
> -               match = first;
> +       if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound)) {
> +               if (rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> +                                   strict) >= 0)
> +                       match = first;
>                 goto out;
>         }

Re: [PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Ido Schimmel]

On Sun, Apr 06, 2025 at 02:30:19PM -0400, Willem de Bruijn wrote:
> Ido Schimmel wrote:
> > Hi Willem,
> > 
> > Thanks for taking a look
> > 
> > On Fri, Apr 04, 2025 at 10:40:32AM -0400, Willem de Bruijn wrote:
> > > Ido Schimmel wrote:
> > > > Cited commit transitioned IPv6 path selection to use hash-threshold
> > > > instead of modulo-N. With hash-threshold, each nexthop is assigned a
> > > > region boundary in the multipath hash function's output space and a
> > > > nexthop is chosen if the calculated hash is smaller than the nexthop's
> > > > region boundary.
> > > > 
> > > > Hash-threshold does not work correctly if path selection does not start
> > > > with the first nexthop. For example, if fib6_select_path() is always
> > > > passed the last nexthop in the group, then it will always be chosen
> > > > because its region boundary covers the entire hash function's output
> > > > space.
> > > > 
> > > > Fix this by starting the selection process from the first nexthop and do
> > > > not consider nexthops for which rt6_score_route() provided a negative
> > > > score.
> > > > 
> > > > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > > > Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
> > > > Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
> > > > Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> > > > ---
> > > >  net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
> > > >  1 file changed, 35 insertions(+), 3 deletions(-)
> > > > 
> > > > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > > > index c3406a0d45bd..864f0002034b 100644
> > > > --- a/net/ipv6/route.c
> > > > +++ b/net/ipv6/route.c
> > > > @@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
> > > >  	return false;
> > > >  }
> > > >  
> > > > +static struct fib6_info *
> > > > +rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
> > > > +{
> > > > +	struct fib6_info *iter;
> > > > +	struct fib6_node *fn;
> > > > +
> > > > +	fn = rcu_dereference(rt->fib6_node);
> > > > +	if (!fn)
> > > > +		goto out;
> > > > +	iter = rcu_dereference(fn->leaf);
> > > > +	if (!iter)
> > > > +		goto out;
> > > > +
> > > > +	while (iter) {
> > > > +		if (iter->fib6_metric == rt->fib6_metric &&
> > > > +		    rt6_qualify_for_ecmp(iter))
> > > > +			return iter;
> > > > +		iter = rcu_dereference(iter->fib6_next);
> > > > +	}
> > > > +
> > > > +out:
> > > > +	return NULL;
> > > > +}
> > > 
> > > The rcu counterpart to rt6_multipath_first_sibling, which is used when
> > > computing the ranges in rt6_multipath_rebalance.
> > 
> > Right
> > 
> > > 
> > > > +
> > > >  void fib6_select_path(const struct net *net, struct fib6_result *res,
> > > >  		      struct flowi6 *fl6, int oif, bool have_oif_match,
> > > >  		      const struct sk_buff *skb, int strict)
> > > >  {
> > > > -	struct fib6_info *match = res->f6i;
> > > > +	struct fib6_info *first, *match = res->f6i;
> > > >  	struct fib6_info *sibling;
> > > >  
> > > >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> > > > @@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > > >  		return;
> > > >  	}
> > > >  
> > > > -	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
> > > > +	first = rt6_multipath_first_sibling_rcu(match);
> > > > +	if (!first)
> > > >  		goto out;
> > > >  
> > > > -	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
> > > > +	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > > > +	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> > > > +			    strict) >= 0) {
> > > 
> > > Does this fix address two issues in one patch: start from the first
> > > sibling, and check validity of the sibling?
> > 
> > The loop below will only choose a nexthop ('match = sibling') if its
> > score is not negative. The purpose of the check here is to do the same
> > for the first nexthop. That is, only choose a nexthop when calculated
> > hash is smaller than the nexthop's region boundary and the nexthop has a
> > non negative score.
> > 
> > This was not done before for 'match' because the caller already chose
> > 'match' based on its score.
> > 
> > > The behavior on negative score for the first_sibling appears
> > > different from that on subsequent siblings in the for_each below:
> > > in that case the loop breaks, while for the first it skips?
> > > 
> > >                 if (fl6->mp_hash > nh_upper_bound)
> > >                         continue;
> > >                 if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
> > >                         break;
> > >                 match = sibling;
> > >                 break;
> > > 
> > > Am I reading that correct and is that intentional?
> > 
> > Hmm, I see. I think it makes sense to have the same behavior for all
> > nexthops. That is, if nexthop fits in terms of hash but has a negative
> > score, then fallback to 'match'. How about the following diff?
> 
> That unifies the behavior.
> 
> Is match guaranteed to be an acceptable path, i.e., having a positive
> score?

It can be negative (-1) if there isn't a neighbour associated with the
nexthop which isn't necessarily a bad sign. Even if this is the case,
it's the nexthop the kernel chose after evaluating the others.

> Else just the first valid sibling after the matching, but invalid,
> sibling, may be the most robust solution.

AFAICT, the kernel has been falling back to 'match' upon a negative
sibling score since 2013, so my preference would be to keep this
behavior.

Re: [PATCH net 1/2] ipv6: Start path selection from the first nexthop

[Willem de Bruijn]

Ido Schimmel wrote:
> On Sun, Apr 06, 2025 at 02:30:19PM -0400, Willem de Bruijn wrote:
> > Ido Schimmel wrote:
> > > Hi Willem,
> > > 
> > > Thanks for taking a look
> > > 
> > > On Fri, Apr 04, 2025 at 10:40:32AM -0400, Willem de Bruijn wrote:
> > > > Ido Schimmel wrote:
> > > > > Cited commit transitioned IPv6 path selection to use hash-threshold
> > > > > instead of modulo-N. With hash-threshold, each nexthop is assigned a
> > > > > region boundary in the multipath hash function's output space and a
> > > > > nexthop is chosen if the calculated hash is smaller than the nexthop's
> > > > > region boundary.
> > > > > 
> > > > > Hash-threshold does not work correctly if path selection does not start
> > > > > with the first nexthop. For example, if fib6_select_path() is always
> > > > > passed the last nexthop in the group, then it will always be chosen
> > > > > because its region boundary covers the entire hash function's output
> > > > > space.
> > > > > 
> > > > > Fix this by starting the selection process from the first nexthop and do
> > > > > not consider nexthops for which rt6_score_route() provided a negative
> > > > > score.
> > > > > 
> > > > > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > > > > Reported-by: Stanislav Fomichev <stfomichev@gmail.com>
> > > > > Closes: https://lore.kernel.org/netdev/Z9RIyKZDNoka53EO@mini-arch/
> > > > > Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> > > > > ---
> > > > >  net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
> > > > >  1 file changed, 35 insertions(+), 3 deletions(-)
> > > > > 
> > > > > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > > > > index c3406a0d45bd..864f0002034b 100644
> > > > > --- a/net/ipv6/route.c
> > > > > +++ b/net/ipv6/route.c
> > > > > @@ -412,11 +412,35 @@ static bool rt6_check_expired(const struct rt6_info *rt)
> > > > >  	return false;
> > > > >  }
> > > > >  
> > > > > +static struct fib6_info *
> > > > > +rt6_multipath_first_sibling_rcu(const struct fib6_info *rt)
> > > > > +{
> > > > > +	struct fib6_info *iter;
> > > > > +	struct fib6_node *fn;
> > > > > +
> > > > > +	fn = rcu_dereference(rt->fib6_node);
> > > > > +	if (!fn)
> > > > > +		goto out;
> > > > > +	iter = rcu_dereference(fn->leaf);
> > > > > +	if (!iter)
> > > > > +		goto out;
> > > > > +
> > > > > +	while (iter) {
> > > > > +		if (iter->fib6_metric == rt->fib6_metric &&
> > > > > +		    rt6_qualify_for_ecmp(iter))
> > > > > +			return iter;
> > > > > +		iter = rcu_dereference(iter->fib6_next);
> > > > > +	}
> > > > > +
> > > > > +out:
> > > > > +	return NULL;
> > > > > +}
> > > > 
> > > > The rcu counterpart to rt6_multipath_first_sibling, which is used when
> > > > computing the ranges in rt6_multipath_rebalance.
> > > 
> > > Right
> > > 
> > > > 
> > > > > +
> > > > >  void fib6_select_path(const struct net *net, struct fib6_result *res,
> > > > >  		      struct flowi6 *fl6, int oif, bool have_oif_match,
> > > > >  		      const struct sk_buff *skb, int strict)
> > > > >  {
> > > > > -	struct fib6_info *match = res->f6i;
> > > > > +	struct fib6_info *first, *match = res->f6i;
> > > > >  	struct fib6_info *sibling;
> > > > >  
> > > > >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> > > > > @@ -440,10 +464,18 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > > > >  		return;
> > > > >  	}
> > > > >  
> > > > > -	if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
> > > > > +	first = rt6_multipath_first_sibling_rcu(match);
> > > > > +	if (!first)
> > > > >  		goto out;
> > > > >  
> > > > > -	list_for_each_entry_rcu(sibling, &match->fib6_siblings,
> > > > > +	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > > > > +	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> > > > > +			    strict) >= 0) {
> > > > 
> > > > Does this fix address two issues in one patch: start from the first
> > > > sibling, and check validity of the sibling?
> > > 
> > > The loop below will only choose a nexthop ('match = sibling') if its
> > > score is not negative. The purpose of the check here is to do the same
> > > for the first nexthop. That is, only choose a nexthop when calculated
> > > hash is smaller than the nexthop's region boundary and the nexthop has a
> > > non negative score.
> > > 
> > > This was not done before for 'match' because the caller already chose
> > > 'match' based on its score.
> > > 
> > > > The behavior on negative score for the first_sibling appears
> > > > different from that on subsequent siblings in the for_each below:
> > > > in that case the loop breaks, while for the first it skips?
> > > > 
> > > >                 if (fl6->mp_hash > nh_upper_bound)
> > > >                         continue;
> > > >                 if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
> > > >                         break;
> > > >                 match = sibling;
> > > >                 break;
> > > > 
> > > > Am I reading that correct and is that intentional?
> > > 
> > > Hmm, I see. I think it makes sense to have the same behavior for all
> > > nexthops. That is, if nexthop fits in terms of hash but has a negative
> > > score, then fallback to 'match'. How about the following diff?
> > 
> > That unifies the behavior.
> > 
> > Is match guaranteed to be an acceptable path, i.e., having a positive
> > score?
> 
> It can be negative (-1) if there isn't a neighbour associated with the
> nexthop which isn't necessarily a bad sign. Even if this is the case,
> it's the nexthop the kernel chose after evaluating the others.
> 
> > Else just the first valid sibling after the matching, but invalid,
> > sibling, may be the most robust solution.
> 
> AFAICT, the kernel has been falling back to 'match' upon a negative
> sibling score since 2013, so my preference would be to keep this
> behavior.

Good point.

[PATCH net 2/2] ipv6: Do not consider link down nexthops in path selection

[Ido Schimmel]

Nexthops whose link is down are not supposed to be considered during
path selection when the "ignore_routes_with_linkdown" sysctl is set.
This is done by assigning them a negative region boundary.

However, when comparing the computed hash (unsigned) with the region
boundary (signed), the negative region boundary is treated as unsigned,
resulting in incorrect nexthop selection.

Fix by treating the computed hash as signed. Note that the computed hash
is always in range of [0, 2^31 - 1].

Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
Signed-off-by: Ido Schimmel <idosch@nvidia.com>
---
 net/ipv6/route.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index 864f0002034b..ab12b816ab94 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -442,6 +442,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
 {
 	struct fib6_info *first, *match = res->f6i;
 	struct fib6_info *sibling;
+	int hash;
 
 	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
 		goto out;
@@ -468,7 +469,8 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
 	if (!first)
 		goto out;
 
-	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
+	hash = fl6->mp_hash;
+	if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
 	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
 			    strict) >= 0) {
 		match = first;
@@ -481,7 +483,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
 		int nh_upper_bound;
 
 		nh_upper_bound = atomic_read(&nh->fib_nh_upper_bound);
-		if (fl6->mp_hash > nh_upper_bound)
+		if (hash > nh_upper_bound)
 			continue;
 		if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
 			break;
-- 
2.49.0

Re: [PATCH net 2/2] ipv6: Do not consider link down nexthops in path selection

[Willem de Bruijn]

Ido Schimmel wrote:
> Nexthops whose link is down are not supposed to be considered during
> path selection when the "ignore_routes_with_linkdown" sysctl is set.
> This is done by assigning them a negative region boundary.
> 
> However, when comparing the computed hash (unsigned) with the region
> boundary (signed), the negative region boundary is treated as unsigned,
> resulting in incorrect nexthop selection.
> 
> Fix by treating the computed hash as signed. Note that the computed hash
> is always in range of [0, 2^31 - 1].
> 
> Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> ---
>  net/ipv6/route.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index 864f0002034b..ab12b816ab94 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -442,6 +442,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
>  {
>  	struct fib6_info *first, *match = res->f6i;
>  	struct fib6_info *sibling;
> +	int hash;
>  
>  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
>  		goto out;
> @@ -468,7 +469,8 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
>  	if (!first)
>  		goto out;
>  
> -	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> +	hash = fl6->mp_hash;
> +	if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&

The combined upper bounds add up to the total weights of the paths.

Should hash be scaled (using reciprocal_scale) to that bound to have
a uniform random distribution across all weights?

Else a hash in the range [0, 2^31 - 1] is unlikely to fall within the
total weights range.

>  	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
>  			    strict) >= 0) {
>  		match = first;
> @@ -481,7 +483,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
>  		int nh_upper_bound;
>  
>  		nh_upper_bound = atomic_read(&nh->fib_nh_upper_bound);
> -		if (fl6->mp_hash > nh_upper_bound)
> +		if (hash > nh_upper_bound)
>  			continue;
>  		if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
>  			break;
> -- 
> 2.49.0
> 

Re: [PATCH net 2/2] ipv6: Do not consider link down nexthops in path selection

[Willem de Bruijn]

Willem de Bruijn wrote:
> Ido Schimmel wrote:
> > Nexthops whose link is down are not supposed to be considered during
> > path selection when the "ignore_routes_with_linkdown" sysctl is set.
> > This is done by assigning them a negative region boundary.
> > 
> > However, when comparing the computed hash (unsigned) with the region
> > boundary (signed), the negative region boundary is treated as unsigned,
> > resulting in incorrect nexthop selection.
> > 
> > Fix by treating the computed hash as signed. Note that the computed hash
> > is always in range of [0, 2^31 - 1].
> > 
> > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > Signed-off-by: Ido Schimmel <idosch@nvidia.com>
> > ---
> >  net/ipv6/route.c | 6 ++++--
> >  1 file changed, 4 insertions(+), 2 deletions(-)
> > 
> > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > index 864f0002034b..ab12b816ab94 100644
> > --- a/net/ipv6/route.c
> > +++ b/net/ipv6/route.c
> > @@ -442,6 +442,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> >  {
> >  	struct fib6_info *first, *match = res->f6i;
> >  	struct fib6_info *sibling;
> > +	int hash;
> >  
> >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> >  		goto out;
> > @@ -468,7 +469,8 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> >  	if (!first)
> >  		goto out;
> >  
> > -	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > +	hash = fl6->mp_hash;
> > +	if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> 
> The combined upper bounds add up to the total weights of the paths.
> 
> Should hash be scaled (using reciprocal_scale) to that bound to have
> a uniform random distribution across all weights?
> 
> Else a hash in the range [0, 2^31 - 1] is unlikely to fall within the
> total weights range.

Never mind, the scaling is handled in rt6_upper_bound_set. Where
weights are scaled to cover the [0, INT_MAX - 1] range.

I confused fib_nh_weight with fib_nh_upper_bound.

But should U32 hash then be truncated to the lower 31 bits, to
drop the sign and negative half of the space when used as int?

> >  	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> >  			    strict) >= 0) {
> >  		match = first;
> > @@ -481,7 +483,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> >  		int nh_upper_bound;
> >  
> >  		nh_upper_bound = atomic_read(&nh->fib_nh_upper_bound);
> > -		if (fl6->mp_hash > nh_upper_bound)
> > +		if (hash > nh_upper_bound)
> >  			continue;
> >  		if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
> >  			break;
> > -- 
> > 2.49.0
> > 
> 
> 

Re: [PATCH net 2/2] ipv6: Do not consider link down nexthops in path selection

[Willem de Bruijn]

Willem de Bruijn wrote:
> Willem de Bruijn wrote:
> > Ido Schimmel wrote:
> > > Nexthops whose link is down are not supposed to be considered during
> > > path selection when the "ignore_routes_with_linkdown" sysctl is set.
> > > This is done by assigning them a negative region boundary.
> > > 
> > > However, when comparing the computed hash (unsigned) with the region
> > > boundary (signed), the negative region boundary is treated as unsigned,
> > > resulting in incorrect nexthop selection.
> > > 
> > > Fix by treating the computed hash as signed. Note that the computed hash
> > > is always in range of [0, 2^31 - 1].
> > > 
> > > Fixes: 3d709f69a3e7 ("ipv6: Use hash-threshold instead of modulo-N")
> > > Signed-off-by: Ido Schimmel <idosch@nvidia.com>

Reviewed-by: Willem de Bruijn <willemb@google.com>

> > > ---
> > >  net/ipv6/route.c | 6 ++++--
> > >  1 file changed, 4 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > > index 864f0002034b..ab12b816ab94 100644
> > > --- a/net/ipv6/route.c
> > > +++ b/net/ipv6/route.c
> > > @@ -442,6 +442,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > >  {
> > >  	struct fib6_info *first, *match = res->f6i;
> > >  	struct fib6_info *sibling;
> > > +	int hash;
> > >  
> > >  	if (!match->nh && (!match->fib6_nsiblings || have_oif_match))
> > >  		goto out;
> > > @@ -468,7 +469,8 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > >  	if (!first)
> > >  		goto out;
> > >  
> > > -	if (fl6->mp_hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > > +	hash = fl6->mp_hash;
> > > +	if (hash <= atomic_read(&first->fib6_nh->fib_nh_upper_bound) &&
> > 
> > The combined upper bounds add up to the total weights of the paths.
> > 
> > Should hash be scaled (using reciprocal_scale) to that bound to have
> > a uniform random distribution across all weights?
> > 
> > Else a hash in the range [0, 2^31 - 1] is unlikely to fall within the
> > total weights range.
> 
> Never mind, the scaling is handled in rt6_upper_bound_set. Where
> weights are scaled to cover the [0, INT_MAX - 1] range.
> 
> I confused fib_nh_weight with fib_nh_upper_bound.
> 
> But should U32 hash then be truncated to the lower 31 bits, to
> drop the sign and negative half of the space when used as int?

And you document this in the commit message: "Note that the computed
hash is always in range of [0, 2^31 - 1]".

That is the `mhash >> 1` at the bottom of rt6_multipath_hash.

Sorry, I'm a bit slow in internalizing this code. And perhaps a bit
too fast at responding ;) But got it now!

 
> > >  	    rt6_score_route(first->fib6_nh, first->fib6_flags, oif,
> > >  			    strict) >= 0) {
> > >  		match = first;
> > > @@ -481,7 +483,7 @@ void fib6_select_path(const struct net *net, struct fib6_result *res,
> > >  		int nh_upper_bound;
> > >  
> > >  		nh_upper_bound = atomic_read(&nh->fib_nh_upper_bound);
> > > -		if (fl6->mp_hash > nh_upper_bound)
> > > +		if (hash > nh_upper_bound)
> > >  			continue;
> > >  		if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
> > >  			break;
> > > -- 
> > > 2.49.0
> > > 
> > 
> > 
> 
> 

Re: [PATCH net 0/2] ipv6: Multipath routing fixes

[patchwork-bot+netdevbpf]

Hello:

This series was applied to netdev/net.git (main)
by Jakub Kicinski <kuba@kernel.org>:

On Wed, 2 Apr 2025 14:42:22 +0300 you wrote:
> This patchset contains two fixes for IPv6 multipath routing. See the
> commit messages for more details.
> 
> Ido Schimmel (2):
>   ipv6: Start path selection from the first nexthop
>   ipv6: Do not consider link down nexthops in path selection
> 
> [...]

Here is the summary with links:
  - [net,1/2] ipv6: Start path selection from the first nexthop
    https://git.kernel.org/netdev/net/c/4d0ab3a6885e
  - [net,2/2] ipv6: Do not consider link down nexthops in path selection
    https://git.kernel.org/netdev/net/c/8b8e0dd35716

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH net 0/2] ipv6: Multipath routing fixes

[Jakub Kicinski]

On Fri, 04 Apr 2025 14:40:33 +0000 patchwork-bot+netdevbpf@kernel.org
wrote:
> Hello:
> 
> This series was applied to netdev/net.git (main)
> by Jakub Kicinski <kuba@kernel.org>:
> 
> On Wed, 2 Apr 2025 14:42:22 +0300 you wrote:
> > This patchset contains two fixes for IPv6 multipath routing. See the
> > commit messages for more details.
> > 
> > Ido Schimmel (2):
> >   ipv6: Start path selection from the first nexthop
> >   ipv6: Do not consider link down nexthops in path selection
> > 
> > [...]  
> 
> Here is the summary with links:
>   - [net,1/2] ipv6: Start path selection from the first nexthop
>     https://git.kernel.org/netdev/net/c/4d0ab3a6885e
>   - [net,2/2] ipv6: Do not consider link down nexthops in path selection
>     https://git.kernel.org/netdev/net/c/8b8e0dd35716
> 
> You are awesome, thank you!

Ugh, rushed this it seems.
Sorry, Willem.

Re: [PATCH net 0/2] ipv6: Multipath routing fixes

[Willem de Bruijn]

Jakub Kicinski wrote:
> On Fri, 04 Apr 2025 14:40:33 +0000 patchwork-bot+netdevbpf@kernel.org
> wrote:
> > Hello:
> > 
> > This series was applied to netdev/net.git (main)
> > by Jakub Kicinski <kuba@kernel.org>:
> > 
> > On Wed, 2 Apr 2025 14:42:22 +0300 you wrote:
> > > This patchset contains two fixes for IPv6 multipath routing. See the
> > > commit messages for more details.
> > > 
> > > Ido Schimmel (2):
> > >   ipv6: Start path selection from the first nexthop
> > >   ipv6: Do not consider link down nexthops in path selection
> > > 
> > > [...]  
> > 
> > Here is the summary with links:
> >   - [net,1/2] ipv6: Start path selection from the first nexthop
> >     https://git.kernel.org/netdev/net/c/4d0ab3a6885e
> >   - [net,2/2] ipv6: Do not consider link down nexthops in path selection
> >     https://git.kernel.org/netdev/net/c/8b8e0dd35716
> > 
> > You are awesome, thank you!
> 
> Ugh, rushed this it seems.
> Sorry, Willem.

No worries of course.

I just did not see a more authoritative Reviewed-by and was trying to
better understand the code. I trust it's fine.

Re: [PATCH net 0/2] ipv6: Multipath routing fixes

[Guillaume Nault]

On Wed, Apr 02, 2025 at 02:42:22PM +0300, Ido Schimmel wrote:
> This patchset contains two fixes for IPv6 multipath routing. See the
> commit messages for more details.

Thanks for fixing this Ido! I've sucessfully tested the patches
(although it's too late for a Tested-by tag).

> Ido Schimmel (2):
>   ipv6: Start path selection from the first nexthop
>   ipv6: Do not consider link down nexthops in path selection
> 
>  net/ipv6/route.c | 42 ++++++++++++++++++++++++++++++++++++++----
>  1 file changed, 38 insertions(+), 4 deletions(-)
> 
> -- 
> 2.49.0
>