properly link unresolvable indirect branches to sink block
[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.h"
40
41 #include <deque>
42 #include <map>
43
44 using namespace Dyninst;
45 using namespace InstructionAPI;
46 using namespace Dyninst::InsnAdapter;
47 using namespace Dyninst::ParseAPI;
48
49 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::framePtr;
50 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::stackPtr;
51 std::map<Architecture, RegisterAST::Ptr> IA_IAPI::thePC;
52
53 void IA_IAPI::initASTs()
54 {
55     if(framePtr.empty())
56     {
57         framePtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86)));
58         framePtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_x86_64)));
59         framePtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc32)));
60         framePtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getFramePointer(Arch_ppc64)));
61     }
62     if(stackPtr.empty())
63     {
64         stackPtr[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86)));
65         stackPtr[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_x86_64)));
66         stackPtr[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc32)));
67         stackPtr[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getStackPointer(Arch_ppc64)));
68     }
69     if(thePC.empty())
70     {
71         thePC[Arch_x86] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86)));
72         thePC[Arch_x86_64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_x86_64)));
73         thePC[Arch_ppc32] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc32)));
74         thePC[Arch_ppc64] = RegisterAST::Ptr(new RegisterAST(MachRegister::getPC(Arch_ppc64)));
75     }
76 }
77
78 IA_IAPI::IA_IAPI(InstructionDecoder dec_, 
79         Address where_,
80         CodeObject * o,
81         CodeRegion * r,
82         InstructionSource *isrc) :
83     InstructionAdapter(where_, o, r, isrc), 
84     dec(dec_),
85     validCFT(false), 
86     cachedCFT(0)
87 {
88     hascftstatus.first = false;
89     tailCall.first = false;
90     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
91     initASTs();
92 }
93
94 void IA_IAPI::advance()
95 {
96     if(!curInsn()) {
97         parsing_printf("..... WARNING: failed to advance InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
98                        allInsns.size());
99         return;
100     }
101     InstructionAdapter::advance();
102     current += curInsn()->size();
103     boost::tuples::tie(curInsnIter, boost::tuples::ignore) = allInsns.insert(std::make_pair(current, dec.decode()));
104     if(!curInsn())
105     {
106         parsing_printf("......WARNING: after advance at 0x%lx, curInsn() NULL\n", current);
107     }
108     validCFT = false;
109     hascftstatus.first = false;
110     tailCall.first = false;
111 }
112
113 void IA_IAPI::retreat()
114 {
115     if(!curInsn()) {
116         parsing_printf("..... WARNING: failed to retreat InstructionAdapter at 0x%lx, allInsns.size() = %d\n", current,
117                        allInsns.size());
118         return;
119     }
120     InstructionAdapter::retreat();
121     std::map<Address,Instruction::Ptr>::iterator remove = curInsnIter;
122     if(curInsnIter != allInsns.begin()) {
123         --curInsnIter;
124         allInsns.erase(remove);
125         current = curInsnIter->first;
126         if(curInsnIter != allInsns.begin()) {
127             std::map<Address,Instruction::Ptr>::iterator pit = curInsnIter;
128             --pit;
129             previous = curInsnIter->first;
130         } else {
131             previous = -1;
132         }
133     } else {
134         parsing_printf("..... WARNING: cowardly refusal to retreat past first instruction at 0x%lx\n", current);
135     }
136
137     /* blind duplication -- nate */
138     validCFT = false;
139     hascftstatus.first = false;
140     tailCall.first = false;
141
142     
143     
144
145 size_t IA_IAPI::getSize() const
146 {
147     Instruction::Ptr ci = curInsn();
148     assert(ci);
149     return ci->size();
150 }
151
152 bool IA_IAPI::hasCFT() const
153 {
154     if(hascftstatus.first) return hascftstatus.second;
155     InsnCategory c = curInsn()->getCategory();
156     hascftstatus.second = false;
157     if(c == c_BranchInsn ||
158        c == c_ReturnInsn)
159     {
160         hascftstatus.second = true;
161     }
162     if(c == c_CallInsn)
163     {
164         if(isRealCall()) {
165             hascftstatus.second = true;
166         }
167         if(isDynamicCall()) {
168             hascftstatus.second = true;
169         }
170         if(simulateJump()) {
171             hascftstatus.second = true;
172         }
173     }
174     hascftstatus.first = true;
175     return hascftstatus.second;
176 }
177
178 bool IA_IAPI::isAbortOrInvalidInsn() const
179 {
180     entryID e = curInsn()->getOperation().getID();
181     if(e == e_No_Entry)
182     {
183         parsing_printf("...WARNING: un-decoded instruction at 0x%x\n", current);
184     }
185     return e == e_No_Entry ||
186             e == e_int3 ||
187             e == e_hlt;
188 }
189
190 bool IA_IAPI::isFrameSetupInsn() const
191 {
192     return isFrameSetupInsn(curInsn());
193 }
194
195 bool IA_IAPI::isDynamicCall() const
196 {
197     Instruction::Ptr ci = curInsn();
198     if(ci && (ci->getCategory() == c_CallInsn))
199     {
200         if(getCFT() == 0)
201         {
202             parsing_printf("... Call 0x%lx is indirect\n", current);
203             return true;
204         }
205     }
206     return false;
207 }
208
209 bool IA_IAPI::isAbsoluteCall() const
210 {
211     Instruction::Ptr ci = curInsn();
212     if(ci->getCategory() == c_CallInsn)
213     {
214         Expression::Ptr cft = ci->getControlFlowTarget();
215         if(cft && dyn_detail::boost::dynamic_pointer_cast<Immediate>(cft))
216         {
217             return true;
218         }
219     }
220     return false;
221 }
222
223
224 bool IA_IAPI::isReturn() const
225 {
226     return curInsn()->getCategory() == c_ReturnInsn;
227 }
228 bool IA_IAPI::isBranch() const
229 {
230     return curInsn()->getCategory() == c_BranchInsn;
231 }
232 bool IA_IAPI::isCall() const
233 {
234     return curInsn()->getCategory() == c_CallInsn;
235 }
236
237 bool IA_IAPI::isInterruptOrSyscall() const
238 {
239     return (isInterrupt() && isSyscall());
240 }
241
242 bool IA_IAPI::isSyscall() const
243 {
244     static RegisterAST::Ptr gs(new RegisterAST(x86::gs));
245     
246     Instruction::Ptr ci = curInsn();
247
248     return (((ci->getOperation().getID() == e_call) &&
249             /*(curInsn()->getOperation().isRead(gs))) ||*/
250             (ci->getOperand(0).format() == "16")) ||
251             (ci->getOperation().getID() == e_syscall) || 
252             (ci->getOperation().getID() == e_int) || 
253             (ci->getOperation().getID() == power_op_sc));
254 }
255
256
257 bool IA_IAPI::isInterrupt() const
258 {
259     Instruction::Ptr ci = curInsn();
260     return ((ci->getOperation().getID() == e_int) ||
261             (ci->getOperation().getID() == e_int3));
262 }
263
264 void IA_IAPI::getNewEdges(
265         std::vector<std::pair< Address, EdgeTypeEnum> >& outEdges,
266         Function* context,
267         Block* currBlk,
268         unsigned int num_insns,
269         dyn_hash_map<Address, std::string> *plt_entries) const
270 {
271     Instruction::Ptr ci = curInsn();
272
273     // Only call this on control flow instructions!
274     if(ci->getCategory() == c_CallInsn)
275     {
276         Address target = getCFT();
277         if(isRealCall() || isDynamicCall())
278         {
279             outEdges.push_back(std::make_pair(target, NOEDGE));
280         }
281         else
282         {
283             if(_isrc->isValidAddress(target))
284             {
285                 if(simulateJump())
286                 {
287                     parsing_printf("[%s:%u] call at 0x%lx simulated as "
288                             "jump to 0x%lx\n",
289                     FILE__,__LINE__,getAddr(),getCFT());
290                     outEdges.push_back(std::make_pair(target, DIRECT));
291                     return;
292                 }
293             }
294         }
295         outEdges.push_back(std::make_pair(getAddr() + getSize(),
296                            CALL_FT));
297         return;
298     }
299     else if(ci->getCategory() == c_BranchInsn)
300     {
301         Address target;
302         if(ci->allowsFallThrough())
303         {
304             outEdges.push_back(std::make_pair(getCFT(),
305                                COND_TAKEN));
306             outEdges.push_back(std::make_pair(getNextAddr(), COND_NOT_TAKEN));
307             return;
308         }
309         // Direct jump
310         else if((target = getCFT()) != 0)
311         {
312             Address catchStart;
313             if(_cr->findCatchBlock(getNextAddr(),catchStart))
314             {
315                 outEdges.push_back(std::make_pair(catchStart, CATCH));
316             }
317         
318
319             if(!isTailCall(context,num_insns))
320             {
321                 if(plt_entries->find(target) == plt_entries->end())
322                 {
323                     outEdges.push_back(std::make_pair(target,DIRECT));
324                 }
325                 else
326                 {
327                     parsing_printf("%s[%d]: PLT tail call to %x (%s)\n", 
328                         FILE__, __LINE__, target,
329                         (*plt_entries)[target].c_str());
330                     outEdges.push_back(std::make_pair(target, NOEDGE));
331                     tailCall.second = true;
332                 }
333             }
334             else
335             {
336                 parsing_printf("%s[%d]: tail call to %x\n", 
337                     FILE__, __LINE__, target);
338                 outEdges.push_back(std::make_pair(target, NOEDGE));
339             }
340             return;
341         }
342         else
343         {
344             parsing_printf("... indirect jump at 0x%x\n", current);
345             if( num_insns == 2 ) {
346                 parsing_printf("... uninstrumentable due to 0 size\n");
347                 return;
348             }
349             if(isTailCall(context,num_insns)) {
350                 parsing_printf("%s[%d]: indirect tail call %s at 0x%lx\n", FILE__, __LINE__,
351                                ci->format().c_str(), current);
352                 return;
353             }
354             parsing_printf("%s[%d]: jump table candidate %s at 0x%lx\n", FILE__, __LINE__,
355                            ci->format().c_str(), current);
356             parsedJumpTable = true;
357             successfullyParsedJumpTable = parseJumpTable(currBlk, outEdges);
358
359             if(!successfullyParsedJumpTable || outEdges.empty()) {
360                 outEdges.push_back(std::make_pair((Address)-1,INDIRECT));
361             }
362             return;
363         }
364     }
365     else if(ci->getCategory() == c_ReturnInsn)
366     {
367         if(ci->allowsFallThrough())
368         {
369             outEdges.push_back(std::make_pair(getNextAddr(), FALLTHROUGH));
370             return;
371         }
372         return;
373     }
374     fprintf(stderr, "Unhandled instruction %s\n", ci->format().c_str());
375     assert(0);
376 }
377
378 bool IA_IAPI::isIPRelativeBranch() const
379 {
380             // These don't exist on IA32...
381 #if !defined(arch_x86_64)
382     return false;
383 #endif
384     Instruction::Ptr ci = curInsn();
385
386     if(ci->getCategory() == c_BranchInsn &&
387         !getCFT())
388 {
389     Expression::Ptr cft = ci->getControlFlowTarget();
390     if(cft->isUsed(thePC[_isrc->getArch()]))
391     {
392         parsing_printf("\tIP-relative indirect jump to %s at 0x%lx\n",
393                        cft->format().c_str(), current);
394         return true;
395     }
396 }
397     return false;
398     
399 }
400
401 Instruction::Ptr IA_IAPI::curInsn() const
402 {
403     return curInsnIter->second;
404 }
405
406 bool IA_IAPI::isLeave() const
407 {
408     Instruction::Ptr ci = curInsn();
409     return ci && (ci->getOperation().getID() == e_leave);
410 }
411
412 bool IA_IAPI::isDelaySlot() const
413 {
414 #if defined(arch_sparc)
415     assert(!"Implement delay slots on SPARC!");
416 #endif
417     return false;
418 }
419
420 Instruction::Ptr IA_IAPI::getInstruction()
421 {
422     return curInsn();
423 }
424
425 bool IA_IAPI::isRealCall() const
426 {
427     if(getCFT() == getNextAddr())
428     {
429         parsing_printf("... getting PC\n");
430         return false;
431     }
432     if(!_isrc->isValidAddress(getCFT()))
433     {
434         parsing_printf(" isREalCall whacked by _isrc->isVAlidAddress(%lx)\n",
435             getCFT());
436         return false;
437     }
438     return (!isThunk());
439 }
440
441 std::map<Address, bool> IA_IAPI::thunkAtTarget;
442
443 bool IA_IAPI::isConditional() const
444 {
445     return curInsn()->allowsFallThrough();
446 }
447
448 bool IA_IAPI::simulateJump() const
449 {
450     // TODO: we don't simulate jumps on x86 architectures; add logic as we need it.                
451     return false;
452 }
453
454 Address IA_IAPI::getCFT() const
455 {
456     if(validCFT) return cachedCFT;
457     Expression::Ptr callTarget = curInsn()->getControlFlowTarget();
458         // FIXME: templated bind(),dammit!
459     callTarget->bind(thePC[_isrc->getArch()].get(), Result(s64, current));
460     parsing_printf("%s[%d]: binding PC %s in %s to 0x%x...", FILE__, __LINE__,
461                    thePC[_isrc->getArch()]->format().c_str(), curInsn()->format().c_str(), current);
462     Result actualTarget = callTarget->eval();
463     if(actualTarget.defined)
464     {
465         cachedCFT = actualTarget.convert<Address>();
466         parsing_printf("SUCCESS (CFT=0x%x)\n", cachedCFT);
467     }
468     else
469     {
470         cachedCFT = 0;
471         parsing_printf("FAIL (CFT=0x%x), callTarget exp: %s\n", cachedCFT,callTarget->format().c_str());
472     }
473     validCFT = true;
474     return cachedCFT;
475 }
476
477 bool IA_IAPI::isRelocatable(InstrumentableLevel lvl) const
478 {
479     Instruction::Ptr ci = curInsn();
480     if(ci && (ci->getCategory() == c_CallInsn))
481     {
482         if(!isDynamicCall())
483         {
484             if(!_isrc->isValidAddress(getCFT()))
485             {
486                 parsing_printf("... Call to 0x%lx is invalid (outside code or data)\n",
487                                getCFT());
488                 return false;
489             }
490         }
491     }
492     if(lvl == HAS_BR_INDIR)
493     {
494         return false;
495     }
496     return true;
497 }
498
499 InstrumentableLevel IA_IAPI::getInstLevel(Function * context, unsigned int num_insns) const
500 {
501     InstrumentableLevel ret = InstructionAdapter::getInstLevel(context, num_insns);
502 /*    if(ret == HAS_BR_INDIR && isIPRelativeBranch())
503     {
504         return NORMAL;
505 }*/
506     return ret;
507 }