function & block removal
[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->object()->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::format() const {
244   stringstream ret;
245   ret << "BB["
246       << hex << start()
247       << ","
248       << end() << dec
249       << "]" << endl;
250   return ret.str();
251 }
252
253 PatchFunction*
254 PatchBlock::getFunction(ParseAPI::Function* f) {
255   return obj_->getFunc(f);
256 }
257
258 ParseAPI::Block*
259 PatchBlock::block() const { return block_; }
260
261 PatchObject*
262 PatchBlock::object() const { return obj_; }
263
264 PatchFunction*
265 PatchBlock::getCallee() {
266   PatchBlock::edgelist::const_iterator it = getTargets().begin();
267   for (; it != getTargets().end(); ++it) {
268     if ((*it)->type() == ParseAPI::CALL) {
269       PatchBlock* trg = (*it)->target();
270       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
271                                                        trg->start()));
272     }
273   }
274   return NULL;
275 }
276
277 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
278    PointMakerPtr maker = obj_->addrSpace()->mgr()->pointMaker();
279    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
280    Point *ret = NULL;
281
282    switch (type) {
283       case Point::BlockEntry:
284          if (!points_.entry && create) {
285             points_.entry = maker->createPoint(loc, type);
286          }
287          return points_.entry;
288          break;
289       case Point::BlockExit:
290          if (!points_.exit && create) {
291             points_.exit = maker->createPoint(loc, type);
292          }
293          return points_.exit;
294          break;
295       case Point::BlockDuring:
296          if (!points_.during && create) {
297             points_.during = maker->createPoint(loc, type);
298          }
299          return points_.during;
300          break;
301       case Point::PreInsn: {
302          if (!loc.addr || !loc.insn) return NULL;
303          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
304          if (iter2 == points_.preInsn.end()) {
305             if (!create) return NULL;
306             ret = maker->createPoint(loc, type);
307             points_.preInsn[loc.addr] = ret;
308             return ret;
309          }
310          else {
311             return iter2->second;
312          }
313          break;
314       }
315       case Point::PostInsn: {
316          if (!loc.addr || !loc.insn) return NULL;
317          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
318          if (iter2 == points_.postInsn.end()) {
319             if (!create) return NULL;
320             ret = maker->createPoint(loc, type);
321             points_.preInsn[loc.addr] = ret;
322             return ret;
323          }
324          else return iter2->second;
325          break;
326       }
327       default:
328          return NULL;
329    }
330    assert(0); return NULL; // unreachable, but keep compiler happy
331 }
332
333
334 void PatchBlock::remove(Point *p) {
335    assert(p->block() == this);
336
337    switch(p->type()) {
338       case Point::PreInsn:
339          points_.preInsn.erase(p->addr());
340          break;
341       case Point::PostInsn:
342          points_.postInsn.erase(p->addr());
343          break;
344       case Point::BlockEntry:
345          points_.entry = NULL;
346          break;
347       case Point::BlockExit:
348          points_.exit = NULL;
349          break;
350       case Point::BlockDuring:
351          points_.during = NULL;
352          break;
353       default:
354          break;
355    }
356 }
357
358 PatchCallback *PatchBlock::cb() const {
359    return obj_->cb();
360 }
361
362 void PatchBlock::splitBlock(PatchBlock *succ)
363 {
364
365    // Okay, get our edges right and stuff. 
366    // We want to modify when possible so that we keep Points on affected edges the same. 
367    // Therefore:
368    // 1) Incoming edges are unchanged. 
369    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
370    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
371    //    of our lazy block & edge creation when parseAPI added the edge)
372    // 4) We fix up Points on the block, entry and during points stay here
373
374    // 2)
375    bool hasFTEdge = false;
376    unsigned tidx= 0; 
377    while (tidx < trglist_.size()) {
378       PatchEdge *cur = trglist_[tidx];
379       if (cur->target() == succ) {
380           hasFTEdge = true;
381           tidx++;
382       } else {
383           cur->src_ = succ;
384           succ->trglist_.push_back(cur);
385           int last = trglist_.size()-1;
386           trglist_[tidx] = trglist_[last];
387           trglist_.pop_back();
388       }
389    }
390
391    // 3)
392    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
393        ParseAPI::Block::edgelist &tmp = this->block()->targets();
394        if (tmp.size() != 1) {
395           cerr << "ERROR: split block has " << tmp.size() 
396               << " edges, not 1 as expected!" << endl;
397           assert(0);
398        }
399        ParseAPI::Edge *ft = *(tmp.begin());
400        obj_->getEdge(ft, this, succ);
401    }
402
403    // 4)
404    if (points_.exit) {
405       succ->points_.exit = points_.exit;
406       points_.exit = NULL;
407       succ->points_.exit->changeBlock(succ);
408    }
409
410    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
411    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
412       tmp->second->changeBlock(succ);
413       succ->points_.preInsn[tmp->first] = tmp->second;
414    }
415    points_.preInsn.erase(pre, points_.preInsn.end());
416
417    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
418    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
419       tmp->second->changeBlock(succ);
420       succ->points_.postInsn[tmp->first] = tmp->second;
421    }
422    points_.postInsn.erase(post, points_.postInsn.end());
423
424 }
425
426 bool PatchBlock::consistency() const {
427    if (!block_) {
428       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
429       CONSIST_FAIL;
430    }
431    if (!srclist_.empty()) {
432       if (srclist_.size() != block_->sources().size()) {
433          cerr << "Error: block has inconsistent sources size" << endl;
434          CONSIST_FAIL;
435       }
436       for (unsigned i = 0; i < srclist_.size(); ++i) {
437          if (!srclist_[i]->consistency()) {
438             cerr << "Error: source edge inconsistent" << endl;
439             CONSIST_FAIL;
440          }
441       }
442    }
443    if (!trglist_.empty()) {
444       if (trglist_.size() != block_->targets().size()) {
445          cerr << "Error: block has inconsistent targets size; ParseAPI "
446               << block_->targets().size() << " and PatchAPI " 
447               << trglist_.size() << endl;
448          CONSIST_FAIL;
449       }
450       for (unsigned i = 0; i < trglist_.size(); ++i) {
451          if (!trglist_[i]->consistency()) {
452             cerr << "Error: target edge inconsistent" << endl;
453             CONSIST_FAIL;
454          }
455       }
456    }
457    if (!obj_) {
458       cerr << "Error: block has no object" << endl;
459       CONSIST_FAIL;
460    }
461    if (!points_.consistency(this, NULL)) {
462       cerr << "Error: block has inconsistent points" << endl;
463       CONSIST_FAIL;
464    }
465    return true;
466 }
467
468 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
469    if (entry) {
470       if (!entry->consistency()) CONSIST_FAIL;
471       if (entry->block() != b) CONSIST_FAIL;
472       if (entry->func() != f) CONSIST_FAIL;
473       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
474    }
475    if (during) {
476       if (!during->consistency()) CONSIST_FAIL;
477       if (during->block() != b) CONSIST_FAIL;
478       if (during->func() != f) CONSIST_FAIL;
479       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
480    }
481    if (exit) {
482       if (!exit->consistency()) CONSIST_FAIL;
483       if (exit->block() != b) CONSIST_FAIL;
484       if (exit->func() != f) CONSIST_FAIL;
485       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
486    }
487    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
488       if (!iter->second->consistency()) CONSIST_FAIL;
489       if (iter->second->block() != b) CONSIST_FAIL;
490       if (iter->second->func() != f) CONSIST_FAIL;
491       if (iter->second->addr() != iter->first) CONSIST_FAIL;
492       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
493       if (!b->getInsn(iter->first)) CONSIST_FAIL;
494    }
495    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
496       if (!iter->second->consistency()) CONSIST_FAIL;
497       if (iter->second->block() != b) CONSIST_FAIL;
498       if (iter->second->func() != f) CONSIST_FAIL;
499       if (iter->second->addr() != iter->first) CONSIST_FAIL;
500       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
501       if (!b->getInsn(iter->first)) CONSIST_FAIL;
502    }
503    return true;
504 }
505