[PATCH v2] perf tools: fix off-by-one error in maps

[PATCH v2] perf tools: fix off-by-one error in maps

[Stephane Eranian]

This patch fixes off-by-one errors in the management of maps.
A map is defined by start address and length as implemented by map__new():

map__init(map, type, start, start + len, pgoff, dso);

map->start = addr;
map->end = end;

Consequently, the actual address range is ]start; end[
map->end is the first byte outside the range. This patch
fixes two bugs where upper bound checking was off-by-one.

In V2, we fix map_groups__fixup_overlappings() some more
where map->start was off-by-one as reported by Jiri.

Signed-off-by: Stephane Eranian <eranian@google.com>
---
 tools/perf/util/map.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index b709059..186418b 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -556,7 +556,7 @@ struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
 
 int map_groups__find_ams(struct addr_map_symbol *ams, symbol_filter_t filter)
 {
-	if (ams->addr < ams->map->start || ams->addr > ams->map->end) {
+	if (ams->addr < ams->map->start || ams->addr >= ams->map->end) {
 		if (ams->map->groups == NULL)
 			return -1;
 		ams->map = map_groups__find(ams->map->groups, ams->map->type,
@@ -664,7 +664,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 				goto move_map;
 			}
 
-			before->end = map->start - 1;
+			before->end = map->start;
 			map_groups__insert(mg, before);
 			if (verbose >= 2)
 				map__fprintf(before, fp);
@@ -678,7 +678,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 				goto move_map;
 			}
 
-			after->start = map->end + 1;
+			after->start = map->end;
 			map_groups__insert(mg, after);
 			if (verbose >= 2)
 				map__fprintf(after, fp);
-- 
1.9.1

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Namhyung Kim]

Hi Stephane,

On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
> This patch fixes off-by-one errors in the management of maps.
> A map is defined by start address and length as implemented by map__new():
>
> map__init(map, type, start, start + len, pgoff, dso);
>
> map->start = addr;
> map->end = end;
>
> Consequently, the actual address range is ]start; end[
> map->end is the first byte outside the range. This patch
> fixes two bugs where upper bound checking was off-by-one.
>
> In V2, we fix map_groups__fixup_overlappings() some more
> where map->start was off-by-one as reported by Jiri.

It seems we also need to fix maps__find():


diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index b7090596ac50..107a8c90785b 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
                m = rb_entry(parent, struct map, rb_node);
                if (ip < m->start)
                        p = &(*p)->rb_left;
-               else if (ip > m->end)
+               else if (ip >= m->end)
                        p = &(*p)->rb_right;
                else
                        return m;

Thanks,
Namhyung


>
> Signed-off-by: Stephane Eranian <eranian@google.com>
> ---
>  tools/perf/util/map.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> index b709059..186418b 100644
> --- a/tools/perf/util/map.c
> +++ b/tools/perf/util/map.c
> @@ -556,7 +556,7 @@ struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
>  
>  int map_groups__find_ams(struct addr_map_symbol *ams, symbol_filter_t filter)
>  {
> -	if (ams->addr < ams->map->start || ams->addr > ams->map->end) {
> +	if (ams->addr < ams->map->start || ams->addr >= ams->map->end) {
>  		if (ams->map->groups == NULL)
>  			return -1;
>  		ams->map = map_groups__find(ams->map->groups, ams->map->type,
> @@ -664,7 +664,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
>  				goto move_map;
>  			}
>  
> -			before->end = map->start - 1;
> +			before->end = map->start;
>  			map_groups__insert(mg, before);
>  			if (verbose >= 2)
>  				map__fprintf(before, fp);
> @@ -678,7 +678,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
>  				goto move_map;
>  			}
>  
> -			after->start = map->end + 1;
> +			after->start = map->end;
>  			map_groups__insert(mg, after);
>  			if (verbose >= 2)
>  				map__fprintf(after, fp);

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Stephane Eranian]

On Tue, Oct 7, 2014 at 7:47 AM, Namhyung Kim <namhyung@kernel.org> wrote:
> Hi Stephane,
>
> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
>> This patch fixes off-by-one errors in the management of maps.
>> A map is defined by start address and length as implemented by map__new():
>>
>> map__init(map, type, start, start + len, pgoff, dso);
>>
>> map->start = addr;
>> map->end = end;
>>
>> Consequently, the actual address range is ]start; end[
>> map->end is the first byte outside the range. This patch
>> fixes two bugs where upper bound checking was off-by-one.
>>
>> In V2, we fix map_groups__fixup_overlappings() some more
>> where map->start was off-by-one as reported by Jiri.
>
> It seems we also need to fix maps__find():
>
>
> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> index b7090596ac50..107a8c90785b 100644
> --- a/tools/perf/util/map.c
> +++ b/tools/perf/util/map.c
> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>                 m = rb_entry(parent, struct map, rb_node);
>                 if (ip < m->start)
>                         p = &(*p)->rb_left;
> -               else if (ip > m->end)
> +               else if (ip >= m->end)
>                         p = &(*p)->rb_right;
>                 else
>                         return m;
>
> Thanks,
> Namhyung
>
Yep, missing that one too. Hope there aren't any others....
Thanks.

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:
> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
> > This patch fixes off-by-one errors in the management of maps.
> > A map is defined by start address and length as implemented by map__new():

> > map__init(map, type, start, start + len, pgoff, dso);

> > map->start = addr;
> > map->end = end;

> > Consequently, the actual address range is ]start; end[
> > map->end is the first byte outside the range. This patch
> > fixes two bugs where upper bound checking was off-by-one.

> > In V2, we fix map_groups__fixup_overlappings() some more
> > where map->start was off-by-one as reported by Jiri.
 
> It seems we also need to fix maps__find():
 
> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> index b7090596ac50..107a8c90785b 100644
> --- a/tools/perf/util/map.c
> +++ b/tools/perf/util/map.c
> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>                 m = rb_entry(parent, struct map, rb_node);
>                 if (ip < m->start)
>                         p = &(*p)->rb_left;
> -               else if (ip > m->end)
> +               else if (ip >= m->end)
>                         p = &(*p)->rb_right;
>                 else
>                         return m;

I keep thinking that this change is making things unclear.

I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
of a map (map->end) is _in_ the map as well.

	if (addr > m->end)

is shorter than:

	if (addr >= m->end)

"start" and "end" should have the same rule applied, i.e. if one is in,
the other is in as well.

Etc.

- Arnaldo

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Stephane Eranian]

On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo
<acme@redhat.com> wrote:
> Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:
>> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
>> > This patch fixes off-by-one errors in the management of maps.
>> > A map is defined by start address and length as implemented by map__new():
>
>> > map__init(map, type, start, start + len, pgoff, dso);
>
>> > map->start = addr;
>> > map->end = end;
>
>> > Consequently, the actual address range is ]start; end[
>> > map->end is the first byte outside the range. This patch
>> > fixes two bugs where upper bound checking was off-by-one.
>
>> > In V2, we fix map_groups__fixup_overlappings() some more
>> > where map->start was off-by-one as reported by Jiri.
>
>> It seems we also need to fix maps__find():
>
>> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
>> index b7090596ac50..107a8c90785b 100644
>> --- a/tools/perf/util/map.c
>> +++ b/tools/perf/util/map.c
>> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>>                 m = rb_entry(parent, struct map, rb_node);
>>                 if (ip < m->start)
>>                         p = &(*p)->rb_left;
>> -               else if (ip > m->end)
>> +               else if (ip >= m->end)
>>                         p = &(*p)->rb_right;
>>                 else
>>                         return m;
>
> I keep thinking that this change is making things unclear.
>
> I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
> of a map (map->end) is _in_ the map as well.
>
>         if (addr > m->end)
>
> is shorter than:
>
>         if (addr >= m->end)
>
> "start" and "end" should have the same rule applied, i.e. if one is in,
> the other is in as well.
>
It is okay but then we need to be consistent all across. This is not
the case today.
I mentioned the cases I ran into.

> Etc.
>
> - Arnaldo

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:
> On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo
> <acme@redhat.com> wrote:
> > Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:
> >> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
> >> > This patch fixes off-by-one errors in the management of maps.
> >> > A map is defined by start address and length as implemented by map__new():
> >
> >> > map__init(map, type, start, start + len, pgoff, dso);
> >
> >> > map->start = addr;
> >> > map->end = end;
> >
> >> > Consequently, the actual address range is ]start; end[
> >> > map->end is the first byte outside the range. This patch
> >> > fixes two bugs where upper bound checking was off-by-one.
> >
> >> > In V2, we fix map_groups__fixup_overlappings() some more
> >> > where map->start was off-by-one as reported by Jiri.
> >
> >> It seems we also need to fix maps__find():
> >
> >> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> >> index b7090596ac50..107a8c90785b 100644
> >> --- a/tools/perf/util/map.c
> >> +++ b/tools/perf/util/map.c
> >> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
> >>                 m = rb_entry(parent, struct map, rb_node);
> >>                 if (ip < m->start)
> >>                         p = &(*p)->rb_left;
> >> -               else if (ip > m->end)
> >> +               else if (ip >= m->end)
> >>                         p = &(*p)->rb_right;
> >>                 else
> >>                         return m;
> >
> > I keep thinking that this change is making things unclear.
> >
> > I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
> > of a map (map->end) is _in_ the map as well.
> >
> >         if (addr > m->end)
> >
> > is shorter than:
> >
> >         if (addr >= m->end)
> >
> > "start" and "end" should have the same rule applied, i.e. if one is in,
> > the other is in as well.
> >
> It is okay but then we need to be consistent all across. This is not
> the case today.
> I mentioned the cases I ran into.

Ok, and provided a patch doing the way I thought was confusing, now its
my turn to use that info and come up with a patch, ok, will do that.

- Arnaldo

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Stephane Eranian]

On Tue, Oct 7, 2014 at 5:10 PM, Arnaldo Carvalho de Melo
<acme@redhat.com> wrote:
> Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:
>> On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo
>> <acme@redhat.com> wrote:
>> > Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:
>> >> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
>> >> > This patch fixes off-by-one errors in the management of maps.
>> >> > A map is defined by start address and length as implemented by map__new():
>> >
>> >> > map__init(map, type, start, start + len, pgoff, dso);
>> >
>> >> > map->start = addr;
>> >> > map->end = end;
>> >
>> >> > Consequently, the actual address range is ]start; end[
>> >> > map->end is the first byte outside the range. This patch
>> >> > fixes two bugs where upper bound checking was off-by-one.
>> >
>> >> > In V2, we fix map_groups__fixup_overlappings() some more
>> >> > where map->start was off-by-one as reported by Jiri.
>> >
>> >> It seems we also need to fix maps__find():
>> >
>> >> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
>> >> index b7090596ac50..107a8c90785b 100644
>> >> --- a/tools/perf/util/map.c
>> >> +++ b/tools/perf/util/map.c
>> >> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>> >>                 m = rb_entry(parent, struct map, rb_node);
>> >>                 if (ip < m->start)
>> >>                         p = &(*p)->rb_left;
>> >> -               else if (ip > m->end)
>> >> +               else if (ip >= m->end)
>> >>                         p = &(*p)->rb_right;
>> >>                 else
>> >>                         return m;
>> >
>> > I keep thinking that this change is making things unclear.
>> >
>> > I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
>> > of a map (map->end) is _in_ the map as well.
>> >
>> >         if (addr > m->end)
>> >
>> > is shorter than:
>> >
>> >         if (addr >= m->end)
>> >
>> > "start" and "end" should have the same rule applied, i.e. if one is in,
>> > the other is in as well.
>> >
>> It is okay but then we need to be consistent all across. This is not
>> the case today.
>> I mentioned the cases I ran into.
>
> Ok, and provided a patch doing the way I thought was confusing, now its
> my turn to use that info and come up with a patch, ok, will do that.
>
You got it! ;->

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Chuck Ebbert]

On Tue, 7 Oct 2014 11:00:50 -0300
Arnaldo Carvalho de Melo <acme@redhat.com> wrote:

> I keep thinking that this change is making things unclear.
> 
> I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
> of a map (map->end) is _in_ the map as well.
> 
> 	if (addr > m->end)
> 
> is shorter than:
> 
> 	if (addr >= m->end)
> 
> "start" and "end" should have the same rule applied, i.e. if one is in,
> the other is in as well.
> 
> Etc.
> 

But the convention used in the memory management code is that "end" is
the next byte after the memory region. This gives you:

  size = end - start
  end = start + size

Using a different convention here will just confuse people used to the
way it's done everywhere else.

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 07, 2014 at 01:58:38PM -0500, Chuck Ebbert escreveu:
> On Tue, 7 Oct 2014 11:00:50 -0300
> Arnaldo Carvalho de Melo <acme@redhat.com> wrote:
> 
> > I keep thinking that this change is making things unclear.
> > 
> > I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
> > of a map (map->end) is _in_ the map as well.
> > 
> > 	if (addr > m->end)
> > 
> > is shorter than:
> > 
> > 	if (addr >= m->end)
> > 
> > "start" and "end" should have the same rule applied, i.e. if one is in,
> > the other is in as well.
> > 
> > Etc.
> > 
> 
> But the convention used in the memory management code is that "end" is
> the next byte after the memory region. This gives you:
> 
>   size = end - start
>   end = start + size
> 
> Using a different convention here will just confuse people used to the
> way it's done everywhere else.

So we should continue using some confusing convention because that is
the way that things are? :-\

- Arnaldo

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 07, 2014 at 05:17:12PM +0200, Stephane Eranian escreveu:
> On Tue, Oct 7, 2014 at 5:10 PM, Arnaldo Carvalho de Melo
> <acme@redhat.com> wrote:
> > Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:
> >> On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo
> >> >> +++ b/tools/perf/util/map.c
> >> >> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
> >> >>                 m = rb_entry(parent, struct map, rb_node);
> >> >>                 if (ip < m->start)
> >> >>                         p = &(*p)->rb_left;
> >> >> -               else if (ip > m->end)
> >> >> +               else if (ip >= m->end)
> >> >>                         p = &(*p)->rb_right;
> >> >>                 else
> >> >>                         return m;

> >> > I keep thinking that this change is making things unclear.

> >> > I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
> >> > of a map (map->end) is _in_ the map as well.

> >> >         if (addr > m->end)

> >> > is shorter than:

> >> >         if (addr >= m->end)

> >> > "start" and "end" should have the same rule applied, i.e. if one is in,
> >> > the other is in as well.

> >> It is okay but then we need to be consistent all across. This is not
> >> the case today.
> >> I mentioned the cases I ran into.

> > Ok, and provided a patch doing the way I thought was confusing, now its
> > my turn to use that info and come up with a patch, ok, will do that.

> You got it! ;->

struct vm_area_struct {
        /* The first cache line has the info for VMA tree walking. */

        unsigned long vm_start;         /* Our start address within vm_mm. */
        unsigned long vm_end;           /* The first byte after our end address
                                           within vm_mm. */

So these guys have been doing this far longer than me, I guess I'll bow
to this convention.

But by renaming map->end to map->end_ and looking at all the usage of
it, there are some inconsistencies...

Like symbol->{start,end} is of the [start,end] case, and to be
consistent with above needs to also move to [start,end[, will cook a
patch and send for review.

- Arnaldo

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Stephane Eranian]

On Tue, Oct 14, 2014 at 8:58 PM, Arnaldo Carvalho de Melo
<acme@redhat.com> wrote:
> Em Tue, Oct 07, 2014 at 05:17:12PM +0200, Stephane Eranian escreveu:
>> On Tue, Oct 7, 2014 at 5:10 PM, Arnaldo Carvalho de Melo
>> <acme@redhat.com> wrote:
>> > Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:
>> >> On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo
>> >> >> +++ b/tools/perf/util/map.c
>> >> >> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>> >> >>                 m = rb_entry(parent, struct map, rb_node);
>> >> >>                 if (ip < m->start)
>> >> >>                         p = &(*p)->rb_left;
>> >> >> -               else if (ip > m->end)
>> >> >> +               else if (ip >= m->end)
>> >> >>                         p = &(*p)->rb_right;
>> >> >>                 else
>> >> >>                         return m;
>
>> >> > I keep thinking that this change is making things unclear.
>
>> >> > I.e. the _start_ of a map (map->start) is _in_ the map, and the _end_
>> >> > of a map (map->end) is _in_ the map as well.
>
>> >> >         if (addr > m->end)
>
>> >> > is shorter than:
>
>> >> >         if (addr >= m->end)
>
>> >> > "start" and "end" should have the same rule applied, i.e. if one is in,
>> >> > the other is in as well.
>
>> >> It is okay but then we need to be consistent all across. This is not
>> >> the case today.
>> >> I mentioned the cases I ran into.
>
>> > Ok, and provided a patch doing the way I thought was confusing, now its
>> > my turn to use that info and come up with a patch, ok, will do that.
>
>> You got it! ;->
>
> struct vm_area_struct {
>         /* The first cache line has the info for VMA tree walking. */
>
>         unsigned long vm_start;         /* Our start address within vm_mm. */
>         unsigned long vm_end;           /* The first byte after our end address
>                                            within vm_mm. */
>
> So these guys have been doing this far longer than me, I guess I'll bow
> to this convention.
>
> But by renaming map->end to map->end_ and looking at all the usage of
> it, there are some inconsistencies...
>
> Like symbol->{start,end} is of the [start,end] case, and to be
> consistent with above needs to also move to [start,end[, will cook a
> patch and send for review.
>
Yes, there were some inconsistencies (or confusions) that I noticed when
I started fixing the maps. I can believe that this off-by-one error exist with
other data types. That could cause wrong symbol correlations in borderline
cases (which are really rare).

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:
> Hi Stephane,
> 
> On Mon, 6 Oct 2014 10:35:32 +0200, Stephane Eranian wrote:
> > This patch fixes off-by-one errors in the management of maps.
> > A map is defined by start address and length as implemented by map__new():
> >
> > map__init(map, type, start, start + len, pgoff, dso);
> >
> > map->start = addr;
> > map->end = end;
> >
> > Consequently, the actual address range is ]start; end[
> > map->end is the first byte outside the range. This patch
> > fixes two bugs where upper bound checking was off-by-one.
> >
> > In V2, we fix map_groups__fixup_overlappings() some more
> > where map->start was off-by-one as reported by Jiri.
> 
>> It seems we also need to fix maps__find():


So I am getting this as an ack for Stephane's V2 patch and the patch
below as an extra patch, from you, acked by Stephane.

- Arnaldo
 
> 
> diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> index b7090596ac50..107a8c90785b 100644
> --- a/tools/perf/util/map.c
> +++ b/tools/perf/util/map.c
> @@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
>                 m = rb_entry(parent, struct map, rb_node);
>                 if (ip < m->start)
>                         p = &(*p)->rb_left;
> -               else if (ip > m->end)
> +               else if (ip >= m->end)
>                         p = &(*p)->rb_right;
>                 else
>                         return m;
> 
> Thanks,
> Namhyung
> 
> 
> >
> > Signed-off-by: Stephane Eranian <eranian@google.com>
> > ---
> >  tools/perf/util/map.c | 6 +++---
> >  1 file changed, 3 insertions(+), 3 deletions(-)
> >
> > diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
> > index b709059..186418b 100644
> > --- a/tools/perf/util/map.c
> > +++ b/tools/perf/util/map.c
> > @@ -556,7 +556,7 @@ struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
> >  
> >  int map_groups__find_ams(struct addr_map_symbol *ams, symbol_filter_t filter)
> >  {
> > -	if (ams->addr < ams->map->start || ams->addr > ams->map->end) {
> > +	if (ams->addr < ams->map->start || ams->addr >= ams->map->end) {
> >  		if (ams->map->groups == NULL)
> >  			return -1;
> >  		ams->map = map_groups__find(ams->map->groups, ams->map->type,
> > @@ -664,7 +664,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
> >  				goto move_map;
> >  			}
> >  
> > -			before->end = map->start - 1;
> > +			before->end = map->start;
> >  			map_groups__insert(mg, before);
> >  			if (verbose >= 2)
> >  				map__fprintf(before, fp);
> > @@ -678,7 +678,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
> >  				goto move_map;
> >  			}
> >  
> > -			after->start = map->end + 1;
> > +			after->start = map->end;
> >  			map_groups__insert(mg, after);
> >  			if (verbose >= 2)
> >  				map__fprintf(after, fp);

Re: [PATCH v2] perf tools: fix off-by-one error in maps

[Arnaldo Carvalho de Melo]

Em Tue, Oct 14, 2014 at 09:03:02PM +0200, Stephane Eranian escreveu:
> On Tue, Oct 14, 2014 at 8:58 PM, Arnaldo Carvalho de Melo
> > struct vm_area_struct {
> >         /* The first cache line has the info for VMA tree walking. */

> >         unsigned long vm_start;         /* Our start address within vm_mm. */
> >         unsigned long vm_end;           /* The first byte after our end address
> >                                            within vm_mm. */

> > So these guys have been doing this far longer than me, I guess I'll bow
> > to this convention.

> > But by renaming map->end to map->end_ and looking at all the usage of
> > it, there are some inconsistencies...

> > Like symbol->{start,end} is of the [start,end] case, and to be
> > consistent with above needs to also move to [start,end[, will cook a
> > patch and send for review.

> Yes, there were some inconsistencies (or confusions) that I noticed when
> I started fixing the maps. I can believe that this off-by-one error exist with
> other data types. That could cause wrong symbol correlations in borderline
> cases (which are really rare).

Yeah, I'll try and fix one by one in separate patches when applicable.

- Arnaldo

[tip:perf/urgent] perf tools: fix off-by-one error in maps

[tip-bot for Stephane Eranian]

Commit-ID:  77faf4d060e3ee1fd2ff6cd39f2b2eb887100422
Gitweb:     http://git.kernel.org/tip/77faf4d060e3ee1fd2ff6cd39f2b2eb887100422
Author:     Stephane Eranian <eranian@google.com>
AuthorDate: Mon, 6 Oct 2014 10:35:32 +0200
Committer:  Arnaldo Carvalho de Melo <acme@redhat.com>
CommitDate: Tue, 14 Oct 2014 17:50:55 -0300

perf tools: fix off-by-one error in maps

This patch fixes off-by-one errors in the management of maps.

A map is defined by start address and length as implemented by
map__new():

  map__init(map, type, start, start + len, pgoff, dso);

  map->start = addr;
  map->end = end;

Consequently, the actual address range is [start; end[ map->end is the
first byte outside the range.

This patch fixes two bugs where upper bound checking was off-by-one.

In V2, we fix map_groups__fixup_overlappings() some more where
map->start was off-by-one as reported by Jiri.

Signed-off-by: Stephane Eranian <eranian@google.com>
Acked-by: Namhyung Kim <namhyung@kernel.org>
Cc: David Ahern <dsahern@gmail.com>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/20141006083532.GA4850@quad
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
 tools/perf/util/map.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index b709059..186418b 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -556,7 +556,7 @@ struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
 
 int map_groups__find_ams(struct addr_map_symbol *ams, symbol_filter_t filter)
 {
-	if (ams->addr < ams->map->start || ams->addr > ams->map->end) {
+	if (ams->addr < ams->map->start || ams->addr >= ams->map->end) {
 		if (ams->map->groups == NULL)
 			return -1;
 		ams->map = map_groups__find(ams->map->groups, ams->map->type,
@@ -664,7 +664,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 				goto move_map;
 			}
 
-			before->end = map->start - 1;
+			before->end = map->start;
 			map_groups__insert(mg, before);
 			if (verbose >= 2)
 				map__fprintf(before, fp);
@@ -678,7 +678,7 @@ int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 				goto move_map;
 			}
 
-			after->start = map->end + 1;
+			after->start = map->end;
 			map_groups__insert(mg, after);
 			if (verbose >= 2)
 				map__fprintf(after, fp);

[tip:perf/urgent] perf tools: Fixup off-by-one comparision in maps__find

[tip-bot for Namhyung Kim]

Commit-ID:  4955ea225db42144d1667838f908315a16d51c5b
Gitweb:     http://git.kernel.org/tip/4955ea225db42144d1667838f908315a16d51c5b
Author:     Namhyung Kim <namhyung@kernel.org>
AuthorDate: Tue, 14 Oct 2014 16:05:38 -0300
Committer:  Arnaldo Carvalho de Melo <acme@redhat.com>
CommitDate: Tue, 14 Oct 2014 17:50:56 -0300

perf tools: Fixup off-by-one comparision in maps__find

map->end is the first addr _outside_ the a map, following the convention
of vm_area_struct->vm_end.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
Acked-by: Stephane Eranian <eranian@google.com>
Cc: David Ahern <dsahern@gmail.com>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Stephane Eranian <eranian@google.com>
Link: http://lkml.kernel.org/r/8761fwh1nc.fsf@sejong.aot.lge.com
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
 tools/perf/util/map.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index 186418b..2137c45 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -752,7 +752,7 @@ struct map *maps__find(struct rb_root *maps, u64 ip)
 		m = rb_entry(parent, struct map, rb_node);
 		if (ip < m->start)
 			p = &(*p)->rb_left;
-		else if (ip > m->end)
+		else if (ip >= m->end)
 			p = &(*p)->rb_right;
 		else
 			return m;