From: Arnaldo Carvalho de Melo <acme@kernel.org>
To: Ingo Molnar <mingo@kernel.org>
Cc: Clark Williams <williams@redhat.com>,
linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org,
Davidlohr Bueso <dave@stgolabs.net>,
Davidlohr Bueso <dbueso@suse.de>,
Arnaldo Carvalho de Melo <acme@redhat.com>,
Jiri Olsa <jolsa@kernel.org>, Namhyung Kim <namhyung@kernel.org>
Subject: [PATCH 12/29] perf callchain: Use cached rbtrees
Date: Sat, 26 Jan 2019 00:18:26 +0100 [thread overview]
Message-ID: <20190125231843.2895-13-acme@kernel.org> (raw)
In-Reply-To: <20190125231843.2895-1-acme@kernel.org>
From: Davidlohr Bueso <dave@stgolabs.net>
At the cost of an extra pointer, we can avoid the O(logN) cost of
finding the first element in the tree (smallest node), which is
something required for nearly every in/srcline callchain node deletion
(in/srcline__tree_delete()).
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Tested-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Namhyung Kim <namhyung@kernel.org>
Link: http://lkml.kernel.org/r/20181206191819.30182-4-dave@stgolabs.net
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
tools/perf/util/dso.c | 4 ++--
tools/perf/util/dso.h | 4 ++--
tools/perf/util/srcline.c | 43 +++++++++++++++++++++++----------------
tools/perf/util/srcline.h | 13 ++++++------
4 files changed, 36 insertions(+), 28 deletions(-)
diff --git a/tools/perf/util/dso.c b/tools/perf/util/dso.c
index 8cbbb5be4a0b..a82bbf6e24e0 100644
--- a/tools/perf/util/dso.c
+++ b/tools/perf/util/dso.c
@@ -1198,8 +1198,8 @@ struct dso *dso__new(const char *name)
dso__set_short_name(dso, dso->name, false);
dso->symbols = dso->symbol_names = RB_ROOT;
dso->data.cache = RB_ROOT;
- dso->inlined_nodes = RB_ROOT;
- dso->srclines = RB_ROOT;
+ dso->inlined_nodes = RB_ROOT_CACHED;
+ dso->srclines = RB_ROOT_CACHED;
dso->data.fd = -1;
dso->data.status = DSO_DATA_STATUS_UNKNOWN;
dso->symtab_type = DSO_BINARY_TYPE__NOT_FOUND;
diff --git a/tools/perf/util/dso.h b/tools/perf/util/dso.h
index 2de54c0b26b2..40edfb375a8b 100644
--- a/tools/perf/util/dso.h
+++ b/tools/perf/util/dso.h
@@ -143,8 +143,8 @@ struct dso {
struct rb_root *root; /* root of rbtree that rb_node is in */
struct rb_root symbols;
struct rb_root symbol_names;
- struct rb_root inlined_nodes;
- struct rb_root srclines;
+ struct rb_root_cached inlined_nodes;
+ struct rb_root_cached srclines;
struct {
u64 addr;
struct symbol *symbol;
diff --git a/tools/perf/util/srcline.c b/tools/perf/util/srcline.c
index dc86597d0cc4..00f215580b5a 100644
--- a/tools/perf/util/srcline.c
+++ b/tools/perf/util/srcline.c
@@ -594,11 +594,12 @@ struct srcline_node {
struct rb_node rb_node;
};
-void srcline__tree_insert(struct rb_root *tree, u64 addr, char *srcline)
+void srcline__tree_insert(struct rb_root_cached *tree, u64 addr, char *srcline)
{
- struct rb_node **p = &tree->rb_node;
+ struct rb_node **p = &tree->rb_root.rb_node;
struct rb_node *parent = NULL;
struct srcline_node *i, *node;
+ bool leftmost = true;
node = zalloc(sizeof(struct srcline_node));
if (!node) {
@@ -614,16 +615,18 @@ void srcline__tree_insert(struct rb_root *tree, u64 addr, char *srcline)
i = rb_entry(parent, struct srcline_node, rb_node);
if (addr < i->addr)
p = &(*p)->rb_left;
- else
+ else {
p = &(*p)->rb_right;
+ leftmost = false;
+ }
}
rb_link_node(&node->rb_node, parent, p);
- rb_insert_color(&node->rb_node, tree);
+ rb_insert_color_cached(&node->rb_node, tree, leftmost);
}
-char *srcline__tree_find(struct rb_root *tree, u64 addr)
+char *srcline__tree_find(struct rb_root_cached *tree, u64 addr)
{
- struct rb_node *n = tree->rb_node;
+ struct rb_node *n = tree->rb_root.rb_node;
while (n) {
struct srcline_node *i = rb_entry(n, struct srcline_node,
@@ -640,15 +643,15 @@ char *srcline__tree_find(struct rb_root *tree, u64 addr)
return NULL;
}
-void srcline__tree_delete(struct rb_root *tree)
+void srcline__tree_delete(struct rb_root_cached *tree)
{
struct srcline_node *pos;
- struct rb_node *next = rb_first(tree);
+ struct rb_node *next = rb_first_cached(tree);
while (next) {
pos = rb_entry(next, struct srcline_node, rb_node);
next = rb_next(&pos->rb_node);
- rb_erase(&pos->rb_node, tree);
+ rb_erase_cached(&pos->rb_node, tree);
free_srcline(pos->srcline);
zfree(&pos);
}
@@ -682,28 +685,32 @@ void inline_node__delete(struct inline_node *node)
free(node);
}
-void inlines__tree_insert(struct rb_root *tree, struct inline_node *inlines)
+void inlines__tree_insert(struct rb_root_cached *tree,
+ struct inline_node *inlines)
{
- struct rb_node **p = &tree->rb_node;
+ struct rb_node **p = &tree->rb_root.rb_node;
struct rb_node *parent = NULL;
const u64 addr = inlines->addr;
struct inline_node *i;
+ bool leftmost = true;
while (*p != NULL) {
parent = *p;
i = rb_entry(parent, struct inline_node, rb_node);
if (addr < i->addr)
p = &(*p)->rb_left;
- else
+ else {
p = &(*p)->rb_right;
+ leftmost = false;
+ }
}
rb_link_node(&inlines->rb_node, parent, p);
- rb_insert_color(&inlines->rb_node, tree);
+ rb_insert_color_cached(&inlines->rb_node, tree, leftmost);
}
-struct inline_node *inlines__tree_find(struct rb_root *tree, u64 addr)
+struct inline_node *inlines__tree_find(struct rb_root_cached *tree, u64 addr)
{
- struct rb_node *n = tree->rb_node;
+ struct rb_node *n = tree->rb_root.rb_node;
while (n) {
struct inline_node *i = rb_entry(n, struct inline_node,
@@ -720,15 +727,15 @@ struct inline_node *inlines__tree_find(struct rb_root *tree, u64 addr)
return NULL;
}
-void inlines__tree_delete(struct rb_root *tree)
+void inlines__tree_delete(struct rb_root_cached *tree)
{
struct inline_node *pos;
- struct rb_node *next = rb_first(tree);
+ struct rb_node *next = rb_first_cached(tree);
while (next) {
pos = rb_entry(next, struct inline_node, rb_node);
next = rb_next(&pos->rb_node);
- rb_erase(&pos->rb_node, tree);
+ rb_erase_cached(&pos->rb_node, tree);
inline_node__delete(pos);
}
}
diff --git a/tools/perf/util/srcline.h b/tools/perf/util/srcline.h
index 5762212dc342..b11a0aaaa676 100644
--- a/tools/perf/util/srcline.h
+++ b/tools/perf/util/srcline.h
@@ -19,11 +19,11 @@ void free_srcline(char *srcline);
char *get_srcline_split(struct dso *dso, u64 addr, unsigned *line);
/* insert the srcline into the DSO, which will take ownership */
-void srcline__tree_insert(struct rb_root *tree, u64 addr, char *srcline);
+void srcline__tree_insert(struct rb_root_cached *tree, u64 addr, char *srcline);
/* find previously inserted srcline */
-char *srcline__tree_find(struct rb_root *tree, u64 addr);
+char *srcline__tree_find(struct rb_root_cached *tree, u64 addr);
/* delete all srclines within the tree */
-void srcline__tree_delete(struct rb_root *tree);
+void srcline__tree_delete(struct rb_root_cached *tree);
#define SRCLINE_UNKNOWN ((char *) "??:0")
@@ -46,10 +46,11 @@ struct inline_node *dso__parse_addr_inlines(struct dso *dso, u64 addr,
void inline_node__delete(struct inline_node *node);
/* insert the inline node list into the DSO, which will take ownership */
-void inlines__tree_insert(struct rb_root *tree, struct inline_node *inlines);
+void inlines__tree_insert(struct rb_root_cached *tree,
+ struct inline_node *inlines);
/* find previously inserted inline node list */
-struct inline_node *inlines__tree_find(struct rb_root *tree, u64 addr);
+struct inline_node *inlines__tree_find(struct rb_root_cached *tree, u64 addr);
/* delete all nodes within the tree of inline_node s */
-void inlines__tree_delete(struct rb_root *tree);
+void inlines__tree_delete(struct rb_root_cached *tree);
#endif /* PERF_SRCLINE_H */
--
2.20.1
next prev parent reply other threads:[~2019-01-25 23:19 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-25 23:18 [GIT PULL 00/29] perf/core improvements and fixes Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 01/29] perf symbols: Move symbol_conf to separate file Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 02/29] perf annotate: Remove lots of headers from annotate.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 03/29] perf tools: Move branch structs to branch.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 04/29] perf block-range: Add missing headers Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 05/29] perf symbols: Remove include map.h from dso.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 06/29] perf symbols: Remove some unnecessary includes from symbol.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 07/29] perf namespaces: Remove namespaces.h from .h headers Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 08/29] perf comm: Remove needless headers from comm.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 09/29] perf callchain: No need to include perf.h Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 10/29] tools: Update rbtree implementation Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 11/29] perf machine: Use cached rbtrees Arnaldo Carvalho de Melo
2019-01-25 23:18 ` Arnaldo Carvalho de Melo [this message]
2019-01-25 23:18 ` [PATCH 13/29] perf util: Use cached rbtree for rblists Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 14/29] perf symbols: Use cached rbtrees Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 15/29] perf hist: " Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 16/29] perf sched: " Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 17/29] perf bpf: Fix synthesized PERF_RECORD_KSYMBOL/BPF_EVENT Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 18/29] perf script python: Add trace_context extension module to sys.modules Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 19/29] perf script python: Use PyBytes for attr in trace-event-python Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 20/29] perf script python: Remove explicit shebang from setup.py Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 21/29] perf script python: Remove explicit shebang from tests/attr.c Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 22/29] perf script python: Remove explicit shebang from Python scripts Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 23/29] perf script python: Add Python3 support to tests/attr.py Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 24/29] perf bpf: Add bpf_map() helper Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 25/29] perf bpf: Convert pid_map() to bpf_map() Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 26/29] perf augmented_raw_syscalls: Use bpf_map() Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 27/29] perf trace: Fixup etcsnoop example Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 28/29] perf bpf examples: Convert etcsnoop to use bpf_map() Arnaldo Carvalho de Melo
2019-01-25 23:18 ` [PATCH 29/29] perf augmented_syscalls: Convert to bpf_map() Arnaldo Carvalho de Melo
2019-01-26 9:52 ` [GIT PULL 00/29] perf/core improvements and fixes Ingo Molnar
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=20190125231843.2895-13-acme@kernel.org \
--to=acme@kernel.org \
--cc=acme@redhat.com \
--cc=dave@stgolabs.net \
--cc=dbueso@suse.de \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=namhyung@kernel.org \
--cc=williams@redhat.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).