After tested under windows.
[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 PARSER_EXPORT 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     PARSER_EXPORT static void destroy(Edge *);
178
179  friend class CFGFactory;
180  friend class Parser;
181 };
182
183 /* 
184  * Iteration over edges can be controlled by an EdgePredicate.
185  * Edges are returned only if pred(edge) evaluates true.
186  * 
187  * EdgePredicates are composable by AND.
188  */
189 class EdgePredicate 
190     : public iterator_predicate<
191         EdgePredicate,
192         Edge *,
193         Edge *
194       >
195 {
196  protected:
197     EdgePredicate * _next; 
198  public:
199     PARSER_EXPORT EdgePredicate() : _next(NULL) { }
200     PARSER_EXPORT EdgePredicate(EdgePredicate * next) : _next(next) { }
201     PARSER_EXPORT virtual ~EdgePredicate() { }
202     PARSER_EXPORT virtual bool pred_impl(Edge *) const;
203 };
204
205 /* may follow branches into the function if there is shared code */
206 class Intraproc : public EdgePredicate {
207  public:
208     PARSER_EXPORT Intraproc() { }
209     PARSER_EXPORT Intraproc(EdgePredicate * next) : EdgePredicate(next) { }
210     PARSER_EXPORT ~Intraproc() { }
211     PARSER_EXPORT bool pred_impl(Edge *) const;
212 };
213
214 /* follow interprocedural edges */
215 class Interproc : public EdgePredicate {
216     public:
217         PARSER_EXPORT Interproc() {}
218         PARSER_EXPORT Interproc(EdgePredicate * next) : EdgePredicate(next) { }
219         PARSER_EXPORT ~Interproc() { }
220         PARSER_EXPORT bool pred_impl(Edge *) const;
221 };
222
223 /*
224  * For proper ostritch-like denial of 
225  * unresolved control flow edges
226  */
227 class NoSinkPredicate : public ParseAPI::EdgePredicate {
228  public:
229     NoSinkPredicate() { }
230     NoSinkPredicate(EdgePredicate * next)
231         : EdgePredicate(next) 
232     { } 
233
234     bool pred_impl(ParseAPI::Edge * e) const {
235         return !e->sinkEdge() && EdgePredicate::pred_impl(e);
236     }
237 };
238
239 /* doesn't follow branches into the function if there is shared code */
240 class Function;
241 class SingleContext : public EdgePredicate {
242  private:
243     Function * _context;
244     bool _forward;
245     bool _backward;
246  public:
247     PARSER_EXPORT SingleContext(Function * f, bool forward, bool backward) : 
248         _context(f),
249         _forward(forward),
250         _backward(backward) { }
251     PARSER_EXPORT ~SingleContext() { }
252     PARSER_EXPORT bool pred_impl(Edge *) const;
253 };
254
255 /* Doesn't follow branches into the function if there is shared code. 
256  * Will follow interprocedural call/return edges */
257 class SingleContextOrInterproc : public EdgePredicate {
258     private:
259         Function * _context;
260         bool _forward;
261         bool _backward;
262     public:
263         PARSER_EXPORT SingleContextOrInterproc(Function * f, bool forward, bool backward) :
264             _context(f),
265             _forward(forward),
266             _backward(backward) { }
267         PARSER_EXPORT ~SingleContextOrInterproc() { }
268         PARSER_EXPORT bool pred_impl(Edge *) const;
269 };
270
271 class CodeObject;
272 class CodeRegion;
273 class Block : public Dyninst::interval<Address>, 
274               public allocatable {
275  public:
276     typedef ContainerWrapper<
277         std::vector<Edge*>,
278         Edge*,
279         Edge*,
280         EdgePredicate
281     > edgelist;
282
283     PARSER_EXPORT Block(CodeObject * o, CodeRegion * r, Address start);
284     PARSER_EXPORT virtual ~Block();
285
286     PARSER_EXPORT Address start() const { return _start; }
287     PARSER_EXPORT Address end() const { return _end; }
288     PARSER_EXPORT Address lastInsnAddr() const { return _lastInsn; } 
289     PARSER_EXPORT Address size() const { return _end - _start; }
290
291     PARSER_EXPORT bool parsed() const { return _parsed; }
292
293     PARSER_EXPORT CodeObject * obj() const { return _obj; }
294     PARSER_EXPORT CodeRegion * region() const { return _region; }
295
296     /* Edge access */
297     PARSER_EXPORT edgelist & sources() { return _srclist; }
298     PARSER_EXPORT edgelist & targets() { return _trglist; }
299
300     PARSER_EXPORT bool consistent(Address addr, Address & prev_insn);
301
302     PARSER_EXPORT int  containingFuncs() const;
303     PARSER_EXPORT void getFuncs(std::vector<Function *> & funcs);
304
305     /* interval implementation */
306     Address low() const { return start(); }
307     Address high() const { return end(); }
308
309     struct compare {
310         bool operator()(Block * const & b1, Block * const & b2) const {
311             if(b1->start() < b2->start()) return true;
312             if(b1->start() > b2->start()) return false;
313             
314             // XXX debugging
315             if(b1 != b2)
316                 fprintf(stderr,"FATAL: blocks %p [%lx,%lx) and %p [%lx,%lx) "
317                             "conflict",b1,b1->start(),b1->end(),
318                             b2,b2->start(),b2->end());
319
320             assert(b1 == b2);
321             return false;
322         }
323     };
324
325     static void destroy(Block *b);
326
327  private:
328     void addSource(Edge * e);
329     void addTarget(Edge * e);
330     void removeTarget(Edge * e);
331     void removeSource(Edge * e);
332     void removeFunc(Function *);
333
334  private:
335     CodeObject * _obj;
336     CodeRegion * _region;
337
338     Address _start;
339     Address _end;
340     Address _lastInsn;
341
342     std::vector<Edge *> _sources;
343     std::vector<Edge *> _targets;
344
345     edgelist _srclist;
346     edgelist _trglist;
347     int _func_cnt;
348     bool _parsed;
349
350  friend class Edge;
351  friend class Function;
352  friend class Parser;
353  friend class CFGFactory;
354 };
355
356 inline void Block::addSource(Edge * e) 
357 {
358     _sources.push_back(e);
359 }
360
361 inline void Block::addTarget(Edge * e)
362 {
363     _targets.push_back(e);
364 }
365
366 inline void Block::removeTarget(Edge * e)
367 {
368     for(unsigned i=0;i<_targets.size();++i) {
369         if(_targets[i] == e) {
370             _targets[i] = _targets.back();
371             _targets.pop_back();    
372             break;
373         }
374     }
375 }
376
377 inline void Block::removeSource(Edge * e) {
378     for(unsigned i=0;i<_sources.size();++i) {
379         if(_sources[i] == e) {
380             _sources[i] = _sources.back();
381             _sources.pop_back();    
382             break;
383         }
384     }
385 }
386
387 enum FuncReturnStatus {
388     UNSET,
389     NORETURN,
390     UNKNOWN,
391     RETURN
392 };
393
394 /* Discovery method of functions */
395 enum FuncSource {
396     RT = 0,     // recursive traversal (default)
397     HINT,       // specified in code object hints
398     GAP,        // gap heuristics
399     GAPRT,      // RT from gap-discovered function
400     ONDEMAND,   // dynamically discovered
401     _funcsource_end_
402 };
403
404 enum StackTamper {
405     TAMPER_UNSET,
406     TAMPER_NONE,
407     TAMPER_REL,
408     TAMPER_ABS,
409     TAMPER_NONZERO
410 };
411
412 class CodeObject;
413 class CodeRegion;
414 class FuncExtent;
415 class Function : public allocatable, public AnnotatableSparse {
416  protected:
417     Address _start;
418     CodeObject * _obj;
419     CodeRegion * _region;
420     InstructionSource * _isrc;
421     
422     FuncSource _src;
423     FuncReturnStatus _rs;
424
425     std::string _name;
426     Block * _entry;
427  protected:
428     PARSER_EXPORT Function(); 
429  public:
430     bool _is_leaf_function;
431     Address _ret_addr; // return address of a function stored in stack at function entry
432     typedef ContainerWrapper<
433         std::vector<Block*>,
434         Block*,
435         Block*
436     > blocklist;
437     typedef ContainerWrapper<
438         std::set<Edge*>,
439         Edge*,
440         Edge*
441     > edgelist;
442
443     PARSER_EXPORT Function(Address addr, string name, CodeObject * obj, 
444         CodeRegion * region, InstructionSource * isource);
445
446     PARSER_EXPORT virtual ~Function();
447
448     PARSER_EXPORT virtual const string & name();
449
450     PARSER_EXPORT Address addr() const { return _start; }
451     PARSER_EXPORT CodeRegion * region() const { return _region; }
452     PARSER_EXPORT InstructionSource * isrc() const { return _isrc; }
453     PARSER_EXPORT CodeObject * obj() const { return _obj; }
454     PARSER_EXPORT FuncSource src() const { return _src; }
455     PARSER_EXPORT FuncReturnStatus retstatus() const { return _rs; }
456     PARSER_EXPORT Block * entry() const { return _entry; }
457     PARSER_EXPORT bool parsed() const { return _parsed; }
458
459     /* Basic block and CFG access */
460     PARSER_EXPORT blocklist & blocks();
461     PARSER_EXPORT bool contains(Block *b);
462     PARSER_EXPORT edgelist & callEdges();
463     PARSER_EXPORT blocklist & returnBlocks();
464
465     /* Function details */
466     PARSER_EXPORT bool hasNoStackFrame() const { return _no_stack_frame; }
467     PARSER_EXPORT bool savesFramePointer() const { return _saves_fp; }
468     PARSER_EXPORT bool cleansOwnStack() const { return _cleans_stack; }
469
470     /* Parse updates and obfuscation */
471     PARSER_EXPORT void setEntryBlock(Block *new_entry);
472     PARSER_EXPORT void set_retstatus(FuncReturnStatus rs) { _rs = rs; }
473
474     // Dangerous and should not be used
475     //PARSER_EXPORT void deleteBlocks( vector<Block*> dead_blocks );
476
477     PARSER_EXPORT StackTamper tampersStack(bool recalculate=false);
478
479     struct less
480     {
481         bool operator()(const Function * f1, const Function * f2) const
482         {
483             return f1->addr() < f2->addr();
484         }
485     };
486
487     /* Contiguous code segments of function */
488     PARSER_EXPORT std::vector<FuncExtent *> const& extents();
489
490     /* This should not remain here - this is an experimental fix for
491        defensive mode CFG inconsistency */
492     void invalidateCache() { _cache_valid = false; }
493
494     static void destroy(Function *f);
495
496  private:
497     std::vector<Block *> const& blocks_int();
498     void delayed_link_return(CodeObject * co, Block * retblk);
499     void finalize();
500
501     bool _parsed;
502     bool _cache_valid;
503     blocklist _bl;
504     std::vector<Block *> _blocks;
505     std::vector<FuncExtent *> _extents;
506
507     /* rapid lookup for edge predicate tests */
508     //typedef dyn_hash_map<Address, Block*> blockmap;
509     typedef std::map<Address, Block*> blockmap;
510     blockmap _bmap;
511
512     /* rapid lookup for interprocedural queries */
513     std::set<Edge *> _call_edges;
514     edgelist _call_edge_list;
515     std::vector<Block *> _return_blocks;
516     blocklist _retBL;
517
518
519     /* function details */
520     bool _no_stack_frame;
521     bool _saves_fp;
522     bool _cleans_stack;
523     StackTamper _tamper;
524     Address _tamper_addr;
525
526     /*** Internal parsing methods and state ***/
527     void add_block(Block *b);
528
529     friend void Edge::uninstall();
530     friend class Parser;
531     friend class CFGFactory;
532     friend class CodeObject;
533 };
534
535 /* Describes a contiguous extent of a Function object */
536 class FuncExtent : public Dyninst::interval<Address> {
537  private:
538     Function * _func;
539     Address _start;
540     Address _end;
541
542  public:
543     FuncExtent(Function * f, Address start, Address end) :
544         _func(f),
545         _start(start),
546         _end(end) { }
547
548     ~FuncExtent() {
549         _func = NULL;
550     }
551
552     PARSER_EXPORT Function * func() { return _func; }
553
554     PARSER_EXPORT Address start() const { return _start; }
555     PARSER_EXPORT Address end() const { return _end; }
556
557     /* interval implementation */
558     PARSER_EXPORT Address low() const { return _start; }
559     PARSER_EXPORT Address high() const { return _end; } 
560 };
561
562
563 } //namespace ParseAPI
564 } //namespace Dyninst
565
566 #endif