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