From mboxrd@z Thu Jan 1 00:00:00 1970 From: Ido Schimmel Subject: [PATCH net-next 3/4] ipv6: Use hash-threshold instead of modulo-N Date: Tue, 9 Jan 2018 16:40:27 +0200 Message-ID: <20180109144028.30133-4-idosch@mellanox.com> References: <20180109144028.30133-1-idosch@mellanox.com> Mime-Version: 1.0 Content-Type: text/plain Cc: davem@davemloft.net, dsahern@gmail.com, roopa@cumulusnetworks.com, nikolay@cumulusnetworks.com, pch@ordbogen.com, jkbs@redhat.com, yoshfuji@linux-ipv6.org, mlxsw@mellanox.com, Ido Schimmel To: netdev@vger.kernel.org Return-path: Received: from mail-ve1eur01on0063.outbound.protection.outlook.com ([104.47.1.63]:36512 "EHLO EUR01-VE1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752769AbeAIOmC (ORCPT ); Tue, 9 Jan 2018 09:42:02 -0500 In-Reply-To: <20180109144028.30133-1-idosch@mellanox.com> Sender: netdev-owner@vger.kernel.org List-ID: Now that each nexthop stores its region boundary in the multipath hash function's output space, we can use hash-threshold instead of modulo-N in multipath selection. This reduces the number of checks we need to perform during lookup, as dead and linkdown nexthops are assigned a negative region boundary. In addition, in contrast to modulo-N, only flows near region boundaries are affected when a nexthop is added or removed. Signed-off-by: Ido Schimmel --- net/ipv6/route.c | 36 +++++++++++++----------------------- 1 file changed, 13 insertions(+), 23 deletions(-) diff --git a/net/ipv6/route.c b/net/ipv6/route.c index 09e8e10b101d..7837b8c754a3 100644 --- a/net/ipv6/route.c +++ b/net/ipv6/route.c @@ -455,7 +455,6 @@ static struct rt6_info *rt6_multipath_select(struct rt6_info *match, int strict) { struct rt6_info *sibling, *next_sibling; - int route_choosen; /* We might have already computed the hash for ICMPv6 errors. In such * case it will always be non-zero. Otherwise now is the time to do it. @@ -463,28 +462,19 @@ static struct rt6_info *rt6_multipath_select(struct rt6_info *match, if (!fl6->mp_hash) fl6->mp_hash = rt6_multipath_hash(fl6, NULL); - route_choosen = fl6->mp_hash % (match->rt6i_nsiblings + 1); - /* Don't change the route, if route_choosen == 0 - * (siblings does not include ourself) - */ - if (route_choosen) - list_for_each_entry_safe(sibling, next_sibling, - &match->rt6i_siblings, rt6i_siblings) { - route_choosen--; - if (route_choosen == 0) { - struct inet6_dev *idev = sibling->rt6i_idev; - - if (sibling->rt6i_nh_flags & RTNH_F_DEAD) - break; - if (sibling->rt6i_nh_flags & RTNH_F_LINKDOWN && - idev->cnf.ignore_routes_with_linkdown) - break; - if (rt6_score_route(sibling, oif, strict) < 0) - break; - match = sibling; - break; - } - } + if (fl6->mp_hash <= atomic_read(&match->rt6i_nh_upper_bound)) + return match; + + list_for_each_entry_safe(sibling, next_sibling, &match->rt6i_siblings, + rt6i_siblings) { + if (fl6->mp_hash > atomic_read(&sibling->rt6i_nh_upper_bound)) + continue; + if (rt6_score_route(sibling, oif, strict) < 0) + break; + match = sibling; + break; + } + return match; } -- 2.14.3