[PATCH net 1/1] ipv4: fib: avoid quadratic table ID lookup
From: Zihan Xi <hidden>
Date: 2026-08-29 06:25:15
Also in:
lkml, stable
Subsystem:
networking [general], networking [ipv4/ipv6], the rest · Maintainers:
"David S. Miller", Eric Dumazet, Jakub Kicinski, Paolo Abeni, David Ahern, Ido Schimmel, Linus Torvalds
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@vger.kernel.org
Reported-by: Vega <redacted>
Assisted-by: Codex:gpt-5.4
Signed-off-by: Zihan Xi <redacted>
---
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