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