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 <[email protected]>

---
 tools/perf/util/map.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

tools/perf/util/map.c +3 -3

index b709059..186418b 100644
@@ -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);

Hi Stephane,

Quoted 8 lines · 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;

Quoted 6 lines

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():

tools/perf/util/map.c +1 -1

index b7090596ac50..107a8c90785b 100644
@@ -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

Quoted 8 lines

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;

Quoted 6 lines

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():

tools/perf/util/map.c +0 -0

index b7090596ac50..107a8c90785b 100644

Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:

Quoted 23 lines · Stephane Eranian

Quoted 8 lines

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;

Quoted 6 lines

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():

tools/perf/util/map.c +0 -0

index b7090596ac50..107a8c90785b 100644

tools/perf/util/map.c struct map *maps__find(struct rb_root *maps, u64 ip) · line 758

Quoted 8 lines

tools/perf/util/map.c +1 -1

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

Quoted 42 lines · Arnaldo Carvalho de Melo

Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:

Quoted 23 lines · Stephane Eranian

Quoted 8 lines

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;

Quoted 6 lines

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():

tools/perf/util/map.c +0 -0

index b7090596ac50..107a8c90785b 100644

tools/perf/util/map.c struct map *maps__find(struct rb_root *maps, u64 ip) · line 758

Quoted 8 lines

tools/perf/util/map.c +1 -1

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

Quoted 5 lines

        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.

Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:

Quoted 49 lines

Quoted 47 lines · Arnaldo Carvalho de Melo

Em Tue, Oct 07, 2014 at 02:47:19PM +0900, Namhyung Kim escreveu:

Quoted 23 lines · Stephane Eranian

Quoted 8 lines

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;

Quoted 6 lines

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():

tools/perf/util/map.c +0 -0

index b7090596ac50..107a8c90785b 100644

tools/perf/util/map.c struct map *maps__find(struct rb_root *maps, u64 ip) · line 758

Quoted 8 lines

tools/perf/util/map.c +1 -1

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

Quoted 3 lines

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.

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.

Quoted 7 lines · On Tue, 7 Oct 2014 11:00:50 -0300 Arnaldo Carvalho de Melo <[email protected]>…

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)

Quoted 9 lines

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.

Quoted 26 lines · Arnaldo Carvalho de Melo

Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:

Quoted 25 lines

On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo

Quoted 24 lines

tools/perf/util/map.c struct map *maps__find(struct rb_root *maps, u64 ip) · line 758

Quoted 10 lines

+++ b/tools/perf/util/map.c

tools/perf/util/map.c +1 -1

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

Quoted 6 lines

Quoted 3 lines

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

Em Tue, Oct 07, 2014 at 05:17:12PM +0200, Stephane Eranian escreveu:

Quoted 29 lines

Quoted 26 lines · Arnaldo Carvalho de Melo

Em Tue, Oct 07, 2014 at 04:17:41PM +0200, Stephane Eranian escreveu:

Quoted 25 lines

On Tue, Oct 7, 2014 at 4:00 PM, Arnaldo Carvalho de Melo

Quoted 24 lines

tools/perf/util/map.c struct map *maps__find(struct rb_root *maps, u64 ip) · line 758

Quoted 10 lines

+++ b/tools/perf/util/map.c

tools/perf/util/map.c +1 -1

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

Quoted 8 lines

Quoted 6 lines

Quoted 3 lines

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.

Hi Stephane,

Quoted 16 lines · 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.

It seems we also need to fix maps__find():

tools/perf/util/map.c +1 -1

index b7090596ac50..107a8c90785b 100644
@@ -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

Quoted 37 lines

Signed-off-by Stephane Eranian <[email protected]>

---
 tools/perf/util/map.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

tools/perf/util/map.c +3 -3

index b709059..186418b 100644
@@ -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);

On Tue, Oct 14, 2014 at 8:58 PM, Arnaldo Carvalho de Melo

Quoted 12 lines

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...

Quoted 3 lines

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