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