[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

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/

[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

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

[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