tools/perf/util/map.c

   1 #include "symbol.h"
   2 #include <errno.h>
   3 #include <inttypes.h>
   4 #include <limits.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <stdio.h>
   8 #include <unistd.h>
   9 #include "map.h"
  10 #include "thread.h"
  11 #include "strlist.h"
  12 #include "vdso.h"
  13 #include "build-id.h"
  14 #include <linux/string.h>
  15
  16 const char *map_type__name[MAP__NR_TYPES] = {
  17         [MAP__FUNCTION] = "Functions",
  18         [MAP__VARIABLE] = "Variables",
  19 };
  20
  21 static inline int is_anon_memory(const char *filename)
  22 {
  23         return !strcmp(filename, "//anon") ||
  24                !strcmp(filename, "/dev/zero (deleted)") ||
  25                !strcmp(filename, "/anon_hugepage (deleted)");
  26 }
  27
  28 static inline int is_no_dso_memory(const char *filename)
  29 {
  30         return !strncmp(filename, "[stack", 6) ||
  31                !strcmp(filename, "[heap]");
  32 }
  33
  34 void map__init(struct map *map, enum map_type type,
  35                u64 start, u64 end, u64 pgoff, struct dso *dso)
  36 {
  37         map->type     = type;
  38         map->start    = start;
  39         map->end      = end;
  40         map->pgoff    = pgoff;
  41         map->dso      = dso;
  42         map->map_ip   = map__map_ip;
  43         map->unmap_ip = map__unmap_ip;
  44         RB_CLEAR_NODE(&map->rb_node);
  45         map->groups   = NULL;
  46         map->referenced = false;
  47         map->erange_warned = false;
  48 }
  49
  50 struct map *map__new(struct list_head *dsos__list, u64 start, u64 len,
  51                      u64 pgoff, u32 pid, char *filename,
  52                      enum map_type type)
  53 {
  54         struct map *map = malloc(sizeof(*map));
  55
  56         if (map != NULL) {
  57                 char newfilename[PATH_MAX];
  58                 struct dso *dso;
  59                 int anon, no_dso, vdso;
  60
  61                 anon = is_anon_memory(filename);
  62                 vdso = is_vdso_map(filename);
  63                 no_dso = is_no_dso_memory(filename);
  64
  65                 if (anon) {
  66                         snprintf(newfilename, sizeof(newfilename), "/tmp/perf-%d.map", pid);
  67                         filename = newfilename;
  68                 }
  69
  70                 if (vdso) {
  71                         pgoff = 0;
  72                         dso = vdso__dso_findnew(dsos__list);
  73                 } else
  74                         dso = __dsos__findnew(dsos__list, filename);
  75
  76                 if (dso == NULL)
  77                         goto out_delete;
  78
  79                 map__init(map, type, start, start + len, pgoff, dso);
  80
  81                 if (anon || no_dso) {
  82                         map->map_ip = map->unmap_ip = identity__map_ip;
  83
  84                         /*
  85                          * Set memory without DSO as loaded. All map__find_*
  86                          * functions still return NULL, and we avoid the
  87                          * unnecessary map__load warning.
  88                          */
  89                         if (no_dso)
  90                                 dso__set_loaded(dso, map->type);
  91                 }
  92         }
  93         return map;
  94 out_delete:
  95         free(map);
  96         return NULL;
  97 }
  98
  99 /*
 100  * Constructor variant for modules (where we know from /proc/modules where
 101  * they are loaded) and for vmlinux, where only after we load all the
 102  * symbols we'll know where it starts and ends.
 103  */
 104 struct map *map__new2(u64 start, struct dso *dso, enum map_type type)
 105 {
 106         struct map *map = calloc(1, (sizeof(*map) +
 107                                      (dso->kernel ? sizeof(struct kmap) : 0)));
 108         if (map != NULL) {
 109                 /*
 110                  * ->end will be filled after we load all the symbols
 111                  */
 112                 map__init(map, type, start, 0, 0, dso);
 113         }
 114
 115         return map;
 116 }
 117
 118 void map__delete(struct map *map)
 119 {
 120         free(map);
 121 }
 122
 123 void map__fixup_start(struct map *map)
 124 {
 125         struct rb_root *symbols = &map->dso->symbols[map->type];
 126         struct rb_node *nd = rb_first(symbols);
 127         if (nd != NULL) {
 128                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 129                 map->start = sym->start;
 130         }
 131 }
 132
 133 void map__fixup_end(struct map *map)
 134 {
 135         struct rb_root *symbols = &map->dso->symbols[map->type];
 136         struct rb_node *nd = rb_last(symbols);
 137         if (nd != NULL) {
 138                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 139                 map->end = sym->end;
 140         }
 141 }
 142
 143 #define DSO__DELETED "(deleted)"
 144
 145 int map__load(struct map *map, symbol_filter_t filter)
 146 {
 147         const char *name = map->dso->long_name;
 148         int nr;
 149
 150         if (dso__loaded(map->dso, map->type))
 151                 return 0;
 152
 153         nr = dso__load(map->dso, map, filter);
 154         if (nr < 0) {
 155                 if (map->dso->has_build_id) {
 156                         char sbuild_id[BUILD_ID_SIZE * 2 + 1];
 157
 158                         build_id__sprintf(map->dso->build_id,
 159                                           sizeof(map->dso->build_id),
 160                                           sbuild_id);
 161                         pr_warning("%s with build id %s not found",
 162                                    name, sbuild_id);
 163                 } else
 164                         pr_warning("Failed to open %s", name);
 165
 166                 pr_warning(", continuing without symbols\n");
 167                 return -1;
 168         } else if (nr == 0) {
 169 #ifdef LIBELF_SUPPORT
 170                 const size_t len = strlen(name);
 171                 const size_t real_len = len - sizeof(DSO__DELETED);
 172
 173                 if (len > sizeof(DSO__DELETED) &&
 174                     strcmp(name + real_len + 1, DSO__DELETED) == 0) {
 175                         pr_warning("%.*s was updated (is prelink enabled?). "
 176                                 "Restart the long running apps that use it!\n",
 177                                    (int)real_len, name);
 178                 } else {
 179                         pr_warning("no symbols found in %s, maybe install "
 180                                    "a debug package?\n", name);
 181                 }
 182 #endif
 183                 return -1;
 184         }
 185
 186         return 0;
 187 }
 188
 189 struct symbol *map__find_symbol(struct map *map, u64 addr,
 190                                 symbol_filter_t filter)
 191 {
 192         if (map__load(map, filter) < 0)
 193                 return NULL;
 194
 195         return dso__find_symbol(map->dso, map->type, addr);
 196 }
 197
 198 struct symbol *map__find_symbol_by_name(struct map *map, const char *name,
 199                                         symbol_filter_t filter)
 200 {
 201         if (map__load(map, filter) < 0)
 202                 return NULL;
 203
 204         if (!dso__sorted_by_name(map->dso, map->type))
 205                 dso__sort_by_name(map->dso, map->type);
 206
 207         return dso__find_symbol_by_name(map->dso, map->type, name);
 208 }
 209
 210 struct map *map__clone(struct map *map)
 211 {
 212         return memdup(map, sizeof(*map));
 213 }
 214
 215 int map__overlap(struct map *l, struct map *r)
 216 {
 217         if (l->start > r->start) {
 218                 struct map *t = l;
 219                 l = r;
 220                 r = t;
 221         }
 222
 223         if (l->end > r->start)
 224                 return 1;
 225
 226         return 0;
 227 }
 228
 229 size_t map__fprintf(struct map *map, FILE *fp)
 230 {
 231         return fprintf(fp, " %" PRIx64 "-%" PRIx64 " %" PRIx64 " %s\n",
 232                        map->start, map->end, map->pgoff, map->dso->name);
 233 }
 234
 235 size_t map__fprintf_dsoname(struct map *map, FILE *fp)
 236 {
 237         const char *dsoname = "[unknown]";
 238
 239         if (map && map->dso && (map->dso->name || map->dso->long_name)) {
 240                 if (symbol_conf.show_kernel_path && map->dso->long_name)
 241                         dsoname = map->dso->long_name;
 242                 else if (map->dso->name)
 243                         dsoname = map->dso->name;
 244         }
 245
 246         return fprintf(fp, "%s", dsoname);
 247 }
 248
 249 /*
 250  * objdump wants/reports absolute IPs for ET_EXEC, and RIPs for ET_DYN.
 251  * map->dso->adjust_symbols==1 for ET_EXEC-like cases except ET_REL which is
 252  * relative to section start.
 253  */
 254 u64 map__rip_2objdump(struct map *map, u64 rip)
 255 {
 256         if (!map->dso->adjust_symbols)
 257                 return rip;
 258
 259         if (map->dso->rel)
 260                 return rip - map->pgoff;
 261
 262         return map->unmap_ip(map, rip);
 263 }
 264
 265 void map_groups__init(struct map_groups *mg)
 266 {
 267         int i;
 268         for (i = 0; i < MAP__NR_TYPES; ++i) {
 269                 mg->maps[i] = RB_ROOT;
 270                 INIT_LIST_HEAD(&mg->removed_maps[i]);
 271         }
 272         mg->machine = NULL;
 273 }
 274
 275 static void maps__delete(struct rb_root *maps)
 276 {
 277         struct rb_node *next = rb_first(maps);
 278
 279         while (next) {
 280                 struct map *pos = rb_entry(next, struct map, rb_node);
 281
 282                 next = rb_next(&pos->rb_node);
 283                 rb_erase(&pos->rb_node, maps);
 284                 map__delete(pos);
 285         }
 286 }
 287
 288 static void maps__delete_removed(struct list_head *maps)
 289 {
 290         struct map *pos, *n;
 291
 292         list_for_each_entry_safe(pos, n, maps, node) {
 293                 list_del(&pos->node);
 294                 map__delete(pos);
 295         }
 296 }
 297
 298 void map_groups__exit(struct map_groups *mg)
 299 {
 300         int i;
 301
 302         for (i = 0; i < MAP__NR_TYPES; ++i) {
 303                 maps__delete(&mg->maps[i]);
 304                 maps__delete_removed(&mg->removed_maps[i]);
 305         }
 306 }
 307
 308 void map_groups__flush(struct map_groups *mg)
 309 {
 310         int type;
 311
 312         for (type = 0; type < MAP__NR_TYPES; type++) {
 313                 struct rb_root *root = &mg->maps[type];
 314                 struct rb_node *next = rb_first(root);
 315
 316                 while (next) {
 317                         struct map *pos = rb_entry(next, struct map, rb_node);
 318                         next = rb_next(&pos->rb_node);
 319                         rb_erase(&pos->rb_node, root);
 320                         /*
 321                          * We may have references to this map, for
 322                          * instance in some hist_entry instances, so
 323                          * just move them to a separate list.
 324                          */
 325                         list_add_tail(&pos->node, &mg->removed_maps[pos->type]);
 326                 }
 327         }
 328 }
 329
 330 struct symbol *map_groups__find_symbol(struct map_groups *mg,
 331                                        enum map_type type, u64 addr,
 332                                        struct map **mapp,
 333                                        symbol_filter_t filter)
 334 {
 335         struct map *map = map_groups__find(mg, type, addr);
 336
 337         if (map != NULL) {
 338                 if (mapp != NULL)
 339                         *mapp = map;
 340                 return map__find_symbol(map, map->map_ip(map, addr), filter);
 341         }
 342
 343         return NULL;
 344 }
 345
 346 struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
 347                                                enum map_type type,
 348                                                const char *name,
 349                                                struct map **mapp,
 350                                                symbol_filter_t filter)
 351 {
 352         struct rb_node *nd;
 353
 354         for (nd = rb_first(&mg->maps[type]); nd; nd = rb_next(nd)) {
 355                 struct map *pos = rb_entry(nd, struct map, rb_node);
 356                 struct symbol *sym = map__find_symbol_by_name(pos, name, filter);
 357
 358                 if (sym == NULL)
 359                         continue;
 360                 if (mapp != NULL)
 361                         *mapp = pos;
 362                 return sym;
 363         }
 364
 365         return NULL;
 366 }
 367
 368 size_t __map_groups__fprintf_maps(struct map_groups *mg,
 369                                   enum map_type type, int verbose, FILE *fp)
 370 {
 371         size_t printed = fprintf(fp, "%s:\n", map_type__name[type]);
 372         struct rb_node *nd;
 373
 374         for (nd = rb_first(&mg->maps[type]); nd; nd = rb_next(nd)) {
 375                 struct map *pos = rb_entry(nd, struct map, rb_node);
 376                 printed += fprintf(fp, "Map:");
 377                 printed += map__fprintf(pos, fp);
 378                 if (verbose > 2) {
 379                         printed += dso__fprintf(pos->dso, type, fp);
 380                         printed += fprintf(fp, "--\n");
 381                 }
 382         }
 383
 384         return printed;
 385 }
 386
 387 size_t map_groups__fprintf_maps(struct map_groups *mg, int verbose, FILE *fp)
 388 {
 389         size_t printed = 0, i;
 390         for (i = 0; i < MAP__NR_TYPES; ++i)
 391                 printed += __map_groups__fprintf_maps(mg, i, verbose, fp);
 392         return printed;
 393 }
 394
 395 static size_t __map_groups__fprintf_removed_maps(struct map_groups *mg,
 396                                                  enum map_type type,
 397                                                  int verbose, FILE *fp)
 398 {
 399         struct map *pos;
 400         size_t printed = 0;
 401
 402         list_for_each_entry(pos, &mg->removed_maps[type], node) {
 403                 printed += fprintf(fp, "Map:");
 404                 printed += map__fprintf(pos, fp);
 405                 if (verbose > 1) {
 406                         printed += dso__fprintf(pos->dso, type, fp);
 407                         printed += fprintf(fp, "--\n");
 408                 }
 409         }
 410         return printed;
 411 }
 412
 413 static size_t map_groups__fprintf_removed_maps(struct map_groups *mg,
 414                                                int verbose, FILE *fp)
 415 {
 416         size_t printed = 0, i;
 417         for (i = 0; i < MAP__NR_TYPES; ++i)
 418                 printed += __map_groups__fprintf_removed_maps(mg, i, verbose, fp);
 419         return printed;
 420 }
 421
 422 size_t map_groups__fprintf(struct map_groups *mg, int verbose, FILE *fp)
 423 {
 424         size_t printed = map_groups__fprintf_maps(mg, verbose, fp);
 425         printed += fprintf(fp, "Removed maps:\n");
 426         return printed + map_groups__fprintf_removed_maps(mg, verbose, fp);
 427 }
 428
 429 int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 430                                    int verbose, FILE *fp)
 431 {
 432         struct rb_root *root = &mg->maps[map->type];
 433         struct rb_node *next = rb_first(root);
 434         int err = 0;
 435
 436         while (next) {
 437                 struct map *pos = rb_entry(next, struct map, rb_node);
 438                 next = rb_next(&pos->rb_node);
 439
 440                 if (!map__overlap(pos, map))
 441                         continue;
 442
 443                 if (verbose >= 2) {
 444                         fputs("overlapping maps:\n", fp);
 445                         map__fprintf(map, fp);
 446                         map__fprintf(pos, fp);
 447                 }
 448
 449                 rb_erase(&pos->rb_node, root);
 450                 /*
 451                  * Now check if we need to create new maps for areas not
 452                  * overlapped by the new map:
 453                  */
 454                 if (map->start > pos->start) {
 455                         struct map *before = map__clone(pos);
 456
 457                         if (before == NULL) {
 458                                 err = -ENOMEM;
 459                                 goto move_map;
 460                         }
 461
 462                         before->end = map->start - 1;
 463                         map_groups__insert(mg, before);
 464                         if (verbose >= 2)
 465                                 map__fprintf(before, fp);
 466                 }
 467
 468                 if (map->end < pos->end) {
 469                         struct map *after = map__clone(pos);
 470
 471                         if (after == NULL) {
 472                                 err = -ENOMEM;
 473                                 goto move_map;
 474                         }
 475
 476                         after->start = map->end + 1;
 477                         map_groups__insert(mg, after);
 478                         if (verbose >= 2)
 479                                 map__fprintf(after, fp);
 480                 }
 481 move_map:
 482                 /*
 483                  * If we have references, just move them to a separate list.
 484                  */
 485                 if (pos->referenced)
 486                         list_add_tail(&pos->node, &mg->removed_maps[map->type]);
 487                 else
 488                         map__delete(pos);
 489
 490                 if (err)
 491                         return err;
 492         }
 493
 494         return 0;
 495 }
 496
 497 /*
 498  * XXX This should not really _copy_ te maps, but refcount them.
 499  */
 500 int map_groups__clone(struct map_groups *mg,
 501                       struct map_groups *parent, enum map_type type)
 502 {
 503         struct rb_node *nd;
 504         for (nd = rb_first(&parent->maps[type]); nd; nd = rb_next(nd)) {
 505                 struct map *map = rb_entry(nd, struct map, rb_node);
 506                 struct map *new = map__clone(map);
 507                 if (new == NULL)
 508                         return -ENOMEM;
 509                 map_groups__insert(mg, new);
 510         }
 511         return 0;
 512 }
 513
 514 void maps__insert(struct rb_root *maps, struct map *map)
 515 {
 516         struct rb_node **p = &maps->rb_node;
 517         struct rb_node *parent = NULL;
 518         const u64 ip = map->start;
 519         struct map *m;
 520
 521         while (*p != NULL) {
 522                 parent = *p;
 523                 m = rb_entry(parent, struct map, rb_node);
 524                 if (ip < m->start)
 525                         p = &(*p)->rb_left;
 526                 else
 527                         p = &(*p)->rb_right;
 528         }
 529
 530         rb_link_node(&map->rb_node, parent, p);
 531         rb_insert_color(&map->rb_node, maps);
 532 }
 533
 534 void maps__remove(struct rb_root *maps, struct map *map)
 535 {
 536         rb_erase(&map->rb_node, maps);
 537 }
 538
 539 struct map *maps__find(struct rb_root *maps, u64 ip)
 540 {
 541         struct rb_node **p = &maps->rb_node;
 542         struct rb_node *parent = NULL;
 543         struct map *m;
 544
 545         while (*p != NULL) {
 546                 parent = *p;
 547                 m = rb_entry(parent, struct map, rb_node);
 548                 if (ip < m->start)
 549                         p = &(*p)->rb_left;
 550                 else if (ip > m->end)
 551                         p = &(*p)->rb_right;
 552                 else
 553                         return m;
 554         }
 555
 556         return NULL;
 557 }
 558
 559 struct map *maps__first(struct rb_root *maps)
 560 {
 561         struct rb_node *first = rb_first(maps);
 562
 563         if (first)
 564                 return rb_entry(first, struct map, rb_node);
 565         return NULL;
 566 }
 567
 568 struct map *maps__next(struct map *map)
 569 {
 570         struct rb_node *next = rb_next(&map->rb_node);
 571
 572         if (next)
 573                 return rb_entry(next, struct map, rb_node);
 574         return NULL;
 575 }