1 files changed, 112 insertions, 56 deletions

diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c
index ea9120a830d8..83bb9d1f30aa 100644
--- a/fs/sysfs/dir.c
+++ b/fs/sysfs/dir.c
@@ -43,20 +43,48 @@ static DEFINE_IDA(sysfs_ino_ida);
 static void sysfs_link_sibling(struct sysfs_dirent *sd)
 {
         struct sysfs_dirent *parent_sd = sd->s_parent;
-        struct sysfs_dirent **pos;
 
-        BUG_ON(sd->s_sibling);
-
-        /* 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.
-         */
-        for (pos = &parent_sd->s_dir.children; *pos; pos = &(*pos)->s_sibling) {
-                if (sd->s_ino < (*pos)->s_ino)
-                        break;
+        struct rb_node **p;
+        struct rb_node *parent;
+
+        if (sysfs_type(sd) == SYSFS_DIR)
+                parent_sd->s_dir.subdirs++;
+
+        p = &parent_sd->s_dir.inode_tree.rb_node;
+        parent = NULL;
+        while (*p) {
+                parent = *p;
+#define node    rb_entry(parent, struct sysfs_dirent, inode_node)
+                if (sd->s_ino < node->s_ino) {
+                        p = &node->inode_node.rb_left;
+                } else if (sd->s_ino > node->s_ino) {
+                        p = &node->inode_node.rb_right;
+                } else {
+                        printk(KERN_CRIT "sysfs: inserting duplicate inode '%lx'\n",
+                               (unsigned long) sd->s_ino);
+                        BUG();
+                }
+#undef node
         }
-        sd->s_sibling = *pos;
-        *pos = sd;
+        rb_link_node(&sd->inode_node, parent, p);
+        rb_insert_color(&sd->inode_node, &parent_sd->s_dir.inode_tree);
+
+        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 {
+                        p = &node->name_node.rb_right;
+                }
+#undef node
+        }
+        rb_link_node(&sd->name_node, parent, p);
+        rb_insert_color(&sd->name_node, &parent_sd->s_dir.name_tree);
 }
 
 /**
@@ -71,16 +99,11 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd)
  */
 static void sysfs_unlink_sibling(struct sysfs_dirent *sd)
 {
-        struct sysfs_dirent **pos;
+        if (sysfs_type(sd) == SYSFS_DIR)
+                sd->s_parent->s_dir.subdirs--;
 
-        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;
-                }
-        }
+        rb_erase(&sd->inode_node, &sd->s_parent->s_dir.inode_tree);
+        rb_erase(&sd->name_node, &sd->s_parent->s_dir.name_tree);
 }
 
 /**
@@ -126,7 +149,6 @@ struct sysfs_dirent *sysfs_get_active(struct sysfs_dirent *sd)
  */
 void sysfs_put_active(struct sysfs_dirent *sd)
 {
-        struct completion *cmpl;
         int v;
 
         if (unlikely(!sd))
@@ -138,10 +160,9 @@ void sysfs_put_active(struct sysfs_dirent *sd)
                 return;
 
         /* atomic_dec_return() is a mb(), we'll always see the updated
-         * sd->s_sibling.
+         * sd->u.completion.
          */
-        cmpl = (void *)sd->s_sibling;
-        complete(cmpl);
+        complete(sd->u.completion);
 }
 
 /**
@@ -155,16 +176,16 @@ static void sysfs_deactivate(struct sysfs_dirent *sd)
         DECLARE_COMPLETION_ONSTACK(wait);
         int v;
 
-        BUG_ON(sd->s_sibling || !(sd->s_flags & SYSFS_FLAG_REMOVED));
+        BUG_ON(!(sd->s_flags & SYSFS_FLAG_REMOVED));
 
         if (!(sysfs_type(sd) & SYSFS_ACTIVE_REF))
                 return;
 
-        sd->s_sibling = (void *)&wait;
+        sd->u.completion = (void *)&wait;
 
         rwsem_acquire(&sd->dep_map, 0, 0, _RET_IP_);
         /* atomic_add_return() is a mb(), put_active() will always see
-         * the updated sd->s_sibling.
+         * the updated sd->u.completion.
          */
         v = atomic_add_return(SD_DEACTIVATED_BIAS, &sd->s_active);
 
@@ -173,8 +194,6 @@ static void sysfs_deactivate(struct sysfs_dirent *sd)
                 wait_for_completion(&wait);
         }
 
-        sd->s_sibling = NULL;
-
         lock_acquired(&sd->dep_map, _RET_IP_);
         rwsem_release(&sd->dep_map, 1, _RET_IP_);
 }
@@ -490,7 +509,7 @@ void sysfs_remove_one(struct sysfs_addrm_cxt *acxt, struct sysfs_dirent *sd)
         }
 
         sd->s_flags |= SYSFS_FLAG_REMOVED;
-        sd->s_sibling = acxt->removed;
+        sd->u.removed_list = acxt->removed;
         acxt->removed = sd;
 }
 
@@ -514,8 +533,7 @@ void sysfs_addrm_finish(struct sysfs_addrm_cxt *acxt)
         while (acxt->removed) {
                 struct sysfs_dirent *sd = acxt->removed;
 
-                acxt->removed = sd->s_sibling;
-                sd->s_sibling = NULL;
+                acxt->removed = sd->u.removed_list;
 
                 sysfs_deactivate(sd);
                 unmap_bin_file(sd);
@@ -540,15 +558,36 @@ struct sysfs_dirent *sysfs_find_dirent(struct sysfs_dirent *parent_sd,
                                        const void *ns,
                                        const unsigned char *name)
 {
-        struct sysfs_dirent *sd;
+        struct rb_node *p = parent_sd->s_dir.name_tree.rb_node;
+        struct sysfs_dirent *found = NULL;
+
+        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 {
+                        found = node;
+                        p = node->name_node.rb_left;
+                }
+#undef 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;
+        if (found && ns) {
+                while (found->s_ns && found->s_ns != ns) {
+                        p = rb_next(&found->name_node);
+                        if (!p)
+                                return NULL;
+                        found = rb_entry(p, struct sysfs_dirent, name_node);
+                        if (strcmp(name, found->s_name))
+                                return NULL;
+                }
         }
-        return NULL;
+
+        return found;
 }
 
 /**
@@ -744,21 +783,19 @@ void sysfs_remove_subdir(struct sysfs_dirent *sd)
 static void __sysfs_remove_dir(struct sysfs_dirent *dir_sd)
 {
         struct sysfs_addrm_cxt acxt;
-        struct sysfs_dirent **pos;
+        struct rb_node *pos;
 
         if (!dir_sd)
                 return;
 
         pr_debug("sysfs %s: removing dir\n", dir_sd->s_name);
         sysfs_addrm_start(&acxt, dir_sd);
-        pos = &dir_sd->s_dir.children;
-        while (*pos) {
-                struct sysfs_dirent *sd = *pos;
-
+        pos = rb_first(&dir_sd->s_dir.inode_tree);
+        while (pos) {
+                struct sysfs_dirent *sd = rb_entry(pos, struct sysfs_dirent, inode_node);
+                pos = rb_next(pos);
                 if (sysfs_type(sd) != SYSFS_DIR)
                         sysfs_remove_one(&acxt, sd);
-                else
-                        pos = &(*pos)->s_sibling;
         }
         sysfs_addrm_finish(&acxt);
 
@@ -881,12 +918,28 @@ static struct sysfs_dirent *sysfs_dir_pos(const void *ns,
                         pos = NULL;
         }
         if (!pos && (ino > 1) && (ino < INT_MAX)) {
-                pos = parent_sd->s_dir.children;
-                while (pos && (ino > pos->s_ino))
-                        pos = pos->s_sibling;
+                struct rb_node *p = parent_sd->s_dir.inode_tree.rb_node;
+                while (p) {
+#define node    rb_entry(p, struct sysfs_dirent, inode_node)
+                        if (ino < node->s_ino) {
+                                pos = node;
+                                p = node->inode_node.rb_left;
+                        } else if (ino > node->s_ino) {
+                                p = node->inode_node.rb_right;
+                        } else {
+                                pos = node;
+                                break;
+                        }
+#undef node
+                }
+        }
+        while (pos && pos->s_ns && pos->s_ns != ns) {
+                struct rb_node *p = rb_next(&pos->inode_node);
+                if (!p)
+                        pos = NULL;
+                else
+                        pos = rb_entry(p, struct sysfs_dirent, inode_node);
         }
-        while (pos && pos->s_ns && pos->s_ns != ns)
-                pos = pos->s_sibling;
         return pos;
 }
 
@@ -894,10 +947,13 @@ static struct sysfs_dirent *sysfs_dir_next_pos(const void *ns,
         struct sysfs_dirent *parent_sd, ino_t ino, struct sysfs_dirent *pos)
 {
         pos = sysfs_dir_pos(ns, parent_sd, ino, pos);
-        if (pos)
-                pos = pos->s_sibling;
-        while (pos && pos->s_ns && pos->s_ns != ns)
-                pos = pos->s_sibling;
+        if (pos) do {
+                struct rb_node *p = rb_next(&pos->inode_node);
+                if (!p)
+                        pos = NULL;
+                else
+                        pos = rb_entry(p, struct sysfs_dirent, inode_node);
+        } while (pos && pos->s_ns && pos->s_ns != ns);
         return pos;
 }