sysfs: use rb-tree for name lookups Use red-black tree for name lookups. This patch improves time to create 10000 block devices from 120 seconds to 68 seconds. Signed-off-by: Mikulas Patocka <mpatocka@xxxxxxxxxx> --- fs/sysfs/dir.c | 45 +++++++++++++++++++++++++++++++++++++++------ fs/sysfs/sysfs.h | 5 +++++ 2 files changed, 44 insertions(+), 6 deletions(-) Index: linux-3.0-rc7-fast/fs/sysfs/sysfs.h =================================================================== --- linux-3.0-rc7-fast.orig/fs/sysfs/sysfs.h 2011-07-18 20:06:24.000000000 +0200 +++ linux-3.0-rc7-fast/fs/sysfs/sysfs.h 2011-07-18 20:16:32.000000000 +0200 @@ -11,6 +11,7 @@ #include <linux/lockdep.h> #include <linux/kobject_ns.h> #include <linux/fs.h> +#include <linux/rbtree.h> struct sysfs_open_dirent; @@ -21,6 +22,8 @@ struct sysfs_elem_dir { struct sysfs_dirent *children; unsigned long subdirs; + + struct rb_root name_tree; }; struct sysfs_elem_symlink { @@ -61,6 +64,8 @@ struct sysfs_dirent { struct sysfs_dirent *s_sibling; const char *s_name; + struct rb_node name_node; + const void *s_ns; /* namespace tag */ union { struct sysfs_elem_dir s_dir; Index: linux-3.0-rc7-fast/fs/sysfs/dir.c =================================================================== --- linux-3.0-rc7-fast.orig/fs/sysfs/dir.c 2011-07-18 20:06:24.000000000 +0200 +++ linux-3.0-rc7-fast/fs/sysfs/dir.c 2011-07-18 20:16:02.000000000 +0200 @@ -45,6 +45,9 @@ static void sysfs_link_sibling(struct sy struct sysfs_dirent *parent_sd = sd->s_parent; struct sysfs_dirent **pos; + struct rb_node **p; + struct rb_node *parent; + BUG_ON(sd->s_sibling); if (sysfs_type(sd) == SYSFS_DIR) @@ -60,6 +63,26 @@ static void sysfs_link_sibling(struct sy } sd->s_sibling = *pos; *pos = sd; + + p = &parent_sd->s_dir.name_tree.rb_node; + parent = NULL; + while (*p) { + int c; + parent = *p; +#define node rb_entry(parent, struct sysfs_dirent, name_node) + c = strcmp(sd->s_name, node->s_name); + if (c < 0) { + p = &node->name_node.rb_left; + } else if (c > 0) { + p = &node->name_node.rb_right; + } else { + printk(KERN_CRIT "sysfs: inserting duplicate filename '%s'\n", sd->s_name); + BUG(); + } +#undef node + } + rb_link_node(&sd->name_node, parent, p); + rb_insert_color(&sd->name_node, &parent_sd->s_dir.name_tree); } /** @@ -87,6 +110,8 @@ static void sysfs_unlink_sibling(struct break; } } + + rb_erase(&sd->name_node, &sd->s_parent->s_dir.name_tree); } /** @@ -546,14 +571,22 @@ struct sysfs_dirent *sysfs_find_dirent(s const void *ns, const unsigned char *name) { - struct sysfs_dirent *sd; + struct rb_node *p = parent_sd->s_dir.name_tree.rb_node; - for (sd = parent_sd->s_dir.children; sd; sd = sd->s_sibling) { - if (ns && sd->s_ns && (sd->s_ns != ns)) - continue; - if (!strcmp(sd->s_name, name)) - return sd; + while (p) { + int c; +#define node rb_entry(p, struct sysfs_dirent, name_node) + c = strcmp(name, node->s_name); + if (c < 0) { + p = node->name_node.rb_left; + } else if (c > 0) { + p = node->name_node.rb_right; + } else { + return node; + } +#undef node } + return NULL; } -- dm-devel mailing list dm-devel@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/dm-devel