// 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 */