Re: [PATCH net 1/1] ipv4: fib: avoid quadratic table ID lookup

[Ido Schimmel]

On Sat, Aug 29, 2026 at 06:24:57AM +0000, Zihan Xi wrote:
> 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.

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.

[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;