dyninstAPI/src/stackanalysis.C

   1 /*
   2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
  12  * charge. We define "research use" to mean you may freely use it
  13  * inside your organization for whatever purposes you see fit. But you
  14  * may not re-distribute Paradyn or parts of Paradyn, in any form
  15  * source or binary (including derivatives), electronic or otherwise,
  16  * to any other organization or entity without our permission.
  17  *
  18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
  19  *
  20  * All warranties, including without limitation, any warranty of
  21  * merchantability or fitness for a particular purpose, are hereby
  22  * excluded.
  23  *
  24  * By your use of Paradyn, you understand and agree that we (or any
  25  * other person or entity with proprietary rights in Paradyn) are
  26  * under no obligation to provide either maintenance services,
  27  * update services, notices of latent defects, or correction of
  28  * defects for Paradyn.
  29  *
  30  * Even if advised of the possibility of such damages, under no
  31  * circumstances shall we (or any other person or entity with
  32  * proprietary rights in the software licensed hereunder) be liable
  33  * to you or any third party for direct, indirect, or consequential
  34  * damages of any character regardless of type of action, including,
  35  * without limitation, loss of profits, loss of use, loss of good
  36  * will, or computer failure or malfunction.  You agree to indemnify
  37  * us (and any other person or entity with proprietary rights in the
  38  * software licensed hereunder) for any and all liability it may
  39  * incur to third parties resulting from your use of Paradyn.
  40  */
  41
  42 #include "dyninstAPI/src/function.h"
  43 #include "dyninstAPI/src/symtab.h"
  44 #include "instPoint.h"
  45
  46 #include "instructionAPI/h/InstructionDecoder.h"
  47 #include "instructionAPI/h/Result.h"
  48 #include "instructionAPI/h/Instruction.h"
  49
  50 #include <queue>
  51 #include <vector>
  52
  53 #include "stackanalysis.h"
  54
  55 #include "Annotatable.h"
  56
  57 #include "debug.h"
  58
  59 using namespace Dyninst;
  60 using namespace InstructionAPI;
  61
  62 const StackAnalysis::StackHeight StackAnalysis::StackHeight::bottom(StackAnalysis::StackHeight::notUnique);
  63 const StackAnalysis::StackHeight StackAnalysis::StackHeight::top(StackAnalysis::StackHeight::uninitialized);
  64
  65 AnnotationClass <StackAnalysis::HeightTree> StackHeightAnno(std::string("StackHeightAnno"));
  66 AnnotationClass <StackAnalysis::PresenceTree> StackPresenceAnno(std::string("StackPresenceAnno"));
  67
  68
  69 //
  70 //
  71 // Concepts:
  72 //
  73 // There are three terms we throw around:
  74 //
  75 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
  76 // Stack delta: the difference in the size of the stack over the execution of
  77 //   a region of code (basic block here). (block_end_stack_ptr - block_start_stack_ptr)
  78 // Stack clean: the amount the callee function shifts the stack. This is an x86 idiom.
  79 //   On x86 the caller pushes arguments onto the stack (and thus shifts the stack).
  80 //   Normally the caller also cleans the stack (that is, removes arguments). However,
  81 //   some callee functions perform this cleaning themselves. We need to account for this
  82 //   in our analysis, which otherwise assumes that callee functions don't alter the stack.
  83 //
  84
  85 bool StackAnalysis::analyze()
  86 {
  87     stanalysis_printf("Beginning stack analysis for function %s\n",
  88                       func->symTabName().c_str());
  89     blocks = func->blocks();
  90     if (blocks.empty()) return false;
  91
  92     blocks = func->blocks();
  93
  94     stanalysis_printf("\tSummarizing block effects\n");
  95     summarizeBlockDeltas();
  96
  97     stanalysis_printf("\tPerforming fixpoint analysis\n");
  98     calculateInterBlockDepth();
  99
 100     stanalysis_printf("\tCreating interval trees\n");
 101     createIntervals();
 102
 103     func->addAnnotation(heightIntervals_, StackHeightAnno);
 104     func->addAnnotation(presenceIntervals_, StackPresenceAnno);
 105
 106     if (dyn_debug_stackanalysis) {
 107         debugStackHeights();
 108         debugStackPresences();
 109     }
 110
 111     stanalysis_printf("Finished stack analysis for function %s\n",
 112                       func->symTabName().c_str());
 113
 114     return true;
 115 }
 116
 117 void StackAnalysis::summarizeBlockDeltas() {
 118     // STACK HEIGHT:
 119     // Foreach block B:
 120     //   Let acc = 0;
 121     //   Foreach (insn i, offset o) in B:
 122     //     Let d = change in stack height at i;
 123     //     Let acc += d;
 124     //     blockToInsnDeltas[B][o] = d;
 125     //   blockHeightDeltas[B] = acc;
 126
 127     // STACK PRESENCE:
 128     // Foreach block B:
 129     //   Let d = uninitialized;
 130     //   Foreach (insn i, offset o) in B:
 131     //     d = change in stack presence at d;
 132     //     blockToInsnDeltas[B][o] = d;
 133     //   blockHeightDeltas[B] = d;
 134
 135     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
 136         Block *block = *iter;
 137         stanalysis_printf("\t Block starting at 0x%lx\n", block->firstInsnOffset());
 138
 139         StackHeight heightChange(0);
 140         StackPresence stackPresence;
 141
 142         std::vector<std::pair<InstructionAPI::Instruction, Offset> > instances;
 143         block->getInsnInstances(instances);
 144
 145         for (unsigned j = 0; j < instances.size(); j++) {
 146             InstructionAPI::Instruction insn = instances[j].first;
 147             Offset off = instances[j].second;
 148
 149             // Can go top...
 150             StackHeight delta;
 151             computeInsnEffects(block, insn, off, delta, stackPresence);
 152             blockToInsnDeltas[block][off] = delta;
 153             blockToInsnPresence[block][off] = stackPresence;
 154
 155             heightChange += delta;
 156         }
 157         blockHeightDeltas[block] = heightChange;
 158         blockPresenceDeltas[block] = stackPresence;
 159     }
 160 }
 161
 162 void StackAnalysis::calculateInterBlockDepth() {
 163
 164     std::queue<Block *> worklist;
 165
 166     worklist.push(func->entryBlock());
 167
 168     //BlockHeight_t blockHeights; // This by default initializes all entries to "bottom".
 169
 170     while (!worklist.empty()) {
 171         Block *block = worklist.front();
 172         stanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n", block->firstInsnOffset());
 173
 174         worklist.pop();
 175
 176         // Step 1: calculate the meet over the heights of all incoming
 177         // intraprocedural blocks.
 178
 179         std::set<StackHeight> inHeights;
 180         std::set<StackPresence> inPresences;
 181
 182         if (block->isEntryBlock(func)) {
 183             // The in height is 0
 184             inHeights.insert(StackHeight(0));
 185             inPresences.insert(StackPresence(StackPresence::noFrame));
 186         }
 187         else {
 188             std::vector<Edge *> inEdges; block->getSources(inEdges);
 189             for (unsigned i = 0; i < inEdges.size(); i++) {
 190                 Edge *edge = inEdges[i];
 191                 if (edge->getType() == ET_CALL) continue;
 192                 inHeights.insert(outBlockHeights[edge->getSource()]);
 193                 inPresences.insert(outBlockPresences[edge->getSource()]);
 194             }
 195         }
 196
 197         StackHeight newInHeight = StackHeight::meet(inHeights);
 198         StackPresence newInPresence = StackPresence::meet(inPresences);
 199
 200         // Step 2: see if the input has changed
 201
 202         if ((newInHeight == inBlockHeights[block]) &&
 203             (newInPresence == inBlockPresences[block])) {
 204             // No new work here
 205             continue;
 206         }
 207
 208         // Step 3: calculate our new out height
 209
 210         inBlockHeights[block] = newInHeight;
 211         outBlockHeights[block] = newInHeight + blockHeightDeltas[block];
 212
 213         inBlockPresences[block] = newInPresence;
 214         // If there was no change in the block then use the in presence; otherwise
 215         // use the change in the block. Effectively a 2-part meet.
 216         outBlockPresences[block] = (blockPresenceDeltas[block].isTop()) ? (newInPresence) : (blockPresenceDeltas[block]);
 217
 218         // Step 4: push all children on the worklist.
 219
 220         std::vector<Edge *> outEdges; block->getTargets(outEdges);
 221
 222         for (unsigned i = 0; i < outEdges.size(); i++) {
 223             if (outEdges[i]->getType() == ET_CALL) continue;
 224             worklist.push(outEdges[i]->getTarget());
 225         }
 226     }
 227 }
 228
 229 void StackAnalysis::createIntervals() {
 230     // Use the results summaries to calculate the
 231     // stack heights. We expect that heights will
 232     // change infrequently and so summarize them at
 233     // the function level.
 234
 235     heightIntervals_ = new HeightTree();
 236     presenceIntervals_ = new PresenceTree();
 237
 238     StackHeight curHeight;
 239     Offset curLB = 0;
 240     Offset curUB = 0;
 241
 242     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
 243         Block *block = *iter;
 244
 245         stanalysis_printf("\t Interval creation: visiting block at 0x%lx\n", block->firstInsnOffset());
 246
 247         curLB = block->firstInsnOffset();
 248         curUB = 0;
 249         curHeight = inBlockHeights[block];
 250
 251         // Now create extents for instructions within this block.
 252
 253         for (InsnDeltas::iterator iter = blockToInsnDeltas[block].begin();
 254              iter != blockToInsnDeltas[block].end();
 255              iter++) {
 256             // Now create extents for instructions within this block.
 257             if ((*iter).second == StackHeight(0)) {
 258                 continue;
 259             }
 260
 261             // We've changed the height of the stack. End this interval
 262             // and start a new one.
 263             //
 264             // We need to determine UB. It's defined as the end of the
 265             // current instruction. Therefore there are two cases:
 266             // if we're the last insn (take the block end) or not
 267             // the last insn (take the start of the next insn)
 268             InsnDeltas::iterator iter2 = iter;
 269             iter2++;
 270             if (iter2 == blockToInsnDeltas[block].end()) {
 271                 curUB = block->endOffset();
 272             }
 273             else {
 274                 curUB = (*iter2).first;
 275             }
 276             heightIntervals_->insert(curLB, curUB, curHeight);
 277
 278             // Start a new one
 279             curLB = curUB;
 280             curUB = 0;
 281             curHeight += (*iter).second;
 282
 283         }
 284
 285         if (curLB != block->endOffset()) {
 286             // Cap off the extent for the current block
 287             curUB = block->endOffset();
 288             if (curHeight != outBlockHeights[block]) {
 289                 fprintf(stderr, "ERROR: inconsistency in stack analysis, %s != %s\n",
 290                         curHeight.getString().c_str(), outBlockHeights[block].getString().c_str());
 291             }
 292             assert(curHeight == outBlockHeights[block]);
 293             heightIntervals_->insert(curLB, curUB, curHeight);
 294         }
 295     }
 296
 297     StackPresence curPres;
 298     curUB = 0;
 299     curLB = 0;
 300
 301     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
 302         Block *block = *iter;
 303
 304         curLB = block->firstInsnOffset();
 305         curUB = 0;
 306         curPres = inBlockPresences[block];
 307
 308         for (InsnPresence::iterator iter = blockToInsnPresence[block].begin();
 309              iter != blockToInsnPresence[block].end();
 310              iter++) {
 311
 312             if ((*iter).second.isTop())
 313                 continue;
 314
 315             // We've changed the state of the stack pointer. End this interval
 316             // and start a new one.
 317             //
 318             // We need to determine UB. It's defined as the end of the
 319             // current instruction. Therefore there are two cases:
 320             // if we're the last insn (take the block end) or not
 321             // the last insn (take the start of the next insn)
 322             InsnPresence::iterator iter2 = iter;
 323             iter2++;
 324             if (iter2 == blockToInsnPresence[block].end()) {
 325                 curUB = block->endOffset();
 326             }
 327             else {
 328                 curUB = (*iter2).first;
 329             }
 330             presenceIntervals_->insert(curLB, curUB, curPres);
 331
 332             // Start a new one
 333             curLB = curUB;
 334             curUB = 0;
 335             curPres = (*iter).second;
 336         }
 337
 338         if (curLB != block->endOffset()) {
 339             // Cap off the extent for the current block
 340             curUB = block->endOffset();
 341             assert(curPres == outBlockPresences[block]);
 342             presenceIntervals_->insert(curLB, curUB, curPres);
 343         }
 344     }
 345 }
 346
 347
 348 void StackAnalysis::computeInsnEffects(const Block *block,
 349                                        const Instruction &insn,
 350                                        Offset off,
 351                                        StackHeight &height,
 352                                        StackPresence &pres)
 353 {
 354     stanalysis_printf("\t\tInsn at 0x%lx\n", off);
 355     Expression::Ptr theStackPtr(new RegisterAST(r_eSP));
 356     Expression::Ptr stackPtr32(new RegisterAST(r_ESP));
 357     Expression::Ptr stackPtr64(new RegisterAST(r_RSP));
 358
 359     Expression::Ptr theFramePtr(new RegisterAST(r_eBP));
 360     Expression::Ptr framePtr32(new RegisterAST(r_EBP));
 361     Expression::Ptr framePtr64(new RegisterAST(r_RBP));
 362
 363     //TODO: Integrate entire test into analysis lattice
 364     entryID what = insn.getOperation().getID();
 365
 366     if (insn.isWritten(theFramePtr) || insn.isWritten(framePtr32) || insn.isWritten(framePtr64)) {
 367         stanalysis_printf("\t\t\t FP written\n");
 368         if (what == e_mov &&
 369             (insn.isRead(theStackPtr) || insn.isRead(stackPtr32) || insn.isRead(stackPtr64))) {
 370             pres = StackPresence::frame;
 371             stanalysis_printf("\t\t\t Frame created\n");
 372         }
 373         else {
 374             pres = StackPresence::noFrame;
 375             stanalysis_printf("\t\t\t Frame destroyed\n");
 376         }
 377     }
 378
 379
 380    if (what == e_call)
 381    {
 382       pdvector<image_edge *> outs;
 383       block->getTargets(outs);
 384       for (unsigned i=0; i<outs.size(); i++) {
 385          image_edge *cur_edge = outs[i];
 386          if (cur_edge->getType() != ET_CALL)
 387              continue;
 388
 389          image_basicBlock *target_bbl = cur_edge->getTarget();
 390          image_func *target_func = target_bbl->getEntryFunc();
 391          if (!target_func)
 392              continue;
 393          height = getStackCleanAmount(target_func);
 394          stanalysis_printf("\t\t\t Stack height changed by self-cleaning function: %s\n", height.getString().c_str());
 395          return;
 396       }
 397       height = StackHeight(0);
 398       stanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
 399       return;
 400    }
 401
 402    int word_size = func->img()->getAddressWidth();
 403
 404    if(!insn.isWritten(theStackPtr) && !insn.isWritten(stackPtr32)) {
 405        height = StackHeight(0);
 406        return;
 407    }
 408    int sign = 1;
 409    switch(what)
 410    {
 411    case e_push:
 412        sign = -1;
 413    case e_pop: {
 414        Operand arg = insn.getOperand(0);
 415        if (arg.getValue()->eval().defined) {
 416            height = StackHeight(sign * word_size);
 417            stanalysis_printf("\t\t\t Stack height changed by evaluated push/pop: %s\n", height.getString().c_str());
 418            return;
 419        }
 420        height = StackHeight(sign * arg.getValue()->size());
 421        stanalysis_printf("\t\t\t Stack height changed by unevalled push/pop: %s\n", height.getString().c_str());
 422        return;
 423    }
 424    case e_sub:
 425        sign = -1;
 426    case e_add: {
 427        // Add/subtract are op0 += (or -=) op1
 428        Operand arg = insn.getOperand(1);
 429        Result delta = arg.getValue()->eval();
 430        if(delta.defined) {
 431            switch(delta.type) {
 432            case u8:
 433                height = StackHeight(sign * delta.val.u8val);
 434                break;
 435            case u16:
 436                height = StackHeight(sign * delta.val.u16val);
 437                break;
 438            case u32:
 439                height = StackHeight(sign * delta.val.u32val);
 440                break;
 441            case u64:
 442                height = StackHeight(sign * delta.val.u64val);
 443                break;
 444            case s8:
 445                height = StackHeight(sign * delta.val.s8val);
 446                break;
 447            case s16:
 448                height = StackHeight(sign * delta.val.s16val);
 449                break;
 450            case s32:
 451                height = StackHeight(sign * delta.val.s32val);
 452                break;
 453            case s64:
 454                height = StackHeight(sign * delta.val.s64val);
 455                break;
 456            default:
 457                // Add of anything that's not a "normal" integral type
 458                // means we don't know what happened
 459                height = StackHeight(StackHeight::bottom);
 460                break;
 461            }
 462            stanalysis_printf("\t\t\t Stack height changed by evalled add/sub: %s\n", height.getString().c_str());
 463            return;
 464        }
 465    }
 466        height = StackHeight(StackHeight::bottom);
 467        stanalysis_printf("\t\t\t Stack height changed by unevalled add/sub: %s\n", height.getString().c_str());
 468        return;
 469        // We treat return as zero-modification right now
 470    case e_ret_near:
 471    case e_ret_far:
 472        height = StackHeight(0);
 473        stanalysis_printf("\t\t\t Stack height changed by ret_near/ret_far %s\n", height.getString().c_str());
 474        return;
 475    default:
 476        stanalysis_printf("\t\t\t Stack height changed by unhandled insn %s: %s\n",
 477                          insn.format().c_str(), height.getString().c_str());
 478        height = StackHeight(StackHeight::bottom);
 479        return;
 480    }
 481    assert(0);
 482    return;
 483 }
 484
 485
 486 StackAnalysis::StackHeight StackAnalysis::getStackCleanAmount(image_func *func) {
 487     // Cache previous work...
 488     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
 489         return funcCleanAmounts[func];
 490     }
 491
 492     if (!func->cleansOwnStack()) {
 493         funcCleanAmounts[func] = StackHeight(0);
 494         return StackHeight(0);
 495     }
 496
 497     InstructionDecoder decoder;
 498     unsigned char *cur;
 499
 500     std::set<StackHeight> returnCleanVals;
 501
 502     for (unsigned i=0; i < func->funcExits().size(); i++) {
 503         cur = (unsigned char *) func->getPtrToInstruction(func->funcExits()[i]->offset());
 504         size_t size = 0;
 505         Instruction insn = decoder.decode(cur, size);
 506
 507         entryID what = insn.getOperation().getID();
 508         if (what != e_ret_near)
 509             continue;
 510
 511         int val;
 512         std::vector<Operand> ops;
 513         insn.getOperands(ops);
 514         if (ops.size() == 0) {
 515             val = 0;
 516         }
 517         else {
 518             Result imm = ops[0].getValue()->eval();
 519             assert(imm.defined);
 520             val = (int) imm.val.s16val;
 521         }
 522         returnCleanVals.insert(StackHeight(val));
 523     }
 524
 525     funcCleanAmounts[func] = StackHeight::meet(returnCleanVals);
 526     return funcCleanAmounts[func];
 527 }
 528
 529 StackAnalysis::StackAnalysis(Function *f) : func(f) {
 530     blocks = func->blocks();
 531     heightIntervals_ = NULL;
 532     presenceIntervals_ = NULL;
 533 }
 534
 535 const StackAnalysis::HeightTree *StackAnalysis::heightIntervals() {
 536     if (func == NULL) return NULL;
 537
 538     // Check the annotation
 539     HeightTree *ret;
 540     func->getAnnotation(ret, StackHeightAnno);
 541     if (ret) return ret;
 542     if (heightIntervals_ == NULL) {
 543         if (!analyze()) return NULL;
 544         ret = heightIntervals_;
 545     }
 546
 547     return ret;
 548 }
 549
 550
 551 const StackAnalysis::PresenceTree *StackAnalysis::presenceIntervals() {
 552     if (func == NULL) return NULL;
 553
 554     // Check the annotation
 555     PresenceTree *ret;
 556     func->getAnnotation(ret, StackPresenceAnno);
 557     if (ret) return ret;
 558
 559     if (presenceIntervals_ == NULL) {
 560         if (!analyze()) return NULL;
 561         ret = presenceIntervals_;
 562     }
 563
 564     return ret;
 565 }
 566
 567 void StackAnalysis::debugStackHeights() {
 568     if (!heightIntervals_) return;
 569     std::vector<std::pair<std::pair<Offset, Offset>, StackHeight> > elements;
 570     heightIntervals_->elements(elements);
 571
 572     for (unsigned i = 0; i < elements.size(); i++) {
 573         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
 574                 elements[i].first.first,
 575                 elements[i].first.second,
 576                 elements[i].second.getString().c_str());
 577     }
 578 }
 579
 580 void StackAnalysis::debugStackPresences() {
 581     if (!presenceIntervals_) return;
 582
 583     std::vector<std::pair<std::pair<Offset, Offset>, StackPresence> > elements;
 584     presenceIntervals_->elements(elements);
 585
 586     for (unsigned i = 0; i < elements.size(); i++) {
 587         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
 588                 elements[i].first.first,
 589                 elements[i].first.second,
 590                 elements[i].second.getString().c_str());
 591     }
 592 }
 593