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