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 }