Skip to contentSkip to conversation

ipv6: Multipath routing fixes

PATCH Applied Ido Schimmel 5 participants 15 messages Apr 2, 2025 – Apr 7, 2025

Subsystems (3)
lore
Share & tools
lore

Ido Schimmel

author maintainer
#0 lore raw

cover ipv6: Multipath routing fixes

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(-)
Signature · 1 line
2.49.0
author maintainer
#1 lore raw

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

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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +35 -3
index c3406a0d45bd..864f0002034b 100644
@@ -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;
Signature · 1 line
2.49.0
#2 lore raw

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

Quoted 45 lines · 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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +13 -0
index c3406a0d45bd..864f0002034b 100644
@@ -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;
+

net/ipv6/route.c static bool rt6_check_expired(const struct rt6_info *rt) · line 437

Quoted 10 lines
net/ipv6/route.c +10 -0
+	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.

Quoted 13 lines
net/ipv6/route.c +2 -1
+
 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;
 	}

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 10 lines
net/ipv6/route.c +5 -2
 
-	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?

Quoted 11 lines
net/ipv6/route.c +5 -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;
Signature · 1 line
2.49.0
author maintainer
#3 lore raw

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

Hi Willem,

Thanks for taking a look

Quoted 51 lines · Willem de Bruijn
Quoted 50 lines · 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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +18 -0
index c3406a0d45bd..864f0002034b 100644
@@ -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);
Quoted 8 lines

net/ipv6/route.c static bool rt6_check_expired(const struct rt6_info *rt) · line 437

Quoted 5 lines
net/ipv6/route.c +5 -0
+	}
+
+out:
+	return NULL;
+}

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

Right

Quoted 20 lines
Quoted 20 lines
net/ipv6/route.c +4 -2
+
 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;
 
Quoted 7 lines

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 4 lines
net/ipv6/route.c +3 -1
-	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.

Quoted 4 lines

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?

Quoted 8 lines
                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?

net/ipv6/route.c +4 -4
index ab12b816ab94..210b84cecc24 100644
@@ -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;
        }
#4 lore raw

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

Quoted 115 lines · Ido Schimmel

Hi Willem,

Thanks for taking a look

Quoted 51 lines · Willem de Bruijn
Quoted 50 lines · 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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +18 -0
index c3406a0d45bd..864f0002034b 100644
@@ -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);
Quoted 8 lines

net/ipv6/route.c static bool rt6_check_expired(const struct rt6_info *rt) · line 437

Quoted 5 lines
net/ipv6/route.c +5 -0
+	}
+
+out:
+	return NULL;
+}

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

Right

Quoted 20 lines
Quoted 20 lines
net/ipv6/route.c +4 -2
+
 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;
 
Quoted 7 lines

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 4 lines
net/ipv6/route.c +3 -1
-	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.

Quoted 11 lines

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;
Quoted 5 lines
Quoted 1 line

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.

Quoted 19 lines
net/ipv6/route.c +4 -4
index ab12b816ab94..210b84cecc24 100644
@@ -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;
        }
author maintainer
#5 lore raw

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

Quoted 118 lines · Willem de Bruijn
Quoted 117 lines · Ido Schimmel

Hi Willem,

Thanks for taking a look

Quoted 51 lines · Willem de Bruijn
Quoted 50 lines · 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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +18 -0
index c3406a0d45bd..864f0002034b 100644
@@ -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);
Quoted 8 lines

net/ipv6/route.c static bool rt6_check_expired(const struct rt6_info *rt) · line 437

Quoted 5 lines
net/ipv6/route.c +5 -0
+	}
+
+out:
+	return NULL;
+}

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

Right

Quoted 20 lines
Quoted 20 lines
net/ipv6/route.c +4 -2
+
 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;
 
Quoted 7 lines

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 4 lines
net/ipv6/route.c +3 -1
-	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.

Quoted 12 lines

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?

Quoted 8 lines
Quoted 3 lines

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.

Quoted 2 lines

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.

#6 lore raw

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

Quoted 132 lines · Ido Schimmel
Quoted 118 lines · Willem de Bruijn
Quoted 117 lines · Ido Schimmel

Hi Willem,

Thanks for taking a look

Quoted 51 lines · Willem de Bruijn
Quoted 50 lines · 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")
---
 net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++---
 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +18 -0
index c3406a0d45bd..864f0002034b 100644
@@ -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);
Quoted 8 lines

net/ipv6/route.c static bool rt6_check_expired(const struct rt6_info *rt) · line 437

Quoted 5 lines
net/ipv6/route.c +5 -0
+	}
+
+out:
+	return NULL;
+}

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

Right

Quoted 20 lines
Quoted 20 lines
net/ipv6/route.c +4 -2
+
 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;
 
Quoted 7 lines

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 4 lines
net/ipv6/route.c +3 -1
-	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.

Quoted 12 lines

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?

Quoted 8 lines
Quoted 3 lines

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.

Quoted 6 lines
Quoted 2 lines

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.

author maintainer
#7 lore raw

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

In reply to 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")
---
 net/ipv6/route.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/ipv6/route.c +4 -2
index 864f0002034b..ab12b816ab94 100644
@@ -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;
Signature · 1 line
2.49.0
#8 lore raw

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

Quoted 30 lines · 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")
---
 net/ipv6/route.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/ipv6/route.c +1 -0
index 864f0002034b..ab12b816ab94 100644
@@ -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;

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 6 lines
net/ipv6/route.c +2 -1
@@ -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.

Quoted 15 lines
net/ipv6/route.c +1 -1
 	    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;
Signature · 1 line
2.49.0
#9 lore raw

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

Quoted 40 lines · Willem de Bruijn
Quoted 30 lines · 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")
---
 net/ipv6/route.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/ipv6/route.c +1 -0
index 864f0002034b..ab12b816ab94 100644
@@ -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;

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 6 lines
net/ipv6/route.c +2 -1
@@ -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.

Quoted 5 lines

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?

Quoted 17 lines
Quoted 15 lines
net/ipv6/route.c +1 -1
 	    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;
Signature · 1 line
2.49.0
Reviewed-by
#10 lore raw

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

Quoted 10 lines · Willem de Bruijn
Quoted 9 lines · Willem de Bruijn
Quoted 8 lines · 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.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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")
Quoted 32 lines
Quoted 26 lines
Quoted 17 lines
---
 net/ipv6/route.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
net/ipv6/route.c +1 -0
index 864f0002034b..ab12b816ab94 100644
@@ -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;

net/ipv6/route.c void fib6_select_path(const struct net *net, struct fib6_result *res, · line 473

Quoted 6 lines
net/ipv6/route.c +2 -1
@@ -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.

Quoted 5 lines

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.

Quoted 7 lines

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!

Quoted 19 lines
Quoted 17 lines
Quoted 15 lines
net/ipv6/route.c +1 -1
 	    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;
Signature · 1 line
2.49.0
#11 lore raw
In reply to Ido Schimmel
This series was applied to netdev/net.git (main) by Jakub Kicinski <[email protected]>:

Hello:

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

Quoted 8 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
maintainer
#12 lore raw
Quoted 15 lines · On Fri, 04 Apr 2025 14:40:33 +0000 [email protected] wrote:

Hello:

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

Quoted 8 lines · 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

[...]

Quoted 7 lines

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.

#13 lore raw
Quoted 23 lines · Jakub Kicinski
Quoted 21 lines · On Fri, 04 Apr 2025 14:40:33 +0000 [email protected] wrote:

Hello:

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

Quoted 8 lines · 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
Quoted 4 lines
Quoted 1 line

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.

#14 lore raw
In reply to Ido Schimmel
Quoted 2 lines · Ido Schimmel

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).

Quoted 10 lines

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(-)
Signature · 1 line
2.49.0