CFG-modification, instrumentation & springboard corner cases, defensive mode
[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 bool
187 PatchBlock::containsCall() {
188   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::CALL == (*eit)->type() ) {
192       return true;
193     }
194   }
195   return false;
196 }
197
198 bool
199 PatchBlock::containsDynamicCall() {
200   ParseAPI::Block::edgelist & out_edges = block_->targets();
201   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
202    for( ; eit != out_edges.end(); ++eit) {
203      if ( ParseAPI::CALL == (*eit)->type() ) { 
204          // see if it's a static call to a bad address
205          if ((*eit)->sinkEdge()) {
206              using namespace InstructionAPI;
207              Instruction::Ptr insn = getInsn(last());
208              if (insn->readsMemory()) { // memory indirect
209                  return true;
210              } else { // check for register indirect
211                  set<InstructionAST::Ptr> regs;
212                  Expression::Ptr tExpr = insn->getControlFlowTarget();
213                  tExpr->getUses(regs);
214                  for (set<InstructionAST::Ptr>::iterator rit = regs.begin(); 
215                       rit != regs.end(); rit++)
216                  {
217                      if (RegisterAST::makePC(obj()->co()->cs()->getArch()).getID() != 
218                          dyn_detail::boost::dynamic_pointer_cast<RegisterAST>(*rit)->getID()) 
219                      {
220                          return true;
221                      }
222                  }
223              }
224          }
225       }
226    }
227    return false;
228 }
229
230 std::string
231 PatchBlock::disassemble() const {
232   stringstream ret;
233   Insns instances;
234   getInsns(instances);
235   for (Insns::iterator iter = instances.begin();
236        iter != instances.end(); ++iter) {
237     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
238   }
239   return ret.str();
240 }
241
242 InstructionAPI::Instruction::Ptr
243 PatchBlock::getInsn(Address a) const {
244    Insns insns;
245    getInsns(insns);
246    return insns[a];
247 }
248
249 std::string
250 PatchBlock::long_format() const {
251   stringstream ret;
252   ret << format() << endl;
253   
254   Insns insns;
255   getInsns(insns);
256   
257   for (Insns::iterator iter = insns.begin(); iter != insns.end(); ++iter) {
258      ret << "\t" << hex << iter->first << " : " << iter->second->format() << dec << endl;
259   }
260   return ret.str();
261 }
262
263 std::string
264 PatchBlock::format() const {
265   stringstream ret;
266   ret << "B[" << hex << start() << "," << end() << "]" << dec;
267
268   return ret.str();
269 }
270
271 PatchFunction*
272 PatchBlock::getFunction(ParseAPI::Function* f) {
273   return obj_->getFunc(f);
274 }
275
276 ParseAPI::Block*
277 PatchBlock::block() const { return block_; }
278
279 PatchObject*
280 PatchBlock::object() const { return obj_; }
281
282 PatchFunction*
283 PatchBlock::getCallee() {
284   PatchBlock::edgelist::const_iterator it = getTargets().begin();
285   for (; it != getTargets().end(); ++it) {
286     if ((*it)->type() == ParseAPI::CALL) {
287       PatchBlock* trg = (*it)->target();
288       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
289                                                        trg->start()));
290     }
291   }
292   return NULL;
293 }
294
295 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
296    PointMakerPtr maker = obj_->addrSpace()->mgr()->pointMaker();
297    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
298    Point *ret = NULL;
299
300    switch (type) {
301       case Point::BlockEntry:
302          if (!points_.entry && create) {
303             points_.entry = maker->createPoint(loc, type);
304          }
305          return points_.entry;
306          break;
307       case Point::BlockExit:
308          if (!points_.exit && create) {
309             points_.exit = maker->createPoint(loc, type);
310          }
311          return points_.exit;
312          break;
313       case Point::BlockDuring:
314          if (!points_.during && create) {
315             points_.during = maker->createPoint(loc, type);
316          }
317          return points_.during;
318          break;
319       case Point::PreInsn: {
320          if (!loc.addr || !loc.insn) return NULL;
321          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
322          if (iter2 == points_.preInsn.end()) {
323             if (!create) return NULL;
324             ret = maker->createPoint(loc, type);
325             points_.preInsn[loc.addr] = ret;
326             return ret;
327          }
328          else {
329             return iter2->second;
330          }
331          break;
332       }
333       case Point::PostInsn: {
334          if (!loc.addr || !loc.insn) return NULL;
335          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
336          if (iter2 == points_.postInsn.end()) {
337             if (!create) return NULL;
338             ret = maker->createPoint(loc, type);
339             points_.preInsn[loc.addr] = ret;
340             return ret;
341          }
342          else return iter2->second;
343          break;
344       }
345       default:
346          return NULL;
347    }
348    assert(0); return NULL; // unreachable, but keep compiler happy
349 }
350
351
352 void PatchBlock::remove(Point *p) {
353    assert(p->block() == this);
354
355    switch(p->type()) {
356       case Point::PreInsn:
357          points_.preInsn.erase(p->addr());
358          break;
359       case Point::PostInsn:
360          points_.postInsn.erase(p->addr());
361          break;
362       case Point::BlockEntry:
363          points_.entry = NULL;
364          break;
365       case Point::BlockExit:
366          points_.exit = NULL;
367          break;
368       case Point::BlockDuring:
369          points_.during = NULL;
370          break;
371       default:
372          break;
373    }
374 }
375
376 // destroy points for this block and then each containing function's
377 // context specific points for the block
378 void PatchBlock::destroyPoints()
379 {
380     PatchCallback *cb = obj()->cb();
381     if (points_.entry) {
382         cb->destroy(points_.entry);
383         delete points_.entry;
384         points_.entry = NULL;
385     } 
386     if (points_.during) {
387         cb->destroy(points_.during);
388         delete points_.during;
389         points_.during = NULL;
390     }
391     if (points_.exit) {
392         cb->destroy(points_.exit);
393         delete points_.exit;
394         points_.exit = NULL;
395     }
396     if (!points_.preInsn.empty()) {
397         for (InsnPoints::iterator iit = points_.preInsn.begin(); 
398              iit != points_.preInsn.end(); 
399              iit++) 
400         {
401             cb->destroy(iit->second);
402             delete iit->second;
403         }
404         points_.preInsn.clear();
405     }
406     if (!points_.postInsn.empty()) {
407         for (InsnPoints::iterator iit = points_.postInsn.begin(); 
408              iit != points_.postInsn.end(); 
409              iit++) 
410         {
411             cb->destroy(iit->second);
412             delete iit->second;
413         }
414         points_.postInsn.clear();
415     }
416
417     // now destroy function's context-specific points for this block
418     vector<PatchFunction *> funcs;
419     getFunctions(back_inserter(funcs));
420     for (vector<PatchFunction *>::iterator fit = funcs.begin();
421          fit != funcs.end();
422          fit++)
423     {
424         (*fit)->destroyBlockPoints(this);
425     }
426 }
427
428 PatchCallback *PatchBlock::cb() const {
429    return obj_->cb();
430 }
431
432 void PatchBlock::splitBlock(PatchBlock *succ)
433 {
434
435    // Okay, get our edges right and stuff. 
436    // We want to modify when possible so that we keep Points on affected edges the same. 
437    // Therefore:
438    // 1) Incoming edges are unchanged. 
439    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
440    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
441    //    of our lazy block & edge creation when parseAPI added the edge)
442    // 4) We fix up Points on the block, entry and during points stay here
443
444    // 2)
445    bool hasFTEdge = false;
446    unsigned tidx= 0; 
447    while (tidx < trglist_.size()) {
448       PatchEdge *cur = trglist_[tidx];
449       if (cur->target() == succ) {
450           hasFTEdge = true;
451           tidx++;
452       } else {
453           cur->src_ = succ;
454           succ->trglist_.push_back(cur);
455           int last = trglist_.size()-1;
456           trglist_[tidx] = trglist_[last];
457           trglist_.pop_back();
458       }
459    }
460
461    // 3)
462    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
463        ParseAPI::Block::edgelist &tmp = this->block()->targets();
464        if (tmp.size() != 1) {
465           cerr << "ERROR: split block has " << tmp.size() 
466               << " edges, not 1 as expected!" << endl;
467           assert(0);
468        }
469        ParseAPI::Edge *ft = *(tmp.begin());
470        obj_->getEdge(ft, this, succ);
471    }
472
473    // 4)
474    if (points_.exit) {
475       succ->points_.exit = points_.exit;
476       points_.exit = NULL;
477       succ->points_.exit->changeBlock(succ);
478    }
479
480    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
481    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
482       tmp->second->changeBlock(succ);
483       succ->points_.preInsn[tmp->first] = tmp->second;
484    }
485    points_.preInsn.erase(pre, points_.preInsn.end());
486
487    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
488    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
489       tmp->second->changeBlock(succ);
490       succ->points_.postInsn[tmp->first] = tmp->second;
491    }
492    points_.postInsn.erase(post, points_.postInsn.end());
493
494 }
495
496 bool PatchBlock::consistency() const {
497    if (!block_) {
498       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
499       CONSIST_FAIL;
500    }
501    if (!srclist_.empty()) {
502       if (srclist_.size() != block_->sources().size()) {
503          cerr << "Error: block has inconsistent sources size" << endl;
504          CONSIST_FAIL;
505       }
506       set<PatchBlock*> srcs;
507       for (unsigned i = 0; i < srclist_.size(); ++i) {
508          // shouldn't have multiple edges to the same block unless one
509          // is a conditional taken and the other a conditional not-taken
510          // (even this is weird, but it happens in obfuscated code)
511          if (srcs.find(srclist_[i]->source()) != srcs.end() &&
512              srclist_[i]->type() != ParseAPI::COND_TAKEN && 
513              srclist_[i]->type() != ParseAPI::COND_NOT_TAKEN) 
514          {
515             cerr << "Error: multiple source edges to same block" << endl;
516             CONSIST_FAIL;
517          }
518          srcs.insert(srclist_[i]->source());
519          if (!srclist_[i]->consistency()) {
520             cerr << "Error: source edge inconsistent" << endl;
521             CONSIST_FAIL;
522          }
523       }
524    }
525    if (!trglist_.empty()) {
526       if (trglist_.size() != block_->targets().size()) {
527          cerr << "Error: block has inconsistent targets size; ParseAPI "
528               << block_->targets().size() << " and PatchAPI " 
529               << trglist_.size() << endl;
530          CONSIST_FAIL;
531       }
532       set<PatchBlock*>trgs;
533       for (unsigned i = 0; i < trglist_.size(); ++i) {
534          // shouldn't have multiple edges to the same block unless one
535          // is a conditional taken and the other a conditional not-taken
536          // (even this is weird, but it happens in obfuscated code)
537          if (trgs.find(trglist_[i]->target()) != trgs.end() &&
538              trglist_[i]->type() != ParseAPI::COND_TAKEN && 
539              trglist_[i]->type() != ParseAPI::COND_NOT_TAKEN) 
540          {
541             cerr << "Error: multiple target edges to same block" << endl;
542             CONSIST_FAIL;
543          }
544          trgs.insert(trglist_[i]->source());
545          if (!trglist_[i]->consistency()) {
546             cerr << "Error: target edge inconsistent" << endl;
547             CONSIST_FAIL;
548          }
549       }
550    }
551    if (!obj_) {
552       cerr << "Error: block has no object" << endl;
553       CONSIST_FAIL;
554    }
555    if (!points_.consistency(this, NULL)) {
556       cerr << "Error: block has inconsistent points" << endl;
557       CONSIST_FAIL;
558    }
559    return true;
560 }
561
562 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
563    if (entry) {
564       if (!entry->consistency()) CONSIST_FAIL;
565       if (entry->block() != b) CONSIST_FAIL;
566       if (entry->func() != f) CONSIST_FAIL;
567       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
568    }
569    if (during) {
570       if (!during->consistency()) CONSIST_FAIL;
571       if (during->block() != b) CONSIST_FAIL;
572       if (during->func() != f) CONSIST_FAIL;
573       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
574    }
575    if (exit) {
576       if (!exit->consistency()) CONSIST_FAIL;
577       if (exit->block() != b) CONSIST_FAIL;
578       if (exit->func() != f) CONSIST_FAIL;
579       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
580    }
581    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
582       if (!iter->second->consistency()) CONSIST_FAIL;
583       if (iter->second->block() != b) CONSIST_FAIL;
584       if (iter->second->func() != f) CONSIST_FAIL;
585       if (iter->second->addr() != iter->first) CONSIST_FAIL;
586       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
587       if (!b->getInsn(iter->first)) CONSIST_FAIL;
588    }
589    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
590       if (!iter->second->consistency()) CONSIST_FAIL;
591       if (iter->second->block() != b) CONSIST_FAIL;
592       if (iter->second->func() != f) CONSIST_FAIL;
593       if (iter->second->addr() != iter->first) CONSIST_FAIL;
594       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
595       if (!b->getInsn(iter->first)) CONSIST_FAIL;
596    }
597    return true;
598 }
599