diff options
Diffstat (limited to 'emulator/qtools/callstack.h')
| -rw-r--r-- | emulator/qtools/callstack.h | 775 |
1 files changed, 0 insertions, 775 deletions
diff --git a/emulator/qtools/callstack.h b/emulator/qtools/callstack.h deleted file mode 100644 index 8982330..0000000 --- a/emulator/qtools/callstack.h +++ /dev/null @@ -1,775 +0,0 @@ -// Copyright 2006 The Android Open Source Project - -#ifndef CALL_STACK_H -#define CALL_STACK_H - -#include "opcode.h" -#include "armdis.h" - -class CallStackBase { - public: - int getId() { return mId; } - void setId(int id) { mId = id; } - - private: - int mId; -}; - -// Define a template class for the stack frame. The template parameter -// SYM is the symbol_type from the TraceReader<> template class. To -// use the CallStack class, the user derives a subclass of StackFrame -// and defines push() and pop() methods. This derived class is then -// passed as a template parameter to CallStack. -template <class SYM> -class StackFrame { - public: - - virtual ~StackFrame() {}; - - virtual void push(int stackLevel, uint64_t time, CallStackBase *base) {}; - virtual void pop(int stackLevel, uint64_t time, CallStackBase *base) {}; - - typedef SYM symbol_type; - static const uint32_t kCausedException = 0x01; - static const uint32_t kInterpreted = 0x02; - static const uint32_t kStartNative = 0x04; - static const uint32_t kPopBarrier = (kCausedException | kInterpreted - | kStartNative); - - symbol_type *function; // the symbol for the function we entered - uint32_t addr; // return address when this function returns - uint32_t flags; - uint32_t time; // for debugging when a problem occurred - uint32_t global_time; // for debugging when a problem occurred -}; - -template <class FRAME, class BASE = CallStackBase> -class CallStack : public BASE { -public: - typedef FRAME frame_type; - typedef typename FRAME::symbol_type symbol_type; - typedef typename FRAME::symbol_type::region_type region_type; - typedef BASE base_type; - - CallStack(int id, int numFrames, TraceReaderType *trace); - ~CallStack(); - - void updateStack(BBEvent *event, symbol_type *function); - void popAll(uint64_t time); - void threadStart(uint64_t time); - void threadStop(uint64_t time); - - // Set to true if you don't want to see any Java methods ever - void setNativeOnly(bool nativeOnly) { - mNativeOnly = nativeOnly; - } - - int getStackLevel() { return mTop; } - - uint64_t getGlobalTime(uint64_t time) { return time + mSkippedTime; } - void showStack(FILE *stream); - - int mNumFrames; - FRAME *mFrames; - int mTop; // index of the next stack frame to write - -private: - enum Action { NONE, PUSH, POP, NATIVE_PUSH }; - - Action getAction(BBEvent *event, symbol_type *function); - void doMethodAction(BBEvent *event, symbol_type *function); - void doMethodPop(BBEvent *event, uint32_t addr, const uint32_t flags); - void doSimplePush(symbol_type *function, uint32_t addr, - uint64_t time, int flags); - void doSimplePop(uint64_t time); - void doPush(BBEvent *event, symbol_type *function); - void doPop(BBEvent *event, symbol_type *function, Action methodAction); - - TraceReaderType *mTrace; - - // This is a global switch that disables Java methods from appearing - // on the stack. - bool mNativeOnly; - - // This keeps track of whether native frames are currently allowed on the - // stack. - bool mAllowNativeFrames; - - symbol_type mDummyFunction; - region_type mDummyRegion; - - symbol_type *mPrevFunction; - BBEvent mPrevEvent; - - symbol_type *mUserFunction; - BBEvent mUserEvent; // the previous user-mode event - - uint64_t mSkippedTime; - uint64_t mLastRunTime; - - static MethodRec sCurrentMethod; - static MethodRec sNextMethod; -}; - -template<class FRAME, class BASE> -MethodRec CallStack<FRAME, BASE>::sCurrentMethod; -template<class FRAME, class BASE> -MethodRec CallStack<FRAME, BASE>::sNextMethod; - -template<class FRAME, class BASE> -CallStack<FRAME, BASE>::CallStack(int id, int numFrames, TraceReaderType *trace) -{ - mNativeOnly = false; - mTrace = trace; - BASE::setId(id); - mNumFrames = numFrames; - mFrames = new FRAME[mNumFrames]; - mTop = 0; - mAllowNativeFrames = true; - - memset(&mDummyFunction, 0, sizeof(symbol_type)); - memset(&mDummyRegion, 0, sizeof(region_type)); - mDummyFunction.region = &mDummyRegion; - mPrevFunction = &mDummyFunction; - memset(&mPrevEvent, 0, sizeof(BBEvent)); - mUserFunction = &mDummyFunction; - memset(&mUserEvent, 0, sizeof(BBEvent)); - mSkippedTime = 0; - mLastRunTime = 0; - - // Read the first two methods from the trace if we haven't already read - // from the method trace yet. - if (sCurrentMethod.time == 0) { - if (mTrace->ReadMethod(&sCurrentMethod)) { - sCurrentMethod.time = ~0ull; - sNextMethod.time = ~0ull; - } - if (sNextMethod.time != ~0ull && mTrace->ReadMethod(&sNextMethod)) { - sNextMethod.time = ~0ull; - } - } -} - -template<class FRAME, class BASE> -CallStack<FRAME, BASE>::~CallStack() -{ - delete mFrames; -} - -template<class FRAME, class BASE> -void -CallStack<FRAME, BASE>::updateStack(BBEvent *event, symbol_type *function) -{ - if (mNativeOnly) { - // If this is an interpreted function, then use the native VM function - // instead. - if (function->vm_sym != NULL) - function = function->vm_sym; - } else { - doMethodAction(event, function); - } - - Action action = getAction(event, function); - - // Allow native frames if we are executing in the kernel. - if (!mAllowNativeFrames - && (function->region->flags & region_type::kIsKernelRegion) == 0) { - action = NONE; - } - - if (function->vm_sym != NULL) { - function = function->vm_sym; - function->vm_sym = NULL; - } - if (action == PUSH) { - doPush(event, function); - } else if (action == POP) { - doPop(event, function, NONE); - } - -#if 0 - // Pop off native functions before pushing or popping Java methods. - if (action == POP && mPrevFunction->vm_sym == NULL) { - // Pop off the previous function first. - doPop(event, function, NONE); - if (methodAction == POP) { - doPop(event, function, POP); - } else if (methodAction == PUSH) { - doPush(event, function); - } - } else { - if (methodAction != NONE) { - // If the method trace has a push or pop, then do it. - action = methodAction; - } else if (function->vm_sym != NULL) { - // This function is a Java method. Don't push or pop the - // Java method without a corresponding method trace record. - action = NONE; - } - if (action == POP) { - doPop(event, function, methodAction); - } else if (action == PUSH) { - doPush(event, function); - } - } -#endif - - // If the stack is now empty, then push the current function. - if (mTop == 0) { - uint64_t time = event->time - mSkippedTime; - int flags = 0; - if (function->vm_sym != NULL) { - flags = FRAME::kInterpreted; - } - doSimplePush(function, 0, time, 0); - } - - mPrevFunction = function; - mPrevEvent = *event; -} - -template<class FRAME, class BASE> -void -CallStack<FRAME, BASE>::threadStart(uint64_t time) -{ - mSkippedTime += time - mLastRunTime; -} - -template<class FRAME, class BASE> -void -CallStack<FRAME, BASE>::threadStop(uint64_t time) -{ - mLastRunTime = time; -} - -template<class FRAME, class BASE> -typename CallStack<FRAME, BASE>::Action -CallStack<FRAME, BASE>::getAction(BBEvent *event, symbol_type *function) -{ - Action action; - uint32_t offset; - - // Compute the offset from the start of the function to this basic - // block address. - offset = event->bb_addr - function->addr - function->region->base_addr; - - // Get the previously executed instruction - Opcode op = OP_INVALID; - int numInsns = mPrevEvent.num_insns; - uint32_t insn = 0; - if (numInsns > 0) { - insn = mPrevEvent.insns[numInsns - 1]; - if (mPrevEvent.is_thumb) { - insn = insn_unwrap_thumb(insn); - op = decode_insn_thumb(insn); - } else { - op = Arm::decode(insn); - } - } - - // The number of bytes in the previous basic block depends on - // whether the basic block was ARM or THUMB instructions. - int numBytes; - if (mPrevEvent.is_thumb) { - numBytes = numInsns << 1; - } else { - numBytes = numInsns << 2; - } - - // If this basic block follows the previous one, then return NONE. - // If we don't do this, then we may be fooled into thinking this - // is a POP if the previous block ended with a conditional - // (non-executed) ldmia instruction. We do this check before - // checking if we are in a different function because we otherwise - // we might be fooled into thinking this is a PUSH to a new function - // when it is really just a fall-thru into a local kernel symbol - // that just looks like a new function. - uint32_t prev_end_addr = mPrevEvent.bb_addr + numBytes; - if (prev_end_addr == event->bb_addr) { - return NONE; - } - - // If this basic block is in the same function as the last basic block, - // then just return NONE (but see the exceptions below). - // Exception 1: if the function calls itself (offset == 0) then we - // want to push this function. - // Exception 2: if the function returns to itself, then we want - // to pop this function. We detect this case by checking if the last - // instruction in the previous basic block was a load-multiple (ldm) - // and included r15 as one of the loaded registers. - if (function == mPrevFunction) { - if (numInsns > 0) { - // If this is the beginning of the function and the previous - // instruction was not a branch, then it's a PUSH. - if (offset == 0 && op != OP_B && op != OP_THUMB_B) - return PUSH; - - // If the previous instruction was an ldm that loaded r15, - // then it's a POP. - if (offset != 0 && ((op == OP_LDM && (insn & 0x8000)) - || (op == OP_THUMB_POP && (insn & 0x100)))) { - return POP; - } - } - - return NONE; - } - - // We have to figure out if this new function is a call or a - // return. We don't necessarily have a complete call stack (since - // we could have started tracing at any point), so we have to use - // heuristics. If the address we are jumping to is the beginning - // of a function, or if the instruction that took us there was - // either "bl" or "blx" then this is a PUSH. Also, if the - // function offset is non-zero and the previous instruction is a - // branch instruction, we will call it a PUSH. This happens in - // the kernel a lot when there is a branch to an offset from a - // label. A couple more special cases: - // - // - entering a .plt section ("procedure linkage table") is a PUSH, - // - an exception that jumps into the kernel vector entry point - // is also a push. - // - // If the function offset is non-zero and the previous instruction - // is a bx or some non-branch instruction, then it's a POP. - // - // There's another special case that comes up. The user code - // might execute an instruction that returns but before the pc - // starts executing in the caller, a kernel interrupt occurs. - // But it may be hard to tell if this is a return until after - // the kernel interrupt code is done and returns to user space. - // So we save the last user basic block and look at it when - // we come back into user space. - - const uint32_t kIsKernelRegion = region_type::kIsKernelRegion; - - if (((mPrevFunction->region->flags & kIsKernelRegion) == 0) - && (function->region->flags & kIsKernelRegion)) { - // We just switched into the kernel. Save the previous - // user-mode basic block and function. - mUserEvent = mPrevEvent; - mUserFunction = mPrevFunction; - } else if ((mPrevFunction->region->flags & kIsKernelRegion) - && ((function->region->flags & kIsKernelRegion) == 0)) { - // We just switched from kernel to user mode. - return POP; - } - - action = PUSH; - if (offset != 0 && mPrevFunction != &mDummyFunction) { - // We are jumping into the middle of a function, so this is - // probably a return, not a function call. But look at the - // previous instruction first to see if it was a branch-and-link. - - // If the previous instruction was not a branch (and not a - // branch-and-link) then POP; or if it is a "bx" instruction - // then POP because that is used to return from functions. - if (!isBranch(op) || op == OP_BX || op == OP_THUMB_BX) { - action = POP; - } else if (isBranch(op) && !isBranchLink(op)) { - // If the previous instruction was a normal branch to a - // local symbol then don't count it as a push or a pop. - action = NONE; - } - - if (function->flags & symbol_type::kIsVectorTable) - action = PUSH; - } - return action; -} - - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doPush(BBEvent *event, symbol_type *function) -{ - uint64_t time = event->time - mSkippedTime; - - // Check for stack overflow - if (mTop >= mNumFrames) { - // Don't show the stack by default because this generates a lot - // of output and this is seen by users if there is an error when - // post-processing the trace. But this is useful for debugging. -#if 0 - showStack(stderr); -#endif - fprintf(stderr, "Error: stack overflow (%d frames)\n", mTop); - exit(1); - } - - // Compute the return address here because we may need to change - // it if we are popping off a frame for a vector table. - int numBytes; - if (mPrevEvent.is_thumb) { - numBytes = mPrevEvent.num_insns << 1; - } else { - numBytes = mPrevEvent.num_insns << 2; - } - uint32_t retAddr = mPrevEvent.bb_addr + numBytes; - - // If this is a Java method then set the return address to zero. - // We won't be using it for popping the method and it may lead - // to false matches when searching the stack. - if (function->vm_sym != NULL) { - retAddr = 0; - } - -#if 0 - // For debugging only. Show the stack before entering the kernel - // exception-handling code. - if (function->flags & symbol_type::kIsVectorStart) { - printf("stack before entering exception\n"); - showStack(stderr); - } -#endif - - // If the top of stack is a vector table, then pop it - // off before pushing on the new function. Also, change the - // return address for the new function to the return address - // from the vector table. - if (mTop > 0 - && (mFrames[mTop - 1].function->flags & symbol_type::kIsVectorTable)) { - retAddr = mFrames[mTop - 1].addr; - doSimplePop(time); - } - - const uint32_t kIsKernelRegion = region_type::kIsKernelRegion; - - // The following code handles the case where one function, F1, - // calls another function, F2, but the before F2 can start - // executing, it takes a page fault (on the first instruction - // in F2). The kernel is entered, handles the page fault, and - // then returns to the called function. The problem is that - // this looks like a new function call to F2 from the kernel. - // The following code cleans up the stack by popping the - // kernel frames back to F1 (but not including F1). The - // return address for F2 also has to be fixed up to point to - // F1 instead of the kernel. - // - // We detect this case by checking if the previous basic block - // was in the kernel and the current basic block is not. - if ((mPrevFunction->region->flags & kIsKernelRegion) - && ((function->region->flags & kIsKernelRegion) == 0) - && mTop > 0) { - // We are switching from kernel mode to user mode. -#if 0 - // For debugging. - printf(" doPush(): popping to user mode, bb_addr: 0x%08x\n", - event->bb_addr); - showStack(stderr); -#endif - do { - // Pop off the kernel frames until we reach the one that - // caused the exception. - doSimplePop(time); - - // If the next stack frame is the one that caused an - // exception then stop popping frames. - if (mTop > 0 - && (mFrames[mTop - 1].flags & FRAME::kCausedException)) { - mFrames[mTop - 1].flags &= ~FRAME::kCausedException; - retAddr = mFrames[mTop].addr; - break; - } - } while (mTop > 0); -#if 0 - // For debugging - printf(" doPush() popping to level %d, using retAddr 0x%08x\n", - mTop, retAddr); -#endif - } - - // If we are starting an exception handler, then mark the previous - // stack frame so that we know where to return when the exception - // handler finishes. - if ((function->flags & symbol_type::kIsVectorStart) && mTop > 0) - mFrames[mTop - 1].flags |= FRAME::kCausedException; - - // If the function being pushed is a Java method, then mark it on - // the stack so that we don't pop it off until we get a matching - // trace record from the method trace file. - int flags = 0; - if (function->vm_sym != NULL) { - flags = FRAME::kInterpreted; - } - doSimplePush(function, retAddr, time, flags); -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doSimplePush(symbol_type *function, uint32_t addr, - uint64_t time, int flags) -{ - // Check for stack overflow - if (mTop >= mNumFrames) { - showStack(stderr); - fprintf(stderr, "too many stack frames (%d)\n", mTop); - exit(1); - } - - mFrames[mTop].addr = addr; - mFrames[mTop].function = function; - mFrames[mTop].flags = flags; - mFrames[mTop].time = time; - mFrames[mTop].global_time = time + mSkippedTime; - - mFrames[mTop].push(mTop, time, this); - mTop += 1; -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doSimplePop(uint64_t time) -{ - if (mTop <= 0) { - return; - } - - mTop -= 1; - mFrames[mTop].pop(mTop, time, this); - - if (mNativeOnly) - return; - - // If the stack is empty, then allow more native frames. - // Otherwise, if we are transitioning from Java to native, then allow - // more native frames. - // Otherwise, if we are transitioning from native to Java, then disallow - // more native frames. - if (mTop == 0) { - mAllowNativeFrames = true; - } else { - bool newerIsJava = (mFrames[mTop].flags & FRAME::kInterpreted) != 0; - bool olderIsJava = (mFrames[mTop - 1].flags & FRAME::kInterpreted) != 0; - if (newerIsJava && !olderIsJava) { - // We are transitioning from Java to native - mAllowNativeFrames = true; - } else if (!newerIsJava && olderIsJava) { - // We are transitioning from native to Java - mAllowNativeFrames = false; - } - } -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doPop(BBEvent *event, symbol_type *function, - Action methodAction) -{ - uint64_t time = event->time - mSkippedTime; - - // Search backward on the stack for a matching return address. - // The most common case is that we pop one stack frame, but - // sometimes we pop more than one. - int stackLevel; - bool allowMethodPop = (methodAction == POP); - for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) { - if (event->bb_addr == mFrames[stackLevel].addr) { - // We found a matching return address on the stack. - break; - } - - // If this stack frame caused an exception, then do not pop - // this stack frame. - if (mFrames[stackLevel].flags & FRAME::kPopBarrier) { - // If this is a Java method, then allow a pop only if we - // have a matching trace record. - if (mFrames[stackLevel].flags & FRAME::kInterpreted) { - if (allowMethodPop) { - // Allow at most one method pop - allowMethodPop = false; - continue; - } - } - stackLevel += 1; - break; - } - } - - // If we didn't find a matching return address then search the stack - // again for a matching function. - if (stackLevel < 0 || event->bb_addr != mFrames[stackLevel].addr) { - bool allowMethodPop = (methodAction == POP); - for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) { - // Compare the function with the one in the stack frame. - if (function == mFrames[stackLevel].function) { - // We found a matching function. We want to pop up to but not - // including this frame. But allow popping this frame if this - // method called itself and we have a method pop. - if (allowMethodPop && function == mPrevFunction) { - // pop this frame - break; - } - // do not pop this frame - stackLevel += 1; - break; - } - - // If this stack frame caused an exception, then do not pop - // this stack frame. - if (mFrames[stackLevel].flags & FRAME::kPopBarrier) { - // If this is a Java method, then allow a pop only if we - // have a matching trace record. - if (mFrames[stackLevel].flags & FRAME::kInterpreted) { - if (allowMethodPop) { - // Allow at most one method pop - allowMethodPop = false; - continue; - } - } - stackLevel += 1; - break; - } - } - if (stackLevel < 0) - stackLevel = 0; - } - - // Note that if we didn't find a matching stack frame, we will pop - // the whole stack (unless there is a Java method or exception - // frame on the stack). This is intentional because we may have - // started the trace in the middle of an executing program that is - // returning up the stack and we do not know the whole stack. So - // the right thing to do is to empty the stack. - - // If we are emptying the stack, then add the current function - // on top. If the current function is the same as the top of - // stack, then avoid an extraneous pop and push. - if (stackLevel == 0 && mFrames[0].function == function) - stackLevel = 1; - -#if 0 - // If we are popping off a large number of stack frames, then - // we might have a bug. - if (mTop - stackLevel > 7) { - printf("popping thru level %d\n", stackLevel); - showStack(stderr); - } -#endif - - // Pop the stack frames - for (int ii = mTop - 1; ii >= stackLevel; --ii) - doSimplePop(time); - - // Clear the "caused exception" bit on the current stack frame - if (mTop > 0) { - mFrames[mTop - 1].flags &= ~FRAME::kCausedException; - } - - // Also handle the case where F1 calls F2 and F2 returns to - // F1, but before we can execute any instructions in F1, we - // switch to the kernel. Then when we return from the kernel - // we want to pop off F2 from the stack instead of pushing F1 - // on top of F2. To handle this case, we saved the last - // user-mode basic block when we entered the kernel (in - // the getAction() function) and now we can check to see if - // that was a return to F1 instead of a call. We use the - // getAction() function to determine this. - const uint32_t kIsKernelRegion = region_type::kIsKernelRegion; - if ((mPrevFunction->region->flags & kIsKernelRegion) - && ((function->region->flags & kIsKernelRegion) == 0)) { - mPrevEvent = mUserEvent; - mPrevFunction = mUserFunction; - if (getAction(event, function) == POP) { - // We may need to pop more than one frame, so just - // call doPop() again. This won't be an infinite loop - // here because we changed mPrevEvent to the last - // user-mode event. - doPop(event, function, methodAction); - return; - } - } -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::popAll(uint64_t time) -{ - time -= mSkippedTime; - while (mTop != 0) { - doSimplePop(time); - } -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doMethodPop(BBEvent *event, uint32_t addr, - const uint32_t flags) -{ - uint64_t time = event->time - mSkippedTime; - - // Search the stack from the top down for a frame that contains a - // matching method. - int stackLevel; - for (stackLevel = mTop - 1; stackLevel >= 0; --stackLevel) { - if (mFrames[stackLevel].flags & flags) { - // If we are searching for a native method, then don't bother trying - // to match the address. - if (flags == FRAME::kStartNative) - break; - symbol_type *func = mFrames[stackLevel].function; - uint32_t methodAddr = func->region->base_addr + func->addr; - if (methodAddr == addr) { - break; - } - } - } - - // If we found a matching frame then pop the stack up to and including - // that frame. - if (stackLevel >= 0) { - // Pop the stack frames - for (int ii = mTop - 1; ii >= stackLevel; --ii) - doSimplePop(time); - } -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::doMethodAction(BBEvent *event, symbol_type *function) -{ - // If the events get ahead of the method trace, then read ahead until we - // sync up again. This can happen if there is a pop of a method in the - // method trace for which we don't have a previous push. Such an unmatched - // pop can happen because the user can start tracing at any time and so - // there might already be a stack when we start tracing. - while (event->time >= sNextMethod.time) { - sCurrentMethod = sNextMethod; - if (mTrace->ReadMethod(&sNextMethod)) { - sNextMethod.time = ~0ull; - } - } - - if (event->time >= sCurrentMethod.time && event->pid == sCurrentMethod.pid) { - uint64_t time = event->time - mSkippedTime; - int flags = sCurrentMethod.flags; - if (flags == kMethodEnter) { - doSimplePush(function, 0, time, FRAME::kInterpreted); - mAllowNativeFrames = false; - } else if (flags == kNativeEnter) { - doSimplePush(function, 0, time, FRAME::kStartNative); - mAllowNativeFrames = true; - } else if (flags == kMethodExit || flags == kMethodException) { - doMethodPop(event, sCurrentMethod.addr, FRAME::kInterpreted); - } else if (flags == kNativeExit || flags == kNativeException) { - doMethodPop(event, sCurrentMethod.addr, FRAME::kStartNative); - } - - // We found a match, so read the next record. When we get to the end - // of the trace, we set the time to the maximum value (~0). - sCurrentMethod = sNextMethod; - if (sNextMethod.time != ~0ull && mTrace->ReadMethod(&sNextMethod)) { - sNextMethod.time = ~0ull; - } - } -} - -template<class FRAME, class BASE> -void CallStack<FRAME, BASE>::showStack(FILE *stream) -{ - fprintf(stream, "mTop: %d skippedTime: %llu\n", mTop, mSkippedTime); - for (int ii = 0; ii < mTop; ++ii) { - uint32_t addr = mFrames[ii].function->addr; - addr += mFrames[ii].function->region->vstart; - fprintf(stream, " %d: t %d gt %d f %x 0x%08x 0x%08x %s\n", - ii, mFrames[ii].time, mFrames[ii].global_time, - mFrames[ii].flags, - mFrames[ii].addr, addr, - mFrames[ii].function->name); - } -} - -#endif /* CALL_STACK_H */ |