powerpc rewriter commit
[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 #include "util.h"
42
43 #include <deque>
44 #include <map>
45
46 #if defined(os_vxworks)
47 #include "common/h/wtxKludges.h"
48 #endif
49
50 using namespace Dyninst;
51 using namespace InstructionAPI;
52 using namespace Dyninst::InsnAdapter;
53 using namespace Dyninst::ParseAPI;
54
55 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::framePtr;
56 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::stackPtr;
57 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::thePC;
58
59 void IA_IAPI::initASTs()
60 {
61     if(framePtr.empty())
62     {
63         framePtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86)));
64         framePtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86_64)));
65         framePtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc32)));
66         framePtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc64)));
67     }
68     if(stackPtr.empty())
69     {
70         stackPtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86)));
71         stackPtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86_64)));
72         stackPtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc32)));
73         stackPtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc64)));
74     }
75     if(thePC.empty())
76     {
77         thePC[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86)));
78         thePC[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86_64)));
79         thePC[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc32)));
80         thePC[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc64)));
81     }
82 }
83
84 IA_IAPI::IA_IAPI(InstructionDecoder dec_, 
85         Address where_,
86         CodeObject * o,
87         CodeRegion * r,
88         InstructionSource *isrc,
89         Block * curBlk_) :
90     InstructionAdapter(where_, o, r, isrc, curBlk_), 
91     dec(dec_),
92     validCFT(false), 
93     cachedCFT(0),
94     validLinkerStubState(false)
95 {
96     hascftstatus.first = false;
97     tailCall.first = false;
98     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
99     initASTs();
100 }
101
102 void IA_IAPI::advance()
103 {
104     if(!curInsn()) {
105         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
106                        allInsns.size());
107         return;
108     }
109     InstructionAdapter::advance();
110     current += curInsn()->size();
111     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
112     if(!curInsn())
113     {
114         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
115     }
116     validCFT = false;
117     validLinkerStubState = false;
118     hascftstatus.first = false;
119     tailCall.first = false;
120 }
121
122 void IA_IAPI::retreat()
123 {
124     if(!curInsn()) {
125         parsing_printf("..... WARNING: failed to retreat InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
126                        allInsns.size());
127         return;
128     }
129     InstructionAdapter::retreat();
130     std::map<Address,Instruction::Ptr>::iterator remove = curInsnIter;
131     if(curInsnIter != allInsns.begin()) {
132         --curInsnIter;
133         allInsns.erase(remove);
134         current = curInsnIter->first;
135         if(curInsnIter != allInsns.begin()) {
136             std::map<Address,Instruction::Ptr>::iterator pit = curInsnIter;
137             --pit;
138             previous = curInsnIter->first;
139         } else {
140             previous = -1;
141         }
142     } else {
143         parsing_printf("..... WARNING: cowardly refusal to retreat past first instruction at 0x%lx\n", current);
144     }
145
146     /* blind duplication -- nate */
147     validCFT = false;
148     validLinkerStubState = false;
149     hascftstatus.first = false;
150     tailCall.first = false;
151
152     
153     
154
155 size_t IA_IAPI::getSize() const
156 {
157     Instruction::Ptr ci = curInsn();
158     assert(ci);
159     return ci->size();
160 }
161
162 bool IA_IAPI::hasCFT() const
163 {
164     if(hascftstatus.first) return hascftstatus.second;
165     InsnCategory c = curInsn()->getCategory();
166     hascftstatus.second = false;
167     if(c == c_BranchInsn ||
168        c == c_ReturnInsn)
169     {
170         hascftstatus.second = true;
171     }
172     else if(c == c_CallInsn)
173     {
174         if(isRealCall()) {
175             hascftstatus.second = true;
176         }
177         else if(isDynamicCall()) {
178             hascftstatus.second = true;
179         }
180         else if(simulateJump()) {
181             hascftstatus.second = true;
182         }
183     }
184     hascftstatus.first = true;
185     return hascftstatus.second;
186 }
187
188 bool IA_IAPI::isAbortOrInvalidInsn() const
189 {
190     entryID e = curInsn()->getOperation().getID();
191     if(e == e_No_Entry)
192     {
193         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
194     }
195     return e == e_No_Entry ||
196             e == e_int3 ||
197             e == e_hlt;
198 }
199
200 bool IA_IAPI::isFrameSetupInsn() const
201 {
202     return isFrameSetupInsn(curInsn());
203 }
204
205 bool IA_IAPI::isDynamicCall() const
206 {
207     Instruction::Ptr ci = curInsn();
208     if(ci && (ci->getCategory() == c_CallInsn))
209     {
210         if(getCFT() == 0)
211         {
212             parsing_printf("... Call 0x%lx is indirect\n", current);
213             return true;
214         }
215     }
216     return false;
217 }
218
219 bool IA_IAPI::isAbsoluteCall() const
220 {
221     Instruction::Ptr ci = curInsn();
222     if(ci->getCategory() == c_CallInsn)
223     {
224         Expression::Ptr cft = ci->getControlFlowTarget();
225         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
226         {
227             return true;
228         }
229     }
230     return false;
231 }
232
233 bool IA_IAPI::isBranch() const
234 {
235     return curInsn()->getCategory() == c_BranchInsn;
236 }
237 bool IA_IAPI::isCall() const
238 {
239     return curInsn()->getCategory() == c_CallInsn;
240 }
241
242 bool IA_IAPI::isInterruptOrSyscall() const
243 {
244     return (isInterrupt() && isSyscall());
245 }
246
247 bool IA_IAPI::isSyscall() const
248 {
249     static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
250     
251     Instruction::Ptr ci = curInsn();
252
253     return (((ci->getOperation().getID() == e_call) &&
254             /*(curInsn()->getOperation().isRead(gs))) ||*/
255             (ci->getOperand(0).format() == "16")) ||
256             (ci->getOperation().getID() == e_syscall) || 
257             (ci->getOperation().getID() == e_int) || 
258             (ci->getOperation().getID() == power_op_sc));
259 }
260
261
262 bool IA_IAPI::isInterrupt() const
263 {
264     Instruction::Ptr ci = curInsn();
265     return ((ci->getOperation().getID() == e_int) ||
266             (ci->getOperation().getID() == e_int3));
267 }
268
269 void IA_IAPI::getNewEdges(
270         std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges,
271         Function* context,
272         Block* currBlk,
273         unsigned int num_insns,
274         dyn_hash_map<Address, std::string> *plt_entries) const
275 {
276     Instruction::Ptr ci = curInsn();
277
278     // Only call this on control flow instructions!
279     if(ci->getCategory() == c_CallInsn)
280     {
281         Address target = getCFT();
282         bool callEdge = true;
283         bool ftEdge = true;
284         if( ! isDynamicCall() )
285         {
286             if ( ! isRealCall() )
287                 callEdge = false;
288
289             if ( simulateJump() ) 
290             {
291                 outEdges.push_back(std::make_pair(target, DIRECT));
292                 callEdge = false;
293                 ftEdge = false;
294             }
295         }
296
297         if ( unlikely(_obj->defensiveMode()) )
298         {
299             if (isDynamicCall()) 
300             {
301                 if ( ! isIATcall() )
302                     ftEdge = false;
303             }
304             else if ( ! _isrc->isValidAddress(target) )
305             {
306                 ftEdge = false;
307             }
308         }
309  
310         if (callEdge)
311             outEdges.push_back(std::make_pair(target, NOEDGE));
312         if (ftEdge)
313             outEdges.push_back(std::make_pair(getAddr() + getSize(), CALL_FT));
314          return;
315     }
316     else if(ci->getCategory() == c_BranchInsn)
317     {
318         Address target;
319         if(ci->allowsFallThrough())
320         {
321             outEdges.push_back(std::make_pair(getCFT(),
322                                COND_TAKEN));
323             outEdges.push_back(std::make_pair(getNextAddr(), COND_NOT_TAKEN));
324             return;
325         }
326         // Direct jump
327         else if((target = getCFT()) != 0)
328         {
329             Address catchStart;
330             if(_cr->findCatchBlock(getNextAddr(),catchStart))
331             {
332                 outEdges.push_back(std::make_pair(catchStart, CATCH));
333             }
334         
335
336             if(!isTailCall(context,num_insns))
337             {
338                 if(plt_entries->find(target) == plt_entries->end())
339                 {
340                     outEdges.push_back(std::make_pair(target,DIRECT));
341                 }
342                 else
343                 {
344                     parsing_printf("%s[%d]: PLT tail call to %x (%s)\n", 
345                         FILE__, __LINE__, target,
346                         (*plt_entries)[target].c_str());
347                     outEdges.push_back(std::make_pair(target, NOEDGE));
348                     tailCall.second = true;
349                 }
350             }
351             else
352             {
353                 parsing_printf("%s[%d]: tail call to %x\n", 
354                     FILE__, __LINE__, target);
355                 outEdges.push_back(std::make_pair(target, NOEDGE));
356             }
357             return;
358         }
359         else
360         {
361             parsing_printf("... indirect jump at 0x%x\n", current);
362             if( num_insns == 2 ) {
363                 parsing_printf("... uninstrumentable due to 0 size\n");
364                 return;
365             }
366             if(isTailCall(context,num_insns)) {
367                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
368                                ci->format().c_str(), current);
369                 return;
370             }
371             parsing_printf("%s[%d]: jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
372                            ci->format().c_str(), current);
373             parsedJumpTable = true;
374             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
375
376             if(!successfullyParsedJumpTable || outEdges.empty()) {
377                 outEdges.push_back(std::make_pair((Address)-1,INDIRECT));
378                 parsing_printf("%s[%d]: BCTR unparsed jump table %s at 0x%lx in function %s UNINSTRUMENTABLE\n", FILE__, __LINE__,
379                            ci->format().c_str(), current, context->name().c_str());
380             }
381             return;
382         }
383     }
384     else if(ci->getCategory() == c_ReturnInsn)
385     {
386         parsing_printf("%s[%d]: BLR %s at 0x%lx\n", FILE__, __LINE__,
387                            ci->format().c_str(), current);
388         if(ci->allowsFallThrough())
389         {
390             outEdges.push_back(std::make_pair(getNextAddr(), FALLTHROUGH));
391         }
392         else if (!isReturnInst(context, currBlk)) {
393             // If BLR is not a return, then it is a jump table
394             parsedJumpTable = true;
395             parsing_printf("%s[%d]: BLR jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
396                            ci->format().c_str(), current);
397             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
398
399             if(!successfullyParsedJumpTable || outEdges.empty()) {
400                 parsing_printf("%s[%d]: BLR unparsed jump table %s at 0x%lx in function %s UNINSTRUMENTABLE\n", FILE__, __LINE__, ci->format().c_str(), current, context->name().c_str());
401                 outEdges.push_back(std::make_pair((Address)-1,INDIRECT));
402             }
403         }
404         return;
405     }
406     fprintf(stderr, "Unhandled instruction %s\n", ci->format().c_str());
407     assert(0);
408 }
409
410 bool IA_IAPI::isIPRelativeBranch() const
411 {
412             // These don't exist on IA32...
413 #if !defined(arch_x86_64)
414     return false;
415 #endif
416     Instruction::Ptr ci = curInsn();
417
418     if(ci->getCategory() == c_BranchInsn &&
419         !getCFT())
420 {
421     Expression::Ptr cft = ci->getControlFlowTarget();
422     if(cft->isUsed(thePC[_isrc->getArch()]))
423     {
424         parsing_printf("\tIP-relative indirect jump to %s at 0x%lx\n",
425                        cft->format().c_str(), current);
426         return true;
427     }
428 }
429     return false;
430     
431 }
432
433 Instruction::Ptr IA_IAPI::curInsn() const
434 {
435     return curInsnIter->second;
436 }
437
438 bool IA_IAPI::isLeave() const
439 {
440     Instruction::Ptr ci = curInsn();
441     return ci && (ci->getOperation().getID() == e_leave);
442 }
443
444 bool IA_IAPI::isDelaySlot() const
445 {
446 #if defined(arch_sparc)
447     assert(!"Implement delay slots on SPARC!");
448 #endif
449     return false;
450 }
451
452 Instruction::Ptr IA_IAPI::getInstruction()
453 {
454     return curInsn();
455 }
456
457 bool IA_IAPI::isRealCall() const
458 {
459     if(getCFT() == getNextAddr())
460     {
461         parsing_printf("... getting PC\n");
462         return false;
463     }
464     if(isThunk()) {
465         parsing_printf("... getting PC (thunk call)\n");
466         return false;
467     }
468     return true;
469 }
470
471 std::map<Address, bool> IA_IAPI::thunkAtTarget;
472
473 bool IA_IAPI::isConditional() const
474 {
475     return curInsn()->allowsFallThrough();
476 }
477
478 bool IA_IAPI::simulateJump() const
479 {
480     // obfuscated programs simulate jumps by calling into a block that 
481     // discards the return address from the stack, we check for these
482     // fake calls in malware mode
483     if (_obj->defensiveMode()) {
484         return isFakeCall();
485     }
486     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.                
487     return false;
488 }
489
490 Address IA_IAPI::getCFT() const
491 {
492     if(validCFT) return cachedCFT;
493     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
494         // FIXME: templated bind(),dammit!
495     callTarget->bind(thePC[_isrc->getArch()].get(), Result(s64, current));
496     parsing_printf("%s[%d]: binding PC %s in %s to 0x%x...", FILE__, __LINE__,
497                    thePC[_isrc->getArch()]->format().c_str(), curInsn()->format().c_str(), current);
498
499     Result actualTarget = callTarget->eval();
500 #if defined(os_vxworks)
501     if (actualTarget.convert<Address>() == current) {
502         // We have a zero offset branch.  Consider relocation information.
503         SymtabCodeRegion *scr = dynamic_cast<SymtabCodeRegion *>(_cr);
504         SymtabCodeSource *scs = dynamic_cast<SymtabCodeSource *>(_obj->cs());
505
506         if (!scr && scs) {
507             set<CodeRegion *> regions;
508             assert( scs->findRegions(current, regions) == 1 );
509             scr = dynamic_cast<SymtabCodeRegion *>(*regions.begin());
510         }
511
512         SymtabAPI::Symbol *sym = NULL;
513         if (scr) {
514             std::vector<SymtabAPI::relocationEntry> relocs =
515                 scr->symRegion()->getRelocations();
516
517             for (unsigned i = 0; i < relocs.size(); ++i) {
518                 if (relocs[i].rel_addr() == current) {
519                     sym = relocs[i].getDynSym();
520                     if (sym && sym->getOffset()) {
521                         parsing_printf(" <reloc hit> ");
522                         actualTarget = Result(s64, sym->getOffset());
523                     }
524                     break;
525                 }
526             }
527         }
528
529         if (sym && sym->getOffset() == 0) {
530             // VxWorks external call.
531             // Need some external means to find the target.
532             Address found;
533             const std::string &sym_name = sym->getMangledName();
534             if (wtxFindFunction(sym_name.c_str(), 0x0, found)) {
535                 parsing_printf(" <wtx search hit> ");
536                 actualTarget = Result(s64, found);
537
538                 // We've effectively found a plt call.  Update linkage table.
539                 _obj->cs()->linkage()[found] = sym_name;
540
541             } else {
542                 parsing_printf(" <wtx fail %s> ", sym_name.c_str());
543                 actualTarget.defined = false;
544             }
545         }
546     }
547 #endif
548
549     if(actualTarget.defined)
550     {
551         cachedCFT = actualTarget.convert<Address>();
552         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
553     }
554     else
555     {
556         cachedCFT = 0;
557         parsing_printf("FAIL (CFT=0x%x), callTarget exp: %s\n",
558                        cachedCFT,callTarget->format().c_str());
559     }
560     validCFT = true;
561
562     if(isLinkerStub()) {
563         parsing_printf("Linker stub detected: Correcting CFT.  (CFT=0x%x)\n",
564                        cachedCFT);
565     }
566
567     return cachedCFT;
568 }
569
570 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
571 {
572     Instruction::Ptr ci = curInsn();
573     if(ci && (ci->getCategory() == c_CallInsn))
574     {
575         if(!isDynamicCall())
576         {
577             if(!_isrc->isValidAddress(getCFT()))
578             {
579                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
580                                getCFT());
581                 return false;
582             }
583         }
584     }
585     if(lvl == HAS_BR_INDIR)
586     {
587         return false;
588     }
589     return true;
590 }
591
592 bool IA_IAPI::parseJumpTable(Dyninst::ParseAPI::Block* currBlk,
593                     std::vector<std::pair< Address, Dyninst::ParseAPI::EdgeTypeEnum > >& outEdges) const
594 {
595     IA_platformDetails* jumpTableParser = makePlatformDetails(_isrc->getArch(), this);
596     bool ret = jumpTableParser->parseJumpTable(currBlk, outEdges);
597     delete jumpTableParser;
598     return ret;
599 }
600
601
602
603 InstrumentableLevel IA_IAPI::getInstLevel(Function * context, unsigned int num_insns) const
604 {
605     InstrumentableLevel ret = InstructionAdapter::getInstLevel(context, num_insns);
606 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
607     {
608         return NORMAL;
609 }*/
610     return ret;
611 }