Re: [PATCH net 1/1] ipv4: fib: avoid quadratic table ID lookup
From: zihan xi <hidden>
Date: 2026-08-31 12:16:04
Also in:
lkml, stable
On Mon, Aug 31, 2026 at 7:07 PM Ido Schimmel [off-list ref] wrote:
On Sat, Aug 29, 2026 at 06:24:57AM +0000, Zihan Xi wrote:quoted
fib_empty_table() probes every table ID from 1 until it finds a free one. Since IPv4 tables are stored in a 256-bucket hash table, a dense set of IDs makes the probes repeatedly walk growing hash chains while RTNL is held. Count the existing tables once and use a bitmap for the bounded range that can contain the first free ID. This keeps table-ID selection linear in the number of tables instead of quadratic, without changing the lowest-free-ID behavior.TBH, I wasn't even aware of this "table 0" functionality and I'm quite certain it's unused nowadays: 1. IPv4 specific: # ip -6 rule add from 2001:db8:1::1 table 0 Error: Invalid table. 2. Not documented in ip-rule man page: " table TABLEID the routing table identifier to lookup if the rule selector matches. It is also possible to use lookup instead of table. " 3. No kernel selftests despite ip-rule having good coverage. 4. Quirky. Requires dumping the rules or listening to netlink notifications to discover the allocated table ID. So, for now, I suggest bounding the maximum table ID that can be automatically allocated. Something like [1]. I will add a deprecation warning in net-next.
Thanks for the review and the suggested patch. I wasn't aware how unused this automatic table-0 assignment is either. I'll drop the bitmap rewrite and send a v2 that just caps the automatically allocated ID at 4096 as you proposed.
FTR, I did consider storing the tables in something like xarray, but:
1. We would still need to keep the hash table given the analysis Jakub
shared in commit 759ab1edb56c ("net: store netdevs in an xarray").
Xarray only starts being worthwhile at around 1k tables and most
deployments never reach this number.
2. It requires adding per-netns xarray for a functionality that is
unlikely to be used today.Agreed, bounding the auto-allocation is the simpler fix here. Thanks, Zihan
quoted hunk ↗ jump to hunk
[1]diff --git a/net/ipv4/fib_rules.c b/net/ipv4/fib_rules.c index 4edb0dca7be8..2e8629df34bb 100644 --- a/net/ipv4/fib_rules.c +++ b/net/ipv4/fib_rules.c@@ -214,6 +214,8 @@ INDIRECT_CALLABLE_SCOPE int fib4_rule_match(struct fib_rule *rule, return 1; } +#define FIB_MAX_AUTO_TABLE_ID 4096 + static struct fib_table *fib_empty_table(struct net *net) { u32 id = 1;@@ -222,7 +224,7 @@ static struct fib_table *fib_empty_table(struct net *net) if (!fib_get_table(net, id)) return fib_new_table(net, id); - if (id++ == RT_TABLE_MAX) + if (id++ == FIB_MAX_AUTO_TABLE_ID) break; } return NULL;