Update copyright to LGPL on all files
[dyninst.git] / symtabAPI / src / Symtab-lookup.C
1 /*
2  * Copyright (c) 1996-2009 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 #include "annotations.h"
55
56 #include "symtabAPI/src/Object.h"
57
58 using namespace Dyninst;
59 using namespace Dyninst::SymtabAPI;
60 using namespace std;
61
62 extern SymtabError serr;
63
64 bool regexEquiv( const std::string &str,const std::string &them, bool checkCase );
65 bool pattern_match( const char *p, const char *s, bool checkCase );
66
67 static bool sort_by_sym_ptr(const Symbol *a, const Symbol *b) {
68     return a < b;
69 }
70
71 std::vector<Symbol *> *Symtab::findSymbolByOffset(Offset o)
72 {
73         //Symbol *s = NULL;
74         dyn_hash_map<Offset, std::vector<Symbol *> >::iterator iter;
75         iter = symsByOffset.find(o);
76         if (iter == symsByOffset.end()) return NULL;
77         return &(iter->second);
78 }
79
80 bool Symtab::findSymbol(std::vector<Symbol *> &ret, const std::string name,
81                         Symbol::SymbolType sType, NameType nameType,
82                         bool isRegex, bool checkCase)
83 {
84     unsigned old_size = ret.size();
85
86     std::vector<Symbol *> symsMangled;
87     std::vector<Symbol *> symsPretty;
88     std::vector<Symbol *> symsTyped;
89
90     if (!isRegex) {
91         // Easy case
92         if (nameType & mangledName) {
93             symsMangled = symsByMangledName[name];
94         }
95         if (nameType & prettyName) {
96             symsPretty = symsByPrettyName[name];
97         }
98         if (nameType & typedName) {
99             symsTyped = symsByTypedName[name];
100         }
101     }
102     else {
103         // Build the regex list of symbols
104         // We need to iterate over every single symbol. Ugh.
105         for (unsigned i = 0; i < everyDefinedSymbol.size(); i++) {
106             if (nameType & mangledName) {
107                 if (regexEquiv(name, everyDefinedSymbol[i]->getName(), checkCase))
108                     symsMangled.push_back(everyDefinedSymbol[i]);
109             }
110             if (nameType & prettyName) {
111                 if (regexEquiv(name, everyDefinedSymbol[i]->getPrettyName(), checkCase))
112                     symsPretty.push_back(everyDefinedSymbol[i]);
113             }
114             if (nameType & typedName) {
115                 if (regexEquiv(name, everyDefinedSymbol[i]->getTypedName(), checkCase))
116                     symsTyped.push_back(everyDefinedSymbol[i]);
117             }
118         }
119     }
120
121     std::vector<Symbol *> allSyms;
122     
123     for (unsigned i = 0; i < symsMangled.size(); i++) {
124         if ((sType == Symbol::ST_UNKNOWN) ||
125             (symsMangled[i]->getType() == sType))
126             allSyms.push_back(symsMangled[i]);
127     }
128     for (unsigned i = 0; i < symsPretty.size(); i++) {
129         if ((sType == Symbol::ST_UNKNOWN) ||
130             (symsPretty[i]->getType() == sType))
131             allSyms.push_back(symsPretty[i]);
132     }
133     for (unsigned i = 0; i < symsTyped.size(); i++) {
134         if ((sType == Symbol::ST_UNKNOWN) ||
135             (symsTyped[i]->getType() == sType))
136             allSyms.push_back(symsTyped[i]);
137     }
138     
139     std::sort(allSyms.begin(), allSyms.end(), sort_by_sym_ptr);
140     std::vector<Symbol *>::iterator endIter;
141     endIter = std::unique(allSyms.begin(), allSyms.end());
142     ret.insert(ret.end(), allSyms.begin(), endIter);
143
144     if (ret.size() == old_size) {
145         serr = No_Such_Symbol;
146         return false;
147     }
148     else {
149         return true;
150     }
151 }
152
153 bool Symtab::getAllSymbols(std::vector<Symbol *> &ret)
154 {
155     ret = everyDefinedSymbol;
156
157     // add undefined symbols
158     std::vector<Symbol *> temp;
159     std::vector<Symbol *>::iterator it;
160     getAllUndefinedSymbols(temp);
161     for (it = temp.begin(); it != temp.end(); it++)
162         ret.push_back(*it);
163
164     if(ret.size() > 0)
165         return true;
166     serr = No_Such_Symbol;
167     return false;
168 }
169
170 bool Symtab::getAllSymbolsByType(std::vector<Symbol *> &ret, Symbol::SymbolType sType)
171 {
172     if (sType == Symbol::ST_UNKNOWN)
173         return getAllSymbols(ret);
174
175     unsigned old_size = ret.size();
176     // Filter by the given type
177     for (unsigned i = 0; i < everyDefinedSymbol.size(); i++) {
178         if (everyDefinedSymbol[i]->getType() == sType)
179             ret.push_back(everyDefinedSymbol[i]);
180     }
181     // add undefined symbols
182     std::vector<Symbol *> temp;
183     getAllUndefinedSymbols(temp);
184     for (unsigned i = 0; i < temp.size(); i++) {
185         if (temp[i]->getType() == sType)
186             ret.push_back(temp[i]);
187     }
188
189     if (ret.size() > old_size) {
190         return true;
191     }
192     else {
193         serr = No_Such_Symbol;
194         return false;
195     }
196 }
197
198 bool Symtab::getAllDefinedSymbols(std::vector<Symbol *> &ret)
199 {
200     ret = everyDefinedSymbol;
201
202     if(ret.size() > 0)
203         return true;
204     serr = No_Such_Symbol;
205     return false;
206 }
207  
208 bool Symtab::getAllUndefinedSymbols(std::vector<Symbol *> &ret){
209     unsigned size = ret.size();
210     map<string, std::vector<Symbol *> >::iterator it;
211     std::vector<Symbol *>::iterator it2;
212     for (it = undefDynSyms.begin(); it != undefDynSyms.end(); it++)
213         for (it2 = it->second.begin(); it2 != it->second.end(); it2++)
214             ret.push_back(*it2);
215     if(ret.size()>size)
216         return true;
217     serr = No_Such_Symbol;
218     return false;
219 }
220
221 bool Symtab::findFuncByEntryOffset(Function *&ret, const Offset entry)
222 {
223     if (funcsByOffset.find(entry) != funcsByOffset.end()) {
224         ret = funcsByOffset[entry];
225         return true;
226     }
227     serr = No_Such_Function;
228     return false;
229 }
230
231 bool sort_by_func_ptr(const Function *a, const Function *b) {
232     return a < b;
233 }
234
235 bool Symtab::findFunctionsByName(std::vector<Function *> &ret, const std::string name,
236                                  NameType nameType, bool isRegex, bool checkCase) {
237     std::vector<Symbol *> funcSyms;
238     if (!findSymbol(funcSyms, name, Symbol::ST_FUNCTION, nameType, isRegex, checkCase))
239         return false;
240
241     std::vector<Function *> unsortedFuncs;
242     for (unsigned i = 0; i < funcSyms.size(); i++) 
243         {
244                 if (!funcSyms[i]->getFunction())
245                 {
246                         fprintf(stderr, "%s[%d]:  WARNING:  internal inconsistency\n", FILE__, __LINE__);
247                         fprintf(stderr, "%s[%d]:  WARNING:  %s is %s a function\n", FILE__, __LINE__, name.c_str(), funcSyms[i]->isFunction() ? "" : "not");
248                         fprintf(stderr, "%s[%d]:  WARNING:  %s is %s a variable\n", FILE__, __LINE__, name.c_str(), funcSyms[i]->isVariable() ? "" : "not");
249                         continue;
250                 }
251         unsortedFuncs.push_back(funcSyms[i]->getFunction());
252     }
253
254     std::sort(unsortedFuncs.begin(), unsortedFuncs.end(), sort_by_func_ptr);
255     std::vector<Function *>::iterator endIter;
256     endIter = std::unique(unsortedFuncs.begin(), unsortedFuncs.end());
257     for (std::vector<Function *>::iterator iter = unsortedFuncs.begin();
258          iter != endIter;
259          iter++)
260         ret.push_back(*iter);
261
262     return true;
263 }
264
265 bool Symtab::getAllFunctions(std::vector<Function *> &ret) {
266     ret = everyFunction;
267     return (ret.size() > 0);
268 }
269
270 bool Symtab::findVariableByOffset(Variable *&ret, const Offset offset) {
271     if (varsByOffset.find(offset) != varsByOffset.end()) {
272         ret = varsByOffset[offset];
273         return true;
274     }
275     serr = No_Such_Variable;
276     return false;
277 }
278
279 static bool sort_by_var_ptr(const Variable * a, const Variable *b) {
280     return a < b;
281 }
282
283 bool Symtab::findVariablesByName(std::vector<Variable *> &ret, const std::string name,
284                                  NameType nameType, bool isRegex, bool checkCase) {
285     std::vector<Symbol *> varSyms;
286     if (!findSymbol(varSyms, name, Symbol::ST_OBJECT, nameType, isRegex, checkCase))
287         return false;
288
289     std::vector<Variable *> unsortedVars;
290     for (unsigned i = 0; i < varSyms.size(); i++) {
291         unsortedVars.push_back(varSyms[i]->getVariable());
292     }
293
294     std::sort(unsortedVars.begin(), unsortedVars.end(), sort_by_var_ptr);
295     std::vector<Variable *>::iterator endIter;
296     endIter = std::unique(unsortedVars.begin(), unsortedVars.end());
297     for (std::vector<Variable *>::iterator iter = unsortedVars.begin();
298          iter != endIter;
299          iter++)
300         ret.push_back(*iter);
301
302     return true;
303 }
304
305 bool Symtab::getAllVariables(std::vector<Variable *> &ret) 
306 {
307     ret = everyVariable;
308     return (ret.size() > 0);
309 }
310
311 bool Symtab::getAllModules(std::vector<Module *> &ret)
312 {
313     if (_mods.size() >0 )
314     {
315         ret = _mods;
316         return true;
317     }   
318
319     serr = No_Such_Module;
320     return false;
321 }
322
323 bool Symtab::findModuleByOffset(Module *&ret, Offset off)
324 {   
325    //  this should be a hash, really
326    for (unsigned int i = 0; i < _mods.size(); ++i) 
327    {
328       Module *mod = _mods[i];
329
330       if (off == mod->addr()) 
331       {
332           ret = mod;
333           return true;
334       }
335    } 
336    return false;
337 }
338
339 bool Symtab::findModuleByName(Module *&ret, const std::string name)
340 {
341    dyn_hash_map<std::string, Module *>::iterator loc;
342    loc = modsByFileName.find(name);
343
344    if (loc != modsByFileName.end()) 
345    {
346       ret = loc->second;
347       return true;
348    }
349
350    loc = modsByFullName.find(name);
351
352    if (loc != modsByFullName.end()) 
353    {
354       ret = loc->second;
355       return true;
356    }
357
358    serr = No_Such_Module;
359    ret = NULL;
360    return false;
361 }
362
363 bool Symtab::getAllRegions(std::vector<Region *>&ret)
364 {
365    if (regions_.size() > 0)
366    {
367       ret = regions_;
368       return true;
369    }
370
371    return false;
372 }
373
374 bool Symtab::getCodeRegions(std::vector<Region *>&ret)
375 {
376    if (codeRegions_.size() > 0)
377    {
378       ret = codeRegions_;
379       return true;
380    }
381
382    return false;
383 }
384
385 bool Symtab::getDataRegions(std::vector<Region *>&ret)
386 {
387    if (dataRegions_.size() > 0)
388    {
389       ret = dataRegions_;
390       return true;
391    }
392    return false;
393 }
394
395
396 bool Symtab::getAllNewRegions(std::vector<Region *>&ret)
397 {
398    std::vector<Region *> *retp = NULL;
399
400    if (!getAnnotation(retp, UserRegionsAnno))
401    {
402       fprintf(stderr, "%s[%d]:  failed to get annotations here\n", FILE__, __LINE__);
403       return false;
404    }
405
406    if (!retp)
407    {
408       fprintf(stderr, "%s[%d]:  failed to get annotations here\n", FILE__, __LINE__);
409       return false;
410    }
411
412    ret = *retp;
413
414    return true;
415 }
416
417 bool Symtab::getAllExceptions(std::vector<ExceptionBlock *> &exceptions)
418 {
419    if (excpBlocks.size()>0)
420    {
421       exceptions = excpBlocks;
422       return true;
423    }    
424
425    return false;
426 }
427
428
429 bool Symtab::findException(ExceptionBlock &excp, Offset addr)
430 {
431    for (unsigned i=0; i<excpBlocks.size(); i++)
432    {
433       if (excpBlocks[i]->contains(addr))
434       {
435          excp = *(excpBlocks[i]);
436          return true;
437       } 
438    }
439
440    return false;
441 }
442
443 /**
444  * Returns true if the Address range addr -> addr+size contains
445  * a catch block, with excp pointing to the appropriate block
446  **/
447 bool Symtab::findCatchBlock(ExceptionBlock &excp, Offset addr, unsigned size)
448 {
449     int min = 0;
450     int max = excpBlocks.size();
451     int cur = -1, last_cur;
452
453     if (max == 0)
454         return false;
455
456     //Binary search through vector for address
457     while (true)
458     {
459         last_cur = cur;
460         cur = (min + max) / 2;
461     
462         if (last_cur == cur)
463             return false;
464
465         Offset curAddr = excpBlocks[cur]->catchStart();
466         if ((curAddr <= addr && curAddr+size > addr) ||
467             (size == 0 && curAddr == addr))
468         {
469             //Found it
470             excp = *(excpBlocks[cur]);
471             return true;
472         }
473         if (addr < curAddr)
474             max = cur;
475         else if (addr > curAddr)
476             min = cur;
477     }
478 }
479  
480 bool Symtab::findRegionByEntry(Region *&ret, const Offset offset)
481 {
482     if(regionsByEntryAddr.find(offset) != regionsByEntryAddr.end())
483     {
484         ret = regionsByEntryAddr[offset];
485         return true;
486     }
487     serr = No_Such_Region;
488     return false;
489 }
490
491 /* Similar to binary search in isCode with the exception that here we
492  * search to the end of regions without regards to whether they have
493  * corresponding raw data on disk, and searches all regions.  
494  *
495  * regions_ elements that start at address 0 may overlap, ELF binaries
496  * have 0 address iff they are not loadable, but xcoff places loadable
497  * sections at address 0, including .text and .data
498  */
499 Region *Symtab::findEnclosingRegion(const Offset where)
500 {
501 #if defined (os_aix) // regions overlap so do sequential search
502     // try code regions first, then data, regions_ vector as last resort
503     for (unsigned rIdx=0; rIdx < codeRegions_.size(); rIdx++) {
504         if (where >= codeRegions_[rIdx]->getRegionAddr() &&
505             where < (codeRegions_[rIdx]->getRegionAddr() 
506                      + codeRegions_[rIdx]->getMemSize())) {
507             return codeRegions_[rIdx];
508         }
509     }
510     for (unsigned rIdx=0; rIdx < dataRegions_.size(); rIdx++) {
511         if (where >= dataRegions_[rIdx]->getRegionAddr() &&
512             where < (dataRegions_[rIdx]->getRegionAddr() 
513                      + dataRegions_[rIdx]->getMemSize())) {
514             return dataRegions_[rIdx];
515         }
516     }
517     for (unsigned rIdx=0; rIdx < regions_.size(); rIdx++) {
518         if (where >= regions_[rIdx]->getRegionAddr() &&
519             where < (regions_[rIdx]->getRegionAddr() 
520                      + regions_[rIdx]->getMemSize())) {
521             return regions_[rIdx];
522         }
523     }
524     return NULL;
525 #endif
526     int first = 0; 
527     int last = regions_.size() - 1;
528     while (last >= first) {
529         Region *curreg = regions_[(first + last) / 2];
530         if (where >= curreg->getRegionAddr()
531             && where < (curreg->getRegionAddr()
532                         + curreg->getMemSize())) {
533             return curreg;
534         }
535         else if (where < curreg->getRegionAddr()) {
536             last = ((first + last) / 2) - 1;
537         }
538         else {/* where >= (cursec->getSecAddr()
539                            + cursec->getSecSize()) */
540             first = ((first + last) / 2) + 1;
541         }
542     }
543     return NULL;
544 }
545
546 bool Symtab::findRegion(Region *&ret, const std::string secName)
547 {
548     for(unsigned index=0;index<regions_.size();index++)
549     {
550         if(regions_[index]->getRegionName() == secName)
551         {
552             ret = regions_[index];
553             return true;
554         }
555     }
556     serr = No_Such_Region;
557     return false;
558 }
559
560
561 bool Symtab::findRegion(Region *&ret, const Offset addr, const unsigned long size)
562 {
563     for(unsigned index=0;index<regions_.size();index++)
564     {
565         if(regions_[index]->getRegionAddr() == addr && regions_[index]->getRegionSize() == size)
566         {
567             ret = regions_[index];
568             return true;
569         }
570     }
571     serr = No_Such_Region;
572     return false;
573 }
574
575 ///////////////////////// REGEX //////////////////////
576
577 // Use POSIX regular expression pattern matching to check if std::string s matches
578 // the pattern in this std::string
579 bool regexEquiv( const std::string &str,const std::string &them, bool checkCase ) 
580 {
581    const char *str_ = str.c_str();
582    const char *s = them.c_str();
583    // Would this work under NT?  I don't know.
584    //#if !defined(os_windows)
585     return pattern_match(str_, s, checkCase);
586
587 }
588
589 // This function will match string s against pattern p.
590 // Asterisks match 0 or more wild characters, and a question
591 // mark matches exactly one wild character.  In other words,
592 // the asterisk is the equivalent of the regex ".*" and the
593 // question mark is the equivalent of "."
594
595 bool
596 pattern_match( const char *p, const char *s, bool checkCase ) {
597    //const char *p = ptrn;
598    //char *s = str;
599
600     while ( true ) {
601         // If at the end of the pattern, it matches if also at the end of the string
602         if( *p == '\0' )
603             return ( *s == '\0' );
604
605         // Process a '*'
606         if( *p == MULTIPLE_WILDCARD_CHARACTER ) {
607             ++p;
608
609             // If at the end of the pattern, it matches
610             if( *p == '\0' )
611                 return true;
612
613             // Try to match the remaining pattern for each remaining substring of s
614             for(; *s != '\0'; ++s )
615                 if( pattern_match( p, s, checkCase ) )
616                     return true;
617             // Failed
618             return false;
619         }
620
621         // If at the end of the string (and at this point, not of the pattern), it fails
622         if( *s == '\0' )
623             return false;
624
625         // Check if this character matches
626         bool matchChar = false;
627         if( *p == WILDCARD_CHARACTER || *p == *s )
628             matchChar = true;
629         else if( !checkCase ) {
630             if( *p >= 'A' && *p <= 'Z' && *s == ( *p + ( 'a' - 'A' ) ) )
631                 matchChar = true;
632             else if( *p >= 'a' && *p <= 'z' && *s == ( *p - ( 'a' - 'A' ) ) )
633                 matchChar = true;
634         }
635
636         if( matchChar ) {
637             ++p;
638             ++s;
639             continue;
640         }
641
642         // Did not match
643         return false;
644     }
645 }
646
647
648
649 struct SymbolCompareByAddr
650 {
651    bool operator()(Function *a, Function *b)
652     {
653        return (a->getOffset() < b->getOffset());
654    }
655 };
656
657 bool Symtab::getContainingFunction(Offset offset, Function* &func)
658 {
659    if (!isCode(offset)) {
660       return false;
661    }
662    if (everyFunction.size() && !sorted_everyFunction)
663    {
664       std::sort(everyFunction.begin(), everyFunction.end(),
665                 SymbolCompareByAddr());
666       sorted_everyFunction = true;
667    }
668    
669    unsigned low = 0;
670    unsigned high = everyFunction.size();
671    unsigned last_mid = high+1;
672    unsigned mid;
673    if (!high) return false;
674    for (;;)
675    {
676       mid = (low + high) / 2;
677       if (last_mid == mid)
678          break;
679       last_mid = mid;
680       Offset cur = everyFunction[mid]->getOffset();
681       if (cur > offset) {
682          high = mid;
683          continue;
684       }
685       if (cur < offset) {
686          low = mid;
687          continue;
688       }
689       if (cur == offset) {
690          func = everyFunction[mid];
691          return true;
692       }
693    }
694
695    if ((everyFunction[low]->getOffset() <= offset) &&
696        ((low+1 == everyFunction.size()) || 
697         (everyFunction[low+1]->getOffset() > offset)))
698    {
699          func = everyFunction[low];
700          return true;
701    }
702    return false;
703 }
704
705 Module *Symtab::getDefaultModule() {
706     Module *mod = NULL;
707     // TODO: automatically pick the module that contains this address?
708     // For now, DEFAULT_MODULE or (if we have only one) that one.
709     if (_mods.size() == 1)
710         return _mods[0];
711     else {
712         if (!findModuleByName(mod, "DEFAULT_MODULE"))
713             return NULL;
714     }
715     return mod;
716 }
717
718 unsigned Function::getSize() {
719    if (functionSize_)
720       return functionSize_;
721    for (unsigned i=0; i<symbols_.size(); i++) {
722       if (symbols_[i]->getSize()) { 
723          functionSize_ = symbols_[i]->getSize();;
724          return functionSize_;
725       }
726    }
727
728    Symtab *symtab = getFirstSymbol()->getSymtab();
729    if (symtab->everyFunction.size() && !symtab->sorted_everyFunction)
730    {
731       std::sort(symtab->everyFunction.begin(), symtab->everyFunction.end(),
732                 SymbolCompareByAddr());
733       symtab->sorted_everyFunction = true;
734    }
735
736    Offset offset = getOffset();
737    unsigned low = 0;
738    unsigned high = symtab->everyFunction.size();
739    unsigned last_mid = high+1;
740    unsigned mid;
741    for (;;)
742    {
743       mid = (low + high) / 2;
744       if (last_mid == mid)
745          return 0;
746       last_mid = mid;
747       Offset cur = symtab->everyFunction[mid]->getOffset();
748       if (cur > offset) {
749          high = mid;
750          continue;
751       }
752       if (cur < offset) {
753          low = mid;
754          continue;
755       }
756       if (cur == offset) {
757          if (mid + 1 >= symtab->everyFunction.size())
758             return 0;
759          Function *next_func = symtab->everyFunction[mid+1];
760          functionSize_ = next_func->getOffset() - getOffset();
761          return functionSize_;
762       }
763    }
764 }
765