1 2 /*--------------------------------------------------------------------*/ 3 /*--- Format-neutral storage of and querying of info acquired from ---*/ 4 /*--- ELF/XCOFF stabs/dwarf1/dwarf2/dwarf3 debug info. ---*/ 5 /*--- storage.c ---*/ 6 /*--------------------------------------------------------------------*/ 7 8 /* 9 This file is part of Valgrind, a dynamic binary instrumentation 10 framework. 11 12 Copyright (C) 2000-2013 Julian Seward 13 jseward (at) acm.org 14 15 This program is free software; you can redistribute it and/or 16 modify it under the terms of the GNU General Public License as 17 published by the Free Software Foundation; either version 2 of the 18 License, or (at your option) any later version. 19 20 This program is distributed in the hope that it will be useful, but 21 WITHOUT ANY WARRANTY; without even the implied warranty of 22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 23 General Public License for more details. 24 25 You should have received a copy of the GNU General Public License 26 along with this program; if not, write to the Free Software 27 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 28 02111-1307, USA. 29 30 The GNU General Public License is contained in the file COPYING. 31 */ 32 33 /* This file manages the data structures built by the debuginfo 34 system. These are: the top level SegInfo list. For each SegInfo, 35 there are tables for for address-to-symbol mappings, 36 address-to-src-file/line mappings, and address-to-CFI-info 37 mappings. 38 */ 39 40 #include "pub_core_basics.h" 41 #include "pub_core_options.h" /* VG_(clo_verbosity) */ 42 #include "pub_core_debuginfo.h" 43 #include "pub_core_libcassert.h" 44 #include "pub_core_libcbase.h" 45 #include "pub_core_libcprint.h" 46 #include "pub_core_xarray.h" 47 #include "pub_core_oset.h" 48 49 #include "priv_misc.h" /* dinfo_zalloc/free/strdup */ 50 #include "priv_image.h" 51 #include "priv_d3basics.h" /* ML_(pp_GX) */ 52 #include "priv_tytypes.h" 53 #include "priv_storage.h" /* self */ 54 55 56 /*------------------------------------------------------------*/ 57 /*--- Misc (printing, errors) ---*/ 58 /*------------------------------------------------------------*/ 59 60 /* Show a non-fatal debug info reading error. Use vg_panic if 61 terminal. 'serious' errors are shown regardless of the 62 verbosity setting. */ 63 void ML_(symerr) ( struct _DebugInfo* di, Bool serious, const HChar* msg ) 64 { 65 /* XML mode hides everything :-( */ 66 if (VG_(clo_xml)) 67 return; 68 69 if (serious) { 70 71 VG_(message)(Vg_DebugMsg, "WARNING: Serious error when " 72 "reading debug info\n"); 73 if (True || VG_(clo_verbosity) < 2) { 74 /* Need to show what the file name is, at verbosity levels 2 75 or below, since that won't already have been shown */ 76 VG_(message)(Vg_DebugMsg, 77 "When reading debug info from %s:\n", 78 (di && di->fsm.filename) ? di->fsm.filename 79 : "???"); 80 } 81 VG_(message)(Vg_DebugMsg, "%s\n", msg); 82 83 } else { /* !serious */ 84 85 if (VG_(clo_verbosity) >= 2) 86 VG_(message)(Vg_DebugMsg, "%s\n", msg); 87 88 } 89 } 90 91 92 /* Print a symbol. */ 93 void ML_(ppSym) ( Int idx, DiSym* sym ) 94 { 95 HChar** sec_names = sym->sec_names; 96 vg_assert(sym->pri_name); 97 if (sec_names) 98 vg_assert(sec_names); 99 VG_(printf)( "%5d: %c%c %#8lx .. %#8lx (%d) %s%s", 100 idx, 101 sym->isText ? 'T' : '-', 102 sym->isIFunc ? 'I' : '-', 103 sym->addr, 104 sym->addr + sym->size - 1, sym->size, 105 sym->pri_name, sec_names ? " " : "" ); 106 if (sec_names) { 107 while (*sec_names) { 108 VG_(printf)("%s%s", *sec_names, *(sec_names+1) ? " " : ""); 109 sec_names++; 110 } 111 } 112 VG_(printf)("\n"); 113 } 114 115 /* Print a call-frame-info summary. */ 116 void ML_(ppDiCfSI) ( XArray* /* of CfiExpr */ exprs, DiCfSI* si ) 117 { 118 # define SHOW_HOW(_how, _off) \ 119 do { \ 120 if (_how == CFIR_UNKNOWN) { \ 121 VG_(printf)("Unknown"); \ 122 } else \ 123 if (_how == CFIR_SAME) { \ 124 VG_(printf)("Same"); \ 125 } else \ 126 if (_how == CFIR_CFAREL) { \ 127 VG_(printf)("cfa+%d", _off); \ 128 } else \ 129 if (_how == CFIR_MEMCFAREL) { \ 130 VG_(printf)("*(cfa+%d)", _off); \ 131 } else \ 132 if (_how == CFIR_EXPR) { \ 133 VG_(printf)("{"); \ 134 ML_(ppCfiExpr)(exprs, _off); \ 135 VG_(printf)("}"); \ 136 } else { \ 137 vg_assert(0+0); \ 138 } \ 139 } while (0) 140 141 VG_(printf)("[%#lx .. %#lx]: ", si->base, 142 si->base + (UWord)si->len - 1); 143 switch (si->cfa_how) { 144 case CFIC_IA_SPREL: 145 VG_(printf)("let cfa=oldSP+%d", si->cfa_off); 146 break; 147 case CFIC_IA_BPREL: 148 VG_(printf)("let cfa=oldBP+%d", si->cfa_off); 149 break; 150 case CFIC_ARM_R13REL: 151 VG_(printf)("let cfa=oldR13+%d", si->cfa_off); 152 break; 153 case CFIC_ARM_R12REL: 154 VG_(printf)("let cfa=oldR12+%d", si->cfa_off); 155 break; 156 case CFIC_ARM_R11REL: 157 VG_(printf)("let cfa=oldR11+%d", si->cfa_off); 158 break; 159 case CFIR_SAME: 160 VG_(printf)("let cfa=Same"); 161 break; 162 case CFIC_ARM_R7REL: 163 VG_(printf)("let cfa=oldR7+%d", si->cfa_off); 164 break; 165 case CFIC_ARM64_SPREL: 166 VG_(printf)("let cfa=oldSP+%d", si->cfa_off); 167 break; 168 case CFIC_ARM64_X29REL: 169 VG_(printf)("let cfa=oldX29+%d", si->cfa_off); 170 break; 171 case CFIC_EXPR: 172 VG_(printf)("let cfa={"); 173 ML_(ppCfiExpr)(exprs, si->cfa_off); 174 VG_(printf)("}"); 175 break; 176 default: 177 vg_assert(0); 178 } 179 180 VG_(printf)(" in RA="); 181 SHOW_HOW(si->ra_how, si->ra_off); 182 # if defined(VGA_x86) || defined(VGA_amd64) 183 VG_(printf)(" SP="); 184 SHOW_HOW(si->sp_how, si->sp_off); 185 VG_(printf)(" BP="); 186 SHOW_HOW(si->bp_how, si->bp_off); 187 # elif defined(VGA_arm) 188 VG_(printf)(" R14="); 189 SHOW_HOW(si->r14_how, si->r14_off); 190 VG_(printf)(" R13="); 191 SHOW_HOW(si->r13_how, si->r13_off); 192 VG_(printf)(" R12="); 193 SHOW_HOW(si->r12_how, si->r12_off); 194 VG_(printf)(" R11="); 195 SHOW_HOW(si->r11_how, si->r11_off); 196 VG_(printf)(" R7="); 197 SHOW_HOW(si->r7_how, si->r7_off); 198 # elif defined(VGA_ppc32) || defined(VGA_ppc64) 199 # elif defined(VGA_s390x) || defined(VGA_mips32) || defined(VGA_mips64) 200 VG_(printf)(" SP="); 201 SHOW_HOW(si->sp_how, si->sp_off); 202 VG_(printf)(" FP="); 203 SHOW_HOW(si->fp_how, si->fp_off); 204 # elif defined(VGA_arm64) 205 VG_(printf)(" SP="); 206 SHOW_HOW(si->sp_how, si->sp_off); 207 VG_(printf)(" X30="); 208 SHOW_HOW(si->x30_how, si->x30_off); 209 VG_(printf)(" X29="); 210 SHOW_HOW(si->x29_how, si->x29_off); 211 # else 212 # error "Unknown arch" 213 # endif 214 VG_(printf)("\n"); 215 # undef SHOW_HOW 216 } 217 218 219 /*------------------------------------------------------------*/ 220 /*--- Adding stuff ---*/ 221 /*------------------------------------------------------------*/ 222 223 /* Add a str to the string table, including terminating zero, and 224 return pointer to the string in vg_strtab. Unless it's been seen 225 recently, in which case we find the old pointer and return that. 226 This avoids the most egregious duplications. 227 228 JSGF: changed from returning an index to a pointer, and changed to 229 a chunking memory allocator rather than reallocating, so the 230 pointers are stable. 231 */ 232 HChar* ML_(addStr) ( struct _DebugInfo* di, const HChar* str, Int len ) 233 { 234 struct strchunk *chunk; 235 Int space_needed; 236 HChar* p; 237 238 if (len == -1) { 239 len = VG_(strlen)(str); 240 } else { 241 vg_assert(len >= 0); 242 } 243 244 space_needed = 1 + len; 245 246 // Allocate a new strtab chunk if necessary 247 if (di->strchunks == NULL || 248 (di->strchunks->strtab_used 249 + space_needed) > SEGINFO_STRCHUNKSIZE) { 250 chunk = ML_(dinfo_zalloc)("di.storage.addStr.1", sizeof(*chunk)); 251 chunk->strtab_used = 0; 252 chunk->next = di->strchunks; 253 di->strchunks = chunk; 254 } 255 chunk = di->strchunks; 256 257 p = &chunk->strtab[chunk->strtab_used]; 258 VG_(memcpy)(p, str, len); 259 chunk->strtab[chunk->strtab_used+len] = '\0'; 260 chunk->strtab_used += space_needed; 261 262 return p; 263 } 264 265 266 /* Add a string to the string table of a DebugInfo, by copying the 267 string from the given DiCursor. Measures the length of the string 268 itself. */ 269 HChar* ML_(addStrFromCursor)( struct _DebugInfo* di, DiCursor c ) 270 { 271 /* This is a less-than-stellar implementation, but it should 272 work. */ 273 vg_assert(ML_(cur_is_valid)(c)); 274 HChar* str = ML_(cur_read_strdup)(c, "di.addStrFromCursor.1"); 275 HChar* res = ML_(addStr)(di, str, -1); 276 ML_(dinfo_free)(str); 277 return res; 278 } 279 280 281 /* Add a symbol to the symbol table, by copying *sym. 'sym' may only 282 have one name, so there's no complexities to do with deep vs 283 shallow copying of the sec_name array. This is checked. 284 */ 285 void ML_(addSym) ( struct _DebugInfo* di, DiSym* sym ) 286 { 287 UInt new_sz, i; 288 DiSym* new_tab; 289 290 vg_assert(sym->pri_name != NULL); 291 vg_assert(sym->sec_names == NULL); 292 293 /* Ignore zero-sized syms. */ 294 if (sym->size == 0) return; 295 296 if (di->symtab_used == di->symtab_size) { 297 new_sz = 2 * di->symtab_size; 298 if (new_sz == 0) new_sz = 500; 299 new_tab = ML_(dinfo_zalloc)( "di.storage.addSym.1", 300 new_sz * sizeof(DiSym) ); 301 if (di->symtab != NULL) { 302 for (i = 0; i < di->symtab_used; i++) 303 new_tab[i] = di->symtab[i]; 304 ML_(dinfo_free)(di->symtab); 305 } 306 di->symtab = new_tab; 307 di->symtab_size = new_sz; 308 } 309 310 di->symtab[di->symtab_used++] = *sym; 311 vg_assert(di->symtab_used <= di->symtab_size); 312 } 313 314 315 /* Add a location to the location table. 316 */ 317 static void addLoc ( struct _DebugInfo* di, DiLoc* loc ) 318 { 319 UInt new_sz, i; 320 DiLoc* new_tab; 321 322 /* Zero-sized locs should have been ignored earlier */ 323 vg_assert(loc->size > 0); 324 325 if (di->loctab_used == di->loctab_size) { 326 new_sz = 2 * di->loctab_size; 327 if (new_sz == 0) new_sz = 500; 328 new_tab = ML_(dinfo_zalloc)( "di.storage.addLoc.1", 329 new_sz * sizeof(DiLoc) ); 330 if (di->loctab != NULL) { 331 for (i = 0; i < di->loctab_used; i++) 332 new_tab[i] = di->loctab[i]; 333 ML_(dinfo_free)(di->loctab); 334 } 335 di->loctab = new_tab; 336 di->loctab_size = new_sz; 337 } 338 339 di->loctab[di->loctab_used] = *loc; 340 di->loctab_used++; 341 vg_assert(di->loctab_used <= di->loctab_size); 342 } 343 344 345 /* Resize the LocTab (line number table) to save memory, by removing 346 (and, potentially, allowing m_mallocfree to unmap) any unused space 347 at the end of the table. 348 */ 349 static void shrinkLocTab ( struct _DebugInfo* di ) 350 { 351 DiLoc* new_tab; 352 UWord new_sz = di->loctab_used; 353 if (new_sz == di->loctab_size) return; 354 vg_assert(new_sz < di->loctab_size); 355 356 new_tab = ML_(dinfo_zalloc)( "di.storage.shrinkLocTab", 357 new_sz * sizeof(DiLoc) ); 358 VG_(memcpy)(new_tab, di->loctab, new_sz * sizeof(DiLoc)); 359 360 ML_(dinfo_free)(di->loctab); 361 di->loctab = new_tab; 362 di->loctab_size = new_sz; 363 } 364 365 366 /* Top-level place to call to add a source-location mapping entry. 367 */ 368 void ML_(addLineInfo) ( struct _DebugInfo* di, 369 const HChar* filename, 370 const HChar* dirname, /* NULL == directory is unknown */ 371 Addr this, 372 Addr next, 373 Int lineno, 374 Int entry /* only needed for debug printing */ 375 ) 376 { 377 static const Bool debug = False; 378 DiLoc loc; 379 UWord size = next - this; 380 381 /* Ignore zero-sized locs */ 382 if (this == next) return; 383 384 if (debug) 385 VG_(printf)( " src %s %s line %d %#lx-%#lx\n", 386 dirname ? dirname : "(unknown)", 387 filename, lineno, this, next ); 388 389 /* Maximum sanity checking. Some versions of GNU as do a shabby 390 * job with stabs entries; if anything looks suspicious, revert to 391 * a size of 1. This should catch the instruction of interest 392 * (since if using asm-level debug info, one instruction will 393 * correspond to one line, unlike with C-level debug info where 394 * multiple instructions can map to the one line), but avoid 395 * catching any other instructions bogusly. */ 396 if (this > next) { 397 if (VG_(clo_verbosity) > 2) { 398 VG_(message)(Vg_DebugMsg, 399 "warning: line info addresses out of order " 400 "at entry %d: 0x%lx 0x%lx\n", entry, this, next); 401 } 402 size = 1; 403 } 404 405 if (size > MAX_LOC_SIZE) { 406 if (0) 407 VG_(message)(Vg_DebugMsg, 408 "warning: line info address range too large " 409 "at entry %d: %lu\n", entry, size); 410 size = 1; 411 } 412 413 /* At this point, we know that the original value for |size|, viz 414 |next - this|, will only still be used in the case where 415 |this| <u |next|, so it can't have underflowed. Considering 416 that and the three checks that follow it, the following must 417 hold. */ 418 vg_assert(size >= 1); 419 vg_assert(size <= MAX_LOC_SIZE); 420 421 /* Rule out ones which are completely outside the r-x mapped area. 422 See "Comment_Regarding_Text_Range_Checks" elsewhere in this file 423 for background and rationale. */ 424 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map); 425 if (ML_(find_rx_mapping)(di, this, this + size - 1) == NULL) { 426 if (0) 427 VG_(message)(Vg_DebugMsg, 428 "warning: ignoring line info entry falling " 429 "outside current DebugInfo: %#lx %#lx %#lx %#lx\n", 430 di->text_avma, 431 di->text_avma + di->text_size, 432 this, this + size - 1); 433 return; 434 } 435 436 vg_assert(lineno >= 0); 437 if (lineno > MAX_LINENO) { 438 static Bool complained = False; 439 if (!complained) { 440 complained = True; 441 VG_(message)(Vg_UserMsg, 442 "warning: ignoring line info entry with " 443 "huge line number (%d)\n", lineno); 444 VG_(message)(Vg_UserMsg, 445 " Can't handle line numbers " 446 "greater than %d, sorry\n", MAX_LINENO); 447 VG_(message)(Vg_UserMsg, 448 "(Nb: this message is only shown once)\n"); 449 } 450 return; 451 } 452 453 loc.addr = this; 454 loc.size = (UShort)size; 455 loc.lineno = lineno; 456 loc.filename = filename; 457 loc.dirname = dirname; 458 459 if (0) VG_(message)(Vg_DebugMsg, 460 "addLoc: addr %#lx, size %lu, line %d, file %s\n", 461 this,size,lineno,filename); 462 463 addLoc ( di, &loc ); 464 } 465 466 467 /* Top-level place to call to add a CFI summary record. The supplied 468 DiCfSI is copied. */ 469 void ML_(addDiCfSI) ( struct _DebugInfo* di, DiCfSI* cfsi_orig ) 470 { 471 static const Bool debug = False; 472 UInt new_sz, i; 473 DiCfSI* new_tab; 474 SSizeT delta; 475 struct _DebugInfoMapping* map; 476 struct _DebugInfoMapping* map2; 477 478 /* copy the original, so we can mess with it */ 479 DiCfSI cfsi = *cfsi_orig; 480 481 if (debug) { 482 VG_(printf)("adding DiCfSI: "); 483 ML_(ppDiCfSI)(di->cfsi_exprs, &cfsi); 484 } 485 486 /* sanity */ 487 vg_assert(cfsi.len > 0); 488 /* If this fails, the implication is you have a single procedure 489 with more than 5 million bytes of code. Which is pretty 490 unlikely. Either that, or the debuginfo reader is somehow 491 broken. 5 million is of course arbitrary; but it's big enough 492 to be bigger than the size of any plausible piece of code that 493 would fall within a single procedure. */ 494 vg_assert(cfsi.len < 5000000); 495 496 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map); 497 /* Find mapping where at least one end of the CFSI falls into. */ 498 map = ML_(find_rx_mapping)(di, cfsi.base, cfsi.base); 499 map2 = ML_(find_rx_mapping)(di, cfsi.base + cfsi.len - 1, 500 cfsi.base + cfsi.len - 1); 501 if (map == NULL) 502 map = map2; 503 else if (map2 == NULL) 504 map2 = map; 505 506 /* Rule out ones which are completely outside the r-x mapped area 507 (or which span across different areas). 508 See "Comment_Regarding_Text_Range_Checks" elsewhere in this file 509 for background and rationale. */ 510 if (map == NULL || map != map2) { 511 static Int complaints = 10; 512 if (VG_(clo_trace_cfi) || complaints > 0) { 513 complaints--; 514 if (VG_(clo_verbosity) > 1) { 515 VG_(message)( 516 Vg_DebugMsg, 517 "warning: DiCfSI %#lx .. %#lx outside mapped rw segments (%s)\n", 518 cfsi.base, 519 cfsi.base + cfsi.len - 1, 520 di->soname 521 ); 522 } 523 if (VG_(clo_trace_cfi)) 524 ML_(ppDiCfSI)(di->cfsi_exprs, &cfsi); 525 } 526 return; 527 } 528 529 /* Now we know the range is at least partially inside the r-x 530 mapped area. That implies that at least one of the ends of the 531 range falls inside the area. If necessary, clip it so it is 532 completely within the area. If we don't do this, 533 check_CFSI_related_invariants() in debuginfo.c (invariant #2) 534 will fail. See 535 "Comment_on_IMPORTANT_CFSI_REPRESENTATIONAL_INVARIANTS" in 536 priv_storage.h for background. */ 537 if (cfsi.base < map->avma) { 538 /* Lower end is outside the mapped area. Hence upper end must 539 be inside it. */ 540 if (0) VG_(printf)("XXX truncate lower\n"); 541 vg_assert(cfsi.base + cfsi.len - 1 >= map->avma); 542 delta = (SSizeT)(map->avma - cfsi.base); 543 vg_assert(delta > 0); 544 vg_assert(delta < (SSizeT)cfsi.len); 545 cfsi.base += delta; 546 cfsi.len -= delta; 547 } 548 else 549 if (cfsi.base + cfsi.len - 1 > map->avma + map->size - 1) { 550 /* Upper end is outside the mapped area. Hence lower end must be 551 inside it. */ 552 if (0) VG_(printf)("XXX truncate upper\n"); 553 vg_assert(cfsi.base <= map->avma + map->size - 1); 554 delta = (SSizeT)( (cfsi.base + cfsi.len - 1) 555 - (map->avma + map->size - 1) ); 556 vg_assert(delta > 0); 557 vg_assert(delta < (SSizeT)cfsi.len); 558 cfsi.len -= delta; 559 } 560 561 /* Final checks */ 562 563 /* Because: either cfsi was entirely inside the range, in which 564 case we asserted that len > 0 at the start, OR it fell partially 565 inside the range, in which case we reduced it by some size 566 (delta) which is < its original size. */ 567 vg_assert(cfsi.len > 0); 568 569 /* Similar logic applies for the next two assertions. */ 570 vg_assert(cfsi.base >= map->avma); 571 vg_assert(cfsi.base + cfsi.len - 1 572 <= map->avma + map->size - 1); 573 574 if (di->cfsi_used == di->cfsi_size) { 575 new_sz = 2 * di->cfsi_size; 576 if (new_sz == 0) new_sz = 20; 577 new_tab = ML_(dinfo_zalloc)( "di.storage.addDiCfSI.1", 578 new_sz * sizeof(DiCfSI) ); 579 if (di->cfsi != NULL) { 580 for (i = 0; i < di->cfsi_used; i++) 581 new_tab[i] = di->cfsi[i]; 582 ML_(dinfo_free)(di->cfsi); 583 } 584 di->cfsi = new_tab; 585 di->cfsi_size = new_sz; 586 } 587 588 di->cfsi[di->cfsi_used] = cfsi; 589 di->cfsi_used++; 590 vg_assert(di->cfsi_used <= di->cfsi_size); 591 } 592 593 594 Int ML_(CfiExpr_Undef)( XArray* dst ) 595 { 596 CfiExpr e; 597 VG_(memset)( &e, 0, sizeof(e) ); 598 e.tag = Cex_Undef; 599 return (Int)VG_(addToXA)( dst, &e ); 600 } 601 Int ML_(CfiExpr_Deref)( XArray* dst, Int ixAddr ) 602 { 603 CfiExpr e; 604 VG_(memset)( &e, 0, sizeof(e) ); 605 e.tag = Cex_Deref; 606 e.Cex.Deref.ixAddr = ixAddr; 607 return (Int)VG_(addToXA)( dst, &e ); 608 } 609 Int ML_(CfiExpr_Const)( XArray* dst, UWord con ) 610 { 611 CfiExpr e; 612 VG_(memset)( &e, 0, sizeof(e) ); 613 e.tag = Cex_Const; 614 e.Cex.Const.con = con; 615 return (Int)VG_(addToXA)( dst, &e ); 616 } 617 Int ML_(CfiExpr_Unop)( XArray* dst, CfiUnop op, Int ix ) 618 { 619 CfiExpr e; 620 VG_(memset)( &e, 0, sizeof(e) ); 621 e.tag = Cex_Unop; 622 e.Cex.Unop.op = op; 623 e.Cex.Unop.ix = ix; 624 return (Int)VG_(addToXA)( dst, &e ); 625 } 626 Int ML_(CfiExpr_Binop)( XArray* dst, CfiBinop op, Int ixL, Int ixR ) 627 { 628 CfiExpr e; 629 VG_(memset)( &e, 0, sizeof(e) ); 630 e.tag = Cex_Binop; 631 e.Cex.Binop.op = op; 632 e.Cex.Binop.ixL = ixL; 633 e.Cex.Binop.ixR = ixR; 634 return (Int)VG_(addToXA)( dst, &e ); 635 } 636 Int ML_(CfiExpr_CfiReg)( XArray* dst, CfiReg reg ) 637 { 638 CfiExpr e; 639 VG_(memset)( &e, 0, sizeof(e) ); 640 e.tag = Cex_CfiReg; 641 e.Cex.CfiReg.reg = reg; 642 return (Int)VG_(addToXA)( dst, &e ); 643 } 644 Int ML_(CfiExpr_DwReg)( XArray* dst, Int reg ) 645 { 646 CfiExpr e; 647 VG_(memset)( &e, 0, sizeof(e) ); 648 e.tag = Cex_DwReg; 649 e.Cex.DwReg.reg = reg; 650 return (Int)VG_(addToXA)( dst, &e ); 651 } 652 653 static void ppCfiUnop ( CfiUnop op ) 654 { 655 switch (op) { 656 case Cunop_Abs: VG_(printf)("abs"); break; 657 case Cunop_Neg: VG_(printf)("-"); break; 658 case Cunop_Not: VG_(printf)("~"); break; 659 default: vg_assert(0); 660 } 661 } 662 663 static void ppCfiBinop ( CfiBinop op ) 664 { 665 switch (op) { 666 case Cbinop_Add: VG_(printf)("+"); break; 667 case Cbinop_Sub: VG_(printf)("-"); break; 668 case Cbinop_And: VG_(printf)("&"); break; 669 case Cbinop_Mul: VG_(printf)("*"); break; 670 case Cbinop_Shl: VG_(printf)("<<"); break; 671 case Cbinop_Shr: VG_(printf)(">>"); break; 672 case Cbinop_Eq: VG_(printf)("=="); break; 673 case Cbinop_Ge: VG_(printf)(">="); break; 674 case Cbinop_Gt: VG_(printf)(">"); break; 675 case Cbinop_Le: VG_(printf)("<="); break; 676 case Cbinop_Lt: VG_(printf)("<"); break; 677 case Cbinop_Ne: VG_(printf)("!="); break; 678 default: vg_assert(0); 679 } 680 } 681 682 static void ppCfiReg ( CfiReg reg ) 683 { 684 switch (reg) { 685 case Creg_IA_SP: VG_(printf)("xSP"); break; 686 case Creg_IA_BP: VG_(printf)("xBP"); break; 687 case Creg_IA_IP: VG_(printf)("xIP"); break; 688 case Creg_ARM_R13: VG_(printf)("R13"); break; 689 case Creg_ARM_R12: VG_(printf)("R12"); break; 690 case Creg_ARM_R15: VG_(printf)("R15"); break; 691 case Creg_ARM_R14: VG_(printf)("R14"); break; 692 case Creg_ARM64_X30: VG_(printf)("X30"); break; 693 case Creg_MIPS_RA: VG_(printf)("RA"); break; 694 case Creg_S390_R14: VG_(printf)("R14"); break; 695 default: vg_assert(0); 696 } 697 } 698 699 void ML_(ppCfiExpr)( XArray* src, Int ix ) 700 { 701 /* VG_(indexXA) checks for invalid src/ix values, so we can 702 use it indiscriminately. */ 703 CfiExpr* e = (CfiExpr*) VG_(indexXA)( src, ix ); 704 switch (e->tag) { 705 case Cex_Undef: 706 VG_(printf)("Undef"); 707 break; 708 case Cex_Deref: 709 VG_(printf)("*("); 710 ML_(ppCfiExpr)(src, e->Cex.Deref.ixAddr); 711 VG_(printf)(")"); 712 break; 713 case Cex_Const: 714 VG_(printf)("0x%lx", e->Cex.Const.con); 715 break; 716 case Cex_Unop: 717 ppCfiUnop(e->Cex.Unop.op); 718 VG_(printf)("("); 719 ML_(ppCfiExpr)(src, e->Cex.Unop.ix); 720 VG_(printf)(")"); 721 break; 722 case Cex_Binop: 723 VG_(printf)("("); 724 ML_(ppCfiExpr)(src, e->Cex.Binop.ixL); 725 VG_(printf)(")"); 726 ppCfiBinop(e->Cex.Binop.op); 727 VG_(printf)("("); 728 ML_(ppCfiExpr)(src, e->Cex.Binop.ixR); 729 VG_(printf)(")"); 730 break; 731 case Cex_CfiReg: 732 ppCfiReg(e->Cex.CfiReg.reg); 733 break; 734 case Cex_DwReg: 735 VG_(printf)("dwr%d", e->Cex.DwReg.reg); 736 break; 737 default: 738 VG_(core_panic)("ML_(ppCfiExpr)"); 739 /*NOTREACHED*/ 740 break; 741 } 742 } 743 744 745 Word ML_(cmp_for_DiAddrRange_range) ( const void* keyV, 746 const void* elemV ) { 747 const Addr* key = (const Addr*)keyV; 748 const DiAddrRange* elem = (const DiAddrRange*)elemV; 749 if (0) 750 VG_(printf)("cmp_for_DiAddrRange_range: %#lx vs %#lx\n", 751 *key, elem->aMin); 752 if ((*key) < elem->aMin) return -1; 753 if ((*key) > elem->aMax) return 1; 754 return 0; 755 } 756 757 static 758 void show_scope ( OSet* /* of DiAddrRange */ scope, const HChar* who ) 759 { 760 DiAddrRange* range; 761 VG_(printf)("Scope \"%s\" = {\n", who); 762 VG_(OSetGen_ResetIter)( scope ); 763 while (True) { 764 range = VG_(OSetGen_Next)( scope ); 765 if (!range) break; 766 VG_(printf)(" %#lx .. %#lx: %lu vars\n", range->aMin, range->aMax, 767 range->vars ? VG_(sizeXA)(range->vars) : 0); 768 } 769 VG_(printf)("}\n"); 770 } 771 772 /* Add the variable 'var' to 'scope' for the address range [aMin,aMax] 773 (inclusive of aMin and aMax). Split existing ranges as required if 774 aMin or aMax or both don't match existing range boundaries, and add 775 'var' to all required ranges. Take great care to preserve the 776 invariant that the ranges in 'scope' cover the entire address range 777 exactly once, with no overlaps and no holes. */ 778 static void add_var_to_arange ( 779 /*MOD*/OSet* /* of DiAddrRange */ scope, 780 Addr aMin, 781 Addr aMax, 782 DiVariable* var 783 ) 784 { 785 DiAddrRange *first, *last, *range; 786 /* These xx variables are for assertion checking only; they don't 787 contribute anything to the actual work of this function. */ 788 DiAddrRange *xxRangep, *xxFirst, *xxLast; 789 UWord xxIters; 790 791 vg_assert(aMin <= aMax); 792 793 if (0) VG_(printf)("add_var_to_arange: %#lx .. %#lx\n", aMin, aMax); 794 if (0) show_scope( scope, "add_var_to_arange(1)" ); 795 796 /* See if the lower end of the range (aMin) falls exactly on an 797 existing range boundary. If not, find the range it does fall 798 into, and split it (copying the variables in the process), so 799 that aMin does exactly fall on a range boundary. */ 800 first = VG_(OSetGen_Lookup)( scope, &aMin ); 801 /* It must be present, since the presented OSet must cover 802 the entire address range. */ 803 vg_assert(first); 804 vg_assert(first->aMin <= first->aMax); 805 vg_assert(first->aMin <= aMin && aMin <= first->aMax); 806 807 /* Fast track common case, which is that the range specified for 808 the variable exactly coincides with one already-existing 809 range. */ 810 if (first->aMin == aMin && first->aMax == aMax) { 811 vg_assert(first->vars); 812 VG_(addToXA)( first->vars, var ); 813 return; 814 } 815 816 /* We have to get into splitting ranges, which is complex 817 and slow. */ 818 if (first->aMin < aMin) { 819 DiAddrRange* nyu; 820 /* Ok. We'll have to split 'first'. */ 821 /* truncate the upper end of 'first' */ 822 Addr tmp = first->aMax; 823 first->aMax = aMin-1; 824 vg_assert(first->aMin <= first->aMax); 825 /* create a new range */ 826 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) ); 827 vg_assert(nyu); 828 nyu->aMin = aMin; 829 nyu->aMax = tmp; 830 vg_assert(nyu->aMin <= nyu->aMax); 831 /* copy vars into it */ 832 vg_assert(first->vars); 833 nyu->vars = VG_(cloneXA)( "di.storage.avta.1", first->vars ); 834 vg_assert(nyu->vars); 835 VG_(OSetGen_Insert)( scope, nyu ); 836 first = nyu; 837 } 838 839 vg_assert(first->aMin == aMin); 840 841 /* Now do exactly the same for the upper end (aMax): if it doesn't 842 fall on a boundary, cause it to do so by splitting the range it 843 does currently fall into. */ 844 last = VG_(OSetGen_Lookup)( scope, &aMax ); 845 vg_assert(last->aMin <= last->aMax); 846 vg_assert(last->aMin <= aMax && aMax <= last->aMax); 847 848 if (aMax < last->aMax) { 849 DiAddrRange* nyu; 850 /* We have to split 'last'. */ 851 /* truncate the lower end of 'last' */ 852 Addr tmp = last->aMin; 853 last->aMin = aMax+1; 854 vg_assert(last->aMin <= last->aMax); 855 /* create a new range */ 856 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) ); 857 vg_assert(nyu); 858 nyu->aMin = tmp; 859 nyu->aMax = aMax; 860 vg_assert(nyu->aMin <= nyu->aMax); 861 /* copy vars into it */ 862 vg_assert(last->vars); 863 nyu->vars = VG_(cloneXA)( "di.storage.avta.2", last->vars ); 864 vg_assert(nyu->vars); 865 VG_(OSetGen_Insert)( scope, nyu ); 866 last = nyu; 867 } 868 869 vg_assert(aMax == last->aMax); 870 871 xxFirst = (DiAddrRange*)VG_(OSetGen_Lookup)(scope, &aMin); 872 xxLast = (DiAddrRange*)VG_(OSetGen_Lookup)(scope, &aMax); 873 vg_assert(xxFirst); 874 vg_assert(xxLast); 875 vg_assert(xxFirst->aMin == aMin); 876 vg_assert(xxLast->aMax == aMax); 877 if (xxFirst != xxLast) 878 vg_assert(xxFirst->aMax < xxLast->aMin); 879 880 /* Great. Now we merely need to iterate over the segments from 881 'first' to 'last' inclusive, and add 'var' to the variable set 882 of each of them. */ 883 if (0) { 884 static UWord ctr = 0; 885 ctr++; 886 VG_(printf)("ctr = %lu\n", ctr); 887 if (ctr >= 33263) show_scope( scope, "add_var_to_arange(2)" ); 888 } 889 890 xxIters = 0; 891 range = xxRangep = NULL; 892 VG_(OSetGen_ResetIterAt)( scope, &aMin ); 893 while (True) { 894 xxRangep = range; 895 range = VG_(OSetGen_Next)( scope ); 896 if (!range) break; 897 if (range->aMin > aMax) break; 898 xxIters++; 899 if (0) VG_(printf)("have range %#lx %#lx\n", 900 range->aMin, range->aMax); 901 902 /* Sanity checks */ 903 if (!xxRangep) { 904 /* This is the first in the range */ 905 vg_assert(range->aMin == aMin); 906 } else { 907 vg_assert(xxRangep->aMax + 1 == range->aMin); 908 } 909 910 vg_assert(range->vars); 911 VG_(addToXA)( range->vars, var ); 912 } 913 /* Done. We should have seen at least one range. */ 914 vg_assert(xxIters >= 1); 915 if (xxIters == 1) vg_assert(xxFirst == xxLast); 916 if (xxFirst == xxLast) vg_assert(xxIters == 1); 917 vg_assert(xxRangep); 918 vg_assert(xxRangep->aMax == aMax); 919 vg_assert(xxRangep == xxLast); 920 } 921 922 923 /* Top-level place to call to add a variable description (as extracted 924 from a DWARF3 .debug_info section. */ 925 void ML_(addVar)( struct _DebugInfo* di, 926 Int level, 927 Addr aMin, 928 Addr aMax, 929 HChar* name, /* in di's .strchunks */ 930 UWord typeR, /* a cuOff */ 931 GExpr* gexpr, 932 GExpr* fbGX, 933 HChar* fileName, /* where decl'd - may be NULL. 934 in di's .strchunks */ 935 Int lineNo, /* where decl'd - may be zero */ 936 Bool show ) 937 { 938 OSet* /* of DiAddrRange */ scope; 939 DiVariable var; 940 Bool all; 941 TyEnt* ent; 942 MaybeULong mul; 943 const HChar* badness; 944 945 tl_assert(di && di->admin_tyents); 946 947 if (0) { 948 VG_(printf)(" ML_(addVar): level %d %#lx-%#lx %s :: ", 949 level, aMin, aMax, name ); 950 ML_(pp_TyEnt_C_ishly)( di->admin_tyents, typeR ); 951 VG_(printf)("\n Var="); 952 ML_(pp_GX)(gexpr); 953 VG_(printf)("\n"); 954 if (fbGX) { 955 VG_(printf)(" FrB="); 956 ML_(pp_GX)( fbGX ); 957 VG_(printf)("\n"); 958 } else { 959 VG_(printf)(" FrB=none\n"); 960 } 961 VG_(printf)("\n"); 962 } 963 964 vg_assert(level >= 0); 965 vg_assert(aMin <= aMax); 966 vg_assert(name); 967 vg_assert(gexpr); 968 969 ent = ML_(TyEnts__index_by_cuOff)( di->admin_tyents, NULL, typeR); 970 tl_assert(ent); 971 vg_assert(ML_(TyEnt__is_type)(ent)); 972 973 /* "Comment_Regarding_Text_Range_Checks" (is referred to elsewhere) 974 ---------------------------------------------------------------- 975 Ignore any variables whose aMin .. aMax (that is, range of text 976 addresses for which they actually exist) falls outside the text 977 segment. Is this indicative of a bug in the reader? Maybe. 978 (LATER): instead of restricting strictly to the .text segment, 979 be a bit more relaxed, and accept any variable whose text range 980 falls inside the r-x mapped area. This is useful because .text 981 is not always the only instruction-carrying segment: others are: 982 .init .plt __libc_freeres_fn and .fini. This implicitly assumes 983 that those extra sections have the same bias as .text, but that 984 seems a reasonable assumption to me. */ 985 /* This is assured us by top level steering logic in debuginfo.c, 986 and it is re-checked at the start of 987 ML_(read_elf_debug_info). */ 988 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map); 989 if (level > 0 && ML_(find_rx_mapping)(di, aMin, aMax) == NULL) { 990 if (VG_(clo_verbosity) >= 0) { 991 VG_(message)(Vg_DebugMsg, 992 "warning: addVar: in range %#lx .. %#lx outside " 993 "all rx mapped areas (%s)\n", 994 aMin, aMax, name 995 ); 996 } 997 return; 998 } 999 1000 /* If the type's size is zero (which can mean unknown size), ignore 1001 it. We will never be able to actually relate a data address to 1002 a data object with zero size, so there's no point in storing 1003 info on it. On 32-bit platforms, also reject types whose size 1004 is 2^32 bytes or large. (It's amazing what junk shows up ..) */ 1005 mul = ML_(sizeOfType)(di->admin_tyents, typeR); 1006 1007 badness = NULL; 1008 if (mul.b != True) 1009 badness = "unknown size"; 1010 else if (mul.ul == 0) 1011 badness = "zero size "; 1012 else if (sizeof(void*) == 4 && mul.ul >= (1ULL<<32)) 1013 badness = "implausibly large"; 1014 1015 if (badness) { 1016 static Int complaints = 10; 1017 if (VG_(clo_verbosity) >= 2 && complaints > 0) { 1018 VG_(message)(Vg_DebugMsg, "warning: addVar: %s (%s)\n", 1019 badness, name ); 1020 complaints--; 1021 } 1022 return; 1023 } 1024 1025 if (!di->varinfo) { 1026 di->varinfo = VG_(newXA)( ML_(dinfo_zalloc), 1027 "di.storage.addVar.1", 1028 ML_(dinfo_free), 1029 sizeof(OSet*) ); 1030 } 1031 1032 vg_assert(level < 256); /* arbitrary; stay sane */ 1033 /* Expand the top level array enough to map this level */ 1034 while ( VG_(sizeXA)(di->varinfo) <= level ) { 1035 DiAddrRange* nyu; 1036 scope = VG_(OSetGen_Create)( offsetof(DiAddrRange,aMin), 1037 ML_(cmp_for_DiAddrRange_range), 1038 ML_(dinfo_zalloc), "di.storage.addVar.2", 1039 ML_(dinfo_free) ); 1040 vg_assert(scope); 1041 if (0) VG_(printf)("create: scope = %p, adding at %ld\n", 1042 scope, VG_(sizeXA)(di->varinfo)); 1043 VG_(addToXA)( di->varinfo, &scope ); 1044 /* Add a single range covering the entire address space. At 1045 level 0 we require this doesn't get split. At levels above 0 1046 we require that any additions to it cause it to get split. 1047 All of these invariants get checked both add_var_to_arange 1048 and after reading is complete, in canonicaliseVarInfo. */ 1049 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) ); 1050 vg_assert(nyu); 1051 nyu->aMin = (Addr)0; 1052 nyu->aMax = ~(Addr)0; 1053 nyu->vars = VG_(newXA)( ML_(dinfo_zalloc), "di.storage.addVar.3", 1054 ML_(dinfo_free), 1055 sizeof(DiVariable) ); 1056 vg_assert(nyu->vars); 1057 VG_(OSetGen_Insert)( scope, nyu ); 1058 } 1059 1060 vg_assert( VG_(sizeXA)(di->varinfo) > level ); 1061 scope = *(OSet**)VG_(indexXA)( di->varinfo, level ); 1062 vg_assert(scope); 1063 1064 var.name = name; 1065 var.typeR = typeR; 1066 var.gexpr = gexpr; 1067 var.fbGX = fbGX; 1068 var.fileName = fileName; 1069 var.lineNo = lineNo; 1070 1071 all = aMin == (Addr)0 && aMax == ~(Addr)0; 1072 vg_assert(level == 0 ? all : !all); 1073 1074 add_var_to_arange( /*MOD*/scope, aMin, aMax, &var ); 1075 } 1076 1077 1078 /* This really just checks the constructed data structure, as there is 1079 no canonicalisation to do. */ 1080 static void canonicaliseVarInfo ( struct _DebugInfo* di ) 1081 { 1082 Word i, nInThisScope; 1083 1084 if (!di->varinfo) 1085 return; 1086 1087 for (i = 0; i < VG_(sizeXA)(di->varinfo); i++) { 1088 1089 DiAddrRange *range, *rangep; 1090 OSet* scope = *(OSet**)VG_(indexXA)(di->varinfo, i); 1091 if (!scope) continue; 1092 1093 /* Deal with the global-scope case. */ 1094 if (i == 0) { 1095 Addr zero = 0; 1096 vg_assert(VG_(OSetGen_Size)( scope ) == 1); 1097 range = VG_(OSetGen_Lookup)( scope, &zero ); 1098 vg_assert(range); 1099 vg_assert(range->aMin == (Addr)0); 1100 vg_assert(range->aMax == ~(Addr)0); 1101 continue; 1102 } 1103 1104 /* All the rest of this is for the local-scope case. */ 1105 /* iterate over all entries in 'scope' */ 1106 nInThisScope = 0; 1107 rangep = NULL; 1108 VG_(OSetGen_ResetIter)(scope); 1109 while (True) { 1110 range = VG_(OSetGen_Next)(scope); 1111 if (!range) { 1112 /* We just saw the last one. There must have been at 1113 least one entry in the range. */ 1114 vg_assert(rangep); 1115 vg_assert(rangep->aMax == ~(Addr)0); 1116 break; 1117 } 1118 1119 vg_assert(range->aMin <= range->aMax); 1120 vg_assert(range->vars); 1121 1122 if (!rangep) { 1123 /* This is the first entry in the range. */ 1124 vg_assert(range->aMin == 0); 1125 } else { 1126 vg_assert(rangep->aMax + 1 == range->aMin); 1127 } 1128 1129 rangep = range; 1130 nInThisScope++; 1131 } /* iterating over ranges in a given scope */ 1132 1133 /* If there's only one entry in this (local) scope, it must 1134 cover the entire address space (obviously), but it must not 1135 contain any vars. */ 1136 1137 vg_assert(nInThisScope > 0); 1138 if (nInThisScope == 1) { 1139 Addr zero = 0; 1140 vg_assert(VG_(OSetGen_Size)( scope ) == 1); 1141 range = VG_(OSetGen_Lookup)( scope, &zero ); 1142 vg_assert(range); 1143 vg_assert(range->aMin == (Addr)0); 1144 vg_assert(range->aMax == ~(Addr)0); 1145 vg_assert(range->vars); 1146 vg_assert(VG_(sizeXA)(range->vars) == 0); 1147 } 1148 1149 } /* iterate over scopes */ 1150 } 1151 1152 1153 /*------------------------------------------------------------*/ 1154 /*--- Canonicalisers ---*/ 1155 /*------------------------------------------------------------*/ 1156 1157 /* Sort the symtab by starting address, and emit warnings if any 1158 symbols have overlapping address ranges. We use that old chestnut, 1159 shellsort. Mash the table around so as to establish the property 1160 that addresses are in order and the ranges to not overlap. This 1161 facilitates using binary search to map addresses to symbols when we 1162 come to query the table. 1163 */ 1164 static Int compare_DiSym ( const void* va, const void* vb ) 1165 { 1166 const DiSym* a = va; 1167 const DiSym* b = vb; 1168 if (a->addr < b->addr) return -1; 1169 if (a->addr > b->addr) return 1; 1170 return 0; 1171 } 1172 1173 1174 /* An address is associated with more than one name. Which do we 1175 prefer as the "display" name (that we show the user in stack 1176 traces)? In order: 1177 1178 - Prefer "PMPI_<foo>" over "MPI_<foo>". 1179 1180 - Else, prefer a non-empty name over an empty one. 1181 1182 - Else, prefer a non-whitespace name over an all-whitespace name. 1183 1184 - Else, prefer the shorter symbol name. If the symbol contains a 1185 version symbol ('@' on Linux, other platforms may differ), which means it 1186 is versioned, then the length up to the version symbol is used for length 1187 comparison purposes (so "foo (at) GLIBC_2.4.2" is considered shorter than 1188 "foobar"). 1189 1190 - Else, if two symbols have the same length, prefer a versioned symbol over 1191 a non-versioned symbol. 1192 1193 - Else, use alphabetical ordering. 1194 1195 - Otherwise, they must be the same; use the name with the lower address. 1196 1197 Very occasionally this goes wrong (eg. 'memcmp' and 'bcmp' are 1198 aliases in glibc, we choose the 'bcmp' symbol because it's shorter, 1199 so we can misdescribe memcmp() as bcmp()). This is hard to avoid. 1200 It's mentioned in the FAQ file. 1201 1202 Returned value is True if a_name is preferred, False if b_name is 1203 preferred. 1204 */ 1205 static 1206 Bool preferName ( struct _DebugInfo* di, 1207 HChar* a_name, HChar* b_name, 1208 Addr sym_avma/*exposition only*/ ) 1209 { 1210 Word cmp; 1211 Word vlena, vlenb; /* length without version */ 1212 const HChar *vpa, *vpb; 1213 1214 Bool preferA = False; 1215 Bool preferB = False; 1216 1217 vg_assert(a_name); 1218 vg_assert(b_name); 1219 vg_assert(a_name != b_name); 1220 1221 vlena = VG_(strlen)(a_name); 1222 vlenb = VG_(strlen)(b_name); 1223 1224 # if defined(VGO_linux) 1225 # define VERSION_CHAR '@' 1226 # elif defined(VGO_darwin) 1227 # define VERSION_CHAR '$' 1228 # else 1229 # error Unknown OS 1230 # endif 1231 1232 vpa = VG_(strchr)(a_name, VERSION_CHAR); 1233 vpb = VG_(strchr)(b_name, VERSION_CHAR); 1234 1235 # undef VERSION_CHAR 1236 1237 if (vpa) 1238 vlena = vpa - a_name; 1239 if (vpb) 1240 vlenb = vpb - b_name; 1241 1242 /* MPI hack: prefer PMPI_Foo over MPI_Foo */ 1243 if (0==VG_(strncmp)(a_name, "MPI_", 4) 1244 && 0==VG_(strncmp)(b_name, "PMPI_", 5) 1245 && 0==VG_(strcmp)(a_name, 1+b_name)) { 1246 preferB = True; goto out; 1247 } 1248 if (0==VG_(strncmp)(b_name, "MPI_", 4) 1249 && 0==VG_(strncmp)(a_name, "PMPI_", 5) 1250 && 0==VG_(strcmp)(b_name, 1+a_name)) { 1251 preferA = True; goto out; 1252 } 1253 1254 /* Prefer non-empty name. */ 1255 if (vlena && !vlenb) { 1256 preferA = True; goto out; 1257 } 1258 if (vlenb && !vlena) { 1259 preferB = True; goto out; 1260 } 1261 1262 /* Prefer non-whitespace name. */ 1263 { 1264 Bool blankA = True; 1265 Bool blankB = True; 1266 HChar *s; 1267 s = a_name; 1268 while (*s) { 1269 if (!VG_(isspace)(*s++)) { 1270 blankA = False; 1271 break; 1272 } 1273 } 1274 s = b_name; 1275 while (*s) { 1276 if (!VG_(isspace)(*s++)) { 1277 blankB = False; 1278 break; 1279 } 1280 } 1281 1282 if (!blankA && blankB) { 1283 preferA = True; goto out; 1284 } 1285 if (!blankB && blankA) { 1286 preferB = True; goto out; 1287 } 1288 } 1289 1290 /* Select the shortest unversioned name */ 1291 if (vlena < vlenb) { 1292 preferA = True; goto out; 1293 } 1294 if (vlenb < vlena) { 1295 preferB = True; goto out; 1296 } 1297 1298 /* Equal lengths; select the versioned name */ 1299 if (vpa && !vpb) { 1300 preferA = True; goto out; 1301 } 1302 if (vpb && !vpa) { 1303 preferB = True; goto out; 1304 } 1305 1306 /* Either both versioned or neither is versioned; select them 1307 alphabetically */ 1308 cmp = VG_(strcmp)(a_name, b_name); 1309 if (cmp < 0) { 1310 preferA = True; goto out; 1311 } 1312 if (cmp > 0) { 1313 preferB = True; goto out; 1314 } 1315 1316 /* If we get here, they are the same name. */ 1317 1318 /* In this case we could choose either (arbitrarily), but might as 1319 well choose the one with the lowest DiSym* address, so as to try 1320 and make the comparison mechanism more stable (a la sorting 1321 parlance). Also, skip the diagnostic printing in this case. */ 1322 return a_name <= b_name ? True : False; 1323 1324 /*NOTREACHED*/ 1325 vg_assert(0); 1326 out: 1327 if (preferA && !preferB) { 1328 TRACE_SYMTAB("sym at %#lx: prefer '%s' to '%s'\n", 1329 sym_avma, a_name, b_name ); 1330 return True; 1331 } 1332 if (preferB && !preferA) { 1333 TRACE_SYMTAB("sym at %#lx: prefer '%s' to '%s'\n", 1334 sym_avma, b_name, a_name ); 1335 return False; 1336 } 1337 /*NOTREACHED*/ 1338 vg_assert(0); 1339 } 1340 1341 1342 /* Add the names in FROM to the names in TO. */ 1343 static 1344 void add_DiSym_names_to_from ( DebugInfo* di, DiSym* to, DiSym* from ) 1345 { 1346 vg_assert(to->pri_name); 1347 vg_assert(from->pri_name); 1348 /* Figure out how many names there will be in the new combined 1349 secondary vector. */ 1350 HChar** to_sec = to->sec_names; 1351 HChar** from_sec = from->sec_names; 1352 Word n_new_sec = 1; 1353 if (from_sec) { 1354 while (*from_sec) { 1355 n_new_sec++; 1356 from_sec++; 1357 } 1358 } 1359 if (to_sec) { 1360 while (*to_sec) { 1361 n_new_sec++; 1362 to_sec++; 1363 } 1364 } 1365 if (0) 1366 TRACE_SYMTAB("merge: -> %ld\n", n_new_sec); 1367 /* Create the new sec and copy stuff into it, putting the new 1368 entries at the end. */ 1369 HChar** new_sec = ML_(dinfo_zalloc)( "di.storage.aDntf.1", 1370 (n_new_sec+1) * sizeof(HChar*) ); 1371 from_sec = from->sec_names; 1372 to_sec = to->sec_names; 1373 Word i = 0; 1374 if (to_sec) { 1375 while (*to_sec) { 1376 new_sec[i++] = *to_sec; 1377 to_sec++; 1378 } 1379 } 1380 new_sec[i++] = from->pri_name; 1381 if (from_sec) { 1382 while (*from_sec) { 1383 new_sec[i++] = *from_sec; 1384 from_sec++; 1385 } 1386 } 1387 vg_assert(i == n_new_sec); 1388 vg_assert(new_sec[i] == NULL); 1389 /* If we're replacing an existing secondary vector, free it. */ 1390 if (to->sec_names) { 1391 ML_(dinfo_free)(to->sec_names); 1392 } 1393 to->sec_names = new_sec; 1394 } 1395 1396 1397 static void canonicaliseSymtab ( struct _DebugInfo* di ) 1398 { 1399 Word i, j, n_truncated; 1400 Addr sta1, sta2, end1, end2, toc1, toc2; 1401 HChar *pri1, *pri2, **sec1, **sec2; 1402 Bool ist1, ist2, isf1, isf2; 1403 1404 # define SWAP(ty,aa,bb) \ 1405 do { ty tt = (aa); (aa) = (bb); (bb) = tt; } while (0) 1406 1407 if (di->symtab_used == 0) 1408 return; 1409 1410 /* Check initial invariants */ 1411 for (i = 0; i < di->symtab_used; i++) { 1412 DiSym* sym = &di->symtab[i]; 1413 vg_assert(sym->pri_name); 1414 vg_assert(!sym->sec_names); 1415 } 1416 1417 /* Sort by address. */ 1418 VG_(ssort)(di->symtab, di->symtab_used, 1419 sizeof(*di->symtab), compare_DiSym); 1420 1421 cleanup_more: 1422 1423 /* If two symbols have identical address ranges, and agree on 1424 .isText and .isIFunc, merge them into a single entry, but 1425 preserve both names, so we end up knowing all the names for that 1426 particular address range. */ 1427 while (1) { 1428 Word r, w, n_merged; 1429 n_merged = 0; 1430 w = 0; 1431 /* A pass merging entries together */ 1432 for (r = 1; r < di->symtab_used; r++) { 1433 vg_assert(w < r); 1434 if ( di->symtab[w].addr == di->symtab[r].addr 1435 && di->symtab[w].size == di->symtab[r].size 1436 && !!di->symtab[w].isText == !!di->symtab[r].isText) { 1437 /* merge the two into one */ 1438 n_merged++; 1439 /* Add r names to w if r has secondary names 1440 or r and w primary names differ. */ 1441 if (di->symtab[r].sec_names 1442 || (0 != VG_(strcmp)(di->symtab[r].pri_name, 1443 di->symtab[w].pri_name))) { 1444 add_DiSym_names_to_from(di, &di->symtab[w], &di->symtab[r]); 1445 } 1446 /* mark w as an IFunc if either w or r are */ 1447 di->symtab[w].isIFunc = di->symtab[w].isIFunc || di->symtab[r].isIFunc; 1448 /* and use ::pri_names to indicate this slot is no longer in use */ 1449 di->symtab[r].pri_name = NULL; 1450 if (di->symtab[r].sec_names) { 1451 ML_(dinfo_free)(di->symtab[r].sec_names); 1452 di->symtab[r].sec_names = NULL; 1453 } 1454 /* Completely zap the entry -- paranoia to make it more 1455 likely we'll notice if we inadvertantly use it 1456 again. */ 1457 VG_(memset)(&di->symtab[r], 0, sizeof(DiSym)); 1458 } else { 1459 w = r; 1460 } 1461 } 1462 TRACE_SYMTAB( "canonicaliseSymtab: %ld symbols merged\n", n_merged); 1463 if (n_merged == 0) 1464 break; 1465 /* Now a pass to squeeze out any unused ones */ 1466 w = 0; 1467 for (r = 0; r < di->symtab_used; r++) { 1468 vg_assert(w <= r); 1469 if (di->symtab[r].pri_name == NULL) 1470 continue; 1471 if (w < r) { 1472 di->symtab[w] = di->symtab[r]; 1473 } 1474 w++; 1475 } 1476 vg_assert(w + n_merged == di->symtab_used); 1477 di->symtab_used = w; 1478 } 1479 1480 /* Detect and "fix" overlapping address ranges. */ 1481 n_truncated = 0; 1482 1483 for (i = 0; i < ((Word)di->symtab_used) -1; i++) { 1484 1485 vg_assert(di->symtab[i].addr <= di->symtab[i+1].addr); 1486 1487 /* Check for common (no overlap) case. */ 1488 if (di->symtab[i].addr + di->symtab[i].size 1489 <= di->symtab[i+1].addr) 1490 continue; 1491 1492 /* There's an overlap. Truncate one or the other. */ 1493 if (di->trace_symtab) { 1494 VG_(printf)("overlapping address ranges in symbol table\n\t"); 1495 ML_(ppSym)( i, &di->symtab[i] ); 1496 VG_(printf)("\t"); 1497 ML_(ppSym)( i+1, &di->symtab[i+1] ); 1498 VG_(printf)("\n"); 1499 } 1500 1501 /* Truncate one or the other. */ 1502 sta1 = di->symtab[i].addr; 1503 end1 = sta1 + di->symtab[i].size - 1; 1504 toc1 = di->symtab[i].tocptr; 1505 pri1 = di->symtab[i].pri_name; 1506 sec1 = di->symtab[i].sec_names; 1507 ist1 = di->symtab[i].isText; 1508 isf1 = di->symtab[i].isIFunc; 1509 1510 sta2 = di->symtab[i+1].addr; 1511 end2 = sta2 + di->symtab[i+1].size - 1; 1512 toc2 = di->symtab[i+1].tocptr; 1513 pri2 = di->symtab[i+1].pri_name; 1514 sec2 = di->symtab[i+1].sec_names; 1515 ist2 = di->symtab[i+1].isText; 1516 isf2 = di->symtab[i+1].isIFunc; 1517 1518 if (sta1 < sta2) { 1519 end1 = sta2 - 1; 1520 } else { 1521 vg_assert(sta1 == sta2); 1522 if (end1 > end2) { 1523 sta1 = end2 + 1; 1524 SWAP(Addr,sta1,sta2); SWAP(Addr,end1,end2); SWAP(Addr,toc1,toc2); 1525 SWAP(HChar*,pri1,pri2); SWAP(HChar**,sec1,sec2); 1526 SWAP(Bool,ist1,ist2); SWAP(Bool,isf1,isf2); 1527 } else 1528 if (end1 < end2) { 1529 sta2 = end1 + 1; 1530 } else { 1531 /* end1 == end2. Identical addr ranges. We'll eventually wind 1532 up back at cleanup_more, which will take care of it. */ 1533 } 1534 } 1535 di->symtab[i].addr = sta1; 1536 di->symtab[i].size = end1 - sta1 + 1; 1537 di->symtab[i].tocptr = toc1; 1538 di->symtab[i].pri_name = pri1; 1539 di->symtab[i].sec_names = sec1; 1540 di->symtab[i].isText = ist1; 1541 di->symtab[i].isIFunc = isf1; 1542 1543 di->symtab[i+1].addr = sta2; 1544 di->symtab[i+1].size = end2 - sta2 + 1; 1545 di->symtab[i+1].tocptr = toc2; 1546 di->symtab[i+1].pri_name = pri2; 1547 di->symtab[i+1].sec_names = sec2; 1548 di->symtab[i+1].isText = ist2; 1549 di->symtab[i+1].isIFunc = isf2; 1550 1551 vg_assert(sta1 <= sta2); 1552 vg_assert(di->symtab[i].size > 0); 1553 vg_assert(di->symtab[i+1].size > 0); 1554 /* It may be that the i+1 entry now needs to be moved further 1555 along to maintain the address order requirement. */ 1556 j = i+1; 1557 while (j < ((Word)di->symtab_used)-1 1558 && di->symtab[j].addr > di->symtab[j+1].addr) { 1559 SWAP(DiSym,di->symtab[j],di->symtab[j+1]); 1560 j++; 1561 } 1562 n_truncated++; 1563 } 1564 1565 if (n_truncated > 0) goto cleanup_more; 1566 1567 /* Ensure relevant postconditions hold. */ 1568 for (i = 0; i < ((Word)di->symtab_used)-1; i++) { 1569 /* No zero-sized symbols. */ 1570 vg_assert(di->symtab[i].size > 0); 1571 /* In order. */ 1572 vg_assert(di->symtab[i].addr < di->symtab[i+1].addr); 1573 /* No overlaps. */ 1574 vg_assert(di->symtab[i].addr + di->symtab[i].size - 1 1575 < di->symtab[i+1].addr); 1576 /* Names are sane(ish) */ 1577 vg_assert(di->symtab[i].pri_name); 1578 if (di->symtab[i].sec_names) { 1579 vg_assert(di->symtab[i].sec_names[0]); 1580 } 1581 } 1582 1583 /* For each symbol that has more than one name, use preferName to 1584 select the primary name. This is a complete kludge in that 1585 doing it properly requires making a total ordering on the 1586 candidate names, whilst what we have to work with is an ad-hoc 1587 binary relation (preferName) that certainly doesn't have the 1588 relevant transitivity etc properties that are needed to induce a 1589 legitimate total order. Doesn't matter though if it doesn't 1590 always work right since this is only used to generate names to 1591 show the user. */ 1592 for (i = 0; i < ((Word)di->symtab_used)-1; i++) { 1593 DiSym* sym = &di->symtab[i]; 1594 HChar** sec = sym->sec_names; 1595 if (!sec) 1596 continue; 1597 /* Slow but simple. Copy all the cands into a temp array, 1598 choose the primary name, and copy them all back again. */ 1599 Word n_tmp = 1; 1600 while (*sec) { n_tmp++; sec++; } 1601 j = 0; 1602 HChar** tmp = ML_(dinfo_zalloc)( "di.storage.cS.1", 1603 (n_tmp+1) * sizeof(HChar*) ); 1604 tmp[j++] = sym->pri_name; 1605 sec = sym->sec_names; 1606 while (*sec) { tmp[j++] = *sec; sec++; } 1607 vg_assert(j == n_tmp); 1608 vg_assert(tmp[n_tmp] == NULL); /* because of zalloc */ 1609 /* Choose the most favoured. */ 1610 Word best = 0; 1611 for (j = 1; j < n_tmp; j++) { 1612 if (preferName(di, tmp[best], tmp[j], di->symtab[i].addr)) { 1613 /* best is unchanged */ 1614 } else { 1615 best = j; 1616 } 1617 } 1618 vg_assert(best >= 0 && best < n_tmp); 1619 /* Copy back */ 1620 sym->pri_name = tmp[best]; 1621 HChar** cursor = sym->sec_names; 1622 for (j = 0; j < n_tmp; j++) { 1623 if (j == best) 1624 continue; 1625 *cursor = tmp[j]; 1626 cursor++; 1627 } 1628 vg_assert(*cursor == NULL); 1629 ML_(dinfo_free)( tmp ); 1630 } 1631 1632 # undef SWAP 1633 } 1634 1635 1636 /* Sort the location table by starting address. Mash the table around 1637 so as to establish the property that addresses are in order and the 1638 ranges do not overlap. This facilitates using binary search to map 1639 addresses to locations when we come to query the table. 1640 */ 1641 static Int compare_DiLoc ( const void* va, const void* vb ) 1642 { 1643 const DiLoc* a = va; 1644 const DiLoc* b = vb; 1645 if (a->addr < b->addr) return -1; 1646 if (a->addr > b->addr) return 1; 1647 return 0; 1648 } 1649 1650 static void canonicaliseLoctab ( struct _DebugInfo* di ) 1651 { 1652 Word i, j; 1653 1654 # define SWAP(ty,aa,bb) \ 1655 do { ty tt = (aa); (aa) = (bb); (bb) = tt; } while (0); 1656 1657 if (di->loctab_used == 0) 1658 return; 1659 1660 /* Sort by start address. */ 1661 VG_(ssort)(di->loctab, di->loctab_used, 1662 sizeof(*di->loctab), compare_DiLoc); 1663 1664 /* If two adjacent entries overlap, truncate the first. */ 1665 for (i = 0; i < ((Word)di->loctab_used)-1; i++) { 1666 vg_assert(di->loctab[i].size < 10000); 1667 if (di->loctab[i].addr + di->loctab[i].size > di->loctab[i+1].addr) { 1668 /* Do this in signed int32 because the actual .size fields 1669 are only 12 bits. */ 1670 Int new_size = di->loctab[i+1].addr - di->loctab[i].addr; 1671 if (new_size < 0) { 1672 di->loctab[i].size = 0; 1673 } else 1674 if (new_size > MAX_LOC_SIZE) { 1675 di->loctab[i].size = MAX_LOC_SIZE; 1676 } else { 1677 di->loctab[i].size = (UShort)new_size; 1678 } 1679 } 1680 } 1681 1682 /* Zap any zero-sized entries resulting from the truncation 1683 process. */ 1684 j = 0; 1685 for (i = 0; i < (Word)di->loctab_used; i++) { 1686 if (di->loctab[i].size > 0) { 1687 if (j != i) 1688 di->loctab[j] = di->loctab[i]; 1689 j++; 1690 } 1691 } 1692 di->loctab_used = j; 1693 1694 /* Ensure relevant postconditions hold. */ 1695 for (i = 0; i < ((Word)di->loctab_used)-1; i++) { 1696 /* 1697 VG_(printf)("%d (%d) %d 0x%x\n", 1698 i, di->loctab[i+1].confident, 1699 di->loctab[i+1].size, di->loctab[i+1].addr ); 1700 */ 1701 /* No zero-sized symbols. */ 1702 vg_assert(di->loctab[i].size > 0); 1703 /* In order. */ 1704 vg_assert(di->loctab[i].addr < di->loctab[i+1].addr); 1705 /* No overlaps. */ 1706 vg_assert(di->loctab[i].addr + di->loctab[i].size - 1 1707 < di->loctab[i+1].addr); 1708 } 1709 # undef SWAP 1710 1711 /* Free up unused space at the end of the table. */ 1712 shrinkLocTab(di); 1713 } 1714 1715 1716 /* Sort the call-frame-info table by starting address. Mash the table 1717 around so as to establish the property that addresses are in order 1718 and the ranges do not overlap. This facilitates using binary 1719 search to map addresses to locations when we come to query the 1720 table. 1721 1722 Also, set cfisi_minaddr and cfisi_maxaddr to be the min and max of 1723 any of the address ranges contained in cfisi[0 .. cfisi_used-1], so 1724 as to facilitate rapidly skipping this SegInfo when looking for an 1725 address which falls outside that range. 1726 */ 1727 static Int compare_DiCfSI ( const void* va, const void* vb ) 1728 { 1729 const DiCfSI* a = va; 1730 const DiCfSI* b = vb; 1731 if (a->base < b->base) return -1; 1732 if (a->base > b->base) return 1; 1733 return 0; 1734 } 1735 1736 void ML_(canonicaliseCFI) ( struct _DebugInfo* di ) 1737 { 1738 Word i, j; 1739 const Addr minAvma = 0; 1740 const Addr maxAvma = ~minAvma; 1741 1742 /* Note: take care in here. di->cfsi can be NULL, in which 1743 case _used and _size fields will be zero. */ 1744 if (di->cfsi == NULL) { 1745 vg_assert(di->cfsi_used == 0); 1746 vg_assert(di->cfsi_size == 0); 1747 } 1748 1749 /* Set cfsi_minavma and cfsi_maxavma to summarise the entire 1750 address range contained in cfsi[0 .. cfsi_used-1]. */ 1751 di->cfsi_minavma = maxAvma; 1752 di->cfsi_maxavma = minAvma; 1753 for (i = 0; i < (Word)di->cfsi_used; i++) { 1754 Addr here_min = di->cfsi[i].base; 1755 Addr here_max = di->cfsi[i].base + di->cfsi[i].len - 1; 1756 if (here_min < di->cfsi_minavma) 1757 di->cfsi_minavma = here_min; 1758 if (here_max > di->cfsi_maxavma) 1759 di->cfsi_maxavma = here_max; 1760 } 1761 1762 if (di->trace_cfi) 1763 VG_(printf)("canonicaliseCfiSI: %ld entries, %#lx .. %#lx\n", 1764 di->cfsi_used, 1765 di->cfsi_minavma, di->cfsi_maxavma); 1766 1767 /* Sort the cfsi array by base address. */ 1768 VG_(ssort)(di->cfsi, di->cfsi_used, sizeof(*di->cfsi), compare_DiCfSI); 1769 1770 /* If two adjacent entries overlap, truncate the first. */ 1771 for (i = 0; i < (Word)di->cfsi_used-1; i++) { 1772 if (di->cfsi[i].base + di->cfsi[i].len > di->cfsi[i+1].base) { 1773 Word new_len = di->cfsi[i+1].base - di->cfsi[i].base; 1774 /* how could it be otherwise? The entries are sorted by the 1775 .base field. */ 1776 vg_assert(new_len >= 0); 1777 vg_assert(new_len <= di->cfsi[i].len); 1778 di->cfsi[i].len = new_len; 1779 } 1780 } 1781 1782 /* Zap any zero-sized entries resulting from the truncation 1783 process. */ 1784 j = 0; 1785 for (i = 0; i < (Word)di->cfsi_used; i++) { 1786 if (di->cfsi[i].len > 0) { 1787 if (j != i) 1788 di->cfsi[j] = di->cfsi[i]; 1789 j++; 1790 } 1791 } 1792 /* VG_(printf)("XXXXXXXXXXXXX %d %d\n", di->cfsi_used, j); */ 1793 di->cfsi_used = j; 1794 1795 /* Ensure relevant postconditions hold. */ 1796 for (i = 0; i < (Word)di->cfsi_used; i++) { 1797 /* No zero-length ranges. */ 1798 vg_assert(di->cfsi[i].len > 0); 1799 /* Makes sense w.r.t. summary address range */ 1800 vg_assert(di->cfsi[i].base >= di->cfsi_minavma); 1801 vg_assert(di->cfsi[i].base + di->cfsi[i].len - 1 1802 <= di->cfsi_maxavma); 1803 1804 if (i < di->cfsi_used - 1) { 1805 /* 1806 if (!(di->cfsi[i].base < di->cfsi[i+1].base)) { 1807 VG_(printf)("\nOOO cfsis:\n"); 1808 ML_(ppCfiSI)(&di->cfsi[i]); 1809 ML_(ppCfiSI)(&di->cfsi[i+1]); 1810 } 1811 */ 1812 /* In order. */ 1813 vg_assert(di->cfsi[i].base < di->cfsi[i+1].base); 1814 /* No overlaps. */ 1815 vg_assert(di->cfsi[i].base + di->cfsi[i].len - 1 1816 < di->cfsi[i+1].base); 1817 } 1818 } 1819 1820 } 1821 1822 1823 /* Canonicalise the tables held by 'di', in preparation for use. Call 1824 this after finishing adding entries to these tables. */ 1825 void ML_(canonicaliseTables) ( struct _DebugInfo* di ) 1826 { 1827 canonicaliseSymtab ( di ); 1828 canonicaliseLoctab ( di ); 1829 ML_(canonicaliseCFI) ( di ); 1830 canonicaliseVarInfo ( di ); 1831 } 1832 1833 1834 /*------------------------------------------------------------*/ 1835 /*--- Searching the tables ---*/ 1836 /*------------------------------------------------------------*/ 1837 1838 /* Find a symbol-table index containing the specified pointer, or -1 1839 if not found. Binary search. */ 1840 1841 Word ML_(search_one_symtab) ( struct _DebugInfo* di, Addr ptr, 1842 Bool match_anywhere_in_sym, 1843 Bool findText ) 1844 { 1845 Addr a_mid_lo, a_mid_hi; 1846 Word mid, size, 1847 lo = 0, 1848 hi = di->symtab_used-1; 1849 while (True) { 1850 /* current unsearched space is from lo to hi, inclusive. */ 1851 if (lo > hi) return -1; /* not found */ 1852 mid = (lo + hi) / 2; 1853 a_mid_lo = di->symtab[mid].addr; 1854 size = ( match_anywhere_in_sym 1855 ? di->symtab[mid].size 1856 : 1); 1857 a_mid_hi = ((Addr)di->symtab[mid].addr) + size - 1; 1858 1859 if (ptr < a_mid_lo) { hi = mid-1; continue; } 1860 if (ptr > a_mid_hi) { lo = mid+1; continue; } 1861 vg_assert(ptr >= a_mid_lo && ptr <= a_mid_hi); 1862 /* Found a symbol with the correct address range. But is it 1863 of the right kind (text vs data) ? */ 1864 if ( findText && di->symtab[mid].isText ) return mid; 1865 if ( (!findText) && (!di->symtab[mid].isText) ) return mid; 1866 return -1; 1867 } 1868 } 1869 1870 1871 /* Find a location-table index containing the specified pointer, or -1 1872 if not found. Binary search. */ 1873 1874 Word ML_(search_one_loctab) ( struct _DebugInfo* di, Addr ptr ) 1875 { 1876 Addr a_mid_lo, a_mid_hi; 1877 Word mid, 1878 lo = 0, 1879 hi = di->loctab_used-1; 1880 while (True) { 1881 /* current unsearched space is from lo to hi, inclusive. */ 1882 if (lo > hi) return -1; /* not found */ 1883 mid = (lo + hi) / 2; 1884 a_mid_lo = di->loctab[mid].addr; 1885 a_mid_hi = ((Addr)di->loctab[mid].addr) + di->loctab[mid].size - 1; 1886 1887 if (ptr < a_mid_lo) { hi = mid-1; continue; } 1888 if (ptr > a_mid_hi) { lo = mid+1; continue; } 1889 vg_assert(ptr >= a_mid_lo && ptr <= a_mid_hi); 1890 return mid; 1891 } 1892 } 1893 1894 1895 /* Find a CFI-table index containing the specified pointer, or -1 1896 if not found. Binary search. */ 1897 1898 Word ML_(search_one_cfitab) ( struct _DebugInfo* di, Addr ptr ) 1899 { 1900 Addr a_mid_lo, a_mid_hi; 1901 Word mid, size, 1902 lo = 0, 1903 hi = di->cfsi_used-1; 1904 while (True) { 1905 /* current unsearched space is from lo to hi, inclusive. */ 1906 if (lo > hi) return -1; /* not found */ 1907 mid = (lo + hi) / 2; 1908 a_mid_lo = di->cfsi[mid].base; 1909 size = di->cfsi[mid].len; 1910 a_mid_hi = a_mid_lo + size - 1; 1911 vg_assert(a_mid_hi >= a_mid_lo); 1912 if (ptr < a_mid_lo) { hi = mid-1; continue; } 1913 if (ptr > a_mid_hi) { lo = mid+1; continue; } 1914 vg_assert(ptr >= a_mid_lo && ptr <= a_mid_hi); 1915 return mid; 1916 } 1917 } 1918 1919 1920 /* Find a FPO-table index containing the specified pointer, or -1 1921 if not found. Binary search. */ 1922 1923 Word ML_(search_one_fpotab) ( struct _DebugInfo* di, Addr ptr ) 1924 { 1925 Addr const addr = ptr - di->fpo_base_avma; 1926 Addr a_mid_lo, a_mid_hi; 1927 Word mid, size, 1928 lo = 0, 1929 hi = di->fpo_size-1; 1930 while (True) { 1931 /* current unsearched space is from lo to hi, inclusive. */ 1932 if (lo > hi) return -1; /* not found */ 1933 mid = (lo + hi) / 2; 1934 a_mid_lo = di->fpo[mid].ulOffStart; 1935 size = di->fpo[mid].cbProcSize; 1936 a_mid_hi = a_mid_lo + size - 1; 1937 vg_assert(a_mid_hi >= a_mid_lo); 1938 if (addr < a_mid_lo) { hi = mid-1; continue; } 1939 if (addr > a_mid_hi) { lo = mid+1; continue; } 1940 vg_assert(addr >= a_mid_lo && addr <= a_mid_hi); 1941 return mid; 1942 } 1943 } 1944 1945 /*--------------------------------------------------------------------*/ 1946 /*--- end ---*/ 1947 /*--------------------------------------------------------------------*/ 1948