summaryrefslogtreecommitdiffstats
path: root/tools/perf/util/maps.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/perf/util/maps.c')
-rw-r--r--tools/perf/util/maps.c528
1 files changed, 445 insertions, 83 deletions
diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c
index 233438c95b..0334fc18d9 100644
--- a/tools/perf/util/maps.c
+++ b/tools/perf/util/maps.c
@@ -10,6 +10,68 @@
#include "ui/ui.h"
#include "unwind.h"
+struct map_rb_node {
+ struct rb_node rb_node;
+ struct map *map;
+};
+
+#define maps__for_each_entry(maps, map) \
+ for (map = maps__first(maps); map; map = map_rb_node__next(map))
+
+#define maps__for_each_entry_safe(maps, map, next) \
+ for (map = maps__first(maps), next = map_rb_node__next(map); map; \
+ map = next, next = map_rb_node__next(map))
+
+static struct rb_root *maps__entries(struct maps *maps)
+{
+ return &RC_CHK_ACCESS(maps)->entries;
+}
+
+static struct rw_semaphore *maps__lock(struct maps *maps)
+{
+ return &RC_CHK_ACCESS(maps)->lock;
+}
+
+static struct map **maps__maps_by_name(struct maps *maps)
+{
+ return RC_CHK_ACCESS(maps)->maps_by_name;
+}
+
+static struct map_rb_node *maps__first(struct maps *maps)
+{
+ struct rb_node *first = rb_first(maps__entries(maps));
+
+ if (first)
+ return rb_entry(first, struct map_rb_node, rb_node);
+ return NULL;
+}
+
+static struct map_rb_node *map_rb_node__next(struct map_rb_node *node)
+{
+ struct rb_node *next;
+
+ if (!node)
+ return NULL;
+
+ next = rb_next(&node->rb_node);
+
+ if (!next)
+ return NULL;
+
+ return rb_entry(next, struct map_rb_node, rb_node);
+}
+
+static struct map_rb_node *maps__find_node(struct maps *maps, struct map *map)
+{
+ struct map_rb_node *rb_node;
+
+ maps__for_each_entry(maps, rb_node) {
+ if (rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map))
+ return rb_node;
+ }
+ return NULL;
+}
+
static void maps__init(struct maps *maps, struct machine *machine)
{
refcount_set(maps__refcnt(maps), 1);
@@ -196,6 +258,41 @@ void maps__put(struct maps *maps)
RC_CHK_PUT(maps);
}
+int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data)
+{
+ struct map_rb_node *pos;
+ int ret = 0;
+
+ down_read(maps__lock(maps));
+ maps__for_each_entry(maps, pos) {
+ ret = cb(pos->map, data);
+ if (ret)
+ break;
+ }
+ up_read(maps__lock(maps));
+ return ret;
+}
+
+void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data)
+{
+ struct map_rb_node *pos, *next;
+ unsigned int start_nr_maps;
+
+ down_write(maps__lock(maps));
+
+ start_nr_maps = maps__nr_maps(maps);
+ maps__for_each_entry_safe(maps, pos, next) {
+ if (cb(pos->map, data)) {
+ __maps__remove(maps, pos);
+ --RC_CHK_ACCESS(maps)->nr_maps;
+ }
+ }
+ if (maps__maps_by_name(maps) && start_nr_maps != maps__nr_maps(maps))
+ __maps__free_maps_by_name(maps);
+
+ up_write(maps__lock(maps));
+}
+
struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
{
struct map *map = maps__find(maps, addr);
@@ -210,31 +307,40 @@ struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
return NULL;
}
-struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
-{
+struct maps__find_symbol_by_name_args {
+ struct map **mapp;
+ const char *name;
struct symbol *sym;
- struct map_rb_node *pos;
+};
- down_read(maps__lock(maps));
+static int maps__find_symbol_by_name_cb(struct map *map, void *data)
+{
+ struct maps__find_symbol_by_name_args *args = data;
- maps__for_each_entry(maps, pos) {
- sym = map__find_symbol_by_name(pos->map, name);
+ args->sym = map__find_symbol_by_name(map, args->name);
+ if (!args->sym)
+ return 0;
- if (sym == NULL)
- continue;
- if (!map__contains_symbol(pos->map, sym)) {
- sym = NULL;
- continue;
- }
- if (mapp != NULL)
- *mapp = pos->map;
- goto out;
+ if (!map__contains_symbol(map, args->sym)) {
+ args->sym = NULL;
+ return 0;
}
- sym = NULL;
-out:
- up_read(maps__lock(maps));
- return sym;
+ if (args->mapp != NULL)
+ *args->mapp = map__get(map);
+ return 1;
+}
+
+struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
+{
+ struct maps__find_symbol_by_name_args args = {
+ .mapp = mapp,
+ .name = name,
+ .sym = NULL,
+ };
+
+ maps__for_each_map(maps, maps__find_symbol_by_name_cb, &args);
+ return args.sym;
}
int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
@@ -253,41 +359,46 @@ int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
return ams->ms.sym ? 0 : -1;
}
-size_t maps__fprintf(struct maps *maps, FILE *fp)
-{
- size_t printed = 0;
- struct map_rb_node *pos;
+struct maps__fprintf_args {
+ FILE *fp;
+ size_t printed;
+};
- down_read(maps__lock(maps));
+static int maps__fprintf_cb(struct map *map, void *data)
+{
+ struct maps__fprintf_args *args = data;
- maps__for_each_entry(maps, pos) {
- printed += fprintf(fp, "Map:");
- printed += map__fprintf(pos->map, fp);
- if (verbose > 2) {
- printed += dso__fprintf(map__dso(pos->map), fp);
- printed += fprintf(fp, "--\n");
- }
+ args->printed += fprintf(args->fp, "Map:");
+ args->printed += map__fprintf(map, args->fp);
+ if (verbose > 2) {
+ args->printed += dso__fprintf(map__dso(map), args->fp);
+ args->printed += fprintf(args->fp, "--\n");
}
+ return 0;
+}
- up_read(maps__lock(maps));
+size_t maps__fprintf(struct maps *maps, FILE *fp)
+{
+ struct maps__fprintf_args args = {
+ .fp = fp,
+ .printed = 0,
+ };
+
+ maps__for_each_map(maps, maps__fprintf_cb, &args);
- return printed;
+ return args.printed;
}
-int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
+/*
+ * Find first map where end > map->start.
+ * Same as find_vma() in kernel.
+ */
+static struct rb_node *first_ending_after(struct maps *maps, const struct map *map)
{
struct rb_root *root;
struct rb_node *next, *first;
- int err = 0;
-
- down_write(maps__lock(maps));
root = maps__entries(maps);
-
- /*
- * Find first map where end > map->start.
- * Same as find_vma() in kernel.
- */
next = root->rb_node;
first = NULL;
while (next) {
@@ -301,8 +412,23 @@ int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
} else
next = next->rb_right;
}
+ return first;
+}
- next = first;
+/*
+ * Adds new to maps, if new overlaps existing entries then the existing maps are
+ * adjusted or removed so that new fits without overlapping any entries.
+ */
+int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
+{
+
+ struct rb_node *next;
+ int err = 0;
+ FILE *fp = debug_file();
+
+ down_write(maps__lock(maps));
+
+ next = first_ending_after(maps, new);
while (next && !err) {
struct map_rb_node *pos = rb_entry(next, struct map_rb_node, rb_node);
next = rb_next(&pos->rb_node);
@@ -311,27 +437,27 @@ int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
* Stop if current map starts after map->end.
* Maps are ordered by start: next will not overlap for sure.
*/
- if (map__start(pos->map) >= map__end(map))
+ if (map__start(pos->map) >= map__end(new))
break;
if (verbose >= 2) {
if (use_browser) {
pr_debug("overlapping maps in %s (disable tui for more info)\n",
- map__dso(map)->name);
+ map__dso(new)->name);
} else {
- fputs("overlapping maps:\n", fp);
- map__fprintf(map, fp);
+ pr_debug("overlapping maps:\n");
+ map__fprintf(new, fp);
map__fprintf(pos->map, fp);
}
}
- rb_erase_init(&pos->rb_node, root);
+ rb_erase_init(&pos->rb_node, maps__entries(maps));
/*
* Now check if we need to create new maps for areas not
* overlapped by the new map:
*/
- if (map__start(map) > map__start(pos->map)) {
+ if (map__start(new) > map__start(pos->map)) {
struct map *before = map__clone(pos->map);
if (before == NULL) {
@@ -339,7 +465,7 @@ int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
goto put_map;
}
- map__set_end(before, map__start(map));
+ map__set_end(before, map__start(new));
err = __maps__insert(maps, before);
if (err) {
map__put(before);
@@ -351,7 +477,7 @@ int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
map__put(before);
}
- if (map__end(map) < map__end(pos->map)) {
+ if (map__end(new) < map__end(pos->map)) {
struct map *after = map__clone(pos->map);
if (after == NULL) {
@@ -359,10 +485,10 @@ int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
goto put_map;
}
- map__set_start(after, map__end(map));
- map__add_pgoff(after, map__end(map) - map__start(pos->map));
- assert(map__map_ip(pos->map, map__end(map)) ==
- map__map_ip(after, map__end(map)));
+ map__set_start(after, map__end(new));
+ map__add_pgoff(after, map__end(new) - map__start(pos->map));
+ assert(map__map_ip(pos->map, map__end(new)) ==
+ map__map_ip(after, map__end(new)));
err = __maps__insert(maps, after);
if (err) {
map__put(after);
@@ -376,16 +502,14 @@ put_map:
map__put(pos->map);
free(pos);
}
+ /* Add the map. */
+ err = __maps__insert(maps, new);
up_write(maps__lock(maps));
return err;
}
-/*
- * XXX This should not really _copy_ te maps, but refcount them.
- */
-int maps__clone(struct thread *thread, struct maps *parent)
+int maps__copy_from(struct maps *maps, struct maps *parent)
{
- struct maps *maps = thread__maps(thread);
int err;
struct map_rb_node *rb_node;
@@ -416,17 +540,6 @@ out_unlock:
return err;
}
-struct map_rb_node *maps__find_node(struct maps *maps, struct map *map)
-{
- struct map_rb_node *rb_node;
-
- maps__for_each_entry(maps, rb_node) {
- if (rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map))
- return rb_node;
- }
- return NULL;
-}
-
struct map *maps__find(struct maps *maps, u64 ip)
{
struct rb_node *p;
@@ -452,26 +565,275 @@ out:
return m ? m->map : NULL;
}
-struct map_rb_node *maps__first(struct maps *maps)
+static int map__strcmp(const void *a, const void *b)
{
- struct rb_node *first = rb_first(maps__entries(maps));
+ const struct map *map_a = *(const struct map **)a;
+ const struct map *map_b = *(const struct map **)b;
+ const struct dso *dso_a = map__dso(map_a);
+ const struct dso *dso_b = map__dso(map_b);
+ int ret = strcmp(dso_a->short_name, dso_b->short_name);
- if (first)
- return rb_entry(first, struct map_rb_node, rb_node);
- return NULL;
+ if (ret == 0 && map_a != map_b) {
+ /*
+ * Ensure distinct but name equal maps have an order in part to
+ * aid reference counting.
+ */
+ ret = (int)map__start(map_a) - (int)map__start(map_b);
+ if (ret == 0)
+ ret = (int)((intptr_t)map_a - (intptr_t)map_b);
+ }
+
+ return ret;
}
-struct map_rb_node *map_rb_node__next(struct map_rb_node *node)
+static int map__strcmp_name(const void *name, const void *b)
{
- struct rb_node *next;
+ const struct dso *dso = map__dso(*(const struct map **)b);
- if (!node)
- return NULL;
+ return strcmp(name, dso->short_name);
+}
- next = rb_next(&node->rb_node);
+void __maps__sort_by_name(struct maps *maps)
+{
+ qsort(maps__maps_by_name(maps), maps__nr_maps(maps), sizeof(struct map *), map__strcmp);
+}
- if (!next)
+static int map__groups__sort_by_name_from_rbtree(struct maps *maps)
+{
+ struct map_rb_node *rb_node;
+ struct map **maps_by_name = realloc(maps__maps_by_name(maps),
+ maps__nr_maps(maps) * sizeof(struct map *));
+ int i = 0;
+
+ if (maps_by_name == NULL)
+ return -1;
+
+ up_read(maps__lock(maps));
+ down_write(maps__lock(maps));
+
+ RC_CHK_ACCESS(maps)->maps_by_name = maps_by_name;
+ RC_CHK_ACCESS(maps)->nr_maps_allocated = maps__nr_maps(maps);
+
+ maps__for_each_entry(maps, rb_node)
+ maps_by_name[i++] = map__get(rb_node->map);
+
+ __maps__sort_by_name(maps);
+
+ up_write(maps__lock(maps));
+ down_read(maps__lock(maps));
+
+ return 0;
+}
+
+static struct map *__maps__find_by_name(struct maps *maps, const char *name)
+{
+ struct map **mapp;
+
+ if (maps__maps_by_name(maps) == NULL &&
+ map__groups__sort_by_name_from_rbtree(maps))
return NULL;
- return rb_entry(next, struct map_rb_node, rb_node);
+ mapp = bsearch(name, maps__maps_by_name(maps), maps__nr_maps(maps),
+ sizeof(*mapp), map__strcmp_name);
+ if (mapp)
+ return *mapp;
+ return NULL;
+}
+
+struct map *maps__find_by_name(struct maps *maps, const char *name)
+{
+ struct map_rb_node *rb_node;
+ struct map *map;
+
+ down_read(maps__lock(maps));
+
+
+ if (RC_CHK_ACCESS(maps)->last_search_by_name) {
+ const struct dso *dso = map__dso(RC_CHK_ACCESS(maps)->last_search_by_name);
+
+ if (strcmp(dso->short_name, name) == 0) {
+ map = RC_CHK_ACCESS(maps)->last_search_by_name;
+ goto out_unlock;
+ }
+ }
+ /*
+ * If we have maps->maps_by_name, then the name isn't in the rbtree,
+ * as maps->maps_by_name mirrors the rbtree when lookups by name are
+ * made.
+ */
+ map = __maps__find_by_name(maps, name);
+ if (map || maps__maps_by_name(maps) != NULL)
+ goto out_unlock;
+
+ /* Fallback to traversing the rbtree... */
+ maps__for_each_entry(maps, rb_node) {
+ struct dso *dso;
+
+ map = rb_node->map;
+ dso = map__dso(map);
+ if (strcmp(dso->short_name, name) == 0) {
+ RC_CHK_ACCESS(maps)->last_search_by_name = map;
+ goto out_unlock;
+ }
+ }
+ map = NULL;
+
+out_unlock:
+ up_read(maps__lock(maps));
+ return map;
+}
+
+struct map *maps__find_next_entry(struct maps *maps, struct map *map)
+{
+ struct map_rb_node *rb_node = maps__find_node(maps, map);
+ struct map_rb_node *next = map_rb_node__next(rb_node);
+
+ if (next)
+ return next->map;
+
+ return NULL;
+}
+
+void maps__fixup_end(struct maps *maps)
+{
+ struct map_rb_node *prev = NULL, *curr;
+
+ down_write(maps__lock(maps));
+
+ maps__for_each_entry(maps, curr) {
+ if (prev && (!map__end(prev->map) || map__end(prev->map) > map__start(curr->map)))
+ map__set_end(prev->map, map__start(curr->map));
+
+ prev = curr;
+ }
+
+ /*
+ * We still haven't the actual symbols, so guess the
+ * last map final address.
+ */
+ if (curr && !map__end(curr->map))
+ map__set_end(curr->map, ~0ULL);
+
+ up_write(maps__lock(maps));
+}
+
+/*
+ * Merges map into maps by splitting the new map within the existing map
+ * regions.
+ */
+int maps__merge_in(struct maps *kmaps, struct map *new_map)
+{
+ struct map_rb_node *rb_node;
+ struct rb_node *first;
+ bool overlaps;
+ LIST_HEAD(merged);
+ int err = 0;
+
+ down_read(maps__lock(kmaps));
+ first = first_ending_after(kmaps, new_map);
+ rb_node = first ? rb_entry(first, struct map_rb_node, rb_node) : NULL;
+ overlaps = rb_node && map__start(rb_node->map) < map__end(new_map);
+ up_read(maps__lock(kmaps));
+
+ if (!overlaps)
+ return maps__insert(kmaps, new_map);
+
+ maps__for_each_entry(kmaps, rb_node) {
+ struct map *old_map = rb_node->map;
+
+ /* no overload with this one */
+ if (map__end(new_map) < map__start(old_map) ||
+ map__start(new_map) >= map__end(old_map))
+ continue;
+
+ if (map__start(new_map) < map__start(old_map)) {
+ /*
+ * |new......
+ * |old....
+ */
+ if (map__end(new_map) < map__end(old_map)) {
+ /*
+ * |new......| -> |new..|
+ * |old....| -> |old....|
+ */
+ map__set_end(new_map, map__start(old_map));
+ } else {
+ /*
+ * |new.............| -> |new..| |new..|
+ * |old....| -> |old....|
+ */
+ struct map_list_node *m = map_list_node__new();
+
+ if (!m) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ m->map = map__clone(new_map);
+ if (!m->map) {
+ free(m);
+ err = -ENOMEM;
+ goto out;
+ }
+
+ map__set_end(m->map, map__start(old_map));
+ list_add_tail(&m->node, &merged);
+ map__add_pgoff(new_map, map__end(old_map) - map__start(new_map));
+ map__set_start(new_map, map__end(old_map));
+ }
+ } else {
+ /*
+ * |new......
+ * |old....
+ */
+ if (map__end(new_map) < map__end(old_map)) {
+ /*
+ * |new..| -> x
+ * |old.........| -> |old.........|
+ */
+ map__put(new_map);
+ new_map = NULL;
+ break;
+ } else {
+ /*
+ * |new......| -> |new...|
+ * |old....| -> |old....|
+ */
+ map__add_pgoff(new_map, map__end(old_map) - map__start(new_map));
+ map__set_start(new_map, map__end(old_map));
+ }
+ }
+ }
+
+out:
+ while (!list_empty(&merged)) {
+ struct map_list_node *old_node;
+
+ old_node = list_entry(merged.next, struct map_list_node, node);
+ list_del_init(&old_node->node);
+ if (!err)
+ err = maps__insert(kmaps, old_node->map);
+ map__put(old_node->map);
+ free(old_node);
+ }
+
+ if (new_map) {
+ if (!err)
+ err = maps__insert(kmaps, new_map);
+ map__put(new_map);
+ }
+ return err;
+}
+
+void maps__load_first(struct maps *maps)
+{
+ struct map_rb_node *first;
+
+ down_read(maps__lock(maps));
+
+ first = maps__first(maps);
+ if (first)
+ map__load(first->map);
+
+ up_read(maps__lock(maps));
}