Refactoring to separate jump table parsing from the rest of InstructionAdapter code...
[dyninst.git] / parseAPI / src / IA_IAPI.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include "dyntypes.h"
33 #include "IA_IAPI.h"
34
35 #include "Register.h"
36 #include "Dereference.h"
37 #include "Immediate.h"
38 #include "BinaryFunction.h"
39 #include "debug_parse.h"
40 #include "IA_platformDetails.h"
41
42 #include <deque>
43 #include <map>
44
45 using namespace Dyninst;
46 using namespace InstructionAPI;
47 using namespace Dyninst::InsnAdapter;
48 using namespace Dyninst::ParseAPI;
49
50 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::framePtr;
51 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::stackPtr;
52 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::thePC;
53
54 void IA_IAPI::initASTs()
55 {
56     if(framePtr.empty())
57     {
58         framePtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86)));
59         framePtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86_64)));
60         framePtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc32)));
61         framePtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc64)));
62     }
63     if(stackPtr.empty())
64     {
65         stackPtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86)));
66         stackPtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86_64)));
67         stackPtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc32)));
68         stackPtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc64)));
69     }
70     if(thePC.empty())
71     {
72         thePC[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86)));
73         thePC[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86_64)));
74         thePC[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc32)));
75         thePC[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc64)));
76     }
77 }
78
79 IA_IAPI::IA_IAPI(InstructionDecoder dec_, 
80         Address where_,
81         CodeObject * o,
82         CodeRegion * r,
83         InstructionSource *isrc) :
84     InstructionAdapter(where_, o, r, isrc), 
85     dec(dec_),
86     validCFT(false), 
87     cachedCFT(0),
88     validLinkerStubState(false)
89 {
90     hascftstatus.first = false;
91     tailCall.first = false;
92     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
93     initASTs();
94 }
95
96 void IA_IAPI::advance()
97 {
98     if(!curInsn()) {
99         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
100                        allInsns.size());
101         return;
102     }
103     InstructionAdapter::advance();
104     current += curInsn()->size();
105     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
106     if(!curInsn())
107     {
108         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
109     }
110     validCFT = false;
111     validLinkerStubState = false;
112     hascftstatus.first = false;
113     tailCall.first = false;
114 }
115
116 void IA_IAPI::retreat()
117 {
118     if(!curInsn()) {
119         parsing_printf("..... WARNING: failed to retreat InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
120                        allInsns.size());
121         return;
122     }
123     InstructionAdapter::retreat();
124     std::map<Address,Instruction::Ptr>::iterator remove = curInsnIter;
125     if(curInsnIter != allInsns.begin()) {
126         --curInsnIter;
127         allInsns.erase(remove);
128         current = curInsnIter->first;
129         if(curInsnIter != allInsns.begin()) {
130             std::map<Address,Instruction::Ptr>::iterator pit = curInsnIter;
131             --pit;
132             previous = curInsnIter->first;
133         } else {
134             previous = -1;
135         }
136     } else {
137         parsing_printf("..... WARNING: cowardly refusal to retreat past first instruction at 0x%lx\n", current);
138     }
139
140     /* blind duplication -- nate */
141     validCFT = false;
142     validLinkerStubState = false;
143     hascftstatus.first = false;
144     tailCall.first = false;
145
146     
147     
148
149 size_t IA_IAPI::getSize() const
150 {
151     Instruction::Ptr ci = curInsn();
152     assert(ci);
153     return ci->size();
154 }
155
156 bool IA_IAPI::hasCFT() const
157 {
158     if(hascftstatus.first) return hascftstatus.second;
159     InsnCategory c = curInsn()->getCategory();
160     hascftstatus.second = false;
161     if(c == c_BranchInsn ||
162        c == c_ReturnInsn)
163     {
164         hascftstatus.second = true;
165     }
166     if(c == c_CallInsn)
167     {
168         if(isRealCall()) {
169             hascftstatus.second = true;
170         }
171         if(isDynamicCall()) {
172             hascftstatus.second = true;
173         }
174         if(simulateJump()) {
175             hascftstatus.second = true;
176         }
177     }
178     hascftstatus.first = true;
179     return hascftstatus.second;
180 }
181
182 bool IA_IAPI::isAbortOrInvalidInsn() const
183 {
184     entryID e = curInsn()->getOperation().getID();
185     if(e == e_No_Entry)
186     {
187         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
188     }
189     return e == e_No_Entry ||
190             e == e_int3 ||
191             e == e_hlt;
192 }
193
194 bool IA_IAPI::isFrameSetupInsn() const
195 {
196     return isFrameSetupInsn(curInsn());
197 }
198
199 bool IA_IAPI::isDynamicCall() const
200 {
201     Instruction::Ptr ci = curInsn();
202     if(ci && (ci->getCategory() == c_CallInsn))
203     {
204         if(getCFT() == 0)
205         {
206             parsing_printf("... Call 0x%lx is indirect\n", current);
207             return true;
208         }
209     }
210     return false;
211 }
212
213 bool IA_IAPI::isAbsoluteCall() const
214 {
215     Instruction::Ptr ci = curInsn();
216     if(ci->getCategory() == c_CallInsn)
217     {
218         Expression::Ptr cft = ci->getControlFlowTarget();
219         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
220         {
221             return true;
222         }
223     }
224     return false;
225 }
226
227
228 bool IA_IAPI::isReturn() const
229 {
230     return curInsn()->getCategory() == c_ReturnInsn;
231 }
232 bool IA_IAPI::isBranch() const
233 {
234     return curInsn()->getCategory() == c_BranchInsn;
235 }
236 bool IA_IAPI::isCall() const
237 {
238     return curInsn()->getCategory() == c_CallInsn;
239 }
240
241 bool IA_IAPI::isInterruptOrSyscall() const
242 {
243     return (isInterrupt() && isSyscall());
244 }
245
246 bool IA_IAPI::isSyscall() const
247 {
248     static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
249     
250     Instruction::Ptr ci = curInsn();
251
252     return (((ci->getOperation().getID() == e_call) &&
253             /*(curInsn()->getOperation().isRead(gs))) ||*/
254             (ci->getOperand(0).format() == "16")) ||
255             (ci->getOperation().getID() == e_syscall) || 
256             (ci->getOperation().getID() == e_int) || 
257             (ci->getOperation().getID() == power_op_sc));
258 }
259
260
261 bool IA_IAPI::isInterrupt() const
262 {
263     Instruction::Ptr ci = curInsn();
264     return ((ci->getOperation().getID() == e_int) ||
265             (ci->getOperation().getID() == e_int3));
266 }
267
268 void IA_IAPI::getNewEdges(
269         std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges,
270         Function* context,
271         Block* currBlk,
272         unsigned int num_insns,
273         dyn_hash_map<Address, std::string> *plt_entries) const
274 {
275     Instruction::Ptr ci = curInsn();
276
277     // Only call this on control flow instructions!
278     if(ci->getCategory() == c_CallInsn)
279     {
280         Address target = getCFT();
281         if(isRealCall() || isDynamicCall())
282         {
283             outEdges.push_back(std::make_pair(target, NOEDGE));
284         }
285         else
286         {
287             if(_isrc->isValidAddress(target))
288             {
289                 if(simulateJump())
290                 {
291                     parsing_printf("[%s:%u] call at 0x%lx simulated as "
292                             "jump to 0x%lx\n",
293                     FILE__,__LINE__,getAddr(),getCFT());
294                     outEdges.push_back(std::make_pair(target, DIRECT));
295                     return;
296                 }
297             }
298         }
299         outEdges.push_back(std::make_pair(getAddr() + getSize(),
300                            CALL_FT));
301         return;
302     }
303     else if(ci->getCategory() == c_BranchInsn)
304     {
305         Address target;
306         if(ci->allowsFallThrough())
307         {
308             outEdges.push_back(std::make_pair(getCFT(),
309                                COND_TAKEN));
310             outEdges.push_back(std::make_pair(getNextAddr(), COND_NOT_TAKEN));
311             return;
312         }
313         // Direct jump
314         else if((target = getCFT()) != 0)
315         {
316             Address catchStart;
317             if(_cr->findCatchBlock(getNextAddr(),catchStart))
318             {
319                 outEdges.push_back(std::make_pair(catchStart, CATCH));
320             }
321         
322
323             if(!isTailCall(context,num_insns))
324             {
325                 if(plt_entries->find(target) == plt_entries->end())
326                 {
327                     outEdges.push_back(std::make_pair(target,DIRECT));
328                 }
329                 else
330                 {
331                     parsing_printf("%s[%d]: PLT tail call to %x (%s)\n", 
332                         FILE__, __LINE__, target,
333                         (*plt_entries)[target].c_str());
334                     outEdges.push_back(std::make_pair(target, NOEDGE));
335                     tailCall.second = true;
336                 }
337             }
338             else
339             {
340                 parsing_printf("%s[%d]: tail call to %x\n", 
341                     FILE__, __LINE__, target);
342                 outEdges.push_back(std::make_pair(target, NOEDGE));
343             }
344             return;
345         }
346         else
347         {
348             parsing_printf("... indirect jump at 0x%x\n", current);
349             if( num_insns == 2 ) {
350                 parsing_printf("... uninstrumentable due to 0 size\n");
351                 return;
352             }
353             if(isTailCall(context,num_insns)) {
354                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
355                                ci->format().c_str(), current);
356                 return;
357             }
358             parsing_printf("%s[%d]: jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
359                            ci->format().c_str(), current);
360             parsedJumpTable = true;
361             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
362
363             if(!successfullyParsedJumpTable || outEdges.empty()) {
364                 outEdges.push_back(std::make_pair((Address)-1,INDIRECT));
365             }
366             return;
367         }
368     }
369     else if(ci->getCategory() == c_ReturnInsn)
370     {
371         if(ci->allowsFallThrough())
372         {
373             outEdges.push_back(std::make_pair(getNextAddr(), FALLTHROUGH));
374             return;
375         }
376         return;
377     }
378     fprintf(stderr, "Unhandled instruction %s\n", ci->format().c_str());
379     assert(0);
380 }
381
382 bool IA_IAPI::isIPRelativeBranch() const
383 {
384             // These don't exist on IA32...
385 #if !defined(arch_x86_64)
386     return false;
387 #endif
388     Instruction::Ptr ci = curInsn();
389
390     if(ci->getCategory() == c_BranchInsn &&
391         !getCFT())
392 {
393     Expression::Ptr cft = ci->getControlFlowTarget();
394     if(cft->isUsed(thePC[_isrc->getArch()]))
395     {
396         parsing_printf("\tIP-relative indirect jump to %s at 0x%lx\n",
397                        cft->format().c_str(), current);
398         return true;
399     }
400 }
401     return false;
402     
403 }
404
405 Instruction::Ptr IA_IAPI::curInsn() const
406 {
407     return curInsnIter->second;
408 }
409
410 bool IA_IAPI::isLeave() const
411 {
412     Instruction::Ptr ci = curInsn();
413     return ci && (ci->getOperation().getID() == e_leave);
414 }
415
416 bool IA_IAPI::isDelaySlot() const
417 {
418 #if defined(arch_sparc)
419     assert(!"Implement delay slots on SPARC!");
420 #endif
421     return false;
422 }
423
424 Instruction::Ptr IA_IAPI::getInstruction()
425 {
426     return curInsn();
427 }
428
429 bool IA_IAPI::isRealCall() const
430 {
431     if(getCFT() == getNextAddr())
432     {
433         parsing_printf("... getting PC\n");
434         return false;
435     }
436     if(!_isrc->isValidAddress(getCFT()))
437     {
438         CodeSource *_csrc = dynamic_cast<CodeSource *>(_isrc);
439         if (!_csrc ||
440              _csrc->linkage().find(getCFT()) == _csrc->linkage().end()) {
441             parsing_printf(" isRealCall failed _isrc->isValidAddress(%lx)\n",
442                            getCFT());
443             return false;
444         }
445     }
446     if(isThunk()) {
447         return false;
448     }
449     return true;
450 }
451
452 std::map<Address, bool> IA_IAPI::thunkAtTarget;
453
454 bool IA_IAPI::isConditional() const
455 {
456     return curInsn()->allowsFallThrough();
457 }
458
459 bool IA_IAPI::simulateJump() const
460 {
461     // obfuscated programs simulate jumps by calling into a block that 
462     // discards the return address from the stack, we check for these
463     // fake calls in malware mode
464     if (_obj->defensiveMode()) {
465         return isFakeCall();
466     }
467     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.                
468     return false;
469 }
470
471 Address IA_IAPI::getCFT() const
472 {
473     if(validCFT) return cachedCFT;
474     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
475         // FIXME: templated bind(),dammit!
476     callTarget->bind(thePC[_isrc->getArch()].get(), Result(s64, current));
477     parsing_printf("%s[%d]: binding PC %s in %s to 0x%x...", FILE__, __LINE__,
478                    thePC[_isrc->getArch()]->format().c_str(), curInsn()->format().c_str(), current);
479     Result actualTarget = callTarget->eval();
480     if(actualTarget.defined)
481     {
482         cachedCFT = actualTarget.convert<Address>();
483         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
484     }
485     else
486     {
487         cachedCFT = 0;
488         parsing_printf("FAIL (CFT=0x%x), callTarget exp: %s\n",
489                        cachedCFT,callTarget->format().c_str());
490     }
491     validCFT = true;
492
493     if(isLinkerStub()) {
494         parsing_printf("Linker stub detected: Correcting CFT.  (CFT=0x%x)\n",
495                        cachedCFT);
496     }
497
498     return cachedCFT;
499 }
500
501 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
502 {
503     Instruction::Ptr ci = curInsn();
504     if(ci && (ci->getCategory() == c_CallInsn))
505     {
506         if(!isDynamicCall())
507         {
508             if(!_isrc->isValidAddress(getCFT()))
509             {
510                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
511                                getCFT());
512                 return false;
513             }
514         }
515     }
516     if(lvl == HAS_BR_INDIR)
517     {
518         return false;
519     }
520     return true;
521 }
522
523 bool IA_IAPI::parseJumpTable(Dyninst::ParseAPI::Block* currBlk,
524                     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) const
525 {
526     IA_platformDetails* jumpTableParser = makePlatformDetails(_isrc->getArch(), this);
527     bool ret = jumpTableParser->parseJumpTable(currBlk, outEdges);
528     delete jumpTableParser;
529     return ret;
530 }
531
532
533
534 InstrumentableLevel IA_IAPI::getInstLevel(Function * context, unsigned int num_insns) const
535 {
536     InstrumentableLevel ret = InstructionAdapter::getInstLevel(context, num_insns);
537 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
538     {
539         return NORMAL;
540 }*/
541     return ret;
542 }