Add a test for inserting new code into the middle of a basic block. Currently will...
[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.
349    // 3) An entirely new edge is created between p1 and p2. 
350    // 4) We fix up Points on the block, entry and during points stay here
351
352    // 2)
353    for (PatchBlock::edgelist::iterator iter = this->trglist_.begin();
354         iter != this->trglist_.end(); ++iter) {
355       (*iter)->src_ = succ;
356       assert(*iter);
357       succ->trglist_.push_back(*iter);
358    }
359    this->trglist_.clear();
360
361    // 3)
362    ParseAPI::Block::edgelist &tmp = this->block()->targets();
363    if (tmp.size() != 1) {
364       cerr << "Error: split block has " << tmp.size() << " edges, not 1 as expected!" << endl;
365    }
366    assert(tmp.size() == 1);
367    ParseAPI::Edge *ft = *(tmp.begin());
368    obj_->getEdge(ft, this, succ);
369
370    // 4)
371    if (points_.exit) {
372       succ->points_.exit = points_.exit;
373       points_.exit = NULL;
374       succ->points_.exit->changeBlock(succ);
375    }
376
377    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
378    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
379       tmp->second->changeBlock(succ);
380       succ->points_.preInsn[tmp->first] = tmp->second;
381    }
382    points_.preInsn.erase(pre, points_.preInsn.end());
383
384    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
385    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
386       tmp->second->changeBlock(succ);
387       succ->points_.postInsn[tmp->first] = tmp->second;
388    }
389    points_.postInsn.erase(post, points_.postInsn.end());
390
391 }
392
393 bool PatchBlock::consistency() const {
394    if (!block_) {
395       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
396       return false;
397    }
398    if (!srclist_.empty()) {
399       if (srclist_.size() != block_->sources().size()) {
400          cerr << "Error: block has inconsistent sources size" << endl;
401          return false;
402       }
403       for (unsigned i = 0; i < srclist_.size(); ++i) {
404          if (!srclist_[i]->consistency()) {
405             cerr << "Error: source edge inconsistent" << endl;
406             return false;
407          }
408       }
409    }
410    if (!trglist_.empty()) {
411       if (trglist_.size() != block_->targets().size()) {
412          cerr << "Error: block has inconsistent targets size; ParseAPI "
413               << block_->targets().size() << " and PatchAPI " 
414               << trglist_.size() << endl;
415          return false;
416       }
417       for (unsigned i = 0; i < trglist_.size(); ++i) {
418          if (!trglist_[i]->consistency()) {
419             cerr << "Error: target edge inconsistent" << endl;
420             return false;
421          }
422       }
423    }
424    if (!obj_) {
425       cerr << "Error: block has no object" << endl;
426       return false;
427    }
428    if (!points_.consistency(this, NULL)) {
429       cerr << "Error: block has inconsistent points" << endl;
430       return false;
431    }
432    return true;
433 }
434
435 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
436    if (entry) {
437       if (!entry->consistency()) return false;
438       if (entry->block() != b) return false;
439       if (entry->func() != f) return false;
440       if (entry->type() != Point::BlockEntry) return false;
441    }
442    if (during) {
443       if (!during->consistency()) return false;
444       if (during->block() != b) return false;
445       if (during->func() != f) return false;
446       if (during->type() != Point::BlockDuring) return false;
447    }
448    if (exit) {
449       if (!exit->consistency()) return false;
450       if (exit->block() != b) return false;
451       if (exit->func() != f) return false;
452       if (exit->type() != Point::BlockExit) return false;
453    }
454    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
455       if (!iter->second->consistency()) return false;
456       if (iter->second->block() != b) return false;
457       if (iter->second->func() != f) return false;
458       if (iter->second->addr() != iter->first) return false;
459       if (iter->second->type() != Point::PreInsn) return false;
460       if (!b->getInsn(iter->first)) return false;
461    }
462    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
463       if (!iter->second->consistency()) return false;
464       if (iter->second->block() != b) return false;
465       if (iter->second->func() != f) return false;
466       if (iter->second->addr() != iter->first) return false;
467       if (iter->second->type() != Point::PostInsn) return false;
468       if (!b->getInsn(iter->first)) return false;
469    }
470    return true;
471 }
472