Fix logic bug relocating a PC-relative instruction that targets 0.
[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/CFWidget.h"
37 #include "../Widgets/PCWidget.h"
38 #include "../CFG/RelocBlock.h"
39 #include "dyninstAPI/src/addressSpace.h"
40 #include "instructionAPI/h/InstructionDecoder.h"
41 #include "../CFG/RelocGraph.h"
42 #include "instructionAPI/h/Visitor.h"
43
44
45 using namespace std;
46 using namespace Dyninst; 
47 using namespace Relocation;
48 using namespace InstructionAPI;
49
50
51 bool adhocMovementTransformer::process(RelocBlock *cur, RelocGraph *cfg) {
52   // Identify PC-relative data accesses
53   // and "get PC" operations and replace them
54   // with dedicated Widgets
55
56    RelocBlock::WidgetList &elements = cur->elements();
57
58   relocation_cerr << "PCRelTrans: processing block " 
59                   << cur << " with "
60                   << elements.size() << " elements." << endl;
61
62   for (RelocBlock::WidgetList::iterator iter = elements.begin();
63        iter != elements.end(); ++iter) {
64     // Can I do in-place replacement? Apparently I can...
65     // first insert new (before iter) and then remove iter
66
67     // Cache this so we don't re-decode...
68     InsnPtr insn = (*iter)->insn();
69
70     if (!insn) continue;
71
72     Address target = 0;
73     Absloc aloc;
74
75     if (isPCDerefCF(*iter, insn, target)) {
76        CFWidget::Ptr cf = boost::dynamic_pointer_cast<CFWidget>(*iter);
77        assert(cf);
78        cf->setOrigTarget(target);
79     }
80     if (isPCRelData(*iter, insn, target)) {
81       relocation_cerr << "  ... isPCRelData at " 
82                       << std::hex << (*iter)->addr() << std::dec << endl;
83       // Two options: a memory reference or a indirect call. The indirect call we 
84       // just want to set target in the CFWidget, as it has the hardware to handle
85       // control flow. Generic memory references get their own atoms. How nice. 
86       Widget::Ptr replacement = RelDataWidget::create(insn,
87                                                      (*iter)->addr(),
88                                                      target);
89       (*iter).swap(replacement);
90       
91     }
92     else if (isGetPC(*iter, insn, aloc, target)) {
93
94       Widget::Ptr replacement = PCWidget::create(insn,
95                                                (*iter)->addr(),
96                                                aloc,
97                                                target);
98       // This is kind of complex. We don't want to just pull the getPC
99       // because it also might end the basic block. If that happens we
100       // need to pull the fallthough element out of the CFWidget so
101       // that we don't hork control flow. What a pain.
102       if ((*iter) != elements.back()) {
103         // Easy case; no worries.
104         (*iter).swap(replacement);
105       }
106       else {
107          // Remove the taken edge from the trace, as we're removing
108          // the call and replacing it with a GetPC operation. 
109          Predicates::Interprocedural pred;
110          bool removed = cfg->removeEdge(pred, cur->outs());
111          assert(removed);
112             
113          // Before we forget: swap in the GetPC for the current element
114          (*iter).swap(replacement);            
115          break;
116       }
117     }
118   }
119   return true;
120 }
121
122 bool adhocMovementTransformer::isPCDerefCF(Widget::Ptr ptr,
123                                            InsnPtr insn,
124                                            Address &target) {
125    Expression::Ptr cf = insn->getControlFlowTarget();
126    if (!cf) return false;
127    
128    Architecture fixme = insn->getArch();
129    if (fixme == Arch_ppc32) fixme = Arch_ppc64;
130    
131    Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
132    Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
133
134    // Okay, see if we're memory
135    set<Expression::Ptr> mems;
136    insn->getMemoryReadOperands(mems);
137    
138    for (set<Expression::Ptr>::const_iterator iter = mems.begin();
139         iter != mems.end(); ++iter) {
140       Expression::Ptr exp = *iter;
141       if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
142           exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
143         // Bind succeeded, eval to get target address
144         Result res = exp->eval();
145         if (!res.defined) {
146           cerr << "ERROR: failed bind/eval at " << std::hex << ptr->addr() << endl;if (insn->getControlFlowTarget()) return false;
147         }
148         assert(res.defined);
149         target = res.convert<Address>();
150         break;
151       }
152    }
153    if (target) return true;
154    return false;
155 }
156
157
158
159 // We define this as "uses PC and is not control flow"
160 bool adhocMovementTransformer::isPCRelData(Widget::Ptr ptr,
161                                            InsnPtr insn,
162                                            Address &target) {
163   target = 0;
164   if (insn->getControlFlowTarget()) return false;
165
166   Architecture fixme = insn->getArch();
167   if (fixme == Arch_ppc32) fixme = Arch_ppc64;
168   
169   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
170   Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
171
172   if (!insn->isRead(thePC) &&
173       !insn->isRead(thePCFixme))
174     return false;
175
176   // Okay, see if we're memory
177   set<Expression::Ptr> mems;
178   insn->getMemoryReadOperands(mems);
179   insn->getMemoryWriteOperands(mems);
180   for (set<Expression::Ptr>::const_iterator iter = mems.begin();
181        iter != mems.end(); ++iter) {
182     Expression::Ptr exp = *iter;
183
184     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
185         exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
186       // Bind succeeded, eval to get target address
187       Result res = exp->eval();
188       if (!res.defined) {
189         continue;
190       }
191       assert(res.defined);
192       target = res.convert<Address>();
193       return 0;
194     }
195   }
196   if (target) return true;
197
198   // Didn't use the PC to read memory; thus we have to grind through
199   // all the operands. We didn't do this directly because the 
200   // memory-topping deref stops eval...
201   vector<Operand> operands;
202   insn->getOperands(operands);
203   for (vector<Operand>::iterator iter = operands.begin();
204        iter != operands.end(); ++iter) {
205     // If we can bind the PC, then we're in the operand
206     // we want.
207     Expression::Ptr exp = iter->getValue();
208     if (exp->bind(thePC.get(), Result(u64, ptr->addr() + insn->size())) ||
209         exp->bind(thePCFixme.get(), Result(u64, ptr->addr() + insn->size()))) {
210       // Bind succeeded, eval to get target address
211       Result res = exp->eval();
212       if (!res.defined) continue;
213
214       target = res.convert<Address>();
215       break;
216     }
217   }
218   if (target == 0) {
219      cerr << "Error: failed to bind PC in " << insn->format() << endl;
220   }
221   assert(target != 0);
222   return true;    
223 }
224
225 class thunkVisitor : public InstructionAPI::Visitor
226 {
227 public:
228   thunkVisitor() : isThunk(true), foundSP(false), foundDeref(false) {}
229   virtual ~thunkVisitor() {}
230
231   bool isThunk;
232   bool foundSP;
233   bool foundDeref;
234
235   virtual void visit(BinaryFunction*)
236   {
237     relocation_cerr << "\t binfunc, ret false" << endl;
238     isThunk = false;
239   }
240
241   virtual void visit(Immediate*)
242   {
243     relocation_cerr << "\t imm, ret false" << endl;
244     isThunk = false;
245   }
246   virtual void visit(RegisterAST* r)
247   {
248     if (foundSP) {
249       isThunk = false;
250     }
251     else if (!r->getID().isStackPointer()) {
252       isThunk = false;
253     }
254     else {
255       foundSP = true;
256     }
257   }
258   virtual void visit(Dereference* )
259   {
260     if (foundDeref) {
261       isThunk = false;
262     }
263     if (!foundSP) {
264       isThunk = false;
265     }
266     foundDeref = true;
267   }  
268 };
269
270
271 bool adhocMovementTransformer::isGetPC(Widget::Ptr ptr,
272                                        InsnPtr insn,
273                                        Absloc &aloc,
274                                        Address &thunk) {
275   // TODO:
276   // Check for call + size;
277   // Check for call to thunk.
278   // TODO: need a return register parameter.
279
280    if (insn->getCategory() != InstructionAPI::c_CallInsn) return false;
281
282   // Okay: checking for call + size
283   Expression::Ptr CFT = insn->getControlFlowTarget();
284   if (!CFT) {
285     relocation_cerr << "      ... no CFT, ret false from isGetPC" << endl;
286     return false;
287   }
288    
289   Architecture fixme = insn->getArch();
290   if (fixme == Arch_ppc32) fixme = Arch_ppc64;
291
292   Expression::Ptr thePC(new RegisterAST(MachRegister::getPC(insn->getArch())));
293   Expression::Ptr thePCFixme(new RegisterAST(MachRegister::getPC(fixme)));
294
295   switch(insn->getArch()) {
296      case Arch_x86:
297      case Arch_ppc32:
298         CFT->bind(thePC.get(), Result(u32, ptr->addr()));
299         CFT->bind(thePCFixme.get(), Result(u32, ptr->addr()));
300         break;
301      case Arch_x86_64:
302      case Arch_ppc64:
303         CFT->bind(thePC.get(), Result(u64, ptr->addr()));
304         CFT->bind(thePCFixme.get(), Result(u64, ptr->addr()));
305         break;
306      default:
307         assert(0);
308         break;
309   }
310
311   Result res = CFT->eval();
312
313   if (!res.defined) {
314     relocation_cerr << "      ... CFT not evallable, ret false from isGetPC" << endl;
315     return false;
316   }
317
318   Address target = res.convert<Address>();
319
320   if (target == (ptr->addr() + insn->size())) {
321     aloc = Absloc(0, 0, NULL);
322     relocation_cerr << "      ... call next insn, ret true" << endl;
323     return true;
324   }
325
326   // Check for a call to a thunk function
327   // TODO: replace entirely with sensitivity analysis. But for now? 
328   // Yeah.
329   
330   // This is yoinked from arch-x86.C...
331   if (addrSpace->isValidAddress(target)) {
332     // Get us an instrucIter    
333     const unsigned char* buf = reinterpret_cast<const unsigned char*>(addrSpace->getPtrToInstruction(target));
334     if (!buf) {
335        cerr << "Error: illegal pointer to buffer!" << endl;
336        cerr << "Target of " << hex << target << " from addr " << ptr->addr() << " in insn " << insn->format() << dec << endl;
337        assert(0);
338     }
339
340     InstructionDecoder decoder(buf,
341                                2*InstructionDecoder::maxInstructionLength,
342                                addrSpace->getArch());
343
344     Instruction::Ptr firstInsn = decoder.decode();
345     Instruction::Ptr secondInsn = decoder.decode();
346
347     relocation_cerr << "      ... decoded target insns "
348                     << firstInsn->format() << ", " 
349                     << secondInsn->format() << endl;
350
351     if(firstInsn && firstInsn->getOperation().getID() == e_mov
352        && firstInsn->readsMemory() && !firstInsn->writesMemory()
353        && secondInsn && secondInsn->getCategory() == c_ReturnInsn) {
354
355       thunkVisitor visitor;
356       relocation_cerr << "Checking operand " << firstInsn->getOperand(1).format(firstInsn->getArch()) << endl;
357       firstInsn->getOperand(1).getValue()->apply(&visitor);
358       if (!visitor.isThunk) return false;
359
360 #if 0
361       // Check to be sure we're reading memory
362       std::set<RegisterAST::Ptr> reads;
363       firstInsn->getReadSet(reads);
364       bool found = false;
365       for (std::set<RegisterAST::Ptr>::iterator iter = reads.begin();
366            iter != reads.end(); ++iter) {
367         if ((*iter)->getID().isStackPointer()) {
368           found = true;
369           break;
370         }
371       }
372       if (!found) return false;
373
374 #endif
375       
376       std::set<RegisterAST::Ptr> writes;
377       firstInsn->getWriteSet(writes);
378       assert(writes.size() == 1);
379       aloc = Absloc((*(writes.begin()))->getID());
380       thunk = target;
381       return true;
382     }
383   }
384   else {     
385      relocation_cerr << "\t Call to " << hex << target << " is not valid address, concluding not thunk" << dec << endl;
386   }
387   return false;
388 }