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