From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from fhigh-a8-smtp.messagingengine.com (fhigh-a8-smtp.messagingengine.com [103.168.172.159]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B5C24221275 for ; Sun, 17 Aug 2025 08:42:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.159 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1755420160; cv=none; b=HEPhV36ca051R9JtAXK8SdCBo7UHH9kWoCbhJa0OUz+0AWmLhMKPDI0V2O9G50tb/OnRN6myYyvIeCxSsK0PqHAfBXulcp7lG5u6Wy0YyKZzopEZLLmuWs1H05ZqEAfe8INuJACq9A5eYLdpQ+PB+oHiVlESgl4TZKSilqVovQw= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1755420160; c=relaxed/simple; bh=skk3bwgggwxUoahjfYSH2fe5PRYax27kvyegnDosuRU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=GMl5tAzc+kq4TXCWUEqRhzfe66LHix5skFHFYfNEO3SUCJH1Bhr87M/AfPwd5Y0ZOXsR8Huda6c4dpVXu1cAlDHjfAyr2yLsM5big2In/u+vE7p4l2FjxmDPFxDNqS5yfKGdeVD8Yp3QE/jD2HOeonXb+WgWhvaJT5UUwqEtK0Y= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=idosch.org; spf=none smtp.mailfrom=idosch.org; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=ZWjl7Beo; arc=none smtp.client-ip=103.168.172.159 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=idosch.org Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=idosch.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="ZWjl7Beo" Received: from phl-compute-12.internal (phl-compute-12.internal [10.202.2.52]) by mailfhigh.phl.internal (Postfix) with ESMTP id 9FC201400041; Sun, 17 Aug 2025 04:42:36 -0400 (EDT) Received: from phl-mailfrontend-02 ([10.202.2.163]) by phl-compute-12.internal (MEProxy); Sun, 17 Aug 2025 04:42:36 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:subject:subject:to :to:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; t= 1755420156; x=1755506556; bh=UBxAH3Eqra2xQGOBIjcZa79z0oTxuD2RIWt YKIdUirI=; b=ZWjl7BeooIrut4NFAQze2EfAJUo3X/3wSGU80HnOJV22XttbR9W X/UWjQM1T/JtH1jF7dE9xtD6q+OYhtO+Va0XmDj1gqGDrN+9BMARdzXKVptZnwxI TtpCUKa8jL/2SJDIexvOLVe/LZM57vrdLefyma32muxm8UFEMyeufv4jRmGltsy1 sNxKN8h9dy/Lp/0UzESW396pe1ySrega6f/pPxy9EtrLEIqCUm1JMz6RybaRaR+4 lhRkLJYlyEa/TO+nVB4p9GlaqUextCSTiY0RRHmoNvIai3KoXxxbbOqaMH/Fcjvr z84hdl1FBRMQsZfIERtB+aC3563l2qtg/JQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeeffedrtdefgddugeelvdekucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfurfetoffkrfgpnffqhgenuceu rghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujf gurhepfffhvfevuffkfhggtggujgesthdtredttddtvdenucfhrhhomhepkfguohcuufgt hhhimhhmvghluceoihguohhstghhsehiughoshgthhdrohhrgheqnecuggftrfgrthhtvg hrnhepvddufeevkeehueegfedtvdevfefgudeifeduieefgfelkeehgeelgeejjeeggefh necuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepihguoh hstghhsehiughoshgthhdrohhrghdpnhgspghrtghpthhtohepledpmhhouggvpehsmhht phhouhhtpdhrtghpthhtoheptghprggrshgthhesohhpvghnrghirdgtohhmpdhrtghpth htohepughsrghhvghrnheskhgvrhhnvghlrdhorhhgpdhrtghpthhtoheprhgriihorhes sghlrggtkhifrghllhdrohhrghdprhgtphhtthhopegurghvvghmsegurghvvghmlhhofh htrdhnvghtpdhrtghpthhtohepvgguuhhmrgiivghtsehgohhoghhlvgdrtghomhdprhgt phhtthhopehkuhgsrgeskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepphgrsggvnhhise hrvgguhhgrthdrtghomhdprhgtphhtthhopehhohhrmhhssehkvghrnhgvlhdrohhrghdp rhgtphhtthhopehnvghtuggvvhesvhhgvghrrdhkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i494840e7:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sun, 17 Aug 2025 04:42:35 -0400 (EDT) Date: Sun, 17 Aug 2025 11:42:32 +0300 From: Ido Schimmel To: cpaasch@openai.com Cc: David Ahern , Nikolay Aleksandrov , "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , Simon Horman , netdev@vger.kernel.org Subject: Re: [PATCH net-next v2 1/2] net: Make nexthop-dumps scale linearly with the number of nexthops Message-ID: References: <20250816-nexthop_dump-v2-0-491da3462118@openai.com> <20250816-nexthop_dump-v2-1-491da3462118@openai.com> Precedence: bulk X-Mailing-List: netdev@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline 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 > > 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 Reviewed-by: Ido Schimmel