tools/perf/util/map.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include "symbol.h"
   3 #include <errno.h>
   4 #include <inttypes.h>
   5 #include <limits.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <stdio.h>
   9 #include <unistd.h>
  10 #include <uapi/linux/mman.h> /* To get things like MAP_HUGETLB even on older libc headers */
  11 #include "map.h"
  12 #include "thread.h"
  13 #include "vdso.h"
  14 #include "build-id.h"
  15 #include "util.h"
  16 #include "debug.h"
  17 #include "machine.h"
  18 #include <linux/string.h>
  19 #include "srcline.h"
  20 #include "namespaces.h"
  21 #include "unwind.h"
  22 #include "srccode.h"
  23
  24 static void __maps__insert(struct maps *maps, struct map *map);
  25 static void __maps__insert_name(struct maps *maps, struct map *map);
  26
  27 static inline int is_anon_memory(const char *filename, u32 flags)
  28 {
  29         return flags & MAP_HUGETLB ||
  30                !strcmp(filename, "//anon") ||
  31                !strncmp(filename, "/dev/zero", sizeof("/dev/zero") - 1) ||
  32                !strncmp(filename, "/anon_hugepage", sizeof("/anon_hugepage") - 1);
  33 }
  34
  35 static inline int is_no_dso_memory(const char *filename)
  36 {
  37         return !strncmp(filename, "[stack", 6) ||
  38                !strncmp(filename, "/SYSV",5)   ||
  39                !strcmp(filename, "[heap]");
  40 }
  41
  42 static inline int is_android_lib(const char *filename)
  43 {
  44         return !strncmp(filename, "/data/app-lib", 13) ||
  45                !strncmp(filename, "/system/lib", 11);
  46 }
  47
  48 static inline bool replace_android_lib(const char *filename, char *newfilename)
  49 {
  50         const char *libname;
  51         char *app_abi;
  52         size_t app_abi_length, new_length;
  53         size_t lib_length = 0;
  54
  55         libname  = strrchr(filename, '/');
  56         if (libname)
  57                 lib_length = strlen(libname);
  58
  59         app_abi = getenv("APP_ABI");
  60         if (!app_abi)
  61                 return false;
  62
  63         app_abi_length = strlen(app_abi);
  64
  65         if (!strncmp(filename, "/data/app-lib", 13)) {
  66                 char *apk_path;
  67
  68                 if (!app_abi_length)
  69                         return false;
  70
  71                 new_length = 7 + app_abi_length + lib_length;
  72
  73                 apk_path = getenv("APK_PATH");
  74                 if (apk_path) {
  75                         new_length += strlen(apk_path) + 1;
  76                         if (new_length > PATH_MAX)
  77                                 return false;
  78                         snprintf(newfilename, new_length,
  79                                  "%s/libs/%s/%s", apk_path, app_abi, libname);
  80                 } else {
  81                         if (new_length > PATH_MAX)
  82                                 return false;
  83                         snprintf(newfilename, new_length,
  84                                  "libs/%s/%s", app_abi, libname);
  85                 }
  86                 return true;
  87         }
  88
  89         if (!strncmp(filename, "/system/lib/", 11)) {
  90                 char *ndk, *app;
  91                 const char *arch;
  92                 size_t ndk_length;
  93                 size_t app_length;
  94
  95                 ndk = getenv("NDK_ROOT");
  96                 app = getenv("APP_PLATFORM");
  97
  98                 if (!(ndk && app))
  99                         return false;
 100
 101                 ndk_length = strlen(ndk);
 102                 app_length = strlen(app);
 103
 104                 if (!(ndk_length && app_length && app_abi_length))
 105                         return false;
 106
 107                 arch = !strncmp(app_abi, "arm", 3) ? "arm" :
 108                        !strncmp(app_abi, "mips", 4) ? "mips" :
 109                        !strncmp(app_abi, "x86", 3) ? "x86" : NULL;
 110
 111                 if (!arch)
 112                         return false;
 113
 114                 new_length = 27 + ndk_length +
 115                              app_length + lib_length
 116                            + strlen(arch);
 117
 118                 if (new_length > PATH_MAX)
 119                         return false;
 120                 snprintf(newfilename, new_length,
 121                         "%s/platforms/%s/arch-%s/usr/lib/%s",
 122                         ndk, app, arch, libname);
 123
 124                 return true;
 125         }
 126         return false;
 127 }
 128
 129 void map__init(struct map *map, u64 start, u64 end, u64 pgoff, struct dso *dso)
 130 {
 131         map->start    = start;
 132         map->end      = end;
 133         map->pgoff    = pgoff;
 134         map->reloc    = 0;
 135         map->dso      = dso__get(dso);
 136         map->map_ip   = map__map_ip;
 137         map->unmap_ip = map__unmap_ip;
 138         RB_CLEAR_NODE(&map->rb_node);
 139         map->groups   = NULL;
 140         map->erange_warned = false;
 141         refcount_set(&map->refcnt, 1);
 142 }
 143
 144 struct map *map__new(struct machine *machine, u64 start, u64 len,
 145                      u64 pgoff, u32 d_maj, u32 d_min, u64 ino,
 146                      u64 ino_gen, u32 prot, u32 flags, char *filename,
 147                      struct thread *thread)
 148 {
 149         struct map *map = malloc(sizeof(*map));
 150         struct nsinfo *nsi = NULL;
 151         struct nsinfo *nnsi;
 152
 153         if (map != NULL) {
 154                 char newfilename[PATH_MAX];
 155                 struct dso *dso;
 156                 int anon, no_dso, vdso, android;
 157
 158                 android = is_android_lib(filename);
 159                 anon = is_anon_memory(filename, flags);
 160                 vdso = is_vdso_map(filename);
 161                 no_dso = is_no_dso_memory(filename);
 162
 163                 map->maj = d_maj;
 164                 map->min = d_min;
 165                 map->ino = ino;
 166                 map->ino_generation = ino_gen;
 167                 map->prot = prot;
 168                 map->flags = flags;
 169                 nsi = nsinfo__get(thread->nsinfo);
 170
 171                 if ((anon || no_dso) && nsi && (prot & PROT_EXEC)) {
 172                         snprintf(newfilename, sizeof(newfilename),
 173                                  "/tmp/perf-%d.map", nsi->pid);
 174                         filename = newfilename;
 175                 }
 176
 177                 if (android) {
 178                         if (replace_android_lib(filename, newfilename))
 179                                 filename = newfilename;
 180                 }
 181
 182                 if (vdso) {
 183                         /* The vdso maps are always on the host and not the
 184                          * container.  Ensure that we don't use setns to look
 185                          * them up.
 186                          */
 187                         nnsi = nsinfo__copy(nsi);
 188                         if (nnsi) {
 189                                 nsinfo__put(nsi);
 190                                 nnsi->need_setns = false;
 191                                 nsi = nnsi;
 192                         }
 193                         pgoff = 0;
 194                         dso = machine__findnew_vdso(machine, thread);
 195                 } else
 196                         dso = machine__findnew_dso(machine, filename);
 197
 198                 if (dso == NULL)
 199                         goto out_delete;
 200
 201                 map__init(map, start, start + len, pgoff, dso);
 202
 203                 if (anon || no_dso) {
 204                         map->map_ip = map->unmap_ip = identity__map_ip;
 205
 206                         /*
 207                          * Set memory without DSO as loaded. All map__find_*
 208                          * functions still return NULL, and we avoid the
 209                          * unnecessary map__load warning.
 210                          */
 211                         if (!(prot & PROT_EXEC))
 212                                 dso__set_loaded(dso);
 213                 }
 214                 dso->nsinfo = nsi;
 215                 dso__put(dso);
 216         }
 217         return map;
 218 out_delete:
 219         nsinfo__put(nsi);
 220         free(map);
 221         return NULL;
 222 }
 223
 224 /*
 225  * Constructor variant for modules (where we know from /proc/modules where
 226  * they are loaded) and for vmlinux, where only after we load all the
 227  * symbols we'll know where it starts and ends.
 228  */
 229 struct map *map__new2(u64 start, struct dso *dso)
 230 {
 231         struct map *map = calloc(1, (sizeof(*map) +
 232                                      (dso->kernel ? sizeof(struct kmap) : 0)));
 233         if (map != NULL) {
 234                 /*
 235                  * ->end will be filled after we load all the symbols
 236                  */
 237                 map__init(map, start, 0, 0, dso);
 238         }
 239
 240         return map;
 241 }
 242
 243 /*
 244  * Use this and __map__is_kmodule() for map instances that are in
 245  * machine->kmaps, and thus have map->groups->machine all properly set, to
 246  * disambiguate between the kernel and modules.
 247  *
 248  * When the need arises, introduce map__is_{kernel,kmodule)() that
 249  * checks (map->groups != NULL && map->groups->machine != NULL &&
 250  * map->dso->kernel) before calling __map__is_{kernel,kmodule}())
 251  */
 252 bool __map__is_kernel(const struct map *map)
 253 {
 254         return machine__kernel_map(map->groups->machine) == map;
 255 }
 256
 257 bool __map__is_extra_kernel_map(const struct map *map)
 258 {
 259         struct kmap *kmap = __map__kmap((struct map *)map);
 260
 261         return kmap && kmap->name[0];
 262 }
 263
 264 bool map__has_symbols(const struct map *map)
 265 {
 266         return dso__has_symbols(map->dso);
 267 }
 268
 269 static void map__exit(struct map *map)
 270 {
 271         BUG_ON(!RB_EMPTY_NODE(&map->rb_node));
 272         dso__zput(map->dso);
 273 }
 274
 275 void map__delete(struct map *map)
 276 {
 277         map__exit(map);
 278         free(map);
 279 }
 280
 281 void map__put(struct map *map)
 282 {
 283         if (map && refcount_dec_and_test(&map->refcnt))
 284                 map__delete(map);
 285 }
 286
 287 void map__fixup_start(struct map *map)
 288 {
 289         struct rb_root_cached *symbols = &map->dso->symbols;
 290         struct rb_node *nd = rb_first_cached(symbols);
 291         if (nd != NULL) {
 292                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 293                 map->start = sym->start;
 294         }
 295 }
 296
 297 void map__fixup_end(struct map *map)
 298 {
 299         struct rb_root_cached *symbols = &map->dso->symbols;
 300         struct rb_node *nd = rb_last(&symbols->rb_root);
 301         if (nd != NULL) {
 302                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 303                 map->end = sym->end;
 304         }
 305 }
 306
 307 #define DSO__DELETED "(deleted)"
 308
 309 int map__load(struct map *map)
 310 {
 311         const char *name = map->dso->long_name;
 312         int nr;
 313
 314         if (dso__loaded(map->dso))
 315                 return 0;
 316
 317         nr = dso__load(map->dso, map);
 318         if (nr < 0) {
 319                 if (map->dso->has_build_id) {
 320                         char sbuild_id[SBUILD_ID_SIZE];
 321
 322                         build_id__sprintf(map->dso->build_id,
 323                                           sizeof(map->dso->build_id),
 324                                           sbuild_id);
 325                         pr_debug("%s with build id %s not found", name, sbuild_id);
 326                 } else
 327                         pr_debug("Failed to open %s", name);
 328
 329                 pr_debug(", continuing without symbols\n");
 330                 return -1;
 331         } else if (nr == 0) {
 332 #ifdef HAVE_LIBELF_SUPPORT
 333                 const size_t len = strlen(name);
 334                 const size_t real_len = len - sizeof(DSO__DELETED);
 335
 336                 if (len > sizeof(DSO__DELETED) &&
 337                     strcmp(name + real_len + 1, DSO__DELETED) == 0) {
 338                         pr_debug("%.*s was updated (is prelink enabled?). "
 339                                 "Restart the long running apps that use it!\n",
 340                                    (int)real_len, name);
 341                 } else {
 342                         pr_debug("no symbols found in %s, maybe install a debug package?\n", name);
 343                 }
 344 #endif
 345                 return -1;
 346         }
 347
 348         return 0;
 349 }
 350
 351 struct symbol *map__find_symbol(struct map *map, u64 addr)
 352 {
 353         if (map__load(map) < 0)
 354                 return NULL;
 355
 356         return dso__find_symbol(map->dso, addr);
 357 }
 358
 359 struct symbol *map__find_symbol_by_name(struct map *map, const char *name)
 360 {
 361         if (map__load(map) < 0)
 362                 return NULL;
 363
 364         if (!dso__sorted_by_name(map->dso))
 365                 dso__sort_by_name(map->dso);
 366
 367         return dso__find_symbol_by_name(map->dso, name);
 368 }
 369
 370 struct map *map__clone(struct map *from)
 371 {
 372         struct map *map = memdup(from, sizeof(*map));
 373
 374         if (map != NULL) {
 375                 refcount_set(&map->refcnt, 1);
 376                 RB_CLEAR_NODE(&map->rb_node);
 377                 dso__get(map->dso);
 378                 map->groups = NULL;
 379         }
 380
 381         return map;
 382 }
 383
 384 size_t map__fprintf(struct map *map, FILE *fp)
 385 {
 386         return fprintf(fp, " %" PRIx64 "-%" PRIx64 " %" PRIx64 " %s\n",
 387                        map->start, map->end, map->pgoff, map->dso->name);
 388 }
 389
 390 size_t map__fprintf_dsoname(struct map *map, FILE *fp)
 391 {
 392         const char *dsoname = "[unknown]";
 393
 394         if (map && map->dso) {
 395                 if (symbol_conf.show_kernel_path && map->dso->long_name)
 396                         dsoname = map->dso->long_name;
 397                 else
 398                         dsoname = map->dso->name;
 399         }
 400
 401         return fprintf(fp, "%s", dsoname);
 402 }
 403
 404 char *map__srcline(struct map *map, u64 addr, struct symbol *sym)
 405 {
 406         if (map == NULL)
 407                 return SRCLINE_UNKNOWN;
 408         return get_srcline(map->dso, map__rip_2objdump(map, addr), sym, true, true, addr);
 409 }
 410
 411 int map__fprintf_srcline(struct map *map, u64 addr, const char *prefix,
 412                          FILE *fp)
 413 {
 414         int ret = 0;
 415
 416         if (map && map->dso) {
 417                 char *srcline = map__srcline(map, addr, NULL);
 418                 if (srcline != SRCLINE_UNKNOWN)
 419                         ret = fprintf(fp, "%s%s", prefix, srcline);
 420                 free_srcline(srcline);
 421         }
 422         return ret;
 423 }
 424
 425 int map__fprintf_srccode(struct map *map, u64 addr,
 426                          FILE *fp,
 427                          struct srccode_state *state)
 428 {
 429         char *srcfile;
 430         int ret = 0;
 431         unsigned line;
 432         int len;
 433         char *srccode;
 434
 435         if (!map || !map->dso)
 436                 return 0;
 437         srcfile = get_srcline_split(map->dso,
 438                                     map__rip_2objdump(map, addr),
 439                                     &line);
 440         if (!srcfile)
 441                 return 0;
 442
 443         /* Avoid redundant printing */
 444         if (state &&
 445             state->srcfile &&
 446             !strcmp(state->srcfile, srcfile) &&
 447             state->line == line) {
 448                 free(srcfile);
 449                 return 0;
 450         }
 451
 452         srccode = find_sourceline(srcfile, line, &len);
 453         if (!srccode)
 454                 goto out_free_line;
 455
 456         ret = fprintf(fp, "|%-8d %.*s", line, len, srccode);
 457         state->srcfile = srcfile;
 458         state->line = line;
 459         return ret;
 460
 461 out_free_line:
 462         free(srcfile);
 463         return ret;
 464 }
 465
 466
 467 void srccode_state_free(struct srccode_state *state)
 468 {
 469         zfree(&state->srcfile);
 470         state->line = 0;
 471 }
 472
 473 /**
 474  * map__rip_2objdump - convert symbol start address to objdump address.
 475  * @map: memory map
 476  * @rip: symbol start address
 477  *
 478  * objdump wants/reports absolute IPs for ET_EXEC, and RIPs for ET_DYN.
 479  * map->dso->adjust_symbols==1 for ET_EXEC-like cases except ET_REL which is
 480  * relative to section start.
 481  *
 482  * Return: Address suitable for passing to "objdump --start-address="
 483  */
 484 u64 map__rip_2objdump(struct map *map, u64 rip)
 485 {
 486         struct kmap *kmap = __map__kmap(map);
 487
 488         /*
 489          * vmlinux does not have program headers for PTI entry trampolines and
 490          * kcore may not either. However the trampoline object code is on the
 491          * main kernel map, so just use that instead.
 492          */
 493         if (kmap && is_entry_trampoline(kmap->name) && kmap->kmaps && kmap->kmaps->machine) {
 494                 struct map *kernel_map = machine__kernel_map(kmap->kmaps->machine);
 495
 496                 if (kernel_map)
 497                         map = kernel_map;
 498         }
 499
 500         if (!map->dso->adjust_symbols)
 501                 return rip;
 502
 503         if (map->dso->rel)
 504                 return rip - map->pgoff;
 505
 506         /*
 507          * kernel modules also have DSO_TYPE_USER in dso->kernel,
 508          * but all kernel modules are ET_REL, so won't get here.
 509          */
 510         if (map->dso->kernel == DSO_TYPE_USER)
 511                 return rip + map->dso->text_offset;
 512
 513         return map->unmap_ip(map, rip) - map->reloc;
 514 }
 515
 516 /**
 517  * map__objdump_2mem - convert objdump address to a memory address.
 518  * @map: memory map
 519  * @ip: objdump address
 520  *
 521  * Closely related to map__rip_2objdump(), this function takes an address from
 522  * objdump and converts it to a memory address.  Note this assumes that @map
 523  * contains the address.  To be sure the result is valid, check it forwards
 524  * e.g. map__rip_2objdump(map->map_ip(map, map__objdump_2mem(map, ip))) == ip
 525  *
 526  * Return: Memory address.
 527  */
 528 u64 map__objdump_2mem(struct map *map, u64 ip)
 529 {
 530         if (!map->dso->adjust_symbols)
 531                 return map->unmap_ip(map, ip);
 532
 533         if (map->dso->rel)
 534                 return map->unmap_ip(map, ip + map->pgoff);
 535
 536         /*
 537          * kernel modules also have DSO_TYPE_USER in dso->kernel,
 538          * but all kernel modules are ET_REL, so won't get here.
 539          */
 540         if (map->dso->kernel == DSO_TYPE_USER)
 541                 return map->unmap_ip(map, ip - map->dso->text_offset);
 542
 543         return ip + map->reloc;
 544 }
 545
 546 static void maps__init(struct maps *maps)
 547 {
 548         maps->entries = RB_ROOT;
 549         maps->names = RB_ROOT;
 550         init_rwsem(&maps->lock);
 551 }
 552
 553 void map_groups__init(struct map_groups *mg, struct machine *machine)
 554 {
 555         maps__init(&mg->maps);
 556         mg->machine = machine;
 557         refcount_set(&mg->refcnt, 1);
 558 }
 559
 560 void map_groups__insert(struct map_groups *mg, struct map *map)
 561 {
 562         maps__insert(&mg->maps, map);
 563         map->groups = mg;
 564 }
 565
 566 static void __maps__purge(struct maps *maps)
 567 {
 568         struct rb_root *root = &maps->entries;
 569         struct rb_node *next = rb_first(root);
 570
 571         while (next) {
 572                 struct map *pos = rb_entry(next, struct map, rb_node);
 573
 574                 next = rb_next(&pos->rb_node);
 575                 rb_erase_init(&pos->rb_node, root);
 576                 map__put(pos);
 577         }
 578 }
 579
 580 static void maps__exit(struct maps *maps)
 581 {
 582         down_write(&maps->lock);
 583         __maps__purge(maps);
 584         up_write(&maps->lock);
 585 }
 586
 587 void map_groups__exit(struct map_groups *mg)
 588 {
 589         maps__exit(&mg->maps);
 590 }
 591
 592 bool map_groups__empty(struct map_groups *mg)
 593 {
 594         return !maps__first(&mg->maps);
 595 }
 596
 597 struct map_groups *map_groups__new(struct machine *machine)
 598 {
 599         struct map_groups *mg = malloc(sizeof(*mg));
 600
 601         if (mg != NULL)
 602                 map_groups__init(mg, machine);
 603
 604         return mg;
 605 }
 606
 607 void map_groups__delete(struct map_groups *mg)
 608 {
 609         map_groups__exit(mg);
 610         free(mg);
 611 }
 612
 613 void map_groups__put(struct map_groups *mg)
 614 {
 615         if (mg && refcount_dec_and_test(&mg->refcnt))
 616                 map_groups__delete(mg);
 617 }
 618
 619 struct symbol *map_groups__find_symbol(struct map_groups *mg,
 620                                        u64 addr, struct map **mapp)
 621 {
 622         struct map *map = map_groups__find(mg, addr);
 623
 624         /* Ensure map is loaded before using map->map_ip */
 625         if (map != NULL && map__load(map) >= 0) {
 626                 if (mapp != NULL)
 627                         *mapp = map;
 628                 return map__find_symbol(map, map->map_ip(map, addr));
 629         }
 630
 631         return NULL;
 632 }
 633
 634 static bool map__contains_symbol(struct map *map, struct symbol *sym)
 635 {
 636         u64 ip = map->unmap_ip(map, sym->start);
 637
 638         return ip >= map->start && ip < map->end;
 639 }
 640
 641 struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name,
 642                                          struct map **mapp)
 643 {
 644         struct symbol *sym;
 645         struct rb_node *nd;
 646
 647         down_read(&maps->lock);
 648
 649         for (nd = rb_first(&maps->entries); nd; nd = rb_next(nd)) {
 650                 struct map *pos = rb_entry(nd, struct map, rb_node);
 651
 652                 sym = map__find_symbol_by_name(pos, name);
 653
 654                 if (sym == NULL)
 655                         continue;
 656                 if (!map__contains_symbol(pos, sym)) {
 657                         sym = NULL;
 658                         continue;
 659                 }
 660                 if (mapp != NULL)
 661                         *mapp = pos;
 662                 goto out;
 663         }
 664
 665         sym = NULL;
 666 out:
 667         up_read(&maps->lock);
 668         return sym;
 669 }
 670
 671 struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
 672                                                const char *name,
 673                                                struct map **mapp)
 674 {
 675         return maps__find_symbol_by_name(&mg->maps, name, mapp);
 676 }
 677
 678 int map_groups__find_ams(struct addr_map_symbol *ams)
 679 {
 680         if (ams->addr < ams->map->start || ams->addr >= ams->map->end) {
 681                 if (ams->map->groups == NULL)
 682                         return -1;
 683                 ams->map = map_groups__find(ams->map->groups, ams->addr);
 684                 if (ams->map == NULL)
 685                         return -1;
 686         }
 687
 688         ams->al_addr = ams->map->map_ip(ams->map, ams->addr);
 689         ams->sym = map__find_symbol(ams->map, ams->al_addr);
 690
 691         return ams->sym ? 0 : -1;
 692 }
 693
 694 static size_t maps__fprintf(struct maps *maps, FILE *fp)
 695 {
 696         size_t printed = 0;
 697         struct rb_node *nd;
 698
 699         down_read(&maps->lock);
 700
 701         for (nd = rb_first(&maps->entries); nd; nd = rb_next(nd)) {
 702                 struct map *pos = rb_entry(nd, struct map, rb_node);
 703                 printed += fprintf(fp, "Map:");
 704                 printed += map__fprintf(pos, fp);
 705                 if (verbose > 2) {
 706                         printed += dso__fprintf(pos->dso, fp);
 707                         printed += fprintf(fp, "--\n");
 708                 }
 709         }
 710
 711         up_read(&maps->lock);
 712
 713         return printed;
 714 }
 715
 716 size_t map_groups__fprintf(struct map_groups *mg, FILE *fp)
 717 {
 718         return maps__fprintf(&mg->maps, fp);
 719 }
 720
 721 static void __map_groups__insert(struct map_groups *mg, struct map *map)
 722 {
 723         __maps__insert(&mg->maps, map);
 724         __maps__insert_name(&mg->maps, map);
 725         map->groups = mg;
 726 }
 727
 728 static int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
 729 {
 730         struct rb_root *root;
 731         struct rb_node *next, *first;
 732         int err = 0;
 733
 734         down_write(&maps->lock);
 735
 736         root = &maps->entries;
 737
 738         /*
 739          * Find first map where end > map->start.
 740          * Same as find_vma() in kernel.
 741          */
 742         next = root->rb_node;
 743         first = NULL;
 744         while (next) {
 745                 struct map *pos = rb_entry(next, struct map, rb_node);
 746
 747                 if (pos->end > map->start) {
 748                         first = next;
 749                         if (pos->start <= map->start)
 750                                 break;
 751                         next = next->rb_left;
 752                 } else
 753                         next = next->rb_right;
 754         }
 755
 756         next = first;
 757         while (next) {
 758                 struct map *pos = rb_entry(next, struct map, rb_node);
 759                 next = rb_next(&pos->rb_node);
 760
 761                 /*
 762                  * Stop if current map starts after map->end.
 763                  * Maps are ordered by start: next will not overlap for sure.
 764                  */
 765                 if (pos->start >= map->end)
 766                         break;
 767
 768                 if (verbose >= 2) {
 769
 770                         if (use_browser) {
 771                                 pr_debug("overlapping maps in %s (disable tui for more info)\n",
 772                                            map->dso->name);
 773                         } else {
 774                                 fputs("overlapping maps:\n", fp);
 775                                 map__fprintf(map, fp);
 776                                 map__fprintf(pos, fp);
 777                         }
 778                 }
 779
 780                 rb_erase_init(&pos->rb_node, root);
 781                 /*
 782                  * Now check if we need to create new maps for areas not
 783                  * overlapped by the new map:
 784                  */
 785                 if (map->start > pos->start) {
 786                         struct map *before = map__clone(pos);
 787
 788                         if (before == NULL) {
 789                                 err = -ENOMEM;
 790                                 goto put_map;
 791                         }
 792
 793                         before->end = map->start;
 794                         __map_groups__insert(pos->groups, before);
 795                         if (verbose >= 2 && !use_browser)
 796                                 map__fprintf(before, fp);
 797                         map__put(before);
 798                 }
 799
 800                 if (map->end < pos->end) {
 801                         struct map *after = map__clone(pos);
 802
 803                         if (after == NULL) {
 804                                 err = -ENOMEM;
 805                                 goto put_map;
 806                         }
 807
 808                         after->start = map->end;
 809                         __map_groups__insert(pos->groups, after);
 810                         if (verbose >= 2 && !use_browser)
 811                                 map__fprintf(after, fp);
 812                         map__put(after);
 813                 }
 814 put_map:
 815                 map__put(pos);
 816
 817                 if (err)
 818                         goto out;
 819         }
 820
 821         err = 0;
 822 out:
 823         up_write(&maps->lock);
 824         return err;
 825 }
 826
 827 int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 828                                    FILE *fp)
 829 {
 830         return maps__fixup_overlappings(&mg->maps, map, fp);
 831 }
 832
 833 /*
 834  * XXX This should not really _copy_ te maps, but refcount them.
 835  */
 836 int map_groups__clone(struct thread *thread, struct map_groups *parent)
 837 {
 838         struct map_groups *mg = thread->mg;
 839         int err = -ENOMEM;
 840         struct map *map;
 841         struct maps *maps = &parent->maps;
 842
 843         down_read(&maps->lock);
 844
 845         for (map = maps__first(maps); map; map = map__next(map)) {
 846                 struct map *new = map__clone(map);
 847                 if (new == NULL)
 848                         goto out_unlock;
 849
 850                 err = unwind__prepare_access(thread, new, NULL);
 851                 if (err)
 852                         goto out_unlock;
 853
 854                 map_groups__insert(mg, new);
 855                 map__put(new);
 856         }
 857
 858         err = 0;
 859 out_unlock:
 860         up_read(&maps->lock);
 861         return err;
 862 }
 863
 864 static void __maps__insert(struct maps *maps, struct map *map)
 865 {
 866         struct rb_node **p = &maps->entries.rb_node;
 867         struct rb_node *parent = NULL;
 868         const u64 ip = map->start;
 869         struct map *m;
 870
 871         while (*p != NULL) {
 872                 parent = *p;
 873                 m = rb_entry(parent, struct map, rb_node);
 874                 if (ip < m->start)
 875                         p = &(*p)->rb_left;
 876                 else
 877                         p = &(*p)->rb_right;
 878         }
 879
 880         rb_link_node(&map->rb_node, parent, p);
 881         rb_insert_color(&map->rb_node, &maps->entries);
 882         map__get(map);
 883 }
 884
 885 static void __maps__insert_name(struct maps *maps, struct map *map)
 886 {
 887         struct rb_node **p = &maps->names.rb_node;
 888         struct rb_node *parent = NULL;
 889         struct map *m;
 890         int rc;
 891
 892         while (*p != NULL) {
 893                 parent = *p;
 894                 m = rb_entry(parent, struct map, rb_node_name);
 895                 rc = strcmp(m->dso->short_name, map->dso->short_name);
 896                 if (rc < 0)
 897                         p = &(*p)->rb_left;
 898                 else if (rc  > 0)
 899                         p = &(*p)->rb_right;
 900                 else
 901                         return;
 902         }
 903         rb_link_node(&map->rb_node_name, parent, p);
 904         rb_insert_color(&map->rb_node_name, &maps->names);
 905         map__get(map);
 906 }
 907
 908 void maps__insert(struct maps *maps, struct map *map)
 909 {
 910         down_write(&maps->lock);
 911         __maps__insert(maps, map);
 912         __maps__insert_name(maps, map);
 913         up_write(&maps->lock);
 914 }
 915
 916 static void __maps__remove(struct maps *maps, struct map *map)
 917 {
 918         rb_erase_init(&map->rb_node, &maps->entries);
 919         map__put(map);
 920 }
 921
 922 void maps__remove(struct maps *maps, struct map *map)
 923 {
 924         down_write(&maps->lock);
 925         __maps__remove(maps, map);
 926         up_write(&maps->lock);
 927 }
 928
 929 struct map *maps__find(struct maps *maps, u64 ip)
 930 {
 931         struct rb_node *p;
 932         struct map *m;
 933
 934         down_read(&maps->lock);
 935
 936         p = maps->entries.rb_node;
 937         while (p != NULL) {
 938                 m = rb_entry(p, struct map, rb_node);
 939                 if (ip < m->start)
 940                         p = p->rb_left;
 941                 else if (ip >= m->end)
 942                         p = p->rb_right;
 943                 else
 944                         goto out;
 945         }
 946
 947         m = NULL;
 948 out:
 949         up_read(&maps->lock);
 950         return m;
 951 }
 952
 953 struct map *maps__first(struct maps *maps)
 954 {
 955         struct rb_node *first = rb_first(&maps->entries);
 956
 957         if (first)
 958                 return rb_entry(first, struct map, rb_node);
 959         return NULL;
 960 }
 961
 962 struct map *map__next(struct map *map)
 963 {
 964         struct rb_node *next = rb_next(&map->rb_node);
 965
 966         if (next)
 967                 return rb_entry(next, struct map, rb_node);
 968         return NULL;
 969 }
 970
 971 struct kmap *__map__kmap(struct map *map)
 972 {
 973         if (!map->dso || !map->dso->kernel)
 974                 return NULL;
 975         return (struct kmap *)(map + 1);
 976 }
 977
 978 struct kmap *map__kmap(struct map *map)
 979 {
 980         struct kmap *kmap = __map__kmap(map);
 981
 982         if (!kmap)
 983                 pr_err("Internal error: map__kmap with a non-kernel map\n");
 984         return kmap;
 985 }
 986
 987 struct map_groups *map__kmaps(struct map *map)
 988 {
 989         struct kmap *kmap = map__kmap(map);
 990
 991         if (!kmap || !kmap->kmaps) {
 992                 pr_err("Internal error: map__kmaps with a non-kernel map\n");
 993                 return NULL;
 994         }
 995         return kmap->kmaps;
 996 }