1 /* Keeping track of DWARF compilation units in libdwfl.
2 Copyright (C) 2005-2010, 2015, 2016, 2017 Red Hat, Inc.
3 This file is part of elfutils.
4
5 This file is free software; you can redistribute it and/or modify
6 it under the terms of either
7
8 * the GNU Lesser General Public License as published by the Free
9 Software Foundation; either version 3 of the License, or (at
10 your option) any later version
11
12 or
13
14 * the GNU General Public License as published by the Free
15 Software Foundation; either version 2 of the License, or (at
16 your option) any later version
17
18 or both in parallel, as here.
19
20 elfutils is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 General Public License for more details.
24
25 You should have received copies of the GNU General Public License and
26 the GNU Lesser General Public License along with this program. If
27 not, see <http://www.gnu.org/licenses/>. */
28
29 #ifdef HAVE_CONFIG_H
30 # include <config.h>
31 #endif
32
33 #include "libdwflP.h"
34 #include "../libdw/libdwP.h"
35 #include "../libdw/memory-access.h"
36 #include <search.h>
37
38
39 static inline Dwarf_Arange *
dwar(Dwfl_Module * mod,unsigned int idx)40 dwar (Dwfl_Module *mod, unsigned int idx)
41 {
42 return &mod->dw->aranges->info[mod->aranges[idx].arange];
43 }
44
45
46 static Dwfl_Error
addrarange(Dwfl_Module * mod,Dwarf_Addr addr,struct dwfl_arange ** arange)47 addrarange (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_arange **arange)
48 {
49 if (mod->aranges == NULL)
50 {
51 struct dwfl_arange *aranges = NULL;
52 Dwarf_Aranges *dwaranges = NULL;
53 size_t naranges;
54 if (INTUSE(dwarf_getaranges) (mod->dw, &dwaranges, &naranges) != 0)
55 return DWFL_E_LIBDW;
56
57 /* If the module has no aranges (when no code is included) we
58 allocate nothing. */
59 if (naranges != 0)
60 {
61 aranges = malloc (naranges * sizeof *aranges);
62 if (unlikely (aranges == NULL))
63 return DWFL_E_NOMEM;
64
65 /* libdw has sorted its list by address, which is how we want it.
66 But the sorted list is full of not-quite-contiguous runs pointing
67 to the same CU. We don't care about the little gaps inside the
68 module, we'll consider them part of the surrounding CU anyway.
69 Collect our own array with just one record for each run of ranges
70 pointing to one CU. */
71
72 naranges = 0;
73 Dwarf_Off lastcu = 0;
74 for (size_t i = 0; i < dwaranges->naranges; ++i)
75 if (i == 0 || dwaranges->info[i].offset != lastcu)
76 {
77 aranges[naranges].arange = i;
78 aranges[naranges].cu = NULL;
79 ++naranges;
80 lastcu = dwaranges->info[i].offset;
81 }
82 }
83
84 /* Store the final array, which is probably much smaller than before. */
85 mod->naranges = naranges;
86 mod->aranges = (realloc (aranges, naranges * sizeof aranges[0])
87 ?: aranges);
88 mod->lazycu += naranges;
89 }
90
91 /* The address must be inside the module to begin with. */
92 addr = dwfl_deadjust_dwarf_addr (mod, addr);
93
94 /* The ranges are sorted by address, so we can use binary search. */
95 size_t l = 0, u = mod->naranges;
96 while (l < u)
97 {
98 size_t idx = (l + u) / 2;
99 Dwarf_Addr start = dwar (mod, idx)->addr;
100 if (addr < start)
101 {
102 u = idx;
103 continue;
104 }
105 else if (addr > start)
106 {
107 if (idx + 1 < mod->naranges)
108 {
109 if (addr >= dwar (mod, idx + 1)->addr)
110 {
111 l = idx + 1;
112 continue;
113 }
114 }
115 else
116 {
117 /* It might be in the last range. */
118 const Dwarf_Arange *last
119 = &mod->dw->aranges->info[mod->dw->aranges->naranges - 1];
120 if (addr > last->addr + last->length)
121 break;
122 }
123 }
124
125 *arange = &mod->aranges[idx];
126 return DWFL_E_NOERROR;
127 }
128
129 return DWFL_E_ADDR_OUTOFRANGE;
130 }
131
132
133 static void
nofree(void * arg)134 nofree (void *arg)
135 {
136 struct dwfl_cu *cu = arg;
137 if (cu == (void *) -1l)
138 return;
139
140 assert (cu->mod->lazycu == 0);
141 }
142
143 /* One reason fewer to keep the lazy lookup table for CUs. */
144 static inline void
less_lazy(Dwfl_Module * mod)145 less_lazy (Dwfl_Module *mod)
146 {
147 if (--mod->lazycu > 0)
148 return;
149
150 /* We know about all the CUs now, we don't need this table. */
151 tdestroy (mod->lazy_cu_root, nofree);
152 mod->lazy_cu_root = NULL;
153 }
154
155 static inline Dwarf_Off
cudie_offset(const struct dwfl_cu * cu)156 cudie_offset (const struct dwfl_cu *cu)
157 {
158 return __libdw_first_die_off_from_cu (cu->die.cu);
159 }
160
161 static int
compare_cukey(const void * a,const void * b)162 compare_cukey (const void *a, const void *b)
163 {
164 Dwarf_Off a_off = cudie_offset (a);
165 Dwarf_Off b_off = cudie_offset (b);
166 return (a_off < b_off) ? -1 : ((a_off > b_off) ? 1 : 0);
167 }
168
169 /* Intern the CU if necessary. */
170 static Dwfl_Error
intern_cu(Dwfl_Module * mod,Dwarf_Off cuoff,struct dwfl_cu ** result)171 intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
172 {
173 if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
174 {
175 if (likely (mod->lazycu == 1))
176 {
177 /* This is the EOF marker. Now we have interned all the CUs.
178 One increment in MOD->lazycu counts not having hit EOF yet. */
179 *result = (void *) -1;
180 less_lazy (mod);
181 return DWFL_E_NOERROR;
182 }
183 else
184 {
185 /* Unexpected EOF, most likely a bogus aranges. */
186 return (DWFL_E (LIBDW, DWARF_E_INVALID_DWARF));
187 }
188 }
189
190 /* Make sure the cuoff points to a real DIE. */
191 Dwarf_Die cudie;
192 Dwarf_Die *die = INTUSE(dwarf_offdie) (mod->dw, cuoff, &cudie);
193 if (die == NULL)
194 return DWFL_E_LIBDW;
195
196 struct dwfl_cu key;
197 key.die.cu = die->cu;
198 struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
199 if (unlikely (found == NULL))
200 return DWFL_E_NOMEM;
201
202 if (*found == &key || *found == NULL)
203 {
204 /* This is a new entry, meaning we haven't looked at this CU. */
205
206 *found = NULL;
207
208 struct dwfl_cu *cu = malloc (sizeof *cu);
209 if (unlikely (cu == NULL))
210 return DWFL_E_NOMEM;
211
212 cu->mod = mod;
213 cu->next = NULL;
214 cu->lines = NULL;
215 cu->die = cudie;
216
217 struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
218 * sizeof (mod->cu[0])));
219 if (newvec == NULL)
220 {
221 free (cu);
222 return DWFL_E_NOMEM;
223 }
224 mod->cu = newvec;
225
226 mod->cu[mod->ncu++] = cu;
227 if (cu->die.cu->start == 0)
228 mod->first_cu = cu;
229
230 *found = cu;
231 }
232
233 *result = *found;
234 return DWFL_E_NOERROR;
235 }
236
237
238 /* Traverse all the CUs in the module. */
239
240 Dwfl_Error
241 internal_function
__libdwfl_nextcu(Dwfl_Module * mod,struct dwfl_cu * lastcu,struct dwfl_cu ** cu)242 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
243 struct dwfl_cu **cu)
244 {
245 Dwarf_Off cuoff;
246 struct dwfl_cu **nextp;
247
248 if (lastcu == NULL)
249 {
250 /* Start the traversal. */
251 cuoff = 0;
252 nextp = &mod->first_cu;
253 }
254 else
255 {
256 /* Continue following LASTCU. */
257 cuoff = lastcu->die.cu->end;
258 nextp = &lastcu->next;
259 }
260
261 if (*nextp == NULL)
262 {
263 size_t cuhdrsz;
264 Dwarf_Off nextoff;
265 int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
266 NULL, NULL, NULL);
267 if (end < 0)
268 return DWFL_E_LIBDW;
269 if (end > 0)
270 {
271 *cu = NULL;
272 return DWFL_E_NOERROR;
273 }
274
275 Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
276 if (result != DWFL_E_NOERROR)
277 return result;
278
279 if (*nextp != (void *) -1
280 && (*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
281 (*nextp)->next = (void *) -1l;
282 }
283
284 *cu = *nextp == (void *) -1l ? NULL : *nextp;
285 return DWFL_E_NOERROR;
286 }
287
288
289 /* Intern the CU arange points to, if necessary. */
290
291 static Dwfl_Error
arangecu(Dwfl_Module * mod,struct dwfl_arange * arange,struct dwfl_cu ** cu)292 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
293 {
294 if (arange->cu == NULL)
295 {
296 const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
297 Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
298 if (result != DWFL_E_NOERROR)
299 return result;
300 assert (arange->cu != NULL && arange->cu != (void *) -1l);
301 less_lazy (mod); /* Each arange with null ->cu counts once. */
302 }
303
304 *cu = arange->cu;
305 return DWFL_E_NOERROR;
306 }
307
308 Dwfl_Error
309 internal_function
__libdwfl_addrcu(Dwfl_Module * mod,Dwarf_Addr addr,struct dwfl_cu ** cu)310 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
311 {
312 struct dwfl_arange *arange;
313 return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
314 }
315