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-2015 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 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_debuglog.h"
44 #include "pub_core_libcassert.h"
45 #include "pub_core_libcbase.h"
46 #include "pub_core_libcprint.h"
47 #include "pub_core_xarray.h"
48 #include "pub_core_oset.h"
49 #include "pub_core_deduppoolalloc.h"
50
51 #include "priv_misc.h" /* dinfo_zalloc/free/strdup */
52 #include "priv_image.h"
53 #include "priv_d3basics.h" /* ML_(pp_GX) */
54 #include "priv_tytypes.h"
55 #include "priv_storage.h" /* self */
56
57
58 /*------------------------------------------------------------*/
59 /*--- Misc (printing, errors) ---*/
60 /*------------------------------------------------------------*/
61
62 /* Show a non-fatal debug info reading error. Use VG_(core_panic) for
63 fatal errors. 'serious' errors are shown regardless of the
64 verbosity setting. */
ML_(symerr)65 void ML_(symerr) ( const DebugInfo* di, Bool serious, const HChar* msg )
66 {
67 /* XML mode hides everything :-( */
68 if (VG_(clo_xml))
69 return;
70
71 if (serious) {
72
73 VG_(message)(Vg_DebugMsg, "WARNING: Serious error when "
74 "reading debug info\n");
75 if (True || VG_(clo_verbosity) < 2) {
76 /* Need to show what the file name is, at verbosity levels 2
77 or below, since that won't already have been shown */
78 VG_(message)(Vg_DebugMsg,
79 "When reading debug info from %s:\n",
80 (di && di->fsm.filename) ? di->fsm.filename
81 : "???");
82 }
83 VG_(message)(Vg_DebugMsg, "%s\n", msg);
84
85 } else { /* !serious */
86
87 if (VG_(clo_verbosity) >= 2)
88 VG_(message)(Vg_DebugMsg, "%s\n", msg);
89
90 }
91 }
92
93
94 /* Print a symbol. */
ML_(ppSym)95 void ML_(ppSym) ( Int idx, const DiSym* sym )
96 {
97 const HChar** sec_names = sym->sec_names;
98 vg_assert(sym->pri_name);
99 if (sec_names)
100 vg_assert(sec_names);
101 VG_(printf)( "%5d: %c%c %#8lx .. %#8lx (%u) %s%s",
102 idx,
103 sym->isText ? 'T' : '-',
104 sym->isIFunc ? 'I' : '-',
105 sym->avmas.main,
106 sym->avmas.main + sym->size - 1, sym->size,
107 sym->pri_name, sec_names ? " " : "" );
108 if (sec_names) {
109 while (*sec_names) {
110 VG_(printf)("%s%s", *sec_names, *(sec_names+1) ? " " : "");
111 sec_names++;
112 }
113 }
114 VG_(printf)("\n");
115 }
116
117 /* Print a call-frame-info summary. */
ML_(ppDiCfSI)118 void ML_(ppDiCfSI) ( const XArray* /* of CfiExpr */ exprs,
119 Addr base, UInt len,
120 const DiCfSI_m* si_m )
121 {
122 # define SHOW_HOW(_how, _off) \
123 do { \
124 if (_how == CFIR_UNKNOWN) { \
125 VG_(printf)("Unknown"); \
126 } else \
127 if (_how == CFIR_SAME) { \
128 VG_(printf)("Same"); \
129 } else \
130 if (_how == CFIR_CFAREL) { \
131 VG_(printf)("cfa+%d", _off); \
132 } else \
133 if (_how == CFIR_MEMCFAREL) { \
134 VG_(printf)("*(cfa+%d)", _off); \
135 } else \
136 if (_how == CFIR_EXPR) { \
137 VG_(printf)("{"); \
138 ML_(ppCfiExpr)(exprs, _off); \
139 VG_(printf)("}"); \
140 } else { \
141 vg_assert(0+0); \
142 } \
143 } while (0)
144
145 if (base != 0 || len != 0)
146 VG_(printf)("[%#lx .. %#lx]: ", base, base + len - 1);
147 else
148 VG_(printf)("[]: ");
149
150 switch (si_m->cfa_how) {
151 case CFIC_IA_SPREL:
152 VG_(printf)("let cfa=oldSP+%d", si_m->cfa_off);
153 break;
154 case CFIC_IA_BPREL:
155 VG_(printf)("let cfa=oldBP+%d", si_m->cfa_off);
156 break;
157 case CFIC_ARM_R13REL:
158 VG_(printf)("let cfa=oldR13+%d", si_m->cfa_off);
159 break;
160 case CFIC_ARM_R12REL:
161 VG_(printf)("let cfa=oldR12+%d", si_m->cfa_off);
162 break;
163 case CFIC_ARM_R11REL:
164 VG_(printf)("let cfa=oldR11+%d", si_m->cfa_off);
165 break;
166 case CFIR_SAME:
167 VG_(printf)("let cfa=Same");
168 break;
169 case CFIC_ARM_R7REL:
170 VG_(printf)("let cfa=oldR7+%d", si_m->cfa_off);
171 break;
172 case CFIC_ARM64_SPREL:
173 VG_(printf)("let cfa=oldSP+%d", si_m->cfa_off);
174 break;
175 case CFIC_ARM64_X29REL:
176 VG_(printf)("let cfa=oldX29+%d", si_m->cfa_off);
177 break;
178 case CFIC_EXPR:
179 VG_(printf)("let cfa={");
180 ML_(ppCfiExpr)(exprs, si_m->cfa_off);
181 VG_(printf)("}");
182 break;
183 default:
184 vg_assert(0);
185 }
186
187 VG_(printf)(" in RA=");
188 SHOW_HOW(si_m->ra_how, si_m->ra_off);
189 # if defined(VGA_x86) || defined(VGA_amd64)
190 VG_(printf)(" SP=");
191 SHOW_HOW(si_m->sp_how, si_m->sp_off);
192 VG_(printf)(" BP=");
193 SHOW_HOW(si_m->bp_how, si_m->bp_off);
194 # elif defined(VGA_arm)
195 VG_(printf)(" R14=");
196 SHOW_HOW(si_m->r14_how, si_m->r14_off);
197 VG_(printf)(" R13=");
198 SHOW_HOW(si_m->r13_how, si_m->r13_off);
199 VG_(printf)(" R12=");
200 SHOW_HOW(si_m->r12_how, si_m->r12_off);
201 VG_(printf)(" R11=");
202 SHOW_HOW(si_m->r11_how, si_m->r11_off);
203 VG_(printf)(" R7=");
204 SHOW_HOW(si_m->r7_how, si_m->r7_off);
205 # elif defined(VGA_ppc32) || defined(VGA_ppc64be) || defined(VGA_ppc64le)
206 # elif defined(VGA_s390x) || defined(VGA_mips32) || defined(VGA_mips64)
207 VG_(printf)(" SP=");
208 SHOW_HOW(si_m->sp_how, si_m->sp_off);
209 VG_(printf)(" FP=");
210 SHOW_HOW(si_m->fp_how, si_m->fp_off);
211 # elif defined(VGA_arm64)
212 VG_(printf)(" SP=");
213 SHOW_HOW(si_m->sp_how, si_m->sp_off);
214 VG_(printf)(" X30=");
215 SHOW_HOW(si_m->x30_how, si_m->x30_off);
216 VG_(printf)(" X29=");
217 SHOW_HOW(si_m->x29_how, si_m->x29_off);
218 # elif defined(VGA_tilegx)
219 VG_(printf)(" SP=");
220 SHOW_HOW(si_m->sp_how, si_m->sp_off);
221 VG_(printf)(" FP=");
222 SHOW_HOW(si_m->fp_how, si_m->fp_off);
223 # else
224 # error "Unknown arch"
225 # endif
226 VG_(printf)("\n");
227 # undef SHOW_HOW
228 }
229
230
231 /*------------------------------------------------------------*/
232 /*--- Adding stuff ---*/
233 /*------------------------------------------------------------*/
234
235 /* Add a str to the string table, including terminating zero, and
236 return pointer to the string in vg_strtab. Unless it's been seen
237 recently, in which case we find the old pointer and return that.
238 This avoids the most egregious duplications.
239
240 JSGF: changed from returning an index to a pointer, and changed to
241 a chunking memory allocator rather than reallocating, so the
242 pointers are stable.
243 */
ML_(addStr)244 const HChar* ML_(addStr) ( DebugInfo* di, const HChar* str, Int len )
245 {
246 if (len == -1) {
247 len = VG_(strlen)(str);
248 } else {
249 vg_assert(len >= 0);
250 }
251 if (UNLIKELY(di->strpool == NULL))
252 di->strpool = VG_(newDedupPA)(SEGINFO_STRPOOLSIZE,
253 1,
254 ML_(dinfo_zalloc),
255 "di.storage.addStr.1",
256 ML_(dinfo_free));
257 return VG_(allocEltDedupPA) (di->strpool, len+1, str);
258 }
259
ML_(addFnDn)260 UInt ML_(addFnDn) (struct _DebugInfo* di,
261 const HChar* filename,
262 const HChar* dirname)
263 {
264 FnDn fndn;
265 UInt fndn_ix;
266
267 if (UNLIKELY(di->fndnpool == NULL))
268 di->fndnpool = VG_(newDedupPA)(500,
269 vg_alignof(FnDn),
270 ML_(dinfo_zalloc),
271 "di.storage.addFnDn.1",
272 ML_(dinfo_free));
273 fndn.filename = ML_(addStr)(di, filename, -1);
274 fndn.dirname = dirname ? ML_(addStr)(di, dirname, -1) : NULL;
275 fndn_ix = VG_(allocFixedEltDedupPA) (di->fndnpool, sizeof(FnDn), &fndn);
276 return fndn_ix;
277 }
278
ML_(fndn_ix2filename)279 const HChar* ML_(fndn_ix2filename) (const DebugInfo* di,
280 UInt fndn_ix)
281 {
282 FnDn *fndn;
283 if (fndn_ix == 0)
284 return "???";
285 else {
286 fndn = VG_(indexEltNumber) (di->fndnpool, fndn_ix);
287 return fndn->filename;
288 }
289 }
290
ML_(fndn_ix2dirname)291 const HChar* ML_(fndn_ix2dirname) (const DebugInfo* di,
292 UInt fndn_ix)
293 {
294 FnDn *fndn;
295 if (fndn_ix == 0)
296 return "";
297 else {
298 fndn = VG_(indexEltNumber) (di->fndnpool, fndn_ix);
299 if (fndn->dirname)
300 return fndn->dirname;
301 else
302 return "";
303 }
304 }
305
306 /* Add a string to the string table of a DebugInfo, by copying the
307 string from the given DiCursor. Measures the length of the string
308 itself. */
ML_(addStrFromCursor)309 const HChar* ML_(addStrFromCursor)( DebugInfo* di, DiCursor c )
310 {
311 /* This is a less-than-stellar implementation, but it should
312 work. */
313 vg_assert(ML_(cur_is_valid)(c));
314 HChar* str = ML_(cur_read_strdup)(c, "di.addStrFromCursor.1");
315 const HChar* res = ML_(addStr)(di, str, -1);
316 ML_(dinfo_free)(str);
317 return res;
318 }
319
320
321 /* Add a symbol to the symbol table, by copying *sym. 'sym' may only
322 have one name, so there's no complexities to do with deep vs
323 shallow copying of the sec_name array. This is checked.
324 */
ML_(addSym)325 void ML_(addSym) ( struct _DebugInfo* di, DiSym* sym )
326 {
327 UInt new_sz, i;
328 DiSym* new_tab;
329
330 vg_assert(sym->pri_name != NULL);
331 vg_assert(sym->sec_names == NULL);
332
333 /* Ignore zero-sized syms. */
334 if (sym->size == 0) return;
335
336 if (di->symtab_used == di->symtab_size) {
337 new_sz = 2 * di->symtab_size;
338 if (new_sz == 0) new_sz = 500;
339 new_tab = ML_(dinfo_zalloc)( "di.storage.addSym.1",
340 new_sz * sizeof(DiSym) );
341 if (di->symtab != NULL) {
342 for (i = 0; i < di->symtab_used; i++)
343 new_tab[i] = di->symtab[i];
344 ML_(dinfo_free)(di->symtab);
345 }
346 di->symtab = new_tab;
347 di->symtab_size = new_sz;
348 }
349
350 di->symtab[di->symtab_used++] = *sym;
351 vg_assert(di->symtab_used <= di->symtab_size);
352 }
353
ML_(fndn_ix)354 UInt ML_(fndn_ix) (const DebugInfo* di, Word locno)
355 {
356 UInt fndn_ix;
357
358 switch(di->sizeof_fndn_ix) {
359 case 1: fndn_ix = ((UChar*) di->loctab_fndn_ix)[locno]; break;
360 case 2: fndn_ix = ((UShort*) di->loctab_fndn_ix)[locno]; break;
361 case 4: fndn_ix = ((UInt*) di->loctab_fndn_ix)[locno]; break;
362 default: vg_assert(0);
363 }
364 return fndn_ix;
365 }
366
set_fndn_ix(struct _DebugInfo * di,Word locno,UInt fndn_ix)367 static inline void set_fndn_ix (struct _DebugInfo* di, Word locno, UInt fndn_ix)
368 {
369 Word i;
370
371 switch(di->sizeof_fndn_ix) {
372 case 1:
373 if (LIKELY (fndn_ix <= 255)) {
374 ((UChar*) di->loctab_fndn_ix)[locno] = fndn_ix;
375 return;
376 }
377 {
378 UChar* old = (UChar*) di->loctab_fndn_ix;
379 UShort* new = ML_(dinfo_zalloc)( "di.storage.sfix.1",
380 di->loctab_size * 2 );
381 for (i = 0; i < di->loctab_used; i++)
382 new[i] = old[i];
383 ML_(dinfo_free)(old);
384 di->sizeof_fndn_ix = 2;
385 di->loctab_fndn_ix = new;
386 }
387 // Fallthrough
388
389 case 2:
390 if (LIKELY (fndn_ix <= 65535)) {
391 ((UShort*) di->loctab_fndn_ix)[locno] = fndn_ix;
392 return;
393 }
394 {
395 UShort* old = (UShort*) di->loctab_fndn_ix;
396 UInt* new = ML_(dinfo_zalloc)( "di.storage.sfix.2",
397 di->loctab_size * 4 );
398 for (i = 0; i < di->loctab_used; i++)
399 new[i] = old[i];
400 ML_(dinfo_free)(old);
401 di->sizeof_fndn_ix = 4;
402 di->loctab_fndn_ix = new;
403 }
404 // Fallthrough
405
406 case 4:
407 ((UInt*) di->loctab_fndn_ix)[locno] = fndn_ix;
408 return;
409
410 default: vg_assert(0);
411 }
412 }
413
414 /* Add a location to the location table.
415 */
addLoc(struct _DebugInfo * di,DiLoc * loc,UInt fndn_ix)416 static void addLoc ( struct _DebugInfo* di, DiLoc* loc, UInt fndn_ix )
417 {
418 /* Zero-sized locs should have been ignored earlier */
419 vg_assert(loc->size > 0);
420
421 if (di->loctab_used == di->loctab_size) {
422 UInt new_sz;
423 DiLoc* new_loctab;
424 void* new_loctab_fndn_ix;
425
426 new_sz = 2 * di->loctab_size;
427 if (new_sz == 0) new_sz = 500;
428 new_loctab = ML_(dinfo_zalloc)( "di.storage.addLoc.1",
429 new_sz * sizeof(DiLoc) );
430 if (di->sizeof_fndn_ix == 0)
431 di->sizeof_fndn_ix = 1; // To start with.
432 new_loctab_fndn_ix = ML_(dinfo_zalloc)( "di.storage.addLoc.2",
433 new_sz * di->sizeof_fndn_ix );
434 if (di->loctab != NULL) {
435 VG_(memcpy)(new_loctab, di->loctab,
436 di->loctab_used * sizeof(DiLoc));
437 VG_(memcpy)(new_loctab_fndn_ix, di->loctab_fndn_ix,
438 di->loctab_used * di->sizeof_fndn_ix);
439 ML_(dinfo_free)(di->loctab);
440 ML_(dinfo_free)(di->loctab_fndn_ix);
441 }
442 di->loctab = new_loctab;
443 di->loctab_fndn_ix = new_loctab_fndn_ix;
444 di->loctab_size = new_sz;
445 }
446
447 di->loctab[di->loctab_used] = *loc;
448 set_fndn_ix (di, di->loctab_used, fndn_ix);
449 di->loctab_used++;
450 vg_assert(di->loctab_used <= di->loctab_size);
451 }
452
453
454 /* Resize the LocTab (line number table) to save memory, by removing
455 (and, potentially, allowing m_mallocfree to unmap) any unused space
456 at the end of the table. */
shrinkLocTab(struct _DebugInfo * di)457 static void shrinkLocTab ( struct _DebugInfo* di )
458 {
459 UWord new_sz = di->loctab_used;
460 if (new_sz == di->loctab_size) return;
461 vg_assert(new_sz < di->loctab_size);
462 ML_(dinfo_shrink_block)( di->loctab, new_sz * sizeof(DiLoc));
463 ML_(dinfo_shrink_block)( di->loctab_fndn_ix, new_sz * di->sizeof_fndn_ix);
464 di->loctab_size = new_sz;
465 }
466
467
468 /* Top-level place to call to add a source-location mapping entry.
469 */
ML_(addLineInfo)470 void ML_(addLineInfo) ( struct _DebugInfo* di,
471 UInt fndn_ix,
472 Addr this,
473 Addr next,
474 Int lineno,
475 Int entry /* only needed for debug printing */
476 )
477 {
478 static const Bool debug = False;
479 DiLoc loc;
480 UWord size = next - this;
481
482 /* Ignore zero-sized locs */
483 if (this == next) return;
484
485 if (debug) {
486 FnDn *fndn = VG_(indexEltNumber) (di->fndnpool, fndn_ix);
487 VG_(printf)( " src ix %u %s %s line %d %#lx-%#lx\n",
488 fndn_ix,
489 fndn->dirname ? fndn->dirname : "(unknown)",
490 fndn->filename, lineno, this, next );
491 }
492
493 /* Maximum sanity checking. Some versions of GNU as do a shabby
494 * job with stabs entries; if anything looks suspicious, revert to
495 * a size of 1. This should catch the instruction of interest
496 * (since if using asm-level debug info, one instruction will
497 * correspond to one line, unlike with C-level debug info where
498 * multiple instructions can map to the one line), but avoid
499 * catching any other instructions bogusly. */
500 if (this > next) {
501 if (VG_(clo_verbosity) > 2) {
502 VG_(message)(Vg_DebugMsg,
503 "warning: line info addresses out of order "
504 "at entry %d: 0x%lx 0x%lx\n", entry, this, next);
505 }
506 size = 1;
507 }
508
509 if (size > MAX_LOC_SIZE) {
510 if (0)
511 VG_(message)(Vg_DebugMsg,
512 "warning: line info address range too large "
513 "at entry %d: %lu\n", entry, size);
514 size = 1;
515 }
516
517 /* At this point, we know that the original value for |size|, viz
518 |next - this|, will only still be used in the case where
519 |this| <u |next|, so it can't have underflowed. Considering
520 that and the three checks that follow it, the following must
521 hold. */
522 vg_assert(size >= 1);
523 vg_assert(size <= MAX_LOC_SIZE);
524
525 /* Rule out ones which are completely outside the r-x mapped area.
526 See "Comment_Regarding_Text_Range_Checks" elsewhere in this file
527 for background and rationale. */
528 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map);
529 if (ML_(find_rx_mapping)(di, this, this + size - 1) == NULL) {
530 if (0)
531 VG_(message)(Vg_DebugMsg,
532 "warning: ignoring line info entry falling "
533 "outside current DebugInfo: %#lx %#lx %#lx %#lx\n",
534 di->text_avma,
535 di->text_avma + di->text_size,
536 this, this + size - 1);
537 return;
538 }
539
540 if (lineno < 0) {
541 static Bool complained = False;
542 if (!complained) {
543 complained = True;
544 VG_(message)(Vg_UserMsg,
545 "warning: ignoring line info entry with "
546 "negative line number (%d)\n", lineno);
547 VG_(message)(Vg_UserMsg,
548 "(Nb: this message is only shown once)\n");
549 }
550 return;
551 }
552 if (lineno > MAX_LINENO) {
553 static Bool complained = False;
554 if (!complained) {
555 complained = True;
556 VG_(message)(Vg_UserMsg,
557 "warning: ignoring line info entry with "
558 "huge line number (%d)\n", lineno);
559 VG_(message)(Vg_UserMsg,
560 " Can't handle line numbers "
561 "greater than %d, sorry\n", MAX_LINENO);
562 VG_(message)(Vg_UserMsg,
563 "(Nb: this message is only shown once)\n");
564 }
565 return;
566 }
567
568 loc.addr = this;
569 loc.size = (UShort)size;
570 loc.lineno = lineno;
571
572 if (0) VG_(message)(Vg_DebugMsg,
573 "addLoc: addr %#lx, size %lu, line %d, fndn_ix %u\n",
574 this,size,lineno,fndn_ix);
575
576 addLoc ( di, &loc, fndn_ix );
577 }
578
579 /* Add an inlined call info to the inlined call table.
580 */
addInl(struct _DebugInfo * di,DiInlLoc * inl)581 static void addInl ( struct _DebugInfo* di, DiInlLoc* inl )
582 {
583 UInt new_sz, i;
584 DiInlLoc* new_tab;
585
586 /* empty inl should have been ignored earlier */
587 vg_assert(inl->addr_lo < inl->addr_hi);
588
589 if (di->inltab_used == di->inltab_size) {
590 new_sz = 2 * di->inltab_size;
591 if (new_sz == 0) new_sz = 500;
592 new_tab = ML_(dinfo_zalloc)( "di.storage.addInl.1",
593 new_sz * sizeof(DiInlLoc) );
594 if (di->inltab != NULL) {
595 for (i = 0; i < di->inltab_used; i++)
596 new_tab[i] = di->inltab[i];
597 ML_(dinfo_free)(di->inltab);
598 }
599 di->inltab = new_tab;
600 di->inltab_size = new_sz;
601 }
602
603 di->inltab[di->inltab_used] = *inl;
604 if (inl->addr_hi - inl->addr_lo > di->maxinl_codesz)
605 di->maxinl_codesz = inl->addr_hi - inl->addr_lo;
606 di->inltab_used++;
607 vg_assert(di->inltab_used <= di->inltab_size);
608 }
609
610
611 /* Resize the InlTab (inlined call table) to save memory, by removing
612 (and, potentially, allowing m_mallocfree to unmap) any unused space
613 at the end of the table. */
shrinkInlTab(struct _DebugInfo * di)614 static void shrinkInlTab ( struct _DebugInfo* di )
615 {
616 UWord new_sz = di->inltab_used;
617 if (new_sz == di->inltab_size) return;
618 vg_assert(new_sz < di->inltab_size);
619 ML_(dinfo_shrink_block)( di->inltab, new_sz * sizeof(DiInlLoc));
620 di->inltab_size = new_sz;
621 }
622
623 /* Top-level place to call to add a addr-to-inlined fn info. */
ML_(addInlInfo)624 void ML_(addInlInfo) ( struct _DebugInfo* di,
625 Addr addr_lo, Addr addr_hi,
626 const HChar* inlinedfn,
627 UInt fndn_ix,
628 Int lineno, UShort level)
629 {
630 DiInlLoc inl;
631
632 /* Similar paranoia as in ML_(addLineInfo). Unclear if needed. */
633 if (addr_lo >= addr_hi) {
634 if (VG_(clo_verbosity) > 2) {
635 VG_(message)(Vg_DebugMsg,
636 "warning: inlined info addresses out of order "
637 "at: 0x%lx 0x%lx\n", addr_lo, addr_hi);
638 }
639 addr_hi = addr_lo + 1;
640 }
641
642 vg_assert(lineno >= 0);
643 if (lineno > MAX_LINENO) {
644 static Bool complained = False;
645 if (!complained) {
646 complained = True;
647 VG_(message)(Vg_UserMsg,
648 "warning: ignoring inlined call info entry with "
649 "huge line number (%d)\n", lineno);
650 VG_(message)(Vg_UserMsg,
651 " Can't handle line numbers "
652 "greater than %d, sorry\n", MAX_LINENO);
653 VG_(message)(Vg_UserMsg,
654 "(Nb: this message is only shown once)\n");
655 }
656 return;
657 }
658
659 // code resulting from inlining of inlinedfn:
660 inl.addr_lo = addr_lo;
661 inl.addr_hi = addr_hi;
662 inl.inlinedfn = inlinedfn;
663 // caller:
664 inl.fndn_ix = fndn_ix;
665 inl.lineno = lineno;
666 inl.level = level;
667
668 if (0) VG_(message)
669 (Vg_DebugMsg,
670 "addInlInfo: fn %s inlined as addr_lo %#lx,addr_hi %#lx,"
671 "caller fndn_ix %u %s:%d\n",
672 inlinedfn, addr_lo, addr_hi, fndn_ix,
673 ML_(fndn_ix2filename) (di, fndn_ix), lineno);
674
675 addInl ( di, &inl );
676 }
677
ML_(get_cfsi_m)678 DiCfSI_m* ML_(get_cfsi_m) (const DebugInfo* di, UInt pos)
679 {
680 UInt cfsi_m_ix;
681
682 vg_assert(pos >= 0 && pos < di->cfsi_used);
683 switch (di->sizeof_cfsi_m_ix) {
684 case 1: cfsi_m_ix = ((UChar*) di->cfsi_m_ix)[pos]; break;
685 case 2: cfsi_m_ix = ((UShort*) di->cfsi_m_ix)[pos]; break;
686 case 4: cfsi_m_ix = ((UInt*) di->cfsi_m_ix)[pos]; break;
687 default: vg_assert(0);
688 }
689 if (cfsi_m_ix == 0)
690 return NULL; // cfi hole
691 else
692 return VG_(indexEltNumber) (di->cfsi_m_pool, cfsi_m_ix);
693 }
694
695 /* Top-level place to call to add a CFI summary record. The supplied
696 DiCfSI_m is copied. */
ML_(addDiCfSI)697 void ML_(addDiCfSI) ( struct _DebugInfo* di,
698 Addr base, UInt len, DiCfSI_m* cfsi_m )
699 {
700 static const Bool debug = False;
701 UInt new_sz;
702 DiCfSI* new_tab;
703 SSizeT delta;
704 DebugInfoMapping* map;
705 DebugInfoMapping* map2;
706
707 if (debug) {
708 VG_(printf)("adding DiCfSI: ");
709 ML_(ppDiCfSI)(di->cfsi_exprs, base, len, cfsi_m);
710 }
711
712 /* sanity */
713 vg_assert(len > 0);
714 /* Issue a warning if LEN is unexpectedly large (exceeds 5 million).
715 The implication is you have a single procedure
716 with more than 5 million bytes of code. Which is pretty
717 unlikely. Either that, or the debuginfo reader is somehow
718 broken. 5 million is of course arbitrary; but it's big enough
719 to be bigger than the size of any plausible piece of code that
720 would fall within a single procedure. But occasionally it does
721 happen (c.f. BZ #339542). */
722 if (len >= 5000000)
723 VG_(message)(Vg_DebugMsg,
724 "warning: DiCfSI %#lx .. %#lx is huge; length = %u (%s)\n",
725 base, base + len - 1, len, di->soname);
726
727 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map);
728 /* Find mapping where at least one end of the CFSI falls into. */
729 map = ML_(find_rx_mapping)(di, base, base);
730 map2 = ML_(find_rx_mapping)(di, base + len - 1,
731 base + len - 1);
732 if (map == NULL)
733 map = map2;
734 else if (map2 == NULL)
735 map2 = map;
736
737 /* Rule out ones which are completely outside the r-x mapped area
738 (or which span across different areas).
739 See "Comment_Regarding_Text_Range_Checks" elsewhere in this file
740 for background and rationale. */
741 if (map == NULL || map != map2) {
742 static Int complaints = 10;
743 if (VG_(clo_trace_cfi) || complaints > 0) {
744 complaints--;
745 if (VG_(clo_verbosity) > 1) {
746 VG_(message)(
747 Vg_DebugMsg,
748 "warning: DiCfSI %#lx .. %#lx outside mapped rx segments (%s)\n",
749 base,
750 base + len - 1,
751 di->soname
752 );
753 }
754 if (VG_(clo_trace_cfi))
755 ML_(ppDiCfSI)(di->cfsi_exprs, base, len, cfsi_m);
756 }
757 return;
758 }
759
760 /* Now we know the range is at least partially inside the r-x
761 mapped area. That implies that at least one of the ends of the
762 range falls inside the area. If necessary, clip it so it is
763 completely within the area. If we don't do this,
764 check_CFSI_related_invariants() in debuginfo.c (invariant #2)
765 will fail. See
766 "Comment_on_IMPORTANT_CFSI_REPRESENTATIONAL_INVARIANTS" in
767 priv_storage.h for background. */
768 if (base < map->avma) {
769 /* Lower end is outside the mapped area. Hence upper end must
770 be inside it. */
771 if (0) VG_(printf)("XXX truncate lower\n");
772 vg_assert(base + len - 1 >= map->avma);
773 delta = (SSizeT)(map->avma - base);
774 vg_assert(delta > 0);
775 vg_assert(delta < (SSizeT)len);
776 base += delta;
777 len -= delta;
778 }
779 else
780 if (base + len - 1 > map->avma + map->size - 1) {
781 /* Upper end is outside the mapped area. Hence lower end must be
782 inside it. */
783 if (0) VG_(printf)("XXX truncate upper\n");
784 vg_assert(base <= map->avma + map->size - 1);
785 delta = (SSizeT)( (base + len - 1)
786 - (map->avma + map->size - 1) );
787 vg_assert(delta > 0);
788 vg_assert(delta < (SSizeT)len);
789 len -= delta;
790 }
791
792 /* Final checks */
793
794 /* Because: either cfsi was entirely inside the range, in which
795 case we asserted that len > 0 at the start, OR it fell partially
796 inside the range, in which case we reduced it by some size
797 (delta) which is < its original size. */
798 vg_assert(len > 0);
799
800 /* Similar logic applies for the next two assertions. */
801 vg_assert(base >= map->avma);
802 vg_assert(base + len - 1
803 <= map->avma + map->size - 1);
804
805 if (di->cfsi_used == di->cfsi_size) {
806 new_sz = 2 * di->cfsi_size;
807 if (new_sz == 0) new_sz = 20;
808 new_tab = ML_(dinfo_zalloc)( "di.storage.addDiCfSI.1",
809 new_sz * sizeof(DiCfSI) );
810 if (di->cfsi_rd != NULL) {
811 VG_(memcpy)(new_tab, di->cfsi_rd,
812 di->cfsi_used * sizeof(DiCfSI));
813 ML_(dinfo_free)(di->cfsi_rd);
814 }
815 di->cfsi_rd = new_tab;
816 di->cfsi_size = new_sz;
817 if (di->cfsi_m_pool == NULL)
818 di->cfsi_m_pool = VG_(newDedupPA)(1000 * sizeof(DiCfSI_m),
819 vg_alignof(DiCfSI_m),
820 ML_(dinfo_zalloc),
821 "di.storage.DiCfSI_m_pool",
822 ML_(dinfo_free));
823 }
824
825 di->cfsi_rd[di->cfsi_used].base = base;
826 di->cfsi_rd[di->cfsi_used].len = len;
827 di->cfsi_rd[di->cfsi_used].cfsi_m_ix
828 = VG_(allocFixedEltDedupPA)(di->cfsi_m_pool,
829 sizeof(DiCfSI_m),
830 cfsi_m);
831 di->cfsi_used++;
832 vg_assert(di->cfsi_used <= di->cfsi_size);
833 }
834
835
ML_(CfiExpr_Undef)836 Int ML_(CfiExpr_Undef)( XArray* dst )
837 {
838 CfiExpr e;
839 VG_(memset)( &e, 0, sizeof(e) );
840 e.tag = Cex_Undef;
841 return (Int)VG_(addToXA)( dst, &e );
842 }
ML_(CfiExpr_Deref)843 Int ML_(CfiExpr_Deref)( XArray* dst, Int ixAddr )
844 {
845 CfiExpr e;
846 VG_(memset)( &e, 0, sizeof(e) );
847 e.tag = Cex_Deref;
848 e.Cex.Deref.ixAddr = ixAddr;
849 return (Int)VG_(addToXA)( dst, &e );
850 }
ML_(CfiExpr_Const)851 Int ML_(CfiExpr_Const)( XArray* dst, UWord con )
852 {
853 CfiExpr e;
854 VG_(memset)( &e, 0, sizeof(e) );
855 e.tag = Cex_Const;
856 e.Cex.Const.con = con;
857 return (Int)VG_(addToXA)( dst, &e );
858 }
ML_(CfiExpr_Unop)859 Int ML_(CfiExpr_Unop)( XArray* dst, CfiUnop op, Int ix )
860 {
861 CfiExpr e;
862 VG_(memset)( &e, 0, sizeof(e) );
863 e.tag = Cex_Unop;
864 e.Cex.Unop.op = op;
865 e.Cex.Unop.ix = ix;
866 return (Int)VG_(addToXA)( dst, &e );
867 }
ML_(CfiExpr_Binop)868 Int ML_(CfiExpr_Binop)( XArray* dst, CfiBinop op, Int ixL, Int ixR )
869 {
870 CfiExpr e;
871 VG_(memset)( &e, 0, sizeof(e) );
872 e.tag = Cex_Binop;
873 e.Cex.Binop.op = op;
874 e.Cex.Binop.ixL = ixL;
875 e.Cex.Binop.ixR = ixR;
876 return (Int)VG_(addToXA)( dst, &e );
877 }
ML_(CfiExpr_CfiReg)878 Int ML_(CfiExpr_CfiReg)( XArray* dst, CfiReg reg )
879 {
880 CfiExpr e;
881 VG_(memset)( &e, 0, sizeof(e) );
882 e.tag = Cex_CfiReg;
883 e.Cex.CfiReg.reg = reg;
884 return (Int)VG_(addToXA)( dst, &e );
885 }
ML_(CfiExpr_DwReg)886 Int ML_(CfiExpr_DwReg)( XArray* dst, Int reg )
887 {
888 CfiExpr e;
889 VG_(memset)( &e, 0, sizeof(e) );
890 e.tag = Cex_DwReg;
891 e.Cex.DwReg.reg = reg;
892 return (Int)VG_(addToXA)( dst, &e );
893 }
894
ppCfiUnop(CfiUnop op)895 static void ppCfiUnop ( CfiUnop op )
896 {
897 switch (op) {
898 case Cunop_Abs: VG_(printf)("abs"); break;
899 case Cunop_Neg: VG_(printf)("-"); break;
900 case Cunop_Not: VG_(printf)("~"); break;
901 default: vg_assert(0);
902 }
903 }
904
ppCfiBinop(CfiBinop op)905 static void ppCfiBinop ( CfiBinop op )
906 {
907 switch (op) {
908 case Cbinop_Add: VG_(printf)("+"); break;
909 case Cbinop_Sub: VG_(printf)("-"); break;
910 case Cbinop_And: VG_(printf)("&"); break;
911 case Cbinop_Mul: VG_(printf)("*"); break;
912 case Cbinop_Shl: VG_(printf)("<<"); break;
913 case Cbinop_Shr: VG_(printf)(">>"); break;
914 case Cbinop_Eq: VG_(printf)("=="); break;
915 case Cbinop_Ge: VG_(printf)(">="); break;
916 case Cbinop_Gt: VG_(printf)(">"); break;
917 case Cbinop_Le: VG_(printf)("<="); break;
918 case Cbinop_Lt: VG_(printf)("<"); break;
919 case Cbinop_Ne: VG_(printf)("!="); break;
920 default: vg_assert(0);
921 }
922 }
923
ppCfiReg(CfiReg reg)924 static void ppCfiReg ( CfiReg reg )
925 {
926 switch (reg) {
927 case Creg_INVALID: VG_(printf)("Creg_INVALID"); break;
928 case Creg_IA_SP: VG_(printf)("xSP"); break;
929 case Creg_IA_BP: VG_(printf)("xBP"); break;
930 case Creg_IA_IP: VG_(printf)("xIP"); break;
931 case Creg_ARM_R13: VG_(printf)("R13"); break;
932 case Creg_ARM_R12: VG_(printf)("R12"); break;
933 case Creg_ARM_R15: VG_(printf)("R15"); break;
934 case Creg_ARM_R14: VG_(printf)("R14"); break;
935 case Creg_ARM_R7: VG_(printf)("R7"); break;
936 case Creg_ARM64_X30: VG_(printf)("X30"); break;
937 case Creg_MIPS_RA: VG_(printf)("RA"); break;
938 case Creg_S390_IA: VG_(printf)("IA"); break;
939 case Creg_S390_SP: VG_(printf)("SP"); break;
940 case Creg_S390_FP: VG_(printf)("FP"); break;
941 case Creg_S390_LR: VG_(printf)("LR"); break;
942 case Creg_TILEGX_IP: VG_(printf)("PC"); break;
943 case Creg_TILEGX_SP: VG_(printf)("SP"); break;
944 case Creg_TILEGX_BP: VG_(printf)("BP"); break;
945 case Creg_TILEGX_LR: VG_(printf)("R55"); break;
946 default: vg_assert(0);
947 }
948 }
949
ML_(ppCfiExpr)950 void ML_(ppCfiExpr)( const XArray* src, Int ix )
951 {
952 /* VG_(indexXA) checks for invalid src/ix values, so we can
953 use it indiscriminately. */
954 const CfiExpr* e = VG_(indexXA)( src, ix );
955 switch (e->tag) {
956 case Cex_Undef:
957 VG_(printf)("Undef");
958 break;
959 case Cex_Deref:
960 VG_(printf)("*(");
961 ML_(ppCfiExpr)(src, e->Cex.Deref.ixAddr);
962 VG_(printf)(")");
963 break;
964 case Cex_Const:
965 VG_(printf)("0x%lx", e->Cex.Const.con);
966 break;
967 case Cex_Unop:
968 ppCfiUnop(e->Cex.Unop.op);
969 VG_(printf)("(");
970 ML_(ppCfiExpr)(src, e->Cex.Unop.ix);
971 VG_(printf)(")");
972 break;
973 case Cex_Binop:
974 VG_(printf)("(");
975 ML_(ppCfiExpr)(src, e->Cex.Binop.ixL);
976 VG_(printf)(")");
977 ppCfiBinop(e->Cex.Binop.op);
978 VG_(printf)("(");
979 ML_(ppCfiExpr)(src, e->Cex.Binop.ixR);
980 VG_(printf)(")");
981 break;
982 case Cex_CfiReg:
983 ppCfiReg(e->Cex.CfiReg.reg);
984 break;
985 case Cex_DwReg:
986 VG_(printf)("dwr%d", e->Cex.DwReg.reg);
987 break;
988 default:
989 VG_(core_panic)("ML_(ppCfiExpr)");
990 /*NOTREACHED*/
991 break;
992 }
993 }
994
995
ML_(cmp_for_DiAddrRange_range)996 Word ML_(cmp_for_DiAddrRange_range) ( const void* keyV,
997 const void* elemV ) {
998 const Addr* key = (const Addr*)keyV;
999 const DiAddrRange* elem = (const DiAddrRange*)elemV;
1000 if (0)
1001 VG_(printf)("cmp_for_DiAddrRange_range: %#lx vs %#lx\n",
1002 *key, elem->aMin);
1003 if ((*key) < elem->aMin) return -1;
1004 if ((*key) > elem->aMax) return 1;
1005 return 0;
1006 }
1007
1008 static
show_scope(OSet * scope,const HChar * who)1009 void show_scope ( OSet* /* of DiAddrRange */ scope, const HChar* who )
1010 {
1011 DiAddrRange* range;
1012 VG_(printf)("Scope \"%s\" = {\n", who);
1013 VG_(OSetGen_ResetIter)( scope );
1014 while (True) {
1015 range = VG_(OSetGen_Next)( scope );
1016 if (!range) break;
1017 VG_(printf)(" %#lx .. %#lx: %ld vars\n", range->aMin, range->aMax,
1018 range->vars ? VG_(sizeXA)(range->vars) : 0);
1019 }
1020 VG_(printf)("}\n");
1021 }
1022
1023 /* Add the variable 'var' to 'scope' for the address range [aMin,aMax]
1024 (inclusive of aMin and aMax). Split existing ranges as required if
1025 aMin or aMax or both don't match existing range boundaries, and add
1026 'var' to all required ranges. Take great care to preserve the
1027 invariant that the ranges in 'scope' cover the entire address range
1028 exactly once, with no overlaps and no holes. */
add_var_to_arange(OSet * scope,Addr aMin,Addr aMax,DiVariable * var)1029 static void add_var_to_arange (
1030 /*MOD*/OSet* /* of DiAddrRange */ scope,
1031 Addr aMin,
1032 Addr aMax,
1033 DiVariable* var
1034 )
1035 {
1036 DiAddrRange *first, *last, *range;
1037 /* These xx variables are for assertion checking only; they don't
1038 contribute anything to the actual work of this function. */
1039 DiAddrRange *xxRangep, *xxFirst, *xxLast;
1040 UWord xxIters;
1041
1042 vg_assert(aMin <= aMax);
1043
1044 if (0) VG_(printf)("add_var_to_arange: %#lx .. %#lx\n", aMin, aMax);
1045 if (0) show_scope( scope, "add_var_to_arange(1)" );
1046
1047 /* See if the lower end of the range (aMin) falls exactly on an
1048 existing range boundary. If not, find the range it does fall
1049 into, and split it (copying the variables in the process), so
1050 that aMin does exactly fall on a range boundary. */
1051 first = VG_(OSetGen_Lookup)( scope, &aMin );
1052 /* It must be present, since the presented OSet must cover
1053 the entire address range. */
1054 vg_assert(first);
1055 vg_assert(first->aMin <= first->aMax);
1056 vg_assert(first->aMin <= aMin && aMin <= first->aMax);
1057
1058 /* Fast track common case, which is that the range specified for
1059 the variable exactly coincides with one already-existing
1060 range. */
1061 if (first->aMin == aMin && first->aMax == aMax) {
1062 vg_assert(first->vars);
1063 VG_(addToXA)( first->vars, var );
1064 return;
1065 }
1066
1067 /* We have to get into splitting ranges, which is complex
1068 and slow. */
1069 if (first->aMin < aMin) {
1070 DiAddrRange* nyu;
1071 /* Ok. We'll have to split 'first'. */
1072 /* truncate the upper end of 'first' */
1073 Addr tmp = first->aMax;
1074 first->aMax = aMin-1;
1075 vg_assert(first->aMin <= first->aMax);
1076 /* create a new range */
1077 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) );
1078 nyu->aMin = aMin;
1079 nyu->aMax = tmp;
1080 vg_assert(nyu->aMin <= nyu->aMax);
1081 /* copy vars into it */
1082 vg_assert(first->vars);
1083 nyu->vars = VG_(cloneXA)( "di.storage.avta.1", first->vars );
1084 VG_(OSetGen_Insert)( scope, nyu );
1085 first = nyu;
1086 }
1087
1088 vg_assert(first->aMin == aMin);
1089
1090 /* Now do exactly the same for the upper end (aMax): if it doesn't
1091 fall on a boundary, cause it to do so by splitting the range it
1092 does currently fall into. */
1093 last = VG_(OSetGen_Lookup)( scope, &aMax );
1094 vg_assert(last->aMin <= last->aMax);
1095 vg_assert(last->aMin <= aMax && aMax <= last->aMax);
1096
1097 if (aMax < last->aMax) {
1098 DiAddrRange* nyu;
1099 /* We have to split 'last'. */
1100 /* truncate the lower end of 'last' */
1101 Addr tmp = last->aMin;
1102 last->aMin = aMax+1;
1103 vg_assert(last->aMin <= last->aMax);
1104 /* create a new range */
1105 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) );
1106 nyu->aMin = tmp;
1107 nyu->aMax = aMax;
1108 vg_assert(nyu->aMin <= nyu->aMax);
1109 /* copy vars into it */
1110 vg_assert(last->vars);
1111 nyu->vars = VG_(cloneXA)( "di.storage.avta.2", last->vars );
1112 VG_(OSetGen_Insert)( scope, nyu );
1113 last = nyu;
1114 }
1115
1116 vg_assert(aMax == last->aMax);
1117
1118 xxFirst = (DiAddrRange*)VG_(OSetGen_Lookup)(scope, &aMin);
1119 xxLast = (DiAddrRange*)VG_(OSetGen_Lookup)(scope, &aMax);
1120 vg_assert(xxFirst);
1121 vg_assert(xxLast);
1122 vg_assert(xxFirst->aMin == aMin);
1123 vg_assert(xxLast->aMax == aMax);
1124 if (xxFirst != xxLast)
1125 vg_assert(xxFirst->aMax < xxLast->aMin);
1126
1127 /* Great. Now we merely need to iterate over the segments from
1128 'first' to 'last' inclusive, and add 'var' to the variable set
1129 of each of them. */
1130 if (0) {
1131 static UWord ctr = 0;
1132 ctr++;
1133 VG_(printf)("ctr = %lu\n", ctr);
1134 if (ctr >= 33263) show_scope( scope, "add_var_to_arange(2)" );
1135 }
1136
1137 xxIters = 0;
1138 range = xxRangep = NULL;
1139 VG_(OSetGen_ResetIterAt)( scope, &aMin );
1140 while (True) {
1141 xxRangep = range;
1142 range = VG_(OSetGen_Next)( scope );
1143 if (!range) break;
1144 if (range->aMin > aMax) break;
1145 xxIters++;
1146 if (0) VG_(printf)("have range %#lx %#lx\n",
1147 range->aMin, range->aMax);
1148
1149 /* Sanity checks */
1150 if (!xxRangep) {
1151 /* This is the first in the range */
1152 vg_assert(range->aMin == aMin);
1153 } else {
1154 vg_assert(xxRangep->aMax + 1 == range->aMin);
1155 }
1156
1157 vg_assert(range->vars);
1158 VG_(addToXA)( range->vars, var );
1159 }
1160 /* Done. We should have seen at least one range. */
1161 vg_assert(xxIters >= 1);
1162 if (xxIters == 1) vg_assert(xxFirst == xxLast);
1163 if (xxFirst == xxLast) vg_assert(xxIters == 1);
1164 vg_assert(xxRangep);
1165 vg_assert(xxRangep->aMax == aMax);
1166 vg_assert(xxRangep == xxLast);
1167 }
1168
1169
1170 /* Top-level place to call to add a variable description (as extracted
1171 from a DWARF3 .debug_info section. */
ML_(addVar)1172 void ML_(addVar)( struct _DebugInfo* di,
1173 Int level,
1174 Addr aMin,
1175 Addr aMax,
1176 const HChar* name, /* in di's .strpool */
1177 UWord typeR, /* a cuOff */
1178 const GExpr* gexpr,
1179 const GExpr* fbGX,
1180 UInt fndn_ix, /* where decl'd - may be zero.
1181 index in in di's .fndnpool */
1182 Int lineNo, /* where decl'd - may be zero */
1183 Bool show )
1184 {
1185 OSet* /* of DiAddrRange */ scope;
1186 DiVariable var;
1187 Bool all;
1188 TyEnt* ent;
1189 MaybeULong mul;
1190 const HChar* badness;
1191
1192 vg_assert(di && di->admin_tyents);
1193
1194 if (0) {
1195 VG_(printf)(" ML_(addVar): level %d %#lx-%#lx %s :: ",
1196 level, aMin, aMax, name );
1197 ML_(pp_TyEnt_C_ishly)( di->admin_tyents, typeR );
1198 VG_(printf)("\n Var=");
1199 ML_(pp_GX)(gexpr);
1200 VG_(printf)("\n");
1201 if (fbGX) {
1202 VG_(printf)(" FrB=");
1203 ML_(pp_GX)( fbGX );
1204 VG_(printf)("\n");
1205 } else {
1206 VG_(printf)(" FrB=none\n");
1207 }
1208 VG_(printf)("\n");
1209 }
1210
1211 vg_assert(level >= 0);
1212 vg_assert(aMin <= aMax);
1213 vg_assert(name);
1214 vg_assert(gexpr);
1215
1216 ent = ML_(TyEnts__index_by_cuOff)( di->admin_tyents, NULL, typeR);
1217 vg_assert(ent);
1218 vg_assert(ML_(TyEnt__is_type)(ent));
1219
1220 /* "Comment_Regarding_Text_Range_Checks" (is referred to elsewhere)
1221 ----------------------------------------------------------------
1222 Ignore any variables whose aMin .. aMax (that is, range of text
1223 addresses for which they actually exist) falls outside the text
1224 segment. Is this indicative of a bug in the reader? Maybe.
1225 (LATER): instead of restricting strictly to the .text segment,
1226 be a bit more relaxed, and accept any variable whose text range
1227 falls inside the r-x mapped area. This is useful because .text
1228 is not always the only instruction-carrying segment: others are:
1229 .init .plt __libc_freeres_fn and .fini. This implicitly assumes
1230 that those extra sections have the same bias as .text, but that
1231 seems a reasonable assumption to me. */
1232 /* This is assured us by top level steering logic in debuginfo.c,
1233 and it is re-checked at the start of
1234 ML_(read_elf_debug_info). */
1235 vg_assert(di->fsm.have_rx_map && di->fsm.have_rw_map);
1236 if (level > 0 && ML_(find_rx_mapping)(di, aMin, aMax) == NULL) {
1237 if (VG_(clo_verbosity) >= 0) {
1238 VG_(message)(Vg_DebugMsg,
1239 "warning: addVar: in range %#lx .. %#lx outside "
1240 "all rx mapped areas (%s)\n",
1241 aMin, aMax, name
1242 );
1243 }
1244 return;
1245 }
1246
1247 /* If the type's size is zero (which can mean unknown size), ignore
1248 it. We will never be able to actually relate a data address to
1249 a data object with zero size, so there's no point in storing
1250 info on it. On 32-bit platforms, also reject types whose size
1251 is 2^32 bytes or large. (It's amazing what junk shows up ..) */
1252 mul = ML_(sizeOfType)(di->admin_tyents, typeR);
1253
1254 badness = NULL;
1255 if (mul.b != True)
1256 badness = "unknown size";
1257 else if (mul.ul == 0)
1258 badness = "zero size ";
1259 else if (sizeof(void*) == 4 && mul.ul >= (1ULL<<32))
1260 badness = "implausibly large";
1261
1262 if (badness) {
1263 static Int complaints = 10;
1264 if (VG_(clo_verbosity) >= 2 && complaints > 0) {
1265 VG_(message)(Vg_DebugMsg, "warning: addVar: %s (%s)\n",
1266 badness, name );
1267 complaints--;
1268 }
1269 return;
1270 }
1271
1272 if (!di->varinfo) {
1273 di->varinfo = VG_(newXA)( ML_(dinfo_zalloc),
1274 "di.storage.addVar.1",
1275 ML_(dinfo_free),
1276 sizeof(OSet*) );
1277 }
1278
1279 vg_assert(level < 256); /* arbitrary; stay sane */
1280 /* Expand the top level array enough to map this level */
1281 while ( VG_(sizeXA)(di->varinfo) <= level ) {
1282 DiAddrRange* nyu;
1283 scope = VG_(OSetGen_Create)( offsetof(DiAddrRange,aMin),
1284 ML_(cmp_for_DiAddrRange_range),
1285 ML_(dinfo_zalloc), "di.storage.addVar.2",
1286 ML_(dinfo_free) );
1287 if (0) VG_(printf)("create: scope = %p, adding at %ld\n",
1288 scope, VG_(sizeXA)(di->varinfo));
1289 VG_(addToXA)( di->varinfo, &scope );
1290 /* Add a single range covering the entire address space. At
1291 level 0 we require this doesn't get split. At levels above 0
1292 we require that any additions to it cause it to get split.
1293 All of these invariants get checked both add_var_to_arange
1294 and after reading is complete, in canonicaliseVarInfo. */
1295 nyu = VG_(OSetGen_AllocNode)( scope, sizeof(DiAddrRange) );
1296 nyu->aMin = (Addr)0;
1297 nyu->aMax = ~(Addr)0;
1298 nyu->vars = VG_(newXA)( ML_(dinfo_zalloc), "di.storage.addVar.3",
1299 ML_(dinfo_free),
1300 sizeof(DiVariable) );
1301 VG_(OSetGen_Insert)( scope, nyu );
1302 }
1303
1304 vg_assert( VG_(sizeXA)(di->varinfo) > level );
1305 scope = *(OSet**)VG_(indexXA)( di->varinfo, level );
1306 vg_assert(scope);
1307
1308 var.name = name;
1309 var.typeR = typeR;
1310 var.gexpr = gexpr;
1311 var.fbGX = fbGX;
1312 var.fndn_ix = fndn_ix;
1313 var.lineNo = lineNo;
1314
1315 all = aMin == (Addr)0 && aMax == ~(Addr)0;
1316 vg_assert(level == 0 ? all : !all);
1317
1318 add_var_to_arange( /*MOD*/scope, aMin, aMax, &var );
1319 }
1320
1321
1322 /* This really just checks the constructed data structure, as there is
1323 no canonicalisation to do. */
canonicaliseVarInfo(struct _DebugInfo * di)1324 static void canonicaliseVarInfo ( struct _DebugInfo* di )
1325 {
1326 Word i, nInThisScope;
1327
1328 if (!di->varinfo)
1329 return;
1330
1331 for (i = 0; i < VG_(sizeXA)(di->varinfo); i++) {
1332
1333 DiAddrRange *range, *rangep;
1334 OSet* scope = *(OSet**)VG_(indexXA)(di->varinfo, i);
1335 if (!scope) continue;
1336
1337 /* Deal with the global-scope case. */
1338 if (i == 0) {
1339 Addr zero = 0;
1340 vg_assert(VG_(OSetGen_Size)( scope ) == 1);
1341 range = VG_(OSetGen_Lookup)( scope, &zero );
1342 vg_assert(range);
1343 vg_assert(range->aMin == (Addr)0);
1344 vg_assert(range->aMax == ~(Addr)0);
1345 continue;
1346 }
1347
1348 /* All the rest of this is for the local-scope case. */
1349 /* iterate over all entries in 'scope' */
1350 nInThisScope = 0;
1351 rangep = NULL;
1352 VG_(OSetGen_ResetIter)(scope);
1353 while (True) {
1354 range = VG_(OSetGen_Next)(scope);
1355 if (!range) {
1356 /* We just saw the last one. There must have been at
1357 least one entry in the range. */
1358 vg_assert(rangep);
1359 vg_assert(rangep->aMax == ~(Addr)0);
1360 break;
1361 }
1362
1363 vg_assert(range->aMin <= range->aMax);
1364 vg_assert(range->vars);
1365
1366 if (!rangep) {
1367 /* This is the first entry in the range. */
1368 vg_assert(range->aMin == 0);
1369 } else {
1370 vg_assert(rangep->aMax + 1 == range->aMin);
1371 }
1372
1373 rangep = range;
1374 nInThisScope++;
1375 } /* iterating over ranges in a given scope */
1376
1377 /* If there's only one entry in this (local) scope, it must
1378 cover the entire address space (obviously), but it must not
1379 contain any vars. */
1380
1381 vg_assert(nInThisScope > 0);
1382 if (nInThisScope == 1) {
1383 Addr zero = 0;
1384 vg_assert(VG_(OSetGen_Size)( scope ) == 1);
1385 range = VG_(OSetGen_Lookup)( scope, &zero );
1386 vg_assert(range);
1387 vg_assert(range->aMin == (Addr)0);
1388 vg_assert(range->aMax == ~(Addr)0);
1389 vg_assert(range->vars);
1390 vg_assert(VG_(sizeXA)(range->vars) == 0);
1391 }
1392
1393 } /* iterate over scopes */
1394 }
1395
1396
1397 /*------------------------------------------------------------*/
1398 /*--- Canonicalisers ---*/
1399 /*------------------------------------------------------------*/
1400
1401 /* Sort the symtab by starting address, and emit warnings if any
1402 symbols have overlapping address ranges. We use that old chestnut,
1403 shellsort. Mash the table around so as to establish the property
1404 that addresses are in order and the ranges to not overlap. This
1405 facilitates using binary search to map addresses to symbols when we
1406 come to query the table.
1407 */
compare_DiSym(const void * va,const void * vb)1408 static Int compare_DiSym ( const void* va, const void* vb )
1409 {
1410 const DiSym* a = va;
1411 const DiSym* b = vb;
1412 if (a->avmas.main < b->avmas.main) return -1;
1413 if (a->avmas.main > b->avmas.main) return 1;
1414 return 0;
1415 }
1416
1417
1418 /* An address is associated with more than one name. Which do we
1419 prefer as the "display" name (that we show the user in stack
1420 traces)? In order:
1421
1422 - Prefer "PMPI_<foo>" over "MPI_<foo>".
1423
1424 - Else, prefer a non-empty name over an empty one.
1425
1426 - Else, prefer a non-whitespace name over an all-whitespace name.
1427
1428 - Else, prefer the shorter symbol name. If the symbol contains a
1429 version symbol ('@' on Linux, other platforms may differ), which means it
1430 is versioned, then the length up to the version symbol is used for length
1431 comparison purposes (so "foo@GLIBC_2.4.2" is considered shorter than
1432 "foobar").
1433
1434 - Else, if two symbols have the same length, prefer a versioned symbol over
1435 a non-versioned symbol.
1436
1437 - Else, use alphabetical ordering.
1438
1439 - Otherwise, they must be the same; use the name with the lower address.
1440
1441 Very occasionally this goes wrong (eg. 'memcmp' and 'bcmp' are
1442 aliases in glibc, we choose the 'bcmp' symbol because it's shorter,
1443 so we can misdescribe memcmp() as bcmp()). This is hard to avoid.
1444 It's mentioned in the FAQ file.
1445
1446 Returned value is True if a_name is preferred, False if b_name is
1447 preferred.
1448 */
1449 static
preferName(const DebugInfo * di,const HChar * a_name,const HChar * b_name,Addr sym_avma)1450 Bool preferName ( const DebugInfo* di,
1451 const HChar* a_name, const HChar* b_name,
1452 Addr sym_avma/*exposition only*/ )
1453 {
1454 Word cmp;
1455 Word vlena, vlenb; /* length without version */
1456 const HChar *vpa, *vpb;
1457
1458 Bool preferA = False;
1459 Bool preferB = False;
1460
1461 vg_assert(a_name);
1462 vg_assert(b_name);
1463 // vg_assert(a_name != b_name);
1464 // ???? now the pointers can be equal but is that
1465 // ???? not the indication of a latent bug ????
1466
1467 vlena = VG_(strlen)(a_name);
1468 vlenb = VG_(strlen)(b_name);
1469
1470 # if defined(VGO_linux) || defined(VGO_solaris)
1471 # define VERSION_CHAR '@'
1472 # elif defined(VGO_darwin)
1473 # define VERSION_CHAR '$'
1474 # else
1475 # error Unknown OS
1476 # endif
1477
1478 vpa = VG_(strchr)(a_name, VERSION_CHAR);
1479 vpb = VG_(strchr)(b_name, VERSION_CHAR);
1480
1481 # undef VERSION_CHAR
1482
1483 if (vpa)
1484 vlena = vpa - a_name;
1485 if (vpb)
1486 vlenb = vpb - b_name;
1487
1488 /* MPI hack: prefer PMPI_Foo over MPI_Foo */
1489 if (0==VG_(strncmp)(a_name, "MPI_", 4)
1490 && 0==VG_(strncmp)(b_name, "PMPI_", 5)
1491 && 0==VG_(strcmp)(a_name, 1+b_name)) {
1492 preferB = True; goto out;
1493 }
1494 if (0==VG_(strncmp)(b_name, "MPI_", 4)
1495 && 0==VG_(strncmp)(a_name, "PMPI_", 5)
1496 && 0==VG_(strcmp)(b_name, 1+a_name)) {
1497 preferA = True; goto out;
1498 }
1499
1500 /* Prefer non-empty name. */
1501 if (vlena && !vlenb) {
1502 preferA = True; goto out;
1503 }
1504 if (vlenb && !vlena) {
1505 preferB = True; goto out;
1506 }
1507
1508 /* Prefer non-whitespace name. */
1509 {
1510 Bool blankA = True;
1511 Bool blankB = True;
1512 const HChar *s;
1513 s = a_name;
1514 while (*s) {
1515 if (!VG_(isspace)(*s++)) {
1516 blankA = False;
1517 break;
1518 }
1519 }
1520 s = b_name;
1521 while (*s) {
1522 if (!VG_(isspace)(*s++)) {
1523 blankB = False;
1524 break;
1525 }
1526 }
1527
1528 if (!blankA && blankB) {
1529 preferA = True; goto out;
1530 }
1531 if (!blankB && blankA) {
1532 preferB = True; goto out;
1533 }
1534 }
1535
1536 /* Select the shortest unversioned name */
1537 if (vlena < vlenb) {
1538 preferA = True; goto out;
1539 }
1540 if (vlenb < vlena) {
1541 preferB = True; goto out;
1542 }
1543
1544 /* Equal lengths; select the versioned name */
1545 if (vpa && !vpb) {
1546 preferA = True; goto out;
1547 }
1548 if (vpb && !vpa) {
1549 preferB = True; goto out;
1550 }
1551
1552 /* Either both versioned or neither is versioned; select them
1553 alphabetically */
1554 cmp = VG_(strcmp)(a_name, b_name);
1555 if (cmp < 0) {
1556 preferA = True; goto out;
1557 }
1558 if (cmp > 0) {
1559 preferB = True; goto out;
1560 }
1561
1562 /* If we get here, they are the same name. */
1563
1564 /* In this case we could choose either (arbitrarily), but might as
1565 well choose the one with the lowest DiSym* address, so as to try
1566 and make the comparison mechanism more stable (a la sorting
1567 parlance). Also, skip the diagnostic printing in this case. */
1568 return a_name <= b_name ? True : False;
1569
1570 /*NOTREACHED*/
1571 vg_assert(0);
1572 out:
1573 if (preferA && !preferB) {
1574 TRACE_SYMTAB("sym at %#lx: prefer '%s' to '%s'\n",
1575 sym_avma, a_name, b_name );
1576 return True;
1577 }
1578 if (preferB && !preferA) {
1579 TRACE_SYMTAB("sym at %#lx: prefer '%s' to '%s'\n",
1580 sym_avma, b_name, a_name );
1581 return False;
1582 }
1583 /*NOTREACHED*/
1584 vg_assert(0);
1585 }
1586
1587
1588 /* Add the names in FROM to the names in TO. */
1589 static
add_DiSym_names_to_from(const DebugInfo * di,DiSym * to,const DiSym * from)1590 void add_DiSym_names_to_from ( const DebugInfo* di, DiSym* to,
1591 const DiSym* from )
1592 {
1593 vg_assert(to->pri_name);
1594 vg_assert(from->pri_name);
1595 /* Figure out how many names there will be in the new combined
1596 secondary vector. */
1597 const HChar** to_sec = to->sec_names;
1598 const HChar** from_sec = from->sec_names;
1599 Word n_new_sec = 1;
1600 if (from_sec) {
1601 while (*from_sec) {
1602 n_new_sec++;
1603 from_sec++;
1604 }
1605 }
1606 if (to_sec) {
1607 while (*to_sec) {
1608 n_new_sec++;
1609 to_sec++;
1610 }
1611 }
1612 if (0)
1613 TRACE_SYMTAB("merge: -> %ld\n", n_new_sec);
1614 /* Create the new sec and copy stuff into it, putting the new
1615 entries at the end. */
1616 const HChar** new_sec = ML_(dinfo_zalloc)( "di.storage.aDntf.1",
1617 (n_new_sec+1) * sizeof(HChar*) );
1618 from_sec = from->sec_names;
1619 to_sec = to->sec_names;
1620 Word i = 0;
1621 if (to_sec) {
1622 while (*to_sec) {
1623 new_sec[i++] = *to_sec;
1624 to_sec++;
1625 }
1626 }
1627 new_sec[i++] = from->pri_name;
1628 if (from_sec) {
1629 while (*from_sec) {
1630 new_sec[i++] = *from_sec;
1631 from_sec++;
1632 }
1633 }
1634 vg_assert(i == n_new_sec);
1635 vg_assert(new_sec[i] == NULL);
1636 /* If we're replacing an existing secondary vector, free it. */
1637 if (to->sec_names) {
1638 ML_(dinfo_free)(to->sec_names);
1639 }
1640 to->sec_names = new_sec;
1641 }
1642
1643
canonicaliseSymtab(struct _DebugInfo * di)1644 static void canonicaliseSymtab ( struct _DebugInfo* di )
1645 {
1646 Word i, j, n_truncated;
1647 Addr sta1, sta2, end1, end2, toc1, toc2;
1648 const HChar *pri1, *pri2, **sec1, **sec2;
1649 Bool ist1, ist2, isf1, isf2;
1650
1651 # define SWAP(ty,aa,bb) \
1652 do { ty tt = (aa); (aa) = (bb); (bb) = tt; } while (0)
1653
1654 if (di->symtab_used == 0)
1655 return;
1656
1657 /* Check initial invariants */
1658 for (i = 0; i < di->symtab_used; i++) {
1659 DiSym* sym = &di->symtab[i];
1660 vg_assert(sym->pri_name);
1661 vg_assert(!sym->sec_names);
1662 }
1663
1664 /* Sort by address. */
1665 VG_(ssort)(di->symtab, di->symtab_used,
1666 sizeof(*di->symtab), compare_DiSym);
1667
1668 cleanup_more:
1669
1670 /* BEGIN Detect and "fix" identical address ranges. */
1671 while (1) {
1672 Word r, w, n_merged;
1673 n_merged = 0;
1674 w = 0;
1675 /* A pass merging entries together in the case where they agree
1676 on .isText -- that is, either: both are .isText or both are
1677 not .isText. They are merged into a single entry, but both
1678 sets of names are preserved, so we end up knowing all the
1679 names for that particular address range.*/
1680 for (r = 1; r < di->symtab_used; r++) {
1681 vg_assert(w < r);
1682 if ( di->symtab[w].avmas.main == di->symtab[r].avmas.main
1683 && di->symtab[w].size == di->symtab[r].size
1684 && !!di->symtab[w].isText == !!di->symtab[r].isText) {
1685 /* merge the two into one */
1686 n_merged++;
1687 /* Add r names to w if r has secondary names
1688 or r and w primary names differ. */
1689 if (di->symtab[r].sec_names
1690 || (0 != VG_(strcmp)(di->symtab[r].pri_name,
1691 di->symtab[w].pri_name))) {
1692 add_DiSym_names_to_from(di, &di->symtab[w], &di->symtab[r]);
1693 }
1694 /* mark w as an IFunc if either w or r are */
1695 di->symtab[w].isIFunc = di->symtab[w].isIFunc || di->symtab[r].isIFunc;
1696 /* and use ::pri_names to indicate this slot is no longer in use */
1697 di->symtab[r].pri_name = NULL;
1698 if (di->symtab[r].sec_names) {
1699 ML_(dinfo_free)(di->symtab[r].sec_names);
1700 di->symtab[r].sec_names = NULL;
1701 }
1702 /* Completely zap the entry -- paranoia to make it more
1703 likely we'll notice if we inadvertantly use it
1704 again. */
1705 VG_(memset)(&di->symtab[r], 0, sizeof(DiSym));
1706 } else {
1707 w = r;
1708 }
1709 }
1710
1711 /* A second pass merging entries together where one .isText but
1712 the other isn't. In such cases, just ignore the non-.isText
1713 one (a heuristic hack.) */
1714 for (r = 1; r < di->symtab_used; r++) {
1715 /* Either of the symbols might already have been zapped by
1716 the previous pass, so we first have to check that. */
1717 if (di->symtab[r-1].pri_name == NULL) continue;
1718 if (di->symtab[r-0].pri_name == NULL) continue;
1719 /* ok, they are both still valid. Identical address ranges? */
1720 if (di->symtab[r-1].avmas.main != di->symtab[r-0].avmas.main) continue;
1721 if (di->symtab[r-1].size != di->symtab[r-0].size) continue;
1722 /* Identical address ranges. They must disagree on .isText
1723 since if they agreed, the previous pass would have merged
1724 them. */
1725 if (di->symtab[r-1].isText && di->symtab[r-0].isText) vg_assert(0);
1726 if (!di->symtab[r-1].isText && !di->symtab[r-0].isText) vg_assert(0);
1727 Word to_zap = di->symtab[r-1].isText ? (r-0) : (r-1);
1728 Word to_keep = di->symtab[r-1].isText ? (r-1) : (r-0);
1729 vg_assert(!di->symtab[to_zap].isText);
1730 vg_assert(di->symtab[to_keep].isText);
1731 /* Add to_zap's names to to_keep if to_zap has secondary names
1732 or to_zap's and to_keep's primary names differ. */
1733 if (di->symtab[to_zap].sec_names
1734 || (0 != VG_(strcmp)(di->symtab[to_zap].pri_name,
1735 di->symtab[to_keep].pri_name))) {
1736 add_DiSym_names_to_from(di, &di->symtab[to_keep],
1737 &di->symtab[to_zap]);
1738 }
1739 /* Mark to_zap as not-in use in the same way as in the
1740 previous loop. */
1741 di->symtab[to_zap].pri_name = NULL;
1742 if (di->symtab[to_zap].sec_names) {
1743 ML_(dinfo_free)(di->symtab[to_zap].sec_names);
1744 di->symtab[to_zap].sec_names = NULL;
1745 }
1746 VG_(memset)(&di->symtab[to_zap], 0, sizeof(DiSym));
1747 n_merged++;
1748 }
1749
1750 TRACE_SYMTAB( "canonicaliseSymtab: %ld symbols merged\n", n_merged);
1751 if (n_merged == 0)
1752 break;
1753 /* Now a pass to squeeze out any unused ones */
1754 w = 0;
1755 for (r = 0; r < di->symtab_used; r++) {
1756 vg_assert(w <= r);
1757 if (di->symtab[r].pri_name == NULL)
1758 continue;
1759 if (w < r) {
1760 di->symtab[w] = di->symtab[r];
1761 }
1762 w++;
1763 }
1764 vg_assert(w + n_merged == di->symtab_used);
1765 di->symtab_used = w;
1766 } /* while (1) */
1767 /* END Detect and "fix" identical address ranges. */
1768
1769 /* BEGIN Detect and "fix" overlapping address ranges. */
1770 n_truncated = 0;
1771
1772 for (i = 0; i < ((Word)di->symtab_used) -1; i++) {
1773
1774 vg_assert(di->symtab[i].avmas.main <= di->symtab[i+1].avmas.main);
1775
1776 /* Check for common (no overlap) case. */
1777 if (di->symtab[i].avmas.main + di->symtab[i].size
1778 <= di->symtab[i+1].avmas.main)
1779 continue;
1780
1781 /* There's an overlap. Truncate one or the other. */
1782 if (di->trace_symtab) {
1783 VG_(printf)("overlapping address ranges in symbol table\n\t");
1784 ML_(ppSym)( i, &di->symtab[i] );
1785 VG_(printf)("\t");
1786 ML_(ppSym)( i+1, &di->symtab[i+1] );
1787 VG_(printf)("\n");
1788 }
1789
1790 /* Truncate one or the other. */
1791 sta1 = di->symtab[i].avmas.main;
1792 end1 = sta1 + di->symtab[i].size - 1;
1793 toc1 = GET_TOCPTR_AVMA(di->symtab[i].avmas);
1794 // aren't we missing local_ep here ????
1795 pri1 = di->symtab[i].pri_name;
1796 sec1 = di->symtab[i].sec_names;
1797 ist1 = di->symtab[i].isText;
1798 isf1 = di->symtab[i].isIFunc;
1799
1800 sta2 = di->symtab[i+1].avmas.main;
1801 end2 = sta2 + di->symtab[i+1].size - 1;
1802 toc2 = GET_TOCPTR_AVMA(di->symtab[i+1].avmas);
1803 // aren't we missing local_ep here ????
1804 pri2 = di->symtab[i+1].pri_name;
1805 sec2 = di->symtab[i+1].sec_names;
1806 ist2 = di->symtab[i+1].isText;
1807 isf2 = di->symtab[i+1].isIFunc;
1808
1809 if (sta1 < sta2) {
1810 end1 = sta2 - 1;
1811 } else {
1812 vg_assert(sta1 == sta2);
1813 if (end1 > end2) {
1814 sta1 = end2 + 1;
1815 SWAP(Addr,sta1,sta2); SWAP(Addr,end1,end2); SWAP(Addr,toc1,toc2);
1816 SWAP(const HChar*,pri1,pri2); SWAP(const HChar**,sec1,sec2);
1817 SWAP(Bool,ist1,ist2); SWAP(Bool,isf1,isf2);
1818 } else
1819 if (end1 < end2) {
1820 sta2 = end1 + 1;
1821 } else {
1822 /* end1 == end2. Identical addr ranges. We'll eventually wind
1823 up back at cleanup_more, which will take care of it. */
1824 }
1825 }
1826 di->symtab[i].avmas.main = sta1;
1827 di->symtab[i].size = end1 - sta1 + 1;
1828 SET_TOCPTR_AVMA(di->symtab[i].avmas, toc1);
1829 // missing local_ep ???
1830 di->symtab[i].pri_name = pri1;
1831 di->symtab[i].sec_names = sec1;
1832 di->symtab[i].isText = ist1;
1833 di->symtab[i].isIFunc = isf1;
1834
1835 di->symtab[i+1].avmas.main = sta2;
1836 di->symtab[i+1].size = end2 - sta2 + 1;
1837 SET_TOCPTR_AVMA(di->symtab[i+1].avmas, toc2);
1838 // missing local_ep ???
1839 di->symtab[i+1].pri_name = pri2;
1840 di->symtab[i+1].sec_names = sec2;
1841 di->symtab[i+1].isText = ist2;
1842 di->symtab[i+1].isIFunc = isf2;
1843
1844 vg_assert(sta1 <= sta2);
1845 vg_assert(di->symtab[i].size > 0);
1846 vg_assert(di->symtab[i+1].size > 0);
1847 /* It may be that the i+1 entry now needs to be moved further
1848 along to maintain the address order requirement. */
1849 j = i+1;
1850 while (j < ((Word)di->symtab_used)-1
1851 && di->symtab[j].avmas.main > di->symtab[j+1].avmas.main) {
1852 SWAP(DiSym,di->symtab[j],di->symtab[j+1]);
1853 j++;
1854 }
1855 n_truncated++;
1856 }
1857 /* END Detect and "fix" overlapping address ranges. */
1858
1859 if (n_truncated > 0) goto cleanup_more;
1860
1861 /* Ensure relevant postconditions hold. */
1862 for (i = 0; i < ((Word)di->symtab_used)-1; i++) {
1863 /* No zero-sized symbols. */
1864 vg_assert(di->symtab[i].size > 0);
1865 /* In order. */
1866 vg_assert(di->symtab[i].avmas.main < di->symtab[i+1].avmas.main);
1867 /* No overlaps. */
1868 vg_assert(di->symtab[i].avmas.main + di->symtab[i].size - 1
1869 < di->symtab[i+1].avmas.main);
1870 /* Names are sane(ish) */
1871 vg_assert(di->symtab[i].pri_name);
1872 if (di->symtab[i].sec_names) {
1873 vg_assert(di->symtab[i].sec_names[0]);
1874 }
1875 }
1876
1877 /* For each symbol that has more than one name, use preferName to
1878 select the primary name. This is a complete kludge in that
1879 doing it properly requires making a total ordering on the
1880 candidate names, whilst what we have to work with is an ad-hoc
1881 binary relation (preferName) that certainly doesn't have the
1882 relevant transitivity etc properties that are needed to induce a
1883 legitimate total order. Doesn't matter though if it doesn't
1884 always work right since this is only used to generate names to
1885 show the user. */
1886 for (i = 0; i < ((Word)di->symtab_used)-1; i++) {
1887 DiSym* sym = &di->symtab[i];
1888 const HChar** sec = sym->sec_names;
1889 if (!sec)
1890 continue;
1891 /* Slow but simple. Copy all the cands into a temp array,
1892 choose the primary name, and copy them all back again. */
1893 Word n_tmp = 1;
1894 while (*sec) { n_tmp++; sec++; }
1895 j = 0;
1896 const HChar** tmp = ML_(dinfo_zalloc)( "di.storage.cS.1",
1897 (n_tmp+1) * sizeof(HChar*) );
1898 tmp[j++] = sym->pri_name;
1899 sec = sym->sec_names;
1900 while (*sec) { tmp[j++] = *sec; sec++; }
1901 vg_assert(j == n_tmp);
1902 vg_assert(tmp[n_tmp] == NULL); /* because of zalloc */
1903 /* Choose the most favoured. */
1904 Word best = 0;
1905 for (j = 1; j < n_tmp; j++) {
1906 if (preferName(di, tmp[best], tmp[j], di->symtab[i].avmas.main)) {
1907 /* best is unchanged */
1908 } else {
1909 best = j;
1910 }
1911 }
1912 vg_assert(best >= 0 && best < n_tmp);
1913 /* Copy back */
1914 sym->pri_name = tmp[best];
1915 const HChar** cursor = sym->sec_names;
1916 for (j = 0; j < n_tmp; j++) {
1917 if (j == best)
1918 continue;
1919 *cursor = tmp[j];
1920 cursor++;
1921 }
1922 vg_assert(*cursor == NULL);
1923 ML_(dinfo_free)( tmp );
1924 }
1925
1926 # undef SWAP
1927 }
1928
1929
1930 static DiLoc* sorting_loctab = NULL;
compare_DiLoc_via_ix(const void * va,const void * vb)1931 static Int compare_DiLoc_via_ix ( const void* va, const void* vb )
1932 {
1933 const DiLoc* a = &sorting_loctab[*(const UInt*)va];
1934 const DiLoc* b = &sorting_loctab[*(const UInt*)vb];
1935 if (a->addr < b->addr) return -1;
1936 if (a->addr > b->addr) return 1;
1937 return 0;
1938 }
sort_loctab_and_loctab_fndn_ix(struct _DebugInfo * di)1939 static void sort_loctab_and_loctab_fndn_ix (struct _DebugInfo* di )
1940 {
1941 /* We have to sort the array loctab by addr
1942 together with its "parallel" array loctab_fndn_ix.
1943 We first build sort_ix : an array of indexes in loctab,
1944 that we sort by loctab address. Then we can reorder both
1945 arrays according to sort_ix. */
1946 UInt *sort_ix = ML_(dinfo_zalloc)("di.storage.six",
1947 di->loctab_used*sizeof(UInt));
1948 Word i, j, k;
1949
1950 for (i = 0; i < di->loctab_used; i++) sort_ix[i] = i;
1951 sorting_loctab = di->loctab;
1952 VG_(ssort)(sort_ix, di->loctab_used,
1953 sizeof(*sort_ix), compare_DiLoc_via_ix);
1954 sorting_loctab = NULL;
1955
1956 // Permute in place, using the sort_ix.
1957 for (i=0; i < di->loctab_used; i++) {
1958 DiLoc tmp_diloc;
1959 UInt tmp_fndn_ix;
1960
1961 if (i == sort_ix[i])
1962 continue; // i already at the good place
1963
1964 tmp_diloc = di->loctab[i];
1965 tmp_fndn_ix = ML_(fndn_ix)(di, i);
1966 j = i;
1967 for (;;) {
1968 k = sort_ix[j];
1969 sort_ix[j] = j;
1970 if (k == i)
1971 break;
1972 di->loctab[j] = di->loctab[k];
1973 set_fndn_ix (di, j, ML_(fndn_ix)(di, k));
1974 j = k;
1975 }
1976 di->loctab[j] = tmp_diloc;
1977 set_fndn_ix (di, j, tmp_fndn_ix);
1978 }
1979 ML_(dinfo_free)(sort_ix);
1980 }
1981
1982 /* Sort the location table by starting address. Mash the table around
1983 so as to establish the property that addresses are in order and the
1984 ranges do not overlap. This facilitates using binary search to map
1985 addresses to locations when we come to query the table.
1986 */
canonicaliseLoctab(struct _DebugInfo * di)1987 static void canonicaliseLoctab ( struct _DebugInfo* di )
1988 {
1989 Word i, j;
1990
1991 if (di->loctab_used == 0)
1992 return;
1993
1994 /* sort loctab and loctab_fndn_ix by addr. */
1995 sort_loctab_and_loctab_fndn_ix (di);
1996
1997 /* If two adjacent entries overlap, truncate the first. */
1998 for (i = 0; i < ((Word)di->loctab_used)-1; i++) {
1999 vg_assert(di->loctab[i].size < 10000);
2000 if (di->loctab[i].addr + di->loctab[i].size > di->loctab[i+1].addr) {
2001 /* Do this in signed int32 because the actual .size fields
2002 are only 12 bits. */
2003 Int new_size = di->loctab[i+1].addr - di->loctab[i].addr;
2004 if (new_size < 0) {
2005 di->loctab[i].size = 0;
2006 } else
2007 if (new_size > MAX_LOC_SIZE) {
2008 di->loctab[i].size = MAX_LOC_SIZE;
2009 } else {
2010 di->loctab[i].size = (UShort)new_size;
2011 }
2012 }
2013 }
2014
2015 /* Zap any zero-sized entries resulting from the truncation
2016 process. */
2017 j = 0;
2018 for (i = 0; i < (Word)di->loctab_used; i++) {
2019 if (di->loctab[i].size > 0) {
2020 if (j != i) {
2021 di->loctab[j] = di->loctab[i];
2022 set_fndn_ix(di, j, ML_(fndn_ix)(di, i));
2023 }
2024 j++;
2025 }
2026 }
2027 di->loctab_used = j;
2028
2029 /* Ensure relevant postconditions hold. */
2030 for (i = 0; i < ((Word)di->loctab_used)-1; i++) {
2031 if (0)
2032 VG_(printf)("%ld 0x%p lno:%d sz:%d fndn_ix:%u i+1 0x%p\n",
2033 i,
2034 (void*)di->loctab[i].addr,
2035 di->loctab[i].lineno,
2036 di->loctab[i].size,
2037 ML_(fndn_ix)(di, i),
2038 (void*)di->loctab[i+1].addr);
2039
2040 /* No zero-sized symbols. */
2041 vg_assert(di->loctab[i].size > 0);
2042 /* In order. */
2043 vg_assert(di->loctab[i].addr < di->loctab[i+1].addr);
2044 /* No overlaps. */
2045 vg_assert(di->loctab[i].addr + di->loctab[i].size - 1
2046 < di->loctab[i+1].addr);
2047 }
2048
2049 /* Free up unused space at the end of the table. */
2050 shrinkLocTab(di);
2051 }
2052
2053 /* Sort the inlined call table by starting address. Mash the table around
2054 so as to establish the property that addresses are in order.
2055 This facilitates using binary search to map addresses to locations when
2056 we come to query the table.
2057 Note : ranges can overlap, multiple ranges can start at an address,
2058 multiple ranges can end at an address.
2059 */
compare_DiInlLoc(const void * va,const void * vb)2060 static Int compare_DiInlLoc ( const void* va, const void* vb )
2061 {
2062 const DiInlLoc* a = va;
2063 const DiInlLoc* b = vb;
2064 if (a->addr_lo < b->addr_lo) return -1;
2065 if (a->addr_lo > b->addr_lo) return 1;
2066 return 0;
2067 }
2068
canonicaliseInltab(struct _DebugInfo * di)2069 static void canonicaliseInltab ( struct _DebugInfo* di )
2070 {
2071 Word i;
2072
2073 if (di->inltab_used == 0)
2074 return;
2075
2076 /* Sort by start address. */
2077 VG_(ssort)(di->inltab, di->inltab_used,
2078 sizeof(*di->inltab), compare_DiInlLoc);
2079
2080 /* Ensure relevant postconditions hold. */
2081 for (i = 0; i < ((Word)di->inltab_used)-1; i++) {
2082 /* No zero-sized inlined call. */
2083 vg_assert(di->inltab[i].addr_lo < di->inltab[i].addr_hi);
2084 /* In order, but we can have duplicates and overlapping ranges. */
2085 vg_assert(di->inltab[i].addr_lo <= di->inltab[i+1].addr_lo);
2086 }
2087
2088 /* Free up unused space at the end of the table. */
2089 shrinkInlTab(di);
2090 }
2091
2092
2093 /* Sort the call-frame-info cfsi_rd by starting address. Mash the table
2094 around so as to establish the property that addresses are in order
2095 and the ranges do not overlap. This facilitates using binary
2096 search to map addresses to locations when we come to query the
2097 table.
2098
2099 Also, set cfisi_minaddr and cfisi_maxaddr to be the min and max of
2100 any of the address ranges contained in cfisi[0 .. cfisi_used-1], so
2101 as to facilitate rapidly skipping this SegInfo when looking for an
2102 address which falls outside that range.
2103 */
compare_DiCfSI(const void * va,const void * vb)2104 static Int compare_DiCfSI ( const void* va, const void* vb )
2105 {
2106 const DiCfSI* a = va;
2107 const DiCfSI* b = vb;
2108 if (a->base < b->base) return -1;
2109 if (a->base > b->base) return 1;
2110 return 0;
2111 }
2112
get_cfsi_rd_stats(const DebugInfo * di,UWord * n_mergeables,UWord * n_holes)2113 static void get_cfsi_rd_stats ( const DebugInfo* di,
2114 UWord *n_mergeables, UWord *n_holes )
2115 {
2116 Word i;
2117
2118 *n_mergeables = 0;
2119 *n_holes = 0;
2120
2121 vg_assert (di->cfsi_used == 0 || di->cfsi_rd);
2122 for (i = 1; i < (Word)di->cfsi_used; i++) {
2123 Addr here_min = di->cfsi_rd[i].base;
2124 Addr prev_max = di->cfsi_rd[i-1].base + di->cfsi_rd[i-1].len - 1;
2125 Addr sep = here_min - prev_max;
2126 if (sep > 1)
2127 (*n_holes)++;
2128 if (sep == 1 && di->cfsi_rd[i-1].cfsi_m_ix == di->cfsi_rd[i].cfsi_m_ix)
2129 (*n_mergeables)++;
2130 }
2131 }
2132
ML_(canonicaliseCFI)2133 void ML_(canonicaliseCFI) ( struct _DebugInfo* di )
2134 {
2135 Word i, j;
2136 const Addr minAvma = 0;
2137 const Addr maxAvma = ~minAvma;
2138
2139 /* Note: take care in here. di->cfsi can be NULL, in which
2140 case _used and _size fields will be zero. */
2141 if (di->cfsi_rd == NULL) {
2142 vg_assert(di->cfsi_used == 0);
2143 vg_assert(di->cfsi_size == 0);
2144 vg_assert(di->cfsi_m_pool == NULL);
2145 } else {
2146 vg_assert(di->cfsi_size != 0);
2147 vg_assert(di->cfsi_m_pool != NULL);
2148 }
2149
2150 /* Set cfsi_minavma and cfsi_maxavma to summarise the entire
2151 address range contained in cfsi_rd[0 .. cfsi_used-1]. */
2152 di->cfsi_minavma = maxAvma;
2153 di->cfsi_maxavma = minAvma;
2154 for (i = 0; i < (Word)di->cfsi_used; i++) {
2155 Addr here_min = di->cfsi_rd[i].base;
2156 Addr here_max = di->cfsi_rd[i].base + di->cfsi_rd[i].len - 1;
2157 if (here_min < di->cfsi_minavma)
2158 di->cfsi_minavma = here_min;
2159 if (here_max > di->cfsi_maxavma)
2160 di->cfsi_maxavma = here_max;
2161 }
2162
2163 if (di->trace_cfi)
2164 VG_(printf)("canonicaliseCfiSI: %lu entries, %#lx .. %#lx\n",
2165 di->cfsi_used,
2166 di->cfsi_minavma, di->cfsi_maxavma);
2167
2168 /* Sort the cfsi_rd array by base address. */
2169 VG_(ssort)(di->cfsi_rd, di->cfsi_used, sizeof(*di->cfsi_rd), compare_DiCfSI);
2170
2171 /* If two adjacent entries overlap, truncate the first. */
2172 for (i = 0; i < (Word)di->cfsi_used-1; i++) {
2173 if (di->cfsi_rd[i].base + di->cfsi_rd[i].len > di->cfsi_rd[i+1].base) {
2174 Word new_len = di->cfsi_rd[i+1].base - di->cfsi_rd[i].base;
2175 /* how could it be otherwise? The entries are sorted by the
2176 .base field. */
2177 vg_assert(new_len >= 0);
2178 vg_assert(new_len <= di->cfsi_rd[i].len);
2179 di->cfsi_rd[i].len = new_len;
2180 }
2181 }
2182
2183 /* Zap any zero-sized entries resulting from the truncation
2184 process. */
2185 j = 0;
2186 for (i = 0; i < (Word)di->cfsi_used; i++) {
2187 if (di->cfsi_rd[i].len > 0) {
2188 if (j != i)
2189 di->cfsi_rd[j] = di->cfsi_rd[i];
2190 j++;
2191 }
2192 }
2193 /* VG_(printf)("XXXXXXXXXXXXX %d %d\n", di->cfsi_used, j); */
2194 di->cfsi_used = j;
2195
2196 /* Ensure relevant postconditions hold. */
2197 for (i = 0; i < (Word)di->cfsi_used; i++) {
2198 /* No zero-length ranges. */
2199 vg_assert(di->cfsi_rd[i].len > 0);
2200 /* Makes sense w.r.t. summary address range */
2201 vg_assert(di->cfsi_rd[i].base >= di->cfsi_minavma);
2202 vg_assert(di->cfsi_rd[i].base + di->cfsi_rd[i].len - 1
2203 <= di->cfsi_maxavma);
2204
2205 if (i < di->cfsi_used - 1) {
2206 /*
2207 if (!(di->cfsi[i].base < di->cfsi[i+1].base)) {
2208 VG_(printf)("\nOOO cfsis:\n");
2209 ML_(ppCfiSI)(&di->cfsi[i]);
2210 ML_(ppCfiSI)(&di->cfsi[i+1]);
2211 }
2212 */
2213 /* In order. */
2214 vg_assert(di->cfsi_rd[i].base < di->cfsi_rd[i+1].base);
2215 /* No overlaps. */
2216 vg_assert(di->cfsi_rd[i].base + di->cfsi_rd[i].len - 1
2217 < di->cfsi_rd[i+1].base);
2218 }
2219 }
2220
2221 if (VG_(clo_stats) && VG_(clo_verbosity) >= 3) {
2222 UWord n_mergeables, n_holes;
2223 get_cfsi_rd_stats (di, &n_mergeables, &n_holes);
2224 VG_(dmsg)("CFSI total %lu mergeables %lu holes %lu uniq cfsi_m %u\n",
2225 di->cfsi_used, n_mergeables, n_holes,
2226 di->cfsi_m_pool ? VG_(sizeDedupPA) (di->cfsi_m_pool) : 0);
2227 }
2228 }
2229
ML_(finish_CFSI_arrays)2230 void ML_(finish_CFSI_arrays) ( struct _DebugInfo* di )
2231 {
2232 UWord n_mergeables, n_holes;
2233 UWord new_used;
2234 UWord i;
2235 UWord pos;
2236 UWord f_mergeables, f_holes;
2237 UInt sz_cfsi_m_pool;
2238
2239 get_cfsi_rd_stats (di, &n_mergeables, &n_holes);
2240
2241 if (di->cfsi_used == 0) {
2242 vg_assert (di->cfsi_rd == NULL);
2243 vg_assert (di->cfsi_m_pool == NULL);
2244 vg_assert (n_mergeables == 0);
2245 vg_assert (n_holes == 0);
2246 return;
2247 }
2248
2249 vg_assert (di->cfsi_used > n_mergeables);
2250 new_used = di->cfsi_used - n_mergeables + n_holes;
2251
2252 sz_cfsi_m_pool = VG_(sizeDedupPA)(di->cfsi_m_pool);
2253 vg_assert (sz_cfsi_m_pool > 0);
2254 if (sz_cfsi_m_pool <= 255)
2255 di->sizeof_cfsi_m_ix = 1;
2256 else if (sz_cfsi_m_pool <= 65535)
2257 di->sizeof_cfsi_m_ix = 2;
2258 else
2259 di->sizeof_cfsi_m_ix = 4;
2260
2261 di->cfsi_base = ML_(dinfo_zalloc)( "di.storage.finCfSI.1",
2262 new_used * sizeof(Addr) );
2263 di->cfsi_m_ix = ML_(dinfo_zalloc)( "di.storage.finCfSI.2",
2264 new_used * sizeof(UChar)*di->sizeof_cfsi_m_ix);
2265
2266 pos = 0;
2267 f_mergeables = 0;
2268 f_holes = 0;
2269 for (i = 0; i < (Word)di->cfsi_used; i++) {
2270 if (i > 0) {
2271 Addr here_min = di->cfsi_rd[i].base;
2272 Addr prev_max = di->cfsi_rd[i-1].base + di->cfsi_rd[i-1].len - 1;
2273 SizeT sep = here_min - prev_max;
2274
2275 // Skip a mergeable entry.
2276 if (sep == 1) {
2277 if (di->cfsi_rd[i-1].cfsi_m_ix == di->cfsi_rd[i].cfsi_m_ix) {
2278 f_mergeables++;
2279 continue;
2280 }
2281 }
2282 // Insert a hole if needed.
2283 if (sep > 1) {
2284 f_holes++;
2285 di->cfsi_base[pos] = prev_max + 1;
2286 switch (di->sizeof_cfsi_m_ix) {
2287 case 1: ((UChar*) di->cfsi_m_ix)[pos] = 0; break;
2288 case 2: ((UShort*)di->cfsi_m_ix)[pos] = 0; break;
2289 case 4: ((UInt*) di->cfsi_m_ix)[pos] = 0; break;
2290 default: vg_assert(0);
2291 }
2292 pos++;
2293 }
2294 }
2295
2296 // Insert the cfsi entry i.
2297 di->cfsi_base[pos] = di->cfsi_rd[i].base;
2298 switch (di->sizeof_cfsi_m_ix) {
2299 case 1: ((UChar*) di->cfsi_m_ix)[pos] = di->cfsi_rd[i].cfsi_m_ix; break;
2300 case 2: ((UShort*)di->cfsi_m_ix)[pos] = di->cfsi_rd[i].cfsi_m_ix; break;
2301 case 4: ((UInt*) di->cfsi_m_ix)[pos] = di->cfsi_rd[i].cfsi_m_ix; break;
2302 default: vg_assert(0);
2303 }
2304 pos++;
2305 }
2306
2307 vg_assert (f_mergeables == n_mergeables);
2308 vg_assert (f_holes == n_holes);
2309 vg_assert (pos == new_used);
2310
2311 di->cfsi_used = new_used;
2312 di->cfsi_size = new_used;
2313 ML_(dinfo_free) (di->cfsi_rd);
2314 di->cfsi_rd = NULL;
2315 }
2316
2317
2318 /* Canonicalise the tables held by 'di', in preparation for use. Call
2319 this after finishing adding entries to these tables. */
ML_(canonicaliseTables)2320 void ML_(canonicaliseTables) ( struct _DebugInfo* di )
2321 {
2322 canonicaliseSymtab ( di );
2323 canonicaliseLoctab ( di );
2324 canonicaliseInltab ( di );
2325 ML_(canonicaliseCFI) ( di );
2326 if (di->cfsi_m_pool)
2327 VG_(freezeDedupPA) (di->cfsi_m_pool, ML_(dinfo_shrink_block));
2328 canonicaliseVarInfo ( di );
2329 if (di->strpool)
2330 VG_(freezeDedupPA) (di->strpool, ML_(dinfo_shrink_block));
2331 if (di->fndnpool)
2332 VG_(freezeDedupPA) (di->fndnpool, ML_(dinfo_shrink_block));
2333 }
2334
2335
2336 /*------------------------------------------------------------*/
2337 /*--- Searching the tables ---*/
2338 /*------------------------------------------------------------*/
2339
2340 /* Find a symbol-table index containing the specified pointer, or -1
2341 if not found. Binary search. */
2342
ML_(search_one_symtab)2343 Word ML_(search_one_symtab) ( const DebugInfo* di, Addr ptr,
2344 Bool match_anywhere_in_sym,
2345 Bool findText )
2346 {
2347 Addr a_mid_lo, a_mid_hi;
2348 Word mid, size,
2349 lo = 0,
2350 hi = di->symtab_used-1;
2351 while (True) {
2352 /* current unsearched space is from lo to hi, inclusive. */
2353 if (lo > hi) return -1; /* not found */
2354 mid = (lo + hi) / 2;
2355 a_mid_lo = di->symtab[mid].avmas.main;
2356 size = ( match_anywhere_in_sym
2357 ? di->symtab[mid].size
2358 : 1);
2359 a_mid_hi = ((Addr)di->symtab[mid].avmas.main) + size - 1;
2360
2361 if (ptr < a_mid_lo) { hi = mid-1; continue; }
2362 if (ptr > a_mid_hi) { lo = mid+1; continue; }
2363 vg_assert(ptr >= a_mid_lo && ptr <= a_mid_hi);
2364 /* Found a symbol with the correct address range. But is it
2365 of the right kind (text vs data) ? */
2366 if ( findText && di->symtab[mid].isText ) return mid;
2367 if ( (!findText) && (!di->symtab[mid].isText) ) return mid;
2368 return -1;
2369 }
2370 }
2371
2372
2373 /* Find a location-table index containing the specified pointer, or -1
2374 if not found. Binary search. */
2375
ML_(search_one_loctab)2376 Word ML_(search_one_loctab) ( const DebugInfo* di, Addr ptr )
2377 {
2378 Addr a_mid_lo, a_mid_hi;
2379 Word mid,
2380 lo = 0,
2381 hi = di->loctab_used-1;
2382 while (True) {
2383 /* current unsearched space is from lo to hi, inclusive. */
2384 if (lo > hi) return -1; /* not found */
2385 mid = (lo + hi) / 2;
2386 a_mid_lo = di->loctab[mid].addr;
2387 a_mid_hi = ((Addr)di->loctab[mid].addr) + di->loctab[mid].size - 1;
2388
2389 if (ptr < a_mid_lo) { hi = mid-1; continue; }
2390 if (ptr > a_mid_hi) { lo = mid+1; continue; }
2391 vg_assert(ptr >= a_mid_lo && ptr <= a_mid_hi);
2392 return mid;
2393 }
2394 }
2395
2396
2397 /* Find a CFI-table index containing the specified pointer, or -1
2398 if not found. Binary search. */
2399
ML_(search_one_cfitab)2400 Word ML_(search_one_cfitab) ( const DebugInfo* di, Addr ptr )
2401 {
2402 Word mid,
2403 lo = 0,
2404 hi = di->cfsi_used-1;
2405
2406 while (lo <= hi) {
2407 /* Invariants : hi == cfsi_used-1 || ptr < cfsi_base[hi+1]
2408 lo == 0 || ptr > cfsi_base[lo-1]
2409 (the first part of the invariants is similar to considering
2410 that cfsi_base[-1] is 0 and cfsi_base[cfsi_used] is ~0) */
2411 mid = (lo + hi) / 2;
2412 if (ptr < di->cfsi_base[mid]) { hi = mid-1; continue; }
2413 if (ptr > di->cfsi_base[mid]) { lo = mid+1; continue; }
2414 lo = mid+1; break;
2415 }
2416
2417 #if 0
2418 for (mid = 0; mid <= di->cfsi_used-1; mid++)
2419 if (ptr < di->cfsi_base[mid])
2420 break;
2421 vg_assert (lo - 1 == mid - 1);
2422 #endif
2423 return lo - 1;
2424 }
2425
2426
2427 /* Find a FPO-table index containing the specified pointer, or -1
2428 if not found. Binary search. */
2429
ML_(search_one_fpotab)2430 Word ML_(search_one_fpotab) ( const DebugInfo* di, Addr ptr )
2431 {
2432 Addr const addr = ptr - di->fpo_base_avma;
2433 Addr a_mid_lo, a_mid_hi;
2434 Word mid, size,
2435 lo = 0,
2436 hi = di->fpo_size-1;
2437 while (True) {
2438 /* current unsearched space is from lo to hi, inclusive. */
2439 if (lo > hi) return -1; /* not found */
2440 mid = (lo + hi) / 2;
2441 a_mid_lo = di->fpo[mid].ulOffStart;
2442 size = di->fpo[mid].cbProcSize;
2443 a_mid_hi = a_mid_lo + size - 1;
2444 vg_assert(a_mid_hi >= a_mid_lo);
2445 if (addr < a_mid_lo) { hi = mid-1; continue; }
2446 if (addr > a_mid_hi) { lo = mid+1; continue; }
2447 vg_assert(addr >= a_mid_lo && addr <= a_mid_hi);
2448 return mid;
2449 }
2450 }
2451
2452 /*--------------------------------------------------------------------*/
2453 /*--- end ---*/
2454 /*--------------------------------------------------------------------*/
2455