linux-kernel - [PATCHES] improve sysfs performance, make it O(log n)

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-next>] [day] [month] [year] [list]

Date:	Wed, 20 Jul 2011 18:56:50 -0400 (EDT)
From:	Mikulas Patocka <mpatocka@...hat.com>
To:	Zdenek Kabelac <zkabelac@...hat.com>,
	Milan Broz <mbroz@...hat.com>,
	"Alasdair G. Kergon" <agk@...hat.com>, dm-devel@...hat.com
cc:	gregkh@...e.de, linux-kernel@...r.kernel.org
Subject: [PATCHES] improve sysfs performance, make it O(log n)

Hi

Here are 5 patches to make sysfs O(log n) and improve performance on 
operations with many block devices.

Patch 1 changes synchronize_rcu() to synchronize_rcu_expedited(), it 
causes massive speedup when deleting many block devices.

Patch 2 fixes inefficient i_nlink calculation in sysfs.

Patch 3 makes name lookups use rb-tree.

Patch 4 removes s_sibling hack (it has no effect on performance).

Patch 5 makes inode number lookups use rb-tree --- thus making all types 
of sysfs directory operations O(log n).

Performance testing --- 10000 dm devices created with dmsetup:

The numbers are time in seconds to perform these operations:
1. create 10000 devices
2. ls -la /sys/block
3. ls -al /sys/block after a cache flush (echo 3 >/proc/sys/vm/drop_caches)
4. dmsetup remove_all

no patches	109	9.8	12	1624
patch 1		109	9.1	12	15
patches 1,2	120	0.19	3.0	16
patches 1,2,3	68	0.17	0.47	12
patches 1,2,3,4	68	0.15	0.48	11
all patches	37	0.16	0.46	3.3

Mikulas
View attachment "bdi-synchronize-rcu-expedited.patch" of type "TEXT/PLAIN" (871 bytes)

View attachment "sysfs-count-subdirs.patch" of type "TEXT/PLAIN" (2885 bytes)

View attachment "sysfs-name-tree.patch" of type "TEXT/PLAIN" (3226 bytes)

View attachment "sysfs-unhack-sibling.patch" of type "TEXT/PLAIN" (3244 bytes)

View attachment "sysfs-inode-tree.patch" of type "TEXT/PLAIN" (5685 bytes)