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