Quelle  maps.c   Sprache: 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 <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;
#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;
}
#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
 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);
}

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));
}

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;

 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]);
  else
   i++;
 }
 check_invariants(maps);
 up_write(maps__lock(maps));
}

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;
  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;
 FILE *fp = debug_file();
 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, fp);
   map__fprintf(pos, fp);
  }

  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, fp);
  }
  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, fp);
  }
  /*
 * 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);
   }

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

   if (i + 1 < maps__nr_maps(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);
    }

    check_invariants(maps);
    return err;
   }
   __maps__remove(maps, pos);
   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));

 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 {
    err = unwind__prepare_access(dest, new, NULL);
    if (!err) {
     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));
  if (!err) {
   RC_CHK_ACCESS(dest)->last_search_by_name_idx =
    RC_CHK_ACCESS(parent)->last_search_by_name_idx;
   maps__set_maps_by_name_sorted(dest,
      dest_maps_by_name &&
      maps__maps_by_name_sorted(parent));
  } else {
   RC_CHK_ACCESS(dest)->last_search_by_name_idx = 0;
   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 = unwind__prepare_access(dest, new, NULL);
    if (!err)
     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));
}