From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752531AbbERAmj (ORCPT ); Sun, 17 May 2015 20:42:39 -0400 Received: from LGEMRELSE6Q.lge.com ([156.147.1.121]:55372 "EHLO lgemrelse6q.lge.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752299AbbERAlx (ORCPT ); Sun, 17 May 2015 20:41:53 -0400 X-Original-SENDERIP: 10.177.220.203 X-Original-MAILFROM: namhyung@kernel.org From: Namhyung Kim To: Arnaldo Carvalho de Melo Cc: Ingo Molnar , Peter Zijlstra , Jiri Olsa , LKML , David Ahern , Adrian Hunter , Andi Kleen , Frederic Weisbecker , Stephane Eranian Subject: [PATCH 22/40] perf tools: Introduce map_groups__{insert,find}_by_time() Date: Mon, 18 May 2015 09:30:37 +0900 Message-Id: <1431909055-21442-23-git-send-email-namhyung@kernel.org> X-Mailer: git-send-email 2.4.0 In-Reply-To: <1431909055-21442-1-git-send-email-namhyung@kernel.org> References: <1431909055-21442-1-git-send-email-namhyung@kernel.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.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 Signed-off-by: Namhyung Kim --- tools/perf/util/map.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++ tools/perf/util/map.h | 25 +++++++++++++++++++++++++ 2 files changed, 77 insertions(+) diff --git a/tools/perf/util/map.c b/tools/perf/util/map.c index fef4e38ccd93..8bc016648a34 100644 --- a/tools/perf/util/map.c +++ b/tools/perf/util/map.c @@ -746,6 +746,33 @@ void maps__insert(struct rb_root *maps, struct map *map) rb_insert_color(&map->rb_node, maps); } +void maps__insert_by_time(struct rb_root *maps, struct map *map) +{ + struct rb_node **p = &maps->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); +} + void maps__remove(struct rb_root *maps, struct map *map) { rb_erase(&map->rb_node, maps); @@ -771,6 +798,31 @@ struct map *maps__find(struct rb_root *maps, u64 ip) return NULL; } +struct map *maps__find_by_time(struct rb_root *maps, u64 ip, u64 timestamp) +{ + struct rb_node **p = &maps->rb_node; + struct rb_node *parent = NULL; + struct map *m; + struct map *best = NULL; + + 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; + } + + return best; +} + struct map *maps__first(struct rb_root *maps) { struct rb_node *first = rb_first(maps); diff --git a/tools/perf/util/map.h b/tools/perf/util/map.h index c1ed11a3e16c..fc8cdb8853f5 100644 --- a/tools/perf/util/map.h +++ b/tools/perf/util/map.h @@ -8,6 +8,8 @@ #include #include +#include "perf.h" /* for perf_has_index */ + enum map_type { MAP__FUNCTION = 0, MAP__VARIABLE, @@ -166,8 +168,10 @@ void map__reloc_vmlinux(struct map *map); size_t __map_groups__fprintf_maps(struct map_groups *mg, enum map_type type, FILE *fp); void maps__insert(struct rb_root *maps, struct map *map); +void maps__insert_by_time(struct rb_root *maps, struct map *map); void maps__remove(struct rb_root *maps, struct map *map); struct map *maps__find(struct rb_root *maps, u64 addr); +struct map *maps__find_by_time(struct rb_root *maps, u64 addr, u64 timestamp); struct map *maps__first(struct rb_root *maps); struct map *maps__next(struct map *map); void map_groups__init(struct map_groups *mg, struct machine *machine); @@ -185,6 +189,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->type], map); + else + maps__insert(&mg->maps[map->type], map); + + map->groups = mg; +} + static inline void map_groups__remove(struct map_groups *mg, struct map *map) { maps__remove(&mg->maps[map->type], map); @@ -196,6 +211,16 @@ static inline struct map *map_groups__find(struct map_groups *mg, return maps__find(&mg->maps[type], addr); } +static inline struct map *map_groups__find_by_time(struct map_groups *mg, + enum map_type type, u64 addr, + u64 timestamp) +{ + if (!perf_has_index) + return maps__find(&mg->maps[type], addr); + + return maps__find_by_time(&mg->maps[type], addr, timestamp); +} + static inline struct map *map_groups__first(struct map_groups *mg, enum map_type type) { -- 2.4.0