Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469// 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_SUPPORTvoid *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;}
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_SUPPORTvoid *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}
/** * maps__mutate_mapping - Apply write-protected mutations to a map. * @maps: The maps collection containing the map. * @map: The map to mutate. * @mutate_cb: Callback function that performs the actual mutations. * @data: Private data passed to the callback. * * This acquires the write lock on the maps semaphore to safely protect * concurrent readers from seeing partially mutated or unsorted map boundaries. * * WARNING: Acquiring down_write() here can trigger a recursive self-deadlock if * the caller already holds the read lock (e.g., during maps__for_each_map() or * maps__find() iteration paths that trigger lazy symbol loading). To completely * avoid this deadlock, all kernel/module maps must be pre-loaded up-front (via * maps__load_maps()) under a clean, single-threaded context before entering * multi-threaded event processing loops. */int maps__mutate_mapping(struct maps *maps, struct map *map, int (*mutate_cb)(struct map *map, void *data), void *data){ int err = 0;
if (maps) { down_write(maps__lock(maps));
err = mutate_cb(map, data);
RC_CHK_ACCESS(maps)->maps_by_address_sorted = false; RC_CHK_ACCESS(maps)->maps_by_name_sorted = false;
up_write(maps__lock(maps));
#ifdef HAVE_LIBDW_SUPPORT libdw__invalidate_dwfl(maps, maps__libdw_addr_space_dwfl(maps));#endif } else { err = mutate_cb(map, data); }
return err;}
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;}
int maps__load_maps(struct maps *maps){ struct map **maps_copy; unsigned int nr_maps; int err = 0;
if (!maps) return 0;
down_read(maps__lock(maps)); nr_maps = maps__nr_maps(maps); if (nr_maps == 0) { up_read(maps__lock(maps)); return 0; } maps_copy = calloc(nr_maps, sizeof(*maps_copy)); if (!maps_copy) { up_read(maps__lock(maps)); return -ENOMEM; } for (unsigned int i = 0; i < nr_maps; i++) maps_copy[i] = map__get(maps__maps_by_address(maps)[i]); up_read(maps__lock(maps));
for (unsigned int i = 0; i < nr_maps; i++) { if (map__load(maps_copy[i]) < 0) { pr_warning("Failed to load map %s\n", dso__name(map__dso(maps_copy[i]))); err = -1; } map__put(maps_copy[i]); } free(maps_copy); return err;}
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 symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp){ struct map **maps_copy; unsigned int nr_maps; struct symbol *sym = NULL;
if (!maps) return NULL;
/* * First, ensure all maps are loaded. We pre-load them outside of any * read-to-write locks to avoid deadlocks. Even if some fail, we proceed. */ maps__load_maps(maps);
/* * Create a local snapshot of the maps while holding the read lock. * This prevents deadlocking if iteration triggers further map insertions. */ down_read(maps__lock(maps)); nr_maps = maps__nr_maps(maps); maps_copy = calloc(nr_maps, sizeof(*maps_copy)); if (maps_copy) { for (unsigned int i = 0; i < nr_maps; i++) { struct map *map = maps__maps_by_address(maps)[i];
maps_copy[i] = map__get(map); } } up_read(maps__lock(maps));
if (!maps_copy) return NULL;
for (unsigned int i = 0; i < nr_maps; i++) { struct map *map = maps_copy[i];
sym = map__find_symbol_by_name(map, name); if (sym && map__contains_symbol(map, sym)) { if (mapp) *mapp = map__get(map); break; } sym = NULL; }
for (unsigned int i = 0; i < nr_maps; i++) map__put(maps_copy[i]);
free(maps_copy); return 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));}