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