libdwfl/cu.c

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