libdwfl/cu.c

   1 /* Keeping track of DWARF compilation units in libdwfl.
   2    Copyright (C) 2005, 2006 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 -= mod->debug.bias;
 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 cu->die.cu->start + 3 * cu->die.cu->offset_size - 4 + 3;
 176 }
 177
 178 static int
 179 compare_cukey (const void *a, const void *b)
 180 {
 181   return cudie_offset (a) - cudie_offset (b);
 182 }
 183
 184 /* Intern the CU if necessary.  */
 185 static Dwfl_Error
 186 intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
 187 {
 188   struct Dwarf_CU dwkey;
 189   struct dwfl_cu key;
 190   key.die.cu = &dwkey;
 191   dwkey.offset_size = 0;
 192   dwkey.start = cuoff - (3 * 0 - 4 + 3);
 193   struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
 194   if (unlikely (found == NULL))
 195     return DWFL_E_NOMEM;
 196
 197   if (*found == &key || *found == NULL)
 198     {
 199       if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
 200         {
 201           /* This is the EOF marker.  Now we have interned all the CUs.
 202              One increment in MOD->lazycu counts not having hit EOF yet.  */
 203           *found = (void *) -1l;
 204           less_lazy (mod);
 205         }
 206       else
 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
 220           /* XXX use non-searching lookup */
 221           Dwarf_Die *die = INTUSE(dwarf_offdie) (mod->dw, cuoff, &cu->die);
 222           if (die == NULL)
 223             return DWFL_E_LIBDW;
 224           assert (die == &cu->die);
 225
 226           struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
 227                                                        * sizeof (mod->cu[0])));
 228           if (newvec == NULL)
 229             {
 230               free (cu);
 231               return DWFL_E_NOMEM;
 232             }
 233           mod->cu = newvec;
 234
 235           mod->cu[mod->ncu++] = cu;
 236           if (cu->die.cu->start == 0)
 237             mod->first_cu = cu;
 238
 239           *found = cu;
 240         }
 241     }
 242
 243   *result = *found;
 244   return DWFL_E_NOERROR;
 245 }
 246
 247
 248 /* Traverse all the CUs in the module.  */
 249
 250 Dwfl_Error
 251 internal_function_def
 252 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
 253                   struct dwfl_cu **cu)
 254 {
 255   Dwarf_Off cuoff;
 256   struct dwfl_cu **nextp;
 257
 258   if (lastcu == NULL)
 259     {
 260       /* Start the traversal.  */
 261       cuoff = 0;
 262       nextp = &mod->first_cu;
 263     }
 264   else
 265     {
 266       /* Continue following LASTCU.  */
 267       cuoff = lastcu->die.cu->end;
 268       nextp = &lastcu->next;
 269     }
 270
 271   if (*nextp == NULL)
 272     {
 273       size_t cuhdrsz;
 274       Dwarf_Off nextoff;
 275       int end = INTUSE(dwarf_nextcu) (mod->dw, cuoff, &nextoff, &cuhdrsz,
 276                                         NULL, NULL, NULL);
 277       if (end < 0)
 278         return DWFL_E_LIBDW;
 279       if (end > 0)
 280         {
 281           *cu = NULL;
 282           return DWFL_E_NOERROR;
 283         }
 284
 285       Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
 286       if (result != DWFL_E_NOERROR)
 287         return result;
 288
 289       if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
 290         (*nextp)->next = (void *) -1l;
 291     }
 292
 293   *cu = *nextp == (void *) -1l ? NULL : *nextp;
 294   return DWFL_E_NOERROR;
 295 }
 296
 297
 298 /* Intern the CU arange points to, if necessary.  */
 299
 300 static Dwfl_Error
 301 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
 302 {
 303   if (arange->cu == NULL)
 304     {
 305       const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
 306       Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
 307       if (result != DWFL_E_NOERROR)
 308         return result;
 309       assert (arange->cu != NULL && arange->cu != (void *) -1l);
 310       less_lazy (mod);          /* Each arange with null ->cu counts once.  */
 311     }
 312
 313   *cu = arange->cu;
 314   return DWFL_E_NOERROR;
 315 }
 316
 317 Dwfl_Error
 318 internal_function_def
 319 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
 320 {
 321   struct dwfl_arange *arange;
 322   return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
 323 }