Merge branch 'liveness' into master_copy
[dyninst.git] / patchAPI / src / PatchBlock.C
1 /* Public Interface */
2
3 #include "common.h"
4 #include "PatchCFG.h"
5 #include "AddrSpace.h"
6 #include "PatchObject.h"
7 #include "PatchMgr.h"
8 #include "PatchCallback.h"
9 #include "Point.h"
10 #include <dyn_detail/boost/shared_ptr.hpp>
11
12 using namespace Dyninst;
13 using namespace PatchAPI;
14 using namespace InstructionAPI;
15
16 PatchBlock*
17 PatchBlock::create(ParseAPI::Block *ib, PatchFunction *f) {
18   return f->obj()->getBlock(ib);
19 }
20
21 PatchBlock::PatchBlock(ParseAPI::Block *blk, PatchObject *obj)
22   : block_(blk),   obj_(obj) {
23 }
24
25 PatchBlock::PatchBlock(const PatchBlock *parent, PatchObject *child)
26   : block_(parent->block_), obj_(child) {
27 }
28
29 void
30 PatchBlock::getInsns(Insns &insns) const {
31   // Pass through to ParseAPI. They don't have a native interface, so add one.
32   Offset off = block_->start();
33   const unsigned char *ptr =
34     (const unsigned char *)block_->region()->getPtrToInstruction(off);
35   if (ptr == NULL) return;
36   InstructionDecoder d(ptr, size(), block_->obj()->cs()->getArch());
37   while (off < block_->end()) {
38     Instruction::Ptr insn = d.decode();
39     insns[off + obj_->codeBase()] = insn;
40     off += insn->size();
41   }
42 }
43
44 const PatchBlock::edgelist&
45 PatchBlock::getSources() {
46   if (srclist_.empty()) {
47     for (ParseAPI::Block::edgelist::iterator iter = block_->sources().begin();
48          iter != block_->sources().end(); ++iter) {
49       PatchEdge *newEdge = obj_->getEdge(*iter, NULL, this);
50       srclist_.push_back(newEdge);
51     }
52   }
53   return srclist_;
54 }
55
56 const PatchBlock::edgelist&
57 PatchBlock::getTargets() {
58   if (trglist_.empty()) {
59     for (ParseAPI::Block::edgelist::iterator iter = block_->targets().begin();
60          iter != block_->targets().end(); ++iter) {
61       PatchEdge *newEdge = obj_->getEdge(*iter, this, NULL);
62       assert(newEdge);
63       trglist_.push_back(newEdge);
64     }
65   }
66   return trglist_;
67 }
68
69 PatchEdge *PatchBlock::findSource(ParseAPI::EdgeTypeEnum type) {
70    getSources();
71    for (edgelist::iterator iter = srclist_.begin();
72         iter != srclist_.end(); ++iter) {
73       if ((*iter)->type() == type) return *iter;
74    }
75    return NULL;
76 }
77
78 PatchEdge *PatchBlock::findTarget(ParseAPI::EdgeTypeEnum type) {
79    getTargets();
80    for (edgelist::iterator iter = trglist_.begin();
81         iter != trglist_.end(); ++iter) {
82       assert(*iter);
83       assert((*iter)->edge());
84       cerr << "Looking for " << ParseAPI::format(type) << ", found edge with " << ParseAPI::format((*iter)->type()) << endl;
85       if ((*iter)->type() == type) return *iter;
86    }
87    return NULL;
88 }
89
90 void PatchBlock::addSourceEdge(PatchEdge *e, bool addIfEmpty) {
91    if (!addIfEmpty && srclist_.empty()) return;
92
93    srclist_.push_back(e);
94
95   cb()->add_edge(this, e, PatchCallback::source);
96 }
97
98 void PatchBlock::addTargetEdge(PatchEdge *e, bool addIfEmpty) {
99    assert(e);
100    if (!addIfEmpty && trglist_.empty()) return;
101
102    trglist_.push_back(e);
103    
104    cb()->add_edge(this, e, PatchCallback::target);
105 }
106
107
108 void
109 PatchBlock::removeSourceEdge(PatchEdge *e) {
110    if (srclist_.empty()) return;
111
112   std::vector<PatchEdge *>::iterator iter;
113   if ((iter = std::find(srclist_.begin(), srclist_.end(), e)) != srclist_.end()) {
114     srclist_.erase(iter);
115   }
116
117   cb()->remove_edge(this, e, PatchCallback::source);
118 }
119
120 void
121 PatchBlock::removeTargetEdge(PatchEdge *e) {
122    if (trglist_.empty()) return;
123
124   std::vector<PatchEdge *>::iterator iter;
125   if ((iter = std::find(trglist_.begin(), trglist_.end(), e)) != trglist_.end()) {
126      cerr << "Erasing target edge" << endl;
127     trglist_.erase(iter);
128   }
129   cb()->remove_edge(this, e, PatchCallback::target);
130 }
131
132
133 bool
134 PatchBlock::isShared() {
135   return containingFuncs() > 1;
136 }
137
138 PatchBlock::~PatchBlock() {
139 #if 0
140    // Our predecessor may be deleted...
141   for (std::vector<PatchEdge *>::iterator iter = srclist_.begin();
142        iter != srclist_.end(); ++iter) {
143     PatchBlock* blk = (*iter)->source();
144     blk->removeTargetEdge(*iter);
145   }
146   for (std::vector<PatchEdge *>::iterator iter = trglist_.begin();
147        iter != trglist_.end(); ++iter) {
148     PatchBlock* blk = (*iter)->target();
149     blk->removeSourceEdge(*iter);
150   }
151 #endif
152 }
153
154 Address
155 PatchBlock::start() const {
156   return object()->codeBase() + block_->start();
157 }
158
159 Address
160 PatchBlock::end() const {
161   return object()->codeBase() + block_->end();
162 }
163
164 Address
165 PatchBlock::last() const {
166   return object()->codeBase() + block_->lastInsnAddr();
167 }
168
169 Address
170 PatchBlock::size() const {
171   return block_->size();
172 }
173
174 int
175 PatchBlock::containingFuncs() const {
176   return block_->containingFuncs();
177 }
178
179 bool
180 PatchBlock::containsCall() {
181   ParseAPI::Block::edgelist & out_edges = block_->targets();
182   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
183   for( ; eit != out_edges.end(); ++eit) {
184     if ( ParseAPI::CALL == (*eit)->type() ) {
185       return true;
186     }
187   }
188   return false;
189 }
190
191 bool
192 PatchBlock::containsDynamicCall() {
193   ParseAPI::Block::edgelist & out_edges = block_->targets();
194   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
195    for( ; eit != out_edges.end(); ++eit) {
196      if ( ParseAPI::CALL == (*eit)->type() ) { 
197          // see if it's a static call to a bad address
198          if ((*eit)->sinkEdge()) {
199              using namespace InstructionAPI;
200              Instruction::Ptr insn = getInsn(last());
201              if (insn->readsMemory()) { // memory indirect
202                  return true;
203              } else { // check for register indirect
204                  set<InstructionAST::Ptr> regs;
205                  Expression::Ptr tExpr = insn->getControlFlowTarget();
206                  tExpr->getUses(regs);
207                  for (set<InstructionAST::Ptr>::iterator rit = regs.begin(); 
208                       rit != regs.end(); rit++)
209                  {
210                      if (RegisterAST::makePC(obj()->co()->cs()->getArch()).getID() != 
211                          dyn_detail::boost::dynamic_pointer_cast<RegisterAST>(*rit)->getID()) 
212                      {
213                          return true;
214                      }
215                  }
216              }
217          }
218       }
219    }
220    return false;
221 }
222
223 std::string
224 PatchBlock::disassemble() const {
225   stringstream ret;
226   Insns instances;
227   getInsns(instances);
228   for (Insns::iterator iter = instances.begin();
229        iter != instances.end(); ++iter) {
230     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
231   }
232   return ret.str();
233 }
234
235 InstructionAPI::Instruction::Ptr
236 PatchBlock::getInsn(Address a) const {
237    Insns insns;
238    getInsns(insns);
239    return insns[a];
240 }
241
242 std::string
243 PatchBlock::long_format() const {
244   stringstream ret;
245   ret << format() << endl;
246   
247   Insns insns;
248   getInsns(insns);
249   
250   for (Insns::iterator iter = insns.begin(); iter != insns.end(); ++iter) {
251      ret << "\t" << hex << iter->first << " : " << iter->second->format() << dec << endl;
252   }
253   return ret.str();
254 }
255
256 std::string
257 PatchBlock::format() const {
258   stringstream ret;
259   ret << "B[" << hex << start() << "," << end() << "]" << dec;
260
261   return ret.str();
262 }
263
264 PatchFunction*
265 PatchBlock::getFunction(ParseAPI::Function* f) {
266   return obj_->getFunc(f);
267 }
268
269 ParseAPI::Block*
270 PatchBlock::block() const { return block_; }
271
272 PatchObject*
273 PatchBlock::object() const { return obj_; }
274
275 PatchFunction*
276 PatchBlock::getCallee() {
277   PatchBlock::edgelist::const_iterator it = getTargets().begin();
278   for (; it != getTargets().end(); ++it) {
279     if ((*it)->type() == ParseAPI::CALL) {
280       PatchBlock* trg = (*it)->target();
281       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
282                                                        trg->block()->start()));
283     }
284   }
285   return NULL;
286 }
287
288
289 Point *PatchBlock::findPoint(PatchLocation loc, Point::Type type, bool create) {
290    PointMaker* maker = obj_->addrSpace()->mgr()->pointMaker();
291
292    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
293    Point *ret = NULL;
294
295    switch (type) {
296       case Point::BlockEntry:
297          if (!points_.entry && create) {
298             points_.entry = maker->createPoint(loc, type);
299          }
300          return points_.entry;
301          break;
302       case Point::BlockExit:
303          if (!points_.exit && create) {
304             points_.exit = maker->createPoint(loc, type);
305          }
306          return points_.exit;
307          break;
308       case Point::BlockDuring:
309          if (!points_.during && create) {
310             points_.during = maker->createPoint(loc, type);
311          }
312          return points_.during;
313          break;
314       case Point::PreInsn: {
315          if (!loc.addr || !loc.insn) return NULL;
316          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
317          if (iter2 == points_.preInsn.end()) {
318             if (!create) return NULL;
319             ret = maker->createPoint(loc, type);
320             points_.preInsn[loc.addr] = ret;
321             return ret;
322          }
323          else {
324             return iter2->second;
325          }
326          break;
327       }
328       case Point::PostInsn: {
329          if (!loc.addr || !loc.insn) return NULL;
330          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
331          if (iter2 == points_.postInsn.end()) {
332             if (!create) return NULL;
333             ret = maker->createPoint(loc, type);
334             points_.preInsn[loc.addr] = ret;
335             return ret;
336          }
337          else return iter2->second;
338          break;
339       }
340       default:
341          return NULL;
342    }
343    assert(0); return NULL; // unreachable, but keep compiler happy
344 }
345
346
347 void PatchBlock::remove(Point *p) {
348    assert(p->block() == this);
349
350    switch(p->type()) {
351       case Point::PreInsn:
352          points_.preInsn.erase(p->addr());
353          break;
354       case Point::PostInsn:
355          points_.postInsn.erase(p->addr());
356          break;
357       case Point::BlockEntry:
358          points_.entry = NULL;
359          break;
360       case Point::BlockExit:
361          points_.exit = NULL;
362          break;
363       case Point::BlockDuring:
364          points_.during = NULL;
365          break;
366       default:
367          break;
368    }
369 }
370
371 // destroy points for this block and then each containing function's
372 // context specific points for the block
373 void PatchBlock::destroyPoints()
374 {
375     PatchCallback *cb = obj()->cb();
376     if (points_.entry) {
377         cb->destroy(points_.entry);
378         delete points_.entry;
379         points_.entry = NULL;
380     } 
381     if (points_.during) {
382         cb->destroy(points_.during);
383         delete points_.during;
384         points_.during = NULL;
385     }
386     if (points_.exit) {
387         cb->destroy(points_.exit);
388         delete points_.exit;
389         points_.exit = NULL;
390     }
391     if (!points_.preInsn.empty()) {
392         for (InsnPoints::iterator iit = points_.preInsn.begin(); 
393              iit != points_.preInsn.end(); 
394              iit++) 
395         {
396             cb->destroy(iit->second);
397             delete iit->second;
398         }
399         points_.preInsn.clear();
400     }
401     if (!points_.postInsn.empty()) {
402         for (InsnPoints::iterator iit = points_.postInsn.begin(); 
403              iit != points_.postInsn.end(); 
404              iit++) 
405         {
406             cb->destroy(iit->second);
407             delete iit->second;
408         }
409         points_.postInsn.clear();
410     }
411
412     // now destroy function's context-specific points for this block
413     vector<PatchFunction *> funcs;
414     getFunctions(back_inserter(funcs));
415     for (vector<PatchFunction *>::iterator fit = funcs.begin();
416          fit != funcs.end();
417          fit++)
418     {
419         (*fit)->destroyBlockPoints(this);
420     }
421 }
422
423 PatchCallback *PatchBlock::cb() const {
424    return obj_->cb();
425 }
426
427 void PatchBlock::splitBlock(PatchBlock *succ)
428 {
429
430    // Okay, get our edges right and stuff. 
431    // We want to modify when possible so that we keep Points on affected edges the same. 
432    // Therefore:
433    // 1) Incoming edges are unchanged. 
434    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
435    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
436    //    of our lazy block & edge creation when parseAPI added the edge)
437    // 4) We fix up Points on the block, entry and during points stay here
438
439    // 2)
440    bool hasFTEdge = false;
441    unsigned tidx= 0; 
442    while (tidx < trglist_.size()) {
443       PatchEdge *cur = trglist_[tidx];
444       if (cur->target() == succ) {
445           hasFTEdge = true;
446           tidx++;
447       } else {
448           cur->src_ = succ;
449           succ->trglist_.push_back(cur);
450           int last = trglist_.size()-1;
451           trglist_[tidx] = trglist_[last];
452           trglist_.pop_back();
453       }
454    }
455
456    // 3)
457    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
458        ParseAPI::Block::edgelist &tmp = this->block()->targets();
459        if (tmp.size() != 1) {
460           cerr << "ERROR: split block has " << tmp.size() 
461               << " edges, not 1 as expected!" << endl;
462           assert(0);
463        }
464        ParseAPI::Edge *ft = *(tmp.begin());
465        obj_->getEdge(ft, this, succ);
466    }
467
468    // 4)
469    if (points_.exit) {
470       succ->points_.exit = points_.exit;
471       points_.exit = NULL;
472       succ->points_.exit->changeBlock(succ);
473    }
474
475    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
476    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
477       tmp->second->changeBlock(succ);
478       succ->points_.preInsn[tmp->first] = tmp->second;
479    }
480    points_.preInsn.erase(pre, points_.preInsn.end());
481
482    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
483    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
484       tmp->second->changeBlock(succ);
485       succ->points_.postInsn[tmp->first] = tmp->second;
486    }
487    points_.postInsn.erase(post, points_.postInsn.end());
488
489 }
490
491 bool PatchBlock::consistency() const {
492    if (!block_) {
493       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
494       CONSIST_FAIL;
495    }
496    if (!srclist_.empty()) {
497       if (srclist_.size() != block_->sources().size()) {
498          cerr << "Error: block has inconsistent sources size" << endl;
499          CONSIST_FAIL;
500       }
501       for (unsigned i = 0; i < srclist_.size(); ++i) {
502          if (!srclist_[i]->consistency()) {
503             cerr << "Error: source edge inconsistent" << endl;
504             CONSIST_FAIL;
505          }
506       }
507    }
508    if (!trglist_.empty()) {
509       if (trglist_.size() != block_->targets().size()) {
510          cerr << "Error: block has inconsistent targets size; ParseAPI "
511               << block_->targets().size() << " and PatchAPI " 
512               << trglist_.size() << endl;
513          CONSIST_FAIL;
514       }
515       for (unsigned i = 0; i < trglist_.size(); ++i) {
516          if (!trglist_[i]->consistency()) {
517             cerr << "Error: target edge inconsistent" << endl;
518             CONSIST_FAIL;
519          }
520       }
521    }
522    if (!obj_) {
523       cerr << "Error: block has no object" << endl;
524       CONSIST_FAIL;
525    }
526    if (!points_.consistency(this, NULL)) {
527       cerr << "Error: block has inconsistent points" << endl;
528       CONSIST_FAIL;
529    }
530    return true;
531 }
532
533 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
534    if (entry) {
535       if (!entry->consistency()) CONSIST_FAIL;
536       if (entry->block() != b) CONSIST_FAIL;
537       if (entry->func() != f) CONSIST_FAIL;
538       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
539    }
540    if (during) {
541       if (!during->consistency()) CONSIST_FAIL;
542       if (during->block() != b) CONSIST_FAIL;
543       if (during->func() != f) CONSIST_FAIL;
544       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
545    }
546    if (exit) {
547       if (!exit->consistency()) CONSIST_FAIL;
548       if (exit->block() != b) CONSIST_FAIL;
549       if (exit->func() != f) CONSIST_FAIL;
550       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
551    }
552    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
553       if (!iter->second->consistency()) CONSIST_FAIL;
554       if (iter->second->block() != b) CONSIST_FAIL;
555       if (iter->second->func() != f) CONSIST_FAIL;
556       if (iter->second->addr() != iter->first) CONSIST_FAIL;
557       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
558       if (!b->getInsn(iter->first)) CONSIST_FAIL;
559    }
560    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
561       if (!iter->second->consistency()) CONSIST_FAIL;
562       if (iter->second->block() != b) CONSIST_FAIL;
563       if (iter->second->func() != f) CONSIST_FAIL;
564       if (iter->second->addr() != iter->first) CONSIST_FAIL;
565       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
566       if (!b->getInsn(iter->first)) CONSIST_FAIL;
567    }
568    return true;
569 }
570