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

[PATCH net-next v3 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
using the network device as its key. Each table uses 64 buckets.
IPv6 routes need additional handling because dst.dev and
rt6i_idev->dev can refer to different devices. Routes are keyed by
rt6i_idev->dev when available. Device teardown scans one bucket for
ordinary devices and all buckets for loopback and L3 master devices.

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 64 buckets.

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 v3:
- Remove IPv4 and IPv6 Kconfig options; use fixed 64-bucket tables.
- Use rcu_assign_pointer in rt6_uncached_list_flush
- Key IPv6 routes by rt6i_idev and scan all buckets for loopback/VRF
- RCT all the things
- Link to v2: https://patch.msgid.link/20260914-hash-bucket-route-lists-v2-0-29f6297d8a5a@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/route.c                              |  36 +++++++--
 net/ipv6/route.c                              | 101 ++++++++++++++++++--------
 tools/testing/selftests/net/vrf-xfrm-tests.sh |  35 +++++++++
 3 files changed, 133 insertions(+), 39 deletions(-)
---
base-commit: 26ee8cd69d46a14b37ba5e512084fe80d730127a
change-id: 20260820-hash-bucket-route-lists-b8cc27ccd53c

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

[PATCH net-next v3 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 64 buckets and costs approximately 1.5 KiB per possible CPU
on x86-64.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
 net/ipv4/route.c | 36 +++++++++++++++++++++++++++++-------
 1 file changed, 29 insertions(+), 7 deletions(-)

diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index d7da2f1acbb5..e5539eda4307 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,22 @@ struct uncached_list {
 	struct list_head	head;
 };
 
-static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt_uncached_list);
+#define RT_UNCACHED_HASH_BITS	6
+#define RT_UNCACHED_HASH_SIZE	BIT(RT_UNCACHED_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),
+				      RT_UNCACHED_HASH_BITS)];
 
 	rt->dst.rt_uncached_list = ul;
 
@@ -1588,14 +1600,18 @@ 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, RT_UNCACHED_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 v3 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. Key routes by rt6i_idev->dev when
available and fall back to dst_dev(). Ordinary devices then require one
bucket scan. Because loopback and L3 masters can instead be referenced by
dst_dev(), scan all buckets when one of those devices is removed.

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

The table has 64 buckets and costs approximately 1.5 KiB per possible CPU
on x86-64.

Signed-off-by: Chris J Arges <carges@cloudflare.com>
---
 net/ipv6/route.c | 101 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 69 insertions(+), 32 deletions(-)

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index 7535b09068a0..cda81e91be65 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,23 @@ struct uncached_list {
 	struct list_head	head;
 };
 
-static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
+#define RT6_UNCACHED_HASH_BITS	6
+#define RT6_UNCACHED_HASH_SIZE	BIT(RT6_UNCACHED_HASH_BITS)
+
+struct rt6_uncached_table {
+	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
+};
+
+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 uncached_list *ul;
+	struct net_device *dev;
+
+	dev = rt->rt6i_idev ? rt->rt6i_idev->dev : dst_dev(&rt->dst);
+	ul = &table->buckets[hash_ptr(dev, RT6_UNCACHED_HASH_BITS)];
 
 	rt->dst.rt_uncached_list = ul;
 
@@ -157,40 +170,58 @@ 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 net_device *rt_dev = dst_dev(&rt->dst);
+		struct inet6_dev *rt_idev = rt->rt6i_idev;
+		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) {
+			rcu_assign_pointer(rt->dst.dev_rcu, 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)
 {
+	bool scan_all = dev->flags & IFF_LOOPBACK || netif_is_l3_master(dev);
 	int cpu;
 
 	for_each_possible_cpu(cpu) {
-		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
-		struct rt6_info *rt, *safe;
-
-		if (list_empty(&ul->head))
+		struct rt6_uncached_table *table;
+		struct uncached_list *ul;
+		int bucket;
+
+		table = per_cpu_ptr(&rt6_uncached_table, cpu);
+		if (!scan_all) {
+			ul = &table->buckets[hash_ptr(dev,
+						      RT6_UNCACHED_HASH_BITS)];
+			rt6_uncached_list_flush(ul, dev);
 			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);
+
+		for (bucket = 0; bucket < RT6_UNCACHED_HASH_SIZE; bucket++)
+			rt6_uncached_list_flush(&table->buckets[bucket], dev);
 	}
 }
 
@@ -6987,10 +7018,16 @@ 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);
+		}
 	}
 
 out:

-- 
2.43.0

[PATCH net-next v3 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 v3 0/3] net: hash uncached route lists by device

[Kuniyuki Iwashima]

From: Chris J Arges <carges@cloudflare.com>
Date: Thu, 17 Sep 2026 14:38:21 -0500
> 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
> using the network device as its key. Each table uses 64 buckets.

This sounds a bit overkill.  Also, this series still leaves
O(N * C) loops.

Given unregistering a single device is less common than
destroying netns, I think the right approach should be to
make the route flush once in cleanup_net() + outside RTNL.

Could you try this change ? (only compile-tested)

---8<---
diff --git a/include/net/net_namespace.h b/include/net/net_namespace.h
index 46b4c67e2966..d8ce7dc0fbdc 100644
--- a/include/net/net_namespace.h
+++ b/include/net/net_namespace.h
@@ -489,6 +489,7 @@ struct pernet_operations {
 	 */
 	int (*init)(struct net *net);
 	void (*pre_exit)(struct net *net);
+	void (*pre_exit_batch)(struct list_head *net_exit_list);
 	void (*exit)(struct net *net);
 	void (*exit_batch)(struct list_head *net_exit_list);
 	/* Following method is called with RTNL held. */
diff --git a/net/core/net_namespace.c b/net/core/net_namespace.c
index da5f881fbd3b..7fc9bf45f3b6 100644
--- a/net/core/net_namespace.c
+++ b/net/core/net_namespace.c
@@ -160,6 +160,9 @@ static void ops_pre_exit_list(const struct pernet_operations *ops,
 		list_for_each_entry(net, net_exit_list, exit_list)
 			ops->pre_exit(net);
 	}
+
+	if (ops->pre_exit_batch)
+		ops->pre_exit_batch(net_exit_list);
 }
 
 static void ops_exit_rtnl_list(const struct list_head *ops_list,
diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
index 8a3dc04e8cac..b8d76b6279e1 100644
--- a/net/ipv4/fib_frontend.c
+++ b/net/ipv4/fib_frontend.c
@@ -1685,6 +1685,11 @@ static void __net_exit fib_net_pre_exit(struct net *net)
 	nl_fib_lookup_exit(net);
 }
 
+static void __net_exit fib_net_pre_exit_batch(struct list_head *net_exit_list)
+{
+	rt_flush_dev(NULL);
+}
+
 static void __net_exit fib_net_exit_rtnl(struct net *net,
 					 struct list_head *dev_kill_list)
 {
@@ -1704,6 +1709,7 @@ static void __net_exit fib_net_exit(struct net *net)
 static struct pernet_operations fib_net_ops = {
 	.init = fib_net_init,
 	.pre_exit = fib_net_pre_exit,
+	.pre_exit_batch = fib_net_pre_exit_batch,
 	.exit_rtnl = fib_net_exit_rtnl,
 	.exit = fib_net_exit,
 };
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index d7da2f1acbb5..d35b66b33bbc 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -1554,14 +1554,28 @@ struct uncached_list {
 
 static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt_uncached_list);
 
+static void rt_replace_uncached_list(struct rtable *rt)
+{
+	struct net_device *dev = dst_dev(&rt->dst);
+
+	rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
+	netdev_ref_replace(dev, blackhole_netdev,
+			   &rt->dst.dev_tracker, GFP_ATOMIC);
+}
+
 void rt_add_uncached_list(struct rtable *rt)
 {
 	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
 
-	rt->dst.rt_uncached_list = ul;
-
 	spin_lock_bh(&ul->lock);
-	list_add_tail(&rt->dst.rt_uncached, &ul->head);
+
+	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
+		rt_replace_uncached_list(rt);
+	} else {
+		rt->dst.rt_uncached_list = ul;
+		list_add_tail(&rt->dst.rt_uncached, &ul->head);
+	}
+
 	spin_unlock_bh(&ul->lock);
 }
 
@@ -1587,6 +1601,9 @@ void rt_flush_dev(struct net_device *dev)
 	struct rtable *rt, *safe;
 	int cpu;
 
+	if (dev && !check_net(dev_net(dev)))
+		return;
+
 	for_each_possible_cpu(cpu) {
 		struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
 
@@ -1595,11 +1612,11 @@ void rt_flush_dev(struct net_device *dev)
 
 		spin_lock_bh(&ul->lock);
 		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
-			if (rt->dst.dev != dev)
+			if (rt->dst.dev != dev &&
+			    (dev || check_net(dev_net(rt->dst.dev))))
 				continue;
-			rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
-			netdev_ref_replace(dev, blackhole_netdev,
-					   &rt->dst.dev_tracker, GFP_ATOMIC);
+
+			rt_replace_uncached_list(rt);
 			list_del_init(&rt->dst.rt_uncached);
 		}
 		spin_unlock_bh(&ul->lock);
diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index 7535b09068a0..28233197e1e1 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -135,14 +135,35 @@ struct uncached_list {
 
 static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
 
+static void rt6_uncached_list_replace(struct rt6_info *rt)
+{
+	struct net_device *dev = dst_dev(&rt->dst);
+	struct inet6_dev *rt_idev = rt->rt6i_idev;
+
+	if (rt_idev) {
+		rt->rt6i_idev = in6_dev_get(blackhole_netdev);
+		in6_dev_put(rt_idev);
+	}
+
+	rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
+	netdev_ref_replace(dev, blackhole_netdev,
+			   &rt->dst.dev_tracker,
+			   GFP_ATOMIC);
+}
+
 void rt6_uncached_list_add(struct rt6_info *rt)
 {
 	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
 
-	rt->dst.rt_uncached_list = ul;
-
 	spin_lock_bh(&ul->lock);
-	list_add_tail(&rt->dst.rt_uncached, &ul->head);
+
+	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
+		rt6_uncached_list_replace(rt);
+	} else {
+		rt->dst.rt_uncached_list = ul;
+		list_add_tail(&rt->dst.rt_uncached, &ul->head);
+	}
+
 	spin_unlock_bh(&ul->lock);
 }
 
@@ -161,6 +182,9 @@ static void rt6_uncached_list_flush_dev(struct net_device *dev)
 {
 	int cpu;
 
+	if (dev && !check_net(dev_net(dev)))
+		return;
+
 	for_each_possible_cpu(cpu) {
 		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
 		struct rt6_info *rt, *safe;
@@ -172,23 +196,17 @@ static void rt6_uncached_list_flush_dev(struct net_device *dev)
 		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 (dev) {
+				if (rt_dev != dev &&
+				    (!rt_idev || rt_idev->dev != dev))
+					continue;
+			} else if (check_net(dev_net(rt_dev))) {
+				continue;
 			}
 
-			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);
+			rt6_uncached_list_replace(rt);
+			list_del_init(&rt->dst.rt_uncached);
 		}
 		spin_unlock_bh(&ul->lock);
 	}
@@ -6795,6 +6813,11 @@ static int __net_init ip6_route_net_init(struct net *net)
 	goto out;
 }
 
+static void __net_exit ip6_route_net_pre_exit_batch(struct list_head *net_exit_list)
+{
+	rt6_uncached_list_flush_dev(NULL);
+}
+
 static void __net_exit ip6_route_net_exit(struct net *net)
 {
 	kfree(net->ipv6.fib6_null_entry);
@@ -6833,6 +6856,7 @@ static void __net_exit ip6_route_net_exit_late(struct net *net)
 
 static struct pernet_operations ip6_route_net_ops = {
 	.init = ip6_route_net_init,
+	.pre_exit_batch = ip6_route_net_pre_exit_batch,
 	.exit = ip6_route_net_exit,
 };
 
---8<---

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

[Chris Arges]

On 2026-09-17 22:10:22, Kuniyuki Iwashima wrote:
> From: Chris J Arges <carges@cloudflare.com>
> Date: Thu, 17 Sep 2026 14:38:21 -0500
> > 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
> > using the network device as its key. Each table uses 64 buckets.
> 
> This sounds a bit overkill.  Also, this series still leaves
> O(N * C) loops.
> 
> Given unregistering a single device is less common than
> destroying netns, I think the right approach should be to
> make the route flush once in cleanup_net() + outside RTNL.
> 
> Could you try this change ? (only compile-tested)
> 
Excellent, I'll test this and report back.
Thanks,
--chris


> ---8<---
> diff --git a/include/net/net_namespace.h b/include/net/net_namespace.h
> index 46b4c67e2966..d8ce7dc0fbdc 100644
> --- a/include/net/net_namespace.h
> +++ b/include/net/net_namespace.h
> @@ -489,6 +489,7 @@ struct pernet_operations {
>  	 */
>  	int (*init)(struct net *net);
>  	void (*pre_exit)(struct net *net);
> +	void (*pre_exit_batch)(struct list_head *net_exit_list);
>  	void (*exit)(struct net *net);
>  	void (*exit_batch)(struct list_head *net_exit_list);
>  	/* Following method is called with RTNL held. */
> diff --git a/net/core/net_namespace.c b/net/core/net_namespace.c
> index da5f881fbd3b..7fc9bf45f3b6 100644
> --- a/net/core/net_namespace.c
> +++ b/net/core/net_namespace.c
> @@ -160,6 +160,9 @@ static void ops_pre_exit_list(const struct pernet_operations *ops,
>  		list_for_each_entry(net, net_exit_list, exit_list)
>  			ops->pre_exit(net);
>  	}
> +
> +	if (ops->pre_exit_batch)
> +		ops->pre_exit_batch(net_exit_list);
>  }
>  
>  static void ops_exit_rtnl_list(const struct list_head *ops_list,
> diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
> index 8a3dc04e8cac..b8d76b6279e1 100644
> --- a/net/ipv4/fib_frontend.c
> +++ b/net/ipv4/fib_frontend.c
> @@ -1685,6 +1685,11 @@ static void __net_exit fib_net_pre_exit(struct net *net)
>  	nl_fib_lookup_exit(net);
>  }
>  
> +static void __net_exit fib_net_pre_exit_batch(struct list_head *net_exit_list)
> +{
> +	rt_flush_dev(NULL);
> +}
> +
>  static void __net_exit fib_net_exit_rtnl(struct net *net,
>  					 struct list_head *dev_kill_list)
>  {
> @@ -1704,6 +1709,7 @@ static void __net_exit fib_net_exit(struct net *net)
>  static struct pernet_operations fib_net_ops = {
>  	.init = fib_net_init,
>  	.pre_exit = fib_net_pre_exit,
> +	.pre_exit_batch = fib_net_pre_exit_batch,
>  	.exit_rtnl = fib_net_exit_rtnl,
>  	.exit = fib_net_exit,
>  };
> diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> index d7da2f1acbb5..d35b66b33bbc 100644
> --- a/net/ipv4/route.c
> +++ b/net/ipv4/route.c
> @@ -1554,14 +1554,28 @@ struct uncached_list {
>  
>  static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt_uncached_list);
>  
> +static void rt_replace_uncached_list(struct rtable *rt)
> +{
> +	struct net_device *dev = dst_dev(&rt->dst);
> +
> +	rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
> +	netdev_ref_replace(dev, blackhole_netdev,
> +			   &rt->dst.dev_tracker, GFP_ATOMIC);
> +}
> +
>  void rt_add_uncached_list(struct rtable *rt)
>  {
>  	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
>  
> -	rt->dst.rt_uncached_list = ul;
> -
>  	spin_lock_bh(&ul->lock);
> -	list_add_tail(&rt->dst.rt_uncached, &ul->head);
> +
> +	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
> +		rt_replace_uncached_list(rt);
> +	} else {
> +		rt->dst.rt_uncached_list = ul;
> +		list_add_tail(&rt->dst.rt_uncached, &ul->head);
> +	}
> +
>  	spin_unlock_bh(&ul->lock);
>  }
>  
> @@ -1587,6 +1601,9 @@ void rt_flush_dev(struct net_device *dev)
>  	struct rtable *rt, *safe;
>  	int cpu;
>  
> +	if (dev && !check_net(dev_net(dev)))
> +		return;
> +
>  	for_each_possible_cpu(cpu) {
>  		struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
>  
> @@ -1595,11 +1612,11 @@ void rt_flush_dev(struct net_device *dev)
>  
>  		spin_lock_bh(&ul->lock);
>  		list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> -			if (rt->dst.dev != dev)
> +			if (rt->dst.dev != dev &&
> +			    (dev || check_net(dev_net(rt->dst.dev))))
>  				continue;
> -			rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
> -			netdev_ref_replace(dev, blackhole_netdev,
> -					   &rt->dst.dev_tracker, GFP_ATOMIC);
> +
> +			rt_replace_uncached_list(rt);
>  			list_del_init(&rt->dst.rt_uncached);
>  		}
>  		spin_unlock_bh(&ul->lock);
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index 7535b09068a0..28233197e1e1 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -135,14 +135,35 @@ struct uncached_list {
>  
>  static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
>  
> +static void rt6_uncached_list_replace(struct rt6_info *rt)
> +{
> +	struct net_device *dev = dst_dev(&rt->dst);
> +	struct inet6_dev *rt_idev = rt->rt6i_idev;
> +
> +	if (rt_idev) {
> +		rt->rt6i_idev = in6_dev_get(blackhole_netdev);
> +		in6_dev_put(rt_idev);
> +	}
> +
> +	rcu_assign_pointer(rt->dst.dev_rcu, blackhole_netdev);
> +	netdev_ref_replace(dev, blackhole_netdev,
> +			   &rt->dst.dev_tracker,
> +			   GFP_ATOMIC);
> +}
> +
>  void rt6_uncached_list_add(struct rt6_info *rt)
>  {
>  	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
>  
> -	rt->dst.rt_uncached_list = ul;
> -
>  	spin_lock_bh(&ul->lock);
> -	list_add_tail(&rt->dst.rt_uncached, &ul->head);
> +
> +	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
> +		rt6_uncached_list_replace(rt);
> +	} else {
> +		rt->dst.rt_uncached_list = ul;
> +		list_add_tail(&rt->dst.rt_uncached, &ul->head);
> +	}
> +
>  	spin_unlock_bh(&ul->lock);
>  }
>  
> @@ -161,6 +182,9 @@ static void rt6_uncached_list_flush_dev(struct net_device *dev)
>  {
>  	int cpu;
>  
> +	if (dev && !check_net(dev_net(dev)))
> +		return;
> +
>  	for_each_possible_cpu(cpu) {
>  		struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
>  		struct rt6_info *rt, *safe;
> @@ -172,23 +196,17 @@ static void rt6_uncached_list_flush_dev(struct net_device *dev)
>  		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 (dev) {
> +				if (rt_dev != dev &&
> +				    (!rt_idev || rt_idev->dev != dev))
> +					continue;
> +			} else if (check_net(dev_net(rt_dev))) {
> +				continue;
>  			}
>  
> -			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);
> +			rt6_uncached_list_replace(rt);
> +			list_del_init(&rt->dst.rt_uncached);
>  		}
>  		spin_unlock_bh(&ul->lock);
>  	}
> @@ -6795,6 +6813,11 @@ static int __net_init ip6_route_net_init(struct net *net)
>  	goto out;
>  }
>  
> +static void __net_exit ip6_route_net_pre_exit_batch(struct list_head *net_exit_list)
> +{
> +	rt6_uncached_list_flush_dev(NULL);
> +}
> +
>  static void __net_exit ip6_route_net_exit(struct net *net)
>  {
>  	kfree(net->ipv6.fib6_null_entry);
> @@ -6833,6 +6856,7 @@ static void __net_exit ip6_route_net_exit_late(struct net *net)
>  
>  static struct pernet_operations ip6_route_net_ops = {
>  	.init = ip6_route_net_init,
> +	.pre_exit_batch = ip6_route_net_pre_exit_batch,
>  	.exit = ip6_route_net_exit,
>  };
>  
> ---8<---

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

[Kuniyuki Iwashima]

From: Chris Arges <carges@cloudflare.com>
Date: Thu, 17 Sep 2026 19:38:40 -0500
> On 2026-09-17 22:10:22, Kuniyuki Iwashima wrote:
> > From: Chris J Arges <carges@cloudflare.com>
> > Date: Thu, 17 Sep 2026 14:38:21 -0500
> > > 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
> > > using the network device as its key. Each table uses 64 buckets.
> > 
> > This sounds a bit overkill.  Also, this series still leaves
> > O(N * C) loops.
> > 
> > Given unregistering a single device is less common than
> > destroying netns, I think the right approach should be to
> > make the route flush once in cleanup_net() + outside RTNL.
> > 
> > Could you try this change ? (only compile-tested)
> > 
> Excellent, I'll test this and report back.

I found a pre-existing issue, which affects the previous
diff, so on top of it, please apply this patch

  https://lore.kernel.org/netdev/20260918041439.2575935-1-kuniyu@google.com/T/#u

and this diff :

---8<---
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index d35b66b33bbc..c12e20e07749 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -1567,12 +1567,13 @@ void rt_add_uncached_list(struct rtable *rt)
 {
 	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
 
+	rt->dst.rt_uncached_list = ul;
+
 	spin_lock_bh(&ul->lock);
 
 	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
 		rt_replace_uncached_list(rt);
 	} else {
-		rt->dst.rt_uncached_list = ul;
 		list_add_tail(&rt->dst.rt_uncached, &ul->head);
 	}
 
diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index 6cffe8440b44..f22793abbbb8 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -155,12 +155,13 @@ void rt6_uncached_list_add(struct rt6_info *rt)
 {
 	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
 
+	rt->dst.rt_uncached_list = ul;
+
 	spin_lock_bh(&ul->lock);
 
 	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
 		rt6_uncached_list_replace(rt);
 	} else {
-		rt->dst.rt_uncached_list = ul;
 		list_add_tail(&rt->dst.rt_uncached, &ul->head);
 	}
 
---8<---

Thanks !

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

[Chris Arges]

On 2026-09-18 04:19:34, Kuniyuki Iwashima wrote:
> From: Chris Arges <carges@cloudflare.com>
> Date: Thu, 17 Sep 2026 19:38:40 -0500
> > On 2026-09-17 22:10:22, Kuniyuki Iwashima wrote:
> > > From: Chris J Arges <carges@cloudflare.com>
> > > Date: Thu, 17 Sep 2026 14:38:21 -0500
> > > > 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
> > > > using the network device as its key. Each table uses 64 buckets.
> > > 
> > > This sounds a bit overkill.  Also, this series still leaves
> > > O(N * C) loops.
> > > 
> > > Given unregistering a single device is less common than
> > > destroying netns, I think the right approach should be to
> > > make the route flush once in cleanup_net() + outside RTNL.
> > > 
> > > Could you try this change ? (only compile-tested)
> > > 
> > Excellent, I'll test this and report back.
> 
> I found a pre-existing issue, which affects the previous
> diff, so on top of it, please apply this patch
> 
>   https://lore.kernel.org/netdev/20260918041439.2575935-1-kuniyu@google.com/T/#u
> 
> and this diff :
> 
> ---8<---
> diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> index d35b66b33bbc..c12e20e07749 100644
> --- a/net/ipv4/route.c
> +++ b/net/ipv4/route.c
> @@ -1567,12 +1567,13 @@ void rt_add_uncached_list(struct rtable *rt)
>  {
>  	struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
>  
> +	rt->dst.rt_uncached_list = ul;
> +
>  	spin_lock_bh(&ul->lock);
>  
>  	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
>  		rt_replace_uncached_list(rt);
>  	} else {
> -		rt->dst.rt_uncached_list = ul;
>  		list_add_tail(&rt->dst.rt_uncached, &ul->head);
>  	}
>  
> diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> index 6cffe8440b44..f22793abbbb8 100644
> --- a/net/ipv6/route.c
> +++ b/net/ipv6/route.c
> @@ -155,12 +155,13 @@ void rt6_uncached_list_add(struct rt6_info *rt)
>  {
>  	struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
>  
> +	rt->dst.rt_uncached_list = ul;
> +
>  	spin_lock_bh(&ul->lock);
>  
>  	if (!check_net(dst_dev_net_rcu(&rt->dst))) {
>  		rt6_uncached_list_replace(rt);
>  	} else {
> -		rt->dst.rt_uncached_list = ul;
>  		list_add_tail(&rt->dst.rt_uncached, &ul->head);
>  	}
>  
> ---8<---

Kuniyuki,

I was able to test this diff, the previous diff you sent plus the fixup
mentioned above. I was able to confirm even greater reduction in contention
as measured by how much latency an unrelated process takes when waiting for
cleanup_net to complete. This makes sense since we don't even need to hold the
lock when processing those routing entries with your patch.

Some rough average latency numbers with 36 devices, 160k routes, 8 vCPUs:
- main: 137ms
- my hashing proposal: 13ms
- your patchset: 1.8ms

I'd be happy to retest any proposed patches.

Thanks,
--chris

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

[Kuniyuki Iwashima]

On Fri, Sep 18, 2026 at 11:24 AM Chris Arges <carges@cloudflare.com> wrote:
>
> On 2026-09-18 04:19:34, Kuniyuki Iwashima wrote:
> > From: Chris Arges <carges@cloudflare.com>
> > Date: Thu, 17 Sep 2026 19:38:40 -0500
> > > On 2026-09-17 22:10:22, Kuniyuki Iwashima wrote:
> > > > From: Chris J Arges <carges@cloudflare.com>
> > > > Date: Thu, 17 Sep 2026 14:38:21 -0500
> > > > > 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
> > > > > using the network device as its key. Each table uses 64 buckets.
> > > >
> > > > This sounds a bit overkill.  Also, this series still leaves
> > > > O(N * C) loops.
> > > >
> > > > Given unregistering a single device is less common than
> > > > destroying netns, I think the right approach should be to
> > > > make the route flush once in cleanup_net() + outside RTNL.
> > > >
> > > > Could you try this change ? (only compile-tested)
> > > >
> > > Excellent, I'll test this and report back.
> >
> > I found a pre-existing issue, which affects the previous
> > diff, so on top of it, please apply this patch
> >
> >   https://lore.kernel.org/netdev/20260918041439.2575935-1-kuniyu@google.com/T/#u
> >
> > and this diff :
> >
> > ---8<---
> > diff --git a/net/ipv4/route.c b/net/ipv4/route.c
> > index d35b66b33bbc..c12e20e07749 100644
> > --- a/net/ipv4/route.c
> > +++ b/net/ipv4/route.c
> > @@ -1567,12 +1567,13 @@ void rt_add_uncached_list(struct rtable *rt)
> >  {
> >       struct uncached_list *ul = raw_cpu_ptr(&rt_uncached_list);
> >
> > +     rt->dst.rt_uncached_list = ul;
> > +
> >       spin_lock_bh(&ul->lock);
> >
> >       if (!check_net(dst_dev_net_rcu(&rt->dst))) {
> >               rt_replace_uncached_list(rt);
> >       } else {
> > -             rt->dst.rt_uncached_list = ul;
> >               list_add_tail(&rt->dst.rt_uncached, &ul->head);
> >       }
> >
> > diff --git a/net/ipv6/route.c b/net/ipv6/route.c
> > index 6cffe8440b44..f22793abbbb8 100644
> > --- a/net/ipv6/route.c
> > +++ b/net/ipv6/route.c
> > @@ -155,12 +155,13 @@ void rt6_uncached_list_add(struct rt6_info *rt)
> >  {
> >       struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);
> >
> > +     rt->dst.rt_uncached_list = ul;
> > +
> >       spin_lock_bh(&ul->lock);
> >
> >       if (!check_net(dst_dev_net_rcu(&rt->dst))) {
> >               rt6_uncached_list_replace(rt);
> >       } else {
> > -             rt->dst.rt_uncached_list = ul;
> >               list_add_tail(&rt->dst.rt_uncached, &ul->head);
> >       }
> >
> > ---8<---
>
> Kuniyuki,
>
> I was able to test this diff, the previous diff you sent plus the fixup
> mentioned above. I was able to confirm even greater reduction in contention
> as measured by how much latency an unrelated process takes when waiting for
> cleanup_net to complete. This makes sense since we don't even need to hold the
> lock when processing those routing entries with your patch.
>
> Some rough average latency numbers with 36 devices, 160k routes, 8 vCPUs:
> - main: 137ms
> - my hashing proposal: 13ms
> - your patchset: 1.8ms
>
> I'd be happy to retest any proposed patches.

Great, thank you for testing !

I will post patches officially once my fix lands in net-next
(so should be after next Thursday)

Thanks !

Re: [PATCH net-next v3 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: 1 · Medium: 0 · Low: 0 (1)

If you believe none of the issues are legitimate, please reply to each
issue of Medium severity or higher and explain why the AI is wrong.
If any of them are legitimate and you plan to respin, please let patchwork
know by including "pw-bot: cr" as a separate line at the end of your reply
(one such reply per series is enough).

- [High] Partially-repaired uncached routes are unlinked from the list,
  permanently pinning the second device.

Pre-existing issues:
- [Low] `rt6_uncached_list_flush()` tests `list_empty(&ul->head)` before
  acquiring `ul->lock` (net/ipv6/route.c:178-181) and returns on the…

--

ipv6: hash uncached routes by device

The patch replaces the single per-CPU uncached route list with a 64 bucket
per-CPU hash table keyed on rt6i_idev->dev (falling back to dst_dev()), so
ordinary device teardown only visits one bucket per CPU.  Loopback and L3
master devices scan all buckets because they can be referenced through
dst_dev() instead.  The flush loop itself is moved into a new helper,
rt6_uncached_list_flush().

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

[ ... ]

> @@ -133,11 +134,23 @@ struct uncached_list {
>  	struct list_head	head;
>  };
>  
> -static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);
> +#define RT6_UNCACHED_HASH_BITS	6
> +#define RT6_UNCACHED_HASH_SIZE	BIT(RT6_UNCACHED_HASH_BITS)
> +
> +struct rt6_uncached_table {
> +	struct uncached_list buckets[RT6_UNCACHED_HASH_SIZE];
> +};
> +
> +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 uncached_list *ul;
> +	struct net_device *dev;
> +
> +	dev = rt->rt6i_idev ? rt->rt6i_idev->dev : dst_dev(&rt->dst);
> +	ul = &table->buckets[hash_ptr(dev, RT6_UNCACHED_HASH_BITS)];
>  
>  	rt->dst.rt_uncached_list = ul;
>  
> @@ -157,40 +170,58 @@ 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);

[Severity: Low]
This isn't a bug introduced by this patch, the same unlocked list_empty()
test existed in rt6_uncached_list_flush_dev() before (with continue instead
of return), and net/ipv4/route.c uses the same idiom.

Still, the test reads ul->head outside ul->lock while
rt6_uncached_list_add() mutates the same head under the lock from softirq
context:

net/ipv6/route.c:rt6_uncached_list_add() {
	spin_lock_bh(&ul->lock);
	list_add_tail(&rt->dst.rt_uncached, &ul->head);
	spin_unlock_bh(&ul->lock);
}

Can the flush skip a bucket that an adder has just populated, so a route
still referencing the device being torn down is left on the list for that
pass?

As far as I can tell such a route is picked up again, because
netdev_wait_allrefs_any() rebroadcasts NETDEV_UNREGISTER roughly once per
second while references remain, and addrconf_ifdown() calls
rt6_disable_ip(dev, event) before its "idev = __in6_dev_get(dev); if (!idev)
return -ENODEV;" early return, so the flush re-runs.  Would it still be
worth moving the list_empty() check under the lock, since the fast path is
already per-bucket now?

> +	list_for_each_entry_safe(rt, safe, &ul->head, dst.rt_uncached) {
> +		struct net_device *rt_dev = dst_dev(&rt->dst);
> +		struct inet6_dev *rt_idev = rt->rt6i_idev;
> +		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) {
> +			rcu_assign_pointer(rt->dst.dev_rcu, 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);
> +}

[Severity: High]
The single handled flag unlinks the route as soon as either of its two
device references matched, even when the other one still points at a
different live device.  Does that break the scan_all fallback this patch
relies on?

The divergent case is the one the changelog describes.  For
RTF_LOCAL/RTF_ANYCAST routes ip6_rt_get_dev_rcu() returns the netns
loopback or the L3 master:

net/ipv6/route.c: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;
		else if (!netif_is_l3_master(dev))
			dev = dev_net(dev)->loopback_dev;
	...
}

while ip6_rt_copy_init() keeps the original interface's inet6_dev via
rt->rt6i_idev = in6_dev_get(nh->fib_nh_dev), so dst_dev(&rt->dst) is vrf0 or
lo and rt6i_idev->dev is eth0.  Such a clone reaches the uncached list from
the FLOWI_FLAG_KNOWN_NH branch of ip6_pol_route():

net/ipv6/route.c:ip6_pol_route() {
	rt = ip6_rt_cache_alloc(&res, &fl6->daddr, NULL);

	if (rt) {
		...
		rt6_uncached_list_add(rt);
}

Removing eth0 then takes only the first branch, sets handled = true and
unlinks the entry, while rt->dst.dev_rcu / dst.dev_tracker still hold a
reference on vrf0.

Deleting vrf0 afterwards walks all 64 buckets, but the entry is no longer on
any list, so scan_all cannot repair it.  The per-second NETDEV_UNREGISTER
rebroadcast from netdev_wait_allrefs_any() has the same problem.  Since the
flush does not set dst->obsolete, a dst parked in sk_dst_cache or in a
delayed qdisc can hold that reference for an unbounded time, so
unregister_netdevice keeps waiting for vrf0 to become free and the deleting
task stays in netdev_run_todo; when the pinned device is a netns loopback,
cleanup_net() is stuck too.

The reverse order has the mirror problem: deleting the VRF or loopback first
unlinks on the dst_dev() match while rt6i_idev still pins eth0 through
inet6_dev->dev_tracker.

Would it be better to unlink only when no device reference remains, for
example:

		if (handled && dst_dev(&rt->dst) != dev &&
		    (!rt->rt6i_idev || rt->rt6i_idev->dev != dev))
			list_del_init(&rt->dst.rt_uncached);

or more directly, only delist once both rt6i_idev->dev and dst_dev() have
been repointed at blackhole_netdev?

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260917-hash-bucket-route-lists-v3-0-30493a37b6eb%40cloudflare.com

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

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found more severe
issue(s) in other patches of this series. This mail is only an FYI, in case
you want to address the nit picks below when you respin.

Low priority / nit picks for your consideration:

- [Low] test_ipv6_uncached_mismatch() mutates the shared topology built
  once by setup() and never restores it: it installs a root netem qdisc…
- [Low] The test's regression signal depends on bucket separation that
  the implementation does not guarantee.
- [Low] test_ipv6_uncached_mismatch() replaces the VRF root qdisc with
  `netem limit 1 delay 10s` (line 397) but neither checks nor logs the…
- [Low] The test verifies 'route retained in the VRF qdisc' with a one-
  shot `tc -s qdisc show` snapshot (line 408) and then performs the…

--

selftests: net: cover IPv6 uncached route device mismatch

This adds test_ipv6_uncached_mismatch() to vrf-xfrm-tests.sh, which installs
a delayed netem qdisc on the VRF, adds a local IPv6 route on the VRF member
interface, sends raw-header packets with msg_zerocopy, and then deletes the
member interface while the uncached route is still referenced by the qdisc
backlog.

> 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

[Severity: Low]
Should the result of this qdisc replacement be checked or logged like the
other setup commands in this script?  The script does not use set -e, so the
status is discarded here.

The main flow has already installed a different qdisc on the same device
before calling this function:

	run_cmd_host1 tc qdisc add dev ${VRF} root netem delay 100ms
	echo
	echo "netem qdisc on VRF device"
	run_tests

If the replace fails, the 100ms qdisc stays in place.  msg_zerocopy with
-t 0 runs for about 200ms (parse_opts() computes
cfg_runtime_ms = 200 + strtoul(optarg, NULL, 10) * 1000), so packets
enqueued in the last 100ms are still in the backlog when tc -s qdisc show is
sampled and the grep for a non-empty backlog still matches.  That backlog
then drains in about 100ms, well within the 2s deletion timeout, so every
added check can pass without ever holding a route across the device
deletion.  Would checking the replace status here close that gap?

> +	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"
> +

[Severity: Low]
Is the retention observed by this snapshot guaranteed to still hold when the
delete runs a few statements later?

The only thing keeping the skb, and therefore the uncached route reference,
in the qdisc is the netem 10s timer, and that timer is armed at enqueue time
during the msg_zerocopy run rather than at the moment of this check.  With
-t 0 the sender runs about 200ms, so roughly 9.8s of slack remain between
the tc -s qdisc show sample and run_cmd_host1 timeout 2 ip link del eth0.

If that slack is consumed by shell forks, grep, printf, or scheduling stalls
on a loaded single-CPU or nested VM, netem has already dequeued the packet
and dropped the dst/idev references, so the delete completes promptly
regardless of whether the kernel bug is present, and the test reports a
pass.  Would a longer netem delay, or re-sampling the backlog immediately
before the delete, make the assertion self-checking?

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

[Severity: Low]
Can a hash bucket collision make this check pass on a kernel where the
insertion key regressed?

rt6_uncached_list_add() in net/ipv6/route.c reduces the keying device
pointer to one of 64 buckets:

	ul = &table->buckets[hash_ptr(dev, RT6_UNCACHED_HASH_BITS)];

and teardown of a non-master device scans only that one bucket:

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

With RT6_UNCACHED_HASH_BITS == 6, if a regression reintroduced keying by
dst_dev() (the VRF) and hash_ptr(vrf) happens to land in the same bucket as
hash_ptr(eth0), the eth0 scan still reaches the wrongly indexed route,
rt6_uncached_list_flush() matches on rt6i_idev->dev == eth0 and releases the
reference, so the delete succeeds and the test passes.  The pointers differ
per boot, so that is roughly a 1-in-64 chance per run.  Would creating
several VRF and member pairs make the signal independent of bucket layout?

[Severity: Low]
Does this function need to undo the state it installs?

test_ipv6_uncached_mismatch() mutates the topology built once by setup() and
never restores it:

  - a root netem qdisc with limit 1 delay 10s on the VRF
  - a local IPv6 route on eth0
  - deletion of eth0, which is the VRF's only member and the only veth to
    host2

There is no matching tc qdisc del or ip -6 route del on any exit path, and
both early returns (the [ $rc -ne 0 ] && return after the sender, and the
backlog-check failure path) skip even the eth0 deletion, leaving the 10s
netem qdisc behind.

That makes the function correct only as the final statement of the script,
and that constraint isn't documented anywhere, so anything appended after it
runs against a namespace with no eth0 and a limit 1 / 10s-delay qdisc.

Related, and not introduced by this patch: the script has no trap cleanup
EXIT, and the cleanup 2>/dev/null in the main flow runs before setup while
$host1/$host2 are still unset, so the namespaces and this state are simply
abandoned at exit.  setup_ns() in tools/testing/selftests/net/lib.sh only
records names in NS_LIST and does not arrange teardown.  Since setup_ns()
picks a fresh randomized name per invocation, a re-run does not inherit the
broken topology, so what remains is leaked state plus the undocumented
ordering requirement.

>  
>  ################################################################################
>  # 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}
>  

Would a short comment here noting that this test must stay last, or a
cleanup/restore inside the function, help whoever extends the script next?

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260917-hash-bucket-route-lists-v3-0-30493a37b6eb%40cloudflare.com