From bd33d12fba60dea3b8f944478c54ac3ba18d2c4d Mon Sep 17 00:00:00 2001 From: Harry Wei Date: Sat, 16 Jul 2011 16:45:13 +0800 Subject: debugfs: Fix a comment mistake The file is fs/debugfs/inode.c but the comment says it is file.c. This patch can fix this little mistake. Signed-off-by: Harry Wei Signed-off-by: Greg Kroah-Hartman --- fs/debugfs/inode.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'fs') diff --git a/fs/debugfs/inode.c b/fs/debugfs/inode.c index e7a7a2f07324..f3a257d7a985 100644 --- a/fs/debugfs/inode.c +++ b/fs/debugfs/inode.c @@ -1,5 +1,5 @@ /* - * file.c - part of debugfs, a tiny little debug file system + * inode.c - part of debugfs, a tiny little debug file system * * Copyright (C) 2004 Greg Kroah-Hartman * Copyright (C) 2004 IBM Inc. -- cgit v1.2.3 From 7f9838fd01833ffb30177d964983076924344c9e Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Thu, 21 Jul 2011 19:59:22 -0400 Subject: sysfs: count subdirectories sysfs: count subdirectories This patch introduces a subdirectory counter for each sysfs directory. Without the patch, sysfs_refresh_inode would walk all entries of the directory to calculate the number of subdirectories. This patch improves time of "ls -la /sys/block" when there are 10000 block devices from 9 seconds to 0.19 seconds. Signed-off-by: Mikulas Patocka Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 6 ++++++ fs/sysfs/inode.c | 14 +------------- fs/sysfs/sysfs.h | 2 ++ 3 files changed, 9 insertions(+), 13 deletions(-) (limited to 'fs') diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index ea9120a830d8..7d240e6b7176 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -47,6 +47,9 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) BUG_ON(sd->s_sibling); + if (sysfs_type(sd) == SYSFS_DIR) + parent_sd->s_dir.subdirs++; + /* 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. @@ -73,6 +76,9 @@ 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) { diff --git a/fs/sysfs/inode.c b/fs/sysfs/inode.c index e3f091a81c72..1ee18c81df78 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 845ab3ad229d..6348e2c753f6 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -19,6 +19,8 @@ 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 sysfs_elem_symlink { -- cgit v1.2.3 From 4f72c0cab40536a0be501d85ea4918467ab82ad5 Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Mon, 25 Jul 2011 17:55:57 -0400 Subject: sysfs: use rb-tree for name lookups sysfs: use rb-tree for name lookups Use red-black tree for name lookups. Signed-off-by: Mikulas Patocka Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++------- fs/sysfs/sysfs.h | 5 +++++ 2 files changed, 55 insertions(+), 7 deletions(-) (limited to 'fs') diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index 7d240e6b7176..3e937da224d4 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -45,6 +45,9 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) 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,23 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) } 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 { + 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); } /** @@ -87,6 +107,8 @@ static void sysfs_unlink_sibling(struct sysfs_dirent *sd) break; } } + + rb_erase(&sd->name_node, &sd->s_parent->s_dir.name_tree); } /** @@ -546,15 +568,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; } /** diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h index 6348e2c753f6..fe1a9e8650bf 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -11,6 +11,7 @@ #include #include #include +#include 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; -- cgit v1.2.3 From 58f2a4c7932d8bec866d0394f806004146cde827 Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Thu, 21 Jul 2011 20:01:12 -0400 Subject: sysfs: remove s_sibling hacks sysfs: remove s_sibling hacks s_sibling was used for three different purposes: 1) as a linked list of entries in the directory 2) as a linked list of entries to be deleted 3) as a pointer to "struct completion" This patch removes the hack and introduces new union u which holds pointers for cases 2) and 3). This change is needed for the following patch that removes s_sibling at all and replaces it with a rb tree. Signed-off-by: Mikulas Patocka Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 19 +++++++------------ fs/sysfs/sysfs.h | 5 +++++ 2 files changed, 12 insertions(+), 12 deletions(-) (limited to 'fs') diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index 3e937da224d4..a4846979d4e8 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -154,7 +154,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)) @@ -166,10 +165,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); } /** @@ -183,16 +181,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); @@ -201,8 +199,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_); } @@ -518,7 +514,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; } @@ -542,8 +538,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); diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h index fe1a9e8650bf..3c261681713b 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -66,6 +66,11 @@ struct sysfs_dirent { 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; -- cgit v1.2.3 From a406f75840e15afbabd98cb64ae36b51424a8033 Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Mon, 25 Jul 2011 17:57:03 -0400 Subject: sysfs: use rb-tree for inode number lookup sysfs: use rb-tree for inode number lookup This patch makes sysfs use red-black tree for inode number lookup. Together with a previous patch to use red-black tree for name lookup, this patch makes all sysfs lookups to have O(log n) complexity. Signed-off-by: Mikulas Patocka Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 89 +++++++++++++++++++++++++++++++------------------------- fs/sysfs/sysfs.h | 5 ++-- 2 files changed, 52 insertions(+), 42 deletions(-) (limited to 'fs') diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index a4846979d4e8..c3646d93a032 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -43,26 +43,30 @@ 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; struct rb_node **p; struct rb_node *parent; - BUG_ON(sd->s_sibling); - if (sysfs_type(sd) == SYSFS_DIR) parent_sd->s_dir.subdirs++; - /* 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; + 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", 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; @@ -94,20 +98,10 @@ 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); } @@ -788,21 +782,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); @@ -925,12 +917,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; } @@ -938,10 +946,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; } diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h index 3c261681713b..ce29e28b766d 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -18,11 +18,10 @@ 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; }; @@ -61,9 +60,9 @@ 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 { -- cgit v1.2.3 From c4253cb0748cd50060d04d838c38b07f1ad0e6e5 Mon Sep 17 00:00:00 2001 From: Heiko Carstens Date: Thu, 22 Sep 2011 19:34:33 +0200 Subject: sysfs: add unsigned long cast to prevent compile warning "sysfs: use rb-tree for inode number lookup" added a new printk which causes a new compile warning on s390 (and few other architectures): fs/sysfs/dir.c: In function 'sysfs_link_sibling': fs/sysfs/dir.c:63:4: warning: format '%lx' expects argument of type 'long unsigned int', but argument 2 has type 'ino_t' [-Wform Add an explicit unsigned long cast since ino_t is an unsigned long on most architectures. Cc: Mikulas Patocka Signed-off-by: Heiko Carstens Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'fs') diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index c3646d93a032..83bb9d1f30aa 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -60,7 +60,8 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) } else if (sd->s_ino > node->s_ino) { p = &node->inode_node.rb_right; } else { - printk(KERN_CRIT "sysfs: inserting duplicate inode '%lx'\n", sd->s_ino); + printk(KERN_CRIT "sysfs: inserting duplicate inode '%lx'\n", + (unsigned long) sd->s_ino); BUG(); } #undef node -- cgit v1.2.3