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