Identify shared code regions
[dyninst.git] / parseAPI / src / ParseData.h
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 #ifndef _PARSE_DATA_H_
32 #define _PARSE_DATA_H_
33
34 #include <set>
35 #include <vector>
36
37 #include "dyntypes.h"
38 #include "IBSTree.h"
39
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 class ParseFrame {
56  public:
57     enum Status {
58         UNPARSED,
59         PROGRESS,
60         CALL_BLOCKED,
61         PARSED,
62         FRAME_ERROR,
63         BAD_LOOKUP  // error for lookups that return Status
64     };
65
66     /* worklist details */
67     typedef std::priority_queue<
68         ParseWorkElem *,
69         vector<ParseWorkElem*>,
70         ParseWorkElem::compare
71        > worklist_t;
72
73     vector<ParseWorkBundle*> work_bundles; 
74
75     void pushWork(ParseWorkElem * elem) {
76         worklist.push(elem);
77     }
78     ParseWorkElem * popWork() {
79         ParseWorkElem * ret = NULL;
80         if(!worklist.empty()) {
81             ret = worklist.top();
82             worklist.pop();
83         }
84         return ret;
85     }
86
87     void cleanup();
88
89     worklist_t worklist; 
90
91     
92     dyn_hash_map<Address, Block*> leadersToBlock;  // block map
93     Address curAddr;                           // current insn address
94     unsigned num_insns;
95     dyn_hash_map<Address, bool> visited;
96
97     /* These are set when status goes to CALL_BLOCKED */
98     Function * call_target;     // discovered callee
99
100     Function * func;
101     CodeRegion * codereg;
102
103     ParseWorkElem * seed; // stored for cleanup
104
105     ParseFrame(Function * f,ParseData *pd) :
106         curAddr(0),
107         num_insns(0),
108         call_target(NULL),
109         func(f),
110         codereg(f->region()),
111         seed(NULL),
112         _pd(pd)
113     {
114         set_status(UNPARSED);
115     }
116
117     ~ParseFrame();
118
119     Status status() const { return _status; }
120     void set_status(Status);
121  private:
122     Status _status;
123     ParseData * _pd;
124 };
125
126 /* per-CodeRegion parsing data */
127 class region_data { 
128  public:
129     // Function lookups
130     Dyninst::IBSTree<FuncExtent> funcsByRange;
131     dyn_hash_map<Address, Function *> funcsByAddr;
132
133     // Block lookups
134     Dyninst::IBSTree<Block> blocksByRange;
135     dyn_hash_map<Address, Block *> blocksByAddr;
136
137     // Parsing internals 
138     dyn_hash_map<Address, ParseFrame *> frame_map;
139     dyn_hash_map<Address, ParseFrame::Status> frame_status;
140
141     Function * findFunc(Address entry);
142     Block * findBlock(Address entry);
143     int findFuncs(Address addr, set<Function *> & funcs);
144     int findBlocks(Address addr, set<Block *> & blocks);
145
146          // Find functions within [start,end)
147          int findFuncs(Address start, Address end, set<Function *> & funcs);
148 };
149
150 /** region_data inlines **/
151
152 inline Function *
153 region_data::findFunc(Address entry)
154 {
155     dyn_hash_map<Address, Function *>::iterator fit;
156     if((fit = funcsByAddr.find(entry)) != funcsByAddr.end())
157         return fit->second;
158     else
159         return NULL;
160 }
161 inline Block *
162 region_data::findBlock(Address entry)
163 {
164     dyn_hash_map<Address, Block *>::iterator bit;
165     if((bit = blocksByAddr.find(entry)) != blocksByAddr.end())
166         return bit->second;
167     else
168         return NULL;
169 }
170 inline int
171 region_data::findFuncs(Address addr, set<Function *> & funcs)
172 {
173     int sz = funcs.size();
174
175     set<FuncExtent *> extents;
176     set<FuncExtent *>::iterator eit;
177     
178     funcsByRange.find(addr,extents);
179     for(eit = extents.begin(); eit != extents.end(); ++eit)
180         funcs.insert((*eit)->func());
181  
182     return funcs.size() - sz;
183 }
184 inline int
185 region_data::findFuncs(Address start, Address end, set<Function *> & funcs)
186 {
187          FuncExtent dummy(NULL,start,end);
188     int sz = funcs.size();
189
190     set<FuncExtent *> extents;
191     set<FuncExtent *>::iterator eit;
192     
193     funcsByRange.find(&dummy,extents);
194     for(eit = extents.begin(); eit != extents.end(); ++eit)
195         funcs.insert((*eit)->func());
196  
197     return funcs.size() - sz;
198 }
199 inline int
200 region_data::findBlocks(Address addr, set<Block *> & blocks)
201 {
202     int sz = blocks.size();
203
204     blocksByRange.find(addr,blocks);
205     return blocks.size() - sz;
206 }
207
208
209 /** end region_data **/
210
211 class ParseData {
212  protected:
213     ParseData(Parser *p) : _parser(p) { }
214     Parser * _parser;
215  public:
216     virtual ~ParseData() { }
217
218     //
219     virtual Function * findFunc(CodeRegion *, Address) =0;
220     virtual Block * findBlock(CodeRegion *, Address) =0;
221     virtual int findFuncs(CodeRegion *, Address, set<Function*> &) =0;
222     virtual int findBlocks(CodeRegion *, Address, set<Block*> &) =0;
223     virtual ParseFrame * findFrame(CodeRegion *, Address) = 0;
224     virtual ParseFrame::Status frameStatus(CodeRegion *, Address) = 0;
225     virtual void setFrameStatus(CodeRegion*,Address,ParseFrame::Status) = 0;
226
227     // creation (if non-existing)
228     virtual Function * get_func(CodeRegion *, Address, FuncSource) =0;
229
230     // mapping
231     virtual region_data * findRegion(CodeRegion *) =0;
232
233     // accounting
234     virtual void record_func(Function *) =0;
235     virtual void record_block(CodeRegion *, Block *) =0;
236     virtual void record_frame(ParseFrame *) =0;
237
238     // removal
239     virtual void remove_frame(ParseFrame *) =0;
240     virtual void remove_func(Function *) =0;
241     virtual void remove_block(Block *) =0;
242     virtual void remove_extents(const std::vector<FuncExtent*> &extents) =0;
243
244     // does the Right Thing(TM) for standard- and overlapping-region 
245     // object types
246     virtual CodeRegion * reglookup(CodeRegion *cr, Address addr) =0;
247 };
248
249 /* StandardParseData represents parse data for Parsers that disallow
250    overlapping CodeRegions. It has fast paths for lookup */
251 class StandardParseData : public ParseData {
252  private:
253     region_data _rdata;
254  public:
255     /* interface implementation */
256     StandardParseData(Parser *p);
257     ~StandardParseData();
258
259     Function * findFunc(CodeRegion * pf, Address addr);
260     Block * findBlock(CodeRegion * pf, Address addr);
261     int findFuncs(CodeRegion *, Address, set<Function*> &);
262     int findBlocks(CodeRegion *, Address, set<Block*> &);
263     ParseFrame * findFrame(CodeRegion *, Address);
264     ParseFrame::Status frameStatus(CodeRegion *, Address);
265     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
266
267     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
268
269     region_data * findRegion(CodeRegion *cr);
270
271     void record_func(Function *f);
272     void record_block(CodeRegion *cr, Block *b);
273     void record_frame(ParseFrame *pf);
274
275     void remove_frame(ParseFrame *);
276     void remove_func(Function *);
277     void remove_block(Block *);
278     void remove_extents(const std::vector<FuncExtent*> &extents);
279
280     CodeRegion * reglookup(CodeRegion *cr, Address addr);
281 };
282
283 inline region_data * StandardParseData::findRegion(CodeRegion * /* cr */)
284 {
285     return &_rdata;
286 }
287 inline void StandardParseData::record_func(Function *f)
288 {
289     _rdata.funcsByAddr[f->addr()] = f;
290 }
291 inline void StandardParseData::record_block(CodeRegion * /* cr */, Block *b)
292 {
293     _rdata.blocksByAddr[b->start()] = b;
294     _rdata.blocksByRange.insert(b);
295 }
296
297 /* OverlappingParseData handles binary code objects like .o files
298    where CodeRegions may overlap on the same linear address space */
299 class OverlappingParseData : public ParseData {
300     typedef dyn_hash_map<void *, region_data *> reg_map_t;
301  private:
302     reg_map_t rmap;
303  public:
304     OverlappingParseData(Parser *p, vector<CodeRegion *> & regions);
305     ~OverlappingParseData();
306
307     /* interface implementation */
308     Function * findFunc(CodeRegion *, Address addr);
309     Block * findBlock(CodeRegion *, Address addr);
310     int findFuncs(CodeRegion *, Address, set<Function*> &);
311     int findBlocks(CodeRegion *, Address, set<Block*> &);
312     ParseFrame * findFrame(CodeRegion *, Address);
313     ParseFrame::Status frameStatus(CodeRegion *, Address);
314     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
315
316     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
317
318     region_data * findRegion(CodeRegion *cr);
319
320     void record_func(Function *f);
321     void record_block(CodeRegion *cr, Block *b);
322     void record_frame(ParseFrame *pf);
323
324     void remove_frame(ParseFrame *);
325     void remove_func(Function *);
326     void remove_block(Block *);
327     void remove_extents(const std::vector<FuncExtent*> &extents);
328
329     CodeRegion * reglookup(CodeRegion *cr, Address addr);
330 };
331
332 }
333 }
334
335 #endif