windows build fixes and some more work on symtab serialization
[dyninst.git] / symtabAPI / src / Symtab-lookup.C
1 /*
2  * Copyright (c) 1996-2007 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
30  */
31
32 /* Lookup functions defined in class Symtab. Separated to reduce file size and classify. */
33
34
35
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <assert.h>
39 #include <string.h>
40 #include <vector>
41 #include <algorithm>
42
43 #include "common/h/Timer.h"
44 #include "common/h/debugOstream.h"
45 #include "common/h/serialize.h"
46 #include "common/h/pathName.h"
47
48 #include "Serialization.h"
49 #include "Symtab.h"
50 #include "Module.h"
51 #include "Collections.h"
52 #include "Function.h"
53 #include "Variable.h"
54
55 #include "symtabAPI/src/Object.h"
56
57 using namespace Dyninst;
58 using namespace Dyninst::SymtabAPI;
59 using namespace std;
60
61 extern SymtabError serr;
62
63 bool regexEquiv( const std::string &str,const std::string &them, bool checkCase );
64 bool pattern_match( const char *p, const char *s, bool checkCase );
65
66 static bool sort_by_sym_ptr(const Symbol *a, const Symbol *b) {
67     return a < b;
68 }
69
70 Symbol *Symtab::findSymbolByIndex(unsigned ndx)
71 {
72         Symbol *s = NULL;
73         if (ndx < everyDefinedSymbol.size())
74                 s = everyDefinedSymbol[ndx];
75         return s;
76 }
77
78 bool Symtab::findSymbolByType(std::vector<Symbol *> &ret, const std::string name,
79                               Symbol::SymbolType sType, NameType nameType,
80                               bool isRegex, bool checkCase)
81 {
82     unsigned old_size = ret.size();
83
84     std::vector<Symbol *> symsMangled;
85     std::vector<Symbol *> symsPretty;
86     std::vector<Symbol *> symsTyped;
87
88     if (!isRegex) {
89         // Easy case
90         if (nameType & mangledName) {
91             symsMangled = symsByMangledName[name];
92         }
93         if (nameType & prettyName) {
94             symsPretty = symsByPrettyName[name];
95         }
96         if (nameType & typedName) {
97             symsTyped = symsByTypedName[name];
98         }
99     }
100     else {
101         // Build the regex list of symbols
102         // We need to iterate over every single symbol. Ugh.
103         for (unsigned i = 0; i < everyDefinedSymbol.size(); i++) {
104             if (nameType & mangledName) {
105                 if (regexEquiv(name, everyDefinedSymbol[i]->getName(), checkCase))
106                     symsMangled.push_back(everyDefinedSymbol[i]);
107             }
108             if (nameType & prettyName) {
109                 if (regexEquiv(name, everyDefinedSymbol[i]->getPrettyName(), checkCase))
110                     symsPretty.push_back(everyDefinedSymbol[i]);
111             }
112             if (nameType & typedName) {
113                 if (regexEquiv(name, everyDefinedSymbol[i]->getTypedName(), checkCase))
114                     symsTyped.push_back(everyDefinedSymbol[i]);
115             }
116         }
117     }
118
119     std::vector<Symbol *> allSyms;
120     
121     for (unsigned i = 0; i < symsMangled.size(); i++) {
122         if ((sType == Symbol::ST_UNKNOWN) ||
123             (symsMangled[i]->getType() == sType))
124             allSyms.push_back(symsMangled[i]);
125     }
126     for (unsigned i = 0; i < symsPretty.size(); i++) {
127         if ((sType == Symbol::ST_UNKNOWN) ||
128             (symsPretty[i]->getType() == sType))
129             allSyms.push_back(symsPretty[i]);
130     }
131     for (unsigned i = 0; i < symsTyped.size(); i++) {
132         if ((sType == Symbol::ST_UNKNOWN) ||
133             (symsTyped[i]->getType() == sType))
134             allSyms.push_back(symsTyped[i]);
135     }
136     
137     std::sort(allSyms.begin(), allSyms.end(), sort_by_sym_ptr);
138     std::vector<Symbol *>::iterator endIter;
139     endIter = std::unique(allSyms.begin(), allSyms.end());
140     ret.insert(ret.end(), allSyms.begin(), endIter);
141
142     if (ret.size() == old_size) {
143         serr = No_Such_Symbol;
144         return false;
145     }
146     else {
147         return true;
148     }
149 }
150
151 bool Symtab::getAllSymbols(std::vector<Symbol *> &ret)
152 {
153     ret = everyDefinedSymbol;
154
155     // add undefined symbols
156     std::vector<Symbol *> temp;
157     std::vector<Symbol *>::iterator it;
158     getAllUndefinedSymbols(temp);
159     for (it = temp.begin(); it != temp.end(); it++)
160         ret.push_back(*it);
161
162     if(ret.size() > 0)
163         return true;
164     serr = No_Such_Symbol;
165     return false;
166 }
167
168 bool Symtab::getAllSymbolsByType(std::vector<Symbol *> &ret, Symbol::SymbolType sType)
169 {
170     if (sType == Symbol::ST_UNKNOWN)
171         return getAllSymbols(ret);
172
173     unsigned old_size = ret.size();
174     // Filter by the given type
175     for (unsigned i = 0; i < everyDefinedSymbol.size(); i++) {
176         if (everyDefinedSymbol[i]->getType() == sType)
177             ret.push_back(everyDefinedSymbol[i]);
178     }
179     // add undefined symbols
180     std::vector<Symbol *> temp;
181     getAllUndefinedSymbols(temp);
182     for (unsigned i = 0; i < temp.size(); i++) {
183         if (temp[i]->getType() == sType)
184             ret.push_back(temp[i]);
185     }
186
187     if (ret.size() > old_size) {
188         return true;
189     }
190     else {
191         serr = No_Such_Symbol;
192         return false;
193     }
194 }
195
196 bool Symtab::getAllDefinedSymbols(std::vector<Symbol *> &ret)
197 {
198     ret = everyDefinedSymbol;
199
200     if(ret.size() > 0)
201         return true;
202     serr = No_Such_Symbol;
203     return false;
204 }
205  
206 bool Symtab::getAllUndefinedSymbols(std::vector<Symbol *> &ret){
207     unsigned size = ret.size();
208     map<string, std::vector<Symbol *> >::iterator it;
209     std::vector<Symbol *>::iterator it2;
210     for (it = undefDynSyms.begin(); it != undefDynSyms.end(); it++)
211         for (it2 = it->second.begin(); it2 != it->second.end(); it2++)
212             ret.push_back(*it2);
213     if(ret.size()>size)
214         return true;
215     serr = No_Such_Symbol;
216     return false;
217 }
218
219 bool Symtab::findFuncByEntryOffset(Function *&ret, const Offset entry)
220 {
221     if (funcsByOffset.find(entry) != funcsByOffset.end()) {
222         ret = funcsByOffset[entry];
223         return true;
224     }
225     serr = No_Such_Function;
226     return false;
227 }
228
229 bool sort_by_func_ptr(const Function *a, const Function *b) {
230     return a < b;
231 }
232
233 bool Symtab::findFunctionsByName(std::vector<Function *> &ret, const std::string name,
234                                  NameType nameType, bool isRegex, bool checkCase) {
235     std::vector<Symbol *> funcSyms;
236     if (!findSymbolByType(funcSyms, name, Symbol::ST_FUNCTION, nameType, isRegex, checkCase))
237         return false;
238
239     std::vector<Function *> unsortedFuncs;
240     for (unsigned i = 0; i < funcSyms.size(); i++) {
241         assert(funcSyms[i]->getFunction());
242         unsortedFuncs.push_back(funcSyms[i]->getFunction());
243     }
244
245     std::sort(unsortedFuncs.begin(), unsortedFuncs.end(), sort_by_func_ptr);
246     std::vector<Function *>::iterator endIter;
247     endIter = std::unique(unsortedFuncs.begin(), unsortedFuncs.end());
248     for (std::vector<Function *>::iterator iter = unsortedFuncs.begin();
249          iter != endIter;
250          iter++)
251         ret.push_back(*iter);
252
253     return true;
254 }
255
256 bool Symtab::getAllFunctions(std::vector<Function *> &ret) {
257     ret = everyFunction;
258     return (ret.size() > 0);
259 }
260
261 bool Symtab::findVariableByOffset(Variable *&ret, const Offset offset) {
262     if (varsByOffset.find(offset) != varsByOffset.end()) {
263         ret = varsByOffset[offset];
264         return true;
265     }
266     serr = No_Such_Variable;
267     return false;
268 }
269
270 static bool sort_by_var_ptr(const Variable * a, const Variable *b) {
271     return a < b;
272 }
273
274 bool Symtab::findVariablesByName(std::vector<Variable *> &ret, const std::string name,
275                                  NameType nameType, bool isRegex, bool checkCase) {
276     std::vector<Symbol *> varSyms;
277     if (!findSymbolByType(varSyms, name, Symbol::ST_OBJECT, nameType, isRegex, checkCase))
278         return false;
279
280     std::vector<Variable *> unsortedVars;
281     for (unsigned i = 0; i < varSyms.size(); i++) {
282         unsortedVars.push_back(varSyms[i]->getVariable());
283     }
284
285     std::sort(unsortedVars.begin(), unsortedVars.end(), sort_by_var_ptr);
286     std::vector<Variable *>::iterator endIter;
287     endIter = std::unique(unsortedVars.begin(), unsortedVars.end());
288     for (std::vector<Variable *>::iterator iter = unsortedVars.begin();
289          iter != endIter;
290          iter++)
291         ret.push_back(*iter);
292
293     return true;
294 }
295
296 bool Symtab::getAllVariables(std::vector<Variable *> &ret) 
297 {
298     ret = everyVariable;
299     return (ret.size() > 0);
300 }
301
302 bool Symtab::getAllModules(std::vector<Module *> &ret)
303 {
304     if (_mods.size() >0 )
305     {
306         ret = _mods;
307         return true;
308     }   
309
310     serr = No_Such_Module;
311     return false;
312 }
313
314 bool Symtab::findModuleByOffset(Module *&ret, Offset off)
315 {   
316    //  this should be a hash, really
317    for (unsigned int i = 0; i < _mods.size(); ++i) 
318    {
319       Module *mod = _mods[i];
320
321       if (off == mod->addr()) 
322       {
323           ret = mod;
324           return true;
325       }
326    } 
327    return false;
328 }
329
330 bool Symtab::findModuleByName(Module *&ret, const std::string name)
331 {
332    dyn_hash_map<std::string, Module *>::iterator loc;
333    loc = modsByFileName.find(name);
334
335    if (loc != modsByFileName.end()) 
336    {
337       ret = loc->second;
338       return true;
339    }
340
341    loc = modsByFullName.find(name);
342
343    if (loc != modsByFullName.end()) 
344    {
345       ret = loc->second;
346       return true;
347    }
348
349    serr = No_Such_Module;
350    ret = NULL;
351    return false;
352 }
353
354 bool Symtab::getAllRegions(std::vector<Region *>&ret)
355 {
356    if (regions_.size() > 0)
357    {
358       ret = regions_;
359       return true;
360    }
361
362    return false;
363 }
364
365 bool Symtab::getCodeRegions(std::vector<Region *>&ret)
366 {
367    if (codeRegions_.size() > 0)
368    {
369       ret = codeRegions_;
370       return true;
371    }
372
373    return false;
374 }
375
376 bool Symtab::getDataRegions(std::vector<Region *>&ret)
377 {
378    if (dataRegions_.size() > 0)
379    {
380       ret = dataRegions_;
381       return true;
382    }
383    return false;
384 }
385
386 extern AnnotationClass<std::vector<Region *> > UserRegionsAnno;
387
388 bool Symtab::getAllNewRegions(std::vector<Region *>&ret)
389 {
390    std::vector<Region *> *retp = NULL;
391
392    if (!getAnnotation(retp, UserRegionsAnno))
393    {
394       fprintf(stderr, "%s[%d]:  failed to get annotations here\n", FILE__, __LINE__);
395       return false;
396    }
397
398    if (!retp)
399    {
400       fprintf(stderr, "%s[%d]:  failed to get annotations here\n", FILE__, __LINE__);
401       return false;
402    }
403
404    ret = *retp;
405
406    return true;
407 }
408
409 bool Symtab::getAllExceptions(std::vector<ExceptionBlock *> &exceptions)
410 {
411    if (excpBlocks.size()>0)
412    {
413       exceptions = excpBlocks;
414       return true;
415    }    
416
417    return false;
418 }
419
420
421 bool Symtab::findException(ExceptionBlock &excp, Offset addr)
422 {
423    for (unsigned i=0; i<excpBlocks.size(); i++)
424    {
425       if (excpBlocks[i]->contains(addr))
426       {
427          excp = *(excpBlocks[i]);
428          return true;
429       } 
430    }
431
432    return false;
433 }
434
435 /**
436  * Returns true if the Address range addr -> addr+size contains
437  * a catch block, with excp pointing to the appropriate block
438  **/
439 bool Symtab::findCatchBlock(ExceptionBlock &excp, Offset addr, unsigned size)
440 {
441     int min = 0;
442     int max = excpBlocks.size();
443     int cur = -1, last_cur;
444
445     if (max == 0)
446         return false;
447
448     //Binary search through vector for address
449     while (true)
450     {
451         last_cur = cur;
452         cur = (min + max) / 2;
453     
454         if (last_cur == cur)
455             return false;
456
457         Offset curAddr = excpBlocks[cur]->catchStart();
458         if ((curAddr <= addr && curAddr+size > addr) ||
459             (size == 0 && curAddr == addr))
460         {
461             //Found it
462             excp = *(excpBlocks[cur]);
463             return true;
464         }
465         if (addr < curAddr)
466             max = cur;
467         else if (addr > curAddr)
468             min = cur;
469     }
470 }
471  
472 bool Symtab::findRegionByEntry(Region *&ret, const Offset offset)
473 {
474     if(regionsByEntryAddr.find(offset) != regionsByEntryAddr.end())
475     {
476         ret = regionsByEntryAddr[offset];
477         return true;
478     }
479     serr = No_Such_Region;
480     return false;
481 }
482
483 /* Similar to binary search in isCode with the exception that here we
484  * search to the end of regions without regards to whether they have
485  * corresponding raw data on disk, and searches all regions.  
486  *
487  * regions_ elements that start at address 0 may overlap, ELF binaries
488  * have 0 address iff they are not loadable, but xcoff places loadable
489  * sections at address 0, including .text and .data
490  */
491 Region *Symtab::findEnclosingRegion(const Offset where)
492 {
493 #if defined (os_aix) // regions overlap so do sequential search
494     // try code regions first, then data, regions_ vector as last resort
495     for (unsigned rIdx=0; rIdx < codeRegions_.size(); rIdx++) {
496         if (where >= codeRegions_[rIdx]->getRegionAddr() &&
497             where < (codeRegions_[rIdx]->getRegionAddr() 
498                      + codeRegions_[rIdx]->getMemSize())) {
499             return codeRegions_[rIdx];
500         }
501     }
502     for (unsigned rIdx=0; rIdx < dataRegions_.size(); rIdx++) {
503         if (where >= dataRegions_[rIdx]->getRegionAddr() &&
504             where < (dataRegions_[rIdx]->getRegionAddr() 
505                      + dataRegions_[rIdx]->getMemSize())) {
506             return dataRegions_[rIdx];
507         }
508     }
509     for (unsigned rIdx=0; rIdx < regions_.size(); rIdx++) {
510         if (where >= regions_[rIdx]->getRegionAddr() &&
511             where < (regions_[rIdx]->getRegionAddr() 
512                      + regions_[rIdx]->getMemSize())) {
513             return regions_[rIdx];
514         }
515     }
516     return NULL;
517 #endif
518     int first = 0; 
519     int last = regions_.size() - 1;
520     while (last >= first) {
521         Region *curreg = regions_[(first + last) / 2];
522         if (where >= curreg->getRegionAddr()
523             && where < (curreg->getRegionAddr()
524                         + curreg->getMemSize())) {
525             return curreg;
526         }
527         else if (where < curreg->getRegionAddr()) {
528             last = ((first + last) / 2) - 1;
529         }
530         else {/* where >= (cursec->getSecAddr()
531                            + cursec->getSecSize()) */
532             first = ((first + last) / 2) + 1;
533         }
534     }
535     return NULL;
536 }
537
538 bool Symtab::findRegion(Region *&ret, const std::string secName)
539 {
540     for(unsigned index=0;index<regions_.size();index++)
541     {
542         if(regions_[index]->getRegionName() == secName)
543         {
544             ret = regions_[index];
545             return true;
546         }
547     }
548     serr = No_Such_Region;
549     return false;
550 }
551
552
553 ///////////////////////// REGEX //////////////////////
554
555 // Use POSIX regular expression pattern matching to check if std::string s matches
556 // the pattern in this std::string
557 bool regexEquiv( const std::string &str,const std::string &them, bool checkCase ) 
558 {
559    const char *str_ = str.c_str();
560    const char *s = them.c_str();
561    // Would this work under NT?  I don't know.
562    //#if !defined(os_windows)
563     return pattern_match(str_, s, checkCase);
564
565 }
566
567 // This function will match string s against pattern p.
568 // Asterisks match 0 or more wild characters, and a question
569 // mark matches exactly one wild character.  In other words,
570 // the asterisk is the equivalent of the regex ".*" and the
571 // question mark is the equivalent of "."
572
573 bool
574 pattern_match( const char *p, const char *s, bool checkCase ) {
575    //const char *p = ptrn;
576    //char *s = str;
577
578     while ( true ) {
579         // If at the end of the pattern, it matches if also at the end of the string
580         if( *p == '\0' )
581             return ( *s == '\0' );
582
583         // Process a '*'
584         if( *p == MULTIPLE_WILDCARD_CHARACTER ) {
585             ++p;
586
587             // If at the end of the pattern, it matches
588             if( *p == '\0' )
589                 return true;
590
591             // Try to match the remaining pattern for each remaining substring of s
592             for(; *s != '\0'; ++s )
593                 if( pattern_match( p, s, checkCase ) )
594                     return true;
595             // Failed
596             return false;
597         }
598
599         // If at the end of the string (and at this point, not of the pattern), it fails
600         if( *s == '\0' )
601             return false;
602
603         // Check if this character matches
604         bool matchChar = false;
605         if( *p == WILDCARD_CHARACTER || *p == *s )
606             matchChar = true;
607         else if( !checkCase ) {
608             if( *p >= 'A' && *p <= 'Z' && *s == ( *p + ( 'a' - 'A' ) ) )
609                 matchChar = true;
610             else if( *p >= 'a' && *p <= 'z' && *s == ( *p - ( 'a' - 'A' ) ) )
611                 matchChar = true;
612         }
613
614         if( matchChar ) {
615             ++p;
616             ++s;
617             continue;
618         }
619
620         // Did not match
621         return false;
622     }
623 }
624
625
626
627 struct SymbolCompareByAddr
628 {
629    bool operator()(Function *a, Function *b)
630     {
631        return (a->getOffset() < b->getOffset());
632    }
633 };
634
635 bool Symtab::getContainingFunction(Offset offset, Function* &func)
636 {
637    if (!isCode(offset)) {
638       return false;
639    }
640    if (everyFunction.size() && !sorted_everyFunction)
641    {
642       std::sort(everyFunction.begin(), everyFunction.end(),
643                 SymbolCompareByAddr());
644       sorted_everyFunction = true;
645    }
646    
647    unsigned low = 0;
648    unsigned high = everyFunction.size();
649    unsigned last_mid = high+1;
650    unsigned mid;
651    for (;;)
652    {
653       mid = (low + high) / 2;
654       if (last_mid == mid)
655          break;
656       last_mid = mid;
657       Offset cur = everyFunction[mid]->getOffset();
658       if (cur > offset) {
659          high = mid;
660          continue;
661       }
662       if (cur < offset) {
663          low = mid;
664          continue;
665       }
666       if (cur == offset) {
667          func = everyFunction[mid];
668          return true;
669       }
670    }
671
672    if ((everyFunction[low]->getOffset() <= offset) &&
673        ((low+1 == everyFunction.size()) || 
674         (everyFunction[low+1]->getOffset() > offset)))
675    {
676          func = everyFunction[low];
677          return true;
678    }
679    return false;
680 }
681
682
683 Module *Symtab::getDefaultModule() {
684     Module *mod = NULL;
685     // TODO: automatically pick the module that contains this address?
686     // For now, DEFAULT_MODULE or (if we have only one) that one.
687     if (_mods.size() == 1)
688         return _mods[0];
689     else {
690         if (!findModuleByName(mod, "DEFAULT_MODULE"))
691             return NULL;
692     }
693     return mod;
694 }