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 "rwsem.h"
10#include "thread.h"
11#include "ui/ui.h"
12#include "unwind.h"
13#include <internal/rc_check.h>
14
15/*
16 * Locking/sorting note:
17 *
18 * Sorting is done with the write lock, iteration and binary searching happens
19 * under the read lock requiring being sorted. There is a race between sorting
20 * releasing the write lock and acquiring the read lock for iteration/searching
21 * where another thread could insert and break the sorting of the maps. In
22 * practice inserting maps should be rare meaning that the race shouldn't lead
23 * to live lock. Removal of maps doesn't break being sorted.
24 */
25
26DECLARE_RC_STRUCT(maps) {
27 struct rw_semaphore lock;
28 /**
29 * @maps_by_address: array of maps sorted by their starting address if
30 * maps_by_address_sorted is true.
31 */
32 struct map **maps_by_address;
33 /**
34 * @maps_by_name: optional array of maps sorted by their dso name if
35 * maps_by_name_sorted is true.
36 */
37 struct map **maps_by_name;
38 struct machine *machine;
39#ifdef HAVE_LIBUNWIND_SUPPORT
40 void *addr_space;
41 const struct unwind_libunwind_ops *unwind_libunwind_ops;
42#endif
43 refcount_t refcnt;
44 /**
45 * @nr_maps: number of maps_by_address, and possibly maps_by_name,
46 * entries that contain maps.
47 */
48 unsigned int nr_maps;
49 /**
50 * @nr_maps_allocated: number of entries in maps_by_address and possibly
51 * maps_by_name.
52 */
53 unsigned int nr_maps_allocated;
54 /**
55 * @last_search_by_name_idx: cache of last found by name entry's index
56 * as frequent searches for the same dso name are common.
57 */
58 unsigned int last_search_by_name_idx;
59 /** @maps_by_address_sorted: is maps_by_address sorted. */
60 bool maps_by_address_sorted;
61 /** @maps_by_name_sorted: is maps_by_name sorted. */
62 bool maps_by_name_sorted;
63 /** @ends_broken: does the map contain a map where end values are unset/unsorted? */
64 bool ends_broken;
65};
66
67static void check_invariants(const struct maps *maps __maybe_unused)
68{
69#ifndef NDEBUG
70 assert(RC_CHK_ACCESS(maps)->nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated);
71 for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
72 struct map *map = RC_CHK_ACCESS(maps)->maps_by_address[i];
73
74 /* Check map is well-formed. */
75 assert(map__end(map) == 0 || map__start(map) <= map__end(map));
76 /* Expect at least 1 reference count. */
77 assert(refcount_read(r: map__refcnt(map)) > 0);
78
79 if (map__dso(map) && dso__kernel(dso: map__dso(map)))
80 assert(RC_CHK_EQUAL(map__kmap(map)->kmaps, maps));
81
82 if (i > 0) {
83 struct map *prev = RC_CHK_ACCESS(maps)->maps_by_address[i - 1];
84
85 /* If addresses are sorted... */
86 if (RC_CHK_ACCESS(maps)->maps_by_address_sorted) {
87 /* Maps should be in start address order. */
88 assert(map__start(map: prev) <= map__start(map));
89 /*
90 * If the ends of maps aren't broken (during
91 * construction) then they should be ordered
92 * too.
93 */
94 if (!RC_CHK_ACCESS(maps)->ends_broken) {
95 assert(map__end(map: prev) <= map__end(map));
96 assert(map__end(map: prev) <= map__start(map) ||
97 map__start(map: prev) == map__start(map));
98 }
99 }
100 }
101 }
102 if (RC_CHK_ACCESS(maps)->maps_by_name) {
103 for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
104 struct map *map = RC_CHK_ACCESS(maps)->maps_by_name[i];
105
106 /*
107 * Maps by name maps should be in maps_by_address, so
108 * the reference count should be higher.
109 */
110 assert(refcount_read(r: map__refcnt(map)) > 1);
111 }
112 }
113#endif
114}
115
116static struct map **maps__maps_by_address(const struct maps *maps)
117{
118 return RC_CHK_ACCESS(maps)->maps_by_address;
119}
120
121static void maps__set_maps_by_address(struct maps *maps, struct map **new)
122{
123 RC_CHK_ACCESS(maps)->maps_by_address = new;
124
125}
126
127static void maps__set_nr_maps_allocated(struct maps *maps, unsigned int nr_maps_allocated)
128{
129 RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_maps_allocated;
130}
131
132static void maps__set_nr_maps(struct maps *maps, unsigned int nr_maps)
133{
134 RC_CHK_ACCESS(maps)->nr_maps = nr_maps;
135}
136
137/* Not in the header, to aid reference counting. */
138static struct map **maps__maps_by_name(const struct maps *maps)
139{
140 return RC_CHK_ACCESS(maps)->maps_by_name;
141
142}
143
144static void maps__set_maps_by_name(struct maps *maps, struct map **new)
145{
146 RC_CHK_ACCESS(maps)->maps_by_name = new;
147
148}
149
150static bool maps__maps_by_address_sorted(const struct maps *maps)
151{
152 return RC_CHK_ACCESS(maps)->maps_by_address_sorted;
153}
154
155static void maps__set_maps_by_address_sorted(struct maps *maps, bool value)
156{
157 RC_CHK_ACCESS(maps)->maps_by_address_sorted = value;
158}
159
160static bool maps__maps_by_name_sorted(const struct maps *maps)
161{
162 return RC_CHK_ACCESS(maps)->maps_by_name_sorted;
163}
164
165static void maps__set_maps_by_name_sorted(struct maps *maps, bool value)
166{
167 RC_CHK_ACCESS(maps)->maps_by_name_sorted = value;
168}
169
170struct machine *maps__machine(const struct maps *maps)
171{
172 return RC_CHK_ACCESS(maps)->machine;
173}
174
175unsigned int maps__nr_maps(const struct maps *maps)
176{
177 return RC_CHK_ACCESS(maps)->nr_maps;
178}
179
180refcount_t *maps__refcnt(struct maps *maps)
181{
182 return &RC_CHK_ACCESS(maps)->refcnt;
183}
184
185#ifdef HAVE_LIBUNWIND_SUPPORT
186void *maps__addr_space(const struct maps *maps)
187{
188 return RC_CHK_ACCESS(maps)->addr_space;
189}
190
191void maps__set_addr_space(struct maps *maps, void *addr_space)
192{
193 RC_CHK_ACCESS(maps)->addr_space = addr_space;
194}
195
196const struct unwind_libunwind_ops *maps__unwind_libunwind_ops(const struct maps *maps)
197{
198 return RC_CHK_ACCESS(maps)->unwind_libunwind_ops;
199}
200
201void maps__set_unwind_libunwind_ops(struct maps *maps, const struct unwind_libunwind_ops *ops)
202{
203 RC_CHK_ACCESS(maps)->unwind_libunwind_ops = ops;
204}
205#endif
206
207static struct rw_semaphore *maps__lock(struct maps *maps)
208{
209 return &RC_CHK_ACCESS(maps)->lock;
210}
211
212static void maps__init(struct maps *maps, struct machine *machine)
213{
214 init_rwsem(maps__lock(maps));
215 RC_CHK_ACCESS(maps)->maps_by_address = NULL;
216 RC_CHK_ACCESS(maps)->maps_by_name = NULL;
217 RC_CHK_ACCESS(maps)->machine = machine;
218#ifdef HAVE_LIBUNWIND_SUPPORT
219 RC_CHK_ACCESS(maps)->addr_space = NULL;
220 RC_CHK_ACCESS(maps)->unwind_libunwind_ops = NULL;
221#endif
222 refcount_set(r: maps__refcnt(maps), n: 1);
223 RC_CHK_ACCESS(maps)->nr_maps = 0;
224 RC_CHK_ACCESS(maps)->nr_maps_allocated = 0;
225 RC_CHK_ACCESS(maps)->last_search_by_name_idx = 0;
226 RC_CHK_ACCESS(maps)->maps_by_address_sorted = true;
227 RC_CHK_ACCESS(maps)->maps_by_name_sorted = false;
228}
229
230static void maps__exit(struct maps *maps)
231{
232 struct map **maps_by_address = maps__maps_by_address(maps);
233 struct map **maps_by_name = maps__maps_by_name(maps);
234
235 for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
236 map__zput(maps_by_address[i]);
237 if (maps_by_name)
238 map__zput(maps_by_name[i]);
239 }
240 zfree(&maps_by_address);
241 zfree(&maps_by_name);
242 unwind__finish_access(maps);
243}
244
245struct maps *maps__new(struct machine *machine)
246{
247 struct maps *result;
248 RC_STRUCT(maps) *maps = zalloc(sizeof(*maps));
249
250 if (ADD_RC_CHK(result, maps))
251 maps__init(maps: result, machine);
252
253 return result;
254}
255
256static void maps__delete(struct maps *maps)
257{
258 maps__exit(maps);
259 RC_CHK_FREE(maps);
260}
261
262struct maps *maps__get(struct maps *maps)
263{
264 struct maps *result;
265
266 if (RC_CHK_GET(result, maps))
267 refcount_inc(r: maps__refcnt(maps));
268
269 return result;
270}
271
272void maps__put(struct maps *maps)
273{
274 if (maps && refcount_dec_and_test(r: maps__refcnt(maps)))
275 maps__delete(maps);
276 else
277 RC_CHK_PUT(maps);
278}
279
280static void __maps__free_maps_by_name(struct maps *maps)
281{
282 if (!maps__maps_by_name(maps))
283 return;
284
285 /*
286 * Free everything to try to do it from the rbtree in the next search
287 */
288 for (unsigned int i = 0; i < maps__nr_maps(maps); i++)
289 map__put(map: maps__maps_by_name(maps)[i]);
290
291 zfree(&RC_CHK_ACCESS(maps)->maps_by_name);
292
293 /* Consistent with maps__init(). When maps_by_name == NULL, maps_by_name_sorted == false */
294 maps__set_maps_by_name_sorted(maps, value: false);
295}
296
297static int map__start_cmp(const void *a, const void *b)
298{
299 const struct map *map_a = *(const struct map * const *)a;
300 const struct map *map_b = *(const struct map * const *)b;
301 u64 map_a_start = map__start(map: map_a);
302 u64 map_b_start = map__start(map: map_b);
303
304 if (map_a_start == map_b_start) {
305 u64 map_a_end = map__end(map: map_a);
306 u64 map_b_end = map__end(map: map_b);
307
308 if (map_a_end == map_b_end) {
309 /* Ensure maps with the same addresses have a fixed order. */
310 if (RC_CHK_ACCESS(map_a) == RC_CHK_ACCESS(map_b))
311 return 0;
312 return (intptr_t)RC_CHK_ACCESS(map_a) > (intptr_t)RC_CHK_ACCESS(map_b)
313 ? 1 : -1;
314 }
315 return map_a_end > map_b_end ? 1 : -1;
316 }
317 return map_a_start > map_b_start ? 1 : -1;
318}
319
320static void __maps__sort_by_address(struct maps *maps)
321{
322 if (maps__maps_by_address_sorted(maps))
323 return;
324
325 qsort(maps__maps_by_address(maps),
326 maps__nr_maps(maps),
327 sizeof(struct map *),
328 map__start_cmp);
329 maps__set_maps_by_address_sorted(maps, value: true);
330}
331
332static void maps__sort_by_address(struct maps *maps)
333{
334 down_write(sem: maps__lock(maps));
335 __maps__sort_by_address(maps);
336 up_write(sem: maps__lock(maps));
337}
338
339static int map__strcmp(const void *a, const void *b)
340{
341 const struct map *map_a = *(const struct map * const *)a;
342 const struct map *map_b = *(const struct map * const *)b;
343 const struct dso *dso_a = map__dso(map: map_a);
344 const struct dso *dso_b = map__dso(map: map_b);
345 int ret = strcmp(dso__short_name(dso: dso_a), dso__short_name(dso: dso_b));
346
347 if (ret == 0 && RC_CHK_ACCESS(map_a) != RC_CHK_ACCESS(map_b)) {
348 /* Ensure distinct but name equal maps have an order. */
349 return map__start_cmp(a, b);
350 }
351 return ret;
352}
353
354static int maps__sort_by_name(struct maps *maps)
355{
356 int err = 0;
357
358 down_write(sem: maps__lock(maps));
359 if (!maps__maps_by_name_sorted(maps)) {
360 struct map **maps_by_name = maps__maps_by_name(maps);
361
362 if (!maps_by_name) {
363 maps_by_name = malloc(RC_CHK_ACCESS(maps)->nr_maps_allocated *
364 sizeof(*maps_by_name));
365 if (!maps_by_name)
366 err = -ENOMEM;
367 else {
368 struct map **maps_by_address = maps__maps_by_address(maps);
369 unsigned int n = maps__nr_maps(maps);
370
371 maps__set_maps_by_name(maps, new: maps_by_name);
372 for (unsigned int i = 0; i < n; i++)
373 maps_by_name[i] = map__get(map: maps_by_address[i]);
374 }
375 }
376 if (!err) {
377 qsort(maps_by_name,
378 maps__nr_maps(maps),
379 sizeof(struct map *),
380 map__strcmp);
381 maps__set_maps_by_name_sorted(maps, value: true);
382 }
383 }
384 check_invariants(maps);
385 up_write(sem: maps__lock(maps));
386 return err;
387}
388
389static unsigned int maps__by_address_index(const struct maps *maps, const struct map *map)
390{
391 struct map **maps_by_address = maps__maps_by_address(maps);
392
393 if (maps__maps_by_address_sorted(maps)) {
394 struct map **mapp =
395 bsearch(key: &map, base: maps__maps_by_address(maps), num: maps__nr_maps(maps),
396 size: sizeof(*mapp), cmp: map__start_cmp);
397
398 if (mapp)
399 return mapp - maps_by_address;
400 } else {
401 for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
402 if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map))
403 return i;
404 }
405 }
406 pr_err("Map missing from maps");
407 return -1;
408}
409
410static unsigned int maps__by_name_index(const struct maps *maps, const struct map *map)
411{
412 struct map **maps_by_name = maps__maps_by_name(maps);
413
414 if (maps__maps_by_name_sorted(maps)) {
415 struct map **mapp =
416 bsearch(key: &map, base: maps_by_name, num: maps__nr_maps(maps),
417 size: sizeof(*mapp), cmp: map__strcmp);
418
419 if (mapp)
420 return mapp - maps_by_name;
421 } else {
422 for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
423 if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map))
424 return i;
425 }
426 }
427 pr_err("Map missing from maps");
428 return -1;
429}
430
431static void map__set_kmap_maps(struct map *map, struct maps *maps)
432{
433 struct dso *dso;
434
435 if (map == NULL)
436 return;
437
438 dso = map__dso(map);
439
440 if (dso && dso__kernel(dso)) {
441 struct kmap *kmap = map__kmap(map);
442
443 if (kmap)
444 kmap->kmaps = maps;
445 else
446 pr_err("Internal error: kernel dso with non kernel map\n");
447 }
448}
449
450static int __maps__insert(struct maps *maps, struct map *new)
451{
452 struct map **maps_by_address = maps__maps_by_address(maps);
453 struct map **maps_by_name = maps__maps_by_name(maps);
454 unsigned int nr_maps = maps__nr_maps(maps);
455 unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated;
456
457 if (nr_maps + 1 > nr_allocate) {
458 nr_allocate = !nr_allocate ? 32 : nr_allocate * 2;
459
460 maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new));
461 if (!maps_by_address)
462 return -ENOMEM;
463
464 maps__set_maps_by_address(maps, new: maps_by_address);
465 if (maps_by_name) {
466 maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new));
467 if (!maps_by_name) {
468 /*
469 * If by name fails, just disable by name and it will
470 * recompute next time it is required.
471 */
472 __maps__free_maps_by_name(maps);
473 }
474 maps__set_maps_by_name(maps, new: maps_by_name);
475 }
476 RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
477 }
478 /* Insert the value at the end. */
479 maps_by_address[nr_maps] = map__get(map: new);
480 map__set_kmap_maps(map: new, maps);
481 if (maps_by_name)
482 maps_by_name[nr_maps] = map__get(map: new);
483
484 nr_maps++;
485 RC_CHK_ACCESS(maps)->nr_maps = nr_maps;
486
487 /*
488 * Recompute if things are sorted. If things are inserted in a sorted
489 * manner, for example by processing /proc/pid/maps, then no
490 * sorting/resorting will be necessary.
491 */
492 if (nr_maps == 1) {
493 /* If there's just 1 entry then maps are sorted. */
494 maps__set_maps_by_address_sorted(maps, value: true);
495 maps__set_maps_by_name_sorted(maps, value: maps_by_name != NULL);
496 } else {
497 /* Sorted if maps were already sorted and this map starts after the last one. */
498 maps__set_maps_by_address_sorted(maps,
499 value: maps__maps_by_address_sorted(maps) &&
500 map__end(map: maps_by_address[nr_maps - 2]) <= map__start(map: new));
501 maps__set_maps_by_name_sorted(maps, value: false);
502 }
503 if (map__end(map: new) < map__start(map: new))
504 RC_CHK_ACCESS(maps)->ends_broken = true;
505
506 return 0;
507}
508
509int maps__insert(struct maps *maps, struct map *map)
510{
511 int ret;
512
513 down_write(sem: maps__lock(maps));
514 ret = __maps__insert(maps, new: map);
515 check_invariants(maps);
516 up_write(sem: maps__lock(maps));
517 return ret;
518}
519
520static void __maps__remove(struct maps *maps, struct map *map)
521{
522 struct map **maps_by_address = maps__maps_by_address(maps);
523 struct map **maps_by_name = maps__maps_by_name(maps);
524 unsigned int nr_maps = maps__nr_maps(maps);
525 unsigned int address_idx;
526
527 /* Slide later mappings over the one to remove */
528 address_idx = maps__by_address_index(maps, map);
529 map__put(map: maps_by_address[address_idx]);
530 memmove(&maps_by_address[address_idx],
531 &maps_by_address[address_idx + 1],
532 (nr_maps - address_idx - 1) * sizeof(*maps_by_address));
533
534 if (maps_by_name) {
535 unsigned int name_idx = maps__by_name_index(maps, map);
536
537 map__put(map: maps_by_name[name_idx]);
538 memmove(&maps_by_name[name_idx],
539 &maps_by_name[name_idx + 1],
540 (nr_maps - name_idx - 1) * sizeof(*maps_by_name));
541 }
542
543 --RC_CHK_ACCESS(maps)->nr_maps;
544}
545
546void maps__remove(struct maps *maps, struct map *map)
547{
548 down_write(sem: maps__lock(maps));
549 __maps__remove(maps, map);
550 check_invariants(maps);
551 up_write(sem: maps__lock(maps));
552}
553
554bool maps__empty(struct maps *maps)
555{
556 bool res;
557
558 down_read(sem: maps__lock(maps));
559 res = maps__nr_maps(maps) == 0;
560 up_read(sem: maps__lock(maps));
561
562 return res;
563}
564
565bool maps__equal(struct maps *a, struct maps *b)
566{
567 return RC_CHK_EQUAL(a, b);
568}
569
570int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data)
571{
572 bool done = false;
573 int ret = 0;
574
575 /* See locking/sorting note. */
576 while (!done) {
577 down_read(sem: maps__lock(maps));
578 if (maps__maps_by_address_sorted(maps)) {
579 /*
580 * maps__for_each_map callbacks may buggily/unsafely
581 * insert into maps_by_address. Deliberately reload
582 * maps__nr_maps and maps_by_address on each iteration
583 * to avoid using memory freed by maps__insert growing
584 * the array - this may cause maps to be skipped or
585 * repeated.
586 */
587 for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
588 struct map **maps_by_address = maps__maps_by_address(maps);
589 struct map *map = maps_by_address[i];
590
591 ret = cb(map, data);
592 if (ret)
593 break;
594 }
595 done = true;
596 }
597 up_read(sem: maps__lock(maps));
598 if (!done)
599 maps__sort_by_address(maps);
600 }
601 return ret;
602}
603
604void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data)
605{
606 struct map **maps_by_address;
607
608 down_write(sem: maps__lock(maps));
609
610 maps_by_address = maps__maps_by_address(maps);
611 for (unsigned int i = 0; i < maps__nr_maps(maps);) {
612 if (cb(maps_by_address[i], data))
613 __maps__remove(maps, map: maps_by_address[i]);
614 else
615 i++;
616 }
617 check_invariants(maps);
618 up_write(sem: maps__lock(maps));
619}
620
621struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
622{
623 struct map *map = maps__find(maps, addr);
624 struct symbol *result = NULL;
625
626 /* Ensure map is loaded before using map->map_ip */
627 if (map != NULL && map__load(map) >= 0)
628 result = map__find_symbol(map, addr: map__map_ip(map, ip_or_rip: addr));
629
630 if (mapp)
631 *mapp = map;
632 else
633 map__put(map);
634
635 return result;
636}
637
638struct maps__find_symbol_by_name_args {
639 struct map **mapp;
640 const char *name;
641 struct symbol *sym;
642};
643
644static int maps__find_symbol_by_name_cb(struct map *map, void *data)
645{
646 struct maps__find_symbol_by_name_args *args = data;
647
648 args->sym = map__find_symbol_by_name(map, name: args->name);
649 if (!args->sym)
650 return 0;
651
652 if (!map__contains_symbol(map, sym: args->sym)) {
653 args->sym = NULL;
654 return 0;
655 }
656
657 if (args->mapp != NULL)
658 *args->mapp = map__get(map);
659 return 1;
660}
661
662struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
663{
664 struct maps__find_symbol_by_name_args args = {
665 .mapp = mapp,
666 .name = name,
667 .sym = NULL,
668 };
669
670 maps__for_each_map(maps, cb: maps__find_symbol_by_name_cb, data: &args);
671 return args.sym;
672}
673
674int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
675{
676 if (ams->addr < map__start(map: ams->ms.map) || ams->addr >= map__end(map: ams->ms.map)) {
677 if (maps == NULL)
678 return -1;
679 ams->ms.map = maps__find(maps, addr: ams->addr);
680 if (ams->ms.map == NULL)
681 return -1;
682 }
683
684 ams->al_addr = map__map_ip(map: ams->ms.map, ip_or_rip: ams->addr);
685 ams->ms.sym = map__find_symbol(map: ams->ms.map, addr: ams->al_addr);
686
687 return ams->ms.sym ? 0 : -1;
688}
689
690struct maps__fprintf_args {
691 FILE *fp;
692 size_t printed;
693};
694
695static int maps__fprintf_cb(struct map *map, void *data)
696{
697 struct maps__fprintf_args *args = data;
698
699 args->printed += fprintf(args->fp, "Map:");
700 args->printed += map__fprintf(map, args->fp);
701 if (verbose > 2) {
702 args->printed += dso__fprintf(map__dso(map), args->fp);
703 args->printed += fprintf(args->fp, "--\n");
704 }
705 return 0;
706}
707
708size_t maps__fprintf(struct maps *maps, FILE *fp)
709{
710 struct maps__fprintf_args args = {
711 .fp = fp,
712 .printed = 0,
713 };
714
715 maps__for_each_map(maps, cb: maps__fprintf_cb, data: &args);
716
717 return args.printed;
718}
719
720/*
721 * Find first map where end > map->start.
722 * Same as find_vma() in kernel.
723 */
724static unsigned int first_ending_after(struct maps *maps, const struct map *map)
725{
726 struct map **maps_by_address = maps__maps_by_address(maps);
727 int low = 0, high = (int)maps__nr_maps(maps) - 1, first = high + 1;
728
729 assert(maps__maps_by_address_sorted(maps));
730 if (low <= high && map__end(map: maps_by_address[0]) > map__start(map))
731 return 0;
732
733 while (low <= high) {
734 int mid = (low + high) / 2;
735 struct map *pos = maps_by_address[mid];
736
737 if (map__end(map: pos) > map__start(map)) {
738 first = mid;
739 if (map__start(map: pos) <= map__start(map)) {
740 /* Entry overlaps map. */
741 break;
742 }
743 high = mid - 1;
744 } else
745 low = mid + 1;
746 }
747 return first;
748}
749
750static int __maps__insert_sorted(struct maps *maps, unsigned int first_after_index,
751 struct map *new1, struct map *new2)
752{
753 struct map **maps_by_address = maps__maps_by_address(maps);
754 struct map **maps_by_name = maps__maps_by_name(maps);
755 unsigned int nr_maps = maps__nr_maps(maps);
756 unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated;
757 unsigned int to_add = new2 ? 2 : 1;
758
759 assert(maps__maps_by_address_sorted(maps));
760 assert(first_after_index == nr_maps ||
761 map__end(map: new1) <= map__start(map: maps_by_address[first_after_index]));
762 assert(!new2 || map__end(map: new1) <= map__start(map: new2));
763 assert(first_after_index == nr_maps || !new2 ||
764 map__end(map: new2) <= map__start(map: maps_by_address[first_after_index]));
765
766 if (nr_maps + to_add > nr_allocate) {
767 nr_allocate = !nr_allocate ? 32 : nr_allocate * 2;
768
769 maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new1));
770 if (!maps_by_address)
771 return -ENOMEM;
772
773 maps__set_maps_by_address(maps, new: maps_by_address);
774 if (maps_by_name) {
775 maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new1));
776 if (!maps_by_name) {
777 /*
778 * If by name fails, just disable by name and it will
779 * recompute next time it is required.
780 */
781 __maps__free_maps_by_name(maps);
782 }
783 maps__set_maps_by_name(maps, new: maps_by_name);
784 }
785 RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
786 }
787 memmove(&maps_by_address[first_after_index+to_add],
788 &maps_by_address[first_after_index],
789 (nr_maps - first_after_index) * sizeof(new1));
790 maps_by_address[first_after_index] = map__get(map: new1);
791 if (maps_by_name)
792 maps_by_name[nr_maps] = map__get(map: new1);
793 if (new2) {
794 maps_by_address[first_after_index + 1] = map__get(map: new2);
795 if (maps_by_name)
796 maps_by_name[nr_maps + 1] = map__get(map: new2);
797 }
798 RC_CHK_ACCESS(maps)->nr_maps = nr_maps + to_add;
799 maps__set_maps_by_name_sorted(maps, value: false);
800 map__set_kmap_maps(map: new1, maps);
801 map__set_kmap_maps(map: new2, maps);
802
803 check_invariants(maps);
804 return 0;
805}
806
807/*
808 * Adds new to maps, if new overlaps existing entries then the existing maps are
809 * adjusted or removed so that new fits without overlapping any entries.
810 */
811static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
812{
813 int err = 0;
814 FILE *fp = debug_file();
815 unsigned int i, ni = INT_MAX; // Some gcc complain, but depends on maps_by_name...
816
817 if (!maps__maps_by_address_sorted(maps))
818 __maps__sort_by_address(maps);
819
820 /*
821 * Iterate through entries where the end of the existing entry is
822 * greater-than the new map's start.
823 */
824 for (i = first_ending_after(maps, map: new); i < maps__nr_maps(maps); ) {
825 struct map **maps_by_address = maps__maps_by_address(maps);
826 struct map **maps_by_name = maps__maps_by_name(maps);
827 struct map *pos = maps_by_address[i];
828 struct map *before = NULL, *after = NULL;
829
830 /*
831 * Stop if current map starts after map->end.
832 * Maps are ordered by start: next will not overlap for sure.
833 */
834 if (map__start(map: pos) >= map__end(map: new))
835 break;
836
837 if (use_browser) {
838 pr_debug("overlapping maps in %s (disable tui for more info)\n",
839 dso__name(map__dso(new)));
840 } else if (verbose >= 2) {
841 pr_debug("overlapping maps:\n");
842 map__fprintf(new, fp);
843 map__fprintf(pos, fp);
844 }
845
846 if (maps_by_name)
847 ni = maps__by_name_index(maps, map: pos);
848
849 /*
850 * Now check if we need to create new maps for areas not
851 * overlapped by the new map:
852 */
853 if (map__start(map: new) > map__start(map: pos)) {
854 /* Map starts within existing map. Need to shorten the existing map. */
855 before = map__clone(map: pos);
856
857 if (before == NULL) {
858 err = -ENOMEM;
859 goto out_err;
860 }
861 map__set_end(map: before, end: map__start(map: new));
862
863 if (verbose >= 2 && !use_browser)
864 map__fprintf(before, fp);
865 }
866 if (map__end(map: new) < map__end(map: pos)) {
867 /* The new map isn't as long as the existing map. */
868 after = map__clone(map: pos);
869
870 if (after == NULL) {
871 map__zput(before);
872 err = -ENOMEM;
873 goto out_err;
874 }
875
876 map__set_start(map: after, start: map__end(map: new));
877 map__add_pgoff(map: after, inc: map__end(map: new) - map__start(map: pos));
878 assert(map__map_ip(map: pos, ip_or_rip: map__end(map: new)) ==
879 map__map_ip(map: after, ip_or_rip: map__end(map: new)));
880
881 if (verbose >= 2 && !use_browser)
882 map__fprintf(after, fp);
883 }
884 /*
885 * If adding one entry, for `before` or `after`, we can replace
886 * the existing entry. If both `before` and `after` are
887 * necessary than an insert is needed. If the existing entry
888 * entirely overlaps the existing entry it can just be removed.
889 */
890 if (before) {
891 map__put(map: maps_by_address[i]);
892 maps_by_address[i] = before;
893 map__set_kmap_maps(map: before, maps);
894
895 if (maps_by_name) {
896 map__put(map: maps_by_name[ni]);
897 maps_by_name[ni] = map__get(map: before);
898 }
899
900 /* Maps are still ordered, go to next one. */
901 i++;
902 if (after) {
903 /*
904 * 'before' and 'after' mean 'new' split the
905 * 'pos' mapping and therefore there are no
906 * later mappings.
907 */
908 err = __maps__insert_sorted(maps, first_after_index: i, new1: new, new2: after);
909 map__put(map: after);
910 check_invariants(maps);
911 return err;
912 }
913 check_invariants(maps);
914 } else if (after) {
915 /*
916 * 'after' means 'new' split 'pos' and there are no
917 * later mappings.
918 */
919 map__put(map: maps_by_address[i]);
920 maps_by_address[i] = map__get(map: new);
921 map__set_kmap_maps(map: new, maps);
922
923 if (maps_by_name) {
924 map__put(map: maps_by_name[ni]);
925 maps_by_name[ni] = map__get(map: new);
926 }
927
928 err = __maps__insert_sorted(maps, first_after_index: i + 1, new1: after, NULL);
929 map__put(map: after);
930 check_invariants(maps);
931 return err;
932 } else {
933 struct map *next = NULL;
934 unsigned int nr_maps = maps__nr_maps(maps);
935
936 if (i + 1 < nr_maps)
937 next = maps_by_address[i + 1];
938
939 if (!next || map__start(map: next) >= map__end(map: new)) {
940 /*
941 * Replace existing mapping and end knowing
942 * there aren't later overlapping or any
943 * mappings.
944 */
945 map__put(map: maps_by_address[i]);
946 maps_by_address[i] = map__get(map: new);
947 map__set_kmap_maps(map: new, maps);
948
949 if (maps_by_name) {
950 map__put(map: maps_by_name[ni]);
951 maps_by_name[ni] = map__get(map: new);
952 }
953
954 check_invariants(maps);
955 return err;
956 }
957 /*
958 * pos fully covers the previous mapping so remove
959 * it. The following is an inlined version of
960 * maps__remove that reuses the already computed
961 * indices.
962 */
963 map__put(map: maps_by_address[i]);
964 memmove(&maps_by_address[i],
965 &maps_by_address[i + 1],
966 (nr_maps - i - 1) * sizeof(*maps_by_address));
967
968 if (maps_by_name) {
969 map__put(map: maps_by_name[ni]);
970 memmove(&maps_by_name[ni],
971 &maps_by_name[ni + 1],
972 (nr_maps - ni - 1) * sizeof(*maps_by_name));
973 }
974 --RC_CHK_ACCESS(maps)->nr_maps;
975 check_invariants(maps);
976 /*
977 * Maps are ordered but no need to increase `i` as the
978 * later maps were moved down.
979 */
980 }
981 }
982 /* Add the map. */
983 err = __maps__insert_sorted(maps, first_after_index: i, new1: new, NULL);
984out_err:
985 return err;
986}
987
988int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
989{
990 int err;
991
992 down_write(sem: maps__lock(maps));
993 err = __maps__fixup_overlap_and_insert(maps, new);
994 up_write(sem: maps__lock(maps));
995 return err;
996}
997
998int maps__copy_from(struct maps *dest, struct maps *parent)
999{
1000 /* Note, if struct map were immutable then cloning could use ref counts. */
1001 struct map **parent_maps_by_address;
1002 int err = 0;
1003 unsigned int n;
1004
1005 down_write(sem: maps__lock(maps: dest));
1006 down_read(sem: maps__lock(maps: parent));
1007
1008 parent_maps_by_address = maps__maps_by_address(maps: parent);
1009 n = maps__nr_maps(maps: parent);
1010 if (maps__nr_maps(maps: dest) == 0) {
1011 /* No existing mappings so just copy from parent to avoid reallocs in insert. */
1012 unsigned int nr_maps_allocated = RC_CHK_ACCESS(parent)->nr_maps_allocated;
1013 struct map **dest_maps_by_address =
1014 malloc(nr_maps_allocated * sizeof(struct map *));
1015 struct map **dest_maps_by_name = NULL;
1016
1017 if (!dest_maps_by_address)
1018 err = -ENOMEM;
1019 else {
1020 if (maps__maps_by_name(maps: parent)) {
1021 dest_maps_by_name =
1022 malloc(nr_maps_allocated * sizeof(struct map *));
1023 }
1024
1025 RC_CHK_ACCESS(dest)->maps_by_address = dest_maps_by_address;
1026 RC_CHK_ACCESS(dest)->maps_by_name = dest_maps_by_name;
1027 RC_CHK_ACCESS(dest)->nr_maps_allocated = nr_maps_allocated;
1028 }
1029
1030 for (unsigned int i = 0; !err && i < n; i++) {
1031 struct map *pos = parent_maps_by_address[i];
1032 struct map *new = map__clone(map: pos);
1033
1034 if (!new)
1035 err = -ENOMEM;
1036 else {
1037 err = unwind__prepare_access(maps: dest, map: new, NULL);
1038 if (!err) {
1039 dest_maps_by_address[i] = new;
1040 map__set_kmap_maps(map: new, maps: dest);
1041 if (dest_maps_by_name)
1042 dest_maps_by_name[i] = map__get(map: new);
1043 RC_CHK_ACCESS(dest)->nr_maps = i + 1;
1044 }
1045 }
1046 if (err)
1047 map__put(map: new);
1048 }
1049 maps__set_maps_by_address_sorted(maps: dest, value: maps__maps_by_address_sorted(maps: parent));
1050 if (!err) {
1051 RC_CHK_ACCESS(dest)->last_search_by_name_idx =
1052 RC_CHK_ACCESS(parent)->last_search_by_name_idx;
1053 maps__set_maps_by_name_sorted(maps: dest,
1054 value: dest_maps_by_name &&
1055 maps__maps_by_name_sorted(maps: parent));
1056 } else {
1057 RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0;
1058 maps__set_maps_by_name_sorted(maps: dest, value: false);
1059 }
1060 } else {
1061 /* Unexpected copying to a maps containing entries. */
1062 for (unsigned int i = 0; !err && i < n; i++) {
1063 struct map *pos = parent_maps_by_address[i];
1064 struct map *new = map__clone(map: pos);
1065
1066 if (!new)
1067 err = -ENOMEM;
1068 else {
1069 err = unwind__prepare_access(maps: dest, map: new, NULL);
1070 if (!err)
1071 err = __maps__insert(maps: dest, new);
1072 }
1073 map__put(map: new);
1074 }
1075 }
1076 check_invariants(maps: dest);
1077
1078 up_read(sem: maps__lock(maps: parent));
1079 up_write(sem: maps__lock(maps: dest));
1080 return err;
1081}
1082
1083static int map__addr_cmp(const void *key, const void *entry)
1084{
1085 const u64 ip = *(const u64 *)key;
1086 const struct map *map = *(const struct map * const *)entry;
1087
1088 if (ip < map__start(map))
1089 return -1;
1090 if (ip >= map__end(map))
1091 return 1;
1092 return 0;
1093}
1094
1095struct map *maps__find(struct maps *maps, u64 ip)
1096{
1097 struct map *result = NULL;
1098 bool done = false;
1099
1100 /* See locking/sorting note. */
1101 while (!done) {
1102 down_read(sem: maps__lock(maps));
1103 if (maps__maps_by_address_sorted(maps)) {
1104 struct map **mapp = NULL;
1105 struct map **maps_by_address = maps__maps_by_address(maps);
1106 unsigned int nr_maps = maps__nr_maps(maps);
1107
1108 if (maps_by_address && nr_maps)
1109 mapp = bsearch(key: &ip, base: maps_by_address, num: nr_maps, size: sizeof(*mapp),
1110 cmp: map__addr_cmp);
1111 if (mapp)
1112 result = map__get(map: *mapp);
1113 done = true;
1114 }
1115 up_read(sem: maps__lock(maps));
1116 if (!done)
1117 maps__sort_by_address(maps);
1118 }
1119 return result;
1120}
1121
1122static int map__strcmp_name(const void *name, const void *b)
1123{
1124 const struct dso *dso = map__dso(map: *(const struct map **)b);
1125
1126 return strcmp(name, dso__short_name(dso));
1127}
1128
1129struct map *maps__find_by_name(struct maps *maps, const char *name)
1130{
1131 struct map *result = NULL;
1132 bool done = false;
1133
1134 /* See locking/sorting note. */
1135 while (!done) {
1136 unsigned int i;
1137
1138 down_read(sem: maps__lock(maps));
1139
1140 /* First check last found entry. */
1141 i = RC_CHK_ACCESS(maps)->last_search_by_name_idx;
1142 if (i < maps__nr_maps(maps) && maps__maps_by_name(maps)) {
1143 struct dso *dso = map__dso(map: maps__maps_by_name(maps)[i]);
1144
1145 if (dso && strcmp(dso__short_name(dso), name) == 0) {
1146 result = map__get(map: maps__maps_by_name(maps)[i]);
1147 done = true;
1148 }
1149 }
1150
1151 /* Second search sorted array. */
1152 if (!done && maps__maps_by_name_sorted(maps)) {
1153 struct map **mapp =
1154 bsearch(key: name, base: maps__maps_by_name(maps), num: maps__nr_maps(maps),
1155 size: sizeof(*mapp), cmp: map__strcmp_name);
1156
1157 if (mapp) {
1158 result = map__get(map: *mapp);
1159 i = mapp - maps__maps_by_name(maps);
1160 RC_CHK_ACCESS(maps)->last_search_by_name_idx = i;
1161 }
1162 done = true;
1163 }
1164 up_read(sem: maps__lock(maps));
1165 if (!done) {
1166 /* Sort and retry binary search. */
1167 if (maps__sort_by_name(maps)) {
1168 /*
1169 * Memory allocation failed do linear search
1170 * through address sorted maps.
1171 */
1172 struct map **maps_by_address;
1173 unsigned int n;
1174
1175 down_read(sem: maps__lock(maps));
1176 maps_by_address = maps__maps_by_address(maps);
1177 n = maps__nr_maps(maps);
1178 for (i = 0; i < n; i++) {
1179 struct map *pos = maps_by_address[i];
1180 struct dso *dso = map__dso(map: pos);
1181
1182 if (dso && strcmp(dso__short_name(dso), name) == 0) {
1183 result = map__get(map: pos);
1184 break;
1185 }
1186 }
1187 up_read(sem: maps__lock(maps));
1188 done = true;
1189 }
1190 }
1191 }
1192 return result;
1193}
1194
1195struct map *maps__find_next_entry(struct maps *maps, struct map *map)
1196{
1197 unsigned int i;
1198 struct map *result = NULL;
1199
1200 down_read(sem: maps__lock(maps));
1201 while (!maps__maps_by_address_sorted(maps)) {
1202 up_read(sem: maps__lock(maps));
1203 maps__sort_by_address(maps);
1204 down_read(sem: maps__lock(maps));
1205 }
1206 i = maps__by_address_index(maps, map);
1207 if (++i < maps__nr_maps(maps))
1208 result = map__get(map: maps__maps_by_address(maps)[i]);
1209
1210 up_read(sem: maps__lock(maps));
1211 return result;
1212}
1213
1214void maps__fixup_end(struct maps *maps)
1215{
1216 struct map **maps_by_address;
1217 unsigned int n;
1218
1219 down_write(sem: maps__lock(maps));
1220 if (!maps__maps_by_address_sorted(maps))
1221 __maps__sort_by_address(maps);
1222
1223 maps_by_address = maps__maps_by_address(maps);
1224 n = maps__nr_maps(maps);
1225 for (unsigned int i = 1; i < n; i++) {
1226 struct map *prev = maps_by_address[i - 1];
1227 struct map *curr = maps_by_address[i];
1228
1229 if (!map__end(map: prev) || map__end(map: prev) > map__start(map: curr))
1230 map__set_end(map: prev, end: map__start(map: curr));
1231 }
1232
1233 /*
1234 * We still haven't the actual symbols, so guess the
1235 * last map final address.
1236 */
1237 if (n > 0 && !map__end(map: maps_by_address[n - 1]))
1238 map__set_end(map: maps_by_address[n - 1], end: ~0ULL);
1239
1240 RC_CHK_ACCESS(maps)->ends_broken = false;
1241 check_invariants(maps);
1242
1243 up_write(sem: maps__lock(maps));
1244}
1245
1246/*
1247 * Merges map into maps by splitting the new map within the existing map
1248 * regions.
1249 */
1250int maps__merge_in(struct maps *kmaps, struct map *new_map)
1251{
1252 unsigned int first_after_, kmaps__nr_maps;
1253 struct map **kmaps_maps_by_address;
1254 struct map **merged_maps_by_address;
1255 unsigned int merged_nr_maps_allocated;
1256
1257 /* First try under a read lock. */
1258 while (true) {
1259 down_read(sem: maps__lock(maps: kmaps));
1260 if (maps__maps_by_address_sorted(maps: kmaps))
1261 break;
1262
1263 up_read(sem: maps__lock(maps: kmaps));
1264
1265 /* First after binary search requires sorted maps. Sort and try again. */
1266 maps__sort_by_address(maps: kmaps);
1267 }
1268 first_after_ = first_ending_after(maps: kmaps, map: new_map);
1269 kmaps_maps_by_address = maps__maps_by_address(maps: kmaps);
1270
1271 if (first_after_ >= maps__nr_maps(maps: kmaps) ||
1272 map__start(map: kmaps_maps_by_address[first_after_]) >= map__end(map: new_map)) {
1273 /* No overlap so regular insert suffices. */
1274 up_read(sem: maps__lock(maps: kmaps));
1275 return maps__insert(maps: kmaps, map: new_map);
1276 }
1277 up_read(sem: maps__lock(maps: kmaps));
1278
1279 /* Plain insert with a read-lock failed, try again now with the write lock. */
1280 down_write(sem: maps__lock(maps: kmaps));
1281 if (!maps__maps_by_address_sorted(maps: kmaps))
1282 __maps__sort_by_address(maps: kmaps);
1283
1284 first_after_ = first_ending_after(maps: kmaps, map: new_map);
1285 kmaps_maps_by_address = maps__maps_by_address(maps: kmaps);
1286 kmaps__nr_maps = maps__nr_maps(maps: kmaps);
1287
1288 if (first_after_ >= kmaps__nr_maps ||
1289 map__start(map: kmaps_maps_by_address[first_after_]) >= map__end(map: new_map)) {
1290 /* No overlap so regular insert suffices. */
1291 int ret = __maps__insert(maps: kmaps, new: new_map);
1292
1293 check_invariants(maps: kmaps);
1294 up_write(sem: maps__lock(maps: kmaps));
1295 return ret;
1296 }
1297 /* Array to merge into, possibly 1 more for the sake of new_map. */
1298 merged_nr_maps_allocated = RC_CHK_ACCESS(kmaps)->nr_maps_allocated;
1299 if (kmaps__nr_maps + 1 == merged_nr_maps_allocated)
1300 merged_nr_maps_allocated++;
1301
1302 merged_maps_by_address = malloc(merged_nr_maps_allocated * sizeof(*merged_maps_by_address));
1303 if (!merged_maps_by_address) {
1304 up_write(sem: maps__lock(maps: kmaps));
1305 return -ENOMEM;
1306 }
1307 maps__set_maps_by_address(maps: kmaps, new: merged_maps_by_address);
1308 maps__set_maps_by_address_sorted(maps: kmaps, value: true);
1309 __maps__free_maps_by_name(maps: kmaps);
1310 maps__set_nr_maps_allocated(maps: kmaps, nr_maps_allocated: merged_nr_maps_allocated);
1311
1312 /* Copy entries before the new_map that can't overlap. */
1313 for (unsigned int i = 0; i < first_after_; i++)
1314 merged_maps_by_address[i] = map__get(map: kmaps_maps_by_address[i]);
1315
1316 maps__set_nr_maps(maps: kmaps, nr_maps: first_after_);
1317
1318 /* Add the new map, it will be split when the later overlapping mappings are added. */
1319 __maps__insert(maps: kmaps, new: new_map);
1320
1321 /* Insert mappings after new_map, splitting new_map in the process. */
1322 for (unsigned int i = first_after_; i < kmaps__nr_maps; i++)
1323 __maps__fixup_overlap_and_insert(maps: kmaps, new: kmaps_maps_by_address[i]);
1324
1325 /* Copy the maps from merged into kmaps. */
1326 for (unsigned int i = 0; i < kmaps__nr_maps; i++)
1327 map__zput(kmaps_maps_by_address[i]);
1328
1329 free(kmaps_maps_by_address);
1330 check_invariants(maps: kmaps);
1331 up_write(sem: maps__lock(maps: kmaps));
1332 return 0;
1333}
1334
1335void maps__load_first(struct maps *maps)
1336{
1337 down_read(sem: maps__lock(maps));
1338
1339 if (maps__nr_maps(maps) > 0)
1340 map__load(map: maps__maps_by_address(maps)[0]);
1341
1342 up_read(sem: maps__lock(maps));
1343}
1344

source code of linux/tools/perf/util/maps.c