emulator/qtools/callstack.h

   1 // Copyright 2006 The Android Open Source Project
   2
   3 #ifndef CALL_STACK_H
   4 #define CALL_STACK_H
   5
   6 #include "opcode.h"
   7 #include "armdis.h"
   8
   9 class CallStackBase {
  10   public:
  11     int    getId()          { return mId; }
  12     void   setId(int id)    { mId = id; }
  13
  14   private:
  15     int    mId;
  16 };
  17
  18 // Define a template class for the stack frame.  The template parameter
  19 // SYM is the symbol_type from the TraceReader<> template class. To
  20 // use the CallStack class, the user derives a subclass of StackFrame
  21 // and defines push() and pop() methods.  This derived class is then
  22 // passed as a template parameter to CallStack.
  23 template <class SYM>
  24 class StackFrame {
  25   public:
  26
  27     virtual ~StackFrame() {};
  28
  29     virtual void push(int stackLevel, uint64_t time, CallStackBase *base) {};
  30     virtual void pop(int stackLevel, uint64_t time, CallStackBase *base) {};
  31
  32     typedef SYM symbol_type;
  33     static const uint32_t kCausedException = 0x01;
  34     static const uint32_t kInterpreted     = 0x02;
  35     static const uint32_t kStartNative     = 0x04;
  36     static const uint32_t kPopBarrier      = (kCausedException | kInterpreted
  37         | kStartNative);
  38
  39     symbol_type *function;      // the symbol for the function we entered
  40     uint32_t    addr;           // return address when this function returns
  41     uint32_t    flags;
  42     uint32_t    time;           // for debugging when a problem occurred
  43     uint32_t    global_time;    // for debugging when a problem occurred
  44 };
  45
  46 template <class FRAME, class BASE = CallStackBase>
  47 class CallStack : public BASE {
  48 public:
  49     typedef FRAME frame_type;
  50     typedef typename FRAME::symbol_type symbol_type;
  51     typedef typename FRAME::symbol_type::region_type region_type;
  52     typedef BASE base_type;
  53
  54     CallStack(int id, int numFrames, TraceReaderType *trace);
  55     ~CallStack();
  56
  57     void    updateStack(BBEvent *event, symbol_type *function);
  58     void    popAll(uint64_t time);
  59     void    threadStart(uint64_t time);
  60     void    threadStop(uint64_t time);
  61
  62     // Set to true if you don't want to see any Java methods ever
  63     void    setNativeOnly(bool nativeOnly) {
  64         mNativeOnly = nativeOnly;
  65     }
  66
  67     int         getStackLevel() { return mTop; }
  68
  69     uint64_t    getGlobalTime(uint64_t time) { return time + mSkippedTime; }
  70     void        showStack(FILE *stream);
  71
  72     int         mNumFrames;
  73     FRAME       *mFrames;
  74     int         mTop;           // index of the next stack frame to write
  75
  76 private:
  77     enum Action { NONE, PUSH, POP, NATIVE_PUSH };
  78
  79     Action      getAction(BBEvent *event, symbol_type *function);
  80     void        doMethodAction(BBEvent *event, symbol_type *function);
  81     void        doMethodPop(BBEvent *event, uint32_t addr, const uint32_t flags);
  82     void        doSimplePush(symbol_type *function, uint32_t addr,
  83                              uint64_t time, int flags);
  84     void        doSimplePop(uint64_t time);
  85     void        doPush(BBEvent *event, symbol_type *function);
  86     void        doPop(BBEvent *event, symbol_type *function, Action methodAction);
  87
  88     TraceReaderType *mTrace;
  89
  90     // This is a global switch that disables Java methods from appearing
  91     // on the stack.
  92     bool        mNativeOnly;
  93
  94     // This keeps track of whether native frames are currently allowed on the
  95     // stack.
  96     bool        mAllowNativeFrames;
  97
  98     symbol_type mDummyFunction;
  99     region_type mDummyRegion;
 100
 101     symbol_type *mPrevFunction;
 102     BBEvent     mPrevEvent;
 103
 104     symbol_type *mUserFunction;
 105     BBEvent     mUserEvent;     // the previous user-mode event
 106
 107     uint64_t    mSkippedTime;
 108     uint64_t    mLastRunTime;
 109
 110     static MethodRec    sCurrentMethod;
 111     static MethodRec    sNextMethod;
 112 };
 113
 114 template<class FRAME, class BASE>
 115 MethodRec CallStack<FRAME, BASE>::sCurrentMethod;
 116 template<class FRAME, class BASE>
 117 MethodRec CallStack<FRAME, BASE>::sNextMethod;
 118
 119 template<class FRAME, class BASE>
 120 CallStack<FRAME, BASE>::CallStack(int id, int numFrames, TraceReaderType *trace)
 121 {
 122     mNativeOnly = false;
 123     mTrace = trace;
 124     BASE::setId(id);
 125     mNumFrames = numFrames;
 126     mFrames = new FRAME[mNumFrames];
 127     mTop = 0;
 128     mAllowNativeFrames = true;
 129
 130     memset(&mDummyFunction, 0, sizeof(symbol_type));
 131     memset(&mDummyRegion, 0, sizeof(region_type));
 132     mDummyFunction.region = &mDummyRegion;
 133     mPrevFunction = &mDummyFunction;
 134     memset(&mPrevEvent, 0, sizeof(BBEvent));
 135     mUserFunction = &mDummyFunction;
 136     memset(&mUserEvent, 0, sizeof(BBEvent));
 137     mSkippedTime = 0;
 138     mLastRunTime = 0;
 139
 140     // Read the first two methods from the trace if we haven't already read
 141     // from the method trace yet.
 142     if (sCurrentMethod.time == 0) {
 143         if (mTrace->ReadMethod(&sCurrentMethod)) {
 144             sCurrentMethod.time = ~0ull;
 145             sNextMethod.time = ~0ull;
 146         }
 147         if (sNextMethod.time != ~0ull && mTrace->ReadMethod(&sNextMethod)) {
 148             sNextMethod.time = ~0ull;
 149         }
 150     }
 151 }
 152
 153 template<class FRAME, class BASE>
 154 CallStack<FRAME, BASE>::~CallStack()
 155 {
 156     delete mFrames;
 157 }
 158
 159 template<class FRAME, class BASE>
 160 void
 161 CallStack<FRAME, BASE>::updateStack(BBEvent *event, symbol_type *function)
 162 {
 163     if (mNativeOnly) {
 164         // If this is an interpreted function, then use the native VM function
 165         // instead.
 166         if (function->vm_sym != NULL)
 167             function = function->vm_sym;
 168     } else {
 169         doMethodAction(event, function);
 170     }
 171
 172     Action action = getAction(event, function);
 173
 174     // Allow native frames if we are executing in the kernel.
 175     if (!mAllowNativeFrames
 176         && (function->region->flags & region_type::kIsKernelRegion) == 0) {
 177         action = NONE;
 178     }
 179
 180     if (function->vm_sym != NULL) {
 181         function = function->vm_sym;
 182         function->vm_sym = NULL;
 183     }
 184     if (action == PUSH) {
 185         doPush(event, function);
 186     } else if (action == POP) {
 187         doPop(event, function, NONE);
 188     }
 189
 190 #if 0
 191     // Pop off native functions before pushing or popping Java methods.
 192     if (action == POP && mPrevFunction->vm_sym == NULL) {
 193         // Pop off the previous function first.
 194         doPop(event, function, NONE);
 195         if (methodAction == POP) {
 196             doPop(event, function, POP);
 197         } else if (methodAction == PUSH) {
 198             doPush(event, function);
 199         }
 200     } else {
 201         if (methodAction != NONE) {
 202             // If the method trace has a push or pop, then do it.
 203             action = methodAction;
 204         } else if (function->vm_sym != NULL) {
 205             // This function is a Java method.  Don't push or pop the
 206             // Java method without a corresponding method trace record.
 207             action = NONE;
 208         }
 209         if (action == POP) {
 210             doPop(event, function, methodAction);
 211         } else if (action == PUSH) {
 212             doPush(event, function);
 213         }
 214     }
 215 #endif
 216
 217     // If the stack is now empty, then push the current function.
 218     if (mTop == 0) {
 219         uint64_t time = event->time - mSkippedTime;
 220         int flags = 0;
 221         if (function->vm_sym != NULL) {
 222             flags = FRAME::kInterpreted;
 223         }
 224         doSimplePush(function, 0, time, 0);
 225     }
 226
 227     mPrevFunction = function;
 228     mPrevEvent = *event;
 229 }
 230
 231 template<class FRAME, class BASE>
 232 void
 233 CallStack<FRAME, BASE>::threadStart(uint64_t time)
 234 {
 235     mSkippedTime += time - mLastRunTime;
 236 }
 237
 238 template<class FRAME, class BASE>
 239 void
 240 CallStack<FRAME, BASE>::threadStop(uint64_t time)
 241 {
 242     mLastRunTime = time;
 243 }
 244
 245 template<class FRAME, class BASE>
 246 typename CallStack<FRAME, BASE>::Action
 247 CallStack<FRAME, BASE>::getAction(BBEvent *event, symbol_type *function)
 248 {
 249     Action action;
 250     uint32_t offset;
 251
 252     // Compute the offset from the start of the function to this basic
 253     // block address.
 254     offset = event->bb_addr - function->addr - function->region->base_addr;
 255
 256     // Get the previously executed instruction
 257     Opcode op = OP_INVALID;
 258     int numInsns = mPrevEvent.num_insns;
 259     uint32_t insn = 0;
 260     if (numInsns > 0) {
 261         insn = mPrevEvent.insns[numInsns - 1];
 262         if (mPrevEvent.is_thumb) {
 263             insn = insn_unwrap_thumb(insn);
 264             op = decode_insn_thumb(insn);
 265         } else {
 266             op = Arm::decode(insn);
 267         }
 268     }
 269
 270     // The number of bytes in the previous basic block depends on
 271     // whether the basic block was ARM or THUMB instructions.
 272     int numBytes;
 273     if (mPrevEvent.is_thumb) {
 274         numBytes = numInsns << 1;
 275     } else {
 276         numBytes = numInsns << 2;
 277     }
 278
 279     // If this basic block follows the previous one, then return NONE.
 280     // If we don't do this, then we may be fooled into thinking this
 281     // is a POP if the previous block ended with a conditional
 282     // (non-executed) ldmia instruction.  We do this check before
 283     // checking if we are in a different function because we otherwise
 284     // we might be fooled into thinking this is a PUSH to a new function
 285     // when it is really just a fall-thru into a local kernel symbol
 286     // that just looks like a new function.
 287     uint32_t prev_end_addr = mPrevEvent.bb_addr + numBytes;
 288     if (prev_end_addr == event->bb_addr) {
 289         return NONE;
 290     }
 291
 292     // If this basic block is in the same function as the last basic block,
 293     // then just return NONE (but see the exceptions below).
 294     // Exception 1: if the function calls itself (offset == 0) then we
 295     // want to push this function.
 296     // Exception 2: if the function returns to itself, then we want
 297     // to pop this function.  We detect this case by checking if the last
 298     // instruction in the previous basic block was a load-multiple (ldm)
 299     // and included r15 as one of the loaded registers.
 300     if (function == mPrevFunction) {
 301         if (numInsns > 0) {
 302             // If this is the beginning of the function and the previous
 303             // instruction was not a branch, then it's a PUSH.
 304             if (offset == 0 && op != OP_B && op != OP_THUMB_B)
 305                 return PUSH;
 306
 307             // If the previous instruction was an ldm that loaded r15,
 308             // then it's a POP.
 309             if (offset != 0 && ((op == OP_LDM && (insn & 0x8000))
 310                                 || (op == OP_THUMB_POP && (insn & 0x100)))) {
 311                 return POP;
 312             }
 313         }
 314
 315         return NONE;
 316     }
 317
 318     // We have to figure out if this new function is a call or a
 319     // return.  We don't necessarily have a complete call stack (since
 320     // we could have started tracing at any point), so we have to use
 321     // heuristics.  If the address we are jumping to is the beginning
 322     // of a function, or if the instruction that took us there was
 323     // either "bl" or "blx" then this is a PUSH.  Also, if the
 324     // function offset is non-zero and the previous instruction is a
 325     // branch instruction, we will call it a PUSH.  This happens in
 326     // the kernel a lot when there is a branch to an offset from a
 327     // label. A couple more special cases:
 328     //
 329     //   - entering a .plt section ("procedure linkage table") is a PUSH,
 330     //   - an exception that jumps into the kernel vector entry point
 331     //     is also a push.
 332     //
 333     // If the function offset is non-zero and the previous instruction
 334     // is a bx or some non-branch instruction, then it's a POP.
 335     //
 336     // There's another special case that comes up.  The user code
 337     // might execute an instruction that returns but before the pc
 338     // starts executing in the caller, a kernel interrupt occurs.
 339     // But it may be hard to tell if this is a return until after
 340     // the kernel interrupt code is done and returns to user space.
 341     // So we save the last user basic block and look at it when
 342     // we come back into user space.
 343
 344     const uint32_t kIsKernelRegion = region_type::kIsKernelRegion;
 345
 346     if (((mPrevFunction->region->flags & kIsKernelRegion) == 0)
 347         && (function->region->flags & kIsKernelRegion)) {
 348         // We just switched into the kernel.  Save the previous
 349         // user-mode basic block and function.
 350         mUserEvent = mPrevEvent;
 351         mUserFunction = mPrevFunction;
 352     } else if ((mPrevFunction->region->flags & kIsKernelRegion)
 353                && ((function->region->flags & kIsKernelRegion) == 0)) {
 354         // We just switched from kernel to user mode.
 355         return POP;
 356     }
 357
 358     action = PUSH;
 359     if (offset != 0 && mPrevFunction != &mDummyFunction) {
 360         // We are jumping into the middle of a function, so this is
 361         // probably a return, not a function call.  But look at the
 362         // previous instruction first to see if it was a branch-and-link.
 363
 364         // If the previous instruction was not a branch (and not a
 365         // branch-and-link) then POP; or if it is a "bx" instruction
 366         // then POP because that is used to return from functions.
 367         if (!isBranch(op) || op == OP_BX || op == OP_THUMB_BX) {
 368             action = POP;
 369         } else if (isBranch(op) && !isBranchLink(op)) {
 370             // If the previous instruction was a normal branch to a
 371             // local symbol then don't count it as a push or a pop.
 372             action = NONE;
 373         }
 374
 375         if (function->flags & symbol_type::kIsVectorTable)
 376             action = PUSH;
 377     }
 378     return action;
 379 }
 380
 381
 382 template<class FRAME, class BASE>
 383 void CallStack<FRAME, BASE>::doPush(BBEvent *event, symbol_type *function)
 384 {
 385     uint64_t time = event->time - mSkippedTime;
 386
 387     // Check for stack overflow
 388     if (mTop >= mNumFrames) {
 389         // Don't show the stack by default because this generates a lot
 390         // of output and this is seen by users if there is an error when
 391         // post-processing the trace. But this is useful for debugging.
 392 #if 0
 393         showStack(stderr);
 394 #endif
 395         fprintf(stderr, "Error: stack overflow (%d frames)\n", mTop);
 396         exit(1);
 397     }
 398
 399     // Compute the return address here because we may need to change
 400     // it if we are popping off a frame for a vector table.
 401     int numBytes;
 402     if (mPrevEvent.is_thumb) {
 403         numBytes = mPrevEvent.num_insns << 1;
 404     } else {
 405         numBytes = mPrevEvent.num_insns << 2;
 406     }
 407     uint32_t retAddr = mPrevEvent.bb_addr + numBytes;
 408
 409     // If this is a Java method then set the return address to zero.
 410     // We won't be using it for popping the method and it may lead
 411     // to false matches when searching the stack.
 412     if (function->vm_sym != NULL) {
 413         retAddr = 0;
 414     }
 415
 416 #if 0
 417     // For debugging only.  Show the stack before entering the kernel
 418     // exception-handling code.
 419     if (function->flags & symbol_type::kIsVectorStart) {
 420         printf("stack before entering exception\n");
 421         showStack(stderr);
 422     }
 423 #endif
 424
 425     // If the top of stack is a vector table, then pop it
 426     // off before pushing on the new function.  Also, change the
 427     // return address for the new function to the return address
 428     // from the vector table.
 429     if (mTop > 0
 430         && (mFrames[mTop - 1].function->flags & symbol_type::kIsVectorTable)) {
 431         retAddr = mFrames[mTop - 1].addr;
 432         doSimplePop(time);
 433     }
 434
 435     const uint32_t kIsKernelRegion = region_type::kIsKernelRegion;
 436
 437     // The following code handles the case where one function, F1,
 438     // calls another function, F2, but the before F2 can start
 439     // executing, it takes a page fault (on the first instruction
 440     // in F2).  The kernel is entered, handles the page fault, and
 441     // then returns to the called function.  The problem is that
 442     // this looks like a new function call to F2 from the kernel.
 443     // The following code cleans up the stack by popping the
 444     // kernel frames back to F1 (but not including F1).  The
 445     // return address for F2 also has to be fixed up to point to
 446     // F1 instead of the kernel.
 447     //
 448     // We detect this case by checking if the previous basic block
 449     // was in the kernel and the current basic block is not.
 450     if ((mPrevFunction->region->flags & kIsKernelRegion)
 451         && ((function->region->flags & kIsKernelRegion) == 0)
 452         && mTop > 0) {
 453         // We are switching from kernel mode to user mode.
 454 #if 0
 455         // For debugging.
 456         printf("  doPush(): popping to user mode, bb_addr: 0x%08x\n",
 457                event->bb_addr);
 458         showStack(stderr);
 459 #endif
 460         do {
 461             // Pop off the kernel frames until we reach the one that
 462             // caused the exception.
 463             doSimplePop(time);
 464
 465             // If the next stack frame is the one that caused an
 466             // exception then stop popping frames.
 467             if (mTop > 0
 468                 && (mFrames[mTop - 1].flags & FRAME::kCausedException)) {
 469                 mFrames[mTop - 1].flags &= ~FRAME::kCausedException;
 470                 retAddr = mFrames[mTop].addr;
 471                 break;
 472             }
 473         } while (mTop > 0);
 474 #if 0
 475         // For debugging
 476         printf("  doPush() popping to level %d, using retAddr 0x%08x\n",
 477                mTop, retAddr);
 478 #endif
 479     }
 480
 481     // If we are starting an exception handler, then mark the previous
 482     // stack frame so that we know where to return when the exception
 483     // handler finishes.
 484     if ((function->flags & symbol_type::kIsVectorStart) && mTop > 0)
 485         mFrames[mTop - 1].flags |= FRAME::kCausedException;
 486
 487     // If the function being pushed is a Java method, then mark it on
 488     // the stack so that we don't pop it off until we get a matching
 489     // trace record from the method trace file.
 490     int flags = 0;
 491     if (function->vm_sym != NULL) {
 492         flags = FRAME::kInterpreted;
 493     }
 494     doSimplePush(function, retAddr, time, flags);
 495 }
 496
 497 template<class FRAME, class BASE>
 498 void CallStack<FRAME, BASE>::doSimplePush(symbol_type *function, uint32_t addr,
 499                                           uint64_t time, int flags)
 500 {
 501     // Check for stack overflow
 502     if (mTop >= mNumFrames) {
 503         showStack(stderr);
 504         fprintf(stderr, "too many stack frames (%d)\n", mTop);
 505         exit(1);
 506     }
 507
 508     mFrames[mTop].addr = addr;
 509     mFrames[mTop].function = function;
 510     mFrames[mTop].flags = flags;
 511     mFrames[mTop].time = time;
 512     mFrames[mTop].global_time = time + mSkippedTime;
 513
 514     mFrames[mTop].push(mTop, time, this);
 515     mTop += 1;
 516 }
 517
 518 template<class FRAME, class BASE>
 519 void CallStack<FRAME, BASE>::doSimplePop(uint64_t time)
 520 {
 521     if (mTop <= 0) {
 522         return;
 523     }
 524
 525     mTop -= 1;
 526     mFrames[mTop].pop(mTop, time, this);
 527
 528     if (mNativeOnly)
 529         return;
 530
 531     // If the stack is empty, then allow more native frames.
 532     // Otherwise, if we are transitioning from Java to native, then allow
 533     // more native frames.
 534     // Otherwise, if we are transitioning from native to Java, then disallow
 535     // more native frames.
 536     if (mTop == 0) {
 537         mAllowNativeFrames = true;
 538     } else {
 539         bool newerIsJava = (mFrames[mTop].flags & FRAME::kInterpreted) != 0;
 540         bool olderIsJava = (mFrames[mTop - 1].flags & FRAME::kInterpreted) != 0;
 541         if (newerIsJava && !olderIsJava) {
 542             // We are transitioning from Java to native
 543             mAllowNativeFrames = true;
 544         } else if (!newerIsJava && olderIsJava) {
 545             // We are transitioning from native to Java
 546             mAllowNativeFrames = false;
 547         }
 548     }
 549 }
 550
 551 template<class FRAME, class BASE>
 552 void CallStack<FRAME, BASE>::doPop(BBEvent *event, symbol_type *function,
 553                                    Action methodAction)
 554 {
 555     uint64_t time = event->time - mSkippedTime;
 556
 557     // Search backward on the stack for a matching return address.
 558     // The most common case is that we pop one stack frame, but
 559     // sometimes we pop more than one.
 560     int stackLevel;
 561     bool allowMethodPop = (methodAction == POP);
 562     for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) {
 563         if (event->bb_addr == mFrames[stackLevel].addr) {
 564             // We found a matching return address on the stack.
 565             break;
 566         }
 567
 568         // If this stack frame caused an exception, then do not pop
 569         // this stack frame.
 570         if (mFrames[stackLevel].flags & FRAME::kPopBarrier) {
 571             // If this is a Java method, then allow a pop only if we
 572             // have a matching trace record.
 573             if (mFrames[stackLevel].flags & FRAME::kInterpreted) {
 574                 if (allowMethodPop) {
 575                     // Allow at most one method pop
 576                     allowMethodPop = false;
 577                     continue;
 578                 }
 579             }
 580             stackLevel += 1;
 581             break;
 582         }
 583     }
 584
 585     // If we didn't find a matching return address then search the stack
 586     // again for a matching function.
 587     if (stackLevel < 0 || event->bb_addr != mFrames[stackLevel].addr) {
 588         bool allowMethodPop = (methodAction == POP);
 589         for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) {
 590             // Compare the function with the one in the stack frame.
 591             if (function == mFrames[stackLevel].function) {
 592                 // We found a matching function.  We want to pop up to but not
 593                 // including this frame.  But allow popping this frame if this
 594                 // method called itself and we have a method pop.
 595                 if (allowMethodPop && function == mPrevFunction) {
 596                     // pop this frame
 597                     break;
 598                 }
 599                 // do not pop this frame
 600                 stackLevel += 1;
 601                 break;
 602             }
 603
 604             // If this stack frame caused an exception, then do not pop
 605             // this stack frame.
 606             if (mFrames[stackLevel].flags & FRAME::kPopBarrier) {
 607                 // If this is a Java method, then allow a pop only if we
 608                 // have a matching trace record.
 609                 if (mFrames[stackLevel].flags & FRAME::kInterpreted) {
 610                     if (allowMethodPop) {
 611                         // Allow at most one method pop
 612                         allowMethodPop = false;
 613                         continue;
 614                     }
 615                 }
 616                 stackLevel += 1;
 617                 break;
 618             }
 619         }
 620         if (stackLevel < 0)
 621             stackLevel = 0;
 622     }
 623
 624     // Note that if we didn't find a matching stack frame, we will pop
 625     // the whole stack (unless there is a Java method or exception
 626     // frame on the stack).  This is intentional because we may have
 627     // started the trace in the middle of an executing program that is
 628     // returning up the stack and we do not know the whole stack.  So
 629     // the right thing to do is to empty the stack.
 630
 631     // If we are emptying the stack, then add the current function
 632     // on top.  If the current function is the same as the top of
 633     // stack, then avoid an extraneous pop and push.
 634     if (stackLevel == 0 && mFrames[0].function == function)
 635         stackLevel = 1;
 636
 637 #if 0
 638     // If we are popping off a large number of stack frames, then
 639     // we might have a bug.
 640     if (mTop - stackLevel > 7) {
 641         printf("popping thru level %d\n", stackLevel);
 642         showStack(stderr);
 643     }
 644 #endif
 645
 646     // Pop the stack frames
 647     for (int ii = mTop - 1; ii >= stackLevel; --ii)
 648         doSimplePop(time);
 649
 650     // Clear the "caused exception" bit on the current stack frame
 651     if (mTop > 0) {
 652         mFrames[mTop - 1].flags &= ~FRAME::kCausedException;
 653     }
 654
 655     // Also handle the case where F1 calls F2 and F2 returns to
 656     // F1, but before we can execute any instructions in F1, we
 657     // switch to the kernel.  Then when we return from the kernel
 658     // we want to pop off F2 from the stack instead of pushing F1
 659     // on top of F2.  To handle this case, we saved the last
 660     // user-mode basic block when we entered the kernel (in
 661     // the getAction() function) and now we can check to see if
 662     // that was a return to F1 instead of a call.  We use the
 663     // getAction() function to determine this.
 664     const uint32_t kIsKernelRegion = region_type::kIsKernelRegion;
 665     if ((mPrevFunction->region->flags & kIsKernelRegion)
 666         && ((function->region->flags & kIsKernelRegion) == 0)) {
 667         mPrevEvent = mUserEvent;
 668         mPrevFunction = mUserFunction;
 669         if (getAction(event, function) == POP) {
 670             // We may need to pop more than one frame, so just
 671             // call doPop() again.  This won't be an infinite loop
 672             // here because we changed mPrevEvent to the last
 673             // user-mode event.
 674             doPop(event, function, methodAction);
 675             return;
 676         }
 677     }
 678 }
 679
 680 template<class FRAME, class BASE>
 681 void CallStack<FRAME, BASE>::popAll(uint64_t time)
 682 {
 683     time -= mSkippedTime;
 684     while (mTop != 0) {
 685         doSimplePop(time);
 686     }
 687 }
 688
 689 template<class FRAME, class BASE>
 690 void CallStack<FRAME, BASE>::doMethodPop(BBEvent *event, uint32_t addr,
 691                                          const uint32_t flags)
 692 {
 693     uint64_t time = event->time - mSkippedTime;
 694
 695     // Search the stack from the top down for a frame that contains a
 696     // matching method.
 697     int stackLevel;
 698     for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) {
 699         if (mFrames[stackLevel].flags & flags) {
 700             // If we are searching for a native method, then don't bother trying
 701             // to match the address.
 702             if (flags == FRAME::kStartNative)
 703                 break;
 704             symbol_type *func = mFrames[stackLevel].function;
 705             uint32_t methodAddr = func->region->base_addr + func->addr;
 706             if (methodAddr == addr) {
 707                 break;
 708             }
 709         }
 710     }
 711
 712     // If we found a matching frame then pop the stack up to and including
 713     // that frame.
 714     if (stackLevel >= 0) {
 715         // Pop the stack frames
 716         for (int ii = mTop - 1; ii >= stackLevel; --ii)
 717             doSimplePop(time);
 718     }
 719 }
 720
 721 template<class FRAME, class BASE>
 722 void CallStack<FRAME, BASE>::doMethodAction(BBEvent *event, symbol_type *function)
 723 {
 724     // If the events get ahead of the method trace, then read ahead until we
 725     // sync up again.  This can happen if there is a pop of a method in the
 726     // method trace for which we don't have a previous push.  Such an unmatched
 727     // pop can happen because the user can start tracing at any time and so
 728     // there might already be a stack when we start tracing.
 729     while (event->time >= sNextMethod.time) {
 730         sCurrentMethod = sNextMethod;
 731         if (mTrace->ReadMethod(&sNextMethod)) {
 732             sNextMethod.time = ~0ull;
 733         }
 734     }
 735
 736     if (event->time >= sCurrentMethod.time && event->pid == sCurrentMethod.pid) {
 737         uint64_t time = event->time - mSkippedTime;
 738         int flags = sCurrentMethod.flags;
 739         if (flags == kMethodEnter) {
 740             doSimplePush(function, 0, time, FRAME::kInterpreted);
 741             mAllowNativeFrames = false;
 742         } else if (flags == kNativeEnter) {
 743             doSimplePush(function, 0, time, FRAME::kStartNative);
 744             mAllowNativeFrames = true;
 745         } else if (flags == kMethodExit || flags == kMethodException) {
 746             doMethodPop(event, sCurrentMethod.addr, FRAME::kInterpreted);
 747         } else if (flags == kNativeExit || flags == kNativeException) {
 748             doMethodPop(event, sCurrentMethod.addr, FRAME::kStartNative);
 749         }
 750
 751         // We found a match, so read the next record. When we get to the end
 752         // of the trace, we set the time to the maximum value (~0).
 753         sCurrentMethod = sNextMethod;
 754         if (sNextMethod.time != ~0ull && mTrace->ReadMethod(&sNextMethod)) {
 755             sNextMethod.time = ~0ull;
 756         }
 757     }
 758 }
 759
 760 template<class FRAME, class BASE>
 761 void CallStack<FRAME, BASE>::showStack(FILE *stream)
 762 {
 763     fprintf(stream, "mTop: %d skippedTime: %llu\n", mTop, mSkippedTime);
 764     for (int ii = 0; ii < mTop; ++ii) {
 765         uint32_t addr = mFrames[ii].function->addr;
 766         addr += mFrames[ii].function->region->vstart;
 767         fprintf(stream, "  %d: t %d gt %d f %x 0x%08x 0x%08x %s\n",
 768                 ii, mFrames[ii].time, mFrames[ii].global_time,
 769                 mFrames[ii].flags,
 770                 mFrames[ii].addr, addr,
 771                 mFrames[ii].function->name);
 772     }
 773 }
 774
 775 #endif /* CALL_STACK_H */