1 // SPDX-License-Identifier: GPL-2.0
2 #include <errno.h>
3 #include <stdlib.h>
4 #include <linux/zalloc.h>
5 #include "debug.h"
6 #include "dso.h"
7 #include "map.h"
8 #include "maps.h"
9 #include "thread.h"
10 #include "ui/ui.h"
11 #include "unwind.h"
12
13 static void __maps__insert(struct maps *maps, struct map *map);
14
maps__init(struct maps * maps,struct machine * machine)15 static void maps__init(struct maps *maps, struct machine *machine)
16 {
17 maps->entries = RB_ROOT;
18 init_rwsem(&maps->lock);
19 maps->machine = machine;
20 maps->last_search_by_name = NULL;
21 maps->nr_maps = 0;
22 maps->maps_by_name = NULL;
23 refcount_set(&maps->refcnt, 1);
24 }
25
__maps__free_maps_by_name(struct maps * maps)26 static void __maps__free_maps_by_name(struct maps *maps)
27 {
28 /*
29 * Free everything to try to do it from the rbtree in the next search
30 */
31 zfree(&maps->maps_by_name);
32 maps->nr_maps_allocated = 0;
33 }
34
maps__insert(struct maps * maps,struct map * map)35 void maps__insert(struct maps *maps, struct map *map)
36 {
37 down_write(&maps->lock);
38 __maps__insert(maps, map);
39 ++maps->nr_maps;
40
41 if (map->dso && map->dso->kernel) {
42 struct kmap *kmap = map__kmap(map);
43
44 if (kmap)
45 kmap->kmaps = maps;
46 else
47 pr_err("Internal error: kernel dso with non kernel map\n");
48 }
49
50
51 /*
52 * If we already performed some search by name, then we need to add the just
53 * inserted map and resort.
54 */
55 if (maps->maps_by_name) {
56 if (maps->nr_maps > maps->nr_maps_allocated) {
57 int nr_allocate = maps->nr_maps * 2;
58 struct map **maps_by_name = realloc(maps->maps_by_name, nr_allocate * sizeof(map));
59
60 if (maps_by_name == NULL) {
61 __maps__free_maps_by_name(maps);
62 up_write(&maps->lock);
63 return;
64 }
65
66 maps->maps_by_name = maps_by_name;
67 maps->nr_maps_allocated = nr_allocate;
68 }
69 maps->maps_by_name[maps->nr_maps - 1] = map;
70 __maps__sort_by_name(maps);
71 }
72 up_write(&maps->lock);
73 }
74
__maps__remove(struct maps * maps,struct map * map)75 static void __maps__remove(struct maps *maps, struct map *map)
76 {
77 rb_erase_init(&map->rb_node, &maps->entries);
78 map__put(map);
79 }
80
maps__remove(struct maps * maps,struct map * map)81 void maps__remove(struct maps *maps, struct map *map)
82 {
83 down_write(&maps->lock);
84 if (maps->last_search_by_name == map)
85 maps->last_search_by_name = NULL;
86
87 __maps__remove(maps, map);
88 --maps->nr_maps;
89 if (maps->maps_by_name)
90 __maps__free_maps_by_name(maps);
91 up_write(&maps->lock);
92 }
93
__maps__purge(struct maps * maps)94 static void __maps__purge(struct maps *maps)
95 {
96 struct map *pos, *next;
97
98 maps__for_each_entry_safe(maps, pos, next) {
99 rb_erase_init(&pos->rb_node, &maps->entries);
100 map__put(pos);
101 }
102 }
103
maps__exit(struct maps * maps)104 static void maps__exit(struct maps *maps)
105 {
106 down_write(&maps->lock);
107 __maps__purge(maps);
108 up_write(&maps->lock);
109 }
110
maps__empty(struct maps * maps)111 bool maps__empty(struct maps *maps)
112 {
113 return !maps__first(maps);
114 }
115
maps__new(struct machine * machine)116 struct maps *maps__new(struct machine *machine)
117 {
118 struct maps *maps = zalloc(sizeof(*maps));
119
120 if (maps != NULL)
121 maps__init(maps, machine);
122
123 return maps;
124 }
125
maps__delete(struct maps * maps)126 void maps__delete(struct maps *maps)
127 {
128 maps__exit(maps);
129 unwind__finish_access(maps);
130 free(maps);
131 }
132
maps__put(struct maps * maps)133 void maps__put(struct maps *maps)
134 {
135 if (maps && refcount_dec_and_test(&maps->refcnt))
136 maps__delete(maps);
137 }
138
maps__find_symbol(struct maps * maps,u64 addr,struct map ** mapp)139 struct symbol *maps__find_symbol(struct maps *maps, u64 addr, struct map **mapp)
140 {
141 struct map *map = maps__find(maps, addr);
142
143 /* Ensure map is loaded before using map->map_ip */
144 if (map != NULL && map__load(map) >= 0) {
145 if (mapp != NULL)
146 *mapp = map;
147 return map__find_symbol(map, map->map_ip(map, addr));
148 }
149
150 return NULL;
151 }
152
maps__find_symbol_by_name(struct maps * maps,const char * name,struct map ** mapp)153 struct symbol *maps__find_symbol_by_name(struct maps *maps, const char *name, struct map **mapp)
154 {
155 struct symbol *sym;
156 struct map *pos;
157
158 down_read(&maps->lock);
159
160 maps__for_each_entry(maps, pos) {
161 sym = map__find_symbol_by_name(pos, name);
162
163 if (sym == NULL)
164 continue;
165 if (!map__contains_symbol(pos, sym)) {
166 sym = NULL;
167 continue;
168 }
169 if (mapp != NULL)
170 *mapp = pos;
171 goto out;
172 }
173
174 sym = NULL;
175 out:
176 up_read(&maps->lock);
177 return sym;
178 }
179
maps__find_ams(struct maps * maps,struct addr_map_symbol * ams)180 int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)
181 {
182 if (ams->addr < ams->ms.map->start || ams->addr >= ams->ms.map->end) {
183 if (maps == NULL)
184 return -1;
185 ams->ms.map = maps__find(maps, ams->addr);
186 if (ams->ms.map == NULL)
187 return -1;
188 }
189
190 ams->al_addr = ams->ms.map->map_ip(ams->ms.map, ams->addr);
191 ams->ms.sym = map__find_symbol(ams->ms.map, ams->al_addr);
192
193 return ams->ms.sym ? 0 : -1;
194 }
195
maps__fprintf(struct maps * maps,FILE * fp)196 size_t maps__fprintf(struct maps *maps, FILE *fp)
197 {
198 size_t printed = 0;
199 struct map *pos;
200
201 down_read(&maps->lock);
202
203 maps__for_each_entry(maps, pos) {
204 printed += fprintf(fp, "Map:");
205 printed += map__fprintf(pos, fp);
206 if (verbose > 2) {
207 printed += dso__fprintf(pos->dso, fp);
208 printed += fprintf(fp, "--\n");
209 }
210 }
211
212 up_read(&maps->lock);
213
214 return printed;
215 }
216
maps__fixup_overlappings(struct maps * maps,struct map * map,FILE * fp)217 int maps__fixup_overlappings(struct maps *maps, struct map *map, FILE *fp)
218 {
219 struct rb_root *root;
220 struct rb_node *next, *first;
221 int err = 0;
222
223 down_write(&maps->lock);
224
225 root = &maps->entries;
226
227 /*
228 * Find first map where end > map->start.
229 * Same as find_vma() in kernel.
230 */
231 next = root->rb_node;
232 first = NULL;
233 while (next) {
234 struct map *pos = rb_entry(next, struct map, rb_node);
235
236 if (pos->end > map->start) {
237 first = next;
238 if (pos->start <= map->start)
239 break;
240 next = next->rb_left;
241 } else
242 next = next->rb_right;
243 }
244
245 next = first;
246 while (next) {
247 struct map *pos = rb_entry(next, struct map, rb_node);
248 next = rb_next(&pos->rb_node);
249
250 /*
251 * Stop if current map starts after map->end.
252 * Maps are ordered by start: next will not overlap for sure.
253 */
254 if (pos->start >= map->end)
255 break;
256
257 if (verbose >= 2) {
258
259 if (use_browser) {
260 pr_debug("overlapping maps in %s (disable tui for more info)\n",
261 map->dso->name);
262 } else {
263 fputs("overlapping maps:\n", fp);
264 map__fprintf(map, fp);
265 map__fprintf(pos, fp);
266 }
267 }
268
269 rb_erase_init(&pos->rb_node, root);
270 /*
271 * Now check if we need to create new maps for areas not
272 * overlapped by the new map:
273 */
274 if (map->start > pos->start) {
275 struct map *before = map__clone(pos);
276
277 if (before == NULL) {
278 err = -ENOMEM;
279 goto put_map;
280 }
281
282 before->end = map->start;
283 __maps__insert(maps, before);
284 if (verbose >= 2 && !use_browser)
285 map__fprintf(before, fp);
286 map__put(before);
287 }
288
289 if (map->end < pos->end) {
290 struct map *after = map__clone(pos);
291
292 if (after == NULL) {
293 err = -ENOMEM;
294 goto put_map;
295 }
296
297 after->start = map->end;
298 after->pgoff += map->end - pos->start;
299 assert(pos->map_ip(pos, map->end) == after->map_ip(after, map->end));
300 __maps__insert(maps, after);
301 if (verbose >= 2 && !use_browser)
302 map__fprintf(after, fp);
303 map__put(after);
304 }
305 put_map:
306 map__put(pos);
307
308 if (err)
309 goto out;
310 }
311
312 err = 0;
313 out:
314 up_write(&maps->lock);
315 return err;
316 }
317
318 /*
319 * XXX This should not really _copy_ te maps, but refcount them.
320 */
maps__clone(struct thread * thread,struct maps * parent)321 int maps__clone(struct thread *thread, struct maps *parent)
322 {
323 struct maps *maps = thread->maps;
324 int err;
325 struct map *map;
326
327 down_read(&parent->lock);
328
329 maps__for_each_entry(parent, map) {
330 struct map *new = map__clone(map);
331
332 if (new == NULL) {
333 err = -ENOMEM;
334 goto out_unlock;
335 }
336
337 err = unwind__prepare_access(maps, new, NULL);
338 if (err)
339 goto out_unlock;
340
341 maps__insert(maps, new);
342 map__put(new);
343 }
344
345 err = 0;
346 out_unlock:
347 up_read(&parent->lock);
348 return err;
349 }
350
__maps__insert(struct maps * maps,struct map * map)351 static void __maps__insert(struct maps *maps, struct map *map)
352 {
353 struct rb_node **p = &maps->entries.rb_node;
354 struct rb_node *parent = NULL;
355 const u64 ip = map->start;
356 struct map *m;
357
358 while (*p != NULL) {
359 parent = *p;
360 m = rb_entry(parent, struct map, rb_node);
361 if (ip < m->start)
362 p = &(*p)->rb_left;
363 else
364 p = &(*p)->rb_right;
365 }
366
367 rb_link_node(&map->rb_node, parent, p);
368 rb_insert_color(&map->rb_node, &maps->entries);
369 map__get(map);
370 }
371
maps__find(struct maps * maps,u64 ip)372 struct map *maps__find(struct maps *maps, u64 ip)
373 {
374 struct rb_node *p;
375 struct map *m;
376
377 down_read(&maps->lock);
378
379 p = maps->entries.rb_node;
380 while (p != NULL) {
381 m = rb_entry(p, struct map, rb_node);
382 if (ip < m->start)
383 p = p->rb_left;
384 else if (ip >= m->end)
385 p = p->rb_right;
386 else
387 goto out;
388 }
389
390 m = NULL;
391 out:
392 up_read(&maps->lock);
393 return m;
394 }
395
maps__first(struct maps * maps)396 struct map *maps__first(struct maps *maps)
397 {
398 struct rb_node *first = rb_first(&maps->entries);
399
400 if (first)
401 return rb_entry(first, struct map, rb_node);
402 return NULL;
403 }
404