Home | History | Annotate | Download | only in libdwfl 
      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 *
     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
     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
    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
    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
    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
    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
    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
    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
    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
    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