summaryrefslogtreecommitdiff
path: root/include/linux/sysctl.h
diff options
context:
space:
mode:
authorEric W. Biederman <ebiederm@xmission.com>2012-01-10 05:24:30 +0400
committerEric W. Biederman <ebiederm@xmission.com>2012-01-25 04:40:30 +0400
commitac13ac6f4c6c0504d2c927862216f4e422a2c0b5 (patch)
tree87d0d698e79b911428b8f8e2f357a27f74c854f9 /include/linux/sysctl.h
parent9e3d47df35abd6430fed04fb40a76c7358b1e815 (diff)
downloadlinux-ac13ac6f4c6c0504d2c927862216f4e422a2c0b5.tar.xz
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.h10
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 {