Revert "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 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
289    PointMaker* maker = obj_->addrSpace()->mgr()->pointMaker();
290    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
291    Point *ret = NULL;
292
293    switch (type) {
294       case Point::BlockEntry:
295          if (!points_.entry && create) {
296             points_.entry = maker->createPoint(loc, type);
297          }
298          return points_.entry;
299          break;
300       case Point::BlockExit:
301          if (!points_.exit && create) {
302             points_.exit = maker->createPoint(loc, type);
303          }
304          return points_.exit;
305          break;
306       case Point::BlockDuring:
307          if (!points_.during && create) {
308             points_.during = maker->createPoint(loc, type);
309          }
310          return points_.during;
311          break;
312       case Point::PreInsn: {
313          if (!loc.addr || !loc.insn) return NULL;
314          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
315          if (iter2 == points_.preInsn.end()) {
316             if (!create) return NULL;
317             ret = maker->createPoint(loc, type);
318             points_.preInsn[loc.addr] = ret;
319             return ret;
320          }
321          else {
322             return iter2->second;
323          }
324          break;
325       }
326       case Point::PostInsn: {
327          if (!loc.addr || !loc.insn) return NULL;
328          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
329          if (iter2 == points_.postInsn.end()) {
330             if (!create) return NULL;
331             ret = maker->createPoint(loc, type);
332             points_.preInsn[loc.addr] = ret;
333             return ret;
334          }
335          else return iter2->second;
336          break;
337       }
338       default:
339          return NULL;
340    }
341    assert(0); return NULL; // unreachable, but keep compiler happy
342 }
343
344
345 void PatchBlock::remove(Point *p) {
346    assert(p->block() == this);
347
348    switch(p->type()) {
349       case Point::PreInsn:
350          points_.preInsn.erase(p->addr());
351          break;
352       case Point::PostInsn:
353          points_.postInsn.erase(p->addr());
354          break;
355       case Point::BlockEntry:
356          points_.entry = NULL;
357          break;
358       case Point::BlockExit:
359          points_.exit = NULL;
360          break;
361       case Point::BlockDuring:
362          points_.during = NULL;
363          break;
364       default:
365          break;
366    }
367 }
368
369 // destroy points for this block and then each containing function's
370 // context specific points for the block
371 void PatchBlock::destroyPoints()
372 {
373     PatchCallback *cb = obj()->cb();
374     if (points_.entry) {
375         cb->destroy(points_.entry);
376         delete points_.entry;
377         points_.entry = NULL;
378     } 
379     if (points_.during) {
380         cb->destroy(points_.during);
381         delete points_.during;
382         points_.during = NULL;
383     }
384     if (points_.exit) {
385         cb->destroy(points_.exit);
386         delete points_.exit;
387         points_.exit = NULL;
388     }
389     if (!points_.preInsn.empty()) {
390         for (InsnPoints::iterator iit = points_.preInsn.begin(); 
391              iit != points_.preInsn.end(); 
392              iit++) 
393         {
394             cb->destroy(iit->second);
395             delete iit->second;
396         }
397         points_.preInsn.clear();
398     }
399     if (!points_.postInsn.empty()) {
400         for (InsnPoints::iterator iit = points_.postInsn.begin(); 
401              iit != points_.postInsn.end(); 
402              iit++) 
403         {
404             cb->destroy(iit->second);
405             delete iit->second;
406         }
407         points_.postInsn.clear();
408     }
409
410     // now destroy function's context-specific points for this block
411     vector<PatchFunction *> funcs;
412     getFunctions(back_inserter(funcs));
413     for (vector<PatchFunction *>::iterator fit = funcs.begin();
414          fit != funcs.end();
415          fit++)
416     {
417         (*fit)->destroyBlockPoints(this);
418     }
419 }
420
421 PatchCallback *PatchBlock::cb() const {
422    return obj_->cb();
423 }
424
425 void PatchBlock::splitBlock(PatchBlock *succ)
426 {
427
428    // Okay, get our edges right and stuff. 
429    // We want to modify when possible so that we keep Points on affected edges the same. 
430    // Therefore:
431    // 1) Incoming edges are unchanged. 
432    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
433    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
434    //    of our lazy block & edge creation when parseAPI added the edge)
435    // 4) We fix up Points on the block, entry and during points stay here
436
437    // 2)
438    bool hasFTEdge = false;
439    unsigned tidx= 0; 
440    while (tidx < trglist_.size()) {
441       PatchEdge *cur = trglist_[tidx];
442       if (cur->target() == succ) {
443           hasFTEdge = true;
444           tidx++;
445       } else {
446           cur->src_ = succ;
447           succ->trglist_.push_back(cur);
448           int last = trglist_.size()-1;
449           trglist_[tidx] = trglist_[last];
450           trglist_.pop_back();
451       }
452    }
453
454    // 3)
455    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
456        ParseAPI::Block::edgelist &tmp = this->block()->targets();
457        if (tmp.size() != 1) {
458           cerr << "ERROR: split block has " << tmp.size() 
459               << " edges, not 1 as expected!" << endl;
460           assert(0);
461        }
462        ParseAPI::Edge *ft = *(tmp.begin());
463        obj_->getEdge(ft, this, succ);
464    }
465
466    // 4)
467    if (points_.exit) {
468       succ->points_.exit = points_.exit;
469       points_.exit = NULL;
470       succ->points_.exit->changeBlock(succ);
471    }
472
473    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
474    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
475       tmp->second->changeBlock(succ);
476       succ->points_.preInsn[tmp->first] = tmp->second;
477    }
478    points_.preInsn.erase(pre, points_.preInsn.end());
479
480    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
481    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
482       tmp->second->changeBlock(succ);
483       succ->points_.postInsn[tmp->first] = tmp->second;
484    }
485    points_.postInsn.erase(post, points_.postInsn.end());
486
487 }
488
489 bool PatchBlock::consistency() const {
490    if (!block_) {
491       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
492       CONSIST_FAIL;
493    }
494    if (!srclist_.empty()) {
495       if (srclist_.size() != block_->sources().size()) {
496          cerr << "Error: block has inconsistent sources size" << endl;
497          CONSIST_FAIL;
498       }
499       for (unsigned i = 0; i < srclist_.size(); ++i) {
500          if (!srclist_[i]->consistency()) {
501             cerr << "Error: source edge inconsistent" << endl;
502             CONSIST_FAIL;
503          }
504       }
505    }
506    if (!trglist_.empty()) {
507       if (trglist_.size() != block_->targets().size()) {
508          cerr << "Error: block has inconsistent targets size; ParseAPI "
509               << block_->targets().size() << " and PatchAPI " 
510               << trglist_.size() << endl;
511          CONSIST_FAIL;
512       }
513       for (unsigned i = 0; i < trglist_.size(); ++i) {
514          if (!trglist_[i]->consistency()) {
515             cerr << "Error: target edge inconsistent" << endl;
516             CONSIST_FAIL;
517          }
518       }
519    }
520    if (!obj_) {
521       cerr << "Error: block has no object" << endl;
522       CONSIST_FAIL;
523    }
524    if (!points_.consistency(this, NULL)) {
525       cerr << "Error: block has inconsistent points" << endl;
526       CONSIST_FAIL;
527    }
528    return true;
529 }
530
531 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
532    if (entry) {
533       if (!entry->consistency()) CONSIST_FAIL;
534       if (entry->block() != b) CONSIST_FAIL;
535       if (entry->func() != f) CONSIST_FAIL;
536       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
537    }
538    if (during) {
539       if (!during->consistency()) CONSIST_FAIL;
540       if (during->block() != b) CONSIST_FAIL;
541       if (during->func() != f) CONSIST_FAIL;
542       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
543    }
544    if (exit) {
545       if (!exit->consistency()) CONSIST_FAIL;
546       if (exit->block() != b) CONSIST_FAIL;
547       if (exit->func() != f) CONSIST_FAIL;
548       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
549    }
550    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
551       if (!iter->second->consistency()) CONSIST_FAIL;
552       if (iter->second->block() != b) CONSIST_FAIL;
553       if (iter->second->func() != f) CONSIST_FAIL;
554       if (iter->second->addr() != iter->first) CONSIST_FAIL;
555       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
556       if (!b->getInsn(iter->first)) CONSIST_FAIL;
557    }
558    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
559       if (!iter->second->consistency()) CONSIST_FAIL;
560       if (iter->second->block() != b) CONSIST_FAIL;
561       if (iter->second->func() != f) CONSIST_FAIL;
562       if (iter->second->addr() != iter->first) CONSIST_FAIL;
563       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
564       if (!b->getInsn(iter->first)) CONSIST_FAIL;
565    }
566    return true;
567 }
568