[PATCH net-next v2 0/3] net: hash uncached route lists by device

[PATCH net-next v2 0/3] net: hash uncached route lists by device

[Chris J Arges]

We have observed hung tasks blocked on rtnl_mutex while network namespaces
were being removed. The namespaces contained many network devices, and the
host had accumulated a large population of entries on the global per-CPU
uncached route lists. A perf profile collected during one incident
attributed most of the cleanup worker's samples to rt_flush_dev():

```
99.92% kworker/u384:3-  worker_thread
  `-88.71% process_one_work
      `-81.02% cleanup_net
          `-81.00% unregister_netdevice_many_notify
              `-79.42% notifier_call_chain
                  `-78.05% fib_netdev_event
                      `-77.92% rt_flush_dev
```

For each device, rt_flush_dev() visits every possible CPU and scans the
global uncached route population while its caller holds rtnl_mutex. If N is
the number of devices, C the number of possible CPUs, and R the number of
uncached routes, the cost is O(N * (C + R)).

During namespace cleanup, other processes that issue RTNETLINK operations
requiring the RTNL lock can stall until cleanup releases the lock.

A minimal reproducer is available here:
https://github.com/arges/linux-reproducers/tree/main/rtnl-flush-storm

This series replaces each per-CPU uncached route list with a hash table
keyed by the route's network device. The bucket count defaults to 64 and is
configurable separately for IPv4 and IPv6. IPv6 routes need additional
handling because dst.dev and rt6i_idev->dev can refer to different devices.
Such routes use a separate per-CPU list that is visited in addition to the
device's hash bucket. Routes whose device references are equal use only the
hash bucket.

We measured user-visible RTNL latency on a 192-CPU x86-64 host. The test
added approximately 80,000 uncached routes across 256 devices simulating a
distribution we saw in production with 6 devices having 4k to 20k routes,
and all others holding ~100 routes. The devices being removed owned none
of these routes.

During asynchronous namespace cleanup, the test repeatedly sends an
idempotent RTM_NEWLINK request that requires RTNL. It then records the
worst request-to-acknowledgment latency in each observation window.

Results from this test show the median latency for the RTM_NEWLINK request
to complete after waiting for unregsiter batch show between 68-75%
reduction in latency when using the patch.

We also measured end-to-end route insertion cost separately on the same
machine. The test inserted 100,000 routes per round for 30 rounds after
three warmups, while pinned to one CPU. Median insertion cost was
2,069 ns/op without hashing and 2,066 ns/op with hashing. This test found
no measurable insertion regression.

The hash approach adds no per-route fields. On x86-64, the tables add
approximately 3 KiB per possible CPU with the default configuration.

Patch 1 hashes IPv4 uncached routes by network device.
Patch 2 applies the hashing design to IPv6 and handles routes whose device
references differ.
Patch 3 adds a selftest for the IPv6 case.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
Changes in v2:
- Add IPv4 and IPv6 Kconfig options for the uncached-route hash size.
- Keep 64 buckets as the default and document the per-CPU memory tradeoff.
- Link to v1: https://patch.msgid.link/20260826-hash-bucket-route-lists-v1-0-fa9b9f30eb74@cloudflare.com

To: "David S. Miller" <davem@davemloft.net>
To: Eric Dumazet <edumazet@google.com>
To: Jakub Kicinski <kuba@kernel.org>
To: Paolo Abeni <pabeni@redhat.com>
To: Simon Horman <horms@kernel.org>
To: David Ahern <dsahern@kernel.org>
To: Ido Schimmel <idosch@nvidia.com>
To: Shuah Khan <shuah@kernel.org>
Cc: netdev@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
Cc: linux-kselftest@vger.kernel.org

---
Chris J Arges (3):
      ipv4: hash uncached routes by device
      ipv6: hash uncached routes by device
      selftests: net: cover IPv6 uncached route device mismatch

 net/ipv4/Kconfig                              |  13 ++++
 net/ipv4/route.c                              |  36 +++++++--
 net/ipv6/Kconfig                              |  13 ++++
 net/ipv6/route.c                              | 102 +++++++++++++++++---------
 tools/testing/selftests/net/vrf-xfrm-tests.sh |  35 +++++++++
 5 files changed, 159 insertions(+), 40 deletions(-)
---
base-commit: 879e280b8486d4612ad1aa050d6fada2dd80cf1c
change-id: 20260820-hash-bucket-route-lists-b8cc27ccd53c

Best regards,
--  
Chris J Arges <carges@cloudflare.com>

[PATCH net-next v2 1/3] ipv4: hash uncached routes by device

[Chris J Arges]

rt_flush_dev() currently walks every per-CPU uncached route list for each
device being removed. This repeatedly examines unrelated routes and makes
teardown increasingly expensive as the number of devices grows.

Replace each per-CPU list with a hash table keyed by the route's netdevice.
Keep the owning-list pointer in dst_entry so route removal remains
unchanged, while device teardown only walks the matching bucket on each
CPU. Hash collisions are filtered by the existing device comparison.

The table has 2^CONFIG_IP_UNCACHED_ROUTE_HASH_BITS buckets and defaults to
64. Larger values shorten each bucket, but every additional bit doubles the
per-CPU memory used by the table. The default costs approximately 1.5 KiB
per possible CPU on x86-64.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
 net/ipv4/Kconfig | 13 +++++++++++++
 net/ipv4/route.c | 36 +++++++++++++++++++++++++++++-------
 2 files changed, 42 insertions(+), 7 deletions(-)

diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index 301b47660305..7d40ca22d2b2 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig
@@ -103,6 +103,19 @@ config IP_ROUTE_VERBOSE
 config IP_ROUTE_CLASSID
 	bool
 
+config IP_UNCACHED_ROUTE_HASH_BITS
+	int "IPv4 uncached route hash bits"
+	range 1 10
+	default 6
+	help
+	  This option sets the number of buckets used in the IPv4 uncached
+	  route hash table to 2^IP_UNCACHED_ROUTE_HASH_BITS buckets. The
+	  allowed values select between 2 and 1024 buckets. Larger values
+	  reduce collisions, but each additional bit doubles the per-CPU
+	  memory used by the table.
+
+	  If unsure, use the default of 6 bits (64 buckets).
+
 config IP_PNP
 	bool "IP: kernel level autoconfiguration"
 	help
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index d7da2f1acbb5..e28e2140cf62 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -74,6 +74,7 @@
 #include <linux/init.h>
 #include <linux/skbuff.h>
 #include <linux/inetdevice.h>
+#include <linux/hash.h>
 #include <linux/igmp.h>
 #include <linux/pkt_sched.h>
 #include <linux/mroute.h>
@@ -1552,11 +1553,21 @@ struct uncached_list {
 	struct list_head	head;
 };
 
-static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt_uncached_list);
+#define RT_UNCACHED_HASH_SIZE	BIT(CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)
+
+struct uncached_table {
+	struct uncached_list buckets[RT_UNCACHED_HASH_SIZE];
+};
+
+static DEFINE_PER_CPU_ALIGNED(struct uncached_table, rt_uncached_table);
 
 void rt_add_uncached_list(struct rtable *rt)
 {
-	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
+	struct uncached_table *table = raw_cpu_ptr(&rt_uncached_table);
+	struct uncached_list *ul;
+
+	ul = &table->buckets[hash_ptr(dst_dev(&rt->dst),
+				      CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)];
 
 	rt->dst.rt_uncached_list = ul;
 
@@ -1588,14 +1599,19 @@ void rt_flush_dev(struct net_device *dev)
 	int cpu;
 
 	for_each_possible_cpu(cpu) {
-		struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
+		struct uncached_table *table;
+		struct uncached_list *ul;
+
+		table = per_cpu_ptr(&rt_uncached_table, cpu);
+		ul = &table->buckets[hash_ptr(dev,
+					      CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)];
 
 		if (list_empty(&ul->head))
 			continue;
 
 		spin_lock_bh(&ul->lock);
 		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
-			if (rt->dst.dev != dev)
+			if (dst_dev(&rt->dst) != dev)
 				continue;
 			rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
 			netdev_ref_replace(dev, blackhole_netdev,
@@ -3771,10 +3787,16 @@ int __init ip_rt_init(void)
 	ip_tstamps = idents_hash + (ip_idents_mask + 1) * sizeof(*ip_idents);
 
 	for_each_possible_cpu(cpu) {
-		struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
+		struct uncached_table *table;
+		int bucket;
+
+		table = per_cpu_ptr(&rt_uncached_table, cpu);
+		for (bucket = 0; bucket < RT_UNCACHED_HASH_SIZE; bucket++) {
+			struct uncached_list *ul = &table->buckets[bucket];
 
-		INIT_LIST_HEAD(&ul->head);
-		spin_lock_init(&ul->lock);
+			INIT_LIST_HEAD(&ul->head);
+			spin_lock_init(&ul->lock);
+		}
 	}
 #ifdef CONFIG_IP_ROUTE_CLASSID
 	ip_rt_acct = __alloc_percpu(256 * sizeof(struct ip_rt_acct), __alignof__(struct ip_rt_acct));

-- 
2.43.0

[PATCH net-next v2 2/3] ipv6: hash uncached routes by device

[Chris J Arges]

rt6_uncached_list_flush_dev() currently walks every per-CPU uncached route
list for each device being removed. Hash uncached routes by their inet6
device so ordinary device teardown only visits the matching bucket on each
CPU.

ip6_rt_get_dev_rcu() can return loopback or an L3 master while rt6i_idev
still refers to the original interface, so such a route must be reachable
from either device. Place those routes on a separate per-CPU list that is
always visited in addition to the keyed bucket.

This avoids growing struct rt6_info while filtering most unrelated routes
from ordinary device teardown.

The table has 2^CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS buckets and defaults
to 64. Larger values shorten each bucket, but every additional bit doubles
the per-CPU memory used by the table. The default costs approximately
1.5 KiB per possible CPU on x86-64.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
 net/ipv6/Kconfig |  13 +++++++
 net/ipv6/route.c | 102 +++++++++++++++++++++++++++++++++++++------------------
 2 files changed, 82 insertions(+), 33 deletions(-)

diff --git a/net/ipv6/Kconfig b/net/ipv6/Kconfig
index c3806c6ac96f..0253178668bd 100644
--- a/net/ipv6/Kconfig
+++ b/net/ipv6/Kconfig
@@ -18,6 +18,19 @@ menuconfig IPV6
 
 if IPV6
 
+config IPV6_UNCACHED_ROUTE_HASH_BITS
+	int "IPv6 uncached route hash bits"
+	range 1 10
+	default 6
+	help
+	  This option sets the number of buckets used in the IPv6 uncached
+	  route hash table to 2^IPV6_UNCACHED_ROUTE_HASH_BITS buckets. The
+	  allowed values select between 2 and 1024 buckets. Larger values
+	  reduce collisions, but each additional bit doubles the per-CPU
+	  memory used by the table.
+
+	  If unsure, use the default of 6 bits (64 buckets).
+
 config IPV6_ROUTER_PREF
 	bool "IPv6: Router Preference (RFC 4191) support"
 	help
diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index 7535b09068a0..080dce329168 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -40,6 +40,7 @@
 #include <linux/seq_file.h>
 #include <linux/nsproxy.h>
 #include <linux/slab.h>
+#include <linux/hash.h>
 #include <linux/jhash.h>
 #include <linux/siphash.h>
 #include <net/net_namespace.h>
@@ -133,11 +134,27 @@ struct uncached_list {
 	struct list_head	head;
 };
 
-static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
+#define RT6_UNCACHED_HASH_SIZE	BIT(CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)
+
+struct rt6_uncached_table {
+	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
+	/* Routes that must be discoverable through two different devices. */
+	struct uncached_list mismatch;
+};
+
+static DEFINE_PER_CPU_ALIGNED(struct rt6_uncached_table, rt6_uncached_table);
 
 void rt6_uncached_list_add(struct rt6_info *rt)
 {
-	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
+	struct rt6_uncached_table *table = raw_cpu_ptr(&rt6_uncached_table);
+	struct net_device *rt_dev = dst_dev(&rt->dst);
+	struct uncached_list *ul;
+
+	if (rt->rt6i_idev && rt->rt6i_idev->dev != rt_dev)
+		ul = &table->mismatch;
+	else
+		ul = &table->buckets[hash_ptr(rt_dev,
+					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
 
 	rt->dst.rt_uncached_list = ul;
 
@@ -157,40 +174,51 @@ void rt6_uncached_list_del(struct rt6_info *rt)
 	}
 }
 
+static void rt6_uncached_list_flush(struct uncached_list *ul,
+				    struct net_device *dev)
+{
+	struct rt6_info *rt, *safe;
+
+	if (list_empty(&ul->head))
+		return;
+
+	spin_lock_bh(&ul->lock);
+	list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
+		struct inet6_dev *rt_idev = rt->rt6i_idev;
+		struct net_device *rt_dev = dst_dev(&rt->dst);
+		bool handled = false;
+
+		if (rt_idev && rt_idev->dev == dev) {
+			rt->rt6i_idev = in6_dev_get(blackhole_netdev);
+			in6_dev_put(rt_idev);
+			handled = true;
+		}
+
+		if (rt_dev == dev) {
+			rt->dst.dev = blackhole_netdev;
+			netdev_ref_replace(rt_dev, blackhole_netdev,
+					   &rt->dst.dev_tracker, GFP_ATOMIC);
+			handled = true;
+		}
+		if (handled)
+			list_del_init(&rt->dst.rt_uncached);
+	}
+	spin_unlock_bh(&ul->lock);
+}
+
 static void rt6_uncached_list_flush_dev(struct net_device *dev)
 {
 	int cpu;
 
 	for_each_possible_cpu(cpu) {
-		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
-		struct rt6_info *rt, *safe;
+		struct rt6_uncached_table *table;
+		struct uncached_list *ul;
 
-		if (list_empty(&ul->head))
-			continue;
-
-		spin_lock_bh(&ul->lock);
-		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
-			struct inet6_dev *rt_idev = rt->rt6i_idev;
-			struct net_device *rt_dev = rt->dst.dev;
-			bool handled = false;
-
-			if (rt_idev && rt_idev->dev == dev) {
-				rt->rt6i_idev = in6_dev_get(blackhole_netdev);
-				in6_dev_put(rt_idev);
-				handled = true;
-			}
-
-			if (rt_dev == dev) {
-				rt->dst.dev = blackhole_netdev;
-				netdev_ref_replace(rt_dev, blackhole_netdev,
-						   &rt->dst.dev_tracker,
-						   GFP_ATOMIC);
-				handled = true;
-			}
-			if (handled)
-				list_del_init(&rt->dst.rt_uncached);
-		}
-		spin_unlock_bh(&ul->lock);
+		table = per_cpu_ptr(&rt6_uncached_table, cpu);
+		ul = &table->buckets[hash_ptr(dev,
+					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
+		rt6_uncached_list_flush(ul, dev);
+		rt6_uncached_list_flush(&table->mismatch, dev);
 	}
 }
 
@@ -6987,10 +7015,18 @@ int __init ip6_route_init(void)
 #endif
 
 	for_each_possible_cpu(cpu) {
-		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
+		struct rt6_uncached_table *table;
+		int bucket;
+
+		table = per_cpu_ptr(&rt6_uncached_table, cpu);
+		for (bucket = 0; bucket < RT6_UNCACHED_HASH_SIZE; bucket++) {
+			struct uncached_list *ul = &table->buckets[bucket];
 
-		INIT_LIST_HEAD(&ul->head);
-		spin_lock_init(&ul->lock);
+			INIT_LIST_HEAD(&ul->head);
+			spin_lock_init(&ul->lock);
+		}
+		INIT_LIST_HEAD(&table->mismatch.head);
+		spin_lock_init(&table->mismatch.lock);
 	}
 
 out:

-- 
2.43.0

[PATCH net-next v2 3/3] selftests: net: cover IPv6 uncached route device mismatch

[Chris J Arges]

Local IPv6 routes through a VRF can use the VRF as dst.dev while
retaining the VRF member interface in rt6i_idev. Exercise device
teardown while such uncached routes are retained by a delayed qdisc.

Reuse the existing VRF topology and msg_zerocopy raw-header sender, and
verify route creation, qdisc retention, and prompt interface deletion.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
 tools/testing/selftests/net/vrf-xfrm-tests.sh | 35 +++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/tools/testing/selftests/net/vrf-xfrm-tests.sh b/tools/testing/selftests/net/vrf-xfrm-tests.sh
index b64dd891699d..4f409d135a99 100755
--- a/tools/testing/selftests/net/vrf-xfrm-tests.sh
+++ b/tools/testing/selftests/net/vrf-xfrm-tests.sh
@@ -385,6 +385,37 @@ run_tests()
 	cleanup_xfrm_dev
 }
 
+test_ipv6_uncached_mismatch()
+{
+	local sender_pid
+	local backlog
+	local rc
+
+	# A local route through a VRF uses the VRF as dst.dev while retaining
+	# the VRF member interface in rt6i_idev. Raw header sends create uncached
+	# routes, and netem keeps them referenced while the interface is deleted.
+	run_cmd_host1 tc qdisc replace dev ${VRF} root netem limit 1 delay 10s
+	ip -6 -netns "$host1" route add local ${HOST1_6}/128 dev eth0
+	ip netns exec "$host1" ./msg_zerocopy -6 \
+		-S ${HOST1_6} -D ${HOST1_6} -s 1200 -t 0 raw_hdrincl \
+		>/dev/null 2>&1 &
+	sender_pid=$!
+	wait "$sender_pid"
+	rc=$?
+	log_test $rc 0 "Create uncached IPv6 routes with mismatched devices"
+	[ $rc -ne 0 ] && return
+
+	backlog=$(ip netns exec "$host1" tc -s qdisc show dev ${VRF})
+	if ! echo "$backlog" | grep -Eq 'backlog .* [1-9][0-9]*p'; then
+		log_test 1 0 "Retain uncached IPv6 routes in VRF qdisc"
+		return
+	fi
+	log_test 0 0 "Retain uncached IPv6 routes in VRF qdisc"
+
+	run_cmd_host1 timeout 2 ip link del eth0
+	log_test $? 0 "Flush uncached IPv6 routes with mismatched devices"
+}
+
 ################################################################################
 # usage
 
@@ -425,6 +456,10 @@ echo
 echo "netem qdisc on VRF device"
 run_tests
 
+echo
+echo "Uncached IPv6 route with mismatched devices"
+test_ipv6_uncached_mismatch
+
 printf "\nTests passed: %3d\n" ${nsuccess}
 printf "Tests failed: %3d\n"   ${nfail}
 

-- 
2.43.0

Re: [PATCH net-next v2 1/3] ipv4: hash uncached routes by device

[Ido Schimmel]

On Mon, Sep 14, 2026 at 09:03:35PM -0500, Chris J Arges wrote:
> rt_flush_dev() currently walks every per-CPU uncached route list for each
> device being removed. This repeatedly examines unrelated routes and makes
> teardown increasingly expensive as the number of devices grows.
> 
> Replace each per-CPU list with a hash table keyed by the route's netdevice.
> Keep the owning-list pointer in dst_entry so route removal remains
> unchanged, while device teardown only walks the matching bucket on each
> CPU. Hash collisions are filtered by the existing device comparison.
> 
> The table has 2^CONFIG_IP_UNCACHED_ROUTE_HASH_BITS buckets and defaults to
> 64. Larger values shorten each bucket, but every additional bit doubles the
> per-CPU memory used by the table. The default costs approximately 1.5 KiB
> per possible CPU on x86-64.

We have a lot of hash tables, but I only found a few similar knobs under
net/: A few in IPVS (IP_VS_TAB_BITS, IP_VS_SH_TAB_BITS and
IP_VS_MH_TAB_INDEX) and INET_TABLE_PERTURB_ORDER.

The latter is hidden behind EXPERT and was added by commit aeac4ec8f46d
("tcp: configurable source port perturb table size") in order to save
memory on embedded systems (not to tune the hash, as in this case). I
don't think the memory saving argument is relevant here given the last
sentence in the commit message.

Even in the thread that Jakub referenced, DaveM wrote that "It should be
dynamically sized. Compile time configuration knobs generally stick" [1]
and I suspect that this is exactly what is going to happen here.

A "dynamically sized" solution can be a per-CPU uncached list for each
net device, but it's more complex than what you implemented and will
also increase the memory usage per-netdev.

So, I think that a fixed size hash table with 64 buckets is a good
starting point and it can be refined later, if needed.

[1] https://lore.kernel.org/netdev/20110131.140503.179938794.davem@davemloft.net/

Re: [PATCH net-next v2 2/3] ipv6: hash uncached routes by device

[Ido Schimmel]

On Mon, Sep 14, 2026 at 09:03:36PM -0500, Chris J Arges wrote:
> rt6_uncached_list_flush_dev() currently walks every per-CPU uncached route
> list for each device being removed. Hash uncached routes by their inet6
> device so ordinary device teardown only visits the matching bucket on each
> CPU.

The code is doing something else and hashing using dst_dev():

	struct net_device *rt_dev = dst_dev(&rt->dst);
[...]
		ul = &table->buckets[hash_ptr(rt_dev,
					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];

> 
> ip6_rt_get_dev_rcu() can return loopback or an L3 master while rt6i_idev
> still refers to the original interface, so such a route must be reachable
> from either device. Place those routes on a separate per-CPU list that is
> always visited in addition to the keyed bucket.
> 
> This avoids growing struct rt6_info while filtering most unrelated routes
> from ordinary device teardown.
> 
> The table has 2^CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS buckets and defaults
> to 64. Larger values shorten each bucket, but every additional bit doubles
> the per-CPU memory used by the table. The default costs approximately
> 1.5 KiB per possible CPU on x86-64.
> 
> Signed-off-by: Chris J Arges <carges@cloudflare.com>
> ---
>  net/ipv6/Kconfig |  13 +++++++

Same comment as in patch 1 about the Kconfig.

>  net/ipv6/route.c | 102 +++++++++++++++++++++++++++++++++++++------------------
>  2 files changed, 82 insertions(+), 33 deletions(-)
> 
> diff --git a/net/ipv6/Kconfig b/net/ipv6/Kconfig
> index c3806c6ac96f..0253178668bd 100644
> --- a/net/ipv6/Kconfig
> +++ b/net/ipv6/Kconfig
> @@ -18,6 +18,19 @@ menuconfig IPV6
>  
>  if IPV6
>  
> +config IPV6_UNCACHED_ROUTE_HASH_BITS
> +	int "IPv6 uncached route hash bits"
> +	range 1 10
> +	default 6
> +	help
> +	  This option sets the number of buckets used in the IPv6 uncached
> +	  route hash table to 2^IPV6_UNCACHED_ROUTE_HASH_BITS buckets. The
> +	  allowed values select between 2 and 1024 buckets. Larger values
> +	  reduce collisions, but each additional bit doubles the per-CPU
> +	  memory used by the table.
> +
> +	  If unsure, use the default of 6 bits (64 buckets).
> +
>  config IPV6_ROUTER_PREF
>  	bool "IPv6: Router Preference (RFC 4191) support"
>  	help
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index 7535b09068a0..080dce329168 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -40,6 +40,7 @@
>  #include <linux/seq_file.h>
>  #include <linux/nsproxy.h>
>  #include <linux/slab.h>
> +#include <linux/hash.h>
>  #include <linux/jhash.h>
>  #include <linux/siphash.h>
>  #include <net/net_namespace.h>
> @@ -133,11 +134,27 @@ struct uncached_list {
>  	struct list_head	head;
>  };
>  
> -static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
> +#define RT6_UNCACHED_HASH_SIZE	BIT(CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)
> +
> +struct rt6_uncached_table {
> +	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
> +	/* Routes that must be discoverable through two different devices. */
> +	struct uncached_list mismatch;
> +};
> +
> +static DEFINE_PER_CPU_ALIGNED(struct rt6_uncached_table, rt6_uncached_table);
>  
>  void rt6_uncached_list_add(struct rt6_info *rt)
>  {
> -	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
> +	struct rt6_uncached_table *table = raw_cpu_ptr(&rt6_uncached_table);
> +	struct net_device *rt_dev = dst_dev(&rt->dst);
> +	struct uncached_list *ul;
> +
> +	if (rt->rt6i_idev && rt->rt6i_idev->dev != rt_dev)
> +		ul = &table->mismatch;
> +	else
> +		ul = &table->buckets[hash_ptr(rt_dev,
> +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
>  
>  	rt->dst.rt_uncached_list = ul;
>  
> @@ -157,40 +174,51 @@ void rt6_uncached_list_del(struct rt6_info *rt)
>  	}
>  }
>  
> +static void rt6_uncached_list_flush(struct uncached_list *ul,
> +				    struct net_device *dev)
> +{
> +	struct rt6_info *rt, *safe;
> +
> +	if (list_empty(&ul->head))
> +		return;
> +
> +	spin_lock_bh(&ul->lock);
> +	list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> +		struct inet6_dev *rt_idev = rt->rt6i_idev;
> +		struct net_device *rt_dev = dst_dev(&rt->dst);
> +		bool handled = false;

https://docs.kernel.org/next/process/maintainer-netdev.html#local-variable-ordering-reverse-xmas-tree-rcs

> +
> +		if (rt_idev && rt_idev->dev == dev) {
> +			rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> +			in6_dev_put(rt_idev);
> +			handled = true;
> +		}
> +
> +		if (rt_dev == dev) {
> +			rt->dst.dev = blackhole_netdev;

Please use:

rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);

See commit 1469773b246a ("ipv4: use rcu_assign_pointer() in
rt_flush_dev()")

> +			netdev_ref_replace(rt_dev, blackhole_netdev,
> +					   &rt->dst.dev_tracker, GFP_ATOMIC);
> +			handled = true;
> +		}
> +		if (handled)
> +			list_del_init(&rt->dst.rt_uncached);
> +	}
> +	spin_unlock_bh(&ul->lock);
> +}
> +
>  static void rt6_uncached_list_flush_dev(struct net_device *dev)
>  {
>  	int cpu;
>  
>  	for_each_possible_cpu(cpu) {
> -		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
> -		struct rt6_info *rt, *safe;
> +		struct rt6_uncached_table *table;
> +		struct uncached_list *ul;
>  
> -		if (list_empty(&ul->head))
> -			continue;
> -
> -		spin_lock_bh(&ul->lock);
> -		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> -			struct inet6_dev *rt_idev = rt->rt6i_idev;
> -			struct net_device *rt_dev = rt->dst.dev;
> -			bool handled = false;
> -
> -			if (rt_idev && rt_idev->dev == dev) {
> -				rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> -				in6_dev_put(rt_idev);
> -				handled = true;
> -			}
> -
> -			if (rt_dev == dev) {
> -				rt->dst.dev = blackhole_netdev;
> -				netdev_ref_replace(rt_dev, blackhole_netdev,
> -						   &rt->dst.dev_tracker,
> -						   GFP_ATOMIC);
> -				handled = true;
> -			}
> -			if (handled)
> -				list_del_init(&rt->dst.rt_uncached);
> -		}
> -		spin_unlock_bh(&ul->lock);
> +		table = per_cpu_ptr(&rt6_uncached_table, cpu);
> +		ul = &table->buckets[hash_ptr(dev,
> +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
> +		rt6_uncached_list_flush(ul, dev);
> +		rt6_uncached_list_flush(&table->mismatch, dev);

The mismatch list can be quite long depending on the workload and every
device needs to walk it for every CPU.

AFAICT, when there is a mismatch, dst_dev() is either loopback or a VRF
device. Can you instead hash based on rt6i_idev->dev (fallback to
dst_dev() when not available) and only iterate over all the buckets when
the device that is going away is loopback / VRF?

That way, in the common case, you only need to walk one list per-CPU.

>  	}
>  }
>  
> @@ -6987,10 +7015,18 @@ int __init ip6_route_init(void)
>  #endif
>  
>  	for_each_possible_cpu(cpu) {
> -		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
> +		struct rt6_uncached_table *table;
> +		int bucket;
> +
> +		table = per_cpu_ptr(&rt6_uncached_table, cpu);
> +		for (bucket = 0; bucket < RT6_UNCACHED_HASH_SIZE; bucket++) {
> +			struct uncached_list *ul = &table->buckets[bucket];
>  
> -		INIT_LIST_HEAD(&ul->head);
> -		spin_lock_init(&ul->lock);
> +			INIT_LIST_HEAD(&ul->head);
> +			spin_lock_init(&ul->lock);
> +		}
> +		INIT_LIST_HEAD(&table->mismatch.head);
> +		spin_lock_init(&table->mismatch.lock);
>  	}
>  
>  out:
> 
> -- 
> 2.43.0
> 

Re: [PATCH net-next v2 2/3] ipv6: hash uncached routes by device

[Chris Arges]

On 2026-09-17 13:14:05, Ido Schimmel wrote:
> On Mon, Sep 14, 2026 at 09:03:36PM -0500, Chris J Arges wrote:
> > rt6_uncached_list_flush_dev() currently walks every per-CPU uncached route
> > list for each device being removed. Hash uncached routes by their inet6
> > device so ordinary device teardown only visits the matching bucket on each
> > CPU.
> 
> The code is doing something else and hashing using dst_dev():
> 
> 	struct net_device *rt_dev = dst_dev(&rt->dst);
> [...]
> 		ul = &table->buckets[hash_ptr(rt_dev,
> 					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
> 
> > 
> > ip6_rt_get_dev_rcu() can return loopback or an L3 master while rt6i_idev
> > still refers to the original interface, so such a route must be reachable
> > from either device. Place those routes on a separate per-CPU list that is
> > always visited in addition to the keyed bucket.
> > 
> > This avoids growing struct rt6_info while filtering most unrelated routes
> > from ordinary device teardown.
> > 
> > The table has 2^CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS buckets and defaults
> > to 64. Larger values shorten each bucket, but every additional bit doubles
> > the per-CPU memory used by the table. The default costs approximately
> > 1.5 KiB per possible CPU on x86-64.
> > 
> > Signed-off-by: Chris J Arges <carges@cloudflare.com>
> > ---
> >  net/ipv6/Kconfig |  13 +++++++
> 
> Same comment as in patch 1 about the Kconfig.
> 
> >  net/ipv6/route.c | 102 +++++++++++++++++++++++++++++++++++++------------------
> >  2 files changed, 82 insertions(+), 33 deletions(-)
> > 
> > diff --git a/net/ipv6/Kconfig b/net/ipv6/Kconfig
> > index c3806c6ac96f..0253178668bd 100644
> > --- a/net/ipv6/Kconfig
> > +++ b/net/ipv6/Kconfig
> > @@ -18,6 +18,19 @@ menuconfig IPV6
> >  
> >  if IPV6
> >  
> > +config IPV6_UNCACHED_ROUTE_HASH_BITS
> > +	int "IPv6 uncached route hash bits"
> > +	range 1 10
> > +	default 6
> > +	help
> > +	  This option sets the number of buckets used in the IPv6 uncached
> > +	  route hash table to 2^IPV6_UNCACHED_ROUTE_HASH_BITS buckets. The
> > +	  allowed values select between 2 and 1024 buckets. Larger values
> > +	  reduce collisions, but each additional bit doubles the per-CPU
> > +	  memory used by the table.
> > +
> > +	  If unsure, use the default of 6 bits (64 buckets).
> > +
> >  config IPV6_ROUTER_PREF
> >  	bool "IPv6: Router Preference (RFC 4191) support"
> >  	help
> > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > index 7535b09068a0..080dce329168 100644
> > --- a/net/ipv6/route.c
> > +++ b/net/ipv6/route.c
> > @@ -40,6 +40,7 @@
> >  #include <linux/seq_file.h>
> >  #include <linux/nsproxy.h>
> >  #include <linux/slab.h>
> > +#include <linux/hash.h>
> >  #include <linux/jhash.h>
> >  #include <linux/siphash.h>
> >  #include <net/net_namespace.h>
> > @@ -133,11 +134,27 @@ struct uncached_list {
> >  	struct list_head	head;
> >  };
> >  
> > -static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
> > +#define RT6_UNCACHED_HASH_SIZE	BIT(CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)
> > +
> > +struct rt6_uncached_table {
> > +	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
> > +	/* Routes that must be discoverable through two different devices. */
> > +	struct uncached_list mismatch;
> > +};
> > +
> > +static DEFINE_PER_CPU_ALIGNED(struct rt6_uncached_table, rt6_uncached_table);
> >  
> >  void rt6_uncached_list_add(struct rt6_info *rt)
> >  {
> > -	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
> > +	struct rt6_uncached_table *table = raw_cpu_ptr(&rt6_uncached_table);
> > +	struct net_device *rt_dev = dst_dev(&rt->dst);
> > +	struct uncached_list *ul;
> > +
> > +	if (rt->rt6i_idev && rt->rt6i_idev->dev != rt_dev)
> > +		ul = &table->mismatch;
> > +	else
> > +		ul = &table->buckets[hash_ptr(rt_dev,
> > +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
> >  
> >  	rt->dst.rt_uncached_list = ul;
> >  
> > @@ -157,40 +174,51 @@ void rt6_uncached_list_del(struct rt6_info *rt)
> >  	}
> >  }
> >  
> > +static void rt6_uncached_list_flush(struct uncached_list *ul,
> > +				    struct net_device *dev)
> > +{
> > +	struct rt6_info *rt, *safe;
> > +
> > +	if (list_empty(&ul->head))
> > +		return;
> > +
> > +	spin_lock_bh(&ul->lock);
> > +	list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> > +		struct inet6_dev *rt_idev = rt->rt6i_idev;
> > +		struct net_device *rt_dev = dst_dev(&rt->dst);
> > +		bool handled = false;
> 
> https://docs.kernel.org/next/process/maintainer-netdev.html#local-variable-ordering-reverse-xmas-tree-rcs
> 
> > +
> > +		if (rt_idev && rt_idev->dev == dev) {
> > +			rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> > +			in6_dev_put(rt_idev);
> > +			handled = true;
> > +		}
> > +
> > +		if (rt_dev == dev) {
> > +			rt->dst.dev = blackhole_netdev;
> 
> Please use:
> 
> rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
> 
> See commit 1469773b246a ("ipv4: use rcu_assign_pointer() in
> rt_flush_dev()")
> 
> > +			netdev_ref_replace(rt_dev, blackhole_netdev,
> > +					   &rt->dst.dev_tracker, GFP_ATOMIC);
> > +			handled = true;
> > +		}
> > +		if (handled)
> > +			list_del_init(&rt->dst.rt_uncached);
> > +	}
> > +	spin_unlock_bh(&ul->lock);
> > +}
> > +
> >  static void rt6_uncached_list_flush_dev(struct net_device *dev)
> >  {
> >  	int cpu;
> >  
> >  	for_each_possible_cpu(cpu) {
> > -		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
> > -		struct rt6_info *rt, *safe;
> > +		struct rt6_uncached_table *table;
> > +		struct uncached_list *ul;
> >  
> > -		if (list_empty(&ul->head))
> > -			continue;
> > -
> > -		spin_lock_bh(&ul->lock);
> > -		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> > -			struct inet6_dev *rt_idev = rt->rt6i_idev;
> > -			struct net_device *rt_dev = rt->dst.dev;
> > -			bool handled = false;
> > -
> > -			if (rt_idev && rt_idev->dev == dev) {
> > -				rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> > -				in6_dev_put(rt_idev);
> > -				handled = true;
> > -			}
> > -
> > -			if (rt_dev == dev) {
> > -				rt->dst.dev = blackhole_netdev;
> > -				netdev_ref_replace(rt_dev, blackhole_netdev,
> > -						   &rt->dst.dev_tracker,
> > -						   GFP_ATOMIC);
> > -				handled = true;
> > -			}
> > -			if (handled)
> > -				list_del_init(&rt->dst.rt_uncached);
> > -		}
> > -		spin_unlock_bh(&ul->lock);
> > +		table = per_cpu_ptr(&rt6_uncached_table, cpu);
> > +		ul = &table->buckets[hash_ptr(dev,
> > +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
> > +		rt6_uncached_list_flush(ul, dev);
> > +		rt6_uncached_list_flush(&table->mismatch, dev);
> 
> The mismatch list can be quite long depending on the workload and every
> device needs to walk it for every CPU.
> 
> AFAICT, when there is a mismatch, dst_dev() is either loopback or a VRF
> device. Can you instead hash based on rt6i_idev->dev (fallback to
> dst_dev() when not available) and only iterate over all the buckets when
> the device that is going away is loopback / VRF?
> 
> That way, in the common case, you only need to walk one list per-CPU.

Ido,
Yea I like this approach much better. Thank you for the reviews.
I've re-tested and implemented your feedback into v3:
https://lore.kernel.org/all/20260917-hash-bucket-route-lists-v3-0-30493a37b6eb@cloudflare.com/
--chris

Re: [PATCH net-next v2 1/3] ipv4: hash uncached routes by device

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found 3 potential
issue(s) to consider:

Critical: 0 · High: 0 · Medium: 0 · Low: 3

- [Low] Performance-only change submitted with no measurement of the
  benefit it claims.
- [Low] Concern that the identical full per-CPU walk remains for IPv6 in
  rt6_uncached_list_flush_dev(), so on dual-stack hosts the scaling…
- [Low] The patch introduces a prompted (user-visible) Kconfig integer,
  IP_UNCACHED_ROUTE_HASH_BITS (net/ipv4/Kconfig:106-117), which becomes…

--

ipv4: hash uncached routes by device

This replaces the per-CPU uncached route list in net/ipv4/route.c with a
per-CPU hash table keyed on the route's netdevice, so rt_flush_dev() only
walks the bucket matching the device being removed.  The bucket count is a
new build-time Kconfig value, IP_UNCACHED_ROUTE_HASH_BITS, defaulting to 6.

> diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
> index 301b47660305b..7d40ca22d2b21 100644
> --- a/net/ipv4/Kconfig
> +++ b/net/ipv4/Kconfig
> @@ -103,6 +103,19 @@ config IP_ROUTE_VERBOSE
>  config IP_ROUTE_CLASSID
>  	bool
>  
> +config IP_UNCACHED_ROUTE_HASH_BITS
> +	int "IPv4 uncached route hash bits"
> +	range 1 10
> +	default 6
> +	help
> +	  This option sets the number of buckets used in the IPv4 uncached
> +	  route hash table to 2^IP_UNCACHED_ROUTE_HASH_BITS buckets. The
> +	  allowed values select between 2 and 1024 buckets. Larger values
> +	  reduce collisions, but each additional bit doubles the per-CPU
> +	  memory used by the table.
> +
> +	  If unsure, use the default of 6 bits (64 buckets).
> +

[Severity: Low]
Could the reasoning for making the bucket count a prompted Kconfig value be
spelled out?  The bucket count is baked in at build time:

	#define RT_UNCACHED_HASH_SIZE	BIT(CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)

	struct uncached_table {
		struct uncached_list buckets[RT_UNCACHED_HASH_SIZE];
	};

so this becomes a permanent user-visible interface.  Would a fixed constant,
or a size derived at ip_rt_init() time from nr_cpu_ids, work instead?

The help text says only "Larger values reduce collisions", which gives no
observable criterion for choosing a value, so is there anything a
distribution could measure to pick something other than the default?

Also, "range 1 10" allows 1 bit, i.e. two buckets.  Is that configuration
useful?  With two buckets the behaviour is essentially the pre-patch single
list plus a hash_ptr() call and one extra indirection in both
rt_add_uncached_list() and rt_flush_dev().  Should the low end of the range
start higher?

> diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> index d7da2f1acbb59..e28e2140cf621 100644
> --- a/net/ipv4/route.c
> +++ b/net/ipv4/route.c

[ ... ]

> @@ -1552,11 +1553,21 @@ struct uncached_list {
>  	struct list_head	head;
>  };
>  
> -static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt_uncached_list);
> +#define RT_UNCACHED_HASH_SIZE	BIT(CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)
> +
> +struct uncached_table {
> +	struct uncached_list buckets[RT_UNCACHED_HASH_SIZE];
> +};
> +
> +static DEFINE_PER_CPU_ALIGNED(struct uncached_table, rt_uncached_table);
>  
>  void rt_add_uncached_list(struct rtable *rt)
>  {
> -	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
> +	struct uncached_table *table = raw_cpu_ptr(&rt_uncached_table);
> +	struct uncached_list *ul;
> +
> +	ul = &table->buckets[hash_ptr(dst_dev(&rt->dst),
> +				      CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)];
>  
>  	rt->dst.rt_uncached_list = ul;

[Severity: Low]
Can before/after numbers be added for this?  The changelog motivates the
change entirely with "makes teardown increasingly expensive as the number of
devices grows", but there is no device count, no uncached route count, no
workload and no timing, so it is hard to tell at what scale the win appears.

The route insertion side also gets slightly more expensive and that is not
mentioned.  rt_add_uncached_list() now computes hash_ptr() and dereferences a
hash-selected bucket inside the per-CPU table instead of using a single
cacheline-aligned list head, and it is reached per uncached route creation
from rt_set_nexthop(), rt_cache_route(), ip_route_input_slow() and
xfrm4_fill_dst().  Was any effect measurable on those paths?

On the memory side, the changelog quantifies only the default in a
non-debug build ("approximately 1.5 KiB per possible CPU on x86-64"; 64
buckets x 24 bytes for struct uncached_list).  At the maximum allowed 10 bits
that is roughly 24 KiB per possible CPU, and with CONFIG_DEBUG_SPINLOCK or
CONFIG_DEBUG_LOCK_ALLOC struct uncached_list grows, multiplying both figures.
Could the changelog and the Kconfig help text state those cases too?

> @@ -1588,14 +1599,19 @@ void rt_flush_dev(struct net_device *dev)
>  	int cpu;
>  
>  	for_each_possible_cpu(cpu) {
> -		struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
> +		struct uncached_table *table;
> +		struct uncached_list *ul;
> +
> +		table = per_cpu_ptr(&rt_uncached_table, cpu);
> +		ul = &table->buckets[hash_ptr(dev,
> +					      CONFIG_IP_UNCACHED_ROUTE_HASH_BITS)];
>  
>  		if (list_empty(&ul->head))
>  			continue;
>  
>  		spin_lock_bh(&ul->lock);
>  		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> -			if (rt->dst.dev != dev)
> +			if (dst_dev(&rt->dst) != dev)
>  				continue;

[Severity: Low]
On a dual-stack host, is the same walk still paid for IPv6 after this patch?
fib_netdev_event() calls rt_flush_dev() on NETDEV_UNREGISTER, and the same
device removal also drives rt6_uncached_list_flush_dev(), which still does
the full per-CPU list walk:

	for_each_possible_cpu(cpu) {
		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);

The IPv6 flush also matches on two keys, rt->rt6i_idev->dev and
rt->dst.dev, so it cannot be converted the same way without handling the
case where those differ.

Checking the rest of the series, the following patch "ipv6: hash uncached
routes by device" does convert rt6_uncached_list_flush_dev() to the same
per-CPU bucket scheme and handles the two-key case with a dedicated
"mismatch" list that rt6_uncached_list_add() uses when rt6i_idev->dev differs
from dst_dev(), and the third patch adds selftest coverage for the VRF case.
So this is addressed within the series; would it be worth a sentence in this
changelog noting that the IPv6 counterpart follows?

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260914-hash-bucket-route-lists-v2-0-29f6297d8a5a%40cloudflare.com

Re: [PATCH net-next v2 2/3] ipv6: hash uncached routes by device

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found 1 potential
issue(s) to consider:

Critical: 0 · High: 0 (1) · Medium: 0 · Low: 1

- [Low] Changelog/code mismatch: the commit message states "Hash uncached
  routes by their inet6 device", but rt6_uncached_list_add()…

Pre-existing issues:
- [High] rt6_uncached_list_flush() (net/ipv6/route.c:177-207) unlinks a
  route from its uncached list as soon as EITHER of its two device…

--

ipv6: hash uncached routes by device

This replaces the single per-CPU uncached route list with a per-CPU hash
table plus a separate "mismatch" list, so that device teardown only has to
walk the bucket belonging to the device being removed. A new
CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS controls the bucket count.

Two questions below, one about the changelog wording and one about the
flush path.

    Hash uncached routes by their inet6
    device so ordinary device teardown only visits the matching bucket on each
    CPU.

[Severity: Low]
Is this description accurate?  In rt6_uncached_list_add() the bucket key is
the dst device, not the inet6 device:

	struct net_device *rt_dev = dst_dev(&rt->dst);
	...
		ul = &table->buckets[hash_ptr(rt_dev,
					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];

rt6i_idev is only used as a discriminator to divert a route onto the
mismatch list, and rt6_uncached_list_flush_dev() likewise computes
hash_ptr(dev) for the device being unregistered.

Since ip6_rt_get_dev_rcu() can make dst.dev and rt6i_idev->dev refer to
different devices, which of the two is the key matters when auditing which
routes a given flush pass can reach.  Could the changelog say "hash uncached
routes by their dst device" instead?

> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index 7535b09068a06..080dce3291682 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c

[ ... ]

> @@ -133,11 +134,27 @@ struct uncached_list {
>  	struct list_head	head;
>  };
>  
> -static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
> +#define RT6_UNCACHED_HASH_SIZE	BIT(CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)
> +
> +struct rt6_uncached_table {
> +	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
> +	/* Routes that must be discoverable through two different devices. */
> +	struct uncached_list mismatch;
> +};
> +
> +static DEFINE_PER_CPU_ALIGNED(struct rt6_uncached_table, rt6_uncached_table);
>  
>  void rt6_uncached_list_add(struct rt6_info *rt)
>  {
> -	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
> +	struct rt6_uncached_table *table = raw_cpu_ptr(&rt6_uncached_table);
> +	struct net_device *rt_dev = dst_dev(&rt->dst);
> +	struct uncached_list *ul;
> +
> +	if (rt->rt6i_idev && rt->rt6i_idev->dev != rt_dev)
> +		ul = &table->mismatch;
> +	else
> +		ul = &table->buckets[hash_ptr(rt_dev,
> +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
>  
>  	rt->dst.rt_uncached_list = ul;
>  
> @@ -157,40 +174,51 @@ void rt6_uncached_list_del(struct rt6_info *rt)
>  	}
>  }
>  
> +static void rt6_uncached_list_flush(struct uncached_list *ul,
> +				    struct net_device *dev)
> +{
> +	struct rt6_info *rt, *safe;
> +
> +	if (list_empty(&ul->head))
> +		return;
> +
> +	spin_lock_bh(&ul->lock);
> +	list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> +		struct inet6_dev *rt_idev = rt->rt6i_idev;
> +		struct net_device *rt_dev = dst_dev(&rt->dst);
> +		bool handled = false;
> +
> +		if (rt_idev && rt_idev->dev == dev) {
> +			rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> +			in6_dev_put(rt_idev);
> +			handled = true;
> +		}
> +
> +		if (rt_dev == dev) {
> +			rt->dst.dev = blackhole_netdev;
> +			netdev_ref_replace(rt_dev, blackhole_netdev,
> +					   &rt->dst.dev_tracker, GFP_ATOMIC);
> +			handled = true;
> +		}
> +		if (handled)
> +			list_del_init(&rt->dst.rt_uncached);

[Severity: High]
This isn't a bug introduced by this patch, the handled/list_del_init()
sequence is textually identical to the pre-patch loop in
rt6_uncached_list_flush_dev().  But does the new mismatch list turn it into
a net_device reference leak?

handled is set independently by the rt6i_idev branch and the dst.dev branch,
and the route is then unlinked even when only one of the two matched.

For a route on table->mismatch the two fields point at two different real
devices by construction:

	if (rt->rt6i_idev && rt->rt6i_idev->dev != rt_dev)
		ul = &table->mismatch;

Such routes are produced by ordinary local traffic through an enslaved
interface.  ip6_rt_cache_alloc() takes dst.dev from ip6_rt_get_dev_rcu():

	if (res->fib6_flags & (RTF_LOCAL | RTF_ANYCAST)) {
		if (netif_is_l3_slave(dev) && !rt6_need_strict(...))
			dev = l3mdev_master_dev_rcu(dev) ? :
			      dev_net(dev)->loopback_dev;

while ip6_rt_copy_init() sets the inet6 device from the nexthop:

	rt->rt6i_idev = dev ? in6_dev_get(dev) : NULL;

So deleting eth0 first retargets only rt6i_idev to blackhole_netdev, sets
handled and calls list_del_init(), leaving dst.dev still holding the VRF
master or loopback device together with its dst.dev_tracker reference.

After the unlink, rt6_uncached_list_flush_dev() can no longer find that
route:

	ul = &table->buckets[hash_ptr(dev,
				      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
	rt6_uncached_list_flush(ul, dev);
	rt6_uncached_list_flush(&table->mismatch, dev);

the route is on neither the keyed bucket nor mismatch, so a later teardown
of the VRF master or loopback never runs netdev_ref_replace() on it.  If the
dst is pinned past that point by sk_dst_cache or a queued skb, does
unregister_netdevice() then loop in netdev_wait_allrefs() printing
"unregister_netdevice: waiting for <dev> to become free", blocking the
netdev todo queue and netns teardown?

The reverse order looks symmetric: deleting the VRF master or loopback first
leaves the eth0 inet6_dev reference in place, which pins eth0 through
idev->dev_tracker.

This also matches the comment added just above:

	/* Routes that must be discoverable through two different devices. */
	struct uncached_list mismatch;

Would it be better to keep the route linked (or relink it into the surviving
device's bucket) until both device references captured at insertion time
have been retargeted, rather than unlinking on the first match?

The accompanying selftest only deletes eth0 and checks that the delete
completes promptly, so it would not observe the surviving reference on the
VRF master or loopback.

>  	}
> +	spin_unlock_bh(&ul->lock);
> +}
> +
>  static void rt6_uncached_list_flush_dev(struct net_device *dev)
>  {
>  	int cpu;
>  
>  	for_each_possible_cpu(cpu) {
> -		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
> -		struct rt6_info *rt, *safe;
> +		struct rt6_uncached_table *table;
> +		struct uncached_list *ul;
>  
> +		table = per_cpu_ptr(&rt6_uncached_table, cpu);
> +		ul = &table->buckets[hash_ptr(dev,
> +					      CONFIG_IPV6_UNCACHED_ROUTE_HASH_BITS)];
> +		rt6_uncached_list_flush(ul, dev);
> +		rt6_uncached_list_flush(&table->mismatch, dev);
>  	}
>  }

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260914-hash-bucket-route-lists-v2-0-29f6297d8a5a%40cloudflare.com

Re: [PATCH net-next v2 3/3] selftests: net: cover IPv6 uncached route device mismatch

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found 5 potential
issue(s) to consider:

Critical: 0 · High: 1 · Medium: 2 · Low: 2

- [High] test_ipv6_uncached_mismatch() (tools/testing/selftests/net/vrf-
  xfrm-tests.sh:388-417) asserts that `timeout 2 ip link del eth0`…
- [Medium] Both setup steps of the new test are unchecked.
- [Medium] `run_cmd_host1 timeout 2 ip link del eth0`
  (tools/testing/selftests/net/vrf-xfrm-tests.sh:415) is used as the…
- [Low] test_ipv6_uncached_mismatch() mutates and then destroys the
  shared fixture without any teardown: it replaces the VRF root qdisc…
- [Low] The retention of the uncached route depends solely on a 10 s
  netem timer armed at enqueue, and nothing re-verifies that the packet…

--

selftests: net: cover IPv6 uncached route device mismatch

This adds a new test case to vrf-xfrm-tests.sh that creates a local IPv6
route through a VRF so that dst.dev is the VRF while rt6i_idev stays on the
member interface, holds the resulting uncached route in a netem queue, and
then deletes the member interface. A few questions below about the new test
function and about the commit message.

> diff --git a/tools/testing/selftests/net/vrf-xfrm-tests.sh b/tools/testing/selftests/net/vrf-xfrm-tests.sh
> index b64dd891699d3..4f409d135a99a 100755
> --- a/tools/testing/selftests/net/vrf-xfrm-tests.sh
> +++ b/tools/testing/selftests/net/vrf-xfrm-tests.sh
> @@ -385,6 +385,37 @@ run_tests()
>  	cleanup_xfrm_dev
>  }
>  
> +test_ipv6_uncached_mismatch()
> +{
> +	local sender_pid
> +	local backlog
> +	local rc
> +
> +	# A local route through a VRF uses the VRF as dst.dev while retaining
> +	# the VRF member interface in rt6i_idev. Raw header sends create uncached
> +	# routes, and netem keeps them referenced while the interface is deleted.
> +	run_cmd_host1 tc qdisc replace dev ${VRF} root netem limit 1 delay 10s
> +	ip -6 -netns "$host1" route add local ${HOST1_6}/128 dev eth0

[Severity: Medium]
Should the exit status of these two setup steps be checked?

The tc qdisc replace status is discarded, and the route add is not run
through run_cmd_host1 at all, so it is invisible under -v and has no
log_test either.

If CONFIG_NET_SCH_NETEM is not built, the qdisc is never installed, but
msg_zerocopy still exits 0 because rawv6_send_hdrinc() in net/ipv6/raw.c
masks -ENOBUFS:

	err = ip6_push_pending_frames(sk);
	...
	if (err == -ENOBUFS && !inet6_test_bit(RECVERR6, sk))
		err = 0;

So the first log_test passes and the failure instead shows up later as
"Retain uncached IPv6 routes in VRF qdisc" FAIL, which reads as a kernel
route-retention regression rather than a missing scheduler. Would a check
plus a skip be clearer here?

The same applies to the route add: it is the precondition that creates the
dst.dev(VRF) versus rt6i_idev(eth0) mismatch the test is named after. If it
fails (EEXIST, table/rule differences, older iproute2), the test either
fails at the sender assertion or silently exercises an unrelated path. The
later "[ $rc -ne 0 ] && return" guard cannot help, since rc only carries
msg_zerocopy's status.

Related to this, the commit message says:

	verify route creation, qdisc retention, and prompt interface
	deletion.

Is "verify route creation" accurate?  No assertion covers the route add; the
first log_test only reports the sender program's exit status.

> +	ip netns exec "$host1" ./msg_zerocopy -6 \
> +		-S ${HOST1_6} -D ${HOST1_6} -s 1200 -t 0 raw_hdrincl \
> +		>/dev/null 2>&1 &
> +	sender_pid=$!
> +	wait "$sender_pid"
> +	rc=$?
> +	log_test $rc 0 "Create uncached IPv6 routes with mismatched devices"
> +	[ $rc -ne 0 ] && return
> +
> +	backlog=$(ip netns exec "$host1" tc -s qdisc show dev ${VRF})
> +	if ! echo "$backlog" | grep -Eq 'backlog .* [1-9][0-9]*p'; then
> +		log_test 1 0 "Retain uncached IPv6 routes in VRF qdisc"
> +		return
> +	fi
> +	log_test 0 0 "Retain uncached IPv6 routes in VRF qdisc"

[Severity: Low]
Is the retention window here deterministic?

The only thing holding the uncached route is the 10s netem timer armed at
enqueue, and the backlog is sampled once and then assumed to still hold at
the ip link del below.  Between enqueue and the delete the script runs
msg_zerocopy for its full runtime (cfg_runtime_ms is 200 + 0 * 1000 with
-t 0, see tools/testing/selftests/net/msg_zerocopy.c), one ip netns exec tc
-s qdisc show, and two more process spawns.

If the timer fires before the grep, the result is a spurious FAIL. If it
fires after the grep but before the delete, all three checks pass while
nothing is actually exercised. Would a much longer netem delay, or a
re-check of the backlog immediately before the delete, make this
deterministic?

> +
> +	run_cmd_host1 timeout 2 ip link del eth0
> +	log_test $? 0 "Flush uncached IPv6 routes with mismatched devices"

[Severity: High]
Can this assertion pass on the tree the patch applies to?

The uncached dst created via ip6_pol_route() -> ip6_rt_cache_alloc() ->
rt6_uncached_list_add() holds a reference on the local route's fib6_info
through ip6_rt_copy_init() -> rt6_set_from(). That fib6_info's nexthop holds
a tracked netdev reference on eth0:

net/ipv6/route.c:fib6_nh_init() {
	...
	dev = netdev_get_by_index(net, cfg->fc_ifindex,
				  dev_tracker, gfp_flags);
	...
}

and that reference is only dropped by fib6_nh_release(), which runs from
fib6_info_destroy_rcu(), i.e. after the last fib6_info reference goes away.

The teardown path does not break that chain:

net/ipv6/route.c:rt6_disable_ip() {
	...
	rt6_sync_down_dev(dev, event);
	rt6_uncached_list_flush_dev(dev);
	neigh_ifdown(nd_table(net), dev);
	...
}

and rt6_uncached_list_flush_dev() only swaps rt6i_idev/dst.dev to
blackhole_netdev:

	if (rt_idev && rt_idev->dev == dev) {
		rt->rt6i_idev = in6_dev_get(blackhole_netdev);
		in6_dev_put(rt_idev);
		handled = true;
	}

It never touches rt->from. The xchg(&rt->from, NULL) in ip6_dst_ifdown() is
only reached through dst->ops->ifdown from dst_dev_put(), which is not
called for this dst because ip6_rt_get_dev_rcu() gives the VRF master as
dst.dev for an RTF_LOCAL route on an enslaved device - the very mismatch
described in the commit message.

So eth0's refcount stays elevated until netem dequeues the skb roughly 10s
later, ip link del blocks in netdev_wait_allrefs_any() for that long,
timeout 2 returns non-zero, and this log_test reports FAIL. The commit
message does not name a kernel fix this test accompanies and does not
mention an expected failure. Is a corresponding kernel change meant to be
part of this series?

[Severity: Medium]
Separately, can timeout bound this operation at all?

RTM_DELLINK finishes unregistration synchronously in the caller's syscall
context via rtnl_unlock() -> netdev_run_todo() -> netdev_wait_allrefs_any(),
whose loop is:

net/core/dev.c:netdev_wait_allrefs_any() {
	...
		} else {
			msleep(wait);
			wait = min(wait << 1, WAIT_REFS_MAX_MSECS);
		}
	...
}

There is no signal check there, so the SIGTERM that timeout 2 queues cannot
be delivered until the syscall returns, and killing ip would not roll back
the in-kernel unregistration either. During that window the half-removed
device also emits the periodic "unregister_netdevice: waiting for eth0 to
become free" messages.

That makes the verdict of this log_test depend on signal delivery timing
rather than on the outcome of the delete, and if a reference were genuinely
never released the script would block indefinitely and never reach the
summary printf and exit $ret.

The test also never removes the retaining netem qdisc, which is the one
action that would release the pinning skb immediately. Would deleting the
qdisc before the link delete, and checking device refcounts instead of
wrapping ip in timeout, be a more reliable detector?

> +}
> +

[Severity: Low]
Does test_ipv6_uncached_mismatch() need to restore what it changes?

It replaces the VRF root qdisc with netem limit 1 delay 10s, adds
local ${HOST1_6}/128 dev eth0, and then deletes eth0, which is the veth
carrying the whole host1/host2 topology built once by setup().

Neither early return ("[ $rc -ne 0 ] && return" and the backlog-grep
return) removes the qdisc or the added route, and the success path also
leaves the 10s qdisc on the VRF.

Because the shared fixture is consumed, the file also gains an implicit
ordering constraint: the test only works while it is the last thing invoked.
Adding anything after it, or repeating run_tests, would fail.

> @@ -425,6 +456,10 @@ echo
>  echo "netem qdisc on VRF device"
>  run_tests
>  
> +echo
> +echo "Uncached IPv6 route with mismatched devices"
> +test_ipv6_uncached_mismatch
> +

Continuing the point above: the earlier phase leaves netem delay 100ms on the
same VRF device, so if the replace in the new test fails the leftover qdisc
can still produce a non-zero backlog and satisfy the grep without holding the
route past the two-second timeout.

The script also has no final cleanup and no EXIT trap. The existing
"cleanup 2>/dev/null" runs before setup() while $host1/$host2 are still
unset, so cleanup_ns gets no arguments. That part is pre-existing and not
introduced by this patch, but with eth0 now deleted and the qdisc and route
left in place the namespaces are leaked in a modified state.

>  printf "\nTests passed: %3d\n" ${nsuccess}
>  printf "Tests failed: %3d\n"   ${nfail}
>

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260914-hash-bucket-route-lists-v2-0-29f6297d8a5a%40cloudflare.com