[PATCH 1/2] perf map: synthesize maps only for thread group leader

[PATCH 1/2] perf map: synthesize maps only for thread group leader

[Konstantin Khlebnikov]

Threads share map_groups, all map events are merged into it.

Thus we could send mmaps only for thread group leader.
Otherwise it took ages to attach and record something from
processes with many vmas and threads.

Thread group leader could be already dead,
but it seems perf cannot handle this case anyway.

Testing dummy:

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <pthread.h>
#include <unistd.h>

void *thread(void *arg) {
        pause();
}

int main(int argc, char **argv) {
        int threads = 10000;
        int vmas = 50000;
        pthread_t th;
        for (int i = 0; i < threads; i++)
                pthread_create(&th, NULL, thread, NULL);
        for (int i = 0; i < vmas; i++)
                mmap(NULL, 4096, (i & 1) ? PROT_READ : PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
        sleep(60);
        return 0;
}

Signed-off-by: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
---
 tools/perf/util/event.c |   13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/event.c b/tools/perf/util/event.c
index 0c8ecf0c78a4..0cd42150f712 100644
--- a/tools/perf/util/event.c
+++ b/tools/perf/util/event.c
@@ -541,10 +541,17 @@ static int __event__synthesize_thread(union perf_event *comm_event,
 						      tgid, process, machine) < 0)
 			return -1;
 
+		/*
+		 * send mmap only for thread group leader
+		 * see thread__init_map_groups
+		 */
+		if (pid == tgid &&
+		    perf_event__synthesize_mmap_events(tool, mmap_event, pid, tgid,
+						       process, machine, mmap_data,
+						       proc_map_timeout))
+			return -1;
 
-		return perf_event__synthesize_mmap_events(tool, mmap_event, pid, tgid,
-							  process, machine, mmap_data,
-							  proc_map_timeout);
+		return 0;
 	}
 
 	if (machine__is_default_guest(machine))

[PATCH 2/2] perf map: optimize maps__fixup_overlappings()

[Konstantin Khlebnikov]

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) {
 

Re: [PATCH 2/2] perf map: optimize maps__fixup_overlappings()

[Jiri Olsa]

On Tue, Aug 07, 2018 at 12:09:05PM +0300, Konstantin Khlebnikov wrote:
> 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;

please use in here the call to map__overlap as in the
while loop below.. we could change map__overlap to above
(yours) overlap check, seems more straight

> +			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;

please put in ehre the comment from changelog,
that we could stop searching in here

thanks,
jirka

>  
>  		if (verbose >= 2) {
>  
> 

Re: [PATCH 2/2] perf map: optimize maps__fixup_overlappings()

[Arnaldo Carvalho de Melo]

Em Tue, Aug 07, 2018 at 02:55:28PM +0200, Jiri Olsa escreveu:
> On Tue, Aug 07, 2018 at 12:09:05PM +0300, Konstantin Khlebnikov wrote:
> > 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.

please address Jiri's suggestions and send a v2 just for this one,

- Arnaldo

[PATCH v2] perf map: optimize maps__fixup_overlappings()

[Konstantin Khlebnikov]

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>

---

v2:
* add comments
* replace map__overlap with minimal check
* remove remove map__overlap, that was the only user
---
 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);

Re: [PATCH v2] perf map: optimize maps__fixup_overlappings()

[Arnaldo Carvalho de Melo]

Em Tue, Aug 07, 2018 at 05:24:54PM +0300, Konstantin Khlebnikov escreveu:
> 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>

Jiri, I'm applying this one with your Acked-by, ok?

- Arnaldo
 
> ---
> 
> v2:
> * add comments
> * replace map__overlap with minimal check
> * remove remove map__overlap, that was the only user
> ---
>  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);

Re: [PATCH v2] perf map: optimize maps__fixup_overlappings()

[Jiri Olsa]

On Tue, Aug 07, 2018 at 05:02:37PM -0300, Arnaldo Carvalho de Melo wrote:
> Em Tue, Aug 07, 2018 at 05:24:54PM +0300, Konstantin Khlebnikov escreveu:
> > 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>
> 
> Jiri, I'm applying this one with your Acked-by, ok?

yep, sry.. overlooked this

Acked-by: Jiri Olsa <jolsa@kernel.org>

thanks,
jirka

Re: [PATCH v2] perf map: optimize maps__fixup_overlappings()

[Arnaldo Carvalho de Melo]

Em Wed, Aug 08, 2018 at 01:03:01AM +0200, Jiri Olsa escreveu:
> On Tue, Aug 07, 2018 at 05:02:37PM -0300, Arnaldo Carvalho de Melo wrote:
> > Em Tue, Aug 07, 2018 at 05:24:54PM +0300, Konstantin Khlebnikov escreveu:
> > > This function splits and removes overlapping areas.

> > > Maps in tree are ordered by start address thus we could find

> > > 
> > > Signed-off-by: Konstantin Khlebnikov <khlebnikov@yandex-team.ru>

> > Jiri, I'm applying this one with your Acked-by, ok?

> yep, sry.. overlooked this

> Acked-by: Jiri Olsa <jolsa@kernel.org>

Thanks!

- Arnaldo

[tip:perf/urgent] perf map: Optimize maps__fixup_overlappings()

[tip-bot for Konstantin Khlebnikov]

Commit-ID:  6a9405b56c274024564f9014bba97b92c91b34d6
Gitweb:     https://git.kernel.org/tip/6a9405b56c274024564f9014bba97b92c91b34d6
Author:     Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
AuthorDate: Tue, 7 Aug 2018 17:24:54 +0300
Committer:  Arnaldo Carvalho de Melo <acme@redhat.com>
CommitDate: Wed, 8 Aug 2018 15:56:00 -0300

perf map: Optimize maps__fixup_overlappings()

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);

Re: [PATCH 1/2] perf map: synthesize maps only for thread group leader

[Jiri Olsa]

On Tue, Aug 07, 2018 at 12:09:01PM +0300, Konstantin Khlebnikov wrote:
> Threads share map_groups, all map events are merged into it.
> 
> Thus we could send mmaps only for thread group leader.
> Otherwise it took ages to attach and record something from
> processes with many vmas and threads.
> 
> Thread group leader could be already dead,
> but it seems perf cannot handle this case anyway.

nice, could mention in the changelog that we actualy
synthesize the group leader (if we found one) for the
thread even if it's not present in the thread_map,
so the process maps are always in data

Acked-by: Jiri Olsa <jolsa@kernel.org>

thanks,
jirka

Re: [PATCH 1/2] perf map: synthesize maps only for thread group leader

[Arnaldo Carvalho de Melo]

Em Tue, Aug 07, 2018 at 02:43:34PM +0200, Jiri Olsa escreveu:
> On Tue, Aug 07, 2018 at 12:09:01PM +0300, Konstantin Khlebnikov wrote:
> > Threads share map_groups, all map events are merged into it.
> > 
> > Thus we could send mmaps only for thread group leader.
> > Otherwise it took ages to attach and record something from
> > processes with many vmas and threads.
> > 
> > Thread group leader could be already dead,
> > but it seems perf cannot handle this case anyway.
> 
> nice, could mention in the changelog that we actualy
> synthesize the group leader (if we found one) for the
> thread even if it's not present in the thread_map,
> so the process maps are always in data
> 
> Acked-by: Jiri Olsa <jolsa@kernel.org>

I'll add your notes, thanks everyone,

- Arnaldo

[tip:perf/urgent] perf map: Synthesize maps only for thread group leader

[tip-bot for Konstantin Khlebnikov]

Commit-ID:  e5adfc3e7e774ba86f7bb725c6eef5f32df8630e
Gitweb:     https://git.kernel.org/tip/e5adfc3e7e774ba86f7bb725c6eef5f32df8630e
Author:     Konstantin Khlebnikov <khlebnikov@yandex-team.ru>
AuthorDate: Tue, 7 Aug 2018 12:09:01 +0300
Committer:  Arnaldo Carvalho de Melo <acme@redhat.com>
CommitDate: Wed, 8 Aug 2018 15:55:59 -0300

perf map: Synthesize maps only for thread group leader

Threads share map_groups, all map events are merged into it.

Thus we could send mmaps only for thread group leader.  Otherwise it
took ages to attach and record something from processes with many vmas
and threads.

Thread group leader could be already dead, but it seems perf cannot
handle this case anyway.

Testing dummy:

  #include <stdio.h>
  #include <stdlib.h>
  #include <sys/mman.h>
  #include <pthread.h>
  #include <unistd.h>

  void *thread(void *arg) {
          pause();
  }

  int main(int argc, char **argv) {
        int threads = 10000;
        int vmas = 50000;
        pthread_t th;
        for (int i = 0; i < threads; i++)
                pthread_create(&th, NULL, thread, NULL);
        for (int i = 0; i < vmas; i++)
                mmap(NULL, 4096, (i & 1) ? PROT_READ : PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
        sleep(60);
        return 0;
  }

Comment by Jiri Olsa:

We actualy synthesize the group leader (if we found one) for the thread
even if it's not present in the thread_map, so the process maps are
always in data.

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/153363294102.396323.6277944760215058174.stgit@buzz
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
 tools/perf/util/event.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/event.c b/tools/perf/util/event.c
index 0c8ecf0c78a4..0cd42150f712 100644
--- a/tools/perf/util/event.c
+++ b/tools/perf/util/event.c
@@ -541,10 +541,17 @@ static int __event__synthesize_thread(union perf_event *comm_event,
 						      tgid, process, machine) < 0)
 			return -1;
 
+		/*
+		 * send mmap only for thread group leader
+		 * see thread__init_map_groups
+		 */
+		if (pid == tgid &&
+		    perf_event__synthesize_mmap_events(tool, mmap_event, pid, tgid,
+						       process, machine, mmap_data,
+						       proc_map_timeout))
+			return -1;
 
-		return perf_event__synthesize_mmap_events(tool, mmap_event, pid, tgid,
-							  process, machine, mmap_data,
-							  proc_map_timeout);
+		return 0;
 	}
 
 	if (machine__is_default_guest(machine))