summaryrefslogtreecommitdiffstats
path: root/fs/sysfs
diff options
context:
space:
mode:
Diffstat (limited to 'fs/sysfs')
-rw-r--r--fs/sysfs/dir.c168
-rw-r--r--fs/sysfs/inode.c14
-rw-r--r--fs/sysfs/sysfs.h17
3 files changed, 127 insertions, 72 deletions
diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c
index 26f370a9b5c..0344ee70a47 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_);
}
@@ -497,7 +516,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;
}
@@ -521,8 +540,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);
@@ -547,7 +565,8 @@ 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;
if (!!sysfs_ns_type(parent_sd) != !!ns) {
WARN(1, KERN_WARNING "sysfs: ns %s in '%s' for '%s'\n",
@@ -556,13 +575,33 @@ struct sysfs_dirent *sysfs_find_dirent(struct sysfs_dirent *parent_sd,
return NULL;
}
- for (sd = parent_sd->s_dir.children; sd; sd = sd->s_sibling) {
- if (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 {
+ found = node;
+ p = node->name_node.rb_left;
+ }
+#undef node
}
- return NULL;
+
+ 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 found;
}
/**
@@ -758,21 +797,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);
@@ -895,12 +932,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 != ns)
- pos = pos->s_sibling;
return pos;
}
@@ -908,10 +961,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 != 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;
}
diff --git a/fs/sysfs/inode.c b/fs/sysfs/inode.c
index 527f0cca66e..e23f28894a3 100644
--- a/fs/sysfs/inode.c
+++ b/fs/sysfs/inode.c
@@ -202,18 +202,6 @@ static inline void set_inode_attr(struct inode * inode, struct iattr * iattr)
inode->i_ctime = iattr->ia_ctime;
}
-static int sysfs_count_nlink(struct sysfs_dirent *sd)
-{
- struct sysfs_dirent *child;
- int nr = 0;
-
- for (child = sd->s_dir.children; child; child = child->s_sibling)
- if (sysfs_type(child) == SYSFS_DIR)
- nr++;
-
- return nr + 2;
-}
-
static void sysfs_refresh_inode(struct sysfs_dirent *sd, struct inode *inode)
{
struct sysfs_inode_attrs *iattrs = sd->s_iattr;
@@ -230,7 +218,7 @@ static void sysfs_refresh_inode(struct sysfs_dirent *sd, struct inode *inode)
}
if (sysfs_type(sd) == SYSFS_DIR)
- inode->i_nlink = sysfs_count_nlink(sd);
+ inode->i_nlink = sd->s_dir.subdirs + 2;
}
int sysfs_getattr(struct vfsmount *mnt, struct dentry *dentry, struct kstat *stat)
diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h
index 845ab3ad229..ce29e28b766 100644
--- a/fs/sysfs/sysfs.h
+++ b/fs/sysfs/sysfs.h
@@ -11,14 +11,18 @@
#include <linux/lockdep.h>
#include <linux/kobject_ns.h>
#include <linux/fs.h>
+#include <linux/rbtree.h>
struct sysfs_open_dirent;
/* type-specific structures for sysfs_dirent->s_* union members */
struct sysfs_elem_dir {
struct kobject *kobj;
- /* children list starts here and goes through sd->s_sibling */
- struct sysfs_dirent *children;
+
+ unsigned long subdirs;
+
+ struct rb_root inode_tree;
+ struct rb_root name_tree;
};
struct sysfs_elem_symlink {
@@ -56,9 +60,16 @@ struct sysfs_dirent {
struct lockdep_map dep_map;
#endif
struct sysfs_dirent *s_parent;
- struct sysfs_dirent *s_sibling;
const char *s_name;
+ struct rb_node inode_node;
+ struct rb_node name_node;
+
+ union {
+ struct completion *completion;
+ struct sysfs_dirent *removed_list;
+ } u;
+
const void *s_ns; /* namespace tag */
union {
struct sysfs_elem_dir s_dir;
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-12-24 16:49:24 +0000