[PATCH 1/3] sysfs directory scaling: rbtree for dirent nam..

Use an rbtree in sysfs_dirent to speed up file lookup times

Systems with large numbers (tens of thousands and more) of network
interfaces stress the sysfs code in ways that make the linear search for
a name match take far too long. Avoid this by using an rbtree.

Signed-off-by: Benjamin LaHaise <bcrl DeleteThis @kvack.org>
diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c
index 5fad489..30c3fc5 100644
--- a/fs/sysfs/dir.c
+++ b/fs/sysfs/dir.c
@@ -44,6 +44,7 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd)
{
struct sysfs_dirent *parent_sd = sd->s_parent;
struct sysfs_dirent **pos;
+ struct rb_node **new, *parent;

BUG_ON(sd->s_sibling);

@@ -57,6 +58,27 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd)
}
sd->s_sibling = *pos;
*pos = sd;
+
+ // rb tree insert
+ new = &(parent_sd->s_dir.child_rb_root.rb_node);
+ parent = NULL;
+
+ while (*new) {
+ struct sysfs_dirent *this =
+ container_of(*new, struct sysfs_dirent, s_rb_node);
+ int result = strcmp(sd->s_name, this->s_name);
+
+ parent = *new;
+ if (result < 0)
+ new = &((*new)->rb_left);
+ else if (result > 0)
+ new = &((*new)->rb_right);
+ else
+ BUG();
+ }
+
+ rb_link_node(&sd->s_rb_node, parent, new);
+ rb_insert_color(&sd->s_rb_node, &parent_sd->s_dir.child_rb_root);
}

/**
@@ -81,6 +103,8 @@ static void sysfs_unlink_sibling(struct sysfs_dirent *sd)
break;
}
}
+
+ rb_erase(&sd->s_rb_node, &sd->s_parent->s_dir.child_rb_root);
}

/**
@@ -331,6 +355,9 @@ struct sysfs_dirent *sysfs_new_dirent(const char *name, umode_t mode, int type)
sd->s_mode = mode;
sd->s_flags = type;

+ if (type == SYSFS_DIR)
+ sd->s_dir.child_rb_root = RB_ROOT;
+
return sd;

err_out2:
@@ -630,11 +657,20 @@ void sysfs_addrm_finish(struct sysfs_addrm_cxt *acxt)
struct sysfs_dirent *sysfs_find_dirent(struct sysfs_dirent *parent_sd,
const unsigned char *name)
{
- struct sysfs_dirent *sd;
-
- for (sd = parent_sd->s_dir.children; sd; sd = sd->s_sibling)
- if (!strcmp(sd->s_name, name))
- return sd;
+ struct rb_node *node = parent_sd->s_dir.child_rb_root.rb_node;
+
+ while (node) {
+ struct sysfs_dirent *data =
+ container_of(node, struct sysfs_dirent, s_rb_node);
+ int result;
+ result = strcmp(name, data->s_name);
+ if (result < 0)
+ node = node->rb_left;
+ else if (result > 0)
+ node = node->rb_right;
+ else
+ return data;
+ }
return NULL;
}

diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h
index af4c4e7..600109c 100644
--- a/fs/sysfs/sysfs.h
+++ b/fs/sysfs/sysfs.h
@@ -9,6 +9,7 @@
*/

#include <linux/fs.h>
+#include <linux/rbtree.h>

struct sysfs_open_dirent;

@@ -17,6 +18,7 @@ struct sysfs_elem_dir {
struct kobject *kobj;
/* children list starts here and goes through sd->s_sibling */
struct sysfs_dirent *children;
+ struct rb_root child_rb_root;
};

struct sysfs_elem_symlink {
@@ -52,6 +54,7 @@ struct sysfs_dirent {
atomic_t s_active;
struct sysfs_dirent *s_parent;
struct sysfs_dirent *s_sibling;
+ struct rb_node s_rb_node;
const char *s_name;

union {
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo DeleteThis @vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

When adding/removing large numbers of entries from sysfs directories, one
hot spot is in the link and unlink operations of sysfs. When linking a
new sysfs_dirent into the tree, operation can be significantly sped up by
starting at the end of the list rather than the beginning. Unlink is
improved by using a doubly linked list.

Signed-off-by: Benjamin LaHaise <bcrl.DeleteThis@kvack.org>
diff -u b/fs/sysfs/dir.c b/fs/sysfs/dir.c
--- b/fs/sysfs/dir.c
+++ b/fs/sysfs/dir.c
@@ -43,11 +43,18 @@
static void sysfs_link_sibling(struct sysfs_dirent *sd)
{
struct sysfs_dirent *parent_sd = sd->s_parent;
- struct sysfs_dirent **pos;
+ struct sysfs_dirent **pos, *prev = NULL;
struct rb_node **new, *parent;

BUG_ON(sd->s_sibling);

+ if (parent_sd->s_dir.children_tail &&
+ parent_sd->s_dir.children_tail->s_ino < sd->s_ino) {
+ prev = parent_sd->s_dir.children_tail;
+ pos = &prev->s_sibling;
+ goto got_it;
+ }
+
/* Store directory entries in order by ino. This allows
* readdir to properly restart without having to add a
* cursor into the s_dir.children list.
@@ -55,8 +62,13 @@
for (pos = &parent_sd->s_dir.children; *pos; pos = &(*pos)->s_sibling) {
if (sd->s_ino < (*pos)->s_ino)
break;
+ prev = *pos;
}
+got_it:
+ if (prev == parent_sd->s_dir.children_tail)
+ parent_sd->s_dir.children_tail = sd;
sd->s_sibling = *pos;
+ sd->s_sibling_prev = prev;
*pos = sd;

// rb tree insert
@@ -93,17 +105,20 @@
*/
static void sysfs_unlink_sibling(struct sysfs_dirent *sd)
{
- struct sysfs_dirent **pos;
-
- for (pos = &sd->s_parent->s_dir.children; *pos;
- pos = &(*pos)->s_sibling) {
- if (*pos == sd) {
- *pos = sd->s_sibling;
- sd->s_sibling = NULL;
- break;
- }
- }
+ struct sysfs_dirent **pos, *prev = NULL;

+ prev = sd->s_sibling_prev;
+ if (prev)
+ pos = &prev->s_sibling;
+ else
+ pos = &sd->s_parent->s_dir.children;
+ if (sd == sd->s_parent->s_dir.children_tail)
+ sd->s_parent->s_dir.children_tail = prev;
+ *pos = sd->s_sibling;
+ if (sd->s_sibling)
+ sd->s_sibling->s_sibling_prev = prev;
+
+ sd->s_sibling_prev = NULL;
rb_erase(&sd->s_rb_node, &sd->s_parent->s_dir.child_rb_root);
}

diff -u b/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h
--- b/fs/sysfs/sysfs.h
+++ b/fs/sysfs/sysfs.h
@@ -17,7 +17,9 @@
struct sysfs_elem_dir {
struct kobject *kobj;
/* children list starts here and goes through sd->s_sibling */
+
struct sysfs_dirent *children;
+ struct sysfs_dirent *children_tail;
struct rb_root child_rb_root;
};

@@ -54,6 +56,7 @@
atomic_t s_active;
struct sysfs_dirent *s_parent;
struct sysfs_dirent *s_sibling;
+ struct sysfs_dirent *s_sibling_prev;
struct rb_node s_rb_node;
const char *s_name;

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo.DeleteThis@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/