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