[PATCH 26/48] perf tools: Introduce map_groups__{insert,find}_by_time()

[Jiri Olsa <jolsa@kernel.org>]

From: Namhyung Kim <namhyung@kernel.org>

It'll manage maps using timestamp so that it can find correct
map/symbol for sample at a certain time.  With this API, it can
maintain overlapping maps in a map_groups.

Cc: Stephane Eranian <eranian@google.com>
Link: http://lkml.kernel.org/n/tip-3bzcl4dzqh6qiqaddo5gco4y@git.kernel.org
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
 tools/perf/util/map.c | 64 +++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/map.h | 24 ++++++++++++++++
 2 files changed, 88 insertions(+)

diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c
index 2821919156c9..4135a22091fe 100644
--- a/tools/perf/util/map.c
+++ b/tools/perf/util/map.c
@@ -825,6 +825,41 @@ void maps__insert(struct maps *maps, struct map *map)
 	up_write(&maps->lock);
 }
 
+static void __maps__insert_by_time(struct maps *maps, struct map *map)
+{
+	struct rb_node **p = &maps->entries.rb_node;
+	struct rb_node *parent = NULL;
+	const u64 ip = map->start;
+	const u64 timestamp = map->timestamp;
+	struct map *m;
+
+	while (*p != NULL) {
+		parent = *p;
+		m = rb_entry(parent, struct map, rb_node);
+		if (ip < m->start)
+			p = &(*p)->rb_left;
+		else if (ip > m->start)
+			p = &(*p)->rb_right;
+		else if (timestamp > m->timestamp)
+			p = &(*p)->rb_left;
+		else if (timestamp <= m->timestamp)
+			p = &(*p)->rb_right;
+		else
+			BUG_ON(1);
+	}
+
+	rb_link_node(&map->rb_node, parent, p);
+	rb_insert_color(&map->rb_node, &maps->entries);
+	map__get(map);
+}
+
+void maps__insert_by_time(struct maps *maps, struct map *map)
+{
+	down_write(&maps->lock);
+	__maps__insert_by_time(maps, map);
+	up_write(&maps->lock);
+}
+
 static void __maps__remove(struct maps *maps, struct map *map)
 {
 	rb_erase_init(&map->rb_node, &maps->entries);
@@ -863,6 +898,35 @@ struct map *maps__find(struct maps *maps, u64 ip)
 	return m;
 }
 
+struct map *maps__find_by_time(struct maps *maps, u64 ip, u64 timestamp)
+{
+	struct rb_node **p;
+	struct rb_node *parent = NULL;
+	struct map *m;
+	struct map *best = NULL;
+
+	down_read(&maps->lock);
+
+	p = &maps->entries.rb_node;
+	while (*p != NULL) {
+		parent = *p;
+		m = rb_entry(parent, struct map, rb_node);
+		if (ip < m->start)
+			p = &(*p)->rb_left;
+		else if (ip >= m->end)
+			p = &(*p)->rb_right;
+		else if (timestamp >= m->timestamp) {
+			if (!best || best->timestamp < m->timestamp)
+				best = m;
+			p = &(*p)->rb_left;
+		} else
+			p = &(*p)->rb_right;
+	}
+
+	up_read(&maps->lock);
+	return best;
+}
+
 struct map *maps__first(struct maps *maps)
 {
 	struct rb_node *first = rb_first(&maps->entries);
diff --git a/tools/perf/util/map.h b/tools/perf/util/map.h
index 0d35064cf813..02c6f6962eb1 100644
--- a/tools/perf/util/map.h
+++ b/tools/perf/util/map.h
@@ -13,6 +13,8 @@
 #include <linux/types.h>
 #include "rwsem.h"
 
+#include "perf.h"  /* for perf_has_index */
+
 struct dso;
 struct ip_callchain;
 struct ref_reloc_sym;
@@ -186,8 +188,10 @@ void map__fixup_end(struct map *map);
 void map__reloc_vmlinux(struct map *map);
 
 void maps__insert(struct maps *maps, struct map *map);
+void maps__insert_by_time(struct maps *maps, struct map *map);
 void maps__remove(struct maps *maps, struct map *map);
 struct map *maps__find(struct maps *maps, u64 addr);
+struct map *maps__find_by_time(struct maps *maps, u64 addr, u64 timestamp);
 struct map *maps__first(struct maps *maps);
 struct map *map__next(struct map *map);
 struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name,
@@ -207,6 +211,17 @@ static inline void map_groups__insert(struct map_groups *mg, struct map *map)
 	map->groups = mg;
 }
 
+static inline void map_groups__insert_by_time(struct map_groups *mg,
+					      struct map *map)
+{
+	if (perf_has_index)
+		maps__insert_by_time(&mg->maps, map);
+	else
+		maps__insert(&mg->maps, map);
+
+	map->groups = mg;
+}
+
 static inline void map_groups__remove(struct map_groups *mg, struct map *map)
 {
 	maps__remove(&mg->maps, map);
@@ -219,6 +234,15 @@ static inline struct map *map_groups__find(struct map_groups *mg, u64 addr)
 
 struct map *map_groups__first(struct map_groups *mg);
 
+static inline struct map *map_groups__find_by_time(struct map_groups *mg,
+						   u64 addr, u64 timestamp)
+{
+	if (!perf_has_index)
+		return maps__find(&mg->maps, addr);
+
+	return maps__find_by_time(&mg->maps, addr, timestamp);
+}
+
 static inline struct map *map_groups__next(struct map *map)
 {
 	return map__next(map);
-- 
2.17.1