PatchObject function, block, edge accessor now creates them; replace BPatch_addressSp...
[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                  tExpr->getUses(regs);
253                  for (set<InstructionAST::Ptr>::iterator rit = regs.begin(); 
254                       rit != regs.end(); rit++)
255                  {
256                      if (RegisterAST::makePC(obj()->co()->cs()->getArch()).getID() != 
257                          boost::dynamic_pointer_cast<RegisterAST>(*rit)->getID()) 
258                      {
259                          return true;
260                      }
261                  }
262              }
263          }
264       }
265    }
266    return false;
267 }
268
269 std::string
270 PatchBlock::disassemble() const {
271   stringstream ret;
272   Insns instances;
273   getInsns(instances);
274   for (Insns::iterator iter = instances.begin();
275        iter != instances.end(); ++iter) {
276     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
277   }
278   return ret.str();
279 }
280
281 InstructionAPI::Instruction::Ptr
282 PatchBlock::getInsn(Address a) const {
283    Insns insns;
284    getInsns(insns);
285    return insns[a];
286 }
287
288 std::string
289 PatchBlock::long_format() const {
290   stringstream ret;
291   ret << format() << endl;
292   
293   Insns insns;
294   getInsns(insns);
295   
296   for (Insns::iterator iter = insns.begin(); iter != insns.end(); ++iter) {
297      ret << "\t" << hex << iter->first << " : " << iter->second->format() << dec << endl;
298   }
299   return ret.str();
300 }
301
302 std::string
303 PatchBlock::format() const {
304   stringstream ret;
305   ret << "B[" << hex << start() << "," << end() << "]" << dec;
306
307   return ret.str();
308 }
309
310 PatchFunction*
311 PatchBlock::getFunction(ParseAPI::Function* f) {
312   return obj_->getFunc(f);
313 }
314
315 ParseAPI::Block*
316 PatchBlock::block() const { return block_; }
317
318 PatchObject*
319 PatchBlock::object() const { return obj_; }
320
321 PatchFunction*
322 PatchBlock::getCallee() {
323    PatchBlock::edgelist::const_iterator it = targets().begin();
324    for (; it != targets().end(); ++it) {
325     if ((*it)->type() == ParseAPI::CALL) {
326       PatchBlock* trg = (*it)->trg();
327       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
328                                                        trg->block()->start()));
329     }
330   }
331   return NULL;
332 }
333
334 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
335    PointMaker* maker = obj_->addrSpace()->mgr()->pointMaker();
336    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
337    Point *ret = NULL;
338
339    switch (type) {
340       case Point::BlockEntry:
341          if (!points_.entry && create) {
342             points_.entry = maker->createPoint(loc, type);
343          }
344          return points_.entry;
345          break;
346       case Point::BlockExit:
347          if (!points_.exit && create) {
348             points_.exit = maker->createPoint(loc, type);
349          }
350          return points_.exit;
351          break;
352       case Point::BlockDuring:
353          if (!points_.during && create) {
354             points_.during = maker->createPoint(loc, type);
355          }
356          return points_.during;
357          break;
358       case Point::PreInsn: {
359          if (!loc.addr || !loc.insn) return NULL;
360          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
361          if (iter2 == points_.preInsn.end()) {
362             if (!create) return NULL;
363             ret = maker->createPoint(loc, type);
364             points_.preInsn[loc.addr] = ret;
365             return ret;
366          }
367          else {
368             return iter2->second;
369          }
370          break;
371       }
372       case Point::PostInsn: {
373          if (!loc.addr || !loc.insn) return NULL;
374          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
375          if (iter2 == points_.postInsn.end()) {
376             if (!create) return NULL;
377             ret = maker->createPoint(loc, type);
378             points_.preInsn[loc.addr] = ret;
379             return ret;
380          }
381          else return iter2->second;
382          break;
383       }
384       default:
385          return NULL;
386    }
387    assert(0); return NULL; // unreachable, but keep compiler happy
388 }
389
390
391 void PatchBlock::remove(Point *p) {
392    assert(p->block() == this);
393
394    switch(p->type()) {
395       case Point::PreInsn:
396          points_.preInsn.erase(p->addr());
397          break;
398       case Point::PostInsn:
399          points_.postInsn.erase(p->addr());
400          break;
401       case Point::BlockEntry:
402          points_.entry = NULL;
403          break;
404       case Point::BlockExit:
405          points_.exit = NULL;
406          break;
407       case Point::BlockDuring:
408          points_.during = NULL;
409          break;
410       default:
411          break;
412    }
413 }
414
415 // destroy points for this block and then each containing function's
416 // context specific points for the block
417 void PatchBlock::destroyPoints()
418 {
419     PatchCallback *cb = obj()->cb();
420     if (points_.entry) {
421         cb->destroy(points_.entry);
422         delete points_.entry;
423         points_.entry = NULL;
424     } 
425     if (points_.during) {
426         cb->destroy(points_.during);
427         delete points_.during;
428         points_.during = NULL;
429     }
430     if (points_.exit) {
431         cb->destroy(points_.exit);
432         delete points_.exit;
433         points_.exit = NULL;
434     }
435     if (!points_.preInsn.empty()) {
436         for (InsnPoints::iterator iit = points_.preInsn.begin(); 
437              iit != points_.preInsn.end(); 
438              iit++) 
439         {
440             cb->destroy(iit->second);
441             delete iit->second;
442         }
443         points_.preInsn.clear();
444     }
445     if (!points_.postInsn.empty()) {
446         for (InsnPoints::iterator iit = points_.postInsn.begin(); 
447              iit != points_.postInsn.end(); 
448              iit++) 
449         {
450             cb->destroy(iit->second);
451             delete iit->second;
452         }
453         points_.postInsn.clear();
454     }
455
456     // now destroy function's context-specific points for this block
457     vector<PatchFunction *> funcs;
458     getFuncs(back_inserter(funcs));
459     for (vector<PatchFunction *>::iterator fit = funcs.begin();
460          fit != funcs.end();
461          fit++)
462     {
463         (*fit)->destroyBlockPoints(this);
464     }
465 }
466
467 PatchCallback *PatchBlock::cb() const {
468    return obj_->cb();
469 }
470
471 void PatchBlock::splitBlock(PatchBlock *succ)
472 {
473
474    // Okay, get our edges right and stuff. 
475    // We want to modify when possible so that we keep Points on affected edges the same. 
476    // Therefore:
477    // 1) Incoming edges are unchanged. 
478    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
479    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
480    //    of our lazy block & edge creation when parseAPI added the edge)
481    // 4) We fix up Points on the block, entry and during points stay here
482
483    // 2)
484    const ParseAPI::Block::edgelist & trgs = succ->block()->targets();
485    ParseAPI::Block::edgelist::const_iterator titer = trgs.begin();
486    for (; titer != trgs.end(); titer++) {
487       PatchEdge *cur = obj()->getEdge(*titer, this, NULL, false);
488       if (cur != NULL) {
489          cur->src_ = succ;
490       }
491    }
492    trglist_.clear();
493    // list will be built up lazily when needed, hopefully after parsing is done
494    succ->trglist_.clear(); 
495
496    // 3)
497    assert(1 == block_->targets().size());
498    PatchEdge *patch_ft = obj()->getEdge(*block_->targets().begin(), this, succ, false);
499    if (patch_ft) {// patch_ft may have been created by another callback
500       trglist_.push_back(patch_ft);
501    }
502    else {
503        const ParseAPI::Block::edgelist &tmp = this->block()->targets();
504        if (tmp.size() != 1) {
505           cerr << "ERROR: split block has " << tmp.size() 
506               << " edges, not 1 as expected!" << endl;
507           assert(0);
508        }
509        ParseAPI::Edge *ft = *(tmp.begin());
510        obj_->getEdge(ft, this, succ);
511    }
512
513    // 4)
514    if (points_.exit) {
515       succ->points_.exit = points_.exit;
516       points_.exit = NULL;
517       succ->points_.exit->changeBlock(succ);
518    }
519
520    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
521    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
522       tmp->second->changeBlock(succ);
523       succ->points_.preInsn[tmp->first] = tmp->second;
524    }
525    points_.preInsn.erase(pre, points_.preInsn.end());
526
527    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
528    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
529       tmp->second->changeBlock(succ);
530       succ->points_.postInsn[tmp->first] = tmp->second;
531    }
532    points_.postInsn.erase(post, points_.postInsn.end());
533
534 }
535
536 bool PatchBlock::consistency() const {
537    if (!block_) {
538       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
539       CONSIST_FAIL;
540    }
541    if (!srclist_.empty()) {
542       if (srclist_.size() != block_->sources().size()) {
543          cerr << "Error: block has inconsistent sources size" << endl;
544          CONSIST_FAIL;
545       }
546       set<PatchBlock*> srcs;
547       for (unsigned i = 0; i < srclist_.size(); ++i) {
548          // shouldn't have multiple edges to the same block unless one
549          // is a conditional taken and the other a conditional not-taken
550          // (even this is weird, but it happens in obfuscated code)
551          if (srcs.find(srclist_[i]->src()) != srcs.end() &&
552              srclist_[i]->type() != ParseAPI::COND_TAKEN && 
553              srclist_[i]->type() != ParseAPI::COND_NOT_TAKEN) 
554          {
555             cerr << "Error: multiple source edges to same block" << endl;
556             CONSIST_FAIL;
557          }
558          srcs.insert(srclist_[i]->src());
559          if (!srclist_[i]->consistency()) {
560             cerr << "Error: source edge inconsistent" << endl;
561             CONSIST_FAIL;
562          }
563       }
564    }
565    if (!trglist_.empty()) {
566       if (trglist_.size() != block_->targets().size()) {
567          cerr << "Error: block at "<<hex<< block_->start()<< dec<<" has inconsistent targets size; ParseAPI "
568               << block_->targets().size() << " and PatchAPI " 
569               << trglist_.size() << endl;
570          CONSIST_FAIL;
571       }
572       set<PatchBlock*>trgs;
573       for (unsigned i = 0; i < trglist_.size(); ++i) {
574          // shouldn't have multiple edges to the same block unless one
575          // is a conditional taken and the other a conditional not-taken
576          // (even this is weird, but it happens in obfuscated code)
577          if (trgs.find(trglist_[i]->trg()) != trgs.end() &&
578              trglist_[i]->type() != ParseAPI::COND_TAKEN && 
579              trglist_[i]->type() != ParseAPI::COND_NOT_TAKEN) 
580          {
581             cerr << "Error: multiple target edges to same block" << endl;
582             CONSIST_FAIL;
583          }
584          trgs.insert(trglist_[i]->src());
585          if (!trglist_[i]->consistency()) {
586             cerr << "Error: target edge inconsistent" << endl;
587             CONSIST_FAIL;
588          }
589       }
590    }
591    if (!obj_) {
592       cerr << "Error: block has no object" << endl;
593       CONSIST_FAIL;
594    }
595    if (!points_.consistency(this, NULL)) {
596       cerr << "Error: block has inconsistent points" << endl;
597       CONSIST_FAIL;
598    }
599    return true;
600 }
601
602 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
603    if (entry) {
604       if (!entry->consistency()) CONSIST_FAIL;
605       if (entry->block() != b) CONSIST_FAIL;
606       if (entry->func() != f) CONSIST_FAIL;
607       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
608    }
609    if (during) {
610       if (!during->consistency()) CONSIST_FAIL;
611       if (during->block() != b) CONSIST_FAIL;
612       if (during->func() != f) CONSIST_FAIL;
613       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
614    }
615    if (exit) {
616       if (!exit->consistency()) CONSIST_FAIL;
617       if (exit->block() != b) CONSIST_FAIL;
618       if (exit->func() != f) CONSIST_FAIL;
619       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
620    }
621    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
622       if (!iter->second->consistency()) CONSIST_FAIL;
623       if (iter->second->block() != b) CONSIST_FAIL;
624       if (iter->second->func() != f) CONSIST_FAIL;
625       if (iter->second->addr() != iter->first) CONSIST_FAIL;
626       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
627       if (!b->getInsn(iter->first)) CONSIST_FAIL;
628    }
629    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
630       if (!iter->second->consistency()) CONSIST_FAIL;
631       if (iter->second->block() != b) CONSIST_FAIL;
632       if (iter->second->func() != f) CONSIST_FAIL;
633       if (iter->second->addr() != iter->first) CONSIST_FAIL;
634       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
635       if (!b->getInsn(iter->first)) CONSIST_FAIL;
636    }
637    return true;
638 }
639
640 bool PatchBlock::wasUserAdded() const {
641    return block_->wasUserAdded();
642 }