Merge branch 'Defensive' of ssh://git.dyninst.org/pub/dyninst into Defensive
[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
11 using namespace Dyninst;
12 using namespace PatchAPI;
13 using namespace InstructionAPI;
14
15 PatchBlock*
16 PatchBlock::create(ParseAPI::Block *ib, PatchFunction *f) {
17   return f->object()->getBlock(ib);
18 }
19
20 PatchBlock::PatchBlock(ParseAPI::Block *blk, PatchObject *obj)
21   : block_(blk),   obj_(obj) {
22 }
23
24 PatchBlock::PatchBlock(const PatchBlock *parent, PatchObject *child)
25   : block_(parent->block_), obj_(child) {
26 }
27
28 void
29 PatchBlock::getInsns(Insns &insns) const {
30   // Pass through to ParseAPI. They don't have a native interface, so add one.
31   Offset off = block_->start();
32   const unsigned char *ptr =
33     (const unsigned char *)block_->region()->getPtrToInstruction(off);
34   if (ptr == NULL) return;
35   InstructionDecoder d(ptr, size(), block_->obj()->cs()->getArch());
36   while (off < block_->end()) {
37     Instruction::Ptr insn = d.decode();
38     insns[off + obj_->codeBase()] = insn;
39     off += insn->size();
40   }
41 }
42
43 const PatchBlock::edgelist&
44 PatchBlock::getSources() {
45   if (srclist_.empty()) {
46     for (ParseAPI::Block::edgelist::iterator iter = block_->sources().begin();
47          iter != block_->sources().end(); ++iter) {
48       PatchEdge *newEdge = obj_->getEdge(*iter, NULL, this);
49       srclist_.push_back(newEdge);
50     }
51   }
52   return srclist_;
53 }
54
55 const PatchBlock::edgelist&
56 PatchBlock::getTargets() {
57   if (trglist_.empty()) {
58     for (ParseAPI::Block::edgelist::iterator iter = block_->targets().begin();
59          iter != block_->targets().end(); ++iter) {
60       PatchEdge *newEdge = obj_->getEdge(*iter, this, NULL);
61       assert(newEdge);
62       trglist_.push_back(newEdge);
63     }
64   }
65   return trglist_;
66 }
67
68 PatchEdge *PatchBlock::findSource(ParseAPI::EdgeTypeEnum type) {
69    getSources();
70    for (edgelist::iterator iter = srclist_.begin();
71         iter != srclist_.end(); ++iter) {
72       if ((*iter)->type() == type) return *iter;
73    }
74    return NULL;
75 }
76
77 PatchEdge *PatchBlock::findTarget(ParseAPI::EdgeTypeEnum type) {
78    getTargets();
79    for (edgelist::iterator iter = trglist_.begin();
80         iter != trglist_.end(); ++iter) {
81       assert(*iter);
82       assert((*iter)->edge());
83       cerr << "Looking for " << ParseAPI::format(type) << ", found edge with " << ParseAPI::format((*iter)->type()) << endl;
84       if ((*iter)->type() == type) return *iter;
85    }
86    return NULL;
87 }
88
89 void PatchBlock::addSourceEdge(PatchEdge *e, bool addIfEmpty) {
90    if (!addIfEmpty && srclist_.empty()) return;
91
92    srclist_.push_back(e);
93
94   cb()->add_edge(this, e, PatchCallback::source);
95 }
96
97 void PatchBlock::addTargetEdge(PatchEdge *e, bool addIfEmpty) {
98    assert(e);
99    if (!addIfEmpty && trglist_.empty()) return;
100
101    trglist_.push_back(e);
102    
103    cb()->add_edge(this, e, PatchCallback::target);
104 }
105
106
107 void
108 PatchBlock::removeSourceEdge(PatchEdge *e) {
109    if (srclist_.empty()) return;
110
111   std::vector<PatchEdge *>::iterator iter;
112   if ((iter = std::find(srclist_.begin(), srclist_.end(), e)) != srclist_.end()) {
113     srclist_.erase(iter);
114   }
115
116   cb()->remove_edge(this, e, PatchCallback::source);
117 }
118
119 void
120 PatchBlock::removeTargetEdge(PatchEdge *e) {
121    if (trglist_.empty()) return;
122
123   std::vector<PatchEdge *>::iterator iter;
124   if ((iter = std::find(trglist_.begin(), trglist_.end(), e)) != trglist_.end()) {
125      cerr << "Erasing target edge" << endl;
126     trglist_.erase(iter);
127   }
128   cb()->remove_edge(this, e, PatchCallback::target);
129 }
130
131
132 bool
133 PatchBlock::isShared() {
134   return containingFuncs() > 1;
135 }
136
137 PatchBlock::~PatchBlock() {
138 #if 0
139    // Our predecessor may be deleted...
140   for (std::vector<PatchEdge *>::iterator iter = srclist_.begin();
141        iter != srclist_.end(); ++iter) {
142     PatchBlock* blk = (*iter)->source();
143     blk->removeTargetEdge(*iter);
144   }
145   for (std::vector<PatchEdge *>::iterator iter = trglist_.begin();
146        iter != trglist_.end(); ++iter) {
147     PatchBlock* blk = (*iter)->target();
148     blk->removeSourceEdge(*iter);
149   }
150 #endif
151 }
152
153 Address
154 PatchBlock::start() const {
155   return object()->codeBase() + block_->start();
156 }
157
158 Address
159 PatchBlock::end() const {
160   return object()->codeBase() + block_->end();
161 }
162
163 Address
164 PatchBlock::last() const {
165   return object()->codeBase() + block_->lastInsnAddr();
166 }
167
168 Address
169 PatchBlock::size() const {
170   return block_->size();
171 }
172
173 int
174 PatchBlock::containingFuncs() const {
175   return block_->containingFuncs();
176 }
177
178 bool
179 PatchBlock::containsCall() {
180   ParseAPI::Block::edgelist & out_edges = block_->targets();
181   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
182   for( ; eit != out_edges.end(); ++eit) {
183     if ( ParseAPI::CALL == (*eit)->type() ) {
184       return true;
185     }
186   }
187   return false;
188 }
189
190 bool
191 PatchBlock::containsDynamicCall() {
192   ParseAPI::Block::edgelist & out_edges = block_->targets();
193   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
194    for( ; eit != out_edges.end(); ++eit) {
195      if ( ParseAPI::CALL == (*eit)->type() && ((*eit)->sinkEdge())) {
196          return true;
197       }
198    }
199    return false;
200 }
201
202 std::string
203 PatchBlock::disassemble() const {
204   stringstream ret;
205   Insns instances;
206   getInsns(instances);
207   for (Insns::iterator iter = instances.begin();
208        iter != instances.end(); ++iter) {
209     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
210   }
211   return ret.str();
212 }
213
214 InstructionAPI::Instruction::Ptr
215 PatchBlock::getInsn(Address a) const {
216    Insns insns;
217    getInsns(insns);
218    return insns[a];
219 }
220
221 std::string
222 PatchBlock::format() const {
223   stringstream ret;
224   ret << "BB["
225       << hex << start()
226       << ","
227       << end() << dec
228       << "]" << endl;
229   return ret.str();
230 }
231
232 PatchFunction*
233 PatchBlock::getFunction(ParseAPI::Function* f) {
234   return obj_->getFunc(f);
235 }
236
237 ParseAPI::Block*
238 PatchBlock::block() const { return block_; }
239
240 PatchObject*
241 PatchBlock::object() const { return obj_; }
242
243 PatchFunction*
244 PatchBlock::getCallee() {
245   PatchBlock::edgelist::const_iterator it = getTargets().begin();
246   for (; it != getTargets().end(); ++it) {
247     if ((*it)->type() == ParseAPI::CALL) {
248       PatchBlock* trg = (*it)->target();
249       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
250                                                        trg->start()));
251     }
252   }
253   return NULL;
254 }
255
256 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
257    PointMakerPtr maker = obj_->addrSpace()->mgr()->pointMaker();
258    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
259    Point *ret = NULL;
260
261    switch (type) {
262       case Point::BlockEntry:
263          if (!points_.entry && create) {
264             points_.entry = maker->createPoint(loc, type);
265          }
266          return points_.entry;
267          break;
268       case Point::BlockExit:
269          if (!points_.exit && create) {
270             points_.exit = maker->createPoint(loc, type);
271          }
272          return points_.exit;
273          break;
274       case Point::BlockDuring:
275          if (!points_.during && create) {
276             points_.during = maker->createPoint(loc, type);
277          }
278          return points_.during;
279          break;
280       case Point::PreInsn: {
281          if (!loc.addr || !loc.insn) return NULL;
282          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
283          if (iter2 == points_.preInsn.end()) {
284             if (!create) return NULL;
285             ret = maker->createPoint(loc, type);
286             points_.preInsn[loc.addr] = ret;
287             return ret;
288          }
289          else {
290             return iter2->second;
291          }
292          break;
293       }
294       case Point::PostInsn: {
295          if (!loc.addr || !loc.insn) return NULL;
296          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
297          if (iter2 == points_.postInsn.end()) {
298             if (!create) return NULL;
299             ret = maker->createPoint(loc, type);
300             points_.preInsn[loc.addr] = ret;
301             return ret;
302          }
303          else return iter2->second;
304          break;
305       }
306       default:
307          return NULL;
308    }
309    assert(0); return NULL; // unreachable, but keep compiler happy
310 }
311
312
313 void PatchBlock::destroy(Point *p) {
314    assert(p->getBlock() == this);
315
316    switch(p->type()) {
317       case Point::PreInsn:
318          delete points_.preInsn[p->address()];
319          break;
320       case Point::PostInsn:
321          delete points_.postInsn[p->address()];
322          break;
323       case Point::BlockEntry:
324          delete points_.entry;
325          break;
326       case Point::BlockExit:
327          delete points_.exit;
328          break;
329       case Point::BlockDuring:
330          delete points_.during;
331          break;
332       default:
333          break;
334    }
335 }
336
337 PatchCallback *PatchBlock::cb() const {
338    return obj_->cb();
339 }
340
341 void PatchBlock::splitBlock(PatchBlock *succ)
342 {
343
344    // Okay, get our edges right and stuff. 
345    // We want to modify when possible so that we keep Points on affected edges the same. 
346    // Therefore:
347    // 1) Incoming edges are unchanged. 
348    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
349    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
350    //    of our lazy block & edge creation when parseAPI added the edge)
351    // 4) We fix up Points on the block, entry and during points stay here
352
353    // 2)
354    bool hasFTEdge = false;
355    unsigned tidx= 0; 
356    while (tidx < trglist_.size()) {
357       PatchEdge *cur = trglist_[tidx];
358       if (cur->target() == succ) {
359           hasFTEdge = true;
360           tidx++;
361       } else {
362           cur->src_ = succ;
363           succ->trglist_.push_back(cur);
364           int last = trglist_.size()-1;
365           trglist_[tidx] = trglist_[last];
366           trglist_.pop_back();
367       }
368    }
369
370    // 3)
371    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
372        ParseAPI::Block::edgelist &tmp = this->block()->targets();
373        if (tmp.size() != 1) {
374           cerr << "ERROR: split block has " << tmp.size() 
375               << " edges, not 1 as expected!" << endl;
376           assert(0);
377        }
378        ParseAPI::Edge *ft = *(tmp.begin());
379        obj_->getEdge(ft, this, succ);
380    }
381
382    // 4)
383    if (points_.exit) {
384       succ->points_.exit = points_.exit;
385       points_.exit = NULL;
386       succ->points_.exit->changeBlock(succ);
387    }
388
389    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
390    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
391       tmp->second->changeBlock(succ);
392       succ->points_.preInsn[tmp->first] = tmp->second;
393    }
394    points_.preInsn.erase(pre, points_.preInsn.end());
395
396    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
397    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
398       tmp->second->changeBlock(succ);
399       succ->points_.postInsn[tmp->first] = tmp->second;
400    }
401    points_.postInsn.erase(post, points_.postInsn.end());
402
403 }
404
405 bool PatchBlock::consistency() const {
406    if (!block_) {
407       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
408       CONSIST_FAIL;
409    }
410    if (!srclist_.empty()) {
411       if (srclist_.size() != block_->sources().size()) {
412          cerr << "Error: block has inconsistent sources size" << endl;
413          CONSIST_FAIL;
414       }
415       for (unsigned i = 0; i < srclist_.size(); ++i) {
416          if (!srclist_[i]->consistency()) {
417             cerr << "Error: source edge inconsistent" << endl;
418             CONSIST_FAIL;
419          }
420       }
421    }
422    if (!trglist_.empty()) {
423       if (trglist_.size() != block_->targets().size()) {
424          cerr << "Error: block has inconsistent targets size; ParseAPI "
425               << block_->targets().size() << " and PatchAPI " 
426               << trglist_.size() << endl;
427          CONSIST_FAIL;
428       }
429       for (unsigned i = 0; i < trglist_.size(); ++i) {
430          if (!trglist_[i]->consistency()) {
431             cerr << "Error: target edge inconsistent" << endl;
432             CONSIST_FAIL;
433          }
434       }
435    }
436    if (!obj_) {
437       cerr << "Error: block has no object" << endl;
438       CONSIST_FAIL;
439    }
440    if (!points_.consistency(this, NULL)) {
441       cerr << "Error: block has inconsistent points" << endl;
442       CONSIST_FAIL;
443    }
444    return true;
445 }
446
447 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
448    if (entry) {
449       if (!entry->consistency()) CONSIST_FAIL;
450       if (entry->block() != b) CONSIST_FAIL;
451       if (entry->func() != f) CONSIST_FAIL;
452       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
453    }
454    if (during) {
455       if (!during->consistency()) CONSIST_FAIL;
456       if (during->block() != b) CONSIST_FAIL;
457       if (during->func() != f) CONSIST_FAIL;
458       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
459    }
460    if (exit) {
461       if (!exit->consistency()) CONSIST_FAIL;
462       if (exit->block() != b) CONSIST_FAIL;
463       if (exit->func() != f) CONSIST_FAIL;
464       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
465    }
466    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
467       if (!iter->second->consistency()) CONSIST_FAIL;
468       if (iter->second->block() != b) CONSIST_FAIL;
469       if (iter->second->func() != f) CONSIST_FAIL;
470       if (iter->second->addr() != iter->first) CONSIST_FAIL;
471       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
472       if (!b->getInsn(iter->first)) CONSIST_FAIL;
473    }
474    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
475       if (!iter->second->consistency()) CONSIST_FAIL;
476       if (iter->second->block() != b) CONSIST_FAIL;
477       if (iter->second->func() != f) CONSIST_FAIL;
478       if (iter->second->addr() != iter->first) CONSIST_FAIL;
479       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
480       if (!b->getInsn(iter->first)) CONSIST_FAIL;
481    }
482    return true;
483 }
484