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