Merge branch 'master' into NewInstpoint
[dyninst.git] / parseAPI / h / CFG.h
1 /*
2  * Copyright (c) 1996-2011 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 _PARSER_CFG_H_
32 #define _PARSER_CFG_H_
33
34 #include <vector>
35 #include <set>
36 #include <map>
37 #include <string>
38
39 #include "dyntypes.h"
40 #include "IBSTree.h"
41
42 #include "InstructionSource.h"
43 #include "ParseContainers.h"
44
45 #include "Annotatable.h"
46 #include <iostream>
47 namespace Dyninst {
48 namespace ParseAPI {
49
50 enum EdgeTypeEnum {
51     CALL = 0,
52     COND_TAKEN,
53     COND_NOT_TAKEN,
54     INDIRECT,
55     DIRECT,
56     FALLTHROUGH,
57     CATCH,
58     CALL_FT,        // fallthrough after call instruction
59     RET,
60     NOEDGE,
61     _edgetype_end_
62 };
63
64 std::string format(EdgeTypeEnum e);
65
66 #define FLIST_BADNEXT ((void*)0x111)
67 #define FLIST_BADPREV ((void*)0x222)
68
69 /*
70  * All CFG objects extend allocatable, which
71  * allows them to be added and removed from
72  * accounting structures in constant time
73  */
74 class allocatable {
75  public:
76     allocatable() :
77        anext_((allocatable*)FLIST_BADNEXT),
78        aprev_((allocatable*)FLIST_BADPREV)
79     { }
80     allocatable * anext_;
81     allocatable * aprev_;
82
83     inline allocatable * alloc_next() const { return anext_; }
84     inline allocatable * alloc_prev() const { return aprev_; }
85     inline void alloc_set_next(allocatable *t) { anext_ = t; }
86     inline void alloc_set_prev(allocatable *t) { aprev_ = t; }
87
88     void remove() {
89         if(anext_ != (allocatable*)FLIST_BADNEXT)
90             anext_->aprev_ = aprev_;
91         if(aprev_ != (allocatable*)FLIST_BADPREV)
92             aprev_->anext_ = anext_;
93
94         anext_ = (allocatable*)FLIST_BADNEXT;
95         aprev_ = (allocatable*)FLIST_BADPREV;
96     }
97
98     void append(allocatable & new_elem) {
99         if(anext_ == (allocatable*)FLIST_BADNEXT ||
100            aprev_ == (allocatable*)FLIST_BADPREV)
101         {
102             fprintf(stderr,
103                 "allocatable::append called on element not on list: %p\n",this);
104             return;
105         }
106         anext_->aprev_ = &new_elem;
107         new_elem.anext_ = anext_;
108         new_elem.aprev_ = this;
109         anext_ = &new_elem;
110     }
111
112     void prepend(allocatable & new_elem) {
113         if(anext_ == (allocatable*)FLIST_BADNEXT ||
114            aprev_ == (allocatable*)FLIST_BADPREV)
115         {
116             fprintf(stderr,
117                "allocatable::prepend called on element not on list: %p\n",this);
118             return;
119         }
120         aprev_->anext_ = &new_elem;
121         new_elem.aprev_ = aprev_;
122         new_elem.anext_ = this;
123         aprev_ = &new_elem;
124     }
125 };
126
127 class Block;
128 class Edge : public allocatable {
129  protected:
130     Block * _source;
131     Block * _target;
132
133  private:
134
135 #if defined(_MSC_VER)
136         typedef unsigned __int16 uint16_t;
137         typedef unsigned __int8 uint8_t;
138 #else
139         typedef unsigned short uint16_t;
140         typedef unsigned char uint8_t;
141 #endif
142
143     struct EdgeType {
144         EdgeType(EdgeTypeEnum t, bool s) :
145             _type_enum(t), _sink(s), _interproc(false)
146         { }
147         uint16_t _type_enum;
148         uint8_t _sink;
149         uint8_t  _interproc;    // modifier for interprocedural branches
150                                 // (tail calls)
151     };
152     EdgeType _type;
153
154  public:
155     PARSER_EXPORT Edge(Block * source,
156          Block * target,
157          EdgeTypeEnum type);
158      PARSER_EXPORT virtual ~Edge();
159
160     PARSER_EXPORT virtual Block * src() const { return _source; }
161     PARSER_EXPORT virtual Block * trg() const { return _target; }
162     PARSER_EXPORT EdgeTypeEnum type() const { 
163         return static_cast<EdgeTypeEnum>(_type._type_enum); 
164     }
165     bool sinkEdge() const { return _type._sink != 0; }
166     bool interproc() const { 
167        return (_type._interproc != 0 ||
168                type() == CALL ||
169                type() == RET);
170     }
171
172     PARSER_EXPORT void install();
173
174     /* removes from blocks & finalized source functions if of type CALL */
175     PARSER_EXPORT void uninstall();
176
177
178  friend class CFGFactory;
179  friend class Parser;
180 };
181
182 /* 
183  * Iteration over edges can be controlled by an EdgePredicate.
184  * Edges are returned only if pred(edge) evaluates true.
185  * 
186  * EdgePredicates are composable by AND.
187  */
188 class EdgePredicate 
189     : public iterator_predicate<
190         EdgePredicate,
191         Edge *,
192         Edge *
193       >
194 {
195  protected:
196     EdgePredicate * _next; 
197  public:
198     PARSER_EXPORT EdgePredicate() : _next(NULL) { }
199     PARSER_EXPORT EdgePredicate(EdgePredicate * next) : _next(next) { }
200     PARSER_EXPORT virtual ~EdgePredicate() { }
201     PARSER_EXPORT virtual bool pred_impl(Edge *) const;
202 };
203
204 /* may follow branches into the function if there is shared code */
205 class Intraproc : public EdgePredicate {
206  public:
207     PARSER_EXPORT Intraproc() { }
208     PARSER_EXPORT Intraproc(EdgePredicate * next) : EdgePredicate(next) { }
209     PARSER_EXPORT ~Intraproc() { }
210     PARSER_EXPORT bool pred_impl(Edge *) const;
211 };
212
213 /* follow interprocedural edges */
214 class Interproc : public EdgePredicate {
215     public:
216         PARSER_EXPORT Interproc() {}
217         PARSER_EXPORT Interproc(EdgePredicate * next) : EdgePredicate(next) { }
218         PARSER_EXPORT ~Interproc() { }
219         PARSER_EXPORT bool pred_impl(Edge *) const;
220 };
221
222 /*
223  * For proper ostritch-like denial of 
224  * unresolved control flow edges
225  */
226 class NoSinkPredicate : public ParseAPI::EdgePredicate {
227  public:
228     NoSinkPredicate() { }
229     NoSinkPredicate(EdgePredicate * next)
230         : EdgePredicate(next) 
231     { } 
232
233     bool pred_impl(ParseAPI::Edge * e) const {
234         return !e->sinkEdge() && EdgePredicate::pred_impl(e);
235     }
236 };
237
238 /* doesn't follow branches into the function if there is shared code */
239 class Function;
240 class SingleContext : public EdgePredicate {
241  private:
242     Function * _context;
243     bool _forward;
244     bool _backward;
245  public:
246     PARSER_EXPORT SingleContext(Function * f, bool forward, bool backward) : 
247         _context(f),
248         _forward(forward),
249         _backward(backward) { }
250     PARSER_EXPORT ~SingleContext() { }
251     PARSER_EXPORT bool pred_impl(Edge *) const;
252 };
253
254 /* Doesn't follow branches into the function if there is shared code. 
255  * Will follow interprocedural call/return edges */
256 class SingleContextOrInterproc : public EdgePredicate {
257     private:
258         Function * _context;
259         bool _forward;
260         bool _backward;
261     public:
262         PARSER_EXPORT SingleContextOrInterproc(Function * f, bool forward, bool backward) :
263             _context(f),
264             _forward(forward),
265             _backward(backward) { }
266         PARSER_EXPORT ~SingleContextOrInterproc() { }
267         PARSER_EXPORT bool pred_impl(Edge *) const;
268 };
269
270 class CodeObject;
271 class CodeRegion;
272 class Block : public Dyninst::interval<Address>, 
273               public allocatable {
274  public:
275     typedef ContainerWrapper<
276         std::vector<Edge*>,
277         Edge*,
278         Edge*,
279         EdgePredicate
280     > edgelist;
281
282     PARSER_EXPORT Block(CodeObject * o, CodeRegion * r, Address start);
283     PARSER_EXPORT virtual ~Block();
284
285     PARSER_EXPORT Address start() const { return _start; }
286     PARSER_EXPORT Address end() const { return _end; }
287     PARSER_EXPORT Address lastInsnAddr() const { return _lastInsn; } 
288     PARSER_EXPORT Address size() const { return _end - _start; }
289
290     PARSER_EXPORT bool parsed() const { return _parsed; }
291
292     PARSER_EXPORT CodeObject * obj() const { return _obj; }
293     PARSER_EXPORT CodeRegion * region() const { return _region; }
294
295     /* Edge access */
296     PARSER_EXPORT edgelist & sources() { return _srclist; }
297     PARSER_EXPORT edgelist & targets() { return _trglist; }
298
299     PARSER_EXPORT bool consistent(Address addr, Address & prev_insn);
300
301     PARSER_EXPORT int  containingFuncs() const;
302     PARSER_EXPORT void getFuncs(std::vector<Function *> & funcs);
303
304     /* interval implementation */
305     Address low() const { return start(); }
306     Address high() const { return end(); }
307
308     struct compare {
309         bool operator()(Block * const & b1, Block * const & b2) const {
310             if(b1->start() < b2->start()) return true;
311             if(b1->start() > b2->start()) return false;
312             
313             // XXX debugging
314             if(b1 != b2)
315                 fprintf(stderr,"FATAL: blocks %p [%lx,%lx) and %p [%lx,%lx) "
316                             "conflict",b1,b1->start(),b1->end(),
317                             b2,b2->start(),b2->end());
318
319             assert(b1 == b2);
320             return false;
321         }
322     };
323
324  private:
325     void addSource(Edge * e);
326     void addTarget(Edge * e);
327     void removeTarget(Edge * e);
328     void removeSource(Edge * e);
329     void removeFunc(Function *);
330
331  private:
332     CodeObject * _obj;
333     CodeRegion * _region;
334
335     Address _start;
336     Address _end;
337     Address _lastInsn;
338
339     std::vector<Edge *> _sources;
340     std::vector<Edge *> _targets;
341
342     edgelist _srclist;
343     edgelist _trglist;
344     int _func_cnt;
345     bool _parsed;
346
347  friend class Edge;
348  friend class Function;
349  friend class Parser;
350  friend class CFGFactory;
351 };
352
353 inline void Block::addSource(Edge * e) 
354 {
355     _sources.push_back(e);
356 }
357
358 inline void Block::addTarget(Edge * e)
359 {
360     _targets.push_back(e);
361 }
362
363 inline void Block::removeTarget(Edge * e)
364 {
365     for(unsigned i=0;i<_targets.size();++i) {
366         if(_targets[i] == e) {
367             _targets[i] = _targets.back();
368             _targets.pop_back();    
369             break;
370         }
371     }
372 }
373
374 inline void Block::removeSource(Edge * e) {
375     for(unsigned i=0;i<_sources.size();++i) {
376         if(_sources[i] == e) {
377             _sources[i] = _sources.back();
378             _sources.pop_back();    
379             break;
380         }
381     }
382 }
383
384 enum FuncReturnStatus {
385     UNSET,
386     NORETURN,
387     UNKNOWN,
388     RETURN
389 };
390
391 /* Discovery method of functions */
392 enum FuncSource {
393     RT = 0,     // recursive traversal (default)
394     HINT,       // specified in code object hints
395     GAP,        // gap heuristics
396     GAPRT,      // RT from gap-discovered function
397     ONDEMAND,   // dynamically discovered
398     _funcsource_end_
399 };
400
401 enum StackTamper {
402     TAMPER_UNSET,
403     TAMPER_NONE,
404     TAMPER_REL,
405     TAMPER_ABS,
406     TAMPER_NONZERO
407 };
408
409 class CodeObject;
410 class CodeRegion;
411 class FuncExtent;
412 class Function : public allocatable, public AnnotatableSparse {
413  protected:
414     Address _start;
415     CodeObject * _obj;
416     CodeRegion * _region;
417     InstructionSource * _isrc;
418     
419     FuncSource _src;
420     FuncReturnStatus _rs;
421
422     std::string _name;
423     Block * _entry;
424  protected:
425     PARSER_EXPORT Function(); 
426  public:
427     bool _is_leaf_function;
428     Address _ret_addr; // return address of a function stored in stack at function entry
429     typedef ContainerWrapper<
430         std::vector<Block*>,
431         Block*,
432         Block*
433     > blocklist;
434     typedef ContainerWrapper<
435         std::set<Edge*>,
436         Edge*,
437         Edge*
438     > edgelist;
439
440     PARSER_EXPORT Function(Address addr, string name, CodeObject * obj, 
441         CodeRegion * region, InstructionSource * isource);
442
443     PARSER_EXPORT virtual ~Function();
444     PARSER_EXPORT virtual const string & name();
445
446     PARSER_EXPORT Address addr() const { return _start; }
447     PARSER_EXPORT CodeRegion * region() const { return _region; }
448     PARSER_EXPORT InstructionSource * isrc() const { return _isrc; }
449     PARSER_EXPORT CodeObject * obj() const { return _obj; }
450     PARSER_EXPORT FuncSource src() const { return _src; }
451     PARSER_EXPORT FuncReturnStatus retstatus() const { return _rs; }
452     PARSER_EXPORT Block * entry() const { return _entry; }
453     PARSER_EXPORT bool parsed() const { return _parsed; }
454
455     /* Basic block and CFG access */
456     PARSER_EXPORT blocklist & blocks();
457     PARSER_EXPORT bool contains(Block *b);
458     PARSER_EXPORT edgelist & callEdges();
459     PARSER_EXPORT blocklist & returnBlocks();
460
461     /* Function details */
462     PARSER_EXPORT bool hasNoStackFrame() const { return _no_stack_frame; }
463     PARSER_EXPORT bool savesFramePointer() const { return _saves_fp; }
464     PARSER_EXPORT bool cleansOwnStack() const { return _cleans_stack; }
465
466     /* Parse updates and obfuscation */
467     PARSER_EXPORT void setEntryBlock(Block *new_entry);
468     PARSER_EXPORT void set_retstatus(FuncReturnStatus rs) { _rs = rs; }
469     PARSER_EXPORT void deleteBlocks( vector<Block*> dead_blocks );
470     PARSER_EXPORT StackTamper tampersStack(bool recalculate=false);
471
472     struct less
473     {
474         bool operator()(const Function * f1, const Function * f2) const
475         {
476             return f1->addr() < f2->addr();
477         }
478     };
479
480     /* Contiguous code segments of function */
481     PARSER_EXPORT std::vector<FuncExtent *> const& extents();
482
483     /* This should not remain here - this is an experimental fix for
484        defensive mode CFG inconsistency */
485     void invalidateCache() { _cache_valid = false; }
486
487  private:
488     std::vector<Block *> const& blocks_int();
489     void delayed_link_return(CodeObject * co, Block * retblk);
490     void finalize();
491
492     bool _parsed;
493     bool _cache_valid;
494     blocklist _bl;
495     std::vector<Block *> _blocks;
496     std::vector<FuncExtent *> _extents;
497
498     /* rapid lookup for edge predicate tests */
499     //typedef dyn_hash_map<Address, Block*> blockmap;
500     typedef std::map<Address, Block*> blockmap;
501     blockmap _bmap;
502
503     /* rapid lookup for interprocedural queries */
504     std::set<Edge *> _call_edges;
505     edgelist _call_edge_list;
506     std::vector<Block *> _return_blocks;
507     blocklist _retBL;
508
509
510     /* function details */
511     bool _no_stack_frame;
512     bool _saves_fp;
513     bool _cleans_stack;
514     StackTamper _tamper;
515     Address _tamper_addr;
516
517     /*** Internal parsing methods and state ***/
518     void add_block(Block *b);
519
520     friend void Edge::uninstall();
521     friend class Parser;
522     friend class CFGFactory;
523     friend class CodeObject;
524 };
525
526 /* Describes a contiguous extent of a Function object */
527 class FuncExtent : public Dyninst::interval<Address> {
528  private:
529     Function * _func;
530     Address _start;
531     Address _end;
532
533  public:
534     FuncExtent(Function * f, Address start, Address end) :
535         _func(f),
536         _start(start),
537         _end(end) { }
538
539     ~FuncExtent() {
540         _func = NULL;
541     }
542
543     PARSER_EXPORT Function * func() { return _func; }
544
545     PARSER_EXPORT Address start() const { return _start; }
546     PARSER_EXPORT Address end() const { return _end; }
547
548     /* interval implementation */
549     PARSER_EXPORT Address low() const { return _start; }
550     PARSER_EXPORT Address high() const { return _end; } 
551 };
552
553
554 } //namespace ParseAPI
555 } //namespace Dyninst
556
557 #endif