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 "util.h"
  15 #include <linux/string.h>
  16
  17 const char *map_type__name[MAP__NR_TYPES] = {
  18         [MAP__FUNCTION] = "Functions",
  19         [MAP__VARIABLE] = "Variables",
  20 };
  21
  22 static inline int is_anon_memory(const char *filename)
  23 {
  24         return !strcmp(filename, "//anon") ||
  25                !strcmp(filename, "/dev/zero (deleted)") ||
  26                !strcmp(filename, "/anon_hugepage (deleted)");
  27 }
  28
  29 static inline int is_no_dso_memory(const char *filename)
  30 {
  31         return !strncmp(filename, "[stack", 6) ||
  32                !strcmp(filename, "[heap]");
  33 }
  34
  35 static inline int is_android_lib(const char *filename)
  36 {
  37         return !strncmp(filename, "/data/app-lib", 13) ||
  38                !strncmp(filename, "/system/lib", 11);
  39 }
  40
  41 static inline bool replace_android_lib(const char *filename, char *newfilename)
  42 {
  43         const char *libname;
  44         char *app_abi;
  45         size_t app_abi_length, new_length;
  46         size_t lib_length = 0;
  47
  48         libname  = strrchr(filename, '/');
  49         if (libname)
  50                 lib_length = strlen(libname);
  51
  52         app_abi = getenv("APP_ABI");
  53         if (!app_abi)
  54                 return false;
  55
  56         app_abi_length = strlen(app_abi);
  57
  58         if (!strncmp(filename, "/data/app-lib", 13)) {
  59                 char *apk_path;
  60
  61                 if (!app_abi_length)
  62                         return false;
  63
  64                 new_length = 7 + app_abi_length + lib_length;
  65
  66                 apk_path = getenv("APK_PATH");
  67                 if (apk_path) {
  68                         new_length += strlen(apk_path) + 1;
  69                         if (new_length > PATH_MAX)
  70                                 return false;
  71                         snprintf(newfilename, new_length,
  72                                  "%s/libs/%s/%s", apk_path, app_abi, libname);
  73                 } else {
  74                         if (new_length > PATH_MAX)
  75                                 return false;
  76                         snprintf(newfilename, new_length,
  77                                  "libs/%s/%s", app_abi, libname);
  78                 }
  79                 return true;
  80         }
  81
  82         if (!strncmp(filename, "/system/lib/", 11)) {
  83                 char *ndk, *app;
  84                 const char *arch;
  85                 size_t ndk_length;
  86                 size_t app_length;
  87
  88                 ndk = getenv("NDK_ROOT");
  89                 app = getenv("APP_PLATFORM");
  90
  91                 if (!(ndk && app))
  92                         return false;
  93
  94                 ndk_length = strlen(ndk);
  95                 app_length = strlen(app);
  96
  97                 if (!(ndk_length && app_length && app_abi_length))
  98                         return false;
  99
 100                 arch = !strncmp(app_abi, "arm", 3) ? "arm" :
 101                        !strncmp(app_abi, "mips", 4) ? "mips" :
 102                        !strncmp(app_abi, "x86", 3) ? "x86" : NULL;
 103
 104                 if (!arch)
 105                         return false;
 106
 107                 new_length = 27 + ndk_length +
 108                              app_length + lib_length
 109                            + strlen(arch);
 110
 111                 if (new_length > PATH_MAX)
 112                         return false;
 113                 snprintf(newfilename, new_length,
 114                         "%s/platforms/%s/arch-%s/usr/lib/%s",
 115                         ndk, app, arch, libname);
 116
 117                 return true;
 118         }
 119         return false;
 120 }
 121
 122 void map__init(struct map *map, enum map_type type,
 123                u64 start, u64 end, u64 pgoff, struct dso *dso)
 124 {
 125         map->type     = type;
 126         map->start    = start;
 127         map->end      = end;
 128         map->pgoff    = pgoff;
 129         map->reloc    = 0;
 130         map->dso      = dso;
 131         map->map_ip   = map__map_ip;
 132         map->unmap_ip = map__unmap_ip;
 133         RB_CLEAR_NODE(&map->rb_node);
 134         map->groups   = NULL;
 135         map->referenced = false;
 136         map->erange_warned = false;
 137 }
 138
 139 struct map *map__new(struct list_head *dsos__list, u64 start, u64 len,
 140                      u64 pgoff, u32 pid, u32 d_maj, u32 d_min, u64 ino,
 141                      u64 ino_gen, u32 prot, u32 flags, char *filename,
 142                      enum map_type type)
 143 {
 144         struct map *map = malloc(sizeof(*map));
 145
 146         if (map != NULL) {
 147                 char newfilename[PATH_MAX];
 148                 struct dso *dso;
 149                 int anon, no_dso, vdso, android;
 150
 151                 android = is_android_lib(filename);
 152                 anon = is_anon_memory(filename);
 153                 vdso = is_vdso_map(filename);
 154                 no_dso = is_no_dso_memory(filename);
 155
 156                 map->maj = d_maj;
 157                 map->min = d_min;
 158                 map->ino = ino;
 159                 map->ino_generation = ino_gen;
 160                 map->prot = prot;
 161                 map->flags = flags;
 162
 163                 if ((anon || no_dso) && type == MAP__FUNCTION) {
 164                         snprintf(newfilename, sizeof(newfilename), "/tmp/perf-%d.map", pid);
 165                         filename = newfilename;
 166                 }
 167
 168                 if (android) {
 169                         if (replace_android_lib(filename, newfilename))
 170                                 filename = newfilename;
 171                 }
 172
 173                 if (vdso) {
 174                         pgoff = 0;
 175                         dso = vdso__dso_findnew(dsos__list);
 176                 } else
 177                         dso = __dsos__findnew(dsos__list, filename);
 178
 179                 if (dso == NULL)
 180                         goto out_delete;
 181
 182                 map__init(map, type, start, start + len, pgoff, dso);
 183
 184                 if (anon || no_dso) {
 185                         map->map_ip = map->unmap_ip = identity__map_ip;
 186
 187                         /*
 188                          * Set memory without DSO as loaded. All map__find_*
 189                          * functions still return NULL, and we avoid the
 190                          * unnecessary map__load warning.
 191                          */
 192                         if (type != MAP__FUNCTION)
 193                                 dso__set_loaded(dso, map->type);
 194                 }
 195         }
 196         return map;
 197 out_delete:
 198         free(map);
 199         return NULL;
 200 }
 201
 202 /*
 203  * Constructor variant for modules (where we know from /proc/modules where
 204  * they are loaded) and for vmlinux, where only after we load all the
 205  * symbols we'll know where it starts and ends.
 206  */
 207 struct map *map__new2(u64 start, struct dso *dso, enum map_type type)
 208 {
 209         struct map *map = calloc(1, (sizeof(*map) +
 210                                      (dso->kernel ? sizeof(struct kmap) : 0)));
 211         if (map != NULL) {
 212                 /*
 213                  * ->end will be filled after we load all the symbols
 214                  */
 215                 map__init(map, type, start, 0, 0, dso);
 216         }
 217
 218         return map;
 219 }
 220
 221 void map__delete(struct map *map)
 222 {
 223         free(map);
 224 }
 225
 226 void map__fixup_start(struct map *map)
 227 {
 228         struct rb_root *symbols = &map->dso->symbols[map->type];
 229         struct rb_node *nd = rb_first(symbols);
 230         if (nd != NULL) {
 231                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 232                 map->start = sym->start;
 233         }
 234 }
 235
 236 void map__fixup_end(struct map *map)
 237 {
 238         struct rb_root *symbols = &map->dso->symbols[map->type];
 239         struct rb_node *nd = rb_last(symbols);
 240         if (nd != NULL) {
 241                 struct symbol *sym = rb_entry(nd, struct symbol, rb_node);
 242                 map->end = sym->end;
 243         }
 244 }
 245
 246 #define DSO__DELETED "(deleted)"
 247
 248 int map__load(struct map *map, symbol_filter_t filter)
 249 {
 250         const char *name = map->dso->long_name;
 251         int nr;
 252
 253         if (dso__loaded(map->dso, map->type))
 254                 return 0;
 255
 256         nr = dso__load(map->dso, map, filter);
 257         if (nr < 0) {
 258                 if (map->dso->has_build_id) {
 259                         char sbuild_id[BUILD_ID_SIZE * 2 + 1];
 260
 261                         build_id__sprintf(map->dso->build_id,
 262                                           sizeof(map->dso->build_id),
 263                                           sbuild_id);
 264                         pr_warning("%s with build id %s not found",
 265                                    name, sbuild_id);
 266                 } else
 267                         pr_warning("Failed to open %s", name);
 268
 269                 pr_warning(", continuing without symbols\n");
 270                 return -1;
 271         } else if (nr == 0) {
 272 #ifdef HAVE_LIBELF_SUPPORT
 273                 const size_t len = strlen(name);
 274                 const size_t real_len = len - sizeof(DSO__DELETED);
 275
 276                 if (len > sizeof(DSO__DELETED) &&
 277                     strcmp(name + real_len + 1, DSO__DELETED) == 0) {
 278                         pr_warning("%.*s was updated (is prelink enabled?). "
 279                                 "Restart the long running apps that use it!\n",
 280                                    (int)real_len, name);
 281                 } else {
 282                         pr_warning("no symbols found in %s, maybe install "
 283                                    "a debug package?\n", name);
 284                 }
 285 #endif
 286                 return -1;
 287         }
 288
 289         return 0;
 290 }
 291
 292 struct symbol *map__find_symbol(struct map *map, u64 addr,
 293                                 symbol_filter_t filter)
 294 {
 295         if (map__load(map, filter) < 0)
 296                 return NULL;
 297
 298         return dso__find_symbol(map->dso, map->type, addr);
 299 }
 300
 301 struct symbol *map__find_symbol_by_name(struct map *map, const char *name,
 302                                         symbol_filter_t filter)
 303 {
 304         if (map__load(map, filter) < 0)
 305                 return NULL;
 306
 307         if (!dso__sorted_by_name(map->dso, map->type))
 308                 dso__sort_by_name(map->dso, map->type);
 309
 310         return dso__find_symbol_by_name(map->dso, map->type, name);
 311 }
 312
 313 struct map *map__clone(struct map *map)
 314 {
 315         return memdup(map, sizeof(*map));
 316 }
 317
 318 int map__overlap(struct map *l, struct map *r)
 319 {
 320         if (l->start > r->start) {
 321                 struct map *t = l;
 322                 l = r;
 323                 r = t;
 324         }
 325
 326         if (l->end > r->start)
 327                 return 1;
 328
 329         return 0;
 330 }
 331
 332 size_t map__fprintf(struct map *map, FILE *fp)
 333 {
 334         return fprintf(fp, " %" PRIx64 "-%" PRIx64 " %" PRIx64 " %s\n",
 335                        map->start, map->end, map->pgoff, map->dso->name);
 336 }
 337
 338 size_t map__fprintf_dsoname(struct map *map, FILE *fp)
 339 {
 340         const char *dsoname = "[unknown]";
 341
 342         if (map && map->dso && (map->dso->name || map->dso->long_name)) {
 343                 if (symbol_conf.show_kernel_path && map->dso->long_name)
 344                         dsoname = map->dso->long_name;
 345                 else if (map->dso->name)
 346                         dsoname = map->dso->name;
 347         }
 348
 349         return fprintf(fp, "%s", dsoname);
 350 }
 351
 352 int map__fprintf_srcline(struct map *map, u64 addr, const char *prefix,
 353                          FILE *fp)
 354 {
 355         char *srcline;
 356         int ret = 0;
 357
 358         if (map && map->dso) {
 359                 srcline = get_srcline(map->dso,
 360                                       map__rip_2objdump(map, addr));
 361                 if (srcline != SRCLINE_UNKNOWN)
 362                         ret = fprintf(fp, "%s%s", prefix, srcline);
 363                 free_srcline(srcline);
 364         }
 365         return ret;
 366 }
 367
 368 /**
 369  * map__rip_2objdump - convert symbol start address to objdump address.
 370  * @map: memory map
 371  * @rip: symbol start address
 372  *
 373  * objdump wants/reports absolute IPs for ET_EXEC, and RIPs for ET_DYN.
 374  * map->dso->adjust_symbols==1 for ET_EXEC-like cases except ET_REL which is
 375  * relative to section start.
 376  *
 377  * Return: Address suitable for passing to "objdump --start-address="
 378  */
 379 u64 map__rip_2objdump(struct map *map, u64 rip)
 380 {
 381         if (!map->dso->adjust_symbols)
 382                 return rip;
 383
 384         if (map->dso->rel)
 385                 return rip - map->pgoff;
 386
 387         return map->unmap_ip(map, rip) - map->reloc;
 388 }
 389
 390 /**
 391  * map__objdump_2mem - convert objdump address to a memory address.
 392  * @map: memory map
 393  * @ip: objdump address
 394  *
 395  * Closely related to map__rip_2objdump(), this function takes an address from
 396  * objdump and converts it to a memory address.  Note this assumes that @map
 397  * contains the address.  To be sure the result is valid, check it forwards
 398  * e.g. map__rip_2objdump(map->map_ip(map, map__objdump_2mem(map, ip))) == ip
 399  *
 400  * Return: Memory address.
 401  */
 402 u64 map__objdump_2mem(struct map *map, u64 ip)
 403 {
 404         if (!map->dso->adjust_symbols)
 405                 return map->unmap_ip(map, ip);
 406
 407         if (map->dso->rel)
 408                 return map->unmap_ip(map, ip + map->pgoff);
 409
 410         return ip + map->reloc;
 411 }
 412
 413 void map_groups__init(struct map_groups *mg)
 414 {
 415         int i;
 416         for (i = 0; i < MAP__NR_TYPES; ++i) {
 417                 mg->maps[i] = RB_ROOT;
 418                 INIT_LIST_HEAD(&mg->removed_maps[i]);
 419         }
 420         mg->machine = NULL;
 421         mg->refcnt = 1;
 422 }
 423
 424 static void maps__delete(struct rb_root *maps)
 425 {
 426         struct rb_node *next = rb_first(maps);
 427
 428         while (next) {
 429                 struct map *pos = rb_entry(next, struct map, rb_node);
 430
 431                 next = rb_next(&pos->rb_node);
 432                 rb_erase(&pos->rb_node, maps);
 433                 map__delete(pos);
 434         }
 435 }
 436
 437 static void maps__delete_removed(struct list_head *maps)
 438 {
 439         struct map *pos, *n;
 440
 441         list_for_each_entry_safe(pos, n, maps, node) {
 442                 list_del(&pos->node);
 443                 map__delete(pos);
 444         }
 445 }
 446
 447 void map_groups__exit(struct map_groups *mg)
 448 {
 449         int i;
 450
 451         for (i = 0; i < MAP__NR_TYPES; ++i) {
 452                 maps__delete(&mg->maps[i]);
 453                 maps__delete_removed(&mg->removed_maps[i]);
 454         }
 455 }
 456
 457 struct map_groups *map_groups__new(void)
 458 {
 459         struct map_groups *mg = malloc(sizeof(*mg));
 460
 461         if (mg != NULL)
 462                 map_groups__init(mg);
 463
 464         return mg;
 465 }
 466
 467 void map_groups__delete(struct map_groups *mg)
 468 {
 469         map_groups__exit(mg);
 470         free(mg);
 471 }
 472
 473 void map_groups__put(struct map_groups *mg)
 474 {
 475         if (--mg->refcnt == 0)
 476                 map_groups__delete(mg);
 477 }
 478
 479 void map_groups__flush(struct map_groups *mg)
 480 {
 481         int type;
 482
 483         for (type = 0; type < MAP__NR_TYPES; type++) {
 484                 struct rb_root *root = &mg->maps[type];
 485                 struct rb_node *next = rb_first(root);
 486
 487                 while (next) {
 488                         struct map *pos = rb_entry(next, struct map, rb_node);
 489                         next = rb_next(&pos->rb_node);
 490                         rb_erase(&pos->rb_node, root);
 491                         /*
 492                          * We may have references to this map, for
 493                          * instance in some hist_entry instances, so
 494                          * just move them to a separate list.
 495                          */
 496                         list_add_tail(&pos->node, &mg->removed_maps[pos->type]);
 497                 }
 498         }
 499 }
 500
 501 struct symbol *map_groups__find_symbol(struct map_groups *mg,
 502                                        enum map_type type, u64 addr,
 503                                        struct map **mapp,
 504                                        symbol_filter_t filter)
 505 {
 506         struct map *map = map_groups__find(mg, type, addr);
 507
 508         /* Ensure map is loaded before using map->map_ip */
 509         if (map != NULL && map__load(map, filter) >= 0) {
 510                 if (mapp != NULL)
 511                         *mapp = map;
 512                 return map__find_symbol(map, map->map_ip(map, addr), filter);
 513         }
 514
 515         return NULL;
 516 }
 517
 518 struct symbol *map_groups__find_symbol_by_name(struct map_groups *mg,
 519                                                enum map_type type,
 520                                                const char *name,
 521                                                struct map **mapp,
 522                                                symbol_filter_t filter)
 523 {
 524         struct rb_node *nd;
 525
 526         for (nd = rb_first(&mg->maps[type]); nd; nd = rb_next(nd)) {
 527                 struct map *pos = rb_entry(nd, struct map, rb_node);
 528                 struct symbol *sym = map__find_symbol_by_name(pos, name, filter);
 529
 530                 if (sym == NULL)
 531                         continue;
 532                 if (mapp != NULL)
 533                         *mapp = pos;
 534                 return sym;
 535         }
 536
 537         return NULL;
 538 }
 539
 540 int map_groups__find_ams(struct addr_map_symbol *ams, symbol_filter_t filter)
 541 {
 542         if (ams->addr < ams->map->start || ams->addr > ams->map->end) {
 543                 if (ams->map->groups == NULL)
 544                         return -1;
 545                 ams->map = map_groups__find(ams->map->groups, ams->map->type,
 546                                             ams->addr);
 547                 if (ams->map == NULL)
 548                         return -1;
 549         }
 550
 551         ams->al_addr = ams->map->map_ip(ams->map, ams->addr);
 552         ams->sym = map__find_symbol(ams->map, ams->al_addr, filter);
 553
 554         return ams->sym ? 0 : -1;
 555 }
 556
 557 size_t __map_groups__fprintf_maps(struct map_groups *mg,
 558                                   enum map_type type, int verbose, FILE *fp)
 559 {
 560         size_t printed = fprintf(fp, "%s:\n", map_type__name[type]);
 561         struct rb_node *nd;
 562
 563         for (nd = rb_first(&mg->maps[type]); nd; nd = rb_next(nd)) {
 564                 struct map *pos = rb_entry(nd, struct map, rb_node);
 565                 printed += fprintf(fp, "Map:");
 566                 printed += map__fprintf(pos, fp);
 567                 if (verbose > 2) {
 568                         printed += dso__fprintf(pos->dso, type, fp);
 569                         printed += fprintf(fp, "--\n");
 570                 }
 571         }
 572
 573         return printed;
 574 }
 575
 576 size_t map_groups__fprintf_maps(struct map_groups *mg, int verbose, FILE *fp)
 577 {
 578         size_t printed = 0, i;
 579         for (i = 0; i < MAP__NR_TYPES; ++i)
 580                 printed += __map_groups__fprintf_maps(mg, i, verbose, fp);
 581         return printed;
 582 }
 583
 584 static size_t __map_groups__fprintf_removed_maps(struct map_groups *mg,
 585                                                  enum map_type type,
 586                                                  int verbose, FILE *fp)
 587 {
 588         struct map *pos;
 589         size_t printed = 0;
 590
 591         list_for_each_entry(pos, &mg->removed_maps[type], node) {
 592                 printed += fprintf(fp, "Map:");
 593                 printed += map__fprintf(pos, fp);
 594                 if (verbose > 1) {
 595                         printed += dso__fprintf(pos->dso, type, fp);
 596                         printed += fprintf(fp, "--\n");
 597                 }
 598         }
 599         return printed;
 600 }
 601
 602 static size_t map_groups__fprintf_removed_maps(struct map_groups *mg,
 603                                                int verbose, FILE *fp)
 604 {
 605         size_t printed = 0, i;
 606         for (i = 0; i < MAP__NR_TYPES; ++i)
 607                 printed += __map_groups__fprintf_removed_maps(mg, i, verbose, fp);
 608         return printed;
 609 }
 610
 611 size_t map_groups__fprintf(struct map_groups *mg, int verbose, FILE *fp)
 612 {
 613         size_t printed = map_groups__fprintf_maps(mg, verbose, fp);
 614         printed += fprintf(fp, "Removed maps:\n");
 615         return printed + map_groups__fprintf_removed_maps(mg, verbose, fp);
 616 }
 617
 618 int map_groups__fixup_overlappings(struct map_groups *mg, struct map *map,
 619                                    int verbose, FILE *fp)
 620 {
 621         struct rb_root *root = &mg->maps[map->type];
 622         struct rb_node *next = rb_first(root);
 623         int err = 0;
 624
 625         while (next) {
 626                 struct map *pos = rb_entry(next, struct map, rb_node);
 627                 next = rb_next(&pos->rb_node);
 628
 629                 if (!map__overlap(pos, map))
 630                         continue;
 631
 632                 if (verbose >= 2) {
 633                         fputs("overlapping maps:\n", fp);
 634                         map__fprintf(map, fp);
 635                         map__fprintf(pos, fp);
 636                 }
 637
 638                 rb_erase(&pos->rb_node, root);
 639                 /*
 640                  * Now check if we need to create new maps for areas not
 641                  * overlapped by the new map:
 642                  */
 643                 if (map->start > pos->start) {
 644                         struct map *before = map__clone(pos);
 645
 646                         if (before == NULL) {
 647                                 err = -ENOMEM;
 648                                 goto move_map;
 649                         }
 650
 651                         before->end = map->start - 1;
 652                         map_groups__insert(mg, before);
 653                         if (verbose >= 2)
 654                                 map__fprintf(before, fp);
 655                 }
 656
 657                 if (map->end < pos->end) {
 658                         struct map *after = map__clone(pos);
 659
 660                         if (after == NULL) {
 661                                 err = -ENOMEM;
 662                                 goto move_map;
 663                         }
 664
 665                         after->start = map->end + 1;
 666                         map_groups__insert(mg, after);
 667                         if (verbose >= 2)
 668                                 map__fprintf(after, fp);
 669                 }
 670 move_map:
 671                 /*
 672                  * If we have references, just move them to a separate list.
 673                  */
 674                 if (pos->referenced)
 675                         list_add_tail(&pos->node, &mg->removed_maps[map->type]);
 676                 else
 677                         map__delete(pos);
 678
 679                 if (err)
 680                         return err;
 681         }
 682
 683         return 0;
 684 }
 685
 686 /*
 687  * XXX This should not really _copy_ te maps, but refcount them.
 688  */
 689 int map_groups__clone(struct map_groups *mg,
 690                       struct map_groups *parent, enum map_type type)
 691 {
 692         struct rb_node *nd;
 693         for (nd = rb_first(&parent->maps[type]); nd; nd = rb_next(nd)) {
 694                 struct map *map = rb_entry(nd, struct map, rb_node);
 695                 struct map *new = map__clone(map);
 696                 if (new == NULL)
 697                         return -ENOMEM;
 698                 map_groups__insert(mg, new);
 699         }
 700         return 0;
 701 }
 702
 703 void maps__insert(struct rb_root *maps, struct map *map)
 704 {
 705         struct rb_node **p = &maps->rb_node;
 706         struct rb_node *parent = NULL;
 707         const u64 ip = map->start;
 708         struct map *m;
 709
 710         while (*p != NULL) {
 711                 parent = *p;
 712                 m = rb_entry(parent, struct map, rb_node);
 713                 if (ip < m->start)
 714                         p = &(*p)->rb_left;
 715                 else
 716                         p = &(*p)->rb_right;
 717         }
 718
 719         rb_link_node(&map->rb_node, parent, p);
 720         rb_insert_color(&map->rb_node, maps);
 721 }
 722
 723 void maps__remove(struct rb_root *maps, struct map *map)
 724 {
 725         rb_erase(&map->rb_node, maps);
 726 }
 727
 728 struct map *maps__find(struct rb_root *maps, u64 ip)
 729 {
 730         struct rb_node **p = &maps->rb_node;
 731         struct rb_node *parent = NULL;
 732         struct map *m;
 733
 734         while (*p != NULL) {
 735                 parent = *p;
 736                 m = rb_entry(parent, struct map, rb_node);
 737                 if (ip < m->start)
 738                         p = &(*p)->rb_left;
 739                 else if (ip > m->end)
 740                         p = &(*p)->rb_right;
 741                 else
 742                         return m;
 743         }
 744
 745         return NULL;
 746 }
 747
 748 struct map *maps__first(struct rb_root *maps)
 749 {
 750         struct rb_node *first = rb_first(maps);
 751
 752         if (first)
 753                 return rb_entry(first, struct map, rb_node);
 754         return NULL;
 755 }
 756
 757 struct map *maps__next(struct map *map)
 758 {
 759         struct rb_node *next = rb_next(&map->rb_node);
 760
 761         if (next)
 762                 return rb_entry(next, struct map, rb_node);
 763         return NULL;
 764 }