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@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. */
ML_(symerr)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. */
ML_(ppSym)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. */
ML_(ppDiCfSI)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 */
ML_(addStr)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. */
ML_(addStrFromCursor)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 */
ML_(addSym)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 */
addLoc(struct _DebugInfo * di,DiLoc * loc)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 */
shrinkLocTab(struct _DebugInfo * di)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 */
ML_(addLineInfo)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. */
ML_(addDiCfSI)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
ML_(CfiExpr_Undef)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 }
ML_(CfiExpr_Deref)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 }
ML_(CfiExpr_Const)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 }
ML_(CfiExpr_Unop)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 }
ML_(CfiExpr_Binop)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 }
ML_(CfiExpr_CfiReg)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 }
ML_(CfiExpr_DwReg)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
ppCfiUnop(CfiUnop op)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
ppCfiBinop(CfiBinop op)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
ppCfiReg(CfiReg reg)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
ML_(ppCfiExpr)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
ML_(cmp_for_DiAddrRange_range)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
show_scope(OSet * scope,const HChar * who)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. */
add_var_to_arange(OSet * scope,Addr aMin,Addr aMax,DiVariable * var)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. */
ML_(addVar)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. */
canonicaliseVarInfo(struct _DebugInfo * di)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 */
compare_DiSym(const void * va,const void * vb)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@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
preferName(struct _DebugInfo * di,HChar * a_name,HChar * b_name,Addr sym_avma)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
add_DiSym_names_to_from(DebugInfo * di,DiSym * to,DiSym * from)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
canonicaliseSymtab(struct _DebugInfo * di)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 */
compare_DiLoc(const void * va,const void * vb)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
canonicaliseLoctab(struct _DebugInfo * di)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 */
compare_DiCfSI(const void * va,const void * vb)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
ML_(canonicaliseCFI)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. */
ML_(canonicaliseTables)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
ML_(search_one_symtab)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
ML_(search_one_loctab)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
ML_(search_one_cfitab)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
ML_(search_one_fpotab)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