Merge John's changes and update test suite.
[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 <atomic>
34 #include <set>
35 #include <vector>
36 #include <queue>
37 #include <atomic>
38
39 #include "dyntypes.h"
40 #include "IBSTree.h"
41 #include "IBSTree-fast.h"
42 #include "CodeObject.h"
43 #include "CFG.h"
44 #include "ParserDetails.h"
45 #include "debug_parse.h"
46
47 #include "race-detector-annotations.h"
48
49 #include <boost/thread/locks.hpp>
50 #include <boost/thread/lockable_adapter.hpp>
51 #include <boost/thread/recursive_mutex.hpp>
52
53
54 #include "tbb/concurrent_hash_map.h"
55
56 using namespace std;
57
58 namespace Dyninst {
59 namespace ParseAPI {
60
61 class Parser;
62 class ParseData;
63
64 /** Describes a saved frame during recursive parsing **/
65 // Parsing data for a function. 
66 class ParseFrame : public boost::lockable_adapter<boost::recursive_mutex> {
67  public:
68     enum Status {
69         UNPARSED,
70         PROGRESS,
71         CALL_BLOCKED,
72         PARSED,
73         FRAME_ERROR,
74         BAD_LOOKUP,  // error for lookups that return Status
75         FRAME_DELAYED // discovered cyclic dependency, delaying parse
76     };
77
78     /* worklist details */
79     typedef std::priority_queue<
80         ParseWorkElem *,
81         vector<ParseWorkElem*>,
82         ParseWorkElem::compare
83        > worklist_t;
84
85     vector<ParseWorkBundle*> work_bundles; 
86    
87     /* convenience generator for work elements. If a NULL bundle is
88        supplied, one will be provided. */
89     ParseWorkElem * mkWork(
90         ParseWorkBundle * b,
91         Edge * e,
92         Address target,
93         bool resolvable,
94         bool tailcall);
95     ParseWorkElem * mkWork(
96         ParseWorkBundle * b,
97         Block* block,
98         const InsnAdapter::IA_IAPI *ah);
99
100     void pushWork(ParseWorkElem * elem) {
101         boost::lock_guard<ParseFrame> g(*this);
102         parsing_printf("\t pushing work element for block %p, edge %p, target %p\n", elem->cur(), elem->edge(), elem->target());
103         worklist.push(elem);
104     }
105     ParseWorkElem * popWork() {
106         boost::lock_guard<ParseFrame> g(*this);
107         ParseWorkElem * ret = NULL;
108         if(!worklist.empty()) {
109             ret = worklist.top();
110             worklist.pop();
111         }
112         return ret;
113     }
114
115     void pushDelayedWork(ParseWorkElem * elem, Function * ct) {
116         boost::lock_guard<ParseFrame> g(*this);
117         delayedWork.insert(make_pair(elem, ct));
118     }
119
120     void cleanup();
121
122     worklist_t worklist;
123     std::set<Address> knownTargets; // This set contains known potential targets in this function 
124    
125     // Delayed work elements 
126     std::map<ParseWorkElem *, Function *> delayedWork;
127
128     dyn_hash_map<Address, Block*> leadersToBlock;  // block map
129     Address curAddr;                           // current insn address
130     unsigned num_insns;
131     dyn_hash_map<Address, bool> visited;
132
133     /* These are set when status goes to CALL_BLOCKED */
134     Function * call_target;     // discovered callee
135
136     Function * func;
137     CodeRegion * codereg;
138
139     ParseWorkElem * seed; // stored for cleanup
140
141     ParseFrame(Function * f,ParseData *pd) :
142         curAddr(0),
143         num_insns(0),
144         call_target(NULL),
145         func(f),
146         codereg(f->region()),
147         seed(NULL),
148         _pd(pd),
149         inProcess(false)
150     {
151         set_status(UNPARSED);
152         busy.store(false);
153     }
154
155     ~ParseFrame();
156
157     Status status() const {
158       race_detector_fake_lock_acquire(race_detector_fake_lock(_status));
159       Status result = _status.load();
160       race_detector_fake_lock_release(race_detector_fake_lock(_status));
161       return result;
162     }
163     void set_status(Status);
164     bool swap_busy(bool value) {
165       return busy.exchange(value);
166     }
167 ;
168  private:
169     std::atomic<Status> _status;
170     std::atomic<bool> busy;
171     ParseData * _pd;
172 };
173
174 /* per-CodeRegion parsing data */
175 class region_data {
176 public:
177     // Function lookups
178     Dyninst::IBSTree_fast<FuncExtent> funcsByRange;
179     tbb::concurrent_hash_map<Address, Function *> funcsByAddr;
180
181     // Block lookups
182     Dyninst::IBSTree_fast<Block > blocksByRange;
183     tbb::concurrent_hash_map<Address, Block *> blocksByAddr;
184
185     // Parsing internals 
186     tbb::concurrent_hash_map<Address, ParseFrame *> frame_map;
187     tbb::concurrent_hash_map<Address, ParseFrame::Status> frame_status;
188
189     Function * findFunc(Address entry);
190     Block * findBlock(Address entry);
191     int findFuncs(Address addr, set<Function *> & funcs);
192     int findBlocks(Address addr, set<Block *> & blocks);
193
194     /* 
195      * Look up the next block for detection of straight-line
196      * fallthrough edges into existing blocks.
197      */
198     inline std::pair<Address, Block*> get_next_block(Address addr)
199     {
200         Block * nextBlock = NULL;
201         Address nextBlockAddr = numeric_limits<Address>::max();
202
203         if((nextBlock = blocksByRange.successor(addr)) &&
204            nextBlock->start() > addr)
205         {
206             nextBlockAddr = nextBlock->start();   
207         }
208
209         return std::pair<Address,Block*>(nextBlockAddr,nextBlock);
210     }
211     ParseFrame* findFrame(Address addr) const {
212         ParseFrame *result = NULL;
213         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_map));
214         {
215           tbb::concurrent_hash_map<Address, ParseFrame*>::const_accessor a;
216           if(frame_map.find(a, addr)) result = a->second;
217         }
218         race_detector_fake_lock_release(race_detector_fake_lock(frame_map));
219         return result;
220     }
221     void setFrameStatus(Address addr, ParseFrame::Status status)
222     {
223         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_status));
224         {
225           tbb::concurrent_hash_map<Address, ParseFrame::Status>::accessor a;
226           frame_status.insert(a, make_pair(addr, status));
227         }
228         race_detector_fake_lock_release(race_detector_fake_lock(frame_status));
229     }
230     void record_func(Function* f) {
231         race_detector_fake_lock_acquire(race_detector_fake_lock(funcsByAddr));
232         {
233           tbb::concurrent_hash_map<Address, Function*>::accessor a;
234           funcsByAddr.insert(a, std::make_pair(f->addr(), f));
235         }
236         race_detector_fake_lock_release(race_detector_fake_lock(funcsByAddr));
237
238     }
239     void record_block(Block* b) {
240         race_detector_fake_lock_acquire(race_detector_fake_lock(blocksByAddr));
241         {
242           tbb::concurrent_hash_map<Address, Block*>::accessor a;
243           blocksByAddr.insert(a, std::make_pair(b->start(), b));
244         }
245         race_detector_fake_lock_release(race_detector_fake_lock(blocksByAddr));
246         blocksByRange.insert(b);
247     }
248     void updateBlockEnd(Block* b, Address addr, Address previnsn) {
249         blocksByRange.remove(b);
250         b->updateEnd(addr);
251         b->_lastInsn = previnsn;
252         blocksByRange.insert(b);
253     }
254     void record_frame(ParseFrame* pf) {
255         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_map));
256         {
257           tbb::concurrent_hash_map<Address, ParseFrame*>::accessor a;
258           frame_map.insert(a, make_pair(pf->func->addr(), pf));
259         }
260         race_detector_fake_lock_release(race_detector_fake_lock(frame_map));
261     }
262     
263          // Find functions within [start,end)
264          int findFuncs(Address start, Address end, set<Function *> & funcs);
265 };
266
267 /** region_data inlines **/
268
269 inline Function *
270 region_data::findFunc(Address entry)
271 {
272     Function *result = NULL;
273     race_detector_fake_lock_acquire(race_detector_fake_lock(funcsByAddr));
274     {
275       tbb::concurrent_hash_map<Address, Function *>::const_accessor a;
276       if(funcsByAddr.find(a, entry)) result = a->second;
277     }
278     race_detector_fake_lock_release(race_detector_fake_lock(funcsByAddr));
279     return result;
280 }
281 inline Block *
282 region_data::findBlock(Address entry)
283 {
284     Block *result = NULL;
285     race_detector_fake_lock_acquire(race_detector_fake_lock(blocksByAddr));
286     {
287       tbb::concurrent_hash_map<Address, Block *>::const_accessor a;
288       if(blocksByAddr.find(a, entry)) result = a->second;
289     }
290     race_detector_fake_lock_release(race_detector_fake_lock(blocksByAddr));
291     return result;
292 }
293 inline int
294 region_data::findFuncs(Address addr, set<Function *> & funcs)
295 {
296     int sz = funcs.size();
297
298     set<FuncExtent *> extents;
299     set<FuncExtent *>::iterator eit;
300     
301     funcsByRange.find(addr,extents);
302     for(eit = extents.begin(); eit != extents.end(); ++eit)
303         funcs.insert((*eit)->func());
304  
305     return funcs.size() - sz;
306 }
307 inline int
308 region_data::findFuncs(Address start, Address end, set<Function *> & funcs)
309 {
310          FuncExtent dummy(NULL,start,end);
311     int sz = funcs.size();
312
313     set<FuncExtent *> extents;
314     set<FuncExtent *>::iterator eit;
315     
316     funcsByRange.find(&dummy,extents);
317     for(eit = extents.begin(); eit != extents.end(); ++eit)
318         funcs.insert((*eit)->func());
319  
320     return funcs.size() - sz;
321 }
322 inline int
323 region_data::findBlocks(Address addr, set<Block *> & blocks)
324 {
325     int sz = blocks.size();
326     blocksByRange.find(addr,blocks);
327     return blocks.size() - sz;
328 }
329
330
331 /** end region_data **/
332
333 class ParseData : public boost::lockable_adapter<boost::recursive_mutex>  {
334  protected:
335     ParseData(Parser *p) : _parser(p) { }
336     Parser * _parser;
337  public:
338     virtual ~ParseData() { }
339
340     //
341     virtual Function * findFunc(CodeRegion *, Address) =0;
342     virtual Block * findBlock(CodeRegion *, Address) =0;
343     virtual int findFuncs(CodeRegion *, Address, set<Function*> &) =0;
344     virtual int findFuncs(CodeRegion *, Address, Address, set<Function*> &) =0;
345     virtual int findBlocks(CodeRegion *, Address, set<Block*> &) =0;
346     virtual ParseFrame * findFrame(CodeRegion *, Address) = 0;
347     ParseFrame::Status frameStatus(CodeRegion *, Address addr) {
348         ParseFrame* f = nullptr;
349         if((f = findFrame(nullptr, addr))) return f->status();
350         return ParseFrame::BAD_LOOKUP;
351     }
352     virtual void setFrameStatus(CodeRegion*,Address,ParseFrame::Status) = 0;
353
354     // creation (if non-existing)
355     virtual Function * get_func(CodeRegion *, Address, FuncSource) =0;
356
357     // mapping
358     virtual region_data * findRegion(CodeRegion *) =0;
359
360     // accounting
361     virtual void record_func(Function *) =0;
362     virtual void record_block(CodeRegion *, Block *) =0;
363     virtual void record_frame(ParseFrame *) =0;
364
365     // removal
366     virtual void remove_frame(ParseFrame *) =0;
367     virtual void remove_func(Function *) =0;
368     virtual void remove_block(Block *) =0;
369     virtual void remove_extents(const std::vector<FuncExtent*> &extents) =0;
370
371     // does the Right Thing(TM) for standard- and overlapping-region 
372     // object types
373     virtual CodeRegion * reglookup(CodeRegion *cr, Address addr) =0;
374 };
375
376 /* StandardParseData represents parse data for Parsers that disallow
377    overlapping CodeRegions. It has fast paths for lookup */
378 class StandardParseData : public ParseData {
379  private:
380     region_data _rdata;
381  public:
382     /* interface implementation */
383     StandardParseData(Parser *p);
384     ~StandardParseData();
385
386     Function * findFunc(CodeRegion * pf, Address addr);
387     Block * findBlock(CodeRegion * pf, Address addr);
388     int findFuncs(CodeRegion *, Address, set<Function*> &);
389     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
390     int findBlocks(CodeRegion *, Address, set<Block*> &);
391     ParseFrame * findFrame(CodeRegion *, Address);
392     ParseFrame::Status frameStatus(CodeRegion *, Address);
393     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
394
395     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
396
397     region_data * findRegion(CodeRegion *cr);
398
399     void record_func(Function *f);
400     void record_block(CodeRegion *cr, Block *b);
401     void record_frame(ParseFrame *pf);
402
403     void remove_frame(ParseFrame *);
404     void remove_func(Function *);
405     void remove_block(Block *);
406     void remove_extents(const std::vector<FuncExtent*> &extents);
407
408     CodeRegion * reglookup(CodeRegion *cr, Address addr);
409 };
410
411 inline region_data * StandardParseData::findRegion(CodeRegion * /* cr */)
412 {
413     return &_rdata;
414 }
415 inline void StandardParseData::record_func(Function *f)
416 {
417     _rdata.record_func(f);
418 }
419 inline void StandardParseData::record_block(CodeRegion * /* cr */, Block *b)
420 {
421     _rdata.record_block(b);
422 }
423
424 /* OverlappingParseData handles binary code objects like .o files
425    where CodeRegions may overlap on the same linear address space */
426 class OverlappingParseData : public ParseData {
427     typedef dyn_hash_map<void *, region_data *> reg_map_t;
428  private:
429     reg_map_t rmap;
430  public:
431     OverlappingParseData(Parser *p, vector<CodeRegion *> & regions);
432     ~OverlappingParseData();
433
434     /* interface implementation */
435     Function * findFunc(CodeRegion *, Address addr);
436     Block * findBlock(CodeRegion *, Address addr);
437     int findFuncs(CodeRegion *, Address, set<Function*> &);
438     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
439     int findBlocks(CodeRegion *, Address, set<Block*> &);
440     ParseFrame * findFrame(CodeRegion *, Address);
441     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
442
443     Function * get_func(CodeRegion * cr, Address addr, FuncSource src);
444
445     region_data * findRegion(CodeRegion *cr);
446
447     void record_func(Function *f);
448     void record_block(CodeRegion *cr, Block *b);
449     void record_frame(ParseFrame *pf);
450
451     void remove_frame(ParseFrame *);
452     void remove_func(Function *);
453     void remove_block(Block *);
454     void remove_extents(const std::vector<FuncExtent*> &extents);
455
456     CodeRegion * reglookup(CodeRegion *cr, Address addr);
457 };
458
459 }
460 }
461
462 #endif