v6: faster tree-based sysctl implementation

This is version 6 of a patch series that introduces a faster/leaner
sysctl internal implementation.
git://github.com/luciang/linux-2.6-new-sysctl.git  v6-new-sysctl-alg
A subset of patches that add the minimal set of patches with the new
algorithm is here:
 git://github.com/luciang/linux-2.6-new-sysctl.git  v6-new-sysctl-alg-slim


= Stats =

$ time modprobe dummy numdummies=N

Without this patch series :(
- ipv4 only
  -  N=1000  time= 0m 07s
  -  N=2000  time= 0m 38s
  -  N=4000  time= 4m 01s
- ipv4 and ipv6
  -  N=1000  time= 0m 35s
  -  N=2000  time= 3m 09s
  -  N=4000  time=14m 27s

With this patch series :)
- ipv4 only
  -  N=1000  time= 0m  0.31s
  -  N=2000  time= 0m  1.23s
  -  N=4000  time= 0m  5.14s
  -  N=8000  time= 0m 20.20s
- ipv4 and ipv6
  -  N=1000  time= 0m  0.70s
  -  N=2000  time= 0m  1.93s
  -  N=4000  time= 0m  7.03s
  -  N=8000  time= 0m 40.89s



= Changes =
since v5:
 - https://lkml.org/lkml/2011/6/2/332 - nothing much because of lack
of review. Echo, echo, echo ... :)
 - minor tweaks
 - rebased on 3.2-rc4


since v4: - http://thread.gmane.org/gmane.linux.network/196495/focus=1144143
- rebased on 3.0-rc1 - added a new patch manually register
kernel/usermodehelper which   was added in 3.0-rc1 - minor changes to
the "sysctl: simplify find_in_table" patch

since v3: - http://thread.gmane.org/gmane.linux.network/196495/ -
removed a bad patch that shrinked a counter from int to u8

since v2: - http://thread.gmane.org/gmane.linux.kernel/1137032/focus=3D194748
- added a compatibility layer to support old registering complex
sysctl trees. This layer will be deleted once all users of the   old
are changed. - subdirectories and netns correspondent dirs are now
held in rbtrees - split of from the patches that make changes in the
rest of the tree - rebased on top of 2.6.39

since v1: - http://thread.gmane.org/gmane.linux.kernel/1133667 -
rebased on top of 2.6.39-rc6 - split the patch that adds the new
algorithm and data structures. - fixed a few bugs lingering in the old
code - shrinked a reference counter - added a new reference counter to
maintain ownership information - added method to register an empty
sysctl dir and converted some users - added checks enforcing the rule
that a non-netns specific directory may   not be registered after a
netns specific one has already been registered. - added cookie
support: register a piece of data with the header to be   used to make
simple conversions on the ctl_table.


= Summary =

Part 1: introduce compatibility layer:
  sysctl: introduce temporary sysctl wrappers
  sysctl: register only tables of sysctl files

Part 2: minimal changes to sysctl users:
  sysctl: call sysctl_init before the first sysctl registration
  sysctl: no-child: manually register kernel/random
  sysctl: no-child: manually register kernel/usermodehelper
  sysctl: no-child: manually register kernel/keys
  sysctl: no-child: manually register fs/inotify
  sysctl: no-child: manually register fs/epoll
  sysctl: no-child: manually register root tables

Part 3: cleanups simplifying the new algorithm:
  sysctl: faster reimplementation of sysctl_check_table
  sysctl: remove useless ctl_table->parent field
  sysctl: simplify find_in_table
  sysctl: sysctl_head_grab defaults to root header on NULL
  sysctl: delete useless grab_header function
  sysctl: rename ->used to ->ctl_use_refs
  sysctl: rename sysctl_head_grab/finish to sysctl_use_header/unuse
  sysctl: rename sysctl_head_next to sysctl_use_next_header
  sysctl: split ->count into ctl_procfs_refs and ctl_header_refs
  sysctl: rename sysctl_head_get/put to sysctl_proc_inode_get/put
  sysctl: rename (un)use_table to __sysctl_(un)use_header
  sysctl: simplify ->permissions hook
  sysctl: move removal from list out of start_unregistering
  sysctl: introduce ctl_table_group and ctl_table_group_ops



Part 4: new algorithm/data structures:
  sysctl: faster tree-based sysctl implementation



Part 5: checks/warns requested during review:
  sysctl: add duplicate entry and sanity ctl_table checks
  sysctl: alloc ctl_table_header with kmem_cache
  sysctl: check netns-specific registration order respected
  sysctl: warn if registration/unregistration order is not respected
  sysctl: always perform sysctl checks
  sysctl: reorder members of ctl_table_header (cleanup)
  sysctl: add ctl_type member

Part 6: further performance optimisations:
  sysctl: replace subdirectory list with rbtree
  sysctl: replace netns corresp list with rbtree
  sysctl: union-ize some ctl_table_header fields

Part 7: Eric requested ability to register an empty dir:
  sysctl: add register_sysctl_dir: register an empty sysctl directory

Part 8: unrequested feature I'd like to piggy back :)
  sysctl: add ctl_cookie and ctl_cookie_handler
  sysctl: add cookie to __register_sysctl_paths
  sysctl: add register_net_sysctl_table_net_cookie

 drivers/char/random.c            |   27 +-
 fs/eventpoll.c                   |   22 +-
 fs/notify/inotify/inotify_user.c |   22 +-
 fs/proc/inode.c                  |    2 +-
 fs/proc/proc_sysctl.c            |  236 +++++---
 include/linux/inotify.h          |    2 -
 include/linux/key.h              |    3 -
 include/linux/kmod.h             |    3 -
 include/linux/poll.h             |    2 -
 include/linux/sysctl.h           |  221 +++++---
 include/net/net_namespace.h      |    4 +-
 init/main.c                      |    1 +
 kernel/Makefile                  |    5 +-
 kernel/kmod.c                    |   14 +-
 kernel/sysctl.c                  | 1170 ++++++++++++++++++++++++++++----------
 kernel/sysctl_check.c            |  316 +++++++----
 lib/Kconfig.debug                |    8 -
 net/sysctl_net.c                 |   86 ++--
 security/keys/key.c              |    7 +
 security/keys/sysctl.c           |   18 +-
 20 files changed, 1500 insertions(+), 669 deletions(-)

-- 
1.7.5.4
-- 
 .
..: Lucian

time modprobe dummy numdummies=1000FATAL: Error inserting dummy
(/lib/modules/3.2.0-3-generic/kernel/drivers/net/dummy.ko): Operation
not permitted
real	0m0.192suser	0m0.000ssys	0m0.012s
That was on an Ubuntu system.
What are the practical problems you solve with this ?
Name one or more.

You add more code. This is not good. If you reduce the code, then it
will be interesting.

On Tue, Dec 6, 2011 at 4:11 PM, Anca Emanuel [off-list ref] 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.

You add more code. This is not good. If you reduce the code, then it
will be interesting.

Thank you. I know that, but it's easier said than done. I'd welcome
some feedback in what could be simplified in my patches :)

-- 
 .
..: Lucian

On 12/06/2011 03:33 PM, Lucian Adrian Grijincu wrote:

On Tue, Dec 6, 2011 at 4:11 PM, Anca Emanuel[off-list ref]  wrote:

quoted

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/ :)

quoted

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

On Tue, Dec 06, 2011 at 05:47:09PM +0100, Damien Millescamps wrote:

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.

I can chime in that this is also an issue for edge routers terminating 
lots of PPPoE, L2TP or even DHCP sessions.  Interfaces numbering in the 
thousands or tens of thousands are common for 1G or 10G worth of bandwidth 
aggregation.

		-ben
-- 
"Thought is the essence of where you are now."

On Tue, Dec 6, 2011 at 4:33 PM, Lucian Adrian Grijincu
[off-list ref] wrote:

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.

[snip]

This algorithm is O(N * logN) for insert and O(logN) for lookup.

quoted

You add more code. This is not good. If you reduce the code, then it
will be interesting.

Thank you. I know that, but it's easier said than done. I'd welcome
some feedback in what could be simplified in my patches :)

From an "airplane view" you can make the algorithms generic, and find

other places in kernel that can use them.
If you do that, I am sure you will get the attention.

You can ask Stephen Rothwell to include your tree in next.
git://github.com/luciang/linux-2.6-new-sysctl.git  v6-new-sysctl-alg

On Wed, Dec 7, 2011 at 2:08 AM, Anca Emanuel [off-list ref] wrote:

You can ask Stephen Rothwell to include your tree in next.
git://github.com/luciang/linux-2.6-new-sysctl.git  v6-new-sysctl-alg

Thank you Anca, but I don't want to pollute Stephen's linux-next tree ATM.
I'd wait until a maintainer chimes in and agrees that this approach is sound.

-- 
 .
..: Lucian