libdwfl/cu.c

   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 }