tools/perf/util/maps.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include <errno.h>
   3 #include <stdlib.h>
   4 #include <linux/zalloc.h>
   5 #include "debug.h"
   6 #include "dso.h"
   7 #include "map.h"
   8 #include "maps.h"
   9 #include "thread.h"
  10 #include "ui/ui.h"
  11 #include "unwind.h"
  12
  13 static void maps__init(struct maps *maps, struct machine *machine)
  14 {
  15         refcount_set(maps__refcnt(maps), 1);
  16         init_rwsem(maps__lock(maps));
  17         RC_CHK_ACCESS(maps)->entries = RB_ROOT;
  18         RC_CHK_ACCESS(maps)->machine = machine;
  19         RC_CHK_ACCESS(maps)->last_search_by_name = NULL;
  20         RC_CHK_ACCESS(maps)->nr_maps = 0;
  21         RC_CHK_ACCESS(maps)->maps_by_name = NULL;
  22 }
  23
  24 static void __maps__free_maps_by_name(struct maps *maps)
  25 {
  26         /*
  27          * Free everything to try to do it from the rbtree in the next search
  28          */
  29         for (unsigned int i = 0; i < maps__nr_maps(maps); i++)
  30                 map__put(maps__maps_by_name(maps)[i]);
  31
  32         zfree(&RC_CHK_ACCESS(maps)->maps_by_name);
  33         RC_CHK_ACCESS(maps)->nr_maps_allocated = 0;
  34 }
  35
  36 static int __maps__insert(struct maps *maps, struct map *map)
  37 {
  38         struct rb_node **p = &maps__entries(maps)->rb_node;
  39         struct rb_node *parent = NULL;
  40         const u64 ip = map__start(map);
  41         struct map_rb_node *m, *new_rb_node;
  42
  43         new_rb_node = malloc(sizeof(*new_rb_node));
  44         if (!new_rb_node)
  45                 return -ENOMEM;
  46
  47         RB_CLEAR_NODE(&new_rb_node->rb_node);
  48         new_rb_node->map = map__get(map);
  49
  50         while (*p != NULL) {
  51                 parent = *p;
  52                 m = rb_entry(parent, struct map_rb_node, rb_node);
  53                 if (ip < map__start(m->map))
  54                         p = &(*p)->rb_left;
  55                 else
  56                         p = &(*p)->rb_right;
  57         }
  58
  59         rb_link_node(&new_rb_node->rb_node, parent, p);
  60         rb_insert_color(&new_rb_node->rb_node, maps__entries(maps));
  61         return 0;
  62 }
  63
  64 int maps__insert(struct maps *maps, struct map *map)
  65 {
  66         int err;
  67         const struct dso *dso = map__dso(map);
  68
  69         down_write(maps__lock(maps));
  70         err = __maps__insert(maps, map);
  71         if (err)
  72                 goto out;
  73
  74         ++RC_CHK_ACCESS(maps)->nr_maps;
  75
  76         if (dso && dso->kernel) {
  77                 struct kmap *kmap = map__kmap(map);
  78
  79                 if (kmap)
  80                         kmap->kmaps = maps;
  81                 else
  82                         pr_err("Internal error: kernel dso with non kernel map\n");
  83         }
  84
  85
  86         /*
  87          * If we already performed some search by name, then we need to add the just
  88          * inserted map and resort.
  89          */
  90         if (maps__maps_by_name(maps)) {
  91                 if (maps__nr_maps(maps) > RC_CHK_ACCESS(maps)->nr_maps_allocated) {
  92                         int nr_allocate = maps__nr_maps(maps) * 2;
  93                         struct map **maps_by_name = realloc(maps__maps_by_name(maps),
  94                                                             nr_allocate * sizeof(map));
  95
  96                         if (maps_by_name == NULL) {
  97                                 __maps__free_maps_by_name(maps);
  98                                 err = -ENOMEM;
  99                                 goto out;
 100                         }
 101
 102                         RC_CHK_ACCESS(maps)->maps_by_name = maps_by_name;
 103                         RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
 104                 }
 105                 maps__maps_by_name(maps)[maps__nr_maps(maps) - 1] = map__get(map);
 106                 __maps__sort_by_name(maps);
 107         }
 108  out:
 109         up_write(maps__lock(maps));
 110         return err;
 111 }
 112
 113 static void __maps__remove(struct maps *maps, struct map_rb_node *rb_node)
 114 {
 115         rb_erase_init(&rb_node->rb_node, maps__entries(maps));
 116         map__put(rb_node->map);
 117         free(rb_node);
 118 }
 119
 120 void maps__remove(struct maps *maps, struct map *map)
 121 {
 122         struct map_rb_node *rb_node;
 123
 124         down_write(maps__lock(maps));
 125         if (RC_CHK_ACCESS(maps)->last_search_by_name == map)
 126                 RC_CHK_ACCESS(maps)->last_search_by_name = NULL;
 127
 128         rb_node = maps__find_node(maps, map);
 129         assert(rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map));
 130         __maps__remove(maps, rb_node);
 131         if (maps__maps_by_name(maps))
 132                 __maps__free_maps_by_name(maps);
 133         --RC_CHK_ACCESS(maps)->nr_maps;
 134         up_write(maps__lock(maps));
 135 }
 136
 137 static void __maps__purge(struct maps *maps)
 138 {
 139         struct map_rb_node *pos, *next;
 140
 141         if (maps__maps_by_name(maps))
 142                 __maps__free_maps_by_name(maps);
 143
 144         maps__for_each_entry_safe(maps, pos, next) {
 145                 rb_erase_init(&pos->rb_node,  maps__entries(maps));
 146                 map__put(pos->map);
 147                 free(pos);
 148         }
 149 }
 150
 151 static void maps__exit(struct maps *maps)
 152 {
 153         down_write(maps__lock(maps));
 154         __maps__purge(maps);
 155         up_write(maps__lock(maps));
 156 }
 157
 158 bool maps__empty(struct maps *maps)
 159 {
 160         return !maps__first(maps);
 161 }
 162
 163 struct maps *maps__new(struct machine *machine)
 164 {
 165         struct maps *result;
 166         RC_STRUCT(maps) *maps = zalloc(sizeof(*maps));
 167
 168         if (ADD_RC_CHK(result, maps))
 169                 maps__init(result, machine);
 170
 171         return result;
 172 }
 173
 174 static void maps__delete(struct maps *maps)
 175 {
 176         maps__exit(maps);
 177         unwind__finish_access(maps);
 178         RC_CHK_FREE(maps);
 179 }
 180
 181 struct maps *maps__get(struct maps *maps)
 182 {
 183         struct maps *result;
 184
 185         if (RC_CHK_GET(result, maps))
 186                 refcount_inc(maps__refcnt(maps));
 187
 188         return result;
 189 }
 190
 191 void maps__put(struct maps *maps)
 192 {
 193         if (maps && refcount_dec_and_test(maps__refcnt(maps)))
 194                 maps__delete(maps);
 195         else
 196                 RC_CHK_PUT(maps);
 197 }
 198
 199 struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
 200 {
 201         struct map *map = maps__find(maps, addr);
 202
 203         /* Ensure map is loaded before using map->map_ip */
 204         if (map != NULL && map__load(map) >= 0) {
 205                 if (mapp != NULL)
 206                         *mapp = map;
 207                 return map__find_symbol(map, map__map_ip(map, addr));
 208         }
 209
 210         return NULL;
 211 }
 212
 213 struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
 214 {
 215         struct symbol *sym;
 216         struct map_rb_node *pos;
 217
 218         down_read(maps__lock(maps));
 219
 220         maps__for_each_entry(maps, pos) {
 221                 sym = map__find_symbol_by_name(pos->map, name);
 222
 223                 if (sym == NULL)
 224                         continue;
 225                 if (!map__contains_symbol(pos->map, sym)) {
 226                         sym = NULL;
 227                         continue;
 228                 }
 229                 if (mapp != NULL)
 230                         *mapp = pos->map;
 231                 goto out;
 232         }
 233
 234         sym = NULL;
 235 out:
 236         up_read(maps__lock(maps));
 237         return sym;
 238 }
 239
 240 int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
 241 {
 242         if (ams->addr < map__start(ams->ms.map) || ams->addr >= map__end(ams->ms.map)) {
 243                 if (maps == NULL)
 244                         return -1;
 245                 ams->ms.map = maps__find(maps, ams->addr);
 246                 if (ams->ms.map == NULL)
 247                         return -1;
 248         }
 249
 250         ams->al_addr = map__map_ip(ams->ms.map, ams->addr);
 251         ams->ms.sym = map__find_symbol(ams->ms.map, ams->al_addr);
 252
 253         return ams->ms.sym ? 0 : -1;
 254 }
 255
 256 size_t maps__fprintf(struct maps *maps, FILE *fp)
 257 {
 258         size_t printed = 0;
 259         struct map_rb_node *pos;
 260
 261         down_read(maps__lock(maps));
 262
 263         maps__for_each_entry(maps, pos) {
 264                 printed += fprintf(fp, "Map:");
 265                 printed += map__fprintf(pos->map, fp);
 266                 if (verbose > 2) {
 267                         printed += dso__fprintf(map__dso(pos->map), fp);
 268                         printed += fprintf(fp, "--\n");
 269                 }
 270         }
 271
 272         up_read(maps__lock(maps));
 273
 274         return printed;
 275 }
 276
 277 int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
 278 {
 279         struct rb_root *root;
 280         struct rb_node *next, *first;
 281         int err = 0;
 282
 283         down_write(maps__lock(maps));
 284
 285         root = maps__entries(maps);
 286
 287         /*
 288          * Find first map where end > map->start.
 289          * Same as find_vma() in kernel.
 290          */
 291         next = root->rb_node;
 292         first = NULL;
 293         while (next) {
 294                 struct map_rb_node *pos = rb_entry(next, struct map_rb_node, rb_node);
 295
 296                 if (map__end(pos->map) > map__start(map)) {
 297                         first = next;
 298                         if (map__start(pos->map) <= map__start(map))
 299                                 break;
 300                         next = next->rb_left;
 301                 } else
 302                         next = next->rb_right;
 303         }
 304
 305         next = first;
 306         while (next && !err) {
 307                 struct map_rb_node *pos = rb_entry(next, struct map_rb_node, rb_node);
 308                 next = rb_next(&pos->rb_node);
 309
 310                 /*
 311                  * Stop if current map starts after map->end.
 312                  * Maps are ordered by start: next will not overlap for sure.
 313                  */
 314                 if (map__start(pos->map) >= map__end(map))
 315                         break;
 316
 317                 if (verbose >= 2) {
 318
 319                         if (use_browser) {
 320                                 pr_debug("overlapping maps in %s (disable tui for more info)\n",
 321                                          map__dso(map)->name);
 322                         } else {
 323                                 fputs("overlapping maps:\n", fp);
 324                                 map__fprintf(map, fp);
 325                                 map__fprintf(pos->map, fp);
 326                         }
 327                 }
 328
 329                 rb_erase_init(&pos->rb_node, root);
 330                 /*
 331                  * Now check if we need to create new maps for areas not
 332                  * overlapped by the new map:
 333                  */
 334                 if (map__start(map) > map__start(pos->map)) {
 335                         struct map *before = map__clone(pos->map);
 336
 337                         if (before == NULL) {
 338                                 err = -ENOMEM;
 339                                 goto put_map;
 340                         }
 341
 342                         map__set_end(before, map__start(map));
 343                         err = __maps__insert(maps, before);
 344                         if (err) {
 345                                 map__put(before);
 346                                 goto put_map;
 347                         }
 348
 349                         if (verbose >= 2 && !use_browser)
 350                                 map__fprintf(before, fp);
 351                         map__put(before);
 352                 }
 353
 354                 if (map__end(map) < map__end(pos->map)) {
 355                         struct map *after = map__clone(pos->map);
 356
 357                         if (after == NULL) {
 358                                 err = -ENOMEM;
 359                                 goto put_map;
 360                         }
 361
 362                         map__set_start(after, map__end(map));
 363                         map__add_pgoff(after, map__end(map) - map__start(pos->map));
 364                         assert(map__map_ip(pos->map, map__end(map)) ==
 365                                 map__map_ip(after, map__end(map)));
 366                         err = __maps__insert(maps, after);
 367                         if (err) {
 368                                 map__put(after);
 369                                 goto put_map;
 370                         }
 371                         if (verbose >= 2 && !use_browser)
 372                                 map__fprintf(after, fp);
 373                         map__put(after);
 374                 }
 375 put_map:
 376                 map__put(pos->map);
 377                 free(pos);
 378         }
 379         up_write(maps__lock(maps));
 380         return err;
 381 }
 382
 383 /*
 384  * XXX This should not really _copy_ te maps, but refcount them.
 385  */
 386 int maps__clone(struct thread *thread, struct maps *parent)
 387 {
 388         struct maps *maps = thread__maps(thread);
 389         int err;
 390         struct map_rb_node *rb_node;
 391
 392         down_read(maps__lock(parent));
 393
 394         maps__for_each_entry(parent, rb_node) {
 395                 struct map *new = map__clone(rb_node->map);
 396
 397                 if (new == NULL) {
 398                         err = -ENOMEM;
 399                         goto out_unlock;
 400                 }
 401
 402                 err = unwind__prepare_access(maps, new, NULL);
 403                 if (err)
 404                         goto out_unlock;
 405
 406                 err = maps__insert(maps, new);
 407                 if (err)
 408                         goto out_unlock;
 409
 410                 map__put(new);
 411         }
 412
 413         err = 0;
 414 out_unlock:
 415         up_read(maps__lock(parent));
 416         return err;
 417 }
 418
 419 struct map_rb_node *maps__find_node(struct maps *maps, struct map *map)
 420 {
 421         struct map_rb_node *rb_node;
 422
 423         maps__for_each_entry(maps, rb_node) {
 424                 if (rb_node->RC_CHK_ACCESS(map) == RC_CHK_ACCESS(map))
 425                         return rb_node;
 426         }
 427         return NULL;
 428 }
 429
 430 struct map *maps__find(struct maps *maps, u64 ip)
 431 {
 432         struct rb_node *p;
 433         struct map_rb_node *m;
 434
 435
 436         down_read(maps__lock(maps));
 437
 438         p = maps__entries(maps)->rb_node;
 439         while (p != NULL) {
 440                 m = rb_entry(p, struct map_rb_node, rb_node);
 441                 if (ip < map__start(m->map))
 442                         p = p->rb_left;
 443                 else if (ip >= map__end(m->map))
 444                         p = p->rb_right;
 445                 else
 446                         goto out;
 447         }
 448
 449         m = NULL;
 450 out:
 451         up_read(maps__lock(maps));
 452         return m ? m->map : NULL;
 453 }
 454
 455 struct map_rb_node *maps__first(struct maps *maps)
 456 {
 457         struct rb_node *first = rb_first(maps__entries(maps));
 458
 459         if (first)
 460                 return rb_entry(first, struct map_rb_node, rb_node);
 461         return NULL;
 462 }
 463
 464 struct map_rb_node *map_rb_node__next(struct map_rb_node *node)
 465 {
 466         struct rb_node *next;
 467
 468         if (!node)
 469                 return NULL;
 470
 471         next = rb_next(&node->rb_node);
 472
 473         if (!next)
 474                 return NULL;
 475
 476         return rb_entry(next, struct map_rb_node, rb_node);
 477 }