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