1 /* Keeping track of DWARF compilation units in libdwfl.
2 Copyright (C) 2005, 2006 Red Hat, Inc.
3 This file is part of Red Hat elfutils.
4
5 Red Hat elfutils is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by the
7 Free Software Foundation; version 2 of the License.
8
9 Red Hat elfutils is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with Red Hat elfutils; if not, write to the Free Software Foundation,
16 Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
17
18 In addition, as a special exception, Red Hat, Inc. gives You the
19 additional right to link the code of Red Hat elfutils with code licensed
20 under any Open Source Initiative certified open source license
21 (http://www.opensource.org/licenses/index.php) which requires the
22 distribution of source code with any binary distribution and to
23 distribute linked combinations of the two. Non-GPL Code permitted under
24 this exception must only link to the code of Red Hat elfutils through
25 those well defined interfaces identified in the file named EXCEPTION
26 found in the source code files (the "Approved Interfaces"). The files
27 of Non-GPL Code may instantiate templates or use macros or inline
28 functions from the Approved Interfaces without causing the resulting
29 work to be covered by the GNU General Public License. Only Red Hat,
30 Inc. may make changes or additions to the list of Approved Interfaces.
31 Red Hat's grant of this exception is conditioned upon your not adding
32 any new exceptions. If you wish to add a new Approved Interface or
33 exception, please contact Red Hat. You must obey the GNU General Public
34 License in all respects for all of the Red Hat elfutils code and other
35 code used in conjunction with Red Hat elfutils except the Non-GPL Code
36 covered by this exception. If you modify this file, you may extend this
37 exception to your version of the file, but you are not obligated to do
38 so. If you do not wish to provide this exception without modification,
39 you must delete this exception statement from your version and license
40 this file solely under the GPL without exception.
41
42 Red Hat elfutils is an included package of the Open Invention Network.
43 An included package of the Open Invention Network is a package for which
44 Open Invention Network licensees cross-license their patents. No patent
45 license is granted, either expressly or impliedly, by designation as an
46 included package. Should you wish to participate in the Open Invention
47 Network licensing program, please visit www.openinventionnetwork.com
48 <http://www.openinventionnetwork.com>. */
49
50 #include "libdwflP.h"
51 #include "../libdw/libdwP.h"
52 #include "../libdw/memory-access.h"
53 #include <search.h>
54
55
56 static inline Dwarf_Arange *
dwar(Dwfl_Module * mod,unsigned int idx)57 dwar (Dwfl_Module *mod, unsigned int idx)
58 {
59 return &mod->dw->aranges->info[mod->aranges[idx].arange];
60 }
61
62
63 static Dwfl_Error
addrarange(Dwfl_Module * mod,Dwarf_Addr addr,struct dwfl_arange ** arange)64 addrarange (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_arange **arange)
65 {
66 if (mod->aranges == NULL)
67 {
68 struct dwfl_arange *aranges = NULL;
69 Dwarf_Aranges *dwaranges = NULL;
70 size_t naranges;
71 if (INTUSE(dwarf_getaranges) (mod->dw, &dwaranges, &naranges) != 0)
72 return DWFL_E_LIBDW;
73
74 /* If the module has no aranges (when no code is included) we
75 allocate nothing. */
76 if (naranges != 0)
77 {
78 aranges = malloc (naranges * sizeof *aranges);
79 if (unlikely (aranges == NULL))
80 return DWFL_E_NOMEM;
81
82 /* libdw has sorted its list by address, which is how we want it.
83 But the sorted list is full of not-quite-contiguous runs pointing
84 to the same CU. We don't care about the little gaps inside the
85 module, we'll consider them part of the surrounding CU anyway.
86 Collect our own array with just one record for each run of ranges
87 pointing to one CU. */
88
89 naranges = 0;
90 Dwarf_Off lastcu = 0;
91 for (size_t i = 0; i < dwaranges->naranges; ++i)
92 if (i == 0 || dwaranges->info[i].offset != lastcu)
93 {
94 aranges[naranges].arange = i;
95 aranges[naranges].cu = NULL;
96 ++naranges;
97 lastcu = dwaranges->info[i].offset;
98 }
99 }
100
101 /* Store the final array, which is probably much smaller than before. */
102 mod->naranges = naranges;
103 mod->aranges = (realloc (aranges, naranges * sizeof aranges[0])
104 ?: aranges);
105 mod->lazycu += naranges;
106 }
107
108 /* The address must be inside the module to begin with. */
109 addr -= mod->debug.bias;
110
111 /* The ranges are sorted by address, so we can use binary search. */
112 size_t l = 0, u = mod->naranges;
113 while (l < u)
114 {
115 size_t idx = (l + u) / 2;
116 Dwarf_Addr start = dwar (mod, idx)->addr;
117 if (addr < start)
118 {
119 u = idx;
120 continue;
121 }
122 else if (addr > start)
123 {
124 if (idx + 1 < mod->naranges)
125 {
126 if (addr >= dwar (mod, idx + 1)->addr)
127 {
128 l = idx + 1;
129 continue;
130 }
131 }
132 else
133 {
134 /* It might be in the last range. */
135 const Dwarf_Arange *last
136 = &mod->dw->aranges->info[mod->dw->aranges->naranges - 1];
137 if (addr > last->addr + last->length)
138 break;
139 }
140 }
141
142 *arange = &mod->aranges[idx];
143 return DWFL_E_NOERROR;
144 }
145
146 return DWFL_E_ADDR_OUTOFRANGE;
147 }
148
149
150 static void
nofree(void * arg)151 nofree (void *arg)
152 {
153 struct dwfl_cu *cu = arg;
154 if (cu == (void *) -1l)
155 return;
156
157 assert (cu->mod->lazycu == 0);
158 }
159
160 /* One reason fewer to keep the lazy lookup table for CUs. */
161 static inline void
less_lazy(Dwfl_Module * mod)162 less_lazy (Dwfl_Module *mod)
163 {
164 if (--mod->lazycu > 0)
165 return;
166
167 /* We know about all the CUs now, we don't need this table. */
168 tdestroy (mod->lazy_cu_root, nofree);
169 mod->lazy_cu_root = NULL;
170 }
171
172 static inline Dwarf_Off
cudie_offset(const struct dwfl_cu * cu)173 cudie_offset (const struct dwfl_cu *cu)
174 {
175 return cu->die.cu->start + 3 * cu->die.cu->offset_size - 4 + 3;
176 }
177
178 static int
compare_cukey(const void * a,const void * b)179 compare_cukey (const void *a, const void *b)
180 {
181 return cudie_offset (a) - cudie_offset (b);
182 }
183
184 /* Intern the CU if necessary. */
185 static Dwfl_Error
intern_cu(Dwfl_Module * mod,Dwarf_Off cuoff,struct dwfl_cu ** result)186 intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
187 {
188 struct Dwarf_CU dwkey;
189 struct dwfl_cu key;
190 key.die.cu = &dwkey;
191 dwkey.offset_size = 0;
192 dwkey.start = cuoff - (3 * 0 - 4 + 3);
193 struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
194 if (unlikely (found == NULL))
195 return DWFL_E_NOMEM;
196
197 if (*found == &key || *found == NULL)
198 {
199 if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
200 {
201 /* This is the EOF marker. Now we have interned all the CUs.
202 One increment in MOD->lazycu counts not having hit EOF yet. */
203 *found = (void *) -1l;
204 less_lazy (mod);
205 }
206 else
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
220 /* XXX use non-searching lookup */
221 Dwarf_Die *die = INTUSE(dwarf_offdie) (mod->dw, cuoff, &cu->die);
222 if (die == NULL)
223 return DWFL_E_LIBDW;
224 assert (die == &cu->die);
225
226 struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
227 * sizeof (mod->cu[0])));
228 if (newvec == NULL)
229 {
230 free (cu);
231 return DWFL_E_NOMEM;
232 }
233 mod->cu = newvec;
234
235 mod->cu[mod->ncu++] = cu;
236 if (cu->die.cu->start == 0)
237 mod->first_cu = cu;
238
239 *found = cu;
240 }
241 }
242
243 *result = *found;
244 return DWFL_E_NOERROR;
245 }
246
247
248 /* Traverse all the CUs in the module. */
249
250 Dwfl_Error
251 internal_function
__libdwfl_nextcu(Dwfl_Module * mod,struct dwfl_cu * lastcu,struct dwfl_cu ** cu)252 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
253 struct dwfl_cu **cu)
254 {
255 Dwarf_Off cuoff;
256 struct dwfl_cu **nextp;
257
258 if (lastcu == NULL)
259 {
260 /* Start the traversal. */
261 cuoff = 0;
262 nextp = &mod->first_cu;
263 }
264 else
265 {
266 /* Continue following LASTCU. */
267 cuoff = lastcu->die.cu->end;
268 nextp = &lastcu->next;
269 }
270
271 if (*nextp == NULL)
272 {
273 size_t cuhdrsz;
274 Dwarf_Off nextoff;
275 int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
276 NULL, NULL, NULL);
277 if (end < 0)
278 return DWFL_E_LIBDW;
279 if (end > 0)
280 {
281 *cu = NULL;
282 return DWFL_E_NOERROR;
283 }
284
285 Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
286 if (result != DWFL_E_NOERROR)
287 return result;
288
289 if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
290 (*nextp)->next = (void *) -1l;
291 }
292
293 *cu = *nextp == (void *) -1l ? NULL : *nextp;
294 return DWFL_E_NOERROR;
295 }
296
297
298 /* Intern the CU arange points to, if necessary. */
299
300 static Dwfl_Error
arangecu(Dwfl_Module * mod,struct dwfl_arange * arange,struct dwfl_cu ** cu)301 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
302 {
303 if (arange->cu == NULL)
304 {
305 const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
306 Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
307 if (result != DWFL_E_NOERROR)
308 return result;
309 assert (arange->cu != NULL && arange->cu != (void *) -1l);
310 less_lazy (mod); /* Each arange with null ->cu counts once. */
311 }
312
313 *cu = arange->cu;
314 return DWFL_E_NOERROR;
315 }
316
317 Dwfl_Error
318 internal_function
__libdwfl_addrcu(Dwfl_Module * mod,Dwarf_Addr addr,struct dwfl_cu ** cu)319 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
320 {
321 struct dwfl_arange *arange;
322 return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
323 }
324