From: Ido Schimmel <idosch@idosch.org>
To: cpaasch@openai.com
Cc: David Ahern <dsahern@kernel.org>,
Nikolay Aleksandrov <razor@blackwall.org>,
"David S. Miller" <davem@davemloft.net>,
Eric Dumazet <edumazet@google.com>,
Jakub Kicinski <kuba@kernel.org>, Paolo Abeni <pabeni@redhat.com>,
Simon Horman <horms@kernel.org>,
netdev@vger.kernel.org
Subject: Re: [PATCH net-next v2 1/2] net: Make nexthop-dumps scale linearly with the number of nexthops
Date: Sun, 17 Aug 2025 11:42:32 +0300 [thread overview]
Message-ID: <aKGV-OQ_EO749Xi0@shredder> (raw)
In-Reply-To: <20250816-nexthop_dump-v2-1-491da3462118@openai.com>
On Sat, Aug 16, 2025 at 04:12:48PM -0700, Christoph Paasch via B4 Relay wrote:
> From: Christoph Paasch <cpaasch@openai.com>
>
> When we have a (very) large number of nexthops, they do not fit within a
> single message. rtm_dump_walk_nexthops() thus will be called repeatedly
> and ctx->idx is used to avoid dumping the same nexthops again.
>
> The approach in which we avoid dumping the same nexthops is by basically
> walking the entire nexthop rb-tree from the left-most node until we find
> a node whose id is >= s_idx. That does not scale well.
>
> Instead of this inefficient approach, rather go directly through the
> tree to the nexthop that should be dumped (the one whose nh_id >=
> s_idx). This allows us to find the relevant node in O(log(n)).
[...]
> Signed-off-by: Christoph Paasch <cpaasch@openai.com>
Reviewed-by: Ido Schimmel <idosch@nvidia.com>
next prev parent reply other threads:[~2025-08-17 8:42 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-08-16 23:12 [PATCH net-next v2 0/2] net: Speedup some nexthop handling when having A LOT of nexthops Christoph Paasch via B4 Relay
2025-08-16 23:12 ` [PATCH net-next v2 1/2] net: Make nexthop-dumps scale linearly with the number " Christoph Paasch via B4 Relay
2025-08-17 8:42 ` Ido Schimmel [this message]
2025-08-17 9:40 ` Nikolay Aleksandrov
2025-08-18 9:54 ` Eric Dumazet
2025-08-16 23:12 ` [PATCH net-next v2 2/2] net: When removing nexthops, don't call synchronize_net if it is not necessary Christoph Paasch via B4 Relay
2025-08-17 8:44 ` Ido Schimmel
2025-08-17 9:40 ` Nikolay Aleksandrov
2025-08-18 10:02 ` Eric Dumazet
2025-08-18 13:33 ` [PATCH net-next v2 0/2] net: Speedup some nexthop handling when having A LOT of nexthops David Ahern
2025-08-20 1:00 ` patchwork-bot+netdevbpf
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=aKGV-OQ_EO749Xi0@shredder \
--to=idosch@idosch.org \
--cc=cpaasch@openai.com \
--cc=davem@davemloft.net \
--cc=dsahern@kernel.org \
--cc=edumazet@google.com \
--cc=horms@kernel.org \
--cc=kuba@kernel.org \
--cc=netdev@vger.kernel.org \
--cc=pabeni@redhat.com \
--cc=razor@blackwall.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox