netdev - Re: v6: faster tree-based sysctl implementation

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]

Date:	Tue, 06 Dec 2011 17:47:09 +0100
From:	Damien Millescamps <damien.millescamps@...nd.com>
To:	netdev@...r.kernel.org
CC:	"Eric W . Biederman" <ebiederm@...ssion.com>,
	linux-kernel <linux-kernel@...r.kernel.org>,
	Octavian Purdila <tavi@...pub.ro>,
	"David S . Miller" <davem@...emloft.net>,
	Alexey Dobriyan <adobriyan@...il.com>
Subject: Re: v6: faster tree-based sysctl implementation

On 12/06/2011 03:33 PM, Lucian Adrian Grijincu wrote:
> On Tue, Dec 6, 2011 at 4:11 PM, Anca Emanuel<anca.emanuel@...il.com>  wrote:
>> time modprobe dummy numdummies=1000FATAL: Error inserting dummy
>> (/lib/modules/3.2.0-3-generic/kernel/drivers/net/dummy.ko): Operation
>> not permitted
> Generally when you get "Operation not permitted" you should try with sudo.
> This is the man-page: http://xkcd.com/149/ :)
>
>
>> What are the practical problems you solve with this ?
>> Name one or more.
>
> Sysctl uses a slow algorithm: O(N^2) for insertions, O(N) for lookup,
> with a relatively big constant.
> The performance is acceptable when N is small, but sometimes it can
> grow to bigger values.
> One case where N can grow to very large values is when you add network
> interfaces.
>
> Some companies (like IXIACOM which sponsored this work at the
> beginning of this year) have use-cases in which they need 10^3..10^6
> network interfaces. The current sysctl implementation is unacceptable
> for them.
>
> @Damien Millescamps might have some input on where he needs better
> sysctl performance as he prompted me to re-send this patch series.
>
> This algorithm is O(N * logN) for insert and O(logN) for lookup.
>
>

A use-case for wanting to be able to create several interfaces is to 
have a "tunnel" server handling several dynamic point to point connections.

The current implementation dates from the "sysctl cleanup" from Al Viro: 
commits 734550921e9b7ab924a43aa3d0bd4239dac4fbf1 to 
ae7edecc9b8810770a8e5cb9a466ea4bdcfa8401, plus some later fixes.
This implementation was suboptimal, and modifying it necessitates a lot 
of reworking of the structures used, so the diff is clearly big. Also 
Lucian took time to add lots of comment to help understanding and using 
the new implementation, which also explains the amount of modifications 
in kernel/sysctl.c

For information, the main idea is to implement sysctl, which has a 
filesystem structure, like most other file system implementation (like 
sysfs), i.e. using an rb_tree.

-- 
damien

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html