sysctl: Index sysctl directories with rbtrees.

One of the most important jobs of sysctl is to export network stack
tunables.  Several of those tunables are per network device.  In
several instances people are running with 1000+ network devices in
there network stacks, which makes the simple per directory linked list
in sysctl a scaling bottleneck.   Replace O(N^2) sysctl insertion and
lookup times with O(NlogN) by using an rbtree to index the sysctl
directories.

Benchmark before:
    make-dummies 0 999 -> 0.32s
    rmmod dummy        -> 0.12s
    make-dummies 0 9999 -> 1m17s
    rmmod dummy         -> 17s

Benchmark after:
    make-dummies 0 999 -> 0.074s
    rmmod dummy        -> 0.070s
    make-dummies 0 9999 -> 3.4s
    rmmod dummy         -> 0.44s

Benchmark after (without dev_snmp6):
    make-dummies 0 9999 -> 0.75s
    rmmod dummy         -> 0.44s
    make-dummies 0 99999 -> 11s
    rmmod dummy          -> 4.3s

At 10,000 dummy devices the bottleneck becomes the time to add and
remove the files under /proc/sys/net/dev_snmp6.  I have commented
out the code that adds and removes files under /proc/sys/net/dev_snmp6
and taken measurments of creating and destroying 100,000 dummies to
verify the sysctl continues to scale.

Signed-off-by: Eric W. Biederman <ebiederm@xmission.com>

1 files changed, 8 insertions, 2 deletions

diff --git a/include/linux/sysctl.h b/include/linux/sysctl.h
index 36dec756ef9d..35c50ed36fc9 100644
--- a/include/linux/sysctl.h
+++ b/include/linux/sysctl.h
@@ -932,6 +932,7 @@ enum
 #include <linux/list.h>
 #include <linux/rcupdate.h>
 #include <linux/wait.h>
+#include <linux/rbtree.h>
 
 /* For the /proc/sys support */
 struct ctl_table;
@@ -1023,6 +1024,11 @@ struct ctl_table
         void *extra2;
 };
 
+struct ctl_node {
+        struct rb_node node;
+        struct ctl_table_header *header;
+};
+
 /* struct ctl_table_header is used to maintain dynamic lists of
    struct ctl_table trees. */
 struct ctl_table_header
@@ -1030,7 +1036,6 @@ struct ctl_table_header
         union {
                 struct {
                         struct ctl_table *ctl_table;
-                        struct list_head ctl_entry;
                         int used;
                         int count;
                         int nreg;
@@ -1042,12 +1047,13 @@ struct ctl_table_header
         struct ctl_table_root *root;
         struct ctl_table_set *set;
         struct ctl_dir *parent;
+        struct ctl_node *node;
 };
 
 struct ctl_dir {
         /* Header must be at the start of ctl_dir */
         struct ctl_table_header header;
-        struct list_head list;
+        struct rb_root root;
 };
 
 struct ctl_table_set {