From: Davidlohr Bueso <dave@stgolabs.net>
To: akpm@linux-foundation.org
Cc: dave@stgolabs.net, linux-kernel@vger.kernel.org,
mcgrof@kernel.org, broonie@kernel.org,
alex.williamson@redhat.com, keescook@chromium.org,
yzaikin@google.com, linux-fsdevel@vger.kernel.org,
Davidlohr Bueso <dbueso@suse.de>
Subject: [PATCH 2/5] proc/sysctl: optimize proc_sys_readdir
Date: Fri, 7 Feb 2020 10:03:02 -0800 [thread overview]
Message-ID: <20200207180305.11092-3-dave@stgolabs.net> (raw)
In-Reply-To: <20200207180305.11092-1-dave@stgolabs.net>
This patch coverts struct ctl_dir to use an llrbtree
instead of a regular rbtree such that computing nodes for
potential usable entries becomes a branchless O(1) operation,
therefore optimizing first_usable_entry(). The cost are
mainly three additional pointers: one for the root and two
for each struct ctl_node next/prev nodes, enlarging it from
32 to 48 bytes on x86-64.
Cc: mcgrof@kernel.org
Cc: keescook@chromium.org
Cc: yzaikin@google.com
Cc: linux-fsdevel@vger.kernel.org
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
fs/proc/proc_sysctl.c | 37 +++++++++++++++++++------------------
include/linux/sysctl.h | 6 +++---
2 files changed, 22 insertions(+), 21 deletions(-)
diff --git a/fs/proc/proc_sysctl.c b/fs/proc/proc_sysctl.c
index d80989b6c344..5a1b3b8be16b 100644
--- a/fs/proc/proc_sysctl.c
+++ b/fs/proc/proc_sysctl.c
@@ -111,15 +111,14 @@ static struct ctl_table *find_entry(struct ctl_table_header **phead,
{
struct ctl_table_header *head;
struct ctl_table *entry;
- struct rb_node *node = dir->root.rb_node;
+ struct rb_node *node = dir->root.rb_root.rb_node;
- while (node)
- {
+ while (node) {
struct ctl_node *ctl_node;
const char *procname;
int cmp;
- ctl_node = rb_entry(node, struct ctl_node, node);
+ ctl_node = llrb_entry(node, struct ctl_node, node);
head = ctl_node->header;
entry = &head->ctl_table[ctl_node - head->node];
procname = entry->procname;
@@ -139,9 +138,10 @@ static struct ctl_table *find_entry(struct ctl_table_header **phead,
static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
{
- struct rb_node *node = &head->node[entry - head->ctl_table].node;
- struct rb_node **p = &head->parent->root.rb_node;
+ struct rb_node *node = &head->node[entry - head->ctl_table].node.rb_node;
+ struct rb_node **p = &head->parent->root.rb_root.rb_node;
struct rb_node *parent = NULL;
+ struct llrb_node *prev = NULL;
const char *name = entry->procname;
int namelen = strlen(name);
@@ -153,7 +153,7 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
int cmp;
parent = *p;
- parent_node = rb_entry(parent, struct ctl_node, node);
+ parent_node = llrb_entry(parent, struct ctl_node, node);
parent_head = parent_node->header;
parent_entry = &parent_head->ctl_table[parent_node - parent_head->node];
parent_name = parent_entry->procname;
@@ -161,9 +161,10 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
cmp = namecmp(name, namelen, parent_name, strlen(parent_name));
if (cmp < 0)
p = &(*p)->rb_left;
- else if (cmp > 0)
+ else if (cmp > 0) {
+ prev = llrb_from_rb(parent);
p = &(*p)->rb_right;
- else {
+ } else {
pr_err("sysctl duplicate entry: ");
sysctl_print_dir(head->parent);
pr_cont("/%s\n", entry->procname);
@@ -172,15 +173,15 @@ static int insert_entry(struct ctl_table_header *head, struct ctl_table *entry)
}
rb_link_node(node, parent, p);
- rb_insert_color(node, &head->parent->root);
+ llrb_insert(&head->parent->root, llrb_from_rb(node), prev);
return 0;
}
static void erase_entry(struct ctl_table_header *head, struct ctl_table *entry)
{
- struct rb_node *node = &head->node[entry - head->ctl_table].node;
+ struct llrb_node *node = &head->node[entry - head->ctl_table].node;
- rb_erase(node, &head->parent->root);
+ llrb_erase(node, &head->parent->root);
}
static void init_header(struct ctl_table_header *head,
@@ -223,7 +224,7 @@ static int insert_header(struct ctl_dir *dir, struct ctl_table_header *header)
/* Am I creating a permanently empty directory? */
if (header->ctl_table == sysctl_mount_point) {
- if (!RB_EMPTY_ROOT(&dir->root))
+ if (!RB_EMPTY_ROOT(&dir->root.rb_root))
return -EINVAL;
set_empty_dir(dir);
}
@@ -381,11 +382,11 @@ static struct ctl_table *lookup_entry(struct ctl_table_header **phead,
return entry;
}
-static struct ctl_node *first_usable_entry(struct rb_node *node)
+static struct ctl_node *first_usable_entry(struct llrb_node *node)
{
struct ctl_node *ctl_node;
- for (;node; node = rb_next(node)) {
+ for (; node; node = llrb_next(node)) {
ctl_node = rb_entry(node, struct ctl_node, node);
if (use_table(ctl_node->header))
return ctl_node;
@@ -401,7 +402,7 @@ static void first_entry(struct ctl_dir *dir,
struct ctl_node *ctl_node;
spin_lock(&sysctl_lock);
- ctl_node = first_usable_entry(rb_first(&dir->root));
+ ctl_node = first_usable_entry(llrb_first(&dir->root));
spin_unlock(&sysctl_lock);
if (ctl_node) {
head = ctl_node->header;
@@ -420,7 +421,7 @@ static void next_entry(struct ctl_table_header **phead, struct ctl_table **pentr
spin_lock(&sysctl_lock);
unuse_table(head);
- ctl_node = first_usable_entry(rb_next(&ctl_node->node));
+ ctl_node = first_usable_entry(llrb_next(&ctl_node->node));
spin_unlock(&sysctl_lock);
head = NULL;
if (ctl_node) {
@@ -1711,7 +1712,7 @@ void setup_sysctl_set(struct ctl_table_set *set,
void retire_sysctl_set(struct ctl_table_set *set)
{
- WARN_ON(!RB_EMPTY_ROOT(&set->dir.root));
+ WARN_ON(!RB_EMPTY_ROOT(&set->dir.root.rb_root));
}
int __init proc_sys_init(void)
diff --git a/include/linux/sysctl.h b/include/linux/sysctl.h
index 02fa84493f23..afb35fa61b91 100644
--- a/include/linux/sysctl.h
+++ b/include/linux/sysctl.h
@@ -25,7 +25,7 @@
#include <linux/list.h>
#include <linux/rcupdate.h>
#include <linux/wait.h>
-#include <linux/rbtree.h>
+#include <linux/ll_rbtree.h>
#include <linux/uidgid.h>
#include <uapi/linux/sysctl.h>
@@ -133,7 +133,7 @@ struct ctl_table {
} __randomize_layout;
struct ctl_node {
- struct rb_node node;
+ struct llrb_node node;
struct ctl_table_header *header;
};
@@ -161,7 +161,7 @@ struct ctl_table_header {
struct ctl_dir {
/* Header must be at the start of ctl_dir */
struct ctl_table_header header;
- struct rb_root root;
+ struct llrb_root root;
};
struct ctl_table_set {
--
2.16.4
next prev parent reply other threads:[~2020-02-07 18:14 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-02-07 18:03 [PATCH -next 0/5] rbtree: optimize frequent tree walks Davidlohr Bueso
2020-02-07 18:03 ` [PATCH 1/5] lib/rbtree: introduce linked-list rbtree interface Davidlohr Bueso
2020-02-10 20:07 ` Luis Chamberlain
2020-02-10 21:28 ` Davidlohr Bueso
2020-02-10 21:44 ` Luis Chamberlain
2020-02-07 18:03 ` Davidlohr Bueso [this message]
2020-02-10 20:08 ` [PATCH 2/5] proc/sysctl: optimize proc_sys_readdir Luis Chamberlain
2020-02-07 18:03 ` [PATCH 3/5] regmap: optimize sync() and drop() regcache callbacks Davidlohr Bueso
2020-02-10 13:11 ` Mark Brown
2020-02-07 18:03 ` [PATCH 4/5] vfio/type1: optimize dma_list tree iterations Davidlohr Bueso
2020-02-07 18:03 ` [PATCH 5/5] uprobes: optimize build_probe_list() Davidlohr Bueso
2020-02-10 1:46 ` [PATCH -next 0/5] rbtree: optimize frequent tree walks Andrew Morton
2020-02-10 15:56 ` Davidlohr Bueso
2020-02-10 22:35 ` Andrew Morton
2020-02-13 15:50 ` Davidlohr Bueso
2020-02-11 11:20 ` Mark Brown
2020-02-13 15:55 ` Davidlohr Bueso
2020-02-13 16:56 ` Mark Brown
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200207180305.11092-3-dave@stgolabs.net \
--to=dave@stgolabs.net \
--cc=akpm@linux-foundation.org \
--cc=alex.williamson@redhat.com \
--cc=broonie@kernel.org \
--cc=dbueso@suse.de \
--cc=keescook@chromium.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mcgrof@kernel.org \
--cc=yzaikin@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).