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             {
 208               free (cu);
 209               return DWFL_E_LIBDW;
 210             }
 211           assert (die == &cu->die);
 212
 213           struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
 214                                                        * sizeof (mod->cu[0])));
 215           if (newvec == NULL)
 216             {
 217               free (cu);
 218               return DWFL_E_NOMEM;
 219             }
 220           mod->cu = newvec;
 221
 222           mod->cu[mod->ncu++] = cu;
 223           if (cu->die.cu->start == 0)
 224             mod->first_cu = cu;
 225
 226           *found = cu;
 227         }
 228     }
 229
 230   *result = *found;
 231   return DWFL_E_NOERROR;
 232 }
 233
 234
 235 /* Traverse all the CUs in the module.  */
 236
 237 Dwfl_Error
 238 internal_function
 239 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
 240                   struct dwfl_cu **cu)
 241 {
 242   Dwarf_Off cuoff;
 243   struct dwfl_cu **nextp;
 244
 245   if (lastcu == NULL)
 246     {
 247       /* Start the traversal.  */
 248       cuoff = 0;
 249       nextp = &mod->first_cu;
 250     }
 251   else
 252     {
 253       /* Continue following LASTCU.  */
 254       cuoff = lastcu->die.cu->end;
 255       nextp = &lastcu->next;
 256     }
 257
 258   if (*nextp == NULL)
 259     {
 260       size_t cuhdrsz;
 261       Dwarf_Off nextoff;
 262       int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
 263                                       NULL, NULL, NULL);
 264       if (end < 0)
 265         return DWFL_E_LIBDW;
 266       if (end > 0)
 267         {
 268           *cu = NULL;
 269           return DWFL_E_NOERROR;
 270         }
 271
 272       Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
 273       if (result != DWFL_E_NOERROR)
 274         return result;
 275
 276       if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
 277         (*nextp)->next = (void *) -1l;
 278     }
 279
 280   *cu = *nextp == (void *) -1l ? NULL : *nextp;
 281   return DWFL_E_NOERROR;
 282 }
 283
 284
 285 /* Intern the CU arange points to, if necessary.  */
 286
 287 static Dwfl_Error
 288 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
 289 {
 290   if (arange->cu == NULL)
 291     {
 292       const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
 293       Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
 294       if (result != DWFL_E_NOERROR)
 295         return result;
 296       assert (arange->cu != NULL && arange->cu != (void *) -1l);
 297       less_lazy (mod);          /* Each arange with null ->cu counts once.  */
 298     }
 299
 300   *cu = arange->cu;
 301   return DWFL_E_NOERROR;
 302 }
 303
 304 Dwfl_Error
 305 internal_function
 306 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
 307 {
 308   struct dwfl_arange *arange;
 309   return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
 310 }