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