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