Merge branch 'Defensive' of ssh://coriander.cs.wisc.edu/u/r/o/roundy/devel/g0/dyninst...
[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() ) { 
196          // see if it's a static call to a bad address
197          return getInsn(last())->readsMemory();
198       }
199    }
200    return false;
201 }
202
203 std::string
204 PatchBlock::disassemble() const {
205   stringstream ret;
206   Insns instances;
207   getInsns(instances);
208   for (Insns::iterator iter = instances.begin();
209        iter != instances.end(); ++iter) {
210     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
211   }
212   return ret.str();
213 }
214
215 InstructionAPI::Instruction::Ptr
216 PatchBlock::getInsn(Address a) const {
217    Insns insns;
218    getInsns(insns);
219    return insns[a];
220 }
221
222 std::string
223 PatchBlock::format() const {
224   stringstream ret;
225   ret << "BB["
226       << hex << start()
227       << ","
228       << end() << dec
229       << "]" << endl;
230   return ret.str();
231 }
232
233 PatchFunction*
234 PatchBlock::getFunction(ParseAPI::Function* f) {
235   return obj_->getFunc(f);
236 }
237
238 ParseAPI::Block*
239 PatchBlock::block() const { return block_; }
240
241 PatchObject*
242 PatchBlock::object() const { return obj_; }
243
244 PatchFunction*
245 PatchBlock::getCallee() {
246   PatchBlock::edgelist::const_iterator it = getTargets().begin();
247   for (; it != getTargets().end(); ++it) {
248     if ((*it)->type() == ParseAPI::CALL) {
249       PatchBlock* trg = (*it)->target();
250       return obj_->getFunc(obj_->co()->findFuncByEntry(trg->block()->region(),
251                                                        trg->start()));
252     }
253   }
254   return NULL;
255 }
256
257 Point *PatchBlock::findPoint(Location loc, Point::Type type, bool create) {
258    PointMakerPtr maker = obj_->addrSpace()->mgr()->pointMaker();
259    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
260    Point *ret = NULL;
261
262    switch (type) {
263       case Point::BlockEntry:
264          if (!points_.entry && create) {
265             points_.entry = maker->createPoint(loc, type);
266          }
267          return points_.entry;
268          break;
269       case Point::BlockExit:
270          if (!points_.exit && create) {
271             points_.exit = maker->createPoint(loc, type);
272          }
273          return points_.exit;
274          break;
275       case Point::BlockDuring:
276          if (!points_.during && create) {
277             points_.during = maker->createPoint(loc, type);
278          }
279          return points_.during;
280          break;
281       case Point::PreInsn: {
282          if (!loc.addr || !loc.insn) return NULL;
283          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
284          if (iter2 == points_.preInsn.end()) {
285             if (!create) return NULL;
286             ret = maker->createPoint(loc, type);
287             points_.preInsn[loc.addr] = ret;
288             return ret;
289          }
290          else {
291             return iter2->second;
292          }
293          break;
294       }
295       case Point::PostInsn: {
296          if (!loc.addr || !loc.insn) return NULL;
297          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
298          if (iter2 == points_.postInsn.end()) {
299             if (!create) return NULL;
300             ret = maker->createPoint(loc, type);
301             points_.preInsn[loc.addr] = ret;
302             return ret;
303          }
304          else return iter2->second;
305          break;
306       }
307       default:
308          return NULL;
309    }
310    assert(0); return NULL; // unreachable, but keep compiler happy
311 }
312
313
314 void PatchBlock::destroy(Point *p) {
315    assert(p->getBlock() == this);
316
317    switch(p->type()) {
318       case Point::PreInsn:
319          delete points_.preInsn[p->address()];
320          break;
321       case Point::PostInsn:
322          delete points_.postInsn[p->address()];
323          break;
324       case Point::BlockEntry:
325          delete points_.entry;
326          break;
327       case Point::BlockExit:
328          delete points_.exit;
329          break;
330       case Point::BlockDuring:
331          delete points_.during;
332          break;
333       default:
334          break;
335    }
336 }
337
338 PatchCallback *PatchBlock::cb() const {
339    return obj_->cb();
340 }
341
342 void PatchBlock::splitBlock(PatchBlock *succ)
343 {
344
345    // Okay, get our edges right and stuff. 
346    // We want to modify when possible so that we keep Points on affected edges the same. 
347    // Therefore:
348    // 1) Incoming edges are unchanged. 
349    // 2) Outgoing edges from p1 are switched to p2 (except the fallthrough from p1 to p2)
350    // 3) Fallthrough edge from p1 to p2 added if it wasn't already (depends on the status
351    //    of our lazy block & edge creation when parseAPI added the edge)
352    // 4) We fix up Points on the block, entry and during points stay here
353
354    // 2)
355    bool hasFTEdge = false;
356    unsigned tidx= 0; 
357    while (tidx < trglist_.size()) {
358       PatchEdge *cur = trglist_[tidx];
359       if (cur->target() == succ) {
360           hasFTEdge = true;
361           tidx++;
362       } else {
363           cur->src_ = succ;
364           succ->trglist_.push_back(cur);
365           int last = trglist_.size()-1;
366           trglist_[tidx] = trglist_[last];
367           trglist_.pop_back();
368       }
369    }
370
371    // 3)
372    if (!hasFTEdge) { // may have been created by ParseAPI callbacks
373        ParseAPI::Block::edgelist &tmp = this->block()->targets();
374        if (tmp.size() != 1) {
375           cerr << "ERROR: split block has " << tmp.size() 
376               << " edges, not 1 as expected!" << endl;
377           assert(0);
378        }
379        ParseAPI::Edge *ft = *(tmp.begin());
380        obj_->getEdge(ft, this, succ);
381    }
382
383    // 4)
384    if (points_.exit) {
385       succ->points_.exit = points_.exit;
386       points_.exit = NULL;
387       succ->points_.exit->changeBlock(succ);
388    }
389
390    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
391    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
392       tmp->second->changeBlock(succ);
393       succ->points_.preInsn[tmp->first] = tmp->second;
394    }
395    points_.preInsn.erase(pre, points_.preInsn.end());
396
397    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
398    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
399       tmp->second->changeBlock(succ);
400       succ->points_.postInsn[tmp->first] = tmp->second;
401    }
402    points_.postInsn.erase(post, points_.postInsn.end());
403
404 }
405
406 bool PatchBlock::consistency() const {
407    if (!block_) {
408       cerr << "Error: block has no associated ParseAPI block, failed consistency" << endl;
409       CONSIST_FAIL;
410    }
411    if (!srclist_.empty()) {
412       if (srclist_.size() != block_->sources().size()) {
413          cerr << "Error: block has inconsistent sources size" << endl;
414          CONSIST_FAIL;
415       }
416       for (unsigned i = 0; i < srclist_.size(); ++i) {
417          if (!srclist_[i]->consistency()) {
418             cerr << "Error: source edge inconsistent" << endl;
419             CONSIST_FAIL;
420          }
421       }
422    }
423    if (!trglist_.empty()) {
424       if (trglist_.size() != block_->targets().size()) {
425          cerr << "Error: block has inconsistent targets size; ParseAPI "
426               << block_->targets().size() << " and PatchAPI " 
427               << trglist_.size() << endl;
428          CONSIST_FAIL;
429       }
430       for (unsigned i = 0; i < trglist_.size(); ++i) {
431          if (!trglist_[i]->consistency()) {
432             cerr << "Error: target edge inconsistent" << endl;
433             CONSIST_FAIL;
434          }
435       }
436    }
437    if (!obj_) {
438       cerr << "Error: block has no object" << endl;
439       CONSIST_FAIL;
440    }
441    if (!points_.consistency(this, NULL)) {
442       cerr << "Error: block has inconsistent points" << endl;
443       CONSIST_FAIL;
444    }
445    return true;
446 }
447
448 bool BlockPoints::consistency(const PatchBlock *b, const PatchFunction *f) const {
449    if (entry) {
450       if (!entry->consistency()) CONSIST_FAIL;
451       if (entry->block() != b) CONSIST_FAIL;
452       if (entry->func() != f) CONSIST_FAIL;
453       if (entry->type() != Point::BlockEntry) CONSIST_FAIL;
454    }
455    if (during) {
456       if (!during->consistency()) CONSIST_FAIL;
457       if (during->block() != b) CONSIST_FAIL;
458       if (during->func() != f) CONSIST_FAIL;
459       if (during->type() != Point::BlockDuring) CONSIST_FAIL;
460    }
461    if (exit) {
462       if (!exit->consistency()) CONSIST_FAIL;
463       if (exit->block() != b) CONSIST_FAIL;
464       if (exit->func() != f) CONSIST_FAIL;
465       if (exit->type() != Point::BlockExit) CONSIST_FAIL;
466    }
467    for (InsnPoints::const_iterator iter = preInsn.begin(); iter != preInsn.end(); ++iter) {
468       if (!iter->second->consistency()) CONSIST_FAIL;
469       if (iter->second->block() != b) CONSIST_FAIL;
470       if (iter->second->func() != f) CONSIST_FAIL;
471       if (iter->second->addr() != iter->first) CONSIST_FAIL;
472       if (iter->second->type() != Point::PreInsn) CONSIST_FAIL;
473       if (!b->getInsn(iter->first)) CONSIST_FAIL;
474    }
475    for (InsnPoints::const_iterator iter = postInsn.begin(); iter != postInsn.end(); ++iter) {
476       if (!iter->second->consistency()) CONSIST_FAIL;
477       if (iter->second->block() != b) CONSIST_FAIL;
478       if (iter->second->func() != f) CONSIST_FAIL;
479       if (iter->second->addr() != iter->first) CONSIST_FAIL;
480       if (iter->second->type() != Point::PostInsn) CONSIST_FAIL;
481       if (!b->getInsn(iter->first)) CONSIST_FAIL;
482    }
483    return true;
484 }
485