block & function removal and relocation fixes
[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::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 // destroy points for this block and then each containing function's
359 // context specific points for the block
360 void PatchBlock::destroyPoints()
361 {
362     PatchCallback *cb = obj()->cb();
363     if (points_.entry) {
364         cb->destroy(points_.entry);
365         delete points_.entry;
366         points_.entry = NULL;
367     } 
368     if (points_.during) {
369         cb->destroy(points_.during);
370         delete points_.during;
371         points_.during = NULL;
372     }
373     if (points_.exit) {
374         cb->destroy(points_.exit);
375         delete points_.exit;
376         points_.exit = NULL;
377     }
378     if (!points_.preInsn.empty()) {
379         for (InsnPoints::iterator iit = points_.preInsn.begin(); 
380              iit != points_.preInsn.end(); 
381              iit++) 
382         {
383             cb->destroy(iit->second);
384             delete iit->second;
385         }
386         points_.preInsn.clear();
387     }
388     if (!points_.postInsn.empty()) {
389         for (InsnPoints::iterator iit = points_.postInsn.begin(); 
390              iit != points_.postInsn.end(); 
391              iit++) 
392         {
393             cb->destroy(iit->second);
394             delete iit->second;
395         }
396         points_.postInsn.clear();
397     }
398
399     // now destroy function's context-specific points for this block
400     vector<PatchFunction *> funcs;
401     getFunctions(back_inserter(funcs));
402     for (vector<PatchFunction *>::iterator fit = funcs.begin();
403          fit != funcs.end();
404          fit++)
405     {
406         (*fit)->destroyBlockPoints(this);
407     }
408 }
409
410 PatchCallback *PatchBlock::cb() const {
411    return obj_->cb();
412 }
413
414 void PatchBlock::splitBlock(PatchBlock *succ)
415 {
416
417    // Okay, get our edges right and stuff. 
418    // We want to modify when possible so that we keep Points on affected edges the same. 
419    // Therefore:
420    // 1) Incoming edges are unchanged. 
421    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
422    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
423    //    of our lazy block & edge creation when parseAPI added the edge)
424    // 4) We fix up Points on the block, entry and during points stay here
425
426    // 2)
427    bool hasFTEdge = false;
428    unsigned tidx= 0; 
429    while (tidx < trglist_.size()) {
430       PatchEdge *cur = trglist_[tidx];
431       if (cur->target() == succ) {
432           hasFTEdge = true;
433           tidx++;
434       } else {
435           cur->src_ = succ;
436           succ->trglist_.push_back(cur);
437           int last = trglist_.size()-1;
438           trglist_[tidx] = trglist_[last];
439           trglist_.pop_back();
440       }
441    }
442
443    // 3)
444    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
445        ParseAPI::Block::edgelist &tmp = this->block()->targets();
446        if (tmp.size() != 1) {
447           cerr << "ERROR: split block has " << tmp.size() 
448               << " edges, not 1 as expected!" << endl;
449           assert(0);
450        }
451        ParseAPI::Edge *ft = *(tmp.begin());
452        obj_->getEdge(ft, this, succ);
453    }
454
455    // 4)
456    if (points_.exit) {
457       succ->points_.exit = points_.exit;
458       points_.exit = NULL;
459       succ->points_.exit->changeBlock(succ);
460    }
461
462    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
463    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
464       tmp->second->changeBlock(succ);
465       succ->points_.preInsn[tmp->first] = tmp->second;
466    }
467    points_.preInsn.erase(pre, points_.preInsn.end());
468
469    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
470    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
471       tmp->second->changeBlock(succ);
472       succ->points_.postInsn[tmp->first] = tmp->second;
473    }
474    points_.postInsn.erase(post, points_.postInsn.end());
475
476 }
477
478 bool PatchBlock::consistency() const {
479    if (!block_) {
480       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
481       CONSIST_FAIL;
482    }
483    if (!srclist_.empty()) {
484       if (srclist_.size() != block_->sources().size()) {
485          cerr << "Error: block has inconsistent sources size" << endl;
486          CONSIST_FAIL;
487       }
488       for (unsigned i = 0; i < srclist_.size(); ++i) {
489          if (!srclist_[i]->consistency()) {
490             cerr << "Error: source edge inconsistent" << endl;
491             CONSIST_FAIL;
492          }
493       }
494    }
495    if (!trglist_.empty()) {
496       if (trglist_.size() != block_->targets().size()) {
497          cerr << "Error: block has inconsistent targets size; ParseAPI "
498               << block_->targets().size() << " and PatchAPI " 
499               << trglist_.size() << endl;
500          CONSIST_FAIL;
501       }
502       for (unsigned i = 0; i < trglist_.size(); ++i) {
503          if (!trglist_[i]->consistency()) {
504             cerr << "Error: target edge inconsistent" << endl;
505             CONSIST_FAIL;
506          }
507       }
508    }
509    if (!obj_) {
510       cerr << "Error: block has no object" << endl;
511       CONSIST_FAIL;
512    }
513    if (!points_.consistency(this, NULL)) {
514       cerr << "Error: block has inconsistent points" << endl;
515       CONSIST_FAIL;
516    }
517    return true;
518 }
519
520 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
521    if (entry) {
522       if (!entry->consistency()) CONSIST_FAIL;
523       if (entry->block() != b) CONSIST_FAIL;
524       if (entry->func() != f) CONSIST_FAIL;
525       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
526    }
527    if (during) {
528       if (!during->consistency()) CONSIST_FAIL;
529       if (during->block() != b) CONSIST_FAIL;
530       if (during->func() != f) CONSIST_FAIL;
531       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
532    }
533    if (exit) {
534       if (!exit->consistency()) CONSIST_FAIL;
535       if (exit->block() != b) CONSIST_FAIL;
536       if (exit->func() != f) CONSIST_FAIL;
537       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
538    }
539    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
540       if (!iter->second->consistency()) CONSIST_FAIL;
541       if (iter->second->block() != b) CONSIST_FAIL;
542       if (iter->second->func() != f) CONSIST_FAIL;
543       if (iter->second->addr() != iter->first) CONSIST_FAIL;
544       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
545       if (!b->getInsn(iter->first)) CONSIST_FAIL;
546    }
547    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
548       if (!iter->second->consistency()) CONSIST_FAIL;
549       if (iter->second->block() != b) CONSIST_FAIL;
550       if (iter->second->func() != f) CONSIST_FAIL;
551       if (iter->second->addr() != iter->first) CONSIST_FAIL;
552       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
553       if (!b->getInsn(iter->first)) CONSIST_FAIL;
554    }
555    return true;
556 }
557