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@xxxxxxxxxx> 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;
>