Fixes for non-returning functions and tail calls:
[dyninst.git] / parseAPI / src / ParseData.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30 #ifndef _PARSE_DATA_H_
31 #define _PARSE_DATA_H_
32
33 #include <set>
34 #include <vector>
35 #include <queue>
36
37 #include "dyntypes.h"
38 #include "IBSTree.h"
39 #include "IBSTree-fast.h"
40 #include "CodeObject.h"
41 #include "CFG.h"
42 #include "ParserDetails.h"
43 #include "debug_parse.h"
44
45
46 using namespace std;
47
48 namespace Dyninst {
49 namespace ParseAPI {
50
51 class Parser;
52 class ParseData;
53
54 /** Describes a saved frame during recursive parsing **/
55 // Parsing data for a function. 
56 class ParseFrame {
57  public:
58     enum Status {
59         UNPARSED,
60         PROGRESS,
61         CALL_BLOCKED,
62         PARSED,
63         FRAME_ERROR,
64         BAD_LOOKUP,  // error for lookups that return Status
65         FRAME_DELAYED // discovered cyclic dependency, delaying parse
66     };
67
68     /* worklist details */
69     typedef std::priority_queue<
70         ParseWorkElem *,
71         vector<ParseWorkElem*>,
72         ParseWorkElem::compare
73        > worklist_t;
74
75     vector<ParseWorkBundle*> work_bundles; 
76    
77     /* convenience generator for work elements. If a NULL bundle is
78        supplied, one will be provided. */
79     ParseWorkElem * mkWork(
80         ParseWorkBundle * b,
81         Edge * e,
82         Address target,
83         bool resolvable,
84         bool tailcall);
85     ParseWorkElem * mkWork(
86         ParseWorkBundle * b,
87         Block* block,
88         const InsnAdapter::IA_IAPI &ah);
89
90     void pushWork(ParseWorkElem * elem) {
91         worklist.push(elem);
92     }
93     ParseWorkElem * popWork() {
94         ParseWorkElem * ret = NULL;
95         if(!worklist.empty()) {
96             ret = worklist.top();
97             worklist.pop();
98         }
99         return ret;
100     }
101
102     void pushDelayedWork(ParseWorkElem * elem, Function * ct) {
103         delayedWork.insert(make_pair(elem, ct));
104     }
105
106     void cleanup();
107
108     worklist_t worklist;
109     std::set<Address> knownTargets; // This set contains known potential targets in this function 
110    
111     // Delayed work elements 
112     std::map<ParseWorkElem *, Function *> delayedWork;
113
114     dyn_hash_map<Address, Block*> leadersToBlock;  // block map
115     Address curAddr;                           // current insn address
116     unsigned num_insns;
117     dyn_hash_map<Address, bool> visited;
118
119     /* These are set when status goes to CALL_BLOCKED */
120     Function * call_target;     // discovered callee
121
122     Function * func;
123     CodeRegion * codereg;
124
125     ParseWorkElem * seed; // stored for cleanup
126
127     ParseFrame(Function * f,ParseData *pd) :
128         curAddr(0),
129         num_insns(0),
130         call_target(NULL),
131         func(f),
132         codereg(f->region()),
133         seed(NULL),
134         _pd(pd)
135     {
136         set_status(UNPARSED);
137     }
138
139     ~ParseFrame();
140
141     Status status() const { return _status; }
142     void set_status(Status);
143  private:
144     Status _status;
145     ParseData * _pd;
146 };
147
148 /* per-CodeRegion parsing data */
149 class region_data { 
150  public:
151   // Function lookups
152   Dyninst::IBSTree_fast<FuncExtent> funcsByRange;
153     dyn_hash_map<Address, Function *> funcsByAddr;
154
155     // Block lookups
156     Dyninst::IBSTree_fast<Block> blocksByRange;
157     dyn_hash_map<Address, Block *> blocksByAddr;
158
159     // Parsing internals 
160     dyn_hash_map<Address, ParseFrame *> frame_map;
161     dyn_hash_map<Address, ParseFrame::Status> frame_status;
162
163     Function * findFunc(Address entry);
164     Block * findBlock(Address entry);
165     int findFuncs(Address addr, set<Function *> & funcs);
166     int findBlocks(Address addr, set<Block *> & blocks);
167
168     /* 
169      * Look up the next block for detection of straight-line
170      * fallthrough edges into existing blocks.
171      */
172     inline std::pair<Address, Block*> get_next_block(Address addr)
173     {
174         Block * nextBlock = NULL;
175         Address nextBlockAddr = numeric_limits<Address>::max();
176
177         if((nextBlock = blocksByRange.successor(addr)) &&
178            nextBlock->start() > addr)
179         {
180             nextBlockAddr = nextBlock->start();   
181         }
182
183         return std::pair<Address,Block*>(nextBlockAddr,nextBlock);
184     }
185     
186          // Find functions within [start,end)
187          int findFuncs(Address start, Address end, set<Function *> & funcs);
188 };
189
190 /** region_data inlines **/
191
192 inline Function *
193 region_data::findFunc(Address entry)
194 {
195     dyn_hash_map<Address, Function *>::iterator fit;
196     if((fit = funcsByAddr.find(entry)) != funcsByAddr.end())
197         return fit->second;
198     else
199         return NULL;
200 }
201 inline Block *
202 region_data::findBlock(Address entry)
203 {
204     dyn_hash_map<Address, Block *>::iterator bit;
205     if((bit = blocksByAddr.find(entry)) != blocksByAddr.end())
206         return bit->second;
207     else
208         return NULL;
209 }
210 inline int
211 region_data::findFuncs(Address addr, set<Function *> & funcs)
212 {
213     int sz = funcs.size();
214
215     set<FuncExtent *> extents;
216     set<FuncExtent *>::iterator eit;
217     
218     funcsByRange.find(addr,extents);
219     for(eit = extents.begin(); eit != extents.end(); ++eit)
220         funcs.insert((*eit)->func());
221  
222     return funcs.size() - sz;
223 }
224 inline int
225 region_data::findFuncs(Address start, Address end, set<Function *> & funcs)
226 {
227          FuncExtent dummy(NULL,start,end);
228     int sz = funcs.size();
229
230     set<FuncExtent *> extents;
231     set<FuncExtent *>::iterator eit;
232     
233     funcsByRange.find(&dummy,extents);
234     for(eit = extents.begin(); eit != extents.end(); ++eit)
235         funcs.insert((*eit)->func());
236  
237     return funcs.size() - sz;
238 }
239 inline int
240 region_data::findBlocks(Address addr, set<Block *> & blocks)
241 {
242     int sz = blocks.size();
243
244     blocksByRange.find(addr,blocks);
245     return blocks.size() - sz;
246 }
247
248
249 /** end region_data **/
250
251 class ParseData {
252  protected:
253     ParseData(Parser *p) : _parser(p) { }
254     Parser * _parser;
255  public:
256     virtual ~ParseData() { }
257
258     //
259     virtual Function * findFunc(CodeRegion *, Address) =0;
260     virtual Block * findBlock(CodeRegion *, Address) =0;
261     virtual int findFuncs(CodeRegion *, Address, set<Function*> &) =0;
262     virtual int findFuncs(CodeRegion *, Address, Address, set<Function*> &) =0;
263     virtual int findBlocks(CodeRegion *, Address, set<Block*> &) =0;
264     virtual ParseFrame * findFrame(CodeRegion *, Address) = 0;
265     virtual ParseFrame::Status frameStatus(CodeRegion *, Address) = 0;
266     virtual void setFrameStatus(CodeRegion*,Address,ParseFrame::Status) = 0;
267
268     // creation (if non-existing)
269     virtual Function * get_func(CodeRegion *, Address, FuncSource) =0;
270
271     // mapping
272     virtual region_data * findRegion(CodeRegion *) =0;
273
274     // accounting
275     virtual void record_func(Function *) =0;
276     virtual void record_block(CodeRegion *, Block *) =0;
277     virtual void record_frame(ParseFrame *) =0;
278
279     // removal
280     virtual void remove_frame(ParseFrame *) =0;
281     virtual void remove_func(Function *) =0;
282     virtual void remove_block(Block *) =0;
283     virtual void remove_extents(const std::vector<FuncExtent*> &extents) =0;
284
285     // does the Right Thing(TM) for standard- and overlapping-region 
286     // object types
287     virtual CodeRegion * reglookup(CodeRegion *cr, Address addr) =0;
288 };
289
290 /* StandardParseData represents parse data for Parsers that disallow
291    overlapping CodeRegions. It has fast paths for lookup */
292 class StandardParseData : public ParseData {
293  private:
294     region_data _rdata;
295  public:
296     /* interface implementation */
297     StandardParseData(Parser *p);
298     ~StandardParseData();
299
300     Function * findFunc(CodeRegion * pf, Address addr);
301     Block * findBlock(CodeRegion * pf, Address addr);
302     int findFuncs(CodeRegion *, Address, set<Function*> &);
303     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
304     int findBlocks(CodeRegion *, Address, set<Block*> &);
305     ParseFrame * findFrame(CodeRegion *, Address);
306     ParseFrame::Status frameStatus(CodeRegion *, Address);
307     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
308
309     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
310
311     region_data * findRegion(CodeRegion *cr);
312
313     void record_func(Function *f);
314     void record_block(CodeRegion *cr, Block *b);
315     void record_frame(ParseFrame *pf);
316
317     void remove_frame(ParseFrame *);
318     void remove_func(Function *);
319     void remove_block(Block *);
320     void remove_extents(const std::vector<FuncExtent*> &extents);
321
322     CodeRegion * reglookup(CodeRegion *cr, Address addr);
323 };
324
325 inline region_data * StandardParseData::findRegion(CodeRegion * /* cr */)
326 {
327     return &_rdata;
328 }
329 inline void StandardParseData::record_func(Function *f)
330 {
331     _rdata.funcsByAddr[f->addr()] = f;
332 }
333 inline void StandardParseData::record_block(CodeRegion * /* cr */, Block *b)
334 {
335     _rdata.blocksByAddr[b->start()] = b;
336     _rdata.blocksByRange.insert(b);
337 }
338
339 /* OverlappingParseData handles binary code objects like .o files
340    where CodeRegions may overlap on the same linear address space */
341 class OverlappingParseData : public ParseData {
342     typedef dyn_hash_map<void *, region_data *> reg_map_t;
343  private:
344     reg_map_t rmap;
345  public:
346     OverlappingParseData(Parser *p, vector<CodeRegion *> & regions);
347     ~OverlappingParseData();
348
349     /* interface implementation */
350     Function * findFunc(CodeRegion *, Address addr);
351     Block * findBlock(CodeRegion *, Address addr);
352     int findFuncs(CodeRegion *, Address, set<Function*> &);
353     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
354     int findBlocks(CodeRegion *, Address, set<Block*> &);
355     ParseFrame * findFrame(CodeRegion *, Address);
356     ParseFrame::Status frameStatus(CodeRegion *, Address);
357     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
358
359     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
360
361     region_data * findRegion(CodeRegion *cr);
362
363     void record_func(Function *f);
364     void record_block(CodeRegion *cr, Block *b);
365     void record_frame(ParseFrame *pf);
366
367     void remove_frame(ParseFrame *);
368     void remove_func(Function *);
369     void remove_block(Block *);
370     void remove_extents(const std::vector<FuncExtent*> &extents);
371
372     CodeRegion * reglookup(CodeRegion *cr, Address addr);
373 };
374
375 }
376 }
377
378 #endif