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