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,
Konstantin Khlebnikov <khlebnikov@yandex-team.ru>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Namhyung Kim <namhyung@kernel.org>,
Peter Zijlstra <peterz@infradead.org>,
Arnaldo Carvalho de Melo <acme@redhat.com>
Subject: [PATCH 44/44] perf map: Optimize maps__fixup_overlappings()
Date: Thu, 9 Aug 2018 11:58:22 -0300 [thread overview]
Message-ID: <20180809145822.21391-45-acme@kernel.org> (raw)
In-Reply-To: <20180809145822.21391-1-acme@kernel.org>
From: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
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>
Acked-by: Jiri Olsa <jolsa@kernel.org>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/153365189407.435244.7234821822450484712.stgit@buzz
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
tools/perf/util/map.c | 44 ++++++++++++++++++++++++++------------------
tools/perf/util/map.h | 1 -
2 files changed, 26 insertions(+), 19 deletions(-)
diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index 89ac5b5dc218..36d0763311ef 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -381,20 +381,6 @@ struct map *map__clone(struct map *from)
return map;
}
-int map__overlap(struct map *l, struct map *r)
-{
- if (l->start > r->start) {
- struct map *t = l;
- l = r;
- r = t;
- }
-
- if (l->end > r->start)
- return 1;
-
- return 0;
-}
-
size_t map__fprintf(struct map *map, FILE *fp)
{
return fprintf(fp, " %" PRIx64 "-%" PRIx64 " %" PRIx64 " %s\n",
@@ -675,20 +661,42 @@ 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 map where end > map->start.
+ * Same as find_vma() in kernel.
+ */
+ 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;
+ /*
+ * Stop if current map starts after map->end.
+ * Maps are ordered by start: next will not overlap for sure.
+ */
+ if (pos->start >= map->end)
+ break;
if (verbose >= 2) {
diff --git a/tools/perf/util/map.h b/tools/perf/util/map.h
index 4cb90f242bed..e0f327b51e66 100644
--- a/tools/perf/util/map.h
+++ b/tools/perf/util/map.h
@@ -166,7 +166,6 @@ static inline void __map__zput(struct map **map)
#define map__zput(map) __map__zput(&map)
-int map__overlap(struct map *l, struct map *r);
size_t map__fprintf(struct map *map, FILE *fp);
size_t map__fprintf_dsoname(struct map *map, FILE *fp);
char *map__srcline(struct map *map, u64 addr, struct symbol *sym);
--
2.14.4
next prev parent reply other threads:[~2018-08-09 15:02 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-09 14:57 [GIT PULL 00/44] perf/core improvements and fixes Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 01/44] perf trace: Associate vfs_getname()'ed pathname with fd returned from 'openat' Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 02/44] perf trace: Use beautifiers on syscalls:sys_enter_ handlers Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 03/44] perf trace: Rename some syscall_tp methods to raw_syscall Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 04/44] perf trace: Allow setting up a syscall_tp struct without a format_field Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 05/44] perf trace: Setup struct syscall_tp for syscalls:sys_{enter,exit}_NAME events Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 06/44] perf trace: Use perf_evsel__sc_tp_{uint,ptr} for "id"/"args" handling syscalls:* events Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 07/44] perf auxtrace: Support for perf report -D for s390 Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 08/44] perf report: Add raw report support for s390 auxiliary trace Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 09/44] perf report: Add GUI " Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 10/44] perf vendor events arm64: Enable JSON events for eMAG Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 11/44] perf tools: Drop unneeded bitmap_zero() calls Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 12/44] perf bpf: Add 'syscall_enter' probe helper for syscall enter tracepoints Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 13/44] perf annotate: Make symbol__annotate_fprintf2() local Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 14/44] perf annotate: Make annotation_line__max_percent static Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 15/44] perf annotate: Get rid of annotation__scnprintf_samples_period() Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 16/44] perf annotate: Rename struct annotation_line::samples* to data* Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 17/44] perf annotate: Rename local sample variables to data Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 18/44] perf annotate: Rename hist to sym_hist in annotation__calc_percent Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 19/44] perf annotate: Loop group events directly in annotation__calc_percent() Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 20/44] perf annotate: Switch struct annotation_data::percent to array Arnaldo Carvalho de Melo
2018-08-09 14:57 ` [PATCH 21/44] perf annotate: Add PERCENT_HITS_GLOBAL percent value Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 22/44] perf annotate: Add PERCENT_PERIOD_LOCAL " Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 23/44] perf annotate: Add PERCENT_PERIOD_GLOBAL " Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 24/44] perf annotate: Add percent_type to struct annotation_options Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 25/44] perf annotate: Pass struct annotation_options to symbol__calc_lines() Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 26/44] perf annotate: Pass 'struct annotation_options' to map_symbol__annotation_dump() Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 27/44] perf annotate: Pass browser percent_type in annotate_browser__calc_percent() Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 28/44] perf annotate: Add support to toggle percent type Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 29/44] perf annotate: Make local period the default " Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 30/44] perf annotate: Display percent type in stdio output Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 31/44] perf annotate: Add --percent-type option Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 32/44] perf report: " Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 33/44] perf bpf: Add struct bpf_map struct Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 34/44] perf bpf: Add bpf/stdio.h wrapper to bpf_perf_event_output function Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 35/44] perf bpf: Make bpf__for_each_stdout_map() generic Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 36/44] perf bpf: Generalize bpf__setup_stdout() Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 37/44] perf bpf: Add bpf__setup_output_event() strerror() counterpart Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 38/44] perf bpf: Add wrappers to BPF_FUNC_probe_read(_str) functions Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 39/44] perf trace: Handle "bpf-output" events associated with "__augmented_syscalls__" BPF map Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 40/44] perf bpf: Make bpf__setup_output_event() return the bpf-output event Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 41/44] perf trace: Setup the augmented syscalls bpf-output event fields Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 42/44] perf trace: Wire up the augmented syscalls with the syscalls:sys_enter_FOO beautifier Arnaldo Carvalho de Melo
2018-08-09 14:58 ` [PATCH 43/44] perf map: Synthesize maps only for thread group leader Arnaldo Carvalho de Melo
2018-08-09 14:58 ` Arnaldo Carvalho de Melo [this message]
2018-08-09 15:27 ` [GIT PULL 00/44] perf/core improvements and fixes Kim Phillips
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=20180809145822.21391-45-acme@kernel.org \
--to=acme@kernel.org \
--cc=acme@redhat.com \
--cc=alexander.shishkin@linux.intel.com \
--cc=khlebnikov@yandex-team.ru \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-perf-users@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=namhyung@kernel.org \
--cc=peterz@infradead.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).