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