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

[Zihan Xi]

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.

Fixes: 1af5a8c4a11c ("[IPV4]: Increase number of possible routing tables to 2^32")
Cc: stable@xxxxxxxxxxxxxxx
Reported-by: Vega <vega@xxxxxxxxxx>
Assisted-by: Codex:gpt-5.4
Signed-off-by: Zihan Xi <zihanx@xxxxxxxxxx>
---
 net/ipv4/fib_rules.c | 44 +++++++++++++++++++++++++++++++++++++-------
 1 file changed, 37 insertions(+), 7 deletions(-)

diff --git a/net/ipv4/fib_rules.c b/net/ipv4/fib_rules.c
index e068a5bac..55751b0d1 100644
--- a/net/ipv4/fib_rules.c
+++ b/net/ipv4/fib_rules.c
@@ -16,6 +16,7 @@
 
 #include <linux/types.h>
 #include <linux/kernel.h>
+#include <linux/bitmap.h>
 #include <linux/netdevice.h>
 #include <linux/netlink.h>
 #include <linux/inetdevice.h>
@@ -216,16 +217,45 @@ INDIRECT_CALLABLE_SCOPE int fib4_rule_match(struct fib_rule *rule,
 
 static struct fib_table *fib_empty_table(struct net *net)
 {
-	u32 id = 1;
+	unsigned int h, count = 0;
+	unsigned long *table_ids;
+	struct fib_table *table;
+	u32 id, max_id;
 
-	while (1) {
-		if (!fib_get_table(net, id))
-			return fib_new_table(net, id);
+	/* The first unused ID is no greater than the number of tables + 1. */
+	rcu_read_lock();
+	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
+		hlist_for_each_entry_rcu(table,
+					 &net->ipv4.fib_table_hash[h],
+					 tb_hlist) {
+			count++;
+		}
+	}
+	rcu_read_unlock();
+
+	if (count == RT_TABLE_MAX)
+		return NULL;
+
+	max_id = count + 1;
+	table_ids = bitmap_zalloc(max_id, GFP_KERNEL);
+	if (!table_ids)
+		return NULL;
 
-		if (id++ == RT_TABLE_MAX)
-			break;
+	rcu_read_lock();
+	for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
+		hlist_for_each_entry_rcu(table,
+					 &net->ipv4.fib_table_hash[h],
+					 tb_hlist) {
+			if (table->tb_id <= max_id)
+				__set_bit(table->tb_id - 1, table_ids);
+		}
 	}
-	return NULL;
+	rcu_read_unlock();
+
+	id = find_first_zero_bit(table_ids, max_id) + 1;
+	bitmap_free(table_ids);
+
+	return fib_new_table(net, id);
 }
 
 static int fib4_nl2rule_dscp(const struct nlattr *nla, struct fib4_rule *rule4,
-- 
2.55.0.windows.3