1. Replace springboards prioriy "OffLimits" and "Required" with "FuncEntry" and ...
[dyninst.git] / dyninstAPI / src / Relocation / CFG / RelocBlock.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include <iostream>
32 #include <iomanip>
33
34 #include "../dyninstAPI/src/debug.h"
35
36 #include "../Widgets/Widget.h"
37 #include "../Widgets/InsnWidget.h" // Default Widget in each RelocBlock
38 #include "../Widgets/InstWidget.h"
39 #include "RelocBlock.h"
40 #include "RelocTarget.h"
41 #include "../Widgets/CFWidget.h"
42
43 #include "../CodeTracker.h"
44 #include "../CodeBuffer.h"
45 #include "../Transformers/Transformer.h" // transformer class
46 #include "RelocGraph.h"
47
48 #include "boost/tuple/tuple.hpp"
49
50 using namespace Dyninst;
51 using namespace Relocation;
52 using namespace InstructionAPI;
53
54 // a RelocBlock is a representation for instructions and instrumentation with
55 // a single entry point and (possibly) multiple exit points. For simplicity,
56 // we initially map a RelocBlock to a basic block. However, edge instrumentation
57 // or post-call padding (in defensive mode) may add additional RelocBlocks. Also,
58 // a RelocBlock may exit early if instrumentation explicitly branches out of a
59 // RelocBlock. 
60 //
61 // A RelocBlock is represented as a list of Widgets. An Widget represents a single
62 // code generation unit: an instruction, an instrumentation sequence, and
63 // the like. 
64 //
65 // Each RelocBlock ends in a distinguished "CFWidget" that tracks the successors 
66 // of the RelocBlock. Arguably this information should be stored in the RelocBlock itself,
67 // but then we'd still need the code generation techniques in a CFWidget anyway. 
68
69 int RelocBlock::RelocBlockID = 0;
70
71 RelocBlock *RelocBlock::createReloc(block_instance *block, func_instance *func) {
72   if (!block) return NULL;
73
74   relocation_cerr << "Creating new RelocBlock" << endl;
75   RelocBlock *newRelocBlock = new RelocBlock(block, func);
76
77   // Get the list of instructions in the block
78   block_instance::Insns insns;
79   block->getInsns(insns);
80   int cnt = 0;
81   for (block_instance::Insns::iterator iter = insns.begin();
82        iter != insns.end(); ++iter, ++cnt) {
83     if (block->_ignorePowerPreamble && cnt < 2) continue;
84     relocation_cerr << "  Adding instruction @" 
85                     << std::hex << iter->first << std::dec
86                     << ": " << iter->second.format(iter->first) << endl;
87     Widget::Ptr ptr = InsnWidget::create(iter->second, iter->first);
88
89     if (!ptr) {
90        delete newRelocBlock;
91        return NULL;
92     }
93     
94     newRelocBlock->elements_.push_back(ptr);
95   }
96
97   // TODO: this should be done just before code generation, 
98   // not up front; however, several transformers depend
99   // on this behavior
100   newRelocBlock->createCFWidget();
101
102   newRelocBlock->preserveBlockGap();
103
104   return newRelocBlock;
105 }
106   
107 RelocBlock *RelocBlock::createInst(instPoint *p, Address a, block_instance *block, func_instance *f) {
108   if (!p) return NULL;
109   if (p->empty()) return NULL;
110
111   RelocBlock *newRelocBlock = new RelocBlock(a, block, f);
112   newRelocBlock->elements_.push_back(InstWidget::create(p));
113   newRelocBlock->createCFWidget();
114   
115   return newRelocBlock;
116 }
117
118 RelocBlock *RelocBlock::createStub(block_instance *block, func_instance *f) {
119    RelocBlock *newRelocBlock = new RelocBlock(block->start(), block, f);
120    newRelocBlock->createCFWidget();
121    newRelocBlock->type_ = Stub; 
122    return newRelocBlock;
123 }
124
125
126
127
128 bool RelocBlock::linkRelocBlocks(RelocGraph *cfg) {
129    // We want to build each RelocBlock into a tangled web. Or at 
130    // least build in links to successor RelocBlocks. This is pretty much
131    // only for our internal code generation requirements;
132    // if you want real CFG traversibility use the Block representation.
133    
134    getPredecessors(cfg);
135    getSuccessors(cfg);
136
137    return true;
138 }
139
140 void RelocBlock::getSuccessors(RelocGraph *cfg) {
141    // We're constructing a copy of a subgraph of the CFG. Initially we just copy the nodes
142    // (aka RelocBlocks), but we also need to copy edges. There are three types of edges we care
143    // care about:
144    // Edges to a block that corresponds to a RelocBlock (RelocBlockEdges)
145    // Edges to a block that does not correspond to a RelocBlock (BlockEdges)
146    // Edges to a raw address, caused by representing inter-CodeObject edges
147    //   -- this last is a Defensive mode special.
148   /*   const block_instance::edgelist &targets = block_->targets();
149        for (block_instance::edgelist::const_iterator iter = targets.begin(); iter != targets.end(); ++iter) {*/
150    const PatchBlock::edgelist &targets = block_->targets();
151    for (PatchBlock::edgelist::const_iterator iter = targets.begin(); iter != targets.end(); ++iter) {
152      processEdge(OutEdge, SCAST_EI(*iter), cfg);
153    }
154 }
155
156 void RelocBlock::getPredecessors(RelocGraph *cfg) {
157    const PatchBlock::edgelist &edges = block_->sources();
158    for (PatchBlock::edgelist::const_iterator iter = edges.begin(); iter != edges.end(); ++iter) {
159      processEdge(InEdge, SCAST_EI(*iter), cfg);
160    }
161
162 }
163
164 // There's some tricky logic going on here. We want to create the following
165 // edges:
166 // 1) All out-edges, as _someone_ has to create them
167 // 2) In-edges that aren't from RelocBlocks; if it's from a RelocBlock we assume we'll
168 //    get it in out-edge construction. 
169
170 void RelocBlock::processEdge(EdgeDirection e, edge_instance *edge, RelocGraph *cfg) {
171    ParseAPI::EdgeTypeEnum type = edge->type();
172    // Maybe we want exception edges too?
173    if (type == ParseAPI::RET || 
174        type == ParseAPI::NOEDGE) return;
175    
176    if (edge->sinkEdge()) {
177       assert(e == OutEdge);
178       // We can get sink edges in the following situations:
179       //   1) Existence of indirect control flow.
180       //   2) An edge between CodeObjects
181       //   3) An edge whose target was deleted as part of a code update
182       //   4) An abrupt end if we think we're parsing garbage
183       //   5) A call that may tamper with its return address or not return
184       // In these cases we run with "mimic the original code behavior"
185       switch (type) {
186          case ParseAPI::CALL:
187          case ParseAPI::COND_TAKEN:
188          case ParseAPI::DIRECT: {
189             bool valid;
190             Address addr;
191             boost::tie(valid, addr) = getJumpTarget();
192             if (valid) {
193                cfg->makeEdge(new Target<RelocBlock *>(this), 
194                              new Target<Address>(addr),
195                              edge, 
196                              type);
197             }
198             break;
199          }
200          case ParseAPI::COND_NOT_TAKEN:
201          case ParseAPI::FALLTHROUGH:
202          case ParseAPI::CALL_FT: {
203
204             cfg->makeEdge(new Target<RelocBlock *>(this), 
205                           new Target<Address>(block_->end()),
206                           edge,
207                           type);
208             break;
209          }
210          default:
211             break;
212       }
213    }
214    else {
215       block_instance *block = (e == OutEdge) ? edge->trg() : edge->src();
216
217       func_instance *f = NULL;
218       // Let's determine the function. If this is an interprocedural edge,
219       // then block must be an entry block and we use its function. Otherwise
220       // we use ours.
221       if (edge->interproc()) {
222          f = block->entryOfFunc();
223       }
224       else {
225          f = func();
226       }
227
228       RelocBlock *t = cfg->find(block, f);
229       if (t) {
230          if (e == OutEdge) {
231             cfg->makeEdge(new Target<RelocBlock *>(this), 
232                           new Target<RelocBlock *>(t),
233                           edge,
234                           type);
235             return;
236          }
237          else {
238             // RelocBlock -> trace edge, will get created later
239             return;
240          }
241       }
242       else {
243          if (e == OutEdge) {
244             cfg->makeEdge(new Target<RelocBlock *>(this), 
245                           new Target<block_instance *>(block),
246                           edge,
247                           type);
248          }
249          else {
250             cfg->makeEdge(new Target<block_instance *>(block), 
251                           new Target<RelocBlock *>(this),
252                           edge,
253                           type);
254          }
255       }
256    }
257 }
258
259
260 bool RelocBlock::determineSpringboards(PriorityMap &p) {
261    // We _require_ a springboard if:
262    // 1) We are a function entry block;
263    // 2) We are the target of an indirect branch;
264    // 3) We are the target of an edge not from a trace. 
265
266    if (func_ &&
267        func_->entryBlock() == block_) {
268      relocation_cerr << "determineSpringboards (entry block): " << func_->symTabName()
269                      << " / " << hex << block_->start() << " is required" << dec << endl;
270       p[std::make_pair(block_, func_)] = FuncEntry;
271       return true;
272    }
273    if (inEdges_.contains(ParseAPI::INDIRECT)) {
274      relocation_cerr << "determineSpringboards (indirect target): " << func_->symTabName()
275                      << " / " << hex << block_->start() << " is required" << dec << endl;
276       p[std::make_pair(block_, func_)] = IndirBlockEntry;
277       return true;
278    }
279    // Slow crawl
280    for (RelocEdges::const_iterator iter = inEdges_.begin();
281         iter != inEdges_.end(); ++iter) {
282      if ((*iter)->type == ParseAPI::CALL) continue;
283      /* Skip tailcalls also */
284      edge_instance* edge = (*iter)->edge;
285      if (edge) {
286          if (edge->interproc() && 
287             (((*iter)->type == ParseAPI::DIRECT) || ((*iter)->type == ParseAPI::INDIRECT))) {
288              continue;
289          }
290      }
291       if ((*iter)->src->type() != TargetInt::RelocBlockTarget) {
292         relocation_cerr << "determineSpringboards (non-relocated source): " << func_->symTabName()
293                         << " / " << hex << block_->start() << " is required (type "
294                         << (*iter)->src->type() << ")" << dec << endl;
295         relocation_cerr << "\t" << (*iter)->src->format() << endl;
296         p[std::make_pair(block_, func_)] = Suggested;
297          return true;
298       }
299    }
300    return true;
301 }
302
303
304 void RelocBlock::createCFWidget() {
305    // If the last instruction in the trace is a CF instruction 
306    // (jump, call, etc.) wrap it in a CFWidget pointer and replace.
307    // Otherwise, create a default CFWidget and append it. In either case,
308    // keep a handle to the atom in cfWidget_.
309
310    if (elements_.empty()) {
311       cfWidget_ = CFWidget::create(origAddr_);
312       elements_.push_back(cfWidget_); 
313       return;
314    }
315
316    bool hasCF = false;
317
318    InstructionAPI::Instruction insn = elements_.back()->insn();
319    if (insn.isValid()) {
320       if (insn.getCategory() == c_CallInsn ||
321           insn.getCategory() == c_ReturnInsn ||
322           insn.getCategory() == c_BranchInsn) {
323          hasCF = true;
324       }
325    }
326
327    if (hasCF) {
328       cfWidget_ = CFWidget::create(elements_.back());
329       elements_.pop_back();
330    }
331    else {
332       cfWidget_ = CFWidget::create(origAddr_);
333    }
334    elements_.push_back(cfWidget_);
335 }
336
337 // Some defensive binaries put gaps in after call instructions to try
338 // and confuse parsing; it's typically something like so:
339 //
340 // call foo
341 // jmp <offset>
342 //
343 // where foo contains code that increments the stack pointer by one,
344 // and <offset> is the encoding of a legal instruction. We really need
345 // to preserve that gap if it exists, and to make life easy we bundle
346 // it into the CFWidget.
347
348 #if defined(arch_x86) || defined(arch_x86_64)
349 #define DEFENSIVE_GAP_SIZE 10
350 #else
351 #define DEFENSIVE_GAP_SIZE 12
352 #endif
353
354 void RelocBlock::preserveBlockGap() {
355   /*   const block_instance::edgelist &targets = block_->targets();
356        for (block_instance::edgelist::const_iterator iter = targets.begin(); iter != targets.end(); ++iter) {*/
357    if (block_->wasUserAdded()) return;
358    const PatchBlock::edgelist &targets = block_->targets();
359    bool hasCall = false;
360    bool hasFT = false;
361    for (auto iter = targets.begin(); iter != targets.end(); ++iter) {
362       if ((*iter)->type() == ParseAPI::CALL) {
363          hasCall = true;
364       }
365       if ((*iter)->trg()->wasUserAdded()) {
366          // DO NOT ADD A GAP. 
367          continue;
368       }
369       if ((*iter)->type() == ParseAPI::CALL_FT ||
370           (*iter)->type() == ParseAPI::FALLTHROUGH ||
371           (*iter)->type() == ParseAPI::COND_NOT_TAKEN) {
372          // Okay, I admit - I want to see this code trigger in the
373          // fallthrough or cond_not_taken cases...
374          hasFT = true;
375          block_instance *target = SCAST_EI(*iter)->trg();
376          if (target && !(*iter)->sinkEdge()) {
377             if (target->start() < block_->end()) {
378                cerr << "Error: source should precede target; edge type " << ParseAPI::format((*iter)->type()) << hex
379                     << " src[" << block_->start() << " " << block_->end()
380                     << "] trg[" << target->start() << " " << target->end() << dec << "]" << endl;
381                assert(0);
382             }
383             cfWidget()->setGap(target->start() - block_->end());
384             return;
385          }
386          else {
387             cfWidget()->setGap(DEFENSIVE_GAP_SIZE);
388          }
389       }
390    }
391    if (hasCall && !hasFT) {
392       cfWidget()->setGap(DEFENSIVE_GAP_SIZE);
393    }
394 }
395
396 // Do the raw computation to determine the target (if it exists) of a
397 // jump instruction that we may not have encoded in ParseAPI.
398
399 std::pair<bool, Address> RelocBlock::getJumpTarget() {
400    InstructionAPI::Instruction insn = cfWidget()->insn();
401    if (!insn.isValid()) return std::make_pair(false, 0);
402
403    Expression::Ptr cft = insn.getControlFlowTarget();
404    if (!cft) return std::make_pair(false, 0);
405
406    Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn.getArch())));
407    
408    cft->bind(thePC.get(), Result(u64, cfWidget()->addr()));
409    Result res = cft->eval();
410    if (res.defined) {
411       return std::make_pair(true, res.convert<Address>());
412    }
413    return std::make_pair(false, 0);
414 }
415
416 // We put in edges for everything - jumps, fallthroughs, you name
417 // it. Some of these can be obviated by code layout. Instead of trying
418 // to precompute which branches are needed, we do a final
419 // pre-generation pass to run through and see which branches we need
420 // based on where we plan to lay blocks out.
421 //
422 // Side note: necessary is set on a per-Target basis. 
423
424 void RelocBlock::determineNecessaryBranches(RelocBlock *successor) {
425    for (CFWidget::DestinationMap::const_iterator d_iter = cfWidget_->destinations().begin();
426         d_iter != cfWidget_->destinations().end(); ++d_iter) {
427       if (d_iter->first != CFWidget::Taken &&
428           d_iter->first != CFWidget::Fallthrough) continue;
429
430       d_iter->second->setNecessary(true);
431
432       if (d_iter->second->matches(successor)) {
433          // A candidate for setting as non-necessary. However, there
434          // are some overrides...
435          //   1) An old one that was in there was if we had post-CF 
436          //      instruction padding, be sure to set this as necessary.
437          //      However, I'm not sure this can realistically happen...
438
439
440          //   2) If the block consisted only of a jump, be sure to keep it
441          //      so that we don't entirely remove original blocks.
442          if ((elements().size() == 1) &&
443              (cfWidget_->destinations().size() == 1)) {
444             continue;
445          }
446          d_iter->second->setNecessary(false);
447       }
448    }
449 }   
450
451 // Each RelocBlock generates a mixture of PIC and non-PIC code. For
452 // efficiency, we precompute the PIC code and generate function callbacks
453 // for the non-PIC code. Thus, what we hand into the code generator
454 // looks like so:
455 //
456 // PIC
457 // PIC
458 // PIC
459 // non-PIC callback
460 // PIC
461 // non-PIC callback
462 // PIC
463 // PIC
464 // ...
465 //
466 // This allows us to minimize unnecessary regeneration when we're trying
467 // to produce the final code sequence. This function generates the mixture
468 // of PIC (as a byte buffer) and non-PIC (in terms of Patch objects) sequences.
469
470
471 bool RelocBlock::generate(const codeGen &templ,
472                           CodeBuffer &buffer) {
473    relocation_cerr << "Generating block " << id() << " orig @ " << hex << origAddr() << dec << endl;
474    relocation_cerr << "\t" << elements_.size() << " elements" << endl; 
475    relocation_cerr << "\t At entry, code buffer has size " << buffer.size() << endl;
476   
477    // Register ourselves with the CodeBuffer and get a label
478    label_ = buffer.getLabel();
479
480    codeGen ourTemplate;
481    ourTemplate.applyTemplate(templ);
482    ourTemplate.setFunction(func());
483
484    relocation_cerr << "\t With function " << (func() ? func()->name() : "<NULL>") << endl;
485
486    // Simple form: iterate over every Widget, in order, and generate it.
487    for (WidgetList::iterator iter = elements_.begin(); iter != elements_.end(); ++iter) {
488       if (!(*iter)->generate(ourTemplate, 
489                              this,
490                              buffer)) {
491          cerr << "Failed to generate widget: " << (*iter)->format() << endl;
492          return false;
493          // This leaves the block in an inconsistent state and should only be used
494          // for fatal failures.
495       }
496    }
497    
498    relocation_cerr << "\t At exit, code buffer has size " << buffer.size() << endl;   
499
500    return true;
501 }
502
503 std::string RelocBlock::format() const {
504     stringstream ret;
505   ret << "RelocBlock(" 
506       << func()->obj()->fullName() << ": " << func()->name() << " " 
507       << std::hex << origAddr() << std::dec
508       << "/" << id() << "/" << label_ 
509       << ") {" << endl;
510   for (WidgetList::const_iterator iter = elements_.begin();
511        iter != elements_.end(); ++iter) {
512     ret << "  " << (*iter)->format() << endl;
513   }
514   ret << "In edges: ";
515   for (RelocEdges::const_iterator iter = inEdges_.begin();
516        iter != inEdges_.end(); ++iter) {
517      ret << (*iter)->src->format() << ", ";
518   }
519   ret << endl;
520   ret << "Out edges:";
521   for (RelocEdges::const_iterator iter = outEdges_.begin();
522        iter != outEdges_.end(); ++iter) {
523      ret << (*iter)->trg->format() 
524          << "<" << ParseAPI::format((*iter)->type) << ">, ";
525   }
526   ret << endl;
527
528   ret << "}" << endl;
529   return ret.str();
530 }
531
532 RelocBlock::Label RelocBlock::getLabel() const {
533    if (label_ == -1) {
534       cerr << "Error: trace with zero label!" << endl;
535       cerr << format() << endl;
536       assert(0);
537    }
538    return label_;
539 }
540
541 bool RelocBlock::finalizeCF() {
542    if (!cfWidget_) {
543       cerr << "Warning: trace has no CFWidget!" << endl;
544       cerr << format() << endl;
545       assert(0);
546    }
547
548    // We've had people munging our out-edges; now
549    // push them to the CFWidget so that it can do its work. 
550    for (RelocEdges::iterator iter = outEdges_.begin(); iter != outEdges_.end(); ++iter) {
551       if ((*iter)->type == ParseAPI::CATCH ||
552           (*iter)->type == ParseAPI::RET ||
553           (*iter)->type == ParseAPI::NOEDGE) continue;
554       Address index;
555       if ((*iter)->type == ParseAPI::FALLTHROUGH ||
556           (*iter)->type == ParseAPI::COND_NOT_TAKEN ||
557           (*iter)->type == ParseAPI::CALL_FT) {
558          index = CFWidget::Fallthrough;
559       }
560       else if ((*iter)->type == ParseAPI::DIRECT ||
561                (*iter)->type == ParseAPI::COND_TAKEN ||
562                (*iter)->type == ParseAPI::CALL) {
563          index = CFWidget::Taken;
564       }
565       else {
566          assert((*iter)->type == ParseAPI::INDIRECT);
567          index = (*iter)->trg->origAddr();
568       }
569       cfWidget_->addDestination(index, (*iter)->trg);
570       (*iter)->trg->setNecessary(isNecessary((*iter)->trg, (*iter)->type));
571    }
572    
573    return true;
574 }
575
576 bool RelocBlock::isNecessary(TargetInt *target,
577                         ParseAPI::EdgeTypeEnum edgeType) {
578    if (!next_) return true;
579
580    // Code copied from the old Fallthrough transformer
581
582    // Case 1: if we're a single direct branch, be sure we don't
583    // elide, or the CFG gets messed up. 
584    // ... or does it...
585    if (elements_.size() == 1 &&
586        (edgeType == ParseAPI::DIRECT ||
587         edgeType == ParseAPI::COND_TAKEN))
588       return true;
589
590    // Case 2: keep calls, d00d
591    if (edgeType == ParseAPI::CALL) return true;
592    
593    // Case 3: if the CFWidget wants a gap, a gap it gets
594    if (cfWidget_->gap() != 0) return true;
595
596    // And finally, case 4: if the next trace isn't our target, keep it
597    if (!target->matches(next_)) return true;
598
599    return false;
600 }
601
602 void RelocBlock::setCF(CFWidgetPtr cf) {
603    elements_.pop_back();
604    elements_.push_back(cf);
605    cfWidget_ = cf;
606 }
607