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

[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@vger.kernel.org
Reported-by: Vega <vega@nebusec.ai>
Assisted-by: Codex:gpt-5.4
Signed-off-by: Zihan Xi <zihanx@nebusec.ai>
---
 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

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;

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

[zihan xi]

On Mon, Aug 31, 2026 at 7:07 PM Ido Schimmel <idosch@nvidia.com> wrote:
>
> 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.
>

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

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