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