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