diff options
author | Eric W. Biederman <ebiederm@xmission.com> | 2012-01-09 17:24:30 -0800 |
---|---|---|
committer | Eric W. Biederman <ebiederm@xmission.com> | 2012-01-24 16:40:30 -0800 |
commit | ac13ac6f4c6c0504d2c927862216f4e422a2c0b5 (patch) | |
tree | 87d0d698e79b911428b8f8e2f357a27f74c854f9 /include/linux/sysctl.h | |
parent | 9e3d47df35abd6430fed04fb40a76c7358b1e815 (diff) | |
download | linux-stable-ac13ac6f4c6c0504d2c927862216f4e422a2c0b5.tar.gz linux-stable-ac13ac6f4c6c0504d2c927862216f4e422a2c0b5.tar.bz2 linux-stable-ac13ac6f4c6c0504d2c927862216f4e422a2c0b5.zip |
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>
Diffstat (limited to 'include/linux/sysctl.h')
-rw-r--r-- | include/linux/sysctl.h | 10 |
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 { |