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