netdev - Re: RFC: Should net namespaces scale up (>10k) ?

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <a8a7bfc4-312d-497b-83c4-64c1207d86e3@orange.com>
Date: Mon, 16 Sep 2024 23:36:33 +0200
From: Alexandre Ferrieux <alexandre.ferrieux@...il.com>
To: Przemek Kitszel <przemyslaw.kitszel@...el.com>,
 Alexandre Ferrieux <alexandre.ferrieux@...il.com>
Cc: horms@...nel.org, Eric Dumazet <edumazet@...gle.com>,
 netdev@...r.kernel.org
Subject: Re: RFC: Should net namespaces scale up (>10k) ?

On 16/09/2024 12:13, Przemek Kitszel wrote:
> On 9/15/24 22:49, Alexandre Ferrieux wrote:
>>
>> 2. When moving an interface (eg an IPVLAN slave) to another netns,
>> __dev_change_net_namespace() calls peernet2id_alloc() in order to get
>> an ID for the target namespace. This again incurs a full scan of the
>> netns list:
>>
>>          int id = idr_for_each(&net->netns_ids, net_eq_idr, peer);
> 
> this piece is inside of __peernet2id(), which is called in for_each_net
> loop, making it O(n^2):
> 
>   548│         for_each_net(tmp) {
>   549│                 int id;
>   550│
>   551│                 spin_lock_bh(&tmp->nsid_lock);
>   552│                 id = __peernet2id(tmp, net);

You're right, though that happens only within unhash_nsid(), which is called 
when deleting an nsnet.

Obviously this quadratic horror you found is even worse than the linear one I 
reported, but it can arguably be worked around in tester-like workloads (just 
never delete the namespaces). While the linear one cannot, as long as you need 
to move any interface into the newly created thousands of namespaces.