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