lkml.org 
[lkml]   [2017]   [Jun]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 8/9] procfs: Use faster rb_first_cached()
    Date
    ... such that we can avoid the tree walks to get the
    node with the smallest key. Semantically the same,
    as the previously used rb_first(), but O(1). The
    main overhead is the extra footprint for the cached
    rb_node pointer, which should not matter for procfs.

    Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
    ---
    fs/proc/generic.c | 26 ++++++++++++++------------
    fs/proc/internal.h | 2 +-
    fs/proc/proc_net.c | 2 +-
    fs/proc/root.c | 2 +-
    4 files changed, 17 insertions(+), 15 deletions(-)

    diff --git a/fs/proc/generic.c b/fs/proc/generic.c
    index e3cda0b5968f..ab6496356dc2 100644
    --- a/fs/proc/generic.c
    +++ b/fs/proc/generic.c
    @@ -40,8 +40,8 @@ static int proc_match(unsigned int len, const char *name, struct proc_dir_entry

    static struct proc_dir_entry *pde_subdir_first(struct proc_dir_entry *dir)
    {
    - return rb_entry_safe(rb_first(&dir->subdir), struct proc_dir_entry,
    - subdir_node);
    + return rb_entry_safe(rb_first_cached(&dir->subdir),
    + struct proc_dir_entry, subdir_node);
    }

    static struct proc_dir_entry *pde_subdir_next(struct proc_dir_entry *dir)
    @@ -54,7 +54,7 @@ static struct proc_dir_entry *pde_subdir_find(struct proc_dir_entry *dir,
    const char *name,
    unsigned int len)
    {
    - struct rb_node *node = dir->subdir.rb_node;
    + struct rb_node *node = dir->subdir.rb_root.rb_node;

    while (node) {
    struct proc_dir_entry *de = rb_entry(node,
    @@ -75,8 +75,9 @@ static struct proc_dir_entry *pde_subdir_find(struct proc_dir_entry *dir,
    static bool pde_subdir_insert(struct proc_dir_entry *dir,
    struct proc_dir_entry *de)
    {
    - struct rb_root *root = &dir->subdir;
    - struct rb_node **new = &root->rb_node, *parent = NULL;
    + struct rb_root_cached *root = &dir->subdir;
    + struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;
    + bool leftmost = true;

    /* Figure out where to put new node */
    while (*new) {
    @@ -88,15 +89,16 @@ static bool pde_subdir_insert(struct proc_dir_entry *dir,
    parent = *new;
    if (result < 0)
    new = &(*new)->rb_left;
    - else if (result > 0)
    + else if (result > 0) {
    new = &(*new)->rb_right;
    - else
    + leftmost = false;
    + } else
    return false;
    }

    /* Add new node and rebalance tree. */
    rb_link_node(&de->subdir_node, parent, new);
    - rb_insert_color(&de->subdir_node, root);
    + rb_insert_color_cached(&de->subdir_node, root, leftmost);
    return true;
    }

    @@ -369,7 +371,7 @@ static struct proc_dir_entry *__proc_create(struct proc_dir_entry **parent,
    ent->namelen = qstr.len;
    ent->mode = mode;
    ent->nlink = nlink;
    - ent->subdir = RB_ROOT;
    + ent->subdir = RB_ROOT_CACHED;
    atomic_set(&ent->count, 1);
    spin_lock_init(&ent->pde_unload_lock);
    INIT_LIST_HEAD(&ent->pde_openers);
    @@ -545,7 +547,7 @@ void remove_proc_entry(const char *name, struct proc_dir_entry *parent)

    de = pde_subdir_find(parent, fn, len);
    if (de)
    - rb_erase(&de->subdir_node, &parent->subdir);
    + rb_erase_cached(&de->subdir_node, &parent->subdir);
    write_unlock(&proc_subdir_lock);
    if (!de) {
    WARN(1, "name '%s'\n", name);
    @@ -582,13 +584,13 @@ int remove_proc_subtree(const char *name, struct proc_dir_entry *parent)
    write_unlock(&proc_subdir_lock);
    return -ENOENT;
    }
    - rb_erase(&root->subdir_node, &parent->subdir);
    + rb_erase_cached(&root->subdir_node, &parent->subdir);

    de = root;
    while (1) {
    next = pde_subdir_first(de);
    if (next) {
    - rb_erase(&next->subdir_node, &de->subdir);
    + rb_erase_cached(&next->subdir_node, &de->subdir);
    de = next;
    continue;
    }
    diff --git a/fs/proc/internal.h b/fs/proc/internal.h
    index 07b16318223f..4db394edb6d9 100644
    --- a/fs/proc/internal.h
    +++ b/fs/proc/internal.h
    @@ -40,7 +40,7 @@ struct proc_dir_entry {
    const struct inode_operations *proc_iops;
    const struct file_operations *proc_fops;
    struct proc_dir_entry *parent;
    - struct rb_root subdir;
    + struct rb_root_cached subdir;
    struct rb_node subdir_node;
    void *data;
    atomic_t count; /* use count */
    diff --git a/fs/proc/proc_net.c b/fs/proc/proc_net.c
    index d72fc40241d9..a2bf369c923d 100644
    --- a/fs/proc/proc_net.c
    +++ b/fs/proc/proc_net.c
    @@ -196,7 +196,7 @@ static __net_init int proc_net_ns_init(struct net *net)
    if (!netd)
    goto out;

    - netd->subdir = RB_ROOT;
    + netd->subdir = RB_ROOT_CACHED;
    netd->data = net;
    netd->nlink = 2;
    netd->namelen = 3;
    diff --git a/fs/proc/root.c b/fs/proc/root.c
    index deecb397daa3..926fb27f4ca2 100644
    --- a/fs/proc/root.c
    +++ b/fs/proc/root.c
    @@ -210,7 +210,7 @@ struct proc_dir_entry proc_root = {
    .proc_iops = &proc_root_inode_operations,
    .proc_fops = &proc_root_operations,
    .parent = &proc_root,
    - .subdir = RB_ROOT,
    + .subdir = RB_ROOT_CACHED,
    .name = "/proc",
    };

    --
    2.12.0
    \
     
     \ /
      Last update: 2017-06-29 19:18    [W:8.436 / U:0.012 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site