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 "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(map__refcnt(map)) > 0);
  78
  79		if (map__dso(map) && dso__kernel(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(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(prev) <= map__end(map));
  96					assert(map__end(prev) <= map__start(map) ||
  97					       map__start(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(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(maps__refcnt(maps), 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(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(maps__refcnt(maps));
 268
 269	return result;
 270}
 271
 272void maps__put(struct maps *maps)
 273{
 274	if (maps && refcount_dec_and_test(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(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, 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_a);
 302	u64 map_b_start = map__start(map_b);
 303
 304	if (map_a_start == map_b_start) {
 305		u64 map_a_end = map__end(map_a);
 306		u64 map_b_end = map__end(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, true);
 330}
 331
 332static void maps__sort_by_address(struct maps *maps)
 333{
 334	down_write(maps__lock(maps));
 335	__maps__sort_by_address(maps);
 336	up_write(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_a);
 344	const struct dso *dso_b = map__dso(map_b);
 345	int ret = strcmp(dso__short_name(dso_a), dso__short_name(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(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, maps_by_name);
 372				for (unsigned int i = 0; i < n; i++)
 373					maps_by_name[i] = map__get(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, true);
 382		}
 383	}
 384	check_invariants(maps);
 385	up_write(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(&map, maps__maps_by_address(maps), maps__nr_maps(maps),
 396				sizeof(*mapp), 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(&map, maps_by_name, maps__nr_maps(maps),
 417				sizeof(*mapp), 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, 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, 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(new);
 480	map__set_kmap_maps(new, maps);
 481	if (maps_by_name)
 482		maps_by_name[nr_maps] = map__get(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, true);
 495		maps__set_maps_by_name_sorted(maps, 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			maps__maps_by_address_sorted(maps) &&
 500			map__end(maps_by_address[nr_maps - 2]) <= map__start(new));
 501		maps__set_maps_by_name_sorted(maps, false);
 502	}
 503	if (map__end(new) < map__start(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(maps__lock(maps));
 514	ret = __maps__insert(maps, map);
 515	check_invariants(maps);
 516	up_write(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(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(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(maps__lock(maps));
 549	__maps__remove(maps, map);
 550	check_invariants(maps);
 551	up_write(maps__lock(maps));
 552}
 553
 554bool maps__empty(struct maps *maps)
 555{
 556	bool res;
 557
 558	down_read(maps__lock(maps));
 559	res = maps__nr_maps(maps) == 0;
 560	up_read(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(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(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(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, maps_by_address[i]);
 614		else
 615			i++;
 616	}
 617	check_invariants(maps);
 618	up_write(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, map__map_ip(map, 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, args->name);
 649	if (!args->sym)
 650		return 0;
 651
 652	if (!map__contains_symbol(map, 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, maps__find_symbol_by_name_cb, &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(ams->ms.map) || ams->addr >= map__end(ams->ms.map)) {
 677		if (maps == NULL)
 678			return -1;
 679		map__put(ams->ms.map);
 680		ams->ms.map = maps__find(maps, ams->addr);
 681		if (ams->ms.map == NULL)
 682			return -1;
 683	}
 684
 685	ams->al_addr = map__map_ip(ams->ms.map, ams->addr);
 686	ams->ms.sym = map__find_symbol(ams->ms.map, ams->al_addr);
 687
 688	return ams->ms.sym ? 0 : -1;
 689}
 690
 691struct maps__fprintf_args {
 692	FILE *fp;
 693	size_t printed;
 694};
 695
 696static int maps__fprintf_cb(struct map *map, void *data)
 697{
 698	struct maps__fprintf_args *args = data;
 699
 700	args->printed += fprintf(args->fp, "Map:");
 701	args->printed += map__fprintf(map, args->fp);
 702	if (verbose > 2) {
 703		args->printed += dso__fprintf(map__dso(map), args->fp);
 704		args->printed += fprintf(args->fp, "--\n");
 705	}
 706	return 0;
 707}
 708
 709size_t maps__fprintf(struct maps *maps, FILE *fp)
 710{
 711	struct maps__fprintf_args args = {
 712		.fp = fp,
 713		.printed = 0,
 714	};
 715
 716	maps__for_each_map(maps, maps__fprintf_cb, &args);
 717
 718	return args.printed;
 719}
 720
 721/*
 722 * Find first map where end > map->start.
 723 * Same as find_vma() in kernel.
 724 */
 725static unsigned int first_ending_after(struct maps *maps, const struct map *map)
 726{
 727	struct map **maps_by_address = maps__maps_by_address(maps);
 728	int low = 0, high = (int)maps__nr_maps(maps) - 1, first = high + 1;
 729
 730	assert(maps__maps_by_address_sorted(maps));
 731	if (low <= high && map__end(maps_by_address[0]) > map__start(map))
 732		return 0;
 733
 734	while (low <= high) {
 735		int mid = (low + high) / 2;
 736		struct map *pos = maps_by_address[mid];
 737
 738		if (map__end(pos) > map__start(map)) {
 739			first = mid;
 740			if (map__start(pos) <= map__start(map)) {
 741				/* Entry overlaps map. */
 742				break;
 743			}
 744			high = mid - 1;
 745		} else
 746			low = mid + 1;
 747	}
 748	return first;
 749}
 750
 751static int __maps__insert_sorted(struct maps *maps, unsigned int first_after_index,
 752				 struct map *new1, struct map *new2)
 753{
 754	struct map **maps_by_address = maps__maps_by_address(maps);
 755	struct map **maps_by_name = maps__maps_by_name(maps);
 756	unsigned int nr_maps = maps__nr_maps(maps);
 757	unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated;
 758	unsigned int to_add = new2 ? 2 : 1;
 759
 760	assert(maps__maps_by_address_sorted(maps));
 761	assert(first_after_index == nr_maps ||
 762	       map__end(new1) <= map__start(maps_by_address[first_after_index]));
 763	assert(!new2 || map__end(new1) <= map__start(new2));
 764	assert(first_after_index == nr_maps || !new2 ||
 765	       map__end(new2) <= map__start(maps_by_address[first_after_index]));
 766
 767	if (nr_maps + to_add > nr_allocate) {
 768		nr_allocate = !nr_allocate ? 32 : nr_allocate * 2;
 769
 770		maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new1));
 771		if (!maps_by_address)
 772			return -ENOMEM;
 773
 774		maps__set_maps_by_address(maps, maps_by_address);
 775		if (maps_by_name) {
 776			maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new1));
 777			if (!maps_by_name) {
 778				/*
 779				 * If by name fails, just disable by name and it will
 780				 * recompute next time it is required.
 781				 */
 782				__maps__free_maps_by_name(maps);
 783			}
 784			maps__set_maps_by_name(maps, maps_by_name);
 785		}
 786		RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
 787	}
 788	memmove(&maps_by_address[first_after_index+to_add],
 789		&maps_by_address[first_after_index],
 790		(nr_maps - first_after_index) * sizeof(new1));
 791	maps_by_address[first_after_index] = map__get(new1);
 792	if (maps_by_name)
 793		maps_by_name[nr_maps] = map__get(new1);
 794	if (new2) {
 795		maps_by_address[first_after_index + 1] = map__get(new2);
 796		if (maps_by_name)
 797			maps_by_name[nr_maps + 1] = map__get(new2);
 798	}
 799	RC_CHK_ACCESS(maps)->nr_maps = nr_maps + to_add;
 800	maps__set_maps_by_name_sorted(maps, false);
 801	map__set_kmap_maps(new1, maps);
 802	map__set_kmap_maps(new2, maps);
 803
 804	check_invariants(maps);
 805	return 0;
 806}
 807
 808/*
 809 * Adds new to maps, if new overlaps existing entries then the existing maps are
 810 * adjusted or removed so that new fits without overlapping any entries.
 811 */
 812static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
 813{
 814	int err = 0;
 815	FILE *fp = debug_file();
 816	unsigned int i, ni = INT_MAX; // Some gcc complain, but depends on maps_by_name...
 817
 818	if (!maps__maps_by_address_sorted(maps))
 819		__maps__sort_by_address(maps);
 820
 821	/*
 822	 * Iterate through entries where the end of the existing entry is
 823	 * greater-than the new map's start.
 824	 */
 825	for (i = first_ending_after(maps, new); i < maps__nr_maps(maps); ) {
 826		struct map **maps_by_address = maps__maps_by_address(maps);
 827		struct map **maps_by_name = maps__maps_by_name(maps);
 828		struct map *pos = maps_by_address[i];
 829		struct map *before = NULL, *after = NULL;
 830
 831		/*
 832		 * Stop if current map starts after map->end.
 833		 * Maps are ordered by start: next will not overlap for sure.
 834		 */
 835		if (map__start(pos) >= map__end(new))
 836			break;
 837
 838		if (use_browser) {
 839			pr_debug("overlapping maps in %s (disable tui for more info)\n",
 840				dso__name(map__dso(new)));
 841		} else if (verbose >= 2) {
 842			pr_debug("overlapping maps:\n");
 843			map__fprintf(new, fp);
 844			map__fprintf(pos, fp);
 845		}
 846
 847		if (maps_by_name)
 848			ni = maps__by_name_index(maps, pos);
 849
 850		/*
 851		 * Now check if we need to create new maps for areas not
 852		 * overlapped by the new map:
 853		 */
 854		if (map__start(new) > map__start(pos)) {
 855			/* Map starts within existing map. Need to shorten the existing map. */
 856			before = map__clone(pos);
 857
 858			if (before == NULL) {
 859				err = -ENOMEM;
 860				goto out_err;
 861			}
 862			map__set_end(before, map__start(new));
 863
 864			if (verbose >= 2 && !use_browser)
 865				map__fprintf(before, fp);
 866		}
 867		if (map__end(new) < map__end(pos)) {
 868			/* The new map isn't as long as the existing map. */
 869			after = map__clone(pos);
 870
 871			if (after == NULL) {
 872				map__zput(before);
 873				err = -ENOMEM;
 874				goto out_err;
 875			}
 876
 877			map__set_start(after, map__end(new));
 878			map__add_pgoff(after, map__end(new) - map__start(pos));
 879			assert(map__map_ip(pos, map__end(new)) ==
 880			       map__map_ip(after, map__end(new)));
 881
 882			if (verbose >= 2 && !use_browser)
 883				map__fprintf(after, fp);
 884		}
 885		/*
 886		 * If adding one entry, for `before` or `after`, we can replace
 887		 * the existing entry. If both `before` and `after` are
 888		 * necessary than an insert is needed. If the existing entry
 889		 * entirely overlaps the existing entry it can just be removed.
 890		 */
 891		if (before) {
 892			map__put(maps_by_address[i]);
 893			maps_by_address[i] = before;
 894			map__set_kmap_maps(before, maps);
 895
 896			if (maps_by_name) {
 897				map__put(maps_by_name[ni]);
 898				maps_by_name[ni] = map__get(before);
 899			}
 900
 901			/* Maps are still ordered, go to next one. */
 902			i++;
 903			if (after) {
 904				/*
 905				 * 'before' and 'after' mean 'new' split the
 906				 * 'pos' mapping and therefore there are no
 907				 * later mappings.
 908				 */
 909				err = __maps__insert_sorted(maps, i, new, after);
 910				map__put(after);
 911				check_invariants(maps);
 912				return err;
 913			}
 914			check_invariants(maps);
 915		} else if (after) {
 916			/*
 917			 * 'after' means 'new' split 'pos' and there are no
 918			 * later mappings.
 919			 */
 920			map__put(maps_by_address[i]);
 921			maps_by_address[i] = map__get(new);
 922			map__set_kmap_maps(new, maps);
 923
 924			if (maps_by_name) {
 925				map__put(maps_by_name[ni]);
 926				maps_by_name[ni] = map__get(new);
 927			}
 928
 929			err = __maps__insert_sorted(maps, i + 1, after, NULL);
 930			map__put(after);
 931			check_invariants(maps);
 932			return err;
 933		} else {
 934			struct map *next = NULL;
 935			unsigned int nr_maps = maps__nr_maps(maps);
 936
 937			if (i + 1 < nr_maps)
 938				next = maps_by_address[i + 1];
 939
 940			if (!next  || map__start(next) >= map__end(new)) {
 941				/*
 942				 * Replace existing mapping and end knowing
 943				 * there aren't later overlapping or any
 944				 * mappings.
 945				 */
 946				map__put(maps_by_address[i]);
 947				maps_by_address[i] = map__get(new);
 948				map__set_kmap_maps(new, maps);
 949
 950				if (maps_by_name) {
 951					map__put(maps_by_name[ni]);
 952					maps_by_name[ni] = map__get(new);
 953				}
 954
 955				check_invariants(maps);
 956				return err;
 957			}
 958			/*
 959			 * pos fully covers the previous mapping so remove
 960			 * it. The following is an inlined version of
 961			 * maps__remove that reuses the already computed
 962			 * indices.
 963			 */
 964			map__put(maps_by_address[i]);
 965			memmove(&maps_by_address[i],
 966				&maps_by_address[i + 1],
 967				(nr_maps - i - 1) * sizeof(*maps_by_address));
 968
 969			if (maps_by_name) {
 970				map__put(maps_by_name[ni]);
 971				memmove(&maps_by_name[ni],
 972					&maps_by_name[ni + 1],
 973					(nr_maps - ni - 1) *  sizeof(*maps_by_name));
 974			}
 975			--RC_CHK_ACCESS(maps)->nr_maps;
 976			check_invariants(maps);
 977			/*
 978			 * Maps are ordered but no need to increase `i` as the
 979			 * later maps were moved down.
 980			 */
 981		}
 982	}
 983	/* Add the map. */
 984	err = __maps__insert_sorted(maps, i, new, NULL);
 985out_err:
 986	return err;
 987}
 988
 989int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
 990{
 991	int err;
 992
 993	down_write(maps__lock(maps));
 994	err =  __maps__fixup_overlap_and_insert(maps, new);
 995	up_write(maps__lock(maps));
 996	return err;
 997}
 998
 999int maps__copy_from(struct maps *dest, struct maps *parent)
1000{
1001	/* Note, if struct map were immutable then cloning could use ref counts. */
1002	struct map **parent_maps_by_address;
1003	int err = 0;
1004	unsigned int n;
1005
1006	down_write(maps__lock(dest));
1007	down_read(maps__lock(parent));
1008
1009	parent_maps_by_address = maps__maps_by_address(parent);
1010	n = maps__nr_maps(parent);
1011	if (maps__nr_maps(dest) == 0) {
1012		/* No existing mappings so just copy from parent to avoid reallocs in insert. */
1013		unsigned int nr_maps_allocated = RC_CHK_ACCESS(parent)->nr_maps_allocated;
1014		struct map **dest_maps_by_address =
1015			malloc(nr_maps_allocated * sizeof(struct map *));
1016		struct map **dest_maps_by_name = NULL;
1017
1018		if (!dest_maps_by_address)
1019			err = -ENOMEM;
1020		else {
1021			if (maps__maps_by_name(parent)) {
1022				dest_maps_by_name =
1023					malloc(nr_maps_allocated * sizeof(struct map *));
1024			}
1025
1026			RC_CHK_ACCESS(dest)->maps_by_address = dest_maps_by_address;
1027			RC_CHK_ACCESS(dest)->maps_by_name = dest_maps_by_name;
1028			RC_CHK_ACCESS(dest)->nr_maps_allocated = nr_maps_allocated;
1029		}
1030
1031		for (unsigned int i = 0; !err && i < n; i++) {
1032			struct map *pos = parent_maps_by_address[i];
1033			struct map *new = map__clone(pos);
1034
1035			if (!new)
1036				err = -ENOMEM;
1037			else {
1038				err = unwind__prepare_access(dest, new, NULL);
1039				if (!err) {
1040					dest_maps_by_address[i] = new;
1041					map__set_kmap_maps(new, dest);
1042					if (dest_maps_by_name)
1043						dest_maps_by_name[i] = map__get(new);
1044					RC_CHK_ACCESS(dest)->nr_maps = i + 1;
1045				}
1046			}
1047			if (err)
1048				map__put(new);
1049		}
1050		maps__set_maps_by_address_sorted(dest, maps__maps_by_address_sorted(parent));
1051		if (!err) {
1052			RC_CHK_ACCESS(dest)->last_search_by_name_idx =
1053				RC_CHK_ACCESS(parent)->last_search_by_name_idx;
1054			maps__set_maps_by_name_sorted(dest,
1055						dest_maps_by_name &&
1056						maps__maps_by_name_sorted(parent));
1057		} else {
1058			RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0;
1059			maps__set_maps_by_name_sorted(dest, false);
1060		}
1061	} else {
1062		/* Unexpected copying to a maps containing entries. */
1063		for (unsigned int i = 0; !err && i < n; i++) {
1064			struct map *pos = parent_maps_by_address[i];
1065			struct map *new = map__clone(pos);
1066
1067			if (!new)
1068				err = -ENOMEM;
1069			else {
1070				err = unwind__prepare_access(dest, new, NULL);
1071				if (!err)
1072					err = __maps__insert(dest, new);
1073			}
1074			map__put(new);
1075		}
1076	}
1077	check_invariants(dest);
1078
1079	up_read(maps__lock(parent));
1080	up_write(maps__lock(dest));
1081	return err;
1082}
1083
1084static int map__addr_cmp(const void *key, const void *entry)
1085{
1086	const u64 ip = *(const u64 *)key;
1087	const struct map *map = *(const struct map * const *)entry;
1088
1089	if (ip < map__start(map))
1090		return -1;
1091	if (ip >= map__end(map))
1092		return 1;
1093	return 0;
1094}
1095
1096struct map *maps__find(struct maps *maps, u64 ip)
1097{
1098	struct map *result = NULL;
1099	bool done = false;
1100
1101	/* See locking/sorting note. */
1102	while (!done) {
1103		down_read(maps__lock(maps));
1104		if (maps__maps_by_address_sorted(maps)) {
1105			struct map **mapp = NULL;
1106			struct map **maps_by_address = maps__maps_by_address(maps);
1107			unsigned int nr_maps = maps__nr_maps(maps);
1108
1109			if (maps_by_address && nr_maps)
1110				mapp = bsearch(&ip, maps_by_address, nr_maps, sizeof(*mapp),
1111					       map__addr_cmp);
1112			if (mapp)
1113				result = map__get(*mapp);
1114			done = true;
1115		}
1116		up_read(maps__lock(maps));
1117		if (!done)
1118			maps__sort_by_address(maps);
1119	}
1120	return result;
1121}
1122
1123static int map__strcmp_name(const void *name, const void *b)
1124{
1125	const struct dso *dso = map__dso(*(const struct map **)b);
1126
1127	return strcmp(name, dso__short_name(dso));
1128}
1129
1130struct map *maps__find_by_name(struct maps *maps, const char *name)
1131{
1132	struct map *result = NULL;
1133	bool done = false;
1134
1135	/* See locking/sorting note. */
1136	while (!done) {
1137		unsigned int i;
1138
1139		down_read(maps__lock(maps));
1140
1141		/* First check last found entry. */
1142		i = RC_CHK_ACCESS(maps)->last_search_by_name_idx;
1143		if (i < maps__nr_maps(maps) && maps__maps_by_name(maps)) {
1144			struct dso *dso = map__dso(maps__maps_by_name(maps)[i]);
1145
1146			if (dso && strcmp(dso__short_name(dso), name) == 0) {
1147				result = map__get(maps__maps_by_name(maps)[i]);
1148				done = true;
1149			}
1150		}
1151
1152		/* Second search sorted array. */
1153		if (!done && maps__maps_by_name_sorted(maps)) {
1154			struct map **mapp =
1155				bsearch(name, maps__maps_by_name(maps), maps__nr_maps(maps),
1156					sizeof(*mapp), map__strcmp_name);
1157
1158			if (mapp) {
1159				result = map__get(*mapp);
1160				i = mapp - maps__maps_by_name(maps);
1161				RC_CHK_ACCESS(maps)->last_search_by_name_idx = i;
1162			}
1163			done = true;
1164		}
1165		up_read(maps__lock(maps));
1166		if (!done) {
1167			/* Sort and retry binary search. */
1168			if (maps__sort_by_name(maps)) {
1169				/*
1170				 * Memory allocation failed do linear search
1171				 * through address sorted maps.
1172				 */
1173				struct map **maps_by_address;
1174				unsigned int n;
1175
1176				down_read(maps__lock(maps));
1177				maps_by_address =  maps__maps_by_address(maps);
1178				n = maps__nr_maps(maps);
1179				for (i = 0; i < n; i++) {
1180					struct map *pos = maps_by_address[i];
1181					struct dso *dso = map__dso(pos);
1182
1183					if (dso && strcmp(dso__short_name(dso), name) == 0) {
1184						result = map__get(pos);
1185						break;
1186					}
1187				}
1188				up_read(maps__lock(maps));
1189				done = true;
1190			}
1191		}
1192	}
1193	return result;
1194}
1195
1196struct map *maps__find_next_entry(struct maps *maps, struct map *map)
1197{
1198	unsigned int i;
1199	struct map *result = NULL;
1200
1201	down_read(maps__lock(maps));
1202	while (!maps__maps_by_address_sorted(maps)) {
1203		up_read(maps__lock(maps));
1204		maps__sort_by_address(maps);
1205		down_read(maps__lock(maps));
1206	}
1207	i = maps__by_address_index(maps, map);
1208	if (++i < maps__nr_maps(maps))
1209		result = map__get(maps__maps_by_address(maps)[i]);
1210
1211	up_read(maps__lock(maps));
1212	return result;
1213}
1214
1215void maps__fixup_end(struct maps *maps)
1216{
1217	struct map **maps_by_address;
1218	unsigned int n;
1219
1220	down_write(maps__lock(maps));
1221	if (!maps__maps_by_address_sorted(maps))
1222		__maps__sort_by_address(maps);
1223
1224	maps_by_address = maps__maps_by_address(maps);
1225	n = maps__nr_maps(maps);
1226	for (unsigned int i = 1; i < n; i++) {
1227		struct map *prev = maps_by_address[i - 1];
1228		struct map *curr = maps_by_address[i];
1229
1230		if (!map__end(prev) || map__end(prev) > map__start(curr))
1231			map__set_end(prev, map__start(curr));
1232	}
1233
1234	/*
1235	 * We still haven't the actual symbols, so guess the
1236	 * last map final address.
1237	 */
1238	if (n > 0 && !map__end(maps_by_address[n - 1]))
1239		map__set_end(maps_by_address[n - 1], ~0ULL);
1240
1241	RC_CHK_ACCESS(maps)->ends_broken = false;
1242	check_invariants(maps);
1243
1244	up_write(maps__lock(maps));
1245}
1246
1247/*
1248 * Merges map into maps by splitting the new map within the existing map
1249 * regions.
1250 */
1251int maps__merge_in(struct maps *kmaps, struct map *new_map)
1252{
1253	unsigned int first_after_, kmaps__nr_maps;
1254	struct map **kmaps_maps_by_address;
1255	struct map **merged_maps_by_address;
1256	unsigned int merged_nr_maps_allocated;
1257
1258	/* First try under a read lock. */
1259	while (true) {
1260		down_read(maps__lock(kmaps));
1261		if (maps__maps_by_address_sorted(kmaps))
1262			break;
1263
1264		up_read(maps__lock(kmaps));
1265
1266		/* First after binary search requires sorted maps. Sort and try again. */
1267		maps__sort_by_address(kmaps);
1268	}
1269	first_after_ = first_ending_after(kmaps, new_map);
1270	kmaps_maps_by_address = maps__maps_by_address(kmaps);
1271
1272	if (first_after_ >= maps__nr_maps(kmaps) ||
1273	    map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) {
1274		/* No overlap so regular insert suffices. */
1275		up_read(maps__lock(kmaps));
1276		return maps__insert(kmaps, new_map);
1277	}
1278	up_read(maps__lock(kmaps));
1279
1280	/* Plain insert with a read-lock failed, try again now with the write lock. */
1281	down_write(maps__lock(kmaps));
1282	if (!maps__maps_by_address_sorted(kmaps))
1283		__maps__sort_by_address(kmaps);
1284
1285	first_after_ = first_ending_after(kmaps, new_map);
1286	kmaps_maps_by_address = maps__maps_by_address(kmaps);
1287	kmaps__nr_maps = maps__nr_maps(kmaps);
1288
1289	if (first_after_ >= kmaps__nr_maps ||
1290	    map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) {
1291		/* No overlap so regular insert suffices. */
1292		int ret = __maps__insert(kmaps, new_map);
1293
1294		check_invariants(kmaps);
1295		up_write(maps__lock(kmaps));
1296		return ret;
1297	}
1298	/* Array to merge into, possibly 1 more for the sake of new_map. */
1299	merged_nr_maps_allocated = RC_CHK_ACCESS(kmaps)->nr_maps_allocated;
1300	if (kmaps__nr_maps + 1 == merged_nr_maps_allocated)
1301		merged_nr_maps_allocated++;
1302
1303	merged_maps_by_address = malloc(merged_nr_maps_allocated * sizeof(*merged_maps_by_address));
1304	if (!merged_maps_by_address) {
1305		up_write(maps__lock(kmaps));
1306		return -ENOMEM;
1307	}
1308	maps__set_maps_by_address(kmaps, merged_maps_by_address);
1309	maps__set_maps_by_address_sorted(kmaps, true);
1310	__maps__free_maps_by_name(kmaps);
1311	maps__set_nr_maps_allocated(kmaps, merged_nr_maps_allocated);
1312
1313	/* Copy entries before the new_map that can't overlap. */
1314	for (unsigned int i = 0; i < first_after_; i++)
1315		merged_maps_by_address[i] = map__get(kmaps_maps_by_address[i]);
1316
1317	maps__set_nr_maps(kmaps, first_after_);
1318
1319	/* Add the new map, it will be split when the later overlapping mappings are added. */
1320	__maps__insert(kmaps, new_map);
1321
1322	/* Insert mappings after new_map, splitting new_map in the process. */
1323	for (unsigned int i = first_after_; i < kmaps__nr_maps; i++)
1324		__maps__fixup_overlap_and_insert(kmaps, kmaps_maps_by_address[i]);
1325
1326	/* Copy the maps from merged into kmaps. */
1327	for (unsigned int i = 0; i < kmaps__nr_maps; i++)
1328		map__zput(kmaps_maps_by_address[i]);
1329
1330	free(kmaps_maps_by_address);
1331	check_invariants(kmaps);
1332	up_write(maps__lock(kmaps));
1333	return 0;
1334}
1335
1336void maps__load_first(struct maps *maps)
1337{
1338	down_read(maps__lock(maps));
1339
1340	if (maps__nr_maps(maps) > 0)
1341		map__load(maps__maps_by_address(maps)[0]);
1342
1343	up_read(maps__lock(maps));
1344}