Defer constructing blocksByRange to function finalizing, and removing the use blocksB...
[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     std::map<Address, Block*> leadersToBlock;
129     //dyn_hash_map<Address, Block*> leadersToBlock;  // block map
130     Address curAddr;                           // current insn address
131     unsigned num_insns;
132     dyn_hash_map<Address, bool> visited;
133
134     /* These are set when status goes to CALL_BLOCKED */
135     Function * call_target;     // discovered callee
136
137     Function * func;
138     CodeRegion * codereg;
139
140     ParseWorkElem * seed; // stored for cleanup
141
142     ParseFrame(Function * f,ParseData *pd) :
143         curAddr(0),
144         num_insns(0),
145         call_target(NULL),
146         func(f),
147         codereg(f->region()),
148         seed(NULL),
149         _pd(pd)
150     {
151         busy.store(false);
152     }
153
154     ~ParseFrame();
155
156     Status status() const {
157       race_detector_fake_lock_acquire(race_detector_fake_lock(_status));
158       Status result = _status.load();
159       race_detector_fake_lock_release(race_detector_fake_lock(_status));
160       return result;
161     }
162     void set_status(Status);
163     bool swap_busy(bool value) {
164       return busy.exchange(value);
165     }
166 ;
167  private:
168     std::atomic<Status> _status;
169     std::atomic<bool> busy;
170     ParseData * _pd;
171 };
172
173 /* per-CodeRegion parsing data */
174 class region_data {
175 public:
176     // Function lookups
177     Dyninst::IBSTree_fast<FuncExtent> funcsByRange;
178     tbb::concurrent_hash_map<Address, Function *> funcsByAddr;
179
180     // Block lookups
181     Dyninst::IBSTree_fast<Block > blocksByRange;
182     tbb::concurrent_hash_map<Address, Block *> blocksByAddr;
183
184     // Parsing internals 
185     tbb::concurrent_hash_map<Address, ParseFrame *> frame_map;
186     tbb::concurrent_hash_map<Address, ParseFrame::Status> frame_status;
187
188     Function * findFunc(Address entry);
189     Block * findBlock(Address entry);
190     int findFuncs(Address addr, set<Function *> & funcs);
191     int findBlocks(Address addr, set<Block *> & blocks);
192
193     /* 
194      * Look up the next block for detection of straight-line
195      * fallthrough edges into existing blocks.
196      */
197     inline std::pair<Address, Block*> get_next_block(Address addr)
198     {
199         Block * nextBlock = NULL;
200         Address nextBlockAddr = numeric_limits<Address>::max();
201
202         if((nextBlock = blocksByRange.successor(addr)) &&
203            nextBlock->start() > addr)
204         {
205             nextBlockAddr = nextBlock->start();   
206         }
207
208         return std::pair<Address,Block*>(nextBlockAddr,nextBlock);
209     }
210     ParseFrame* findFrame(Address addr) const {
211         ParseFrame *result = NULL;
212         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_map));
213         {
214           tbb::concurrent_hash_map<Address, ParseFrame*>::const_accessor a;
215           if(frame_map.find(a, addr)) result = a->second;
216         }
217         race_detector_fake_lock_release(race_detector_fake_lock(frame_map));
218         return result;
219     }
220     ParseFrame::Status getFrameStatus(Address addr) {
221         tbb::concurrent_hash_map<Address, ParseFrame::Status>::const_accessor a;
222         frame_status.find(a, addr);
223         return a->second;
224     }
225
226
227     void setFrameStatus(Address addr, ParseFrame::Status status)
228     {
229         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_status));
230         {
231           tbb::concurrent_hash_map<Address, ParseFrame::Status>::accessor a;
232           frame_status.insert(a, make_pair(addr, status));
233       a->second = status;
234         }
235         race_detector_fake_lock_release(race_detector_fake_lock(frame_status));
236     }
237
238     void record_func(Function* f) {
239         race_detector_fake_lock_acquire(race_detector_fake_lock(funcsByAddr));
240         {
241           tbb::concurrent_hash_map<Address, Function*>::accessor a;
242           funcsByAddr.insert(a, std::make_pair(f->addr(), f));
243         }
244         race_detector_fake_lock_release(race_detector_fake_lock(funcsByAddr));
245
246     }
247     Block* record_block(Block* b) {
248         race_detector_fake_lock_acquire(race_detector_fake_lock(blocksByAddr));
249         {
250           tbb::concurrent_hash_map<Address, Block*>::accessor a;
251           bool inserted = blocksByAddr.insert(a, std::make_pair(b->start(), b));
252           if(!inserted) {
253             // Inserting failed when another thread has inserted a block with the same starting address
254             return a->second;
255           } else {
256             return b;
257           }
258         }
259     }
260     void insertBlockByRange(Block* b) {
261         blocksByRange.insert(b);
262     }
263     void record_frame(ParseFrame* pf) {
264         race_detector_fake_lock_acquire(race_detector_fake_lock(frame_map));
265         {
266           tbb::concurrent_hash_map<Address, ParseFrame*>::accessor a;
267           frame_map.insert(a, make_pair(pf->func->addr(), pf));
268         }
269         race_detector_fake_lock_release(race_detector_fake_lock(frame_map));
270     }
271
272          // Find functions within [start,end)
273          int findFuncs(Address start, Address end, set<Function *> & funcs);
274     region_data(CodeObject* obj, CodeRegion* reg) {
275         Block* sink = new Block(obj, reg, numeric_limits<Address>::max());
276         blocksByAddr.insert(make_pair(sink->start(),sink));
277         blocksByRange.insert(sink);
278     }
279 };
280
281 /** region_data inlines **/
282
283 inline Function *
284 region_data::findFunc(Address entry)
285 {
286     Function *result = NULL;
287     race_detector_fake_lock_acquire(race_detector_fake_lock(funcsByAddr));
288     {
289       tbb::concurrent_hash_map<Address, Function *>::const_accessor a;
290       if(funcsByAddr.find(a, entry)) result = a->second;
291     }
292     race_detector_fake_lock_release(race_detector_fake_lock(funcsByAddr));
293     return result;
294 }
295 inline Block *
296 region_data::findBlock(Address entry)
297 {
298     Block *result = NULL;
299     race_detector_fake_lock_acquire(race_detector_fake_lock(blocksByAddr));
300     {
301       tbb::concurrent_hash_map<Address, Block *>::const_accessor a;
302       if(blocksByAddr.find(a, entry)) result = a->second;
303     }
304     race_detector_fake_lock_release(race_detector_fake_lock(blocksByAddr));
305     return result;
306 }
307 inline int
308 region_data::findFuncs(Address addr, set<Function *> & funcs)
309 {
310     int sz = funcs.size();
311
312     set<FuncExtent *> extents;
313     set<FuncExtent *>::iterator eit;
314     
315     funcsByRange.find(addr,extents);
316     for(eit = extents.begin(); eit != extents.end(); ++eit)
317         funcs.insert((*eit)->func());
318  
319     return funcs.size() - sz;
320 }
321 inline int
322 region_data::findFuncs(Address start, Address end, set<Function *> & funcs)
323 {
324          FuncExtent dummy(NULL,start,end);
325     int sz = funcs.size();
326
327     set<FuncExtent *> extents;
328     set<FuncExtent *>::iterator eit;
329     
330     funcsByRange.find(&dummy,extents);
331     for(eit = extents.begin(); eit != extents.end(); ++eit)
332         funcs.insert((*eit)->func());
333  
334     return funcs.size() - sz;
335 }
336 inline int
337 region_data::findBlocks(Address addr, set<Block *> & blocks)
338 {
339     int sz = blocks.size();
340     blocksByRange.find(addr,blocks);
341     return blocks.size() - sz;
342 }
343
344
345 /** end region_data **/
346
347 class ParseData : public boost::lockable_adapter<boost::recursive_mutex>  {
348  protected:
349     ParseData(Parser *p) : _parser(p) { }
350     Parser * _parser;
351  public:
352     virtual ~ParseData() { }
353
354     //
355     virtual Function * findFunc(CodeRegion *, Address) =0;
356     virtual Block * findBlock(CodeRegion *, Address) =0;
357     virtual int findFuncs(CodeRegion *, Address, set<Function*> &) =0;
358     virtual int findFuncs(CodeRegion *, Address, Address, set<Function*> &) =0;
359     virtual int findBlocks(CodeRegion *, Address, set<Block*> &) =0;
360     virtual ParseFrame * findFrame(CodeRegion *, Address) = 0;
361     virtual ParseFrame::Status frameStatus(CodeRegion *, Address addr) = 0;
362     virtual void setFrameStatus(CodeRegion*,Address,ParseFrame::Status) = 0;
363
364     // Atomically lookup whether there is a frame for a Function object.
365     // If there is no frame for the Function, create a new frame and record it.
366     // Return NULL if a frame already exists;
367     // Return the pointer to the new frame if a new frame is created 
368     virtual ParseFrame* createAndRecordFrame(Function*) = 0;
369
370     // creation (if non-existing)
371     virtual Function * createAndRecordFunc(CodeRegion *, Address, FuncSource) =0;
372
373     // mapping
374     virtual region_data * findRegion(CodeRegion *) =0;
375
376     // accounting
377     virtual void record_func(Function *) =0;
378     virtual Block* record_block(CodeRegion *, Block *) =0;
379     virtual void record_frame(ParseFrame *) =0;
380
381     // removal
382     virtual void remove_frame(ParseFrame *) =0;
383     virtual void remove_func(Function *) =0;
384     virtual void remove_block(Block *) =0;
385     virtual void remove_extents(const std::vector<FuncExtent*> &extents) =0;
386
387     // does the Right Thing(TM) for standard- and overlapping-region 
388     // object types
389     virtual CodeRegion * reglookup(CodeRegion *cr, Address addr) =0;
390 };
391
392 /* StandardParseData represents parse data for Parsers that disallow
393    overlapping CodeRegions. It has fast paths for lookup */
394 class StandardParseData : public ParseData {
395  private:
396     region_data _rdata;
397  public:
398     /* interface implementation */
399     StandardParseData(Parser *p);
400     ~StandardParseData();
401
402     Function * findFunc(CodeRegion * pf, Address addr);
403     Block * findBlock(CodeRegion * pf, Address addr);
404     int findFuncs(CodeRegion *, Address, set<Function*> &);
405     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
406     int findBlocks(CodeRegion *, Address, set<Block*> &);
407     ParseFrame * findFrame(CodeRegion *, Address);
408     ParseFrame::Status frameStatus(CodeRegion *, Address);
409     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
410
411     virtual ParseFrame* createAndRecordFrame(Function*);
412
413     Function * createAndRecordFunc(CodeRegion * cr, Address addr, FuncSource src);
414
415     region_data * findRegion(CodeRegion *cr);
416
417     void record_func(Function *f);
418     Block* record_block(CodeRegion *cr, Block *b);
419     void record_frame(ParseFrame *pf);
420
421     void remove_frame(ParseFrame *);
422     void remove_func(Function *);
423     void remove_block(Block *);
424     void remove_extents(const std::vector<FuncExtent*> &extents);
425
426     CodeRegion * reglookup(CodeRegion *cr, Address addr);
427 };
428
429 inline region_data * StandardParseData::findRegion(CodeRegion * /* cr */)
430 {
431     return &_rdata;
432 }
433 inline void StandardParseData::record_func(Function *f)
434 {
435     _rdata.record_func(f);
436 }
437 inline Block* StandardParseData::record_block(CodeRegion * /* cr */, Block *b)
438 {
439     return _rdata.record_block(b);
440 }
441
442 /* OverlappingParseData handles binary code objects like .o files
443    where CodeRegions may overlap on the same linear address space */
444 class OverlappingParseData : public ParseData {
445     typedef dyn_hash_map<void *, region_data *> reg_map_t;
446  private:
447     reg_map_t rmap;
448  public:
449     OverlappingParseData(Parser *p, vector<CodeRegion *> & regions);
450     ~OverlappingParseData();
451
452     /* interface implementation */
453     Function * findFunc(CodeRegion *, Address addr);
454     Block * findBlock(CodeRegion *, Address addr);
455     int findFuncs(CodeRegion *, Address, set<Function*> &);
456     int findFuncs(CodeRegion *, Address, Address, set<Function*> &);
457     int findBlocks(CodeRegion *, Address, set<Block*> &);
458     ParseFrame * findFrame(CodeRegion *, Address);
459     ParseFrame::Status frameStatus(CodeRegion *, Address);
460     void setFrameStatus(CodeRegion*,Address,ParseFrame::Status);
461
462     virtual ParseFrame* createAndRecordFrame(Function*);
463
464     Function * createAndRecordFunc(CodeRegion * cr, Address addr, FuncSource src);
465
466     region_data * findRegion(CodeRegion *cr);
467
468     void record_func(Function *f);
469     Block* record_block(CodeRegion *cr, Block *b);
470     void record_frame(ParseFrame *pf);
471
472     void remove_frame(ParseFrame *);
473     void remove_func(Function *);
474     void remove_block(Block *);
475     void remove_extents(const std::vector<FuncExtent*> &extents);
476
477     CodeRegion * reglookup(CodeRegion *cr, Address addr);
478 };
479
480 }
481 }
482
483 #endif