Define cap_stack_mods and properly limit stack mods to x86,x86_64
[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 " 
63                   << cur << " with "
64                   << elements.size() << " elements." << endl;
65
66 #if defined(cap_stack_mods)
67   // Grab some stack modification data structures if we need them
68   OffsetVector* offVec;
69   TMap* tMap;
70   if (cur->func()->hasStackMod()) {
71     // Make sure we have an offset vector and transformation mapping
72     // - We shouldn't be able to get to relocation without having generated these
73     if (!cur->func()->hasOffsetVector()) {
74         cur->func()->createOffsetVector();
75     }
76     offVec = cur->func()->getOffsetVector();
77     assert(offVec);
78
79     if (!cur->func()->hasValidOffsetVector()) {
80         // We should not be able to get here, but enforce that we do don't
81         return false;
82     }
83
84     tMap = cur->func()->getTMap();
85     assert(tMap);
86   }
87 #endif
88
89   for (RelocBlock::WidgetList::iterator iter = elements.begin();
90        iter != elements.end(); ++iter) {
91     // Can I do in-place replacement? Apparently I can...
92     // first insert new (before iter) and then remove iter
93
94     // Cache this so we don't re-decode...
95     InsnPtr insn = (*iter)->insn();
96
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 analysis;
152             // 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", (*iter)->addr(), insn->format().c_str());
162             if (isStackFrameSensitive(origDisp,
163                         delta,
164                         accesses, offVec, tMap,
165                         cur->block()->llb(), (*iter)->addr())) {
166
167                 signed long newDisp = origDisp + delta;
168
169                 stackmods_printf(" ... is Stack Frame SENSITIVE at 0x%lx\n", (*iter)->addr());
170                 stackmods_printf("\t\t origDisp = %ld, delta = %ld, newDisp = %ld\n",
171                         origDisp, delta, newDisp);
172
173                 relocation_cerr << " ... is Stack Frame Sensitive at "
174                     << std::hex << (*iter)->addr()
175                     << std::dec
176                     << ", origDisp = " << origDisp
177                     << ", delta = " << delta
178                     << ", newDisp = " << newDisp
179                     << endl;
180
181                 Widget::Ptr replacement = StackModWidget::create(insn,
182                         (*iter)->addr(),
183                         newDisp,
184                         arch);
185                 (*iter).swap(replacement);
186             }
187         }
188     }
189 #endif
190   }
191   return true;
192 }
193
194 bool adhocMovementTransformer::isPCDerefCF(Widget::Ptr ptr,
195                                            InsnPtr insn,
196                                            Address &target) {
197    Expression::Ptr cf = insn->getControlFlowTarget();
198    if (!cf) return false;
199    
200    Architecture fixme = insn->getArch();
201    if (fixme == Arch_ppc32) fixme = Arch_ppc64;
202    
203    Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
204    Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
205
206    // Okay, see if we're memory
207    set<Expression::Ptr> mems;
208    insn->getMemoryReadOperands(mems);
209    
210    for (set<Expression::Ptr>::const_iterator iter = mems.begin();
211         iter != mems.end(); ++iter) {
212       Expression::Ptr exp = *iter;
213       if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
214           exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
215         // Bind succeeded, eval to get target address
216         Result res = exp->eval();
217         if (!res.defined) {
218           cerr << "ERROR: failed bind/eval at " << std::hex << ptr->addr() << endl;if (insn->getControlFlowTarget()) return false;
219         }
220         assert(res.defined);
221         target = res.convert<Address>();
222         break;
223       }
224    }
225    if (target) return true;
226    return false;
227 }
228
229
230
231 // We define this as "uses PC and is not control flow"
232 bool adhocMovementTransformer::isPCRelData(Widget::Ptr ptr,
233                                            InsnPtr insn,
234                                            Address &target) {
235   target = 0;
236   if (insn->getControlFlowTarget()) return false;
237
238   Architecture fixme = insn->getArch();
239   if (fixme == Arch_ppc32) fixme = Arch_ppc64;
240   
241   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
242   Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
243
244   if (!insn->isRead(thePC) &&
245       !insn->isRead(thePCFixme))
246     return false;
247
248   // Okay, see if we're memory
249   set<Expression::Ptr> mems;
250   insn->getMemoryReadOperands(mems);
251   insn->getMemoryWriteOperands(mems);
252   for (set<Expression::Ptr>::const_iterator iter = mems.begin();
253        iter != mems.end(); ++iter) {
254     Expression::Ptr exp = *iter;
255     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
256         exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
257       // Bind succeeded, eval to get target address
258       Result res = exp->eval();
259       if (!res.defined) {
260         cerr << "ERROR: failed bind/eval at " << std::hex << ptr->addr() << endl;
261         continue;
262       }
263       assert(res.defined);
264       target = res.convert<Address>();
265       return true;
266     }
267   }
268
269   // Didn't use the PC to read memory; thus we have to grind through
270   // all the operands. We didn't do this directly because the 
271   // memory-topping deref stops eval...
272   vector<Operand> operands;
273   insn->getOperands(operands);
274   for (vector<Operand>::iterator iter = operands.begin();
275        iter != operands.end(); ++iter) {
276     // If we can bind the PC, then we're in the operand
277     // we want.
278     Expression::Ptr exp = iter->getValue();
279     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
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   Architecture fixme = insn->getArch();
360   if (fixme == Arch_ppc32) fixme = Arch_ppc64;
361
362   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
363   Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
364
365   switch(insn->getArch()) {
366      case Arch_x86:
367      case Arch_ppc32:
368         CFT->bind(thePC.get(), Result(u32, ptr->addr()));
369         CFT->bind(thePCFixme.get(), Result(u32, ptr->addr()));
370         break;
371      case Arch_x86_64:
372      case Arch_ppc64:
373         CFT->bind(thePC.get(), Result(u64, ptr->addr()));
374         CFT->bind(thePCFixme.get(), Result(u64, ptr->addr()));
375         break;
376      default:
377         assert(0);
378         break;
379   }
380
381   Result res = CFT->eval();
382
383   if (!res.defined) {
384     relocation_cerr << "      ... CFT not evallable, ret false from isGetPC" << endl;
385     return false;
386   }
387
388   Address target = res.convert<Address>();
389
390   if (target == (ptr->addr() + insn->size())) {
391     aloc = Absloc(0, 0, NULL);
392     relocation_cerr << "      ... call next insn, ret true" << endl;
393     return true;
394   }
395
396   // Check for a call to a thunk function
397   // TODO: replace entirely with sensitivity analysis. But for now? 
398   // Yeah.
399   
400   // This is yoinked from arch-x86.C...
401   if (addrSpace->isValidAddress(target)) {
402     // Get us an instrucIter    
403     const unsigned char* buf = reinterpret_cast<const unsigned char*>(addrSpace->getPtrToInstruction(target));
404     if (!buf) {
405        cerr << "Error: illegal pointer to buffer!" << endl;
406        cerr << "Target of " << hex << target << " from addr " << ptr->addr() << " in insn " << insn->format() << dec << endl;
407        assert(0);
408     }
409
410     InstructionDecoder decoder(buf,
411                                2*InstructionDecoder::maxInstructionLength,
412                                addrSpace->getArch());
413
414     Instruction::Ptr firstInsn = decoder.decode();
415     Instruction::Ptr secondInsn = decoder.decode();
416
417     relocation_cerr << "      ... decoded target insns "
418                     << firstInsn->format() << ", " 
419                     << secondInsn->format() << endl;
420
421     if(firstInsn && firstInsn->getOperation().getID() == e_mov
422        && firstInsn->readsMemory() && !firstInsn->writesMemory()
423        && secondInsn && secondInsn->getCategory() == c_ReturnInsn) {
424
425       thunkVisitor visitor;
426       relocation_cerr << "Checking operand " << firstInsn->getOperand(1).format(firstInsn->getArch()) << endl;
427       firstInsn->getOperand(1).getValue()->apply(&visitor);
428       if (!visitor.isThunk) return false;
429
430 #if 0
431       // Check to be sure we're reading memory
432       std::set<RegisterAST::Ptr> reads;
433       firstInsn->getReadSet(reads);
434       bool found = false;
435       for (std::set<RegisterAST::Ptr>::iterator iter = reads.begin();
436            iter != reads.end(); ++iter) {
437         if ((*iter)->getID().isStackPointer()) {
438           found = true;
439           break;
440         }
441       }
442       if (!found) return false;
443
444 #endif
445       
446       std::set<RegisterAST::Ptr> writes;
447       firstInsn->getWriteSet(writes);
448       assert(writes.size() == 1);
449       aloc = Absloc((*(writes.begin()))->getID());
450       thunk = target;
451       return true;
452     }
453   }
454   else {     
455      relocation_cerr << "\t Call to " << hex << target << " is not valid address, concluding not thunk" << dec << endl;
456   }
457   return false;
458 }
459
460 #if defined(cap_stack_mods)
461 bool adhocMovementTransformer::isStackFrameSensitive(Offset& origDisp,
462         signed long& delta,
463         const Accesses* accesses,
464         OffsetVector*& offVec,
465         TMap*& tMap,
466         ParseAPI::Block* block,
467         Address addr)
468 {
469     StackAnalysis::Height regDelta(0);
470     StackAnalysis::Height readDelta(0);
471
472     bool ret = false;
473     for (auto iter = accesses->begin(); iter != accesses->end(); ++iter) {
474         MachRegister curReg = (*iter).first;
475         StackAccess* access = (*iter).second;
476
477         origDisp = access->disp();
478
479         stackmods_printf("\t %s\n", access->format().c_str());
480
481         StackAnalysis::Height regHeightPrime = access->regHeight();
482         StackAnalysis::Height readHeightPrime = access->readHeight();
483
484         stackmods_printf("\t\t regHeight = %ld, readHeight = %ld\n", access->regHeight().height(), access->readHeight().height());
485
486         // Idea: Check for exact match first, then check for overlaps
487         // This should fix the case where we add an exact match. However, find is going to search for any match, so we need to look ourselves
488
489         bool foundReg = false;
490         bool foundRead = false;
491
492         // Find any updates to regHeight or readHeight (exact matches)
493         for (auto tIter = tMap->begin(); (!foundReg || !foundRead) && tIter != tMap->end(); ++tIter) {
494             StackLocation* src = (*tIter).first;
495             StackLocation* dest = (*tIter).second;
496
497             stackmods_printf("\t\t\t Checking %s -> %s\n", src->format().c_str(), dest->format().c_str());
498
499             if (src->isStackMemory() && dest->isStackMemory()) {
500                 if (src->isRegisterHeight()) {
501                     if (src->off() == access->regHeight()) {
502
503                         int tmp;
504                         if (src->valid() && !src->valid()->find(addr, tmp)) {
505                             stackmods_printf("\t\t\t\t Matching src height not valid for this PC\n");
506                             continue;
507                         }
508
509                         if (src->reg() == curReg) {
510                             foundReg = true;
511                             if (!offVec->isSkip(curReg, access->regHeight(), block->start(), addr)) {
512                                 regHeightPrime = dest->off();
513                                 stackmods_printf("\t\t\t\t regHeight' = %ld\n", regHeightPrime.height());
514                             } else {
515                                 stackmods_printf("\t\t\t\t Register marked as skip.\n");
516                             }
517                         }
518                     }
519                 } else {
520
521                     if (src->off() == access->readHeight()) {
522
523                         int tmp;
524                         if (src->valid() && !src->valid()->find(addr, tmp)) {
525                             stackmods_printf("\t\t\t\t Matching src height not valid for this PC\n");
526                             continue;
527                         }
528
529                         foundRead = true;
530                         readHeightPrime = dest->off();
531                         stackmods_printf("\t\t\t\t readHeight' = %ld\n", readHeightPrime.height());
532                     }
533                 }
534             } else if (src->isNull()) {
535                 stackmods_printf("\t\t\t\t Ignoring: insertion\n");
536             } else {
537                 // Shouldn't be able to get here
538                 assert(0);
539             }
540         }
541
542         // Still necessary because accesses contained inside other accesses may not have an exact offset match in O
543         // Look for ranges that include the readHeight
544         for (auto tIter = tMap->begin(); !foundRead && tIter != tMap->end(); ++tIter) {
545             StackLocation* src = (*tIter).first;
546             StackLocation* dest = (*tIter).second;
547
548             stackmods_printf("\t\t\t Checking %s -> %s\n", src->format().c_str(), dest->format().c_str());
549             if (src->isStackMemory() && dest->isStackMemory()) {
550                 if (src->isRegisterHeight()) {
551                     // Nothing to do
552                 } else {
553                     if (src->off() < access->readHeight() && access->readHeight() < src->off() + src->size()) {
554                         int tmp;
555                         if (src->valid() && !src->valid()->find(addr, tmp)) {
556                             stackmods_printf("\t\t\t\t Matching src height not valid for this PC\n");
557                             continue;
558                         }
559                         foundRead = true;
560                         readHeightPrime = dest->off() + (access->readHeight() - src->off());
561                         stackmods_printf("\t\t\t\t readHeight' = %ld\n", readHeightPrime.height());
562                     }
563                 }
564             }
565         }
566
567         regDelta += access->regHeight() - regHeightPrime;
568         readDelta += access->readHeight() - readHeightPrime;
569
570         if (regDelta != readDelta) {
571         }
572     }
573
574     if (regDelta != readDelta) {
575         ret = true;
576         delta = regDelta.height() - readDelta.height();
577     }
578
579     return ret;
580 }
581 #endif