1 /* Keeping track of DWARF compilation units in libdwfl.
2 Copyright (C) 2005-2010 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 struct Dwarf_CU dwkey;
175 struct dwfl_cu key;
176 key.die.cu = &dwkey;
177 dwkey.offset_size = 0;
178 dwkey.start = cuoff - (3 * 0 - 4 + 3);
179 struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
180 if (unlikely (found == NULL))
181 return DWFL_E_NOMEM;
182
183 if (*found == &key || *found == NULL)
184 {
185 if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
186 {
187 /* This is the EOF marker. Now we have interned all the CUs.
188 One increment in MOD->lazycu counts not having hit EOF yet. */
189 *found = (void *) -1l;
190 less_lazy (mod);
191 }
192 else
193 {
194 /* This is a new entry, meaning we haven't looked at this CU. */
195
196 *found = NULL;
197
198 struct dwfl_cu *cu = malloc (sizeof *cu);
199 if (unlikely (cu == NULL))
200 return DWFL_E_NOMEM;
201
202 cu->mod = mod;
203 cu->next = NULL;
204 cu->lines = NULL;
205
206 /* XXX use non-searching lookup */
207 Dwarf_Die *die = INTUSE(dwarf_offdie) (mod->dw, cuoff, &cu->die);
208 if (die == NULL)
209 {
210 free (cu);
211 return DWFL_E_LIBDW;
212 }
213 assert (die == &cu->die);
214
215 struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
216 * sizeof (mod->cu[0])));
217 if (newvec == NULL)
218 {
219 free (cu);
220 return DWFL_E_NOMEM;
221 }
222 mod->cu = newvec;
223
224 mod->cu[mod->ncu++] = cu;
225 if (cu->die.cu->start == 0)
226 mod->first_cu = cu;
227
228 *found = cu;
229 }
230 }
231
232 *result = *found;
233 return DWFL_E_NOERROR;
234 }
235
236
237 /* Traverse all the CUs in the module. */
238
239 Dwfl_Error
240 internal_function
__libdwfl_nextcu(Dwfl_Module * mod,struct dwfl_cu * lastcu,struct dwfl_cu ** cu)241 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
242 struct dwfl_cu **cu)
243 {
244 Dwarf_Off cuoff;
245 struct dwfl_cu **nextp;
246
247 if (lastcu == NULL)
248 {
249 /* Start the traversal. */
250 cuoff = 0;
251 nextp = &mod->first_cu;
252 }
253 else
254 {
255 /* Continue following LASTCU. */
256 cuoff = lastcu->die.cu->end;
257 nextp = &lastcu->next;
258 }
259
260 if (*nextp == NULL)
261 {
262 size_t cuhdrsz;
263 Dwarf_Off nextoff;
264 int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
265 NULL, NULL, NULL);
266 if (end < 0)
267 return DWFL_E_LIBDW;
268 if (end > 0)
269 {
270 *cu = NULL;
271 return DWFL_E_NOERROR;
272 }
273
274 Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
275 if (result != DWFL_E_NOERROR)
276 return result;
277
278 if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
279 (*nextp)->next = (void *) -1l;
280 }
281
282 *cu = *nextp == (void *) -1l ? NULL : *nextp;
283 return DWFL_E_NOERROR;
284 }
285
286
287 /* Intern the CU arange points to, if necessary. */
288
289 static Dwfl_Error
arangecu(Dwfl_Module * mod,struct dwfl_arange * arange,struct dwfl_cu ** cu)290 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
291 {
292 if (arange->cu == NULL)
293 {
294 const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
295 Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
296 if (result != DWFL_E_NOERROR)
297 return result;
298 assert (arange->cu != NULL && arange->cu != (void *) -1l);
299 less_lazy (mod); /* Each arange with null ->cu counts once. */
300 }
301
302 *cu = arange->cu;
303 return DWFL_E_NOERROR;
304 }
305
306 Dwfl_Error
307 internal_function
__libdwfl_addrcu(Dwfl_Module * mod,Dwarf_Addr addr,struct dwfl_cu ** cu)308 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
309 {
310 struct dwfl_arange *arange;
311 return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
312 }
313