From: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
To: linux-kernel@vger.kernel.org, Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Namhyung Kim <namhyung@kernel.org>,
Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>, Jiri Olsa <jolsa@redhat.com>
Subject: [PATCH 2/2] perf map: optimize maps__fixup_overlappings()
Date: Tue, 07 Aug 2018 12:09:05 +0300 [thread overview]
Message-ID: <153363294565.396323.4605638589903548668.stgit@buzz> (raw)
In-Reply-To: <153363294102.396323.6277944760215058174.stgit@buzz>
This function splits and removes overlapping areas.
Maps in tree are ordered by start address thus we could find
first overlap and stop if next map does not overlap.
Signed-off-by: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
---
tools/perf/util/map.c | 21 ++++++++++++++++++---
1 file changed, 18 insertions(+), 3 deletions(-)
diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index 89ac5b5dc218..9b3f4d244ad4 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -675,20 +675,35 @@ static void __map_groups__insert(struct map_groups *mg, struct map *map)
static int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
{
struct rb_root *root;
- struct rb_node *next;
+ struct rb_node *next, *first;
int err = 0;
down_write(&maps->lock);
root = &maps->entries;
- next = rb_first(root);
+ /* find first where end > map->start, same as find_vma() */
+ next = root->rb_node;
+ first = NULL;
+ while (next) {
+ struct map *pos = rb_entry(next, struct map, rb_node);
+
+ if (pos->end > map->start) {
+ first = next;
+ if (pos->start <= map->start)
+ break;
+ next = next->rb_left;
+ } else
+ next = next->rb_right;
+ }
+
+ next = first;
while (next) {
struct map *pos = rb_entry(next, struct map, rb_node);
next = rb_next(&pos->rb_node);
if (!map__overlap(pos, map))
- continue;
+ break;
if (verbose >= 2) {
next prev parent reply other threads:[~2018-08-07 9:09 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-07 9:09 [PATCH 1/2] perf map: synthesize maps only for thread group leader Konstantin Khlebnikov
2018-08-07 9:09 ` Konstantin Khlebnikov [this message]
2018-08-07 12:55 ` [PATCH 2/2] perf map: optimize maps__fixup_overlappings() Jiri Olsa
2018-08-07 13:15 ` Arnaldo Carvalho de Melo
2018-08-07 14:24 ` [PATCH v2] " Konstantin Khlebnikov
2018-08-07 20:02 ` Arnaldo Carvalho de Melo
2018-08-07 23:03 ` Jiri Olsa
2018-08-08 12:40 ` Arnaldo Carvalho de Melo
2018-08-18 11:42 ` [tip:perf/urgent] perf map: Optimize maps__fixup_overlappings() tip-bot for Konstantin Khlebnikov
2018-08-07 12:43 ` [PATCH 1/2] perf map: synthesize maps only for thread group leader Jiri Olsa
2018-08-07 13:15 ` Arnaldo Carvalho de Melo
2018-08-18 11:41 ` [tip:perf/urgent] perf map: Synthesize " tip-bot for Konstantin Khlebnikov
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=153363294565.396323.4605638589903548668.stgit@buzz \
--to=khlebnikov@yandex-team.ru \
--cc=acme@kernel.org \
--cc=alexander.shishkin@linux.intel.com \
--cc=jolsa@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@redhat.com \
--cc=namhyung@kernel.org \
--cc=peterz@infradead.org \
/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).