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