perf/util/maps.c

// SPDX-License-Identifier: GPL-2.0
#include <errno.h>
#include <stdlib.h>
#include <linux/zalloc.h>
#include "debug.h"
#include "dso.h"
#include "map.h"
#include "maps.h"
#include "rwsem.h"
#include "thread.h"
#include "ui/ui.h"
#include "unwind.h"
#include "unwind-libdw.h"
#include <internal/rc_check.h>

/*
 * Locking/sorting note:
 *
 * Sorting is done with the write lock, iteration and binary searching happens
 * under the read lock requiring being sorted. There is a race between sorting
 * releasing the write lock and acquiring the read lock for iteration/searching
 * where another thread could insert and break the sorting of the maps. In
 * practice inserting maps should be rare meaning that the race shouldn't lead
 * to live lock. Removal of maps doesn't break being sorted.
 */

DECLARE_RC_STRUCT(maps) {
	struct rw_semaphore lock;
	/**
	 * @maps_by_address: array of maps sorted by their starting address if
	 * maps_by_address_sorted is true.
	 */
	struct map	 **maps_by_address;
	/**
	 * @maps_by_name: optional array of maps sorted by their dso name if
	 * maps_by_name_sorted is true.
	 */
	struct map	 **maps_by_name;
	struct machine	 *machine;
#ifdef HAVE_LIBUNWIND_SUPPORT
	void		*addr_space;
	const struct unwind_libunwind_ops *unwind_libunwind_ops;
	uint16_t	 e_machine;
#endif
#ifdef HAVE_LIBDW_SUPPORT
	void		*libdw_addr_space_dwfl;
#endif
	refcount_t	 refcnt;
	/**
	 * @nr_maps: number of maps_by_address, and possibly maps_by_name,
	 * entries that contain maps.
	 */
	unsigned int	 nr_maps;
	/**
	 * @nr_maps_allocated: number of entries in maps_by_address and possibly
	 * maps_by_name.
	 */
	unsigned int	 nr_maps_allocated;
	/**
	 * @last_search_by_name_idx: cache of last found by name entry's index
	 * as frequent searches for the same dso name are common.
	 */
	unsigned int	 last_search_by_name_idx;
	/** @maps_by_address_sorted: is maps_by_address sorted. */
	bool		 maps_by_address_sorted;
	/** @maps_by_name_sorted: is maps_by_name sorted. */
	bool		 maps_by_name_sorted;
	/** @ends_broken: does the map contain a map where end values are unset/unsorted? */
	bool		 ends_broken;
};

static void check_invariants(const struct maps *maps __maybe_unused)
{
#ifndef NDEBUG
	assert(RC_CHK_ACCESS(maps)->nr_maps <= RC_CHK_ACCESS(maps)->nr_maps_allocated);
	for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
		struct map *map = RC_CHK_ACCESS(maps)->maps_by_address[i];

		/* Check map is well-formed. */
		assert(map__end(map) == 0 || map__start(map) <= map__end(map));
		/* Expect at least 1 reference count. */
		assert(refcount_read(map__refcnt(map)) > 0);

		if (map__dso(map) && dso__kernel(map__dso(map)))
			assert(RC_CHK_EQUAL(map__kmap(map)->kmaps, maps));

		if (i > 0) {
			struct map *prev = RC_CHK_ACCESS(maps)->maps_by_address[i - 1];

			/* If addresses are sorted... */
			if (RC_CHK_ACCESS(maps)->maps_by_address_sorted) {
				/* Maps should be in start address order. */
				assert(map__start(prev) <= map__start(map));
				/*
				 * If the ends of maps aren't broken (during
				 * construction) then they should be ordered
				 * too.
				 */
				if (!RC_CHK_ACCESS(maps)->ends_broken) {
					assert(map__end(prev) <= map__end(map));
					assert(map__end(prev) <= map__start(map) ||
					       map__start(prev) == map__start(map));
				}
			}
		}
	}
	if (RC_CHK_ACCESS(maps)->maps_by_name) {
		for (unsigned int i = 0; i < RC_CHK_ACCESS(maps)->nr_maps; i++) {
			struct map *map = RC_CHK_ACCESS(maps)->maps_by_name[i];

			/*
			 * Maps by name maps should be in maps_by_address, so
			 * the reference count should be higher.
			 */
			assert(refcount_read(map__refcnt(map)) > 1);
		}
	}
#endif
}

static struct map **maps__maps_by_address(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->maps_by_address;
}

static void maps__set_maps_by_address(struct maps *maps, struct map **new)
{
	RC_CHK_ACCESS(maps)->maps_by_address = new;

}

static void maps__set_nr_maps_allocated(struct maps *maps, unsigned int nr_maps_allocated)
{
	RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_maps_allocated;
}

static void maps__set_nr_maps(struct maps *maps, unsigned int nr_maps)
{
	RC_CHK_ACCESS(maps)->nr_maps = nr_maps;
}

/* Not in the header, to aid reference counting. */
static struct map **maps__maps_by_name(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->maps_by_name;

}

static void maps__set_maps_by_name(struct maps *maps, struct map **new)
{
	RC_CHK_ACCESS(maps)->maps_by_name = new;

}

static bool maps__maps_by_address_sorted(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->maps_by_address_sorted;
}

static void maps__set_maps_by_address_sorted(struct maps *maps, bool value)
{
	RC_CHK_ACCESS(maps)->maps_by_address_sorted = value;
}

static bool maps__maps_by_name_sorted(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->maps_by_name_sorted;
}

static void maps__set_maps_by_name_sorted(struct maps *maps, bool value)
{
	RC_CHK_ACCESS(maps)->maps_by_name_sorted = value;
}

struct machine *maps__machine(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->machine;
}

unsigned int maps__nr_maps(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->nr_maps;
}

refcount_t *maps__refcnt(struct maps *maps)
{
	return &RC_CHK_ACCESS(maps)->refcnt;
}

#ifdef HAVE_LIBUNWIND_SUPPORT
void *maps__addr_space(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->addr_space;
}

void maps__set_addr_space(struct maps *maps, void *addr_space)
{
	RC_CHK_ACCESS(maps)->addr_space = addr_space;
}

const struct unwind_libunwind_ops *maps__unwind_libunwind_ops(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->unwind_libunwind_ops;
}

void maps__set_unwind_libunwind_ops(struct maps *maps, const struct unwind_libunwind_ops *ops)
{
	RC_CHK_ACCESS(maps)->unwind_libunwind_ops = ops;
}

uint16_t maps__e_machine(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->e_machine;
}

void maps__set_e_machine(struct maps *maps, uint16_t e_machine)
{
	RC_CHK_ACCESS(maps)->e_machine = e_machine;
}
#endif
#ifdef HAVE_LIBDW_SUPPORT
void *maps__libdw_addr_space_dwfl(const struct maps *maps)
{
	return RC_CHK_ACCESS(maps)->libdw_addr_space_dwfl;
}

void maps__set_libdw_addr_space_dwfl(struct maps *maps, void *dwfl)
{
	RC_CHK_ACCESS(maps)->libdw_addr_space_dwfl = dwfl;
}
#endif

static struct rw_semaphore *maps__lock(struct maps *maps)
{
	return &RC_CHK_ACCESS(maps)->lock;
}

static void maps__init(struct maps *maps, struct machine *machine)
{
	init_rwsem(maps__lock(maps));
	RC_CHK_ACCESS(maps)->maps_by_address = NULL;
	RC_CHK_ACCESS(maps)->maps_by_name = NULL;
	RC_CHK_ACCESS(maps)->machine = machine;
#ifdef HAVE_LIBUNWIND_SUPPORT
	RC_CHK_ACCESS(maps)->addr_space = NULL;
	RC_CHK_ACCESS(maps)->unwind_libunwind_ops = NULL;
#endif
#ifdef HAVE_LIBDW_SUPPORT
	RC_CHK_ACCESS(maps)->libdw_addr_space_dwfl = NULL;
#endif
	refcount_set(maps__refcnt(maps), 1);
	RC_CHK_ACCESS(maps)->nr_maps = 0;
	RC_CHK_ACCESS(maps)->nr_maps_allocated = 0;
	RC_CHK_ACCESS(maps)->last_search_by_name_idx = 0;
	RC_CHK_ACCESS(maps)->maps_by_address_sorted = true;
	RC_CHK_ACCESS(maps)->maps_by_name_sorted = false;
}

static void maps__exit(struct maps *maps)
{
	struct map **maps_by_address = maps__maps_by_address(maps);
	struct map **maps_by_name = maps__maps_by_name(maps);

	for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
		map__zput(maps_by_address[i]);
		if (maps_by_name)
			map__zput(maps_by_name[i]);
	}
	zfree(&maps_by_address);
	zfree(&maps_by_name);
	unwind__finish_access(maps);
#ifdef HAVE_LIBDW_SUPPORT
	libdw__invalidate_dwfl(maps, maps__libdw_addr_space_dwfl(maps));
#endif
}

struct maps *maps__new(struct machine *machine)
{
	struct maps *result;
	RC_STRUCT(maps) *maps = zalloc(sizeof(*maps));

	if (ADD_RC_CHK(result, maps))
		maps__init(result, machine);

	return result;
}

static void maps__delete(struct maps *maps)
{
	maps__exit(maps);
	RC_CHK_FREE(maps);
}

struct maps *maps__get(struct maps *maps)
{
	struct maps *result;

	if (RC_CHK_GET(result, maps))
		refcount_inc(maps__refcnt(maps));

	return result;
}

void maps__put(struct maps *maps)
{
	if (maps && refcount_dec_and_test(maps__refcnt(maps)))
		maps__delete(maps);
	else
		RC_CHK_PUT(maps);
}

static void __maps__free_maps_by_name(struct maps *maps)
{
	if (!maps__maps_by_name(maps))
		return;

	/*
	 * Free everything to try to do it from the rbtree in the next search
	 */
	for (unsigned int i = 0; i < maps__nr_maps(maps); i++)
		map__put(maps__maps_by_name(maps)[i]);

	zfree(&RC_CHK_ACCESS(maps)->maps_by_name);

	/* Consistent with maps__init(). When maps_by_name == NULL, maps_by_name_sorted == false */
	maps__set_maps_by_name_sorted(maps, false);
}

static int map__start_cmp(const void *a, const void *b)
{
	const struct map *map_a = *(const struct map * const *)a;
	const struct map *map_b = *(const struct map * const *)b;
	u64 map_a_start = map__start(map_a);
	u64 map_b_start = map__start(map_b);

	if (map_a_start == map_b_start) {
		u64 map_a_end = map__end(map_a);
		u64 map_b_end = map__end(map_b);

		if  (map_a_end == map_b_end) {
			/* Ensure maps with the same addresses have a fixed order. */
			if (RC_CHK_ACCESS(map_a) == RC_CHK_ACCESS(map_b))
				return 0;
			return (intptr_t)RC_CHK_ACCESS(map_a) > (intptr_t)RC_CHK_ACCESS(map_b)
				? 1 : -1;
		}
		return map_a_end > map_b_end ? 1 : -1;
	}
	return map_a_start > map_b_start ? 1 : -1;
}

static void __maps__sort_by_address(struct maps *maps)
{
	if (maps__maps_by_address_sorted(maps))
		return;

	qsort(maps__maps_by_address(maps),
		maps__nr_maps(maps),
		sizeof(struct map *),
		map__start_cmp);
	maps__set_maps_by_address_sorted(maps, true);
}

static void maps__sort_by_address(struct maps *maps)
{
	down_write(maps__lock(maps));
	__maps__sort_by_address(maps);
	up_write(maps__lock(maps));
}

static int map__strcmp(const void *a, const void *b)
{
	const struct map *map_a = *(const struct map * const *)a;
	const struct map *map_b = *(const struct map * const *)b;
	const struct dso *dso_a = map__dso(map_a);
	const struct dso *dso_b = map__dso(map_b);
	int ret = strcmp(dso__short_name(dso_a), dso__short_name(dso_b));

	if (ret == 0 && RC_CHK_ACCESS(map_a) != RC_CHK_ACCESS(map_b)) {
		/* Ensure distinct but name equal maps have an order. */
		return map__start_cmp(a, b);
	}
	return ret;
}

static int maps__sort_by_name(struct maps *maps)
{
	int err = 0;

	down_write(maps__lock(maps));
	if (!maps__maps_by_name_sorted(maps)) {
		struct map **maps_by_name = maps__maps_by_name(maps);

		if (!maps_by_name) {
			maps_by_name = malloc(RC_CHK_ACCESS(maps)->nr_maps_allocated *
					sizeof(*maps_by_name));
			if (!maps_by_name)
				err = -ENOMEM;
			else {
				struct map **maps_by_address = maps__maps_by_address(maps);
				unsigned int n = maps__nr_maps(maps);

				maps__set_maps_by_name(maps, maps_by_name);
				for (unsigned int i = 0; i < n; i++)
					maps_by_name[i] = map__get(maps_by_address[i]);
			}
		}
		if (!err) {
			qsort(maps_by_name,
				maps__nr_maps(maps),
				sizeof(struct map *),
				map__strcmp);
			maps__set_maps_by_name_sorted(maps, true);
		}
	}
	check_invariants(maps);
	up_write(maps__lock(maps));
	return err;
}

static unsigned int maps__by_address_index(const struct maps *maps, const struct map *map)
{
	struct map **maps_by_address = maps__maps_by_address(maps);

	if (maps__maps_by_address_sorted(maps)) {
		struct map **mapp =
			bsearch(&map, maps__maps_by_address(maps), maps__nr_maps(maps),
				sizeof(*mapp), map__start_cmp);

		if (mapp)
			return mapp - maps_by_address;
	} else {
		for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
			if (RC_CHK_ACCESS(maps_by_address[i]) == RC_CHK_ACCESS(map))
				return i;
		}
	}
	pr_err("Map missing from maps");
	return -1;
}

static unsigned int maps__by_name_index(const struct maps *maps, const struct map *map)
{
	struct map **maps_by_name = maps__maps_by_name(maps);

	if (maps__maps_by_name_sorted(maps)) {
		struct map **mapp =
			bsearch(&map, maps_by_name, maps__nr_maps(maps),
				sizeof(*mapp), map__strcmp);

		if (mapp)
			return mapp - maps_by_name;
	} else {
		for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
			if (RC_CHK_ACCESS(maps_by_name[i]) == RC_CHK_ACCESS(map))
				return i;
		}
	}
	pr_err("Map missing from maps");
	return -1;
}

static void map__set_kmap_maps(struct map *map, struct maps *maps)
{
	struct dso *dso;

	if (map == NULL)
		return;

	dso = map__dso(map);

	if (dso && dso__kernel(dso)) {
                struct kmap *kmap = map__kmap(map);

                if (kmap)
                        kmap->kmaps = maps;
                else
                        pr_err("Internal error: kernel dso with non kernel map\n");
        }
}

static int __maps__insert(struct maps *maps, struct map *new)
{
	struct map **maps_by_address = maps__maps_by_address(maps);
	struct map **maps_by_name = maps__maps_by_name(maps);
	unsigned int nr_maps = maps__nr_maps(maps);
	unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated;

	if (nr_maps + 1 > nr_allocate) {
		nr_allocate = !nr_allocate ? 32 : nr_allocate * 2;

		maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new));
		if (!maps_by_address)
			return -ENOMEM;

		maps__set_maps_by_address(maps, maps_by_address);
		if (maps_by_name) {
			maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new));
			if (!maps_by_name) {
				/*
				 * If by name fails, just disable by name and it will
				 * recompute next time it is required.
				 */
				__maps__free_maps_by_name(maps);
			}
			maps__set_maps_by_name(maps, maps_by_name);
		}
		RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
	}
	/* Insert the value at the end. */
	maps_by_address[nr_maps] = map__get(new);
	map__set_kmap_maps(new, maps);
	if (maps_by_name)
		maps_by_name[nr_maps] = map__get(new);

	nr_maps++;
	RC_CHK_ACCESS(maps)->nr_maps = nr_maps;

	/*
	 * Recompute if things are sorted. If things are inserted in a sorted
	 * manner, for example by processing /proc/pid/maps, then no
	 * sorting/resorting will be necessary.
	 */
	if (nr_maps == 1) {
		/* If there's just 1 entry then maps are sorted. */
		maps__set_maps_by_address_sorted(maps, true);
		maps__set_maps_by_name_sorted(maps, maps_by_name != NULL);
	} else {
		/* Sorted if maps were already sorted and this map starts after the last one. */
		maps__set_maps_by_address_sorted(maps,
			maps__maps_by_address_sorted(maps) &&
			map__end(maps_by_address[nr_maps - 2]) <= map__start(new));
		maps__set_maps_by_name_sorted(maps, false);
	}
	if (map__end(new) < map__start(new))
		RC_CHK_ACCESS(maps)->ends_broken = true;

	return 0;
}

int maps__insert(struct maps *maps, struct map *map)
{
	int ret;

	down_write(maps__lock(maps));
	ret = __maps__insert(maps, map);
	check_invariants(maps);
	up_write(maps__lock(maps));
	return ret;
}

static void __maps__remove(struct maps *maps, struct map *map)
{
	struct map **maps_by_address = maps__maps_by_address(maps);
	struct map **maps_by_name = maps__maps_by_name(maps);
	unsigned int nr_maps = maps__nr_maps(maps);
	unsigned int address_idx;

	/* Slide later mappings over the one to remove */
	address_idx = maps__by_address_index(maps, map);
	map__put(maps_by_address[address_idx]);
	memmove(&maps_by_address[address_idx],
		&maps_by_address[address_idx + 1],
		(nr_maps - address_idx - 1) * sizeof(*maps_by_address));

	if (maps_by_name) {
		unsigned int name_idx = maps__by_name_index(maps, map);

		map__put(maps_by_name[name_idx]);
		memmove(&maps_by_name[name_idx],
			&maps_by_name[name_idx + 1],
			(nr_maps - name_idx - 1) *  sizeof(*maps_by_name));
	}

	--RC_CHK_ACCESS(maps)->nr_maps;
}

void maps__remove(struct maps *maps, struct map *map)
{
	down_write(maps__lock(maps));
	__maps__remove(maps, map);
	check_invariants(maps);
	up_write(maps__lock(maps));
#ifdef HAVE_LIBDW_SUPPORT
	libdw__invalidate_dwfl(maps, maps__libdw_addr_space_dwfl(maps));
#endif
}

bool maps__empty(struct maps *maps)
{
	bool res;

	down_read(maps__lock(maps));
	res = maps__nr_maps(maps) == 0;
	up_read(maps__lock(maps));

	return res;
}

bool maps__equal(struct maps *a, struct maps *b)
{
	return RC_CHK_EQUAL(a, b);
}

int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data)
{
	bool done = false;
	int ret = 0;

	/* See locking/sorting note. */
	while (!done) {
		down_read(maps__lock(maps));
		if (maps__maps_by_address_sorted(maps)) {
			/*
			 * maps__for_each_map callbacks may buggily/unsafely
			 * insert into maps_by_address. Deliberately reload
			 * maps__nr_maps and maps_by_address on each iteration
			 * to avoid using memory freed by maps__insert growing
			 * the array - this may cause maps to be skipped or
			 * repeated.
			 */
			for (unsigned int i = 0; i < maps__nr_maps(maps); i++) {
				struct map **maps_by_address = maps__maps_by_address(maps);
				struct map *map = maps_by_address[i];

				ret = cb(map, data);
				if (ret)
					break;
			}
			done = true;
		}
		up_read(maps__lock(maps));
		if (!done)
			maps__sort_by_address(maps);
	}
	return ret;
}

void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data), void *data)
{
	struct map **maps_by_address;
	bool removed = false;

	down_write(maps__lock(maps));

	maps_by_address = maps__maps_by_address(maps);
	for (unsigned int i = 0; i < maps__nr_maps(maps);) {
		if (cb(maps_by_address[i], data)) {
			__maps__remove(maps, maps_by_address[i]);
			removed = true;
		} else {
			i++;
		}
	}
	check_invariants(maps);
	up_write(maps__lock(maps));
	if (removed) {
#ifdef HAVE_LIBDW_SUPPORT
		libdw__invalidate_dwfl(maps, maps__libdw_addr_space_dwfl(maps));
#endif
	}
}

struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
{
	struct map *map = maps__find(maps, addr);
	struct symbol *result = NULL;

	/* Ensure map is loaded before using map->map_ip */
	if (map != NULL && map__load(map) >= 0)
		result = map__find_symbol(map, map__map_ip(map, addr));

	if (mapp)
		*mapp = map;
	else
		map__put(map);

	return result;
}

struct maps__find_symbol_by_name_args {
	struct map **mapp;
	const char *name;
	struct symbol *sym;
};

static int maps__find_symbol_by_name_cb(struct map *map, void *data)
{
	struct maps__find_symbol_by_name_args *args = data;

	args->sym = map__find_symbol_by_name(map, args->name);
	if (!args->sym)
		return 0;

	if (!map__contains_symbol(map, args->sym)) {
		args->sym = NULL;
		return 0;
	}

	if (args->mapp != NULL)
		*args->mapp = map__get(map);
	return 1;
}

struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
{
	struct maps__find_symbol_by_name_args args = {
		.mapp = mapp,
		.name = name,
		.sym = NULL,
	};

	maps__for_each_map(maps, maps__find_symbol_by_name_cb, &args);
	return args.sym;
}

int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
{
	if (ams->addr < map__start(ams->ms.map) || ams->addr >= map__end(ams->ms.map)) {
		if (maps == NULL)
			return -1;
		map__put(ams->ms.map);
		ams->ms.map = maps__find(maps, ams->addr);
		if (ams->ms.map == NULL)
			return -1;
	}

	ams->al_addr = map__map_ip(ams->ms.map, ams->addr);
	ams->ms.sym = map__find_symbol(ams->ms.map, ams->al_addr);

	return ams->ms.sym ? 0 : -1;
}

struct maps__fprintf_args {
	FILE *fp;
	size_t printed;
};

static int maps__fprintf_cb(struct map *map, void *data)
{
	struct maps__fprintf_args *args = data;

	args->printed += fprintf(args->fp, "Map:");
	args->printed += map__fprintf(map, args->fp);
	if (verbose > 2) {
		args->printed += dso__fprintf(map__dso(map), args->fp);
		args->printed += fprintf(args->fp, "--\n");
	}
	return 0;
}

size_t maps__fprintf(struct maps *maps, FILE *fp)
{
	struct maps__fprintf_args args = {
		.fp = fp,
		.printed = 0,
	};

	maps__for_each_map(maps, maps__fprintf_cb, &args);

	return args.printed;
}

/*
 * Find first map where end > map->start.
 * Same as find_vma() in kernel.
 */
static unsigned int first_ending_after(struct maps *maps, const struct map *map)
{
	struct map **maps_by_address = maps__maps_by_address(maps);
	int low = 0, high = (int)maps__nr_maps(maps) - 1, first = high + 1;

	assert(maps__maps_by_address_sorted(maps));
	if (low <= high && map__end(maps_by_address[0]) > map__start(map))
		return 0;

	while (low <= high) {
		int mid = (low + high) / 2;
		struct map *pos = maps_by_address[mid];

		if (map__end(pos) > map__start(map)) {
			first = mid;
			if (map__start(pos) <= map__start(map)) {
				/* Entry overlaps map. */
				break;
			}
			high = mid - 1;
		} else
			low = mid + 1;
	}
	return first;
}

static int __maps__insert_sorted(struct maps *maps, unsigned int first_after_index,
				 struct map *new1, struct map *new2)
{
	struct map **maps_by_address = maps__maps_by_address(maps);
	struct map **maps_by_name = maps__maps_by_name(maps);
	unsigned int nr_maps = maps__nr_maps(maps);
	unsigned int nr_allocate = RC_CHK_ACCESS(maps)->nr_maps_allocated;
	unsigned int to_add = new2 ? 2 : 1;

	assert(maps__maps_by_address_sorted(maps));
	assert(first_after_index == nr_maps ||
	       map__end(new1) <= map__start(maps_by_address[first_after_index]));
	assert(!new2 || map__end(new1) <= map__start(new2));
	assert(first_after_index == nr_maps || !new2 ||
	       map__end(new2) <= map__start(maps_by_address[first_after_index]));

	if (nr_maps + to_add > nr_allocate) {
		nr_allocate = !nr_allocate ? 32 : nr_allocate * 2;

		maps_by_address = realloc(maps_by_address, nr_allocate * sizeof(new1));
		if (!maps_by_address)
			return -ENOMEM;

		maps__set_maps_by_address(maps, maps_by_address);
		if (maps_by_name) {
			maps_by_name = realloc(maps_by_name, nr_allocate * sizeof(new1));
			if (!maps_by_name) {
				/*
				 * If by name fails, just disable by name and it will
				 * recompute next time it is required.
				 */
				__maps__free_maps_by_name(maps);
			}
			maps__set_maps_by_name(maps, maps_by_name);
		}
		RC_CHK_ACCESS(maps)->nr_maps_allocated = nr_allocate;
	}
	memmove(&maps_by_address[first_after_index+to_add],
		&maps_by_address[first_after_index],
		(nr_maps - first_after_index) * sizeof(new1));
	maps_by_address[first_after_index] = map__get(new1);
	if (maps_by_name)
		maps_by_name[nr_maps] = map__get(new1);
	if (new2) {
		maps_by_address[first_after_index + 1] = map__get(new2);
		if (maps_by_name)
			maps_by_name[nr_maps + 1] = map__get(new2);
	}
	RC_CHK_ACCESS(maps)->nr_maps = nr_maps + to_add;
	maps__set_maps_by_name_sorted(maps, false);
	map__set_kmap_maps(new1, maps);
	map__set_kmap_maps(new2, maps);

	check_invariants(maps);
	return 0;
}

/*
 * Adds new to maps, if new overlaps existing entries then the existing maps are
 * adjusted or removed so that new fits without overlapping any entries.
 */
static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
{
	int err = 0;
	unsigned int i, ni = INT_MAX; // Some gcc complain, but depends on maps_by_name...

	if (!maps__maps_by_address_sorted(maps))
		__maps__sort_by_address(maps);

	/*
	 * Iterate through entries where the end of the existing entry is
	 * greater-than the new map's start.
	 */
	for (i = first_ending_after(maps, new); i < maps__nr_maps(maps); ) {
		struct map **maps_by_address = maps__maps_by_address(maps);
		struct map **maps_by_name = maps__maps_by_name(maps);
		struct map *pos = maps_by_address[i];
		struct map *before = NULL, *after = NULL;

		/*
		 * Stop if current map starts after map->end.
		 * Maps are ordered by start: next will not overlap for sure.
		 */
		if (map__start(pos) >= map__end(new))
			break;

		if (use_browser) {
			pr_debug("overlapping maps in %s (disable tui for more info)\n",
				dso__name(map__dso(new)));
		} else if (verbose >= 2) {
			pr_debug("overlapping maps:\n");
			map__fprintf(new, debug_file());
			map__fprintf(pos, debug_file());
		}

		if (maps_by_name)
			ni = maps__by_name_index(maps, pos);

		/*
		 * Now check if we need to create new maps for areas not
		 * overlapped by the new map:
		 */
		if (map__start(new) > map__start(pos)) {
			/* Map starts within existing map. Need to shorten the existing map. */
			before = map__clone(pos);

			if (before == NULL) {
				err = -ENOMEM;
				goto out_err;
			}
			map__set_end(before, map__start(new));

			if (verbose >= 2 && !use_browser)
				map__fprintf(before, debug_file());
		}
		if (map__end(new) < map__end(pos)) {
			/* The new map isn't as long as the existing map. */
			after = map__clone(pos);

			if (after == NULL) {
				map__zput(before);
				err = -ENOMEM;
				goto out_err;
			}

			map__set_start(after, map__end(new));
			map__add_pgoff(after, map__end(new) - map__start(pos));
			assert(map__map_ip(pos, map__end(new)) ==
			       map__map_ip(after, map__end(new)));

			if (verbose >= 2 && !use_browser)
				map__fprintf(after, debug_file());
		}
		/*
		 * If adding one entry, for `before` or `after`, we can replace
		 * the existing entry. If both `before` and `after` are
		 * necessary than an insert is needed. If the existing entry
		 * entirely overlaps the existing entry it can just be removed.
		 */
		if (before) {
			map__put(maps_by_address[i]);
			maps_by_address[i] = before;
			map__set_kmap_maps(before, maps);

			if (maps_by_name) {
				map__put(maps_by_name[ni]);
				maps_by_name[ni] = map__get(before);
			}

			/* Maps are still ordered, go to next one. */
			i++;
			if (after) {
				/*
				 * 'before' and 'after' mean 'new' split the
				 * 'pos' mapping and therefore there are no
				 * later mappings.
				 */
				err = __maps__insert_sorted(maps, i, new, after);
				map__put(after);
				check_invariants(maps);
				return err;
			}
			check_invariants(maps);
		} else if (after) {
			/*
			 * 'after' means 'new' split 'pos' and there are no
			 * later mappings.
			 */
			map__put(maps_by_address[i]);
			maps_by_address[i] = map__get(new);
			map__set_kmap_maps(new, maps);

			if (maps_by_name) {
				map__put(maps_by_name[ni]);
				maps_by_name[ni] = map__get(new);
				maps__set_maps_by_name_sorted(maps, false);
			}

			err = __maps__insert_sorted(maps, i + 1, after, NULL);
			map__put(after);
			check_invariants(maps);
			return err;
		} else {
			struct map *next = NULL;
			unsigned int nr_maps = maps__nr_maps(maps);

			if (i + 1 < nr_maps)
				next = maps_by_address[i + 1];

			if (!next  || map__start(next) >= map__end(new)) {
				/*
				 * Replace existing mapping and end knowing
				 * there aren't later overlapping or any
				 * mappings.
				 */
				map__put(maps_by_address[i]);
				maps_by_address[i] = map__get(new);
				map__set_kmap_maps(new, maps);

				if (maps_by_name) {
					map__put(maps_by_name[ni]);
					maps_by_name[ni] = map__get(new);
					maps__set_maps_by_name_sorted(maps, false);
				}

				check_invariants(maps);
				return err;
			}
			/*
			 * pos fully covers the previous mapping so remove
			 * it. The following is an inlined version of
			 * maps__remove that reuses the already computed
			 * indices.
			 */
			map__put(maps_by_address[i]);
			memmove(&maps_by_address[i],
				&maps_by_address[i + 1],
				(nr_maps - i - 1) * sizeof(*maps_by_address));

			if (maps_by_name) {
				map__put(maps_by_name[ni]);
				memmove(&maps_by_name[ni],
					&maps_by_name[ni + 1],
					(nr_maps - ni - 1) *  sizeof(*maps_by_name));
			}
			--RC_CHK_ACCESS(maps)->nr_maps;
			check_invariants(maps);
			/*
			 * Maps are ordered but no need to increase `i` as the
			 * later maps were moved down.
			 */
		}
	}
	/* Add the map. */
	err = __maps__insert_sorted(maps, i, new, NULL);
out_err:
	return err;
}

int maps__fixup_overlap_and_insert(struct maps *maps, struct map *new)
{
	int err;

	down_write(maps__lock(maps));
	err =  __maps__fixup_overlap_and_insert(maps, new);
	up_write(maps__lock(maps));
	return err;
}

int maps__copy_from(struct maps *dest, struct maps *parent)
{
	/* Note, if struct map were immutable then cloning could use ref counts. */
	struct map **parent_maps_by_address;
	int err = 0;
	unsigned int n;

	down_write(maps__lock(dest));
	down_read(maps__lock(parent));

#ifdef HAVE_LIBUNWIND_SUPPORT
	err = unwind__prepare_access(dest, maps__e_machine(parent));
	if (err) {
		up_read(maps__lock(parent));
		up_write(maps__lock(dest));
		return err;
	}
#endif
	parent_maps_by_address = maps__maps_by_address(parent);
	n = maps__nr_maps(parent);
	if (maps__nr_maps(dest) == 0) {
		/* No existing mappings so just copy from parent to avoid reallocs in insert. */
		unsigned int nr_maps_allocated = RC_CHK_ACCESS(parent)->nr_maps_allocated;
		struct map **dest_maps_by_address =
			malloc(nr_maps_allocated * sizeof(struct map *));
		struct map **dest_maps_by_name = NULL;

		if (!dest_maps_by_address)
			err = -ENOMEM;
		else {
			if (maps__maps_by_name(parent)) {
				dest_maps_by_name =
					malloc(nr_maps_allocated * sizeof(struct map *));
			}

			RC_CHK_ACCESS(dest)->maps_by_address = dest_maps_by_address;
			RC_CHK_ACCESS(dest)->maps_by_name = dest_maps_by_name;
			RC_CHK_ACCESS(dest)->nr_maps_allocated = nr_maps_allocated;
		}

		for (unsigned int i = 0; !err && i < n; i++) {
			struct map *pos = parent_maps_by_address[i];
			struct map *new = map__clone(pos);

			if (!new)
				err = -ENOMEM;
			else {
				dest_maps_by_address[i] = new;
				map__set_kmap_maps(new, dest);
				if (dest_maps_by_name)
					dest_maps_by_name[i] = map__get(new);
				RC_CHK_ACCESS(dest)->nr_maps = i + 1;
			}
			if (err)
				map__put(new);
		}
		maps__set_maps_by_address_sorted(dest, maps__maps_by_address_sorted(parent));
		RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0;
		/* Values were copied into the name array in address order. */
		maps__set_maps_by_name_sorted(dest, false);
	} else {
		/* Unexpected copying to a maps containing entries. */
		for (unsigned int i = 0; !err && i < n; i++) {
			struct map *pos = parent_maps_by_address[i];
			struct map *new = map__clone(pos);

			if (!new)
				err = -ENOMEM;
			else {
				err = __maps__insert(dest, new);
			}
			map__put(new);
		}
	}
	check_invariants(dest);

	up_read(maps__lock(parent));
	up_write(maps__lock(dest));
	return err;
}

static int map__addr_cmp(const void *key, const void *entry)
{
	const u64 ip = *(const u64 *)key;
	const struct map *map = *(const struct map * const *)entry;

	if (ip < map__start(map))
		return -1;
	if (ip >= map__end(map))
		return 1;
	return 0;
}

struct map *maps__find(struct maps *maps, u64 ip)
{
	struct map *result = NULL;
	bool done = false;

	/* See locking/sorting note. */
	while (!done) {
		down_read(maps__lock(maps));
		if (maps__maps_by_address_sorted(maps)) {
			struct map **mapp = NULL;
			struct map **maps_by_address = maps__maps_by_address(maps);
			unsigned int nr_maps = maps__nr_maps(maps);

			if (maps_by_address && nr_maps)
				mapp = bsearch(&ip, maps_by_address, nr_maps, sizeof(*mapp),
					       map__addr_cmp);
			if (mapp)
				result = map__get(*mapp);
			done = true;
		}
		up_read(maps__lock(maps));
		if (!done)
			maps__sort_by_address(maps);
	}
	return result;
}

static int map__strcmp_name(const void *name, const void *b)
{
	const struct dso *dso = map__dso(*(const struct map **)b);

	return strcmp(name, dso__short_name(dso));
}

struct map *maps__find_by_name(struct maps *maps, const char *name)
{
	struct map *result = NULL;
	bool done = false;

	/* See locking/sorting note. */
	while (!done) {
		unsigned int i;

		down_read(maps__lock(maps));

		/* First check last found entry. */
		i = RC_CHK_ACCESS(maps)->last_search_by_name_idx;
		if (i < maps__nr_maps(maps) && maps__maps_by_name(maps)) {
			struct dso *dso = map__dso(maps__maps_by_name(maps)[i]);

			if (dso && strcmp(dso__short_name(dso), name) == 0) {
				result = map__get(maps__maps_by_name(maps)[i]);
				done = true;
			}
		}

		/* Second search sorted array. */
		if (!done && maps__maps_by_name_sorted(maps)) {
			struct map **mapp =
				bsearch(name, maps__maps_by_name(maps), maps__nr_maps(maps),
					sizeof(*mapp), map__strcmp_name);

			if (mapp) {
				result = map__get(*mapp);
				i = mapp - maps__maps_by_name(maps);
				RC_CHK_ACCESS(maps)->last_search_by_name_idx = i;
			}
			done = true;
		}
		up_read(maps__lock(maps));
		if (!done) {
			/* Sort and retry binary search. */
			if (maps__sort_by_name(maps)) {
				/*
				 * Memory allocation failed do linear search
				 * through address sorted maps.
				 */
				struct map **maps_by_address;
				unsigned int n;

				down_read(maps__lock(maps));
				maps_by_address =  maps__maps_by_address(maps);
				n = maps__nr_maps(maps);
				for (i = 0; i < n; i++) {
					struct map *pos = maps_by_address[i];
					struct dso *dso = map__dso(pos);

					if (dso && strcmp(dso__short_name(dso), name) == 0) {
						result = map__get(pos);
						break;
					}
				}
				up_read(maps__lock(maps));
				done = true;
			}
		}
	}
	return result;
}

struct map *maps__find_next_entry(struct maps *maps, struct map *map)
{
	unsigned int i;
	struct map *result = NULL;

	down_read(maps__lock(maps));
	while (!maps__maps_by_address_sorted(maps)) {
		up_read(maps__lock(maps));
		maps__sort_by_address(maps);
		down_read(maps__lock(maps));
	}
	i = maps__by_address_index(maps, map);
	if (++i < maps__nr_maps(maps))
		result = map__get(maps__maps_by_address(maps)[i]);

	up_read(maps__lock(maps));
	return result;
}

void maps__fixup_end(struct maps *maps)
{
	struct map **maps_by_address;
	unsigned int n;

	down_write(maps__lock(maps));
	if (!maps__maps_by_address_sorted(maps))
		__maps__sort_by_address(maps);

	maps_by_address = maps__maps_by_address(maps);
	n = maps__nr_maps(maps);
	for (unsigned int i = 1; i < n; i++) {
		struct map *prev = maps_by_address[i - 1];
		struct map *curr = maps_by_address[i];

		if (!map__end(prev) || map__end(prev) > map__start(curr))
			map__set_end(prev, map__start(curr));
	}

	/*
	 * We still haven't the actual symbols, so guess the
	 * last map final address.
	 */
	if (n > 0 && !map__end(maps_by_address[n - 1]))
		map__set_end(maps_by_address[n - 1], ~0ULL);

	RC_CHK_ACCESS(maps)->ends_broken = false;
	check_invariants(maps);

	up_write(maps__lock(maps));
}

/*
 * Merges map into maps by splitting the new map within the existing map
 * regions.
 */
int maps__merge_in(struct maps *kmaps, struct map *new_map)
{
	unsigned int first_after_, kmaps__nr_maps;
	struct map **kmaps_maps_by_address;
	struct map **merged_maps_by_address;
	unsigned int merged_nr_maps_allocated;

	/* First try under a read lock. */
	while (true) {
		down_read(maps__lock(kmaps));
		if (maps__maps_by_address_sorted(kmaps))
			break;

		up_read(maps__lock(kmaps));

		/* First after binary search requires sorted maps. Sort and try again. */
		maps__sort_by_address(kmaps);
	}
	first_after_ = first_ending_after(kmaps, new_map);
	kmaps_maps_by_address = maps__maps_by_address(kmaps);

	if (first_after_ >= maps__nr_maps(kmaps) ||
	    map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) {
		/* No overlap so regular insert suffices. */
		up_read(maps__lock(kmaps));
		return maps__insert(kmaps, new_map);
	}
	up_read(maps__lock(kmaps));

	/* Plain insert with a read-lock failed, try again now with the write lock. */
	down_write(maps__lock(kmaps));
	if (!maps__maps_by_address_sorted(kmaps))
		__maps__sort_by_address(kmaps);

	first_after_ = first_ending_after(kmaps, new_map);
	kmaps_maps_by_address = maps__maps_by_address(kmaps);
	kmaps__nr_maps = maps__nr_maps(kmaps);

	if (first_after_ >= kmaps__nr_maps ||
	    map__start(kmaps_maps_by_address[first_after_]) >= map__end(new_map)) {
		/* No overlap so regular insert suffices. */
		int ret = __maps__insert(kmaps, new_map);

		check_invariants(kmaps);
		up_write(maps__lock(kmaps));
		return ret;
	}
	/* Array to merge into, possibly 1 more for the sake of new_map. */
	merged_nr_maps_allocated = RC_CHK_ACCESS(kmaps)->nr_maps_allocated;
	if (kmaps__nr_maps + 1 == merged_nr_maps_allocated)
		merged_nr_maps_allocated++;

	merged_maps_by_address = malloc(merged_nr_maps_allocated * sizeof(*merged_maps_by_address));
	if (!merged_maps_by_address) {
		up_write(maps__lock(kmaps));
		return -ENOMEM;
	}
	maps__set_maps_by_address(kmaps, merged_maps_by_address);
	maps__set_maps_by_address_sorted(kmaps, true);
	__maps__free_maps_by_name(kmaps);
	maps__set_nr_maps_allocated(kmaps, merged_nr_maps_allocated);

	/* Copy entries before the new_map that can't overlap. */
	for (unsigned int i = 0; i < first_after_; i++)
		merged_maps_by_address[i] = map__get(kmaps_maps_by_address[i]);

	maps__set_nr_maps(kmaps, first_after_);

	/* Add the new map, it will be split when the later overlapping mappings are added. */
	__maps__insert(kmaps, new_map);

	/* Insert mappings after new_map, splitting new_map in the process. */
	for (unsigned int i = first_after_; i < kmaps__nr_maps; i++)
		__maps__fixup_overlap_and_insert(kmaps, kmaps_maps_by_address[i]);

	/* Copy the maps from merged into kmaps. */
	for (unsigned int i = 0; i < kmaps__nr_maps; i++)
		map__zput(kmaps_maps_by_address[i]);

	free(kmaps_maps_by_address);
	check_invariants(kmaps);
	up_write(maps__lock(kmaps));
	return 0;
}

void maps__load_first(struct maps *maps)
{
	down_read(maps__lock(maps));

	if (maps__nr_maps(maps) > 0)
		map__load(maps__maps_by_address(maps)[0]);

	up_read(maps__lock(maps));
}