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 Red Hat elfutils.
   4
   5    Red Hat elfutils is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by the
   7    Free Software Foundation; version 2 of the License.
   8
   9    Red Hat elfutils is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License along
  15    with Red Hat elfutils; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
  17
  18    In addition, as a special exception, Red Hat, Inc. gives You the
  19    additional right to link the code of Red Hat elfutils with code licensed
  20    under any Open Source Initiative certified open source license
  21    (http://www.opensource.org/licenses/index.php) which requires the
  22    distribution of source code with any binary distribution and to
  23    distribute linked combinations of the two.  Non-GPL Code permitted under
  24    this exception must only link to the code of Red Hat elfutils through
  25    those well defined interfaces identified in the file named EXCEPTION
  26    found in the source code files (the "Approved Interfaces").  The files
  27    of Non-GPL Code may instantiate templates or use macros or inline
  28    functions from the Approved Interfaces without causing the resulting
  29    work to be covered by the GNU General Public License.  Only Red Hat,
  30    Inc. may make changes or additions to the list of Approved Interfaces.
  31    Red Hat's grant of this exception is conditioned upon your not adding
  32    any new exceptions.  If you wish to add a new Approved Interface or
  33    exception, please contact Red Hat.  You must obey the GNU General Public
  34    License in all respects for all of the Red Hat elfutils code and other
  35    code used in conjunction with Red Hat elfutils except the Non-GPL Code
  36    covered by this exception.  If you modify this file, you may extend this
  37    exception to your version of the file, but you are not obligated to do
  38    so.  If you do not wish to provide this exception without modification,
  39    you must delete this exception statement from your version and license
  40    this file solely under the GPL without exception.
  41
  42    Red Hat elfutils is an included package of the Open Invention Network.
  43    An included package of the Open Invention Network is a package for which
  44    Open Invention Network licensees cross-license their patents.  No patent
  45    license is granted, either expressly or impliedly, by designation as an
  46    included package.  Should you wish to participate in the Open Invention
  47    Network licensing program, please visit www.openinventionnetwork.com
  48    <http://www.openinventionnetwork.com>.  */
  49
  50 #include "libdwflP.h"
  51 #include "../libdw/libdwP.h"
  52 #include "../libdw/memory-access.h"
  53 #include <search.h>
  54
  55
  56 static inline Dwarf_Arange *
  57 dwar (Dwfl_Module *mod, unsigned int idx)
  58 {
  59   return &mod->dw->aranges->info[mod->aranges[idx].arange];
  60 }
  61
  62
  63 static Dwfl_Error
  64 addrarange (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_arange **arange)
  65 {
  66   if (mod->aranges == NULL)
  67     {
  68       struct dwfl_arange *aranges = NULL;
  69       Dwarf_Aranges *dwaranges = NULL;
  70       size_t naranges;
  71       if (INTUSE(dwarf_getaranges) (mod->dw, &dwaranges, &naranges) != 0)
  72         return DWFL_E_LIBDW;
  73
  74       /* If the module has no aranges (when no code is included) we
  75          allocate nothing.  */
  76       if (naranges != 0)
  77         {
  78           aranges = malloc (naranges * sizeof *aranges);
  79           if (unlikely (aranges == NULL))
  80             return DWFL_E_NOMEM;
  81
  82           /* libdw has sorted its list by address, which is how we want it.
  83              But the sorted list is full of not-quite-contiguous runs pointing
  84              to the same CU.  We don't care about the little gaps inside the
  85              module, we'll consider them part of the surrounding CU anyway.
  86              Collect our own array with just one record for each run of ranges
  87              pointing to one CU.  */
  88
  89           naranges = 0;
  90           Dwarf_Off lastcu = 0;
  91           for (size_t i = 0; i < dwaranges->naranges; ++i)
  92             if (i == 0 || dwaranges->info[i].offset != lastcu)
  93               {
  94                 aranges[naranges].arange = i;
  95                 aranges[naranges].cu = NULL;
  96                 ++naranges;
  97                 lastcu = dwaranges->info[i].offset;
  98               }
  99         }
 100
 101       /* Store the final array, which is probably much smaller than before.  */
 102       mod->naranges = naranges;
 103       mod->aranges = (realloc (aranges, naranges * sizeof aranges[0])
 104                       ?: aranges);
 105       mod->lazycu += naranges;
 106     }
 107
 108   /* The address must be inside the module to begin with.  */
 109   addr = dwfl_deadjust_dwarf_addr (mod, addr);
 110
 111   /* The ranges are sorted by address, so we can use binary search.  */
 112   size_t l = 0, u = mod->naranges;
 113   while (l < u)
 114     {
 115       size_t idx = (l + u) / 2;
 116       Dwarf_Addr start = dwar (mod, idx)->addr;
 117       if (addr < start)
 118         {
 119           u = idx;
 120           continue;
 121         }
 122       else if (addr > start)
 123         {
 124           if (idx + 1 < mod->naranges)
 125             {
 126               if (addr >= dwar (mod, idx + 1)->addr)
 127                 {
 128                   l = idx + 1;
 129                   continue;
 130                 }
 131             }
 132           else
 133             {
 134               /* It might be in the last range.  */
 135               const Dwarf_Arange *last
 136                 = &mod->dw->aranges->info[mod->dw->aranges->naranges - 1];
 137               if (addr > last->addr + last->length)
 138                 break;
 139             }
 140         }
 141
 142       *arange = &mod->aranges[idx];
 143       return DWFL_E_NOERROR;
 144     }
 145
 146   return DWFL_E_ADDR_OUTOFRANGE;
 147 }
 148
 149
 150 static void
 151 nofree (void *arg)
 152 {
 153   struct dwfl_cu *cu = arg;
 154   if (cu == (void *) -1l)
 155     return;
 156
 157   assert (cu->mod->lazycu == 0);
 158 }
 159
 160 /* One reason fewer to keep the lazy lookup table for CUs.  */
 161 static inline void
 162 less_lazy (Dwfl_Module *mod)
 163 {
 164   if (--mod->lazycu > 0)
 165     return;
 166
 167   /* We know about all the CUs now, we don't need this table.  */
 168   tdestroy (mod->lazy_cu_root, nofree);
 169   mod->lazy_cu_root = NULL;
 170 }
 171
 172 static inline Dwarf_Off
 173 cudie_offset (const struct dwfl_cu *cu)
 174 {
 175   return DIE_OFFSET_FROM_CU_OFFSET (cu->die.cu->start, cu->die.cu->offset_size,
 176                                     cu->die.cu->type_sig8 != 0);
 177 }
 178
 179 static int
 180 compare_cukey (const void *a, const void *b)
 181 {
 182   return cudie_offset (a) - cudie_offset (b);
 183 }
 184
 185 /* Intern the CU if necessary.  */
 186 static Dwfl_Error
 187 intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
 188 {
 189   struct Dwarf_CU dwkey;
 190   struct dwfl_cu key;
 191   key.die.cu = &dwkey;
 192   dwkey.offset_size = 0;
 193   dwkey.start = cuoff - (3 * 0 - 4 + 3);
 194   struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
 195   if (unlikely (found == NULL))
 196     return DWFL_E_NOMEM;
 197
 198   if (*found == &key || *found == NULL)
 199     {
 200       if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
 201         {
 202           /* This is the EOF marker.  Now we have interned all the CUs.
 203              One increment in MOD->lazycu counts not having hit EOF yet.  */
 204           *found = (void *) -1l;
 205           less_lazy (mod);
 206         }
 207       else
 208         {
 209           /* This is a new entry, meaning we haven't looked at this CU.  */
 210
 211           *found = NULL;
 212
 213           struct dwfl_cu *cu = malloc (sizeof *cu);
 214           if (unlikely (cu == NULL))
 215             return DWFL_E_NOMEM;
 216
 217           cu->mod = mod;
 218           cu->next = NULL;
 219           cu->lines = NULL;
 220
 221           /* XXX use non-searching lookup */
 222           Dwarf_Die *die = INTUSE(dwarf_offdie) (mod->dw, cuoff, &cu->die);
 223           if (die == NULL)
 224             return DWFL_E_LIBDW;
 225           assert (die == &cu->die);
 226
 227           struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
 228                                                        * sizeof (mod->cu[0])));
 229           if (newvec == NULL)
 230             {
 231               free (cu);
 232               return DWFL_E_NOMEM;
 233             }
 234           mod->cu = newvec;
 235
 236           mod->cu[mod->ncu++] = cu;
 237           if (cu->die.cu->start == 0)
 238             mod->first_cu = cu;
 239
 240           *found = cu;
 241         }
 242     }
 243
 244   *result = *found;
 245   return DWFL_E_NOERROR;
 246 }
 247
 248
 249 /* Traverse all the CUs in the module.  */
 250
 251 Dwfl_Error
 252 internal_function
 253 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
 254                   struct dwfl_cu **cu)
 255 {
 256   Dwarf_Off cuoff;
 257   struct dwfl_cu **nextp;
 258
 259   if (lastcu == NULL)
 260     {
 261       /* Start the traversal.  */
 262       cuoff = 0;
 263       nextp = &mod->first_cu;
 264     }
 265   else
 266     {
 267       /* Continue following LASTCU.  */
 268       cuoff = lastcu->die.cu->end;
 269       nextp = &lastcu->next;
 270     }
 271
 272   if (*nextp == NULL)
 273     {
 274       size_t cuhdrsz;
 275       Dwarf_Off nextoff;
 276       int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
 277                                       NULL, NULL, NULL);
 278       if (end < 0)
 279         return DWFL_E_LIBDW;
 280       if (end > 0)
 281         {
 282           *cu = NULL;
 283           return DWFL_E_NOERROR;
 284         }
 285
 286       Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
 287       if (result != DWFL_E_NOERROR)
 288         return result;
 289
 290       if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
 291         (*nextp)->next = (void *) -1l;
 292     }
 293
 294   *cu = *nextp == (void *) -1l ? NULL : *nextp;
 295   return DWFL_E_NOERROR;
 296 }
 297
 298
 299 /* Intern the CU arange points to, if necessary.  */
 300
 301 static Dwfl_Error
 302 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
 303 {
 304   if (arange->cu == NULL)
 305     {
 306       const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
 307       Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
 308       if (result != DWFL_E_NOERROR)
 309         return result;
 310       assert (arange->cu != NULL && arange->cu != (void *) -1l);
 311       less_lazy (mod);          /* Each arange with null ->cu counts once.  */
 312     }
 313
 314   *cu = arange->cu;
 315   return DWFL_E_NOERROR;
 316 }
 317
 318 Dwfl_Error
 319 internal_function
 320 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
 321 {
 322   struct dwfl_arange *arange;
 323   return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
 324 }