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@xxxxxxxxxxxxxx>

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