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 <[email protected]>
---
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-fa9b9f30e...@cloudflare.com
To: "David S. Miller" <[email protected]>
To: Eric Dumazet <[email protected]>
To: Jakub Kicinski <[email protected]>
To: Paolo Abeni <[email protected]>
To: Simon Horman <[email protected]>
To: David Ahern <[email protected]>
To: Ido Schimmel <[email protected]>
To: Shuah Khan <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: [email protected]
---
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 <[email protected]>
