ipv6: Multipath routing fixes
Subsystems (3)
Ido Schimmel
maintainercover 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
Ido Schimmel
maintainerPATCH 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.
--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)
net/ipv6/route.c +35 -3
@@ -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
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")Reported-by Stanislav Fomichev <[email protected]>Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)net/ipv6/route.c +13
-0@@ -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
Ido Schimmel
maintainerRe: [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")Reported-by Stanislav Fomichev <[email protected]>Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)net/ipv6/route.c +18
-0@@ -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 inrt6_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_siblingappears different from that on subsequent siblings in thefor_eachbelow:
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
@@ -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
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")Reported-by Stanislav Fomichev <[email protected]>Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)net/ipv6/route.c +18
-0@@ -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 inrt6_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_siblingappears different from that on subsequent siblings in thefor_eachbelow:
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@@ -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; }
Ido Schimmel
maintainerRe: [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")Reported-by Stanislav Fomichev <[email protected]>Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)net/ipv6/route.c +18
-0@@ -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 inrt6_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_siblingappears different from that on subsequent siblings in thefor_eachbelow:
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.
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")Reported-by Stanislav Fomichev <[email protected]>Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 38 +++++++++++++++++++++++++++++++++++--- 1 file changed, 35 insertions(+), 3 deletions(-)net/ipv6/route.c +18
-0@@ -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 inrt6_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_siblingappears different from that on subsequent siblings in thefor_eachbelow:
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.
Ido Schimmel
maintainerPATCH 2/2 ipv6: Do not consider link down nexthops in path selection
In reply to Ido SchimmelNexthops 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].
--- net/ipv6/route.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
net/ipv6/route.c +4 -2
@@ -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
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")Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)net/ipv6/route.c +1
-0@@ -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
-1rt6_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
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")Signed-off-by Ido Schimmel <[email protected]>--- net/ipv6/route.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)net/ipv6/route.c +1
-0@@ -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
-1rt6_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
Willem de Bruijn
Reviewed-byRe: [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")Signed-off-by Ido Schimmel <[email protected]>
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@@ -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_weightwithfib_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
-1rt6_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
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
Jakub Kicinski
maintainerQuoted 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 nexthophttps://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/8b8e0dd35716You are awesome, thank you!
Ugh, rushed this it seems.
Sorry, Willem.
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 nexthophttps://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.
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 selectionnet/ipv6/route.c | 42 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 38 insertions(+), 4 deletions(-)Signature · 1 line
2.49.0