Merge branch 'master' into att_syntax
[dyninst.git] / dyninstAPI / src / Relocation / Transformers / Movement-adhoc.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 "Transformer.h"
32 #include "Movement-adhoc.h"
33 #include "../dyninstAPI/src/debug.h"
34 #include "../Widgets/Widget.h"
35 #include "../Widgets/RelDataWidget.h"
36 #include "../Widgets/StackModWidget.h"
37 #include "../Widgets/CFWidget.h"
38 #include "../Widgets/PCWidget.h"
39 #include "../CFG/RelocBlock.h"
40 #include "dyninstAPI/src/addressSpace.h"
41 #include "instructionAPI/h/InstructionDecoder.h"
42 #include "../CFG/RelocGraph.h"
43 #include "instructionAPI/h/Visitor.h"
44
45 #include "StackMod.h"
46 #include "function.h"
47 #include "dataflowAPI/h/stackanalysis.h"
48
49 using namespace std;
50 using namespace Dyninst; 
51 using namespace Relocation;
52 using namespace InstructionAPI;
53
54
55 bool adhocMovementTransformer::process(RelocBlock *cur, RelocGraph *cfg) {
56   // Identify PC-relative data accesses
57   // and "get PC" operations and replace them
58   // with dedicated Widgets
59
60    RelocBlock::WidgetList &elements = cur->elements();
61
62   relocation_cerr << "PCRelTrans: processing block (ID= "
63                   << cur->id() << ") " 
64                   << cur << " with "
65                   << elements.size() << " elements." << endl;
66
67 #if defined(cap_stack_mods)
68   // Grab some stack modification data structures if we need them
69   OffsetVector* offVec = NULL;
70   TMap* tMap = NULL;
71   if (cur->func()->hasStackMod()) {
72     // Make sure we have an offset vector and transformation mapping.  We
73     // shouldn't be able to get to relocation without having generated these.
74     if (!cur->func()->hasOffsetVector()) {
75       cur->func()->createOffsetVector();
76     }
77     offVec = cur->func()->getOffsetVector();
78     assert(offVec);
79
80     if (!cur->func()->hasValidOffsetVector()) {
81       // We should not be able to get here, but enforce that we don't
82       return false;
83     }
84
85     tMap = cur->func()->getTMap();
86     assert(tMap);
87   }
88 #endif
89
90   for (RelocBlock::WidgetList::iterator iter = elements.begin();
91        iter != elements.end(); ++iter) {
92     // Can I do in-place replacement? Apparently I can...
93     // first insert new (before iter) and then remove iter
94
95     // Cache this so we don't re-decode...
96     InsnPtr insn = (*iter)->insn();
97     if (!insn) continue;
98
99     Address target = 0;
100     Absloc aloc;
101
102     if (isPCDerefCF(*iter, insn, target)) {
103        CFWidget::Ptr cf = boost::dynamic_pointer_cast<CFWidget>(*iter);
104        assert(cf);
105        cf->setOrigTarget(target);
106     }
107     if (isPCRelData(*iter, insn, target)) {
108       relocation_cerr << "  ... isPCRelData at " 
109                       << std::hex << (*iter)->addr() << std::dec << endl;
110       // Two options: a memory reference or a indirect call. The indirect call we 
111       // just want to set target in the CFWidget, as it has the hardware to handle
112       // control flow. Generic memory references get their own atoms. How nice. 
113       Widget::Ptr replacement = RelDataWidget::create(insn,
114                                                      (*iter)->addr(),
115                                                      target);
116       (*iter).swap(replacement);
117       
118     }
119     else if (isGetPC(*iter, insn, aloc, target)) {
120
121       Widget::Ptr replacement = PCWidget::create(insn,
122                                                (*iter)->addr(),
123                                                aloc,
124                                                target);
125       // This is kind of complex. We don't want to just pull the getPC
126       // because it also might end the basic block. If that happens we
127       // need to pull the fallthough element out of the CFWidget so
128       // that we don't hork control flow. What a pain.
129       if ((*iter) != elements.back()) {
130         // Easy case; no worries.
131         (*iter).swap(replacement);
132       }
133       else {
134          // Remove the taken edge from the trace, as we're removing
135          // the call and replacing it with a GetPC operation. 
136          Predicates::Interprocedural pred;
137          bool removed = cfg->removeEdge(pred, cur->outs());
138          assert(removed);
139             
140          // Before we forget: swap in the GetPC for the current element
141          (*iter).swap(replacement);            
142          break;
143       }
144     }
145 #if defined(cap_stack_mods)
146     else {
147       // If we have stack modifications, check for sensitive instructions;
148       // we must update the displacement encoded in these instructions
149       if (cur->func()->hasStackMod() && cur->func()->getMods()->size()) {
150         const Accesses* accesses = cur->func()->getAccesses((*iter)->addr());
151         // If this function makes no stack accesses, no need to perform
152         // analysis; there won't be any sensitive instructions
153         if (!accesses) {
154           continue;
155         }
156
157         // Perform check and generate StackModWidget if necessary
158         Offset origDisp;
159         signed long delta;
160         Architecture arch = insn->getArch();
161         stackmods_printf("Checking isStackFrameSensitive @ 0x%lx = %s\n",
162           (*iter)->addr(), insn->format().c_str());
163         if (isStackFrameSensitive(origDisp, delta, accesses, offVec, tMap,
164           cur->block()->llb(), (*iter)->addr())) {
165           signed long newDisp = origDisp + delta;
166
167           stackmods_printf(" ... is Stack Frame SENSITIVE at 0x%lx\n",
168             (*iter)->addr());
169           stackmods_printf("\t\t origDisp = %ld, delta = %ld, newDisp = %ld\n",
170             origDisp, delta, newDisp);
171
172           relocation_cerr << " ... is Stack Frame Sensitive at "
173             << std::hex << (*iter)->addr()
174             << std::dec
175             << ", origDisp = " << origDisp
176             << ", delta = " << delta
177             << ", newDisp = " << newDisp
178             << endl;
179
180           Widget::Ptr replacement = StackModWidget::create(insn,
181             (*iter)->addr(), newDisp, arch);
182           (*iter).swap(replacement);
183         }
184       }
185     }
186 #endif
187   }
188   return true;
189 }
190
191 bool adhocMovementTransformer::isPCDerefCF(Widget::Ptr ptr,
192                                            InsnPtr insn,
193                                            Address &target) {
194    Expression::Ptr cf = insn->getControlFlowTarget();
195    if (!cf) return false;
196    
197 //   Architecture fixme = insn->getArch();
198 //   if (fixme == Arch_ppc32) fixme = Arch_ppc64;
199    
200    Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
201 //   Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
202
203    // Okay, see if we're memory
204    set<Expression::Ptr> mems;
205    insn->getMemoryReadOperands(mems);
206    
207    for (set<Expression::Ptr>::const_iterator iter = mems.begin();
208         iter != mems.end(); ++iter) {
209       Expression::Ptr exp = *iter;
210       if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size()))) {
211         // Bind succeeded, eval to get target address
212         Result res = exp->eval();
213         if (!res.defined) {
214           cerr << "ERROR: failed bind/eval at " << std::hex << ptr->addr() << endl;if (insn->getControlFlowTarget()) return false;
215         }
216         assert(res.defined);
217         target = res.convert<Address>();
218         break;
219       }
220    }
221    if (target) return true;
222    return false;
223 }
224
225
226
227 // We define this as "uses PC and is not control flow"
228 bool adhocMovementTransformer::isPCRelData(Widget::Ptr ptr,
229                                            InsnPtr insn,
230                                            Address &target) {
231   target = 0;
232   if (insn->getControlFlowTarget()) return false;
233
234   //Architecture fixme = insn->getArch();
235   //if (fixme == Arch_ppc32) fixme = Arch_ppc64;
236   
237   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
238   //Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
239
240   if (!insn->isRead(thePC))
241     //&&
242 //      !insn->isRead(thePCFixme))
243     return false;
244
245   // Okay, see if we're memory
246   set<Expression::Ptr> mems;
247   insn->getMemoryReadOperands(mems);
248   insn->getMemoryWriteOperands(mems);
249   for (set<Expression::Ptr>::const_iterator iter = mems.begin();
250        iter != mems.end(); ++iter) {
251     Expression::Ptr exp = *iter;
252     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size()))) {
253
254     //||
255         //exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
256       // Bind succeeded, eval to get target address
257       Result res = exp->eval();
258       if (!res.defined) {
259         cerr << "ERROR: failed bind/eval at " << std::hex << ptr->addr() << endl;
260         continue;
261       }
262       assert(res.defined);
263       target = res.convert<Address>();
264       return true;
265     }
266   }
267
268   // Didn't use the PC to read memory; thus we have to grind through
269   // all the operands. We didn't do this directly because the 
270   // memory-topping deref stops eval...
271   vector<Operand> operands;
272   insn->getOperands(operands);
273   for (vector<Operand>::iterator iter = operands.begin();
274        iter != operands.end(); ++iter) {
275     // If we can bind the PC, then we're in the operand
276     // we want.
277     Expression::Ptr exp = iter->getValue();
278     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size()))) {
279         //||
280         //exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
281       // Bind succeeded, eval to get target address
282       Result res = exp->eval();
283       assert(res.defined);
284       target = res.convert<Address>();
285       return true;
286     }
287   }
288   if (target == 0) {
289      cerr << "Error: failed to bind PC in " << insn->format() << endl;
290   }
291   assert(target != 0);
292   return true;    
293 }
294
295 class thunkVisitor : public InstructionAPI::Visitor
296 {
297 public:
298   thunkVisitor() : isThunk(true), foundSP(false), foundDeref(false) {}
299   virtual ~thunkVisitor() {}
300
301   bool isThunk;
302   bool foundSP;
303   bool foundDeref;
304
305   virtual void visit(BinaryFunction*)
306   {
307     relocation_cerr << "\t binfunc, ret false" << endl;
308     isThunk = false;
309   }
310
311   virtual void visit(Immediate*)
312   {
313     relocation_cerr << "\t imm, ret false" << endl;
314     isThunk = false;
315   }
316   virtual void visit(RegisterAST* r)
317   {
318     if (foundSP) {
319       isThunk = false;
320     }
321     else if (!r->getID().isStackPointer()) {
322       isThunk = false;
323     }
324     else {
325       foundSP = true;
326     }
327   }
328   virtual void visit(Dereference* )
329   {
330     if (foundDeref) {
331       isThunk = false;
332     }
333     if (!foundSP) {
334       isThunk = false;
335     }
336     foundDeref = true;
337   }  
338 };
339
340
341 bool adhocMovementTransformer::isGetPC(Widget::Ptr ptr,
342                                        InsnPtr insn,
343                                        Absloc &aloc,
344                                        Address &thunk) {
345   // TODO:
346   // Check for call + size;
347   // Check for call to thunk.
348   // TODO: need a return register parameter.
349
350    if (insn->getCategory() != InstructionAPI::c_CallInsn) return false;
351
352   // Okay: checking for call + size
353   Expression::Ptr CFT = insn->getControlFlowTarget();
354   if (!CFT) {
355     relocation_cerr << "      ... no CFT, ret false from isGetPC" << endl;
356     return false;
357   }
358    
359
360   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
361
362   switch(insn->getArch()) {
363      case Arch_x86:
364      case Arch_ppc32:
365         CFT->bind(thePC.get(), Result(u32, ptr->addr()));
366         break;
367      case Arch_x86_64:
368      case Arch_ppc64:
369         CFT->bind(thePC.get(), Result(u64, ptr->addr()));
370         break;
371      default:
372         assert(0);
373         break;
374   }
375
376   Result res = CFT->eval();
377
378   if (!res.defined) {
379     relocation_cerr << "      ... CFT not evallable, ret false from isGetPC" << endl;
380     return false;
381   }
382
383   Address target = res.convert<Address>();
384
385   if (target == (ptr->addr() + insn->size())) {
386     aloc = Absloc(0, 0, NULL);
387     relocation_cerr << "      ... call next insn, ret true" << endl;
388     return true;
389   }
390
391   // Check for a call to a thunk function
392   // TODO: replace entirely with sensitivity analysis. But for now? 
393   // Yeah.
394   
395   // This is yoinked from arch-x86.C...
396   if (addrSpace->isValidAddress(target)) {
397     // Get us an instrucIter    
398     const unsigned char* buf = reinterpret_cast<const unsigned char*>(addrSpace->getPtrToInstruction(target));
399     if (!buf) {
400        cerr << "Error: illegal pointer to buffer!" << endl;
401        cerr << "Target of " << hex << target << " from addr " << ptr->addr() << " in insn " << insn->format() << dec << endl;
402        assert(0);
403     }
404
405     InstructionDecoder decoder(buf,
406                                2*InstructionDecoder::maxInstructionLength,
407                                addrSpace->getArch());
408
409     Instruction::Ptr firstInsn = decoder.decode();
410     Instruction::Ptr secondInsn = decoder.decode();
411
412     relocation_cerr << "      ... decoded target insns "
413                     << firstInsn->format() << ", " 
414                     << secondInsn->format() << endl;
415
416     if(firstInsn && firstInsn->getOperation().getID() == e_mov
417        && firstInsn->readsMemory() && !firstInsn->writesMemory()
418        && secondInsn && secondInsn->getCategory() == c_ReturnInsn) {
419
420       thunkVisitor visitor;
421       relocation_cerr << "Checking operand " << firstInsn->getOperand(1).format(firstInsn->getFormatter(), firstInsn->getArch()) << endl;
422       firstInsn->getOperand(1).getValue()->apply(&visitor);
423       if (!visitor.isThunk) return false;
424
425 #if 0
426       // Check to be sure we're reading memory
427       std::set<RegisterAST::Ptr> reads;
428       firstInsn->getReadSet(reads);
429       bool found = false;
430       for (std::set<RegisterAST::Ptr>::iterator iter = reads.begin();
431            iter != reads.end(); ++iter) {
432         if ((*iter)->getID().isStackPointer()) {
433           found = true;
434           break;
435         }
436       }
437       if (!found) return false;
438
439 #endif
440       
441       std::set<RegisterAST::Ptr> writes;
442       firstInsn->getWriteSet(writes);
443       assert(writes.size() == 1);
444       aloc = Absloc((*(writes.begin()))->getID());
445       thunk = target;
446       return true;
447     }
448   }
449   else {     
450      relocation_cerr << "\t Call to " << hex << target << " is not valid address, concluding not thunk" << dec << endl;
451   }
452   return false;
453 }
454
455 #if defined(cap_stack_mods)
456 // Determines if an instruction is stack frame sensitive (i.e. needs to be
457 // updated with a new displacement).  If so, returns in delta the amount by
458 // which the displacement needs to be updated.
459 bool adhocMovementTransformer::isStackFrameSensitive(Offset& origDisp,
460     signed long& delta,
461     const Accesses* accesses,
462     OffsetVector*& offVec,
463     TMap*& tMap,
464     ParseAPI::Block* block,
465     Address addr)
466 {
467     // Track changes after transformations are applied
468     StackAnalysis::Height regDelta(0);  // Change in base register height
469     StackAnalysis::Height readDelta(0);  // Change in access height
470
471     bool ret = false;
472     for (auto iter = accesses->begin(); iter != accesses->end(); ++iter) {
473         MachRegister curReg = (*iter).first;
474         StackAccess* access = (*iter).second;
475
476         // The original difference between base register height and access
477         // height
478         origDisp = access->disp();
479
480         stackmods_printf("\t %s\n", access->format().c_str());
481
482         StackAnalysis::Height regHeightPrime = access->regHeight();
483         StackAnalysis::Height readHeightPrime = access->readHeight();
484
485         stackmods_printf("\t\t regHeight = %ld, readHeight = %ld\n",
486             access->regHeight().height(), access->readHeight().height());
487
488         // Idea: Check for exact match first, then check for overlaps.  This
489         // should fix the case where we add an exact match. However, find is
490         // going to search for any match, so we need to look ourselves.
491
492         bool foundReg = false;
493         bool foundRead = false;
494
495         // Find any updates to regHeight or readHeight (exact matches)
496         for (auto tIter = tMap->begin(); (!foundReg || !foundRead) &&
497             tIter != tMap->end(); ++tIter) {
498             StackLocation* src = (*tIter).first;
499             StackLocation* dest = (*tIter).second;
500
501             stackmods_printf("\t\t\t Checking %s -> %s\n",
502                 src->format().c_str(), dest->format().c_str());
503
504             if (src->isStackMemory() && dest->isStackMemory()) {
505                 if (src->isRegisterHeight()) {
506                     if (src->off() == access->regHeight()) {
507                         int tmp;
508                         if (src->valid() && !src->valid()->find(addr, tmp)) {
509                             stackmods_printf("\t\t\t\t Matching src height not "
510                                 "valid for this PC\n");
511                             continue;
512                         }
513
514                         if (src->reg() == curReg) {
515                             foundReg = true;
516                             assert(!offVec->isSkip(curReg, access->regHeight(),
517                                 block->start(), addr));
518                             regHeightPrime = dest->off();
519                             stackmods_printf("\t\t\t\t regHeight' = %ld\n",
520                                 regHeightPrime.height());
521                         }
522                     }
523                 } else {
524                     if (src->off() == access->readHeight()) {
525                         int tmp;
526                         if (src->valid() && !src->valid()->find(addr, tmp)) {
527                             stackmods_printf("\t\t\t\t Matching src height not "
528                                 "valid for this PC\n");
529                             continue;
530                         }
531
532                         foundRead = true;
533                         readHeightPrime = dest->off();
534                         stackmods_printf("\t\t\t\t readHeight' = %ld\n",
535                             readHeightPrime.height());
536                     }
537                 }
538             } else if (src->isNull()) {
539                 stackmods_printf("\t\t\t\t Ignoring: insertion\n");
540             } else {
541                 assert(0);
542             }
543         }
544
545         // Still necessary because accesses contained inside other accesses may
546         // not have an exact offset match in O.
547         // Look for ranges that include the readHeight.
548         for (auto tIter = tMap->begin(); !foundRead && tIter != tMap->end();
549             ++tIter) {
550             StackLocation* src = (*tIter).first;
551             StackLocation* dest = (*tIter).second;
552
553             stackmods_printf("\t\t\t Checking %s -> %s\n",
554                 src->format().c_str(), dest->format().c_str());
555             if (src->isStackMemory() && dest->isStackMemory()) {
556                 if (src->isRegisterHeight()) {
557                     // Nothing to do
558                 } else {
559                     if (src->off() < access->readHeight() &&
560                         access->readHeight() < src->off() + src->size()) {
561                         int tmp;
562                         if (src->valid() && !src->valid()->find(addr, tmp)) {
563                             stackmods_printf("\t\t\t\t Matching src height not "
564                                 "valid for this PC\n");
565                             continue;
566                         }
567                         foundRead = true;
568                         readHeightPrime = dest->off() +
569                             (access->readHeight() - src->off());
570                         stackmods_printf("\t\t\t\t readHeight' = %ld\n",
571                             readHeightPrime.height());
572                     }
573                 }
574             }
575         }
576
577         regDelta += access->regHeight() - regHeightPrime;
578         readDelta += access->readHeight() - readHeightPrime;
579     }
580
581     if (regDelta != readDelta) {
582         ret = true;
583         delta = regDelta.height() - readDelta.height();
584     }
585
586     return ret;
587 }
588 #endif