v6: faster tree-based sysctl implementation

v6: faster tree-based sysctl implementation

[Lucian Adrian Grijincu]

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

Re: v6: faster tree-based sysctl implementation

[Anca Emanuel]

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.

Re: v6: faster tree-based sysctl implementation

[Lucian Adrian Grijincu]

On Tue, Dec 6, 2011 at 4:11 PM, Anca Emanuel <anca.emanuel@gmail.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.


> 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

Re: v6: faster tree-based sysctl implementation

[Damien Millescamps]

On 12/06/2011 03:33 PM, Lucian Adrian Grijincu wrote:
> On Tue, Dec 6, 2011 at 4:11 PM, Anca Emanuel<anca.emanuel@gmail.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

Re: v6: faster tree-based sysctl implementation

[Benjamin LaHaise]

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."

Re: v6: faster tree-based sysctl implementation

[Anca Emanuel]

On Tue, Dec 6, 2011 at 4:33 PM, Lucian Adrian Grijincu
<lucian.grijincu@gmail.com> 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.
>
>
>> 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.

Re: v6: faster tree-based sysctl implementation

[Anca Emanuel]

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

Re: v6: faster tree-based sysctl implementation

[Lucian Adrian Grijincu]

On Wed, Dec 7, 2011 at 2:08 AM, Anca Emanuel <anca.emanuel@gmail.com> 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

Re: v6: faster tree-based sysctl implementation

[Eric W. Biederman]

Lucian Adrian Grijincu <lucian.grijincu@gmail.com> writes:

> On Wed, Dec 7, 2011 at 2:08 AM, Anca Emanuel <anca.emanuel@gmail.com> 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.

Which is my cue to say that I am behind the power curve in reviewing
this.  I will see if I can get to this before the end of the week.

Doing this and getting it right is definitely something we need to do.

We do need to be careful so that the code we wind up with is not just
faster but more maintainable than what we have today.

Thanks for still pushing this,

Eric

Re: v6: faster tree-based sysctl implementation

[Eric W. Biederman]

Bringing this back on list because my reply is a design discussion and
that has every reason to be public.

Lucian Adrian Grijincu <lucian.grijincu@gmail.com> writes:
> On Thu, Dec 8, 2011 at 2:19 AM, Eric W. Biederman <ebiederm@xmission.com> wrote:
> > Which is my cue to say that I am behind the power curve in reviewing
> > this.  I will see if I can get to this before the end of the week.
> 
> 
> Did you had time to take a look over the code?

Not as much time as I would have liked.  However I have looked at it
some and I have brought back some of the state from my head so I
can remember where we last at in the conversation.

> I'm inclined to do a bit of redesign: currently files are kept in
> lists of files and sub-directories in a rbtree; I'd like to put
> everything in a rbtree and make things simpler.

I like the idea of putting everything in an rbtree. And
I like the idea of making things simpler.

> But I'd first like some sort of feedback from you. I wouldn't like to
> spend time working on something only to be told that the base idea of
> the reworking is unacceptable and everything needs to be rewritten.

As things stand I don't think your changes really solve the problem.
At least not if your change log can be believed.

> = New algorithm =
> 
> == Time complexity ==
> 
> - registration of N headers. Registration means adding new directories
>   at each level or incrementing an existing directory's refcount.
> 
>   - O(N * lnN) - if the paths to the headers are evenly distributed
> 
>   - O(N^2) - if most of the headers registered are children of the
>     same parent directory (searching the list of subdirs takes O(N)).
>     There are cases where this happens (e.g. registering sysctl
>     entries for net devices under /proc/sys/net/ipv4|6/conf/device).

This worries me because this is the case that we really care about.

>     A few later patches will add an optimisation, to fix locations
>     that might trigger the O(N^2) issue.

Is it your rb directory tree patch that addresses this?

....

My big concerns.
- I don't want to inflict churn on the users of sysctl unless we are
  certain it will gain us something.

- I really would like to see the core become simple enough that
  non-sysctl experts can look at the code and understand what is going
  on.

It doesn't look like your design has achieved sufficient simplicity yet
so that a non sysctl expert can look the code and understand what is
going on and why.

....

There are two very worthwhile things I see us doing with this patchset.
- Moving the users of sysctl to full directory semantics.
- Improving the data structures so that the data structures are
  efficient.

....

*** Moving the users of sysctl to full directory semantics. ***

As I have been watching the code sysctl has been moving from
a custom union filesystem (where each ctl_table was unioned
together) to normal filesystem semantics.   The last hold out
for union semantics are directories.

The truly weird case in this is "/proc/sys/fs/binfmt_misc/" an empty
directory for mounting the "binfmt_misc" filesystem on.

Which means that fundamentally we need a way to create, remove and
represent empty directories.  So while it is attractive to be lazy
and handle directories with some variant of lazy semantics creating
them when needed and deleting them when there is nothing left in the
directory I don't believe that will work.

Currently sysctl directories live under a relaxed version of the normal
fs rules:
- A directory must be created we can create children in it.
- A directory may not be deleted before we can remove children from it.

Since we in theory already have this strong property I don't see a
benefit of killing the sysctl .child table entry in the beginning of
the patchset.    It means a lot of churn and a lot more code to review
without giving us more useful properties.  Furthermore it retains the
clumsy ctl_path structure, which now that we don't need to add ctl_names
is a very clumsy structure to use.  A normal pathname would be better.

So initially I think at most we want to enhance sysctl_check to verify
that we retain normal directory create and remove discipline with the
current sysctl users.

....

*** Improving the internal sysctl data structures ***

With that the simplest way I can see of dealing with the sysctl data
structures is simply replace our current internal kernel data structures
with something that we want to use, with a compatibility layer from
the current users of sysctl to what we want to see.

My guess is that we would like to have a data structure like:
struct proc_sysctl_dirent {
	struct ctl_table *table; /* Point to the original ctl_table */
        struct rb_node	rb_node;
        struct rb_root  children;
        atomic_t count;
};

That is not perfect but I think building a data structure like that
without changing the userspace interface might actually reduce the
line count of sysctl, and drastically reduce the challenge of
understanding the code.

In a perfect world we might even want to use proc_dir_entry for the
new data structure but that is probably more complication than it is
worth right now.

My biggest concern is how do we handle the duplication of directories
that comes with the network namespace?   There are some weird things
in there.

....

Lucian is that anything like what you were thinking?

Does just improving the sysctl data structures and treating ctl_table
and it's kin as just a weird interface the callers use sound like it
might be a feasible path to you?

Eric

Re: v6: faster tree-based sysctl implementation

[Eric W. Biederman]

I spent some time playing this and managed to get something that works
using proc_dir_entries.  And while it is simpler (600 less lines of
code) it takes about 3x the space of just what using ctl_table entries
does.

I managed to prove to myself that the current sysctl infrastructure
relies the union directory existence semantics pretty strongly.  Despite
all of Al's work to the contrary when he introduced attached_by and kin
in sysctl head.

One nice thing I managed to do was to shift around the problem a bit
so that only at /proc/sys/net do we to namespace weirdness.  Which also
considerably simplifies the problem.

Now that I know that normal unix directory semantics are a lost cause
removing the child entry from ctl_table looks like a very productive
exercise.  

Furthermore it feels like the optimal data structure would be a
directory tree that is created on demand as we create entries,
and a second copy of that directory tree that is per network namespace.

That is very similar to the data structure you wound up with.

So in the next little bit I am going to see if I can combine what
you did and what I did and see if I can come up with something that
is obvious in how it works from looking at it's data structures.

Eric