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 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 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 } 324
