netdev - Re: Massive hash collisions on FIB

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CANn89i+nMyTsY8+KcoYXZPor8Y3r+rbt5LvZe1sC3yZq1wqGeQ@mail.gmail.com>
Date: Tue, 24 Sep 2024 16:36:39 +0200
From: Eric Dumazet <edumazet@...gle.com>
To: Alexandre Ferrieux <alexandre.ferrieux@...il.com>
Cc: Simon Horman <horms@...nel.org>, Przemek Kitszel <przemyslaw.kitszel@...el.com>, 
	netdev@...r.kernel.org
Subject: Re: Massive hash collisions on FIB

On Tue, Sep 24, 2024 at 4:06 PM Alexandre Ferrieux
<alexandre.ferrieux@...il.com> wrote:
>
> On 17/09/2024 08:59, Eric Dumazet wrote:
> >
> >> What do you think ?
> >
> > I do not see any blocker for making things more scalable.
> >
> > It is only a matter of time and interest. I think that 99.99 % of
> > linux hosts around the world
> > have less than 10 netns.
> >
> > RTNL removal is a little bit harder (and we hit RTNL contention even
> > with less than 10 netns around)
>
> Given this encouragement, I'm proceeding towards the the "million-tunnel baby".
> And knowing where the current road bumps are, workarounds are possible: instead
> of a direct 1M fanout of (netns+interface), I'm doing 10k netns with 100
> interfaces each, which works like a charm.
>
> But doing this I met an entirely new kind of bottleneck: the single FIB
> hashtable, shared by all netns, lends itself to massive collision if many netns
> contain the same local address.
>
> Indeed, in this situation, the fib_inetaddr_notifier ends up inserting a local
> route for the address, and the only "moving part" in the hash input is the
> address itself.
>
> As an example, after creating 7000 veth pairs and moving their "right half" to
> 7000 namespaces, an "ip addr add 192.168.1.2/32 dev $D" on one of them hits a
> bucket of depth 7000.

Shocking

>
> To solve this, I'd naively inject a few bits of entropy from the netns itself
> (inode number, middle bits of (struct net *) address, etc.), by XORing them to
> the hash value. Unless I'm mistaken, the netns is always unambiguous when a FIB
> decision is made, be it for a packet or for some interface configuration task.
>
> Would that be acceptable ?

Sure, but please use the standard way : net_hash_mix(net)