libdwfl/cu.c

   1 /* Keeping track of DWARF compilation units in libdwfl.
   2    Copyright (C) 2005 Red Hat, Inc.
   3
   4    This program is Open Source software; you can redistribute it and/or
   5    modify it under the terms of the Open Software License version 1.0 as
   6    published by the Open Source Initiative.
   7
   8    You should have received a copy of the Open Software License along
   9    with this program; if not, you may obtain a copy of the Open Software
  10    License version 1.0 from http://www.opensource.org/licenses/osl.php or
  11    by writing the Open Source Initiative c/o Lawrence Rosen, Esq.,
  12    3001 King Ranch Road, Ukiah, CA 95482.   */
  13
  14 #include "libdwflP.h"
  15 #include "../libdw/libdwP.h"
  16 #include "../libdw/memory-access.h"
  17 #include <search.h>
  18
  19
  20 static inline Dwarf_Arange *
  21 dwar (Dwfl_Module *mod, unsigned int idx)
  22 {
  23   return &mod->dw->aranges->info[mod->aranges[idx].arange];
  24 }
  25
  26
  27 static Dwfl_Error
  28 addrarange (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_arange **arange)
  29 {
  30   if (mod->aranges == NULL)
  31     {
  32       Dwarf_Aranges *dwaranges;
  33       if (dwarf_getaranges (mod->dw, &dwaranges, NULL) != 0)
  34         return DWFL_E_LIBDW;
  35
  36       struct dwfl_arange *aranges = malloc (dwaranges->naranges
  37                                             * sizeof *aranges);
  38       if (unlikely (aranges == NULL))
  39         return DWFL_E_NOMEM;
  40
  41       /* libdw has sorted its list by address, which is how we want it.
  42          But the sorted list is full of not-quite-contiguous runs pointing
  43          to the same CU.  We don't care about the little gaps inside the
  44          module, we'll consider them part of the surrounding CU anyway.
  45          Collect our own array with just one record for each run of ranges
  46          pointing to one CU.  */
  47
  48       size_t naranges = 0;
  49       Dwarf_Off lastcu = 0;
  50       for (size_t i = 0; i < dwaranges->naranges; ++i)
  51         if (i == 0 || dwaranges->info[i].offset != lastcu)
  52           {
  53             aranges[naranges].arange = i;
  54             aranges[naranges].cu = NULL;
  55             ++naranges;
  56             lastcu = dwaranges->info[i].offset;
  57           }
  58
  59       /* Store the final array, which is probably much smaller than before.  */
  60       mod->naranges = naranges;
  61       mod->aranges = (realloc (aranges, naranges * sizeof aranges[0])
  62                       ?: aranges);
  63       mod->lazycu += naranges;
  64     }
  65
  66   /* The address must be inside the module to begin with.  */
  67   addr -= mod->debug.bias;
  68
  69   /* The ranges are sorted by address, so we can use binary search.  */
  70   size_t l = 0, u = mod->naranges;
  71   while (l < u)
  72     {
  73       size_t idx = (l + u) / 2;
  74       Dwarf_Addr start = dwar (mod, idx)->addr;
  75       if (addr < start)
  76         {
  77           u = idx;
  78           continue;
  79         }
  80       else if (addr > start)
  81         {
  82           if (idx + 1 < mod->naranges)
  83             {
  84               if (addr >= dwar (mod, idx + 1)->addr)
  85                 {
  86                   l = idx + 1;
  87                   continue;
  88                 }
  89             }
  90           else
  91             {
  92               /* It might be in the last range.  */
  93               const Dwarf_Arange *last
  94                 = &mod->dw->aranges->info[mod->dw->aranges->naranges - 1];
  95               if (addr > last->addr + last->length)
  96                 break;
  97             }
  98         }
  99
 100       *arange = &mod->aranges[idx];
 101       return DWFL_E_NOERROR;
 102     }
 103
 104   return DWFL_E_ADDR_OUTOFRANGE;
 105 }
 106
 107
 108 static void
 109 nofree (void *arg)
 110 {
 111   struct dwfl_cu *cu = arg;
 112   if (cu == (void *) -1l)
 113     return;
 114
 115   assert (cu->mod->lazycu == 0);
 116 }
 117
 118 /* One reason fewer to keep the lazy lookup table for CUs.  */
 119 static inline void
 120 less_lazy (Dwfl_Module *mod)
 121 {
 122   if (--mod->lazycu > 0)
 123     return;
 124
 125   /* We know about all the CUs now, we don't need this table.  */
 126   tdestroy (mod->lazy_cu_root, nofree);
 127   mod->lazy_cu_root = NULL;
 128 }
 129
 130 static inline Dwarf_Off
 131 cudie_offset (const struct dwfl_cu *cu)
 132 {
 133   return cu->die.cu->start + 3 * cu->die.cu->offset_size - 4 + 3;
 134 }
 135
 136 static int
 137 compare_cukey (const void *a, const void *b)
 138 {
 139   return cudie_offset (a) - cudie_offset (b);
 140 }
 141
 142 /* Intern the CU if necessary.  */
 143 static Dwfl_Error
 144 intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
 145 {
 146   struct Dwarf_CU dwkey;
 147   struct dwfl_cu key;
 148   key.die.cu = &dwkey;
 149   dwkey.offset_size = 0;
 150   dwkey.start = cuoff - (3 * 0 - 4 + 3);
 151   struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
 152   if (unlikely (found == NULL))
 153     return DWFL_E_NOMEM;
 154
 155   if (*found == &key || *found == NULL)
 156     {
 157       if (unlikely (cuoff + 4 >= mod->dw->sectiondata[IDX_debug_info]->d_size))
 158         {
 159           /* This is the EOF marker.  Now we have interned all the CUs.
 160              One increment in MOD->lazycu counts not having hit EOF yet.  */
 161           *found = (void *) -1l;
 162           less_lazy (mod);
 163         }
 164       else
 165         {
 166           /* This is a new entry, meaning we haven't looked at this CU.  */
 167
 168           *found = NULL;
 169
 170           struct dwfl_cu *cu = malloc (sizeof *cu);
 171           if (unlikely (cu == NULL))
 172             return DWFL_E_NOMEM;
 173
 174           cu->mod = mod;
 175           cu->next = NULL;
 176           cu->lines = NULL;
 177
 178           /* XXX use non-searching lookup */
 179           Dwarf_Die *die = dwarf_offdie (mod->dw, cuoff, &cu->die);
 180           if (die == NULL)
 181             return DWFL_E_LIBDW;
 182           assert (die == &cu->die);
 183
 184           struct dwfl_cu **newvec = realloc (mod->cu, ((mod->ncu + 1)
 185                                                        * sizeof (mod->cu[0])));
 186           if (newvec == NULL)
 187             {
 188               free (cu);
 189               return DWFL_E_NOMEM;
 190             }
 191           mod->cu = newvec;
 192
 193           mod->cu[mod->ncu++] = cu;
 194           if (cu->die.cu->start == 0)
 195             mod->first_cu = cu;
 196
 197           *found = cu;
 198         }
 199     }
 200
 201   *result = *found;
 202   return DWFL_E_NOERROR;
 203 }
 204
 205
 206 /* Traverse all the CUs in the module.  */
 207
 208 Dwfl_Error
 209 internal_function_def
 210 __libdwfl_nextcu (Dwfl_Module *mod, struct dwfl_cu *lastcu,
 211                   struct dwfl_cu **cu)
 212 {
 213   Dwarf_Off cuoff;
 214   struct dwfl_cu **nextp;
 215
 216   if (lastcu == NULL)
 217     {
 218       /* Start the traversal.  */
 219       cuoff = 0;
 220       nextp = &mod->first_cu;
 221     }
 222   else
 223     {
 224       /* Continue following LASTCU.  */
 225       cuoff = lastcu->die.cu->end;
 226       nextp = &lastcu->next;
 227     }
 228
 229   if (*nextp == NULL)
 230     {
 231       size_t cuhdrsz;
 232       Dwarf_Off nextoff;
 233       if (dwarf_nextcu (mod->dw, cuoff, &nextoff, &cuhdrsz,
 234                         NULL, NULL, NULL) != 0)
 235         return DWFL_E_LIBDW;
 236
 237       Dwfl_Error result = intern_cu (mod, cuoff + cuhdrsz, nextp);
 238       if (result != DWFL_E_NOERROR)
 239         return result;
 240
 241       if ((*nextp)->next == NULL && nextoff == (Dwarf_Off) -1l)
 242         (*nextp)->next = (void *) -1l;
 243     }
 244
 245   *cu = *nextp == (void *) -1l ? NULL : *nextp;
 246   return DWFL_E_NOERROR;
 247 }
 248
 249
 250 /* Intern the CU arange points to, if necessary.  */
 251
 252 static Dwfl_Error
 253 arangecu (Dwfl_Module *mod, struct dwfl_arange *arange, struct dwfl_cu **cu)
 254 {
 255   if (arange->cu == NULL)
 256     {
 257       const Dwarf_Arange *dwarange = &mod->dw->aranges->info[arange->arange];
 258       Dwfl_Error result = intern_cu (mod, dwarange->offset, &arange->cu);
 259       if (result != DWFL_E_NOERROR)
 260         return result;
 261       assert (arange->cu != NULL && arange->cu != (void *) -1l);
 262       less_lazy (mod);          /* Each arange with null ->cu counts once.  */
 263     }
 264
 265   *cu = arange->cu;
 266   return DWFL_E_NOERROR;
 267 }
 268
 269 Dwfl_Error
 270 internal_function_def
 271 __libdwfl_addrcu (Dwfl_Module *mod, Dwarf_Addr addr, struct dwfl_cu **cu)
 272 {
 273   struct dwfl_arange *arange;
 274   return addrarange (mod, addr, &arange) ?: arangecu (mod, arange, cu);
 275 }